lib/zstd/common/bitstream.h - linux - Git at Google

 /* ******************************************************************
  * bitstream
  * Part of FSE library
  * Copyright (c) Yann Collet, Facebook, Inc.
  *
  * You can contact the author at :
  * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
  *
  * This source code is licensed under both the BSD-style license (found in the
  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
  * in the COPYING file in the root directory of this source tree).
  * You may select, at your option, one of the above-listed licenses.
 ****************************************************************** */
 #ifndef BITSTREAM_H_MODULE
 #define BITSTREAM_H_MODULE

 /*
 *  This API consists of small unitary functions, which must be inlined for best performance.
 *  Since link-time-optimization is not available for all compilers,
 *  these functions are defined into a .h to be included.
 */

 /*-****************************************
 *  Dependencies
 ******************************************/
 #include "mem.h"            /* unaligned access routines */
 #include "compiler.h"       /* UNLIKELY() */
 #include "debug.h"          /* assert(), DEBUGLOG(), RAWLOG() */
 #include "error_private.h"  /* error codes and messages */


 /*=========================================
 *  Target specific
 =========================================*/

 #define STREAM_ACCUMULATOR_MIN_32  25
 #define STREAM_ACCUMULATOR_MIN_64  57
 #define STREAM_ACCUMULATOR_MIN    ((U32)(MEM_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))


 /*-******************************************
 *  bitStream encoding API (write forward)
 ********************************************/
 /* bitStream can mix input from multiple sources.
  * A critical property of these streams is that they encode and decode in **reverse** direction.
  * So the first bit sequence you add will be the last to be read, like a LIFO stack.
  */
 typedef struct {
     size_t bitContainer;
     unsigned bitPos;
     char*  startPtr;
     char*  ptr;
     char*  endPtr;
 } BIT_CStream_t;

 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
 MEM_STATIC void   BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
 MEM_STATIC void   BIT_flushBits(BIT_CStream_t* bitC);
 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC);

 /* Start with initCStream, providing the size of buffer to write into.
 *  bitStream will never write outside of this buffer.
 *  `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
 *
 *  bits are first added to a local register.
 *  Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
 *  Writing data into memory is an explicit operation, performed by the flushBits function.
 *  Hence keep track how many bits are potentially stored into local register to avoid register overflow.
 *  After a flushBits, a maximum of 7 bits might still be stored into local register.
 *
 *  Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
 *
 *  Last operation is to close the bitStream.
 *  The function returns the final size of CStream in bytes.
 *  If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
 */


 /*-********************************************
 *  bitStream decoding API (read backward)
 **********************************************/
 typedef struct {
     size_t   bitContainer;
     unsigned bitsConsumed;
     const char* ptr;
     const char* start;
     const char* limitPtr;
 } BIT_DStream_t;

 typedef enum { BIT_DStream_unfinished = 0,
                BIT_DStream_endOfBuffer = 1,
                BIT_DStream_completed = 2,
                BIT_DStream_overflow = 3 } BIT_DStream_status;  /* result of BIT_reloadDStream() */
                /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */

 MEM_STATIC size_t   BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
 MEM_STATIC size_t   BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);


 /* Start by invoking BIT_initDStream().
 *  A chunk of the bitStream is then stored into a local register.
 *  Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
 *  You can then retrieve bitFields stored into the local register, **in reverse order**.
 *  Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
 *  A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
 *  Otherwise, it can be less than that, so proceed accordingly.
 *  Checking if DStream has reached its end can be performed with BIT_endOfDStream().
 */


 /*-****************************************
 *  unsafe API
 ******************************************/
 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
 /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */

 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);
 /* unsafe version; does not check buffer overflow */

 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
 /* faster, but works only if nbBits >= 1 */


 /*-**************************************************************
 *  Internal functions
 ****************************************************************/
 MEM_STATIC unsigned BIT_highbit32 (U32 val)
 {
     assert(val != 0);
     {
 #   if (__GNUC__ >= 3)   /* Use GCC Intrinsic */
         return __builtin_clz (val) ^ 31;
 #   else   /* Software version */
         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 };
         U32 v = val;
         v |= v >> 1;
         v |= v >> 2;
         v |= v >> 4;
         v |= v >> 8;
         v |= v >> 16;
         return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
 #   endif
     }
 }

 /*=====    Local Constants   =====*/
 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, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF,
     0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits */
 #define BIT_MASK_SIZE (sizeof(BIT_mask) / sizeof(BIT_mask[0]))

 /*-**************************************************************
 *  bitStream encoding
 ****************************************************************/
 /*! BIT_initCStream() :
  *  `dstCapacity` must be > sizeof(size_t)
  *  @return : 0 if success,
  *            otherwise an error code (can be tested using ERR_isError()) */
 MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC,
                                   void* startPtr, size_t dstCapacity)
 {
     bitC->bitContainer = 0;
     bitC->bitPos = 0;
     bitC->startPtr = (char*)startPtr;
     bitC->ptr = bitC->startPtr;
     bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->bitContainer);
     if (dstCapacity <= sizeof(bitC->bitContainer)) return ERROR(dstSize_tooSmall);
     return 0;
 }

 /*! BIT_addBits() :
  *  can add up to 31 bits into `bitC`.
  *  Note : does not check for register overflow ! */
 MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC,
                             size_t value, unsigned nbBits)
 {
     DEBUG_STATIC_ASSERT(BIT_MASK_SIZE == 32);
     assert(nbBits < BIT_MASK_SIZE);
     assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
     bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
     bitC->bitPos += nbBits;
 }

 /*! BIT_addBitsFast() :
  *  works only if `value` is _clean_,
  *  meaning all high bits above nbBits are 0 */
 MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC,
                                 size_t value, unsigned nbBits)
 {
     assert((value>>nbBits) == 0);
     assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
     bitC->bitContainer |= value << bitC->bitPos;
     bitC->bitPos += nbBits;
 }

 /*! BIT_flushBitsFast() :
  *  assumption : bitContainer has not overflowed
  *  unsafe version; does not check buffer overflow */
 MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)
 {
     size_t const nbBytes = bitC->bitPos >> 3;
     assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
     assert(bitC->ptr <= bitC->endPtr);
     MEM_writeLEST(bitC->ptr, bitC->bitContainer);
     bitC->ptr += nbBytes;
     bitC->bitPos &= 7;
     bitC->bitContainer >>= nbBytes*8;
 }

 /*! BIT_flushBits() :
  *  assumption : bitContainer has not overflowed
  *  safe version; check for buffer overflow, and prevents it.
  *  note : does not signal buffer overflow.
  *  overflow will be revealed later on using BIT_closeCStream() */
 MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)
 {
     size_t const nbBytes = bitC->bitPos >> 3;
     assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
     assert(bitC->ptr <= bitC->endPtr);
     MEM_writeLEST(bitC->ptr, bitC->bitContainer);
     bitC->ptr += nbBytes;
     if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
     bitC->bitPos &= 7;
     bitC->bitContainer >>= nbBytes*8;
 }

 /*! BIT_closeCStream() :
  *  @return : size of CStream, in bytes,
  *            or 0 if it could not fit into dstBuffer */
 MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)
 {
     BIT_addBitsFast(bitC, 1, 1);   /* endMark */
     BIT_flushBits(bitC);
     if (bitC->ptr >= bitC->endPtr) return 0; /* overflow detected */
     return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
 }


 /*-********************************************************
 *  bitStream decoding
 **********************************************************/
 /*! BIT_initDStream() :
  *  Initialize a BIT_DStream_t.
  * `bitD` : a pointer to an already allocated BIT_DStream_t structure.
  * `srcSize` must be the *exact* size of the bitStream, in bytes.
  * @return : size of stream (== srcSize), or an errorCode if a problem is detected
  */
 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
 {
     if (srcSize < 1) { ZSTD_memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }

     bitD->start = (const char*)srcBuffer;
     bitD->limitPtr = bitD->start + sizeof(bitD->bitContainer);

     if (srcSize >=  sizeof(bitD->bitContainer)) {  /* normal case */
         bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
         bitD->bitContainer = MEM_readLEST(bitD->ptr);
         { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
           bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;  /* ensures bitsConsumed is always set */
           if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
     } else {
         bitD->ptr   = bitD->start;
         bitD->bitContainer = *(const BYTE*)(bitD->start);
         switch(srcSize)
         {
         case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
                 ZSTD_FALLTHROUGH;

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

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

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

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

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

         default: break;
         }
         {   BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
             bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
             if (lastByte == 0) return ERROR(corruption_detected);  /* endMark not present */
         }
         bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
     }

     return srcSize;
 }

 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
 {
     return bitContainer >> start;
 }

 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
 {
     U32 const regMask = sizeof(bitContainer)*8 - 1;
     /* if start > regMask, bitstream is corrupted, and result is undefined */
     assert(nbBits < BIT_MASK_SIZE);
     /* x86 transform & ((1 << nbBits) - 1) to bzhi instruction, it is better
      * than accessing memory. When bmi2 instruction is not present, we consider
      * such cpus old (pre-Haswell, 2013) and their performance is not of that
      * importance.
      */
 #if defined(__x86_64__) || defined(_M_X86)
     return (bitContainer >> (start & regMask)) & ((((U64)1) << nbBits) - 1);
 #else
     return (bitContainer >> (start & regMask)) & BIT_mask[nbBits];
 #endif
 }

 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
 {
     assert(nbBits < BIT_MASK_SIZE);
     return bitContainer & BIT_mask[nbBits];
 }

 /*! BIT_lookBits() :
  *  Provides next n bits from local register.
  *  local register is not modified.
  *  On 32-bits, maxNbBits==24.
  *  On 64-bits, maxNbBits==56.
  * @return : value extracted */
 MEM_STATIC  FORCE_INLINE_ATTR size_t BIT_lookBits(const BIT_DStream_t*  bitD, U32 nbBits)
 {
     /* arbitrate between double-shift and shift+mask */
 #if 1
     /* if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8,
      * bitstream is likely corrupted, and result is undefined */
     return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);
 #else
     /* this code path is slower on my os-x laptop */
     U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
     return ((bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> 1) >> ((regMask-nbBits) & regMask);
 #endif
 }

 /*! BIT_lookBitsFast() :
  *  unsafe version; only works if nbBits >= 1 */
 MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
 {
     U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
     assert(nbBits >= 1);
     return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask);
 }

 MEM_STATIC FORCE_INLINE_ATTR void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
 {
     bitD->bitsConsumed += nbBits;
 }

 /*! BIT_readBits() :
  *  Read (consume) next n bits from local register and update.
  *  Pay attention to not read more than nbBits contained into local register.
  * @return : extracted value. */
 MEM_STATIC FORCE_INLINE_ATTR size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits)
 {
     size_t const value = BIT_lookBits(bitD, nbBits);
     BIT_skipBits(bitD, nbBits);
     return value;
 }

 /*! BIT_readBitsFast() :
  *  unsafe version; only works only if nbBits >= 1 */
 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits)
 {
     size_t const value = BIT_lookBitsFast(bitD, nbBits);
     assert(nbBits >= 1);
     BIT_skipBits(bitD, nbBits);
     return value;
 }

 /*! BIT_reloadDStreamFast() :
  *  Similar to BIT_reloadDStream(), but with two differences:
  *  1. bitsConsumed <= sizeof(bitD->bitContainer)*8 must hold!
  *  2. Returns BIT_DStream_overflow when bitD->ptr < bitD->limitPtr, at this
  *     point you must use BIT_reloadDStream() to reload.
  */
 MEM_STATIC BIT_DStream_status BIT_reloadDStreamFast(BIT_DStream_t* bitD)
 {
     if (UNLIKELY(bitD->ptr < bitD->limitPtr))
         return BIT_DStream_overflow;
     assert(bitD->bitsConsumed <= sizeof(bitD->bitContainer)*8);
     bitD->ptr -= bitD->bitsConsumed >> 3;
     bitD->bitsConsumed &= 7;
     bitD->bitContainer = MEM_readLEST(bitD->ptr);
     return BIT_DStream_unfinished;
 }

 /*! BIT_reloadDStream() :
  *  Refill `bitD` from buffer previously set in BIT_initDStream() .
  *  This function is safe, it guarantees it will not read beyond src buffer.
  * @return : status of `BIT_DStream_t` internal register.
  *           when status == BIT_DStream_unfinished, internal register is filled with at least 25 or 57 bits */
 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
 {
     if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* overflow detected, like end of stream */
         return BIT_DStream_overflow;

     if (bitD->ptr >= bitD->limitPtr) {
         return BIT_reloadDStreamFast(bitD);
     }
     if (bitD->ptr == bitD->start) {
         if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
         return BIT_DStream_completed;
     }
     /* start < ptr < limitPtr */
     {   U32 nbBytes = bitD->bitsConsumed >> 3;
         BIT_DStream_status result = BIT_DStream_unfinished;
         if (bitD->ptr - nbBytes < bitD->start) {
             nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */
             result = BIT_DStream_endOfBuffer;
         }
         bitD->ptr -= nbBytes;
         bitD->bitsConsumed -= nbBytes*8;
         bitD->bitContainer = MEM_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD->bitContainer), otherwise bitD->ptr == bitD->start */
         return result;
     }
 }

 /*! BIT_endOfDStream() :
  * @return : 1 if DStream has _exactly_ reached its end (all bits consumed).
  */
 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
 {
     return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
 }


 #endif /* BITSTREAM_H_MODULE */
	/* ******************************************************************
	* bitstream
	* Part of FSE library
	* Copyright (c) Yann Collet, Facebook, Inc.
	*
	* You can contact the author at :
	* - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
	*
	* This source code is licensed under both the BSD-style license (found in the
	* LICENSE file in the root directory of this source tree) and the GPLv2 (found
	* in the COPYING file in the root directory of this source tree).
	* You may select, at your option, one of the above-listed licenses.
	****************************************************************** */
	#ifndef BITSTREAM_H_MODULE
	#define BITSTREAM_H_MODULE

	/*
	* This API consists of small unitary functions, which must be inlined for best performance.
	* Since link-time-optimization is not available for all compilers,
	* these functions are defined into a .h to be included.
	*/

	/-***************************************
	* Dependencies
	******************************************/
	#include "mem.h" /* unaligned access routines */
	#include "compiler.h" /* UNLIKELY() */
	#include "debug.h" /* assert(), DEBUGLOG(), RAWLOG() */
	#include "error_private.h" /* error codes and messages */


	/*=========================================
	* Target specific
	=========================================*/

	#define STREAM_ACCUMULATOR_MIN_32 25
	#define STREAM_ACCUMULATOR_MIN_64 57
	#define STREAM_ACCUMULATOR_MIN ((U32)(MEM_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))


	/-*****************************************
	* bitStream encoding API (write forward)
	********************************************/
	/* bitStream can mix input from multiple sources.
	* A critical property of these streams is that they encode and decode in reverse direction.
	* So the first bit sequence you add will be the last to be read, like a LIFO stack.
	*/
	typedef struct {
	size_t bitContainer;
	unsigned bitPos;
	char* startPtr;
	char* ptr;
	char* endPtr;
	} BIT_CStream_t;

	MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
	MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
	MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC);
	MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC);

	/* Start with initCStream, providing the size of buffer to write into.
	* bitStream will never write outside of this buffer.
	* `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
	*
	* bits are first added to a local register.
	* Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
	* Writing data into memory is an explicit operation, performed by the flushBits function.
	* Hence keep track how many bits are potentially stored into local register to avoid register overflow.
	* After a flushBits, a maximum of 7 bits might still be stored into local register.
	*
	* Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
	*
	* Last operation is to close the bitStream.
	* The function returns the final size of CStream in bytes.
	* If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
	*/


	/-*******************************************
	* bitStream decoding API (read backward)
	**********************************************/
	typedef struct {
	size_t bitContainer;
	unsigned bitsConsumed;
	const char* ptr;
	const char* start;
	const char* limitPtr;
	} BIT_DStream_t;

	typedef enum { BIT_DStream_unfinished = 0,
	BIT_DStream_endOfBuffer = 1,
	BIT_DStream_completed = 2,
	BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
	/* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */

	MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
	MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
	MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
	MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);


	/* Start by invoking BIT_initDStream().
	* A chunk of the bitStream is then stored into a local register.
	* Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
	* You can then retrieve bitFields stored into the local register, in reverse order.
	* Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
	* A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
	* Otherwise, it can be less than that, so proceed accordingly.
	* Checking if DStream has reached its end can be performed with BIT_endOfDStream().
	*/


	/-***************************************
	* unsafe API
	******************************************/
	MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
	/* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */

	MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);
	/* unsafe version; does not check buffer overflow */

	MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
	/* faster, but works only if nbBits >= 1 */



	/-*************************************************************
	* Internal functions
	****************************************************************/
	MEM_STATIC unsigned BIT_highbit32 (U32 val)
	{
	assert(val != 0);
	{
	# if (__GNUC__ >= 3) /* Use GCC Intrinsic */
	return __builtin_clz (val) ^ 31;
	# else /* Software version */
	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 };
	U32 v = val;
	v \|= v >> 1;
	v \|= v >> 2;
	v \|= v >> 4;
	v \|= v >> 8;
	v \|= v >> 16;
	return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
	# endif
	}
	}

	/===== Local Constants =====/
	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, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF,
	0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits */
	#define BIT_MASK_SIZE (sizeof(BIT_mask) / sizeof(BIT_mask[0]))

	/-*************************************************************
	* bitStream encoding
	****************************************************************/
	/*! BIT_initCStream() :
	* `dstCapacity` must be > sizeof(size_t)
	* @return : 0 if success,
	* otherwise an error code (can be tested using ERR_isError()) */
	MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC,
	void* startPtr, size_t dstCapacity)
	{
	bitC->bitContainer = 0;
	bitC->bitPos = 0;
	bitC->startPtr = (char*)startPtr;
	bitC->ptr = bitC->startPtr;
	bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->bitContainer);
	if (dstCapacity <= sizeof(bitC->bitContainer)) return ERROR(dstSize_tooSmall);
	return 0;
	}

	/*! BIT_addBits() :
	* can add up to 31 bits into `bitC`.
	* Note : does not check for register overflow ! */
	MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC,
	size_t value, unsigned nbBits)
	{
	DEBUG_STATIC_ASSERT(BIT_MASK_SIZE == 32);
	assert(nbBits < BIT_MASK_SIZE);
	assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
	bitC->bitContainer \|= (value & BIT_mask[nbBits]) << bitC->bitPos;
	bitC->bitPos += nbBits;
	}

	/*! BIT_addBitsFast() :
	* works only if `value` is _clean_,
	* meaning all high bits above nbBits are 0 */
	MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC,
	size_t value, unsigned nbBits)
	{
	assert((value>>nbBits) == 0);
	assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
	bitC->bitContainer \|= value << bitC->bitPos;
	bitC->bitPos += nbBits;
	}

	/*! BIT_flushBitsFast() :
	* assumption : bitContainer has not overflowed
	* unsafe version; does not check buffer overflow */
	MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)
	{
	size_t const nbBytes = bitC->bitPos >> 3;
	assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
	assert(bitC->ptr <= bitC->endPtr);
	MEM_writeLEST(bitC->ptr, bitC->bitContainer);
	bitC->ptr += nbBytes;
	bitC->bitPos &= 7;
	bitC->bitContainer >>= nbBytes*8;
	}

	/*! BIT_flushBits() :
	* assumption : bitContainer has not overflowed
	* safe version; check for buffer overflow, and prevents it.
	* note : does not signal buffer overflow.
	* overflow will be revealed later on using BIT_closeCStream() */
	MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)
	{
	size_t const nbBytes = bitC->bitPos >> 3;
	assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
	assert(bitC->ptr <= bitC->endPtr);
	MEM_writeLEST(bitC->ptr, bitC->bitContainer);
	bitC->ptr += nbBytes;
	if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
	bitC->bitPos &= 7;
	bitC->bitContainer >>= nbBytes*8;
	}

	/*! BIT_closeCStream() :
	* @return : size of CStream, in bytes,
	* or 0 if it could not fit into dstBuffer */
	MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)
	{
	BIT_addBitsFast(bitC, 1, 1); /* endMark */
	BIT_flushBits(bitC);
	if (bitC->ptr >= bitC->endPtr) return 0; /* overflow detected */
	return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
	}


	/-*******************************************************
	* bitStream decoding
	**********************************************************/
	/*! BIT_initDStream() :
	* Initialize a BIT_DStream_t.
	* `bitD` : a pointer to an already allocated BIT_DStream_t structure.
	* `srcSize` must be the exact size of the bitStream, in bytes.
	* @return : size of stream (== srcSize), or an errorCode if a problem is detected
	*/
	MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
	{
	if (srcSize < 1) { ZSTD_memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }

	bitD->start = (const char*)srcBuffer;
	bitD->limitPtr = bitD->start + sizeof(bitD->bitContainer);

	if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
	bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
	bitD->bitContainer = MEM_readLEST(bitD->ptr);
	{ BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
	bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */
	if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
	} else {
	bitD->ptr = bitD->start;
	bitD->bitContainer = (const BYTE)(bitD->start);
	switch(srcSize)
	{
	case 7: bitD->bitContainer += (size_t)(((const BYTE)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)8 - 16);
	ZSTD_FALLTHROUGH;

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

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

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

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

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

	default: break;
	}
	{ BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
	bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
	if (lastByte == 0) return ERROR(corruption_detected); /* endMark not present */
	}
	bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
	}

	return srcSize;
	}

	MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
	{
	return bitContainer >> start;
	}

	MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
	{
	U32 const regMask = sizeof(bitContainer)*8 - 1;
	/* if start > regMask, bitstream is corrupted, and result is undefined */
	assert(nbBits < BIT_MASK_SIZE);
	/* x86 transform & ((1 << nbBits) - 1) to bzhi instruction, it is better
	* than accessing memory. When bmi2 instruction is not present, we consider
	* such cpus old (pre-Haswell, 2013) and their performance is not of that
	* importance.
	*/
	#if defined(__x86_64__) \|\| defined(_M_X86)
	return (bitContainer >> (start & regMask)) & ((((U64)1) << nbBits) - 1);
	#else
	return (bitContainer >> (start & regMask)) & BIT_mask[nbBits];
	#endif
	}

	MEM_STATIC FORCE_INLINE_ATTR size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
	{
	assert(nbBits < BIT_MASK_SIZE);
	return bitContainer & BIT_mask[nbBits];
	}

	/*! BIT_lookBits() :
	* Provides next n bits from local register.
	* local register is not modified.
	* On 32-bits, maxNbBits==24.
	* On 64-bits, maxNbBits==56.
	* @return : value extracted */
	MEM_STATIC FORCE_INLINE_ATTR size_t BIT_lookBits(const BIT_DStream_t* bitD, U32 nbBits)
	{
	/* arbitrate between double-shift and shift+mask */
	#if 1
	/* if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8,
	* bitstream is likely corrupted, and result is undefined */
	return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);
	#else
	/* this code path is slower on my os-x laptop */
	U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
	return ((bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> 1) >> ((regMask-nbBits) & regMask);
	#endif
	}

	/*! BIT_lookBitsFast() :
	* unsafe version; only works if nbBits >= 1 */
	MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
	{
	U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
	assert(nbBits >= 1);
	return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask);
	}

	MEM_STATIC FORCE_INLINE_ATTR void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
	{
	bitD->bitsConsumed += nbBits;
	}

	/*! BIT_readBits() :
	* Read (consume) next n bits from local register and update.
	* Pay attention to not read more than nbBits contained into local register.
	* @return : extracted value. */
	MEM_STATIC FORCE_INLINE_ATTR size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits)
	{
	size_t const value = BIT_lookBits(bitD, nbBits);
	BIT_skipBits(bitD, nbBits);
	return value;
	}

	/*! BIT_readBitsFast() :
	* unsafe version; only works only if nbBits >= 1 */
	MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits)
	{
	size_t const value = BIT_lookBitsFast(bitD, nbBits);
	assert(nbBits >= 1);
	BIT_skipBits(bitD, nbBits);
	return value;
	}

	/*! BIT_reloadDStreamFast() :
	* Similar to BIT_reloadDStream(), but with two differences:
	* 1. bitsConsumed <= sizeof(bitD->bitContainer)*8 must hold!
	* 2. Returns BIT_DStream_overflow when bitD->ptr < bitD->limitPtr, at this
	* point you must use BIT_reloadDStream() to reload.
	*/
	MEM_STATIC BIT_DStream_status BIT_reloadDStreamFast(BIT_DStream_t* bitD)
	{
	if (UNLIKELY(bitD->ptr < bitD->limitPtr))
	return BIT_DStream_overflow;
	assert(bitD->bitsConsumed <= sizeof(bitD->bitContainer)*8);
	bitD->ptr -= bitD->bitsConsumed >> 3;
	bitD->bitsConsumed &= 7;
	bitD->bitContainer = MEM_readLEST(bitD->ptr);
	return BIT_DStream_unfinished;
	}

	/*! BIT_reloadDStream() :
	* Refill `bitD` from buffer previously set in BIT_initDStream() .
	* This function is safe, it guarantees it will not read beyond src buffer.
	* @return : status of `BIT_DStream_t` internal register.
	* when status == BIT_DStream_unfinished, internal register is filled with at least 25 or 57 bits */
	MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
	{
	if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)8)) / overflow detected, like end of stream */
	return BIT_DStream_overflow;

	if (bitD->ptr >= bitD->limitPtr) {
	return BIT_reloadDStreamFast(bitD);
	}
	if (bitD->ptr == bitD->start) {
	if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
	return BIT_DStream_completed;
	}
	/* start < ptr < limitPtr */
	{ U32 nbBytes = bitD->bitsConsumed >> 3;
	BIT_DStream_status result = BIT_DStream_unfinished;
	if (bitD->ptr - nbBytes < bitD->start) {
	nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
	result = BIT_DStream_endOfBuffer;
	}
	bitD->ptr -= nbBytes;
	bitD->bitsConsumed -= nbBytes*8;
	bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD->bitContainer), otherwise bitD->ptr == bitD->start */
	return result;
	}
	}

	/*! BIT_endOfDStream() :
	* @return : 1 if DStream has _exactly_ reached its end (all bits consumed).
	*/
	MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
	{
	return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
	}


	#endif /* BITSTREAM_H_MODULE */