xref: /freebsd/sys/contrib/zstd/lib/common/bitstream.h (revision 56e53cb8ef000c3ef72337a4095987a932cdedef)
1 /* ******************************************************************
2    bitstream
3    Part of FSE library
4    header file (to include)
5    Copyright (C) 2013-2017, Yann Collet.
6 
7    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
8 
9    Redistribution and use in source and binary forms, with or without
10    modification, are permitted provided that the following conditions are
11    met:
12 
13        * Redistributions of source code must retain the above copyright
14    notice, this list of conditions and the following disclaimer.
15        * Redistributions in binary form must reproduce the above
16    copyright notice, this list of conditions and the following disclaimer
17    in the documentation and/or other materials provided with the
18    distribution.
19 
20    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 
32    You can contact the author at :
33    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
34 ****************************************************************** */
35 #ifndef BITSTREAM_H_MODULE
36 #define BITSTREAM_H_MODULE
37 
38 #if defined (__cplusplus)
39 extern "C" {
40 #endif
41 
42 /*
43 *  This API consists of small unitary functions, which must be inlined for best performance.
44 *  Since link-time-optimization is not available for all compilers,
45 *  these functions are defined into a .h to be included.
46 */
47 
48 /*-****************************************
49 *  Dependencies
50 ******************************************/
51 #include "mem.h"            /* unaligned access routines */
52 #include "error_private.h"  /* error codes and messages */
53 
54 
55 /*-*************************************
56 *  Debug
57 ***************************************/
58 #if defined(BIT_DEBUG) && (BIT_DEBUG>=1)
59 #  include <assert.h>
60 #else
61 #  ifndef assert
62 #    define assert(condition) ((void)0)
63 #  endif
64 #endif
65 
66 
67 /*=========================================
68 *  Target specific
69 =========================================*/
70 #if defined(__BMI__) && defined(__GNUC__)
71 #  include <immintrin.h>   /* support for bextr (experimental) */
72 #endif
73 
74 #define STREAM_ACCUMULATOR_MIN_32  25
75 #define STREAM_ACCUMULATOR_MIN_64  57
76 #define STREAM_ACCUMULATOR_MIN    ((U32)(MEM_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
77 
78 
79 /*-******************************************
80 *  bitStream encoding API (write forward)
81 ********************************************/
82 /* bitStream can mix input from multiple sources.
83  * A critical property of these streams is that they encode and decode in **reverse** direction.
84  * So the first bit sequence you add will be the last to be read, like a LIFO stack.
85  */
86 typedef struct
87 {
88     size_t bitContainer;
89     unsigned bitPos;
90     char*  startPtr;
91     char*  ptr;
92     char*  endPtr;
93 } BIT_CStream_t;
94 
95 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
96 MEM_STATIC void   BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
97 MEM_STATIC void   BIT_flushBits(BIT_CStream_t* bitC);
98 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC);
99 
100 /* Start with initCStream, providing the size of buffer to write into.
101 *  bitStream will never write outside of this buffer.
102 *  `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
103 *
104 *  bits are first added to a local register.
105 *  Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
106 *  Writing data into memory is an explicit operation, performed by the flushBits function.
107 *  Hence keep track how many bits are potentially stored into local register to avoid register overflow.
108 *  After a flushBits, a maximum of 7 bits might still be stored into local register.
109 *
110 *  Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
111 *
112 *  Last operation is to close the bitStream.
113 *  The function returns the final size of CStream in bytes.
114 *  If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
115 */
116 
117 
118 /*-********************************************
119 *  bitStream decoding API (read backward)
120 **********************************************/
121 typedef struct
122 {
123     size_t   bitContainer;
124     unsigned bitsConsumed;
125     const char* ptr;
126     const char* start;
127     const char* limitPtr;
128 } BIT_DStream_t;
129 
130 typedef enum { BIT_DStream_unfinished = 0,
131                BIT_DStream_endOfBuffer = 1,
132                BIT_DStream_completed = 2,
133                BIT_DStream_overflow = 3 } BIT_DStream_status;  /* result of BIT_reloadDStream() */
134                /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
135 
136 MEM_STATIC size_t   BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
137 MEM_STATIC size_t   BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
138 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
139 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
140 
141 
142 /* Start by invoking BIT_initDStream().
143 *  A chunk of the bitStream is then stored into a local register.
144 *  Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
145 *  You can then retrieve bitFields stored into the local register, **in reverse order**.
146 *  Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
147 *  A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
148 *  Otherwise, it can be less than that, so proceed accordingly.
149 *  Checking if DStream has reached its end can be performed with BIT_endOfDStream().
150 */
151 
152 
153 /*-****************************************
154 *  unsafe API
155 ******************************************/
156 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
157 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
158 
159 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);
160 /* unsafe version; does not check buffer overflow */
161 
162 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
163 /* faster, but works only if nbBits >= 1 */
164 
165 
166 
167 /*-**************************************************************
168 *  Internal functions
169 ****************************************************************/
170 MEM_STATIC unsigned BIT_highbit32 (register U32 val)
171 {
172     assert(val != 0);
173     {
174 #   if defined(_MSC_VER)   /* Visual */
175         unsigned long r=0;
176         _BitScanReverse ( &r, val );
177         return (unsigned) r;
178 #   elif defined(__GNUC__) && (__GNUC__ >= 3) && __has_builtin(__builtin_clz)   /* Use GCC Intrinsic */
179         return 31 - __builtin_clz (val);
180 #   else   /* Software version */
181         static const unsigned DeBruijnClz[32] = { 0,  9,  1, 10, 13, 21,  2, 29,
182                                                  11, 14, 16, 18, 22, 25,  3, 30,
183                                                   8, 12, 20, 28, 15, 17, 24,  7,
184                                                  19, 27, 23,  6, 26,  5,  4, 31 };
185         U32 v = val;
186         v |= v >> 1;
187         v |= v >> 2;
188         v |= v >> 4;
189         v |= v >> 8;
190         v |= v >> 16;
191         return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
192 #   endif
193     }
194 }
195 
196 /*=====    Local Constants   =====*/
197 static const unsigned BIT_mask[] = {
198     0,          1,         3,         7,         0xF,       0x1F,
199     0x3F,       0x7F,      0xFF,      0x1FF,     0x3FF,     0x7FF,
200     0xFFF,      0x1FFF,    0x3FFF,    0x7FFF,    0xFFFF,    0x1FFFF,
201     0x3FFFF,    0x7FFFF,   0xFFFFF,   0x1FFFFF,  0x3FFFFF,  0x7FFFFF,
202     0xFFFFFF,   0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF,
203     0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits */
204 #define BIT_MASK_SIZE (sizeof(BIT_mask) / sizeof(BIT_mask[0]))
205 
206 /*-**************************************************************
207 *  bitStream encoding
208 ****************************************************************/
209 /*! BIT_initCStream() :
210  *  `dstCapacity` must be > sizeof(size_t)
211  *  @return : 0 if success,
212  *            otherwise an error code (can be tested using ERR_isError()) */
213 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC,
214                                   void* startPtr, size_t dstCapacity)
215 {
216     bitC->bitContainer = 0;
217     bitC->bitPos = 0;
218     bitC->startPtr = (char*)startPtr;
219     bitC->ptr = bitC->startPtr;
220     bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->bitContainer);
221     if (dstCapacity <= sizeof(bitC->bitContainer)) return ERROR(dstSize_tooSmall);
222     return 0;
223 }
224 
225 /*! BIT_addBits() :
226  *  can add up to 31 bits into `bitC`.
227  *  Note : does not check for register overflow ! */
228 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC,
229                             size_t value, unsigned nbBits)
230 {
231     MEM_STATIC_ASSERT(BIT_MASK_SIZE == 32);
232     assert(nbBits < BIT_MASK_SIZE);
233     assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
234     bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
235     bitC->bitPos += nbBits;
236 }
237 
238 /*! BIT_addBitsFast() :
239  *  works only if `value` is _clean_, meaning all high bits above nbBits are 0 */
240 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC,
241                                 size_t value, unsigned nbBits)
242 {
243     assert((value>>nbBits) == 0);
244     assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
245     bitC->bitContainer |= value << bitC->bitPos;
246     bitC->bitPos += nbBits;
247 }
248 
249 /*! BIT_flushBitsFast() :
250  *  assumption : bitContainer has not overflowed
251  *  unsafe version; does not check buffer overflow */
252 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)
253 {
254     size_t const nbBytes = bitC->bitPos >> 3;
255     assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
256     MEM_writeLEST(bitC->ptr, bitC->bitContainer);
257     bitC->ptr += nbBytes;
258     assert(bitC->ptr <= bitC->endPtr);
259     bitC->bitPos &= 7;
260     bitC->bitContainer >>= nbBytes*8;
261 }
262 
263 /*! BIT_flushBits() :
264  *  assumption : bitContainer has not overflowed
265  *  safe version; check for buffer overflow, and prevents it.
266  *  note : does not signal buffer overflow.
267  *  overflow will be revealed later on using BIT_closeCStream() */
268 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)
269 {
270     size_t const nbBytes = bitC->bitPos >> 3;
271     assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
272     MEM_writeLEST(bitC->ptr, bitC->bitContainer);
273     bitC->ptr += nbBytes;
274     if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
275     bitC->bitPos &= 7;
276     bitC->bitContainer >>= nbBytes*8;
277 }
278 
279 /*! BIT_closeCStream() :
280  *  @return : size of CStream, in bytes,
281  *            or 0 if it could not fit into dstBuffer */
282 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)
283 {
284     BIT_addBitsFast(bitC, 1, 1);   /* endMark */
285     BIT_flushBits(bitC);
286     if (bitC->ptr >= bitC->endPtr) return 0; /* overflow detected */
287     return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
288 }
289 
290 
291 /*-********************************************************
292 *  bitStream decoding
293 **********************************************************/
294 /*! BIT_initDStream() :
295  *  Initialize a BIT_DStream_t.
296  * `bitD` : a pointer to an already allocated BIT_DStream_t structure.
297  * `srcSize` must be the *exact* size of the bitStream, in bytes.
298  * @return : size of stream (== srcSize), or an errorCode if a problem is detected
299  */
300 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
301 {
302     if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
303 
304     bitD->start = (const char*)srcBuffer;
305     bitD->limitPtr = bitD->start + sizeof(bitD->bitContainer);
306 
307     if (srcSize >=  sizeof(bitD->bitContainer)) {  /* normal case */
308         bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
309         bitD->bitContainer = MEM_readLEST(bitD->ptr);
310         { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
311           bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;  /* ensures bitsConsumed is always set */
312           if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
313     } else {
314         bitD->ptr   = bitD->start;
315         bitD->bitContainer = *(const BYTE*)(bitD->start);
316         switch(srcSize)
317         {
318         case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
319                 /* fall-through */
320 
321         case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);
322                 /* fall-through */
323 
324         case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);
325                 /* fall-through */
326 
327         case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24;
328                 /* fall-through */
329 
330         case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16;
331                 /* fall-through */
332 
333         case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) <<  8;
334                 /* fall-through */
335 
336         default: break;
337         }
338         {   BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
339             bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
340             if (lastByte == 0) return ERROR(corruption_detected);  /* endMark not present */
341         }
342         bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
343     }
344 
345     return srcSize;
346 }
347 
348 MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
349 {
350     return bitContainer >> start;
351 }
352 
353 MEM_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
354 {
355 #if defined(__BMI__) && defined(__GNUC__) && __GNUC__*1000+__GNUC_MINOR__ >= 4008  /* experimental */
356 #  if defined(__x86_64__)
357     if (sizeof(bitContainer)==8)
358         return _bextr_u64(bitContainer, start, nbBits);
359     else
360 #  endif
361         return _bextr_u32(bitContainer, start, nbBits);
362 #else
363     assert(nbBits < BIT_MASK_SIZE);
364     return (bitContainer >> start) & BIT_mask[nbBits];
365 #endif
366 }
367 
368 MEM_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
369 {
370     assert(nbBits < BIT_MASK_SIZE);
371     return bitContainer & BIT_mask[nbBits];
372 }
373 
374 /*! BIT_lookBits() :
375  *  Provides next n bits from local register.
376  *  local register is not modified.
377  *  On 32-bits, maxNbBits==24.
378  *  On 64-bits, maxNbBits==56.
379  * @return : value extracted */
380 MEM_STATIC size_t BIT_lookBits(const BIT_DStream_t* bitD, U32 nbBits)
381 {
382 #if defined(__BMI__) && defined(__GNUC__)   /* experimental; fails if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8 */
383     return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);
384 #else
385     U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
386     return ((bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> 1) >> ((regMask-nbBits) & regMask);
387 #endif
388 }
389 
390 /*! BIT_lookBitsFast() :
391  *  unsafe version; only works if nbBits >= 1 */
392 MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
393 {
394     U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
395     assert(nbBits >= 1);
396     return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask);
397 }
398 
399 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
400 {
401     bitD->bitsConsumed += nbBits;
402 }
403 
404 /*! BIT_readBits() :
405  *  Read (consume) next n bits from local register and update.
406  *  Pay attention to not read more than nbBits contained into local register.
407  * @return : extracted value. */
408 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
409 {
410     size_t const value = BIT_lookBits(bitD, nbBits);
411     BIT_skipBits(bitD, nbBits);
412     return value;
413 }
414 
415 /*! BIT_readBitsFast() :
416  *  unsafe version; only works only if nbBits >= 1 */
417 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
418 {
419     size_t const value = BIT_lookBitsFast(bitD, nbBits);
420     assert(nbBits >= 1);
421     BIT_skipBits(bitD, nbBits);
422     return value;
423 }
424 
425 /*! BIT_reloadDStream() :
426  *  Refill `bitD` from buffer previously set in BIT_initDStream() .
427  *  This function is safe, it guarantees it will not read beyond src buffer.
428  * @return : status of `BIT_DStream_t` internal register.
429  *           when status == BIT_DStream_unfinished, internal register is filled with at least 25 or 57 bits */
430 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
431 {
432     if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* overflow detected, like end of stream */
433         return BIT_DStream_overflow;
434 
435     if (bitD->ptr >= bitD->limitPtr) {
436         bitD->ptr -= bitD->bitsConsumed >> 3;
437         bitD->bitsConsumed &= 7;
438         bitD->bitContainer = MEM_readLEST(bitD->ptr);
439         return BIT_DStream_unfinished;
440     }
441     if (bitD->ptr == bitD->start) {
442         if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
443         return BIT_DStream_completed;
444     }
445     /* start < ptr < limitPtr */
446     {   U32 nbBytes = bitD->bitsConsumed >> 3;
447         BIT_DStream_status result = BIT_DStream_unfinished;
448         if (bitD->ptr - nbBytes < bitD->start) {
449             nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */
450             result = BIT_DStream_endOfBuffer;
451         }
452         bitD->ptr -= nbBytes;
453         bitD->bitsConsumed -= nbBytes*8;
454         bitD->bitContainer = MEM_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD->bitContainer), otherwise bitD->ptr == bitD->start */
455         return result;
456     }
457 }
458 
459 /*! BIT_endOfDStream() :
460  * @return : 1 if DStream has _exactly_ reached its end (all bits consumed).
461  */
462 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
463 {
464     return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
465 }
466 
467 #if defined (__cplusplus)
468 }
469 #endif
470 
471 #endif /* BITSTREAM_H_MODULE */
472