lib/zstd/bitstream.h

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