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(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
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
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(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
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(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) {
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(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(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
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(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 extraCSize);
1398
1399 #endif /* ZSTD_COMPRESS_H */
1400
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.