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