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