ReactOS 0.4.16-dev-297-gc569aee
fse_compress.c File Reference
#include <stdlib.h>
#include <string.h>
#include "compiler.h"
#include "mem.h"
#include "debug.h"
#include "hist.h"
#include "bitstream.h"
#include "fse.h"
#include "error_private.h"
#include <ntifs.h>
#include <ntddk.h>
Include dependency graph for fse_compress.c:

Go to the source code of this file.

Classes

struct  fseWkspMax_t
 

Macros

#define FSE_STATIC_LINKING_ONLY
 
#define FSE_isError   ERR_isError
 
#define FSE_CAT(X, Y)   X##Y
 
#define FSE_FUNCTION_NAME(X, Y)   FSE_CAT(X,Y)
 
#define FSE_TYPE_NAME(X, Y)   FSE_CAT(X,Y)
 
#define FSEC_ALLOC_TAG   0x64455346
 
#define FSE_FLUSHBITS(s)   (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
 

Functions

size_t FSE_buildCTable_wksp (FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
 
size_t FSE_buildCTable (FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
 
size_t FSE_NCountWriteBound (unsigned maxSymbolValue, unsigned tableLog)
 
static size_t FSE_writeNCount_generic (void *header, size_t headerBufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, unsigned writeIsSafe)
 
size_t FSE_writeNCount (void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
 
FSE_CTableFSE_createCTable (unsigned maxSymbolValue, unsigned tableLog)
 
void FSE_freeCTable (FSE_CTable *ct)
 
static unsigned FSE_minTableLog (size_t srcSize, unsigned maxSymbolValue)
 
unsigned FSE_optimalTableLog_internal (unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
 
unsigned FSE_optimalTableLog (unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
 
static size_t FSE_normalizeM2 (short *norm, U32 tableLog, const unsigned *count, size_t total, U32 maxSymbolValue)
 
size_t FSE_normalizeCount (short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t total, unsigned maxSymbolValue)
 
size_t FSE_buildCTable_raw (FSE_CTable *ct, unsigned nbBits)
 
size_t FSE_buildCTable_rle (FSE_CTable *ct, BYTE symbolValue)
 
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_compress_usingCTable (void *dst, size_t dstSize, const void *src, size_t srcSize, const FSE_CTable *ct)
 
size_t FSE_compressBound (size_t size)
 
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)
 
size_t FSE_compress2 (void *dst, size_t dstCapacity, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
 
size_t FSE_compress (void *dst, size_t dstCapacity, const void *src, size_t srcSize)
 

Macro Definition Documentation

◆ FSE_CAT

#define FSE_CAT (   X,
  Y 
)    X##Y

Definition at line 56 of file fse_compress.c.

◆ FSE_FLUSHBITS

#define FSE_FLUSHBITS (   s)    (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))

◆ FSE_FUNCTION_NAME

#define FSE_FUNCTION_NAME (   X,
  Y 
)    FSE_CAT(X,Y)

Definition at line 57 of file fse_compress.c.

◆ FSE_isError

#define FSE_isError   ERR_isError

Definition at line 35 of file fse_compress.c.

◆ FSE_STATIC_LINKING_ONLY

#define FSE_STATIC_LINKING_ONLY

Definition at line 25 of file fse_compress.c.

◆ FSE_TYPE_NAME

#define FSE_TYPE_NAME (   X,
  Y 
)    FSE_CAT(X,Y)

Definition at line 58 of file fse_compress.c.

◆ FSEC_ALLOC_TAG

#define FSEC_ALLOC_TAG   0x64455346

Definition at line 60 of file fse_compress.c.

Function Documentation

◆ FSE_buildCTable()

size_t FSE_buildCTable ( FSE_CTable ct,
const short normalizedCounter,
unsigned  maxSymbolValue,
unsigned  tableLog 
)

FSE_buildCTable(): Builds ct, which must be already allocated, using FSE_createCTable().

Returns
: 0, or an errorCode, which can be tested using FSE_isError()

Definition at line 175 of file fse_compress.c.

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}
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

◆ FSE_buildCTable_raw()

size_t FSE_buildCTable_raw ( FSE_CTable ct,
unsigned  nbBits 
)

Definition at line 501 of file fse_compress.c.

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}
#define ERROR(name)
Definition: error_private.h:53
GLdouble s
Definition: gl.h:2039
static PVOID ptr
Definition: dispmode.c:27
unsigned int U32
Definition: xxhash.c:195
unsigned short U16
Definition: xxhash.c:194

◆ FSE_buildCTable_rle()

size_t FSE_buildCTable_rle ( FSE_CTable ct,
BYTE  symbolValue 
)

Definition at line 534 of file fse_compress.c.

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}

Referenced by ZSTD_buildCTable().

◆ FSE_buildCTable_wksp()

