ReactOS 0.4.15-dev-7897-g78dc504
zstd_compress_internal.h File Reference
#include "zstd_internal.h"
#include "zstd_cwksp.h"
Include dependency graph for zstd_compress_internal.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  ZSTD_prefixDict_s
 
struct  ZSTD_localDict
 
struct  ZSTD_hufCTables_t
 
struct  ZSTD_fseCTables_t
 
struct  ZSTD_entropyCTables_t
 
struct  ZSTD_match_t
 
struct  ZSTD_optimal_t
 
struct  optState_t
 
struct  ZSTD_compressedBlockState_t
 
struct  ZSTD_window_t
 
struct  ZSTD_matchState_t
 
struct  ZSTD_blockState_t
 
struct  ldmEntry_t
 
struct  ldmState_t
 
struct  ldmParams_t
 
struct  rawSeq
 
struct  rawSeqStore_t
 
struct  SeqCollector
 
struct  ZSTD_CCtx_params_s
 
struct  ZSTD_CCtx_s
 
struct  repcodes_s
 

Macros

#define kSearchStrength   8
 
#define HASH_READ_SIZE   8
 
#define ZSTD_DUBT_UNSORTED_MARK
 
#define ZSTD_ROLL_HASH_CHAR_OFFSET   10
 
#define ZSTD_CURRENT_MAX   ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX))
 
#define ZSTD_CHUNKSIZE_MAX
 

Typedefs

typedef struct ZSTD_prefixDict_s ZSTD_prefixDict
 
typedef struct ZSTD_matchState_t ZSTD_matchState_t
 
