lib/zstd/bitstream.h

   1 /* SPDX-License-Identifier: (GPL-2.0 or BSD-2-Clause) */
   2 /*
   3  * bitstream
   4  * Part of FSE library
   5  * header file (to include)
   6  * Copyright (C) 2013-2016, Yann Collet.
   7  *
   8  * You can contact the author at :
   9  * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
  10  */
  11 #ifndef BITSTREAM_H_MODULE
  12 #define BITSTREAM_H_MODULE
  13
  14 /*
  15 *  This API consists of small unitary functions, which must be inlined for best performance.
  16 *  Since link-time-optimization is not available for all compilers,
  17 *  these functions are defined into a .h to be included.
  18 */
  19
  20 /*-****************************************
  21 *  Dependencies
  22 ******************************************/
  23 #include "error_private.h" /* error codes and messages */
  24 #include "mem.h"           /* unaligned access routines */
  25
  26 /*=========================================
  27 *  Target specific
  28 =========================================*/
  29 #define STREAM_ACCUMULATOR_MIN_32 25
  30 #define STREAM_ACCUMULATOR_MIN_64 57
  31 #define STREAM_ACCUMULATOR_MIN ((U32)(ZSTD_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
  32
  33 /*-******************************************
  34 *  bitStream encoding API (write forward)
  35 ********************************************/
  36 /* bitStream can mix input from multiple sources.
  37 *  A critical property of these streams is that they encode and decode in **reverse** direction.
  38 *  So the first bit sequence you add will be the last to be read, like a LIFO stack.
  39 */
  40 typedef struct {
  41         size_t bitContainer;
  42         int bitPos;
  43         char *startPtr;
  44         char *ptr;
  45         char *endPtr;
  46 } BIT_CStream_t;
  47
  48 ZSTD_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity);
  49 ZSTD_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned nbBits);
  50 ZSTD_STATIC void BIT_flushBits(BIT_CStream_t *bitC);
  51 ZSTD_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC);
  52
  53 /* Start with initCStream, providing the size of buffer to write into.
  54 *  bitStream will never write outside of this buffer.
  55 *  `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
  56 *
  57 *  bits are first added to a local register.
  58 *  Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
  59 *  Writing data into memory is an explicit operation, performed by the flushBits function.
  60 *  Hence keep track how many bits are potentially stored into local register to avoid register overflow.
  61 *  After a flushBits, a maximum of 7 bits might still be stored into local register.
  62 *
  63 *  Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
  64 *
  65 *  Last operation is to close the bitStream.
  66 *  The function returns the final size of CStream in bytes.
  67 *  If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
  68 */
  69
  70 /*-********************************************
  71 *  bitStream decoding API (read backward)
  72 **********************************************/
  73 typedef struct {
  74         size_t bitContainer;
  75         unsigned bitsConsumed;
  76         const char *ptr;
  77         const char *start;
  78 } BIT_DStream_t;
  79
  80 typedef enum {
  81         BIT_DStream_unfinished = 0,
  82         BIT_DStream_endOfBuffer = 1,
  83         BIT_DStream_completed = 2,
  84         BIT_DStream_overflow = 3
  85 } BIT_DStream_status; /* result of BIT_reloadDStream() */
  86 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
  87
  88 ZSTD_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize);
  89 ZSTD_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, unsigned nbBits);
  90 ZSTD_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD);
  91 ZSTD_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *bitD);
  92
  93 /* Start by invoking BIT_initDStream().
  94 *  A chunk of the bitStream is then stored into a local register.
  95 *  Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
  96 *  You can then retrieve bitFields stored into the local register, **in reverse order**.
  97 *  Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
  98 *  A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
  99 *  Otherwise, it can be less than that, so proceed accordingly.
 100 *  Checking if DStream has reached its end can be performed with BIT_endOfDStream().
 101 */
 102
 103 /*-****************************************
 104 *  unsafe API
 105 ******************************************/
 106 ZSTD_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits);
 107 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
 108
 109 ZSTD_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC);
 110 /* unsafe version; does not check buffer overflow */
 111
 112 ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, unsigned nbBits);
 113 /* faster, but works only if nbBits >= 1 */
 114
 115 /*-**************************************************************
 116 *  Internal functions
 117 ****************************************************************/
 118 ZSTD_STATIC unsigned BIT_highbit32(register U32 val) { return 31 - __builtin_clz(val); }
 119
 120 /*=====    Local Constants   =====*/
 121 static const unsigned BIT_mask[] = {0,       1,       3,       7,       0xF,      0x1F,     0x3F,     0x7F,      0xFF,
 122                                     0x1FF,   0x3FF,   0x7FF,   0xFFF,    0x1FFF,   0x3FFF,   0x7FFF,   0xFFFF,    0x1FFFF,
 123                                     0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF}; /* up to 26 bits */
 124
 125 /*-**************************************************************
 126 *  bitStream encoding
 127 ****************************************************************/
 128 /*! BIT_initCStream() :
 129  *  `dstCapacity` must be > sizeof(void*)
 130  *  @return : 0 if success,
 131                           otherwise an error code (can be tested using ERR_isError() ) */
 132 ZSTD_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *startPtr, size_t dstCapacity)
 133 {
 134         bitC->bitContainer = 0;
 135         bitC->bitPos = 0;
 136         bitC->startPtr = (char *)startPtr;
 137         bitC->ptr = bitC->startPtr;
 138         bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->ptr);
 139         if (dstCapacity <= sizeof(bitC->ptr))
 140                 return ERROR(dstSize_tooSmall);
 141         return 0;
 142 }
 143
 144 /*! BIT_addBits() :
 145         can add up to 26 bits into `bitC`.
 146         Does not check for register overflow ! */
 147 ZSTD_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
 148 {
 149         bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
 150         bitC->bitPos += nbBits;
 151 }
 152
 153 /*! BIT_addBitsFast() :
 154  *  works only if `value` is _clean_, meaning all high bits above nbBits are 0 */
 155 ZSTD_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
 156 {
 157         bitC->bitContainer |= value << bitC->bitPos;
 158         bitC->bitPos += nbBits;
 159 }
 160
 161 /*! BIT_flushBitsFast() :
 162  *  unsafe version; does not check buffer overflow */
 163 ZSTD_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC)
 164 {
 165         size_t const nbBytes = bitC->bitPos >> 3;
 166         ZSTD_writeLEST(bitC->ptr, bitC->bitContainer);
 167         bitC->ptr += nbBytes;
 168         bitC->bitPos &= 7;
 169         bitC->bitContainer >>= nbBytes * 8; /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */
 170 }
 171
 172 /*! BIT_flushBits() :
 173  *  safe version; check for buffer overflow, and prevents it.
 174  *  note : does not signal buffer overflow. This will be revealed later on using BIT_closeCStream() */
 175 ZSTD_STATIC void BIT_flushBits(BIT_CStream_t *bitC)
 176 {
 177         size_t const nbBytes = bitC->bitPos >> 3;
 178         ZSTD_writeLEST(bitC->ptr, bitC->bitContainer);
 179         bitC->ptr += nbBytes;
 180         if (bitC->ptr > bitC->endPtr)
 181                 bitC->ptr = bitC->endPtr;
 182         bitC->bitPos &= 7;
 183         bitC->bitContainer >>= nbBytes * 8; /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */
 184 }
 185
 186 /*! BIT_closeCStream() :
 187  *  @return : size of CStream, in bytes,
 188                           or 0 if it could not fit into dstBuffer */
 189 ZSTD_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
 190 {
 191         BIT_addBitsFast(bitC, 1, 1); /* endMark */
 192         BIT_flushBits(bitC);
 193
 194         if (bitC->ptr >= bitC->endPtr)
 195                 return 0; /* doesn't fit within authorized budget : cancel */
 196
 197         return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
 198 }
 199
 200 /*-********************************************************
 201 * bitStream decoding
 202 **********************************************************/
 203 /*! BIT_initDStream() :
 204 *   Initialize a BIT_DStream_t.
 205 *   `bitD` : a pointer to an already allocated BIT_DStream_t structure.
 206 *   `srcSize` must be the *exact* size of the bitStream, in bytes.
 207 *   @return : size of stream (== srcSize) or an errorCode if a problem is detected
 208 */
 209 ZSTD_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize)
 210 {
 211         if (srcSize < 1) {
 212                 memset(bitD, 0, sizeof(*bitD));
 213                 return ERROR(srcSize_wrong);
 214         }
 215
 216         if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
 217                 bitD->start = (const char *)srcBuffer;
 218                 bitD->ptr = (const char *)srcBuffer + srcSize - sizeof(bitD->bitContainer);
 219                 bitD->bitContainer = ZSTD_readLEST(bitD->ptr);
 220                 {
 221                         BYTE const lastByte = ((const BYTE *)srcBuffer)[srcSize - 1];
 222                         bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */
 223                         if (lastByte == 0)
 224                                 return ERROR(GENERIC); /* endMark not present */
 225                 }
 226         } else {
 227                 bitD->start = (const char *)srcBuffer;
 228                 bitD->ptr = bitD->start;
 229                 bitD->bitContainer = *(const BYTE *)(bitD->start);
 230                 switch (srcSize) {
 231                 case 7: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[6]) << (sizeof(bitD->bitContainer) * 8 - 16);
 232                 case 6: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[5]) << (sizeof(bitD->bitContainer) * 8 - 24);
 233                 case 5: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[4]) << (sizeof(bitD->bitContainer) * 8 - 32);
 234                 case 4: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[3]) << 24;
 235                 case 3: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[2]) << 16;
 236                 case 2: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[1]) << 8;
 237                 default:;
 238                 }
 239                 {
 240                         BYTE const lastByte = ((const BYTE *)srcBuffer)[srcSize - 1];
 241                         bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
 242                         if (lastByte == 0)
 243                                 return ERROR(GENERIC); /* endMark not present */
 244                 }
 245                 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize) * 8;
 246         }
 247
 248         return srcSize;
 249 }
 250
 251 ZSTD_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start) { return bitContainer >> start; }
 252
 253 ZSTD_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits) { return (bitContainer >> start) & BIT_mask[nbBits]; }
 254
 255 ZSTD_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits) { return bitContainer & BIT_mask[nbBits]; }
 256
 257 /*! BIT_lookBits() :
 258  *  Provides next n bits from local register.
 259  *  local register is not modified.
 260  *  On 32-bits, maxNbBits==24.
 261  *  On 64-bits, maxNbBits==56.
 262  *  @return : value extracted
 263  */
 264 ZSTD_STATIC size_t BIT_lookBits(const BIT_DStream_t *bitD, U32 nbBits)
 265 {
 266         U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1;
 267         return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask - nbBits) & bitMask);
 268 }
 269
 270 /*! BIT_lookBitsFast() :
 271 *   unsafe version; only works only if nbBits >= 1 */
 272 ZSTD_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t *bitD, U32 nbBits)
 273 {
 274         U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1;
 275         return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask + 1) - nbBits) & bitMask);
 276 }
 277
 278 ZSTD_STATIC void BIT_skipBits(BIT_DStream_t *bitD, U32 nbBits) { bitD->bitsConsumed += nbBits; }
 279
 280 /*! BIT_readBits() :
 281  *  Read (consume) next n bits from local register and update.
 282  *  Pay attention to not read more than nbBits contained into local register.
 283  *  @return : extracted value.
 284  */
 285 ZSTD_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, U32 nbBits)
 286 {
 287         size_t const value = BIT_lookBits(bitD, nbBits);
 288         BIT_skipBits(bitD, nbBits);
 289         return value;
 290 }
 291
 292 /*! BIT_readBitsFast() :
 293 *   unsafe version; only works only if nbBits >= 1 */
 294 ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, U32 nbBits)
 295 {
 296         size_t const value = BIT_lookBitsFast(bitD, nbBits);
 297         BIT_skipBits(bitD, nbBits);
 298         return value;
 299 }
 300
 301 /*! BIT_reloadDStream() :
 302 *   Refill `bitD` from buffer previously set in BIT_initDStream() .
 303 *   This function is safe, it guarantees it will not read beyond src buffer.
 304 *   @return : status of `BIT_DStream_t` internal register.
 305                           if status == BIT_DStream_unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */
 306 ZSTD_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
 307 {
 308         if (bitD->bitsConsumed > (sizeof(bitD->bitContainer) * 8)) /* should not happen => corruption detected */
 309                 return BIT_DStream_overflow;
 310
 311         if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
 312                 bitD->ptr -= bitD->bitsConsumed >> 3;
 313                 bitD->bitsConsumed &= 7;
 314                 bitD->bitContainer = ZSTD_readLEST(bitD->ptr);
 315                 return BIT_DStream_unfinished;
 316         }
 317         if (bitD->ptr == bitD->start) {
 318                 if (bitD->bitsConsumed < sizeof(bitD->bitContainer) * 8)
 319                         return BIT_DStream_endOfBuffer;
 320                 return BIT_DStream_completed;
 321         }
 322         {
 323                 U32 nbBytes = bitD->bitsConsumed >> 3;
 324                 BIT_DStream_status result = BIT_DStream_unfinished;
 325                 if (bitD->ptr - nbBytes < bitD->start) {
 326                         nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
 327                         result = BIT_DStream_endOfBuffer;
 328                 }
 329                 bitD->ptr -= nbBytes;
 330                 bitD->bitsConsumed -= nbBytes * 8;
 331                 bitD->bitContainer = ZSTD_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
 332                 return result;
 333         }
 334 }
 335
 336 /*! BIT_endOfDStream() :
 337 *   @return Tells if DStream has exactly reached its end (all bits consumed).
 338 */
 339 ZSTD_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *DStream)
 340 {
 341         return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer) * 8));
 342 }
 343
 344 #endif /* BITSTREAM_H_MODULE */