bitstream.h File Reference

#include "mem.h"
#include "compiler.h"
#include "debug.h"
#include "error_private.h"

Include dependency graph for bitstream.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	BIT_CStream_t
struct	BIT_DStream_t

Macros
#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))
#define	BIT_MASK_SIZE   (sizeof(BIT_mask) / sizeof(BIT_mask[0]))

Enumerations
enum	BIT_DStream_status { BIT_DStream_unfinished = 0, BIT_DStream_endOfBuffer = 1, BIT_DStream_completed = 2, BIT_DStream_overflow = 3 }

Functions
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)
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)
MEM_STATIC void	BIT_addBitsFast (BIT_CStream_t *bitC, size_t value, unsigned nbBits)
MEM_STATIC void	BIT_flushBitsFast (BIT_CStream_t *bitC)
MEM_STATIC size_t	BIT_readBitsFast (BIT_DStream_t *bitD, unsigned nbBits)
MEM_STATIC unsigned	BIT_highbit32 (U32 val)
MEM_STATIC size_t	BIT_getUpperBits (size_t bitContainer, U32 const start)
MEM_STATIC size_t	BIT_getMiddleBits (size_t bitContainer, U32 const start, U32 const nbBits)
MEM_STATIC size_t	BIT_getLowerBits (size_t bitContainer, U32 const nbBits)
MEM_STATIC size_t	BIT_lookBits (const BIT_DStream_t *bitD, U32 nbBits)
MEM_STATIC size_t	BIT_lookBitsFast (const BIT_DStream_t *bitD, U32 nbBits)
MEM_STATIC void	BIT_skipBits (BIT_DStream_t *bitD, U32 nbBits)
MEM_STATIC BIT_DStream_status	BIT_reloadDStreamFast (BIT_DStream_t *bitD)

Variables
static const unsigned	BIT_mask []

Macro Definition Documentation

BIT_MASK_SIZE

#define BIT_MASK_SIZE   (sizeof(BIT_mask) / sizeof(BIT_mask[0]))

Definition at line 174 of file bitstream.h.

STREAM_ACCUMULATOR_MIN

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

Definition at line 47 of file bitstream.h.

STREAM_ACCUMULATOR_MIN_32

#define STREAM_ACCUMULATOR_MIN_32   25

Definition at line 45 of file bitstream.h.

STREAM_ACCUMULATOR_MIN_64

#define STREAM_ACCUMULATOR_MIN_64   57

Definition at line 46 of file bitstream.h.

Enumeration Type Documentation

BIT_DStream_status

enum BIT_DStream_status

Enumerator
BIT_DStream_unfinished
BIT_DStream_endOfBuffer
BIT_DStream_completed
BIT_DStream_overflow

Definition at line 99 of file bitstream.h.

             { BIT_DStream_unfinished = 0,
               BIT_DStream_endOfBuffer = 1,
               BIT_DStream_completed = 2,
               BIT_DStream_overflow = 3 } BIT_DStream_status;  /* result of BIT_reloadDStream() */

Function Documentation

BIT_addBits()

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

BIT_addBits() : can add up to 31 bits into bitC. Note : does not check for register overflow !

Definition at line 198 of file bitstream.h.

{
    MEM_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;
}

Referenced by ZSTD_encodeSequences_body().

BIT_addBitsFast()

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

BIT_addBitsFast() : works only if value is clean, meaning all high bits above nbBits are 0

Definition at line 211 of file bitstream.h.

{
    assert((value>>nbBits) == 0);
    assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
    bitC->bitContainer |= value << bitC->bitPos;
    bitC->bitPos += nbBits;
}

Referenced by BIT_closeCStream(), and HUF_encodeSymbol().

BIT_closeCStream()

MEM_STATIC size_t BIT_closeCStream

(

BIT_CStream_t *

bitC

)

BIT_closeCStream() :

Returns

: size of CStream, in bytes, or 0 if it could not fit into dstBuffer

Definition at line 254 of file bitstream.h.

{
    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);
}

Referenced by FSE_compress_usingCTable_generic(), HUF_compress1X_usingCTable_internal_body(), and ZSTD_encodeSequences_body().

BIT_endOfDStream()

MEM_STATIC unsigned BIT_endOfDStream

(

const BIT_DStream_t *

DStream

)

BIT_endOfDStream() :

Returns

: 1 if DStream has exactly reached its end (all bits consumed).

Definition at line 445 of file bitstream.h.

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

Referenced by HUF_decompress1X1_usingDTable_internal_body(), HUF_decompress1X2_usingDTable_internal_body(), HUF_decompress4X1_usingDTable_internal_body(), and HUF_decompress4X2_usingDTable_internal_body().

BIT_flushBits()

MEM_STATIC void BIT_flushBits

(

BIT_CStream_t *

bitC

)

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()

Definition at line 239 of file bitstream.h.

{
    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;
}

Referenced by BIT_closeCStream(), and ZSTD_encodeSequences_body().

BIT_flushBitsFast()

MEM_STATIC void BIT_flushBitsFast

(

BIT_CStream_t *

bitC

)

BIT_flushBitsFast() : assumption : bitContainer has not overflowed unsafe version; does not check buffer overflow

Definition at line 223 of file bitstream.h.

