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