1 /* ******************************************* 1
2 * bitstream
3 * Part of FSE library
4 * Copyright (c) Yann Collet, Facebook, Inc.
5 *
6 * You can contact the author at :
7 * - Source repository : https://github.com/Cy
8 *
9 * This source code is licensed under both the
10 * LICENSE file in the root directory of this
11 * in the COPYING file in the root directory o
12 * You may select, at your option, one of the
13 **********************************************
14 #ifndef BITSTREAM_H_MODULE
15 #define BITSTREAM_H_MODULE
16
17 /*
18 * This API consists of small unitary function
19 * Since link-time-optimization is not availab
20 * these functions are defined into a .h to be
21 */
22
23 /*-****************************************
24 * Dependencies
25 ******************************************/
26 #include "mem.h" /* unaligned acces
27 #include "compiler.h" /* UNLIKELY() */
28 #include "debug.h" /* assert(), DEBUG
29 #include "error_private.h" /* error codes and
30
31
32 /*=========================================
33 * Target specific
34 =========================================*/
35
36 #define STREAM_ACCUMULATOR_MIN_32 25
37 #define STREAM_ACCUMULATOR_MIN_64 57
38 #define STREAM_ACCUMULATOR_MIN ((U32)(MEM_3
39
40
41 /*-******************************************
42 * bitStream encoding API (write forward)
43 ********************************************/
44 /* bitStream can mix input from multiple sourc
45 * A critical property of these streams is tha
46 * So the first bit sequence you add will be t
47 */
48 typedef struct {
49 size_t bitContainer;
50 unsigned bitPos;
51 char* startPtr;
52 char* ptr;
53 char* endPtr;
54 } BIT_CStream_t;
55
56 MEM_STATIC size_t BIT_initCStream(BIT_CStream_
57 MEM_STATIC void BIT_addBits(BIT_CStream_t* b
58 MEM_STATIC void BIT_flushBits(BIT_CStream_t*
59 MEM_STATIC size_t BIT_closeCStream(BIT_CStream
60
61 /* Start with initCStream, providing the size
62 * bitStream will never write outside of this
63 * `dstCapacity` must be >= sizeof(bitD->bitCo
64 *
65 * bits are first added to a local register.
66 * Local register is size_t, hence 64-bits on
67 * Writing data into memory is an explicit ope
68 * Hence keep track how many bits are potentia
69 * After a flushBits, a maximum of 7 bits migh
70 *
71 * Avoid storing elements of more than 24 bits
72 *
73 * Last operation is to close the bitStream.
74 * The function returns the final size of CStr
75 * If data couldn't fit into `dstBuffer`, it w
76 */
77
78
79 /*-*******************************************
80 * bitStream decoding API (read backward)
81 **********************************************
82 typedef struct {
83 size_t bitContainer;
84 unsigned bitsConsumed;
85 const char* ptr;
86 const char* start;
87 const char* limitPtr;
88 } BIT_DStream_t;
89
90 typedef enum { BIT_DStream_unfinished = 0,
91 BIT_DStream_endOfBuffer = 1,
92 BIT_DStream_completed = 2,
93 BIT_DStream_overflow = 3 } BIT_
94 /* 1,2,4,8 would be better for
95
96 MEM_STATIC size_t BIT_initDStream(BIT_DStrea
97 MEM_STATIC size_t BIT_readBits(BIT_DStream_t
98 MEM_STATIC BIT_DStream_status BIT_reloadDStrea
99 MEM_STATIC unsigned BIT_endOfDStream(const BIT
100
101
102 /* Start by invoking BIT_initDStream().
103 * A chunk of the bitStream is then stored int
104 * Local register size is 64-bits on 64-bits s
105 * You can then retrieve bitFields stored into
106 * Local register is explicitly reloaded from
107 * A reload guarantee a minimum of ((8*sizeof(
108 * Otherwise, it can be less than that, so pro
109 * Checking if DStream has reached its end can
110 */
111
112
113 /*-****************************************
114 * unsafe API
115 ******************************************/
116 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t*
117 /* faster, but works only if value is "clean",
118
119 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_
120 /* unsafe version; does not check buffer overf
121
122 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream
123 /* faster, but works only if nbBits >= 1 */
124
125
126
127 /*-*******************************************
128 * Internal functions
129 **********************************************
130 MEM_STATIC unsigned BIT_highbit32 (U32 val)
131 {
132 assert(val != 0);
133 {
134 # if (__GNUC__ >= 3) /* Use GCC Intrinsic
135 return __builtin_clz (val) ^ 31;
136 # else /* Software version */
137 static const unsigned DeBruijnClz[32]
138
139
140
141 U32 v = val;
142 v |= v >> 1;
143 v |= v >> 2;
144 v |= v >> 4;
145 v |= v >> 8;
146 v |= v >> 16;
147 return DeBruijnClz[ (U32) (v * 0x07C4A
148 # endif
149 }
150 }
151
152 /*===== Local Constants =====*/
153 static const unsigned BIT_mask[] = {
154 0, 1, 3, 7,
155 0x3F, 0x7F, 0xFF, 0x1FF,
156 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF,
157 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF
158 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, 0x7FFFFF
159 0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits
160 #define BIT_MASK_SIZE (sizeof(BIT_mask) / size
161
162 /*-*******************************************
163 * bitStream encoding
164 **********************************************
165 /*! BIT_initCStream() :
166 * `dstCapacity` must be > sizeof(size_t)
167 * @return : 0 if success,
168 * otherwise an error code (can be
169 MEM_STATIC size_t BIT_initCStream(BIT_CStream_
170 void* startP
171 {
172 bitC->bitContainer = 0;
173 bitC->bitPos = 0;
174 bitC->startPtr = (char*)startPtr;
175 bitC->ptr = bitC->startPtr;
176 bitC->endPtr = bitC->startPtr + dstCapacit
177 if (dstCapacity <= sizeof(bitC->bitContain
178 return 0;
179 }
180
181 /*! BIT_addBits() :
182 * can add up to 31 bits into `bitC`.
183 * Note : does not check for register overflo
184 MEM_STATIC void BIT_addBits(BIT_CStream_t* bit
185 size_t value, unsi
186 {
187 DEBUG_STATIC_ASSERT(BIT_MASK_SIZE == 32);
188 assert(nbBits < BIT_MASK_SIZE);
189 assert(nbBits + bitC->bitPos < sizeof(bitC
190 bitC->bitContainer |= (value & BIT_mask[nb
191 bitC->bitPos += nbBits;
192 }
193
194 /*! BIT_addBitsFast() :
195 * works only if `value` is _clean_,
196 * meaning all high bits above nbBits are 0 *
197 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t*
198 size_t value,
199 {
200 assert((value>>nbBits) == 0);
201 assert(nbBits + bitC->bitPos < sizeof(bitC
202 bitC->bitContainer |= value << bitC->bitPo
203 bitC->bitPos += nbBits;
204 }
205
206 /*! BIT_flushBitsFast() :
207 * assumption : bitContainer has not overflow
208 * unsafe version; does not check buffer over
209 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_
210 {
211 size_t const nbBytes = bitC->bitPos >> 3;
212 assert(bitC->bitPos < sizeof(bitC->bitCont
213 assert(bitC->ptr <= bitC->endPtr);
214 MEM_writeLEST(bitC->ptr, bitC->bitContaine
215 bitC->ptr += nbBytes;
216 bitC->bitPos &= 7;
217 bitC->bitContainer >>= nbBytes*8;
218 }
219
220 /*! BIT_flushBits() :
221 * assumption : bitContainer has not overflow
222 * safe version; check for buffer overflow, a
223 * note : does not signal buffer overflow.
224 * overflow will be revealed later on using B
225 MEM_STATIC void BIT_flushBits(BIT_CStream_t* b
226 {
227 size_t const nbBytes = bitC->bitPos >> 3;
228 assert(bitC->bitPos < sizeof(bitC->bitCont
229 assert(bitC->ptr <= bitC->endPtr);
230 MEM_writeLEST(bitC->ptr, bitC->bitContaine
231 bitC->ptr += nbBytes;
232 if (bitC->ptr > bitC->endPtr) bitC->ptr =
233 bitC->bitPos &= 7;
234 bitC->bitContainer >>= nbBytes*8;
235 }
236
237 /*! BIT_closeCStream() :
238 * @return : size of CStream, in bytes,
239 * or 0 if it could not fit into ds
240 MEM_STATIC size_t BIT_closeCStream(BIT_CStream
241 {
242 BIT_addBitsFast(bitC, 1, 1); /* endMark
243 BIT_flushBits(bitC);
244 if (bitC->ptr >= bitC->endPtr) return 0; /
245 return (bitC->ptr - bitC->startPtr) + (bit
246 }
247
248
249 /*-*******************************************
250 * bitStream decoding
251 **********************************************
252 /*! BIT_initDStream() :
253 * Initialize a BIT_DStream_t.
254 * `bitD` : a pointer to an already allocated
255 * `srcSize` must be the *exact* size of the b
256 * @return : size of stream (== srcSize), or a
257 */
258 MEM_STATIC size_t BIT_initDStream(BIT_DStream_
259 {
260 if (srcSize < 1) { ZSTD_memset(bitD, 0, si
261
262 bitD->start = (const char*)srcBuffer;
263 bitD->limitPtr = bitD->start + sizeof(bitD
264
265 if (srcSize >= sizeof(bitD->bitContainer)
266 bitD->ptr = (const char*)srcBuffer +
267 bitD->bitContainer = MEM_readLEST(bitD
268 { BYTE const lastByte = ((const BYTE*)
269 bitD->bitsConsumed = lastByte ? 8 -
270 if (lastByte == 0) return ERROR(GENE
271 } else {
272 bitD->ptr = bitD->start;
273 bitD->bitContainer = *(const BYTE*)(bi
274 switch(srcSize)
275 {
276 case 7: bitD->bitContainer += (size_t)
277 ZSTD_FALLTHROUGH;
278
279 case 6: bitD->bitContainer += (size_t)
280 ZSTD_FALLTHROUGH;
281
282 case 5: bitD->bitContainer += (size_t)
283 ZSTD_FALLTHROUGH;
284
285 case 4: bitD->bitContainer += (size_t)
286 ZSTD_FALLTHROUGH;
287
288 case 3: bitD->bitContainer += (size_t)
289 ZSTD_FALLTHROUGH;
290
291 case 2: bitD->bitContainer += (size_t)
292 ZSTD_FALLTHROUGH;
293
294 default: break;
295 }
296 { BYTE const lastByte = ((const BYTE
297 bitD->bitsConsumed = lastByte ? 8
298 if (lastByte == 0) return ERROR(co
299 }
300 bitD->bitsConsumed += (U32)(sizeof(bit
301 }
302
303 return srcSize;
304 }
305
306 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getUpp
307 {
308 return bitContainer >> start;
309 }
310
311 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getMid
312 {
313 U32 const regMask = sizeof(bitContainer)*8
314 /* if start > regMask, bitstream is corrup
315 assert(nbBits < BIT_MASK_SIZE);
316 /* x86 transform & ((1 << nbBits) - 1) to
317 * than accessing memory. When bmi2 instru
318 * such cpus old (pre-Haswell, 2013) and t
319 * importance.
320 */
321 #if defined(__x86_64__) || defined(_M_X86)
322 return (bitContainer >> (start & regMask))
323 #else
324 return (bitContainer >> (start & regMask))
325 #endif
326 }
327
328 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getLow
329 {
330 assert(nbBits < BIT_MASK_SIZE);
331 return bitContainer & BIT_mask[nbBits];
332 }
333
334 /*! BIT_lookBits() :
335 * Provides next n bits from local register.
336 * local register is not modified.
337 * On 32-bits, maxNbBits==24.
338 * On 64-bits, maxNbBits==56.
339 * @return : value extracted */
340 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_lookB
341 {
342 /* arbitrate between double-shift and shif
343 #if 1
344 /* if bitD->bitsConsumed + nbBits > sizeof
345 * bitstream is likely corrupted, and resu
346 return BIT_getMiddleBits(bitD->bitContaine
347 #else
348 /* this code path is slower on my os-x lap
349 U32 const regMask = sizeof(bitD->bitContai
350 return ((bitD->bitContainer << (bitD->bits
351 #endif
352 }
353
354 /*! BIT_lookBitsFast() :
355 * unsafe version; only works if nbBits >= 1
356 MEM_STATIC size_t BIT_lookBitsFast(const BIT_D
357 {
358 U32 const regMask = sizeof(bitD->bitContai
359 assert(nbBits >= 1);
360 return (bitD->bitContainer << (bitD->bitsC
361 }
362
363 MEM_STATIC FORCE_INLINE_ATTR void BIT_skipBits
364 {
365 bitD->bitsConsumed += nbBits;
366 }
367
368 /*! BIT_readBits() :
369 * Read (consume) next n bits from local regi
370 * Pay attention to not read more than nbBits
371 * @return : extracted value. */
372 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_readBi
373 {
374 size_t const value = BIT_lookBits(bitD, nb
375 BIT_skipBits(bitD, nbBits);
376 return value;
377 }
378
379 /*! BIT_readBitsFast() :
380 * unsafe version; only works only if nbBits
381 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream
382 {
383 size_t const value = BIT_lookBitsFast(bitD
384 assert(nbBits >= 1);
385 BIT_skipBits(bitD, nbBits);
386 return value;
387 }
388
389 /*! BIT_reloadDStreamFast() :
390 * Similar to BIT_reloadDStream(), but with t
391 * 1. bitsConsumed <= sizeof(bitD->bitContain
392 * 2. Returns BIT_DStream_overflow when bitD-
393 * point you must use BIT_reloadDStream()
394 */
395 MEM_STATIC BIT_DStream_status BIT_reloadDStrea
396 {
397 if (UNLIKELY(bitD->ptr < bitD->limitPtr))
398 return BIT_DStream_overflow;
399 assert(bitD->bitsConsumed <= sizeof(bitD->
400 bitD->ptr -= bitD->bitsConsumed >> 3;
401 bitD->bitsConsumed &= 7;
402 bitD->bitContainer = MEM_readLEST(bitD->pt
403 return BIT_DStream_unfinished;
404 }
405
406 /*! BIT_reloadDStream() :
407 * Refill `bitD` from buffer previously set i
408 * This function is safe, it guarantees it wi
409 * @return : status of `BIT_DStream_t` interna
410 * when status == BIT_DStream_unfini
411 MEM_STATIC BIT_DStream_status BIT_reloadDStrea
412 {
413 if (bitD->bitsConsumed > (sizeof(bitD->bit
414 return BIT_DStream_overflow;
415
416 if (bitD->ptr >= bitD->limitPtr) {
417 return BIT_reloadDStreamFast(bitD);
418 }
419 if (bitD->ptr == bitD->start) {
420 if (bitD->bitsConsumed < sizeof(bitD->
421 return BIT_DStream_completed;
422 }
423 /* start < ptr < limitPtr */
424 { U32 nbBytes = bitD->bitsConsumed >> 3;
425 BIT_DStream_status result = BIT_DStrea
426 if (bitD->ptr - nbBytes < bitD->start)
427 nbBytes = (U32)(bitD->ptr - bitD->
428 result = BIT_DStream_endOfBuffer;
429 }
430 bitD->ptr -= nbBytes;
431 bitD->bitsConsumed -= nbBytes*8;
432 bitD->bitContainer = MEM_readLEST(bitD
433 return result;
434 }
435 }
436
437 /*! BIT_endOfDStream() :
438 * @return : 1 if DStream has _exactly_ reache
439 */
440 MEM_STATIC unsigned BIT_endOfDStream(const BIT
441 {
442 return ((DStream->ptr == DStream->start) &
443 }
444
445
446 #endif /* BITSTREAM_H_MODULE */
447
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.