source: thirdparty/blosc/internal-complibs/zstd-0.7.4/decompress/huf_decompress.c @ 8ebc79b

Revision 8ebc79b, 35.1 KB checked in by Hal Finkel <hfinkel@…>, 8 years ago (diff)

Add the other internal compression libraries from blocs
  • Property mode set to 100644
Line 
1/* ******************************************************************
2   Huffman decoder, part of New Generation Entropy library
3   Copyright (C) 2013-2016, Yann Collet.
4
5   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6
7   Redistribution and use in source and binary forms, with or without
8   modification, are permitted provided that the following conditions are
9   met:
10
11       * Redistributions of source code must retain the above copyright
12   notice, this list of conditions and the following disclaimer.
13       * Redistributions in binary form must reproduce the above
14   copyright notice, this list of conditions and the following disclaimer
15   in the documentation and/or other materials provided with the
16   distribution.
17
18   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30    You can contact the author at :
31    - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
32    - Public forum : https://groups.google.com/forum/#!forum/lz4c
33****************************************************************** */
34
35/* **************************************************************
36*  Compiler specifics
37****************************************************************/
38#if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
39/* inline is defined */
40#elif defined(_MSC_VER)
41#  define inline __inline
42#else
43#  define inline /* disable inline */
44#endif
45
46
47#ifdef _MSC_VER    /* Visual Studio */
48#  define FORCE_INLINE static __forceinline
49#  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
50#else
51#  ifdef __GNUC__
52#    define FORCE_INLINE static inline __attribute__((always_inline))
53#  else
54#    define FORCE_INLINE static inline
55#  endif
56#endif
57
58
59/* **************************************************************
60*  Includes
61****************************************************************/
62#include <string.h>     /* memcpy, memset */
63#include "bitstream.h"
64#include "fse.h"        /* header compression */
65#define HUF_STATIC_LINKING_ONLY
66#include "huf.h"
67
68
69/* **************************************************************
70*  Error Management
71****************************************************************/
72#define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
73
74
75/*-***************************/
76/*  generic DTableDesc       */
77/*-***************************/
78
79typedef struct { BYTE maxTableLog; BYTE tableType; BYTE tableLog; BYTE reserved; } DTableDesc;
80
81static DTableDesc HUF_getDTableDesc(const HUF_DTable* table)
82{
83    DTableDesc dtd;
84    memcpy(&dtd, table, sizeof(dtd));
85    return dtd;
86}
87
88
89/*-***************************/
90/*  single-symbol decoding   */
91/*-***************************/
92
93typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2;   /* single-symbol decoding */
94
95size_t HUF_readDTableX2 (HUF_DTable* DTable, const void* src, size_t srcSize)
96{
97    BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1];
98    U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1];   /* large enough for values from 0 to 16 */
99    U32 tableLog = 0;
100    U32 nbSymbols = 0;
101    size_t iSize;
102    void* const dtPtr = DTable + 1;
103    HUF_DEltX2* const dt = (HUF_DEltX2*)dtPtr;
104
105    HUF_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUF_DTable));
106    //memset(huffWeight, 0, sizeof(huffWeight));   /* is not necessary, even though some analyzer complain ... */
107
108    iSize = HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
109    if (HUF_isError(iSize)) return iSize;
110
111    /* Table header */
112    {   DTableDesc dtd = HUF_getDTableDesc(DTable);
113        if (tableLog > (U32)(dtd.maxTableLog+1)) return ERROR(tableLog_tooLarge);   /* DTable too small, huffman tree cannot fit in */
114        dtd.tableType = 0;
115        dtd.tableLog = (BYTE)tableLog;
116        memcpy(DTable, &dtd, sizeof(dtd));
117    }
118
119    /* Prepare ranks */
120    {   U32 n, nextRankStart = 0;
121        for (n=1; n<tableLog+1; n++) {
122            U32 current = nextRankStart;
123            nextRankStart += (rankVal[n] << (n-1));
124            rankVal[n] = current;
125    }   }
126
127    /* fill DTable */
128    {   U32 n;
129        for (n=0; n<nbSymbols; n++) {
130            U32 const w = huffWeight[n];
131            U32 const length = (1 << w) >> 1;
132            U32 i;
133            HUF_DEltX2 D;
134            D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
135            for (i = rankVal[w]; i < rankVal[w] + length; i++)
136                dt[i] = D;
137            rankVal[w] += length;
138    }   }
139
140    return iSize;
141}
142
143
144static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
145{
146    size_t const val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
147    BYTE const c = dt[val].byte;
148    BIT_skipBits(Dstream, dt[val].nbBits);
149    return c;
150}
151
152#define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
153    *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
154
155#define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
156    if (MEM_64bits() || (HUF_TABLELOG_MAX<=12)) \
157        HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
158
159#define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
160    if (MEM_64bits()) \
161        HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
162
163static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
164{
165    BYTE* const pStart = p;
166
167    /* up to 4 symbols at a time */
168    while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4)) {
169        HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
170        HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
171        HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
172        HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
173    }
174
175    /* closer to the end */
176    while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
177        HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
178
179    /* no more data to retrieve from bitstream, hence no need to reload */
180    while (p < pEnd)
181        HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
182
183    return pEnd-pStart;
184}
185
186static size_t HUF_decompress1X2_usingDTable_internal(
187          void* dst,  size_t dstSize,
188    const void* cSrc, size_t cSrcSize,
189    const HUF_DTable* DTable)
190{
191    BYTE* op = (BYTE*)dst;
192    BYTE* const oend = op + dstSize;
193    const void* dtPtr = DTable + 1;
194    const HUF_DEltX2* const dt = (const HUF_DEltX2*)dtPtr;
195    BIT_DStream_t bitD;
196    DTableDesc const dtd = HUF_getDTableDesc(DTable);
197    U32 const dtLog = dtd.tableLog;
198
199    { size_t const errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize);
200      if (HUF_isError(errorCode)) return errorCode; }
201
202    HUF_decodeStreamX2(op, &bitD, oend, dt, dtLog);
203
204    /* check */
205    if (!BIT_endOfDStream(&bitD)) return ERROR(corruption_detected);
206
207    return dstSize;
208}
209
210size_t HUF_decompress1X2_usingDTable(
211          void* dst,  size_t dstSize,
212    const void* cSrc, size_t cSrcSize,
213    const HUF_DTable* DTable)
214{
215    DTableDesc dtd = HUF_getDTableDesc(DTable);
216    if (dtd.tableType != 0) return ERROR(GENERIC);
217    return HUF_decompress1X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
218}
219
220size_t HUF_decompress1X2_DCtx (HUF_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
221{
222    const BYTE* ip = (const BYTE*) cSrc;
223
224    size_t const hSize = HUF_readDTableX2 (DCtx, cSrc, cSrcSize);
225    if (HUF_isError(hSize)) return hSize;
226    if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
227    ip += hSize; cSrcSize -= hSize;
228
229    return HUF_decompress1X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
230}
231
232size_t HUF_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
233{
234    HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_TABLELOG_MAX);
235    return HUF_decompress1X2_DCtx (DTable, dst, dstSize, cSrc, cSrcSize);
236}
237
238
239static size_t HUF_decompress4X2_usingDTable_internal(
240          void* dst,  size_t dstSize,
241    const void* cSrc, size_t cSrcSize,
242    const HUF_DTable* DTable)
243{
244    /* Check */
245    if (cSrcSize < 10) return ERROR(corruption_detected);  /* strict minimum : jump table + 1 byte per stream */
246
247    {   const BYTE* const istart = (const BYTE*) cSrc;
248        BYTE* const ostart = (BYTE*) dst;
249        BYTE* const oend = ostart + dstSize;
250        const void* const dtPtr = DTable + 1;
251        const HUF_DEltX2* const dt = (const HUF_DEltX2*)dtPtr;
252
253        /* Init */
254        BIT_DStream_t bitD1;
255        BIT_DStream_t bitD2;
256        BIT_DStream_t bitD3;
257        BIT_DStream_t bitD4;
258        size_t const length1 = MEM_readLE16(istart);
259        size_t const length2 = MEM_readLE16(istart+2);
260        size_t const length3 = MEM_readLE16(istart+4);
261        size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
262        const BYTE* const istart1 = istart + 6;  /* jumpTable */
263        const BYTE* const istart2 = istart1 + length1;
264        const BYTE* const istart3 = istart2 + length2;
265        const BYTE* const istart4 = istart3 + length3;
266        const size_t segmentSize = (dstSize+3) / 4;
267        BYTE* const opStart2 = ostart + segmentSize;
268        BYTE* const opStart3 = opStart2 + segmentSize;
269        BYTE* const opStart4 = opStart3 + segmentSize;
270        BYTE* op1 = ostart;
271        BYTE* op2 = opStart2;
272        BYTE* op3 = opStart3;
273        BYTE* op4 = opStart4;
274        U32 endSignal;
275        DTableDesc const dtd = HUF_getDTableDesc(DTable);
276        U32 const dtLog = dtd.tableLog;
277
278        if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
279        { size_t const errorCode = BIT_initDStream(&bitD1, istart1, length1);
280          if (HUF_isError(errorCode)) return errorCode; }
281        { size_t const errorCode = BIT_initDStream(&bitD2, istart2, length2);
282          if (HUF_isError(errorCode)) return errorCode; }
283        { size_t const errorCode = BIT_initDStream(&bitD3, istart3, length3);
284          if (HUF_isError(errorCode)) return errorCode; }
285        { size_t const errorCode = BIT_initDStream(&bitD4, istart4, length4);
286          if (HUF_isError(errorCode)) return errorCode; }
287
288        /* 16-32 symbols per loop (4-8 symbols per stream) */
289        endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
290        for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; ) {
291            HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
292            HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
293            HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
294            HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
295            HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
296            HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
297            HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
298            HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
299            HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
300            HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
301            HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
302            HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
303            HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
304            HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
305            HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
306            HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
307            endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
308        }
309
310        /* check corruption */
311        if (op1 > opStart2) return ERROR(corruption_detected);
312        if (op2 > opStart3) return ERROR(corruption_detected);
313        if (op3 > opStart4) return ERROR(corruption_detected);
314        /* note : op4 supposed already verified within main loop */
315
316        /* finish bitStreams one by one */
317        HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
318        HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
319        HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
320        HUF_decodeStreamX2(op4, &bitD4, oend,     dt, dtLog);
321
322        /* check */
323        endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
324        if (!endSignal) return ERROR(corruption_detected);
325
326        /* decoded size */
327        return dstSize;
328    }
329}
330
331
332size_t HUF_decompress4X2_usingDTable(
333          void* dst,  size_t dstSize,
334    const void* cSrc, size_t cSrcSize,
335    const HUF_DTable* DTable)
336{
337    DTableDesc dtd = HUF_getDTableDesc(DTable);
338    if (dtd.tableType != 0) return ERROR(GENERIC);
339    return HUF_decompress4X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
340}
341
342
343size_t HUF_decompress4X2_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
344{
345    const BYTE* ip = (const BYTE*) cSrc;
346
347    size_t const hSize = HUF_readDTableX2 (dctx, cSrc, cSrcSize);
348    if (HUF_isError(hSize)) return hSize;
349    if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
350    ip += hSize; cSrcSize -= hSize;
351
352    return HUF_decompress4X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, dctx);
353}
354
355size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
356{
357    HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_TABLELOG_MAX);
358    return HUF_decompress4X2_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
359}
360
361
362/* *************************/
363/* double-symbols decoding */
364/* *************************/
365typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4;  /* double-symbols decoding */
366
367typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
368
369static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
370                           const U32* rankValOrigin, const int minWeight,
371                           const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
372                           U32 nbBitsBaseline, U16 baseSeq)
373{
374    HUF_DEltX4 DElt;
375    U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1];
376
377    /* get pre-calculated rankVal */
378    memcpy(rankVal, rankValOrigin, sizeof(rankVal));
379
380    /* fill skipped values */
381    if (minWeight>1) {
382        U32 i, skipSize = rankVal[minWeight];
383        MEM_writeLE16(&(DElt.sequence), baseSeq);
384        DElt.nbBits   = (BYTE)(consumed);
385        DElt.length   = 1;
386        for (i = 0; i < skipSize; i++)
387            DTable[i] = DElt;
388    }
389
390    /* fill DTable */
391    { U32 s; for (s=0; s<sortedListSize; s++) {   /* note : sortedSymbols already skipped */
392        const U32 symbol = sortedSymbols[s].symbol;
393        const U32 weight = sortedSymbols[s].weight;
394        const U32 nbBits = nbBitsBaseline - weight;
395        const U32 length = 1 << (sizeLog-nbBits);
396        const U32 start = rankVal[weight];
397        U32 i = start;
398        const U32 end = start + length;
399
400        MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
401        DElt.nbBits = (BYTE)(nbBits + consumed);
402        DElt.length = 2;
403        do { DTable[i++] = DElt; } while (i<end);   /* since length >= 1 */
404
405        rankVal[weight] += length;
406    }}
407}
408
409typedef U32 rankVal_t[HUF_TABLELOG_ABSOLUTEMAX][HUF_TABLELOG_ABSOLUTEMAX + 1];
410
411static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
412                           const sortedSymbol_t* sortedList, const U32 sortedListSize,
413                           const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
414                           const U32 nbBitsBaseline)
415{
416    U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1];
417    const int scaleLog = nbBitsBaseline - targetLog;   /* note : targetLog >= srcLog, hence scaleLog <= 1 */
418    const U32 minBits  = nbBitsBaseline - maxWeight;
419    U32 s;
420
421    memcpy(rankVal, rankValOrigin, sizeof(rankVal));
422
423    /* fill DTable */
424    for (s=0; s<sortedListSize; s++) {
425        const U16 symbol = sortedList[s].symbol;
426        const U32 weight = sortedList[s].weight;
427        const U32 nbBits = nbBitsBaseline - weight;
428        const U32 start = rankVal[weight];
429        const U32 length = 1 << (targetLog-nbBits);
430
431        if (targetLog-nbBits >= minBits) {   /* enough room for a second symbol */
432            U32 sortedRank;
433            int minWeight = nbBits + scaleLog;
434            if (minWeight < 1) minWeight = 1;
435            sortedRank = rankStart[minWeight];
436            HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
437                           rankValOrigin[nbBits], minWeight,
438                           sortedList+sortedRank, sortedListSize-sortedRank,
439                           nbBitsBaseline, symbol);
440        } else {
441            HUF_DEltX4 DElt;
442            MEM_writeLE16(&(DElt.sequence), symbol);
443            DElt.nbBits = (BYTE)(nbBits);
444            DElt.length = 1;
445            {   U32 u;
446                const U32 end = start + length;
447                for (u = start; u < end; u++) DTable[u] = DElt;
448        }   }
449        rankVal[weight] += length;
450    }
451}
452
453size_t HUF_readDTableX4 (HUF_DTable* DTable, const void* src, size_t srcSize)
454{
455    BYTE weightList[HUF_SYMBOLVALUE_MAX + 1];
456    sortedSymbol_t sortedSymbol[HUF_SYMBOLVALUE_MAX + 1];
457    U32 rankStats[HUF_TABLELOG_ABSOLUTEMAX + 1] = { 0 };
458    U32 rankStart0[HUF_TABLELOG_ABSOLUTEMAX + 2] = { 0 };
459    U32* const rankStart = rankStart0+1;
460    rankVal_t rankVal;
461    U32 tableLog, maxW, sizeOfSort, nbSymbols;
462    DTableDesc dtd = HUF_getDTableDesc(DTable);
463    U32 const maxTableLog = dtd.maxTableLog;
464    size_t iSize;
465    void* dtPtr = DTable+1;   /* force compiler to avoid strict-aliasing */
466    HUF_DEltX4* const dt = (HUF_DEltX4*)dtPtr;
467
468    HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(HUF_DTable));   /* if compilation fails here, assertion is false */
469    if (maxTableLog > HUF_TABLELOG_ABSOLUTEMAX) return ERROR(tableLog_tooLarge);
470    //memset(weightList, 0, sizeof(weightList));   /* is not necessary, even though some analyzer complain ... */
471
472    iSize = HUF_readStats(weightList, HUF_SYMBOLVALUE_MAX + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
473    if (HUF_isError(iSize)) return iSize;
474
475    /* check result */
476    if (tableLog > maxTableLog) return ERROR(tableLog_tooLarge);   /* DTable can't fit code depth */
477
478    /* find maxWeight */
479    for (maxW = tableLog; rankStats[maxW]==0; maxW--) {}  /* necessarily finds a solution before 0 */
480
481    /* Get start index of each weight */
482    {   U32 w, nextRankStart = 0;
483        for (w=1; w<maxW+1; w++) {
484            U32 current = nextRankStart;
485            nextRankStart += rankStats[w];
486            rankStart[w] = current;
487        }
488        rankStart[0] = nextRankStart;   /* put all 0w symbols at the end of sorted list*/
489        sizeOfSort = nextRankStart;
490    }
491
492    /* sort symbols by weight */
493    {   U32 s;
494        for (s=0; s<nbSymbols; s++) {
495            U32 const w = weightList[s];
496            U32 const r = rankStart[w]++;
497            sortedSymbol[r].symbol = (BYTE)s;
498            sortedSymbol[r].weight = (BYTE)w;
499        }
500        rankStart[0] = 0;   /* forget 0w symbols; this is beginning of weight(1) */
501    }
502
503    /* Build rankVal */
504    {   U32* const rankVal0 = rankVal[0];
505        {   int const rescale = (maxTableLog-tableLog) - 1;   /* tableLog <= maxTableLog */
506            U32 nextRankVal = 0;
507            U32 w;
508            for (w=1; w<maxW+1; w++) {
509                U32 current = nextRankVal;
510                nextRankVal += rankStats[w] << (w+rescale);
511                rankVal0[w] = current;
512        }   }
513        {   U32 const minBits = tableLog+1 - maxW;
514            U32 consumed;
515            for (consumed = minBits; consumed < maxTableLog - minBits + 1; consumed++) {
516                U32* const rankValPtr = rankVal[consumed];
517                U32 w;
518                for (w = 1; w < maxW+1; w++) {
519                    rankValPtr[w] = rankVal0[w] >> consumed;
520    }   }   }   }
521
522    HUF_fillDTableX4(dt, maxTableLog,
523                   sortedSymbol, sizeOfSort,
524                   rankStart0, rankVal, maxW,
525                   tableLog+1);
526
527    dtd.tableLog = (BYTE)maxTableLog;
528    dtd.tableType = 1;
529    memcpy(DTable, &dtd, sizeof(dtd));
530    return iSize;
531}
532
533
534static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
535{
536    const size_t val = BIT_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
537    memcpy(op, dt+val, 2);
538    BIT_skipBits(DStream, dt[val].nbBits);
539    return dt[val].length;
540}
541
542static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
543{
544    const size_t val = BIT_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
545    memcpy(op, dt+val, 1);
546    if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
547    else {
548        if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
549            BIT_skipBits(DStream, dt[val].nbBits);
550            if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
551                DStream->bitsConsumed = (sizeof(DStream->bitContainer)*8);   /* ugly hack; works only because it's the last symbol. Note : can't easily extract nbBits from just this symbol */
552    }   }
553    return 1;
554}
555
556
557#define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
558    ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
559
560#define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
561    if (MEM_64bits() || (HUF_TABLELOG_MAX<=12)) \
562        ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
563
564#define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
565    if (MEM_64bits()) \
566        ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
567
568static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
569{
570    BYTE* const pStart = p;
571
572    /* up to 8 symbols at a time */
573    while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7)) {
574        HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
575        HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
576        HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
577        HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
578    }
579
580    /* closer to end : up to 2 symbols at a time */
581    while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
582        HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
583
584    while (p <= pEnd-2)
585        HUF_DECODE_SYMBOLX4_0(p, bitDPtr);   /* no need to reload : reached the end of DStream */
586
587    if (p < pEnd)
588        p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
589
590    return p-pStart;
591}
592
593
594static size_t HUF_decompress1X4_usingDTable_internal(
595          void* dst,  size_t dstSize,
596    const void* cSrc, size_t cSrcSize,
597    const HUF_DTable* DTable)
598{
599    BIT_DStream_t bitD;
600
601    /* Init */
602    {   size_t const errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize);
603        if (HUF_isError(errorCode)) return errorCode;
604    }
605
606    /* decode */
607    {   BYTE* const ostart = (BYTE*) dst;
608        BYTE* const oend = ostart + dstSize;
609        const void* const dtPtr = DTable+1;   /* force compiler to not use strict-aliasing */
610        const HUF_DEltX4* const dt = (const HUF_DEltX4*)dtPtr;
611        DTableDesc const dtd = HUF_getDTableDesc(DTable);
612        HUF_decodeStreamX4(ostart, &bitD, oend, dt, dtd.tableLog);
613    }
614
615    /* check */
616    if (!BIT_endOfDStream(&bitD)) return ERROR(corruption_detected);
617
618    /* decoded size */
619    return dstSize;
620}
621
622size_t HUF_decompress1X4_usingDTable(
623          void* dst,  size_t dstSize,
624    const void* cSrc, size_t cSrcSize,
625    const HUF_DTable* DTable)
626{
627    DTableDesc dtd = HUF_getDTableDesc(DTable);
628    if (dtd.tableType != 1) return ERROR(GENERIC);
629    return HUF_decompress1X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
630}
631
632size_t HUF_decompress1X4_DCtx (HUF_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
633{
634    const BYTE* ip = (const BYTE*) cSrc;
635
636    size_t const hSize = HUF_readDTableX4 (DCtx, cSrc, cSrcSize);
637    if (HUF_isError(hSize)) return hSize;
638    if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
639    ip += hSize; cSrcSize -= hSize;
640
641    return HUF_decompress1X4_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
642}
643
644size_t HUF_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
645{
646    HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_TABLELOG_MAX);
647    return HUF_decompress1X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
648}
649
650static size_t HUF_decompress4X4_usingDTable_internal(
651          void* dst,  size_t dstSize,
652    const void* cSrc, size_t cSrcSize,
653    const HUF_DTable* DTable)
654{
655    if (cSrcSize < 10) return ERROR(corruption_detected);   /* strict minimum : jump table + 1 byte per stream */
656
657    {   const BYTE* const istart = (const BYTE*) cSrc;
658        BYTE* const ostart = (BYTE*) dst;
659        BYTE* const oend = ostart + dstSize;
660        const void* const dtPtr = DTable+1;
661        const HUF_DEltX4* const dt = (const HUF_DEltX4*)dtPtr;
662
663        /* Init */
664        BIT_DStream_t bitD1;
665        BIT_DStream_t bitD2;
666        BIT_DStream_t bitD3;
667        BIT_DStream_t bitD4;
668        size_t const length1 = MEM_readLE16(istart);
669        size_t const length2 = MEM_readLE16(istart+2);
670        size_t const length3 = MEM_readLE16(istart+4);
671        size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
672        const BYTE* const istart1 = istart + 6;  /* jumpTable */
673        const BYTE* const istart2 = istart1 + length1;
674        const BYTE* const istart3 = istart2 + length2;
675        const BYTE* const istart4 = istart3 + length3;
676        size_t const segmentSize = (dstSize+3) / 4;
677        BYTE* const opStart2 = ostart + segmentSize;
678        BYTE* const opStart3 = opStart2 + segmentSize;
679        BYTE* const opStart4 = opStart3 + segmentSize;
680        BYTE* op1 = ostart;
681        BYTE* op2 = opStart2;
682        BYTE* op3 = opStart3;
683        BYTE* op4 = opStart4;
684        U32 endSignal;
685        DTableDesc const dtd = HUF_getDTableDesc(DTable);
686        U32 const dtLog = dtd.tableLog;
687
688        if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
689        { size_t const errorCode = BIT_initDStream(&bitD1, istart1, length1);
690          if (HUF_isError(errorCode)) return errorCode; }
691        { size_t const errorCode = BIT_initDStream(&bitD2, istart2, length2);
692          if (HUF_isError(errorCode)) return errorCode; }
693        { size_t const errorCode = BIT_initDStream(&bitD3, istart3, length3);
694          if (HUF_isError(errorCode)) return errorCode; }
695        { size_t const errorCode = BIT_initDStream(&bitD4, istart4, length4);
696          if (HUF_isError(errorCode)) return errorCode; }
697
698        /* 16-32 symbols per loop (4-8 symbols per stream) */
699        endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
700        for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; ) {
701            HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
702            HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
703            HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
704            HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
705            HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
706            HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
707            HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
708            HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
709            HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
710            HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
711            HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
712            HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
713            HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
714            HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
715            HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
716            HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
717
718            endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
719        }
720
721        /* check corruption */
722        if (op1 > opStart2) return ERROR(corruption_detected);
723        if (op2 > opStart3) return ERROR(corruption_detected);
724        if (op3 > opStart4) return ERROR(corruption_detected);
725        /* note : op4 supposed already verified within main loop */
726
727        /* finish bitStreams one by one */
728        HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
729        HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
730        HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
731        HUF_decodeStreamX4(op4, &bitD4, oend,     dt, dtLog);
732
733        /* check */
734        { U32 const endCheck = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
735          if (!endCheck) return ERROR(corruption_detected); }
736
737        /* decoded size */
738        return dstSize;
739    }
740}
741
742
743size_t HUF_decompress4X4_usingDTable(
744          void* dst,  size_t dstSize,
745    const void* cSrc, size_t cSrcSize,
746    const HUF_DTable* DTable)
747{
748    DTableDesc dtd = HUF_getDTableDesc(DTable);
749    if (dtd.tableType != 1) return ERROR(GENERIC);
750    return HUF_decompress4X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
751}
752
753
754size_t HUF_decompress4X4_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
755{
756    const BYTE* ip = (const BYTE*) cSrc;
757
758    size_t hSize = HUF_readDTableX4 (dctx, cSrc, cSrcSize);
759    if (HUF_isError(hSize)) return hSize;
760    if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
761    ip += hSize; cSrcSize -= hSize;
762
763    return HUF_decompress4X4_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx);
764}
765
766size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
767{
768    HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_TABLELOG_MAX);
769    return HUF_decompress4X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
770}
771
772
773/* ********************************/
774/* Generic decompression selector */
775/* ********************************/
776
777size_t HUF_decompress1X_usingDTable(void* dst, size_t maxDstSize,
778                                    const void* cSrc, size_t cSrcSize,
779                                    const HUF_DTable* DTable)
780{
781    DTableDesc const dtd = HUF_getDTableDesc(DTable);
782    return dtd.tableType ? HUF_decompress1X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) :
783                           HUF_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
784}
785
786size_t HUF_decompress4X_usingDTable(void* dst, size_t maxDstSize,
787                                    const void* cSrc, size_t cSrcSize,
788                                    const HUF_DTable* DTable)
789{
790    DTableDesc const dtd = HUF_getDTableDesc(DTable);
791    return dtd.tableType ? HUF_decompress4X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) :
792                           HUF_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
793}
794
795
796typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
797static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
798{
799    /* single, double, quad */
800    {{0,0}, {1,1}, {2,2}},  /* Q==0 : impossible */
801    {{0,0}, {1,1}, {2,2}},  /* Q==1 : impossible */
802    {{  38,130}, {1313, 74}, {2151, 38}},   /* Q == 2 : 12-18% */
803    {{ 448,128}, {1353, 74}, {2238, 41}},   /* Q == 3 : 18-25% */
804    {{ 556,128}, {1353, 74}, {2238, 47}},   /* Q == 4 : 25-32% */
805    {{ 714,128}, {1418, 74}, {2436, 53}},   /* Q == 5 : 32-38% */
806    {{ 883,128}, {1437, 74}, {2464, 61}},   /* Q == 6 : 38-44% */
807    {{ 897,128}, {1515, 75}, {2622, 68}},   /* Q == 7 : 44-50% */
808    {{ 926,128}, {1613, 75}, {2730, 75}},   /* Q == 8 : 50-56% */
809    {{ 947,128}, {1729, 77}, {3359, 77}},   /* Q == 9 : 56-62% */
810    {{1107,128}, {2083, 81}, {4006, 84}},   /* Q ==10 : 62-69% */
811    {{1177,128}, {2379, 87}, {4785, 88}},   /* Q ==11 : 69-75% */
812    {{1242,128}, {2415, 93}, {5155, 84}},   /* Q ==12 : 75-81% */
813    {{1349,128}, {2644,106}, {5260,106}},   /* Q ==13 : 81-87% */
814    {{1455,128}, {2422,124}, {4174,124}},   /* Q ==14 : 87-93% */
815    {{ 722,128}, {1891,145}, {1936,146}},   /* Q ==15 : 93-99% */
816};
817
818/** HUF_selectDecoder() :
819*   Tells which decoder is likely to decode faster,
820*   based on a set of pre-determined metrics.
821*   @return : 0==HUF_decompress4X2, 1==HUF_decompress4X4 .
822*   Assumption : 0 < cSrcSize < dstSize <= 128 KB */
823U32 HUF_selectDecoder (size_t dstSize, size_t cSrcSize)
824{
825    /* decoder timing evaluation */
826    U32 const Q = (U32)(cSrcSize * 16 / dstSize);   /* Q < 16 since dstSize > cSrcSize */
827    U32 const D256 = (U32)(dstSize >> 8);
828    U32 const DTime0 = algoTime[Q][0].tableTime + (algoTime[Q][0].decode256Time * D256);
829    U32 DTime1 = algoTime[Q][1].tableTime + (algoTime[Q][1].decode256Time * D256);
830    DTime1 += DTime1 >> 3;  /* advantage to algorithm using less memory, for cache eviction */
831
832    return DTime1 < DTime0;
833}
834
835
836typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
837
838size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
839{
840    static const decompressionAlgo decompress[2] = { HUF_decompress4X2, HUF_decompress4X4 };
841
842    /* validation checks */
843    if (dstSize == 0) return ERROR(dstSize_tooSmall);
844    if (cSrcSize > dstSize) return ERROR(corruption_detected);   /* invalid */
845    if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; }   /* not compressed */
846    if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; }   /* RLE */
847
848    {   U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
849        return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
850    }
851
852    //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize);   /* multi-streams single-symbol decoding */
853    //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize);   /* multi-streams double-symbols decoding */
854}
855
856size_t HUF_decompress4X_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
857{
858    /* validation checks */
859    if (dstSize == 0) return ERROR(dstSize_tooSmall);
860    if (cSrcSize > dstSize) return ERROR(corruption_detected);   /* invalid */
861    if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; }   /* not compressed */
862    if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; }   /* RLE */
863
864    {   U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
865        return algoNb ? HUF_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
866                        HUF_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
867    }
868}
869
870size_t HUF_decompress4X_hufOnly (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
871{
872    /* validation checks */
873    if (dstSize == 0) return ERROR(dstSize_tooSmall);
874    if ((cSrcSize >= dstSize) || (cSrcSize <= 1)) return ERROR(corruption_detected);   /* invalid */
875
876    {   U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
877        return algoNb ? HUF_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
878                        HUF_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
879    }
880}
881
882size_t HUF_decompress1X_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
883{
884    /* validation checks */
885    if (dstSize == 0) return ERROR(dstSize_tooSmall);
886    if (cSrcSize > dstSize) return ERROR(corruption_detected);   /* invalid */
887    if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; }   /* not compressed */
888    if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; }   /* RLE */
889
890    {   U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
891        return algoNb ? HUF_decompress1X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
892                        HUF_decompress1X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
893    }
894}
Note: See TracBrowser for help on using the repository browser.