1 /* ******************************************************************
2  * FSE : Finite State Entropy encoder
3  * Copyright (c) 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 
175 
176 
177 #ifndef FSE_COMMONDEFS_ONLY
178 
179 
180 /*-**************************************************************
181 *  FSE NCount encoding
182 ****************************************************************/
FSE_NCountWriteBound(unsigned maxSymbolValue,unsigned tableLog)183 size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
184 {
185     size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3;
186     return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND;  /* maxSymbolValue==0 ? use default */
187 }
188 
189 static size_t
FSE_writeNCount_generic(void * header,size_t headerBufferSize,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog,unsigned writeIsSafe)190 FSE_writeNCount_generic (void* header, size_t headerBufferSize,
191                    const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
192                          unsigned writeIsSafe)
193 {
194     BYTE* const ostart = (BYTE*) header;
195     BYTE* out = ostart;
196     BYTE* const oend = ostart + headerBufferSize;
197     int nbBits;
198     const int tableSize = 1 << tableLog;
199     int remaining;
200     int threshold;
201     U32 bitStream = 0;
202     int bitCount = 0;
203     unsigned symbol = 0;
204     unsigned const alphabetSize = maxSymbolValue + 1;
205     int previousIs0 = 0;
206 
207     /* Table Size */
208     bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount;
209     bitCount  += 4;
210 
211     /* Init */
212     remaining = tableSize+1;   /* +1 for extra accuracy */
213     threshold = tableSize;
214     nbBits = tableLog+1;
215 
216     while ((symbol < alphabetSize) && (remaining>1)) {  /* stops at 1 */
217         if (previousIs0) {
218             unsigned start = symbol;
219             while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++;
220             if (symbol == alphabetSize) break;   /* incorrect distribution */
221             while (symbol >= start+24) {
222                 start+=24;
223                 bitStream += 0xFFFFU << bitCount;
224                 if ((!writeIsSafe) && (out > oend-2))
225                     return ERROR(dstSize_tooSmall);   /* Buffer overflow */
226                 out[0] = (BYTE) bitStream;
227                 out[1] = (BYTE)(bitStream>>8);
228                 out+=2;
229                 bitStream>>=16;
230             }
231             while (symbol >= start+3) {
232                 start+=3;
233                 bitStream += 3 << bitCount;
234                 bitCount += 2;
235             }
236             bitStream += (symbol-start) << bitCount;
237             bitCount += 2;
238             if (bitCount>16) {
239                 if ((!writeIsSafe) && (out > oend - 2))
240                     return ERROR(dstSize_tooSmall);   /* Buffer overflow */
241                 out[0] = (BYTE)bitStream;
242                 out[1] = (BYTE)(bitStream>>8);
243                 out += 2;
244                 bitStream >>= 16;
245                 bitCount -= 16;
246         }   }
247         {   int count = normalizedCounter[symbol++];
248             int const max = (2*threshold-1) - remaining;
249             remaining -= count < 0 ? -count : count;
250             count++;   /* +1 for extra accuracy */
251             if (count>=threshold)
252                 count += max;   /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */
253             bitStream += count << bitCount;
254             bitCount  += nbBits;
255             bitCount  -= (count<max);
256             previousIs0  = (count==1);
257             if (remaining<1) return ERROR(GENERIC);
258             while (remaining<threshold) { nbBits--; threshold>>=1; }
259         }
260         if (bitCount>16) {
261             if ((!writeIsSafe) && (out > oend - 2))
262                 return ERROR(dstSize_tooSmall);   /* Buffer overflow */
263             out[0] = (BYTE)bitStream;
264             out[1] = (BYTE)(bitStream>>8);
265             out += 2;
266             bitStream >>= 16;
267             bitCount -= 16;
268     }   }
269 
270     if (remaining != 1)
271         return ERROR(GENERIC);  /* incorrect normalized distribution */
272     assert(symbol <= alphabetSize);
273 
274     /* flush remaining bitStream */
275     if ((!writeIsSafe) && (out > oend - 2))
276         return ERROR(dstSize_tooSmall);   /* Buffer overflow */
277     out[0] = (BYTE)bitStream;
278     out[1] = (BYTE)(bitStream>>8);
279     out+= (bitCount+7) /8;
280 
281     return (out-ostart);
282 }
283 
284 
FSE_writeNCount(void * buffer,size_t bufferSize,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog)285 size_t FSE_writeNCount (void* buffer, size_t bufferSize,
286                   const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
287 {
288     if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);   /* Unsupported */
289     if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC);   /* Unsupported */
290 
291     if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
292         return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
293 
294     return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */);
295 }
296 
297 
298 /*-**************************************************************
299 *  FSE Compression Code
300 ****************************************************************/
301 
FSE_createCTable(unsigned maxSymbolValue,unsigned tableLog)302 FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog)
303 {
304     size_t size;
305     if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
306     size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32);
307     return (FSE_CTable*)ZSTD_malloc(size);
308 }
309 
FSE_freeCTable(FSE_CTable * ct)310 void FSE_freeCTable (FSE_CTable* ct) { ZSTD_free(ct); }
311 
312 /* provides the minimum logSize to safely represent a distribution */
FSE_minTableLog(size_t srcSize,unsigned maxSymbolValue)313 static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
314 {
315     U32 minBitsSrc = BIT_highbit32((U32)(srcSize)) + 1;
316     U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
317     U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
318     assert(srcSize > 1); /* Not supported, RLE should be used instead */
319     return minBits;
320 }
321 
FSE_optimalTableLog_internal(unsigned maxTableLog,size_t srcSize,unsigned maxSymbolValue,unsigned minus)322 unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
323 {
324     U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
325     U32 tableLog = maxTableLog;
326     U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
327     assert(srcSize > 1); /* Not supported, RLE should be used instead */
328     if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
329     if (maxBitsSrc < tableLog) tableLog = maxBitsSrc;   /* Accuracy can be reduced */
330     if (minBits > tableLog) tableLog = minBits;   /* Need a minimum to safely represent all symbol values */
331     if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG;
332     if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG;
333     return tableLog;
334 }
335 
FSE_optimalTableLog(unsigned maxTableLog,size_t srcSize,unsigned maxSymbolValue)336 unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
337 {
338     return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
339 }
340 
341 /* Secondary normalization method.
342    To be used when primary method fails. */
343 
FSE_normalizeM2(short * norm,U32 tableLog,const unsigned * count,size_t total,U32 maxSymbolValue,short lowProbCount)344 static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue, short lowProbCount)
345 {
346     short const NOT_YET_ASSIGNED = -2;
347     U32 s;
348     U32 distributed = 0;
349     U32 ToDistribute;
350 
351     /* Init */
352     U32 const lowThreshold = (U32)(total >> tableLog);
353     U32 lowOne = (U32)((total * 3) >> (tableLog + 1));
354 
355     for (s=0; s<=maxSymbolValue; s++) {
356         if (count[s] == 0) {
357             norm[s]=0;
358             continue;
359         }
360         if (count[s] <= lowThreshold) {
361             norm[s] = lowProbCount;
362             distributed++;
363             total -= count[s];
364             continue;
365         }
366         if (count[s] <= lowOne) {
367             norm[s] = 1;
368             distributed++;
369             total -= count[s];
370             continue;
371         }
372 
373         norm[s]=NOT_YET_ASSIGNED;
374     }
375     ToDistribute = (1 << tableLog) - distributed;
376 
377     if (ToDistribute == 0)
378         return 0;
379 
380     if ((total / ToDistribute) > lowOne) {
381         /* risk of rounding to zero */
382         lowOne = (U32)((total * 3) / (ToDistribute * 2));
383         for (s=0; s<=maxSymbolValue; s++) {
384             if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) {
385                 norm[s] = 1;
386                 distributed++;
387                 total -= count[s];
388                 continue;
389         }   }
390         ToDistribute = (1 << tableLog) - distributed;
391     }
392 
393     if (distributed == maxSymbolValue+1) {
394         /* all values are pretty poor;
395            probably incompressible data (should have already been detected);
396            find max, then give all remaining points to max */
397         U32 maxV = 0, maxC = 0;
398         for (s=0; s<=maxSymbolValue; s++)
399             if (count[s] > maxC) { maxV=s; maxC=count[s]; }
400         norm[maxV] += (short)ToDistribute;
401         return 0;
402     }
403 
404     if (total == 0) {
405         /* all of the symbols were low enough for the lowOne or lowThreshold */
406         for (s=0; ToDistribute > 0; s = (s+1)%(maxSymbolValue+1))
407             if (norm[s] > 0) { ToDistribute--; norm[s]++; }
408         return 0;
409     }
410 
411     {   U64 const vStepLog = 62 - tableLog;
412         U64 const mid = (1ULL << (vStepLog-1)) - 1;
413         U64 const rStep = ZSTD_div64((((U64)1<<vStepLog) * ToDistribute) + mid, (U32)total);   /* scale on remaining */
414         U64 tmpTotal = mid;
415         for (s=0; s<=maxSymbolValue; s++) {
416             if (norm[s]==NOT_YET_ASSIGNED) {
417                 U64 const end = tmpTotal + (count[s] * rStep);
418                 U32 const sStart = (U32)(tmpTotal >> vStepLog);
419                 U32 const sEnd = (U32)(end >> vStepLog);
420                 U32 const weight = sEnd - sStart;
421                 if (weight < 1)
422                     return ERROR(GENERIC);
423                 norm[s] = (short)weight;
424                 tmpTotal = end;
425     }   }   }
426 
427     return 0;
428 }
429 
FSE_normalizeCount(short * normalizedCounter,unsigned tableLog,const unsigned * count,size_t total,unsigned maxSymbolValue,unsigned useLowProbCount)430 size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog,
431                            const unsigned* count, size_t total,
432                            unsigned maxSymbolValue, unsigned useLowProbCount)
433 {
434     /* Sanity checks */
435     if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
436     if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC);   /* Unsupported size */
437     if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);   /* Unsupported size */
438     if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC);   /* Too small tableLog, compression potentially impossible */
439 
440     {   static U32 const rtbTable[] = {     0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
441         short const lowProbCount = useLowProbCount ? -1 : 1;
442         U64 const scale = 62 - tableLog;
443         U64 const step = ZSTD_div64((U64)1<<62, (U32)total);   /* <== here, one division ! */
444         U64 const vStep = 1ULL<<(scale-20);
445         int stillToDistribute = 1<<tableLog;
446         unsigned s;
447         unsigned largest=0;
448         short largestP=0;
449         U32 lowThreshold = (U32)(total >> tableLog);
450 
451         for (s=0; s<=maxSymbolValue; s++) {
452             if (count[s] == total) return 0;   /* rle special case */
453             if (count[s] == 0) { normalizedCounter[s]=0; continue; }
454             if (count[s] <= lowThreshold) {
455                 normalizedCounter[s] = lowProbCount;
456                 stillToDistribute--;
457             } else {
458                 short proba = (short)((count[s]*step) >> scale);
459                 if (proba<8) {
460                     U64 restToBeat = vStep * rtbTable[proba];
461                     proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat;
462                 }
463                 if (proba > largestP) { largestP=proba; largest=s; }
464                 normalizedCounter[s] = proba;
465                 stillToDistribute -= proba;
466         }   }
467         if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
468             /* corner case, need another normalization method */
469             size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue, lowProbCount);
470             if (FSE_isError(errorCode)) return errorCode;
471         }
472         else normalizedCounter[largest] += (short)stillToDistribute;
473     }
474 
475 #if 0
476     {   /* Print Table (debug) */
477         U32 s;
478         U32 nTotal = 0;
479         for (s=0; s<=maxSymbolValue; s++)
480             RAWLOG(2, "%3i: %4i \n", s, normalizedCounter[s]);
481         for (s=0; s<=maxSymbolValue; s++)
482             nTotal += abs(normalizedCounter[s]);
483         if (nTotal != (1U<<tableLog))
484             RAWLOG(2, "Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog);
485         getchar();
486     }
487 #endif
488 
489     return tableLog;
490 }
491 
492 
493 /* fake FSE_CTable, for raw (uncompressed) input */
FSE_buildCTable_raw(FSE_CTable * ct,unsigned nbBits)494 size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits)
495 {
496     const unsigned tableSize = 1 << nbBits;
497     const unsigned tableMask = tableSize - 1;
498     const unsigned maxSymbolValue = tableMask;
499     void* const ptr = ct;
500     U16* const tableU16 = ( (U16*) ptr) + 2;
501     void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableSize>>1);   /* assumption : tableLog >= 1 */
502     FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
503     unsigned s;
504 
505     /* Sanity checks */
506     if (nbBits < 1) return ERROR(GENERIC);             /* min size */
507 
508     /* header */
509     tableU16[-2] = (U16) nbBits;
510     tableU16[-1] = (U16) maxSymbolValue;
511 
512     /* Build table */
513     for (s=0; s<tableSize; s++)
514         tableU16[s] = (U16)(tableSize + s);
515 
516     /* Build Symbol Transformation Table */
517     {   const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits);
518         for (s=0; s<=maxSymbolValue; s++) {
519             symbolTT[s].deltaNbBits = deltaNbBits;
520             symbolTT[s].deltaFindState = s-1;
521     }   }
522 
523     return 0;
524 }
525 
526 /* fake FSE_CTable, for rle input (always same symbol) */
FSE_buildCTable_rle(FSE_CTable * ct,BYTE symbolValue)527 size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue)
528 {
529     void* ptr = ct;
530     U16* tableU16 = ( (U16*) ptr) + 2;
531     void* FSCTptr = (U32*)ptr + 2;
532     FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr;
533 
534     /* header */
535     tableU16[-2] = (U16) 0;
536     tableU16[-1] = (U16) symbolValue;
537 
538     /* Build table */
539     tableU16[0] = 0;
540     tableU16[1] = 0;   /* just in case */
541 
542     /* Build Symbol Transformation Table */
543     symbolTT[symbolValue].deltaNbBits = 0;
544     symbolTT[symbolValue].deltaFindState = 0;
545 
546     return 0;
547 }
548 
549 
FSE_compress_usingCTable_generic(void * dst,size_t dstSize,const void * src,size_t srcSize,const FSE_CTable * ct,const unsigned fast)550 static size_t FSE_compress_usingCTable_generic (void* dst, size_t dstSize,
551                            const void* src, size_t srcSize,
552                            const FSE_CTable* ct, const unsigned fast)
553 {
554     const BYTE* const istart = (const BYTE*) src;
555     const BYTE* const iend = istart + srcSize;
556     const BYTE* ip=iend;
557 
558     BIT_CStream_t bitC;
559     FSE_CState_t CState1, CState2;
560 
561     /* init */
562     if (srcSize <= 2) return 0;
563     { size_t const initError = BIT_initCStream(&bitC, dst, dstSize);
564       if (FSE_isError(initError)) return 0; /* not enough space available to write a bitstream */ }
565 
566 #define FSE_FLUSHBITS(s)  (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
567 
568     if (srcSize & 1) {
569         FSE_initCState2(&CState1, ct, *--ip);
570         FSE_initCState2(&CState2, ct, *--ip);
571         FSE_encodeSymbol(&bitC, &CState1, *--ip);
572         FSE_FLUSHBITS(&bitC);
573     } else {
574         FSE_initCState2(&CState2, ct, *--ip);
575         FSE_initCState2(&CState1, ct, *--ip);
576     }
577 
578     /* join to mod 4 */
579     srcSize -= 2;
580     if ((sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) && (srcSize & 2)) {  /* test bit 2 */
581         FSE_encodeSymbol(&bitC, &CState2, *--ip);
582         FSE_encodeSymbol(&bitC, &CState1, *--ip);
583         FSE_FLUSHBITS(&bitC);
584     }
585 
586     /* 2 or 4 encoding per loop */
587     while ( ip>istart ) {
588 
589         FSE_encodeSymbol(&bitC, &CState2, *--ip);
590 
591         if (sizeof(bitC.bitContainer)*8 < FSE_MAX_TABLELOG*2+7 )   /* this test must be static */
592             FSE_FLUSHBITS(&bitC);
593 
594         FSE_encodeSymbol(&bitC, &CState1, *--ip);
595 
596         if (sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) {  /* this test must be static */
597             FSE_encodeSymbol(&bitC, &CState2, *--ip);
598             FSE_encodeSymbol(&bitC, &CState1, *--ip);
599         }
600 
601         FSE_FLUSHBITS(&bitC);
602     }
603 
604     FSE_flushCState(&bitC, &CState2);
605     FSE_flushCState(&bitC, &CState1);
606     return BIT_closeCStream(&bitC);
607 }
608 
FSE_compress_usingCTable(void * dst,size_t dstSize,const void * src,size_t srcSize,const FSE_CTable * ct)609 size_t FSE_compress_usingCTable (void* dst, size_t dstSize,
610                            const void* src, size_t srcSize,
611                            const FSE_CTable* ct)
612 {
613     unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
614 
615     if (fast)
616         return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1);
617     else
618         return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0);
619 }
620 
621 
FSE_compressBound(size_t size)622 size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); }
623 
624 
625 #endif   /* FSE_COMMONDEFS_ONLY */
626