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    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 /*

    44 *  This API consists of small unitary functions, which must be inlined for best performance.

    45 *  Since link-time-optimization is not available for all compilers,

    46 *  these functions are defined into a .h to be included.

    47 */

    48 

    49 /*-****************************************

    50 *  Dependencies

    51 ******************************************/

    52 #include "mem.h"            /* unaligned access routines */

    53 #include "error_private.h"  /* error codes and messages */

    54 

    55 

    56 /*=========================================

    57 *  Target specific

    58 =========================================*/

    59 #if defined(__BMI__) && defined(__GNUC__)

    60 #  include <immintrin.h>   /* support for bextr (experimental) */

    61 #endif

    62 

    63 

    64 /*-******************************************

    65 *  bitStream encoding API (write forward)

    66 ********************************************/

    67 /* bitStream can mix input from multiple sources.

    68 *  A critical property of these streams is that they encode and decode in **reverse** direction.

    69 *  So the first bit sequence you add will be the last to be read, like a LIFO stack.

    70 */

    71 typedef struct

    72 {

    73     size_t bitContainer;

    74     int    bitPos;

    75     char*  startPtr;

    76     char*  ptr;

    77     char*  endPtr;

    78 } BIT_CStream_t;

    79 

    80 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);

    81 MEM_STATIC void   BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);

    82 MEM_STATIC void   BIT_flushBits(BIT_CStream_t* bitC);

    83 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC);

    84 

    85 /* Start with initCStream, providing the size of buffer to write into.

    86 *  bitStream will never write outside of this buffer.

    87 *  `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.

    88 *

    89 *  bits are first added to a local register.

    90 *  Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.

    91 *  Writing data into memory is an explicit operation, performed by the flushBits function.

    92 *  Hence keep track how many bits are potentially stored into local register to avoid register overflow.

    93 *  After a flushBits, a maximum of 7 bits might still be stored into local register.

    94 *

    95 *  Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.

    96 *

    97 *  Last operation is to close the bitStream.

    98 *  The function returns the final size of CStream in bytes.

    99 *  If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)

   100 */

   101 

   102 

   103 /*-********************************************

   104 *  bitStream decoding API (read backward)

   105 **********************************************/

   106 typedef struct

   107 {

   108     size_t   bitContainer;

   109     unsigned bitsConsumed;

   110     const char* ptr;

   111     const char* start;

   112 } BIT_DStream_t;

   113 

   114 typedef enum { BIT_DStream_unfinished = 0,

   115                BIT_DStream_endOfBuffer = 1,

   116                BIT_DStream_completed = 2,

   117                BIT_DStream_overflow = 3 } BIT_DStream_status;  /* result of BIT_reloadDStream() */

   118                /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */

   119 

   120 MEM_STATIC size_t   BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);

   121 MEM_STATIC size_t   BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);

   122 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);

   123 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);

   124 

   125 

   126 /* Start by invoking BIT_initDStream().

   127 *  A chunk of the bitStream is then stored into a local register.

   128 *  Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).

   129 *  You can then retrieve bitFields stored into the local register, **in reverse order**.

   130 *  Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.

   131 *  A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.

   132 *  Otherwise, it can be less than that, so proceed accordingly.

   133 *  Checking if DStream has reached its end can be performed with BIT_endOfDStream().

   134 */

   135 

   136 

   137 /*-****************************************

   138 *  unsafe API

   139 ******************************************/

   140 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);

   141 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */

   142 

   143 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);

   144 /* unsafe version; does not check buffer overflow */

   145 

   146 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);

   147 /* faster, but works only if nbBits >= 1 */

   148 

   149 

   150 

   151 /*-**************************************************************

   152 *  Internal functions

   153 ****************************************************************/

   154 MEM_STATIC unsigned BIT_highbit32 (register U32 val)

   155 {

   156 #   if defined(_MSC_VER)   /* Visual */

   157     unsigned long r=0;

   158     _BitScanReverse ( &r, val );

   159     return (unsigned) r;

   160 #   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* Use GCC Intrinsic */

   161     return 31 - __builtin_clz (val);

   162 #   else   /* Software version */

   163     static const unsigned DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 };

   164     U32 v = val;

   165     v |= v >> 1;

   166     v |= v >> 2;

   167     v |= v >> 4;

   168     v |= v >> 8;

   169     v |= v >> 16;

   170     return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];

   171 #   endif

   172 }

   173 

   174 /*=====    Local Constants   =====*/

   175 static const unsigned BIT_mask[] = { 0, 1, 3, 7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF,  0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF };   /* up to 26 bits */

   176 

   177 

   178 /*-**************************************************************

   179 *  bitStream encoding

   180 ****************************************************************/

   181 /*! BIT_initCStream() :

   182  *  `dstCapacity` must be > sizeof(void*)

   183  *  @return : 0 if success,

   184               otherwise an error code (can be tested using ERR_isError() ) */

   185 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* startPtr, size_t dstCapacity)

   186 {

   187     bitC->bitContainer = 0;

   188     bitC->bitPos = 0;

   189     bitC->startPtr = (char*)startPtr;

   190     bitC->ptr = bitC->startPtr;

   191     bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->ptr);

   192     if (dstCapacity <= sizeof(bitC->ptr)) return ERROR(dstSize_tooSmall);

   193     return 0;

   194 }

   195 

   196 /*! BIT_addBits() :

   197     can add up to 26 bits into `bitC`.

   198     Does not check for register overflow ! */

   199 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits)

   200 {

   201     bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;

   202     bitC->bitPos += nbBits;

   203 }

   204 

   205 /*! BIT_addBitsFast() :

   206  *  works only if `value` is _clean_, meaning all high bits above nbBits are 0 */

   207 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits)

   208 {

   209     bitC->bitContainer |= value << bitC->bitPos;

   210     bitC->bitPos += nbBits;

   211 }

   212 

   213 /*! BIT_flushBitsFast() :

   214  *  unsafe version; does not check buffer overflow */

   215 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)

   216 {

   217     size_t const nbBytes = bitC->bitPos >> 3;

   218     MEM_writeLEST(bitC->ptr, bitC->bitContainer);

   219     bitC->ptr += nbBytes;

   220     bitC->bitPos &= 7;

   221     bitC->bitContainer >>= nbBytes*8;   /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */

   222 }

   223 

   224 /*! BIT_flushBits() :

   225  *  safe version; check for buffer overflow, and prevents it.

   226  *  note : does not signal buffer overflow. This will be revealed later on using BIT_closeCStream() */

   227 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)

   228 {

   229     size_t const nbBytes = bitC->bitPos >> 3;

   230     MEM_writeLEST(bitC->ptr, bitC->bitContainer);

   231     bitC->ptr += nbBytes;

   232     if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;

   233     bitC->bitPos &= 7;

   234     bitC->bitContainer >>= nbBytes*8;   /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */

   235 }

   236 

   237 /*! BIT_closeCStream() :

   238  *  @return : size of CStream, in bytes,

   239               or 0 if it could not fit into dstBuffer */

   240 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)

   241 {

   242     BIT_addBitsFast(bitC, 1, 1);   /* endMark */

   243     BIT_flushBits(bitC);

   244 

   245     if (bitC->ptr >= bitC->endPtr) return 0; /* doesn't fit within authorized budget : cancel */

   246 

   247     return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);

   248 }

   249 

   250 

   251 /*-********************************************************

   252 * bitStream decoding

   253 **********************************************************/

   254 /*! BIT_initDStream() :

   255 *   Initialize a BIT_DStream_t.

   256 *   `bitD` : a pointer to an already allocated BIT_DStream_t structure.

   257 *   `srcSize` must be the *exact* size of the bitStream, in bytes.

   258 *   @return : size of stream (== srcSize) or an errorCode if a problem is detected

   259 */

   260 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)

   261 {

   262     if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }

   263 

   264     if (srcSize >=  sizeof(bitD->bitContainer)) {  /* normal case */

   265         bitD->start = (const char*)srcBuffer;

   266         bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);

   267         bitD->bitContainer = MEM_readLEST(bitD->ptr);

   268         { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];

   269           bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;

   270           if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }

   271     } else {

   272         bitD->start = (const char*)srcBuffer;

   273         bitD->ptr   = bitD->start;

   274         bitD->bitContainer = *(const BYTE*)(bitD->start);

   275         switch(srcSize)

   276         {

   277             case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);

   278             case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);

   279             case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);

   280             case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24;

   281             case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16;

   282             case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) <<  8;

   283             default:;

   284         }

   285         { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];

   286           bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;

   287           if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }

   288         bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;

   289     }

   290 

   291     return srcSize;

   292 }

   293 

   294 MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)

   295 {

   296     return bitContainer >> start;

   297 }

   298 

   299 MEM_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)

   300 {

   301 #if defined(__BMI__) && defined(__GNUC__)   /* experimental */

   302 #  if defined(__x86_64__)

   303     if (sizeof(bitContainer)==8)

   304         return _bextr_u64(bitContainer, start, nbBits);

   305     else

   306 #  endif

   307         return _bextr_u32(bitContainer, start, nbBits);

   308 #else

   309     return (bitContainer >> start) & BIT_mask[nbBits];

   310 #endif

   311 }

   312 

   313 MEM_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)

   314 {

   315     return bitContainer & BIT_mask[nbBits];

   316 }

   317 

   318 /*! BIT_lookBits() :

   319  *  Provides next n bits from local register.

   320  *  local register is not modified.

   321  *  On 32-bits, maxNbBits==24.

   322  *  On 64-bits, maxNbBits==56.

   323  *  @return : value extracted

   324  */

   325  MEM_STATIC size_t BIT_lookBits(const BIT_DStream_t* bitD, U32 nbBits)

   326 {

   327 #if defined(__BMI__) && defined(__GNUC__)   /* experimental; fails if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8 */

   328     return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);

   329 #else

   330     U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;

   331     return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);

   332 #endif

   333 }

   334 

   335 /*! BIT_lookBitsFast() :

   336 *   unsafe version; only works only if nbBits >= 1 */

   337 MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)

   338 {

   339     U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;

   340     return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);

   341 }

   342 

   343 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)

   344 {

   345     bitD->bitsConsumed += nbBits;

   346 }

   347 

   348 /*! BIT_readBits() :

   349  *  Read (consume) next n bits from local register and update.

   350  *  Pay attention to not read more than nbBits contained into local register.

   351  *  @return : extracted value.

   352  */

   353 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)

   354 {

   355     size_t const value = BIT_lookBits(bitD, nbBits);

   356     BIT_skipBits(bitD, nbBits);

   357     return value;

   358 }

   359 

   360 /*! BIT_readBitsFast() :

   361 *   unsafe version; only works only if nbBits >= 1 */

   362 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)

   363 {

   364     size_t const value = BIT_lookBitsFast(bitD, nbBits);

   365     BIT_skipBits(bitD, nbBits);

   366     return value;

   367 }

   368 

   369 /*! BIT_reloadDStream() :

   370 *   Refill `BIT_DStream_t` from src buffer previously defined (see BIT_initDStream() ).

   371 *   This function is safe, it guarantees it will not read beyond src buffer.

   372 *   @return : status of `BIT_DStream_t` internal register.

   373               if status == unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */

   374 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)

   375 {

   376 	if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* should not happen => corruption detected */

   377 		return BIT_DStream_overflow;

   378 

   379     if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {

   380         bitD->ptr -= bitD->bitsConsumed >> 3;

   381         bitD->bitsConsumed &= 7;

   382         bitD->bitContainer = MEM_readLEST(bitD->ptr);

   383         return BIT_DStream_unfinished;

   384     }

   385     if (bitD->ptr == bitD->start) {

   386         if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;

   387         return BIT_DStream_completed;

   388     }

   389     {   U32 nbBytes = bitD->bitsConsumed >> 3;

   390         BIT_DStream_status result = BIT_DStream_unfinished;

   391         if (bitD->ptr - nbBytes < bitD->start) {

   392             nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */

   393             result = BIT_DStream_endOfBuffer;

   394         }

   395         bitD->ptr -= nbBytes;

   396         bitD->bitsConsumed -= nbBytes*8;

   397         bitD->bitContainer = MEM_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD) */

   398         return result;

   399     }

   400 }

   401 

   402 /*! BIT_endOfDStream() :

   403 *   @return Tells if DStream has exactly reached its end (all bits consumed).

   404 */

   405 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)

   406 {

   407     return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));

   408 }

   409 

   410 #if defined (__cplusplus)

   411 }

   412 #endif

   413 

   414 #endif /* BITSTREAM_H_MODULE */