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