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