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