Commit | Line | Data |
---|---|---|
73f3d1b4 NT |
1 | /** |
2 | * Copyright (c) 2016-present, Przemyslaw Skibinski, Yann Collet, Facebook, Inc. | |
3 | * All rights reserved. | |
4 | * | |
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. | |
7 | * An additional grant of patent rights can be found in the PATENTS file in the | |
8 | * same directory. | |
9 | * | |
10 | * This program is free software; you can redistribute it and/or modify it under | |
11 | * the terms of the GNU General Public License version 2 as published by the | |
12 | * Free Software Foundation. This program is dual-licensed; you may select | |
13 | * either version 2 of the GNU General Public License ("GPL") or BSD license | |
14 | * ("BSD"). | |
15 | */ | |
16 | ||
17 | /* Note : this file is intended to be included within zstd_compress.c */ | |
18 | ||
19 | #ifndef ZSTD_OPT_H_91842398743 | |
20 | #define ZSTD_OPT_H_91842398743 | |
21 | ||
22 | #define ZSTD_LITFREQ_ADD 2 | |
23 | #define ZSTD_FREQ_DIV 4 | |
24 | #define ZSTD_MAX_PRICE (1 << 30) | |
25 | ||
26 | /*-************************************* | |
27 | * Price functions for optimal parser | |
28 | ***************************************/ | |
29 | FORCE_INLINE void ZSTD_setLog2Prices(seqStore_t *ssPtr) | |
30 | { | |
31 | ssPtr->log2matchLengthSum = ZSTD_highbit32(ssPtr->matchLengthSum + 1); | |
32 | ssPtr->log2litLengthSum = ZSTD_highbit32(ssPtr->litLengthSum + 1); | |
33 | ssPtr->log2litSum = ZSTD_highbit32(ssPtr->litSum + 1); | |
34 | ssPtr->log2offCodeSum = ZSTD_highbit32(ssPtr->offCodeSum + 1); | |
35 | ssPtr->factor = 1 + ((ssPtr->litSum >> 5) / ssPtr->litLengthSum) + ((ssPtr->litSum << 1) / (ssPtr->litSum + ssPtr->matchSum)); | |
36 | } | |
37 | ||
38 | ZSTD_STATIC void ZSTD_rescaleFreqs(seqStore_t *ssPtr, const BYTE *src, size_t srcSize) | |
39 | { | |
40 | unsigned u; | |
41 | ||
42 | ssPtr->cachedLiterals = NULL; | |
43 | ssPtr->cachedPrice = ssPtr->cachedLitLength = 0; | |
44 | ssPtr->staticPrices = 0; | |
45 | ||
46 | if (ssPtr->litLengthSum == 0) { | |
47 | if (srcSize <= 1024) | |
48 | ssPtr->staticPrices = 1; | |
49 | ||
50 | for (u = 0; u <= MaxLit; u++) | |
51 | ssPtr->litFreq[u] = 0; | |
52 | for (u = 0; u < srcSize; u++) | |
53 | ssPtr->litFreq[src[u]]++; | |
54 | ||
55 | ssPtr->litSum = 0; | |
56 | ssPtr->litLengthSum = MaxLL + 1; | |
57 | ssPtr->matchLengthSum = MaxML + 1; | |
58 | ssPtr->offCodeSum = (MaxOff + 1); | |
59 | ssPtr->matchSum = (ZSTD_LITFREQ_ADD << Litbits); | |
60 | ||
61 | for (u = 0; u <= MaxLit; u++) { | |
62 | ssPtr->litFreq[u] = 1 + (ssPtr->litFreq[u] >> ZSTD_FREQ_DIV); | |
63 | ssPtr->litSum += ssPtr->litFreq[u]; | |
64 | } | |
65 | for (u = 0; u <= MaxLL; u++) | |
66 | ssPtr->litLengthFreq[u] = 1; | |
67 | for (u = 0; u <= MaxML; u++) | |
68 | ssPtr->matchLengthFreq[u] = 1; | |
69 | for (u = 0; u <= MaxOff; u++) | |
70 | ssPtr->offCodeFreq[u] = 1; | |
71 | } else { | |
72 | ssPtr->matchLengthSum = 0; | |
73 | ssPtr->litLengthSum = 0; | |
74 | ssPtr->offCodeSum = 0; | |
75 | ssPtr->matchSum = 0; | |
76 | ssPtr->litSum = 0; | |
77 | ||
78 | for (u = 0; u <= MaxLit; u++) { | |
79 | ssPtr->litFreq[u] = 1 + (ssPtr->litFreq[u] >> (ZSTD_FREQ_DIV + 1)); | |
80 | ssPtr->litSum += ssPtr->litFreq[u]; | |
81 | } | |
82 | for (u = 0; u <= MaxLL; u++) { | |
83 | ssPtr->litLengthFreq[u] = 1 + (ssPtr->litLengthFreq[u] >> (ZSTD_FREQ_DIV + 1)); | |
84 | ssPtr->litLengthSum += ssPtr->litLengthFreq[u]; | |
85 | } | |
86 | for (u = 0; u <= MaxML; u++) { | |
87 | ssPtr->matchLengthFreq[u] = 1 + (ssPtr->matchLengthFreq[u] >> ZSTD_FREQ_DIV); | |
88 | ssPtr->matchLengthSum += ssPtr->matchLengthFreq[u]; | |
89 | ssPtr->matchSum += ssPtr->matchLengthFreq[u] * (u + 3); | |
90 | } | |
91 | ssPtr->matchSum *= ZSTD_LITFREQ_ADD; | |
92 | for (u = 0; u <= MaxOff; u++) { | |
93 | ssPtr->offCodeFreq[u] = 1 + (ssPtr->offCodeFreq[u] >> ZSTD_FREQ_DIV); | |
94 | ssPtr->offCodeSum += ssPtr->offCodeFreq[u]; | |
95 | } | |
96 | } | |
97 | ||
98 | ZSTD_setLog2Prices(ssPtr); | |
99 | } | |
100 | ||
101 | FORCE_INLINE U32 ZSTD_getLiteralPrice(seqStore_t *ssPtr, U32 litLength, const BYTE *literals) | |
102 | { | |
103 | U32 price, u; | |
104 | ||
105 | if (ssPtr->staticPrices) | |
106 | return ZSTD_highbit32((U32)litLength + 1) + (litLength * 6); | |
107 | ||
108 | if (litLength == 0) | |
109 | return ssPtr->log2litLengthSum - ZSTD_highbit32(ssPtr->litLengthFreq[0] + 1); | |
110 | ||
111 | /* literals */ | |
112 | if (ssPtr->cachedLiterals == literals) { | |
113 | U32 const additional = litLength - ssPtr->cachedLitLength; | |
114 | const BYTE *literals2 = ssPtr->cachedLiterals + ssPtr->cachedLitLength; | |
115 | price = ssPtr->cachedPrice + additional * ssPtr->log2litSum; | |
116 | for (u = 0; u < additional; u++) | |
117 | price -= ZSTD_highbit32(ssPtr->litFreq[literals2[u]] + 1); | |
118 | ssPtr->cachedPrice = price; | |
119 | ssPtr->cachedLitLength = litLength; | |
120 | } else { | |
121 | price = litLength * ssPtr->log2litSum; | |
122 | for (u = 0; u < litLength; u++) | |
123 | price -= ZSTD_highbit32(ssPtr->litFreq[literals[u]] + 1); | |
124 | ||
125 | if (litLength >= 12) { | |
126 | ssPtr->cachedLiterals = literals; | |
127 | ssPtr->cachedPrice = price; | |
128 | ssPtr->cachedLitLength = litLength; | |
129 | } | |
130 | } | |
131 | ||
132 | /* literal Length */ | |
133 | { | |
134 | const BYTE LL_deltaCode = 19; | |
135 | const BYTE llCode = (litLength > 63) ? (BYTE)ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength]; | |
136 | price += LL_bits[llCode] + ssPtr->log2litLengthSum - ZSTD_highbit32(ssPtr->litLengthFreq[llCode] + 1); | |
137 | } | |
138 | ||
139 | return price; | |
140 | } | |
141 | ||
142 | FORCE_INLINE U32 ZSTD_getPrice(seqStore_t *seqStorePtr, U32 litLength, const BYTE *literals, U32 offset, U32 matchLength, const int ultra) | |
143 | { | |
144 | /* offset */ | |
145 | U32 price; | |
146 | BYTE const offCode = (BYTE)ZSTD_highbit32(offset + 1); | |
147 | ||
148 | if (seqStorePtr->staticPrices) | |
149 | return ZSTD_getLiteralPrice(seqStorePtr, litLength, literals) + ZSTD_highbit32((U32)matchLength + 1) + 16 + offCode; | |
150 | ||
151 | price = offCode + seqStorePtr->log2offCodeSum - ZSTD_highbit32(seqStorePtr->offCodeFreq[offCode] + 1); | |
152 | if (!ultra && offCode >= 20) | |
153 | price += (offCode - 19) * 2; | |
154 | ||
155 | /* match Length */ | |
156 | { | |
157 | const BYTE ML_deltaCode = 36; | |
158 | const BYTE mlCode = (matchLength > 127) ? (BYTE)ZSTD_highbit32(matchLength) + ML_deltaCode : ML_Code[matchLength]; | |
159 | price += ML_bits[mlCode] + seqStorePtr->log2matchLengthSum - ZSTD_highbit32(seqStorePtr->matchLengthFreq[mlCode] + 1); | |
160 | } | |
161 | ||
162 | return price + ZSTD_getLiteralPrice(seqStorePtr, litLength, literals) + seqStorePtr->factor; | |
163 | } | |
164 | ||
165 | ZSTD_STATIC void ZSTD_updatePrice(seqStore_t *seqStorePtr, U32 litLength, const BYTE *literals, U32 offset, U32 matchLength) | |
166 | { | |
167 | U32 u; | |
168 | ||
169 | /* literals */ | |
170 | seqStorePtr->litSum += litLength * ZSTD_LITFREQ_ADD; | |
171 | for (u = 0; u < litLength; u++) | |
172 | seqStorePtr->litFreq[literals[u]] += ZSTD_LITFREQ_ADD; | |
173 | ||
174 | /* literal Length */ | |
175 | { | |
176 | const BYTE LL_deltaCode = 19; | |
177 | const BYTE llCode = (litLength > 63) ? (BYTE)ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength]; | |
178 | seqStorePtr->litLengthFreq[llCode]++; | |
179 | seqStorePtr->litLengthSum++; | |
180 | } | |
181 | ||
182 | /* match offset */ | |
183 | { | |
184 | BYTE const offCode = (BYTE)ZSTD_highbit32(offset + 1); | |
185 | seqStorePtr->offCodeSum++; | |
186 | seqStorePtr->offCodeFreq[offCode]++; | |
187 | } | |
188 | ||
189 | /* match Length */ | |
190 | { | |
191 | const BYTE ML_deltaCode = 36; | |
192 | const BYTE mlCode = (matchLength > 127) ? (BYTE)ZSTD_highbit32(matchLength) + ML_deltaCode : ML_Code[matchLength]; | |
193 | seqStorePtr->matchLengthFreq[mlCode]++; | |
194 | seqStorePtr->matchLengthSum++; | |
195 | } | |
196 | ||
197 | ZSTD_setLog2Prices(seqStorePtr); | |
198 | } | |
199 | ||
200 | #define SET_PRICE(pos, mlen_, offset_, litlen_, price_) \ | |
201 | { \ | |
202 | while (last_pos < pos) { \ | |
203 | opt[last_pos + 1].price = ZSTD_MAX_PRICE; \ | |
204 | last_pos++; \ | |
205 | } \ | |
206 | opt[pos].mlen = mlen_; \ | |
207 | opt[pos].off = offset_; \ | |
208 | opt[pos].litlen = litlen_; \ | |
209 | opt[pos].price = price_; \ | |
210 | } | |
211 | ||
212 | /* Update hashTable3 up to ip (excluded) | |
213 | Assumption : always within prefix (i.e. not within extDict) */ | |
214 | FORCE_INLINE | |
215 | U32 ZSTD_insertAndFindFirstIndexHash3(ZSTD_CCtx *zc, const BYTE *ip) | |
216 | { | |
217 | U32 *const hashTable3 = zc->hashTable3; | |
218 | U32 const hashLog3 = zc->hashLog3; | |
219 | const BYTE *const base = zc->base; | |
220 | U32 idx = zc->nextToUpdate3; | |
221 | const U32 target = zc->nextToUpdate3 = (U32)(ip - base); | |
222 | const size_t hash3 = ZSTD_hash3Ptr(ip, hashLog3); | |
223 | ||
224 | while (idx < target) { | |
225 | hashTable3[ZSTD_hash3Ptr(base + idx, hashLog3)] = idx; | |
226 | idx++; | |
227 | } | |
228 | ||
229 | return hashTable3[hash3]; | |
230 | } | |
231 | ||
232 | /*-************************************* | |
233 | * Binary Tree search | |
234 | ***************************************/ | |
235 | static U32 ZSTD_insertBtAndGetAllMatches(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iLimit, U32 nbCompares, const U32 mls, U32 extDict, | |
236 | ZSTD_match_t *matches, const U32 minMatchLen) | |
237 | { | |
238 | const BYTE *const base = zc->base; | |
239 | const U32 curr = (U32)(ip - base); | |
240 | const U32 hashLog = zc->params.cParams.hashLog; | |
241 | const size_t h = ZSTD_hashPtr(ip, hashLog, mls); | |
242 | U32 *const hashTable = zc->hashTable; | |
243 | U32 matchIndex = hashTable[h]; | |
244 | U32 *const bt = zc->chainTable; | |
245 | const U32 btLog = zc->params.cParams.chainLog - 1; | |
246 | const U32 btMask = (1U << btLog) - 1; | |
247 | size_t commonLengthSmaller = 0, commonLengthLarger = 0; | |
248 | const BYTE *const dictBase = zc->dictBase; | |
249 | const U32 dictLimit = zc->dictLimit; | |
250 | const BYTE *const dictEnd = dictBase + dictLimit; | |
251 | const BYTE *const prefixStart = base + dictLimit; | |
252 | const U32 btLow = btMask >= curr ? 0 : curr - btMask; | |
253 | const U32 windowLow = zc->lowLimit; | |
254 | U32 *smallerPtr = bt + 2 * (curr & btMask); | |
255 | U32 *largerPtr = bt + 2 * (curr & btMask) + 1; | |
256 | U32 matchEndIdx = curr + 8; | |
257 | U32 dummy32; /* to be nullified at the end */ | |
258 | U32 mnum = 0; | |
259 | ||
260 | const U32 minMatch = (mls == 3) ? 3 : 4; | |
261 | size_t bestLength = minMatchLen - 1; | |
262 | ||
263 | if (minMatch == 3) { /* HC3 match finder */ | |
264 | U32 const matchIndex3 = ZSTD_insertAndFindFirstIndexHash3(zc, ip); | |
265 | if (matchIndex3 > windowLow && (curr - matchIndex3 < (1 << 18))) { | |
266 | const BYTE *match; | |
267 | size_t currMl = 0; | |
268 | if ((!extDict) || matchIndex3 >= dictLimit) { | |
269 | match = base + matchIndex3; | |
270 | if (match[bestLength] == ip[bestLength]) | |
271 | currMl = ZSTD_count(ip, match, iLimit); | |
272 | } else { | |
273 | match = dictBase + matchIndex3; | |
274 | if (ZSTD_readMINMATCH(match, MINMATCH) == | |
275 | ZSTD_readMINMATCH(ip, MINMATCH)) /* assumption : matchIndex3 <= dictLimit-4 (by table construction) */ | |
276 | currMl = ZSTD_count_2segments(ip + MINMATCH, match + MINMATCH, iLimit, dictEnd, prefixStart) + MINMATCH; | |
277 | } | |
278 | ||
279 | /* save best solution */ | |
280 | if (currMl > bestLength) { | |
281 | bestLength = currMl; | |
282 | matches[mnum].off = ZSTD_REP_MOVE_OPT + curr - matchIndex3; | |
283 | matches[mnum].len = (U32)currMl; | |
284 | mnum++; | |
285 | if (currMl > ZSTD_OPT_NUM) | |
286 | goto update; | |
287 | if (ip + currMl == iLimit) | |
288 | goto update; /* best possible, and avoid read overflow*/ | |
289 | } | |
290 | } | |
291 | } | |
292 | ||
293 | hashTable[h] = curr; /* Update Hash Table */ | |
294 | ||
295 | while (nbCompares-- && (matchIndex > windowLow)) { | |
296 | U32 *nextPtr = bt + 2 * (matchIndex & btMask); | |
297 | size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ | |
298 | const BYTE *match; | |
299 | ||
300 | if ((!extDict) || (matchIndex + matchLength >= dictLimit)) { | |
301 | match = base + matchIndex; | |
302 | if (match[matchLength] == ip[matchLength]) { | |
303 | matchLength += ZSTD_count(ip + matchLength + 1, match + matchLength + 1, iLimit) + 1; | |
304 | } | |
305 | } else { | |
306 | match = dictBase + matchIndex; | |
307 | matchLength += ZSTD_count_2segments(ip + matchLength, match + matchLength, iLimit, dictEnd, prefixStart); | |
308 | if (matchIndex + matchLength >= dictLimit) | |
309 | match = base + matchIndex; /* to prepare for next usage of match[matchLength] */ | |
310 | } | |
311 | ||
312 | if (matchLength > bestLength) { | |
313 | if (matchLength > matchEndIdx - matchIndex) | |
314 | matchEndIdx = matchIndex + (U32)matchLength; | |
315 | bestLength = matchLength; | |
316 | matches[mnum].off = ZSTD_REP_MOVE_OPT + curr - matchIndex; | |
317 | matches[mnum].len = (U32)matchLength; | |
318 | mnum++; | |
319 | if (matchLength > ZSTD_OPT_NUM) | |
320 | break; | |
321 | if (ip + matchLength == iLimit) /* equal : no way to know if inf or sup */ | |
322 | break; /* drop, to guarantee consistency (miss a little bit of compression) */ | |
323 | } | |
324 | ||
325 | if (match[matchLength] < ip[matchLength]) { | |
326 | /* match is smaller than curr */ | |
327 | *smallerPtr = matchIndex; /* update smaller idx */ | |
328 | commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */ | |
329 | if (matchIndex <= btLow) { | |
330 | smallerPtr = &dummy32; | |
331 | break; | |
332 | } /* beyond tree size, stop the search */ | |
333 | smallerPtr = nextPtr + 1; /* new "smaller" => larger of match */ | |
334 | matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to curr) */ | |
335 | } else { | |
336 | /* match is larger than curr */ | |
337 | *largerPtr = matchIndex; | |
338 | commonLengthLarger = matchLength; | |
339 | if (matchIndex <= btLow) { | |
340 | largerPtr = &dummy32; | |
341 | break; | |
342 | } /* beyond tree size, stop the search */ | |
343 | largerPtr = nextPtr; | |
344 | matchIndex = nextPtr[0]; | |
345 | } | |
346 | } | |
347 | ||
348 | *smallerPtr = *largerPtr = 0; | |
349 | ||
350 | update: | |
351 | zc->nextToUpdate = (matchEndIdx > curr + 8) ? matchEndIdx - 8 : curr + 1; | |
352 | return mnum; | |
353 | } | |
354 | ||
355 | /** Tree updater, providing best match */ | |
356 | 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, | |
357 | const U32 minMatchLen) | |
358 | { | |
359 | if (ip < zc->base + zc->nextToUpdate) | |
360 | return 0; /* skipped area */ | |
361 | ZSTD_updateTree(zc, ip, iLimit, maxNbAttempts, mls); | |
362 | return ZSTD_insertBtAndGetAllMatches(zc, ip, iLimit, maxNbAttempts, mls, 0, matches, minMatchLen); | |
363 | } | |
364 | ||
365 | static U32 ZSTD_BtGetAllMatches_selectMLS(ZSTD_CCtx *zc, /* Index table will be updated */ | |
366 | const BYTE *ip, const BYTE *const iHighLimit, const U32 maxNbAttempts, const U32 matchLengthSearch, | |
367 | ZSTD_match_t *matches, const U32 minMatchLen) | |
368 | { | |
369 | switch (matchLengthSearch) { | |
370 | case 3: return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 3, matches, minMatchLen); | |
371 | default: | |
372 | case 4: return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 4, matches, minMatchLen); | |
373 | case 5: return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 5, matches, minMatchLen); | |
374 | case 7: | |
375 | case 6: return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 6, matches, minMatchLen); | |
376 | } | |
377 | } | |
378 | ||
379 | /** Tree updater, providing best match */ | |
380 | static U32 ZSTD_BtGetAllMatches_extDict(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iLimit, const U32 maxNbAttempts, const U32 mls, | |
381 | ZSTD_match_t *matches, const U32 minMatchLen) | |
382 | { | |
383 | if (ip < zc->base + zc->nextToUpdate) | |
384 | return 0; /* skipped area */ | |
385 | ZSTD_updateTree_extDict(zc, ip, iLimit, maxNbAttempts, mls); | |
386 | return ZSTD_insertBtAndGetAllMatches(zc, ip, iLimit, maxNbAttempts, mls, 1, matches, minMatchLen); | |
387 | } | |
388 | ||
389 | static U32 ZSTD_BtGetAllMatches_selectMLS_extDict(ZSTD_CCtx *zc, /* Index table will be updated */ | |
390 | const BYTE *ip, const BYTE *const iHighLimit, const U32 maxNbAttempts, const U32 matchLengthSearch, | |
391 | ZSTD_match_t *matches, const U32 minMatchLen) | |
392 | { | |
393 | switch (matchLengthSearch) { | |
394 | case 3: return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 3, matches, minMatchLen); | |
395 | default: | |
396 | case 4: return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 4, matches, minMatchLen); | |
397 | case 5: return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 5, matches, minMatchLen); | |
398 | case 7: | |
399 | case 6: return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 6, matches, minMatchLen); | |
400 | } | |
401 | } | |
402 | ||
403 | /*-******************************* | |
404 | * Optimal parser | |
405 | *********************************/ | |
406 | FORCE_INLINE | |
407 | void ZSTD_compressBlock_opt_generic(ZSTD_CCtx *ctx, const void *src, size_t srcSize, const int ultra) | |
408 | { | |
409 | seqStore_t *seqStorePtr = &(ctx->seqStore); | |
410 | const BYTE *const istart = (const BYTE *)src; | |
411 | const BYTE *ip = istart; | |
412 | const BYTE *anchor = istart; | |
413 | const BYTE *const iend = istart + srcSize; | |
414 | const BYTE *const ilimit = iend - 8; | |
415 | const BYTE *const base = ctx->base; | |
416 | const BYTE *const prefixStart = base + ctx->dictLimit; | |
417 | ||
418 | const U32 maxSearches = 1U << ctx->params.cParams.searchLog; | |
419 | const U32 sufficient_len = ctx->params.cParams.targetLength; | |
420 | const U32 mls = ctx->params.cParams.searchLength; | |
421 | const U32 minMatch = (ctx->params.cParams.searchLength == 3) ? 3 : 4; | |
422 | ||
423 | ZSTD_optimal_t *opt = seqStorePtr->priceTable; | |
424 | ZSTD_match_t *matches = seqStorePtr->matchTable; | |
425 | const BYTE *inr; | |
426 | U32 offset, rep[ZSTD_REP_NUM]; | |
427 | ||
428 | /* init */ | |
429 | ctx->nextToUpdate3 = ctx->nextToUpdate; | |
430 | ZSTD_rescaleFreqs(seqStorePtr, (const BYTE *)src, srcSize); | |
431 | ip += (ip == prefixStart); | |
432 | { | |
433 | U32 i; | |
434 | for (i = 0; i < ZSTD_REP_NUM; i++) | |
435 | rep[i] = ctx->rep[i]; | |
436 | } | |
437 | ||
438 | /* Match Loop */ | |
439 | while (ip < ilimit) { | |
440 | U32 cur, match_num, last_pos, litlen, price; | |
441 | U32 u, mlen, best_mlen, best_off, litLength; | |
442 | memset(opt, 0, sizeof(ZSTD_optimal_t)); | |
443 | last_pos = 0; | |
444 | litlen = (U32)(ip - anchor); | |
445 | ||
446 | /* check repCode */ | |
447 | { | |
448 | U32 i, last_i = ZSTD_REP_CHECK + (ip == anchor); | |
449 | for (i = (ip == anchor); i < last_i; i++) { | |
450 | const S32 repCur = (i == ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : rep[i]; | |
451 | if ((repCur > 0) && (repCur < (S32)(ip - prefixStart)) && | |
452 | (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(ip - repCur, minMatch))) { | |
453 | mlen = (U32)ZSTD_count(ip + minMatch, ip + minMatch - repCur, iend) + minMatch; | |
454 | if (mlen > sufficient_len || mlen >= ZSTD_OPT_NUM) { | |
455 | best_mlen = mlen; | |
456 | best_off = i; | |
457 | cur = 0; | |
458 | last_pos = 1; | |
459 | goto _storeSequence; | |
460 | } | |
461 | best_off = i - (ip == anchor); | |
462 | do { | |
463 | price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra); | |
464 | if (mlen > last_pos || price < opt[mlen].price) | |
465 | SET_PRICE(mlen, mlen, i, litlen, price); /* note : macro modifies last_pos */ | |
466 | mlen--; | |
467 | } while (mlen >= minMatch); | |
468 | } | |
469 | } | |
470 | } | |
471 | ||
472 | match_num = ZSTD_BtGetAllMatches_selectMLS(ctx, ip, iend, maxSearches, mls, matches, minMatch); | |
473 | ||
474 | if (!last_pos && !match_num) { | |
475 | ip++; | |
476 | continue; | |
477 | } | |
478 | ||
479 | if (match_num && (matches[match_num - 1].len > sufficient_len || matches[match_num - 1].len >= ZSTD_OPT_NUM)) { | |
480 | best_mlen = matches[match_num - 1].len; | |
481 | best_off = matches[match_num - 1].off; | |
482 | cur = 0; | |
483 | last_pos = 1; | |
484 | goto _storeSequence; | |
485 | } | |
486 | ||
487 | /* set prices using matches at position = 0 */ | |
488 | best_mlen = (last_pos) ? last_pos : minMatch; | |
489 | for (u = 0; u < match_num; u++) { | |
490 | mlen = (u > 0) ? matches[u - 1].len + 1 : best_mlen; | |
491 | best_mlen = matches[u].len; | |
492 | while (mlen <= best_mlen) { | |
493 | price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off - 1, mlen - MINMATCH, ultra); | |
494 | if (mlen > last_pos || price < opt[mlen].price) | |
495 | SET_PRICE(mlen, mlen, matches[u].off, litlen, price); /* note : macro modifies last_pos */ | |
496 | mlen++; | |
497 | } | |
498 | } | |
499 | ||
500 | if (last_pos < minMatch) { | |
501 | ip++; | |
502 | continue; | |
503 | } | |
504 | ||
505 | /* initialize opt[0] */ | |
506 | { | |
507 | U32 i; | |
508 | for (i = 0; i < ZSTD_REP_NUM; i++) | |
509 | opt[0].rep[i] = rep[i]; | |
510 | } | |
511 | opt[0].mlen = 1; | |
512 | opt[0].litlen = litlen; | |
513 | ||
514 | /* check further positions */ | |
515 | for (cur = 1; cur <= last_pos; cur++) { | |
516 | inr = ip + cur; | |
517 | ||
518 | if (opt[cur - 1].mlen == 1) { | |
519 | litlen = opt[cur - 1].litlen + 1; | |
520 | if (cur > litlen) { | |
521 | price = opt[cur - litlen].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr - litlen); | |
522 | } else | |
523 | price = ZSTD_getLiteralPrice(seqStorePtr, litlen, anchor); | |
524 | } else { | |
525 | litlen = 1; | |
526 | price = opt[cur - 1].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr - 1); | |
527 | } | |
528 | ||
529 | if (cur > last_pos || price <= opt[cur].price) | |
530 | SET_PRICE(cur, 1, 0, litlen, price); | |
531 | ||
532 | if (cur == last_pos) | |
533 | break; | |
534 | ||
535 | if (inr > ilimit) /* last match must start at a minimum distance of 8 from oend */ | |
536 | continue; | |
537 | ||
538 | mlen = opt[cur].mlen; | |
539 | if (opt[cur].off > ZSTD_REP_MOVE_OPT) { | |
540 | opt[cur].rep[2] = opt[cur - mlen].rep[1]; | |
541 | opt[cur].rep[1] = opt[cur - mlen].rep[0]; | |
542 | opt[cur].rep[0] = opt[cur].off - ZSTD_REP_MOVE_OPT; | |
543 | } else { | |
544 | opt[cur].rep[2] = (opt[cur].off > 1) ? opt[cur - mlen].rep[1] : opt[cur - mlen].rep[2]; | |
545 | opt[cur].rep[1] = (opt[cur].off > 0) ? opt[cur - mlen].rep[0] : opt[cur - mlen].rep[1]; | |
546 | opt[cur].rep[0] = | |
547 | ((opt[cur].off == ZSTD_REP_MOVE_OPT) && (mlen != 1)) ? (opt[cur - mlen].rep[0] - 1) : (opt[cur - mlen].rep[opt[cur].off]); | |
548 | } | |
549 | ||
550 | best_mlen = minMatch; | |
551 | { | |
552 | U32 i, last_i = ZSTD_REP_CHECK + (mlen != 1); | |
553 | for (i = (opt[cur].mlen != 1); i < last_i; i++) { /* check rep */ | |
554 | const S32 repCur = (i == ZSTD_REP_MOVE_OPT) ? (opt[cur].rep[0] - 1) : opt[cur].rep[i]; | |
555 | if ((repCur > 0) && (repCur < (S32)(inr - prefixStart)) && | |
556 | (ZSTD_readMINMATCH(inr, minMatch) == ZSTD_readMINMATCH(inr - repCur, minMatch))) { | |
557 | mlen = (U32)ZSTD_count(inr + minMatch, inr + minMatch - repCur, iend) + minMatch; | |
558 | ||
559 | if (mlen > sufficient_len || cur + mlen >= ZSTD_OPT_NUM) { | |
560 | best_mlen = mlen; | |
561 | best_off = i; | |
562 | last_pos = cur + 1; | |
563 | goto _storeSequence; | |
564 | } | |
565 | ||
566 | best_off = i - (opt[cur].mlen != 1); | |
567 | if (mlen > best_mlen) | |
568 | best_mlen = mlen; | |
569 | ||
570 | do { | |
571 | if (opt[cur].mlen == 1) { | |
572 | litlen = opt[cur].litlen; | |
573 | if (cur > litlen) { | |
574 | price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, inr - litlen, | |
575 | best_off, mlen - MINMATCH, ultra); | |
576 | } else | |
577 | price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra); | |
578 | } else { | |
579 | litlen = 0; | |
580 | price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, best_off, mlen - MINMATCH, ultra); | |
581 | } | |
582 | ||
583 | if (cur + mlen > last_pos || price <= opt[cur + mlen].price) | |
584 | SET_PRICE(cur + mlen, mlen, i, litlen, price); | |
585 | mlen--; | |
586 | } while (mlen >= minMatch); | |
587 | } | |
588 | } | |
589 | } | |
590 | ||
591 | match_num = ZSTD_BtGetAllMatches_selectMLS(ctx, inr, iend, maxSearches, mls, matches, best_mlen); | |
592 | ||
593 | if (match_num > 0 && (matches[match_num - 1].len > sufficient_len || cur + matches[match_num - 1].len >= ZSTD_OPT_NUM)) { | |
594 | best_mlen = matches[match_num - 1].len; | |
595 | best_off = matches[match_num - 1].off; | |
596 | last_pos = cur + 1; | |
597 | goto _storeSequence; | |
598 | } | |
599 | ||
600 | /* set prices using matches at position = cur */ | |
601 | for (u = 0; u < match_num; u++) { | |
602 | mlen = (u > 0) ? matches[u - 1].len + 1 : best_mlen; | |
603 | best_mlen = matches[u].len; | |
604 | ||
605 | while (mlen <= best_mlen) { | |
606 | if (opt[cur].mlen == 1) { | |
607 | litlen = opt[cur].litlen; | |
608 | if (cur > litlen) | |
609 | price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, ip + cur - litlen, | |
610 | matches[u].off - 1, mlen - MINMATCH, ultra); | |
611 | else | |
612 | price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off - 1, mlen - MINMATCH, ultra); | |
613 | } else { | |
614 | litlen = 0; | |
615 | price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, matches[u].off - 1, mlen - MINMATCH, ultra); | |
616 | } | |
617 | ||
618 | if (cur + mlen > last_pos || (price < opt[cur + mlen].price)) | |
619 | SET_PRICE(cur + mlen, mlen, matches[u].off, litlen, price); | |
620 | ||
621 | mlen++; | |
622 | } | |
623 | } | |
624 | } | |
625 | ||
626 | best_mlen = opt[last_pos].mlen; | |
627 | best_off = opt[last_pos].off; | |
628 | cur = last_pos - best_mlen; | |
629 | ||
630 | /* store sequence */ | |
631 | _storeSequence: /* cur, last_pos, best_mlen, best_off have to be set */ | |
632 | opt[0].mlen = 1; | |
633 | ||
634 | while (1) { | |
635 | mlen = opt[cur].mlen; | |
636 | offset = opt[cur].off; | |
637 | opt[cur].mlen = best_mlen; | |
638 | opt[cur].off = best_off; | |
639 | best_mlen = mlen; | |
640 | best_off = offset; | |
641 | if (mlen > cur) | |
642 | break; | |
643 | cur -= mlen; | |
644 | } | |
645 | ||
646 | for (u = 0; u <= last_pos;) { | |
647 | u += opt[u].mlen; | |
648 | } | |
649 | ||
650 | for (cur = 0; cur < last_pos;) { | |
651 | mlen = opt[cur].mlen; | |
652 | if (mlen == 1) { | |
653 | ip++; | |
654 | cur++; | |
655 | continue; | |
656 | } | |
657 | offset = opt[cur].off; | |
658 | cur += mlen; | |
659 | litLength = (U32)(ip - anchor); | |
660 | ||
661 | if (offset > ZSTD_REP_MOVE_OPT) { | |
662 | rep[2] = rep[1]; | |
663 | rep[1] = rep[0]; | |
664 | rep[0] = offset - ZSTD_REP_MOVE_OPT; | |
665 | offset--; | |
666 | } else { | |
667 | if (offset != 0) { | |
668 | best_off = (offset == ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : (rep[offset]); | |
669 | if (offset != 1) | |
670 | rep[2] = rep[1]; | |
671 | rep[1] = rep[0]; | |
672 | rep[0] = best_off; | |
673 | } | |
674 | if (litLength == 0) | |
675 | offset--; | |
676 | } | |
677 | ||
678 | ZSTD_updatePrice(seqStorePtr, litLength, anchor, offset, mlen - MINMATCH); | |
679 | ZSTD_storeSeq(seqStorePtr, litLength, anchor, offset, mlen - MINMATCH); | |
680 | anchor = ip = ip + mlen; | |
681 | } | |
682 | } /* for (cur=0; cur < last_pos; ) */ | |
683 | ||
684 | /* Save reps for next block */ | |
685 | { | |
686 | int i; | |
687 | for (i = 0; i < ZSTD_REP_NUM; i++) | |
688 | ctx->repToConfirm[i] = rep[i]; | |
689 | } | |
690 | ||
691 | /* Last Literals */ | |
692 | { | |
693 | size_t const lastLLSize = iend - anchor; | |
694 | memcpy(seqStorePtr->lit, anchor, lastLLSize); | |
695 | seqStorePtr->lit += lastLLSize; | |
696 | } | |
697 | } | |
698 | ||
699 | FORCE_INLINE | |
700 | void ZSTD_compressBlock_opt_extDict_generic(ZSTD_CCtx *ctx, const void *src, size_t srcSize, const int ultra) | |
701 | { | |
702 | seqStore_t *seqStorePtr = &(ctx->seqStore); | |
703 | const BYTE *const istart = (const BYTE *)src; | |
704 | const BYTE *ip = istart; | |
705 | const BYTE *anchor = istart; | |
706 | const BYTE *const iend = istart + srcSize; | |
707 | const BYTE *const ilimit = iend - 8; | |
708 | const BYTE *const base = ctx->base; | |
709 | const U32 lowestIndex = ctx->lowLimit; | |
710 | const U32 dictLimit = ctx->dictLimit; | |
711 | const BYTE *const prefixStart = base + dictLimit; | |
712 | const BYTE *const dictBase = ctx->dictBase; | |
713 | const BYTE *const dictEnd = dictBase + dictLimit; | |
714 | ||
715 | const U32 maxSearches = 1U << ctx->params.cParams.searchLog; | |
716 | const U32 sufficient_len = ctx->params.cParams.targetLength; | |
717 | const U32 mls = ctx->params.cParams.searchLength; | |
718 | const U32 minMatch = (ctx->params.cParams.searchLength == 3) ? 3 : 4; | |
719 | ||
720 | ZSTD_optimal_t *opt = seqStorePtr->priceTable; | |
721 | ZSTD_match_t *matches = seqStorePtr->matchTable; | |
722 | const BYTE *inr; | |
723 | ||
724 | /* init */ | |
725 | U32 offset, rep[ZSTD_REP_NUM]; | |
726 | { | |
727 | U32 i; | |
728 | for (i = 0; i < ZSTD_REP_NUM; i++) | |
729 | rep[i] = ctx->rep[i]; | |
730 | } | |
731 | ||
732 | ctx->nextToUpdate3 = ctx->nextToUpdate; | |
733 | ZSTD_rescaleFreqs(seqStorePtr, (const BYTE *)src, srcSize); | |
734 | ip += (ip == prefixStart); | |
735 | ||
736 | /* Match Loop */ | |
737 | while (ip < ilimit) { | |
738 | U32 cur, match_num, last_pos, litlen, price; | |
739 | U32 u, mlen, best_mlen, best_off, litLength; | |
740 | U32 curr = (U32)(ip - base); | |
741 | memset(opt, 0, sizeof(ZSTD_optimal_t)); | |
742 | last_pos = 0; | |
743 | opt[0].litlen = (U32)(ip - anchor); | |
744 | ||
745 | /* check repCode */ | |
746 | { | |
747 | U32 i, last_i = ZSTD_REP_CHECK + (ip == anchor); | |
748 | for (i = (ip == anchor); i < last_i; i++) { | |
749 | const S32 repCur = (i == ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : rep[i]; | |
750 | const U32 repIndex = (U32)(curr - repCur); | |
751 | const BYTE *const repBase = repIndex < dictLimit ? dictBase : base; | |
752 | const BYTE *const repMatch = repBase + repIndex; | |
753 | if ((repCur > 0 && repCur <= (S32)curr) && | |
754 | (((U32)((dictLimit - 1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */ | |
755 | && (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(repMatch, minMatch))) { | |
756 | /* repcode detected we should take it */ | |
757 | const BYTE *const repEnd = repIndex < dictLimit ? dictEnd : iend; | |
758 | mlen = (U32)ZSTD_count_2segments(ip + minMatch, repMatch + minMatch, iend, repEnd, prefixStart) + minMatch; | |
759 | ||
760 | if (mlen > sufficient_len || mlen >= ZSTD_OPT_NUM) { | |
761 | best_mlen = mlen; | |
762 | best_off = i; | |
763 | cur = 0; | |
764 | last_pos = 1; | |
765 | goto _storeSequence; | |
766 | } | |
767 | ||
768 | best_off = i - (ip == anchor); | |
769 | litlen = opt[0].litlen; | |
770 | do { | |
771 | price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra); | |
772 | if (mlen > last_pos || price < opt[mlen].price) | |
773 | SET_PRICE(mlen, mlen, i, litlen, price); /* note : macro modifies last_pos */ | |
774 | mlen--; | |
775 | } while (mlen >= minMatch); | |
776 | } | |
777 | } | |
778 | } | |
779 | ||
780 | match_num = ZSTD_BtGetAllMatches_selectMLS_extDict(ctx, ip, iend, maxSearches, mls, matches, minMatch); /* first search (depth 0) */ | |
781 | ||
782 | if (!last_pos && !match_num) { | |
783 | ip++; | |
784 | continue; | |
785 | } | |
786 | ||
787 | { | |
788 | U32 i; | |
789 | for (i = 0; i < ZSTD_REP_NUM; i++) | |
790 | opt[0].rep[i] = rep[i]; | |
791 | } | |
792 | opt[0].mlen = 1; | |
793 | ||
794 | if (match_num && (matches[match_num - 1].len > sufficient_len || matches[match_num - 1].len >= ZSTD_OPT_NUM)) { | |
795 | best_mlen = matches[match_num - 1].len; | |
796 | best_off = matches[match_num - 1].off; | |
797 | cur = 0; | |
798 | last_pos = 1; | |
799 | goto _storeSequence; | |
800 | } | |
801 | ||
802 | best_mlen = (last_pos) ? last_pos : minMatch; | |
803 | ||
804 | /* set prices using matches at position = 0 */ | |
805 | for (u = 0; u < match_num; u++) { | |
806 | mlen = (u > 0) ? matches[u - 1].len + 1 : best_mlen; | |
807 | best_mlen = matches[u].len; | |
808 | litlen = opt[0].litlen; | |
809 | while (mlen <= best_mlen) { | |
810 | price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off - 1, mlen - MINMATCH, ultra); | |
811 | if (mlen > last_pos || price < opt[mlen].price) | |
812 | SET_PRICE(mlen, mlen, matches[u].off, litlen, price); | |
813 | mlen++; | |
814 | } | |
815 | } | |
816 | ||
817 | if (last_pos < minMatch) { | |
818 | ip++; | |
819 | continue; | |
820 | } | |
821 | ||
822 | /* check further positions */ | |
823 | for (cur = 1; cur <= last_pos; cur++) { | |
824 | inr = ip + cur; | |
825 | ||
826 | if (opt[cur - 1].mlen == 1) { | |
827 | litlen = opt[cur - 1].litlen + 1; | |
828 | if (cur > litlen) { | |
829 | price = opt[cur - litlen].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr - litlen); | |
830 | } else | |
831 | price = ZSTD_getLiteralPrice(seqStorePtr, litlen, anchor); | |
832 | } else { | |
833 | litlen = 1; | |
834 | price = opt[cur - 1].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr - 1); | |
835 | } | |
836 | ||
837 | if (cur > last_pos || price <= opt[cur].price) | |
838 | SET_PRICE(cur, 1, 0, litlen, price); | |
839 | ||
840 | if (cur == last_pos) | |
841 | break; | |
842 | ||
843 | if (inr > ilimit) /* last match must start at a minimum distance of 8 from oend */ | |
844 | continue; | |
845 | ||
846 | mlen = opt[cur].mlen; | |
847 | if (opt[cur].off > ZSTD_REP_MOVE_OPT) { | |
848 | opt[cur].rep[2] = opt[cur - mlen].rep[1]; | |
849 | opt[cur].rep[1] = opt[cur - mlen].rep[0]; | |
850 | opt[cur].rep[0] = opt[cur].off - ZSTD_REP_MOVE_OPT; | |
851 | } else { | |
852 | opt[cur].rep[2] = (opt[cur].off > 1) ? opt[cur - mlen].rep[1] : opt[cur - mlen].rep[2]; | |
853 | opt[cur].rep[1] = (opt[cur].off > 0) ? opt[cur - mlen].rep[0] : opt[cur - mlen].rep[1]; | |
854 | opt[cur].rep[0] = | |
855 | ((opt[cur].off == ZSTD_REP_MOVE_OPT) && (mlen != 1)) ? (opt[cur - mlen].rep[0] - 1) : (opt[cur - mlen].rep[opt[cur].off]); | |
856 | } | |
857 | ||
858 | best_mlen = minMatch; | |
859 | { | |
860 | U32 i, last_i = ZSTD_REP_CHECK + (mlen != 1); | |
861 | for (i = (mlen != 1); i < last_i; i++) { | |
862 | const S32 repCur = (i == ZSTD_REP_MOVE_OPT) ? (opt[cur].rep[0] - 1) : opt[cur].rep[i]; | |
863 | const U32 repIndex = (U32)(curr + cur - repCur); | |
864 | const BYTE *const repBase = repIndex < dictLimit ? dictBase : base; | |
865 | const BYTE *const repMatch = repBase + repIndex; | |
866 | if ((repCur > 0 && repCur <= (S32)(curr + cur)) && | |
867 | (((U32)((dictLimit - 1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */ | |
868 | && (ZSTD_readMINMATCH(inr, minMatch) == ZSTD_readMINMATCH(repMatch, minMatch))) { | |
869 | /* repcode detected */ | |
870 | const BYTE *const repEnd = repIndex < dictLimit ? dictEnd : iend; | |
871 | mlen = (U32)ZSTD_count_2segments(inr + minMatch, repMatch + minMatch, iend, repEnd, prefixStart) + minMatch; | |
872 | ||
873 | if (mlen > sufficient_len || cur + mlen >= ZSTD_OPT_NUM) { | |
874 | best_mlen = mlen; | |
875 | best_off = i; | |
876 | last_pos = cur + 1; | |
877 | goto _storeSequence; | |
878 | } | |
879 | ||
880 | best_off = i - (opt[cur].mlen != 1); | |
881 | if (mlen > best_mlen) | |
882 | best_mlen = mlen; | |
883 | ||
884 | do { | |
885 | if (opt[cur].mlen == 1) { | |
886 | litlen = opt[cur].litlen; | |
887 | if (cur > litlen) { | |
888 | price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, inr - litlen, | |
889 | best_off, mlen - MINMATCH, ultra); | |
890 | } else | |
891 | price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra); | |
892 | } else { | |
893 | litlen = 0; | |
894 | price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, best_off, mlen - MINMATCH, ultra); | |
895 | } | |
896 | ||
897 | if (cur + mlen > last_pos || price <= opt[cur + mlen].price) | |
898 | SET_PRICE(cur + mlen, mlen, i, litlen, price); | |
899 | mlen--; | |
900 | } while (mlen >= minMatch); | |
901 | } | |
902 | } | |
903 | } | |
904 | ||
905 | match_num = ZSTD_BtGetAllMatches_selectMLS_extDict(ctx, inr, iend, maxSearches, mls, matches, minMatch); | |
906 | ||
907 | if (match_num > 0 && (matches[match_num - 1].len > sufficient_len || cur + matches[match_num - 1].len >= ZSTD_OPT_NUM)) { | |
908 | best_mlen = matches[match_num - 1].len; | |
909 | best_off = matches[match_num - 1].off; | |
910 | last_pos = cur + 1; | |
911 | goto _storeSequence; | |
912 | } | |
913 | ||
914 | /* set prices using matches at position = cur */ | |
915 | for (u = 0; u < match_num; u++) { | |
916 | mlen = (u > 0) ? matches[u - 1].len + 1 : best_mlen; | |
917 | best_mlen = matches[u].len; | |
918 | ||
919 | while (mlen <= best_mlen) { | |
920 | if (opt[cur].mlen == 1) { | |
921 | litlen = opt[cur].litlen; | |
922 | if (cur > litlen) | |
923 | price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, ip + cur - litlen, | |
924 | matches[u].off - 1, mlen - MINMATCH, ultra); | |
925 | else | |
926 | price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off - 1, mlen - MINMATCH, ultra); | |
927 | } else { | |
928 | litlen = 0; | |
929 | price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, matches[u].off - 1, mlen - MINMATCH, ultra); | |
930 | } | |
931 | ||
932 | if (cur + mlen > last_pos || (price < opt[cur + mlen].price)) | |
933 | SET_PRICE(cur + mlen, mlen, matches[u].off, litlen, price); | |
934 | ||
935 | mlen++; | |
936 | } | |
937 | } | |
938 | } /* for (cur = 1; cur <= last_pos; cur++) */ | |
939 | ||
940 | best_mlen = opt[last_pos].mlen; | |
941 | best_off = opt[last_pos].off; | |
942 | cur = last_pos - best_mlen; | |
943 | ||
944 | /* store sequence */ | |
945 | _storeSequence: /* cur, last_pos, best_mlen, best_off have to be set */ | |
946 | opt[0].mlen = 1; | |
947 | ||
948 | while (1) { | |
949 | mlen = opt[cur].mlen; | |
950 | offset = opt[cur].off; | |
951 | opt[cur].mlen = best_mlen; | |
952 | opt[cur].off = best_off; | |
953 | best_mlen = mlen; | |
954 | best_off = offset; | |
955 | if (mlen > cur) | |
956 | break; | |
957 | cur -= mlen; | |
958 | } | |
959 | ||
960 | for (u = 0; u <= last_pos;) { | |
961 | u += opt[u].mlen; | |
962 | } | |
963 | ||
964 | for (cur = 0; cur < last_pos;) { | |
965 | mlen = opt[cur].mlen; | |
966 | if (mlen == 1) { | |
967 | ip++; | |
968 | cur++; | |
969 | continue; | |
970 | } | |
971 | offset = opt[cur].off; | |
972 | cur += mlen; | |
973 | litLength = (U32)(ip - anchor); | |
974 | ||
975 | if (offset > ZSTD_REP_MOVE_OPT) { | |
976 | rep[2] = rep[1]; | |
977 | rep[1] = rep[0]; | |
978 | rep[0] = offset - ZSTD_REP_MOVE_OPT; | |
979 | offset--; | |
980 | } else { | |
981 | if (offset != 0) { | |
982 | best_off = (offset == ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : (rep[offset]); | |
983 | if (offset != 1) | |
984 | rep[2] = rep[1]; | |
985 | rep[1] = rep[0]; | |
986 | rep[0] = best_off; | |
987 | } | |
988 | ||
989 | if (litLength == 0) | |
990 | offset--; | |
991 | } | |
992 | ||
993 | ZSTD_updatePrice(seqStorePtr, litLength, anchor, offset, mlen - MINMATCH); | |
994 | ZSTD_storeSeq(seqStorePtr, litLength, anchor, offset, mlen - MINMATCH); | |
995 | anchor = ip = ip + mlen; | |
996 | } | |
997 | } /* for (cur=0; cur < last_pos; ) */ | |
998 | ||
999 | /* Save reps for next block */ | |
1000 | { | |
1001 | int i; | |
1002 | for (i = 0; i < ZSTD_REP_NUM; i++) | |
1003 | ctx->repToConfirm[i] = rep[i]; | |
1004 | } | |
1005 | ||
1006 | /* Last Literals */ | |
1007 | { | |
1008 | size_t lastLLSize = iend - anchor; | |
1009 | memcpy(seqStorePtr->lit, anchor, lastLLSize); | |
1010 | seqStorePtr->lit += lastLLSize; | |
1011 | } | |
1012 | } | |
1013 | ||
1014 | #endif /* ZSTD_OPT_H_91842398743 */ |