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