/* ****************************************************************** * huff0 huffman decoder, * part of Finite State Entropy library * Copyright (c) Yann Collet, Facebook, Inc. * * 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 */ #define HUF_STATIC_LINKING_ONLY #include "../common/huf.h" #include "../common/error_private.h" #include "../common/zstd_internal.h" /* ************************************************************** * Constants ****************************************************************/ #define HUF_DECODER_FAST_TABLELOG … /* ************************************************************** * Macros ****************************************************************/ /* 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 #if ZSTD_ENABLE_ASM_X86_64_BMI2 && DYNAMIC_BMI2 #define HUF_ASM_X86_64_BMI2_ATTRS … #else #define HUF_ASM_X86_64_BMI2_ATTRS #endif #define HUF_EXTERN_C #define HUF_ASM_DECL … #if DYNAMIC_BMI2 || (ZSTD_ENABLE_ASM_X86_64_BMI2 && defined(__BMI2__)) #define HUF_NEED_BMI2_FUNCTION … #else #define HUF_NEED_BMI2_FUNCTION … #endif #if !(ZSTD_ENABLE_ASM_X86_64_BMI2 && defined(__BMI2__)) #define HUF_NEED_DEFAULT_FUNCTION … #else #define HUF_NEED_DEFAULT_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 ****************************************************************/ #if DYNAMIC_BMI2 #define HUF_DGEN(fn) … #else #define HUF_DGEN … #endif /*-***************************/ /* generic DTableDesc */ /*-***************************/ DTableDesc; static DTableDesc HUF_getDTableDesc(const HUF_DTable* table) { … } #if ZSTD_ENABLE_ASM_X86_64_BMI2 static size_t HUF_initDStream(BYTE const* ip) { BYTE const lastByte = ip[7]; size_t const bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; size_t const value = MEM_readLEST(ip) | 1; assert(bitsConsumed <= 8); return value << bitsConsumed; } typedef struct { BYTE const* ip[4]; BYTE* op[4]; U64 bits[4]; void const* dt; BYTE const* ilimit; BYTE* oend; BYTE const* iend[4]; } HUF_DecompressAsmArgs; /* * Initializes args for the asm decoding loop. * @returns 0 on success * 1 if the fallback implementation should be used. * Or an error code on failure. */ static size_t HUF_DecompressAsmArgs_init(HUF_DecompressAsmArgs* args, void* dst, size_t dstSize, void const* src, size_t srcSize, const HUF_DTable* DTable) { void const* dt = DTable + 1; U32 const dtLog = HUF_getDTableDesc(DTable).tableLog; const BYTE* const ilimit = (const BYTE*)src + 6 + 8; BYTE* const oend = (BYTE*)dst + dstSize; /* The following condition is false on x32 platform, * but HUF_asm is not compatible with this ABI */ if (!(MEM_isLittleEndian() && !MEM_32bits())) return 1; /* strict minimum : jump table + 1 byte per stream */ if (srcSize < 10) return ERROR(corruption_detected); /* Must have at least 8 bytes per stream because we don't handle initializing smaller bit containers. * If table log is not correct at this point, fallback to the old decoder. * On small inputs we don't have enough data to trigger the fast loop, so use the old decoder. */ if (dtLog != HUF_DECODER_FAST_TABLELOG) return 1; /* Read the jump table. */ { const BYTE* const istart = (const BYTE*)src; size_t const length1 = MEM_readLE16(istart); size_t const length2 = MEM_readLE16(istart+2); size_t const length3 = MEM_readLE16(istart+4); size_t const length4 = srcSize - (length1 + length2 + length3 + 6); args->iend[0] = istart + 6; /* jumpTable */ args->iend[1] = args->iend[0] + length1; args->iend[2] = args->iend[1] + length2; args->iend[3] = args->iend[2] + length3; /* HUF_initDStream() requires this, and this small of an input * won't benefit from the ASM loop anyways. * length1 must be >= 16 so that ip[0] >= ilimit before the loop * starts. */ if (length1 < 16 || length2 < 8 || length3 < 8 || length4 < 8) return 1; if (length4 > srcSize) return ERROR(corruption_detected); /* overflow */ } /* ip[] contains the position that is currently loaded into bits[]. */ args->ip[0] = args->iend[1] - sizeof(U64); args->ip[1] = args->iend[2] - sizeof(U64); args->ip[2] = args->iend[3] - sizeof(U64); args->ip[3] = (BYTE const*)src + srcSize - sizeof(U64); /* op[] contains the output pointers. */ args->op[0] = (BYTE*)dst; args->op[1] = args->op[0] + (dstSize+3)/4; args->op[2] = args->op[1] + (dstSize+3)/4; args->op[3] = args->op[2] + (dstSize+3)/4; /* No point to call the ASM loop for tiny outputs. */ if (args->op[3] >= oend) return 1; /* bits[] is the bit container. * It is read from the MSB down to the LSB. * It is shifted left as it is read, and zeros are * shifted in. After the lowest valid bit a 1 is * set, so that CountTrailingZeros(bits[]) can be used * to count how many bits we've consumed. */ args->bits[0] = HUF_initDStream(args->ip[0]); args->bits[1] = HUF_initDStream(args->ip[1]); args->bits[2] = HUF_initDStream(args->ip[2]); args->bits[3] = HUF_initDStream(args->ip[3]); /* If ip[] >= ilimit, it is guaranteed to be safe to * reload bits[]. It may be beyond its section, but is * guaranteed to be valid (>= istart). */ args->ilimit = ilimit; args->oend = oend; args->dt = dt; return 0; } static size_t HUF_initRemainingDStream(BIT_DStream_t* bit, HUF_DecompressAsmArgs const* args, int stream, BYTE* segmentEnd) { /* Validate that we haven't overwritten. */ if (args->op[stream] > segmentEnd) return ERROR(corruption_detected); /* Validate that we haven't read beyond iend[]. * Note that ip[] may be < iend[] because the MSB is * the next bit to read, and we may have consumed 100% * of the stream, so down to iend[i] - 8 is valid. */ if (args->ip[stream] < args->iend[stream] - 8) return ERROR(corruption_detected); /* Construct the BIT_DStream_t. */ bit->bitContainer = MEM_readLE64(args->ip[stream]); bit->bitsConsumed = ZSTD_countTrailingZeros((size_t)args->bits[stream]); bit->start = (const char*)args->iend[0]; bit->limitPtr = bit->start + sizeof(size_t); bit->ptr = (const char*)args->ip[stream]; return 0; } #endif #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) { … } size_t HUF_readDTableX1_wksp_bmi2(HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize, int bmi2) { … } 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) { … } 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 #if HUF_NEED_DEFAULT_FUNCTION static size_t HUF_decompress4X1_usingDTable_internal_default(void* dst, size_t dstSize, void const* cSrc, size_t cSrcSize, HUF_DTable const* DTable) { … } #endif #if ZSTD_ENABLE_ASM_X86_64_BMI2 HUF_ASM_DECL void HUF_decompress4X1_usingDTable_internal_bmi2_asm_loop(HUF_DecompressAsmArgs* args) ZSTDLIB_HIDDEN; static HUF_ASM_X86_64_BMI2_ATTRS size_t HUF_decompress4X1_usingDTable_internal_bmi2_asm( void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable) { void const* dt = DTable + 1; const BYTE* const iend = (const BYTE*)cSrc + 6; BYTE* const oend = (BYTE*)dst + dstSize; HUF_DecompressAsmArgs args; { size_t const ret = HUF_DecompressAsmArgs_init(&args, dst, dstSize, cSrc, cSrcSize, DTable); FORWARD_IF_ERROR(ret, "Failed to init asm args"); if (ret != 0) return HUF_decompress4X1_usingDTable_internal_bmi2(dst, dstSize, cSrc, cSrcSize, DTable); } assert(args.ip[0] >= args.ilimit); HUF_decompress4X1_usingDTable_internal_bmi2_asm_loop(&args); /* Our loop guarantees that ip[] >= ilimit and that we haven't * overwritten any op[]. */ assert(args.ip[0] >= iend); assert(args.ip[1] >= iend); assert(args.ip[2] >= iend); assert(args.ip[3] >= iend); assert(args.op[3] <= oend); (void)iend; /* finish bit streams one by one. */ { size_t const segmentSize = (dstSize+3) / 4; BYTE* segmentEnd = (BYTE*)dst; int i; for (i = 0; i < 4; ++i) { BIT_DStream_t bit; if (segmentSize <= (size_t)(oend - segmentEnd)) segmentEnd += segmentSize; else segmentEnd = oend; FORWARD_IF_ERROR(HUF_initRemainingDStream(&bit, &args, i, segmentEnd), "corruption"); /* Decompress and validate that we've produced exactly the expected length. */ args.op[i] += HUF_decodeStreamX1(args.op[i], &bit, segmentEnd, (HUF_DEltX1 const*)dt, HUF_DECODER_FAST_TABLELOG); if (args.op[i] != segmentEnd) return ERROR(corruption_detected); } } /* decoded size */ return dstSize; } #endif /* ZSTD_ENABLE_ASM_X86_64_BMI2 */ HUF_decompress_usingDTable_t; 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 bmi2) { … } size_t HUF_decompress1X1_usingDTable( void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable) { … } 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) { … } size_t HUF_decompress4X1_usingDTable( void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable) { … } static size_t HUF_decompress4X1_DCtx_wksp_bmi2(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize, int bmi2) { … } 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) { … } #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) { … } size_t HUF_readDTableX2_wksp_bmi2(HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize, int bmi2) { … } 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) { … } 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 #if HUF_NEED_DEFAULT_FUNCTION static size_t HUF_decompress4X2_usingDTable_internal_default(void* dst, size_t dstSize, void const* cSrc, size_t cSrcSize, HUF_DTable const* DTable) { … } #endif #if ZSTD_ENABLE_ASM_X86_64_BMI2 HUF_ASM_DECL void HUF_decompress4X2_usingDTable_internal_bmi2_asm_loop(HUF_DecompressAsmArgs* args) ZSTDLIB_HIDDEN; static HUF_ASM_X86_64_BMI2_ATTRS size_t HUF_decompress4X2_usingDTable_internal_bmi2_asm( void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable) { void const* dt = DTable + 1; const BYTE* const iend = (const BYTE*)cSrc + 6; BYTE* const oend = (BYTE*)dst + dstSize; HUF_DecompressAsmArgs args; { size_t const ret = HUF_DecompressAsmArgs_init(&args, dst, dstSize, cSrc, cSrcSize, DTable); FORWARD_IF_ERROR(ret, "Failed to init asm args"); if (ret != 0) return HUF_decompress4X2_usingDTable_internal_bmi2(dst, dstSize, cSrc, cSrcSize, DTable); } assert(args.ip[0] >= args.ilimit); HUF_decompress4X2_usingDTable_internal_bmi2_asm_loop(&args); /* note : op4 already verified within main loop */ assert(args.ip[0] >= iend); assert(args.ip[1] >= iend); assert(args.ip[2] >= iend); assert(args.ip[3] >= iend); assert(args.op[3] <= oend); (void)iend; /* finish bitStreams one by one */ { size_t const segmentSize = (dstSize+3) / 4; BYTE* segmentEnd = (BYTE*)dst; int i; for (i = 0; i < 4; ++i) { BIT_DStream_t bit; if (segmentSize <= (size_t)(oend - segmentEnd)) segmentEnd += segmentSize; else segmentEnd = oend; FORWARD_IF_ERROR(HUF_initRemainingDStream(&bit, &args, i, segmentEnd), "corruption"); args.op[i] += HUF_decodeStreamX2(args.op[i], &bit, segmentEnd, (HUF_DEltX2 const*)dt, HUF_DECODER_FAST_TABLELOG); if (args.op[i] != segmentEnd) return ERROR(corruption_detected); } } /* decoded size */ return dstSize; } #endif /* ZSTD_ENABLE_ASM_X86_64_BMI2 */ static size_t HUF_decompress4X2_usingDTable_internal(void* dst, size_t dstSize, void const* cSrc, size_t cSrcSize, HUF_DTable const* DTable, int bmi2) { … } HUF_DGEN(…) size_t HUF_decompress1X2_usingDTable( void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable) { … } 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) { … } size_t HUF_decompress4X2_usingDTable( void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable) { … } static size_t HUF_decompress4X2_DCtx_wksp_bmi2(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize, int bmi2) { … } 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) { … } #endif /* HUF_FORCE_DECOMPRESS_X1 */ /* ***********************************/ /* Universal decompression selectors */ /* ***********************************/ size_t HUF_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable) { … } size_t HUF_decompress4X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable) { … } #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_decompress4X_hufOnly_wksp(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize, void* workSpace, size_t wkspSize) { … } 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) { … } size_t HUF_decompress1X_usingDTable_bmi2(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, int bmi2) { … } #ifndef HUF_FORCE_DECOMPRESS_X2 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) { … } #endif size_t HUF_decompress4X_usingDTable_bmi2(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, int bmi2) { … } 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) { … }
Codebase Browser
linux