size_t FSE_buildCTable_wksp ( FSE_CTable ct,
const short normalizedCounter,
unsigned  maxSymbolValue,
unsigned  tableLog,
void workSpace,
size_t  wkspSize 
)

Definition at line 69 of file fse_compress.c.

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}
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
#define assert(x)
Definition: debug.h:53
#define DEBUGLOG(l,...)
Definition: debug.h:106
size_t total
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
#define memset(x, y, z)
Definition: compat.h:39

Referenced by FSE_buildCTable(), FSE_compress_wksp(), HUF_compressWeights(), ZSTD_buildCTable(), and ZSTD_loadCEntropy().

◆ FSE_compress()

size_t FSE_compress ( void dst,
size_t  dstCapacity,
const void src,
size_t  srcSize 
)

FSE_compress() : Compress content of buffer 'src', of size 'srcSize', into destination buffer 'dst'. 'dst' buffer must be already allocated. Compression runs faster is dstCapacity >= FSE_compressBound(srcSize).

Returns
: size of compressed data (<= dstCapacity). Special values : if return == 0, srcData is not compressible => Nothing is stored within dst !!! if return == 1, srcData is a single byte symbol * srcSize times. Use RLE compression instead. if FSE_isError(return), compression failed (more details using FSE_getErrorName())

Definition at line 695 of file fse_compress.c.

696{
697 return FSE_compress2(dst, dstCapacity, src, srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG);
698}
size_t FSE_compress2(void *dst, size_t dstCapacity, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:687
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

◆ FSE_compress2()

size_t FSE_compress2 ( void dst,
size_t  dstSize,
const void src,
size_t  srcSize,
unsigned  maxSymbolValue,
unsigned  tableLog 
)

FSE_compress2() : Same as FSE_compress(), but allows the selection of 'maxSymbolValue' and 'tableLog' Both parameters can be defined as '0' to mean : use default value

Returns
: size of compressed data Special values : if return == 0, srcData is not compressible => Nothing is stored within cSrc !!! if return == 1, srcData is a single byte symbol * srcSize times. Use RLE compression. if FSE_isError(return), it's an error code.

Definition at line 687 of file fse_compress.c.

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}
#define DEBUG_STATIC_ASSERT(c)
Definition: debug.h:43
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

Referenced by FSE_compress().

◆ FSE_compress_usingCTable()

size_t FSE_compress_usingCTable ( void dst,
size_t  dstCapacity,
const void src,
size_t  srcSize,
const FSE_CTable ct 
)

FSE_compress_usingCTable(): Compress src using ct into dst which must be already allocated.

Returns
: size of compressed data (<= dstCapacity), or 0 if compressed data could not fit into dst, or an errorCode, which can be tested using FSE_isError()

Definition at line 616 of file fse_compress.c.

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}
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

Referenced by FSE_compress_wksp(), and HUF_compressWeights().

◆ FSE_compress_usingCTable_generic()

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 
)
static

Definition at line 557 of file fse_compress.c.

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}
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
Definition: bitstream.h:254
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity)
Definition: bitstream.h:183
#define FSE_isError
Definition: fse_compress.c:35
#define FSE_FLUSHBITS(s)
size_t bitContainer
Definition: bitstream.h:58
Definition: dhcpd.h:62
unsigned char BYTE
Definition: xxhash.c:193

Referenced by FSE_compress_usingCTable().

◆ FSE_compress_wksp()

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 at line 635 of file fse_compress.c.

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}
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
UINT op
Definition: effect.c:236
signed short S16
Definition: mem.h:146
#define CHECK_F(f)
Definition: error_private.h:62
#define CHECK_V_F(e, f)
Definition: error_private.h:61
unsigned FSE_CTable
Definition: fse.h:160
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_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t total, unsigned maxSymbolValue)
Definition: fse_compress.c:438
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
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLsizei maxCount
Definition: glext.h:6042
size_t HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
Definition: hist.c:166

Referenced by FSE_compress2().

◆ FSE_compressBound()

size_t FSE_compressBound ( size_t  size)

Definition at line 629 of file fse_compress.c.

629{ return FSE_COMPRESSBOUND(size); }
GLsizeiptr size
Definition: glext.h:5919

◆ FSE_createCTable()

FSE_CTable * FSE_createCTable ( unsigned  maxSymbolValue,
unsigned  tableLog 
)

Definition at line 308 of file fse_compress.c.

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}
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define PagedPool
Definition: env_spec_w32.h:308
#define FSEC_ALLOC_TAG
Definition: fse_compress.c:60

◆ FSE_freeCTable()

void FSE_freeCTable ( FSE_CTable ct)

Definition at line 316 of file fse_compress.c.

316{ ExFreePool(ct); }
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

◆ FSE_minTableLog()

static unsigned FSE_minTableLog ( size_t  srcSize,
unsigned  maxSymbolValue 
)
static

Definition at line 319 of file fse_compress.c.

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}

Referenced by FSE_normalizeCount(), and FSE_optimalTableLog_internal().

