ReactOS  0.4.15-dev-321-g2d9b385
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 69 of file fse.h.

◆ FSE_H

#define FSE_H

Definition at line 40 of file fse.h.

◆ FSE_LIB_VERSION

Definition at line 67 of file fse.h.

◆ FSE_PUBLIC_API

#define FSE_PUBLIC_API

Definition at line 59 of file fse.h.

◆ FSE_QUOTE

#define FSE_QUOTE (   str)    #str

Definition at line 68 of file fse.h.

◆ FSE_VERSION_MAJOR

#define FSE_VERSION_MAJOR   0

Definition at line 63 of file fse.h.

◆ FSE_VERSION_MINOR

#define FSE_VERSION_MINOR   9

Definition at line 64 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 72 of file fse.h.

◆ FSE_VERSION_RELEASE

#define FSE_VERSION_RELEASE   0

Definition at line 65 of file fse.h.

◆ FSE_VERSION_STRING

#define FSE_VERSION_STRING   FSE_EXPAND_AND_QUOTE(FSE_LIB_VERSION)

Definition at line 70 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 180 of file fse.h.

◆ FSE_DTable

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

Definition at line 253 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 195 of file fse_compress.c.

196 {
197  FSE_FUNCTION_TYPE* tableSymbol = ExAllocatePoolWithTag(NonPagedPool, sizeof(FSE_FUNCTION_TYPE) * FSE_MAX_TABLESIZE, FSEC_ALLOC_TAG);
198  size_t ret;
199 
200  if (!tableSymbol)
201  return 0;
202 
203  ret = FSE_buildCTable_wksp(ct, normalizedCounter, maxSymbolValue, tableLog, tableSymbol, sizeof(FSE_FUNCTION_TYPE) * FSE_MAX_TABLESIZE);
204 
205  ExFreePool(tableSymbol);
206 
207  return ret;
208 }
size_t FSE_buildCTable_wksp(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
Definition: fse_compress.c:89
#define FSEC_ALLOC_TAG
Definition: fse_compress.c:80
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
int ret
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

◆ 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 97 of file fse_decompress.c.

98 {
99  void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
100  FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr);
101  U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
102 
103  U32 const maxSV1 = maxSymbolValue + 1;
104  U32 const tableSize = 1 << tableLog;
105  U32 highThreshold = tableSize-1;
106 
107  /* Sanity Checks */
108  if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
109  if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
110 
111  /* Init, lay down lowprob symbols */
112  { FSE_DTableHeader DTableH;
113  DTableH.tableLog = (U16)tableLog;
114  DTableH.fastMode = 1;
115  { S16 const largeLimit= (S16)(1 << (tableLog-1));
116  U32 s;
117  for (s=0; s<maxSV1; s++) {
118  if (normalizedCounter[s]==-1) {
119  tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
120  symbolNext[s] = 1;
121  } else {
122  if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
123  symbolNext[s] = normalizedCounter[s];
124  } } }
125  memcpy(dt, &DTableH, sizeof(DTableH));
126  }
127 
128  /* Spread symbols */
129  { U32 const tableMask = tableSize-1;
130  U32 const step = FSE_TABLESTEP(tableSize);
131  U32 s, position = 0;
132  for (s=0; s<maxSV1; s++) {
133  int i;
134  for (i=0; i<normalizedCounter[s]; i++) {
135  tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
136  position = (position + step) & tableMask;
137  while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
138  } }
139  if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
140  }
141 
142  /* Build Decoding table */
143  { U32 u;
144  for (u=0; u<tableSize; u++) {
145  FSE_FUNCTION_TYPE const symbol = (FSE_FUNCTION_TYPE)(tableDecode[u].symbol);
146  U32 const nextState = symbolNext[symbol]++;
147  tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
148  tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
149  } }
150 
151  return 0;
152 }
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:156
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
#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
signed short S16
Definition: mem.h:73
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 741 of file fse_compress.c.

742 {
743  return FSE_compress2(dst, dstCapacity, src, srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG);
744 }
size_t FSE_compress2(void *dst, size_t dstCapacity, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:719
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 719 of file fse_compress.c.

720 {
721  fseWkspMax_t* scratchBuffer;
722  size_t ret;
723 
724  DEBUG_STATIC_ASSERT(sizeof(fseWkspMax_t) >= FSE_WKSP_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)); /* compilation failures here means scratchBuffer is not large enough */
725 
726  if (tableLog > FSE_MAX_TABLELOG)
727  return ERROR(tableLog_tooLarge);
728 
730 
731  if (!scratchBuffer)
732  return 0;
733 
734  ret = FSE_compress_wksp(dst, dstCapacity, src, srcSize, maxSymbolValue, tableLog, scratchBuffer, sizeof(fseWkspMax_t));
735 
736  ExFreePool(scratchBuffer);
737 
738  return ret;
739 }
#define ERROR(name)
Definition: error_private.h:53
#define FSEC_ALLOC_TAG
Definition: fse_compress.c:80
#define DEBUG_STATIC_ASSERT(c)
Definition: debug.h:63
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:667
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
int ret
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

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 645 of file fse_compress.c.

