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 ****************************************************************/
HUF_optimalTableLog(unsigned maxTableLog,size_t srcSize,unsigned maxSymbolValue)80 unsigned 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 *********************************************************/
89 struct HUF_CElt_s {
90 U16 val;
91 BYTE nbBits;
92 }; /* typedef'd to HUF_CElt within huf_static.h */
93
94 typedef 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 */
HUF_writeCTable(void * dst,size_t maxDstSize,const HUF_CElt * CTable,U32 maxSymbolValue,U32 huffLog)104 size_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
HUF_readCTable(HUF_CElt * CTable,U32 maxSymbolValue,const void * src,size_t srcSize)170 size_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
HUF_setMaxHeight(nodeElt * huffNode,U32 lastNonNull,U32 maxNbBits)220 static 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
297 typedef struct {
298 U32 base;
299 U32 current;
300 } rankPos;
301
HUF_sort(nodeElt * huffNode,const U32 * count,U32 maxSymbolValue)302 static 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)
HUF_buildCTable(HUF_CElt * tree,const U32 * count,U32 maxSymbolValue,U32 maxNbBits)326 size_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
HUF_encodeSymbol(BIT_CStream_t * bitCPtr,U32 symbol,const HUF_CElt * CTable)394 static 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
HUF_compressBound(size_t size)399 size_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
HUF_compress1X_usingCTable(void * dst,size_t dstSize,const void * src,size_t srcSize,const HUF_CElt * CTable)409 size_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
HUF_compress4X_usingCTable(void * dst,size_t dstSize,const void * src,size_t srcSize,const HUF_CElt * CTable)452 size_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
HUF_compress_internal(void * dst,size_t dstSize,const void * src,size_t srcSize,unsigned maxSymbolValue,unsigned huffLog,unsigned singleStream)499 static 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
HUF_compress1X(void * dst,size_t dstSize,const void * src,size_t srcSize,unsigned maxSymbolValue,unsigned huffLog)559 size_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
HUF_compress2(void * dst,size_t dstSize,const void * src,size_t srcSize,unsigned maxSymbolValue,unsigned huffLog)566 size_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
HUF_compress(void * dst,size_t maxDstSize,const void * src,size_t srcSize)574 size_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 }
578