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