+// SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause

+ * Copyright (c) Meta Platforms, Inc. and affiliates.

+#include "../common/allocations.h" /* ZSTD_customMalloc, ZSTD_customCalloc, ZSTD_customFree */

+#include "../common/error_private.h"

+#include "../common/bits.h" /* ZSTD_highbit32, ZSTD_rotateRight_U64 */

+ * The actual (selected) size of the hash table is then stored in ZSTD_MatchState_t.hashLog3,

+ * Note that the result from this function is only valid for

+ * the one-pass compression functions.

+ * When employing the streaming mode,

+ * if flushes are frequently altering the size of blocks,

+ * the overhead from block headers can make the compressed data larger

+ * than the return value of ZSTD_compressBound().

+ size_t const r = ZSTD_COMPRESSBOUND(srcSize);

+ if (r==0) return ERROR(srcSize_wrong);

+ return r;

+ ZSTD_MatchState_t matchState;

+ ZSTD_ParamSwitch_e useRowMatchFinder; /* Indicates whether the CDict was created with params that would use

+ /* statically sized space. tmpWorkspace never moves (but prev/next block swap places) */

+ if (!ZSTD_cwksp_check_available(&cctx->workspace, TMP_WORKSPACE_SIZE + 2 * sizeof(ZSTD_compressedBlockState_t))) return NULL;

+ cctx->tmpWorkspace = ZSTD_cwksp_reserve_object(&cctx->workspace, TMP_WORKSPACE_SIZE);

+ cctx->tmpWkspSize = TMP_WORKSPACE_SIZE;

+ DEBUGLOG(3, "ZSTD_freeCCtx (address: %p)", (void*)cctx);

+ { int cctxInWorkspace = ZSTD_cwksp_owns_buffer(&cctx->workspace, cctx);

+ if (!cctxInWorkspace) ZSTD_customFree(cctx, cctx->customMem);

+const SeqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx) { return &(ctx->seqStore); }

+static int ZSTD_rowMatchFinderUsed(const ZSTD_strategy strategy, const ZSTD_ParamSwitch_e mode) {

+static ZSTD_ParamSwitch_e ZSTD_resolveRowMatchFinderMode(ZSTD_ParamSwitch_e mode,

+ /* The Linux Kernel does not use SIMD, and 128KB is a very common size, e.g. in BtrFS.

+ * The row match finder is slower for this size without SIMD, so disable it.

+ */

+ const unsigned kWindowLogLowerBound = 17;

+ if (cParams->windowLog > kWindowLogLowerBound) mode = ZSTD_ps_enable;

+static ZSTD_ParamSwitch_e ZSTD_resolveBlockSplitterMode(ZSTD_ParamSwitch_e mode,

+ const ZSTD_ParamSwitch_e useRowMatchFinder,

+/* Returns ZSTD_ps_enable if compression parameters are such that we should

+ * Returns ZSTD_ps_disable otherwise.

+static ZSTD_ParamSwitch_e ZSTD_resolveEnableLdm(ZSTD_ParamSwitch_e mode,

+static int ZSTD_resolveExternalSequenceValidation(int mode) {

+ return mode;

+}

+

+/* Resolves maxBlockSize to the default if no value is present. */

+static size_t ZSTD_resolveMaxBlockSize(size_t maxBlockSize) {

+ if (maxBlockSize == 0) {

+ return ZSTD_BLOCKSIZE_MAX;

+ } else {

+ return maxBlockSize;

+ }

+}

+

+static ZSTD_ParamSwitch_e ZSTD_resolveExternalRepcodeSearch(ZSTD_ParamSwitch_e value, int cLevel) {

+ if (value != ZSTD_ps_auto) return value;

+ if (cLevel < 10) {

+ return ZSTD_ps_disable;

+ } else {

+ return ZSTD_ps_enable;

+ }

+}

+

+/* Returns 1 if compression parameters are such that CDict hashtable and chaintable indices are tagged.

+ * If so, the tags need to be removed in ZSTD_resetCCtx_byCopyingCDict. */

+static int ZSTD_CDictIndicesAreTagged(const ZSTD_compressionParameters* const cParams) {

+ return cParams->strategy == ZSTD_fast || cParams->strategy == ZSTD_dfast;

+}

+

+ cctxParams.postBlockSplitter = ZSTD_resolveBlockSplitterMode(cctxParams.postBlockSplitter, &cParams);

+ cctxParams.validateSequences = ZSTD_resolveExternalSequenceValidation(cctxParams.validateSequences);

+ cctxParams.maxBlockSize = ZSTD_resolveMaxBlockSize(cctxParams.maxBlockSize);

+ cctxParams.searchForExternalRepcodes = ZSTD_resolveExternalRepcodeSearch(cctxParams.searchForExternalRepcodes,

+ cctxParams.compressionLevel);

+ * Initializes `cctxParams` from `params` and `compressionLevel`.

+static void

+ZSTD_CCtxParams_init_internal(ZSTD_CCtx_params* cctxParams,

+ const ZSTD_parameters* params,

+ int compressionLevel)

+ cctxParams->postBlockSplitter = ZSTD_resolveBlockSplitterMode(cctxParams->postBlockSplitter, &params->cParams);

+ cctxParams->validateSequences = ZSTD_resolveExternalSequenceValidation(cctxParams->validateSequences);

+ cctxParams->maxBlockSize = ZSTD_resolveMaxBlockSize(cctxParams->maxBlockSize);

+ cctxParams->searchForExternalRepcodes = ZSTD_resolveExternalRepcodeSearch(cctxParams->searchForExternalRepcodes, compressionLevel);

+ cctxParams->useRowMatchFinder, cctxParams->postBlockSplitter, cctxParams->ldmParams.enableLdm);

+ * @param params Validated zstd parameters.

+ bounds.lowerBound = (int)ZSTD_ps_auto;

+ bounds.upperBound = (int)ZSTD_ps_disable;

+ case ZSTD_c_splitAfterSequences:

+ case ZSTD_c_blockSplitterLevel:

+ bounds.lowerBound = 0;

+ bounds.upperBound = ZSTD_BLOCKSPLITTER_LEVEL_MAX;

+ return bounds;

+

+ case ZSTD_c_prefetchCDictTables:

+ bounds.lowerBound = (int)ZSTD_ps_auto;

+ bounds.upperBound = (int)ZSTD_ps_disable;

+ return bounds;

+

+ case ZSTD_c_enableSeqProducerFallback:

+ bounds.lowerBound = 0;

+ bounds.upperBound = 1;

+ return bounds;

+

+ case ZSTD_c_maxBlockSize:

+ bounds.lowerBound = ZSTD_BLOCKSIZE_MAX_MIN;

+ bounds.upperBound = ZSTD_BLOCKSIZE_MAX;

+ return bounds;

+

+ case ZSTD_c_repcodeResolution:

+ bounds.lowerBound = (int)ZSTD_ps_auto;

+ bounds.upperBound = (int)ZSTD_ps_disable;

+ return bounds;

+

+#define BOUNDCHECK(cParam, val) \

+ do { \

+ RETURN_ERROR_IF(!ZSTD_cParam_withinBounds(cParam,val), \

+ parameter_outOfBound, "Param out of bounds"); \

+ } while (0)

+ case ZSTD_c_blockSplitterLevel:

+ case ZSTD_c_splitAfterSequences:

+ case ZSTD_c_prefetchCDictTables:

+ case ZSTD_c_enableSeqProducerFallback:

+ case ZSTD_c_maxBlockSize:

+ case ZSTD_c_repcodeResolution:

+ RETURN_ERROR(stage_wrong, "can only set params in cctx init stage");

+ case ZSTD_c_splitAfterSequences:

+ case ZSTD_c_blockSplitterLevel:

+ case ZSTD_c_prefetchCDictTables:

+ case ZSTD_c_enableSeqProducerFallback:

+ case ZSTD_c_maxBlockSize:

+ case ZSTD_c_repcodeResolution:

+ CCtxParams->cParams.minMatch = (U32)value;

+ CCtxParams->cParams.targetLength = (U32)value;

+ return (size_t)CCtxParams->fParams.contentSizeFlag;

+ return (size_t)CCtxParams->fParams.checksumFlag;

+ return (size_t)CCtxParams->forceWindow;

+ BOUNDCHECK(ZSTD_c_forceAttachDict, (int)pref);

+ const ZSTD_ParamSwitch_e lcm = (ZSTD_ParamSwitch_e)value;

+ BOUNDCHECK(ZSTD_c_literalCompressionMode, (int)lcm);

+ return (size_t)CCtxParams->enableDedicatedDictSearch;

+ BOUNDCHECK(ZSTD_c_enableLongDistanceMatching, value);

+ CCtxParams->ldmParams.enableLdm = (ZSTD_ParamSwitch_e)value;

+ CCtxParams->ldmParams.hashLog = (U32)value;

+ CCtxParams->ldmParams.minMatchLength = (U32)value;

+ CCtxParams->ldmParams.bucketSizeLog = (U32)value;

+ CCtxParams->ldmParams.hashRateLog = (U32)value;

+ if (value!=0) { /* 0 ==> default */

+ value = MAX(value, ZSTD_TARGETCBLOCKSIZE_MIN);

+ }

+ CCtxParams->targetCBlockSize = (U32)value;

+ return (size_t)CCtxParams->srcSizeHint;

+ CCtxParams->blockDelimiters = (ZSTD_SequenceFormat_e)value;

+ return (size_t)CCtxParams->validateSequences;

+

+ case ZSTD_c_splitAfterSequences:

+ BOUNDCHECK(ZSTD_c_splitAfterSequences, value);

+ CCtxParams->postBlockSplitter = (ZSTD_ParamSwitch_e)value;

+ return CCtxParams->postBlockSplitter;

+ case ZSTD_c_blockSplitterLevel:

+ BOUNDCHECK(ZSTD_c_blockSplitterLevel, value);

+ CCtxParams->preBlockSplitter_level = value;

+ return (size_t)CCtxParams->preBlockSplitter_level;

+ CCtxParams->useRowMatchFinder = (ZSTD_ParamSwitch_e)value;

+ return (size_t)CCtxParams->deterministicRefPrefix;

+

+ case ZSTD_c_prefetchCDictTables:

+ BOUNDCHECK(ZSTD_c_prefetchCDictTables, value);

+ CCtxParams->prefetchCDictTables = (ZSTD_ParamSwitch_e)value;

+ return CCtxParams->prefetchCDictTables;

+

+ case ZSTD_c_enableSeqProducerFallback:

+ BOUNDCHECK(ZSTD_c_enableSeqProducerFallback, value);

+ CCtxParams->enableMatchFinderFallback = value;

+ return (size_t)CCtxParams->enableMatchFinderFallback;

+

+ case ZSTD_c_maxBlockSize:

+ if (value!=0) /* 0 ==> default */

+ BOUNDCHECK(ZSTD_c_maxBlockSize, value);

+ assert(value>=0);

+ CCtxParams->maxBlockSize = (size_t)value;

+ return CCtxParams->maxBlockSize;

+

+ case ZSTD_c_repcodeResolution:

+ BOUNDCHECK(ZSTD_c_repcodeResolution, value);

+ CCtxParams->searchForExternalRepcodes = (ZSTD_ParamSwitch_e)value;

+ return CCtxParams->searchForExternalRepcodes;

+ *value = (int)CCtxParams->format;

+ *value = (int)CCtxParams->cParams.searchLog;

+ *value = (int)CCtxParams->cParams.minMatch;

+ *value = (int)CCtxParams->cParams.targetLength;

+ *value = (int)CCtxParams->cParams.strategy;

+ *value = (int)CCtxParams->attachDictPref;

+ *value = (int)CCtxParams->literalCompressionMode;

+ *value = (int)CCtxParams->ldmParams.enableLdm;

+ *value = (int)CCtxParams->ldmParams.hashLog;

+ *value = (int)CCtxParams->ldmParams.minMatchLength;

+ *value = (int)CCtxParams->ldmParams.bucketSizeLog;

+ *value = (int)CCtxParams->ldmParams.hashRateLog;

+ case ZSTD_c_splitAfterSequences :

+ *value = (int)CCtxParams->postBlockSplitter;

+ break;

+ case ZSTD_c_blockSplitterLevel :

+ *value = CCtxParams->preBlockSplitter_level;

+ case ZSTD_c_prefetchCDictTables:

+ *value = (int)CCtxParams->prefetchCDictTables;

+ break;

+ case ZSTD_c_enableSeqProducerFallback:

+ *value = CCtxParams->enableMatchFinderFallback;

+ break;

+ case ZSTD_c_maxBlockSize:

+ *value = (int)CCtxParams->maxBlockSize;

+ break;

+ case ZSTD_c_repcodeResolution:

+ *value = (int)CCtxParams->searchForExternalRepcodes;

+ break;

+size_t ZSTD_CCtx_setCParams(ZSTD_CCtx* cctx, ZSTD_compressionParameters cparams)

+{

+ ZSTD_STATIC_ASSERT(sizeof(cparams) == 7 * 4 /* all params are listed below */);

+ DEBUGLOG(4, "ZSTD_CCtx_setCParams");

+ /* only update if all parameters are valid */

+ FORWARD_IF_ERROR(ZSTD_checkCParams(cparams), "");

+ FORWARD_IF_ERROR(ZSTD_CCtx_setParameter(cctx, ZSTD_c_windowLog, (int)cparams.windowLog), "");

+ FORWARD_IF_ERROR(ZSTD_CCtx_setParameter(cctx, ZSTD_c_chainLog, (int)cparams.chainLog), "");

+ FORWARD_IF_ERROR(ZSTD_CCtx_setParameter(cctx, ZSTD_c_hashLog, (int)cparams.hashLog), "");

+ FORWARD_IF_ERROR(ZSTD_CCtx_setParameter(cctx, ZSTD_c_searchLog, (int)cparams.searchLog), "");

+ FORWARD_IF_ERROR(ZSTD_CCtx_setParameter(cctx, ZSTD_c_minMatch, (int)cparams.minMatch), "");

+ FORWARD_IF_ERROR(ZSTD_CCtx_setParameter(cctx, ZSTD_c_targetLength, (int)cparams.targetLength), "");

+ FORWARD_IF_ERROR(ZSTD_CCtx_setParameter(cctx, ZSTD_c_strategy, (int)cparams.strategy), "");

+ return 0;

+}

+

+size_t ZSTD_CCtx_setFParams(ZSTD_CCtx* cctx, ZSTD_frameParameters fparams)

+{

+ ZSTD_STATIC_ASSERT(sizeof(fparams) == 3 * 4 /* all params are listed below */);

+ DEBUGLOG(4, "ZSTD_CCtx_setFParams");

+ FORWARD_IF_ERROR(ZSTD_CCtx_setParameter(cctx, ZSTD_c_contentSizeFlag, fparams.contentSizeFlag != 0), "");

+ FORWARD_IF_ERROR(ZSTD_CCtx_setParameter(cctx, ZSTD_c_checksumFlag, fparams.checksumFlag != 0), "");

+ FORWARD_IF_ERROR(ZSTD_CCtx_setParameter(cctx, ZSTD_c_dictIDFlag, fparams.noDictIDFlag == 0), "");

+ return 0;

+}

+

+size_t ZSTD_CCtx_setParams(ZSTD_CCtx* cctx, ZSTD_parameters params)

+{

+ DEBUGLOG(4, "ZSTD_CCtx_setParams");

+ /* First check cParams, because we want to update all or none. */

+ FORWARD_IF_ERROR(ZSTD_checkCParams(params.cParams), "");

+ /* Next set fParams, because this could fail if the cctx isn't in init stage. */

+ FORWARD_IF_ERROR(ZSTD_CCtx_setFParams(cctx, params.fParams), "");

+ /* Finally set cParams, which should succeed. */

+ FORWARD_IF_ERROR(ZSTD_CCtx_setCParams(cctx, params.cParams), "");

+ return 0;

+}

+

+ DEBUGLOG(4, "ZSTD_CCtx_setPledgedSrcSize to %llu bytes", pledgedSrcSize);

+ * Initializes the local dictionary using requested parameters.

+ * NOTE: Initialization does not employ the pledged src size,

+ * because the dictionary may be used for multiple compressions.

+ assert(cctx->cdict == dl->cdict);

+ ZSTD_CCtx* cctx,

+ const void* dict, size_t dictSize,

+ ZSTD_dictLoadMethod_e dictLoadMethod,

+ ZSTD_dictContentType_e dictContentType)

+ RETURN_ERROR_IF(cctx->streamStage != zcss_init, stage_wrong,

+ "Can't load a dictionary when cctx is not in init stage.");

+ ZSTD_clearAllDicts(cctx); /* erase any previously set dictionary */

+ if (dict == NULL || dictSize == 0) /* no dictionary */

+ /* copy dictionary content inside CCtx to own its lifetime */

+ "static CCtx can't allocate for an internal copy of dictionary");

+ RETURN_ERROR_IF(dictBuffer==NULL, memory_allocation,

+ "allocation failed for dictionary content");

+ cctx->localDict.dictBuffer = dictBuffer; /* owned ptr to free */

+ cctx->localDict.dict = dictBuffer; /* read-only reference */

+ "Reset parameters is only possible during init stage.");

+ BOUNDCHECK(ZSTD_c_strategy, (int)cParams.strategy);

+# define CLAMP_TYPE(cParam, val, type) \

+ do { \

+ ZSTD_bounds const bounds = ZSTD_cParam_getBounds(cParam); \

+ if ((int)val<bounds.lowerBound) val=(type)bounds.lowerBound; \

+ else if ((int)val>bounds.upperBound) val=(type)bounds.upperBound; \

+ } while (0)

+ * `mode` is the mode for parameter adjustment. See docs for `ZSTD_CParamMode_e`.

+ ZSTD_CParamMode_e mode,

