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 { |
60 | HUF_CElt CTable[HUF_CTABLE_SIZE_ST(255)]; |
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 | |
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() */ |
86 | typedef struct { |
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 */ |
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 */ |
176 | ZSTD_paramSwitch_e literalCompressionMode; |
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 { |
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 | */ |
194 | } ZSTD_window_t; |
195 | |
196 | #define ZSTD_WINDOW_START_INDEX 2 |
197 | |
198 | typedef struct ZSTD_matchState_t ZSTD_matchState_t; |
199 | |
200 | #define ZSTD_ROW_HASH_CACHE_SIZE 8 /* Size of prefetching hash cache for row-based matchfinder */ |
201 | |
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 */ |
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 | |
218 | U32* hashTable; |
219 | U32* hashTable3; |
220 | U32* chainTable; |
221 | |
222 | U32 forceNonContiguous; /* Non-zero if we should force non-contiguous load for the next window update. */ |
223 | |
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 { |
263 | ZSTD_paramSwitch_e enableLdm; /* ZSTD_ps_enable to enable LDM. ZSTD_ps_auto by default */ |
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; |
294 | ZSTD_paramSwitch_e literalCompressionMode; |
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 | |
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 | |
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 | |
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 | |
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; |
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. */ |
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 | |
389 | /* Whether we are streaming or not */ |
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 */ |
417 | |
418 | /* Workspace for block splitter */ |
419 | ZSTD_blockSplitCtx blockSplitCtx; |
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); |
454 | ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_paramSwitch_e rowMatchfinderMode, ZSTD_dictMode_e dictMode); |
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(val: 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(val: mlBase) + ML_deltaCode : ML_Code[mlBase]; |
486 | } |
487 | |
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(code: 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 = 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(memPtr: dst, val: 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 = lastBlock + (((U32)bt_rle)<<1) + (U32)(srcSize << 3); |
517 | RETURN_ERROR_IF(dstCapacity < 4, dstSize_tooSmall, "" ); |
518 | MEM_writeLE24(memPtr: op, val: 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 | |
536 | MEM_STATIC int ZSTD_literalsCompressionIsDisabled(const ZSTD_CCtx_params* cctxParams) |
537 | { |
538 | switch (cctxParams->literalCompressionMode) { |
539 | case ZSTD_ps_enable: |
540 | return 0; |
541 | case ZSTD_ps_disable: |
542 | return 1; |
543 | default: |
544 | assert(0 /* impossible: pre-validated */); |
545 | ZSTD_FALLTHROUGH; |
546 | case ZSTD_ps_auto: |
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 | */ |
556 | static void |
557 | ZSTD_safecopyLiterals(BYTE* op, BYTE const* ip, BYTE const* const iend, BYTE const* ilimit_w) |
558 | { |
559 | assert(iend > ilimit_w); |
560 | if (ip <= ilimit_w) { |
561 | ZSTD_wildcopy(dst: op, src: ip, length: ilimit_w - ip, ovtype: ZSTD_no_overlap); |
562 | op += ilimit_w - ip; |
563 | ip = ilimit_w; |
564 | } |
565 | while (ip < iend) *op++ = *ip++; |
566 | } |
567 | |
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 | |
581 | /*! ZSTD_storeSeq() : |
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 |
585 | * Allowed to overread literals up to litLimit. |
586 | */ |
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) |
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" , |
600 | pos, (U32)litLength, (U32)matchLength, (U32)offBase_minus1); |
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(dst: seqStorePtr->lit, src: literals); |
614 | if (litLength > 16) { |
615 | ZSTD_wildcopy(dst: seqStorePtr->lit+16, src: literals+16, length: (ptrdiff_t)litLength-16, ovtype: ZSTD_no_overlap); |
616 | } |
617 | } else { |
618 | ZSTD_safecopyLiterals(op: seqStorePtr->lit, ip: literals, iend: litEnd, ilimit_w: litLimit_w); |
619 | } |
620 | seqStorePtr->lit += litLength; |
621 | |
622 | /* literal Length */ |
623 | if (litLength>0xFFFF) { |
624 | assert(seqStorePtr->longLengthType == ZSTD_llt_none); /* there can only be a single long length */ |
625 | seqStorePtr->longLengthType = ZSTD_llt_literalLength; |
626 | seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); |
627 | } |
628 | seqStorePtr->sequences[0].litLength = (U16)litLength; |
629 | |
630 | /* match offset */ |
631 | seqStorePtr->sequences[0].offBase = STORED_TO_OFFBASE(offBase_minus1); |
632 | |
633 | /* match Length */ |
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; |
642 | } |
643 | |
644 | seqStorePtr->sequences++; |
645 | } |
646 | |
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(rep: newReps.rep, offBase_minus1, ll0); |
681 | return newReps; |
682 | } |
683 | |
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(memPtr: pMatch) ^ MEM_readST(memPtr: pIn); |
748 | if (diff) return ZSTD_NbCommonBytes(val: diff); } |
749 | pIn+=sizeof(size_t); pMatch+=sizeof(size_t); |
750 | while (pIn < pInLoopLimit) { |
751 | size_t const diff = MEM_readST(memPtr: pMatch) ^ MEM_readST(memPtr: pIn); |
752 | if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; } |
753 | pIn += ZSTD_NbCommonBytes(val: diff); |
754 | return (size_t)(pIn - pStart); |
755 | } } |
756 | if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(memPtr: pMatch) == MEM_read32(memPtr: pIn))) { pIn+=4; pMatch+=4; } |
757 | if ((pIn<(pInLimit-1)) && (MEM_read16(memPtr: pMatch) == MEM_read16(memPtr: 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(pIn: ip, pMatch: match, pInLimit: 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(pIn: ip+matchLength, pMatch: iStart, pInLimit: 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(u: MEM_readLE32(memPtr: 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(u: MEM_read32(memPtr: 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(u: MEM_readLE64(memPtr: 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(u: MEM_readLE64(memPtr: 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(u: MEM_readLE64(memPtr: 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(u: MEM_readLE64(memPtr: 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(ptr: p, h: hBits); |
816 | case 5: return ZSTD_hash5Ptr(p, h: hBits); |
817 | case 6: return ZSTD_hash6Ptr(p, h: hBits); |
818 | case 7: return ZSTD_hash7Ptr(p, h: hBits); |
819 | case 8: return ZSTD_hash8Ptr(p, h: 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(hash: 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(base: prime8bytes, exponent: 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 | |
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 | |
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(window: ms->window) ? |
931 | ZSTD_extDict : |
932 | ms->dictMatchState != NULL ? |
933 | (ms->dictMatchState->dedicatedDictSearch ? ZSTD_dedicatedDictSearch : ZSTD_dictMatchState) : |
934 | ZSTD_noDict; |
935 | } |
936 | |
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 | |
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, |
990 | U32 cycleLog, |
991 | U32 maxDist, |
992 | U32 loadedDictEnd, |
993 | void const* src, |
994 | void const* srcEnd) |
995 | { |
996 | U32 const curr = (U32)((BYTE const*)srcEnd - window.base); |
997 | if (ZSTD_WINDOW_OVERFLOW_CORRECT_FREQUENTLY) { |
998 | if (ZSTD_window_canOverflowCorrect(window, cycleLog, maxDist, loadedDictEnd, src)) { |
999 | return 1; |
1000 | } |
1001 | } |
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. |
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 | */ |
1036 | U32 const cycleSize = 1u << cycleLog; |
1037 | U32 const cycleMask = cycleSize - 1; |
1038 | U32 const curr = (U32)((BYTE const*)src - window->base); |
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); |
1047 | U32 const correction = curr - newCurrent; |
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)); |
1054 | assert(curr > newCurrent); |
1055 | if (!ZSTD_WINDOW_OVERFLOW_CORRECT_FREQUENTLY) { |
1056 | /* Loose bound, should be around 1<<29 (see above) */ |
1057 | assert(correction > 1<<28); |
1058 | } |
1059 | |
1060 | window->base += correction; |
1061 | window->dictBase += correction; |
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 | } |
1072 | |
1073 | /* Ensure we can still reference the full window. */ |
1074 | assert(newCurrent >= maxDist); |
1075 | assert(newCurrent - maxDist >= ZSTD_WINDOW_START_INDEX); |
1076 | /* Ensure that lowLimit and dictLimit didn't underflow. */ |
1077 | assert(window->lowLimit <= newCurrent); |
1078 | assert(window->dictLimit <= newCurrent); |
1079 | |
1080 | ++window->nbOverflowCorrections; |
1081 | |
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)); |
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; |
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, |
1203 | void const* src, size_t srcSize, |
1204 | int forceNonContiguous) |
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 */ |
1214 | if (src != window->nextSrc || forceNonContiguous) { |
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 | { |
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); |
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 | */ |
1252 | U32 const matchLowest = isDictionary ? lowestValid : withinWindow; |
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 ); |
1398 | |
1399 | #endif /* ZSTD_COMPRESS_H */ |
1400 | |