lib/zstd/common/bitstream.h

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