sys/contrib/zstd/lib/common/bitstream.h

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