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 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=1)
29 # define assert(condition) ((void)0)
32 #define ZSTD_STATIC_ASSERT(c) { enum { ZSTD_static_assert = 1/(int)(!!(c)) }; }
34 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=2)
36 static unsigned g_debugLevel = ZSTD_DEBUG;
37 # define DEBUGLOG(l, ...) if (l<=g_debugLevel) { fprintf(stderr, __FILE__ ": "); fprintf(stderr, __VA_ARGS__); fprintf(stderr, " \n"); }
39 # define DEBUGLOG(l, ...) {} /* disabled */
43 /*-*************************************
45 ***************************************/
46 static const U32 g_searchStrength = 8; /* control skip over incompressible data */
47 #define HASH_READ_SIZE 8
48 typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;
50 /* entropy tables always have same size */
51 static size_t const hufCTable_size = HUF_CTABLE_SIZE(255);
52 static size_t const litlengthCTable_size = FSE_CTABLE_SIZE(LLFSELog, MaxLL);
53 static size_t const offcodeCTable_size = FSE_CTABLE_SIZE(OffFSELog, MaxOff);
54 static size_t const matchlengthCTable_size = FSE_CTABLE_SIZE(MLFSELog, MaxML);
55 static size_t const entropyScratchSpace_size = HUF_WORKSPACE_SIZE;
58 /*-*************************************
60 ***************************************/
61 size_t ZSTD_compressBound(size_t srcSize) {
62 size_t const lowLimit = 256 KB;
63 size_t const margin = (srcSize < lowLimit) ? (lowLimit-srcSize) >> 12 : 0; /* from 64 to 0 */
64 return srcSize + (srcSize >> 8) + margin;
68 /*-*************************************
70 ***************************************/
71 static void ZSTD_resetSeqStore(seqStore_t* ssPtr)
73 ssPtr->lit = ssPtr->litStart;
74 ssPtr->sequences = ssPtr->sequencesStart;
75 ssPtr->longLengthID = 0;
79 /*-*************************************
80 * Context memory management
81 ***************************************/
83 const BYTE* nextSrc; /* next block here to continue on current prefix */
84 const BYTE* base; /* All regular indexes relative to this position */
85 const BYTE* dictBase; /* extDict indexes relative to this position */
86 U32 dictLimit; /* below that point, need extDict */
87 U32 lowLimit; /* below that point, no more data */
88 U32 nextToUpdate; /* index from which to continue dictionary update */
89 U32 nextToUpdate3; /* index from which to continue dictionary update */
90 U32 hashLog3; /* dispatch table : larger == faster, more memory */
91 U32 loadedDictEnd; /* index of end of dictionary */
92 U32 forceWindow; /* force back-references to respect limit of 1<<wLog, even for dictionary */
93 U32 forceRawDict; /* Force loading dictionary in "content-only" mode (no header analysis) */
94 ZSTD_compressionStage_e stage;
95 U32 rep[ZSTD_REP_NUM];
96 U32 repToConfirm[ZSTD_REP_NUM];
98 ZSTD_parameters params;
100 size_t workSpaceSize;
102 U64 frameContentSize;
104 XXH64_state_t xxhState;
105 ZSTD_customMem customMem;
107 seqStore_t seqStore; /* sequences storage ptrs */
111 HUF_repeat hufCTable_repeatMode;
113 U32 fseCTables_ready;
114 FSE_CTable* offcodeCTable;
115 FSE_CTable* matchlengthCTable;
116 FSE_CTable* litlengthCTable;
117 unsigned* entropyScratchSpace;
120 ZSTD_CCtx* ZSTD_createCCtx(void)
122 return ZSTD_createCCtx_advanced(defaultCustomMem);
125 ZSTD_CCtx* ZSTD_createCCtx_advanced(ZSTD_customMem customMem)
129 if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;
130 if (!customMem.customAlloc || !customMem.customFree) return NULL;
132 cctx = (ZSTD_CCtx*) ZSTD_malloc(sizeof(ZSTD_CCtx), customMem);
133 if (!cctx) return NULL;
134 memset(cctx, 0, sizeof(ZSTD_CCtx));
135 cctx->customMem = customMem;
139 size_t ZSTD_freeCCtx(ZSTD_CCtx* cctx)
141 if (cctx==NULL) return 0; /* support free on NULL */
142 ZSTD_free(cctx->workSpace, cctx->customMem);
143 ZSTD_free(cctx, cctx->customMem);
144 return 0; /* reserved as a potential error code in the future */
147 size_t ZSTD_sizeof_CCtx(const ZSTD_CCtx* cctx)
149 if (cctx==NULL) return 0; /* support sizeof on NULL */
150 return sizeof(*cctx) + cctx->workSpaceSize;
153 size_t ZSTD_setCCtxParameter(ZSTD_CCtx* cctx, ZSTD_CCtxParameter param, unsigned value)
157 case ZSTD_p_forceWindow : cctx->forceWindow = value>0; cctx->loadedDictEnd = 0; return 0;
158 case ZSTD_p_forceRawDict : cctx->forceRawDict = value>0; return 0;
159 default: return ERROR(parameter_unknown);
163 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx) /* hidden interface */
165 return &(ctx->seqStore);
168 static ZSTD_parameters ZSTD_getParamsFromCCtx(const ZSTD_CCtx* cctx)
174 /** ZSTD_checkParams() :
175 ensure param values remain within authorized range.
176 @return : 0, or an error code if one value is beyond authorized range */
177 size_t ZSTD_checkCParams(ZSTD_compressionParameters cParams)
179 # define CLAMPCHECK(val,min,max) { if ((val<min) | (val>max)) return ERROR(compressionParameter_unsupported); }
180 CLAMPCHECK(cParams.windowLog, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);
181 CLAMPCHECK(cParams.chainLog, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX);
182 CLAMPCHECK(cParams.hashLog, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX);
183 CLAMPCHECK(cParams.searchLog, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX);
184 CLAMPCHECK(cParams.searchLength, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX);
185 CLAMPCHECK(cParams.targetLength, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX);
186 if ((U32)(cParams.strategy) > (U32)ZSTD_btopt2) return ERROR(compressionParameter_unsupported);
191 /** ZSTD_cycleLog() :
192 * condition for correct operation : hashLog > 1 */
193 static U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat)
195 U32 const btScale = ((U32)strat >= (U32)ZSTD_btlazy2);
196 return hashLog - btScale;
199 /** ZSTD_adjustCParams() :
200 optimize `cPar` for a given input (`srcSize` and `dictSize`).
201 mostly downsizing to reduce memory consumption and initialization.
202 Both `srcSize` and `dictSize` are optional (use 0 if unknown),
203 but if both are 0, no optimization can be done.
204 Note : cPar is considered validated at this stage. Use ZSTD_checkParams() to ensure that. */
205 ZSTD_compressionParameters ZSTD_adjustCParams(ZSTD_compressionParameters cPar, unsigned long long srcSize, size_t dictSize)
207 if (srcSize+dictSize == 0) return cPar; /* no size information available : no adjustment */
209 /* resize params, to use less memory when necessary */
210 { U32 const minSrcSize = (srcSize==0) ? 500 : 0;
211 U64 const rSize = srcSize + dictSize + minSrcSize;
212 if (rSize < ((U64)1<<ZSTD_WINDOWLOG_MAX)) {
213 U32 const srcLog = MAX(ZSTD_HASHLOG_MIN, ZSTD_highbit32((U32)(rSize)-1) + 1);
214 if (cPar.windowLog > srcLog) cPar.windowLog = srcLog;
216 if (cPar.hashLog > cPar.windowLog) cPar.hashLog = cPar.windowLog;
217 { U32 const cycleLog = ZSTD_cycleLog(cPar.chainLog, cPar.strategy);
218 if (cycleLog > cPar.windowLog) cPar.chainLog -= (cycleLog - cPar.windowLog);
221 if (cPar.windowLog < ZSTD_WINDOWLOG_ABSOLUTEMIN) cPar.windowLog = ZSTD_WINDOWLOG_ABSOLUTEMIN; /* required for frame header */
227 size_t ZSTD_estimateCCtxSize(ZSTD_compressionParameters cParams)
229 size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << cParams.windowLog);
230 U32 const divider = (cParams.searchLength==3) ? 3 : 4;
231 size_t const maxNbSeq = blockSize / divider;
232 size_t const tokenSpace = blockSize + 11*maxNbSeq;
234 size_t const chainSize = (cParams.strategy == ZSTD_fast) ? 0 : (1 << cParams.chainLog);
235 size_t const hSize = ((size_t)1) << cParams.hashLog;
236 U32 const hashLog3 = (cParams.searchLength>3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, cParams.windowLog);
237 size_t const h3Size = ((size_t)1) << hashLog3;
238 size_t const entropySpace = hufCTable_size + litlengthCTable_size
239 + offcodeCTable_size + matchlengthCTable_size
240 + entropyScratchSpace_size;
241 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
243 size_t const optSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits))*sizeof(U32)
244 + (ZSTD_OPT_NUM+1)*(sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t));
245 size_t const neededSpace = entropySpace + tableSpace + tokenSpace
246 + (((cParams.strategy == ZSTD_btopt) || (cParams.strategy == ZSTD_btopt2)) ? optSpace : 0);
248 return sizeof(ZSTD_CCtx) + neededSpace;
252 static U32 ZSTD_equivalentParams(ZSTD_parameters param1, ZSTD_parameters param2)
254 return (param1.cParams.hashLog == param2.cParams.hashLog)
255 & (param1.cParams.chainLog == param2.cParams.chainLog)
256 & (param1.cParams.strategy == param2.cParams.strategy)
257 & ((param1.cParams.searchLength==3) == (param2.cParams.searchLength==3));
260 /*! ZSTD_continueCCtx() :
261 reuse CCtx without reset (note : requires no dictionary) */
262 static size_t ZSTD_continueCCtx(ZSTD_CCtx* cctx, ZSTD_parameters params, U64 frameContentSize)
264 U32 const end = (U32)(cctx->nextSrc - cctx->base);
265 cctx->params = params;
266 cctx->frameContentSize = frameContentSize;
267 cctx->consumedSrcSize = 0;
268 cctx->lowLimit = end;
269 cctx->dictLimit = end;
270 cctx->nextToUpdate = end+1;
271 cctx->stage = ZSTDcs_init;
273 cctx->loadedDictEnd = 0;
274 { int i; for (i=0; i<ZSTD_REP_NUM; i++) cctx->rep[i] = repStartValue[i]; }
275 cctx->seqStore.litLengthSum = 0; /* force reset of btopt stats */
276 XXH64_reset(&cctx->xxhState, 0);
280 typedef enum { ZSTDcrp_continue, ZSTDcrp_noMemset, ZSTDcrp_fullReset } ZSTD_compResetPolicy_e;
282 /*! ZSTD_resetCCtx_internal() :
283 note : `params` must be validated */
284 static size_t ZSTD_resetCCtx_internal (ZSTD_CCtx* zc,
285 ZSTD_parameters params, U64 frameContentSize,
286 ZSTD_compResetPolicy_e const crp)
288 if (crp == ZSTDcrp_continue)
289 if (ZSTD_equivalentParams(params, zc->params)) {
290 zc->fseCTables_ready = 0;
291 zc->hufCTable_repeatMode = HUF_repeat_none;
292 return ZSTD_continueCCtx(zc, params, frameContentSize);
295 { size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << params.cParams.windowLog);
296 U32 const divider = (params.cParams.searchLength==3) ? 3 : 4;
297 size_t const maxNbSeq = blockSize / divider;
298 size_t const tokenSpace = blockSize + 11*maxNbSeq;
299 size_t const chainSize = (params.cParams.strategy == ZSTD_fast) ? 0 : (1 << params.cParams.chainLog);
300 size_t const hSize = ((size_t)1) << params.cParams.hashLog;
301 U32 const hashLog3 = (params.cParams.searchLength>3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, params.cParams.windowLog);
302 size_t const h3Size = ((size_t)1) << hashLog3;
303 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
306 /* Check if workSpace is large enough, alloc a new one if needed */
307 { size_t const entropySpace = hufCTable_size + litlengthCTable_size
308 + offcodeCTable_size + matchlengthCTable_size
309 + entropyScratchSpace_size;
310 size_t const optPotentialSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits)) * sizeof(U32)
311 + (ZSTD_OPT_NUM+1) * (sizeof(ZSTD_match_t)+sizeof(ZSTD_optimal_t));
312 size_t const optSpace = ((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) ? optPotentialSpace : 0;
313 size_t const neededSpace = entropySpace + optSpace + tableSpace + tokenSpace;
314 if (zc->workSpaceSize < neededSpace) {
315 zc->workSpaceSize = 0;
316 ZSTD_free(zc->workSpace, zc->customMem);
317 zc->workSpace = ZSTD_malloc(neededSpace, zc->customMem);
318 if (zc->workSpace == NULL) return ERROR(memory_allocation);
319 zc->workSpaceSize = neededSpace;
323 zc->hufCTable = (HUF_CElt*)ptr;
324 ptr = (char*)zc->hufCTable + hufCTable_size; /* note : HUF_CElt* is incomplete type, size is estimated via macro */
325 zc->offcodeCTable = (FSE_CTable*) ptr;
326 ptr = (char*)ptr + offcodeCTable_size;
327 zc->matchlengthCTable = (FSE_CTable*) ptr;
328 ptr = (char*)ptr + matchlengthCTable_size;
329 zc->litlengthCTable = (FSE_CTable*) ptr;
330 ptr = (char*)ptr + litlengthCTable_size;
331 assert(((size_t)ptr & 3) == 0); /* ensure correct alignment */
332 zc->entropyScratchSpace = (unsigned*) ptr;
337 zc->blockSize = blockSize;
338 zc->frameContentSize = frameContentSize;
339 zc->consumedSrcSize = 0;
341 XXH64_reset(&zc->xxhState, 0);
342 zc->stage = ZSTDcs_init;
344 zc->loadedDictEnd = 0;
345 zc->fseCTables_ready = 0;
346 zc->hufCTable_repeatMode = HUF_repeat_none;
347 zc->nextToUpdate = 1;
353 { int i; for (i=0; i<ZSTD_REP_NUM; i++) zc->rep[i] = repStartValue[i]; }
354 zc->hashLog3 = hashLog3;
355 zc->seqStore.litLengthSum = 0;
357 /* ensure entropy tables are close together at the beginning */
358 assert((void*)zc->hufCTable == zc->workSpace);
359 assert((char*)zc->offcodeCTable == (char*)zc->hufCTable + hufCTable_size);
360 assert((char*)zc->matchlengthCTable == (char*)zc->offcodeCTable + offcodeCTable_size);
361 assert((char*)zc->litlengthCTable == (char*)zc->matchlengthCTable + matchlengthCTable_size);
362 assert((char*)zc->entropyScratchSpace == (char*)zc->litlengthCTable + litlengthCTable_size);
363 ptr = (char*)zc->entropyScratchSpace + entropyScratchSpace_size;
365 /* opt parser space */
366 if ((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) {
367 assert(((size_t)ptr & 3) == 0); /* ensure ptr is properly aligned */
368 zc->seqStore.litFreq = (U32*)ptr;
369 zc->seqStore.litLengthFreq = zc->seqStore.litFreq + (1<<Litbits);
370 zc->seqStore.matchLengthFreq = zc->seqStore.litLengthFreq + (MaxLL+1);
371 zc->seqStore.offCodeFreq = zc->seqStore.matchLengthFreq + (MaxML+1);
372 ptr = zc->seqStore.offCodeFreq + (MaxOff+1);
373 zc->seqStore.matchTable = (ZSTD_match_t*)ptr;
374 ptr = zc->seqStore.matchTable + ZSTD_OPT_NUM+1;
375 zc->seqStore.priceTable = (ZSTD_optimal_t*)ptr;
376 ptr = zc->seqStore.priceTable + ZSTD_OPT_NUM+1;
380 if (crp!=ZSTDcrp_noMemset) memset(ptr, 0, tableSpace); /* reset tables only */
381 assert(((size_t)ptr & 3) == 0); /* ensure ptr is properly aligned */
382 zc->hashTable = (U32*)(ptr);
383 zc->chainTable = zc->hashTable + hSize;
384 zc->hashTable3 = zc->chainTable + chainSize;
385 ptr = zc->hashTable3 + h3Size;
387 /* sequences storage */
388 zc->seqStore.sequencesStart = (seqDef*)ptr;
389 ptr = zc->seqStore.sequencesStart + maxNbSeq;
390 zc->seqStore.llCode = (BYTE*) ptr;
391 zc->seqStore.mlCode = zc->seqStore.llCode + maxNbSeq;
392 zc->seqStore.ofCode = zc->seqStore.mlCode + maxNbSeq;
393 zc->seqStore.litStart = zc->seqStore.ofCode + maxNbSeq;
399 /* ZSTD_invalidateRepCodes() :
400 * ensures next compression will not use repcodes from previous block.
401 * Note : only works with regular variant;
402 * do not use with extDict variant ! */
403 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx) {
405 for (i=0; i<ZSTD_REP_NUM; i++) cctx->rep[i] = 0;
409 /*! ZSTD_copyCCtx_internal() :
410 * Duplicate an existing context `srcCCtx` into another one `dstCCtx`.
411 * Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()).
412 * pledgedSrcSize=0 means "empty" if fParams.contentSizeFlag=1
413 * @return : 0, or an error code */
414 size_t ZSTD_copyCCtx_internal(ZSTD_CCtx* dstCCtx, const ZSTD_CCtx* srcCCtx,
415 ZSTD_frameParameters fParams, unsigned long long pledgedSrcSize)
417 if (srcCCtx->stage!=ZSTDcs_init) return ERROR(stage_wrong);
419 memcpy(&dstCCtx->customMem, &srcCCtx->customMem, sizeof(ZSTD_customMem));
420 { ZSTD_parameters params = srcCCtx->params;
421 params.fParams = fParams;
422 DEBUGLOG(5, "ZSTD_resetCCtx_internal : dictIDFlag : %u \n", !fParams.noDictIDFlag);
423 ZSTD_resetCCtx_internal(dstCCtx, params, pledgedSrcSize, ZSTDcrp_noMemset);
427 { size_t const chainSize = (srcCCtx->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << srcCCtx->params.cParams.chainLog);
428 size_t const hSize = (size_t)1 << srcCCtx->params.cParams.hashLog;
429 size_t const h3Size = (size_t)1 << srcCCtx->hashLog3;
430 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
431 assert((U32*)dstCCtx->chainTable == (U32*)dstCCtx->hashTable + hSize); /* chainTable must follow hashTable */
432 assert((U32*)dstCCtx->hashTable3 == (U32*)dstCCtx->chainTable + chainSize);
433 memcpy(dstCCtx->hashTable, srcCCtx->hashTable, tableSpace); /* presumes all tables follow each other */
436 /* copy dictionary offsets */
437 dstCCtx->nextToUpdate = srcCCtx->nextToUpdate;
438 dstCCtx->nextToUpdate3= srcCCtx->nextToUpdate3;
439 dstCCtx->nextSrc = srcCCtx->nextSrc;
440 dstCCtx->base = srcCCtx->base;
441 dstCCtx->dictBase = srcCCtx->dictBase;
442 dstCCtx->dictLimit = srcCCtx->dictLimit;
443 dstCCtx->lowLimit = srcCCtx->lowLimit;
444 dstCCtx->loadedDictEnd= srcCCtx->loadedDictEnd;
445 dstCCtx->dictID = srcCCtx->dictID;
447 /* copy entropy tables */
448 dstCCtx->fseCTables_ready = srcCCtx->fseCTables_ready;
449 if (srcCCtx->fseCTables_ready) {
450 memcpy(dstCCtx->litlengthCTable, srcCCtx->litlengthCTable, litlengthCTable_size);
451 memcpy(dstCCtx->matchlengthCTable, srcCCtx->matchlengthCTable, matchlengthCTable_size);
452 memcpy(dstCCtx->offcodeCTable, srcCCtx->offcodeCTable, offcodeCTable_size);
454 dstCCtx->hufCTable_repeatMode = srcCCtx->hufCTable_repeatMode;
455 if (srcCCtx->hufCTable_repeatMode) {
456 memcpy(dstCCtx->hufCTable, srcCCtx->hufCTable, hufCTable_size);
462 /*! ZSTD_copyCCtx() :
463 * Duplicate an existing context `srcCCtx` into another one `dstCCtx`.
464 * Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()).
465 * pledgedSrcSize==0 means "unknown".
466 * @return : 0, or an error code */
467 size_t ZSTD_copyCCtx(ZSTD_CCtx* dstCCtx, const ZSTD_CCtx* srcCCtx, unsigned long long pledgedSrcSize)
469 ZSTD_frameParameters fParams = { 1 /*content*/, 0 /*checksum*/, 0 /*noDictID*/ };
470 fParams.contentSizeFlag = pledgedSrcSize>0;
472 return ZSTD_copyCCtx_internal(dstCCtx, srcCCtx, fParams, pledgedSrcSize);
476 /*! ZSTD_reduceTable() :
477 * reduce table indexes by `reducerValue` */
478 static void ZSTD_reduceTable (U32* const table, U32 const size, U32 const reducerValue)
481 for (u=0 ; u < size ; u++) {
482 if (table[u] < reducerValue) table[u] = 0;
483 else table[u] -= reducerValue;
487 /*! ZSTD_reduceIndex() :
488 * rescale all indexes to avoid future overflow (indexes are U32) */
489 static void ZSTD_reduceIndex (ZSTD_CCtx* zc, const U32 reducerValue)
491 { U32 const hSize = 1 << zc->params.cParams.hashLog;
492 ZSTD_reduceTable(zc->hashTable, hSize, reducerValue); }
494 { U32 const chainSize = (zc->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << zc->params.cParams.chainLog);
495 ZSTD_reduceTable(zc->chainTable, chainSize, reducerValue); }
497 { U32 const h3Size = (zc->hashLog3) ? 1 << zc->hashLog3 : 0;
498 ZSTD_reduceTable(zc->hashTable3, h3Size, reducerValue); }
502 /*-*******************************************************
503 * Block entropic compression
504 *********************************************************/
506 /* See doc/zstd_compression_format.md for detailed format description */
508 size_t ZSTD_noCompressBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
510 if (srcSize + ZSTD_blockHeaderSize > dstCapacity) return ERROR(dstSize_tooSmall);
511 memcpy((BYTE*)dst + ZSTD_blockHeaderSize, src, srcSize);
512 MEM_writeLE24(dst, (U32)(srcSize << 2) + (U32)bt_raw);
513 return ZSTD_blockHeaderSize+srcSize;
517 static size_t ZSTD_noCompressLiterals (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
519 BYTE* const ostart = (BYTE* const)dst;
520 U32 const flSize = 1 + (srcSize>31) + (srcSize>4095);
522 if (srcSize + flSize > dstCapacity) return ERROR(dstSize_tooSmall);
526 case 1: /* 2 - 1 - 5 */
527 ostart[0] = (BYTE)((U32)set_basic + (srcSize<<3));
529 case 2: /* 2 - 2 - 12 */
530 MEM_writeLE16(ostart, (U16)((U32)set_basic + (1<<2) + (srcSize<<4)));
532 default: /*note : should not be necessary : flSize is within {1,2,3} */
533 case 3: /* 2 - 2 - 20 */
534 MEM_writeLE32(ostart, (U32)((U32)set_basic + (3<<2) + (srcSize<<4)));
538 memcpy(ostart + flSize, src, srcSize);
539 return srcSize + flSize;
542 static size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
544 BYTE* const ostart = (BYTE* const)dst;
545 U32 const flSize = 1 + (srcSize>31) + (srcSize>4095);
547 (void)dstCapacity; /* dstCapacity already guaranteed to be >=4, hence large enough */
551 case 1: /* 2 - 1 - 5 */
552 ostart[0] = (BYTE)((U32)set_rle + (srcSize<<3));
554 case 2: /* 2 - 2 - 12 */
555 MEM_writeLE16(ostart, (U16)((U32)set_rle + (1<<2) + (srcSize<<4)));
557 default: /*note : should not be necessary : flSize is necessarily within {1,2,3} */
558 case 3: /* 2 - 2 - 20 */
559 MEM_writeLE32(ostart, (U32)((U32)set_rle + (3<<2) + (srcSize<<4)));
563 ostart[flSize] = *(const BYTE*)src;
568 static size_t ZSTD_minGain(size_t srcSize) { return (srcSize >> 6) + 2; }
570 static size_t ZSTD_compressLiterals (ZSTD_CCtx* zc,
571 void* dst, size_t dstCapacity,
572 const void* src, size_t srcSize)
574 size_t const minGain = ZSTD_minGain(srcSize);
575 size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB);
576 BYTE* const ostart = (BYTE*)dst;
577 U32 singleStream = srcSize < 256;
578 symbolEncodingType_e hType = set_compressed;
582 /* small ? don't even attempt compression (speed opt) */
583 # define LITERAL_NOENTROPY 63
584 { size_t const minLitSize = zc->hufCTable_repeatMode == HUF_repeat_valid ? 6 : LITERAL_NOENTROPY;
585 if (srcSize <= minLitSize) return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
588 if (dstCapacity < lhSize+1) return ERROR(dstSize_tooSmall); /* not enough space for compression */
589 { HUF_repeat repeat = zc->hufCTable_repeatMode;
590 int const preferRepeat = zc->params.cParams.strategy < ZSTD_lazy ? srcSize <= 1024 : 0;
591 if (repeat == HUF_repeat_valid && lhSize == 3) singleStream = 1;
592 cLitSize = singleStream ? HUF_compress1X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11,
593 zc->entropyScratchSpace, entropyScratchSpace_size, zc->hufCTable, &repeat, preferRepeat)
594 : HUF_compress4X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11,
595 zc->entropyScratchSpace, entropyScratchSpace_size, zc->hufCTable, &repeat, preferRepeat);
596 if (repeat != HUF_repeat_none) { hType = set_repeat; } /* reused the existing table */
597 else { zc->hufCTable_repeatMode = HUF_repeat_check; } /* now have a table to reuse */
600 if ((cLitSize==0) | (cLitSize >= srcSize - minGain)) {
601 zc->hufCTable_repeatMode = HUF_repeat_none;
602 return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
605 zc->hufCTable_repeatMode = HUF_repeat_none;
606 return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize);
612 case 3: /* 2 - 2 - 10 - 10 */
613 { U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<14);
614 MEM_writeLE24(ostart, lhc);
617 case 4: /* 2 - 2 - 14 - 14 */
618 { U32 const lhc = hType + (2 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<18);
619 MEM_writeLE32(ostart, lhc);
622 default: /* should not be necessary, lhSize is only {3,4,5} */
623 case 5: /* 2 - 2 - 18 - 18 */
624 { U32 const lhc = hType + (3 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<22);
625 MEM_writeLE32(ostart, lhc);
626 ostart[4] = (BYTE)(cLitSize >> 10);
630 return lhSize+cLitSize;
633 static const BYTE LL_Code[64] = { 0, 1, 2, 3, 4, 5, 6, 7,
634 8, 9, 10, 11, 12, 13, 14, 15,
635 16, 16, 17, 17, 18, 18, 19, 19,
636 20, 20, 20, 20, 21, 21, 21, 21,
637 22, 22, 22, 22, 22, 22, 22, 22,
638 23, 23, 23, 23, 23, 23, 23, 23,
639 24, 24, 24, 24, 24, 24, 24, 24,
640 24, 24, 24, 24, 24, 24, 24, 24 };
642 static const BYTE ML_Code[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
643 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
644 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
645 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
646 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
647 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
648 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
649 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
652 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr)
654 BYTE const LL_deltaCode = 19;
655 BYTE const ML_deltaCode = 36;
656 const seqDef* const sequences = seqStorePtr->sequencesStart;
657 BYTE* const llCodeTable = seqStorePtr->llCode;
658 BYTE* const ofCodeTable = seqStorePtr->ofCode;
659 BYTE* const mlCodeTable = seqStorePtr->mlCode;
660 U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
662 for (u=0; u<nbSeq; u++) {
663 U32 const llv = sequences[u].litLength;
664 U32 const mlv = sequences[u].matchLength;
665 llCodeTable[u] = (llv> 63) ? (BYTE)ZSTD_highbit32(llv) + LL_deltaCode : LL_Code[llv];
666 ofCodeTable[u] = (BYTE)ZSTD_highbit32(sequences[u].offset);
667 mlCodeTable[u] = (mlv>127) ? (BYTE)ZSTD_highbit32(mlv) + ML_deltaCode : ML_Code[mlv];
669 if (seqStorePtr->longLengthID==1)
670 llCodeTable[seqStorePtr->longLengthPos] = MaxLL;
671 if (seqStorePtr->longLengthID==2)
672 mlCodeTable[seqStorePtr->longLengthPos] = MaxML;
675 MEM_STATIC size_t ZSTD_compressSequences (ZSTD_CCtx* zc,
676 void* dst, size_t dstCapacity,
679 const int longOffsets = zc->params.cParams.windowLog > STREAM_ACCUMULATOR_MIN;
680 const seqStore_t* seqStorePtr = &(zc->seqStore);
683 FSE_CTable* CTable_LitLength = zc->litlengthCTable;
684 FSE_CTable* CTable_OffsetBits = zc->offcodeCTable;
685 FSE_CTable* CTable_MatchLength = zc->matchlengthCTable;
686 U32 LLtype, Offtype, MLtype; /* compressed, raw or rle */
687 const seqDef* const sequences = seqStorePtr->sequencesStart;
688 const BYTE* const ofCodeTable = seqStorePtr->ofCode;
689 const BYTE* const llCodeTable = seqStorePtr->llCode;
690 const BYTE* const mlCodeTable = seqStorePtr->mlCode;
691 BYTE* const ostart = (BYTE*)dst;
692 BYTE* const oend = ostart + dstCapacity;
694 size_t const nbSeq = seqStorePtr->sequences - seqStorePtr->sequencesStart;
696 BYTE scratchBuffer[1<<MAX(MLFSELog,LLFSELog)];
698 /* Compress literals */
699 { const BYTE* const literals = seqStorePtr->litStart;
700 size_t const litSize = seqStorePtr->lit - literals;
701 size_t const cSize = ZSTD_compressLiterals(zc, op, dstCapacity, literals, litSize);
702 if (ZSTD_isError(cSize)) return cSize;
706 /* Sequences Header */
707 if ((oend-op) < 3 /*max nbSeq Size*/ + 1 /*seqHead */) return ERROR(dstSize_tooSmall);
708 if (nbSeq < 0x7F) *op++ = (BYTE)nbSeq;
709 else if (nbSeq < LONGNBSEQ) op[0] = (BYTE)((nbSeq>>8) + 0x80), op[1] = (BYTE)nbSeq, op+=2;
710 else op[0]=0xFF, MEM_writeLE16(op+1, (U16)(nbSeq - LONGNBSEQ)), op+=3;
711 if (nbSeq==0) goto _check_compressibility;
713 /* seqHead : flags for FSE encoding type */
716 #define MIN_SEQ_FOR_DYNAMIC_FSE 64
717 #define MAX_SEQ_FOR_STATIC_FSE 1000
719 /* convert length/distances into codes */
720 ZSTD_seqToCodes(seqStorePtr);
722 /* CTable for Literal Lengths */
724 size_t const mostFrequent = FSE_countFast_wksp(count, &max, llCodeTable, nbSeq, zc->entropyScratchSpace);
725 if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
726 *op++ = llCodeTable[0];
727 FSE_buildCTable_rle(CTable_LitLength, (BYTE)max);
729 } else if ((zc->fseCTables_ready) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
731 } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (LL_defaultNormLog-1)))) {
732 FSE_buildCTable_wksp(CTable_LitLength, LL_defaultNorm, MaxLL, LL_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
735 size_t nbSeq_1 = nbSeq;
736 const U32 tableLog = FSE_optimalTableLog(LLFSELog, nbSeq, max);
737 if (count[llCodeTable[nbSeq-1]]>1) { count[llCodeTable[nbSeq-1]]--; nbSeq_1--; }
738 FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
739 { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */
740 if (FSE_isError(NCountSize)) return NCountSize;
742 FSE_buildCTable_wksp(CTable_LitLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
743 LLtype = set_compressed;
746 /* CTable for Offsets */
748 size_t const mostFrequent = FSE_countFast_wksp(count, &max, ofCodeTable, nbSeq, zc->entropyScratchSpace);
749 if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
750 *op++ = ofCodeTable[0];
751 FSE_buildCTable_rle(CTable_OffsetBits, (BYTE)max);
753 } else if ((zc->fseCTables_ready) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
754 Offtype = set_repeat;
755 } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (OF_defaultNormLog-1)))) {
756 FSE_buildCTable_wksp(CTable_OffsetBits, OF_defaultNorm, MaxOff, OF_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
759 size_t nbSeq_1 = nbSeq;
760 const U32 tableLog = FSE_optimalTableLog(OffFSELog, nbSeq, max);
761 if (count[ofCodeTable[nbSeq-1]]>1) { count[ofCodeTable[nbSeq-1]]--; nbSeq_1--; }
762 FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
763 { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */
764 if (FSE_isError(NCountSize)) return NCountSize;
766 FSE_buildCTable_wksp(CTable_OffsetBits, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
767 Offtype = set_compressed;
770 /* CTable for MatchLengths */
772 size_t const mostFrequent = FSE_countFast_wksp(count, &max, mlCodeTable, nbSeq, zc->entropyScratchSpace);
773 if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
774 *op++ = *mlCodeTable;
775 FSE_buildCTable_rle(CTable_MatchLength, (BYTE)max);
777 } else if ((zc->fseCTables_ready) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
779 } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (ML_defaultNormLog-1)))) {
780 FSE_buildCTable_wksp(CTable_MatchLength, ML_defaultNorm, MaxML, ML_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
783 size_t nbSeq_1 = nbSeq;
784 const U32 tableLog = FSE_optimalTableLog(MLFSELog, nbSeq, max);
785 if (count[mlCodeTable[nbSeq-1]]>1) { count[mlCodeTable[nbSeq-1]]--; nbSeq_1--; }
786 FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
787 { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */
788 if (FSE_isError(NCountSize)) return NCountSize;
790 FSE_buildCTable_wksp(CTable_MatchLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
791 MLtype = set_compressed;
794 *seqHead = (BYTE)((LLtype<<6) + (Offtype<<4) + (MLtype<<2));
795 zc->fseCTables_ready = 0;
797 /* Encoding Sequences */
798 { BIT_CStream_t blockStream;
799 FSE_CState_t stateMatchLength;
800 FSE_CState_t stateOffsetBits;
801 FSE_CState_t stateLitLength;
803 CHECK_E(BIT_initCStream(&blockStream, op, oend-op), dstSize_tooSmall); /* not enough space remaining */
806 FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);
807 FSE_initCState2(&stateOffsetBits, CTable_OffsetBits, ofCodeTable[nbSeq-1]);
808 FSE_initCState2(&stateLitLength, CTable_LitLength, llCodeTable[nbSeq-1]);
809 BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);
810 if (MEM_32bits()) BIT_flushBits(&blockStream);
811 BIT_addBits(&blockStream, sequences[nbSeq-1].matchLength, ML_bits[mlCodeTable[nbSeq-1]]);
812 if (MEM_32bits()) BIT_flushBits(&blockStream);
814 U32 const ofBits = ofCodeTable[nbSeq-1];
815 int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
817 BIT_addBits(&blockStream, sequences[nbSeq-1].offset, extraBits);
818 BIT_flushBits(&blockStream);
820 BIT_addBits(&blockStream, sequences[nbSeq-1].offset >> extraBits,
823 BIT_addBits(&blockStream, sequences[nbSeq-1].offset, ofCodeTable[nbSeq-1]);
825 BIT_flushBits(&blockStream);
828 for (n=nbSeq-2 ; n<nbSeq ; n--) { /* intentional underflow */
829 BYTE const llCode = llCodeTable[n];
830 BYTE const ofCode = ofCodeTable[n];
831 BYTE const mlCode = mlCodeTable[n];
832 U32 const llBits = LL_bits[llCode];
833 U32 const ofBits = ofCode; /* 32b*/ /* 64b*/
834 U32 const mlBits = ML_bits[mlCode];
836 FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode); /* 15 */ /* 15 */
837 FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode); /* 24 */ /* 24 */
838 if (MEM_32bits()) BIT_flushBits(&blockStream); /* (7)*/
839 FSE_encodeSymbol(&blockStream, &stateLitLength, llCode); /* 16 */ /* 33 */
840 if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))
841 BIT_flushBits(&blockStream); /* (7)*/
842 BIT_addBits(&blockStream, sequences[n].litLength, llBits);
843 if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);
844 BIT_addBits(&blockStream, sequences[n].matchLength, mlBits);
845 if (MEM_32bits()) BIT_flushBits(&blockStream); /* (7)*/
847 int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
849 BIT_addBits(&blockStream, sequences[n].offset, extraBits);
850 BIT_flushBits(&blockStream); /* (7)*/
852 BIT_addBits(&blockStream, sequences[n].offset >> extraBits,
853 ofBits - extraBits); /* 31 */
855 BIT_addBits(&blockStream, sequences[n].offset, ofBits); /* 31 */
857 BIT_flushBits(&blockStream); /* (7)*/
860 FSE_flushCState(&blockStream, &stateMatchLength);
861 FSE_flushCState(&blockStream, &stateOffsetBits);
862 FSE_flushCState(&blockStream, &stateLitLength);
864 { size_t const streamSize = BIT_closeCStream(&blockStream);
865 if (streamSize==0) return ERROR(dstSize_tooSmall); /* not enough space */
869 /* check compressibility */
870 _check_compressibility:
871 { size_t const minGain = ZSTD_minGain(srcSize);
872 size_t const maxCSize = srcSize - minGain;
873 if ((size_t)(op-ostart) >= maxCSize) {
874 zc->hufCTable_repeatMode = HUF_repeat_none;
878 /* confirm repcodes */
879 { int i; for (i=0; i<ZSTD_REP_NUM; i++) zc->rep[i] = zc->repToConfirm[i]; }
884 #if 0 /* for debug */
885 # define STORESEQ_DEBUG
886 #include <stdio.h> /* fprintf */
887 U32 g_startDebug = 0;
888 const BYTE* g_start = NULL;
891 /*! ZSTD_storeSeq() :
892 Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
893 `offsetCode` : distance to match, or 0 == repCode.
894 `matchCode` : matchLength - MINMATCH
896 MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const void* literals, U32 offsetCode, size_t matchCode)
898 #ifdef STORESEQ_DEBUG
900 const U32 pos = (U32)((const BYTE*)literals - g_start);
901 if (g_start==NULL) g_start = (const BYTE*)literals;
902 if ((pos > 1895000) && (pos < 1895300))
903 DEBUGLOG(5, "Cpos %6u :%5u literals & match %3u bytes at distance %6u \n",
904 pos, (U32)litLength, (U32)matchCode+MINMATCH, (U32)offsetCode);
908 ZSTD_wildcopy(seqStorePtr->lit, literals, litLength);
909 seqStorePtr->lit += litLength;
912 if (litLength>0xFFFF) {
913 seqStorePtr->longLengthID = 1;
914 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
916 seqStorePtr->sequences[0].litLength = (U16)litLength;
919 seqStorePtr->sequences[0].offset = offsetCode + 1;
922 if (matchCode>0xFFFF) {
923 seqStorePtr->longLengthID = 2;
924 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
926 seqStorePtr->sequences[0].matchLength = (U16)matchCode;
928 seqStorePtr->sequences++;
932 /*-*************************************
933 * Match length counter
934 ***************************************/
935 static unsigned ZSTD_NbCommonBytes (register size_t val)
937 if (MEM_isLittleEndian()) {
939 # if defined(_MSC_VER) && defined(_WIN64)
941 _BitScanForward64( &r, (U64)val );
942 return (unsigned)(r>>3);
943 # elif defined(__GNUC__) && (__GNUC__ >= 3)
944 return (__builtin_ctzll((U64)val) >> 3);
946 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
947 0, 3, 1, 3, 1, 4, 2, 7,
948 0, 2, 3, 6, 1, 5, 3, 5,
949 1, 3, 4, 4, 2, 5, 6, 7,
950 7, 0, 1, 2, 3, 3, 4, 6,
951 2, 6, 5, 5, 3, 4, 5, 6,
952 7, 1, 2, 4, 6, 4, 4, 5,
953 7, 2, 6, 5, 7, 6, 7, 7 };
954 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
956 } else { /* 32 bits */
957 # if defined(_MSC_VER)
959 _BitScanForward( &r, (U32)val );
960 return (unsigned)(r>>3);
961 # elif defined(__GNUC__) && (__GNUC__ >= 3)
962 return (__builtin_ctz((U32)val) >> 3);
964 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
965 3, 2, 2, 1, 3, 2, 0, 1,
966 3, 3, 1, 2, 2, 2, 2, 0,
967 3, 1, 2, 0, 1, 0, 1, 1 };
968 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
971 } else { /* Big Endian CPU */
973 # if defined(_MSC_VER) && defined(_WIN64)
975 _BitScanReverse64( &r, val );
976 return (unsigned)(r>>3);
977 # elif defined(__GNUC__) && (__GNUC__ >= 3)
978 return (__builtin_clzll(val) >> 3);
981 const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */
982 if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
983 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
987 } else { /* 32 bits */
988 # if defined(_MSC_VER)
990 _BitScanReverse( &r, (unsigned long)val );
991 return (unsigned)(r>>3);
992 # elif defined(__GNUC__) && (__GNUC__ >= 3)
993 return (__builtin_clz((U32)val) >> 3);
996 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
1004 static size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
1006 const BYTE* const pStart = pIn;
1007 const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
1009 while (pIn < pInLoopLimit) {
1010 size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
1011 if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
1012 pIn += ZSTD_NbCommonBytes(diff);
1013 return (size_t)(pIn - pStart);
1015 if (MEM_64bits()) if ((pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
1016 if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
1017 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
1018 return (size_t)(pIn - pStart);
1021 /** ZSTD_count_2segments() :
1022 * can count match length with `ip` & `match` in 2 different segments.
1023 * convention : on reaching mEnd, match count continue starting from iStart
1025 static size_t ZSTD_count_2segments(const BYTE* ip, const BYTE* match, const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
1027 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
1028 size_t const matchLength = ZSTD_count(ip, match, vEnd);
1029 if (match + matchLength != mEnd) return matchLength;
1030 return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
1034 /*-*************************************
1036 ***************************************/
1037 static const U32 prime3bytes = 506832829U;
1038 static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; }
1039 MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
1041 static const U32 prime4bytes = 2654435761U;
1042 static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
1043 static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
1045 static const U64 prime5bytes = 889523592379ULL;
1046 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h)) ; }
1047 static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
1049 static const U64 prime6bytes = 227718039650203ULL;
1050 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; }
1051 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
1053 static const U64 prime7bytes = 58295818150454627ULL;
1054 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h)) ; }
1055 static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
1057 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
1058 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
1059 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
1061 static size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
1066 case 4: return ZSTD_hash4Ptr(p, hBits);
1067 case 5: return ZSTD_hash5Ptr(p, hBits);
1068 case 6: return ZSTD_hash6Ptr(p, hBits);
1069 case 7: return ZSTD_hash7Ptr(p, hBits);
1070 case 8: return ZSTD_hash8Ptr(p, hBits);
1075 /*-*************************************
1077 ***************************************/
1078 static void ZSTD_fillHashTable (ZSTD_CCtx* zc, const void* end, const U32 mls)
1080 U32* const hashTable = zc->hashTable;
1081 U32 const hBits = zc->params.cParams.hashLog;
1082 const BYTE* const base = zc->base;
1083 const BYTE* ip = base + zc->nextToUpdate;
1084 const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
1085 const size_t fastHashFillStep = 3;
1088 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip - base);
1089 ip += fastHashFillStep;
1095 void ZSTD_compressBlock_fast_generic(ZSTD_CCtx* cctx,
1096 const void* src, size_t srcSize,
1099 U32* const hashTable = cctx->hashTable;
1100 U32 const hBits = cctx->params.cParams.hashLog;
1101 seqStore_t* seqStorePtr = &(cctx->seqStore);
1102 const BYTE* const base = cctx->base;
1103 const BYTE* const istart = (const BYTE*)src;
1104 const BYTE* ip = istart;
1105 const BYTE* anchor = istart;
1106 const U32 lowestIndex = cctx->dictLimit;
1107 const BYTE* const lowest = base + lowestIndex;
1108 const BYTE* const iend = istart + srcSize;
1109 const BYTE* const ilimit = iend - HASH_READ_SIZE;
1110 U32 offset_1=cctx->rep[0], offset_2=cctx->rep[1];
1111 U32 offsetSaved = 0;
1115 { U32 const maxRep = (U32)(ip-lowest);
1116 if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;
1117 if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;
1120 /* Main Search Loop */
1121 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */
1123 size_t const h = ZSTD_hashPtr(ip, hBits, mls);
1124 U32 const current = (U32)(ip-base);
1125 U32 const matchIndex = hashTable[h];
1126 const BYTE* match = base + matchIndex;
1127 hashTable[h] = current; /* update hash table */
1129 if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) {
1130 mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
1132 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1135 if ( (matchIndex <= lowestIndex) || (MEM_read32(match) != MEM_read32(ip)) ) {
1136 ip += ((ip-anchor) >> g_searchStrength) + 1;
1139 mLength = ZSTD_count(ip+4, match+4, iend) + 4;
1140 offset = (U32)(ip-match);
1141 while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1142 offset_2 = offset_1;
1145 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1154 hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2; /* here because current+2 could be > iend-8 */
1155 hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base);
1156 /* check immediate repcode */
1157 while ( (ip <= ilimit)
1159 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
1160 /* store sequence */
1161 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
1162 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; } /* swap offset_2 <=> offset_1 */
1163 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip-base);
1164 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength-MINMATCH);
1167 continue; /* faster when present ... (?) */
1170 /* save reps for next block */
1171 cctx->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved;
1172 cctx->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved;
1175 { size_t const lastLLSize = iend - anchor;
1176 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1177 seqStorePtr->lit += lastLLSize;
1182 static void ZSTD_compressBlock_fast(ZSTD_CCtx* ctx,
1183 const void* src, size_t srcSize)
1185 const U32 mls = ctx->params.cParams.searchLength;
1188 default: /* includes case 3 */
1190 ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 4); return;
1192 ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 5); return;
1194 ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 6); return;
1196 ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 7); return;
1201 static void ZSTD_compressBlock_fast_extDict_generic(ZSTD_CCtx* ctx,
1202 const void* src, size_t srcSize,
1205 U32* hashTable = ctx->hashTable;
1206 const U32 hBits = ctx->params.cParams.hashLog;
1207 seqStore_t* seqStorePtr = &(ctx->seqStore);
1208 const BYTE* const base = ctx->base;
1209 const BYTE* const dictBase = ctx->dictBase;
1210 const BYTE* const istart = (const BYTE*)src;
1211 const BYTE* ip = istart;
1212 const BYTE* anchor = istart;
1213 const U32 lowestIndex = ctx->lowLimit;
1214 const BYTE* const dictStart = dictBase + lowestIndex;
1215 const U32 dictLimit = ctx->dictLimit;
1216 const BYTE* const lowPrefixPtr = base + dictLimit;
1217 const BYTE* const dictEnd = dictBase + dictLimit;
1218 const BYTE* const iend = istart + srcSize;
1219 const BYTE* const ilimit = iend - 8;
1220 U32 offset_1=ctx->rep[0], offset_2=ctx->rep[1];
1223 while (ip < ilimit) { /* < instead of <=, because (ip+1) */
1224 const size_t h = ZSTD_hashPtr(ip, hBits, mls);
1225 const U32 matchIndex = hashTable[h];
1226 const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base;
1227 const BYTE* match = matchBase + matchIndex;
1228 const U32 current = (U32)(ip-base);
1229 const U32 repIndex = current + 1 - offset_1; /* offset_1 expected <= current +1 */
1230 const BYTE* repBase = repIndex < dictLimit ? dictBase : base;
1231 const BYTE* repMatch = repBase + repIndex;
1233 hashTable[h] = current; /* update hash table */
1235 if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex))
1236 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
1237 const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend;
1238 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, lowPrefixPtr) + 4;
1240 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1242 if ( (matchIndex < lowestIndex) ||
1243 (MEM_read32(match) != MEM_read32(ip)) ) {
1244 ip += ((ip-anchor) >> g_searchStrength) + 1;
1247 { const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend;
1248 const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;
1250 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, lowPrefixPtr) + 4;
1251 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1252 offset = current - matchIndex;
1253 offset_2 = offset_1;
1255 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1258 /* found a match : store it */
1264 hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2;
1265 hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base);
1266 /* check immediate repcode */
1267 while (ip <= ilimit) {
1268 U32 const current2 = (U32)(ip-base);
1269 U32 const repIndex2 = current2 - offset_2;
1270 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;
1271 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */
1272 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
1273 const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;
1274 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, lowPrefixPtr) + 4;
1275 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */
1276 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2-MINMATCH);
1277 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = current2;
1285 /* save reps for next block */
1286 ctx->repToConfirm[0] = offset_1; ctx->repToConfirm[1] = offset_2;
1289 { size_t const lastLLSize = iend - anchor;
1290 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1291 seqStorePtr->lit += lastLLSize;
1296 static void ZSTD_compressBlock_fast_extDict(ZSTD_CCtx* ctx,
1297 const void* src, size_t srcSize)
1299 U32 const mls = ctx->params.cParams.searchLength;
1302 default: /* includes case 3 */
1304 ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 4); return;
1306 ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 5); return;
1308 ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 6); return;
1310 ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 7); return;
1315 /*-*************************************
1317 ***************************************/
1318 static void ZSTD_fillDoubleHashTable (ZSTD_CCtx* cctx, const void* end, const U32 mls)
1320 U32* const hashLarge = cctx->hashTable;
1321 U32 const hBitsL = cctx->params.cParams.hashLog;
1322 U32* const hashSmall = cctx->chainTable;
1323 U32 const hBitsS = cctx->params.cParams.chainLog;
1324 const BYTE* const base = cctx->base;
1325 const BYTE* ip = base + cctx->nextToUpdate;
1326 const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
1327 const size_t fastHashFillStep = 3;
1330 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip - base);
1331 hashLarge[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip - base);
1332 ip += fastHashFillStep;
1338 void ZSTD_compressBlock_doubleFast_generic(ZSTD_CCtx* cctx,
1339 const void* src, size_t srcSize,
1342 U32* const hashLong = cctx->hashTable;
1343 const U32 hBitsL = cctx->params.cParams.hashLog;
1344 U32* const hashSmall = cctx->chainTable;
1345 const U32 hBitsS = cctx->params.cParams.chainLog;
1346 seqStore_t* seqStorePtr = &(cctx->seqStore);
1347 const BYTE* const base = cctx->base;
1348 const BYTE* const istart = (const BYTE*)src;
1349 const BYTE* ip = istart;
1350 const BYTE* anchor = istart;
1351 const U32 lowestIndex = cctx->dictLimit;
1352 const BYTE* const lowest = base + lowestIndex;
1353 const BYTE* const iend = istart + srcSize;
1354 const BYTE* const ilimit = iend - HASH_READ_SIZE;
1355 U32 offset_1=cctx->rep[0], offset_2=cctx->rep[1];
1356 U32 offsetSaved = 0;
1360 { U32 const maxRep = (U32)(ip-lowest);
1361 if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;
1362 if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;
1365 /* Main Search Loop */
1366 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */
1368 size_t const h2 = ZSTD_hashPtr(ip, hBitsL, 8);
1369 size_t const h = ZSTD_hashPtr(ip, hBitsS, mls);
1370 U32 const current = (U32)(ip-base);
1371 U32 const matchIndexL = hashLong[h2];
1372 U32 const matchIndexS = hashSmall[h];
1373 const BYTE* matchLong = base + matchIndexL;
1374 const BYTE* match = base + matchIndexS;
1375 hashLong[h2] = hashSmall[h] = current; /* update hash tables */
1377 assert(offset_1 <= current); /* supposed guaranteed by construction */
1378 if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) {
1380 mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
1382 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1385 if ( (matchIndexL > lowestIndex) && (MEM_read64(matchLong) == MEM_read64(ip)) ) {
1386 mLength = ZSTD_count(ip+8, matchLong+8, iend) + 8;
1387 offset = (U32)(ip-matchLong);
1388 while (((ip>anchor) & (matchLong>lowest)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */
1389 } else if ( (matchIndexS > lowestIndex) && (MEM_read32(match) == MEM_read32(ip)) ) {
1390 size_t const hl3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
1391 U32 const matchIndexL3 = hashLong[hl3];
1392 const BYTE* matchL3 = base + matchIndexL3;
1393 hashLong[hl3] = current + 1;
1394 if ( (matchIndexL3 > lowestIndex) && (MEM_read64(matchL3) == MEM_read64(ip+1)) ) {
1395 mLength = ZSTD_count(ip+9, matchL3+8, iend) + 8;
1397 offset = (U32)(ip-matchL3);
1398 while (((ip>anchor) & (matchL3>lowest)) && (ip[-1] == matchL3[-1])) { ip--; matchL3--; mLength++; } /* catch up */
1400 mLength = ZSTD_count(ip+4, match+4, iend) + 4;
1401 offset = (U32)(ip-match);
1402 while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1405 ip += ((ip-anchor) >> g_searchStrength) + 1;
1409 offset_2 = offset_1;
1412 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1421 hashLong[ZSTD_hashPtr(base+current+2, hBitsL, 8)] =
1422 hashSmall[ZSTD_hashPtr(base+current+2, hBitsS, mls)] = current+2; /* here because current+2 could be > iend-8 */
1423 hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] =
1424 hashSmall[ZSTD_hashPtr(ip-2, hBitsS, mls)] = (U32)(ip-2-base);
1426 /* check immediate repcode */
1427 while ( (ip <= ilimit)
1429 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
1430 /* store sequence */
1431 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
1432 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; } /* swap offset_2 <=> offset_1 */
1433 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip-base);
1434 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip-base);
1435 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength-MINMATCH);
1438 continue; /* faster when present ... (?) */
1441 /* save reps for next block */
1442 cctx->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved;
1443 cctx->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved;
1446 { size_t const lastLLSize = iend - anchor;
1447 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1448 seqStorePtr->lit += lastLLSize;
1453 static void ZSTD_compressBlock_doubleFast(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
1455 const U32 mls = ctx->params.cParams.searchLength;
1458 default: /* includes case 3 */
1460 ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 4); return;
1462 ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 5); return;
1464 ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 6); return;
1466 ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 7); return;
1471 static void ZSTD_compressBlock_doubleFast_extDict_generic(ZSTD_CCtx* ctx,
1472 const void* src, size_t srcSize,
1475 U32* const hashLong = ctx->hashTable;
1476 U32 const hBitsL = ctx->params.cParams.hashLog;
1477 U32* const hashSmall = ctx->chainTable;
1478 U32 const hBitsS = ctx->params.cParams.chainLog;
1479 seqStore_t* seqStorePtr = &(ctx->seqStore);
1480 const BYTE* const base = ctx->base;
1481 const BYTE* const dictBase = ctx->dictBase;
1482 const BYTE* const istart = (const BYTE*)src;
1483 const BYTE* ip = istart;
1484 const BYTE* anchor = istart;
1485 const U32 lowestIndex = ctx->lowLimit;
1486 const BYTE* const dictStart = dictBase + lowestIndex;
1487 const U32 dictLimit = ctx->dictLimit;
1488 const BYTE* const lowPrefixPtr = base + dictLimit;
1489 const BYTE* const dictEnd = dictBase + dictLimit;
1490 const BYTE* const iend = istart + srcSize;
1491 const BYTE* const ilimit = iend - 8;
1492 U32 offset_1=ctx->rep[0], offset_2=ctx->rep[1];
1495 while (ip < ilimit) { /* < instead of <=, because (ip+1) */
1496 const size_t hSmall = ZSTD_hashPtr(ip, hBitsS, mls);
1497 const U32 matchIndex = hashSmall[hSmall];
1498 const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base;
1499 const BYTE* match = matchBase + matchIndex;
1501 const size_t hLong = ZSTD_hashPtr(ip, hBitsL, 8);
1502 const U32 matchLongIndex = hashLong[hLong];
1503 const BYTE* matchLongBase = matchLongIndex < dictLimit ? dictBase : base;
1504 const BYTE* matchLong = matchLongBase + matchLongIndex;
1506 const U32 current = (U32)(ip-base);
1507 const U32 repIndex = current + 1 - offset_1; /* offset_1 expected <= current +1 */
1508 const BYTE* repBase = repIndex < dictLimit ? dictBase : base;
1509 const BYTE* repMatch = repBase + repIndex;
1511 hashSmall[hSmall] = hashLong[hLong] = current; /* update hash table */
1513 if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex))
1514 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
1515 const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend;
1516 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, lowPrefixPtr) + 4;
1518 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1520 if ((matchLongIndex > lowestIndex) && (MEM_read64(matchLong) == MEM_read64(ip))) {
1521 const BYTE* matchEnd = matchLongIndex < dictLimit ? dictEnd : iend;
1522 const BYTE* lowMatchPtr = matchLongIndex < dictLimit ? dictStart : lowPrefixPtr;
1524 mLength = ZSTD_count_2segments(ip+8, matchLong+8, iend, matchEnd, lowPrefixPtr) + 8;
1525 offset = current - matchLongIndex;
1526 while (((ip>anchor) & (matchLong>lowMatchPtr)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */
1527 offset_2 = offset_1;
1529 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1531 } else if ((matchIndex > lowestIndex) && (MEM_read32(match) == MEM_read32(ip))) {
1532 size_t const h3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
1533 U32 const matchIndex3 = hashLong[h3];
1534 const BYTE* const match3Base = matchIndex3 < dictLimit ? dictBase : base;
1535 const BYTE* match3 = match3Base + matchIndex3;
1537 hashLong[h3] = current + 1;
1538 if ( (matchIndex3 > lowestIndex) && (MEM_read64(match3) == MEM_read64(ip+1)) ) {
1539 const BYTE* matchEnd = matchIndex3 < dictLimit ? dictEnd : iend;
1540 const BYTE* lowMatchPtr = matchIndex3 < dictLimit ? dictStart : lowPrefixPtr;
1541 mLength = ZSTD_count_2segments(ip+9, match3+8, iend, matchEnd, lowPrefixPtr) + 8;
1543 offset = current+1 - matchIndex3;
1544 while (((ip>anchor) & (match3>lowMatchPtr)) && (ip[-1] == match3[-1])) { ip--; match3--; mLength++; } /* catch up */
1546 const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend;
1547 const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;
1548 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, lowPrefixPtr) + 4;
1549 offset = current - matchIndex;
1550 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1552 offset_2 = offset_1;
1554 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1557 ip += ((ip-anchor) >> g_searchStrength) + 1;
1561 /* found a match : store it */
1567 hashSmall[ZSTD_hashPtr(base+current+2, hBitsS, mls)] = current+2;
1568 hashLong[ZSTD_hashPtr(base+current+2, hBitsL, 8)] = current+2;
1569 hashSmall[ZSTD_hashPtr(ip-2, hBitsS, mls)] = (U32)(ip-2-base);
1570 hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base);
1571 /* check immediate repcode */
1572 while (ip <= ilimit) {
1573 U32 const current2 = (U32)(ip-base);
1574 U32 const repIndex2 = current2 - offset_2;
1575 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;
1576 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */
1577 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
1578 const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;
1579 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, lowPrefixPtr) + 4;
1580 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */
1581 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2-MINMATCH);
1582 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2;
1583 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2;
1591 /* save reps for next block */
1592 ctx->repToConfirm[0] = offset_1; ctx->repToConfirm[1] = offset_2;
1595 { size_t const lastLLSize = iend - anchor;
1596 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1597 seqStorePtr->lit += lastLLSize;
1602 static void ZSTD_compressBlock_doubleFast_extDict(ZSTD_CCtx* ctx,
1603 const void* src, size_t srcSize)
1605 U32 const mls = ctx->params.cParams.searchLength;
1608 default: /* includes case 3 */
1610 ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 4); return;
1612 ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 5); return;
1614 ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 6); return;
1616 ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 7); return;
1621 /*-*************************************
1622 * Binary Tree search
1623 ***************************************/
1624 /** ZSTD_insertBt1() : add one or multiple positions to tree.
1625 * ip : assumed <= iend-8 .
1626 * @return : nb of positions added */
1627 static U32 ZSTD_insertBt1(ZSTD_CCtx* zc, const BYTE* const ip, const U32 mls, const BYTE* const iend, U32 nbCompares,
1630 U32* const hashTable = zc->hashTable;
1631 U32 const hashLog = zc->params.cParams.hashLog;
1632 size_t const h = ZSTD_hashPtr(ip, hashLog, mls);
1633 U32* const bt = zc->chainTable;
1634 U32 const btLog = zc->params.cParams.chainLog - 1;
1635 U32 const btMask = (1 << btLog) - 1;
1636 U32 matchIndex = hashTable[h];
1637 size_t commonLengthSmaller=0, commonLengthLarger=0;
1638 const BYTE* const base = zc->base;
1639 const BYTE* const dictBase = zc->dictBase;
1640 const U32 dictLimit = zc->dictLimit;
1641 const BYTE* const dictEnd = dictBase + dictLimit;
1642 const BYTE* const prefixStart = base + dictLimit;
1644 const U32 current = (U32)(ip-base);
1645 const U32 btLow = btMask >= current ? 0 : current - btMask;
1646 U32* smallerPtr = bt + 2*(current&btMask);
1647 U32* largerPtr = smallerPtr + 1;
1648 U32 dummy32; /* to be nullified at the end */
1649 U32 const windowLow = zc->lowLimit;
1650 U32 matchEndIdx = current+8;
1651 size_t bestLength = 8;
1652 #ifdef ZSTD_C_PREDICT
1653 U32 predictedSmall = *(bt + 2*((current-1)&btMask) + 0);
1654 U32 predictedLarge = *(bt + 2*((current-1)&btMask) + 1);
1655 predictedSmall += (predictedSmall>0);
1656 predictedLarge += (predictedLarge>0);
1657 #endif /* ZSTD_C_PREDICT */
1659 hashTable[h] = current; /* Update Hash Table */
1661 while (nbCompares-- && (matchIndex > windowLow)) {
1662 U32* const nextPtr = bt + 2*(matchIndex & btMask);
1663 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
1665 #ifdef ZSTD_C_PREDICT /* note : can create issues when hlog small <= 11 */
1666 const U32* predictPtr = bt + 2*((matchIndex-1) & btMask); /* written this way, as bt is a roll buffer */
1667 if (matchIndex == predictedSmall) {
1668 /* no need to check length, result known */
1669 *smallerPtr = matchIndex;
1670 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
1671 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */
1672 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
1673 predictedSmall = predictPtr[1] + (predictPtr[1]>0);
1676 if (matchIndex == predictedLarge) {
1677 *largerPtr = matchIndex;
1678 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
1679 largerPtr = nextPtr;
1680 matchIndex = nextPtr[0];
1681 predictedLarge = predictPtr[0] + (predictPtr[0]>0);
1685 if ((!extDict) || (matchIndex+matchLength >= dictLimit)) {
1686 match = base + matchIndex;
1687 if (match[matchLength] == ip[matchLength])
1688 matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iend) +1;
1690 match = dictBase + matchIndex;
1691 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
1692 if (matchIndex+matchLength >= dictLimit)
1693 match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
1696 if (matchLength > bestLength) {
1697 bestLength = matchLength;
1698 if (matchLength > matchEndIdx - matchIndex)
1699 matchEndIdx = matchIndex + (U32)matchLength;
1702 if (ip+matchLength == iend) /* equal : no way to know if inf or sup */
1703 break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt the tree */
1705 if (match[matchLength] < ip[matchLength]) { /* necessarily within correct buffer */
1706 /* match is smaller than current */
1707 *smallerPtr = matchIndex; /* update smaller idx */
1708 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
1709 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
1710 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */
1711 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
1713 /* match is larger than current */
1714 *largerPtr = matchIndex;
1715 commonLengthLarger = matchLength;
1716 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
1717 largerPtr = nextPtr;
1718 matchIndex = nextPtr[0];
1721 *smallerPtr = *largerPtr = 0;
1722 if (bestLength > 384) return MIN(192, (U32)(bestLength - 384)); /* speed optimization */
1723 if (matchEndIdx > current + 8) return matchEndIdx - current - 8;
1728 static size_t ZSTD_insertBtAndFindBestMatch (
1730 const BYTE* const ip, const BYTE* const iend,
1732 U32 nbCompares, const U32 mls,
1735 U32* const hashTable = zc->hashTable;
1736 U32 const hashLog = zc->params.cParams.hashLog;
1737 size_t const h = ZSTD_hashPtr(ip, hashLog, mls);
1738 U32* const bt = zc->chainTable;
1739 U32 const btLog = zc->params.cParams.chainLog - 1;
1740 U32 const btMask = (1 << btLog) - 1;
1741 U32 matchIndex = hashTable[h];
1742 size_t commonLengthSmaller=0, commonLengthLarger=0;
1743 const BYTE* const base = zc->base;
1744 const BYTE* const dictBase = zc->dictBase;
1745 const U32 dictLimit = zc->dictLimit;
1746 const BYTE* const dictEnd = dictBase + dictLimit;
1747 const BYTE* const prefixStart = base + dictLimit;
1748 const U32 current = (U32)(ip-base);
1749 const U32 btLow = btMask >= current ? 0 : current - btMask;
1750 const U32 windowLow = zc->lowLimit;
1751 U32* smallerPtr = bt + 2*(current&btMask);
1752 U32* largerPtr = bt + 2*(current&btMask) + 1;
1753 U32 matchEndIdx = current+8;
1754 U32 dummy32; /* to be nullified at the end */
1755 size_t bestLength = 0;
1757 hashTable[h] = current; /* Update Hash Table */
1759 while (nbCompares-- && (matchIndex > windowLow)) {
1760 U32* const nextPtr = bt + 2*(matchIndex & btMask);
1761 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
1764 if ((!extDict) || (matchIndex+matchLength >= dictLimit)) {
1765 match = base + matchIndex;
1766 if (match[matchLength] == ip[matchLength])
1767 matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iend) +1;
1769 match = dictBase + matchIndex;
1770 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
1771 if (matchIndex+matchLength >= dictLimit)
1772 match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
1775 if (matchLength > bestLength) {
1776 if (matchLength > matchEndIdx - matchIndex)
1777 matchEndIdx = matchIndex + (U32)matchLength;
1778 if ( (4*(int)(matchLength-bestLength)) > (int)(ZSTD_highbit32(current-matchIndex+1) - ZSTD_highbit32((U32)offsetPtr[0]+1)) )
1779 bestLength = matchLength, *offsetPtr = ZSTD_REP_MOVE + current - matchIndex;
1780 if (ip+matchLength == iend) /* equal : no way to know if inf or sup */
1781 break; /* drop, to guarantee consistency (miss a little bit of compression) */
1784 if (match[matchLength] < ip[matchLength]) {
1785 /* match is smaller than current */
1786 *smallerPtr = matchIndex; /* update smaller idx */
1787 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
1788 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
1789 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */
1790 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
1792 /* match is larger than current */
1793 *largerPtr = matchIndex;
1794 commonLengthLarger = matchLength;
1795 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
1796 largerPtr = nextPtr;
1797 matchIndex = nextPtr[0];
1800 *smallerPtr = *largerPtr = 0;
1802 zc->nextToUpdate = (matchEndIdx > current + 8) ? matchEndIdx - 8 : current+1;
1807 static void ZSTD_updateTree(ZSTD_CCtx* zc, const BYTE* const ip, const BYTE* const iend, const U32 nbCompares, const U32 mls)
1809 const BYTE* const base = zc->base;
1810 const U32 target = (U32)(ip - base);
1811 U32 idx = zc->nextToUpdate;
1814 idx += ZSTD_insertBt1(zc, base+idx, mls, iend, nbCompares, 0);
1817 /** ZSTD_BtFindBestMatch() : Tree updater, providing best match */
1818 static size_t ZSTD_BtFindBestMatch (
1820 const BYTE* const ip, const BYTE* const iLimit,
1822 const U32 maxNbAttempts, const U32 mls)
1824 if (ip < zc->base + zc->nextToUpdate) return 0; /* skipped area */
1825 ZSTD_updateTree(zc, ip, iLimit, maxNbAttempts, mls);
1826 return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls, 0);
1830 static size_t ZSTD_BtFindBestMatch_selectMLS (
1831 ZSTD_CCtx* zc, /* Index table will be updated */
1832 const BYTE* ip, const BYTE* const iLimit,
1834 const U32 maxNbAttempts, const U32 matchLengthSearch)
1836 switch(matchLengthSearch)
1838 default : /* includes case 3 */
1839 case 4 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4);
1840 case 5 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5);
1842 case 6 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6);
1847 static void ZSTD_updateTree_extDict(ZSTD_CCtx* zc, const BYTE* const ip, const BYTE* const iend, const U32 nbCompares, const U32 mls)
1849 const BYTE* const base = zc->base;
1850 const U32 target = (U32)(ip - base);
1851 U32 idx = zc->nextToUpdate;
1853 while (idx < target) idx += ZSTD_insertBt1(zc, base+idx, mls, iend, nbCompares, 1);
1857 /** Tree updater, providing best match */
1858 static size_t ZSTD_BtFindBestMatch_extDict (
1860 const BYTE* const ip, const BYTE* const iLimit,
1862 const U32 maxNbAttempts, const U32 mls)
1864 if (ip < zc->base + zc->nextToUpdate) return 0; /* skipped area */
1865 ZSTD_updateTree_extDict(zc, ip, iLimit, maxNbAttempts, mls);
1866 return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls, 1);
1870 static size_t ZSTD_BtFindBestMatch_selectMLS_extDict (
1871 ZSTD_CCtx* zc, /* Index table will be updated */
1872 const BYTE* ip, const BYTE* const iLimit,
1874 const U32 maxNbAttempts, const U32 matchLengthSearch)
1876 switch(matchLengthSearch)
1878 default : /* includes case 3 */
1879 case 4 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4);
1880 case 5 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5);
1882 case 6 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6);
1888 /* *********************************
1890 ***********************************/
1891 #define NEXT_IN_CHAIN(d, mask) chainTable[(d) & mask]
1893 /* Update chains up to ip (excluded)
1894 Assumption : always within prefix (i.e. not within extDict) */
1896 U32 ZSTD_insertAndFindFirstIndex (ZSTD_CCtx* zc, const BYTE* ip, U32 mls)
1898 U32* const hashTable = zc->hashTable;
1899 const U32 hashLog = zc->params.cParams.hashLog;
1900 U32* const chainTable = zc->chainTable;
1901 const U32 chainMask = (1 << zc->params.cParams.chainLog) - 1;
1902 const BYTE* const base = zc->base;
1903 const U32 target = (U32)(ip - base);
1904 U32 idx = zc->nextToUpdate;
1906 while(idx < target) { /* catch up */
1907 size_t const h = ZSTD_hashPtr(base+idx, hashLog, mls);
1908 NEXT_IN_CHAIN(idx, chainMask) = hashTable[h];
1913 zc->nextToUpdate = target;
1914 return hashTable[ZSTD_hashPtr(ip, hashLog, mls)];
1919 FORCE_INLINE /* inlining is important to hardwire a hot branch (template emulation) */
1920 size_t ZSTD_HcFindBestMatch_generic (
1921 ZSTD_CCtx* zc, /* Index table will be updated */
1922 const BYTE* const ip, const BYTE* const iLimit,
1924 const U32 maxNbAttempts, const U32 mls, const U32 extDict)
1926 U32* const chainTable = zc->chainTable;
1927 const U32 chainSize = (1 << zc->params.cParams.chainLog);
1928 const U32 chainMask = chainSize-1;
1929 const BYTE* const base = zc->base;
1930 const BYTE* const dictBase = zc->dictBase;
1931 const U32 dictLimit = zc->dictLimit;
1932 const BYTE* const prefixStart = base + dictLimit;
1933 const BYTE* const dictEnd = dictBase + dictLimit;
1934 const U32 lowLimit = zc->lowLimit;
1935 const U32 current = (U32)(ip-base);
1936 const U32 minChain = current > chainSize ? current - chainSize : 0;
1937 int nbAttempts=maxNbAttempts;
1940 /* HC4 match finder */
1941 U32 matchIndex = ZSTD_insertAndFindFirstIndex (zc, ip, mls);
1943 for ( ; (matchIndex>lowLimit) & (nbAttempts>0) ; nbAttempts--) {
1946 if ((!extDict) || matchIndex >= dictLimit) {
1947 match = base + matchIndex;
1948 if (match[ml] == ip[ml]) /* potentially better */
1949 currentMl = ZSTD_count(ip, match, iLimit);
1951 match = dictBase + matchIndex;
1952 if (MEM_read32(match) == MEM_read32(ip)) /* assumption : matchIndex <= dictLimit-4 (by table construction) */
1953 currentMl = ZSTD_count_2segments(ip+4, match+4, iLimit, dictEnd, prefixStart) + 4;
1956 /* save best solution */
1957 if (currentMl > ml) {
1959 *offsetPtr = current - matchIndex + ZSTD_REP_MOVE;
1960 if (ip+currentMl == iLimit) break; /* best possible, avoids read overflow on next attempt */
1963 if (matchIndex <= minChain) break;
1964 matchIndex = NEXT_IN_CHAIN(matchIndex, chainMask);
1971 FORCE_INLINE size_t ZSTD_HcFindBestMatch_selectMLS (
1973 const BYTE* ip, const BYTE* const iLimit,
1975 const U32 maxNbAttempts, const U32 matchLengthSearch)
1977 switch(matchLengthSearch)
1979 default : /* includes case 3 */
1980 case 4 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 0);
1981 case 5 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 0);
1983 case 6 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 0);
1988 FORCE_INLINE size_t ZSTD_HcFindBestMatch_extDict_selectMLS (
1990 const BYTE* ip, const BYTE* const iLimit,
1992 const U32 maxNbAttempts, const U32 matchLengthSearch)
1994 switch(matchLengthSearch)
1996 default : /* includes case 3 */
1997 case 4 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 1);
1998 case 5 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 1);
2000 case 6 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 1);
2005 /* *******************************
2006 * Common parser - lazy strategy
2007 *********************************/
2009 void ZSTD_compressBlock_lazy_generic(ZSTD_CCtx* ctx,
2010 const void* src, size_t srcSize,
2011 const U32 searchMethod, const U32 depth)
2013 seqStore_t* seqStorePtr = &(ctx->seqStore);
2014 const BYTE* const istart = (const BYTE*)src;
2015 const BYTE* ip = istart;
2016 const BYTE* anchor = istart;
2017 const BYTE* const iend = istart + srcSize;
2018 const BYTE* const ilimit = iend - 8;
2019 const BYTE* const base = ctx->base + ctx->dictLimit;
2021 U32 const maxSearches = 1 << ctx->params.cParams.searchLog;
2022 U32 const mls = ctx->params.cParams.searchLength;
2024 typedef size_t (*searchMax_f)(ZSTD_CCtx* zc, const BYTE* ip, const BYTE* iLimit,
2026 U32 maxNbAttempts, U32 matchLengthSearch);
2027 searchMax_f const searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS : ZSTD_HcFindBestMatch_selectMLS;
2028 U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1], savedOffset=0;
2032 ctx->nextToUpdate3 = ctx->nextToUpdate;
2033 { U32 const maxRep = (U32)(ip-base);
2034 if (offset_2 > maxRep) savedOffset = offset_2, offset_2 = 0;
2035 if (offset_1 > maxRep) savedOffset = offset_1, offset_1 = 0;
2039 while (ip < ilimit) {
2040 size_t matchLength=0;
2042 const BYTE* start=ip+1;
2045 if ((offset_1>0) & (MEM_read32(ip+1) == MEM_read32(ip+1 - offset_1))) {
2046 /* repcode : we take it */
2047 matchLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
2048 if (depth==0) goto _storeSequence;
2051 /* first search (depth 0) */
2052 { size_t offsetFound = 99999999;
2053 size_t const ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls);
2054 if (ml2 > matchLength)
2055 matchLength = ml2, start = ip, offset=offsetFound;
2058 if (matchLength < 4) {
2059 ip += ((ip-anchor) >> g_searchStrength) + 1; /* jump faster over incompressible sections */
2063 /* let's try to find a better solution */
2067 if ((offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) {
2068 size_t const mlRep = ZSTD_count(ip+4, ip+4-offset_1, iend) + 4;
2069 int const gain2 = (int)(mlRep * 3);
2070 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);
2071 if ((mlRep >= 4) && (gain2 > gain1))
2072 matchLength = mlRep, offset = 0, start = ip;
2074 { size_t offset2=99999999;
2075 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2076 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */
2077 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4);
2078 if ((ml2 >= 4) && (gain2 > gain1)) {
2079 matchLength = ml2, offset = offset2, start = ip;
2080 continue; /* search a better one */
2083 /* let's find an even better one */
2084 if ((depth==2) && (ip<ilimit)) {
2086 if ((offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) {
2087 size_t const ml2 = ZSTD_count(ip+4, ip+4-offset_1, iend) + 4;
2088 int const gain2 = (int)(ml2 * 4);
2089 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);
2090 if ((ml2 >= 4) && (gain2 > gain1))
2091 matchLength = ml2, offset = 0, start = ip;
2093 { size_t offset2=99999999;
2094 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2095 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */
2096 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7);
2097 if ((ml2 >= 4) && (gain2 > gain1)) {
2098 matchLength = ml2, offset = offset2, start = ip;
2101 break; /* nothing found : store previous solution */
2106 while ( (start > anchor)
2107 && (start > base+offset-ZSTD_REP_MOVE)
2108 && (start[-1] == start[-1-offset+ZSTD_REP_MOVE]) ) /* only search for offset within prefix */
2109 { start--; matchLength++; }
2110 offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE);
2113 /* store sequence */
2115 { size_t const litLength = start - anchor;
2116 ZSTD_storeSeq(seqStorePtr, litLength, anchor, (U32)offset, matchLength-MINMATCH);
2117 anchor = ip = start + matchLength;
2120 /* check immediate repcode */
2121 while ( (ip <= ilimit)
2123 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
2124 /* store sequence */
2125 matchLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
2126 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap repcodes */
2127 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength-MINMATCH);
2130 continue; /* faster when present ... (?) */
2133 /* Save reps for next block */
2134 ctx->repToConfirm[0] = offset_1 ? offset_1 : savedOffset;
2135 ctx->repToConfirm[1] = offset_2 ? offset_2 : savedOffset;
2138 { size_t const lastLLSize = iend - anchor;
2139 memcpy(seqStorePtr->lit, anchor, lastLLSize);
2140 seqStorePtr->lit += lastLLSize;
2145 static void ZSTD_compressBlock_btlazy2(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2147 ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 1, 2);
2150 static void ZSTD_compressBlock_lazy2(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2152 ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 2);
2155 static void ZSTD_compressBlock_lazy(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2157 ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 1);
2160 static void ZSTD_compressBlock_greedy(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2162 ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 0);
2167 void ZSTD_compressBlock_lazy_extDict_generic(ZSTD_CCtx* ctx,
2168 const void* src, size_t srcSize,
2169 const U32 searchMethod, const U32 depth)
2171 seqStore_t* seqStorePtr = &(ctx->seqStore);
2172 const BYTE* const istart = (const BYTE*)src;
2173 const BYTE* ip = istart;
2174 const BYTE* anchor = istart;
2175 const BYTE* const iend = istart + srcSize;
2176 const BYTE* const ilimit = iend - 8;
2177 const BYTE* const base = ctx->base;
2178 const U32 dictLimit = ctx->dictLimit;
2179 const U32 lowestIndex = ctx->lowLimit;
2180 const BYTE* const prefixStart = base + dictLimit;
2181 const BYTE* const dictBase = ctx->dictBase;
2182 const BYTE* const dictEnd = dictBase + dictLimit;
2183 const BYTE* const dictStart = dictBase + ctx->lowLimit;
2185 const U32 maxSearches = 1 << ctx->params.cParams.searchLog;
2186 const U32 mls = ctx->params.cParams.searchLength;
2188 typedef size_t (*searchMax_f)(ZSTD_CCtx* zc, const BYTE* ip, const BYTE* iLimit,
2190 U32 maxNbAttempts, U32 matchLengthSearch);
2191 searchMax_f searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS_extDict : ZSTD_HcFindBestMatch_extDict_selectMLS;
2193 U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1];
2196 ctx->nextToUpdate3 = ctx->nextToUpdate;
2197 ip += (ip == prefixStart);
2200 while (ip < ilimit) {
2201 size_t matchLength=0;
2203 const BYTE* start=ip+1;
2204 U32 current = (U32)(ip-base);
2207 { const U32 repIndex = (U32)(current+1 - offset_1);
2208 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2209 const BYTE* const repMatch = repBase + repIndex;
2210 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2211 if (MEM_read32(ip+1) == MEM_read32(repMatch)) {
2212 /* repcode detected we should take it */
2213 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2214 matchLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repEnd, prefixStart) + 4;
2215 if (depth==0) goto _storeSequence;
2218 /* first search (depth 0) */
2219 { size_t offsetFound = 99999999;
2220 size_t const ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls);
2221 if (ml2 > matchLength)
2222 matchLength = ml2, start = ip, offset=offsetFound;
2225 if (matchLength < 4) {
2226 ip += ((ip-anchor) >> g_searchStrength) + 1; /* jump faster over incompressible sections */
2230 /* let's try to find a better solution */
2237 const U32 repIndex = (U32)(current - offset_1);
2238 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2239 const BYTE* const repMatch = repBase + repIndex;
2240 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2241 if (MEM_read32(ip) == MEM_read32(repMatch)) {
2242 /* repcode detected */
2243 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2244 size_t const repLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;
2245 int const gain2 = (int)(repLength * 3);
2246 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);
2247 if ((repLength >= 4) && (gain2 > gain1))
2248 matchLength = repLength, offset = 0, start = ip;
2251 /* search match, depth 1 */
2252 { size_t offset2=99999999;
2253 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2254 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */
2255 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4);
2256 if ((ml2 >= 4) && (gain2 > gain1)) {
2257 matchLength = ml2, offset = offset2, start = ip;
2258 continue; /* search a better one */
2261 /* let's find an even better one */
2262 if ((depth==2) && (ip<ilimit)) {
2267 const U32 repIndex = (U32)(current - offset_1);
2268 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2269 const BYTE* const repMatch = repBase + repIndex;
2270 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2271 if (MEM_read32(ip) == MEM_read32(repMatch)) {
2272 /* repcode detected */
2273 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2274 size_t const repLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;
2275 int const gain2 = (int)(repLength * 4);
2276 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);
2277 if ((repLength >= 4) && (gain2 > gain1))
2278 matchLength = repLength, offset = 0, start = ip;
2281 /* search match, depth 2 */
2282 { size_t offset2=99999999;
2283 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2284 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */
2285 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7);
2286 if ((ml2 >= 4) && (gain2 > gain1)) {
2287 matchLength = ml2, offset = offset2, start = ip;
2290 break; /* nothing found : store previous solution */
2295 U32 const matchIndex = (U32)((start-base) - (offset - ZSTD_REP_MOVE));
2296 const BYTE* match = (matchIndex < dictLimit) ? dictBase + matchIndex : base + matchIndex;
2297 const BYTE* const mStart = (matchIndex < dictLimit) ? dictStart : prefixStart;
2298 while ((start>anchor) && (match>mStart) && (start[-1] == match[-1])) { start--; match--; matchLength++; } /* catch up */
2299 offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE);
2302 /* store sequence */
2304 { size_t const litLength = start - anchor;
2305 ZSTD_storeSeq(seqStorePtr, litLength, anchor, (U32)offset, matchLength-MINMATCH);
2306 anchor = ip = start + matchLength;
2309 /* check immediate repcode */
2310 while (ip <= ilimit) {
2311 const U32 repIndex = (U32)((ip-base) - offset_2);
2312 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2313 const BYTE* const repMatch = repBase + repIndex;
2314 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2315 if (MEM_read32(ip) == MEM_read32(repMatch)) {
2316 /* repcode detected we should take it */
2317 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2318 matchLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;
2319 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap offset history */
2320 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength-MINMATCH);
2323 continue; /* faster when present ... (?) */
2328 /* Save reps for next block */
2329 ctx->repToConfirm[0] = offset_1; ctx->repToConfirm[1] = offset_2;
2332 { size_t const lastLLSize = iend - anchor;
2333 memcpy(seqStorePtr->lit, anchor, lastLLSize);
2334 seqStorePtr->lit += lastLLSize;
2339 void ZSTD_compressBlock_greedy_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2341 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 0);
2344 static void ZSTD_compressBlock_lazy_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2346 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 1);
2349 static void ZSTD_compressBlock_lazy2_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2351 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 2);
2354 static void ZSTD_compressBlock_btlazy2_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2356 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 1, 2);
2360 /* The optimal parser */
2361 #include "zstd_opt.h"
2363 static void ZSTD_compressBlock_btopt(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2365 #ifdef ZSTD_OPT_H_91842398743
2366 ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 0);
2368 (void)ctx; (void)src; (void)srcSize;
2373 static void ZSTD_compressBlock_btopt2(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2375 #ifdef ZSTD_OPT_H_91842398743
2376 ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 1);
2378 (void)ctx; (void)src; (void)srcSize;
2383 static void ZSTD_compressBlock_btopt_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2385 #ifdef ZSTD_OPT_H_91842398743
2386 ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 0);
2388 (void)ctx; (void)src; (void)srcSize;
2393 static void ZSTD_compressBlock_btopt2_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2395 #ifdef ZSTD_OPT_H_91842398743
2396 ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 1);
2398 (void)ctx; (void)src; (void)srcSize;
2404 typedef void (*ZSTD_blockCompressor) (ZSTD_CCtx* ctx, const void* src, size_t srcSize);
2406 static ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, int extDict)
2408 static const ZSTD_blockCompressor blockCompressor[2][8] = {
2409 { ZSTD_compressBlock_fast, ZSTD_compressBlock_doubleFast, ZSTD_compressBlock_greedy,
2410 ZSTD_compressBlock_lazy, ZSTD_compressBlock_lazy2, ZSTD_compressBlock_btlazy2,
2411 ZSTD_compressBlock_btopt, ZSTD_compressBlock_btopt2 },
2412 { ZSTD_compressBlock_fast_extDict, ZSTD_compressBlock_doubleFast_extDict, ZSTD_compressBlock_greedy_extDict,
2413 ZSTD_compressBlock_lazy_extDict,ZSTD_compressBlock_lazy2_extDict, ZSTD_compressBlock_btlazy2_extDict,
2414 ZSTD_compressBlock_btopt_extDict, ZSTD_compressBlock_btopt2_extDict }
2417 return blockCompressor[extDict][(U32)strat];
2421 static size_t ZSTD_compressBlock_internal(ZSTD_CCtx* zc, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2423 ZSTD_blockCompressor const blockCompressor = ZSTD_selectBlockCompressor(zc->params.cParams.strategy, zc->lowLimit < zc->dictLimit);
2424 const BYTE* const base = zc->base;
2425 const BYTE* const istart = (const BYTE*)src;
2426 const U32 current = (U32)(istart-base);
2427 if (srcSize < MIN_CBLOCK_SIZE+ZSTD_blockHeaderSize+1) return 0; /* don't even attempt compression below a certain srcSize */
2428 ZSTD_resetSeqStore(&(zc->seqStore));
2429 if (current > zc->nextToUpdate + 384)
2430 zc->nextToUpdate = current - MIN(192, (U32)(current - zc->nextToUpdate - 384)); /* limited update after finding a very long match */
2431 blockCompressor(zc, src, srcSize);
2432 return ZSTD_compressSequences(zc, dst, dstCapacity, srcSize);
2436 /*! ZSTD_compress_generic() :
2437 * Compress a chunk of data into one or multiple blocks.
2438 * All blocks will be terminated, all input will be consumed.
2439 * Function will issue an error if there is not enough `dstCapacity` to hold the compressed content.
2440 * Frame is supposed already started (header already produced)
2441 * @return : compressed size, or an error code
2443 static size_t ZSTD_compress_generic (ZSTD_CCtx* cctx,
2444 void* dst, size_t dstCapacity,
2445 const void* src, size_t srcSize,
2448 size_t blockSize = cctx->blockSize;
2449 size_t remaining = srcSize;
2450 const BYTE* ip = (const BYTE*)src;
2451 BYTE* const ostart = (BYTE*)dst;
2453 U32 const maxDist = 1 << cctx->params.cParams.windowLog;
2455 if (cctx->params.fParams.checksumFlag && srcSize)
2456 XXH64_update(&cctx->xxhState, src, srcSize);
2459 U32 const lastBlock = lastFrameChunk & (blockSize >= remaining);
2462 if (dstCapacity < ZSTD_blockHeaderSize + MIN_CBLOCK_SIZE)
2463 return ERROR(dstSize_tooSmall); /* not enough space to store compressed block */
2464 if (remaining < blockSize) blockSize = remaining;
2466 /* preemptive overflow correction */
2467 if (cctx->lowLimit > (3U<<29)) {
2468 U32 const cycleMask = (1 << ZSTD_cycleLog(cctx->params.cParams.hashLog, cctx->params.cParams.strategy)) - 1;
2469 U32 const current = (U32)(ip - cctx->base);
2470 U32 const newCurrent = (current & cycleMask) + (1 << cctx->params.cParams.windowLog);
2471 U32 const correction = current - newCurrent;
2472 ZSTD_STATIC_ASSERT(ZSTD_WINDOWLOG_MAX_64 <= 30);
2473 ZSTD_reduceIndex(cctx, correction);
2474 cctx->base += correction;
2475 cctx->dictBase += correction;
2476 cctx->lowLimit -= correction;
2477 cctx->dictLimit -= correction;
2478 if (cctx->nextToUpdate < correction) cctx->nextToUpdate = 0;
2479 else cctx->nextToUpdate -= correction;
2482 if ((U32)(ip+blockSize - cctx->base) > cctx->loadedDictEnd + maxDist) {
2483 /* enforce maxDist */
2484 U32 const newLowLimit = (U32)(ip+blockSize - cctx->base) - maxDist;
2485 if (cctx->lowLimit < newLowLimit) cctx->lowLimit = newLowLimit;
2486 if (cctx->dictLimit < cctx->lowLimit) cctx->dictLimit = cctx->lowLimit;
2489 cSize = ZSTD_compressBlock_internal(cctx, op+ZSTD_blockHeaderSize, dstCapacity-ZSTD_blockHeaderSize, ip, blockSize);
2490 if (ZSTD_isError(cSize)) return cSize;
2492 if (cSize == 0) { /* block is not compressible */
2493 U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(blockSize << 3);
2494 if (blockSize + ZSTD_blockHeaderSize > dstCapacity) return ERROR(dstSize_tooSmall);
2495 MEM_writeLE32(op, cBlockHeader24); /* no pb, 4th byte will be overwritten */
2496 memcpy(op + ZSTD_blockHeaderSize, ip, blockSize);
2497 cSize = ZSTD_blockHeaderSize+blockSize;
2499 U32 const cBlockHeader24 = lastBlock + (((U32)bt_compressed)<<1) + (U32)(cSize << 3);
2500 MEM_writeLE24(op, cBlockHeader24);
2501 cSize += ZSTD_blockHeaderSize;
2504 remaining -= blockSize;
2505 dstCapacity -= cSize;
2510 if (lastFrameChunk && (op>ostart)) cctx->stage = ZSTDcs_ending;
2515 static size_t ZSTD_writeFrameHeader(void* dst, size_t dstCapacity,
2516 ZSTD_parameters params, U64 pledgedSrcSize, U32 dictID)
2517 { BYTE* const op = (BYTE*)dst;
2518 U32 const dictIDSizeCodeLength = (dictID>0) + (dictID>=256) + (dictID>=65536); /* 0-3 */
2519 U32 const dictIDSizeCode = params.fParams.noDictIDFlag ? 0 : dictIDSizeCodeLength; /* 0-3 */
2520 U32 const checksumFlag = params.fParams.checksumFlag>0;
2521 U32 const windowSize = 1U << params.cParams.windowLog;
2522 U32 const singleSegment = params.fParams.contentSizeFlag && (windowSize >= pledgedSrcSize);
2523 BYTE const windowLogByte = (BYTE)((params.cParams.windowLog - ZSTD_WINDOWLOG_ABSOLUTEMIN) << 3);
2524 U32 const fcsCode = params.fParams.contentSizeFlag ?
2525 (pledgedSrcSize>=256) + (pledgedSrcSize>=65536+256) + (pledgedSrcSize>=0xFFFFFFFFU) : /* 0-3 */
2527 BYTE const frameHeaderDecriptionByte = (BYTE)(dictIDSizeCode + (checksumFlag<<2) + (singleSegment<<5) + (fcsCode<<6) );
2530 if (dstCapacity < ZSTD_frameHeaderSize_max) return ERROR(dstSize_tooSmall);
2531 DEBUGLOG(5, "ZSTD_writeFrameHeader : dictIDFlag : %u \n", !params.fParams.noDictIDFlag);
2532 DEBUGLOG(5, "ZSTD_writeFrameHeader : dictID : %u \n", dictID);
2533 DEBUGLOG(5, "ZSTD_writeFrameHeader : dictIDSizeCode : %u \n", dictIDSizeCode);
2535 MEM_writeLE32(dst, ZSTD_MAGICNUMBER);
2536 op[4] = frameHeaderDecriptionByte; pos=5;
2537 if (!singleSegment) op[pos++] = windowLogByte;
2538 switch(dictIDSizeCode)
2540 default: /* impossible */
2542 case 1 : op[pos] = (BYTE)(dictID); pos++; break;
2543 case 2 : MEM_writeLE16(op+pos, (U16)dictID); pos+=2; break;
2544 case 3 : MEM_writeLE32(op+pos, dictID); pos+=4; break;
2548 default: /* impossible */
2549 case 0 : if (singleSegment) op[pos++] = (BYTE)(pledgedSrcSize); break;
2550 case 1 : MEM_writeLE16(op+pos, (U16)(pledgedSrcSize-256)); pos+=2; break;
2551 case 2 : MEM_writeLE32(op+pos, (U32)(pledgedSrcSize)); pos+=4; break;
2552 case 3 : MEM_writeLE64(op+pos, (U64)(pledgedSrcSize)); pos+=8; break;
2558 static size_t ZSTD_compressContinue_internal (ZSTD_CCtx* cctx,
2559 void* dst, size_t dstCapacity,
2560 const void* src, size_t srcSize,
2561 U32 frame, U32 lastFrameChunk)
2563 const BYTE* const ip = (const BYTE*) src;
2566 if (cctx->stage==ZSTDcs_created) return ERROR(stage_wrong); /* missing init (ZSTD_compressBegin) */
2568 if (frame && (cctx->stage==ZSTDcs_init)) {
2569 fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, cctx->params, cctx->frameContentSize, cctx->dictID);
2570 if (ZSTD_isError(fhSize)) return fhSize;
2571 dstCapacity -= fhSize;
2572 dst = (char*)dst + fhSize;
2573 cctx->stage = ZSTDcs_ongoing;
2576 /* Check if blocks follow each other */
2577 if (src != cctx->nextSrc) {
2578 /* not contiguous */
2579 ptrdiff_t const delta = cctx->nextSrc - ip;
2580 cctx->lowLimit = cctx->dictLimit;
2581 cctx->dictLimit = (U32)(cctx->nextSrc - cctx->base);
2582 cctx->dictBase = cctx->base;
2583 cctx->base -= delta;
2584 cctx->nextToUpdate = cctx->dictLimit;
2585 if (cctx->dictLimit - cctx->lowLimit < HASH_READ_SIZE) cctx->lowLimit = cctx->dictLimit; /* too small extDict */
2588 /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
2589 if ((ip+srcSize > cctx->dictBase + cctx->lowLimit) & (ip < cctx->dictBase + cctx->dictLimit)) {
2590 ptrdiff_t const highInputIdx = (ip + srcSize) - cctx->dictBase;
2591 U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)cctx->dictLimit) ? cctx->dictLimit : (U32)highInputIdx;
2592 cctx->lowLimit = lowLimitMax;
2595 cctx->nextSrc = ip + srcSize;
2598 size_t const cSize = frame ?
2599 ZSTD_compress_generic (cctx, dst, dstCapacity, src, srcSize, lastFrameChunk) :
2600 ZSTD_compressBlock_internal (cctx, dst, dstCapacity, src, srcSize);
2601 if (ZSTD_isError(cSize)) return cSize;
2602 cctx->consumedSrcSize += srcSize;
2603 return cSize + fhSize;
2609 size_t ZSTD_compressContinue (ZSTD_CCtx* cctx,
2610 void* dst, size_t dstCapacity,
2611 const void* src, size_t srcSize)
2613 return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 1 /* frame mode */, 0 /* last chunk */);
2617 size_t ZSTD_getBlockSizeMax(ZSTD_CCtx* cctx)
2619 return MIN (ZSTD_BLOCKSIZE_ABSOLUTEMAX, 1 << cctx->params.cParams.windowLog);
2622 size_t ZSTD_compressBlock(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2624 size_t const blockSizeMax = ZSTD_getBlockSizeMax(cctx);
2625 if (srcSize > blockSizeMax) return ERROR(srcSize_wrong);
2626 return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 0 /* frame mode */, 0 /* last chunk */);
2629 /*! ZSTD_loadDictionaryContent() :
2630 * @return : 0, or an error code
2632 static size_t ZSTD_loadDictionaryContent(ZSTD_CCtx* zc, const void* src, size_t srcSize)
2634 const BYTE* const ip = (const BYTE*) src;
2635 const BYTE* const iend = ip + srcSize;
2637 /* input becomes current prefix */
2638 zc->lowLimit = zc->dictLimit;
2639 zc->dictLimit = (U32)(zc->nextSrc - zc->base);
2640 zc->dictBase = zc->base;
2641 zc->base += ip - zc->nextSrc;
2642 zc->nextToUpdate = zc->dictLimit;
2643 zc->loadedDictEnd = zc->forceWindow ? 0 : (U32)(iend - zc->base);
2646 if (srcSize <= HASH_READ_SIZE) return 0;
2648 switch(zc->params.cParams.strategy)
2651 ZSTD_fillHashTable (zc, iend, zc->params.cParams.searchLength);
2655 ZSTD_fillDoubleHashTable (zc, iend, zc->params.cParams.searchLength);
2661 if (srcSize >= HASH_READ_SIZE)
2662 ZSTD_insertAndFindFirstIndex(zc, iend-HASH_READ_SIZE, zc->params.cParams.searchLength);
2668 if (srcSize >= HASH_READ_SIZE)
2669 ZSTD_updateTree(zc, iend-HASH_READ_SIZE, iend, 1 << zc->params.cParams.searchLog, zc->params.cParams.searchLength);
2673 return ERROR(GENERIC); /* strategy doesn't exist; impossible */
2676 zc->nextToUpdate = (U32)(iend - zc->base);
2681 /* Dictionaries that assign zero probability to symbols that show up causes problems
2682 when FSE encoding. Refuse dictionaries that assign zero probability to symbols
2683 that we may encounter during compression.
2684 NOTE: This behavior is not standard and could be improved in the future. */
2685 static size_t ZSTD_checkDictNCount(short* normalizedCounter, unsigned dictMaxSymbolValue, unsigned maxSymbolValue) {
2687 if (dictMaxSymbolValue < maxSymbolValue) return ERROR(dictionary_corrupted);
2688 for (s = 0; s <= maxSymbolValue; ++s) {
2689 if (normalizedCounter[s] == 0) return ERROR(dictionary_corrupted);
2695 /* Dictionary format :
2697 * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#dictionary-format
2699 /*! ZSTD_loadZstdDictionary() :
2700 * @return : 0, or an error code
2701 * assumptions : magic number supposed already checked
2702 * dictSize supposed > 8
2704 static size_t ZSTD_loadZstdDictionary(ZSTD_CCtx* cctx, const void* dict, size_t dictSize)
2706 const BYTE* dictPtr = (const BYTE*)dict;
2707 const BYTE* const dictEnd = dictPtr + dictSize;
2708 short offcodeNCount[MaxOff+1];
2709 unsigned offcodeMaxValue = MaxOff;
2710 BYTE scratchBuffer[1<<MAX(MLFSELog,LLFSELog)];
2712 dictPtr += 4; /* skip magic number */
2713 cctx->dictID = cctx->params.fParams.noDictIDFlag ? 0 : MEM_readLE32(dictPtr);
2716 { size_t const hufHeaderSize = HUF_readCTable(cctx->hufCTable, 255, dictPtr, dictEnd-dictPtr);
2717 if (HUF_isError(hufHeaderSize)) return ERROR(dictionary_corrupted);
2718 dictPtr += hufHeaderSize;
2721 { unsigned offcodeLog;
2722 size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
2723 if (FSE_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
2724 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
2725 /* Defer checking offcodeMaxValue because we need to know the size of the dictionary content */
2726 CHECK_E( FSE_buildCTable_wksp(cctx->offcodeCTable, offcodeNCount, offcodeMaxValue, offcodeLog, scratchBuffer, sizeof(scratchBuffer)),
2727 dictionary_corrupted);
2728 dictPtr += offcodeHeaderSize;
2731 { short matchlengthNCount[MaxML+1];
2732 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
2733 size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
2734 if (FSE_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
2735 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
2736 /* Every match length code must have non-zero probability */
2737 CHECK_F( ZSTD_checkDictNCount(matchlengthNCount, matchlengthMaxValue, MaxML));
2738 CHECK_E( FSE_buildCTable_wksp(cctx->matchlengthCTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, scratchBuffer, sizeof(scratchBuffer)),
2739 dictionary_corrupted);
2740 dictPtr += matchlengthHeaderSize;
2743 { short litlengthNCount[MaxLL+1];
2744 unsigned litlengthMaxValue = MaxLL, litlengthLog;
2745 size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
2746 if (FSE_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
2747 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
2748 /* Every literal length code must have non-zero probability */
2749 CHECK_F( ZSTD_checkDictNCount(litlengthNCount, litlengthMaxValue, MaxLL));
2750 CHECK_E( FSE_buildCTable_wksp(cctx->litlengthCTable, litlengthNCount, litlengthMaxValue, litlengthLog, scratchBuffer, sizeof(scratchBuffer)),
2751 dictionary_corrupted);
2752 dictPtr += litlengthHeaderSize;
2755 if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
2756 cctx->rep[0] = MEM_readLE32(dictPtr+0);
2757 cctx->rep[1] = MEM_readLE32(dictPtr+4);
2758 cctx->rep[2] = MEM_readLE32(dictPtr+8);
2761 { size_t const dictContentSize = (size_t)(dictEnd - dictPtr);
2762 U32 offcodeMax = MaxOff;
2763 if (dictContentSize <= ((U32)-1) - 128 KB) {
2764 U32 const maxOffset = (U32)dictContentSize + 128 KB; /* The maximum offset that must be supported */
2765 offcodeMax = ZSTD_highbit32(maxOffset); /* Calculate minimum offset code required to represent maxOffset */
2767 /* All offset values <= dictContentSize + 128 KB must be representable */
2768 CHECK_F (ZSTD_checkDictNCount(offcodeNCount, offcodeMaxValue, MIN(offcodeMax, MaxOff)));
2769 /* All repCodes must be <= dictContentSize and != 0*/
2771 for (u=0; u<3; u++) {
2772 if (cctx->rep[u] == 0) return ERROR(dictionary_corrupted);
2773 if (cctx->rep[u] > dictContentSize) return ERROR(dictionary_corrupted);
2776 cctx->fseCTables_ready = 1;
2777 cctx->hufCTable_repeatMode = HUF_repeat_valid;
2778 return ZSTD_loadDictionaryContent(cctx, dictPtr, dictContentSize);
2782 /** ZSTD_compress_insertDictionary() :
2783 * @return : 0, or an error code */
2784 static size_t ZSTD_compress_insertDictionary(ZSTD_CCtx* cctx, const void* dict, size_t dictSize)
2786 if ((dict==NULL) || (dictSize<=8)) return 0;
2788 /* dict as pure content */
2789 if ((MEM_readLE32(dict) != ZSTD_DICT_MAGIC) || (cctx->forceRawDict))
2790 return ZSTD_loadDictionaryContent(cctx, dict, dictSize);
2792 /* dict as zstd dictionary */
2793 return ZSTD_loadZstdDictionary(cctx, dict, dictSize);
2796 /*! ZSTD_compressBegin_internal() :
2797 * @return : 0, or an error code */
2798 static size_t ZSTD_compressBegin_internal(ZSTD_CCtx* cctx,
2799 const void* dict, size_t dictSize,
2800 ZSTD_parameters params, U64 pledgedSrcSize)
2802 ZSTD_compResetPolicy_e const crp = dictSize ? ZSTDcrp_fullReset : ZSTDcrp_continue;
2803 assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
2804 CHECK_F(ZSTD_resetCCtx_internal(cctx, params, pledgedSrcSize, crp));
2805 return ZSTD_compress_insertDictionary(cctx, dict, dictSize);
2809 /*! ZSTD_compressBegin_advanced() :
2810 * @return : 0, or an error code */
2811 size_t ZSTD_compressBegin_advanced(ZSTD_CCtx* cctx,
2812 const void* dict, size_t dictSize,
2813 ZSTD_parameters params, unsigned long long pledgedSrcSize)
2815 /* compression parameters verification and optimization */
2816 CHECK_F(ZSTD_checkCParams(params.cParams));
2817 return ZSTD_compressBegin_internal(cctx, dict, dictSize, params, pledgedSrcSize);
2821 size_t ZSTD_compressBegin_usingDict(ZSTD_CCtx* cctx, const void* dict, size_t dictSize, int compressionLevel)
2823 ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, dictSize);
2824 return ZSTD_compressBegin_internal(cctx, dict, dictSize, params, 0);
2828 size_t ZSTD_compressBegin(ZSTD_CCtx* cctx, int compressionLevel)
2830 return ZSTD_compressBegin_usingDict(cctx, NULL, 0, compressionLevel);
2834 /*! ZSTD_writeEpilogue() :
2836 * @return : nb of bytes written into dst (or an error code) */
2837 static size_t ZSTD_writeEpilogue(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity)
2839 BYTE* const ostart = (BYTE*)dst;
2843 if (cctx->stage == ZSTDcs_created) return ERROR(stage_wrong); /* init missing */
2845 /* special case : empty frame */
2846 if (cctx->stage == ZSTDcs_init) {
2847 fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, cctx->params, 0, 0);
2848 if (ZSTD_isError(fhSize)) return fhSize;
2849 dstCapacity -= fhSize;
2851 cctx->stage = ZSTDcs_ongoing;
2854 if (cctx->stage != ZSTDcs_ending) {
2855 /* write one last empty block, make it the "last" block */
2856 U32 const cBlockHeader24 = 1 /* last block */ + (((U32)bt_raw)<<1) + 0;
2857 if (dstCapacity<4) return ERROR(dstSize_tooSmall);
2858 MEM_writeLE32(op, cBlockHeader24);
2859 op += ZSTD_blockHeaderSize;
2860 dstCapacity -= ZSTD_blockHeaderSize;
2863 if (cctx->params.fParams.checksumFlag) {
2864 U32 const checksum = (U32) XXH64_digest(&cctx->xxhState);
2865 if (dstCapacity<4) return ERROR(dstSize_tooSmall);
2866 MEM_writeLE32(op, checksum);
2870 cctx->stage = ZSTDcs_created; /* return to "created but no init" status */
2875 size_t ZSTD_compressEnd (ZSTD_CCtx* cctx,
2876 void* dst, size_t dstCapacity,
2877 const void* src, size_t srcSize)
2880 size_t const cSize = ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 1 /* frame mode */, 1 /* last chunk */);
2881 if (ZSTD_isError(cSize)) return cSize;
2882 endResult = ZSTD_writeEpilogue(cctx, (char*)dst + cSize, dstCapacity-cSize);
2883 if (ZSTD_isError(endResult)) return endResult;
2884 if (cctx->params.fParams.contentSizeFlag) { /* control src size */
2885 if (cctx->frameContentSize != cctx->consumedSrcSize) return ERROR(srcSize_wrong);
2887 return cSize + endResult;
2891 static size_t ZSTD_compress_internal (ZSTD_CCtx* cctx,
2892 void* dst, size_t dstCapacity,
2893 const void* src, size_t srcSize,
2894 const void* dict,size_t dictSize,
2895 ZSTD_parameters params)
2897 CHECK_F(ZSTD_compressBegin_internal(cctx, dict, dictSize, params, srcSize));
2898 return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
2901 size_t ZSTD_compress_advanced (ZSTD_CCtx* ctx,
2902 void* dst, size_t dstCapacity,
2903 const void* src, size_t srcSize,
2904 const void* dict,size_t dictSize,
2905 ZSTD_parameters params)
2907 CHECK_F(ZSTD_checkCParams(params.cParams));
2908 return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, dict, dictSize, params);
2911 size_t ZSTD_compress_usingDict(ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize,
2912 const void* dict, size_t dictSize, int compressionLevel)
2914 ZSTD_parameters params = ZSTD_getParams(compressionLevel, srcSize, dict ? dictSize : 0);
2915 params.fParams.contentSizeFlag = 1;
2916 return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, dict, dictSize, params);
2919 size_t ZSTD_compressCCtx (ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel)
2921 return ZSTD_compress_usingDict(ctx, dst, dstCapacity, src, srcSize, NULL, 0, compressionLevel);
2924 size_t ZSTD_compress(void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel)
2928 memset(&ctxBody, 0, sizeof(ctxBody));
2929 memcpy(&ctxBody.customMem, &defaultCustomMem, sizeof(ZSTD_customMem));
2930 result = ZSTD_compressCCtx(&ctxBody, dst, dstCapacity, src, srcSize, compressionLevel);
2931 ZSTD_free(ctxBody.workSpace, defaultCustomMem); /* can't free ctxBody itself, as it's on stack; free only heap content */
2936 /* ===== Dictionary API ===== */
2938 struct ZSTD_CDict_s {
2940 const void* dictContent;
2941 size_t dictContentSize;
2942 ZSTD_CCtx* refContext;
2943 }; /* typedef'd tp ZSTD_CDict within "zstd.h" */
2945 size_t ZSTD_sizeof_CDict(const ZSTD_CDict* cdict)
2947 if (cdict==NULL) return 0; /* support sizeof on NULL */
2948 return ZSTD_sizeof_CCtx(cdict->refContext) + (cdict->dictBuffer ? cdict->dictContentSize : 0) + sizeof(*cdict);
2951 static ZSTD_parameters ZSTD_makeParams(ZSTD_compressionParameters cParams, ZSTD_frameParameters fParams)
2953 ZSTD_parameters params;
2954 params.cParams = cParams;
2955 params.fParams = fParams;
2959 ZSTD_CDict* ZSTD_createCDict_advanced(const void* dictBuffer, size_t dictSize, unsigned byReference,
2960 ZSTD_compressionParameters cParams, ZSTD_customMem customMem)
2962 if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;
2963 if (!customMem.customAlloc || !customMem.customFree) return NULL;
2965 { ZSTD_CDict* const cdict = (ZSTD_CDict*) ZSTD_malloc(sizeof(ZSTD_CDict), customMem);
2966 ZSTD_CCtx* const cctx = ZSTD_createCCtx_advanced(customMem);
2968 if (!cdict || !cctx) {
2969 ZSTD_free(cdict, customMem);
2970 ZSTD_freeCCtx(cctx);
2974 if ((byReference) || (!dictBuffer) || (!dictSize)) {
2975 cdict->dictBuffer = NULL;
2976 cdict->dictContent = dictBuffer;
2978 void* const internalBuffer = ZSTD_malloc(dictSize, customMem);
2979 if (!internalBuffer) { ZSTD_free(cctx, customMem); ZSTD_free(cdict, customMem); return NULL; }
2980 memcpy(internalBuffer, dictBuffer, dictSize);
2981 cdict->dictBuffer = internalBuffer;
2982 cdict->dictContent = internalBuffer;
2985 { ZSTD_frameParameters const fParams = { 0 /* contentSizeFlag */, 0 /* checksumFlag */, 0 /* noDictIDFlag */ }; /* dummy */
2986 ZSTD_parameters const params = ZSTD_makeParams(cParams, fParams);
2987 size_t const errorCode = ZSTD_compressBegin_advanced(cctx, cdict->dictContent, dictSize, params, 0);
2988 if (ZSTD_isError(errorCode)) {
2989 ZSTD_free(cdict->dictBuffer, customMem);
2990 ZSTD_free(cdict, customMem);
2991 ZSTD_freeCCtx(cctx);
2995 cdict->refContext = cctx;
2996 cdict->dictContentSize = dictSize;
3001 ZSTD_CDict* ZSTD_createCDict(const void* dict, size_t dictSize, int compressionLevel)
3003 ZSTD_customMem const allocator = { NULL, NULL, NULL };
3004 ZSTD_compressionParameters cParams = ZSTD_getCParams(compressionLevel, 0, dictSize);
3005 return ZSTD_createCDict_advanced(dict, dictSize, 0, cParams, allocator);
3008 ZSTD_CDict* ZSTD_createCDict_byReference(const void* dict, size_t dictSize, int compressionLevel)
3010 ZSTD_customMem const allocator = { NULL, NULL, NULL };
3011 ZSTD_compressionParameters cParams = ZSTD_getCParams(compressionLevel, 0, dictSize);
3012 return ZSTD_createCDict_advanced(dict, dictSize, 1, cParams, allocator);
3015 size_t ZSTD_freeCDict(ZSTD_CDict* cdict)
3017 if (cdict==NULL) return 0; /* support free on NULL */
3018 { ZSTD_customMem const cMem = cdict->refContext->customMem;
3019 ZSTD_freeCCtx(cdict->refContext);
3020 ZSTD_free(cdict->dictBuffer, cMem);
3021 ZSTD_free(cdict, cMem);
3026 static ZSTD_parameters ZSTD_getParamsFromCDict(const ZSTD_CDict* cdict) {
3027 return ZSTD_getParamsFromCCtx(cdict->refContext);
3030 /* ZSTD_compressBegin_usingCDict_advanced() :
3031 * cdict must be != NULL */
3032 size_t ZSTD_compressBegin_usingCDict_advanced(
3033 ZSTD_CCtx* const cctx, const ZSTD_CDict* const cdict,
3034 ZSTD_frameParameters const fParams, unsigned long long const pledgedSrcSize)
3036 if (cdict==NULL) return ERROR(GENERIC); /* does not support NULL cdict */
3037 DEBUGLOG(5, "ZSTD_compressBegin_usingCDict_advanced : dictIDFlag == %u \n", !fParams.noDictIDFlag);
3038 if (cdict->dictContentSize)
3039 CHECK_F( ZSTD_copyCCtx_internal(cctx, cdict->refContext, fParams, pledgedSrcSize) )
3041 ZSTD_parameters params = cdict->refContext->params;
3042 params.fParams = fParams;
3043 CHECK_F(ZSTD_compressBegin_internal(cctx, NULL, 0, params, pledgedSrcSize));
3048 /* ZSTD_compressBegin_usingCDict() :
3049 * pledgedSrcSize=0 means "unknown"
3050 * if pledgedSrcSize>0, it will enable contentSizeFlag */
3051 size_t ZSTD_compressBegin_usingCDict(ZSTD_CCtx* cctx, const ZSTD_CDict* cdict)
3053 ZSTD_frameParameters const fParams = { 0 /*content*/, 0 /*checksum*/, 0 /*noDictID*/ };
3054 DEBUGLOG(5, "ZSTD_compressBegin_usingCDict : dictIDFlag == %u \n", !fParams.noDictIDFlag);
3055 return ZSTD_compressBegin_usingCDict_advanced(cctx, cdict, fParams, 0);
3058 size_t ZSTD_compress_usingCDict_advanced(ZSTD_CCtx* cctx,
3059 void* dst, size_t dstCapacity,
3060 const void* src, size_t srcSize,
3061 const ZSTD_CDict* cdict, ZSTD_frameParameters fParams)
3063 CHECK_F (ZSTD_compressBegin_usingCDict_advanced(cctx, cdict, fParams, srcSize)); /* will check if cdict != NULL */
3064 return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
3067 /*! ZSTD_compress_usingCDict() :
3068 * Compression using a digested Dictionary.
3069 * Faster startup than ZSTD_compress_usingDict(), recommended when same dictionary is used multiple times.
3070 * Note that compression parameters are decided at CDict creation time
3071 * while frame parameters are hardcoded */
3072 size_t ZSTD_compress_usingCDict(ZSTD_CCtx* cctx,
3073 void* dst, size_t dstCapacity,
3074 const void* src, size_t srcSize,
3075 const ZSTD_CDict* cdict)
3077 ZSTD_frameParameters const fParams = { 1 /*content*/, 0 /*checksum*/, 0 /*noDictID*/ };
3078 return ZSTD_compress_usingCDict_advanced(cctx, dst, dstCapacity, src, srcSize, cdict, fParams);
3083 /* ******************************************************************
3085 ********************************************************************/
3087 typedef enum { zcss_init, zcss_load, zcss_flush, zcss_final } ZSTD_cStreamStage;
3089 struct ZSTD_CStream_s {
3091 ZSTD_CDict* cdictLocal;
3092 const ZSTD_CDict* cdict;
3095 size_t inToCompress;
3097 size_t inBuffTarget;
3101 size_t outBuffContentSize;
3102 size_t outBuffFlushedSize;
3103 ZSTD_cStreamStage stage;
3107 ZSTD_parameters params;
3108 ZSTD_customMem customMem;
3109 }; /* typedef'd to ZSTD_CStream within "zstd.h" */
3111 ZSTD_CStream* ZSTD_createCStream(void)
3113 return ZSTD_createCStream_advanced(defaultCustomMem);
3116 ZSTD_CStream* ZSTD_createCStream_advanced(ZSTD_customMem customMem)
3120 if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;
3121 if (!customMem.customAlloc || !customMem.customFree) return NULL;
3123 zcs = (ZSTD_CStream*)ZSTD_malloc(sizeof(ZSTD_CStream), customMem);
3124 if (zcs==NULL) return NULL;
3125 memset(zcs, 0, sizeof(ZSTD_CStream));
3126 memcpy(&zcs->customMem, &customMem, sizeof(ZSTD_customMem));
3127 zcs->cctx = ZSTD_createCCtx_advanced(customMem);
3128 if (zcs->cctx == NULL) { ZSTD_freeCStream(zcs); return NULL; }
3132 size_t ZSTD_freeCStream(ZSTD_CStream* zcs)
3134 if (zcs==NULL) return 0; /* support free on NULL */
3135 { ZSTD_customMem const cMem = zcs->customMem;
3136 ZSTD_freeCCtx(zcs->cctx);
3138 ZSTD_freeCDict(zcs->cdictLocal);
3139 zcs->cdictLocal = NULL;
3140 ZSTD_free(zcs->inBuff, cMem);
3142 ZSTD_free(zcs->outBuff, cMem);
3143 zcs->outBuff = NULL;
3144 ZSTD_free(zcs, cMem);
3150 /*====== Initialization ======*/
3152 size_t ZSTD_CStreamInSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; }
3154 size_t ZSTD_CStreamOutSize(void)
3156 return ZSTD_compressBound(ZSTD_BLOCKSIZE_ABSOLUTEMAX) + ZSTD_blockHeaderSize + 4 /* 32-bits hash */ ;
3159 static size_t ZSTD_resetCStream_internal(ZSTD_CStream* zcs, unsigned long long pledgedSrcSize)
3161 if (zcs->inBuffSize==0) return ERROR(stage_wrong); /* zcs has not been init at least once => can't reset */
3163 DEBUGLOG(5, "ZSTD_resetCStream_internal : dictIDFlag == %u \n", !zcs->params.fParams.noDictIDFlag);
3165 if (zcs->cdict) CHECK_F(ZSTD_compressBegin_usingCDict_advanced(zcs->cctx, zcs->cdict, zcs->params.fParams, pledgedSrcSize))
3166 else CHECK_F(ZSTD_compressBegin_internal(zcs->cctx, NULL, 0, zcs->params, pledgedSrcSize));
3168 zcs->inToCompress = 0;
3170 zcs->inBuffTarget = zcs->blockSize;
3171 zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0;
3172 zcs->stage = zcss_load;
3173 zcs->frameEnded = 0;
3174 zcs->pledgedSrcSize = pledgedSrcSize;
3175 return 0; /* ready to go */
3178 size_t ZSTD_resetCStream(ZSTD_CStream* zcs, unsigned long long pledgedSrcSize)
3181 zcs->params.fParams.contentSizeFlag = (pledgedSrcSize > 0);
3182 DEBUGLOG(5, "ZSTD_resetCStream : dictIDFlag == %u \n", !zcs->params.fParams.noDictIDFlag);
3183 return ZSTD_resetCStream_internal(zcs, pledgedSrcSize);
3186 /* ZSTD_initCStream_internal() :
3187 * params are supposed validated at this stage
3188 * and zcs->cdict is supposed to be correct */
3189 static size_t ZSTD_initCStream_stage2(ZSTD_CStream* zcs,
3190 const ZSTD_parameters params,
3191 unsigned long long pledgedSrcSize)
3193 assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
3195 /* allocate buffers */
3196 { size_t const neededInBuffSize = (size_t)1 << params.cParams.windowLog;
3197 if (zcs->inBuffSize < neededInBuffSize) {
3198 zcs->inBuffSize = 0;
3199 ZSTD_free(zcs->inBuff, zcs->customMem);
3200 zcs->inBuff = (char*) ZSTD_malloc(neededInBuffSize, zcs->customMem);
3201 if (zcs->inBuff == NULL) return ERROR(memory_allocation);
3202 zcs->inBuffSize = neededInBuffSize;
3204 zcs->blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, neededInBuffSize);
3206 if (zcs->outBuffSize < ZSTD_compressBound(zcs->blockSize)+1) {
3207 size_t const outBuffSize = ZSTD_compressBound(zcs->blockSize)+1;
3208 zcs->outBuffSize = 0;
3209 ZSTD_free(zcs->outBuff, zcs->customMem);
3210 zcs->outBuff = (char*) ZSTD_malloc(outBuffSize, zcs->customMem);
3211 if (zcs->outBuff == NULL) return ERROR(memory_allocation);
3212 zcs->outBuffSize = outBuffSize;
3215 zcs->checksum = params.fParams.checksumFlag > 0;
3216 zcs->params = params;
3218 DEBUGLOG(5, "ZSTD_initCStream_stage2 : dictIDFlag == %u \n", !params.fParams.noDictIDFlag);
3219 return ZSTD_resetCStream_internal(zcs, pledgedSrcSize);
3222 /* ZSTD_initCStream_usingCDict_advanced() :
3223 * same as ZSTD_initCStream_usingCDict(), with control over frame parameters */
3224 size_t ZSTD_initCStream_usingCDict_advanced(ZSTD_CStream* zcs, const ZSTD_CDict* cdict, unsigned long long pledgedSrcSize, ZSTD_frameParameters fParams)
3226 if (!cdict) return ERROR(GENERIC); /* cannot handle NULL cdict (does not know what to do) */
3227 { ZSTD_parameters params = ZSTD_getParamsFromCDict(cdict);
3228 params.fParams = fParams;
3230 return ZSTD_initCStream_stage2(zcs, params, pledgedSrcSize);
3234 /* note : cdict must outlive compression session */
3235 size_t ZSTD_initCStream_usingCDict(ZSTD_CStream* zcs, const ZSTD_CDict* cdict)
3237 ZSTD_frameParameters const fParams = { 0 /* content */, 0 /* checksum */, 0 /* noDictID */ };
3238 return ZSTD_initCStream_usingCDict_advanced(zcs, cdict, 0, fParams);
3241 static size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs,
3242 const void* dict, size_t dictSize,
3243 ZSTD_parameters params, unsigned long long pledgedSrcSize)
3245 assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
3248 if (dict && dictSize >= 8) {
3249 ZSTD_freeCDict(zcs->cdictLocal);
3250 zcs->cdictLocal = ZSTD_createCDict_advanced(dict, dictSize, 0 /* copy */, params.cParams, zcs->customMem);
3251 if (zcs->cdictLocal == NULL) return ERROR(memory_allocation);
3252 zcs->cdict = zcs->cdictLocal;
3255 DEBUGLOG(5, "ZSTD_initCStream_internal : dictIDFlag == %u \n", !params.fParams.noDictIDFlag);
3256 return ZSTD_initCStream_stage2(zcs, params, pledgedSrcSize);
3259 size_t ZSTD_initCStream_advanced(ZSTD_CStream* zcs,
3260 const void* dict, size_t dictSize,
3261 ZSTD_parameters params, unsigned long long pledgedSrcSize)
3263 CHECK_F( ZSTD_checkCParams(params.cParams) );
3264 DEBUGLOG(5, "ZSTD_initCStream_advanced : dictIDFlag == %u \n", !params.fParams.noDictIDFlag);
3265 return ZSTD_initCStream_internal(zcs, dict, dictSize, params, pledgedSrcSize);
3268 size_t ZSTD_initCStream_usingDict(ZSTD_CStream* zcs, const void* dict, size_t dictSize, int compressionLevel)
3270 ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, dictSize);
3271 return ZSTD_initCStream_internal(zcs, dict, dictSize, params, 0);
3274 size_t ZSTD_initCStream_srcSize(ZSTD_CStream* zcs, int compressionLevel, unsigned long long pledgedSrcSize)
3276 ZSTD_parameters params = ZSTD_getParams(compressionLevel, pledgedSrcSize, 0);
3277 params.fParams.contentSizeFlag = (pledgedSrcSize>0);
3278 return ZSTD_initCStream_internal(zcs, NULL, 0, params, pledgedSrcSize);
3281 size_t ZSTD_initCStream(ZSTD_CStream* zcs, int compressionLevel)
3283 ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, 0);
3284 return ZSTD_initCStream_internal(zcs, NULL, 0, params, 0);
3287 size_t ZSTD_sizeof_CStream(const ZSTD_CStream* zcs)
3289 if (zcs==NULL) return 0; /* support sizeof on NULL */
3290 return sizeof(*zcs) + ZSTD_sizeof_CCtx(zcs->cctx) + ZSTD_sizeof_CDict(zcs->cdictLocal) + zcs->outBuffSize + zcs->inBuffSize;
3293 /*====== Compression ======*/
3295 typedef enum { zsf_gather, zsf_flush, zsf_end } ZSTD_flush_e;
3297 MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3299 size_t const length = MIN(dstCapacity, srcSize);
3300 memcpy(dst, src, length);
3304 static size_t ZSTD_compressStream_generic(ZSTD_CStream* zcs,
3305 void* dst, size_t* dstCapacityPtr,
3306 const void* src, size_t* srcSizePtr,
3307 ZSTD_flush_e const flush)
3309 U32 someMoreWork = 1;
3310 const char* const istart = (const char*)src;
3311 const char* const iend = istart + *srcSizePtr;
3312 const char* ip = istart;
3313 char* const ostart = (char*)dst;
3314 char* const oend = ostart + *dstCapacityPtr;
3317 while (someMoreWork) {
3320 case zcss_init: return ERROR(init_missing); /* call ZBUFF_compressInit() first ! */
3323 /* complete inBuffer */
3324 { size_t const toLoad = zcs->inBuffTarget - zcs->inBuffPos;
3325 size_t const loaded = ZSTD_limitCopy(zcs->inBuff + zcs->inBuffPos, toLoad, ip, iend-ip);
3326 zcs->inBuffPos += loaded;
3328 if ( (zcs->inBuffPos==zcs->inToCompress) || (!flush && (toLoad != loaded)) ) {
3329 someMoreWork = 0; break; /* not enough input to get a full block : stop there, wait for more */
3331 /* compress current block (note : this stage cannot be stopped in the middle) */
3334 size_t const iSize = zcs->inBuffPos - zcs->inToCompress;
3335 size_t oSize = oend-op;
3336 if (oSize >= ZSTD_compressBound(iSize))
3337 cDst = op; /* compress directly into output buffer (avoid flush stage) */
3339 cDst = zcs->outBuff, oSize = zcs->outBuffSize;
3340 cSize = (flush == zsf_end) ?
3341 ZSTD_compressEnd(zcs->cctx, cDst, oSize, zcs->inBuff + zcs->inToCompress, iSize) :
3342 ZSTD_compressContinue(zcs->cctx, cDst, oSize, zcs->inBuff + zcs->inToCompress, iSize);
3343 if (ZSTD_isError(cSize)) return cSize;
3344 if (flush == zsf_end) zcs->frameEnded = 1;
3345 /* prepare next block */
3346 zcs->inBuffTarget = zcs->inBuffPos + zcs->blockSize;
3347 if (zcs->inBuffTarget > zcs->inBuffSize)
3348 zcs->inBuffPos = 0, zcs->inBuffTarget = zcs->blockSize; /* note : inBuffSize >= blockSize */
3349 zcs->inToCompress = zcs->inBuffPos;
3350 if (cDst == op) { op += cSize; break; } /* no need to flush */
3351 zcs->outBuffContentSize = cSize;
3352 zcs->outBuffFlushedSize = 0;
3353 zcs->stage = zcss_flush; /* pass-through to flush stage */
3357 { size_t const toFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3358 size_t const flushed = ZSTD_limitCopy(op, oend-op, zcs->outBuff + zcs->outBuffFlushedSize, toFlush);
3360 zcs->outBuffFlushedSize += flushed;
3361 if (toFlush!=flushed) { someMoreWork = 0; break; } /* dst too small to store flushed data : stop there */
3362 zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0;
3363 zcs->stage = zcss_load;
3368 someMoreWork = 0; /* do nothing */
3372 return ERROR(GENERIC); /* impossible */
3376 *srcSizePtr = ip - istart;
3377 *dstCapacityPtr = op - ostart;
3378 if (zcs->frameEnded) return 0;
3379 { size_t hintInSize = zcs->inBuffTarget - zcs->inBuffPos;
3380 if (hintInSize==0) hintInSize = zcs->blockSize;
3385 size_t ZSTD_compressStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output, ZSTD_inBuffer* input)
3387 size_t sizeRead = input->size - input->pos;
3388 size_t sizeWritten = output->size - output->pos;
3389 size_t const result = ZSTD_compressStream_generic(zcs,
3390 (char*)(output->dst) + output->pos, &sizeWritten,
3391 (const char*)(input->src) + input->pos, &sizeRead, zsf_gather);
3392 input->pos += sizeRead;
3393 output->pos += sizeWritten;
3398 /*====== Finalize ======*/
3400 /*! ZSTD_flushStream() :
3401 * @return : amount of data remaining to flush */
3402 size_t ZSTD_flushStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output)
3405 size_t sizeWritten = output->size - output->pos;
3406 size_t const result = ZSTD_compressStream_generic(zcs,
3407 (char*)(output->dst) + output->pos, &sizeWritten,
3408 &srcSize, &srcSize, /* use a valid src address instead of NULL */
3410 output->pos += sizeWritten;
3411 if (ZSTD_isError(result)) return result;
3412 return zcs->outBuffContentSize - zcs->outBuffFlushedSize; /* remaining to flush */
3416 size_t ZSTD_endStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output)
3418 BYTE* const ostart = (BYTE*)(output->dst) + output->pos;
3419 BYTE* const oend = (BYTE*)(output->dst) + output->size;
3422 if (zcs->stage != zcss_final) {
3423 /* flush whatever remains */
3425 size_t sizeWritten = output->size - output->pos;
3426 size_t const notEnded = ZSTD_compressStream_generic(zcs, ostart, &sizeWritten,
3427 &srcSize /* use a valid src address instead of NULL */, &srcSize, zsf_end);
3428 size_t const remainingToFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3430 if (remainingToFlush) {
3431 output->pos += sizeWritten;
3432 return remainingToFlush + ZSTD_BLOCKHEADERSIZE /* final empty block */ + (zcs->checksum * 4);
3434 /* create epilogue */
3435 zcs->stage = zcss_final;
3436 zcs->outBuffContentSize = !notEnded ? 0 :
3437 /* write epilogue, including final empty block, into outBuff */
3438 ZSTD_compressEnd(zcs->cctx, zcs->outBuff, zcs->outBuffSize, NULL, 0);
3439 if (ZSTD_isError(zcs->outBuffContentSize)) return zcs->outBuffContentSize;
3442 /* flush epilogue */
3443 { size_t const toFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3444 size_t const flushed = ZSTD_limitCopy(op, oend-op, zcs->outBuff + zcs->outBuffFlushedSize, toFlush);
3446 zcs->outBuffFlushedSize += flushed;
3447 output->pos += op-ostart;
3448 if (toFlush==flushed) zcs->stage = zcss_init; /* end reached */
3449 return toFlush - flushed;
3455 /*-===== Pre-defined compression levels =====-*/
3457 #define ZSTD_DEFAULT_CLEVEL 1
3458 #define ZSTD_MAX_CLEVEL 22
3459 int ZSTD_maxCLevel(void) { return ZSTD_MAX_CLEVEL; }
3461 static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEVEL+1] = {
3463 /* W, C, H, S, L, TL, strat */
3464 { 18, 12, 12, 1, 7, 16, ZSTD_fast }, /* level 0 - never used */
3465 { 19, 13, 14, 1, 7, 16, ZSTD_fast }, /* level 1 */
3466 { 19, 15, 16, 1, 6, 16, ZSTD_fast }, /* level 2 */
3467 { 20, 16, 17, 1, 5, 16, ZSTD_dfast }, /* level 3.*/
3468 { 20, 18, 18, 1, 5, 16, ZSTD_dfast }, /* level 4.*/
3469 { 20, 15, 18, 3, 5, 16, ZSTD_greedy }, /* level 5 */
3470 { 21, 16, 19, 2, 5, 16, ZSTD_lazy }, /* level 6 */
3471 { 21, 17, 20, 3, 5, 16, ZSTD_lazy }, /* level 7 */
3472 { 21, 18, 20, 3, 5, 16, ZSTD_lazy2 }, /* level 8 */
3473 { 21, 20, 20, 3, 5, 16, ZSTD_lazy2 }, /* level 9 */
3474 { 21, 19, 21, 4, 5, 16, ZSTD_lazy2 }, /* level 10 */
3475 { 22, 20, 22, 4, 5, 16, ZSTD_lazy2 }, /* level 11 */
3476 { 22, 20, 22, 5, 5, 16, ZSTD_lazy2 }, /* level 12 */
3477 { 22, 21, 22, 5, 5, 16, ZSTD_lazy2 }, /* level 13 */
3478 { 22, 21, 22, 6, 5, 16, ZSTD_lazy2 }, /* level 14 */
3479 { 22, 21, 21, 5, 5, 16, ZSTD_btlazy2 }, /* level 15 */
3480 { 23, 22, 22, 5, 5, 16, ZSTD_btlazy2 }, /* level 16 */
3481 { 23, 21, 22, 4, 5, 24, ZSTD_btopt }, /* level 17 */
3482 { 23, 22, 22, 5, 4, 32, ZSTD_btopt }, /* level 18 */
3483 { 23, 23, 22, 6, 3, 48, ZSTD_btopt }, /* level 19 */
3484 { 25, 25, 23, 7, 3, 64, ZSTD_btopt2 }, /* level 20 */
3485 { 26, 26, 23, 7, 3,256, ZSTD_btopt2 }, /* level 21 */
3486 { 27, 27, 25, 9, 3,512, ZSTD_btopt2 }, /* level 22 */
3488 { /* for srcSize <= 256 KB */
3489 /* W, C, H, S, L, T, strat */
3490 { 0, 0, 0, 0, 0, 0, ZSTD_fast }, /* level 0 - not used */
3491 { 18, 13, 14, 1, 6, 8, ZSTD_fast }, /* level 1 */
3492 { 18, 14, 13, 1, 5, 8, ZSTD_dfast }, /* level 2 */
3493 { 18, 16, 15, 1, 5, 8, ZSTD_dfast }, /* level 3 */
3494 { 18, 15, 17, 1, 5, 8, ZSTD_greedy }, /* level 4.*/
3495 { 18, 16, 17, 4, 5, 8, ZSTD_greedy }, /* level 5.*/
3496 { 18, 16, 17, 3, 5, 8, ZSTD_lazy }, /* level 6.*/
3497 { 18, 17, 17, 4, 4, 8, ZSTD_lazy }, /* level 7 */
3498 { 18, 17, 17, 4, 4, 8, ZSTD_lazy2 }, /* level 8 */
3499 { 18, 17, 17, 5, 4, 8, ZSTD_lazy2 }, /* level 9 */
3500 { 18, 17, 17, 6, 4, 8, ZSTD_lazy2 }, /* level 10 */
3501 { 18, 18, 17, 6, 4, 8, ZSTD_lazy2 }, /* level 11.*/
3502 { 18, 18, 17, 7, 4, 8, ZSTD_lazy2 }, /* level 12.*/
3503 { 18, 19, 17, 6, 4, 8, ZSTD_btlazy2 }, /* level 13 */
3504 { 18, 18, 18, 4, 4, 16, ZSTD_btopt }, /* level 14.*/
3505 { 18, 18, 18, 4, 3, 16, ZSTD_btopt }, /* level 15.*/
3506 { 18, 19, 18, 6, 3, 32, ZSTD_btopt }, /* level 16.*/
3507 { 18, 19, 18, 8, 3, 64, ZSTD_btopt }, /* level 17.*/
3508 { 18, 19, 18, 9, 3,128, ZSTD_btopt }, /* level 18.*/
3509 { 18, 19, 18, 10, 3,256, ZSTD_btopt }, /* level 19.*/
3510 { 18, 19, 18, 11, 3,512, ZSTD_btopt2 }, /* level 20.*/
3511 { 18, 19, 18, 12, 3,512, ZSTD_btopt2 }, /* level 21.*/
3512 { 18, 19, 18, 13, 3,512, ZSTD_btopt2 }, /* level 22.*/
3514 { /* for srcSize <= 128 KB */
3515 /* W, C, H, S, L, T, strat */
3516 { 17, 12, 12, 1, 7, 8, ZSTD_fast }, /* level 0 - not used */
3517 { 17, 12, 13, 1, 6, 8, ZSTD_fast }, /* level 1 */
3518 { 17, 13, 16, 1, 5, 8, ZSTD_fast }, /* level 2 */
3519 { 17, 16, 16, 2, 5, 8, ZSTD_dfast }, /* level 3 */
3520 { 17, 13, 15, 3, 4, 8, ZSTD_greedy }, /* level 4 */
3521 { 17, 15, 17, 4, 4, 8, ZSTD_greedy }, /* level 5 */
3522 { 17, 16, 17, 3, 4, 8, ZSTD_lazy }, /* level 6 */
3523 { 17, 15, 17, 4, 4, 8, ZSTD_lazy2 }, /* level 7 */
3524 { 17, 17, 17, 4, 4, 8, ZSTD_lazy2 }, /* level 8 */
3525 { 17, 17, 17, 5, 4, 8, ZSTD_lazy2 }, /* level 9 */
3526 { 17, 17, 17, 6, 4, 8, ZSTD_lazy2 }, /* level 10 */
3527 { 17, 17, 17, 7, 4, 8, ZSTD_lazy2 }, /* level 11 */
3528 { 17, 17, 17, 8, 4, 8, ZSTD_lazy2 }, /* level 12 */
3529 { 17, 18, 17, 6, 4, 8, ZSTD_btlazy2 }, /* level 13.*/
3530 { 17, 17, 17, 7, 3, 8, ZSTD_btopt }, /* level 14.*/
3531 { 17, 17, 17, 7, 3, 16, ZSTD_btopt }, /* level 15.*/
3532 { 17, 18, 17, 7, 3, 32, ZSTD_btopt }, /* level 16.*/
3533 { 17, 18, 17, 7, 3, 64, ZSTD_btopt }, /* level 17.*/
3534 { 17, 18, 17, 7, 3,256, ZSTD_btopt }, /* level 18.*/
3535 { 17, 18, 17, 8, 3,256, ZSTD_btopt }, /* level 19.*/
3536 { 17, 18, 17, 9, 3,256, ZSTD_btopt2 }, /* level 20.*/
3537 { 17, 18, 17, 10, 3,256, ZSTD_btopt2 }, /* level 21.*/
3538 { 17, 18, 17, 11, 3,512, ZSTD_btopt2 }, /* level 22.*/
3540 { /* for srcSize <= 16 KB */
3541 /* W, C, H, S, L, T, strat */
3542 { 14, 12, 12, 1, 7, 6, ZSTD_fast }, /* level 0 - not used */
3543 { 14, 14, 14, 1, 6, 6, ZSTD_fast }, /* level 1 */
3544 { 14, 14, 14, 1, 4, 6, ZSTD_fast }, /* level 2 */
3545 { 14, 14, 14, 1, 4, 6, ZSTD_dfast }, /* level 3.*/
3546 { 14, 14, 14, 4, 4, 6, ZSTD_greedy }, /* level 4.*/
3547 { 14, 14, 14, 3, 4, 6, ZSTD_lazy }, /* level 5.*/
3548 { 14, 14, 14, 4, 4, 6, ZSTD_lazy2 }, /* level 6 */
3549 { 14, 14, 14, 5, 4, 6, ZSTD_lazy2 }, /* level 7 */
3550 { 14, 14, 14, 6, 4, 6, ZSTD_lazy2 }, /* level 8.*/
3551 { 14, 15, 14, 6, 4, 6, ZSTD_btlazy2 }, /* level 9.*/
3552 { 14, 15, 14, 3, 3, 6, ZSTD_btopt }, /* level 10.*/
3553 { 14, 15, 14, 6, 3, 8, ZSTD_btopt }, /* level 11.*/
3554 { 14, 15, 14, 6, 3, 16, ZSTD_btopt }, /* level 12.*/
3555 { 14, 15, 14, 6, 3, 24, ZSTD_btopt }, /* level 13.*/
3556 { 14, 15, 15, 6, 3, 48, ZSTD_btopt }, /* level 14.*/
3557 { 14, 15, 15, 6, 3, 64, ZSTD_btopt }, /* level 15.*/
3558 { 14, 15, 15, 6, 3, 96, ZSTD_btopt }, /* level 16.*/
3559 { 14, 15, 15, 6, 3,128, ZSTD_btopt }, /* level 17.*/
3560 { 14, 15, 15, 6, 3,256, ZSTD_btopt }, /* level 18.*/
3561 { 14, 15, 15, 7, 3,256, ZSTD_btopt }, /* level 19.*/
3562 { 14, 15, 15, 8, 3,256, ZSTD_btopt2 }, /* level 20.*/
3563 { 14, 15, 15, 9, 3,256, ZSTD_btopt2 }, /* level 21.*/
3564 { 14, 15, 15, 10, 3,256, ZSTD_btopt2 }, /* level 22.*/
3568 /*! ZSTD_getCParams() :
3569 * @return ZSTD_compressionParameters structure for a selected compression level, `srcSize` and `dictSize`.
3570 * Size values are optional, provide 0 if not known or unused */
3571 ZSTD_compressionParameters ZSTD_getCParams(int compressionLevel, unsigned long long srcSize, size_t dictSize)
3573 ZSTD_compressionParameters cp;
3574 size_t const addedSize = srcSize ? 0 : 500;
3575 U64 const rSize = srcSize+dictSize ? srcSize+dictSize+addedSize : (U64)-1;
3576 U32 const tableID = (rSize <= 256 KB) + (rSize <= 128 KB) + (rSize <= 16 KB); /* intentional underflow for srcSizeHint == 0 */
3577 if (compressionLevel <= 0) compressionLevel = ZSTD_DEFAULT_CLEVEL; /* 0 == default; no negative compressionLevel yet */
3578 if (compressionLevel > ZSTD_MAX_CLEVEL) compressionLevel = ZSTD_MAX_CLEVEL;
3579 cp = ZSTD_defaultCParameters[tableID][compressionLevel];
3580 if (MEM_32bits()) { /* auto-correction, for 32-bits mode */
3581 if (cp.windowLog > ZSTD_WINDOWLOG_MAX) cp.windowLog = ZSTD_WINDOWLOG_MAX;
3582 if (cp.chainLog > ZSTD_CHAINLOG_MAX) cp.chainLog = ZSTD_CHAINLOG_MAX;
3583 if (cp.hashLog > ZSTD_HASHLOG_MAX) cp.hashLog = ZSTD_HASHLOG_MAX;
3585 cp = ZSTD_adjustCParams(cp, srcSize, dictSize);
3589 /*! ZSTD_getParams() :
3590 * same as ZSTD_getCParams(), but @return a `ZSTD_parameters` object (instead of `ZSTD_compressionParameters`).
3591 * All fields of `ZSTD_frameParameters` are set to default (0) */
3592 ZSTD_parameters ZSTD_getParams(int compressionLevel, unsigned long long srcSize, size_t dictSize) {
3593 ZSTD_parameters params;
3594 ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, srcSize, dictSize);
3595 memset(¶ms, 0, sizeof(params));
3596 params.cParams = cParams;