{
    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_getLowerBits()

MEM_STATIC size_t BIT_getLowerBits	(	size_t	bitContainer,
		U32 const	nbBits
	)

Definition at line 333 of file bitstream.h.

{
    assert(nbBits < BIT_MASK_SIZE);
    return bitContainer & BIT_mask[nbBits];
}

BIT_getMiddleBits()

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

Definition at line 325 of file bitstream.h.

{
    U32 const regMask = sizeof(bitContainer)*8 - 1;
    /* if start > regMask, bitstream is corrupted, and result is undefined */
    assert(nbBits < BIT_MASK_SIZE);
    return (bitContainer >> (start & regMask)) & BIT_mask[nbBits];
}

Referenced by BIT_lookBits().

BIT_getUpperBits()

MEM_STATIC size_t BIT_getUpperBits	(	size_t	bitContainer,
		U32 const	start
	)

Definition at line 320 of file bitstream.h.

{
    return bitContainer >> start;
}

BIT_highbit32()

MEM_STATIC unsigned BIT_highbit32

(

U32

val

)

Definition at line 139 of file bitstream.h.

{
    assert(val != 0);
    {
#   if defined(_MSC_VER)   /* Visual */
        unsigned long r=0;
        return _BitScanReverse ( &r, val ) ? (unsigned)r : 0;
#   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* Use GCC Intrinsic */
        return __builtin_clz (val) ^ 31;
#   elif defined(__ICCARM__)    /* IAR Intrinsic */
        return 31 - __CLZ(val);
#   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
    }
}

Referenced by BIT_initDStream(), FSE_buildCTable_wksp(), FSE_buildDTable(), FSE_minTableLog(), FSE_optimalTableLog_internal(), HUF_readStats(), HUF_setMaxHeight(), and HUF_sort().

BIT_initCStream()

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

BIT_initCStream() : dstCapacity must be > sizeof(size_t)

Returns

: 0 if success, otherwise an error code (can be tested using ERR_isError())

Definition at line 183 of file bitstream.h.

{
    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;
}

Referenced by FSE_compress_usingCTable_generic(), HUF_compress1X_usingCTable_internal_body(), and ZSTD_encodeSequences_body().

BIT_initDStream()

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

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.

Returns

: size of stream (== srcSize), or an errorCode if a problem is detected

Definition at line 272 of file bitstream.h.

{
    if (srcSize < 1) { 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);
                /* fall-through */

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

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

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

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

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

        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;
}

Referenced by FSE_decompress_usingDTable_generic(), HUF_decompress1X1_usingDTable_internal_body(), HUF_decompress1X2_usingDTable_internal_body(), HUF_decompress4X1_usingDTable_internal_body(), and HUF_decompress4X2_usingDTable_internal_body().

BIT_lookBits()

MEM_STATIC size_t BIT_lookBits	(	const BIT_DStream_t *	bitD,
		U32	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.

Returns

: value extracted

Definition at line 345 of file bitstream.h.

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

Referenced by BIT_readBits().

BIT_lookBitsFast()

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

BIT_lookBitsFast() : unsafe version; only works if nbBits >= 1

Definition at line 361 of file bitstream.h.

{
    U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
    assert(nbBits >= 1);
    return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask);
}

Referenced by BIT_readBitsFast(), HUF_decodeLastSymbolX2(), HUF_decodeSymbolX1(), and HUF_decodeSymbolX2().

BIT_readBits()

MEM_STATIC size_t BIT_readBits	(	BIT_DStream_t *	bitD,
		unsigned	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.

Returns

: extracted value.

Definition at line 377 of file bitstream.h.

{
    size_t const value = BIT_lookBits(bitD, nbBits);
    BIT_skipBits(bitD, nbBits);
    return value;
}

BIT_readBitsFast()

MEM_STATIC size_t BIT_readBitsFast	(	BIT_DStream_t *	bitD,
		unsigned	nbBits
	)

BIT_readBitsFast() : unsafe version; only works only if nbBits >= 1

Definition at line 386 of file bitstream.h.

{
    size_t const value = BIT_lookBitsFast(bitD, nbBits);
    assert(nbBits >= 1);
    BIT_skipBits(bitD, nbBits);
    return value;
}

BIT_reloadDStream()

MEM_STATIC BIT_DStream_status BIT_reloadDStream

(

BIT_DStream_t *

bitD

)

BIT_reloadDStream() : Refill bitD from buffer previously set in BIT_initDStream() . This function is safe, it guarantees it will not read beyond src buffer.

Returns

: status of BIT_DStream_t internal register. when status == BIT_DStream_unfinished, internal register is filled with at least 25 or 57 bits

Definition at line 416 of file bitstream.h.

{
    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;
    }
}

Referenced by FSE_decompress_usingDTable_generic(), HUF_decodeStreamX1(), and HUF_decodeStreamX2().

BIT_reloadDStreamFast()

MEM_STATIC BIT_DStream_status BIT_reloadDStreamFast

(

BIT_DStream_t *

bitD

)

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.

Definition at line 400 of file bitstream.h.

{
    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;
}

Referenced by BIT_reloadDStream(), HUF_decompress4X1_usingDTable_internal_body(), and HUF_decompress4X2_usingDTable_internal_body().

BIT_skipBits()

MEM_STATIC void BIT_skipBits	(	BIT_DStream_t *	bitD,
		U32	nbBits
	)

Definition at line 368 of file bitstream.h.

{
    bitD->bitsConsumed += nbBits;
}

Referenced by BIT_readBits(), BIT_readBitsFast(), HUF_decodeLastSymbolX2(), HUF_decodeSymbolX1(), and HUF_decodeSymbolX2().

Variable Documentation

BIT_mask

const unsigned BIT_mask[]

static

Initial value:

= {
    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}

Definition at line 167 of file bitstream.h.

Referenced by BIT_addBits(), BIT_getLowerBits(), and BIT_getMiddleBits().