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