2 * Copyright (c) 2016-present, Przemyslaw Skibinski, Yann Collet, Facebook, Inc.
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.
11 #include "zstd_compress_internal.h"
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)
21 /*-*************************************
22 * Price functions for optimal parser
23 ***************************************/
25 #if 0 /* approximation at bit level */
26 # define BITCOST_ACCURACY 0
27 # define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
28 # define WEIGHT(stat) ((void)opt, ZSTD_bitWeight(stat))
29 #elif 0 /* fractional bit accuracy */
30 # define BITCOST_ACCURACY 8
31 # define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
32 # define WEIGHT(stat,opt) ((void)opt, ZSTD_fracWeight(stat))
33 #else /* opt==approx, ultra==accurate */
34 # define BITCOST_ACCURACY 8
35 # define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
36 # define WEIGHT(stat,opt) (opt ? ZSTD_fracWeight(stat) : ZSTD_bitWeight(stat))
39 MEM_STATIC U32
ZSTD_bitWeight(U32 stat
)
41 return (ZSTD_highbit32(stat
+1) * BITCOST_MULTIPLIER
);
44 MEM_STATIC U32
ZSTD_fracWeight(U32 rawStat
)
46 U32
const stat
= rawStat
+ 1;
47 U32
const hb
= ZSTD_highbit32(stat
);
48 U32
const BWeight
= hb
* BITCOST_MULTIPLIER
;
49 U32
const FWeight
= (stat
<< BITCOST_ACCURACY
) >> hb
;
50 U32
const weight
= BWeight
+ FWeight
;
51 assert(hb
+ BITCOST_ACCURACY
< 31);
55 /* debugging function, @return price in bytes */
56 MEM_STATIC
double ZSTD_fCost(U32 price
)
58 return (double)price
/ (BITCOST_MULTIPLIER
*8);
61 static void ZSTD_setBasePrices(optState_t
* optPtr
, int optLevel
)
63 optPtr
->litSumBasePrice
= WEIGHT(optPtr
->litSum
, optLevel
);
64 optPtr
->litLengthSumBasePrice
= WEIGHT(optPtr
->litLengthSum
, optLevel
);
65 optPtr
->matchLengthSumBasePrice
= WEIGHT(optPtr
->matchLengthSum
, optLevel
);
66 optPtr
->offCodeSumBasePrice
= WEIGHT(optPtr
->offCodeSum
, optLevel
);
70 static U32
ZSTD_downscaleStat(U32
* table
, U32 lastEltIndex
, int malus
)
73 assert(ZSTD_FREQ_DIV
+malus
> 0 && ZSTD_FREQ_DIV
+malus
< 31);
74 for (s
=0; s
<=lastEltIndex
; s
++) {
75 table
[s
] = 1 + (table
[s
] >> (ZSTD_FREQ_DIV
+malus
));
81 static void ZSTD_rescaleFreqs(optState_t
* const optPtr
,
82 const BYTE
* const src
, size_t const srcSize
,
85 optPtr
->priceType
= zop_dynamic
;
87 if (optPtr
->litLengthSum
== 0) { /* first block : init */
88 if (srcSize
<= 1024) /* heuristic */
89 optPtr
->priceType
= zop_predef
;
91 assert(optPtr
->symbolCosts
!= NULL
);
92 if (optPtr
->symbolCosts
->huf
.repeatMode
== HUF_repeat_valid
) { /* huffman table presumed generated by dictionary */
93 optPtr
->priceType
= zop_dynamic
;
95 assert(optPtr
->litFreq
!= NULL
);
98 for (lit
=0; lit
<=MaxLit
; lit
++) {
99 U32
const scaleLog
= 11; /* scale to 2K */
100 U32
const bitCost
= HUF_getNbBits(optPtr
->symbolCosts
->huf
.CTable
, lit
);
101 assert(bitCost
<= scaleLog
);
102 optPtr
->litFreq
[lit
] = bitCost
? 1 << (scaleLog
-bitCost
) : 1 /*minimum to calculate cost*/;
103 optPtr
->litSum
+= optPtr
->litFreq
[lit
];
107 FSE_CState_t llstate
;
108 FSE_initCState(&llstate
, optPtr
->symbolCosts
->fse
.litlengthCTable
);
109 optPtr
->litLengthSum
= 0;
110 for (ll
=0; ll
<=MaxLL
; ll
++) {
111 U32
const scaleLog
= 10; /* scale to 1K */
112 U32
const bitCost
= FSE_getMaxNbBits(llstate
.symbolTT
, ll
);
113 assert(bitCost
< scaleLog
);
114 optPtr
->litLengthFreq
[ll
] = bitCost
? 1 << (scaleLog
-bitCost
) : 1 /*minimum to calculate cost*/;
115 optPtr
->litLengthSum
+= optPtr
->litLengthFreq
[ll
];
119 FSE_CState_t mlstate
;
120 FSE_initCState(&mlstate
, optPtr
->symbolCosts
->fse
.matchlengthCTable
);
121 optPtr
->matchLengthSum
= 0;
122 for (ml
=0; ml
<=MaxML
; ml
++) {
123 U32
const scaleLog
= 10;
124 U32
const bitCost
= FSE_getMaxNbBits(mlstate
.symbolTT
, ml
);
125 assert(bitCost
< scaleLog
);
126 optPtr
->matchLengthFreq
[ml
] = bitCost
? 1 << (scaleLog
-bitCost
) : 1 /*minimum to calculate cost*/;
127 optPtr
->matchLengthSum
+= optPtr
->matchLengthFreq
[ml
];
131 FSE_CState_t ofstate
;
132 FSE_initCState(&ofstate
, optPtr
->symbolCosts
->fse
.offcodeCTable
);
133 optPtr
->offCodeSum
= 0;
134 for (of
=0; of
<=MaxOff
; of
++) {
135 U32
const scaleLog
= 10;
136 U32
const bitCost
= FSE_getMaxNbBits(ofstate
.symbolTT
, of
);
137 assert(bitCost
< scaleLog
);
138 optPtr
->offCodeFreq
[of
] = bitCost
? 1 << (scaleLog
-bitCost
) : 1 /*minimum to calculate cost*/;
139 optPtr
->offCodeSum
+= optPtr
->offCodeFreq
[of
];
142 } else { /* not a dictionary */
144 assert(optPtr
->litFreq
!= NULL
);
145 { unsigned lit
= MaxLit
;
146 HIST_count_simple(optPtr
->litFreq
, &lit
, src
, srcSize
); /* use raw first block to init statistics */
148 optPtr
->litSum
= ZSTD_downscaleStat(optPtr
->litFreq
, MaxLit
, 1);
151 for (ll
=0; ll
<=MaxLL
; ll
++)
152 optPtr
->litLengthFreq
[ll
] = 1;
154 optPtr
->litLengthSum
= MaxLL
+1;
157 for (ml
=0; ml
<=MaxML
; ml
++)
158 optPtr
->matchLengthFreq
[ml
] = 1;
160 optPtr
->matchLengthSum
= MaxML
+1;
163 for (of
=0; of
<=MaxOff
; of
++)
164 optPtr
->offCodeFreq
[of
] = 1;
166 optPtr
->offCodeSum
= MaxOff
+1;
170 } else { /* new block : re-use previous statistics, scaled down */
172 optPtr
->litSum
= ZSTD_downscaleStat(optPtr
->litFreq
, MaxLit
, 1);
173 optPtr
->litLengthSum
= ZSTD_downscaleStat(optPtr
->litLengthFreq
, MaxLL
, 0);
174 optPtr
->matchLengthSum
= ZSTD_downscaleStat(optPtr
->matchLengthFreq
, MaxML
, 0);
175 optPtr
->offCodeSum
= ZSTD_downscaleStat(optPtr
->offCodeFreq
, MaxOff
, 0);
178 ZSTD_setBasePrices(optPtr
, optLevel
);
181 /* ZSTD_rawLiteralsCost() :
182 * price of literals (only) in specified segment (which length can be 0).
183 * does not include price of literalLength symbol */
184 static U32
ZSTD_rawLiteralsCost(const BYTE
* const literals
, U32
const litLength
,
185 const optState_t
* const optPtr
,
188 if (litLength
== 0) return 0;
189 if (optPtr
->priceType
== zop_predef
)
190 return (litLength
*6) * BITCOST_MULTIPLIER
; /* 6 bit per literal - no statistic used */
192 /* dynamic statistics */
193 { U32 price
= litLength
* optPtr
->litSumBasePrice
;
195 for (u
=0; u
< litLength
; u
++) {
196 assert(WEIGHT(optPtr
->litFreq
[literals
[u
]], optLevel
) <= optPtr
->litSumBasePrice
); /* literal cost should never be negative */
197 price
-= WEIGHT(optPtr
->litFreq
[literals
[u
]], optLevel
);
203 /* ZSTD_litLengthPrice() :
204 * cost of literalLength symbol */
205 static U32
ZSTD_litLengthPrice(U32
const litLength
, const optState_t
* const optPtr
, int optLevel
)
207 if (optPtr
->priceType
== zop_predef
) return WEIGHT(litLength
, optLevel
);
209 /* dynamic statistics */
210 { U32
const llCode
= ZSTD_LLcode(litLength
);
211 return (LL_bits
[llCode
] * BITCOST_MULTIPLIER
) + (optPtr
->litLengthSumBasePrice
- WEIGHT(optPtr
->litLengthFreq
[llCode
], optLevel
));
215 /* ZSTD_litLengthContribution() :
216 * @return ( cost(litlength) - cost(0) )
217 * this value can then be added to rawLiteralsCost()
218 * to provide a cost which is directly comparable to a match ending at same position */
219 static int ZSTD_litLengthContribution(U32
const litLength
, const optState_t
* const optPtr
, int optLevel
)
221 if (optPtr
->priceType
>= zop_predef
) return WEIGHT(litLength
, optLevel
);
223 /* dynamic statistics */
224 { U32
const llCode
= ZSTD_LLcode(litLength
);
225 int const contribution
= (LL_bits
[llCode
] * BITCOST_MULTIPLIER
)
226 + WEIGHT(optPtr
->litLengthFreq
[0], optLevel
) /* note: log2litLengthSum cancel out */
227 - WEIGHT(optPtr
->litLengthFreq
[llCode
], optLevel
);
231 return MAX(0, contribution
); /* sometimes better, sometimes not ... */
236 /* ZSTD_literalsContribution() :
237 * creates a fake cost for the literals part of a sequence
238 * which can be compared to the ending cost of a match
239 * should a new match start at this position */
240 static int ZSTD_literalsContribution(const BYTE
* const literals
, U32
const litLength
,
241 const optState_t
* const optPtr
,
244 int const contribution
= ZSTD_rawLiteralsCost(literals
, litLength
, optPtr
, optLevel
)
245 + ZSTD_litLengthContribution(litLength
, optPtr
, optLevel
);
249 /* ZSTD_getMatchPrice() :
250 * Provides the cost of the match part (offset + matchLength) of a sequence
251 * Must be combined with ZSTD_fullLiteralsCost() to get the full cost of a sequence.
252 * optLevel: when <2, favors small offset for decompression speed (improved cache efficiency) */
253 FORCE_INLINE_TEMPLATE U32
254 ZSTD_getMatchPrice(U32
const offset
,
255 U32
const matchLength
,
256 const optState_t
* const optPtr
,
260 U32
const offCode
= ZSTD_highbit32(offset
+1);
261 U32
const mlBase
= matchLength
- MINMATCH
;
262 assert(matchLength
>= MINMATCH
);
264 if (optPtr
->priceType
== zop_predef
) /* fixed scheme, do not use statistics */
265 return WEIGHT(mlBase
, optLevel
) + ((16 + offCode
) * BITCOST_MULTIPLIER
);
267 /* dynamic statistics */
268 price
= (offCode
* BITCOST_MULTIPLIER
) + (optPtr
->offCodeSumBasePrice
- WEIGHT(optPtr
->offCodeFreq
[offCode
], optLevel
));
269 if ((optLevel
<2) /*static*/ && offCode
>= 20)
270 price
+= (offCode
-19)*2 * BITCOST_MULTIPLIER
; /* handicap for long distance offsets, favor decompression speed */
273 { U32
const mlCode
= ZSTD_MLcode(mlBase
);
274 price
+= (ML_bits
[mlCode
] * BITCOST_MULTIPLIER
) + (optPtr
->matchLengthSumBasePrice
- WEIGHT(optPtr
->matchLengthFreq
[mlCode
], optLevel
));
277 price
+= BITCOST_MULTIPLIER
/ 5; /* heuristic : make matches a bit more costly to favor less sequences -> faster decompression speed */
279 DEBUGLOG(8, "ZSTD_getMatchPrice(ml:%u) = %u", matchLength
, price
);
283 /* ZSTD_updateStats() :
284 * assumption : literals + litLengtn <= iend */
285 static void ZSTD_updateStats(optState_t
* const optPtr
,
286 U32 litLength
, const BYTE
* literals
,
287 U32 offsetCode
, U32 matchLength
)
291 for (u
=0; u
< litLength
; u
++)
292 optPtr
->litFreq
[literals
[u
]] += ZSTD_LITFREQ_ADD
;
293 optPtr
->litSum
+= litLength
*ZSTD_LITFREQ_ADD
;
297 { U32
const llCode
= ZSTD_LLcode(litLength
);
298 optPtr
->litLengthFreq
[llCode
]++;
299 optPtr
->litLengthSum
++;
302 /* match offset code (0-2=>repCode; 3+=>offset+2) */
303 { U32
const offCode
= ZSTD_highbit32(offsetCode
+1);
304 assert(offCode
<= MaxOff
);
305 optPtr
->offCodeFreq
[offCode
]++;
306 optPtr
->offCodeSum
++;
310 { U32
const mlBase
= matchLength
- MINMATCH
;
311 U32
const mlCode
= ZSTD_MLcode(mlBase
);
312 optPtr
->matchLengthFreq
[mlCode
]++;
313 optPtr
->matchLengthSum
++;
318 /* ZSTD_readMINMATCH() :
319 * function safe only for comparisons
320 * assumption : memPtr must be at least 4 bytes before end of buffer */
321 MEM_STATIC U32
ZSTD_readMINMATCH(const void* memPtr
, U32 length
)
326 case 4 : return MEM_read32(memPtr
);
327 case 3 : if (MEM_isLittleEndian())
328 return MEM_read32(memPtr
)<<8;
330 return MEM_read32(memPtr
)>>8;
335 /* Update hashTable3 up to ip (excluded)
336 Assumption : always within prefix (i.e. not within extDict) */
337 static U32
ZSTD_insertAndFindFirstIndexHash3 (ZSTD_matchState_t
* ms
, const BYTE
* const ip
)
339 U32
* const hashTable3
= ms
->hashTable3
;
340 U32
const hashLog3
= ms
->hashLog3
;
341 const BYTE
* const base
= ms
->window
.base
;
342 U32 idx
= ms
->nextToUpdate3
;
343 U32
const target
= ms
->nextToUpdate3
= (U32
)(ip
- base
);
344 size_t const hash3
= ZSTD_hash3Ptr(ip
, hashLog3
);
345 assert(hashLog3
> 0);
347 while(idx
< target
) {
348 hashTable3
[ZSTD_hash3Ptr(base
+idx
, hashLog3
)] = idx
;
352 return hashTable3
[hash3
];
356 /*-*************************************
358 ***************************************/
359 /** ZSTD_insertBt1() : add one or multiple positions to tree.
360 * ip : assumed <= iend-8 .
361 * @return : nb of positions added */
362 static U32
ZSTD_insertBt1(
363 ZSTD_matchState_t
* ms
,
364 const BYTE
* const ip
, const BYTE
* const iend
,
365 U32
const mls
, const int extDict
)
367 const ZSTD_compressionParameters
* const cParams
= &ms
->cParams
;
368 U32
* const hashTable
= ms
->hashTable
;
369 U32
const hashLog
= cParams
->hashLog
;
370 size_t const h
= ZSTD_hashPtr(ip
, hashLog
, mls
);
371 U32
* const bt
= ms
->chainTable
;
372 U32
const btLog
= cParams
->chainLog
- 1;
373 U32
const btMask
= (1 << btLog
) - 1;
374 U32 matchIndex
= hashTable
[h
];
375 size_t commonLengthSmaller
=0, commonLengthLarger
=0;
376 const BYTE
* const base
= ms
->window
.base
;
377 const BYTE
* const dictBase
= ms
->window
.dictBase
;
378 const U32 dictLimit
= ms
->window
.dictLimit
;
379 const BYTE
* const dictEnd
= dictBase
+ dictLimit
;
380 const BYTE
* const prefixStart
= base
+ dictLimit
;
382 const U32 current
= (U32
)(ip
-base
);
383 const U32 btLow
= btMask
>= current
? 0 : current
- btMask
;
384 U32
* smallerPtr
= bt
+ 2*(current
&btMask
);
385 U32
* largerPtr
= smallerPtr
+ 1;
386 U32 dummy32
; /* to be nullified at the end */
387 U32
const windowLow
= ms
->window
.lowLimit
;
388 U32
const matchLow
= windowLow
? windowLow
: 1;
389 U32 matchEndIdx
= current
+8+1;
390 size_t bestLength
= 8;
391 U32 nbCompares
= 1U << cParams
->searchLog
;
392 #ifdef ZSTD_C_PREDICT
393 U32 predictedSmall
= *(bt
+ 2*((current
-1)&btMask
) + 0);
394 U32 predictedLarge
= *(bt
+ 2*((current
-1)&btMask
) + 1);
395 predictedSmall
+= (predictedSmall
>0);
396 predictedLarge
+= (predictedLarge
>0);
397 #endif /* ZSTD_C_PREDICT */
399 DEBUGLOG(8, "ZSTD_insertBt1 (%u)", current
);
401 assert(ip
<= iend
-8); /* required for h calculation */
402 hashTable
[h
] = current
; /* Update Hash Table */
404 while (nbCompares
-- && (matchIndex
>= matchLow
)) {
405 U32
* const nextPtr
= bt
+ 2*(matchIndex
& btMask
);
406 size_t matchLength
= MIN(commonLengthSmaller
, commonLengthLarger
); /* guaranteed minimum nb of common bytes */
407 assert(matchIndex
< current
);
409 #ifdef ZSTD_C_PREDICT /* note : can create issues when hlog small <= 11 */
410 const U32
* predictPtr
= bt
+ 2*((matchIndex
-1) & btMask
); /* written this way, as bt is a roll buffer */
411 if (matchIndex
== predictedSmall
) {
412 /* no need to check length, result known */
413 *smallerPtr
= matchIndex
;
414 if (matchIndex
<= btLow
) { smallerPtr
=&dummy32
; break; } /* beyond tree size, stop the search */
415 smallerPtr
= nextPtr
+1; /* new "smaller" => larger of match */
416 matchIndex
= nextPtr
[1]; /* new matchIndex larger than previous (closer to current) */
417 predictedSmall
= predictPtr
[1] + (predictPtr
[1]>0);
420 if (matchIndex
== predictedLarge
) {
421 *largerPtr
= matchIndex
;
422 if (matchIndex
<= btLow
) { largerPtr
=&dummy32
; break; } /* beyond tree size, stop the search */
424 matchIndex
= nextPtr
[0];
425 predictedLarge
= predictPtr
[0] + (predictPtr
[0]>0);
430 if (!extDict
|| (matchIndex
+matchLength
>= dictLimit
)) {
431 assert(matchIndex
+matchLength
>= dictLimit
); /* might be wrong if actually extDict */
432 match
= base
+ matchIndex
;
433 matchLength
+= ZSTD_count(ip
+matchLength
, match
+matchLength
, iend
);
435 match
= dictBase
+ matchIndex
;
436 matchLength
+= ZSTD_count_2segments(ip
+matchLength
, match
+matchLength
, iend
, dictEnd
, prefixStart
);
437 if (matchIndex
+matchLength
>= dictLimit
)
438 match
= base
+ matchIndex
; /* to prepare for next usage of match[matchLength] */
441 if (matchLength
> bestLength
) {
442 bestLength
= matchLength
;
443 if (matchLength
> matchEndIdx
- matchIndex
)
444 matchEndIdx
= matchIndex
+ (U32
)matchLength
;
447 if (ip
+matchLength
== iend
) { /* equal : no way to know if inf or sup */
448 break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt tree */
451 if (match
[matchLength
] < ip
[matchLength
]) { /* necessarily within buffer */
452 /* match is smaller than current */
453 *smallerPtr
= matchIndex
; /* update smaller idx */
454 commonLengthSmaller
= matchLength
; /* all smaller will now have at least this guaranteed common length */
455 if (matchIndex
<= btLow
) { smallerPtr
=&dummy32
; break; } /* beyond tree size, stop searching */
456 smallerPtr
= nextPtr
+1; /* new "candidate" => larger than match, which was smaller than target */
457 matchIndex
= nextPtr
[1]; /* new matchIndex, larger than previous and closer to current */
459 /* match is larger than current */
460 *largerPtr
= matchIndex
;
461 commonLengthLarger
= matchLength
;
462 if (matchIndex
<= btLow
) { largerPtr
=&dummy32
; break; } /* beyond tree size, stop searching */
464 matchIndex
= nextPtr
[0];
467 *smallerPtr
= *largerPtr
= 0;
468 if (bestLength
> 384) return MIN(192, (U32
)(bestLength
- 384)); /* speed optimization */
469 assert(matchEndIdx
> current
+ 8);
470 return matchEndIdx
- (current
+ 8);
473 FORCE_INLINE_TEMPLATE
474 void ZSTD_updateTree_internal(
475 ZSTD_matchState_t
* ms
,
476 const BYTE
* const ip
, const BYTE
* const iend
,
477 const U32 mls
, const ZSTD_dictMode_e dictMode
)
479 const BYTE
* const base
= ms
->window
.base
;
480 U32
const target
= (U32
)(ip
- base
);
481 U32 idx
= ms
->nextToUpdate
;
482 DEBUGLOG(5, "ZSTD_updateTree_internal, from %u to %u (dictMode:%u)",
483 idx
, target
, dictMode
);
486 idx
+= ZSTD_insertBt1(ms
, base
+idx
, iend
, mls
, dictMode
== ZSTD_extDict
);
487 ms
->nextToUpdate
= target
;
490 void ZSTD_updateTree(ZSTD_matchState_t
* ms
, const BYTE
* ip
, const BYTE
* iend
) {
491 ZSTD_updateTree_internal(ms
, ip
, iend
, ms
->cParams
.searchLength
, ZSTD_noDict
);
494 FORCE_INLINE_TEMPLATE
495 U32
ZSTD_insertBtAndGetAllMatches (
496 ZSTD_matchState_t
* ms
,
497 const BYTE
* const ip
, const BYTE
* const iLimit
, const ZSTD_dictMode_e dictMode
,
498 U32 rep
[ZSTD_REP_NUM
], U32
const ll0
,
499 ZSTD_match_t
* matches
, const U32 lengthToBeat
, U32
const mls
/* template */)
501 const ZSTD_compressionParameters
* const cParams
= &ms
->cParams
;
502 U32
const sufficient_len
= MIN(cParams
->targetLength
, ZSTD_OPT_NUM
-1);
503 const BYTE
* const base
= ms
->window
.base
;
504 U32
const current
= (U32
)(ip
-base
);
505 U32
const hashLog
= cParams
->hashLog
;
506 U32
const minMatch
= (mls
==3) ? 3 : 4;
507 U32
* const hashTable
= ms
->hashTable
;
508 size_t const h
= ZSTD_hashPtr(ip
, hashLog
, mls
);
509 U32 matchIndex
= hashTable
[h
];
510 U32
* const bt
= ms
->chainTable
;
511 U32
const btLog
= cParams
->chainLog
- 1;
512 U32
const btMask
= (1U << btLog
) - 1;
513 size_t commonLengthSmaller
=0, commonLengthLarger
=0;
514 const BYTE
* const dictBase
= ms
->window
.dictBase
;
515 U32
const dictLimit
= ms
->window
.dictLimit
;
516 const BYTE
* const dictEnd
= dictBase
+ dictLimit
;
517 const BYTE
* const prefixStart
= base
+ dictLimit
;
518 U32
const btLow
= btMask
>= current
? 0 : current
- btMask
;
519 U32
const windowLow
= ms
->window
.lowLimit
;
520 U32
const matchLow
= windowLow
? windowLow
: 1;
521 U32
* smallerPtr
= bt
+ 2*(current
&btMask
);
522 U32
* largerPtr
= bt
+ 2*(current
&btMask
) + 1;
523 U32 matchEndIdx
= current
+8+1; /* farthest referenced position of any match => detects repetitive patterns */
524 U32 dummy32
; /* to be nullified at the end */
526 U32 nbCompares
= 1U << cParams
->searchLog
;
528 const ZSTD_matchState_t
* dms
= dictMode
== ZSTD_dictMatchState
? ms
->dictMatchState
: NULL
;
529 const ZSTD_compressionParameters
* const dmsCParams
=
530 dictMode
== ZSTD_dictMatchState
? &dms
->cParams
: NULL
;
531 const BYTE
* const dmsBase
= dictMode
== ZSTD_dictMatchState
? dms
->window
.base
: NULL
;
532 const BYTE
* const dmsEnd
= dictMode
== ZSTD_dictMatchState
? dms
->window
.nextSrc
: NULL
;
533 U32
const dmsHighLimit
= dictMode
== ZSTD_dictMatchState
? (U32
)(dmsEnd
- dmsBase
) : 0;
534 U32
const dmsLowLimit
= dictMode
== ZSTD_dictMatchState
? dms
->window
.lowLimit
: 0;
535 U32
const dmsIndexDelta
= dictMode
== ZSTD_dictMatchState
? windowLow
- dmsHighLimit
: 0;
536 U32
const dmsHashLog
= dictMode
== ZSTD_dictMatchState
? dmsCParams
->hashLog
: hashLog
;
537 U32
const dmsBtLog
= dictMode
== ZSTD_dictMatchState
? dmsCParams
->chainLog
- 1 : btLog
;
538 U32
const dmsBtMask
= dictMode
== ZSTD_dictMatchState
? (1U << dmsBtLog
) - 1 : 0;
539 U32
const dmsBtLow
= dictMode
== ZSTD_dictMatchState
&& dmsBtMask
< dmsHighLimit
- dmsLowLimit
? dmsHighLimit
- dmsBtMask
: dmsLowLimit
;
541 size_t bestLength
= lengthToBeat
-1;
542 DEBUGLOG(8, "ZSTD_insertBtAndGetAllMatches: current=%u", current
);
545 { U32
const lastR
= ZSTD_REP_NUM
+ ll0
;
547 for (repCode
= ll0
; repCode
< lastR
; repCode
++) {
548 U32
const repOffset
= (repCode
==ZSTD_REP_NUM
) ? (rep
[0] - 1) : rep
[repCode
];
549 U32
const repIndex
= current
- repOffset
;
551 assert(current
>= dictLimit
);
552 if (repOffset
-1 /* intentional overflow, discards 0 and -1 */ < current
-dictLimit
) { /* equivalent to `current > repIndex >= dictLimit` */
553 if (ZSTD_readMINMATCH(ip
, minMatch
) == ZSTD_readMINMATCH(ip
- repOffset
, minMatch
)) {
554 repLen
= (U32
)ZSTD_count(ip
+minMatch
, ip
+minMatch
-repOffset
, iLimit
) + minMatch
;
556 } else { /* repIndex < dictLimit || repIndex >= current */
557 const BYTE
* const repMatch
= dictMode
== ZSTD_dictMatchState
?
558 dmsBase
+ repIndex
- dmsIndexDelta
:
560 assert(current
>= windowLow
);
561 if ( dictMode
== ZSTD_extDict
562 && ( ((repOffset
-1) /*intentional overflow*/ < current
- windowLow
) /* equivalent to `current > repIndex >= windowLow` */
563 & (((U32
)((dictLimit
-1) - repIndex
) >= 3) ) /* intentional overflow : do not test positions overlapping 2 memory segments */)
564 && (ZSTD_readMINMATCH(ip
, minMatch
) == ZSTD_readMINMATCH(repMatch
, minMatch
)) ) {
565 repLen
= (U32
)ZSTD_count_2segments(ip
+minMatch
, repMatch
+minMatch
, iLimit
, dictEnd
, prefixStart
) + minMatch
;
567 if (dictMode
== ZSTD_dictMatchState
568 && ( ((repOffset
-1) /*intentional overflow*/ < current
- (dmsLowLimit
+ dmsIndexDelta
)) /* equivalent to `current > repIndex >= dmsLowLimit` */
569 & ((U32
)((dictLimit
-1) - repIndex
) >= 3) ) /* intentional overflow : do not test positions overlapping 2 memory segments */
570 && (ZSTD_readMINMATCH(ip
, minMatch
) == ZSTD_readMINMATCH(repMatch
, minMatch
)) ) {
571 repLen
= (U32
)ZSTD_count_2segments(ip
+minMatch
, repMatch
+minMatch
, iLimit
, dmsEnd
, prefixStart
) + minMatch
;
573 /* save longer solution */
574 if (repLen
> bestLength
) {
575 DEBUGLOG(8, "found repCode %u (ll0:%u, offset:%u) of length %u",
576 repCode
, ll0
, repOffset
, repLen
);
578 matches
[mnum
].off
= repCode
- ll0
;
579 matches
[mnum
].len
= (U32
)repLen
;
581 if ( (repLen
> sufficient_len
)
582 | (ip
+repLen
== iLimit
) ) { /* best possible */
586 /* HC3 match finder */
587 if ((mls
== 3) /*static*/ && (bestLength
< mls
)) {
588 U32
const matchIndex3
= ZSTD_insertAndFindFirstIndexHash3(ms
, ip
);
589 if ((matchIndex3
>= matchLow
)
590 & (current
- matchIndex3
< (1<<18)) /*heuristic : longer distance likely too expensive*/ ) {
592 if ((dictMode
== ZSTD_noDict
) /*static*/ || (dictMode
== ZSTD_dictMatchState
) /*static*/ || (matchIndex3
>= dictLimit
)) {
593 const BYTE
* const match
= base
+ matchIndex3
;
594 mlen
= ZSTD_count(ip
, match
, iLimit
);
596 const BYTE
* const match
= dictBase
+ matchIndex3
;
597 mlen
= ZSTD_count_2segments(ip
, match
, iLimit
, dictEnd
, prefixStart
);
600 /* save best solution */
601 if (mlen
>= mls
/* == 3 > bestLength */) {
602 DEBUGLOG(8, "found small match with hlog3, of length %u",
605 assert(current
> matchIndex3
);
606 assert(mnum
==0); /* no prior solution */
607 matches
[0].off
= (current
- matchIndex3
) + ZSTD_REP_MOVE
;
608 matches
[0].len
= (U32
)mlen
;
610 if ( (mlen
> sufficient_len
) |
611 (ip
+mlen
== iLimit
) ) { /* best possible length */
612 ms
->nextToUpdate
= current
+1; /* skip insertion */
617 /* no dictMatchState lookup: dicts don't have a populated HC3 table */
620 hashTable
[h
] = current
; /* Update Hash Table */
622 while (nbCompares
-- && (matchIndex
>= matchLow
)) {
623 U32
* const nextPtr
= bt
+ 2*(matchIndex
& btMask
);
624 size_t matchLength
= MIN(commonLengthSmaller
, commonLengthLarger
); /* guaranteed minimum nb of common bytes */
626 assert(current
> matchIndex
);
628 if ((dictMode
== ZSTD_noDict
) || (dictMode
== ZSTD_dictMatchState
) || (matchIndex
+matchLength
>= dictLimit
)) {
629 assert(matchIndex
+matchLength
>= dictLimit
); /* ensure the condition is correct when !extDict */
630 match
= base
+ matchIndex
;
631 matchLength
+= ZSTD_count(ip
+matchLength
, match
+matchLength
, iLimit
);
633 match
= dictBase
+ matchIndex
;
634 matchLength
+= ZSTD_count_2segments(ip
+matchLength
, match
+matchLength
, iLimit
, dictEnd
, prefixStart
);
635 if (matchIndex
+matchLength
>= dictLimit
)
636 match
= base
+ matchIndex
; /* prepare for match[matchLength] */
639 if (matchLength
> bestLength
) {
640 DEBUGLOG(8, "found match of length %u at distance %u (offCode=%u)",
641 (U32
)matchLength
, current
- matchIndex
, current
- matchIndex
+ ZSTD_REP_MOVE
);
642 assert(matchEndIdx
> matchIndex
);
643 if (matchLength
> matchEndIdx
- matchIndex
)
644 matchEndIdx
= matchIndex
+ (U32
)matchLength
;
645 bestLength
= matchLength
;
646 matches
[mnum
].off
= (current
- matchIndex
) + ZSTD_REP_MOVE
;
647 matches
[mnum
].len
= (U32
)matchLength
;
649 if ( (matchLength
> ZSTD_OPT_NUM
)
650 | (ip
+matchLength
== iLimit
) /* equal : no way to know if inf or sup */) {
651 if (dictMode
== ZSTD_dictMatchState
) nbCompares
= 0; /* break should also skip searching dms */
652 break; /* drop, to preserve bt consistency (miss a little bit of compression) */
656 if (match
[matchLength
] < ip
[matchLength
]) {
657 /* match smaller than current */
658 *smallerPtr
= matchIndex
; /* update smaller idx */
659 commonLengthSmaller
= matchLength
; /* all smaller will now have at least this guaranteed common length */
660 if (matchIndex
<= btLow
) { smallerPtr
=&dummy32
; break; } /* beyond tree size, stop the search */
661 smallerPtr
= nextPtr
+1; /* new candidate => larger than match, which was smaller than current */
662 matchIndex
= nextPtr
[1]; /* new matchIndex, larger than previous, closer to current */
664 *largerPtr
= matchIndex
;
665 commonLengthLarger
= matchLength
;
666 if (matchIndex
<= btLow
) { largerPtr
=&dummy32
; break; } /* beyond tree size, stop the search */
668 matchIndex
= nextPtr
[0];
671 *smallerPtr
= *largerPtr
= 0;
673 if (dictMode
== ZSTD_dictMatchState
&& nbCompares
) {
674 size_t const dmsH
= ZSTD_hashPtr(ip
, dmsHashLog
, mls
);
675 U32 dictMatchIndex
= dms
->hashTable
[dmsH
];
676 const U32
* const dmsBt
= dms
->chainTable
;
677 commonLengthSmaller
= commonLengthLarger
= 0;
678 while (nbCompares
-- && (dictMatchIndex
> dmsLowLimit
)) {
679 const U32
* const nextPtr
= dmsBt
+ 2*(dictMatchIndex
& dmsBtMask
);
680 size_t matchLength
= MIN(commonLengthSmaller
, commonLengthLarger
); /* guaranteed minimum nb of common bytes */
681 const BYTE
* match
= dmsBase
+ dictMatchIndex
;
682 matchLength
+= ZSTD_count_2segments(ip
+matchLength
, match
+matchLength
, iLimit
, dmsEnd
, prefixStart
);
683 if (dictMatchIndex
+matchLength
>= dmsHighLimit
)
684 match
= base
+ dictMatchIndex
+ dmsIndexDelta
; /* to prepare for next usage of match[matchLength] */
686 if (matchLength
> bestLength
) {
687 matchIndex
= dictMatchIndex
+ dmsIndexDelta
;
688 DEBUGLOG(8, "found dms match of length %u at distance %u (offCode=%u)",
689 (U32
)matchLength
, current
- matchIndex
, current
- matchIndex
+ ZSTD_REP_MOVE
);
690 if (matchLength
> matchEndIdx
- matchIndex
)
691 matchEndIdx
= matchIndex
+ (U32
)matchLength
;
692 bestLength
= matchLength
;
693 matches
[mnum
].off
= (current
- matchIndex
) + ZSTD_REP_MOVE
;
694 matches
[mnum
].len
= (U32
)matchLength
;
696 if ( (matchLength
> ZSTD_OPT_NUM
)
697 | (ip
+matchLength
== iLimit
) /* equal : no way to know if inf or sup */) {
698 break; /* drop, to guarantee consistency (miss a little bit of compression) */
702 if (dictMatchIndex
<= dmsBtLow
) { break; } /* beyond tree size, stop the search */
703 if (match
[matchLength
] < ip
[matchLength
]) {
704 commonLengthSmaller
= matchLength
; /* all smaller will now have at least this guaranteed common length */
705 dictMatchIndex
= nextPtr
[1]; /* new matchIndex larger than previous (closer to current) */
707 /* match is larger than current */
708 commonLengthLarger
= matchLength
;
709 dictMatchIndex
= nextPtr
[0];
714 assert(matchEndIdx
> current
+8);
715 ms
->nextToUpdate
= matchEndIdx
- 8; /* skip repetitive patterns */
720 FORCE_INLINE_TEMPLATE U32
ZSTD_BtGetAllMatches (
721 ZSTD_matchState_t
* ms
,
722 const BYTE
* ip
, const BYTE
* const iHighLimit
, const ZSTD_dictMode_e dictMode
,
723 U32 rep
[ZSTD_REP_NUM
], U32
const ll0
,
724 ZSTD_match_t
* matches
, U32
const lengthToBeat
)
726 const ZSTD_compressionParameters
* const cParams
= &ms
->cParams
;
727 U32
const matchLengthSearch
= cParams
->searchLength
;
728 DEBUGLOG(8, "ZSTD_BtGetAllMatches");
729 if (ip
< ms
->window
.base
+ ms
->nextToUpdate
) return 0; /* skipped area */
730 ZSTD_updateTree_internal(ms
, ip
, iHighLimit
, matchLengthSearch
, dictMode
);
731 switch(matchLengthSearch
)
733 case 3 : return ZSTD_insertBtAndGetAllMatches(ms
, ip
, iHighLimit
, dictMode
, rep
, ll0
, matches
, lengthToBeat
, 3);
735 case 4 : return ZSTD_insertBtAndGetAllMatches(ms
, ip
, iHighLimit
, dictMode
, rep
, ll0
, matches
, lengthToBeat
, 4);
736 case 5 : return ZSTD_insertBtAndGetAllMatches(ms
, ip
, iHighLimit
, dictMode
, rep
, ll0
, matches
, lengthToBeat
, 5);
738 case 6 : return ZSTD_insertBtAndGetAllMatches(ms
, ip
, iHighLimit
, dictMode
, rep
, ll0
, matches
, lengthToBeat
, 6);
743 /*-*******************************
745 *********************************/
746 typedef struct repcodes_s
{
750 static repcodes_t
ZSTD_updateRep(U32
const rep
[3], U32
const offset
, U32
const ll0
)
753 if (offset
>= ZSTD_REP_NUM
) { /* full offset */
754 newReps
.rep
[2] = rep
[1];
755 newReps
.rep
[1] = rep
[0];
756 newReps
.rep
[0] = offset
- ZSTD_REP_MOVE
;
757 } else { /* repcode */
758 U32
const repCode
= offset
+ ll0
;
759 if (repCode
> 0) { /* note : if repCode==0, no change */
760 U32
const currentOffset
= (repCode
==ZSTD_REP_NUM
) ? (rep
[0] - 1) : rep
[repCode
];
761 newReps
.rep
[2] = (repCode
>= 2) ? rep
[1] : rep
[2];
762 newReps
.rep
[1] = rep
[0];
763 newReps
.rep
[0] = currentOffset
;
764 } else { /* repCode == 0 */
765 memcpy(&newReps
, rep
, sizeof(newReps
));
772 static U32
ZSTD_totalLen(ZSTD_optimal_t sol
)
774 return sol
.litlen
+ sol
.mlen
;
777 FORCE_INLINE_TEMPLATE
size_t
778 ZSTD_compressBlock_opt_generic(ZSTD_matchState_t
* ms
,
779 seqStore_t
* seqStore
,
780 U32 rep
[ZSTD_REP_NUM
],
781 const void* src
, size_t srcSize
,
782 const int optLevel
, const ZSTD_dictMode_e dictMode
)
784 optState_t
* const optStatePtr
= &ms
->opt
;
785 const BYTE
* const istart
= (const BYTE
*)src
;
786 const BYTE
* ip
= istart
;
787 const BYTE
* anchor
= istart
;
788 const BYTE
* const iend
= istart
+ srcSize
;
789 const BYTE
* const ilimit
= iend
- 8;
790 const BYTE
* const base
= ms
->window
.base
;
791 const BYTE
* const prefixStart
= base
+ ms
->window
.dictLimit
;
792 const ZSTD_compressionParameters
* const cParams
= &ms
->cParams
;
794 U32
const sufficient_len
= MIN(cParams
->targetLength
, ZSTD_OPT_NUM
-1);
795 U32
const minMatch
= (cParams
->searchLength
== 3) ? 3 : 4;
797 ZSTD_optimal_t
* const opt
= optStatePtr
->priceTable
;
798 ZSTD_match_t
* const matches
= optStatePtr
->matchTable
;
799 ZSTD_optimal_t lastSequence
;
802 DEBUGLOG(5, "ZSTD_compressBlock_opt_generic");
803 assert(optLevel
<= 2);
804 ms
->nextToUpdate3
= ms
->nextToUpdate
;
805 ZSTD_rescaleFreqs(optStatePtr
, (const BYTE
*)src
, srcSize
, optLevel
);
806 ip
+= (ip
==prefixStart
);
809 while (ip
< ilimit
) {
810 U32 cur
, last_pos
= 0;
812 /* find first match */
813 { U32
const litlen
= (U32
)(ip
- anchor
);
814 U32
const ll0
= !litlen
;
815 U32
const nbMatches
= ZSTD_BtGetAllMatches(ms
, ip
, iend
, dictMode
, rep
, ll0
, matches
, minMatch
);
816 if (!nbMatches
) { ip
++; continue; }
818 /* initialize opt[0] */
819 { U32 i
; for (i
=0; i
<ZSTD_REP_NUM
; i
++) opt
[0].rep
[i
] = rep
[i
]; }
820 opt
[0].mlen
= 0; /* means is_a_literal */
821 opt
[0].litlen
= litlen
;
822 opt
[0].price
= ZSTD_literalsContribution(anchor
, litlen
, optStatePtr
, optLevel
);
824 /* large match -> immediate encoding */
825 { U32
const maxML
= matches
[nbMatches
-1].len
;
826 U32
const maxOffset
= matches
[nbMatches
-1].off
;
827 DEBUGLOG(6, "found %u matches of maxLength=%u and maxOffCode=%u at cPos=%u => start new serie",
828 nbMatches
, maxML
, maxOffset
, (U32
)(ip
-prefixStart
));
830 if (maxML
> sufficient_len
) {
831 lastSequence
.litlen
= litlen
;
832 lastSequence
.mlen
= maxML
;
833 lastSequence
.off
= maxOffset
;
834 DEBUGLOG(6, "large match (%u>%u), immediate encoding",
835 maxML
, sufficient_len
);
837 last_pos
= ZSTD_totalLen(lastSequence
);
841 /* set prices for first matches starting position == 0 */
842 { U32
const literalsPrice
= opt
[0].price
+ ZSTD_litLengthPrice(0, optStatePtr
, optLevel
);
845 for (pos
= 1; pos
< minMatch
; pos
++) {
846 opt
[pos
].price
= ZSTD_MAX_PRICE
; /* mlen, litlen and price will be fixed during forward scanning */
848 for (matchNb
= 0; matchNb
< nbMatches
; matchNb
++) {
849 U32
const offset
= matches
[matchNb
].off
;
850 U32
const end
= matches
[matchNb
].len
;
851 repcodes_t
const repHistory
= ZSTD_updateRep(rep
, offset
, ll0
);
852 for ( ; pos
<= end
; pos
++ ) {
853 U32
const matchPrice
= ZSTD_getMatchPrice(offset
, pos
, optStatePtr
, optLevel
);
854 U32
const sequencePrice
= literalsPrice
+ matchPrice
;
855 DEBUGLOG(7, "rPos:%u => set initial price : %.2f",
856 pos
, ZSTD_fCost(sequencePrice
));
858 opt
[pos
].off
= offset
;
859 opt
[pos
].litlen
= litlen
;
860 opt
[pos
].price
= sequencePrice
;
861 ZSTD_STATIC_ASSERT(sizeof(opt
[pos
].rep
) == sizeof(repHistory
));
862 memcpy(opt
[pos
].rep
, &repHistory
, sizeof(repHistory
));
868 /* check further positions */
869 for (cur
= 1; cur
<= last_pos
; cur
++) {
870 const BYTE
* const inr
= ip
+ cur
;
871 assert(cur
< ZSTD_OPT_NUM
);
872 DEBUGLOG(7, "cPos:%zi==rPos:%u", inr
-istart
, cur
)
874 /* Fix current position with one literal if cheaper */
875 { U32
const litlen
= (opt
[cur
-1].mlen
== 0) ? opt
[cur
-1].litlen
+ 1 : 1;
876 int const price
= opt
[cur
-1].price
877 + ZSTD_rawLiteralsCost(ip
+cur
-1, 1, optStatePtr
, optLevel
)
878 + ZSTD_litLengthPrice(litlen
, optStatePtr
, optLevel
)
879 - ZSTD_litLengthPrice(litlen
-1, optStatePtr
, optLevel
);
880 assert(price
< 1000000000); /* overflow check */
881 if (price
<= opt
[cur
].price
) {
882 DEBUGLOG(7, "cPos:%zi==rPos:%u : better price (%.2f<=%.2f) using literal (ll==%u) (hist:%u,%u,%u)",
883 inr
-istart
, cur
, ZSTD_fCost(price
), ZSTD_fCost(opt
[cur
].price
), litlen
,
884 opt
[cur
-1].rep
[0], opt
[cur
-1].rep
[1], opt
[cur
-1].rep
[2]);
887 opt
[cur
].litlen
= litlen
;
888 opt
[cur
].price
= price
;
889 memcpy(opt
[cur
].rep
, opt
[cur
-1].rep
, sizeof(opt
[cur
].rep
));
891 DEBUGLOG(7, "cPos:%zi==rPos:%u : literal would cost more (%.2f>%.2f) (hist:%u,%u,%u)",
892 inr
-istart
, cur
, ZSTD_fCost(price
), ZSTD_fCost(opt
[cur
].price
),
893 opt
[cur
].rep
[0], opt
[cur
].rep
[1], opt
[cur
].rep
[2]);
897 /* last match must start at a minimum distance of 8 from oend */
898 if (inr
> ilimit
) continue;
900 if (cur
== last_pos
) break;
902 if ( (optLevel
==0) /*static_test*/
903 && (opt
[cur
+1].price
<= opt
[cur
].price
+ (BITCOST_MULTIPLIER
/2)) ) {
904 DEBUGLOG(7, "move to next rPos:%u : price is <=", cur
+1);
905 continue; /* skip unpromising positions; about ~+6% speed, -0.01 ratio */
908 { U32
const ll0
= (opt
[cur
].mlen
!= 0);
909 U32
const litlen
= (opt
[cur
].mlen
== 0) ? opt
[cur
].litlen
: 0;
910 U32
const previousPrice
= opt
[cur
].price
;
911 U32
const basePrice
= previousPrice
+ ZSTD_litLengthPrice(0, optStatePtr
, optLevel
);
912 U32
const nbMatches
= ZSTD_BtGetAllMatches(ms
, inr
, iend
, dictMode
, opt
[cur
].rep
, ll0
, matches
, minMatch
);
915 DEBUGLOG(7, "rPos:%u : no match found", cur
);
919 { U32
const maxML
= matches
[nbMatches
-1].len
;
920 DEBUGLOG(7, "cPos:%zi==rPos:%u, found %u matches, of maxLength=%u",
921 inr
-istart
, cur
, nbMatches
, maxML
);
923 if ( (maxML
> sufficient_len
)
924 || (cur
+ maxML
>= ZSTD_OPT_NUM
) ) {
925 lastSequence
.mlen
= maxML
;
926 lastSequence
.off
= matches
[nbMatches
-1].off
;
927 lastSequence
.litlen
= litlen
;
928 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 */
929 last_pos
= cur
+ ZSTD_totalLen(lastSequence
);
930 if (cur
> ZSTD_OPT_NUM
) cur
= 0; /* underflow => first match */
934 /* set prices using matches found at position == cur */
935 for (matchNb
= 0; matchNb
< nbMatches
; matchNb
++) {
936 U32
const offset
= matches
[matchNb
].off
;
937 repcodes_t
const repHistory
= ZSTD_updateRep(opt
[cur
].rep
, offset
, ll0
);
938 U32
const lastML
= matches
[matchNb
].len
;
939 U32
const startML
= (matchNb
>0) ? matches
[matchNb
-1].len
+1 : minMatch
;
942 DEBUGLOG(7, "testing match %u => offCode=%4u, mlen=%2u, llen=%2u",
943 matchNb
, matches
[matchNb
].off
, lastML
, litlen
);
945 for (mlen
= lastML
; mlen
>= startML
; mlen
--) { /* scan downward */
946 U32
const pos
= cur
+ mlen
;
947 int const price
= basePrice
+ ZSTD_getMatchPrice(offset
, mlen
, optStatePtr
, optLevel
);
949 if ((pos
> last_pos
) || (price
< opt
[pos
].price
)) {
950 DEBUGLOG(7, "rPos:%u (ml=%2u) => new better price (%.2f<%.2f)",
951 pos
, mlen
, ZSTD_fCost(price
), ZSTD_fCost(opt
[pos
].price
));
952 while (last_pos
< pos
) { opt
[last_pos
+1].price
= ZSTD_MAX_PRICE
; last_pos
++; } /* fill empty positions */
953 opt
[pos
].mlen
= mlen
;
954 opt
[pos
].off
= offset
;
955 opt
[pos
].litlen
= litlen
;
956 opt
[pos
].price
= price
;
957 ZSTD_STATIC_ASSERT(sizeof(opt
[pos
].rep
) == sizeof(repHistory
));
958 memcpy(opt
[pos
].rep
, &repHistory
, sizeof(repHistory
));
960 DEBUGLOG(7, "rPos:%u (ml=%2u) => new price is worse (%.2f>=%.2f)",
961 pos
, mlen
, ZSTD_fCost(price
), ZSTD_fCost(opt
[pos
].price
));
962 if (optLevel
==0) break; /* early update abort; gets ~+10% speed for about -0.01 ratio loss */
965 } /* for (cur = 1; cur <= last_pos; cur++) */
967 lastSequence
= opt
[last_pos
];
968 cur
= last_pos
> ZSTD_totalLen(lastSequence
) ? last_pos
- ZSTD_totalLen(lastSequence
) : 0; /* single sequence, and it starts before `ip` */
969 assert(cur
< ZSTD_OPT_NUM
); /* control overflow*/
971 _shortestPath
: /* cur, last_pos, best_mlen, best_off have to be set */
972 assert(opt
[0].mlen
== 0);
974 { U32
const storeEnd
= cur
+ 1;
975 U32 storeStart
= storeEnd
;
978 DEBUGLOG(6, "start reverse traversal (last_pos:%u, cur:%u)",
979 last_pos
, cur
); (void)last_pos
;
980 assert(storeEnd
< ZSTD_OPT_NUM
);
981 DEBUGLOG(6, "last sequence copied into pos=%u (llen=%u,mlen=%u,ofc=%u)",
982 storeEnd
, lastSequence
.litlen
, lastSequence
.mlen
, lastSequence
.off
);
983 opt
[storeEnd
] = lastSequence
;
985 U32
const backDist
= ZSTD_totalLen(opt
[seqPos
]);
987 DEBUGLOG(6, "sequence from rPos=%u copied into pos=%u (llen=%u,mlen=%u,ofc=%u)",
988 seqPos
, storeStart
, opt
[seqPos
].litlen
, opt
[seqPos
].mlen
, opt
[seqPos
].off
);
989 opt
[storeStart
] = opt
[seqPos
];
990 seqPos
= (seqPos
> backDist
) ? seqPos
- backDist
: 0;
994 DEBUGLOG(6, "sending selected sequences into seqStore")
996 for (storePos
=storeStart
; storePos
<= storeEnd
; storePos
++) {
997 U32
const llen
= opt
[storePos
].litlen
;
998 U32
const mlen
= opt
[storePos
].mlen
;
999 U32
const offCode
= opt
[storePos
].off
;
1000 U32
const advance
= llen
+ mlen
;
1001 DEBUGLOG(6, "considering seq starting at %zi, llen=%u, mlen=%u",
1002 anchor
- istart
, llen
, mlen
);
1004 if (mlen
==0) { /* only literals => must be last "sequence", actually starting a new stream of sequences */
1005 assert(storePos
== storeEnd
); /* must be last sequence */
1006 ip
= anchor
+ llen
; /* last "sequence" is a bunch of literals => don't progress anchor */
1007 continue; /* will finish */
1010 /* repcodes update : like ZSTD_updateRep(), but update in place */
1011 if (offCode
>= ZSTD_REP_NUM
) { /* full offset */
1014 rep
[0] = offCode
- ZSTD_REP_MOVE
;
1015 } else { /* repcode */
1016 U32
const repCode
= offCode
+ (llen
==0);
1017 if (repCode
) { /* note : if repCode==0, no change */
1018 U32
const currentOffset
= (repCode
==ZSTD_REP_NUM
) ? (rep
[0] - 1) : rep
[repCode
];
1019 if (repCode
>= 2) rep
[2] = rep
[1];
1021 rep
[0] = currentOffset
;
1024 assert(anchor
+ llen
<= iend
);
1025 ZSTD_updateStats(optStatePtr
, llen
, anchor
, offCode
, mlen
);
1026 ZSTD_storeSeq(seqStore
, llen
, anchor
, offCode
, mlen
-MINMATCH
);
1030 ZSTD_setBasePrices(optStatePtr
, optLevel
);
1033 } /* while (ip < ilimit) */
1035 /* Return the last literals size */
1036 return iend
- anchor
;
1040 size_t ZSTD_compressBlock_btopt(
1041 ZSTD_matchState_t
* ms
, seqStore_t
* seqStore
, U32 rep
[ZSTD_REP_NUM
],
1042 const void* src
, size_t srcSize
)
1044 DEBUGLOG(5, "ZSTD_compressBlock_btopt");
1045 return ZSTD_compressBlock_opt_generic(ms
, seqStore
, rep
, src
, srcSize
, 0 /*optLevel*/, ZSTD_noDict
);
1049 /* used in 2-pass strategy */
1050 static U32
ZSTD_upscaleStat(U32
* table
, U32 lastEltIndex
, int bonus
)
1053 assert(ZSTD_FREQ_DIV
+bonus
> 0);
1054 for (s
=0; s
<=lastEltIndex
; s
++) {
1055 table
[s
] <<= ZSTD_FREQ_DIV
+bonus
;
1062 /* used in 2-pass strategy */
1063 MEM_STATIC
void ZSTD_upscaleStats(optState_t
* optPtr
)
1065 optPtr
->litSum
= ZSTD_upscaleStat(optPtr
->litFreq
, MaxLit
, 0);
1066 optPtr
->litLengthSum
= ZSTD_upscaleStat(optPtr
->litLengthFreq
, MaxLL
, 1);
1067 optPtr
->matchLengthSum
= ZSTD_upscaleStat(optPtr
->matchLengthFreq
, MaxML
, 1);
1068 optPtr
->offCodeSum
= ZSTD_upscaleStat(optPtr
->offCodeFreq
, MaxOff
, 1);
1071 size_t ZSTD_compressBlock_btultra(
1072 ZSTD_matchState_t
* ms
, seqStore_t
* seqStore
, U32 rep
[ZSTD_REP_NUM
],
1073 const void* src
, size_t srcSize
)
1075 DEBUGLOG(5, "ZSTD_compressBlock_btultra (srcSize=%zu)", srcSize
);
1077 /* 2-pass strategy (disabled)
1078 * this strategy makes a first pass over first block to collect statistics
1079 * and seed next round's statistics with it.
1080 * The compression ratio gain is generally small (~0.5% on first block),
1081 * the cost is 2x cpu time on first block. */
1082 assert(srcSize
<= ZSTD_BLOCKSIZE_MAX
);
1083 if ( (ms
->opt
.litLengthSum
==0) /* first block */
1084 && (seqStore
->sequences
== seqStore
->sequencesStart
) /* no ldm */
1085 && (ms
->window
.dictLimit
== ms
->window
.lowLimit
) ) { /* no dictionary */
1086 U32 tmpRep
[ZSTD_REP_NUM
];
1087 DEBUGLOG(5, "ZSTD_compressBlock_btultra: first block: collecting statistics");
1088 assert(ms
->nextToUpdate
>= ms
->window
.dictLimit
1089 && ms
->nextToUpdate
<= ms
->window
.dictLimit
+ 1);
1090 memcpy(tmpRep
, rep
, sizeof(tmpRep
));
1091 ZSTD_compressBlock_opt_generic(ms
, seqStore
, tmpRep
, src
, srcSize
, 2 /*optLevel*/, ZSTD_noDict
); /* generate stats into ms->opt*/
1092 ZSTD_resetSeqStore(seqStore
);
1093 /* invalidate first scan from history */
1094 ms
->window
.base
-= srcSize
;
1095 ms
->window
.dictLimit
+= (U32
)srcSize
;
1096 ms
->window
.lowLimit
= ms
->window
.dictLimit
;
1097 ms
->nextToUpdate
= ms
->window
.dictLimit
;
1098 ms
->nextToUpdate3
= ms
->window
.dictLimit
;
1099 /* re-inforce weight of collected statistics */
1100 ZSTD_upscaleStats(&ms
->opt
);
1103 return ZSTD_compressBlock_opt_generic(ms
, seqStore
, rep
, src
, srcSize
, 2 /*optLevel*/, ZSTD_noDict
);
1106 size_t ZSTD_compressBlock_btopt_dictMatchState(
1107 ZSTD_matchState_t
* ms
, seqStore_t
* seqStore
, U32 rep
[ZSTD_REP_NUM
],
1108 const void* src
, size_t srcSize
)
1110 return ZSTD_compressBlock_opt_generic(ms
, seqStore
, rep
, src
, srcSize
, 0 /*optLevel*/, ZSTD_dictMatchState
);
1113 size_t ZSTD_compressBlock_btultra_dictMatchState(
1114 ZSTD_matchState_t
* ms
, seqStore_t
* seqStore
, U32 rep
[ZSTD_REP_NUM
],
1115 const void* src
, size_t srcSize
)
1117 return ZSTD_compressBlock_opt_generic(ms
, seqStore
, rep
, src
, srcSize
, 2 /*optLevel*/, ZSTD_dictMatchState
);
1120 size_t ZSTD_compressBlock_btopt_extDict(
1121 ZSTD_matchState_t
* ms
, seqStore_t
* seqStore
, U32 rep
[ZSTD_REP_NUM
],
1122 const void* src
, size_t srcSize
)
1124 return ZSTD_compressBlock_opt_generic(ms
, seqStore
, rep
, src
, srcSize
, 0 /*optLevel*/, ZSTD_extDict
);
1127 size_t ZSTD_compressBlock_btultra_extDict(
1128 ZSTD_matchState_t
* ms
, seqStore_t
* seqStore
, U32 rep
[ZSTD_REP_NUM
],
1129 const void* src
, size_t srcSize
)
1131 return ZSTD_compressBlock_opt_generic(ms
, seqStore
, rep
, src
, srcSize
, 2 /*optLevel*/, ZSTD_extDict
);