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