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