Line data Source code
1 : /* ******************************************************************
2 : FSE : Finite State Entropy encoder
3 : Copyright (C) 2013-2015, 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 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 : # define FORCE_INLINE static __forceinline
40 : # include <intrin.h> /* For Visual 2005 */
41 : # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
42 : # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
43 : #else
44 : # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
45 : # ifdef __GNUC__
46 : # define FORCE_INLINE static inline __attribute__((always_inline))
47 : # else
48 : # define FORCE_INLINE static inline
49 : # endif
50 : # else
51 : # define FORCE_INLINE static
52 : # endif /* __STDC_VERSION__ */
53 : #endif
54 :
55 :
56 : /* **************************************************************
57 : * Includes
58 : ****************************************************************/
59 : #include <stdlib.h> /* malloc, free, qsort */
60 : #include <string.h> /* memcpy, memset */
61 : #include <stdio.h> /* printf (debug) */
62 : #include "bitstream.h"
63 : #define FSE_STATIC_LINKING_ONLY
64 : #include "fse.h"
65 :
66 :
67 : /* **************************************************************
68 : * Error Management
69 : ****************************************************************/
70 : #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
71 :
72 :
73 : /* **************************************************************
74 : * Complex types
75 : ****************************************************************/
76 : typedef U32 CTable_max_t[FSE_CTABLE_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)];
77 :
78 :
79 : /* **************************************************************
80 : * Templates
81 : ****************************************************************/
82 : /*
83 : designed to be included
84 : for type-specific functions (template emulation in C)
85 : Objective is to write these functions only once, for improved maintenance
86 : */
87 :
88 : /* safety checks */
89 : #ifndef FSE_FUNCTION_EXTENSION
90 : # error "FSE_FUNCTION_EXTENSION must be defined"
91 : #endif
92 : #ifndef FSE_FUNCTION_TYPE
93 : # error "FSE_FUNCTION_TYPE must be defined"
94 : #endif
95 :
96 : /* Function names */
97 : #define FSE_CAT(X,Y) X##Y
98 : #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
99 : #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
100 :
101 :
102 : /* Function templates */
103 6244 : size_t FSE_buildCTable(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
104 : {
105 6244 : U32 const tableSize = 1 << tableLog;
106 6244 : U32 const tableMask = tableSize - 1;
107 6244 : void* const ptr = ct;
108 6244 : U16* const tableU16 = ( (U16*) ptr) + 2;
109 6244 : void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableLog ? tableSize>>1 : 1) ;
110 6244 : FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
111 6244 : U32 const step = FSE_TABLESTEP(tableSize);
112 : U32 cumul[FSE_MAX_SYMBOL_VALUE+2];
113 :
114 : FSE_FUNCTION_TYPE tableSymbol[FSE_MAX_TABLESIZE]; /* memset() is not necessary, even if static analyzer complain about it */
115 6244 : U32 highThreshold = tableSize-1;
116 :
117 : /* CTable header */
118 6244 : tableU16[-2] = (U16) tableLog;
119 6244 : tableU16[-1] = (U16) maxSymbolValue;
120 :
121 : /* For explanations on how to distribute symbol values over the table :
122 : * http://fastcompression.blogspot.fr/2014/02/fse-distributing-symbol-values.html */
123 :
124 : /* symbol start positions */
125 : { U32 u;
126 6244 : cumul[0] = 0;
127 137218 : for (u=1; u<=maxSymbolValue+1; u++) {
128 130974 : if (normalizedCounter[u-1]==-1) { /* Low proba symbol */
129 32864 : cumul[u] = cumul[u-1] + 1;
130 32864 : tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(u-1);
131 : } else {
132 98110 : cumul[u] = cumul[u-1] + normalizedCounter[u-1];
133 : } }
134 6244 : cumul[maxSymbolValue+1] = tableSize+1;
135 : }
136 :
137 : /* Spread symbols */
138 6244 : { U32 position = 0;
139 : U32 symbol;
140 137218 : for (symbol=0; symbol<=maxSymbolValue; symbol++) {
141 : int nbOccurences;
142 1732030 : for (nbOccurences=0; nbOccurences<normalizedCounter[symbol]; nbOccurences++) {
143 1601056 : tableSymbol[position] = (FSE_FUNCTION_TYPE)symbol;
144 1601056 : position = (position + step) & tableMask;
145 1601056 : while (position > highThreshold) position = (position + step) & tableMask; /* Low proba area */
146 : } }
147 :
148 6244 : if (position!=0) return ERROR(GENERIC); /* Must have gone through all positions */
149 : }
150 :
151 : /* Build table */
152 1640164 : { U32 u; for (u=0; u<tableSize; u++) {
153 1633920 : FSE_FUNCTION_TYPE s = tableSymbol[u]; /* note : static analyzer may not understand tableSymbol is properly initialized */
154 1633920 : tableU16[cumul[s]++] = (U16) (tableSize+u); /* TableU16 : sorted by symbol order; gives next state value */
155 : } }
156 :
157 : /* Build Symbol Transformation Table */
158 6244 : { unsigned total = 0;
159 : unsigned s;
160 137218 : for (s=0; s<=maxSymbolValue; s++) {
161 130974 : switch (normalizedCounter[s])
162 : {
163 14754 : case 0: break;
164 :
165 : case -1:
166 : case 1:
167 46180 : symbolTT[s].deltaNbBits = (tableLog << 16) - (1<<tableLog);
168 46180 : symbolTT[s].deltaFindState = total - 1;
169 46180 : total ++;
170 46180 : break;
171 : default :
172 : {
173 70040 : U32 const maxBitsOut = tableLog - BIT_highbit32 (normalizedCounter[s]-1);
174 70040 : U32 const minStatePlus = normalizedCounter[s] << maxBitsOut;
175 70040 : symbolTT[s].deltaNbBits = (maxBitsOut << 16) - minStatePlus;
176 70040 : symbolTT[s].deltaFindState = total - normalizedCounter[s];
177 70040 : total += normalizedCounter[s];
178 : } } } }
179 :
180 6244 : return 0;
181 : }
182 :
183 :
184 :
185 : #ifndef FSE_COMMONDEFS_ONLY
186 :
187 : /*-**************************************************************
188 : * FSE NCount encoding-decoding
189 : ****************************************************************/
190 5940 : size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
191 : {
192 5940 : size_t maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3;
193 5940 : return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */
194 : }
195 :
196 113946 : static short FSE_abs(short a) { return (short)(a<0 ? -a : a); }
197 :
198 5940 : static size_t FSE_writeNCount_generic (void* header, size_t headerBufferSize,
199 : const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
200 : unsigned writeIsSafe)
201 : {
202 5940 : BYTE* const ostart = (BYTE*) header;
203 5940 : BYTE* out = ostart;
204 5940 : BYTE* const oend = ostart + headerBufferSize;
205 : int nbBits;
206 5940 : const int tableSize = 1 << tableLog;
207 : int remaining;
208 : int threshold;
209 : U32 bitStream;
210 : int bitCount;
211 5940 : unsigned charnum = 0;
212 5940 : int previous0 = 0;
213 :
214 5940 : bitStream = 0;
215 5940 : bitCount = 0;
216 : /* Table Size */
217 5940 : bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount;
218 5940 : bitCount += 4;
219 :
220 : /* Init */
221 5940 : remaining = tableSize+1; /* +1 for extra accuracy */
222 5940 : threshold = tableSize;
223 5940 : nbBits = tableLog+1;
224 :
225 125826 : while (remaining>1) { /* stops at 1 */
226 113946 : if (previous0) {
227 9732 : unsigned start = charnum;
228 9732 : while (!normalizedCounter[charnum]) charnum++;
229 19478 : while (charnum >= start+24) {
230 14 : start+=24;
231 14 : bitStream += 0xFFFFU << bitCount;
232 14 : if ((!writeIsSafe) && (out > oend-2)) return ERROR(dstSize_tooSmall); /* Buffer overflow */
233 14 : out[0] = (BYTE) bitStream;
234 14 : out[1] = (BYTE)(bitStream>>8);
235 14 : out+=2;
236 14 : bitStream>>=16;
237 : }
238 20122 : while (charnum >= start+3) {
239 658 : start+=3;
240 658 : bitStream += 3 << bitCount;
241 658 : bitCount += 2;
242 : }
243 9732 : bitStream += (charnum-start) << bitCount;
244 9732 : bitCount += 2;
245 9732 : if (bitCount>16) {
246 998 : if ((!writeIsSafe) && (out > oend - 2)) return ERROR(dstSize_tooSmall); /* Buffer overflow */
247 998 : out[0] = (BYTE)bitStream;
248 998 : out[1] = (BYTE)(bitStream>>8);
249 998 : out += 2;
250 998 : bitStream >>= 16;
251 998 : bitCount -= 16;
252 : } }
253 113946 : { short count = normalizedCounter[charnum++];
254 113946 : const short max = (short)((2*threshold-1)-remaining);
255 113946 : remaining -= FSE_abs(count);
256 113946 : if (remaining<1) return ERROR(GENERIC);
257 113946 : count++; /* +1 for extra accuracy */
258 113946 : if (count>=threshold) count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */
259 113946 : bitStream += count << bitCount;
260 113946 : bitCount += nbBits;
261 113946 : bitCount -= (count<max);
262 113946 : previous0 = (count==1);
263 113946 : while (remaining<threshold) nbBits--, threshold>>=1;
264 : }
265 113946 : if (bitCount>16) {
266 32800 : if ((!writeIsSafe) && (out > oend - 2)) return ERROR(dstSize_tooSmall); /* Buffer overflow */
267 32800 : out[0] = (BYTE)bitStream;
268 32800 : out[1] = (BYTE)(bitStream>>8);
269 32800 : out += 2;
270 32800 : bitStream >>= 16;
271 32800 : bitCount -= 16;
272 : } }
273 :
274 : /* flush remaining bitStream */
275 5940 : if ((!writeIsSafe) && (out > oend - 2)) return ERROR(dstSize_tooSmall); /* Buffer overflow */
276 5940 : out[0] = (BYTE)bitStream;
277 5940 : out[1] = (BYTE)(bitStream>>8);
278 5940 : out+= (bitCount+7) /8;
279 :
280 5940 : if (charnum > maxSymbolValue + 1) return ERROR(GENERIC);
281 :
282 5940 : return (out-ostart);
283 : }
284 :
285 :
286 5940 : size_t FSE_writeNCount (void* buffer, size_t bufferSize, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
287 : {
288 5940 : if (tableLog > FSE_MAX_TABLELOG) return ERROR(GENERIC); /* Unsupported */
289 5940 : if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */
290 :
291 5940 : if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
292 0 : return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
293 :
294 5940 : return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1);
295 : }
296 :
297 :
298 :
299 : /*-**************************************************************
300 : * Counting histogram
301 : ****************************************************************/
302 : /*! FSE_count_simple
303 : This function just counts byte values within `src`,
304 : and store the histogram into table `count`.
305 : This function is unsafe : it doesn't check that all values within `src` can fit into `count`.
306 : For this reason, prefer using a table `count` with 256 elements.
307 : @return : count of most numerous element
308 : */
309 2756 : static size_t FSE_count_simple(unsigned* count, unsigned* maxSymbolValuePtr,
310 : const void* src, size_t srcSize)
311 : {
312 2756 : const BYTE* ip = (const BYTE*)src;
313 2756 : const BYTE* const end = ip + srcSize;
314 2756 : unsigned maxSymbolValue = *maxSymbolValuePtr;
315 2756 : unsigned max=0;
316 :
317 :
318 2756 : memset(count, 0, (maxSymbolValue+1)*sizeof(*count));
319 2756 : if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; }
320 :
321 2756 : while (ip<end) count[*ip++]++;
322 :
323 2756 : while (!count[maxSymbolValue]) maxSymbolValue--;
324 2756 : *maxSymbolValuePtr = maxSymbolValue;
325 :
326 2756 : { U32 s; for (s=0; s<=maxSymbolValue; s++) if (count[s] > max) max = count[s]; }
327 :
328 2756 : return (size_t)max;
329 : }
330 :
331 :
332 6830 : static size_t FSE_count_parallel(unsigned* count, unsigned* maxSymbolValuePtr,
333 : const void* source, size_t sourceSize,
334 : unsigned checkMax)
335 : {
336 6830 : const BYTE* ip = (const BYTE*)source;
337 6830 : const BYTE* const iend = ip+sourceSize;
338 6830 : unsigned maxSymbolValue = *maxSymbolValuePtr;
339 6830 : unsigned max=0;
340 :
341 :
342 6830 : U32 Counting1[256] = { 0 };
343 6830 : U32 Counting2[256] = { 0 };
344 6830 : U32 Counting3[256] = { 0 };
345 6830 : U32 Counting4[256] = { 0 };
346 :
347 : /* safety checks */
348 6830 : if (!sourceSize) {
349 0 : memset(count, 0, maxSymbolValue + 1);
350 0 : *maxSymbolValuePtr = 0;
351 0 : return 0;
352 : }
353 6830 : if (!maxSymbolValue) maxSymbolValue = 255; /* 0 == default */
354 :
355 : /* by stripes of 16 bytes */
356 6830 : { U32 cached = MEM_read32(ip); ip += 4;
357 21290798 : while (ip < iend-15) {
358 21277138 : U32 c = cached; cached = MEM_read32(ip); ip += 4;
359 21277138 : Counting1[(BYTE) c ]++;
360 21277138 : Counting2[(BYTE)(c>>8) ]++;
361 21277138 : Counting3[(BYTE)(c>>16)]++;
362 21277138 : Counting4[ c>>24 ]++;
363 21277138 : c = cached; cached = MEM_read32(ip); ip += 4;
364 21277138 : Counting1[(BYTE) c ]++;
365 21277138 : Counting2[(BYTE)(c>>8) ]++;
366 21277138 : Counting3[(BYTE)(c>>16)]++;
367 21277138 : Counting4[ c>>24 ]++;
368 21277138 : c = cached; cached = MEM_read32(ip); ip += 4;
369 21277138 : Counting1[(BYTE) c ]++;
370 21277138 : Counting2[(BYTE)(c>>8) ]++;
371 21277138 : Counting3[(BYTE)(c>>16)]++;
372 21277138 : Counting4[ c>>24 ]++;
373 21277138 : c = cached; cached = MEM_read32(ip); ip += 4;
374 21277138 : Counting1[(BYTE) c ]++;
375 21277138 : Counting2[(BYTE)(c>>8) ]++;
376 21277138 : Counting3[(BYTE)(c>>16)]++;
377 21277138 : Counting4[ c>>24 ]++;
378 : }
379 6830 : ip-=4;
380 : }
381 :
382 : /* finish last symbols */
383 6830 : while (ip<iend) Counting1[*ip++]++;
384 :
385 6830 : if (checkMax) { /* verify stats will fit into destination table */
386 0 : U32 s; for (s=255; s>maxSymbolValue; s--) {
387 0 : Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
388 0 : if (Counting1[s]) return ERROR(maxSymbolValue_tooSmall);
389 : } }
390 :
391 987010 : { U32 s; for (s=0; s<=maxSymbolValue; s++) {
392 980180 : count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s];
393 980180 : if (count[s] > max) max = count[s];
394 : }}
395 :
396 6830 : while (!count[maxSymbolValue]) maxSymbolValue--;
397 6830 : *maxSymbolValuePtr = maxSymbolValue;
398 6830 : return (size_t)max;
399 : }
400 :
401 : /* fast variant (unsafe : won't check if src contains values beyond count[] limit) */
402 9586 : size_t FSE_countFast(unsigned* count, unsigned* maxSymbolValuePtr,
403 : const void* source, size_t sourceSize)
404 : {
405 9586 : if (sourceSize < 1500) return FSE_count_simple(count, maxSymbolValuePtr, source, sourceSize);
406 6830 : return FSE_count_parallel(count, maxSymbolValuePtr, source, sourceSize, 0);
407 : }
408 :
409 5362 : size_t FSE_count(unsigned* count, unsigned* maxSymbolValuePtr,
410 : const void* source, size_t sourceSize)
411 : {
412 5362 : if (*maxSymbolValuePtr <255)
413 0 : return FSE_count_parallel(count, maxSymbolValuePtr, source, sourceSize, 1);
414 5362 : *maxSymbolValuePtr = 255;
415 5362 : return FSE_countFast(count, maxSymbolValuePtr, source, sourceSize);
416 : }
417 :
418 :
419 :
420 : /*-**************************************************************
421 : * FSE Compression Code
422 : ****************************************************************/
423 : /*! FSE_sizeof_CTable() :
424 : FSE_CTable is a variable size structure which contains :
425 : `U16 tableLog;`
426 : `U16 maxSymbolValue;`
427 : `U16 nextStateNumber[1 << tableLog];` // This size is variable
428 : `FSE_symbolCompressionTransform symbolTT[maxSymbolValue+1];` // This size is variable
429 : Allocation is manual (C standard does not support variable-size structures).
430 : */
431 :
432 0 : size_t FSE_sizeof_CTable (unsigned maxSymbolValue, unsigned tableLog)
433 : {
434 : size_t size;
435 : FSE_STATIC_ASSERT((size_t)FSE_CTABLE_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)*4 >= sizeof(CTable_max_t)); /* A compilation error here means FSE_CTABLE_SIZE_U32 is not large enough */
436 0 : if (tableLog > FSE_MAX_TABLELOG) return ERROR(GENERIC);
437 0 : size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32);
438 0 : return size;
439 : }
440 :
441 0 : FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog)
442 : {
443 : size_t size;
444 0 : if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
445 0 : size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32);
446 0 : return (FSE_CTable*)malloc(size);
447 : }
448 :
449 0 : void FSE_freeCTable (FSE_CTable* ct) { free(ct); }
450 :
451 : /* provides the minimum logSize to safely represent a distribution */
452 13916 : static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
453 : {
454 13916 : U32 minBitsSrc = BIT_highbit32((U32)(srcSize - 1)) + 1;
455 13916 : U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
456 13916 : U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
457 13916 : return minBits;
458 : }
459 :
460 7976 : unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
461 : {
462 7976 : U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
463 7976 : U32 tableLog = maxTableLog;
464 7976 : U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
465 7976 : if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
466 7976 : if (maxBitsSrc < tableLog) tableLog = maxBitsSrc; /* Accuracy can be reduced */
467 7976 : if (minBits > tableLog) tableLog = minBits; /* Need a minimum to safely represent all symbol values */
468 7976 : if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG;
469 7976 : if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG;
470 7976 : return tableLog;
471 : }
472 :
473 5940 : unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
474 : {
475 5940 : return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
476 : }
477 :
478 :
479 : /* Secondary normalization method.
480 : To be used when primary method fails. */
481 :
482 6 : static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue)
483 : {
484 : U32 s;
485 6 : U32 distributed = 0;
486 : U32 ToDistribute;
487 :
488 : /* Init */
489 6 : U32 lowThreshold = (U32)(total >> tableLog);
490 6 : U32 lowOne = (U32)((total * 3) >> (tableLog + 1));
491 :
492 272 : for (s=0; s<=maxSymbolValue; s++) {
493 266 : if (count[s] == 0) {
494 52 : norm[s]=0;
495 52 : continue;
496 : }
497 214 : if (count[s] <= lowThreshold) {
498 130 : norm[s] = -1;
499 130 : distributed++;
500 130 : total -= count[s];
501 130 : continue;
502 : }
503 84 : if (count[s] <= lowOne) {
504 8 : norm[s] = 1;
505 8 : distributed++;
506 8 : total -= count[s];
507 8 : continue;
508 : }
509 76 : norm[s]=-2;
510 : }
511 6 : ToDistribute = (1 << tableLog) - distributed;
512 :
513 6 : if ((total / ToDistribute) > lowOne) {
514 : /* risk of rounding to zero */
515 0 : lowOne = (U32)((total * 3) / (ToDistribute * 2));
516 0 : for (s=0; s<=maxSymbolValue; s++) {
517 0 : if ((norm[s] == -2) && (count[s] <= lowOne)) {
518 0 : norm[s] = 1;
519 0 : distributed++;
520 0 : total -= count[s];
521 0 : continue;
522 : } }
523 0 : ToDistribute = (1 << tableLog) - distributed;
524 : }
525 :
526 6 : if (distributed == maxSymbolValue+1) {
527 : /* all values are pretty poor;
528 : probably incompressible data (should have already been detected);
529 : find max, then give all remaining points to max */
530 0 : U32 maxV = 0, maxC = 0;
531 0 : for (s=0; s<=maxSymbolValue; s++)
532 0 : if (count[s] > maxC) maxV=s, maxC=count[s];
533 0 : norm[maxV] += (short)ToDistribute;
534 0 : return 0;
535 : }
536 :
537 : {
538 6 : U64 const vStepLog = 62 - tableLog;
539 6 : U64 const mid = (1ULL << (vStepLog-1)) - 1;
540 6 : U64 const rStep = ((((U64)1<<vStepLog) * ToDistribute) + mid) / total; /* scale on remaining */
541 6 : U64 tmpTotal = mid;
542 272 : for (s=0; s<=maxSymbolValue; s++) {
543 266 : if (norm[s]==-2) {
544 76 : U64 end = tmpTotal + (count[s] * rStep);
545 76 : U32 sStart = (U32)(tmpTotal >> vStepLog);
546 76 : U32 sEnd = (U32)(end >> vStepLog);
547 76 : U32 weight = sEnd - sStart;
548 76 : if (weight < 1)
549 0 : return ERROR(GENERIC);
550 76 : norm[s] = (short)weight;
551 76 : tmpTotal = end;
552 : } } }
553 :
554 6 : return 0;
555 : }
556 :
557 :
558 5940 : size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog,
559 : const unsigned* count, size_t total,
560 : unsigned maxSymbolValue)
561 : {
562 : /* Sanity checks */
563 5940 : if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
564 5940 : if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported size */
565 5940 : if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported size */
566 5940 : if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */
567 :
568 5940 : { U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
569 :
570 5940 : U64 const scale = 62 - tableLog;
571 5940 : U64 const step = ((U64)1<<62) / total; /* <== here, one division ! */
572 5940 : U64 const vStep = 1ULL<<(scale-20);
573 5940 : int stillToDistribute = 1<<tableLog;
574 : unsigned s;
575 5940 : unsigned largest=0;
576 5940 : short largestP=0;
577 5940 : U32 lowThreshold = (U32)(total >> tableLog);
578 :
579 124908 : for (s=0; s<=maxSymbolValue; s++) {
580 118968 : if (count[s] == total) return 0; /* rle special case */
581 118968 : if (count[s] == 0) { normalizedCounter[s]=0; continue; }
582 104214 : if (count[s] <= lowThreshold) {
583 31246 : normalizedCounter[s] = -1;
584 31246 : stillToDistribute--;
585 : } else {
586 72968 : short proba = (short)((count[s]*step) >> scale);
587 72968 : if (proba<8) {
588 39974 : U64 restToBeat = vStep * rtbTable[proba];
589 39974 : proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat;
590 : }
591 72968 : if (proba > largestP) largestP=proba, largest=s;
592 72968 : normalizedCounter[s] = proba;
593 72968 : stillToDistribute -= proba;
594 : } }
595 5940 : if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
596 : /* corner case, need another normalization method */
597 6 : size_t errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue);
598 6 : if (FSE_isError(errorCode)) return errorCode;
599 : }
600 5934 : else normalizedCounter[largest] += (short)stillToDistribute;
601 : }
602 :
603 : #if 0
604 : { /* Print Table (debug) */
605 : U32 s;
606 : U32 nTotal = 0;
607 : for (s=0; s<=maxSymbolValue; s++)
608 : printf("%3i: %4i \n", s, normalizedCounter[s]);
609 : for (s=0; s<=maxSymbolValue; s++)
610 : nTotal += abs(normalizedCounter[s]);
611 : if (nTotal != (1U<<tableLog))
612 : printf("Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog);
613 : getchar();
614 : }
615 : #endif
616 :
617 5940 : return tableLog;
618 : }
619 :
620 :
621 : /* fake FSE_CTable, for raw (uncompressed) input */
622 0 : size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits)
623 : {
624 0 : const unsigned tableSize = 1 << nbBits;
625 0 : const unsigned tableMask = tableSize - 1;
626 0 : const unsigned maxSymbolValue = tableMask;
627 0 : void* const ptr = ct;
628 0 : U16* const tableU16 = ( (U16*) ptr) + 2;
629 0 : void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableSize>>1); /* assumption : tableLog >= 1 */
630 0 : FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
631 : unsigned s;
632 :
633 : /* Sanity checks */
634 0 : if (nbBits < 1) return ERROR(GENERIC); /* min size */
635 :
636 : /* header */
637 0 : tableU16[-2] = (U16) nbBits;
638 0 : tableU16[-1] = (U16) maxSymbolValue;
639 :
640 : /* Build table */
641 0 : for (s=0; s<tableSize; s++)
642 0 : tableU16[s] = (U16)(tableSize + s);
643 :
644 : /* Build Symbol Transformation Table */
645 0 : { const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits);
646 :
647 0 : for (s=0; s<=maxSymbolValue; s++) {
648 0 : symbolTT[s].deltaNbBits = deltaNbBits;
649 0 : symbolTT[s].deltaFindState = s-1;
650 : } }
651 :
652 :
653 0 : return 0;
654 : }
655 :
656 : /* fake FSE_CTable, for rle (100% always same symbol) input */
657 16 : size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue)
658 : {
659 16 : void* ptr = ct;
660 16 : U16* tableU16 = ( (U16*) ptr) + 2;
661 16 : void* FSCTptr = (U32*)ptr + 2;
662 16 : FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr;
663 :
664 : /* header */
665 16 : tableU16[-2] = (U16) 0;
666 16 : tableU16[-1] = (U16) symbolValue;
667 :
668 : /* Build table */
669 16 : tableU16[0] = 0;
670 16 : tableU16[1] = 0; /* just in case */
671 :
672 : /* Build Symbol Transformation Table */
673 16 : symbolTT[symbolValue].deltaNbBits = 0;
674 16 : symbolTT[symbolValue].deltaFindState = 0;
675 :
676 16 : return 0;
677 : }
678 :
679 :
680 2036 : static size_t FSE_compress_usingCTable_generic (void* dst, size_t dstSize,
681 : const void* src, size_t srcSize,
682 : const FSE_CTable* ct, const unsigned fast)
683 : {
684 2036 : const BYTE* const istart = (const BYTE*) src;
685 2036 : const BYTE* const iend = istart + srcSize;
686 2036 : const BYTE* ip=iend;
687 :
688 :
689 : BIT_CStream_t bitC;
690 : FSE_CState_t CState1, CState2;
691 :
692 : /* init */
693 2036 : if (srcSize <= 2) return 0;
694 2036 : { size_t const errorCode = BIT_initCStream(&bitC, dst, dstSize);
695 2036 : if (FSE_isError(errorCode)) return 0; }
696 :
697 : #define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
698 :
699 2036 : if (srcSize & 1) {
700 1996 : FSE_initCState2(&CState1, ct, *--ip);
701 1996 : FSE_initCState2(&CState2, ct, *--ip);
702 1996 : FSE_encodeSymbol(&bitC, &CState1, *--ip);
703 1996 : FSE_FLUSHBITS(&bitC);
704 : } else {
705 40 : FSE_initCState2(&CState2, ct, *--ip);
706 40 : FSE_initCState2(&CState1, ct, *--ip);
707 : }
708 :
709 : /* join to mod 4 */
710 2036 : srcSize -= 2;
711 2036 : if ((sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) && (srcSize & 2)) { /* test bit 2 */
712 28 : FSE_encodeSymbol(&bitC, &CState2, *--ip);
713 28 : FSE_encodeSymbol(&bitC, &CState1, *--ip);
714 28 : FSE_FLUSHBITS(&bitC);
715 : }
716 :
717 : /* 2 or 4 encoding per loop */
718 131142 : for ( ; ip>istart ; ) {
719 :
720 127070 : FSE_encodeSymbol(&bitC, &CState2, *--ip);
721 :
722 : if (sizeof(bitC.bitContainer)*8 < FSE_MAX_TABLELOG*2+7 ) /* this test must be static */
723 : FSE_FLUSHBITS(&bitC);
724 :
725 127070 : FSE_encodeSymbol(&bitC, &CState1, *--ip);
726 :
727 : if (sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) { /* this test must be static */
728 127070 : FSE_encodeSymbol(&bitC, &CState2, *--ip);
729 127070 : FSE_encodeSymbol(&bitC, &CState1, *--ip);
730 : }
731 :
732 127070 : FSE_FLUSHBITS(&bitC);
733 : }
734 :
735 2036 : FSE_flushCState(&bitC, &CState2);
736 2036 : FSE_flushCState(&bitC, &CState1);
737 2036 : return BIT_closeCStream(&bitC);
738 : }
739 :
740 2036 : size_t FSE_compress_usingCTable (void* dst, size_t dstSize,
741 : const void* src, size_t srcSize,
742 : const FSE_CTable* ct)
743 : {
744 2036 : const unsigned fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
745 :
746 2036 : if (fast)
747 2036 : return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1);
748 : else
749 0 : return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0);
750 : }
751 :
752 :
753 74 : size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); }
754 :
755 2036 : size_t FSE_compress2 (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
756 : {
757 2036 : const BYTE* const istart = (const BYTE*) src;
758 2036 : const BYTE* ip = istart;
759 :
760 2036 : BYTE* const ostart = (BYTE*) dst;
761 2036 : BYTE* op = ostart;
762 2036 : BYTE* const oend = ostart + dstSize;
763 :
764 : U32 count[FSE_MAX_SYMBOL_VALUE+1];
765 : S16 norm[FSE_MAX_SYMBOL_VALUE+1];
766 : CTable_max_t ct;
767 : size_t errorCode;
768 :
769 : /* init conditions */
770 2036 : if (srcSize <= 1) return 0; /* Uncompressible */
771 2036 : if (!maxSymbolValue) maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
772 2036 : if (!tableLog) tableLog = FSE_DEFAULT_TABLELOG;
773 :
774 : /* Scan input and build symbol stats */
775 2036 : errorCode = FSE_count (count, &maxSymbolValue, ip, srcSize);
776 2036 : if (FSE_isError(errorCode)) return errorCode;
777 2036 : if (errorCode == srcSize) return 1;
778 2036 : if (errorCode == 1) return 0; /* each symbol only present once */
779 2036 : if (errorCode < (srcSize >> 7)) return 0; /* Heuristic : not compressible enough */
780 :
781 2036 : tableLog = FSE_optimalTableLog(tableLog, srcSize, maxSymbolValue);
782 2036 : errorCode = FSE_normalizeCount (norm, tableLog, count, srcSize, maxSymbolValue);
783 2036 : if (FSE_isError(errorCode)) return errorCode;
784 :
785 : /* Write table description header */
786 2036 : errorCode = FSE_writeNCount (op, oend-op, norm, maxSymbolValue, tableLog);
787 2036 : if (FSE_isError(errorCode)) return errorCode;
788 2036 : op += errorCode;
789 :
790 : /* Compress */
791 2036 : errorCode = FSE_buildCTable (ct, norm, maxSymbolValue, tableLog);
792 2036 : if (FSE_isError(errorCode)) return errorCode;
793 2036 : errorCode = FSE_compress_usingCTable(op, oend - op, ip, srcSize, ct);
794 2036 : if (errorCode == 0) return 0; /* not enough space for compressed data */
795 2036 : op += errorCode;
796 :
797 : /* check compressibility */
798 2036 : if ( (size_t)(op-ostart) >= srcSize-1 )
799 0 : return 0;
800 :
801 2036 : return op-ostart;
802 : }
803 :
804 2036 : size_t FSE_compress (void* dst, size_t dstSize, const void* src, size_t srcSize)
805 : {
806 2036 : return FSE_compress2(dst, dstSize, src, (U32)srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG);
807 : }
808 :
809 :
810 : #endif /* FSE_COMMONDEFS_ONLY */
|
