contrib/zstd/lib/common/bitstream.h

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