lib/zstd/decompress/huf_decompress.c

   1 /* ******************************************************************
   2  * huff0 huffman decoder,
   3  * part of Finite State Entropy library
   4  * Copyright (c) Yann Collet, Facebook, Inc.
   5  *
   6  *  You can contact the author at :
   7  *  - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
   8  *
   9  * This source code is licensed under both the BSD-style license (found in the
  10  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
  11  * 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 *  Dependencies
  17 ****************************************************************/
  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_ONLY
  23 #include "../common/huf.h"
  24 #include "../common/error_private.h"
  25 #include "../common/zstd_internal.h"
  26
  27 /* **************************************************************
  28 *  Constants
  29 ****************************************************************/
  30
  31 #define HUF_DECODER_FAST_TABLELOG 11
  32
  33 /* **************************************************************
  34 *  Macros
  35 ****************************************************************/
  36
  37 /* These two optional macros force the use one way or another of the two
  38  * Huffman decompression implementations. You can't force in both directions
  39  * 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 #endif
  45
  46 #if ZSTD_ENABLE_ASM_X86_64_BMI2 && DYNAMIC_BMI2
  47 # define HUF_ASM_X86_64_BMI2_ATTRS BMI2_TARGET_ATTRIBUTE
  48 #else
  49 # define HUF_ASM_X86_64_BMI2_ATTRS
  50 #endif
  51
  52 #define HUF_EXTERN_C
  53 #define HUF_ASM_DECL HUF_EXTERN_C
  54
  55 #if DYNAMIC_BMI2 || (ZSTD_ENABLE_ASM_X86_64_BMI2 && defined(__BMI2__))
  56 # define HUF_NEED_BMI2_FUNCTION 1
  57 #else
  58 # define HUF_NEED_BMI2_FUNCTION 0
  59 #endif
  60
  61 #if !(ZSTD_ENABLE_ASM_X86_64_BMI2 && defined(__BMI2__))
  62 # define HUF_NEED_DEFAULT_FUNCTION 1
  63 #else
  64 # define HUF_NEED_DEFAULT_FUNCTION 0
  65 #endif
  66
  67 /* **************************************************************
  68 *  Error Management
  69 ****************************************************************/
  70 #define HUF_isError ERR_isError
  71
  72
  73 /* **************************************************************
  74 *  Byte alignment for workSpace management
  75 ****************************************************************/
  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 Wrappers
  82 ****************************************************************/
  83 #if DYNAMIC_BMI2
  84
  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 #else
 113
 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 #endif
 123
 124
 125 /*-***************************/
 126 /*  generic DTableDesc       */
 127 /*-***************************/
 128 typedef struct { BYTE maxTableLog; BYTE tableType; BYTE tableLog; BYTE reserved; } DTableDesc;
 129
 130 static 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_BMI2
 138
 139 static 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 }
 146 typedef 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 success
 159  *          1 if the fallback implementation should be used.
 160  *          Or an error code on failure.
 161  */
 162 static 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 input
 199          * won't benefit from the ASM loop anyways.
 200          * length1 must be >= 16 so that ip[0] >= ilimit before the loop
 201          * 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 are
 226         * shifted in. After the lowest valid bit a 1 is
 227         * set, so that CountTrailingZeros(bits[]) can be used
 228         * 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 to
 236         * reload bits[]. It may be beyond its section, but is
 237         * 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
 247 static 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 is
 254         * 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 #endif
 270
 271
 272 #ifndef HUF_FORCE_DECOMPRESS_X2
 273
 274 /*-***************************/
 275 /*  single-symbol decoding   */
 276 /*-***************************/
 277 typedef 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 at
 281  * a time.
 282  */
 283 static 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 tableLog
 298  */
 299 static 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
 324 typedef 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
 333 size_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
 338 size_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 for
 378      * 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 DTable
 404      * 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 is
 407      * 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
 476 FORCE_INLINE_TEMPLATE BYTE
 477 HUF_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
 496 HINT_INLINE size_t
 497 HUF_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
 525 FORCE_INLINE_TEMPLATE size_t
 526 HUF_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
 548 FORCE_INLINE_TEMPLATE size_t
 549 HUF_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_FUNCTION
 646 static BMI2_TARGET_ATTRIBUTE
 647 size_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 #endif
 652
 653 #if HUF_NEED_DEFAULT_FUNCTION
 654 static
 655 size_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 #endif
 660
 661 #if ZSTD_ENABLE_ASM_X86_64_BMI2
 662
 663 HUF_ASM_DECL void HUF_decompress4X1_usingDTable_internal_bmi2_asm_loop(HUF_DecompressAsmArgs* args) ZSTDLIB_HIDDEN;
 664
 665 static HUF_ASM_X86_64_BMI2_ATTRS
 666 size_t
 667 HUF_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't
 687     * 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             else
 706                 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
 719 typedef 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
 724 HUF_DGEN(HUF_decompress1X1_usingDTable_internal)
 725
 726 static 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_BMI2
 730     if (bmi2) {
 731 # if ZSTD_ENABLE_ASM_X86_64_BMI2
 732         return HUF_decompress4X1_usingDTable_internal_bmi2_asm(dst, dstSize, cSrc, cSrcSize, DTable);
 733 # else
 734         return HUF_decompress4X1_usingDTable_internal_bmi2(dst, dstSize, cSrc, cSrcSize, DTable);
 735 # endif
 736     }
 737 #else
 738     (void)bmi2;
 739 #endif
 740
 741 #if ZSTD_ENABLE_ASM_X86_64_BMI2 && defined(__BMI2__)
 742     return HUF_decompress4X1_usingDTable_internal_bmi2_asm(dst, dstSize, cSrc, cSrcSize, DTable);
 743 #else
 744     return HUF_decompress4X1_usingDTable_internal_default(dst, dstSize, cSrc, cSrcSize, DTable);
 745 #endif
 746 }
 747
 748
 749 size_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
 759 size_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
 774 size_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
 784 static 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
 798 size_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_X1
 810
 811 /* *************************/
 812 /* double-symbols decoding */
 813 /* *************************/
 814
 815 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX2;  /* double-symbols decoding */
 816 typedef struct { BYTE symbol; } sortedSymbol_t;
 817 typedef U32 rankValCol_t[HUF_TABLELOG_MAX + 1];
 818 typedef rankValCol_t rankVal_t[HUF_TABLELOG_MAX];
 819
 820 /*
 821  * Constructs a HUF_DEltX2 in a U32.
 822  */
 823 static 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  */
 842 static 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  */
 854 static 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 each
 862  * 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  */
 872 static 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 */
 931 static 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 weight
 938      * 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
 986 static 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
