ReactOS  0.4.15-dev-5097-g328cc41
zstd_compress_sequences.h File Reference
#include "fse.h"
#include "zstd_internal.h"
Include dependency graph for zstd_compress_sequences.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Enumerations

enum  ZSTD_defaultPolicy_e { ZSTD_defaultDisallowed = 0, ZSTD_defaultAllowed = 1 }
 

Functions

symbolEncodingType_e ZSTD_selectEncodingType (FSE_repeat *repeatMode, unsigned const *count, unsigned const max, size_t const mostFrequent, size_t nbSeq, unsigned const FSELog, FSE_CTable const *prevCTable, short const *defaultNorm, U32 defaultNormLog, ZSTD_defaultPolicy_e const isDefaultAllowed, ZSTD_strategy const strategy)
 
size_t ZSTD_buildCTable (void *dst, size_t dstCapacity, FSE_CTable *nextCTable, U32 FSELog, symbolEncodingType_e type, unsigned *count, U32 max, const BYTE *codeTable, size_t nbSeq, const S16 *defaultNorm, U32 defaultNormLog, U32 defaultMax, const FSE_CTable *prevCTable, size_t prevCTableSize, void *entropyWorkspace, size_t entropyWorkspaceSize)
 
size_t ZSTD_encodeSequences (void *dst, size_t dstCapacity, FSE_CTable const *CTable_MatchLength, BYTE const *mlCodeTable, FSE_CTable const *CTable_OffsetBits, BYTE const *ofCodeTable, FSE_CTable const *CTable_LitLength, BYTE const *llCodeTable, seqDef const *sequences, size_t nbSeq, int longOffsets, int bmi2)
 
size_t ZSTD_fseBitCost (FSE_CTable const *ctable, unsigned const *count, unsigned const max)
 
size_t ZSTD_crossEntropyCost (short const *norm, unsigned accuracyLog, unsigned const *count, unsigned const max)
 

Enumeration Type Documentation

◆ ZSTD_defaultPolicy_e

Enumerator
ZSTD_defaultDisallowed 
ZSTD_defaultAllowed 

Definition at line 17 of file zstd_compress_sequences.h.

Function Documentation

◆ ZSTD_buildCTable()

size_t ZSTD_buildCTable ( void dst,
size_t  dstCapacity,
FSE_CTable nextCTable,
U32  FSELog,
symbolEncodingType_e  type,
unsigned count,
U32  max,
const BYTE codeTable,
size_t  nbSeq,
const S16 defaultNorm,
U32  defaultNormLog,
U32  defaultMax,
const FSE_CTable prevCTable,
size_t  prevCTableSize,
void entropyWorkspace,
size_t  entropyWorkspaceSize 
)

Definition at line 223 of file zstd_compress_sequences.c.

