1 #define LIZARD_LOG_PARSER(fmt, ...) //printf(fmt, __VA_ARGS__)
2 #define LIZARD_LOG_PRICE(fmt, ...) //printf(fmt, __VA_ARGS__)
3 #define LIZARD_LOG_ENCODE(fmt, ...) //printf(fmt, __VA_ARGS__)
4 
5 #define LIZARD_OPTIMAL_MIN_OFFSET  8
6 #define LIZARD_OPT_NUM             (1<<12)
7 #define REPMINMATCH             1
8 
9 
Lizard_get_price(Lizard_stream_t * const ctx,int rep,const BYTE * ip,const BYTE * off24pos,size_t litLength,U32 offset,size_t matchLength)10 FORCE_INLINE size_t Lizard_get_price(Lizard_stream_t* const ctx, int rep, const BYTE *ip, const BYTE *off24pos, size_t litLength, U32 offset, size_t matchLength)
11 {
12     if (ctx->params.decompressType == Lizard_coderwords_LZ4)
13         return Lizard_get_price_LZ4(ctx, ip, litLength, offset, matchLength);
14 
15     return Lizard_get_price_LIZv1(ctx, rep, ip, off24pos, litLength, offset, matchLength);
16 }
17 
18 
19 
20 typedef struct
21 {
22     int off;
23     int len;
24     int back;
25 } Lizard_match_t;
26 
27 typedef struct
28 {
29     int price;
30     int off;
31     int mlen;
32     int litlen;
33     int rep;
34     const BYTE* off24pos;
35 } Lizard_optimal_t;
36 
37 
38 /* Update chains up to ip (excluded) */
Lizard_BinTree_Insert(Lizard_stream_t * ctx,const BYTE * ip)39 FORCE_INLINE void Lizard_BinTree_Insert(Lizard_stream_t* ctx, const BYTE* ip)
40 {
41 #if MINMATCH == 3
42     U32* HashTable3  = ctx->hashTable3;
43     const BYTE* const base = ctx->base;
44     const U32 target = (U32)(ip - base);
45     U32 idx = ctx->nextToUpdate;
46 
47     while(idx < target) {
48         HashTable3[Lizard_hash3Ptr(base+idx, ctx->params.hashLog3)] = idx;
49         idx++;
50     }
51 
52     ctx->nextToUpdate = target;
53 #else
54     (void)ctx; (void)ip;
55 #endif
56 }
57 
58 
59 
Lizard_GetAllMatches(Lizard_stream_t * ctx,const BYTE * const ip,const BYTE * const iLowLimit,const BYTE * const iHighLimit,size_t best_mlen,Lizard_match_t * matches)60 FORCE_INLINE int Lizard_GetAllMatches (
61     Lizard_stream_t* ctx,
62     const BYTE* const ip,
63     const BYTE* const iLowLimit,
64     const BYTE* const iHighLimit,
65     size_t best_mlen,
66     Lizard_match_t* matches)
67 {
68     U32* const chainTable = ctx->chainTable;
69     U32* const HashTable = ctx->hashTable;
70     const BYTE* const base = ctx->base;
71     const BYTE* const dictBase = ctx->dictBase;
72     const intptr_t dictLimit = ctx->dictLimit;
73     const BYTE* const dictEnd = dictBase + dictLimit;
74     const BYTE* const lowPrefixPtr = base + dictLimit;
75     const intptr_t maxDistance = (1 << ctx->params.windowLog) - 1;
76     const intptr_t current = (ip - base);
77     const intptr_t lowLimit = ((intptr_t)ctx->lowLimit + maxDistance >= current) ? (intptr_t)ctx->lowLimit : current - maxDistance;
78     const U32 contentMask = (1 << ctx->params.contentLog) - 1;
79     const BYTE* match, *matchDict;
80     const size_t minMatchLongOff = ctx->params.minMatchLongOff;
81     intptr_t matchIndex;
82     int nbAttempts = ctx->params.searchNum;
83  //   bool fullSearch = (ctx->params.fullSearch >= 2);
84     int mnum = 0;
85     U32* HashPos;
86     size_t mlt;
87 
88     if (ip + MINMATCH > iHighLimit) return 0;
89 
90     /* First Match */
91     HashPos = &HashTable[Lizard_hashPtr(ip, ctx->params.hashLog, ctx->params.searchLength)];
92     matchIndex = *HashPos;
93 #if MINMATCH == 3
94     {
95     U32* const HashTable3 = ctx->hashTable3;
96     U32* HashPos3 = &HashTable3[Lizard_hash3Ptr(ip, ctx->params.hashLog3)];
97 
98     if ((*HashPos3 < current) && (*HashPos3 >= lowLimit)) {
99         size_t offset = current - *HashPos3;
100         if (offset < LIZARD_MAX_8BIT_OFFSET) {
101             match = ip - offset;
102             if (match > base && MEM_readMINMATCH(ip) == MEM_readMINMATCH(match)) {
103                 size_t mlt = Lizard_count(ip + MINMATCH, match + MINMATCH, iHighLimit) + MINMATCH;
104 
105                 int back = 0;
106                 while ((ip + back > iLowLimit) && (match + back > lowPrefixPtr) && (ip[back - 1] == match[back - 1])) back--;
107                 mlt -= back;
108 
109                 matches[mnum].off = (int)offset;
110                 matches[mnum].len = (int)mlt;
111                 matches[mnum].back = -back;
112                 mnum++;
113             }
114         }
115     }
116 
117     *HashPos3 = current;
118     }
119 #endif
120 
121     chainTable[current & contentMask] = (U32)(current - matchIndex);
122     *HashPos =  (U32)current;
123     ctx->nextToUpdate++;
124 
125     if (best_mlen < MINMATCH-1) best_mlen = MINMATCH-1;
126 
127     while ((matchIndex < current) && (matchIndex >= lowLimit) && (nbAttempts)) {
128         nbAttempts--;
129         match = base + matchIndex;
130         if ((U32)(ip - match) >= LIZARD_OPTIMAL_MIN_OFFSET) {
131             if (matchIndex >= dictLimit) {
132                 if ((/*fullSearch ||*/ ip[best_mlen] == match[best_mlen]) && (MEM_readMINMATCH(match) == MEM_readMINMATCH(ip))) {
133                     int back = 0;
134                     mlt = Lizard_count(ip+MINMATCH, match+MINMATCH, iHighLimit) + MINMATCH;
135                     while ((ip+back > iLowLimit) && (match+back > lowPrefixPtr) && (ip[back-1] == match[back-1])) back--;
136                     mlt -= back;
137 
138                     if ((mlt >= minMatchLongOff) || ((U32)(ip - match) < LIZARD_MAX_16BIT_OFFSET))
139                     if (mlt > best_mlen) {
140                         best_mlen = mlt;
141                         matches[mnum].off = (int)(ip - match);
142                         matches[mnum].len = (int)mlt;
143                         matches[mnum].back = -back;
144                         mnum++;
145 
146                         if (best_mlen > LIZARD_OPT_NUM) break;
147                     }
148                 }
149             } else {
150                 matchDict = dictBase + matchIndex;
151     //            fprintf(stderr, "dictBase[%p]+matchIndex[%d]=match[%p] dictLimit=%d base=%p ip=%p iLimit=%p off=%d\n", dictBase, matchIndex, match, dictLimit, base, ip, iLimit, (U32)(ip-match));
152                 if ((U32)((dictLimit-1) - matchIndex) >= 3)  /* intentional overflow */
153                 if (MEM_readMINMATCH(matchDict) == MEM_readMINMATCH(ip)) {
154                     int back=0;
155                     mlt = Lizard_count_2segments(ip+MINMATCH, matchDict+MINMATCH, iHighLimit, dictEnd, lowPrefixPtr) + MINMATCH;
156                     while ((ip+back > iLowLimit) && (matchIndex+back > lowLimit) && (ip[back-1] == matchDict[back-1])) back--;
157                     mlt -= back;
158 
159                     if ((mlt >= minMatchLongOff) || ((U32)(ip - match) < LIZARD_MAX_16BIT_OFFSET))
160                     if (mlt > best_mlen) {
161                         best_mlen = mlt;
162                         matches[mnum].off = (int)(ip - match);
163                         matches[mnum].len = (int)mlt;
164                         matches[mnum].back = -back;
165                         mnum++;
166 
167                         if (best_mlen > LIZARD_OPT_NUM) break;
168                     }
169                 }
170             }
171         }
172         matchIndex -= chainTable[matchIndex & contentMask];
173     }
174 
175     return mnum;
176 }
177 
178 
179 
180 
Lizard_BinTree_GetAllMatches(Lizard_stream_t * ctx,const BYTE * const ip,const BYTE * const iHighLimit,size_t best_mlen,Lizard_match_t * matches)181 FORCE_INLINE int Lizard_BinTree_GetAllMatches (
182     Lizard_stream_t* ctx,
183     const BYTE* const ip,
184     const BYTE* const iHighLimit,
185     size_t best_mlen,
186     Lizard_match_t* matches)
187 {
188     U32* const chainTable = ctx->chainTable;
189     U32* const HashTable = ctx->hashTable;
190     const BYTE* const base = ctx->base;
191     const intptr_t dictLimit = ctx->dictLimit;
192     const BYTE* const dictBase = ctx->dictBase;
193     const BYTE* const dictEnd = dictBase + dictLimit;
194     const U32 contentMask = (1 << ctx->params.contentLog) - 1;
195     const BYTE* const lowPrefixPtr = base + dictLimit;
196     const intptr_t maxDistance = (1 << ctx->params.windowLog) - 1;
197     const intptr_t current = (ip - base);
198     const intptr_t lowLimit = ((intptr_t)ctx->lowLimit + maxDistance >= current) ? (intptr_t)ctx->lowLimit : current - maxDistance;
199     const BYTE* match;
200     const size_t minMatchLongOff = ctx->params.minMatchLongOff;
201     int nbAttempts = ctx->params.searchNum;
202     int mnum = 0;
203     U32 *ptr0, *ptr1, delta0, delta1;
204     intptr_t matchIndex;
205     size_t mlt = 0;
206     U32* HashPos;
207 
208     if (ip + MINMATCH > iHighLimit) return 0;
209 
210     /* First Match */
211     HashPos = &HashTable[Lizard_hashPtr(ip, ctx->params.hashLog, ctx->params.searchLength)];
212     matchIndex = *HashPos;
213 
214 
215 #if MINMATCH == 3
216     {
217     U32* HashPos3 = &ctx->hashTable3[Lizard_hash3Ptr(ip, ctx->params.hashLog3)];
218 
219     if ((*HashPos3 < current) && (*HashPos3 >= lowLimit)) {
220         size_t offset = current - *HashPos3;
221         if (offset < LIZARD_MAX_8BIT_OFFSET) {
222             match = ip - offset;
223             if (match > base && MEM_readMINMATCH(ip) == MEM_readMINMATCH(match))
224             {
225                 mlt = Lizard_count(ip + MINMATCH, match + MINMATCH, iHighLimit) + MINMATCH;
226 
227                 matches[mnum].off = (int)offset;
228                 matches[mnum].len = (int)mlt;
229                 matches[mnum].back = 0;
230                 mnum++;
231             }
232         }
233         *HashPos3 = current;
234     }
235     }
236 #endif
237 
238     *HashPos = (U32)current;
239     ctx->nextToUpdate++;
240 
241     // check rest of matches
242     ptr0 = &chainTable[(current*2+1) & contentMask];
243     ptr1 = &chainTable[(current*2) & contentMask];
244     delta0 = delta1 = (U32)(current - matchIndex);
245 
246     if (best_mlen < MINMATCH-1) best_mlen = MINMATCH-1;
247 
248     while ((matchIndex < current) && (matchIndex >= lowLimit) && (nbAttempts)) {
249         nbAttempts--;
250         if (matchIndex >= dictLimit) {
251             match = base + matchIndex;
252            // if (ip[mlt] == match[mlt])
253                 mlt = Lizard_count(ip, match, iHighLimit);
254         } else {
255             match = dictBase + matchIndex;
256             mlt = Lizard_count_2segments(ip, match, iHighLimit, dictEnd, lowPrefixPtr);
257             if (matchIndex + (int)mlt >= dictLimit)
258                 match = base + matchIndex;   /* to prepare for next usage of match[mlt] */
259         }
260 
261         if ((U32)(current - matchIndex) >= LIZARD_OPTIMAL_MIN_OFFSET) {
262             if ((mlt >= minMatchLongOff) || ((U32)(current - matchIndex) < LIZARD_MAX_16BIT_OFFSET))
263             if (mlt > best_mlen) {
264                 best_mlen = mlt;
265                 matches[mnum].off = (int)(current - matchIndex);
266                 matches[mnum].len = (int)mlt;
267                 matches[mnum].back = 0;
268                 mnum++;
269 
270                 if (mlt > LIZARD_OPT_NUM) break;
271                 if (ip + mlt >= iHighLimit) break;
272             }
273         } else {
274 #if 1
275             intptr_t newMatchIndex;
276             size_t newml = 0, newoff = 0;
277             do {
278                 newoff += (int)(current - matchIndex);
279             } while (newoff < LIZARD_OPTIMAL_MIN_OFFSET);
280             newMatchIndex = current - newoff;
281             if (newMatchIndex >= dictLimit) newml = Lizard_count(ip, base + newMatchIndex, iHighLimit);
282 
283         //    printf("%d: off=%d mlt=%d\n", (U32)current, (U32)(current - matchIndex), (int)mlt);
284         //    printf("%d: newoff=%d newml=%d\n", (U32)current, (int)newoff, (int)newml);
285 
286             if ((newml >= minMatchLongOff) && (newml > best_mlen)) {
287                 best_mlen = newml;
288                 matches[mnum].off = (int)newoff;
289                 matches[mnum].len = (int)newml;
290                 matches[mnum].back = 0;
291                 mnum++;
292 
293                 if (newml > LIZARD_OPT_NUM) break;
294                 if (ip + newml >= iHighLimit) break;
295             }
296 #endif
297         }
298 
299         if (ip[mlt] < match[mlt]) {
300             *ptr0 = delta0;
301             ptr0 = &chainTable[(matchIndex*2) & contentMask];
302             if (*ptr0 == (U32)-1) break;
303             delta0 = *ptr0;
304             delta1 += delta0;
305             matchIndex -= delta0;
306         } else {
307             *ptr1 = delta1;
308             ptr1 = &chainTable[(matchIndex*2+1) & contentMask];
309             if (*ptr1 == (U32)-1) break;
310             delta1 = *ptr1;
311             delta0 += delta1;
312             matchIndex -= delta1;
313         }
314     }
315 
316     *ptr0 = (U32)-1;
317     *ptr1 = (U32)-1;
318 
319     return mnum;
320 }
321 
322 
323 #define SET_PRICE(pos, mlen, offset, litlen, price)   \
324     {                                                 \
325         while (last_pos < pos)  { opt[last_pos+1].price = LIZARD_MAX_PRICE; last_pos++; } \
326         opt[pos].mlen = (int)mlen;                         \
327         opt[pos].off = (int)offset;                        \
328         opt[pos].litlen = (int)litlen;                     \
329         opt[pos].price = (int)price;                       \
330         LIZARD_LOG_PARSER("%d: SET price[%d/%d]=%d litlen=%d len=%d off=%d\n", (int)(inr-source), pos, last_pos, opt[pos].price, opt[pos].litlen, opt[pos].mlen, opt[pos].off); \
331     }
332 
333 
Lizard_compress_optimalPrice(Lizard_stream_t * const ctx,const BYTE * ip,const BYTE * const iend)334 FORCE_INLINE int Lizard_compress_optimalPrice(
335         Lizard_stream_t* const ctx,
336         const BYTE* ip,
337         const BYTE* const iend)
338 {
339     Lizard_optimal_t opt[LIZARD_OPT_NUM + 4];
340     Lizard_match_t matches[LIZARD_OPT_NUM + 1];
341     const BYTE *inr;
342     size_t res, cur, cur2, skip_num = 0;
343     size_t i, llen, litlen, mlen, best_mlen, price, offset, best_off, match_num, last_pos;
344 
345     const BYTE* anchor = ip;
346     const BYTE* const mflimit = iend - MFLIMIT;
347     const BYTE* const matchlimit = (iend - LASTLITERALS);
348     const BYTE* const base = ctx->base;
349     const BYTE* const dictBase = ctx->dictBase;
350     const intptr_t dictLimit = ctx->dictLimit;
351     const BYTE* const dictEnd = dictBase + dictLimit;
352     const BYTE* const lowPrefixPtr = base + dictLimit;
353     const intptr_t lowLimit = ctx->lowLimit;
354     const intptr_t maxDistance = (1 << ctx->params.windowLog) - 1;
355 
356     const size_t sufficient_len = ctx->params.sufficientLength;
357     const int faster_get_matches = (ctx->params.fullSearch == 0);
358     const size_t minMatchLongOff = ctx->params.minMatchLongOff;
359     const int lizardOptimalMinOffset = (ctx->params.decompressType == Lizard_coderwords_LZ4) ? (1<<30) : LIZARD_OPTIMAL_MIN_OFFSET;
360     const size_t repMinMatch = (ctx->params.decompressType == Lizard_coderwords_LZ4) ? MINMATCH : REPMINMATCH;
361 
362     /* Main Loop */
363     while (ip < mflimit) {
364         memset(opt, 0, sizeof(Lizard_optimal_t));
365         last_pos = 0;
366         llen = ip - anchor;
367 
368         /* check rep code */
369 
370         if (ctx->last_off >= lizardOptimalMinOffset) {
371             intptr_t matchIndexLO = (ip - ctx->last_off) - base;
372             mlen = 0;
373             if ((matchIndexLO >= lowLimit) && (base + matchIndexLO + maxDistance >= ip)) {
374                 if (matchIndexLO >= dictLimit) {
375                     mlen = Lizard_count(ip, base + matchIndexLO, matchlimit);
376                 } else {
377                     mlen = Lizard_count_2segments(ip, dictBase + matchIndexLO, matchlimit, dictEnd, lowPrefixPtr);
378                 }
379             }
380             if (mlen >= REPMINMATCH) {
381                 if (mlen > sufficient_len || mlen >= LIZARD_OPT_NUM) {
382                     best_mlen = mlen; best_off = 0; cur = 0; last_pos = 1;
383                     goto encode;
384                 }
385 
386                 do
387                 {
388                     litlen = 0;
389                     price = Lizard_get_price(ctx, ctx->last_off, ip, ctx->off24pos, llen, 0, mlen);
390                     if (mlen > last_pos || price < (size_t)opt[mlen].price)
391                         SET_PRICE(mlen, mlen, 0, litlen, price);
392                     mlen--;
393                 }
394                 while (mlen >= REPMINMATCH);
395             }
396         }
397 
398         if (faster_get_matches && last_pos)
399            match_num = 0;
400         else
401         {
402             if (ctx->params.parserType == Lizard_parser_optimalPrice) {
403                 Lizard_Insert(ctx, ip);
404                 match_num = Lizard_GetAllMatches(ctx, ip, ip, matchlimit, last_pos, matches);
405             } else {
406                 Lizard_BinTree_Insert(ctx, ip);
407                 match_num = Lizard_BinTree_GetAllMatches(ctx, ip, matchlimit, last_pos, matches);
408             }
409         }
410 
411         LIZARD_LOG_PARSER("%d: match_num=%d last_pos=%d\n", (int)(ip-source), match_num, last_pos);
412         if (!last_pos && !match_num) { ip++; continue; }
413 
414         if (match_num && (size_t)matches[match_num-1].len > sufficient_len) {
415             best_mlen = matches[match_num-1].len;
416             best_off = matches[match_num-1].off;
417             cur = 0;
418             last_pos = 1;
419             goto encode;
420         }
421 
422         // set prices using matches at position = 0
423         best_mlen = (last_pos > MINMATCH) ? last_pos : MINMATCH;
424 
425         for (i = 0; i < match_num; i++) {
426             mlen = (i>0) ? (size_t)matches[i-1].len+1 : best_mlen;
427             best_mlen = (matches[i].len < LIZARD_OPT_NUM) ? matches[i].len : LIZARD_OPT_NUM;
428             LIZARD_LOG_PARSER("%d: start Found mlen=%d off=%d best_mlen=%d last_pos=%d\n", (int)(ip-source), matches[i].len, matches[i].off, best_mlen, last_pos);
429             while (mlen <= best_mlen){
430                 litlen = 0;
431                 price = Lizard_get_price(ctx, ctx->last_off, ip, ctx->off24pos, llen + litlen, matches[i].off, mlen);
432 
433                 if ((mlen >= minMatchLongOff) || (matches[i].off < LIZARD_MAX_16BIT_OFFSET))
434                 if (mlen > last_pos || price < (size_t)opt[mlen].price)
435                     SET_PRICE(mlen, mlen, matches[i].off, litlen, price);
436                 mlen++;
437             }
438         }
439 
440         if (last_pos < repMinMatch) { ip++; continue; }
441 
442         opt[0].off24pos = ctx->off24pos;
443         opt[0].rep = ctx->last_off;
444         opt[0].mlen = 1;
445         opt[0].off = -1;
446 
447         // check further positions
448         for (skip_num = 0, cur = 1; cur <= last_pos; cur++) {
449             int rep;
450             inr = ip + cur;
451 
452             if (opt[cur-1].off == -1) { // -1 = literals, 0 = rep
453                 litlen = opt[cur-1].litlen + 1;
454 
455                 if (cur != litlen) {
456                     price = opt[cur - litlen].price + Lizard_get_price(ctx, opt[cur-litlen].rep, inr, ctx->off24pos, litlen, 0, 0);
457                     LIZARD_LOG_PRICE("%d: TRY1 opt[%d].price=%d price=%d cur=%d litlen=%d\n", (int)(inr-source), cur - litlen, opt[cur - litlen].price, price, cur, litlen);
458                 } else {
459                     price = Lizard_get_price(ctx, ctx->last_off, inr, ctx->off24pos, llen + litlen, 0, 0);
460                     LIZARD_LOG_PRICE("%d: TRY2 price=%d cur=%d litlen=%d llen=%d\n", (int)(inr-source), price, cur, litlen, llen);
461                 }
462             } else {
463                 litlen = 1;
464                 price = opt[cur - 1].price + Lizard_get_price(ctx, opt[cur-1].rep, inr, ctx->off24pos, litlen, 0, 0);
465                 LIZARD_LOG_PRICE("%d: TRY3 price=%d cur=%d litlen=%d litonly=%d\n", (int)(inr-source), price, cur, litlen, Lizard_get_price(ctx, rep, inr, ctx->off24pos, litlen, 0, 0));
466             }
467 
468             mlen = 1;
469             best_mlen = 0;
470             LIZARD_LOG_PARSER("%d: TRY price=%d opt[%d].price=%d\n", (int)(inr-source), price, cur, opt[cur].price);
471 
472             if (cur > last_pos || price <= (size_t)opt[cur].price) // || ((price == opt[cur].price) && (opt[cur-1].mlen == 1) && (cur != litlen)))
473                 SET_PRICE(cur, mlen, -1, litlen, price);
474 
475             if (cur == last_pos) break;
476 
477 
478 
479             /* set rep code */
480             if (opt[cur].off != -1) {
481                 mlen = opt[cur].mlen;
482                 offset = opt[cur].off;
483                 if (offset < 1) {
484                     opt[cur].rep = opt[cur-mlen].rep;
485                     opt[cur].off24pos = opt[cur-mlen].off24pos;
486                     LIZARD_LOG_PARSER("%d: COPYREP1 cur=%d mlen=%d rep=%d\n", (int)(inr-source), cur, mlen, opt[cur-mlen].rep);
487                 } else {
488                     opt[cur].rep = (int)offset;
489                     opt[cur].off24pos = (offset >= LIZARD_MAX_16BIT_OFFSET) ? inr : opt[cur-mlen].off24pos;
490                     LIZARD_LOG_PARSER("%d: COPYREP2 cur=%d offset=%d rep=%d\n", (int)(inr-source), cur, offset, opt[cur].rep);
491                 }
492             } else {
493                 opt[cur].rep = opt[cur-1].rep; // copy rep
494                 opt[cur].off24pos = opt[cur-1].off24pos;
495             }
496 
497             rep = opt[cur].rep;
498             LIZARD_LOG_PARSER("%d: CURRENT price[%d/%d]=%d off=%d mlen=%d litlen=%d rep=%d\n", (int)(inr-source), cur, last_pos, opt[cur].price, opt[cur].off, opt[cur].mlen, opt[cur].litlen, opt[cur].rep);
499 
500 
501             /* check rep code */
502             if (opt[cur].rep >= lizardOptimalMinOffset) {
503                 intptr_t matchIndexLO = (inr - opt[cur].rep) - base;
504                 mlen = 0;
505                 if ((matchIndexLO >= lowLimit) && (base + matchIndexLO + maxDistance >= inr)) {
506                     if (matchIndexLO >= dictLimit) {
507                         mlen = Lizard_count(inr, base + matchIndexLO, matchlimit);
508                     } else {
509                         mlen = Lizard_count_2segments(inr, dictBase + matchIndexLO, matchlimit, dictEnd, lowPrefixPtr);
510                     }
511                 }
512                 if (mlen >= REPMINMATCH/* && mlen > best_mlen*/) {
513                     LIZARD_LOG_PARSER("%d: try REP rep=%d mlen=%d\n", (int)(inr-source), opt[cur].rep, mlen);
514                     LIZARD_LOG_PARSER("%d: Found REP mlen=%d off=%d rep=%d opt[%d].off=%d\n", (int)(inr-source), mlen, 0, opt[cur].rep, cur, opt[cur].off);
515 
516                     if (mlen > sufficient_len || cur + mlen >= LIZARD_OPT_NUM) {
517                         best_mlen = mlen;
518                         best_off = 0;
519                         LIZARD_LOG_PARSER("%d: REP sufficient_len=%d best_mlen=%d best_off=%d last_pos=%d\n", (int)(inr-source), sufficient_len, best_mlen, best_off, last_pos);
520                         last_pos = cur + 1;
521                         goto encode;
522                     }
523 
524                     best_mlen = mlen;
525                     if (faster_get_matches)
526                         skip_num = best_mlen;
527 
528                     do
529                     {
530                         //if (opt[cur].mlen == 1)
531                         if (opt[cur].off == -1) {
532                             litlen = opt[cur].litlen;
533 
534                             if (cur != litlen) {
535                                 price = opt[cur - litlen].price + Lizard_get_price(ctx, rep, inr, opt[cur].off24pos, litlen, 0, mlen);
536                                 LIZARD_LOG_PRICE("%d: TRY1 opt[%d].price=%d price=%d cur=%d litlen=%d\n", (int)(inr-source), cur - litlen, opt[cur - litlen].price, price, cur, litlen);
537                             } else {
538                                 price = Lizard_get_price(ctx, rep, inr, ctx->off24pos, llen + litlen, 0, mlen);
539                                 LIZARD_LOG_PRICE("%d: TRY2 price=%d cur=%d litlen=%d llen=%d\n", (int)(inr-source), price, cur, litlen, llen);
540                             }
541                         } else {
542                             litlen = 0;
543                             price = opt[cur].price + Lizard_get_price(ctx, rep, inr, opt[cur].off24pos, litlen, 0, mlen);
544                             LIZARD_LOG_PRICE("%d: TRY3 price=%d cur=%d litlen=%d getprice=%d\n", (int)(inr-source), price, cur, litlen, Lizard_get_price(ctx, rep, inr, opt[cur].off24pos, litlen, 0, mlen - MINMATCH));
545                         }
546 
547                         LIZARD_LOG_PARSER("%d: Found REP mlen=%d off=%d price=%d litlen=%d price[%d]=%d\n", (int)(inr-source), mlen, 0, price, litlen, cur - litlen, opt[cur - litlen].price);
548 
549                         if (cur + mlen > last_pos || price <= (size_t)opt[cur + mlen].price) // || ((price == opt[cur + mlen].price) && (opt[cur].mlen == 1) && (cur != litlen))) // at equal price prefer REP instead of MATCH
550                             SET_PRICE(cur + mlen, mlen, 0, litlen, price);
551                         mlen--;
552                     }
553                     while (mlen >= REPMINMATCH);
554                 }
555             }
556 
557             if (faster_get_matches && skip_num > 0) {
558                 skip_num--;
559                 continue;
560             }
561 
562             if (ctx->params.parserType == Lizard_parser_optimalPrice) {
563                 Lizard_Insert(ctx, inr);
564                 match_num = Lizard_GetAllMatches(ctx, inr, ip, matchlimit, best_mlen, matches);
565                 LIZARD_LOG_PARSER("%d: Lizard_GetAllMatches match_num=%d\n", (int)(inr-source), match_num);
566             } else {
567                 Lizard_BinTree_Insert(ctx, inr);
568                 match_num = Lizard_BinTree_GetAllMatches(ctx, inr, matchlimit, best_mlen, matches);
569                 LIZARD_LOG_PARSER("%d: Lizard_BinTree_GetAllMatches match_num=%d\n", (int)(inr-source), match_num);
570             }
571 
572 
573             if (match_num > 0 && (size_t)matches[match_num-1].len > sufficient_len) {
574                 cur -= matches[match_num-1].back;
575                 best_mlen = matches[match_num-1].len;
576                 best_off = matches[match_num-1].off;
577                 last_pos = cur + 1;
578                 goto encode;
579             }
580 
581             // set prices using matches at position = cur
582             best_mlen = (best_mlen > MINMATCH) ? best_mlen : MINMATCH;
583 
584             for (i = 0; i < match_num; i++) {
585                 mlen = (i>0) ? (size_t)matches[i-1].len+1 : best_mlen;
586                 cur2 = cur - matches[i].back;
587                 best_mlen = (cur2 + matches[i].len < LIZARD_OPT_NUM) ? (size_t)matches[i].len : LIZARD_OPT_NUM - cur2;
588                 LIZARD_LOG_PARSER("%d: Found1 cur=%d cur2=%d mlen=%d off=%d best_mlen=%d last_pos=%d\n", (int)(inr-source), cur, cur2, matches[i].len, matches[i].off, best_mlen, last_pos);
589 
590                 if (mlen < (size_t)matches[i].back + 1)
591                     mlen = matches[i].back + 1;
592 
593                 while (mlen <= best_mlen) {
594                   //  if (opt[cur2].mlen == 1)
595                     if (opt[cur2].off == -1)
596                     {
597                         litlen = opt[cur2].litlen;
598 
599                         if (cur2 != litlen)
600                             price = opt[cur2 - litlen].price + Lizard_get_price(ctx, rep, inr, opt[cur2].off24pos, litlen, matches[i].off, mlen);
601                         else
602                             price = Lizard_get_price(ctx, rep, inr, ctx->off24pos, llen + litlen, matches[i].off, mlen);
603                     } else {
604                         litlen = 0;
605                         price = opt[cur2].price + Lizard_get_price(ctx, rep, inr, opt[cur2].off24pos, litlen, matches[i].off, mlen);
606                     }
607 
608                     LIZARD_LOG_PARSER("%d: Found2 pred=%d mlen=%d best_mlen=%d off=%d price=%d litlen=%d price[%d]=%d\n", (int)(inr-source), matches[i].back, mlen, best_mlen, matches[i].off, price, litlen, cur - litlen, opt[cur - litlen].price);
609         //                if (cur2 + mlen > last_pos || ((matches[i].off != opt[cur2 + mlen].off) && (price < opt[cur2 + mlen].price)))
610 
611                     if ((mlen >= minMatchLongOff) || (matches[i].off < LIZARD_MAX_16BIT_OFFSET))
612                     if (cur2 + mlen > last_pos || price < (size_t)opt[cur2 + mlen].price)
613                     {
614                         SET_PRICE(cur2 + mlen, mlen, matches[i].off, litlen, price);
615                     }
616 
617                     mlen++;
618                 }
619             }
620         } //  for (skip_num = 0, cur = 1; cur <= last_pos; cur++)
621 
622 
623         best_mlen = opt[last_pos].mlen;
624         best_off = opt[last_pos].off;
625         cur = last_pos - best_mlen;
626 
627         encode: // cur, last_pos, best_mlen, best_off have to be set
628         for (i = 1; i <= last_pos; i++) {
629             LIZARD_LOG_PARSER("%d: price[%d/%d]=%d off=%d mlen=%d litlen=%d rep=%d\n", (int)(ip-source+i), i, last_pos, opt[i].price, opt[i].off, opt[i].mlen, opt[i].litlen, opt[i].rep);
630         }
631 
632         LIZARD_LOG_PARSER("%d: cur=%d/%d best_mlen=%d best_off=%d rep=%d\n", (int)(ip-source+cur), cur, last_pos, best_mlen, best_off, opt[cur].rep);
633 
634         opt[0].mlen = 1;
635 
636         while (1) {
637             mlen = opt[cur].mlen;
638             offset = opt[cur].off;
639             opt[cur].mlen = (int)best_mlen;
640             opt[cur].off = (int)best_off;
641             best_mlen = mlen;
642             best_off = offset;
643             if (mlen > cur) break;
644             cur -= mlen;
645         }
646 
647         for (i = 0; i <= last_pos;) {
648             LIZARD_LOG_PARSER("%d: price2[%d/%d]=%d off=%d mlen=%d litlen=%d rep=%d\n", (int)(ip-source+i), i, last_pos, opt[i].price, opt[i].off, opt[i].mlen, opt[i].litlen, opt[i].rep);
649             i += opt[i].mlen;
650         }
651 
652         cur = 0;
653 
654         while (cur < last_pos) {
655             LIZARD_LOG_PARSER("%d: price3[%d/%d]=%d off=%d mlen=%d litlen=%d rep=%d\n", (int)(ip-source+cur), cur, last_pos, opt[cur].price, opt[cur].off, opt[cur].mlen, opt[cur].litlen, opt[cur].rep);
656             mlen = opt[cur].mlen;
657         //            if (mlen == 1) { ip++; cur++; continue; }
658             if (opt[cur].off == -1) { ip++; cur++; continue; }
659             offset = opt[cur].off;
660             cur += mlen;
661 
662             LIZARD_LOG_ENCODE("%d: ENCODE literals=%d off=%d mlen=%d ", (int)(ip-source), (int)(ip-anchor), (int)(offset), mlen);
663             res = Lizard_encodeSequence(ctx, &ip, &anchor, mlen, ip - offset);
664             if (res) return 0;
665 
666             LIZARD_LOG_PARSER("%d: offset=%d rep=%d\n", (int)(ip-source), offset, ctx->last_off);
667         }
668     }
669 
670     /* Encode Last Literals */
671     ip = iend;
672     if (Lizard_encodeLastLiterals(ctx, &ip, &anchor)) goto _output_error;
673 
674     /* End */
675     return 1;
676 _output_error:
677     return 0;
678 }
679 
680