Lines Matching +full:1 +full:ms
30 void ZSTD_updateDUBT(ZSTD_MatchState_t* ms, in ZSTD_updateDUBT() argument
34 const ZSTD_compressionParameters* const cParams = &ms->cParams; in ZSTD_updateDUBT()
35 U32* const hashTable = ms->hashTable; in ZSTD_updateDUBT()
38 U32* const bt = ms->chainTable; in ZSTD_updateDUBT()
39 U32 const btLog = cParams->chainLog - 1; in ZSTD_updateDUBT()
40 U32 const btMask = (1 << btLog) - 1; in ZSTD_updateDUBT()
42 const BYTE* const base = ms->window.base; in ZSTD_updateDUBT()
44 U32 idx = ms->nextToUpdate; in ZSTD_updateDUBT()
48 idx, target, ms->window.dictLimit); in ZSTD_updateDUBT()
52 assert(idx >= ms->window.dictLimit); /* condition for valid base+idx */ in ZSTD_updateDUBT()
58 U32* const sortMarkPtr = nextCandidatePtr + 1; in ZSTD_updateDUBT()
65 ms->nextToUpdate = target; in ZSTD_updateDUBT()
75 void ZSTD_insertDUBT1(const ZSTD_MatchState_t* ms, in ZSTD_insertDUBT1() argument
80 const ZSTD_compressionParameters* const cParams = &ms->cParams; in ZSTD_insertDUBT1()
81 U32* const bt = ms->chainTable; in ZSTD_insertDUBT1()
82 U32 const btLog = cParams->chainLog - 1; in ZSTD_insertDUBT1()
83 U32 const btMask = (1 << btLog) - 1; in ZSTD_insertDUBT1()
85 const BYTE* const base = ms->window.base; in ZSTD_insertDUBT1()
86 const BYTE* const dictBase = ms->window.dictBase; in ZSTD_insertDUBT1()
87 const U32 dictLimit = ms->window.dictLimit; in ZSTD_insertDUBT1()
94 U32* largerPtr = smallerPtr + 1; in ZSTD_insertDUBT1()
97 U32 const windowValid = ms->window.lowLimit; in ZSTD_insertDUBT1()
98 U32 const maxDistance = 1U << cParams->windowLog; in ZSTD_insertDUBT1()
112 * but it's still possible to have nextPtr[1] == ZSTD_DUBT_UNSORTED_MARK in ZSTD_insertDUBT1()
145 matchIndex, btLow, nextPtr[1]); in ZSTD_insertDUBT1()
146 …smallerPtr = nextPtr+1; /* new "candidate" => larger than match, which was smaller t… in ZSTD_insertDUBT1()
147 …matchIndex = nextPtr[1]; /* new matchIndex, larger than previous and closer to curren… in ZSTD_insertDUBT1()
166 const ZSTD_MatchState_t* ms, in ZSTD_DUBT_findBetterDictMatch() argument
174 const ZSTD_MatchState_t * const dms = ms->dictMatchState; in ZSTD_DUBT_findBetterDictMatch()
181 const BYTE* const base = ms->window.base; in ZSTD_DUBT_findBetterDictMatch()
182 const BYTE* const prefixStart = base + ms->window.dictLimit; in ZSTD_DUBT_findBetterDictMatch()
188 U32 const dictIndexDelta = ms->window.lowLimit - dictHighLimit; in ZSTD_DUBT_findBetterDictMatch()
191 U32 const btLog = dmsCParams->chainLog - 1; in ZSTD_DUBT_findBetterDictMatch()
192 U32 const btMask = (1 << btLog) - 1; in ZSTD_DUBT_findBetterDictMatch()
210 …ngth-bestLength)) > (int)(ZSTD_highbit32(curr-matchIndex+1) - ZSTD_highbit32((U32)offsetPtr[0]+1))… in ZSTD_DUBT_findBetterDictMatch()
223 …dictMatchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to curren… in ZSTD_DUBT_findBetterDictMatch()
244 size_t ZSTD_DUBT_findBestMatch(ZSTD_MatchState_t* ms, in ZSTD_DUBT_findBestMatch() argument
250 const ZSTD_compressionParameters* const cParams = &ms->cParams; in ZSTD_DUBT_findBestMatch()
251 U32* const hashTable = ms->hashTable; in ZSTD_DUBT_findBestMatch()
256 const BYTE* const base = ms->window.base; in ZSTD_DUBT_findBestMatch()
258 U32 const windowLow = ZSTD_getLowestMatchIndex(ms, curr, cParams->windowLog); in ZSTD_DUBT_findBestMatch()
260 U32* const bt = ms->chainTable; in ZSTD_DUBT_findBestMatch()
261 U32 const btLog = cParams->chainLog - 1; in ZSTD_DUBT_findBestMatch()
262 U32 const btMask = (1 << btLog) - 1; in ZSTD_DUBT_findBestMatch()
267 U32* unsortedMark = bt + 2*(matchIndex&btMask) + 1; in ZSTD_DUBT_findBestMatch()
268 U32 nbCompares = 1U << cParams->searchLog; in ZSTD_DUBT_findBestMatch()
279 && (nbCandidates > 1) ) { in ZSTD_DUBT_findBestMatch()
286 unsortedMark = bt + 2*(matchIndex&btMask) + 1; in ZSTD_DUBT_findBestMatch()
302 U32* const nextCandidateIdxPtr = bt + 2*(matchIndex&btMask) + 1; in ZSTD_DUBT_findBestMatch()
304 ZSTD_insertDUBT1(ms, matchIndex, iend, in ZSTD_DUBT_findBestMatch()
312 const BYTE* const dictBase = ms->window.dictBase; in ZSTD_DUBT_findBestMatch()
313 const U32 dictLimit = ms->window.dictLimit; in ZSTD_DUBT_findBestMatch()
317 U32* largerPtr = bt + 2*(curr&btMask) + 1; in ZSTD_DUBT_findBestMatch()
318 U32 matchEndIdx = curr + 8 + 1; in ZSTD_DUBT_findBestMatch()
343 …if ( (4*(int)(matchLength-bestLength)) > (int)(ZSTD_highbit32(curr - matchIndex + 1) - ZSTD_highbi… in ZSTD_DUBT_findBestMatch()
360 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */ in ZSTD_DUBT_findBestMatch()
361 …matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */ in ZSTD_DUBT_findBestMatch()
373 assert(nbCompares <= (1U << ZSTD_SEARCHLOG_MAX)); /* Check we haven't underflowed. */ in ZSTD_DUBT_findBestMatch()
376 ms, ip, iend, in ZSTD_DUBT_findBestMatch()
382 ms->nextToUpdate = matchEndIdx - 8; /* skip repetitive patterns */ in ZSTD_DUBT_findBestMatch()
396 size_t ZSTD_BtFindBestMatch( ZSTD_MatchState_t* ms, in ZSTD_BtFindBestMatch() argument
403 if (ip < ms->window.base + ms->nextToUpdate) return 0; /* skipped area */ in ZSTD_BtFindBestMatch()
404 ZSTD_updateDUBT(ms, ip, iLimit, mls); in ZSTD_BtFindBestMatch()
405 return ZSTD_DUBT_findBestMatch(ms, ip, iLimit, offBasePtr, mls, dictMode); in ZSTD_BtFindBestMatch()
412 void ZSTD_dedicatedDictSearch_lazy_loadDictionary(ZSTD_MatchState_t* ms, const BYTE* const ip) in ZSTD_dedicatedDictSearch_lazy_loadDictionary() argument
414 const BYTE* const base = ms->window.base; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
416 U32* const hashTable = ms->hashTable; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
417 U32* const chainTable = ms->chainTable; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
418 U32 const chainSize = 1 << ms->cParams.chainLog; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
419 U32 idx = ms->nextToUpdate; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
421 U32 const bucketSize = 1 << ZSTD_LAZY_DDSS_BUCKET_LOG; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
422 U32 const cacheSize = bucketSize - 1; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
423 U32 const chainAttempts = (1 << ms->cParams.searchLog) - cacheSize; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
427 * We are going to temporarily pretend `bucketSize == 1`, keeping only a in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
431 U32 const hashLog = ms->cParams.hashLog - ZSTD_LAZY_DDSS_BUCKET_LOG; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
433 U32* const tmpChainTable = hashTable + ((size_t)1 << hashLog); in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
434 U32 const tmpChainSize = (U32)((1 << ZSTD_LAZY_DDSS_BUCKET_LOG) - 1) << hashLog; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
438 assert(ms->cParams.chainLog <= 24); in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
439 assert(ms->cParams.hashLog > ms->cParams.chainLog); in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
445 U32 const h = (U32)ZSTD_hashPtr(base + idx, hashLog, ms->cParams.minMatch); in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
455 for (hashIdx = 0; hashIdx < (1U << hashLog); hashIdx++) { in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
502 for (hashIdx = (1 << hashLog); hashIdx; ) { in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
509 hashTable[bucketIdx + bucketSize - 1] = chainPackedPointer; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
513 for (idx = ms->nextToUpdate; idx < target; idx++) { in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
514 U32 const h = (U32)ZSTD_hashPtr(base + idx, hashLog, ms->cParams.minMatch) in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
517 /* Shift hash cache down 1. */ in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
518 for (i = cacheSize - 1; i; i--) in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
519 hashTable[h + i] = hashTable[h + i - 1]; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
523 ms->nextToUpdate = target; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
540 const U32 bucketSize = (1 << ZSTD_LAZY_DDSS_BUCKET_LOG); in ZSTD_dedicatedDictSearch_lazy_search()
541 const U32 bucketLimit = nbAttempts < bucketSize - 1 ? nbAttempts : bucketSize - 1; in ZSTD_dedicatedDictSearch_lazy_search()
545 for (ddsAttempt = 0; ddsAttempt < bucketSize - 1; ddsAttempt++) { in ZSTD_dedicatedDictSearch_lazy_search()
550 U32 const chainPackedPointer = dms->hashTable[ddsIdx + bucketSize - 1]; in ZSTD_dedicatedDictSearch_lazy_search()
587 U32 const chainPackedPointer = dms->hashTable[ddsIdx + bucketSize - 1]; in ZSTD_dedicatedDictSearch_lazy_search()
634 ZSTD_MatchState_t* ms, in ZSTD_insertAndFindFirstIndex_internal() argument
638 U32* const hashTable = ms->hashTable; in ZSTD_insertAndFindFirstIndex_internal()
640 U32* const chainTable = ms->chainTable; in ZSTD_insertAndFindFirstIndex_internal()
641 const U32 chainMask = (1 << cParams->chainLog) - 1; in ZSTD_insertAndFindFirstIndex_internal()
642 const BYTE* const base = ms->window.base; in ZSTD_insertAndFindFirstIndex_internal()
644 U32 idx = ms->nextToUpdate; in ZSTD_insertAndFindFirstIndex_internal()
656 ms->nextToUpdate = target; in ZSTD_insertAndFindFirstIndex_internal()
660 U32 ZSTD_insertAndFindFirstIndex(ZSTD_MatchState_t* ms, const BYTE* ip) { in ZSTD_insertAndFindFirstIndex() argument
661 const ZSTD_compressionParameters* const cParams = &ms->cParams; in ZSTD_insertAndFindFirstIndex()
662 …return ZSTD_insertAndFindFirstIndex_internal(ms, cParams, ip, ms->cParams.minMatch, /* lazySkippin… in ZSTD_insertAndFindFirstIndex()
669 ZSTD_MatchState_t* ms, in ZSTD_HcFindBestMatch() argument
674 const ZSTD_compressionParameters* const cParams = &ms->cParams; in ZSTD_HcFindBestMatch()
675 U32* const chainTable = ms->chainTable; in ZSTD_HcFindBestMatch()
676 const U32 chainSize = (1 << cParams->chainLog); in ZSTD_HcFindBestMatch()
677 const U32 chainMask = chainSize-1; in ZSTD_HcFindBestMatch()
678 const BYTE* const base = ms->window.base; in ZSTD_HcFindBestMatch()
679 const BYTE* const dictBase = ms->window.dictBase; in ZSTD_HcFindBestMatch()
680 const U32 dictLimit = ms->window.dictLimit; in ZSTD_HcFindBestMatch()
684 const U32 maxDistance = 1U << cParams->windowLog; in ZSTD_HcFindBestMatch()
685 const U32 lowestValid = ms->window.lowLimit; in ZSTD_HcFindBestMatch()
687 const U32 isDictionary = (ms->loadedDictEnd != 0); in ZSTD_HcFindBestMatch()
690 U32 nbAttempts = 1U << cParams->searchLog; in ZSTD_HcFindBestMatch()
691 size_t ml=4-1; in ZSTD_HcFindBestMatch()
693 const ZSTD_MatchState_t* const dms = ms->dictMatchState; in ZSTD_HcFindBestMatch()
707 matchIndex = ZSTD_insertAndFindFirstIndex_internal(ms, cParams, ip, mls, ms->lazySkipping); in ZSTD_HcFindBestMatch()
714 /* read 4B starting from (match + ml + 1 - sizeof(U32)) */ in ZSTD_HcFindBestMatch()
735 assert(nbAttempts <= (1U << ZSTD_SEARCHLOG_MAX)); /* Check we haven't underflowed. */ in ZSTD_HcFindBestMatch()
741 const U32 dmsChainSize = (1 << dms->cParams.chainLog); in ZSTD_HcFindBestMatch()
742 const U32 dmsChainMask = dmsChainSize - 1; in ZSTD_HcFindBestMatch()
780 #define ZSTD_ROW_HASH_TAG_MASK ((1u << ZSTD_ROW_HASH_TAG_BITS) - 1)
783 #define ZSTD_ROW_HASH_CACHE_MASK (ZSTD_ROW_HASH_CACHE_SIZE - 1)
797 * value to reflect the update. Essentially cycles backwards from [1, {entries per row})
800 U32 next = (*tagRow-1) & rowMask; in ZSTD_row_nextIndex()
810 assert((align & (align - 1)) == 0); in ZSTD_isAligned()
811 return (((size_t)ptr) & (align - 1)) == 0; in ZSTD_isAligned()
829 …assert(ZSTD_isAligned(tagTable + relRow, (size_t)1 << rowLog)); /* prefetched tagRow sits on corre… in ZSTD_row_prefetch()
838 void ZSTD_row_fillHashCache(ZSTD_MatchState_t* ms, const BYTE* base, in ZSTD_row_fillHashCache() argument
842 U32 const* const hashTable = ms->hashTable; in ZSTD_row_fillHashCache()
843 BYTE const* const tagTable = ms->tagTable; in ZSTD_row_fillHashCache()
844 U32 const hashLog = ms->rowHashLog; in ZSTD_row_fillHashCache()
845 U32 const maxElemsToPrefetch = (base + idx) > iLimit ? 0 : (U32)(iLimit - (base + idx) + 1); in ZSTD_row_fillHashCache()
849 …st hash = (U32)ZSTD_hashPtrSalted(base + idx, hashLog + ZSTD_ROW_HASH_TAG_BITS, mls, ms->hashSalt); in ZSTD_row_fillHashCache()
852 ms->hashCache[idx & ZSTD_ROW_HASH_CACHE_MASK] = hash; in ZSTD_row_fillHashCache()
855 …UGLOG(6, "ZSTD_row_fillHashCache(): [%u %u %u %u %u %u %u %u]", ms->hashCache[0], ms->hashCache[1], in ZSTD_row_fillHashCache()
856 … ms->hashCache[2], ms->hashCache[3], ms->hashCache[4], in ZSTD_row_fillHashCache()
857 … ms->hashCache[5], ms->hashCache[6], ms->hashCache[7]); in ZSTD_row_fillHashCache()
886 void ZSTD_row_update_internalImpl(ZSTD_MatchState_t* ms, in ZSTD_row_update_internalImpl() argument
891 U32* const hashTable = ms->hashTable; in ZSTD_row_update_internalImpl()
892 BYTE* const tagTable = ms->tagTable; in ZSTD_row_update_internalImpl()
893 U32 const hashLog = ms->rowHashLog; in ZSTD_row_update_internalImpl()
894 const BYTE* const base = ms->window.base; in ZSTD_row_update_internalImpl()
898 …useCache ? ZSTD_row_nextCachedHash(ms->hashCache, hashTable, tagTable, base, updateStartIdx, hashL… in ZSTD_row_update_internalImpl()
899 …U32)ZSTD_hashPtrSalted(base + updateStartIdx, hashLog + ZSTD_ROW_HASH_TAG_BITS, mls, ms->hashSalt); in ZSTD_row_update_internalImpl()
905 …== ZSTD_hashPtrSalted(base + updateStartIdx, hashLog + ZSTD_ROW_HASH_TAG_BITS, mls, ms->hashSalt)); in ZSTD_row_update_internalImpl()
912 …* Inserts the byte at ip into the appropriate position in the hash table, and updates ms->nextToUp…
917 void ZSTD_row_update_internal(ZSTD_MatchState_t* ms, const BYTE* ip, in ZSTD_row_update_internal() argument
921 U32 idx = ms->nextToUpdate; in ZSTD_row_update_internal()
922 const BYTE* const base = ms->window.base; in ZSTD_row_update_internal()
936 ZSTD_row_update_internalImpl(ms, idx, bound, mls, rowLog, rowMask, useCache); in ZSTD_row_update_internal()
938 ZSTD_row_fillHashCache(ms, base, rowLog, mls, idx, ip+1); in ZSTD_row_update_internal()
942 ZSTD_row_update_internalImpl(ms, idx, target, mls, rowLog, rowMask, useCache); in ZSTD_row_update_internal()
943 ms->nextToUpdate = target; in ZSTD_row_update_internal()
950 void ZSTD_row_update(ZSTD_MatchState_t* const ms, const BYTE* ip) { in ZSTD_row_update() argument
951 const U32 rowLog = BOUNDED(4, ms->cParams.searchLog, 6); in ZSTD_row_update()
952 const U32 rowMask = (1u << rowLog) - 1; in ZSTD_row_update()
953 const U32 mls = MIN(ms->cParams.minMatch, 6 /* mls caps out at 6 */); in ZSTD_row_update()
956 ZSTD_row_update_internal(ms, ip, mls, rowLog, rowMask, 0 /* don't use cache */); in ZSTD_row_update()
959 /* Returns the mask width of bits group of which will be set to 1. Given not all
972 return 1; in ZSTD_row_matchMaskGroupWidth()
981 return 1; in ZSTD_row_matchMaskGroupWidth()
984 return 1; in ZSTD_row_matchMaskGroupWidth()
994 assert(nbChunks == 1 || nbChunks == 2 || nbChunks == 4); in ZSTD_row_getSSEMask()
1000 if (nbChunks == 1) return ZSTD_rotateRight_U16((U16)matches[0], head); in ZSTD_row_getSSEMask()
1001 if (nbChunks == 2) return ZSTD_rotateRight_U32((U32)matches[1] << 16 | (U32)matches[0], head); in ZSTD_row_getSSEMask()
1003 …return ZSTD_rotateRight_U64((U64)matches[3] << 48 | (U64)matches[2] << 32 | (U64)matches[1] << 16 … in ZSTD_row_getSSEMask()
1029 const uint8x16_t chunk1 = vreinterpretq_u8_u16(chunk.val[1]); in ZSTD_row_getNEONMask()
1040 const uint8x16_t cmp1 = vceqq_u8(chunk.val[1], dup); in ZSTD_row_getNEONMask()
1044 const uint8x16_t t0 = vsriq_n_u8(cmp1, cmp0, 1); in ZSTD_row_getNEONMask()
1045 const uint8x16_t t1 = vsriq_n_u8(cmp3, cmp2, 1); in ZSTD_row_getNEONMask()
1056 * ZSTD_row_matchMaskGroupWidth) of bits set to 1 if the newly-computed "tag"
1102 const size_t msb = xFF ^ (xFF >> 1); in ZSTD_row_getMatchMask()
1135 …* - Use SIMD to efficiently compare the tags in the tagTable to the 1-byte tag calculated for the …
1143 ZSTD_MatchState_t* ms, in ZSTD_RowFindBestMatch() argument
1149 U32* const hashTable = ms->hashTable; in ZSTD_RowFindBestMatch()
1150 BYTE* const tagTable = ms->tagTable; in ZSTD_RowFindBestMatch()
1151 U32* const hashCache = ms->hashCache; in ZSTD_RowFindBestMatch()
1152 const U32 hashLog = ms->rowHashLog; in ZSTD_RowFindBestMatch()
1153 const ZSTD_compressionParameters* const cParams = &ms->cParams; in ZSTD_RowFindBestMatch()
1154 const BYTE* const base = ms->window.base; in ZSTD_RowFindBestMatch()
1155 const BYTE* const dictBase = ms->window.dictBase; in ZSTD_RowFindBestMatch()
1156 const U32 dictLimit = ms->window.dictLimit; in ZSTD_RowFindBestMatch()
1160 const U32 maxDistance = 1U << cParams->windowLog; in ZSTD_RowFindBestMatch()
1161 const U32 lowestValid = ms->window.lowLimit; in ZSTD_RowFindBestMatch()
1163 const U32 isDictionary = (ms->loadedDictEnd != 0); in ZSTD_RowFindBestMatch()
1165 const U32 rowEntries = (1U << rowLog); in ZSTD_RowFindBestMatch()
1166 const U32 rowMask = rowEntries - 1; in ZSTD_RowFindBestMatch()
1169 const U64 hashSalt = ms->hashSalt; in ZSTD_RowFindBestMatch()
1170 U32 nbAttempts = 1U << cappedSearchLog; in ZSTD_RowFindBestMatch()
1171 size_t ml=4-1; in ZSTD_RowFindBestMatch()
1175 const ZSTD_MatchState_t* const dms = ms->dictMatchState; in ZSTD_RowFindBestMatch()
1190 ddsExtraAttempts = cParams->searchLog > rowLog ? 1U << (cParams->searchLog - rowLog) : 0; in ZSTD_RowFindBestMatch()
1206 if (!ms->lazySkipping) { in ZSTD_RowFindBestMatch()
1207 ZSTD_row_update_internal(ms, ip, mls, rowLog, rowMask, 1 /* useCache */); in ZSTD_RowFindBestMatch()
1214 ms->nextToUpdate = curr; in ZSTD_RowFindBestMatch()
1216 ms->hashSaltEntropy += hash; /* collect salt entropy */ in ZSTD_RowFindBestMatch()
1230 for (; (matches > 0) && (nbAttempts > 0); matches &= (matches - 1)) { in ZSTD_RowFindBestMatch()
1251 row[pos] = ms->nextToUpdate++; in ZSTD_RowFindBestMatch()
1264 /* read 4B starting from (match + ml + 1 - sizeof(U32)) */ in ZSTD_RowFindBestMatch()
1283 assert(nbAttempts <= (1U << ZSTD_SEARCHLOG_MAX)); /* Check we haven't underflowed. */ in ZSTD_RowFindBestMatch()
1301 for (; (matches > 0) && (nbAttempts > 0); matches &= (matches - 1)) { in ZSTD_RowFindBestMatch()
1368 ZSTD_MatchState_t* ms, \
1372 assert(MAX(4, MIN(6, ms->cParams.minMatch)) == mls); \
1373 return ZSTD_BtFindBestMatch(ms, ip, iLimit, offBasePtr, mls, ZSTD_##dictMode); \
1378 ZSTD_MatchState_t* ms, \
1382 assert(MAX(4, MIN(6, ms->cParams.minMatch)) == mls); \
1383 return ZSTD_HcFindBestMatch(ms, ip, iLimit, offsetPtr, mls, ZSTD_##dictMode); \
1388 ZSTD_MatchState_t* ms, \
1392 assert(MAX(4, MIN(6, ms->cParams.minMatch)) == mls); \
1393 assert(MAX(4, MIN(6, ms->cParams.searchLog)) == rowLog); \
1394 return ZSTD_RowFindBestMatch(ms, ip, iLimit, offsetPtr, mls, ZSTD_##dictMode, rowLog); \
1425 typedef enum { search_hashChain=0, search_binaryTree=1, search_rowHash=2 } searchMethod_e;
1429 return ZSTD_BT_SEARCH_FN(dictMode, mls)(ms, ip, iend, offsetPtr);
1432 return ZSTD_HC_SEARCH_FN(dictMode, mls)(ms, ip, iend, offsetPtr);
1435 return ZSTD_ROW_SEARCH_FN(dictMode, mls, rowLog)(ms, ip, iend, offsetPtr);
1476 * @param ms The match state.
1489 ZSTD_MatchState_t* ms, in ZSTD_searchMax() argument
1518 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, in ZSTD_compressBlock_lazy_generic() argument
1529 const BYTE* const base = ms->window.base; in ZSTD_compressBlock_lazy_generic()
1530 const U32 prefixLowestIndex = ms->window.dictLimit; in ZSTD_compressBlock_lazy_generic()
1532 const U32 mls = BOUNDED(4, ms->cParams.minMatch, 6); in ZSTD_compressBlock_lazy_generic()
1533 const U32 rowLog = BOUNDED(4, ms->cParams.searchLog, 6); in ZSTD_compressBlock_lazy_generic()
1535 U32 offset_1 = rep[0], offset_2 = rep[1]; in ZSTD_compressBlock_lazy_generic()
1541 const ZSTD_MatchState_t* const dms = ms->dictMatchState; in ZSTD_compressBlock_lazy_generic()
1555 U32 const windowLow = ZSTD_getLowestPrefixIndex(ms, curr, ms->cParams.windowLog); in ZSTD_compressBlock_lazy_generic()
1568 ms->lazySkipping = 0; in ZSTD_compressBlock_lazy_generic()
1571 ZSTD_row_fillHashCache(ms, base, rowLog, mls, ms->nextToUpdate, ilimit); in ZSTD_compressBlock_lazy_generic()
1584 const BYTE* start=ip+1; in ZSTD_compressBlock_lazy_generic()
1589 const U32 repIndex = (U32)(ip - base) + 1 - offset_1; in ZSTD_compressBlock_lazy_generic()
1595 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) { in ZSTD_compressBlock_lazy_generic()
1597 … matchLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixLowest) + 4; in ZSTD_compressBlock_lazy_generic()
1602 && ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1)))) { in ZSTD_compressBlock_lazy_generic()
1603 matchLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4; in ZSTD_compressBlock_lazy_generic()
1609 …size_t const ml2 = ZSTD_searchMax(ms, ip, iend, &offbaseFound, mls, rowLog, searchMethod, dictMode… in ZSTD_compressBlock_lazy_generic()
1615 …size_t const step = ((size_t)(ip-anchor) >> kSearchStrength) + 1; /* jump faster over incompress… in ZSTD_compressBlock_lazy_generic()
1624 ms->lazySkipping = step > kLazySkippingStep; in ZSTD_compressBlock_lazy_generic()
1629 if (depth>=1) in ZSTD_compressBlock_lazy_generic()
1631 DEBUGLOG(7, "search depth 1"); in ZSTD_compressBlock_lazy_generic()
1637 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offBase) + 1); in ZSTD_compressBlock_lazy_generic()
1651 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offBase) + 1); in ZSTD_compressBlock_lazy_generic()
1657 …size_t const ml2 = ZSTD_searchMax(ms, ip, iend, &ofbCandidate, mls, rowLog, searchMethod, dictMode… in ZSTD_compressBlock_lazy_generic()
1673 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offBase) + 1); in ZSTD_compressBlock_lazy_generic()
1687 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offBase) + 1); in ZSTD_compressBlock_lazy_generic()
1693 …size_t const ml2 = ZSTD_searchMax(ms, ip, iend, &ofbCandidate, mls, rowLog, searchMethod, dictMode… in ZSTD_compressBlock_lazy_generic()
1711 …&& (start[-1] == (start-OFFBASE_TO_OFFSET(offBase))[-1]) ) /* only search for offset within prefi… in ZSTD_compressBlock_lazy_generic()
1718 …while ((start>anchor) && (match>mStart) && (start[-1] == match[-1])) { start--; match--; matchLeng… in ZSTD_compressBlock_lazy_generic()
1728 if (ms->lazySkipping) { in ZSTD_compressBlock_lazy_generic()
1731 ZSTD_row_fillHashCache(ms, base, rowLog, mls, ms->nextToUpdate, ilimit); in ZSTD_compressBlock_lazy_generic()
1733 ms->lazySkipping = 0; in ZSTD_compressBlock_lazy_generic()
1776 rep[1] = offset_2 ? offset_2 : offsetSaved2; in ZSTD_compressBlock_lazy_generic()
1786 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy() argument
1789 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 0, ZSTD_… in ZSTD_compressBlock_greedy()
1793 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_dictMatchState() argument
1796 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 0, ZSTD_… in ZSTD_compressBlock_greedy_dictMatchState()
1800 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_dedicatedDictSearch() argument
1803 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 0, ZSTD_… in ZSTD_compressBlock_greedy_dedicatedDictSearch()
1807 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_row() argument
1810 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_rowHash, 0, ZSTD_no… in ZSTD_compressBlock_greedy_row()
1814 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_dictMatchState_row() argument
1817 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_rowHash, 0, ZSTD_di… in ZSTD_compressBlock_greedy_dictMatchState_row()
1821 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_dedicatedDictSearch_row() argument
1824 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_rowHash, 0, ZSTD_de… in ZSTD_compressBlock_greedy_dedicatedDictSearch_row()
1830 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy() argument
1833 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 1, ZSTD_… in ZSTD_compressBlock_lazy()
1837 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_dictMatchState() argument
1840 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 1, ZSTD_… in ZSTD_compressBlock_lazy_dictMatchState()
1844 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_dedicatedDictSearch() argument
1847 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 1, ZSTD_… in ZSTD_compressBlock_lazy_dedicatedDictSearch()
1851 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_row() argument
1854 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_rowHash, 1, ZSTD_no… in ZSTD_compressBlock_lazy_row()
1858 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_dictMatchState_row() argument
1861 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_rowHash, 1, ZSTD_di… in ZSTD_compressBlock_lazy_dictMatchState_row()
1865 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_dedicatedDictSearch_row() argument
1868 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_rowHash, 1, ZSTD_de… in ZSTD_compressBlock_lazy_dedicatedDictSearch_row()
1874 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2() argument
1877 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 2, ZSTD_… in ZSTD_compressBlock_lazy2()
1881 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_dictMatchState() argument
1884 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 2, ZSTD_… in ZSTD_compressBlock_lazy2_dictMatchState()
1888 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_dedicatedDictSearch() argument
1891 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 2, ZSTD_… in ZSTD_compressBlock_lazy2_dedicatedDictSearch()
1895 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_row() argument
1898 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_rowHash, 2, ZSTD_no… in ZSTD_compressBlock_lazy2_row()
1902 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_dictMatchState_row() argument
1905 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_rowHash, 2, ZSTD_di… in ZSTD_compressBlock_lazy2_dictMatchState_row()
1909 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_dedicatedDictSearch_row() argument
1912 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_rowHash, 2, ZSTD_de… in ZSTD_compressBlock_lazy2_dedicatedDictSearch_row()
1918 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btlazy2() argument
1921 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_binaryTree, 2, ZSTD… in ZSTD_compressBlock_btlazy2()
1925 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btlazy2_dictMatchState() argument
1928 …return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_binaryTree, 2, ZSTD… in ZSTD_compressBlock_btlazy2_dictMatchState()
1939 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, in ZSTD_compressBlock_lazy_extDict_generic() argument
1949 const BYTE* const base = ms->window.base; in ZSTD_compressBlock_lazy_extDict_generic()
1950 const U32 dictLimit = ms->window.dictLimit; in ZSTD_compressBlock_lazy_extDict_generic()
1952 const BYTE* const dictBase = ms->window.dictBase; in ZSTD_compressBlock_lazy_extDict_generic()
1954 const BYTE* const dictStart = dictBase + ms->window.lowLimit; in ZSTD_compressBlock_lazy_extDict_generic()
1955 const U32 windowLog = ms->cParams.windowLog; in ZSTD_compressBlock_lazy_extDict_generic()
1956 const U32 mls = BOUNDED(4, ms->cParams.minMatch, 6); in ZSTD_compressBlock_lazy_extDict_generic()
1957 const U32 rowLog = BOUNDED(4, ms->cParams.searchLog, 6); in ZSTD_compressBlock_lazy_extDict_generic()
1959 U32 offset_1 = rep[0], offset_2 = rep[1]; in ZSTD_compressBlock_lazy_extDict_generic()
1964 ms->lazySkipping = 0; in ZSTD_compressBlock_lazy_extDict_generic()
1969 ZSTD_row_fillHashCache(ms, base, rowLog, mls, ms->nextToUpdate, ilimit); in ZSTD_compressBlock_lazy_extDict_generic()
1982 const BYTE* start=ip+1; in ZSTD_compressBlock_lazy_extDict_generic()
1986 { const U32 windowLow = ZSTD_getLowestMatchIndex(ms, curr+1, windowLog); in ZSTD_compressBlock_lazy_extDict_generic()
1987 const U32 repIndex = (U32)(curr+1 - offset_1); in ZSTD_compressBlock_lazy_extDict_generic()
1991 & (offset_1 <= curr+1 - windowLow) ) /* note: we are searching at curr+1 */ in ZSTD_compressBlock_lazy_extDict_generic()
1992 if (MEM_read32(ip+1) == MEM_read32(repMatch)) { in ZSTD_compressBlock_lazy_extDict_generic()
1995 … matchLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repEnd, prefixStart) + 4; in ZSTD_compressBlock_lazy_extDict_generic()
2001 …size_t const ml2 = ZSTD_searchMax(ms, ip, iend, &ofbCandidate, mls, rowLog, searchMethod, ZSTD_ext… in ZSTD_compressBlock_lazy_extDict_generic()
2008 ip += step + 1; /* jump faster over incompressible sections */ in ZSTD_compressBlock_lazy_extDict_generic()
2016 ms->lazySkipping = step > kLazySkippingStep; in ZSTD_compressBlock_lazy_extDict_generic()
2021 if (depth>=1) in ZSTD_compressBlock_lazy_extDict_generic()
2027 const U32 windowLow = ZSTD_getLowestMatchIndex(ms, curr, windowLog); in ZSTD_compressBlock_lazy_extDict_generic()
2038 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offBase) + 1); in ZSTD_compressBlock_lazy_extDict_generic()
2043 /* search match, depth 1 */ in ZSTD_compressBlock_lazy_extDict_generic()
2045 …size_t const ml2 = ZSTD_searchMax(ms, ip, iend, &ofbCandidate, mls, rowLog, searchMethod, ZSTD_ext… in ZSTD_compressBlock_lazy_extDict_generic()
2059 const U32 windowLow = ZSTD_getLowestMatchIndex(ms, curr, windowLog); in ZSTD_compressBlock_lazy_extDict_generic()
2070 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offBase) + 1); in ZSTD_compressBlock_lazy_extDict_generic()
2077 …size_t const ml2 = ZSTD_searchMax(ms, ip, iend, &ofbCandidate, mls, rowLog, searchMethod, ZSTD_ext… in ZSTD_compressBlock_lazy_extDict_generic()
2092 …while ((start>anchor) && (match>mStart) && (start[-1] == match[-1])) { start--; match--; matchLeng… in ZSTD_compressBlock_lazy_extDict_generic()
2102 if (ms->lazySkipping) { in ZSTD_compressBlock_lazy_extDict_generic()
2105 ZSTD_row_fillHashCache(ms, base, rowLog, mls, ms->nextToUpdate, ilimit); in ZSTD_compressBlock_lazy_extDict_generic()
2107 ms->lazySkipping = 0; in ZSTD_compressBlock_lazy_extDict_generic()
2113 const U32 windowLow = ZSTD_getLowestMatchIndex(ms, repCurrent, windowLog); in ZSTD_compressBlock_lazy_extDict_generic()
2134 rep[1] = offset_2; in ZSTD_compressBlock_lazy_extDict_generic()
2143 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_extDict() argument
2146 …return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_hashChain, … in ZSTD_compressBlock_greedy_extDict()
2150 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_extDict_row() argument
2153 …return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_rowHash, 0); in ZSTD_compressBlock_greedy_extDict_row()
2159 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_extDict() argument
2163 …return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_hashChain, … in ZSTD_compressBlock_lazy_extDict()
2167 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_extDict_row() argument
2171 …return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_rowHash, 1); in ZSTD_compressBlock_lazy_extDict_row()
2177 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_extDict() argument
2181 …return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_hashChain, … in ZSTD_compressBlock_lazy2_extDict()
2185 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_extDict_row() argument
2188 …return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_rowHash, 2); in ZSTD_compressBlock_lazy2_extDict_row()
2194 ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btlazy2_extDict() argument
2198 …return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_binaryTree,… in ZSTD_compressBlock_btlazy2_extDict()