ReactOS  0.4.15-dev-5459-gb85f005
bitstream.h
Go to the documentation of this file.
1 /* ******************************************************************
2  * bitstream
3  * Part of FSE library
4  * Copyright (c) 2013-2020, Yann Collet, Facebook, Inc.
5  *
6  * You can contact the author at :
7  * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
8  *
9  * This source code is licensed under both the BSD-style license (found in the
10  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
11  * in the COPYING file in the root directory of this source tree).
12  * You may select, at your option, one of the above-listed licenses.
13 ****************************************************************** */
14 #ifndef BITSTREAM_H_MODULE
15 #define BITSTREAM_H_MODULE
16 
17 #if defined (__cplusplus)
18 extern "C" {
19 #endif
20 
21 /*
22 * This API consists of small unitary functions, which must be inlined for best performance.
23 * Since link-time-optimization is not available for all compilers,
24 * these functions are defined into a .h to be included.
25 */
26 
27 /*-****************************************
28 * Dependencies
29 ******************************************/
30 #include "mem.h" /* unaligned access routines */
31 #include "compiler.h" /* UNLIKELY() */
32 #include "debug.h" /* assert(), DEBUGLOG(), RAWLOG() */
33 #include "error_private.h" /* error codes and messages */
34 
35 
36 /*=========================================
37 * Target specific
38 =========================================*/
39 #if defined(__BMI__) && defined(__GNUC__)
40 # include <immintrin.h> /* support for bextr (experimental) */
41 #elif defined(__ICCARM__)
42 # include <intrinsics.h>
43 #endif
44 
45 #define STREAM_ACCUMULATOR_MIN_32 25
46 #define STREAM_ACCUMULATOR_MIN_64 57
47 #define STREAM_ACCUMULATOR_MIN ((U32)(MEM_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
48 
49 
50 /*-******************************************
51 * bitStream encoding API (write forward)
52 ********************************************/
53 /* bitStream can mix input from multiple sources.
54  * A critical property of these streams is that they encode and decode in **reverse** direction.
55  * So the first bit sequence you add will be the last to be read, like a LIFO stack.
56  */
57 typedef struct {
58  size_t bitContainer;
59  unsigned bitPos;
60  char* startPtr;
61  char* ptr;
62  char* endPtr;
64 
65 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
66 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
69 
70 /* Start with initCStream, providing the size of buffer to write into.
71 * bitStream will never write outside of this buffer.
72 * `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
73 *
74 * bits are first added to a local register.
75 * Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
76 * Writing data into memory is an explicit operation, performed by the flushBits function.
77 * Hence keep track how many bits are potentially stored into local register to avoid register overflow.
78 * After a flushBits, a maximum of 7 bits might still be stored into local register.
79 *
80 * Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
81 *
82 * Last operation is to close the bitStream.
83 * The function returns the final size of CStream in bytes.
84 * If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
85 */
86 
87 
88 /*-********************************************
89 * bitStream decoding API (read backward)
90 **********************************************/
91 typedef struct {
92  size_t bitContainer;
93  unsigned bitsConsumed;
94  const char* ptr;
95  const char* start;
96  const char* limitPtr;
98 
99 typedef enum { BIT_DStream_unfinished = 0,
102  BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
103  /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
104 
105 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
106 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
108 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
109 
110 
111 /* Start by invoking BIT_initDStream().
112 * A chunk of the bitStream is then stored into a local register.
113 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
114 * You can then retrieve bitFields stored into the local register, **in reverse order**.
115 * Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
116 * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
117 * Otherwise, it can be less than that, so proceed accordingly.
118 * Checking if DStream has reached its end can be performed with BIT_endOfDStream().
119 */
120 
121 
122 /*-****************************************
123 * unsafe API
124 ******************************************/
125 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
126 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
127 
129 /* unsafe version; does not check buffer overflow */
130 
131 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
132 /* faster, but works only if nbBits >= 1 */
133 
134 
135 
136 /*-**************************************************************
137 * Internal functions
138 ****************************************************************/
140 {
141  assert(val != 0);
142  {
143 # if defined(_MSC_VER) /* Visual */
144  unsigned long r=0;
145  return _BitScanReverse ( &r, val ) ? (unsigned)r : 0;
146 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
147  return __builtin_clz (val) ^ 31;
148 # elif defined(__ICCARM__) /* IAR Intrinsic */
149  return 31 - __CLZ(val);
150 # else /* Software version */
151  static const unsigned DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29,
152  11, 14, 16, 18, 22, 25, 3, 30,
153  8, 12, 20, 28, 15, 17, 24, 7,
154  19, 27, 23, 6, 26, 5, 4, 31 };
155  U32 v = val;
156  v |= v >> 1;
157  v |= v >> 2;
158  v |= v >> 4;
159  v |= v >> 8;
160  v |= v >> 16;
161  return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
162 # endif
163  }
164 }
165 
166 /*===== Local Constants =====*/
167 static const unsigned BIT_mask[] = {
168  0, 1, 3, 7, 0xF, 0x1F,
169  0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF,
170  0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF,
171  0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF,
172  0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF,
173  0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits */
174 #define BIT_MASK_SIZE (sizeof(BIT_mask) / sizeof(BIT_mask[0]))
175 
176 /*-**************************************************************
177 * bitStream encoding
178 ****************************************************************/
184  void* startPtr, size_t dstCapacity)
185 {
186  bitC->bitContainer = 0;
187  bitC->bitPos = 0;
188  bitC->startPtr = (char*)startPtr;
189  bitC->ptr = bitC->startPtr;
190  bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->bitContainer);
191  if (dstCapacity <= sizeof(bitC->bitContainer)) return ERROR(dstSize_tooSmall);
192  return 0;
193 }
194 
199  size_t value, unsigned nbBits)
200 {
202  assert(nbBits < BIT_MASK_SIZE);
203  assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
204  bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
205  bitC->bitPos += nbBits;
206 }
207 
212  size_t value, unsigned nbBits)
213 {
214  assert((value>>nbBits) == 0);
215  assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
216  bitC->bitContainer |= value << bitC->bitPos;
217  bitC->bitPos += nbBits;
218 }
219 
224 {
225  size_t const nbBytes = bitC->bitPos >> 3;
226  assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
227  assert(bitC->ptr <= bitC->endPtr);
228  MEM_writeLEST(bitC->ptr, bitC->bitContainer);
229  bitC->ptr += nbBytes;
230  bitC->bitPos &= 7;
231  bitC->bitContainer >>= nbBytes*8;
232 }
233 
240 {
241  size_t const nbBytes = bitC->bitPos >> 3;
242  assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
243  assert(bitC->ptr <= bitC->endPtr);
244  MEM_writeLEST(bitC->ptr, bitC->bitContainer);
245  bitC->ptr += nbBytes;
246  if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
247  bitC->bitPos &= 7;
248  bitC->bitContainer >>= nbBytes*8;
249 }
250 
255 {
256  BIT_addBitsFast(bitC, 1, 1); /* endMark */
257  BIT_flushBits(bitC);
258  if (bitC->ptr >= bitC->endPtr) return 0; /* overflow detected */
259  return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
260 }
261 
262 
263 /*-********************************************************
264 * bitStream decoding
265 **********************************************************/
272 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
273 {
274  if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
275 
276  bitD->start = (const char*)srcBuffer;
277  bitD->limitPtr = bitD->start + sizeof(bitD->bitContainer);
278 
279  if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
280  bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
281  bitD->bitContainer = MEM_readLEST(bitD->ptr);
282  { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
283  bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */
284  if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
285  } else {
286  bitD->ptr = bitD->start;
287  bitD->bitContainer = *(const BYTE*)(bitD->start);
288  switch(srcSize)
289  {
290  case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
291  /* fall-through */
292 
293  case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);
294  /* fall-through */
295 
296  case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);
297  /* fall-through */
298 
299  case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24;
300  /* fall-through */
301 
302  case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16;
303  /* fall-through */
304 
305  case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8;
306  /* fall-through */
307 
308  default: break;
309  }
310  { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
311  bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
312  if (lastByte == 0) return ERROR(corruption_detected); /* endMark not present */
313  }
314  bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
315  }
316 
317  return srcSize;
318 }
319 
320 MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
321 {
322  return bitContainer >> start;
323 }
324 
325 MEM_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
326 {
327  U32 const regMask = sizeof(bitContainer)*8 - 1;
328  /* if start > regMask, bitstream is corrupted, and result is undefined */
329  assert(nbBits < BIT_MASK_SIZE);
330  return (bitContainer >> (start & regMask)) & BIT_mask[nbBits];
331 }
332 
333 MEM_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
334 {
335  assert(nbBits < BIT_MASK_SIZE);
336  return bitContainer & BIT_mask[nbBits];
337 }
338 
345 MEM_STATIC size_t BIT_lookBits(const BIT_DStream_t* bitD, U32 nbBits)
346 {
347  /* arbitrate between double-shift and shift+mask */
348 #if 1
349  /* if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8,
350  * bitstream is likely corrupted, and result is undefined */
351  return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);
352 #else
353  /* this code path is slower on my os-x laptop */
354  U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
355  return ((bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> 1) >> ((regMask-nbBits) & regMask);
356 #endif
357 }
358 
361 MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
362 {
363  U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
364  assert(nbBits >= 1);
365  return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask);
366 }
367 
369 {
370  bitD->bitsConsumed += nbBits;
371 }
372 
377 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits)
378 {
379  size_t const value = BIT_lookBits(bitD, nbBits);
380  BIT_skipBits(bitD, nbBits);
381  return value;
382 }
383 
386 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits)
387 {
388  size_t const value = BIT_lookBitsFast(bitD, nbBits);
389  assert(nbBits >= 1);
390  BIT_skipBits(bitD, nbBits);
391  return value;
392 }
393 
401 {
402  if (UNLIKELY(bitD->ptr < bitD->limitPtr))
403  return BIT_DStream_overflow;
404  assert(bitD->bitsConsumed <= sizeof(bitD->bitContainer)*8);
405  bitD->ptr -= bitD->bitsConsumed >> 3;
406  bitD->bitsConsumed &= 7;
407  bitD->bitContainer = MEM_readLEST(bitD->ptr);
408  return BIT_DStream_unfinished;
409 }
410 
417 {
418  if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* overflow detected, like end of stream */
419  return BIT_DStream_overflow;
420 
421  if (bitD->ptr >= bitD->limitPtr) {
422  return BIT_reloadDStreamFast(bitD);
423  }
424  if (bitD->ptr == bitD->start) {
425  if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
426  return BIT_DStream_completed;
427  }
428  /* start < ptr < limitPtr */
429  { U32 nbBytes = bitD->bitsConsumed >> 3;
431  if (bitD->ptr - nbBytes < bitD->start) {
432  nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
434  }
435  bitD->ptr -= nbBytes;
436  bitD->bitsConsumed -= nbBytes*8;
437  bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD->bitContainer), otherwise bitD->ptr == bitD->start */
438  return result;
439  }
440 }
441 
445 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
446 {
447  return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
448 }
449 
450 #if defined (__cplusplus)
451 }
452 #endif
453 
454 #endif /* BITSTREAM_H_MODULE */
Definition: pdh_main.c:93
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:223
MEM_STATIC size_t MEM_readLEST(const void *memPtr)
Definition: mem.h:378
MEM_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize)
Definition: bitstream.h:272
#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:325
const char * start
Definition: bitstream.h:95
MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
Definition: bitstream.h:416
#define BIT_MASK_SIZE
Definition: bitstream.h:174
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity)
Definition: bitstream.h:183
MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, unsigned nbBits)
Definition: bitstream.h:386
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *bitD)
Definition: bitstream.h:445
static const unsigned BIT_mask[]
Definition: bitstream.h:167
size_t bitContainer
Definition: bitstream.h:58
const char * ptr
Definition: bitstream.h:94
#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:99
size_t bitContainer
Definition: bitstream.h:92
MEM_STATIC void MEM_writeLEST(void *memPtr, size_t val)
Definition: mem.h:386
#define MEM_STATIC
Definition: mem.h:39
MEM_STATIC void BIT_flushBits(BIT_CStream_t *bitC)
Definition: bitstream.h:239
unsigned bitPos
Definition: bitstream.h:59
MEM_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
Definition: bitstream.h:333
MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t *bitD, U32 nbBits)
Definition: bitstream.h:361
MEM_STATIC void BIT_skipBits(BIT_DStream_t *bitD, U32 nbBits)
Definition: bitstream.h:368
MEM_STATIC size_t BIT_lookBits(const BIT_DStream_t *bitD, U32 nbBits)
Definition: bitstream.h:345
#define UNLIKELY(x)
Definition: compiler.h:162
unsigned bitsConsumed
Definition: bitstream.h:93
const char * limitPtr
Definition: bitstream.h:96
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:198
const GLdouble * v
Definition: gl.h:2040
MEM_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, unsigned nbBits)
Definition: bitstream.h:377
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:61
char * endPtr
Definition: bitstream.h:62
MEM_STATIC BIT_DStream_status BIT_reloadDStreamFast(BIT_DStream_t *bitD)
Definition: bitstream.h:400
MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
Definition: bitstream.h:320
char * startPtr
Definition: bitstream.h:60
MEM_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
Definition: bitstream.h:211
#define memset(x, y, z)
Definition: compat.h:39
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
Definition: bitstream.h:254
unsigned int U32
Definition: xxhash.c:195
static unsigned(__cdecl *hash_bstr)(bstr_t s)