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