+ ZSTD_ParamSwitch_e useRowMatchFinder)

+ /* Cascade the selected strategy down to the next-highest one built into

+ * this binary. */

+#ifdef ZSTD_EXCLUDE_BTULTRA_BLOCK_COMPRESSOR

+ if (cPar.strategy == ZSTD_btultra2) {

+ cPar.strategy = ZSTD_btultra;

+ }

+ if (cPar.strategy == ZSTD_btultra) {

+ cPar.strategy = ZSTD_btopt;

+ }

+#endif

+#ifdef ZSTD_EXCLUDE_BTOPT_BLOCK_COMPRESSOR

+ if (cPar.strategy == ZSTD_btopt) {

+ cPar.strategy = ZSTD_btlazy2;

+ }

+#endif

+#ifdef ZSTD_EXCLUDE_BTLAZY2_BLOCK_COMPRESSOR

+ if (cPar.strategy == ZSTD_btlazy2) {

+ cPar.strategy = ZSTD_lazy2;

+ }

+#endif

+#ifdef ZSTD_EXCLUDE_LAZY2_BLOCK_COMPRESSOR

+ if (cPar.strategy == ZSTD_lazy2) {

+ cPar.strategy = ZSTD_lazy;

+ }

+#endif

+#ifdef ZSTD_EXCLUDE_LAZY_BLOCK_COMPRESSOR

+ if (cPar.strategy == ZSTD_lazy) {

+ cPar.strategy = ZSTD_greedy;

+ }

+#endif

+#ifdef ZSTD_EXCLUDE_GREEDY_BLOCK_COMPRESSOR

+ if (cPar.strategy == ZSTD_greedy) {

+ cPar.strategy = ZSTD_dfast;

+ }

+#endif

+#ifdef ZSTD_EXCLUDE_DFAST_BLOCK_COMPRESSOR

+ if (cPar.strategy == ZSTD_dfast) {

+ cPar.strategy = ZSTD_fast;

+ cPar.targetLength = 0;

+ }

+#endif

+

+ if ( (srcSize <= maxWindowResize)

+ && (dictSize <= maxWindowResize) ) {

+ /* We can't use more than 32 bits of hash in total, so that means that we require:

+ * (hashLog + 8) <= 32 && (chainLog + 8) <= 32

+ */

+ if (mode == ZSTD_cpm_createCDict && ZSTD_CDictIndicesAreTagged(&cPar)) {

+ U32 const maxShortCacheHashLog = 32 - ZSTD_SHORT_CACHE_TAG_BITS;

+ if (cPar.hashLog > maxShortCacheHashLog) {

+ cPar.hashLog = maxShortCacheHashLog;

+ }

+ if (cPar.chainLog > maxShortCacheHashLog) {

+ cPar.chainLog = maxShortCacheHashLog;

+ }

+ }

+

+

+ /* At this point, we aren't 100% sure if we are using the row match finder.

+ * Unless it is explicitly disabled, conservatively assume that it is enabled.

+ * In this case it will only be disabled for small sources, so shrinking the

+ * hash log a little bit shouldn't result in any ratio loss.

+ */

+ if (useRowMatchFinder == ZSTD_ps_auto)

+ useRowMatchFinder = ZSTD_ps_enable;

+

+ /* We can't hash more than 32-bits in total. So that means that we require:

+ * (hashLog - rowLog + 8) <= 32

+ */

+ if (ZSTD_rowMatchFinderUsed(cPar.strategy, useRowMatchFinder)) {

+ /* Switch to 32-entry rows if searchLog is 5 (or more) */

+ U32 const rowLog = BOUNDED(4, cPar.searchLog, 6);

+ U32 const maxRowHashLog = 32 - ZSTD_ROW_HASH_TAG_BITS;

+ U32 const maxHashLog = maxRowHashLog + rowLog;

+ assert(cPar.hashLog >= rowLog);

+ if (cPar.hashLog > maxHashLog) {

+ cPar.hashLog = maxHashLog;

+ }

+ }

+

+ return ZSTD_adjustCParams_internal(cPar, srcSize, dictSize, ZSTD_cpm_unknown, ZSTD_ps_auto);

+static ZSTD_compressionParameters ZSTD_getCParams_internal(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize, ZSTD_CParamMode_e mode);

+static ZSTD_parameters ZSTD_getParams_internal(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize, ZSTD_CParamMode_e mode);

+ const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize, ZSTD_CParamMode_e mode)

+ assert(CCtxParams->srcSizeHint>=0);

+ srcSizeHint = (U64)CCtxParams->srcSizeHint;

+ return ZSTD_adjustCParams_internal(cParams, srcSizeHint, dictSize, mode, CCtxParams->useRowMatchFinder);

+ const ZSTD_ParamSwitch_e useRowMatchFinder,

+ const int enableDedicatedDictSearch,

+ ZSTD_cwksp_aligned64_alloc_size((MaxML+1) * sizeof(U32))

+ + ZSTD_cwksp_aligned64_alloc_size((MaxLL+1) * sizeof(U32))

+ + ZSTD_cwksp_aligned64_alloc_size((MaxOff+1) * sizeof(U32))

+ + ZSTD_cwksp_aligned64_alloc_size((1<<Litbits) * sizeof(U32))

+ + ZSTD_cwksp_aligned64_alloc_size(ZSTD_OPT_SIZE * sizeof(ZSTD_match_t))

+ + ZSTD_cwksp_aligned64_alloc_size(ZSTD_OPT_SIZE * sizeof(ZSTD_optimal_t));

+ ? ZSTD_cwksp_aligned64_alloc_size(hSize)

+/* Helper function for calculating memory requirements.

+ * Gives a tighter bound than ZSTD_sequenceBound() by taking minMatch into account. */

+static size_t ZSTD_maxNbSeq(size_t blockSize, unsigned minMatch, int useSequenceProducer) {

+ U32 const divider = (minMatch==3 || useSequenceProducer) ? 3 : 4;

+ return blockSize / divider;

+}

+

+ const ZSTD_ParamSwitch_e useRowMatchFinder,

+ const U64 pledgedSrcSize,

+ int useSequenceProducer,

+ size_t maxBlockSize)

+ size_t const blockSize = MIN(ZSTD_resolveMaxBlockSize(maxBlockSize), windowSize);

+ size_t const maxNbSeq = ZSTD_maxNbSeq(blockSize, cParams->minMatch, useSequenceProducer);

+ + ZSTD_cwksp_aligned64_alloc_size(maxNbSeq * sizeof(SeqDef))

+ size_t const tmpWorkSpace = ZSTD_cwksp_alloc_size(TMP_WORKSPACE_SIZE);

+ ZSTD_cwksp_aligned64_alloc_size(maxNbLdmSeq * sizeof(rawSeq)) : 0;

+ size_t const maxNbExternalSeq = ZSTD_sequenceBound(blockSize);

+ size_t const externalSeqSpace = useSequenceProducer

+ ? ZSTD_cwksp_aligned64_alloc_size(maxNbExternalSeq * sizeof(ZSTD_Sequence))

+ : 0;

+

+ tmpWorkSpace +

+ bufferSpace +

+ externalSeqSpace;

+ ZSTD_ParamSwitch_e const useRowMatchFinder = ZSTD_resolveRowMatchFinderMode(params->useRowMatchFinder,

+ &cParams, &params->ldmParams, 1, useRowMatchFinder, 0, 0, ZSTD_CONTENTSIZE_UNKNOWN, ZSTD_hasExtSeqProd(params), params->maxBlockSize);

+ size_t const blockSize = MIN(ZSTD_resolveMaxBlockSize(params->maxBlockSize), (size_t)1 << cParams.windowLog);

+ ZSTD_ParamSwitch_e const useRowMatchFinder = ZSTD_resolveRowMatchFinderMode(params->useRowMatchFinder, &params->cParams);

+ ZSTD_CONTENTSIZE_UNKNOWN, ZSTD_hasExtSeqProd(params), params->maxBlockSize);

+static void ZSTD_invalidateMatchState(ZSTD_MatchState_t* ms)

+/* Mixes bits in a 64 bits in a value, based on XXH3_rrmxmx */

+static U64 ZSTD_bitmix(U64 val, U64 len) {

+ val ^= ZSTD_rotateRight_U64(val, 49) ^ ZSTD_rotateRight_U64(val, 24);

+ val *= 0x9FB21C651E98DF25ULL;

+ val ^= (val >> 35) + len ;

+ val *= 0x9FB21C651E98DF25ULL;

+ return val ^ (val >> 28);

+}

+

+/* Mixes in the hashSalt and hashSaltEntropy to create a new hashSalt */

+static void ZSTD_advanceHashSalt(ZSTD_MatchState_t* ms) {

+ ms->hashSalt = ZSTD_bitmix(ms->hashSalt, 8) ^ ZSTD_bitmix((U64) ms->hashSaltEntropy, 4);

+}

+ZSTD_reset_matchState(ZSTD_MatchState_t* ms,

+ const ZSTD_ParamSwitch_e useRowMatchFinder,

+ ms->lazySkipping = 0;

+ /* Row match finder needs an additional table of hashes ("tags") */

+ size_t const tagTableSize = hSize;

+ /* We want to generate a new salt in case we reset a Cctx, but we always want to use

+ * 0 when we reset a Cdict */

+ if(forWho == ZSTD_resetTarget_CCtx) {

+ ms->tagTable = (BYTE*) ZSTD_cwksp_reserve_aligned_init_once(ws, tagTableSize);

+ ZSTD_advanceHashSalt(ms);

+ } else {

+ /* When we are not salting we want to always memset the memory */

+ ms->tagTable = (BYTE*) ZSTD_cwksp_reserve_aligned64(ws, tagTableSize);

+ ZSTD_memset(ms->tagTable, 0, tagTableSize);

+ ms->hashSalt = 0;

+ /* opt parser space */

+ if ((forWho == ZSTD_resetTarget_CCtx) && (cParams->strategy >= ZSTD_btopt)) {

+ DEBUGLOG(4, "reserving optimal parser space");

+ ms->opt.litFreq = (unsigned*)ZSTD_cwksp_reserve_aligned64(ws, (1<<Litbits) * sizeof(unsigned));

+ ms->opt.litLengthFreq = (unsigned*)ZSTD_cwksp_reserve_aligned64(ws, (MaxLL+1) * sizeof(unsigned));

+ ms->opt.matchLengthFreq = (unsigned*)ZSTD_cwksp_reserve_aligned64(ws, (MaxML+1) * sizeof(unsigned));

+ ms->opt.offCodeFreq = (unsigned*)ZSTD_cwksp_reserve_aligned64(ws, (MaxOff+1) * sizeof(unsigned));

+ ms->opt.matchTable = (ZSTD_match_t*)ZSTD_cwksp_reserve_aligned64(ws, ZSTD_OPT_SIZE * sizeof(ZSTD_match_t));

+ ms->opt.priceTable = (ZSTD_optimal_t*)ZSTD_cwksp_reserve_aligned64(ws, ZSTD_OPT_SIZE * sizeof(ZSTD_optimal_t));

+ }

+

+ (U32)pledgedSrcSize, params->cParams.windowLog, (int)params->useRowMatchFinder, (int)params->postBlockSplitter);

+ assert(params->postBlockSplitter != ZSTD_ps_auto);

+ assert(params->maxBlockSize != 0);

+ size_t const blockSize = MIN(params->maxBlockSize, windowSize);

+ size_t const maxNbSeq = ZSTD_maxNbSeq(blockSize, params->cParams.minMatch, ZSTD_hasExtSeqProd(params));

+ buffInSize, buffOutSize, pledgedSrcSize, ZSTD_hasExtSeqProd(params), params->maxBlockSize);

+ int resizeWorkspace = workspaceTooSmall || workspaceWasteful;

+ * tmpWorkspace never moves,

+ zc->tmpWorkspace = ZSTD_cwksp_reserve_object(ws, TMP_WORKSPACE_SIZE);

+ RETURN_ERROR_IF(zc->tmpWorkspace == NULL, memory_allocation, "couldn't allocate tmpWorkspace");

+ zc->tmpWkspSize = TMP_WORKSPACE_SIZE;

+ zc->blockState.matchState.prefetchCDictTables = params->prefetchCDictTables == ZSTD_ps_enable;

+ zc->blockSizeMax = blockSize;

+ FORWARD_IF_ERROR(ZSTD_reset_matchState(

+ &zc->blockState.matchState,

+ ws,

+ &params->cParams,

+ params->useRowMatchFinder,

+ crp,

+ needsIndexReset,

+ ZSTD_resetTarget_CCtx), "");

+

+ zc->seqStore.sequencesStart = (SeqDef*)ZSTD_cwksp_reserve_aligned64(ws, maxNbSeq * sizeof(SeqDef));

+

+ /* ldm hash table */

+ if (params->ldmParams.enableLdm == ZSTD_ps_enable) {

+ /* TODO: avoid memset? */

+ size_t const ldmHSize = ((size_t)1) << params->ldmParams.hashLog;

+ zc->ldmState.hashTable = (ldmEntry_t*)ZSTD_cwksp_reserve_aligned64(ws, ldmHSize * sizeof(ldmEntry_t));

+ ZSTD_memset(zc->ldmState.hashTable, 0, ldmHSize * sizeof(ldmEntry_t));

+ zc->ldmSequences = (rawSeq*)ZSTD_cwksp_reserve_aligned64(ws, maxNbLdmSeq * sizeof(rawSeq));

+ zc->maxNbLdmSequences = maxNbLdmSeq;

+

+ ZSTD_window_init(&zc->ldmState.window);

+ zc->ldmState.loadedDictEnd = 0;

+ }

+

+ /* reserve space for block-level external sequences */

+ if (ZSTD_hasExtSeqProd(params)) {

+ size_t const maxNbExternalSeq = ZSTD_sequenceBound(blockSize);

+ zc->extSeqBufCapacity = maxNbExternalSeq;

+ zc->extSeqBuf =

+ (ZSTD_Sequence*)ZSTD_cwksp_reserve_aligned64(ws, maxNbExternalSeq * sizeof(ZSTD_Sequence));

+ }

+

+ /* buffers */

+

+ assert(ZSTD_cwksp_estimated_space_within_bounds(ws, neededSpace));

+ cdict->dictContentSize, ZSTD_cpm_attachDict,

+ params.useRowMatchFinder);

+static void ZSTD_copyCDictTableIntoCCtx(U32* dst, U32 const* src, size_t tableSize,

+ ZSTD_compressionParameters const* cParams) {

+ if (ZSTD_CDictIndicesAreTagged(cParams)){

+ /* Remove tags from the CDict table if they are present.

+ * See docs on "short cache" in zstd_compress_internal.h for context. */

+ size_t i;

+ for (i = 0; i < tableSize; i++) {

+ U32 const taggedIndex = src[i];

+ U32 const index = taggedIndex >> ZSTD_SHORT_CACHE_TAG_BITS;

+ dst[i] = index;

+ }

+ } else {

+ ZSTD_memcpy(dst, src, tableSize * sizeof(U32));

+ }

+}

+

+ ZSTD_copyCDictTableIntoCCtx(cctx->blockState.matchState.hashTable,

+ cdict->matchState.hashTable,

+ hSize, cdict_cParams);

+

+ ZSTD_copyCDictTableIntoCCtx(cctx->blockState.matchState.chainTable,

+ cdict->matchState.chainTable,

+ chainSize, cdict_cParams);

+ size_t const tagTableSize = hSize;

+ cdict->matchState.tagTable,

+ tagTableSize);

+ cctx->blockState.matchState.hashSalt = cdict->matchState.hashSalt;

+ assert(cctx->blockState.matchState.hashLog3 <= 31);

