ReactOS 0.4.15-dev-5829-g6b6a045
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)
18extern "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 */
57typedef struct {
59 unsigned bitPos;
60 char* startPtr;
61 char* ptr;
62 char* endPtr;
64
65MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
66MEM_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**********************************************/
91typedef struct {
93 unsigned bitsConsumed;
94 const char* ptr;
95 const char* start;
96 const char* limitPtr;
98
99typedef 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
105MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
106MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
108MEM_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******************************************/
125MEM_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
131MEM_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 =====*/
167static 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**********************************************************/
272MEM_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
320MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
321{
322 return bitContainer >> start;
323}
324
325MEM_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
333MEM_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
345MEM_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
361MEM_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
377MEM_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
386MEM_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))
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);
409}
410
417{
418 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* overflow detected, like end of stream */
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;
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
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 */
MEM_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize)
Definition: bitstream.h:272
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
Definition: bitstream.h:254
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
MEM_STATIC void BIT_skipBits(BIT_DStream_t *bitD, U32 nbBits)
Definition: bitstream.h:368
MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
Definition: bitstream.h:416
MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
Definition: bitstream.h:320
MEM_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, unsigned nbBits)
Definition: bitstream.h:377
MEM_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
Definition: bitstream.h:333
MEM_STATIC void BIT_flushBits(BIT_CStream_t *bitC)
Definition: bitstream.h:239
MEM_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
Definition: bitstream.h:325
BIT_DStream_status
Definition: bitstream.h:99
@ BIT_DStream_endOfBuffer
Definition: bitstream.h:100
@ BIT_DStream_overflow
Definition: bitstream.h:102
@ BIT_DStream_unfinished
Definition: bitstream.h:99
@ BIT_DStream_completed
Definition: bitstream.h:101
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_endOfDStream(const BIT_DStream_t *bitD)
Definition: bitstream.h:445
MEM_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
Definition: bitstream.h:198
static const unsigned BIT_mask[]
Definition: bitstream.h:167
#define BIT_MASK_SIZE
Definition: bitstream.h:174
MEM_STATIC size_t BIT_lookBits(const BIT_DStream_t *bitD, U32 nbBits)
Definition: bitstream.h:345
MEM_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
Definition: bitstream.h:211
MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t *bitD, U32 nbBits)
Definition: bitstream.h:361
MEM_STATIC BIT_DStream_status BIT_reloadDStreamFast(BIT_DStream_t *bitD)
Definition: bitstream.h:400
MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC)
Definition: bitstream.h:223
#define assert(x)
Definition: debug.h:53
#define UNLIKELY(x)
Definition: compiler.h:162
#define MEM_STATIC_ASSERT(c)
Definition: mem.h:47
MEM_STATIC size_t MEM_readLEST(const void *memPtr)
Definition: mem.h:378
MEM_STATIC void MEM_writeLEST(void *memPtr, size_t val)
Definition: mem.h:386
#define MEM_STATIC
Definition: mem.h:39
__kernel_size_t size_t
Definition: linux.h:237
#define ERROR(name)
Definition: error_private.h:53
GLuint start
Definition: gl.h:1545
const GLdouble * v
Definition: gl.h:2040
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLuint GLfloat * val
Definition: glext.h:7180
GLuint64EXT * result
Definition: glext.h:11304
unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask)
Definition: intrin_arm.h:180
static unsigned(__cdecl *hash_bstr)(bstr_t s)
#define memset(x, y, z)
Definition: compat.h:39
size_t bitContainer
Definition: bitstream.h:58
char * endPtr
Definition: bitstream.h:62
char * ptr
Definition: bitstream.h:61
char * startPtr
Definition: bitstream.h:60
unsigned bitPos
Definition: bitstream.h:59
const char * ptr
Definition: bitstream.h:94
const char * start
Definition: bitstream.h:95
unsigned bitsConsumed
Definition: bitstream.h:93
size_t bitContainer
Definition: bitstream.h:92
const char * limitPtr
Definition: bitstream.h:96
Definition: pdh_main.c:94
unsigned char BYTE
Definition: xxhash.c:193
unsigned int U32
Definition: xxhash.c:195