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