Lines Matching refs:U32
40 MEM_STATIC U32 ZSTD_bitWeight(U32 stat)
45 MEM_STATIC U32 ZSTD_fracWeight(U32 rawStat)
47 U32 const stat = rawStat + 1;
48 U32 const hb = ZSTD_highbit32(stat);
49 U32 const BWeight = hb * BITCOST_MULTIPLIER;
50 U32 const FWeight = (stat << BITCOST_ACCURACY) >> hb;
51 U32 const weight = BWeight + FWeight;
60 MEM_STATIC double ZSTD_fCost(U32 price)
81 static U32 sum_u32(const unsigned table[], size_t nbElts)
84 U32 total = 0;
91 static U32 ZSTD_downscaleStats(unsigned* table, U32 lastEltIndex, U32 shift)
93 U32 s, sum=0;
106 static U32 ZSTD_scaleStats(unsigned* table, U32 lastEltIndex, U32 logTarget)
108 U32 const prevsum = sum_u32(table, lastEltIndex+1);
109 U32 const factor = prevsum >> logTarget;
148 U32 const scaleLog = 11; /* scale to 2K */
149 U32 const bitCost = HUF_getNbBitsFromCTable(optPtr->symbolCosts->huf.CTable, lit);
160 U32 const scaleLog = 10; /* scale to 1K */
161 U32 const bitCost = FSE_getMaxNbBits(llstate.symbolTT, ll);
172 U32 const scaleLog = 10;
173 U32 const bitCost = FSE_getMaxNbBits(mlstate.symbolTT, ml);
184 U32 const scaleLog = 10;
185 U32 const bitCost = FSE_getMaxNbBits(ofstate.symbolTT, of);
245 static U32 ZSTD_rawLiteralsCost(const BYTE* const literals, U32 const litLength,
258 { U32 price = litLength * optPtr->litSumBasePrice;
259 U32 u;
270 static U32 ZSTD_litLengthPrice(U32 const litLength, const optState_t* const optPtr, int optLevel)
284 { U32 const llCode = ZSTD_LLcode(litLength);
297 FORCE_INLINE_TEMPLATE U32
298 ZSTD_getMatchPrice(U32 const offcode,
299 U32 const matchLength,
303 U32 price;
304 U32 const offCode = ZSTD_highbit32(STORED_TO_OFFBASE(offcode));
305 U32 const mlBase = matchLength - MINMATCH;
317 { U32 const mlCode = ZSTD_MLcode(mlBase);
330 U32 litLength, const BYTE* literals,
331 U32 offsetCode, U32 matchLength)
335 U32 u;
342 { U32 const llCode = ZSTD_LLcode(litLength);
348 { U32 const offCode = ZSTD_highbit32(STORED_TO_OFFBASE(offsetCode));
355 { U32 const mlBase = matchLength - MINMATCH;
356 U32 const mlCode = ZSTD_MLcode(mlBase);
366 MEM_STATIC U32 ZSTD_readMINMATCH(const void* memPtr, U32 length)
382 static U32 ZSTD_insertAndFindFirstIndexHash3 (const ZSTD_matchState_t* ms,
383 U32* nextToUpdate3,
386 U32* const hashTable3 = ms->hashTable3;
387 U32 const hashLog3 = ms->hashLog3;
389 U32 idx = *nextToUpdate3;
390 U32 const target = (U32)(ip - base);
411 static U32 ZSTD_insertBt1(
414 U32 const target,
415 U32 const mls, const int extDict)
418 U32* const hashTable = ms->hashTable;
419 U32 const hashLog = cParams->hashLog;
421 U32* const bt = ms->chainTable;
422 U32 const btLog = cParams->chainLog - 1;
423 U32 const btMask = (1 << btLog) - 1;
424 U32 matchIndex = hashTable[h];
428 const U32 dictLimit = ms->window.dictLimit;
432 const U32 curr = (U32)(ip-base);
433 const U32 btLow = btMask >= curr ? 0 : curr - btMask;
434 U32* smallerPtr = bt + 2*(curr&btMask);
435 U32* largerPtr = smallerPtr + 1;
436 U32 dummy32; /* to be nullified at the end */
440 U32 const windowLow = ZSTD_getLowestMatchIndex(ms, target, cParams->windowLog);
441 U32 matchEndIdx = curr+8+1;
443 U32 nbCompares = 1U << cParams->searchLog;
445 U32 predictedSmall = *(bt + 2*((curr-1)&btMask) + 0);
446 U32 predictedLarge = *(bt + 2*((curr-1)&btMask) + 1);
459 U32* const nextPtr = bt + 2*(matchIndex & btMask);
464 const U32* predictPtr = bt + 2*((matchIndex-1) & btMask); /* written this way, as bt is a roll buffer */
498 matchEndIdx = matchIndex + (U32)matchLength;
522 { U32 positions = 0;
523 if (bestLength > 384) positions = MIN(192, (U32)(bestLength - 384)); /* speed optimization */
533 const U32 mls, const ZSTD_dictMode_e dictMode)
536 U32 const target = (U32)(ip - base);
537 U32 idx = ms->nextToUpdate;
542 U32 const forward = ZSTD_insertBt1(ms, base+idx, iend, target, mls, dictMode == ZSTD_extDict);
543 assert(idx < (U32)(idx + forward));
546 assert((size_t)(ip - base) <= (size_t)(U32)(-1));
547 assert((size_t)(iend - base) <= (size_t)(U32)(-1));
556 U32 ZSTD_insertBtAndGetAllMatches (
559 U32* nextToUpdate3,
561 const U32 rep[ZSTD_REP_NUM],
562 U32 const ll0, /* tells if associated literal length is 0 or not. This value must be 0 or 1 */
563 const U32 lengthToBeat,
564 U32 const mls /* template */)
567 U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1);
569 U32 const curr = (U32)(ip-base);
570 U32 const hashLog = cParams->hashLog;
571 U32 const minMatch = (mls==3) ? 3 : 4;
572 U32* const hashTable = ms->hashTable;
574 U32 matchIndex = hashTable[h];
575 U32* const bt = ms->chainTable;
576 U32 const btLog = cParams->chainLog - 1;
577 U32 const btMask= (1U << btLog) - 1;
580 U32 const dictLimit = ms->window.dictLimit;
583 U32 const btLow = (btMask >= curr) ? 0 : curr - btMask;
584 U32 const windowLow = ZSTD_getLowestMatchIndex(ms, curr, cParams->windowLog);
585 U32 const matchLow = windowLow ? windowLow : 1;
586 U32* smallerPtr = bt + 2*(curr&btMask);
587 U32* largerPtr = bt + 2*(curr&btMask) + 1;
588 U32 matchEndIdx = curr+8+1; /* farthest referenced position of any match => detects repetitive patterns */
589 U32 dummy32; /* to be nullified at the end */
590 U32 mnum = 0;
591 U32 nbCompares = 1U << cParams->searchLog;
598 U32 const dmsHighLimit = dictMode == ZSTD_dictMatchState ? (U32)(dmsEnd - dmsBase) : 0;
599 U32 const dmsLowLimit = dictMode == ZSTD_dictMatchState ? dms->window.lowLimit : 0;
600 U32 const dmsIndexDelta = dictMode == ZSTD_dictMatchState ? windowLow - dmsHighLimit : 0;
601 U32 const dmsHashLog = dictMode == ZSTD_dictMatchState ? dmsCParams->hashLog : hashLog;
602 U32 const dmsBtLog = dictMode == ZSTD_dictMatchState ? dmsCParams->chainLog - 1 : btLog;
603 U32 const dmsBtMask = dictMode == ZSTD_dictMatchState ? (1U << dmsBtLog) - 1 : 0;
604 U32 const dmsBtLow = dictMode == ZSTD_dictMatchState && dmsBtMask < dmsHighLimit - dmsLowLimit ? dmsHighLimit - dmsBtMask : dmsLowLimit;
611 { U32 const lastR = ZSTD_REP_NUM + ll0;
612 U32 repCode;
614 U32 const repOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode];
615 U32 const repIndex = curr - repOffset;
616 U32 repLen = 0;
623 repLen = (U32)ZSTD_count(ip+minMatch, ip+minMatch-repOffset, iLimit) + minMatch;
632 & (((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overlapping 2 memory segments */)
634 repLen = (U32)ZSTD_count_2segments(ip+minMatch, repMatch+minMatch, iLimit, dictEnd, prefixStart) + minMatch;
638 & ((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overlapping 2 memory segments */
640 repLen = (U32)ZSTD_count_2segments(ip+minMatch, repMatch+minMatch, iLimit, dmsEnd, prefixStart) + minMatch;
648 matches[mnum].len = (U32)repLen;
657 U32 const matchIndex3 = ZSTD_insertAndFindFirstIndexHash3(ms, nextToUpdate3, ip);
672 (U32)mlen);
677 matches[0].len = (U32)mlen;
690 U32* const nextPtr = bt + 2*(matchIndex & btMask);
710 (U32)matchLength, curr - matchIndex, STORE_OFFSET(curr - matchIndex));
713 matchEndIdx = matchIndex + (U32)matchLength;
716 matches[mnum].len = (U32)matchLength;
744 U32 dictMatchIndex = dms->hashTable[dmsH];
745 const U32* const dmsBt = dms->chainTable;
748 const U32* const nextPtr = dmsBt + 2*(dictMatchIndex & dmsBtMask);
758 (U32)matchLength, curr - matchIndex, STORE_OFFSET(curr - matchIndex));
760 matchEndIdx = matchIndex + (U32)matchLength;
763 matches[mnum].len = (U32)matchLength;
785 typedef U32 (*ZSTD_getAllMatchesFn)(
788 U32*,
791 const U32 rep[ZSTD_REP_NUM],
792 U32 const ll0,
793 U32 const lengthToBeat);
795 FORCE_INLINE_TEMPLATE U32 ZSTD_btGetAllMatches_internal(
798 U32* nextToUpdate3,
801 const U32 rep[ZSTD_REP_NUM],
802 U32 const ll0,
803 U32 const lengthToBeat,
805 const U32 mls)
818 static U32 ZSTD_BT_GET_ALL_MATCHES_FN(dictMode, mls)( \
821 U32* nextToUpdate3, \
824 const U32 rep[ZSTD_REP_NUM], \
825 U32 const ll0, \
826 U32 const lengthToBeat) \
859 U32 const mls = BOUNDED(3, ms->cParams.minMatch, 6);
860 assert((U32)dictMode < 3);
872 U32 startPosInBlock; /* Start position of the current match candidate */
873 U32 endPosInBlock; /* End position of the current match candidate */
874 U32 offset; /* Offset of the match candidate */
883 U32 currPos = (U32)(rawSeqStore->posInSequence + nbBytes);
904 ZSTD_opt_getNextMatchAndUpdateSeqStore(ZSTD_optLdm_t* optLdm, U32 currPosInBlock,
905 U32 blockBytesRemaining)
908 U32 currBlockEndPos;
909 U32 literalsBytesRemaining;
910 U32 matchBytesRemaining;
924 currSeq.litLength - (U32)optLdm->seqStore.posInSequence :
927 currSeq.matchLength - ((U32)optLdm->seqStore.posInSequence - currSeq.litLength) :
959 static void ZSTD_optLdm_maybeAddMatch(ZSTD_match_t* matches, U32* nbMatches,
960 const ZSTD_optLdm_t* optLdm, U32 currPosInBlock)
962 U32 const posDiff = currPosInBlock - optLdm->startPosInBlock;
964 U32 const candidateMatchLength = optLdm->endPosInBlock - optLdm->startPosInBlock - posDiff;
974 U32 const candidateOffCode = STORE_OFFSET(optLdm->offset);
988 ZSTD_match_t* matches, U32* nbMatches,
989 U32 currPosInBlock, U32 remainingBytes)
1001 U32 const posOvershoot = currPosInBlock - optLdm->endPosInBlock;
1014 static U32 ZSTD_totalLen(ZSTD_optimal_t sol)
1022 listStats(const U32* table, int lastEltID)
1039 U32 rep[ZSTD_REP_NUM],
1056 U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1);
1057 U32 const minMatch = (cParams->minMatch == 3) ? 3 : 4;
1058 U32 nextToUpdate3 = ms->nextToUpdate;
1067 ZSTD_opt_getNextMatchAndUpdateSeqStore(&optLdm, (U32)(ip-istart), (U32)(iend-ip));
1071 (U32)(ip - base), ms->window.dictLimit, ms->nextToUpdate);
1078 U32 cur, last_pos = 0;
1081 { U32 const litlen = (U32)(ip - anchor);
1082 U32 const ll0 = !litlen;
1083 U32 nbMatches = getAllMatches(matches, ms, &nextToUpdate3, ip, iend, rep, ll0, minMatch);
1085 (U32)(ip-istart), (U32)(iend - ip));
1089 { U32 i ; for (i=0; i<ZSTD_REP_NUM; i++) opt[0].rep[i] = rep[i]; }
1100 { U32 const maxML = matches[nbMatches-1].len;
1101 U32 const maxOffcode = matches[nbMatches-1].off;
1103 nbMatches, maxML, maxOffcode, (U32)(ip-prefixStart));
1118 { U32 const literalsPrice = (U32)opt[0].price + ZSTD_litLengthPrice(0, optStatePtr, optLevel);
1119 U32 pos;
1120 U32 matchNb;
1125 U32 const offcode = matches[matchNb].off;
1126 U32 const end = matches[matchNb].len;
1128 U32 const matchPrice = ZSTD_getMatchPrice(offcode, pos, optStatePtr, optLevel);
1129 U32 const sequencePrice = literalsPrice + matchPrice;
1148 { U32 const litlen = (opt[cur-1].mlen == 0) ? opt[cur-1].litlen + 1 : 1;
1177 U32 const prev = cur - opt[cur].mlen;
1196 { U32 const ll0 = (opt[cur].mlen != 0);
1197 U32 const litlen = (opt[cur].mlen == 0) ? opt[cur].litlen : 0;
1198 U32 const previousPrice = (U32)opt[cur].price;
1199 U32 const basePrice = previousPrice + ZSTD_litLengthPrice(0, optStatePtr, optLevel);
1200 U32 nbMatches = getAllMatches(matches, ms, &nextToUpdate3, inr, iend, opt[cur].rep, ll0, minMatch);
1201 U32 matchNb;
1204 (U32)(inr-istart), (U32)(iend-inr));
1211 { U32 const maxML = matches[nbMatches-1].len;
1228 U32 const offset = matches[matchNb].off;
1229 U32 const lastML = matches[matchNb].len;
1230 U32 const startML = (matchNb>0) ? matches[matchNb-1].len+1 : minMatch;
1231 U32 mlen;
1237 U32 const pos = cur + mlen;
1274 { U32 const storeEnd = cur + 1;
1275 U32 storeStart = storeEnd;
1276 U32 seqPos = cur;
1285 U32 const backDist = ZSTD_totalLen(opt[seqPos]);
1295 { U32 storePos;
1297 U32 const llen = opt[storePos].litlen;
1298 U32 const mlen = opt[storePos].mlen;
1299 U32 const offCode = opt[storePos].off;
1300 U32 const advance = llen + mlen;
1325 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1332 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1339 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1357 U32 rep[ZSTD_REP_NUM],
1360 U32 tmpRep[ZSTD_REP_NUM]; /* updated rep codes will sink here */
1374 ms->window.dictLimit += (U32)srcSize;
1381 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1389 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1392 U32 const curr = (U32)((const BYTE*)src - ms->window.base);
1417 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1424 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1431 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1438 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],