2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
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.
11 /* This header contains definitions
12 * that shall **only** be used by modules within lib/compress.
15 #ifndef ZSTD_COMPRESS_H
16 #define ZSTD_COMPRESS_H
18 /*-*************************************
20 ***************************************/
21 #include "zstd_internal.h"
22 #ifdef ZSTD_MULTITHREAD
23 # include "zstdmt_compress.h"
26 #if defined (__cplusplus)
30 /*-*************************************
32 ***************************************/
33 #define kSearchStrength 8
34 #define HASH_READ_SIZE 8
35 #define ZSTD_DUBT_UNSORTED_MARK 1 /* For btlazy2 strategy, index 1 now means "unsorted".
36 It could be confused for a real successor at index "1", if sorted as larger than its predecessor.
37 It's not a big deal though : candidate will just be sorted again.
38 Additionnally, candidate position 1 will be lost.
39 But candidate 1 cannot hide a large tree of candidates, so it's a minimal loss.
40 The benefit is that ZSTD_DUBT_UNSORTED_MARK cannot be misdhandled after table re-use with a different strategy */
43 /*-*************************************
44 * Context memory management
45 ***************************************/
46 typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;
47 typedef enum { zcss_init=0, zcss_load, zcss_flush } ZSTD_cStreamStage;
49 typedef struct ZSTD_prefixDict_s {
52 ZSTD_dictContentType_e dictContentType;
56 U32 hufCTable[HUF_CTABLE_SIZE_U32(255)];
57 FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];
58 FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];
59 FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];
60 HUF_repeat hufCTable_repeatMode;
61 FSE_repeat offcode_repeatMode;
62 FSE_repeat matchlength_repeatMode;
63 FSE_repeat litlength_repeatMode;
64 } ZSTD_entropyCTables_t;
76 U32 rep[ZSTD_REP_NUM];
80 /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */
81 U32* litFreq; /* table of literals statistics, of size 256 */
82 U32* litLengthFreq; /* table of litLength statistics, of size (MaxLL+1) */
83 U32* matchLengthFreq; /* table of matchLength statistics, of size (MaxML+1) */
84 U32* offCodeFreq; /* table of offCode statistics, of size (MaxOff+1) */
85 ZSTD_match_t* matchTable; /* list of found matches, of size ZSTD_OPT_NUM+1 */
86 ZSTD_optimal_t* priceTable; /* All positions tracked by optimal parser, of size ZSTD_OPT_NUM+1 */
88 U32 litSum; /* nb of literals */
89 U32 litLengthSum; /* nb of litLength codes */
90 U32 matchLengthSum; /* nb of matchLength codes */
91 U32 offCodeSum; /* nb of offset codes */
92 /* begin updated by ZSTD_setLog2Prices */
93 U32 log2litSum; /* pow2 to compare log2(litfreq) to */
94 U32 log2litLengthSum; /* pow2 to compare log2(llfreq) to */
95 U32 log2matchLengthSum; /* pow2 to compare log2(mlfreq) to */
96 U32 log2offCodeSum; /* pow2 to compare log2(offreq) to */
97 /* end : updated by ZSTD_setLog2Prices */
98 U32 staticPrices; /* prices follow a pre-defined cost structure, statistics are irrelevant */
102 ZSTD_entropyCTables_t entropy;
103 U32 rep[ZSTD_REP_NUM];
104 } ZSTD_compressedBlockState_t;
107 BYTE const* nextSrc; /* next block here to continue on current prefix */
108 BYTE const* base; /* All regular indexes relative to this position */
109 BYTE const* dictBase; /* extDict indexes relative to this position */
110 U32 dictLimit; /* below that point, need extDict */
111 U32 lowLimit; /* below that point, no more data */
115 ZSTD_window_t window; /* State for window round buffer management */
116 U32 loadedDictEnd; /* index of end of dictionary */
117 U32 nextToUpdate; /* index from which to continue table update */
118 U32 nextToUpdate3; /* index from which to continue table update */
119 U32 hashLog3; /* dispatch table : larger == faster, more memory */
123 optState_t opt; /* optimal parser state */
127 ZSTD_compressedBlockState_t* prevCBlock;
128 ZSTD_compressedBlockState_t* nextCBlock;
129 ZSTD_matchState_t matchState;
138 ZSTD_window_t window; /* State for the window round buffer management */
139 ldmEntry_t* hashTable;
140 BYTE* bucketOffsets; /* Next position in bucket to insert entry */
141 U64 hashPower; /* Used to compute the rolling hash.
142 * Depends on ldmParams.minMatchLength */
146 U32 enableLdm; /* 1 if enable long distance matching */
147 U32 hashLog; /* Log size of hashTable */
148 U32 bucketSizeLog; /* Log bucket size for collision resolution, at most 8 */
149 U32 minMatchLength; /* Minimum match length */
150 U32 hashEveryLog; /* Log number of entries to skip */
151 U32 windowLog; /* Window log for the LDM */
161 rawSeq* seq; /* The start of the sequences */
162 size_t pos; /* The position where reading stopped. <= size. */
163 size_t size; /* The number of sequences. <= capacity. */
164 size_t capacity; /* The capacity of the `seq` pointer */
167 struct ZSTD_CCtx_params_s {
168 ZSTD_format_e format;
169 ZSTD_compressionParameters cParams;
170 ZSTD_frameParameters fParams;
172 int compressionLevel;
173 int disableLiteralCompression;
174 int forceWindow; /* force back-references to respect limit of
175 * 1<<wLog, even for dictionary */
177 /* Multithreading: used to pass parameters to mtctx */
180 unsigned overlapSizeLog;
182 /* Long distance matching parameters */
183 ldmParams_t ldmParams;
185 /* Internal use, for createCCtxParams() and freeCCtxParams() only */
186 ZSTD_customMem customMem;
187 }; /* typedef'd to ZSTD_CCtx_params within "zstd.h" */
190 ZSTD_compressionStage_e stage;
191 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. */
192 int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
193 ZSTD_CCtx_params requestedParams;
194 ZSTD_CCtx_params appliedParams;
197 size_t workSpaceSize;
199 unsigned long long pledgedSrcSizePlusOne; /* this way, 0 (default) == unknown */
200 unsigned long long consumedSrcSize;
201 unsigned long long producedCSize;
202 XXH64_state_t xxhState;
203 ZSTD_customMem customMem;
206 seqStore_t seqStore; /* sequences storage ptrs */
207 ldmState_t ldmState; /* long distance matching state */
208 rawSeq* ldmSequences; /* Storage for the ldm output sequences */
209 size_t maxNbLdmSequences;
210 rawSeqStore_t externSeqStore; /* Mutable reference to external sequences */
211 ZSTD_blockState_t blockState;
212 U32* entropyWorkspace; /* entropy workspace of HUF_WORKSPACE_SIZE bytes */
222 size_t outBuffContentSize;
223 size_t outBuffFlushedSize;
224 ZSTD_cStreamStage streamStage;
228 ZSTD_CDict* cdictLocal;
229 const ZSTD_CDict* cdict;
230 ZSTD_prefixDict prefixDict; /* single-usage dictionary */
232 /* Multi-threading */
233 #ifdef ZSTD_MULTITHREAD
239 typedef size_t (*ZSTD_blockCompressor) (
240 ZSTD_matchState_t* bs, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
241 ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize);
242 ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, int extDict);
245 MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
247 static const BYTE LL_Code[64] = { 0, 1, 2, 3, 4, 5, 6, 7,
248 8, 9, 10, 11, 12, 13, 14, 15,
249 16, 16, 17, 17, 18, 18, 19, 19,
250 20, 20, 20, 20, 21, 21, 21, 21,
251 22, 22, 22, 22, 22, 22, 22, 22,
252 23, 23, 23, 23, 23, 23, 23, 23,
253 24, 24, 24, 24, 24, 24, 24, 24,
254 24, 24, 24, 24, 24, 24, 24, 24 };
255 static const U32 LL_deltaCode = 19;
256 return (litLength > 63) ? ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
260 * note : mlBase = matchLength - MINMATCH;
261 * because it's the format it's stored in seqStore->sequences */
262 MEM_STATIC U32 ZSTD_MLcode(U32 mlBase)
264 static const BYTE ML_Code[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
265 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
266 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
267 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
268 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
269 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
270 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
271 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
272 static const U32 ML_deltaCode = 36;
273 return (mlBase > 127) ? ZSTD_highbit32(mlBase) + ML_deltaCode : ML_Code[mlBase];
276 /*! ZSTD_storeSeq() :
277 * Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
278 * `offsetCode` : distance to match + 3 (values 1-3 are repCodes).
279 * `mlBase` : matchLength - MINMATCH
281 MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const void* literals, U32 offsetCode, size_t mlBase)
283 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG >= 6)
284 static const BYTE* g_start = NULL;
285 if (g_start==NULL) g_start = (const BYTE*)literals; /* note : index only works for compression within a single segment */
286 { U32 const pos = (U32)((const BYTE*)literals - g_start);
287 DEBUGLOG(6, "Cpos%7u :%3u literals, match%3u bytes at dist.code%7u",
288 pos, (U32)litLength, (U32)mlBase+MINMATCH, (U32)offsetCode);
292 assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + 128 KB);
293 ZSTD_wildcopy(seqStorePtr->lit, literals, litLength);
294 seqStorePtr->lit += litLength;
297 if (litLength>0xFFFF) {
298 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
299 seqStorePtr->longLengthID = 1;
300 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
302 seqStorePtr->sequences[0].litLength = (U16)litLength;
305 seqStorePtr->sequences[0].offset = offsetCode + 1;
309 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
310 seqStorePtr->longLengthID = 2;
311 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
313 seqStorePtr->sequences[0].matchLength = (U16)mlBase;
315 seqStorePtr->sequences++;
319 /*-*************************************
320 * Match length counter
321 ***************************************/
322 static unsigned ZSTD_NbCommonBytes (size_t val)
324 if (MEM_isLittleEndian()) {
326 # if defined(_MSC_VER) && defined(_WIN64)
328 _BitScanForward64( &r, (U64)val );
329 return (unsigned)(r>>3);
330 # elif defined(__GNUC__) && (__GNUC__ >= 4)
331 return (__builtin_ctzll((U64)val) >> 3);
333 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
334 0, 3, 1, 3, 1, 4, 2, 7,
335 0, 2, 3, 6, 1, 5, 3, 5,
336 1, 3, 4, 4, 2, 5, 6, 7,
337 7, 0, 1, 2, 3, 3, 4, 6,
338 2, 6, 5, 5, 3, 4, 5, 6,
339 7, 1, 2, 4, 6, 4, 4, 5,
340 7, 2, 6, 5, 7, 6, 7, 7 };
341 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
343 } else { /* 32 bits */
344 # if defined(_MSC_VER)
346 _BitScanForward( &r, (U32)val );
347 return (unsigned)(r>>3);
348 # elif defined(__GNUC__) && (__GNUC__ >= 3)
349 return (__builtin_ctz((U32)val) >> 3);
351 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
352 3, 2, 2, 1, 3, 2, 0, 1,
353 3, 3, 1, 2, 2, 2, 2, 0,
354 3, 1, 2, 0, 1, 0, 1, 1 };
355 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
358 } else { /* Big Endian CPU */
360 # if defined(_MSC_VER) && defined(_WIN64)
362 _BitScanReverse64( &r, val );
363 return (unsigned)(r>>3);
364 # elif defined(__GNUC__) && (__GNUC__ >= 4) && __has_builtin(__builtin_clzll)
365 return (__builtin_clzll(val) >> 3);
368 const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */
369 if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
370 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
374 } else { /* 32 bits */
375 # if defined(_MSC_VER)
377 _BitScanReverse( &r, (unsigned long)val );
378 return (unsigned)(r>>3);
379 # elif defined(__GNUC__) && (__GNUC__ >= 3) && __has_builtin(__builtin_clz)
380 return (__builtin_clz((U32)val) >> 3);
383 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
391 MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
393 const BYTE* const pStart = pIn;
394 const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
396 if (pIn < pInLoopLimit) {
397 { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
398 if (diff) return ZSTD_NbCommonBytes(diff); }
399 pIn+=sizeof(size_t); pMatch+=sizeof(size_t);
400 while (pIn < pInLoopLimit) {
401 size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
402 if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
403 pIn += ZSTD_NbCommonBytes(diff);
404 return (size_t)(pIn - pStart);
406 if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
407 if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
408 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
409 return (size_t)(pIn - pStart);
412 /** ZSTD_count_2segments() :
413 * can count match length with `ip` & `match` in 2 different segments.
414 * convention : on reaching mEnd, match count continue starting from iStart
417 ZSTD_count_2segments(const BYTE* ip, const BYTE* match,
418 const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
420 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
421 size_t const matchLength = ZSTD_count(ip, match, vEnd);
422 if (match + matchLength != mEnd) return matchLength;
423 return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
427 /*-*************************************
429 ***************************************/
430 static const U32 prime3bytes = 506832829U;
431 static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; }
432 MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
434 static const U32 prime4bytes = 2654435761U;
435 static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
436 static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
438 static const U64 prime5bytes = 889523592379ULL;
439 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h)) ; }
440 static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
442 static const U64 prime6bytes = 227718039650203ULL;
443 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; }
444 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
446 static const U64 prime7bytes = 58295818150454627ULL;
447 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h)) ; }
448 static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
450 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
451 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
452 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
454 MEM_STATIC size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
459 case 4: return ZSTD_hash4Ptr(p, hBits);
460 case 5: return ZSTD_hash5Ptr(p, hBits);
461 case 6: return ZSTD_hash6Ptr(p, hBits);
462 case 7: return ZSTD_hash7Ptr(p, hBits);
463 case 8: return ZSTD_hash8Ptr(p, hBits);
467 /*-*************************************
468 * Round buffer management
469 ***************************************/
470 /* Max current allowed */
471 #define ZSTD_CURRENT_MAX ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX))
472 /* Maximum chunk size before overflow correction needs to be called again */
473 #define ZSTD_CHUNKSIZE_MAX \
474 ( ((U32)-1) /* Maximum ending current index */ \
475 - ZSTD_CURRENT_MAX) /* Maximum beginning lowLimit */
478 * ZSTD_window_clear():
479 * Clears the window containing the history by simply setting it to empty.
481 MEM_STATIC void ZSTD_window_clear(ZSTD_window_t* window)
483 size_t const endT = (size_t)(window->nextSrc - window->base);
484 U32 const end = (U32)endT;
486 window->lowLimit = end;
487 window->dictLimit = end;
491 * ZSTD_window_hasExtDict():
492 * Returns non-zero if the window has a non-empty extDict.
494 MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
496 return window.lowLimit < window.dictLimit;
500 * ZSTD_window_needOverflowCorrection():
501 * Returns non-zero if the indices are getting too large and need overflow
504 MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window,
507 U32 const current = (U32)((BYTE const*)srcEnd - window.base);
508 return current > ZSTD_CURRENT_MAX;
512 * ZSTD_window_correctOverflow():
513 * Reduces the indices to protect from index overflow.
514 * Returns the correction made to the indices, which must be applied to every
517 * The least significant cycleLog bits of the indices must remain the same,
518 * which may be 0. Every index up to maxDist in the past must be valid.
519 * NOTE: (maxDist & cycleMask) must be zero.
521 MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t* window, U32 cycleLog,
522 U32 maxDist, void const* src)
524 /* preemptive overflow correction:
525 * 1. correction is large enough:
526 * lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog
527 * 1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog
529 * current - newCurrent
530 * > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog)
531 * > (3<<29) - (1<<chainLog)
532 * > (3<<29) - (1<<30) (NOTE: chainLog <= 30)
535 * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow:
536 * After correction, current is less than (1<<chainLog + 1<<windowLog).
537 * In 64-bit mode we are safe, because we have 64-bit ptrdiff_t.
538 * In 32-bit mode we are safe, because (chainLog <= 29), so
539 * ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32.
540 * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32:
541 * windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32.
543 U32 const cycleMask = (1U << cycleLog) - 1;
544 U32 const current = (U32)((BYTE const*)src - window->base);
545 U32 const newCurrent = (current & cycleMask) + maxDist;
546 U32 const correction = current - newCurrent;
547 assert((maxDist & cycleMask) == 0);
548 assert(current > newCurrent);
549 /* Loose bound, should be around 1<<29 (see above) */
550 assert(correction > 1<<28);
552 window->base += correction;
553 window->dictBase += correction;
554 window->lowLimit -= correction;
555 window->dictLimit -= correction;
557 DEBUGLOG(4, "Correction of 0x%x bytes to lowLimit=0x%x", correction,
563 * ZSTD_window_enforceMaxDist():
564 * Updates lowLimit so that:
565 * (srcEnd - base) - lowLimit == maxDist + loadedDictEnd
566 * This allows a simple check that index >= lowLimit to see if index is valid.
567 * This must be called before a block compression call, with srcEnd as the block
569 * If loadedDictEndPtr is not NULL, we set it to zero once we update lowLimit.
570 * This is because dictionaries are allowed to be referenced as long as the last
571 * byte of the dictionary is in the window, but once they are out of range,
572 * they cannot be referenced. If loadedDictEndPtr is NULL, we use
573 * loadedDictEnd == 0.
575 MEM_STATIC void ZSTD_window_enforceMaxDist(ZSTD_window_t* window,
576 void const* srcEnd, U32 maxDist,
577 U32* loadedDictEndPtr)
579 U32 const current = (U32)((BYTE const*)srcEnd - window->base);
580 U32 loadedDictEnd = loadedDictEndPtr != NULL ? *loadedDictEndPtr : 0;
581 if (current > maxDist + loadedDictEnd) {
582 U32 const newLowLimit = current - maxDist;
583 if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit;
584 if (window->dictLimit < window->lowLimit) {
585 DEBUGLOG(5, "Update dictLimit from %u to %u", window->dictLimit,
587 window->dictLimit = window->lowLimit;
589 if (loadedDictEndPtr)
590 *loadedDictEndPtr = 0;
595 * ZSTD_window_update():
596 * Updates the window by appending [src, src + srcSize) to the window.
597 * If it is not contiguous, the current prefix becomes the extDict, and we
598 * forget about the extDict. Handles overlap of the prefix and extDict.
599 * Returns non-zero if the segment is contiguous.
601 MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t* window,
602 void const* src, size_t srcSize)
604 BYTE const* const ip = (BYTE const*)src;
606 /* Check if blocks follow each other */
607 if (src != window->nextSrc) {
609 size_t const distanceFromBase = (size_t)(window->nextSrc - window->base);
610 DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u",
612 window->lowLimit = window->dictLimit;
613 assert(distanceFromBase == (size_t)(U32)distanceFromBase); /* should never overflow */
614 window->dictLimit = (U32)distanceFromBase;
615 window->dictBase = window->base;
616 window->base = ip - distanceFromBase;
617 // ms->nextToUpdate = window->dictLimit;
618 if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit; /* too small extDict */
621 window->nextSrc = ip + srcSize;
622 /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
623 if ( (ip+srcSize > window->dictBase + window->lowLimit)
624 & (ip < window->dictBase + window->dictLimit)) {
625 ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase;
626 U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)window->dictLimit) ? window->dictLimit : (U32)highInputIdx;
627 window->lowLimit = lowLimitMax;
632 #if defined (__cplusplus)
637 /* ==============================================================
638 * Private declarations
639 * These prototypes shall only be called from within lib/compress
640 * ============================================================== */
642 /* ZSTD_getCParamsFromCCtxParams() :
643 * cParams are built depending on compressionLevel, src size hints,
644 * LDM and manually set compression parameters.
646 ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams(
647 const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize);
649 /*! ZSTD_initCStream_internal() :
650 * Private use only. Init streaming operation.
651 * expects params to be valid.
652 * must receive dict, or cdict, or none, but not both.
653 * @return : 0, or an error code */
654 size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs,
655 const void* dict, size_t dictSize,
656 const ZSTD_CDict* cdict,
657 ZSTD_CCtx_params params, unsigned long long pledgedSrcSize);
659 /*! ZSTD_compressStream_generic() :
660 * Private use only. To be called from zstdmt_compress.c in single-thread mode. */
661 size_t ZSTD_compressStream_generic(ZSTD_CStream* zcs,
662 ZSTD_outBuffer* output,
663 ZSTD_inBuffer* input,
664 ZSTD_EndDirective const flushMode);
666 /*! ZSTD_getCParamsFromCDict() :
667 * as the name implies */
668 ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict);
670 /* ZSTD_compressBegin_advanced_internal() :
671 * Private use only. To be called from zstdmt_compress.c. */
672 size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx* cctx,
673 const void* dict, size_t dictSize,
674 ZSTD_dictContentType_e dictContentType,
675 const ZSTD_CDict* cdict,
676 ZSTD_CCtx_params params,
677 unsigned long long pledgedSrcSize);
679 /* ZSTD_compress_advanced_internal() :
680 * Private use only. To be called from zstdmt_compress.c. */
681 size_t ZSTD_compress_advanced_internal(ZSTD_CCtx* cctx,
682 void* dst, size_t dstCapacity,
683 const void* src, size_t srcSize,
684 const void* dict,size_t dictSize,
685 ZSTD_CCtx_params params);
688 /* ZSTD_writeLastEmptyBlock() :
689 * output an empty Block with end-of-frame mark to complete a frame
690 * @return : size of data written into `dst` (== ZSTD_blockHeaderSize (defined in zstd_internal.h))
691 * or an error code if `dstCapcity` is too small (<ZSTD_blockHeaderSize)
693 size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity);
696 /* ZSTD_referenceExternalSequences() :
697 * Must be called before starting a compression operation.
698 * seqs must parse a prefix of the source.
699 * This cannot be used when long range matching is enabled.
700 * Zstd will use these sequences, and pass the literals to a secondary block
702 * @return : An error code on failure.
703 * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory
704 * access and data corruption.
706 size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq);
709 #endif /* ZSTD_COMPRESS_H */