typedef size_t(* ZSTD_blockCompressor) (ZSTD_matchState_t *bs, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
 
typedef struct repcodes_s repcodes_t
 

Enumerations

enum  ZSTD_compressionStage_e { ZSTDcs_created =0 , ZSTDcs_init , ZSTDcs_ongoing , ZSTDcs_ending }
 
enum  ZSTD_cStreamStage { zcss_init =0 , zcss_load , zcss_flush }
 
enum  ZSTD_OptPrice_e { zop_dynamic =0 , zop_predef }
 
enum  ZSTD_dictTableLoadMethod_e { ZSTD_dtlm_fast , ZSTD_dtlm_full }
 
enum  ZSTD_dictMode_e { ZSTD_noDict = 0 , ZSTD_extDict = 1 , ZSTD_dictMatchState = 2 }
 

Functions

ZSTD_blockCompressor ZSTD_selectBlockCompressor (ZSTD_strategy strat, ZSTD_dictMode_e dictMode)
 
MEM_STATIC U32 ZSTD_LLcode (U32 litLength)
 
MEM_STATIC U32 ZSTD_MLcode (U32 mlBase)
 
MEM_STATIC repcodes_t ZSTD_updateRep (U32 const rep[3], U32 const offset, U32 const ll0)
 
MEM_STATIC int ZSTD_cParam_withinBounds (ZSTD_cParameter cParam, int value)
 
MEM_STATIC size_t ZSTD_noCompressBlock (void *dst, size_t dstCapacity, const void *src, size_t srcSize, U32 lastBlock)
 
MEM_STATIC size_t ZSTD_rleCompressBlock (void *dst, size_t dstCapacity, BYTE src, size_t srcSize, U32 lastBlock)
 
MEM_STATIC size_t ZSTD_minGain (size_t srcSize, ZSTD_strategy strat)
 
MEM_STATIC int ZSTD_disableLiteralsCompression (const ZSTD_CCtx_params *cctxParams)
 
static void ZSTD_safecopyLiterals (BYTE *op, BYTE const *ip, BYTE const *const iend, BYTE const *ilimit_w)
 
HINT_INLINE UNUSED_ATTR void ZSTD_storeSeq (seqStore_t *seqStorePtr, size_t litLength, const BYTE *literals, const BYTE *litLimit, U32 offCode, size_t mlBase)
 
static unsigned ZSTD_NbCommonBytes (size_t val)
 
MEM_STATIC size_t ZSTD_count (const BYTE *pIn, const BYTE *pMatch, const BYTE *const pInLimit)
 
MEM_STATIC size_t ZSTD_count_2segments (const BYTE *ip, const BYTE *match, const BYTE *iEnd, const BYTE *mEnd, const BYTE *iStart)
 
static U32 ZSTD_hash3 (U32 u, U32 h)
 
MEM_STATIC size_t ZSTD_hash3Ptr (const void *ptr, U32 h)
 
static U32 ZSTD_hash4 (U32 u, U32 h)
 
static size_t ZSTD_hash4Ptr (const void *ptr, U32 h)
 
static size_t ZSTD_hash5 (U64 u, U32 h)
 
static size_t ZSTD_hash5Ptr (const void *p, U32 h)
 
static size_t ZSTD_hash6 (U64 u, U32 h)
 
static size_t ZSTD_hash6Ptr (const void *p, U32 h)
 
static size_t ZSTD_hash7 (U64 u, U32 h)
 
static size_t ZSTD_hash7Ptr (const void *p, U32 h)
 
static size_t ZSTD_hash8 (U64 u, U32 h)
 
static size_t ZSTD_hash8Ptr (const void *p, U32 h)
 
MEM_STATIC size_t ZSTD_hashPtr (const void *p, U32 hBits, U32 mls)
 
static U64 ZSTD_ipow (U64 base, U64 exponent)
 
static U64 ZSTD_rollingHash_append (U64 hash, void const *buf, size_t size)
 
MEM_STATIC U64 ZSTD_rollingHash_compute (void const *buf, size_t size)
 
MEM_STATIC U64 ZSTD_rollingHash_primePower (U32 length)
 
MEM_STATIC U64 ZSTD_rollingHash_rotate (U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
 
MEM_STATIC void ZSTD_window_clear (ZSTD_window_t *window)
 
MEM_STATIC U32 ZSTD_window_hasExtDict (ZSTD_window_t const window)
 
MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode (const ZSTD_matchState_t *ms)
 
MEM_STATIC U32 ZSTD_window_needOverflowCorrection (ZSTD_window_t const window, void const *srcEnd)
 
MEM_STATIC U32 ZSTD_window_correctOverflow (ZSTD_window_t *window, U32 cycleLog, U32 maxDist, void const *src)
 
MEM_STATIC void ZSTD_window_enforceMaxDist (ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
 
MEM_STATIC void ZSTD_checkDictValidity (const ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
 
MEM_STATIC void ZSTD_window_init (ZSTD_window_t *window)
 
MEM_STATIC U32 ZSTD_window_update (ZSTD_window_t *window, void const *src, size_t srcSize)
 
MEM_STATIC U32 ZSTD_getLowestMatchIndex (const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
 
MEM_STATIC U32 ZSTD_getLowestPrefixIndex (const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
 
size_t ZSTD_loadCEntropy (ZSTD_compressedBlockState_t *bs, void *workspace, short *offcodeNCount, unsigned *offcodeMaxValue, const void *const dict, size_t dictSize)
 
void ZSTD_reset_compressedBlockState (ZSTD_compressedBlockState_t *bs)
 
ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams (const ZSTD_CCtx_params *CCtxParams, U64 srcSizeHint, size_t dictSize)
 
size_t ZSTD_initCStream_internal (ZSTD_CStream *zcs, const void *dict, size_t dictSize, const ZSTD_CDict *cdict, const ZSTD_CCtx_params *params, unsigned long long pledgedSrcSize)
 
void ZSTD_resetSeqStore (seqStore_t *ssPtr)
 
ZSTD_compressionParameters ZSTD_getCParamsFromCDict (const ZSTD_CDict *cdict)
 
size_t ZSTD_compressBegin_advanced_internal (ZSTD_CCtx *cctx, const void *dict, size_t dictSize, ZSTD_dictContentType_e dictContentType, ZSTD_dictTableLoadMethod_e dtlm, const ZSTD_CDict *cdict, const ZSTD_CCtx_params *params, unsigned long long pledgedSrcSize)
 
size_t ZSTD_compress_advanced_internal (ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize, const ZSTD_CCtx_params *params)
 
size_t ZSTD_writeLastEmptyBlock (void *dst, size_t dstCapacity)
 
size_t ZSTD_referenceExternalSequences (ZSTD_CCtx *cctx, rawSeq *seq, size_t nbSeq)
 
U32 ZSTD_cycleLog (U32 hashLog, ZSTD_strategy strat)
 

Variables

static const U32 prime3bytes = 506832829U
 
static const U32 prime4bytes = 2654435761U
 
static const U64 prime5bytes = 889523592379ULL
 
static const U64 prime6bytes = 227718039650203ULL
 
static const U64 prime7bytes = 58295818150454627ULL
 
static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL
 

Macro Definition Documentation

◆ HASH_READ_SIZE

#define HASH_READ_SIZE   8

Definition at line 36 of file zstd_compress_internal.h.

◆ kSearchStrength

#define kSearchStrength   8

Definition at line 35 of file zstd_compress_internal.h.

◆ ZSTD_CHUNKSIZE_MAX

#define ZSTD_CHUNKSIZE_MAX
Value:
( ((U32)-1) /* Maximum ending current index */ \
- ZSTD_CURRENT_MAX) /* Maximum beginning lowLimit */
unsigned int U32
Definition: xxhash.c:195
#define ZSTD_CURRENT_MAX

Definition at line 703 of file zstd_compress_internal.h.

◆ ZSTD_CURRENT_MAX

#define ZSTD_CURRENT_MAX   ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX))

Definition at line 701 of file zstd_compress_internal.h.

◆ ZSTD_DUBT_UNSORTED_MARK

#define ZSTD_DUBT_UNSORTED_MARK
Value:
1 /* For btlazy2 strategy, index ZSTD_DUBT_UNSORTED_MARK==1 means "unsorted".
It could be confused for a real successor at index "1", if sorted as larger than its predecessor.
It's not a big deal though : candidate will just be sorted again.
Additionally, candidate position 1 will be lost.
But candidate 1 cannot hide a large tree of candidates, so it's a minimal loss.
The benefit is that ZSTD_DUBT_UNSORTED_MARK cannot be mishandled after table re-use with a different strategy.
This constant is required by ZSTD_compressBlock_btlazy2() and ZSTD_reduceTable_internal() */

Definition at line 37 of file zstd_compress_internal.h.

◆ ZSTD_ROLL_HASH_CHAR_OFFSET

#define ZSTD_ROLL_HASH_CHAR_OFFSET   10

Definition at line 650 of file zstd_compress_internal.h.

Typedef Documentation

◆ repcodes_t

◆ ZSTD_blockCompressor

typedef size_t(* ZSTD_blockCompressor) (ZSTD_matchState_t *bs, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

Definition at line 286 of file zstd_compress_internal.h.

◆ ZSTD_matchState_t

◆ ZSTD_prefixDict

Enumeration Type Documentation

◆ ZSTD_compressionStage_e

Enumerator
ZSTDcs_created 
ZSTDcs_init 
ZSTDcs_ongoing 
ZSTDcs_ending 

Definition at line 43 of file zstd_compress_internal.h.

50
51typedef struct ZSTD_prefixDict_s {
52 const void* dict;
53 size_t dictSize;
54 ZSTD_dictContentType_e dictContentType;
56
57typedef struct {
58 void* dictBuffer;
59 void const* dict;
60 size_t dictSize;
61 ZSTD_dictContentType_e dictContentType;
62 ZSTD_CDict* cdict;
64
65typedef struct {
66 U32 CTable[HUF_CTABLE_SIZE_U32(255)];
67 HUF_repeat repeatMode;
69
70typedef struct {
71 FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];
72 FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];
73 FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];
74 FSE_repeat offcode_repeatMode;
75 FSE_repeat matchlength_repeatMode;
76 FSE_repeat litlength_repeatMode;
78
79typedef struct {
83
84typedef struct {
85 U32 off;
86 U32 len;
88
89typedef struct {
90 int price;
91 U32 off;
92 U32 mlen;
93 U32 litlen;
94 U32 rep[ZSTD_REP_NUM];
96
97typedef enum { zop_dynamic=0, zop_predef } ZSTD_OptPrice_e;
98
99typedef struct {
100 /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */
101 unsigned* litFreq; /* table of literals statistics, of size 256 */
102 unsigned* litLengthFreq; /* table of litLength statistics, of size (MaxLL+1) */
103 unsigned* matchLengthFreq; /* table of matchLength statistics, of size (MaxML+1) */
104 unsigned* offCodeFreq; /* table of offCode statistics, of size (MaxOff+1) */
105 ZSTD_match_t* matchTable; /* list of found matches, of size ZSTD_OPT_NUM+1 */
106 ZSTD_optimal_t* priceTable; /* All positions tracked by optimal parser, of size ZSTD_OPT_NUM+1 */
107
108 U32 litSum; /* nb of literals */
109 U32 litLengthSum; /* nb of litLength codes */
110 U32 matchLengthSum; /* nb of matchLength codes */
111 U32 offCodeSum; /* nb of offset codes */
112 U32 litSumBasePrice; /* to compare to log2(litfreq) */
113 U32 litLengthSumBasePrice; /* to compare to log2(llfreq) */
114 U32 matchLengthSumBasePrice;/* to compare to log2(mlfreq) */
115 U32 offCodeSumBasePrice; /* to compare to log2(offreq) */
116 ZSTD_OptPrice_e priceType; /* prices can be determined dynamically, or follow a pre-defined cost structure */
117 const ZSTD_entropyCTables_t* symbolCosts; /* pre-calculated dictionary statistics */
118 ZSTD_literalCompressionMode_e literalCompressionMode;
119} optState_t;
120
121typedef struct {
122 ZSTD_entropyCTables_t entropy;
123 U32 rep[ZSTD_REP_NUM];
125
126typedef struct {
127 BYTE const* nextSrc; /* next block here to continue on current prefix */
128 BYTE const* base; /* All regular indexes relative to this position */
129 BYTE const* dictBase; /* extDict indexes relative to this position */
130 U32 dictLimit; /* below that point, need extDict */
131 U32 lowLimit; /* below that point, no more valid data */
133
135struct ZSTD_matchState_t {
136 ZSTD_window_t window; /* State for window round buffer management */
137 U32 loadedDictEnd; /* index of end of dictionary, within context's referential.
138 * When loadedDictEnd != 0, a dictionary is in use, and still valid.
139 * This relies on a mechanism to set loadedDictEnd=0 when dictionary is no longer within distance.
140 * Such mechanism is provided within ZSTD_window_enforceMaxDist() and ZSTD_checkDictValidity().
141 * When dict referential is copied into active context (i.e. not attached),
142 * loadedDictEnd == dictSize, since referential starts from zero.
143 */
144 U32 nextToUpdate; /* index from which to continue table update */
145 U32 hashLog3; /* dispatch table for matches of len==3 : larger == faster, more memory */
146 U32* hashTable;
149 optState_t opt; /* optimal parser state */
151 ZSTD_compressionParameters cParams;
152};
153
154typedef struct {
155 ZSTD_compressedBlockState_t* prevCBlock;
156 ZSTD_compressedBlockState_t* nextCBlock;
157 ZSTD_matchState_t matchState;
159
160typedef struct {
161 U32 offset;
163} ldmEntry_t;
164
165typedef struct {
166 ZSTD_window_t window; /* State for the window round buffer management */
167 ldmEntry_t* hashTable;
168 U32 loadedDictEnd;
169 BYTE* bucketOffsets; /* Next position in bucket to insert entry */
170 U64 hashPower; /* Used to compute the rolling hash.
171 * Depends on ldmParams.minMatchLength */
172} ldmState_t;
173
174typedef struct {
175 U32 enableLdm; /* 1 if enable long distance matching */
176 U32 hashLog; /* Log size of hashTable */
177 U32 bucketSizeLog; /* Log bucket size for collision resolution, at most 8 */
178 U32 minMatchLength; /* Minimum match length */
179 U32 hashRateLog; /* Log number of entries to skip */
180 U32 windowLog; /* Window log for the LDM */
182
183typedef struct {
184 U32 offset;
185 U32 litLength;
186 U32 matchLength;
187} rawSeq;
188
189typedef struct {
190 rawSeq* seq; /* The start of the sequences */
191 size_t pos; /* The position where reading stopped. <= size. */
192 size_t size; /* The number of sequences. <= capacity. */
193 size_t capacity; /* The capacity starting from `seq` pointer */
195
196typedef struct {
197 int collectSequences;
198 ZSTD_Sequence* seqStart;
199 size_t seqIndex;
200 size_t maxSequences;
202
203struct ZSTD_CCtx_params_s {
204 ZSTD_format_e format;
205 ZSTD_compressionParameters cParams;
206 ZSTD_frameParameters fParams;
207
209 int forceWindow; /* force back-references to respect limit of
210 * 1<<wLog, even for dictionary */
211 size_t targetCBlockSize; /* Tries to fit compressed block size to be around targetCBlockSize.
212 * No target when targetCBlockSize == 0.
213 * There is no guarantee on compressed block size */
214 int srcSizeHint; /* User's best guess of source size.
215 * Hint is not valid when srcSizeHint == 0.
216 * There is no guarantee that hint is close to actual source size */
217
218 ZSTD_dictAttachPref_e attachDictPref;
219 ZSTD_literalCompressionMode_e literalCompressionMode;
220
221 /* Multithreading: used to pass parameters to mtctx */
222 int nbWorkers;
223 size_t jobSize;
224 int overlapLog;
225 int rsyncable;
226
227 /* Long distance matching parameters */
229
230 /* Internal use, for createCCtxParams() and freeCCtxParams() only */
231 ZSTD_customMem customMem;
232}; /* typedef'd to ZSTD_CCtx_params within "zstd.h" */
233
234struct ZSTD_CCtx_s {
236 int cParamsChanged; /* == 1 if cParams(except wlog) or compression level are changed in requestedParams. Triggers transmission of new params to ZSTDMT (if available) then reset to 0. */
237 int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
238 ZSTD_CCtx_params requestedParams;
239 ZSTD_CCtx_params appliedParams;
240 U32 dictID;
241
242 ZSTD_cwksp workspace; /* manages buffer for dynamic allocations */
243 size_t blockSize;
244 unsigned long long pledgedSrcSizePlusOne; /* this way, 0 (default) == unknown */
245 unsigned long long consumedSrcSize;
246 unsigned long long producedCSize;
248 ZSTD_customMem customMem;
249 size_t staticSize;
251 int isFirstBlock;
252 int initialized;
253
254 seqStore_t seqStore; /* sequences storage ptrs */
255 ldmState_t ldmState; /* long distance matching state */
256 rawSeq* ldmSequences; /* Storage for the ldm output sequences */
257 size_t maxNbLdmSequences;
258 rawSeqStore_t externSeqStore; /* Mutable reference to external sequences */
260 U32* entropyWorkspace; /* entropy workspace of HUF_WORKSPACE_SIZE bytes */
261
262 /* streaming */
263 char* inBuff;
264 size_t inBuffSize;
265 size_t inToCompress;
266 size_t inBuffPos;
267 size_t inBuffTarget;
268 char* outBuff;
269 size_t outBuffSize;
270 size_t outBuffContentSize;
271 size_t outBuffFlushedSize;
274
275 /* Dictionary */
277 const ZSTD_CDict* cdict;
278 ZSTD_prefixDict prefixDict; /* single-usage dictionary */
279
280 /* Multi-threading */
281#ifdef ZSTD_MULTITHREAD
282 ZSTDMT_CCtx* mtctx;
283#endif
284};
285
287
288typedef enum { ZSTD_noDict = 0, ZSTD_extDict = 1, ZSTD_dictMatchState = 2 } ZSTD_dictMode_e;
289
290
291typedef size_t (*ZSTD_blockCompressor) (
293 void const* src, size_t srcSize);
295
296
297MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
298{
299 static const BYTE LL_Code[64] = { 0, 1, 2, 3, 4, 5, 6, 7,
300 8, 9, 10, 11, 12, 13, 14, 15,
301 16, 16, 17, 17, 18, 18, 19, 19,
302 20, 20, 20, 20, 21, 21, 21, 21,
303 22, 22, 22, 22, 22, 22, 22, 22,
304 23, 23, 23, 23, 23, 23, 23, 23,
305 24, 24, 24, 24, 24, 24, 24, 24,
306 24, 24, 24, 24, 24, 24, 24, 24 };
307 static const U32 LL_deltaCode = 19;
308 return (litLength > 63) ? ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
309}
310
311/* ZSTD_MLcode() :
312 * note : mlBase = matchLength - MINMATCH;
313 * because it's the format it's stored in seqStore->sequences */
315{
316 static const BYTE ML_Code[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
317 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
318 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
319 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
320 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
321 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
322 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
323 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
324 static const U32 ML_deltaCode = 36;
325 return (mlBase > 127) ? ZSTD_highbit32(mlBase) + ML_deltaCode : ML_Code[mlBase];
326}
327
328typedef struct repcodes_s {
329 U32 rep[3];
330} repcodes_t;
331
332MEM_STATIC repcodes_t ZSTD_updateRep(U32 const rep[3], U32 const offset, U32 const ll0)
333{
334 repcodes_t newReps;
335 if (offset >= ZSTD_REP_NUM) { /* full offset */
336 newReps.rep[2] = rep[1];
337 newReps.rep[1] = rep[0];
338 newReps.rep[0] = offset - ZSTD_REP_MOVE;
339 } else { /* repcode */
340 U32 const repCode = offset + ll0;
341 if (repCode > 0) { /* note : if repCode==0, no change */
342 U32 const currentOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode];
343 newReps.rep[2] = (repCode >= 2) ? rep[1] : rep[2];
344 newReps.rep[1] = rep[0];
345 newReps.rep[0] = currentOffset;
346 } else { /* repCode == 0 */
347 memcpy(&newReps, rep, sizeof(newReps));
348 }
349 }
350 return newReps;
351}
352
353/* ZSTD_cParam_withinBounds:
354 * @return 1 if value is within cParam bounds,
355 * 0 otherwise */
357{
358 ZSTD_bounds const bounds = ZSTD_cParam_getBounds(cParam);
359 if (ZSTD_isError(bounds.error)) return 0;
360 if (value < bounds.lowerBound) return 0;
361 if (value > bounds.upperBound) return 0;
362 return 1;
363}
364
365/* ZSTD_noCompressBlock() :
366 * Writes uncompressed block to dst buffer from given src.
367 * Returns the size of the block */
368MEM_STATIC size_t ZSTD_noCompressBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize, U32 lastBlock)
369{
370 U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(srcSize << 3);
371 RETURN_ERROR_IF(srcSize + ZSTD_blockHeaderSize > dstCapacity,
372 dstSize_tooSmall, "dst buf too small for uncompressed block");
373 MEM_writeLE24(dst, cBlockHeader24);
374 memcpy((BYTE*)dst + ZSTD_blockHeaderSize, src, srcSize);
375 return ZSTD_blockHeaderSize + srcSize;
376}
377
378MEM_STATIC size_t ZSTD_rleCompressBlock (void* dst, size_t dstCapacity, BYTE src, size_t srcSize, U32 lastBlock)
379{
380 BYTE* const op = (BYTE*)dst;
381 U32 const cBlockHeader = lastBlock + (((U32)bt_rle)<<1) + (U32)(srcSize << 3);
382 RETURN_ERROR_IF(dstCapacity < 4, dstSize_tooSmall, "");
383 MEM_writeLE24(op, cBlockHeader);
384 op[3] = src;
385 return 4;
386}
387
388
389/* ZSTD_minGain() :
390 * minimum compression required
391 * to generate a compress block or a compressed literals section.
392 * note : use same formula for both situations */
393MEM_STATIC size_t ZSTD_minGain(size_t srcSize, ZSTD_strategy strat)
394{
395 U32 const minlog = (strat>=ZSTD_btultra) ? (U32)(strat) - 1 : 6;
398 return (srcSize >> minlog) + 2;
399}
400
401MEM_STATIC int ZSTD_disableLiteralsCompression(const ZSTD_CCtx_params* cctxParams)
402{
403 switch (cctxParams->literalCompressionMode) {
404 case ZSTD_lcm_huffman:
405 return 0;
406 case ZSTD_lcm_uncompressed:
407 return 1;
408 default:
409 assert(0 /* impossible: pre-validated */);
410 /* fall-through */
411 case ZSTD_lcm_auto:
412 return (cctxParams->cParams.strategy == ZSTD_fast) && (cctxParams->cParams.targetLength > 0);
413 }
414}
415
421static void ZSTD_safecopyLiterals(BYTE* op, BYTE const* ip, BYTE const* const iend, BYTE const* ilimit_w) {
422 assert(iend > ilimit_w);
423 if (ip <= ilimit_w) {
424 ZSTD_wildcopy(op, ip, ilimit_w - ip, ZSTD_no_overlap);
425 op += ilimit_w - ip;
426 ip = ilimit_w;
427 }
428 while (ip < iend) *op++ = *ip++;
429}
430
438void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const BYTE* literals, const BYTE* litLimit, U32 offCode, size_t mlBase)
439{
440 BYTE const* const litLimit_w = litLimit - WILDCOPY_OVERLENGTH;
441 BYTE const* const litEnd = literals + litLength;
442#if defined(DEBUGLEVEL) && (DEBUGLEVEL >= 6)
443 static const BYTE* g_start = NULL;
444 if (g_start==NULL) g_start = (const BYTE*)literals; /* note : index only works for compression within a single segment */
445 { U32 const pos = (U32)((const BYTE*)literals - g_start);
446 DEBUGLOG(6, "Cpos%7u :%3u literals, match%4u bytes at offCode%7u",
447 pos, (U32)litLength, (U32)mlBase+MINMATCH, (U32)offCode);
448 }
449#endif
450 assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq);
451 /* copy Literals */
452 assert(seqStorePtr->maxNbLit <= 128 KB);
453 assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit);
454 assert(literals + litLength <= litLimit);
455 if (litEnd <= litLimit_w) {
456 /* Common case we can use wildcopy.
457 * First copy 16 bytes, because literals are likely short.
458 */
460 ZSTD_copy16(seqStorePtr->lit, literals);
461 if (litLength > 16) {
462 ZSTD_wildcopy(seqStorePtr->lit+16, literals+16, (ptrdiff_t)litLength-16, ZSTD_no_overlap);
463 }
464 } else {
465 ZSTD_safecopyLiterals(seqStorePtr->lit, literals, litEnd, litLimit_w);
466 }
467 seqStorePtr->lit += litLength;
468
469 /* literal Length */
470 if (litLength>0xFFFF) {
471 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
472 seqStorePtr->longLengthID = 1;
473 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
474 }
475 seqStorePtr->sequences[0].litLength = (U16)litLength;
476
477 /* match offset */
478 seqStorePtr->sequences[0].offset = offCode + 1;
479
480 /* match Length */
481 if (mlBase>0xFFFF) {
482 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
483 seqStorePtr->longLengthID = 2;
484 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
485 }
486 seqStorePtr->sequences[0].matchLength = (U16)mlBase;
487
488 seqStorePtr->sequences++;
489}
490
491
492/*-*************************************
493* Match length counter
494***************************************/
495static unsigned ZSTD_NbCommonBytes (size_t val)
496{
497 if (MEM_isLittleEndian()) {
498 if (MEM_64bits()) {
499# if defined(_MSC_VER) && defined(_WIN64)
500 unsigned long r = 0;
501 return _BitScanForward64( &r, (U64)val ) ? (unsigned)(r >> 3) : 0;
502# elif defined(__GNUC__) && (__GNUC__ >= 4)
503 return (__builtin_ctzll((U64)val) >> 3);
504# else
505 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
506 0, 3, 1, 3, 1, 4, 2, 7,
507 0, 2, 3, 6, 1, 5, 3, 5,
508 1, 3, 4, 4, 2, 5, 6, 7,
509 7, 0, 1, 2, 3, 3, 4, 6,
510 2, 6, 5, 5, 3, 4, 5, 6,
511 7, 1, 2, 4, 6, 4, 4, 5,
512 7, 2, 6, 5, 7, 6, 7, 7 };
513 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
514# endif
515 } else { /* 32 bits */
516# if defined(_MSC_VER)
517 unsigned long r=0;
518 return _BitScanForward( &r, (U32)val ) ? (unsigned)(r >> 3) : 0;
519# elif defined(__GNUC__) && (__GNUC__ >= 3)
520 return (__builtin_ctz((U32)val) >> 3);
521# else
522 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
523 3, 2, 2, 1, 3, 2, 0, 1,
524 3, 3, 1, 2, 2, 2, 2, 0,
525 3, 1, 2, 0, 1, 0, 1, 1 };
526 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
527# endif
528 }
529 } else { /* Big Endian CPU */
530 if (MEM_64bits()) {
531# if defined(_MSC_VER) && defined(_WIN64)
532 unsigned long r = 0;
533 return _BitScanReverse64( &r, val ) ? (unsigned)(r >> 3) : 0;
534# elif defined(__GNUC__) && (__GNUC__ >= 4)
535 return (__builtin_clzll(val) >> 3);
536# else
537 unsigned r;
538 const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */
539 if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
540 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
541 r += (!val);
542 return r;
543# endif
544 } else { /* 32 bits */
545# if defined(_MSC_VER)
546 unsigned long r = 0;
547 return _BitScanReverse( &r, (unsigned long)val ) ? (unsigned)(r >> 3) : 0;
548# elif defined(__GNUC__) && (__GNUC__ >= 3)
549 return (__builtin_clz((U32)val) >> 3);
550# else
551 unsigned r;
552 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
553 r += (!val);
554 return r;
555# endif
556 } }
557}
558
559
560MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
561{
562 const BYTE* const pStart = pIn;
563 const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
564
565 if (pIn < pInLoopLimit) {
566 { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
567 if (diff) return ZSTD_NbCommonBytes(diff); }
568 pIn+=sizeof(size_t); pMatch+=sizeof(size_t);
569 while (pIn < pInLoopLimit) {
570 size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
571 if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
572 pIn += ZSTD_NbCommonBytes(diff);
573 return (size_t)(pIn - pStart);
574 } }
575 if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
576 if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
577 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
578 return (size_t)(pIn - pStart);
579}
580
585MEM_STATIC size_t
586ZSTD_count_2segments(const BYTE* ip, const BYTE* match,
587 const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
588{
589 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
590 size_t const matchLength = ZSTD_count(ip, match, vEnd);
591 if (match + matchLength != mEnd) return matchLength;
592 DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength);
593 DEBUGLOG(7, "distance from match beginning to end dictionary = %zi", mEnd - match);
594 DEBUGLOG(7, "distance from current pos to end buffer = %zi", iEnd - ip);
595 DEBUGLOG(7, "next byte : ip==%02X, istart==%02X", ip[matchLength], *iStart);
596 DEBUGLOG(7, "final match length = %zu", matchLength + ZSTD_count(ip+matchLength, iStart, iEnd));
597 return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
598}
599
600
601/*-*************************************
602 * Hashes
603 ***************************************/
604static const U32 prime3bytes = 506832829U;
605static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; }
606MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
607
608static const U32 prime4bytes = 2654435761U;
609static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
610static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
611
612static const U64 prime5bytes = 889523592379ULL;
613static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h)) ; }
614static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
615
616static const U64 prime6bytes = 227718039650203ULL;
617static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; }
618static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
619
620static const U64 prime7bytes = 58295818150454627ULL;
621static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h)) ; }
622static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
623
624static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
625static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
626static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
627
628MEM_STATIC size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
629{
630 switch(mls)
631 {
632 default:
633 case 4: return ZSTD_hash4Ptr(p, hBits);
634 case 5: return ZSTD_hash5Ptr(p, hBits);
635 case 6: return ZSTD_hash6Ptr(p, hBits);
636 case 7: return ZSTD_hash7Ptr(p, hBits);
637 case 8: return ZSTD_hash8Ptr(p, hBits);
638 }
639}
640
644static U64 ZSTD_ipow(U64 base, U64 exponent)
645{
646 U64 power = 1;
647 while (exponent) {
648 if (exponent & 1) power *= base;
649 exponent >>= 1;
650 base *= base;
651 }
652 return power;
653}
654
655#define ZSTD_ROLL_HASH_CHAR_OFFSET 10
656
660static U64 ZSTD_rollingHash_append(U64 hash, void const* buf, size_t size)
661{
662 BYTE const* istart = (BYTE const*)buf;
663 size_t pos;
664 for (pos = 0; pos < size; ++pos) {
665 hash *= prime8bytes;
667 }
668 return hash;
669}
670
675{
676 return ZSTD_rollingHash_append(0, buf, size);
677}
678
684{
685 return ZSTD_ipow(prime8bytes, length - 1);
686}
687
691MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
692{
693 hash -= (toRemove + ZSTD_ROLL_HASH_CHAR_OFFSET) * primePower;
694 hash *= prime8bytes;
696 return hash;
697}
698
699/*-*************************************
700* Round buffer management
701***************************************/
702#if (ZSTD_WINDOWLOG_MAX_64 > 31)
703# error "ZSTD_WINDOWLOG_MAX is too large : would overflow ZSTD_CURRENT_MAX"
704#endif
705/* Max current allowed */
706#define ZSTD_CURRENT_MAX ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX))
707/* Maximum chunk size before overflow correction needs to be called again */
708#define ZSTD_CHUNKSIZE_MAX \
709 ( ((U32)-1) /* Maximum ending current index */ \
710 - ZSTD_CURRENT_MAX) /* Maximum beginning lowLimit */
711
717{
718 size_t const endT = (size_t)(window->nextSrc - window->base);
719 U32 const end = (U32)endT;
720
721 window->lowLimit = end;
722 window->dictLimit = end;
723}
724
730{
731 return window.lowLimit < window.dictLimit;
732}
733
740{
741 return ZSTD_window_hasExtDict(ms->window) ?
743 ms->dictMatchState != NULL ?
746}
747
754 void const* srcEnd)
755{
756 U32 const current = (U32)((BYTE const*)srcEnd - window.base);
757 return current > ZSTD_CURRENT_MAX;
758}
759
771 U32 maxDist, void const* src)
772{
773 /* preemptive overflow correction:
774 * 1. correction is large enough:
775 * lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog
776 * 1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog
777 *
778 * current - newCurrent
779 * > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog)
780 * > (3<<29) - (1<<chainLog)
781 * > (3<<29) - (1<<30) (NOTE: chainLog <= 30)
782 * > 1<<29
783 *
784 * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow:
785 * After correction, current is less than (1<<chainLog + 1<<windowLog).
786 * In 64-bit mode we are safe, because we have 64-bit ptrdiff_t.
787 * In 32-bit mode we are safe, because (chainLog <= 29), so
788 * ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32.
789 * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32:
790 * windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32.
791 */
792 U32 const cycleMask = (1U << cycleLog) - 1;
793 U32 const current = (U32)((BYTE const*)src - window->base);
794 U32 const currentCycle0 = current & cycleMask;
795 /* Exclude zero so that newCurrent - maxDist >= 1. */
796 U32 const currentCycle1 = currentCycle0 == 0 ? (1U << cycleLog) : currentCycle0;
797 U32 const newCurrent = currentCycle1 + maxDist;
798 U32 const correction = current - newCurrent;
799 assert((maxDist & cycleMask) == 0);
800 assert(current > newCurrent);
801 /* Loose bound, should be around 1<<29 (see above) */
802 assert(correction > 1<<28);
803
804 window->base += correction;
805 window->dictBase += correction;
806 if (window->lowLimit <= correction) window->lowLimit = 1;
807 else window->lowLimit -= correction;
808 if (window->dictLimit <= correction) window->dictLimit = 1;
809 else window->dictLimit -= correction;
810
811 /* Ensure we can still reference the full window. */
812 assert(newCurrent >= maxDist);
813 assert(newCurrent - maxDist >= 1);
814 /* Ensure that lowLimit and dictLimit didn't underflow. */
815 assert(window->lowLimit <= newCurrent);
816 assert(window->dictLimit <= newCurrent);
817
818 DEBUGLOG(4, "Correction of 0x%x bytes to lowLimit=0x%x", correction,
819 window->lowLimit);
820 return correction;
821}
822
846MEM_STATIC void
848 const void* blockEnd,
849 U32 maxDist,
850 U32* loadedDictEndPtr,
851 const ZSTD_matchState_t** dictMatchStatePtr)
852{
853 U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
854 U32 const loadedDictEnd = (loadedDictEndPtr != NULL) ? *loadedDictEndPtr : 0;
855 DEBUGLOG(5, "ZSTD_window_enforceMaxDist: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
856 (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd);
857
858 /* - When there is no dictionary : loadedDictEnd == 0.
859 In which case, the test (blockEndIdx > maxDist) is merely to avoid
860 overflowing next operation `newLowLimit = blockEndIdx - maxDist`.
861 - When there is a standard dictionary :
862 Index referential is copied from the dictionary,
863 which means it starts from 0.
864 In which case, loadedDictEnd == dictSize,
865 and it makes sense to compare `blockEndIdx > maxDist + dictSize`
866 since `blockEndIdx` also starts from zero.
867 - When there is an attached dictionary :
868 loadedDictEnd is expressed within the referential of the context,
869 so it can be directly compared against blockEndIdx.
870 */
871 if (blockEndIdx > maxDist + loadedDictEnd) {
872 U32 const newLowLimit = blockEndIdx - maxDist;
873 if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit;
874 if (window->dictLimit < window->lowLimit) {
875 DEBUGLOG(5, "Update dictLimit to match lowLimit, from %u to %u",
876 (unsigned)window->dictLimit, (unsigned)window->lowLimit);
877 window->dictLimit = window->lowLimit;
878 }
879 /* On reaching window size, dictionaries are invalidated */
880 if (loadedDictEndPtr) *loadedDictEndPtr = 0;
881 if (dictMatchStatePtr) *dictMatchStatePtr = NULL;
882 }
883}
884
885/* Similar to ZSTD_window_enforceMaxDist(),
886 * but only invalidates dictionary
887 * when input progresses beyond window size.
888 * assumption : loadedDictEndPtr and dictMatchStatePtr are valid (non NULL)
889 * loadedDictEnd uses same referential as window->base
890 * maxDist is the window size */
891MEM_STATIC void
893 const void* blockEnd,
894 U32 maxDist,
895 U32* loadedDictEndPtr,
896 const ZSTD_matchState_t** dictMatchStatePtr)
897{
898 assert(loadedDictEndPtr != NULL);
899 assert(dictMatchStatePtr != NULL);
900 { U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
901 U32 const loadedDictEnd = *loadedDictEndPtr;
902 DEBUGLOG(5, "ZSTD_checkDictValidity: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
903 (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd);
904 assert(blockEndIdx >= loadedDictEnd);
905
906 if (blockEndIdx > loadedDictEnd + maxDist) {
907 /* On reaching window size, dictionaries are invalidated.
908 * For simplification, if window size is reached anywhere within next block,
909 * the dictionary is invalidated for the full block.
910 */
911 DEBUGLOG(6, "invalidating dictionary for current block (distance > windowSize)");
912 *loadedDictEndPtr = 0;
913 *dictMatchStatePtr = NULL;
914 } else {
915 if (*loadedDictEndPtr != 0) {
916 DEBUGLOG(6, "dictionary considered valid for current block");
917 } } }
918}
919
921 memset(window, 0, sizeof(*window));
922 window->base = (BYTE const*)"";
923 window->dictBase = (BYTE const*)"";
924 window->dictLimit = 1; /* start from 1, so that 1st position is valid */
925 window->lowLimit = 1; /* it ensures first and later CCtx usages compress the same */
926 window->nextSrc = window->base + 1; /* see issue #1241 */
927}
928
937 void const* src, size_t srcSize)
938{
939 BYTE const* const ip = (BYTE const*)src;
940 U32 contiguous = 1;
941 DEBUGLOG(5, "ZSTD_window_update");
942 if (srcSize == 0)
943 return contiguous;
944 assert(window->base != NULL);
945 assert(window->dictBase != NULL);
946 /* Check if blocks follow each other */
947 if (src != window->nextSrc) {
948 /* not contiguous */
949 size_t const distanceFromBase = (size_t)(window->nextSrc - window->base);
950 DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit);
951 window->lowLimit = window->dictLimit;
952 assert(distanceFromBase == (size_t)(U32)distanceFromBase); /* should never overflow */
953 window->dictLimit = (U32)distanceFromBase;
954 window->dictBase = window->base;
955 window->base = ip - distanceFromBase;
956 /* ms->nextToUpdate = window->dictLimit; */
957 if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit; /* too small extDict */
958 contiguous = 0;
959 }
960 window->nextSrc = ip + srcSize;
961 /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
962 if ( (ip+srcSize > window->dictBase + window->lowLimit)
963 & (ip < window->dictBase + window->dictLimit)) {
964 ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase;
965 U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)window->dictLimit) ? window->dictLimit : (U32)highInputIdx;
966 window->lowLimit = lowLimitMax;
967 DEBUGLOG(5, "Overlapping extDict and input : new lowLimit = %u", window->lowLimit);
968 }
969 return contiguous;
970}
971
976{
977 U32 const maxDistance = 1U << windowLog;
978 U32 const lowestValid = ms->window.lowLimit;
979 U32 const withinWindow = (current - lowestValid > maxDistance) ? current - maxDistance : lowestValid;
980 U32 const isDictionary = (ms->loadedDictEnd != 0);
981 U32 const matchLowest = isDictionary ? lowestValid : withinWindow;
982 return matchLowest;
983}
984
989{
990 U32 const maxDistance = 1U << windowLog;
991 U32 const lowestValid = ms->window.dictLimit;
992 U32 const withinWindow = (current - lowestValid > maxDistance) ? current - maxDistance : lowestValid;
993 U32 const isDictionary = (ms->loadedDictEnd != 0);
994 U32 const matchLowest = isDictionary ? lowestValid : withinWindow;
995 return matchLowest;
996}
997
998
999
1000/* debug functions */
1001#if (DEBUGLEVEL>=2)
1002
1003MEM_STATIC double ZSTD_fWeight(U32 rawStat)
1004{
1005 U32 const fp_accuracy = 8;
1006 U32 const fp_multiplier = (1 << fp_accuracy);
1007 U32 const newStat = rawStat + 1;
1008 U32 const hb = ZSTD_highbit32(newStat);
1009 U32 const BWeight = hb * fp_multiplier;
1010 U32 const FWeight = (newStat << fp_accuracy) >> hb;
1011 U32 const weight = BWeight + FWeight;
1012 assert(hb + fp_accuracy < 31);
1013 return (double)weight / fp_multiplier;
1014}
1015
1016/* display a table content,
1017 * listing each element, its frequency, and its predicted bit cost */
1018MEM_STATIC void ZSTD_debugTable(const U32* table, U32 max)
1019{
1020 unsigned u, sum;
1021 for (u=0, sum=0; u<=max; u++) sum += table[u];
1022 DEBUGLOG(2, "total nb elts: %u", sum);
1023 for (u=0; u<=max; u++) {
1024 DEBUGLOG(2, "%2u: %5u (%.2f)",
1025 u, table[u], ZSTD_fWeight(sum) - ZSTD_fWeight(table[u]) );
1026 }
1027}
1028
1029#endif
1030
1031
1032#if defined (__cplusplus)
1033}
1034#endif
1035
1036/* ===============================================================
1037 * Shared internal declarations
1038 * These prototypes may be called from sources not in lib/compress
1039 * =============================================================== */
1040
1041/* ZSTD_loadCEntropy() :
1042 * dict : must point at beginning of a valid zstd dictionary.
1043 * return : size of dictionary header (size of magic number + dict ID + entropy tables)
1044 * assumptions : magic number supposed already checked
1045 * and dictSize >= 8 */
1046size_t ZSTD_loadCEntropy(ZSTD_compressedBlockState_t* bs, void* workspace,
1047 short* offcodeNCount, unsigned* offcodeMaxValue,
1048 const void* const dict, size_t dictSize);
1049
1051
1052/* ==============================================================
1053 * Private declarations
1054 * These prototypes shall only be called from within lib/compress
1055 * ============================================================== */
1056
1057/* ZSTD_getCParamsFromCCtxParams() :
1058 * cParams are built depending on compressionLevel, src size hints,
1059 * LDM and manually set compression parameters.
1060 * Note: srcSizeHint == 0 means 0!
1061 */
1062ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams(
1063 const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize);
1064
1071 const void* dict, size_t dictSize,
1072 const ZSTD_CDict* cdict,
1073 const ZSTD_CCtx_params* params, unsigned long long pledgedSrcSize);
1074
1075void ZSTD_resetSeqStore(seqStore_t* ssPtr);
1076
1079ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict);
1080
1081/* ZSTD_compressBegin_advanced_internal() :
1082 * Private use only. To be called from zstdmt_compress.c. */
1084 const void* dict, size_t dictSize,
1085 ZSTD_dictContentType_e dictContentType,
1087 const ZSTD_CDict* cdict,
1088 const ZSTD_CCtx_params* params,
1089 unsigned long long pledgedSrcSize);
1090
1091/* ZSTD_compress_advanced_internal() :
1092 * Private use only. To be called from zstdmt_compress.c. */
1094 void* dst, size_t dstCapacity,
1095 const void* src, size_t srcSize,
1096 const void* dict,size_t dictSize,
1097 const ZSTD_CCtx_params* params);
1098
1099
1100/* ZSTD_writeLastEmptyBlock() :
1101 * output an empty Block with end-of-frame mark to complete a frame
1102 * @return : size of data written into `dst` (== ZSTD_blockHeaderSize (defined in zstd_internal.h))
1103 * or an error code if `dstCapacity` is too small (<ZSTD_blockHeaderSize)
1104 */
1105size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity);
1106
1107
1108/* ZSTD_referenceExternalSequences() :
1109 * Must be called before starting a compression operation.
1110 * seqs must parse a prefix of the source.
1111 * This cannot be used when long range matching is enabled.
1112 * Zstd will use these sequences, and pass the literals to a secondary block
1113 * compressor.
1114 * @return : An error code on failure.
1115 * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory
1116 * access and data corruption.
1117 */
1118size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq);
1119
1122U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat);
1123
1124#endif /* ZSTD_COMPRESS_H */
#define MIN(x, y)
Definition: rdesktop.h:171
void mls(int argc, const char *argv[])
Definition: cmds.c:1168
#define NULL
Definition: types.h:112
UINT op
Definition: effect.c:236
static cab_ULONG checksum(const cab_UBYTE *data, cab_UWORD bytes, cab_ULONG csum)
Definition: fdi.c:353
#define assert(x)
Definition: debug.h:53
#define HINT_INLINE
Definition: compiler.h:61
#define UNUSED_ATTR
Definition: compiler.h:68
#define DEBUGLOG(l,...)
Definition: debug.h:106
MEM_STATIC U32 MEM_read32(const void *memPtr)
Definition: mem.h:242
MEM_STATIC U16 MEM_read16(const void *memPtr)
Definition: mem.h:237
MEM_STATIC size_t MEM_readST(const void *memPtr)
Definition: mem.h:252
MEM_STATIC unsigned MEM_isLittleEndian(void)
Definition: mem.h:186
MEM_STATIC unsigned MEM_64bits(void)
Definition: mem.h:184
MEM_STATIC U64 MEM_readLE64(const void *memPtr)
Definition: mem.h:362
#define MEM_STATIC
Definition: mem.h:39
MEM_STATIC void MEM_writeLE24(void *memPtr, U32 val)
Definition: mem.h:340
MEM_STATIC U32 MEM_readLE32(const void *memPtr)
Definition: mem.h:346
__kernel_size_t size_t
Definition: linux.h:237
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
unsigned FSE_CTable
Definition: fse.h:160
GLuint GLuint end
Definition: gl.h:1545
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLsizeiptr size
Definition: glext.h:5919
GLenum src
Definition: glext.h:6340
GLenum const GLfloat * params
Definition: glext.h:5645
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
GLenum GLenum dst
Definition: glext.h:6340
GLuint GLsizei GLsizei * length
Definition: glext.h:6040
GLuint GLfloat * val
Definition: glext.h:7180
GLfloat GLfloat p
Definition: glext.h:8902
GLenum GLsizei len
Definition: glext.h:6722
GLintptr offset
Definition: glext.h:5920
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
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
unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask)
Definition: intrin_arm.h:180
unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask)
Definition: intrin_arm.h:57
static struct msdos_boot_sector bs
Definition: mkdosfs.c:539
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
struct task_struct * current
Definition: linux.c:32
static PVOID ptr
Definition: dispmode.c:27
float power
Definition: d3drm.c:3372
static IHTMLWindow2 * window
Definition: events.c:77
static unsigned(__cdecl *hash_bstr)(bstr_t s)
static int sum(int x_, int y_)
Definition: ptr2_test.cpp:35
#define memset(x, y, z)
Definition: compat.h:39
weight
Definition: sortkey.c:157
#define KB
Definition: setuplib.h:55
ZSTD_frameParameters fParams
ZSTD_compressionParameters cParams
ZSTD_literalCompressionMode_e literalCompressionMode
ZSTD_dictAttachPref_e attachDictPref
ZSTD_CCtx_params appliedParams
ZSTD_customMem customMem
ZSTD_prefixDict prefixDict
SeqCollector seqCollector
ZSTD_compressionStage_e stage
ZSTD_CCtx_params requestedParams
rawSeqStore_t externSeqStore
unsigned long long pledgedSrcSizePlusOne
ZSTD_blockState_t blockState
ZSTD_cStreamStage streamStage
const ZSTD_CDict * cdict
XXH64_state_t xxhState
unsigned long long consumedSrcSize
unsigned long long producedCSize
ZSTD_localDict localDict
int upperBound
Definition: zstd.h:422
size_t error
Definition: zstd.h:420
int lowerBound
Definition: zstd.h:421
ZSTD_compressionParameters cParams
const ZSTD_matchState_t * dictMatchState
ZSTD_dictContentType_e dictContentType
Definition: _hash_fun.h:40
Definition: dhcpd.h:62
Definition: match.c:28
U16 matchLength
size_t maxNbSeq
size_t maxNbLit
seqDef * sequencesStart
seqDef * sequences
#define max(a, b)
Definition: svc.c:63
Definition: pdh_main.c:94
_In_ UINT iStart
Definition: wingdi.h:3620
unsigned long long U64
Definition: xxhash.c:197
signed int S32
Definition: xxhash.c:196
unsigned char BYTE
Definition: xxhash.c:193
unsigned short U16
Definition: xxhash.c:194
struct XXH64_state_s XXH64_state_t
Definition: xxhash.h:183
ZSTD_cParameter
Definition: zstd.h:265
@ ZSTD_c_strategy
Definition: zstd.h:326
ZSTD_strategy
Definition: zstd.h:251
@ ZSTD_btultra
Definition: zstd.h:258
@ ZSTD_fast
Definition: zstd.h:251
ZSTDLIB_API ZSTD_bounds ZSTD_cParam_getBounds(ZSTD_cParameter cParam)
ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode)
size_t ZSTD_compress_advanced_internal(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize, const ZSTD_CCtx_params *params)
MEM_STATIC size_t ZSTD_minGain(size_t srcSize, ZSTD_strategy strat)
MEM_STATIC U32 ZSTD_MLcode(U32 mlBase)
static size_t ZSTD_hash6Ptr(const void *p, U32 h)
MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
static const U64 prime7bytes
static size_t ZSTD_hash6(U64 u, U32 h)
static const U32 prime4bytes
MEM_STATIC void ZSTD_window_clear(ZSTD_window_t *window)
static size_t ZSTD_hash5(U64 u, U32 h)
static const U64 prime6bytes
MEM_STATIC U64 ZSTD_rollingHash_compute(void const *buf, size_t size)
MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
size_t ZSTD_referenceExternalSequences(ZSTD_CCtx *cctx, rawSeq *seq, size_t nbSeq)
MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window, void const *srcEnd)
static U32 ZSTD_hash4(U32 u, U32 h)
static size_t ZSTD_hash8(U64 u, U32 h)
MEM_STATIC size_t ZSTD_noCompressBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize, U32 lastBlock)
MEM_STATIC size_t ZSTD_count_2segments(const BYTE *ip, const BYTE *match, const BYTE *iEnd, const BYTE *mEnd, const BYTE *iStart)
static size_t ZSTD_hash8Ptr(const void *p, U32 h)
MEM_STATIC U64 ZSTD_rollingHash_primePower(U32 length)
MEM_STATIC repcodes_t ZSTD_updateRep(U32 const rep[3], U32 const offset, U32 const ll0)
static U64 ZSTD_ipow(U64 base, U64 exponent)
MEM_STATIC size_t ZSTD_hashPtr(const void *p, U32 hBits, U32 mls)
size_t ZSTD_loadCEntropy(ZSTD_compressedBlockState_t *bs, void *workspace, short *offcodeNCount, unsigned *offcodeMaxValue, const void *const dict, size_t dictSize)
static unsigned ZSTD_NbCommonBytes(size_t val)
MEM_STATIC U32 ZSTD_getLowestPrefixIndex(const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
struct repcodes_s repcodes_t
MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
static U64 ZSTD_rollingHash_append(U64 hash, void const *buf, size_t size)
MEM_STATIC U32 ZSTD_getLowestMatchIndex(const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
void ZSTD_resetSeqStore(seqStore_t *ssPtr)
MEM_STATIC void ZSTD_window_init(ZSTD_window_t *window)
MEM_STATIC size_t ZSTD_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *const pInLimit)
size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx *cctx, const void *dict, size_t dictSize, ZSTD_dictContentType_e dictContentType, ZSTD_dictTableLoadMethod_e dtlm, const ZSTD_CDict *cdict, const ZSTD_CCtx_params *params, unsigned long long pledgedSrcSize)
struct ZSTD_prefixDict_s ZSTD_prefixDict
size_t ZSTD_initCStream_internal(ZSTD_CStream *zcs, const void *dict, size_t dictSize, const ZSTD_CDict *cdict, const ZSTD_CCtx_params *params, unsigned long long pledgedSrcSize)
size_t(* ZSTD_blockCompressor)(ZSTD_matchState_t *bs, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
static size_t ZSTD_hash5Ptr(const void *p, U32 h)
MEM_STATIC int ZSTD_disableLiteralsCompression(const ZSTD_CCtx_params *cctxParams)
MEM_STATIC size_t ZSTD_rleCompressBlock(void *dst, size_t dstCapacity, BYTE src, size_t srcSize, U32 lastBlock)
MEM_STATIC int ZSTD_cParam_withinBounds(ZSTD_cParameter cParam, int value)
MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t *window, void const *src, size_t srcSize)
static const U32 prime3bytes
MEM_STATIC void ZSTD_checkDictValidity(const ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
ZSTD_compressionStage_e
@ ZSTDcs_ongoing
@ ZSTDcs_created
@ ZSTDcs_ending
static void ZSTD_safecopyLiterals(BYTE *op, BYTE const *ip, BYTE const *const iend, BYTE const *ilimit_w)
MEM_STATIC size_t ZSTD_hash3Ptr(const void *ptr, U32 h)
MEM_STATIC void ZSTD_window_enforceMaxDist(ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat)
HINT_INLINE UNUSED_ATTR void ZSTD_storeSeq(seqStore_t *seqStorePtr, size_t litLength, const BYTE *literals, const BYTE *litLimit, U32 offCode, size_t mlBase)
ZSTD_dictTableLoadMethod_e
@ ZSTD_dtlm_full
@ ZSTD_dtlm_fast
static const U64 prime8bytes
size_t ZSTD_writeLastEmptyBlock(void *dst, size_t dstCapacity)
static U32 ZSTD_hash3(U32 u, U32 h)
static size_t ZSTD_hash7Ptr(const void *p, U32 h)
void ZSTD_reset_compressedBlockState(ZSTD_compressedBlockState_t *bs)
MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t *window, U32 cycleLog, U32 maxDist, void const *src)
#define HASH_READ_SIZE
static size_t ZSTD_hash4Ptr(const void *ptr, U32 h)
#define ZSTD_ROLL_HASH_CHAR_OFFSET
static const U64 prime5bytes
ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams(const ZSTD_CCtx_params *CCtxParams, U64 srcSizeHint, size_t dictSize)
ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict *cdict)
@ ZSTD_dictMatchState
static size_t ZSTD_hash7(U64 u, U32 h)
#define MINMATCH
#define MaxLL
static const size_t ZSTD_blockHeaderSize
#define WILDCOPY_OVERLENGTH
#define MaxML
MEM_STATIC U32 ZSTD_highbit32(U32 val)
#define RETURN_ERROR_IF(cond, err,...)
Definition: zstd_internal.h:91
#define ZSTD_REP_MOVE
#define ZSTD_isError
Definition: zstd_internal.h:46
#define MLFSELog
@ bt_rle
@ bt_raw
static void ZSTD_copy16(void *dst, const void *src)
#define MaxOff
MEM_STATIC FORCE_INLINE_ATTR void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length, ZSTD_overlap_e const ovtype)
#define LLFSELog
#define ZSTD_STATIC_ASSERT(c)
Definition: zstd_internal.h:45
#define ZSTD_REP_NUM
@ ZSTD_no_overlap
#define OffFSELog

