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 assert(val != 0); 173 { 174 # if defined(_MSC_VER) /* Visual */ 175 unsigned long r=0; 176 _BitScanReverse ( &r, val ); 177 return (unsigned) r; 178 # elif defined(__GNUC__) && (__GNUC__ >= 3) && __has_builtin(__builtin_clz) /* Use GCC Intrinsic */ 179 return 31 - __builtin_clz (val); 180 # else /* Software version */ 181 static const unsigned DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 182 11, 14, 16, 18, 22, 25, 3, 30, 183 8, 12, 20, 28, 15, 17, 24, 7, 184 19, 27, 23, 6, 26, 5, 4, 31 }; 185 U32 v = val; 186 v |= v >> 1; 187 v |= v >> 2; 188 v |= v >> 4; 189 v |= v >> 8; 190 v |= v >> 16; 191 return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27]; 192 # endif 193 } 194 } 195 196 /*===== Local Constants =====*/ 197 static const unsigned BIT_mask[] = { 198 0, 1, 3, 7, 0xF, 0x1F, 199 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF, 200 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF, 201 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, 202 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF, 203 0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits */ 204 #define BIT_MASK_SIZE (sizeof(BIT_mask) / sizeof(BIT_mask[0])) 205 206 /*-************************************************************** 207 * bitStream encoding 208 ****************************************************************/ 209 /*! BIT_initCStream() : 210 * `dstCapacity` must be > sizeof(size_t) 211 * @return : 0 if success, 212 * otherwise an error code (can be tested using ERR_isError()) */ 213 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, 214 void* startPtr, size_t dstCapacity) 215 { 216 bitC->bitContainer = 0; 217 bitC->bitPos = 0; 218 bitC->startPtr = (char*)startPtr; 219 bitC->ptr = bitC->startPtr; 220 bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->bitContainer); 221 if (dstCapacity <= sizeof(bitC->bitContainer)) return ERROR(dstSize_tooSmall); 222 return 0; 223 } 224 225 /*! BIT_addBits() : 226 * can add up to 31 bits into `bitC`. 227 * Note : does not check for register overflow ! */ 228 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, 229 size_t value, unsigned nbBits) 230 { 231 MEM_STATIC_ASSERT(BIT_MASK_SIZE == 32); 232 assert(nbBits < BIT_MASK_SIZE); 233 assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8); 234 bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos; 235 bitC->bitPos += nbBits; 236 } 237 238 /*! BIT_addBitsFast() : 239 * works only if `value` is _clean_, meaning all high bits above nbBits are 0 */ 240 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, 241 size_t value, unsigned nbBits) 242 { 243 assert((value>>nbBits) == 0); 244 assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8); 245 bitC->bitContainer |= value << bitC->bitPos; 246 bitC->bitPos += nbBits; 247 } 248 249 /*! BIT_flushBitsFast() : 250 * assumption : bitContainer has not overflowed 251 * unsafe version; does not check buffer overflow */ 252 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC) 253 { 254 size_t const nbBytes = bitC->bitPos >> 3; 255 assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8); 256 MEM_writeLEST(bitC->ptr, bitC->bitContainer); 257 bitC->ptr += nbBytes; 258 assert(bitC->ptr <= bitC->endPtr); 259 bitC->bitPos &= 7; 260 bitC->bitContainer >>= nbBytes*8; 261 } 262 263 /*! BIT_flushBits() : 264 * assumption : bitContainer has not overflowed 265 * safe version; check for buffer overflow, and prevents it. 266 * note : does not signal buffer overflow. 267 * overflow will be revealed later on using BIT_closeCStream() */ 268 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC) 269 { 270 size_t const nbBytes = bitC->bitPos >> 3; 271 assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8); 272 MEM_writeLEST(bitC->ptr, bitC->bitContainer); 273 bitC->ptr += nbBytes; 274 if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr; 275 bitC->bitPos &= 7; 276 bitC->bitContainer >>= nbBytes*8; 277 } 278 279 /*! BIT_closeCStream() : 280 * @return : size of CStream, in bytes, 281 * or 0 if it could not fit into dstBuffer */ 282 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC) 283 { 284 BIT_addBitsFast(bitC, 1, 1); /* endMark */ 285 BIT_flushBits(bitC); 286 if (bitC->ptr >= bitC->endPtr) return 0; /* overflow detected */ 287 return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0); 288 } 289 290 291 /*-******************************************************** 292 * bitStream decoding 293 **********************************************************/ 294 /*! BIT_initDStream() : 295 * Initialize a BIT_DStream_t. 296 * `bitD` : a pointer to an already allocated BIT_DStream_t structure. 297 * `srcSize` must be the *exact* size of the bitStream, in bytes. 298 * @return : size of stream (== srcSize), or an errorCode if a problem is detected 299 */ 300 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize) 301 { 302 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); } 303 304 bitD->start = (const char*)srcBuffer; 305 bitD->limitPtr = bitD->start + sizeof(bitD->bitContainer); 306 307 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */ 308 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer); 309 bitD->bitContainer = MEM_readLEST(bitD->ptr); 310 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1]; 311 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */ 312 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ } 313 } else { 314 bitD->ptr = bitD->start; 315 bitD->bitContainer = *(const BYTE*)(bitD->start); 316 switch(srcSize) 317 { 318 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16); 319 /* fall-through */ 320 321 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24); 322 /* fall-through */ 323 324 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32); 325 /* fall-through */ 326 327 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; 328 /* fall-through */ 329 330 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; 331 /* fall-through */ 332 333 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8; 334 /* fall-through */ 335 336 default: break; 337 } 338 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1]; 339 bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; 340 if (lastByte == 0) return ERROR(corruption_detected); /* endMark not present */ 341 } 342 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8; 343 } 344 345 return srcSize; 346 } 347 348 MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start) 349 { 350 return bitContainer >> start; 351 } 352 353 MEM_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits) 354 { 355 #if defined(__BMI__) && defined(__GNUC__) && __GNUC__*1000+__GNUC_MINOR__ >= 4008 /* experimental */ 356 # if defined(__x86_64__) 357 if (sizeof(bitContainer)==8) 358 return _bextr_u64(bitContainer, start, nbBits); 359 else 360 # endif 361 return _bextr_u32(bitContainer, start, nbBits); 362 #else 363 assert(nbBits < BIT_MASK_SIZE); 364 return (bitContainer >> start) & BIT_mask[nbBits]; 365 #endif 366 } 367 368 MEM_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits) 369 { 370 assert(nbBits < BIT_MASK_SIZE); 371 return bitContainer & BIT_mask[nbBits]; 372 } 373 374 /*! BIT_lookBits() : 375 * Provides next n bits from local register. 376 * local register is not modified. 377 * On 32-bits, maxNbBits==24. 378 * On 64-bits, maxNbBits==56. 379 * @return : value extracted */ 380 MEM_STATIC size_t BIT_lookBits(const BIT_DStream_t* bitD, U32 nbBits) 381 { 382 #if defined(__BMI__) && defined(__GNUC__) /* experimental; fails if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8 */ 383 return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits); 384 #else 385 U32 const regMask = sizeof(bitD->bitContainer)*8 - 1; 386 return ((bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> 1) >> ((regMask-nbBits) & regMask); 387 #endif 388 } 389 390 /*! BIT_lookBitsFast() : 391 * unsafe version; only works if nbBits >= 1 */ 392 MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits) 393 { 394 U32 const regMask = sizeof(bitD->bitContainer)*8 - 1; 395 assert(nbBits >= 1); 396 return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask); 397 } 398 399 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits) 400 { 401 bitD->bitsConsumed += nbBits; 402 } 403 404 /*! BIT_readBits() : 405 * Read (consume) next n bits from local register and update. 406 * Pay attention to not read more than nbBits contained into local register. 407 * @return : extracted value. */ 408 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits) 409 { 410 size_t const value = BIT_lookBits(bitD, nbBits); 411 BIT_skipBits(bitD, nbBits); 412 return value; 413 } 414 415 /*! BIT_readBitsFast() : 416 * unsafe version; only works only if nbBits >= 1 */ 417 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits) 418 { 419 size_t const value = BIT_lookBitsFast(bitD, nbBits); 420 assert(nbBits >= 1); 421 BIT_skipBits(bitD, nbBits); 422 return value; 423 } 424 425 /*! BIT_reloadDStream() : 426 * Refill `bitD` from buffer previously set in BIT_initDStream() . 427 * This function is safe, it guarantees it will not read beyond src buffer. 428 * @return : status of `BIT_DStream_t` internal register. 429 * when status == BIT_DStream_unfinished, internal register is filled with at least 25 or 57 bits */ 430 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD) 431 { 432 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* overflow detected, like end of stream */ 433 return BIT_DStream_overflow; 434 435 if (bitD->ptr >= bitD->limitPtr) { 436 bitD->ptr -= bitD->bitsConsumed >> 3; 437 bitD->bitsConsumed &= 7; 438 bitD->bitContainer = MEM_readLEST(bitD->ptr); 439 return BIT_DStream_unfinished; 440 } 441 if (bitD->ptr == bitD->start) { 442 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer; 443 return BIT_DStream_completed; 444 } 445 /* start < ptr < limitPtr */ 446 { U32 nbBytes = bitD->bitsConsumed >> 3; 447 BIT_DStream_status result = BIT_DStream_unfinished; 448 if (bitD->ptr - nbBytes < bitD->start) { 449 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */ 450 result = BIT_DStream_endOfBuffer; 451 } 452 bitD->ptr -= nbBytes; 453 bitD->bitsConsumed -= nbBytes*8; 454 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD->bitContainer), otherwise bitD->ptr == bitD->start */ 455 return result; 456 } 457 } 458 459 /*! BIT_endOfDStream() : 460 * @return : 1 if DStream has _exactly_ reached its end (all bits consumed). 461 */ 462 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream) 463 { 464 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8)); 465 } 466 467 #if defined (__cplusplus) 468 } 469 #endif 470 471 #endif /* BITSTREAM_H_MODULE */ 472