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 #elif defined(__ICCARM__)
61 # include <intrinsics.h>
62 #endif
63
64 #define STREAM_ACCUMULATOR_MIN_32 25
65 #define STREAM_ACCUMULATOR_MIN_64 57
66 #define STREAM_ACCUMULATOR_MIN ((U32)(MEM_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
67
68
69 /*-******************************************
70 * bitStream encoding API (write forward)
71 ********************************************/
72 /* bitStream can mix input from multiple sources.
73 * A critical property of these streams is that they encode and decode in **reverse** direction.
74 * So the first bit sequence you add will be the last to be read, like a LIFO stack.
75 */
76 typedef struct {
77 size_t bitContainer;
78 unsigned bitPos;
79 char* startPtr;
80 char* ptr;
81 char* endPtr;
82 } BIT_CStream_t;
83
84 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
85 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
86 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC);
87 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC);
88
89 /* Start with initCStream, providing the size of buffer to write into.
90 * bitStream will never write outside of this buffer.
91 * `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
92 *
93 * bits are first added to a local register.
94 * Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
95 * Writing data into memory is an explicit operation, performed by the flushBits function.
96 * Hence keep track how many bits are potentially stored into local register to avoid register overflow.
97 * After a flushBits, a maximum of 7 bits might still be stored into local register.
98 *
99 * Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
100 *
101 * Last operation is to close the bitStream.
102 * The function returns the final size of CStream in bytes.
103 * If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
104 */
105
106
107 /*-********************************************
108 * bitStream decoding API (read backward)
109 **********************************************/
110 typedef struct {
111 size_t bitContainer;
112 unsigned bitsConsumed;
113 const char* ptr;
114 const char* start;
115 const char* limitPtr;
116 } BIT_DStream_t;
117
118 typedef enum { BIT_DStream_unfinished = 0,
119 BIT_DStream_endOfBuffer = 1,
120 BIT_DStream_completed = 2,
121 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
122 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
123
124 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
125 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
126 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
127 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
128
129
130 /* Start by invoking BIT_initDStream().
131 * A chunk of the bitStream is then stored into a local register.
132 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
133 * You can then retrieve bitFields stored into the local register, **in reverse order**.
134 * Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
135 * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
136 * Otherwise, it can be less than that, so proceed accordingly.
137 * Checking if DStream has reached its end can be performed with BIT_endOfDStream().
138 */
139
140
141 /*-****************************************
142 * unsafe API
143 ******************************************/
144 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
145 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
146
147 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);
148 /* unsafe version; does not check buffer overflow */
149
150 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
151 /* faster, but works only if nbBits >= 1 */
152
153
154
155 /*-**************************************************************
156 * Internal functions
157 ****************************************************************/
BIT_highbit32(U32 val)158 MEM_STATIC unsigned BIT_highbit32 (U32 val)
159 {
160 assert(val != 0);
161 {
162 # if defined(_MSC_VER) /* Visual */
163 unsigned long r=0;
164 _BitScanReverse ( &r, val );
165 return (unsigned) r;
166 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
167 return 31 - __builtin_clz (val);
168 # elif defined(__ICCARM__) /* IAR Intrinsic */
169 return 31 - __CLZ(val);
170 # else /* Software version */
171 static const unsigned DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29,
172 11, 14, 16, 18, 22, 25, 3, 30,
173 8, 12, 20, 28, 15, 17, 24, 7,
174 19, 27, 23, 6, 26, 5, 4, 31 };
175 U32 v = val;
176 v |= v >> 1;
177 v |= v >> 2;
178 v |= v >> 4;
179 v |= v >> 8;
180 v |= v >> 16;
181 return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
182 # endif
183 }
184 }
185
186 /*===== Local Constants =====*/
187 static const unsigned BIT_mask[] = {
188 0, 1, 3, 7, 0xF, 0x1F,
189 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF,
190 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF,
191 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF,
192 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF,
193 0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits */
194 #define BIT_MASK_SIZE (sizeof(BIT_mask) / sizeof(BIT_mask[0]))
195
196 /*-**************************************************************
197 * bitStream encoding
198 ****************************************************************/
199 /*! BIT_initCStream() :
200 * `dstCapacity` must be > sizeof(size_t)
201 * @return : 0 if success,
202 * otherwise an error code (can be tested using ERR_isError()) */
BIT_initCStream(BIT_CStream_t * bitC,void * startPtr,size_t dstCapacity)203 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC,
204 void* startPtr, size_t dstCapacity)
205 {
206 bitC->bitContainer = 0;
207 bitC->bitPos = 0;
208 bitC->startPtr = (char*)startPtr;
209 bitC->ptr = bitC->startPtr;
210 bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->bitContainer);
211 if (dstCapacity <= sizeof(bitC->bitContainer)) return ERROR(dstSize_tooSmall);
212 return 0;
213 }
214
215 /*! BIT_addBits() :
216 * can add up to 31 bits into `bitC`.
217 * Note : does not check for register overflow ! */
BIT_addBits(BIT_CStream_t * bitC,size_t value,unsigned nbBits)218 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC,
219 size_t value, unsigned nbBits)
220 {
221 MEM_STATIC_ASSERT(BIT_MASK_SIZE == 32);
222 assert(nbBits < BIT_MASK_SIZE);
223 assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
224 bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
225 bitC->bitPos += nbBits;
226 }
227
228 /*! BIT_addBitsFast() :
229 * works only if `value` is _clean_,
230 * meaning all high bits above nbBits are 0 */
BIT_addBitsFast(BIT_CStream_t * bitC,size_t value,unsigned nbBits)231 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC,
232 size_t value, unsigned nbBits)
233 {
234 assert((value>>nbBits) == 0);
235 assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
236 bitC->bitContainer |= value << bitC->bitPos;
237 bitC->bitPos += nbBits;
238 }
239
240 /*! BIT_flushBitsFast() :
241 * assumption : bitContainer has not overflowed
242 * unsafe version; does not check buffer overflow */
BIT_flushBitsFast(BIT_CStream_t * bitC)243 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)
244 {
245 size_t const nbBytes = bitC->bitPos >> 3;
246 assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
247 MEM_writeLEST(bitC->ptr, bitC->bitContainer);
248 bitC->ptr += nbBytes;
249 assert(bitC->ptr <= bitC->endPtr);
250 bitC->bitPos &= 7;
251 bitC->bitContainer >>= nbBytes*8;
252 }
253
254 /*! BIT_flushBits() :
255 * assumption : bitContainer has not overflowed
256 * safe version; check for buffer overflow, and prevents it.
257 * note : does not signal buffer overflow.
258 * overflow will be revealed later on using BIT_closeCStream() */
BIT_flushBits(BIT_CStream_t * bitC)259 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)
260 {
261 size_t const nbBytes = bitC->bitPos >> 3;
262 assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
263 MEM_writeLEST(bitC->ptr, bitC->bitContainer);
264 bitC->ptr += nbBytes;
265 if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
266 bitC->bitPos &= 7;
267 bitC->bitContainer >>= nbBytes*8;
268 }
269
270 /*! BIT_closeCStream() :
271 * @return : size of CStream, in bytes,
272 * or 0 if it could not fit into dstBuffer */
BIT_closeCStream(BIT_CStream_t * bitC)273 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)
274 {
275 BIT_addBitsFast(bitC, 1, 1); /* endMark */
276 BIT_flushBits(bitC);
277 if (bitC->ptr >= bitC->endPtr) return 0; /* overflow detected */
278 return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
279 }
280
281
282 /*-********************************************************
283 * bitStream decoding
284 **********************************************************/
285 /*! BIT_initDStream() :
286 * Initialize a BIT_DStream_t.
287 * `bitD` : a pointer to an already allocated BIT_DStream_t structure.
288 * `srcSize` must be the *exact* size of the bitStream, in bytes.
289 * @return : size of stream (== srcSize), or an errorCode if a problem is detected
290 */
BIT_initDStream(BIT_DStream_t * bitD,const void * srcBuffer,size_t srcSize)291 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
292 {
293 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
294
295 bitD->start = (const char*)srcBuffer;
296 bitD->limitPtr = bitD->start + sizeof(bitD->bitContainer);
297
298 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
299 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
300 bitD->bitContainer = MEM_readLEST(bitD->ptr);
301 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
302 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */
303 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
304 } else {
305 bitD->ptr = bitD->start;
306 bitD->bitContainer = *(const BYTE*)(bitD->start);
307 switch(srcSize)
308 {
309 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
310 /* fall-through */
311
312 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);
313 /* fall-through */
314
315 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);
316 /* fall-through */
317
318 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24;
319 /* fall-through */
320
321 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16;
322 /* fall-through */
323
324 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8;
325 /* fall-through */
326
327 default: break;
328 }
329 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
330 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
331 if (lastByte == 0) return ERROR(corruption_detected); /* endMark not present */
332 }
333 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
334 }
335
336 return srcSize;
337 }
338
BIT_getUpperBits(size_t bitContainer,U32 const start)339 MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
340 {
341 return bitContainer >> start;
342 }
343
BIT_getMiddleBits(size_t bitContainer,U32 const start,U32 const nbBits)344 MEM_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
345 {
346 U32 const regMask = sizeof(bitContainer)*8 - 1;
347 /* if start > regMask, bitstream is corrupted, and result is undefined */
348 assert(nbBits < BIT_MASK_SIZE);
349 return (bitContainer >> (start & regMask)) & BIT_mask[nbBits];
350 }
351
BIT_getLowerBits(size_t bitContainer,U32 const nbBits)352 MEM_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
353 {
354 assert(nbBits < BIT_MASK_SIZE);
355 return bitContainer & BIT_mask[nbBits];
356 }
357
358 /*! BIT_lookBits() :
359 * Provides next n bits from local register.
360 * local register is not modified.
361 * On 32-bits, maxNbBits==24.
362 * On 64-bits, maxNbBits==56.
363 * @return : value extracted */
BIT_lookBits(const BIT_DStream_t * bitD,U32 nbBits)364 MEM_STATIC size_t BIT_lookBits(const BIT_DStream_t* bitD, U32 nbBits)
365 {
366 /* arbitrate between double-shift and shift+mask */
367 #if 1
368 /* if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8,
369 * bitstream is likely corrupted, and result is undefined */
370 return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);
371 #else
372 /* this code path is slower on my os-x laptop */
373 U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
374 return ((bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> 1) >> ((regMask-nbBits) & regMask);
375 #endif
376 }
377
378 /*! BIT_lookBitsFast() :
379 * unsafe version; only works if nbBits >= 1 */
BIT_lookBitsFast(const BIT_DStream_t * bitD,U32 nbBits)380 MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
381 {
382 U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
383 assert(nbBits >= 1);
384 return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask);
385 }
386
BIT_skipBits(BIT_DStream_t * bitD,U32 nbBits)387 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
388 {
389 bitD->bitsConsumed += nbBits;
390 }
391
392 /*! BIT_readBits() :
393 * Read (consume) next n bits from local register and update.
394 * Pay attention to not read more than nbBits contained into local register.
395 * @return : extracted value. */
BIT_readBits(BIT_DStream_t * bitD,unsigned nbBits)396 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits)
397 {
398 size_t const value = BIT_lookBits(bitD, nbBits);
399 BIT_skipBits(bitD, nbBits);
400 return value;
401 }
402
403 /*! BIT_readBitsFast() :
404 * unsafe version; only works only if nbBits >= 1 */
BIT_readBitsFast(BIT_DStream_t * bitD,unsigned nbBits)405 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits)
406 {
407 size_t const value = BIT_lookBitsFast(bitD, nbBits);
408 assert(nbBits >= 1);
409 BIT_skipBits(bitD, nbBits);
410 return value;
411 }
412
413 /*! BIT_reloadDStream() :
414 * Refill `bitD` from buffer previously set in BIT_initDStream() .
415 * This function is safe, it guarantees it will not read beyond src buffer.
416 * @return : status of `BIT_DStream_t` internal register.
417 * when status == BIT_DStream_unfinished, internal register is filled with at least 25 or 57 bits */
BIT_reloadDStream(BIT_DStream_t * bitD)418 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
419 {
420 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* overflow detected, like end of stream */
421 return BIT_DStream_overflow;
422
423 if (bitD->ptr >= bitD->limitPtr) {
424 bitD->ptr -= bitD->bitsConsumed >> 3;
425 bitD->bitsConsumed &= 7;
426 bitD->bitContainer = MEM_readLEST(bitD->ptr);
427 return BIT_DStream_unfinished;
428 }
429 if (bitD->ptr == bitD->start) {
430 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
431 return BIT_DStream_completed;
432 }
433 /* start < ptr < limitPtr */
434 { U32 nbBytes = bitD->bitsConsumed >> 3;
435 BIT_DStream_status result = BIT_DStream_unfinished;
436 if (bitD->ptr - nbBytes < bitD->start) {
437 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
438 result = BIT_DStream_endOfBuffer;
439 }
440 bitD->ptr -= nbBytes;
441 bitD->bitsConsumed -= nbBytes*8;
442 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD->bitContainer), otherwise bitD->ptr == bitD->start */
443 return result;
444 }
445 }
446
447 /*! BIT_endOfDStream() :
448 * @return : 1 if DStream has _exactly_ reached its end (all bits consumed).
449 */
BIT_endOfDStream(const BIT_DStream_t * DStream)450 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
451 {
452 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
453 }
454
455 #if defined (__cplusplus)
456 }
457 #endif
458
459 #endif /* BITSTREAM_H_MODULE */
460