1 /* ******************************************************************
4 * Copyright (c) Meta Platforms, Inc. and affiliates.
6 * You can contact the author at :
7 * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
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
17 #if defined (__cplusplus)
21 * This API consists of small unitary functions, which must be inlined for best performance.
22 * Since link-time-optimization is not available for all compilers,
23 * these functions are defined into a .h to be included.
26 /*-****************************************
28 ******************************************/
29 #include "mem.h" /* unaligned access routines */
30 #include "compiler.h" /* UNLIKELY() */
31 #include "debug.h" /* assert(), DEBUGLOG(), RAWLOG() */
32 #include "error_private.h" /* error codes and messages */
33 #include "bits.h" /* ZSTD_highbit32 */
36 /*=========================================
38 =========================================*/
39 #ifndef ZSTD_NO_INTRINSICS
40 # if (defined(__BMI__) || defined(__BMI2__)) && defined(__GNUC__)
41 # include <immintrin.h> /* support for bextr (experimental)/bzhi */
42 # elif defined(__ICCARM__)
43 # include <intrinsics.h>
47 #define STREAM_ACCUMULATOR_MIN_32 25
48 #define STREAM_ACCUMULATOR_MIN_64 57
49 #define STREAM_ACCUMULATOR_MIN ((U32)(MEM_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
52 /*-******************************************
53 * bitStream encoding API (write forward)
54 ********************************************/
55 /* bitStream can mix input from multiple sources.
56 * A critical property of these streams is that they encode and decode in **reverse** direction.
57 * So the first bit sequence you add will be the last to be read, like a LIFO stack.
67 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
68 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
69 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC);
70 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC);
72 /* Start with initCStream, providing the size of buffer to write into.
73 * bitStream will never write outside of this buffer.
74 * `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
76 * bits are first added to a local register.
77 * Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
78 * Writing data into memory is an explicit operation, performed by the flushBits function.
79 * Hence keep track how many bits are potentially stored into local register to avoid register overflow.
80 * After a flushBits, a maximum of 7 bits might still be stored into local register.
82 * Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
84 * Last operation is to close the bitStream.
85 * The function returns the final size of CStream in bytes.
86 * If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
90 /*-********************************************
91 * bitStream decoding API (read backward)
92 **********************************************/
93 typedef size_t BitContainerType;
95 BitContainerType bitContainer;
96 unsigned bitsConsumed;
102 typedef enum { BIT_DStream_unfinished = 0, /* fully refilled */
103 BIT_DStream_endOfBuffer = 1, /* still some bits left in bitstream */
104 BIT_DStream_completed = 2, /* bitstream entirely consumed, bit-exact */
105 BIT_DStream_overflow = 3 /* user requested more bits than present in bitstream */
106 } BIT_DStream_status; /* result of BIT_reloadDStream() */
108 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
109 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
110 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
111 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
114 /* Start by invoking BIT_initDStream().
115 * A chunk of the bitStream is then stored into a local register.
116 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (BitContainerType).
117 * You can then retrieve bitFields stored into the local register, **in reverse order**.
118 * Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
119 * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
120 * Otherwise, it can be less than that, so proceed accordingly.
121 * Checking if DStream has reached its end can be performed with BIT_endOfDStream().
125 /*-****************************************
127 ******************************************/
128 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
129 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
131 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);
132 /* unsafe version; does not check buffer overflow */
134 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
135 /* faster, but works only if nbBits >= 1 */
137 /*===== Local Constants =====*/
138 static const unsigned BIT_mask[] = {
139 0, 1, 3, 7, 0xF, 0x1F,
140 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF,
141 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF,
142 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF,
143 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF,
144 0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits */
145 #define BIT_MASK_SIZE (sizeof(BIT_mask) / sizeof(BIT_mask[0]))
147 /*-**************************************************************
149 ****************************************************************/
150 /*! BIT_initCStream() :
151 * `dstCapacity` must be > sizeof(size_t)
152 * @return : 0 if success,
153 * otherwise an error code (can be tested using ERR_isError()) */
154 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC,
155 void* startPtr, size_t dstCapacity)
157 bitC->bitContainer = 0;
159 bitC->startPtr = (char*)startPtr;
160 bitC->ptr = bitC->startPtr;
161 bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->bitContainer);
162 if (dstCapacity <= sizeof(bitC->bitContainer)) return ERROR(dstSize_tooSmall);
166 FORCE_INLINE_TEMPLATE size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
168 #if defined(STATIC_BMI2) && STATIC_BMI2 == 1 && !defined(ZSTD_NO_INTRINSICS)
169 return _bzhi_u64(bitContainer, nbBits);
171 assert(nbBits < BIT_MASK_SIZE);
172 return bitContainer & BIT_mask[nbBits];
177 * can add up to 31 bits into `bitC`.
178 * Note : does not check for register overflow ! */
179 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC,
180 size_t value, unsigned nbBits)
182 DEBUG_STATIC_ASSERT(BIT_MASK_SIZE == 32);
183 assert(nbBits < BIT_MASK_SIZE);
184 assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
185 bitC->bitContainer |= BIT_getLowerBits(value, nbBits) << bitC->bitPos;
186 bitC->bitPos += nbBits;
189 /*! BIT_addBitsFast() :
190 * works only if `value` is _clean_,
191 * meaning all high bits above nbBits are 0 */
192 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC,
193 size_t value, unsigned nbBits)
195 assert((value>>nbBits) == 0);
196 assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
197 bitC->bitContainer |= value << bitC->bitPos;
198 bitC->bitPos += nbBits;
201 /*! BIT_flushBitsFast() :
202 * assumption : bitContainer has not overflowed
203 * unsafe version; does not check buffer overflow */
204 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)
206 size_t const nbBytes = bitC->bitPos >> 3;
207 assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
208 assert(bitC->ptr <= bitC->endPtr);
209 MEM_writeLEST(bitC->ptr, bitC->bitContainer);
210 bitC->ptr += nbBytes;
212 bitC->bitContainer >>= nbBytes*8;
215 /*! BIT_flushBits() :
216 * assumption : bitContainer has not overflowed
217 * safe version; check for buffer overflow, and prevents it.
218 * note : does not signal buffer overflow.
219 * overflow will be revealed later on using BIT_closeCStream() */
220 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)
222 size_t const nbBytes = bitC->bitPos >> 3;
223 assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
224 assert(bitC->ptr <= bitC->endPtr);
225 MEM_writeLEST(bitC->ptr, bitC->bitContainer);
226 bitC->ptr += nbBytes;
227 if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
229 bitC->bitContainer >>= nbBytes*8;
232 /*! BIT_closeCStream() :
233 * @return : size of CStream, in bytes,
234 * or 0 if it could not fit into dstBuffer */
235 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)
237 BIT_addBitsFast(bitC, 1, 1); /* endMark */
239 if (bitC->ptr >= bitC->endPtr) return 0; /* overflow detected */
240 return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
244 /*-********************************************************
246 **********************************************************/
247 /*! BIT_initDStream() :
248 * Initialize a BIT_DStream_t.
249 * `bitD` : a pointer to an already allocated BIT_DStream_t structure.
250 * `srcSize` must be the *exact* size of the bitStream, in bytes.
251 * @return : size of stream (== srcSize), or an errorCode if a problem is detected
253 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
255 if (srcSize < 1) { ZSTD_memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
257 bitD->start = (const char*)srcBuffer;
258 bitD->limitPtr = bitD->start + sizeof(bitD->bitContainer);
260 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
261 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
262 bitD->bitContainer = MEM_readLEST(bitD->ptr);
263 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
264 bitD->bitsConsumed = lastByte ? 8 - ZSTD_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */
265 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
267 bitD->ptr = bitD->start;
268 bitD->bitContainer = *(const BYTE*)(bitD->start);
271 case 7: bitD->bitContainer += (BitContainerType)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
274 case 6: bitD->bitContainer += (BitContainerType)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);
277 case 5: bitD->bitContainer += (BitContainerType)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);
280 case 4: bitD->bitContainer += (BitContainerType)(((const BYTE*)(srcBuffer))[3]) << 24;
283 case 3: bitD->bitContainer += (BitContainerType)(((const BYTE*)(srcBuffer))[2]) << 16;
286 case 2: bitD->bitContainer += (BitContainerType)(((const BYTE*)(srcBuffer))[1]) << 8;
291 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
292 bitD->bitsConsumed = lastByte ? 8 - ZSTD_highbit32(lastByte) : 0;
293 if (lastByte == 0) return ERROR(corruption_detected); /* endMark not present */
295 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
301 FORCE_INLINE_TEMPLATE size_t BIT_getUpperBits(BitContainerType bitContainer, U32 const start)
303 return bitContainer >> start;
306 FORCE_INLINE_TEMPLATE size_t BIT_getMiddleBits(BitContainerType bitContainer, U32 const start, U32 const nbBits)
308 U32 const regMask = sizeof(bitContainer)*8 - 1;
309 /* if start > regMask, bitstream is corrupted, and result is undefined */
310 assert(nbBits < BIT_MASK_SIZE);
311 /* x86 transform & ((1 << nbBits) - 1) to bzhi instruction, it is better
312 * than accessing memory. When bmi2 instruction is not present, we consider
313 * such cpus old (pre-Haswell, 2013) and their performance is not of that
316 #if defined(__x86_64__) || defined(_M_X86)
317 return (bitContainer >> (start & regMask)) & ((((U64)1) << nbBits) - 1);
319 return (bitContainer >> (start & regMask)) & BIT_mask[nbBits];
324 * Provides next n bits from local register.
325 * local register is not modified.
326 * On 32-bits, maxNbBits==24.
327 * On 64-bits, maxNbBits==56.
328 * @return : value extracted */
329 FORCE_INLINE_TEMPLATE size_t BIT_lookBits(const BIT_DStream_t* bitD, U32 nbBits)
331 /* arbitrate between double-shift and shift+mask */
333 /* if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8,
334 * bitstream is likely corrupted, and result is undefined */
335 return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);
337 /* this code path is slower on my os-x laptop */
338 U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
339 return ((bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> 1) >> ((regMask-nbBits) & regMask);
343 /*! BIT_lookBitsFast() :
344 * unsafe version; only works if nbBits >= 1 */
345 MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
347 U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
349 return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask);
352 FORCE_INLINE_TEMPLATE void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
354 bitD->bitsConsumed += nbBits;
358 * Read (consume) next n bits from local register and update.
359 * Pay attention to not read more than nbBits contained into local register.
360 * @return : extracted value. */
361 FORCE_INLINE_TEMPLATE size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits)
363 size_t const value = BIT_lookBits(bitD, nbBits);
364 BIT_skipBits(bitD, nbBits);
368 /*! BIT_readBitsFast() :
369 * unsafe version; only works if nbBits >= 1 */
370 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits)
372 size_t const value = BIT_lookBitsFast(bitD, nbBits);
374 BIT_skipBits(bitD, nbBits);
378 /*! BIT_reloadDStream_internal() :
379 * Simple variant of BIT_reloadDStream(), with two conditions:
380 * 1. bitstream is valid : bitsConsumed <= sizeof(bitD->bitContainer)*8
381 * 2. look window is valid after shifted down : bitD->ptr >= bitD->start
383 MEM_STATIC BIT_DStream_status BIT_reloadDStream_internal(BIT_DStream_t* bitD)
385 assert(bitD->bitsConsumed <= sizeof(bitD->bitContainer)*8);
386 bitD->ptr -= bitD->bitsConsumed >> 3;
387 assert(bitD->ptr >= bitD->start);
388 bitD->bitsConsumed &= 7;
389 bitD->bitContainer = MEM_readLEST(bitD->ptr);
390 return BIT_DStream_unfinished;
393 /*! BIT_reloadDStreamFast() :
394 * Similar to BIT_reloadDStream(), but with two differences:
395 * 1. bitsConsumed <= sizeof(bitD->bitContainer)*8 must hold!
396 * 2. Returns BIT_DStream_overflow when bitD->ptr < bitD->limitPtr, at this
397 * point you must use BIT_reloadDStream() to reload.
399 MEM_STATIC BIT_DStream_status BIT_reloadDStreamFast(BIT_DStream_t* bitD)
401 if (UNLIKELY(bitD->ptr < bitD->limitPtr))
402 return BIT_DStream_overflow;
403 return BIT_reloadDStream_internal(bitD);
406 /*! BIT_reloadDStream() :
407 * Refill `bitD` from buffer previously set in BIT_initDStream() .
408 * This function is safe, it guarantees it will not never beyond src buffer.
409 * @return : status of `BIT_DStream_t` internal register.
410 * when status == BIT_DStream_unfinished, internal register is filled with at least 25 or 57 bits */
411 FORCE_INLINE_TEMPLATE BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
413 /* note : once in overflow mode, a bitstream remains in this mode until it's reset */
414 if (UNLIKELY(bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))) {
415 static const BitContainerType zeroFilled = 0;
416 bitD->ptr = (const char*)&zeroFilled; /* aliasing is allowed for char */
417 /* overflow detected, erroneous scenario or end of stream: no update */
418 return BIT_DStream_overflow;
421 assert(bitD->ptr >= bitD->start);
423 if (bitD->ptr >= bitD->limitPtr) {
424 return BIT_reloadDStream_internal(bitD);
426 if (bitD->ptr == bitD->start) {
427 /* reached end of bitStream => no update */
428 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
429 return BIT_DStream_completed;
431 /* start < ptr < limitPtr => cautious update */
432 { U32 nbBytes = bitD->bitsConsumed >> 3;
433 BIT_DStream_status result = BIT_DStream_unfinished;
434 if (bitD->ptr - nbBytes < bitD->start) {
435 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
436 result = BIT_DStream_endOfBuffer;
438 bitD->ptr -= nbBytes;
439 bitD->bitsConsumed -= nbBytes*8;
440 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD->bitContainer), otherwise bitD->ptr == bitD->start */
445 /*! BIT_endOfDStream() :
446 * @return : 1 if DStream has _exactly_ reached its end (all bits consumed).
448 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
450 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
453 #if defined (__cplusplus)
457 #endif /* BITSTREAM_H_MODULE */