ReactOS 0.4.15-dev-8241-g63935f8
zstd_compress_sequences.c File Reference
Include dependency graph for zstd_compress_sequences.c:

Go to the source code of this file.

Functions

static unsigned ZSTD_getFSEMaxSymbolValue (FSE_CTable const *ctable)
 
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)
 
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)
 
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)
 
FORCE_INLINE_TEMPLATE size_t ZSTD_encodeSequences_body (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)
 
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)
 
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)
 

Variables

static unsigned const kInverseProbabilityLog256 [256]
 

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}
#define RETURN_ERROR(StatusCode)
Definition: Base.h:751
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
UINT op
Definition: effect.c:236
#define assert(x)
Definition: debug.h:53
#define DEBUGLOG(l,...)
Definition: debug.h:106
signed short S16
Definition: mem.h:146
FSE_PUBLIC_API size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:291
FSE_PUBLIC_API size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:438
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
size_t FSE_buildCTable_rle(FSE_CTable *ct, BYTE symbolValue)
Definition: fse_compress.c:534
GLuint GLuint GLsizei GLenum type
Definition: gl.h:1545
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLenum GLenum dst
Definition: glext.h:6340
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
#define max(a, b)
Definition: svc.c:63
unsigned char BYTE
Definition: xxhash.c:193
unsigned int U32
Definition: xxhash.c:195
#define FORWARD_IF_ERROR(err,...)
#define RETURN_ERROR_IF(cond, err,...)
Definition: zstd_internal.h:91
@ set_repeat
@ set_basic
@ set_compressed
@ set_rle
#define MaxSeq

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}
GLdouble s
Definition: gl.h:2039
#define shift
Definition: input.c:1755
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}
static struct msg_sequence * sequences[NUM_MSG_SEQUENCES]
Definition: button.c:54
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_encodeSequences_body()

FORCE_INLINE_TEMPLATE size_t ZSTD_encodeSequences_body ( 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 
)

Definition at line 268 of file zstd_compress_sequences.c.

