ReactOS  0.4.15-dev-4614-ga5a6101
fse.h File Reference
#include <stddef.h>
#include "bitstream.h"
Include dependency graph for fse.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define FSE_H
 
#define FSE_PUBLIC_API
 
#define FSE_VERSION_MAJOR   0
 
#define FSE_VERSION_MINOR   9
 
#define FSE_VERSION_RELEASE   0
 
#define FSE_LIB_VERSION   FSE_VERSION_MAJOR.FSE_VERSION_MINOR.FSE_VERSION_RELEASE
 
#define FSE_QUOTE(str)   #str
 
#define FSE_EXPAND_AND_QUOTE(str)   FSE_QUOTE(str)
 
#define FSE_VERSION_STRING   FSE_EXPAND_AND_QUOTE(FSE_LIB_VERSION)
 
#define FSE_VERSION_NUMBER   (FSE_VERSION_MAJOR *100*100 + FSE_VERSION_MINOR *100 + FSE_VERSION_RELEASE)
 

Typedefs

typedef unsigned FSE_CTable
 
typedef unsigned FSE_DTable
 

Functions

FSE_PUBLIC_API unsigned FSE_versionNumber (void)
 
FSE_PUBLIC_API size_t FSE_compress (void *dst, size_t dstCapacity, const void *src, size_t srcSize)
 
FSE_PUBLIC_API size_t FSE_decompress (void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize)
 
FSE_PUBLIC_API size_t FSE_compressBound (size_t size)
 
FSE_PUBLIC_API unsigned FSE_isError (size_t code)
 
FSE_PUBLIC_API const charFSE_getErrorName (size_t code)
 