◆ FSE_NCountWriteBound()

size_t FSE_NCountWriteBound ( unsigned  maxSymbolValue,
unsigned  tableLog 
)

FSE_NCountWriteBound(): Provides the maximum possible size of an FSE normalized table, given 'maxSymbolValue' and 'tableLog'. Typically useful for allocation purpose.

Definition at line 189 of file fse_compress.c.

190{
191 size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3;
192 return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */
193}

Referenced by FSE_writeNCount().

◆ FSE_normalizeCount()

size_t FSE_normalizeCount ( short normalizedCounter,
unsigned  tableLog,
const unsigned count,
size_t  srcSize,
unsigned  maxSymbolValue 
)

FSE_normalizeCount(): normalize counts so that sum(count[]) == Power_of_2 (2^tableLog) 'normalizedCounter' is a table of short, of minimum size (maxSymbolValue+1).

Returns
: tableLog, or an errorCode, which can be tested using FSE_isError()

Definition at line 438 of file fse_compress.c.

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}
unsigned short(__cdecl typeof(TIFFCurrentDirectory))(struct tiff *)
Definition: typeof.h:94
#define RAWLOG(l,...)
Definition: debug.h:105
#define abs(i)
Definition: fconv.c:206
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
GLenum GLenum GLenum GLenum GLenum scale
Definition: glext.h:9032
_Check_return_ _CRTIMP int __cdecl getchar(void)
Definition: file.c:3629
unsigned long long U64
Definition: xxhash.c:197

Referenced by FSE_compress_wksp(), HUF_compressWeights(), ZSTD_buildCTable(), and ZSTD_NCountCost().

◆ FSE_normalizeM2()

static size_t FSE_normalizeM2 ( short norm,
U32  tableLog,
const unsigned count,
size_t  total,
U32  maxSymbolValue 
)
static

Definition at line 351 of file fse_compress.c.

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}
GLuint GLuint end
Definition: gl.h:1545
weight
Definition: sortkey.c:157

Referenced by FSE_normalizeCount().

◆ FSE_optimalTableLog()

unsigned FSE_optimalTableLog ( unsigned  maxTableLog,
size_t  srcSize,
unsigned  maxSymbolValue 
)

FSE_compress() does the following:

  1. count symbol occurrence from source[] into table count[] (see hist.h)
  2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog)
  3. save normalized counters to memory buffer using writeNCount()
  4. build encoding table 'CTable' from normalized counters
  5. encode the data stream using encoding table 'CTable'

FSE_decompress() does the following:

  1. read normalized counters with readNCount()
  2. build decoding table 'DTable' from normalized counters
  3. decode the data stream using decoding table 'DTable'

The following API allows targeting specific sub-functions for advanced tasks. For example, it's possible to compress several blocks using the same 'CTable', or to save and provide normalized distribution using external method.

FSE_optimalTableLog(): dynamically downsize 'tableLog' when conditions are met. It saves CPU time, by using smaller tables, while preserving or even improving compression ratio.

Returns
: recommended tableLog (necessarily <= 'maxTableLog')

Definition at line 342 of file fse_compress.c.

343{
344 return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
345}
unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
Definition: fse_compress.c:328

Referenced by FSE_compress_wksp(), HUF_compressWeights(), ZSTD_buildCTable(), and ZSTD_NCountCost().

◆ FSE_optimalTableLog_internal()

unsigned FSE_optimalTableLog_internal ( unsigned  maxTableLog,
size_t  srcSize,
unsigned  maxSymbolValue,
unsigned  minus 
)

Definition at line 328 of file fse_compress.c.

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}

Referenced by FSE_optimalTableLog(), and HUF_optimalTableLog().

◆ FSE_writeNCount()

size_t FSE_writeNCount ( void buffer,
size_t  bufferSize,
const short normalizedCounter,
unsigned  maxSymbolValue,
unsigned  tableLog 
)

FSE_writeNCount(): Compactly save 'normalizedCounter' into 'buffer'.

Returns
: size of the compressed table, or an errorCode, which can be tested using FSE_isError().

Definition at line 291 of file fse_compress.c.

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}
size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:189
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
size_t bufferSize
GLuint buffer
Definition: glext.h:5915

Referenced by FSE_compress_wksp(), HUF_compressWeights(), ZSTD_buildCTable(), and ZSTD_NCountCost().

◆ FSE_writeNCount_generic()

static size_t FSE_writeNCount_generic ( void header,
size_t  headerBufferSize,
const short normalizedCounter,
unsigned  maxSymbolValue,
unsigned  tableLog,
unsigned  writeIsSafe 
)
static

Definition at line 196 of file fse_compress.c.

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}
GLuint start
Definition: gl.h:1545
static FILE * out
Definition: regtests2xml.c:44
#define max(a, b)
Definition: svc.c:63

Referenced by FSE_writeNCount().