]>
Commit | Line | Data |
---|---|---|
1e230224 | 1 | /* LzFind.c -- Match finder for LZ algorithms\r |
7e6776de | 2 | 2018-07-08 : Igor Pavlov : Public domain */\r |
11ff2c71 | 3 | \r |
1e230224 | 4 | #include "Precomp.h"\r |
11ff2c71 LG |
5 | \r |
6 | #ifndef EFIAPI\r | |
11ff2c71 | 7 | #include <string.h>\r |
1e230224 | 8 | #endif\r |
11ff2c71 LG |
9 | \r |
10 | #include "LzFind.h"\r | |
11 | #include "LzHash.h"\r | |
12 | \r | |
13 | #define kEmptyHashValue 0\r | |
14 | #define kMaxValForNormalize ((UInt32)0xFFFFFFFF)\r | |
15 | #define kNormalizeStepMin (1 << 10) /* it must be power of 2 */\r | |
1e230224 LG |
16 | #define kNormalizeMask (~(UInt32)(kNormalizeStepMin - 1))\r |
17 | #define kMaxHistorySize ((UInt32)7 << 29)\r | |
11ff2c71 LG |
18 | \r |
19 | #define kStartMaxLen 3\r | |
20 | \r | |
f0737de8 | 21 | static void LzInWindow_Free(CMatchFinder *p, ISzAllocPtr alloc)\r |
11ff2c71 LG |
22 | {\r |
23 | if (!p->directInput)\r | |
24 | {\r | |
f0737de8 | 25 | ISzAlloc_Free(alloc, p->bufferBase);\r |
1e230224 | 26 | p->bufferBase = NULL;\r |
11ff2c71 LG |
27 | }\r |
28 | }\r | |
29 | \r | |
30 | /* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */\r | |
31 | \r | |
f0737de8 | 32 | static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAllocPtr alloc)\r |
11ff2c71 LG |
33 | {\r |
34 | UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;\r | |
35 | if (p->directInput)\r | |
36 | {\r | |
37 | p->blockSize = blockSize;\r | |
38 | return 1;\r | |
39 | }\r | |
1e230224 | 40 | if (!p->bufferBase || p->blockSize != blockSize)\r |
11ff2c71 LG |
41 | {\r |
42 | LzInWindow_Free(p, alloc);\r | |
43 | p->blockSize = blockSize;\r | |
f0737de8 | 44 | p->bufferBase = (Byte *)ISzAlloc_Alloc(alloc, (size_t)blockSize);\r |
11ff2c71 | 45 | }\r |
1e230224 | 46 | return (p->bufferBase != NULL);\r |
11ff2c71 LG |
47 | }\r |
48 | \r | |
49 | Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }\r | |
11ff2c71 LG |
50 | \r |
51 | UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }\r | |
52 | \r | |
53 | void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)\r | |
54 | {\r | |
55 | p->posLimit -= subValue;\r | |
56 | p->pos -= subValue;\r | |
57 | p->streamPos -= subValue;\r | |
58 | }\r | |
59 | \r | |
60 | static void MatchFinder_ReadBlock(CMatchFinder *p)\r | |
61 | {\r | |
62 | if (p->streamEndWasReached || p->result != SZ_OK)\r | |
63 | return;\r | |
1e230224 LG |
64 | \r |
65 | /* We use (p->streamPos - p->pos) value. (p->streamPos < p->pos) is allowed. */\r | |
66 | \r | |
67 | if (p->directInput)\r | |
68 | {\r | |
69 | UInt32 curSize = 0xFFFFFFFF - (p->streamPos - p->pos);\r | |
70 | if (curSize > p->directInputRem)\r | |
71 | curSize = (UInt32)p->directInputRem;\r | |
72 | p->directInputRem -= curSize;\r | |
73 | p->streamPos += curSize;\r | |
74 | if (p->directInputRem == 0)\r | |
75 | p->streamEndWasReached = 1;\r | |
76 | return;\r | |
77 | }\r | |
ba39402f | 78 | \r |
11ff2c71 LG |
79 | for (;;)\r |
80 | {\r | |
81 | Byte *dest = p->buffer + (p->streamPos - p->pos);\r | |
82 | size_t size = (p->bufferBase + p->blockSize - dest);\r | |
83 | if (size == 0)\r | |
84 | return;\r | |
1e230224 | 85 | \r |
f0737de8 | 86 | p->result = ISeqInStream_Read(p->stream, dest, &size);\r |
11ff2c71 LG |
87 | if (p->result != SZ_OK)\r |
88 | return;\r | |
89 | if (size == 0)\r | |
90 | {\r | |
91 | p->streamEndWasReached = 1;\r | |
92 | return;\r | |
93 | }\r | |
94 | p->streamPos += (UInt32)size;\r | |
95 | if (p->streamPos - p->pos > p->keepSizeAfter)\r | |
96 | return;\r | |
97 | }\r | |
98 | }\r | |
99 | \r | |
100 | void MatchFinder_MoveBlock(CMatchFinder *p)\r | |
101 | {\r | |
102 | memmove(p->bufferBase,\r | |
1e230224 LG |
103 | p->buffer - p->keepSizeBefore,\r |
104 | (size_t)(p->streamPos - p->pos) + p->keepSizeBefore);\r | |
11ff2c71 LG |
105 | p->buffer = p->bufferBase + p->keepSizeBefore;\r |
106 | }\r | |
107 | \r | |
108 | int MatchFinder_NeedMove(CMatchFinder *p)\r | |
109 | {\r | |
1e230224 LG |
110 | if (p->directInput)\r |
111 | return 0;\r | |
11ff2c71 LG |
112 | /* if (p->streamEndWasReached) return 0; */\r |
113 | return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);\r | |
114 | }\r | |
115 | \r | |
116 | void MatchFinder_ReadIfRequired(CMatchFinder *p)\r | |
117 | {\r | |
118 | if (p->streamEndWasReached)\r | |
119 | return;\r | |
120 | if (p->keepSizeAfter >= p->streamPos - p->pos)\r | |
121 | MatchFinder_ReadBlock(p);\r | |
122 | }\r | |
123 | \r | |
124 | static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)\r | |
125 | {\r | |
126 | if (MatchFinder_NeedMove(p))\r | |
127 | MatchFinder_MoveBlock(p);\r | |
128 | MatchFinder_ReadBlock(p);\r | |
129 | }\r | |
130 | \r | |
131 | static void MatchFinder_SetDefaultSettings(CMatchFinder *p)\r | |
132 | {\r | |
133 | p->cutValue = 32;\r | |
134 | p->btMode = 1;\r | |
135 | p->numHashBytes = 4;\r | |
11ff2c71 LG |
136 | p->bigHash = 0;\r |
137 | }\r | |
138 | \r | |
139 | #define kCrcPoly 0xEDB88320\r | |
140 | \r | |
141 | void MatchFinder_Construct(CMatchFinder *p)\r | |
142 | {\r | |
7e6776de | 143 | unsigned i;\r |
1e230224 | 144 | p->bufferBase = NULL;\r |
11ff2c71 | 145 | p->directInput = 0;\r |
1e230224 | 146 | p->hash = NULL;\r |
f0737de8 | 147 | p->expectedDataSize = (UInt64)(Int64)-1;\r |
11ff2c71 LG |
148 | MatchFinder_SetDefaultSettings(p);\r |
149 | \r | |
150 | for (i = 0; i < 256; i++)\r | |
151 | {\r | |
7e6776de | 152 | UInt32 r = (UInt32)i;\r |
1e230224 | 153 | unsigned j;\r |
11ff2c71 | 154 | for (j = 0; j < 8; j++)\r |
f0737de8 | 155 | r = (r >> 1) ^ (kCrcPoly & ((UInt32)0 - (r & 1)));\r |
11ff2c71 LG |
156 | p->crc[i] = r;\r |
157 | }\r | |
158 | }\r | |
159 | \r | |
f0737de8 | 160 | static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAllocPtr alloc)\r |
11ff2c71 | 161 | {\r |
f0737de8 | 162 | ISzAlloc_Free(alloc, p->hash);\r |
1e230224 | 163 | p->hash = NULL;\r |
11ff2c71 LG |
164 | }\r |
165 | \r | |
f0737de8 | 166 | void MatchFinder_Free(CMatchFinder *p, ISzAllocPtr alloc)\r |
11ff2c71 LG |
167 | {\r |
168 | MatchFinder_FreeThisClassMemory(p, alloc);\r | |
169 | LzInWindow_Free(p, alloc);\r | |
170 | }\r | |
171 | \r | |
f0737de8 | 172 | static CLzRef* AllocRefs(size_t num, ISzAllocPtr alloc)\r |
11ff2c71 LG |
173 | {\r |
174 | size_t sizeInBytes = (size_t)num * sizeof(CLzRef);\r | |
175 | if (sizeInBytes / sizeof(CLzRef) != num)\r | |
1e230224 | 176 | return NULL;\r |
f0737de8 | 177 | return (CLzRef *)ISzAlloc_Alloc(alloc, sizeInBytes);\r |
11ff2c71 LG |
178 | }\r |
179 | \r | |
180 | int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,\r | |
181 | UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,\r | |
f0737de8 | 182 | ISzAllocPtr alloc)\r |
11ff2c71 LG |
183 | {\r |
184 | UInt32 sizeReserv;\r | |
ba39402f | 185 | \r |
11ff2c71 LG |
186 | if (historySize > kMaxHistorySize)\r |
187 | {\r | |
188 | MatchFinder_Free(p, alloc);\r | |
189 | return 0;\r | |
190 | }\r | |
ba39402f | 191 | \r |
11ff2c71 | 192 | sizeReserv = historySize >> 1;\r |
1e230224 LG |
193 | if (historySize >= ((UInt32)3 << 30)) sizeReserv = historySize >> 3;\r |
194 | else if (historySize >= ((UInt32)2 << 30)) sizeReserv = historySize >> 2;\r | |
ba39402f | 195 | \r |
11ff2c71 LG |
196 | sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);\r |
197 | \r | |
198 | p->keepSizeBefore = historySize + keepAddBufferBefore + 1;\r | |
199 | p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;\r | |
ba39402f | 200 | \r |
11ff2c71 | 201 | /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */\r |
ba39402f | 202 | \r |
11ff2c71 LG |
203 | if (LzInWindow_Create(p, sizeReserv, alloc))\r |
204 | {\r | |
1e230224 | 205 | UInt32 newCyclicBufferSize = historySize + 1;\r |
11ff2c71 LG |
206 | UInt32 hs;\r |
207 | p->matchMaxLen = matchMaxLen;\r | |
208 | {\r | |
209 | p->fixedHashSize = 0;\r | |
210 | if (p->numHashBytes == 2)\r | |
211 | hs = (1 << 16) - 1;\r | |
212 | else\r | |
213 | {\r | |
f0737de8 LG |
214 | hs = historySize;\r |
215 | if (hs > p->expectedDataSize)\r | |
216 | hs = (UInt32)p->expectedDataSize;\r | |
217 | if (hs != 0)\r | |
218 | hs--;\r | |
11ff2c71 LG |
219 | hs |= (hs >> 1);\r |
220 | hs |= (hs >> 2);\r | |
221 | hs |= (hs >> 4);\r | |
222 | hs |= (hs >> 8);\r | |
223 | hs >>= 1;\r | |
11ff2c71 LG |
224 | hs |= 0xFFFF; /* don't change it! It's required for Deflate */\r |
225 | if (hs > (1 << 24))\r | |
226 | {\r | |
227 | if (p->numHashBytes == 3)\r | |
228 | hs = (1 << 24) - 1;\r | |
229 | else\r | |
230 | hs >>= 1;\r | |
1e230224 | 231 | /* if (bigHash) mode, GetHeads4b() in LzFindMt.c needs (hs >= ((1 << 24) - 1))) */\r |
11ff2c71 LG |
232 | }\r |
233 | }\r | |
234 | p->hashMask = hs;\r | |
235 | hs++;\r | |
236 | if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;\r | |
237 | if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;\r | |
238 | if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;\r | |
239 | hs += p->fixedHashSize;\r | |
240 | }\r | |
241 | \r | |
242 | {\r | |
1e230224 LG |
243 | size_t newSize;\r |
244 | size_t numSons;\r | |
11ff2c71 LG |
245 | p->historySize = historySize;\r |
246 | p->hashSizeSum = hs;\r | |
247 | p->cyclicBufferSize = newCyclicBufferSize;\r | |
ba39402f | 248 | \r |
1e230224 LG |
249 | numSons = newCyclicBufferSize;\r |
250 | if (p->btMode)\r | |
251 | numSons <<= 1;\r | |
252 | newSize = hs + numSons;\r | |
253 | \r | |
254 | if (p->hash && p->numRefs == newSize)\r | |
11ff2c71 | 255 | return 1;\r |
ba39402f | 256 | \r |
11ff2c71 | 257 | MatchFinder_FreeThisClassMemory(p, alloc);\r |
1e230224 | 258 | p->numRefs = newSize;\r |
11ff2c71 | 259 | p->hash = AllocRefs(newSize, alloc);\r |
ba39402f | 260 | \r |
1e230224 | 261 | if (p->hash)\r |
11ff2c71 LG |
262 | {\r |
263 | p->son = p->hash + p->hashSizeSum;\r | |
264 | return 1;\r | |
265 | }\r | |
266 | }\r | |
267 | }\r | |
1e230224 | 268 | \r |
11ff2c71 LG |
269 | MatchFinder_Free(p, alloc);\r |
270 | return 0;\r | |
271 | }\r | |
272 | \r | |
273 | static void MatchFinder_SetLimits(CMatchFinder *p)\r | |
274 | {\r | |
275 | UInt32 limit = kMaxValForNormalize - p->pos;\r | |
276 | UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;\r | |
ba39402f | 277 | \r |
11ff2c71 LG |
278 | if (limit2 < limit)\r |
279 | limit = limit2;\r | |
280 | limit2 = p->streamPos - p->pos;\r | |
ba39402f | 281 | \r |
11ff2c71 LG |
282 | if (limit2 <= p->keepSizeAfter)\r |
283 | {\r | |
284 | if (limit2 > 0)\r | |
285 | limit2 = 1;\r | |
286 | }\r | |
287 | else\r | |
288 | limit2 -= p->keepSizeAfter;\r | |
ba39402f | 289 | \r |
11ff2c71 LG |
290 | if (limit2 < limit)\r |
291 | limit = limit2;\r | |
ba39402f | 292 | \r |
11ff2c71 LG |
293 | {\r |
294 | UInt32 lenLimit = p->streamPos - p->pos;\r | |
295 | if (lenLimit > p->matchMaxLen)\r | |
296 | lenLimit = p->matchMaxLen;\r | |
297 | p->lenLimit = lenLimit;\r | |
298 | }\r | |
299 | p->posLimit = p->pos + limit;\r | |
300 | }\r | |
301 | \r | |
f0737de8 LG |
302 | \r |
303 | void MatchFinder_Init_LowHash(CMatchFinder *p)\r | |
304 | {\r | |
305 | size_t i;\r | |
306 | CLzRef *items = p->hash;\r | |
307 | size_t numItems = p->fixedHashSize;\r | |
308 | for (i = 0; i < numItems; i++)\r | |
309 | items[i] = kEmptyHashValue;\r | |
310 | }\r | |
311 | \r | |
312 | \r | |
313 | void MatchFinder_Init_HighHash(CMatchFinder *p)\r | |
314 | {\r | |
315 | size_t i;\r | |
316 | CLzRef *items = p->hash + p->fixedHashSize;\r | |
317 | size_t numItems = (size_t)p->hashMask + 1;\r | |
318 | for (i = 0; i < numItems; i++)\r | |
319 | items[i] = kEmptyHashValue;\r | |
320 | }\r | |
321 | \r | |
322 | \r | |
323 | void MatchFinder_Init_3(CMatchFinder *p, int readData)\r | |
11ff2c71 | 324 | {\r |
11ff2c71 LG |
325 | p->cyclicBufferPos = 0;\r |
326 | p->buffer = p->bufferBase;\r | |
f0737de8 LG |
327 | p->pos =\r |
328 | p->streamPos = p->cyclicBufferSize;\r | |
11ff2c71 LG |
329 | p->result = SZ_OK;\r |
330 | p->streamEndWasReached = 0;\r | |
ba39402f | 331 | \r |
1e230224 LG |
332 | if (readData)\r |
333 | MatchFinder_ReadBlock(p);\r | |
ba39402f | 334 | \r |
11ff2c71 LG |
335 | MatchFinder_SetLimits(p);\r |
336 | }\r | |
337 | \r | |
f0737de8 | 338 | \r |
1e230224 LG |
339 | void MatchFinder_Init(CMatchFinder *p)\r |
340 | {\r | |
f0737de8 LG |
341 | MatchFinder_Init_HighHash(p);\r |
342 | MatchFinder_Init_LowHash(p);\r | |
343 | MatchFinder_Init_3(p, True);\r | |
1e230224 | 344 | }\r |
f0737de8 | 345 | \r |
ba39402f | 346 | \r |
11ff2c71 LG |
347 | static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)\r |
348 | {\r | |
349 | return (p->pos - p->historySize - 1) & kNormalizeMask;\r | |
350 | }\r | |
351 | \r | |
1e230224 | 352 | void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, size_t numItems)\r |
11ff2c71 | 353 | {\r |
1e230224 | 354 | size_t i;\r |
11ff2c71 LG |
355 | for (i = 0; i < numItems; i++)\r |
356 | {\r | |
357 | UInt32 value = items[i];\r | |
358 | if (value <= subValue)\r | |
359 | value = kEmptyHashValue;\r | |
360 | else\r | |
361 | value -= subValue;\r | |
362 | items[i] = value;\r | |
363 | }\r | |
364 | }\r | |
365 | \r | |
366 | static void MatchFinder_Normalize(CMatchFinder *p)\r | |
367 | {\r | |
368 | UInt32 subValue = MatchFinder_GetSubValue(p);\r | |
1e230224 | 369 | MatchFinder_Normalize3(subValue, p->hash, p->numRefs);\r |
11ff2c71 LG |
370 | MatchFinder_ReduceOffsets(p, subValue);\r |
371 | }\r | |
372 | \r | |
7e6776de LW |
373 | \r |
374 | MY_NO_INLINE\r | |
11ff2c71 LG |
375 | static void MatchFinder_CheckLimits(CMatchFinder *p)\r |
376 | {\r | |
377 | if (p->pos == kMaxValForNormalize)\r | |
378 | MatchFinder_Normalize(p);\r | |
379 | if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)\r | |
380 | MatchFinder_CheckAndMoveAndRead(p);\r | |
381 | if (p->cyclicBufferPos == p->cyclicBufferSize)\r | |
382 | p->cyclicBufferPos = 0;\r | |
383 | MatchFinder_SetLimits(p);\r | |
384 | }\r | |
385 | \r | |
7e6776de LW |
386 | \r |
387 | /*\r | |
388 | (lenLimit > maxLen)\r | |
389 | */\r | |
390 | MY_FORCE_INLINE\r | |
391 | static UInt32 * Hc_GetMatchesSpec(unsigned lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,\r | |
11ff2c71 | 392 | UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,\r |
7e6776de | 393 | UInt32 *distances, unsigned maxLen)\r |
11ff2c71 | 394 | {\r |
7e6776de | 395 | /*\r |
11ff2c71 LG |
396 | son[_cyclicBufferPos] = curMatch;\r |
397 | for (;;)\r | |
398 | {\r | |
399 | UInt32 delta = pos - curMatch;\r | |
400 | if (cutValue-- == 0 || delta >= _cyclicBufferSize)\r | |
401 | return distances;\r | |
402 | {\r | |
403 | const Byte *pb = cur - delta;\r | |
404 | curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];\r | |
405 | if (pb[maxLen] == cur[maxLen] && *pb == *cur)\r | |
406 | {\r | |
407 | UInt32 len = 0;\r | |
408 | while (++len != lenLimit)\r | |
409 | if (pb[len] != cur[len])\r | |
410 | break;\r | |
411 | if (maxLen < len)\r | |
412 | {\r | |
7e6776de LW |
413 | maxLen = len;\r |
414 | *distances++ = len;\r | |
11ff2c71 LG |
415 | *distances++ = delta - 1;\r |
416 | if (len == lenLimit)\r | |
417 | return distances;\r | |
418 | }\r | |
419 | }\r | |
420 | }\r | |
421 | }\r | |
7e6776de LW |
422 | */\r |
423 | \r | |
424 | const Byte *lim = cur + lenLimit;\r | |
425 | son[_cyclicBufferPos] = curMatch;\r | |
426 | do\r | |
427 | {\r | |
428 | UInt32 delta = pos - curMatch;\r | |
429 | if (delta >= _cyclicBufferSize)\r | |
430 | break;\r | |
431 | {\r | |
432 | ptrdiff_t diff;\r | |
433 | curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];\r | |
434 | diff = (ptrdiff_t)0 - delta;\r | |
435 | if (cur[maxLen] == cur[maxLen + diff])\r | |
436 | {\r | |
437 | const Byte *c = cur;\r | |
438 | while (*c == c[diff])\r | |
439 | {\r | |
440 | if (++c == lim)\r | |
441 | {\r | |
442 | distances[0] = (UInt32)(lim - cur);\r | |
443 | distances[1] = delta - 1;\r | |
444 | return distances + 2;\r | |
445 | }\r | |
446 | }\r | |
447 | {\r | |
448 | unsigned len = (unsigned)(c - cur);\r | |
449 | if (maxLen < len)\r | |
450 | {\r | |
451 | maxLen = len;\r | |
452 | distances[0] = (UInt32)len;\r | |
453 | distances[1] = delta - 1;\r | |
454 | distances += 2;\r | |
455 | }\r | |
456 | }\r | |
457 | }\r | |
458 | }\r | |
459 | }\r | |
460 | while (--cutValue);\r | |
461 | \r | |
462 | return distances;\r | |
11ff2c71 LG |
463 | }\r |
464 | \r | |
7e6776de LW |
465 | \r |
466 | MY_FORCE_INLINE\r | |
11ff2c71 LG |
467 | UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,\r |
468 | UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,\r | |
469 | UInt32 *distances, UInt32 maxLen)\r | |
470 | {\r | |
7e6776de LW |
471 | CLzRef *ptr0 = son + ((size_t)_cyclicBufferPos << 1) + 1;\r |
472 | CLzRef *ptr1 = son + ((size_t)_cyclicBufferPos << 1);\r | |
473 | unsigned len0 = 0, len1 = 0;\r | |
11ff2c71 LG |
474 | for (;;)\r |
475 | {\r | |
476 | UInt32 delta = pos - curMatch;\r | |
477 | if (cutValue-- == 0 || delta >= _cyclicBufferSize)\r | |
478 | {\r | |
479 | *ptr0 = *ptr1 = kEmptyHashValue;\r | |
480 | return distances;\r | |
481 | }\r | |
482 | {\r | |
7e6776de | 483 | CLzRef *pair = son + ((size_t)(_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);\r |
11ff2c71 | 484 | const Byte *pb = cur - delta;\r |
7e6776de LW |
485 | unsigned len = (len0 < len1 ? len0 : len1);\r |
486 | UInt32 pair0 = pair[0];\r | |
11ff2c71 LG |
487 | if (pb[len] == cur[len])\r |
488 | {\r | |
489 | if (++len != lenLimit && pb[len] == cur[len])\r | |
490 | while (++len != lenLimit)\r | |
491 | if (pb[len] != cur[len])\r | |
492 | break;\r | |
493 | if (maxLen < len)\r | |
494 | {\r | |
7e6776de LW |
495 | maxLen = (UInt32)len;\r |
496 | *distances++ = (UInt32)len;\r | |
11ff2c71 LG |
497 | *distances++ = delta - 1;\r |
498 | if (len == lenLimit)\r | |
499 | {\r | |
7e6776de | 500 | *ptr1 = pair0;\r |
11ff2c71 LG |
501 | *ptr0 = pair[1];\r |
502 | return distances;\r | |
503 | }\r | |
504 | }\r | |
505 | }\r | |
506 | if (pb[len] < cur[len])\r | |
507 | {\r | |
508 | *ptr1 = curMatch;\r | |
509 | ptr1 = pair + 1;\r | |
510 | curMatch = *ptr1;\r | |
511 | len1 = len;\r | |
512 | }\r | |
513 | else\r | |
514 | {\r | |
515 | *ptr0 = curMatch;\r | |
516 | ptr0 = pair;\r | |
517 | curMatch = *ptr0;\r | |
518 | len0 = len;\r | |
519 | }\r | |
520 | }\r | |
521 | }\r | |
522 | }\r | |
523 | \r | |
524 | static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,\r | |
525 | UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)\r | |
526 | {\r | |
7e6776de LW |
527 | CLzRef *ptr0 = son + ((size_t)_cyclicBufferPos << 1) + 1;\r |
528 | CLzRef *ptr1 = son + ((size_t)_cyclicBufferPos << 1);\r | |
529 | unsigned len0 = 0, len1 = 0;\r | |
11ff2c71 LG |
530 | for (;;)\r |
531 | {\r | |
532 | UInt32 delta = pos - curMatch;\r | |
533 | if (cutValue-- == 0 || delta >= _cyclicBufferSize)\r | |
534 | {\r | |
535 | *ptr0 = *ptr1 = kEmptyHashValue;\r | |
536 | return;\r | |
537 | }\r | |
538 | {\r | |
7e6776de | 539 | CLzRef *pair = son + ((size_t)(_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);\r |
11ff2c71 | 540 | const Byte *pb = cur - delta;\r |
7e6776de | 541 | unsigned len = (len0 < len1 ? len0 : len1);\r |
11ff2c71 LG |
542 | if (pb[len] == cur[len])\r |
543 | {\r | |
544 | while (++len != lenLimit)\r | |
545 | if (pb[len] != cur[len])\r | |
546 | break;\r | |
547 | {\r | |
548 | if (len == lenLimit)\r | |
549 | {\r | |
550 | *ptr1 = pair[0];\r | |
551 | *ptr0 = pair[1];\r | |
552 | return;\r | |
553 | }\r | |
554 | }\r | |
555 | }\r | |
556 | if (pb[len] < cur[len])\r | |
557 | {\r | |
558 | *ptr1 = curMatch;\r | |
559 | ptr1 = pair + 1;\r | |
560 | curMatch = *ptr1;\r | |
561 | len1 = len;\r | |
562 | }\r | |
563 | else\r | |
564 | {\r | |
565 | *ptr0 = curMatch;\r | |
566 | ptr0 = pair;\r | |
567 | curMatch = *ptr0;\r | |
568 | len0 = len;\r | |
569 | }\r | |
570 | }\r | |
571 | }\r | |
572 | }\r | |
573 | \r | |
574 | #define MOVE_POS \\r | |
575 | ++p->cyclicBufferPos; \\r | |
576 | p->buffer++; \\r | |
577 | if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);\r | |
578 | \r | |
7e6776de | 579 | #define MOVE_POS_RET MOVE_POS return (UInt32)offset;\r |
11ff2c71 LG |
580 | \r |
581 | static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }\r | |
582 | \r | |
583 | #define GET_MATCHES_HEADER2(minLen, ret_op) \\r | |
7e6776de LW |
584 | unsigned lenLimit; UInt32 hv; const Byte *cur; UInt32 curMatch; \\r |
585 | lenLimit = (unsigned)p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \\r | |
11ff2c71 LG |
586 | cur = p->buffer;\r |
587 | \r | |
588 | #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)\r | |
589 | #define SKIP_HEADER(minLen) GET_MATCHES_HEADER2(minLen, continue)\r | |
590 | \r | |
591 | #define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue\r | |
592 | \r | |
593 | #define GET_MATCHES_FOOTER(offset, maxLen) \\r | |
7e6776de LW |
594 | offset = (unsigned)(GetMatchesSpec1((UInt32)lenLimit, curMatch, MF_PARAMS(p), \\r |
595 | distances + offset, (UInt32)maxLen) - distances); MOVE_POS_RET;\r | |
11ff2c71 LG |
596 | \r |
597 | #define SKIP_FOOTER \\r | |
7e6776de | 598 | SkipMatchesSpec((UInt32)lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;\r |
11ff2c71 | 599 | \r |
1e230224 LG |
600 | #define UPDATE_maxLen { \\r |
601 | ptrdiff_t diff = (ptrdiff_t)0 - d2; \\r | |
602 | const Byte *c = cur + maxLen; \\r | |
603 | const Byte *lim = cur + lenLimit; \\r | |
604 | for (; c != lim; c++) if (*(c + diff) != *c) break; \\r | |
7e6776de | 605 | maxLen = (unsigned)(c - cur); }\r |
1e230224 | 606 | \r |
11ff2c71 LG |
607 | static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r |
608 | {\r | |
7e6776de | 609 | unsigned offset;\r |
11ff2c71 LG |
610 | GET_MATCHES_HEADER(2)\r |
611 | HASH2_CALC;\r | |
1e230224 LG |
612 | curMatch = p->hash[hv];\r |
613 | p->hash[hv] = p->pos;\r | |
11ff2c71 LG |
614 | offset = 0;\r |
615 | GET_MATCHES_FOOTER(offset, 1)\r | |
616 | }\r | |
617 | \r | |
618 | UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r | |
619 | {\r | |
7e6776de | 620 | unsigned offset;\r |
11ff2c71 LG |
621 | GET_MATCHES_HEADER(3)\r |
622 | HASH_ZIP_CALC;\r | |
1e230224 LG |
623 | curMatch = p->hash[hv];\r |
624 | p->hash[hv] = p->pos;\r | |
11ff2c71 LG |
625 | offset = 0;\r |
626 | GET_MATCHES_FOOTER(offset, 2)\r | |
627 | }\r | |
628 | \r | |
629 | static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r | |
630 | {\r | |
7e6776de LW |
631 | UInt32 h2, d2, pos;\r |
632 | unsigned maxLen, offset;\r | |
1e230224 | 633 | UInt32 *hash;\r |
11ff2c71 LG |
634 | GET_MATCHES_HEADER(3)\r |
635 | \r | |
636 | HASH3_CALC;\r | |
637 | \r | |
1e230224 LG |
638 | hash = p->hash;\r |
639 | pos = p->pos;\r | |
640 | \r | |
641 | d2 = pos - hash[h2];\r | |
11ff2c71 | 642 | \r |
f0737de8 | 643 | curMatch = (hash + kFix3HashSize)[hv];\r |
ba39402f | 644 | \r |
1e230224 | 645 | hash[h2] = pos;\r |
f0737de8 | 646 | (hash + kFix3HashSize)[hv] = pos;\r |
11ff2c71 LG |
647 | \r |
648 | maxLen = 2;\r | |
649 | offset = 0;\r | |
1e230224 LG |
650 | \r |
651 | if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)\r | |
11ff2c71 | 652 | {\r |
1e230224 | 653 | UPDATE_maxLen\r |
7e6776de | 654 | distances[0] = (UInt32)maxLen;\r |
1e230224 | 655 | distances[1] = d2 - 1;\r |
11ff2c71 LG |
656 | offset = 2;\r |
657 | if (maxLen == lenLimit)\r | |
658 | {\r | |
7e6776de | 659 | SkipMatchesSpec((UInt32)lenLimit, curMatch, MF_PARAMS(p));\r |
11ff2c71 LG |
660 | MOVE_POS_RET;\r |
661 | }\r | |
662 | }\r | |
ba39402f | 663 | \r |
11ff2c71 LG |
664 | GET_MATCHES_FOOTER(offset, maxLen)\r |
665 | }\r | |
666 | \r | |
667 | static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r | |
668 | {\r | |
7e6776de LW |
669 | UInt32 h2, h3, d2, d3, pos;\r |
670 | unsigned maxLen, offset;\r | |
1e230224 | 671 | UInt32 *hash;\r |
11ff2c71 LG |
672 | GET_MATCHES_HEADER(4)\r |
673 | \r | |
674 | HASH4_CALC;\r | |
675 | \r | |
1e230224 LG |
676 | hash = p->hash;\r |
677 | pos = p->pos;\r | |
11ff2c71 | 678 | \r |
1e230224 | 679 | d2 = pos - hash[ h2];\r |
f0737de8 | 680 | d3 = pos - (hash + kFix3HashSize)[h3];\r |
1e230224 | 681 | \r |
f0737de8 | 682 | curMatch = (hash + kFix4HashSize)[hv];\r |
1e230224 LG |
683 | \r |
684 | hash[ h2] = pos;\r | |
f0737de8 LG |
685 | (hash + kFix3HashSize)[h3] = pos;\r |
686 | (hash + kFix4HashSize)[hv] = pos;\r | |
1e230224 LG |
687 | \r |
688 | maxLen = 0;\r | |
11ff2c71 | 689 | offset = 0;\r |
ba39402f | 690 | \r |
1e230224 | 691 | if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)\r |
11ff2c71 | 692 | {\r |
7e6776de LW |
693 | maxLen = 2;\r |
694 | distances[0] = 2;\r | |
1e230224 | 695 | distances[1] = d2 - 1;\r |
11ff2c71 LG |
696 | offset = 2;\r |
697 | }\r | |
ba39402f | 698 | \r |
1e230224 | 699 | if (d2 != d3 && d3 < p->cyclicBufferSize && *(cur - d3) == *cur)\r |
11ff2c71 LG |
700 | {\r |
701 | maxLen = 3;\r | |
f0737de8 | 702 | distances[(size_t)offset + 1] = d3 - 1;\r |
11ff2c71 | 703 | offset += 2;\r |
1e230224 | 704 | d2 = d3;\r |
11ff2c71 | 705 | }\r |
ba39402f | 706 | \r |
11ff2c71 LG |
707 | if (offset != 0)\r |
708 | {\r | |
1e230224 | 709 | UPDATE_maxLen\r |
7e6776de | 710 | distances[(size_t)offset - 2] = (UInt32)maxLen;\r |
11ff2c71 LG |
711 | if (maxLen == lenLimit)\r |
712 | {\r | |
7e6776de | 713 | SkipMatchesSpec((UInt32)lenLimit, curMatch, MF_PARAMS(p));\r |
11ff2c71 LG |
714 | MOVE_POS_RET;\r |
715 | }\r | |
716 | }\r | |
ba39402f | 717 | \r |
11ff2c71 LG |
718 | if (maxLen < 3)\r |
719 | maxLen = 3;\r | |
ba39402f | 720 | \r |
11ff2c71 LG |
721 | GET_MATCHES_FOOTER(offset, maxLen)\r |
722 | }\r | |
723 | \r | |
1e230224 LG |
724 | /*\r |
725 | static UInt32 Bt5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r | |
726 | {\r | |
727 | UInt32 h2, h3, h4, d2, d3, d4, maxLen, offset, pos;\r | |
728 | UInt32 *hash;\r | |
729 | GET_MATCHES_HEADER(5)\r | |
730 | \r | |
731 | HASH5_CALC;\r | |
732 | \r | |
733 | hash = p->hash;\r | |
734 | pos = p->pos;\r | |
735 | \r | |
736 | d2 = pos - hash[ h2];\r | |
f0737de8 LG |
737 | d3 = pos - (hash + kFix3HashSize)[h3];\r |
738 | d4 = pos - (hash + kFix4HashSize)[h4];\r | |
1e230224 | 739 | \r |
f0737de8 | 740 | curMatch = (hash + kFix5HashSize)[hv];\r |
1e230224 LG |
741 | \r |
742 | hash[ h2] = pos;\r | |
f0737de8 LG |
743 | (hash + kFix3HashSize)[h3] = pos;\r |
744 | (hash + kFix4HashSize)[h4] = pos;\r | |
745 | (hash + kFix5HashSize)[hv] = pos;\r | |
1e230224 LG |
746 | \r |
747 | maxLen = 0;\r | |
748 | offset = 0;\r | |
749 | \r | |
750 | if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)\r | |
751 | {\r | |
752 | distances[0] = maxLen = 2;\r | |
753 | distances[1] = d2 - 1;\r | |
754 | offset = 2;\r | |
755 | if (*(cur - d2 + 2) == cur[2])\r | |
756 | distances[0] = maxLen = 3;\r | |
757 | else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)\r | |
758 | {\r | |
759 | distances[2] = maxLen = 3;\r | |
760 | distances[3] = d3 - 1;\r | |
761 | offset = 4;\r | |
762 | d2 = d3;\r | |
763 | }\r | |
764 | }\r | |
765 | else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)\r | |
766 | {\r | |
767 | distances[0] = maxLen = 3;\r | |
768 | distances[1] = d3 - 1;\r | |
769 | offset = 2;\r | |
770 | d2 = d3;\r | |
771 | }\r | |
ba39402f | 772 | \r |
1e230224 LG |
773 | if (d2 != d4 && d4 < p->cyclicBufferSize\r |
774 | && *(cur - d4) == *cur\r | |
775 | && *(cur - d4 + 3) == *(cur + 3))\r | |
776 | {\r | |
777 | maxLen = 4;\r | |
f0737de8 | 778 | distances[(size_t)offset + 1] = d4 - 1;\r |
1e230224 LG |
779 | offset += 2;\r |
780 | d2 = d4;\r | |
781 | }\r | |
ba39402f | 782 | \r |
1e230224 LG |
783 | if (offset != 0)\r |
784 | {\r | |
785 | UPDATE_maxLen\r | |
f0737de8 | 786 | distances[(size_t)offset - 2] = maxLen;\r |
1e230224 LG |
787 | if (maxLen == lenLimit)\r |
788 | {\r | |
789 | SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));\r | |
790 | MOVE_POS_RET;\r | |
791 | }\r | |
792 | }\r | |
793 | \r | |
794 | if (maxLen < 4)\r | |
795 | maxLen = 4;\r | |
ba39402f | 796 | \r |
1e230224 LG |
797 | GET_MATCHES_FOOTER(offset, maxLen)\r |
798 | }\r | |
799 | */\r | |
800 | \r | |
11ff2c71 LG |
801 | static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r |
802 | {\r | |
7e6776de LW |
803 | UInt32 h2, h3, d2, d3, pos;\r |
804 | unsigned maxLen, offset;\r | |
1e230224 | 805 | UInt32 *hash;\r |
11ff2c71 LG |
806 | GET_MATCHES_HEADER(4)\r |
807 | \r | |
808 | HASH4_CALC;\r | |
809 | \r | |
1e230224 LG |
810 | hash = p->hash;\r |
811 | pos = p->pos;\r | |
ba39402f | 812 | \r |
1e230224 | 813 | d2 = pos - hash[ h2];\r |
f0737de8 | 814 | d3 = pos - (hash + kFix3HashSize)[h3];\r |
ba39402f | 815 | \r |
f0737de8 | 816 | curMatch = (hash + kFix4HashSize)[hv];\r |
11ff2c71 | 817 | \r |
1e230224 | 818 | hash[ h2] = pos;\r |
f0737de8 LG |
819 | (hash + kFix3HashSize)[h3] = pos;\r |
820 | (hash + kFix4HashSize)[hv] = pos;\r | |
11ff2c71 | 821 | \r |
1e230224 | 822 | maxLen = 0;\r |
11ff2c71 | 823 | offset = 0;\r |
1e230224 LG |
824 | \r |
825 | if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)\r | |
11ff2c71 | 826 | {\r |
7e6776de LW |
827 | maxLen = 2;\r |
828 | distances[0] = 2;\r | |
1e230224 | 829 | distances[1] = d2 - 1;\r |
11ff2c71 LG |
830 | offset = 2;\r |
831 | }\r | |
ba39402f | 832 | \r |
1e230224 | 833 | if (d2 != d3 && d3 < p->cyclicBufferSize && *(cur - d3) == *cur)\r |
11ff2c71 LG |
834 | {\r |
835 | maxLen = 3;\r | |
f0737de8 | 836 | distances[(size_t)offset + 1] = d3 - 1;\r |
11ff2c71 | 837 | offset += 2;\r |
1e230224 | 838 | d2 = d3;\r |
11ff2c71 | 839 | }\r |
ba39402f | 840 | \r |
11ff2c71 LG |
841 | if (offset != 0)\r |
842 | {\r | |
1e230224 | 843 | UPDATE_maxLen\r |
7e6776de | 844 | distances[(size_t)offset - 2] = (UInt32)maxLen;\r |
11ff2c71 LG |
845 | if (maxLen == lenLimit)\r |
846 | {\r | |
847 | p->son[p->cyclicBufferPos] = curMatch;\r | |
848 | MOVE_POS_RET;\r | |
849 | }\r | |
850 | }\r | |
ba39402f | 851 | \r |
11ff2c71 LG |
852 | if (maxLen < 3)\r |
853 | maxLen = 3;\r | |
1e230224 | 854 | \r |
7e6776de | 855 | offset = (unsigned)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),\r |
1e230224 | 856 | distances + offset, maxLen) - (distances));\r |
11ff2c71 LG |
857 | MOVE_POS_RET\r |
858 | }\r | |
859 | \r | |
1e230224 LG |
860 | /*\r |
861 | static UInt32 Hc5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r | |
862 | {\r | |
863 | UInt32 h2, h3, h4, d2, d3, d4, maxLen, offset, pos\r | |
864 | UInt32 *hash;\r | |
865 | GET_MATCHES_HEADER(5)\r | |
866 | \r | |
867 | HASH5_CALC;\r | |
868 | \r | |
869 | hash = p->hash;\r | |
870 | pos = p->pos;\r | |
ba39402f | 871 | \r |
1e230224 | 872 | d2 = pos - hash[ h2];\r |
f0737de8 LG |
873 | d3 = pos - (hash + kFix3HashSize)[h3];\r |
874 | d4 = pos - (hash + kFix4HashSize)[h4];\r | |
1e230224 | 875 | \r |
f0737de8 | 876 | curMatch = (hash + kFix5HashSize)[hv];\r |
1e230224 LG |
877 | \r |
878 | hash[ h2] = pos;\r | |
f0737de8 LG |
879 | (hash + kFix3HashSize)[h3] = pos;\r |
880 | (hash + kFix4HashSize)[h4] = pos;\r | |
881 | (hash + kFix5HashSize)[hv] = pos;\r | |
1e230224 LG |
882 | \r |
883 | maxLen = 0;\r | |
884 | offset = 0;\r | |
885 | \r | |
886 | if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)\r | |
887 | {\r | |
888 | distances[0] = maxLen = 2;\r | |
889 | distances[1] = d2 - 1;\r | |
890 | offset = 2;\r | |
891 | if (*(cur - d2 + 2) == cur[2])\r | |
892 | distances[0] = maxLen = 3;\r | |
893 | else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)\r | |
894 | {\r | |
895 | distances[2] = maxLen = 3;\r | |
896 | distances[3] = d3 - 1;\r | |
897 | offset = 4;\r | |
898 | d2 = d3;\r | |
899 | }\r | |
900 | }\r | |
901 | else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)\r | |
902 | {\r | |
903 | distances[0] = maxLen = 3;\r | |
904 | distances[1] = d3 - 1;\r | |
905 | offset = 2;\r | |
906 | d2 = d3;\r | |
907 | }\r | |
ba39402f | 908 | \r |
1e230224 LG |
909 | if (d2 != d4 && d4 < p->cyclicBufferSize\r |
910 | && *(cur - d4) == *cur\r | |
911 | && *(cur - d4 + 3) == *(cur + 3))\r | |
912 | {\r | |
913 | maxLen = 4;\r | |
f0737de8 | 914 | distances[(size_t)offset + 1] = d4 - 1;\r |
1e230224 LG |
915 | offset += 2;\r |
916 | d2 = d4;\r | |
917 | }\r | |
ba39402f | 918 | \r |
1e230224 LG |
919 | if (offset != 0)\r |
920 | {\r | |
921 | UPDATE_maxLen\r | |
f0737de8 | 922 | distances[(size_t)offset - 2] = maxLen;\r |
1e230224 LG |
923 | if (maxLen == lenLimit)\r |
924 | {\r | |
925 | p->son[p->cyclicBufferPos] = curMatch;\r | |
926 | MOVE_POS_RET;\r | |
927 | }\r | |
928 | }\r | |
ba39402f | 929 | \r |
1e230224 LG |
930 | if (maxLen < 4)\r |
931 | maxLen = 4;\r | |
932 | \r | |
933 | offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),\r | |
934 | distances + offset, maxLen) - (distances));\r | |
935 | MOVE_POS_RET\r | |
936 | }\r | |
937 | */\r | |
938 | \r | |
11ff2c71 LG |
939 | UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r |
940 | {\r | |
7e6776de | 941 | unsigned offset;\r |
11ff2c71 LG |
942 | GET_MATCHES_HEADER(3)\r |
943 | HASH_ZIP_CALC;\r | |
1e230224 LG |
944 | curMatch = p->hash[hv];\r |
945 | p->hash[hv] = p->pos;\r | |
7e6776de | 946 | offset = (unsigned)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),\r |
1e230224 | 947 | distances, 2) - (distances));\r |
11ff2c71 LG |
948 | MOVE_POS_RET\r |
949 | }\r | |
950 | \r | |
951 | static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r | |
952 | {\r | |
953 | do\r | |
954 | {\r | |
955 | SKIP_HEADER(2)\r | |
956 | HASH2_CALC;\r | |
1e230224 LG |
957 | curMatch = p->hash[hv];\r |
958 | p->hash[hv] = p->pos;\r | |
11ff2c71 LG |
959 | SKIP_FOOTER\r |
960 | }\r | |
961 | while (--num != 0);\r | |
962 | }\r | |
963 | \r | |
964 | void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r | |
965 | {\r | |
966 | do\r | |
967 | {\r | |
968 | SKIP_HEADER(3)\r | |
969 | HASH_ZIP_CALC;\r | |
1e230224 LG |
970 | curMatch = p->hash[hv];\r |
971 | p->hash[hv] = p->pos;\r | |
11ff2c71 LG |
972 | SKIP_FOOTER\r |
973 | }\r | |
974 | while (--num != 0);\r | |
975 | }\r | |
976 | \r | |
977 | static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r | |
978 | {\r | |
979 | do\r | |
980 | {\r | |
1e230224 LG |
981 | UInt32 h2;\r |
982 | UInt32 *hash;\r | |
11ff2c71 LG |
983 | SKIP_HEADER(3)\r |
984 | HASH3_CALC;\r | |
1e230224 | 985 | hash = p->hash;\r |
f0737de8 | 986 | curMatch = (hash + kFix3HashSize)[hv];\r |
1e230224 | 987 | hash[h2] =\r |
f0737de8 | 988 | (hash + kFix3HashSize)[hv] = p->pos;\r |
11ff2c71 LG |
989 | SKIP_FOOTER\r |
990 | }\r | |
991 | while (--num != 0);\r | |
992 | }\r | |
993 | \r | |
994 | static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r | |
995 | {\r | |
996 | do\r | |
997 | {\r | |
1e230224 LG |
998 | UInt32 h2, h3;\r |
999 | UInt32 *hash;\r | |
11ff2c71 LG |
1000 | SKIP_HEADER(4)\r |
1001 | HASH4_CALC;\r | |
1e230224 | 1002 | hash = p->hash;\r |
f0737de8 | 1003 | curMatch = (hash + kFix4HashSize)[hv];\r |
1e230224 | 1004 | hash[ h2] =\r |
f0737de8 LG |
1005 | (hash + kFix3HashSize)[h3] =\r |
1006 | (hash + kFix4HashSize)[hv] = p->pos;\r | |
1e230224 LG |
1007 | SKIP_FOOTER\r |
1008 | }\r | |
1009 | while (--num != 0);\r | |
1010 | }\r | |
1011 | \r | |
1012 | /*\r | |
1013 | static void Bt5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r | |
1014 | {\r | |
1015 | do\r | |
1016 | {\r | |
1017 | UInt32 h2, h3, h4;\r | |
1018 | UInt32 *hash;\r | |
1019 | SKIP_HEADER(5)\r | |
1020 | HASH5_CALC;\r | |
1021 | hash = p->hash;\r | |
f0737de8 | 1022 | curMatch = (hash + kFix5HashSize)[hv];\r |
1e230224 | 1023 | hash[ h2] =\r |
f0737de8 LG |
1024 | (hash + kFix3HashSize)[h3] =\r |
1025 | (hash + kFix4HashSize)[h4] =\r | |
1026 | (hash + kFix5HashSize)[hv] = p->pos;\r | |
11ff2c71 LG |
1027 | SKIP_FOOTER\r |
1028 | }\r | |
1029 | while (--num != 0);\r | |
1030 | }\r | |
1e230224 | 1031 | */\r |
11ff2c71 LG |
1032 | \r |
1033 | static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r | |
1034 | {\r | |
1035 | do\r | |
1036 | {\r | |
1e230224 LG |
1037 | UInt32 h2, h3;\r |
1038 | UInt32 *hash;\r | |
11ff2c71 LG |
1039 | SKIP_HEADER(4)\r |
1040 | HASH4_CALC;\r | |
1e230224 | 1041 | hash = p->hash;\r |
f0737de8 | 1042 | curMatch = (hash + kFix4HashSize)[hv];\r |
1e230224 | 1043 | hash[ h2] =\r |
f0737de8 LG |
1044 | (hash + kFix3HashSize)[h3] =\r |
1045 | (hash + kFix4HashSize)[hv] = p->pos;\r | |
1e230224 LG |
1046 | p->son[p->cyclicBufferPos] = curMatch;\r |
1047 | MOVE_POS\r | |
1048 | }\r | |
1049 | while (--num != 0);\r | |
1050 | }\r | |
1051 | \r | |
1052 | /*\r | |
1053 | static void Hc5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r | |
1054 | {\r | |
1055 | do\r | |
1056 | {\r | |
1057 | UInt32 h2, h3, h4;\r | |
1058 | UInt32 *hash;\r | |
1059 | SKIP_HEADER(5)\r | |
1060 | HASH5_CALC;\r | |
1061 | hash = p->hash;\r | |
f0737de8 | 1062 | curMatch = hash + kFix5HashSize)[hv];\r |
1e230224 | 1063 | hash[ h2] =\r |
f0737de8 LG |
1064 | (hash + kFix3HashSize)[h3] =\r |
1065 | (hash + kFix4HashSize)[h4] =\r | |
1066 | (hash + kFix5HashSize)[hv] = p->pos;\r | |
11ff2c71 LG |
1067 | p->son[p->cyclicBufferPos] = curMatch;\r |
1068 | MOVE_POS\r | |
1069 | }\r | |
1070 | while (--num != 0);\r | |
1071 | }\r | |
1e230224 | 1072 | */\r |
11ff2c71 LG |
1073 | \r |
1074 | void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r | |
1075 | {\r | |
1076 | do\r | |
1077 | {\r | |
1078 | SKIP_HEADER(3)\r | |
1079 | HASH_ZIP_CALC;\r | |
1e230224 LG |
1080 | curMatch = p->hash[hv];\r |
1081 | p->hash[hv] = p->pos;\r | |
11ff2c71 LG |
1082 | p->son[p->cyclicBufferPos] = curMatch;\r |
1083 | MOVE_POS\r | |
1084 | }\r | |
1085 | while (--num != 0);\r | |
1086 | }\r | |
1087 | \r | |
1088 | void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)\r | |
1089 | {\r | |
1090 | vTable->Init = (Mf_Init_Func)MatchFinder_Init;\r | |
11ff2c71 LG |
1091 | vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;\r |
1092 | vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;\r | |
1093 | if (!p->btMode)\r | |
1094 | {\r | |
1e230224 LG |
1095 | /* if (p->numHashBytes <= 4) */\r |
1096 | {\r | |
1097 | vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;\r | |
1098 | vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;\r | |
1099 | }\r | |
1100 | /*\r | |
1101 | else\r | |
1102 | {\r | |
1103 | vTable->GetMatches = (Mf_GetMatches_Func)Hc5_MatchFinder_GetMatches;\r | |
1104 | vTable->Skip = (Mf_Skip_Func)Hc5_MatchFinder_Skip;\r | |
1105 | }\r | |
1106 | */\r | |
11ff2c71 LG |
1107 | }\r |
1108 | else if (p->numHashBytes == 2)\r | |
1109 | {\r | |
1110 | vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;\r | |
1111 | vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;\r | |
1112 | }\r | |
1113 | else if (p->numHashBytes == 3)\r | |
1114 | {\r | |
1115 | vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;\r | |
1116 | vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;\r | |
1117 | }\r | |
1e230224 | 1118 | else /* if (p->numHashBytes == 4) */\r |
11ff2c71 LG |
1119 | {\r |
1120 | vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;\r | |
1121 | vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;\r | |
1122 | }\r | |
1e230224 LG |
1123 | /*\r |
1124 | else\r | |
1125 | {\r | |
1126 | vTable->GetMatches = (Mf_GetMatches_Func)Bt5_MatchFinder_GetMatches;\r | |
1127 | vTable->Skip = (Mf_Skip_Func)Bt5_MatchFinder_Skip;\r | |
1128 | }\r | |
1129 | */\r | |
11ff2c71 | 1130 | }\r |