projects/linux·blob master · refs

626 lines · 23.6 KiB

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