module/zstd/lib/common/bitstream.h

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