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