FreeBSD/Linux Kernel Cross Reference
sys/contrib/zstd/lib/common/bitstream.h

     /* ******************************************************************
      * 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
    
    #if defined (__cplusplus)
    extern "C" {
    #endif
    /*
    *  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
    =========================================*/
    #ifndef ZSTD_NO_INTRINSICS
    #  if defined(__BMI__) && defined(__GNUC__)
    #    include <immintrin.h>   /* support for bextr (experimental) */
    #  elif defined(__ICCARM__)
    #    include <intrinsics.h>
    #  endif
    #endif
    
    #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 defined(_MSC_VER)   /* Visual */
   #       if STATIC_BMI2 == 1
               return _lzcnt_u32(val) ^ 31;
   #       else
               if (val != 0) {
                   unsigned long r;
                   _BitScanReverse(&r, val);
                   return (unsigned)r;
               } else {
                   /* Should not reach this code path */
                   __assume(0);
               }
   #       endif
   #   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
       }
   }
   
   /*=====    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)
   {
   #if defined(STATIC_BMI2) && STATIC_BMI2 == 1
           return  _bzhi_u64(bitContainer, nbBits);
   #else
       assert(nbBits < BIT_MASK_SIZE);
       return bitContainer & BIT_mask[nbBits];
   #endif
   }
   
   /*! 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));
   }
   
   #if defined (__cplusplus)
   }
   #endif
   
   #endif /* BITSTREAM_H_MODULE */

Cache object: 8df0ee7ecec64ac52b0aa3e23f9ec586