1 /* ******************************************************************
3 part of Finite State Entropy library
4 Copyright (C) 2013-present, Yann Collet.
6 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions are
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
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.
31 You can contact the author at :
32 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
33 ****************************************************************** */
35 /* **************************************************************
37 ****************************************************************/
38 #include <string.h> /* memcpy, memset */
40 #include "bitstream.h" /* BIT_* */
41 #include "fse.h" /* to compress headers */
42 #define HUF_STATIC_LINKING_ONLY
44 #include "error_private.h"
46 /* **************************************************************
48 ****************************************************************/
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
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!"
60 /* **************************************************************
62 ****************************************************************/
63 #define HUF_isError ERR_isError
64 #define CHECK_F(f) { size_t const err_ = (f); if (HUF_isError(err_)) return err_; }
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))
74 /* **************************************************************
75 * BMI2 Variant Wrappers
76 ****************************************************************/
79 #define HUF_DGEN(fn) \
81 static size_t fn##_default( \
82 void* dst, size_t dstSize, \
83 const void* cSrc, size_t cSrcSize, \
84 const HUF_DTable* DTable) \
86 return fn##_body(dst, dstSize, cSrc, cSrcSize, DTable); \
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) \
94 return fn##_body(dst, dstSize, cSrc, cSrcSize, DTable); \
97 static size_t fn(void* dst, size_t dstSize, void const* cSrc, \
98 size_t cSrcSize, HUF_DTable const* DTable, int bmi2) \
101 return fn##_bmi2(dst, dstSize, cSrc, cSrcSize, DTable); \
103 return fn##_default(dst, dstSize, cSrc, cSrcSize, DTable); \
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) \
113 return fn##_body(dst, dstSize, cSrc, cSrcSize, DTable); \
119 /*-***************************/
120 /* generic DTableDesc */
121 /*-***************************/
122 typedef struct { BYTE maxTableLog; BYTE tableType; BYTE tableLog; BYTE reserved; } DTableDesc;
124 static DTableDesc HUF_getDTableDesc(const HUF_DTable* table)
127 memcpy(&dtd, table, sizeof(dtd));
132 #ifndef HUF_FORCE_DECOMPRESS_X2
134 /*-***************************/
135 /* single-symbol decoding */
136 /*-***************************/
137 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX1; /* single-symbol decoding */
139 size_t HUF_readDTableX1_wksp(HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize)
144 void* const dtPtr = DTable + 1;
145 HUF_DEltX1* const dt = (HUF_DEltX1*)dtPtr;
149 size_t spaceUsed32 = 0;
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;
156 if ((spaceUsed32 << 2) > wkspSize) return ERROR(tableLog_tooLarge);
158 DEBUG_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUF_DTable));
159 /* memset(huffWeight, 0, sizeof(huffWeight)); */ /* is not necessary, even though some analyzer complain ... */
161 iSize = HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
162 if (HUF_isError(iSize)) return iSize;
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 */
168 dtd.tableLog = (BYTE)tableLog;
169 memcpy(DTable, &dtd, sizeof(dtd));
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;
182 for (n=0; n<nbSymbols; n++) {
183 U32 const w = huffWeight[n];
184 U32 const length = (1 << w) >> 1;
187 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
188 for (u = rankVal[w]; u < rankVal[w] + length; u++)
190 rankVal[w] += length;
196 size_t HUF_readDTableX1(HUF_DTable* DTable, const void* src, size_t srcSize)
198 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
199 return HUF_readDTableX1_wksp(DTable, src, srcSize,
200 workSpace, sizeof(workSpace));
203 FORCE_INLINE_TEMPLATE BYTE
204 HUF_decodeSymbolX1(BIT_DStream_t* Dstream, const HUF_DEltX1* dt, const U32 dtLog)
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);
212 #define HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr) \
213 *ptr++ = HUF_decodeSymbolX1(DStreamPtr, dt, dtLog)
215 #define HUF_DECODE_SYMBOLX1_1(ptr, DStreamPtr) \
216 if (MEM_64bits() || (HUF_TABLELOG_MAX<=12)) \
217 HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr)
219 #define HUF_DECODE_SYMBOLX1_2(ptr, DStreamPtr) \
221 HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr)
224 HUF_decodeStreamX1(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX1* const dt, const U32 dtLog)
226 BYTE* const pStart = p;
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);
236 /* [0-3] symbols remaining */
238 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p < pEnd))
239 HUF_DECODE_SYMBOLX1_0(p, bitDPtr);
241 /* no more data to retrieve from bitstream, no need to reload */
243 HUF_DECODE_SYMBOLX1_0(p, bitDPtr);
248 FORCE_INLINE_TEMPLATE size_t
249 HUF_decompress1X1_usingDTable_internal_body(
250 void* dst, size_t dstSize,
251 const void* cSrc, size_t cSrcSize,
252 const HUF_DTable* DTable)
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;
259 DTableDesc const dtd = HUF_getDTableDesc(DTable);
260 U32 const dtLog = dtd.tableLog;
262 CHECK_F( BIT_initDStream(&bitD, cSrc, cSrcSize) );
264 HUF_decodeStreamX1(op, &bitD, oend, dt, dtLog);
266 if (!BIT_endOfDStream(&bitD)) return ERROR(corruption_detected);
271 FORCE_INLINE_TEMPLATE size_t
272 HUF_decompress4X1_usingDTable_internal_body(
273 void* dst, size_t dstSize,
274 const void* cSrc, size_t cSrcSize,
275 const HUF_DTable* DTable)
278 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
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;
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;
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;
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) );
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);
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 */
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);
357 { U32 const endCheck = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
358 if (!endCheck) return ERROR(corruption_detected); }
366 typedef size_t (*HUF_decompress_usingDTable_t)(void *dst, size_t dstSize,
369 const HUF_DTable *DTable);
371 HUF_DGEN(HUF_decompress1X1_usingDTable_internal)
372 HUF_DGEN(HUF_decompress4X1_usingDTable_internal)
376 size_t HUF_decompress1X1_usingDTable(
377 void* dst, size_t dstSize,
378 const void* cSrc, size_t cSrcSize,
379 const HUF_DTable* DTable)
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);
386 size_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)
390 const BYTE* ip = (const BYTE*) cSrc;
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;
397 return HUF_decompress1X1_usingDTable_internal(dst, dstSize, ip, cSrcSize, DCtx, /* bmi2 */ 0);
401 size_t HUF_decompress1X1_DCtx(HUF_DTable* DCtx, void* dst, size_t dstSize,
402 const void* cSrc, size_t cSrcSize)
404 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
405 return HUF_decompress1X1_DCtx_wksp(DCtx, dst, dstSize, cSrc, cSrcSize,
406 workSpace, sizeof(workSpace));
409 size_t HUF_decompress1X1 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
411 HUF_CREATE_STATIC_DTABLEX1(DTable, HUF_TABLELOG_MAX);
412 return HUF_decompress1X1_DCtx (DTable, dst, dstSize, cSrc, cSrcSize);
415 size_t HUF_decompress4X1_usingDTable(
416 void* dst, size_t dstSize,
417 const void* cSrc, size_t cSrcSize,
418 const HUF_DTable* DTable)
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);
425 static 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)
429 const BYTE* ip = (const BYTE*) cSrc;
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;
437 return HUF_decompress4X1_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx, bmi2);
440 size_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)
444 return HUF_decompress4X1_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, 0);
448 size_t HUF_decompress4X1_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
450 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
451 return HUF_decompress4X1_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize,
452 workSpace, sizeof(workSpace));
454 size_t HUF_decompress4X1 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
456 HUF_CREATE_STATIC_DTABLEX1(DTable, HUF_TABLELOG_MAX);
457 return HUF_decompress4X1_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
460 #endif /* HUF_FORCE_DECOMPRESS_X2 */
463 #ifndef HUF_FORCE_DECOMPRESS_X1
465 /* *************************/
466 /* double-symbols decoding */
467 /* *************************/
469 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX2; /* double-symbols decoding */
470 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
471 typedef U32 rankValCol_t[HUF_TABLELOG_MAX + 1];
472 typedef rankValCol_t rankVal_t[HUF_TABLELOG_MAX];
475 /* HUF_fillDTableX2Level2() :
476 * `rankValOrigin` must be a table of at least (HUF_TABLELOG_MAX + 1) U32 */
477 static 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)
483 U32 rankVal[HUF_TABLELOG_MAX + 1];
485 /* get pre-calculated rankVal */
486 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
488 /* fill skipped values */
490 U32 i, skipSize = rankVal[minWeight];
491 MEM_writeLE16(&(DElt.sequence), baseSeq);
492 DElt.nbBits = (BYTE)(consumed);
494 for (i = 0; i < skipSize; i++)
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];
506 const U32 end = start + length;
508 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
509 DElt.nbBits = (BYTE)(nbBits + consumed);
511 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
513 rankVal[weight] += length;
518 static 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)
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;
528 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
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);
538 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */
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);
549 MEM_writeLE16(&(DElt.sequence), symbol);
550 DElt.nbBits = (BYTE)(nbBits);
552 { U32 const end = start + length;
554 for (u = start; u < end; u++) DTable[u] = DElt;
556 rankVal[weight] += length;
560 size_t HUF_readDTableX2_wksp(HUF_DTable* DTable,
561 const void* src, size_t srcSize,
562 void* workSpace, size_t wkspSize)
564 U32 tableLog, maxW, sizeOfSort, nbSymbols;
565 DTableDesc dtd = HUF_getDTableDesc(DTable);
566 U32 const maxTableLog = dtd.maxTableLog;
568 void* dtPtr = DTable+1; /* force compiler to avoid strict-aliasing */
569 HUF_DEltX2* const dt = (HUF_DEltX2*)dtPtr;
572 rankValCol_t* rankVal;
575 sortedSymbol_t* sortedSymbol;
577 size_t spaceUsed32 = 0;
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;
590 if ((spaceUsed32 << 2) > wkspSize) return ERROR(tableLog_tooLarge);
592 rankStart = rankStart0 + 1;
593 memset(rankStats, 0, sizeof(U32) * (2 * HUF_TABLELOG_MAX + 2 + 1));
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 ... */
599 iSize = HUF_readStats(weightList, HUF_SYMBOLVALUE_MAX + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
600 if (HUF_isError(iSize)) return iSize;
603 if (tableLog > maxTableLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
606 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */
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;
615 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
616 sizeOfSort = nextRankStart;
619 /* sort symbols by weight */
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;
627 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
631 { U32* const rankVal0 = rankVal[0];
632 { int const rescale = (maxTableLog-tableLog) - 1; /* tableLog <= maxTableLog */
635 for (w=1; w<maxW+1; w++) {
636 U32 current = nextRankVal;
637 nextRankVal += rankStats[w] << (w+rescale);
638 rankVal0[w] = current;
640 { U32 const minBits = tableLog+1 - maxW;
642 for (consumed = minBits; consumed < maxTableLog - minBits + 1; consumed++) {
643 U32* const rankValPtr = rankVal[consumed];
645 for (w = 1; w < maxW+1; w++) {
646 rankValPtr[w] = rankVal0[w] >> consumed;
649 HUF_fillDTableX2(dt, maxTableLog,
650 sortedSymbol, sizeOfSort,
651 rankStart0, rankVal, maxW,
654 dtd.tableLog = (BYTE)maxTableLog;
656 memcpy(DTable, &dtd, sizeof(dtd));
660 size_t HUF_readDTableX2(HUF_DTable* DTable, const void* src, size_t srcSize)
662 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
663 return HUF_readDTableX2_wksp(DTable, src, srcSize,
664 workSpace, sizeof(workSpace));
668 FORCE_INLINE_TEMPLATE U32
669 HUF_decodeSymbolX2(void* op, BIT_DStream_t* DStream, const HUF_DEltX2* dt, const U32 dtLog)
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;
677 FORCE_INLINE_TEMPLATE U32
678 HUF_decodeLastSymbolX2(void* op, BIT_DStream_t* DStream, const HUF_DEltX2* dt, const U32 dtLog)
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);
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);
693 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
694 ptr += HUF_decodeSymbolX2(ptr, DStreamPtr, dt, dtLog)
696 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
697 if (MEM_64bits() || (HUF_TABLELOG_MAX<=12)) \
698 ptr += HUF_decodeSymbolX2(ptr, DStreamPtr, dt, dtLog)
700 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
702 ptr += HUF_decodeSymbolX2(ptr, DStreamPtr, dt, dtLog)
705 HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd,
706 const HUF_DEltX2* const dt, const U32 dtLog)
708 BYTE* const pStart = p;
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);
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);
723 HUF_DECODE_SYMBOLX2_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
726 p += HUF_decodeLastSymbolX2(p, bitDPtr, dt, dtLog);
731 FORCE_INLINE_TEMPLATE size_t
732 HUF_decompress1X2_usingDTable_internal_body(
733 void* dst, size_t dstSize,
734 const void* cSrc, size_t cSrcSize,
735 const HUF_DTable* DTable)
740 CHECK_F( BIT_initDStream(&bitD, cSrc, cSrcSize) );
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);
752 if (!BIT_endOfDStream(&bitD)) return ERROR(corruption_detected);
759 FORCE_INLINE_TEMPLATE size_t
760 HUF_decompress4X2_usingDTable_internal_body(
761 void* dst, size_t dstSize,
762 const void* cSrc, size_t cSrcSize,
763 const HUF_DTable* DTable)
765 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
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;
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;
791 BYTE* op2 = opStart2;
792 BYTE* op3 = opStart3;
793 BYTE* op4 = opStart4;
795 DTableDesc const dtd = HUF_getDTableDesc(DTable);
796 U32 const dtLog = dtd.tableLog;
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) );
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);
824 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
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 */
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);
840 { U32 const endCheck = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
841 if (!endCheck) return ERROR(corruption_detected); }
848 HUF_DGEN(HUF_decompress1X2_usingDTable_internal)
849 HUF_DGEN(HUF_decompress4X2_usingDTable_internal)
851 size_t HUF_decompress1X2_usingDTable(
852 void* dst, size_t dstSize,
853 const void* cSrc, size_t cSrcSize,
854 const HUF_DTable* DTable)
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);
861 size_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)
865 const BYTE* ip = (const BYTE*) cSrc;
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;
873 return HUF_decompress1X2_usingDTable_internal(dst, dstSize, ip, cSrcSize, DCtx, /* bmi2 */ 0);
877 size_t HUF_decompress1X2_DCtx(HUF_DTable* DCtx, void* dst, size_t dstSize,
878 const void* cSrc, size_t cSrcSize)
880 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
881 return HUF_decompress1X2_DCtx_wksp(DCtx, dst, dstSize, cSrc, cSrcSize,
882 workSpace, sizeof(workSpace));
885 size_t HUF_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
887 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_TABLELOG_MAX);
888 return HUF_decompress1X2_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
891 size_t HUF_decompress4X2_usingDTable(
892 void* dst, size_t dstSize,
893 const void* cSrc, size_t cSrcSize,
894 const HUF_DTable* DTable)
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);
901 static 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)
905 const BYTE* ip = (const BYTE*) cSrc;
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;
913 return HUF_decompress4X2_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx, bmi2);
916 size_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)
920 return HUF_decompress4X2_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, /* bmi2 */ 0);
924 size_t HUF_decompress4X2_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize,
925 const void* cSrc, size_t cSrcSize)
927 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
928 return HUF_decompress4X2_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize,
929 workSpace, sizeof(workSpace));
932 size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
934 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_TABLELOG_MAX);
935 return HUF_decompress4X2_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
938 #endif /* HUF_FORCE_DECOMPRESS_X1 */
941 /* ***********************************/
942 /* Universal decompression selectors */
943 /* ***********************************/
945 size_t HUF_decompress1X_usingDTable(void* dst, size_t maxDstSize,
946 const void* cSrc, size_t cSrcSize,
947 const HUF_DTable* DTable)
949 DTableDesc const dtd = HUF_getDTableDesc(DTable);
950 #if defined(HUF_FORCE_DECOMPRESS_X1)
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)
956 assert(dtd.tableType == 1);
957 return HUF_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);
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);
964 size_t HUF_decompress4X_usingDTable(void* dst, size_t maxDstSize,
965 const void* cSrc, size_t cSrcSize,
966 const HUF_DTable* DTable)
968 DTableDesc const dtd = HUF_getDTableDesc(DTable);
969 #if defined(HUF_FORCE_DECOMPRESS_X1)
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)
975 assert(dtd.tableType == 1);
976 return HUF_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);
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);
984 #if !defined(HUF_FORCE_DECOMPRESS_X1) && !defined(HUF_FORCE_DECOMPRESS_X2)
985 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
986 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
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% */
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 */
1013 U32 HUF_selectDecoder (size_t dstSize, size_t cSrcSize)
1015 assert(dstSize > 0);
1016 assert(dstSize <= 128*1024);
1017 #if defined(HUF_FORCE_DECOMPRESS_X1)
1021 #elif defined(HUF_FORCE_DECOMPRESS_X2)
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;
1038 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
1040 size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1042 #if !defined(HUF_FORCE_DECOMPRESS_X1) && !defined(HUF_FORCE_DECOMPRESS_X2)
1043 static const decompressionAlgo decompress[2] = { HUF_decompress4X1, HUF_decompress4X2 };
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 */
1052 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
1053 #if defined(HUF_FORCE_DECOMPRESS_X1)
1055 assert(algoNb == 0);
1056 return HUF_decompress4X1(dst, dstSize, cSrc, cSrcSize);
1057 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1059 assert(algoNb == 1);
1060 return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize);
1062 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
1067 size_t HUF_decompress4X_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
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 */
1075 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
1076 #if defined(HUF_FORCE_DECOMPRESS_X1)
1078 assert(algoNb == 0);
1079 return HUF_decompress4X1_DCtx(dctx, dst, dstSize, cSrc, cSrcSize);
1080 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1082 assert(algoNb == 1);
1083 return HUF_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize);
1085 return algoNb ? HUF_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
1086 HUF_decompress4X1_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
1091 size_t HUF_decompress4X_hufOnly(HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1093 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
1094 return HUF_decompress4X_hufOnly_wksp(dctx, dst, dstSize, cSrc, cSrcSize,
1095 workSpace, sizeof(workSpace));
1099 size_t HUF_decompress4X_hufOnly_wksp(HUF_DTable* dctx, void* dst,
1100 size_t dstSize, const void* cSrc,
1101 size_t cSrcSize, void* workSpace,
1104 /* validation checks */
1105 if (dstSize == 0) return ERROR(dstSize_tooSmall);
1106 if (cSrcSize == 0) return ERROR(corruption_detected);
1108 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
1109 #if defined(HUF_FORCE_DECOMPRESS_X1)
1111 assert(algoNb == 0);
1112 return HUF_decompress4X1_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize);
1113 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1115 assert(algoNb == 1);
1116 return HUF_decompress4X2_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize);
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);
1125 size_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)
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 */
1135 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
1136 #if defined(HUF_FORCE_DECOMPRESS_X1)
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)
1143 assert(algoNb == 1);
1144 return HUF_decompress1X2_DCtx_wksp(dctx, dst, dstSize, cSrc,
1145 cSrcSize, workSpace, wkspSize);
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);
1155 size_t HUF_decompress1X_DCtx(HUF_DTable* dctx, void* dst, size_t dstSize,
1156 const void* cSrc, size_t cSrcSize)
1158 U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];
1159 return HUF_decompress1X_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize,
1160 workSpace, sizeof(workSpace));
1164 size_t HUF_decompress1X_usingDTable_bmi2(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, int bmi2)
1166 DTableDesc const dtd = HUF_getDTableDesc(DTable);
1167 #if defined(HUF_FORCE_DECOMPRESS_X1)
1169 assert(dtd.tableType == 0);
1170 return HUF_decompress1X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);
1171 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1173 assert(dtd.tableType == 1);
1174 return HUF_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);
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);
1181 #ifndef HUF_FORCE_DECOMPRESS_X2
1182 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)
1184 const BYTE* ip = (const BYTE*) cSrc;
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;
1191 return HUF_decompress1X1_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx, bmi2);
1195 size_t HUF_decompress4X_usingDTable_bmi2(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUF_DTable* DTable, int bmi2)
1197 DTableDesc const dtd = HUF_getDTableDesc(DTable);
1198 #if defined(HUF_FORCE_DECOMPRESS_X1)
1200 assert(dtd.tableType == 0);
1201 return HUF_decompress4X1_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);
1202 #elif defined(HUF_FORCE_DECOMPRESS_X2)
1204 assert(dtd.tableType == 1);
1205 return HUF_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable, bmi2);
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);
1212 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)
1214 /* validation checks */
1215 if (dstSize == 0) return ERROR(dstSize_tooSmall);
1216 if (cSrcSize == 0) return ERROR(corruption_detected);
1218 { U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
1219 #if defined(HUF_FORCE_DECOMPRESS_X1)
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)
1225 assert(algoNb == 1);
1226 return HUF_decompress4X2_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, bmi2);
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);