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