Project Alice
Loading...
Searching...
No Matches
fse_compress.c
Go to the documentation of this file.
1/* ******************************************************************
2 * FSE : Finite State Entropy encoder
3 * Copyright (c) Meta Platforms, Inc. and affiliates.
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_memset */
29#include "../common/bits.h" /* ZSTD_highbit32 */
30
31
32/* **************************************************************
33* Error Management
34****************************************************************/
35#define FSE_isError ERR_isError
36
37
38/* **************************************************************
39* Templates
40****************************************************************/
41/*
42 designed to be included
43 for type-specific functions (template emulation in C)
44 Objective is to write these functions only once, for improved maintenance
45*/
46
47/* safety checks */
48#ifndef FSE_FUNCTION_EXTENSION
49# error "FSE_FUNCTION_EXTENSION must be defined"
50#endif
51#ifndef FSE_FUNCTION_TYPE
52# error "FSE_FUNCTION_TYPE must be defined"
53#endif
54
55/* Function names */
56#define FSE_CAT(X,Y) X##Y
57#define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
58#define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
59
60
61/* Function templates */
62
63/* FSE_buildCTable_wksp() :
64 * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`).
65 * wkspSize should be sized to handle worst case situation, which is `1<<max_tableLog * sizeof(FSE_FUNCTION_TYPE)`
66 * workSpace must also be properly aligned with FSE_FUNCTION_TYPE requirements
67 */
69 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
70 void* workSpace, size_t wkspSize)
71{
72 U32 const tableSize = 1 << tableLog;
73 U32 const tableMask = tableSize - 1;
74 void* const ptr = ct;
75 U16* const tableU16 = ( (U16*) ptr) + 2;
76 void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableLog ? tableSize>>1 : 1) ;
77 FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
78 U32 const step = FSE_TABLESTEP(tableSize);
79 U32 const maxSV1 = maxSymbolValue+1;
80
81 U16* cumul = (U16*)workSpace; /* size = maxSV1 */
82 FSE_FUNCTION_TYPE* const tableSymbol = (FSE_FUNCTION_TYPE*)(cumul + (maxSV1+1)); /* size = tableSize */
83
84 U32 highThreshold = tableSize-1;
85
86 assert(((size_t)workSpace & 1) == 0); /* Must be 2 bytes-aligned */
87 if (FSE_BUILD_CTABLE_WORKSPACE_SIZE(maxSymbolValue, tableLog) > wkspSize) return ERROR(tableLog_tooLarge);
88 /* CTable header */
89 tableU16[-2] = (U16) tableLog;
90 tableU16[-1] = (U16) maxSymbolValue;
91 assert(tableLog < 16); /* required for threshold strategy to work */
92
93 /* For explanations on how to distribute symbol values over the table :
94 * https://fastcompression.blogspot.fr/2014/02/fse-distributing-symbol-values.html */
95
96 #ifdef __clang_analyzer__
97 ZSTD_memset(tableSymbol, 0, sizeof(*tableSymbol) * tableSize); /* useless initialization, just to keep scan-build happy */
98 #endif
99
100 /* symbol start positions */
101 { U32 u;
102 cumul[0] = 0;
103 for (u=1; u <= maxSV1; u++) {
104 if (normalizedCounter[u-1]==-1) { /* Low proba symbol */
105 cumul[u] = cumul[u-1] + 1;
106 tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(u-1);
107 } else {
108 assert(normalizedCounter[u-1] >= 0);
109 cumul[u] = cumul[u-1] + (U16)normalizedCounter[u-1];
110 assert(cumul[u] >= cumul[u-1]); /* no overflow */
111 } }
112 cumul[maxSV1] = (U16)(tableSize+1);
113 }
114
115 /* Spread symbols */
116 if (highThreshold == tableSize - 1) {
117 /* Case for no low prob count symbols. Lay down 8 bytes at a time
118 * to reduce branch misses since we are operating on a small block
119 */
120 BYTE* const spread = tableSymbol + tableSize; /* size = tableSize + 8 (may write beyond tableSize) */
121 { U64 const add = 0x0101010101010101ull;
122 size_t pos = 0;
123 U64 sv = 0;
124 U32 s;
125 for (s=0; s<maxSV1; ++s, sv += add) {
126 int i;
127 int const n = normalizedCounter[s];
128 MEM_write64(spread + pos, sv);
129 for (i = 8; i < n; i += 8) {
130 MEM_write64(spread + pos + i, sv);
131 }
132 assert(n>=0);
133 pos += (size_t)n;
134 }
135 }
136 /* Spread symbols across the table. Lack of lowprob symbols means that
137 * we don't need variable sized inner loop, so we can unroll the loop and
138 * reduce branch misses.
139 */
140 { size_t position = 0;
141 size_t s;
142 size_t const unroll = 2; /* Experimentally determined optimal unroll */
143 assert(tableSize % unroll == 0); /* FSE_MIN_TABLELOG is 5 */
144 for (s = 0; s < (size_t)tableSize; s += unroll) {
145 size_t u;
146 for (u = 0; u < unroll; ++u) {
147 size_t const uPosition = (position + (u * step)) & tableMask;
148 tableSymbol[uPosition] = spread[s + u];
149 }
150 position = (position + (unroll * step)) & tableMask;
151 }
152 assert(position == 0); /* Must have initialized all positions */
153 }
154 } else {
155 U32 position = 0;
156 U32 symbol;
157 for (symbol=0; symbol<maxSV1; symbol++) {
158 int nbOccurrences;
159 int const freq = normalizedCounter[symbol];
160 for (nbOccurrences=0; nbOccurrences<freq; nbOccurrences++) {
161 tableSymbol[position] = (FSE_FUNCTION_TYPE)symbol;
162 position = (position + step) & tableMask;
163 while (position > highThreshold)
164 position = (position + step) & tableMask; /* Low proba area */
165 } }
166 assert(position==0); /* Must have initialized all positions */
167 }
168
169 /* Build table */
170 { U32 u; for (u=0; u<tableSize; u++) {
171 FSE_FUNCTION_TYPE s = tableSymbol[u]; /* note : static analyzer may not understand tableSymbol is properly initialized */
172 tableU16[cumul[s]++] = (U16) (tableSize+u); /* TableU16 : sorted by symbol order; gives next state value */
173 } }
174
175 /* Build Symbol Transformation Table */
176 { unsigned total = 0;
177 unsigned s;
178 for (s=0; s<=maxSymbolValue; s++) {
179 switch (normalizedCounter[s])
180 {
181 case 0:
182 /* filling nonetheless, for compatibility with FSE_getMaxNbBits() */
183 symbolTT[s].deltaNbBits = ((tableLog+1) << 16) - (1<<tableLog);
184 break;
185
186 case -1:
187 case 1:
188 symbolTT[s].deltaNbBits = (tableLog << 16) - (1<<tableLog);
189 assert(total <= INT_MAX);
190 symbolTT[s].deltaFindState = (int)(total - 1);
191 total ++;
192 break;
193 default :
194 assert(normalizedCounter[s] > 1);
195 { U32 const maxBitsOut = tableLog - ZSTD_highbit32 ((U32)normalizedCounter[s]-1);
196 U32 const minStatePlus = (U32)normalizedCounter[s] << maxBitsOut;
197 symbolTT[s].deltaNbBits = (maxBitsOut << 16) - minStatePlus;
198 symbolTT[s].deltaFindState = (int)(total - (unsigned)normalizedCounter[s]);
199 total += (unsigned)normalizedCounter[s];
200 } } } }
201
202#if 0 /* debug : symbol costs */
203 DEBUGLOG(5, "\n --- table statistics : ");
204 { U32 symbol;
205 for (symbol=0; symbol<=maxSymbolValue; symbol++) {
206 DEBUGLOG(5, "%3u: w=%3i, maxBits=%u, fracBits=%.2f",
207 symbol, normalizedCounter[symbol],
208 FSE_getMaxNbBits(symbolTT, symbol),
209 (double)FSE_bitCost(symbolTT, tableLog, symbol, 8) / 256);
210 } }
211#endif
212
213 return 0;
214}
215
216
217
218#ifndef FSE_COMMONDEFS_ONLY
219
220/*-**************************************************************
221* FSE NCount encoding
222****************************************************************/
223size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
224{
225 size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog
226 + 4 /* bitCount initialized at 4 */
227 + 2 /* first two symbols may use one additional bit each */) / 8)
228 + 1 /* round up to whole nb bytes */
229 + 2 /* additional two bytes for bitstream flush */;
230 return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */
231}
232
233static size_t
234FSE_writeNCount_generic (void* header, size_t headerBufferSize,
235 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
236 unsigned writeIsSafe)
237{
238 BYTE* const ostart = (BYTE*) header;
239 BYTE* out = ostart;
240 BYTE* const oend = ostart + headerBufferSize;
241 int nbBits;
242 const int tableSize = 1 << tableLog;
243 int remaining;
244 int threshold;
245 U32 bitStream = 0;
246 int bitCount = 0;
247 unsigned symbol = 0;
248 unsigned const alphabetSize = maxSymbolValue + 1;
249 int previousIs0 = 0;
250
251 /* Table Size */
252 bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount;
253 bitCount += 4;
254
255 /* Init */
256 remaining = tableSize+1; /* +1 for extra accuracy */
257 threshold = tableSize;
258 nbBits = (int)tableLog+1;
259
260 while ((symbol < alphabetSize) && (remaining>1)) { /* stops at 1 */
261 if (previousIs0) {
262 unsigned start = symbol;
263 while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++;
264 if (symbol == alphabetSize) break; /* incorrect distribution */
265 while (symbol >= start+24) {
266 start+=24;
267 bitStream += 0xFFFFU << bitCount;
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 }
275 while (symbol >= start+3) {
276 start+=3;
277 bitStream += 3U << bitCount;
278 bitCount += 2;
279 }
280 bitStream += (symbol-start) << bitCount;
281 bitCount += 2;
282 if (bitCount>16) {
283 if ((!writeIsSafe) && (out > oend - 2))
284 return ERROR(dstSize_tooSmall); /* Buffer overflow */
285 out[0] = (BYTE)bitStream;
286 out[1] = (BYTE)(bitStream>>8);
287 out += 2;
288 bitStream >>= 16;
289 bitCount -= 16;
290 } }
291 { int count = normalizedCounter[symbol++];
292 int const max = (2*threshold-1) - remaining;
293 remaining -= count < 0 ? -count : count;
294 count++; /* +1 for extra accuracy */
295 if (count>=threshold)
296 count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */
297 bitStream += (U32)count << bitCount;
298 bitCount += nbBits;
299 bitCount -= (count<max);
300 previousIs0 = (count==1);
301 if (remaining<1) return ERROR(GENERIC);
302 while (remaining<threshold) { nbBits--; threshold>>=1; }
303 }
304 if (bitCount>16) {
305 if ((!writeIsSafe) && (out > oend - 2))
306 return ERROR(dstSize_tooSmall); /* Buffer overflow */
307 out[0] = (BYTE)bitStream;
308 out[1] = (BYTE)(bitStream>>8);
309 out += 2;
310 bitStream >>= 16;
311 bitCount -= 16;
312 } }
313
314 if (remaining != 1)
315 return ERROR(GENERIC); /* incorrect normalized distribution */
316 assert(symbol <= alphabetSize);
317
318 /* flush remaining bitStream */
319 if ((!writeIsSafe) && (out > oend - 2))
320 return ERROR(dstSize_tooSmall); /* Buffer overflow */
321 out[0] = (BYTE)bitStream;
322 out[1] = (BYTE)(bitStream>>8);
323 out+= (bitCount+7) /8;
324
325 assert(out >= ostart);
326 return (size_t)(out-ostart);
327}
328
329
330size_t FSE_writeNCount (void* buffer, size_t bufferSize,
331 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
332{
333 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported */
334 if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */
335
336 if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
337 return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
338
339 return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */);
340}
341
342
343/*-**************************************************************
344* FSE Compression Code
345****************************************************************/
346
347/* provides the minimum logSize to safely represent a distribution */
348static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
349{
350 U32 minBitsSrc = ZSTD_highbit32((U32)(srcSize)) + 1;
351 U32 minBitsSymbols = ZSTD_highbit32(maxSymbolValue) + 2;
352 U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
353 assert(srcSize > 1); /* Not supported, RLE should be used instead */
354 return minBits;
355}
356
357unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
358{
359 U32 maxBitsSrc = ZSTD_highbit32((U32)(srcSize - 1)) - minus;
360 U32 tableLog = maxTableLog;
361 U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
362 assert(srcSize > 1); /* Not supported, RLE should be used instead */
363 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
364 if (maxBitsSrc < tableLog) tableLog = maxBitsSrc; /* Accuracy can be reduced */
365 if (minBits > tableLog) tableLog = minBits; /* Need a minimum to safely represent all symbol values */
366 if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG;
367 if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG;
368 return tableLog;
369}
370
371unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
372{
373 return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
374}
375
376/* Secondary normalization method.
377 To be used when primary method fails. */
378
379static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue, short lowProbCount)
380{
381 short const NOT_YET_ASSIGNED = -2;
382 U32 s;
383 U32 distributed = 0;
384 U32 ToDistribute;
385
386 /* Init */
387 U32 const lowThreshold = (U32)(total >> tableLog);
388 U32 lowOne = (U32)((total * 3) >> (tableLog + 1));
389
390 for (s=0; s<=maxSymbolValue; s++) {
391 if (count[s] == 0) {
392 norm[s]=0;
393 continue;
394 }
395 if (count[s] <= lowThreshold) {
396 norm[s] = lowProbCount;
397 distributed++;
398 total -= count[s];
399 continue;
400 }
401 if (count[s] <= lowOne) {
402 norm[s] = 1;
403 distributed++;
404 total -= count[s];
405 continue;
406 }
407
408 norm[s]=NOT_YET_ASSIGNED;
409 }
410 ToDistribute = (1 << tableLog) - distributed;
411
412 if (ToDistribute == 0)
413 return 0;
414
415 if ((total / ToDistribute) > lowOne) {
416 /* risk of rounding to zero */
417 lowOne = (U32)((total * 3) / (ToDistribute * 2));
418 for (s=0; s<=maxSymbolValue; s++) {
419 if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) {
420 norm[s] = 1;
421 distributed++;
422 total -= count[s];
423 continue;
424 } }
425 ToDistribute = (1 << tableLog) - distributed;
426 }
427
428 if (distributed == maxSymbolValue+1) {
429 /* all values are pretty poor;
430 probably incompressible data (should have already been detected);
431 find max, then give all remaining points to max */
432 U32 maxV = 0, maxC = 0;
433 for (s=0; s<=maxSymbolValue; s++)
434 if (count[s] > maxC) { maxV=s; maxC=count[s]; }
435 norm[maxV] += (short)ToDistribute;
436 return 0;
437 }
438
439 if (total == 0) {
440 /* all of the symbols were low enough for the lowOne or lowThreshold */
441 for (s=0; ToDistribute > 0; s = (s+1)%(maxSymbolValue+1))
442 if (norm[s] > 0) { ToDistribute--; norm[s]++; }
443 return 0;
444 }
445
446 { U64 const vStepLog = 62 - tableLog;
447 U64 const mid = (1ULL << (vStepLog-1)) - 1;
448 U64 const rStep = ZSTD_div64((((U64)1<<vStepLog) * ToDistribute) + mid, (U32)total); /* scale on remaining */
449 U64 tmpTotal = mid;
450 for (s=0; s<=maxSymbolValue; s++) {
451 if (norm[s]==NOT_YET_ASSIGNED) {
452 U64 const end = tmpTotal + (count[s] * rStep);
453 U32 const sStart = (U32)(tmpTotal >> vStepLog);
454 U32 const sEnd = (U32)(end >> vStepLog);
455 U32 const weight = sEnd - sStart;
456 if (weight < 1)
457 return ERROR(GENERIC);
458 norm[s] = (short)weight;
459 tmpTotal = end;
460 } } }
461
462 return 0;
463}
464
465size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog,
466 const unsigned* count, size_t total,
467 unsigned maxSymbolValue, unsigned useLowProbCount)
468{
469 /* Sanity checks */
470 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
471 if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported size */
472 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported size */
473 if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */
474
475 { static U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
476 short const lowProbCount = useLowProbCount ? -1 : 1;
477 U64 const scale = 62 - tableLog;
478 U64 const step = ZSTD_div64((U64)1<<62, (U32)total); /* <== here, one division ! */
479 U64 const vStep = 1ULL<<(scale-20);
480 int stillToDistribute = 1<<tableLog;
481 unsigned s;
482 unsigned largest=0;
483 short largestP=0;
484 U32 lowThreshold = (U32)(total >> tableLog);
485
486 for (s=0; s<=maxSymbolValue; s++) {
487 if (count[s] == total) return 0; /* rle special case */
488 if (count[s] == 0) { normalizedCounter[s]=0; continue; }
489 if (count[s] <= lowThreshold) {
490 normalizedCounter[s] = lowProbCount;
491 stillToDistribute--;
492 } else {
493 short proba = (short)((count[s]*step) >> scale);
494 if (proba<8) {
495 U64 restToBeat = vStep * rtbTable[proba];
496 proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat;
497 }
498 if (proba > largestP) { largestP=proba; largest=s; }
499 normalizedCounter[s] = proba;
500 stillToDistribute -= proba;
501 } }
502 if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
503 /* corner case, need another normalization method */
504 size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue, lowProbCount);
505 if (FSE_isError(errorCode)) return errorCode;
506 }
507 else normalizedCounter[largest] += (short)stillToDistribute;
508 }
509
510#if 0
511 { /* Print Table (debug) */
512 U32 s;
513 U32 nTotal = 0;
514 for (s=0; s<=maxSymbolValue; s++)
515 RAWLOG(2, "%3i: %4i \n", s, normalizedCounter[s]);
516 for (s=0; s<=maxSymbolValue; s++)
517 nTotal += abs(normalizedCounter[s]);
518 if (nTotal != (1U<<tableLog))
519 RAWLOG(2, "Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog);
520 getchar();
521 }
522#endif
523
524 return tableLog;
525}
526
527/* fake FSE_CTable, for rle input (always same symbol) */
528size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue)
529{
530 void* ptr = ct;
531 U16* tableU16 = ( (U16*) ptr) + 2;
532 void* FSCTptr = (U32*)ptr + 2;
533 FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr;
534
535 /* header */
536 tableU16[-2] = (U16) 0;
537 tableU16[-1] = (U16) symbolValue;
538
539 /* Build table */
540 tableU16[0] = 0;
541 tableU16[1] = 0; /* just in case */
542
543 /* Build Symbol Transformation Table */
544 symbolTT[symbolValue].deltaNbBits = 0;
545 symbolTT[symbolValue].deltaFindState = 0;
546
547 return 0;
548}
549
550
551static size_t FSE_compress_usingCTable_generic (void* dst, size_t dstSize,
552 const void* src, size_t srcSize,
553 const FSE_CTable* ct, const unsigned fast)
554{
555 const BYTE* const istart = (const BYTE*) src;
556 const BYTE* const iend = istart + srcSize;
557 const BYTE* ip=iend;
558
559 BIT_CStream_t bitC;
560 FSE_CState_t CState1, CState2;
561
562 /* init */
563 if (srcSize <= 2) return 0;
564 { size_t const initError = BIT_initCStream(&bitC, dst, dstSize);
565 if (FSE_isError(initError)) return 0; /* not enough space available to write a bitstream */ }
566
567#define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
568
569 if (srcSize & 1) {
570 FSE_initCState2(&CState1, ct, *--ip);
571 FSE_initCState2(&CState2, ct, *--ip);
572 FSE_encodeSymbol(&bitC, &CState1, *--ip);
573 FSE_FLUSHBITS(&bitC);
574 } else {
575 FSE_initCState2(&CState2, ct, *--ip);
576 FSE_initCState2(&CState1, ct, *--ip);
577 }
578
579 /* join to mod 4 */
580 srcSize -= 2;
581 if ((sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) && (srcSize & 2)) { /* test bit 2 */
582 FSE_encodeSymbol(&bitC, &CState2, *--ip);
583 FSE_encodeSymbol(&bitC, &CState1, *--ip);
584 FSE_FLUSHBITS(&bitC);
585 }
586
587 /* 2 or 4 encoding per loop */
588 while ( ip>istart ) {
589
590 FSE_encodeSymbol(&bitC, &CState2, *--ip);
591
592 if (sizeof(bitC.bitContainer)*8 < FSE_MAX_TABLELOG*2+7 ) /* this test must be static */
593 FSE_FLUSHBITS(&bitC);
594
595 FSE_encodeSymbol(&bitC, &CState1, *--ip);
596
597 if (sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) { /* this test must be static */
598 FSE_encodeSymbol(&bitC, &CState2, *--ip);
599 FSE_encodeSymbol(&bitC, &CState1, *--ip);
600 }
601
602 FSE_FLUSHBITS(&bitC);
603 }
604
605 FSE_flushCState(&bitC, &CState2);
606 FSE_flushCState(&bitC, &CState1);
607 return BIT_closeCStream(&bitC);
608}
609
610size_t FSE_compress_usingCTable (void* dst, size_t dstSize,
611 const void* src, size_t srcSize,
612 const FSE_CTable* ct)
613{
614 unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
615
616 if (fast)
617 return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1);
618 else
619 return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0);
620}
621
622
623size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); }
624
625#endif /* FSE_COMMONDEFS_ONLY */
MEM_STATIC unsigned ZSTD_highbit32(U32 val)
Definition: bits.h:169
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
Definition: bitstream.h:235
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity)
Definition: bitstream.h:154
#define DEBUGLOG(l,...)
Definition: debug.h:108
#define RAWLOG(l,...)
Definition: debug.h:107
#define assert(condition)
Definition: debug.h:74
#define ERROR(name)
Definition: error_private.h:55
unsigned FSE_CTable
Definition: fse.h:124
size_t FSE_compressBound(size_t size)
Definition: fse_compress.c:623
size_t FSE_buildCTable_wksp(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
Definition: fse_compress.c:68
size_t FSE_compress_usingCTable(void *dst, size_t dstSize, const void *src, size_t srcSize, const FSE_CTable *ct)
Definition: fse_compress.c:610
size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:223
unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
Definition: fse_compress.c:357
size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t total, unsigned maxSymbolValue, unsigned useLowProbCount)
Definition: fse_compress.c:465
#define FSE_isError
Definition: fse_compress.c:35
size_t FSE_buildCTable_rle(FSE_CTable *ct, BYTE symbolValue)
Definition: fse_compress.c:528
#define FSE_FLUSHBITS(s)
unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:371
size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:330
MEM_STATIC void MEM_write64(void *memPtr, U64 value)
Definition: mem.h:227
unsigned long long U64
Definition: mem.h:73
unsigned char BYTE
Definition: mem.h:58
unsigned int U32
Definition: mem.h:69
unsigned short U16
Definition: mem.h:64
constexpr dcon::demographics_key total(0)
MOD_PROV_LIST constexpr uint32_t count
Definition: modifiers.hpp:207
size_t bitContainer
Definition: bitstream.h:60
#define ZSTD_memset(p, v, l)
Definition: zstd_deps.h:38