Commit | Line | Data |
---|---|---|
e0c1b49f NT |
1 | /* |
2 | * Copyright (c) Yann Collet, Facebook, Inc. | |
3 | * All rights reserved. | |
4 | * | |
5 | * This source code is licensed under both the BSD-style license (found in the | |
6 | * LICENSE file in the root directory of this source tree) and the GPLv2 (found | |
7 | * in the COPYING file in the root directory of this source tree). | |
8 | * You may select, at your option, one of the above-listed licenses. | |
9 | */ | |
10 | ||
11 | /* This header contains definitions | |
12 | * that shall **only** be used by modules within lib/compress. | |
13 | */ | |
14 | ||
15 | #ifndef ZSTD_COMPRESS_H | |
16 | #define ZSTD_COMPRESS_H | |
17 | ||
18 | /*-************************************* | |
19 | * Dependencies | |
20 | ***************************************/ | |
21 | #include "../common/zstd_internal.h" | |
22 | #include "zstd_cwksp.h" | |
23 | ||
24 | ||
25 | /*-************************************* | |
26 | * Constants | |
27 | ***************************************/ | |
28 | #define kSearchStrength 8 | |
29 | #define HASH_READ_SIZE 8 | |
30 | #define ZSTD_DUBT_UNSORTED_MARK 1 /* For btlazy2 strategy, index ZSTD_DUBT_UNSORTED_MARK==1 means "unsorted". | |
31 | It could be confused for a real successor at index "1", if sorted as larger than its predecessor. | |
32 | It's not a big deal though : candidate will just be sorted again. | |
33 | Additionally, candidate position 1 will be lost. | |
34 | But candidate 1 cannot hide a large tree of candidates, so it's a minimal loss. | |
35 | The benefit is that ZSTD_DUBT_UNSORTED_MARK cannot be mishandled after table re-use with a different strategy. | |
36 | This constant is required by ZSTD_compressBlock_btlazy2() and ZSTD_reduceTable_internal() */ | |
37 | ||
38 | ||
39 | /*-************************************* | |
40 | * Context memory management | |
41 | ***************************************/ | |
42 | typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e; | |
43 | typedef enum { zcss_init=0, zcss_load, zcss_flush } ZSTD_cStreamStage; | |
44 | ||
45 | typedef struct ZSTD_prefixDict_s { | |
46 | const void* dict; | |
47 | size_t dictSize; | |
48 | ZSTD_dictContentType_e dictContentType; | |
49 | } ZSTD_prefixDict; | |
50 | ||
51 | typedef struct { | |
52 | void* dictBuffer; | |
53 | void const* dict; | |
54 | size_t dictSize; | |
55 | ZSTD_dictContentType_e dictContentType; | |
56 | ZSTD_CDict* cdict; | |
57 | } ZSTD_localDict; | |
58 | ||
59 | typedef struct { | |
2aa14b1a | 60 | HUF_CElt CTable[HUF_CTABLE_SIZE_ST(255)]; |
e0c1b49f NT |
61 | HUF_repeat repeatMode; |
62 | } ZSTD_hufCTables_t; | |
63 | ||
64 | typedef struct { | |
65 | FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)]; | |
66 | FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)]; | |
67 | FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)]; | |
68 | FSE_repeat offcode_repeatMode; | |
69 | FSE_repeat matchlength_repeatMode; | |
70 | FSE_repeat litlength_repeatMode; | |
71 | } ZSTD_fseCTables_t; | |
72 | ||
73 | typedef struct { | |
74 | ZSTD_hufCTables_t huf; | |
75 | ZSTD_fseCTables_t fse; | |
76 | } ZSTD_entropyCTables_t; | |
77 | ||
2aa14b1a NT |
78 | /* ********************************************* |
79 | * Entropy buffer statistics structs and funcs * | |
80 | ***********************************************/ | |
81 | /* ZSTD_hufCTablesMetadata_t : | |
82 | * Stores Literals Block Type for a super-block in hType, and | |
83 | * huffman tree description in hufDesBuffer. | |
84 | * hufDesSize refers to the size of huffman tree description in bytes. | |
85 | * This metadata is populated in ZSTD_buildBlockEntropyStats_literals() */ | |
e0c1b49f | 86 | typedef struct { |
2aa14b1a NT |
87 | symbolEncodingType_e hType; |
88 | BYTE hufDesBuffer[ZSTD_MAX_HUF_HEADER_SIZE]; | |
89 | size_t hufDesSize; | |
90 | } ZSTD_hufCTablesMetadata_t; | |
91 | ||
92 | /* ZSTD_fseCTablesMetadata_t : | |
93 | * Stores symbol compression modes for a super-block in {ll, ol, ml}Type, and | |
94 | * fse tables in fseTablesBuffer. | |
95 | * fseTablesSize refers to the size of fse tables in bytes. | |
96 | * This metadata is populated in ZSTD_buildBlockEntropyStats_sequences() */ | |
97 | typedef struct { | |
98 | symbolEncodingType_e llType; | |
99 | symbolEncodingType_e ofType; | |
100 | symbolEncodingType_e mlType; | |
101 | BYTE fseTablesBuffer[ZSTD_MAX_FSE_HEADERS_SIZE]; | |
102 | size_t fseTablesSize; | |
103 | size_t lastCountSize; /* This is to account for bug in 1.3.4. More detail in ZSTD_entropyCompressSeqStore_internal() */ | |
104 | } ZSTD_fseCTablesMetadata_t; | |
105 | ||
106 | typedef struct { | |
107 | ZSTD_hufCTablesMetadata_t hufMetadata; | |
108 | ZSTD_fseCTablesMetadata_t fseMetadata; | |
109 | } ZSTD_entropyCTablesMetadata_t; | |
110 | ||
111 | /* ZSTD_buildBlockEntropyStats() : | |
112 | * Builds entropy for the block. | |
113 | * @return : 0 on success or error code */ | |
114 | size_t ZSTD_buildBlockEntropyStats(seqStore_t* seqStorePtr, | |
115 | const ZSTD_entropyCTables_t* prevEntropy, | |
116 | ZSTD_entropyCTables_t* nextEntropy, | |
117 | const ZSTD_CCtx_params* cctxParams, | |
118 | ZSTD_entropyCTablesMetadata_t* entropyMetadata, | |
119 | void* workspace, size_t wkspSize); | |
120 | ||
121 | /* ******************************* | |
122 | * Compression internals structs * | |
123 | *********************************/ | |
124 | ||
125 | typedef struct { | |
126 | U32 off; /* Offset sumtype code for the match, using ZSTD_storeSeq() format */ | |
e0c1b49f NT |
127 | U32 len; /* Raw length of match */ |
128 | } ZSTD_match_t; | |
129 | ||
130 | typedef struct { | |
131 | U32 offset; /* Offset of sequence */ | |
132 | U32 litLength; /* Length of literals prior to match */ | |
133 | U32 matchLength; /* Raw length of match */ | |
134 | } rawSeq; | |
135 | ||
136 | typedef struct { | |
137 | rawSeq* seq; /* The start of the sequences */ | |
138 | size_t pos; /* The index in seq where reading stopped. pos <= size. */ | |
139 | size_t posInSequence; /* The position within the sequence at seq[pos] where reading | |
140 | stopped. posInSequence <= seq[pos].litLength + seq[pos].matchLength */ | |
141 | size_t size; /* The number of sequences. <= capacity. */ | |
142 | size_t capacity; /* The capacity starting from `seq` pointer */ | |
143 | } rawSeqStore_t; | |
144 | ||
145 | UNUSED_ATTR static const rawSeqStore_t kNullRawSeqStore = {NULL, 0, 0, 0, 0}; | |
146 | ||
147 | typedef struct { | |
148 | int price; | |
149 | U32 off; | |
150 | U32 mlen; | |
151 | U32 litlen; | |
152 | U32 rep[ZSTD_REP_NUM]; | |
153 | } ZSTD_optimal_t; | |
154 | ||
155 | typedef enum { zop_dynamic=0, zop_predef } ZSTD_OptPrice_e; | |
156 | ||
157 | typedef struct { | |
158 | /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */ | |
159 | unsigned* litFreq; /* table of literals statistics, of size 256 */ | |
160 | unsigned* litLengthFreq; /* table of litLength statistics, of size (MaxLL+1) */ | |
161 | unsigned* matchLengthFreq; /* table of matchLength statistics, of size (MaxML+1) */ | |
162 | unsigned* offCodeFreq; /* table of offCode statistics, of size (MaxOff+1) */ | |
163 | ZSTD_match_t* matchTable; /* list of found matches, of size ZSTD_OPT_NUM+1 */ | |
164 | ZSTD_optimal_t* priceTable; /* All positions tracked by optimal parser, of size ZSTD_OPT_NUM+1 */ | |
165 | ||
166 | U32 litSum; /* nb of literals */ | |
167 | U32 litLengthSum; /* nb of litLength codes */ | |
168 | U32 matchLengthSum; /* nb of matchLength codes */ | |
169 | U32 offCodeSum; /* nb of offset codes */ | |
170 | U32 litSumBasePrice; /* to compare to log2(litfreq) */ | |
171 | U32 litLengthSumBasePrice; /* to compare to log2(llfreq) */ | |
172 | U32 matchLengthSumBasePrice;/* to compare to log2(mlfreq) */ | |
173 | U32 offCodeSumBasePrice; /* to compare to log2(offreq) */ | |
174 | ZSTD_OptPrice_e priceType; /* prices can be determined dynamically, or follow a pre-defined cost structure */ | |
175 | const ZSTD_entropyCTables_t* symbolCosts; /* pre-calculated dictionary statistics */ | |
2aa14b1a | 176 | ZSTD_paramSwitch_e literalCompressionMode; |
e0c1b49f NT |
177 | } optState_t; |
178 | ||
179 | typedef struct { | |
180 | ZSTD_entropyCTables_t entropy; | |
181 | U32 rep[ZSTD_REP_NUM]; | |
182 | } ZSTD_compressedBlockState_t; | |
183 | ||
184 | typedef struct { | |
2aa14b1a NT |
185 | BYTE const* nextSrc; /* next block here to continue on current prefix */ |
186 | BYTE const* base; /* All regular indexes relative to this position */ | |
187 | BYTE const* dictBase; /* extDict indexes relative to this position */ | |
188 | U32 dictLimit; /* below that point, need extDict */ | |
189 | U32 lowLimit; /* below that point, no more valid data */ | |
190 | U32 nbOverflowCorrections; /* Number of times overflow correction has run since | |
191 | * ZSTD_window_init(). Useful for debugging coredumps | |
192 | * and for ZSTD_WINDOW_OVERFLOW_CORRECT_FREQUENTLY. | |
193 | */ | |
e0c1b49f NT |
194 | } ZSTD_window_t; |
195 | ||
2aa14b1a NT |
196 | #define ZSTD_WINDOW_START_INDEX 2 |
197 | ||
e0c1b49f | 198 | typedef struct ZSTD_matchState_t ZSTD_matchState_t; |
2aa14b1a NT |
199 | |
200 | #define ZSTD_ROW_HASH_CACHE_SIZE 8 /* Size of prefetching hash cache for row-based matchfinder */ | |
201 | ||
e0c1b49f NT |
202 | struct ZSTD_matchState_t { |
203 | ZSTD_window_t window; /* State for window round buffer management */ | |
204 | U32 loadedDictEnd; /* index of end of dictionary, within context's referential. | |
205 | * When loadedDictEnd != 0, a dictionary is in use, and still valid. | |
206 | * This relies on a mechanism to set loadedDictEnd=0 when dictionary is no longer within distance. | |
207 | * Such mechanism is provided within ZSTD_window_enforceMaxDist() and ZSTD_checkDictValidity(). | |
208 | * When dict referential is copied into active context (i.e. not attached), | |
209 | * loadedDictEnd == dictSize, since referential starts from zero. | |
210 | */ | |
211 | U32 nextToUpdate; /* index from which to continue table update */ | |
212 | U32 hashLog3; /* dispatch table for matches of len==3 : larger == faster, more memory */ | |
2aa14b1a NT |
213 | |
214 | U32 rowHashLog; /* For row-based matchfinder: Hashlog based on nb of rows in the hashTable.*/ | |
215 | U16* tagTable; /* For row-based matchFinder: A row-based table containing the hashes and head index. */ | |
216 | U32 hashCache[ZSTD_ROW_HASH_CACHE_SIZE]; /* For row-based matchFinder: a cache of hashes to improve speed */ | |
217 | ||
e0c1b49f NT |
218 | U32* hashTable; |
219 | U32* hashTable3; | |
220 | U32* chainTable; | |
2aa14b1a NT |
221 | |
222 | U32 forceNonContiguous; /* Non-zero if we should force non-contiguous load for the next window update. */ | |
223 | ||
e0c1b49f NT |
224 | int dedicatedDictSearch; /* Indicates whether this matchState is using the |
225 | * dedicated dictionary search structure. | |
226 | */ | |
227 | optState_t opt; /* optimal parser state */ | |
228 | const ZSTD_matchState_t* dictMatchState; | |
229 | ZSTD_compressionParameters cParams; | |
230 | const rawSeqStore_t* ldmSeqStore; | |
231 | }; | |
232 | ||
233 | typedef struct { | |
234 | ZSTD_compressedBlockState_t* prevCBlock; | |
235 | ZSTD_compressedBlockState_t* nextCBlock; | |
236 | ZSTD_matchState_t matchState; | |
237 | } ZSTD_blockState_t; | |
238 | ||
239 | typedef struct { | |
240 | U32 offset; | |
241 | U32 checksum; | |
242 | } ldmEntry_t; | |
243 | ||
244 | typedef struct { | |
245 | BYTE const* split; | |
246 | U32 hash; | |
247 | U32 checksum; | |
248 | ldmEntry_t* bucket; | |
249 | } ldmMatchCandidate_t; | |
250 | ||
251 | #define LDM_BATCH_SIZE 64 | |
252 | ||
253 | typedef struct { | |
254 | ZSTD_window_t window; /* State for the window round buffer management */ | |
255 | ldmEntry_t* hashTable; | |
256 | U32 loadedDictEnd; | |
257 | BYTE* bucketOffsets; /* Next position in bucket to insert entry */ | |
258 | size_t splitIndices[LDM_BATCH_SIZE]; | |
259 | ldmMatchCandidate_t matchCandidates[LDM_BATCH_SIZE]; | |
260 | } ldmState_t; | |
261 | ||
262 | typedef struct { | |
2aa14b1a | 263 | ZSTD_paramSwitch_e enableLdm; /* ZSTD_ps_enable to enable LDM. ZSTD_ps_auto by default */ |
e0c1b49f NT |
264 | U32 hashLog; /* Log size of hashTable */ |
265 | U32 bucketSizeLog; /* Log bucket size for collision resolution, at most 8 */ | |
266 | U32 minMatchLength; /* Minimum match length */ | |
267 | U32 hashRateLog; /* Log number of entries to skip */ | |
268 | U32 windowLog; /* Window log for the LDM */ | |
269 | } ldmParams_t; | |
270 | ||
271 | typedef struct { | |
272 | int collectSequences; | |
273 | ZSTD_Sequence* seqStart; | |
274 | size_t seqIndex; | |
275 | size_t maxSequences; | |
276 | } SeqCollector; | |
277 | ||
278 | struct ZSTD_CCtx_params_s { | |
279 | ZSTD_format_e format; | |
280 | ZSTD_compressionParameters cParams; | |
281 | ZSTD_frameParameters fParams; | |
282 | ||
283 | int compressionLevel; | |
284 | int forceWindow; /* force back-references to respect limit of | |
285 | * 1<<wLog, even for dictionary */ | |
286 | size_t targetCBlockSize; /* Tries to fit compressed block size to be around targetCBlockSize. | |
287 | * No target when targetCBlockSize == 0. | |
288 | * There is no guarantee on compressed block size */ | |
289 | int srcSizeHint; /* User's best guess of source size. | |
290 | * Hint is not valid when srcSizeHint == 0. | |
291 | * There is no guarantee that hint is close to actual source size */ | |
292 | ||
293 | ZSTD_dictAttachPref_e attachDictPref; | |
2aa14b1a | 294 | ZSTD_paramSwitch_e literalCompressionMode; |
e0c1b49f NT |
295 | |
296 | /* Multithreading: used to pass parameters to mtctx */ | |
297 | int nbWorkers; | |
298 | size_t jobSize; | |
299 | int overlapLog; | |
300 | int rsyncable; | |
301 | ||
302 | /* Long distance matching parameters */ | |
303 | ldmParams_t ldmParams; | |
304 | ||
305 | /* Dedicated dict search algorithm trigger */ | |
306 | int enableDedicatedDictSearch; | |
307 | ||
308 | /* Input/output buffer modes */ | |
309 | ZSTD_bufferMode_e inBufferMode; | |
310 | ZSTD_bufferMode_e outBufferMode; | |
311 | ||
312 | /* Sequence compression API */ | |
313 | ZSTD_sequenceFormat_e blockDelimiters; | |
314 | int validateSequences; | |
315 | ||
2aa14b1a NT |
316 | /* Block splitting */ |
317 | ZSTD_paramSwitch_e useBlockSplitter; | |
318 | ||
319 | /* Param for deciding whether to use row-based matchfinder */ | |
320 | ZSTD_paramSwitch_e useRowMatchFinder; | |
321 | ||
322 | /* Always load a dictionary in ext-dict mode (not prefix mode)? */ | |
323 | int deterministicRefPrefix; | |
324 | ||
e0c1b49f NT |
325 | /* Internal use, for createCCtxParams() and freeCCtxParams() only */ |
326 | ZSTD_customMem customMem; | |
327 | }; /* typedef'd to ZSTD_CCtx_params within "zstd.h" */ | |
328 | ||
329 | #define COMPRESS_SEQUENCES_WORKSPACE_SIZE (sizeof(unsigned) * (MaxSeq + 2)) | |
330 | #define ENTROPY_WORKSPACE_SIZE (HUF_WORKSPACE_SIZE + COMPRESS_SEQUENCES_WORKSPACE_SIZE) | |
331 | ||
332 | /* | |
333 | * Indicates whether this compression proceeds directly from user-provided | |
334 | * source buffer to user-provided destination buffer (ZSTDb_not_buffered), or | |
335 | * whether the context needs to buffer the input/output (ZSTDb_buffered). | |
336 | */ | |
337 | typedef enum { | |
338 | ZSTDb_not_buffered, | |
339 | ZSTDb_buffered | |
340 | } ZSTD_buffered_policy_e; | |
341 | ||
2aa14b1a NT |
342 | /* |
343 | * Struct that contains all elements of block splitter that should be allocated | |
344 | * in a wksp. | |
345 | */ | |
346 | #define ZSTD_MAX_NB_BLOCK_SPLITS 196 | |
347 | typedef struct { | |
348 | seqStore_t fullSeqStoreChunk; | |
349 | seqStore_t firstHalfSeqStore; | |
350 | seqStore_t secondHalfSeqStore; | |
351 | seqStore_t currSeqStore; | |
352 | seqStore_t nextSeqStore; | |
353 | ||
354 | U32 partitions[ZSTD_MAX_NB_BLOCK_SPLITS]; | |
355 | ZSTD_entropyCTablesMetadata_t entropyMetadata; | |
356 | } ZSTD_blockSplitCtx; | |
357 | ||
e0c1b49f NT |
358 | struct ZSTD_CCtx_s { |
359 | ZSTD_compressionStage_e stage; | |
360 | 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. */ | |
361 | int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */ | |
362 | ZSTD_CCtx_params requestedParams; | |
363 | ZSTD_CCtx_params appliedParams; | |
2aa14b1a | 364 | ZSTD_CCtx_params simpleApiParams; /* Param storage used by the simple API - not sticky. Must only be used in top-level simple API functions for storage. */ |
e0c1b49f NT |
365 | U32 dictID; |
366 | size_t dictContentSize; | |
367 | ||
368 | ZSTD_cwksp workspace; /* manages buffer for dynamic allocations */ | |
369 | size_t blockSize; | |
370 | unsigned long long pledgedSrcSizePlusOne; /* this way, 0 (default) == unknown */ | |
371 | unsigned long long consumedSrcSize; | |
372 | unsigned long long producedCSize; | |
373 | struct xxh64_state xxhState; | |
374 | ZSTD_customMem customMem; | |
375 | ZSTD_threadPool* pool; | |
376 | size_t staticSize; | |
377 | SeqCollector seqCollector; | |
378 | int isFirstBlock; | |
379 | int initialized; | |
380 | ||
381 | seqStore_t seqStore; /* sequences storage ptrs */ | |
382 | ldmState_t ldmState; /* long distance matching state */ | |
383 | rawSeq* ldmSequences; /* Storage for the ldm output sequences */ | |
384 | size_t maxNbLdmSequences; | |
385 | rawSeqStore_t externSeqStore; /* Mutable reference to external sequences */ | |
386 | ZSTD_blockState_t blockState; | |
387 | U32* entropyWorkspace; /* entropy workspace of ENTROPY_WORKSPACE_SIZE bytes */ | |
388 | ||
2aa14b1a | 389 | /* Whether we are streaming or not */ |
e0c1b49f NT |
390 | ZSTD_buffered_policy_e bufferedPolicy; |
391 | ||
392 | /* streaming */ | |
393 | char* inBuff; | |
394 | size_t inBuffSize; | |
395 | size_t inToCompress; | |
396 | size_t inBuffPos; | |
397 | size_t inBuffTarget; | |
398 | char* outBuff; | |
399 | size_t outBuffSize; | |
400 | size_t outBuffContentSize; | |
401 | size_t outBuffFlushedSize; | |
402 | ZSTD_cStreamStage streamStage; | |
403 | U32 frameEnded; | |
404 | ||
405 | /* Stable in/out buffer verification */ | |
406 | ZSTD_inBuffer expectedInBuffer; | |
407 | size_t expectedOutBufferSize; | |
408 | ||
409 | /* Dictionary */ | |
410 | ZSTD_localDict localDict; | |
411 | const ZSTD_CDict* cdict; | |
412 | ZSTD_prefixDict prefixDict; /* single-usage dictionary */ | |
413 | ||
414 | /* Multi-threading */ | |
415 | ||
416 | /* Tracing */ | |
2aa14b1a NT |
417 | |
418 | /* Workspace for block splitter */ | |
419 | ZSTD_blockSplitCtx blockSplitCtx; | |
e0c1b49f NT |
420 | }; |
421 | ||
422 | typedef enum { ZSTD_dtlm_fast, ZSTD_dtlm_full } ZSTD_dictTableLoadMethod_e; | |
423 | ||
424 | typedef enum { | |
425 | ZSTD_noDict = 0, | |
426 | ZSTD_extDict = 1, | |
427 | ZSTD_dictMatchState = 2, | |
428 | ZSTD_dedicatedDictSearch = 3 | |
429 | } ZSTD_dictMode_e; | |
430 | ||
431 | typedef enum { | |
432 | ZSTD_cpm_noAttachDict = 0, /* Compression with ZSTD_noDict or ZSTD_extDict. | |
433 | * In this mode we use both the srcSize and the dictSize | |
434 | * when selecting and adjusting parameters. | |
435 | */ | |
436 | ZSTD_cpm_attachDict = 1, /* Compression with ZSTD_dictMatchState or ZSTD_dedicatedDictSearch. | |
437 | * In this mode we only take the srcSize into account when selecting | |
438 | * and adjusting parameters. | |
439 | */ | |
440 | ZSTD_cpm_createCDict = 2, /* Creating a CDict. | |
441 | * In this mode we take both the source size and the dictionary size | |
442 | * into account when selecting and adjusting the parameters. | |
443 | */ | |
444 | ZSTD_cpm_unknown = 3, /* ZSTD_getCParams, ZSTD_getParams, ZSTD_adjustParams. | |
445 | * We don't know what these parameters are for. We default to the legacy | |
446 | * behavior of taking both the source size and the dict size into account | |
447 | * when selecting and adjusting parameters. | |
448 | */ | |
449 | } ZSTD_cParamMode_e; | |
450 | ||
451 | typedef size_t (*ZSTD_blockCompressor) ( | |
452 | ZSTD_matchState_t* bs, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], | |
453 | void const* src, size_t srcSize); | |
2aa14b1a | 454 | ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_paramSwitch_e rowMatchfinderMode, ZSTD_dictMode_e dictMode); |
e0c1b49f NT |
455 | |
456 | ||
457 | MEM_STATIC U32 ZSTD_LLcode(U32 litLength) | |
458 | { | |
459 | static const BYTE LL_Code[64] = { 0, 1, 2, 3, 4, 5, 6, 7, | |
460 | 8, 9, 10, 11, 12, 13, 14, 15, | |
461 | 16, 16, 17, 17, 18, 18, 19, 19, | |
462 | 20, 20, 20, 20, 21, 21, 21, 21, | |
463 | 22, 22, 22, 22, 22, 22, 22, 22, | |
464 | 23, 23, 23, 23, 23, 23, 23, 23, | |
465 | 24, 24, 24, 24, 24, 24, 24, 24, | |
466 | 24, 24, 24, 24, 24, 24, 24, 24 }; | |
467 | static const U32 LL_deltaCode = 19; | |
468 | return (litLength > 63) ? ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength]; | |
469 | } | |
470 | ||
471 | /* ZSTD_MLcode() : | |
472 | * note : mlBase = matchLength - MINMATCH; | |
473 | * because it's the format it's stored in seqStore->sequences */ | |
474 | MEM_STATIC U32 ZSTD_MLcode(U32 mlBase) | |
475 | { | |
476 | static const BYTE ML_Code[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, | |
477 | 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, | |
478 | 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37, | |
479 | 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, | |
480 | 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, | |
481 | 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, | |
482 | 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, | |
483 | 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 }; | |
484 | static const U32 ML_deltaCode = 36; | |
485 | return (mlBase > 127) ? ZSTD_highbit32(mlBase) + ML_deltaCode : ML_Code[mlBase]; | |
486 | } | |
487 | ||
e0c1b49f NT |
488 | /* ZSTD_cParam_withinBounds: |
489 | * @return 1 if value is within cParam bounds, | |
490 | * 0 otherwise */ | |
491 | MEM_STATIC int ZSTD_cParam_withinBounds(ZSTD_cParameter cParam, int value) | |
492 | { | |
493 | ZSTD_bounds const bounds = ZSTD_cParam_getBounds(cParam); | |
494 | if (ZSTD_isError(bounds.error)) return 0; | |
495 | if (value < bounds.lowerBound) return 0; | |
496 | if (value > bounds.upperBound) return 0; | |
497 | return 1; | |
498 | } | |
499 | ||
500 | /* ZSTD_noCompressBlock() : | |
501 | * Writes uncompressed block to dst buffer from given src. | |
502 | * Returns the size of the block */ | |
503 | MEM_STATIC size_t ZSTD_noCompressBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize, U32 lastBlock) | |
504 | { | |
505 | U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(srcSize << 3); | |
506 | RETURN_ERROR_IF(srcSize + ZSTD_blockHeaderSize > dstCapacity, | |
507 | dstSize_tooSmall, "dst buf too small for uncompressed block"); | |
508 | MEM_writeLE24(dst, cBlockHeader24); | |
509 | ZSTD_memcpy((BYTE*)dst + ZSTD_blockHeaderSize, src, srcSize); | |
510 | return ZSTD_blockHeaderSize + srcSize; | |
511 | } | |
512 | ||
513 | MEM_STATIC size_t ZSTD_rleCompressBlock (void* dst, size_t dstCapacity, BYTE src, size_t srcSize, U32 lastBlock) | |
514 | { | |
515 | BYTE* const op = (BYTE*)dst; | |
516 | U32 const cBlockHeader = lastBlock + (((U32)bt_rle)<<1) + (U32)(srcSize << 3); | |
517 | RETURN_ERROR_IF(dstCapacity < 4, dstSize_tooSmall, ""); | |
518 | MEM_writeLE24(op, cBlockHeader); | |
519 | op[3] = src; | |
520 | return 4; | |
521 | } | |
522 | ||
523 | ||
524 | /* ZSTD_minGain() : | |
525 | * minimum compression required | |
526 | * to generate a compress block or a compressed literals section. | |
527 | * note : use same formula for both situations */ | |
528 | MEM_STATIC size_t ZSTD_minGain(size_t srcSize, ZSTD_strategy strat) | |
529 | { | |
530 | U32 const minlog = (strat>=ZSTD_btultra) ? (U32)(strat) - 1 : 6; | |
531 | ZSTD_STATIC_ASSERT(ZSTD_btultra == 8); | |
532 | assert(ZSTD_cParam_withinBounds(ZSTD_c_strategy, strat)); | |
533 | return (srcSize >> minlog) + 2; | |
534 | } | |
535 | ||
2aa14b1a | 536 | MEM_STATIC int ZSTD_literalsCompressionIsDisabled(const ZSTD_CCtx_params* cctxParams) |
e0c1b49f NT |
537 | { |
538 | switch (cctxParams->literalCompressionMode) { | |
2aa14b1a | 539 | case ZSTD_ps_enable: |
e0c1b49f | 540 | return 0; |
2aa14b1a | 541 | case ZSTD_ps_disable: |
e0c1b49f NT |
542 | return 1; |
543 | default: | |
544 | assert(0 /* impossible: pre-validated */); | |
545 | ZSTD_FALLTHROUGH; | |
2aa14b1a | 546 | case ZSTD_ps_auto: |
e0c1b49f NT |
547 | return (cctxParams->cParams.strategy == ZSTD_fast) && (cctxParams->cParams.targetLength > 0); |
548 | } | |
549 | } | |
550 | ||
551 | /*! ZSTD_safecopyLiterals() : | |
552 | * memcpy() function that won't read beyond more than WILDCOPY_OVERLENGTH bytes past ilimit_w. | |
553 | * Only called when the sequence ends past ilimit_w, so it only needs to be optimized for single | |
554 | * large copies. | |
555 | */ | |
2aa14b1a NT |
556 | static void |
557 | ZSTD_safecopyLiterals(BYTE* op, BYTE const* ip, BYTE const* const iend, BYTE const* ilimit_w) | |
558 | { | |
e0c1b49f NT |
559 | assert(iend > ilimit_w); |
560 | if (ip <= ilimit_w) { | |
561 | ZSTD_wildcopy(op, ip, ilimit_w - ip, ZSTD_no_overlap); | |
562 | op += ilimit_w - ip; | |
563 | ip = ilimit_w; | |
564 | } | |
565 | while (ip < iend) *op++ = *ip++; | |
566 | } | |
567 | ||
2aa14b1a NT |
568 | #define ZSTD_REP_MOVE (ZSTD_REP_NUM-1) |
569 | #define STORE_REPCODE_1 STORE_REPCODE(1) | |
570 | #define STORE_REPCODE_2 STORE_REPCODE(2) | |
571 | #define STORE_REPCODE_3 STORE_REPCODE(3) | |
572 | #define STORE_REPCODE(r) (assert((r)>=1), assert((r)<=3), (r)-1) | |
573 | #define STORE_OFFSET(o) (assert((o)>0), o + ZSTD_REP_MOVE) | |
574 | #define STORED_IS_OFFSET(o) ((o) > ZSTD_REP_MOVE) | |
575 | #define STORED_IS_REPCODE(o) ((o) <= ZSTD_REP_MOVE) | |
576 | #define STORED_OFFSET(o) (assert(STORED_IS_OFFSET(o)), (o)-ZSTD_REP_MOVE) | |
577 | #define STORED_REPCODE(o) (assert(STORED_IS_REPCODE(o)), (o)+1) /* returns ID 1,2,3 */ | |
578 | #define STORED_TO_OFFBASE(o) ((o)+1) | |
579 | #define OFFBASE_TO_STORED(o) ((o)-1) | |
580 | ||
e0c1b49f | 581 | /*! ZSTD_storeSeq() : |
2aa14b1a NT |
582 | * Store a sequence (litlen, litPtr, offCode and matchLength) into seqStore_t. |
583 | * @offBase_minus1 : Users should use employ macros STORE_REPCODE_X and STORE_OFFSET(). | |
584 | * @matchLength : must be >= MINMATCH | |
e0c1b49f NT |
585 | * Allowed to overread literals up to litLimit. |
586 | */ | |
2aa14b1a NT |
587 | HINT_INLINE UNUSED_ATTR void |
588 | ZSTD_storeSeq(seqStore_t* seqStorePtr, | |
589 | size_t litLength, const BYTE* literals, const BYTE* litLimit, | |
590 | U32 offBase_minus1, | |
591 | size_t matchLength) | |
e0c1b49f NT |
592 | { |
593 | BYTE const* const litLimit_w = litLimit - WILDCOPY_OVERLENGTH; | |
594 | BYTE const* const litEnd = literals + litLength; | |
595 | #if defined(DEBUGLEVEL) && (DEBUGLEVEL >= 6) | |
596 | static const BYTE* g_start = NULL; | |
597 | if (g_start==NULL) g_start = (const BYTE*)literals; /* note : index only works for compression within a single segment */ | |
598 | { U32 const pos = (U32)((const BYTE*)literals - g_start); | |
599 | DEBUGLOG(6, "Cpos%7u :%3u literals, match%4u bytes at offCode%7u", | |
2aa14b1a | 600 | pos, (U32)litLength, (U32)matchLength, (U32)offBase_minus1); |
e0c1b49f NT |
601 | } |
602 | #endif | |
603 | assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq); | |
604 | /* copy Literals */ | |
605 | assert(seqStorePtr->maxNbLit <= 128 KB); | |
606 | assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit); | |
607 | assert(literals + litLength <= litLimit); | |
608 | if (litEnd <= litLimit_w) { | |
609 | /* Common case we can use wildcopy. | |
610 | * First copy 16 bytes, because literals are likely short. | |
611 | */ | |
612 | assert(WILDCOPY_OVERLENGTH >= 16); | |
613 | ZSTD_copy16(seqStorePtr->lit, literals); | |
614 | if (litLength > 16) { | |
615 | ZSTD_wildcopy(seqStorePtr->lit+16, literals+16, (ptrdiff_t)litLength-16, ZSTD_no_overlap); | |
616 | } | |
617 | } else { | |
618 | ZSTD_safecopyLiterals(seqStorePtr->lit, literals, litEnd, litLimit_w); | |
619 | } | |
620 | seqStorePtr->lit += litLength; | |
621 | ||
622 | /* literal Length */ | |
623 | if (litLength>0xFFFF) { | |
2aa14b1a NT |
624 | assert(seqStorePtr->longLengthType == ZSTD_llt_none); /* there can only be a single long length */ |
625 | seqStorePtr->longLengthType = ZSTD_llt_literalLength; | |
e0c1b49f NT |
626 | seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); |
627 | } | |
628 | seqStorePtr->sequences[0].litLength = (U16)litLength; | |
629 | ||
630 | /* match offset */ | |
2aa14b1a | 631 | seqStorePtr->sequences[0].offBase = STORED_TO_OFFBASE(offBase_minus1); |
e0c1b49f NT |
632 | |
633 | /* match Length */ | |
2aa14b1a NT |
634 | assert(matchLength >= MINMATCH); |
635 | { size_t const mlBase = matchLength - MINMATCH; | |
636 | if (mlBase>0xFFFF) { | |
637 | assert(seqStorePtr->longLengthType == ZSTD_llt_none); /* there can only be a single long length */ | |
638 | seqStorePtr->longLengthType = ZSTD_llt_matchLength; | |
639 | seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); | |
640 | } | |
641 | seqStorePtr->sequences[0].mlBase = (U16)mlBase; | |
e0c1b49f | 642 | } |
e0c1b49f NT |
643 | |
644 | seqStorePtr->sequences++; | |
645 | } | |
646 | ||
2aa14b1a NT |
647 | /* ZSTD_updateRep() : |
648 | * updates in-place @rep (array of repeat offsets) | |
649 | * @offBase_minus1 : sum-type, with same numeric representation as ZSTD_storeSeq() | |
650 | */ | |
651 | MEM_STATIC void | |
652 | ZSTD_updateRep(U32 rep[ZSTD_REP_NUM], U32 const offBase_minus1, U32 const ll0) | |
653 | { | |
654 | if (STORED_IS_OFFSET(offBase_minus1)) { /* full offset */ | |
655 | rep[2] = rep[1]; | |
656 | rep[1] = rep[0]; | |
657 | rep[0] = STORED_OFFSET(offBase_minus1); | |
658 | } else { /* repcode */ | |
659 | U32 const repCode = STORED_REPCODE(offBase_minus1) - 1 + ll0; | |
660 | if (repCode > 0) { /* note : if repCode==0, no change */ | |
661 | U32 const currentOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode]; | |
662 | rep[2] = (repCode >= 2) ? rep[1] : rep[2]; | |
663 | rep[1] = rep[0]; | |
664 | rep[0] = currentOffset; | |
665 | } else { /* repCode == 0 */ | |
666 | /* nothing to do */ | |
667 | } | |
668 | } | |
669 | } | |
670 | ||
671 | typedef struct repcodes_s { | |
672 | U32 rep[3]; | |
673 | } repcodes_t; | |
674 | ||
675 | MEM_STATIC repcodes_t | |
676 | ZSTD_newRep(U32 const rep[ZSTD_REP_NUM], U32 const offBase_minus1, U32 const ll0) | |
677 | { | |
678 | repcodes_t newReps; | |
679 | ZSTD_memcpy(&newReps, rep, sizeof(newReps)); | |
680 | ZSTD_updateRep(newReps.rep, offBase_minus1, ll0); | |
681 | return newReps; | |
682 | } | |
683 | ||
e0c1b49f NT |
684 | |
685 | /*-************************************* | |
686 | * Match length counter | |
687 | ***************************************/ | |
688 | static unsigned ZSTD_NbCommonBytes (size_t val) | |
689 | { | |
690 | if (MEM_isLittleEndian()) { | |
691 | if (MEM_64bits()) { | |
692 | # if (__GNUC__ >= 4) | |
693 | return (__builtin_ctzll((U64)val) >> 3); | |
694 | # else | |
695 | static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, | |
696 | 0, 3, 1, 3, 1, 4, 2, 7, | |
697 | 0, 2, 3, 6, 1, 5, 3, 5, | |
698 | 1, 3, 4, 4, 2, 5, 6, 7, | |
699 | 7, 0, 1, 2, 3, 3, 4, 6, | |
700 | 2, 6, 5, 5, 3, 4, 5, 6, | |
701 | 7, 1, 2, 4, 6, 4, 4, 5, | |
702 | 7, 2, 6, 5, 7, 6, 7, 7 }; | |
703 | return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58]; | |
704 | # endif | |
705 | } else { /* 32 bits */ | |
706 | # if (__GNUC__ >= 3) | |
707 | return (__builtin_ctz((U32)val) >> 3); | |
708 | # else | |
709 | static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, | |
710 | 3, 2, 2, 1, 3, 2, 0, 1, | |
711 | 3, 3, 1, 2, 2, 2, 2, 0, | |
712 | 3, 1, 2, 0, 1, 0, 1, 1 }; | |
713 | return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; | |
714 | # endif | |
715 | } | |
716 | } else { /* Big Endian CPU */ | |
717 | if (MEM_64bits()) { | |
718 | # if (__GNUC__ >= 4) | |
719 | return (__builtin_clzll(val) >> 3); | |
720 | # else | |
721 | unsigned r; | |
722 | const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */ | |
723 | if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; } | |
724 | if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } | |
725 | r += (!val); | |
726 | return r; | |
727 | # endif | |
728 | } else { /* 32 bits */ | |
729 | # if (__GNUC__ >= 3) | |
730 | return (__builtin_clz((U32)val) >> 3); | |
731 | # else | |
732 | unsigned r; | |
733 | if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } | |
734 | r += (!val); | |
735 | return r; | |
736 | # endif | |
737 | } } | |
738 | } | |
739 | ||
740 | ||
741 | MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit) | |
742 | { | |
743 | const BYTE* const pStart = pIn; | |
744 | const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1); | |
745 | ||
746 | if (pIn < pInLoopLimit) { | |
747 | { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn); | |
748 | if (diff) return ZSTD_NbCommonBytes(diff); } | |
749 | pIn+=sizeof(size_t); pMatch+=sizeof(size_t); | |
750 | while (pIn < pInLoopLimit) { | |
751 | size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn); | |
752 | if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; } | |
753 | pIn += ZSTD_NbCommonBytes(diff); | |
754 | return (size_t)(pIn - pStart); | |
755 | } } | |
756 | if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; } | |
757 | if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; } | |
758 | if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++; | |
759 | return (size_t)(pIn - pStart); | |
760 | } | |
761 | ||
762 | /* ZSTD_count_2segments() : | |
763 | * can count match length with `ip` & `match` in 2 different segments. | |
764 | * convention : on reaching mEnd, match count continue starting from iStart | |
765 | */ | |
766 | MEM_STATIC size_t | |
767 | ZSTD_count_2segments(const BYTE* ip, const BYTE* match, | |
768 | const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart) | |
769 | { | |
770 | const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd); | |
771 | size_t const matchLength = ZSTD_count(ip, match, vEnd); | |
772 | if (match + matchLength != mEnd) return matchLength; | |
773 | DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength); | |
774 | DEBUGLOG(7, "distance from match beginning to end dictionary = %zi", mEnd - match); | |
775 | DEBUGLOG(7, "distance from current pos to end buffer = %zi", iEnd - ip); | |
776 | DEBUGLOG(7, "next byte : ip==%02X, istart==%02X", ip[matchLength], *iStart); | |
777 | DEBUGLOG(7, "final match length = %zu", matchLength + ZSTD_count(ip+matchLength, iStart, iEnd)); | |
778 | return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd); | |
779 | } | |
780 | ||
781 | ||
782 | /*-************************************* | |
783 | * Hashes | |
784 | ***************************************/ | |
785 | static const U32 prime3bytes = 506832829U; | |
786 | static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; } | |
787 | MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */ | |
788 | ||
789 | static const U32 prime4bytes = 2654435761U; | |
790 | static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; } | |
791 | static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); } | |
792 | ||
793 | static const U64 prime5bytes = 889523592379ULL; | |
794 | static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h)) ; } | |
795 | static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); } | |
796 | ||
797 | static const U64 prime6bytes = 227718039650203ULL; | |
798 | static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; } | |
799 | static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); } | |
800 | ||
801 | static const U64 prime7bytes = 58295818150454627ULL; | |
802 | static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h)) ; } | |
803 | static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); } | |
804 | ||
805 | static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL; | |
806 | static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; } | |
807 | static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); } | |
808 | ||
809 | MEM_STATIC FORCE_INLINE_ATTR | |
810 | size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls) | |
811 | { | |
812 | switch(mls) | |
813 | { | |
814 | default: | |
815 | case 4: return ZSTD_hash4Ptr(p, hBits); | |
816 | case 5: return ZSTD_hash5Ptr(p, hBits); | |
817 | case 6: return ZSTD_hash6Ptr(p, hBits); | |
818 | case 7: return ZSTD_hash7Ptr(p, hBits); | |
819 | case 8: return ZSTD_hash8Ptr(p, hBits); | |
820 | } | |
821 | } | |
822 | ||
823 | /* ZSTD_ipow() : | |
824 | * Return base^exponent. | |
825 | */ | |
826 | static U64 ZSTD_ipow(U64 base, U64 exponent) | |
827 | { | |
828 | U64 power = 1; | |
829 | while (exponent) { | |
830 | if (exponent & 1) power *= base; | |
831 | exponent >>= 1; | |
832 | base *= base; | |
833 | } | |
834 | return power; | |
835 | } | |
836 | ||
837 | #define ZSTD_ROLL_HASH_CHAR_OFFSET 10 | |
838 | ||
839 | /* ZSTD_rollingHash_append() : | |
840 | * Add the buffer to the hash value. | |
841 | */ | |
842 | static U64 ZSTD_rollingHash_append(U64 hash, void const* buf, size_t size) | |
843 | { | |
844 | BYTE const* istart = (BYTE const*)buf; | |
845 | size_t pos; | |
846 | for (pos = 0; pos < size; ++pos) { | |
847 | hash *= prime8bytes; | |
848 | hash += istart[pos] + ZSTD_ROLL_HASH_CHAR_OFFSET; | |
849 | } | |
850 | return hash; | |
851 | } | |
852 | ||
853 | /* ZSTD_rollingHash_compute() : | |
854 | * Compute the rolling hash value of the buffer. | |
855 | */ | |
856 | MEM_STATIC U64 ZSTD_rollingHash_compute(void const* buf, size_t size) | |
857 | { | |
858 | return ZSTD_rollingHash_append(0, buf, size); | |
859 | } | |
860 | ||
861 | /* ZSTD_rollingHash_primePower() : | |
862 | * Compute the primePower to be passed to ZSTD_rollingHash_rotate() for a hash | |
863 | * over a window of length bytes. | |
864 | */ | |
865 | MEM_STATIC U64 ZSTD_rollingHash_primePower(U32 length) | |
866 | { | |
867 | return ZSTD_ipow(prime8bytes, length - 1); | |
868 | } | |
869 | ||
870 | /* ZSTD_rollingHash_rotate() : | |
871 | * Rotate the rolling hash by one byte. | |
872 | */ | |
873 | MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower) | |
874 | { | |
875 | hash -= (toRemove + ZSTD_ROLL_HASH_CHAR_OFFSET) * primePower; | |
876 | hash *= prime8bytes; | |
877 | hash += toAdd + ZSTD_ROLL_HASH_CHAR_OFFSET; | |
878 | return hash; | |
879 | } | |
880 | ||
881 | /*-************************************* | |
882 | * Round buffer management | |
883 | ***************************************/ | |
884 | #if (ZSTD_WINDOWLOG_MAX_64 > 31) | |
885 | # error "ZSTD_WINDOWLOG_MAX is too large : would overflow ZSTD_CURRENT_MAX" | |
886 | #endif | |
887 | /* Max current allowed */ | |
888 | #define ZSTD_CURRENT_MAX ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX)) | |
889 | /* Maximum chunk size before overflow correction needs to be called again */ | |
890 | #define ZSTD_CHUNKSIZE_MAX \ | |
891 | ( ((U32)-1) /* Maximum ending current index */ \ | |
892 | - ZSTD_CURRENT_MAX) /* Maximum beginning lowLimit */ | |
893 | ||
894 | /* | |
895 | * ZSTD_window_clear(): | |
896 | * Clears the window containing the history by simply setting it to empty. | |
897 | */ | |
898 | MEM_STATIC void ZSTD_window_clear(ZSTD_window_t* window) | |
899 | { | |
900 | size_t const endT = (size_t)(window->nextSrc - window->base); | |
901 | U32 const end = (U32)endT; | |
902 | ||
903 | window->lowLimit = end; | |
904 | window->dictLimit = end; | |
905 | } | |
906 | ||
2aa14b1a NT |
907 | MEM_STATIC U32 ZSTD_window_isEmpty(ZSTD_window_t const window) |
908 | { | |
909 | return window.dictLimit == ZSTD_WINDOW_START_INDEX && | |
910 | window.lowLimit == ZSTD_WINDOW_START_INDEX && | |
911 | (window.nextSrc - window.base) == ZSTD_WINDOW_START_INDEX; | |
912 | } | |
913 | ||
e0c1b49f NT |
914 | /* |
915 | * ZSTD_window_hasExtDict(): | |
916 | * Returns non-zero if the window has a non-empty extDict. | |
917 | */ | |
918 | MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window) | |
919 | { | |
920 | return window.lowLimit < window.dictLimit; | |
921 | } | |
922 | ||
923 | /* | |
924 | * ZSTD_matchState_dictMode(): | |
925 | * Inspects the provided matchState and figures out what dictMode should be | |
926 | * passed to the compressor. | |
927 | */ | |
928 | MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms) | |
929 | { | |
930 | return ZSTD_window_hasExtDict(ms->window) ? | |
931 | ZSTD_extDict : | |
932 | ms->dictMatchState != NULL ? | |
933 | (ms->dictMatchState->dedicatedDictSearch ? ZSTD_dedicatedDictSearch : ZSTD_dictMatchState) : | |
934 | ZSTD_noDict; | |
935 | } | |
936 | ||
2aa14b1a NT |
937 | /* Defining this macro to non-zero tells zstd to run the overflow correction |
938 | * code much more frequently. This is very inefficient, and should only be | |
939 | * used for tests and fuzzers. | |
940 | */ | |
941 | #ifndef ZSTD_WINDOW_OVERFLOW_CORRECT_FREQUENTLY | |
942 | # ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION | |
943 | # define ZSTD_WINDOW_OVERFLOW_CORRECT_FREQUENTLY 1 | |
944 | # else | |
945 | # define ZSTD_WINDOW_OVERFLOW_CORRECT_FREQUENTLY 0 | |
946 | # endif | |
947 | #endif | |
948 | ||
949 | /* | |
950 | * ZSTD_window_canOverflowCorrect(): | |
951 | * Returns non-zero if the indices are large enough for overflow correction | |
952 | * to work correctly without impacting compression ratio. | |
953 | */ | |
954 | MEM_STATIC U32 ZSTD_window_canOverflowCorrect(ZSTD_window_t const window, | |
955 | U32 cycleLog, | |
956 | U32 maxDist, | |
957 | U32 loadedDictEnd, | |
958 | void const* src) | |
959 | { | |
960 | U32 const cycleSize = 1u << cycleLog; | |
961 | U32 const curr = (U32)((BYTE const*)src - window.base); | |
962 | U32 const minIndexToOverflowCorrect = cycleSize | |
963 | + MAX(maxDist, cycleSize) | |
964 | + ZSTD_WINDOW_START_INDEX; | |
965 | ||
966 | /* Adjust the min index to backoff the overflow correction frequency, | |
967 | * so we don't waste too much CPU in overflow correction. If this | |
968 | * computation overflows we don't really care, we just need to make | |
969 | * sure it is at least minIndexToOverflowCorrect. | |
970 | */ | |
971 | U32 const adjustment = window.nbOverflowCorrections + 1; | |
972 | U32 const adjustedIndex = MAX(minIndexToOverflowCorrect * adjustment, | |
973 | minIndexToOverflowCorrect); | |
974 | U32 const indexLargeEnough = curr > adjustedIndex; | |
975 | ||
976 | /* Only overflow correct early if the dictionary is invalidated already, | |
977 | * so we don't hurt compression ratio. | |
978 | */ | |
979 | U32 const dictionaryInvalidated = curr > maxDist + loadedDictEnd; | |
980 | ||
981 | return indexLargeEnough && dictionaryInvalidated; | |
982 | } | |
983 | ||
e0c1b49f NT |
984 | /* |
985 | * ZSTD_window_needOverflowCorrection(): | |
986 | * Returns non-zero if the indices are getting too large and need overflow | |
987 | * protection. | |
988 | */ | |
989 | MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window, | |
2aa14b1a NT |
990 | U32 cycleLog, |
991 | U32 maxDist, | |
992 | U32 loadedDictEnd, | |
993 | void const* src, | |
e0c1b49f NT |
994 | void const* srcEnd) |
995 | { | |
996 | U32 const curr = (U32)((BYTE const*)srcEnd - window.base); | |
2aa14b1a NT |
997 | if (ZSTD_WINDOW_OVERFLOW_CORRECT_FREQUENTLY) { |
998 | if (ZSTD_window_canOverflowCorrect(window, cycleLog, maxDist, loadedDictEnd, src)) { | |
999 | return 1; | |
1000 | } | |
1001 | } | |
e0c1b49f NT |
1002 | return curr > ZSTD_CURRENT_MAX; |
1003 | } | |
1004 | ||
1005 | /* | |
1006 | * ZSTD_window_correctOverflow(): | |
1007 | * Reduces the indices to protect from index overflow. | |
1008 | * Returns the correction made to the indices, which must be applied to every | |
1009 | * stored index. | |
1010 | * | |
1011 | * The least significant cycleLog bits of the indices must remain the same, | |
1012 | * which may be 0. Every index up to maxDist in the past must be valid. | |
e0c1b49f NT |
1013 | */ |
1014 | MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t* window, U32 cycleLog, | |
1015 | U32 maxDist, void const* src) | |
1016 | { | |
1017 | /* preemptive overflow correction: | |
1018 | * 1. correction is large enough: | |
1019 | * lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog | |
1020 | * 1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog | |
1021 | * | |
1022 | * current - newCurrent | |
1023 | * > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog) | |
1024 | * > (3<<29) - (1<<chainLog) | |
1025 | * > (3<<29) - (1<<30) (NOTE: chainLog <= 30) | |
1026 | * > 1<<29 | |
1027 | * | |
1028 | * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow: | |
1029 | * After correction, current is less than (1<<chainLog + 1<<windowLog). | |
1030 | * In 64-bit mode we are safe, because we have 64-bit ptrdiff_t. | |
1031 | * In 32-bit mode we are safe, because (chainLog <= 29), so | |
1032 | * ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32. | |
1033 | * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32: | |
1034 | * windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32. | |
1035 | */ | |
2aa14b1a NT |
1036 | U32 const cycleSize = 1u << cycleLog; |
1037 | U32 const cycleMask = cycleSize - 1; | |
e0c1b49f | 1038 | U32 const curr = (U32)((BYTE const*)src - window->base); |
2aa14b1a NT |
1039 | U32 const currentCycle = curr & cycleMask; |
1040 | /* Ensure newCurrent - maxDist >= ZSTD_WINDOW_START_INDEX. */ | |
1041 | U32 const currentCycleCorrection = currentCycle < ZSTD_WINDOW_START_INDEX | |
1042 | ? MAX(cycleSize, ZSTD_WINDOW_START_INDEX) | |
1043 | : 0; | |
1044 | U32 const newCurrent = currentCycle | |
1045 | + currentCycleCorrection | |
1046 | + MAX(maxDist, cycleSize); | |
e0c1b49f | 1047 | U32 const correction = curr - newCurrent; |
2aa14b1a NT |
1048 | /* maxDist must be a power of two so that: |
1049 | * (newCurrent & cycleMask) == (curr & cycleMask) | |
1050 | * This is required to not corrupt the chains / binary tree. | |
1051 | */ | |
1052 | assert((maxDist & (maxDist - 1)) == 0); | |
1053 | assert((curr & cycleMask) == (newCurrent & cycleMask)); | |
e0c1b49f | 1054 | assert(curr > newCurrent); |
2aa14b1a NT |
1055 | if (!ZSTD_WINDOW_OVERFLOW_CORRECT_FREQUENTLY) { |
1056 | /* Loose bound, should be around 1<<29 (see above) */ | |
1057 | assert(correction > 1<<28); | |
1058 | } | |
e0c1b49f NT |
1059 | |
1060 | window->base += correction; | |
1061 | window->dictBase += correction; | |
2aa14b1a NT |
1062 | if (window->lowLimit < correction + ZSTD_WINDOW_START_INDEX) { |
1063 | window->lowLimit = ZSTD_WINDOW_START_INDEX; | |
1064 | } else { | |
1065 | window->lowLimit -= correction; | |
1066 | } | |
1067 | if (window->dictLimit < correction + ZSTD_WINDOW_START_INDEX) { | |
1068 | window->dictLimit = ZSTD_WINDOW_START_INDEX; | |
1069 | } else { | |
1070 | window->dictLimit -= correction; | |
1071 | } | |
e0c1b49f NT |
1072 | |
1073 | /* Ensure we can still reference the full window. */ | |
1074 | assert(newCurrent >= maxDist); | |
2aa14b1a | 1075 | assert(newCurrent - maxDist >= ZSTD_WINDOW_START_INDEX); |
e0c1b49f NT |
1076 | /* Ensure that lowLimit and dictLimit didn't underflow. */ |
1077 | assert(window->lowLimit <= newCurrent); | |
1078 | assert(window->dictLimit <= newCurrent); | |
1079 | ||
2aa14b1a NT |
1080 | ++window->nbOverflowCorrections; |
1081 | ||
e0c1b49f NT |
1082 | DEBUGLOG(4, "Correction of 0x%x bytes to lowLimit=0x%x", correction, |
1083 | window->lowLimit); | |
1084 | return correction; | |
1085 | } | |
1086 | ||
1087 | /* | |
1088 | * ZSTD_window_enforceMaxDist(): | |
1089 | * Updates lowLimit so that: | |
1090 | * (srcEnd - base) - lowLimit == maxDist + loadedDictEnd | |
1091 | * | |
1092 | * It ensures index is valid as long as index >= lowLimit. | |
1093 | * This must be called before a block compression call. | |
1094 | * | |
1095 | * loadedDictEnd is only defined if a dictionary is in use for current compression. | |
1096 | * As the name implies, loadedDictEnd represents the index at end of dictionary. | |
1097 | * The value lies within context's referential, it can be directly compared to blockEndIdx. | |
1098 | * | |
1099 | * If loadedDictEndPtr is NULL, no dictionary is in use, and we use loadedDictEnd == 0. | |
1100 | * If loadedDictEndPtr is not NULL, we set it to zero after updating lowLimit. | |
1101 | * This is because dictionaries are allowed to be referenced fully | |
1102 | * as long as the last byte of the dictionary is in the window. | |
1103 | * Once input has progressed beyond window size, dictionary cannot be referenced anymore. | |
1104 | * | |
1105 | * In normal dict mode, the dictionary lies between lowLimit and dictLimit. | |
1106 | * In dictMatchState mode, lowLimit and dictLimit are the same, | |
1107 | * and the dictionary is below them. | |
1108 | * forceWindow and dictMatchState are therefore incompatible. | |
1109 | */ | |
1110 | MEM_STATIC void | |
1111 | ZSTD_window_enforceMaxDist(ZSTD_window_t* window, | |
1112 | const void* blockEnd, | |
1113 | U32 maxDist, | |
1114 | U32* loadedDictEndPtr, | |
1115 | const ZSTD_matchState_t** dictMatchStatePtr) | |
1116 | { | |
1117 | U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base); | |
1118 | U32 const loadedDictEnd = (loadedDictEndPtr != NULL) ? *loadedDictEndPtr : 0; | |
1119 | DEBUGLOG(5, "ZSTD_window_enforceMaxDist: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u", | |
1120 | (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd); | |
1121 | ||
1122 | /* - When there is no dictionary : loadedDictEnd == 0. | |
1123 | In which case, the test (blockEndIdx > maxDist) is merely to avoid | |
1124 | overflowing next operation `newLowLimit = blockEndIdx - maxDist`. | |
1125 | - When there is a standard dictionary : | |
1126 | Index referential is copied from the dictionary, | |
1127 | which means it starts from 0. | |
1128 | In which case, loadedDictEnd == dictSize, | |
1129 | and it makes sense to compare `blockEndIdx > maxDist + dictSize` | |
1130 | since `blockEndIdx` also starts from zero. | |
1131 | - When there is an attached dictionary : | |
1132 | loadedDictEnd is expressed within the referential of the context, | |
1133 | so it can be directly compared against blockEndIdx. | |
1134 | */ | |
1135 | if (blockEndIdx > maxDist + loadedDictEnd) { | |
1136 | U32 const newLowLimit = blockEndIdx - maxDist; | |
1137 | if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit; | |
1138 | if (window->dictLimit < window->lowLimit) { | |
1139 | DEBUGLOG(5, "Update dictLimit to match lowLimit, from %u to %u", | |
1140 | (unsigned)window->dictLimit, (unsigned)window->lowLimit); | |
1141 | window->dictLimit = window->lowLimit; | |
1142 | } | |
1143 | /* On reaching window size, dictionaries are invalidated */ | |
1144 | if (loadedDictEndPtr) *loadedDictEndPtr = 0; | |
1145 | if (dictMatchStatePtr) *dictMatchStatePtr = NULL; | |
1146 | } | |
1147 | } | |
1148 | ||
1149 | /* Similar to ZSTD_window_enforceMaxDist(), | |
1150 | * but only invalidates dictionary | |
1151 | * when input progresses beyond window size. | |
1152 | * assumption : loadedDictEndPtr and dictMatchStatePtr are valid (non NULL) | |
1153 | * loadedDictEnd uses same referential as window->base | |
1154 | * maxDist is the window size */ | |
1155 | MEM_STATIC void | |
1156 | ZSTD_checkDictValidity(const ZSTD_window_t* window, | |
1157 | const void* blockEnd, | |
1158 | U32 maxDist, | |
1159 | U32* loadedDictEndPtr, | |
1160 | const ZSTD_matchState_t** dictMatchStatePtr) | |
1161 | { | |
1162 | assert(loadedDictEndPtr != NULL); | |
1163 | assert(dictMatchStatePtr != NULL); | |
1164 | { U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base); | |
1165 | U32 const loadedDictEnd = *loadedDictEndPtr; | |
1166 | DEBUGLOG(5, "ZSTD_checkDictValidity: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u", | |
1167 | (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd); | |
1168 | assert(blockEndIdx >= loadedDictEnd); | |
1169 | ||
1170 | if (blockEndIdx > loadedDictEnd + maxDist) { | |
1171 | /* On reaching window size, dictionaries are invalidated. | |
1172 | * For simplification, if window size is reached anywhere within next block, | |
1173 | * the dictionary is invalidated for the full block. | |
1174 | */ | |
1175 | DEBUGLOG(6, "invalidating dictionary for current block (distance > windowSize)"); | |
1176 | *loadedDictEndPtr = 0; | |
1177 | *dictMatchStatePtr = NULL; | |
1178 | } else { | |
1179 | if (*loadedDictEndPtr != 0) { | |
1180 | DEBUGLOG(6, "dictionary considered valid for current block"); | |
1181 | } } } | |
1182 | } | |
1183 | ||
1184 | MEM_STATIC void ZSTD_window_init(ZSTD_window_t* window) { | |
1185 | ZSTD_memset(window, 0, sizeof(*window)); | |
2aa14b1a NT |
1186 | window->base = (BYTE const*)" "; |
1187 | window->dictBase = (BYTE const*)" "; | |
1188 | ZSTD_STATIC_ASSERT(ZSTD_DUBT_UNSORTED_MARK < ZSTD_WINDOW_START_INDEX); /* Start above ZSTD_DUBT_UNSORTED_MARK */ | |
1189 | window->dictLimit = ZSTD_WINDOW_START_INDEX; /* start from >0, so that 1st position is valid */ | |
1190 | window->lowLimit = ZSTD_WINDOW_START_INDEX; /* it ensures first and later CCtx usages compress the same */ | |
1191 | window->nextSrc = window->base + ZSTD_WINDOW_START_INDEX; /* see issue #1241 */ | |
1192 | window->nbOverflowCorrections = 0; | |
e0c1b49f NT |
1193 | } |
1194 | ||
1195 | /* | |
1196 | * ZSTD_window_update(): | |
1197 | * Updates the window by appending [src, src + srcSize) to the window. | |
1198 | * If it is not contiguous, the current prefix becomes the extDict, and we | |
1199 | * forget about the extDict. Handles overlap of the prefix and extDict. | |
1200 | * Returns non-zero if the segment is contiguous. | |
1201 | */ | |
1202 | MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t* window, | |
2aa14b1a NT |
1203 | void const* src, size_t srcSize, |
1204 | int forceNonContiguous) | |
e0c1b49f NT |
1205 | { |
1206 | BYTE const* const ip = (BYTE const*)src; | |
1207 | U32 contiguous = 1; | |
1208 | DEBUGLOG(5, "ZSTD_window_update"); | |
1209 | if (srcSize == 0) | |
1210 | return contiguous; | |
1211 | assert(window->base != NULL); | |
1212 | assert(window->dictBase != NULL); | |
1213 | /* Check if blocks follow each other */ | |
2aa14b1a | 1214 | if (src != window->nextSrc || forceNonContiguous) { |
e0c1b49f NT |
1215 | /* not contiguous */ |
1216 | size_t const distanceFromBase = (size_t)(window->nextSrc - window->base); | |
1217 | DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit); | |
1218 | window->lowLimit = window->dictLimit; | |
1219 | assert(distanceFromBase == (size_t)(U32)distanceFromBase); /* should never overflow */ | |
1220 | window->dictLimit = (U32)distanceFromBase; | |
1221 | window->dictBase = window->base; | |
1222 | window->base = ip - distanceFromBase; | |
1223 | /* ms->nextToUpdate = window->dictLimit; */ | |
1224 | if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit; /* too small extDict */ | |
1225 | contiguous = 0; | |
1226 | } | |
1227 | window->nextSrc = ip + srcSize; | |
1228 | /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */ | |
1229 | if ( (ip+srcSize > window->dictBase + window->lowLimit) | |
1230 | & (ip < window->dictBase + window->dictLimit)) { | |
1231 | ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase; | |
1232 | U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)window->dictLimit) ? window->dictLimit : (U32)highInputIdx; | |
1233 | window->lowLimit = lowLimitMax; | |
1234 | DEBUGLOG(5, "Overlapping extDict and input : new lowLimit = %u", window->lowLimit); | |
1235 | } | |
1236 | return contiguous; | |
1237 | } | |
1238 | ||
1239 | /* | |
1240 | * Returns the lowest allowed match index. It may either be in the ext-dict or the prefix. | |
1241 | */ | |
1242 | MEM_STATIC U32 ZSTD_getLowestMatchIndex(const ZSTD_matchState_t* ms, U32 curr, unsigned windowLog) | |
1243 | { | |
2aa14b1a NT |
1244 | U32 const maxDistance = 1U << windowLog; |
1245 | U32 const lowestValid = ms->window.lowLimit; | |
1246 | U32 const withinWindow = (curr - lowestValid > maxDistance) ? curr - maxDistance : lowestValid; | |
1247 | U32 const isDictionary = (ms->loadedDictEnd != 0); | |
e0c1b49f NT |
1248 | /* When using a dictionary the entire dictionary is valid if a single byte of the dictionary |
1249 | * is within the window. We invalidate the dictionary (and set loadedDictEnd to 0) when it isn't | |
1250 | * valid for the entire block. So this check is sufficient to find the lowest valid match index. | |
1251 | */ | |
2aa14b1a | 1252 | U32 const matchLowest = isDictionary ? lowestValid : withinWindow; |
e0c1b49f NT |
1253 | return matchLowest; |
1254 | } | |
1255 | ||
1256 | /* | |
1257 | * Returns the lowest allowed match index in the prefix. | |
1258 | */ | |
1259 | MEM_STATIC U32 ZSTD_getLowestPrefixIndex(const ZSTD_matchState_t* ms, U32 curr, unsigned windowLog) | |
1260 | { | |
1261 | U32 const maxDistance = 1U << windowLog; | |
1262 | U32 const lowestValid = ms->window.dictLimit; | |
1263 | U32 const withinWindow = (curr - lowestValid > maxDistance) ? curr - maxDistance : lowestValid; | |
1264 | U32 const isDictionary = (ms->loadedDictEnd != 0); | |
1265 | /* When computing the lowest prefix index we need to take the dictionary into account to handle | |
1266 | * the edge case where the dictionary and the source are contiguous in memory. | |
1267 | */ | |
1268 | U32 const matchLowest = isDictionary ? lowestValid : withinWindow; | |
1269 | return matchLowest; | |
1270 | } | |
1271 | ||
1272 | ||
1273 | ||
1274 | /* debug functions */ | |
1275 | #if (DEBUGLEVEL>=2) | |
1276 | ||
1277 | MEM_STATIC double ZSTD_fWeight(U32 rawStat) | |
1278 | { | |
1279 | U32 const fp_accuracy = 8; | |
1280 | U32 const fp_multiplier = (1 << fp_accuracy); | |
1281 | U32 const newStat = rawStat + 1; | |
1282 | U32 const hb = ZSTD_highbit32(newStat); | |
1283 | U32 const BWeight = hb * fp_multiplier; | |
1284 | U32 const FWeight = (newStat << fp_accuracy) >> hb; | |
1285 | U32 const weight = BWeight + FWeight; | |
1286 | assert(hb + fp_accuracy < 31); | |
1287 | return (double)weight / fp_multiplier; | |
1288 | } | |
1289 | ||
1290 | /* display a table content, | |
1291 | * listing each element, its frequency, and its predicted bit cost */ | |
1292 | MEM_STATIC void ZSTD_debugTable(const U32* table, U32 max) | |
1293 | { | |
1294 | unsigned u, sum; | |
1295 | for (u=0, sum=0; u<=max; u++) sum += table[u]; | |
1296 | DEBUGLOG(2, "total nb elts: %u", sum); | |
1297 | for (u=0; u<=max; u++) { | |
1298 | DEBUGLOG(2, "%2u: %5u (%.2f)", | |
1299 | u, table[u], ZSTD_fWeight(sum) - ZSTD_fWeight(table[u]) ); | |
1300 | } | |
1301 | } | |
1302 | ||
1303 | #endif | |
1304 | ||
1305 | ||
1306 | ||
1307 | /* =============================================================== | |
1308 | * Shared internal declarations | |
1309 | * These prototypes may be called from sources not in lib/compress | |
1310 | * =============================================================== */ | |
1311 | ||
1312 | /* ZSTD_loadCEntropy() : | |
1313 | * dict : must point at beginning of a valid zstd dictionary. | |
1314 | * return : size of dictionary header (size of magic number + dict ID + entropy tables) | |
1315 | * assumptions : magic number supposed already checked | |
1316 | * and dictSize >= 8 */ | |
1317 | size_t ZSTD_loadCEntropy(ZSTD_compressedBlockState_t* bs, void* workspace, | |
1318 | const void* const dict, size_t dictSize); | |
1319 | ||
1320 | void ZSTD_reset_compressedBlockState(ZSTD_compressedBlockState_t* bs); | |
1321 | ||
1322 | /* ============================================================== | |
1323 | * Private declarations | |
1324 | * These prototypes shall only be called from within lib/compress | |
1325 | * ============================================================== */ | |
1326 | ||
1327 | /* ZSTD_getCParamsFromCCtxParams() : | |
1328 | * cParams are built depending on compressionLevel, src size hints, | |
1329 | * LDM and manually set compression parameters. | |
1330 | * Note: srcSizeHint == 0 means 0! | |
1331 | */ | |
1332 | ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams( | |
1333 | const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize, ZSTD_cParamMode_e mode); | |
1334 | ||
1335 | /*! ZSTD_initCStream_internal() : | |
1336 | * Private use only. Init streaming operation. | |
1337 | * expects params to be valid. | |
1338 | * must receive dict, or cdict, or none, but not both. | |
1339 | * @return : 0, or an error code */ | |
1340 | size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs, | |
1341 | const void* dict, size_t dictSize, | |
1342 | const ZSTD_CDict* cdict, | |
1343 | const ZSTD_CCtx_params* params, unsigned long long pledgedSrcSize); | |
1344 | ||
1345 | void ZSTD_resetSeqStore(seqStore_t* ssPtr); | |
1346 | ||
1347 | /*! ZSTD_getCParamsFromCDict() : | |
1348 | * as the name implies */ | |
1349 | ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict); | |
1350 | ||
1351 | /* ZSTD_compressBegin_advanced_internal() : | |
1352 | * Private use only. To be called from zstdmt_compress.c. */ | |
1353 | size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx* cctx, | |
1354 | const void* dict, size_t dictSize, | |
1355 | ZSTD_dictContentType_e dictContentType, | |
1356 | ZSTD_dictTableLoadMethod_e dtlm, | |
1357 | const ZSTD_CDict* cdict, | |
1358 | const ZSTD_CCtx_params* params, | |
1359 | unsigned long long pledgedSrcSize); | |
1360 | ||
1361 | /* ZSTD_compress_advanced_internal() : | |
1362 | * Private use only. To be called from zstdmt_compress.c. */ | |
1363 | size_t ZSTD_compress_advanced_internal(ZSTD_CCtx* cctx, | |
1364 | void* dst, size_t dstCapacity, | |
1365 | const void* src, size_t srcSize, | |
1366 | const void* dict,size_t dictSize, | |
1367 | const ZSTD_CCtx_params* params); | |
1368 | ||
1369 | ||
1370 | /* ZSTD_writeLastEmptyBlock() : | |
1371 | * output an empty Block with end-of-frame mark to complete a frame | |
1372 | * @return : size of data written into `dst` (== ZSTD_blockHeaderSize (defined in zstd_internal.h)) | |
1373 | * or an error code if `dstCapacity` is too small (<ZSTD_blockHeaderSize) | |
1374 | */ | |
1375 | size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity); | |
1376 | ||
1377 | ||
1378 | /* ZSTD_referenceExternalSequences() : | |
1379 | * Must be called before starting a compression operation. | |
1380 | * seqs must parse a prefix of the source. | |
1381 | * This cannot be used when long range matching is enabled. | |
1382 | * Zstd will use these sequences, and pass the literals to a secondary block | |
1383 | * compressor. | |
1384 | * @return : An error code on failure. | |
1385 | * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory | |
1386 | * access and data corruption. | |
1387 | */ | |
1388 | size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq); | |
1389 | ||
1390 | /* ZSTD_cycleLog() : | |
1391 | * condition for correct operation : hashLog > 1 */ | |
1392 | U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat); | |
1393 | ||
1394 | /* ZSTD_CCtx_trace() : | |
1395 | * Trace the end of a compression call. | |
1396 | */ | |
1397 | void ZSTD_CCtx_trace(ZSTD_CCtx* cctx, size_t extraCSize); | |
1398 | ||
1399 | #endif /* ZSTD_COMPRESS_H */ |