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