25#define FSE_STATIC_LINKING_ONLY
35#define FSE_isError ERR_isError
48#ifndef FSE_FUNCTION_EXTENSION
49# error "FSE_FUNCTION_EXTENSION must be defined"
51#ifndef FSE_FUNCTION_TYPE
52# error "FSE_FUNCTION_TYPE must be defined"
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)
60#define FSEC_ALLOC_TAG 0x64455346
70 const short* normalizedCounter,
unsigned maxSymbolValue,
unsigned tableLog,
71 void* workSpace,
size_t wkspSize)
73 U32 const tableSize = 1 << tableLog;
74 U32 const tableMask = tableSize - 1;
77 void*
const FSCT = ((
U32*)
ptr) + 1 + (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];
82 FSE_FUNCTION_TYPE*
const tableSymbol = (FSE_FUNCTION_TYPE*)workSpace;
83 U32 highThreshold = tableSize-1;
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;
94 #ifdef __clang_analyzer__
95 memset(tableSymbol, 0,
sizeof(*tableSymbol) * tableSize);
101 for (
u=1;
u <= maxSymbolValue+1;
u++) {
102 if (normalizedCounter[
u-1]==-1) {
103 cumul[
u] = cumul[
u-1] + 1;
104 tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(
u-1);
106 cumul[
u] = cumul[
u-1] + normalizedCounter[
u-1];
108 cumul[maxSymbolValue+1] = tableSize+1;
114 for (symbol=0; symbol<=maxSymbolValue; symbol++) {
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;
128 {
U32 u;
for (
u=0;
u<tableSize;
u++) {
129 FSE_FUNCTION_TYPE
s = tableSymbol[
u];
130 tableU16[cumul[
s]++] = (
U16) (tableSize+
u);
134 {
unsigned total = 0;
136 for (
s=0;
s<=maxSymbolValue;
s++) {
137 switch (normalizedCounter[
s])
141 symbolTT[
s].deltaNbBits = ((tableLog+1) << 16) - (1<<tableLog);
146 symbolTT[
s].deltaNbBits = (tableLog << 16) - (1<<tableLog);
147 symbolTT[
s].deltaFindState =
total - 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];
160 DEBUGLOG(5,
"\n --- table statistics : ");
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);
177 FSE_FUNCTION_TYPE tableSymbol[FSE_MAX_TABLESIZE];
178 return FSE_buildCTable_wksp(ct, normalizedCounter, maxSymbolValue, tableLog, tableSymbol,
sizeof(tableSymbol));
183#ifndef FSE_COMMONDEFS_ONLY
191 size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3;
192 return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND;
197 const short* normalizedCounter,
unsigned maxSymbolValue,
unsigned tableLog,
198 unsigned writeIsSafe)
202 BYTE*
const oend = ostart + headerBufferSize;
204 const int tableSize = 1 << tableLog;
210 unsigned const alphabetSize = maxSymbolValue + 1;
214 bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount;
218 remaining = tableSize+1;
219 threshold = tableSize;
222 while ((symbol < alphabetSize) && (remaining>1)) {
224 unsigned start = symbol;
225 while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++;
226 if (symbol == alphabetSize)
break;
227 while (symbol >=
start+24) {
229 bitStream += 0xFFFFU << bitCount;
230 if ((!writeIsSafe) && (
out > oend-2))
231 return ERROR(dstSize_tooSmall);
237 while (symbol >=
start+3) {
239 bitStream += 3 << bitCount;
242 bitStream += (symbol-
start) << bitCount;
245 if ((!writeIsSafe) && (
out > oend - 2))
246 return ERROR(dstSize_tooSmall);
253 {
int count = normalizedCounter[symbol++];
254 int const max = (2*threshold-1) - remaining;
257 if (
count>=threshold)
259 bitStream +=
count << bitCount;
262 previousIs0 = (
count==1);
263 if (remaining<1)
return ERROR(GENERIC);
264 while (remaining<threshold) { nbBits--; threshold>>=1; }
267 if ((!writeIsSafe) && (
out > oend - 2))
268 return ERROR(dstSize_tooSmall);
277 return ERROR(GENERIC);
278 assert(symbol <= alphabetSize);
281 if ((!writeIsSafe) && (
out > oend - 2))
282 return ERROR(dstSize_tooSmall);
285 out+= (bitCount+7) /8;
292 const short* normalizedCounter,
unsigned maxSymbolValue,
unsigned tableLog)
294 if (tableLog > FSE_MAX_TABLELOG)
return ERROR(tableLog_tooLarge);
295 if (tableLog < FSE_MIN_TABLELOG)
return ERROR(GENERIC);
311 if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
312 size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) *
sizeof(
U32);
323 U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
331 U32 tableLog = maxTableLog;
334 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
335 if (maxBitsSrc < tableLog) tableLog = maxBitsSrc;
336 if (minBits > tableLog) tableLog = minBits;
337 if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG;
338 if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG;
353 short const NOT_YET_ASSIGNED = -2;
362 for (
s=0;
s<=maxSymbolValue;
s++) {
367 if (
count[
s] <= lowThreshold) {
380 norm[
s]=NOT_YET_ASSIGNED;
382 ToDistribute = (1 << tableLog) - distributed;
384 if (ToDistribute == 0)
387 if ((
total / ToDistribute) > lowOne) {
389 lowOne = (
U32)((
total * 3) / (ToDistribute * 2));
390 for (
s=0;
s<=maxSymbolValue;
s++) {
391 if ((
norm[
s] == NOT_YET_ASSIGNED) && (
count[
s] <= lowOne)) {
397 ToDistribute = (1 << tableLog) - distributed;
400 if (distributed == maxSymbolValue+1) {
404 U32 maxV = 0, maxC = 0;
405 for (
s=0;
s<=maxSymbolValue;
s++)
413 for (
s=0; ToDistribute > 0;
s = (
s+1)%(maxSymbolValue+1))
414 if (
norm[
s] > 0) { ToDistribute--;
norm[
s]++; }
418 {
U64 const vStepLog = 62 - tableLog;
419 U64 const mid = (1ULL << (vStepLog-1)) - 1;
420 U64 const rStep = ((((
U64)1<<vStepLog) * ToDistribute) + mid) /
total;
422 for (
s=0;
s<=maxSymbolValue;
s++) {
423 if (
norm[
s]==NOT_YET_ASSIGNED) {
425 U32 const sStart = (
U32)(tmpTotal >> vStepLog);
429 return ERROR(GENERIC);
440 unsigned maxSymbolValue)
443 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
444 if (tableLog < FSE_MIN_TABLELOG)
return ERROR(GENERIC);
445 if (tableLog > FSE_MAX_TABLELOG)
return ERROR(tableLog_tooLarge);
448 {
static U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
452 int stillToDistribute = 1<<tableLog;
458 for (
s=0;
s<=maxSymbolValue;
s++) {
460 if (
count[
s] == 0) { normalizedCounter[
s]=0;
continue; }
461 if (
count[
s] <= lowThreshold) {
462 normalizedCounter[
s] = -1;
467 U64 restToBeat = vStep * rtbTable[proba];
468 proba += (
count[
s]*step) - ((
U64)proba<<scale) > restToBeat;
470 if (proba > largestP) { largestP=proba; largest=
s; }
471 normalizedCounter[
s] = proba;
472 stillToDistribute -= proba;
474 if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
479 else normalizedCounter[largest] += (
short)stillToDistribute;
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);
503 const unsigned tableSize = 1 << nbBits;
504 const unsigned tableMask = tableSize - 1;
505 const unsigned maxSymbolValue = tableMask;
506 void*
const ptr = ct;
508 void*
const FSCT = ((
U32*)
ptr) + 1 + (tableSize>>1);
509 FSE_symbolCompressionTransform*
const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
513 if (nbBits < 1)
return ERROR(GENERIC);
516 tableU16[-2] = (
U16) nbBits;
517 tableU16[-1] = (
U16) maxSymbolValue;
520 for (
s=0;
s<tableSize;
s++)
521 tableU16[
s] = (
U16)(tableSize +
s);
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;
538 void* FSCTptr = (
U32*)
ptr + 2;
539 FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr;
542 tableU16[-2] = (
U16) 0;
543 tableU16[-1] = (
U16) symbolValue;
550 symbolTT[symbolValue].deltaNbBits = 0;
551 symbolTT[symbolValue].deltaFindState = 0;
558 const void*
src,
size_t srcSize,
562 const BYTE*
const iend = istart + srcSize;
566 FSE_CState_t CState1, CState2;
569 if (srcSize <= 2)
return 0;
573#define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
576 FSE_initCState2(&CState1, ct, *--
ip);
577 FSE_initCState2(&CState2, ct, *--
ip);
578 FSE_encodeSymbol(&bitC, &CState1, *--
ip);
581 FSE_initCState2(&CState2, ct, *--
ip);
582 FSE_initCState2(&CState1, ct, *--
ip);
587 if ((
sizeof(bitC.
bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) && (srcSize & 2)) {
588 FSE_encodeSymbol(&bitC, &CState2, *--
ip);
589 FSE_encodeSymbol(&bitC, &CState1, *--
ip);
594 while (
ip>istart ) {
596 FSE_encodeSymbol(&bitC, &CState2, *--
ip);
598 if (
sizeof(bitC.
bitContainer)*8 < FSE_MAX_TABLELOG*2+7 )
601 FSE_encodeSymbol(&bitC, &CState1, *--
ip);
603 if (
sizeof(bitC.
bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) {
604 FSE_encodeSymbol(&bitC, &CState2, *--
ip);
605 FSE_encodeSymbol(&bitC, &CState1, *--
ip);
611 FSE_flushCState(&bitC, &CState2);
612 FSE_flushCState(&bitC, &CState1);
617 const void*
src,
size_t srcSize,
620 unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
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)
639 BYTE*
const oend = ostart + dstSize;
641 unsigned count[FSE_MAX_SYMBOL_VALUE+1];
642 S16 norm[FSE_MAX_SYMBOL_VALUE+1];
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));
649 if (wkspSize < FSE_WKSP_SIZE_U32(tableLog, maxSymbolValue))
return ERROR(tableLog_tooLarge);
650 if (srcSize <= 1)
return 0;
651 if (!maxSymbolValue) maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
652 if (!tableLog) tableLog = FSE_DEFAULT_TABLELOG;
658 if (
maxCount < (srcSize >> 7))
return 0;
672 if (cSize == 0)
return 0;
677 if ( (
size_t)(
op-ostart) >= srcSize-1 )
return 0;
683 FSE_CTable CTable_max[FSE_CTABLE_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)];
684 BYTE scratchBuffer[1 << FSE_MAX_TABLELOG];
687size_t FSE_compress2 (
void*
dst,
size_t dstCapacity,
const void*
src,
size_t srcSize,
unsigned maxSymbolValue,
unsigned tableLog)
690 DEBUG_STATIC_ASSERT(
sizeof(scratchBuffer) >= FSE_WKSP_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE));
691 if (tableLog > FSE_MAX_TABLELOG)
return ERROR(tableLog_tooLarge);
692 return FSE_compress_wksp(
dst, dstCapacity,
src, srcSize, maxSymbolValue, tableLog, &scratchBuffer,
sizeof(scratchBuffer));
697 return FSE_compress2(
dst, dstCapacity,
src, srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG);
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
MEM_STATIC unsigned BIT_highbit32(U32 val)
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity)
unsigned short(__cdecl typeof(TIFFCurrentDirectory))(struct tiff *)
#define DEBUG_STATIC_ASSERT(c)
#define ExAllocatePoolWithTag(hernya, size, tag)
size_t FSE_compress(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
size_t FSE_buildCTable(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
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)
static size_t FSE_normalizeM2(short *norm, U32 tableLog, const unsigned *count, size_t total, U32 maxSymbolValue)
static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
size_t FSE_compressBound(size_t size)
size_t FSE_buildCTable_wksp(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
size_t FSE_compress_usingCTable(void *dst, size_t dstSize, const void *src, size_t srcSize, const FSE_CTable *ct)
size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
void FSE_freeCTable(FSE_CTable *ct)
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)
size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t total, unsigned maxSymbolValue)
size_t FSE_compress2(void *dst, size_t dstCapacity, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
size_t FSE_buildCTable_rle(FSE_CTable *ct, BYTE symbolValue)
FSE_CTable * FSE_createCTable(unsigned maxSymbolValue, unsigned tableLog)
size_t FSE_buildCTable_raw(FSE_CTable *ct, unsigned nbBits)
static size_t FSE_writeNCount_generic(void *header, size_t headerBufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, unsigned writeIsSafe)
unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
GLuint GLuint GLsizei count
GLenum GLenum GLenum GLenum GLenum scale
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
size_t HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
_Check_return_ _CRTIMP int __cdecl getchar(void)