/* ****************************************************************** * huff0 huffman decoder, * part of Finite State Entropy library * Copyright (c) Meta Platforms, Inc. and affiliates. * * You can contact the author at : * - FSE+HUF 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. ****************************************************************** */ /* ************************************************************** * Dependencies ****************************************************************/ #include "../common/zstd_deps.h" /* ZSTD_memcpy, ZSTD_memset */ #include "../common/compiler.h" #include "../common/bitstream.h" /* BIT_* */ #include "../common/fse.h" /* to compress headers */ #include "../common/huf.h" #include "../common/error_private.h" #include "../common/zstd_internal.h" #include "../common/bits.h" /* ZSTD_highbit32, ZSTD_countTrailingZeros64 */ /* ************************************************************** * Constants ****************************************************************/ #define HUF_DECODER_FAST_TABLELOG … /* ************************************************************** * Macros ****************************************************************/ #ifdef HUF_DISABLE_FAST_DECODE #define HUF_ENABLE_FAST_DECODE … #else #define HUF_ENABLE_FAST_DECODE … #endif /* These two optional macros force the use one way or another of the two * Huffman decompression implementations. You can't force in both directions * at the same time. */ #if defined(HUF_FORCE_DECOMPRESS_X1) && \ defined(HUF_FORCE_DECOMPRESS_X2) #error "Cannot force the use of the X1 and X2 decoders at the same time!" #endif /* When DYNAMIC_BMI2 is enabled, fast decoders are only called when bmi2 is * supported at runtime, so we can add the BMI2 target attribute. * When it is disabled, we will still get BMI2 if it is enabled statically. */ #if DYNAMIC_BMI2 #define HUF_FAST_BMI2_ATTRS … #else #define HUF_FAST_BMI2_ATTRS #endif #ifdef __cplusplus #define HUF_EXTERN_C … #else #define HUF_EXTERN_C #endif #define HUF_ASM_DECL … #if DYNAMIC_BMI2 #define HUF_NEED_BMI2_FUNCTION … #else #define HUF_NEED_BMI2_FUNCTION … #endif /* ************************************************************** * Error Management ****************************************************************/ #define HUF_isError … /* ************************************************************** * Byte alignment for workSpace management ****************************************************************/ #define HUF_ALIGN(x, a) … #define HUF_ALIGN_MASK(x, mask) … /* ************************************************************** * BMI2 Variant Wrappers ****************************************************************/ HUF_DecompressUsingDTableFn; #if DYNAMIC_BMI2 #define HUF_DGEN(fn) … #else #define HUF_DGEN … #endif /*-***************************/ /* generic DTableDesc */ /*-***************************/ DTableDesc; static DTableDesc HUF_getDTableDesc(const HUF_DTable* table) { … } static size_t HUF_initFastDStream(BYTE const* ip) { … } /** * The input/output arguments to the Huffman fast decoding loop: * * ip [in/out] - The input pointers, must be updated to reflect what is consumed. * op [in/out] - The output pointers, must be updated to reflect what is written. * bits [in/out] - The bitstream containers, must be updated to reflect the current state. * dt [in] - The decoding table. * ilowest [in] - The beginning of the valid range of the input. Decoders may read * down to this pointer. It may be below iend[0]. * oend [in] - The end of the output stream. op[3] must not cross oend. * iend [in] - The end of each input stream. ip[i] may cross iend[i], * as long as it is above ilowest, but that indicates corruption. */ HUF_DecompressFastArgs; HUF_DecompressFastLoopFn; /** * Initializes args for the fast decoding loop. * @returns 1 on success * 0 if the fallback implementation should be used. * Or an error code on failure. */ static size_t HUF_DecompressFastArgs_init(HUF_DecompressFastArgs* args, void* dst, size_t dstSize, void const* src, size_t srcSize, const HUF_DTable* DTable) { … } static size_t HUF_initRemainingDStream(BIT_DStream_t* bit, HUF_DecompressFastArgs const* args, int stream, BYTE* segmentEnd) { … } /* Calls X(N) for each stream 0, 1, 2, 3. */ #define HUF_4X_FOR_EACH_STREAM(X) … /* Calls X(N, var) for each stream 0, 1, 2, 3. */ #define HUF_4X_FOR_EACH_STREAM_WITH_VAR(X, var) … #ifndef HUF_FORCE_DECOMPRESS_X2 /*-***************************/ /* single-symbol decoding */ /*-***************************/ HUF_DEltX1; /* single-symbol decoding */ /** * Packs 4 HUF_DEltX1 structs into a U64. This is used to lay down 4 entries at * a time. */ static U64 HUF_DEltX1_set4(BYTE symbol, BYTE nbBits) { … } /** * Increase the tableLog to targetTableLog and rescales the stats. * If tableLog > targetTableLog this is a no-op. * @returns New tableLog */ static U32 HUF_rescaleStats(BYTE* huffWeight, U32* rankVal, U32 nbSymbols, U32 tableLog, U32 targetTableLog) { … } HUF_ReadDTableX1_Workspace; size_t HUF_readDTableX1_wksp(HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize, int flags) { … } FORCE_INLINE_TEMPLATE BYTE HUF_decodeSymbolX1(BIT_DStream_t* Dstream, const HUF_DEltX1* dt, const U32 dtLog) { … } #define HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr) … #define HUF_DECODE_SYMBOLX1_1(ptr, DStreamPtr) … #define HUF_DECODE_SYMBOLX1_2(ptr, DStreamPtr) … HINT_INLINE size_t HUF_decodeStreamX1(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX1* const dt, const U32 dtLog) { … } FORCE_INLINE_TEMPLATE size_t HUF_decompress1X1_usingDTable_internal_body( void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable) { … } /* HUF_decompress4X1_usingDTable_internal_body(): * Conditions : * @dstSize >= 6 */ FORCE_INLINE_TEMPLATE size_t HUF_decompress4X1_usingDTable_internal_body( void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable) { … } #if HUF_NEED_BMI2_FUNCTION static BMI2_TARGET_ATTRIBUTE size_t HUF_decompress4X1_usingDTable_internal_bmi2(void* dst, size_t dstSize, void const* cSrc, size_t cSrcSize, HUF_DTable const* DTable) { … } #endif static size_t HUF_decompress4X1_usingDTable_internal_default(void* dst, size_t dstSize, void const* cSrc, size_t cSrcSize, HUF_DTable const* DTable) { … } #if ZSTD_ENABLE_ASM_X86_64_BMI2 HUF_ASM_DECL void HUF_decompress4X1_usingDTable_internal_fast_asm_loop(HUF_DecompressFastArgs* args) ZSTDLIB_HIDDEN; #endif static HUF_FAST_BMI2_ATTRS void HUF_decompress4X1_usingDTable_internal_fast_c_loop(HUF_DecompressFastArgs* args) { … } /** * @returns @p dstSize on success (>= 6) * 0 if the fallback implementation should be used * An error if an error occurred */ static HUF_FAST_BMI2_ATTRS size_t HUF_decompress4X1_usingDTable_internal_fast( void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, HUF_DecompressFastLoopFn loopFn) { … } HUF_DGEN(…) static size_t HUF_decompress4X1_usingDTable_internal(void* dst, size_t dstSize, void const* cSrc, size_t cSrcSize, HUF_DTable const* DTable, int flags) { … } static 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, int flags) { … } #endif /* HUF_FORCE_DECOMPRESS_X2 */ #ifndef HUF_FORCE_DECOMPRESS_X1 /* *************************/ /* double-symbols decoding */ /* *************************/ HUF_DEltX2; /* double-symbols decoding */ sortedSymbol_t; rankValCol_t; rankVal_t; /** * Constructs a HUF_DEltX2 in a U32. */ static U32 HUF_buildDEltX2U32(U32 symbol, U32 nbBits, U32 baseSeq, int level) { … } /** * Constructs a HUF_DEltX2. */ static HUF_DEltX2 HUF_buildDEltX2(U32 symbol, U32 nbBits, U32 baseSeq, int level) { … } /** * Constructs 2 HUF_DEltX2s and packs them into a U64. */ static U64 HUF_buildDEltX2U64(U32 symbol, U32 nbBits, U16 baseSeq, int level) { … } /** * Fills the DTable rank with all the symbols from [begin, end) that are each * nbBits long. * * @param DTableRank The start of the rank in the DTable. * @param begin The first symbol to fill (inclusive). * @param end The last symbol to fill (exclusive). * @param nbBits Each symbol is nbBits long. * @param tableLog The table log. * @param baseSeq If level == 1 { 0 } else { the first level symbol } * @param level The level in the table. Must be 1 or 2. */ static void HUF_fillDTableX2ForWeight( HUF_DEltX2* DTableRank, sortedSymbol_t const* begin, sortedSymbol_t const* end, U32 nbBits, U32 tableLog, U16 baseSeq, int const level) { … } /* HUF_fillDTableX2Level2() : * `rankValOrigin` must be a table of at least (HUF_TABLELOG_MAX + 1) U32 */ static void HUF_fillDTableX2Level2(HUF_DEltX2* DTable, U32 targetLog, const U32 consumedBits, const U32* rankVal, const int minWeight, const int maxWeight1, const sortedSymbol_t* sortedSymbols, U32 const* rankStart, U32 nbBitsBaseline, U16 baseSeq) { … } static void HUF_fillDTableX2(HUF_DEltX2* DTable, const U32 targetLog, const sortedSymbol_t* sortedList, const U32* rankStart, rankValCol_t* rankValOrigin, const U32 maxWeight, const U32 nbBitsBaseline) { … } HUF_ReadDTableX2_Workspace; size_t HUF_readDTableX2_wksp(HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize, int flags) { … } FORCE_INLINE_TEMPLATE U32 HUF_decodeSymbolX2(void* op, BIT_DStream_t* DStream, const HUF_DEltX2* dt, const U32 dtLog) { … } FORCE_INLINE_TEMPLATE U32 HUF_decodeLastSymbolX2(void* op, BIT_DStream_t* DStream, const HUF_DEltX2* dt, const U32 dtLog) { … } #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) … #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) … #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) … HINT_INLINE size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog) { … } FORCE_INLINE_TEMPLATE size_t HUF_decompress1X2_usingDTable_internal_body( void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable) { … } /* HUF_decompress4X2_usingDTable_internal_body(): * Conditions: * @dstSize >= 6 */ FORCE_INLINE_TEMPLATE size_t HUF_decompress4X2_usingDTable_internal_body( void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable) { … } #if HUF_NEED_BMI2_FUNCTION static BMI2_TARGET_ATTRIBUTE size_t HUF_decompress4X2_usingDTable_internal_bmi2(void* dst, size_t dstSize, void const* cSrc, size_t cSrcSize, HUF_DTable const* DTable) { … } #endif static size_t HUF_decompress4X2_usingDTable_internal_default(void* dst, size_t dstSize, void const* cSrc, size_t cSrcSize, HUF_DTable const* DTable) { … } #if ZSTD_ENABLE_ASM_X86_64_BMI2 HUF_ASM_DECL void HUF_decompress4X2_usingDTable_internal_fast_asm_loop(HUF_DecompressFastArgs* args) ZSTDLIB_HIDDEN; #endif static HUF_FAST_BMI2_ATTRS void HUF_decompress4X2_usingDTable_internal_fast_c_loop(HUF_DecompressFastArgs* args) { … } static HUF_FAST_BMI2_ATTRS size_t HUF_decompress4X2_usingDTable_internal_fast( void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, HUF_DecompressFastLoopFn loopFn) { … } static size_t HUF_decompress4X2_usingDTable_internal(void* dst, size_t dstSize, void const* cSrc, size_t cSrcSize, HUF_DTable const* DTable, int flags) { … } HUF_DGEN(…) 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, int flags) { … } static 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, int flags) { … } #endif /* HUF_FORCE_DECOMPRESS_X1 */ /* ***********************************/ /* Universal decompression selectors */ /* ***********************************/ #if !defined(HUF_FORCE_DECOMPRESS_X1) && !defined(HUF_FORCE_DECOMPRESS_X2) algo_time_t; static const algo_time_t algoTime[16 /* Quantization */][2 /* single, double */] = …; #endif /** HUF_selectDecoder() : * Tells which decoder is likely to decode faster, * based on a set of pre-computed metrics. * @return : 0==HUF_decompress4X1, 1==HUF_decompress4X2 . * Assumption : 0 < dstSize <= 128 KB */ U32 HUF_selectDecoder (size_t dstSize, size_t cSrcSize) { … } 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, int flags) { … } size_t HUF_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, int flags) { … } #ifndef HUF_FORCE_DECOMPRESS_X2 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, int flags) { … } #endif size_t HUF_decompress4X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, int flags) { … } 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, int flags) { … }
Codebase Browser
chromium