274{
275 BIT_CStream_t blockStream;
276 FSE_CState_t stateMatchLength;
277 FSE_CState_t stateOffsetBits;
278 FSE_CState_t stateLitLength;
279
281 ERR_isError(BIT_initCStream(&blockStream, dst, dstCapacity)),
282 dstSize_tooSmall, "not enough space remaining");
283 DEBUGLOG(6, "available space for bitstream : %i (dstCapacity=%u)",
284 (int)(blockStream.endPtr - blockStream.startPtr),
285 (unsigned)dstCapacity);
286
287 /* first symbols */
288 FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);
289 FSE_initCState2(&stateOffsetBits, CTable_OffsetBits, ofCodeTable[nbSeq-1]);
290 FSE_initCState2(&stateLitLength, CTable_LitLength, llCodeTable[nbSeq-1]);
291 BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);
292 if (MEM_32bits()) BIT_flushBits(&blockStream);
293 BIT_addBits(&blockStream, sequences[nbSeq-1].matchLength, ML_bits[mlCodeTable[nbSeq-1]]);
294 if (MEM_32bits()) BIT_flushBits(&blockStream);
295 if (longOffsets) {
296 U32 const ofBits = ofCodeTable[nbSeq-1];
297 unsigned const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
298 if (extraBits) {
299 BIT_addBits(&blockStream, sequences[nbSeq-1].offset, extraBits);
300 BIT_flushBits(&blockStream);
301 }
302 BIT_addBits(&blockStream, sequences[nbSeq-1].offset >> extraBits,
303 ofBits - extraBits);
304 } else {
305 BIT_addBits(&blockStream, sequences[nbSeq-1].offset, ofCodeTable[nbSeq-1]);
306 }
307 BIT_flushBits(&blockStream);
308
309 { size_t n;
310 for (n=nbSeq-2 ; n<nbSeq ; n--) { /* intentional underflow */
311 BYTE const llCode = llCodeTable[n];
312 BYTE const ofCode = ofCodeTable[n];
313 BYTE const mlCode = mlCodeTable[n];
314 U32 const llBits = LL_bits[llCode];
315 U32 const ofBits = ofCode;
316 U32 const mlBits = ML_bits[mlCode];
317 DEBUGLOG(6, "encoding: litlen:%2u - matchlen:%2u - offCode:%7u",
318 (unsigned)sequences[n].litLength,
319 (unsigned)sequences[n].matchLength + MINMATCH,
320 (unsigned)sequences[n].offset);
321 /* 32b*/ /* 64b*/
322 /* (7)*/ /* (7)*/
323 FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode); /* 15 */ /* 15 */
324 FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode); /* 24 */ /* 24 */
325 if (MEM_32bits()) BIT_flushBits(&blockStream); /* (7)*/
326 FSE_encodeSymbol(&blockStream, &stateLitLength, llCode); /* 16 */ /* 33 */
327 if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))
328 BIT_flushBits(&blockStream); /* (7)*/
329 BIT_addBits(&blockStream, sequences[n].litLength, llBits);
330 if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);
331 BIT_addBits(&blockStream, sequences[n].matchLength, mlBits);
332 if (MEM_32bits() || (ofBits+mlBits+llBits > 56)) BIT_flushBits(&blockStream);
333 if (longOffsets) {
334 unsigned const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
335 if (extraBits) {
336 BIT_addBits(&blockStream, sequences[n].offset, extraBits);
337 BIT_flushBits(&blockStream); /* (7)*/
338 }
339 BIT_addBits(&blockStream, sequences[n].offset >> extraBits,
340 ofBits - extraBits); /* 31 */
341 } else {
342 BIT_addBits(&blockStream, sequences[n].offset, ofBits); /* 31 */
343 }
344 BIT_flushBits(&blockStream); /* (7)*/
345 DEBUGLOG(7, "remaining space : %i", (int)(blockStream.endPtr - blockStream.ptr));
346 } }
347
348 DEBUGLOG(6, "ZSTD_encodeSequences: flushing ML state with %u bits", stateMatchLength.stateLog);
349 FSE_flushCState(&blockStream, &stateMatchLength);
350 DEBUGLOG(6, "ZSTD_encodeSequences: flushing Off state with %u bits", stateOffsetBits.stateLog);
351 FSE_flushCState(&blockStream, &stateOffsetBits);
352 DEBUGLOG(6, "ZSTD_encodeSequences: flushing LL state with %u bits", stateLitLength.stateLog);
353 FSE_flushCState(&blockStream, &stateLitLength);
354
355 { size_t const streamSize = BIT_closeCStream(&blockStream);
356 RETURN_ERROR_IF(streamSize==0, dstSize_tooSmall, "not enough space");
357 return streamSize;
358 }
359}
#define MIN(x, y)
Definition: rdesktop.h:171
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
Definition: bitstream.h:254
MEM_STATIC void BIT_flushBits(BIT_CStream_t *bitC)
Definition: bitstream.h:239
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity)
Definition: bitstream.h:183
MEM_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
Definition: bitstream.h:198
#define STREAM_ACCUMULATOR_MIN
Definition: bitstream.h:47
MEM_STATIC unsigned MEM_32bits(void)
Definition: mem.h:183
ERR_STATIC unsigned ERR_isError(size_t code)
Definition: error_private.h:56
GLdouble n
Definition: glext.h:7729
GLintptr offset
Definition: glext.h:5920
char * endPtr
Definition: bitstream.h:62
char * ptr
Definition: bitstream.h:61
char * startPtr
Definition: bitstream.h:60
#define MINMATCH
static const U32 ML_bits[MaxML+1]
#define MLFSELog
static const U32 LL_bits[MaxLL+1]
#define LLFSELog
#define OffFSELog

Referenced by ZSTD_encodeSequences_default().

◆ ZSTD_encodeSequences_default()

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

Definition at line 362 of file zstd_compress_sequences.c.

368{
369 return ZSTD_encodeSequences_body(dst, dstCapacity,
370 CTable_MatchLength, mlCodeTable,
371 CTable_OffsetBits, ofCodeTable,
372 CTable_LitLength, llCodeTable,
373 sequences, nbSeq, longOffsets);
374}
FORCE_INLINE_TEMPLATE size_t ZSTD_encodeSequences_body(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_encodeSequences().

◆ ZSTD_entropyCost()

static size_t ZSTD_entropyCost ( unsigned const count,
unsigned const  max,
size_t const  total 
)
static

Returns the cost in bits of encoding the distribution described by count using the entropy bound.

Definition at line 71 of file zstd_compress_sequences.c.

72{
73 unsigned cost = 0;
74 unsigned s;
75 for (s = 0; s <= max; ++s) {
76 unsigned norm = (unsigned)((256 * count[s]) / total);
77 if (count[s] != 0 && norm == 0)
78 norm = 1;
79 assert(count[s] < total);
81 }
82 return cost >> 8;
83}
size_t total
static unsigned(__cdecl *hash_bstr)(bstr_t s)

Referenced by ZSTD_selectEncodingType().

◆ 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}
static _Locale_mask_t ctable[256]
__kernel_size_t size_t
Definition: linux.h:237
#define ERROR(name)
Definition: error_private.h:53
Definition: vj.h:105
static unsigned ZSTD_getFSEMaxSymbolValue(FSE_CTable const *ctable)

Referenced by ZSTD_estimateSubBlockSize_symbolType(), and ZSTD_selectEncodingType().

◆ ZSTD_getFSEMaxSymbolValue()

