Debian Codegraph @

src/lzma/LzFind.c

raw
1 /* LzFind.c -- Match finder for LZ algorithms
2 2008-10-04 : Igor Pavlov : Public domain */
3 // ----------------------------------------------------------------------------
4 // Copyright (C) 2014
5 // David Freese, W1HKJ
6 //
7 // This file is part of flmsg
8 //
9 // flrig is free software; you can redistribute it and/or modify
10 // it under the terms of the GNU General Public License as published by
11 // the Free Software Foundation; either version 3 of the License, or
12 // (at your option) any later version.
13 //
14 // flrig is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 // GNU General Public License for more details.
18 //
19 // You should have received a copy of the GNU General Public License
20 // along with this program. If not, see <http://www.gnu.org/licenses/>.
21 // ----------------------------------------------------------------------------
22
23 #include <string.h>
24
25 #include "LzFind.h"
26 #include "LzHash.h"
27
28 #define kEmptyHashValue 0
29 #define kMaxValForNormalize ((LZ_UInt32)0xFFFFFFFF)
30 #define kNormalizeStepMin (1 << 10) /* it must be power of 2 */
31 #define kNormalizeMask (~(kNormalizeStepMin - 1))
32 #define kMaxHistorySize ((LZ_UInt32)3 << 30)
33
34 #define kStartMaxLen 3
35
36 static void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc)
37 {
38 if (!p->directInput)
39 {
40 alloc->Free(alloc, p->bufferBase);
41 p->bufferBase = 0;
42 }
43 }
44
45 /* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */
46
47 static int LzInWindow_Create(CMatchFinder *p, LZ_UInt32 keepSizeReserv, ISzAlloc *alloc)
48 {
49 LZ_UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;
50 if (p->directInput)
51 {
52 p->blockSize = blockSize;
53 return 1;
54 }
55 if (p->bufferBase == 0 || p->blockSize != blockSize)
56 {
57 LzInWindow_Free(p, alloc);
58 p->blockSize = blockSize;
59 p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);
60 }
61 return (p->bufferBase != 0);
62 }
63
64 Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }
65 Byte MatchFinder_GetIndexByte(CMatchFinder *p, LZ_Int32 index) { return p->buffer[index]; }
66
67 LZ_UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }
68
69 void MatchFinder_ReduceOffsets(CMatchFinder *p, LZ_UInt32 subValue)
70 {
71 p->posLimit -= subValue;
72 p->pos -= subValue;
73 p->streamPos -= subValue;
74 }
75
76 static void MatchFinder_ReadBlock(CMatchFinder *p)
77 {
78 if (p->streamEndWasReached || p->result != SZ_OK)
79 return;
80 for (;;)
81 {
82 Byte *dest = p->buffer + (p->streamPos - p->pos);
83 size_t size = (p->bufferBase + p->blockSize - dest);
84 if (size == 0)
85 return;
86 p->result = p->stream->Read(p->stream, dest, &size);
87 if (p->result != SZ_OK)
88 return;
89 if (size == 0)
90 {
91 p->streamEndWasReached = 1;
92 return;
93 }
94 p->streamPos += (LZ_UInt32)size;
95 if (p->streamPos - p->pos > p->keepSizeAfter)
96 return;
97 }
98 }
99
100 void MatchFinder_MoveBlock(CMatchFinder *p)
101 {
102 memmove(p->bufferBase,
103 p->buffer - p->keepSizeBefore,
104 (size_t)(p->streamPos - p->pos + p->keepSizeBefore));
105 p->buffer = p->bufferBase + p->keepSizeBefore;
106 }
107
108 int MatchFinder_NeedMove(CMatchFinder *p)
109 {
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->skipModeBits = 0; */
135 p->directInput = 0;
136 p->bigHash = 0;
137 }
138
139 #define kCrcPoly 0xEDB88320
140
141 void MatchFinder_Construct(CMatchFinder *p)
142 {
143 LZ_UInt32 i;
144 p->bufferBase = 0;
145 p->directInput = 0;
146 p->hash = 0;
147 MatchFinder_SetDefaultSettings(p);
148
149 for (i = 0; i < 256; i++)
150 {
151 LZ_UInt32 r = i;
152 int j;
153 for (j = 0; j < 8; j++)
154 r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));
155 p->crc[i] = r;
156 }
157 }
158
159 static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)
160 {
161 alloc->Free(alloc, p->hash);
162 p->hash = 0;
163 }
164
165 void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)
166 {
167 MatchFinder_FreeThisClassMemory(p, alloc);
168 LzInWindow_Free(p, alloc);
169 }
170
171 static CLzRef* AllocRefs(LZ_UInt32 num, ISzAlloc *alloc)
172 {
173 size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
174 if (sizeInBytes / sizeof(CLzRef) != num)
175 return 0;
176 return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);
177 }
178
179 int MatchFinder_Create(CMatchFinder *p, LZ_UInt32 historySize,
180 LZ_UInt32 keepAddBufferBefore, LZ_UInt32 matchMaxLen, LZ_UInt32 keepAddBufferAfter,
181 ISzAlloc *alloc)
182 {
183 LZ_UInt32 sizeReserv;
184 if (historySize > kMaxHistorySize)
185 {
186 MatchFinder_Free(p, alloc);
187 return 0;
188 }
189 sizeReserv = historySize >> 1;
190 if (historySize > ((LZ_UInt32)2 << 30))
191 sizeReserv = historySize >> 2;
192 sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);
193
194 p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
195 p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
196 /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
197 if (LzInWindow_Create(p, sizeReserv, alloc))
198 {
199 LZ_UInt32 newCyclicBufferSize = (historySize /* >> p->skipModeBits */) + 1;
200 LZ_UInt32 hs;
201 p->matchMaxLen = matchMaxLen;
202 {
203 p->fixedHashSize = 0;
204 if (p->numHashBytes == 2)
205 hs = (1 << 16) - 1;
206 else
207 {
208 hs = historySize - 1;
209 hs |= (hs >> 1);
210 hs |= (hs >> 2);
211 hs |= (hs >> 4);
212 hs |= (hs >> 8);
213 hs >>= 1;
214 /* hs >>= p->skipModeBits; */
215 hs |= 0xFFFF; /* don't change it! It's required for Deflate */
216 if (hs > (1 << 24))
217 {
218 if (p->numHashBytes == 3)
219 hs = (1 << 24) - 1;
220 else
221 hs >>= 1;
222 }
223 }
224 p->hashMask = hs;
225 hs++;
226 if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;
227 if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;
228 if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;
229 hs += p->fixedHashSize;
230 }
231
232 {
233 LZ_UInt32 prevSize = p->hashSizeSum + p->numSons;
234 LZ_UInt32 newSize;
235 p->historySize = historySize;
236 p->hashSizeSum = hs;
237 p->cyclicBufferSize = newCyclicBufferSize;
238 p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize);
239 newSize = p->hashSizeSum + p->numSons;
240 if (p->hash != 0 && prevSize == newSize)
241 return 1;
242 MatchFinder_FreeThisClassMemory(p, alloc);
243 p->hash = AllocRefs(newSize, alloc);
244 if (p->hash != 0)
245 {
246 p->son = p->hash + p->hashSizeSum;
247 return 1;
248 }
249 }
250 }
251 MatchFinder_Free(p, alloc);
252 return 0;
253 }
254
255 static void MatchFinder_SetLimits(CMatchFinder *p)
256 {
257 LZ_UInt32 limit = kMaxValForNormalize - p->pos;
258 LZ_UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
259 if (limit2 < limit)
260 limit = limit2;
261 limit2 = p->streamPos - p->pos;
262 if (limit2 <= p->keepSizeAfter)
263 {
264 if (limit2 > 0)
265 limit2 = 1;
266 }
267 else
268 limit2 -= p->keepSizeAfter;
269 if (limit2 < limit)
270 limit = limit2;
271 {
272 LZ_UInt32 lenLimit = p->streamPos - p->pos;
273 if (lenLimit > p->matchMaxLen)
274 lenLimit = p->matchMaxLen;
275 p->lenLimit = lenLimit;
276 }
277 p->posLimit = p->pos + limit;
278 }
279
280 void MatchFinder_Init(CMatchFinder *p)
281 {
282 LZ_UInt32 i;
283 for (i = 0; i < p->hashSizeSum; i++)
284 p->hash[i] = kEmptyHashValue;
285 p->cyclicBufferPos = 0;
286 p->buffer = p->bufferBase;
287 p->pos = p->streamPos = p->cyclicBufferSize;
288 p->result = SZ_OK;
289 p->streamEndWasReached = 0;
290 MatchFinder_ReadBlock(p);
291 MatchFinder_SetLimits(p);
292 }
293
294 static LZ_UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
295 {
296 return (p->pos - p->historySize - 1) & kNormalizeMask;
297 }
298
299 void MatchFinder_Normalize3(LZ_UInt32 subValue, CLzRef *items, LZ_UInt32 numItems)
300 {
301 LZ_UInt32 i;
302 for (i = 0; i < numItems; i++)
303 {
304 LZ_UInt32 value = items[i];
305 if (value <= subValue)
306 value = kEmptyHashValue;
307 else
308 value -= subValue;
309 items[i] = value;
310 }
311 }
312
313 static void MatchFinder_Normalize(CMatchFinder *p)
314 {
315 LZ_UInt32 subValue = MatchFinder_GetSubValue(p);
316 MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons);
317 MatchFinder_ReduceOffsets(p, subValue);
318 }
319
320 static void MatchFinder_CheckLimits(CMatchFinder *p)
321 {
322 if (p->pos == kMaxValForNormalize)
323 MatchFinder_Normalize(p);
324 if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
325 MatchFinder_CheckAndMoveAndRead(p);
326 if (p->cyclicBufferPos == p->cyclicBufferSize)
327 p->cyclicBufferPos = 0;
328 MatchFinder_SetLimits(p);
329 }
330
331 static LZ_UInt32 * Hc_GetMatchesSpec(LZ_UInt32 lenLimit, LZ_UInt32 curMatch, LZ_UInt32 pos, const Byte *cur, CLzRef *son,
332 LZ_UInt32 _cyclicBufferPos, LZ_UInt32 _cyclicBufferSize, LZ_UInt32 cutValue,
333 LZ_UInt32 *distances, LZ_UInt32 maxLen)
334 {
335 son[_cyclicBufferPos] = curMatch;
336 for (;;)
337 {
338 LZ_UInt32 delta = pos - curMatch;
339 if (cutValue-- == 0 || delta >= _cyclicBufferSize)
340 return distances;
341 {
342 const Byte *pb = cur - delta;
343 curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
344 if (pb[maxLen] == cur[maxLen] && *pb == *cur)
345 {
346 LZ_UInt32 len = 0;
347 while (++len != lenLimit)
348 if (pb[len] != cur[len])
349 break;
350 if (maxLen < len)
351 {
352 *distances++ = maxLen = len;
353 *distances++ = delta - 1;
354 if (len == lenLimit)
355 return distances;
356 }
357 }
358 }
359 }
360 }
361
362 LZ_UInt32 * GetMatchesSpec1(LZ_UInt32 lenLimit, LZ_UInt32 curMatch, LZ_UInt32 pos, const Byte *cur, CLzRef *son,
363 LZ_UInt32 _cyclicBufferPos, LZ_UInt32 _cyclicBufferSize, LZ_UInt32 cutValue,
364 LZ_UInt32 *distances, LZ_UInt32 maxLen)
365 {
366 CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
367 CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
368 LZ_UInt32 len0 = 0, len1 = 0;
369 for (;;)
370 {
371 LZ_UInt32 delta = pos - curMatch;
372 if (cutValue-- == 0 || delta >= _cyclicBufferSize)
373 {
374 *ptr0 = *ptr1 = kEmptyHashValue;
375 return distances;
376 }
377 {
378 CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
379 const Byte *pb = cur - delta;
380 LZ_UInt32 len = (len0 < len1 ? len0 : len1);
381 if (pb[len] == cur[len])
382 {
383 if (++len != lenLimit && pb[len] == cur[len])
384 while (++len != lenLimit)
385 if (pb[len] != cur[len])
386 break;
387 if (maxLen < len)
388 {
389 *distances++ = maxLen = len;
390 *distances++ = delta - 1;
391 if (len == lenLimit)
392 {
393 *ptr1 = pair[0];
394 *ptr0 = pair[1];
395 return distances;
396 }
397 }
398 }
399 if (pb[len] < cur[len])
400 {
401 *ptr1 = curMatch;
402 ptr1 = pair + 1;
403 curMatch = *ptr1;
404 len1 = len;
405 }
406 else
407 {
408 *ptr0 = curMatch;
409 ptr0 = pair;
410 curMatch = *ptr0;
411 len0 = len;
412 }
413 }
414 }
415 }
416
417 static void SkipMatchesSpec(LZ_UInt32 lenLimit, LZ_UInt32 curMatch, LZ_UInt32 pos, const Byte *cur, CLzRef *son,
418 LZ_UInt32 _cyclicBufferPos, LZ_UInt32 _cyclicBufferSize, LZ_UInt32 cutValue)
419 {
420 CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
421 CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
422 LZ_UInt32 len0 = 0, len1 = 0;
423 for (;;)
424 {
425 LZ_UInt32 delta = pos - curMatch;
426 if (cutValue-- == 0 || delta >= _cyclicBufferSize)
427 {
428 *ptr0 = *ptr1 = kEmptyHashValue;
429 return;
430 }
431 {
432 CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
433 const Byte *pb = cur - delta;
434 LZ_UInt32 len = (len0 < len1 ? len0 : len1);
435 if (pb[len] == cur[len])
436 {
437 while (++len != lenLimit)
438 if (pb[len] != cur[len])
439 break;
440 {
441 if (len == lenLimit)
442 {
443 *ptr1 = pair[0];
444 *ptr0 = pair[1];
445 return;
446 }
447 }
448 }
449 if (pb[len] < cur[len])
450 {
451 *ptr1 = curMatch;
452 ptr1 = pair + 1;
453 curMatch = *ptr1;
454 len1 = len;
455 }
456 else
457 {
458 *ptr0 = curMatch;
459 ptr0 = pair;
460 curMatch = *ptr0;
461 len0 = len;
462 }
463 }
464 }
465 }
466
467 #define MOVE_POS \
468 ++p->cyclicBufferPos; \
469 p->buffer++; \
470 if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
471
472 #define MOVE_POS_RET MOVE_POS return offset;
473
474 static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }
475
476 #define GET_MATCHES_HEADER2(minLen, ret_op) \
477 LZ_UInt32 lenLimit; LZ_UInt32 hashValue; const Byte *cur; LZ_UInt32 curMatch; \
478 lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
479 cur = p->buffer;
480
481 #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
482 #define SKIP_HEADER(minLen) GET_MATCHES_HEADER2(minLen, continue)
483
484 #define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
485
486 #define GET_MATCHES_FOOTER(offset, maxLen) \
487 offset = (LZ_UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
488 distances + offset, maxLen) - distances); MOVE_POS_RET;
489
490 #define SKIP_FOOTER \
491 SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
492
493 static LZ_UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, LZ_UInt32 *distances)
494 {
495 LZ_UInt32 offset;
496 GET_MATCHES_HEADER(2)
497 HASH2_CALC;
498 curMatch = p->hash[hashValue];
499 p->hash[hashValue] = p->pos;
500 offset = 0;
501 GET_MATCHES_FOOTER(offset, 1)
502 }
503
504 LZ_UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, LZ_UInt32 *distances)
505 {
506 LZ_UInt32 offset;
507 GET_MATCHES_HEADER(3)
508 HASH_ZIP_CALC;
509 curMatch = p->hash[hashValue];
510 p->hash[hashValue] = p->pos;
511 offset = 0;
512 GET_MATCHES_FOOTER(offset, 2)
513 }
514
515 static LZ_UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, LZ_UInt32 *distances)
516 {
517 LZ_UInt32 hash2Value, delta2, maxLen, offset;
518 GET_MATCHES_HEADER(3)
519
520 HASH3_CALC;
521
522 delta2 = p->pos - p->hash[hash2Value];
523 curMatch = p->hash[kFix3HashSize + hashValue];
524
525 p->hash[hash2Value] =
526 p->hash[kFix3HashSize + hashValue] = p->pos;
527
528
529 maxLen = 2;
530 offset = 0;
531 if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
532 {
533 for (; maxLen != lenLimit; maxLen++)
534 if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
535 break;
536 distances[0] = maxLen;
537 distances[1] = delta2 - 1;
538 offset = 2;
539 if (maxLen == lenLimit)
540 {
541 SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
542 MOVE_POS_RET;
543 }
544 }
545 GET_MATCHES_FOOTER(offset, maxLen)
546 }
547
548 static LZ_UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, LZ_UInt32 *distances)
549 {
550 LZ_UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
551 GET_MATCHES_HEADER(4)
552
553 HASH4_CALC;
554
555 delta2 = p->pos - p->hash[ hash2Value];
556 delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
557 curMatch = p->hash[kFix4HashSize + hashValue];
558
559 p->hash[ hash2Value] =
560 p->hash[kFix3HashSize + hash3Value] =
561 p->hash[kFix4HashSize + hashValue] = p->pos;
562
563 maxLen = 1;
564 offset = 0;
565 if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
566 {
567 distances[0] = maxLen = 2;
568 distances[1] = delta2 - 1;
569 offset = 2;
570 }
571 if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
572 {
573 maxLen = 3;
574 distances[offset + 1] = delta3 - 1;
575 offset += 2;
576 delta2 = delta3;
577 }
578 if (offset != 0)
579 {
580 for (; maxLen != lenLimit; maxLen++)
581 if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
582 break;
583 distances[offset - 2] = maxLen;
584 if (maxLen == lenLimit)
585 {
586 SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
587 MOVE_POS_RET;
588 }
589 }
590 if (maxLen < 3)
591 maxLen = 3;
592 GET_MATCHES_FOOTER(offset, maxLen)
593 }
594
595 static LZ_UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, LZ_UInt32 *distances)
596 {
597 LZ_UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
598 GET_MATCHES_HEADER(4)
599
600 HASH4_CALC;
601
602 delta2 = p->pos - p->hash[ hash2Value];
603 delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
604 curMatch = p->hash[kFix4HashSize + hashValue];
605
606 p->hash[ hash2Value] =
607 p->hash[kFix3HashSize + hash3Value] =
608 p->hash[kFix4HashSize + hashValue] = p->pos;
609
610 maxLen = 1;
611 offset = 0;
612 if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
613 {
614 distances[0] = maxLen = 2;
615 distances[1] = delta2 - 1;
616 offset = 2;
617 }
618 if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
619 {
620 maxLen = 3;
621 distances[offset + 1] = delta3 - 1;
622 offset += 2;
623 delta2 = delta3;
624 }
625 if (offset != 0)
626 {
627 for (; maxLen != lenLimit; maxLen++)
628 if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
629 break;
630 distances[offset - 2] = maxLen;
631 if (maxLen == lenLimit)
632 {
633 p->son[p->cyclicBufferPos] = curMatch;
634 MOVE_POS_RET;
635 }
636 }
637 if (maxLen < 3)
638 maxLen = 3;
639 offset = (LZ_UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
640 distances + offset, maxLen) - (distances));
641 MOVE_POS_RET
642 }
643
644 LZ_UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, LZ_UInt32 *distances)
645 {
646 LZ_UInt32 offset;
647 GET_MATCHES_HEADER(3)
648 HASH_ZIP_CALC;
649 curMatch = p->hash[hashValue];
650 p->hash[hashValue] = p->pos;
651 offset = (LZ_UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
652 distances, 2) - (distances));
653 MOVE_POS_RET
654 }
655
656 static void Bt2_MatchFinder_Skip(CMatchFinder *p, LZ_UInt32 num)
657 {
658 do
659 {
660 SKIP_HEADER(2)
661 HASH2_CALC;
662 curMatch = p->hash[hashValue];
663 p->hash[hashValue] = p->pos;
664 SKIP_FOOTER
665 }
666 while (--num != 0);
667 }
668
669 void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, LZ_UInt32 num)
670 {
671 do
672 {
673 SKIP_HEADER(3)
674 HASH_ZIP_CALC;
675 curMatch = p->hash[hashValue];
676 p->hash[hashValue] = p->pos;
677 SKIP_FOOTER
678 }
679 while (--num != 0);
680 }
681
682 static void Bt3_MatchFinder_Skip(CMatchFinder *p, LZ_UInt32 num)
683 {
684 do
685 {
686 LZ_UInt32 hash2Value;
687 SKIP_HEADER(3)
688 HASH3_CALC;
689 curMatch = p->hash[kFix3HashSize + hashValue];
690 p->hash[hash2Value] =
691 p->hash[kFix3HashSize + hashValue] = p->pos;
692 SKIP_FOOTER
693 }
694 while (--num != 0);
695 }
696
697 static void Bt4_MatchFinder_Skip(CMatchFinder *p, LZ_UInt32 num)
698 {
699 do
700 {
701 LZ_UInt32 hash2Value, hash3Value;
702 SKIP_HEADER(4)
703 HASH4_CALC;
704 curMatch = p->hash[kFix4HashSize + hashValue];
705 p->hash[ hash2Value] =
706 p->hash[kFix3HashSize + hash3Value] = p->pos;
707 p->hash[kFix4HashSize + hashValue] = p->pos;
708 SKIP_FOOTER
709 }
710 while (--num != 0);
711 }
712
713 static void Hc4_MatchFinder_Skip(CMatchFinder *p, LZ_UInt32 num)
714 {
715 do
716 {
717 LZ_UInt32 hash2Value, hash3Value;
718 SKIP_HEADER(4)
719 HASH4_CALC;
720 curMatch = p->hash[kFix4HashSize + hashValue];
721 p->hash[ hash2Value] =
722 p->hash[kFix3HashSize + hash3Value] =
723 p->hash[kFix4HashSize + hashValue] = p->pos;
724 p->son[p->cyclicBufferPos] = curMatch;
725 MOVE_POS
726 }
727 while (--num != 0);
728 }
729
730 void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, LZ_UInt32 num)
731 {
732 do
733 {
734 SKIP_HEADER(3)
735 HASH_ZIP_CALC;
736 curMatch = p->hash[hashValue];
737 p->hash[hashValue] = p->pos;
738 p->son[p->cyclicBufferPos] = curMatch;
739 MOVE_POS
740 }
741 while (--num != 0);
742 }
743
744 void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)
745 {
746 vTable->Init = (Mf_Init_Func)MatchFinder_Init;
747 vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte;
748 vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
749 vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
750 if (!p->btMode)
751 {
752 vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
753 vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
754 }
755 else if (p->numHashBytes == 2)
756 {
757 vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
758 vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
759 }
760 else if (p->numHashBytes == 3)
761 {
762 vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
763 vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
764 }
765 else
766 {
767 vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
768 vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
769 }
770 }