1 // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0-only
2 /* ******************************************************************
3 * FSE : Finite State Entropy encoder
4 * Copyright (c) 2013-2020, Yann Collet, Facebook, Inc.
5 *
6 * You can contact the author at :
7 * - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
8 * - Public forum : https://groups.google.com/forum/#!forum/lz4c
9 *
10 * This source code is licensed under both the BSD-style license (found in the
11 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
12 * in the COPYING file in the root directory of this source tree).
13 * You may select, at your option, one of the above-listed licenses.
14 ****************************************************************** */
15
16 /* **************************************************************
17 * Includes
18 ****************************************************************/
19 #include <stdlib.h> /* malloc, free, qsort */
20 #include <string.h> /* memcpy, memset */
21 #include "../common/compiler.h"
22 #include "../common/mem.h" /* U32, U16, etc. */
23 #include "../common/debug.h" /* assert, DEBUGLOG */
24 #include "hist.h" /* HIST_count_wksp */
25 #include "../common/bitstream.h"
26 #define FSE_STATIC_LINKING_ONLY
27 #include "../common/fse.h"
28 #include "../common/error_private.h"
29
30
31 /* **************************************************************
32 * Error Management
33 ****************************************************************/
34 #define FSE_isError ERR_isError
35
36
37 /* **************************************************************
38 * Templates
39 ****************************************************************/
40 /*
41 designed to be included
42 for type-specific functions (template emulation in C)
43 Objective is to write these functions only once, for improved maintenance
44 */
45
46 /* safety checks */
47 #ifndef FSE_FUNCTION_EXTENSION
48 # error "FSE_FUNCTION_EXTENSION must be defined"
49 #endif
50 #ifndef FSE_FUNCTION_TYPE
51 # error "FSE_FUNCTION_TYPE must be defined"
52 #endif
53
54 /* Function names */
55 #define FSE_CAT(X,Y) X##Y
56 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
57 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
58
59
60 /* Function templates */
61
62 /* FSE_buildCTable_wksp() :
63 * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`).
64 * wkspSize should be sized to handle worst case situation, which is `1<<max_tableLog * sizeof(FSE_FUNCTION_TYPE)`
65 * workSpace must also be properly aligned with FSE_FUNCTION_TYPE requirements
66 */
FSE_buildCTable_wksp(FSE_CTable * ct,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog,void * workSpace,size_t wkspSize)67 size_t FSE_buildCTable_wksp(FSE_CTable* ct,
68 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
69 void* workSpace, size_t wkspSize)
70 {
71 U32 const tableSize = 1 << tableLog;
72 U32 const tableMask = tableSize - 1;
73 void* const ptr = ct;
74 U16* const tableU16 = ( (U16*) ptr) + 2;
75 void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableLog ? tableSize>>1 : 1) ;
76 FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
77 U32 const step = FSE_TABLESTEP(tableSize);
78 U32 cumul[FSE_MAX_SYMBOL_VALUE+2];
79
80 FSE_FUNCTION_TYPE* const tableSymbol = (FSE_FUNCTION_TYPE*)workSpace;
81 U32 highThreshold = tableSize-1;
82
83 /* CTable header */
84 if (((size_t)1 << tableLog) * sizeof(FSE_FUNCTION_TYPE) > wkspSize) return ERROR(tableLog_tooLarge);
85 tableU16[-2] = (U16) tableLog;
86 tableU16[-1] = (U16) maxSymbolValue;
87 assert(tableLog < 16); /* required for threshold strategy to work */
88
89 /* For explanations on how to distribute symbol values over the table :
90 * http://fastcompression.blogspot.fr/2014/02/fse-distributing-symbol-values.html */
91
92 #ifdef __clang_analyzer__
93 memset(tableSymbol, 0, sizeof(*tableSymbol) * tableSize); /* useless initialization, just to keep scan-build happy */
94 #endif
95
96 /* symbol start positions */
97 { U32 u;
98 cumul[0] = 0;
99 for (u=1; u <= maxSymbolValue+1; u++) {
100 if (normalizedCounter[u-1]==-1) { /* Low proba symbol */
101 cumul[u] = cumul[u-1] + 1;
102 tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(u-1);
103 } else {
104 cumul[u] = cumul[u-1] + normalizedCounter[u-1];
105 } }
106 cumul[maxSymbolValue+1] = tableSize+1;
107 }
108
109 /* Spread symbols */
110 { U32 position = 0;
111 U32 symbol;
112 for (symbol=0; symbol<=maxSymbolValue; symbol++) {
113 int nbOccurrences;
114 int const freq = normalizedCounter[symbol];
115 for (nbOccurrences=0; nbOccurrences<freq; nbOccurrences++) {
116 tableSymbol[position] = (FSE_FUNCTION_TYPE)symbol;
117 position = (position + step) & tableMask;
118 while (position > highThreshold)
119 position = (position + step) & tableMask; /* Low proba area */
120 } }
121
122 assert(position==0); /* Must have initialized all positions */
123 }
124
125 /* Build table */
126 { U32 u; for (u=0; u<tableSize; u++) {
127 FSE_FUNCTION_TYPE s = tableSymbol[u]; /* note : static analyzer may not understand tableSymbol is properly initialized */
128 tableU16[cumul[s]++] = (U16) (tableSize+u); /* TableU16 : sorted by symbol order; gives next state value */
129 } }
130
131 /* Build Symbol Transformation Table */
132 { unsigned total = 0;
133 unsigned s;
134 for (s=0; s<=maxSymbolValue; s++) {
135 switch (normalizedCounter[s])
136 {
137 case 0:
138 /* filling nonetheless, for compatibility with FSE_getMaxNbBits() */
139 symbolTT[s].deltaNbBits = ((tableLog+1) << 16) - (1<<tableLog);
140 break;
141
142 case -1:
143 case 1:
144 symbolTT[s].deltaNbBits = (tableLog << 16) - (1<<tableLog);
145 symbolTT[s].deltaFindState = total - 1;
146 total ++;
147 break;
148 default :
149 {
150 U32 const maxBitsOut = tableLog - BIT_highbit32 (normalizedCounter[s]-1);
151 U32 const minStatePlus = normalizedCounter[s] << maxBitsOut;
152 symbolTT[s].deltaNbBits = (maxBitsOut << 16) - minStatePlus;
153 symbolTT[s].deltaFindState = total - normalizedCounter[s];
154 total += normalizedCounter[s];
155 } } } }
156
157 #if 0 /* debug : symbol costs */
158 DEBUGLOG(5, "\n --- table statistics : ");
159 { U32 symbol;
160 for (symbol=0; symbol<=maxSymbolValue; symbol++) {
161 DEBUGLOG(5, "%3u: w=%3i, maxBits=%u, fracBits=%.2f",
162 symbol, normalizedCounter[symbol],
163 FSE_getMaxNbBits(symbolTT, symbol),
164 (double)FSE_bitCost(symbolTT, tableLog, symbol, 8) / 256);
165 }
166 }
167 #endif
168
169 return 0;
170 }
171
172
FSE_buildCTable(FSE_CTable * ct,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog)173 size_t FSE_buildCTable(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
174 {
175 FSE_FUNCTION_TYPE tableSymbol[FSE_MAX_TABLESIZE]; /* memset() is not necessary, even if static analyzer complain about it */
176 return FSE_buildCTable_wksp(ct, normalizedCounter, maxSymbolValue, tableLog, tableSymbol, sizeof(tableSymbol));
177 }
178
179
180
181 #ifndef FSE_COMMONDEFS_ONLY
182
183
184 /*-**************************************************************
185 * FSE NCount encoding
186 ****************************************************************/
FSE_NCountWriteBound(unsigned maxSymbolValue,unsigned tableLog)187 size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
188 {
189 size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3;
190 return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */
191 }
192
193 static size_t
FSE_writeNCount_generic(void * header,size_t headerBufferSize,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog,unsigned writeIsSafe)194 FSE_writeNCount_generic (void* header, size_t headerBufferSize,
195 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
196 unsigned writeIsSafe)
197 {
198 BYTE* const ostart = (BYTE*) header;
199 BYTE* out = ostart;
200 BYTE* const oend = ostart + headerBufferSize;
201 int nbBits;
202 const int tableSize = 1 << tableLog;
203 int remaining;
204 int threshold;
205 U32 bitStream = 0;
206 int bitCount = 0;
207 unsigned symbol = 0;
208 unsigned const alphabetSize = maxSymbolValue + 1;
209 int previousIs0 = 0;
210
211 /* Table Size */
212 bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount;
213 bitCount += 4;
214
215 /* Init */
216 remaining = tableSize+1; /* +1 for extra accuracy */
217 threshold = tableSize;
218 nbBits = tableLog+1;
219
220 while ((symbol < alphabetSize) && (remaining>1)) { /* stops at 1 */
221 if (previousIs0) {
222 unsigned start = symbol;
223 while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++;
224 if (symbol == alphabetSize) break; /* incorrect distribution */
225 while (symbol >= start+24) {
226 start+=24;
227 bitStream += 0xFFFFU << bitCount;
228 if ((!writeIsSafe) && (out > oend-2))
229 return ERROR(dstSize_tooSmall); /* Buffer overflow */
230 out[0] = (BYTE) bitStream;
231 out[1] = (BYTE)(bitStream>>8);
232 out+=2;
233 bitStream>>=16;
234 }
235 while (symbol >= start+3) {
236 start+=3;
237 bitStream += 3 << bitCount;
238 bitCount += 2;
239 }
240 bitStream += (symbol-start) << bitCount;
241 bitCount += 2;
242 if (bitCount>16) {
243 if ((!writeIsSafe) && (out > oend - 2))
244 return ERROR(dstSize_tooSmall); /* Buffer overflow */
245 out[0] = (BYTE)bitStream;
246 out[1] = (BYTE)(bitStream>>8);
247 out += 2;
248 bitStream >>= 16;
249 bitCount -= 16;
250 } }
251 { int count = normalizedCounter[symbol++];
252 int const max = (2*threshold-1) - remaining;
253 remaining -= count < 0 ? -count : count;
254 count++; /* +1 for extra accuracy */
255 if (count>=threshold)
256 count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */
257 bitStream += count << bitCount;
258 bitCount += nbBits;
259 bitCount -= (count<max);
260 previousIs0 = (count==1);
261 if (remaining<1) return ERROR(GENERIC);
262 while (remaining<threshold) { nbBits--; threshold>>=1; }
263 }
264 if (bitCount>16) {
265 if ((!writeIsSafe) && (out > oend - 2))
266 return ERROR(dstSize_tooSmall); /* Buffer overflow */
267 out[0] = (BYTE)bitStream;
268 out[1] = (BYTE)(bitStream>>8);
269 out += 2;
270 bitStream >>= 16;
271 bitCount -= 16;
272 } }
273
274 if (remaining != 1)
275 return ERROR(GENERIC); /* incorrect normalized distribution */
276 assert(symbol <= alphabetSize);
277
278 /* flush remaining bitStream */
279 if ((!writeIsSafe) && (out > oend - 2))
280 return ERROR(dstSize_tooSmall); /* Buffer overflow */
281 out[0] = (BYTE)bitStream;
282 out[1] = (BYTE)(bitStream>>8);
283 out+= (bitCount+7) /8;
284
285 return (out-ostart);
286 }
287
288
FSE_writeNCount(void * buffer,size_t bufferSize,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog)289 size_t FSE_writeNCount (void* buffer, size_t bufferSize,
290 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
291 {
292 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported */
293 if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */
294
295 if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
296 return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
297
298 return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */);
299 }
300
301
302 /*-**************************************************************
303 * FSE Compression Code
304 ****************************************************************/
305
FSE_createCTable(unsigned maxSymbolValue,unsigned tableLog)306 FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog)
307 {
308 size_t size __attribute__ ((unused));
309 if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
310 size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32);
311 return (FSE_CTable*)malloc(size);
312 }
313
FSE_freeCTable(FSE_CTable * ct)314 void FSE_freeCTable (FSE_CTable* ct) { free(ct); }
315
316 /* provides the minimum logSize to safely represent a distribution */
FSE_minTableLog(size_t srcSize,unsigned maxSymbolValue)317 static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
318 {
319 U32 minBitsSrc = BIT_highbit32((U32)(srcSize)) + 1;
320 U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
321 U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
322 assert(srcSize > 1); /* Not supported, RLE should be used instead */
323 return minBits;
324 }
325
FSE_optimalTableLog_internal(unsigned maxTableLog,size_t srcSize,unsigned maxSymbolValue,unsigned minus)326 unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
327 {
328 U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
329 U32 tableLog = maxTableLog;
330 U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
331 assert(srcSize > 1); /* Not supported, RLE should be used instead */
332 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
333 if (maxBitsSrc < tableLog) tableLog = maxBitsSrc; /* Accuracy can be reduced */
334 if (minBits > tableLog) tableLog = minBits; /* Need a minimum to safely represent all symbol values */
335 if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG;
336 if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG;
337 return tableLog;
338 }
339
FSE_optimalTableLog(unsigned maxTableLog,size_t srcSize,unsigned maxSymbolValue)340 unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
341 {
342 return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
343 }
344
345
346 /* Secondary normalization method.
347 To be used when primary method fails. */
348
FSE_normalizeM2(short * norm,U32 tableLog,const unsigned * count,size_t total,U32 maxSymbolValue)349 static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue)
350 {
351 short const NOT_YET_ASSIGNED = -2;
352 U32 s;
353 U32 distributed = 0;
354 U32 ToDistribute;
355
356 /* Init */
357 U32 const lowThreshold = (U32)(total >> tableLog);
358 U32 lowOne = (U32)((total * 3) >> (tableLog + 1));
359
360 for (s=0; s<=maxSymbolValue; s++) {
361 if (count[s] == 0) {
362 norm[s]=0;
363 continue;
364 }
365 if (count[s] <= lowThreshold) {
366 norm[s] = -1;
367 distributed++;
368 total -= count[s];
369 continue;
370 }
371 if (count[s] <= lowOne) {
372 norm[s] = 1;
373 distributed++;
374 total -= count[s];
375 continue;
376 }
377
378 norm[s]=NOT_YET_ASSIGNED;
379 }
380 ToDistribute = (1 << tableLog) - distributed;
381
382 if (ToDistribute == 0)
383 return 0;
384
385 if ((total / ToDistribute) > lowOne) {
386 /* risk of rounding to zero */
387 lowOne = (U32)((total * 3) / (ToDistribute * 2));
388 for (s=0; s<=maxSymbolValue; s++) {
389 if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) {
390 norm[s] = 1;
391 distributed++;
392 total -= count[s];
393 continue;
394 } }
395 ToDistribute = (1 << tableLog) - distributed;
396 }
397
398 if (distributed == maxSymbolValue+1) {
399 /* all values are pretty poor;
400 probably incompressible data (should have already been detected);
401 find max, then give all remaining points to max */
402 U32 maxV = 0, maxC = 0;
403 for (s=0; s<=maxSymbolValue; s++)
404 if (count[s] > maxC) { maxV=s; maxC=count[s]; }
405 norm[maxV] += (short)ToDistribute;
406 return 0;
407 }
408
409 if (total == 0) {
410 /* all of the symbols were low enough for the lowOne or lowThreshold */
411 for (s=0; ToDistribute > 0; s = (s+1)%(maxSymbolValue+1))
412 if (norm[s] > 0) { ToDistribute--; norm[s]++; }
413 return 0;
414 }
415
416 { U64 const vStepLog = 62 - tableLog;
417 U64 const mid = (1ULL << (vStepLog-1)) - 1;
418 U64 const rStep = ((((U64)1<<vStepLog) * ToDistribute) + mid) / total; /* scale on remaining */
419 U64 tmpTotal = mid;
420 for (s=0; s<=maxSymbolValue; s++) {
421 if (norm[s]==NOT_YET_ASSIGNED) {
422 U64 const end = tmpTotal + (count[s] * rStep);
423 U32 const sStart = (U32)(tmpTotal >> vStepLog);
424 U32 const sEnd = (U32)(end >> vStepLog);
425 U32 const weight = sEnd - sStart;
426 if (weight < 1)
427 return ERROR(GENERIC);
428 norm[s] = (short)weight;
429 tmpTotal = end;
430 } } }
431
432 return 0;
433 }
434
435
FSE_normalizeCount(short * normalizedCounter,unsigned tableLog,const unsigned * count,size_t total,unsigned maxSymbolValue)436 size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog,
437 const unsigned* count, size_t total,
438 unsigned maxSymbolValue)
439 {
440 /* Sanity checks */
441 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
442 if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported size */
443 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported size */
444 if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */
445
446 { static U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
447 U64 const scale = 62 - tableLog;
448 U64 const step = ((U64)1<<62) / total; /* <== here, one division ! */
449 U64 const vStep = 1ULL<<(scale-20);
450 int stillToDistribute = 1<<tableLog;
451 unsigned s;
452 unsigned largest=0;
453 short largestP=0;
454 U32 lowThreshold = (U32)(total >> tableLog);
455
456 for (s=0; s<=maxSymbolValue; s++) {
457 if (count[s] == total) return 0; /* rle special case */
458 if (count[s] == 0) { normalizedCounter[s]=0; continue; }
459 if (count[s] <= lowThreshold) {
460 normalizedCounter[s] = -1;
461 stillToDistribute--;
462 } else {
463 short proba = (short)((count[s]*step) >> scale);
464 if (proba<8) {
465 U64 restToBeat = vStep * rtbTable[proba];
466 proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat;
467 }
468 if (proba > largestP) { largestP=proba; largest=s; }
469 normalizedCounter[s] = proba;
470 stillToDistribute -= proba;
471 } }
472 if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
473 /* corner case, need another normalization method */
474 size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue);
475 if (FSE_isError(errorCode)) return errorCode;
476 }
477 else normalizedCounter[largest] += (short)stillToDistribute;
478 }
479
480 #if 0
481 { /* Print Table (debug) */
482 U32 s;
483 U32 nTotal = 0;
484 for (s=0; s<=maxSymbolValue; s++)
485 RAWLOG(2, "%3i: %4i \n", s, normalizedCounter[s]);
486 for (s=0; s<=maxSymbolValue; s++)
487 nTotal += abs(normalizedCounter[s]);
488 if (nTotal != (1U<<tableLog))
489 RAWLOG(2, "Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog);
490 getchar();
491 }
492 #endif
493
494 return tableLog;
495 }
496
497
498 /* fake FSE_CTable, for raw (uncompressed) input */
FSE_buildCTable_raw(FSE_CTable * ct,unsigned nbBits)499 size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits)
500 {
501 const unsigned tableSize = 1 << nbBits;
502 const unsigned tableMask = tableSize - 1;
503 const unsigned maxSymbolValue = tableMask;
504 void* const ptr = ct;
505 U16* const tableU16 = ( (U16*) ptr) + 2;
506 void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableSize>>1); /* assumption : tableLog >= 1 */
507 FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
508 unsigned s;
509
510 /* Sanity checks */
511 if (nbBits < 1) return ERROR(GENERIC); /* min size */
512
513 /* header */
514 tableU16[-2] = (U16) nbBits;
515 tableU16[-1] = (U16) maxSymbolValue;
516
517 /* Build table */
518 for (s=0; s<tableSize; s++)
519 tableU16[s] = (U16)(tableSize + s);
520
521 /* Build Symbol Transformation Table */
522 { const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits);
523 for (s=0; s<=maxSymbolValue; s++) {
524 symbolTT[s].deltaNbBits = deltaNbBits;
525 symbolTT[s].deltaFindState = s-1;
526 } }
527
528 return 0;
529 }
530
531 /* fake FSE_CTable, for rle input (always same symbol) */
FSE_buildCTable_rle(FSE_CTable * ct,BYTE symbolValue)532 size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue)
533 {
534 void* ptr = ct;
535 U16* tableU16 = ( (U16*) ptr) + 2;
536 void* FSCTptr = (U32*)ptr + 2;
537 FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr;
538
539 /* header */
540 tableU16[-2] = (U16) 0;
541 tableU16[-1] = (U16) symbolValue;
542
543 /* Build table */
544 tableU16[0] = 0;
545 tableU16[1] = 0; /* just in case */
546
547 /* Build Symbol Transformation Table */
548 symbolTT[symbolValue].deltaNbBits = 0;
549 symbolTT[symbolValue].deltaFindState = 0;
550
551 return 0;
552 }
553
554
FSE_compress_usingCTable_generic(void * dst,size_t dstSize,const void * src,size_t srcSize,const FSE_CTable * ct,const unsigned fast)555 static size_t FSE_compress_usingCTable_generic (void* dst, size_t dstSize,
556 const void* src, size_t srcSize,
557 const FSE_CTable* ct, const unsigned fast)
558 {
559 const BYTE* const istart = (const BYTE*) src;
560 const BYTE* const iend = istart + srcSize;
561 const BYTE* ip=iend;
562
563 BIT_CStream_t bitC;
564 FSE_CState_t CState1, CState2;
565
566 /* init */
567 if (srcSize <= 2) return 0;
568 { size_t const initError = BIT_initCStream(&bitC, dst, dstSize);
569 if (FSE_isError(initError)) return 0; /* not enough space available to write a bitstream */ }
570
571 #define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
572
573 if (srcSize & 1) {
574 FSE_initCState2(&CState1, ct, *--ip);
575 FSE_initCState2(&CState2, ct, *--ip);
576 FSE_encodeSymbol(&bitC, &CState1, *--ip);
577 FSE_FLUSHBITS(&bitC);
578 } else {
579 FSE_initCState2(&CState2, ct, *--ip);
580 FSE_initCState2(&CState1, ct, *--ip);
581 }
582
583 /* join to mod 4 */
584 srcSize -= 2;
585 if ((sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) && (srcSize & 2)) { /* test bit 2 */
586 FSE_encodeSymbol(&bitC, &CState2, *--ip);
587 FSE_encodeSymbol(&bitC, &CState1, *--ip);
588 FSE_FLUSHBITS(&bitC);
589 }
590
591 /* 2 or 4 encoding per loop */
592 while ( ip>istart ) {
593
594 FSE_encodeSymbol(&bitC, &CState2, *--ip);
595
596 if (sizeof(bitC.bitContainer)*8 < FSE_MAX_TABLELOG*2+7 ) /* this test must be static */
597 FSE_FLUSHBITS(&bitC);
598
599 FSE_encodeSymbol(&bitC, &CState1, *--ip);
600
601 if (sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) { /* this test must be static */
602 FSE_encodeSymbol(&bitC, &CState2, *--ip);
603 FSE_encodeSymbol(&bitC, &CState1, *--ip);
604 }
605
606 FSE_FLUSHBITS(&bitC);
607 }
608
609 FSE_flushCState(&bitC, &CState2);
610 FSE_flushCState(&bitC, &CState1);
611 return BIT_closeCStream(&bitC);
612 }
613
FSE_compress_usingCTable(void * dst,size_t dstSize,const void * src,size_t srcSize,const FSE_CTable * ct)614 size_t FSE_compress_usingCTable (void* dst, size_t dstSize,
615 const void* src, size_t srcSize,
616 const FSE_CTable* ct)
617 {
618 unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
619
620 if (fast)
621 return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1);
622 else
623 return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0);
624 }
625
626
FSE_compressBound(size_t size)627 size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); }
628
629 /* FSE_compress_wksp() :
630 * Same as FSE_compress2(), but using an externally allocated scratch buffer (`workSpace`).
631 * `wkspSize` size must be `(1<<tableLog)`.
632 */
FSE_compress_wksp(void * dst,size_t dstSize,const void * src,size_t srcSize,unsigned maxSymbolValue,unsigned tableLog,void * workSpace,size_t wkspSize)633 size_t FSE_compress_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize)
634 {
635 BYTE* const ostart = (BYTE*) dst;
636 BYTE* op = ostart;
637 BYTE* const oend = ostart + dstSize;
638
639 unsigned count[FSE_MAX_SYMBOL_VALUE+1];
640 S16 norm[FSE_MAX_SYMBOL_VALUE+1];
641 FSE_CTable* CTable = (FSE_CTable*)workSpace;
642 size_t const CTableSize = FSE_CTABLE_SIZE_U32(tableLog, maxSymbolValue);
643 void* scratchBuffer = (void*)(CTable + CTableSize);
644 size_t const scratchBufferSize = wkspSize - (CTableSize * sizeof(FSE_CTable));
645
646 /* init conditions */
647 if (wkspSize < FSE_WKSP_SIZE_U32(tableLog, maxSymbolValue)) return ERROR(tableLog_tooLarge);
648 if (srcSize <= 1) return 0; /* Not compressible */
649 if (!maxSymbolValue) maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
650 if (!tableLog) tableLog = FSE_DEFAULT_TABLELOG;
651
652 /* Scan input and build symbol stats */
653 { CHECK_V_F(maxCount, HIST_count_wksp(count, &maxSymbolValue, src, srcSize, scratchBuffer, scratchBufferSize) );
654 if (maxCount == srcSize) return 1; /* only a single symbol in src : rle */
655 if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */
656 if (maxCount < (srcSize >> 7)) return 0; /* Heuristic : not compressible enough */
657 }
658
659 tableLog = FSE_optimalTableLog(tableLog, srcSize, maxSymbolValue);
660 CHECK_F( FSE_normalizeCount(norm, tableLog, count, srcSize, maxSymbolValue) );
661
662 /* Write table description header */
663 { CHECK_V_F(nc_err, FSE_writeNCount(op, oend-op, norm, maxSymbolValue, tableLog) );
664 op += nc_err;
665 }
666
667 /* Compress */
668 CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, scratchBufferSize) );
669 { CHECK_V_F(cSize, FSE_compress_usingCTable(op, oend - op, src, srcSize, CTable) );
670 if (cSize == 0) return 0; /* not enough space for compressed data */
671 op += cSize;
672 }
673
674 /* check compressibility */
675 if ( (size_t)(op-ostart) >= srcSize-1 ) return 0;
676
677 return op-ostart;
678 }
679
680 typedef struct {
681 FSE_CTable CTable_max[FSE_CTABLE_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)];
682 BYTE scratchBuffer[1 << FSE_MAX_TABLELOG];
683 } fseWkspMax_t;
684
FSE_compress2(void * dst,size_t dstCapacity,const void * src,size_t srcSize,unsigned maxSymbolValue,unsigned tableLog)685 size_t FSE_compress2 (void* dst, size_t dstCapacity, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
686 {
687 fseWkspMax_t scratchBuffer;
688 DEBUG_STATIC_ASSERT(sizeof(scratchBuffer) >= FSE_WKSP_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)); /* compilation failures here means scratchBuffer is not large enough */
689 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
690 return FSE_compress_wksp(dst, dstCapacity, src, srcSize, maxSymbolValue, tableLog, &scratchBuffer, sizeof(scratchBuffer));
691 }
692
FSE_compress(void * dst,size_t dstCapacity,const void * src,size_t srcSize)693 size_t FSE_compress (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
694 {
695 return FSE_compress2(dst, dstCapacity, src, srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG);
696 }
697
698
699 #endif /* FSE_COMMONDEFS_ONLY */
700