1741 lines · c
1/* ******************************************************************2 * huff0 huffman decoder,3 * part of Finite State Entropy library4 * Copyright (c) Yann Collet, Facebook, Inc.5 *6 * You can contact the author at :7 * - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy8 *9 * This source code is licensed under both the BSD-style license (found in the10 * LICENSE file in the root directory of this source tree) and the GPLv2 (found11 * in the COPYING file in the root directory of this source tree).12 * You may select, at your option, one of the above-listed licenses.13****************************************************************** */14 15/* **************************************************************16* Dependencies17****************************************************************/18#include "../common/zstd_deps.h" /* ZSTD_memcpy, ZSTD_memset */19#include "../common/compiler.h"20#include "../common/bitstream.h" /* BIT_* */21#include "../common/fse.h" /* to compress headers */22#define HUF_STATIC_LINKING_ONLY23#include "../common/huf.h"24#include "../common/error_private.h"25#include "../common/zstd_internal.h"26 27/* **************************************************************28* Constants29****************************************************************/30 31#define HUF_DECODER_FAST_TABLELOG 1132 33/* **************************************************************34* Macros35****************************************************************/36 37/* These two optional macros force the use one way or another of the two38 * Huffman decompression implementations. You can't force in both directions39 * at the same time.40 */41#if defined(HUF_FORCE_DECOMPRESS_X1) && \42 defined(HUF_FORCE_DECOMPRESS_X2)43#error "Cannot force the use of the X1 and X2 decoders at the same time!"44#endif45 46#if ZSTD_ENABLE_ASM_X86_64_BMI2 && DYNAMIC_BMI247# define HUF_ASM_X86_64_BMI2_ATTRS BMI2_TARGET_ATTRIBUTE48#else49# define HUF_ASM_X86_64_BMI2_ATTRS50#endif51 52#define HUF_EXTERN_C53#define HUF_ASM_DECL HUF_EXTERN_C54 55#if DYNAMIC_BMI2 || (ZSTD_ENABLE_ASM_X86_64_BMI2 && defined(__BMI2__))56# define HUF_NEED_BMI2_FUNCTION 157#else58# define HUF_NEED_BMI2_FUNCTION 059#endif60 61#if !(ZSTD_ENABLE_ASM_X86_64_BMI2 && defined(__BMI2__))62# define HUF_NEED_DEFAULT_FUNCTION 163#else64# define HUF_NEED_DEFAULT_FUNCTION 065#endif66 67/* **************************************************************68* Error Management69****************************************************************/70#define HUF_isError ERR_isError71 72 73/* **************************************************************74* Byte alignment for workSpace management75****************************************************************/76#define HUF_ALIGN(x, a) HUF_ALIGN_MASK((x), (a) - 1)77#define HUF_ALIGN_MASK(x, mask) (((x) + (mask)) & ~(mask))78 79 80/* **************************************************************81* BMI2 Variant Wrappers82****************************************************************/83#if DYNAMIC_BMI284 85#define HUF_DGEN(fn) \86 \87 static size_t fn##_default( \88 void* dst, size_t dstSize, \89 const void* cSrc, size_t cSrcSize, \90 const HUF_DTable* DTable) \91 { \92 return fn##_body(dst, dstSize, cSrc, cSrcSize, DTable); \93 } \94 \95 static BMI2_TARGET_ATTRIBUTE size_t fn##_bmi2( \96 void* dst, size_t dstSize, \97 const void* cSrc, size_t cSrcSize, \98 const HUF_DTable* DTable) \99 { \100 return fn##_body(dst, dstSize, cSrc, cSrcSize, DTable); \101 } \102 \103 static size_t fn(void* dst, size_t dstSize, void const* cSrc, \104 size_t cSrcSize, HUF_DTable const* DTable, int bmi2) \105 { \106 if (bmi2) { \107 return fn##_bmi2(dst, dstSize, cSrc, cSrcSize, DTable); \108 } \109 return fn##_default(dst, dstSize, cSrc, cSrcSize, DTable); \110 }111 112#else113 114#define HUF_DGEN(fn) \115 static size_t fn(void* dst, size_t dstSize, void const* cSrc, \116 size_t cSrcSize, HUF_DTable const* DTable, int bmi2) \117 { \118 (void)bmi2; \119 return fn##_body(dst, dstSize, cSrc, cSrcSize, DTable); \120 }121 122#endif123 124 125/*-***************************/126/* generic DTableDesc */127/*-***************************/128typedef struct { BYTE maxTableLog; BYTE tableType; BYTE tableLog; BYTE reserved; } DTableDesc;129 130static DTableDesc HUF_getDTableDesc(const HUF_DTable* table)131{132 DTableDesc dtd;133 ZSTD_memcpy(&dtd, table, sizeof(dtd));134 return dtd;135}136 137#if ZSTD_ENABLE_ASM_X86_64_BMI2138 139static size_t HUF_initDStream(BYTE const* ip) {140 BYTE const lastByte = ip[7];141 size_t const bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;142 size_t const value = MEM_readLEST(ip) | 1;143 assert(bitsConsumed <= 8);144 return value << bitsConsumed;145}146typedef struct {147 BYTE const* ip[4];148 BYTE* op[4];149 U64 bits[4];150 void const* dt;151 BYTE const* ilimit;152 BYTE* oend;153 BYTE const* iend[4];154} HUF_DecompressAsmArgs;155 156/*157 * Initializes args for the asm decoding loop.158 * @returns 0 on success159 * 1 if the fallback implementation should be used.160 * Or an error code on failure.161 */162static size_t HUF_DecompressAsmArgs_init(HUF_DecompressAsmArgs* args, void* dst, size_t dstSize, void const* src, size_t srcSize, const HUF_DTable* DTable)163{164 void const* dt = DTable + 1;165 U32 const dtLog = HUF_getDTableDesc(DTable).tableLog;166 167 const BYTE* const ilimit = (const BYTE*)src + 6 + 8;168 169 BYTE* const oend = (BYTE*)dst + dstSize;170 171 /* The following condition is false on x32 platform,172 * but HUF_asm is not compatible with this ABI */173 if (!(MEM_isLittleEndian() && !MEM_32bits())) return 1;174 175 /* strict minimum : jump table + 1 byte per stream */176 if (srcSize < 10)177 return ERROR(corruption_detected);178 179 /* Must have at least 8 bytes per stream because we don't handle initializing smaller bit containers.180 * If table log is not correct at this point, fallback to the old decoder.181 * On small inputs we don't have enough data to trigger the fast loop, so use the old decoder.182 */183 if (dtLog != HUF_DECODER_FAST_TABLELOG)184 return 1;185 186 /* Read the jump table. */187 {188 const BYTE* const istart = (const BYTE*)src;189 size_t const length1 = MEM_readLE16(istart);190 size_t const length2 = MEM_readLE16(istart+2);191 size_t const length3 = MEM_readLE16(istart+4);192 size_t const length4 = srcSize - (length1 + length2 + length3 + 6);193 args->iend[0] = istart + 6; /* jumpTable */194 args->iend[1] = args->iend[0] + length1;195 args->iend[2] = args->iend[1] + length2;196 args->iend[3] = args->iend[2] + length3;197 198 /* HUF_initDStream() requires this, and this small of an input199 * won't benefit from the ASM loop anyways.200 * length1 must be >= 16 so that ip[0] >= ilimit before the loop201 * starts.202 */203 if (length1 < 16 || length2 < 8 || length3 < 8 || length4 < 8)204 return 1;205 if (length4 > srcSize) return ERROR(corruption_detected); /* overflow */206 }207 /* ip[] contains the position that is currently loaded into bits[]. */208 args->ip[0] = args->iend[1] - sizeof(U64);209 args->ip[1] = args->iend[2] - sizeof(U64);210 args->ip[2] = args->iend[3] - sizeof(U64);211 args->ip[3] = (BYTE const*)src + srcSize - sizeof(U64);212 213 /* op[] contains the output pointers. */214 args->op[0] = (BYTE*)dst;215 args->op[1] = args->op[0] + (dstSize+3)/4;216 args->op[2] = args->op[1] + (dstSize+3)/4;217 args->op[3] = args->op[2] + (dstSize+3)/4;218 219 /* No point to call the ASM loop for tiny outputs. */220 if (args->op[3] >= oend)221 return 1;222 223 /* bits[] is the bit container.224 * It is read from the MSB down to the LSB.225 * It is shifted left as it is read, and zeros are226 * shifted in. After the lowest valid bit a 1 is227 * set, so that CountTrailingZeros(bits[]) can be used228 * to count how many bits we've consumed.229 */230 args->bits[0] = HUF_initDStream(args->ip[0]);231 args->bits[1] = HUF_initDStream(args->ip[1]);232 args->bits[2] = HUF_initDStream(args->ip[2]);233 args->bits[3] = HUF_initDStream(args->ip[3]);234 235 /* If ip[] >= ilimit, it is guaranteed to be safe to236 * reload bits[]. It may be beyond its section, but is237 * guaranteed to be valid (>= istart).238 */239 args->ilimit = ilimit;240 241 args->oend = oend;242 args->dt = dt;243 244 return 0;245}246 247static size_t HUF_initRemainingDStream(BIT_DStream_t* bit, HUF_DecompressAsmArgs const* args, int stream, BYTE* segmentEnd)248{249 /* Validate that we haven't overwritten. */250 if (args->op[stream] > segmentEnd)251 return ERROR(corruption_detected);252 /* Validate that we haven't read beyond iend[].253 * Note that ip[] may be < iend[] because the MSB is254 * the next bit to read, and we may have consumed 100%255 * of the stream, so down to iend[i] - 8 is valid.256 */257 if (args->ip[stream] < args->iend[stream] - 8)258 return ERROR(corruption_detected);259 260 /* Construct the BIT_DStream_t. */261 bit->bitContainer = MEM_readLE64(args->ip[stream]);262 bit->bitsConsumed = ZSTD_countTrailingZeros((size_t)args->bits[stream]);263 bit->start = (const char*)args->iend[0];264 bit->limitPtr = bit->start + sizeof(size_t);265 bit->ptr = (const char*)args->ip[stream];266 267 return 0;268}269#endif270 271 272#ifndef HUF_FORCE_DECOMPRESS_X2273 274/*-***************************/275/* single-symbol decoding */276/*-***************************/277typedef struct { BYTE nbBits; BYTE byte; } HUF_DEltX1; /* single-symbol decoding */278 279/*280 * Packs 4 HUF_DEltX1 structs into a U64. This is used to lay down 4 entries at281 * a time.282 */283static U64 HUF_DEltX1_set4(BYTE symbol, BYTE nbBits) {284 U64 D4;285 if (MEM_isLittleEndian()) {286 D4 = (symbol << 8) + nbBits;287 } else {288 D4 = symbol + (nbBits << 8);289 }290 D4 *= 0x0001000100010001ULL;291 return D4;292}293 294/*295 * Increase the tableLog to targetTableLog and rescales the stats.296 * If tableLog > targetTableLog this is a no-op.297 * @returns New tableLog298 */299static U32 HUF_rescaleStats(BYTE* huffWeight, U32* rankVal, U32 nbSymbols, U32 tableLog, U32 targetTableLog)300{301 if (tableLog > targetTableLog)302 return tableLog;303 if (tableLog < targetTableLog) {304 U32 const scale = targetTableLog - tableLog;305 U32 s;306 /* Increase the weight for all non-zero probability symbols by scale. */307 for (s = 0; s < nbSymbols; ++s) {308 huffWeight[s] += (BYTE)((huffWeight[s] == 0) ? 0 : scale);309 }310 /* Update rankVal to reflect the new weights.311 * All weights except 0 get moved to weight + scale.312 * Weights [1, scale] are empty.313 */314 for (s = targetTableLog; s > scale; --s) {315 rankVal[s] = rankVal[s - scale];316 }317 for (s = scale; s > 0; --s) {318 rankVal[s] = 0;319 }320 }321 return targetTableLog;322}323 324typedef struct {325 U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1];326 U32 rankStart[HUF_TABLELOG_ABSOLUTEMAX + 1];327 U32 statsWksp[HUF_READ_STATS_WORKSPACE_SIZE_U32];328 BYTE symbols[HUF_SYMBOLVALUE_MAX + 1];329 BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1];330} HUF_ReadDTableX1_Workspace;331 332 333size_t HUF_readDTableX1_wksp(HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize)334{335 return HUF_readDTableX1_wksp_bmi2(DTable, src, srcSize, workSpace, wkspSize, /* bmi2 */ 0);336}337 338size_t HUF_readDTableX1_wksp_bmi2(HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize, int bmi2)339{340 U32 tableLog = 0;341 U32 nbSymbols = 0;342 size_t iSize;343 void* const dtPtr = DTable + 1;344 HUF_DEltX1* const dt = (HUF_DEltX1*)dtPtr;345 HUF_ReadDTableX1_Workspace* wksp = (HUF_ReadDTableX1_Workspace*)workSpace;346 347 DEBUG_STATIC_ASSERT(HUF_DECOMPRESS_WORKSPACE_SIZE >= sizeof(*wksp));348 if (sizeof(*wksp) > wkspSize) return ERROR(tableLog_tooLarge);349 350 DEBUG_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUF_DTable));351 /* ZSTD_memset(huffWeight, 0, sizeof(huffWeight)); */ /* is not necessary, even though some analyzer complain ... */352 353 iSize = HUF_readStats_wksp(wksp->huffWeight, HUF_SYMBOLVALUE_MAX + 1, wksp->rankVal, &nbSymbols, &tableLog, src, srcSize, wksp->statsWksp, sizeof(wksp->statsWksp), bmi2);354 if (HUF_isError(iSize)) return iSize;355 356 357 /* Table header */358 { DTableDesc dtd = HUF_getDTableDesc(DTable);359 U32 const maxTableLog = dtd.maxTableLog + 1;360 U32 const targetTableLog = MIN(maxTableLog, HUF_DECODER_FAST_TABLELOG);361 tableLog = HUF_rescaleStats(wksp->huffWeight, wksp->rankVal, nbSymbols, tableLog, targetTableLog);362 if (tableLog > (U32)(dtd.maxTableLog+1)) return ERROR(tableLog_tooLarge); /* DTable too small, Huffman tree cannot fit in */363 dtd.tableType = 0;364 dtd.tableLog = (BYTE)tableLog;365 ZSTD_memcpy(DTable, &dtd, sizeof(dtd));366 }367 368 /* Compute symbols and rankStart given rankVal:369 *370 * rankVal already contains the number of values of each weight.371 *372 * symbols contains the symbols ordered by weight. First are the rankVal[0]373 * weight 0 symbols, followed by the rankVal[1] weight 1 symbols, and so on.374 * symbols[0] is filled (but unused) to avoid a branch.375 *376 * rankStart contains the offset where each rank belongs in the DTable.377 * rankStart[0] is not filled because there are no entries in the table for378 * weight 0.379 */380 {381 int n;382 int nextRankStart = 0;383 int const unroll = 4;384 int const nLimit = (int)nbSymbols - unroll + 1;385 for (n=0; n<(int)tableLog+1; n++) {386 U32 const curr = nextRankStart;387 nextRankStart += wksp->rankVal[n];388 wksp->rankStart[n] = curr;389 }390 for (n=0; n < nLimit; n += unroll) {391 int u;392 for (u=0; u < unroll; ++u) {393 size_t const w = wksp->huffWeight[n+u];394 wksp->symbols[wksp->rankStart[w]++] = (BYTE)(n+u);395 }396 }397 for (; n < (int)nbSymbols; ++n) {398 size_t const w = wksp->huffWeight[n];399 wksp->symbols[wksp->rankStart[w]++] = (BYTE)n;400 }401 }402 403 /* fill DTable404 * We fill all entries of each weight in order.405 * That way length is a constant for each iteration of the outer loop.406 * We can switch based on the length to a different inner loop which is407 * optimized for that particular case.408 */409 {410 U32 w;411 int symbol=wksp->rankVal[0];412 int rankStart=0;413 for (w=1; w<tableLog+1; ++w) {414 int const symbolCount = wksp->rankVal[w];415 int const length = (1 << w) >> 1;416 int uStart = rankStart;417 BYTE const nbBits = (BYTE)(tableLog + 1 - w);418 int s;419 int u;420 switch (length) {421 case 1:422 for (s=0; s<symbolCount; ++s) {423 HUF_DEltX1 D;424 D.byte = wksp->symbols[symbol + s];425 D.nbBits = nbBits;426 dt[uStart] = D;427 uStart += 1;428 }429 break;430 case 2:431 for (s=0; s<symbolCount; ++s) {432 HUF_DEltX1 D;433 D.byte = wksp->symbols[symbol + s];434 D.nbBits = nbBits;435 dt[uStart+0] = D;436 dt[uStart+1] = D;437 uStart += 2;438 }439 break;440 case 4:441 for (s=0; s<symbolCount; ++s) {442 U64 const D4 = HUF_DEltX1_set4(wksp->symbols[symbol + s], nbBits);443 MEM_write64(dt + uStart, D4);444 uStart += 4;445 }446 break;447 case 8:448 for (s=0; s<symbolCount; ++s) {449 U64 const D4 = HUF_DEltX1_set4(wksp->symbols[symbol + s], nbBits);450 MEM_write64(dt + uStart, D4);451 MEM_write64(dt + uStart + 4, D4);452 uStart += 8;453 }454 break;455 default:456 for (s=0; s<symbolCount; ++s) {457 U64 const D4 = HUF_DEltX1_set4(wksp->symbols[symbol + s], nbBits);458 for (u=0; u < length; u += 16) {459 MEM_write64(dt + uStart + u + 0, D4);460 MEM_write64(dt + uStart + u + 4, D4);461 MEM_write64(dt + uStart + u + 8, D4);462 MEM_write64(dt + uStart + u + 12, D4);463 }464 assert(u == length);465 uStart += length;466 }467 break;468 }469 symbol += symbolCount;470 rankStart += symbolCount * length;471 }472 }473 return iSize;474}475 476FORCE_INLINE_TEMPLATE BYTE477HUF_decodeSymbolX1(BIT_DStream_t* Dstream, const HUF_DEltX1* dt, const U32 dtLog)478{479 size_t const val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */480 BYTE const c = dt[val].byte;481 BIT_skipBits(Dstream, dt[val].nbBits);482 return c;483}484 485#define HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr) \486 *ptr++ = HUF_decodeSymbolX1(DStreamPtr, dt, dtLog)487 488#define HUF_DECODE_SYMBOLX1_1(ptr, DStreamPtr) \489 if (MEM_64bits() || (HUF_TABLELOG_MAX<=12)) \490 HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr)491 492#define HUF_DECODE_SYMBOLX1_2(ptr, DStreamPtr) \493 if (MEM_64bits()) \494 HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr)495 496HINT_INLINE size_t497HUF_decodeStreamX1(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX1* const dt, const U32 dtLog)498{499 BYTE* const pStart = p;500 501 /* up to 4 symbols at a time */502 if ((pEnd - p) > 3) {503 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p < pEnd-3)) {504 HUF_DECODE_SYMBOLX1_2(p, bitDPtr);505 HUF_DECODE_SYMBOLX1_1(p, bitDPtr);506 HUF_DECODE_SYMBOLX1_2(p, bitDPtr);507 HUF_DECODE_SYMBOLX1_0(p, bitDPtr);508 }509 } else {510 BIT_reloadDStream(bitDPtr);511 }512 513 /* [0-3] symbols remaining */514 if (MEM_32bits())515 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p < pEnd))516 HUF_DECODE_SYMBOLX1_0(p, bitDPtr);517 518 /* no more data to retrieve from bitstream, no need to reload */519 while (p < pEnd)520 HUF_DECODE_SYMBOLX1_0(p, bitDPtr);521 522 return pEnd-pStart;523}524 525FORCE_INLINE_TEMPLATE size_t526HUF_decompress1X1_usingDTable_internal_body(527 void* dst, size_t dstSize,528 const void* cSrc, size_t cSrcSize,529 const HUF_DTable* DTable)530{531 BYTE* op = (BYTE*)dst;532 BYTE* const oend = op + dstSize;533 const void* dtPtr = DTable + 1;534 const HUF_DEltX1* const dt = (const HUF_DEltX1*)dtPtr;535 BIT_DStream_t bitD;536 DTableDesc const dtd = HUF_getDTableDesc(DTable);537 U32 const dtLog = dtd.tableLog;538 539 CHECK_F( BIT_initDStream(&bitD, cSrc, cSrcSize) );540 541 HUF_decodeStreamX1(op, &bitD, oend, dt, dtLog);542 543 if (!BIT_endOfDStream(&bitD)) return ERROR(corruption_detected);544 545 return dstSize;546}547 548FORCE_INLINE_TEMPLATE size_t549HUF_decompress4X1_usingDTable_internal_body(550 void* dst, size_t dstSize,551 const void* cSrc, size_t cSrcSize,552 const HUF_DTable* DTable)553{554 /* Check */555 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */556 557 { const BYTE* const istart = (const BYTE*) cSrc;558 BYTE* const ostart = (BYTE*) dst;559 BYTE* const oend = ostart + dstSize;560 BYTE* const olimit = oend - 3;561 const void* const dtPtr = DTable + 1;562 const HUF_DEltX1* const dt = (const HUF_DEltX1*)dtPtr;563 564 /* Init */565 BIT_DStream_t bitD1;566 BIT_DStream_t bitD2;567 BIT_DStream_t bitD3;568 BIT_DStream_t bitD4;569 size_t const length1 = MEM_readLE16(istart);570 size_t const length2 = MEM_readLE16(istart+2);571 size_t const length3 = MEM_readLE16(istart+4);572 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);573 const BYTE* const istart1 = istart + 6; /* jumpTable */574 const BYTE* const istart2 = istart1 + length1;575 const BYTE* const istart3 = istart2 + length2;576 const BYTE* const istart4 = istart3 + length3;577 const size_t segmentSize = (dstSize+3) / 4;578 BYTE* const opStart2 = ostart + segmentSize;579 BYTE* const opStart3 = opStart2 + segmentSize;580 BYTE* const opStart4 = opStart3 + segmentSize;581 BYTE* op1 = ostart;582 BYTE* op2 = opStart2;583 BYTE* op3 = opStart3;584 BYTE* op4 = opStart4;585 DTableDesc const dtd = HUF_getDTableDesc(DTable);586 U32 const dtLog = dtd.tableLog;587 U32 endSignal = 1;588 589 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */590 if (opStart4 > oend) return ERROR(corruption_detected); /* overflow */591 CHECK_F( BIT_initDStream(&bitD1, istart1, length1) );592 CHECK_F( BIT_initDStream(&bitD2, istart2, length2) );593 CHECK_F( BIT_initDStream(&bitD3, istart3, length3) );594 CHECK_F( BIT_initDStream(&bitD4, istart4, length4) );595 596 /* up to 16 symbols per loop (4 symbols per stream) in 64-bit mode */597 if ((size_t)(oend - op4) >= sizeof(size_t)) {598 for ( ; (endSignal) & (op4 < olimit) ; ) {599 HUF_DECODE_SYMBOLX1_2(op1, &bitD1);600 HUF_DECODE_SYMBOLX1_2(op2, &bitD2);601 HUF_DECODE_SYMBOLX1_2(op3, &bitD3);602 HUF_DECODE_SYMBOLX1_2(op4, &bitD4);603 HUF_DECODE_SYMBOLX1_1(op1, &bitD1);604 HUF_DECODE_SYMBOLX1_1(op2, &bitD2);605 HUF_DECODE_SYMBOLX1_1(op3, &bitD3);606 HUF_DECODE_SYMBOLX1_1(op4, &bitD4);607 HUF_DECODE_SYMBOLX1_2(op1, &bitD1);608 HUF_DECODE_SYMBOLX1_2(op2, &bitD2);609 HUF_DECODE_SYMBOLX1_2(op3, &bitD3);610 HUF_DECODE_SYMBOLX1_2(op4, &bitD4);611 HUF_DECODE_SYMBOLX1_0(op1, &bitD1);612 HUF_DECODE_SYMBOLX1_0(op2, &bitD2);613 HUF_DECODE_SYMBOLX1_0(op3, &bitD3);614 HUF_DECODE_SYMBOLX1_0(op4, &bitD4);615 endSignal &= BIT_reloadDStreamFast(&bitD1) == BIT_DStream_unfinished;616 endSignal &= BIT_reloadDStreamFast(&bitD2) == BIT_DStream_unfinished;617 endSignal &= BIT_reloadDStreamFast(&bitD3) == BIT_DStream_unfinished;618 endSignal &= BIT_reloadDStreamFast(&bitD4) == BIT_DStream_unfinished;619 }620 }621 622 /* check corruption */623 /* note : should not be necessary : op# advance in lock step, and we control op4.624 * but curiously, binary generated by gcc 7.2 & 7.3 with -mbmi2 runs faster when >=1 test is present */625 if (op1 > opStart2) return ERROR(corruption_detected);626 if (op2 > opStart3) return ERROR(corruption_detected);627 if (op3 > opStart4) return ERROR(corruption_detected);628 /* note : op4 supposed already verified within main loop */629 630 /* finish bitStreams one by one */631 HUF_decodeStreamX1(op1, &bitD1, opStart2, dt, dtLog);632 HUF_decodeStreamX1(op2, &bitD2, opStart3, dt, dtLog);633 HUF_decodeStreamX1(op3, &bitD3, opStart4, dt, dtLog);634 HUF_decodeStreamX1(op4, &bitD4, oend, dt, dtLog);635 636 /* check */637 { U32 const endCheck = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);638 if (!endCheck) return ERROR(corruption_detected); }639 640 /* decoded size */641 return dstSize;642 }643}644 645#if HUF_NEED_BMI2_FUNCTION646static BMI2_TARGET_ATTRIBUTE647size_t HUF_decompress4X1_usingDTable_internal_bmi2(void* dst, size_t dstSize, void const* cSrc,648 size_t cSrcSize, HUF_DTable const* DTable) {649 return HUF_decompress4X1_usingDTable_internal_body(dst, dstSize, cSrc, cSrcSize, DTable);650}651#endif652 653#if HUF_NEED_DEFAULT_FUNCTION654static655size_t HUF_decompress4X1_usingDTable_internal_default(void* dst, size_t dstSize, void const* cSrc,656 size_t cSrcSize, HUF_DTable const* DTable) {657 return HUF_decompress4X1_usingDTable_internal_body(dst, dstSize, cSrc, cSrcSize, DTable);658}659#endif660 661#if ZSTD_ENABLE_ASM_X86_64_BMI2662 663HUF_ASM_DECL void HUF_decompress4X1_usingDTable_internal_bmi2_asm_loop(HUF_DecompressAsmArgs* args) ZSTDLIB_HIDDEN;664 665static HUF_ASM_X86_64_BMI2_ATTRS666size_t667HUF_decompress4X1_usingDTable_internal_bmi2_asm(668 void* dst, size_t dstSize,669 const void* cSrc, size_t cSrcSize,670 const HUF_DTable* DTable)671{672 void const* dt = DTable + 1;673 const BYTE* const iend = (const BYTE*)cSrc + 6;674 BYTE* const oend = (BYTE*)dst + dstSize;675 HUF_DecompressAsmArgs args;676 {677 size_t const ret = HUF_DecompressAsmArgs_init(&args, dst, dstSize, cSrc, cSrcSize, DTable);678 FORWARD_IF_ERROR(ret, "Failed to init asm args");679 if (ret != 0)680 return HUF_decompress4X1_usingDTable_internal_bmi2(dst, dstSize, cSrc, cSrcSize, DTable);681 }682 683 assert(args.ip[0] >= args.ilimit);684 HUF_decompress4X1_usingDTable_internal_bmi2_asm_loop(&args);685 686 /* Our loop guarantees that ip[] >= ilimit and that we haven't687 * overwritten any op[].688 */689 assert(args.ip[0] >= iend);690 assert(args.ip[1] >= iend);691 assert(args.ip[2] >= iend);692 assert(args.ip[3] >= iend);693 assert(args.op[3] <= oend);694 (void)iend;695 696 /* finish bit streams one by one. */697 {698 size_t const segmentSize = (dstSize+3) / 4;699 BYTE* segmentEnd = (BYTE*)dst;700 int i;701 for (i = 0; i < 4; ++i) {702 BIT_DStream_t bit;703 if (segmentSize <= (size_t)(oend - segmentEnd))704 segmentEnd += segmentSize;705 else706 segmentEnd = oend;707 FORWARD_IF_ERROR(HUF_initRemainingDStream(&bit, &args, i, segmentEnd), "corruption");708 /* Decompress and validate that we've produced exactly the expected length. */709 args.op[i] += HUF_decodeStreamX1(args.op[i], &bit, segmentEnd, (HUF_DEltX1 const*)dt, HUF_DECODER_FAST_TABLELOG);710 if (args.op[i] != segmentEnd) return ERROR(corruption_detected);711 }712 }713 714 /* decoded size */715 return dstSize;716}717#endif /* ZSTD_ENABLE_ASM_X86_64_BMI2 */718 719typedef size_t (*HUF_decompress_usingDTable_t)(void *dst, size_t dstSize,720 const void *cSrc,721 size_t cSrcSize,722 const HUF_DTable *DTable);723 724HUF_DGEN(HUF_decompress1X1_usingDTable_internal)725 726static size_t HUF_decompress4X1_usingDTable_internal(void* dst, size_t dstSize, void const* cSrc,727 size_t cSrcSize, HUF_DTable const* DTable, int bmi2)728{729#if DYNAMIC_BMI2730 if (bmi2) {731# if ZSTD_ENABLE_ASM_X86_64_BMI2732 return HUF_decompress4X1_usingDTable_internal_bmi2_asm(dst, dstSize, cSrc, cSrcSize, DTable);733# else734 return HUF_decompress4X1_usingDTable_internal_bmi2(dst, dstSize, cSrc, cSrcSize, DTable);735# endif736 }737#else738 (void)bmi2;739#endif740 741#if ZSTD_ENABLE_ASM_X86_64_BMI2 && defined(__BMI2__)742 return HUF_decompress4X1_usingDTable_internal_bmi2_asm(dst, dstSize, cSrc, cSrcSize, DTable);743#else744 return HUF_decompress4X1_usingDTable_internal_default(dst, dstSize, cSrc, cSrcSize, DTable);745#endif746}747 748 749size_t HUF_decompress1X1_usingDTable(750 void* dst, size_t dstSize,751 const void* cSrc, size_t cSrcSize,752 const HUF_DTable* DTable)753{754 DTableDesc dtd = HUF_getDTableDesc(DTable);755 if (dtd.tableType != 0) return ERROR(GENERIC);756 return HUF_decompress1X1_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);757}758 759size_t HUF_decompress1X1_DCtx_wksp(HUF_DTable* DCtx, void* dst, size_t dstSize,760 const void* cSrc, size_t cSrcSize,761 void* workSpace, size_t wkspSize)762{763 const BYTE* ip = (const BYTE*) cSrc;764 765 size_t const hSize = HUF_readDTableX1_wksp(DCtx, cSrc, cSrcSize, workSpace, wkspSize);766 if (HUF_isError(hSize)) return hSize;767 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);768 ip += hSize; cSrcSize -= hSize;769 770 return HUF_decompress1X1_usingDTable_internal(dst, dstSize, ip, cSrcSize, DCtx, /* bmi2 */ 0);771}772 773 774size_t HUF_decompress4X1_usingDTable(775 void* dst, size_t dstSize,776 const void* cSrc, size_t cSrcSize,777 const HUF_DTable* DTable)778{779 DTableDesc dtd = HUF_getDTableDesc(DTable);780 if (dtd.tableType != 0) return ERROR(GENERIC);781 return HUF_decompress4X1_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);782}783 784static size_t HUF_decompress4X1_DCtx_wksp_bmi2(HUF_DTable* dctx, void* dst, size_t dstSize,785 const void* cSrc, size_t cSrcSize,786 void* workSpace, size_t wkspSize, int bmi2)787{788 const BYTE* ip = (const BYTE*) cSrc;789 790 size_t const hSize = HUF_readDTableX1_wksp_bmi2(dctx, cSrc, cSrcSize, workSpace, wkspSize, bmi2);791 if (HUF_isError(hSize)) return hSize;792 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);793 ip += hSize; cSrcSize -= hSize;794 795 return HUF_decompress4X1_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx, bmi2);796}797 798size_t HUF_decompress4X1_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize,799 const void* cSrc, size_t cSrcSize,800 void* workSpace, size_t wkspSize)801{802 return HUF_decompress4X1_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, 0);803}804 805 806#endif /* HUF_FORCE_DECOMPRESS_X2 */807 808 809#ifndef HUF_FORCE_DECOMPRESS_X1810 811/* *************************/812/* double-symbols decoding */813/* *************************/814 815typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX2; /* double-symbols decoding */816typedef struct { BYTE symbol; } sortedSymbol_t;817typedef U32 rankValCol_t[HUF_TABLELOG_MAX + 1];818typedef rankValCol_t rankVal_t[HUF_TABLELOG_MAX];819 820/*821 * Constructs a HUF_DEltX2 in a U32.822 */823static U32 HUF_buildDEltX2U32(U32 symbol, U32 nbBits, U32 baseSeq, int level)824{825 U32 seq;826 DEBUG_STATIC_ASSERT(offsetof(HUF_DEltX2, sequence) == 0);827 DEBUG_STATIC_ASSERT(offsetof(HUF_DEltX2, nbBits) == 2);828 DEBUG_STATIC_ASSERT(offsetof(HUF_DEltX2, length) == 3);829 DEBUG_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U32));830 if (MEM_isLittleEndian()) {831 seq = level == 1 ? symbol : (baseSeq + (symbol << 8));832 return seq + (nbBits << 16) + ((U32)level << 24);833 } else {834 seq = level == 1 ? (symbol << 8) : ((baseSeq << 8) + symbol);835 return (seq << 16) + (nbBits << 8) + (U32)level;836 }837}838 839/*840 * Constructs a HUF_DEltX2.841 */842static HUF_DEltX2 HUF_buildDEltX2(U32 symbol, U32 nbBits, U32 baseSeq, int level)843{844 HUF_DEltX2 DElt;845 U32 const val = HUF_buildDEltX2U32(symbol, nbBits, baseSeq, level);846 DEBUG_STATIC_ASSERT(sizeof(DElt) == sizeof(val));847 ZSTD_memcpy(&DElt, &val, sizeof(val));848 return DElt;849}850 851/*852 * Constructs 2 HUF_DEltX2s and packs them into a U64.853 */854static U64 HUF_buildDEltX2U64(U32 symbol, U32 nbBits, U16 baseSeq, int level)855{856 U32 DElt = HUF_buildDEltX2U32(symbol, nbBits, baseSeq, level);857 return (U64)DElt + ((U64)DElt << 32);858}859 860/*861 * Fills the DTable rank with all the symbols from [begin, end) that are each862 * nbBits long.863 *864 * @param DTableRank The start of the rank in the DTable.865 * @param begin The first symbol to fill (inclusive).866 * @param end The last symbol to fill (exclusive).867 * @param nbBits Each symbol is nbBits long.868 * @param tableLog The table log.869 * @param baseSeq If level == 1 { 0 } else { the first level symbol }870 * @param level The level in the table. Must be 1 or 2.871 */872static void HUF_fillDTableX2ForWeight(873 HUF_DEltX2* DTableRank,874 sortedSymbol_t const* begin, sortedSymbol_t const* end,875 U32 nbBits, U32 tableLog,876 U16 baseSeq, int const level)877{878 U32 const length = 1U << ((tableLog - nbBits) & 0x1F /* quiet static-analyzer */);879 const sortedSymbol_t* ptr;880 assert(level >= 1 && level <= 2);881 switch (length) {882 case 1:883 for (ptr = begin; ptr != end; ++ptr) {884 HUF_DEltX2 const DElt = HUF_buildDEltX2(ptr->symbol, nbBits, baseSeq, level);885 *DTableRank++ = DElt;886 }887 break;888 case 2:889 for (ptr = begin; ptr != end; ++ptr) {890 HUF_DEltX2 const DElt = HUF_buildDEltX2(ptr->symbol, nbBits, baseSeq, level);891 DTableRank[0] = DElt;892 DTableRank[1] = DElt;893 DTableRank += 2;894 }895 break;896 case 4:897 for (ptr = begin; ptr != end; ++ptr) {898 U64 const DEltX2 = HUF_buildDEltX2U64(ptr->symbol, nbBits, baseSeq, level);899 ZSTD_memcpy(DTableRank + 0, &DEltX2, sizeof(DEltX2));900 ZSTD_memcpy(DTableRank + 2, &DEltX2, sizeof(DEltX2));901 DTableRank += 4;902 }903 break;904 case 8:905 for (ptr = begin; ptr != end; ++ptr) {906 U64 const DEltX2 = HUF_buildDEltX2U64(ptr->symbol, nbBits, baseSeq, level);907 ZSTD_memcpy(DTableRank + 0, &DEltX2, sizeof(DEltX2));908 ZSTD_memcpy(DTableRank + 2, &DEltX2, sizeof(DEltX2));909 ZSTD_memcpy(DTableRank + 4, &DEltX2, sizeof(DEltX2));910 ZSTD_memcpy(DTableRank + 6, &DEltX2, sizeof(DEltX2));911 DTableRank += 8;912 }913 break;914 default:915 for (ptr = begin; ptr != end; ++ptr) {916 U64 const DEltX2 = HUF_buildDEltX2U64(ptr->symbol, nbBits, baseSeq, level);917 HUF_DEltX2* const DTableRankEnd = DTableRank + length;918 for (; DTableRank != DTableRankEnd; DTableRank += 8) {919 ZSTD_memcpy(DTableRank + 0, &DEltX2, sizeof(DEltX2));920 ZSTD_memcpy(DTableRank + 2, &DEltX2, sizeof(DEltX2));921 ZSTD_memcpy(DTableRank + 4, &DEltX2, sizeof(DEltX2));922 ZSTD_memcpy(DTableRank + 6, &DEltX2, sizeof(DEltX2));923 }924 }925 break;926 }927}928 929/* HUF_fillDTableX2Level2() :930 * `rankValOrigin` must be a table of at least (HUF_TABLELOG_MAX + 1) U32 */931static void HUF_fillDTableX2Level2(HUF_DEltX2* DTable, U32 targetLog, const U32 consumedBits,932 const U32* rankVal, const int minWeight, const int maxWeight1,933 const sortedSymbol_t* sortedSymbols, U32 const* rankStart,934 U32 nbBitsBaseline, U16 baseSeq)935{936 /* Fill skipped values (all positions up to rankVal[minWeight]).937 * These are positions only get a single symbol because the combined weight938 * is too large.939 */940 if (minWeight>1) {941 U32 const length = 1U << ((targetLog - consumedBits) & 0x1F /* quiet static-analyzer */);942 U64 const DEltX2 = HUF_buildDEltX2U64(baseSeq, consumedBits, /* baseSeq */ 0, /* level */ 1);943 int const skipSize = rankVal[minWeight];944 assert(length > 1);945 assert((U32)skipSize < length);946 switch (length) {947 case 2:948 assert(skipSize == 1);949 ZSTD_memcpy(DTable, &DEltX2, sizeof(DEltX2));950 break;951 case 4:952 assert(skipSize <= 4);953 ZSTD_memcpy(DTable + 0, &DEltX2, sizeof(DEltX2));954 ZSTD_memcpy(DTable + 2, &DEltX2, sizeof(DEltX2));955 break;956 default:957 {958 int i;959 for (i = 0; i < skipSize; i += 8) {960 ZSTD_memcpy(DTable + i + 0, &DEltX2, sizeof(DEltX2));961 ZSTD_memcpy(DTable + i + 2, &DEltX2, sizeof(DEltX2));962 ZSTD_memcpy(DTable + i + 4, &DEltX2, sizeof(DEltX2));963 ZSTD_memcpy(DTable + i + 6, &DEltX2, sizeof(DEltX2));964 }965 }966 }967 }968 969 /* Fill each of the second level symbols by weight. */970 {971 int w;972 for (w = minWeight; w < maxWeight1; ++w) {973 int const begin = rankStart[w];974 int const end = rankStart[w+1];975 U32 const nbBits = nbBitsBaseline - w;976 U32 const totalBits = nbBits + consumedBits;977 HUF_fillDTableX2ForWeight(978 DTable + rankVal[w],979 sortedSymbols + begin, sortedSymbols + end,980 totalBits, targetLog,981 baseSeq, /* level */ 2);982 }983 }984}985 986static void HUF_fillDTableX2(HUF_DEltX2* DTable, const U32 targetLog,987 const sortedSymbol_t* sortedList,988 const U32* rankStart, rankValCol_t *rankValOrigin, const U32 maxWeight,989 const U32 nbBitsBaseline)990{991 U32* const rankVal = rankValOrigin[0];992 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */993 const U32 minBits = nbBitsBaseline - maxWeight;994 int w;995 int const wEnd = (int)maxWeight + 1;996 997 /* Fill DTable in order of weight. */998 for (w = 1; w < wEnd; ++w) {999 int const begin = (int)rankStart[w];1000 int const end = (int)rankStart[w+1];1001 U32 const nbBits = nbBitsBaseline - w;1002 1003 if (targetLog-nbBits >= minBits) {1004 /* Enough room for a second symbol. */1005 int start = rankVal[w];1006 U32 const length = 1U << ((targetLog - nbBits) & 0x1F /* quiet static-analyzer */);1007 int minWeight = nbBits + scaleLog;1008 int s;1009 if (minWeight < 1) minWeight = 1;1010 /* Fill the DTable for every symbol of weight w.1011 * These symbols get at least 1 second symbol.1012 */1013 for (s = begin; s != end; ++s) {1014 HUF_fillDTableX2Level2(1015 DTable + start, targetLog, nbBits,1016 rankValOrigin[nbBits], minWeight, wEnd,1017 sortedList, rankStart,1018 nbBitsBaseline, sortedList[s].symbol);1019 start += length;1020 }1021 } else {1022 /* Only a single symbol. */1023 HUF_fillDTableX2ForWeight(1024 DTable + rankVal[w],1025 sortedList + begin, sortedList + end,1026 nbBits, targetLog,1027 /* baseSeq */ 0, /* level */ 1);1028 }1029 }1030}1031 1032typedef struct {1033 rankValCol_t rankVal[HUF_TABLELOG_MAX];1034 U32 rankStats[HUF_TABLELOG_MAX + 1];1035 U32 rankStart0[HUF_TABLELOG_MAX + 3];1036 sortedSymbol_t sortedSymbol[HUF_SYMBOLVALUE_MAX + 1];1037 BYTE weightList[HUF_SYMBOLVALUE_MAX + 1];1038 U32 calleeWksp[HUF_READ_STATS_WORKSPACE_SIZE_U32];1039} HUF_ReadDTableX2_Workspace;1040 1041size_t HUF_readDTableX2_wksp(HUF_DTable* DTable,1042 const void* src, size_t srcSize,1043 void* workSpace, size_t wkspSize)1044{1045 return HUF_readDTableX2_wksp_bmi2(DTable, src, srcSize, workSpace, wkspSize, /* bmi2 */ 0);1046}1047 1048size_t HUF_readDTableX2_wksp_bmi2(HUF_DTable* DTable,1049 const void* src, size_t srcSize,1050 void* workSpace, size_t wkspSize, int bmi2)1051{1052 U32 tableLog, maxW, nbSymbols;1053 DTableDesc dtd = HUF_getDTableDesc(DTable);1054 U32 maxTableLog = dtd.maxTableLog;1055 size_t iSize;1056 void* dtPtr = DTable+1; /* force compiler to avoid strict-aliasing */1057 HUF_DEltX2* const dt = (HUF_DEltX2*)dtPtr;1058 U32 *rankStart;1059 1060 HUF_ReadDTableX2_Workspace* const wksp = (HUF_ReadDTableX2_Workspace*)workSpace;1061 1062 if (sizeof(*wksp) > wkspSize) return ERROR(GENERIC);1063 1064 rankStart = wksp->rankStart0 + 1;1065 ZSTD_memset(wksp->rankStats, 0, sizeof(wksp->rankStats));1066 ZSTD_memset(wksp->rankStart0, 0, sizeof(wksp->rankStart0));1067 1068 DEBUG_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(HUF_DTable)); /* if compiler fails here, assertion is wrong */1069 if (maxTableLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);1070 /* ZSTD_memset(weightList, 0, sizeof(weightList)); */ /* is not necessary, even though some analyzer complain ... */1071 1072 iSize = HUF_readStats_wksp(wksp->weightList, HUF_SYMBOLVALUE_MAX + 1, wksp->rankStats, &nbSymbols, &tableLog, src, srcSize, wksp->calleeWksp, sizeof(wksp->calleeWksp), bmi2);1073 if (HUF_isError(iSize)) return iSize;1074 1075 /* check result */1076 if (tableLog > maxTableLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */1077 if (tableLog <= HUF_DECODER_FAST_TABLELOG && maxTableLog > HUF_DECODER_FAST_TABLELOG) maxTableLog = HUF_DECODER_FAST_TABLELOG;1078 1079 /* find maxWeight */1080 for (maxW = tableLog; wksp->rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */1081 1082 /* Get start index of each weight */1083 { U32 w, nextRankStart = 0;1084 for (w=1; w<maxW+1; w++) {1085 U32 curr = nextRankStart;1086 nextRankStart += wksp->rankStats[w];1087 rankStart[w] = curr;1088 }1089 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/1090 rankStart[maxW+1] = nextRankStart;1091 }1092 1093 /* sort symbols by weight */1094 { U32 s;1095 for (s=0; s<nbSymbols; s++) {1096 U32 const w = wksp->weightList[s];1097 U32 const r = rankStart[w]++;1098 wksp->sortedSymbol[r].symbol = (BYTE)s;1099 }1100 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */1101 }1102 1103 /* Build rankVal */1104 { U32* const rankVal0 = wksp->rankVal[0];1105 { int const rescale = (maxTableLog-tableLog) - 1; /* tableLog <= maxTableLog */1106 U32 nextRankVal = 0;1107 U32 w;1108 for (w=1; w<maxW+1; w++) {1109 U32 curr = nextRankVal;1110 nextRankVal += wksp->rankStats[w] << (w+rescale);1111 rankVal0[w] = curr;1112 } }1113 { U32 const minBits = tableLog+1 - maxW;1114 U32 consumed;1115 for (consumed = minBits; consumed < maxTableLog - minBits + 1; consumed++) {1116 U32* const rankValPtr = wksp->rankVal[consumed];1117 U32 w;1118 for (w = 1; w < maxW+1; w++) {1119 rankValPtr[w] = rankVal0[w] >> consumed;1120 } } } }1121 1122 HUF_fillDTableX2(dt, maxTableLog,1123 wksp->sortedSymbol,1124 wksp->rankStart0, wksp->rankVal, maxW,1125 tableLog+1);1126 1127 dtd.tableLog = (BYTE)maxTableLog;1128 dtd.tableType = 1;1129 ZSTD_memcpy(DTable, &dtd, sizeof(dtd));1130 return iSize;1131}1132 1133 1134FORCE_INLINE_TEMPLATE U321135HUF_decodeSymbolX2(void* op, BIT_DStream_t* DStream, const HUF_DEltX2* dt, const U32 dtLog)1136{1137 size_t const val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */1138 ZSTD_memcpy(op, &dt[val].sequence, 2);1139 BIT_skipBits(DStream, dt[val].nbBits);1140 return dt[val].length;1141}1142 1143FORCE_INLINE_TEMPLATE U321144HUF_decodeLastSymbolX2(void* op, BIT_DStream_t* DStream, const HUF_DEltX2* dt, const U32 dtLog)1145{1146 size_t const val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */1147 ZSTD_memcpy(op, &dt[val].sequence, 1);1148 if (dt[val].length==1) {1149 BIT_skipBits(DStream, dt[val].nbBits);1150 } else {1151 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {1152 BIT_skipBits(DStream, dt[val].nbBits);1153 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))1154 /* ugly hack; works only because it's the last symbol. Note : can't easily extract nbBits from just this symbol */1155 DStream->bitsConsumed = (sizeof(DStream->bitContainer)*8);1156 }1157 }1158 return 1;1159}1160 1161#define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \1162 ptr += HUF_decodeSymbolX2(ptr, DStreamPtr, dt, dtLog)1163 1164#define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \1165 if (MEM_64bits() || (HUF_TABLELOG_MAX<=12)) \1166 ptr += HUF_decodeSymbolX2(ptr, DStreamPtr, dt, dtLog)1167 1168#define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \1169 if (MEM_64bits()) \1170 ptr += HUF_decodeSymbolX2(ptr, DStreamPtr, dt, dtLog)1171 1172HINT_INLINE size_t1173HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd,1174 const HUF_DEltX2* const dt, const U32 dtLog)1175{1176 BYTE* const pStart = p;1177 1178 /* up to 8 symbols at a time */1179 if ((size_t)(pEnd - p) >= sizeof(bitDPtr->bitContainer)) {1180 if (dtLog <= 11 && MEM_64bits()) {1181 /* up to 10 symbols at a time */1182 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p < pEnd-9)) {1183 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);1184 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);1185 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);1186 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);1187 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);1188 }1189 } else {1190 /* up to 8 symbols at a time */1191 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p < pEnd-(sizeof(bitDPtr->bitContainer)-1))) {1192 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);1193 HUF_DECODE_SYMBOLX2_1(p, bitDPtr);1194 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);1195 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);1196 }1197 }1198 } else {1199 BIT_reloadDStream(bitDPtr);1200 }1201 1202 /* closer to end : up to 2 symbols at a time */1203 if ((size_t)(pEnd - p) >= 2) {1204 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p <= pEnd-2))1205 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);1206 1207 while (p <= pEnd-2)1208 HUF_DECODE_SYMBOLX2_0(p, bitDPtr); /* no need to reload : reached the end of DStream */1209 }1210 1211 if (p < pEnd)1212 p += HUF_decodeLastSymbolX2(p, bitDPtr, dt, dtLog);1213 1214 return p-pStart;1215}1216 1217FORCE_INLINE_TEMPLATE size_t1218HUF_decompress1X2_usingDTable_internal_body(1219 void* dst, size_t dstSize,1220 const void* cSrc, size_t cSrcSize,1221 const HUF_DTable* DTable)1222{1223 BIT_DStream_t bitD;1224 1225 /* Init */1226 CHECK_F( BIT_initDStream(&bitD, cSrc, cSrcSize) );1227 1228 /* decode */1229 { BYTE* const ostart = (BYTE*) dst;1230 BYTE* const oend = ostart + dstSize;1231 const void* const dtPtr = DTable+1; /* force compiler to not use strict-aliasing */1232 const HUF_DEltX2* const dt = (const HUF_DEltX2*)dtPtr;1233 DTableDesc const dtd = HUF_getDTableDesc(DTable);1234 HUF_decodeStreamX2(ostart, &bitD, oend, dt, dtd.tableLog);1235 }1236 1237 /* check */1238 if (!BIT_endOfDStream(&bitD)) return ERROR(corruption_detected);1239 1240 /* decoded size */1241 return dstSize;1242}1243FORCE_INLINE_TEMPLATE size_t1244HUF_decompress4X2_usingDTable_internal_body(1245 void* dst, size_t dstSize,1246 const void* cSrc, size_t cSrcSize,1247 const HUF_DTable* DTable)1248{1249 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */1250 1251 { const BYTE* const istart = (const BYTE*) cSrc;1252 BYTE* const ostart = (BYTE*) dst;1253 BYTE* const oend = ostart + dstSize;1254 BYTE* const olimit = oend - (sizeof(size_t)-1);1255 const void* const dtPtr = DTable+1;1256 const HUF_DEltX2* const dt = (const HUF_DEltX2*)dtPtr;1257 1258 /* Init */1259 BIT_DStream_t bitD1;1260 BIT_DStream_t bitD2;1261 BIT_DStream_t bitD3;1262 BIT_DStream_t bitD4;1263 size_t const length1 = MEM_readLE16(istart);1264 size_t const length2 = MEM_readLE16(istart+2);1265 size_t const length3 = MEM_readLE16(istart+4);1266 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);1267 const BYTE* const istart1 = istart + 6; /* jumpTable */1268 const BYTE* const istart2 = istart1 + length1;1269 const BYTE* const istart3 = istart2 + length2;1270 const BYTE* const istart4 = istart3 + length3;1271 size_t const segmentSize = (dstSize+3) / 4;1272 BYTE* const opStart2 = ostart + segmentSize;1273 BYTE* const opStart3 = opStart2 + segmentSize;1274 BYTE* const opStart4 = opStart3 + segmentSize;1275 BYTE* op1 = ostart;1276 BYTE* op2 = opStart2;1277 BYTE* op3 = opStart3;1278 BYTE* op4 = opStart4;1279 U32 endSignal = 1;1280 DTableDesc const dtd = HUF_getDTableDesc(DTable);1281 U32 const dtLog = dtd.tableLog;1282 1283 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */1284 if (opStart4 > oend) return ERROR(corruption_detected); /* overflow */1285 CHECK_F( BIT_initDStream(&bitD1, istart1, length1) );1286 CHECK_F( BIT_initDStream(&bitD2, istart2, length2) );1287 CHECK_F( BIT_initDStream(&bitD3, istart3, length3) );1288 CHECK_F( BIT_initDStream(&bitD4, istart4, length4) );1289 1290 /* 16-32 symbols per loop (4-8 symbols per stream) */1291 if ((size_t)(oend - op4) >= sizeof(size_t)) {1292 for ( ; (endSignal) & (op4 < olimit); ) {1293#if defined(__clang__) && (defined(__x86_64__) || defined(__i386__))1294 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);1295 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);1296 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);1297 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);1298 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);1299 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);1300 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);1301 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);1302 endSignal &= BIT_reloadDStreamFast(&bitD1) == BIT_DStream_unfinished;1303 endSignal &= BIT_reloadDStreamFast(&bitD2) == BIT_DStream_unfinished;1304 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);1305 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);1306 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);1307 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);1308 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);1309 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);1310 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);1311 HUF_DECODE_SYMBOLX2_0(op4, &bitD4);1312 endSignal &= BIT_reloadDStreamFast(&bitD3) == BIT_DStream_unfinished;1313 endSignal &= BIT_reloadDStreamFast(&bitD4) == BIT_DStream_unfinished;1314#else1315 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);1316 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);1317 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);1318 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);1319 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);1320 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);1321 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);1322 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);1323 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);1324 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);1325 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);1326 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);1327 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);1328 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);1329 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);1330 HUF_DECODE_SYMBOLX2_0(op4, &bitD4);1331 endSignal = (U32)LIKELY((U32)1332 (BIT_reloadDStreamFast(&bitD1) == BIT_DStream_unfinished)1333 & (BIT_reloadDStreamFast(&bitD2) == BIT_DStream_unfinished)1334 & (BIT_reloadDStreamFast(&bitD3) == BIT_DStream_unfinished)1335 & (BIT_reloadDStreamFast(&bitD4) == BIT_DStream_unfinished));1336#endif1337 }1338 }1339 1340 /* check corruption */1341 if (op1 > opStart2) return ERROR(corruption_detected);1342 if (op2 > opStart3) return ERROR(corruption_detected);1343 if (op3 > opStart4) return ERROR(corruption_detected);1344 /* note : op4 already verified within main loop */1345 1346 /* finish bitStreams one by one */1347 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);1348 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);1349 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);1350 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);1351 1352 /* check */1353 { U32 const endCheck = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);1354 if (!endCheck) return ERROR(corruption_detected); }1355 1356 /* decoded size */1357 return dstSize;1358 }1359}1360 1361#if HUF_NEED_BMI2_FUNCTION1362static BMI2_TARGET_ATTRIBUTE1363size_t HUF_decompress4X2_usingDTable_internal_bmi2(void* dst, size_t dstSize, void const* cSrc,1364 size_t cSrcSize, HUF_DTable const* DTable) {1365 return HUF_decompress4X2_usingDTable_internal_body(dst, dstSize, cSrc, cSrcSize, DTable);1366}1367#endif1368 1369#if HUF_NEED_DEFAULT_FUNCTION1370static1371size_t HUF_decompress4X2_usingDTable_internal_default(void* dst, size_t dstSize, void const* cSrc,1372 size_t cSrcSize, HUF_DTable const* DTable) {1373 return HUF_decompress4X2_usingDTable_internal_body(dst, dstSize, cSrc, cSrcSize, DTable);1374}1375#endif1376 1377#if ZSTD_ENABLE_ASM_X86_64_BMI21378 1379HUF_ASM_DECL void HUF_decompress4X2_usingDTable_internal_bmi2_asm_loop(HUF_DecompressAsmArgs* args) ZSTDLIB_HIDDEN;1380 1381static HUF_ASM_X86_64_BMI2_ATTRS size_t1382HUF_decompress4X2_usingDTable_internal_bmi2_asm(1383 void* dst, size_t dstSize,1384 const void* cSrc, size_t cSrcSize,1385 const HUF_DTable* DTable) {1386 void const* dt = DTable + 1;1387 const BYTE* const iend = (const BYTE*)cSrc + 6;1388 BYTE* const oend = (BYTE*)dst + dstSize;1389 HUF_DecompressAsmArgs args;1390 {1391 size_t const ret = HUF_DecompressAsmArgs_init(&args, dst, dstSize, cSrc, cSrcSize, DTable);1392 FORWARD_IF_ERROR(ret, "Failed to init asm args");1393 if (ret != 0)1394 return HUF_decompress4X2_usingDTable_internal_bmi2(dst, dstSize, cSrc, cSrcSize, DTable);1395 }1396 1397 assert(args.ip[0] >= args.ilimit);1398 HUF_decompress4X2_usingDTable_internal_bmi2_asm_loop(&args);1399 1400 /* note : op4 already verified within main loop */1401 assert(args.ip[0] >= iend);1402 assert(args.ip[1] >= iend);1403 assert(args.ip[2] >= iend);1404 assert(args.ip[3] >= iend);1405 assert(args.op[3] <= oend);1406 (void)iend;1407 1408 /* finish bitStreams one by one */1409 {1410 size_t const segmentSize = (dstSize+3) / 4;1411 BYTE* segmentEnd = (BYTE*)dst;1412 int i;1413 for (i = 0; i < 4; ++i) {1414 BIT_DStream_t bit;1415 if (segmentSize <= (size_t)(oend - segmentEnd))1416 segmentEnd += segmentSize;1417 else1418 segmentEnd = oend;1419 FORWARD_IF_ERROR(HUF_initRemainingDStream(&bit, &args, i, segmentEnd), "corruption");1420 args.op[i] += HUF_decodeStreamX2(args.op[i], &bit, segmentEnd, (HUF_DEltX2 const*)dt, HUF_DECODER_FAST_TABLELOG);1421 if (args.op[i] != segmentEnd)1422 return ERROR(corruption_detected);1423 }1424 }1425 1426 /* decoded size */1427 return dstSize;1428}1429#endif /* ZSTD_ENABLE_ASM_X86_64_BMI2 */1430 1431static size_t HUF_decompress4X2_usingDTable_internal(void* dst, size_t dstSize, void const* cSrc,1432 size_t cSrcSize, HUF_DTable const* DTable, int bmi2)1433{1434#if DYNAMIC_BMI21435 if (bmi2) {1436# if ZSTD_ENABLE_ASM_X86_64_BMI21437 return HUF_decompress4X2_usingDTable_internal_bmi2_asm(dst, dstSize, cSrc, cSrcSize, DTable);1438# else1439 return HUF_decompress4X2_usingDTable_internal_bmi2(dst, dstSize, cSrc, cSrcSize, DTable);1440# endif1441 }1442#else1443 (void)bmi2;1444#endif1445 1446#if ZSTD_ENABLE_ASM_X86_64_BMI2 && defined(__BMI2__)1447 return HUF_decompress4X2_usingDTable_internal_bmi2_asm(dst, dstSize, cSrc, cSrcSize, DTable);1448#else1449 return HUF_decompress4X2_usingDTable_internal_default(dst, dstSize, cSrc, cSrcSize, DTable);1450#endif1451}1452 1453HUF_DGEN(HUF_decompress1X2_usingDTable_internal)1454 1455size_t HUF_decompress1X2_usingDTable(1456 void* dst, size_t dstSize,1457 const void* cSrc, size_t cSrcSize,1458 const HUF_DTable* DTable)1459{1460 DTableDesc dtd = HUF_getDTableDesc(DTable);1461 if (dtd.tableType != 1) return ERROR(GENERIC);1462 return HUF_decompress1X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);1463}1464 1465size_t HUF_decompress1X2_DCtx_wksp(HUF_DTable* DCtx, void* dst, size_t dstSize,1466 const void* cSrc, size_t cSrcSize,1467 void* workSpace, size_t wkspSize)1468{1469 const BYTE* ip = (const BYTE*) cSrc;1470 1471 size_t const hSize = HUF_readDTableX2_wksp(DCtx, cSrc, cSrcSize,1472 workSpace, wkspSize);1473 if (HUF_isError(hSize)) return hSize;1474 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);1475 ip += hSize; cSrcSize -= hSize;1476 1477 return HUF_decompress1X2_usingDTable_internal(dst, dstSize, ip, cSrcSize, DCtx, /* bmi2 */ 0);1478}1479 1480 1481size_t HUF_decompress4X2_usingDTable(1482 void* dst, size_t dstSize,1483 const void* cSrc, size_t cSrcSize,1484 const HUF_DTable* DTable)1485{1486 DTableDesc dtd = HUF_getDTableDesc(DTable);1487 if (dtd.tableType != 1) return ERROR(GENERIC);1488 return HUF_decompress4X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);1489}1490 1491static size_t HUF_decompress4X2_DCtx_wksp_bmi2(HUF_DTable* dctx, void* dst, size_t dstSize,1492 const void* cSrc, size_t cSrcSize,1493 void* workSpace, size_t wkspSize, int bmi2)1494{1495 const BYTE* ip = (const BYTE*) cSrc;1496 1497 size_t hSize = HUF_readDTableX2_wksp(dctx, cSrc, cSrcSize,1498 workSpace, wkspSize);1499 if (HUF_isError(hSize)) return hSize;1500 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);1501 ip += hSize; cSrcSize -= hSize;1502 1503 return HUF_decompress4X2_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx, bmi2);1504}1505 1506size_t HUF_decompress4X2_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize,1507 const void* cSrc, size_t cSrcSize,1508 void* workSpace, size_t wkspSize)1509{1510 return HUF_decompress4X2_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, /* bmi2 */ 0);1511}1512 1513 1514#endif /* HUF_FORCE_DECOMPRESS_X1 */1515 1516 1517/* ***********************************/1518/* Universal decompression selectors */1519/* ***********************************/1520 1521size_t HUF_decompress1X_usingDTable(void* dst, size_t maxDstSize,1522 const void* cSrc, size_t cSrcSize,1523 const HUF_DTable* DTable)1524{1525 DTableDesc const dtd = HUF_getDTableDesc(DTable);1526#if defined(HUF_FORCE_DECOMPRESS_X1)1527 (void)dtd;1528 assert(dtd.tableType == 0);1529 return HUF_decompress1X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);1530#elif defined(HUF_FORCE_DECOMPRESS_X2)1531 (void)dtd;1532 assert(dtd.tableType == 1);1533 return HUF_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);1534#else1535 return dtd.tableType ? HUF_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0) :1536 HUF_decompress1X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);1537#endif1538}1539 1540size_t HUF_decompress4X_usingDTable(void* dst, size_t maxDstSize,1541 const void* cSrc, size_t cSrcSize,1542 const HUF_DTable* DTable)1543{1544 DTableDesc const dtd = HUF_getDTableDesc(DTable);1545#if defined(HUF_FORCE_DECOMPRESS_X1)1546 (void)dtd;1547 assert(dtd.tableType == 0);1548 return HUF_decompress4X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);1549#elif defined(HUF_FORCE_DECOMPRESS_X2)1550 (void)dtd;1551 assert(dtd.tableType == 1);1552 return HUF_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);1553#else1554 return dtd.tableType ? HUF_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0) :1555 HUF_decompress4X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);1556#endif1557}1558 1559 1560#if !defined(HUF_FORCE_DECOMPRESS_X1) && !defined(HUF_FORCE_DECOMPRESS_X2)1561typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;1562static const algo_time_t algoTime[16 /* Quantization */][2 /* single, double */] =1563{1564 /* single, double, quad */1565 {{0,0}, {1,1}}, /* Q==0 : impossible */1566 {{0,0}, {1,1}}, /* Q==1 : impossible */1567 {{ 150,216}, { 381,119}}, /* Q == 2 : 12-18% */1568 {{ 170,205}, { 514,112}}, /* Q == 3 : 18-25% */1569 {{ 177,199}, { 539,110}}, /* Q == 4 : 25-32% */1570 {{ 197,194}, { 644,107}}, /* Q == 5 : 32-38% */1571 {{ 221,192}, { 735,107}}, /* Q == 6 : 38-44% */1572 {{ 256,189}, { 881,106}}, /* Q == 7 : 44-50% */1573 {{ 359,188}, {1167,109}}, /* Q == 8 : 50-56% */1574 {{ 582,187}, {1570,114}}, /* Q == 9 : 56-62% */1575 {{ 688,187}, {1712,122}}, /* Q ==10 : 62-69% */1576 {{ 825,186}, {1965,136}}, /* Q ==11 : 69-75% */1577 {{ 976,185}, {2131,150}}, /* Q ==12 : 75-81% */1578 {{1180,186}, {2070,175}}, /* Q ==13 : 81-87% */1579 {{1377,185}, {1731,202}}, /* Q ==14 : 87-93% */1580 {{1412,185}, {1695,202}}, /* Q ==15 : 93-99% */1581};1582#endif1583 1584/* HUF_selectDecoder() :1585 * Tells which decoder is likely to decode faster,1586 * based on a set of pre-computed metrics.1587 * @return : 0==HUF_decompress4X1, 1==HUF_decompress4X2 .1588 * Assumption : 0 < dstSize <= 128 KB */1589U32 HUF_selectDecoder (size_t dstSize, size_t cSrcSize)1590{1591 assert(dstSize > 0);1592 assert(dstSize <= 128*1024);1593#if defined(HUF_FORCE_DECOMPRESS_X1)1594 (void)dstSize;1595 (void)cSrcSize;1596 return 0;1597#elif defined(HUF_FORCE_DECOMPRESS_X2)1598 (void)dstSize;1599 (void)cSrcSize;1600 return 1;1601#else1602 /* decoder timing evaluation */1603 { U32 const Q = (cSrcSize >= dstSize) ? 15 : (U32)(cSrcSize * 16 / dstSize); /* Q < 16 */1604 U32 const D256 = (U32)(dstSize >> 8);1605 U32 const DTime0 = algoTime[Q][0].tableTime + (algoTime[Q][0].decode256Time * D256);1606 U32 DTime1 = algoTime[Q][1].tableTime + (algoTime[Q][1].decode256Time * D256);1607 DTime1 += DTime1 >> 5; /* small advantage to algorithm using less memory, to reduce cache eviction */1608 return DTime1 < DTime0;1609 }1610#endif1611}1612 1613 1614size_t HUF_decompress4X_hufOnly_wksp(HUF_DTable* dctx, void* dst,1615 size_t dstSize, const void* cSrc,1616 size_t cSrcSize, void* workSpace,1617 size_t wkspSize)1618{1619 /* validation checks */1620 if (dstSize == 0) return ERROR(dstSize_tooSmall);1621 if (cSrcSize == 0) return ERROR(corruption_detected);1622 1623 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);1624#if defined(HUF_FORCE_DECOMPRESS_X1)1625 (void)algoNb;1626 assert(algoNb == 0);1627 return HUF_decompress4X1_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize);1628#elif defined(HUF_FORCE_DECOMPRESS_X2)1629 (void)algoNb;1630 assert(algoNb == 1);1631 return HUF_decompress4X2_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize);1632#else1633 return algoNb ? HUF_decompress4X2_DCtx_wksp(dctx, dst, dstSize, cSrc,1634 cSrcSize, workSpace, wkspSize):1635 HUF_decompress4X1_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize);1636#endif1637 }1638}1639 1640size_t HUF_decompress1X_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize,1641 const void* cSrc, size_t cSrcSize,1642 void* workSpace, size_t wkspSize)1643{1644 /* validation checks */1645 if (dstSize == 0) return ERROR(dstSize_tooSmall);1646 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */1647 if (cSrcSize == dstSize) { ZSTD_memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */1648 if (cSrcSize == 1) { ZSTD_memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */1649 1650 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);1651#if defined(HUF_FORCE_DECOMPRESS_X1)1652 (void)algoNb;1653 assert(algoNb == 0);1654 return HUF_decompress1X1_DCtx_wksp(dctx, dst, dstSize, cSrc,1655 cSrcSize, workSpace, wkspSize);1656#elif defined(HUF_FORCE_DECOMPRESS_X2)1657 (void)algoNb;1658 assert(algoNb == 1);1659 return HUF_decompress1X2_DCtx_wksp(dctx, dst, dstSize, cSrc,1660 cSrcSize, workSpace, wkspSize);1661#else1662 return algoNb ? HUF_decompress1X2_DCtx_wksp(dctx, dst, dstSize, cSrc,1663 cSrcSize, workSpace, wkspSize):1664 HUF_decompress1X1_DCtx_wksp(dctx, dst, dstSize, cSrc,1665 cSrcSize, workSpace, wkspSize);1666#endif1667 }1668}1669 1670 1671size_t HUF_decompress1X_usingDTable_bmi2(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, int bmi2)1672{1673 DTableDesc const dtd = HUF_getDTableDesc(DTable);1674#if defined(HUF_FORCE_DECOMPRESS_X1)1675 (void)dtd;1676 assert(dtd.tableType == 0);1677 return HUF_decompress1X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);1678#elif defined(HUF_FORCE_DECOMPRESS_X2)1679 (void)dtd;1680 assert(dtd.tableType == 1);1681 return HUF_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);1682#else1683 return dtd.tableType ? HUF_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2) :1684 HUF_decompress1X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);1685#endif1686}1687 1688#ifndef HUF_FORCE_DECOMPRESS_X21689size_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)1690{1691 const BYTE* ip = (const BYTE*) cSrc;1692 1693 size_t const hSize = HUF_readDTableX1_wksp_bmi2(dctx, cSrc, cSrcSize, workSpace, wkspSize, bmi2);1694 if (HUF_isError(hSize)) return hSize;1695 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);1696 ip += hSize; cSrcSize -= hSize;1697 1698 return HUF_decompress1X1_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx, bmi2);1699}1700#endif1701 1702size_t HUF_decompress4X_usingDTable_bmi2(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, int bmi2)1703{1704 DTableDesc const dtd = HUF_getDTableDesc(DTable);1705#if defined(HUF_FORCE_DECOMPRESS_X1)1706 (void)dtd;1707 assert(dtd.tableType == 0);1708 return HUF_decompress4X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);1709#elif defined(HUF_FORCE_DECOMPRESS_X2)1710 (void)dtd;1711 assert(dtd.tableType == 1);1712 return HUF_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);1713#else1714 return dtd.tableType ? HUF_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2) :1715 HUF_decompress4X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);1716#endif1717}1718 1719size_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)1720{1721 /* validation checks */1722 if (dstSize == 0) return ERROR(dstSize_tooSmall);1723 if (cSrcSize == 0) return ERROR(corruption_detected);1724 1725 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);1726#if defined(HUF_FORCE_DECOMPRESS_X1)1727 (void)algoNb;1728 assert(algoNb == 0);1729 return HUF_decompress4X1_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, bmi2);1730#elif defined(HUF_FORCE_DECOMPRESS_X2)1731 (void)algoNb;1732 assert(algoNb == 1);1733 return HUF_decompress4X2_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, bmi2);1734#else1735 return algoNb ? HUF_decompress4X2_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, bmi2) :1736 HUF_decompress4X1_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, bmi2);1737#endif1738 }1739}1740 1741