]>
git.proxmox.com Git - ceph.git/blob - ceph/src/zstd/contrib/linux-kernel/lib/zstd/zstd_opt.h
2 * Copyright (c) 2016-present, Przemyslaw Skibinski, Yann Collet, Facebook, Inc.
5 * This source code is licensed under the BSD-style license found in the
6 * LICENSE file in the root directory of https://github.com/facebook/zstd.
8 * This program is free software; you can redistribute it and/or modify it under
9 * the terms of the GNU General Public License version 2 as published by the
10 * Free Software Foundation. This program is dual-licensed; you may select
11 * either version 2 of the GNU General Public License ("GPL") or BSD license
15 /* Note : this file is intended to be included within zstd_compress.c */
17 #ifndef ZSTD_OPT_H_91842398743
18 #define ZSTD_OPT_H_91842398743
20 #define ZSTD_LITFREQ_ADD 2
21 #define ZSTD_FREQ_DIV 4
22 #define ZSTD_MAX_PRICE (1 << 30)
24 /*-*************************************
25 * Price functions for optimal parser
26 ***************************************/
27 FORCE_INLINE
void ZSTD_setLog2Prices(seqStore_t
*ssPtr
)
29 ssPtr
->log2matchLengthSum
= ZSTD_highbit32(ssPtr
->matchLengthSum
+ 1);
30 ssPtr
->log2litLengthSum
= ZSTD_highbit32(ssPtr
->litLengthSum
+ 1);
31 ssPtr
->log2litSum
= ZSTD_highbit32(ssPtr
->litSum
+ 1);
32 ssPtr
->log2offCodeSum
= ZSTD_highbit32(ssPtr
->offCodeSum
+ 1);
33 ssPtr
->factor
= 1 + ((ssPtr
->litSum
>> 5) / ssPtr
->litLengthSum
) + ((ssPtr
->litSum
<< 1) / (ssPtr
->litSum
+ ssPtr
->matchSum
));
36 ZSTD_STATIC
void ZSTD_rescaleFreqs(seqStore_t
*ssPtr
, const BYTE
*src
, size_t srcSize
)
40 ssPtr
->cachedLiterals
= NULL
;
41 ssPtr
->cachedPrice
= ssPtr
->cachedLitLength
= 0;
42 ssPtr
->staticPrices
= 0;
44 if (ssPtr
->litLengthSum
== 0) {
46 ssPtr
->staticPrices
= 1;
48 for (u
= 0; u
<= MaxLit
; u
++)
49 ssPtr
->litFreq
[u
] = 0;
50 for (u
= 0; u
< srcSize
; u
++)
51 ssPtr
->litFreq
[src
[u
]]++;
54 ssPtr
->litLengthSum
= MaxLL
+ 1;
55 ssPtr
->matchLengthSum
= MaxML
+ 1;
56 ssPtr
->offCodeSum
= (MaxOff
+ 1);
57 ssPtr
->matchSum
= (ZSTD_LITFREQ_ADD
<< Litbits
);
59 for (u
= 0; u
<= MaxLit
; u
++) {
60 ssPtr
->litFreq
[u
] = 1 + (ssPtr
->litFreq
[u
] >> ZSTD_FREQ_DIV
);
61 ssPtr
->litSum
+= ssPtr
->litFreq
[u
];
63 for (u
= 0; u
<= MaxLL
; u
++)
64 ssPtr
->litLengthFreq
[u
] = 1;
65 for (u
= 0; u
<= MaxML
; u
++)
66 ssPtr
->matchLengthFreq
[u
] = 1;
67 for (u
= 0; u
<= MaxOff
; u
++)
68 ssPtr
->offCodeFreq
[u
] = 1;
70 ssPtr
->matchLengthSum
= 0;
71 ssPtr
->litLengthSum
= 0;
72 ssPtr
->offCodeSum
= 0;
76 for (u
= 0; u
<= MaxLit
; u
++) {
77 ssPtr
->litFreq
[u
] = 1 + (ssPtr
->litFreq
[u
] >> (ZSTD_FREQ_DIV
+ 1));
78 ssPtr
->litSum
+= ssPtr
->litFreq
[u
];
80 for (u
= 0; u
<= MaxLL
; u
++) {
81 ssPtr
->litLengthFreq
[u
] = 1 + (ssPtr
->litLengthFreq
[u
] >> (ZSTD_FREQ_DIV
+ 1));
82 ssPtr
->litLengthSum
+= ssPtr
->litLengthFreq
[u
];
84 for (u
= 0; u
<= MaxML
; u
++) {
85 ssPtr
->matchLengthFreq
[u
] = 1 + (ssPtr
->matchLengthFreq
[u
] >> ZSTD_FREQ_DIV
);
86 ssPtr
->matchLengthSum
+= ssPtr
->matchLengthFreq
[u
];
87 ssPtr
->matchSum
+= ssPtr
->matchLengthFreq
[u
] * (u
+ 3);
89 ssPtr
->matchSum
*= ZSTD_LITFREQ_ADD
;
90 for (u
= 0; u
<= MaxOff
; u
++) {
91 ssPtr
->offCodeFreq
[u
] = 1 + (ssPtr
->offCodeFreq
[u
] >> ZSTD_FREQ_DIV
);
92 ssPtr
->offCodeSum
+= ssPtr
->offCodeFreq
[u
];
96 ZSTD_setLog2Prices(ssPtr
);
99 FORCE_INLINE U32
ZSTD_getLiteralPrice(seqStore_t
*ssPtr
, U32 litLength
, const BYTE
*literals
)
103 if (ssPtr
->staticPrices
)
104 return ZSTD_highbit32((U32
)litLength
+ 1) + (litLength
* 6);
107 return ssPtr
->log2litLengthSum
- ZSTD_highbit32(ssPtr
->litLengthFreq
[0] + 1);
110 if (ssPtr
->cachedLiterals
== literals
) {
111 U32
const additional
= litLength
- ssPtr
->cachedLitLength
;
112 const BYTE
*literals2
= ssPtr
->cachedLiterals
+ ssPtr
->cachedLitLength
;
113 price
= ssPtr
->cachedPrice
+ additional
* ssPtr
->log2litSum
;
114 for (u
= 0; u
< additional
; u
++)
115 price
-= ZSTD_highbit32(ssPtr
->litFreq
[literals2
[u
]] + 1);
116 ssPtr
->cachedPrice
= price
;
117 ssPtr
->cachedLitLength
= litLength
;
119 price
= litLength
* ssPtr
->log2litSum
;
120 for (u
= 0; u
< litLength
; u
++)
121 price
-= ZSTD_highbit32(ssPtr
->litFreq
[literals
[u
]] + 1);
123 if (litLength
>= 12) {
124 ssPtr
->cachedLiterals
= literals
;
125 ssPtr
->cachedPrice
= price
;
126 ssPtr
->cachedLitLength
= litLength
;
132 const BYTE LL_deltaCode
= 19;
133 const BYTE llCode
= (litLength
> 63) ? (BYTE
)ZSTD_highbit32(litLength
) + LL_deltaCode
: LL_Code
[litLength
];
134 price
+= LL_bits
[llCode
] + ssPtr
->log2litLengthSum
- ZSTD_highbit32(ssPtr
->litLengthFreq
[llCode
] + 1);
140 FORCE_INLINE U32
ZSTD_getPrice(seqStore_t
*seqStorePtr
, U32 litLength
, const BYTE
*literals
, U32 offset
, U32 matchLength
, const int ultra
)
144 BYTE
const offCode
= (BYTE
)ZSTD_highbit32(offset
+ 1);
146 if (seqStorePtr
->staticPrices
)
147 return ZSTD_getLiteralPrice(seqStorePtr
, litLength
, literals
) + ZSTD_highbit32((U32
)matchLength
+ 1) + 16 + offCode
;
149 price
= offCode
+ seqStorePtr
->log2offCodeSum
- ZSTD_highbit32(seqStorePtr
->offCodeFreq
[offCode
] + 1);
150 if (!ultra
&& offCode
>= 20)
151 price
+= (offCode
- 19) * 2;
155 const BYTE ML_deltaCode
= 36;
156 const BYTE mlCode
= (matchLength
> 127) ? (BYTE
)ZSTD_highbit32(matchLength
) + ML_deltaCode
: ML_Code
[matchLength
];
157 price
+= ML_bits
[mlCode
] + seqStorePtr
->log2matchLengthSum
- ZSTD_highbit32(seqStorePtr
->matchLengthFreq
[mlCode
] + 1);
160 return price
+ ZSTD_getLiteralPrice(seqStorePtr
, litLength
, literals
) + seqStorePtr
->factor
;
163 ZSTD_STATIC
void ZSTD_updatePrice(seqStore_t
*seqStorePtr
, U32 litLength
, const BYTE
*literals
, U32 offset
, U32 matchLength
)
168 seqStorePtr
->litSum
+= litLength
* ZSTD_LITFREQ_ADD
;
169 for (u
= 0; u
< litLength
; u
++)
170 seqStorePtr
->litFreq
[literals
[u
]] += ZSTD_LITFREQ_ADD
;
174 const BYTE LL_deltaCode
= 19;
175 const BYTE llCode
= (litLength
> 63) ? (BYTE
)ZSTD_highbit32(litLength
) + LL_deltaCode
: LL_Code
[litLength
];
176 seqStorePtr
->litLengthFreq
[llCode
]++;
177 seqStorePtr
->litLengthSum
++;
182 BYTE
const offCode
= (BYTE
)ZSTD_highbit32(offset
+ 1);
183 seqStorePtr
->offCodeSum
++;
184 seqStorePtr
->offCodeFreq
[offCode
]++;
189 const BYTE ML_deltaCode
= 36;
190 const BYTE mlCode
= (matchLength
> 127) ? (BYTE
)ZSTD_highbit32(matchLength
) + ML_deltaCode
: ML_Code
[matchLength
];
191 seqStorePtr
->matchLengthFreq
[mlCode
]++;
192 seqStorePtr
->matchLengthSum
++;
195 ZSTD_setLog2Prices(seqStorePtr
);
198 #define SET_PRICE(pos, mlen_, offset_, litlen_, price_) \
200 while (last_pos < pos) { \
201 opt[last_pos + 1].price = ZSTD_MAX_PRICE; \
204 opt[pos].mlen = mlen_; \
205 opt[pos].off = offset_; \
206 opt[pos].litlen = litlen_; \
207 opt[pos].price = price_; \
210 /* Update hashTable3 up to ip (excluded)
211 Assumption : always within prefix (i.e. not within extDict) */
213 U32
ZSTD_insertAndFindFirstIndexHash3(ZSTD_CCtx
*zc
, const BYTE
*ip
)
215 U32
*const hashTable3
= zc
->hashTable3
;
216 U32
const hashLog3
= zc
->hashLog3
;
217 const BYTE
*const base
= zc
->base
;
218 U32 idx
= zc
->nextToUpdate3
;
219 const U32 target
= zc
->nextToUpdate3
= (U32
)(ip
- base
);
220 const size_t hash3
= ZSTD_hash3Ptr(ip
, hashLog3
);
222 while (idx
< target
) {
223 hashTable3
[ZSTD_hash3Ptr(base
+ idx
, hashLog3
)] = idx
;
227 return hashTable3
[hash3
];
230 /*-*************************************
232 ***************************************/
233 static U32
ZSTD_insertBtAndGetAllMatches(ZSTD_CCtx
*zc
, const BYTE
*const ip
, const BYTE
*const iLimit
, U32 nbCompares
, const U32 mls
, U32 extDict
,
234 ZSTD_match_t
*matches
, const U32 minMatchLen
)
236 const BYTE
*const base
= zc
->base
;
237 const U32 curr
= (U32
)(ip
- base
);
238 const U32 hashLog
= zc
->params
.cParams
.hashLog
;
239 const size_t h
= ZSTD_hashPtr(ip
, hashLog
, mls
);
240 U32
*const hashTable
= zc
->hashTable
;
241 U32 matchIndex
= hashTable
[h
];
242 U32
*const bt
= zc
->chainTable
;
243 const U32 btLog
= zc
->params
.cParams
.chainLog
- 1;
244 const U32 btMask
= (1U << btLog
) - 1;
245 size_t commonLengthSmaller
= 0, commonLengthLarger
= 0;
246 const BYTE
*const dictBase
= zc
->dictBase
;
247 const U32 dictLimit
= zc
->dictLimit
;
248 const BYTE
*const dictEnd
= dictBase
+ dictLimit
;
249 const BYTE
*const prefixStart
= base
+ dictLimit
;
250 const U32 btLow
= btMask
>= curr
? 0 : curr
- btMask
;
251 const U32 windowLow
= zc
->lowLimit
;
252 U32
*smallerPtr
= bt
+ 2 * (curr
& btMask
);
253 U32
*largerPtr
= bt
+ 2 * (curr
& btMask
) + 1;
254 U32 matchEndIdx
= curr
+ 8;
255 U32 dummy32
; /* to be nullified at the end */
258 const U32 minMatch
= (mls
== 3) ? 3 : 4;
259 size_t bestLength
= minMatchLen
- 1;
261 if (minMatch
== 3) { /* HC3 match finder */
262 U32
const matchIndex3
= ZSTD_insertAndFindFirstIndexHash3(zc
, ip
);
263 if (matchIndex3
> windowLow
&& (curr
- matchIndex3
< (1 << 18))) {
266 if ((!extDict
) || matchIndex3
>= dictLimit
) {
267 match
= base
+ matchIndex3
;
268 if (match
[bestLength
] == ip
[bestLength
])
269 currMl
= ZSTD_count(ip
, match
, iLimit
);
271 match
= dictBase
+ matchIndex3
;
272 if (ZSTD_readMINMATCH(match
, MINMATCH
) ==
273 ZSTD_readMINMATCH(ip
, MINMATCH
)) /* assumption : matchIndex3 <= dictLimit-4 (by table construction) */
274 currMl
= ZSTD_count_2segments(ip
+ MINMATCH
, match
+ MINMATCH
, iLimit
, dictEnd
, prefixStart
) + MINMATCH
;
277 /* save best solution */
278 if (currMl
> bestLength
) {
280 matches
[mnum
].off
= ZSTD_REP_MOVE_OPT
+ curr
- matchIndex3
;
281 matches
[mnum
].len
= (U32
)currMl
;
283 if (currMl
> ZSTD_OPT_NUM
)
285 if (ip
+ currMl
== iLimit
)
286 goto update
; /* best possible, and avoid read overflow*/
291 hashTable
[h
] = curr
; /* Update Hash Table */
293 while (nbCompares
-- && (matchIndex
> windowLow
)) {
294 U32
*nextPtr
= bt
+ 2 * (matchIndex
& btMask
);
295 size_t matchLength
= MIN(commonLengthSmaller
, commonLengthLarger
); /* guaranteed minimum nb of common bytes */
298 if ((!extDict
) || (matchIndex
+ matchLength
>= dictLimit
)) {
299 match
= base
+ matchIndex
;
300 if (match
[matchLength
] == ip
[matchLength
]) {
301 matchLength
+= ZSTD_count(ip
+ matchLength
+ 1, match
+ matchLength
+ 1, iLimit
) + 1;
304 match
= dictBase
+ matchIndex
;
305 matchLength
+= ZSTD_count_2segments(ip
+ matchLength
, match
+ matchLength
, iLimit
, dictEnd
, prefixStart
);
306 if (matchIndex
+ matchLength
>= dictLimit
)
307 match
= base
+ matchIndex
; /* to prepare for next usage of match[matchLength] */
310 if (matchLength
> bestLength
) {
311 if (matchLength
> matchEndIdx
- matchIndex
)
312 matchEndIdx
= matchIndex
+ (U32
)matchLength
;
313 bestLength
= matchLength
;
314 matches
[mnum
].off
= ZSTD_REP_MOVE_OPT
+ curr
- matchIndex
;
315 matches
[mnum
].len
= (U32
)matchLength
;
317 if (matchLength
> ZSTD_OPT_NUM
)
319 if (ip
+ matchLength
== iLimit
) /* equal : no way to know if inf or sup */
320 break; /* drop, to guarantee consistency (miss a little bit of compression) */
323 if (match
[matchLength
] < ip
[matchLength
]) {
324 /* match is smaller than curr */
325 *smallerPtr
= matchIndex
; /* update smaller idx */
326 commonLengthSmaller
= matchLength
; /* all smaller will now have at least this guaranteed common length */
327 if (matchIndex
<= btLow
) {
328 smallerPtr
= &dummy32
;
330 } /* beyond tree size, stop the search */
331 smallerPtr
= nextPtr
+ 1; /* new "smaller" => larger of match */
332 matchIndex
= nextPtr
[1]; /* new matchIndex larger than previous (closer to curr) */
334 /* match is larger than curr */
335 *largerPtr
= matchIndex
;
336 commonLengthLarger
= matchLength
;
337 if (matchIndex
<= btLow
) {
338 largerPtr
= &dummy32
;
340 } /* beyond tree size, stop the search */
342 matchIndex
= nextPtr
[0];
346 *smallerPtr
= *largerPtr
= 0;
349 zc
->nextToUpdate
= (matchEndIdx
> curr
+ 8) ? matchEndIdx
- 8 : curr
+ 1;
353 /** Tree updater, providing best match */
354 static U32
ZSTD_BtGetAllMatches(ZSTD_CCtx
*zc
, const BYTE
*const ip
, const BYTE
*const iLimit
, const U32 maxNbAttempts
, const U32 mls
, ZSTD_match_t
*matches
,
355 const U32 minMatchLen
)
357 if (ip
< zc
->base
+ zc
->nextToUpdate
)
358 return 0; /* skipped area */
359 ZSTD_updateTree(zc
, ip
, iLimit
, maxNbAttempts
, mls
);
360 return ZSTD_insertBtAndGetAllMatches(zc
, ip
, iLimit
, maxNbAttempts
, mls
, 0, matches
, minMatchLen
);
363 static U32
ZSTD_BtGetAllMatches_selectMLS(ZSTD_CCtx
*zc
, /* Index table will be updated */
364 const BYTE
*ip
, const BYTE
*const iHighLimit
, const U32 maxNbAttempts
, const U32 matchLengthSearch
,
365 ZSTD_match_t
*matches
, const U32 minMatchLen
)
367 switch (matchLengthSearch
) {
368 case 3: return ZSTD_BtGetAllMatches(zc
, ip
, iHighLimit
, maxNbAttempts
, 3, matches
, minMatchLen
);
370 case 4: return ZSTD_BtGetAllMatches(zc
, ip
, iHighLimit
, maxNbAttempts
, 4, matches
, minMatchLen
);
371 case 5: return ZSTD_BtGetAllMatches(zc
, ip
, iHighLimit
, maxNbAttempts
, 5, matches
, minMatchLen
);
373 case 6: return ZSTD_BtGetAllMatches(zc
, ip
, iHighLimit
, maxNbAttempts
, 6, matches
, minMatchLen
);
377 /** Tree updater, providing best match */
378 static U32
ZSTD_BtGetAllMatches_extDict(ZSTD_CCtx
*zc
, const BYTE
*const ip
, const BYTE
*const iLimit
, const U32 maxNbAttempts
, const U32 mls
,
379 ZSTD_match_t
*matches
, const U32 minMatchLen
)
381 if (ip
< zc
->base
+ zc
->nextToUpdate
)
382 return 0; /* skipped area */
383 ZSTD_updateTree_extDict(zc
, ip
, iLimit
, maxNbAttempts
, mls
);
384 return ZSTD_insertBtAndGetAllMatches(zc
, ip
, iLimit
, maxNbAttempts
, mls
, 1, matches
, minMatchLen
);
387 static U32
ZSTD_BtGetAllMatches_selectMLS_extDict(ZSTD_CCtx
*zc
, /* Index table will be updated */
388 const BYTE
*ip
, const BYTE
*const iHighLimit
, const U32 maxNbAttempts
, const U32 matchLengthSearch
,
389 ZSTD_match_t
*matches
, const U32 minMatchLen
)
391 switch (matchLengthSearch
) {
392 case 3: return ZSTD_BtGetAllMatches_extDict(zc
, ip
, iHighLimit
, maxNbAttempts
, 3, matches
, minMatchLen
);
394 case 4: return ZSTD_BtGetAllMatches_extDict(zc
, ip
, iHighLimit
, maxNbAttempts
, 4, matches
, minMatchLen
);
395 case 5: return ZSTD_BtGetAllMatches_extDict(zc
, ip
, iHighLimit
, maxNbAttempts
, 5, matches
, minMatchLen
);
397 case 6: return ZSTD_BtGetAllMatches_extDict(zc
, ip
, iHighLimit
, maxNbAttempts
, 6, matches
, minMatchLen
);
401 /*-*******************************
403 *********************************/
405 void ZSTD_compressBlock_opt_generic(ZSTD_CCtx
*ctx
, const void *src
, size_t srcSize
, const int ultra
)
407 seqStore_t
*seqStorePtr
= &(ctx
->seqStore
);
408 const BYTE
*const istart
= (const BYTE
*)src
;
409 const BYTE
*ip
= istart
;
410 const BYTE
*anchor
= istart
;
411 const BYTE
*const iend
= istart
+ srcSize
;
412 const BYTE
*const ilimit
= iend
- 8;
413 const BYTE
*const base
= ctx
->base
;
414 const BYTE
*const prefixStart
= base
+ ctx
->dictLimit
;
416 const U32 maxSearches
= 1U << ctx
->params
.cParams
.searchLog
;
417 const U32 sufficient_len
= ctx
->params
.cParams
.targetLength
;
418 const U32 mls
= ctx
->params
.cParams
.searchLength
;
419 const U32 minMatch
= (ctx
->params
.cParams
.searchLength
== 3) ? 3 : 4;
421 ZSTD_optimal_t
*opt
= seqStorePtr
->priceTable
;
422 ZSTD_match_t
*matches
= seqStorePtr
->matchTable
;
424 U32 offset
, rep
[ZSTD_REP_NUM
];
427 ctx
->nextToUpdate3
= ctx
->nextToUpdate
;
428 ZSTD_rescaleFreqs(seqStorePtr
, (const BYTE
*)src
, srcSize
);
429 ip
+= (ip
== prefixStart
);
432 for (i
= 0; i
< ZSTD_REP_NUM
; i
++)
433 rep
[i
] = ctx
->rep
[i
];
437 while (ip
< ilimit
) {
438 U32 cur
, match_num
, last_pos
, litlen
, price
;
439 U32 u
, mlen
, best_mlen
, best_off
, litLength
;
440 memset(opt
, 0, sizeof(ZSTD_optimal_t
));
442 litlen
= (U32
)(ip
- anchor
);
446 U32 i
, last_i
= ZSTD_REP_CHECK
+ (ip
== anchor
);
447 for (i
= (ip
== anchor
); i
< last_i
; i
++) {
448 const S32 repCur
= (i
== ZSTD_REP_MOVE_OPT
) ? (rep
[0] - 1) : rep
[i
];
449 if ((repCur
> 0) && (repCur
< (S32
)(ip
- prefixStart
)) &&
450 (ZSTD_readMINMATCH(ip
, minMatch
) == ZSTD_readMINMATCH(ip
- repCur
, minMatch
))) {
451 mlen
= (U32
)ZSTD_count(ip
+ minMatch
, ip
+ minMatch
- repCur
, iend
) + minMatch
;
452 if (mlen
> sufficient_len
|| mlen
>= ZSTD_OPT_NUM
) {
459 best_off
= i
- (ip
== anchor
);
461 price
= ZSTD_getPrice(seqStorePtr
, litlen
, anchor
, best_off
, mlen
- MINMATCH
, ultra
);
462 if (mlen
> last_pos
|| price
< opt
[mlen
].price
)
463 SET_PRICE(mlen
, mlen
, i
, litlen
, price
); /* note : macro modifies last_pos */
465 } while (mlen
>= minMatch
);
470 match_num
= ZSTD_BtGetAllMatches_selectMLS(ctx
, ip
, iend
, maxSearches
, mls
, matches
, minMatch
);
472 if (!last_pos
&& !match_num
) {
477 if (match_num
&& (matches
[match_num
- 1].len
> sufficient_len
|| matches
[match_num
- 1].len
>= ZSTD_OPT_NUM
)) {
478 best_mlen
= matches
[match_num
- 1].len
;
479 best_off
= matches
[match_num
- 1].off
;
485 /* set prices using matches at position = 0 */
486 best_mlen
= (last_pos
) ? last_pos
: minMatch
;
487 for (u
= 0; u
< match_num
; u
++) {
488 mlen
= (u
> 0) ? matches
[u
- 1].len
+ 1 : best_mlen
;
489 best_mlen
= matches
[u
].len
;
490 while (mlen
<= best_mlen
) {
491 price
= ZSTD_getPrice(seqStorePtr
, litlen
, anchor
, matches
[u
].off
- 1, mlen
- MINMATCH
, ultra
);
492 if (mlen
> last_pos
|| price
< opt
[mlen
].price
)
493 SET_PRICE(mlen
, mlen
, matches
[u
].off
, litlen
, price
); /* note : macro modifies last_pos */
498 if (last_pos
< minMatch
) {
503 /* initialize opt[0] */
506 for (i
= 0; i
< ZSTD_REP_NUM
; i
++)
507 opt
[0].rep
[i
] = rep
[i
];
510 opt
[0].litlen
= litlen
;
512 /* check further positions */
513 for (cur
= 1; cur
<= last_pos
; cur
++) {
516 if (opt
[cur
- 1].mlen
== 1) {
517 litlen
= opt
[cur
- 1].litlen
+ 1;
519 price
= opt
[cur
- litlen
].price
+ ZSTD_getLiteralPrice(seqStorePtr
, litlen
, inr
- litlen
);
521 price
= ZSTD_getLiteralPrice(seqStorePtr
, litlen
, anchor
);
524 price
= opt
[cur
- 1].price
+ ZSTD_getLiteralPrice(seqStorePtr
, litlen
, inr
- 1);
527 if (cur
> last_pos
|| price
<= opt
[cur
].price
)
528 SET_PRICE(cur
, 1, 0, litlen
, price
);
533 if (inr
> ilimit
) /* last match must start at a minimum distance of 8 from oend */
536 mlen
= opt
[cur
].mlen
;
537 if (opt
[cur
].off
> ZSTD_REP_MOVE_OPT
) {
538 opt
[cur
].rep
[2] = opt
[cur
- mlen
].rep
[1];
539 opt
[cur
].rep
[1] = opt
[cur
- mlen
].rep
[0];
540 opt
[cur
].rep
[0] = opt
[cur
].off
- ZSTD_REP_MOVE_OPT
;
542 opt
[cur
].rep
[2] = (opt
[cur
].off
> 1) ? opt
[cur
- mlen
].rep
[1] : opt
[cur
- mlen
].rep
[2];
543 opt
[cur
].rep
[1] = (opt
[cur
].off
> 0) ? opt
[cur
- mlen
].rep
[0] : opt
[cur
- mlen
].rep
[1];
545 ((opt
[cur
].off
== ZSTD_REP_MOVE_OPT
) && (mlen
!= 1)) ? (opt
[cur
- mlen
].rep
[0] - 1) : (opt
[cur
- mlen
].rep
[opt
[cur
].off
]);
548 best_mlen
= minMatch
;
550 U32 i
, last_i
= ZSTD_REP_CHECK
+ (mlen
!= 1);
551 for (i
= (opt
[cur
].mlen
!= 1); i
< last_i
; i
++) { /* check rep */
552 const S32 repCur
= (i
== ZSTD_REP_MOVE_OPT
) ? (opt
[cur
].rep
[0] - 1) : opt
[cur
].rep
[i
];
553 if ((repCur
> 0) && (repCur
< (S32
)(inr
- prefixStart
)) &&
554 (ZSTD_readMINMATCH(inr
, minMatch
) == ZSTD_readMINMATCH(inr
- repCur
, minMatch
))) {
555 mlen
= (U32
)ZSTD_count(inr
+ minMatch
, inr
+ minMatch
- repCur
, iend
) + minMatch
;
557 if (mlen
> sufficient_len
|| cur
+ mlen
>= ZSTD_OPT_NUM
) {
564 best_off
= i
- (opt
[cur
].mlen
!= 1);
565 if (mlen
> best_mlen
)
569 if (opt
[cur
].mlen
== 1) {
570 litlen
= opt
[cur
].litlen
;
572 price
= opt
[cur
- litlen
].price
+ ZSTD_getPrice(seqStorePtr
, litlen
, inr
- litlen
,
573 best_off
, mlen
- MINMATCH
, ultra
);
575 price
= ZSTD_getPrice(seqStorePtr
, litlen
, anchor
, best_off
, mlen
- MINMATCH
, ultra
);
578 price
= opt
[cur
].price
+ ZSTD_getPrice(seqStorePtr
, 0, NULL
, best_off
, mlen
- MINMATCH
, ultra
);
581 if (cur
+ mlen
> last_pos
|| price
<= opt
[cur
+ mlen
].price
)
582 SET_PRICE(cur
+ mlen
, mlen
, i
, litlen
, price
);
584 } while (mlen
>= minMatch
);
589 match_num
= ZSTD_BtGetAllMatches_selectMLS(ctx
, inr
, iend
, maxSearches
, mls
, matches
, best_mlen
);
591 if (match_num
> 0 && (matches
[match_num
- 1].len
> sufficient_len
|| cur
+ matches
[match_num
- 1].len
>= ZSTD_OPT_NUM
)) {
592 best_mlen
= matches
[match_num
- 1].len
;
593 best_off
= matches
[match_num
- 1].off
;
598 /* set prices using matches at position = cur */
599 for (u
= 0; u
< match_num
; u
++) {
600 mlen
= (u
> 0) ? matches
[u
- 1].len
+ 1 : best_mlen
;
601 best_mlen
= matches
[u
].len
;
603 while (mlen
<= best_mlen
) {
604 if (opt
[cur
].mlen
== 1) {
605 litlen
= opt
[cur
].litlen
;
607 price
= opt
[cur
- litlen
].price
+ ZSTD_getPrice(seqStorePtr
, litlen
, ip
+ cur
- litlen
,
608 matches
[u
].off
- 1, mlen
- MINMATCH
, ultra
);
610 price
= ZSTD_getPrice(seqStorePtr
, litlen
, anchor
, matches
[u
].off
- 1, mlen
- MINMATCH
, ultra
);
613 price
= opt
[cur
].price
+ ZSTD_getPrice(seqStorePtr
, 0, NULL
, matches
[u
].off
- 1, mlen
- MINMATCH
, ultra
);
616 if (cur
+ mlen
> last_pos
|| (price
< opt
[cur
+ mlen
].price
))
617 SET_PRICE(cur
+ mlen
, mlen
, matches
[u
].off
, litlen
, price
);
624 best_mlen
= opt
[last_pos
].mlen
;
625 best_off
= opt
[last_pos
].off
;
626 cur
= last_pos
- best_mlen
;
629 _storeSequence
: /* cur, last_pos, best_mlen, best_off have to be set */
633 mlen
= opt
[cur
].mlen
;
634 offset
= opt
[cur
].off
;
635 opt
[cur
].mlen
= best_mlen
;
636 opt
[cur
].off
= best_off
;
644 for (u
= 0; u
<= last_pos
;) {
648 for (cur
= 0; cur
< last_pos
;) {
649 mlen
= opt
[cur
].mlen
;
655 offset
= opt
[cur
].off
;
657 litLength
= (U32
)(ip
- anchor
);
659 if (offset
> ZSTD_REP_MOVE_OPT
) {
662 rep
[0] = offset
- ZSTD_REP_MOVE_OPT
;
666 best_off
= (offset
== ZSTD_REP_MOVE_OPT
) ? (rep
[0] - 1) : (rep
[offset
]);
676 ZSTD_updatePrice(seqStorePtr
, litLength
, anchor
, offset
, mlen
- MINMATCH
);
677 ZSTD_storeSeq(seqStorePtr
, litLength
, anchor
, offset
, mlen
- MINMATCH
);
678 anchor
= ip
= ip
+ mlen
;
680 } /* for (cur=0; cur < last_pos; ) */
682 /* Save reps for next block */
685 for (i
= 0; i
< ZSTD_REP_NUM
; i
++)
686 ctx
->repToConfirm
[i
] = rep
[i
];
691 size_t const lastLLSize
= iend
- anchor
;
692 memcpy(seqStorePtr
->lit
, anchor
, lastLLSize
);
693 seqStorePtr
->lit
+= lastLLSize
;
698 void ZSTD_compressBlock_opt_extDict_generic(ZSTD_CCtx
*ctx
, const void *src
, size_t srcSize
, const int ultra
)
700 seqStore_t
*seqStorePtr
= &(ctx
->seqStore
);
701 const BYTE
*const istart
= (const BYTE
*)src
;
702 const BYTE
*ip
= istart
;
703 const BYTE
*anchor
= istart
;
704 const BYTE
*const iend
= istart
+ srcSize
;
705 const BYTE
*const ilimit
= iend
- 8;
706 const BYTE
*const base
= ctx
->base
;
707 const U32 lowestIndex
= ctx
->lowLimit
;
708 const U32 dictLimit
= ctx
->dictLimit
;
709 const BYTE
*const prefixStart
= base
+ dictLimit
;
710 const BYTE
*const dictBase
= ctx
->dictBase
;
711 const BYTE
*const dictEnd
= dictBase
+ dictLimit
;
713 const U32 maxSearches
= 1U << ctx
->params
.cParams
.searchLog
;
714 const U32 sufficient_len
= ctx
->params
.cParams
.targetLength
;
715 const U32 mls
= ctx
->params
.cParams
.searchLength
;
716 const U32 minMatch
= (ctx
->params
.cParams
.searchLength
== 3) ? 3 : 4;
718 ZSTD_optimal_t
*opt
= seqStorePtr
->priceTable
;
719 ZSTD_match_t
*matches
= seqStorePtr
->matchTable
;
723 U32 offset
, rep
[ZSTD_REP_NUM
];
726 for (i
= 0; i
< ZSTD_REP_NUM
; i
++)
727 rep
[i
] = ctx
->rep
[i
];
730 ctx
->nextToUpdate3
= ctx
->nextToUpdate
;
731 ZSTD_rescaleFreqs(seqStorePtr
, (const BYTE
*)src
, srcSize
);
732 ip
+= (ip
== prefixStart
);
735 while (ip
< ilimit
) {
736 U32 cur
, match_num
, last_pos
, litlen
, price
;
737 U32 u
, mlen
, best_mlen
, best_off
, litLength
;
738 U32 curr
= (U32
)(ip
- base
);
739 memset(opt
, 0, sizeof(ZSTD_optimal_t
));
741 opt
[0].litlen
= (U32
)(ip
- anchor
);
745 U32 i
, last_i
= ZSTD_REP_CHECK
+ (ip
== anchor
);
746 for (i
= (ip
== anchor
); i
< last_i
; i
++) {
747 const S32 repCur
= (i
== ZSTD_REP_MOVE_OPT
) ? (rep
[0] - 1) : rep
[i
];
748 const U32 repIndex
= (U32
)(curr
- repCur
);
749 const BYTE
*const repBase
= repIndex
< dictLimit
? dictBase
: base
;
750 const BYTE
*const repMatch
= repBase
+ repIndex
;
751 if ((repCur
> 0 && repCur
<= (S32
)curr
) &&
752 (((U32
)((dictLimit
- 1) - repIndex
) >= 3) & (repIndex
> lowestIndex
)) /* intentional overflow */
753 && (ZSTD_readMINMATCH(ip
, minMatch
) == ZSTD_readMINMATCH(repMatch
, minMatch
))) {
754 /* repcode detected we should take it */
755 const BYTE
*const repEnd
= repIndex
< dictLimit
? dictEnd
: iend
;
756 mlen
= (U32
)ZSTD_count_2segments(ip
+ minMatch
, repMatch
+ minMatch
, iend
, repEnd
, prefixStart
) + minMatch
;
758 if (mlen
> sufficient_len
|| mlen
>= ZSTD_OPT_NUM
) {
766 best_off
= i
- (ip
== anchor
);
767 litlen
= opt
[0].litlen
;
769 price
= ZSTD_getPrice(seqStorePtr
, litlen
, anchor
, best_off
, mlen
- MINMATCH
, ultra
);
770 if (mlen
> last_pos
|| price
< opt
[mlen
].price
)
771 SET_PRICE(mlen
, mlen
, i
, litlen
, price
); /* note : macro modifies last_pos */
773 } while (mlen
>= minMatch
);
778 match_num
= ZSTD_BtGetAllMatches_selectMLS_extDict(ctx
, ip
, iend
, maxSearches
, mls
, matches
, minMatch
); /* first search (depth 0) */
780 if (!last_pos
&& !match_num
) {
787 for (i
= 0; i
< ZSTD_REP_NUM
; i
++)
788 opt
[0].rep
[i
] = rep
[i
];
792 if (match_num
&& (matches
[match_num
- 1].len
> sufficient_len
|| matches
[match_num
- 1].len
>= ZSTD_OPT_NUM
)) {
793 best_mlen
= matches
[match_num
- 1].len
;
794 best_off
= matches
[match_num
- 1].off
;
800 best_mlen
= (last_pos
) ? last_pos
: minMatch
;
802 /* set prices using matches at position = 0 */
803 for (u
= 0; u
< match_num
; u
++) {
804 mlen
= (u
> 0) ? matches
[u
- 1].len
+ 1 : best_mlen
;
805 best_mlen
= matches
[u
].len
;
806 litlen
= opt
[0].litlen
;
807 while (mlen
<= best_mlen
) {
808 price
= ZSTD_getPrice(seqStorePtr
, litlen
, anchor
, matches
[u
].off
- 1, mlen
- MINMATCH
, ultra
);
809 if (mlen
> last_pos
|| price
< opt
[mlen
].price
)
810 SET_PRICE(mlen
, mlen
, matches
[u
].off
, litlen
, price
);
815 if (last_pos
< minMatch
) {
820 /* check further positions */
821 for (cur
= 1; cur
<= last_pos
; cur
++) {
824 if (opt
[cur
- 1].mlen
== 1) {
825 litlen
= opt
[cur
- 1].litlen
+ 1;
827 price
= opt
[cur
- litlen
].price
+ ZSTD_getLiteralPrice(seqStorePtr
, litlen
, inr
- litlen
);
829 price
= ZSTD_getLiteralPrice(seqStorePtr
, litlen
, anchor
);
832 price
= opt
[cur
- 1].price
+ ZSTD_getLiteralPrice(seqStorePtr
, litlen
, inr
- 1);
835 if (cur
> last_pos
|| price
<= opt
[cur
].price
)
836 SET_PRICE(cur
, 1, 0, litlen
, price
);
841 if (inr
> ilimit
) /* last match must start at a minimum distance of 8 from oend */
844 mlen
= opt
[cur
].mlen
;
845 if (opt
[cur
].off
> ZSTD_REP_MOVE_OPT
) {
846 opt
[cur
].rep
[2] = opt
[cur
- mlen
].rep
[1];
847 opt
[cur
].rep
[1] = opt
[cur
- mlen
].rep
[0];
848 opt
[cur
].rep
[0] = opt
[cur
].off
- ZSTD_REP_MOVE_OPT
;
850 opt
[cur
].rep
[2] = (opt
[cur
].off
> 1) ? opt
[cur
- mlen
].rep
[1] : opt
[cur
- mlen
].rep
[2];
851 opt
[cur
].rep
[1] = (opt
[cur
].off
> 0) ? opt
[cur
- mlen
].rep
[0] : opt
[cur
- mlen
].rep
[1];
853 ((opt
[cur
].off
== ZSTD_REP_MOVE_OPT
) && (mlen
!= 1)) ? (opt
[cur
- mlen
].rep
[0] - 1) : (opt
[cur
- mlen
].rep
[opt
[cur
].off
]);
856 best_mlen
= minMatch
;
858 U32 i
, last_i
= ZSTD_REP_CHECK
+ (mlen
!= 1);
859 for (i
= (mlen
!= 1); i
< last_i
; i
++) {
860 const S32 repCur
= (i
== ZSTD_REP_MOVE_OPT
) ? (opt
[cur
].rep
[0] - 1) : opt
[cur
].rep
[i
];
861 const U32 repIndex
= (U32
)(curr
+ cur
- repCur
);
862 const BYTE
*const repBase
= repIndex
< dictLimit
? dictBase
: base
;
863 const BYTE
*const repMatch
= repBase
+ repIndex
;
864 if ((repCur
> 0 && repCur
<= (S32
)(curr
+ cur
)) &&
865 (((U32
)((dictLimit
- 1) - repIndex
) >= 3) & (repIndex
> lowestIndex
)) /* intentional overflow */
866 && (ZSTD_readMINMATCH(inr
, minMatch
) == ZSTD_readMINMATCH(repMatch
, minMatch
))) {
867 /* repcode detected */
868 const BYTE
*const repEnd
= repIndex
< dictLimit
? dictEnd
: iend
;
869 mlen
= (U32
)ZSTD_count_2segments(inr
+ minMatch
, repMatch
+ minMatch
, iend
, repEnd
, prefixStart
) + minMatch
;
871 if (mlen
> sufficient_len
|| cur
+ mlen
>= ZSTD_OPT_NUM
) {
878 best_off
= i
- (opt
[cur
].mlen
!= 1);
879 if (mlen
> best_mlen
)
883 if (opt
[cur
].mlen
== 1) {
884 litlen
= opt
[cur
].litlen
;
886 price
= opt
[cur
- litlen
].price
+ ZSTD_getPrice(seqStorePtr
, litlen
, inr
- litlen
,
887 best_off
, mlen
- MINMATCH
, ultra
);
889 price
= ZSTD_getPrice(seqStorePtr
, litlen
, anchor
, best_off
, mlen
- MINMATCH
, ultra
);
892 price
= opt
[cur
].price
+ ZSTD_getPrice(seqStorePtr
, 0, NULL
, best_off
, mlen
- MINMATCH
, ultra
);
895 if (cur
+ mlen
> last_pos
|| price
<= opt
[cur
+ mlen
].price
)
896 SET_PRICE(cur
+ mlen
, mlen
, i
, litlen
, price
);
898 } while (mlen
>= minMatch
);
903 match_num
= ZSTD_BtGetAllMatches_selectMLS_extDict(ctx
, inr
, iend
, maxSearches
, mls
, matches
, minMatch
);
905 if (match_num
> 0 && (matches
[match_num
- 1].len
> sufficient_len
|| cur
+ matches
[match_num
- 1].len
>= ZSTD_OPT_NUM
)) {
906 best_mlen
= matches
[match_num
- 1].len
;
907 best_off
= matches
[match_num
- 1].off
;
912 /* set prices using matches at position = cur */
913 for (u
= 0; u
< match_num
; u
++) {
914 mlen
= (u
> 0) ? matches
[u
- 1].len
+ 1 : best_mlen
;
915 best_mlen
= matches
[u
].len
;
917 while (mlen
<= best_mlen
) {
918 if (opt
[cur
].mlen
== 1) {
919 litlen
= opt
[cur
].litlen
;
921 price
= opt
[cur
- litlen
].price
+ ZSTD_getPrice(seqStorePtr
, litlen
, ip
+ cur
- litlen
,
922 matches
[u
].off
- 1, mlen
- MINMATCH
, ultra
);
924 price
= ZSTD_getPrice(seqStorePtr
, litlen
, anchor
, matches
[u
].off
- 1, mlen
- MINMATCH
, ultra
);
927 price
= opt
[cur
].price
+ ZSTD_getPrice(seqStorePtr
, 0, NULL
, matches
[u
].off
- 1, mlen
- MINMATCH
, ultra
);
930 if (cur
+ mlen
> last_pos
|| (price
< opt
[cur
+ mlen
].price
))
931 SET_PRICE(cur
+ mlen
, mlen
, matches
[u
].off
, litlen
, price
);
936 } /* for (cur = 1; cur <= last_pos; cur++) */
938 best_mlen
= opt
[last_pos
].mlen
;
939 best_off
= opt
[last_pos
].off
;
940 cur
= last_pos
- best_mlen
;
943 _storeSequence
: /* cur, last_pos, best_mlen, best_off have to be set */
947 mlen
= opt
[cur
].mlen
;
948 offset
= opt
[cur
].off
;
949 opt
[cur
].mlen
= best_mlen
;
950 opt
[cur
].off
= best_off
;
958 for (u
= 0; u
<= last_pos
;) {
962 for (cur
= 0; cur
< last_pos
;) {
963 mlen
= opt
[cur
].mlen
;
969 offset
= opt
[cur
].off
;
971 litLength
= (U32
)(ip
- anchor
);
973 if (offset
> ZSTD_REP_MOVE_OPT
) {
976 rep
[0] = offset
- ZSTD_REP_MOVE_OPT
;
980 best_off
= (offset
== ZSTD_REP_MOVE_OPT
) ? (rep
[0] - 1) : (rep
[offset
]);
991 ZSTD_updatePrice(seqStorePtr
, litLength
, anchor
, offset
, mlen
- MINMATCH
);
992 ZSTD_storeSeq(seqStorePtr
, litLength
, anchor
, offset
, mlen
- MINMATCH
);
993 anchor
= ip
= ip
+ mlen
;
995 } /* for (cur=0; cur < last_pos; ) */
997 /* Save reps for next block */
1000 for (i
= 0; i
< ZSTD_REP_NUM
; i
++)
1001 ctx
->repToConfirm
[i
] = rep
[i
];
1006 size_t lastLLSize
= iend
- anchor
;
1007 memcpy(seqStorePtr
->lit
, anchor
, lastLLSize
);
1008 seqStorePtr
->lit
+= lastLLSize
;
1012 #endif /* ZSTD_OPT_H_91842398743 */