?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
zpool/zfs: restore -V & --version options
[zfs.git] / module / zstd / lib / decompress / huf_decompress.c
blob68293a13096abaf42b3512464efd0614fd957408
1 /* ******************************************************************
2 * huff0 huffman decoder,
3 * part of Finite State Entropy library
4 * Copyright (c) 2013-2020, 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 <string.h> /* memcpy, 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
26 /* **************************************************************
27 * Macros
28 ****************************************************************/
29
30 /* These two optional macros force the use one way or another of the two
31 * Huffman decompression implementations. You can't force in both directions
32 * at the same time.
33 */
34 #if defined(HUF_FORCE_DECOMPRESS_X1) && \
35 defined(HUF_FORCE_DECOMPRESS_X2)
36 #error "Cannot force the use of the X1 and X2 decoders at the same time!"
37 #endif
38
39
40 /* **************************************************************
41 * Error Management
42 ****************************************************************/
43 #define HUF_isError ERR_isError
44
45
46 /* **************************************************************
47 * Byte alignment for workSpace management
48 ****************************************************************/
49 #define HUF_ALIGN(x, a) HUF_ALIGN_MASK((x), (a) - 1)
50 #define HUF_ALIGN_MASK(x, mask) (((x) + (mask)) & ~(mask))
51
52
53 /* **************************************************************
54 * BMI2 Variant Wrappers
55 ****************************************************************/
56 #if DYNAMIC_BMI2
57
58 #define HUF_DGEN(fn) \
59 \
60 static size_t fn##_default( \
61 void* dst, size_t dstSize, \
62 const void* cSrc, size_t cSrcSize, \
63 const HUF_DTable* DTable) \
64 { \
65 return fn##_body(dst, dstSize, cSrc, cSrcSize, DTable); \
66 } \
67 \
68 static TARGET_ATTRIBUTE("bmi2") size_t fn##_bmi2( \
69 void* dst, size_t dstSize, \
70 const void* cSrc, size_t cSrcSize, \
71 const HUF_DTable* DTable) \
72 { \
73 return fn##_body(dst, dstSize, cSrc, cSrcSize, DTable); \
74 } \
75 \
76 static size_t fn(void* dst, size_t dstSize, void const* cSrc, \
77 size_t cSrcSize, HUF_DTable const* DTable, int bmi2) \
78 { \
79 if (bmi2) { \
80 return fn##_bmi2(dst, dstSize, cSrc, cSrcSize, DTable); \
81 } \
82 return fn##_default(dst, dstSize, cSrc, cSrcSize, DTable); \
83 }
84
85 #else
86
87 #define HUF_DGEN(fn) \
88 static size_t fn(void* dst, size_t dstSize, void const* cSrc, \
89 size_t cSrcSize, HUF_DTable const* DTable, int bmi2) \
90 { \
91 (void)bmi2; \
92 return fn##_body(dst, dstSize, cSrc, cSrcSize, DTable); \
93 }
94
95 #endif
96
97
98 /*-***************************/
99 /* generic DTableDesc */
100 /*-***************************/
101 typedef struct { BYTE maxTableLog; BYTE tableType; BYTE tableLog; BYTE reserved; } DTableDesc;
102
103 static DTableDesc HUF_getDTableDesc(const HUF_DTable* table)
104 {
105 DTableDesc dtd;
106 memcpy(&dtd, table, sizeof(dtd));
107 return dtd;
108 }
109
110
111 #ifndef HUF_FORCE_DECOMPRESS_X2
112
113 /*-***************************/
114 /* single-symbol decoding */
115 /*-***************************/
116 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX1; /* single-symbol decoding */
117
118 size_t HUF_readDTableX1_wksp(HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize)
119 {
120 U32 tableLog = 0;
121 U32 nbSymbols = 0;
122 size_t iSize;
123 void* const dtPtr = DTable + 1;
124 HUF_DEltX1* const dt = (HUF_DEltX1*)dtPtr;
125
126 U32* rankVal;
127 BYTE* huffWeight;
128 size_t spaceUsed32 = 0;
129
130 rankVal = (U32 *)workSpace + spaceUsed32;
131 spaceUsed32 += HUF_TABLELOG_ABSOLUTEMAX + 1;
132 huffWeight = (BYTE *)((U32 *)workSpace + spaceUsed32);
133 spaceUsed32 += HUF_ALIGN(HUF_SYMBOLVALUE_MAX + 1, sizeof(U32)) >> 2;
134
135 if ((spaceUsed32 << 2) > wkspSize) return ERROR(tableLog_tooLarge);
136
137 DEBUG_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUF_DTable));
138 /* memset(huffWeight, 0, sizeof(huffWeight)); */ /* is not necessary, even though some analyzer complain ... */
139
140 iSize = HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
141 if (HUF_isError(iSize)) return iSize;
142
143 /* Table header */
144 { DTableDesc dtd = HUF_getDTableDesc(DTable);
145 if (tableLog > (U32)(dtd.maxTableLog+1)) return ERROR(tableLog_tooLarge); /* DTable too small, Huffman tree cannot fit in */
146 dtd.tableType = 0;
147 dtd.tableLog = (BYTE)tableLog;
148 memcpy(DTable, &dtd, sizeof(dtd));
149 }
150
151 /* Calculate starting value for each rank */
152 { U32 n, nextRankStart = 0;
153 for (n=1; n<tableLog+1; n++) {
154 U32 const current = nextRankStart;
155 nextRankStart += (rankVal[n] << (n-1));
156 rankVal[n] = current;
157 } }
158
159 /* fill DTable */
160 { U32 n;
161 size_t const nEnd = nbSymbols;
162 for (n=0; n<nEnd; n++) {
163 size_t const w = huffWeight[n];
164 size_t const length = (1 << w) >> 1;
165 size_t const uStart = rankVal[w];
166 size_t const uEnd = uStart + length;
167 size_t u;
168 HUF_DEltX1 D;
169 D.byte = (BYTE)n;
170 D.nbBits = (BYTE)(tableLog + 1 - w);
171 rankVal[w] = (U32)uEnd;
172 if (length < 4) {
173 /* Use length in the loop bound so the compiler knows it is short. */
174 for (u = 0; u < length; ++u)
175 dt[uStart + u] = D;
176 } else {
177 /* Unroll the loop 4 times, we know it is a power of 2. */
178 for (u = uStart; u < uEnd; u += 4) {
179 dt[u + 0] = D;
180 dt[u + 1] = D;
181 dt[u + 2] = D;
182 dt[u + 3] = D;
183 } } } }
184 return iSize;
185 }
186
187 size_t HUF_readDTableX1(HUF_DTable* DTable, const void* src, size_t srcSize)
188 {
189 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
190 return HUF_readDTableX1_wksp(DTable, src, srcSize,
191 workSpace, sizeof(workSpace));
192 }
193
194 FORCE_INLINE_TEMPLATE BYTE
195 HUF_decodeSymbolX1(BIT_DStream_t* Dstream, const HUF_DEltX1* dt, const U32 dtLog)
196 {
197 size_t const val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
198 BYTE const c = dt[val].byte;
199 BIT_skipBits(Dstream, dt[val].nbBits);
200 return c;
201 }
202
203 #define HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr) \
204 *ptr++ = HUF_decodeSymbolX1(DStreamPtr, dt, dtLog)
205
206 #define HUF_DECODE_SYMBOLX1_1(ptr, DStreamPtr) \
207 if (MEM_64bits() || (HUF_TABLELOG_MAX<=12)) \
208 HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr)
209
210 #define HUF_DECODE_SYMBOLX1_2(ptr, DStreamPtr) \
211 if (MEM_64bits()) \
212 HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr)
213
214 HINT_INLINE size_t
215 HUF_decodeStreamX1(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX1* const dt, const U32 dtLog)
216 {
217 BYTE* const pStart = p;
218
219 /* up to 4 symbols at a time */
220 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p < pEnd-3)) {
221 HUF_DECODE_SYMBOLX1_2(p, bitDPtr);
222 HUF_DECODE_SYMBOLX1_1(p, bitDPtr);
223 HUF_DECODE_SYMBOLX1_2(p, bitDPtr);
224 HUF_DECODE_SYMBOLX1_0(p, bitDPtr);
225 }
226
227 /* [0-3] symbols remaining */
228 if (MEM_32bits())
229 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p < pEnd))
230 HUF_DECODE_SYMBOLX1_0(p, bitDPtr);
231
232 /* no more data to retrieve from bitstream, no need to reload */
233 while (p < pEnd)
234 HUF_DECODE_SYMBOLX1_0(p, bitDPtr);
235
236 return pEnd-pStart;
237 }
238
239 FORCE_INLINE_TEMPLATE size_t
240 HUF_decompress1X1_usingDTable_internal_body(
241 void* dst, size_t dstSize,
242 const void* cSrc, size_t cSrcSize,
243 const HUF_DTable* DTable)
244 {
245 BYTE* op = (BYTE*)dst;
246 BYTE* const oend = op + dstSize;
247 const void* dtPtr = DTable + 1;
248 const HUF_DEltX1* const dt = (const HUF_DEltX1*)dtPtr;
249 BIT_DStream_t bitD;
250 DTableDesc const dtd = HUF_getDTableDesc(DTable);
251 U32 const dtLog = dtd.tableLog;
252
253 CHECK_F( BIT_initDStream(&bitD, cSrc, cSrcSize) );
254
255 HUF_decodeStreamX1(op, &bitD, oend, dt, dtLog);
256
257 if (!BIT_endOfDStream(&bitD)) return ERROR(corruption_detected);
258
259 return dstSize;
260 }
261
262 FORCE_INLINE_TEMPLATE size_t
263 HUF_decompress4X1_usingDTable_internal_body(
264 void* dst, size_t dstSize,
265 const void* cSrc, size_t cSrcSize,
266 const HUF_DTable* DTable)
267 {
268 /* Check */
269 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
270
271 { const BYTE* const istart = (const BYTE*) cSrc;
272 BYTE* const ostart = (BYTE*) dst;
273 BYTE* const oend = ostart + dstSize;
274 BYTE* const olimit = oend - 3;
275 const void* const dtPtr = DTable + 1;
276 const HUF_DEltX1* const dt = (const HUF_DEltX1*)dtPtr;
277
278 /* Init */
279 BIT_DStream_t bitD1;
280 BIT_DStream_t bitD2;
281 BIT_DStream_t bitD3;
282 BIT_DStream_t bitD4;
283 size_t const length1 = MEM_readLE16(istart);
284 size_t const length2 = MEM_readLE16(istart+2);
285 size_t const length3 = MEM_readLE16(istart+4);
286 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
287 const BYTE* const istart1 = istart + 6; /* jumpTable */
288 const BYTE* const istart2 = istart1 + length1;
289 const BYTE* const istart3 = istart2 + length2;
290 const BYTE* const istart4 = istart3 + length3;
291 const size_t segmentSize = (dstSize+3) / 4;
292 BYTE* const opStart2 = ostart + segmentSize;
293 BYTE* const opStart3 = opStart2 + segmentSize;
294 BYTE* const opStart4 = opStart3 + segmentSize;
295 BYTE* op1 = ostart;
296 BYTE* op2 = opStart2;
297 BYTE* op3 = opStart3;
298 BYTE* op4 = opStart4;
299 DTableDesc const dtd = HUF_getDTableDesc(DTable);
300 U32 const dtLog = dtd.tableLog;
301 U32 endSignal = 1;
302
303 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
304 CHECK_F( BIT_initDStream(&bitD1, istart1, length1) );
305 CHECK_F( BIT_initDStream(&bitD2, istart2, length2) );
306 CHECK_F( BIT_initDStream(&bitD3, istart3, length3) );
307 CHECK_F( BIT_initDStream(&bitD4, istart4, length4) );
308
309 /* up to 16 symbols per loop (4 symbols per stream) in 64-bit mode */
310 for ( ; (endSignal) & (op4 < olimit) ; ) {
311 HUF_DECODE_SYMBOLX1_2(op1, &bitD1);
312 HUF_DECODE_SYMBOLX1_2(op2, &bitD2);
313 HUF_DECODE_SYMBOLX1_2(op3, &bitD3);
314 HUF_DECODE_SYMBOLX1_2(op4, &bitD4);
315 HUF_DECODE_SYMBOLX1_1(op1, &bitD1);
316 HUF_DECODE_SYMBOLX1_1(op2, &bitD2);
317 HUF_DECODE_SYMBOLX1_1(op3, &bitD3);
318 HUF_DECODE_SYMBOLX1_1(op4, &bitD4);
319 HUF_DECODE_SYMBOLX1_2(op1, &bitD1);
320 HUF_DECODE_SYMBOLX1_2(op2, &bitD2);
321 HUF_DECODE_SYMBOLX1_2(op3, &bitD3);
322 HUF_DECODE_SYMBOLX1_2(op4, &bitD4);
323 HUF_DECODE_SYMBOLX1_0(op1, &bitD1);
324 HUF_DECODE_SYMBOLX1_0(op2, &bitD2);
325 HUF_DECODE_SYMBOLX1_0(op3, &bitD3);
326 HUF_DECODE_SYMBOLX1_0(op4, &bitD4);
327 endSignal &= BIT_reloadDStreamFast(&bitD1) == BIT_DStream_unfinished;
328 endSignal &= BIT_reloadDStreamFast(&bitD2) == BIT_DStream_unfinished;
329 endSignal &= BIT_reloadDStreamFast(&bitD3) == BIT_DStream_unfinished;
330 endSignal &= BIT_reloadDStreamFast(&bitD4) == BIT_DStream_unfinished;
331 }
332
333 /* check corruption */
334 /* note : should not be necessary : op# advance in lock step, and we control op4.
335 * but curiously, binary generated by gcc 7.2 & 7.3 with -mbmi2 runs faster when >=1 test is present */
336 if (op1 > opStart2) return ERROR(corruption_detected);
337 if (op2 > opStart3) return ERROR(corruption_detected);
338 if (op3 > opStart4) return ERROR(corruption_detected);
339 /* note : op4 supposed already verified within main loop */
340
341 /* finish bitStreams one by one */
342 HUF_decodeStreamX1(op1, &bitD1, opStart2, dt, dtLog);
343 HUF_decodeStreamX1(op2, &bitD2, opStart3, dt, dtLog);
344 HUF_decodeStreamX1(op3, &bitD3, opStart4, dt, dtLog);
345 HUF_decodeStreamX1(op4, &bitD4, oend, dt, dtLog);
346
347 /* check */
348 { U32 const endCheck = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
349 if (!endCheck) return ERROR(corruption_detected); }
350
351 /* decoded size */
352 return dstSize;
353 }
354 }
355
356
357 typedef size_t (*HUF_decompress_usingDTable_t)(void *dst, size_t dstSize,
358 const void *cSrc,
359 size_t cSrcSize,
360 const HUF_DTable *DTable);
361
362 HUF_DGEN(HUF_decompress1X1_usingDTable_internal)
363 HUF_DGEN(HUF_decompress4X1_usingDTable_internal)
364
365
366
367 size_t HUF_decompress1X1_usingDTable(
368 void* dst, size_t dstSize,
369 const void* cSrc, size_t cSrcSize,
370 const HUF_DTable* DTable)
371 {
372 DTableDesc dtd = HUF_getDTableDesc(DTable);
373 if (dtd.tableType != 0) return ERROR(GENERIC);
374 return HUF_decompress1X1_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);
375 }
376
377 size_t HUF_decompress1X1_DCtx_wksp(HUF_DTable* DCtx, void* dst, size_t dstSize,
378 const void* cSrc, size_t cSrcSize,
379 void* workSpace, size_t wkspSize)
380 {
381 const BYTE* ip = (const BYTE*) cSrc;
382
383 size_t const hSize = HUF_readDTableX1_wksp(DCtx, cSrc, cSrcSize, workSpace, wkspSize);
384 if (HUF_isError(hSize)) return hSize;
385 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
386 ip += hSize; cSrcSize -= hSize;
387
388 return HUF_decompress1X1_usingDTable_internal(dst, dstSize, ip, cSrcSize, DCtx, /* bmi2 */ 0);
389 }
390
391
392 size_t HUF_decompress1X1_DCtx(HUF_DTable* DCtx, void* dst, size_t dstSize,
393 const void* cSrc, size_t cSrcSize)
394 {
395 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
396 return HUF_decompress1X1_DCtx_wksp(DCtx, dst, dstSize, cSrc, cSrcSize,
397 workSpace, sizeof(workSpace));
398 }
399
400 size_t HUF_decompress1X1 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
401 {
402 HUF_CREATE_STATIC_DTABLEX1(DTable, HUF_TABLELOG_MAX);
403 return HUF_decompress1X1_DCtx (DTable, dst, dstSize, cSrc, cSrcSize);
404 }
405
406 size_t HUF_decompress4X1_usingDTable(
407 void* dst, size_t dstSize,
408 const void* cSrc, size_t cSrcSize,
409 const HUF_DTable* DTable)
410 {
411 DTableDesc dtd = HUF_getDTableDesc(DTable);
412 if (dtd.tableType != 0) return ERROR(GENERIC);
413 return HUF_decompress4X1_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);
414 }
415
416 static size_t HUF_decompress4X1_DCtx_wksp_bmi2(HUF_DTable* dctx, void* dst, size_t dstSize,
417 const void* cSrc, size_t cSrcSize,
418 void* workSpace, size_t wkspSize, int bmi2)
419 {
420 const BYTE* ip = (const BYTE*) cSrc;
421
422 size_t const hSize = HUF_readDTableX1_wksp (dctx, cSrc, cSrcSize,
423 workSpace, wkspSize);
424 if (HUF_isError(hSize)) return hSize;
425 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
426 ip += hSize; cSrcSize -= hSize;
427
428 return HUF_decompress4X1_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx, bmi2);
429 }
430
431 size_t HUF_decompress4X1_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize,
432 const void* cSrc, size_t cSrcSize,
433 void* workSpace, size_t wkspSize)
434 {
435 return HUF_decompress4X1_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, 0);
436 }
437
438
439 size_t HUF_decompress4X1_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
440 {
441 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
442 return HUF_decompress4X1_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize,
443 workSpace, sizeof(workSpace));
444 }
445 size_t HUF_decompress4X1 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
446 {
447 HUF_CREATE_STATIC_DTABLEX1(DTable, HUF_TABLELOG_MAX);
448 return HUF_decompress4X1_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
449 }
450
451 #endif /* HUF_FORCE_DECOMPRESS_X2 */
452
453
454 #ifndef HUF_FORCE_DECOMPRESS_X1
455
456 /* *************************/
457 /* double-symbols decoding */
458 /* *************************/
459
460 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX2; /* double-symbols decoding */
461 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
462 typedef U32 rankValCol_t[HUF_TABLELOG_MAX + 1];
463 typedef rankValCol_t rankVal_t[HUF_TABLELOG_MAX];
464
465
466 /* HUF_fillDTableX2Level2() :
467 * `rankValOrigin` must be a table of at least (HUF_TABLELOG_MAX + 1) U32 */
468 static void HUF_fillDTableX2Level2(HUF_DEltX2* DTable, U32 sizeLog, const U32 consumed,
469 const U32* rankValOrigin, const int minWeight,
470 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
471 U32 nbBitsBaseline, U16 baseSeq)
472 {
473 HUF_DEltX2 DElt;
474 U32 rankVal[HUF_TABLELOG_MAX + 1];
475
476 /* get pre-calculated rankVal */
477 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
478
479 /* fill skipped values */
480 if (minWeight>1) {
481 U32 i, skipSize = rankVal[minWeight];
482 MEM_writeLE16(&(DElt.sequence), baseSeq);
483 DElt.nbBits = (BYTE)(consumed);
484 DElt.length = 1;
485 for (i = 0; i < skipSize; i++)
486 DTable[i] = DElt;
487 }
488
489 /* fill DTable */
490 { U32 s; for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */
491 const U32 symbol = sortedSymbols[s].symbol;
492 const U32 weight = sortedSymbols[s].weight;
493 const U32 nbBits = nbBitsBaseline - weight;
494 const U32 length = 1 << (sizeLog-nbBits);
495 const U32 start = rankVal[weight];
496 U32 i = start;
497 const U32 end = start + length;
498
499 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
500 DElt.nbBits = (BYTE)(nbBits + consumed);
501 DElt.length = 2;
502 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
503
504 rankVal[weight] += length;
505 } }
506 }
507
508
509 static void HUF_fillDTableX2(HUF_DEltX2* DTable, const U32 targetLog,
510 const sortedSymbol_t* sortedList, const U32 sortedListSize,
511 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
512 const U32 nbBitsBaseline)
513 {
514 U32 rankVal[HUF_TABLELOG_MAX + 1];
515 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
516 const U32 minBits = nbBitsBaseline - maxWeight;
517 U32 s;
518
519 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
520
521 /* fill DTable */
522 for (s=0; s<sortedListSize; s++) {
523 const U16 symbol = sortedList[s].symbol;
524 const U32 weight = sortedList[s].weight;
525 const U32 nbBits = nbBitsBaseline - weight;
526 const U32 start = rankVal[weight];
527 const U32 length = 1 << (targetLog-nbBits);
528
529 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */
530 U32 sortedRank;
531 int minWeight = nbBits + scaleLog;
532 if (minWeight < 1) minWeight = 1;
533 sortedRank = rankStart[minWeight];
534 HUF_fillDTableX2Level2(DTable+start, targetLog-nbBits, nbBits,
535 rankValOrigin[nbBits], minWeight,
536 sortedList+sortedRank, sortedListSize-sortedRank,
537 nbBitsBaseline, symbol);
538 } else {
539 HUF_DEltX2 DElt;
540 MEM_writeLE16(&(DElt.sequence), symbol);
541 DElt.nbBits = (BYTE)(nbBits);
542 DElt.length = 1;
543 { U32 const end = start + length;
544 U32 u;
545 for (u = start; u < end; u++) DTable[u] = DElt;
546 } }
547 rankVal[weight] += length;
548 }
549 }
550
551 size_t HUF_readDTableX2_wksp(HUF_DTable* DTable,
552 const void* src, size_t srcSize,
553 void* workSpace, size_t wkspSize)
554 {
555 U32 tableLog, maxW, sizeOfSort, nbSymbols;
556 DTableDesc dtd = HUF_getDTableDesc(DTable);
557 U32 const maxTableLog = dtd.maxTableLog;
558 size_t iSize;
559 void* dtPtr = DTable+1; /* force compiler to avoid strict-aliasing */
560 HUF_DEltX2* const dt = (HUF_DEltX2*)dtPtr;
561 U32 *rankStart;
562
563 rankValCol_t* rankVal;
564 U32* rankStats;
565 U32* rankStart0;
566 sortedSymbol_t* sortedSymbol;
567 BYTE* weightList;
568 size_t spaceUsed32 = 0;
569
570 rankVal = (rankValCol_t *)((U32 *)workSpace + spaceUsed32);
571 spaceUsed32 += (sizeof(rankValCol_t) * HUF_TABLELOG_MAX) >> 2;
572 rankStats = (U32 *)workSpace + spaceUsed32;
573 spaceUsed32 += HUF_TABLELOG_MAX + 1;
574 rankStart0 = (U32 *)workSpace + spaceUsed32;
575 spaceUsed32 += HUF_TABLELOG_MAX + 2;
576 sortedSymbol = (sortedSymbol_t *)workSpace + (spaceUsed32 * sizeof(U32)) / sizeof(sortedSymbol_t);
577 spaceUsed32 += HUF_ALIGN(sizeof(sortedSymbol_t) * (HUF_SYMBOLVALUE_MAX + 1), sizeof(U32)) >> 2;
578 weightList = (BYTE *)((U32 *)workSpace + spaceUsed32);
579 spaceUsed32 += HUF_ALIGN(HUF_SYMBOLVALUE_MAX + 1, sizeof(U32)) >> 2;
580
581 if ((spaceUsed32 << 2) > wkspSize) return ERROR(tableLog_tooLarge);
582
583 rankStart = rankStart0 + 1;
584 memset(rankStats, 0, sizeof(U32) * (2 * HUF_TABLELOG_MAX + 2 + 1));
585
586 DEBUG_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(HUF_DTable)); /* if compiler fails here, assertion is wrong */
587 if (maxTableLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
588 /* memset(weightList, 0, sizeof(weightList)); */ /* is not necessary, even though some analyzer complain ... */
589
590 iSize = HUF_readStats(weightList, HUF_SYMBOLVALUE_MAX + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
591 if (HUF_isError(iSize)) return iSize;
592
593 /* check result */
594 if (tableLog > maxTableLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
595
596 /* find maxWeight */
597 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */
598
599 /* Get start index of each weight */
600 { U32 w, nextRankStart = 0;
601 for (w=1; w<maxW+1; w++) {
602 U32 current = nextRankStart;
603 nextRankStart += rankStats[w];
604 rankStart[w] = current;
605 }
606 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
607 sizeOfSort = nextRankStart;
608 }
609
610 /* sort symbols by weight */
611 { U32 s;
612 for (s=0; s<nbSymbols; s++) {
613 U32 const w = weightList[s];
614 U32 const r = rankStart[w]++;
615 sortedSymbol[r].symbol = (BYTE)s;
616 sortedSymbol[r].weight = (BYTE)w;
617 }
618 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
619 }
620
621 /* Build rankVal */
622 { U32* const rankVal0 = rankVal[0];
623 { int const rescale = (maxTableLog-tableLog) - 1; /* tableLog <= maxTableLog */
624 U32 nextRankVal = 0;
625 U32 w;
626 for (w=1; w<maxW+1; w++) {
627 U32 current = nextRankVal;
628 nextRankVal += rankStats[w] << (w+rescale);
629 rankVal0[w] = current;
630 } }
631 { U32 const minBits = tableLog+1 - maxW;
632 U32 consumed;
633 for (consumed = minBits; consumed < maxTableLog - minBits + 1; consumed++) {
634 U32* const rankValPtr = rankVal[consumed];
635 U32 w;
636 for (w = 1; w < maxW+1; w++) {
637 rankValPtr[w] = rankVal0[w] >> consumed;
638 } } } }
639
640 HUF_fillDTableX2(dt, maxTableLog,
641 sortedSymbol, sizeOfSort,
642 rankStart0, rankVal, maxW,
643 tableLog+1);
644
645 dtd.tableLog = (BYTE)maxTableLog;
646 dtd.tableType = 1;
647 memcpy(DTable, &dtd, sizeof(dtd));
648 return iSize;
649 }
650
651 size_t HUF_readDTableX2(HUF_DTable* DTable, const void* src, size_t srcSize)
652 {
653 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
654 return HUF_readDTableX2_wksp(DTable, src, srcSize,
655 workSpace, sizeof(workSpace));
656 }
657
658
659 FORCE_INLINE_TEMPLATE U32
660 HUF_decodeSymbolX2(void* op, BIT_DStream_t* DStream, const HUF_DEltX2* dt, const U32 dtLog)
661 {
662 size_t const val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
663 memcpy(op, dt+val, 2);
664 BIT_skipBits(DStream, dt[val].nbBits);
665 return dt[val].length;
666 }
667
668 FORCE_INLINE_TEMPLATE U32
669 HUF_decodeLastSymbolX2(void* op, BIT_DStream_t* DStream, const HUF_DEltX2* dt, const U32 dtLog)
670 {
671 size_t const val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
672 memcpy(op, dt+val, 1);
673 if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
674 else {
675 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
676 BIT_skipBits(DStream, dt[val].nbBits);
677 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
678 /* ugly hack; works only because it's the last symbol. Note : can't easily extract nbBits from just this symbol */
679 DStream->bitsConsumed = (sizeof(DStream->bitContainer)*8);
680 } }
681 return 1;
682 }
683
684 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
685 ptr += HUF_decodeSymbolX2(ptr, DStreamPtr, dt, dtLog)
686
687 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
688 if (MEM_64bits() || (HUF_TABLELOG_MAX<=12)) \
689 ptr += HUF_decodeSymbolX2(ptr, DStreamPtr, dt, dtLog)
690
691 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
692 if (MEM_64bits()) \
693 ptr += HUF_decodeSymbolX2(ptr, DStreamPtr, dt, dtLog)
694
695 HINT_INLINE size_t
696 HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd,
697 const HUF_DEltX2* const dt, const U32 dtLog)
698 {
699 BYTE* const pStart = p;
700
701 /* up to 8 symbols at a time */
702 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p < pEnd-(sizeof(bitDPtr->bitContainer)-1))) {
703 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
704 HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
705 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
706 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
707 }
708
709 /* closer to end : up to 2 symbols at a time */
710 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p <= pEnd-2))
711 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
712
713 while (p <= pEnd-2)
714 HUF_DECODE_SYMBOLX2_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
715
716 if (p < pEnd)
717 p += HUF_decodeLastSymbolX2(p, bitDPtr, dt, dtLog);
718
719 return p-pStart;
720 }
721
722 FORCE_INLINE_TEMPLATE size_t
723 HUF_decompress1X2_usingDTable_internal_body(
724 void* dst, size_t dstSize,
725 const void* cSrc, size_t cSrcSize,
726 const HUF_DTable* DTable)
727 {
728 BIT_DStream_t bitD;
729
730 /* Init */
731 CHECK_F( BIT_initDStream(&bitD, cSrc, cSrcSize) );
732
733 /* decode */
734 { BYTE* const ostart = (BYTE*) dst;
735 BYTE* const oend = ostart + dstSize;
736 const void* const dtPtr = DTable+1; /* force compiler to not use strict-aliasing */
737 const HUF_DEltX2* const dt = (const HUF_DEltX2*)dtPtr;
738 DTableDesc const dtd = HUF_getDTableDesc(DTable);
739 HUF_decodeStreamX2(ostart, &bitD, oend, dt, dtd.tableLog);
740 }
741
742 /* check */
743 if (!BIT_endOfDStream(&bitD)) return ERROR(corruption_detected);
744
745 /* decoded size */
746 return dstSize;
747 }
748
749 FORCE_INLINE_TEMPLATE size_t
750 HUF_decompress4X2_usingDTable_internal_body(
751 void* dst, size_t dstSize,
752 const void* cSrc, size_t cSrcSize,
753 const HUF_DTable* DTable)
754 {
755 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
756
757 { const BYTE* const istart = (const BYTE*) cSrc;
758 BYTE* const ostart = (BYTE*) dst;
759 BYTE* const oend = ostart + dstSize;
760 BYTE* const olimit = oend - (sizeof(size_t)-1);
761 const void* const dtPtr = DTable+1;
762 const HUF_DEltX2* const dt = (const HUF_DEltX2*)dtPtr;
763
764 /* Init */
765 BIT_DStream_t bitD1;
766 BIT_DStream_t bitD2;
767 BIT_DStream_t bitD3;
768 BIT_DStream_t bitD4;
769 size_t const length1 = MEM_readLE16(istart);
770 size_t const length2 = MEM_readLE16(istart+2);
771 size_t const length3 = MEM_readLE16(istart+4);
772 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
773 const BYTE* const istart1 = istart + 6; /* jumpTable */
774 const BYTE* const istart2 = istart1 + length1;
775 const BYTE* const istart3 = istart2 + length2;
776 const BYTE* const istart4 = istart3 + length3;
777 size_t const segmentSize = (dstSize+3) / 4;
778 BYTE* const opStart2 = ostart + segmentSize;
779 BYTE* const opStart3 = opStart2 + segmentSize;
780 BYTE* const opStart4 = opStart3 + segmentSize;
781 BYTE* op1 = ostart;
782 BYTE* op2 = opStart2;
783 BYTE* op3 = opStart3;
784 BYTE* op4 = opStart4;
785 U32 endSignal = 1;
786 DTableDesc const dtd = HUF_getDTableDesc(DTable);
787 U32 const dtLog = dtd.tableLog;
788
789 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
790 CHECK_F( BIT_initDStream(&bitD1, istart1, length1) );
791 CHECK_F( BIT_initDStream(&bitD2, istart2, length2) );
792 CHECK_F( BIT_initDStream(&bitD3, istart3, length3) );
793 CHECK_F( BIT_initDStream(&bitD4, istart4, length4) );
794
795 /* 16-32 symbols per loop (4-8 symbols per stream) */
796 for ( ; (endSignal) & (op4 < olimit); ) {
797 #if defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
798 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
799 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
800 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
801 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
802 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
803 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
804 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
805 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
806 endSignal &= BIT_reloadDStreamFast(&bitD1) == BIT_DStream_unfinished;
807 endSignal &= BIT_reloadDStreamFast(&bitD2) == BIT_DStream_unfinished;
808 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
809 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
810 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
811 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
812 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
813 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
814 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
815 HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
816 endSignal &= BIT_reloadDStreamFast(&bitD3) == BIT_DStream_unfinished;
817 endSignal &= BIT_reloadDStreamFast(&bitD4) == BIT_DStream_unfinished;
818 #else
819 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
820 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
821 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
822 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
823 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
824 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
825 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
826 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
827 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
828 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
829 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
830 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
831 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
832 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
833 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
834 HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
835 endSignal = (U32)LIKELY(
836 (BIT_reloadDStreamFast(&bitD1) == BIT_DStream_unfinished)
837 & (BIT_reloadDStreamFast(&bitD2) == BIT_DStream_unfinished)
838 & (BIT_reloadDStreamFast(&bitD3) == BIT_DStream_unfinished)
839 & (BIT_reloadDStreamFast(&bitD4) == BIT_DStream_unfinished));
840 #endif
841 }
842
843 /* check corruption */
844 if (op1 > opStart2) return ERROR(corruption_detected);
845 if (op2 > opStart3) return ERROR(corruption_detected);
846 if (op3 > opStart4) return ERROR(corruption_detected);
847 /* note : op4 already verified within main loop */
848
849 /* finish bitStreams one by one */
850 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
851 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
852 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
853 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
854
855 /* check */
856 { U32 const endCheck = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
857 if (!endCheck) return ERROR(corruption_detected); }
858
859 /* decoded size */
860 return dstSize;
861 }
862 }
863
864 HUF_DGEN(HUF_decompress1X2_usingDTable_internal)
865 HUF_DGEN(HUF_decompress4X2_usingDTable_internal)
866
867 size_t HUF_decompress1X2_usingDTable(
868 void* dst, size_t dstSize,
869 const void* cSrc, size_t cSrcSize,
870 const HUF_DTable* DTable)
871 {
872 DTableDesc dtd = HUF_getDTableDesc(DTable);
873 if (dtd.tableType != 1) return ERROR(GENERIC);
874 return HUF_decompress1X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);
875 }
876
877 size_t HUF_decompress1X2_DCtx_wksp(HUF_DTable* DCtx, void* dst, size_t dstSize,
878 const void* cSrc, size_t cSrcSize,
879 void* workSpace, size_t wkspSize)
880 {
881 const BYTE* ip = (const BYTE*) cSrc;
882
883 size_t const hSize = HUF_readDTableX2_wksp(DCtx, cSrc, cSrcSize,
884 workSpace, wkspSize);
885 if (HUF_isError(hSize)) return hSize;
886 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
887 ip += hSize; cSrcSize -= hSize;
888
889 return HUF_decompress1X2_usingDTable_internal(dst, dstSize, ip, cSrcSize, DCtx, /* bmi2 */ 0);
890 }
891
892
893 size_t HUF_decompress1X2_DCtx(HUF_DTable* DCtx, void* dst, size_t dstSize,
894 const void* cSrc, size_t cSrcSize)
895 {
896 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
897 return HUF_decompress1X2_DCtx_wksp(DCtx, dst, dstSize, cSrc, cSrcSize,
898 workSpace, sizeof(workSpace));
899 }
900
901 size_t HUF_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
902 {
903 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_TABLELOG_MAX);
904 return HUF_decompress1X2_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
905 }
906
907 size_t HUF_decompress4X2_usingDTable(
908 void* dst, size_t dstSize,
909 const void* cSrc, size_t cSrcSize,
910 const HUF_DTable* DTable)
911 {
912 DTableDesc dtd = HUF_getDTableDesc(DTable);
913 if (dtd.tableType != 1) return ERROR(GENERIC);
914 return HUF_decompress4X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);
915 }
916
917 static size_t HUF_decompress4X2_DCtx_wksp_bmi2(HUF_DTable* dctx, void* dst, size_t dstSize,
918 const void* cSrc, size_t cSrcSize,
919 void* workSpace, size_t wkspSize, int bmi2)
920 {
921 const BYTE* ip = (const BYTE*) cSrc;
922
923 size_t hSize = HUF_readDTableX2_wksp(dctx, cSrc, cSrcSize,
924 workSpace, wkspSize);
925 if (HUF_isError(hSize)) return hSize;
926 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
927 ip += hSize; cSrcSize -= hSize;
928
929 return HUF_decompress4X2_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx, bmi2);
930 }
931
932 size_t HUF_decompress4X2_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize,
933 const void* cSrc, size_t cSrcSize,
934 void* workSpace, size_t wkspSize)
935 {
936 return HUF_decompress4X2_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, /* bmi2 */ 0);
937 }
938
939
940 size_t HUF_decompress4X2_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize,
941 const void* cSrc, size_t cSrcSize)
942 {
943 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
944 return HUF_decompress4X2_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize,
945 workSpace, sizeof(workSpace));
946 }
947
948 size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
949 {
950 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_TABLELOG_MAX);
951 return HUF_decompress4X2_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
952 }
953
954 #endif /* HUF_FORCE_DECOMPRESS_X1 */
955
956
957 /* ***********************************/
958 /* Universal decompression selectors */
959 /* ***********************************/
960
961 size_t HUF_decompress1X_usingDTable(void* dst, size_t maxDstSize,
962 const void* cSrc, size_t cSrcSize,
963 const HUF_DTable* DTable)
964 {
965 DTableDesc const dtd = HUF_getDTableDesc(DTable);
966 #if defined(HUF_FORCE_DECOMPRESS_X1)
967 (void)dtd;
968 assert(dtd.tableType == 0);
969 return HUF_decompress1X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);
970 #elif defined(HUF_FORCE_DECOMPRESS_X2)
971 (void)dtd;
972 assert(dtd.tableType == 1);
973 return HUF_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);
974 #else
975 return dtd.tableType ? HUF_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0) :
976 HUF_decompress1X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);
977 #endif
978 }
979
980 size_t HUF_decompress4X_usingDTable(void* dst, size_t maxDstSize,
981 const void* cSrc, size_t cSrcSize,
982 const HUF_DTable* DTable)
983 {
984 DTableDesc const dtd = HUF_getDTableDesc(DTable);
985 #if defined(HUF_FORCE_DECOMPRESS_X1)
986 (void)dtd;
987 assert(dtd.tableType == 0);
988 return HUF_decompress4X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);
989 #elif defined(HUF_FORCE_DECOMPRESS_X2)
990 (void)dtd;
991 assert(dtd.tableType == 1);
992 return HUF_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);
993 #else
994 return dtd.tableType ? HUF_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0) :
995 HUF_decompress4X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);
996 #endif
997 }
998
999
1000 #if !defined(HUF_FORCE_DECOMPRESS_X1) && !defined(HUF_FORCE_DECOMPRESS_X2)
1001 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
1002 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
1003 {
1004 /* single, double, quad */
1005 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
1006 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
1007 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
1008 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
1009 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
1010 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
1011 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
1012 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
1013 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
1014 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
1015 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
1016 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
1017 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
1018 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
1019 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
1020 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
1021 };
1022 #endif
1023
1024 /** HUF_selectDecoder() :
1025 * Tells which decoder is likely to decode faster,
1026 * based on a set of pre-computed metrics.
1027 * @return : 0==HUF_decompress4X1, 1==HUF_decompress4X2 .
1028 * Assumption : 0 < dstSize <= 128 KB */
1029 U32 HUF_selectDecoder (size_t dstSize, size_t cSrcSize)
1030 {
1031 assert(dstSize > 0);
1032 assert(dstSize <= 128*1024);
1033 #if defined(HUF_FORCE_DECOMPRESS_X1)
1034 (void)dstSize;
1035 (void)cSrcSize;
1036 return 0;
1037 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1038 (void)dstSize;
1039 (void)cSrcSize;
1040 return 1;
1041 #else
1042 /* decoder timing evaluation */
1043 { U32 const Q = (cSrcSize >= dstSize) ? 15 : (U32)(cSrcSize * 16 / dstSize); /* Q < 16 */
1044 U32 const D256 = (U32)(dstSize >> 8);
1045 U32 const DTime0 = algoTime[Q][0].tableTime + (algoTime[Q][0].decode256Time * D256);
1046 U32 DTime1 = algoTime[Q][1].tableTime + (algoTime[Q][1].decode256Time * D256);
1047 DTime1 += DTime1 >> 3; /* advantage to algorithm using less memory, to reduce cache eviction */
1048 return DTime1 < DTime0;
1049 }
1050 #endif
1051 }
1052
1053
1054 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
1055
1056 size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1057 {
1058 #if !defined(HUF_FORCE_DECOMPRESS_X1) && !defined(HUF_FORCE_DECOMPRESS_X2)
1059 static const decompressionAlgo decompress[2] = { HUF_decompress4X1, HUF_decompress4X2 };
1060 #endif
1061
1062 /* validation checks */
1063 if (dstSize == 0) return ERROR(dstSize_tooSmall);
1064 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
1065 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
1066 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
1067
1068 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
1069 #if defined(HUF_FORCE_DECOMPRESS_X1)
1070 (void)algoNb;
1071 assert(algoNb == 0);
1072 return HUF_decompress4X1(dst, dstSize, cSrc, cSrcSize);
1073 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1074 (void)algoNb;
1075 assert(algoNb == 1);
1076 return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize);
1077 #else
1078 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
1079 #endif
1080 }
1081 }
1082
1083 size_t HUF_decompress4X_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1084 {
1085 /* validation checks */
1086 if (dstSize == 0) return ERROR(dstSize_tooSmall);
1087 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
1088 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
1089 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
1090
1091 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
1092 #if defined(HUF_FORCE_DECOMPRESS_X1)
1093 (void)algoNb;
1094 assert(algoNb == 0);
1095 return HUF_decompress4X1_DCtx(dctx, dst, dstSize, cSrc, cSrcSize);
1096 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1097 (void)algoNb;
1098 assert(algoNb == 1);
1099 return HUF_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize);
1100 #else
1101 return algoNb ? HUF_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
1102 HUF_decompress4X1_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
1103 #endif
1104 }
1105 }
1106
1107 size_t HUF_decompress4X_hufOnly(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1108 {
1109 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
1110 return HUF_decompress4X_hufOnly_wksp(dctx, dst, dstSize, cSrc, cSrcSize,
1111 workSpace, sizeof(workSpace));
1112 }
1113
1114
1115 size_t HUF_decompress4X_hufOnly_wksp(HUF_DTable* dctx, void* dst,
1116 size_t dstSize, const void* cSrc,
1117 size_t cSrcSize, void* workSpace,
1118 size_t wkspSize)
1119 {
1120 /* validation checks */
1121 if (dstSize == 0) return ERROR(dstSize_tooSmall);
1122 if (cSrcSize == 0) return ERROR(corruption_detected);
1123
1124 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
1125 #if defined(HUF_FORCE_DECOMPRESS_X1)
1126 (void)algoNb;
1127 assert(algoNb == 0);
1128 return HUF_decompress4X1_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize);
1129 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1130 (void)algoNb;
1131 assert(algoNb == 1);
1132 return HUF_decompress4X2_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize);
1133 #else
1134 return algoNb ? HUF_decompress4X2_DCtx_wksp(dctx, dst, dstSize, cSrc,
1135 cSrcSize, workSpace, wkspSize):
1136 HUF_decompress4X1_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize);
1137 #endif
1138 }
1139 }
1140
1141 size_t HUF_decompress1X_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize,
1142 const void* cSrc, size_t cSrcSize,
1143 void* workSpace, size_t wkspSize)
1144 {
1145 /* validation checks */
1146 if (dstSize == 0) return ERROR(dstSize_tooSmall);
1147 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
1148 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
1149 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
1150
1151 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
1152 #if defined(HUF_FORCE_DECOMPRESS_X1)
1153 (void)algoNb;
1154 assert(algoNb == 0);
1155 return HUF_decompress1X1_DCtx_wksp(dctx, dst, dstSize, cSrc,
1156 cSrcSize, workSpace, wkspSize);
1157 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1158 (void)algoNb;
1159 assert(algoNb == 1);
1160 return HUF_decompress1X2_DCtx_wksp(dctx, dst, dstSize, cSrc,
1161 cSrcSize, workSpace, wkspSize);
1162 #else
1163 return algoNb ? HUF_decompress1X2_DCtx_wksp(dctx, dst, dstSize, cSrc,
1164 cSrcSize, workSpace, wkspSize):
1165 HUF_decompress1X1_DCtx_wksp(dctx, dst, dstSize, cSrc,
1166 cSrcSize, workSpace, wkspSize);
1167 #endif
1168 }
1169 }
1170
1171 size_t HUF_decompress1X_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize,
1172 const void* cSrc, size_t cSrcSize)
1173 {
1174 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
1175 return HUF_decompress1X_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize,
1176 workSpace, sizeof(workSpace));
1177 }
1178
1179
1180 size_t HUF_decompress1X_usingDTable_bmi2(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, int bmi2)
1181 {
1182 DTableDesc const dtd = HUF_getDTableDesc(DTable);
1183 #if defined(HUF_FORCE_DECOMPRESS_X1)
1184 (void)dtd;
1185 assert(dtd.tableType == 0);
1186 return HUF_decompress1X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);
1187 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1188 (void)dtd;
1189 assert(dtd.tableType == 1);
1190 return HUF_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);
1191 #else
1192 return dtd.tableType ? HUF_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2) :
1193 HUF_decompress1X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);
1194 #endif
1195 }
1196
1197 #ifndef HUF_FORCE_DECOMPRESS_X2
1198 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)
1199 {
1200 const BYTE* ip = (const BYTE*) cSrc;
1201
1202 size_t const hSize = HUF_readDTableX1_wksp(dctx, cSrc, cSrcSize, workSpace, wkspSize);
1203 if (HUF_isError(hSize)) return hSize;
1204 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
1205 ip += hSize; cSrcSize -= hSize;
1206
1207 return HUF_decompress1X1_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx, bmi2);
1208 }
1209 #endif
1210
1211 size_t HUF_decompress4X_usingDTable_bmi2(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, int bmi2)
1212 {
1213 DTableDesc const dtd = HUF_getDTableDesc(DTable);
1214 #if defined(HUF_FORCE_DECOMPRESS_X1)
1215 (void)dtd;
1216 assert(dtd.tableType == 0);
1217 return HUF_decompress4X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);
1218 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1219 (void)dtd;
1220 assert(dtd.tableType == 1);
1221 return HUF_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);
1222 #else
1223 return dtd.tableType ? HUF_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2) :
1224 HUF_decompress4X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);
1225 #endif
1226 }
1227
1228 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)
1229 {
1230 /* validation checks */
1231 if (dstSize == 0) return ERROR(dstSize_tooSmall);
1232 if (cSrcSize == 0) return ERROR(corruption_detected);
1233
1234 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
1235 #if defined(HUF_FORCE_DECOMPRESS_X1)
1236 (void)algoNb;
1237 assert(algoNb == 0);
1238 return HUF_decompress4X1_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, bmi2);
1239 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1240 (void)algoNb;
1241 assert(algoNb == 1);
1242 return HUF_decompress4X2_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, bmi2);
1243 #else
1244 return algoNb ? HUF_decompress4X2_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, bmi2) :
1245 HUF_decompress4X1_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, bmi2);
1246 #endif
1247 }
1248 }
OpenZFS on Linux and FreeBSD