source: thirdparty/blosc/internal-complibs/zstd-0.7.4/compress/zstd_opt.h @ 8ebc79b

Revision 8ebc79b, 50.3 KB checked in by Hal Finkel <hfinkel@…>, 8 years ago (diff)

Add the other internal compression libraries from blocs

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