static unsigned ZSTD_getFSEMaxSymbolValue ( FSE_CTable const ctable)
static

Definition at line 46 of file zstd_compress_sequences.c.

46 {
47 void const* ptr = ctable;
48 U16 const* u16ptr = (U16 const*)ptr;
49 U32 const maxSymbolValue = MEM_read16(u16ptr + 1);
50 return maxSymbolValue;
51}
MEM_STATIC U16 MEM_read16(const void *memPtr)
Definition: mem.h:237
static PVOID ptr
Definition: dispmode.c:27
unsigned short U16
Definition: xxhash.c:194

Referenced by ZSTD_fseBitCost().

◆ ZSTD_NCountCost()

static size_t ZSTD_NCountCost ( unsigned const count,
unsigned const  max,
size_t const  nbSeq,
unsigned const  FSELog 
)
static

Returns the cost in bytes of encoding the normalized count header. Returns an error if any of the helper functions return an error.

Definition at line 57 of file zstd_compress_sequences.c.

59{
60 BYTE wksp[FSE_NCOUNTBOUND];
61 S16 norm[MaxSeq + 1];
62 const U32 tableLog = FSE_optimalTableLog(FSELog, nbSeq, max);
63 FORWARD_IF_ERROR(FSE_normalizeCount(norm, tableLog, count, nbSeq, max), "");
64 return FSE_writeNCount(wksp, sizeof(wksp), norm, max, tableLog);
65}

Referenced by 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}
@ ZSTD_lazy
Definition: zstd.h:254
size_t ZSTD_crossEntropyCost(short const *norm, unsigned accuracyLog, unsigned const *count, unsigned const max)
static size_t ZSTD_entropyCost(unsigned const *count, unsigned const max, size_t const total)
static size_t ZSTD_NCountCost(unsigned const *count, unsigned const max, size_t const nbSeq, unsigned const FSELog)
size_t ZSTD_fseBitCost(FSE_CTable const *ctable, unsigned const *count, unsigned const max)
@ ZSTD_defaultAllowed
@ ZSTD_defaultDisallowed
#define ZSTD_isError
Definition: zstd_internal.h:46
#define ZSTD_STATIC_ASSERT(c)
Definition: zstd_internal.h:45

Referenced by ZSTD_buildSuperBlockEntropy_sequences(), and ZSTD_compressSequences_internal().

Variable Documentation

◆ kInverseProbabilityLog256

unsigned const kInverseProbabilityLog256[256]
static
Initial value:
= {
0, 2048, 1792, 1642, 1536, 1453, 1386, 1329, 1280, 1236, 1197, 1162,
1130, 1100, 1073, 1047, 1024, 1001, 980, 960, 941, 923, 906, 889,
874, 859, 844, 830, 817, 804, 791, 779, 768, 756, 745, 734,
724, 714, 704, 694, 685, 676, 667, 658, 650, 642, 633, 626,
618, 610, 603, 595, 588, 581, 574, 567, 561, 554, 548, 542,
535, 529, 523, 517, 512, 506, 500, 495, 489, 484, 478, 473,
468, 463, 458, 453, 448, 443, 438, 434, 429, 424, 420, 415,
411, 407, 402, 398, 394, 390, 386, 382, 377, 373, 370, 366,
362, 358, 354, 350, 347, 343, 339, 336, 332, 329, 325, 322,
318, 315, 311, 308, 305, 302, 298, 295, 292, 289, 286, 282,
279, 276, 273, 270, 267, 264, 261, 258, 256, 253, 250, 247,
244, 241, 239, 236, 233, 230, 228, 225, 222, 220, 217, 215,
212, 209, 207, 204, 202, 199, 197, 194, 192, 190, 187, 185,
182, 180, 178, 175, 173, 171, 168, 166, 164, 162, 159, 157,
155, 153, 151, 149, 146, 144, 142, 140, 138, 136, 134, 132,
130, 128, 126, 123, 121, 119, 117, 115, 114, 112, 110, 108,
106, 104, 102, 100, 98, 96, 94, 93, 91, 89, 87, 85,
83, 82, 80, 78, 76, 74, 73, 71, 69, 67, 66, 64,
62, 61, 59, 57, 55, 54, 52, 50, 49, 47, 46, 44,
42, 41, 39, 37, 36, 34, 33, 31, 30, 28, 26, 25,
23, 22, 20, 19, 17, 16, 14, 13, 11, 10, 8, 7,
5, 4, 2, 1,
}

-log2(x / 256) lookup table for x in [0, 256). If x == 0: Return 0 Else: Return floor(-log2(x / 256) * 256)

Definition at line 21 of file zstd_compress_sequences.c.

Referenced by ZSTD_crossEntropyCost(), and ZSTD_entropyCost().