2
* The Progressive Graphics File; http://www.libpgf.org
4
* $Date: 2006-06-04 22:05:59 +0200 (So, 04 Jun 2006) $
7
* This file Copyright (C) 2006 xeraina GmbH, Switzerland
9
* This program is free software; you can redistribute it and/or
10
* modify it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE
11
* as published by the Free Software Foundation; either version 2.1
12
* of the License, or (at your option) any later version.
14
* This program is distributed in the hope that it will be useful,
15
* but WITHOUT ANY WARRANTY; without even the implied warranty of
16
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17
* GNU General Public License for more details.
19
* You should have received a copy of the GNU General Public License
20
* along with this program; if not, write to the Free Software
21
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
24
//////////////////////////////////////////////////////////////////////
26
/// @brief PGF bit-stream operations
29
#ifndef PGF_BITSTREAM_H
30
#define PGF_BITSTREAM_H
35
//static const WordWidth = 32;
36
//static const WordWidthLog = 5;
37
static const UINT32 Filled = 0xFFFFFFFF;
39
/// @brief Make 64 bit unsigned integer from two 32 bit unsigned integers
40
#define MAKEU64(a, b) ((UINT64) (((UINT32) (a)) | ((UINT64) ((UINT32) (b))) << 32))
42
// these procedures have to be inlined because of performance reasons
44
//////////////////////////////////////////////////////////////////////
45
/// Set one bit of a bit stream to 1
46
/// @param stream A bit stream stored in array of unsigned integers
47
/// @param pos A valid zero-based position in the bit stream
48
inline void SetBit(UINT32* stream, UINT32 pos) {
49
stream[pos >> WordWidthLog] |= (1 << (pos%WordWidth));
52
//////////////////////////////////////////////////////////////////////
53
/// Set one bit of a bit stream to 0
54
/// @param stream A bit stream stored in array of unsigned integers
55
/// @param pos A valid zero-based position in the bit stream
56
inline void ClearBit(UINT32* stream, UINT32 pos) {
57
stream[pos >> WordWidthLog] &= ~(1 << (pos%WordWidth));
60
//////////////////////////////////////////////////////////////////////
61
/// Return one bit of a bit stream
62
/// @param stream A bit stream stored in array of unsigned integers
63
/// @param pos A valid zero-based position in the bit stream
64
/// @return bit at position pos of bit stream stream
65
inline bool GetBit(UINT32* stream, UINT32 pos) {
66
return (stream[pos >> WordWidthLog] & (1 << (pos%WordWidth))) > 0;
70
//////////////////////////////////////////////////////////////////////
71
/// Compare k-bit binary representation of stream at position pos with val
72
/// @param stream A bit stream stored in array of unsigned integers
73
/// @param pos A valid zero-based position in the bit stream
74
/// @param k Number of bits to compare
75
/// @param val Value to compare with
76
/// @return true if equal
77
inline bool CompareBitBlock(UINT32* stream, UINT32 pos, UINT32 k, UINT32 val) {
78
const UINT32 iLoInt = pos >> WordWidthLog;
79
const UINT32 iHiInt = (pos + k - 1) >> WordWidthLog;
80
ASSERT(iLoInt <= iHiInt);
81
const UINT32 mask = (Filled >> (WordWidth - k));
83
if (iLoInt == iHiInt) {
84
// fits into one integer
86
val <<= (pos%WordWidth);
87
return (stream[iLoInt] & val) == val;
89
// must be splitted over integer boundary
90
UINT64 v1 = MAKEU64(stream[iLoInt], stream[iHiInt]);
91
UINT64 v2 = UINT64(val & mask) << (pos%WordWidth);
92
return (v1 & v2) == v2;
96
//////////////////////////////////////////////////////////////////////
97
/// Store k-bit binary representation of val in stream at position pos
98
/// @param stream A bit stream stored in array of unsigned integers
99
/// @param pos A valid zero-based position in the bit stream
100
/// @param val Value to store in stream at position pos
101
/// @param k Number of bits of integer representation of val
102
inline void SetValueBlock(UINT32* stream, UINT32 pos, UINT32 val, UINT32 k) {
103
const UINT32 offset = pos%WordWidth;
104
const UINT32 iLoInt = pos >> WordWidthLog;
105
const UINT32 iHiInt = (pos + k - 1) >> WordWidthLog;
106
ASSERT(iLoInt <= iHiInt);
107
const UINT32 loMask = Filled << offset;
108
const UINT32 hiMask = Filled >> (WordWidth - 1 - ((pos + k - 1)%WordWidth));
110
if (iLoInt == iHiInt) {
111
// fits into one integer
112
stream[iLoInt] &= ~(loMask & hiMask); // clear bits
113
stream[iLoInt] |= val << offset; // write value
115
// must be splitted over integer boundary
116
stream[iLoInt] &= ~loMask; // clear bits
117
stream[iLoInt] |= val << offset; // write lower part of value
118
stream[iHiInt] &= ~hiMask; // clear bits
119
stream[iHiInt] |= val >> (WordWidth - offset); // write higher part of value
123
//////////////////////////////////////////////////////////////////////
124
/// Read k-bit number from stream at position pos
125
/// @param stream A bit stream stored in array of unsigned integers
126
/// @param pos A valid zero-based position in the bit stream
127
/// @param k Number of bits to read: 1 <= k <= 32
128
inline UINT32 GetValueBlock(UINT32* stream, UINT32 pos, UINT32 k) {
129
UINT32 count, hiCount;
130
const UINT32 iLoInt = pos >> WordWidthLog; // integer of first bit
131
const UINT32 iHiInt = (pos + k - 1) >> WordWidthLog; // integer of last bit
132
const UINT32 loMask = Filled << (pos%WordWidth);
133
const UINT32 hiMask = Filled >> (WordWidth - 1 - ((pos + k - 1)%WordWidth));
135
if (iLoInt == iHiInt) {
136
// inside integer boundary
137
count = stream[iLoInt] & (loMask & hiMask);
138
count >>= pos%WordWidth;
140
// overlapping integer boundary
141
count = stream[iLoInt] & loMask;
142
count >>= pos%WordWidth;
143
hiCount = stream[iHiInt] & hiMask;
144
hiCount <<= WordWidth - (pos%WordWidth);
150
//////////////////////////////////////////////////////////////////////
151
/// Clear block of size at least len at position pos in stream
152
/// @param stream A bit stream stored in array of unsigned integers
153
/// @param pos A valid zero-based position in the bit stream
154
/// @param len Number of bits set to 0
155
inline void ClearBitBlock(UINT32* stream, UINT32 pos, UINT32 len) {
157
const UINT32 iFirstInt = pos >> WordWidthLog;
158
const UINT32 iLastInt = (pos + len - 1) >> WordWidthLog;
160
const UINT32 startMask = Filled << (pos%WordWidth);
161
// const UINT32 endMask=Filled>>(WordWidth-1-((pos+len-1)%WordWidth));
163
if (iFirstInt == iLastInt) {
164
stream[iFirstInt] &= ~(startMask /*& endMask*/);
166
stream[iFirstInt] &= ~startMask;
167
for (UINT32 i = iFirstInt + 1; i <= iLastInt; i++) { // changed <=
170
//stream[iLastInt] &= ~endMask;
174
//////////////////////////////////////////////////////////////////////
175
/// Set block of size at least len at position pos in stream
176
/// @param stream A bit stream stored in array of unsigned integers
177
/// @param pos A valid zero-based position in the bit stream
178
/// @param len Number of bits set to 1
179
inline void SetBitBlock(UINT32* stream, UINT32 pos, UINT32 len) {
182
const UINT32 iFirstInt = pos >> WordWidthLog;
183
const UINT32 iLastInt = (pos + len - 1) >> WordWidthLog;
185
const UINT32 startMask = Filled << (pos%WordWidth);
186
// const UINT32 endMask=Filled>>(WordWidth-1-((pos+len-1)%WordWidth));
188
if (iFirstInt == iLastInt) {
189
stream[iFirstInt] |= (startMask /*& endMask*/);
191
stream[iFirstInt] |= startMask;
192
for (UINT32 i = iFirstInt + 1; i <= iLastInt; i++) { // changed <=
195
//stream[iLastInt] &= ~endMask;
199
//////////////////////////////////////////////////////////////////////
200
/// Returns the distance to the next 1 in stream at position pos.
201
/// If no 1 is found within len bits, then len is returned.
202
/// @param stream A bit stream stored in array of unsigned integers
203
/// @param pos A valid zero-based position in the bit stream
204
/// @param len size of search area (in bits)
205
/// return The distance to the next 1 in stream at position pos
206
inline UINT32 SeekBitRange(UINT32* stream, UINT32 pos, UINT32 len) {
208
UINT32 testMask = 1 << (pos%WordWidth);
209
UINT32* word = stream + (pos >> WordWidthLog);
211
while (((*word & testMask) == 0) && (count < len)) {
215
word++; testMask = 1;
217
// fast steps if all bits in a word are zero
218
while ((count + WordWidth <= len) && (*word == 0)) {
228
//////////////////////////////////////////////////////////////////////
229
/// Returns the distance to the next 0 in stream at position pos.
230
/// If no 0 is found within len bits, then len is returned.
231
/// @param stream A bit stream stored in array of unsigned integers
232
/// @param pos A valid zero-based position in the bit stream
233
/// @param len size of search area (in bits)
234
/// return The distance to the next 0 in stream at position pos
235
inline UINT32 SeekBit1Range(UINT32* stream, UINT32 pos, UINT32 len) {
237
UINT32 testMask = 1 << (pos%WordWidth);
238
UINT32* word = stream + (pos >> WordWidthLog);
240
while (((*word & testMask) != 0) && (count < len)) {
244
word++; testMask = 1;
246
// fast steps if all bits in a word are one
247
while ((count + WordWidth <= len) && (*word == Filled)) {
256
//////////////////////////////////////////////////////////////////////
257
/// Compute bit position of the next 32-bit word
258
/// @param pos current bit stream position
259
/// @return bit position of next 32-bit word
260
inline UINT32 AlignWordPos(UINT32 pos) {
261
// return ((pos + WordWidth - 1) >> WordWidthLog) << WordWidthLog;
262
return (pos + WordWidth - 1) & WordMask;
265
//////////////////////////////////////////////////////////////////////
266
/// Compute number of the 32-bit words
267
/// @param pos Current bit stream position
268
/// @return Number of 32-bit words
269
inline UINT32 NumberOfWords(UINT32 pos) {
270
return (pos + WordWidth - 1) >> WordWidthLog;
272
#endif //PGF_BITSTREAM_H