648 {
649  unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
650 
651  if (fast)
652  return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1);
653  else
654  return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0);
655 }
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:586
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 658 of file fse_compress.c.

658 { 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 337 of file fse_compress.c.

338 {
339  size_t size;
340  if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
341  size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32);
343 }
unsigned FSE_CTable
Definition: fse.h:180
#define FSEC_ALLOC_TAG
Definition: fse_compress.c:80
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 86 of file fse_decompress.c.

87 {
88  if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
89  return (FSE_DTable*)ExAllocatePoolWithTag(PagedPool, FSE_DTABLE_SIZE_U32(tableLog) * sizeof (U32), FSED_ALLOC_TAG);
90 }
unsigned FSE_DTable
Definition: fse.h:253
#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 305 of file fse_decompress.c.

306 {
307  DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
308  return FSE_decompress_wksp(dst, dstCapacity, cSrc, cSrcSize, dt, FSE_MAX_TABLELOG);
309 }
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 267 of file fse_decompress.c.

270 {
271  const void* ptr = dt;
272  const FSE_DTableHeader* DTableH = (const FSE_DTableHeader*)ptr;
273  const U32 fastMode = DTableH->fastMode;
274 
275  /* select fast mode (static) */
276  if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
277  return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
278 }
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 345 of file fse_compress.c.

345 { 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 92 of file fse_decompress.c.

93 {
94  ExFreePool(dt);
95 }
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

◆ FSE_getErrorName()

FSE_PUBLIC_API const char* FSE_getErrorName ( size_t  code)

Definition at line 52 of file entropy_common.c.

52 { return ERR_getErrorName(code); }
ERR_STATIC const char * ERR_getErrorName(size_t code)
Definition: error_private.h:67

◆ FSE_isError()

FSE_PUBLIC_API unsigned FSE_isError ( size_t  code)

Definition at line 51 of file entropy_common.c.

51 { return ERR_isError(code); }
ERR_STATIC unsigned ERR_isError(size_t code)
Definition: error_private.h:56

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 218 of file fse_compress.c.

219 {
220  size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3;
221  return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */
222 }

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 467 of file fse_compress.c.

470 {
471  /* Sanity checks */
472  if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
473  if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported size */
474  if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported size */
475  if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */
476 
477  { static U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
478  U64 const scale = 62 - tableLog;
479  U64 const step = ((U64)1<<62) / total; /* <== here, one division ! */
480  U64 const vStep = 1ULL<<(scale-20);
481  int stillToDistribute = 1<<tableLog;
482  unsigned s;
483  unsigned largest=0;
484  short largestP=0;
485  U32 lowThreshold = (U32)(total >> tableLog);
486 
487  for (s=0; s<=maxSymbolValue; s++) {
488  if (count[s] == total) return 0; /* rle special case */
489  if (count[s] == 0) { normalizedCounter[s]=0; continue; }
490  if (count[s] <= lowThreshold) {
491  normalizedCounter[s] = -1;
492  stillToDistribute--;
493  } else {
494  short proba = (short)((count[s]*step) >> scale);
495  if (proba<8) {
496  U64 restToBeat = vStep * rtbTable[proba];
497  proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat;
498  }
499  if (proba > largestP) { largestP=proba; largest=s; }
500  normalizedCounter[s] = proba;
501  stillToDistribute -= proba;
502  } }
503  if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
504  /* corner case, need another normalization method */
505  size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue);
506  if (FSE_isError(errorCode)) return errorCode;
507  }
508  else normalizedCounter[largest] += (short)stillToDistribute;
509  }
510 
511 #if 0
512  { /* Print Table (debug) */
513  U32 s;
514  U32 nTotal = 0;
515  for (s=0; s<=maxSymbolValue; s++)
516  RAWLOG(2, "%3i: %4i \n", s, normalizedCounter[s]);
517  for (s=0; s<=maxSymbolValue; s++)
518  nTotal += abs(normalizedCounter[s]);
519  if (nTotal != (1U<<tableLog))
520  RAWLOG(2, "Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog);
521  getchar();
522  }
523 #endif
524 
525  return tableLog;
526 }
#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:380
#define RAWLOG(l,...)
Definition: debug.h:114
#define FSE_isError
Definition: fse_compress.c:55
#define ULL(a, b)
Definition: format_msg.c:27
static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:348
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
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 371 of file fse_compress.c.

