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