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