230 {
231  BYTE* op = (BYTE*)dst;
232  const BYTE* const oend = op + dstCapacity;
233  DEBUGLOG(6, "ZSTD_buildCTable (dstCapacity=%u)", (unsigned)dstCapacity);
234 
235  switch (type) {
236  case set_rle:
237  FORWARD_IF_ERROR(FSE_buildCTable_rle(nextCTable, (BYTE)max), "");
238  RETURN_ERROR_IF(dstCapacity==0, dstSize_tooSmall, "not enough space");
239  *op = codeTable[0];
240  return 1;
241  case set_repeat:
242  memcpy(nextCTable, prevCTable, prevCTableSize);
243  return 0;
244  case set_basic:
245  FORWARD_IF_ERROR(FSE_buildCTable_wksp(nextCTable, defaultNorm, defaultMax, defaultNormLog, entropyWorkspace, entropyWorkspaceSize), ""); /* note : could be pre-calculated */
246  return 0;
247  case set_compressed: {
248  S16 norm[MaxSeq + 1];
249  size_t nbSeq_1 = nbSeq;
250  const U32 tableLog = FSE_optimalTableLog(FSELog, nbSeq, max);
251  if (count[codeTable[nbSeq-1]] > 1) {
252  count[codeTable[nbSeq-1]]--;
253  nbSeq_1--;
254  }
255  assert(nbSeq_1 > 1);
256  FORWARD_IF_ERROR(FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max), "");
257  { size_t const NCountSize = FSE_writeNCount(op, oend - op, norm, max, tableLog); /* overflow protected */
258  FORWARD_IF_ERROR(NCountSize, "FSE_writeNCount failed");
259  FORWARD_IF_ERROR(FSE_buildCTable_wksp(nextCTable, norm, max, tableLog, entropyWorkspace, entropyWorkspaceSize), "");
260  return NCountSize;
261  }
262  }
263  default: assert(0); RETURN_ERROR(GENERIC, "impossible to reach");
264  }
265 }
FSE_PUBLIC_API unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:342
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_PUBLIC_API size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:438
#define max(a, b)
Definition: svc.c:63
#define MaxSeq
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
GLuint GLuint GLsizei count
Definition: gl.h:1545
#define assert(x)
Definition: debug.h:53
#define DEBUGLOG(l,...)
Definition: debug.h:106
#define RETURN_ERROR(StatusCode)
Definition: Base.h:751
size_t FSE_buildCTable_rle(FSE_CTable *ct, BYTE symbolValue)
Definition: fse_compress.c:534
#define RETURN_ERROR_IF(cond, err,...)
Definition: zstd_internal.h:91
UINT op
Definition: effect.c:236
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
unsigned char BYTE
Definition: xxhash.c:193
GLenum GLenum dst
Definition: glext.h:6340
#define FORWARD_IF_ERROR(err,...)
FSE_PUBLIC_API size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:291
signed short S16
Definition: mem.h:146
GLuint GLuint GLsizei GLenum type
Definition: gl.h:1545
unsigned int U32
Definition: xxhash.c:195

Referenced by ZSTD_buildSuperBlockEntropy_sequences(), and ZSTD_compressSequences_internal().

◆ ZSTD_crossEntropyCost()

size_t ZSTD_crossEntropyCost ( short const norm,
unsigned  accuracyLog,
unsigned const count,
unsigned const  max 
)

Returns the cost in bits of encoding the distribution in count using the table described by norm. The max symbol support by norm is assumed >= max. norm must be valid for every symbol with non-zero probability in count.

Definition at line 124 of file zstd_compress_sequences.c.

126 {
127  unsigned const shift = 8 - accuracyLog;
128  size_t cost = 0;
129  unsigned s;
130  assert(accuracyLog <= 8);
131  for (s = 0; s <= max; ++s) {
132  unsigned const normAcc = (norm[s] != -1) ? (unsigned)norm[s] : 1;
133  unsigned const norm256 = normAcc << shift;
134  assert(norm256 > 0);
135  assert(norm256 < 256);
136  cost += count[s] * kInverseProbabilityLog256[norm256];
137  }
138  return cost >> 8;
139 }
#define max(a, b)
Definition: svc.c:63
#define shift
Definition: input.c:1756
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
GLuint GLuint GLsizei count
Definition: gl.h:1545
#define assert(x)
Definition: debug.h:53
GLdouble s
Definition: gl.h:2039
static unsigned const kInverseProbabilityLog256[256]

Referenced by ZSTD_estimateSubBlockSize_symbolType(), and ZSTD_selectEncodingType().

◆ ZSTD_encodeSequences()

size_t ZSTD_encodeSequences ( void dst,
size_t  dstCapacity,
FSE_CTable const CTable_MatchLength,
BYTE const mlCodeTable,
FSE_CTable const CTable_OffsetBits,
BYTE const ofCodeTable,
FSE_CTable const CTable_LitLength,
BYTE const llCodeTable,
seqDef const sequences,
size_t  nbSeq,
int  longOffsets,
int  bmi2 
)

Definition at line 396 of file zstd_compress_sequences.c.

