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 
HUF_getDTableDesc(const HUF_DTable * table)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 
HUF_initDStream(BYTE const * ip)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  */
HUF_DecompressAsmArgs_init(HUF_DecompressAsmArgs * args,void * dst,size_t dstSize,void const * src,size_t srcSize,const HUF_DTable * DTable)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 
HUF_initRemainingDStream(BIT_DStream_t * bit,HUF_DecompressAsmArgs const * args,int stream,BYTE * segmentEnd)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  */
HUF_DEltX1_set4(BYTE symbol,BYTE nbBits)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  */
HUF_rescaleStats(BYTE * huffWeight,U32 * rankVal,U32 nbSymbols,U32 tableLog,U32 targetTableLog)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 
HUF_readDTableX1_wksp(HUF_DTable * DTable,const void * src,size_t srcSize,void * workSpace,size_t wkspSize)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 
HUF_readDTableX1_wksp_bmi2(HUF_DTable * DTable,const void * src,size_t srcSize,void * workSpace,size_t wkspSize,int bmi2)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
HUF_decodeSymbolX1(BIT_DStream_t * Dstream,const HUF_DEltX1 * dt,const U32 dtLog)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
HUF_decodeStreamX1(BYTE * p,BIT_DStream_t * const bitDPtr,BYTE * const pEnd,const HUF_DEltX1 * const dt,const U32 dtLog)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
HUF_decompress1X1_usingDTable_internal_body(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable)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
HUF_decompress4X1_usingDTable_internal_body(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable)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
HUF_decompress4X1_usingDTable_internal_bmi2(void * dst,size_t dstSize,void const * cSrc,size_t cSrcSize,HUF_DTable const * DTable)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
HUF_decompress4X1_usingDTable_internal_default(void * dst,size_t dstSize,void const * cSrc,size_t cSrcSize,HUF_DTable const * DTable)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
HUF_decompress4X1_usingDTable_internal_bmi2_asm(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable)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 
HUF_DGEN(HUF_decompress1X1_usingDTable_internal)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 
HUF_decompress1X1_usingDTable(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable)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 
HUF_decompress1X1_DCtx_wksp(HUF_DTable * DCtx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,void * workSpace,size_t wkspSize)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 
HUF_decompress4X1_usingDTable(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable)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 
HUF_decompress4X1_DCtx_wksp_bmi2(HUF_DTable * dctx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,void * workSpace,size_t wkspSize,int bmi2)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 
HUF_decompress4X1_DCtx_wksp(HUF_DTable * dctx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,void * workSpace,size_t wkspSize)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  */
HUF_buildDEltX2U32(U32 symbol,U32 nbBits,U32 baseSeq,int level)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  */
HUF_buildDEltX2(U32 symbol,U32 nbBits,U32 baseSeq,int level)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  */
HUF_buildDEltX2U64(U32 symbol,U32 nbBits,U16 baseSeq,int level)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  */
HUF_fillDTableX2ForWeight(HUF_DEltX2 * DTableRank,sortedSymbol_t const * begin,sortedSymbol_t const * end,U32 nbBits,U32 tableLog,U16 baseSeq,int const level)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 */
HUF_fillDTableX2Level2(HUF_DEltX2 * DTable,U32 targetLog,const U32 consumedBits,const U32 * rankVal,const int minWeight,const int maxWeight1,const sortedSymbol_t * sortedSymbols,U32 const * rankStart,U32 nbBitsBaseline,U16 baseSeq)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 
HUF_fillDTableX2(HUF_DEltX2 * DTable,const U32 targetLog,const sortedSymbol_t * sortedList,const U32 * rankStart,rankValCol_t * rankValOrigin,const U32 maxWeight,const U32 nbBitsBaseline)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 
HUF_readDTableX2_wksp(HUF_DTable * DTable,const void * src,size_t srcSize,void * workSpace,size_t wkspSize)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 
HUF_readDTableX2_wksp_bmi2(HUF_DTable * DTable,const void * src,size_t srcSize,void * workSpace,size_t wkspSize,int bmi2)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
HUF_decodeSymbolX2(void * op,BIT_DStream_t * DStream,const HUF_DEltX2 * dt,const U32 dtLog)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
HUF_decodeLastSymbolX2(void * op,BIT_DStream_t * DStream,const HUF_DEltX2 * dt,const U32 dtLog)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
HUF_decodeStreamX2(BYTE * p,BIT_DStream_t * bitDPtr,BYTE * const pEnd,const HUF_DEltX2 * const dt,const U32 dtLog)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
HUF_decompress1X2_usingDTable_internal_body(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable)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
HUF_decompress4X2_usingDTable_internal_body(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable)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
HUF_decompress4X2_usingDTable_internal_bmi2(void * dst,size_t dstSize,void const * cSrc,size_t cSrcSize,HUF_DTable const * DTable)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
HUF_decompress4X2_usingDTable_internal_default(void * dst,size_t dstSize,void const * cSrc,size_t cSrcSize,HUF_DTable const * DTable)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
HUF_decompress4X2_usingDTable_internal_bmi2_asm(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable)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 
HUF_decompress4X2_usingDTable_internal(void * dst,size_t dstSize,void const * cSrc,size_t cSrcSize,HUF_DTable const * DTable,int bmi2)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 
HUF_DGEN(HUF_decompress1X2_usingDTable_internal)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 
HUF_decompress1X2_DCtx_wksp(HUF_DTable * DCtx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,void * workSpace,size_t wkspSize)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 
HUF_decompress4X2_usingDTable(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable)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 
HUF_decompress4X2_DCtx_wksp_bmi2(HUF_DTable * dctx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,void * workSpace,size_t wkspSize,int bmi2)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 
HUF_decompress4X2_DCtx_wksp(HUF_DTable * dctx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,void * workSpace,size_t wkspSize)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 
HUF_decompress1X_usingDTable(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable)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 
HUF_decompress4X_usingDTable(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable)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 */
HUF_selectDecoder(size_t dstSize,size_t cSrcSize)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 
HUF_decompress4X_hufOnly_wksp(HUF_DTable * dctx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,void * workSpace,size_t wkspSize)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 
HUF_decompress1X_DCtx_wksp(HUF_DTable * dctx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,void * workSpace,size_t wkspSize)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 
HUF_decompress1X_usingDTable_bmi2(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable,int bmi2)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
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)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 
HUF_decompress4X_usingDTable_bmi2(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const HUF_DTable * DTable,int bmi2)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 
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)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 
1741