ReactOS  0.4.15-dev-1374-g8d3e80e
bitstream.h
Go to the documentation of this file.
1 /* ******************************************************************
2  bitstream
3  Part of FSE library
4  Copyright (C) 2013-present, Yann Collet.
5 
6  BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
7 
8  Redistribution and use in source and binary forms, with or without
9  modification, are permitted provided that the following conditions are
10  met:
11 
12  * Redistributions of source code must retain the above copyright
13  notice, this list of conditions and the following disclaimer.
14  * Redistributions in binary form must reproduce the above
15  copyright notice, this list of conditions and the following disclaimer
16  in the documentation and/or other materials provided with the
17  distribution.
18 
19  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 
31  You can contact the author at :
32  - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
33 ****************************************************************** */
34 #ifndef BITSTREAM_H_MODULE
35 #define BITSTREAM_H_MODULE
36 
37 #if defined (__cplusplus)
38 extern "C" {
39 #endif
40 
41 /*
42 * This API consists of small unitary functions, which must be inlined for best performance.
43 * Since link-time-optimization is not available for all compilers,
44 * these functions are defined into a .h to be included.
45 */
46 
47 /*-****************************************
48 * Dependencies
49 ******************************************/
50 #include "mem.h" /* unaligned access routines */
51 #include "debug.h" /* assert(), DEBUGLOG(), RAWLOG() */
52 #include "error_private.h" /* error codes and messages */
53 
54 
55 /*=========================================
56 * Target specific
57 =========================================*/
58 #if defined(__BMI__) && defined(__GNUC__)
59 # include <immintrin.h> /* support for bextr (experimental) */
60 #endif
61 
62 #define STREAM_ACCUMULATOR_MIN_32 25
63 #define STREAM_ACCUMULATOR_MIN_64 57
64 #define STREAM_ACCUMULATOR_MIN ((U32)(MEM_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
65 
66 
67 /*-******************************************
68 * bitStream encoding API (write forward)
69 ********************************************/
70 /* bitStream can mix input from multiple sources.
71  * A critical property of these streams is that they encode and decode in **reverse** direction.
72  * So the first bit sequence you add will be the last to be read, like a LIFO stack.
73  */
74 typedef struct {
75  size_t bitContainer;
76  unsigned bitPos;
77  char* startPtr;
78  char* ptr;
79  char* endPtr;
81 
82 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
83 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
86 
87 /* Start with initCStream, providing the size of buffer to write into.
88 * bitStream will never write outside of this buffer.
89 * `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
90 *
91 * bits are first added to a local register.
92 * Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
93 * Writing data into memory is an explicit operation, performed by the flushBits function.
94 * Hence keep track how many bits are potentially stored into local register to avoid register overflow.
95 * After a flushBits, a maximum of 7 bits might still be stored into local register.
96 *
97 * Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
98 *
99 * Last operation is to close the bitStream.
100 * The function returns the final size of CStream in bytes.
101 * If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
102 */
103 
104 
105 /*-********************************************
106 * bitStream decoding API (read backward)
107 **********************************************/
108 typedef struct {
109  size_t bitContainer;
110  unsigned bitsConsumed;
111  const char* ptr;
112  const char* start;
113  const char* limitPtr;
114 } BIT_DStream_t;
115 
116 typedef enum { BIT_DStream_unfinished = 0,
119  BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
120  /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
121 
122 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
123 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
125 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
126 
127 
128 /* Start by invoking BIT_initDStream().
129 * A chunk of the bitStream is then stored into a local register.
130 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
131 * You can then retrieve bitFields stored into the local register, **in reverse order**.
132 * Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
133 * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
134 * Otherwise, it can be less than that, so proceed accordingly.
135 * Checking if DStream has reached its end can be performed with BIT_endOfDStream().
136 */
137 
138 
139 /*-****************************************
140 * unsafe API
141 ******************************************/
142 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
143 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
144 
146 /* unsafe version; does not check buffer overflow */
147 
148 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
149 /* faster, but works only if nbBits >= 1 */
150 
151 
152 
153 /*-**************************************************************
154 * Internal functions
155 ****************************************************************/
157 {
158  assert(val != 0);
159  {
160 # if defined(_MSC_VER) /* Visual */
161  unsigned long r=0;
162  _BitScanReverse ( &r, val );
163  return (unsigned) r;
164 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
165  return 31 - __builtin_clz (val);
166 # else /* Software version */
167  static const unsigned DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29,
168  11, 14, 16, 18, 22, 25, 3, 30,
169  8, 12, 20, 28, 15, 17, 24, 7,
170  19, 27, 23, 6, 26, 5, 4, 31 };
171  U32 v = val;
172  v |= v >> 1;
173  v |= v >> 2;
174  v |= v >> 4;
175  v |= v >> 8;
176  v |= v >> 16;
177  return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
178 # endif
179  }
180 }
181 
182 /*===== Local Constants =====*/
183 static const unsigned BIT_mask[] = {
184  0, 1, 3, 7, 0xF, 0x1F,
185  0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF,
186  0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF,
187  0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF,
188  0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF,
189  0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits */
190 #define BIT_MASK_SIZE (sizeof(BIT_mask) / sizeof(BIT_mask[0]))
191 
192 /*-**************************************************************
193 * bitStream encoding
194 ****************************************************************/
200  void* startPtr, size_t dstCapacity)
201 {
202  bitC->bitContainer = 0;
203  bitC->bitPos = 0;
204  bitC->startPtr = (char*)startPtr;
205  bitC->ptr = bitC->startPtr;
206  bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->bitContainer);
207  if (dstCapacity <= sizeof(bitC->bitContainer)) return ERROR(dstSize_tooSmall);
208  return 0;
209 }
210 
215  size_t value, unsigned nbBits)
216 {
218  assert(nbBits < BIT_MASK_SIZE);
219  assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
220  bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
221  bitC->bitPos += nbBits;
222 }
223 
228  size_t value, unsigned nbBits)
229 {
230  assert((value>>nbBits) == 0);
231  assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
232  bitC->bitContainer |= value << bitC->bitPos;
233  bitC->bitPos += nbBits;
234 }
235 
240 {
241  size_t const nbBytes = bitC->bitPos >> 3;
242  assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
243  MEM_writeLEST(bitC->ptr, bitC->bitContainer);
244  bitC->ptr += nbBytes;
245  assert(bitC->ptr <= bitC->endPtr);
246  bitC->bitPos &= 7;
247  bitC->bitContainer >>= nbBytes*8;
248 }
249 
256 {
257  size_t const nbBytes = bitC->bitPos >> 3;
258  assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
259  MEM_writeLEST(bitC->ptr, bitC->bitContainer);
260  bitC->ptr += nbBytes;
261  if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
262  bitC->bitPos &= 7;
263  bitC->bitContainer >>= nbBytes*8;
264 }
265 
270 {
271  BIT_addBitsFast(bitC, 1, 1); /* endMark */
272  BIT_flushBits(bitC);
273  if (bitC->ptr >= bitC->endPtr) return 0; /* overflow detected */
274  return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
275 }
276 
277 
278 /*-********************************************************
279 * bitStream decoding
280 **********************************************************/
287 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
288 {
289  if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
290 
291  bitD->start = (const char*)srcBuffer;
292  bitD->limitPtr = bitD->start + sizeof(bitD->bitContainer);
293 
294  if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
295  bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
296  bitD->bitContainer = MEM_readLEST(bitD->ptr);
297  { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
298  bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */
299  if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
300  } else {
301  bitD->ptr = bitD->start;
302  bitD->bitContainer = *(const BYTE*)(bitD->start);
303  switch(srcSize)
304  {
305  case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
306  /* fall-through */
307 
308  case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);
309  /* fall-through */
310 
311  case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);
312  /* fall-through */
313 
314  case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24;
315  /* fall-through */
316 
317  case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16;
318  /* fall-through */
319 
320  case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8;
321  /* fall-through */
322 
323  default: break;
324  }
325  { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
326  bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
327  if (lastByte == 0) return ERROR(corruption_detected); /* endMark not present */
328  }
329  bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
330  }
331 
332  return srcSize;
333 }
334 
335 MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
336 {
337  return bitContainer >> start;
338 }
339 
340 MEM_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
341 {
342  U32 const regMask = sizeof(bitContainer)*8 - 1;
343  /* if start > regMask, bitstream is corrupted, and result is undefined */
344  assert(nbBits < BIT_MASK_SIZE);
345  return (bitContainer >> (start & regMask)) & BIT_mask[nbBits];
346 }
347 
348 MEM_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
349 {
350  assert(nbBits < BIT_MASK_SIZE);
351  return bitContainer & BIT_mask[nbBits];
352 }
353 
360 MEM_STATIC size_t BIT_lookBits(const BIT_DStream_t* bitD, U32 nbBits)
361 {
362  /* arbitrate between double-shift and shift+mask */
363 #if 1
364  /* if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8,
365  * bitstream is likely corrupted, and result is undefined */
366  return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);
367 #else
368  /* this code path is slower on my os-x laptop */
369  U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
370  return ((bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> 1) >> ((regMask-nbBits) & regMask);
371 #endif
372 }
373 
376 MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
377 {
378  U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
379  assert(nbBits >= 1);
380  return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask);
381 }
382 
384 {
385  bitD->bitsConsumed += nbBits;
386 }
387 
393 {
394  size_t const value = BIT_lookBits(bitD, nbBits);
395  BIT_skipBits(bitD, nbBits);
396  return value;
397 }
398 
402 {
403  size_t const value = BIT_lookBitsFast(bitD, nbBits);
404  assert(nbBits >= 1);
405  BIT_skipBits(bitD, nbBits);
406  return value;
407 }
408 
415 {
416  if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* overflow detected, like end of stream */
417  return BIT_DStream_overflow;
418 
419  if (bitD->ptr >= bitD->limitPtr) {
420  bitD->ptr -= bitD->bitsConsumed >> 3;
421  bitD->bitsConsumed &= 7;
422  bitD->bitContainer = MEM_readLEST(bitD->ptr);
423  return BIT_DStream_unfinished;
424  }
425  if (bitD->ptr == bitD->start) {
426  if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
427  return BIT_DStream_completed;
428  }
429  /* start < ptr < limitPtr */
430  { U32 nbBytes = bitD->bitsConsumed >> 3;
432  if (bitD->ptr - nbBytes < bitD->start) {
433  nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
435  }
436  bitD->ptr -= nbBytes;
437  bitD->bitsConsumed -= nbBytes*8;
438  bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD->bitContainer), otherwise bitD->ptr == bitD->start */
439  return result;
440  }
441 }
442 
446 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
447 {
448  return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
449 }
450 
451 #if defined (__cplusplus)
452 }
453 #endif
454 
455 #endif /* BITSTREAM_H_MODULE */
GLuint64EXT * result
Definition: glext.h:11304
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
#define ERROR(name)
Definition: error_private.h:53
MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC)
Definition: bitstream.h:239
MEM_STATIC size_t MEM_readLEST(const void *memPtr)
Definition: mem.h:305
MEM_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize)
Definition: bitstream.h:287
#define assert(x)
Definition: debug.h:53
MEM_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
Definition: bitstream.h:340
const char * start
Definition: bitstream.h:112
MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
Definition: bitstream.h:414
#define BIT_MASK_SIZE
Definition: bitstream.h:190
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity)
Definition: bitstream.h:199
MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, unsigned nbBits)
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:156
MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *bitD)
Definition: bitstream.h:446
static const unsigned BIT_mask[]
Definition: bitstream.h:183
size_t bitContainer
Definition: bitstream.h:75
const char * ptr
Definition: bitstream.h:111
#define MEM_STATIC_ASSERT(c)
Definition: mem.h:47
GLuint GLfloat * val
Definition: glext.h:7180
__kernel_size_t size_t
Definition: linux.h:237
BIT_DStream_status
Definition: bitstream.h:116
size_t bitContainer
Definition: bitstream.h:109
MEM_STATIC void MEM_writeLEST(void *memPtr, size_t val)
Definition: mem.h:313
#define MEM_STATIC
Definition: mem.h:39
MEM_STATIC void BIT_flushBits(BIT_CStream_t *bitC)
Definition: bitstream.h:255
unsigned bitPos
Definition: bitstream.h:76
MEM_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
Definition: bitstream.h:348
MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t *bitD, U32 nbBits)
Definition: bitstream.h:376
MEM_STATIC void BIT_skipBits(BIT_DStream_t *bitD, U32 nbBits)
Definition: bitstream.h:383
MEM_STATIC size_t BIT_lookBits(const BIT_DStream_t *bitD, U32 nbBits)
Definition: bitstream.h:360
unsigned bitsConsumed
Definition: bitstream.h:110
const char * limitPtr
Definition: bitstream.h:113
GLsizei const GLfloat * value
Definition: glext.h:6069
unsigned char BYTE
Definition: xxhash.c:193
MEM_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
Definition: bitstream.h:214
const GLdouble * v
Definition: gl.h:2040
MEM_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, unsigned nbBits)
unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask)
Definition: intrin_arm.h:180
GLuint start
Definition: gl.h:1545
char * ptr
Definition: bitstream.h:78
char * endPtr
Definition: bitstream.h:79
MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
Definition: bitstream.h:335
char * startPtr
Definition: bitstream.h:77
MEM_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
Definition: bitstream.h:227
#define memset(x, y, z)
Definition: compat.h:39
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
Definition: bitstream.h:269
unsigned int U32
Definition: xxhash.c:195