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