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