FSE_PUBLIC_API size_t FSE_compress2 (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
 
FSE_PUBLIC_API unsigned FSE_optimalTableLog (unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
 
FSE_PUBLIC_API size_t FSE_normalizeCount (short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t srcSize, unsigned maxSymbolValue)
 
FSE_PUBLIC_API size_t FSE_NCountWriteBound (unsigned maxSymbolValue, unsigned tableLog)
 
FSE_PUBLIC_API size_t FSE_writeNCount (void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
 
FSE_PUBLIC_API FSE_CTableFSE_createCTable (unsigned maxSymbolValue, unsigned tableLog)
 
FSE_PUBLIC_API void FSE_freeCTable (FSE_CTable *ct)
 
FSE_PUBLIC_API size_t FSE_buildCTable (FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
 
FSE_PUBLIC_API size_t FSE_compress_usingCTable (void *dst, size_t dstCapacity, const void *src, size_t srcSize, const FSE_CTable *ct)
 
FSE_PUBLIC_API size_t FSE_readNCount (short *normalizedCounter, unsigned *maxSymbolValuePtr, unsigned *tableLogPtr, const void *rBuffer, size_t rBuffSize)
 
FSE_PUBLIC_API FSE_DTableFSE_createDTable (unsigned tableLog)
 
FSE_PUBLIC_API void FSE_freeDTable (FSE_DTable *dt)
 
FSE_PUBLIC_API size_t FSE_buildDTable (FSE_DTable *dt, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
 
FSE_PUBLIC_API size_t FSE_decompress_usingDTable (void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt)
 

Macro Definition Documentation

◆ FSE_EXPAND_AND_QUOTE

#define FSE_EXPAND_AND_QUOTE (   str)    FSE_QUOTE(str)

Definition at line 49 of file fse.h.

◆ FSE_H

#define FSE_H

Definition at line 20 of file fse.h.

◆ FSE_LIB_VERSION

Definition at line 47 of file fse.h.

◆ FSE_PUBLIC_API

#define FSE_PUBLIC_API

Definition at line 39 of file fse.h.

◆ FSE_QUOTE

#define FSE_QUOTE (   str)    #str

Definition at line 48 of file fse.h.

◆ FSE_VERSION_MAJOR

#define FSE_VERSION_MAJOR   0

Definition at line 43 of file fse.h.

◆ FSE_VERSION_MINOR

#define FSE_VERSION_MINOR   9

Definition at line 44 of file fse.h.

◆ FSE_VERSION_NUMBER

#define FSE_VERSION_NUMBER   (FSE_VERSION_MAJOR *100*100 + FSE_VERSION_MINOR *100 + FSE_VERSION_RELEASE)

Definition at line 52 of file fse.h.

◆ FSE_VERSION_RELEASE

#define FSE_VERSION_RELEASE   0

Definition at line 45 of file fse.h.

◆ FSE_VERSION_STRING

#define FSE_VERSION_STRING   FSE_EXPAND_AND_QUOTE(FSE_LIB_VERSION)

Definition at line 50 of file fse.h.

Typedef Documentation

◆ FSE_CTable

Constructor and Destructor of FSE_CTable. Note that FSE_CTable size depends on 'tableLog' and 'maxSymbolValue'

Definition at line 160 of file fse.h.

◆ FSE_DTable

Constructor and Destructor of FSE_DTable. Note that its size depends on 'tableLog'

Definition at line 233 of file fse.h.

Function Documentation

◆ FSE_buildCTable()

FSE_PUBLIC_API 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_buildDTable()

FSE_PUBLIC_API size_t FSE_buildDTable ( FSE_DTable dt,
const short normalizedCounter,
unsigned  maxSymbolValue,
unsigned  tableLog 
)

FSE_buildDTable(): Builds 'dt', which must be already allocated, using FSE_createDTable(). return : 0, or an errorCode, which can be tested using FSE_isError()

Definition at line 73 of file fse_decompress.c.

74 {
75  void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
76  FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr);
77  U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
78 
79  U32 const maxSV1 = maxSymbolValue + 1;
80  U32 const tableSize = 1 << tableLog;
81  U32 highThreshold = tableSize-1;
82 
83  /* Sanity Checks */
84  if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
85  if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
86 
87  /* Init, lay down lowprob symbols */
88  { FSE_DTableHeader DTableH;
89  DTableH.tableLog = (U16)tableLog;
90  DTableH.fastMode = 1;
91  { S16 const largeLimit= (S16)(1 << (tableLog-1));
92  U32 s;
93  for (s=0; s<maxSV1; s++) {
94  if (normalizedCounter[s]==-1) {
95  tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
96  symbolNext[s] = 1;
97  } else {
98  if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
99  symbolNext[s] = normalizedCounter[s];
100  } } }
101  memcpy(dt, &DTableH, sizeof(DTableH));
102  }
103 
104  /* Spread symbols */
105  { U32 const tableMask = tableSize-1;
106  U32 const step = FSE_TABLESTEP(tableSize);
107  U32 s, position = 0;
108  for (s=0; s<maxSV1; s++) {
109  int i;
110  for (i=0; i<normalizedCounter[s]; i++) {
111  tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
112  position = (position + step) & tableMask;
113  while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
114  } }
115  if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
116  }
117 
118  /* Build Decoding table */
119  { U32 u;
120  for (u=0; u<tableSize; u++) {
121  FSE_FUNCTION_TYPE const symbol = (FSE_FUNCTION_TYPE)(tableDecode[u].symbol);
122  U32 const nextState = symbolNext[symbol]++;
123  tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
124  tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
125  } }
126 
127  return 0;
128 }
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 ERROR(name)
Definition: error_private.h:53
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
GLdouble s
Definition: gl.h:2039
unsigned char BYTE
Definition: xxhash.c:193
unsigned short U16
Definition: xxhash.c:194
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 const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
signed short S16
Definition: mem.h:146
unsigned int U32
Definition: xxhash.c:195

Referenced by FSE_decompress_wksp().

◆ FSE_compress()

FSE_PUBLIC_API 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()

FSE_PUBLIC_API 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 ERROR(name)
Definition: error_private.h:53
#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
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

Referenced by FSE_compress().

◆ FSE_compress_usingCTable()

FSE_PUBLIC_API 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
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

Referenced by FSE_compress_wksp(), and HUF_compressWeights().

◆ FSE_compressBound()

FSE_PUBLIC_API 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_PUBLIC_API 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 }
unsigned FSE_CTable
Definition: fse.h:160
#define FSEC_ALLOC_TAG
Definition: fse_compress.c:60
GLsizeiptr size
Definition: glext.h:5919
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
unsigned int U32
Definition: xxhash.c:195

◆ FSE_createDTable()

FSE_PUBLIC_API FSE_DTable* FSE_createDTable ( unsigned  tableLog)

Definition at line 62 of file fse_decompress.c.

63 {
64  if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
65  return (FSE_DTable*)ExAllocatePoolWithTag(PagedPool, FSE_DTABLE_SIZE_U32(tableLog) * sizeof (U32), FSED_ALLOC_TAG);
66 }
unsigned FSE_DTable
Definition: fse.h:233
#define FSED_ALLOC_TAG
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
unsigned int U32
Definition: xxhash.c:195

◆ FSE_decompress()

FSE_PUBLIC_API size_t FSE_decompress ( void dst,
size_t  dstCapacity,
const void cSrc,
size_t  cSrcSize 
)

FSE_decompress(): Decompress FSE data from buffer 'cSrc', of size 'cSrcSize', into already allocated destination buffer 'dst', of size 'dstCapacity'.

Returns
: size of regenerated data (<= maxDstSize), or an error code, which can be tested using FSE_isError() .

Important ** : FSE_decompress() does not decompress non-compressible nor RLE data !!! Why ? : making this distinction requires a header. Header management is intentionally delegated to the user layer, which can better manage special cases.

Definition at line 281 of file fse_decompress.c.

282 {
283  DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
284  return FSE_decompress_wksp(dst, dstCapacity, cSrc, cSrcSize, dt, FSE_MAX_TABLELOG);
285 }
FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]
GLenum GLenum dst
Definition: glext.h:6340
size_t FSE_decompress_wksp(void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize, FSE_DTable *workSpace, unsigned maxLog)

◆ FSE_decompress_usingDTable()

FSE_PUBLIC_API size_t FSE_decompress_usingDTable ( void dst,
size_t  dstCapacity,
const void cSrc,
size_t  cSrcSize,
const FSE_DTable dt 
)

FSE_decompress_usingDTable(): Decompress compressed source cSrc of size cSrcSize using dt into dst which must be already allocated.

Returns
: size of regenerated data (necessarily <= dstCapacity), or an errorCode, which can be tested using FSE_isError()

Definition at line 243 of file fse_decompress.c.

246 {
247  const void* ptr = dt;
248  const FSE_DTableHeader* DTableH = (const FSE_DTableHeader*)ptr;
249  const U32 fastMode = DTableH->fastMode;
250 
251  /* select fast mode (static) */
252  if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
253  return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
254 }
FORCE_INLINE_TEMPLATE size_t FSE_decompress_usingDTable_generic(void *dst, size_t maxDstSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt, const unsigned fast)
static PVOID ptr
Definition: dispmode.c:27
GLenum GLenum dst
Definition: glext.h:6340
unsigned int U32
Definition: xxhash.c:195

Referenced by FSE_decompress_wksp().

◆ FSE_freeCTable()

FSE_PUBLIC_API 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_freeDTable()

FSE_PUBLIC_API void FSE_freeDTable ( FSE_DTable dt)

Definition at line 68 of file fse_decompress.c.

69 {
70  ExFreePool(dt);
71 }
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

◆ FSE_getErrorName()

FSE_PUBLIC_API const char* FSE_getErrorName ( size_t  code)

Definition at line 32 of file entropy_common.c.

32 { return ERR_getErrorName(code); }
ERR_STATIC const char * ERR_getErrorName(size_t code)
Definition: error_private.h:71
Definition: inflate.c:139

◆ FSE_isError()

FSE_PUBLIC_API unsigned FSE_isError ( size_t  code)

Definition at line 31 of file entropy_common.c.

31 { return ERR_isError(code); }
ERR_STATIC unsigned ERR_isError(size_t code)
Definition: error_private.h:56
Definition: inflate.c:139

Referenced by FSE_readNCount(), and HUF_readStats().

◆ FSE_NCountWriteBound()

FSE_PUBLIC_API 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()

FSE_PUBLIC_API 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 }
#define abs(i)
Definition: fconv.c:206
#define ERROR(name)
Definition: error_private.h:53
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLenum GLenum GLenum GLenum GLenum scale
Definition: glext.h:9032
#define U(x)
Definition: wordpad.c:45
unsigned short(__cdecl typeof(TIFFCurrentDirectory))(struct tiff *)
Definition: typeof.h:94
static size_t FSE_normalizeM2(short *norm, U32 tableLog, const unsigned *count, size_t total, U32 maxSymbolValue)
Definition: fse_compress.c:351
#define RAWLOG(l,...)
Definition: debug.h:105
#define FSE_isError
Definition: fse_compress.c:35
#define ULL(a, b)
Definition: format_msg.c:27
static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:319
GLdouble s
Definition: gl.h:2039
_Check_return_ _CRTIMP int __cdecl getchar(void)
Definition: file.c:3627
unsigned long long U64
Definition: xxhash.c:197
size_t total
unsigned int U32
Definition: xxhash.c:195

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

◆ FSE_optimalTableLog()

FSE_PUBLIC_API 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_readNCount()

FSE_PUBLIC_API size_t FSE_readNCount ( short normalizedCounter,
unsigned maxSymbolValuePtr,
unsigned tableLogPtr,
const void rBuffer,
size_t  rBuffSize 
)

Tutorial :

The first step is to count all symbols. FSE_count() does this job very fast. Result will be saved into 'count', a table of unsigned int, which must be already allocated, and have 'maxSymbolValuePtr[0]+1' cells. 'src' is a table of bytes of size 'srcSize'. All values within 'src' MUST be <= maxSymbolValuePtr[0] maxSymbolValuePtr[0] will be updated, with its real value (necessarily <= original value) FSE_count() will return the number of occurrence of the most frequent symbol. This can be used to know if there is a single symbol within 'src', and to quickly evaluate its compressibility. If there is an error, the function will return an ErrorCode (which can be tested using FSE_isError()).

The next step is to normalize the frequencies. FSE_normalizeCount() will ensure that sum of frequencies is == 2 ^'tableLog'. It also guarantees a minimum of 1 to any Symbol with frequency >= 1. You can use 'tableLog'==0 to mean "use default tableLog value". If you are unsure of which tableLog value to use, you can ask FSE_optimalTableLog(), which will provide the optimal valid tableLog given sourceSize, maxSymbolValue, and a user-defined maximum (0 means "default").

The result of FSE_normalizeCount() will be saved into a table, called 'normalizedCounter', which is a table of signed short. 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValue+1' cells. The return value is tableLog if everything proceeded as expected. It is 0 if there is a single symbol within distribution. If there is an error (ex: invalid tableLog value), the function will return an ErrorCode (which can be tested using FSE_isError()).

'normalizedCounter' can be saved in a compact manner to a memory area using FSE_writeNCount(). 'buffer' must be already allocated. For guaranteed success, buffer size must be at least FSE_headerBound(). The result of the function is the number of bytes written into 'buffer'. If there is an error, the function will return an ErrorCode (which can be tested using FSE_isError(); ex : buffer size too small).

'normalizedCounter' can then be used to create the compression table 'CTable'. The space required by 'CTable' must be already allocated, using FSE_createCTable(). You can then use FSE_buildCTable() to fill 'CTable'. If there is an error, both functions will return an ErrorCode (which can be tested using FSE_isError()).

'CTable' can then be used to compress 'src', with FSE_compress_usingCTable(). Similar to FSE_count(), the convention is that 'src' is assumed to be a table of char of size 'srcSize' The function returns the size of compressed data (without header), necessarily <= dstCapacity. If it returns '0', compressed data could not fit into 'dst'. If there is an error, the function will return an ErrorCode (which can be tested using FSE_isError()).

FSE_readNCount(): Read compactly saved 'normalizedCounter' from 'rBuffer'.

Returns
: size read from 'rBuffer', or an errorCode, which can be tested using FSE_isError(). maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values

Definition at line 41 of file entropy_common.c.

43 {
44  const BYTE* const istart = (const BYTE*) headerBuffer;
45  const BYTE* const iend = istart + hbSize;
46  const BYTE* ip = istart;
47  int nbBits;
48  int remaining;
49  int threshold;
50  U32 bitStream;
51  int bitCount;
52  unsigned charnum = 0;
53  int previous0 = 0;
54 
55  if (hbSize < 4) {
56  /* This function only works when hbSize >= 4 */
57  char buffer[4];
58  memset(buffer, 0, sizeof(buffer));
59  memcpy(buffer, headerBuffer, hbSize);
60  { size_t const countSize = FSE_readNCount(normalizedCounter, maxSVPtr, tableLogPtr,
61  buffer, sizeof(buffer));
62  if (FSE_isError(countSize)) return countSize;
63  if (countSize > hbSize) return ERROR(corruption_detected);
64  return countSize;
65  } }
66  assert(hbSize >= 4);
67 
68  /* init */
69  memset(normalizedCounter, 0, (*maxSVPtr+1) * sizeof(normalizedCounter[0])); /* all symbols not present in NCount have a frequency of 0 */
70  bitStream = MEM_readLE32(ip);
71  nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
72  if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
73  bitStream >>= 4;
74  bitCount = 4;
75  *tableLogPtr = nbBits;
76  remaining = (1<<nbBits)+1;
77  threshold = 1<<nbBits;
78  nbBits++;
79 
80  while ((remaining>1) & (charnum<=*maxSVPtr)) {
81  if (previous0) {
82  unsigned n0 = charnum;
83  while ((bitStream & 0xFFFF) == 0xFFFF) {
84  n0 += 24;
85  if (ip < iend-5) {
86  ip += 2;
87  bitStream = MEM_readLE32(ip) >> bitCount;
88  } else {
89  bitStream >>= 16;
90  bitCount += 16;
91  } }
92  while ((bitStream & 3) == 3) {
93  n0 += 3;
94  bitStream >>= 2;
95  bitCount += 2;
96  }
97  n0 += bitStream & 3;
98  bitCount += 2;
99  if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
100  while (charnum < n0) normalizedCounter[charnum++] = 0;
101  if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
102  assert((bitCount >> 3) <= 3); /* For first condition to work */
103  ip += bitCount>>3;
104  bitCount &= 7;
105  bitStream = MEM_readLE32(ip) >> bitCount;
106  } else {
107  bitStream >>= 2;
108  } }
109  { int const max = (2*threshold-1) - remaining;
110  int count;
111 
112  if ((bitStream & (threshold-1)) < (U32)max) {
113  count = bitStream & (threshold-1);
114  bitCount += nbBits-1;
115  } else {
116  count = bitStream & (2*threshold-1);
117  if (count >= threshold) count -= max;
118  bitCount += nbBits;
119  }
120 
121  count--; /* extra accuracy */
122  remaining -= count < 0 ? -count : count; /* -1 means +1 */
123  normalizedCounter[charnum++] = (short)count;
124  previous0 = !count;
125  while (remaining < threshold) {
126  nbBits--;
127  threshold >>= 1;
128  }
129 
130  if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
131  ip += bitCount>>3;
132  bitCount &= 7;
133  } else {
134  bitCount -= (int)(8 * (iend - 4 - ip));
135  ip = iend - 4;
136  }
137  bitStream = MEM_readLE32(ip) >> (bitCount & 31);
138  } } /* while ((remaining>1) & (charnum<=*maxSVPtr)) */
139  if (remaining != 1) return ERROR(corruption_detected);
140  if (bitCount > 32) return ERROR(corruption_detected);
141  *maxSVPtr = charnum-1;
142 
143  ip += (bitCount+7)>>3;
144  return ip-istart;
145 }
#define max(a, b)
Definition: svc.c:63
#define ERROR(name)
Definition: error_private.h:53
size_t FSE_readNCount(short *normalizedCounter, unsigned *maxSVPtr, unsigned *tableLogPtr, const void *headerBuffer, size_t hbSize)
GLuint GLuint GLsizei count
Definition: gl.h:1545
MEM_STATIC U32 MEM_readLE32(const void *memPtr)
Definition: mem.h:346
#define assert(x)
Definition: debug.h:53
GLuint buffer
Definition: glext.h:5915
unsigned short(__cdecl typeof(TIFFCurrentDirectory))(struct tiff *)
Definition: typeof.h:94
Definition: dhcpd.h:61
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
unsigned char BYTE
Definition: xxhash.c:193
unsigned FSE_isError(size_t code)
#define memset(x, y, z)
Definition: compat.h:39
unsigned int U32
Definition: xxhash.c:195
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31

Referenced by FSE_decompress_wksp(), FSE_readNCount(), ZSTD_loadCEntropy(), and ZSTD_loadDEntropy().

◆ FSE_versionNumber()

FSE_PUBLIC_API unsigned FSE_versionNumber ( void  )

library version number; to be used when checking dll version

Definition at line 27 of file entropy_common.c.

27 { return FSE_VERSION_NUMBER; }
#define FSE_VERSION_NUMBER
Definition: fse.h:52

◆ FSE_writeNCount()

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

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