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