Lines Matching +full:dynamic +full:- +full:range +full:- +full:compressor
5 * This source code is licensed under both the BSD-style license (found in the
8 * You may select, at your option, one of the above-listed licenses.
18 /*-*************************************
25 /*-*************************************
35 … benefit is that ZSTD_DUBT_UNSORTED_MARK cannot be mishandled after table re-use with a different …
39 /*-*************************************
82 * Stores Literals Block Type for a super-block in hType, and
93 * Stores symbol compression modes for a super-block in {ll, ol, ml}Type, and
158 /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */
174 …ZSTD_OptPrice_e priceType; /* prices can be determined dynamically, or follow a pre-defined cost…
175 const ZSTD_entropyCTables_t* symbolCosts; /* pre-calculated dictionary statistics */
200 #define ZSTD_ROW_HASH_CACHE_SIZE 8 /* Size of prefetching hash cache for row-based matchfinde…
214 …U32 rowHashLog; /* For row-based matchfinder: Hashlog based on nb of rows…
215 …U16* tagTable; /* For row-based matchFinder: A row-based table containin…
216 …U32 hashCache[ZSTD_ROW_HASH_CACHE_SIZE]; /* For row-based matchFinder: a cache of hashes to improv…
222 …U32 forceNonContiguous; /* Non-zero if we should force non-contiguous load for the next window upd…
284 int forceWindow; /* force back-references to respect limit of
319 /* Param for deciding whether to use row-based matchfinder */
322 /* Always load a dictionary in ext-dict mode (not prefix mode)? */
333 * Indicates whether this compression proceeds directly from user-provided
334 * source buffer to user-provided destination buffer (ZSTDb_not_buffered), or
364 …pleApiParams; /* Param storage used by the simple API - not sticky. Must only be used in top-le…
368 ZSTD_cwksp workspace; /* manages buffer for dynamic allocations */
412 ZSTD_prefixDict prefixDict; /* single-usage dictionary */
414 /* Multi-threading */
472 * note : mlBase = matchLength - MINMATCH;
473 * because it's the format it's stored in seqStore->sequences */
530 U32 const minlog = (strat>=ZSTD_btultra) ? (U32)(strat) - 1 : 6; in ZSTD_minGain()
538 switch (cctxParams->literalCompressionMode) { in ZSTD_literalsCompressionIsDisabled()
544 assert(0 /* impossible: pre-validated */); in ZSTD_literalsCompressionIsDisabled()
547 … return (cctxParams->cParams.strategy == ZSTD_fast) && (cctxParams->cParams.targetLength > 0); in ZSTD_literalsCompressionIsDisabled()
561 ZSTD_wildcopy(op, ip, ilimit_w - ip, ZSTD_no_overlap); in ZSTD_safecopyLiterals()
562 op += ilimit_w - ip; in ZSTD_safecopyLiterals()
568 #define ZSTD_REP_MOVE (ZSTD_REP_NUM-1)
572 #define STORE_REPCODE(r) (assert((r)>=1), assert((r)<=3), (r)-1)
576 #define STORED_OFFSET(o) (assert(STORED_IS_OFFSET(o)), (o)-ZSTD_REP_MOVE)
579 #define OFFBASE_TO_STORED(o) ((o)-1)
593 BYTE const* const litLimit_w = litLimit - WILDCOPY_OVERLENGTH; in ZSTD_storeSeq()
598 { U32 const pos = (U32)((const BYTE*)literals - g_start); in ZSTD_storeSeq()
603 assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq); in ZSTD_storeSeq()
605 assert(seqStorePtr->maxNbLit <= 128 KB); in ZSTD_storeSeq()
606 assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit); in ZSTD_storeSeq()
613 ZSTD_copy16(seqStorePtr->lit, literals); in ZSTD_storeSeq()
615 … ZSTD_wildcopy(seqStorePtr->lit+16, literals+16, (ptrdiff_t)litLength-16, ZSTD_no_overlap); in ZSTD_storeSeq()
618 ZSTD_safecopyLiterals(seqStorePtr->lit, literals, litEnd, litLimit_w); in ZSTD_storeSeq()
620 seqStorePtr->lit += litLength; in ZSTD_storeSeq()
624 … assert(seqStorePtr->longLengthType == ZSTD_llt_none); /* there can only be a single long length */ in ZSTD_storeSeq()
625 seqStorePtr->longLengthType = ZSTD_llt_literalLength; in ZSTD_storeSeq()
626 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); in ZSTD_storeSeq()
628 seqStorePtr->sequences[0].litLength = (U16)litLength; in ZSTD_storeSeq()
631 seqStorePtr->sequences[0].offBase = STORED_TO_OFFBASE(offBase_minus1); in ZSTD_storeSeq()
635 { size_t const mlBase = matchLength - MINMATCH; in ZSTD_storeSeq()
637 … assert(seqStorePtr->longLengthType == ZSTD_llt_none); /* there can only be a single long length */ in ZSTD_storeSeq()
638 seqStorePtr->longLengthType = ZSTD_llt_matchLength; in ZSTD_storeSeq()
639 … seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); in ZSTD_storeSeq()
641 seqStorePtr->sequences[0].mlBase = (U16)mlBase; in ZSTD_storeSeq()
644 seqStorePtr->sequences++; in ZSTD_storeSeq()
648 * updates in-place @rep (array of repeat offsets)
649 * @offBase_minus1 : sum-type, with same numeric representation as ZSTD_storeSeq()
659 U32 const repCode = STORED_REPCODE(offBase_minus1) - 1 + ll0; in ZSTD_updateRep()
661 U32 const currentOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode]; in ZSTD_updateRep()
685 /*-*************************************
703 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58]; in ZSTD_NbCommonBytes()
713 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; in ZSTD_NbCommonBytes()
722 …gned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */ in ZSTD_NbCommonBytes()
744 const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1); in ZSTD_count()
754 return (size_t)(pIn - pStart); in ZSTD_count()
756 …if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatc… in ZSTD_count()
757 if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; } in ZSTD_count()
759 return (size_t)(pIn - pStart); in ZSTD_count()
770 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd); in ZSTD_count_2segments()
773 DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength); in ZSTD_count_2segments()
774 DEBUGLOG(7, "distance from match beginning to end dictionary = %zi", mEnd - match); in ZSTD_count_2segments()
775 DEBUGLOG(7, "distance from current pos to end buffer = %zi", iEnd - ip); in ZSTD_count_2segments()
782 /*-*************************************
786 static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; } in ZSTD_hash3()
790 static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; } in ZSTD_hash4()
794 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h))… in ZSTD_hash5()
798 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h))… in ZSTD_hash6()
802 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h))… in ZSTD_hash7()
806 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; } in ZSTD_hash8()
867 return ZSTD_ipow(prime8bytes, length - 1); in ZSTD_rollingHash_primePower()
875 hash -= (toRemove + ZSTD_ROLL_HASH_CHAR_OFFSET) * primePower; in ZSTD_rollingHash_rotate()
881 /*-*************************************
891 ( ((U32)-1) /* Maximum ending current index */ \
892 - ZSTD_CURRENT_MAX) /* Maximum beginning lowLimit */
900 size_t const endT = (size_t)(window->nextSrc - window->base); in ZSTD_window_clear()
903 window->lowLimit = end; in ZSTD_window_clear()
904 window->dictLimit = end; in ZSTD_window_clear()
911 (window.nextSrc - window.base) == ZSTD_WINDOW_START_INDEX; in ZSTD_window_isEmpty()
916 * Returns non-zero if the window has a non-empty extDict.
926 * passed to the compressor.
930 return ZSTD_window_hasExtDict(ms->window) ? in ZSTD_matchState_dictMode()
932 ms->dictMatchState != NULL ? in ZSTD_matchState_dictMode()
933 … (ms->dictMatchState->dedicatedDictSearch ? ZSTD_dedicatedDictSearch : ZSTD_dictMatchState) : in ZSTD_matchState_dictMode()
937 /* Defining this macro to non-zero tells zstd to run the overflow correction
951 * Returns non-zero if the indices are large enough for overflow correction
961 U32 const curr = (U32)((BYTE const*)src - window.base); in ZSTD_window_canOverflowCorrect()
986 * Returns non-zero if the indices are getting too large and need overflow
996 U32 const curr = (U32)((BYTE const*)srcEnd - window.base); in ZSTD_window_needOverflowCorrection()
1022 * current - newCurrent in ZSTD_window_correctOverflow()
1023 * > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog) in ZSTD_window_correctOverflow()
1024 * > (3<<29) - (1<<chainLog) in ZSTD_window_correctOverflow()
1025 * > (3<<29) - (1<<30) (NOTE: chainLog <= 30) in ZSTD_window_correctOverflow()
1028 * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow: in ZSTD_window_correctOverflow()
1030 * In 64-bit mode we are safe, because we have 64-bit ptrdiff_t. in ZSTD_window_correctOverflow()
1031 * In 32-bit mode we are safe, because (chainLog <= 29), so in ZSTD_window_correctOverflow()
1032 * ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32. in ZSTD_window_correctOverflow()
1033 * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32: in ZSTD_window_correctOverflow()
1037 U32 const cycleMask = cycleSize - 1; in ZSTD_window_correctOverflow()
1038 U32 const curr = (U32)((BYTE const*)src - window->base); in ZSTD_window_correctOverflow()
1040 /* Ensure newCurrent - maxDist >= ZSTD_WINDOW_START_INDEX. */ in ZSTD_window_correctOverflow()
1047 U32 const correction = curr - newCurrent; in ZSTD_window_correctOverflow()
1052 assert((maxDist & (maxDist - 1)) == 0); in ZSTD_window_correctOverflow()
1060 window->base += correction; in ZSTD_window_correctOverflow()
1061 window->dictBase += correction; in ZSTD_window_correctOverflow()
1062 if (window->lowLimit < correction + ZSTD_WINDOW_START_INDEX) { in ZSTD_window_correctOverflow()
1063 window->lowLimit = ZSTD_WINDOW_START_INDEX; in ZSTD_window_correctOverflow()
1065 window->lowLimit -= correction; in ZSTD_window_correctOverflow()
1067 if (window->dictLimit < correction + ZSTD_WINDOW_START_INDEX) { in ZSTD_window_correctOverflow()
1068 window->dictLimit = ZSTD_WINDOW_START_INDEX; in ZSTD_window_correctOverflow()
1070 window->dictLimit -= correction; in ZSTD_window_correctOverflow()
1075 assert(newCurrent - maxDist >= ZSTD_WINDOW_START_INDEX); in ZSTD_window_correctOverflow()
1077 assert(window->lowLimit <= newCurrent); in ZSTD_window_correctOverflow()
1078 assert(window->dictLimit <= newCurrent); in ZSTD_window_correctOverflow()
1080 ++window->nbOverflowCorrections; in ZSTD_window_correctOverflow()
1083 window->lowLimit); in ZSTD_window_correctOverflow()
1090 * (srcEnd - base) - lowLimit == maxDist + loadedDictEnd
1117 U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base); in ZSTD_window_enforceMaxDist()
1122 /* - When there is no dictionary : loadedDictEnd == 0. in ZSTD_window_enforceMaxDist()
1124 overflowing next operation `newLowLimit = blockEndIdx - maxDist`. in ZSTD_window_enforceMaxDist()
1125 - When there is a standard dictionary : in ZSTD_window_enforceMaxDist()
1131 - When there is an attached dictionary : in ZSTD_window_enforceMaxDist()
1136 U32 const newLowLimit = blockEndIdx - maxDist; in ZSTD_window_enforceMaxDist()
1137 if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit; in ZSTD_window_enforceMaxDist()
1138 if (window->dictLimit < window->lowLimit) { in ZSTD_window_enforceMaxDist()
1140 (unsigned)window->dictLimit, (unsigned)window->lowLimit); in ZSTD_window_enforceMaxDist()
1141 window->dictLimit = window->lowLimit; in ZSTD_window_enforceMaxDist()
1153 * loadedDictEnd uses same referential as window->base
1164 { U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base); in ZSTD_checkDictValidity()
1186 window->base = (BYTE const*)" "; in ZSTD_window_init()
1187 window->dictBase = (BYTE const*)" "; in ZSTD_window_init()
1189 … window->dictLimit = ZSTD_WINDOW_START_INDEX; /* start from >0, so that 1st position is valid */ in ZSTD_window_init()
1190 …window->lowLimit = ZSTD_WINDOW_START_INDEX; /* it ensures first and later CCtx usages compress… in ZSTD_window_init()
1191 window->nextSrc = window->base + ZSTD_WINDOW_START_INDEX; /* see issue #1241 */ in ZSTD_window_init()
1192 window->nbOverflowCorrections = 0; in ZSTD_window_init()
1200 * Returns non-zero if the segment is contiguous.
1211 assert(window->base != NULL); in ZSTD_window_update()
1212 assert(window->dictBase != NULL); in ZSTD_window_update()
1214 if (src != window->nextSrc || forceNonContiguous) { in ZSTD_window_update()
1216 size_t const distanceFromBase = (size_t)(window->nextSrc - window->base); in ZSTD_window_update()
1217 DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit); in ZSTD_window_update()
1218 window->lowLimit = window->dictLimit; in ZSTD_window_update()
1220 window->dictLimit = (U32)distanceFromBase; in ZSTD_window_update()
1221 window->dictBase = window->base; in ZSTD_window_update()
1222 window->base = ip - distanceFromBase; in ZSTD_window_update()
1223 /* ms->nextToUpdate = window->dictLimit; */ in ZSTD_window_update()
1224 …if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit; … in ZSTD_window_update()
1227 window->nextSrc = ip + srcSize; in ZSTD_window_update()
1229 if ( (ip+srcSize > window->dictBase + window->lowLimit) in ZSTD_window_update()
1230 & (ip < window->dictBase + window->dictLimit)) { in ZSTD_window_update()
1231 ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase; in ZSTD_window_update()
1232 …U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)window->dictLimit) ? window->dictLimit : (U32)h… in ZSTD_window_update()
1233 window->lowLimit = lowLimitMax; in ZSTD_window_update()
1234 DEBUGLOG(5, "Overlapping extDict and input : new lowLimit = %u", window->lowLimit); in ZSTD_window_update()
1240 * Returns the lowest allowed match index. It may either be in the ext-dict or the prefix.
1245 U32 const lowestValid = ms->window.lowLimit; in ZSTD_getLowestMatchIndex()
1246 U32 const withinWindow = (curr - lowestValid > maxDistance) ? curr - maxDistance : lowestValid; in ZSTD_getLowestMatchIndex()
1247 U32 const isDictionary = (ms->loadedDictEnd != 0); in ZSTD_getLowestMatchIndex()
1262 U32 const lowestValid = ms->window.dictLimit; in ZSTD_getLowestPrefixIndex()
1263 … U32 const withinWindow = (curr - lowestValid > maxDistance) ? curr - maxDistance : lowestValid; in ZSTD_getLowestPrefixIndex()
1264 U32 const isDictionary = (ms->loadedDictEnd != 0); in ZSTD_getLowestPrefixIndex()
1299 u, table[u], ZSTD_fWeight(sum) - ZSTD_fWeight(table[u]) ); in ZSTD_debugTable()
1371 * output an empty Block with end-of-frame mark to complete a frame
1381 * This cannot be used when long range matching is enabled.
1383 * compressor.
1385 * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory