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