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