2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
5 * This source code is licensed under the BSD-style license found in the
6 * LICENSE file in the root directory of this source tree. An additional grant
7 * of patent rights can be found in the PATENTS file in the same directory.
11 /*-*************************************
13 ***************************************/
14 #include <string.h> /* memset */
16 #define FSE_STATIC_LINKING_ONLY /* FSE_encodeSymbol */
18 #define HUF_STATIC_LINKING_ONLY
20 #include "zstd_internal.h" /* includes zstd.h */
23 /*-*************************************
25 ***************************************/
26 static const U32 g_searchStrength = 8; /* control skip over incompressible data */
27 #define HASH_READ_SIZE 8
28 typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;
31 /*-*************************************
33 ***************************************/
34 #define ZSTD_STATIC_ASSERT(c) { enum { ZSTD_static_assert = 1/(int)(!!(c)) }; }
35 size_t ZSTD_compressBound(size_t srcSize) { return FSE_compressBound(srcSize) + 12; }
38 /*-*************************************
40 ***************************************/
41 static void ZSTD_resetSeqStore(seqStore_t* ssPtr)
43 ssPtr->lit = ssPtr->litStart;
44 ssPtr->sequences = ssPtr->sequencesStart;
45 ssPtr->longLengthID = 0;
49 /*-*************************************
50 * Context memory management
51 ***************************************/
53 const BYTE* nextSrc; /* next block here to continue on current prefix */
54 const BYTE* base; /* All regular indexes relative to this position */
55 const BYTE* dictBase; /* extDict indexes relative to this position */
56 U32 dictLimit; /* below that point, need extDict */
57 U32 lowLimit; /* below that point, no more data */
58 U32 nextToUpdate; /* index from which to continue dictionary update */
59 U32 nextToUpdate3; /* index from which to continue dictionary update */
60 U32 hashLog3; /* dispatch table : larger == faster, more memory */
61 U32 loadedDictEnd; /* index of end of dictionary */
62 U32 forceWindow; /* force back-references to respect limit of 1<<wLog, even for dictionary */
63 U32 forceRawDict; /* Force loading dictionary in "content-only" mode (no header analysis) */
64 ZSTD_compressionStage_e stage;
65 U32 rep[ZSTD_REP_NUM];
66 U32 repToConfirm[ZSTD_REP_NUM];
68 ZSTD_parameters params;
73 XXH64_state_t xxhState;
74 ZSTD_customMem customMem;
76 seqStore_t seqStore; /* sequences storage ptrs */
82 HUF_repeat flagStaticHufTable;
83 FSE_CTable offcodeCTable [FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];
84 FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];
85 FSE_CTable litlengthCTable [FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];
86 unsigned tmpCounters[HUF_WORKSPACE_SIZE_U32];
89 ZSTD_CCtx* ZSTD_createCCtx(void)
91 return ZSTD_createCCtx_advanced(defaultCustomMem);
94 ZSTD_CCtx* ZSTD_createCCtx_advanced(ZSTD_customMem customMem)
98 if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;
99 if (!customMem.customAlloc || !customMem.customFree) return NULL;
101 cctx = (ZSTD_CCtx*) ZSTD_malloc(sizeof(ZSTD_CCtx), customMem);
102 if (!cctx) return NULL;
103 memset(cctx, 0, sizeof(ZSTD_CCtx));
104 cctx->customMem = customMem;
108 size_t ZSTD_freeCCtx(ZSTD_CCtx* cctx)
110 if (cctx==NULL) return 0; /* support free on NULL */
111 ZSTD_free(cctx->workSpace, cctx->customMem);
112 ZSTD_free(cctx, cctx->customMem);
113 return 0; /* reserved as a potential error code in the future */
116 size_t ZSTD_sizeof_CCtx(const ZSTD_CCtx* cctx)
118 if (cctx==NULL) return 0; /* support sizeof on NULL */
119 return sizeof(*cctx) + cctx->workSpaceSize;
122 size_t ZSTD_setCCtxParameter(ZSTD_CCtx* cctx, ZSTD_CCtxParameter param, unsigned value)
126 case ZSTD_p_forceWindow : cctx->forceWindow = value>0; cctx->loadedDictEnd = 0; return 0;
127 case ZSTD_p_forceRawDict : cctx->forceRawDict = value>0; return 0;
128 default: return ERROR(parameter_unknown);
132 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx) /* hidden interface */
134 return &(ctx->seqStore);
137 static ZSTD_parameters ZSTD_getParamsFromCCtx(const ZSTD_CCtx* cctx)
143 /** ZSTD_checkParams() :
144 ensure param values remain within authorized range.
145 @return : 0, or an error code if one value is beyond authorized range */
146 size_t ZSTD_checkCParams(ZSTD_compressionParameters cParams)
148 # define CLAMPCHECK(val,min,max) { if ((val<min) | (val>max)) return ERROR(compressionParameter_unsupported); }
149 CLAMPCHECK(cParams.windowLog, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);
150 CLAMPCHECK(cParams.chainLog, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX);
151 CLAMPCHECK(cParams.hashLog, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX);
152 CLAMPCHECK(cParams.searchLog, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX);
153 { U32 const searchLengthMin = ((cParams.strategy == ZSTD_fast) | (cParams.strategy == ZSTD_greedy)) ? ZSTD_SEARCHLENGTH_MIN+1 : ZSTD_SEARCHLENGTH_MIN;
154 U32 const searchLengthMax = (cParams.strategy == ZSTD_fast) ? ZSTD_SEARCHLENGTH_MAX : ZSTD_SEARCHLENGTH_MAX-1;
155 CLAMPCHECK(cParams.searchLength, searchLengthMin, searchLengthMax); }
156 CLAMPCHECK(cParams.targetLength, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX);
157 if ((U32)(cParams.strategy) > (U32)ZSTD_btopt2) return ERROR(compressionParameter_unsupported);
162 /** ZSTD_cycleLog() :
163 * condition for correct operation : hashLog > 1 */
164 static U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat)
166 U32 const btScale = ((U32)strat >= (U32)ZSTD_btlazy2);
167 return hashLog - btScale;
170 /** ZSTD_adjustCParams() :
171 optimize `cPar` for a given input (`srcSize` and `dictSize`).
172 mostly downsizing to reduce memory consumption and initialization.
173 Both `srcSize` and `dictSize` are optional (use 0 if unknown),
174 but if both are 0, no optimization can be done.
175 Note : cPar is considered validated at this stage. Use ZSTD_checkParams() to ensure that. */
176 ZSTD_compressionParameters ZSTD_adjustCParams(ZSTD_compressionParameters cPar, unsigned long long srcSize, size_t dictSize)
178 if (srcSize+dictSize == 0) return cPar; /* no size information available : no adjustment */
180 /* resize params, to use less memory when necessary */
181 { U32 const minSrcSize = (srcSize==0) ? 500 : 0;
182 U64 const rSize = srcSize + dictSize + minSrcSize;
183 if (rSize < ((U64)1<<ZSTD_WINDOWLOG_MAX)) {
184 U32 const srcLog = MAX(ZSTD_HASHLOG_MIN, ZSTD_highbit32((U32)(rSize)-1) + 1);
185 if (cPar.windowLog > srcLog) cPar.windowLog = srcLog;
187 if (cPar.hashLog > cPar.windowLog) cPar.hashLog = cPar.windowLog;
188 { U32 const cycleLog = ZSTD_cycleLog(cPar.chainLog, cPar.strategy);
189 if (cycleLog > cPar.windowLog) cPar.chainLog -= (cycleLog - cPar.windowLog);
192 if (cPar.windowLog < ZSTD_WINDOWLOG_ABSOLUTEMIN) cPar.windowLog = ZSTD_WINDOWLOG_ABSOLUTEMIN; /* required for frame header */
198 size_t ZSTD_estimateCCtxSize(ZSTD_compressionParameters cParams)
200 size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << cParams.windowLog);
201 U32 const divider = (cParams.searchLength==3) ? 3 : 4;
202 size_t const maxNbSeq = blockSize / divider;
203 size_t const tokenSpace = blockSize + 11*maxNbSeq;
205 size_t const chainSize = (cParams.strategy == ZSTD_fast) ? 0 : (1 << cParams.chainLog);
206 size_t const hSize = ((size_t)1) << cParams.hashLog;
207 U32 const hashLog3 = (cParams.searchLength>3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, cParams.windowLog);
208 size_t const h3Size = ((size_t)1) << hashLog3;
209 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
211 size_t const optSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits))*sizeof(U32)
212 + (ZSTD_OPT_NUM+1)*(sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t));
213 size_t const neededSpace = tableSpace + (256*sizeof(U32)) /* huffTable */ + tokenSpace
214 + (((cParams.strategy == ZSTD_btopt) || (cParams.strategy == ZSTD_btopt2)) ? optSpace : 0);
216 return sizeof(ZSTD_CCtx) + neededSpace;
220 static U32 ZSTD_equivalentParams(ZSTD_parameters param1, ZSTD_parameters param2)
222 return (param1.cParams.hashLog == param2.cParams.hashLog)
223 & (param1.cParams.chainLog == param2.cParams.chainLog)
224 & (param1.cParams.strategy == param2.cParams.strategy)
225 & ((param1.cParams.searchLength==3) == (param2.cParams.searchLength==3));
228 /*! ZSTD_continueCCtx() :
229 reuse CCtx without reset (note : requires no dictionary) */
230 static size_t ZSTD_continueCCtx(ZSTD_CCtx* cctx, ZSTD_parameters params, U64 frameContentSize)
232 U32 const end = (U32)(cctx->nextSrc - cctx->base);
233 cctx->params = params;
234 cctx->frameContentSize = frameContentSize;
235 cctx->lowLimit = end;
236 cctx->dictLimit = end;
237 cctx->nextToUpdate = end+1;
238 cctx->stage = ZSTDcs_init;
240 cctx->loadedDictEnd = 0;
241 { int i; for (i=0; i<ZSTD_REP_NUM; i++) cctx->rep[i] = repStartValue[i]; }
242 cctx->seqStore.litLengthSum = 0; /* force reset of btopt stats */
243 XXH64_reset(&cctx->xxhState, 0);
247 typedef enum { ZSTDcrp_continue, ZSTDcrp_noMemset, ZSTDcrp_fullReset } ZSTD_compResetPolicy_e;
249 /*! ZSTD_resetCCtx_advanced() :
250 note : `params` must be validated */
251 static size_t ZSTD_resetCCtx_advanced (ZSTD_CCtx* zc,
252 ZSTD_parameters params, U64 frameContentSize,
253 ZSTD_compResetPolicy_e const crp)
255 if (crp == ZSTDcrp_continue)
256 if (ZSTD_equivalentParams(params, zc->params)) {
257 zc->flagStaticTables = 0;
258 zc->flagStaticHufTable = HUF_repeat_none;
259 return ZSTD_continueCCtx(zc, params, frameContentSize);
262 { size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << params.cParams.windowLog);
263 U32 const divider = (params.cParams.searchLength==3) ? 3 : 4;
264 size_t const maxNbSeq = blockSize / divider;
265 size_t const tokenSpace = blockSize + 11*maxNbSeq;
266 size_t const chainSize = (params.cParams.strategy == ZSTD_fast) ? 0 : (1 << params.cParams.chainLog);
267 size_t const hSize = ((size_t)1) << params.cParams.hashLog;
268 U32 const hashLog3 = (params.cParams.searchLength>3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, params.cParams.windowLog);
269 size_t const h3Size = ((size_t)1) << hashLog3;
270 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
273 /* Check if workSpace is large enough, alloc a new one if needed */
274 { size_t const optSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits))*sizeof(U32)
275 + (ZSTD_OPT_NUM+1)*(sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t));
276 size_t const neededSpace = tableSpace + (256*sizeof(U32)) /* huffTable */ + tokenSpace
277 + (((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) ? optSpace : 0);
278 if (zc->workSpaceSize < neededSpace) {
279 ZSTD_free(zc->workSpace, zc->customMem);
280 zc->workSpace = ZSTD_malloc(neededSpace, zc->customMem);
281 if (zc->workSpace == NULL) return ERROR(memory_allocation);
282 zc->workSpaceSize = neededSpace;
285 if (crp!=ZSTDcrp_noMemset) memset(zc->workSpace, 0, tableSpace); /* reset tables only */
286 XXH64_reset(&zc->xxhState, 0);
287 zc->hashLog3 = hashLog3;
288 zc->hashTable = (U32*)(zc->workSpace);
289 zc->chainTable = zc->hashTable + hSize;
290 zc->hashTable3 = zc->chainTable + chainSize;
291 ptr = zc->hashTable3 + h3Size;
292 zc->hufTable = (HUF_CElt*)ptr;
293 zc->flagStaticTables = 0;
294 zc->flagStaticHufTable = HUF_repeat_none;
295 ptr = ((U32*)ptr) + 256; /* note : HUF_CElt* is incomplete type, size is simulated using U32 */
297 zc->nextToUpdate = 1;
304 zc->blockSize = blockSize;
305 zc->frameContentSize = frameContentSize;
306 { int i; for (i=0; i<ZSTD_REP_NUM; i++) zc->rep[i] = repStartValue[i]; }
308 if ((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) {
309 zc->seqStore.litFreq = (U32*)ptr;
310 zc->seqStore.litLengthFreq = zc->seqStore.litFreq + (1<<Litbits);
311 zc->seqStore.matchLengthFreq = zc->seqStore.litLengthFreq + (MaxLL+1);
312 zc->seqStore.offCodeFreq = zc->seqStore.matchLengthFreq + (MaxML+1);
313 ptr = zc->seqStore.offCodeFreq + (MaxOff+1);
314 zc->seqStore.matchTable = (ZSTD_match_t*)ptr;
315 ptr = zc->seqStore.matchTable + ZSTD_OPT_NUM+1;
316 zc->seqStore.priceTable = (ZSTD_optimal_t*)ptr;
317 ptr = zc->seqStore.priceTable + ZSTD_OPT_NUM+1;
318 zc->seqStore.litLengthSum = 0;
320 zc->seqStore.sequencesStart = (seqDef*)ptr;
321 ptr = zc->seqStore.sequencesStart + maxNbSeq;
322 zc->seqStore.llCode = (BYTE*) ptr;
323 zc->seqStore.mlCode = zc->seqStore.llCode + maxNbSeq;
324 zc->seqStore.ofCode = zc->seqStore.mlCode + maxNbSeq;
325 zc->seqStore.litStart = zc->seqStore.ofCode + maxNbSeq;
327 zc->stage = ZSTDcs_init;
329 zc->loadedDictEnd = 0;
335 /* ZSTD_invalidateRepCodes() :
336 * ensures next compression will not use repcodes from previous block.
337 * Note : only works with regular variant;
338 * do not use with extDict variant ! */
339 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx) {
341 for (i=0; i<ZSTD_REP_NUM; i++) cctx->rep[i] = 0;
344 /*! ZSTD_copyCCtx() :
345 * Duplicate an existing context `srcCCtx` into another one `dstCCtx`.
346 * Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()).
347 * @return : 0, or an error code */
348 size_t ZSTD_copyCCtx(ZSTD_CCtx* dstCCtx, const ZSTD_CCtx* srcCCtx, unsigned long long pledgedSrcSize)
350 if (srcCCtx->stage!=ZSTDcs_init) return ERROR(stage_wrong);
353 memcpy(&dstCCtx->customMem, &srcCCtx->customMem, sizeof(ZSTD_customMem));
354 { ZSTD_parameters params = srcCCtx->params;
355 params.fParams.contentSizeFlag = (pledgedSrcSize > 0);
356 ZSTD_resetCCtx_advanced(dstCCtx, params, pledgedSrcSize, ZSTDcrp_noMemset);
360 { size_t const chainSize = (srcCCtx->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << srcCCtx->params.cParams.chainLog);
361 size_t const hSize = ((size_t)1) << srcCCtx->params.cParams.hashLog;
362 size_t const h3Size = (size_t)1 << srcCCtx->hashLog3;
363 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
364 memcpy(dstCCtx->workSpace, srcCCtx->workSpace, tableSpace);
367 /* copy dictionary offsets */
368 dstCCtx->nextToUpdate = srcCCtx->nextToUpdate;
369 dstCCtx->nextToUpdate3= srcCCtx->nextToUpdate3;
370 dstCCtx->nextSrc = srcCCtx->nextSrc;
371 dstCCtx->base = srcCCtx->base;
372 dstCCtx->dictBase = srcCCtx->dictBase;
373 dstCCtx->dictLimit = srcCCtx->dictLimit;
374 dstCCtx->lowLimit = srcCCtx->lowLimit;
375 dstCCtx->loadedDictEnd= srcCCtx->loadedDictEnd;
376 dstCCtx->dictID = srcCCtx->dictID;
378 /* copy entropy tables */
379 dstCCtx->flagStaticTables = srcCCtx->flagStaticTables;
380 dstCCtx->flagStaticHufTable = srcCCtx->flagStaticHufTable;
381 if (srcCCtx->flagStaticTables) {
382 memcpy(dstCCtx->litlengthCTable, srcCCtx->litlengthCTable, sizeof(dstCCtx->litlengthCTable));
383 memcpy(dstCCtx->matchlengthCTable, srcCCtx->matchlengthCTable, sizeof(dstCCtx->matchlengthCTable));
384 memcpy(dstCCtx->offcodeCTable, srcCCtx->offcodeCTable, sizeof(dstCCtx->offcodeCTable));
386 if (srcCCtx->flagStaticHufTable) {
387 memcpy(dstCCtx->hufTable, srcCCtx->hufTable, 256*4);
394 /*! ZSTD_reduceTable() :
395 * reduce table indexes by `reducerValue` */
396 static void ZSTD_reduceTable (U32* const table, U32 const size, U32 const reducerValue)
399 for (u=0 ; u < size ; u++) {
400 if (table[u] < reducerValue) table[u] = 0;
401 else table[u] -= reducerValue;
405 /*! ZSTD_reduceIndex() :
406 * rescale all indexes to avoid future overflow (indexes are U32) */
407 static void ZSTD_reduceIndex (ZSTD_CCtx* zc, const U32 reducerValue)
409 { U32 const hSize = 1 << zc->params.cParams.hashLog;
410 ZSTD_reduceTable(zc->hashTable, hSize, reducerValue); }
412 { U32 const chainSize = (zc->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << zc->params.cParams.chainLog);
413 ZSTD_reduceTable(zc->chainTable, chainSize, reducerValue); }
415 { U32 const h3Size = (zc->hashLog3) ? 1 << zc->hashLog3 : 0;
416 ZSTD_reduceTable(zc->hashTable3, h3Size, reducerValue); }
420 /*-*******************************************************
421 * Block entropic compression
422 *********************************************************/
424 /* See doc/zstd_compression_format.md for detailed format description */
426 size_t ZSTD_noCompressBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
428 if (srcSize + ZSTD_blockHeaderSize > dstCapacity) return ERROR(dstSize_tooSmall);
429 memcpy((BYTE*)dst + ZSTD_blockHeaderSize, src, srcSize);
430 MEM_writeLE24(dst, (U32)(srcSize << 2) + (U32)bt_raw);
431 return ZSTD_blockHeaderSize+srcSize;
435 static size_t ZSTD_noCompressLiterals (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
437 BYTE* const ostart = (BYTE* const)dst;
438 U32 const flSize = 1 + (srcSize>31) + (srcSize>4095);
440 if (srcSize + flSize > dstCapacity) return ERROR(dstSize_tooSmall);
444 case 1: /* 2 - 1 - 5 */
445 ostart[0] = (BYTE)((U32)set_basic + (srcSize<<3));
447 case 2: /* 2 - 2 - 12 */
448 MEM_writeLE16(ostart, (U16)((U32)set_basic + (1<<2) + (srcSize<<4)));
450 default: /*note : should not be necessary : flSize is within {1,2,3} */
451 case 3: /* 2 - 2 - 20 */
452 MEM_writeLE32(ostart, (U32)((U32)set_basic + (3<<2) + (srcSize<<4)));
456 memcpy(ostart + flSize, src, srcSize);
457 return srcSize + flSize;
460 static size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
462 BYTE* const ostart = (BYTE* const)dst;
463 U32 const flSize = 1 + (srcSize>31) + (srcSize>4095);
465 (void)dstCapacity; /* dstCapacity already guaranteed to be >=4, hence large enough */
469 case 1: /* 2 - 1 - 5 */
470 ostart[0] = (BYTE)((U32)set_rle + (srcSize<<3));
472 case 2: /* 2 - 2 - 12 */
473 MEM_writeLE16(ostart, (U16)((U32)set_rle + (1<<2) + (srcSize<<4)));
475 default: /*note : should not be necessary : flSize is necessarily within {1,2,3} */
476 case 3: /* 2 - 2 - 20 */
477 MEM_writeLE32(ostart, (U32)((U32)set_rle + (3<<2) + (srcSize<<4)));
481 ostart[flSize] = *(const BYTE*)src;
486 static size_t ZSTD_minGain(size_t srcSize) { return (srcSize >> 6) + 2; }
488 static size_t ZSTD_compressLiterals (ZSTD_CCtx* zc,
489 void* dst, size_t dstCapacity,
490 const void* src, size_t srcSize)
492 size_t const minGain = ZSTD_minGain(srcSize);
493 size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB);
494 BYTE* const ostart = (BYTE*)dst;
495 U32 singleStream = srcSize < 256;
496 symbolEncodingType_e hType = set_compressed;
500 /* small ? don't even attempt compression (speed opt) */
501 # define LITERAL_NOENTROPY 63
502 { size_t const minLitSize = zc->flagStaticHufTable == HUF_repeat_valid ? 6 : LITERAL_NOENTROPY;
503 if (srcSize <= minLitSize) return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
506 if (dstCapacity < lhSize+1) return ERROR(dstSize_tooSmall); /* not enough space for compression */
507 { HUF_repeat repeat = zc->flagStaticHufTable;
508 int const preferRepeat = zc->params.cParams.strategy < ZSTD_lazy ? srcSize <= 1024 : 0;
509 if (repeat == HUF_repeat_valid && lhSize == 3) singleStream = 1;
510 cLitSize = singleStream ? HUF_compress1X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11, zc->tmpCounters, sizeof(zc->tmpCounters), zc->hufTable, &repeat, preferRepeat)
511 : HUF_compress4X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11, zc->tmpCounters, sizeof(zc->tmpCounters), zc->hufTable, &repeat, preferRepeat);
512 if (repeat != HUF_repeat_none) { hType = set_repeat; } /* reused the existing table */
513 else { zc->flagStaticHufTable = HUF_repeat_check; } /* now have a table to reuse */
516 if ((cLitSize==0) | (cLitSize >= srcSize - minGain)) {
517 zc->flagStaticHufTable = HUF_repeat_none;
518 return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
521 zc->flagStaticHufTable = HUF_repeat_none;
522 return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize);
528 case 3: /* 2 - 2 - 10 - 10 */
529 { U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<14);
530 MEM_writeLE24(ostart, lhc);
533 case 4: /* 2 - 2 - 14 - 14 */
534 { U32 const lhc = hType + (2 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<18);
535 MEM_writeLE32(ostart, lhc);
538 default: /* should not be necessary, lhSize is only {3,4,5} */
539 case 5: /* 2 - 2 - 18 - 18 */
540 { U32 const lhc = hType + (3 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<22);
541 MEM_writeLE32(ostart, lhc);
542 ostart[4] = (BYTE)(cLitSize >> 10);
546 return lhSize+cLitSize;
549 static const BYTE LL_Code[64] = { 0, 1, 2, 3, 4, 5, 6, 7,
550 8, 9, 10, 11, 12, 13, 14, 15,
551 16, 16, 17, 17, 18, 18, 19, 19,
552 20, 20, 20, 20, 21, 21, 21, 21,
553 22, 22, 22, 22, 22, 22, 22, 22,
554 23, 23, 23, 23, 23, 23, 23, 23,
555 24, 24, 24, 24, 24, 24, 24, 24,
556 24, 24, 24, 24, 24, 24, 24, 24 };
558 static const BYTE ML_Code[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
559 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
560 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
561 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
562 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
563 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
564 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
565 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
568 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr)
570 BYTE const LL_deltaCode = 19;
571 BYTE const ML_deltaCode = 36;
572 const seqDef* const sequences = seqStorePtr->sequencesStart;
573 BYTE* const llCodeTable = seqStorePtr->llCode;
574 BYTE* const ofCodeTable = seqStorePtr->ofCode;
575 BYTE* const mlCodeTable = seqStorePtr->mlCode;
576 U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
578 for (u=0; u<nbSeq; u++) {
579 U32 const llv = sequences[u].litLength;
580 U32 const mlv = sequences[u].matchLength;
581 llCodeTable[u] = (llv> 63) ? (BYTE)ZSTD_highbit32(llv) + LL_deltaCode : LL_Code[llv];
582 ofCodeTable[u] = (BYTE)ZSTD_highbit32(sequences[u].offset);
583 mlCodeTable[u] = (mlv>127) ? (BYTE)ZSTD_highbit32(mlv) + ML_deltaCode : ML_Code[mlv];
585 if (seqStorePtr->longLengthID==1)
586 llCodeTable[seqStorePtr->longLengthPos] = MaxLL;
587 if (seqStorePtr->longLengthID==2)
588 mlCodeTable[seqStorePtr->longLengthPos] = MaxML;
591 MEM_STATIC size_t ZSTD_compressSequences (ZSTD_CCtx* zc,
592 void* dst, size_t dstCapacity,
595 const int longOffsets = zc->params.cParams.windowLog > STREAM_ACCUMULATOR_MIN;
596 const seqStore_t* seqStorePtr = &(zc->seqStore);
599 FSE_CTable* CTable_LitLength = zc->litlengthCTable;
600 FSE_CTable* CTable_OffsetBits = zc->offcodeCTable;
601 FSE_CTable* CTable_MatchLength = zc->matchlengthCTable;
602 U32 LLtype, Offtype, MLtype; /* compressed, raw or rle */
603 const seqDef* const sequences = seqStorePtr->sequencesStart;
604 const BYTE* const ofCodeTable = seqStorePtr->ofCode;
605 const BYTE* const llCodeTable = seqStorePtr->llCode;
606 const BYTE* const mlCodeTable = seqStorePtr->mlCode;
607 BYTE* const ostart = (BYTE*)dst;
608 BYTE* const oend = ostart + dstCapacity;
610 size_t const nbSeq = seqStorePtr->sequences - seqStorePtr->sequencesStart;
612 BYTE scratchBuffer[1<<MAX(MLFSELog,LLFSELog)];
614 /* Compress literals */
615 { const BYTE* const literals = seqStorePtr->litStart;
616 size_t const litSize = seqStorePtr->lit - literals;
617 size_t const cSize = ZSTD_compressLiterals(zc, op, dstCapacity, literals, litSize);
618 if (ZSTD_isError(cSize)) return cSize;
622 /* Sequences Header */
623 if ((oend-op) < 3 /*max nbSeq Size*/ + 1 /*seqHead */) return ERROR(dstSize_tooSmall);
624 if (nbSeq < 0x7F) *op++ = (BYTE)nbSeq;
625 else if (nbSeq < LONGNBSEQ) op[0] = (BYTE)((nbSeq>>8) + 0x80), op[1] = (BYTE)nbSeq, op+=2;
626 else op[0]=0xFF, MEM_writeLE16(op+1, (U16)(nbSeq - LONGNBSEQ)), op+=3;
627 if (nbSeq==0) goto _check_compressibility;
629 /* seqHead : flags for FSE encoding type */
632 #define MIN_SEQ_FOR_DYNAMIC_FSE 64
633 #define MAX_SEQ_FOR_STATIC_FSE 1000
635 /* convert length/distances into codes */
636 ZSTD_seqToCodes(seqStorePtr);
638 /* CTable for Literal Lengths */
640 size_t const mostFrequent = FSE_countFast_wksp(count, &max, llCodeTable, nbSeq, zc->tmpCounters);
641 if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
642 *op++ = llCodeTable[0];
643 FSE_buildCTable_rle(CTable_LitLength, (BYTE)max);
645 } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
647 } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (LL_defaultNormLog-1)))) {
648 FSE_buildCTable_wksp(CTable_LitLength, LL_defaultNorm, MaxLL, LL_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
651 size_t nbSeq_1 = nbSeq;
652 const U32 tableLog = FSE_optimalTableLog(LLFSELog, nbSeq, max);
653 if (count[llCodeTable[nbSeq-1]]>1) { count[llCodeTable[nbSeq-1]]--; nbSeq_1--; }
654 FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
655 { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */
656 if (FSE_isError(NCountSize)) return ERROR(GENERIC);
658 FSE_buildCTable_wksp(CTable_LitLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
659 LLtype = set_compressed;
662 /* CTable for Offsets */
664 size_t const mostFrequent = FSE_countFast_wksp(count, &max, ofCodeTable, nbSeq, zc->tmpCounters);
665 if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
666 *op++ = ofCodeTable[0];
667 FSE_buildCTable_rle(CTable_OffsetBits, (BYTE)max);
669 } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
670 Offtype = set_repeat;
671 } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (OF_defaultNormLog-1)))) {
672 FSE_buildCTable_wksp(CTable_OffsetBits, OF_defaultNorm, MaxOff, OF_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
675 size_t nbSeq_1 = nbSeq;
676 const U32 tableLog = FSE_optimalTableLog(OffFSELog, nbSeq, max);
677 if (count[ofCodeTable[nbSeq-1]]>1) { count[ofCodeTable[nbSeq-1]]--; nbSeq_1--; }
678 FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
679 { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */
680 if (FSE_isError(NCountSize)) return ERROR(GENERIC);
682 FSE_buildCTable_wksp(CTable_OffsetBits, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
683 Offtype = set_compressed;
686 /* CTable for MatchLengths */
688 size_t const mostFrequent = FSE_countFast_wksp(count, &max, mlCodeTable, nbSeq, zc->tmpCounters);
689 if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
690 *op++ = *mlCodeTable;
691 FSE_buildCTable_rle(CTable_MatchLength, (BYTE)max);
693 } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
695 } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (ML_defaultNormLog-1)))) {
696 FSE_buildCTable_wksp(CTable_MatchLength, ML_defaultNorm, MaxML, ML_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
699 size_t nbSeq_1 = nbSeq;
700 const U32 tableLog = FSE_optimalTableLog(MLFSELog, nbSeq, max);
701 if (count[mlCodeTable[nbSeq-1]]>1) { count[mlCodeTable[nbSeq-1]]--; nbSeq_1--; }
702 FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
703 { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */
704 if (FSE_isError(NCountSize)) return ERROR(GENERIC);
706 FSE_buildCTable_wksp(CTable_MatchLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
707 MLtype = set_compressed;
710 *seqHead = (BYTE)((LLtype<<6) + (Offtype<<4) + (MLtype<<2));
711 zc->flagStaticTables = 0;
713 /* Encoding Sequences */
714 { BIT_CStream_t blockStream;
715 FSE_CState_t stateMatchLength;
716 FSE_CState_t stateOffsetBits;
717 FSE_CState_t stateLitLength;
719 CHECK_E(BIT_initCStream(&blockStream, op, oend-op), dstSize_tooSmall); /* not enough space remaining */
722 FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);
723 FSE_initCState2(&stateOffsetBits, CTable_OffsetBits, ofCodeTable[nbSeq-1]);
724 FSE_initCState2(&stateLitLength, CTable_LitLength, llCodeTable[nbSeq-1]);
725 BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);
726 if (MEM_32bits()) BIT_flushBits(&blockStream);
727 BIT_addBits(&blockStream, sequences[nbSeq-1].matchLength, ML_bits[mlCodeTable[nbSeq-1]]);
728 if (MEM_32bits()) BIT_flushBits(&blockStream);
730 U32 const ofBits = ofCodeTable[nbSeq-1];
731 int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
733 BIT_addBits(&blockStream, sequences[nbSeq-1].offset, extraBits);
734 BIT_flushBits(&blockStream);
736 BIT_addBits(&blockStream, sequences[nbSeq-1].offset >> extraBits,
739 BIT_addBits(&blockStream, sequences[nbSeq-1].offset, ofCodeTable[nbSeq-1]);
741 BIT_flushBits(&blockStream);
744 for (n=nbSeq-2 ; n<nbSeq ; n--) { /* intentional underflow */
745 BYTE const llCode = llCodeTable[n];
746 BYTE const ofCode = ofCodeTable[n];
747 BYTE const mlCode = mlCodeTable[n];
748 U32 const llBits = LL_bits[llCode];
749 U32 const ofBits = ofCode; /* 32b*/ /* 64b*/
750 U32 const mlBits = ML_bits[mlCode];
752 FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode); /* 15 */ /* 15 */
753 FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode); /* 24 */ /* 24 */
754 if (MEM_32bits()) BIT_flushBits(&blockStream); /* (7)*/
755 FSE_encodeSymbol(&blockStream, &stateLitLength, llCode); /* 16 */ /* 33 */
756 if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))
757 BIT_flushBits(&blockStream); /* (7)*/
758 BIT_addBits(&blockStream, sequences[n].litLength, llBits);
759 if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);
760 BIT_addBits(&blockStream, sequences[n].matchLength, mlBits);
761 if (MEM_32bits()) BIT_flushBits(&blockStream); /* (7)*/
763 int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
765 BIT_addBits(&blockStream, sequences[n].offset, extraBits);
766 BIT_flushBits(&blockStream); /* (7)*/
768 BIT_addBits(&blockStream, sequences[n].offset >> extraBits,
769 ofBits - extraBits); /* 31 */
771 BIT_addBits(&blockStream, sequences[n].offset, ofBits); /* 31 */
773 BIT_flushBits(&blockStream); /* (7)*/
776 FSE_flushCState(&blockStream, &stateMatchLength);
777 FSE_flushCState(&blockStream, &stateOffsetBits);
778 FSE_flushCState(&blockStream, &stateLitLength);
780 { size_t const streamSize = BIT_closeCStream(&blockStream);
781 if (streamSize==0) return ERROR(dstSize_tooSmall); /* not enough space */
785 /* check compressibility */
786 _check_compressibility:
787 { size_t const minGain = ZSTD_minGain(srcSize);
788 size_t const maxCSize = srcSize - minGain;
789 if ((size_t)(op-ostart) >= maxCSize) {
790 zc->flagStaticHufTable = HUF_repeat_none;
794 /* confirm repcodes */
795 { int i; for (i=0; i<ZSTD_REP_NUM; i++) zc->rep[i] = zc->repToConfirm[i]; }
800 #if 0 /* for debug */
801 # define STORESEQ_DEBUG
802 #include <stdio.h> /* fprintf */
803 U32 g_startDebug = 0;
804 const BYTE* g_start = NULL;
807 /*! ZSTD_storeSeq() :
808 Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
809 `offsetCode` : distance to match, or 0 == repCode.
810 `matchCode` : matchLength - MINMATCH
812 MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const void* literals, U32 offsetCode, size_t matchCode)
814 #ifdef STORESEQ_DEBUG
816 const U32 pos = (U32)((const BYTE*)literals - g_start);
817 if (g_start==NULL) g_start = (const BYTE*)literals;
818 if ((pos > 1895000) && (pos < 1895300))
819 fprintf(stderr, "Cpos %6u :%5u literals & match %3u bytes at distance %6u \n",
820 pos, (U32)litLength, (U32)matchCode+MINMATCH, (U32)offsetCode);
824 ZSTD_wildcopy(seqStorePtr->lit, literals, litLength);
825 seqStorePtr->lit += litLength;
828 if (litLength>0xFFFF) { seqStorePtr->longLengthID = 1; seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); }
829 seqStorePtr->sequences[0].litLength = (U16)litLength;
832 seqStorePtr->sequences[0].offset = offsetCode + 1;
835 if (matchCode>0xFFFF) { seqStorePtr->longLengthID = 2; seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); }
836 seqStorePtr->sequences[0].matchLength = (U16)matchCode;
838 seqStorePtr->sequences++;
842 /*-*************************************
843 * Match length counter
844 ***************************************/
845 static unsigned ZSTD_NbCommonBytes (register size_t val)
847 if (MEM_isLittleEndian()) {
849 # if defined(_MSC_VER) && defined(_WIN64)
851 _BitScanForward64( &r, (U64)val );
852 return (unsigned)(r>>3);
853 # elif defined(__GNUC__) && (__GNUC__ >= 3)
854 return (__builtin_ctzll((U64)val) >> 3);
856 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 };
857 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
859 } else { /* 32 bits */
860 # if defined(_MSC_VER)
862 _BitScanForward( &r, (U32)val );
863 return (unsigned)(r>>3);
864 # elif defined(__GNUC__) && (__GNUC__ >= 3)
865 return (__builtin_ctz((U32)val) >> 3);
867 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };
868 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
871 } else { /* Big Endian CPU */
873 # if defined(_MSC_VER) && defined(_WIN64)
875 _BitScanReverse64( &r, val );
876 return (unsigned)(r>>3);
877 # elif defined(__GNUC__) && (__GNUC__ >= 3)
878 return (__builtin_clzll(val) >> 3);
881 const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */
882 if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
883 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
887 } else { /* 32 bits */
888 # if defined(_MSC_VER)
890 _BitScanReverse( &r, (unsigned long)val );
891 return (unsigned)(r>>3);
892 # elif defined(__GNUC__) && (__GNUC__ >= 3)
893 return (__builtin_clz((U32)val) >> 3);
896 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
904 static size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
906 const BYTE* const pStart = pIn;
907 const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
909 while (pIn < pInLoopLimit) {
910 size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
911 if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
912 pIn += ZSTD_NbCommonBytes(diff);
913 return (size_t)(pIn - pStart);
915 if (MEM_64bits()) if ((pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
916 if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
917 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
918 return (size_t)(pIn - pStart);
921 /** ZSTD_count_2segments() :
922 * can count match length with `ip` & `match` in 2 different segments.
923 * convention : on reaching mEnd, match count continue starting from iStart
925 static size_t ZSTD_count_2segments(const BYTE* ip, const BYTE* match, const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
927 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
928 size_t const matchLength = ZSTD_count(ip, match, vEnd);
929 if (match + matchLength != mEnd) return matchLength;
930 return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
934 /*-*************************************
936 ***************************************/
937 static const U32 prime3bytes = 506832829U;
938 static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; }
939 MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
941 static const U32 prime4bytes = 2654435761U;
942 static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
943 static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
945 static const U64 prime5bytes = 889523592379ULL;
946 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h)) ; }
947 static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
949 static const U64 prime6bytes = 227718039650203ULL;
950 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; }
951 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
953 static const U64 prime7bytes = 58295818150454627ULL;
954 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h)) ; }
955 static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
957 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
958 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
959 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
961 static size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
966 case 4: return ZSTD_hash4Ptr(p, hBits);
967 case 5: return ZSTD_hash5Ptr(p, hBits);
968 case 6: return ZSTD_hash6Ptr(p, hBits);
969 case 7: return ZSTD_hash7Ptr(p, hBits);
970 case 8: return ZSTD_hash8Ptr(p, hBits);
975 /*-*************************************
977 ***************************************/
978 static void ZSTD_fillHashTable (ZSTD_CCtx* zc, const void* end, const U32 mls)
980 U32* const hashTable = zc->hashTable;
981 U32 const hBits = zc->params.cParams.hashLog;
982 const BYTE* const base = zc->base;
983 const BYTE* ip = base + zc->nextToUpdate;
984 const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
985 const size_t fastHashFillStep = 3;
988 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip - base);
989 ip += fastHashFillStep;
995 void ZSTD_compressBlock_fast_generic(ZSTD_CCtx* cctx,
996 const void* src, size_t srcSize,
999 U32* const hashTable = cctx->hashTable;
1000 U32 const hBits = cctx->params.cParams.hashLog;
1001 seqStore_t* seqStorePtr = &(cctx->seqStore);
1002 const BYTE* const base = cctx->base;
1003 const BYTE* const istart = (const BYTE*)src;
1004 const BYTE* ip = istart;
1005 const BYTE* anchor = istart;
1006 const U32 lowestIndex = cctx->dictLimit;
1007 const BYTE* const lowest = base + lowestIndex;
1008 const BYTE* const iend = istart + srcSize;
1009 const BYTE* const ilimit = iend - HASH_READ_SIZE;
1010 U32 offset_1=cctx->rep[0], offset_2=cctx->rep[1];
1011 U32 offsetSaved = 0;
1015 { U32 const maxRep = (U32)(ip-lowest);
1016 if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;
1017 if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;
1020 /* Main Search Loop */
1021 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */
1023 size_t const h = ZSTD_hashPtr(ip, hBits, mls);
1024 U32 const current = (U32)(ip-base);
1025 U32 const matchIndex = hashTable[h];
1026 const BYTE* match = base + matchIndex;
1027 hashTable[h] = current; /* update hash table */
1029 if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) {
1030 mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
1032 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1035 if ( (matchIndex <= lowestIndex) || (MEM_read32(match) != MEM_read32(ip)) ) {
1036 ip += ((ip-anchor) >> g_searchStrength) + 1;
1039 mLength = ZSTD_count(ip+4, match+4, iend) + 4;
1040 offset = (U32)(ip-match);
1041 while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1042 offset_2 = offset_1;
1045 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1054 hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2; /* here because current+2 could be > iend-8 */
1055 hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base);
1056 /* check immediate repcode */
1057 while ( (ip <= ilimit)
1059 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
1060 /* store sequence */
1061 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
1062 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; } /* swap offset_2 <=> offset_1 */
1063 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip-base);
1064 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength-MINMATCH);
1067 continue; /* faster when present ... (?) */
1070 /* save reps for next block */
1071 cctx->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved;
1072 cctx->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved;
1075 { size_t const lastLLSize = iend - anchor;
1076 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1077 seqStorePtr->lit += lastLLSize;
1082 static void ZSTD_compressBlock_fast(ZSTD_CCtx* ctx,
1083 const void* src, size_t srcSize)
1085 const U32 mls = ctx->params.cParams.searchLength;
1090 ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 4); return;
1092 ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 5); return;
1094 ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 6); return;
1096 ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 7); return;
1101 static void ZSTD_compressBlock_fast_extDict_generic(ZSTD_CCtx* ctx,
1102 const void* src, size_t srcSize,
1105 U32* hashTable = ctx->hashTable;
1106 const U32 hBits = ctx->params.cParams.hashLog;
1107 seqStore_t* seqStorePtr = &(ctx->seqStore);
1108 const BYTE* const base = ctx->base;
1109 const BYTE* const dictBase = ctx->dictBase;
1110 const BYTE* const istart = (const BYTE*)src;
1111 const BYTE* ip = istart;
1112 const BYTE* anchor = istart;
1113 const U32 lowestIndex = ctx->lowLimit;
1114 const BYTE* const dictStart = dictBase + lowestIndex;
1115 const U32 dictLimit = ctx->dictLimit;
1116 const BYTE* const lowPrefixPtr = base + dictLimit;
1117 const BYTE* const dictEnd = dictBase + dictLimit;
1118 const BYTE* const iend = istart + srcSize;
1119 const BYTE* const ilimit = iend - 8;
1120 U32 offset_1=ctx->rep[0], offset_2=ctx->rep[1];
1123 while (ip < ilimit) { /* < instead of <=, because (ip+1) */
1124 const size_t h = ZSTD_hashPtr(ip, hBits, mls);
1125 const U32 matchIndex = hashTable[h];
1126 const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base;
1127 const BYTE* match = matchBase + matchIndex;
1128 const U32 current = (U32)(ip-base);
1129 const U32 repIndex = current + 1 - offset_1; /* offset_1 expected <= current +1 */
1130 const BYTE* repBase = repIndex < dictLimit ? dictBase : base;
1131 const BYTE* repMatch = repBase + repIndex;
1133 hashTable[h] = current; /* update hash table */
1135 if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex))
1136 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
1137 const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend;
1138 mLength = ZSTD_count_2segments(ip+1+EQUAL_READ32, repMatch+EQUAL_READ32, iend, repMatchEnd, lowPrefixPtr) + EQUAL_READ32;
1140 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1142 if ( (matchIndex < lowestIndex) ||
1143 (MEM_read32(match) != MEM_read32(ip)) ) {
1144 ip += ((ip-anchor) >> g_searchStrength) + 1;
1147 { const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend;
1148 const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;
1150 mLength = ZSTD_count_2segments(ip+EQUAL_READ32, match+EQUAL_READ32, iend, matchEnd, lowPrefixPtr) + EQUAL_READ32;
1151 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1152 offset = current - matchIndex;
1153 offset_2 = offset_1;
1155 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1158 /* found a match : store it */
1164 hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2;
1165 hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base);
1166 /* check immediate repcode */
1167 while (ip <= ilimit) {
1168 U32 const current2 = (U32)(ip-base);
1169 U32 const repIndex2 = current2 - offset_2;
1170 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;
1171 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */
1172 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
1173 const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;
1174 size_t repLength2 = ZSTD_count_2segments(ip+EQUAL_READ32, repMatch2+EQUAL_READ32, iend, repEnd2, lowPrefixPtr) + EQUAL_READ32;
1175 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */
1176 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2-MINMATCH);
1177 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = current2;
1185 /* save reps for next block */
1186 ctx->repToConfirm[0] = offset_1; ctx->repToConfirm[1] = offset_2;
1189 { size_t const lastLLSize = iend - anchor;
1190 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1191 seqStorePtr->lit += lastLLSize;
1196 static void ZSTD_compressBlock_fast_extDict(ZSTD_CCtx* ctx,
1197 const void* src, size_t srcSize)
1199 U32 const mls = ctx->params.cParams.searchLength;
1204 ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 4); return;
1206 ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 5); return;
1208 ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 6); return;
1210 ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 7); return;
1215 /*-*************************************
1217 ***************************************/
1218 static void ZSTD_fillDoubleHashTable (ZSTD_CCtx* cctx, const void* end, const U32 mls)
1220 U32* const hashLarge = cctx->hashTable;
1221 U32 const hBitsL = cctx->params.cParams.hashLog;
1222 U32* const hashSmall = cctx->chainTable;
1223 U32 const hBitsS = cctx->params.cParams.chainLog;
1224 const BYTE* const base = cctx->base;
1225 const BYTE* ip = base + cctx->nextToUpdate;
1226 const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
1227 const size_t fastHashFillStep = 3;
1230 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip - base);
1231 hashLarge[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip - base);
1232 ip += fastHashFillStep;
1238 void ZSTD_compressBlock_doubleFast_generic(ZSTD_CCtx* cctx,
1239 const void* src, size_t srcSize,
1242 U32* const hashLong = cctx->hashTable;
1243 const U32 hBitsL = cctx->params.cParams.hashLog;
1244 U32* const hashSmall = cctx->chainTable;
1245 const U32 hBitsS = cctx->params.cParams.chainLog;
1246 seqStore_t* seqStorePtr = &(cctx->seqStore);
1247 const BYTE* const base = cctx->base;
1248 const BYTE* const istart = (const BYTE*)src;
1249 const BYTE* ip = istart;
1250 const BYTE* anchor = istart;
1251 const U32 lowestIndex = cctx->dictLimit;
1252 const BYTE* const lowest = base + lowestIndex;
1253 const BYTE* const iend = istart + srcSize;
1254 const BYTE* const ilimit = iend - HASH_READ_SIZE;
1255 U32 offset_1=cctx->rep[0], offset_2=cctx->rep[1];
1256 U32 offsetSaved = 0;
1260 { U32 const maxRep = (U32)(ip-lowest);
1261 if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;
1262 if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;
1265 /* Main Search Loop */
1266 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */
1268 size_t const h2 = ZSTD_hashPtr(ip, hBitsL, 8);
1269 size_t const h = ZSTD_hashPtr(ip, hBitsS, mls);
1270 U32 const current = (U32)(ip-base);
1271 U32 const matchIndexL = hashLong[h2];
1272 U32 const matchIndexS = hashSmall[h];
1273 const BYTE* matchLong = base + matchIndexL;
1274 const BYTE* match = base + matchIndexS;
1275 hashLong[h2] = hashSmall[h] = current; /* update hash tables */
1277 if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) { /* note : by construction, offset_1 <= current */
1278 mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
1280 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1283 if ( (matchIndexL > lowestIndex) && (MEM_read64(matchLong) == MEM_read64(ip)) ) {
1284 mLength = ZSTD_count(ip+8, matchLong+8, iend) + 8;
1285 offset = (U32)(ip-matchLong);
1286 while (((ip>anchor) & (matchLong>lowest)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */
1287 } else if ( (matchIndexS > lowestIndex) && (MEM_read32(match) == MEM_read32(ip)) ) {
1288 size_t const h3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
1289 U32 const matchIndex3 = hashLong[h3];
1290 const BYTE* match3 = base + matchIndex3;
1291 hashLong[h3] = current + 1;
1292 if ( (matchIndex3 > lowestIndex) && (MEM_read64(match3) == MEM_read64(ip+1)) ) {
1293 mLength = ZSTD_count(ip+9, match3+8, iend) + 8;
1295 offset = (U32)(ip-match3);
1296 while (((ip>anchor) & (match3>lowest)) && (ip[-1] == match3[-1])) { ip--; match3--; mLength++; } /* catch up */
1298 mLength = ZSTD_count(ip+4, match+4, iend) + 4;
1299 offset = (U32)(ip-match);
1300 while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1303 ip += ((ip-anchor) >> g_searchStrength) + 1;
1307 offset_2 = offset_1;
1310 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1319 hashLong[ZSTD_hashPtr(base+current+2, hBitsL, 8)] =
1320 hashSmall[ZSTD_hashPtr(base+current+2, hBitsS, mls)] = current+2; /* here because current+2 could be > iend-8 */
1321 hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] =
1322 hashSmall[ZSTD_hashPtr(ip-2, hBitsS, mls)] = (U32)(ip-2-base);
1324 /* check immediate repcode */
1325 while ( (ip <= ilimit)
1327 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
1328 /* store sequence */
1329 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
1330 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; } /* swap offset_2 <=> offset_1 */
1331 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip-base);
1332 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip-base);
1333 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength-MINMATCH);
1336 continue; /* faster when present ... (?) */
1339 /* save reps for next block */
1340 cctx->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved;
1341 cctx->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved;
1344 { size_t const lastLLSize = iend - anchor;
1345 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1346 seqStorePtr->lit += lastLLSize;
1351 static void ZSTD_compressBlock_doubleFast(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
1353 const U32 mls = ctx->params.cParams.searchLength;
1358 ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 4); return;
1360 ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 5); return;
1362 ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 6); return;
1364 ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 7); return;
1369 static void ZSTD_compressBlock_doubleFast_extDict_generic(ZSTD_CCtx* ctx,
1370 const void* src, size_t srcSize,
1373 U32* const hashLong = ctx->hashTable;
1374 U32 const hBitsL = ctx->params.cParams.hashLog;
1375 U32* const hashSmall = ctx->chainTable;
1376 U32 const hBitsS = ctx->params.cParams.chainLog;
1377 seqStore_t* seqStorePtr = &(ctx->seqStore);
1378 const BYTE* const base = ctx->base;
1379 const BYTE* const dictBase = ctx->dictBase;
1380 const BYTE* const istart = (const BYTE*)src;
1381 const BYTE* ip = istart;
1382 const BYTE* anchor = istart;
1383 const U32 lowestIndex = ctx->lowLimit;
1384 const BYTE* const dictStart = dictBase + lowestIndex;
1385 const U32 dictLimit = ctx->dictLimit;
1386 const BYTE* const lowPrefixPtr = base + dictLimit;
1387 const BYTE* const dictEnd = dictBase + dictLimit;
1388 const BYTE* const iend = istart + srcSize;
1389 const BYTE* const ilimit = iend - 8;
1390 U32 offset_1=ctx->rep[0], offset_2=ctx->rep[1];
1393 while (ip < ilimit) { /* < instead of <=, because (ip+1) */
1394 const size_t hSmall = ZSTD_hashPtr(ip, hBitsS, mls);
1395 const U32 matchIndex = hashSmall[hSmall];
1396 const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base;
1397 const BYTE* match = matchBase + matchIndex;
1399 const size_t hLong = ZSTD_hashPtr(ip, hBitsL, 8);
1400 const U32 matchLongIndex = hashLong[hLong];
1401 const BYTE* matchLongBase = matchLongIndex < dictLimit ? dictBase : base;
1402 const BYTE* matchLong = matchLongBase + matchLongIndex;
1404 const U32 current = (U32)(ip-base);
1405 const U32 repIndex = current + 1 - offset_1; /* offset_1 expected <= current +1 */
1406 const BYTE* repBase = repIndex < dictLimit ? dictBase : base;
1407 const BYTE* repMatch = repBase + repIndex;
1409 hashSmall[hSmall] = hashLong[hLong] = current; /* update hash table */
1411 if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex))
1412 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
1413 const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend;
1414 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, lowPrefixPtr) + 4;
1416 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1418 if ((matchLongIndex > lowestIndex) && (MEM_read64(matchLong) == MEM_read64(ip))) {
1419 const BYTE* matchEnd = matchLongIndex < dictLimit ? dictEnd : iend;
1420 const BYTE* lowMatchPtr = matchLongIndex < dictLimit ? dictStart : lowPrefixPtr;
1422 mLength = ZSTD_count_2segments(ip+8, matchLong+8, iend, matchEnd, lowPrefixPtr) + 8;
1423 offset = current - matchLongIndex;
1424 while (((ip>anchor) & (matchLong>lowMatchPtr)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */
1425 offset_2 = offset_1;
1427 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1429 } else if ((matchIndex > lowestIndex) && (MEM_read32(match) == MEM_read32(ip))) {
1430 size_t const h3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
1431 U32 const matchIndex3 = hashLong[h3];
1432 const BYTE* const match3Base = matchIndex3 < dictLimit ? dictBase : base;
1433 const BYTE* match3 = match3Base + matchIndex3;
1435 hashLong[h3] = current + 1;
1436 if ( (matchIndex3 > lowestIndex) && (MEM_read64(match3) == MEM_read64(ip+1)) ) {
1437 const BYTE* matchEnd = matchIndex3 < dictLimit ? dictEnd : iend;
1438 const BYTE* lowMatchPtr = matchIndex3 < dictLimit ? dictStart : lowPrefixPtr;
1439 mLength = ZSTD_count_2segments(ip+9, match3+8, iend, matchEnd, lowPrefixPtr) + 8;
1441 offset = current+1 - matchIndex3;
1442 while (((ip>anchor) & (match3>lowMatchPtr)) && (ip[-1] == match3[-1])) { ip--; match3--; mLength++; } /* catch up */
1444 const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend;
1445 const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;
1446 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, lowPrefixPtr) + 4;
1447 offset = current - matchIndex;
1448 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1450 offset_2 = offset_1;
1452 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1455 ip += ((ip-anchor) >> g_searchStrength) + 1;
1459 /* found a match : store it */
1465 hashSmall[ZSTD_hashPtr(base+current+2, hBitsS, mls)] = current+2;
1466 hashLong[ZSTD_hashPtr(base+current+2, hBitsL, 8)] = current+2;
1467 hashSmall[ZSTD_hashPtr(ip-2, hBitsS, mls)] = (U32)(ip-2-base);
1468 hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base);
1469 /* check immediate repcode */
1470 while (ip <= ilimit) {
1471 U32 const current2 = (U32)(ip-base);
1472 U32 const repIndex2 = current2 - offset_2;
1473 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;
1474 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */
1475 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
1476 const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;
1477 size_t const repLength2 = ZSTD_count_2segments(ip+EQUAL_READ32, repMatch2+EQUAL_READ32, iend, repEnd2, lowPrefixPtr) + EQUAL_READ32;
1478 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */
1479 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2-MINMATCH);
1480 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2;
1481 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2;
1489 /* save reps for next block */
1490 ctx->repToConfirm[0] = offset_1; ctx->repToConfirm[1] = offset_2;
1493 { size_t const lastLLSize = iend - anchor;
1494 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1495 seqStorePtr->lit += lastLLSize;
1500 static void ZSTD_compressBlock_doubleFast_extDict(ZSTD_CCtx* ctx,
1501 const void* src, size_t srcSize)
1503 U32 const mls = ctx->params.cParams.searchLength;
1508 ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 4); return;
1510 ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 5); return;
1512 ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 6); return;
1514 ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 7); return;
1519 /*-*************************************
1520 * Binary Tree search
1521 ***************************************/
1522 /** ZSTD_insertBt1() : add one or multiple positions to tree.
1523 * ip : assumed <= iend-8 .
1524 * @return : nb of positions added */
1525 static U32 ZSTD_insertBt1(ZSTD_CCtx* zc, const BYTE* const ip, const U32 mls, const BYTE* const iend, U32 nbCompares,
1528 U32* const hashTable = zc->hashTable;
1529 U32 const hashLog = zc->params.cParams.hashLog;
1530 size_t const h = ZSTD_hashPtr(ip, hashLog, mls);
1531 U32* const bt = zc->chainTable;
1532 U32 const btLog = zc->params.cParams.chainLog - 1;
1533 U32 const btMask = (1 << btLog) - 1;
1534 U32 matchIndex = hashTable[h];
1535 size_t commonLengthSmaller=0, commonLengthLarger=0;
1536 const BYTE* const base = zc->base;
1537 const BYTE* const dictBase = zc->dictBase;
1538 const U32 dictLimit = zc->dictLimit;
1539 const BYTE* const dictEnd = dictBase + dictLimit;
1540 const BYTE* const prefixStart = base + dictLimit;
1542 const U32 current = (U32)(ip-base);
1543 const U32 btLow = btMask >= current ? 0 : current - btMask;
1544 U32* smallerPtr = bt + 2*(current&btMask);
1545 U32* largerPtr = smallerPtr + 1;
1546 U32 dummy32; /* to be nullified at the end */
1547 U32 const windowLow = zc->lowLimit;
1548 U32 matchEndIdx = current+8;
1549 size_t bestLength = 8;
1550 #ifdef ZSTD_C_PREDICT
1551 U32 predictedSmall = *(bt + 2*((current-1)&btMask) + 0);
1552 U32 predictedLarge = *(bt + 2*((current-1)&btMask) + 1);
1553 predictedSmall += (predictedSmall>0);
1554 predictedLarge += (predictedLarge>0);
1555 #endif /* ZSTD_C_PREDICT */
1557 hashTable[h] = current; /* Update Hash Table */
1559 while (nbCompares-- && (matchIndex > windowLow)) {
1560 U32* const nextPtr = bt + 2*(matchIndex & btMask);
1561 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
1563 #ifdef ZSTD_C_PREDICT /* note : can create issues when hlog small <= 11 */
1564 const U32* predictPtr = bt + 2*((matchIndex-1) & btMask); /* written this way, as bt is a roll buffer */
1565 if (matchIndex == predictedSmall) {
1566 /* no need to check length, result known */
1567 *smallerPtr = matchIndex;
1568 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
1569 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */
1570 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
1571 predictedSmall = predictPtr[1] + (predictPtr[1]>0);
1574 if (matchIndex == predictedLarge) {
1575 *largerPtr = matchIndex;
1576 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
1577 largerPtr = nextPtr;
1578 matchIndex = nextPtr[0];
1579 predictedLarge = predictPtr[0] + (predictPtr[0]>0);
1583 if ((!extDict) || (matchIndex+matchLength >= dictLimit)) {
1584 match = base + matchIndex;
1585 if (match[matchLength] == ip[matchLength])
1586 matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iend) +1;
1588 match = dictBase + matchIndex;
1589 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
1590 if (matchIndex+matchLength >= dictLimit)
1591 match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
1594 if (matchLength > bestLength) {
1595 bestLength = matchLength;
1596 if (matchLength > matchEndIdx - matchIndex)
1597 matchEndIdx = matchIndex + (U32)matchLength;
1600 if (ip+matchLength == iend) /* equal : no way to know if inf or sup */
1601 break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt the tree */
1603 if (match[matchLength] < ip[matchLength]) { /* necessarily within correct buffer */
1604 /* match is smaller than current */
1605 *smallerPtr = matchIndex; /* update smaller idx */
1606 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
1607 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
1608 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */
1609 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
1611 /* match is larger than current */
1612 *largerPtr = matchIndex;
1613 commonLengthLarger = matchLength;
1614 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
1615 largerPtr = nextPtr;
1616 matchIndex = nextPtr[0];
1619 *smallerPtr = *largerPtr = 0;
1620 if (bestLength > 384) return MIN(192, (U32)(bestLength - 384)); /* speed optimization */
1621 if (matchEndIdx > current + 8) return matchEndIdx - current - 8;
1626 static size_t ZSTD_insertBtAndFindBestMatch (
1628 const BYTE* const ip, const BYTE* const iend,
1630 U32 nbCompares, const U32 mls,
1633 U32* const hashTable = zc->hashTable;
1634 U32 const hashLog = zc->params.cParams.hashLog;
1635 size_t const h = ZSTD_hashPtr(ip, hashLog, mls);
1636 U32* const bt = zc->chainTable;
1637 U32 const btLog = zc->params.cParams.chainLog - 1;
1638 U32 const btMask = (1 << btLog) - 1;
1639 U32 matchIndex = hashTable[h];
1640 size_t commonLengthSmaller=0, commonLengthLarger=0;
1641 const BYTE* const base = zc->base;
1642 const BYTE* const dictBase = zc->dictBase;
1643 const U32 dictLimit = zc->dictLimit;
1644 const BYTE* const dictEnd = dictBase + dictLimit;
1645 const BYTE* const prefixStart = base + dictLimit;
1646 const U32 current = (U32)(ip-base);
1647 const U32 btLow = btMask >= current ? 0 : current - btMask;
1648 const U32 windowLow = zc->lowLimit;
1649 U32* smallerPtr = bt + 2*(current&btMask);
1650 U32* largerPtr = bt + 2*(current&btMask) + 1;
1651 U32 matchEndIdx = current+8;
1652 U32 dummy32; /* to be nullified at the end */
1653 size_t bestLength = 0;
1655 hashTable[h] = current; /* Update Hash Table */
1657 while (nbCompares-- && (matchIndex > windowLow)) {
1658 U32* const nextPtr = bt + 2*(matchIndex & btMask);
1659 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
1662 if ((!extDict) || (matchIndex+matchLength >= dictLimit)) {
1663 match = base + matchIndex;
1664 if (match[matchLength] == ip[matchLength])
1665 matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iend) +1;
1667 match = dictBase + matchIndex;
1668 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
1669 if (matchIndex+matchLength >= dictLimit)
1670 match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
1673 if (matchLength > bestLength) {
1674 if (matchLength > matchEndIdx - matchIndex)
1675 matchEndIdx = matchIndex + (U32)matchLength;
1676 if ( (4*(int)(matchLength-bestLength)) > (int)(ZSTD_highbit32(current-matchIndex+1) - ZSTD_highbit32((U32)offsetPtr[0]+1)) )
1677 bestLength = matchLength, *offsetPtr = ZSTD_REP_MOVE + current - matchIndex;
1678 if (ip+matchLength == iend) /* equal : no way to know if inf or sup */
1679 break; /* drop, to guarantee consistency (miss a little bit of compression) */
1682 if (match[matchLength] < ip[matchLength]) {
1683 /* match is smaller than current */
1684 *smallerPtr = matchIndex; /* update smaller idx */
1685 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
1686 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
1687 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */
1688 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
1690 /* match is larger than current */
1691 *largerPtr = matchIndex;
1692 commonLengthLarger = matchLength;
1693 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
1694 largerPtr = nextPtr;
1695 matchIndex = nextPtr[0];
1698 *smallerPtr = *largerPtr = 0;
1700 zc->nextToUpdate = (matchEndIdx > current + 8) ? matchEndIdx - 8 : current+1;
1705 static void ZSTD_updateTree(ZSTD_CCtx* zc, const BYTE* const ip, const BYTE* const iend, const U32 nbCompares, const U32 mls)
1707 const BYTE* const base = zc->base;
1708 const U32 target = (U32)(ip - base);
1709 U32 idx = zc->nextToUpdate;
1712 idx += ZSTD_insertBt1(zc, base+idx, mls, iend, nbCompares, 0);
1715 /** ZSTD_BtFindBestMatch() : Tree updater, providing best match */
1716 static size_t ZSTD_BtFindBestMatch (
1718 const BYTE* const ip, const BYTE* const iLimit,
1720 const U32 maxNbAttempts, const U32 mls)
1722 if (ip < zc->base + zc->nextToUpdate) return 0; /* skipped area */
1723 ZSTD_updateTree(zc, ip, iLimit, maxNbAttempts, mls);
1724 return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls, 0);
1728 static size_t ZSTD_BtFindBestMatch_selectMLS (
1729 ZSTD_CCtx* zc, /* Index table will be updated */
1730 const BYTE* ip, const BYTE* const iLimit,
1732 const U32 maxNbAttempts, const U32 matchLengthSearch)
1734 switch(matchLengthSearch)
1737 case 4 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4);
1738 case 5 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5);
1739 case 6 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6);
1744 static void ZSTD_updateTree_extDict(ZSTD_CCtx* zc, const BYTE* const ip, const BYTE* const iend, const U32 nbCompares, const U32 mls)
1746 const BYTE* const base = zc->base;
1747 const U32 target = (U32)(ip - base);
1748 U32 idx = zc->nextToUpdate;
1750 while (idx < target) idx += ZSTD_insertBt1(zc, base+idx, mls, iend, nbCompares, 1);
1754 /** Tree updater, providing best match */
1755 static size_t ZSTD_BtFindBestMatch_extDict (
1757 const BYTE* const ip, const BYTE* const iLimit,
1759 const U32 maxNbAttempts, const U32 mls)
1761 if (ip < zc->base + zc->nextToUpdate) return 0; /* skipped area */
1762 ZSTD_updateTree_extDict(zc, ip, iLimit, maxNbAttempts, mls);
1763 return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls, 1);
1767 static size_t ZSTD_BtFindBestMatch_selectMLS_extDict (
1768 ZSTD_CCtx* zc, /* Index table will be updated */
1769 const BYTE* ip, const BYTE* const iLimit,
1771 const U32 maxNbAttempts, const U32 matchLengthSearch)
1773 switch(matchLengthSearch)
1776 case 4 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4);
1777 case 5 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5);
1778 case 6 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6);
1784 /* *********************************
1786 ***********************************/
1787 #define NEXT_IN_CHAIN(d, mask) chainTable[(d) & mask]
1789 /* Update chains up to ip (excluded)
1790 Assumption : always within prefix (i.e. not within extDict) */
1792 U32 ZSTD_insertAndFindFirstIndex (ZSTD_CCtx* zc, const BYTE* ip, U32 mls)
1794 U32* const hashTable = zc->hashTable;
1795 const U32 hashLog = zc->params.cParams.hashLog;
1796 U32* const chainTable = zc->chainTable;
1797 const U32 chainMask = (1 << zc->params.cParams.chainLog) - 1;
1798 const BYTE* const base = zc->base;
1799 const U32 target = (U32)(ip - base);
1800 U32 idx = zc->nextToUpdate;
1802 while(idx < target) { /* catch up */
1803 size_t const h = ZSTD_hashPtr(base+idx, hashLog, mls);
1804 NEXT_IN_CHAIN(idx, chainMask) = hashTable[h];
1809 zc->nextToUpdate = target;
1810 return hashTable[ZSTD_hashPtr(ip, hashLog, mls)];
1815 FORCE_INLINE /* inlining is important to hardwire a hot branch (template emulation) */
1816 size_t ZSTD_HcFindBestMatch_generic (
1817 ZSTD_CCtx* zc, /* Index table will be updated */
1818 const BYTE* const ip, const BYTE* const iLimit,
1820 const U32 maxNbAttempts, const U32 mls, const U32 extDict)
1822 U32* const chainTable = zc->chainTable;
1823 const U32 chainSize = (1 << zc->params.cParams.chainLog);
1824 const U32 chainMask = chainSize-1;
1825 const BYTE* const base = zc->base;
1826 const BYTE* const dictBase = zc->dictBase;
1827 const U32 dictLimit = zc->dictLimit;
1828 const BYTE* const prefixStart = base + dictLimit;
1829 const BYTE* const dictEnd = dictBase + dictLimit;
1830 const U32 lowLimit = zc->lowLimit;
1831 const U32 current = (U32)(ip-base);
1832 const U32 minChain = current > chainSize ? current - chainSize : 0;
1833 int nbAttempts=maxNbAttempts;
1834 size_t ml=EQUAL_READ32-1;
1836 /* HC4 match finder */
1837 U32 matchIndex = ZSTD_insertAndFindFirstIndex (zc, ip, mls);
1839 for ( ; (matchIndex>lowLimit) & (nbAttempts>0) ; nbAttempts--) {
1842 if ((!extDict) || matchIndex >= dictLimit) {
1843 match = base + matchIndex;
1844 if (match[ml] == ip[ml]) /* potentially better */
1845 currentMl = ZSTD_count(ip, match, iLimit);
1847 match = dictBase + matchIndex;
1848 if (MEM_read32(match) == MEM_read32(ip)) /* assumption : matchIndex <= dictLimit-4 (by table construction) */
1849 currentMl = ZSTD_count_2segments(ip+EQUAL_READ32, match+EQUAL_READ32, iLimit, dictEnd, prefixStart) + EQUAL_READ32;
1852 /* save best solution */
1853 if (currentMl > ml) { ml = currentMl; *offsetPtr = current - matchIndex + ZSTD_REP_MOVE; if (ip+currentMl == iLimit) break; /* best possible, and avoid read overflow*/ }
1855 if (matchIndex <= minChain) break;
1856 matchIndex = NEXT_IN_CHAIN(matchIndex, chainMask);
1863 FORCE_INLINE size_t ZSTD_HcFindBestMatch_selectMLS (
1865 const BYTE* ip, const BYTE* const iLimit,
1867 const U32 maxNbAttempts, const U32 matchLengthSearch)
1869 switch(matchLengthSearch)
1872 case 4 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 0);
1873 case 5 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 0);
1874 case 6 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 0);
1879 FORCE_INLINE size_t ZSTD_HcFindBestMatch_extDict_selectMLS (
1881 const BYTE* ip, const BYTE* const iLimit,
1883 const U32 maxNbAttempts, const U32 matchLengthSearch)
1885 switch(matchLengthSearch)
1888 case 4 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 1);
1889 case 5 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 1);
1890 case 6 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 1);
1895 /* *******************************
1896 * Common parser - lazy strategy
1897 *********************************/
1899 void ZSTD_compressBlock_lazy_generic(ZSTD_CCtx* ctx,
1900 const void* src, size_t srcSize,
1901 const U32 searchMethod, const U32 depth)
1903 seqStore_t* seqStorePtr = &(ctx->seqStore);
1904 const BYTE* const istart = (const BYTE*)src;
1905 const BYTE* ip = istart;
1906 const BYTE* anchor = istart;
1907 const BYTE* const iend = istart + srcSize;
1908 const BYTE* const ilimit = iend - 8;
1909 const BYTE* const base = ctx->base + ctx->dictLimit;
1911 U32 const maxSearches = 1 << ctx->params.cParams.searchLog;
1912 U32 const mls = ctx->params.cParams.searchLength;
1914 typedef size_t (*searchMax_f)(ZSTD_CCtx* zc, const BYTE* ip, const BYTE* iLimit,
1916 U32 maxNbAttempts, U32 matchLengthSearch);
1917 searchMax_f const searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS : ZSTD_HcFindBestMatch_selectMLS;
1918 U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1], savedOffset=0;
1922 ctx->nextToUpdate3 = ctx->nextToUpdate;
1923 { U32 const maxRep = (U32)(ip-base);
1924 if (offset_2 > maxRep) savedOffset = offset_2, offset_2 = 0;
1925 if (offset_1 > maxRep) savedOffset = offset_1, offset_1 = 0;
1929 while (ip < ilimit) {
1930 size_t matchLength=0;
1932 const BYTE* start=ip+1;
1935 if ((offset_1>0) & (MEM_read32(ip+1) == MEM_read32(ip+1 - offset_1))) {
1936 /* repcode : we take it */
1937 matchLength = ZSTD_count(ip+1+EQUAL_READ32, ip+1+EQUAL_READ32-offset_1, iend) + EQUAL_READ32;
1938 if (depth==0) goto _storeSequence;
1941 /* first search (depth 0) */
1942 { size_t offsetFound = 99999999;
1943 size_t const ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls);
1944 if (ml2 > matchLength)
1945 matchLength = ml2, start = ip, offset=offsetFound;
1948 if (matchLength < EQUAL_READ32) {
1949 ip += ((ip-anchor) >> g_searchStrength) + 1; /* jump faster over incompressible sections */
1953 /* let's try to find a better solution */
1957 if ((offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) {
1958 size_t const mlRep = ZSTD_count(ip+EQUAL_READ32, ip+EQUAL_READ32-offset_1, iend) + EQUAL_READ32;
1959 int const gain2 = (int)(mlRep * 3);
1960 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);
1961 if ((mlRep >= EQUAL_READ32) && (gain2 > gain1))
1962 matchLength = mlRep, offset = 0, start = ip;
1964 { size_t offset2=99999999;
1965 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
1966 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */
1967 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4);
1968 if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) {
1969 matchLength = ml2, offset = offset2, start = ip;
1970 continue; /* search a better one */
1973 /* let's find an even better one */
1974 if ((depth==2) && (ip<ilimit)) {
1976 if ((offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) {
1977 size_t const ml2 = ZSTD_count(ip+EQUAL_READ32, ip+EQUAL_READ32-offset_1, iend) + EQUAL_READ32;
1978 int const gain2 = (int)(ml2 * 4);
1979 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);
1980 if ((ml2 >= EQUAL_READ32) && (gain2 > gain1))
1981 matchLength = ml2, offset = 0, start = ip;
1983 { size_t offset2=99999999;
1984 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
1985 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */
1986 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7);
1987 if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) {
1988 matchLength = ml2, offset = offset2, start = ip;
1991 break; /* nothing found : store previous solution */
1996 while ((start>anchor) && (start>base+offset-ZSTD_REP_MOVE) && (start[-1] == start[-1-offset+ZSTD_REP_MOVE])) /* only search for offset within prefix */
1997 { start--; matchLength++; }
1998 offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE);
2001 /* store sequence */
2003 { size_t const litLength = start - anchor;
2004 ZSTD_storeSeq(seqStorePtr, litLength, anchor, (U32)offset, matchLength-MINMATCH);
2005 anchor = ip = start + matchLength;
2008 /* check immediate repcode */
2009 while ( (ip <= ilimit)
2011 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
2012 /* store sequence */
2013 matchLength = ZSTD_count(ip+EQUAL_READ32, ip+EQUAL_READ32-offset_2, iend) + EQUAL_READ32;
2014 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap repcodes */
2015 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength-MINMATCH);
2018 continue; /* faster when present ... (?) */
2021 /* Save reps for next block */
2022 ctx->repToConfirm[0] = offset_1 ? offset_1 : savedOffset;
2023 ctx->repToConfirm[1] = offset_2 ? offset_2 : savedOffset;
2026 { size_t const lastLLSize = iend - anchor;
2027 memcpy(seqStorePtr->lit, anchor, lastLLSize);
2028 seqStorePtr->lit += lastLLSize;
2033 static void ZSTD_compressBlock_btlazy2(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2035 ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 1, 2);
2038 static void ZSTD_compressBlock_lazy2(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2040 ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 2);
2043 static void ZSTD_compressBlock_lazy(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2045 ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 1);
2048 static void ZSTD_compressBlock_greedy(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2050 ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 0);
2055 void ZSTD_compressBlock_lazy_extDict_generic(ZSTD_CCtx* ctx,
2056 const void* src, size_t srcSize,
2057 const U32 searchMethod, const U32 depth)
2059 seqStore_t* seqStorePtr = &(ctx->seqStore);
2060 const BYTE* const istart = (const BYTE*)src;
2061 const BYTE* ip = istart;
2062 const BYTE* anchor = istart;
2063 const BYTE* const iend = istart + srcSize;
2064 const BYTE* const ilimit = iend - 8;
2065 const BYTE* const base = ctx->base;
2066 const U32 dictLimit = ctx->dictLimit;
2067 const U32 lowestIndex = ctx->lowLimit;
2068 const BYTE* const prefixStart = base + dictLimit;
2069 const BYTE* const dictBase = ctx->dictBase;
2070 const BYTE* const dictEnd = dictBase + dictLimit;
2071 const BYTE* const dictStart = dictBase + ctx->lowLimit;
2073 const U32 maxSearches = 1 << ctx->params.cParams.searchLog;
2074 const U32 mls = ctx->params.cParams.searchLength;
2076 typedef size_t (*searchMax_f)(ZSTD_CCtx* zc, const BYTE* ip, const BYTE* iLimit,
2078 U32 maxNbAttempts, U32 matchLengthSearch);
2079 searchMax_f searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS_extDict : ZSTD_HcFindBestMatch_extDict_selectMLS;
2081 U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1];
2084 ctx->nextToUpdate3 = ctx->nextToUpdate;
2085 ip += (ip == prefixStart);
2088 while (ip < ilimit) {
2089 size_t matchLength=0;
2091 const BYTE* start=ip+1;
2092 U32 current = (U32)(ip-base);
2095 { const U32 repIndex = (U32)(current+1 - offset_1);
2096 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2097 const BYTE* const repMatch = repBase + repIndex;
2098 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2099 if (MEM_read32(ip+1) == MEM_read32(repMatch)) {
2100 /* repcode detected we should take it */
2101 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2102 matchLength = ZSTD_count_2segments(ip+1+EQUAL_READ32, repMatch+EQUAL_READ32, iend, repEnd, prefixStart) + EQUAL_READ32;
2103 if (depth==0) goto _storeSequence;
2106 /* first search (depth 0) */
2107 { size_t offsetFound = 99999999;
2108 size_t const ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls);
2109 if (ml2 > matchLength)
2110 matchLength = ml2, start = ip, offset=offsetFound;
2113 if (matchLength < EQUAL_READ32) {
2114 ip += ((ip-anchor) >> g_searchStrength) + 1; /* jump faster over incompressible sections */
2118 /* let's try to find a better solution */
2125 const U32 repIndex = (U32)(current - offset_1);
2126 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2127 const BYTE* const repMatch = repBase + repIndex;
2128 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2129 if (MEM_read32(ip) == MEM_read32(repMatch)) {
2130 /* repcode detected */
2131 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2132 size_t const repLength = ZSTD_count_2segments(ip+EQUAL_READ32, repMatch+EQUAL_READ32, iend, repEnd, prefixStart) + EQUAL_READ32;
2133 int const gain2 = (int)(repLength * 3);
2134 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);
2135 if ((repLength >= EQUAL_READ32) && (gain2 > gain1))
2136 matchLength = repLength, offset = 0, start = ip;
2139 /* search match, depth 1 */
2140 { size_t offset2=99999999;
2141 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2142 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */
2143 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4);
2144 if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) {
2145 matchLength = ml2, offset = offset2, start = ip;
2146 continue; /* search a better one */
2149 /* let's find an even better one */
2150 if ((depth==2) && (ip<ilimit)) {
2155 const U32 repIndex = (U32)(current - offset_1);
2156 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2157 const BYTE* const repMatch = repBase + repIndex;
2158 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2159 if (MEM_read32(ip) == MEM_read32(repMatch)) {
2160 /* repcode detected */
2161 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2162 size_t repLength = ZSTD_count_2segments(ip+EQUAL_READ32, repMatch+EQUAL_READ32, iend, repEnd, prefixStart) + EQUAL_READ32;
2163 int gain2 = (int)(repLength * 4);
2164 int gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);
2165 if ((repLength >= EQUAL_READ32) && (gain2 > gain1))
2166 matchLength = repLength, offset = 0, start = ip;
2169 /* search match, depth 2 */
2170 { size_t offset2=99999999;
2171 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2172 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */
2173 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7);
2174 if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) {
2175 matchLength = ml2, offset = offset2, start = ip;
2178 break; /* nothing found : store previous solution */
2183 U32 const matchIndex = (U32)((start-base) - (offset - ZSTD_REP_MOVE));
2184 const BYTE* match = (matchIndex < dictLimit) ? dictBase + matchIndex : base + matchIndex;
2185 const BYTE* const mStart = (matchIndex < dictLimit) ? dictStart : prefixStart;
2186 while ((start>anchor) && (match>mStart) && (start[-1] == match[-1])) { start--; match--; matchLength++; } /* catch up */
2187 offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE);
2190 /* store sequence */
2192 { size_t const litLength = start - anchor;
2193 ZSTD_storeSeq(seqStorePtr, litLength, anchor, (U32)offset, matchLength-MINMATCH);
2194 anchor = ip = start + matchLength;
2197 /* check immediate repcode */
2198 while (ip <= ilimit) {
2199 const U32 repIndex = (U32)((ip-base) - offset_2);
2200 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2201 const BYTE* const repMatch = repBase + repIndex;
2202 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2203 if (MEM_read32(ip) == MEM_read32(repMatch)) {
2204 /* repcode detected we should take it */
2205 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2206 matchLength = ZSTD_count_2segments(ip+EQUAL_READ32, repMatch+EQUAL_READ32, iend, repEnd, prefixStart) + EQUAL_READ32;
2207 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap offset history */
2208 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength-MINMATCH);
2211 continue; /* faster when present ... (?) */
2216 /* Save reps for next block */
2217 ctx->repToConfirm[0] = offset_1; ctx->repToConfirm[1] = offset_2;
2220 { size_t const lastLLSize = iend - anchor;
2221 memcpy(seqStorePtr->lit, anchor, lastLLSize);
2222 seqStorePtr->lit += lastLLSize;
2227 void ZSTD_compressBlock_greedy_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2229 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 0);
2232 static void ZSTD_compressBlock_lazy_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2234 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 1);
2237 static void ZSTD_compressBlock_lazy2_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2239 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 2);
2242 static void ZSTD_compressBlock_btlazy2_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2244 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 1, 2);
2248 /* The optimal parser */
2249 #include "zstd_opt.h"
2251 static void ZSTD_compressBlock_btopt(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2253 #ifdef ZSTD_OPT_H_91842398743
2254 ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 0);
2256 (void)ctx; (void)src; (void)srcSize;
2261 static void ZSTD_compressBlock_btopt2(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2263 #ifdef ZSTD_OPT_H_91842398743
2264 ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 1);
2266 (void)ctx; (void)src; (void)srcSize;
2271 static void ZSTD_compressBlock_btopt_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2273 #ifdef ZSTD_OPT_H_91842398743
2274 ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 0);
2276 (void)ctx; (void)src; (void)srcSize;
2281 static void ZSTD_compressBlock_btopt2_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2283 #ifdef ZSTD_OPT_H_91842398743
2284 ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 1);
2286 (void)ctx; (void)src; (void)srcSize;
2292 typedef void (*ZSTD_blockCompressor) (ZSTD_CCtx* ctx, const void* src, size_t srcSize);
2294 static ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, int extDict)
2296 static const ZSTD_blockCompressor blockCompressor[2][8] = {
2297 { ZSTD_compressBlock_fast, ZSTD_compressBlock_doubleFast, ZSTD_compressBlock_greedy, ZSTD_compressBlock_lazy, ZSTD_compressBlock_lazy2, ZSTD_compressBlock_btlazy2, ZSTD_compressBlock_btopt, ZSTD_compressBlock_btopt2 },
2298 { ZSTD_compressBlock_fast_extDict, ZSTD_compressBlock_doubleFast_extDict, ZSTD_compressBlock_greedy_extDict, ZSTD_compressBlock_lazy_extDict,ZSTD_compressBlock_lazy2_extDict, ZSTD_compressBlock_btlazy2_extDict, ZSTD_compressBlock_btopt_extDict, ZSTD_compressBlock_btopt2_extDict }
2301 return blockCompressor[extDict][(U32)strat];
2305 static size_t ZSTD_compressBlock_internal(ZSTD_CCtx* zc, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2307 ZSTD_blockCompressor const blockCompressor = ZSTD_selectBlockCompressor(zc->params.cParams.strategy, zc->lowLimit < zc->dictLimit);
2308 const BYTE* const base = zc->base;
2309 const BYTE* const istart = (const BYTE*)src;
2310 const U32 current = (U32)(istart-base);
2311 if (srcSize < MIN_CBLOCK_SIZE+ZSTD_blockHeaderSize+1) return 0; /* don't even attempt compression below a certain srcSize */
2312 ZSTD_resetSeqStore(&(zc->seqStore));
2313 if (current > zc->nextToUpdate + 384)
2314 zc->nextToUpdate = current - MIN(192, (U32)(current - zc->nextToUpdate - 384)); /* update tree not updated after finding very long rep matches */
2315 blockCompressor(zc, src, srcSize);
2316 return ZSTD_compressSequences(zc, dst, dstCapacity, srcSize);
2320 /*! ZSTD_compress_generic() :
2321 * Compress a chunk of data into one or multiple blocks.
2322 * All blocks will be terminated, all input will be consumed.
2323 * Function will issue an error if there is not enough `dstCapacity` to hold the compressed content.
2324 * Frame is supposed already started (header already produced)
2325 * @return : compressed size, or an error code
2327 static size_t ZSTD_compress_generic (ZSTD_CCtx* cctx,
2328 void* dst, size_t dstCapacity,
2329 const void* src, size_t srcSize,
2332 size_t blockSize = cctx->blockSize;
2333 size_t remaining = srcSize;
2334 const BYTE* ip = (const BYTE*)src;
2335 BYTE* const ostart = (BYTE*)dst;
2337 U32 const maxDist = 1 << cctx->params.cParams.windowLog;
2339 if (cctx->params.fParams.checksumFlag && srcSize)
2340 XXH64_update(&cctx->xxhState, src, srcSize);
2343 U32 const lastBlock = lastFrameChunk & (blockSize >= remaining);
2346 if (dstCapacity < ZSTD_blockHeaderSize + MIN_CBLOCK_SIZE) return ERROR(dstSize_tooSmall); /* not enough space to store compressed block */
2347 if (remaining < blockSize) blockSize = remaining;
2349 /* preemptive overflow correction */
2350 if (cctx->lowLimit > (3U<<29)) {
2351 U32 const cycleMask = (1 << ZSTD_cycleLog(cctx->params.cParams.hashLog, cctx->params.cParams.strategy)) - 1;
2352 U32 const current = (U32)(ip - cctx->base);
2353 U32 const newCurrent = (current & cycleMask) + (1 << cctx->params.cParams.windowLog);
2354 U32 const correction = current - newCurrent;
2355 ZSTD_STATIC_ASSERT(ZSTD_WINDOWLOG_MAX_64 <= 30);
2356 ZSTD_reduceIndex(cctx, correction);
2357 cctx->base += correction;
2358 cctx->dictBase += correction;
2359 cctx->lowLimit -= correction;
2360 cctx->dictLimit -= correction;
2361 if (cctx->nextToUpdate < correction) cctx->nextToUpdate = 0;
2362 else cctx->nextToUpdate -= correction;
2365 if ((U32)(ip+blockSize - cctx->base) > cctx->loadedDictEnd + maxDist) {
2366 /* enforce maxDist */
2367 U32 const newLowLimit = (U32)(ip+blockSize - cctx->base) - maxDist;
2368 if (cctx->lowLimit < newLowLimit) cctx->lowLimit = newLowLimit;
2369 if (cctx->dictLimit < cctx->lowLimit) cctx->dictLimit = cctx->lowLimit;
2372 cSize = ZSTD_compressBlock_internal(cctx, op+ZSTD_blockHeaderSize, dstCapacity-ZSTD_blockHeaderSize, ip, blockSize);
2373 if (ZSTD_isError(cSize)) return cSize;
2375 if (cSize == 0) { /* block is not compressible */
2376 U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(blockSize << 3);
2377 if (blockSize + ZSTD_blockHeaderSize > dstCapacity) return ERROR(dstSize_tooSmall);
2378 MEM_writeLE32(op, cBlockHeader24); /* no pb, 4th byte will be overwritten */
2379 memcpy(op + ZSTD_blockHeaderSize, ip, blockSize);
2380 cSize = ZSTD_blockHeaderSize+blockSize;
2382 U32 const cBlockHeader24 = lastBlock + (((U32)bt_compressed)<<1) + (U32)(cSize << 3);
2383 MEM_writeLE24(op, cBlockHeader24);
2384 cSize += ZSTD_blockHeaderSize;
2387 remaining -= blockSize;
2388 dstCapacity -= cSize;
2393 if (lastFrameChunk && (op>ostart)) cctx->stage = ZSTDcs_ending;
2398 static size_t ZSTD_writeFrameHeader(void* dst, size_t dstCapacity,
2399 ZSTD_parameters params, U64 pledgedSrcSize, U32 dictID)
2400 { BYTE* const op = (BYTE*)dst;
2401 U32 const dictIDSizeCode = (dictID>0) + (dictID>=256) + (dictID>=65536); /* 0-3 */
2402 U32 const checksumFlag = params.fParams.checksumFlag>0;
2403 U32 const windowSize = 1U << params.cParams.windowLog;
2404 U32 const singleSegment = params.fParams.contentSizeFlag && (windowSize >= pledgedSrcSize);
2405 BYTE const windowLogByte = (BYTE)((params.cParams.windowLog - ZSTD_WINDOWLOG_ABSOLUTEMIN) << 3);
2406 U32 const fcsCode = params.fParams.contentSizeFlag ?
2407 (pledgedSrcSize>=256) + (pledgedSrcSize>=65536+256) + (pledgedSrcSize>=0xFFFFFFFFU) : /* 0-3 */
2409 BYTE const frameHeaderDecriptionByte = (BYTE)(dictIDSizeCode + (checksumFlag<<2) + (singleSegment<<5) + (fcsCode<<6) );
2412 if (dstCapacity < ZSTD_frameHeaderSize_max) return ERROR(dstSize_tooSmall);
2414 MEM_writeLE32(dst, ZSTD_MAGICNUMBER);
2415 op[4] = frameHeaderDecriptionByte; pos=5;
2416 if (!singleSegment) op[pos++] = windowLogByte;
2417 switch(dictIDSizeCode)
2419 default: /* impossible */
2421 case 1 : op[pos] = (BYTE)(dictID); pos++; break;
2422 case 2 : MEM_writeLE16(op+pos, (U16)dictID); pos+=2; break;
2423 case 3 : MEM_writeLE32(op+pos, dictID); pos+=4; break;
2427 default: /* impossible */
2428 case 0 : if (singleSegment) op[pos++] = (BYTE)(pledgedSrcSize); break;
2429 case 1 : MEM_writeLE16(op+pos, (U16)(pledgedSrcSize-256)); pos+=2; break;
2430 case 2 : MEM_writeLE32(op+pos, (U32)(pledgedSrcSize)); pos+=4; break;
2431 case 3 : MEM_writeLE64(op+pos, (U64)(pledgedSrcSize)); pos+=8; break;
2437 static size_t ZSTD_compressContinue_internal (ZSTD_CCtx* cctx,
2438 void* dst, size_t dstCapacity,
2439 const void* src, size_t srcSize,
2440 U32 frame, U32 lastFrameChunk)
2442 const BYTE* const ip = (const BYTE*) src;
2445 if (cctx->stage==ZSTDcs_created) return ERROR(stage_wrong); /* missing init (ZSTD_compressBegin) */
2447 if (frame && (cctx->stage==ZSTDcs_init)) {
2448 fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, cctx->params, cctx->frameContentSize, cctx->dictID);
2449 if (ZSTD_isError(fhSize)) return fhSize;
2450 dstCapacity -= fhSize;
2451 dst = (char*)dst + fhSize;
2452 cctx->stage = ZSTDcs_ongoing;
2455 /* Check if blocks follow each other */
2456 if (src != cctx->nextSrc) {
2457 /* not contiguous */
2458 ptrdiff_t const delta = cctx->nextSrc - ip;
2459 cctx->lowLimit = cctx->dictLimit;
2460 cctx->dictLimit = (U32)(cctx->nextSrc - cctx->base);
2461 cctx->dictBase = cctx->base;
2462 cctx->base -= delta;
2463 cctx->nextToUpdate = cctx->dictLimit;
2464 if (cctx->dictLimit - cctx->lowLimit < HASH_READ_SIZE) cctx->lowLimit = cctx->dictLimit; /* too small extDict */
2467 /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
2468 if ((ip+srcSize > cctx->dictBase + cctx->lowLimit) & (ip < cctx->dictBase + cctx->dictLimit)) {
2469 ptrdiff_t const highInputIdx = (ip + srcSize) - cctx->dictBase;
2470 U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)cctx->dictLimit) ? cctx->dictLimit : (U32)highInputIdx;
2471 cctx->lowLimit = lowLimitMax;
2474 cctx->nextSrc = ip + srcSize;
2477 size_t const cSize = frame ?
2478 ZSTD_compress_generic (cctx, dst, dstCapacity, src, srcSize, lastFrameChunk) :
2479 ZSTD_compressBlock_internal (cctx, dst, dstCapacity, src, srcSize);
2480 if (ZSTD_isError(cSize)) return cSize;
2481 return cSize + fhSize;
2487 size_t ZSTD_compressContinue (ZSTD_CCtx* cctx,
2488 void* dst, size_t dstCapacity,
2489 const void* src, size_t srcSize)
2491 return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 1, 0);
2495 size_t ZSTD_getBlockSizeMax(ZSTD_CCtx* cctx)
2497 return MIN (ZSTD_BLOCKSIZE_ABSOLUTEMAX, 1 << cctx->params.cParams.windowLog);
2500 size_t ZSTD_compressBlock(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2502 size_t const blockSizeMax = ZSTD_getBlockSizeMax(cctx);
2503 if (srcSize > blockSizeMax) return ERROR(srcSize_wrong);
2504 return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 0, 0);
2508 static size_t ZSTD_loadDictionaryContent(ZSTD_CCtx* zc, const void* src, size_t srcSize)
2510 const BYTE* const ip = (const BYTE*) src;
2511 const BYTE* const iend = ip + srcSize;
2513 /* input becomes current prefix */
2514 zc->lowLimit = zc->dictLimit;
2515 zc->dictLimit = (U32)(zc->nextSrc - zc->base);
2516 zc->dictBase = zc->base;
2517 zc->base += ip - zc->nextSrc;
2518 zc->nextToUpdate = zc->dictLimit;
2519 zc->loadedDictEnd = zc->forceWindow ? 0 : (U32)(iend - zc->base);
2522 if (srcSize <= HASH_READ_SIZE) return 0;
2524 switch(zc->params.cParams.strategy)
2527 ZSTD_fillHashTable (zc, iend, zc->params.cParams.searchLength);
2531 ZSTD_fillDoubleHashTable (zc, iend, zc->params.cParams.searchLength);
2537 ZSTD_insertAndFindFirstIndex (zc, iend-HASH_READ_SIZE, zc->params.cParams.searchLength);
2543 ZSTD_updateTree(zc, iend-HASH_READ_SIZE, iend, 1 << zc->params.cParams.searchLog, zc->params.cParams.searchLength);
2547 return ERROR(GENERIC); /* strategy doesn't exist; impossible */
2550 zc->nextToUpdate = (U32)(iend - zc->base);
2555 /* Dictionaries that assign zero probability to symbols that show up causes problems
2556 when FSE encoding. Refuse dictionaries that assign zero probability to symbols
2557 that we may encounter during compression.
2558 NOTE: This behavior is not standard and could be improved in the future. */
2559 static size_t ZSTD_checkDictNCount(short* normalizedCounter, unsigned dictMaxSymbolValue, unsigned maxSymbolValue) {
2561 if (dictMaxSymbolValue < maxSymbolValue) return ERROR(dictionary_corrupted);
2562 for (s = 0; s <= maxSymbolValue; ++s) {
2563 if (normalizedCounter[s] == 0) return ERROR(dictionary_corrupted);
2569 /* Dictionary format :
2570 Magic == ZSTD_DICT_MAGIC (4 bytes)
2571 HUF_writeCTable(256)
2572 FSE_writeNCount(off)
2578 /*! ZSTD_loadDictEntropyStats() :
2579 @return : size read from dictionary
2580 note : magic number supposed already checked */
2581 static size_t ZSTD_loadDictEntropyStats(ZSTD_CCtx* cctx, const void* dict, size_t dictSize)
2583 const BYTE* dictPtr = (const BYTE*)dict;
2584 const BYTE* const dictEnd = dictPtr + dictSize;
2585 short offcodeNCount[MaxOff+1];
2586 unsigned offcodeMaxValue = MaxOff;
2587 BYTE scratchBuffer[1<<MAX(MLFSELog,LLFSELog)];
2589 { size_t const hufHeaderSize = HUF_readCTable(cctx->hufTable, 255, dict, dictSize);
2590 if (HUF_isError(hufHeaderSize)) return ERROR(dictionary_corrupted);
2591 dictPtr += hufHeaderSize;
2594 { unsigned offcodeLog;
2595 size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
2596 if (FSE_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
2597 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
2598 /* Defer checking offcodeMaxValue because we need to know the size of the dictionary content */
2599 CHECK_E (FSE_buildCTable_wksp(cctx->offcodeCTable, offcodeNCount, offcodeMaxValue, offcodeLog, scratchBuffer, sizeof(scratchBuffer)), dictionary_corrupted);
2600 dictPtr += offcodeHeaderSize;
2603 { short matchlengthNCount[MaxML+1];
2604 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
2605 size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
2606 if (FSE_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
2607 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
2608 /* Every match length code must have non-zero probability */
2609 CHECK_F (ZSTD_checkDictNCount(matchlengthNCount, matchlengthMaxValue, MaxML));
2610 CHECK_E (FSE_buildCTable_wksp(cctx->matchlengthCTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, scratchBuffer, sizeof(scratchBuffer)), dictionary_corrupted);
2611 dictPtr += matchlengthHeaderSize;
2614 { short litlengthNCount[MaxLL+1];
2615 unsigned litlengthMaxValue = MaxLL, litlengthLog;
2616 size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
2617 if (FSE_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
2618 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
2619 /* Every literal length code must have non-zero probability */
2620 CHECK_F (ZSTD_checkDictNCount(litlengthNCount, litlengthMaxValue, MaxLL));
2621 CHECK_E(FSE_buildCTable_wksp(cctx->litlengthCTable, litlengthNCount, litlengthMaxValue, litlengthLog, scratchBuffer, sizeof(scratchBuffer)), dictionary_corrupted);
2622 dictPtr += litlengthHeaderSize;
2625 if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
2626 cctx->rep[0] = MEM_readLE32(dictPtr+0); if (cctx->rep[0] == 0 || cctx->rep[0] >= dictSize) return ERROR(dictionary_corrupted);
2627 cctx->rep[1] = MEM_readLE32(dictPtr+4); if (cctx->rep[1] == 0 || cctx->rep[1] >= dictSize) return ERROR(dictionary_corrupted);
2628 cctx->rep[2] = MEM_readLE32(dictPtr+8); if (cctx->rep[2] == 0 || cctx->rep[2] >= dictSize) return ERROR(dictionary_corrupted);
2631 { U32 offcodeMax = MaxOff;
2632 if ((size_t)(dictEnd - dictPtr) <= ((U32)-1) - 128 KB) {
2633 U32 const maxOffset = (U32)(dictEnd - dictPtr) + 128 KB; /* The maximum offset that must be supported */
2634 /* Calculate minimum offset code required to represent maxOffset */
2635 offcodeMax = ZSTD_highbit32(maxOffset);
2637 /* Every possible supported offset <= dictContentSize + 128 KB must be representable */
2638 CHECK_F (ZSTD_checkDictNCount(offcodeNCount, offcodeMaxValue, MIN(offcodeMax, MaxOff)));
2641 cctx->flagStaticTables = 1;
2642 cctx->flagStaticHufTable = HUF_repeat_valid;
2643 return dictPtr - (const BYTE*)dict;
2646 /** ZSTD_compress_insertDictionary() :
2647 * @return : 0, or an error code */
2648 static size_t ZSTD_compress_insertDictionary(ZSTD_CCtx* zc, const void* dict, size_t dictSize)
2650 if ((dict==NULL) || (dictSize<=8)) return 0;
2652 /* dict as pure content */
2653 if ((MEM_readLE32(dict) != ZSTD_DICT_MAGIC) || (zc->forceRawDict))
2654 return ZSTD_loadDictionaryContent(zc, dict, dictSize);
2655 zc->dictID = zc->params.fParams.noDictIDFlag ? 0 : MEM_readLE32((const char*)dict+4);
2657 /* known magic number : dict is parsed for entropy stats and content */
2658 { size_t const loadError = ZSTD_loadDictEntropyStats(zc, (const char*)dict+8 /* skip dictHeader */, dictSize-8);
2659 size_t const eSize = loadError + 8;
2660 if (ZSTD_isError(loadError)) return loadError;
2661 return ZSTD_loadDictionaryContent(zc, (const char*)dict+eSize, dictSize-eSize);
2665 /*! ZSTD_compressBegin_internal() :
2666 * @return : 0, or an error code */
2667 static size_t ZSTD_compressBegin_internal(ZSTD_CCtx* cctx,
2668 const void* dict, size_t dictSize,
2669 ZSTD_parameters params, U64 pledgedSrcSize)
2671 ZSTD_compResetPolicy_e const crp = dictSize ? ZSTDcrp_fullReset : ZSTDcrp_continue;
2672 CHECK_F(ZSTD_resetCCtx_advanced(cctx, params, pledgedSrcSize, crp));
2673 return ZSTD_compress_insertDictionary(cctx, dict, dictSize);
2677 /*! ZSTD_compressBegin_advanced() :
2678 * @return : 0, or an error code */
2679 size_t ZSTD_compressBegin_advanced(ZSTD_CCtx* cctx,
2680 const void* dict, size_t dictSize,
2681 ZSTD_parameters params, unsigned long long pledgedSrcSize)
2683 /* compression parameters verification and optimization */
2684 CHECK_F(ZSTD_checkCParams(params.cParams));
2685 return ZSTD_compressBegin_internal(cctx, dict, dictSize, params, pledgedSrcSize);
2689 size_t ZSTD_compressBegin_usingDict(ZSTD_CCtx* cctx, const void* dict, size_t dictSize, int compressionLevel)
2691 ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, dictSize);
2692 return ZSTD_compressBegin_internal(cctx, dict, dictSize, params, 0);
2696 size_t ZSTD_compressBegin(ZSTD_CCtx* cctx, int compressionLevel)
2698 return ZSTD_compressBegin_usingDict(cctx, NULL, 0, compressionLevel);
2702 /*! ZSTD_writeEpilogue() :
2704 * @return : nb of bytes written into dst (or an error code) */
2705 static size_t ZSTD_writeEpilogue(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity)
2707 BYTE* const ostart = (BYTE*)dst;
2711 if (cctx->stage == ZSTDcs_created) return ERROR(stage_wrong); /* init missing */
2713 /* special case : empty frame */
2714 if (cctx->stage == ZSTDcs_init) {
2715 fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, cctx->params, 0, 0);
2716 if (ZSTD_isError(fhSize)) return fhSize;
2717 dstCapacity -= fhSize;
2719 cctx->stage = ZSTDcs_ongoing;
2722 if (cctx->stage != ZSTDcs_ending) {
2723 /* write one last empty block, make it the "last" block */
2724 U32 const cBlockHeader24 = 1 /* last block */ + (((U32)bt_raw)<<1) + 0;
2725 if (dstCapacity<4) return ERROR(dstSize_tooSmall);
2726 MEM_writeLE32(op, cBlockHeader24);
2727 op += ZSTD_blockHeaderSize;
2728 dstCapacity -= ZSTD_blockHeaderSize;
2731 if (cctx->params.fParams.checksumFlag) {
2732 U32 const checksum = (U32) XXH64_digest(&cctx->xxhState);
2733 if (dstCapacity<4) return ERROR(dstSize_tooSmall);
2734 MEM_writeLE32(op, checksum);
2738 cctx->stage = ZSTDcs_created; /* return to "created but no init" status */
2743 size_t ZSTD_compressEnd (ZSTD_CCtx* cctx,
2744 void* dst, size_t dstCapacity,
2745 const void* src, size_t srcSize)
2748 size_t const cSize = ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 1, 1);
2749 if (ZSTD_isError(cSize)) return cSize;
2750 endResult = ZSTD_writeEpilogue(cctx, (char*)dst + cSize, dstCapacity-cSize);
2751 if (ZSTD_isError(endResult)) return endResult;
2752 return cSize + endResult;
2756 static size_t ZSTD_compress_internal (ZSTD_CCtx* cctx,
2757 void* dst, size_t dstCapacity,
2758 const void* src, size_t srcSize,
2759 const void* dict,size_t dictSize,
2760 ZSTD_parameters params)
2762 CHECK_F(ZSTD_compressBegin_internal(cctx, dict, dictSize, params, srcSize));
2763 return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
2766 size_t ZSTD_compress_advanced (ZSTD_CCtx* ctx,
2767 void* dst, size_t dstCapacity,
2768 const void* src, size_t srcSize,
2769 const void* dict,size_t dictSize,
2770 ZSTD_parameters params)
2772 CHECK_F(ZSTD_checkCParams(params.cParams));
2773 return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, dict, dictSize, params);
2776 size_t ZSTD_compress_usingDict(ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, const void* dict, size_t dictSize, int compressionLevel)
2778 ZSTD_parameters params = ZSTD_getParams(compressionLevel, srcSize, dict ? dictSize : 0);
2779 params.fParams.contentSizeFlag = 1;
2780 return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, dict, dictSize, params);
2783 size_t ZSTD_compressCCtx (ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel)
2785 return ZSTD_compress_usingDict(ctx, dst, dstCapacity, src, srcSize, NULL, 0, compressionLevel);
2788 size_t ZSTD_compress(void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel)
2792 memset(&ctxBody, 0, sizeof(ctxBody));
2793 memcpy(&ctxBody.customMem, &defaultCustomMem, sizeof(ZSTD_customMem));
2794 result = ZSTD_compressCCtx(&ctxBody, dst, dstCapacity, src, srcSize, compressionLevel);
2795 ZSTD_free(ctxBody.workSpace, defaultCustomMem); /* can't free ctxBody itself, as it's on stack; free only heap content */
2800 /* ===== Dictionary API ===== */
2802 struct ZSTD_CDict_s {
2804 const void* dictContent;
2805 size_t dictContentSize;
2806 ZSTD_CCtx* refContext;
2807 }; /* typedef'd tp ZSTD_CDict within "zstd.h" */
2809 size_t ZSTD_sizeof_CDict(const ZSTD_CDict* cdict)
2811 if (cdict==NULL) return 0; /* support sizeof on NULL */
2812 return ZSTD_sizeof_CCtx(cdict->refContext) + (cdict->dictBuffer ? cdict->dictContentSize : 0) + sizeof(*cdict);
2815 ZSTD_CDict* ZSTD_createCDict_advanced(const void* dictBuffer, size_t dictSize, unsigned byReference,
2816 ZSTD_parameters params, ZSTD_customMem customMem)
2818 if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;
2819 if (!customMem.customAlloc || !customMem.customFree) return NULL;
2821 { ZSTD_CDict* const cdict = (ZSTD_CDict*) ZSTD_malloc(sizeof(ZSTD_CDict), customMem);
2822 ZSTD_CCtx* const cctx = ZSTD_createCCtx_advanced(customMem);
2824 if (!cdict || !cctx) {
2825 ZSTD_free(cdict, customMem);
2826 ZSTD_freeCCtx(cctx);
2830 if ((byReference) || (!dictBuffer) || (!dictSize)) {
2831 cdict->dictBuffer = NULL;
2832 cdict->dictContent = dictBuffer;
2834 void* const internalBuffer = ZSTD_malloc(dictSize, customMem);
2835 if (!internalBuffer) { ZSTD_free(cctx, customMem); ZSTD_free(cdict, customMem); return NULL; }
2836 memcpy(internalBuffer, dictBuffer, dictSize);
2837 cdict->dictBuffer = internalBuffer;
2838 cdict->dictContent = internalBuffer;
2841 { size_t const errorCode = ZSTD_compressBegin_advanced(cctx, cdict->dictContent, dictSize, params, 0);
2842 if (ZSTD_isError(errorCode)) {
2843 ZSTD_free(cdict->dictBuffer, customMem);
2844 ZSTD_free(cdict, customMem);
2845 ZSTD_freeCCtx(cctx);
2849 cdict->refContext = cctx;
2850 cdict->dictContentSize = dictSize;
2855 ZSTD_CDict* ZSTD_createCDict(const void* dict, size_t dictSize, int compressionLevel)
2857 ZSTD_customMem const allocator = { NULL, NULL, NULL };
2858 ZSTD_parameters params = ZSTD_getParams(compressionLevel, 0, dictSize);
2859 params.fParams.contentSizeFlag = 1;
2860 return ZSTD_createCDict_advanced(dict, dictSize, 0, params, allocator);
2863 ZSTD_CDict* ZSTD_createCDict_byReference(const void* dict, size_t dictSize, int compressionLevel)
2865 ZSTD_customMem const allocator = { NULL, NULL, NULL };
2866 ZSTD_parameters params = ZSTD_getParams(compressionLevel, 0, dictSize);
2867 params.fParams.contentSizeFlag = 1;
2868 return ZSTD_createCDict_advanced(dict, dictSize, 1, params, allocator);
2871 size_t ZSTD_freeCDict(ZSTD_CDict* cdict)
2873 if (cdict==NULL) return 0; /* support free on NULL */
2874 { ZSTD_customMem const cMem = cdict->refContext->customMem;
2875 ZSTD_freeCCtx(cdict->refContext);
2876 ZSTD_free(cdict->dictBuffer, cMem);
2877 ZSTD_free(cdict, cMem);
2882 static ZSTD_parameters ZSTD_getParamsFromCDict(const ZSTD_CDict* cdict) {
2883 return ZSTD_getParamsFromCCtx(cdict->refContext);
2886 size_t ZSTD_compressBegin_usingCDict(ZSTD_CCtx* cctx, const ZSTD_CDict* cdict, unsigned long long pledgedSrcSize)
2888 if (cdict->dictContentSize) CHECK_F(ZSTD_copyCCtx(cctx, cdict->refContext, pledgedSrcSize))
2890 ZSTD_parameters params = cdict->refContext->params;
2891 params.fParams.contentSizeFlag = (pledgedSrcSize > 0);
2892 CHECK_F(ZSTD_compressBegin_advanced(cctx, NULL, 0, params, pledgedSrcSize));
2897 /*! ZSTD_compress_usingCDict() :
2898 * Compression using a digested Dictionary.
2899 * Faster startup than ZSTD_compress_usingDict(), recommended when same dictionary is used multiple times.
2900 * Note that compression level is decided during dictionary creation */
2901 size_t ZSTD_compress_usingCDict(ZSTD_CCtx* cctx,
2902 void* dst, size_t dstCapacity,
2903 const void* src, size_t srcSize,
2904 const ZSTD_CDict* cdict)
2906 CHECK_F(ZSTD_compressBegin_usingCDict(cctx, cdict, srcSize));
2908 if (cdict->refContext->params.fParams.contentSizeFlag==1) {
2909 cctx->params.fParams.contentSizeFlag = 1;
2910 cctx->frameContentSize = srcSize;
2913 return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
2918 /* ******************************************************************
2920 ********************************************************************/
2922 typedef enum { zcss_init, zcss_load, zcss_flush, zcss_final } ZSTD_cStreamStage;
2924 struct ZSTD_CStream_s {
2926 ZSTD_CDict* cdictLocal;
2927 const ZSTD_CDict* cdict;
2930 size_t inToCompress;
2932 size_t inBuffTarget;
2936 size_t outBuffContentSize;
2937 size_t outBuffFlushedSize;
2938 ZSTD_cStreamStage stage;
2943 ZSTD_parameters params;
2944 ZSTD_customMem customMem;
2945 }; /* typedef'd to ZSTD_CStream within "zstd.h" */
2947 ZSTD_CStream* ZSTD_createCStream(void)
2949 return ZSTD_createCStream_advanced(defaultCustomMem);
2952 ZSTD_CStream* ZSTD_createCStream_advanced(ZSTD_customMem customMem)
2956 if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;
2957 if (!customMem.customAlloc || !customMem.customFree) return NULL;
2959 zcs = (ZSTD_CStream*)ZSTD_malloc(sizeof(ZSTD_CStream), customMem);
2960 if (zcs==NULL) return NULL;
2961 memset(zcs, 0, sizeof(ZSTD_CStream));
2962 memcpy(&zcs->customMem, &customMem, sizeof(ZSTD_customMem));
2963 zcs->cctx = ZSTD_createCCtx_advanced(customMem);
2964 if (zcs->cctx == NULL) { ZSTD_freeCStream(zcs); return NULL; }
2968 size_t ZSTD_freeCStream(ZSTD_CStream* zcs)
2970 if (zcs==NULL) return 0; /* support free on NULL */
2971 { ZSTD_customMem const cMem = zcs->customMem;
2972 ZSTD_freeCCtx(zcs->cctx);
2973 ZSTD_freeCDict(zcs->cdictLocal);
2974 ZSTD_free(zcs->inBuff, cMem);
2975 ZSTD_free(zcs->outBuff, cMem);
2976 ZSTD_free(zcs, cMem);
2982 /*====== Initialization ======*/
2984 size_t ZSTD_CStreamInSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; }
2985 size_t ZSTD_CStreamOutSize(void) { return ZSTD_compressBound(ZSTD_BLOCKSIZE_ABSOLUTEMAX) + ZSTD_blockHeaderSize + 4 /* 32-bits hash */ ; }
2987 static size_t ZSTD_resetCStream_internal(ZSTD_CStream* zcs, unsigned long long pledgedSrcSize)
2989 if (zcs->inBuffSize==0) return ERROR(stage_wrong); /* zcs has not been init at least once => can't reset */
2991 if (zcs->cdict) CHECK_F(ZSTD_compressBegin_usingCDict(zcs->cctx, zcs->cdict, pledgedSrcSize))
2992 else CHECK_F(ZSTD_compressBegin_advanced(zcs->cctx, NULL, 0, zcs->params, pledgedSrcSize));
2994 zcs->inToCompress = 0;
2996 zcs->inBuffTarget = zcs->blockSize;
2997 zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0;
2998 zcs->stage = zcss_load;
2999 zcs->frameEnded = 0;
3000 zcs->pledgedSrcSize = pledgedSrcSize;
3001 zcs->inputProcessed = 0;
3002 return 0; /* ready to go */
3005 size_t ZSTD_resetCStream(ZSTD_CStream* zcs, unsigned long long pledgedSrcSize)
3008 zcs->params.fParams.contentSizeFlag = (pledgedSrcSize > 0);
3010 return ZSTD_resetCStream_internal(zcs, pledgedSrcSize);
3013 size_t ZSTD_initCStream_advanced(ZSTD_CStream* zcs,
3014 const void* dict, size_t dictSize,
3015 ZSTD_parameters params, unsigned long long pledgedSrcSize)
3017 /* allocate buffers */
3018 { size_t const neededInBuffSize = (size_t)1 << params.cParams.windowLog;
3019 if (zcs->inBuffSize < neededInBuffSize) {
3020 zcs->inBuffSize = neededInBuffSize;
3021 ZSTD_free(zcs->inBuff, zcs->customMem);
3022 zcs->inBuff = (char*) ZSTD_malloc(neededInBuffSize, zcs->customMem);
3023 if (zcs->inBuff == NULL) return ERROR(memory_allocation);
3025 zcs->blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, neededInBuffSize);
3027 if (zcs->outBuffSize < ZSTD_compressBound(zcs->blockSize)+1) {
3028 zcs->outBuffSize = ZSTD_compressBound(zcs->blockSize)+1;
3029 ZSTD_free(zcs->outBuff, zcs->customMem);
3030 zcs->outBuff = (char*) ZSTD_malloc(zcs->outBuffSize, zcs->customMem);
3031 if (zcs->outBuff == NULL) return ERROR(memory_allocation);
3034 if (dict && dictSize >= 8) {
3035 ZSTD_freeCDict(zcs->cdictLocal);
3036 zcs->cdictLocal = ZSTD_createCDict_advanced(dict, dictSize, 0, params, zcs->customMem);
3037 if (zcs->cdictLocal == NULL) return ERROR(memory_allocation);
3038 zcs->cdict = zcs->cdictLocal;
3039 } else zcs->cdict = NULL;
3041 zcs->checksum = params.fParams.checksumFlag > 0;
3042 zcs->params = params;
3044 return ZSTD_resetCStream_internal(zcs, pledgedSrcSize);
3047 /* note : cdict must outlive compression session */
3048 size_t ZSTD_initCStream_usingCDict(ZSTD_CStream* zcs, const ZSTD_CDict* cdict)
3050 ZSTD_parameters const params = ZSTD_getParamsFromCDict(cdict);
3051 size_t const initError = ZSTD_initCStream_advanced(zcs, NULL, 0, params, 0);
3053 zcs->cctx->dictID = params.fParams.noDictIDFlag ? 0 : cdict->refContext->dictID;
3057 size_t ZSTD_initCStream_usingDict(ZSTD_CStream* zcs, const void* dict, size_t dictSize, int compressionLevel)
3059 ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, dictSize);
3060 return ZSTD_initCStream_advanced(zcs, dict, dictSize, params, 0);
3063 size_t ZSTD_initCStream_srcSize(ZSTD_CStream* zcs, int compressionLevel, unsigned long long pledgedSrcSize)
3065 ZSTD_parameters params = ZSTD_getParams(compressionLevel, pledgedSrcSize, 0);
3066 if (pledgedSrcSize) params.fParams.contentSizeFlag = 1;
3067 return ZSTD_initCStream_advanced(zcs, NULL, 0, params, pledgedSrcSize);
3070 size_t ZSTD_initCStream(ZSTD_CStream* zcs, int compressionLevel)
3072 return ZSTD_initCStream_usingDict(zcs, NULL, 0, compressionLevel);
3075 size_t ZSTD_sizeof_CStream(const ZSTD_CStream* zcs)
3077 if (zcs==NULL) return 0; /* support sizeof on NULL */
3078 return sizeof(*zcs) + ZSTD_sizeof_CCtx(zcs->cctx) + ZSTD_sizeof_CDict(zcs->cdictLocal) + zcs->outBuffSize + zcs->inBuffSize;
3081 /*====== Compression ======*/
3083 typedef enum { zsf_gather, zsf_flush, zsf_end } ZSTD_flush_e;
3085 MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3087 size_t const length = MIN(dstCapacity, srcSize);
3088 memcpy(dst, src, length);
3092 static size_t ZSTD_compressStream_generic(ZSTD_CStream* zcs,
3093 void* dst, size_t* dstCapacityPtr,
3094 const void* src, size_t* srcSizePtr,
3095 ZSTD_flush_e const flush)
3097 U32 someMoreWork = 1;
3098 const char* const istart = (const char*)src;
3099 const char* const iend = istart + *srcSizePtr;
3100 const char* ip = istart;
3101 char* const ostart = (char*)dst;
3102 char* const oend = ostart + *dstCapacityPtr;
3105 while (someMoreWork) {
3108 case zcss_init: return ERROR(init_missing); /* call ZBUFF_compressInit() first ! */
3111 /* complete inBuffer */
3112 { size_t const toLoad = zcs->inBuffTarget - zcs->inBuffPos;
3113 size_t const loaded = ZSTD_limitCopy(zcs->inBuff + zcs->inBuffPos, toLoad, ip, iend-ip);
3114 zcs->inBuffPos += loaded;
3116 if ( (zcs->inBuffPos==zcs->inToCompress) || (!flush && (toLoad != loaded)) ) {
3117 someMoreWork = 0; break; /* not enough input to get a full block : stop there, wait for more */
3119 /* compress current block (note : this stage cannot be stopped in the middle) */
3122 size_t const iSize = zcs->inBuffPos - zcs->inToCompress;
3123 size_t oSize = oend-op;
3124 if (oSize >= ZSTD_compressBound(iSize))
3125 cDst = op; /* compress directly into output buffer (avoid flush stage) */
3127 cDst = zcs->outBuff, oSize = zcs->outBuffSize;
3128 cSize = (flush == zsf_end) ?
3129 ZSTD_compressEnd(zcs->cctx, cDst, oSize, zcs->inBuff + zcs->inToCompress, iSize) :
3130 ZSTD_compressContinue(zcs->cctx, cDst, oSize, zcs->inBuff + zcs->inToCompress, iSize);
3131 if (ZSTD_isError(cSize)) return cSize;
3132 if (flush == zsf_end) zcs->frameEnded = 1;
3133 /* prepare next block */
3134 zcs->inBuffTarget = zcs->inBuffPos + zcs->blockSize;
3135 if (zcs->inBuffTarget > zcs->inBuffSize)
3136 zcs->inBuffPos = 0, zcs->inBuffTarget = zcs->blockSize; /* note : inBuffSize >= blockSize */
3137 zcs->inToCompress = zcs->inBuffPos;
3138 if (cDst == op) { op += cSize; break; } /* no need to flush */
3139 zcs->outBuffContentSize = cSize;
3140 zcs->outBuffFlushedSize = 0;
3141 zcs->stage = zcss_flush; /* pass-through to flush stage */
3145 { size_t const toFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3146 size_t const flushed = ZSTD_limitCopy(op, oend-op, zcs->outBuff + zcs->outBuffFlushedSize, toFlush);
3148 zcs->outBuffFlushedSize += flushed;
3149 if (toFlush!=flushed) { someMoreWork = 0; break; } /* dst too small to store flushed data : stop there */
3150 zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0;
3151 zcs->stage = zcss_load;
3156 someMoreWork = 0; /* do nothing */
3160 return ERROR(GENERIC); /* impossible */
3164 *srcSizePtr = ip - istart;
3165 *dstCapacityPtr = op - ostart;
3166 zcs->inputProcessed += *srcSizePtr;
3167 if (zcs->frameEnded) return 0;
3168 { size_t hintInSize = zcs->inBuffTarget - zcs->inBuffPos;
3169 if (hintInSize==0) hintInSize = zcs->blockSize;
3174 size_t ZSTD_compressStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output, ZSTD_inBuffer* input)
3176 size_t sizeRead = input->size - input->pos;
3177 size_t sizeWritten = output->size - output->pos;
3178 size_t const result = ZSTD_compressStream_generic(zcs,
3179 (char*)(output->dst) + output->pos, &sizeWritten,
3180 (const char*)(input->src) + input->pos, &sizeRead, zsf_gather);
3181 input->pos += sizeRead;
3182 output->pos += sizeWritten;
3187 /*====== Finalize ======*/
3189 /*! ZSTD_flushStream() :
3190 * @return : amount of data remaining to flush */
3191 size_t ZSTD_flushStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output)
3194 size_t sizeWritten = output->size - output->pos;
3195 size_t const result = ZSTD_compressStream_generic(zcs,
3196 (char*)(output->dst) + output->pos, &sizeWritten,
3197 &srcSize, &srcSize, /* use a valid src address instead of NULL */
3199 output->pos += sizeWritten;
3200 if (ZSTD_isError(result)) return result;
3201 return zcs->outBuffContentSize - zcs->outBuffFlushedSize; /* remaining to flush */
3205 size_t ZSTD_endStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output)
3207 BYTE* const ostart = (BYTE*)(output->dst) + output->pos;
3208 BYTE* const oend = (BYTE*)(output->dst) + output->size;
3211 if ((zcs->pledgedSrcSize) && (zcs->inputProcessed != zcs->pledgedSrcSize))
3212 return ERROR(srcSize_wrong); /* pledgedSrcSize not respected */
3214 if (zcs->stage != zcss_final) {
3215 /* flush whatever remains */
3217 size_t sizeWritten = output->size - output->pos;
3218 size_t const notEnded = ZSTD_compressStream_generic(zcs, ostart, &sizeWritten, &srcSize, &srcSize, zsf_end); /* use a valid src address instead of NULL */
3219 size_t const remainingToFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3221 if (remainingToFlush) {
3222 output->pos += sizeWritten;
3223 return remainingToFlush + ZSTD_BLOCKHEADERSIZE /* final empty block */ + (zcs->checksum * 4);
3225 /* create epilogue */
3226 zcs->stage = zcss_final;
3227 zcs->outBuffContentSize = !notEnded ? 0 :
3228 ZSTD_compressEnd(zcs->cctx, zcs->outBuff, zcs->outBuffSize, NULL, 0); /* write epilogue, including final empty block, into outBuff */
3231 /* flush epilogue */
3232 { size_t const toFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3233 size_t const flushed = ZSTD_limitCopy(op, oend-op, zcs->outBuff + zcs->outBuffFlushedSize, toFlush);
3235 zcs->outBuffFlushedSize += flushed;
3236 output->pos += op-ostart;
3237 if (toFlush==flushed) zcs->stage = zcss_init; /* end reached */
3238 return toFlush - flushed;
3244 /*-===== Pre-defined compression levels =====-*/
3246 #define ZSTD_DEFAULT_CLEVEL 1
3247 #define ZSTD_MAX_CLEVEL 22
3248 int ZSTD_maxCLevel(void) { return ZSTD_MAX_CLEVEL; }
3250 static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEVEL+1] = {
3252 /* W, C, H, S, L, TL, strat */
3253 { 18, 12, 12, 1, 7, 16, ZSTD_fast }, /* level 0 - never used */
3254 { 19, 13, 14, 1, 7, 16, ZSTD_fast }, /* level 1 */
3255 { 19, 15, 16, 1, 6, 16, ZSTD_fast }, /* level 2 */
3256 { 20, 16, 17, 1, 5, 16, ZSTD_dfast }, /* level 3.*/
3257 { 20, 18, 18, 1, 5, 16, ZSTD_dfast }, /* level 4.*/
3258 { 20, 15, 18, 3, 5, 16, ZSTD_greedy }, /* level 5 */
3259 { 21, 16, 19, 2, 5, 16, ZSTD_lazy }, /* level 6 */
3260 { 21, 17, 20, 3, 5, 16, ZSTD_lazy }, /* level 7 */
3261 { 21, 18, 20, 3, 5, 16, ZSTD_lazy2 }, /* level 8 */
3262 { 21, 20, 20, 3, 5, 16, ZSTD_lazy2 }, /* level 9 */
3263 { 21, 19, 21, 4, 5, 16, ZSTD_lazy2 }, /* level 10 */
3264 { 22, 20, 22, 4, 5, 16, ZSTD_lazy2 }, /* level 11 */
3265 { 22, 20, 22, 5, 5, 16, ZSTD_lazy2 }, /* level 12 */
3266 { 22, 21, 22, 5, 5, 16, ZSTD_lazy2 }, /* level 13 */
3267 { 22, 21, 22, 6, 5, 16, ZSTD_lazy2 }, /* level 14 */
3268 { 22, 21, 21, 5, 5, 16, ZSTD_btlazy2 }, /* level 15 */
3269 { 23, 22, 22, 5, 5, 16, ZSTD_btlazy2 }, /* level 16 */
3270 { 23, 21, 22, 4, 5, 24, ZSTD_btopt }, /* level 17 */
3271 { 23, 23, 22, 6, 5, 32, ZSTD_btopt }, /* level 18 */
3272 { 23, 23, 22, 6, 3, 48, ZSTD_btopt }, /* level 19 */
3273 { 25, 25, 23, 7, 3, 64, ZSTD_btopt2 }, /* level 20 */
3274 { 26, 26, 23, 7, 3,256, ZSTD_btopt2 }, /* level 21 */
3275 { 27, 27, 25, 9, 3,512, ZSTD_btopt2 }, /* level 22 */
3277 { /* for srcSize <= 256 KB */
3278 /* W, C, H, S, L, T, strat */
3279 { 0, 0, 0, 0, 0, 0, ZSTD_fast }, /* level 0 - not used */
3280 { 18, 13, 14, 1, 6, 8, ZSTD_fast }, /* level 1 */
3281 { 18, 14, 13, 1, 5, 8, ZSTD_dfast }, /* level 2 */
3282 { 18, 16, 15, 1, 5, 8, ZSTD_dfast }, /* level 3 */
3283 { 18, 15, 17, 1, 5, 8, ZSTD_greedy }, /* level 4.*/
3284 { 18, 16, 17, 4, 5, 8, ZSTD_greedy }, /* level 5.*/
3285 { 18, 16, 17, 3, 5, 8, ZSTD_lazy }, /* level 6.*/
3286 { 18, 17, 17, 4, 4, 8, ZSTD_lazy }, /* level 7 */
3287 { 18, 17, 17, 4, 4, 8, ZSTD_lazy2 }, /* level 8 */
3288 { 18, 17, 17, 5, 4, 8, ZSTD_lazy2 }, /* level 9 */
3289 { 18, 17, 17, 6, 4, 8, ZSTD_lazy2 }, /* level 10 */
3290 { 18, 18, 17, 6, 4, 8, ZSTD_lazy2 }, /* level 11.*/
3291 { 18, 18, 17, 7, 4, 8, ZSTD_lazy2 }, /* level 12.*/
3292 { 18, 19, 17, 6, 4, 8, ZSTD_btlazy2 }, /* level 13 */
3293 { 18, 18, 18, 4, 4, 16, ZSTD_btopt }, /* level 14.*/
3294 { 18, 18, 18, 4, 3, 16, ZSTD_btopt }, /* level 15.*/
3295 { 18, 19, 18, 6, 3, 32, ZSTD_btopt }, /* level 16.*/
3296 { 18, 19, 18, 8, 3, 64, ZSTD_btopt }, /* level 17.*/
3297 { 18, 19, 18, 9, 3,128, ZSTD_btopt }, /* level 18.*/
3298 { 18, 19, 18, 10, 3,256, ZSTD_btopt }, /* level 19.*/
3299 { 18, 19, 18, 11, 3,512, ZSTD_btopt2 }, /* level 20.*/
3300 { 18, 19, 18, 12, 3,512, ZSTD_btopt2 }, /* level 21.*/
3301 { 18, 19, 18, 13, 3,512, ZSTD_btopt2 }, /* level 22.*/
3303 { /* for srcSize <= 128 KB */
3304 /* W, C, H, S, L, T, strat */
3305 { 17, 12, 12, 1, 7, 8, ZSTD_fast }, /* level 0 - not used */
3306 { 17, 12, 13, 1, 6, 8, ZSTD_fast }, /* level 1 */
3307 { 17, 13, 16, 1, 5, 8, ZSTD_fast }, /* level 2 */
3308 { 17, 16, 16, 2, 5, 8, ZSTD_dfast }, /* level 3 */
3309 { 17, 13, 15, 3, 4, 8, ZSTD_greedy }, /* level 4 */
3310 { 17, 15, 17, 4, 4, 8, ZSTD_greedy }, /* level 5 */
3311 { 17, 16, 17, 3, 4, 8, ZSTD_lazy }, /* level 6 */
3312 { 17, 15, 17, 4, 4, 8, ZSTD_lazy2 }, /* level 7 */
3313 { 17, 17, 17, 4, 4, 8, ZSTD_lazy2 }, /* level 8 */
3314 { 17, 17, 17, 5, 4, 8, ZSTD_lazy2 }, /* level 9 */
3315 { 17, 17, 17, 6, 4, 8, ZSTD_lazy2 }, /* level 10 */
3316 { 17, 17, 17, 7, 4, 8, ZSTD_lazy2 }, /* level 11 */
3317 { 17, 17, 17, 8, 4, 8, ZSTD_lazy2 }, /* level 12 */
3318 { 17, 18, 17, 6, 4, 8, ZSTD_btlazy2 }, /* level 13.*/
3319 { 17, 17, 17, 7, 3, 8, ZSTD_btopt }, /* level 14.*/
3320 { 17, 17, 17, 7, 3, 16, ZSTD_btopt }, /* level 15.*/
3321 { 17, 18, 17, 7, 3, 32, ZSTD_btopt }, /* level 16.*/
3322 { 17, 18, 17, 7, 3, 64, ZSTD_btopt }, /* level 17.*/
3323 { 17, 18, 17, 7, 3,256, ZSTD_btopt }, /* level 18.*/
3324 { 17, 18, 17, 8, 3,256, ZSTD_btopt }, /* level 19.*/
3325 { 17, 18, 17, 9, 3,256, ZSTD_btopt2 }, /* level 20.*/
3326 { 17, 18, 17, 10, 3,256, ZSTD_btopt2 }, /* level 21.*/
3327 { 17, 18, 17, 11, 3,512, ZSTD_btopt2 }, /* level 22.*/
3329 { /* for srcSize <= 16 KB */
3330 /* W, C, H, S, L, T, strat */
3331 { 14, 12, 12, 1, 7, 6, ZSTD_fast }, /* level 0 - not used */
3332 { 14, 14, 14, 1, 6, 6, ZSTD_fast }, /* level 1 */
3333 { 14, 14, 14, 1, 4, 6, ZSTD_fast }, /* level 2 */
3334 { 14, 14, 14, 1, 4, 6, ZSTD_dfast }, /* level 3.*/
3335 { 14, 14, 14, 4, 4, 6, ZSTD_greedy }, /* level 4.*/
3336 { 14, 14, 14, 3, 4, 6, ZSTD_lazy }, /* level 5.*/
3337 { 14, 14, 14, 4, 4, 6, ZSTD_lazy2 }, /* level 6 */
3338 { 14, 14, 14, 5, 4, 6, ZSTD_lazy2 }, /* level 7 */
3339 { 14, 14, 14, 6, 4, 6, ZSTD_lazy2 }, /* level 8.*/
3340 { 14, 15, 14, 6, 4, 6, ZSTD_btlazy2 }, /* level 9.*/
3341 { 14, 15, 14, 3, 3, 6, ZSTD_btopt }, /* level 10.*/
3342 { 14, 15, 14, 6, 3, 8, ZSTD_btopt }, /* level 11.*/
3343 { 14, 15, 14, 6, 3, 16, ZSTD_btopt }, /* level 12.*/
3344 { 14, 15, 14, 6, 3, 24, ZSTD_btopt }, /* level 13.*/
3345 { 14, 15, 15, 6, 3, 48, ZSTD_btopt }, /* level 14.*/
3346 { 14, 15, 15, 6, 3, 64, ZSTD_btopt }, /* level 15.*/
3347 { 14, 15, 15, 6, 3, 96, ZSTD_btopt }, /* level 16.*/
3348 { 14, 15, 15, 6, 3,128, ZSTD_btopt }, /* level 17.*/
3349 { 14, 15, 15, 6, 3,256, ZSTD_btopt }, /* level 18.*/
3350 { 14, 15, 15, 7, 3,256, ZSTD_btopt }, /* level 19.*/
3351 { 14, 15, 15, 8, 3,256, ZSTD_btopt2 }, /* level 20.*/
3352 { 14, 15, 15, 9, 3,256, ZSTD_btopt2 }, /* level 21.*/
3353 { 14, 15, 15, 10, 3,256, ZSTD_btopt2 }, /* level 22.*/
3357 /*! ZSTD_getCParams() :
3358 * @return ZSTD_compressionParameters structure for a selected compression level, `srcSize` and `dictSize`.
3359 * Size values are optional, provide 0 if not known or unused */
3360 ZSTD_compressionParameters ZSTD_getCParams(int compressionLevel, unsigned long long srcSize, size_t dictSize)
3362 ZSTD_compressionParameters cp;
3363 size_t const addedSize = srcSize ? 0 : 500;
3364 U64 const rSize = srcSize+dictSize ? srcSize+dictSize+addedSize : (U64)-1;
3365 U32 const tableID = (rSize <= 256 KB) + (rSize <= 128 KB) + (rSize <= 16 KB); /* intentional underflow for srcSizeHint == 0 */
3366 if (compressionLevel <= 0) compressionLevel = ZSTD_DEFAULT_CLEVEL; /* 0 == default; no negative compressionLevel yet */
3367 if (compressionLevel > ZSTD_MAX_CLEVEL) compressionLevel = ZSTD_MAX_CLEVEL;
3368 cp = ZSTD_defaultCParameters[tableID][compressionLevel];
3369 if (MEM_32bits()) { /* auto-correction, for 32-bits mode */
3370 if (cp.windowLog > ZSTD_WINDOWLOG_MAX) cp.windowLog = ZSTD_WINDOWLOG_MAX;
3371 if (cp.chainLog > ZSTD_CHAINLOG_MAX) cp.chainLog = ZSTD_CHAINLOG_MAX;
3372 if (cp.hashLog > ZSTD_HASHLOG_MAX) cp.hashLog = ZSTD_HASHLOG_MAX;
3374 cp = ZSTD_adjustCParams(cp, srcSize, dictSize);
3378 /*! ZSTD_getParams() :
3379 * same as ZSTD_getCParams(), but @return a `ZSTD_parameters` object (instead of `ZSTD_compressionParameters`).
3380 * All fields of `ZSTD_frameParameters` are set to default (0) */
3381 ZSTD_parameters ZSTD_getParams(int compressionLevel, unsigned long long srcSize, size_t dictSize) {
3382 ZSTD_parameters params;
3383 ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, srcSize, dictSize);
3384 memset(¶ms, 0, sizeof(params));
3385 params.cParams = cParams;