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