+ { U32 const h3log = cctx->blockState.matchState.hashLog3;

+ { ZSTD_MatchState_t const* srcMatchState = &cdict->matchState;

+ ZSTD_MatchState_t* dstMatchState = &cctx->blockState.matchState;

+ assert(srcCCtx->appliedParams.postBlockSplitter != ZSTD_ps_auto);

+ params.postBlockSplitter = srcCCtx->appliedParams.postBlockSplitter;

+ params.maxBlockSize = srcCCtx->appliedParams.maxBlockSize;

+ U32 const h3log = srcCCtx->blockState.matchState.hashLog3;

+ const ZSTD_MatchState_t* srcMatchState = &srcCCtx->blockState.matchState;

+ ZSTD_MatchState_t* dstMatchState = &dstCCtx->blockState.matchState;

+ assert(size < (1U<<31)); /* can be cast to int */

+static void ZSTD_reduceIndex (ZSTD_MatchState_t* ms, ZSTD_CCtx_params const* params, const U32 reducerValue)

+int ZSTD_seqToCodes(const SeqStore_t* seqStorePtr)

+ const SeqDef* const sequences = seqStorePtr->sequencesStart;

+ int longOffsets = 0;

+ U32 const ofCode = ZSTD_highbit32(sequences[u].offBase);

+ ofCodeTable[u] = (BYTE)ofCode;

+ assert(!(MEM_64bits() && ofCode >= STREAM_ACCUMULATOR_MIN));

+ if (MEM_32bits() && ofCode >= STREAM_ACCUMULATOR_MIN)

+ longOffsets = 1;

+ return longOffsets;

+ DEBUGLOG(5, "ZSTD_blockSplitterEnabled (postBlockSplitter=%d)", cctxParams->postBlockSplitter);

+ assert(cctxParams->postBlockSplitter != ZSTD_ps_auto);

+ return (cctxParams->postBlockSplitter == ZSTD_ps_enable);

+ int longOffsets;

+ZSTD_buildSequencesStatistics(

+ const SeqStore_t* seqStorePtr, size_t nbSeq,

+ const ZSTD_fseCTables_t* prevEntropy, ZSTD_fseCTables_t* nextEntropy,

+ BYTE* dst, const BYTE* const dstEnd,

+ ZSTD_strategy strategy, unsigned* countWorkspace,

+ void* entropyWorkspace, size_t entropyWkspSize)

+{

+ stats.longOffsets = ZSTD_seqToCodes(seqStorePtr);

+ CTable_LitLength, LLFSELog, (SymbolEncodingType_e)stats.LLtype,

+ ZSTD_DefaultPolicy_e const defaultPolicy = (max <= DefaultMaxOff) ? ZSTD_defaultAllowed : ZSTD_defaultDisallowed;

+ CTable_OffsetBits, OffFSELog, (SymbolEncodingType_e)stats.Offtype,

+ CTable_MatchLength, MLFSELog, (SymbolEncodingType_e)stats.MLtype,

+ZSTD_entropyCompressSeqStore_internal(

+ void* dst, size_t dstCapacity,

+ const void* literals, size_t litSize,

+ const SeqStore_t* seqStorePtr,

+ const ZSTD_entropyCTables_t* prevEntropy,

+ ZSTD_entropyCTables_t* nextEntropy,

+ const ZSTD_CCtx_params* cctxParams,

+ void* entropyWorkspace, size_t entropyWkspSize,

+ const int bmi2)

+ const SeqDef* const sequences = seqStorePtr->sequencesStart;

+ const size_t nbSeq = (size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart);

+ int longOffsets = 0;

+ DEBUGLOG(5, "ZSTD_entropyCompressSeqStore_internal (nbSeq=%zu, dstCapacity=%zu)", nbSeq, dstCapacity);

+ { size_t const numSequences = (size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart);

+ int const suspectUncompressible = (numSequences == 0) || (litSize / numSequences >= SUSPECT_UNCOMPRESSIBLE_LITERAL_RATIO);

+

+ &prevEntropy->huf, &nextEntropy->huf,

+ cctxParams->cParams.strategy,

+ ZSTD_literalsCompressionIsDisabled(cctxParams),

+ suspectUncompressible, bmi2);

+ { BYTE* const seqHead = op++;

+ const ZSTD_symbolEncodingTypeStats_t stats =

+ ZSTD_buildSequencesStatistics(seqStorePtr, nbSeq,

+ longOffsets = stats.longOffsets;

+static size_t

+ZSTD_entropyCompressSeqStore_wExtLitBuffer(

+ void* dst, size_t dstCapacity,

+ const void* literals, size_t litSize,

+ size_t blockSize,

+ const SeqStore_t* seqStorePtr,

+ const ZSTD_entropyCTables_t* prevEntropy,

+ ZSTD_entropyCTables_t* nextEntropy,

+ const ZSTD_CCtx_params* cctxParams,

+ void* entropyWorkspace, size_t entropyWkspSize,

+ int bmi2)

+ literals, litSize,

+ seqStorePtr, prevEntropy, nextEntropy, cctxParams,

+ if ((cSize == ERROR(dstSize_tooSmall)) & (blockSize <= dstCapacity)) {

+ DEBUGLOG(4, "not enough dstCapacity (%zu) for ZSTD_entropyCompressSeqStore_internal()=> do not compress block", dstCapacity);

+ }

+ { size_t const maxCSize = blockSize - ZSTD_minGain(blockSize, cctxParams->cParams.strategy);

+ DEBUGLOG(5, "ZSTD_entropyCompressSeqStore() cSize: %zu", cSize);

+ /* libzstd decoder before > v1.5.4 is not compatible with compressed blocks of size ZSTD_BLOCKSIZE_MAX exactly.

+ * This restriction is indirectly already fulfilled by respecting ZSTD_minGain() condition above.

+ */

+ assert(cSize < ZSTD_BLOCKSIZE_MAX);

+static size_t

+ZSTD_entropyCompressSeqStore(

+ const SeqStore_t* seqStorePtr,

+ const ZSTD_entropyCTables_t* prevEntropy,

+ ZSTD_entropyCTables_t* nextEntropy,

+ const ZSTD_CCtx_params* cctxParams,

+ void* dst, size_t dstCapacity,

+ size_t srcSize,

+ void* entropyWorkspace, size_t entropyWkspSize,

+ int bmi2)

+{

+ return ZSTD_entropyCompressSeqStore_wExtLitBuffer(

+ dst, dstCapacity,

+ seqStorePtr->litStart, (size_t)(seqStorePtr->lit - seqStorePtr->litStart),

+ srcSize,

+ seqStorePtr,

+ prevEntropy, nextEntropy,

+ cctxParams,

+ entropyWorkspace, entropyWkspSize,

+ bmi2);

+}

+

+ZSTD_BlockCompressor_f ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_ParamSwitch_e useRowMatchFinder, ZSTD_dictMode_e dictMode)

+ static const ZSTD_BlockCompressor_f blockCompressor[4][ZSTD_STRATEGY_MAX+1] = {

+ ZSTD_COMPRESSBLOCK_DOUBLEFAST,

+ ZSTD_COMPRESSBLOCK_GREEDY,

+ ZSTD_COMPRESSBLOCK_LAZY,

+ ZSTD_COMPRESSBLOCK_LAZY2,

+ ZSTD_COMPRESSBLOCK_BTLAZY2,

+ ZSTD_COMPRESSBLOCK_BTOPT,

+ ZSTD_COMPRESSBLOCK_BTULTRA,

+ ZSTD_COMPRESSBLOCK_BTULTRA2

+ },

+ ZSTD_COMPRESSBLOCK_DOUBLEFAST_EXTDICT,

+ ZSTD_COMPRESSBLOCK_GREEDY_EXTDICT,

+ ZSTD_COMPRESSBLOCK_LAZY_EXTDICT,

+ ZSTD_COMPRESSBLOCK_LAZY2_EXTDICT,

+ ZSTD_COMPRESSBLOCK_BTLAZY2_EXTDICT,

+ ZSTD_COMPRESSBLOCK_BTOPT_EXTDICT,

+ ZSTD_COMPRESSBLOCK_BTULTRA_EXTDICT,

+ ZSTD_COMPRESSBLOCK_BTULTRA_EXTDICT

+ },

+ ZSTD_COMPRESSBLOCK_DOUBLEFAST_DICTMATCHSTATE,

+ ZSTD_COMPRESSBLOCK_GREEDY_DICTMATCHSTATE,

+ ZSTD_COMPRESSBLOCK_LAZY_DICTMATCHSTATE,

+ ZSTD_COMPRESSBLOCK_LAZY2_DICTMATCHSTATE,

+ ZSTD_COMPRESSBLOCK_BTLAZY2_DICTMATCHSTATE,

+ ZSTD_COMPRESSBLOCK_BTOPT_DICTMATCHSTATE,

+ ZSTD_COMPRESSBLOCK_BTULTRA_DICTMATCHSTATE,

+ ZSTD_COMPRESSBLOCK_BTULTRA_DICTMATCHSTATE

+ },

+ ZSTD_COMPRESSBLOCK_GREEDY_DEDICATEDDICTSEARCH,

+ ZSTD_COMPRESSBLOCK_LAZY_DEDICATEDDICTSEARCH,

+ ZSTD_COMPRESSBLOCK_LAZY2_DEDICATEDDICTSEARCH,

+ ZSTD_BlockCompressor_f selectedCompressor;

+ assert(ZSTD_cParam_withinBounds(ZSTD_c_strategy, (int)strat));

+ DEBUGLOG(5, "Selected block compressor: dictMode=%d strat=%d rowMatchfinder=%d", (int)dictMode, (int)strat, (int)useRowMatchFinder);

+ static const ZSTD_BlockCompressor_f rowBasedBlockCompressors[4][3] = {

+ {

+ ZSTD_COMPRESSBLOCK_GREEDY_ROW,

+ ZSTD_COMPRESSBLOCK_LAZY_ROW,

+ ZSTD_COMPRESSBLOCK_LAZY2_ROW

+ },

+ {

+ ZSTD_COMPRESSBLOCK_GREEDY_EXTDICT_ROW,

+ ZSTD_COMPRESSBLOCK_LAZY_EXTDICT_ROW,

+ ZSTD_COMPRESSBLOCK_LAZY2_EXTDICT_ROW

+ },

+ {

+ ZSTD_COMPRESSBLOCK_GREEDY_DICTMATCHSTATE_ROW,

+ ZSTD_COMPRESSBLOCK_LAZY_DICTMATCHSTATE_ROW,

+ ZSTD_COMPRESSBLOCK_LAZY2_DICTMATCHSTATE_ROW

+ },

+ {

+ ZSTD_COMPRESSBLOCK_GREEDY_DEDICATEDDICTSEARCH_ROW,

+ ZSTD_COMPRESSBLOCK_LAZY_DEDICATEDDICTSEARCH_ROW,

+ ZSTD_COMPRESSBLOCK_LAZY2_DEDICATEDDICTSEARCH_ROW

+ }

+ DEBUGLOG(5, "Selecting a row-based matchfinder");

+static void ZSTD_storeLastLiterals(SeqStore_t* seqStorePtr,

+void ZSTD_resetSeqStore(SeqStore_t* ssPtr)

+/* ZSTD_postProcessSequenceProducerResult() :

+ * Validates and post-processes sequences obtained through the external matchfinder API:

+ * - Checks whether nbExternalSeqs represents an error condition.

+ * - Appends a block delimiter to outSeqs if one is not already present.

+ * See zstd.h for context regarding block delimiters.

+ * Returns the number of sequences after post-processing, or an error code. */

+static size_t ZSTD_postProcessSequenceProducerResult(

+ ZSTD_Sequence* outSeqs, size_t nbExternalSeqs, size_t outSeqsCapacity, size_t srcSize

+) {

+ RETURN_ERROR_IF(

+ nbExternalSeqs > outSeqsCapacity,

+ sequenceProducer_failed,

+ "External sequence producer returned error code %lu",

+ (unsigned long)nbExternalSeqs

+ );

+

+ RETURN_ERROR_IF(

+ nbExternalSeqs == 0 && srcSize > 0,

+ sequenceProducer_failed,

+ "Got zero sequences from external sequence producer for a non-empty src buffer!"

+ );

+

+ if (srcSize == 0) {

+ ZSTD_memset(&outSeqs[0], 0, sizeof(ZSTD_Sequence));

+ return 1;

+ }

+

+ {

+ ZSTD_Sequence const lastSeq = outSeqs[nbExternalSeqs - 1];

+

+ /* We can return early if lastSeq is already a block delimiter. */

+ if (lastSeq.offset == 0 && lastSeq.matchLength == 0) {

+ return nbExternalSeqs;

+ }

+

+ /* This error condition is only possible if the external matchfinder

+ * produced an invalid parse, by definition of ZSTD_sequenceBound(). */

+ RETURN_ERROR_IF(

+ nbExternalSeqs == outSeqsCapacity,

+ sequenceProducer_failed,

+ "nbExternalSeqs == outSeqsCapacity but lastSeq is not a block delimiter!"

+ );

+

+ /* lastSeq is not a block delimiter, so we need to append one. */

+ ZSTD_memset(&outSeqs[nbExternalSeqs], 0, sizeof(ZSTD_Sequence));

+ return nbExternalSeqs + 1;

+ }

+}

+

+/* ZSTD_fastSequenceLengthSum() :

+ * Returns sum(litLen) + sum(matchLen) + lastLits for *seqBuf*.

+ * Similar to another function in zstd_compress.c (determine_blockSize),

+ * except it doesn't check for a block delimiter to end summation.

+ * Removing the early exit allows the compiler to auto-vectorize (https://godbolt.org/z/cY1cajz9P).

+ * This function can be deleted and replaced by determine_blockSize after we resolve issue #3456. */

+static size_t ZSTD_fastSequenceLengthSum(ZSTD_Sequence const* seqBuf, size_t seqBufSize) {

+ size_t matchLenSum, litLenSum, i;

+ matchLenSum = 0;

+ litLenSum = 0;

+ for (i = 0; i < seqBufSize; i++) {

+ litLenSum += seqBuf[i].litLength;

+ matchLenSum += seqBuf[i].matchLength;

+ }

+ return litLenSum + matchLenSum;

+}

+

+/*

+ * Function to validate sequences produced by a block compressor.

+ */

+static void ZSTD_validateSeqStore(const SeqStore_t* seqStore, const ZSTD_compressionParameters* cParams)

+{

+#if DEBUGLEVEL >= 1

+ const SeqDef* seq = seqStore->sequencesStart;

+ const SeqDef* const seqEnd = seqStore->sequences;

+ size_t const matchLenLowerBound = cParams->minMatch == 3 ? 3 : 4;

+ for (; seq < seqEnd; ++seq) {

+ const ZSTD_SequenceLength seqLength = ZSTD_getSequenceLength(seqStore, seq);

+ assert(seqLength.matchLength >= matchLenLowerBound);

+ (void)seqLength;

+ (void)matchLenLowerBound;

+ }

+#else

+ (void)seqStore;

+ (void)cParams;

+#endif

+}

+

+static size_t

+ZSTD_transferSequences_wBlockDelim(ZSTD_CCtx* cctx,

+ ZSTD_SequencePosition* seqPos,

+ const ZSTD_Sequence* const inSeqs, size_t inSeqsSize,

+ const void* src, size_t blockSize,

+ ZSTD_ParamSwitch_e externalRepSearch);

+

+typedef enum { ZSTDbss_compress, ZSTDbss_noCompress } ZSTD_BuildSeqStore_e;

+ ZSTD_MatchState_t* const ms = &zc->blockState.matchState;

+ /* TODO: See 3090. We reduced MIN_CBLOCK_SIZE from 3 to 2 so to compensate we are adding

+ * additional 1. We need to revisit and change this logic to be more consistent */

+ if (srcSize < MIN_CBLOCK_SIZE+ZSTD_blockHeaderSize+1+1) {

+

+ /* External matchfinder + LDM is technically possible, just not implemented yet.

+ * We need to revisit soon and implement it. */

+ RETURN_ERROR_IF(

+ ZSTD_hasExtSeqProd(&zc->appliedParams),

+ parameter_combination_unsupported,

+ "Long-distance matching with external sequence producer enabled is not currently supported."

+ );

+

+ RawSeqStore_t ldmSeqStore = kNullRawSeqStore;

+

+ /* External matchfinder + LDM is technically possible, just not implemented yet.

+ * We need to revisit soon and implement it. */

+ RETURN_ERROR_IF(

+ ZSTD_hasExtSeqProd(&zc->appliedParams),

+ parameter_combination_unsupported,

+ "Long-distance matching with external sequence producer enabled is not currently supported."

+ );

+ } else if (ZSTD_hasExtSeqProd(&zc->appliedParams)) {

+ assert(

+ zc->extSeqBufCapacity >= ZSTD_sequenceBound(srcSize)

+ );

+ assert(zc->appliedParams.extSeqProdFunc != NULL);

+

+ { U32 const windowSize = (U32)1 << zc->appliedParams.cParams.windowLog;

+

+ size_t const nbExternalSeqs = (zc->appliedParams.extSeqProdFunc)(

+ zc->appliedParams.extSeqProdState,

+ zc->extSeqBuf,

+ zc->extSeqBufCapacity,

+ src, srcSize,

+ NULL, 0, /* dict and dictSize, currently not supported */

+ zc->appliedParams.compressionLevel,

+ windowSize

+ );

+

+ size_t const nbPostProcessedSeqs = ZSTD_postProcessSequenceProducerResult(

+ zc->extSeqBuf,

+ nbExternalSeqs,

+ zc->extSeqBufCapacity,

+ srcSize

+ );

+

+ /* Return early if there is no error, since we don't need to worry about last literals */

+ if (!ZSTD_isError(nbPostProcessedSeqs)) {

+ ZSTD_SequencePosition seqPos = {0,0,0};

+ size_t const seqLenSum = ZSTD_fastSequenceLengthSum(zc->extSeqBuf, nbPostProcessedSeqs);

+ RETURN_ERROR_IF(seqLenSum > srcSize, externalSequences_invalid, "External sequences imply too large a block!");

+ FORWARD_IF_ERROR(

+ ZSTD_transferSequences_wBlockDelim(

+ zc, &seqPos,

+ zc->extSeqBuf, nbPostProcessedSeqs,

+ src, srcSize,

+ zc->appliedParams.searchForExternalRepcodes

+ ),

+ "Failed to copy external sequences to seqStore!"

+ );

+ ms->ldmSeqStore = NULL;

+ DEBUGLOG(5, "Copied %lu sequences from external sequence producer to internal seqStore.", (unsigned long)nbExternalSeqs);

+ return ZSTDbss_compress;

+ }

+

+ /* Propagate the error if fallback is disabled */

+ if (!zc->appliedParams.enableMatchFinderFallback) {

+ return nbPostProcessedSeqs;

+ }

+

+ /* Fallback to software matchfinder */

+ { ZSTD_BlockCompressor_f const blockCompressor =

+ ZSTD_selectBlockCompressor(

+ zc->appliedParams.cParams.strategy,

+ zc->appliedParams.useRowMatchFinder,

+ dictMode);

+ ms->ldmSeqStore = NULL;

+ DEBUGLOG(

+ 5,

+ "External sequence producer returned error code %lu. Falling back to internal parser.",

+ (unsigned long)nbExternalSeqs

+ );

+ lastLLSize = blockCompressor(ms, &zc->seqStore, zc->blockState.nextCBlock->rep, src, srcSize);

+ } }

+ } else { /* not long range mode and no external matchfinder */

+ ZSTD_BlockCompressor_f const blockCompressor = ZSTD_selectBlockCompressor(

+ zc->appliedParams.cParams.strategy,

+ zc->appliedParams.useRowMatchFinder,

+ dictMode);

+ ZSTD_validateSeqStore(&zc->seqStore, &zc->appliedParams.cParams);

+static size_t ZSTD_copyBlockSequences(SeqCollector* seqCollector, const SeqStore_t* seqStore, const U32 prevRepcodes[ZSTD_REP_NUM])

+ const SeqDef* inSeqs = seqStore->sequencesStart;

+ const size_t nbInSequences = (size_t)(seqStore->sequences - inSeqs);

+ const size_t nbInLiterals = (size_t)(seqStore->lit - seqStore->litStart);

+ ZSTD_Sequence* outSeqs = seqCollector->seqIndex == 0 ? seqCollector->seqStart : seqCollector->seqStart + seqCollector->seqIndex;

+ const size_t nbOutSequences = nbInSequences + 1;

+ size_t nbOutLiterals = 0;

+ Repcodes_t repcodes;

+

+ /* Bounds check that we have enough space for every input sequence

+ * and the block delimiter

+ */

+ assert(seqCollector->seqIndex <= seqCollector->maxSequences);

+ RETURN_ERROR_IF(

+ nbOutSequences > (size_t)(seqCollector->maxSequences - seqCollector->seqIndex),

+ dstSize_tooSmall,

+ "Not enough space to copy sequences");

+

+ ZSTD_memcpy(&repcodes, prevRepcodes, sizeof(repcodes));

+ for (i = 0; i < nbInSequences; ++i) {

+ U32 rawOffset;

+ outSeqs[i].litLength = inSeqs[i].litLength;

+ outSeqs[i].matchLength = inSeqs[i].mlBase + MINMATCH;

+ /* Handle the possible single length >= 64K

+ * There can only be one because we add MINMATCH to every match length,

+ * and blocks are at most 128K.

+ */

+ /* Determine the raw offset given the offBase, which may be a repcode. */

+ if (OFFBASE_IS_REPCODE(inSeqs[i].offBase)) {

+ const U32 repcode = OFFBASE_TO_REPCODE(inSeqs[i].offBase);

+ assert(repcode > 0);

+ outSeqs[i].rep = repcode;

+ rawOffset = repcodes.rep[repcode - 1];

+ if (repcode == 3) {

+ assert(repcodes.rep[0] > 1);

+ rawOffset = repcodes.rep[0] - 1;

+ rawOffset = repcodes.rep[repcode];

+ } else {

+ rawOffset = OFFBASE_TO_OFFSET(inSeqs[i].offBase);

+

+ /* Update repcode history for the sequence */

+ ZSTD_updateRep(repcodes.rep,

+ inSeqs[i].offBase,

+ inSeqs[i].litLength == 0);

+

+ nbOutLiterals += outSeqs[i].litLength;

+ assert(nbInLiterals >= nbOutLiterals);

+ {

+ const size_t lastLLSize = nbInLiterals - nbOutLiterals;

+ outSeqs[nbInSequences].litLength = (U32)lastLLSize;

+ outSeqs[nbInSequences].matchLength = 0;

+ outSeqs[nbInSequences].offset = 0;

+ assert(nbOutSequences == nbInSequences + 1);

+ }

+ seqCollector->seqIndex += nbOutSequences;

+ assert(seqCollector->seqIndex <= seqCollector->maxSequences);

+

+ return 0;

+}

+

+size_t ZSTD_sequenceBound(size_t srcSize) {

+ const size_t maxNbSeq = (srcSize / ZSTD_MINMATCH_MIN) + 1;

+ const size_t maxNbDelims = (srcSize / ZSTD_BLOCKSIZE_MAX_MIN) + 1;

+ return maxNbSeq + maxNbDelims;

+ void* dst; /* Make C90 happy. */

+ {

+ int targetCBlockSize;

+ FORWARD_IF_ERROR(ZSTD_CCtx_getParameter(zc, ZSTD_c_targetCBlockSize, &targetCBlockSize), "");

+ RETURN_ERROR_IF(targetCBlockSize != 0, parameter_unsupported, "targetCBlockSize != 0");

+ }

+ {

+ int nbWorkers;

+ FORWARD_IF_ERROR(ZSTD_CCtx_getParameter(zc, ZSTD_c_nbWorkers, &nbWorkers), "");

+ RETURN_ERROR_IF(nbWorkers != 0, parameter_unsupported, "nbWorkers != 0");

+ }

+ dst = ZSTD_customMalloc(dstCapacity, ZSTD_defaultCMem);

+ {

+ const size_t ret = ZSTD_compress2(zc, dst, dstCapacity, src, srcSize);

+ ZSTD_customFree(dst, ZSTD_defaultCMem);

+ FORWARD_IF_ERROR(ret, "ZSTD_compress2 failed");

+ }

+ assert(zc->seqCollector.seqIndex <= ZSTD_sequenceBound(srcSize));

+ size_t u;

+ } } }

+static int ZSTD_maybeRLE(SeqStore_t const* seqStore)

+static void

+ZSTD_blockState_confirmRepcodesAndEntropyTables(ZSTD_blockState_t* const bs)

+static void

+writeBlockHeader(void* op, size_t cSize, size_t blockSize, U32 lastBlock)

+{

+ DEBUGLOG(5, "writeBlockHeader: cSize: %zu blockSize: %zu lastBlock: %u", cSize, blockSize, lastBlock);

+ * @return : size of huffman description table, or an error code

+ */

+static size_t

+ZSTD_buildBlockEntropyStats_literals(void* const src, size_t srcSize,

+ const ZSTD_hufCTables_t* prevHuf,

+ ZSTD_hufCTables_t* nextHuf,

+ ZSTD_hufCTablesMetadata_t* hufMetadata,

+ const int literalsCompressionIsDisabled,

+ void* workspace, size_t wkspSize,

+ int hufFlags)

+ const size_t nodeWkspSize = (size_t)(wkspEnd - nodeWksp);

+ unsigned huffLog = LitHufLog;

+# define COMPRESS_LITERALS_SIZE_MIN 63 /* heuristic */

+ } }

+ { size_t const largest =

+ HIST_count_wksp (countWksp, &maxSymbolValue,

+ (const BYTE*)src, srcSize,

+ workspace, wkspSize);

+ /* only one literal symbol */

+ /* heuristic: likely not compressible */

+ } }

+ if (repeat == HUF_repeat_check

+ && !HUF_validateCTable((HUF_CElt const*)prevHuf->CTable, countWksp, maxSymbolValue)) {

+ huffLog = HUF_optimalTableLog(huffLog, srcSize, maxSymbolValue, nodeWksp, nodeWkspSize, nextHuf->CTable, countWksp, hufFlags);

+ assert(huffLog <= LitHufLog);

+ }

+ { /* Build and write the CTable */

+ size_t const newCSize = HUF_estimateCompressedSize(

+ (HUF_CElt*)nextHuf->CTable, countWksp, maxSymbolValue);

+ size_t const hSize = HUF_writeCTable_wksp(

+ hufMetadata->hufDesBuffer, sizeof(hufMetadata->hufDesBuffer),

+ (HUF_CElt*)nextHuf->CTable, maxSymbolValue, huffLog,

+ nodeWksp, nodeWkspSize);

+ /* Check against repeating the previous CTable */

+ if (repeat != HUF_repeat_none) {

+ size_t const oldCSize = HUF_estimateCompressedSize(

+ (HUF_CElt const*)prevHuf->CTable, countWksp, maxSymbolValue);

+ if (oldCSize < srcSize && (oldCSize <= hSize + newCSize || hSize + 12 >= srcSize)) {

+ DEBUGLOG(5, "set_repeat - smaller");

+ hufMetadata->hType = set_repeat;

+ } }

+ if (newCSize + hSize >= srcSize) {

+ DEBUGLOG(5, "set_basic - no gains");

+ ZSTD_memcpy(nextHuf, prevHuf, sizeof(*prevHuf));

+ hufMetadata->hType = set_basic;

+ return 0;

+ DEBUGLOG(5, "set_compressed (hSize=%u)", (U32)hSize);

+ hufMetadata->hType = set_compressed;

+ nextHuf->repeatMode = HUF_repeat_check;

+ return hSize;

+ZSTD_buildDummySequencesStatistics(ZSTD_fseCTables_t* nextEntropy)

+{

+ ZSTD_symbolEncodingTypeStats_t stats = {set_basic, set_basic, set_basic, 0, 0, 0};

+ * @return : size of fse tables or error code */

+static size_t

+ZSTD_buildBlockEntropyStats_sequences(

+ const SeqStore_t* seqStorePtr,

+ const ZSTD_fseCTables_t* prevEntropy,

+ ZSTD_fseCTables_t* nextEntropy,

+ const ZSTD_CCtx_params* cctxParams,

+ ZSTD_fseCTablesMetadata_t* fseMetadata,

+ void* workspace, size_t wkspSize)

+ size_t const nbSeq = (size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart);

+ fseMetadata->llType = (SymbolEncodingType_e) stats.LLtype;

+ fseMetadata->ofType = (SymbolEncodingType_e) stats.Offtype;

+ fseMetadata->mlType = (SymbolEncodingType_e) stats.MLtype;

+ * @return : 0 on success, or an error code

+ * Note : also employed in superblock

+size_t ZSTD_buildBlockEntropyStats(

+ const SeqStore_t* seqStorePtr,

+ const ZSTD_entropyCTables_t* prevEntropy,

+ ZSTD_entropyCTables_t* nextEntropy,

+ const ZSTD_CCtx_params* cctxParams,

+ ZSTD_entropyCTablesMetadata_t* entropyMetadata,

+ void* workspace, size_t wkspSize)

+{

+ size_t const litSize = (size_t)(seqStorePtr->lit - seqStorePtr->litStart);

+ int const huf_useOptDepth = (cctxParams->cParams.strategy >= HUF_OPTIMAL_DEPTH_THRESHOLD);

+ int const hufFlags = huf_useOptDepth ? HUF_flags_optimalDepth : 0;

+

+ workspace, wkspSize, hufFlags);

+

+static size_t

+ZSTD_estimateBlockSize_literal(const BYTE* literals, size_t litSize,

+ const ZSTD_hufCTables_t* huf,

+ const ZSTD_hufCTablesMetadata_t* hufMetadata,

+ void* workspace, size_t wkspSize,

+ int writeEntropy)

+static size_t

+ZSTD_estimateBlockSize_symbolType(SymbolEncodingType_e type,

+ const BYTE* codeTable, size_t nbSeq, unsigned maxCode,

+ const FSE_CTable* fseCTable,

+ const U8* additionalBits,

+ short const* defaultNorm, U32 defaultNormLog, U32 defaultMax,

+ void* workspace, size_t wkspSize)

+static size_t

+ZSTD_estimateBlockSize_sequences(const BYTE* ofCodeTable,

+ const BYTE* llCodeTable,

+ const BYTE* mlCodeTable,

+ size_t nbSeq,

+ const ZSTD_fseCTables_t* fseTables,

+ const ZSTD_fseCTablesMetadata_t* fseMetadata,

+ void* workspace, size_t wkspSize,

+ int writeEntropy)

+ fseTables->offcodeCTable, NULL,

+ OF_defaultNorm, OF_defaultNormLog, DefaultMaxOff,

+ workspace, wkspSize);

+ fseTables->litlengthCTable, LL_bits,

+ LL_defaultNorm, LL_defaultNormLog, MaxLL,

+ workspace, wkspSize);

+ fseTables->matchlengthCTable, ML_bits,

+ ML_defaultNorm, ML_defaultNormLog, MaxML,

+ workspace, wkspSize);

+static size_t

+ZSTD_estimateBlockSize(const BYTE* literals, size_t litSize,

+ const BYTE* ofCodeTable,

+ const BYTE* llCodeTable,

+ const BYTE* mlCodeTable,

+ size_t nbSeq,

+ const ZSTD_entropyCTables_t* entropy,

+ const ZSTD_entropyCTablesMetadata_t* entropyMetadata,

+ void* workspace, size_t wkspSize,

+ int writeLitEntropy, int writeSeqEntropy)

+{

+ &entropy->huf, &entropyMetadata->hufMetadata,

+ workspace, wkspSize, writeLitEntropy);

+ nbSeq, &entropy->fse, &entropyMetadata->fseMetadata,

+ workspace, wkspSize, writeSeqEntropy);

+ * @return: estimated compressed size of the seqStore, or a zstd error.

+static size_t

+ZSTD_buildEntropyStatisticsAndEstimateSubBlockSize(SeqStore_t* seqStore, ZSTD_CCtx* zc)

+{

+ ZSTD_entropyCTablesMetadata_t* const entropyMetadata = &zc->blockSplitCtx.entropyMetadata;

+ zc->tmpWorkspace, zc->tmpWkspSize), "");

+ return ZSTD_estimateBlockSize(

+ seqStore->litStart, (size_t)(seqStore->lit - seqStore->litStart),

+ &zc->blockState.nextCBlock->entropy,

+ entropyMetadata,

+ zc->tmpWorkspace, zc->tmpWkspSize,

+static size_t ZSTD_countSeqStoreLiteralsBytes(const SeqStore_t* const seqStore)

+{

+ size_t const nbSeqs = (size_t)(seqStore->sequences - seqStore->sequencesStart);

+ SeqDef const seq = seqStore->sequencesStart[i];

+ } }

+static size_t ZSTD_countSeqStoreMatchBytes(const SeqStore_t* const seqStore)

+{

+ size_t const nbSeqs = (size_t)(seqStore->sequences - seqStore->sequencesStart);

+ SeqDef seq = seqStore->sequencesStart[i];

+ } }

+static void ZSTD_deriveSeqStoreChunk(SeqStore_t* resultSeqStore,

+ const SeqStore_t* originalSeqStore,

+ size_t startIdx, size_t endIdx)

+{

+ resultSeqStore->litStart += ZSTD_countSeqStoreLiteralsBytes(resultSeqStore);

+ assert(resultSeqStore->lit == originalSeqStore->lit);

+ size_t const literalsBytes = ZSTD_countSeqStoreLiteralsBytes(resultSeqStore);

+ resultSeqStore->lit = resultSeqStore->litStart + literalsBytes;

+ * Returns the raw offset represented by the combination of offBase, ll0, and repcode history.

+ * offBase must represent a repcode in the numeric representation of ZSTD_storeSeq().

+ZSTD_resolveRepcodeToRawOffset(const U32 rep[ZSTD_REP_NUM], const U32 offBase, const U32 ll0)

+{

+ U32 const adjustedRepCode = OFFBASE_TO_REPCODE(offBase) - 1 + ll0; /* [ 0 - 3 ] */

+ assert(OFFBASE_IS_REPCODE(offBase));

+ if (adjustedRepCode == ZSTD_REP_NUM) {

+ assert(ll0);

+ /* litlength == 0 and offCode == 2 implies selection of first repcode - 1

+ * This is only valid if it results in a valid offset value, aka > 0.

+ * Note : it may happen that `rep[0]==1` in exceptional circumstances.

+ * In which case this function will return 0, which is an invalid offset.

+ * It's not an issue though, since this value will be

+ * compared and discarded within ZSTD_seqStore_resolveOffCodes().

+ */

+ return rep[adjustedRepCode];

+static void

+ZSTD_seqStore_resolveOffCodes(Repcodes_t* const dRepcodes, Repcodes_t* const cRepcodes,

+ const SeqStore_t* const seqStore, U32 const nbSeq)

+{

+ U32 const longLitLenIdx = seqStore->longLengthType == ZSTD_llt_literalLength ? seqStore->longLengthPos : nbSeq;

+ SeqDef* const seq = seqStore->sequencesStart + idx;

+ U32 const ll0 = (seq->litLength == 0) && (idx != longLitLenIdx);

+ U32 const offBase = seq->offBase;

+ assert(offBase > 0);

+ if (OFFBASE_IS_REPCODE(offBase)) {

+ U32 const dRawOffset = ZSTD_resolveRepcodeToRawOffset(dRepcodes->rep, offBase, ll0);

+ U32 const cRawOffset = ZSTD_resolveRepcodeToRawOffset(cRepcodes->rep, offBase, ll0);

+ seq->offBase = OFFSET_TO_OFFBASE(cRawOffset);

+ ZSTD_updateRep(dRepcodes->rep, seq->offBase, ll0);

+ ZSTD_updateRep(cRepcodes->rep, offBase, ll0);

+ZSTD_compressSeqStore_singleBlock(ZSTD_CCtx* zc,

+ const SeqStore_t* const seqStore,

+ Repcodes_t* const dRep, Repcodes_t* const cRep,

+ const void* src, size_t srcSize,

+ Repcodes_t const dRepOriginal = *dRep;

+ zc->tmpWorkspace, zc->tmpWkspSize /* statically allocated in resetCCtx */,

+ /* Sequence collection not supported when block splitting */

+ FORWARD_IF_ERROR(ZSTD_copyBlockSequences(&zc->seqCollector, seqStore, dRepOriginal.rep), "copyBlockSequences failed");

+ DEBUGLOG(5, "Writing out nocompress block, size: %zu", cSize);

+ DEBUGLOG(5, "Writing out RLE block, size: %zu", cSize);

+ DEBUGLOG(5, "Writing out compressed block, size: %zu", cSize);

+ * If advantageous to split, then we recurse down the two sub-blocks.

+ * If not, or if an error occurred in estimation, then we do not recurse.

+ * Note: The recursion depth is capped by a heuristic minimum number of sequences,

+ * defined by MIN_SEQUENCES_BLOCK_SPLITTING.

+ * Furthermore, the number of splits is capped by ZSTD_MAX_NB_BLOCK_SPLITS.

+ * At ZSTD_MAX_NB_BLOCK_SPLITS == 196 with the current existing blockSize

+ ZSTD_CCtx* zc, const SeqStore_t* origSeqStore)

+ SeqStore_t* const fullSeqStoreChunk = &zc->blockSplitCtx.fullSeqStoreChunk;

+ SeqStore_t* const firstHalfSeqStore = &zc->blockSplitCtx.firstHalfSeqStore;

+ SeqStore_t* const secondHalfSeqStore = &zc->blockSplitCtx.secondHalfSeqStore;

+ DEBUGLOG(5, "ZSTD_deriveBlockSplitsHelper: startIdx=%zu endIdx=%zu", startIdx, endIdx);

+ assert(endIdx >= startIdx);

+ DEBUGLOG(6, "ZSTD_deriveBlockSplitsHelper: Too few sequences (%zu)", endIdx - startIdx);

+ DEBUGLOG(5, "Estimated original block size: %zu -- First half split: %zu -- Second half split: %zu",

+ DEBUGLOG(5, "split decided at seqNb:%zu", midIdx);

+/* Base recursive function.

+ * Populates a table with intra-block partition indices that can improve compression ratio.

+ * @return: number of splits made (which equals the size of the partition table - 1).

+static size_t ZSTD_deriveBlockSplits(ZSTD_CCtx* zc, U32 partitions[], U32 nbSeq)

+{

+ seqStoreSplits splits;

+ splits.splitLocations = partitions;

+ splits.idx = 0;

+ DEBUGLOG(5, "ZSTD_deriveBlockSplits: Too few sequences to split (%u <= 4)", nbSeq);

+ZSTD_compressBlock_splitBlock_internal(ZSTD_CCtx* zc,

+ void* dst, size_t dstCapacity,

+ const void* src, size_t blockSize,

+ U32 lastBlock, U32 nbSeq)

+ U32* const partitions = zc->blockSplitCtx.partitions; /* size == ZSTD_MAX_NB_BLOCK_SPLITS */

+ SeqStore_t* const nextSeqStore = &zc->blockSplitCtx.nextSeqStore;

+ SeqStore_t* const currSeqStore = &zc->blockSplitCtx.currSeqStore;

+ size_t const numSplits = ZSTD_deriveBlockSplits(zc, partitions, nbSeq);

+ Repcodes_t dRep;

+ Repcodes_t cRep;

+ ZSTD_memcpy(dRep.rep, zc->blockState.prevCBlock->rep, sizeof(Repcodes_t));

+ ZSTD_memcpy(cRep.rep, zc->blockState.prevCBlock->rep, sizeof(Repcodes_t));

+ ZSTD_memset(nextSeqStore, 0, sizeof(SeqStore_t));

+ DEBUGLOG(5, "ZSTD_compressBlock_splitBlock_internal (dstCapacity=%u, dictLimit=%u, nextToUpdate=%u)",

+ size_t cSizeSingleBlock =

+ ZSTD_compressSeqStore_singleBlock(zc, &zc->seqStore,

+ &dRep, &cRep,

+ op, dstCapacity,

+ ip, blockSize,

+ lastBlock, 0 /* isPartition */);

+ assert(zc->blockSizeMax <= ZSTD_BLOCKSIZE_MAX);

+ assert(cSizeSingleBlock <= zc->blockSizeMax + ZSTD_blockHeaderSize);

+ size_t srcBytes = ZSTD_countSeqStoreLiteralsBytes(currSeqStore) + ZSTD_countSeqStoreMatchBytes(currSeqStore);

+ DEBUGLOG(5, "Estimated size: %zu vs %zu : actual size",

+ ZSTD_buildEntropyStatisticsAndEstimateSubBlockSize(currSeqStore, zc), cSizeChunk);

+ assert(cSizeChunk <= zc->blockSizeMax + ZSTD_blockHeaderSize);

+ /* cRep and dRep may have diverged during the compression.

+ * If so, we use the dRep repcodes for the next block.

+ ZSTD_memcpy(zc->blockState.prevCBlock->rep, dRep.rep, sizeof(Repcodes_t));

+ DEBUGLOG(5, "ZSTD_compressBlock_splitBlock");

+ assert(zc->appliedParams.postBlockSplitter == ZSTD_ps_enable);

+ RETURN_ERROR_IF(zc->seqCollector.collectSequences, sequenceProducer_failed, "Uncompressible block");

+ cSize = ZSTD_noCompressBlock(dst, dstCapacity, src, srcSize, lastBlock);

+ DEBUGLOG(5, "ZSTD_compressBlock_splitBlock: Nocompress block");

+ /* This is an estimated upper bound for the length of an rle block.

+ * This isn't the actual upper bound.

+ * Finding the real threshold needs further investigation.

+ if (bss == ZSTDbss_noCompress) {

+ RETURN_ERROR_IF(zc->seqCollector.collectSequences, sequenceProducer_failed, "Uncompressible block");

+ cSize = 0;

+ goto out;

+ }

+ FORWARD_IF_ERROR(ZSTD_copyBlockSequences(&zc->seqCollector, ZSTD_getSeqStore(zc), zc->blockState.prevCBlock->rep), "copyBlockSequences failed");

+ zc->tmpWorkspace, zc->tmpWkspSize /* statically allocated in resetCCtx */,

+ { size_t const cSize =

+ ZSTD_compressSuperBlock(zc, dst, dstCapacity, src, srcSize, lastBlock);

+ size_t const maxCSize =

+ srcSize - ZSTD_minGain(srcSize, zc->appliedParams.cParams.strategy);

+ } /* if (bss == ZSTDbss_compress)*/

+static void ZSTD_overflowCorrectIfNeeded(ZSTD_MatchState_t* ms,

+#include "zstd_preSplit.h"

+

+static size_t ZSTD_optimalBlockSize(ZSTD_CCtx* cctx, const void* src, size_t srcSize, size_t blockSizeMax, int splitLevel, ZSTD_strategy strat, S64 savings)

+{

+ /* split level based on compression strategy, from `fast` to `btultra2` */

+ static const int splitLevels[] = { 0, 0, 1, 2, 2, 3, 3, 4, 4, 4 };

+ /* note: conservatively only split full blocks (128 KB) currently.

+ * While it's possible to go lower, let's keep it simple for a first implementation.

+ * Besides, benefits of splitting are reduced when blocks are already small.

+ */

+ if (srcSize < 128 KB || blockSizeMax < 128 KB)

+ return MIN(srcSize, blockSizeMax);

+ /* do not split incompressible data though:

+ * require verified savings to allow pre-splitting.

+ * Note: as a consequence, the first full block is not split.

+ */

+ if (savings < 3) {

+ DEBUGLOG(6, "don't attempt splitting: savings (%i) too low", (int)savings);

+ return 128 KB;

+ }

+ /* apply @splitLevel, or use default value (which depends on @strat).

+ * note that splitting heuristic is still conditioned by @savings >= 3,

+ * so the first block will not reach this code path */

+ if (splitLevel == 1) return 128 KB;

+ if (splitLevel == 0) {

+ assert(ZSTD_fast <= strat && strat <= ZSTD_btultra2);

+ splitLevel = splitLevels[strat];

+ } else {

+ assert(2 <= splitLevel && splitLevel <= 6);

+ splitLevel -= 2;

+ }

+ return ZSTD_splitBlock(src, blockSizeMax, splitLevel, cctx->tmpWorkspace, cctx->tmpWkspSize);

+}

+

+* @return : compressed size, or an error code

+ size_t blockSizeMax = cctx->blockSizeMax;

+ S64 savings = (S64)cctx->consumedSrcSize - (S64)cctx->producedCSize;

+ DEBUGLOG(5, "ZSTD_compress_frameChunk (srcSize=%u, blockSizeMax=%u)", (unsigned)srcSize, (unsigned)blockSizeMax);

+ ZSTD_MatchState_t* const ms = &cctx->blockState.matchState;

+ size_t const blockSize = ZSTD_optimalBlockSize(cctx,

+ ip, remaining,

+ blockSizeMax,

+ cctx->appliedParams.preBlockSplitter_level,

+ cctx->appliedParams.cParams.strategy,

+ savings);

+ U32 const lastBlock = lastFrameChunk & (blockSize == remaining);

+ assert(blockSize <= remaining);

+

+ /* TODO: See 3090. We reduced MIN_CBLOCK_SIZE from 3 to 2 so to compensate we are adding

+ * additional 1. We need to revisit and change this logic to be more consistent */

+ RETURN_ERROR_IF(dstCapacity < ZSTD_blockHeaderSize + MIN_CBLOCK_SIZE + 1,

+ } /* if (ZSTD_useTargetCBlockSize(&cctx->appliedParams))*/

+

+ /* @savings is employed to ensure that splitting doesn't worsen expansion of incompressible data.

+ * Without splitting, the maximum expansion is 3 bytes per full block.

+ * An adversarial input could attempt to fudge the split detector,

+ * and make it split incompressible data, resulting in more block headers.

+ * Note that, since ZSTD_COMPRESSBOUND() assumes a worst case scenario of 1KB per block,

+ * and the splitter never creates blocks that small (current lower limit is 8 KB),

+ * there is already no risk to expand beyond ZSTD_COMPRESSBOUND() limit.

+ * But if the goal is to not expand by more than 3-bytes per 128 KB full block,

+ * then yes, it becomes possible to make the block splitter oversplit incompressible data.

+ * Using @savings, we enforce an even more conservative condition,

+ * requiring the presence of enough savings (at least 3 bytes) to authorize splitting,

+ * otherwise only full blocks are used.

+ * But being conservative is fine,

+ * since splitting barely compressible blocks is not fruitful anyway */

+ savings += (S64)blockSize - (S64)cSize;

+ const ZSTD_CCtx_params* params,

+ U64 pledgedSrcSize, U32 dictID)

+{

+ BYTE* const op = (BYTE*)dst;

+void ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq)

+ assert(cctx->stage == ZSTDcs_init);

+ assert(nbSeq == 0 || cctx->appliedParams.ldmParams.enableLdm != ZSTD_ps_enable);

+ ZSTD_MatchState_t* const ms = &cctx->blockState.matchState;

+ DEBUGLOG(5, "ZSTD_compressContinue_internal (blockSize=%u)", (unsigned)cctx->blockSizeMax);

+size_t ZSTD_compressContinue_public(ZSTD_CCtx* cctx,

+ void* dst, size_t dstCapacity,

+ const void* src, size_t srcSize)

+/* NOTE: Must just wrap ZSTD_compressContinue_public() */

+size_t ZSTD_compressContinue(ZSTD_CCtx* cctx,

+ void* dst, size_t dstCapacity,

+ const void* src, size_t srcSize)

+{

+ return ZSTD_compressContinue_public(cctx, dst, dstCapacity, src, srcSize);

+}

+static size_t ZSTD_getBlockSize_deprecated(const ZSTD_CCtx* cctx)

+ return MIN(cctx->appliedParams.maxBlockSize, (size_t)1 << cParams.windowLog);

+/* NOTE: Must just wrap ZSTD_getBlockSize_deprecated() */

+size_t ZSTD_getBlockSize(const ZSTD_CCtx* cctx)

+{

+ return ZSTD_getBlockSize_deprecated(cctx);

+}

+

+/* NOTE: Must just wrap ZSTD_compressBlock_deprecated() */

+size_t ZSTD_compressBlock_deprecated(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)

+ { size_t const blockSizeMax = ZSTD_getBlockSize_deprecated(cctx);

+/* NOTE: Must just wrap ZSTD_compressBlock_deprecated() */

+size_t ZSTD_compressBlock(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)

+{

+ return ZSTD_compressBlock_deprecated(cctx, dst, dstCapacity, src, srcSize);

+}

+

+static size_t

+ZSTD_loadDictionaryContent(ZSTD_MatchState_t* ms,

+ ldmState_t* ls,

+ ZSTD_cwksp* ws,

+ ZSTD_CCtx_params const* params,

+ const void* src, size_t srcSize,

+ ZSTD_dictTableLoadMethod_e dtlm,

+ ZSTD_tableFillPurpose_e tfp)

+ /* Assert that the ms params match the params we're being given */

+ { /* Ensure large dictionaries can't cause index overflow */

+

+ U32 maxDictSize = ZSTD_CURRENT_MAX - ZSTD_WINDOW_START_INDEX;

+

+ int const CDictTaggedIndices = ZSTD_CDictIndicesAreTagged(&params->cParams);

+ if (CDictTaggedIndices && tfp == ZSTD_tfp_forCDict) {

+ /* Some dictionary matchfinders in zstd use "short cache",

+ * which treats the lower ZSTD_SHORT_CACHE_TAG_BITS of each

+ * CDict hashtable entry as a tag rather than as part of an index.

+ * When short cache is used, we need to truncate the dictionary

+ * so that its indices don't overlap with the tag. */

+ U32 const shortCacheMaxDictSize = (1u << (32 - ZSTD_SHORT_CACHE_TAG_BITS)) - ZSTD_WINDOW_START_INDEX;

+ maxDictSize = MIN(maxDictSize, shortCacheMaxDictSize);

+ assert(!loadLdmDict);

+ }

+

+ if (srcSize > ZSTD_CHUNKSIZE_MAX) {

+ /* We must have cleared our windows when our source is this large. */

+ assert(ZSTD_window_isEmpty(ms->window));

+ if (loadLdmDict) assert(ZSTD_window_isEmpty(ls->window));

+ }

+ DEBUGLOG(4, "ZSTD_loadDictionaryContent: useRowMatchFinder=%d", (int)params->useRowMatchFinder);

+

+ if (loadLdmDict) { /* Load the entire dict into LDM matchfinders. */

+ DEBUGLOG(4, "ZSTD_loadDictionaryContent: Trigger loadLdmDict");

+ ZSTD_ldm_fillHashTable(ls, ip, iend, &params->ldmParams);

+ DEBUGLOG(4, "ZSTD_loadDictionaryContent: ZSTD_ldm_fillHashTable completes");

+ }

+

+ /* If the dict is larger than we can reasonably index in our tables, only load the suffix. */

+ { U32 maxDictSize = 1U << MIN(MAX(params->cParams.hashLog + 3, params->cParams.chainLog + 1), 31);

+ if (srcSize > maxDictSize) {

+ ip = iend - maxDictSize;

+ src = ip;

+ srcSize = maxDictSize;

+ }

+ ms->nextToUpdate = (U32)(ip - ms->window.base);

+ ms->loadedDictEnd = params->forceWindow ? 0 : (U32)(iend - ms->window.base);

+ ms->forceNonContiguous = params->deterministicRefPrefix;

+

+ ZSTD_fillHashTable(ms, iend, dtlm, tfp);

+#ifndef ZSTD_EXCLUDE_DFAST_BLOCK_COMPRESSOR

+ ZSTD_fillDoubleHashTable(ms, iend, dtlm, tfp);

+#else

+ assert(0); /* shouldn't be called: cparams should've been adjusted. */

+#endif

+#if !defined(ZSTD_EXCLUDE_GREEDY_BLOCK_COMPRESSOR) \

+ || !defined(ZSTD_EXCLUDE_LAZY_BLOCK_COMPRESSOR) \

+ || !defined(ZSTD_EXCLUDE_LAZY2_BLOCK_COMPRESSOR)

+ size_t const tagTableSize = ((size_t)1 << params->cParams.hashLog);

+#else

+ assert(0); /* shouldn't be called: cparams should've been adjusted. */

+#endif

+#if !defined(ZSTD_EXCLUDE_BTLAZY2_BLOCK_COMPRESSOR) \

+ || !defined(ZSTD_EXCLUDE_BTOPT_BLOCK_COMPRESSOR) \

+ || !defined(ZSTD_EXCLUDE_BTULTRA_BLOCK_COMPRESSOR)

+ DEBUGLOG(4, "Fill %u bytes into the Binary Tree", (unsigned)srcSize);

+#else

+ assert(0); /* shouldn't be called: cparams should've been adjusted. */

+#endif

+ (size_t)(dictEnd-dictPtr), &hasZeroWeights);

+ if (!hasZeroWeights && maxSymbolValue == 255)

+ size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, (size_t)(dictEnd-dictPtr));

+ size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, (size_t)(dictEnd-dictPtr));

+ size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, (size_t)(dictEnd-dictPtr));

+ return (size_t)(dictPtr - (const BYTE*)dict);

+ ZSTD_MatchState_t* ms,

+ ZSTD_tableFillPurpose_e tfp,

+ ms, NULL, ws, params, dictPtr, dictContentSize, dtlm, tfp), "");

+ ZSTD_MatchState_t* ms,

+ ZSTD_tableFillPurpose_e tfp,

+ return ZSTD_loadDictionaryContent(ms, ls, ws, params, dict, dictSize, dtlm, tfp);

+ ms, ls, ws, params, dict, dictSize, dtlm, tfp);

+ bs, ms, ws, params, dict, dictSize, dtlm, tfp, workspace);

+ * Assumption : either @dict OR @cdict (or none) is non-NULL, never both

+ ZSTD_tfp_forCCtx, cctx->tmpWorkspace)

+ dictContentType, dtlm, ZSTD_tfp_forCCtx, cctx->tmpWorkspace);

+static size_t

+ZSTD_compressBegin_usingDict_deprecated(ZSTD_CCtx* cctx, const void* dict, size_t dictSize, int compressionLevel)

+ { ZSTD_parameters const params = ZSTD_getParams_internal(compressionLevel, ZSTD_CONTENTSIZE_UNKNOWN, dictSize, ZSTD_cpm_noAttachDict);

+size_t

+ZSTD_compressBegin_usingDict(ZSTD_CCtx* cctx, const void* dict, size_t dictSize, int compressionLevel)

+{

+ return ZSTD_compressBegin_usingDict_deprecated(cctx, dict, dictSize, compressionLevel);

+}

+

+ return ZSTD_compressBegin_usingDict_deprecated(cctx, NULL, 0, compressionLevel);

+ size_t fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, &cctx->appliedParams, 0, 0);

+ ZSTD_STATIC_ASSERT(ZSTD_BLOCKHEADERSIZE == 3);

+ RETURN_ERROR_IF(dstCapacity<3, dstSize_tooSmall, "no room for epilogue");

+ MEM_writeLE24(op, cBlockHeader24);

+ return (size_t)(op-ostart);

+size_t ZSTD_compressEnd_public(ZSTD_CCtx* cctx,

+ void* dst, size_t dstCapacity,

+ const void* src, size_t srcSize)

+/* NOTE: Must just wrap ZSTD_compressEnd_public() */

+size_t ZSTD_compressEnd(ZSTD_CCtx* cctx,

+ void* dst, size_t dstCapacity,

+ const void* src, size_t srcSize)

+{

+ return ZSTD_compressEnd_public(cctx, dst, dstCapacity, src, srcSize);

+}

+

+ return ZSTD_compressEnd_public(cctx, dst, dstCapacity, src, srcSize);

+ dictContentType, ZSTD_dtlm_full, ZSTD_tfp_forCDict, cdict->entropyWorkspace);

