Back to home page

OSCL-LXR
 
 

     

0001 /* ******************************************************************
0002  * bitstream
0003  * Part of FSE library
0004  * Copyright (c) Yann Collet, Facebook, Inc.
0005  *
0006  * You can contact the author at :
0007  * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
0008  *
0009  * This source code is licensed under both the BSD-style license (found in the
0010  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
0011  * in the COPYING file in the root directory of this source tree).
0012  * You may select, at your option, one of the above-listed licenses.
0013 ****************************************************************** */
0014 #ifndef BITSTREAM_H_MODULE
0015 #define BITSTREAM_H_MODULE
0016 
0017 /*
0018 *  This API consists of small unitary functions, which must be inlined for best performance.
0019 *  Since link-time-optimization is not available for all compilers,
0020 *  these functions are defined into a .h to be included.
0021 */
0022 
0023 /*-****************************************
0024 *  Dependencies
0025 ******************************************/
0026 #include "mem.h"            /* unaligned access routines */
0027 #include "compiler.h"       /* UNLIKELY() */
0028 #include "debug.h"          /* assert(), DEBUGLOG(), RAWLOG() */
0029 #include "error_private.h"  /* error codes and messages */
0030 
0031 
0032 /*=========================================
0033 *  Target specific
0034 =========================================*/
0035 
0036 #define STREAM_ACCUMULATOR_MIN_32  25
0037 #define STREAM_ACCUMULATOR_MIN_64  57
0038 #define STREAM_ACCUMULATOR_MIN    ((U32)(MEM_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
0039 
0040 
0041 /*-******************************************
0042 *  bitStream encoding API (write forward)
0043 ********************************************/
0044 /* bitStream can mix input from multiple sources.
0045  * A critical property of these streams is that they encode and decode in **reverse** direction.
0046  * So the first bit sequence you add will be the last to be read, like a LIFO stack.
0047  */
0048 typedef struct {
0049     size_t bitContainer;
0050     unsigned bitPos;
0051     char*  startPtr;
0052     char*  ptr;
0053     char*  endPtr;
0054 } BIT_CStream_t;
0055 
0056 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
0057 MEM_STATIC void   BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
0058 MEM_STATIC void   BIT_flushBits(BIT_CStream_t* bitC);
0059 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC);
0060 
0061 /* Start with initCStream, providing the size of buffer to write into.
0062 *  bitStream will never write outside of this buffer.
0063 *  `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
0064 *
0065 *  bits are first added to a local register.
0066 *  Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
0067 *  Writing data into memory is an explicit operation, performed by the flushBits function.
0068 *  Hence keep track how many bits are potentially stored into local register to avoid register overflow.
0069 *  After a flushBits, a maximum of 7 bits might still be stored into local register.
0070 *
0071 *  Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
0072 *
0073 *  Last operation is to close the bitStream.
0074 *  The function returns the final size of CStream in bytes.
0075 *  If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
0076 */
0077 
0078 
0079 /*-********************************************
0080 *  bitStream decoding API (read backward)
0081 **********************************************/
0082 typedef struct {
0083     size_t   bitContainer;
0084     unsigned bitsConsumed;
0085     const char* ptr;
0086     const char* start;
0087     const char* limitPtr;
0088 } BIT_DStream_t;
0089 
0090 typedef enum { BIT_DStream_unfinished = 0,
0091                BIT_DStream_endOfBuffer = 1,
0092                BIT_DStream_completed = 2,
0093                BIT_DStream_overflow = 3 } BIT_DStream_status;  /* result of BIT_reloadDStream() */
0094                /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
0095 
0096 MEM_STATIC size_t   BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
0097 MEM_STATIC size_t   BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
0098 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
0099 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
0100 
0101 
0102 /* Start by invoking BIT_initDStream().
0103 *  A chunk of the bitStream is then stored into a local register.
0104 *  Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
0105 *  You can then retrieve bitFields stored into the local register, **in reverse order**.
0106 *  Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
0107 *  A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
0108 *  Otherwise, it can be less than that, so proceed accordingly.
0109 *  Checking if DStream has reached its end can be performed with BIT_endOfDStream().
0110 */
0111 
0112 
0113 /*-****************************************
0114 *  unsafe API
0115 ******************************************/
0116 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
0117 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
0118 
0119 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);
0120 /* unsafe version; does not check buffer overflow */
0121 
0122 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
0123 /* faster, but works only if nbBits >= 1 */
0124 
0125 
0126 
0127 /*-**************************************************************
0128 *  Internal functions
0129 ****************************************************************/
0130 MEM_STATIC unsigned BIT_highbit32 (U32 val)
0131 {
0132     assert(val != 0);
0133     {
0134 #   if (__GNUC__ >= 3)   /* Use GCC Intrinsic */
0135         return __builtin_clz (val) ^ 31;
0136 #   else   /* Software version */
0137         static const unsigned DeBruijnClz[32] = { 0,  9,  1, 10, 13, 21,  2, 29,
0138                                                  11, 14, 16, 18, 22, 25,  3, 30,
0139                                                   8, 12, 20, 28, 15, 17, 24,  7,
0140                                                  19, 27, 23,  6, 26,  5,  4, 31 };
0141         U32 v = val;
0142         v |= v >> 1;
0143         v |= v >> 2;
0144         v |= v >> 4;
0145         v |= v >> 8;
0146         v |= v >> 16;
0147         return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
0148 #   endif
0149     }
0150 }
0151 
0152 /*=====    Local Constants   =====*/
0153 static const unsigned BIT_mask[] = {
0154     0,          1,         3,         7,         0xF,       0x1F,
0155     0x3F,       0x7F,      0xFF,      0x1FF,     0x3FF,     0x7FF,
0156     0xFFF,      0x1FFF,    0x3FFF,    0x7FFF,    0xFFFF,    0x1FFFF,
0157     0x3FFFF,    0x7FFFF,   0xFFFFF,   0x1FFFFF,  0x3FFFFF,  0x7FFFFF,
0158     0xFFFFFF,   0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF,
0159     0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits */
0160 #define BIT_MASK_SIZE (sizeof(BIT_mask) / sizeof(BIT_mask[0]))
0161 
0162 /*-**************************************************************
0163 *  bitStream encoding
0164 ****************************************************************/
0165 /*! BIT_initCStream() :
0166  *  `dstCapacity` must be > sizeof(size_t)
0167  *  @return : 0 if success,
0168  *            otherwise an error code (can be tested using ERR_isError()) */
0169 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC,
0170                                   void* startPtr, size_t dstCapacity)
0171 {
0172     bitC->bitContainer = 0;
0173     bitC->bitPos = 0;
0174     bitC->startPtr = (char*)startPtr;
0175     bitC->ptr = bitC->startPtr;
0176     bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->bitContainer);
0177     if (dstCapacity <= sizeof(bitC->bitContainer)) return ERROR(dstSize_tooSmall);
0178     return 0;
0179 }
0180 
0181 /*! BIT_addBits() :
0182  *  can add up to 31 bits into `bitC`.
0183  *  Note : does not check for register overflow ! */
0184 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC,
0185                             size_t value, unsigned nbBits)
0186 {
0187     DEBUG_STATIC_ASSERT(BIT_MASK_SIZE == 32);
0188     assert(nbBits < BIT_MASK_SIZE);
0189     assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
0190     bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
0191     bitC->bitPos += nbBits;
0192 }
0193 
0194 /*! BIT_addBitsFast() :
0195  *  works only if `value` is _clean_,
0196  *  meaning all high bits above nbBits are 0 */
0197 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC,
0198                                 size_t value, unsigned nbBits)
0199 {
0200     assert((value>>nbBits) == 0);
0201     assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
0202     bitC->bitContainer |= value << bitC->bitPos;
0203     bitC->bitPos += nbBits;
0204 }
0205 
0206 /*! BIT_flushBitsFast() :
0207  *  assumption : bitContainer has not overflowed
0208  *  unsafe version; does not check buffer overflow */
0209 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)
0210 {
0211     size_t const nbBytes = bitC->bitPos >> 3;
0212     assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
0213     assert(bitC->ptr <= bitC->endPtr);
0214     MEM_writeLEST(bitC->ptr, bitC->bitContainer);
0215     bitC->ptr += nbBytes;
0216     bitC->bitPos &= 7;
0217     bitC->bitContainer >>= nbBytes*8;
0218 }
0219 
0220 /*! BIT_flushBits() :
0221  *  assumption : bitContainer has not overflowed
0222  *  safe version; check for buffer overflow, and prevents it.
0223  *  note : does not signal buffer overflow.
0224  *  overflow will be revealed later on using BIT_closeCStream() */
0225 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)
0226 {
0227     size_t const nbBytes = bitC->bitPos >> 3;
0228     assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
0229     assert(bitC->ptr <= bitC->endPtr);
0230     MEM_writeLEST(bitC->ptr, bitC->bitContainer);
0231     bitC->ptr += nbBytes;
0232     if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
0233     bitC->bitPos &= 7;
0234     bitC->bitContainer >>= nbBytes*8;
0235 }
0236 
0237 /*! BIT_closeCStream() :
0238  *  @return : size of CStream, in bytes,
0239  *            or 0 if it could not fit into dstBuffer */
0240 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)
0241 {
0242     BIT_addBitsFast(bitC, 1, 1);   /* endMark */
0243     BIT_flushBits(bitC);
0244     if (bitC->ptr >= bitC->endPtr) return 0; /* overflow detected */
0245     return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
0246 }
0247 
0248 
0249 /*-********************************************************
0250 *  bitStream decoding
0251 **********************************************************/
0252 /*! BIT_initDStream() :
0253  *  Initialize a BIT_DStream_t.
0254  * `bitD` : a pointer to an already allocated BIT_DStream_t structure.
0255  * `srcSize` must be the *exact* size of the bitStream, in bytes.
0256  * @return : size of stream (== srcSize), or an errorCode if a problem is detected
0257  */
0258 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
0259 {
0260     if (srcSize < 1) { ZSTD_memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
0261 
0262     bitD->start = (const char*)srcBuffer;
0263     bitD->limitPtr = bitD->start + sizeof(bitD->bitContainer);
0264 
0265     if (srcSize >=  sizeof(bitD->bitContainer)) {  /* normal case */
0266         bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
0267         bitD->bitContainer = MEM_readLEST(bitD->ptr);
0268         { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
0269           bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;  /* ensures bitsConsumed is always set */
0270           if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
0271     } else {
0272         bitD->ptr   = bitD->start;
0273         bitD->bitContainer = *(const BYTE*)(bitD->start);
0274         switch(srcSize)
0275         {
0276         case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
0277                 ZSTD_FALLTHROUGH;
0278 
0279         case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);
0280                 ZSTD_FALLTHROUGH;
0281 
0282         case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);
0283                 ZSTD_FALLTHROUGH;
0284 
0285         case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24;
0286                 ZSTD_FALLTHROUGH;
0287 
0288         case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16;
0289                 ZSTD_FALLTHROUGH;
0290 
0291         case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) <<  8;
0292                 ZSTD_FALLTHROUGH;
0293 
0294         default: break;
0295         }
0296         {   BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
0297             bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
0298             if (lastByte == 0) return ERROR(corruption_detected);  /* endMark not present */
0299         }
0300         bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
0301     }
0302 
0303     return srcSize;
0304 }
0305 
0306 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
0307 {
0308     return bitContainer >> start;
0309 }
0310 
0311 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
0312 {
0313     U32 const regMask = sizeof(bitContainer)*8 - 1;
0314     /* if start > regMask, bitstream is corrupted, and result is undefined */
0315     assert(nbBits < BIT_MASK_SIZE);
0316     return (bitContainer >> (start & regMask)) & BIT_mask[nbBits];
0317 }
0318 
0319 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
0320 {
0321     assert(nbBits < BIT_MASK_SIZE);
0322     return bitContainer & BIT_mask[nbBits];
0323 }
0324 
0325 /*! BIT_lookBits() :
0326  *  Provides next n bits from local register.
0327  *  local register is not modified.
0328  *  On 32-bits, maxNbBits==24.
0329  *  On 64-bits, maxNbBits==56.
0330  * @return : value extracted */
0331 MEM_STATIC  FORCE_INLINE_ATTR size_t BIT_lookBits(const BIT_DStream_t*  bitD, U32 nbBits)
0332 {
0333     /* arbitrate between double-shift and shift+mask */
0334 #if 1
0335     /* if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8,
0336      * bitstream is likely corrupted, and result is undefined */
0337     return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);
0338 #else
0339     /* this code path is slower on my os-x laptop */
0340     U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
0341     return ((bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> 1) >> ((regMask-nbBits) & regMask);
0342 #endif
0343 }
0344 
0345 /*! BIT_lookBitsFast() :
0346  *  unsafe version; only works if nbBits >= 1 */
0347 MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
0348 {
0349     U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
0350     assert(nbBits >= 1);
0351     return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask);
0352 }
0353 
0354 MEM_STATIC FORCE_INLINE_ATTR void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
0355 {
0356     bitD->bitsConsumed += nbBits;
0357 }
0358 
0359 /*! BIT_readBits() :
0360  *  Read (consume) next n bits from local register and update.
0361  *  Pay attention to not read more than nbBits contained into local register.
0362  * @return : extracted value. */
0363 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits)
0364 {
0365     size_t const value = BIT_lookBits(bitD, nbBits);
0366     BIT_skipBits(bitD, nbBits);
0367     return value;
0368 }
0369 
0370 /*! BIT_readBitsFast() :
0371  *  unsafe version; only works only if nbBits >= 1 */
0372 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits)
0373 {
0374     size_t const value = BIT_lookBitsFast(bitD, nbBits);
0375     assert(nbBits >= 1);
0376     BIT_skipBits(bitD, nbBits);
0377     return value;
0378 }
0379 
0380 /*! BIT_reloadDStreamFast() :
0381  *  Similar to BIT_reloadDStream(), but with two differences:
0382  *  1. bitsConsumed <= sizeof(bitD->bitContainer)*8 must hold!
0383  *  2. Returns BIT_DStream_overflow when bitD->ptr < bitD->limitPtr, at this
0384  *     point you must use BIT_reloadDStream() to reload.
0385  */
0386 MEM_STATIC BIT_DStream_status BIT_reloadDStreamFast(BIT_DStream_t* bitD)
0387 {
0388     if (UNLIKELY(bitD->ptr < bitD->limitPtr))
0389         return BIT_DStream_overflow;
0390     assert(bitD->bitsConsumed <= sizeof(bitD->bitContainer)*8);
0391     bitD->ptr -= bitD->bitsConsumed >> 3;
0392     bitD->bitsConsumed &= 7;
0393     bitD->bitContainer = MEM_readLEST(bitD->ptr);
0394     return BIT_DStream_unfinished;
0395 }
0396 
0397 /*! BIT_reloadDStream() :
0398  *  Refill `bitD` from buffer previously set in BIT_initDStream() .
0399  *  This function is safe, it guarantees it will not read beyond src buffer.
0400  * @return : status of `BIT_DStream_t` internal register.
0401  *           when status == BIT_DStream_unfinished, internal register is filled with at least 25 or 57 bits */
0402 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
0403 {
0404     if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* overflow detected, like end of stream */
0405         return BIT_DStream_overflow;
0406 
0407     if (bitD->ptr >= bitD->limitPtr) {
0408         return BIT_reloadDStreamFast(bitD);
0409     }
0410     if (bitD->ptr == bitD->start) {
0411         if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
0412         return BIT_DStream_completed;
0413     }
0414     /* start < ptr < limitPtr */
0415     {   U32 nbBytes = bitD->bitsConsumed >> 3;
0416         BIT_DStream_status result = BIT_DStream_unfinished;
0417         if (bitD->ptr - nbBytes < bitD->start) {
0418             nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */
0419             result = BIT_DStream_endOfBuffer;
0420         }
0421         bitD->ptr -= nbBytes;
0422         bitD->bitsConsumed -= nbBytes*8;
0423         bitD->bitContainer = MEM_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD->bitContainer), otherwise bitD->ptr == bitD->start */
0424         return result;
0425     }
0426 }
0427 
0428 /*! BIT_endOfDStream() :
0429  * @return : 1 if DStream has _exactly_ reached its end (all bits consumed).
0430  */
0431 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
0432 {
0433     return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
0434 }
0435 
0436 
0437 #endif /* BITSTREAM_H_MODULE */
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!