372 {
373  return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
374 }
unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
Definition: fse_compress.c:357

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 61 of file entropy_common.c.

63 {
64  const BYTE* const istart = (const BYTE*) headerBuffer;
65  const BYTE* const iend = istart + hbSize;
66  const BYTE* ip = istart;
67  int nbBits;
68  int remaining;
69  int threshold;
70  U32 bitStream;
71  int bitCount;
72  unsigned charnum = 0;
73  int previous0 = 0;
74 
75  if (hbSize < 4) {
76  /* This function only works when hbSize >= 4 */
77  char buffer[4];
78  memset(buffer, 0, sizeof(buffer));
79  memcpy(buffer, headerBuffer, hbSize);
80  { size_t const countSize = FSE_readNCount(normalizedCounter, maxSVPtr, tableLogPtr,
81  buffer, sizeof(buffer));
82  if (FSE_isError(countSize)) return countSize;
83  if (countSize > hbSize) return ERROR(corruption_detected);
84  return countSize;
85  } }
86  assert(hbSize >= 4);
87 
88  /* init */
89  memset(normalizedCounter, 0, (*maxSVPtr+1) * sizeof(normalizedCounter[0])); /* all symbols not present in NCount have a frequency of 0 */
90  bitStream = MEM_readLE32(ip);
91  nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
92  if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
93  bitStream >>= 4;
94  bitCount = 4;
95  *tableLogPtr = nbBits;
96  remaining = (1<<nbBits)+1;
97  threshold = 1<<nbBits;
98  nbBits++;
99 
100  while ((remaining>1) & (charnum<=*maxSVPtr)) {
101  if (previous0) {
102  unsigned n0 = charnum;
103  while ((bitStream & 0xFFFF) == 0xFFFF) {
104  n0 += 24;
105  if (ip < iend-5) {
106  ip += 2;
107  bitStream = MEM_readLE32(ip) >> bitCount;
108  } else {
109  bitStream >>= 16;
110  bitCount += 16;
111  } }
112  while ((bitStream & 3) == 3) {
113  n0 += 3;
114  bitStream >>= 2;
115  bitCount += 2;
116  }
117  n0 += bitStream & 3;
118  bitCount += 2;
119  if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
120  while (charnum < n0) normalizedCounter[charnum++] = 0;
121  if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
122  assert((bitCount >> 3) <= 3); /* For first condition to work */
123  ip += bitCount>>3;
124  bitCount &= 7;
125  bitStream = MEM_readLE32(ip) >> bitCount;
126  } else {
127  bitStream >>= 2;
128  } }
129  { int const max = (2*threshold-1) - remaining;
130  int count;
131 
132  if ((bitStream & (threshold-1)) < (U32)max) {
133  count = bitStream & (threshold-1);
134  bitCount += nbBits-1;
135  } else {
136  count = bitStream & (2*threshold-1);
137  if (count >= threshold) count -= max;
138  bitCount += nbBits;
139  }
140 
141  count--; /* extra accuracy */
142  remaining -= count < 0 ? -count : count; /* -1 means +1 */
143  normalizedCounter[charnum++] = (short)count;
144  previous0 = !count;
145  while (remaining < threshold) {
146  nbBits--;
147  threshold >>= 1;
148  }
149 
150  if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
151  ip += bitCount>>3;
152  bitCount &= 7;
153  } else {
154  bitCount -= (int)(8 * (iend - 4 - ip));
155  ip = iend - 4;
156  }
157  bitStream = MEM_readLE32(ip) >> (bitCount & 31);
158  } } /* while ((remaining>1) & (charnum<=*maxSVPtr)) */
159  if (remaining != 1) return ERROR(corruption_detected);
160  if (bitCount > 32) return ERROR(corruption_detected);
161  *maxSVPtr = charnum-1;
162 
163  ip += (bitCount+7)>>3;
164  return ip-istart;
165 }
#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:273
#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_buildSeqTable(), ZSTD_loadEntropy(), and ZSTD_loadZstdDictionary().

◆ FSE_versionNumber()

FSE_PUBLIC_API unsigned FSE_versionNumber ( void  )

library version number; to be used when checking dll version

Definition at line 47 of file entropy_common.c.

47 { return FSE_VERSION_NUMBER; }
#define FSE_VERSION_NUMBER
Definition: fse.h:72

◆ 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 320 of file fse_compress.c.

322 {
323  if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported */
324  if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */
325 
326  if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
327  return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
328 
329  return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */);
330 }
#define ERROR(name)
Definition: error_private.h:53
GLuint buffer
Definition: glext.h:5915
static size_t FSE_writeNCount_generic(void *header, size_t headerBufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, unsigned writeIsSafe)
Definition: fse_compress.c:225
size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:218

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