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