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