ReactOS  0.4.15-dev-4872-g8a3db97
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
static PVOID ptr
Definition: dispmode.c:27
GLdouble s
Definition: gl.h:2039
unsigned short U16
Definition: xxhash.c:194
unsigned int U32
Definition: xxhash.c:195

◆ 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 }
static PVOID ptr
Definition: dispmode.c:27
unsigned short U16
Definition: xxhash.c:194
unsigned int U32
Definition: xxhash.c:195

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 }
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
#define assert(x)
Definition: debug.h:53
#define DEBUGLOG(l,...)
Definition: debug.h:106
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
static PVOID ptr
Definition: dispmode.c:27
GLdouble s
Definition: gl.h:2039
unsigned short U16
Definition: xxhash.c:194
size_t total
#define memset(x, y, z)
Definition: compat.h:39
unsigned int U32
Definition: xxhash.c:195

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

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_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_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity)
Definition: bitstream.h:183
#define FSE_isError
Definition: fse_compress.c:35
size_t bitContainer
Definition: bitstream.h:58
Definition: dhcpd.h:61
GLenum src
Definition: glext.h:6340
unsigned char BYTE
Definition: xxhash.c:193
GLenum GLenum dst
Definition: glext.h:6340
#define FSE_FLUSHBITS(s)
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
Definition: bitstream.h:254

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 }
size_t FSE_buildCTable_wksp(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
Definition: fse_compress.c:69
#define CHECK_F(f)
Definition: error_private.h:62
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
#define ERROR(name)
Definition: error_private.h:53
GLuint GLuint GLsizei count
Definition: gl.h:1545
#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 HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
Definition: hist.c:166
UINT op
Definition: effect.c:236
size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:291
unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:342
GLenum src
Definition: glext.h:6340
unsigned char BYTE
Definition: xxhash.c:193
GLenum GLenum dst
Definition: glext.h:6340
GLsizei maxCount
Definition: glext.h:6042
size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t total, unsigned maxSymbolValue)
Definition: fse_compress.c:438
signed short S16
Definition: mem.h:146

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 }
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_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 }
#define assert(x)
Definition: debug.h:53
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
unsigned int U32
Definition: xxhash.c:195

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 }
#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_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 }
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
#define ERROR(name)
Definition: error_private.h:53
GLuint GLuint GLsizei count
Definition: gl.h:1545
unsigned short(__cdecl typeof(TIFFCurrentDirectory))(struct tiff *)
Definition: typeof.h:94
#define ULL(a, b)
Definition: format_msg.c:27
GLuint GLuint end
Definition: gl.h:1545
GLdouble s
Definition: gl.h:2039
weight
Definition: sortkey.c:156
unsigned long long U64
Definition: xxhash.c:197
size_t total
unsigned int U32
Definition: xxhash.c:195

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 }
#define assert(x)
Definition: debug.h:53
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:319
unsigned int U32
Definition: xxhash.c:195

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 }
#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().

◆ 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 }
#define max(a, b)
Definition: svc.c:63
#define ERROR(name)
Definition: error_private.h:53
GLuint GLuint GLsizei count
Definition: gl.h:1545
#define U(x)
Definition: wordpad.c:45
#define assert(x)
Definition: debug.h:53
static FILE * out
Definition: regtests2xml.c:44
unsigned char BYTE
Definition: xxhash.c:193
GLuint start
Definition: gl.h:1545
unsigned int U32
Definition: xxhash.c:195

Referenced by FSE_writeNCount().