1 /* LzFind.c -- Match finder for LZ algorithms
2 2015-10-15 : Igor Pavlov : Public domain */
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)
17 #define kStartMaxLen 3
19 static void LzInWindow_Free(CMatchFinder
*p
, ISzAlloc
*alloc
)
23 alloc
->Free(alloc
, p
->bufferBase
);
28 /* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */
30 static int LzInWindow_Create(CMatchFinder
*p
, UInt32 keepSizeReserv
, ISzAlloc
*alloc
)
32 UInt32 blockSize
= p
->keepSizeBefore
+ p
->keepSizeAfter
+ keepSizeReserv
;
35 p
->blockSize
= blockSize
;
38 if (!p
->bufferBase
|| p
->blockSize
!= blockSize
)
40 LzInWindow_Free(p
, alloc
);
41 p
->blockSize
= blockSize
;
42 p
->bufferBase
= (Byte
*)alloc
->Alloc(alloc
, (size_t)blockSize
);
44 return (p
->bufferBase
!= NULL
);
47 Byte
*MatchFinder_GetPointerToCurrentPos(CMatchFinder
*p
) { return p
->buffer
; }
49 UInt32
MatchFinder_GetNumAvailableBytes(CMatchFinder
*p
) { return p
->streamPos
- p
->pos
; }
51 void MatchFinder_ReduceOffsets(CMatchFinder
*p
, UInt32 subValue
)
53 p
->posLimit
-= subValue
;
55 p
->streamPos
-= subValue
;
58 static void MatchFinder_ReadBlock(CMatchFinder
*p
)
60 if (p
->streamEndWasReached
|| p
->result
!= SZ_OK
)
63 /* We use (p->streamPos - p->pos) value. (p->streamPos < p->pos) is allowed. */
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;
79 Byte
*dest
= p
->buffer
+ (p
->streamPos
- p
->pos
);
80 size_t size
= (p
->bufferBase
+ p
->blockSize
- dest
);
84 p
->result
= p
->stream
->Read(p
->stream
, dest
, &size
);
85 if (p
->result
!= SZ_OK
)
89 p
->streamEndWasReached
= 1;
92 p
->streamPos
+= (UInt32
)size
;
93 if (p
->streamPos
- p
->pos
> p
->keepSizeAfter
)
98 void MatchFinder_MoveBlock(CMatchFinder
*p
)
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
;
106 int MatchFinder_NeedMove(CMatchFinder
*p
)
110 /* if (p->streamEndWasReached) return 0; */
111 return ((size_t)(p
->bufferBase
+ p
->blockSize
- p
->buffer
) <= p
->keepSizeAfter
);
114 void MatchFinder_ReadIfRequired(CMatchFinder
*p
)
116 if (p
->streamEndWasReached
)
118 if (p
->keepSizeAfter
>= p
->streamPos
- p
->pos
)
119 MatchFinder_ReadBlock(p
);
122 static void MatchFinder_CheckAndMoveAndRead(CMatchFinder
*p
)
124 if (MatchFinder_NeedMove(p
))
125 MatchFinder_MoveBlock(p
);
126 MatchFinder_ReadBlock(p
);
129 static void MatchFinder_SetDefaultSettings(CMatchFinder
*p
)
137 #define kCrcPoly 0xEDB88320
139 void MatchFinder_Construct(CMatchFinder
*p
)
142 p
->bufferBase
= NULL
;
145 MatchFinder_SetDefaultSettings(p
);
147 for (i
= 0; i
< 256; i
++)
151 for (j
= 0; j
< 8; j
++)
152 r
= (r
>> 1) ^ (kCrcPoly
& ~((r
& 1) - 1));
157 static void MatchFinder_FreeThisClassMemory(CMatchFinder
*p
, ISzAlloc
*alloc
)
159 alloc
->Free(alloc
, p
->hash
);
163 void MatchFinder_Free(CMatchFinder
*p
, ISzAlloc
*alloc
)
165 MatchFinder_FreeThisClassMemory(p
, alloc
);
166 LzInWindow_Free(p
, alloc
);
169 static CLzRef
* AllocRefs(size_t num
, ISzAlloc
*alloc
)
171 size_t sizeInBytes
= (size_t)num
* sizeof(CLzRef
);
172 if (sizeInBytes
/ sizeof(CLzRef
) != num
)
174 return (CLzRef
*)alloc
->Alloc(alloc
, sizeInBytes
);
177 int MatchFinder_Create(CMatchFinder
*p
, UInt32 historySize
,
178 UInt32 keepAddBufferBefore
, UInt32 matchMaxLen
, UInt32 keepAddBufferAfter
,
183 if (historySize
> kMaxHistorySize
)
185 MatchFinder_Free(p
, alloc
);
189 sizeReserv
= historySize
>> 1;
190 if (historySize
>= ((UInt32
)3 << 30)) sizeReserv
= historySize
>> 3;
191 else if (historySize
>= ((UInt32
)2 << 30)) sizeReserv
= historySize
>> 2;
193 sizeReserv
+= (keepAddBufferBefore
+ matchMaxLen
+ keepAddBufferAfter
) / 2 + (1 << 19);
195 p
->keepSizeBefore
= historySize
+ keepAddBufferBefore
+ 1;
196 p
->keepSizeAfter
= matchMaxLen
+ keepAddBufferAfter
;
198 /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
200 if (LzInWindow_Create(p
, sizeReserv
, alloc
))
202 UInt32 newCyclicBufferSize
= historySize
+ 1;
204 p
->matchMaxLen
= matchMaxLen
;
206 p
->fixedHashSize
= 0;
207 if (p
->numHashBytes
== 2)
211 hs
= historySize
- 1;
217 hs
|= 0xFFFF; /* don't change it! It's required for Deflate */
220 if (p
->numHashBytes
== 3)
224 /* if (bigHash) mode, GetHeads4b() in LzFindMt.c needs (hs >= ((1 << 24) - 1))) */
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
;
238 p
->historySize
= historySize
;
240 p
->cyclicBufferSize
= newCyclicBufferSize
;
242 numSons
= newCyclicBufferSize
;
245 newSize
= hs
+ numSons
;
247 if (p
->hash
&& p
->numRefs
== newSize
)
250 MatchFinder_FreeThisClassMemory(p
, alloc
);
251 p
->numRefs
= newSize
;
252 p
->hash
= AllocRefs(newSize
, alloc
);
256 p
->son
= p
->hash
+ p
->hashSizeSum
;
262 MatchFinder_Free(p
, alloc
);
266 static void MatchFinder_SetLimits(CMatchFinder
*p
)
268 UInt32 limit
= kMaxValForNormalize
- p
->pos
;
269 UInt32 limit2
= p
->cyclicBufferSize
- p
->cyclicBufferPos
;
273 limit2
= p
->streamPos
- p
->pos
;
275 if (limit2
<= p
->keepSizeAfter
)
281 limit2
-= p
->keepSizeAfter
;
287 UInt32 lenLimit
= p
->streamPos
- p
->pos
;
288 if (lenLimit
> p
->matchMaxLen
)
289 lenLimit
= p
->matchMaxLen
;
290 p
->lenLimit
= lenLimit
;
292 p
->posLimit
= p
->pos
+ limit
;
295 void MatchFinder_Init_2(CMatchFinder
*p
, int readData
)
298 UInt32
*hash
= p
->hash
;
299 UInt32 num
= p
->hashSizeSum
;
300 for (i
= 0; i
< num
; i
++)
301 hash
[i
] = kEmptyHashValue
;
303 p
->cyclicBufferPos
= 0;
304 p
->buffer
= p
->bufferBase
;
305 p
->pos
= p
->streamPos
= p
->cyclicBufferSize
;
307 p
->streamEndWasReached
= 0;
310 MatchFinder_ReadBlock(p
);
312 MatchFinder_SetLimits(p
);
315 void MatchFinder_Init(CMatchFinder
*p
)
317 MatchFinder_Init_2(p
, True
);
320 static UInt32
MatchFinder_GetSubValue(CMatchFinder
*p
)
322 return (p
->pos
- p
->historySize
- 1) & kNormalizeMask
;
325 void MatchFinder_Normalize3(UInt32 subValue
, CLzRef
*items
, size_t numItems
)
328 for (i
= 0; i
< numItems
; i
++)
330 UInt32 value
= items
[i
];
331 if (value
<= subValue
)
332 value
= kEmptyHashValue
;
339 static void MatchFinder_Normalize(CMatchFinder
*p
)
341 UInt32 subValue
= MatchFinder_GetSubValue(p
);
342 MatchFinder_Normalize3(subValue
, p
->hash
, p
->numRefs
);
343 MatchFinder_ReduceOffsets(p
, subValue
);
346 static void MatchFinder_CheckLimits(CMatchFinder
*p
)
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
);
357 static 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
)
361 son
[_cyclicBufferPos
] = curMatch
;
364 UInt32 delta
= pos
- curMatch
;
365 if (cutValue
-- == 0 || delta
>= _cyclicBufferSize
)
368 const Byte
*pb
= cur
- delta
;
369 curMatch
= son
[_cyclicBufferPos
- delta
+ ((delta
> _cyclicBufferPos
) ? _cyclicBufferSize
: 0)];
370 if (pb
[maxLen
] == cur
[maxLen
] && *pb
== *cur
)
373 while (++len
!= lenLimit
)
374 if (pb
[len
] != cur
[len
])
378 *distances
++ = maxLen
= len
;
379 *distances
++ = delta
- 1;
388 UInt32
* GetMatchesSpec1(UInt32 lenLimit
, UInt32 curMatch
, UInt32 pos
, const Byte
*cur
, CLzRef
*son
,
389 UInt32 _cyclicBufferPos
, UInt32 _cyclicBufferSize
, UInt32 cutValue
,
390 UInt32
*distances
, UInt32 maxLen
)
392 CLzRef
*ptr0
= son
+ (_cyclicBufferPos
<< 1) + 1;
393 CLzRef
*ptr1
= son
+ (_cyclicBufferPos
<< 1);
394 UInt32 len0
= 0, len1
= 0;
397 UInt32 delta
= pos
- curMatch
;
398 if (cutValue
-- == 0 || delta
>= _cyclicBufferSize
)
400 *ptr0
= *ptr1
= kEmptyHashValue
;
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
])
409 if (++len
!= lenLimit
&& pb
[len
] == cur
[len
])
410 while (++len
!= lenLimit
)
411 if (pb
[len
] != cur
[len
])
415 *distances
++ = maxLen
= len
;
416 *distances
++ = delta
- 1;
425 if (pb
[len
] < cur
[len
])
443 static void SkipMatchesSpec(UInt32 lenLimit
, UInt32 curMatch
, UInt32 pos
, const Byte
*cur
, CLzRef
*son
,
444 UInt32 _cyclicBufferPos
, UInt32 _cyclicBufferSize
, UInt32 cutValue
)
446 CLzRef
*ptr0
= son
+ (_cyclicBufferPos
<< 1) + 1;
447 CLzRef
*ptr1
= son
+ (_cyclicBufferPos
<< 1);
448 UInt32 len0
= 0, len1
= 0;
451 UInt32 delta
= pos
- curMatch
;
452 if (cutValue
-- == 0 || delta
>= _cyclicBufferSize
)
454 *ptr0
= *ptr1
= kEmptyHashValue
;
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
])
463 while (++len
!= lenLimit
)
464 if (pb
[len
] != cur
[len
])
475 if (pb
[len
] < cur
[len
])
494 ++p->cyclicBufferPos; \
496 if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
498 #define MOVE_POS_RET MOVE_POS return offset;
500 static void MatchFinder_MovePos(CMatchFinder
*p
) { MOVE_POS
; }
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; }} \
507 #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
508 #define SKIP_HEADER(minLen) GET_MATCHES_HEADER2(minLen, continue)
510 #define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
512 #define GET_MATCHES_FOOTER(offset, maxLen) \
513 offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
514 distances + offset, maxLen) - distances); MOVE_POS_RET;
516 #define SKIP_FOOTER \
517 SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
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); }
526 static UInt32
Bt2_MatchFinder_GetMatches(CMatchFinder
*p
, UInt32
*distances
)
529 GET_MATCHES_HEADER(2)
531 curMatch
= p
->hash
[hv
];
532 p
->hash
[hv
] = p
->pos
;
534 GET_MATCHES_FOOTER(offset
, 1)
537 UInt32
Bt3Zip_MatchFinder_GetMatches(CMatchFinder
*p
, UInt32
*distances
)
540 GET_MATCHES_HEADER(3)
542 curMatch
= p
->hash
[hv
];
543 p
->hash
[hv
] = p
->pos
;
545 GET_MATCHES_FOOTER(offset
, 2)
548 static UInt32
Bt3_MatchFinder_GetMatches(CMatchFinder
*p
, UInt32
*distances
)
550 UInt32 h2
, d2
, maxLen
, offset
, pos
;
552 GET_MATCHES_HEADER(3)
561 curMatch
= hash
[kFix3HashSize
+ hv
];
564 hash
[kFix3HashSize
+ hv
] = pos
;
569 if (d2
< p
->cyclicBufferSize
&& *(cur
- d2
) == *cur
)
572 distances
[0] = maxLen
;
573 distances
[1] = d2
- 1;
575 if (maxLen
== lenLimit
)
577 SkipMatchesSpec(lenLimit
, curMatch
, MF_PARAMS(p
));
582 GET_MATCHES_FOOTER(offset
, maxLen
)
585 static UInt32
Bt4_MatchFinder_GetMatches(CMatchFinder
*p
, UInt32
*distances
)
587 UInt32 h2
, h3
, d2
, d3
, maxLen
, offset
, pos
;
589 GET_MATCHES_HEADER(4)
596 d2
= pos
- hash
[ h2
];
597 d3
= pos
- hash
[kFix3HashSize
+ h3
];
599 curMatch
= hash
[kFix4HashSize
+ hv
];
602 hash
[kFix3HashSize
+ h3
] = pos
;
603 hash
[kFix4HashSize
+ hv
] = pos
;
608 if (d2
< p
->cyclicBufferSize
&& *(cur
- d2
) == *cur
)
610 distances
[0] = maxLen
= 2;
611 distances
[1] = d2
- 1;
615 if (d2
!= d3
&& d3
< p
->cyclicBufferSize
&& *(cur
- d3
) == *cur
)
618 distances
[offset
+ 1] = d3
- 1;
626 distances
[offset
- 2] = maxLen
;
627 if (maxLen
== lenLimit
)
629 SkipMatchesSpec(lenLimit
, curMatch
, MF_PARAMS(p
));
637 GET_MATCHES_FOOTER(offset
, maxLen
)
641 static UInt32 Bt5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
643 UInt32 h2, h3, h4, d2, d3, d4, maxLen, offset, pos;
645 GET_MATCHES_HEADER(5)
652 d2 = pos - hash[ h2];
653 d3 = pos - hash[kFix3HashSize + h3];
654 d4 = pos - hash[kFix4HashSize + h4];
656 curMatch = hash[kFix5HashSize + hv];
659 hash[kFix3HashSize + h3] = pos;
660 hash[kFix4HashSize + h4] = pos;
661 hash[kFix5HashSize + hv] = pos;
666 if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
668 distances[0] = maxLen = 2;
669 distances[1] = d2 - 1;
671 if (*(cur - d2 + 2) == cur[2])
672 distances[0] = maxLen = 3;
673 else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
675 distances[2] = maxLen = 3;
676 distances[3] = d3 - 1;
681 else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
683 distances[0] = maxLen = 3;
684 distances[1] = d3 - 1;
689 if (d2 != d4 && d4 < p->cyclicBufferSize
690 && *(cur - d4) == *cur
691 && *(cur - d4 + 3) == *(cur + 3))
694 distances[offset + 1] = d4 - 1;
702 distances[offset - 2] = maxLen;
703 if (maxLen == lenLimit)
705 SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
713 GET_MATCHES_FOOTER(offset, maxLen)
717 static UInt32
Hc4_MatchFinder_GetMatches(CMatchFinder
*p
, UInt32
*distances
)
719 UInt32 h2
, h3
, d2
, d3
, maxLen
, offset
, pos
;
721 GET_MATCHES_HEADER(4)
728 d2
= pos
- hash
[ h2
];
729 d3
= pos
- hash
[kFix3HashSize
+ h3
];
731 curMatch
= hash
[kFix4HashSize
+ hv
];
734 hash
[kFix3HashSize
+ h3
] = pos
;
735 hash
[kFix4HashSize
+ hv
] = pos
;
740 if (d2
< p
->cyclicBufferSize
&& *(cur
- d2
) == *cur
)
742 distances
[0] = maxLen
= 2;
743 distances
[1] = d2
- 1;
747 if (d2
!= d3
&& d3
< p
->cyclicBufferSize
&& *(cur
- d3
) == *cur
)
750 distances
[offset
+ 1] = d3
- 1;
758 distances
[offset
- 2] = maxLen
;
759 if (maxLen
== lenLimit
)
761 p
->son
[p
->cyclicBufferPos
] = curMatch
;
769 offset
= (UInt32
)(Hc_GetMatchesSpec(lenLimit
, curMatch
, MF_PARAMS(p
),
770 distances
+ offset
, maxLen
) - (distances
));
775 static UInt32 Hc5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
777 UInt32 h2, h3, h4, d2, d3, d4, maxLen, offset, pos
779 GET_MATCHES_HEADER(5)
786 d2 = pos - hash[ h2];
787 d3 = pos - hash[kFix3HashSize + h3];
788 d4 = pos - hash[kFix4HashSize + h4];
790 curMatch = hash[kFix5HashSize + hv];
793 hash[kFix3HashSize + h3] = pos;
794 hash[kFix4HashSize + h4] = pos;
795 hash[kFix5HashSize + hv] = pos;
800 if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
802 distances[0] = maxLen = 2;
803 distances[1] = d2 - 1;
805 if (*(cur - d2 + 2) == cur[2])
806 distances[0] = maxLen = 3;
807 else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
809 distances[2] = maxLen = 3;
810 distances[3] = d3 - 1;
815 else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
817 distances[0] = maxLen = 3;
818 distances[1] = d3 - 1;
823 if (d2 != d4 && d4 < p->cyclicBufferSize
824 && *(cur - d4) == *cur
825 && *(cur - d4 + 3) == *(cur + 3))
828 distances[offset + 1] = d4 - 1;
836 distances[offset - 2] = maxLen;
837 if (maxLen == lenLimit)
839 p->son[p->cyclicBufferPos] = curMatch;
847 offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
848 distances + offset, maxLen) - (distances));
853 UInt32
Hc3Zip_MatchFinder_GetMatches(CMatchFinder
*p
, UInt32
*distances
)
856 GET_MATCHES_HEADER(3)
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
));
865 static void Bt2_MatchFinder_Skip(CMatchFinder
*p
, UInt32 num
)
871 curMatch
= p
->hash
[hv
];
872 p
->hash
[hv
] = p
->pos
;
878 void Bt3Zip_MatchFinder_Skip(CMatchFinder
*p
, UInt32 num
)
884 curMatch
= p
->hash
[hv
];
885 p
->hash
[hv
] = p
->pos
;
891 static void Bt3_MatchFinder_Skip(CMatchFinder
*p
, UInt32 num
)
900 curMatch
= hash
[kFix3HashSize
+ hv
];
902 hash
[kFix3HashSize
+ hv
] = p
->pos
;
908 static void Bt4_MatchFinder_Skip(CMatchFinder
*p
, UInt32 num
)
917 curMatch
= hash
[kFix4HashSize
+ hv
];
919 hash
[kFix3HashSize
+ h3
] =
920 hash
[kFix4HashSize
+ hv
] = p
->pos
;
927 static void Bt5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
936 curMatch = hash[kFix5HashSize + hv];
938 hash[kFix3HashSize + h3] =
939 hash[kFix4HashSize + h4] =
940 hash[kFix5HashSize + hv] = p->pos;
947 static void Hc4_MatchFinder_Skip(CMatchFinder
*p
, UInt32 num
)
956 curMatch
= hash
[kFix4HashSize
+ hv
];
958 hash
[kFix3HashSize
+ h3
] =
959 hash
[kFix4HashSize
+ hv
] = p
->pos
;
960 p
->son
[p
->cyclicBufferPos
] = curMatch
;
967 static void Hc5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
976 curMatch = p->hash[kFix5HashSize + hv];
978 hash[kFix3HashSize + h3] =
979 hash[kFix4HashSize + h4] =
980 hash[kFix5HashSize + hv] = p->pos;
981 p->son[p->cyclicBufferPos] = curMatch;
988 void Hc3Zip_MatchFinder_Skip(CMatchFinder
*p
, UInt32 num
)
994 curMatch
= p
->hash
[hv
];
995 p
->hash
[hv
] = p
->pos
;
996 p
->son
[p
->cyclicBufferPos
] = curMatch
;
1002 void MatchFinder_CreateVTable(CMatchFinder
*p
, IMatchFinder
*vTable
)
1004 vTable
->Init
= (Mf_Init_Func
)MatchFinder_Init
;
1005 vTable
->GetNumAvailableBytes
= (Mf_GetNumAvailableBytes_Func
)MatchFinder_GetNumAvailableBytes
;
1006 vTable
->GetPointerToCurrentPos
= (Mf_GetPointerToCurrentPos_Func
)MatchFinder_GetPointerToCurrentPos
;
1009 /* if (p->numHashBytes <= 4) */
1011 vTable
->GetMatches
= (Mf_GetMatches_Func
)Hc4_MatchFinder_GetMatches
;
1012 vTable
->Skip
= (Mf_Skip_Func
)Hc4_MatchFinder_Skip
;
1017 vTable->GetMatches = (Mf_GetMatches_Func)Hc5_MatchFinder_GetMatches;
1018 vTable->Skip = (Mf_Skip_Func)Hc5_MatchFinder_Skip;
1022 else if (p
->numHashBytes
== 2)
1024 vTable
->GetMatches
= (Mf_GetMatches_Func
)Bt2_MatchFinder_GetMatches
;
1025 vTable
->Skip
= (Mf_Skip_Func
)Bt2_MatchFinder_Skip
;
1027 else if (p
->numHashBytes
== 3)
1029 vTable
->GetMatches
= (Mf_GetMatches_Func
)Bt3_MatchFinder_GetMatches
;
1030 vTable
->Skip
= (Mf_Skip_Func
)Bt3_MatchFinder_Skip
;
1032 else /* if (p->numHashBytes == 4) */
1034 vTable
->GetMatches
= (Mf_GetMatches_Func
)Bt4_MatchFinder_GetMatches
;
1035 vTable
->Skip
= (Mf_Skip_Func
)Bt4_MatchFinder_Skip
;
1040 vTable->GetMatches = (Mf_GetMatches_Func)Bt5_MatchFinder_GetMatches;
1041 vTable->Skip = (Mf_Skip_Func)Bt5_MatchFinder_Skip;