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 #ifndef ZSTD_CLEVEL_DEFAULT
15 # define ZSTD_CLEVEL_DEFAULT 3
19 /*-*************************************
21 ***************************************/
22 #include <string.h> /* memset */
24 #define FSE_STATIC_LINKING_ONLY /* FSE_encodeSymbol */
26 #define HUF_STATIC_LINKING_ONLY
28 #include "zstd_internal.h" /* includes zstd.h */
29 #include "zstdmt_compress.h"
32 /*-*************************************
34 ***************************************/
35 static const U32 g_searchStrength = 8; /* control skip over incompressible data */
36 #define HASH_READ_SIZE 8
37 typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;
39 /* entropy tables always have same size */
40 static size_t const hufCTable_size = HUF_CTABLE_SIZE(255);
41 static size_t const litlengthCTable_size = FSE_CTABLE_SIZE(LLFSELog, MaxLL);
42 static size_t const offcodeCTable_size = FSE_CTABLE_SIZE(OffFSELog, MaxOff);
43 static size_t const matchlengthCTable_size = FSE_CTABLE_SIZE(MLFSELog, MaxML);
44 static size_t const entropyScratchSpace_size = HUF_WORKSPACE_SIZE;
47 /*-*************************************
49 ***************************************/
50 size_t ZSTD_compressBound(size_t srcSize) {
51 size_t const lowLimit = 256 KB;
52 size_t const margin = (srcSize < lowLimit) ? (lowLimit-srcSize) >> 12 : 0; /* from 64 to 0 */
53 return srcSize + (srcSize >> 8) + margin;
57 /*-*************************************
59 ***************************************/
60 static void ZSTD_resetSeqStore(seqStore_t* ssPtr)
62 ssPtr->lit = ssPtr->litStart;
63 ssPtr->sequences = ssPtr->sequencesStart;
64 ssPtr->longLengthID = 0;
68 /*-*************************************
69 * Context memory management
70 ***************************************/
71 typedef enum { zcss_init=0, zcss_load, zcss_flush } ZSTD_cStreamStage;
75 const void* dictContent;
76 size_t dictContentSize;
77 ZSTD_CCtx* refContext;
78 }; /* typedef'd to ZSTD_CDict within "zstd.h" */
81 const BYTE* nextSrc; /* next block here to continue on current prefix */
82 const BYTE* base; /* All regular indexes relative to this position */
83 const BYTE* dictBase; /* extDict indexes relative to this position */
84 U32 dictLimit; /* below that point, need extDict */
85 U32 lowLimit; /* below that point, no more data */
86 U32 nextToUpdate; /* index from which to continue dictionary update */
87 U32 nextToUpdate3; /* index from which to continue dictionary update */
88 U32 hashLog3; /* dispatch table : larger == faster, more memory */
89 U32 loadedDictEnd; /* index of end of dictionary */
90 U32 forceWindow; /* force back-references to respect limit of 1<<wLog, even for dictionary */
91 ZSTD_compressionStage_e stage;
92 U32 rep[ZSTD_REP_NUM];
93 U32 repToConfirm[ZSTD_REP_NUM];
96 ZSTD_parameters requestedParams;
97 ZSTD_parameters appliedParams;
101 U64 pledgedSrcSizePlusOne; /* this way, 0 (default) == unknown */
103 XXH64_state_t xxhState;
104 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;
127 size_t outBuffContentSize;
128 size_t outBuffFlushedSize;
129 ZSTD_cStreamStage streamStage;
133 ZSTD_dictMode_e dictMode; /* select restricting dictionary to "rawContent" or "fullDict" only */
134 U32 dictContentByRef;
135 ZSTD_CDict* cdictLocal;
136 const ZSTD_CDict* cdict;
140 /* Multi-threading */
146 ZSTD_CCtx* ZSTD_createCCtx(void)
148 return ZSTD_createCCtx_advanced(ZSTD_defaultCMem);
151 ZSTD_CCtx* ZSTD_createCCtx_advanced(ZSTD_customMem customMem)
155 if (!customMem.customAlloc ^ !customMem.customFree) return NULL;
157 cctx = (ZSTD_CCtx*) ZSTD_calloc(sizeof(ZSTD_CCtx), customMem);
158 if (!cctx) return NULL;
159 cctx->customMem = customMem;
160 cctx->compressionLevel = ZSTD_CLEVEL_DEFAULT;
161 ZSTD_STATIC_ASSERT(zcss_init==0);
162 ZSTD_STATIC_ASSERT(ZSTD_CONTENTSIZE_UNKNOWN==(0ULL - 1));
166 ZSTD_CCtx* ZSTD_initStaticCCtx(void *workspace, size_t workspaceSize)
168 ZSTD_CCtx* cctx = (ZSTD_CCtx*) workspace;
169 if (workspaceSize <= sizeof(ZSTD_CCtx)) return NULL; /* minimum size */
170 if ((size_t)workspace & 7) return NULL; /* must be 8-aligned */
171 memset(workspace, 0, workspaceSize); /* may be a bit generous, could memset be smaller ? */
172 cctx->staticSize = workspaceSize;
173 cctx->workSpace = (void*)(cctx+1);
174 cctx->workSpaceSize = workspaceSize - sizeof(ZSTD_CCtx);
176 /* entropy space (never moves) */
177 /* note : this code should be shared with resetCCtx, rather than copy/pasted */
178 { void* ptr = cctx->workSpace;
179 cctx->hufCTable = (HUF_CElt*)ptr;
180 ptr = (char*)cctx->hufCTable + hufCTable_size;
181 cctx->offcodeCTable = (FSE_CTable*) ptr;
182 ptr = (char*)ptr + offcodeCTable_size;
183 cctx->matchlengthCTable = (FSE_CTable*) ptr;
184 ptr = (char*)ptr + matchlengthCTable_size;
185 cctx->litlengthCTable = (FSE_CTable*) ptr;
186 ptr = (char*)ptr + litlengthCTable_size;
187 assert(((size_t)ptr & 3) == 0); /* ensure correct alignment */
188 cctx->entropyScratchSpace = (unsigned*) ptr;
194 size_t ZSTD_freeCCtx(ZSTD_CCtx* cctx)
196 if (cctx==NULL) return 0; /* support free on NULL */
197 if (cctx->staticSize) return ERROR(memory_allocation); /* not compatible with static CCtx */
198 ZSTD_free(cctx->workSpace, cctx->customMem);
199 cctx->workSpace = NULL;
200 ZSTD_freeCDict(cctx->cdictLocal);
201 cctx->cdictLocal = NULL;
202 ZSTDMT_freeCCtx(cctx->mtctx);
204 ZSTD_free(cctx, cctx->customMem);
205 return 0; /* reserved as a potential error code in the future */
208 size_t ZSTD_sizeof_CCtx(const ZSTD_CCtx* cctx)
210 if (cctx==NULL) return 0; /* support sizeof on NULL */
211 DEBUGLOG(5, "sizeof(*cctx) : %u", (U32)sizeof(*cctx));
212 DEBUGLOG(5, "workSpaceSize : %u", (U32)cctx->workSpaceSize);
213 DEBUGLOG(5, "streaming buffers : %u", (U32)(cctx->outBuffSize + cctx->inBuffSize));
214 DEBUGLOG(5, "inner MTCTX : %u", (U32)ZSTDMT_sizeof_CCtx(cctx->mtctx));
215 return sizeof(*cctx) + cctx->workSpaceSize
216 + ZSTD_sizeof_CDict(cctx->cdictLocal)
217 + cctx->outBuffSize + cctx->inBuffSize
218 + ZSTDMT_sizeof_CCtx(cctx->mtctx);
221 size_t ZSTD_sizeof_CStream(const ZSTD_CStream* zcs)
223 return ZSTD_sizeof_CCtx(zcs); /* same object */
226 /* private API call, for dictBuilder only */
227 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx) { return &(ctx->seqStore); }
229 static ZSTD_parameters ZSTD_getParamsFromCCtx(const ZSTD_CCtx* cctx) { return cctx->appliedParams; }
231 /* older variant; will be deprecated */
232 size_t ZSTD_setCCtxParameter(ZSTD_CCtx* cctx, ZSTD_CCtxParameter param, unsigned value)
236 case ZSTD_p_forceWindow : cctx->forceWindow = value>0; cctx->loadedDictEnd = 0; return 0;
237 ZSTD_STATIC_ASSERT(ZSTD_dm_auto==0);
238 ZSTD_STATIC_ASSERT(ZSTD_dm_rawContent==1);
239 case ZSTD_p_forceRawDict : cctx->dictMode = (ZSTD_dictMode_e)(value>0); return 0;
240 default: return ERROR(parameter_unknown);
245 #define ZSTD_CLEVEL_CUSTOM 999
246 static void ZSTD_cLevelToCParams(ZSTD_CCtx* cctx)
248 if (cctx->compressionLevel==ZSTD_CLEVEL_CUSTOM) return;
249 cctx->requestedParams.cParams = ZSTD_getCParams(cctx->compressionLevel,
250 cctx->pledgedSrcSizePlusOne-1, 0);
251 cctx->compressionLevel = ZSTD_CLEVEL_CUSTOM;
254 #define CLAMPCHECK(val,min,max) { \
255 if (((val)<(min)) | ((val)>(max))) { \
256 return ERROR(compressionParameter_outOfBound); \
259 size_t ZSTD_CCtx_setParameter(ZSTD_CCtx* cctx, ZSTD_cParameter param, unsigned value)
261 if (cctx->streamStage != zcss_init) return ERROR(stage_wrong);
265 case ZSTD_p_compressionLevel :
266 if ((int)value > ZSTD_maxCLevel()) value = ZSTD_maxCLevel(); /* cap max compression level */
267 if (value == 0) return 0; /* special value : 0 means "don't change anything" */
268 if (cctx->cdict) return ERROR(stage_wrong);
269 cctx->compressionLevel = value;
272 case ZSTD_p_windowLog :
273 DEBUGLOG(5, "setting ZSTD_p_windowLog = %u (cdict:%u)",
274 value, (cctx->cdict!=NULL));
275 if (value == 0) return 0; /* special value : 0 means "don't change anything" */
276 if (cctx->cdict) return ERROR(stage_wrong);
277 CLAMPCHECK(value, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);
278 ZSTD_cLevelToCParams(cctx);
279 cctx->requestedParams.cParams.windowLog = value;
282 case ZSTD_p_hashLog :
283 if (value == 0) return 0; /* special value : 0 means "don't change anything" */
284 if (cctx->cdict) return ERROR(stage_wrong);
285 CLAMPCHECK(value, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX);
286 ZSTD_cLevelToCParams(cctx);
287 cctx->requestedParams.cParams.hashLog = value;
290 case ZSTD_p_chainLog :
291 if (value == 0) return 0; /* special value : 0 means "don't change anything" */
292 if (cctx->cdict) return ERROR(stage_wrong);
293 CLAMPCHECK(value, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX);
294 ZSTD_cLevelToCParams(cctx);
295 cctx->requestedParams.cParams.chainLog = value;
298 case ZSTD_p_searchLog :
299 if (value == 0) return 0; /* special value : 0 means "don't change anything" */
300 if (cctx->cdict) return ERROR(stage_wrong);
301 CLAMPCHECK(value, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX);
302 ZSTD_cLevelToCParams(cctx);
303 cctx->requestedParams.cParams.searchLog = value;
306 case ZSTD_p_minMatch :
307 if (value == 0) return 0; /* special value : 0 means "don't change anything" */
308 if (cctx->cdict) return ERROR(stage_wrong);
309 CLAMPCHECK(value, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX);
310 ZSTD_cLevelToCParams(cctx);
311 cctx->requestedParams.cParams.searchLength = value;
314 case ZSTD_p_targetLength :
315 if (value == 0) return 0; /* special value : 0 means "don't change anything" */
316 if (cctx->cdict) return ERROR(stage_wrong);
317 CLAMPCHECK(value, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX);
318 ZSTD_cLevelToCParams(cctx);
319 cctx->requestedParams.cParams.targetLength = value;
322 case ZSTD_p_compressionStrategy :
323 if (value == 0) return 0; /* special value : 0 means "don't change anything" */
324 if (cctx->cdict) return ERROR(stage_wrong);
325 CLAMPCHECK(value, (unsigned)ZSTD_fast, (unsigned)ZSTD_btultra);
326 ZSTD_cLevelToCParams(cctx);
327 cctx->requestedParams.cParams.strategy = (ZSTD_strategy)value;
330 case ZSTD_p_contentSizeFlag :
331 DEBUGLOG(5, "set content size flag = %u", (value>0));
332 /* Content size written in frame header _when known_ (default:1) */
333 cctx->requestedParams.fParams.contentSizeFlag = value>0;
336 case ZSTD_p_checksumFlag :
337 /* A 32-bits content checksum will be calculated and written at end of frame (default:0) */
338 cctx->requestedParams.fParams.checksumFlag = value>0;
341 case ZSTD_p_dictIDFlag : /* When applicable, dictionary's dictID is provided in frame header (default:1) */
342 DEBUGLOG(5, "set dictIDFlag = %u", (value>0));
343 cctx->requestedParams.fParams.noDictIDFlag = (value==0);
346 /* Dictionary parameters */
347 case ZSTD_p_dictMode :
348 if (cctx->cdict) return ERROR(stage_wrong); /* must be set before loading */
349 /* restrict dictionary mode, to "rawContent" or "fullDict" only */
350 ZSTD_STATIC_ASSERT((U32)ZSTD_dm_fullDict > (U32)ZSTD_dm_rawContent);
351 if (value > (unsigned)ZSTD_dm_fullDict)
352 return ERROR(compressionParameter_outOfBound);
353 cctx->dictMode = (ZSTD_dictMode_e)value;
356 case ZSTD_p_refDictContent :
357 if (cctx->cdict) return ERROR(stage_wrong); /* must be set before loading */
358 /* dictionary content will be referenced, instead of copied */
359 cctx->dictContentByRef = value>0;
362 case ZSTD_p_forceMaxWindow : /* Force back-references to remain < windowSize,
363 * even when referencing into Dictionary content
364 * default : 0 when using a CDict, 1 when using a Prefix */
365 cctx->forceWindow = value>0;
366 cctx->loadedDictEnd = 0;
369 case ZSTD_p_nbThreads:
370 if (value==0) return 0;
371 DEBUGLOG(5, " setting nbThreads : %u", value);
372 #ifndef ZSTD_MULTITHREAD
373 if (value > 1) return ERROR(compressionParameter_unsupported);
375 if ((value>1) && (cctx->nbThreads != value)) {
376 if (cctx->staticSize) /* MT not compatible with static alloc */
377 return ERROR(compressionParameter_unsupported);
378 ZSTDMT_freeCCtx(cctx->mtctx);
380 cctx->mtctx = ZSTDMT_createCCtx(value);
381 if (cctx->mtctx == NULL) return ERROR(memory_allocation);
383 cctx->nbThreads = value;
387 if (cctx->nbThreads <= 1) return ERROR(compressionParameter_unsupported);
388 assert(cctx->mtctx != NULL);
389 return ZSTDMT_setMTCtxParameter(cctx->mtctx, ZSTDMT_p_sectionSize, value);
391 case ZSTD_p_overlapSizeLog:
392 DEBUGLOG(5, " setting overlap with nbThreads == %u", cctx->nbThreads);
393 if (cctx->nbThreads <= 1) return ERROR(compressionParameter_unsupported);
394 assert(cctx->mtctx != NULL);
395 return ZSTDMT_setMTCtxParameter(cctx->mtctx, ZSTDMT_p_overlapSectionLog, value);
397 default: return ERROR(parameter_unknown);
401 ZSTDLIB_API size_t ZSTD_CCtx_setPledgedSrcSize(ZSTD_CCtx* cctx, unsigned long long pledgedSrcSize)
403 DEBUGLOG(5, " setting pledgedSrcSize to %u", (U32)pledgedSrcSize);
404 if (cctx->streamStage != zcss_init) return ERROR(stage_wrong);
405 cctx->pledgedSrcSizePlusOne = pledgedSrcSize+1;
409 ZSTDLIB_API size_t ZSTD_CCtx_loadDictionary(ZSTD_CCtx* cctx, const void* dict, size_t dictSize)
411 if (cctx->streamStage != zcss_init) return ERROR(stage_wrong);
412 if (cctx->staticSize) return ERROR(memory_allocation); /* no malloc for static CCtx */
413 DEBUGLOG(5, "load dictionary of size %u", (U32)dictSize);
414 ZSTD_freeCDict(cctx->cdictLocal); /* in case one already exists */
415 if (dict==NULL || dictSize==0) { /* no dictionary mode */
416 cctx->cdictLocal = NULL;
419 ZSTD_compressionParameters const cParams =
420 cctx->compressionLevel == ZSTD_CLEVEL_CUSTOM ?
421 cctx->requestedParams.cParams :
422 ZSTD_getCParams(cctx->compressionLevel, 0, dictSize);
423 cctx->cdictLocal = ZSTD_createCDict_advanced(
425 cctx->dictContentByRef, cctx->dictMode,
426 cParams, cctx->customMem);
427 cctx->cdict = cctx->cdictLocal;
428 if (cctx->cdictLocal == NULL)
429 return ERROR(memory_allocation);
434 size_t ZSTD_CCtx_refCDict(ZSTD_CCtx* cctx, const ZSTD_CDict* cdict)
436 if (cctx->streamStage != zcss_init) return ERROR(stage_wrong);
438 cctx->prefix = NULL; /* exclusive */
439 cctx->prefixSize = 0;
443 size_t ZSTD_CCtx_refPrefix(ZSTD_CCtx* cctx, const void* prefix, size_t prefixSize)
445 if (cctx->streamStage != zcss_init) return ERROR(stage_wrong);
446 cctx->cdict = NULL; /* prefix discards any prior cdict */
447 cctx->prefix = prefix;
448 cctx->prefixSize = prefixSize;
452 static void ZSTD_startNewCompression(ZSTD_CCtx* cctx)
454 cctx->streamStage = zcss_init;
455 cctx->pledgedSrcSizePlusOne = 0;
458 /*! ZSTD_CCtx_reset() :
459 * Also dumps dictionary */
460 void ZSTD_CCtx_reset(ZSTD_CCtx* cctx)
462 ZSTD_startNewCompression(cctx);
466 /** ZSTD_checkCParams() :
467 control CParam values remain within authorized range.
468 @return : 0, or an error code if one value is beyond authorized range */
469 size_t ZSTD_checkCParams(ZSTD_compressionParameters cParams)
471 CLAMPCHECK(cParams.windowLog, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);
472 CLAMPCHECK(cParams.chainLog, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX);
473 CLAMPCHECK(cParams.hashLog, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX);
474 CLAMPCHECK(cParams.searchLog, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX);
475 CLAMPCHECK(cParams.searchLength, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX);
476 CLAMPCHECK(cParams.targetLength, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX);
477 if ((U32)(cParams.strategy) > (U32)ZSTD_btultra) return ERROR(compressionParameter_unsupported);
481 /** ZSTD_clampCParams() :
482 * make CParam values within valid range.
483 * @return : valid CParams */
484 static ZSTD_compressionParameters ZSTD_clampCParams(ZSTD_compressionParameters cParams)
486 # define CLAMP(val,min,max) { \
487 if (val<min) val=min; \
488 else if (val>max) val=max; \
490 CLAMP(cParams.windowLog, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);
491 CLAMP(cParams.chainLog, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX);
492 CLAMP(cParams.hashLog, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX);
493 CLAMP(cParams.searchLog, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX);
494 CLAMP(cParams.searchLength, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX);
495 CLAMP(cParams.targetLength, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX);
496 if ((U32)(cParams.strategy) > (U32)ZSTD_btultra) cParams.strategy = ZSTD_btultra;
500 /** ZSTD_cycleLog() :
501 * condition for correct operation : hashLog > 1 */
502 static U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat)
504 U32 const btScale = ((U32)strat >= (U32)ZSTD_btlazy2);
505 return hashLog - btScale;
508 /** ZSTD_adjustCParams_internal() :
509 optimize `cPar` for a given input (`srcSize` and `dictSize`).
510 mostly downsizing to reduce memory consumption and initialization.
511 Both `srcSize` and `dictSize` are optional (use 0 if unknown),
512 but if both are 0, no optimization can be done.
513 Note : cPar is considered validated at this stage. Use ZSTD_checkParams() to ensure that. */
514 ZSTD_compressionParameters ZSTD_adjustCParams_internal(ZSTD_compressionParameters cPar, unsigned long long srcSize, size_t dictSize)
516 assert(ZSTD_checkCParams(cPar)==0);
517 if (srcSize+dictSize == 0) return cPar; /* no size information available : no adjustment */
519 /* resize params, to use less memory when necessary */
520 { U32 const minSrcSize = (srcSize==0) ? 500 : 0;
521 U64 const rSize = srcSize + dictSize + minSrcSize;
522 if (rSize < ((U64)1<<ZSTD_WINDOWLOG_MAX)) {
523 U32 const srcLog = MAX(ZSTD_HASHLOG_MIN, ZSTD_highbit32((U32)(rSize)-1) + 1);
524 if (cPar.windowLog > srcLog) cPar.windowLog = srcLog;
526 if (cPar.hashLog > cPar.windowLog) cPar.hashLog = cPar.windowLog;
527 { U32 const cycleLog = ZSTD_cycleLog(cPar.chainLog, cPar.strategy);
528 if (cycleLog > cPar.windowLog) cPar.chainLog -= (cycleLog - cPar.windowLog);
531 if (cPar.windowLog < ZSTD_WINDOWLOG_ABSOLUTEMIN) cPar.windowLog = ZSTD_WINDOWLOG_ABSOLUTEMIN; /* required for frame header */
536 ZSTD_compressionParameters ZSTD_adjustCParams(ZSTD_compressionParameters cPar, unsigned long long srcSize, size_t dictSize)
538 cPar = ZSTD_clampCParams(cPar);
539 return ZSTD_adjustCParams_internal(cPar, srcSize, dictSize);
543 size_t ZSTD_estimateCCtxSize_advanced(ZSTD_compressionParameters cParams)
545 size_t const blockSize = MIN(ZSTD_BLOCKSIZE_MAX, (size_t)1 << cParams.windowLog);
546 U32 const divider = (cParams.searchLength==3) ? 3 : 4;
547 size_t const maxNbSeq = blockSize / divider;
548 size_t const tokenSpace = blockSize + 11*maxNbSeq;
550 size_t const chainSize = (cParams.strategy == ZSTD_fast) ? 0 : (1 << cParams.chainLog);
551 size_t const hSize = ((size_t)1) << cParams.hashLog;
552 U32 const hashLog3 = (cParams.searchLength>3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, cParams.windowLog);
553 size_t const h3Size = ((size_t)1) << hashLog3;
554 size_t const entropySpace = hufCTable_size + litlengthCTable_size
555 + offcodeCTable_size + matchlengthCTable_size
556 + entropyScratchSpace_size;
557 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
559 size_t const optBudget = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits))*sizeof(U32)
560 + (ZSTD_OPT_NUM+1)*(sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t));
561 size_t const optSpace = ((cParams.strategy == ZSTD_btopt) || (cParams.strategy == ZSTD_btultra)) ? optBudget : 0;
562 size_t const neededSpace = entropySpace + tableSpace + tokenSpace + optSpace;
564 DEBUGLOG(5, "sizeof(ZSTD_CCtx) : %u", (U32)sizeof(ZSTD_CCtx));
565 DEBUGLOG(5, "estimate workSpace : %u", (U32)neededSpace);
566 return sizeof(ZSTD_CCtx) + neededSpace;
569 size_t ZSTD_estimateCCtxSize(int compressionLevel)
571 ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, 0, 0);
572 return ZSTD_estimateCCtxSize_advanced(cParams);
575 size_t ZSTD_estimateCStreamSize_advanced(ZSTD_compressionParameters cParams)
577 size_t const CCtxSize = ZSTD_estimateCCtxSize_advanced(cParams);
578 size_t const blockSize = MIN(ZSTD_BLOCKSIZE_MAX, (size_t)1 << cParams.windowLog);
579 size_t const inBuffSize = ((size_t)1 << cParams.windowLog) + blockSize;
580 size_t const outBuffSize = ZSTD_compressBound(blockSize) + 1;
581 size_t const streamingSize = inBuffSize + outBuffSize;
583 return CCtxSize + streamingSize;
586 size_t ZSTD_estimateCStreamSize(int compressionLevel) {
587 ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, 0, 0);
588 return ZSTD_estimateCStreamSize_advanced(cParams);
592 static U32 ZSTD_equivalentParams(ZSTD_compressionParameters cParams1,
593 ZSTD_compressionParameters cParams2)
595 U32 bslog1 = MIN(cParams1.windowLog, ZSTD_BLOCKSIZELOG_MAX);
596 U32 bslog2 = MIN(cParams2.windowLog, ZSTD_BLOCKSIZELOG_MAX);
597 return (bslog1 == bslog2) /* same block size */
598 & (cParams1.hashLog == cParams2.hashLog)
599 & (cParams1.chainLog == cParams2.chainLog)
600 & (cParams1.strategy == cParams2.strategy) /* opt parser space */
601 & ((cParams1.searchLength==3) == (cParams2.searchLength==3)); /* hashlog3 space */
604 /*! ZSTD_continueCCtx() :
605 * reuse CCtx without reset (note : requires no dictionary) */
606 static size_t ZSTD_continueCCtx(ZSTD_CCtx* cctx, ZSTD_parameters params, U64 pledgedSrcSize)
608 U32 const end = (U32)(cctx->nextSrc - cctx->base);
609 DEBUGLOG(5, "continue mode");
610 cctx->appliedParams = params;
611 cctx->pledgedSrcSizePlusOne = pledgedSrcSize+1;
612 cctx->consumedSrcSize = 0;
613 if (pledgedSrcSize == ZSTD_CONTENTSIZE_UNKNOWN)
614 cctx->appliedParams.fParams.contentSizeFlag = 0;
615 DEBUGLOG(5, "pledged content size : %u ; flag : %u",
616 (U32)pledgedSrcSize, cctx->appliedParams.fParams.contentSizeFlag);
617 cctx->lowLimit = end;
618 cctx->dictLimit = end;
619 cctx->nextToUpdate = end+1;
620 cctx->stage = ZSTDcs_init;
622 cctx->loadedDictEnd = 0;
623 { int i; for (i=0; i<ZSTD_REP_NUM; i++) cctx->rep[i] = repStartValue[i]; }
624 cctx->seqStore.litLengthSum = 0; /* force reset of btopt stats */
625 XXH64_reset(&cctx->xxhState, 0);
629 typedef enum { ZSTDcrp_continue, ZSTDcrp_noMemset } ZSTD_compResetPolicy_e;
630 typedef enum { ZSTDb_not_buffered, ZSTDb_buffered } ZSTD_buffered_policy_e;
632 /*! ZSTD_resetCCtx_internal() :
633 note : `params` are assumed fully validated at this stage */
634 static size_t ZSTD_resetCCtx_internal(ZSTD_CCtx* zc,
635 ZSTD_parameters params, U64 pledgedSrcSize,
636 ZSTD_compResetPolicy_e const crp,
637 ZSTD_buffered_policy_e const zbuff)
639 assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
641 if (crp == ZSTDcrp_continue) {
642 if (ZSTD_equivalentParams(params.cParams, zc->appliedParams.cParams)) {
643 DEBUGLOG(5, "ZSTD_equivalentParams()==1");
644 zc->fseCTables_ready = 0;
645 zc->hufCTable_repeatMode = HUF_repeat_none;
646 return ZSTD_continueCCtx(zc, params, pledgedSrcSize);
649 { size_t const blockSize = MIN(ZSTD_BLOCKSIZE_MAX, (size_t)1 << params.cParams.windowLog);
650 U32 const divider = (params.cParams.searchLength==3) ? 3 : 4;
651 size_t const maxNbSeq = blockSize / divider;
652 size_t const tokenSpace = blockSize + 11*maxNbSeq;
653 size_t const chainSize = (params.cParams.strategy == ZSTD_fast) ?
654 0 : (1 << params.cParams.chainLog);
655 size_t const hSize = ((size_t)1) << params.cParams.hashLog;
656 U32 const hashLog3 = (params.cParams.searchLength>3) ?
657 0 : MIN(ZSTD_HASHLOG3_MAX, params.cParams.windowLog);
658 size_t const h3Size = ((size_t)1) << hashLog3;
659 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
660 size_t const buffOutSize = (zbuff==ZSTDb_buffered) ? ZSTD_compressBound(blockSize)+1 : 0;
661 size_t const buffInSize = (zbuff==ZSTDb_buffered) ? ((size_t)1 << params.cParams.windowLog) + blockSize : 0;
664 /* Check if workSpace is large enough, alloc a new one if needed */
665 { size_t const entropySpace = hufCTable_size + litlengthCTable_size
666 + offcodeCTable_size + matchlengthCTable_size
667 + entropyScratchSpace_size;
668 size_t const optPotentialSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits)) * sizeof(U32)
669 + (ZSTD_OPT_NUM+1) * (sizeof(ZSTD_match_t)+sizeof(ZSTD_optimal_t));
670 size_t const optSpace = ( (params.cParams.strategy == ZSTD_btopt)
671 || (params.cParams.strategy == ZSTD_btultra)) ?
672 optPotentialSpace : 0;
673 size_t const bufferSpace = buffInSize + buffOutSize;
674 size_t const neededSpace = entropySpace + optSpace + tableSpace
675 + tokenSpace + bufferSpace;
677 if (zc->workSpaceSize < neededSpace) { /* too small : resize /*/
678 DEBUGLOG(5, "Need to update workSpaceSize from %uK to %uK \n",
679 (unsigned)zc->workSpaceSize>>10,
680 (unsigned)neededSpace>>10);
681 /* static cctx : no resize, error out */
682 if (zc->staticSize) return ERROR(memory_allocation);
684 zc->workSpaceSize = 0;
685 ZSTD_free(zc->workSpace, zc->customMem);
686 zc->workSpace = ZSTD_malloc(neededSpace, zc->customMem);
687 if (zc->workSpace == NULL) return ERROR(memory_allocation);
688 zc->workSpaceSize = neededSpace;
692 zc->hufCTable = (HUF_CElt*)ptr;
693 ptr = (char*)zc->hufCTable + hufCTable_size; /* note : HUF_CElt* is incomplete type, size is estimated via macro */
694 zc->offcodeCTable = (FSE_CTable*) ptr;
695 ptr = (char*)ptr + offcodeCTable_size;
696 zc->matchlengthCTable = (FSE_CTable*) ptr;
697 ptr = (char*)ptr + matchlengthCTable_size;
698 zc->litlengthCTable = (FSE_CTable*) ptr;
699 ptr = (char*)ptr + litlengthCTable_size;
700 assert(((size_t)ptr & 3) == 0); /* ensure correct alignment */
701 zc->entropyScratchSpace = (unsigned*) ptr;
705 zc->appliedParams = params;
706 zc->pledgedSrcSizePlusOne = pledgedSrcSize+1;
707 zc->consumedSrcSize = 0;
708 if (pledgedSrcSize == ZSTD_CONTENTSIZE_UNKNOWN)
709 zc->appliedParams.fParams.contentSizeFlag = 0;
710 DEBUGLOG(5, "pledged content size : %u ; flag : %u",
711 (U32)pledgedSrcSize, zc->appliedParams.fParams.contentSizeFlag);
712 zc->blockSize = blockSize;
714 XXH64_reset(&zc->xxhState, 0);
715 zc->stage = ZSTDcs_init;
717 zc->loadedDictEnd = 0;
718 zc->fseCTables_ready = 0;
719 zc->hufCTable_repeatMode = HUF_repeat_none;
720 zc->nextToUpdate = 1;
726 { int i; for (i=0; i<ZSTD_REP_NUM; i++) zc->rep[i] = repStartValue[i]; }
727 zc->hashLog3 = hashLog3;
728 zc->seqStore.litLengthSum = 0;
730 /* ensure entropy tables are close together at the beginning */
731 assert((void*)zc->hufCTable == zc->workSpace);
732 assert((char*)zc->offcodeCTable == (char*)zc->hufCTable + hufCTable_size);
733 assert((char*)zc->matchlengthCTable == (char*)zc->offcodeCTable + offcodeCTable_size);
734 assert((char*)zc->litlengthCTable == (char*)zc->matchlengthCTable + matchlengthCTable_size);
735 assert((char*)zc->entropyScratchSpace == (char*)zc->litlengthCTable + litlengthCTable_size);
736 ptr = (char*)zc->entropyScratchSpace + entropyScratchSpace_size;
738 /* opt parser space */
739 if ((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btultra)) {
740 DEBUGLOG(5, "reserving optimal parser space");
741 assert(((size_t)ptr & 3) == 0); /* ensure ptr is properly aligned */
742 zc->seqStore.litFreq = (U32*)ptr;
743 zc->seqStore.litLengthFreq = zc->seqStore.litFreq + (1<<Litbits);
744 zc->seqStore.matchLengthFreq = zc->seqStore.litLengthFreq + (MaxLL+1);
745 zc->seqStore.offCodeFreq = zc->seqStore.matchLengthFreq + (MaxML+1);
746 ptr = zc->seqStore.offCodeFreq + (MaxOff+1);
747 zc->seqStore.matchTable = (ZSTD_match_t*)ptr;
748 ptr = zc->seqStore.matchTable + ZSTD_OPT_NUM+1;
749 zc->seqStore.priceTable = (ZSTD_optimal_t*)ptr;
750 ptr = zc->seqStore.priceTable + ZSTD_OPT_NUM+1;
754 if (crp!=ZSTDcrp_noMemset) memset(ptr, 0, tableSpace); /* reset tables only */
755 assert(((size_t)ptr & 3) == 0); /* ensure ptr is properly aligned */
756 zc->hashTable = (U32*)(ptr);
757 zc->chainTable = zc->hashTable + hSize;
758 zc->hashTable3 = zc->chainTable + chainSize;
759 ptr = zc->hashTable3 + h3Size;
761 /* sequences storage */
762 zc->seqStore.sequencesStart = (seqDef*)ptr;
763 ptr = zc->seqStore.sequencesStart + maxNbSeq;
764 zc->seqStore.llCode = (BYTE*) ptr;
765 zc->seqStore.mlCode = zc->seqStore.llCode + maxNbSeq;
766 zc->seqStore.ofCode = zc->seqStore.mlCode + maxNbSeq;
767 zc->seqStore.litStart = zc->seqStore.ofCode + maxNbSeq;
768 ptr = zc->seqStore.litStart + blockSize;
771 zc->inBuffSize = buffInSize;
772 zc->inBuff = (char*)ptr;
773 zc->outBuffSize = buffOutSize;
774 zc->outBuff = zc->inBuff + buffInSize;
780 /* ZSTD_invalidateRepCodes() :
781 * ensures next compression will not use repcodes from previous block.
782 * Note : only works with regular variant;
783 * do not use with extDict variant ! */
784 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx) {
786 for (i=0; i<ZSTD_REP_NUM; i++) cctx->rep[i] = 0;
790 /*! ZSTD_copyCCtx_internal() :
791 * Duplicate an existing context `srcCCtx` into another one `dstCCtx`.
792 * Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()).
793 * pledgedSrcSize=0 means "empty" if fParams.contentSizeFlag=1
794 * @return : 0, or an error code */
795 static size_t ZSTD_copyCCtx_internal(ZSTD_CCtx* dstCCtx,
796 const ZSTD_CCtx* srcCCtx,
797 ZSTD_frameParameters fParams,
798 unsigned long long pledgedSrcSize,
799 ZSTD_buffered_policy_e zbuff)
801 DEBUGLOG(5, "ZSTD_copyCCtx_internal");
802 if (srcCCtx->stage!=ZSTDcs_init) return ERROR(stage_wrong);
804 memcpy(&dstCCtx->customMem, &srcCCtx->customMem, sizeof(ZSTD_customMem));
805 { ZSTD_parameters params = srcCCtx->appliedParams;
806 params.fParams = fParams;
807 ZSTD_resetCCtx_internal(dstCCtx, params, pledgedSrcSize,
808 ZSTDcrp_noMemset, zbuff);
812 { size_t const chainSize = (srcCCtx->appliedParams.cParams.strategy == ZSTD_fast) ? 0 : (1 << srcCCtx->appliedParams.cParams.chainLog);
813 size_t const hSize = (size_t)1 << srcCCtx->appliedParams.cParams.hashLog;
814 size_t const h3Size = (size_t)1 << srcCCtx->hashLog3;
815 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
816 assert((U32*)dstCCtx->chainTable == (U32*)dstCCtx->hashTable + hSize); /* chainTable must follow hashTable */
817 assert((U32*)dstCCtx->hashTable3 == (U32*)dstCCtx->chainTable + chainSize);
818 memcpy(dstCCtx->hashTable, srcCCtx->hashTable, tableSpace); /* presumes all tables follow each other */
821 /* copy dictionary offsets */
822 dstCCtx->nextToUpdate = srcCCtx->nextToUpdate;
823 dstCCtx->nextToUpdate3= srcCCtx->nextToUpdate3;
824 dstCCtx->nextSrc = srcCCtx->nextSrc;
825 dstCCtx->base = srcCCtx->base;
826 dstCCtx->dictBase = srcCCtx->dictBase;
827 dstCCtx->dictLimit = srcCCtx->dictLimit;
828 dstCCtx->lowLimit = srcCCtx->lowLimit;
829 dstCCtx->loadedDictEnd= srcCCtx->loadedDictEnd;
830 dstCCtx->dictID = srcCCtx->dictID;
832 /* copy entropy tables */
833 dstCCtx->fseCTables_ready = srcCCtx->fseCTables_ready;
834 if (srcCCtx->fseCTables_ready) {
835 memcpy(dstCCtx->litlengthCTable, srcCCtx->litlengthCTable, litlengthCTable_size);
836 memcpy(dstCCtx->matchlengthCTable, srcCCtx->matchlengthCTable, matchlengthCTable_size);
837 memcpy(dstCCtx->offcodeCTable, srcCCtx->offcodeCTable, offcodeCTable_size);
839 dstCCtx->hufCTable_repeatMode = srcCCtx->hufCTable_repeatMode;
840 if (srcCCtx->hufCTable_repeatMode) {
841 memcpy(dstCCtx->hufCTable, srcCCtx->hufCTable, hufCTable_size);
847 /*! ZSTD_copyCCtx() :
848 * Duplicate an existing context `srcCCtx` into another one `dstCCtx`.
849 * Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()).
850 * pledgedSrcSize==0 means "unknown".
851 * @return : 0, or an error code */
852 size_t ZSTD_copyCCtx(ZSTD_CCtx* dstCCtx, const ZSTD_CCtx* srcCCtx, unsigned long long pledgedSrcSize)
854 ZSTD_frameParameters fParams = { 1 /*content*/, 0 /*checksum*/, 0 /*noDictID*/ };
855 ZSTD_buffered_policy_e const zbuff = (ZSTD_buffered_policy_e)(srcCCtx->inBuffSize>0);
856 ZSTD_STATIC_ASSERT((U32)ZSTDb_buffered==1);
857 fParams.contentSizeFlag = pledgedSrcSize>0;
859 return ZSTD_copyCCtx_internal(dstCCtx, srcCCtx, fParams, pledgedSrcSize, zbuff);
863 /*! ZSTD_reduceTable() :
864 * reduce table indexes by `reducerValue` */
865 static void ZSTD_reduceTable (U32* const table, U32 const size, U32 const reducerValue)
868 for (u=0 ; u < size ; u++) {
869 if (table[u] < reducerValue) table[u] = 0;
870 else table[u] -= reducerValue;
874 /*! ZSTD_reduceIndex() :
875 * rescale all indexes to avoid future overflow (indexes are U32) */
876 static void ZSTD_reduceIndex (ZSTD_CCtx* zc, const U32 reducerValue)
878 { U32 const hSize = 1 << zc->appliedParams.cParams.hashLog;
879 ZSTD_reduceTable(zc->hashTable, hSize, reducerValue); }
881 { U32 const chainSize = (zc->appliedParams.cParams.strategy == ZSTD_fast) ? 0 : (1 << zc->appliedParams.cParams.chainLog);
882 ZSTD_reduceTable(zc->chainTable, chainSize, reducerValue); }
884 { U32 const h3Size = (zc->hashLog3) ? 1 << zc->hashLog3 : 0;
885 ZSTD_reduceTable(zc->hashTable3, h3Size, reducerValue); }
889 /*-*******************************************************
890 * Block entropic compression
891 *********************************************************/
893 /* See doc/zstd_compression_format.md for detailed format description */
895 size_t ZSTD_noCompressBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
897 if (srcSize + ZSTD_blockHeaderSize > dstCapacity) return ERROR(dstSize_tooSmall);
898 memcpy((BYTE*)dst + ZSTD_blockHeaderSize, src, srcSize);
899 MEM_writeLE24(dst, (U32)(srcSize << 2) + (U32)bt_raw);
900 return ZSTD_blockHeaderSize+srcSize;
904 static size_t ZSTD_noCompressLiterals (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
906 BYTE* const ostart = (BYTE* const)dst;
907 U32 const flSize = 1 + (srcSize>31) + (srcSize>4095);
909 if (srcSize + flSize > dstCapacity) return ERROR(dstSize_tooSmall);
913 case 1: /* 2 - 1 - 5 */
914 ostart[0] = (BYTE)((U32)set_basic + (srcSize<<3));
916 case 2: /* 2 - 2 - 12 */
917 MEM_writeLE16(ostart, (U16)((U32)set_basic + (1<<2) + (srcSize<<4)));
919 case 3: /* 2 - 2 - 20 */
920 MEM_writeLE32(ostart, (U32)((U32)set_basic + (3<<2) + (srcSize<<4)));
922 default: /* not necessary : flSize is {1,2,3} */
926 memcpy(ostart + flSize, src, srcSize);
927 return srcSize + flSize;
930 static size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
932 BYTE* const ostart = (BYTE* const)dst;
933 U32 const flSize = 1 + (srcSize>31) + (srcSize>4095);
935 (void)dstCapacity; /* dstCapacity already guaranteed to be >=4, hence large enough */
939 case 1: /* 2 - 1 - 5 */
940 ostart[0] = (BYTE)((U32)set_rle + (srcSize<<3));
942 case 2: /* 2 - 2 - 12 */
943 MEM_writeLE16(ostart, (U16)((U32)set_rle + (1<<2) + (srcSize<<4)));
945 case 3: /* 2 - 2 - 20 */
946 MEM_writeLE32(ostart, (U32)((U32)set_rle + (3<<2) + (srcSize<<4)));
948 default: /* not necessary : flSize is {1,2,3} */
952 ostart[flSize] = *(const BYTE*)src;
957 static size_t ZSTD_minGain(size_t srcSize) { return (srcSize >> 6) + 2; }
959 static size_t ZSTD_compressLiterals (ZSTD_CCtx* zc,
960 void* dst, size_t dstCapacity,
961 const void* src, size_t srcSize)
963 size_t const minGain = ZSTD_minGain(srcSize);
964 size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB);
965 BYTE* const ostart = (BYTE*)dst;
966 U32 singleStream = srcSize < 256;
967 symbolEncodingType_e hType = set_compressed;
971 /* small ? don't even attempt compression (speed opt) */
972 # define LITERAL_NOENTROPY 63
973 { size_t const minLitSize = zc->hufCTable_repeatMode == HUF_repeat_valid ? 6 : LITERAL_NOENTROPY;
974 if (srcSize <= minLitSize) return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
977 if (dstCapacity < lhSize+1) return ERROR(dstSize_tooSmall); /* not enough space for compression */
978 { HUF_repeat repeat = zc->hufCTable_repeatMode;
979 int const preferRepeat = zc->appliedParams.cParams.strategy < ZSTD_lazy ? srcSize <= 1024 : 0;
980 if (repeat == HUF_repeat_valid && lhSize == 3) singleStream = 1;
981 cLitSize = singleStream ? HUF_compress1X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11,
982 zc->entropyScratchSpace, entropyScratchSpace_size, zc->hufCTable, &repeat, preferRepeat)
983 : HUF_compress4X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11,
984 zc->entropyScratchSpace, entropyScratchSpace_size, zc->hufCTable, &repeat, preferRepeat);
985 if (repeat != HUF_repeat_none) { hType = set_repeat; } /* reused the existing table */
986 else { zc->hufCTable_repeatMode = HUF_repeat_check; } /* now have a table to reuse */
989 if ((cLitSize==0) | (cLitSize >= srcSize - minGain)) {
990 zc->hufCTable_repeatMode = HUF_repeat_none;
991 return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
994 zc->hufCTable_repeatMode = HUF_repeat_none;
995 return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize);
1001 case 3: /* 2 - 2 - 10 - 10 */
1002 { U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<14);
1003 MEM_writeLE24(ostart, lhc);
1006 case 4: /* 2 - 2 - 14 - 14 */
1007 { U32 const lhc = hType + (2 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<18);
1008 MEM_writeLE32(ostart, lhc);
1011 case 5: /* 2 - 2 - 18 - 18 */
1012 { U32 const lhc = hType + (3 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<22);
1013 MEM_writeLE32(ostart, lhc);
1014 ostart[4] = (BYTE)(cLitSize >> 10);
1017 default: /* not possible : lhSize is {3,4,5} */
1020 return lhSize+cLitSize;
1023 static const BYTE LL_Code[64] = { 0, 1, 2, 3, 4, 5, 6, 7,
1024 8, 9, 10, 11, 12, 13, 14, 15,
1025 16, 16, 17, 17, 18, 18, 19, 19,
1026 20, 20, 20, 20, 21, 21, 21, 21,
1027 22, 22, 22, 22, 22, 22, 22, 22,
1028 23, 23, 23, 23, 23, 23, 23, 23,
1029 24, 24, 24, 24, 24, 24, 24, 24,
1030 24, 24, 24, 24, 24, 24, 24, 24 };
1032 static const BYTE ML_Code[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
1033 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
1034 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
1035 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
1036 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
1037 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
1038 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
1039 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
1042 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr)
1044 BYTE const LL_deltaCode = 19;
1045 BYTE const ML_deltaCode = 36;
1046 const seqDef* const sequences = seqStorePtr->sequencesStart;
1047 BYTE* const llCodeTable = seqStorePtr->llCode;
1048 BYTE* const ofCodeTable = seqStorePtr->ofCode;
1049 BYTE* const mlCodeTable = seqStorePtr->mlCode;
1050 U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
1052 for (u=0; u<nbSeq; u++) {
1053 U32 const llv = sequences[u].litLength;
1054 U32 const mlv = sequences[u].matchLength;
1055 llCodeTable[u] = (llv> 63) ? (BYTE)ZSTD_highbit32(llv) + LL_deltaCode : LL_Code[llv];
1056 ofCodeTable[u] = (BYTE)ZSTD_highbit32(sequences[u].offset);
1057 mlCodeTable[u] = (mlv>127) ? (BYTE)ZSTD_highbit32(mlv) + ML_deltaCode : ML_Code[mlv];
1059 if (seqStorePtr->longLengthID==1)
1060 llCodeTable[seqStorePtr->longLengthPos] = MaxLL;
1061 if (seqStorePtr->longLengthID==2)
1062 mlCodeTable[seqStorePtr->longLengthPos] = MaxML;
1065 MEM_STATIC size_t ZSTD_compressSequences (ZSTD_CCtx* zc,
1066 void* dst, size_t dstCapacity,
1069 const int longOffsets = zc->appliedParams.cParams.windowLog > STREAM_ACCUMULATOR_MIN;
1070 const seqStore_t* seqStorePtr = &(zc->seqStore);
1071 U32 count[MaxSeq+1];
1073 FSE_CTable* CTable_LitLength = zc->litlengthCTable;
1074 FSE_CTable* CTable_OffsetBits = zc->offcodeCTable;
1075 FSE_CTable* CTable_MatchLength = zc->matchlengthCTable;
1076 U32 LLtype, Offtype, MLtype; /* compressed, raw or rle */
1077 const seqDef* const sequences = seqStorePtr->sequencesStart;
1078 const BYTE* const ofCodeTable = seqStorePtr->ofCode;
1079 const BYTE* const llCodeTable = seqStorePtr->llCode;
1080 const BYTE* const mlCodeTable = seqStorePtr->mlCode;
1081 BYTE* const ostart = (BYTE*)dst;
1082 BYTE* const oend = ostart + dstCapacity;
1084 size_t const nbSeq = seqStorePtr->sequences - seqStorePtr->sequencesStart;
1086 BYTE scratchBuffer[1<<MAX(MLFSELog,LLFSELog)];
1088 /* Compress literals */
1089 { const BYTE* const literals = seqStorePtr->litStart;
1090 size_t const litSize = seqStorePtr->lit - literals;
1091 size_t const cSize = ZSTD_compressLiterals(zc, op, dstCapacity, literals, litSize);
1092 if (ZSTD_isError(cSize)) return cSize;
1096 /* Sequences Header */
1097 if ((oend-op) < 3 /*max nbSeq Size*/ + 1 /*seqHead */) return ERROR(dstSize_tooSmall);
1098 if (nbSeq < 0x7F) *op++ = (BYTE)nbSeq;
1099 else if (nbSeq < LONGNBSEQ) op[0] = (BYTE)((nbSeq>>8) + 0x80), op[1] = (BYTE)nbSeq, op+=2;
1100 else op[0]=0xFF, MEM_writeLE16(op+1, (U16)(nbSeq - LONGNBSEQ)), op+=3;
1101 if (nbSeq==0) goto _check_compressibility;
1103 /* seqHead : flags for FSE encoding type */
1106 #define MIN_SEQ_FOR_DYNAMIC_FSE 64
1107 #define MAX_SEQ_FOR_STATIC_FSE 1000
1109 /* convert length/distances into codes */
1110 ZSTD_seqToCodes(seqStorePtr);
1112 /* CTable for Literal Lengths */
1114 size_t const mostFrequent = FSE_countFast_wksp(count, &max, llCodeTable, nbSeq, zc->entropyScratchSpace);
1115 if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
1116 *op++ = llCodeTable[0];
1117 FSE_buildCTable_rle(CTable_LitLength, (BYTE)max);
1119 } else if ((zc->fseCTables_ready) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
1120 LLtype = set_repeat;
1121 } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (LL_defaultNormLog-1)))) {
1122 FSE_buildCTable_wksp(CTable_LitLength, LL_defaultNorm, MaxLL, LL_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
1125 size_t nbSeq_1 = nbSeq;
1126 const U32 tableLog = FSE_optimalTableLog(LLFSELog, nbSeq, max);
1127 if (count[llCodeTable[nbSeq-1]]>1) { count[llCodeTable[nbSeq-1]]--; nbSeq_1--; }
1128 FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
1129 { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */
1130 if (FSE_isError(NCountSize)) return NCountSize;
1132 FSE_buildCTable_wksp(CTable_LitLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
1133 LLtype = set_compressed;
1136 /* CTable for Offsets */
1138 size_t const mostFrequent = FSE_countFast_wksp(count, &max, ofCodeTable, nbSeq, zc->entropyScratchSpace);
1139 if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
1140 *op++ = ofCodeTable[0];
1141 FSE_buildCTable_rle(CTable_OffsetBits, (BYTE)max);
1143 } else if ((zc->fseCTables_ready) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
1144 Offtype = set_repeat;
1145 } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (OF_defaultNormLog-1)))) {
1146 FSE_buildCTable_wksp(CTable_OffsetBits, OF_defaultNorm, MaxOff, OF_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
1147 Offtype = set_basic;
1149 size_t nbSeq_1 = nbSeq;
1150 const U32 tableLog = FSE_optimalTableLog(OffFSELog, nbSeq, max);
1151 if (count[ofCodeTable[nbSeq-1]]>1) { count[ofCodeTable[nbSeq-1]]--; nbSeq_1--; }
1152 FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
1153 { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */
1154 if (FSE_isError(NCountSize)) return NCountSize;
1156 FSE_buildCTable_wksp(CTable_OffsetBits, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
1157 Offtype = set_compressed;
1160 /* CTable for MatchLengths */
1162 size_t const mostFrequent = FSE_countFast_wksp(count, &max, mlCodeTable, nbSeq, zc->entropyScratchSpace);
1163 if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
1164 *op++ = *mlCodeTable;
1165 FSE_buildCTable_rle(CTable_MatchLength, (BYTE)max);
1167 } else if ((zc->fseCTables_ready) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
1168 MLtype = set_repeat;
1169 } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (ML_defaultNormLog-1)))) {
1170 FSE_buildCTable_wksp(CTable_MatchLength, ML_defaultNorm, MaxML, ML_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
1173 size_t nbSeq_1 = nbSeq;
1174 const U32 tableLog = FSE_optimalTableLog(MLFSELog, nbSeq, max);
1175 if (count[mlCodeTable[nbSeq-1]]>1) { count[mlCodeTable[nbSeq-1]]--; nbSeq_1--; }
1176 FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
1177 { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */
1178 if (FSE_isError(NCountSize)) return NCountSize;
1180 FSE_buildCTable_wksp(CTable_MatchLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
1181 MLtype = set_compressed;
1184 *seqHead = (BYTE)((LLtype<<6) + (Offtype<<4) + (MLtype<<2));
1185 zc->fseCTables_ready = 0;
1187 /* Encoding Sequences */
1188 { BIT_CStream_t blockStream;
1189 FSE_CState_t stateMatchLength;
1190 FSE_CState_t stateOffsetBits;
1191 FSE_CState_t stateLitLength;
1193 CHECK_E(BIT_initCStream(&blockStream, op, oend-op), dstSize_tooSmall); /* not enough space remaining */
1196 FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);
1197 FSE_initCState2(&stateOffsetBits, CTable_OffsetBits, ofCodeTable[nbSeq-1]);
1198 FSE_initCState2(&stateLitLength, CTable_LitLength, llCodeTable[nbSeq-1]);
1199 BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);
1200 if (MEM_32bits()) BIT_flushBits(&blockStream);
1201 BIT_addBits(&blockStream, sequences[nbSeq-1].matchLength, ML_bits[mlCodeTable[nbSeq-1]]);
1202 if (MEM_32bits()) BIT_flushBits(&blockStream);
1204 U32 const ofBits = ofCodeTable[nbSeq-1];
1205 int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
1207 BIT_addBits(&blockStream, sequences[nbSeq-1].offset, extraBits);
1208 BIT_flushBits(&blockStream);
1210 BIT_addBits(&blockStream, sequences[nbSeq-1].offset >> extraBits,
1211 ofBits - extraBits);
1213 BIT_addBits(&blockStream, sequences[nbSeq-1].offset, ofCodeTable[nbSeq-1]);
1215 BIT_flushBits(&blockStream);
1218 for (n=nbSeq-2 ; n<nbSeq ; n--) { /* intentional underflow */
1219 BYTE const llCode = llCodeTable[n];
1220 BYTE const ofCode = ofCodeTable[n];
1221 BYTE const mlCode = mlCodeTable[n];
1222 U32 const llBits = LL_bits[llCode];
1223 U32 const ofBits = ofCode; /* 32b*/ /* 64b*/
1224 U32 const mlBits = ML_bits[mlCode];
1226 FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode); /* 15 */ /* 15 */
1227 FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode); /* 24 */ /* 24 */
1228 if (MEM_32bits()) BIT_flushBits(&blockStream); /* (7)*/
1229 FSE_encodeSymbol(&blockStream, &stateLitLength, llCode); /* 16 */ /* 33 */
1230 if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))
1231 BIT_flushBits(&blockStream); /* (7)*/
1232 BIT_addBits(&blockStream, sequences[n].litLength, llBits);
1233 if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);
1234 BIT_addBits(&blockStream, sequences[n].matchLength, mlBits);
1235 if (MEM_32bits()) BIT_flushBits(&blockStream); /* (7)*/
1237 int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
1239 BIT_addBits(&blockStream, sequences[n].offset, extraBits);
1240 BIT_flushBits(&blockStream); /* (7)*/
1242 BIT_addBits(&blockStream, sequences[n].offset >> extraBits,
1243 ofBits - extraBits); /* 31 */
1245 BIT_addBits(&blockStream, sequences[n].offset, ofBits); /* 31 */
1247 BIT_flushBits(&blockStream); /* (7)*/
1250 FSE_flushCState(&blockStream, &stateMatchLength);
1251 FSE_flushCState(&blockStream, &stateOffsetBits);
1252 FSE_flushCState(&blockStream, &stateLitLength);
1254 { size_t const streamSize = BIT_closeCStream(&blockStream);
1255 if (streamSize==0) return ERROR(dstSize_tooSmall); /* not enough space */
1259 /* check compressibility */
1260 _check_compressibility:
1261 { size_t const minGain = ZSTD_minGain(srcSize);
1262 size_t const maxCSize = srcSize - minGain;
1263 if ((size_t)(op-ostart) >= maxCSize) {
1264 zc->hufCTable_repeatMode = HUF_repeat_none;
1268 /* confirm repcodes */
1269 { int i; for (i=0; i<ZSTD_REP_NUM; i++) zc->rep[i] = zc->repToConfirm[i]; }
1275 /*! ZSTD_storeSeq() :
1276 Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
1277 `offsetCode` : distance to match, or 0 == repCode.
1278 `matchCode` : matchLength - MINMATCH
1280 MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const void* literals, U32 offsetCode, size_t matchCode)
1282 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG >= 6)
1283 static const BYTE* g_start = NULL;
1284 U32 const pos = (U32)((const BYTE*)literals - g_start);
1285 if (g_start==NULL) g_start = (const BYTE*)literals;
1286 if ((pos > 0) && (pos < 1000000000))
1287 DEBUGLOG(6, "Cpos %6u :%5u literals & match %3u bytes at distance %6u",
1288 pos, (U32)litLength, (U32)matchCode+MINMATCH, (U32)offsetCode);
1291 assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + 128 KB);
1292 ZSTD_wildcopy(seqStorePtr->lit, literals, litLength);
1293 seqStorePtr->lit += litLength;
1295 /* literal Length */
1296 if (litLength>0xFFFF) {
1297 seqStorePtr->longLengthID = 1;
1298 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
1300 seqStorePtr->sequences[0].litLength = (U16)litLength;
1303 seqStorePtr->sequences[0].offset = offsetCode + 1;
1306 if (matchCode>0xFFFF) {
1307 seqStorePtr->longLengthID = 2;
1308 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
1310 seqStorePtr->sequences[0].matchLength = (U16)matchCode;
1312 seqStorePtr->sequences++;
1316 /*-*************************************
1317 * Match length counter
1318 ***************************************/
1319 static unsigned ZSTD_NbCommonBytes (register size_t val)
1321 if (MEM_isLittleEndian()) {
1323 # if defined(_MSC_VER) && defined(_WIN64)
1324 unsigned long r = 0;
1325 _BitScanForward64( &r, (U64)val );
1326 return (unsigned)(r>>3);
1327 # elif defined(__GNUC__) && (__GNUC__ >= 3)
1328 return (__builtin_ctzll((U64)val) >> 3);
1330 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
1331 0, 3, 1, 3, 1, 4, 2, 7,
1332 0, 2, 3, 6, 1, 5, 3, 5,
1333 1, 3, 4, 4, 2, 5, 6, 7,
1334 7, 0, 1, 2, 3, 3, 4, 6,
1335 2, 6, 5, 5, 3, 4, 5, 6,
1336 7, 1, 2, 4, 6, 4, 4, 5,
1337 7, 2, 6, 5, 7, 6, 7, 7 };
1338 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
1340 } else { /* 32 bits */
1341 # if defined(_MSC_VER)
1343 _BitScanForward( &r, (U32)val );
1344 return (unsigned)(r>>3);
1345 # elif defined(__GNUC__) && (__GNUC__ >= 3)
1346 return (__builtin_ctz((U32)val) >> 3);
1348 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
1349 3, 2, 2, 1, 3, 2, 0, 1,
1350 3, 3, 1, 2, 2, 2, 2, 0,
1351 3, 1, 2, 0, 1, 0, 1, 1 };
1352 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
1355 } else { /* Big Endian CPU */
1357 # if defined(_MSC_VER) && defined(_WIN64)
1358 unsigned long r = 0;
1359 _BitScanReverse64( &r, val );
1360 return (unsigned)(r>>3);
1361 # elif defined(__GNUC__) && (__GNUC__ >= 3)
1362 return (__builtin_clzll(val) >> 3);
1365 const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */
1366 if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
1367 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
1371 } else { /* 32 bits */
1372 # if defined(_MSC_VER)
1373 unsigned long r = 0;
1374 _BitScanReverse( &r, (unsigned long)val );
1375 return (unsigned)(r>>3);
1376 # elif defined(__GNUC__) && (__GNUC__ >= 3)
1377 return (__builtin_clz((U32)val) >> 3);
1380 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
1388 static size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
1390 const BYTE* const pStart = pIn;
1391 const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
1393 while (pIn < pInLoopLimit) {
1394 size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
1395 if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
1396 pIn += ZSTD_NbCommonBytes(diff);
1397 return (size_t)(pIn - pStart);
1399 if (MEM_64bits()) if ((pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
1400 if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
1401 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
1402 return (size_t)(pIn - pStart);
1405 /** ZSTD_count_2segments() :
1406 * can count match length with `ip` & `match` in 2 different segments.
1407 * convention : on reaching mEnd, match count continue starting from iStart
1409 static size_t ZSTD_count_2segments(const BYTE* ip, const BYTE* match, const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
1411 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
1412 size_t const matchLength = ZSTD_count(ip, match, vEnd);
1413 if (match + matchLength != mEnd) return matchLength;
1414 return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
1418 /*-*************************************
1420 ***************************************/
1421 static const U32 prime3bytes = 506832829U;
1422 static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; }
1423 MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
1425 static const U32 prime4bytes = 2654435761U;
1426 static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
1427 static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
1429 static const U64 prime5bytes = 889523592379ULL;
1430 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h)) ; }
1431 static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
1433 static const U64 prime6bytes = 227718039650203ULL;
1434 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; }
1435 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
1437 static const U64 prime7bytes = 58295818150454627ULL;
1438 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h)) ; }
1439 static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
1441 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
1442 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
1443 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
1445 static size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
1450 case 4: return ZSTD_hash4Ptr(p, hBits);
1451 case 5: return ZSTD_hash5Ptr(p, hBits);
1452 case 6: return ZSTD_hash6Ptr(p, hBits);
1453 case 7: return ZSTD_hash7Ptr(p, hBits);
1454 case 8: return ZSTD_hash8Ptr(p, hBits);
1459 /*-*************************************
1461 ***************************************/
1462 static void ZSTD_fillHashTable (ZSTD_CCtx* zc, const void* end, const U32 mls)
1464 U32* const hashTable = zc->hashTable;
1465 U32 const hBits = zc->appliedParams.cParams.hashLog;
1466 const BYTE* const base = zc->base;
1467 const BYTE* ip = base + zc->nextToUpdate;
1468 const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
1469 const size_t fastHashFillStep = 3;
1472 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip - base);
1473 ip += fastHashFillStep;
1479 void ZSTD_compressBlock_fast_generic(ZSTD_CCtx* cctx,
1480 const void* src, size_t srcSize,
1483 U32* const hashTable = cctx->hashTable;
1484 U32 const hBits = cctx->appliedParams.cParams.hashLog;
1485 seqStore_t* seqStorePtr = &(cctx->seqStore);
1486 const BYTE* const base = cctx->base;
1487 const BYTE* const istart = (const BYTE*)src;
1488 const BYTE* ip = istart;
1489 const BYTE* anchor = istart;
1490 const U32 lowestIndex = cctx->dictLimit;
1491 const BYTE* const lowest = base + lowestIndex;
1492 const BYTE* const iend = istart + srcSize;
1493 const BYTE* const ilimit = iend - HASH_READ_SIZE;
1494 U32 offset_1=cctx->rep[0], offset_2=cctx->rep[1];
1495 U32 offsetSaved = 0;
1499 { U32 const maxRep = (U32)(ip-lowest);
1500 if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;
1501 if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;
1504 /* Main Search Loop */
1505 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */
1507 size_t const h = ZSTD_hashPtr(ip, hBits, mls);
1508 U32 const current = (U32)(ip-base);
1509 U32 const matchIndex = hashTable[h];
1510 const BYTE* match = base + matchIndex;
1511 hashTable[h] = current; /* update hash table */
1513 if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) {
1514 mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
1516 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1519 if ( (matchIndex <= lowestIndex) || (MEM_read32(match) != MEM_read32(ip)) ) {
1520 ip += ((ip-anchor) >> g_searchStrength) + 1;
1523 mLength = ZSTD_count(ip+4, match+4, iend) + 4;
1524 offset = (U32)(ip-match);
1525 while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1526 offset_2 = offset_1;
1529 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1538 hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2; /* here because current+2 could be > iend-8 */
1539 hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base);
1540 /* check immediate repcode */
1541 while ( (ip <= ilimit)
1543 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
1544 /* store sequence */
1545 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
1546 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; } /* swap offset_2 <=> offset_1 */
1547 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip-base);
1548 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength-MINMATCH);
1551 continue; /* faster when present ... (?) */
1554 /* save reps for next block */
1555 cctx->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved;
1556 cctx->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved;
1559 { size_t const lastLLSize = iend - anchor;
1560 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1561 seqStorePtr->lit += lastLLSize;
1566 static void ZSTD_compressBlock_fast(ZSTD_CCtx* ctx,
1567 const void* src, size_t srcSize)
1569 const U32 mls = ctx->appliedParams.cParams.searchLength;
1572 default: /* includes case 3 */
1574 ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 4); return;
1576 ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 5); return;
1578 ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 6); return;
1580 ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 7); return;
1585 static void ZSTD_compressBlock_fast_extDict_generic(ZSTD_CCtx* ctx,
1586 const void* src, size_t srcSize,
1589 U32* hashTable = ctx->hashTable;
1590 const U32 hBits = ctx->appliedParams.cParams.hashLog;
1591 seqStore_t* seqStorePtr = &(ctx->seqStore);
1592 const BYTE* const base = ctx->base;
1593 const BYTE* const dictBase = ctx->dictBase;
1594 const BYTE* const istart = (const BYTE*)src;
1595 const BYTE* ip = istart;
1596 const BYTE* anchor = istart;
1597 const U32 lowestIndex = ctx->lowLimit;
1598 const BYTE* const dictStart = dictBase + lowestIndex;
1599 const U32 dictLimit = ctx->dictLimit;
1600 const BYTE* const lowPrefixPtr = base + dictLimit;
1601 const BYTE* const dictEnd = dictBase + dictLimit;
1602 const BYTE* const iend = istart + srcSize;
1603 const BYTE* const ilimit = iend - 8;
1604 U32 offset_1=ctx->rep[0], offset_2=ctx->rep[1];
1607 while (ip < ilimit) { /* < instead of <=, because (ip+1) */
1608 const size_t h = ZSTD_hashPtr(ip, hBits, mls);
1609 const U32 matchIndex = hashTable[h];
1610 const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base;
1611 const BYTE* match = matchBase + matchIndex;
1612 const U32 current = (U32)(ip-base);
1613 const U32 repIndex = current + 1 - offset_1; /* offset_1 expected <= current +1 */
1614 const BYTE* repBase = repIndex < dictLimit ? dictBase : base;
1615 const BYTE* repMatch = repBase + repIndex;
1617 hashTable[h] = current; /* update hash table */
1619 if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex))
1620 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
1621 const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend;
1622 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, lowPrefixPtr) + 4;
1624 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1626 if ( (matchIndex < lowestIndex) ||
1627 (MEM_read32(match) != MEM_read32(ip)) ) {
1628 ip += ((ip-anchor) >> g_searchStrength) + 1;
1631 { const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend;
1632 const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;
1634 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, lowPrefixPtr) + 4;
1635 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1636 offset = current - matchIndex;
1637 offset_2 = offset_1;
1639 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1642 /* found a match : store it */
1648 hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2;
1649 hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base);
1650 /* check immediate repcode */
1651 while (ip <= ilimit) {
1652 U32 const current2 = (U32)(ip-base);
1653 U32 const repIndex2 = current2 - offset_2;
1654 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;
1655 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */
1656 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
1657 const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;
1658 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, lowPrefixPtr) + 4;
1659 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */
1660 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2-MINMATCH);
1661 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = current2;
1669 /* save reps for next block */
1670 ctx->repToConfirm[0] = offset_1; ctx->repToConfirm[1] = offset_2;
1673 { size_t const lastLLSize = iend - anchor;
1674 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1675 seqStorePtr->lit += lastLLSize;
1680 static void ZSTD_compressBlock_fast_extDict(ZSTD_CCtx* ctx,
1681 const void* src, size_t srcSize)
1683 U32 const mls = ctx->appliedParams.cParams.searchLength;
1686 default: /* includes case 3 */
1688 ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 4); return;
1690 ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 5); return;
1692 ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 6); return;
1694 ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 7); return;
1699 /*-*************************************
1701 ***************************************/
1702 static void ZSTD_fillDoubleHashTable (ZSTD_CCtx* cctx, const void* end, const U32 mls)
1704 U32* const hashLarge = cctx->hashTable;
1705 U32 const hBitsL = cctx->appliedParams.cParams.hashLog;
1706 U32* const hashSmall = cctx->chainTable;
1707 U32 const hBitsS = cctx->appliedParams.cParams.chainLog;
1708 const BYTE* const base = cctx->base;
1709 const BYTE* ip = base + cctx->nextToUpdate;
1710 const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
1711 const size_t fastHashFillStep = 3;
1714 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip - base);
1715 hashLarge[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip - base);
1716 ip += fastHashFillStep;
1722 void ZSTD_compressBlock_doubleFast_generic(ZSTD_CCtx* cctx,
1723 const void* src, size_t srcSize,
1726 U32* const hashLong = cctx->hashTable;
1727 const U32 hBitsL = cctx->appliedParams.cParams.hashLog;
1728 U32* const hashSmall = cctx->chainTable;
1729 const U32 hBitsS = cctx->appliedParams.cParams.chainLog;
1730 seqStore_t* seqStorePtr = &(cctx->seqStore);
1731 const BYTE* const base = cctx->base;
1732 const BYTE* const istart = (const BYTE*)src;
1733 const BYTE* ip = istart;
1734 const BYTE* anchor = istart;
1735 const U32 lowestIndex = cctx->dictLimit;
1736 const BYTE* const lowest = base + lowestIndex;
1737 const BYTE* const iend = istart + srcSize;
1738 const BYTE* const ilimit = iend - HASH_READ_SIZE;
1739 U32 offset_1=cctx->rep[0], offset_2=cctx->rep[1];
1740 U32 offsetSaved = 0;
1744 { U32 const maxRep = (U32)(ip-lowest);
1745 if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;
1746 if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;
1749 /* Main Search Loop */
1750 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */
1752 size_t const h2 = ZSTD_hashPtr(ip, hBitsL, 8);
1753 size_t const h = ZSTD_hashPtr(ip, hBitsS, mls);
1754 U32 const current = (U32)(ip-base);
1755 U32 const matchIndexL = hashLong[h2];
1756 U32 const matchIndexS = hashSmall[h];
1757 const BYTE* matchLong = base + matchIndexL;
1758 const BYTE* match = base + matchIndexS;
1759 hashLong[h2] = hashSmall[h] = current; /* update hash tables */
1761 assert(offset_1 <= current); /* supposed guaranteed by construction */
1762 if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) {
1764 mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
1766 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1769 if ( (matchIndexL > lowestIndex) && (MEM_read64(matchLong) == MEM_read64(ip)) ) {
1770 mLength = ZSTD_count(ip+8, matchLong+8, iend) + 8;
1771 offset = (U32)(ip-matchLong);
1772 while (((ip>anchor) & (matchLong>lowest)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */
1773 } else if ( (matchIndexS > lowestIndex) && (MEM_read32(match) == MEM_read32(ip)) ) {
1774 size_t const hl3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
1775 U32 const matchIndexL3 = hashLong[hl3];
1776 const BYTE* matchL3 = base + matchIndexL3;
1777 hashLong[hl3] = current + 1;
1778 if ( (matchIndexL3 > lowestIndex) && (MEM_read64(matchL3) == MEM_read64(ip+1)) ) {
1779 mLength = ZSTD_count(ip+9, matchL3+8, iend) + 8;
1781 offset = (U32)(ip-matchL3);
1782 while (((ip>anchor) & (matchL3>lowest)) && (ip[-1] == matchL3[-1])) { ip--; matchL3--; mLength++; } /* catch up */
1784 mLength = ZSTD_count(ip+4, match+4, iend) + 4;
1785 offset = (U32)(ip-match);
1786 while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1789 ip += ((ip-anchor) >> g_searchStrength) + 1;
1793 offset_2 = offset_1;
1796 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1805 hashLong[ZSTD_hashPtr(base+current+2, hBitsL, 8)] =
1806 hashSmall[ZSTD_hashPtr(base+current+2, hBitsS, mls)] = current+2; /* here because current+2 could be > iend-8 */
1807 hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] =
1808 hashSmall[ZSTD_hashPtr(ip-2, hBitsS, mls)] = (U32)(ip-2-base);
1810 /* check immediate repcode */
1811 while ( (ip <= ilimit)
1813 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
1814 /* store sequence */
1815 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
1816 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; } /* swap offset_2 <=> offset_1 */
1817 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip-base);
1818 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip-base);
1819 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength-MINMATCH);
1822 continue; /* faster when present ... (?) */
1825 /* save reps for next block */
1826 cctx->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved;
1827 cctx->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved;
1830 { size_t const lastLLSize = iend - anchor;
1831 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1832 seqStorePtr->lit += lastLLSize;
1837 static void ZSTD_compressBlock_doubleFast(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
1839 const U32 mls = ctx->appliedParams.cParams.searchLength;
1842 default: /* includes case 3 */
1844 ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 4); return;
1846 ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 5); return;
1848 ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 6); return;
1850 ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 7); return;
1855 static void ZSTD_compressBlock_doubleFast_extDict_generic(ZSTD_CCtx* ctx,
1856 const void* src, size_t srcSize,
1859 U32* const hashLong = ctx->hashTable;
1860 U32 const hBitsL = ctx->appliedParams.cParams.hashLog;
1861 U32* const hashSmall = ctx->chainTable;
1862 U32 const hBitsS = ctx->appliedParams.cParams.chainLog;
1863 seqStore_t* seqStorePtr = &(ctx->seqStore);
1864 const BYTE* const base = ctx->base;
1865 const BYTE* const dictBase = ctx->dictBase;
1866 const BYTE* const istart = (const BYTE*)src;
1867 const BYTE* ip = istart;
1868 const BYTE* anchor = istart;
1869 const U32 lowestIndex = ctx->lowLimit;
1870 const BYTE* const dictStart = dictBase + lowestIndex;
1871 const U32 dictLimit = ctx->dictLimit;
1872 const BYTE* const lowPrefixPtr = base + dictLimit;
1873 const BYTE* const dictEnd = dictBase + dictLimit;
1874 const BYTE* const iend = istart + srcSize;
1875 const BYTE* const ilimit = iend - 8;
1876 U32 offset_1=ctx->rep[0], offset_2=ctx->rep[1];
1879 while (ip < ilimit) { /* < instead of <=, because (ip+1) */
1880 const size_t hSmall = ZSTD_hashPtr(ip, hBitsS, mls);
1881 const U32 matchIndex = hashSmall[hSmall];
1882 const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base;
1883 const BYTE* match = matchBase + matchIndex;
1885 const size_t hLong = ZSTD_hashPtr(ip, hBitsL, 8);
1886 const U32 matchLongIndex = hashLong[hLong];
1887 const BYTE* matchLongBase = matchLongIndex < dictLimit ? dictBase : base;
1888 const BYTE* matchLong = matchLongBase + matchLongIndex;
1890 const U32 current = (U32)(ip-base);
1891 const U32 repIndex = current + 1 - offset_1; /* offset_1 expected <= current +1 */
1892 const BYTE* repBase = repIndex < dictLimit ? dictBase : base;
1893 const BYTE* repMatch = repBase + repIndex;
1895 hashSmall[hSmall] = hashLong[hLong] = current; /* update hash table */
1897 if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex))
1898 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
1899 const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend;
1900 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, lowPrefixPtr) + 4;
1902 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1904 if ((matchLongIndex > lowestIndex) && (MEM_read64(matchLong) == MEM_read64(ip))) {
1905 const BYTE* matchEnd = matchLongIndex < dictLimit ? dictEnd : iend;
1906 const BYTE* lowMatchPtr = matchLongIndex < dictLimit ? dictStart : lowPrefixPtr;
1908 mLength = ZSTD_count_2segments(ip+8, matchLong+8, iend, matchEnd, lowPrefixPtr) + 8;
1909 offset = current - matchLongIndex;
1910 while (((ip>anchor) & (matchLong>lowMatchPtr)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */
1911 offset_2 = offset_1;
1913 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1915 } else if ((matchIndex > lowestIndex) && (MEM_read32(match) == MEM_read32(ip))) {
1916 size_t const h3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
1917 U32 const matchIndex3 = hashLong[h3];
1918 const BYTE* const match3Base = matchIndex3 < dictLimit ? dictBase : base;
1919 const BYTE* match3 = match3Base + matchIndex3;
1921 hashLong[h3] = current + 1;
1922 if ( (matchIndex3 > lowestIndex) && (MEM_read64(match3) == MEM_read64(ip+1)) ) {
1923 const BYTE* matchEnd = matchIndex3 < dictLimit ? dictEnd : iend;
1924 const BYTE* lowMatchPtr = matchIndex3 < dictLimit ? dictStart : lowPrefixPtr;
1925 mLength = ZSTD_count_2segments(ip+9, match3+8, iend, matchEnd, lowPrefixPtr) + 8;
1927 offset = current+1 - matchIndex3;
1928 while (((ip>anchor) & (match3>lowMatchPtr)) && (ip[-1] == match3[-1])) { ip--; match3--; mLength++; } /* catch up */
1930 const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend;
1931 const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;
1932 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, lowPrefixPtr) + 4;
1933 offset = current - matchIndex;
1934 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1936 offset_2 = offset_1;
1938 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1941 ip += ((ip-anchor) >> g_searchStrength) + 1;
1945 /* found a match : store it */
1951 hashSmall[ZSTD_hashPtr(base+current+2, hBitsS, mls)] = current+2;
1952 hashLong[ZSTD_hashPtr(base+current+2, hBitsL, 8)] = current+2;
1953 hashSmall[ZSTD_hashPtr(ip-2, hBitsS, mls)] = (U32)(ip-2-base);
1954 hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base);
1955 /* check immediate repcode */
1956 while (ip <= ilimit) {
1957 U32 const current2 = (U32)(ip-base);
1958 U32 const repIndex2 = current2 - offset_2;
1959 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;
1960 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */
1961 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
1962 const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;
1963 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, lowPrefixPtr) + 4;
1964 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */
1965 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2-MINMATCH);
1966 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2;
1967 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2;
1975 /* save reps for next block */
1976 ctx->repToConfirm[0] = offset_1; ctx->repToConfirm[1] = offset_2;
1979 { size_t const lastLLSize = iend - anchor;
1980 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1981 seqStorePtr->lit += lastLLSize;
1986 static void ZSTD_compressBlock_doubleFast_extDict(ZSTD_CCtx* ctx,
1987 const void* src, size_t srcSize)
1989 U32 const mls = ctx->appliedParams.cParams.searchLength;
1992 default: /* includes case 3 */
1994 ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 4); return;
1996 ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 5); return;
1998 ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 6); return;
2000 ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 7); return;
2005 /*-*************************************
2006 * Binary Tree search
2007 ***************************************/
2008 /** ZSTD_insertBt1() : add one or multiple positions to tree.
2009 * ip : assumed <= iend-8 .
2010 * @return : nb of positions added */
2011 static U32 ZSTD_insertBt1(ZSTD_CCtx* zc, const BYTE* const ip, const U32 mls, const BYTE* const iend, U32 nbCompares,
2014 U32* const hashTable = zc->hashTable;
2015 U32 const hashLog = zc->appliedParams.cParams.hashLog;
2016 size_t const h = ZSTD_hashPtr(ip, hashLog, mls);
2017 U32* const bt = zc->chainTable;
2018 U32 const btLog = zc->appliedParams.cParams.chainLog - 1;
2019 U32 const btMask = (1 << btLog) - 1;
2020 U32 matchIndex = hashTable[h];
2021 size_t commonLengthSmaller=0, commonLengthLarger=0;
2022 const BYTE* const base = zc->base;
2023 const BYTE* const dictBase = zc->dictBase;
2024 const U32 dictLimit = zc->dictLimit;
2025 const BYTE* const dictEnd = dictBase + dictLimit;
2026 const BYTE* const prefixStart = base + dictLimit;
2028 const U32 current = (U32)(ip-base);
2029 const U32 btLow = btMask >= current ? 0 : current - btMask;
2030 U32* smallerPtr = bt + 2*(current&btMask);
2031 U32* largerPtr = smallerPtr + 1;
2032 U32 dummy32; /* to be nullified at the end */
2033 U32 const windowLow = zc->lowLimit;
2034 U32 matchEndIdx = current+8;
2035 size_t bestLength = 8;
2036 #ifdef ZSTD_C_PREDICT
2037 U32 predictedSmall = *(bt + 2*((current-1)&btMask) + 0);
2038 U32 predictedLarge = *(bt + 2*((current-1)&btMask) + 1);
2039 predictedSmall += (predictedSmall>0);
2040 predictedLarge += (predictedLarge>0);
2041 #endif /* ZSTD_C_PREDICT */
2043 hashTable[h] = current; /* Update Hash Table */
2045 while (nbCompares-- && (matchIndex > windowLow)) {
2046 U32* const nextPtr = bt + 2*(matchIndex & btMask);
2047 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
2049 #ifdef ZSTD_C_PREDICT /* note : can create issues when hlog small <= 11 */
2050 const U32* predictPtr = bt + 2*((matchIndex-1) & btMask); /* written this way, as bt is a roll buffer */
2051 if (matchIndex == predictedSmall) {
2052 /* no need to check length, result known */
2053 *smallerPtr = matchIndex;
2054 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
2055 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */
2056 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
2057 predictedSmall = predictPtr[1] + (predictPtr[1]>0);
2060 if (matchIndex == predictedLarge) {
2061 *largerPtr = matchIndex;
2062 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
2063 largerPtr = nextPtr;
2064 matchIndex = nextPtr[0];
2065 predictedLarge = predictPtr[0] + (predictPtr[0]>0);
2069 if ((!extDict) || (matchIndex+matchLength >= dictLimit)) {
2070 match = base + matchIndex;
2071 if (match[matchLength] == ip[matchLength])
2072 matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iend) +1;
2074 match = dictBase + matchIndex;
2075 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
2076 if (matchIndex+matchLength >= dictLimit)
2077 match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
2080 if (matchLength > bestLength) {
2081 bestLength = matchLength;
2082 if (matchLength > matchEndIdx - matchIndex)
2083 matchEndIdx = matchIndex + (U32)matchLength;
2086 if (ip+matchLength == iend) /* equal : no way to know if inf or sup */
2087 break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt the tree */
2089 if (match[matchLength] < ip[matchLength]) { /* necessarily within correct buffer */
2090 /* match is smaller than current */
2091 *smallerPtr = matchIndex; /* update smaller idx */
2092 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
2093 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
2094 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */
2095 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
2097 /* match is larger than current */
2098 *largerPtr = matchIndex;
2099 commonLengthLarger = matchLength;
2100 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
2101 largerPtr = nextPtr;
2102 matchIndex = nextPtr[0];
2105 *smallerPtr = *largerPtr = 0;
2106 if (bestLength > 384) return MIN(192, (U32)(bestLength - 384)); /* speed optimization */
2107 if (matchEndIdx > current + 8) return matchEndIdx - current - 8;
2112 static size_t ZSTD_insertBtAndFindBestMatch (
2114 const BYTE* const ip, const BYTE* const iend,
2116 U32 nbCompares, const U32 mls,
2119 U32* const hashTable = zc->hashTable;
2120 U32 const hashLog = zc->appliedParams.cParams.hashLog;
2121 size_t const h = ZSTD_hashPtr(ip, hashLog, mls);
2122 U32* const bt = zc->chainTable;
2123 U32 const btLog = zc->appliedParams.cParams.chainLog - 1;
2124 U32 const btMask = (1 << btLog) - 1;
2125 U32 matchIndex = hashTable[h];
2126 size_t commonLengthSmaller=0, commonLengthLarger=0;
2127 const BYTE* const base = zc->base;
2128 const BYTE* const dictBase = zc->dictBase;
2129 const U32 dictLimit = zc->dictLimit;
2130 const BYTE* const dictEnd = dictBase + dictLimit;
2131 const BYTE* const prefixStart = base + dictLimit;
2132 const U32 current = (U32)(ip-base);
2133 const U32 btLow = btMask >= current ? 0 : current - btMask;
2134 const U32 windowLow = zc->lowLimit;
2135 U32* smallerPtr = bt + 2*(current&btMask);
2136 U32* largerPtr = bt + 2*(current&btMask) + 1;
2137 U32 matchEndIdx = current+8;
2138 U32 dummy32; /* to be nullified at the end */
2139 size_t bestLength = 0;
2141 hashTable[h] = current; /* Update Hash Table */
2143 while (nbCompares-- && (matchIndex > windowLow)) {
2144 U32* const nextPtr = bt + 2*(matchIndex & btMask);
2145 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
2148 if ((!extDict) || (matchIndex+matchLength >= dictLimit)) {
2149 match = base + matchIndex;
2150 if (match[matchLength] == ip[matchLength])
2151 matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iend) +1;
2153 match = dictBase + matchIndex;
2154 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
2155 if (matchIndex+matchLength >= dictLimit)
2156 match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
2159 if (matchLength > bestLength) {
2160 if (matchLength > matchEndIdx - matchIndex)
2161 matchEndIdx = matchIndex + (U32)matchLength;
2162 if ( (4*(int)(matchLength-bestLength)) > (int)(ZSTD_highbit32(current-matchIndex+1) - ZSTD_highbit32((U32)offsetPtr[0]+1)) )
2163 bestLength = matchLength, *offsetPtr = ZSTD_REP_MOVE + current - matchIndex;
2164 if (ip+matchLength == iend) /* equal : no way to know if inf or sup */
2165 break; /* drop, to guarantee consistency (miss a little bit of compression) */
2168 if (match[matchLength] < ip[matchLength]) {
2169 /* match is smaller than current */
2170 *smallerPtr = matchIndex; /* update smaller idx */
2171 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
2172 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
2173 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */
2174 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
2176 /* match is larger than current */
2177 *largerPtr = matchIndex;
2178 commonLengthLarger = matchLength;
2179 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
2180 largerPtr = nextPtr;
2181 matchIndex = nextPtr[0];
2184 *smallerPtr = *largerPtr = 0;
2186 zc->nextToUpdate = (matchEndIdx > current + 8) ? matchEndIdx - 8 : current+1;
2191 static void ZSTD_updateTree(ZSTD_CCtx* zc, const BYTE* const ip, const BYTE* const iend, const U32 nbCompares, const U32 mls)
2193 const BYTE* const base = zc->base;
2194 const U32 target = (U32)(ip - base);
2195 U32 idx = zc->nextToUpdate;
2198 idx += ZSTD_insertBt1(zc, base+idx, mls, iend, nbCompares, 0);
2201 /** ZSTD_BtFindBestMatch() : Tree updater, providing best match */
2202 static size_t ZSTD_BtFindBestMatch (
2204 const BYTE* const ip, const BYTE* const iLimit,
2206 const U32 maxNbAttempts, const U32 mls)
2208 if (ip < zc->base + zc->nextToUpdate) return 0; /* skipped area */
2209 ZSTD_updateTree(zc, ip, iLimit, maxNbAttempts, mls);
2210 return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls, 0);
2214 static size_t ZSTD_BtFindBestMatch_selectMLS (
2215 ZSTD_CCtx* zc, /* Index table will be updated */
2216 const BYTE* ip, const BYTE* const iLimit,
2218 const U32 maxNbAttempts, const U32 matchLengthSearch)
2220 switch(matchLengthSearch)
2222 default : /* includes case 3 */
2223 case 4 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4);
2224 case 5 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5);
2226 case 6 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6);
2231 static void ZSTD_updateTree_extDict(ZSTD_CCtx* zc, const BYTE* const ip, const BYTE* const iend, const U32 nbCompares, const U32 mls)
2233 const BYTE* const base = zc->base;
2234 const U32 target = (U32)(ip - base);
2235 U32 idx = zc->nextToUpdate;
2237 while (idx < target) idx += ZSTD_insertBt1(zc, base+idx, mls, iend, nbCompares, 1);
2241 /** Tree updater, providing best match */
2242 static size_t ZSTD_BtFindBestMatch_extDict (
2244 const BYTE* const ip, const BYTE* const iLimit,
2246 const U32 maxNbAttempts, const U32 mls)
2248 if (ip < zc->base + zc->nextToUpdate) return 0; /* skipped area */
2249 ZSTD_updateTree_extDict(zc, ip, iLimit, maxNbAttempts, mls);
2250 return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls, 1);
2254 static size_t ZSTD_BtFindBestMatch_selectMLS_extDict (
2255 ZSTD_CCtx* zc, /* Index table will be updated */
2256 const BYTE* ip, const BYTE* const iLimit,
2258 const U32 maxNbAttempts, const U32 matchLengthSearch)
2260 switch(matchLengthSearch)
2262 default : /* includes case 3 */
2263 case 4 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4);
2264 case 5 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5);
2266 case 6 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6);
2272 /* *********************************
2274 ***********************************/
2275 #define NEXT_IN_CHAIN(d, mask) chainTable[(d) & mask]
2277 /* Update chains up to ip (excluded)
2278 Assumption : always within prefix (i.e. not within extDict) */
2280 U32 ZSTD_insertAndFindFirstIndex (ZSTD_CCtx* zc, const BYTE* ip, U32 mls)
2282 U32* const hashTable = zc->hashTable;
2283 const U32 hashLog = zc->appliedParams.cParams.hashLog;
2284 U32* const chainTable = zc->chainTable;
2285 const U32 chainMask = (1 << zc->appliedParams.cParams.chainLog) - 1;
2286 const BYTE* const base = zc->base;
2287 const U32 target = (U32)(ip - base);
2288 U32 idx = zc->nextToUpdate;
2290 while(idx < target) { /* catch up */
2291 size_t const h = ZSTD_hashPtr(base+idx, hashLog, mls);
2292 NEXT_IN_CHAIN(idx, chainMask) = hashTable[h];
2297 zc->nextToUpdate = target;
2298 return hashTable[ZSTD_hashPtr(ip, hashLog, mls)];
2302 /* inlining is important to hardwire a hot branch (template emulation) */
2304 size_t ZSTD_HcFindBestMatch_generic (
2305 ZSTD_CCtx* zc, /* Index table will be updated */
2306 const BYTE* const ip, const BYTE* const iLimit,
2308 const U32 maxNbAttempts, const U32 mls, const U32 extDict)
2310 U32* const chainTable = zc->chainTable;
2311 const U32 chainSize = (1 << zc->appliedParams.cParams.chainLog);
2312 const U32 chainMask = chainSize-1;
2313 const BYTE* const base = zc->base;
2314 const BYTE* const dictBase = zc->dictBase;
2315 const U32 dictLimit = zc->dictLimit;
2316 const BYTE* const prefixStart = base + dictLimit;
2317 const BYTE* const dictEnd = dictBase + dictLimit;
2318 const U32 lowLimit = zc->lowLimit;
2319 const U32 current = (U32)(ip-base);
2320 const U32 minChain = current > chainSize ? current - chainSize : 0;
2321 int nbAttempts=maxNbAttempts;
2324 /* HC4 match finder */
2325 U32 matchIndex = ZSTD_insertAndFindFirstIndex (zc, ip, mls);
2327 for ( ; (matchIndex>lowLimit) & (nbAttempts>0) ; nbAttempts--) {
2330 if ((!extDict) || matchIndex >= dictLimit) {
2331 match = base + matchIndex;
2332 if (match[ml] == ip[ml]) /* potentially better */
2333 currentMl = ZSTD_count(ip, match, iLimit);
2335 match = dictBase + matchIndex;
2336 if (MEM_read32(match) == MEM_read32(ip)) /* assumption : matchIndex <= dictLimit-4 (by table construction) */
2337 currentMl = ZSTD_count_2segments(ip+4, match+4, iLimit, dictEnd, prefixStart) + 4;
2340 /* save best solution */
2341 if (currentMl > ml) {
2343 *offsetPtr = current - matchIndex + ZSTD_REP_MOVE;
2344 if (ip+currentMl == iLimit) break; /* best possible, avoids read overflow on next attempt */
2347 if (matchIndex <= minChain) break;
2348 matchIndex = NEXT_IN_CHAIN(matchIndex, chainMask);
2355 FORCE_INLINE size_t ZSTD_HcFindBestMatch_selectMLS (
2357 const BYTE* ip, const BYTE* const iLimit,
2359 const U32 maxNbAttempts, const U32 matchLengthSearch)
2361 switch(matchLengthSearch)
2363 default : /* includes case 3 */
2364 case 4 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 0);
2365 case 5 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 0);
2367 case 6 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 0);
2372 FORCE_INLINE size_t ZSTD_HcFindBestMatch_extDict_selectMLS (
2374 const BYTE* ip, const BYTE* const iLimit,
2376 const U32 maxNbAttempts, const U32 matchLengthSearch)
2378 switch(matchLengthSearch)
2380 default : /* includes case 3 */
2381 case 4 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 1);
2382 case 5 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 1);
2384 case 6 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 1);
2389 /* *******************************
2390 * Common parser - lazy strategy
2391 *********************************/
2393 void ZSTD_compressBlock_lazy_generic(ZSTD_CCtx* ctx,
2394 const void* src, size_t srcSize,
2395 const U32 searchMethod, const U32 depth)
2397 seqStore_t* seqStorePtr = &(ctx->seqStore);
2398 const BYTE* const istart = (const BYTE*)src;
2399 const BYTE* ip = istart;
2400 const BYTE* anchor = istart;
2401 const BYTE* const iend = istart + srcSize;
2402 const BYTE* const ilimit = iend - 8;
2403 const BYTE* const base = ctx->base + ctx->dictLimit;
2405 U32 const maxSearches = 1 << ctx->appliedParams.cParams.searchLog;
2406 U32 const mls = ctx->appliedParams.cParams.searchLength;
2408 typedef size_t (*searchMax_f)(ZSTD_CCtx* zc, const BYTE* ip, const BYTE* iLimit,
2410 U32 maxNbAttempts, U32 matchLengthSearch);
2411 searchMax_f const searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS : ZSTD_HcFindBestMatch_selectMLS;
2412 U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1], savedOffset=0;
2416 ctx->nextToUpdate3 = ctx->nextToUpdate;
2417 { U32 const maxRep = (U32)(ip-base);
2418 if (offset_2 > maxRep) savedOffset = offset_2, offset_2 = 0;
2419 if (offset_1 > maxRep) savedOffset = offset_1, offset_1 = 0;
2423 while (ip < ilimit) {
2424 size_t matchLength=0;
2426 const BYTE* start=ip+1;
2429 if ((offset_1>0) & (MEM_read32(ip+1) == MEM_read32(ip+1 - offset_1))) {
2430 /* repcode : we take it */
2431 matchLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
2432 if (depth==0) goto _storeSequence;
2435 /* first search (depth 0) */
2436 { size_t offsetFound = 99999999;
2437 size_t const ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls);
2438 if (ml2 > matchLength)
2439 matchLength = ml2, start = ip, offset=offsetFound;
2442 if (matchLength < 4) {
2443 ip += ((ip-anchor) >> g_searchStrength) + 1; /* jump faster over incompressible sections */
2447 /* let's try to find a better solution */
2451 if ((offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) {
2452 size_t const mlRep = ZSTD_count(ip+4, ip+4-offset_1, iend) + 4;
2453 int const gain2 = (int)(mlRep * 3);
2454 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);
2455 if ((mlRep >= 4) && (gain2 > gain1))
2456 matchLength = mlRep, offset = 0, start = ip;
2458 { size_t offset2=99999999;
2459 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2460 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */
2461 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4);
2462 if ((ml2 >= 4) && (gain2 > gain1)) {
2463 matchLength = ml2, offset = offset2, start = ip;
2464 continue; /* search a better one */
2467 /* let's find an even better one */
2468 if ((depth==2) && (ip<ilimit)) {
2470 if ((offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) {
2471 size_t const ml2 = ZSTD_count(ip+4, ip+4-offset_1, iend) + 4;
2472 int const gain2 = (int)(ml2 * 4);
2473 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);
2474 if ((ml2 >= 4) && (gain2 > gain1))
2475 matchLength = ml2, offset = 0, start = ip;
2477 { size_t offset2=99999999;
2478 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2479 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */
2480 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7);
2481 if ((ml2 >= 4) && (gain2 > gain1)) {
2482 matchLength = ml2, offset = offset2, start = ip;
2485 break; /* nothing found : store previous solution */
2489 * start[-offset+ZSTD_REP_MOVE-1] is undefined behavior.
2490 * (-offset+ZSTD_REP_MOVE-1) is unsigned, and is added to start, which
2491 * overflows the pointer, which is undefined behavior.
2495 while ( (start > anchor)
2496 && (start > base+offset-ZSTD_REP_MOVE)
2497 && (start[-1] == (start-offset+ZSTD_REP_MOVE)[-1]) ) /* only search for offset within prefix */
2498 { start--; matchLength++; }
2499 offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE);
2501 /* store sequence */
2503 { size_t const litLength = start - anchor;
2504 ZSTD_storeSeq(seqStorePtr, litLength, anchor, (U32)offset, matchLength-MINMATCH);
2505 anchor = ip = start + matchLength;
2508 /* check immediate repcode */
2509 while ( (ip <= ilimit)
2511 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
2512 /* store sequence */
2513 matchLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
2514 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap repcodes */
2515 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength-MINMATCH);
2518 continue; /* faster when present ... (?) */
2521 /* Save reps for next block */
2522 ctx->repToConfirm[0] = offset_1 ? offset_1 : savedOffset;
2523 ctx->repToConfirm[1] = offset_2 ? offset_2 : savedOffset;
2526 { size_t const lastLLSize = iend - anchor;
2527 memcpy(seqStorePtr->lit, anchor, lastLLSize);
2528 seqStorePtr->lit += lastLLSize;
2533 static void ZSTD_compressBlock_btlazy2(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2535 ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 1, 2);
2538 static void ZSTD_compressBlock_lazy2(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2540 ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 2);
2543 static void ZSTD_compressBlock_lazy(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2545 ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 1);
2548 static void ZSTD_compressBlock_greedy(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2550 ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 0);
2555 void ZSTD_compressBlock_lazy_extDict_generic(ZSTD_CCtx* ctx,
2556 const void* src, size_t srcSize,
2557 const U32 searchMethod, const U32 depth)
2559 seqStore_t* seqStorePtr = &(ctx->seqStore);
2560 const BYTE* const istart = (const BYTE*)src;
2561 const BYTE* ip = istart;
2562 const BYTE* anchor = istart;
2563 const BYTE* const iend = istart + srcSize;
2564 const BYTE* const ilimit = iend - 8;
2565 const BYTE* const base = ctx->base;
2566 const U32 dictLimit = ctx->dictLimit;
2567 const U32 lowestIndex = ctx->lowLimit;
2568 const BYTE* const prefixStart = base + dictLimit;
2569 const BYTE* const dictBase = ctx->dictBase;
2570 const BYTE* const dictEnd = dictBase + dictLimit;
2571 const BYTE* const dictStart = dictBase + ctx->lowLimit;
2573 const U32 maxSearches = 1 << ctx->appliedParams.cParams.searchLog;
2574 const U32 mls = ctx->appliedParams.cParams.searchLength;
2576 typedef size_t (*searchMax_f)(ZSTD_CCtx* zc, const BYTE* ip, const BYTE* iLimit,
2578 U32 maxNbAttempts, U32 matchLengthSearch);
2579 searchMax_f searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS_extDict : ZSTD_HcFindBestMatch_extDict_selectMLS;
2581 U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1];
2584 ctx->nextToUpdate3 = ctx->nextToUpdate;
2585 ip += (ip == prefixStart);
2588 while (ip < ilimit) {
2589 size_t matchLength=0;
2591 const BYTE* start=ip+1;
2592 U32 current = (U32)(ip-base);
2595 { const U32 repIndex = (U32)(current+1 - offset_1);
2596 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2597 const BYTE* const repMatch = repBase + repIndex;
2598 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2599 if (MEM_read32(ip+1) == MEM_read32(repMatch)) {
2600 /* repcode detected we should take it */
2601 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2602 matchLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repEnd, prefixStart) + 4;
2603 if (depth==0) goto _storeSequence;
2606 /* first search (depth 0) */
2607 { size_t offsetFound = 99999999;
2608 size_t const ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls);
2609 if (ml2 > matchLength)
2610 matchLength = ml2, start = ip, offset=offsetFound;
2613 if (matchLength < 4) {
2614 ip += ((ip-anchor) >> g_searchStrength) + 1; /* jump faster over incompressible sections */
2618 /* let's try to find a better solution */
2625 const U32 repIndex = (U32)(current - offset_1);
2626 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2627 const BYTE* const repMatch = repBase + repIndex;
2628 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2629 if (MEM_read32(ip) == MEM_read32(repMatch)) {
2630 /* repcode detected */
2631 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2632 size_t const repLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;
2633 int const gain2 = (int)(repLength * 3);
2634 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);
2635 if ((repLength >= 4) && (gain2 > gain1))
2636 matchLength = repLength, offset = 0, start = ip;
2639 /* search match, depth 1 */
2640 { size_t offset2=99999999;
2641 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2642 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */
2643 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4);
2644 if ((ml2 >= 4) && (gain2 > gain1)) {
2645 matchLength = ml2, offset = offset2, start = ip;
2646 continue; /* search a better one */
2649 /* let's find an even better one */
2650 if ((depth==2) && (ip<ilimit)) {
2655 const U32 repIndex = (U32)(current - offset_1);
2656 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2657 const BYTE* const repMatch = repBase + repIndex;
2658 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2659 if (MEM_read32(ip) == MEM_read32(repMatch)) {
2660 /* repcode detected */
2661 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2662 size_t const repLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;
2663 int const gain2 = (int)(repLength * 4);
2664 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);
2665 if ((repLength >= 4) && (gain2 > gain1))
2666 matchLength = repLength, offset = 0, start = ip;
2669 /* search match, depth 2 */
2670 { size_t offset2=99999999;
2671 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2672 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */
2673 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7);
2674 if ((ml2 >= 4) && (gain2 > gain1)) {
2675 matchLength = ml2, offset = offset2, start = ip;
2678 break; /* nothing found : store previous solution */
2683 U32 const matchIndex = (U32)((start-base) - (offset - ZSTD_REP_MOVE));
2684 const BYTE* match = (matchIndex < dictLimit) ? dictBase + matchIndex : base + matchIndex;
2685 const BYTE* const mStart = (matchIndex < dictLimit) ? dictStart : prefixStart;
2686 while ((start>anchor) && (match>mStart) && (start[-1] == match[-1])) { start--; match--; matchLength++; } /* catch up */
2687 offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE);
2690 /* store sequence */
2692 { size_t const litLength = start - anchor;
2693 ZSTD_storeSeq(seqStorePtr, litLength, anchor, (U32)offset, matchLength-MINMATCH);
2694 anchor = ip = start + matchLength;
2697 /* check immediate repcode */
2698 while (ip <= ilimit) {
2699 const U32 repIndex = (U32)((ip-base) - offset_2);
2700 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2701 const BYTE* const repMatch = repBase + repIndex;
2702 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2703 if (MEM_read32(ip) == MEM_read32(repMatch)) {
2704 /* repcode detected we should take it */
2705 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2706 matchLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;
2707 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap offset history */
2708 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength-MINMATCH);
2711 continue; /* faster when present ... (?) */
2716 /* Save reps for next block */
2717 ctx->repToConfirm[0] = offset_1; ctx->repToConfirm[1] = offset_2;
2720 { size_t const lastLLSize = iend - anchor;
2721 memcpy(seqStorePtr->lit, anchor, lastLLSize);
2722 seqStorePtr->lit += lastLLSize;
2727 void ZSTD_compressBlock_greedy_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2729 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 0);
2732 static void ZSTD_compressBlock_lazy_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2734 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 1);
2737 static void ZSTD_compressBlock_lazy2_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2739 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 2);
2742 static void ZSTD_compressBlock_btlazy2_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2744 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 1, 2);
2748 /* The optimal parser */
2749 #include "zstd_opt.h"
2751 static void ZSTD_compressBlock_btopt(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2753 #ifdef ZSTD_OPT_H_91842398743
2754 ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 0);
2756 (void)ctx; (void)src; (void)srcSize;
2761 static void ZSTD_compressBlock_btultra(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2763 #ifdef ZSTD_OPT_H_91842398743
2764 ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 1);
2766 (void)ctx; (void)src; (void)srcSize;
2771 static void ZSTD_compressBlock_btopt_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2773 #ifdef ZSTD_OPT_H_91842398743
2774 ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 0);
2776 (void)ctx; (void)src; (void)srcSize;
2781 static void ZSTD_compressBlock_btultra_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2783 #ifdef ZSTD_OPT_H_91842398743
2784 ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 1);
2786 (void)ctx; (void)src; (void)srcSize;
2792 /* ZSTD_selectBlockCompressor() :
2793 * assumption : strat is a valid strategy */
2794 typedef void (*ZSTD_blockCompressor) (ZSTD_CCtx* ctx, const void* src, size_t srcSize);
2795 static ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, int extDict)
2797 static const ZSTD_blockCompressor blockCompressor[2][(unsigned)ZSTD_btultra+1] = {
2798 { ZSTD_compressBlock_fast /* default for 0 */,
2799 ZSTD_compressBlock_fast, ZSTD_compressBlock_doubleFast, ZSTD_compressBlock_greedy,
2800 ZSTD_compressBlock_lazy, ZSTD_compressBlock_lazy2, ZSTD_compressBlock_btlazy2,
2801 ZSTD_compressBlock_btopt, ZSTD_compressBlock_btultra },
2802 { ZSTD_compressBlock_fast_extDict /* default for 0 */,
2803 ZSTD_compressBlock_fast_extDict, ZSTD_compressBlock_doubleFast_extDict, ZSTD_compressBlock_greedy_extDict,
2804 ZSTD_compressBlock_lazy_extDict,ZSTD_compressBlock_lazy2_extDict, ZSTD_compressBlock_btlazy2_extDict,
2805 ZSTD_compressBlock_btopt_extDict, ZSTD_compressBlock_btultra_extDict }
2807 ZSTD_STATIC_ASSERT((unsigned)ZSTD_fast == 1);
2808 assert((U32)strat >= (U32)ZSTD_fast);
2809 assert((U32)strat <= (U32)ZSTD_btultra);
2811 return blockCompressor[extDict!=0][(U32)strat];
2815 static size_t ZSTD_compressBlock_internal(ZSTD_CCtx* zc, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2817 ZSTD_blockCompressor const blockCompressor = ZSTD_selectBlockCompressor(zc->appliedParams.cParams.strategy, zc->lowLimit < zc->dictLimit);
2818 const BYTE* const base = zc->base;
2819 const BYTE* const istart = (const BYTE*)src;
2820 const U32 current = (U32)(istart-base);
2821 if (srcSize < MIN_CBLOCK_SIZE+ZSTD_blockHeaderSize+1) return 0; /* don't even attempt compression below a certain srcSize */
2822 ZSTD_resetSeqStore(&(zc->seqStore));
2823 if (current > zc->nextToUpdate + 384)
2824 zc->nextToUpdate = current - MIN(192, (U32)(current - zc->nextToUpdate - 384)); /* limited update after finding a very long match */
2825 blockCompressor(zc, src, srcSize);
2826 return ZSTD_compressSequences(zc, dst, dstCapacity, srcSize);
2830 /*! ZSTD_compress_frameChunk() :
2831 * Compress a chunk of data into one or multiple blocks.
2832 * All blocks will be terminated, all input will be consumed.
2833 * Function will issue an error if there is not enough `dstCapacity` to hold the compressed content.
2834 * Frame is supposed already started (header already produced)
2835 * @return : compressed size, or an error code
2837 static size_t ZSTD_compress_frameChunk (ZSTD_CCtx* cctx,
2838 void* dst, size_t dstCapacity,
2839 const void* src, size_t srcSize,
2842 size_t blockSize = cctx->blockSize;
2843 size_t remaining = srcSize;
2844 const BYTE* ip = (const BYTE*)src;
2845 BYTE* const ostart = (BYTE*)dst;
2847 U32 const maxDist = 1 << cctx->appliedParams.cParams.windowLog;
2849 if (cctx->appliedParams.fParams.checksumFlag && srcSize)
2850 XXH64_update(&cctx->xxhState, src, srcSize);
2853 U32 const lastBlock = lastFrameChunk & (blockSize >= remaining);
2856 if (dstCapacity < ZSTD_blockHeaderSize + MIN_CBLOCK_SIZE)
2857 return ERROR(dstSize_tooSmall); /* not enough space to store compressed block */
2858 if (remaining < blockSize) blockSize = remaining;
2860 /* preemptive overflow correction */
2861 if (cctx->lowLimit > (3U<<29)) {
2862 U32 const cycleMask = (1 << ZSTD_cycleLog(cctx->appliedParams.cParams.hashLog, cctx->appliedParams.cParams.strategy)) - 1;
2863 U32 const current = (U32)(ip - cctx->base);
2864 U32 const newCurrent = (current & cycleMask) + (1 << cctx->appliedParams.cParams.windowLog);
2865 U32 const correction = current - newCurrent;
2866 ZSTD_STATIC_ASSERT(ZSTD_WINDOWLOG_MAX_64 <= 30);
2867 ZSTD_reduceIndex(cctx, correction);
2868 cctx->base += correction;
2869 cctx->dictBase += correction;
2870 cctx->lowLimit -= correction;
2871 cctx->dictLimit -= correction;
2872 if (cctx->nextToUpdate < correction) cctx->nextToUpdate = 0;
2873 else cctx->nextToUpdate -= correction;
2876 if ((U32)(ip+blockSize - cctx->base) > cctx->loadedDictEnd + maxDist) {
2877 /* enforce maxDist */
2878 U32 const newLowLimit = (U32)(ip+blockSize - cctx->base) - maxDist;
2879 if (cctx->lowLimit < newLowLimit) cctx->lowLimit = newLowLimit;
2880 if (cctx->dictLimit < cctx->lowLimit) cctx->dictLimit = cctx->lowLimit;
2883 cSize = ZSTD_compressBlock_internal(cctx, op+ZSTD_blockHeaderSize, dstCapacity-ZSTD_blockHeaderSize, ip, blockSize);
2884 if (ZSTD_isError(cSize)) return cSize;
2886 if (cSize == 0) { /* block is not compressible */
2887 U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(blockSize << 3);
2888 if (blockSize + ZSTD_blockHeaderSize > dstCapacity) return ERROR(dstSize_tooSmall);
2889 MEM_writeLE32(op, cBlockHeader24); /* no pb, 4th byte will be overwritten */
2890 memcpy(op + ZSTD_blockHeaderSize, ip, blockSize);
2891 cSize = ZSTD_blockHeaderSize+blockSize;
2893 U32 const cBlockHeader24 = lastBlock + (((U32)bt_compressed)<<1) + (U32)(cSize << 3);
2894 MEM_writeLE24(op, cBlockHeader24);
2895 cSize += ZSTD_blockHeaderSize;
2898 remaining -= blockSize;
2899 dstCapacity -= cSize;
2904 if (lastFrameChunk && (op>ostart)) cctx->stage = ZSTDcs_ending;
2909 static size_t ZSTD_writeFrameHeader(void* dst, size_t dstCapacity,
2910 ZSTD_parameters params, U64 pledgedSrcSize, U32 dictID)
2911 { BYTE* const op = (BYTE*)dst;
2912 U32 const dictIDSizeCodeLength = (dictID>0) + (dictID>=256) + (dictID>=65536); /* 0-3 */
2913 U32 const dictIDSizeCode = params.fParams.noDictIDFlag ? 0 : dictIDSizeCodeLength; /* 0-3 */
2914 U32 const checksumFlag = params.fParams.checksumFlag>0;
2915 U32 const windowSize = 1U << params.cParams.windowLog;
2916 U32 const singleSegment = params.fParams.contentSizeFlag && (windowSize >= pledgedSrcSize);
2917 BYTE const windowLogByte = (BYTE)((params.cParams.windowLog - ZSTD_WINDOWLOG_ABSOLUTEMIN) << 3);
2918 U32 const fcsCode = params.fParams.contentSizeFlag ?
2919 (pledgedSrcSize>=256) + (pledgedSrcSize>=65536+256) + (pledgedSrcSize>=0xFFFFFFFFU) : 0; /* 0-3 */
2920 BYTE const frameHeaderDecriptionByte = (BYTE)(dictIDSizeCode + (checksumFlag<<2) + (singleSegment<<5) + (fcsCode<<6) );
2923 if (dstCapacity < ZSTD_frameHeaderSize_max) return ERROR(dstSize_tooSmall);
2924 DEBUGLOG(5, "ZSTD_writeFrameHeader : dictIDFlag : %u ; dictID : %u ; dictIDSizeCode : %u",
2925 !params.fParams.noDictIDFlag, dictID, dictIDSizeCode);
2927 MEM_writeLE32(dst, ZSTD_MAGICNUMBER);
2928 op[4] = frameHeaderDecriptionByte; pos=5;
2929 if (!singleSegment) op[pos++] = windowLogByte;
2930 switch(dictIDSizeCode)
2932 default: assert(0); /* impossible */
2934 case 1 : op[pos] = (BYTE)(dictID); pos++; break;
2935 case 2 : MEM_writeLE16(op+pos, (U16)dictID); pos+=2; break;
2936 case 3 : MEM_writeLE32(op+pos, dictID); pos+=4; break;
2940 default: assert(0); /* impossible */
2941 case 0 : if (singleSegment) op[pos++] = (BYTE)(pledgedSrcSize); break;
2942 case 1 : MEM_writeLE16(op+pos, (U16)(pledgedSrcSize-256)); pos+=2; break;
2943 case 2 : MEM_writeLE32(op+pos, (U32)(pledgedSrcSize)); pos+=4; break;
2944 case 3 : MEM_writeLE64(op+pos, (U64)(pledgedSrcSize)); pos+=8; break;
2950 static size_t ZSTD_compressContinue_internal (ZSTD_CCtx* cctx,
2951 void* dst, size_t dstCapacity,
2952 const void* src, size_t srcSize,
2953 U32 frame, U32 lastFrameChunk)
2955 const BYTE* const ip = (const BYTE*) src;
2958 DEBUGLOG(5, "ZSTD_compressContinue_internal");
2959 DEBUGLOG(5, "stage: %u", cctx->stage);
2960 if (cctx->stage==ZSTDcs_created) return ERROR(stage_wrong); /* missing init (ZSTD_compressBegin) */
2962 if (frame && (cctx->stage==ZSTDcs_init)) {
2963 fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, cctx->appliedParams,
2964 cctx->pledgedSrcSizePlusOne-1, cctx->dictID);
2965 if (ZSTD_isError(fhSize)) return fhSize;
2966 dstCapacity -= fhSize;
2967 dst = (char*)dst + fhSize;
2968 cctx->stage = ZSTDcs_ongoing;
2971 /* Check if blocks follow each other */
2972 if (src != cctx->nextSrc) {
2973 /* not contiguous */
2974 ptrdiff_t const delta = cctx->nextSrc - ip;
2975 cctx->lowLimit = cctx->dictLimit;
2976 cctx->dictLimit = (U32)(cctx->nextSrc - cctx->base);
2977 cctx->dictBase = cctx->base;
2978 cctx->base -= delta;
2979 cctx->nextToUpdate = cctx->dictLimit;
2980 if (cctx->dictLimit - cctx->lowLimit < HASH_READ_SIZE) cctx->lowLimit = cctx->dictLimit; /* too small extDict */
2983 /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
2984 if ((ip+srcSize > cctx->dictBase + cctx->lowLimit) & (ip < cctx->dictBase + cctx->dictLimit)) {
2985 ptrdiff_t const highInputIdx = (ip + srcSize) - cctx->dictBase;
2986 U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)cctx->dictLimit) ? cctx->dictLimit : (U32)highInputIdx;
2987 cctx->lowLimit = lowLimitMax;
2990 cctx->nextSrc = ip + srcSize;
2993 size_t const cSize = frame ?
2994 ZSTD_compress_frameChunk (cctx, dst, dstCapacity, src, srcSize, lastFrameChunk) :
2995 ZSTD_compressBlock_internal (cctx, dst, dstCapacity, src, srcSize);
2996 if (ZSTD_isError(cSize)) return cSize;
2997 cctx->consumedSrcSize += srcSize;
2998 return cSize + fhSize;
3004 size_t ZSTD_compressContinue (ZSTD_CCtx* cctx,
3005 void* dst, size_t dstCapacity,
3006 const void* src, size_t srcSize)
3008 return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 1 /* frame mode */, 0 /* last chunk */);
3012 size_t ZSTD_getBlockSize(const ZSTD_CCtx* cctx)
3014 U32 const cLevel = cctx->compressionLevel;
3015 ZSTD_compressionParameters cParams = (cLevel == ZSTD_CLEVEL_CUSTOM) ?
3016 cctx->appliedParams.cParams :
3017 ZSTD_getCParams(cLevel, 0, 0);
3018 return MIN (ZSTD_BLOCKSIZE_MAX, 1 << cParams.windowLog);
3021 size_t ZSTD_compressBlock(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3023 size_t const blockSizeMax = ZSTD_getBlockSize(cctx);
3024 if (srcSize > blockSizeMax) return ERROR(srcSize_wrong);
3025 return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 0 /* frame mode */, 0 /* last chunk */);
3028 /*! ZSTD_loadDictionaryContent() :
3029 * @return : 0, or an error code
3031 static size_t ZSTD_loadDictionaryContent(ZSTD_CCtx* zc, const void* src, size_t srcSize)
3033 const BYTE* const ip = (const BYTE*) src;
3034 const BYTE* const iend = ip + srcSize;
3036 /* input becomes current prefix */
3037 zc->lowLimit = zc->dictLimit;
3038 zc->dictLimit = (U32)(zc->nextSrc - zc->base);
3039 zc->dictBase = zc->base;
3040 zc->base += ip - zc->nextSrc;
3041 zc->nextToUpdate = zc->dictLimit;
3042 zc->loadedDictEnd = zc->forceWindow ? 0 : (U32)(iend - zc->base);
3045 if (srcSize <= HASH_READ_SIZE) return 0;
3047 switch(zc->appliedParams.cParams.strategy)
3050 ZSTD_fillHashTable (zc, iend, zc->appliedParams.cParams.searchLength);
3054 ZSTD_fillDoubleHashTable (zc, iend, zc->appliedParams.cParams.searchLength);
3060 if (srcSize >= HASH_READ_SIZE)
3061 ZSTD_insertAndFindFirstIndex(zc, iend-HASH_READ_SIZE, zc->appliedParams.cParams.searchLength);
3067 if (srcSize >= HASH_READ_SIZE)
3068 ZSTD_updateTree(zc, iend-HASH_READ_SIZE, iend, 1 << zc->appliedParams.cParams.searchLog, zc->appliedParams.cParams.searchLength);
3072 assert(0); /* not possible : not a valid strategy id */
3075 zc->nextToUpdate = (U32)(iend - zc->base);
3080 /* Dictionaries that assign zero probability to symbols that show up causes problems
3081 when FSE encoding. Refuse dictionaries that assign zero probability to symbols
3082 that we may encounter during compression.
3083 NOTE: This behavior is not standard and could be improved in the future. */
3084 static size_t ZSTD_checkDictNCount(short* normalizedCounter, unsigned dictMaxSymbolValue, unsigned maxSymbolValue) {
3086 if (dictMaxSymbolValue < maxSymbolValue) return ERROR(dictionary_corrupted);
3087 for (s = 0; s <= maxSymbolValue; ++s) {
3088 if (normalizedCounter[s] == 0) return ERROR(dictionary_corrupted);
3094 /* Dictionary format :
3096 * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#dictionary-format
3098 /*! ZSTD_loadZstdDictionary() :
3099 * @return : 0, or an error code
3100 * assumptions : magic number supposed already checked
3101 * dictSize supposed > 8
3103 static size_t ZSTD_loadZstdDictionary(ZSTD_CCtx* cctx, const void* dict, size_t dictSize)
3105 const BYTE* dictPtr = (const BYTE*)dict;
3106 const BYTE* const dictEnd = dictPtr + dictSize;
3107 short offcodeNCount[MaxOff+1];
3108 unsigned offcodeMaxValue = MaxOff;
3109 BYTE scratchBuffer[1<<MAX(MLFSELog,LLFSELog)];
3111 dictPtr += 4; /* skip magic number */
3112 cctx->dictID = cctx->appliedParams.fParams.noDictIDFlag ? 0 : MEM_readLE32(dictPtr);
3115 { size_t const hufHeaderSize = HUF_readCTable(cctx->hufCTable, 255, dictPtr, dictEnd-dictPtr);
3116 if (HUF_isError(hufHeaderSize)) return ERROR(dictionary_corrupted);
3117 dictPtr += hufHeaderSize;
3120 { unsigned offcodeLog;
3121 size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
3122 if (FSE_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
3123 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
3124 /* Defer checking offcodeMaxValue because we need to know the size of the dictionary content */
3125 CHECK_E( FSE_buildCTable_wksp(cctx->offcodeCTable, offcodeNCount, offcodeMaxValue, offcodeLog, scratchBuffer, sizeof(scratchBuffer)),
3126 dictionary_corrupted);
3127 dictPtr += offcodeHeaderSize;
3130 { short matchlengthNCount[MaxML+1];
3131 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
3132 size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
3133 if (FSE_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
3134 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
3135 /* Every match length code must have non-zero probability */
3136 CHECK_F( ZSTD_checkDictNCount(matchlengthNCount, matchlengthMaxValue, MaxML));
3137 CHECK_E( FSE_buildCTable_wksp(cctx->matchlengthCTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, scratchBuffer, sizeof(scratchBuffer)),
3138 dictionary_corrupted);
3139 dictPtr += matchlengthHeaderSize;
3142 { short litlengthNCount[MaxLL+1];
3143 unsigned litlengthMaxValue = MaxLL, litlengthLog;
3144 size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
3145 if (FSE_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
3146 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
3147 /* Every literal length code must have non-zero probability */
3148 CHECK_F( ZSTD_checkDictNCount(litlengthNCount, litlengthMaxValue, MaxLL));
3149 CHECK_E( FSE_buildCTable_wksp(cctx->litlengthCTable, litlengthNCount, litlengthMaxValue, litlengthLog, scratchBuffer, sizeof(scratchBuffer)),
3150 dictionary_corrupted);
3151 dictPtr += litlengthHeaderSize;
3154 if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
3155 cctx->rep[0] = MEM_readLE32(dictPtr+0);
3156 cctx->rep[1] = MEM_readLE32(dictPtr+4);
3157 cctx->rep[2] = MEM_readLE32(dictPtr+8);
3160 { size_t const dictContentSize = (size_t)(dictEnd - dictPtr);
3161 U32 offcodeMax = MaxOff;
3162 if (dictContentSize <= ((U32)-1) - 128 KB) {
3163 U32 const maxOffset = (U32)dictContentSize + 128 KB; /* The maximum offset that must be supported */
3164 offcodeMax = ZSTD_highbit32(maxOffset); /* Calculate minimum offset code required to represent maxOffset */
3166 /* All offset values <= dictContentSize + 128 KB must be representable */
3167 CHECK_F (ZSTD_checkDictNCount(offcodeNCount, offcodeMaxValue, MIN(offcodeMax, MaxOff)));
3168 /* All repCodes must be <= dictContentSize and != 0*/
3170 for (u=0; u<3; u++) {
3171 if (cctx->rep[u] == 0) return ERROR(dictionary_corrupted);
3172 if (cctx->rep[u] > dictContentSize) return ERROR(dictionary_corrupted);
3175 cctx->fseCTables_ready = 1;
3176 cctx->hufCTable_repeatMode = HUF_repeat_valid;
3177 return ZSTD_loadDictionaryContent(cctx, dictPtr, dictContentSize);
3181 /** ZSTD_compress_insertDictionary() :
3182 * @return : 0, or an error code */
3183 static size_t ZSTD_compress_insertDictionary(ZSTD_CCtx* cctx,
3184 const void* dict, size_t dictSize,
3185 ZSTD_dictMode_e dictMode)
3187 DEBUGLOG(5, "ZSTD_compress_insertDictionary");
3188 if ((dict==NULL) || (dictSize<=8)) return 0;
3190 /* dict restricted modes */
3191 if (dictMode==ZSTD_dm_rawContent)
3192 return ZSTD_loadDictionaryContent(cctx, dict, dictSize);
3194 if (MEM_readLE32(dict) != ZSTD_MAGIC_DICTIONARY) {
3195 if (dictMode == ZSTD_dm_auto) {
3196 DEBUGLOG(5, "raw content dictionary detected");
3197 return ZSTD_loadDictionaryContent(cctx, dict, dictSize);
3199 if (dictMode == ZSTD_dm_fullDict)
3200 return ERROR(dictionary_wrong);
3201 assert(0); /* impossible */
3204 /* dict as full zstd dictionary */
3205 return ZSTD_loadZstdDictionary(cctx, dict, dictSize);
3208 /*! ZSTD_compressBegin_internal() :
3209 * @return : 0, or an error code */
3210 static size_t ZSTD_compressBegin_internal(ZSTD_CCtx* cctx,
3211 const void* dict, size_t dictSize,
3212 ZSTD_dictMode_e dictMode,
3213 const ZSTD_CDict* cdict,
3214 ZSTD_parameters params, U64 pledgedSrcSize,
3215 ZSTD_buffered_policy_e zbuff)
3217 DEBUGLOG(4, "ZSTD_compressBegin_internal");
3218 DEBUGLOG(4, "dict ? %s", dict ? "dict" : (cdict ? "cdict" : "none"));
3219 DEBUGLOG(4, "dictMode : %u", (U32)dictMode);
3220 /* params are supposed to be fully validated at this point */
3221 assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
3222 assert(!((dict) && (cdict))); /* either dict or cdict, not both */
3224 if (cdict && cdict->dictContentSize>0) {
3225 return ZSTD_copyCCtx_internal(cctx, cdict->refContext,
3226 params.fParams, pledgedSrcSize,
3230 CHECK_F( ZSTD_resetCCtx_internal(cctx, params, pledgedSrcSize,
3231 ZSTDcrp_continue, zbuff) );
3232 return ZSTD_compress_insertDictionary(cctx, dict, dictSize, dictMode);
3236 /*! ZSTD_compressBegin_advanced() :
3237 * @return : 0, or an error code */
3238 size_t ZSTD_compressBegin_advanced(ZSTD_CCtx* cctx,
3239 const void* dict, size_t dictSize,
3240 ZSTD_parameters params, unsigned long long pledgedSrcSize)
3242 /* compression parameters verification and optimization */
3243 CHECK_F(ZSTD_checkCParams(params.cParams));
3244 return ZSTD_compressBegin_internal(cctx, dict, dictSize, ZSTD_dm_auto, NULL,
3245 params, pledgedSrcSize, ZSTDb_not_buffered);
3249 size_t ZSTD_compressBegin_usingDict(ZSTD_CCtx* cctx, const void* dict, size_t dictSize, int compressionLevel)
3251 ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, dictSize);
3252 return ZSTD_compressBegin_internal(cctx, dict, dictSize, ZSTD_dm_auto, NULL,
3253 params, 0, ZSTDb_not_buffered);
3257 size_t ZSTD_compressBegin(ZSTD_CCtx* cctx, int compressionLevel)
3259 return ZSTD_compressBegin_usingDict(cctx, NULL, 0, compressionLevel);
3263 /*! ZSTD_writeEpilogue() :
3265 * @return : nb of bytes written into dst (or an error code) */
3266 static size_t ZSTD_writeEpilogue(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity)
3268 BYTE* const ostart = (BYTE*)dst;
3272 DEBUGLOG(5, "ZSTD_writeEpilogue");
3273 if (cctx->stage == ZSTDcs_created) return ERROR(stage_wrong); /* init missing */
3275 /* special case : empty frame */
3276 if (cctx->stage == ZSTDcs_init) {
3277 fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, cctx->appliedParams, 0, 0);
3278 if (ZSTD_isError(fhSize)) return fhSize;
3279 dstCapacity -= fhSize;
3281 cctx->stage = ZSTDcs_ongoing;
3284 if (cctx->stage != ZSTDcs_ending) {
3285 /* write one last empty block, make it the "last" block */
3286 U32 const cBlockHeader24 = 1 /* last block */ + (((U32)bt_raw)<<1) + 0;
3287 if (dstCapacity<4) return ERROR(dstSize_tooSmall);
3288 MEM_writeLE32(op, cBlockHeader24);
3289 op += ZSTD_blockHeaderSize;
3290 dstCapacity -= ZSTD_blockHeaderSize;
3293 if (cctx->appliedParams.fParams.checksumFlag) {
3294 U32 const checksum = (U32) XXH64_digest(&cctx->xxhState);
3295 if (dstCapacity<4) return ERROR(dstSize_tooSmall);
3296 MEM_writeLE32(op, checksum);
3300 cctx->stage = ZSTDcs_created; /* return to "created but no init" status */
3305 size_t ZSTD_compressEnd (ZSTD_CCtx* cctx,
3306 void* dst, size_t dstCapacity,
3307 const void* src, size_t srcSize)
3310 size_t const cSize = ZSTD_compressContinue_internal(cctx,
3311 dst, dstCapacity, src, srcSize,
3312 1 /* frame mode */, 1 /* last chunk */);
3313 if (ZSTD_isError(cSize)) return cSize;
3314 endResult = ZSTD_writeEpilogue(cctx, (char*)dst + cSize, dstCapacity-cSize);
3315 if (ZSTD_isError(endResult)) return endResult;
3316 if (cctx->appliedParams.fParams.contentSizeFlag) { /* control src size */
3317 DEBUGLOG(5, "end of frame : controlling src size");
3318 if (cctx->pledgedSrcSizePlusOne != cctx->consumedSrcSize+1) {
3319 DEBUGLOG(5, "error : pledgedSrcSize = %u, while realSrcSize = %u",
3320 (U32)cctx->pledgedSrcSizePlusOne-1, (U32)cctx->consumedSrcSize);
3321 return ERROR(srcSize_wrong);
3323 return cSize + endResult;
3327 static size_t ZSTD_compress_internal (ZSTD_CCtx* cctx,
3328 void* dst, size_t dstCapacity,
3329 const void* src, size_t srcSize,
3330 const void* dict,size_t dictSize,
3331 ZSTD_parameters params)
3333 CHECK_F( ZSTD_compressBegin_internal(cctx, dict, dictSize, ZSTD_dm_auto, NULL,
3334 params, srcSize, ZSTDb_not_buffered) );
3335 return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
3338 size_t ZSTD_compress_advanced (ZSTD_CCtx* ctx,
3339 void* dst, size_t dstCapacity,
3340 const void* src, size_t srcSize,
3341 const void* dict,size_t dictSize,
3342 ZSTD_parameters params)
3344 CHECK_F(ZSTD_checkCParams(params.cParams));
3345 return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, dict, dictSize, params);
3348 size_t ZSTD_compress_usingDict(ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize,
3349 const void* dict, size_t dictSize, int compressionLevel)
3351 ZSTD_parameters params = ZSTD_getParams(compressionLevel, srcSize, dict ? dictSize : 0);
3352 params.fParams.contentSizeFlag = 1;
3353 return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, dict, dictSize, params);
3356 size_t ZSTD_compressCCtx (ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel)
3358 return ZSTD_compress_usingDict(ctx, dst, dstCapacity, src, srcSize, NULL, 0, compressionLevel);
3361 size_t ZSTD_compress(void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel)
3365 memset(&ctxBody, 0, sizeof(ctxBody));
3366 ctxBody.customMem = ZSTD_defaultCMem;
3367 result = ZSTD_compressCCtx(&ctxBody, dst, dstCapacity, src, srcSize, compressionLevel);
3368 ZSTD_free(ctxBody.workSpace, ZSTD_defaultCMem); /* can't free ctxBody itself, as it's on stack; free only heap content */
3373 /* ===== Dictionary API ===== */
3375 /*! ZSTD_estimateCDictSize_advanced() :
3376 * Estimate amount of memory that will be needed to create a dictionary with following arguments */
3377 size_t ZSTD_estimateCDictSize_advanced(size_t dictSize, ZSTD_compressionParameters cParams, unsigned byReference)
3379 DEBUGLOG(5, "sizeof(ZSTD_CDict) : %u", (U32)sizeof(ZSTD_CDict));
3380 DEBUGLOG(5, "CCtx estimate : %u", (U32)ZSTD_estimateCCtxSize_advanced(cParams));
3381 return sizeof(ZSTD_CDict) + ZSTD_estimateCCtxSize_advanced(cParams)
3382 + (byReference ? 0 : dictSize);
3385 size_t ZSTD_estimateCDictSize(size_t dictSize, int compressionLevel)
3387 ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, 0, dictSize);
3388 return ZSTD_estimateCDictSize_advanced(dictSize, cParams, 0);
3391 size_t ZSTD_sizeof_CDict(const ZSTD_CDict* cdict)
3393 if (cdict==NULL) return 0; /* support sizeof on NULL */
3394 DEBUGLOG(5, "sizeof(*cdict) : %u", (U32)sizeof(*cdict));
3395 DEBUGLOG(5, "ZSTD_sizeof_CCtx : %u", (U32)ZSTD_sizeof_CCtx(cdict->refContext));
3396 return ZSTD_sizeof_CCtx(cdict->refContext) + (cdict->dictBuffer ? cdict->dictContentSize : 0) + sizeof(*cdict);
3399 static ZSTD_parameters ZSTD_makeParams(ZSTD_compressionParameters cParams, ZSTD_frameParameters fParams)
3401 ZSTD_parameters params;
3402 params.cParams = cParams;
3403 params.fParams = fParams;
3407 static size_t ZSTD_initCDict_internal(
3409 const void* dictBuffer, size_t dictSize,
3410 unsigned byReference, ZSTD_dictMode_e dictMode,
3411 ZSTD_compressionParameters cParams)
3413 DEBUGLOG(5, "ZSTD_initCDict_internal, mode %u", (U32)dictMode);
3414 if ((byReference) || (!dictBuffer) || (!dictSize)) {
3415 cdict->dictBuffer = NULL;
3416 cdict->dictContent = dictBuffer;
3418 void* const internalBuffer = ZSTD_malloc(dictSize, cdict->refContext->customMem);
3419 cdict->dictBuffer = internalBuffer;
3420 cdict->dictContent = internalBuffer;
3421 if (!internalBuffer) return ERROR(memory_allocation);
3422 memcpy(internalBuffer, dictBuffer, dictSize);
3424 cdict->dictContentSize = dictSize;
3426 { ZSTD_frameParameters const fParams = { 0 /* contentSizeFlag */,
3427 0 /* checksumFlag */, 0 /* noDictIDFlag */ }; /* dummy */
3428 ZSTD_parameters const params = ZSTD_makeParams(cParams, fParams);
3429 CHECK_F( ZSTD_compressBegin_internal(cdict->refContext,
3430 cdict->dictContent, dictSize, dictMode,
3432 params, ZSTD_CONTENTSIZE_UNKNOWN,
3433 ZSTDb_not_buffered) );
3439 ZSTD_CDict* ZSTD_createCDict_advanced(const void* dictBuffer, size_t dictSize,
3440 unsigned byReference, ZSTD_dictMode_e dictMode,
3441 ZSTD_compressionParameters cParams, ZSTD_customMem customMem)
3443 DEBUGLOG(5, "ZSTD_createCDict_advanced, mode %u", (U32)dictMode);
3444 if (!customMem.customAlloc ^ !customMem.customFree) return NULL;
3446 { ZSTD_CDict* const cdict = (ZSTD_CDict*)ZSTD_malloc(sizeof(ZSTD_CDict), customMem);
3447 ZSTD_CCtx* const cctx = ZSTD_createCCtx_advanced(customMem);
3449 if (!cdict || !cctx) {
3450 ZSTD_free(cdict, customMem);
3451 ZSTD_freeCCtx(cctx);
3454 cdict->refContext = cctx;
3456 if (ZSTD_isError( ZSTD_initCDict_internal(cdict,
3457 dictBuffer, dictSize,
3458 byReference, dictMode,
3460 ZSTD_freeCDict(cdict);
3468 ZSTD_CDict* ZSTD_createCDict(const void* dict, size_t dictSize, int compressionLevel)
3470 ZSTD_compressionParameters cParams = ZSTD_getCParams(compressionLevel, 0, dictSize);
3471 return ZSTD_createCDict_advanced(dict, dictSize,
3472 0 /* byReference */, ZSTD_dm_auto,
3473 cParams, ZSTD_defaultCMem);
3476 ZSTD_CDict* ZSTD_createCDict_byReference(const void* dict, size_t dictSize, int compressionLevel)
3478 ZSTD_compressionParameters cParams = ZSTD_getCParams(compressionLevel, 0, dictSize);
3479 return ZSTD_createCDict_advanced(dict, dictSize,
3480 1 /* byReference */, ZSTD_dm_auto,
3481 cParams, ZSTD_defaultCMem);
3484 size_t ZSTD_freeCDict(ZSTD_CDict* cdict)
3486 if (cdict==NULL) return 0; /* support free on NULL */
3487 { ZSTD_customMem const cMem = cdict->refContext->customMem;
3488 ZSTD_freeCCtx(cdict->refContext);
3489 ZSTD_free(cdict->dictBuffer, cMem);
3490 ZSTD_free(cdict, cMem);
3495 /*! ZSTD_initStaticCDict_advanced() :
3496 * Generate a digested dictionary in provided memory area.
3497 * workspace: The memory area to emplace the dictionary into.
3498 * Provided pointer must 8-bytes aligned.
3499 * It must outlive dictionary usage.
3500 * workspaceSize: Use ZSTD_estimateCDictSize()
3501 * to determine how large workspace must be.
3502 * cParams : use ZSTD_getCParams() to transform a compression level
3503 * into its relevants cParams.
3504 * @return : pointer to ZSTD_CDict*, or NULL if error (size too small)
3505 * Note : there is no corresponding "free" function.
3506 * Since workspace was allocated externally, it must be freed externally.
3508 ZSTD_CDict* ZSTD_initStaticCDict(void* workspace, size_t workspaceSize,
3509 const void* dict, size_t dictSize,
3510 unsigned byReference, ZSTD_dictMode_e dictMode,
3511 ZSTD_compressionParameters cParams)
3513 size_t const cctxSize = ZSTD_estimateCCtxSize_advanced(cParams);
3514 size_t const neededSize = sizeof(ZSTD_CDict) + (byReference ? 0 : dictSize)
3516 ZSTD_CDict* const cdict = (ZSTD_CDict*) workspace;
3518 DEBUGLOG(5, "(size_t)workspace & 7 : %u", (U32)(size_t)workspace & 7);
3519 if ((size_t)workspace & 7) return NULL; /* 8-aligned */
3520 DEBUGLOG(5, "(workspaceSize < neededSize) : (%u < %u) => %u",
3521 (U32)workspaceSize, (U32)neededSize, (U32)(workspaceSize < neededSize));
3522 if (workspaceSize < neededSize) return NULL;
3525 memcpy(cdict+1, dict, dictSize);
3527 ptr = (char*)workspace + sizeof(ZSTD_CDict) + dictSize;
3531 cdict->refContext = ZSTD_initStaticCCtx(ptr, cctxSize);
3533 if (ZSTD_isError( ZSTD_initCDict_internal(cdict,
3535 1 /* byReference */, dictMode,
3542 ZSTD_parameters ZSTD_getParamsFromCDict(const ZSTD_CDict* cdict) {
3543 return ZSTD_getParamsFromCCtx(cdict->refContext);
3546 /* ZSTD_compressBegin_usingCDict_advanced() :
3547 * cdict must be != NULL */
3548 size_t ZSTD_compressBegin_usingCDict_advanced(
3549 ZSTD_CCtx* const cctx, const ZSTD_CDict* const cdict,
3550 ZSTD_frameParameters const fParams, unsigned long long const pledgedSrcSize)
3552 if (cdict==NULL) return ERROR(dictionary_wrong);
3553 { ZSTD_parameters params = cdict->refContext->appliedParams;
3554 params.fParams = fParams;
3555 DEBUGLOG(5, "ZSTD_compressBegin_usingCDict_advanced");
3556 return ZSTD_compressBegin_internal(cctx,
3557 NULL, 0, ZSTD_dm_auto,
3559 params, pledgedSrcSize,
3560 ZSTDb_not_buffered);
3564 /* ZSTD_compressBegin_usingCDict() :
3565 * pledgedSrcSize=0 means "unknown"
3566 * if pledgedSrcSize>0, it will enable contentSizeFlag */
3567 size_t ZSTD_compressBegin_usingCDict(ZSTD_CCtx* cctx, const ZSTD_CDict* cdict)
3569 ZSTD_frameParameters const fParams = { 0 /*content*/, 0 /*checksum*/, 0 /*noDictID*/ };
3570 DEBUGLOG(5, "ZSTD_compressBegin_usingCDict : dictIDFlag == %u", !fParams.noDictIDFlag);
3571 return ZSTD_compressBegin_usingCDict_advanced(cctx, cdict, fParams, 0);
3574 size_t ZSTD_compress_usingCDict_advanced(ZSTD_CCtx* cctx,
3575 void* dst, size_t dstCapacity,
3576 const void* src, size_t srcSize,
3577 const ZSTD_CDict* cdict, ZSTD_frameParameters fParams)
3579 CHECK_F (ZSTD_compressBegin_usingCDict_advanced(cctx, cdict, fParams, srcSize)); /* will check if cdict != NULL */
3580 return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
3583 /*! ZSTD_compress_usingCDict() :
3584 * Compression using a digested Dictionary.
3585 * Faster startup than ZSTD_compress_usingDict(), recommended when same dictionary is used multiple times.
3586 * Note that compression parameters are decided at CDict creation time
3587 * while frame parameters are hardcoded */
3588 size_t ZSTD_compress_usingCDict(ZSTD_CCtx* cctx,
3589 void* dst, size_t dstCapacity,
3590 const void* src, size_t srcSize,
3591 const ZSTD_CDict* cdict)
3593 ZSTD_frameParameters const fParams = { 1 /*content*/, 0 /*checksum*/, 0 /*noDictID*/ };
3594 return ZSTD_compress_usingCDict_advanced(cctx, dst, dstCapacity, src, srcSize, cdict, fParams);
3599 /* ******************************************************************
3601 ********************************************************************/
3603 ZSTD_CStream* ZSTD_createCStream(void)
3605 return ZSTD_createCStream_advanced(ZSTD_defaultCMem);
3608 ZSTD_CStream* ZSTD_initStaticCStream(void *workspace, size_t workspaceSize)
3610 return ZSTD_initStaticCCtx(workspace, workspaceSize);
3613 ZSTD_CStream* ZSTD_createCStream_advanced(ZSTD_customMem customMem)
3614 { /* CStream and CCtx are now same object */
3615 return ZSTD_createCCtx_advanced(customMem);
3618 size_t ZSTD_freeCStream(ZSTD_CStream* zcs)
3620 return ZSTD_freeCCtx(zcs); /* same object */
3625 /*====== Initialization ======*/
3627 size_t ZSTD_CStreamInSize(void) { return ZSTD_BLOCKSIZE_MAX; }
3629 size_t ZSTD_CStreamOutSize(void)
3631 return ZSTD_compressBound(ZSTD_BLOCKSIZE_MAX) + ZSTD_blockHeaderSize + 4 /* 32-bits hash */ ;
3634 static size_t ZSTD_resetCStream_internal(ZSTD_CStream* zcs,
3635 const void* dict, size_t dictSize, ZSTD_dictMode_e dictMode,
3636 const ZSTD_CDict* cdict,
3637 ZSTD_parameters params, unsigned long long pledgedSrcSize)
3639 DEBUGLOG(4, "ZSTD_resetCStream_internal");
3640 /* params are supposed to be fully validated at this point */
3641 assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
3642 assert(!((dict) && (cdict))); /* either dict or cdict, not both */
3644 CHECK_F( ZSTD_compressBegin_internal(zcs,
3645 dict, dictSize, dictMode,
3647 params, pledgedSrcSize,
3650 zcs->inToCompress = 0;
3652 zcs->inBuffTarget = zcs->blockSize;
3653 zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0;
3654 zcs->streamStage = zcss_load;
3655 zcs->frameEnded = 0;
3656 return 0; /* ready to go */
3659 size_t ZSTD_resetCStream(ZSTD_CStream* zcs, unsigned long long pledgedSrcSize)
3661 ZSTD_parameters params = zcs->requestedParams;
3662 params.fParams.contentSizeFlag = (pledgedSrcSize > 0);
3663 DEBUGLOG(5, "ZSTD_resetCStream");
3664 if (zcs->compressionLevel != ZSTD_CLEVEL_CUSTOM) {
3665 params.cParams = ZSTD_getCParams(zcs->compressionLevel, pledgedSrcSize, 0 /* dictSize */);
3667 return ZSTD_resetCStream_internal(zcs, NULL, 0, zcs->dictMode, zcs->cdict, params, pledgedSrcSize);
3670 /*! ZSTD_initCStream_internal() :
3671 * Note : not static, but hidden (not exposed). Used by zstdmt_compress.c
3672 * Assumption 1 : params are valid
3673 * Assumption 2 : either dict, or cdict, is defined, not both */
3674 size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs,
3675 const void* dict, size_t dictSize, const ZSTD_CDict* cdict,
3676 ZSTD_parameters params, unsigned long long pledgedSrcSize)
3678 DEBUGLOG(5, "ZSTD_initCStream_internal");
3679 assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
3680 assert(!((dict) && (cdict))); /* either dict or cdict, not both */
3682 if (dict && dictSize >= 8) {
3683 DEBUGLOG(5, "loading dictionary of size %u", (U32)dictSize);
3684 if (zcs->staticSize) { /* static CCtx : never uses malloc */
3685 /* incompatible with internal cdict creation */
3686 return ERROR(memory_allocation);
3688 ZSTD_freeCDict(zcs->cdictLocal);
3689 zcs->cdictLocal = ZSTD_createCDict_advanced(dict, dictSize,
3690 zcs->dictContentByRef, zcs->dictMode,
3691 params.cParams, zcs->customMem);
3692 zcs->cdict = zcs->cdictLocal;
3693 if (zcs->cdictLocal == NULL) return ERROR(memory_allocation);
3696 ZSTD_parameters const cdictParams = ZSTD_getParamsFromCDict(cdict);
3697 params.cParams = cdictParams.cParams; /* cParams are enforced from cdict */
3699 ZSTD_freeCDict(zcs->cdictLocal);
3700 zcs->cdictLocal = NULL;
3704 zcs->requestedParams = params;
3705 zcs->compressionLevel = ZSTD_CLEVEL_CUSTOM;
3706 return ZSTD_resetCStream_internal(zcs, NULL, 0, zcs->dictMode, zcs->cdict, params, pledgedSrcSize);
3709 /* ZSTD_initCStream_usingCDict_advanced() :
3710 * same as ZSTD_initCStream_usingCDict(), with control over frame parameters */
3711 size_t ZSTD_initCStream_usingCDict_advanced(ZSTD_CStream* zcs,
3712 const ZSTD_CDict* cdict,
3713 ZSTD_frameParameters fParams,
3714 unsigned long long pledgedSrcSize)
3715 { /* cannot handle NULL cdict (does not know what to do) */
3716 if (!cdict) return ERROR(dictionary_wrong);
3717 { ZSTD_parameters params = ZSTD_getParamsFromCDict(cdict);
3718 params.fParams = fParams;
3719 return ZSTD_initCStream_internal(zcs,
3721 params, pledgedSrcSize);
3725 /* note : cdict must outlive compression session */
3726 size_t ZSTD_initCStream_usingCDict(ZSTD_CStream* zcs, const ZSTD_CDict* cdict)
3728 ZSTD_frameParameters const fParams = { 0 /* contentSize */, 0 /* checksum */, 0 /* hideDictID */ };
3729 return ZSTD_initCStream_usingCDict_advanced(zcs, cdict, fParams, 0); /* note : will check that cdict != NULL */
3732 size_t ZSTD_initCStream_advanced(ZSTD_CStream* zcs,
3733 const void* dict, size_t dictSize,
3734 ZSTD_parameters params, unsigned long long pledgedSrcSize)
3736 CHECK_F( ZSTD_checkCParams(params.cParams) );
3737 zcs->requestedParams = params;
3738 zcs->compressionLevel = ZSTD_CLEVEL_CUSTOM;
3739 return ZSTD_initCStream_internal(zcs, dict, dictSize, NULL, params, pledgedSrcSize);
3742 size_t ZSTD_initCStream_usingDict(ZSTD_CStream* zcs, const void* dict, size_t dictSize, int compressionLevel)
3744 ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, dictSize);
3745 zcs->compressionLevel = compressionLevel;
3746 return ZSTD_initCStream_internal(zcs, dict, dictSize, NULL, params, 0);
3749 size_t ZSTD_initCStream_srcSize(ZSTD_CStream* zcs, int compressionLevel, unsigned long long pledgedSrcSize)
3751 ZSTD_parameters params = ZSTD_getParams(compressionLevel, pledgedSrcSize, 0);
3752 params.fParams.contentSizeFlag = (pledgedSrcSize>0);
3753 return ZSTD_initCStream_internal(zcs, NULL, 0, NULL, params, pledgedSrcSize);
3756 size_t ZSTD_initCStream(ZSTD_CStream* zcs, int compressionLevel)
3758 ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, 0);
3759 return ZSTD_initCStream_internal(zcs, NULL, 0, NULL, params, 0);
3762 /*====== Compression ======*/
3764 MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity,
3765 const void* src, size_t srcSize)
3767 size_t const length = MIN(dstCapacity, srcSize);
3768 if (length) memcpy(dst, src, length);
3772 /** ZSTD_compressStream_generic():
3773 * internal function for all *compressStream*() variants and *compress_generic()
3774 * @return : hint size for next input */
3775 size_t ZSTD_compressStream_generic(ZSTD_CStream* zcs,
3776 ZSTD_outBuffer* output,
3777 ZSTD_inBuffer* input,
3778 ZSTD_EndDirective const flushMode)
3780 const char* const istart = (const char*)input->src;
3781 const char* const iend = istart + input->size;
3782 const char* ip = istart + input->pos;
3783 char* const ostart = (char*)output->dst;
3784 char* const oend = ostart + output->size;
3785 char* op = ostart + output->pos;
3786 U32 someMoreWork = 1;
3788 /* check expectations */
3789 DEBUGLOG(5, "ZSTD_compressStream_generic, flush=%u", (U32)flushMode);
3790 assert(zcs->inBuff != NULL);
3791 assert(zcs->inBuffSize>0);
3792 assert(zcs->outBuff!= NULL);
3793 assert(zcs->outBuffSize>0);
3794 assert(output->pos <= output->size);
3795 assert(input->pos <= input->size);
3797 while (someMoreWork) {
3798 switch(zcs->streamStage)
3801 /* call ZSTD_initCStream() first ! */
3802 return ERROR(init_missing);
3805 if ( (flushMode == ZSTD_e_end)
3806 && ((size_t)(oend-op) >= ZSTD_compressBound(iend-ip)) /* enough dstCapacity */
3807 && (zcs->inBuffPos == 0) ) {
3808 /* shortcut to compression pass directly into output buffer */
3809 size_t const cSize = ZSTD_compressEnd(zcs,
3810 op, oend-op, ip, iend-ip);
3811 DEBUGLOG(4, "ZSTD_compressEnd : %u", (U32)cSize);
3812 if (ZSTD_isError(cSize)) return cSize;
3815 zcs->frameEnded = 1;
3816 ZSTD_startNewCompression(zcs);
3817 someMoreWork = 0; break;
3819 /* complete loading into inBuffer */
3820 { size_t const toLoad = zcs->inBuffTarget - zcs->inBuffPos;
3821 size_t const loaded = ZSTD_limitCopy(
3822 zcs->inBuff + zcs->inBuffPos, toLoad,
3824 zcs->inBuffPos += loaded;
3826 if ( (flushMode == ZSTD_e_continue)
3827 && (zcs->inBuffPos < zcs->inBuffTarget) ) {
3828 /* not enough input to fill full block : stop here */
3829 someMoreWork = 0; break;
3831 if ( (flushMode == ZSTD_e_flush)
3832 && (zcs->inBuffPos == zcs->inToCompress) ) {
3834 someMoreWork = 0; break;
3837 /* compress current block (note : this stage cannot be stopped in the middle) */
3838 DEBUGLOG(5, "stream compression stage (flushMode==%u)", flushMode);
3841 size_t const iSize = zcs->inBuffPos - zcs->inToCompress;
3842 size_t oSize = oend-op;
3843 unsigned const lastBlock = (flushMode == ZSTD_e_end) && (ip==iend);
3844 if (oSize >= ZSTD_compressBound(iSize))
3845 cDst = op; /* compress into output buffer, to skip flush stage */
3847 cDst = zcs->outBuff, oSize = zcs->outBuffSize;
3849 ZSTD_compressEnd(zcs, cDst, oSize,
3850 zcs->inBuff + zcs->inToCompress, iSize) :
3851 ZSTD_compressContinue(zcs, cDst, oSize,
3852 zcs->inBuff + zcs->inToCompress, iSize);
3853 if (ZSTD_isError(cSize)) return cSize;
3854 zcs->frameEnded = lastBlock;
3855 /* prepare next block */
3856 zcs->inBuffTarget = zcs->inBuffPos + zcs->blockSize;
3857 if (zcs->inBuffTarget > zcs->inBuffSize)
3858 zcs->inBuffPos = 0, zcs->inBuffTarget = zcs->blockSize;
3859 DEBUGLOG(5, "inBuffTarget:%u / inBuffSize:%u",
3860 (U32)zcs->inBuffTarget, (U32)zcs->inBuffSize);
3862 assert(zcs->inBuffTarget <= zcs->inBuffSize);
3863 zcs->inToCompress = zcs->inBuffPos;
3864 if (cDst == op) { /* no need to flush */
3866 if (zcs->frameEnded) {
3867 DEBUGLOG(5, "Frame completed directly in outBuffer");
3869 ZSTD_startNewCompression(zcs);
3873 zcs->outBuffContentSize = cSize;
3874 zcs->outBuffFlushedSize = 0;
3875 zcs->streamStage = zcss_flush; /* pass-through to flush stage */
3879 DEBUGLOG(5, "flush stage");
3880 { size_t const toFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3881 size_t const flushed = ZSTD_limitCopy(op, oend-op,
3882 zcs->outBuff + zcs->outBuffFlushedSize, toFlush);
3883 DEBUGLOG(5, "toFlush: %u into %u ==> flushed: %u",
3884 (U32)toFlush, (U32)(oend-op), (U32)flushed);
3886 zcs->outBuffFlushedSize += flushed;
3887 if (toFlush!=flushed) {
3888 /* flush not fully completed, presumably because dst is too small */
3893 zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0;
3894 if (zcs->frameEnded) {
3895 DEBUGLOG(5, "Frame completed on flush");
3897 ZSTD_startNewCompression(zcs);
3900 zcs->streamStage = zcss_load;
3904 default: /* impossible */
3909 input->pos = ip - istart;
3910 output->pos = op - ostart;
3911 if (zcs->frameEnded) return 0;
3912 { size_t hintInSize = zcs->inBuffTarget - zcs->inBuffPos;
3913 if (hintInSize==0) hintInSize = zcs->blockSize;
3918 size_t ZSTD_compressStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output, ZSTD_inBuffer* input)
3920 /* check conditions */
3921 if (output->pos > output->size) return ERROR(GENERIC);
3922 if (input->pos > input->size) return ERROR(GENERIC);
3924 return ZSTD_compressStream_generic(zcs, output, input, ZSTD_e_continue);
3927 /*! ZSTDMT_initCStream_internal() :
3928 * Private use only. Init streaming operation.
3929 * expects params to be valid.
3930 * must receive dict, or cdict, or none, but not both.
3931 * @return : 0, or an error code */
3932 size_t ZSTDMT_initCStream_internal(ZSTDMT_CCtx* zcs,
3933 const void* dict, size_t dictSize, const ZSTD_CDict* cdict,
3934 ZSTD_parameters params, unsigned long long pledgedSrcSize);
3937 size_t ZSTD_compress_generic (ZSTD_CCtx* cctx,
3938 ZSTD_outBuffer* output,
3939 ZSTD_inBuffer* input,
3940 ZSTD_EndDirective endOp)
3942 /* check conditions */
3943 if (output->pos > output->size) return ERROR(GENERIC);
3944 if (input->pos > input->size) return ERROR(GENERIC);
3947 /* transparent initialization stage */
3948 if (cctx->streamStage == zcss_init) {
3949 const void* const prefix = cctx->prefix;
3950 size_t const prefixSize = cctx->prefixSize;
3951 ZSTD_parameters params = cctx->requestedParams;
3952 if (cctx->compressionLevel != ZSTD_CLEVEL_CUSTOM)
3953 params.cParams = ZSTD_getCParams(cctx->compressionLevel,
3954 cctx->pledgedSrcSizePlusOne-1, 0 /*dictSize*/);
3955 cctx->prefix = NULL; cctx->prefixSize = 0; /* single usage */
3956 assert(prefix==NULL || cctx->cdict==NULL); /* only one can be set */
3958 #ifdef ZSTD_MULTITHREAD
3959 if (cctx->nbThreads > 1) {
3960 DEBUGLOG(4, "call ZSTDMT_initCStream_internal as nbThreads=%u", cctx->nbThreads);
3961 CHECK_F( ZSTDMT_initCStream_internal(cctx->mtctx, prefix, prefixSize, cctx->cdict, params, cctx->pledgedSrcSizePlusOne-1) );
3962 cctx->streamStage = zcss_load;
3966 CHECK_F( ZSTD_resetCStream_internal(cctx, prefix, prefixSize, cctx->dictMode, cctx->cdict, params, cctx->pledgedSrcSizePlusOne-1) );
3969 /* compression stage */
3970 #ifdef ZSTD_MULTITHREAD
3971 if (cctx->nbThreads > 1) {
3972 size_t const flushMin = ZSTDMT_compressStream_generic(cctx->mtctx, output, input, endOp);
3973 DEBUGLOG(5, "ZSTDMT_compressStream_generic : %u", (U32)flushMin);
3974 if ( ZSTD_isError(flushMin)
3975 || (endOp == ZSTD_e_end && flushMin == 0) ) { /* compression completed */
3976 ZSTD_startNewCompression(cctx);
3982 CHECK_F( ZSTD_compressStream_generic(cctx, output, input, endOp) );
3983 DEBUGLOG(5, "completed ZSTD_compress_generic");
3984 return cctx->outBuffContentSize - cctx->outBuffFlushedSize; /* remaining to flush */
3987 size_t ZSTD_compress_generic_simpleArgs (
3989 void* dst, size_t dstCapacity, size_t* dstPos,
3990 const void* src, size_t srcSize, size_t* srcPos,
3991 ZSTD_EndDirective endOp)
3993 ZSTD_outBuffer output = { dst, dstCapacity, *dstPos };
3994 ZSTD_inBuffer input = { src, srcSize, *srcPos };
3995 /* ZSTD_compress_generic() will check validity of dstPos and srcPos */
3996 size_t const cErr = ZSTD_compress_generic(cctx, &output, &input, endOp);
3997 *dstPos = output.pos;
3998 *srcPos = input.pos;
4003 /*====== Finalize ======*/
4005 /*! ZSTD_flushStream() :
4006 * @return : amount of data remaining to flush */
4007 size_t ZSTD_flushStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output)
4009 ZSTD_inBuffer input = { NULL, 0, 0 };
4010 if (output->pos > output->size) return ERROR(GENERIC);
4011 CHECK_F( ZSTD_compressStream_generic(zcs, output, &input, ZSTD_e_flush) );
4012 return zcs->outBuffContentSize - zcs->outBuffFlushedSize; /* remaining to flush */
4016 size_t ZSTD_endStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output)
4018 ZSTD_inBuffer input = { NULL, 0, 0 };
4019 if (output->pos > output->size) return ERROR(GENERIC);
4020 CHECK_F( ZSTD_compressStream_generic(zcs, output, &input, ZSTD_e_end) );
4021 { size_t const lastBlockSize = zcs->frameEnded ? 0 : ZSTD_BLOCKHEADERSIZE;
4022 size_t const checksumSize = zcs->frameEnded ? 0 : zcs->appliedParams.fParams.checksumFlag * 4;
4023 size_t const toFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize + lastBlockSize + checksumSize;
4024 DEBUGLOG(5, "ZSTD_endStream : remaining to flush : %u",
4031 /*-===== Pre-defined compression levels =====-*/
4033 #define ZSTD_MAX_CLEVEL 22
4034 int ZSTD_maxCLevel(void) { return ZSTD_MAX_CLEVEL; }
4036 static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEVEL+1] = {
4037 { /* "default" - guarantees a monotonically increasing memory budget */
4038 /* W, C, H, S, L, TL, strat */
4039 { 18, 12, 12, 1, 7, 16, ZSTD_fast }, /* level 0 - never used */
4040 { 19, 13, 14, 1, 7, 16, ZSTD_fast }, /* level 1 */
4041 { 19, 15, 16, 1, 6, 16, ZSTD_fast }, /* level 2 */
4042 { 20, 16, 17, 1, 5, 16, ZSTD_dfast }, /* level 3 */
4043 { 20, 17, 18, 1, 5, 16, ZSTD_dfast }, /* level 4 */
4044 { 20, 17, 18, 2, 5, 16, ZSTD_greedy }, /* level 5 */
4045 { 21, 17, 19, 2, 5, 16, ZSTD_lazy }, /* level 6 */
4046 { 21, 18, 19, 3, 5, 16, ZSTD_lazy }, /* level 7 */
4047 { 21, 18, 20, 3, 5, 16, ZSTD_lazy2 }, /* level 8 */
4048 { 21, 19, 20, 3, 5, 16, ZSTD_lazy2 }, /* level 9 */
4049 { 21, 19, 21, 4, 5, 16, ZSTD_lazy2 }, /* level 10 */
4050 { 22, 20, 22, 4, 5, 16, ZSTD_lazy2 }, /* level 11 */
4051 { 22, 20, 22, 5, 5, 16, ZSTD_lazy2 }, /* level 12 */
4052 { 22, 21, 22, 5, 5, 16, ZSTD_lazy2 }, /* level 13 */
4053 { 22, 21, 22, 6, 5, 16, ZSTD_lazy2 }, /* level 14 */
4054 { 22, 21, 22, 5, 5, 16, ZSTD_btlazy2 }, /* level 15 */
4055 { 23, 22, 22, 5, 5, 16, ZSTD_btlazy2 }, /* level 16 */
4056 { 23, 22, 22, 4, 5, 24, ZSTD_btopt }, /* level 17 */
4057 { 23, 22, 22, 5, 4, 32, ZSTD_btopt }, /* level 18 */
4058 { 23, 23, 22, 6, 3, 48, ZSTD_btopt }, /* level 19 */
4059 { 25, 25, 23, 7, 3, 64, ZSTD_btultra }, /* level 20 */
4060 { 26, 26, 24, 7, 3,256, ZSTD_btultra }, /* level 21 */
4061 { 27, 27, 25, 9, 3,512, ZSTD_btultra }, /* level 22 */
4063 { /* for srcSize <= 256 KB */
4064 /* W, C, H, S, L, T, strat */
4065 { 0, 0, 0, 0, 0, 0, ZSTD_fast }, /* level 0 - not used */
4066 { 18, 13, 14, 1, 6, 8, ZSTD_fast }, /* level 1 */
4067 { 18, 14, 13, 1, 5, 8, ZSTD_dfast }, /* level 2 */
4068 { 18, 16, 15, 1, 5, 8, ZSTD_dfast }, /* level 3 */
4069 { 18, 15, 17, 1, 5, 8, ZSTD_greedy }, /* level 4.*/
4070 { 18, 16, 17, 4, 5, 8, ZSTD_greedy }, /* level 5.*/
4071 { 18, 16, 17, 3, 5, 8, ZSTD_lazy }, /* level 6.*/
4072 { 18, 17, 17, 4, 4, 8, ZSTD_lazy }, /* level 7 */
4073 { 18, 17, 17, 4, 4, 8, ZSTD_lazy2 }, /* level 8 */
4074 { 18, 17, 17, 5, 4, 8, ZSTD_lazy2 }, /* level 9 */
4075 { 18, 17, 17, 6, 4, 8, ZSTD_lazy2 }, /* level 10 */
4076 { 18, 18, 17, 6, 4, 8, ZSTD_lazy2 }, /* level 11.*/
4077 { 18, 18, 17, 7, 4, 8, ZSTD_lazy2 }, /* level 12.*/
4078 { 18, 19, 17, 6, 4, 8, ZSTD_btlazy2 }, /* level 13 */
4079 { 18, 18, 18, 4, 4, 16, ZSTD_btopt }, /* level 14.*/
4080 { 18, 18, 18, 4, 3, 16, ZSTD_btopt }, /* level 15.*/
4081 { 18, 19, 18, 6, 3, 32, ZSTD_btopt }, /* level 16.*/
4082 { 18, 19, 18, 8, 3, 64, ZSTD_btopt }, /* level 17.*/
4083 { 18, 19, 18, 9, 3,128, ZSTD_btopt }, /* level 18.*/
4084 { 18, 19, 18, 10, 3,256, ZSTD_btopt }, /* level 19.*/
4085 { 18, 19, 18, 11, 3,512, ZSTD_btultra }, /* level 20.*/
4086 { 18, 19, 18, 12, 3,512, ZSTD_btultra }, /* level 21.*/
4087 { 18, 19, 18, 13, 3,512, ZSTD_btultra }, /* level 22.*/
4089 { /* for srcSize <= 128 KB */
4090 /* W, C, H, S, L, T, strat */
4091 { 17, 12, 12, 1, 7, 8, ZSTD_fast }, /* level 0 - not used */
4092 { 17, 12, 13, 1, 6, 8, ZSTD_fast }, /* level 1 */
4093 { 17, 13, 16, 1, 5, 8, ZSTD_fast }, /* level 2 */
4094 { 17, 16, 16, 2, 5, 8, ZSTD_dfast }, /* level 3 */
4095 { 17, 13, 15, 3, 4, 8, ZSTD_greedy }, /* level 4 */
4096 { 17, 15, 17, 4, 4, 8, ZSTD_greedy }, /* level 5 */
4097 { 17, 16, 17, 3, 4, 8, ZSTD_lazy }, /* level 6 */
4098 { 17, 15, 17, 4, 4, 8, ZSTD_lazy2 }, /* level 7 */
4099 { 17, 17, 17, 4, 4, 8, ZSTD_lazy2 }, /* level 8 */
4100 { 17, 17, 17, 5, 4, 8, ZSTD_lazy2 }, /* level 9 */
4101 { 17, 17, 17, 6, 4, 8, ZSTD_lazy2 }, /* level 10 */
4102 { 17, 17, 17, 7, 4, 8, ZSTD_lazy2 }, /* level 11 */
4103 { 17, 17, 17, 8, 4, 8, ZSTD_lazy2 }, /* level 12 */
4104 { 17, 18, 17, 6, 4, 8, ZSTD_btlazy2 }, /* level 13.*/
4105 { 17, 17, 17, 7, 3, 8, ZSTD_btopt }, /* level 14.*/
4106 { 17, 17, 17, 7, 3, 16, ZSTD_btopt }, /* level 15.*/
4107 { 17, 18, 17, 7, 3, 32, ZSTD_btopt }, /* level 16.*/
4108 { 17, 18, 17, 7, 3, 64, ZSTD_btopt }, /* level 17.*/
4109 { 17, 18, 17, 7, 3,256, ZSTD_btopt }, /* level 18.*/
4110 { 17, 18, 17, 8, 3,256, ZSTD_btopt }, /* level 19.*/
4111 { 17, 18, 17, 9, 3,256, ZSTD_btultra }, /* level 20.*/
4112 { 17, 18, 17, 10, 3,256, ZSTD_btultra }, /* level 21.*/
4113 { 17, 18, 17, 11, 3,512, ZSTD_btultra }, /* level 22.*/
4115 { /* for srcSize <= 16 KB */
4116 /* W, C, H, S, L, T, strat */
4117 { 14, 12, 12, 1, 7, 6, ZSTD_fast }, /* level 0 - not used */
4118 { 14, 14, 14, 1, 6, 6, ZSTD_fast }, /* level 1 */
4119 { 14, 14, 14, 1, 4, 6, ZSTD_fast }, /* level 2 */
4120 { 14, 14, 14, 1, 4, 6, ZSTD_dfast }, /* level 3.*/
4121 { 14, 14, 14, 4, 4, 6, ZSTD_greedy }, /* level 4.*/
4122 { 14, 14, 14, 3, 4, 6, ZSTD_lazy }, /* level 5.*/
4123 { 14, 14, 14, 4, 4, 6, ZSTD_lazy2 }, /* level 6 */
4124 { 14, 14, 14, 5, 4, 6, ZSTD_lazy2 }, /* level 7 */
4125 { 14, 14, 14, 6, 4, 6, ZSTD_lazy2 }, /* level 8.*/
4126 { 14, 15, 14, 6, 4, 6, ZSTD_btlazy2 }, /* level 9.*/
4127 { 14, 15, 14, 3, 3, 6, ZSTD_btopt }, /* level 10.*/
4128 { 14, 15, 14, 6, 3, 8, ZSTD_btopt }, /* level 11.*/
4129 { 14, 15, 14, 6, 3, 16, ZSTD_btopt }, /* level 12.*/
4130 { 14, 15, 14, 6, 3, 24, ZSTD_btopt }, /* level 13.*/
4131 { 14, 15, 15, 6, 3, 48, ZSTD_btopt }, /* level 14.*/
4132 { 14, 15, 15, 6, 3, 64, ZSTD_btopt }, /* level 15.*/
4133 { 14, 15, 15, 6, 3, 96, ZSTD_btopt }, /* level 16.*/
4134 { 14, 15, 15, 6, 3,128, ZSTD_btopt }, /* level 17.*/
4135 { 14, 15, 15, 6, 3,256, ZSTD_btopt }, /* level 18.*/
4136 { 14, 15, 15, 7, 3,256, ZSTD_btopt }, /* level 19.*/
4137 { 14, 15, 15, 8, 3,256, ZSTD_btultra }, /* level 20.*/
4138 { 14, 15, 15, 9, 3,256, ZSTD_btultra }, /* level 21.*/
4139 { 14, 15, 15, 10, 3,256, ZSTD_btultra }, /* level 22.*/
4143 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=1)
4144 /* This function just controls
4145 * the monotonic memory budget increase of ZSTD_defaultCParameters[0].
4146 * Run once, on first ZSTD_getCParams() usage, if ZSTD_DEBUG is enabled
4148 MEM_STATIC void ZSTD_check_compressionLevel_monotonicIncrease_memoryBudget(void)
4151 for (level=1; level<ZSTD_maxCLevel(); level++) {
4152 ZSTD_compressionParameters const c1 = ZSTD_defaultCParameters[0][level];
4153 ZSTD_compressionParameters const c2 = ZSTD_defaultCParameters[0][level+1];
4154 assert(c1.windowLog <= c2.windowLog);
4155 # define ZSTD_TABLECOST(h,c) ((1<<(h)) + (1<<(c)))
4156 assert(ZSTD_TABLECOST(c1.hashLog, c1.chainLog) <= ZSTD_TABLECOST(c2.hashLog, c2.chainLog));
4161 /*! ZSTD_getCParams() :
4162 * @return ZSTD_compressionParameters structure for a selected compression level, `srcSize` and `dictSize`.
4163 * Size values are optional, provide 0 if not known or unused */
4164 ZSTD_compressionParameters ZSTD_getCParams(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize)
4166 size_t const addedSize = srcSizeHint ? 0 : 500;
4167 U64 const rSize = srcSizeHint+dictSize ? srcSizeHint+dictSize+addedSize : (U64)-1;
4168 U32 const tableID = (rSize <= 256 KB) + (rSize <= 128 KB) + (rSize <= 16 KB); /* intentional underflow for srcSizeHint == 0 */
4170 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=1)
4171 static int g_monotonicTest = 1;
4172 if (g_monotonicTest) {
4173 ZSTD_check_compressionLevel_monotonicIncrease_memoryBudget();
4178 if (compressionLevel <= 0) compressionLevel = ZSTD_CLEVEL_DEFAULT; /* 0 == default; no negative compressionLevel yet */
4179 if (compressionLevel > ZSTD_MAX_CLEVEL) compressionLevel = ZSTD_MAX_CLEVEL;
4180 { ZSTD_compressionParameters const cp = ZSTD_defaultCParameters[tableID][compressionLevel];
4181 return ZSTD_adjustCParams_internal(cp, srcSizeHint, dictSize); }
4184 /*! ZSTD_getParams() :
4185 * same as ZSTD_getCParams(), but @return a `ZSTD_parameters` object (instead of `ZSTD_compressionParameters`).
4186 * All fields of `ZSTD_frameParameters` are set to default (0) */
4187 ZSTD_parameters ZSTD_getParams(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize) {
4188 ZSTD_parameters params;
4189 ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, srcSizeHint, dictSize);
4190 memset(¶ms, 0, sizeof(params));
4191 params.cParams = cParams;