1 #define OPTIMAL_ML (int)((ML_MASK_LZ4-1)+MINMATCH)
2
3 //#define LIZARD_NOCHAIN_HASH_FUNCTION(ip, hashLog) Lizard_hashPtr(ip, hashLog, ctx->params.searchLength)
4 #define LIZARD_NOCHAIN_HASH_FUNCTION(ip, hashLog) Lizard_hash5Ptr(ip, hashLog)
5 #define LIZARD_NOCHAIN_MIN_OFFSET 8
6
7 /* Update chains up to ip (excluded) */
Lizard_InsertNoChain(Lizard_stream_t * ctx,const BYTE * ip)8 FORCE_INLINE void Lizard_InsertNoChain (Lizard_stream_t* ctx, const BYTE* ip)
9 {
10 U32* const hashTable = ctx->hashTable;
11 const BYTE* const base = ctx->base;
12 U32 const target = (U32)(ip - base);
13 U32 idx = ctx->nextToUpdate;
14 const int hashLog = ctx->params.hashLog;
15
16 while (idx < target) {
17 size_t const h = LIZARD_NOCHAIN_HASH_FUNCTION(base+idx, hashLog);
18 if ((hashTable[h] >= idx) || (idx >= hashTable[h] + LIZARD_NOCHAIN_MIN_OFFSET))
19 hashTable[h] = idx;
20 idx++;
21 }
22
23 ctx->nextToUpdate = target;
24 }
25
26
Lizard_InsertAndFindBestMatchNoChain(Lizard_stream_t * ctx,const BYTE * ip,const BYTE * const iLimit,const BYTE ** matchpos)27 FORCE_INLINE int Lizard_InsertAndFindBestMatchNoChain (Lizard_stream_t* ctx, /* Index table will be updated */
28 const BYTE* ip, const BYTE* const iLimit,
29 const BYTE** matchpos)
30 {
31 U32* const HashTable = ctx->hashTable;
32 const BYTE* const base = ctx->base;
33 const BYTE* const dictBase = ctx->dictBase;
34 const U32 dictLimit = ctx->dictLimit;
35 const BYTE* const lowPrefixPtr = base + dictLimit;
36 const BYTE* const dictEnd = dictBase + dictLimit;
37 U32 matchIndex;
38 const BYTE* match;
39 size_t ml=0;
40 const int hashLog = ctx->params.hashLog;
41 const U32 maxDistance = (1 << ctx->params.windowLog) - 1;
42 const U32 current = (U32)(ip - base);
43 const U32 lowLimit = (ctx->lowLimit + maxDistance >= current) ? ctx->lowLimit : current - maxDistance;
44
45 /* HC4 match finder */
46 Lizard_InsertNoChain(ctx, ip);
47 matchIndex = HashTable[LIZARD_NOCHAIN_HASH_FUNCTION(ip, hashLog)];
48
49 if ((matchIndex < current) && (matchIndex >= lowLimit)) {
50 if (matchIndex >= dictLimit) {
51 match = base + matchIndex;
52 #if LIZARD_NOCHAIN_MIN_OFFSET > 0
53 if ((U32)(ip - match) >= LIZARD_NOCHAIN_MIN_OFFSET)
54 #endif
55 if (*(match+ml) == *(ip+ml) && (MEM_read32(match) == MEM_read32(ip)))
56 {
57 size_t const mlt = Lizard_count(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH;
58 if (mlt > ml) { ml = mlt; *matchpos = match; }
59 }
60 } else {
61 match = dictBase + matchIndex;
62 #if LIZARD_NOCHAIN_MIN_OFFSET > 0
63 if ((U32)(ip - (base + matchIndex)) >= LIZARD_NOCHAIN_MIN_OFFSET)
64 #endif
65 if ((U32)((dictLimit-1) - matchIndex) >= 3) /* intentional overflow */
66 if (MEM_read32(match) == MEM_read32(ip)) {
67 size_t mlt = Lizard_count_2segments(ip+MINMATCH, match+MINMATCH, iLimit, dictEnd, lowPrefixPtr) + MINMATCH;
68 if (mlt > ml) { ml = mlt; *matchpos = base + matchIndex; } /* virtual matchpos */
69 }
70 }
71 }
72
73 return (int)ml;
74 }
75
76
Lizard_InsertAndGetWiderMatchNoChain(Lizard_stream_t * ctx,const BYTE * const ip,const BYTE * const iLowLimit,const BYTE * const iHighLimit,int longest,const BYTE ** matchpos,const BYTE ** startpos)77 FORCE_INLINE int Lizard_InsertAndGetWiderMatchNoChain (
78 Lizard_stream_t* ctx,
79 const BYTE* const ip,
80 const BYTE* const iLowLimit,
81 const BYTE* const iHighLimit,
82 int longest,
83 const BYTE** matchpos,
84 const BYTE** startpos)
85 {
86 U32* const HashTable = ctx->hashTable;
87 const BYTE* const base = ctx->base;
88 const U32 dictLimit = ctx->dictLimit;
89 const BYTE* const lowPrefixPtr = base + dictLimit;
90 const BYTE* const dictBase = ctx->dictBase;
91 const BYTE* const dictEnd = dictBase + dictLimit;
92 U32 matchIndex;
93 int LLdelta = (int)(ip-iLowLimit);
94 const int hashLog = ctx->params.hashLog;
95 const U32 maxDistance = (1 << ctx->params.windowLog) - 1;
96 const U32 current = (U32)(ip - base);
97 const U32 lowLimit = (ctx->lowLimit + maxDistance >= current) ? ctx->lowLimit : current - maxDistance;
98
99 /* First Match */
100 Lizard_InsertNoChain(ctx, ip);
101 matchIndex = HashTable[LIZARD_NOCHAIN_HASH_FUNCTION(ip, hashLog)];
102
103 if ((matchIndex < current) && (matchIndex >= lowLimit)) {
104 if (matchIndex >= dictLimit) {
105 const BYTE* match = base + matchIndex;
106 #if LIZARD_NOCHAIN_MIN_OFFSET > 0
107 if ((U32)(ip - match) >= LIZARD_NOCHAIN_MIN_OFFSET)
108 #endif
109 if (*(iLowLimit + longest) == *(match - LLdelta + longest)) {
110 if (MEM_read32(match) == MEM_read32(ip)) {
111 int mlt = MINMATCH + Lizard_count(ip+MINMATCH, match+MINMATCH, iHighLimit);
112 int back = 0;
113 while ((ip+back > iLowLimit) && (match+back > lowPrefixPtr) && (ip[back-1] == match[back-1])) back--;
114 mlt -= back;
115
116 if (mlt > longest) {
117 longest = (int)mlt;
118 *matchpos = match+back;
119 *startpos = ip+back;
120 }
121 }
122 }
123 } else {
124 const BYTE* match = dictBase + matchIndex;
125 #if LIZARD_NOCHAIN_MIN_OFFSET > 0
126 if ((U32)(ip - (base + matchIndex)) >= LIZARD_NOCHAIN_MIN_OFFSET)
127 #endif
128 if ((U32)((dictLimit-1) - matchIndex) >= 3) /* intentional overflow */
129 if (MEM_read32(match) == MEM_read32(ip)) {
130 int back=0;
131 size_t mlt = Lizard_count_2segments(ip+MINMATCH, match+MINMATCH, iHighLimit, dictEnd, lowPrefixPtr) + MINMATCH;
132 while ((ip+back > iLowLimit) && (matchIndex+back > lowLimit) && (ip[back-1] == match[back-1])) back--;
133 mlt -= back;
134 if ((int)mlt > longest) { longest = (int)mlt; *matchpos = base + matchIndex + back; *startpos = ip+back; }
135 }
136 }
137 }
138
139 return longest;
140 }
141
142
Lizard_compress_noChain(Lizard_stream_t * const ctx,const BYTE * ip,const BYTE * const iend)143 FORCE_INLINE int Lizard_compress_noChain (
144 Lizard_stream_t* const ctx,
145 const BYTE* ip,
146 const BYTE* const iend)
147 {
148 const BYTE* anchor = ip;
149 const BYTE* const mflimit = iend - MFLIMIT;
150 const BYTE* const matchlimit = (iend - LASTLITERALS);
151
152 int ml, ml2, ml3, ml0;
153 const BYTE* ref = NULL;
154 const BYTE* start2 = NULL;
155 const BYTE* ref2 = NULL;
156 const BYTE* start3 = NULL;
157 const BYTE* ref3 = NULL;
158 const BYTE* start0;
159 const BYTE* ref0;
160
161 /* init */
162 ip++;
163
164 /* Main Loop */
165 while (ip < mflimit) {
166 ml = Lizard_InsertAndFindBestMatchNoChain (ctx, ip, matchlimit, (&ref));
167 if (!ml) { ip++; continue; }
168
169 /* saved, in case we would skip too much */
170 start0 = ip;
171 ref0 = ref;
172 ml0 = ml;
173
174 _Search2:
175 if (ip+ml < mflimit)
176 ml2 = Lizard_InsertAndGetWiderMatchNoChain(ctx, ip + ml - 2, ip + 1, matchlimit, ml, &ref2, &start2);
177 else ml2 = ml;
178
179 if (ml2 == ml) { /* No better match */
180 if (Lizard_encodeSequence_LZ4(ctx, &ip, &anchor, ml, ref)) return 0;
181 continue;
182 }
183
184 if (start0 < ip) {
185 if (start2 < ip + ml0) { /* empirical */
186 ip = start0;
187 ref = ref0;
188 ml = ml0;
189 }
190 }
191
192 /* Here, start0==ip */
193 if ((start2 - ip) < 3) { /* First Match too small : removed */
194 ml = ml2;
195 ip = start2;
196 ref =ref2;
197 goto _Search2;
198 }
199
200 _Search3:
201 /*
202 * Currently we have :
203 * ml2 > ml1, and
204 * ip1+3 <= ip2 (usually < ip1+ml1)
205 */
206 if ((start2 - ip) < OPTIMAL_ML) {
207 int correction;
208 int new_ml = ml;
209 if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML;
210 if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = (int)(start2 - ip) + ml2 - MINMATCH;
211 correction = new_ml - (int)(start2 - ip);
212 if (correction > 0) {
213 start2 += correction;
214 ref2 += correction;
215 ml2 -= correction;
216 }
217 }
218 /* Now, we have start2 = ip+new_ml, with new_ml = min(ml, OPTIMAL_ML=18) */
219
220 if (start2 + ml2 < mflimit)
221 ml3 = Lizard_InsertAndGetWiderMatchNoChain(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3);
222 else ml3 = ml2;
223
224 if (ml3 == ml2) { /* No better match : 2 sequences to encode */
225 /* ip & ref are known; Now for ml */
226 if (start2 < ip+ml) ml = (int)(start2 - ip);
227 /* Now, encode 2 sequences */
228 if (Lizard_encodeSequence_LZ4(ctx, &ip, &anchor, ml, ref)) return 0;
229 ip = start2;
230 if (Lizard_encodeSequence_LZ4(ctx, &ip, &anchor, ml2, ref2)) return 0;
231 continue;
232 }
233
234 if (start3 < ip+ml+3) { /* Not enough space for match 2 : remove it */
235 if (start3 >= (ip+ml)) { /* can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1 */
236 if (start2 < ip+ml) {
237 int correction = (int)(ip+ml - start2);
238 start2 += correction;
239 ref2 += correction;
240 ml2 -= correction;
241 if (ml2 < MINMATCH) {
242 start2 = start3;
243 ref2 = ref3;
244 ml2 = ml3;
245 }
246 }
247
248 if (Lizard_encodeSequence_LZ4(ctx, &ip, &anchor, ml, ref)) return 0;
249 ip = start3;
250 ref = ref3;
251 ml = ml3;
252
253 start0 = start2;
254 ref0 = ref2;
255 ml0 = ml2;
256 goto _Search2;
257 }
258
259 start2 = start3;
260 ref2 = ref3;
261 ml2 = ml3;
262 goto _Search3;
263 }
264
265 /*
266 * OK, now we have 3 ascending matches; let's write at least the first one
267 * ip & ref are known; Now for ml
268 */
269 if (start2 < ip+ml) {
270 if ((start2 - ip) < (int)ML_MASK_LZ4) {
271 int correction;
272 if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;
273 if (ip + ml > start2 + ml2 - MINMATCH) {
274 ml = (int)(start2 - ip) + ml2 - MINMATCH;
275 if (ml < MINMATCH) { // match2 doesn't fit, remove it
276 if (Lizard_encodeSequence_LZ4(ctx, &ip, &anchor, ml, ref)) return 0;
277 ip = start3;
278 ref = ref3;
279 ml = ml3;
280
281 start0 = start2;
282 ref0 = ref2;
283 ml0 = ml2;
284 goto _Search2;
285 }
286 }
287 correction = ml - (int)(start2 - ip);
288 if (correction > 0) {
289 start2 += correction;
290 ref2 += correction;
291 ml2 -= correction;
292 }
293 } else {
294 ml = (int)(start2 - ip);
295 }
296 }
297 if (Lizard_encodeSequence_LZ4(ctx, &ip, &anchor, ml, ref)) return 0;
298
299 ip = start2;
300 ref = ref2;
301 ml = ml2;
302
303 start2 = start3;
304 ref2 = ref3;
305 ml2 = ml3;
306
307 goto _Search3;
308 }
309
310 /* Encode Last Literals */
311 ip = iend;
312 if (Lizard_encodeLastLiterals_LZ4(ctx, &ip, &anchor)) goto _output_error;
313
314 /* End */
315 return 1;
316 _output_error:
317 return 0;
318 }
319