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