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