402 {
403  DEBUGLOG(5, "ZSTD_encodeSequences: dstCapacity = %u", (unsigned)dstCapacity);
404 #if DYNAMIC_BMI2
405  if (bmi2) {
406  return ZSTD_encodeSequences_bmi2(dst, dstCapacity,
407  CTable_MatchLength, mlCodeTable,
408  CTable_OffsetBits, ofCodeTable,
409  CTable_LitLength, llCodeTable,
410  sequences, nbSeq, longOffsets);
411  }
412 #endif
413  (void)bmi2;
414  return ZSTD_encodeSequences_default(dst, dstCapacity,
415  CTable_MatchLength, mlCodeTable,
416  CTable_OffsetBits, ofCodeTable,
417  CTable_LitLength, llCodeTable,
418  sequences, nbSeq, longOffsets);
419 }
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
Definition: typeof.h:49
#define DEBUGLOG(l,...)
Definition: debug.h:106
static struct msg_sequence * sequences[NUM_MSG_SEQUENCES]
Definition: button.c:54
GLenum GLenum dst
Definition: glext.h:6340
static size_t ZSTD_encodeSequences_default(void *dst, size_t dstCapacity, FSE_CTable const *CTable_MatchLength, BYTE const *mlCodeTable, FSE_CTable const *CTable_OffsetBits, BYTE const *ofCodeTable, FSE_CTable const *CTable_LitLength, BYTE const *llCodeTable, seqDef const *sequences, size_t nbSeq, int longOffsets)

Referenced by ZSTD_compressSequences_internal(), and ZSTD_compressSubBlock_sequences().

◆ ZSTD_fseBitCost()

size_t ZSTD_fseBitCost ( FSE_CTable const ctable,
unsigned const count,
unsigned const  max 
)

Returns the cost in bits of encoding the distribution in count using ctable. Returns an error if ctable cannot represent all the symbols in count.

Definition at line 89 of file zstd_compress_sequences.c.

93 {
94  unsigned const kAccuracyLog = 8;
95  size_t cost = 0;
96  unsigned s;
97  FSE_CState_t cstate;
98  FSE_initCState(&cstate, ctable);
100  DEBUGLOG(5, "Repeat FSE_CTable has maxSymbolValue %u < %u",
102  return ERROR(GENERIC);
103  }
104  for (s = 0; s <= max; ++s) {
105  unsigned const tableLog = cstate.stateLog;
106  unsigned const badCost = (tableLog + 1) << kAccuracyLog;
107  unsigned const bitCost = FSE_bitCost(cstate.symbolTT, tableLog, s, kAccuracyLog);
108  if (count[s] == 0)
109  continue;
110  if (bitCost >= badCost) {
111  DEBUGLOG(5, "Repeat FSE_CTable has Prob[%u] == 0", s);
112  return ERROR(GENERIC);
113  }
114  cost += (size_t)count[s] * bitCost;
115  }
116  return cost >> kAccuracyLog;
117 }
Definition: vj.h:105
#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 DEBUGLOG(l,...)
Definition: debug.h:106
static _Locale_mask_t ctable[256]
__kernel_size_t size_t
Definition: linux.h:237
GLdouble s
Definition: gl.h:2039
static unsigned ZSTD_getFSEMaxSymbolValue(FSE_CTable const *ctable)

Referenced by ZSTD_estimateSubBlockSize_symbolType(), and ZSTD_selectEncodingType().

◆ ZSTD_selectEncodingType()

symbolEncodingType_e ZSTD_selectEncodingType ( FSE_repeat *  repeatMode,
unsigned const count,
unsigned const  max,
size_t const  mostFrequent,
size_t  nbSeq,
unsigned const  FSELog,
FSE_CTable const prevCTable,
short const defaultNorm,
U32  defaultNormLog,
ZSTD_defaultPolicy_e const  isDefaultAllowed,
ZSTD_strategy const  strategy 
)

Definition at line 142 of file zstd_compress_sequences.c.