◆ ZSTD_cStreamStage

Enumerator
zcss_init 
zcss_load 
zcss_flush 

Definition at line 44 of file zstd_compress_internal.h.

◆ ZSTD_dictMode_e

Enumerator
ZSTD_noDict 
ZSTD_extDict 
ZSTD_dictMatchState 

Definition at line 283 of file zstd_compress_internal.h.

◆ ZSTD_dictTableLoadMethod_e

Enumerator
ZSTD_dtlm_fast 
ZSTD_dtlm_full 

Definition at line 281 of file zstd_compress_internal.h.

◆ ZSTD_OptPrice_e

Enumerator
zop_dynamic 
zop_predef 

Definition at line 92 of file zstd_compress_internal.h.

Function Documentation

◆ ZSTD_checkDictValidity()

MEM_STATIC void ZSTD_checkDictValidity ( const ZSTD_window_t window,
const void blockEnd,
U32  maxDist,
U32 loadedDictEndPtr,
const ZSTD_matchState_t **  dictMatchStatePtr 
)

Definition at line 887 of file zstd_compress_internal.h.

889 : loadedDictEndPtr and dictMatchStatePtr are valid (non NULL)
890 * loadedDictEnd uses same referential as window->base
891 * maxDist is the window size */
892MEM_STATIC void
894 const void* blockEnd,
895 U32 maxDist,
896 U32* loadedDictEndPtr,
897 const ZSTD_matchState_t** dictMatchStatePtr)
898{
899 assert(loadedDictEndPtr != NULL);
900 assert(dictMatchStatePtr != NULL);
901 { U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
902 U32 const loadedDictEnd = *loadedDictEndPtr;
903 DEBUGLOG(5, "ZSTD_checkDictValidity: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
904 (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd);
905 assert(blockEndIdx >= loadedDictEnd);
906
907 if (blockEndIdx > loadedDictEnd + maxDist) {
908 /* On reaching window size, dictionaries are invalidated.
909 * For simplification, if window size is reached anywhere within next block,
910 * the dictionary is invalidated for the full block.
911 */
912 DEBUGLOG(6, "invalidating dictionary for current block (distance > windowSize)");
913 *loadedDictEndPtr = 0;
BOOLEAN valid

Referenced by ZSTD_compress_frameChunk().

◆ ZSTD_compress_advanced_internal()

size_t ZSTD_compress_advanced_internal ( ZSTD_CCtx cctx,
void dst,
size_t  dstCapacity,
const void src,
size_t  srcSize,
const void dict,
size_t  dictSize,
const ZSTD_CCtx_params *  params 
)

Definition at line 3270 of file zstd_compress.c.

3276{
3277 DEBUGLOG(4, "ZSTD_compress_advanced_internal (srcSize:%u)", (unsigned)srcSize);
3279 dict, dictSize, ZSTD_dct_auto, ZSTD_dtlm_fast, NULL,
3280 params, srcSize, ZSTDb_not_buffered) , "");
3281 return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
3282}
@ ZSTDb_not_buffered
static size_t ZSTD_compressBegin_internal(ZSTD_CCtx *cctx, const void *dict, size_t dictSize, ZSTD_dictContentType_e dictContentType, ZSTD_dictTableLoadMethod_e dtlm, const ZSTD_CDict *cdict, const ZSTD_CCtx_params *params, U64 pledgedSrcSize, ZSTD_buffered_policy_e zbuff)
size_t ZSTD_compressEnd(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
#define FORWARD_IF_ERROR(err,...)

Referenced by ZSTD_compress_internal(), and ZSTD_compress_usingDict().

◆ ZSTD_compressBegin_advanced_internal()

size_t ZSTD_compressBegin_advanced_internal ( ZSTD_CCtx cctx,
const void dict,
size_t  dictSize,
ZSTD_dictContentType_e  dictContentType,
ZSTD_dictTableLoadMethod_e  dtlm,
const ZSTD_CDict cdict,
const ZSTD_CCtx_params *  params,
unsigned long long  pledgedSrcSize 
)

Definition at line 3122 of file zstd_compress.c.

3129{
3130 DEBUGLOG(4, "ZSTD_compressBegin_advanced_internal: wlog=%u", params->cParams.windowLog);
3131 /* compression parameters verification and optimization */
3132 FORWARD_IF_ERROR( ZSTD_checkCParams(params->cParams) , "");
3133 return ZSTD_compressBegin_internal(cctx,
3134 dict, dictSize, dictContentType, dtlm,
3135 cdict,
3136 params, pledgedSrcSize,
3138}
size_t ZSTD_checkCParams(ZSTD_compressionParameters cParams)

Referenced by ZSTD_compressBegin_advanced().

◆ ZSTD_count()

MEM_STATIC size_t ZSTD_count ( const BYTE pIn,
const BYTE pMatch,
const BYTE *const  pInLimit 
)

Definition at line 555 of file zstd_compress_internal.h.

562{
563 const BYTE* const pStart = pIn;
564 const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
565
566 if (pIn < pInLoopLimit) {
567 { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
568 if (diff) return ZSTD_NbCommonBytes(diff); }
569 pIn+=sizeof(size_t); pMatch+=sizeof(size_t);
570 while (pIn < pInLoopLimit) {
571 size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
572 if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
573 pIn += ZSTD_NbCommonBytes(diff);
574 return (size_t)(pIn - pStart);

Referenced by ZSTD_compressBlock_doubleFast_generic(), ZSTD_compressBlock_fast_dictMatchState_generic(), ZSTD_compressBlock_fast_generic(), ZSTD_compressBlock_lazy_generic(), ZSTD_count_2segments(), ZSTD_DUBT_findBestMatch(), ZSTD_HcFindBestMatch_generic(), ZSTD_insertBt1(), ZSTD_insertBtAndGetAllMatches(), ZSTD_insertDUBT1(), and ZSTD_ldm_generateSequences_internal().

◆ ZSTD_count_2segments()

MEM_STATIC size_t ZSTD_count_2segments ( const BYTE ip,
const BYTE match,
const BYTE iEnd,
const BYTE mEnd,
const BYTE iStart 
)

ZSTD_count_2segments() : can count match length with ip & match in 2 different segments. convention : on reaching mEnd, match count continue starting from iStart

Definition at line 581 of file zstd_compress_internal.h.

589{
590 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
591 size_t const matchLength = ZSTD_count(ip, match, vEnd);
592 if (match + matchLength != mEnd) return matchLength;
593 DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength);

Referenced by ZSTD_compressBlock_doubleFast_extDict_generic(), ZSTD_compressBlock_doubleFast_generic(), ZSTD_compressBlock_fast_dictMatchState_generic(), ZSTD_compressBlock_fast_extDict_generic(), ZSTD_compressBlock_lazy_extDict_generic(), ZSTD_compressBlock_lazy_generic(), ZSTD_DUBT_findBestMatch(), ZSTD_DUBT_findBetterDictMatch(), ZSTD_HcFindBestMatch_generic(), ZSTD_insertBt1(), ZSTD_insertBtAndGetAllMatches(), ZSTD_insertDUBT1(), and ZSTD_ldm_generateSequences_internal().

◆ ZSTD_cParam_withinBounds()

MEM_STATIC int ZSTD_cParam_withinBounds ( ZSTD_cParameter  cParam,
int  value 
)

Definition at line 351 of file zstd_compress_internal.h.

358{

Referenced by ZSTD_selectBlockCompressor().

◆ ZSTD_cycleLog()

U32 ZSTD_cycleLog ( U32  hashLog,
ZSTD_strategy  strat 
)

ZSTD_cycleLog() : condition for correct operation : hashLog > 1

Definition at line 1019 of file zstd_compress.c.

1020{
1021 U32 const btScale = ((U32)strat >= (U32)ZSTD_btlazy2);
1022 return hashLog - btScale;
1023}
@ ZSTD_btlazy2
Definition: zstd.h:256

Referenced by ZSTD_adjustCParams_internal(), and ZSTD_overflowCorrectIfNeeded().

◆ ZSTD_disableLiteralsCompression()

MEM_STATIC int ZSTD_disableLiteralsCompression ( const ZSTD_CCtx_params *  cctxParams)

Definition at line 396 of file zstd_compress_internal.h.

396 : 6;
399 return (srcSize >> minlog) + 2;
400}
401
402MEM_STATIC int ZSTD_disableLiteralsCompression(const ZSTD_CCtx_params* cctxParams)
403{
404 switch (cctxParams->literalCompressionMode) {
405 case ZSTD_lcm_huffman:
406 return 0;
407 case ZSTD_lcm_uncompressed:
408 return 1;
409 default:

Referenced by ZSTD_buildSuperBlockEntropy(), and ZSTD_compressSequences_internal().

◆ ZSTD_getCParamsFromCCtxParams()

ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams ( const ZSTD_CCtx_params *  CCtxParams,
U64  srcSizeHint,
size_t  dictSize 
)

Definition at line 1077 of file zstd_compress.c.

1079{
1080 ZSTD_compressionParameters cParams;
1081 if (srcSizeHint == ZSTD_CONTENTSIZE_UNKNOWN && CCtxParams->srcSizeHint > 0) {
1082 srcSizeHint = CCtxParams->srcSizeHint;
1083 }
1084 cParams = ZSTD_getCParams_internal(CCtxParams->compressionLevel, srcSizeHint, dictSize);
1085 if (CCtxParams->ldmParams.enableLdm) cParams.windowLog = ZSTD_LDM_DEFAULT_WINDOW_LOG;
1086 if (CCtxParams->cParams.windowLog) cParams.windowLog = CCtxParams->cParams.windowLog;
1087 if (CCtxParams->cParams.hashLog) cParams.hashLog = CCtxParams->cParams.hashLog;
1088 if (CCtxParams->cParams.chainLog) cParams.chainLog = CCtxParams->cParams.chainLog;
1089 if (CCtxParams->cParams.searchLog) cParams.searchLog = CCtxParams->cParams.searchLog;
1090 if (CCtxParams->cParams.minMatch) cParams.minMatch = CCtxParams->cParams.minMatch;
1091 if (CCtxParams->cParams.targetLength) cParams.targetLength = CCtxParams->cParams.targetLength;
1092 if (CCtxParams->cParams.strategy) cParams.strategy = CCtxParams->cParams.strategy;
1093 assert(!ZSTD_checkCParams(cParams));
1094 /* srcSizeHint == 0 means 0 */
1095 return ZSTD_adjustCParams_internal(cParams, srcSizeHint, dictSize);
1096}
#define ZSTD_CONTENTSIZE_UNKNOWN
Definition: zstd.h:152
static ZSTD_compressionParameters ZSTD_adjustCParams_internal(ZSTD_compressionParameters cPar, unsigned long long srcSize, size_t dictSize)
static ZSTD_compressionParameters ZSTD_getCParams_internal(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize)
#define ZSTD_LDM_DEFAULT_WINDOW_LOG
Definition: zstd_ldm.h:25

Referenced by ZSTD_compressStream2(), ZSTD_estimateCCtxSize_usingCCtxParams(), ZSTD_estimateCStreamSize_usingCCtxParams(), ZSTD_initLocalDict(), and ZSTD_resetCStream_internal().

◆ ZSTD_getCParamsFromCDict()

ZSTD_compressionParameters ZSTD_getCParamsFromCDict ( const ZSTD_CDict cdict)

ZSTD_getCParamsFromCDict() : as the name implies

Definition at line 3530 of file zstd_compress.c.

3531{
3532 assert(cdict != NULL);
3533 return cdict->matchState.cParams;
3534}
ZSTD_matchState_t matchState
Definition: zstd_compress.c:57

Referenced by ZSTD_compressBegin_usingCDict_advanced().

◆ ZSTD_getLowestMatchIndex()

MEM_STATIC U32 ZSTD_getLowestMatchIndex ( const ZSTD_matchState_t ms,
U32  current,
unsigned  windowLog 
)

Returns the lowest allowed match index. It may either be in the ext-dict or the prefix.

Definition at line 970 of file zstd_compress_internal.h.

977{
978 U32 const maxDistance = 1U << windowLog;

Referenced by ZSTD_compressBlock_doubleFast_extDict_generic(), ZSTD_compressBlock_fast_extDict_generic(), ZSTD_compressBlock_lazy_extDict_generic(), ZSTD_DUBT_findBestMatch(), and ZSTD_insertBtAndGetAllMatches().

◆ ZSTD_getLowestPrefixIndex()

MEM_STATIC U32 ZSTD_getLowestPrefixIndex ( const ZSTD_matchState_t ms,
U32  current,
unsigned  windowLog 
)

Returns the lowest allowed match index in the prefix.

Definition at line 983 of file zstd_compress_internal.h.

990{
991 U32 const maxDistance = 1U << windowLog;

Referenced by ZSTD_compressBlock_doubleFast_generic(), ZSTD_compressBlock_fast_generic(), and ZSTD_compressBlock_lazy_generic().

◆ ZSTD_hash3()

static U32 ZSTD_hash3 ( U32  u,
U32  h 
)
static

Definition at line 600 of file zstd_compress_internal.h.

◆ ZSTD_hash3Ptr()

MEM_STATIC size_t ZSTD_hash3Ptr ( const void ptr,
U32  h 
)

Definition at line 601 of file zstd_compress_internal.h.

Referenced by ZSTD_insertAndFindFirstIndexHash3().

◆ ZSTD_hash4()

static U32 ZSTD_hash4 ( U32  u,
U32  h 
)
static

Definition at line 604 of file zstd_compress_internal.h.

◆ ZSTD_hash4Ptr()

static size_t ZSTD_hash4Ptr ( const void ptr,
U32  h 
)
static

Definition at line 605 of file zstd_compress_internal.h.

◆ ZSTD_hash5()

static size_t ZSTD_hash5 ( U64  u,
U32  h 
)
static

Definition at line 608 of file zstd_compress_internal.h.

◆ ZSTD_hash5Ptr()

static size_t ZSTD_hash5Ptr ( const void p,
U32  h 
)
static

Definition at line 609 of file zstd_compress_internal.h.

◆ ZSTD_hash6()

static size_t ZSTD_hash6 ( U64  u,
U32  h 
)
static

Definition at line 612 of file zstd_compress_internal.h.

◆ ZSTD_hash6Ptr()

static size_t ZSTD_hash6Ptr ( const void p,
U32  h 
)
static

Definition at line 613 of file zstd_compress_internal.h.

◆ ZSTD_hash7()

static size_t ZSTD_hash7 ( U64  u,
U32  h 
)
static

Definition at line 616 of file zstd_compress_internal.h.

Referenced by ZSTD_hashPtr().

◆ ZSTD_hash7Ptr()

static size_t ZSTD_hash7Ptr ( const void p,
U32  h 
)
static

Definition at line 617 of file zstd_compress_internal.h.

◆ ZSTD_hash8()

static size_t ZSTD_hash8 ( U64  u,
U32  h 
)
static

Definition at line 620 of file zstd_compress_internal.h.

◆ ZSTD_hash8Ptr()

static size_t ZSTD_hash8Ptr ( const void p,
U32  h 
)
static

Definition at line 621 of file zstd_compress_internal.h.

◆ ZSTD_hashPtr()

◆ ZSTD_initCStream_internal()

size_t ZSTD_initCStream_internal ( ZSTD_CStream zcs,
const void dict,
size_t  dictSize,
const ZSTD_CDict cdict,
const ZSTD_CCtx_params *  params,
unsigned long long  pledgedSrcSize 
)

ZSTD_initCStream_internal() : Private use only. Init streaming operation. expects params to be valid. must receive dict, or cdict, or none, but not both.

Returns
: 0, or an error code

ZSTD_initCStream_internal() : Note : for lib/compress only. Used by zstdmt_compress.c. Assumption 1 : params are valid Assumption 2 : either dict, or cdict, is defined, not both

Definition at line 3690 of file zstd_compress.c.

3694{
3695 DEBUGLOG(4, "ZSTD_initCStream_internal");
3697 FORWARD_IF_ERROR( ZSTD_CCtx_setPledgedSrcSize(zcs, pledgedSrcSize) , "");
3699 zcs->requestedParams = *params;
3700 assert(!((dict) && (cdict))); /* either dict or cdict, not both */
3701 if (dict) {
3702 FORWARD_IF_ERROR( ZSTD_CCtx_loadDictionary(zcs, dict, dictSize) , "");
3703 } else {
3704 /* Dictionary is cleared if !cdict */
3705 FORWARD_IF_ERROR( ZSTD_CCtx_refCDict(zcs, cdict) , "");
3706 }
3707 return 0;
3708}
@ ZSTD_reset_session_only
Definition: zstd.h:465
ZSTDLIB_API size_t ZSTD_CCtx_loadDictionary(ZSTD_CCtx *cctx, const void *dict, size_t dictSize)
size_t ZSTD_CCtx_reset(ZSTD_CCtx *cctx, ZSTD_ResetDirective reset)
size_t ZSTD_CCtx_refCDict(ZSTD_CCtx *cctx, const ZSTD_CDict *cdict)
ZSTDLIB_API size_t ZSTD_CCtx_setPledgedSrcSize(ZSTD_CCtx *cctx, unsigned long long pledgedSrcSize)

◆ ZSTD_ipow()

static U64 ZSTD_ipow ( U64  base,
U64  exponent 
)
static

ZSTD_ipow() : Return base^exponent.

Definition at line 639 of file zstd_compress_internal.h.

646{
647 U64 power = 1;
648 while (exponent) {

◆ ZSTD_LLcode()

MEM_STATIC U32 ZSTD_LLcode ( U32  litLength)

Definition at line 292 of file zstd_compress_internal.h.

299{
300 static const BYTE LL_Code[64] = { 0, 1, 2, 3, 4, 5, 6, 7,
301 8, 9, 10, 11, 12, 13, 14, 15,
302 16, 16, 17, 17, 18, 18, 19, 19,
303 20, 20, 20, 20, 21, 21, 21, 21,
304 22, 22, 22, 22, 22, 22, 22, 22,

Referenced by ZSTD_litLengthPrice(), ZSTD_seqToCodes(), and ZSTD_updateStats().

◆ ZSTD_loadCEntropy()

size_t ZSTD_loadCEntropy ( ZSTD_compressedBlockState_t bs,
void workspace,
short offcodeNCount,
unsigned offcodeMaxValue,
const void *const  dict,
size_t  dictSize 
)

Definition at line 2902 of file zstd_compress.c.

2905{
2906 const BYTE* dictPtr = (const BYTE*)dict; /* skip magic num and dict ID */
2907 const BYTE* const dictEnd = dictPtr + dictSize;
2908 dictPtr += 8;
2909 bs->entropy.huf.repeatMode = HUF_repeat_check;
2910
2911 { unsigned maxSymbolValue = 255;
2912 unsigned hasZeroWeights = 1;
2913 size_t const hufHeaderSize = HUF_readCTable((HUF_CElt*)bs->entropy.huf.CTable, &maxSymbolValue, dictPtr,
2914 dictEnd-dictPtr, &hasZeroWeights);
2915
2916 /* We only set the loaded table as valid if it contains all non-zero
2917 * weights. Otherwise, we set it to check */
2918 if (!hasZeroWeights)
2919 bs->entropy.huf.repeatMode = HUF_repeat_valid;
2920
2921 RETURN_ERROR_IF(HUF_isError(hufHeaderSize), dictionary_corrupted, "");
2922 RETURN_ERROR_IF(maxSymbolValue < 255, dictionary_corrupted, "");
2923 dictPtr += hufHeaderSize;
2924 }
2925
2926 { unsigned offcodeLog;
2927 size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
2928 RETURN_ERROR_IF(FSE_isError(offcodeHeaderSize), dictionary_corrupted, "");
2929 RETURN_ERROR_IF(offcodeLog > OffFSELog, dictionary_corrupted, "");
2930 /* Defer checking offcodeMaxValue because we need to know the size of the dictionary content */
2931 /* fill all offset symbols to avoid garbage at end of table */
2933 bs->entropy.fse.offcodeCTable,
2934 offcodeNCount, MaxOff, offcodeLog,
2935 workspace, HUF_WORKSPACE_SIZE)),
2936 dictionary_corrupted, "");
2937 dictPtr += offcodeHeaderSize;
2938 }
2939
2940 { short matchlengthNCount[MaxML+1];
2941 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
2942 size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
2943 RETURN_ERROR_IF(FSE_isError(matchlengthHeaderSize), dictionary_corrupted, "");
2944 RETURN_ERROR_IF(matchlengthLog > MLFSELog, dictionary_corrupted, "");
2945 /* Every match length code must have non-zero probability */
2946 FORWARD_IF_ERROR( ZSTD_checkDictNCount(matchlengthNCount, matchlengthMaxValue, MaxML), "");
2948 bs->entropy.fse.matchlengthCTable,
2949 matchlengthNCount, matchlengthMaxValue, matchlengthLog,
2950 workspace, HUF_WORKSPACE_SIZE)),
2951 dictionary_corrupted, "");
2952 dictPtr += matchlengthHeaderSize;
2953 }
2954
2955 { short litlengthNCount[MaxLL+1];
2956 unsigned litlengthMaxValue = MaxLL, litlengthLog;
2957 size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
2958 RETURN_ERROR_IF(FSE_isError(litlengthHeaderSize), dictionary_corrupted, "");
2959 RETURN_ERROR_IF(litlengthLog > LLFSELog, dictionary_corrupted, "");
2960 /* Every literal length code must have non-zero probability */
2961 FORWARD_IF_ERROR( ZSTD_checkDictNCount(litlengthNCount, litlengthMaxValue, MaxLL), "");
2963 bs->entropy.fse.litlengthCTable,
2964 litlengthNCount, litlengthMaxValue, litlengthLog,
2965 workspace, HUF_WORKSPACE_SIZE)),
2966 dictionary_corrupted, "");
2967 dictPtr += litlengthHeaderSize;
2968 }
2969
2970 RETURN_ERROR_IF(dictPtr+12 > dictEnd, dictionary_corrupted, "");
2971 bs->rep[0] = MEM_readLE32(dictPtr+0);
2972 bs->rep[1] = MEM_readLE32(dictPtr+4);
2973 bs->rep[2] = MEM_readLE32(dictPtr+8);
2974 dictPtr += 12;
2975
2976 return dictPtr - (const BYTE*)dict;
2977}
size_t FSE_readNCount(short *normalizedCounter, unsigned *maxSVPtr, unsigned *tableLogPtr, const void *headerBuffer, size_t hbSize)
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 FSE_isError
Definition: fse_compress.c:35
#define HUF_WORKSPACE_SIZE
Definition: huf.h:93
#define HUF_isError
Definition: huf_compress.c:41
size_t HUF_readCTable(HUF_CElt *CTable, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize, unsigned *hasZeroWeights)
Definition: huf_compress.c:150
static size_t ZSTD_checkDictNCount(short *normalizedCounter, unsigned dictMaxSymbolValue, unsigned maxSymbolValue)

Referenced by ZSTD_loadZstdDictionary().

◆ ZSTD_matchState_dictMode()

MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode ( const ZSTD_matchState_t ms)

ZSTD_matchState_dictMode(): Inspects the provided matchState and figures out what dictMode should be passed to the compressor.

Definition at line 734 of file zstd_compress_internal.h.

741{

Referenced by ZSTD_buildSeqStore(), and ZSTD_ldm_blockCompress().

◆ ZSTD_minGain()

◆ ZSTD_MLcode()

MEM_STATIC U32 ZSTD_MLcode ( U32  mlBase)

Definition at line 309 of file zstd_compress_internal.h.

309 : LL_Code[litLength];
310}
311
312/* ZSTD_MLcode() :
313 * note : mlBase = matchLength - MINMATCH;
314 * because it's the format it's stored in seqStore->sequences */
316{
317 static const BYTE ML_Code[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
318 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
319 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
320 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
321 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,

Referenced by ZSTD_getMatchPrice(), ZSTD_seqToCodes(), and ZSTD_updateStats().

◆ ZSTD_NbCommonBytes()

static unsigned ZSTD_NbCommonBytes ( size_t  val)
static

Definition at line 490 of file zstd_compress_internal.h.

497{
498 if (MEM_isLittleEndian()) {
499 if (MEM_64bits()) {
500# if defined(_MSC_VER) && defined(_WIN64)
501 unsigned long r = 0;
502 return _BitScanForward64( &r, (U64)val ) ? (unsigned)(r >> 3) : 0;
503# elif defined(__GNUC__) && (__GNUC__ >= 4)
504 return (__builtin_ctzll((U64)val) >> 3);
505# else
506 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
507 0, 3, 1, 3, 1, 4, 2, 7,
508 0, 2, 3, 6, 1, 5, 3, 5,
509 1, 3, 4, 4, 2, 5, 6, 7,
510 7, 0, 1, 2, 3, 3, 4, 6,
511 2, 6, 5, 5, 3, 4, 5, 6,
512 7, 1, 2, 4, 6, 4, 4, 5,
513 7, 2, 6, 5, 7, 6, 7, 7 };
514 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
515# endif
516 } else { /* 32 bits */
517# if defined(_MSC_VER)
518 unsigned long r=0;
519 return _BitScanForward( &r, (U32)val ) ? (unsigned)(r >> 3) : 0;
520# elif defined(__GNUC__) && (__GNUC__ >= 3)
521 return (__builtin_ctz((U32)val) >> 3);
522# else
523 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
524 3, 2, 2, 1, 3, 2, 0, 1,
525 3, 3, 1, 2, 2, 2, 2, 0,
526 3, 1, 2, 0, 1, 0, 1, 1 };
527 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
528# endif
529 }
530 } else { /* Big Endian CPU */
531 if (MEM_64bits()) {
532# if defined(_MSC_VER) && defined(_WIN64)
533 unsigned long r = 0;
534 return _BitScanReverse64( &r, val ) ? (unsigned)(r >> 3) : 0;
535# elif defined(__GNUC__) && (__GNUC__ >= 4)
536 return (__builtin_clzll(val) >> 3);
537# else
538 unsigned r;
539 const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */
540 if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
541 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
542 r += (!val);
543 return r;
544# endif
545 } else { /* 32 bits */
546# if defined(_MSC_VER)
547 unsigned long r = 0;
548 return _BitScanReverse( &r, (unsigned long)val ) ? (unsigned)(r >> 3) : 0;
549# elif defined(__GNUC__) && (__GNUC__ >= 3)
550 return (__builtin_clz((U32)val) >> 3);
551# else
552 unsigned r;

◆ ZSTD_noCompressBlock()

MEM_STATIC size_t ZSTD_noCompressBlock ( void dst,
size_t  dstCapacity,
const void src,
size_t  srcSize,
U32  lastBlock 
)

Definition at line 363 of file zstd_compress_internal.h.

370{
371 U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(srcSize << 3);

Referenced by ZSTD_compress_frameChunk(), ZSTD_compressBlock_targetCBlockSize_body(), and ZSTD_compressSubBlock_multi().

◆ ZSTD_referenceExternalSequences()

size_t ZSTD_referenceExternalSequences ( ZSTD_CCtx cctx,
rawSeq seq,
size_t  nbSeq 
)

Definition at line 2717 of file zstd_compress.c.

2718{
2719 RETURN_ERROR_IF(cctx->stage != ZSTDcs_init, stage_wrong,
2720 "wrong cctx stage");
2721 RETURN_ERROR_IF(cctx->appliedParams.ldmParams.enableLdm,
2722 parameter_unsupported,
2723 "incompatible with ldm");
2724 cctx->externSeqStore.seq = seq;
2725 cctx->externSeqStore.size = nbSeq;
2726 cctx->externSeqStore.capacity = nbSeq;
2727 cctx->externSeqStore.pos = 0;
2728 return 0;
2729}

Referenced by ZSTD_resetCCtx_internal().

◆ ZSTD_reset_compressedBlockState()

void ZSTD_reset_compressedBlockState ( ZSTD_compressedBlockState_t bs)

Definition at line 1282 of file zstd_compress.c.

1283{
1284 int i;
1285 for (i = 0; i < ZSTD_REP_NUM; ++i)
1286 bs->rep[i] = repStartValue[i];
1287 bs->entropy.huf.repeatMode = HUF_repeat_none;
1288 bs->entropy.fse.offcode_repeatMode = FSE_repeat_none;
1289 bs->entropy.fse.matchlength_repeatMode = FSE_repeat_none;
1290 bs->entropy.fse.litlength_repeatMode = FSE_repeat_none;
1291}
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
static const U32 repStartValue[ZSTD_REP_NUM]

Referenced by ZSTD_compress_insertDictionary(), ZSTD_initCDict_internal(), and ZSTD_resetCCtx_internal().

◆ ZSTD_resetSeqStore()

void ZSTD_resetSeqStore ( seqStore_t ssPtr)

Definition at line 2233 of file zstd_compress.c.

2234{
2235 ssPtr->lit = ssPtr->litStart;
2236 ssPtr->sequences = ssPtr->sequencesStart;
2237 ssPtr->longLengthID = 0;
2238}
BYTE * litStart

Referenced by ZSTD_buildSeqStore(), and ZSTD_initStats_ultra().

◆ ZSTD_rleCompressBlock()

MEM_STATIC size_t ZSTD_rleCompressBlock ( void dst,
size_t  dstCapacity,
BYTE  src,
size_t  srcSize,
U32  lastBlock 
)

Definition at line 373 of file zstd_compress_internal.h.

380{
381 BYTE* const op = (BYTE*)dst;

Referenced by ZSTD_compressBlock_targetCBlockSize_body().

◆ ZSTD_rollingHash_append()

static U64 ZSTD_rollingHash_append ( U64  hash,
void const buf,
size_t  size 
)
static

ZSTD_rollingHash_append() : Add the buffer to the hash value.

Definition at line 655 of file zstd_compress_internal.h.

662{
663 BYTE const* istart = (BYTE const*)buf;
664 size_t pos;

◆ ZSTD_rollingHash_compute()

MEM_STATIC U64 ZSTD_rollingHash_compute ( void const buf,
size_t  size 
)

ZSTD_rollingHash_compute() : Compute the rolling hash value of the buffer.

Definition at line 669 of file zstd_compress_internal.h.

Referenced by ZSTD_ldm_fillHashTable(), and ZSTD_ldm_generateSequences_internal().

◆ ZSTD_rollingHash_primePower()

MEM_STATIC U64 ZSTD_rollingHash_primePower ( U32  length)

ZSTD_rollingHash_primePower() : Compute the primePower to be passed to ZSTD_rollingHash_rotate() for a hash over a window of length bytes.

Definition at line 678 of file zstd_compress_internal.h.

Referenced by ZSTD_resetCCtx_internal().

◆ ZSTD_rollingHash_rotate()

MEM_STATIC U64 ZSTD_rollingHash_rotate ( U64  hash,
BYTE  toRemove,
BYTE  toAdd,
U64  primePower 
)

ZSTD_rollingHash_rotate() : Rotate the rolling hash by one byte.

Definition at line 686 of file zstd_compress_internal.h.

Referenced by ZSTD_ldm_fillLdmHashTable(), and ZSTD_ldm_generateSequences_internal().

◆ ZSTD_safecopyLiterals()

static void ZSTD_safecopyLiterals ( BYTE op,
BYTE const ip,
BYTE const *const  iend,
BYTE const ilimit_w 
)
static

ZSTD_safecopyLiterals() : memcpy() function that won't read beyond more than WILDCOPY_OVERLENGTH bytes past ilimit_w. Only called when the sequence ends past ilimit_w, so it only needs to be optimized for single large copies.

Definition at line 416 of file zstd_compress_internal.h.

422 {
423 assert(iend > ilimit_w);
424 if (ip <= ilimit_w) {

◆ ZSTD_selectBlockCompressor()

ZSTD_blockCompressor ZSTD_selectBlockCompressor ( ZSTD_strategy  strat,
ZSTD_dictMode_e  dictMode 
)

Definition at line 2183 of file zstd_compress.c.

2184{
2185 static const ZSTD_blockCompressor blockCompressor[3][ZSTD_STRATEGY_MAX+1] = {
2186 { ZSTD_compressBlock_fast /* default for 0 */,
2196 { ZSTD_compressBlock_fast_extDict /* default for 0 */,
2206 { ZSTD_compressBlock_fast_dictMatchState /* default for 0 */,
2216 };
2217 ZSTD_blockCompressor selectedCompressor;
2218 ZSTD_STATIC_ASSERT((unsigned)ZSTD_fast == 1);
2219
2221 selectedCompressor = blockCompressor[(int)dictMode][(int)strat];
2222 assert(selectedCompressor != NULL);
2223 return selectedCompressor;
2224}
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
size_t ZSTD_compressBlock_doubleFast(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
size_t ZSTD_compressBlock_doubleFast_extDict(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
size_t ZSTD_compressBlock_doubleFast_dictMatchState(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
size_t ZSTD_compressBlock_fast_dictMatchState(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_fast.c:354
size_t ZSTD_compressBlock_fast(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_fast.c:186
size_t ZSTD_compressBlock_fast_extDict(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_fast.c:479
size_t ZSTD_compressBlock_btlazy2(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_lazy.c:871
size_t ZSTD_compressBlock_lazy_extDict(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_lazy.c:1116
size_t ZSTD_compressBlock_lazy_dictMatchState(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_lazy.c:913
size_t ZSTD_compressBlock_greedy_dictMatchState(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_lazy.c:920
size_t ZSTD_compressBlock_lazy2_dictMatchState(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_lazy.c:906
size_t ZSTD_compressBlock_btlazy2_extDict(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_lazy.c:1132
size_t ZSTD_compressBlock_greedy(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_lazy.c:892
size_t ZSTD_compressBlock_lazy2(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_lazy.c:878
size_t ZSTD_compressBlock_lazy2_extDict(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_lazy.c:1124
size_t ZSTD_compressBlock_lazy(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_lazy.c:885
size_t ZSTD_compressBlock_greedy_extDict(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_lazy.c:1109
size_t ZSTD_compressBlock_btlazy2_dictMatchState(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_lazy.c:899
size_t ZSTD_compressBlock_btopt_extDict(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1184
size_t ZSTD_compressBlock_btopt(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1069
size_t ZSTD_compressBlock_btultra_dictMatchState(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1177
size_t ZSTD_compressBlock_btultra_extDict(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1191
size_t ZSTD_compressBlock_btultra2(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1142
size_t ZSTD_compressBlock_btultra(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1134
size_t ZSTD_compressBlock_btopt_dictMatchState(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1170

Referenced by ZSTD_buildSeqStore(), and ZSTD_ldm_blockCompress().

◆ ZSTD_storeSeq()

HINT_INLINE UNUSED_ATTR void ZSTD_storeSeq ( seqStore_t seqStorePtr,
size_t  litLength,
const BYTE literals,
const BYTE litLimit,
U32  offCode,
size_t  mlBase 
)

ZSTD_storeSeq() : Store a sequence (litlen, litPtr, offCode and mlBase) into seqStore_t. offCode : distance to match + ZSTD_REP_MOVE (values <= ZSTD_REP_MOVE are repCodes). mlBase : matchLength - MINMATCH Allowed to overread literals up to litLimit.

Definition at line 433 of file zstd_compress_internal.h.

434 : distance to match + ZSTD_REP_MOVE (values <= ZSTD_REP_MOVE are repCodes).
435 * `mlBase` : matchLength - MINMATCH
436 * Allowed to overread literals up to litLimit.
437*/
439void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const BYTE* literals, const BYTE* litLimit, U32 offCode, size_t mlBase)
440{
441 BYTE const* const litLimit_w = litLimit - WILDCOPY_OVERLENGTH;
442 BYTE const* const litEnd = literals + litLength;
443#if defined(DEBUGLEVEL) && (DEBUGLEVEL >= 6)
444 static const BYTE* g_start = NULL;
445 if (g_start==NULL) g_start = (const BYTE*)literals; /* note : index only works for compression within a single segment */
446 { U32 const pos = (U32)((const BYTE*)literals - g_start);
447 DEBUGLOG(6, "Cpos%7u :%3u literals, match%4u bytes at offCode%7u",
448 pos, (U32)litLength, (U32)mlBase+MINMATCH, (U32)offCode);
449 }
450#endif
451 assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq);
452 /* copy Literals */
453 assert(seqStorePtr->maxNbLit <= 128 KB);
454 assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit);
455 assert(literals + litLength <= litLimit);
456 if (litEnd <= litLimit_w) {
457 /* Common case we can use wildcopy.
458 * First copy 16 bytes, because literals are likely short.
459 */
461 ZSTD_copy16(seqStorePtr->lit, literals);
462 if (litLength > 16) {
463 ZSTD_wildcopy(seqStorePtr->lit+16, literals+16, (ptrdiff_t)litLength-16, ZSTD_no_overlap);
464 }
465 } else {
466 ZSTD_safecopyLiterals(seqStorePtr->lit, literals, litEnd, litLimit_w);
467 }
468 seqStorePtr->lit += litLength;
469
470 /* literal Length */
471 if (litLength>0xFFFF) {
472 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
473 seqStorePtr->longLengthID = 1;
474 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
475 }
476 seqStorePtr->sequences[0].litLength = (U16)litLength;
477
478 /* match offset */
479 seqStorePtr->sequences[0].offset = offCode + 1;
480
481 /* match Length */
482 if (mlBase>0xFFFF) {
483 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
484 seqStorePtr->longLengthID = 2;
GLsizei GLsizei GLfloat distance
Definition: glext.h:11755
GLboolean GLenum GLenum GLvoid * values
Definition: glext.h:5666
#define up(mutex)
Definition: glue.h:30

Referenced by ZSTD_compressBlock_doubleFast_extDict_generic(), ZSTD_compressBlock_doubleFast_generic(), ZSTD_compressBlock_fast_dictMatchState_generic(), ZSTD_compressBlock_fast_extDict_generic(), ZSTD_compressBlock_fast_generic(), ZSTD_compressBlock_lazy_extDict_generic(), ZSTD_compressBlock_lazy_generic(), ZSTD_compressBlock_opt_generic(), and ZSTD_ldm_blockCompress().

◆ ZSTD_updateRep()

MEM_STATIC repcodes_t ZSTD_updateRep ( U32 const  rep[3],
U32 const  offset,
U32 const  ll0 
)

Definition at line 327 of file zstd_compress_internal.h.

329 {
330 U32 rep[3];
331} repcodes_t;
332
333MEM_STATIC repcodes_t ZSTD_updateRep(U32 const rep[3], U32 const offset, U32 const ll0)
334{
335 repcodes_t newReps;
336 if (offset >= ZSTD_REP_NUM) { /* full offset */
337 newReps.rep[2] = rep[1];
338 newReps.rep[1] = rep[0];
339 newReps.rep[0] = offset - ZSTD_REP_MOVE;
340 } else { /* repcode */
341 U32 const repCode = offset + ll0;
342 if (repCode > 0) { /* note : if repCode==0, no change */
343 U32 const currentOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode];
344 newReps.rep[2] = (repCode >= 2) ? rep[1] : rep[2];
345 newReps.rep[1] = rep[0];
346 newReps.rep[0] = currentOffset;

Referenced by ZSTD_compressBlock_opt_generic(), and ZSTD_compressSubBlock_multi().

◆ ZSTD_window_clear()

MEM_STATIC void ZSTD_window_clear ( ZSTD_window_t window)

ZSTD_window_clear(): Clears the window containing the history by simply setting it to empty.

Definition at line 711 of file zstd_compress_internal.h.

718{

Referenced by ZSTD_invalidateMatchState(), ZSTD_resetCCtx_byAttachingCDict(), and ZSTD_resetCCtx_internal().

◆ ZSTD_window_correctOverflow()

MEM_STATIC U32 ZSTD_window_correctOverflow ( ZSTD_window_t window,
U32  cycleLog,
U32  maxDist,
void const src 
)

ZSTD_window_correctOverflow(): Reduces the indices to protect from index overflow. Returns the correction made to the indices, which must be applied to every stored index.

The least significant cycleLog bits of the indices must remain the same, which may be 0. Every index up to maxDist in the past must be valid. NOTE: (maxDist & cycleMask) must be zero.

Definition at line 765 of file zstd_compress_internal.h.

769 : (maxDist & cycleMask) must be zero.
770 */
772 U32 maxDist, void const* src)
773{
774 /* preemptive overflow correction:
775 * 1. correction is large enough:
776 * lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog
777 * 1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog
778 *
779 * current - newCurrent
780 * > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog)
781 * > (3<<29) - (1<<chainLog)
782 * > (3<<29) - (1<<30) (NOTE: chainLog <= 30)
783 * > 1<<29
784 *
785 * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow:
786 * After correction, current is less than (1<<chainLog + 1<<windowLog).
787 * In 64-bit mode we are safe, because we have 64-bit ptrdiff_t.
788 * In 32-bit mode we are safe, because (chainLog <= 29), so
789 * ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32.
790 * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32:
791 * windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32.
792 */
793 U32 const cycleMask = (1U << cycleLog) - 1;
794 U32 const current = (U32)((BYTE const*)src - window->base);
795 U32 const currentCycle0 = current & cycleMask;
796 /* Exclude zero so that newCurrent - maxDist >= 1. */
797 U32 const currentCycle1 = currentCycle0 == 0 ? (1U << cycleLog) : currentCycle0;
798 U32 const newCurrent = currentCycle1 + maxDist;
799 U32 const correction = current - newCurrent;
800 assert((maxDist & cycleMask) == 0);
801 assert(current > newCurrent);
802 /* Loose bound, should be around 1<<29 (see above) */
803 assert(correction > 1<<28);
804
805 window->base += correction;
806 window->dictBase += correction;
807 if (window->lowLimit <= correction) window->lowLimit = 1;
808 else window->lowLimit -= correction;
809 if (window->dictLimit <= correction) window->dictLimit = 1;
810 else window->dictLimit -= correction;
811
812 /* Ensure we can still reference the full window. */
813 assert(newCurrent >= maxDist);
814 assert(newCurrent - maxDist >= 1);
815 /* Ensure that lowLimit and dictLimit didn't underflow. */
816 assert(window->lowLimit <= newCurrent);
int zero
Definition: sehframes.cpp:29

Referenced by ZSTD_ldm_generateSequences(), and ZSTD_overflowCorrectIfNeeded().

◆ ZSTD_window_enforceMaxDist()

MEM_STATIC void ZSTD_window_enforceMaxDist ( ZSTD_window_t window,
const void blockEnd,
U32  maxDist,
U32 loadedDictEndPtr,
const ZSTD_matchState_t **  dictMatchStatePtr 
)

ZSTD_window_enforceMaxDist(): Updates lowLimit so that: (srcEnd - base) - lowLimit == maxDist + loadedDictEnd

It ensures index is valid as long as index >= lowLimit. This must be called before a block compression call.

loadedDictEnd is only defined if a dictionary is in use for current compression. As the name implies, loadedDictEnd represents the index at end of dictionary. The value lies within context's referential, it can be directly compared to blockEndIdx.

If loadedDictEndPtr is NULL, no dictionary is in use, and we use loadedDictEnd == 0. If loadedDictEndPtr is not NULL, we set it to zero after updating lowLimit. This is because dictionaries are allowed to be referenced fully as long as the last byte of the dictionary is in the window. Once input has progressed beyond window size, dictionary cannot be referenced anymore.

In normal dict mode, the dictionary lies between lowLimit and dictLimit. In dictMatchState mode, lowLimit and dictLimit are the same, and the dictionary is below them. forceWindow and dictMatchState are therefore incompatible.

Definition at line 842 of file zstd_compress_internal.h.

853{
854 U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
855 U32 const loadedDictEnd = (loadedDictEndPtr != NULL) ? *loadedDictEndPtr : 0;
856 DEBUGLOG(5, "ZSTD_window_enforceMaxDist: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
857 (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd);
858
859 /* - When there is no dictionary : loadedDictEnd == 0.
860 In which case, the test (blockEndIdx > maxDist) is merely to avoid
861 overflowing next operation `newLowLimit = blockEndIdx - maxDist`.
862 - When there is a standard dictionary :
863 Index referential is copied from the dictionary,
864 which means it starts from 0.
865 In which case, loadedDictEnd == dictSize,
866 and it makes sense to compare `blockEndIdx > maxDist + dictSize`
867 since `blockEndIdx` also starts from zero.
868 - When there is an attached dictionary :
869 loadedDictEnd is expressed within the referential of the context,
870 so it can be directly compared against blockEndIdx.
871 */
872 if (blockEndIdx > maxDist + loadedDictEnd) {
873 U32 const newLowLimit = blockEndIdx - maxDist;
874 if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit;
875 if (window->dictLimit < window->lowLimit) {
876 DEBUGLOG(5, "Update dictLimit to match lowLimit, from %u to %u",
877 (unsigned)window->dictLimit, (unsigned)window->lowLimit);
878 window->dictLimit = window->lowLimit;

Referenced by ZSTD_ldm_generateSequences().

◆ ZSTD_window_hasExtDict()

MEM_STATIC U32 ZSTD_window_hasExtDict ( ZSTD_window_t const  window)

ZSTD_window_hasExtDict(): Returns non-zero if the window has a non-empty extDict.

Definition at line 724 of file zstd_compress_internal.h.

Referenced by ZSTD_invalidateRepCodes(), ZSTD_ldm_generateSequences_internal(), and ZSTD_matchState_dictMode().

◆ ZSTD_window_init()

MEM_STATIC void ZSTD_window_init ( ZSTD_window_t window)

Definition at line 915 of file zstd_compress_internal.h.

915 {
916 if (*loadedDictEndPtr != 0) {
917 DEBUGLOG(6, "dictionary considered valid for current block");
918 } } }
919}
920
922 memset(window, 0, sizeof(*window));

Referenced by ZSTD_reset_matchState(), and ZSTD_resetCCtx_internal().

◆ ZSTD_window_needOverflowCorrection()

MEM_STATIC U32 ZSTD_window_needOverflowCorrection ( ZSTD_window_t const  window,
void const srcEnd 
)

ZSTD_window_needOverflowCorrection(): Returns non-zero if the indices are getting too large and need overflow protection.

Definition at line 748 of file zstd_compress_internal.h.

Referenced by ZSTD_ldm_generateSequences(), and ZSTD_overflowCorrectIfNeeded().

◆ ZSTD_window_update()

MEM_STATIC U32 ZSTD_window_update ( ZSTD_window_t window,
void const src,
size_t  srcSize 
)

ZSTD_window_update(): Updates the window by appending [src, src + srcSize) to the window. If it is not contiguous, the current prefix becomes the extDict, and we forget about the extDict. Handles overlap of the prefix and extDict. Returns non-zero if the segment is contiguous.

Definition at line 931 of file zstd_compress_internal.h.

931 :
932 * Updates the window by appending [src, src + srcSize) to the window.
933 * If it is not contiguous, the current prefix becomes the extDict, and we
934 * forget about the extDict. Handles overlap of the prefix and extDict.
935 * Returns non-zero if the segment is contiguous.
936 */
938 void const* src, size_t srcSize)
939{
940 BYTE const* const ip = (BYTE const*)src;
941 U32 contiguous = 1;
942 DEBUGLOG(5, "ZSTD_window_update");
943 if (srcSize == 0)
944 return contiguous;
945 assert(window->base != NULL);
946 assert(window->dictBase != NULL);
947 /* Check if blocks follow each other */
948 if (src != window->nextSrc) {
949 /* not contiguous */
950 size_t const distanceFromBase = (size_t)(window->nextSrc - window->base);
951 DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit);
952 window->lowLimit = window->dictLimit;
953 assert(distanceFromBase == (size_t)(U32)distanceFromBase); /* should never overflow */
954 window->dictLimit = (U32)distanceFromBase;
955 window->dictBase = window->base;
956 window->base = ip - distanceFromBase;
957 /* ms->nextToUpdate = window->dictLimit; */
958 if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit; /* too small extDict */
959 contiguous = 0;
960 }
961 window->nextSrc = ip + srcSize;
962 /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
963 if ( (ip+srcSize > window->dictBase + window->lowLimit)
964 & (ip < window->dictBase + window->dictLimit)) {
965 ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase;
GLbyte by
Definition: glext.h:8766
int about
Definition: msacm.c:1366

Referenced by ZSTD_compressContinue_internal(), and ZSTD_loadDictionaryContent().

◆ ZSTD_writeLastEmptyBlock()

size_t ZSTD_writeLastEmptyBlock ( void dst,
size_t  dstCapacity 
)

Definition at line 2707 of file zstd_compress.c.

2708{
2709 RETURN_ERROR_IF(dstCapacity < ZSTD_blockHeaderSize, dstSize_tooSmall,
2710 "dst buf is too small to write frame trailer empty block.");
2711 { U32 const cBlockHeader24 = 1 /*lastBlock*/ + (((U32)bt_raw)<<1); /* 0 size */
2712 MEM_writeLE24(dst, cBlockHeader24);
2713 return ZSTD_blockHeaderSize;
2714 }
2715}

Variable Documentation

◆ prime3bytes

const U32 prime3bytes = 506832829U
static

Definition at line 599 of file zstd_compress_internal.h.

Referenced by ZSTD_hash4Ptr().

◆ prime4bytes

const U32 prime4bytes = 2654435761U
static

Definition at line 603 of file zstd_compress_internal.h.

Referenced by ZSTD_hash5Ptr().

◆ prime5bytes

const U64 prime5bytes = 889523592379ULL
static

Definition at line 607 of file zstd_compress_internal.h.

Referenced by ZSTD_hash6Ptr().

◆ prime6bytes

const U64 prime6bytes = 227718039650203ULL
static

Definition at line 611 of file zstd_compress_internal.h.

Referenced by ZSTD_hash7Ptr().

◆ prime7bytes

const U64 prime7bytes = 58295818150454627ULL
static

Definition at line 615 of file zstd_compress_internal.h.

Referenced by ZSTD_hash8Ptr().

◆ prime8bytes

const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL
static

Definition at line 619 of file zstd_compress_internal.h.

Referenced by ZSTD_rollingHash_append().