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