Lines Matching +full:1 +full:ms
17 #define ZSTD_MAX_PRICE (1<<30)
28 # define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
32 # define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
36 # define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
42 return (ZSTD_highbit32(stat+1) * BITCOST_MULTIPLIER); in ZSTD_bitWeight()
47 U32 const stat = rawStat + 1; in ZSTD_fracWeight()
94 …DEBUGLOG(5, "ZSTD_downscaleStats (nbElts=%u, shift=%u)", (unsigned)lastEltIndex+1, (unsigned)shift… in ZSTD_downscaleStats()
96 for (s=0; s<lastEltIndex+1; s++) { in ZSTD_downscaleStats()
97 table[s] = 1 + (table[s] >> shift); in ZSTD_downscaleStats()
108 U32 const prevsum = sum_u32(table, lastEltIndex+1); in ZSTD_scaleStats()
110 …DEBUGLOG(5, "ZSTD_scaleStats (nbElts=%u, target=%u)", (unsigned)lastEltIndex+1, (unsigned)logTarge… in ZSTD_scaleStats()
112 if (factor <= 1) return prevsum; in ZSTD_scaleStats()
151 … optPtr->litFreq[lit] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/; in ZSTD_rescaleFreqs()
160 U32 const scaleLog = 10; /* scale to 1K */ in ZSTD_rescaleFreqs()
163 … optPtr->litLengthFreq[ll] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/; in ZSTD_rescaleFreqs()
175 … optPtr->matchLengthFreq[ml] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/; in ZSTD_rescaleFreqs()
187 … optPtr->offCodeFreq[of] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/; in ZSTD_rescaleFreqs()
200 { unsigned const baseLLfreqs[MaxLL+1] = { in ZSTD_rescaleFreqs()
201 4, 2, 1, 1, 1, 1, 1, 1, in ZSTD_rescaleFreqs()
202 1, 1, 1, 1, 1, 1, 1, 1, in ZSTD_rescaleFreqs()
203 1, 1, 1, 1, 1, 1, 1, 1, in ZSTD_rescaleFreqs()
204 1, 1, 1, 1, 1, 1, 1, 1, in ZSTD_rescaleFreqs()
205 1, 1, 1, 1 in ZSTD_rescaleFreqs()
208 optPtr->litLengthSum = sum_u32(baseLLfreqs, MaxLL+1); in ZSTD_rescaleFreqs()
213 optPtr->matchLengthFreq[ml] = 1; in ZSTD_rescaleFreqs()
215 optPtr->matchLengthSum = MaxML+1; in ZSTD_rescaleFreqs()
217 { unsigned const baseOFCfreqs[MaxOff+1] = { in ZSTD_rescaleFreqs()
218 6, 2, 1, 1, 2, 3, 4, 4, in ZSTD_rescaleFreqs()
219 4, 3, 2, 1, 1, 1, 1, 1, in ZSTD_rescaleFreqs()
220 1, 1, 1, 1, 1, 1, 1, 1, in ZSTD_rescaleFreqs()
221 1, 1, 1, 1, 1, 1, 1, 1 in ZSTD_rescaleFreqs()
224 optPtr->offCodeSum = sum_u32(baseOFCfreqs, MaxOff+1); in ZSTD_rescaleFreqs()
277 * call it 1 bit more than ZSTD_BLOCKSIZE_MAX - 1. In this case the block in ZSTD_litLengthPrice()
281 return BITCOST_MULTIPLIER + ZSTD_litLengthPrice(ZSTD_BLOCKSIZE_MAX - 1, optPtr, optLevel); in ZSTD_litLengthPrice()
294 * @offcode : expects a scale where 0,1,2 are repcodes 1-3, and 3+ are real_offsets+2
382 static U32 ZSTD_insertAndFindFirstIndexHash3 (const ZSTD_matchState_t* ms, in ZSTD_insertAndFindFirstIndexHash3() argument
386 U32* const hashTable3 = ms->hashTable3; in ZSTD_insertAndFindFirstIndexHash3()
387 U32 const hashLog3 = ms->hashLog3; in ZSTD_insertAndFindFirstIndexHash3()
388 const BYTE* const base = ms->window.base; in ZSTD_insertAndFindFirstIndexHash3()
412 const ZSTD_matchState_t* ms, in ZSTD_insertBt1() argument
417 const ZSTD_compressionParameters* const cParams = &ms->cParams; in ZSTD_insertBt1()
418 U32* const hashTable = ms->hashTable; in ZSTD_insertBt1()
421 U32* const bt = ms->chainTable; in ZSTD_insertBt1()
422 U32 const btLog = cParams->chainLog - 1; in ZSTD_insertBt1()
423 U32 const btMask = (1 << btLog) - 1; in ZSTD_insertBt1()
426 const BYTE* const base = ms->window.base; in ZSTD_insertBt1()
427 const BYTE* const dictBase = ms->window.dictBase; in ZSTD_insertBt1()
428 const U32 dictLimit = ms->window.dictLimit; in ZSTD_insertBt1()
435 U32* largerPtr = smallerPtr + 1; in ZSTD_insertBt1()
440 U32 const windowLow = ZSTD_getLowestMatchIndex(ms, target, cParams->windowLog); in ZSTD_insertBt1()
441 U32 matchEndIdx = curr+8+1; in ZSTD_insertBt1()
443 U32 nbCompares = 1U << cParams->searchLog; in ZSTD_insertBt1()
445 U32 predictedSmall = *(bt + 2*((curr-1)&btMask) + 0); in ZSTD_insertBt1()
446 U32 predictedLarge = *(bt + 2*((curr-1)&btMask) + 1); in ZSTD_insertBt1()
464 …const U32* predictPtr = bt + 2*((matchIndex-1) & btMask); /* written this way, as bt is a roll b… in ZSTD_insertBt1()
469 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */ in ZSTD_insertBt1()
470 …matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */ in ZSTD_insertBt1()
471 predictedSmall = predictPtr[1] + (predictPtr[1]>0); in ZSTD_insertBt1()
510 …smallerPtr = nextPtr+1; /* new "candidate" => larger than match, which was smaller t… in ZSTD_insertBt1()
511 …matchIndex = nextPtr[1]; /* new matchIndex, larger than previous and closer to curren… in ZSTD_insertBt1()
531 ZSTD_matchState_t* ms, in ZSTD_updateTree_internal() argument
535 const BYTE* const base = ms->window.base; in ZSTD_updateTree_internal()
537 U32 idx = ms->nextToUpdate; in ZSTD_updateTree_internal()
542 … U32 const forward = ZSTD_insertBt1(ms, base+idx, iend, target, mls, dictMode == ZSTD_extDict); in ZSTD_updateTree_internal()
546 assert((size_t)(ip - base) <= (size_t)(U32)(-1)); in ZSTD_updateTree_internal()
547 assert((size_t)(iend - base) <= (size_t)(U32)(-1)); in ZSTD_updateTree_internal()
548 ms->nextToUpdate = target; in ZSTD_updateTree_internal()
551 void ZSTD_updateTree(ZSTD_matchState_t* ms, const BYTE* ip, const BYTE* iend) { in ZSTD_updateTree() argument
552 ZSTD_updateTree_internal(ms, ip, iend, ms->cParams.minMatch, ZSTD_noDict); in ZSTD_updateTree()
558 ZSTD_matchState_t* ms, in ZSTD_insertBtAndGetAllMatches() argument
562 … U32 const ll0, /* tells if associated literal length is 0 or not. This value must be 0 or 1 */ in ZSTD_insertBtAndGetAllMatches()
566 const ZSTD_compressionParameters* const cParams = &ms->cParams; in ZSTD_insertBtAndGetAllMatches()
567 U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1); in ZSTD_insertBtAndGetAllMatches()
568 const BYTE* const base = ms->window.base; in ZSTD_insertBtAndGetAllMatches()
572 U32* const hashTable = ms->hashTable; in ZSTD_insertBtAndGetAllMatches()
575 U32* const bt = ms->chainTable; in ZSTD_insertBtAndGetAllMatches()
576 U32 const btLog = cParams->chainLog - 1; in ZSTD_insertBtAndGetAllMatches()
577 U32 const btMask= (1U << btLog) - 1; in ZSTD_insertBtAndGetAllMatches()
579 const BYTE* const dictBase = ms->window.dictBase; in ZSTD_insertBtAndGetAllMatches()
580 U32 const dictLimit = ms->window.dictLimit; in ZSTD_insertBtAndGetAllMatches()
584 U32 const windowLow = ZSTD_getLowestMatchIndex(ms, curr, cParams->windowLog); in ZSTD_insertBtAndGetAllMatches()
585 U32 const matchLow = windowLow ? windowLow : 1; in ZSTD_insertBtAndGetAllMatches()
587 U32* largerPtr = bt + 2*(curr&btMask) + 1; in ZSTD_insertBtAndGetAllMatches()
588 …U32 matchEndIdx = curr+8+1; /* farthest referenced position of any match => detects repetitive p… in ZSTD_insertBtAndGetAllMatches()
591 U32 nbCompares = 1U << cParams->searchLog; in ZSTD_insertBtAndGetAllMatches()
593 const ZSTD_matchState_t* dms = dictMode == ZSTD_dictMatchState ? ms->dictMatchState : NULL; in ZSTD_insertBtAndGetAllMatches()
602 …U32 const dmsBtLog = dictMode == ZSTD_dictMatchState ? dmsCParams->chainLog - 1 : btL… in ZSTD_insertBtAndGetAllMatches()
603 U32 const dmsBtMask = dictMode == ZSTD_dictMatchState ? (1U << dmsBtLog) - 1 : 0; in ZSTD_insertBtAndGetAllMatches()
606 size_t bestLength = lengthToBeat-1; in ZSTD_insertBtAndGetAllMatches()
610 assert(ll0 <= 1); /* necessarily 1 or 0 */ in ZSTD_insertBtAndGetAllMatches()
614 U32 const repOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode]; in ZSTD_insertBtAndGetAllMatches()
618 …if (repOffset-1 /* intentional overflow, discards 0 and -1 */ < curr-dictLimit) { /* equivalent t… in ZSTD_insertBtAndGetAllMatches()
631 …&& ( ((repOffset-1) /*intentional overflow*/ < curr - windowLow) /* equivalent to `curr > repInde… in ZSTD_insertBtAndGetAllMatches()
632 …& (((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overla… in ZSTD_insertBtAndGetAllMatches()
637 …&& ( ((repOffset-1) /*intentional overflow*/ < curr - (dmsLowLimit + dmsIndexDelta)) /* equivalen… in ZSTD_insertBtAndGetAllMatches()
638 …& ((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overlap… in ZSTD_insertBtAndGetAllMatches()
647 … matches[mnum].off = STORE_REPCODE(repCode - ll0 + 1); /* expect value between 1 and 3 */ in ZSTD_insertBtAndGetAllMatches()
657 U32 const matchIndex3 = ZSTD_insertAndFindFirstIndexHash3(ms, nextToUpdate3, ip); in ZSTD_insertBtAndGetAllMatches()
659 & (curr - matchIndex3 < (1<<18)) /*heuristic : longer distance likely too expensive*/ ) { in ZSTD_insertBtAndGetAllMatches()
678 mnum = 1; in ZSTD_insertBtAndGetAllMatches()
681 ms->nextToUpdate = curr+1; /* skip insertion */ in ZSTD_insertBtAndGetAllMatches()
682 return 1; in ZSTD_insertBtAndGetAllMatches()
729 …smallerPtr = nextPtr+1; /* new candidate => larger than match, which was smaller tha… in ZSTD_insertBtAndGetAllMatches()
730 …matchIndex = nextPtr[1]; /* new matchIndex, larger than previous, closer to current */ in ZSTD_insertBtAndGetAllMatches()
741 assert(nbCompares <= (1U << ZSTD_SEARCHLOG_MAX)); /* Check we haven't underflowed. */ in ZSTD_insertBtAndGetAllMatches()
773 …dictMatchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to curren… in ZSTD_insertBtAndGetAllMatches()
781 ms->nextToUpdate = matchEndIdx - 8; /* skip repetitive patterns */ in ZSTD_insertBtAndGetAllMatches()
797 ZSTD_matchState_t* ms, in ZSTD_btGetAllMatches_internal() argument
807 assert(BOUNDED(3, ms->cParams.minMatch, 6) == mls); in ZSTD_btGetAllMatches_internal()
809 if (ip < ms->window.base + ms->nextToUpdate) in ZSTD_btGetAllMatches_internal()
811 ZSTD_updateTree_internal(ms, ip, iHighLimit, mls, dictMode); in ZSTD_btGetAllMatches_internal()
812 …return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode, rep, ll… in ZSTD_btGetAllMatches_internal()
820 ZSTD_matchState_t* ms, \
829 matches, ms, nextToUpdate3, ip, iHighLimit, \
852 ZSTD_selectBtGetAllMatches(ZSTD_matchState_t const* ms, ZSTD_dictMode_e const dictMode)
859 U32 const mls = BOUNDED(3, ms->cParams.minMatch, 6);
973 …if (*nbMatches == 0 || ((candidateMatchLength > matches[*nbMatches-1].len) && *nbMatches < ZSTD_OP… in ZSTD_optLdm_maybeAddMatch()
1024 int const nbElts = lastEltID + 1;
1037 ZSTD_compressBlock_opt_generic(ZSTD_matchState_t* ms, in ZSTD_compressBlock_opt_generic() argument
1044 optState_t* const optStatePtr = &ms->opt; in ZSTD_compressBlock_opt_generic()
1050 const BYTE* const base = ms->window.base; in ZSTD_compressBlock_opt_generic()
1051 const BYTE* const prefixStart = base + ms->window.dictLimit; in ZSTD_compressBlock_opt_generic()
1052 const ZSTD_compressionParameters* const cParams = &ms->cParams; in ZSTD_compressBlock_opt_generic()
1054 ZSTD_getAllMatchesFn getAllMatches = ZSTD_selectBtGetAllMatches(ms, dictMode); in ZSTD_compressBlock_opt_generic()
1056 U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1); in ZSTD_compressBlock_opt_generic()
1058 U32 nextToUpdate3 = ms->nextToUpdate; in ZSTD_compressBlock_opt_generic()
1065 optLdm.seqStore = ms->ldmSeqStore ? *ms->ldmSeqStore : kNullRawSeqStore; in ZSTD_compressBlock_opt_generic()
1071 (U32)(ip - base), ms->window.dictLimit, ms->nextToUpdate); in ZSTD_compressBlock_opt_generic()
1083 … U32 nbMatches = getAllMatches(matches, ms, &nextToUpdate3, ip, iend, rep, ll0, minMatch); in ZSTD_compressBlock_opt_generic()
1100 { U32 const maxML = matches[nbMatches-1].len; in ZSTD_compressBlock_opt_generic()
1101 U32 const maxOffcode = matches[nbMatches-1].off; in ZSTD_compressBlock_opt_generic()
1121 for (pos = 1; pos < minMatch; pos++) { in ZSTD_compressBlock_opt_generic()
1137 last_pos = pos-1; in ZSTD_compressBlock_opt_generic()
1142 for (cur = 1; cur <= last_pos; cur++) { in ZSTD_compressBlock_opt_generic()
1148 { U32 const litlen = (opt[cur-1].mlen == 0) ? opt[cur-1].litlen + 1 : 1; in ZSTD_compressBlock_opt_generic()
1149 int const price = opt[cur-1].price in ZSTD_compressBlock_opt_generic()
1150 + (int)ZSTD_rawLiteralsCost(ip+cur-1, 1, optStatePtr, optLevel) in ZSTD_compressBlock_opt_generic()
1152 - (int)ZSTD_litLengthPrice(litlen-1, optStatePtr, optLevel); in ZSTD_compressBlock_opt_generic()
1157 opt[cur-1].rep[0], opt[cur-1].rep[1], opt[cur-1].rep[2]); in ZSTD_compressBlock_opt_generic()
1165 opt[cur].rep[0], opt[cur].rep[1], opt[cur].rep[2]); in ZSTD_compressBlock_opt_generic()
1181 ZSTD_memcpy(opt[cur].rep, opt[cur - 1].rep, sizeof(repcodes_t)); in ZSTD_compressBlock_opt_generic()
1190 && (opt[cur+1].price <= opt[cur].price + (BITCOST_MULTIPLIER/2)) ) { in ZSTD_compressBlock_opt_generic()
1191 DEBUGLOG(7, "move to next rPos:%u : price is <=", cur+1); in ZSTD_compressBlock_opt_generic()
1200 …U32 nbMatches = getAllMatches(matches, ms, &nextToUpdate3, inr, iend, opt[cur].rep, ll0, minMatch); in ZSTD_compressBlock_opt_generic()
1211 { U32 const maxML = matches[nbMatches-1].len; in ZSTD_compressBlock_opt_generic()
1218 lastSequence.off = matches[nbMatches-1].off; in ZSTD_compressBlock_opt_generic()
1230 U32 const startML = (matchNb>0) ? matches[matchNb-1].len+1 : minMatch; in ZSTD_compressBlock_opt_generic()
1243 …while (last_pos < pos) { opt[last_pos+1].price = ZSTD_MAX_PRICE; last_pos++; } /* fill empty pos… in ZSTD_compressBlock_opt_generic()
1254 } /* for (cur = 1; cur <= last_pos; cur++) */ in ZSTD_compressBlock_opt_generic()
1274 { U32 const storeEnd = cur + 1; in ZSTD_compressBlock_opt_generic()
1325 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_opt0() argument
1328 …return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 0 /* optLevel */, dictMode); in ZSTD_compressBlock_opt0()
1332 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_opt2() argument
1335 …return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /* optLevel */, dictMode); in ZSTD_compressBlock_opt2()
1339 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btopt() argument
1343 return ZSTD_compressBlock_opt0(ms, seqStore, rep, src, srcSize, ZSTD_noDict); in ZSTD_compressBlock_btopt()
1355 ZSTD_initStats_ultra(ZSTD_matchState_t* ms, in ZSTD_initStats_ultra() argument
1364 assert(ms->opt.litLengthSum == 0); /* first block */ in ZSTD_initStats_ultra()
1366 assert(ms->window.dictLimit == ms->window.lowLimit); /* no dictionary */ in ZSTD_initStats_ultra()
1367 …assert(ms->window.dictLimit - ms->nextToUpdate <= 1); /* no prefix (note: intentional overflow, d… in ZSTD_initStats_ultra()
1369 …ZSTD_compressBlock_opt2(ms, seqStore, tmpRep, src, srcSize, ZSTD_noDict); /* generate stats into… in ZSTD_initStats_ultra()
1373 ms->window.base -= srcSize; in ZSTD_initStats_ultra()
1374 ms->window.dictLimit += (U32)srcSize; in ZSTD_initStats_ultra()
1375 ms->window.lowLimit = ms->window.dictLimit; in ZSTD_initStats_ultra()
1376 ms->nextToUpdate = ms->window.dictLimit; in ZSTD_initStats_ultra()
1381 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btultra() argument
1385 return ZSTD_compressBlock_opt2(ms, seqStore, rep, src, srcSize, ZSTD_noDict); in ZSTD_compressBlock_btultra()
1389 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btultra2() argument
1392 U32 const curr = (U32)((const BYTE*)src - ms->window.base); in ZSTD_compressBlock_btultra2()
1398 * After 1st pass, function forgets everything, and starts a new block. in ZSTD_compressBlock_btultra2()
1404 if ( (ms->opt.litLengthSum==0) /* first block */ in ZSTD_compressBlock_btultra2()
1406 && (ms->window.dictLimit == ms->window.lowLimit) /* no dictionary */ in ZSTD_compressBlock_btultra2()
1407 && (curr == ms->window.dictLimit) /* start of frame, nothing already loaded nor skipped */ in ZSTD_compressBlock_btultra2()
1410 ZSTD_initStats_ultra(ms, seqStore, rep, src, srcSize); in ZSTD_compressBlock_btultra2()
1413 return ZSTD_compressBlock_opt2(ms, seqStore, rep, src, srcSize, ZSTD_noDict); in ZSTD_compressBlock_btultra2()
1417 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btopt_dictMatchState() argument
1420 return ZSTD_compressBlock_opt0(ms, seqStore, rep, src, srcSize, ZSTD_dictMatchState); in ZSTD_compressBlock_btopt_dictMatchState()
1424 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btultra_dictMatchState() argument
1427 return ZSTD_compressBlock_opt2(ms, seqStore, rep, src, srcSize, ZSTD_dictMatchState); in ZSTD_compressBlock_btultra_dictMatchState()
1431 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btopt_extDict() argument
1434 return ZSTD_compressBlock_opt0(ms, seqStore, rep, src, srcSize, ZSTD_extDict); in ZSTD_compressBlock_btopt_extDict()
1438 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], in ZSTD_compressBlock_btultra_extDict() argument
1441 return ZSTD_compressBlock_opt2(ms, seqStore, rep, src, srcSize, ZSTD_extDict); in ZSTD_compressBlock_btultra_extDict()