1032 typedef 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
1041 size_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
1048 size_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
1134 FORCE_INLINE_TEMPLATE U32
1135 HUF_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
1143 FORCE_INLINE_TEMPLATE U32
1144 HUF_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
1172 HINT_INLINE size_t
1173 HUF_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
1217 FORCE_INLINE_TEMPLATE size_t
1218 HUF_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 }
1243 FORCE_INLINE_TEMPLATE size_t
1244 HUF_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 #else
1315                 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 #endif
1337             }
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_FUNCTION
1362 static BMI2_TARGET_ATTRIBUTE
1363 size_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 #endif
1368
1369 #if HUF_NEED_DEFAULT_FUNCTION
1370 static
1371 size_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 #endif
1376
1377 #if ZSTD_ENABLE_ASM_X86_64_BMI2
1378
1379 HUF_ASM_DECL void HUF_decompress4X2_usingDTable_internal_bmi2_asm_loop(HUF_DecompressAsmArgs* args) ZSTDLIB_HIDDEN;
1380
1381 static HUF_ASM_X86_64_BMI2_ATTRS size_t
1382 HUF_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             else
1418                 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
1431 static 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_BMI2
1435     if (bmi2) {
1436 # if ZSTD_ENABLE_ASM_X86_64_BMI2
1437         return HUF_decompress4X2_usingDTable_internal_bmi2_asm(dst, dstSize, cSrc, cSrcSize, DTable);
1438 # else
1439         return HUF_decompress4X2_usingDTable_internal_bmi2(dst, dstSize, cSrc, cSrcSize, DTable);
1440 # endif
1441     }
1442 #else
1443     (void)bmi2;
1444 #endif
1445
1446 #if ZSTD_ENABLE_ASM_X86_64_BMI2 && defined(__BMI2__)
1447     return HUF_decompress4X2_usingDTable_internal_bmi2_asm(dst, dstSize, cSrc, cSrcSize, DTable);
1448 #else
1449     return HUF_decompress4X2_usingDTable_internal_default(dst, dstSize, cSrc, cSrcSize, DTable);
1450 #endif
1451 }
1452
1453 HUF_DGEN(HUF_decompress1X2_usingDTable_internal)
1454
1455 size_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
1465 size_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
1481 size_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
1491 static 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
1506 size_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
1521 size_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 #else
1535     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 #endif
1538 }
1539
1540 size_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 #else
1554     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 #endif
1557 }
1558
1559
1560 #if !defined(HUF_FORCE_DECOMPRESS_X1) && !defined(HUF_FORCE_DECOMPRESS_X2)
1561 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
1562 static 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 #endif
1583
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 */
1589 U32 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 #else
1602     /* 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 #endif
1611 }
1612
1613
1614 size_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 #else
1633         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 #endif
1637     }
1638 }
1639
1640 size_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 #else
1662         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 #endif
1667     }
1668 }
1669
1670
1671 size_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 #else
1683     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 #endif
1686 }
1687
1688 #ifndef HUF_FORCE_DECOMPRESS_X2
1689 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)
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 #endif
1701
1702 size_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 #else
1714     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 #endif
1717 }
1718
1719 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)
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 #else
1735         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 #endif
1738     }
1739 }
1740