1 #define LIZARD_PRICEFAST_MIN_OFFSET 8
2 
Lizard_FindMatchFast(Lizard_stream_t * ctx,intptr_t matchIndex,intptr_t matchIndex3,const BYTE * ip,const BYTE * const iLimit,const BYTE ** matchpos)3 FORCE_INLINE int Lizard_FindMatchFast(Lizard_stream_t* ctx, intptr_t matchIndex, intptr_t matchIndex3, /* Index table will be updated */
4                                                const BYTE* ip, const BYTE* const iLimit,
5                                                const BYTE** matchpos)
6 {
7     const BYTE* const base = ctx->base;
8     const BYTE* const dictBase = ctx->dictBase;
9     const intptr_t dictLimit = ctx->dictLimit;
10     const BYTE* const dictEnd = dictBase + dictLimit;
11     const intptr_t maxDistance = (1 << ctx->params.windowLog) - 1;
12     const intptr_t current = (U32)(ip - base);
13     const intptr_t lowLimit = ((intptr_t)ctx->lowLimit + maxDistance >= current) ? (intptr_t)ctx->lowLimit : current - maxDistance;
14     const BYTE* const lowPrefixPtr = base + dictLimit;
15     const size_t minMatchLongOff = ctx->params.minMatchLongOff;
16     const BYTE* match, *matchDict;
17     size_t ml=0, mlt;
18 
19     if (ctx->last_off >= LIZARD_PRICEFAST_MIN_OFFSET) {
20         intptr_t matchIndexLO = (ip - ctx->last_off) - base;
21         if (matchIndexLO >= lowLimit) {
22             if (matchIndexLO >= dictLimit) {
23                 match = base + matchIndexLO;
24                 if (MEM_readMINMATCH(match) == MEM_readMINMATCH(ip)) {
25                     mlt = Lizard_count(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH;
26                  //   if ((mlt >= minMatchLongOff) || (ctx->last_off < LIZARD_MAX_16BIT_OFFSET))
27                     {
28                         *matchpos = match;
29                         return (int)mlt;
30                     }
31                 }
32             } else {
33                 match = dictBase + matchIndexLO;
34                 if ((U32)((dictLimit-1) - matchIndexLO) >= 3)  /* intentional overflow */
35                 if (MEM_readMINMATCH(match) == MEM_readMINMATCH(ip)) {
36                     mlt = Lizard_count_2segments(ip+MINMATCH, match+MINMATCH, iLimit, dictEnd, lowPrefixPtr) + MINMATCH;
37                  //   if ((mlt >= minMatchLongOff) || (ctx->last_off < LIZARD_MAX_16BIT_OFFSET))
38                     {
39                         *matchpos = base + matchIndexLO;  /* virtual matchpos */
40                         return (int)mlt;
41                     }
42                 }
43             }
44         }
45     }
46 
47 
48 #if MINMATCH == 3
49     if (matchIndex3 < current && matchIndex3 >= lowLimit) {
50         intptr_t offset = current - matchIndex3;
51         if (offset < LIZARD_MAX_8BIT_OFFSET) {
52             match = ip - offset;
53             if (match > base && MEM_readMINMATCH(ip) == MEM_readMINMATCH(match)) {
54                 ml = 3;//Lizard_count(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH;
55                 *matchpos = match;
56             }
57         }
58     }
59 #else
60     (void)matchIndex3;
61 #endif
62 
63     if ((matchIndex < current) && (matchIndex >= lowLimit)) {
64         match = base + matchIndex;
65         if ((U32)(ip - match) >= LIZARD_PRICEFAST_MIN_OFFSET) {
66             if (matchIndex >= dictLimit) {
67                 if (*(match+ml) == *(ip+ml) && (MEM_read32(match) == MEM_read32(ip))) {
68                     mlt = Lizard_count(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH;
69                     if ((mlt >= minMatchLongOff) || ((U32)(ip - match) < LIZARD_MAX_16BIT_OFFSET))
70                     if (!ml || (mlt > ml)) // && Lizard_better_price((ip - *matchpos), ml, (ip - match), mlt, ctx->last_off)))
71                     { ml = mlt; *matchpos = match; }
72                 }
73             } else {
74                 matchDict = dictBase + matchIndex;
75                 if ((U32)((dictLimit-1) - matchIndex) >= 3)  /* intentional overflow */
76                 if (MEM_read32(matchDict) == MEM_read32(ip)) {
77                     mlt = Lizard_count_2segments(ip+MINMATCH, matchDict+MINMATCH, iLimit, dictEnd, lowPrefixPtr) + MINMATCH;
78                     if ((mlt >= minMatchLongOff) || ((U32)(ip - match) < LIZARD_MAX_16BIT_OFFSET))
79                     if (!ml || (mlt > ml)) // && Lizard_better_price((ip - *matchpos), ml, (U32)(ip - match), mlt, ctx->last_off)))
80                     { ml = mlt; *matchpos = match; }   /* virtual matchpos */
81                 }
82             }
83         }
84     }
85 
86     return (int)ml;
87 }
88 
89 
Lizard_FindMatchFaster(Lizard_stream_t * ctx,U32 matchIndex,const BYTE * ip,const BYTE * const iLimit,const BYTE ** matchpos)90 FORCE_INLINE int Lizard_FindMatchFaster (Lizard_stream_t* ctx, U32 matchIndex,  /* Index table will be updated */
91                                                const BYTE* ip, const BYTE* const iLimit,
92                                                const BYTE** matchpos)
93 {
94     const BYTE* const base = ctx->base;
95     const BYTE* const dictBase = ctx->dictBase;
96     const U32 dictLimit = ctx->dictLimit;
97     const BYTE* const dictEnd = dictBase + dictLimit;
98     const U32 maxDistance = (1 << ctx->params.windowLog) - 1;
99     const U32 current = (U32)(ip - base);
100     const U32 lowLimit = (ctx->lowLimit + maxDistance >= current) ? ctx->lowLimit : current - maxDistance;
101     const BYTE* const lowPrefixPtr = base + dictLimit;
102     const size_t minMatchLongOff = ctx->params.minMatchLongOff;
103     const BYTE* match, *matchDict;
104     size_t ml=0, mlt;
105 
106     if (matchIndex < current && matchIndex >= lowLimit) {
107         match = base + matchIndex;
108         if ((U32)(ip - match) >= LIZARD_PRICEFAST_MIN_OFFSET) {
109             if (matchIndex >= dictLimit) {
110                 if (MEM_read32(match) == MEM_read32(ip)) {
111                     mlt = Lizard_count(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH;
112                     if ((mlt >= minMatchLongOff) || ((U32)(ip - match) < LIZARD_MAX_16BIT_OFFSET))
113                     { ml = mlt; *matchpos = match; }
114                 }
115             } else {
116                 matchDict = dictBase + matchIndex;
117                 if ((U32)((dictLimit-1) - matchIndex) >= 3)  /* intentional overflow */
118                 if (MEM_read32(matchDict) == MEM_read32(ip)) {
119                     mlt = Lizard_count_2segments(ip+MINMATCH, matchDict+MINMATCH, iLimit, dictEnd, lowPrefixPtr) + MINMATCH;
120                     if ((mlt >= minMatchLongOff) || ((U32)(ip - match) < LIZARD_MAX_16BIT_OFFSET))
121                     { ml = mlt; *matchpos = match; }   /* virtual matchpos */
122                 }
123             }
124         }
125     }
126 
127     return (int)ml;
128 }
129 
130 
131 
Lizard_compress_priceFast(Lizard_stream_t * const ctx,const BYTE * ip,const BYTE * const iend)132 FORCE_INLINE int Lizard_compress_priceFast(
133         Lizard_stream_t* const ctx,
134         const BYTE* ip,
135         const BYTE* const iend)
136 {
137     const BYTE* anchor = ip;
138     const BYTE* const mflimit = iend - MFLIMIT;
139     const BYTE* const matchlimit = (iend - LASTLITERALS);
140 
141     size_t ml, ml2=0;
142     const BYTE* ref=NULL;
143     const BYTE* start2=NULL;
144     const BYTE* ref2=NULL;
145     const BYTE* lowPrefixPtr = ctx->base + ctx->dictLimit;
146     U32* HashTable  = ctx->hashTable;
147 #if MINMATCH == 3
148     U32* HashTable3  = ctx->hashTable3;
149 #endif
150     const BYTE* const base = ctx->base;
151     const size_t minMatchLongOff = ctx->params.minMatchLongOff;
152     U32* HashPos;
153 
154     /* init */
155     ip++;
156 
157     /* Main Loop */
158     while (ip < mflimit)
159     {
160         HashPos = &HashTable[Lizard_hashPtr(ip, ctx->params.hashLog, ctx->params.searchLength)];
161 #if MINMATCH == 3
162         {
163         U32* HashPos3 = &HashTable3[Lizard_hash3Ptr(ip, ctx->params.hashLog3)];
164         ml = Lizard_FindMatchFast (ctx, *HashPos, *HashPos3, ip, matchlimit, (&ref));
165         *HashPos3 = (U32)(ip - base);
166         }
167 #else
168         ml = Lizard_FindMatchFast (ctx, *HashPos, 0, ip, matchlimit, (&ref));
169 #endif
170         if ((*HashPos >= (U32)(ip - base)) || ((U32)(ip - base) >= *HashPos + LIZARD_PRICEFAST_MIN_OFFSET))
171             *HashPos = (U32)(ip - base);
172 
173         if (!ml) { ip++; continue; }
174         if ((int)(ip - ref) == ctx->last_off) { ml2=0; ref=ip; goto _Encode; }
175 
176         {
177         int back = 0;
178         while ((ip+back>anchor) && (ref+back > lowPrefixPtr) && (ip[back-1] == ref[back-1])) back--;
179         ml -= back;
180         ip += back;
181         ref += back;
182         }
183 
184 _Search:
185         if (ip+ml >= mflimit) goto _Encode;
186 
187         start2 = ip + ml - 2;
188         HashPos = &HashTable[Lizard_hashPtr(start2, ctx->params.hashLog, ctx->params.searchLength)];
189         ml2 = Lizard_FindMatchFaster(ctx, *HashPos, start2, matchlimit, (&ref2));
190         if ((*HashPos >= (U32)(start2 - base)) || ((U32)(start2 - base) >= *HashPos + LIZARD_PRICEFAST_MIN_OFFSET))
191             *HashPos = (U32)(start2 - base);
192 
193         if (!ml2) goto _Encode;
194 
195         {
196         int back = 0;
197         while ((start2+back>ip) && (ref2+back > lowPrefixPtr) && (start2[back-1] == ref2[back-1])) back--;
198         ml2 -= back;
199         start2 += back;
200         ref2 += back;
201         }
202 
203         if (ml2 <= ml) { ml2 = 0; goto _Encode; }
204 
205         if (start2 <= ip)
206         {
207 
208             ip = start2; ref = ref2; ml = ml2;
209             ml2 = 0;
210             goto _Encode;
211         }
212 
213         if (start2 - ip < 3)
214         {
215             ip = start2; ref = ref2; ml = ml2;
216             ml2 = 0;
217             goto _Search;
218         }
219 
220         if (start2 < ip + ml)
221         {
222             size_t correction = ml - (int)(start2 - ip);
223             start2 += correction;
224             ref2 += correction;
225             ml2 -= correction;
226             if (ml2 < 3) { ml2 = 0; }
227             if ((ml2 < minMatchLongOff) && ((U32)(start2 - ref2) >= LIZARD_MAX_16BIT_OFFSET))  { ml2 = 0; }
228         }
229 
230 _Encode:
231         if (Lizard_encodeSequence_LIZv1(ctx, &ip, &anchor, ml, ref)) goto _output_error;
232 
233         if (ml2)
234         {
235             ip = start2; ref = ref2; ml = ml2;
236             ml2 = 0;
237             goto _Search;
238         }
239     }
240 
241     /* Encode Last Literals */
242     ip = iend;
243     if (Lizard_encodeLastLiterals_LIZv1(ctx, &ip, &anchor)) goto _output_error;
244 
245     /* End */
246     return 1;
247 _output_error:
248     return 0;
249 }
250 
251