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