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