1 /* SPDX-License-Identifier: (GPL-2.0 or BSD-2-Clause) */
2 /*
3 * bitstream
4 * Part of FSE library
5 * header file (to include)
6 * Copyright (C) 2013-2016, Yann Collet.
7 *
8 * You can contact the author at :
9 * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
10 */
11 #ifndef BITSTREAM_H_MODULE
12 #define BITSTREAM_H_MODULE
13
14 /*
15 * This API consists of small unitary functions, which must be inlined for best performance.
16 * Since link-time-optimization is not available for all compilers,
17 * these functions are defined into a .h to be included.
18 */
19
20 /*-****************************************
21 * Dependencies
22 ******************************************/
23 #include "error_private.h" /* error codes and messages */
24 #include "mem.h" /* unaligned access routines */
25
26 /*=========================================
27 * Target specific
28 =========================================*/
29 #define STREAM_ACCUMULATOR_MIN_32 25
30 #define STREAM_ACCUMULATOR_MIN_64 57
31 #define STREAM_ACCUMULATOR_MIN ((U32)(ZSTD_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
32
33 /*-******************************************
34 * bitStream encoding API (write forward)
35 ********************************************/
36 /* bitStream can mix input from multiple sources.
37 * A critical property of these streams is that they encode and decode in **reverse** direction.
38 * So the first bit sequence you add will be the last to be read, like a LIFO stack.
39 */
40 typedef struct {
41 size_t bitContainer;
42 int bitPos;
43 char *startPtr;
44 char *ptr;
45 char *endPtr;
46 } BIT_CStream_t;
47
48 ZSTD_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity);
49 ZSTD_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned nbBits);
50 ZSTD_STATIC void BIT_flushBits(BIT_CStream_t *bitC);
51 ZSTD_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC);
52
53 /* Start with initCStream, providing the size of buffer to write into.
54 * bitStream will never write outside of this buffer.
55 * `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
56 *
57 * bits are first added to a local register.
58 * Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
59 * Writing data into memory is an explicit operation, performed by the flushBits function.
60 * Hence keep track how many bits are potentially stored into local register to avoid register overflow.
61 * After a flushBits, a maximum of 7 bits might still be stored into local register.
62 *
63 * Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
64 *
65 * Last operation is to close the bitStream.
66 * The function returns the final size of CStream in bytes.
67 * If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
68 */
69
70 /*-********************************************
71 * bitStream decoding API (read backward)
72 **********************************************/
73 typedef struct {
74 size_t bitContainer;
75 unsigned bitsConsumed;
76 const char *ptr;
77 const char *start;
78 } BIT_DStream_t;
79
80 typedef enum {
81 BIT_DStream_unfinished = 0,
82 BIT_DStream_endOfBuffer = 1,
83 BIT_DStream_completed = 2,
84 BIT_DStream_overflow = 3
85 } BIT_DStream_status; /* result of BIT_reloadDStream() */
86 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
87
88 ZSTD_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize);
89 ZSTD_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, unsigned nbBits);
90 ZSTD_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD);
91 ZSTD_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *bitD);
92
93 /* Start by invoking BIT_initDStream().
94 * A chunk of the bitStream is then stored into a local register.
95 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
96 * You can then retrieve bitFields stored into the local register, **in reverse order**.
97 * Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
98 * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
99 * Otherwise, it can be less than that, so proceed accordingly.
100 * Checking if DStream has reached its end can be performed with BIT_endOfDStream().
101 */
102
103 /*-****************************************
104 * unsafe API
105 ******************************************/
106 ZSTD_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits);
107 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
108
109 ZSTD_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC);
110 /* unsafe version; does not check buffer overflow */
111
112 ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, unsigned nbBits);
113 /* faster, but works only if nbBits >= 1 */
114
115 /*-**************************************************************
116 * Internal functions
117 ****************************************************************/
BIT_highbit32(register U32 val)118 ZSTD_STATIC unsigned BIT_highbit32(register U32 val) { return 31 - __builtin_clz(val); }
119
120 /*===== Local Constants =====*/
121 static const unsigned BIT_mask[] = {0, 1, 3, 7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF,
122 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF,
123 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF}; /* up to 26 bits */
124
125 /*-**************************************************************
126 * bitStream encoding
127 ****************************************************************/
128 /*! BIT_initCStream() :
129 * `dstCapacity` must be > sizeof(void*)
130 * @return : 0 if success,
131 otherwise an error code (can be tested using ERR_isError() ) */
BIT_initCStream(BIT_CStream_t * bitC,void * startPtr,size_t dstCapacity)132 ZSTD_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *startPtr, size_t dstCapacity)
133 {
134 bitC->bitContainer = 0;
135 bitC->bitPos = 0;
136 bitC->startPtr = (char *)startPtr;
137 bitC->ptr = bitC->startPtr;
138 bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->ptr);
139 if (dstCapacity <= sizeof(bitC->ptr))
140 return ERROR(dstSize_tooSmall);
141 return 0;
142 }
143
144 /*! BIT_addBits() :
145 can add up to 26 bits into `bitC`.
146 Does not check for register overflow ! */
BIT_addBits(BIT_CStream_t * bitC,size_t value,unsigned nbBits)147 ZSTD_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
148 {
149 bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
150 bitC->bitPos += nbBits;
151 }
152
153 /*! BIT_addBitsFast() :
154 * works only if `value` is _clean_, meaning all high bits above nbBits are 0 */
BIT_addBitsFast(BIT_CStream_t * bitC,size_t value,unsigned nbBits)155 ZSTD_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
156 {
157 bitC->bitContainer |= value << bitC->bitPos;
158 bitC->bitPos += nbBits;
159 }
160
161 /*! BIT_flushBitsFast() :
162 * unsafe version; does not check buffer overflow */
BIT_flushBitsFast(BIT_CStream_t * bitC)163 ZSTD_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC)
164 {
165 size_t const nbBytes = bitC->bitPos >> 3;
166 ZSTD_writeLEST(bitC->ptr, bitC->bitContainer);
167 bitC->ptr += nbBytes;
168 bitC->bitPos &= 7;
169 bitC->bitContainer >>= nbBytes * 8; /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */
170 }
171
172 /*! BIT_flushBits() :
173 * safe version; check for buffer overflow, and prevents it.
174 * note : does not signal buffer overflow. This will be revealed later on using BIT_closeCStream() */
BIT_flushBits(BIT_CStream_t * bitC)175 ZSTD_STATIC void BIT_flushBits(BIT_CStream_t *bitC)
176 {
177 size_t const nbBytes = bitC->bitPos >> 3;
178 ZSTD_writeLEST(bitC->ptr, bitC->bitContainer);
179 bitC->ptr += nbBytes;
180 if (bitC->ptr > bitC->endPtr)
181 bitC->ptr = bitC->endPtr;
182 bitC->bitPos &= 7;
183 bitC->bitContainer >>= nbBytes * 8; /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */
184 }
185
186 /*! BIT_closeCStream() :
187 * @return : size of CStream, in bytes,
188 or 0 if it could not fit into dstBuffer */
BIT_closeCStream(BIT_CStream_t * bitC)189 ZSTD_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
190 {
191 BIT_addBitsFast(bitC, 1, 1); /* endMark */
192 BIT_flushBits(bitC);
193
194 if (bitC->ptr >= bitC->endPtr)
195 return 0; /* doesn't fit within authorized budget : cancel */
196
197 return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
198 }
199
200 /*-********************************************************
201 * bitStream decoding
202 **********************************************************/
203 /*! BIT_initDStream() :
204 * Initialize a BIT_DStream_t.
205 * `bitD` : a pointer to an already allocated BIT_DStream_t structure.
206 * `srcSize` must be the *exact* size of the bitStream, in bytes.
207 * @return : size of stream (== srcSize) or an errorCode if a problem is detected
208 */
BIT_initDStream(BIT_DStream_t * bitD,const void * srcBuffer,size_t srcSize)209 ZSTD_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize)
210 {
211 if (srcSize < 1) {
212 memset(bitD, 0, sizeof(*bitD));
213 return ERROR(srcSize_wrong);
214 }
215
216 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
217 bitD->start = (const char *)srcBuffer;
218 bitD->ptr = (const char *)srcBuffer + srcSize - sizeof(bitD->bitContainer);
219 bitD->bitContainer = ZSTD_readLEST(bitD->ptr);
220 {
221 BYTE const lastByte = ((const BYTE *)srcBuffer)[srcSize - 1];
222 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */
223 if (lastByte == 0)
224 return ERROR(GENERIC); /* endMark not present */
225 }
226 } else {
227 bitD->start = (const char *)srcBuffer;
228 bitD->ptr = bitD->start;
229 bitD->bitContainer = *(const BYTE *)(bitD->start);
230 switch (srcSize) {
231 case 7: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[6]) << (sizeof(bitD->bitContainer) * 8 - 16);
232 case 6: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[5]) << (sizeof(bitD->bitContainer) * 8 - 24);
233 case 5: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[4]) << (sizeof(bitD->bitContainer) * 8 - 32);
234 case 4: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[3]) << 24;
235 case 3: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[2]) << 16;
236 case 2: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[1]) << 8;
237 default:;
238 }
239 {
240 BYTE const lastByte = ((const BYTE *)srcBuffer)[srcSize - 1];
241 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
242 if (lastByte == 0)
243 return ERROR(GENERIC); /* endMark not present */
244 }
245 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize) * 8;
246 }
247
248 return srcSize;
249 }
250
BIT_getUpperBits(size_t bitContainer,U32 const start)251 ZSTD_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start) { return bitContainer >> start; }
252
BIT_getMiddleBits(size_t bitContainer,U32 const start,U32 const nbBits)253 ZSTD_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits) { return (bitContainer >> start) & BIT_mask[nbBits]; }
254
BIT_getLowerBits(size_t bitContainer,U32 const nbBits)255 ZSTD_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits) { return bitContainer & BIT_mask[nbBits]; }
256
257 /*! BIT_lookBits() :
258 * Provides next n bits from local register.
259 * local register is not modified.
260 * On 32-bits, maxNbBits==24.
261 * On 64-bits, maxNbBits==56.
262 * @return : value extracted
263 */
BIT_lookBits(const BIT_DStream_t * bitD,U32 nbBits)264 ZSTD_STATIC size_t BIT_lookBits(const BIT_DStream_t *bitD, U32 nbBits)
265 {
266 U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1;
267 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask - nbBits) & bitMask);
268 }
269
270 /*! BIT_lookBitsFast() :
271 * unsafe version; only works only if nbBits >= 1 */
BIT_lookBitsFast(const BIT_DStream_t * bitD,U32 nbBits)272 ZSTD_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t *bitD, U32 nbBits)
273 {
274 U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1;
275 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask + 1) - nbBits) & bitMask);
276 }
277
BIT_skipBits(BIT_DStream_t * bitD,U32 nbBits)278 ZSTD_STATIC void BIT_skipBits(BIT_DStream_t *bitD, U32 nbBits) { bitD->bitsConsumed += nbBits; }
279
280 /*! BIT_readBits() :
281 * Read (consume) next n bits from local register and update.
282 * Pay attention to not read more than nbBits contained into local register.
283 * @return : extracted value.
284 */
BIT_readBits(BIT_DStream_t * bitD,U32 nbBits)285 ZSTD_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, U32 nbBits)
286 {
287 size_t const value = BIT_lookBits(bitD, nbBits);
288 BIT_skipBits(bitD, nbBits);
289 return value;
290 }
291
292 /*! BIT_readBitsFast() :
293 * unsafe version; only works only if nbBits >= 1 */
BIT_readBitsFast(BIT_DStream_t * bitD,U32 nbBits)294 ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, U32 nbBits)
295 {
296 size_t const value = BIT_lookBitsFast(bitD, nbBits);
297 BIT_skipBits(bitD, nbBits);
298 return value;
299 }
300
301 /*! BIT_reloadDStream() :
302 * Refill `bitD` from buffer previously set in BIT_initDStream() .
303 * This function is safe, it guarantees it will not read beyond src buffer.
304 * @return : status of `BIT_DStream_t` internal register.
305 if status == BIT_DStream_unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */
BIT_reloadDStream(BIT_DStream_t * bitD)306 ZSTD_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
307 {
308 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer) * 8)) /* should not happen => corruption detected */
309 return BIT_DStream_overflow;
310
311 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
312 bitD->ptr -= bitD->bitsConsumed >> 3;
313 bitD->bitsConsumed &= 7;
314 bitD->bitContainer = ZSTD_readLEST(bitD->ptr);
315 return BIT_DStream_unfinished;
316 }
317 if (bitD->ptr == bitD->start) {
318 if (bitD->bitsConsumed < sizeof(bitD->bitContainer) * 8)
319 return BIT_DStream_endOfBuffer;
320 return BIT_DStream_completed;
321 }
322 {
323 U32 nbBytes = bitD->bitsConsumed >> 3;
324 BIT_DStream_status result = BIT_DStream_unfinished;
325 if (bitD->ptr - nbBytes < bitD->start) {
326 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
327 result = BIT_DStream_endOfBuffer;
328 }
329 bitD->ptr -= nbBytes;
330 bitD->bitsConsumed -= nbBytes * 8;
331 bitD->bitContainer = ZSTD_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
332 return result;
333 }
334 }
335
336 /*! BIT_endOfDStream() :
337 * @return Tells if DStream has exactly reached its end (all bits consumed).
338 */
BIT_endOfDStream(const BIT_DStream_t * DStream)339 ZSTD_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *DStream)
340 {
341 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer) * 8));
342 }
343
344 #endif /* BITSTREAM_H_MODULE */
345