149 {
151  if (mostFrequent == nbSeq) {
152  *repeatMode = FSE_repeat_none;
153  if (isDefaultAllowed && nbSeq <= 2) {
154  /* Prefer set_basic over set_rle when there are 2 or less symbols,
155  * since RLE uses 1 byte, but set_basic uses 5-6 bits per symbol.
156  * If basic encoding isn't possible, always choose RLE.
157  */
158  DEBUGLOG(5, "Selected set_basic");
159  return set_basic;
160  }
161  DEBUGLOG(5, "Selected set_rle");
162  return set_rle;
163  }
164  if (strategy < ZSTD_lazy) {
165  if (isDefaultAllowed) {
166  size_t const staticFse_nbSeq_max = 1000;
167  size_t const mult = 10 - strategy;
168  size_t const baseLog = 3;
169  size_t const dynamicFse_nbSeq_min = (((size_t)1 << defaultNormLog) * mult) >> baseLog; /* 28-36 for offset, 56-72 for lengths */
170  assert(defaultNormLog >= 5 && defaultNormLog <= 6); /* xx_DEFAULTNORMLOG */
171  assert(mult <= 9 && mult >= 7);
172  if ( (*repeatMode == FSE_repeat_valid)
173  && (nbSeq < staticFse_nbSeq_max) ) {
174  DEBUGLOG(5, "Selected set_repeat");
175  return set_repeat;
176  }
177  if ( (nbSeq < dynamicFse_nbSeq_min)
178  || (mostFrequent < (nbSeq >> (defaultNormLog-1))) ) {
179  DEBUGLOG(5, "Selected set_basic");
180  /* The format allows default tables to be repeated, but it isn't useful.
181  * When using simple heuristics to select encoding type, we don't want
182  * to confuse these tables with dictionaries. When running more careful
183  * analysis, we don't need to waste time checking both repeating tables
184  * and default tables.
185  */
186  *repeatMode = FSE_repeat_none;
187  return set_basic;
188  }
189  }
190  } else {
191  size_t const basicCost = isDefaultAllowed ? ZSTD_crossEntropyCost(defaultNorm, defaultNormLog, count, max) : ERROR(GENERIC);
192  size_t const repeatCost = *repeatMode != FSE_repeat_none ? ZSTD_fseBitCost(prevCTable, count, max) : ERROR(GENERIC);
193  size_t const NCountCost = ZSTD_NCountCost(count, max, nbSeq, FSELog);
194  size_t const compressedCost = (NCountCost << 3) + ZSTD_entropyCost(count, max, nbSeq);
195 
196  if (isDefaultAllowed) {
197  assert(!ZSTD_isError(basicCost));
198  assert(!(*repeatMode == FSE_repeat_valid && ZSTD_isError(repeatCost)));
199  }
200  assert(!ZSTD_isError(NCountCost));
201  assert(compressedCost < ERROR(maxCode));
202  DEBUGLOG(5, "Estimated bit costs: basic=%u\trepeat=%u\tcompressed=%u",
203  (unsigned)basicCost, (unsigned)repeatCost, (unsigned)compressedCost);
204  if (basicCost <= repeatCost && basicCost <= compressedCost) {
205  DEBUGLOG(5, "Selected set_basic");
206  assert(isDefaultAllowed);
207  *repeatMode = FSE_repeat_none;
208  return set_basic;
209  }
210  if (repeatCost <= compressedCost) {
211  DEBUGLOG(5, "Selected set_repeat");
212  assert(!ZSTD_isError(repeatCost));
213  return set_repeat;
214  }
215  assert(compressedCost < basicCost && compressedCost < repeatCost);
216  }
217  DEBUGLOG(5, "Selected set_compressed");
218  *repeatMode = FSE_repeat_check;
219  return set_compressed;
220 }
#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 assert(x)
Definition: debug.h:53
size_t ZSTD_fseBitCost(FSE_CTable const *ctable, unsigned const *count, unsigned const max)
#define ZSTD_STATIC_ASSERT(c)
Definition: zstd_internal.h:45
#define DEBUGLOG(l,...)
Definition: debug.h:106
#define ZSTD_isError
Definition: zstd_internal.h:46
size_t ZSTD_crossEntropyCost(short const *norm, unsigned accuracyLog, unsigned const *count, unsigned const max)
__kernel_size_t size_t
Definition: linux.h:237
static size_t ZSTD_NCountCost(unsigned const *count, unsigned const max, size_t const nbSeq, unsigned const FSELog)
static size_t ZSTD_entropyCost(unsigned const *count, unsigned const max, size_t const total)

Referenced by ZSTD_buildSuperBlockEntropy_sequences(), and ZSTD_compressSequences_internal().