+static ZSTD_CDict*

+ZSTD_createCDict_advanced_internal(size_t dictSize,

+ ZSTD_dictLoadMethod_e dictLoadMethod,

+ ZSTD_compressionParameters cParams,

+ ZSTD_ParamSwitch_e useRowMatchFinder,

+ int enableDedicatedDictSearch,

+ ZSTD_customMem customMem)

+ DEBUGLOG(3, "ZSTD_createCDict_advanced_internal (dictSize=%u)", (unsigned)dictSize);

+ DEBUGLOG(3, "ZSTD_createCDict_advanced, dictSize=%u, mode=%u", (unsigned)dictSize, (unsigned)dictContentType);

+ DEBUGLOG(3, "ZSTD_createCDict_advanced2, dictSize=%u, mode=%u", (unsigned)dictSize, (unsigned)dictContentType);

+ DEBUGLOG(3, "ZSTD_createCDict_advanced2: DedicatedDictSearch=%u", cctxParams.enableDedicatedDictSearch);

+ if (!cdict || ZSTD_isError( ZSTD_initCDict_internal(cdict,

+ * into its relevant cParams.

+ ZSTD_ParamSwitch_e const useRowMatchFinder = ZSTD_resolveRowMatchFinderMode(ZSTD_ps_auto, &cParams);

+ DEBUGLOG(4, "ZSTD_initStaticCDict (dictSize==%u)", (unsigned)dictSize);

+ cdict->compressionLevel = ZSTD_NO_CLEVEL;

+size_t ZSTD_compressBegin_usingCDict_deprecated(ZSTD_CCtx* cctx, const ZSTD_CDict* cdict)

+size_t ZSTD_compressBegin_usingCDict(ZSTD_CCtx* cctx, const ZSTD_CDict* cdict)

+{

+ return ZSTD_compressBegin_usingCDict_deprecated(cctx, cdict);

+}

+

+ return ZSTD_compressEnd_public(cctx, dst, dstCapacity, src, srcSize);

+static ZSTD_CParamMode_e ZSTD_getCParamMode(ZSTD_CDict const* cdict, ZSTD_CCtx_params const* params, U64 pledgedSrcSize)

+ if (cctx->appliedParams.inBufferMode == ZSTD_bm_stable) {

+ return cctx->blockSizeMax - cctx->stableIn_notConsumed;

+ }

+ assert(cctx->appliedParams.inBufferMode == ZSTD_bm_buffered);

+ { size_t hintInSize = cctx->inBuffTarget - cctx->inBuffPos;

+ if (hintInSize==0) hintInSize = cctx->blockSizeMax;

+ return hintInSize;

+ }

+ * @return : hint size for next input to complete ongoing block */

+ const char* const istart = (assert(input != NULL), (const char*)input->src);

+ const char* const iend = (istart != NULL) ? istart + input->size : istart;

+ const char* ip = (istart != NULL) ? istart + input->pos : istart;

+ char* const ostart = (assert(output != NULL), (char*)output->dst);

+ char* const oend = (ostart != NULL) ? ostart + output->size : ostart;

+ char* op = (ostart != NULL) ? ostart + output->pos : ostart;

+ DEBUGLOG(5, "ZSTD_compressStream_generic, flush=%i, srcSize = %zu", (int)flushMode, input->size - input->pos);

+ assert(zcs != NULL);

+ if (zcs->appliedParams.inBufferMode == ZSTD_bm_stable) {

+ assert(input->pos >= zcs->stableIn_notConsumed);

+ input->pos -= zcs->stableIn_notConsumed;

+ if (ip) ip -= zcs->stableIn_notConsumed;

+ zcs->stableIn_notConsumed = 0;

+ }

+ if (input->src == NULL) assert(input->size == 0);

+ if (output->dst == NULL) assert(output->size == 0);

+ assert(output->pos <= output->size);

+ && ( (size_t)(oend-op) >= ZSTD_compressBound((size_t)(iend-ip)) /* Enough output space */

+ size_t const cSize = ZSTD_compressEnd_public(zcs,

+ op, (size_t)(oend-op),

+ ip, (size_t)(iend-ip));

+ ip, (size_t)(iend-ip));

+ if (ip) ip += loaded;

+ } else {

+ assert(zcs->appliedParams.inBufferMode == ZSTD_bm_stable);

+ if ( (flushMode == ZSTD_e_continue)

+ && ( (size_t)(iend - ip) < zcs->blockSizeMax) ) {

+ /* can't compress a full block : stop here */

+ zcs->stableIn_notConsumed = (size_t)(iend - ip);

+ ip = iend; /* pretend to have consumed input */

+ someMoreWork = 0; break;

+ }

+ if ( (flushMode == ZSTD_e_flush)

+ && (ip == iend) ) {

+ /* empty */

+ someMoreWork = 0; break;

+ }

+ size_t oSize = (size_t)(oend-op);

+ size_t const iSize = inputBuffered ? zcs->inBuffPos - zcs->inToCompress

+ : MIN((size_t)(iend - ip), zcs->blockSizeMax);

+ ZSTD_compressEnd_public(zcs, cDst, oSize,

+ ZSTD_compressContinue_public(zcs, cDst, oSize,

+ zcs->inBuffTarget = zcs->inBuffPos + zcs->blockSizeMax;

+ zcs->inBuffPos = 0, zcs->inBuffTarget = zcs->blockSizeMax;

+ } else { /* !inputBuffered, hence ZSTD_bm_stable */

+ unsigned const lastBlock = (flushMode == ZSTD_e_end) && (ip + iSize == iend);

+ ZSTD_compressEnd_public(zcs, cDst, oSize, ip, iSize) :

+ ZSTD_compressContinue_public(zcs, cDst, oSize, ip, iSize);

+ if (ip) ip += iSize;

+ if (lastBlock) assert(ip == iend);

+ input->pos = (size_t)(ip - istart);

+ output->pos = (size_t)(op - ostart);

+static void

+ZSTD_setBufferExpectations(ZSTD_CCtx* cctx, const ZSTD_outBuffer* output, const ZSTD_inBuffer* input)

+ DEBUGLOG(5, "ZSTD_setBufferExpectations (for advanced stable in/out modes)");

+ if (expect.src != input->src || expect.pos != input->pos)

+ RETURN_ERROR(stabilityCondition_notRespected, "ZSTD_c_stableInBuffer enabled but input differs!");

+ (void)endOp;

+ RETURN_ERROR(stabilityCondition_notRespected, "ZSTD_c_stableOutBuffer enabled but output size differs!");

+/*

+ * If @endOp == ZSTD_e_end, @inSize becomes pledgedSrcSize.

+ * Otherwise, it's ignored.

+ * @return: 0 on success, or a ZSTD_error code otherwise.

+ */

+ size_t inSize)

+{

+ DEBUGLOG(4, "ZSTD_CCtx_init_compressStream2 : transparent init stage");

+ if (endOp == ZSTD_e_end) cctx->pledgedSrcSizePlusOne = inSize + 1; /* auto-determine pledgedSrcSize */

+

+ { size_t const dictSize = prefixDict.dict

+ ZSTD_CParamMode_e const mode = ZSTD_getCParamMode(cctx->cdict, &params, cctx->pledgedSrcSizePlusOne - 1);

+ params.postBlockSplitter = ZSTD_resolveBlockSplitterMode(params.postBlockSplitter, &params.cParams);

+ params.validateSequences = ZSTD_resolveExternalSequenceValidation(params.validateSequences);

+ params.maxBlockSize = ZSTD_resolveMaxBlockSize(params.maxBlockSize);

+ params.searchForExternalRepcodes = ZSTD_resolveExternalRepcodeSearch(params.searchForExternalRepcodes, params.compressionLevel);

+ cctx->inBuffTarget = cctx->blockSizeMax + (cctx->blockSizeMax == pledgedSrcSize);

+/* @return provides a minimum amount of data remaining to be flushed from internal buffers

+ */

+ size_t const inputSize = input->size - input->pos; /* no obligation to start from pos==0 */

+ size_t const totalInputSize = inputSize + cctx->stableIn_notConsumed;

+ if ( (cctx->requestedParams.inBufferMode == ZSTD_bm_stable) /* input is presumed stable, across invocations */

+ && (endOp == ZSTD_e_continue) /* no flush requested, more input to come */

+ && (totalInputSize < ZSTD_BLOCKSIZE_MAX) ) { /* not even reached one block yet */

+ if (cctx->stableIn_notConsumed) { /* not the first time */

+ /* check stable source guarantees */

+ RETURN_ERROR_IF(input->src != cctx->expectedInBuffer.src, stabilityCondition_notRespected, "stableInBuffer condition not respected: wrong src pointer");

+ RETURN_ERROR_IF(input->pos != cctx->expectedInBuffer.size, stabilityCondition_notRespected, "stableInBuffer condition not respected: externally modified pos");

+ }

+ /* pretend input was consumed, to give a sense forward progress */

+ input->pos = input->size;

+ /* save stable inBuffer, for later control, and flush/end */

+ cctx->expectedInBuffer = *input;

+ /* but actually input wasn't consumed, so keep track of position from where compression shall resume */

+ cctx->stableIn_notConsumed += inputSize;

+ /* don't initialize yet, wait for the first block of flush() order, for better parameters adaptation */

+ return ZSTD_FRAMEHEADERSIZE_MIN(cctx->requestedParams.format); /* at least some header to produce */

+ }

+ FORWARD_IF_ERROR(ZSTD_CCtx_init_compressStream2(cctx, endOp, totalInputSize), "compressStream2 initialization failed");

+ ZSTD_setBufferExpectations(cctx, output, input); /* Set initial buffer expectations now that we've initialized */

+ ZSTD_outBuffer output;

+ ZSTD_inBuffer input;

+ output.dst = dst;

+ output.size = dstCapacity;

+ output.pos = *dstPos;

+ input.src = src;

+ input.size = srcSize;

+ input.pos = *srcPos;

+ { size_t const cErr = ZSTD_compressStream2(cctx, &output, &input, endOp);

+ *dstPos = output.pos;

+ *srcPos = input.pos;

+ return cErr;

+ }

+

+ * @offBase : must use the format required by ZSTD_storeSeq()

+ZSTD_validateSequence(U32 offBase, U32 matchLength, U32 minMatch,

+ size_t posInSrc, U32 windowLog, size_t dictSize, int useSequenceProducer)

+ U32 const windowSize = 1u << windowLog;

+ size_t const matchLenLowerBound = (minMatch == 3 || useSequenceProducer) ? 3 : 4;

+ RETURN_ERROR_IF(offBase > OFFSET_TO_OFFBASE(offsetBound), externalSequences_invalid, "Offset too large!");

+ /* Validate maxNbSeq is large enough for the given matchLength and minMatch */

+ RETURN_ERROR_IF(matchLength < matchLenLowerBound, externalSequences_invalid, "Matchlength too small for the minMatch");

+static U32 ZSTD_finalizeOffBase(U32 rawOffset, const U32 rep[ZSTD_REP_NUM], U32 ll0)

+ U32 offBase = OFFSET_TO_OFFBASE(rawOffset);

+ offBase = REPCODE1_TO_OFFBASE;

+ offBase = REPCODE_TO_OFFBASE(2 - ll0);

+ offBase = REPCODE_TO_OFFBASE(3 - ll0);

+ offBase = REPCODE3_TO_OFFBASE;

+ return offBase;

+/* This function scans through an array of ZSTD_Sequence,

+ * storing the sequences it reads, until it reaches a block delimiter.

+ * Note that the block delimiter includes the last literals of the block.

+ * @blockSize must be == sum(sequence_lengths).

+ * @returns @blockSize on success, and a ZSTD_error otherwise.

+ZSTD_transferSequences_wBlockDelim(ZSTD_CCtx* cctx,

+ ZSTD_SequencePosition* seqPos,

+ const ZSTD_Sequence* const inSeqs, size_t inSeqsSize,

+ const void* src, size_t blockSize,

+ ZSTD_ParamSwitch_e externalRepSearch)

+ U32 const startIdx = idx;

+ Repcodes_t updatedRepcodes;

+ DEBUGLOG(5, "ZSTD_transferSequences_wBlockDelim (blockSize = %zu)", blockSize);

+

+ ZSTD_memcpy(updatedRepcodes.rep, cctx->blockState.prevCBlock->rep, sizeof(Repcodes_t));

+ for (; idx < inSeqsSize && (inSeqs[idx].matchLength != 0 || inSeqs[idx].offset != 0); ++idx) {

+ U32 offBase;

+ if (externalRepSearch == ZSTD_ps_disable) {

+ offBase = OFFSET_TO_OFFBASE(inSeqs[idx].offset);

+ } else {

+ U32 const ll0 = (litLength == 0);

+ offBase = ZSTD_finalizeOffBase(inSeqs[idx].offset, updatedRepcodes.rep, ll0);

+ ZSTD_updateRep(updatedRepcodes.rep, offBase, ll0);

+ }

+

+ DEBUGLOG(6, "Storing sequence: (of: %u, ml: %u, ll: %u)", offBase, matchLength, litLength);

+ FORWARD_IF_ERROR(ZSTD_validateSequence(offBase, matchLength, cctx->appliedParams.cParams.minMatch,

+ seqPos->posInSrc,

+ cctx->appliedParams.cParams.windowLog, dictSize,

+ ZSTD_hasExtSeqProd(&cctx->appliedParams)),

+ RETURN_ERROR_IF(idx - seqPos->idx >= cctx->seqStore.maxNbSeq, externalSequences_invalid,

+ ZSTD_storeSeq(&cctx->seqStore, litLength, ip, iend, offBase, matchLength);

+ RETURN_ERROR_IF(idx == inSeqsSize, externalSequences_invalid, "Block delimiter not found.");

+

+ /* If we skipped repcode search while parsing, we need to update repcodes now */

+ assert(externalRepSearch != ZSTD_ps_auto);

+ assert(idx >= startIdx);

+ if (externalRepSearch == ZSTD_ps_disable && idx != startIdx) {

+ U32* const rep = updatedRepcodes.rep;

+ U32 lastSeqIdx = idx - 1; /* index of last non-block-delimiter sequence */

+

+ if (lastSeqIdx >= startIdx + 2) {

+ rep[2] = inSeqs[lastSeqIdx - 2].offset;

+ rep[1] = inSeqs[lastSeqIdx - 1].offset;

+ rep[0] = inSeqs[lastSeqIdx].offset;

+ } else if (lastSeqIdx == startIdx + 1) {

+ rep[2] = rep[0];

+ rep[1] = inSeqs[lastSeqIdx - 1].offset;

+ rep[0] = inSeqs[lastSeqIdx].offset;

+ } else {

+ assert(lastSeqIdx == startIdx);

+ rep[2] = rep[1];

+ rep[1] = rep[0];

+ rep[0] = inSeqs[lastSeqIdx].offset;

+ }

+ }

+

+ ZSTD_memcpy(cctx->blockState.nextCBlock->rep, updatedRepcodes.rep, sizeof(Repcodes_t));

+ RETURN_ERROR_IF(ip != iend, externalSequences_invalid, "Blocksize doesn't agree with block delimiter!");

+ return blockSize;

+/*

+ * This function attempts to scan through @blockSize bytes in @src

+ * represented by the sequences in @inSeqs,

+ * storing any (partial) sequences.

+ * Occasionally, we may want to reduce the actual number of bytes consumed from @src

+ * to avoid splitting a match, notably if it would produce a match smaller than MINMATCH.

+ * @returns the number of bytes consumed from @src, necessarily <= @blockSize.

+ * Otherwise, it may return a ZSTD error if something went wrong.

+ZSTD_transferSequences_noDelim(ZSTD_CCtx* cctx,

+ ZSTD_SequencePosition* seqPos,

+ const ZSTD_Sequence* const inSeqs, size_t inSeqsSize,

+ const void* src, size_t blockSize,

+ ZSTD_ParamSwitch_e externalRepSearch)

+ const BYTE* const istart = (const BYTE*)(src);

+ const BYTE* ip = istart;

+ const BYTE* iend = istart + blockSize; /* May be adjusted if we decide to process fewer than blockSize bytes */

+ Repcodes_t updatedRepcodes;

+ /* TODO(embg) support fast parsing mode in noBlockDelim mode */

+ (void)externalRepSearch;

+

+ DEBUGLOG(5, "ZSTD_transferSequences_noDelim: idx: %u PIS: %u blockSize: %zu", idx, startPosInSequence, blockSize);

+ ZSTD_memcpy(updatedRepcodes.rep, cctx->blockState.prevCBlock->rep, sizeof(Repcodes_t));

+ U32 offBase;

+ offBase = ZSTD_finalizeOffBase(rawOffset, updatedRepcodes.rep, ll0);

+ ZSTD_updateRep(updatedRepcodes.rep, offBase, ll0);

+ FORWARD_IF_ERROR(ZSTD_validateSequence(offBase, matchLength, cctx->appliedParams.cParams.minMatch, seqPos->posInSrc,

+ cctx->appliedParams.cParams.windowLog, dictSize, ZSTD_hasExtSeqProd(&cctx->appliedParams)),

+ DEBUGLOG(6, "Storing sequence: (of: %u, ml: %u, ll: %u)", offBase, matchLength, litLength);

+ RETURN_ERROR_IF(idx - seqPos->idx >= cctx->seqStore.maxNbSeq, externalSequences_invalid,

+ ZSTD_storeSeq(&cctx->seqStore, litLength, ip, iend, offBase, matchLength);

+ if (!finalMatchSplit)

+ idx++; /* Next Sequence */

+ ZSTD_memcpy(cctx->blockState.nextCBlock->rep, updatedRepcodes.rep, sizeof(Repcodes_t));

+ U32 const lastLLSize = (U32)(iend - ip);

+ return (size_t)(iend-istart);

+/* @seqPos represents a position within @inSeqs,

+ * it is read and updated by this function,

+ * once the goal to produce a block of size @blockSize is reached.

+ * @return: nb of bytes consumed from @src, necessarily <= @blockSize.

+ */

+typedef size_t (*ZSTD_SequenceCopier_f)(ZSTD_CCtx* cctx,

+ ZSTD_SequencePosition* seqPos,

+ const ZSTD_Sequence* const inSeqs, size_t inSeqsSize,

+ const void* src, size_t blockSize,

+ ZSTD_ParamSwitch_e externalRepSearch);

+

+static ZSTD_SequenceCopier_f ZSTD_selectSequenceCopier(ZSTD_SequenceFormat_e mode)

+ assert(ZSTD_cParam_withinBounds(ZSTD_c_blockDelimiters, (int)mode));

+ return ZSTD_transferSequences_wBlockDelim;

+ }

+ assert(mode == ZSTD_sf_noBlockDelimiters);

+ return ZSTD_transferSequences_noDelim;

+}

+

+/* Discover the size of next block by searching for the delimiter.

+ * Note that a block delimiter **must** exist in this mode,

+ * otherwise it's an input error.

+ * The block size retrieved will be later compared to ensure it remains within bounds */

+static size_t

+blockSize_explicitDelimiter(const ZSTD_Sequence* inSeqs, size_t inSeqsSize, ZSTD_SequencePosition seqPos)

+{

+ int end = 0;

+ size_t blockSize = 0;

+ size_t spos = seqPos.idx;

+ DEBUGLOG(6, "blockSize_explicitDelimiter : seq %zu / %zu", spos, inSeqsSize);

+ assert(spos <= inSeqsSize);

+ while (spos < inSeqsSize) {

+ end = (inSeqs[spos].offset == 0);

+ blockSize += inSeqs[spos].litLength + inSeqs[spos].matchLength;

+ if (end) {

+ if (inSeqs[spos].matchLength != 0)

+ RETURN_ERROR(externalSequences_invalid, "delimiter format error : both matchlength and offset must be == 0");

+ break;

+ }

+ spos++;

+ }

+ if (!end)

+ RETURN_ERROR(externalSequences_invalid, "Reached end of sequences without finding a block delimiter");

+ return blockSize;

+}

+

+static size_t determine_blockSize(ZSTD_SequenceFormat_e mode,

+ size_t blockSize, size_t remaining,

+ const ZSTD_Sequence* inSeqs, size_t inSeqsSize,

+ ZSTD_SequencePosition seqPos)

+{

+ DEBUGLOG(6, "determine_blockSize : remainingSize = %zu", remaining);

+ if (mode == ZSTD_sf_noBlockDelimiters) {

+ /* Note: more a "target" block size */

+ return MIN(remaining, blockSize);

+ }

+ assert(mode == ZSTD_sf_explicitBlockDelimiters);

+ { size_t const explicitBlockSize = blockSize_explicitDelimiter(inSeqs, inSeqsSize, seqPos);

+ FORWARD_IF_ERROR(explicitBlockSize, "Error while determining block size with explicit delimiters");

+ if (explicitBlockSize > blockSize)

+ RETURN_ERROR(externalSequences_invalid, "sequences incorrectly define a too large block");

+ if (explicitBlockSize > remaining)

+ RETURN_ERROR(externalSequences_invalid, "sequences define a frame longer than source");

+ return explicitBlockSize;

+/* Compress all provided sequences, block-by-block.

+ ZSTD_SequencePosition seqPos = {0, 0, 0};

+ const BYTE* ip = (BYTE const*)src;

+ ZSTD_SequenceCopier_f const sequenceCopier = ZSTD_selectSequenceCopier(cctx->appliedParams.blockDelimiters);

+ size_t compressedSeqsSize;

+ size_t blockSize = determine_blockSize(cctx->appliedParams.blockDelimiters,

+ cctx->blockSizeMax, remaining,

+ inSeqs, inSeqsSize, seqPos);

+ U32 const lastBlock = (blockSize == remaining);

+ FORWARD_IF_ERROR(blockSize, "Error while trying to determine block size");

+ assert(blockSize <= remaining);

+ blockSize = sequenceCopier(cctx,

+ &seqPos, inSeqs, inSeqsSize,

+ ip, blockSize,

+ cctx->appliedParams.searchForExternalRepcodes);

+ FORWARD_IF_ERROR(blockSize, "Bad sequence copy");

+ /* TODO: See 3090. We reduced MIN_CBLOCK_SIZE from 3 to 2 so to compensate we are adding

+ * additional 1. We need to revisit and change this logic to be more consistent */

+ if (blockSize < MIN_CBLOCK_SIZE+ZSTD_blockHeaderSize+1+1) {

+ DEBUGLOG(5, "Block too small (%zu): data remains uncompressed: cSize=%zu", blockSize, cBlockSize);

+ RETURN_ERROR_IF(dstCapacity < ZSTD_blockHeaderSize, dstSize_tooSmall, "not enough dstCapacity to write a new compressed block");

+ cctx->tmpWorkspace, cctx->tmpWkspSize /* statically allocated in resetCCtx */,

+ DEBUGLOG(5, "Compressed sequences size: %zu", compressedSeqsSize);

+ ZSTD_isRLE(ip, blockSize)) {

+ /* Note: don't emit the first block as RLE even if it qualifies because

+ * doing so will cause the decoder (cli <= v1.4.3 only) to throw an (invalid) error

+ * "should consume all input error."

+ */

+ FORWARD_IF_ERROR(cBlockSize, "ZSTD_noCompressBlock failed");

+ DEBUGLOG(5, "Writing out nocompress block, size: %zu", cBlockSize);

+ FORWARD_IF_ERROR(cBlockSize, "ZSTD_rleCompressBlock failed");

+ DEBUGLOG(5, "Writing out RLE block, size: %zu", cBlockSize);

+ DEBUGLOG(5, "Writing out compressed block, size: %zu", cBlockSize);

+ DEBUGLOG(5, "cSize running total: %zu (remaining dstCapacity=%zu)", cSize, dstCapacity);

+ DEBUGLOG(4, "cSize final total: %zu", cSize);

+size_t ZSTD_compressSequences(ZSTD_CCtx* cctx,

+ void* dst, size_t dstCapacity,

+ DEBUGLOG(4, "ZSTD_compressSequences (nbSeqs=%zu,dstCapacity=%zu)", inSeqsSize, dstCapacity);

+

+ { size_t const frameHeaderSize = ZSTD_writeFrameHeader(op, dstCapacity,

+ &cctx->appliedParams, srcSize, cctx->dictID);

+ op += frameHeaderSize;

+ assert(frameHeaderSize <= dstCapacity);

+ dstCapacity -= frameHeaderSize;

+ cSize += frameHeaderSize;

+ }

+

+ /* Now generate compressed blocks */

+ { size_t const cBlocksSize = ZSTD_compressSequences_internal(cctx,

+ FORWARD_IF_ERROR(cBlocksSize, "Compressing blocks failed!");

+ cSize += cBlocksSize;

+ assert(cBlocksSize <= dstCapacity);

+ dstCapacity -= cBlocksSize;

+ }

+ /* Complete with frame checksum, if needed */

+ DEBUGLOG(4, "Final compressed size: %zu", cSize);

+ return cSize;

+}

+

+

+#if defined(__AVX2__)

+

+#include <immintrin.h> /* AVX2 intrinsics */

+

+/*

+ * Convert 2 sequences per iteration, using AVX2 intrinsics:

+ * - offset -> offBase = offset + 2

+ * - litLength -> (U16) litLength

+ * - matchLength -> (U16)(matchLength - 3)

+ * - rep is ignored

+ * Store only 8 bytes per SeqDef (offBase[4], litLength[2], mlBase[2]).

+ *

+ * At the end, instead of extracting two __m128i,

+ * we use _mm256_permute4x64_epi64(..., 0xE8) to move lane2 into lane1,

+ * then store the lower 16 bytes in one go.

+ *

+ * @returns 0 on succes, with no long length detected

+ * @returns > 0 if there is one long length (> 65535),

+ * indicating the position, and type.

+ */

+static size_t convertSequences_noRepcodes(

+ SeqDef* dstSeqs,

+ const ZSTD_Sequence* inSeqs,

+ size_t nbSequences)

+{

+ /*

+ * addition:

+ * For each 128-bit half: (offset+2, litLength+0, matchLength-3, rep+0)

+ */

+ const __m256i addition = _mm256_setr_epi32(

+ ZSTD_REP_NUM, 0, -MINMATCH, 0, /* for sequence i */

+ ZSTD_REP_NUM, 0, -MINMATCH, 0 /* for sequence i+1 */

+ );

+

+ /* limit: check if there is a long length */

+ const __m256i limit = _mm256_set1_epi32(65535);

+

+ /*

+ * shuffle mask for byte-level rearrangement in each 128-bit half:

+ *

+ * Input layout (after addition) per 128-bit half:

+ * [ offset+2 (4 bytes) | litLength (4 bytes) | matchLength (4 bytes) | rep (4 bytes) ]

+ * We only need:

+ * offBase (4 bytes) = offset+2

+ * litLength (2 bytes) = low 2 bytes of litLength

+ * mlBase (2 bytes) = low 2 bytes of (matchLength)

+ * => Bytes [0..3, 4..5, 8..9], zero the rest.

+ */

+ const __m256i mask = _mm256_setr_epi8(

+ /* For the lower 128 bits => sequence i */

+ 0, 1, 2, 3, /* offset+2 */

+ 4, 5, /* litLength (16 bits) */

+ 8, 9, /* matchLength (16 bits) */

+ (BYTE)0x80, (BYTE)0x80, (BYTE)0x80, (BYTE)0x80,

+ (BYTE)0x80, (BYTE)0x80, (BYTE)0x80, (BYTE)0x80,

+

+ /* For the upper 128 bits => sequence i+1 */

+ 16,17,18,19, /* offset+2 */

+ 20,21, /* litLength */

+ 24,25, /* matchLength */

+ (BYTE)0x80, (BYTE)0x80, (BYTE)0x80, (BYTE)0x80,

+ (BYTE)0x80, (BYTE)0x80, (BYTE)0x80, (BYTE)0x80

+ );

+

+ /*

+ * Next, we'll use _mm256_permute4x64_epi64(vshf, 0xE8).

+ * Explanation of 0xE8 = 11101000b => [lane0, lane2, lane2, lane3].

+ * So the lower 128 bits become [lane0, lane2] => combining seq0 and seq1.

+ */

+#define PERM_LANE_0X_E8 0xE8 /* [0,2,2,3] in lane indices */

+

+ size_t longLen = 0, i = 0;

+

+ /* AVX permutation depends on the specific definition of target structures */

+ ZSTD_STATIC_ASSERT(sizeof(ZSTD_Sequence) == 16);

+ ZSTD_STATIC_ASSERT(offsetof(ZSTD_Sequence, offset) == 0);

+ ZSTD_STATIC_ASSERT(offsetof(ZSTD_Sequence, litLength) == 4);

+ ZSTD_STATIC_ASSERT(offsetof(ZSTD_Sequence, matchLength) == 8);

+ ZSTD_STATIC_ASSERT(sizeof(SeqDef) == 8);

+ ZSTD_STATIC_ASSERT(offsetof(SeqDef, offBase) == 0);

+ ZSTD_STATIC_ASSERT(offsetof(SeqDef, litLength) == 4);

+ ZSTD_STATIC_ASSERT(offsetof(SeqDef, mlBase) == 6);

+

+ /* Process 2 sequences per loop iteration */

+ for (; i + 1 < nbSequences; i += 2) {

+ /* Load 2 ZSTD_Sequence (32 bytes) */

+ __m256i vin = _mm256_loadu_si256((const __m256i*)(const void*)&inSeqs[i]);

+

+ /* Add {2, 0, -3, 0} in each 128-bit half */

+ __m256i vadd = _mm256_add_epi32(vin, addition);

+

+ /* Check for long length */

+ __m256i ll_cmp = _mm256_cmpgt_epi32(vadd, limit); /* 0xFFFFFFFF for element > 65535 */

+ int ll_res = _mm256_movemask_epi8(ll_cmp);

+

+ /* Shuffle bytes so each half gives us the 8 bytes we need */

+ __m256i vshf = _mm256_shuffle_epi8(vadd, mask);

+ /*

+ * Now:

+ * Lane0 = seq0's 8 bytes

+ * Lane1 = 0

+ * Lane2 = seq1's 8 bytes

+ * Lane3 = 0

+ */

+

+ /* Permute 64-bit lanes => move Lane2 down into Lane1. */

+ __m256i vperm = _mm256_permute4x64_epi64(vshf, PERM_LANE_0X_E8);

+ /*

+ * Now the lower 16 bytes (Lane0+Lane1) = [seq0, seq1].

+ * The upper 16 bytes are [Lane2, Lane3] = [seq1, 0], but we won't use them.

+ */

+

+ /* Store only the lower 16 bytes => 2 SeqDef (8 bytes each) */

+ _mm_storeu_si128((__m128i *)(void*)&dstSeqs[i], _mm256_castsi256_si128(vperm));

+ /*

+ * This writes out 16 bytes total:

+ * - offset 0..7 => seq0 (offBase, litLength, mlBase)

+ * - offset 8..15 => seq1 (offBase, litLength, mlBase)

+ */

+

+ /* check (unlikely) long lengths > 65535

+ * indices for lengths correspond to bits [4..7], [8..11], [20..23], [24..27]

+ * => combined mask = 0x0FF00FF0

+ */

+ if (UNLIKELY((ll_res & 0x0FF00FF0) != 0)) {

+ /* long length detected: let's figure out which one*/

+ if (inSeqs[i].matchLength > 65535+MINMATCH) {

+ assert(longLen == 0);

+ longLen = i + 1;

+ }

+ if (inSeqs[i].litLength > 65535) {

+ assert(longLen == 0);

+ longLen = i + nbSequences + 1;

+ }

+ if (inSeqs[i+1].matchLength > 65535+MINMATCH) {

+ assert(longLen == 0);

+ longLen = i + 1 + 1;

+ }

+ if (inSeqs[i+1].litLength > 65535) {

+ assert(longLen == 0);

+ longLen = i + 1 + nbSequences + 1;

+ }

+ }

+ }

+

+ /* Handle leftover if @nbSequences is odd */

+ if (i < nbSequences) {

+ /* process last sequence */

+ assert(i == nbSequences - 1);

+ dstSeqs[i].offBase = OFFSET_TO_OFFBASE(inSeqs[i].offset);

+ dstSeqs[i].litLength = (U16)inSeqs[i].litLength;

+ dstSeqs[i].mlBase = (U16)(inSeqs[i].matchLength - MINMATCH);

+ /* check (unlikely) long lengths > 65535 */

+ if (UNLIKELY(inSeqs[i].matchLength > 65535+MINMATCH)) {

+ assert(longLen == 0);

+ longLen = i + 1;

+ }

+ if (UNLIKELY(inSeqs[i].litLength > 65535)) {

+ assert(longLen == 0);

+ longLen = i + nbSequences + 1;

+ }

+ }

+

+ return longLen;

+}

+

+/* the vector implementation could also be ported to SSSE3,

+ * but since this implementation is targeting modern systems (>= Sapphire Rapid),

+ * it's not useful to develop and maintain code for older pre-AVX2 platforms */

+

+#else /* no AVX2 */

+

+static size_t convertSequences_noRepcodes(

+ SeqDef* dstSeqs,

+ const ZSTD_Sequence* inSeqs,

+ size_t nbSequences)

+{

+ size_t longLen = 0;

+ size_t n;

+ for (n=0; n<nbSequences; n++) {

+ dstSeqs[n].offBase = OFFSET_TO_OFFBASE(inSeqs[n].offset);

+ dstSeqs[n].litLength = (U16)inSeqs[n].litLength;

+ dstSeqs[n].mlBase = (U16)(inSeqs[n].matchLength - MINMATCH);

+ /* check for long length > 65535 */

+ if (UNLIKELY(inSeqs[n].matchLength > 65535+MINMATCH)) {

+ assert(longLen == 0);

+ longLen = n + 1;

+ }

+ if (UNLIKELY(inSeqs[n].litLength > 65535)) {

+ assert(longLen == 0);

+ longLen = n + nbSequences + 1;

+ }

+ }

+ return longLen;

+}

+

+#endif

+

+/*

+ * Precondition: Sequences must end on an explicit Block Delimiter

+ * @return: 0 on success, or an error code.

+ * Note: Sequence validation functionality has been disabled (removed).

+ * This is helpful to generate a lean main pipeline, improving performance.

+ * It may be re-inserted later.

+ */

+size_t ZSTD_convertBlockSequences(ZSTD_CCtx* cctx,

+ const ZSTD_Sequence* const inSeqs, size_t nbSequences,

+ int repcodeResolution)

+{

+ Repcodes_t updatedRepcodes;

+ size_t seqNb = 0;

+

+ DEBUGLOG(5, "ZSTD_convertBlockSequences (nbSequences = %zu)", nbSequences);

+

+ RETURN_ERROR_IF(nbSequences >= cctx->seqStore.maxNbSeq, externalSequences_invalid,

+ "Not enough memory allocated. Try adjusting ZSTD_c_minMatch.");

+

+ ZSTD_memcpy(updatedRepcodes.rep, cctx->blockState.prevCBlock->rep, sizeof(Repcodes_t));

+

+ /* check end condition */

+ assert(nbSequences >= 1);

+ assert(inSeqs[nbSequences-1].matchLength == 0);

+ assert(inSeqs[nbSequences-1].offset == 0);

+

+ /* Convert Sequences from public format to internal format */

+ if (!repcodeResolution) {

+ size_t const longl = convertSequences_noRepcodes(cctx->seqStore.sequencesStart, inSeqs, nbSequences-1);

+ cctx->seqStore.sequences = cctx->seqStore.sequencesStart + nbSequences-1;

+ if (longl) {

+ DEBUGLOG(5, "long length");

+ assert(cctx->seqStore.longLengthType == ZSTD_llt_none);

+ if (longl <= nbSequences-1) {

+ DEBUGLOG(5, "long match length detected at pos %zu", longl-1);

+ cctx->seqStore.longLengthType = ZSTD_llt_matchLength;

+ cctx->seqStore.longLengthPos = (U32)(longl-1);

+ } else {

+ DEBUGLOG(5, "long literals length detected at pos %zu", longl-nbSequences);

+ assert(longl <= 2* (nbSequences-1));

+ cctx->seqStore.longLengthType = ZSTD_llt_literalLength;

+ cctx->seqStore.longLengthPos = (U32)(longl-(nbSequences-1)-1);

+ }

+ }

+ } else {

+ for (seqNb = 0; seqNb < nbSequences - 1 ; seqNb++) {

+ U32 const litLength = inSeqs[seqNb].litLength;

+ U32 const matchLength = inSeqs[seqNb].matchLength;

+ U32 const ll0 = (litLength == 0);

+ U32 const offBase = ZSTD_finalizeOffBase(inSeqs[seqNb].offset, updatedRepcodes.rep, ll0);

+

+ DEBUGLOG(6, "Storing sequence: (of: %u, ml: %u, ll: %u)", offBase, matchLength, litLength);

+ ZSTD_storeSeqOnly(&cctx->seqStore, litLength, offBase, matchLength);

+ ZSTD_updateRep(updatedRepcodes.rep, offBase, ll0);

+ }

+ }

+

+ /* If we skipped repcode search while parsing, we need to update repcodes now */

+ if (!repcodeResolution && nbSequences > 1) {

+ U32* const rep = updatedRepcodes.rep;

+

+ if (nbSequences >= 4) {

+ U32 lastSeqIdx = (U32)nbSequences - 2; /* index of last full sequence */

+ rep[2] = inSeqs[lastSeqIdx - 2].offset;

+ rep[1] = inSeqs[lastSeqIdx - 1].offset;

+ rep[0] = inSeqs[lastSeqIdx].offset;

+ } else if (nbSequences == 3) {

+ rep[2] = rep[0];

+ rep[1] = inSeqs[0].offset;

+ rep[0] = inSeqs[1].offset;

+ } else {

+ assert(nbSequences == 2);

+ rep[2] = rep[1];

+ rep[1] = rep[0];

+ rep[0] = inSeqs[0].offset;

+ }

+ }

+

+ ZSTD_memcpy(cctx->blockState.nextCBlock->rep, updatedRepcodes.rep, sizeof(Repcodes_t));

+

+ return 0;

+}

+

+#if defined(ZSTD_ARCH_X86_AVX2)

+

+BlockSummary ZSTD_get1BlockSummary(const ZSTD_Sequence* seqs, size_t nbSeqs)

+{

+ size_t i;

+ __m256i const zeroVec = _mm256_setzero_si256();

+ __m256i sumVec = zeroVec; /* accumulates match+lit in 32-bit lanes */

+ ZSTD_ALIGNED(32) U32 tmp[8]; /* temporary buffer for reduction */

+ size_t mSum = 0, lSum = 0;

+ ZSTD_STATIC_ASSERT(sizeof(ZSTD_Sequence) == 16);

+

+ /* Process 2 structs (32 bytes) at a time */

+ for (i = 0; i + 2 <= nbSeqs; i += 2) {

+ /* Load two consecutive ZSTD_Sequence (8×4 = 32 bytes) */

+ __m256i data = _mm256_loadu_si256((const __m256i*)(const void*)&seqs[i]);

+ /* check end of block signal */

+ __m256i cmp = _mm256_cmpeq_epi32(data, zeroVec);

+ int cmp_res = _mm256_movemask_epi8(cmp);

+ /* indices for match lengths correspond to bits [8..11], [24..27]

+ * => combined mask = 0x0F000F00 */

+ ZSTD_STATIC_ASSERT(offsetof(ZSTD_Sequence, matchLength) == 8);

+ if (cmp_res & 0x0F000F00) break;

+ /* Accumulate in sumVec */

+ sumVec = _mm256_add_epi32(sumVec, data);

+ }

+

+ /* Horizontal reduction */

+ _mm256_store_si256((__m256i*)tmp, sumVec);

+ lSum = tmp[1] + tmp[5];

+ mSum = tmp[2] + tmp[6];

+

+ /* Handle the leftover */

+ for (; i < nbSeqs; i++) {

+ lSum += seqs[i].litLength;

+ mSum += seqs[i].matchLength;

+ if (seqs[i].matchLength == 0) break; /* end of block */

+ }

+

+ if (i==nbSeqs) {

+ /* reaching end of sequences: end of block signal was not present */

+ BlockSummary bs;

+ bs.nbSequences = ERROR(externalSequences_invalid);

+ return bs;

+ }

+ { BlockSummary bs;

+ bs.nbSequences = i+1;

+ bs.blockSize = lSum + mSum;

+ bs.litSize = lSum;

+ return bs;

+ }

+}

+

+#else

+

+BlockSummary ZSTD_get1BlockSummary(const ZSTD_Sequence* seqs, size_t nbSeqs)

+{

+ size_t totalMatchSize = 0;

+ size_t litSize = 0;

+ size_t n;

+ assert(seqs);

+ for (n=0; n<nbSeqs; n++) {

+ totalMatchSize += seqs[n].matchLength;

+ litSize += seqs[n].litLength;

+ if (seqs[n].matchLength == 0) {

+ assert(seqs[n].offset == 0);

+ break;

+ }

+ }

+ if (n==nbSeqs) {

+ BlockSummary bs;

+ bs.nbSequences = ERROR(externalSequences_invalid);

+ return bs;

+ }

+ { BlockSummary bs;

+ bs.nbSequences = n+1;

+ bs.blockSize = litSize + totalMatchSize;

+ bs.litSize = litSize;

+ return bs;

+ }

+}

+#endif

+

+

+static size_t

+ZSTD_compressSequencesAndLiterals_internal(ZSTD_CCtx* cctx,

+ void* dst, size_t dstCapacity,

+ const ZSTD_Sequence* inSeqs, size_t nbSequences,

+ const void* literals, size_t litSize, size_t srcSize)

+{

+ size_t remaining = srcSize;

+ size_t cSize = 0;

+ BYTE* op = (BYTE*)dst;

+ int const repcodeResolution = (cctx->appliedParams.searchForExternalRepcodes == ZSTD_ps_enable);

+ assert(cctx->appliedParams.searchForExternalRepcodes != ZSTD_ps_auto);

+

+ DEBUGLOG(4, "ZSTD_compressSequencesAndLiterals_internal: nbSeqs=%zu, litSize=%zu", nbSequences, litSize);

+ RETURN_ERROR_IF(nbSequences == 0, externalSequences_invalid, "Requires at least 1 end-of-block");

+

+ /* Special case: empty frame */

+ if ((nbSequences == 1) && (inSeqs[0].litLength == 0)) {

+ U32 const cBlockHeader24 = 1 /* last block */ + (((U32)bt_raw)<<1);

+ RETURN_ERROR_IF(dstCapacity<3, dstSize_tooSmall, "No room for empty frame block header");

+ MEM_writeLE24(op, cBlockHeader24);

+ op += ZSTD_blockHeaderSize;

+ dstCapacity -= ZSTD_blockHeaderSize;

+ cSize += ZSTD_blockHeaderSize;

+ }

+

+ while (nbSequences) {

+ size_t compressedSeqsSize, cBlockSize, conversionStatus;

+ BlockSummary const block = ZSTD_get1BlockSummary(inSeqs, nbSequences);

+ U32 const lastBlock = (block.nbSequences == nbSequences);

+ FORWARD_IF_ERROR(block.nbSequences, "Error while trying to determine nb of sequences for a block");

+ assert(block.nbSequences <= nbSequences);

+ RETURN_ERROR_IF(block.litSize > litSize, externalSequences_invalid, "discrepancy: Sequences require more literals than present in buffer");

+ ZSTD_resetSeqStore(&cctx->seqStore);

+

+ conversionStatus = ZSTD_convertBlockSequences(cctx,

+ inSeqs, block.nbSequences,

+ repcodeResolution);

+ FORWARD_IF_ERROR(conversionStatus, "Bad sequence conversion");

+ inSeqs += block.nbSequences;

+ nbSequences -= block.nbSequences;

+ remaining -= block.blockSize;

+

+ /* Note: when blockSize is very small, other variant send it uncompressed.

+ * Here, we still send the sequences, because we don't have the original source to send it uncompressed.

+ * One could imagine in theory reproducing the source from the sequences,

+ * but that's complex and costly memory intensive, and goes against the objectives of this variant. */

+

+ RETURN_ERROR_IF(dstCapacity < ZSTD_blockHeaderSize, dstSize_tooSmall, "not enough dstCapacity to write a new compressed block");

+

+ compressedSeqsSize = ZSTD_entropyCompressSeqStore_internal(

+ op + ZSTD_blockHeaderSize /* Leave space for block header */, dstCapacity - ZSTD_blockHeaderSize,

+ literals, block.litSize,

+ &cctx->seqStore,

+ &cctx->blockState.prevCBlock->entropy, &cctx->blockState.nextCBlock->entropy,

+ &cctx->appliedParams,

+ cctx->tmpWorkspace, cctx->tmpWkspSize /* statically allocated in resetCCtx */,

+ cctx->bmi2);

+ FORWARD_IF_ERROR(compressedSeqsSize, "Compressing sequences of block failed");

+ /* note: the spec forbids for any compressed block to be larger than maximum block size */

+ if (compressedSeqsSize > cctx->blockSizeMax) compressedSeqsSize = 0;

+ DEBUGLOG(5, "Compressed sequences size: %zu", compressedSeqsSize);

+ litSize -= block.litSize;

+ literals = (const char*)literals + block.litSize;

+

+ /* Note: difficult to check source for RLE block when only Literals are provided,

+ * but it could be considered from analyzing the sequence directly */

+

+ if (compressedSeqsSize == 0) {

+ /* Sending uncompressed blocks is out of reach, because the source is not provided.

+ * In theory, one could use the sequences to regenerate the source, like a decompressor,

+ * but it's complex, and memory hungry, killing the purpose of this variant.

+ * Current outcome: generate an error code.

+ */

+ RETURN_ERROR(cannotProduce_uncompressedBlock, "ZSTD_compressSequencesAndLiterals cannot generate an uncompressed block");

+ } else {

+ U32 cBlockHeader;

+ assert(compressedSeqsSize > 1); /* no RLE */

+ /* Error checking and repcodes update */

+ ZSTD_blockState_confirmRepcodesAndEntropyTables(&cctx->blockState);

+ if (cctx->blockState.prevCBlock->entropy.fse.offcode_repeatMode == FSE_repeat_valid)

+ cctx->blockState.prevCBlock->entropy.fse.offcode_repeatMode = FSE_repeat_check;

+

+ /* Write block header into beginning of block*/

+ cBlockHeader = lastBlock + (((U32)bt_compressed)<<1) + (U32)(compressedSeqsSize << 3);

+ MEM_writeLE24(op, cBlockHeader);

+ cBlockSize = ZSTD_blockHeaderSize + compressedSeqsSize;

+ DEBUGLOG(5, "Writing out compressed block, size: %zu", cBlockSize);

+ }

+

+ cSize += cBlockSize;

+ op += cBlockSize;

+ dstCapacity -= cBlockSize;

+ cctx->isFirstBlock = 0;

+ DEBUGLOG(5, "cSize running total: %zu (remaining dstCapacity=%zu)", cSize, dstCapacity);

+

+ if (lastBlock) {

+ assert(nbSequences == 0);

+ break;

+ }

+ }

+

+ RETURN_ERROR_IF(litSize != 0, externalSequences_invalid, "literals must be entirely and exactly consumed");

+ RETURN_ERROR_IF(remaining != 0, externalSequences_invalid, "Sequences must represent a total of exactly srcSize=%zu", srcSize);

+ DEBUGLOG(4, "cSize final total: %zu", cSize);

+ return cSize;

+}

+

+size_t

+ZSTD_compressSequencesAndLiterals(ZSTD_CCtx* cctx,

+ void* dst, size_t dstCapacity,

+ const ZSTD_Sequence* inSeqs, size_t inSeqsSize,

+ const void* literals, size_t litSize, size_t litCapacity,

+ size_t decompressedSize)

+{

+ BYTE* op = (BYTE*)dst;

+ size_t cSize = 0;

+

+ /* Transparent initialization stage, same as compressStream2() */

+ DEBUGLOG(4, "ZSTD_compressSequencesAndLiterals (dstCapacity=%zu)", dstCapacity);

+ assert(cctx != NULL);

+ if (litCapacity < litSize) {

+ RETURN_ERROR(workSpace_tooSmall, "literals buffer is not large enough: must be at least 8 bytes larger than litSize (risk of read out-of-bound)");

+ }

+ FORWARD_IF_ERROR(ZSTD_CCtx_init_compressStream2(cctx, ZSTD_e_end, decompressedSize), "CCtx initialization failed");

+

+ if (cctx->appliedParams.blockDelimiters == ZSTD_sf_noBlockDelimiters) {

+ RETURN_ERROR(frameParameter_unsupported, "This mode is only compatible with explicit delimiters");

+ }

+ if (cctx->appliedParams.validateSequences) {

+ RETURN_ERROR(parameter_unsupported, "This mode is not compatible with Sequence validation");

+ }

+ if (cctx->appliedParams.fParams.checksumFlag) {

+ RETURN_ERROR(frameParameter_unsupported, "this mode is not compatible with frame checksum");

+ }

+

+ /* Begin writing output, starting with frame header */

+ { size_t const frameHeaderSize = ZSTD_writeFrameHeader(op, dstCapacity,

+ &cctx->appliedParams, decompressedSize, cctx->dictID);

+ op += frameHeaderSize;

+ assert(frameHeaderSize <= dstCapacity);

+ dstCapacity -= frameHeaderSize;

+ cSize += frameHeaderSize;

+ }

+

+ /* Now generate compressed blocks */

+ { size_t const cBlocksSize = ZSTD_compressSequencesAndLiterals_internal(cctx,

+ op, dstCapacity,

+ inSeqs, inSeqsSize,

+ literals, litSize, decompressedSize);

+ FORWARD_IF_ERROR(cBlocksSize, "Compressing blocks failed!");

+ cSize += cBlocksSize;

+ assert(cBlocksSize <= dstCapacity);

+ dstCapacity -= cBlocksSize;

+ }

+

+ DEBUGLOG(4, "Final compressed size: %zu", cSize);

+static ZSTD_inBuffer inBuffer_forEndFlush(const ZSTD_CStream* zcs)

+{

+ const ZSTD_inBuffer nullInput = { NULL, 0, 0 };

+ const int stableInput = (zcs->appliedParams.inBufferMode == ZSTD_bm_stable);

+ return stableInput ? zcs->expectedInBuffer : nullInput;

+}

+

+ ZSTD_inBuffer input = inBuffer_forEndFlush(zcs);

+ input.size = input.pos; /* do not ingest more input during flush */

+ ZSTD_inBuffer input = inBuffer_forEndFlush(zcs);

+ FORWARD_IF_ERROR(remainingToFlush , "ZSTD_compressStream2(,,ZSTD_e_end) failed");

+static U64 ZSTD_getCParamRowSize(U64 srcSizeHint, size_t dictSize, ZSTD_CParamMode_e mode)

+ * Note: `mode` controls how we treat the `dictSize`. See docs for `ZSTD_CParamMode_e`. */

+static ZSTD_compressionParameters ZSTD_getCParams_internal(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize, ZSTD_CParamMode_e mode)

+ return ZSTD_adjustCParams_internal(cp, srcSizeHint, dictSize, mode, ZSTD_ps_auto);

+static ZSTD_parameters

+ZSTD_getParams_internal(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize, ZSTD_CParamMode_e mode)

+{

+ZSTD_parameters ZSTD_getParams(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize)

+{

+

+void ZSTD_registerSequenceProducer(

+ ZSTD_CCtx* zc,

+ void* extSeqProdState,

+ ZSTD_sequenceProducer_F extSeqProdFunc)

+{

+ assert(zc != NULL);

+ ZSTD_CCtxParams_registerSequenceProducer(

+ &zc->requestedParams, extSeqProdState, extSeqProdFunc

+ );

+}

+

+void ZSTD_CCtxParams_registerSequenceProducer(

+ ZSTD_CCtx_params* params,

+ void* extSeqProdState,

+ ZSTD_sequenceProducer_F extSeqProdFunc)

+{

+ assert(params != NULL);

+ if (extSeqProdFunc != NULL) {

+ params->extSeqProdFunc = extSeqProdFunc;

+ params->extSeqProdState = extSeqProdState;

+ } else {

+ params->extSeqProdFunc = NULL;

+ params->extSeqProdState = NULL;

+ }

+}