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