ReactOS 0.4.16-dev-401-g45b008d
zstd_opt.c
Go to the documentation of this file.
1/*
2 * Copyright (c) 2016-2020, Przemyslaw Skibinski, Yann Collet, Facebook, Inc.
3 * All rights reserved.
4 *
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
9 */
10
12#include "hist.h"
13#include "zstd_opt.h"
14
15
16#define ZSTD_LITFREQ_ADD 2 /* scaling factor for litFreq, so that frequencies adapt faster to new stats */
17#define ZSTD_FREQ_DIV 4 /* log factor when using previous stats to init next stats */
18#define ZSTD_MAX_PRICE (1<<30)
19
20#define ZSTD_PREDEF_THRESHOLD 1024 /* if srcSize < ZSTD_PREDEF_THRESHOLD, symbols' cost is assumed static, directly determined by pre-defined distributions */
21
22
23/*-*************************************
24* Price functions for optimal parser
25***************************************/
26
27#if 0 /* approximation at bit level */
28# define BITCOST_ACCURACY 0
29# define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
30# define WEIGHT(stat) ((void)opt, ZSTD_bitWeight(stat))
31#elif 0 /* fractional bit accuracy */
32# define BITCOST_ACCURACY 8
33# define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
34# define WEIGHT(stat,opt) ((void)opt, ZSTD_fracWeight(stat))
35#else /* opt==approx, ultra==accurate */
36# define BITCOST_ACCURACY 8
37# define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
38# define WEIGHT(stat,opt) (opt ? ZSTD_fracWeight(stat) : ZSTD_bitWeight(stat))
39#endif
40
42{
44}
45
47{
48 U32 const stat = rawStat + 1;
49 U32 const hb = ZSTD_highbit32(stat);
50 U32 const BWeight = hb * BITCOST_MULTIPLIER;
51 U32 const FWeight = (stat << BITCOST_ACCURACY) >> hb;
52 U32 const weight = BWeight + FWeight;
53 assert(hb + BITCOST_ACCURACY < 31);
54 return weight;
55}
56
57#if (DEBUGLEVEL>=2)
58/* debugging function,
59 * @return price in bytes as fractional value
60 * for debug messages only */
61MEM_STATIC double ZSTD_fCost(U32 price)
62{
63 return (double)price / (BITCOST_MULTIPLIER*8);
64}
65#endif
66
67static int ZSTD_compressedLiterals(optState_t const* const optPtr)
68{
69 return optPtr->literalCompressionMode != ZSTD_lcm_uncompressed;
70}
71
72static void ZSTD_setBasePrices(optState_t* optPtr, int optLevel)
73{
74 if (ZSTD_compressedLiterals(optPtr))
75 optPtr->litSumBasePrice = WEIGHT(optPtr->litSum, optLevel);
76 optPtr->litLengthSumBasePrice = WEIGHT(optPtr->litLengthSum, optLevel);
77 optPtr->matchLengthSumBasePrice = WEIGHT(optPtr->matchLengthSum, optLevel);
78 optPtr->offCodeSumBasePrice = WEIGHT(optPtr->offCodeSum, optLevel);
79}
80
81
82/* ZSTD_downscaleStat() :
83 * reduce all elements in table by a factor 2^(ZSTD_FREQ_DIV+malus)
84 * return the resulting sum of elements */
85static U32 ZSTD_downscaleStat(unsigned* table, U32 lastEltIndex, int malus)
86{
87 U32 s, sum=0;
88 DEBUGLOG(5, "ZSTD_downscaleStat (nbElts=%u)", (unsigned)lastEltIndex+1);
89 assert(ZSTD_FREQ_DIV+malus > 0 && ZSTD_FREQ_DIV+malus < 31);
90 for (s=0; s<lastEltIndex+1; s++) {
91 table[s] = 1 + (table[s] >> (ZSTD_FREQ_DIV+malus));
92 sum += table[s];
93 }
94 return sum;
95}
96
97/* ZSTD_rescaleFreqs() :
98 * if first block (detected by optPtr->litLengthSum == 0) : init statistics
99 * take hints from dictionary if there is one
100 * or init from zero, using src for literals stats, or flat 1 for match symbols
101 * otherwise downscale existing stats, to be used as seed for next block.
102 */
103static void
105 const BYTE* const src, size_t const srcSize,
106 int const optLevel)
107{
108 int const compressedLiterals = ZSTD_compressedLiterals(optPtr);
109 DEBUGLOG(5, "ZSTD_rescaleFreqs (srcSize=%u)", (unsigned)srcSize);
110 optPtr->priceType = zop_dynamic;
111
112 if (optPtr->litLengthSum == 0) { /* first block : init */
113 if (srcSize <= ZSTD_PREDEF_THRESHOLD) { /* heuristic */
114 DEBUGLOG(5, "(srcSize <= ZSTD_PREDEF_THRESHOLD) => zop_predef");
115 optPtr->priceType = zop_predef;
116 }
117
118 assert(optPtr->symbolCosts != NULL);
119 if (optPtr->symbolCosts->huf.repeatMode == HUF_repeat_valid) {
120 /* huffman table presumed generated by dictionary */
121 optPtr->priceType = zop_dynamic;
122
123 if (compressedLiterals) {
124 unsigned lit;
125 assert(optPtr->litFreq != NULL);
126 optPtr->litSum = 0;
127 for (lit=0; lit<=MaxLit; lit++) {
128 U32 const scaleLog = 11; /* scale to 2K */
129 U32 const bitCost = HUF_getNbBits(optPtr->symbolCosts->huf.CTable, lit);
130 assert(bitCost <= scaleLog);
131 optPtr->litFreq[lit] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;
132 optPtr->litSum += optPtr->litFreq[lit];
133 } }
134
135 { unsigned ll;
136 FSE_CState_t llstate;
137 FSE_initCState(&llstate, optPtr->symbolCosts->fse.litlengthCTable);
138 optPtr->litLengthSum = 0;
139 for (ll=0; ll<=MaxLL; ll++) {
140 U32 const scaleLog = 10; /* scale to 1K */
141 U32 const bitCost = FSE_getMaxNbBits(llstate.symbolTT, ll);
142 assert(bitCost < scaleLog);
143 optPtr->litLengthFreq[ll] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;
144 optPtr->litLengthSum += optPtr->litLengthFreq[ll];
145 } }
146
147 { unsigned ml;
148 FSE_CState_t mlstate;
149 FSE_initCState(&mlstate, optPtr->symbolCosts->fse.matchlengthCTable);
150 optPtr->matchLengthSum = 0;
151 for (ml=0; ml<=MaxML; ml++) {
152 U32 const scaleLog = 10;
153 U32 const bitCost = FSE_getMaxNbBits(mlstate.symbolTT, ml);
154 assert(bitCost < scaleLog);
155 optPtr->matchLengthFreq[ml] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;
156 optPtr->matchLengthSum += optPtr->matchLengthFreq[ml];
157 } }
158
159 { unsigned of;
160 FSE_CState_t ofstate;
161 FSE_initCState(&ofstate, optPtr->symbolCosts->fse.offcodeCTable);
162 optPtr->offCodeSum = 0;
163 for (of=0; of<=MaxOff; of++) {
164 U32 const scaleLog = 10;
165 U32 const bitCost = FSE_getMaxNbBits(ofstate.symbolTT, of);
166 assert(bitCost < scaleLog);
167 optPtr->offCodeFreq[of] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;
168 optPtr->offCodeSum += optPtr->offCodeFreq[of];
169 } }
170
171 } else { /* not a dictionary */
172
173 assert(optPtr->litFreq != NULL);
174 if (compressedLiterals) {
175 unsigned lit = MaxLit;
176 HIST_count_simple(optPtr->litFreq, &lit, src, srcSize); /* use raw first block to init statistics */
177 optPtr->litSum = ZSTD_downscaleStat(optPtr->litFreq, MaxLit, 1);
178 }
179
180 { unsigned ll;
181 for (ll=0; ll<=MaxLL; ll++)
182 optPtr->litLengthFreq[ll] = 1;
183 }
184 optPtr->litLengthSum = MaxLL+1;
185
186 { unsigned ml;
187 for (ml=0; ml<=MaxML; ml++)
188 optPtr->matchLengthFreq[ml] = 1;
189 }
190 optPtr->matchLengthSum = MaxML+1;
191
192 { unsigned of;
193 for (of=0; of<=MaxOff; of++)
194 optPtr->offCodeFreq[of] = 1;
195 }
196 optPtr->offCodeSum = MaxOff+1;
197
198 }
199
200 } else { /* new block : re-use previous statistics, scaled down */
201
202 if (compressedLiterals)
203 optPtr->litSum = ZSTD_downscaleStat(optPtr->litFreq, MaxLit, 1);
204 optPtr->litLengthSum = ZSTD_downscaleStat(optPtr->litLengthFreq, MaxLL, 0);
206 optPtr->offCodeSum = ZSTD_downscaleStat(optPtr->offCodeFreq, MaxOff, 0);
207 }
208
209 ZSTD_setBasePrices(optPtr, optLevel);
210}
211
212/* ZSTD_rawLiteralsCost() :
213 * price of literals (only) in specified segment (which length can be 0).
214 * does not include price of literalLength symbol */
215static U32 ZSTD_rawLiteralsCost(const BYTE* const literals, U32 const litLength,
216 const optState_t* const optPtr,
217 int optLevel)
218{
219 if (litLength == 0) return 0;
220
221 if (!ZSTD_compressedLiterals(optPtr))
222 return (litLength << 3) * BITCOST_MULTIPLIER; /* Uncompressed - 8 bytes per literal. */
223
224 if (optPtr->priceType == zop_predef)
225 return (litLength*6) * BITCOST_MULTIPLIER; /* 6 bit per literal - no statistic used */
226
227 /* dynamic statistics */
228 { U32 price = litLength * optPtr->litSumBasePrice;
229 U32 u;
230 for (u=0; u < litLength; u++) {
231 assert(WEIGHT(optPtr->litFreq[literals[u]], optLevel) <= optPtr->litSumBasePrice); /* literal cost should never be negative */
232 price -= WEIGHT(optPtr->litFreq[literals[u]], optLevel);
233 }
234 return price;
235 }
236}
237
238/* ZSTD_litLengthPrice() :
239 * cost of literalLength symbol */
240static U32 ZSTD_litLengthPrice(U32 const litLength, const optState_t* const optPtr, int optLevel)
241{
242 if (optPtr->priceType == zop_predef) return WEIGHT(litLength, optLevel);
243
244 /* dynamic statistics */
245 { U32 const llCode = ZSTD_LLcode(litLength);
246 return (LL_bits[llCode] * BITCOST_MULTIPLIER)
247 + optPtr->litLengthSumBasePrice
248 - WEIGHT(optPtr->litLengthFreq[llCode], optLevel);
249 }
250}
251
252/* ZSTD_getMatchPrice() :
253 * Provides the cost of the match part (offset + matchLength) of a sequence
254 * Must be combined with ZSTD_fullLiteralsCost() to get the full cost of a sequence.
255 * optLevel: when <2, favors small offset for decompression speed (improved cache efficiency) */
258 U32 const matchLength,
259 const optState_t* const optPtr,
260 int const optLevel)
261{
262 U32 price;
263 U32 const offCode = ZSTD_highbit32(offset+1);
264 U32 const mlBase = matchLength - MINMATCH;
265 assert(matchLength >= MINMATCH);
266
267 if (optPtr->priceType == zop_predef) /* fixed scheme, do not use statistics */
268 return WEIGHT(mlBase, optLevel) + ((16 + offCode) * BITCOST_MULTIPLIER);
269
270 /* dynamic statistics */
271 price = (offCode * BITCOST_MULTIPLIER) + (optPtr->offCodeSumBasePrice - WEIGHT(optPtr->offCodeFreq[offCode], optLevel));
272 if ((optLevel<2) /*static*/ && offCode >= 20)
273 price += (offCode-19)*2 * BITCOST_MULTIPLIER; /* handicap for long distance offsets, favor decompression speed */
274
275 /* match Length */
276 { U32 const mlCode = ZSTD_MLcode(mlBase);
277 price += (ML_bits[mlCode] * BITCOST_MULTIPLIER) + (optPtr->matchLengthSumBasePrice - WEIGHT(optPtr->matchLengthFreq[mlCode], optLevel));
278 }
279
280 price += BITCOST_MULTIPLIER / 5; /* heuristic : make matches a bit more costly to favor less sequences -> faster decompression speed */
281
282 DEBUGLOG(8, "ZSTD_getMatchPrice(ml:%u) = %u", matchLength, price);
283 return price;
284}
285
286/* ZSTD_updateStats() :
287 * assumption : literals + litLengtn <= iend */
288static void ZSTD_updateStats(optState_t* const optPtr,
289 U32 litLength, const BYTE* literals,
290 U32 offsetCode, U32 matchLength)
291{
292 /* literals */
293 if (ZSTD_compressedLiterals(optPtr)) {
294 U32 u;
295 for (u=0; u < litLength; u++)
296 optPtr->litFreq[literals[u]] += ZSTD_LITFREQ_ADD;
297 optPtr->litSum += litLength*ZSTD_LITFREQ_ADD;
298 }
299
300 /* literal Length */
301 { U32 const llCode = ZSTD_LLcode(litLength);
302 optPtr->litLengthFreq[llCode]++;
303 optPtr->litLengthSum++;
304 }
305
306 /* match offset code (0-2=>repCode; 3+=>offset+2) */
307 { U32 const offCode = ZSTD_highbit32(offsetCode+1);
308 assert(offCode <= MaxOff);
309 optPtr->offCodeFreq[offCode]++;
310 optPtr->offCodeSum++;
311 }
312
313 /* match Length */
314 { U32 const mlBase = matchLength - MINMATCH;
315 U32 const mlCode = ZSTD_MLcode(mlBase);
316 optPtr->matchLengthFreq[mlCode]++;
317 optPtr->matchLengthSum++;
318 }
319}
320
321
322/* ZSTD_readMINMATCH() :
323 * function safe only for comparisons
324 * assumption : memPtr must be at least 4 bytes before end of buffer */
326{
327 switch (length)
328 {
329 default :
330 case 4 : return MEM_read32(memPtr);
331 case 3 : if (MEM_isLittleEndian())
332 return MEM_read32(memPtr)<<8;
333 else
334 return MEM_read32(memPtr)>>8;
335 }
336}
337
338
339/* Update hashTable3 up to ip (excluded)
340 Assumption : always within prefix (i.e. not within extDict) */
342 U32* nextToUpdate3,
343 const BYTE* const ip)
344{
345 U32* const hashTable3 = ms->hashTable3;
346 U32 const hashLog3 = ms->hashLog3;
347 const BYTE* const base = ms->window.base;
348 U32 idx = *nextToUpdate3;
349 U32 const target = (U32)(ip - base);
350 size_t const hash3 = ZSTD_hash3Ptr(ip, hashLog3);
351 assert(hashLog3 > 0);
352
353 while(idx < target) {
354 hashTable3[ZSTD_hash3Ptr(base+idx, hashLog3)] = idx;
355 idx++;
356 }
357
358 *nextToUpdate3 = target;
359 return hashTable3[hash3];
360}
361
362
363/*-*************************************
364* Binary Tree search
365***************************************/
371 const BYTE* const ip, const BYTE* const iend,
372 U32 const mls, const int extDict)
373{
374 const ZSTD_compressionParameters* const cParams = &ms->cParams;
375 U32* const hashTable = ms->hashTable;
376 U32 const hashLog = cParams->hashLog;
377 size_t const h = ZSTD_hashPtr(ip, hashLog, mls);
378 U32* const bt = ms->chainTable;
379 U32 const btLog = cParams->chainLog - 1;
380 U32 const btMask = (1 << btLog) - 1;
381 U32 matchIndex = hashTable[h];
382 size_t commonLengthSmaller=0, commonLengthLarger=0;
383 const BYTE* const base = ms->window.base;
384 const BYTE* const dictBase = ms->window.dictBase;
385 const U32 dictLimit = ms->window.dictLimit;
386 const BYTE* const dictEnd = dictBase + dictLimit;
387 const BYTE* const prefixStart = base + dictLimit;
388 const BYTE* match;
389 const U32 current = (U32)(ip-base);
390 const U32 btLow = btMask >= current ? 0 : current - btMask;
391 U32* smallerPtr = bt + 2*(current&btMask);
392 U32* largerPtr = smallerPtr + 1;
393 U32 dummy32; /* to be nullified at the end */
394 U32 const windowLow = ms->window.lowLimit;
395 U32 matchEndIdx = current+8+1;
396 size_t bestLength = 8;
397 U32 nbCompares = 1U << cParams->searchLog;
398#ifdef ZSTD_C_PREDICT
399 U32 predictedSmall = *(bt + 2*((current-1)&btMask) + 0);
400 U32 predictedLarge = *(bt + 2*((current-1)&btMask) + 1);
401 predictedSmall += (predictedSmall>0);
402 predictedLarge += (predictedLarge>0);
403#endif /* ZSTD_C_PREDICT */
404
405 DEBUGLOG(8, "ZSTD_insertBt1 (%u)", current);
406
407 assert(ip <= iend-8); /* required for h calculation */
408 hashTable[h] = current; /* Update Hash Table */
409
410 assert(windowLow > 0);
411 while (nbCompares-- && (matchIndex >= windowLow)) {
412 U32* const nextPtr = bt + 2*(matchIndex & btMask);
413 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
414 assert(matchIndex < current);
415
416#ifdef ZSTD_C_PREDICT /* note : can create issues when hlog small <= 11 */
417 const U32* predictPtr = bt + 2*((matchIndex-1) & btMask); /* written this way, as bt is a roll buffer */
418 if (matchIndex == predictedSmall) {
419 /* no need to check length, result known */
420 *smallerPtr = matchIndex;
421 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
422 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */
423 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
424 predictedSmall = predictPtr[1] + (predictPtr[1]>0);
425 continue;
426 }
427 if (matchIndex == predictedLarge) {
428 *largerPtr = matchIndex;
429 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
430 largerPtr = nextPtr;
431 matchIndex = nextPtr[0];
432 predictedLarge = predictPtr[0] + (predictPtr[0]>0);
433 continue;
434 }
435#endif
436
437 if (!extDict || (matchIndex+matchLength >= dictLimit)) {
438 assert(matchIndex+matchLength >= dictLimit); /* might be wrong if actually extDict */
439 match = base + matchIndex;
440 matchLength += ZSTD_count(ip+matchLength, match+matchLength, iend);
441 } else {
442 match = dictBase + matchIndex;
443 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
444 if (matchIndex+matchLength >= dictLimit)
445 match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
446 }
447
448 if (matchLength > bestLength) {
449 bestLength = matchLength;
450 if (matchLength > matchEndIdx - matchIndex)
451 matchEndIdx = matchIndex + (U32)matchLength;
452 }
453
454 if (ip+matchLength == iend) { /* equal : no way to know if inf or sup */
455 break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt tree */
456 }
457
458 if (match[matchLength] < ip[matchLength]) { /* necessarily within buffer */
459 /* match is smaller than current */
460 *smallerPtr = matchIndex; /* update smaller idx */
461 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
462 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop searching */
463 smallerPtr = nextPtr+1; /* new "candidate" => larger than match, which was smaller than target */
464 matchIndex = nextPtr[1]; /* new matchIndex, larger than previous and closer to current */
465 } else {
466 /* match is larger than current */
467 *largerPtr = matchIndex;
468 commonLengthLarger = matchLength;
469 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop searching */
470 largerPtr = nextPtr;
471 matchIndex = nextPtr[0];
472 } }
473
474 *smallerPtr = *largerPtr = 0;
475 { U32 positions = 0;
476 if (bestLength > 384) positions = MIN(192, (U32)(bestLength - 384)); /* speed optimization */
477 assert(matchEndIdx > current + 8);
478 return MAX(positions, matchEndIdx - (current + 8));
479 }
480}
481
485 const BYTE* const ip, const BYTE* const iend,
486 const U32 mls, const ZSTD_dictMode_e dictMode)
487{
488 const BYTE* const base = ms->window.base;
489 U32 const target = (U32)(ip - base);
490 U32 idx = ms->nextToUpdate;
491 DEBUGLOG(6, "ZSTD_updateTree_internal, from %u to %u (dictMode:%u)",
492 idx, target, dictMode);
493
494 while(idx < target) {
495 U32 const forward = ZSTD_insertBt1(ms, base+idx, iend, mls, dictMode == ZSTD_extDict);
496 assert(idx < (U32)(idx + forward));
497 idx += forward;
498 }
499 assert((size_t)(ip - base) <= (size_t)(U32)(-1));
500 assert((size_t)(iend - base) <= (size_t)(U32)(-1));
501 ms->nextToUpdate = target;
502}
503
504void ZSTD_updateTree(ZSTD_matchState_t* ms, const BYTE* ip, const BYTE* iend) {
505 ZSTD_updateTree_internal(ms, ip, iend, ms->cParams.minMatch, ZSTD_noDict);
506}
507
510 ZSTD_match_t* matches, /* store result (found matches) in this table (presumed large enough) */
512 U32* nextToUpdate3,
513 const BYTE* const ip, const BYTE* const iLimit, const ZSTD_dictMode_e dictMode,
514 const U32 rep[ZSTD_REP_NUM],
515 U32 const ll0, /* tells if associated literal length is 0 or not. This value must be 0 or 1 */
516 const U32 lengthToBeat,
517 U32 const mls /* template */)
518{
519 const ZSTD_compressionParameters* const cParams = &ms->cParams;
520 U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1);
521 const BYTE* const base = ms->window.base;
522 U32 const current = (U32)(ip-base);
523 U32 const hashLog = cParams->hashLog;
524 U32 const minMatch = (mls==3) ? 3 : 4;
525 U32* const hashTable = ms->hashTable;
526 size_t const h = ZSTD_hashPtr(ip, hashLog, mls);
527 U32 matchIndex = hashTable[h];
528 U32* const bt = ms->chainTable;
529 U32 const btLog = cParams->chainLog - 1;
530 U32 const btMask= (1U << btLog) - 1;
531 size_t commonLengthSmaller=0, commonLengthLarger=0;
532 const BYTE* const dictBase = ms->window.dictBase;
533 U32 const dictLimit = ms->window.dictLimit;
534 const BYTE* const dictEnd = dictBase + dictLimit;
535 const BYTE* const prefixStart = base + dictLimit;
536 U32 const btLow = (btMask >= current) ? 0 : current - btMask;
537 U32 const windowLow = ZSTD_getLowestMatchIndex(ms, current, cParams->windowLog);
538 U32 const matchLow = windowLow ? windowLow : 1;
539 U32* smallerPtr = bt + 2*(current&btMask);
540 U32* largerPtr = bt + 2*(current&btMask) + 1;
541 U32 matchEndIdx = current+8+1; /* farthest referenced position of any match => detects repetitive patterns */
542 U32 dummy32; /* to be nullified at the end */
543 U32 mnum = 0;
544 U32 nbCompares = 1U << cParams->searchLog;
545
546 const ZSTD_matchState_t* dms = dictMode == ZSTD_dictMatchState ? ms->dictMatchState : NULL;
547 const ZSTD_compressionParameters* const dmsCParams =
548 dictMode == ZSTD_dictMatchState ? &dms->cParams : NULL;
549 const BYTE* const dmsBase = dictMode == ZSTD_dictMatchState ? dms->window.base : NULL;
550 const BYTE* const dmsEnd = dictMode == ZSTD_dictMatchState ? dms->window.nextSrc : NULL;
551 U32 const dmsHighLimit = dictMode == ZSTD_dictMatchState ? (U32)(dmsEnd - dmsBase) : 0;
552 U32 const dmsLowLimit = dictMode == ZSTD_dictMatchState ? dms->window.lowLimit : 0;
553 U32 const dmsIndexDelta = dictMode == ZSTD_dictMatchState ? windowLow - dmsHighLimit : 0;
554 U32 const dmsHashLog = dictMode == ZSTD_dictMatchState ? dmsCParams->hashLog : hashLog;
555 U32 const dmsBtLog = dictMode == ZSTD_dictMatchState ? dmsCParams->chainLog - 1 : btLog;
556 U32 const dmsBtMask = dictMode == ZSTD_dictMatchState ? (1U << dmsBtLog) - 1 : 0;
557 U32 const dmsBtLow = dictMode == ZSTD_dictMatchState && dmsBtMask < dmsHighLimit - dmsLowLimit ? dmsHighLimit - dmsBtMask : dmsLowLimit;
558
559 size_t bestLength = lengthToBeat-1;
560 DEBUGLOG(8, "ZSTD_insertBtAndGetAllMatches: current=%u", current);
561
562 /* check repCode */
563 assert(ll0 <= 1); /* necessarily 1 or 0 */
564 { U32 const lastR = ZSTD_REP_NUM + ll0;
565 U32 repCode;
566 for (repCode = ll0; repCode < lastR; repCode++) {
567 U32 const repOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode];
568 U32 const repIndex = current - repOffset;
569 U32 repLen = 0;
570 assert(current >= dictLimit);
571 if (repOffset-1 /* intentional overflow, discards 0 and -1 */ < current-dictLimit) { /* equivalent to `current > repIndex >= dictLimit` */
572 /* We must validate the repcode offset because when we're using a dictionary the
573 * valid offset range shrinks when the dictionary goes out of bounds.
574 */
575 if ((repIndex >= windowLow) & (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(ip - repOffset, minMatch))) {
576 repLen = (U32)ZSTD_count(ip+minMatch, ip+minMatch-repOffset, iLimit) + minMatch;
577 }
578 } else { /* repIndex < dictLimit || repIndex >= current */
579 const BYTE* const repMatch = dictMode == ZSTD_dictMatchState ?
580 dmsBase + repIndex - dmsIndexDelta :
581 dictBase + repIndex;
582 assert(current >= windowLow);
583 if ( dictMode == ZSTD_extDict
584 && ( ((repOffset-1) /*intentional overflow*/ < current - windowLow) /* equivalent to `current > repIndex >= windowLow` */
585 & (((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overlapping 2 memory segments */)
586 && (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(repMatch, minMatch)) ) {
587 repLen = (U32)ZSTD_count_2segments(ip+minMatch, repMatch+minMatch, iLimit, dictEnd, prefixStart) + minMatch;
588 }
589 if (dictMode == ZSTD_dictMatchState
590 && ( ((repOffset-1) /*intentional overflow*/ < current - (dmsLowLimit + dmsIndexDelta)) /* equivalent to `current > repIndex >= dmsLowLimit` */
591 & ((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overlapping 2 memory segments */
592 && (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(repMatch, minMatch)) ) {
593 repLen = (U32)ZSTD_count_2segments(ip+minMatch, repMatch+minMatch, iLimit, dmsEnd, prefixStart) + minMatch;
594 } }
595 /* save longer solution */
596 if (repLen > bestLength) {
597 DEBUGLOG(8, "found repCode %u (ll0:%u, offset:%u) of length %u",
598 repCode, ll0, repOffset, repLen);
599 bestLength = repLen;
600 matches[mnum].off = repCode - ll0;
601 matches[mnum].len = (U32)repLen;
602 mnum++;
603 if ( (repLen > sufficient_len)
604 | (ip+repLen == iLimit) ) { /* best possible */
605 return mnum;
606 } } } }
607
608 /* HC3 match finder */
609 if ((mls == 3) /*static*/ && (bestLength < mls)) {
610 U32 const matchIndex3 = ZSTD_insertAndFindFirstIndexHash3(ms, nextToUpdate3, ip);
611 if ((matchIndex3 >= matchLow)
612 & (current - matchIndex3 < (1<<18)) /*heuristic : longer distance likely too expensive*/ ) {
613 size_t mlen;
614 if ((dictMode == ZSTD_noDict) /*static*/ || (dictMode == ZSTD_dictMatchState) /*static*/ || (matchIndex3 >= dictLimit)) {
615 const BYTE* const match = base + matchIndex3;
616 mlen = ZSTD_count(ip, match, iLimit);
617 } else {
618 const BYTE* const match = dictBase + matchIndex3;
619 mlen = ZSTD_count_2segments(ip, match, iLimit, dictEnd, prefixStart);
620 }
621
622 /* save best solution */
623 if (mlen >= mls /* == 3 > bestLength */) {
624 DEBUGLOG(8, "found small match with hlog3, of length %u",
625 (U32)mlen);
626 bestLength = mlen;
627 assert(current > matchIndex3);
628 assert(mnum==0); /* no prior solution */
629 matches[0].off = (current - matchIndex3) + ZSTD_REP_MOVE;
630 matches[0].len = (U32)mlen;
631 mnum = 1;
632 if ( (mlen > sufficient_len) |
633 (ip+mlen == iLimit) ) { /* best possible length */
634 ms->nextToUpdate = current+1; /* skip insertion */
635 return 1;
636 } } }
637 /* no dictMatchState lookup: dicts don't have a populated HC3 table */
638 }
639
640 hashTable[h] = current; /* Update Hash Table */
641
642 while (nbCompares-- && (matchIndex >= matchLow)) {
643 U32* const nextPtr = bt + 2*(matchIndex & btMask);
644 const BYTE* match;
645 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
646 assert(current > matchIndex);
647
648 if ((dictMode == ZSTD_noDict) || (dictMode == ZSTD_dictMatchState) || (matchIndex+matchLength >= dictLimit)) {
649 assert(matchIndex+matchLength >= dictLimit); /* ensure the condition is correct when !extDict */
650 match = base + matchIndex;
651 if (matchIndex >= dictLimit) assert(memcmp(match, ip, matchLength) == 0); /* ensure early section of match is equal as expected */
652 matchLength += ZSTD_count(ip+matchLength, match+matchLength, iLimit);
653 } else {
654 match = dictBase + matchIndex;
655 assert(memcmp(match, ip, matchLength) == 0); /* ensure early section of match is equal as expected */
656 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iLimit, dictEnd, prefixStart);
657 if (matchIndex+matchLength >= dictLimit)
658 match = base + matchIndex; /* prepare for match[matchLength] read */
659 }
660
661 if (matchLength > bestLength) {
662 DEBUGLOG(8, "found match of length %u at distance %u (offCode=%u)",
663 (U32)matchLength, current - matchIndex, current - matchIndex + ZSTD_REP_MOVE);
664 assert(matchEndIdx > matchIndex);
665 if (matchLength > matchEndIdx - matchIndex)
666 matchEndIdx = matchIndex + (U32)matchLength;
667 bestLength = matchLength;
668 matches[mnum].off = (current - matchIndex) + ZSTD_REP_MOVE;
669 matches[mnum].len = (U32)matchLength;
670 mnum++;
671 if ( (matchLength > ZSTD_OPT_NUM)
672 | (ip+matchLength == iLimit) /* equal : no way to know if inf or sup */) {
673 if (dictMode == ZSTD_dictMatchState) nbCompares = 0; /* break should also skip searching dms */
674 break; /* drop, to preserve bt consistency (miss a little bit of compression) */
675 }
676 }
677
678 if (match[matchLength] < ip[matchLength]) {
679 /* match smaller than current */
680 *smallerPtr = matchIndex; /* update smaller idx */
681 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
682 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
683 smallerPtr = nextPtr+1; /* new candidate => larger than match, which was smaller than current */
684 matchIndex = nextPtr[1]; /* new matchIndex, larger than previous, closer to current */
685 } else {
686 *largerPtr = matchIndex;
687 commonLengthLarger = matchLength;
688 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
689 largerPtr = nextPtr;
690 matchIndex = nextPtr[0];
691 } }
692
693 *smallerPtr = *largerPtr = 0;
694
695 if (dictMode == ZSTD_dictMatchState && nbCompares) {
696 size_t const dmsH = ZSTD_hashPtr(ip, dmsHashLog, mls);
697 U32 dictMatchIndex = dms->hashTable[dmsH];
698 const U32* const dmsBt = dms->chainTable;
699 commonLengthSmaller = commonLengthLarger = 0;
700 while (nbCompares-- && (dictMatchIndex > dmsLowLimit)) {
701 const U32* const nextPtr = dmsBt + 2*(dictMatchIndex & dmsBtMask);
702 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
703 const BYTE* match = dmsBase + dictMatchIndex;
704 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iLimit, dmsEnd, prefixStart);
705 if (dictMatchIndex+matchLength >= dmsHighLimit)
706 match = base + dictMatchIndex + dmsIndexDelta; /* to prepare for next usage of match[matchLength] */
707
708 if (matchLength > bestLength) {
709 matchIndex = dictMatchIndex + dmsIndexDelta;
710 DEBUGLOG(8, "found dms match of length %u at distance %u (offCode=%u)",
711 (U32)matchLength, current - matchIndex, current - matchIndex + ZSTD_REP_MOVE);
712 if (matchLength > matchEndIdx - matchIndex)
713 matchEndIdx = matchIndex + (U32)matchLength;
714 bestLength = matchLength;
715 matches[mnum].off = (current - matchIndex) + ZSTD_REP_MOVE;
716 matches[mnum].len = (U32)matchLength;
717 mnum++;
718 if ( (matchLength > ZSTD_OPT_NUM)
719 | (ip+matchLength == iLimit) /* equal : no way to know if inf or sup */) {
720 break; /* drop, to guarantee consistency (miss a little bit of compression) */
721 }
722 }
723
724 if (dictMatchIndex <= dmsBtLow) { break; } /* beyond tree size, stop the search */
725 if (match[matchLength] < ip[matchLength]) {
726 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
727 dictMatchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
728 } else {
729 /* match is larger than current */
730 commonLengthLarger = matchLength;
731 dictMatchIndex = nextPtr[0];
732 }
733 }
734 }
735
736 assert(matchEndIdx > current+8);
737 ms->nextToUpdate = matchEndIdx - 8; /* skip repetitive patterns */
738 return mnum;
739}
740
741
743 ZSTD_match_t* matches, /* store result (match found, increasing size) in this table */
745 U32* nextToUpdate3,
746 const BYTE* ip, const BYTE* const iHighLimit, const ZSTD_dictMode_e dictMode,
747 const U32 rep[ZSTD_REP_NUM],
748 U32 const ll0,
749 U32 const lengthToBeat)
750{
751 const ZSTD_compressionParameters* const cParams = &ms->cParams;
752 U32 const matchLengthSearch = cParams->minMatch;
753 DEBUGLOG(8, "ZSTD_BtGetAllMatches");
754 if (ip < ms->window.base + ms->nextToUpdate) return 0; /* skipped area */
755 ZSTD_updateTree_internal(ms, ip, iHighLimit, matchLengthSearch, dictMode);
756 switch(matchLengthSearch)
757 {
758 case 3 : return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode, rep, ll0, lengthToBeat, 3);
759 default :
760 case 4 : return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode, rep, ll0, lengthToBeat, 4);
761 case 5 : return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode, rep, ll0, lengthToBeat, 5);
762 case 7 :
763 case 6 : return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode, rep, ll0, lengthToBeat, 6);
764 }
765}
766
767
768/*-*******************************
769* Optimal parser
770*********************************/
771
772
774{
775 return sol.litlen + sol.mlen;
776}
777
778#if 0 /* debug */
779
780static void
781listStats(const U32* table, int lastEltID)
782{
783 int const nbElts = lastEltID + 1;
784 int enb;
785 for (enb=0; enb < nbElts; enb++) {
786 (void)table;
787 /* RAWLOG(2, "%3i:%3i, ", enb, table[enb]); */
788 RAWLOG(2, "%4i,", table[enb]);
789 }
790 RAWLOG(2, " \n");
791}
792
793#endif
794
797 seqStore_t* seqStore,
798 U32 rep[ZSTD_REP_NUM],
799 const void* src, size_t srcSize,
800 const int optLevel,
801 const ZSTD_dictMode_e dictMode)
802{
803 optState_t* const optStatePtr = &ms->opt;
804 const BYTE* const istart = (const BYTE*)src;
805 const BYTE* ip = istart;
806 const BYTE* anchor = istart;
807 const BYTE* const iend = istart + srcSize;
808 const BYTE* const ilimit = iend - 8;
809 const BYTE* const base = ms->window.base;
810 const BYTE* const prefixStart = base + ms->window.dictLimit;
811 const ZSTD_compressionParameters* const cParams = &ms->cParams;
812
813 U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1);
814 U32 const minMatch = (cParams->minMatch == 3) ? 3 : 4;
815 U32 nextToUpdate3 = ms->nextToUpdate;
816
817 ZSTD_optimal_t* const opt = optStatePtr->priceTable;
818 ZSTD_match_t* const matches = optStatePtr->matchTable;
819 ZSTD_optimal_t lastSequence;
820
821 /* init */
822 DEBUGLOG(5, "ZSTD_compressBlock_opt_generic: current=%u, prefix=%u, nextToUpdate=%u",
823 (U32)(ip - base), ms->window.dictLimit, ms->nextToUpdate);
824 assert(optLevel <= 2);
825 ZSTD_rescaleFreqs(optStatePtr, (const BYTE*)src, srcSize, optLevel);
826 ip += (ip==prefixStart);
827
828 /* Match Loop */
829 while (ip < ilimit) {
830 U32 cur, last_pos = 0;
831
832 /* find first match */
833 { U32 const litlen = (U32)(ip - anchor);
834 U32 const ll0 = !litlen;
835 U32 const nbMatches = ZSTD_BtGetAllMatches(matches, ms, &nextToUpdate3, ip, iend, dictMode, rep, ll0, minMatch);
836 if (!nbMatches) { ip++; continue; }
837
838 /* initialize opt[0] */
839 { U32 i ; for (i=0; i<ZSTD_REP_NUM; i++) opt[0].rep[i] = rep[i]; }
840 opt[0].mlen = 0; /* means is_a_literal */
841 opt[0].litlen = litlen;
842 /* We don't need to include the actual price of the literals because
843 * it is static for the duration of the forward pass, and is included
844 * in every price. We include the literal length to avoid negative
845 * prices when we subtract the previous literal length.
846 */
847 opt[0].price = ZSTD_litLengthPrice(litlen, optStatePtr, optLevel);
848
849 /* large match -> immediate encoding */
850 { U32 const maxML = matches[nbMatches-1].len;
851 U32 const maxOffset = matches[nbMatches-1].off;
852 DEBUGLOG(6, "found %u matches of maxLength=%u and maxOffCode=%u at cPos=%u => start new series",
853 nbMatches, maxML, maxOffset, (U32)(ip-prefixStart));
854
855 if (maxML > sufficient_len) {
856 lastSequence.litlen = litlen;
857 lastSequence.mlen = maxML;
858 lastSequence.off = maxOffset;
859 DEBUGLOG(6, "large match (%u>%u), immediate encoding",
860 maxML, sufficient_len);
861 cur = 0;
862 last_pos = ZSTD_totalLen(lastSequence);
863 goto _shortestPath;
864 } }
865
866 /* set prices for first matches starting position == 0 */
867 { U32 const literalsPrice = opt[0].price + ZSTD_litLengthPrice(0, optStatePtr, optLevel);
868 U32 pos;
869 U32 matchNb;
870 for (pos = 1; pos < minMatch; pos++) {
871 opt[pos].price = ZSTD_MAX_PRICE; /* mlen, litlen and price will be fixed during forward scanning */
872 }
873 for (matchNb = 0; matchNb < nbMatches; matchNb++) {
874 U32 const offset = matches[matchNb].off;
875 U32 const end = matches[matchNb].len;
876 for ( ; pos <= end ; pos++ ) {
877 U32 const matchPrice = ZSTD_getMatchPrice(offset, pos, optStatePtr, optLevel);
878 U32 const sequencePrice = literalsPrice + matchPrice;
879 DEBUGLOG(7, "rPos:%u => set initial price : %.2f",
880 pos, ZSTD_fCost(sequencePrice));
881 opt[pos].mlen = pos;
882 opt[pos].off = offset;
883 opt[pos].litlen = litlen;
884 opt[pos].price = sequencePrice;
885 } }
886 last_pos = pos-1;
887 }
888 }
889
890 /* check further positions */
891 for (cur = 1; cur <= last_pos; cur++) {
892 const BYTE* const inr = ip + cur;
894 DEBUGLOG(7, "cPos:%zi==rPos:%u", inr-istart, cur)
895
896 /* Fix current position with one literal if cheaper */
897 { U32 const litlen = (opt[cur-1].mlen == 0) ? opt[cur-1].litlen + 1 : 1;
898 int const price = opt[cur-1].price
899 + ZSTD_rawLiteralsCost(ip+cur-1, 1, optStatePtr, optLevel)
900 + ZSTD_litLengthPrice(litlen, optStatePtr, optLevel)
901 - ZSTD_litLengthPrice(litlen-1, optStatePtr, optLevel);
902 assert(price < 1000000000); /* overflow check */
903 if (price <= opt[cur].price) {
904 DEBUGLOG(7, "cPos:%zi==rPos:%u : better price (%.2f<=%.2f) using literal (ll==%u) (hist:%u,%u,%u)",
905 inr-istart, cur, ZSTD_fCost(price), ZSTD_fCost(opt[cur].price), litlen,
906 opt[cur-1].rep[0], opt[cur-1].rep[1], opt[cur-1].rep[2]);
907 opt[cur].mlen = 0;
908 opt[cur].off = 0;
909 opt[cur].litlen = litlen;
910 opt[cur].price = price;
911 } else {
912 DEBUGLOG(7, "cPos:%zi==rPos:%u : literal would cost more (%.2f>%.2f) (hist:%u,%u,%u)",
913 inr-istart, cur, ZSTD_fCost(price), ZSTD_fCost(opt[cur].price),
914 opt[cur].rep[0], opt[cur].rep[1], opt[cur].rep[2]);
915 }
916 }
917
918 /* Set the repcodes of the current position. We must do it here
919 * because we rely on the repcodes of the 2nd to last sequence being
920 * correct to set the next chunks repcodes during the backward
921 * traversal.
922 */
923 ZSTD_STATIC_ASSERT(sizeof(opt[cur].rep) == sizeof(repcodes_t));
924 assert(cur >= opt[cur].mlen);
925 if (opt[cur].mlen != 0) {
926 U32 const prev = cur - opt[cur].mlen;
927 repcodes_t newReps = ZSTD_updateRep(opt[prev].rep, opt[cur].off, opt[cur].litlen==0);
928 memcpy(opt[cur].rep, &newReps, sizeof(repcodes_t));
929 } else {
930 memcpy(opt[cur].rep, opt[cur - 1].rep, sizeof(repcodes_t));
931 }
932
933 /* last match must start at a minimum distance of 8 from oend */
934 if (inr > ilimit) continue;
935
936 if (cur == last_pos) break;
937
938 if ( (optLevel==0) /*static_test*/
939 && (opt[cur+1].price <= opt[cur].price + (BITCOST_MULTIPLIER/2)) ) {
940 DEBUGLOG(7, "move to next rPos:%u : price is <=", cur+1);
941 continue; /* skip unpromising positions; about ~+6% speed, -0.01 ratio */
942 }
943
944 { U32 const ll0 = (opt[cur].mlen != 0);
945 U32 const litlen = (opt[cur].mlen == 0) ? opt[cur].litlen : 0;
946 U32 const previousPrice = opt[cur].price;
947 U32 const basePrice = previousPrice + ZSTD_litLengthPrice(0, optStatePtr, optLevel);
948 U32 const nbMatches = ZSTD_BtGetAllMatches(matches, ms, &nextToUpdate3, inr, iend, dictMode, opt[cur].rep, ll0, minMatch);
949 U32 matchNb;
950 if (!nbMatches) {
951 DEBUGLOG(7, "rPos:%u : no match found", cur);
952 continue;
953 }
954
955 { U32 const maxML = matches[nbMatches-1].len;
956 DEBUGLOG(7, "cPos:%zi==rPos:%u, found %u matches, of maxLength=%u",
957 inr-istart, cur, nbMatches, maxML);
958
959 if ( (maxML > sufficient_len)
960 || (cur + maxML >= ZSTD_OPT_NUM) ) {
961 lastSequence.mlen = maxML;
962 lastSequence.off = matches[nbMatches-1].off;
963 lastSequence.litlen = litlen;
964 cur -= (opt[cur].mlen==0) ? opt[cur].litlen : 0; /* last sequence is actually only literals, fix cur to last match - note : may underflow, in which case, it's first sequence, and it's okay */
965 last_pos = cur + ZSTD_totalLen(lastSequence);
966 if (cur > ZSTD_OPT_NUM) cur = 0; /* underflow => first match */
967 goto _shortestPath;
968 } }
969
970 /* set prices using matches found at position == cur */
971 for (matchNb = 0; matchNb < nbMatches; matchNb++) {
972 U32 const offset = matches[matchNb].off;
973 U32 const lastML = matches[matchNb].len;
974 U32 const startML = (matchNb>0) ? matches[matchNb-1].len+1 : minMatch;
975 U32 mlen;
976
977 DEBUGLOG(7, "testing match %u => offCode=%4u, mlen=%2u, llen=%2u",
978 matchNb, matches[matchNb].off, lastML, litlen);
979
980 for (mlen = lastML; mlen >= startML; mlen--) { /* scan downward */
981 U32 const pos = cur + mlen;
982 int const price = basePrice + ZSTD_getMatchPrice(offset, mlen, optStatePtr, optLevel);
983
984 if ((pos > last_pos) || (price < opt[pos].price)) {
985 DEBUGLOG(7, "rPos:%u (ml=%2u) => new better price (%.2f<%.2f)",
986 pos, mlen, ZSTD_fCost(price), ZSTD_fCost(opt[pos].price));
987 while (last_pos < pos) { opt[last_pos+1].price = ZSTD_MAX_PRICE; last_pos++; } /* fill empty positions */
988 opt[pos].mlen = mlen;
989 opt[pos].off = offset;
990 opt[pos].litlen = litlen;
991 opt[pos].price = price;
992 } else {
993 DEBUGLOG(7, "rPos:%u (ml=%2u) => new price is worse (%.2f>=%.2f)",
994 pos, mlen, ZSTD_fCost(price), ZSTD_fCost(opt[pos].price));
995 if (optLevel==0) break; /* early update abort; gets ~+10% speed for about -0.01 ratio loss */
996 }
997 } } }
998 } /* for (cur = 1; cur <= last_pos; cur++) */
999
1000 lastSequence = opt[last_pos];
1001 cur = last_pos > ZSTD_totalLen(lastSequence) ? last_pos - ZSTD_totalLen(lastSequence) : 0; /* single sequence, and it starts before `ip` */
1002 assert(cur < ZSTD_OPT_NUM); /* control overflow*/
1003
1004_shortestPath: /* cur, last_pos, best_mlen, best_off have to be set */
1005 assert(opt[0].mlen == 0);
1006
1007 /* Set the next chunk's repcodes based on the repcodes of the beginning
1008 * of the last match, and the last sequence. This avoids us having to
1009 * update them while traversing the sequences.
1010 */
1011 if (lastSequence.mlen != 0) {
1012 repcodes_t reps = ZSTD_updateRep(opt[cur].rep, lastSequence.off, lastSequence.litlen==0);
1013 memcpy(rep, &reps, sizeof(reps));
1014 } else {
1015 memcpy(rep, opt[cur].rep, sizeof(repcodes_t));
1016 }
1017
1018 { U32 const storeEnd = cur + 1;
1019 U32 storeStart = storeEnd;
1020 U32 seqPos = cur;
1021
1022 DEBUGLOG(6, "start reverse traversal (last_pos:%u, cur:%u)",
1023 last_pos, cur); (void)last_pos;
1024 assert(storeEnd < ZSTD_OPT_NUM);
1025 DEBUGLOG(6, "last sequence copied into pos=%u (llen=%u,mlen=%u,ofc=%u)",
1026 storeEnd, lastSequence.litlen, lastSequence.mlen, lastSequence.off);
1027 opt[storeEnd] = lastSequence;
1028 while (seqPos > 0) {
1029 U32 const backDist = ZSTD_totalLen(opt[seqPos]);
1030 storeStart--;
1031 DEBUGLOG(6, "sequence from rPos=%u copied into pos=%u (llen=%u,mlen=%u,ofc=%u)",
1032 seqPos, storeStart, opt[seqPos].litlen, opt[seqPos].mlen, opt[seqPos].off);
1033 opt[storeStart] = opt[seqPos];
1034 seqPos = (seqPos > backDist) ? seqPos - backDist : 0;
1035 }
1036
1037 /* save sequences */
1038 DEBUGLOG(6, "sending selected sequences into seqStore")
1039 { U32 storePos;
1040 for (storePos=storeStart; storePos <= storeEnd; storePos++) {
1041 U32 const llen = opt[storePos].litlen;
1042 U32 const mlen = opt[storePos].mlen;
1043 U32 const offCode = opt[storePos].off;
1044 U32 const advance = llen + mlen;
1045 DEBUGLOG(6, "considering seq starting at %zi, llen=%u, mlen=%u",
1046 anchor - istart, (unsigned)llen, (unsigned)mlen);
1047
1048 if (mlen==0) { /* only literals => must be last "sequence", actually starting a new stream of sequences */
1049 assert(storePos == storeEnd); /* must be last sequence */
1050 ip = anchor + llen; /* last "sequence" is a bunch of literals => don't progress anchor */
1051 continue; /* will finish */
1052 }
1053
1054 assert(anchor + llen <= iend);
1055 ZSTD_updateStats(optStatePtr, llen, anchor, offCode, mlen);
1056 ZSTD_storeSeq(seqStore, llen, anchor, iend, offCode, mlen-MINMATCH);
1057 anchor += advance;
1058 ip = anchor;
1059 } }
1060 ZSTD_setBasePrices(optStatePtr, optLevel);
1061 }
1062 } /* while (ip < ilimit) */
1063
1064 /* Return the last literals size */
1065 return (size_t)(iend - anchor);
1066}
1067
1068
1070 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1071 const void* src, size_t srcSize)
1072{
1073 DEBUGLOG(5, "ZSTD_compressBlock_btopt");
1074 return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 0 /*optLevel*/, ZSTD_noDict);
1075}
1076
1077
1078/* used in 2-pass strategy */
1079static U32 ZSTD_upscaleStat(unsigned* table, U32 lastEltIndex, int bonus)
1080{
1081 U32 s, sum=0;
1082 assert(ZSTD_FREQ_DIV+bonus >= 0);
1083 for (s=0; s<lastEltIndex+1; s++) {
1084 table[s] <<= ZSTD_FREQ_DIV+bonus;
1085 table[s]--;
1086 sum += table[s];
1087 }
1088 return sum;
1089}
1090
1091/* used in 2-pass strategy */
1093{
1094 if (ZSTD_compressedLiterals(optPtr))
1095 optPtr->litSum = ZSTD_upscaleStat(optPtr->litFreq, MaxLit, 0);
1096 optPtr->litLengthSum = ZSTD_upscaleStat(optPtr->litLengthFreq, MaxLL, 0);
1098 optPtr->offCodeSum = ZSTD_upscaleStat(optPtr->offCodeFreq, MaxOff, 0);
1099}
1100
1101/* ZSTD_initStats_ultra():
1102 * make a first compression pass, just to seed stats with more accurate starting values.
1103 * only works on first block, with no dictionary and no ldm.
1104 * this function cannot error, hence its contract must be respected.
1105 */
1106static void
1108 seqStore_t* seqStore,
1109 U32 rep[ZSTD_REP_NUM],
1110 const void* src, size_t srcSize)
1111{
1112 U32 tmpRep[ZSTD_REP_NUM]; /* updated rep codes will sink here */
1113 memcpy(tmpRep, rep, sizeof(tmpRep));
1114
1115 DEBUGLOG(4, "ZSTD_initStats_ultra (srcSize=%zu)", srcSize);
1116 assert(ms->opt.litLengthSum == 0); /* first block */
1117 assert(seqStore->sequences == seqStore->sequencesStart); /* no ldm */
1118 assert(ms->window.dictLimit == ms->window.lowLimit); /* no dictionary */
1119 assert(ms->window.dictLimit - ms->nextToUpdate <= 1); /* no prefix (note: intentional overflow, defined as 2-complement) */
1120
1121 ZSTD_compressBlock_opt_generic(ms, seqStore, tmpRep, src, srcSize, 2 /*optLevel*/, ZSTD_noDict); /* generate stats into ms->opt*/
1122
1123 /* invalidate first scan from history */
1124 ZSTD_resetSeqStore(seqStore);
1125 ms->window.base -= srcSize;
1126 ms->window.dictLimit += (U32)srcSize;
1127 ms->window.lowLimit = ms->window.dictLimit;
1128 ms->nextToUpdate = ms->window.dictLimit;
1129
1130 /* re-inforce weight of collected statistics */
1131 ZSTD_upscaleStats(&ms->opt);
1132}
1133
1135 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1136 const void* src, size_t srcSize)
1137{
1138 DEBUGLOG(5, "ZSTD_compressBlock_btultra (srcSize=%zu)", srcSize);
1139 return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /*optLevel*/, ZSTD_noDict);
1140}
1141
1143 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1144 const void* src, size_t srcSize)
1145{
1146 U32 const current = (U32)((const BYTE*)src - ms->window.base);
1147 DEBUGLOG(5, "ZSTD_compressBlock_btultra2 (srcSize=%zu)", srcSize);
1148
1149 /* 2-pass strategy:
1150 * this strategy makes a first pass over first block to collect statistics
1151 * and seed next round's statistics with it.
1152 * After 1st pass, function forgets everything, and starts a new block.
1153 * Consequently, this can only work if no data has been previously loaded in tables,
1154 * aka, no dictionary, no prefix, no ldm preprocessing.
1155 * The compression ratio gain is generally small (~0.5% on first block),
1156 * the cost is 2x cpu time on first block. */
1157 assert(srcSize <= ZSTD_BLOCKSIZE_MAX);
1158 if ( (ms->opt.litLengthSum==0) /* first block */
1159 && (seqStore->sequences == seqStore->sequencesStart) /* no ldm */
1160 && (ms->window.dictLimit == ms->window.lowLimit) /* no dictionary */
1161 && (current == ms->window.dictLimit) /* start of frame, nothing already loaded nor skipped */
1162 && (srcSize > ZSTD_PREDEF_THRESHOLD)
1163 ) {
1164 ZSTD_initStats_ultra(ms, seqStore, rep, src, srcSize);
1165 }
1166
1167 return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /*optLevel*/, ZSTD_noDict);
1168}
1169
1171 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1172 const void* src, size_t srcSize)
1173{
1174 return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 0 /*optLevel*/, ZSTD_dictMatchState);
1175}
1176
1178 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1179 const void* src, size_t srcSize)
1180{
1181 return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /*optLevel*/, ZSTD_dictMatchState);
1182}
1183
1185 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1186 const void* src, size_t srcSize)
1187{
1188 return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 0 /*optLevel*/, ZSTD_extDict);
1189}
1190
1192 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1193 const void* src, size_t srcSize)
1194{
1195 return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /*optLevel*/, ZSTD_extDict);
1196}
1197
1198/* note : no btultra2 variant for extDict nor dictMatchState,
1199 * because btultra2 is not meant to work with dictionaries
1200 * and is only specific for the first block (no prefix) */
_STLP_MOVE_TO_STD_NAMESPACE void _STLP_CALL advance(_InputIterator &__i, _Distance __n)
int memcmp(void *Buffer1, void *Buffer2, ACPI_SIZE Count)
Definition: utclib.c:112
#define MIN(x, y)
Definition: rdesktop.h:171
#define MAX(x, y)
Definition: rdesktop.h:175
void mls(int argc, const char *argv[])
Definition: cmds.c:1168
w ll
Definition: byte_order.h:167
#define NULL
Definition: types.h:112
unsigned int idx
Definition: utils.c:41
#define assert(x)
Definition: debug.h:53
#define DEBUGLOG(l,...)
Definition: debug.h:106
#define RAWLOG(l,...)
Definition: debug.h:105
MEM_STATIC U32 MEM_read32(const void *memPtr)
Definition: mem.h:242
MEM_STATIC unsigned MEM_isLittleEndian(void)
Definition: mem.h:186
#define MEM_STATIC
Definition: mem.h:39
FxCollectionEntry * cur
GLdouble s
Definition: gl.h:2039
GLuint GLuint end
Definition: gl.h:1545
GLenum src
Definition: glext.h:6340
GLuint GLsizei GLsizei * length
Definition: glext.h:6040
GLenum GLsizei len
Definition: glext.h:6722
GLintptr offset
Definition: glext.h:5920
GLenum target
Definition: glext.h:7315
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
unsigned HIST_count_simple(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
Definition: hist.c:29
U32 HUF_getNbBits(const void *symbolTable, U32 symbolValue)
Definition: huf_compress.c:200
#define matches(FN)
Definition: match.h:70
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
struct task_struct * current
Definition: linux.c:32
static IHTMLWindow2 * window
Definition: events.c:77
static int sum(int x_, int y_)
Definition: ptr2_test.cpp:35
weight
Definition: sortkey.c:157
FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)]
FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)]
FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)]
U32 CTable[HUF_CTABLE_SIZE_U32(255)]
ZSTD_compressionParameters cParams
const ZSTD_matchState_t * dictMatchState
Definition: dhcpd.h:62
Definition: match.c:28
ZSTD_match_t * matchTable
ZSTD_optimal_t * priceTable
unsigned * offCodeFreq
ZSTD_OptPrice_e priceType
unsigned * matchLengthFreq
ZSTD_literalCompressionMode_e literalCompressionMode
unsigned * litLengthFreq
const ZSTD_entropyCTables_t * symbolCosts
seqDef * sequencesStart
seqDef * sequences
Definition: stat.h:55
unsigned char BYTE
Definition: xxhash.c:193
#define FORCE_INLINE_TEMPLATE
Definition: xxhash.c:172
unsigned int U32
Definition: xxhash.c:195
#define ZSTD_BLOCKSIZE_MAX
Definition: zstd.h:104
void ZSTD_resetSeqStore(seqStore_t *ssPtr)
MEM_STATIC U32 ZSTD_MLcode(U32 mlBase)
MEM_STATIC size_t ZSTD_count_2segments(const BYTE *ip, const BYTE *match, const BYTE *iEnd, const BYTE *mEnd, const BYTE *iStart)
MEM_STATIC repcodes_t ZSTD_updateRep(U32 const rep[3], U32 const offset, U32 const ll0)
MEM_STATIC size_t ZSTD_hashPtr(const void *p, U32 hBits, U32 mls)
MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
MEM_STATIC U32 ZSTD_getLowestMatchIndex(const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
MEM_STATIC size_t ZSTD_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *const pInLimit)
MEM_STATIC size_t ZSTD_hash3Ptr(const void *ptr, U32 h)
HINT_INLINE UNUSED_ATTR void ZSTD_storeSeq(seqStore_t *seqStorePtr, size_t litLength, const BYTE *literals, const BYTE *litLimit, U32 offCode, size_t mlBase)
@ ZSTD_dictMatchState
#define MaxLit
#define ZSTD_OPT_NUM
#define MINMATCH
#define MaxLL
#define MaxML
MEM_STATIC U32 ZSTD_highbit32(U32 val)
#define ZSTD_REP_MOVE
static const U32 ML_bits[MaxML+1]
static const U32 LL_bits[MaxLL+1]
#define MaxOff
#define ZSTD_STATIC_ASSERT(c)
Definition: zstd_internal.h:45
#define ZSTD_REP_NUM
#define BITCOST_ACCURACY
Definition: zstd_opt.c:36
MEM_STATIC U32 ZSTD_fracWeight(U32 rawStat)
Definition: zstd_opt.c:46
FORCE_INLINE_TEMPLATE U32 ZSTD_getMatchPrice(U32 const offset, U32 const matchLength, const optState_t *const optPtr, int const optLevel)
Definition: zstd_opt.c:257
FORCE_INLINE_TEMPLATE U32 ZSTD_insertBtAndGetAllMatches(ZSTD_match_t *matches, ZSTD_matchState_t *ms, U32 *nextToUpdate3, const BYTE *const ip, const BYTE *const iLimit, const ZSTD_dictMode_e dictMode, const U32 rep[ZSTD_REP_NUM], U32 const ll0, const U32 lengthToBeat, U32 const mls)
Definition: zstd_opt.c:509
static void ZSTD_rescaleFreqs(optState_t *const optPtr, const BYTE *const src, size_t const srcSize, int const optLevel)
Definition: zstd_opt.c:104
static U32 ZSTD_upscaleStat(unsigned *table, U32 lastEltIndex, int bonus)
Definition: zstd_opt.c:1079
#define WEIGHT(stat, opt)
Definition: zstd_opt.c:38
MEM_STATIC U32 ZSTD_bitWeight(U32 stat)
Definition: zstd_opt.c:41
size_t ZSTD_compressBlock_btopt_extDict(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1184
#define ZSTD_FREQ_DIV
Definition: zstd_opt.c:17
#define ZSTD_LITFREQ_ADD
Definition: zstd_opt.c:16
FORCE_INLINE_TEMPLATE size_t ZSTD_compressBlock_opt_generic(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize, const int optLevel, const ZSTD_dictMode_e dictMode)
Definition: zstd_opt.c:796
size_t ZSTD_compressBlock_btopt(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1069
static U32 ZSTD_insertBt1(ZSTD_matchState_t *ms, const BYTE *const ip, const BYTE *const iend, U32 const mls, const int extDict)
Definition: zstd_opt.c:369
static void ZSTD_setBasePrices(optState_t *optPtr, int optLevel)
Definition: zstd_opt.c:72
static U32 ZSTD_insertAndFindFirstIndexHash3(ZSTD_matchState_t *ms, U32 *nextToUpdate3, const BYTE *const ip)
Definition: zstd_opt.c:341
#define BITCOST_MULTIPLIER
Definition: zstd_opt.c:37
MEM_STATIC U32 ZSTD_readMINMATCH(const void *memPtr, U32 length)
Definition: zstd_opt.c:325
static U32 ZSTD_litLengthPrice(U32 const litLength, const optState_t *const optPtr, int optLevel)
Definition: zstd_opt.c:240
void ZSTD_updateTree(ZSTD_matchState_t *ms, const BYTE *ip, const BYTE *iend)
Definition: zstd_opt.c:504
static U32 ZSTD_downscaleStat(unsigned *table, U32 lastEltIndex, int malus)
Definition: zstd_opt.c:85
static void ZSTD_updateStats(optState_t *const optPtr, U32 litLength, const BYTE *literals, U32 offsetCode, U32 matchLength)
Definition: zstd_opt.c:288
MEM_STATIC void ZSTD_upscaleStats(optState_t *optPtr)
Definition: zstd_opt.c:1092
FORCE_INLINE_TEMPLATE void ZSTD_updateTree_internal(ZSTD_matchState_t *ms, const BYTE *const ip, const BYTE *const iend, const U32 mls, const ZSTD_dictMode_e dictMode)
Definition: zstd_opt.c:483
static U32 ZSTD_totalLen(ZSTD_optimal_t sol)
Definition: zstd_opt.c:773
static U32 ZSTD_rawLiteralsCost(const BYTE *const literals, U32 const litLength, const optState_t *const optPtr, int optLevel)
Definition: zstd_opt.c:215
#define ZSTD_MAX_PRICE
Definition: zstd_opt.c:18
size_t ZSTD_compressBlock_btultra_dictMatchState(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1177
static int ZSTD_compressedLiterals(optState_t const *const optPtr)
Definition: zstd_opt.c:67
size_t ZSTD_compressBlock_btultra_extDict(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1191
size_t ZSTD_compressBlock_btultra2(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1142
size_t ZSTD_compressBlock_btultra(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1134
size_t ZSTD_compressBlock_btopt_dictMatchState(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1170
FORCE_INLINE_TEMPLATE U32 ZSTD_BtGetAllMatches(ZSTD_match_t *matches, ZSTD_matchState_t *ms, U32 *nextToUpdate3, const BYTE *ip, const BYTE *const iHighLimit, const ZSTD_dictMode_e dictMode, const U32 rep[ZSTD_REP_NUM], U32 const ll0, U32 const lengthToBeat)
Definition: zstd_opt.c:742
static void ZSTD_initStats_ultra(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize)
Definition: zstd_opt.c:1107
#define ZSTD_PREDEF_THRESHOLD
Definition: zstd_opt.c:20