1 #define LIZARD_LOWESTPRICE_MIN_OFFSET 8
2
3
Lizard_more_profitable(Lizard_stream_t * const ctx,const BYTE * best_ip,size_t best_off,size_t best_common,const BYTE * ip,size_t off,size_t common,size_t literals,int last_off)4 FORCE_INLINE size_t Lizard_more_profitable(Lizard_stream_t* const ctx, const BYTE *best_ip, size_t best_off, size_t best_common, const BYTE *ip, size_t off, size_t common, size_t literals, int last_off)
5 {
6 size_t sum;
7
8 if (literals > 0)
9 sum = MAX(common + literals, best_common);
10 else
11 sum = MAX(common, best_common - literals);
12
13 if ((int)off == last_off) off = 0; // rep code
14 if ((int)best_off == last_off) best_off = 0;
15
16 return Lizard_get_price_LIZv1(ctx, last_off, ip, ctx->off24pos, sum - common, (U32)off, common) <= Lizard_get_price_LIZv1(ctx, last_off, best_ip, ctx->off24pos, sum - best_common, (U32)best_off, best_common);
17 }
18
19
Lizard_better_price(Lizard_stream_t * const ctx,const BYTE * best_ip,size_t best_off,size_t best_common,const BYTE * ip,size_t off,size_t common,int last_off)20 FORCE_INLINE size_t Lizard_better_price(Lizard_stream_t* const ctx, const BYTE *best_ip, size_t best_off, size_t best_common, const BYTE *ip, size_t off, size_t common, int last_off)
21 {
22 if ((int)off == last_off) off = 0; // rep code
23 if ((int)best_off == last_off) best_off = 0;
24
25 return Lizard_get_price_LIZv1(ctx, last_off, ip, ctx->off24pos, 0, (U32)off, common) < Lizard_get_price_LIZv1(ctx, last_off, best_ip, ctx->off24pos, common - best_common, (U32)best_off, best_common);
26 }
27
28
Lizard_FindMatchLowestPrice(Lizard_stream_t * ctx,const BYTE * ip,const BYTE * const iLimit,const BYTE ** matchpos)29 FORCE_INLINE int Lizard_FindMatchLowestPrice (Lizard_stream_t* ctx, /* Index table will be updated */
30 const BYTE* ip, const BYTE* const iLimit,
31 const BYTE** matchpos)
32 {
33 U32* const chainTable = ctx->chainTable;
34 U32* const HashTable = ctx->hashTable;
35 const BYTE* const base = ctx->base;
36 const BYTE* const dictBase = ctx->dictBase;
37 const intptr_t dictLimit = ctx->dictLimit;
38 const BYTE* const dictEnd = dictBase + dictLimit;
39 const intptr_t maxDistance = (1 << ctx->params.windowLog) - 1;
40 const intptr_t current = (ip - base);
41 const intptr_t lowLimit = ((intptr_t)ctx->lowLimit + maxDistance >= current) ? (intptr_t)ctx->lowLimit : current - maxDistance;
42 const BYTE* const lowPrefixPtr = base + dictLimit;
43 const U32 contentMask = (1 << ctx->params.contentLog) - 1;
44 const size_t minMatchLongOff = ctx->params.minMatchLongOff;
45 intptr_t matchIndex;
46 const BYTE* match, *matchDict;
47 int nbAttempts=ctx->params.searchNum;
48 size_t ml=0, mlt;
49
50 matchIndex = HashTable[Lizard_hashPtr(ip, ctx->params.hashLog, ctx->params.searchLength)];
51
52 if (ctx->last_off >= LIZARD_LOWESTPRICE_MIN_OFFSET) {
53 intptr_t matchIndexLO = (ip - ctx->last_off) - base;
54 if (matchIndexLO >= lowLimit) {
55 if (matchIndexLO >= dictLimit) {
56 match = base + matchIndexLO;
57 mlt = Lizard_count(ip, match, iLimit);// + MINMATCH;
58 // if ((mlt >= minMatchLongOff) || (ctx->last_off < LIZARD_MAX_16BIT_OFFSET))
59 if (mlt > REPMINMATCH) {
60 *matchpos = match;
61 return (int)mlt;
62 }
63 } else {
64 match = dictBase + matchIndexLO;
65 if ((U32)((dictLimit-1) - matchIndexLO) >= 3) { /* intentional overflow */
66 mlt = Lizard_count_2segments(ip, match, iLimit, dictEnd, lowPrefixPtr);
67 // if ((mlt >= minMatchLongOff) || (ctx->last_off < LIZARD_MAX_16BIT_OFFSET))
68 if (mlt > REPMINMATCH) {
69 *matchpos = base + matchIndexLO; /* virtual matchpos */
70 return (int)mlt;
71 }
72 }
73 }
74 }
75 }
76
77
78 #if MINMATCH == 3
79 {
80 U32 matchIndex3 = ctx->hashTable3[Lizard_hash3Ptr(ip, ctx->params.hashLog3)];
81 if (matchIndex3 < current && matchIndex3 >= lowLimit)
82 {
83 size_t offset = (size_t)current - matchIndex3;
84 if (offset < LIZARD_MAX_8BIT_OFFSET)
85 {
86 match = ip - offset;
87 if (match > base && MEM_readMINMATCH(ip) == MEM_readMINMATCH(match))
88 {
89 ml = 3;//Lizard_count(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH;
90 *matchpos = match;
91 }
92 }
93 }
94 }
95 #endif
96 while ((matchIndex < current) && (matchIndex >= lowLimit) && (nbAttempts)) {
97 nbAttempts--;
98 match = base + matchIndex;
99 if ((U32)(ip - match) >= LIZARD_LOWESTPRICE_MIN_OFFSET) {
100 if (matchIndex >= dictLimit) {
101 if (*(match+ml) == *(ip+ml) && (MEM_read32(match) == MEM_read32(ip))) {
102 mlt = Lizard_count(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH;
103 if ((mlt >= minMatchLongOff) || ((U32)(ip - match) < LIZARD_MAX_16BIT_OFFSET))
104 if (!ml || (mlt > ml && Lizard_better_price(ctx, ip, (ip - *matchpos), ml, ip, (ip - match), mlt, ctx->last_off)))
105 { ml = mlt; *matchpos = match; }
106 }
107 } else {
108 matchDict = dictBase + matchIndex;
109 if ((U32)((dictLimit-1) - matchIndex) >= 3) /* intentional overflow */
110 if (MEM_read32(matchDict) == MEM_read32(ip)) {
111 mlt = Lizard_count_2segments(ip+MINMATCH, matchDict+MINMATCH, iLimit, dictEnd, lowPrefixPtr) + MINMATCH;
112 if ((mlt >= minMatchLongOff) || ((U32)(ip - match) < LIZARD_MAX_16BIT_OFFSET))
113 if (!ml || (mlt > ml && Lizard_better_price(ctx, ip, (ip - *matchpos), ml, ip, (U32)(ip - match), mlt, ctx->last_off)))
114 { ml = mlt; *matchpos = match; } /* virtual matchpos */
115 }
116 }
117 }
118 matchIndex -= chainTable[matchIndex & contentMask];
119 }
120
121 return (int)ml;
122 }
123
124
Lizard_GetWiderMatch(Lizard_stream_t * ctx,const BYTE * const ip,const BYTE * const iLowLimit,const BYTE * const iHighLimit,size_t longest,const BYTE ** matchpos,const BYTE ** startpos)125 FORCE_INLINE size_t Lizard_GetWiderMatch (
126 Lizard_stream_t* ctx,
127 const BYTE* const ip,
128 const BYTE* const iLowLimit,
129 const BYTE* const iHighLimit,
130 size_t longest,
131 const BYTE** matchpos,
132 const BYTE** startpos)
133 {
134 U32* const chainTable = ctx->chainTable;
135 U32* const HashTable = ctx->hashTable;
136 const BYTE* const base = ctx->base;
137 const BYTE* const dictBase = ctx->dictBase;
138 const intptr_t dictLimit = ctx->dictLimit;
139 const BYTE* const dictEnd = dictBase + dictLimit;
140 const intptr_t maxDistance = (1 << ctx->params.windowLog) - 1;
141 const intptr_t current = (ip - base);
142 const intptr_t lowLimit = ((intptr_t)ctx->lowLimit + maxDistance >= current) ? (intptr_t)ctx->lowLimit : current - maxDistance;
143 const BYTE* const lowPrefixPtr = base + dictLimit;
144 const U32 contentMask = (1 << ctx->params.contentLog) - 1;
145 const BYTE* match, *matchDict;
146 const size_t minMatchLongOff = ctx->params.minMatchLongOff;
147 intptr_t matchIndex;
148 int nbAttempts = ctx->params.searchNum;
149 size_t mlt;
150
151 /* First Match */
152 matchIndex = HashTable[Lizard_hashPtr(ip, ctx->params.hashLog, ctx->params.searchLength)];
153
154 if (ctx->last_off >= LIZARD_LOWESTPRICE_MIN_OFFSET) {
155 intptr_t matchIndexLO = (ip - ctx->last_off) - base;
156 if (matchIndexLO >= lowLimit) {
157 if (matchIndexLO >= dictLimit) {
158 match = base + matchIndexLO;
159 if (MEM_readMINMATCH(match) == MEM_readMINMATCH(ip)) {
160 int back = 0;
161 mlt = Lizard_count(ip+MINMATCH, match+MINMATCH, iHighLimit) + MINMATCH;
162 while ((ip+back > iLowLimit) && (match+back > lowPrefixPtr) && (ip[back-1] == match[back-1])) back--;
163 mlt -= back;
164
165 if (mlt > longest)
166 if ((mlt >= minMatchLongOff) || (ctx->last_off < LIZARD_MAX_16BIT_OFFSET)) {
167 *matchpos = match+back;
168 *startpos = ip+back;
169 longest = mlt;
170 }
171 }
172 } else {
173 match = dictBase + matchIndexLO;
174 if ((U32)((dictLimit-1) - matchIndexLO) >= 3) /* intentional overflow */
175 if (MEM_readMINMATCH(match) == MEM_readMINMATCH(ip)) {
176 int back=0;
177 mlt = Lizard_count_2segments(ip+MINMATCH, match+MINMATCH, iHighLimit, dictEnd, lowPrefixPtr) + MINMATCH;
178 while ((ip+back > iLowLimit) && (matchIndexLO+back > lowLimit) && (ip[back-1] == match[back-1])) back--;
179 mlt -= back;
180
181 if (mlt > longest)
182 if ((mlt >= minMatchLongOff) || (ctx->last_off < LIZARD_MAX_16BIT_OFFSET)) {
183 *matchpos = base + matchIndexLO + back; /* virtual matchpos */
184 *startpos = ip+back;
185 longest = mlt;
186 }
187 }
188 }
189 }
190 }
191
192 #if MINMATCH == 3
193 {
194 U32 matchIndex3 = ctx->hashTable3[Lizard_hash3Ptr(ip, ctx->params.hashLog3)];
195 if (matchIndex3 < current && matchIndex3 >= lowLimit) {
196 size_t offset = (size_t)current - matchIndex3;
197 if (offset < LIZARD_MAX_8BIT_OFFSET) {
198 match = ip - offset;
199 if (match > base && MEM_readMINMATCH(ip) == MEM_readMINMATCH(match)) {
200 mlt = Lizard_count(ip + MINMATCH, match + MINMATCH, iHighLimit) + MINMATCH;
201
202 int back = 0;
203 while ((ip + back > iLowLimit) && (match + back > lowPrefixPtr) && (ip[back - 1] == match[back - 1])) back--;
204 mlt -= back;
205
206 if (!longest || (mlt > longest && Lizard_better_price(ctx, *startpos, (*startpos - *matchpos), longest, ip, (ip - match), mlt, ctx->last_off))) {
207 *matchpos = match + back;
208 *startpos = ip + back;
209 longest = mlt;
210 }
211 }
212 }
213 }
214 }
215 #endif
216
217 while ((matchIndex < current) && (matchIndex >= lowLimit) && (nbAttempts)) {
218 nbAttempts--;
219 match = base + matchIndex;
220 if ((U32)(ip - match) >= LIZARD_LOWESTPRICE_MIN_OFFSET) {
221 if (matchIndex >= dictLimit) {
222 if (MEM_read32(match) == MEM_read32(ip)) {
223 int back = 0;
224 mlt = Lizard_count(ip+MINMATCH, match+MINMATCH, iHighLimit) + MINMATCH;
225 while ((ip+back > iLowLimit) && (match+back > lowPrefixPtr) && (ip[back-1] == match[back-1])) back--;
226 mlt -= back;
227
228 if ((mlt >= minMatchLongOff) || ((U32)(ip - match) < LIZARD_MAX_16BIT_OFFSET))
229 if (!longest || (mlt > longest && Lizard_better_price(ctx, *startpos, (*startpos - *matchpos), longest, ip, (ip - match), mlt, ctx->last_off)))
230 { longest = mlt; *startpos = ip+back; *matchpos = match+back; }
231 }
232 } else {
233 matchDict = dictBase + matchIndex;
234 if ((U32)((dictLimit-1) - matchIndex) >= 3) /* intentional overflow */
235 if (MEM_read32(matchDict) == MEM_read32(ip)) {
236 int back=0;
237 mlt = Lizard_count_2segments(ip+MINMATCH, matchDict+MINMATCH, iHighLimit, dictEnd, lowPrefixPtr) + MINMATCH;
238 while ((ip+back > iLowLimit) && (matchIndex+back > lowLimit) && (ip[back-1] == matchDict[back-1])) back--;
239 mlt -= back;
240
241 if ((mlt >= minMatchLongOff) || ((U32)(ip - match) < LIZARD_MAX_16BIT_OFFSET))
242 if (!longest || (mlt > longest && Lizard_better_price(ctx, *startpos, (*startpos - *matchpos), longest, ip, (U32)(ip - match), mlt, ctx->last_off)))
243 { longest = mlt; *startpos = ip+back; *matchpos = match+back; } /* virtual matchpos */
244 }
245 }
246 }
247 matchIndex -= chainTable[matchIndex & contentMask];
248 }
249
250 return longest;
251 }
252
253
254
255
Lizard_compress_lowestPrice(Lizard_stream_t * const ctx,const BYTE * ip,const BYTE * const iend)256 FORCE_INLINE int Lizard_compress_lowestPrice(
257 Lizard_stream_t* const ctx,
258 const BYTE* ip,
259 const BYTE* const iend)
260 {
261 const BYTE* anchor = ip;
262 const BYTE* const mflimit = iend - MFLIMIT;
263 const BYTE* const matchlimit = (iend - LASTLITERALS);
264
265 size_t ml, ml2, ml0;
266 const BYTE* ref=NULL;
267 const BYTE* start2=NULL;
268 const BYTE* ref2=NULL;
269 const BYTE* start0;
270 const BYTE* ref0;
271 const BYTE* lowPrefixPtr = ctx->base + ctx->dictLimit;
272 const size_t minMatchLongOff = ctx->params.minMatchLongOff;
273 const size_t sufficient_len = ctx->params.sufficientLength;
274
275 /* Main Loop */
276 while (ip < mflimit)
277 {
278 Lizard_Insert(ctx, ip);
279 ml = Lizard_FindMatchLowestPrice (ctx, ip, matchlimit, (&ref));
280 if (!ml) { ip++; continue; }
281
282 {
283 int back = 0;
284 while ((ip + back > anchor) && (ref + back > lowPrefixPtr) && (ip[back - 1] == ref[back - 1])) back--;
285 ml -= back;
286 ip += back;
287 ref += back;
288 }
289
290 /* saved, in case we would skip too much */
291 start0 = ip;
292 ref0 = ref;
293 ml0 = ml;
294 // goto _Encode;
295
296 _Search:
297 if (ip+ml >= mflimit) { goto _Encode; }
298 if (ml >= sufficient_len) { goto _Encode; }
299
300 Lizard_Insert(ctx, ip);
301 ml2 = (int)Lizard_GetWiderMatch(ctx, ip + ml - 2, anchor, matchlimit, 0, &ref2, &start2);
302 if (!ml2) goto _Encode;
303
304 {
305 U64 price, best_price;
306 int off0=0, off1=0;
307 const BYTE *pos, *best_pos;
308
309 // find the lowest price for encoding ml bytes
310 best_pos = ip;
311 best_price = LIZARD_MAX_PRICE;
312 off0 = (int)(ip - ref);
313 off1 = (int)(start2 - ref2);
314
315 for (pos = ip + ml; pos >= start2; pos--)
316 {
317 int common0 = (int)(pos - ip);
318 if (common0 >= MINMATCH) {
319 price = (int)Lizard_get_price_LIZv1(ctx, ctx->last_off, ip, ctx->off24pos, ip - anchor, (off0 == ctx->last_off) ? 0 : off0, common0);
320
321 {
322 int common1 = (int)(start2 + ml2 - pos);
323 if (common1 >= MINMATCH)
324 price += Lizard_get_price_LIZv1(ctx, ctx->last_off, pos, ctx->off24pos, 0, (off1 == off0) ? 0 : (off1), common1);
325 else
326 price += Lizard_get_price_LIZv1(ctx, ctx->last_off, pos, ctx->off24pos, common1, 0, 0);
327 }
328
329 if (price < best_price) {
330 best_price = price;
331 best_pos = pos;
332 }
333 } else {
334 price = Lizard_get_price_LIZv1(ctx, ctx->last_off, ip, ctx->off24pos, start2 - anchor, (off1 == ctx->last_off) ? 0 : off1, ml2);
335
336 if (price < best_price)
337 best_pos = pos;
338 break;
339 }
340 }
341 ml = (int)(best_pos - ip);
342 }
343
344
345 if ((ml < MINMATCH) || ((ml < minMatchLongOff) && ((U32)(ip-ref) >= LIZARD_MAX_16BIT_OFFSET)))
346 {
347 ip = start2;
348 ref = ref2;
349 ml = ml2;
350 goto _Search;
351 }
352
353 _Encode:
354 if (start0 < ip)
355 {
356 if (Lizard_more_profitable(ctx, ip, (ip - ref), ml, start0, (start0 - ref0), ml0, (ref0 - ref), ctx->last_off))
357 {
358 ip = start0;
359 ref = ref0;
360 ml = ml0;
361 }
362 }
363
364 if (Lizard_encodeSequence_LIZv1(ctx, &ip, &anchor, ml, ((ip - ref == ctx->last_off) ? ip : ref))) return 0;
365 }
366
367 /* Encode Last Literals */
368 ip = iend;
369 if (Lizard_encodeLastLiterals_LIZv1(ctx, &ip, &anchor)) goto _output_error;
370
371 /* End */
372 return 1;
373 _output_error:
374 return 0;
375 }
376
377