deps/libchdr/deps/zstd-1.5.6/lib/common/bitstream.h

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