source: thirdparty/blosc/internal-complibs/zstd-0.7.4/compress/huf_compress.c @ 8ebc79b

Revision 8ebc79b, 22.3 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 encoder, 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 <stdio.h>      /* printf (debug) */
64#include "bitstream.h"
65#define FSE_STATIC_LINKING_ONLY   /* FSE_optimalTableLog_internal */
66#include "fse.h"        /* header compression */
67#define HUF_STATIC_LINKING_ONLY
68#include "huf.h"
69
70
71/* **************************************************************
72*  Error Management
73****************************************************************/
74#define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
75
76
77/* **************************************************************
78*  Utils
79****************************************************************/
80unsigned HUF_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
81{
82    return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 1);
83}
84
85
86/* *******************************************************
87*  HUF : Huffman block compression
88*********************************************************/
89struct HUF_CElt_s {
90  U16  val;
91  BYTE nbBits;
92};   /* typedef'd to HUF_CElt within huf_static.h */
93
94typedef struct nodeElt_s {
95    U32 count;
96    U16 parent;
97    BYTE byte;
98    BYTE nbBits;
99} nodeElt;
100
101/*! HUF_writeCTable() :
102    `CTable` : huffman tree to save, using huf representation.
103    @return : size of saved CTable */
104size_t HUF_writeCTable (void* dst, size_t maxDstSize,
105                        const HUF_CElt* CTable, U32 maxSymbolValue, U32 huffLog)
106{
107    BYTE bitsToWeight[HUF_TABLELOG_MAX + 1];
108    BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1];
109    U32 n;
110    BYTE* op = (BYTE*)dst;
111    size_t size;
112
113     /* check conditions */
114    if (maxSymbolValue > HUF_SYMBOLVALUE_MAX + 1)
115        return ERROR(GENERIC);
116
117    /* convert to weight */
118    bitsToWeight[0] = 0;
119    for (n=1; n<=huffLog; n++)
120        bitsToWeight[n] = (BYTE)(huffLog + 1 - n);
121    for (n=0; n<maxSymbolValue; n++)
122        huffWeight[n] = bitsToWeight[CTable[n].nbBits];
123
124    size = FSE_compress(op+1, maxDstSize-1, huffWeight, maxSymbolValue);   /* don't need last symbol stat : implied */
125    if (HUF_isError(size)) return size;
126    if (size >= 128) return ERROR(GENERIC);   /* should never happen, since maxSymbolValue <= 255 */
127    if ((size <= 1) || (size >= maxSymbolValue/2)) {
128        if (size==1) {  /* RLE */
129            /* only possible case : series of 1 (because there are at least 2) */
130            /* can only be 2^n or (2^n-1), otherwise not an huffman tree */
131            BYTE code;
132            switch(maxSymbolValue)
133            {
134            case 1: code = 0; break;
135            case 2: code = 1; break;
136            case 3: code = 2; break;
137            case 4: code = 3; break;
138            case 7: code = 4; break;
139            case 8: code = 5; break;
140            case 15: code = 6; break;
141            case 16: code = 7; break;
142            case 31: code = 8; break;
143            case 32: code = 9; break;
144            case 63: code = 10; break;
145            case 64: code = 11; break;
146            case 127: code = 12; break;
147            case 128: code = 13; break;
148            default : return ERROR(corruption_detected);
149            }
150            op[0] = (BYTE)(255-13 + code);
151            return 1;
152        }
153         /* Not compressible */
154        if (maxSymbolValue > (241-128)) return ERROR(GENERIC);   /* not implemented (not possible with current format) */
155        if (((maxSymbolValue+1)/2) + 1 > maxDstSize) return ERROR(dstSize_tooSmall);   /* not enough space within dst buffer */
156        op[0] = (BYTE)(128 /*special case*/ + 0 /* Not Compressible */ + (maxSymbolValue-1));
157        huffWeight[maxSymbolValue] = 0;   /* to be sure it doesn't cause issue in final combination */
158        for (n=0; n<maxSymbolValue; n+=2)
159            op[(n/2)+1] = (BYTE)((huffWeight[n] << 4) + huffWeight[n+1]);
160        return ((maxSymbolValue+1)/2) + 1;
161    }
162
163    /* normal header case */
164    op[0] = (BYTE)size;
165    return size+1;
166}
167
168
169
170size_t HUF_readCTable (HUF_CElt* CTable, U32 maxSymbolValue, const void* src, size_t srcSize)
171{
172    BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1];
173    U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1];   /* large enough for values from 0 to 16 */
174    U32 tableLog = 0;
175    size_t readSize;
176    U32 nbSymbols = 0;
177    //memset(huffWeight, 0, sizeof(huffWeight));   /* is not necessary, even though some analyzer complain ... */
178
179    /* get symbol weights */
180    readSize = HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX+1, rankVal, &nbSymbols, &tableLog, src, srcSize);
181    if (HUF_isError(readSize)) return readSize;
182
183    /* check result */
184    if (tableLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
185    if (nbSymbols > maxSymbolValue+1) return ERROR(maxSymbolValue_tooSmall);
186
187    /* Prepare base value per rank */
188    {   U32 n, nextRankStart = 0;
189        for (n=1; n<=tableLog; n++) {
190            U32 current = nextRankStart;
191            nextRankStart += (rankVal[n] << (n-1));
192            rankVal[n] = current;
193    }   }
194
195    /* fill nbBits */
196    { U32 n; for (n=0; n<nbSymbols; n++) {
197        const U32 w = huffWeight[n];
198        CTable[n].nbBits = (BYTE)(tableLog + 1 - w);
199    }}
200
201    /* fill val */
202    {   U16 nbPerRank[HUF_TABLELOG_MAX+1] = {0};
203        U16 valPerRank[HUF_TABLELOG_MAX+1] = {0};
204        { U32 n; for (n=0; n<nbSymbols; n++) nbPerRank[CTable[n].nbBits]++; }
205        /* determine stating value per rank */
206        {   U16 min = 0;
207            U32 n; for (n=HUF_TABLELOG_MAX; n>0; n--) {
208                valPerRank[n] = min;      /* get starting value within each rank */
209                min += nbPerRank[n];
210                min >>= 1;
211        }   }
212        /* assign value within rank, symbol order */
213        { U32 n; for (n=0; n<=maxSymbolValue; n++) CTable[n].val = valPerRank[CTable[n].nbBits]++; }
214    }
215
216    return readSize;
217}
218
219
220static U32 HUF_setMaxHeight(nodeElt* huffNode, U32 lastNonNull, U32 maxNbBits)
221{
222    const U32 largestBits = huffNode[lastNonNull].nbBits;
223    if (largestBits <= maxNbBits) return largestBits;   /* early exit : no elt > maxNbBits */
224
225    /* there are several too large elements (at least >= 2) */
226    {   int totalCost = 0;
227        const U32 baseCost = 1 << (largestBits - maxNbBits);
228        U32 n = lastNonNull;
229
230        while (huffNode[n].nbBits > maxNbBits) {
231            totalCost += baseCost - (1 << (largestBits - huffNode[n].nbBits));
232            huffNode[n].nbBits = (BYTE)maxNbBits;
233            n --;
234        }  /* n stops at huffNode[n].nbBits <= maxNbBits */
235        while (huffNode[n].nbBits == maxNbBits) n--;   /* n end at index of smallest symbol using < maxNbBits */
236
237        /* renorm totalCost */
238        totalCost >>= (largestBits - maxNbBits);  /* note : totalCost is necessarily a multiple of baseCost */
239
240        /* repay normalized cost */
241        {   U32 const noSymbol = 0xF0F0F0F0;
242            U32 rankLast[HUF_TABLELOG_MAX+2];
243            int pos;
244
245            /* Get pos of last (smallest) symbol per rank */
246            memset(rankLast, 0xF0, sizeof(rankLast));
247            {   U32 currentNbBits = maxNbBits;
248                for (pos=n ; pos >= 0; pos--) {
249                    if (huffNode[pos].nbBits >= currentNbBits) continue;
250                    currentNbBits = huffNode[pos].nbBits;   /* < maxNbBits */
251                    rankLast[maxNbBits-currentNbBits] = pos;
252            }   }
253
254            while (totalCost > 0) {
255                U32 nBitsToDecrease = BIT_highbit32(totalCost) + 1;
256                for ( ; nBitsToDecrease > 1; nBitsToDecrease--) {
257                    U32 highPos = rankLast[nBitsToDecrease];
258                    U32 lowPos = rankLast[nBitsToDecrease-1];
259                    if (highPos == noSymbol) continue;
260                    if (lowPos == noSymbol) break;
261                    {   U32 const highTotal = huffNode[highPos].count;
262                        U32 const lowTotal = 2 * huffNode[lowPos].count;
263                        if (highTotal <= lowTotal) break;
264                }   }
265                /* only triggered when no more rank 1 symbol left => find closest one (note : there is necessarily at least one !) */
266                while ((nBitsToDecrease<=HUF_TABLELOG_MAX) && (rankLast[nBitsToDecrease] == noSymbol))  /* HUF_MAX_TABLELOG test just to please gcc 5+; but it should not be necessary */
267                    nBitsToDecrease ++;
268                totalCost -= 1 << (nBitsToDecrease-1);
269                if (rankLast[nBitsToDecrease-1] == noSymbol)
270                    rankLast[nBitsToDecrease-1] = rankLast[nBitsToDecrease];   /* this rank is no longer empty */
271                huffNode[rankLast[nBitsToDecrease]].nbBits ++;
272                if (rankLast[nBitsToDecrease] == 0)    /* special case, reached largest symbol */
273                    rankLast[nBitsToDecrease] = noSymbol;
274                else {
275                    rankLast[nBitsToDecrease]--;
276                    if (huffNode[rankLast[nBitsToDecrease]].nbBits != maxNbBits-nBitsToDecrease)
277                        rankLast[nBitsToDecrease] = noSymbol;   /* this rank is now empty */
278            }   }   /* while (totalCost > 0) */
279
280            while (totalCost < 0) {  /* Sometimes, cost correction overshoot */
281                if (rankLast[1] == noSymbol) {  /* special case : no rank 1 symbol (using maxNbBits-1); let's create one from largest rank 0 (using maxNbBits) */
282                    while (huffNode[n].nbBits == maxNbBits) n--;
283                    huffNode[n+1].nbBits--;
284                    rankLast[1] = n+1;
285                    totalCost++;
286                    continue;
287                }
288                huffNode[ rankLast[1] + 1 ].nbBits--;
289                rankLast[1]++;
290                totalCost ++;
291    }   }   }   /* there are several too large elements (at least >= 2) */
292
293    return maxNbBits;
294}
295
296
297typedef struct {
298    U32 base;
299    U32 current;
300} rankPos;
301
302static void HUF_sort(nodeElt* huffNode, const U32* count, U32 maxSymbolValue)
303{
304    rankPos rank[32];
305    U32 n;
306
307    memset(rank, 0, sizeof(rank));
308    for (n=0; n<=maxSymbolValue; n++) {
309        U32 r = BIT_highbit32(count[n] + 1);
310        rank[r].base ++;
311    }
312    for (n=30; n>0; n--) rank[n-1].base += rank[n].base;
313    for (n=0; n<32; n++) rank[n].current = rank[n].base;
314    for (n=0; n<=maxSymbolValue; n++) {
315        U32 const c = count[n];
316        U32 const r = BIT_highbit32(c+1) + 1;
317        U32 pos = rank[r].current++;
318        while ((pos > rank[r].base) && (c > huffNode[pos-1].count)) huffNode[pos]=huffNode[pos-1], pos--;
319        huffNode[pos].count = c;
320        huffNode[pos].byte  = (BYTE)n;
321    }
322}
323
324
325#define STARTNODE (HUF_SYMBOLVALUE_MAX+1)
326size_t HUF_buildCTable (HUF_CElt* tree, const U32* count, U32 maxSymbolValue, U32 maxNbBits)
327{
328    nodeElt huffNode0[2*HUF_SYMBOLVALUE_MAX+1 +1];
329    nodeElt* huffNode = huffNode0 + 1;
330    U32 n, nonNullRank;
331    int lowS, lowN;
332    U16 nodeNb = STARTNODE;
333    U32 nodeRoot;
334
335    /* safety checks */
336    if (maxNbBits == 0) maxNbBits = HUF_TABLELOG_DEFAULT;
337    if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(GENERIC);
338    memset(huffNode0, 0, sizeof(huffNode0));
339
340    /* sort, decreasing order */
341    HUF_sort(huffNode, count, maxSymbolValue);
342
343    /* init for parents */
344    nonNullRank = maxSymbolValue;
345    while(huffNode[nonNullRank].count == 0) nonNullRank--;
346    lowS = nonNullRank; nodeRoot = nodeNb + lowS - 1; lowN = nodeNb;
347    huffNode[nodeNb].count = huffNode[lowS].count + huffNode[lowS-1].count;
348    huffNode[lowS].parent = huffNode[lowS-1].parent = nodeNb;
349    nodeNb++; lowS-=2;
350    for (n=nodeNb; n<=nodeRoot; n++) huffNode[n].count = (U32)(1U<<30);
351    huffNode0[0].count = (U32)(1U<<31);
352
353    /* create parents */
354    while (nodeNb <= nodeRoot) {
355        U32 n1 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++;
356        U32 n2 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++;
357        huffNode[nodeNb].count = huffNode[n1].count + huffNode[n2].count;
358        huffNode[n1].parent = huffNode[n2].parent = nodeNb;
359        nodeNb++;
360    }
361
362    /* distribute weights (unlimited tree height) */
363    huffNode[nodeRoot].nbBits = 0;
364    for (n=nodeRoot-1; n>=STARTNODE; n--)
365        huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1;
366    for (n=0; n<=nonNullRank; n++)
367        huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1;
368
369    /* enforce maxTableLog */
370    maxNbBits = HUF_setMaxHeight(huffNode, nonNullRank, maxNbBits);
371
372    /* fill result into tree (val, nbBits) */
373    {   U16 nbPerRank[HUF_TABLELOG_MAX+1] = {0};
374        U16 valPerRank[HUF_TABLELOG_MAX+1] = {0};
375        if (maxNbBits > HUF_TABLELOG_MAX) return ERROR(GENERIC);   /* check fit into table */
376        for (n=0; n<=nonNullRank; n++)
377            nbPerRank[huffNode[n].nbBits]++;
378        /* determine stating value per rank */
379        {   U16 min = 0;
380            for (n=maxNbBits; n>0; n--) {
381                valPerRank[n] = min;      /* get starting value within each rank */
382                min += nbPerRank[n];
383                min >>= 1;
384        }   }
385        for (n=0; n<=maxSymbolValue; n++)
386            tree[huffNode[n].byte].nbBits = huffNode[n].nbBits;   /* push nbBits per symbol, symbol order */
387        for (n=0; n<=maxSymbolValue; n++)
388            tree[n].val = valPerRank[tree[n].nbBits]++;   /* assign value within rank, symbol order */
389    }
390
391    return maxNbBits;
392}
393
394static void HUF_encodeSymbol(BIT_CStream_t* bitCPtr, U32 symbol, const HUF_CElt* CTable)
395{
396    BIT_addBitsFast(bitCPtr, CTable[symbol].val, CTable[symbol].nbBits);
397}
398
399size_t HUF_compressBound(size_t size) { return HUF_COMPRESSBOUND(size); }
400
401#define HUF_FLUSHBITS(s)  (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
402
403#define HUF_FLUSHBITS_1(stream) \
404    if (sizeof((stream)->bitContainer)*8 < HUF_TABLELOG_MAX*2+7) HUF_FLUSHBITS(stream)
405
406#define HUF_FLUSHBITS_2(stream) \
407    if (sizeof((stream)->bitContainer)*8 < HUF_TABLELOG_MAX*4+7) HUF_FLUSHBITS(stream)
408
409size_t HUF_compress1X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable)
410{
411    const BYTE* ip = (const BYTE*) src;
412    BYTE* const ostart = (BYTE*)dst;
413    BYTE* const oend = ostart + dstSize;
414    BYTE* op = ostart;
415    size_t n;
416    const unsigned fast = (dstSize >= HUF_BLOCKBOUND(srcSize));
417    BIT_CStream_t bitC;
418
419    /* init */
420    if (dstSize < 8) return 0;   /* not enough space to compress */
421    { size_t const errorCode = BIT_initCStream(&bitC, op, oend-op);
422      if (HUF_isError(errorCode)) return 0; }
423
424    n = srcSize & ~3;  /* join to mod 4 */
425    switch (srcSize & 3)
426    {
427        case 3 : HUF_encodeSymbol(&bitC, ip[n+ 2], CTable);
428                 HUF_FLUSHBITS_2(&bitC);
429        case 2 : HUF_encodeSymbol(&bitC, ip[n+ 1], CTable);
430                 HUF_FLUSHBITS_1(&bitC);
431        case 1 : HUF_encodeSymbol(&bitC, ip[n+ 0], CTable);
432                 HUF_FLUSHBITS(&bitC);
433        case 0 :
434        default: ;
435    }
436
437    for (; n>0; n-=4) {  /* note : n&3==0 at this stage */
438        HUF_encodeSymbol(&bitC, ip[n- 1], CTable);
439        HUF_FLUSHBITS_1(&bitC);
440        HUF_encodeSymbol(&bitC, ip[n- 2], CTable);
441        HUF_FLUSHBITS_2(&bitC);
442        HUF_encodeSymbol(&bitC, ip[n- 3], CTable);
443        HUF_FLUSHBITS_1(&bitC);
444        HUF_encodeSymbol(&bitC, ip[n- 4], CTable);
445        HUF_FLUSHBITS(&bitC);
446    }
447
448    return BIT_closeCStream(&bitC);
449}
450
451
452size_t HUF_compress4X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable)
453{
454    size_t const segmentSize = (srcSize+3)/4;   /* first 3 segments */
455    const BYTE* ip = (const BYTE*) src;
456    const BYTE* const iend = ip + srcSize;
457    BYTE* const ostart = (BYTE*) dst;
458    BYTE* const oend = ostart + dstSize;
459    BYTE* op = ostart;
460
461    if (dstSize < 6 + 1 + 1 + 1 + 8) return 0;   /* minimum space to compress successfully */
462    if (srcSize < 12) return 0;   /* no saving possible : too small input */
463    op += 6;   /* jumpTable */
464
465    {   size_t const cSize = HUF_compress1X_usingCTable(op, oend-op, ip, segmentSize, CTable);
466        if (HUF_isError(cSize)) return cSize;
467        if (cSize==0) return 0;
468        MEM_writeLE16(ostart, (U16)cSize);
469        op += cSize;
470    }
471
472    ip += segmentSize;
473    {   size_t const cSize = HUF_compress1X_usingCTable(op, oend-op, ip, segmentSize, CTable);
474        if (HUF_isError(cSize)) return cSize;
475        if (cSize==0) return 0;
476        MEM_writeLE16(ostart+2, (U16)cSize);
477        op += cSize;
478    }
479
480    ip += segmentSize;
481    {   size_t const cSize = HUF_compress1X_usingCTable(op, oend-op, ip, segmentSize, CTable);
482        if (HUF_isError(cSize)) return cSize;
483        if (cSize==0) return 0;
484        MEM_writeLE16(ostart+4, (U16)cSize);
485        op += cSize;
486    }
487
488    ip += segmentSize;
489    {   size_t const cSize = HUF_compress1X_usingCTable(op, oend-op, ip, iend-ip, CTable);
490        if (HUF_isError(cSize)) return cSize;
491        if (cSize==0) return 0;
492        op += cSize;
493    }
494
495    return op-ostart;
496}
497
498
499static size_t HUF_compress_internal (
500                void* dst, size_t dstSize,
501                const void* src, size_t srcSize,
502                unsigned maxSymbolValue, unsigned huffLog,
503                unsigned singleStream)
504{
505    BYTE* const ostart = (BYTE*)dst;
506    BYTE* const oend = ostart + dstSize;
507    BYTE* op = ostart;
508
509    U32 count[HUF_SYMBOLVALUE_MAX+1];
510    HUF_CElt CTable[HUF_SYMBOLVALUE_MAX+1];
511
512    /* checks & inits */
513    if (!srcSize) return 0;  /* Uncompressed (note : 1 means rle, so first byte must be correct) */
514    if (!dstSize) return 0;  /* cannot fit within dst budget */
515    if (srcSize > HUF_BLOCKSIZE_MAX) return ERROR(srcSize_wrong);   /* current block size limit */
516    if (huffLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
517    if (!maxSymbolValue) maxSymbolValue = HUF_SYMBOLVALUE_MAX;
518    if (!huffLog) huffLog = HUF_TABLELOG_DEFAULT;
519
520    /* Scan input and build symbol stats */
521    {   size_t const largest = FSE_count (count, &maxSymbolValue, (const BYTE*)src, srcSize);
522        if (HUF_isError(largest)) return largest;
523        if (largest == srcSize) { *ostart = ((const BYTE*)src)[0]; return 1; }   /* rle */
524        if (largest <= (srcSize >> 7)+1) return 0;   /* Fast heuristic : not compressible enough */
525    }
526
527    /* Build Huffman Tree */
528    huffLog = HUF_optimalTableLog(huffLog, srcSize, maxSymbolValue);
529    {   size_t const maxBits = HUF_buildCTable (CTable, count, maxSymbolValue, huffLog);
530        if (HUF_isError(maxBits)) return maxBits;
531        huffLog = (U32)maxBits;
532    }
533
534    /* Write table description header */
535    {   size_t const hSize = HUF_writeCTable (op, dstSize, CTable, maxSymbolValue, huffLog);
536        if (HUF_isError(hSize)) return hSize;
537        if (hSize + 12 >= srcSize) return 0;   /* not useful to try compression */
538        //static U64 totalHSize = 0; static U32 nbHSize = 0; totalHSize += hSize; nbHSize++; if ((nbHSize & 63) == 1) printf("average : %6.3f \n", (double)totalHSize / nbHSize);
539        op += hSize;
540    }
541
542    /* Compress */
543    {   size_t const cSize = (singleStream) ?
544                            HUF_compress1X_usingCTable(op, oend - op, src, srcSize, CTable) :   /* single segment */
545                            HUF_compress4X_usingCTable(op, oend - op, src, srcSize, CTable);
546        if (HUF_isError(cSize)) return cSize;
547        if (cSize==0) return 0;   /* uncompressible */
548        op += cSize;
549    }
550
551    /* check compressibility */
552    if ((size_t)(op-ostart) >= srcSize-1)
553        return 0;
554
555    return op-ostart;
556}
557
558
559size_t HUF_compress1X (void* dst, size_t dstSize,
560                 const void* src, size_t srcSize,
561                 unsigned maxSymbolValue, unsigned huffLog)
562{
563    return HUF_compress_internal(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, 1);
564}
565
566size_t HUF_compress2 (void* dst, size_t dstSize,
567                const void* src, size_t srcSize,
568                unsigned maxSymbolValue, unsigned huffLog)
569{
570    return HUF_compress_internal(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, 0);
571}
572
573
574size_t HUF_compress (void* dst, size_t maxDstSize, const void* src, size_t srcSize)
575{
576    return HUF_compress2(dst, maxDstSize, src, (U32)srcSize, 255, HUF_TABLELOG_DEFAULT);
577}
Note: See TracBrowser for help on using the repository browser.