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