Lines Matching +full:diff +full:- +full:sequences
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 /*-*************************************
32 /*-*************************************
46 /*-*************************************
89 * Stores Literals Block Type for a super-block in hType, and
100 * Stores symbol compression modes for a super-block in {ll, ol, ml}Type, and
145 rawSeq* seq; /* The start of the sequences */
149 size_t size; /* The number of sequences. <= capacity. */
156 size_t posInSrc; /* Number of bytes given by sequences provided so far */
173 /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */
189 …ZSTD_OptPrice_e priceType; /* prices can be determined dynamically, or follow a pre-defined cost…
190 const ZSTD_entropyCTables_t* symbolCosts; /* pre-calculated dictionary statistics */
215 #define ZSTD_ROW_HASH_CACHE_SIZE 8 /* Size of prefetching hash cache for row-based matchfinde…
229 …U32 rowHashLog; /* For row-based matchfinder: Hashlog based on nb of rows…
230 …BYTE* tagTable; /* For row-based matchFinder: A row-based table containin…
231 …U32 hashCache[ZSTD_ROW_HASH_CACHE_SIZE]; /* For row-based matchFinder: a cache of hashes to improv…
232 …U64 hashSalt; /* For row-based matchFinder: salts the hash for reuse of…
233 …U32 hashSaltEntropy; /* For row-based matchFinder: collects entropy for salt g…
239 …U32 forceNonContiguous; /* Non-zero if we should force non-contiguous load for the next window upd…
313 int forceWindow; /* force back-references to respect limit of
348 /* Param for deciding whether to use row-based matchfinder */
351 /* Always load a dictionary in ext-dict mode (not prefix mode)? */
381 * Indicates whether this compression proceeds directly from user-provided
382 * source buffer to user-provided destination buffer (ZSTDb_not_buffered), or
412 …pleApiParams; /* Param storage used by the simple API - not sticky. Must only be used in top-le…
429 seqStore_t seqStore; /* sequences storage ptrs */
431 rawSeq* ldmSequences; /* Storage for the ldm output sequences */
433 rawSeqStore_t externSeqStore; /* Mutable reference to external sequences */
461 ZSTD_prefixDict prefixDict; /* single-usage dictionary */
463 /* Multi-threading */
532 * note : mlBase = matchLength - MINMATCH;
533 * because it's the format it's stored in seqStore->sequences */
593 U32 const minlog = (strat>=ZSTD_btultra) ? (U32)(strat) - 1 : 6; in ZSTD_minGain()
601 switch (cctxParams->literalCompressionMode) { in ZSTD_literalsCompressionIsDisabled()
607 assert(0 /* impossible: pre-validated */); in ZSTD_literalsCompressionIsDisabled()
610 … return (cctxParams->cParams.strategy == ZSTD_fast) && (cctxParams->cParams.targetLength > 0); in ZSTD_literalsCompressionIsDisabled()
624 ZSTD_wildcopy(op, ip, ilimit_w - ip, ZSTD_no_overlap); in ZSTD_safecopyLiterals()
625 op += ilimit_w - ip; in ZSTD_safecopyLiterals()
639 #define OFFBASE_TO_OFFSET(o) (assert(OFFBASE_IS_OFFSET(o)), (o) - ZSTD_REP_NUM)
646 * Allowed to over-read literals up to litLimit.
654 BYTE const* const litLimit_w = litLimit - WILDCOPY_OVERLENGTH; in ZSTD_storeSeq()
659 { U32 const pos = (U32)((const BYTE*)literals - g_start); in ZSTD_storeSeq()
664 assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq); in ZSTD_storeSeq()
666 assert(seqStorePtr->maxNbLit <= 128 KB); in ZSTD_storeSeq()
667 assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit); in ZSTD_storeSeq()
674 ZSTD_copy16(seqStorePtr->lit, literals); in ZSTD_storeSeq()
676 … ZSTD_wildcopy(seqStorePtr->lit+16, literals+16, (ptrdiff_t)litLength-16, ZSTD_no_overlap); in ZSTD_storeSeq()
679 ZSTD_safecopyLiterals(seqStorePtr->lit, literals, litEnd, litLimit_w); in ZSTD_storeSeq()
681 seqStorePtr->lit += litLength; in ZSTD_storeSeq()
685 … assert(seqStorePtr->longLengthType == ZSTD_llt_none); /* there can only be a single long length */ in ZSTD_storeSeq()
686 seqStorePtr->longLengthType = ZSTD_llt_literalLength; in ZSTD_storeSeq()
687 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); in ZSTD_storeSeq()
689 seqStorePtr->sequences[0].litLength = (U16)litLength; in ZSTD_storeSeq()
692 seqStorePtr->sequences[0].offBase = offBase; in ZSTD_storeSeq()
696 { size_t const mlBase = matchLength - MINMATCH; in ZSTD_storeSeq()
698 … assert(seqStorePtr->longLengthType == ZSTD_llt_none); /* there can only be a single long length */ in ZSTD_storeSeq()
699 seqStorePtr->longLengthType = ZSTD_llt_matchLength; in ZSTD_storeSeq()
700 … seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); in ZSTD_storeSeq()
702 seqStorePtr->sequences[0].mlBase = (U16)mlBase; in ZSTD_storeSeq()
705 seqStorePtr->sequences++; in ZSTD_storeSeq()
709 * updates in-place @rep (array of repeat offsets)
710 * @offBase : sum-type, using numeric representation of ZSTD_storeSeq()
720 U32 const repCode = OFFBASE_TO_REPCODE(offBase) - 1 + ll0; in ZSTD_updateRep()
722 U32 const currentOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode]; in ZSTD_updateRep()
746 /*-*************************************
752 const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1); in ZSTD_count()
755 { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn); in ZSTD_count() local
756 if (diff) return ZSTD_NbCommonBytes(diff); } in ZSTD_count()
759 size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn); in ZSTD_count() local
760 if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; } in ZSTD_count()
761 pIn += ZSTD_NbCommonBytes(diff); in ZSTD_count()
762 return (size_t)(pIn - pStart); in ZSTD_count()
764 …if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatc… in ZSTD_count()
765 if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; } in ZSTD_count()
767 return (size_t)(pIn - pStart); in ZSTD_count()
778 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd); in ZSTD_count_2segments()
781 DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength); in ZSTD_count_2segments()
782 DEBUGLOG(7, "distance from match beginning to end dictionary = %zi", mEnd - match); in ZSTD_count_2segments()
783 DEBUGLOG(7, "distance from current pos to end buffer = %zi", iEnd - ip); in ZSTD_count_2segments()
790 /*-*************************************
794 …(U32 u, U32 h, U32 s) { assert(h <= 32); return (((u << (32-24)) * prime3bytes) ^ s) >> (32-h) ; } in ZSTD_hash3()
799 … ZSTD_hash4(U32 u, U32 h, U32 s) { assert(h <= 32); return ((u * prime4bytes) ^ s) >> (32-h) ; } in ZSTD_hash4()
804 …32 h, U64 s) { assert(h <= 64); return (size_t)((((u << (64-40)) * prime5bytes) ^ s) >> (64-h)) ;… in ZSTD_hash5()
809 …32 h, U64 s) { assert(h <= 64); return (size_t)((((u << (64-48)) * prime6bytes) ^ s) >> (64-h)) ;… in ZSTD_hash6()
814 …32 h, U64 s) { assert(h <= 64); return (size_t)((((u << (64-56)) * prime7bytes) ^ s) >> (64-h)) ;… in ZSTD_hash7()
819 …8(U64 u, U32 h, U64 s) { assert(h <= 64); return (size_t)((((u) * prime8bytes) ^ s) >> (64-h)) ; } in ZSTD_hash8()
904 return ZSTD_ipow(prime8bytes, length - 1); in ZSTD_rollingHash_primePower()
912 hash -= (toRemove + ZSTD_ROLL_HASH_CHAR_OFFSET) * primePower; in ZSTD_rollingHash_rotate()
918 /*-*************************************
928 ( ((U32)-1) /* Maximum ending current index */ \
929 - ZSTD_CURRENT_MAX) /* Maximum beginning lowLimit */
937 size_t const endT = (size_t)(window->nextSrc - window->base); in ZSTD_window_clear()
940 window->lowLimit = end; in ZSTD_window_clear()
941 window->dictLimit = end; in ZSTD_window_clear()
948 (window.nextSrc - window.base) == ZSTD_WINDOW_START_INDEX; in ZSTD_window_isEmpty()
953 * Returns non-zero if the window has a non-empty extDict.
967 return ZSTD_window_hasExtDict(ms->window) ? in ZSTD_matchState_dictMode()
969 ms->dictMatchState != NULL ? in ZSTD_matchState_dictMode()
970 … (ms->dictMatchState->dedicatedDictSearch ? ZSTD_dedicatedDictSearch : ZSTD_dictMatchState) : in ZSTD_matchState_dictMode()
974 /* Defining this macro to non-zero tells zstd to run the overflow correction
988 * Returns non-zero if the indices are large enough for overflow correction
998 U32 const curr = (U32)((BYTE const*)src - window.base); in ZSTD_window_canOverflowCorrect()
1023 * Returns non-zero if the indices are getting too large and need overflow
1033 U32 const curr = (U32)((BYTE const*)srcEnd - window.base); in ZSTD_window_needOverflowCorrection()
1061 * current - newCurrent in ZSTD_window_correctOverflow()
1062 * > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog) in ZSTD_window_correctOverflow()
1063 * > (3<<29) - (1<<chainLog) in ZSTD_window_correctOverflow()
1064 * > (3<<29) - (1<<30) (NOTE: chainLog <= 30) in ZSTD_window_correctOverflow()
1067 * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow: in ZSTD_window_correctOverflow()
1069 * In 64-bit mode we are safe, because we have 64-bit ptrdiff_t. in ZSTD_window_correctOverflow()
1070 * In 32-bit mode we are safe, because (chainLog <= 29), so in ZSTD_window_correctOverflow()
1071 * ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32. in ZSTD_window_correctOverflow()
1072 * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32: in ZSTD_window_correctOverflow()
1076 U32 const cycleMask = cycleSize - 1; in ZSTD_window_correctOverflow()
1077 U32 const curr = (U32)((BYTE const*)src - window->base); in ZSTD_window_correctOverflow()
1079 /* Ensure newCurrent - maxDist >= ZSTD_WINDOW_START_INDEX. */ in ZSTD_window_correctOverflow()
1086 U32 const correction = curr - newCurrent; in ZSTD_window_correctOverflow()
1091 assert((maxDist & (maxDist - 1)) == 0); in ZSTD_window_correctOverflow()
1099 window->base += correction; in ZSTD_window_correctOverflow()
1100 window->dictBase += correction; in ZSTD_window_correctOverflow()
1101 if (window->lowLimit < correction + ZSTD_WINDOW_START_INDEX) { in ZSTD_window_correctOverflow()
1102 window->lowLimit = ZSTD_WINDOW_START_INDEX; in ZSTD_window_correctOverflow()
1104 window->lowLimit -= correction; in ZSTD_window_correctOverflow()
1106 if (window->dictLimit < correction + ZSTD_WINDOW_START_INDEX) { in ZSTD_window_correctOverflow()
1107 window->dictLimit = ZSTD_WINDOW_START_INDEX; in ZSTD_window_correctOverflow()
1109 window->dictLimit -= correction; in ZSTD_window_correctOverflow()
1114 assert(newCurrent - maxDist >= ZSTD_WINDOW_START_INDEX); in ZSTD_window_correctOverflow()
1116 assert(window->lowLimit <= newCurrent); in ZSTD_window_correctOverflow()
1117 assert(window->dictLimit <= newCurrent); in ZSTD_window_correctOverflow()
1119 ++window->nbOverflowCorrections; in ZSTD_window_correctOverflow()
1122 window->lowLimit); in ZSTD_window_correctOverflow()
1129 * (srcEnd - base) - lowLimit == maxDist + loadedDictEnd
1156 U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base); in ZSTD_window_enforceMaxDist()
1161 /* - When there is no dictionary : loadedDictEnd == 0. in ZSTD_window_enforceMaxDist()
1163 overflowing next operation `newLowLimit = blockEndIdx - maxDist`. in ZSTD_window_enforceMaxDist()
1164 - When there is a standard dictionary : in ZSTD_window_enforceMaxDist()
1170 - When there is an attached dictionary : in ZSTD_window_enforceMaxDist()
1175 U32 const newLowLimit = blockEndIdx - maxDist; in ZSTD_window_enforceMaxDist()
1176 if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit; in ZSTD_window_enforceMaxDist()
1177 if (window->dictLimit < window->lowLimit) { in ZSTD_window_enforceMaxDist()
1179 (unsigned)window->dictLimit, (unsigned)window->lowLimit); in ZSTD_window_enforceMaxDist()
1180 window->dictLimit = window->lowLimit; in ZSTD_window_enforceMaxDist()
1192 * loadedDictEnd uses same referential as window->base
1203 { U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base); in ZSTD_checkDictValidity()
1209 if (blockEndIdx > loadedDictEnd + maxDist || loadedDictEnd != window->dictLimit) { in ZSTD_checkDictValidity()
1215 * non-contiguous segments, which means that loadedDictEnd != window->dictLimit. in ZSTD_checkDictValidity()
1230 window->base = (BYTE const*)" "; in ZSTD_window_init()
1231 window->dictBase = (BYTE const*)" "; in ZSTD_window_init()
1233 … window->dictLimit = ZSTD_WINDOW_START_INDEX; /* start from >0, so that 1st position is valid */ in ZSTD_window_init()
1234 …window->lowLimit = ZSTD_WINDOW_START_INDEX; /* it ensures first and later CCtx usages compress… in ZSTD_window_init()
1235 window->nextSrc = window->base + ZSTD_WINDOW_START_INDEX; /* see issue #1241 */ in ZSTD_window_init()
1236 window->nbOverflowCorrections = 0; in ZSTD_window_init()
1244 * Returns non-zero if the segment is contiguous.
1257 assert(window->base != NULL); in ZSTD_window_update()
1258 assert(window->dictBase != NULL); in ZSTD_window_update()
1260 if (src != window->nextSrc || forceNonContiguous) { in ZSTD_window_update()
1262 size_t const distanceFromBase = (size_t)(window->nextSrc - window->base); in ZSTD_window_update()
1263 DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit); in ZSTD_window_update()
1264 window->lowLimit = window->dictLimit; in ZSTD_window_update()
1266 window->dictLimit = (U32)distanceFromBase; in ZSTD_window_update()
1267 window->dictBase = window->base; in ZSTD_window_update()
1268 window->base = ip - distanceFromBase; in ZSTD_window_update()
1269 /* ms->nextToUpdate = window->dictLimit; */ in ZSTD_window_update()
1270 …if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit; … in ZSTD_window_update()
1273 window->nextSrc = ip + srcSize; in ZSTD_window_update()
1275 if ( (ip+srcSize > window->dictBase + window->lowLimit) in ZSTD_window_update()
1276 & (ip < window->dictBase + window->dictLimit)) { in ZSTD_window_update()
1277 ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase; in ZSTD_window_update()
1278 …U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)window->dictLimit) ? window->dictLimit : (U32)h… in ZSTD_window_update()
1279 window->lowLimit = lowLimitMax; in ZSTD_window_update()
1280 DEBUGLOG(5, "Overlapping extDict and input : new lowLimit = %u", window->lowLimit); in ZSTD_window_update()
1286 * Returns the lowest allowed match index. It may either be in the ext-dict or the prefix.
1291 U32 const lowestValid = ms->window.lowLimit; in ZSTD_getLowestMatchIndex()
1292 U32 const withinWindow = (curr - lowestValid > maxDistance) ? curr - maxDistance : lowestValid; in ZSTD_getLowestMatchIndex()
1293 U32 const isDictionary = (ms->loadedDictEnd != 0); in ZSTD_getLowestMatchIndex()
1308 U32 const lowestValid = ms->window.dictLimit; in ZSTD_getLowestPrefixIndex()
1309 … U32 const withinWindow = (curr - lowestValid > maxDistance) ? curr - maxDistance : lowestValid; in ZSTD_getLowestPrefixIndex()
1310 U32 const isDictionary = (ms->loadedDictEnd != 0); in ZSTD_getLowestPrefixIndex()
1345 u, table[u], ZSTD_fWeight(sum) - ZSTD_fWeight(table[u]) ); in ZSTD_debugTable()
1361 * 1. Compute (hash, currentTag) at ip. currentTag is an 8-bit independent hash at ip.
1369 #define ZSTD_SHORT_CACHE_TAG_MASK ((1u << ZSTD_SHORT_CACHE_TAG_BITS) - 1)
1376 assert(index >> (32 - ZSTD_SHORT_CACHE_TAG_BITS) == 0); in ZSTD_writeTaggedIndex()
1456 * output an empty Block with end-of-frame mark to complete a frame
1467 * Zstd will use these sequences, and pass the literals to a secondary block
1469 * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory
1484 * ZSTD_Sequence, storing the sequences it finds, until it reaches a block delimiter.
1494 * Only non-zero if we ended up splitting a sequence.
1498 * represented by the sequences in @inSeqs,
1499 * storing any (partial) sequences.
1512 return params->extSeqProdFunc != NULL; in ZSTD_hasExtSeqProd()