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