1*a28cd43dSSascha Wildner /* ****************************************************************** 2*a28cd43dSSascha Wildner * huff0 huffman codec, 3*a28cd43dSSascha Wildner * part of Finite State Entropy library 4*a28cd43dSSascha Wildner * Copyright (c) 2013-2020, Yann Collet, Facebook, Inc. 5*a28cd43dSSascha Wildner * 6*a28cd43dSSascha Wildner * You can contact the author at : 7*a28cd43dSSascha Wildner * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 8*a28cd43dSSascha Wildner * 9*a28cd43dSSascha Wildner * This source code is licensed under both the BSD-style license (found in the 10*a28cd43dSSascha Wildner * LICENSE file in the root directory of this source tree) and the GPLv2 (found 11*a28cd43dSSascha Wildner * in the COPYING file in the root directory of this source tree). 12*a28cd43dSSascha Wildner * You may select, at your option, one of the above-listed licenses. 13*a28cd43dSSascha Wildner ****************************************************************** */ 14*a28cd43dSSascha Wildner 15*a28cd43dSSascha Wildner #if defined (__cplusplus) 16*a28cd43dSSascha Wildner extern "C" { 17*a28cd43dSSascha Wildner #endif 18*a28cd43dSSascha Wildner 19*a28cd43dSSascha Wildner #ifndef HUF_H_298734234 20*a28cd43dSSascha Wildner #define HUF_H_298734234 21*a28cd43dSSascha Wildner 22*a28cd43dSSascha Wildner /* *** Dependencies *** */ 23*a28cd43dSSascha Wildner #include "zstd_deps.h" /* size_t */ 24*a28cd43dSSascha Wildner 25*a28cd43dSSascha Wildner 26*a28cd43dSSascha Wildner /* *** library symbols visibility *** */ 27*a28cd43dSSascha Wildner /* Note : when linking with -fvisibility=hidden on gcc, or by default on Visual, 28*a28cd43dSSascha Wildner * HUF symbols remain "private" (internal symbols for library only). 29*a28cd43dSSascha Wildner * Set macro FSE_DLL_EXPORT to 1 if you want HUF symbols visible on DLL interface */ 30*a28cd43dSSascha Wildner #if defined(FSE_DLL_EXPORT) && (FSE_DLL_EXPORT==1) && defined(__GNUC__) && (__GNUC__ >= 4) 31*a28cd43dSSascha Wildner # define HUF_PUBLIC_API __attribute__ ((visibility ("default"))) 32*a28cd43dSSascha Wildner #elif defined(FSE_DLL_EXPORT) && (FSE_DLL_EXPORT==1) /* Visual expected */ 33*a28cd43dSSascha Wildner # define HUF_PUBLIC_API __declspec(dllexport) 34*a28cd43dSSascha Wildner #elif defined(FSE_DLL_IMPORT) && (FSE_DLL_IMPORT==1) 35*a28cd43dSSascha Wildner # define HUF_PUBLIC_API __declspec(dllimport) /* not required, just to generate faster code (saves a function pointer load from IAT and an indirect jump) */ 36*a28cd43dSSascha Wildner #else 37*a28cd43dSSascha Wildner # define HUF_PUBLIC_API 38*a28cd43dSSascha Wildner #endif 39*a28cd43dSSascha Wildner 40*a28cd43dSSascha Wildner 41*a28cd43dSSascha Wildner /* ========================== */ 42*a28cd43dSSascha Wildner /* *** simple functions *** */ 43*a28cd43dSSascha Wildner /* ========================== */ 44*a28cd43dSSascha Wildner 45*a28cd43dSSascha Wildner /** HUF_compress() : 46*a28cd43dSSascha Wildner * Compress content from buffer 'src', of size 'srcSize', into buffer 'dst'. 47*a28cd43dSSascha Wildner * 'dst' buffer must be already allocated. 48*a28cd43dSSascha Wildner * Compression runs faster if `dstCapacity` >= HUF_compressBound(srcSize). 49*a28cd43dSSascha Wildner * `srcSize` must be <= `HUF_BLOCKSIZE_MAX` == 128 KB. 50*a28cd43dSSascha Wildner * @return : size of compressed data (<= `dstCapacity`). 51*a28cd43dSSascha Wildner * Special values : if return == 0, srcData is not compressible => Nothing is stored within dst !!! 52*a28cd43dSSascha Wildner * if HUF_isError(return), compression failed (more details using HUF_getErrorName()) 53*a28cd43dSSascha Wildner */ 54*a28cd43dSSascha Wildner HUF_PUBLIC_API size_t HUF_compress(void* dst, size_t dstCapacity, 55*a28cd43dSSascha Wildner const void* src, size_t srcSize); 56*a28cd43dSSascha Wildner 57*a28cd43dSSascha Wildner /** HUF_decompress() : 58*a28cd43dSSascha Wildner * Decompress HUF data from buffer 'cSrc', of size 'cSrcSize', 59*a28cd43dSSascha Wildner * into already allocated buffer 'dst', of minimum size 'dstSize'. 60*a28cd43dSSascha Wildner * `originalSize` : **must** be the ***exact*** size of original (uncompressed) data. 61*a28cd43dSSascha Wildner * Note : in contrast with FSE, HUF_decompress can regenerate 62*a28cd43dSSascha Wildner * RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, 63*a28cd43dSSascha Wildner * because it knows size to regenerate (originalSize). 64*a28cd43dSSascha Wildner * @return : size of regenerated data (== originalSize), 65*a28cd43dSSascha Wildner * or an error code, which can be tested using HUF_isError() 66*a28cd43dSSascha Wildner */ 67*a28cd43dSSascha Wildner HUF_PUBLIC_API size_t HUF_decompress(void* dst, size_t originalSize, 68*a28cd43dSSascha Wildner const void* cSrc, size_t cSrcSize); 69*a28cd43dSSascha Wildner 70*a28cd43dSSascha Wildner 71*a28cd43dSSascha Wildner /* *** Tool functions *** */ 72*a28cd43dSSascha Wildner #define HUF_BLOCKSIZE_MAX (128 * 1024) /**< maximum input size for a single block compressed with HUF_compress */ 73*a28cd43dSSascha Wildner HUF_PUBLIC_API size_t HUF_compressBound(size_t size); /**< maximum compressed size (worst case) */ 74*a28cd43dSSascha Wildner 75*a28cd43dSSascha Wildner /* Error Management */ 76*a28cd43dSSascha Wildner HUF_PUBLIC_API unsigned HUF_isError(size_t code); /**< tells if a return value is an error code */ 77*a28cd43dSSascha Wildner HUF_PUBLIC_API const char* HUF_getErrorName(size_t code); /**< provides error code string (useful for debugging) */ 78*a28cd43dSSascha Wildner 79*a28cd43dSSascha Wildner 80*a28cd43dSSascha Wildner /* *** Advanced function *** */ 81*a28cd43dSSascha Wildner 82*a28cd43dSSascha Wildner /** HUF_compress2() : 83*a28cd43dSSascha Wildner * Same as HUF_compress(), but offers control over `maxSymbolValue` and `tableLog`. 84*a28cd43dSSascha Wildner * `maxSymbolValue` must be <= HUF_SYMBOLVALUE_MAX . 85*a28cd43dSSascha Wildner * `tableLog` must be `<= HUF_TABLELOG_MAX` . */ 86*a28cd43dSSascha Wildner HUF_PUBLIC_API size_t HUF_compress2 (void* dst, size_t dstCapacity, 87*a28cd43dSSascha Wildner const void* src, size_t srcSize, 88*a28cd43dSSascha Wildner unsigned maxSymbolValue, unsigned tableLog); 89*a28cd43dSSascha Wildner 90*a28cd43dSSascha Wildner /** HUF_compress4X_wksp() : 91*a28cd43dSSascha Wildner * Same as HUF_compress2(), but uses externally allocated `workSpace`. 92*a28cd43dSSascha Wildner * `workspace` must have minimum alignment of 4, and be at least as large as HUF_WORKSPACE_SIZE */ 93*a28cd43dSSascha Wildner #define HUF_WORKSPACE_SIZE ((6 << 10) + 256) 94*a28cd43dSSascha Wildner #define HUF_WORKSPACE_SIZE_U32 (HUF_WORKSPACE_SIZE / sizeof(U32)) 95*a28cd43dSSascha Wildner HUF_PUBLIC_API size_t HUF_compress4X_wksp (void* dst, size_t dstCapacity, 96*a28cd43dSSascha Wildner const void* src, size_t srcSize, 97*a28cd43dSSascha Wildner unsigned maxSymbolValue, unsigned tableLog, 98*a28cd43dSSascha Wildner void* workSpace, size_t wkspSize); 99*a28cd43dSSascha Wildner 100*a28cd43dSSascha Wildner #endif /* HUF_H_298734234 */ 101*a28cd43dSSascha Wildner 102*a28cd43dSSascha Wildner /* ****************************************************************** 103*a28cd43dSSascha Wildner * WARNING !! 104*a28cd43dSSascha Wildner * The following section contains advanced and experimental definitions 105*a28cd43dSSascha Wildner * which shall never be used in the context of a dynamic library, 106*a28cd43dSSascha Wildner * because they are not guaranteed to remain stable in the future. 107*a28cd43dSSascha Wildner * Only consider them in association with static linking. 108*a28cd43dSSascha Wildner * *****************************************************************/ 109*a28cd43dSSascha Wildner #if defined(HUF_STATIC_LINKING_ONLY) && !defined(HUF_H_HUF_STATIC_LINKING_ONLY) 110*a28cd43dSSascha Wildner #define HUF_H_HUF_STATIC_LINKING_ONLY 111*a28cd43dSSascha Wildner 112*a28cd43dSSascha Wildner /* *** Dependencies *** */ 113*a28cd43dSSascha Wildner #include "mem.h" /* U32 */ 114*a28cd43dSSascha Wildner #define FSE_STATIC_LINKING_ONLY 115*a28cd43dSSascha Wildner #include "fse.h" 116*a28cd43dSSascha Wildner 117*a28cd43dSSascha Wildner 118*a28cd43dSSascha Wildner /* *** Constants *** */ 119*a28cd43dSSascha Wildner #define HUF_TABLELOG_MAX 12 /* max runtime value of tableLog (due to static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */ 120*a28cd43dSSascha Wildner #define HUF_TABLELOG_DEFAULT 11 /* default tableLog value when none specified */ 121*a28cd43dSSascha Wildner #define HUF_SYMBOLVALUE_MAX 255 122*a28cd43dSSascha Wildner 123*a28cd43dSSascha Wildner #define HUF_TABLELOG_ABSOLUTEMAX 15 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */ 124*a28cd43dSSascha Wildner #if (HUF_TABLELOG_MAX > HUF_TABLELOG_ABSOLUTEMAX) 125*a28cd43dSSascha Wildner # error "HUF_TABLELOG_MAX is too large !" 126*a28cd43dSSascha Wildner #endif 127*a28cd43dSSascha Wildner 128*a28cd43dSSascha Wildner 129*a28cd43dSSascha Wildner /* **************************************** 130*a28cd43dSSascha Wildner * Static allocation 131*a28cd43dSSascha Wildner ******************************************/ 132*a28cd43dSSascha Wildner /* HUF buffer bounds */ 133*a28cd43dSSascha Wildner #define HUF_CTABLEBOUND 129 134*a28cd43dSSascha Wildner #define HUF_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true when incompressible is pre-filtered with fast heuristic */ 135*a28cd43dSSascha Wildner #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ 136*a28cd43dSSascha Wildner 137*a28cd43dSSascha Wildner /* static allocation of HUF's Compression Table */ 138*a28cd43dSSascha Wildner /* this is a private definition, just exposed for allocation and strict aliasing purpose. never EVER access its members directly */ 139*a28cd43dSSascha Wildner struct HUF_CElt_s { 140*a28cd43dSSascha Wildner U16 val; 141*a28cd43dSSascha Wildner BYTE nbBits; 142*a28cd43dSSascha Wildner }; /* typedef'd to HUF_CElt */ 143*a28cd43dSSascha Wildner typedef struct HUF_CElt_s HUF_CElt; /* consider it an incomplete type */ 144*a28cd43dSSascha Wildner #define HUF_CTABLE_SIZE_U32(maxSymbolValue) ((maxSymbolValue)+1) /* Use tables of U32, for proper alignment */ 145*a28cd43dSSascha Wildner #define HUF_CTABLE_SIZE(maxSymbolValue) (HUF_CTABLE_SIZE_U32(maxSymbolValue) * sizeof(U32)) 146*a28cd43dSSascha Wildner #define HUF_CREATE_STATIC_CTABLE(name, maxSymbolValue) \ 147*a28cd43dSSascha Wildner HUF_CElt name[HUF_CTABLE_SIZE_U32(maxSymbolValue)] /* no final ; */ 148*a28cd43dSSascha Wildner 149*a28cd43dSSascha Wildner /* static allocation of HUF's DTable */ 150*a28cd43dSSascha Wildner typedef U32 HUF_DTable; 151*a28cd43dSSascha Wildner #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<(maxTableLog))) 152*a28cd43dSSascha Wildner #define HUF_CREATE_STATIC_DTABLEX1(DTable, maxTableLog) \ 153*a28cd43dSSascha Wildner HUF_DTable DTable[HUF_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1) * 0x01000001) } 154*a28cd43dSSascha Wildner #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \ 155*a28cd43dSSascha Wildner HUF_DTable DTable[HUF_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog) * 0x01000001) } 156*a28cd43dSSascha Wildner 157*a28cd43dSSascha Wildner 158*a28cd43dSSascha Wildner /* **************************************** 159*a28cd43dSSascha Wildner * Advanced decompression functions 160*a28cd43dSSascha Wildner ******************************************/ 161*a28cd43dSSascha Wildner size_t HUF_decompress4X1 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */ 162*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X1 163*a28cd43dSSascha Wildner size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */ 164*a28cd43dSSascha Wildner #endif 165*a28cd43dSSascha Wildner 166*a28cd43dSSascha Wildner size_t HUF_decompress4X_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< decodes RLE and uncompressed */ 167*a28cd43dSSascha Wildner size_t HUF_decompress4X_hufOnly(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< considers RLE and uncompressed as errors */ 168*a28cd43dSSascha Wildner size_t HUF_decompress4X_hufOnly_wksp(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize); /**< considers RLE and uncompressed as errors */ 169*a28cd43dSSascha Wildner size_t HUF_decompress4X1_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */ 170*a28cd43dSSascha Wildner size_t HUF_decompress4X1_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize); /**< single-symbol decoder */ 171*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X1 172*a28cd43dSSascha Wildner size_t HUF_decompress4X2_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */ 173*a28cd43dSSascha Wildner size_t HUF_decompress4X2_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize); /**< double-symbols decoder */ 174*a28cd43dSSascha Wildner #endif 175*a28cd43dSSascha Wildner 176*a28cd43dSSascha Wildner 177*a28cd43dSSascha Wildner /* **************************************** 178*a28cd43dSSascha Wildner * HUF detailed API 179*a28cd43dSSascha Wildner * ****************************************/ 180*a28cd43dSSascha Wildner 181*a28cd43dSSascha Wildner /*! HUF_compress() does the following: 182*a28cd43dSSascha Wildner * 1. count symbol occurrence from source[] into table count[] using FSE_count() (exposed within "fse.h") 183*a28cd43dSSascha Wildner * 2. (optional) refine tableLog using HUF_optimalTableLog() 184*a28cd43dSSascha Wildner * 3. build Huffman table from count using HUF_buildCTable() 185*a28cd43dSSascha Wildner * 4. save Huffman table to memory buffer using HUF_writeCTable() 186*a28cd43dSSascha Wildner * 5. encode the data stream using HUF_compress4X_usingCTable() 187*a28cd43dSSascha Wildner * 188*a28cd43dSSascha Wildner * The following API allows targeting specific sub-functions for advanced tasks. 189*a28cd43dSSascha Wildner * For example, it's possible to compress several blocks using the same 'CTable', 190*a28cd43dSSascha Wildner * or to save and regenerate 'CTable' using external methods. 191*a28cd43dSSascha Wildner */ 192*a28cd43dSSascha Wildner unsigned HUF_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue); 193*a28cd43dSSascha Wildner size_t HUF_buildCTable (HUF_CElt* CTable, const unsigned* count, unsigned maxSymbolValue, unsigned maxNbBits); /* @return : maxNbBits; CTable and count can overlap. In which case, CTable will overwrite count content */ 194*a28cd43dSSascha Wildner size_t HUF_writeCTable (void* dst, size_t maxDstSize, const HUF_CElt* CTable, unsigned maxSymbolValue, unsigned huffLog); 195*a28cd43dSSascha Wildner size_t HUF_compress4X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable); 196*a28cd43dSSascha Wildner size_t HUF_estimateCompressedSize(const HUF_CElt* CTable, const unsigned* count, unsigned maxSymbolValue); 197*a28cd43dSSascha Wildner int HUF_validateCTable(const HUF_CElt* CTable, const unsigned* count, unsigned maxSymbolValue); 198*a28cd43dSSascha Wildner 199*a28cd43dSSascha Wildner typedef enum { 200*a28cd43dSSascha Wildner HUF_repeat_none, /**< Cannot use the previous table */ 201*a28cd43dSSascha Wildner HUF_repeat_check, /**< Can use the previous table but it must be checked. Note : The previous table must have been constructed by HUF_compress{1, 4}X_repeat */ 202*a28cd43dSSascha Wildner HUF_repeat_valid /**< Can use the previous table and it is assumed to be valid */ 203*a28cd43dSSascha Wildner } HUF_repeat; 204*a28cd43dSSascha Wildner /** HUF_compress4X_repeat() : 205*a28cd43dSSascha Wildner * Same as HUF_compress4X_wksp(), but considers using hufTable if *repeat != HUF_repeat_none. 206*a28cd43dSSascha Wildner * If it uses hufTable it does not modify hufTable or repeat. 207*a28cd43dSSascha Wildner * If it doesn't, it sets *repeat = HUF_repeat_none, and it sets hufTable to the table used. 208*a28cd43dSSascha Wildner * If preferRepeat then the old table will always be used if valid. */ 209*a28cd43dSSascha Wildner size_t HUF_compress4X_repeat(void* dst, size_t dstSize, 210*a28cd43dSSascha Wildner const void* src, size_t srcSize, 211*a28cd43dSSascha Wildner unsigned maxSymbolValue, unsigned tableLog, 212*a28cd43dSSascha Wildner void* workSpace, size_t wkspSize, /**< `workSpace` must be aligned on 4-bytes boundaries, `wkspSize` must be >= HUF_WORKSPACE_SIZE */ 213*a28cd43dSSascha Wildner HUF_CElt* hufTable, HUF_repeat* repeat, int preferRepeat, int bmi2); 214*a28cd43dSSascha Wildner 215*a28cd43dSSascha Wildner /** HUF_buildCTable_wksp() : 216*a28cd43dSSascha Wildner * Same as HUF_buildCTable(), but using externally allocated scratch buffer. 217*a28cd43dSSascha Wildner * `workSpace` must be aligned on 4-bytes boundaries, and its size must be >= HUF_CTABLE_WORKSPACE_SIZE. 218*a28cd43dSSascha Wildner */ 219*a28cd43dSSascha Wildner #define HUF_CTABLE_WORKSPACE_SIZE_U32 (2*HUF_SYMBOLVALUE_MAX +1 +1) 220*a28cd43dSSascha Wildner #define HUF_CTABLE_WORKSPACE_SIZE (HUF_CTABLE_WORKSPACE_SIZE_U32 * sizeof(unsigned)) 221*a28cd43dSSascha Wildner size_t HUF_buildCTable_wksp (HUF_CElt* tree, 222*a28cd43dSSascha Wildner const unsigned* count, U32 maxSymbolValue, U32 maxNbBits, 223*a28cd43dSSascha Wildner void* workSpace, size_t wkspSize); 224*a28cd43dSSascha Wildner 225*a28cd43dSSascha Wildner /*! HUF_readStats() : 226*a28cd43dSSascha Wildner * Read compact Huffman tree, saved by HUF_writeCTable(). 227*a28cd43dSSascha Wildner * `huffWeight` is destination buffer. 228*a28cd43dSSascha Wildner * @return : size read from `src` , or an error Code . 229*a28cd43dSSascha Wildner * Note : Needed by HUF_readCTable() and HUF_readDTableXn() . */ 230*a28cd43dSSascha Wildner size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, 231*a28cd43dSSascha Wildner U32* rankStats, U32* nbSymbolsPtr, U32* tableLogPtr, 232*a28cd43dSSascha Wildner const void* src, size_t srcSize); 233*a28cd43dSSascha Wildner 234*a28cd43dSSascha Wildner /*! HUF_readStats_wksp() : 235*a28cd43dSSascha Wildner * Same as HUF_readStats() but takes an external workspace which must be 236*a28cd43dSSascha Wildner * 4-byte aligned and its size must be >= HUF_READ_STATS_WORKSPACE_SIZE. 237*a28cd43dSSascha Wildner * If the CPU has BMI2 support, pass bmi2=1, otherwise pass bmi2=0. 238*a28cd43dSSascha Wildner */ 239*a28cd43dSSascha Wildner #define HUF_READ_STATS_WORKSPACE_SIZE_U32 FSE_DECOMPRESS_WKSP_SIZE_U32(6, HUF_TABLELOG_MAX-1) 240*a28cd43dSSascha Wildner #define HUF_READ_STATS_WORKSPACE_SIZE (HUF_READ_STATS_WORKSPACE_SIZE_U32 * sizeof(unsigned)) 241*a28cd43dSSascha Wildner size_t HUF_readStats_wksp(BYTE* huffWeight, size_t hwSize, 242*a28cd43dSSascha Wildner U32* rankStats, U32* nbSymbolsPtr, U32* tableLogPtr, 243*a28cd43dSSascha Wildner const void* src, size_t srcSize, 244*a28cd43dSSascha Wildner void* workspace, size_t wkspSize, 245*a28cd43dSSascha Wildner int bmi2); 246*a28cd43dSSascha Wildner 247*a28cd43dSSascha Wildner /** HUF_readCTable() : 248*a28cd43dSSascha Wildner * Loading a CTable saved with HUF_writeCTable() */ 249*a28cd43dSSascha Wildner size_t HUF_readCTable (HUF_CElt* CTable, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize, unsigned *hasZeroWeights); 250*a28cd43dSSascha Wildner 251*a28cd43dSSascha Wildner /** HUF_getNbBits() : 252*a28cd43dSSascha Wildner * Read nbBits from CTable symbolTable, for symbol `symbolValue` presumed <= HUF_SYMBOLVALUE_MAX 253*a28cd43dSSascha Wildner * Note 1 : is not inlined, as HUF_CElt definition is private 254*a28cd43dSSascha Wildner * Note 2 : const void* used, so that it can provide a statically allocated table as argument (which uses type U32) */ 255*a28cd43dSSascha Wildner U32 HUF_getNbBits(const void* symbolTable, U32 symbolValue); 256*a28cd43dSSascha Wildner 257*a28cd43dSSascha Wildner /* 258*a28cd43dSSascha Wildner * HUF_decompress() does the following: 259*a28cd43dSSascha Wildner * 1. select the decompression algorithm (X1, X2) based on pre-computed heuristics 260*a28cd43dSSascha Wildner * 2. build Huffman table from save, using HUF_readDTableX?() 261*a28cd43dSSascha Wildner * 3. decode 1 or 4 segments in parallel using HUF_decompress?X?_usingDTable() 262*a28cd43dSSascha Wildner */ 263*a28cd43dSSascha Wildner 264*a28cd43dSSascha Wildner /** HUF_selectDecoder() : 265*a28cd43dSSascha Wildner * Tells which decoder is likely to decode faster, 266*a28cd43dSSascha Wildner * based on a set of pre-computed metrics. 267*a28cd43dSSascha Wildner * @return : 0==HUF_decompress4X1, 1==HUF_decompress4X2 . 268*a28cd43dSSascha Wildner * Assumption : 0 < dstSize <= 128 KB */ 269*a28cd43dSSascha Wildner U32 HUF_selectDecoder (size_t dstSize, size_t cSrcSize); 270*a28cd43dSSascha Wildner 271*a28cd43dSSascha Wildner /** 272*a28cd43dSSascha Wildner * The minimum workspace size for the `workSpace` used in 273*a28cd43dSSascha Wildner * HUF_readDTableX1_wksp() and HUF_readDTableX2_wksp(). 274*a28cd43dSSascha Wildner * 275*a28cd43dSSascha Wildner * The space used depends on HUF_TABLELOG_MAX, ranging from ~1500 bytes when 276*a28cd43dSSascha Wildner * HUF_TABLE_LOG_MAX=12 to ~1850 bytes when HUF_TABLE_LOG_MAX=15. 277*a28cd43dSSascha Wildner * Buffer overflow errors may potentially occur if code modifications result in 278*a28cd43dSSascha Wildner * a required workspace size greater than that specified in the following 279*a28cd43dSSascha Wildner * macro. 280*a28cd43dSSascha Wildner */ 281*a28cd43dSSascha Wildner #define HUF_DECOMPRESS_WORKSPACE_SIZE (2 << 10) 282*a28cd43dSSascha Wildner #define HUF_DECOMPRESS_WORKSPACE_SIZE_U32 (HUF_DECOMPRESS_WORKSPACE_SIZE / sizeof(U32)) 283*a28cd43dSSascha Wildner 284*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X2 285*a28cd43dSSascha Wildner size_t HUF_readDTableX1 (HUF_DTable* DTable, const void* src, size_t srcSize); 286*a28cd43dSSascha Wildner size_t HUF_readDTableX1_wksp (HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize); 287*a28cd43dSSascha Wildner #endif 288*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X1 289*a28cd43dSSascha Wildner size_t HUF_readDTableX2 (HUF_DTable* DTable, const void* src, size_t srcSize); 290*a28cd43dSSascha Wildner size_t HUF_readDTableX2_wksp (HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize); 291*a28cd43dSSascha Wildner #endif 292*a28cd43dSSascha Wildner 293*a28cd43dSSascha Wildner size_t HUF_decompress4X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable); 294*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X2 295*a28cd43dSSascha Wildner size_t HUF_decompress4X1_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable); 296*a28cd43dSSascha Wildner #endif 297*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X1 298*a28cd43dSSascha Wildner size_t HUF_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable); 299*a28cd43dSSascha Wildner #endif 300*a28cd43dSSascha Wildner 301*a28cd43dSSascha Wildner 302*a28cd43dSSascha Wildner /* ====================== */ 303*a28cd43dSSascha Wildner /* single stream variants */ 304*a28cd43dSSascha Wildner /* ====================== */ 305*a28cd43dSSascha Wildner 306*a28cd43dSSascha Wildner size_t HUF_compress1X (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog); 307*a28cd43dSSascha Wildner size_t HUF_compress1X_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); /**< `workSpace` must be a table of at least HUF_WORKSPACE_SIZE_U32 unsigned */ 308*a28cd43dSSascha Wildner size_t HUF_compress1X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable); 309*a28cd43dSSascha Wildner /** HUF_compress1X_repeat() : 310*a28cd43dSSascha Wildner * Same as HUF_compress1X_wksp(), but considers using hufTable if *repeat != HUF_repeat_none. 311*a28cd43dSSascha Wildner * If it uses hufTable it does not modify hufTable or repeat. 312*a28cd43dSSascha Wildner * If it doesn't, it sets *repeat = HUF_repeat_none, and it sets hufTable to the table used. 313*a28cd43dSSascha Wildner * If preferRepeat then the old table will always be used if valid. */ 314*a28cd43dSSascha Wildner size_t HUF_compress1X_repeat(void* dst, size_t dstSize, 315*a28cd43dSSascha Wildner const void* src, size_t srcSize, 316*a28cd43dSSascha Wildner unsigned maxSymbolValue, unsigned tableLog, 317*a28cd43dSSascha Wildner void* workSpace, size_t wkspSize, /**< `workSpace` must be aligned on 4-bytes boundaries, `wkspSize` must be >= HUF_WORKSPACE_SIZE */ 318*a28cd43dSSascha Wildner HUF_CElt* hufTable, HUF_repeat* repeat, int preferRepeat, int bmi2); 319*a28cd43dSSascha Wildner 320*a28cd43dSSascha Wildner size_t HUF_decompress1X1 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ 321*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X1 322*a28cd43dSSascha Wildner size_t HUF_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */ 323*a28cd43dSSascha Wildner #endif 324*a28cd43dSSascha Wildner 325*a28cd43dSSascha Wildner size_t HUF_decompress1X_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); 326*a28cd43dSSascha Wildner size_t HUF_decompress1X_DCtx_wksp (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize); 327*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X2 328*a28cd43dSSascha Wildner size_t HUF_decompress1X1_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */ 329*a28cd43dSSascha Wildner size_t HUF_decompress1X1_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize); /**< single-symbol decoder */ 330*a28cd43dSSascha Wildner #endif 331*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X1 332*a28cd43dSSascha Wildner size_t HUF_decompress1X2_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */ 333*a28cd43dSSascha Wildner size_t HUF_decompress1X2_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize); /**< double-symbols decoder */ 334*a28cd43dSSascha Wildner #endif 335*a28cd43dSSascha Wildner 336*a28cd43dSSascha Wildner size_t HUF_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable); /**< automatic selection of sing or double symbol decoder, based on DTable */ 337*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X2 338*a28cd43dSSascha Wildner size_t HUF_decompress1X1_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable); 339*a28cd43dSSascha Wildner #endif 340*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X1 341*a28cd43dSSascha Wildner size_t HUF_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable); 342*a28cd43dSSascha Wildner #endif 343*a28cd43dSSascha Wildner 344*a28cd43dSSascha Wildner /* BMI2 variants. 345*a28cd43dSSascha Wildner * If the CPU has BMI2 support, pass bmi2=1, otherwise pass bmi2=0. 346*a28cd43dSSascha Wildner */ 347*a28cd43dSSascha Wildner size_t HUF_decompress1X_usingDTable_bmi2(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, int bmi2); 348*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X2 349*a28cd43dSSascha Wildner size_t HUF_decompress1X1_DCtx_wksp_bmi2(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize, int bmi2); 350*a28cd43dSSascha Wildner #endif 351*a28cd43dSSascha Wildner size_t HUF_decompress4X_usingDTable_bmi2(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, int bmi2); 352*a28cd43dSSascha Wildner size_t HUF_decompress4X_hufOnly_wksp_bmi2(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize, int bmi2); 353*a28cd43dSSascha Wildner #ifndef HUF_FORCE_DECOMPRESS_X2 354*a28cd43dSSascha Wildner size_t HUF_readDTableX1_wksp_bmi2(HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize, int bmi2); 355*a28cd43dSSascha Wildner #endif 356*a28cd43dSSascha Wildner 357*a28cd43dSSascha Wildner #endif /* HUF_STATIC_LINKING_ONLY */ 358*a28cd43dSSascha Wildner 359*a28cd43dSSascha Wildner #if defined (__cplusplus) 360*a28cd43dSSascha Wildner } 361*a28cd43dSSascha Wildner #endif 362