Lines Matching refs:U32
22 U32 mls) in ZSTD_updateDUBT()
25 U32* const hashTable = ms->hashTable; in ZSTD_updateDUBT()
26 U32 const hashLog = cParams->hashLog; in ZSTD_updateDUBT()
28 U32* const bt = ms->chainTable; in ZSTD_updateDUBT()
29 U32 const btLog = cParams->chainLog - 1; in ZSTD_updateDUBT()
30 U32 const btMask = (1 << btLog) - 1; in ZSTD_updateDUBT()
33 U32 const target = (U32)(ip - base); in ZSTD_updateDUBT()
34 U32 idx = ms->nextToUpdate; in ZSTD_updateDUBT()
45 U32 const matchIndex = hashTable[h]; in ZSTD_updateDUBT()
47 U32* const nextCandidatePtr = bt + 2*(idx&btMask); in ZSTD_updateDUBT()
48 U32* const sortMarkPtr = nextCandidatePtr + 1; in ZSTD_updateDUBT()
65 U32 curr, const BYTE* inputEnd, in ZSTD_insertDUBT1()
66 U32 nbCompares, U32 btLow, in ZSTD_insertDUBT1()
70 U32* const bt = ms->chainTable; in ZSTD_insertDUBT1()
71 U32 const btLog = cParams->chainLog - 1; in ZSTD_insertDUBT1()
72 U32 const btMask = (1 << btLog) - 1; in ZSTD_insertDUBT1()
76 const U32 dictLimit = ms->window.dictLimit; in ZSTD_insertDUBT1()
82 U32* smallerPtr = bt + 2*(curr&btMask); in ZSTD_insertDUBT1()
83 U32* largerPtr = smallerPtr + 1; in ZSTD_insertDUBT1()
84 …U32 matchIndex = *smallerPtr; /* this candidate is unsorted : next sorted candidate is reached t… in ZSTD_insertDUBT1()
85 U32 dummy32; /* to be nullified at the end */ in ZSTD_insertDUBT1()
86 U32 const windowValid = ms->window.lowLimit; in ZSTD_insertDUBT1()
87 U32 const maxDistance = 1U << cParams->windowLog; in ZSTD_insertDUBT1()
88 U32 const windowLow = (curr - windowValid > maxDistance) ? curr - maxDistance : windowValid; in ZSTD_insertDUBT1()
97 U32* const nextPtr = bt + 2*(matchIndex & btMask); in ZSTD_insertDUBT1()
122 curr, matchIndex, (U32)matchLength); in ZSTD_insertDUBT1()
158 U32 nbCompares, in ZSTD_DUBT_findBetterDictMatch()
159 U32 const mls, in ZSTD_DUBT_findBetterDictMatch()
164 const U32 * const dictHashTable = dms->hashTable; in ZSTD_DUBT_findBetterDictMatch()
165 U32 const hashLog = dmsCParams->hashLog; in ZSTD_DUBT_findBetterDictMatch()
167 U32 dictMatchIndex = dictHashTable[h]; in ZSTD_DUBT_findBetterDictMatch()
171 U32 const curr = (U32)(ip-base); in ZSTD_DUBT_findBetterDictMatch()
174 U32 const dictHighLimit = (U32)(dms->window.nextSrc - dms->window.base); in ZSTD_DUBT_findBetterDictMatch()
175 U32 const dictLowLimit = dms->window.lowLimit; in ZSTD_DUBT_findBetterDictMatch()
176 U32 const dictIndexDelta = ms->window.lowLimit - dictHighLimit; in ZSTD_DUBT_findBetterDictMatch()
178 U32* const dictBt = dms->chainTable; in ZSTD_DUBT_findBetterDictMatch()
179 U32 const btLog = dmsCParams->chainLog - 1; in ZSTD_DUBT_findBetterDictMatch()
180 U32 const btMask = (1 << btLog) - 1; in ZSTD_DUBT_findBetterDictMatch()
181 …U32 const btLow = (btMask >= dictHighLimit - dictLowLimit) ? dictLowLimit : dictHighLimit … in ZSTD_DUBT_findBetterDictMatch()
189 U32* const nextPtr = dictBt + 2*(dictMatchIndex & btMask); in ZSTD_DUBT_findBetterDictMatch()
197 U32 matchIndex = dictMatchIndex + dictIndexDelta; in ZSTD_DUBT_findBetterDictMatch()
198 …h-bestLength)) > (int)(ZSTD_highbit32(curr-matchIndex+1) - ZSTD_highbit32((U32)offsetPtr[0]+1)) ) { in ZSTD_DUBT_findBetterDictMatch()
200 …curr, (U32)bestLength, (U32)matchLength, (U32)*offsetPtr, STORE_OFFSET(curr - matchIndex), dictMat… in ZSTD_DUBT_findBetterDictMatch()
221 U32 const mIndex = curr - (U32)STORED_OFFSET(*offsetPtr); (void)mIndex; in ZSTD_DUBT_findBetterDictMatch()
223 curr, (U32)bestLength, (U32)*offsetPtr, mIndex); in ZSTD_DUBT_findBetterDictMatch()
234 U32 const mls, in ZSTD_DUBT_findBestMatch()
238 U32* const hashTable = ms->hashTable; in ZSTD_DUBT_findBestMatch()
239 U32 const hashLog = cParams->hashLog; in ZSTD_DUBT_findBestMatch()
241 U32 matchIndex = hashTable[h]; in ZSTD_DUBT_findBestMatch()
244 U32 const curr = (U32)(ip-base); in ZSTD_DUBT_findBestMatch()
245 U32 const windowLow = ZSTD_getLowestMatchIndex(ms, curr, cParams->windowLog); in ZSTD_DUBT_findBestMatch()
247 U32* const bt = ms->chainTable; in ZSTD_DUBT_findBestMatch()
248 U32 const btLog = cParams->chainLog - 1; in ZSTD_DUBT_findBestMatch()
249 U32 const btMask = (1 << btLog) - 1; in ZSTD_DUBT_findBestMatch()
250 U32 const btLow = (btMask >= curr) ? 0 : curr - btMask; in ZSTD_DUBT_findBestMatch()
251 U32 const unsortLimit = MAX(btLow, windowLow); in ZSTD_DUBT_findBestMatch()
253 U32* nextCandidate = bt + 2*(matchIndex&btMask); in ZSTD_DUBT_findBestMatch()
254 U32* unsortedMark = bt + 2*(matchIndex&btMask) + 1; in ZSTD_DUBT_findBestMatch()
255 U32 nbCompares = 1U << cParams->searchLog; in ZSTD_DUBT_findBestMatch()
256 U32 nbCandidates = nbCompares; in ZSTD_DUBT_findBestMatch()
257 U32 previousCandidate = 0; in ZSTD_DUBT_findBestMatch()
289 U32* const nextCandidateIdxPtr = bt + 2*(matchIndex&btMask) + 1; in ZSTD_DUBT_findBestMatch()
290 U32 const nextCandidateIdx = *nextCandidateIdxPtr; in ZSTD_DUBT_findBestMatch()
300 const U32 dictLimit = ms->window.dictLimit; in ZSTD_DUBT_findBestMatch()
303 U32* smallerPtr = bt + 2*(curr&btMask); in ZSTD_DUBT_findBestMatch()
304 U32* largerPtr = bt + 2*(curr&btMask) + 1; in ZSTD_DUBT_findBestMatch()
305 U32 matchEndIdx = curr + 8 + 1; in ZSTD_DUBT_findBestMatch()
306 U32 dummy32; /* to be nullified at the end */ in ZSTD_DUBT_findBestMatch()
313 U32* const nextPtr = bt + 2*(matchIndex & btMask); in ZSTD_DUBT_findBestMatch()
329 matchEndIdx = matchIndex + (U32)matchLength; in ZSTD_DUBT_findBestMatch()
330 …gth-bestLength)) > (int)(ZSTD_highbit32(curr-matchIndex+1) - ZSTD_highbit32((U32)offsetPtr[0]+1)) ) in ZSTD_DUBT_findBestMatch()
371 U32 const mIndex = curr - (U32)STORED_OFFSET(*offsetPtr); (void)mIndex; in ZSTD_DUBT_findBestMatch()
373 curr, (U32)bestLength, (U32)*offsetPtr, mIndex); in ZSTD_DUBT_findBestMatch()
385 const U32 mls /* template */, in ZSTD_BtFindBestMatch()
401 U32 const target = (U32)(ip - base); in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
402 U32* const hashTable = ms->hashTable; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
403 U32* const chainTable = ms->chainTable; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
404 U32 const chainSize = 1 << ms->cParams.chainLog; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
405 U32 idx = ms->nextToUpdate; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
406 U32 const minChain = chainSize < target - idx ? target - chainSize : idx; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
407 U32 const bucketSize = 1 << ZSTD_LAZY_DDSS_BUCKET_LOG; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
408 U32 const cacheSize = bucketSize - 1; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
409 U32 const chainAttempts = (1 << ms->cParams.searchLog) - cacheSize; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
410 U32 const chainLimit = chainAttempts > 255 ? 255 : chainAttempts; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
417 U32 const hashLog = ms->cParams.hashLog - ZSTD_LAZY_DDSS_BUCKET_LOG; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
418 U32* const tmpHashTable = hashTable; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
419 U32* const tmpChainTable = hashTable + ((size_t)1 << hashLog); in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
420 U32 const tmpChainSize = (U32)((1 << ZSTD_LAZY_DDSS_BUCKET_LOG) - 1) << hashLog; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
421 U32 const tmpMinChain = tmpChainSize < target ? target - tmpChainSize : idx; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
422 U32 hashIdx; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
431 U32 const h = (U32)ZSTD_hashPtr(base + idx, hashLog, ms->cParams.minMatch); in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
440 U32 chainPos = 0; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
442 U32 count; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
443 U32 countBeyondMinChain = 0; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
444 U32 i = tmpHashTable[hashIdx]; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
489 U32 const bucketIdx = --hashIdx << ZSTD_LAZY_DDSS_BUCKET_LOG; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
490 U32 const chainPackedPointer = tmpHashTable[hashIdx]; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
491 U32 i; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
500 U32 const h = (U32)ZSTD_hashPtr(base + idx, hashLog, ms->cParams.minMatch) in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
502 U32 i; in ZSTD_dedicatedDictSearch_lazy_loadDictionary()
516 size_t ZSTD_dedicatedDictSearch_lazy_search(size_t* offsetPtr, size_t ml, U32 nbAttempts, in ZSTD_dedicatedDictSearch_lazy_search()
519 const BYTE* const prefixStart, const U32 curr, in ZSTD_dedicatedDictSearch_lazy_search()
520 const U32 dictLimit, const size_t ddsIdx) { in ZSTD_dedicatedDictSearch_lazy_search()
521 const U32 ddsLowestIndex = dms->window.dictLimit; in ZSTD_dedicatedDictSearch_lazy_search()
524 const U32 ddsSize = (U32)(ddsEnd - ddsBase); in ZSTD_dedicatedDictSearch_lazy_search()
525 const U32 ddsIndexDelta = dictLimit - ddsSize; in ZSTD_dedicatedDictSearch_lazy_search()
526 const U32 bucketSize = (1 << ZSTD_LAZY_DDSS_BUCKET_LOG); in ZSTD_dedicatedDictSearch_lazy_search()
527 const U32 bucketLimit = nbAttempts < bucketSize - 1 ? nbAttempts : bucketSize - 1; in ZSTD_dedicatedDictSearch_lazy_search()
528 U32 ddsAttempt; in ZSTD_dedicatedDictSearch_lazy_search()
529 U32 matchIndex; in ZSTD_dedicatedDictSearch_lazy_search()
536 U32 const chainPackedPointer = dms->hashTable[ddsIdx + bucketSize - 1]; in ZSTD_dedicatedDictSearch_lazy_search()
537 U32 const chainIndex = chainPackedPointer >> 8; in ZSTD_dedicatedDictSearch_lazy_search()
573 U32 const chainPackedPointer = dms->hashTable[ddsIdx + bucketSize - 1]; in ZSTD_dedicatedDictSearch_lazy_search()
574 U32 chainIndex = chainPackedPointer >> 8; in ZSTD_dedicatedDictSearch_lazy_search()
575 U32 const chainLength = chainPackedPointer & 0xFF; in ZSTD_dedicatedDictSearch_lazy_search()
576 U32 const chainAttempts = nbAttempts - ddsAttempt; in ZSTD_dedicatedDictSearch_lazy_search()
577 U32 const chainLimit = chainAttempts > chainLength ? chainLength : chainAttempts; in ZSTD_dedicatedDictSearch_lazy_search()
578 U32 chainAttempt; in ZSTD_dedicatedDictSearch_lazy_search()
617 FORCE_INLINE_TEMPLATE U32 ZSTD_insertAndFindFirstIndex_internal( in ZSTD_insertAndFindFirstIndex_internal()
620 const BYTE* ip, U32 const mls) in ZSTD_insertAndFindFirstIndex_internal()
622 U32* const hashTable = ms->hashTable; in ZSTD_insertAndFindFirstIndex_internal()
623 const U32 hashLog = cParams->hashLog; in ZSTD_insertAndFindFirstIndex_internal()
624 U32* const chainTable = ms->chainTable; in ZSTD_insertAndFindFirstIndex_internal()
625 const U32 chainMask = (1 << cParams->chainLog) - 1; in ZSTD_insertAndFindFirstIndex_internal()
627 const U32 target = (U32)(ip - base); in ZSTD_insertAndFindFirstIndex_internal()
628 U32 idx = ms->nextToUpdate; in ZSTD_insertAndFindFirstIndex_internal()
641 U32 ZSTD_insertAndFindFirstIndex(ZSTD_matchState_t* ms, const BYTE* ip) { in ZSTD_insertAndFindFirstIndex()
652 const U32 mls, const ZSTD_dictMode_e dictMode) in ZSTD_HcFindBestMatch()
655 U32* const chainTable = ms->chainTable; in ZSTD_HcFindBestMatch()
656 const U32 chainSize = (1 << cParams->chainLog); in ZSTD_HcFindBestMatch()
657 const U32 chainMask = chainSize-1; in ZSTD_HcFindBestMatch()
660 const U32 dictLimit = ms->window.dictLimit; in ZSTD_HcFindBestMatch()
663 const U32 curr = (U32)(ip-base); in ZSTD_HcFindBestMatch()
664 const U32 maxDistance = 1U << cParams->windowLog; in ZSTD_HcFindBestMatch()
665 const U32 lowestValid = ms->window.lowLimit; in ZSTD_HcFindBestMatch()
666 …const U32 withinMaxDistance = (curr - lowestValid > maxDistance) ? curr - maxDistance : lowestVali… in ZSTD_HcFindBestMatch()
667 const U32 isDictionary = (ms->loadedDictEnd != 0); in ZSTD_HcFindBestMatch()
668 const U32 lowLimit = isDictionary ? lowestValid : withinMaxDistance; in ZSTD_HcFindBestMatch()
669 const U32 minChain = curr > chainSize ? curr - chainSize : 0; in ZSTD_HcFindBestMatch()
670 U32 nbAttempts = 1U << cParams->searchLog; in ZSTD_HcFindBestMatch()
674 const U32 ddsHashLog = dictMode == ZSTD_dedicatedDictSearch in ZSTD_HcFindBestMatch()
679 U32 matchIndex; in ZSTD_HcFindBestMatch()
682 const U32* entry = &dms->hashTable[ddsIdx]; in ZSTD_HcFindBestMatch()
719 const U32* const dmsChainTable = dms->chainTable; in ZSTD_HcFindBestMatch()
720 const U32 dmsChainSize = (1 << dms->cParams.chainLog); in ZSTD_HcFindBestMatch()
721 const U32 dmsChainMask = dmsChainSize - 1; in ZSTD_HcFindBestMatch()
722 const U32 dmsLowestIndex = dms->window.dictLimit; in ZSTD_HcFindBestMatch()
725 const U32 dmsSize = (U32)(dmsEnd - dmsBase); in ZSTD_HcFindBestMatch()
726 const U32 dmsIndexDelta = dictLimit - dmsSize; in ZSTD_HcFindBestMatch()
727 const U32 dmsMinChain = dmsSize > dmsChainSize ? dmsSize - dmsChainSize : 0; in ZSTD_HcFindBestMatch()
772 static U32 ZSTD_VecMask_next(ZSTD_VecMask val) { in ZSTD_VecMask_next()
776 U32 mostSignificantWord = (U32)(val >> 32); in ZSTD_VecMask_next()
777 U32 leastSignificantWord = (U32)val; in ZSTD_VecMask_next()
779 return 32 + (U32)__builtin_ctz(mostSignificantWord); in ZSTD_VecMask_next()
781 return (U32)__builtin_ctz(leastSignificantWord); in ZSTD_VecMask_next()
784 return (U32)__builtin_ctzll(val); in ZSTD_VecMask_next()
793 return (U32)((((val + (val >> 4)) & 0xF0F0F0F0F0F0F0FULL) * 0x101010101010101ULL) >> 56); in ZSTD_VecMask_next()
802 U64 ZSTD_rotateRight_U64(U64 const value, U32 count) { in ZSTD_rotateRight_U64()
809 U32 ZSTD_rotateRight_U32(U32 const value, U32 count) { in ZSTD_rotateRight_U32()
812 return (value >> count) | (U32)(value << ((0U - count) & 0x1F)); in ZSTD_rotateRight_U32()
816 U16 ZSTD_rotateRight_U16(U16 const value, U32 count) { in ZSTD_rotateRight_U16()
826 FORCE_INLINE_TEMPLATE U32 ZSTD_row_nextIndex(BYTE* const tagRow, U32 const rowMask) { in ZSTD_row_nextIndex()
827 U32 const next = (*tagRow - 1) & rowMask; in ZSTD_row_nextIndex()
843 …ORCE_INLINE_TEMPLATE void ZSTD_row_prefetch(U32 const* hashTable, U16 const* tagTable, U32 const r… in ZSTD_row_prefetch()
863 U32 const rowLog, U32 const mls, in ZSTD_row_fillHashCache()
864 U32 idx, const BYTE* const iLimit) in ZSTD_row_fillHashCache()
866 U32 const* const hashTable = ms->hashTable; in ZSTD_row_fillHashCache()
868 U32 const hashLog = ms->rowHashLog; in ZSTD_row_fillHashCache()
869 U32 const maxElemsToPrefetch = (base + idx) > iLimit ? 0 : (U32)(iLimit - (base + idx) + 1); in ZSTD_row_fillHashCache()
870 U32 const lim = idx + MIN(ZSTD_ROW_HASH_CACHE_SIZE, maxElemsToPrefetch); in ZSTD_row_fillHashCache()
873 U32 const hash = (U32)ZSTD_hashPtr(base + idx, hashLog + ZSTD_ROW_HASH_TAG_BITS, mls); in ZSTD_row_fillHashCache()
874 U32 const row = (hash >> ZSTD_ROW_HASH_TAG_BITS) << rowLog; in ZSTD_row_fillHashCache()
888 FORCE_INLINE_TEMPLATE U32 ZSTD_row_nextCachedHash(U32* cache, U32 const* hashTable, in ZSTD_row_nextCachedHash()
890 U32 idx, U32 const hashLog, in ZSTD_row_nextCachedHash()
891 U32 const rowLog, U32 const mls) in ZSTD_row_nextCachedHash()
893 …U32 const newHash = (U32)ZSTD_hashPtr(base+idx+ZSTD_ROW_HASH_CACHE_SIZE, hashLog + ZSTD_ROW_HASH_T… in ZSTD_row_nextCachedHash()
894 U32 const row = (newHash >> ZSTD_ROW_HASH_TAG_BITS) << rowLog; in ZSTD_row_nextCachedHash()
896 { U32 const hash = cache[idx & ZSTD_ROW_HASH_CACHE_MASK]; in ZSTD_row_nextCachedHash()
906 U32 updateStartIdx, U32 const updateEndIdx, in ZSTD_row_update_internalImpl()
907 U32 const mls, U32 const rowLog, in ZSTD_row_update_internalImpl()
908 U32 const rowMask, U32 const useCache) in ZSTD_row_update_internalImpl()
910 U32* const hashTable = ms->hashTable; in ZSTD_row_update_internalImpl()
912 U32 const hashLog = ms->rowHashLog; in ZSTD_row_update_internalImpl()
917 …U32 const hash = useCache ? ZSTD_row_nextCachedHash(ms->hashCache, hashTable, tagTable, base, upda… in ZSTD_row_update_internalImpl()
918 … : (U32)ZSTD_hashPtr(base + updateStartIdx, hashLog + ZSTD_ROW_HASH_TAG_BITS, mls); in ZSTD_row_update_internalImpl()
919 U32 const relRow = (hash >> ZSTD_ROW_HASH_TAG_BITS) << rowLog; in ZSTD_row_update_internalImpl()
920 U32* const row = hashTable + relRow; in ZSTD_row_update_internalImpl()
923 U32 const pos = ZSTD_row_nextIndex(tagRow, rowMask); in ZSTD_row_update_internalImpl()
936 U32 const mls, U32 const rowLog, in ZSTD_row_update_internal()
937 U32 const rowMask, U32 const useCache) in ZSTD_row_update_internal()
939 U32 idx = ms->nextToUpdate; in ZSTD_row_update_internal()
941 const U32 target = (U32)(ip - base); in ZSTD_row_update_internal()
942 const U32 kSkipThreshold = 384; in ZSTD_row_update_internal()
943 const U32 kMaxMatchStartPositionsToUpdate = 96; in ZSTD_row_update_internal()
944 const U32 kMaxMatchEndPositionsToUpdate = 32; in ZSTD_row_update_internal()
953 U32 const bound = idx + kMaxMatchStartPositionsToUpdate; in ZSTD_row_update_internal()
969 const U32 rowLog = BOUNDED(4, ms->cParams.searchLog, 6); in ZSTD_row_update()
970 const U32 rowMask = (1u << rowLog) - 1; in ZSTD_row_update()
971 const U32 mls = MIN(ms->cParams.minMatch, 6 /* mls caps out at 6 */); in ZSTD_row_update()
979 ZSTD_row_getSSEMask(int nbChunks, const BYTE* const src, const BYTE tag, const U32 head) in ZSTD_row_getSSEMask()
991 if (nbChunks == 2) return ZSTD_rotateRight_U32((U32)matches[1] << 16 | (U32)matches[0], head); in ZSTD_row_getSSEMask()
1002 ZSTD_row_getMatchMask(const BYTE* const tagRow, const BYTE tag, const U32 head, const U32 rowEntrie… in ZSTD_row_getMatchMask()
1040 const U32 matches = vget_lane_u32(vreinterpret_u32_u8(t4), 0); in ZSTD_row_getMatchMask()
1096 return ZSTD_rotateRight_U32((U32)matches, head); in ZSTD_row_getMatchMask()
1124 const U32 mls, const ZSTD_dictMode_e dictMode, in ZSTD_RowFindBestMatch()
1125 const U32 rowLog) in ZSTD_RowFindBestMatch()
1127 U32* const hashTable = ms->hashTable; in ZSTD_RowFindBestMatch()
1129 U32* const hashCache = ms->hashCache; in ZSTD_RowFindBestMatch()
1130 const U32 hashLog = ms->rowHashLog; in ZSTD_RowFindBestMatch()
1134 const U32 dictLimit = ms->window.dictLimit; in ZSTD_RowFindBestMatch()
1137 const U32 curr = (U32)(ip-base); in ZSTD_RowFindBestMatch()
1138 const U32 maxDistance = 1U << cParams->windowLog; in ZSTD_RowFindBestMatch()
1139 const U32 lowestValid = ms->window.lowLimit; in ZSTD_RowFindBestMatch()
1140 …const U32 withinMaxDistance = (curr - lowestValid > maxDistance) ? curr - maxDistance : lowestVali… in ZSTD_RowFindBestMatch()
1141 const U32 isDictionary = (ms->loadedDictEnd != 0); in ZSTD_RowFindBestMatch()
1142 const U32 lowLimit = isDictionary ? lowestValid : withinMaxDistance; in ZSTD_RowFindBestMatch()
1143 const U32 rowEntries = (1U << rowLog); in ZSTD_RowFindBestMatch()
1144 const U32 rowMask = rowEntries - 1; in ZSTD_RowFindBestMatch()
1145 …const U32 cappedSearchLog = MIN(cParams->searchLog, rowLog); /* nb of searches is capped at nb ent… in ZSTD_RowFindBestMatch()
1146 U32 nbAttempts = 1U << cappedSearchLog; in ZSTD_RowFindBestMatch()
1154 …U32 ddsExtraAttempts = 0; /* cctx hash tables are limited in searches, but allow extra searches in… in ZSTD_RowFindBestMatch()
1155 U32 dmsTag = 0; in ZSTD_RowFindBestMatch()
1156 U32* dmsRow = NULL; in ZSTD_RowFindBestMatch()
1160 const U32 ddsHashLog = dms->cParams.hashLog - ZSTD_LAZY_DDSS_BUCKET_LOG; in ZSTD_RowFindBestMatch()
1170 U32* const dmsHashTable = dms->hashTable; in ZSTD_RowFindBestMatch()
1172 U32 const dmsHash = (U32)ZSTD_hashPtr(ip, dms->rowHashLog + ZSTD_ROW_HASH_TAG_BITS, mls); in ZSTD_RowFindBestMatch()
1173 U32 const dmsRelRow = (dmsHash >> ZSTD_ROW_HASH_TAG_BITS) << rowLog; in ZSTD_RowFindBestMatch()
1183 …U32 const hash = ZSTD_row_nextCachedHash(hashCache, hashTable, tagTable, base, curr, hashLog, rowL… in ZSTD_RowFindBestMatch()
1184 U32 const relRow = (hash >> ZSTD_ROW_HASH_TAG_BITS) << rowLog; in ZSTD_RowFindBestMatch()
1185 U32 const tag = hash & ZSTD_ROW_HASH_TAG_MASK; in ZSTD_RowFindBestMatch()
1186 U32* const row = hashTable + relRow; in ZSTD_RowFindBestMatch()
1188 U32 const head = *tagRow & rowMask; in ZSTD_RowFindBestMatch()
1189 U32 matchBuffer[ZSTD_ROW_HASH_MAX_ENTRIES]; in ZSTD_RowFindBestMatch()
1196 U32 const matchPos = (head + ZSTD_VecMask_next(matches)) & rowMask; in ZSTD_RowFindBestMatch()
1197 U32 const matchIndex = row[matchPos]; in ZSTD_RowFindBestMatch()
1212 U32 const pos = ZSTD_row_nextIndex(tagRow, rowMask); in ZSTD_RowFindBestMatch()
1219 U32 const matchIndex = matchBuffer[currMatch]; in ZSTD_RowFindBestMatch()
1251 const U32 dmsLowestIndex = dms->window.dictLimit; in ZSTD_RowFindBestMatch()
1254 const U32 dmsSize = (U32)(dmsEnd - dmsBase); in ZSTD_RowFindBestMatch()
1255 const U32 dmsIndexDelta = dictLimit - dmsSize; in ZSTD_RowFindBestMatch()
1257 { U32 const head = *dmsTagRow & rowMask; in ZSTD_RowFindBestMatch()
1258 U32 matchBuffer[ZSTD_ROW_HASH_MAX_ENTRIES]; in ZSTD_RowFindBestMatch()
1264 U32 const matchPos = (head + ZSTD_VecMask_next(matches)) & rowMask; in ZSTD_RowFindBestMatch()
1265 U32 const matchIndex = dmsRow[matchPos]; in ZSTD_RowFindBestMatch()
1274 U32 const matchIndex = matchBuffer[currMatch]; in ZSTD_RowFindBestMatch()
1453 U32 const mls, in ZSTD_searchMax()
1454 U32 const rowLog, in ZSTD_searchMax()
1478 U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_generic()
1480 const searchMethod_e searchMethod, const U32 depth, in ZSTD_compressBlock_lazy_generic()
1489 const U32 prefixLowestIndex = ms->window.dictLimit; in ZSTD_compressBlock_lazy_generic()
1491 const U32 mls = BOUNDED(4, ms->cParams.minMatch, 6); in ZSTD_compressBlock_lazy_generic()
1492 const U32 rowLog = BOUNDED(4, ms->cParams.searchLog, 6); in ZSTD_compressBlock_lazy_generic()
1494 U32 offset_1 = rep[0], offset_2 = rep[1], savedOffset=0; in ZSTD_compressBlock_lazy_generic()
1500 const U32 dictLowestIndex = isDxS ? dms->window.dictLimit : 0; in ZSTD_compressBlock_lazy_generic()
1504 const U32 dictIndexDelta = isDxS ? in ZSTD_compressBlock_lazy_generic()
1505 prefixLowestIndex - (U32)(dictEnd - dictBase) : in ZSTD_compressBlock_lazy_generic()
1507 const U32 dictAndPrefixLength = (U32)((ip - prefixLowest) + (dictEnd - dictLowest)); in ZSTD_compressBlock_lazy_generic()
1509 … "ZSTD_compressBlock_lazy_generic (dictMode=%u) (searchFunc=%u)", (U32)dictMode, (U32)searchMethod… in ZSTD_compressBlock_lazy_generic()
1512 U32 const curr = (U32)(ip - base); in ZSTD_compressBlock_lazy_generic()
1513 U32 const windowLow = ZSTD_getLowestPrefixIndex(ms, curr, ms->cParams.windowLog); in ZSTD_compressBlock_lazy_generic()
1514 U32 const maxRep = curr - windowLow; in ZSTD_compressBlock_lazy_generic()
1546 const U32 repIndex = (U32)(ip - base) + 1 - offset_1; in ZSTD_compressBlock_lazy_generic()
1551 if (((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */) in ZSTD_compressBlock_lazy_generic()
1585 … int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offcode)) + 1); in ZSTD_compressBlock_lazy_generic()
1590 const U32 repIndex = (U32)(ip - base) - offset_1; in ZSTD_compressBlock_lazy_generic()
1594 if (((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */) in ZSTD_compressBlock_lazy_generic()
1599 … int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offcode)) + 1); in ZSTD_compressBlock_lazy_generic()
1606 …int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offset2))); /* raw approx … in ZSTD_compressBlock_lazy_generic()
1607 … int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offcode)) + 4); in ZSTD_compressBlock_lazy_generic()
1621 … int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offcode)) + 1); in ZSTD_compressBlock_lazy_generic()
1626 const U32 repIndex = (U32)(ip - base) - offset_1; in ZSTD_compressBlock_lazy_generic()
1630 if (((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */) in ZSTD_compressBlock_lazy_generic()
1635 … int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offcode)) + 1); in ZSTD_compressBlock_lazy_generic()
1642 …int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offset2))); /* raw approx … in ZSTD_compressBlock_lazy_generic()
1643 … int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offcode)) + 7); in ZSTD_compressBlock_lazy_generic()
1663 U32 const matchIndex = (U32)((size_t)(start-base) - STORED_OFFSET(offcode)); in ZSTD_compressBlock_lazy_generic()
1668 offset_2 = offset_1; offset_1 = (U32)STORED_OFFSET(offcode); in ZSTD_compressBlock_lazy_generic()
1673 ZSTD_storeSeq(seqStore, litLength, anchor, iend, (U32)offcode, matchLength); in ZSTD_compressBlock_lazy_generic()
1680 U32 const current2 = (U32)(ip-base); in ZSTD_compressBlock_lazy_generic()
1681 U32 const repIndex = current2 - offset_2; in ZSTD_compressBlock_lazy_generic()
1685 if ( ((U32)((prefixLowestIndex-1) - (U32)repIndex) >= 3 /* intentional overflow */) in ZSTD_compressBlock_lazy_generic()
1689 …offcode = offset_2; offset_2 = offset_1; offset_1 = (U32)offcode; /* swap offset_2 <=> offset_1 … in ZSTD_compressBlock_lazy_generic()
1704 … offcode = offset_2; offset_2 = offset_1; offset_1 = (U32)offcode; /* swap repcodes */ in ZSTD_compressBlock_lazy_generic()
1721 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btlazy2()
1728 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2()
1735 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy()
1742 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy()
1749 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btlazy2_dictMatchState()
1756 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_dictMatchState()
1763 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_dictMatchState()
1770 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_dictMatchState()
1778 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_dedicatedDictSearch()
1785 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_dedicatedDictSearch()
1792 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_dedicatedDictSearch()
1800 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_row()
1807 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_row()
1814 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_row()
1821 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_dictMatchState_row()
1828 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_dictMatchState_row()
1835 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_dictMatchState_row()
1843 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_dedicatedDictSearch_row()
1850 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_dedicatedDictSearch_row()
1857 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_dedicatedDictSearch_row()
1866 U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_extDict_generic()
1868 const searchMethod_e searchMethod, const U32 depth) in ZSTD_compressBlock_lazy_extDict_generic()
1876 const U32 dictLimit = ms->window.dictLimit; in ZSTD_compressBlock_lazy_extDict_generic()
1881 const U32 windowLog = ms->cParams.windowLog; in ZSTD_compressBlock_lazy_extDict_generic()
1882 const U32 mls = BOUNDED(4, ms->cParams.minMatch, 6); in ZSTD_compressBlock_lazy_extDict_generic()
1883 const U32 rowLog = BOUNDED(4, ms->cParams.searchLog, 6); in ZSTD_compressBlock_lazy_extDict_generic()
1885 U32 offset_1 = rep[0], offset_2 = rep[1]; in ZSTD_compressBlock_lazy_extDict_generic()
1887 DEBUGLOG(5, "ZSTD_compressBlock_lazy_extDict_generic (searchFunc=%u)", (U32)searchMethod); in ZSTD_compressBlock_lazy_extDict_generic()
1908 U32 curr = (U32)(ip-base); in ZSTD_compressBlock_lazy_extDict_generic()
1911 { const U32 windowLow = ZSTD_getLowestMatchIndex(ms, curr+1, windowLog); in ZSTD_compressBlock_lazy_extDict_generic()
1912 const U32 repIndex = (U32)(curr+1 - offset_1); in ZSTD_compressBlock_lazy_extDict_generic()
1915 if ( ((U32)((dictLimit-1) - repIndex) >= 3) /* intentional overflow */ in ZSTD_compressBlock_lazy_extDict_generic()
1943 const U32 windowLow = ZSTD_getLowestMatchIndex(ms, curr, windowLog); in ZSTD_compressBlock_lazy_extDict_generic()
1944 const U32 repIndex = (U32)(curr - offset_1); in ZSTD_compressBlock_lazy_extDict_generic()
1947 …if ( ((U32)((dictLimit-1) - repIndex) >= 3) /* intentional overflow : do not test positions overla… in ZSTD_compressBlock_lazy_extDict_generic()
1954 … int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offcode)) + 1); in ZSTD_compressBlock_lazy_extDict_generic()
1962 …int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offset2))); /* raw approx … in ZSTD_compressBlock_lazy_extDict_generic()
1963 … int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offcode)) + 4); in ZSTD_compressBlock_lazy_extDict_generic()
1975 const U32 windowLow = ZSTD_getLowestMatchIndex(ms, curr, windowLog); in ZSTD_compressBlock_lazy_extDict_generic()
1976 const U32 repIndex = (U32)(curr - offset_1); in ZSTD_compressBlock_lazy_extDict_generic()
1979 …if ( ((U32)((dictLimit-1) - repIndex) >= 3) /* intentional overflow : do not test positions overla… in ZSTD_compressBlock_lazy_extDict_generic()
1986 … int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offcode)) + 1); in ZSTD_compressBlock_lazy_extDict_generic()
1994 …int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offset2))); /* raw approx … in ZSTD_compressBlock_lazy_extDict_generic()
1995 … int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)STORED_TO_OFFBASE(offcode)) + 7); in ZSTD_compressBlock_lazy_extDict_generic()
2005 U32 const matchIndex = (U32)((size_t)(start-base) - STORED_OFFSET(offcode)); in ZSTD_compressBlock_lazy_extDict_generic()
2009 offset_2 = offset_1; offset_1 = (U32)STORED_OFFSET(offcode); in ZSTD_compressBlock_lazy_extDict_generic()
2015 ZSTD_storeSeq(seqStore, litLength, anchor, iend, (U32)offcode, matchLength); in ZSTD_compressBlock_lazy_extDict_generic()
2021 const U32 repCurrent = (U32)(ip-base); in ZSTD_compressBlock_lazy_extDict_generic()
2022 const U32 windowLow = ZSTD_getLowestMatchIndex(ms, repCurrent, windowLog); in ZSTD_compressBlock_lazy_extDict_generic()
2023 const U32 repIndex = repCurrent - offset_2; in ZSTD_compressBlock_lazy_extDict_generic()
2026 …if ( ((U32)((dictLimit-1) - repIndex) >= 3) /* intentional overflow : do not test positions overla… in ZSTD_compressBlock_lazy_extDict_generic()
2032 … offcode = offset_2; offset_2 = offset_1; offset_1 = (U32)offcode; /* swap offset history */ in ZSTD_compressBlock_lazy_extDict_generic()
2051 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_extDict()
2058 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_extDict()
2066 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_extDict()
2074 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btlazy2_extDict()
2082 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_greedy_extDict_row()
2089 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy_extDict_row()
2097 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_lazy2_extDict_row()