Lines Matching +full:dynamic +full:- +full:range +full:- +full:compressor
1 /* SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause */
6 * This source code is licensed under both the BSD-style license (found in the
9 * You may select, at your option, one of the above-listed licenses.
19 /*-*************************************
27 /*-*************************************
41 /*-*************************************
86 U16 mlBase; /* mlBase == matchLength - MINMATCH */
127 seqLen.litLength = seq->litLength; in ZSTD_getSequenceLength()
128 seqLen.matchLength = seq->mlBase + MINMATCH; in ZSTD_getSequenceLength()
129 if (seqStore->longLengthPos == (U32)(seq - seqStore->sequencesStart)) { in ZSTD_getSequenceLength()
130 if (seqStore->longLengthType == ZSTD_llt_literalLength) { in ZSTD_getSequenceLength()
133 if (seqStore->longLengthType == ZSTD_llt_matchLength) { in ZSTD_getSequenceLength()
148 * Stores Literals Block Type for a super-block in hType, and
159 * Stores symbol compression modes for a super-block in {ll, ol, ml}Type, and
226 /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */
242 …ZSTD_OptPrice_e priceType; /* prices can be determined dynamically, or follow a pre-defined cost…
243 const ZSTD_entropyCTables_t* symbolCosts; /* pre-calculated dictionary statistics */
268 #define ZSTD_ROW_HASH_CACHE_SIZE 8 /* Size of prefetching hash cache for row-based matchfinde…
282 …U32 rowHashLog; /* For row-based matchfinder: Hashlog based on nb of rows…
283 …BYTE* tagTable; /* For row-based matchFinder: A row-based table containin…
284 …U32 hashCache[ZSTD_ROW_HASH_CACHE_SIZE]; /* For row-based matchFinder: a cache of hashes to improv…
285 …U64 hashSalt; /* For row-based matchFinder: salts the hash for reuse of…
286 …U32 hashSaltEntropy; /* For row-based matchFinder: collects entropy for salt g…
292 …int forceNonContiguous; /* Non-zero if we should force non-contiguous load for the next window upd…
366 int forceWindow; /* force back-references to respect limit of
403 * Valid @preBlockSplitter_level values range from 0 to 6 (included).
414 /* Param for deciding whether to use row-based matchfinder */
417 /* Always load a dictionary in ext-dict mode (not prefix mode)? */
445 * Indicates whether this compression proceeds directly from user-provided
446 * source buffer to user-provided destination buffer (ZSTDb_not_buffered), or
476 …pleApiParams; /* Param storage used by the simple API - not sticky. Must only be used in top-le…
480 ZSTD_cwksp workspace; /* manages buffer for dynamic allocations */
499 void* tmpWorkspace; /* used as substitute of stack space - must be aligned for S64 type */
526 ZSTD_prefixDict prefixDict; /* single-usage dictionary */
528 /* Multi-threading */
591 * note : mlBase = matchLength - MINMATCH;
592 * because it's the format it's stored in seqStore->sequences */
671 U32 const minlog = (strat>=ZSTD_btultra) ? (U32)(strat) - 1 : 6; in ZSTD_minGain()
679 switch (cctxParams->literalCompressionMode) { in ZSTD_literalsCompressionIsDisabled()
685 assert(0 /* impossible: pre-validated */); in ZSTD_literalsCompressionIsDisabled()
688 … return (cctxParams->cParams.strategy == ZSTD_fast) && (cctxParams->cParams.targetLength > 0); in ZSTD_literalsCompressionIsDisabled()
702 ZSTD_wildcopy(op, ip, ilimit_w - ip, ZSTD_no_overlap); in ZSTD_safecopyLiterals()
703 op += ilimit_w - ip; in ZSTD_safecopyLiterals()
717 #define OFFBASE_TO_OFFSET(o) (assert(OFFBASE_IS_OFFSET(o)), (o) - ZSTD_REP_NUM)
732 assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq); in ZSTD_storeSeqOnly()
737 … assert(seqStorePtr->longLengthType == ZSTD_llt_none); /* there can only be a single long length */ in ZSTD_storeSeqOnly()
738 seqStorePtr->longLengthType = ZSTD_llt_literalLength; in ZSTD_storeSeqOnly()
739 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); in ZSTD_storeSeqOnly()
741 seqStorePtr->sequences[0].litLength = (U16)litLength; in ZSTD_storeSeqOnly()
744 seqStorePtr->sequences[0].offBase = offBase; in ZSTD_storeSeqOnly()
749 { size_t const mlBase = matchLength - MINMATCH; in ZSTD_storeSeqOnly()
751 … assert(seqStorePtr->longLengthType == ZSTD_llt_none); /* there can only be a single long length */ in ZSTD_storeSeqOnly()
752 seqStorePtr->longLengthType = ZSTD_llt_matchLength; in ZSTD_storeSeqOnly()
753 … seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); in ZSTD_storeSeqOnly()
755 seqStorePtr->sequences[0].mlBase = (U16)mlBase; in ZSTD_storeSeqOnly()
758 seqStorePtr->sequences++; in ZSTD_storeSeqOnly()
765 * Allowed to over-read literals up to litLimit.
773 BYTE const* const litLimit_w = litLimit - WILDCOPY_OVERLENGTH; in ZSTD_storeSeq()
778 { U32 const pos = (U32)((const BYTE*)literals - g_start); in ZSTD_storeSeq()
783 assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq); in ZSTD_storeSeq()
785 assert(seqStorePtr->maxNbLit <= 128 KB); in ZSTD_storeSeq()
786 assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit); in ZSTD_storeSeq()
793 ZSTD_copy16(seqStorePtr->lit, literals); in ZSTD_storeSeq()
795 … ZSTD_wildcopy(seqStorePtr->lit+16, literals+16, (ptrdiff_t)litLength-16, ZSTD_no_overlap); in ZSTD_storeSeq()
798 ZSTD_safecopyLiterals(seqStorePtr->lit, literals, litEnd, litLimit_w); in ZSTD_storeSeq()
800 seqStorePtr->lit += litLength; in ZSTD_storeSeq()
806 * updates in-place @rep (array of repeat offsets)
807 * @offBase : sum-type, using numeric representation of ZSTD_storeSeq()
817 U32 const repCode = OFFBASE_TO_REPCODE(offBase) - 1 + ll0; in ZSTD_updateRep()
819 U32 const currentOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode]; in ZSTD_updateRep()
843 /*-*************************************
849 const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1); in ZSTD_count()
859 return (size_t)(pIn - pStart); in ZSTD_count()
861 …if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatc… in ZSTD_count()
862 if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; } in ZSTD_count()
864 return (size_t)(pIn - pStart); in ZSTD_count()
875 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd); in ZSTD_count_2segments()
878 DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength); in ZSTD_count_2segments()
879 DEBUGLOG(7, "distance from match beginning to end dictionary = %i", (int)(mEnd - match)); in ZSTD_count_2segments()
880 DEBUGLOG(7, "distance from current pos to end buffer = %i", (int)(iEnd - ip)); in ZSTD_count_2segments()
887 /*-*************************************
891 …(U32 u, U32 h, U32 s) { assert(h <= 32); return (((u << (32-24)) * prime3bytes) ^ s) >> (32-h) ; } in ZSTD_hash3()
896 … ZSTD_hash4(U32 u, U32 h, U32 s) { assert(h <= 32); return ((u * prime4bytes) ^ s) >> (32-h) ; } in ZSTD_hash4()
901 …32 h, U64 s) { assert(h <= 64); return (size_t)((((u << (64-40)) * prime5bytes) ^ s) >> (64-h)) ;… in ZSTD_hash5()
906 …32 h, U64 s) { assert(h <= 64); return (size_t)((((u << (64-48)) * prime6bytes) ^ s) >> (64-h)) ;… in ZSTD_hash6()
911 …32 h, U64 s) { assert(h <= 64); return (size_t)((((u << (64-56)) * prime7bytes) ^ s) >> (64-h)) ;… in ZSTD_hash7()
916 …8(U64 u, U32 h, U64 s) { assert(h <= 64); return (size_t)((((u) * prime8bytes) ^ s) >> (64-h)) ; } in ZSTD_hash8()
1001 return ZSTD_ipow(prime8bytes, length - 1); in ZSTD_rollingHash_primePower()
1009 hash -= (toRemove + ZSTD_ROLL_HASH_CHAR_OFFSET) * primePower; in ZSTD_rollingHash_rotate()
1015 /*-*************************************
1019 * In 32-bit mode: we want to avoid crossing the 2 GB limit,
1021 * In 64-bit mode: we want to ensure that adding the maximum job size (512 MB)
1026 ( ((U32)-1) /* Maximum ending current index */ \
1027 - ZSTD_CURRENT_MAX) /* Maximum beginning lowLimit */
1035 size_t const endT = (size_t)(window->nextSrc - window->base); in ZSTD_window_clear()
1038 window->lowLimit = end; in ZSTD_window_clear()
1039 window->dictLimit = end; in ZSTD_window_clear()
1046 (window.nextSrc - window.base) == ZSTD_WINDOW_START_INDEX; in ZSTD_window_isEmpty()
1051 * Returns non-zero if the window has a non-empty extDict.
1061 * passed to the compressor.
1065 return ZSTD_window_hasExtDict(ms->window) ? in ZSTD_matchState_dictMode()
1067 ms->dictMatchState != NULL ? in ZSTD_matchState_dictMode()
1068 … (ms->dictMatchState->dedicatedDictSearch ? ZSTD_dedicatedDictSearch : ZSTD_dictMatchState) : in ZSTD_matchState_dictMode()
1072 /* Defining this macro to non-zero tells zstd to run the overflow correction
1086 * Returns non-zero if the indices are large enough for overflow correction
1096 U32 const curr = (U32)((BYTE const*)src - window.base); in ZSTD_window_canOverflowCorrect()
1121 * Returns non-zero if the indices are getting too large and need overflow
1131 U32 const curr = (U32)((BYTE const*)srcEnd - window.base); in ZSTD_window_needOverflowCorrection()
1159 * current - newCurrent in ZSTD_window_correctOverflow()
1160 * > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog) in ZSTD_window_correctOverflow()
1161 * > (3<<29) - (1<<chainLog) in ZSTD_window_correctOverflow()
1162 * > (3<<29) - (1<<30) (NOTE: chainLog <= 30) in ZSTD_window_correctOverflow()
1165 * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow: in ZSTD_window_correctOverflow()
1167 * In 64-bit mode we are safe, because we have 64-bit ptrdiff_t. in ZSTD_window_correctOverflow()
1168 * In 32-bit mode we are safe, because (chainLog <= 29), so in ZSTD_window_correctOverflow()
1169 * ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32. in ZSTD_window_correctOverflow()
1170 * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32: in ZSTD_window_correctOverflow()
1174 U32 const cycleMask = cycleSize - 1; in ZSTD_window_correctOverflow()
1175 U32 const curr = (U32)((BYTE const*)src - window->base); in ZSTD_window_correctOverflow()
1177 /* Ensure newCurrent - maxDist >= ZSTD_WINDOW_START_INDEX. */ in ZSTD_window_correctOverflow()
1184 U32 const correction = curr - newCurrent; in ZSTD_window_correctOverflow()
1189 assert((maxDist & (maxDist - 1)) == 0); in ZSTD_window_correctOverflow()
1197 window->base += correction; in ZSTD_window_correctOverflow()
1198 window->dictBase += correction; in ZSTD_window_correctOverflow()
1199 if (window->lowLimit < correction + ZSTD_WINDOW_START_INDEX) { in ZSTD_window_correctOverflow()
1200 window->lowLimit = ZSTD_WINDOW_START_INDEX; in ZSTD_window_correctOverflow()
1202 window->lowLimit -= correction; in ZSTD_window_correctOverflow()
1204 if (window->dictLimit < correction + ZSTD_WINDOW_START_INDEX) { in ZSTD_window_correctOverflow()
1205 window->dictLimit = ZSTD_WINDOW_START_INDEX; in ZSTD_window_correctOverflow()
1207 window->dictLimit -= correction; in ZSTD_window_correctOverflow()
1212 assert(newCurrent - maxDist >= ZSTD_WINDOW_START_INDEX); in ZSTD_window_correctOverflow()
1214 assert(window->lowLimit <= newCurrent); in ZSTD_window_correctOverflow()
1215 assert(window->dictLimit <= newCurrent); in ZSTD_window_correctOverflow()
1217 ++window->nbOverflowCorrections; in ZSTD_window_correctOverflow()
1220 window->lowLimit); in ZSTD_window_correctOverflow()
1227 * (srcEnd - base) - lowLimit == maxDist + loadedDictEnd
1254 U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base); in ZSTD_window_enforceMaxDist()
1259 /* - When there is no dictionary : loadedDictEnd == 0. in ZSTD_window_enforceMaxDist()
1261 overflowing next operation `newLowLimit = blockEndIdx - maxDist`. in ZSTD_window_enforceMaxDist()
1262 - When there is a standard dictionary : in ZSTD_window_enforceMaxDist()
1268 - When there is an attached dictionary : in ZSTD_window_enforceMaxDist()
1273 U32 const newLowLimit = blockEndIdx - maxDist; in ZSTD_window_enforceMaxDist()
1274 if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit; in ZSTD_window_enforceMaxDist()
1275 if (window->dictLimit < window->lowLimit) { in ZSTD_window_enforceMaxDist()
1277 (unsigned)window->dictLimit, (unsigned)window->lowLimit); in ZSTD_window_enforceMaxDist()
1278 window->dictLimit = window->lowLimit; in ZSTD_window_enforceMaxDist()
1290 * loadedDictEnd uses same referential as window->base
1301 { U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base); in ZSTD_checkDictValidity()
1307 if (blockEndIdx > loadedDictEnd + maxDist || loadedDictEnd != window->dictLimit) { in ZSTD_checkDictValidity()
1313 * non-contiguous segments, which means that loadedDictEnd != window->dictLimit. in ZSTD_checkDictValidity()
1328 window->base = (BYTE const*)" "; in ZSTD_window_init()
1329 window->dictBase = (BYTE const*)" "; in ZSTD_window_init()
1331 … window->dictLimit = ZSTD_WINDOW_START_INDEX; /* start from >0, so that 1st position is valid */ in ZSTD_window_init()
1332 …window->lowLimit = ZSTD_WINDOW_START_INDEX; /* it ensures first and later CCtx usages compress… in ZSTD_window_init()
1333 window->nextSrc = window->base + ZSTD_WINDOW_START_INDEX; /* see issue #1241 */ in ZSTD_window_init()
1334 window->nbOverflowCorrections = 0; in ZSTD_window_init()
1342 * Returns non-zero if the segment is contiguous.
1355 assert(window->base != NULL); in ZSTD_window_update()
1356 assert(window->dictBase != NULL); in ZSTD_window_update()
1358 if (src != window->nextSrc || forceNonContiguous) { in ZSTD_window_update()
1360 size_t const distanceFromBase = (size_t)(window->nextSrc - window->base); in ZSTD_window_update()
1361 DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit); in ZSTD_window_update()
1362 window->lowLimit = window->dictLimit; in ZSTD_window_update()
1364 window->dictLimit = (U32)distanceFromBase; in ZSTD_window_update()
1365 window->dictBase = window->base; in ZSTD_window_update()
1366 window->base = ip - distanceFromBase; in ZSTD_window_update()
1367 /* ms->nextToUpdate = window->dictLimit; */ in ZSTD_window_update()
1368 …if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit; … in ZSTD_window_update()
1371 window->nextSrc = ip + srcSize; in ZSTD_window_update()
1373 if ( (ip+srcSize > window->dictBase + window->lowLimit) in ZSTD_window_update()
1374 & (ip < window->dictBase + window->dictLimit)) { in ZSTD_window_update()
1375 size_t const highInputIdx = (size_t)((ip + srcSize) - window->dictBase); in ZSTD_window_update()
1376 …U32 const lowLimitMax = (highInputIdx > (size_t)window->dictLimit) ? window->dictLimit : (U32)high… in ZSTD_window_update()
1378 window->lowLimit = lowLimitMax; in ZSTD_window_update()
1379 DEBUGLOG(5, "Overlapping extDict and input : new lowLimit = %u", window->lowLimit); in ZSTD_window_update()
1385 * Returns the lowest allowed match index. It may either be in the ext-dict or the prefix.
1390 U32 const lowestValid = ms->window.lowLimit; in ZSTD_getLowestMatchIndex()
1391 U32 const withinWindow = (curr - lowestValid > maxDistance) ? curr - maxDistance : lowestValid; in ZSTD_getLowestMatchIndex()
1392 U32 const isDictionary = (ms->loadedDictEnd != 0); in ZSTD_getLowestMatchIndex()
1407 U32 const lowestValid = ms->window.dictLimit; in ZSTD_getLowestPrefixIndex()
1408 … U32 const withinWindow = (curr - lowestValid > maxDistance) ? curr - maxDistance : lowestValid; in ZSTD_getLowestPrefixIndex()
1409 U32 const isDictionary = (ms->loadedDictEnd != 0); in ZSTD_getLowestPrefixIndex()
1422 return ((U32)((prefixLowestIndex-1) - repIndex) >= 3); in ZSTD_index_overlap_check()
1451 u, table[u], ZSTD_fWeight(sum) - ZSTD_fWeight(table[u]) ); in ZSTD_debugTable()
1467 * 1. Compute (hash, currentTag) at ip. currentTag is an 8-bit independent hash at ip.
1475 #define ZSTD_SHORT_CACHE_TAG_MASK ((1u << ZSTD_SHORT_CACHE_TAG_BITS) - 1)
1482 assert(index >> (32 - ZSTD_SHORT_CACHE_TAG_BITS) == 0); in ZSTD_writeTaggedIndex()
1577 * output an empty Block with end-of-frame mark to complete a frame
1587 * This cannot be used when long range matching is enabled.
1589 * compressor.
1590 * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory
1606 return params->extSeqProdFunc != NULL; in ZSTD_hasExtSeqProd()