ReactOS 0.4.15-dev-8109-gd7be748
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}
#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_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_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)
#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().