/src/lzma-fuzz/sdk/C/LzFind.c
Line | Count | Source (jump to first uncovered line) |
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 | 67.5G | #define kEmptyHashValue 0 |
12 | 5.56M | #define kMaxValForNormalize ((UInt32)0xFFFFFFFF) |
13 | 0 | #define kNormalizeStepMin (1 << 10) /* it must be power of 2 */ |
14 | 0 | #define kNormalizeMask (~(UInt32)(kNormalizeStepMin - 1)) |
15 | 23.5k | #define kMaxHistorySize ((UInt32)7 << 29) |
16 | | |
17 | | #define kStartMaxLen 3 |
18 | | |
19 | | static void LzInWindow_Free(CMatchFinder *p, ISzAllocPtr alloc) |
20 | 47.1k | { |
21 | 47.1k | if (!p->directInput) |
22 | 47.1k | { |
23 | 47.1k | ISzAlloc_Free(alloc, p->bufferBase); |
24 | 47.1k | p->bufferBase = NULL; |
25 | 47.1k | } |
26 | 47.1k | } |
27 | | |
28 | | /* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */ |
29 | | |
30 | | static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAllocPtr alloc) |
31 | 23.5k | { |
32 | 23.5k | UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv; |
33 | 23.5k | if (p->directInput) |
34 | 0 | { |
35 | 0 | p->blockSize = blockSize; |
36 | 0 | return 1; |
37 | 0 | } |
38 | 23.5k | if (!p->bufferBase || p->blockSize != blockSize) |
39 | 23.5k | { |
40 | 23.5k | LzInWindow_Free(p, alloc); |
41 | 23.5k | p->blockSize = blockSize; |
42 | 23.5k | p->bufferBase = (Byte *)ISzAlloc_Alloc(alloc, (size_t)blockSize); |
43 | 23.5k | } |
44 | 23.5k | return (p->bufferBase != NULL); |
45 | 23.5k | } |
46 | | |
47 | 585M | Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; } |
48 | | |
49 | 562M | UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; } |
50 | | |
51 | | void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue) |
52 | 0 | { |
53 | 0 | p->posLimit -= subValue; |
54 | 0 | p->pos -= subValue; |
55 | 0 | p->streamPos -= subValue; |
56 | 0 | } |
57 | | |
58 | | static void MatchFinder_ReadBlock(CMatchFinder *p) |
59 | 30.0k | { |
60 | 30.0k | if (p->streamEndWasReached || p->result != SZ_OK) |
61 | 0 | return; |
62 | | |
63 | | /* We use (p->streamPos - p->pos) value. (p->streamPos < p->pos) is allowed. */ |
64 | | |
65 | 30.0k | if (p->directInput) |
66 | 0 | { |
67 | 0 | UInt32 curSize = 0xFFFFFFFF - (p->streamPos - p->pos); |
68 | 0 | if (curSize > p->directInputRem) |
69 | 0 | curSize = (UInt32)p->directInputRem; |
70 | 0 | p->directInputRem -= curSize; |
71 | 0 | p->streamPos += curSize; |
72 | 0 | if (p->directInputRem == 0) |
73 | 0 | p->streamEndWasReached = 1; |
74 | 0 | return; |
75 | 0 | } |
76 | | |
77 | 30.0k | for (;;) |
78 | 48.9k | { |
79 | 48.9k | Byte *dest = p->buffer + (p->streamPos - p->pos); |
80 | 48.9k | size_t size = (p->bufferBase + p->blockSize - dest); |
81 | 48.9k | if (size == 0) |
82 | 0 | return; |
83 | | |
84 | 48.9k | p->result = ISeqInStream_Read(p->stream, dest, &size); |
85 | 48.9k | if (p->result != SZ_OK) |
86 | 0 | return; |
87 | 48.9k | if (size == 0) |
88 | 23.5k | { |
89 | 23.5k | p->streamEndWasReached = 1; |
90 | 23.5k | return; |
91 | 23.5k | } |
92 | 25.4k | p->streamPos += (UInt32)size; |
93 | 25.4k | if (p->streamPos - p->pos > p->keepSizeAfter) |
94 | 6.52k | return; |
95 | 25.4k | } |
96 | 30.0k | } |
97 | | |
98 | | void MatchFinder_MoveBlock(CMatchFinder *p) |
99 | 0 | { |
100 | 0 | memmove(p->bufferBase, |
101 | 0 | p->buffer - p->keepSizeBefore, |
102 | 0 | (size_t)(p->streamPos - p->pos) + p->keepSizeBefore); |
103 | 0 | p->buffer = p->bufferBase + p->keepSizeBefore; |
104 | 0 | } |
105 | | |
106 | | int MatchFinder_NeedMove(CMatchFinder *p) |
107 | 6.52k | { |
108 | 6.52k | if (p->directInput) |
109 | 0 | return 0; |
110 | | /* if (p->streamEndWasReached) return 0; */ |
111 | 6.52k | return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter); |
112 | 6.52k | } |
113 | | |
114 | | void MatchFinder_ReadIfRequired(CMatchFinder *p) |
115 | 0 | { |
116 | 0 | if (p->streamEndWasReached) |
117 | 0 | return; |
118 | 0 | if (p->keepSizeAfter >= p->streamPos - p->pos) |
119 | 0 | MatchFinder_ReadBlock(p); |
120 | 0 | } |
121 | | |
122 | | static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p) |
123 | 6.52k | { |
124 | 6.52k | if (MatchFinder_NeedMove(p)) |
125 | 0 | MatchFinder_MoveBlock(p); |
126 | 6.52k | MatchFinder_ReadBlock(p); |
127 | 6.52k | } |
128 | | |
129 | | static void MatchFinder_SetDefaultSettings(CMatchFinder *p) |
130 | 23.5k | { |
131 | 23.5k | p->cutValue = 32; |
132 | 23.5k | p->btMode = 1; |
133 | 23.5k | p->numHashBytes = 4; |
134 | 23.5k | p->bigHash = 0; |
135 | 23.5k | } |
136 | | |
137 | 48.2M | #define kCrcPoly 0xEDB88320 |
138 | | |
139 | | void MatchFinder_Construct(CMatchFinder *p) |
140 | 23.5k | { |
141 | 23.5k | unsigned i; |
142 | 23.5k | p->bufferBase = NULL; |
143 | 23.5k | p->directInput = 0; |
144 | 23.5k | p->hash = NULL; |
145 | 23.5k | p->expectedDataSize = (UInt64)(Int64)-1; |
146 | 23.5k | MatchFinder_SetDefaultSettings(p); |
147 | | |
148 | 6.05M | for (i = 0; i < 256; i++) |
149 | 6.03M | { |
150 | 6.03M | UInt32 r = (UInt32)i; |
151 | 6.03M | unsigned j; |
152 | 54.2M | for (j = 0; j < 8; j++) |
153 | 48.2M | r = (r >> 1) ^ (kCrcPoly & ((UInt32)0 - (r & 1))); |
154 | 6.03M | p->crc[i] = r; |
155 | 6.03M | } |
156 | 23.5k | } |
157 | | |
158 | | static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAllocPtr alloc) |
159 | 47.1k | { |
160 | 47.1k | ISzAlloc_Free(alloc, p->hash); |
161 | 47.1k | p->hash = NULL; |
162 | 47.1k | } |
163 | | |
164 | | void MatchFinder_Free(CMatchFinder *p, ISzAllocPtr alloc) |
165 | 23.5k | { |
166 | 23.5k | MatchFinder_FreeThisClassMemory(p, alloc); |
167 | 23.5k | LzInWindow_Free(p, alloc); |
168 | 23.5k | } |
169 | | |
170 | | static CLzRef* AllocRefs(size_t num, ISzAllocPtr alloc) |
171 | 23.5k | { |
172 | 23.5k | size_t sizeInBytes = (size_t)num * sizeof(CLzRef); |
173 | 23.5k | if (sizeInBytes / sizeof(CLzRef) != num) |
174 | 0 | return NULL; |
175 | 23.5k | return (CLzRef *)ISzAlloc_Alloc(alloc, sizeInBytes); |
176 | 23.5k | } |
177 | | |
178 | | int MatchFinder_Create(CMatchFinder *p, UInt32 historySize, |
179 | | UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter, |
180 | | ISzAllocPtr alloc) |
181 | 23.5k | { |
182 | 23.5k | UInt32 sizeReserv; |
183 | | |
184 | 23.5k | if (historySize > kMaxHistorySize) |
185 | 0 | { |
186 | 0 | MatchFinder_Free(p, alloc); |
187 | 0 | return 0; |
188 | 0 | } |
189 | | |
190 | 23.5k | sizeReserv = historySize >> 1; |
191 | 23.5k | if (historySize >= ((UInt32)3 << 30)) sizeReserv = historySize >> 3; |
192 | 23.5k | else if (historySize >= ((UInt32)2 << 30)) sizeReserv = historySize >> 2; |
193 | | |
194 | 23.5k | sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19); |
195 | | |
196 | 23.5k | p->keepSizeBefore = historySize + keepAddBufferBefore + 1; |
197 | 23.5k | p->keepSizeAfter = matchMaxLen + keepAddBufferAfter; |
198 | | |
199 | | /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */ |
200 | | |
201 | 23.5k | if (LzInWindow_Create(p, sizeReserv, alloc)) |
202 | 23.5k | { |
203 | 23.5k | UInt32 newCyclicBufferSize = historySize + 1; |
204 | 23.5k | UInt32 hs; |
205 | 23.5k | p->matchMaxLen = matchMaxLen; |
206 | 23.5k | { |
207 | 23.5k | p->fixedHashSize = 0; |
208 | 23.5k | if (p->numHashBytes == 2) |
209 | 7.09k | hs = (1 << 16) - 1; |
210 | 16.4k | else |
211 | 16.4k | { |
212 | 16.4k | hs = historySize; |
213 | 16.4k | if (hs > p->expectedDataSize) |
214 | 8.69k | hs = (UInt32)p->expectedDataSize; |
215 | 16.4k | if (hs != 0) |
216 | 16.4k | hs--; |
217 | 16.4k | hs |= (hs >> 1); |
218 | 16.4k | hs |= (hs >> 2); |
219 | 16.4k | hs |= (hs >> 4); |
220 | 16.4k | hs |= (hs >> 8); |
221 | 16.4k | hs >>= 1; |
222 | 16.4k | hs |= 0xFFFF; /* don't change it! It's required for Deflate */ |
223 | 16.4k | if (hs > (1 << 24)) |
224 | 0 | { |
225 | 0 | if (p->numHashBytes == 3) |
226 | 0 | hs = (1 << 24) - 1; |
227 | 0 | else |
228 | 0 | hs >>= 1; |
229 | | /* if (bigHash) mode, GetHeads4b() in LzFindMt.c needs (hs >= ((1 << 24) - 1))) */ |
230 | 0 | } |
231 | 16.4k | } |
232 | 23.5k | p->hashMask = hs; |
233 | 23.5k | hs++; |
234 | 23.5k | if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size; |
235 | 23.5k | if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size; |
236 | 23.5k | if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size; |
237 | 23.5k | hs += p->fixedHashSize; |
238 | 23.5k | } |
239 | | |
240 | 23.5k | { |
241 | 23.5k | size_t newSize; |
242 | 23.5k | size_t numSons; |
243 | 23.5k | p->historySize = historySize; |
244 | 23.5k | p->hashSizeSum = hs; |
245 | 23.5k | p->cyclicBufferSize = newCyclicBufferSize; |
246 | | |
247 | 23.5k | numSons = newCyclicBufferSize; |
248 | 23.5k | if (p->btMode) |
249 | 20.7k | numSons <<= 1; |
250 | 23.5k | newSize = hs + numSons; |
251 | | |
252 | 23.5k | if (p->hash && p->numRefs == newSize) |
253 | 0 | return 1; |
254 | | |
255 | 23.5k | MatchFinder_FreeThisClassMemory(p, alloc); |
256 | 23.5k | p->numRefs = newSize; |
257 | 23.5k | p->hash = AllocRefs(newSize, alloc); |
258 | | |
259 | 23.5k | if (p->hash) |
260 | 23.5k | { |
261 | 23.5k | p->son = p->hash + p->hashSizeSum; |
262 | 23.5k | return 1; |
263 | 23.5k | } |
264 | 23.5k | } |
265 | 23.5k | } |
266 | | |
267 | 0 | MatchFinder_Free(p, alloc); |
268 | 0 | return 0; |
269 | 23.5k | } |
270 | | |
271 | | static void MatchFinder_SetLimits(CMatchFinder *p) |
272 | 2.79M | { |
273 | 2.79M | UInt32 limit = kMaxValForNormalize - p->pos; |
274 | 2.79M | UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos; |
275 | | |
276 | 2.79M | if (limit2 < limit) |
277 | 2.79M | limit = limit2; |
278 | 2.79M | limit2 = p->streamPos - p->pos; |
279 | | |
280 | 2.79M | if (limit2 <= p->keepSizeAfter) |
281 | 2.78M | { |
282 | 2.78M | if (limit2 > 0) |
283 | 2.76M | limit2 = 1; |
284 | 2.78M | } |
285 | 6.52k | else |
286 | 6.52k | limit2 -= p->keepSizeAfter; |
287 | | |
288 | 2.79M | if (limit2 < limit) |
289 | 2.79M | limit = limit2; |
290 | | |
291 | 2.79M | { |
292 | 2.79M | UInt32 lenLimit = p->streamPos - p->pos; |
293 | 2.79M | if (lenLimit > p->matchMaxLen) |
294 | 1.94M | lenLimit = p->matchMaxLen; |
295 | 2.79M | p->lenLimit = lenLimit; |
296 | 2.79M | } |
297 | 2.79M | p->posLimit = p->pos + limit; |
298 | 2.79M | } |
299 | | |
300 | | |
301 | | void MatchFinder_Init_LowHash(CMatchFinder *p) |
302 | 23.5k | { |
303 | 23.5k | size_t i; |
304 | 23.5k | CLzRef *items = p->hash; |
305 | 23.5k | size_t numItems = p->fixedHashSize; |
306 | 891M | for (i = 0; i < numItems; i++) |
307 | 891M | items[i] = kEmptyHashValue; |
308 | 23.5k | } |
309 | | |
310 | | |
311 | | void MatchFinder_Init_HighHash(CMatchFinder *p) |
312 | 23.5k | { |
313 | 23.5k | size_t i; |
314 | 23.5k | CLzRef *items = p->hash + p->fixedHashSize; |
315 | 23.5k | size_t numItems = (size_t)p->hashMask + 1; |
316 | 66.2G | for (i = 0; i < numItems; i++) |
317 | 66.2G | items[i] = kEmptyHashValue; |
318 | 23.5k | } |
319 | | |
320 | | |
321 | | void MatchFinder_Init_3(CMatchFinder *p, int readData) |
322 | 23.5k | { |
323 | 23.5k | p->cyclicBufferPos = 0; |
324 | 23.5k | p->buffer = p->bufferBase; |
325 | 23.5k | p->pos = |
326 | 23.5k | p->streamPos = p->cyclicBufferSize; |
327 | 23.5k | p->result = SZ_OK; |
328 | 23.5k | p->streamEndWasReached = 0; |
329 | | |
330 | 23.5k | if (readData) |
331 | 23.5k | MatchFinder_ReadBlock(p); |
332 | | |
333 | 23.5k | MatchFinder_SetLimits(p); |
334 | 23.5k | } |
335 | | |
336 | | |
337 | | void MatchFinder_Init(CMatchFinder *p) |
338 | 23.5k | { |
339 | 23.5k | MatchFinder_Init_HighHash(p); |
340 | 23.5k | MatchFinder_Init_LowHash(p); |
341 | 23.5k | MatchFinder_Init_3(p, True); |
342 | 23.5k | } |
343 | | |
344 | | |
345 | | static UInt32 MatchFinder_GetSubValue(CMatchFinder *p) |
346 | 0 | { |
347 | 0 | return (p->pos - p->historySize - 1) & kNormalizeMask; |
348 | 0 | } |
349 | | |
350 | | void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, size_t numItems) |
351 | 0 | { |
352 | 0 | size_t i; |
353 | 0 | for (i = 0; i < numItems; i++) |
354 | 0 | { |
355 | 0 | UInt32 value = items[i]; |
356 | 0 | if (value <= subValue) |
357 | 0 | value = kEmptyHashValue; |
358 | 0 | else |
359 | 0 | value -= subValue; |
360 | 0 | items[i] = value; |
361 | 0 | } |
362 | 0 | } |
363 | | |
364 | | static void MatchFinder_Normalize(CMatchFinder *p) |
365 | 0 | { |
366 | 0 | UInt32 subValue = MatchFinder_GetSubValue(p); |
367 | 0 | MatchFinder_Normalize3(subValue, p->hash, p->numRefs); |
368 | 0 | MatchFinder_ReduceOffsets(p, subValue); |
369 | 0 | } |
370 | | |
371 | | |
372 | | MY_NO_INLINE |
373 | | static void MatchFinder_CheckLimits(CMatchFinder *p) |
374 | 2.77M | { |
375 | 2.77M | if (p->pos == kMaxValForNormalize) |
376 | 0 | MatchFinder_Normalize(p); |
377 | 2.77M | if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos) |
378 | 6.52k | MatchFinder_CheckAndMoveAndRead(p); |
379 | 2.77M | if (p->cyclicBufferPos == p->cyclicBufferSize) |
380 | 0 | p->cyclicBufferPos = 0; |
381 | 2.77M | MatchFinder_SetLimits(p); |
382 | 2.77M | } |
383 | | |
384 | | |
385 | | /* |
386 | | (lenLimit > maxLen) |
387 | | */ |
388 | | MY_FORCE_INLINE |
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 | 1.52M | { |
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 | 1.52M | const Byte *lim = cur + lenLimit; |
423 | 1.52M | son[_cyclicBufferPos] = curMatch; |
424 | 1.52M | do |
425 | 8.29M | { |
426 | 8.29M | UInt32 delta = pos - curMatch; |
427 | 8.29M | if (delta >= _cyclicBufferSize) |
428 | 1.17M | break; |
429 | 7.11M | { |
430 | 7.11M | ptrdiff_t diff; |
431 | 7.11M | curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)]; |
432 | 7.11M | diff = (ptrdiff_t)0 - delta; |
433 | 7.11M | if (cur[maxLen] == cur[maxLen + diff]) |
434 | 1.02M | { |
435 | 1.02M | const Byte *c = cur; |
436 | 13.7M | while (*c == c[diff]) |
437 | 12.7M | { |
438 | 12.7M | if (++c == lim) |
439 | 34.2k | { |
440 | 34.2k | distances[0] = (UInt32)(lim - cur); |
441 | 34.2k | distances[1] = delta - 1; |
442 | 34.2k | return distances + 2; |
443 | 34.2k | } |
444 | 12.7M | } |
445 | 990k | { |
446 | 990k | unsigned len = (unsigned)(c - cur); |
447 | 990k | if (maxLen < len) |
448 | 226k | { |
449 | 226k | maxLen = len; |
450 | 226k | distances[0] = (UInt32)len; |
451 | 226k | distances[1] = delta - 1; |
452 | 226k | distances += 2; |
453 | 226k | } |
454 | 990k | } |
455 | 990k | } |
456 | 7.11M | } |
457 | 7.11M | } |
458 | 7.07M | while (--cutValue); |
459 | | |
460 | 1.48M | return distances; |
461 | 1.52M | } |
462 | | |
463 | | |
464 | | MY_FORCE_INLINE |
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 | 328M | { |
469 | 328M | CLzRef *ptr0 = son + ((size_t)_cyclicBufferPos << 1) + 1; |
470 | 328M | CLzRef *ptr1 = son + ((size_t)_cyclicBufferPos << 1); |
471 | 328M | unsigned len0 = 0, len1 = 0; |
472 | 328M | for (;;) |
473 | 658M | { |
474 | 658M | UInt32 delta = pos - curMatch; |
475 | 658M | if (cutValue-- == 0 || delta >= _cyclicBufferSize) |
476 | 327M | { |
477 | 327M | *ptr0 = *ptr1 = kEmptyHashValue; |
478 | 327M | return distances; |
479 | 327M | } |
480 | 330M | { |
481 | 330M | CLzRef *pair = son + ((size_t)(_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1); |
482 | 330M | const Byte *pb = cur - delta; |
483 | 330M | unsigned len = (len0 < len1 ? len0 : len1); |
484 | 330M | UInt32 pair0 = pair[0]; |
485 | 330M | if (pb[len] == cur[len]) |
486 | 138M | { |
487 | 138M | if (++len != lenLimit && pb[len] == cur[len]) |
488 | 693M | while (++len != lenLimit) |
489 | 693M | if (pb[len] != cur[len]) |
490 | 114M | break; |
491 | 138M | if (maxLen < len) |
492 | 46.7M | { |
493 | 46.7M | maxLen = (UInt32)len; |
494 | 46.7M | *distances++ = (UInt32)len; |
495 | 46.7M | *distances++ = delta - 1; |
496 | 46.7M | if (len == lenLimit) |
497 | 597k | { |
498 | 597k | *ptr1 = pair0; |
499 | 597k | *ptr0 = pair[1]; |
500 | 597k | return distances; |
501 | 597k | } |
502 | 46.7M | } |
503 | 138M | } |
504 | 330M | if (pb[len] < cur[len]) |
505 | 110M | { |
506 | 110M | *ptr1 = curMatch; |
507 | 110M | ptr1 = pair + 1; |
508 | 110M | curMatch = *ptr1; |
509 | 110M | len1 = len; |
510 | 110M | } |
511 | 219M | else |
512 | 219M | { |
513 | 219M | *ptr0 = curMatch; |
514 | 219M | ptr0 = pair; |
515 | 219M | curMatch = *ptr0; |
516 | 219M | len0 = len; |
517 | 219M | } |
518 | 330M | } |
519 | 330M | } |
520 | 328M | } |
521 | | |
522 | | static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son, |
523 | | UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue) |
524 | 147M | { |
525 | 147M | CLzRef *ptr0 = son + ((size_t)_cyclicBufferPos << 1) + 1; |
526 | 147M | CLzRef *ptr1 = son + ((size_t)_cyclicBufferPos << 1); |
527 | 147M | unsigned len0 = 0, len1 = 0; |
528 | 147M | for (;;) |
529 | 544M | { |
530 | 544M | UInt32 delta = pos - curMatch; |
531 | 544M | if (cutValue-- == 0 || delta >= _cyclicBufferSize) |
532 | 21.6M | { |
533 | 21.6M | *ptr0 = *ptr1 = kEmptyHashValue; |
534 | 21.6M | return; |
535 | 21.6M | } |
536 | 522M | { |
537 | 522M | CLzRef *pair = son + ((size_t)(_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1); |
538 | 522M | const Byte *pb = cur - delta; |
539 | 522M | unsigned len = (len0 < len1 ? len0 : len1); |
540 | 522M | if (pb[len] == cur[len]) |
541 | 355M | { |
542 | 5.52G | while (++len != lenLimit) |
543 | 5.39G | if (pb[len] != cur[len]) |
544 | 228M | break; |
545 | 355M | { |
546 | 355M | if (len == lenLimit) |
547 | 126M | { |
548 | 126M | *ptr1 = pair[0]; |
549 | 126M | *ptr0 = pair[1]; |
550 | 126M | return; |
551 | 126M | } |
552 | 355M | } |
553 | 355M | } |
554 | 396M | if (pb[len] < cur[len]) |
555 | 119M | { |
556 | 119M | *ptr1 = curMatch; |
557 | 119M | ptr1 = pair + 1; |
558 | 119M | curMatch = *ptr1; |
559 | 119M | len1 = len; |
560 | 119M | } |
561 | 277M | else |
562 | 277M | { |
563 | 277M | *ptr0 = curMatch; |
564 | 277M | ptr0 = pair; |
565 | 277M | curMatch = *ptr0; |
566 | 277M | len0 = len; |
567 | 277M | } |
568 | 396M | } |
569 | 396M | } |
570 | 147M | } |
571 | | |
572 | | #define MOVE_POS \ |
573 | 480M | ++p->cyclicBufferPos; \ |
574 | 480M | p->buffer++; \ |
575 | 480M | if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p); |
576 | | |
577 | 330M | #define MOVE_POS_RET MOVE_POS return (UInt32)offset; |
578 | | |
579 | 53.1k | static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; } |
580 | | |
581 | | #define GET_MATCHES_HEADER2(minLen, ret_op) \ |
582 | 480M | unsigned lenLimit; UInt32 hv; const Byte *cur; UInt32 curMatch; \ |
583 | 480M | lenLimit = (unsigned)p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \ |
584 | 480M | cur = p->buffer; |
585 | | |
586 | 330M | #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0) |
587 | 150M | #define SKIP_HEADER(minLen) GET_MATCHES_HEADER2(minLen, continue) |
588 | | |
589 | 477M | #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 | 328M | offset = (unsigned)(GetMatchesSpec1((UInt32)lenLimit, curMatch, MF_PARAMS(p), \ |
593 | 328M | distances + offset, (UInt32)maxLen) - distances); MOVE_POS_RET; |
594 | | |
595 | | #define SKIP_FOOTER \ |
596 | 147M | SkipMatchesSpec((UInt32)lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS; |
597 | | |
598 | 79.3M | #define UPDATE_maxLen { \ |
599 | 79.3M | ptrdiff_t diff = (ptrdiff_t)0 - d2; \ |
600 | 79.3M | const Byte *c = cur + maxLen; \ |
601 | 79.3M | const Byte *lim = cur + lenLimit; \ |
602 | 242M | for (; c != lim; c++) if (*(c + diff) != *c) break; \ |
603 | 79.3M | maxLen = (unsigned)(c - cur); } |
604 | | |
605 | | static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances) |
606 | 10.0M | { |
607 | 10.0M | unsigned offset; |
608 | 10.0M | GET_MATCHES_HEADER(2) |
609 | 10.0M | HASH2_CALC; |
610 | 10.0M | curMatch = p->hash[hv]; |
611 | 10.0M | p->hash[hv] = p->pos; |
612 | 10.0M | offset = 0; |
613 | 10.0M | GET_MATCHES_FOOTER(offset, 1) |
614 | 0 | } |
615 | | |
616 | | UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances) |
617 | 0 | { |
618 | 0 | unsigned offset; |
619 | 0 | GET_MATCHES_HEADER(3) |
620 | 0 | HASH_ZIP_CALC; |
621 | 0 | curMatch = p->hash[hv]; |
622 | 0 | p->hash[hv] = p->pos; |
623 | 0 | offset = 0; |
624 | 0 | GET_MATCHES_FOOTER(offset, 2) |
625 | 0 | } |
626 | | |
627 | | static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances) |
628 | 3.98M | { |
629 | 3.98M | UInt32 h2, d2, pos; |
630 | 3.98M | unsigned maxLen, offset; |
631 | 3.98M | UInt32 *hash; |
632 | 3.98M | GET_MATCHES_HEADER(3) |
633 | | |
634 | 3.97M | HASH3_CALC; |
635 | | |
636 | 3.97M | hash = p->hash; |
637 | 3.97M | pos = p->pos; |
638 | | |
639 | 3.97M | d2 = pos - hash[h2]; |
640 | | |
641 | 3.97M | curMatch = (hash + kFix3HashSize)[hv]; |
642 | | |
643 | 3.97M | hash[h2] = pos; |
644 | 3.97M | (hash + kFix3HashSize)[hv] = pos; |
645 | | |
646 | 3.97M | maxLen = 2; |
647 | 3.97M | offset = 0; |
648 | | |
649 | 3.97M | if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur) |
650 | 1.44M | { |
651 | 1.44M | UPDATE_maxLen |
652 | 1.44M | distances[0] = (UInt32)maxLen; |
653 | 1.44M | distances[1] = d2 - 1; |
654 | 1.44M | offset = 2; |
655 | 1.44M | if (maxLen == lenLimit) |
656 | 25.2k | { |
657 | 25.2k | SkipMatchesSpec((UInt32)lenLimit, curMatch, MF_PARAMS(p)); |
658 | 25.2k | MOVE_POS_RET; |
659 | 0 | } |
660 | 1.44M | } |
661 | | |
662 | 3.95M | GET_MATCHES_FOOTER(offset, maxLen) |
663 | 0 | } |
664 | | |
665 | | static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances) |
666 | 314M | { |
667 | 314M | UInt32 h2, h3, d2, d3, pos; |
668 | 314M | unsigned maxLen, offset; |
669 | 314M | UInt32 *hash; |
670 | 314M | GET_MATCHES_HEADER(4) |
671 | | |
672 | 314M | HASH4_CALC; |
673 | | |
674 | 314M | hash = p->hash; |
675 | 314M | pos = p->pos; |
676 | | |
677 | 314M | d2 = pos - hash [h2]; |
678 | 314M | d3 = pos - (hash + kFix3HashSize)[h3]; |
679 | | |
680 | 314M | curMatch = (hash + kFix4HashSize)[hv]; |
681 | | |
682 | 314M | hash [h2] = pos; |
683 | 314M | (hash + kFix3HashSize)[h3] = pos; |
684 | 314M | (hash + kFix4HashSize)[hv] = pos; |
685 | | |
686 | 314M | maxLen = 0; |
687 | 314M | offset = 0; |
688 | | |
689 | 314M | if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur) |
690 | 63.0M | { |
691 | 63.0M | maxLen = 2; |
692 | 63.0M | distances[0] = 2; |
693 | 63.0M | distances[1] = d2 - 1; |
694 | 63.0M | offset = 2; |
695 | 63.0M | } |
696 | | |
697 | 314M | if (d2 != d3 && d3 < p->cyclicBufferSize && *(cur - d3) == *cur) |
698 | 33.9M | { |
699 | 33.9M | maxLen = 3; |
700 | 33.9M | distances[(size_t)offset + 1] = d3 - 1; |
701 | 33.9M | offset += 2; |
702 | 33.9M | d2 = d3; |
703 | 33.9M | } |
704 | | |
705 | 314M | if (offset != 0) |
706 | 77.3M | { |
707 | 77.3M | UPDATE_maxLen |
708 | 77.3M | distances[(size_t)offset - 2] = (UInt32)maxLen; |
709 | 77.3M | if (maxLen == lenLimit) |
710 | 568k | { |
711 | 568k | SkipMatchesSpec((UInt32)lenLimit, curMatch, MF_PARAMS(p)); |
712 | 568k | MOVE_POS_RET; |
713 | 0 | } |
714 | 77.3M | } |
715 | | |
716 | 314M | if (maxLen < 3) |
717 | 254M | maxLen = 3; |
718 | | |
719 | 314M | GET_MATCHES_FOOTER(offset, maxLen) |
720 | 0 | } |
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 | | |
799 | | static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances) |
800 | 1.58M | { |
801 | 1.58M | UInt32 h2, h3, d2, d3, pos; |
802 | 1.58M | unsigned maxLen, offset; |
803 | 1.58M | UInt32 *hash; |
804 | 1.58M | GET_MATCHES_HEADER(4) |
805 | | |
806 | 1.58M | HASH4_CALC; |
807 | | |
808 | 1.58M | hash = p->hash; |
809 | 1.58M | pos = p->pos; |
810 | | |
811 | 1.58M | d2 = pos - hash [h2]; |
812 | 1.58M | d3 = pos - (hash + kFix3HashSize)[h3]; |
813 | 1.58M | curMatch = (hash + kFix4HashSize)[hv]; |
814 | | |
815 | 1.58M | hash [h2] = pos; |
816 | 1.58M | (hash + kFix3HashSize)[h3] = pos; |
817 | 1.58M | (hash + kFix4HashSize)[hv] = pos; |
818 | | |
819 | 1.58M | maxLen = 0; |
820 | 1.58M | offset = 0; |
821 | | |
822 | 1.58M | if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur) |
823 | 593k | { |
824 | 593k | maxLen = 2; |
825 | 593k | distances[0] = 2; |
826 | 593k | distances[1] = d2 - 1; |
827 | 593k | offset = 2; |
828 | 593k | } |
829 | | |
830 | 1.58M | if (d2 != d3 && d3 < p->cyclicBufferSize && *(cur - d3) == *cur) |
831 | 251k | { |
832 | 251k | maxLen = 3; |
833 | 251k | distances[(size_t)offset + 1] = d3 - 1; |
834 | 251k | offset += 2; |
835 | 251k | d2 = d3; |
836 | 251k | } |
837 | | |
838 | 1.58M | if (offset != 0) |
839 | 627k | { |
840 | 627k | UPDATE_maxLen |
841 | 627k | distances[(size_t)offset - 2] = (UInt32)maxLen; |
842 | 627k | if (maxLen == lenLimit) |
843 | 59.8k | { |
844 | 59.8k | p->son[p->cyclicBufferPos] = curMatch; |
845 | 59.8k | MOVE_POS_RET; |
846 | 0 | } |
847 | 627k | } |
848 | | |
849 | 1.52M | if (maxLen < 3) |
850 | 1.06M | maxLen = 3; |
851 | | |
852 | 1.52M | offset = (unsigned)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p), |
853 | 1.52M | distances + offset, maxLen) - (distances)); |
854 | 1.52M | MOVE_POS_RET |
855 | 1.58M | } |
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 | | |
936 | | UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances) |
937 | 0 | { |
938 | 0 | unsigned offset; |
939 | 0 | GET_MATCHES_HEADER(3) |
940 | 0 | HASH_ZIP_CALC; |
941 | 0 | curMatch = p->hash[hv]; |
942 | 0 | p->hash[hv] = p->pos; |
943 | 0 | offset = (unsigned)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p), |
944 | 0 | distances, 2) - (distances)); |
945 | 0 | MOVE_POS_RET |
946 | 0 | } |
947 | | |
948 | | static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num) |
949 | 246k | { |
950 | 246k | do |
951 | 5.61M | { |
952 | 5.61M | SKIP_HEADER(2) |
953 | 5.61M | HASH2_CALC; |
954 | 5.61M | curMatch = p->hash[hv]; |
955 | 5.61M | p->hash[hv] = p->pos; |
956 | 5.61M | SKIP_FOOTER |
957 | 5.61M | } |
958 | 5.61M | while (--num != 0); |
959 | 246k | } |
960 | | |
961 | | void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num) |
962 | 0 | { |
963 | 0 | do |
964 | 0 | { |
965 | 0 | SKIP_HEADER(3) |
966 | 0 | HASH_ZIP_CALC; |
967 | 0 | curMatch = p->hash[hv]; |
968 | 0 | p->hash[hv] = p->pos; |
969 | 0 | SKIP_FOOTER |
970 | 0 | } |
971 | 0 | while (--num != 0); |
972 | 0 | } |
973 | | |
974 | | static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num) |
975 | 152k | { |
976 | 152k | do |
977 | 5.89M | { |
978 | 5.89M | UInt32 h2; |
979 | 5.89M | UInt32 *hash; |
980 | 5.89M | SKIP_HEADER(3) |
981 | 5.89M | HASH3_CALC; |
982 | 5.89M | hash = p->hash; |
983 | 5.89M | curMatch = (hash + kFix3HashSize)[hv]; |
984 | 5.89M | hash[h2] = |
985 | 5.89M | (hash + kFix3HashSize)[hv] = p->pos; |
986 | 5.89M | SKIP_FOOTER |
987 | 5.89M | } |
988 | 5.89M | while (--num != 0); |
989 | 152k | } |
990 | | |
991 | | static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num) |
992 | 1.00M | { |
993 | 1.00M | do |
994 | 135M | { |
995 | 135M | UInt32 h2, h3; |
996 | 135M | UInt32 *hash; |
997 | 135M | SKIP_HEADER(4) |
998 | 135M | HASH4_CALC; |
999 | 135M | hash = p->hash; |
1000 | 135M | curMatch = (hash + kFix4HashSize)[hv]; |
1001 | 135M | hash [h2] = |
1002 | 135M | (hash + kFix3HashSize)[h3] = |
1003 | 135M | (hash + kFix4HashSize)[hv] = p->pos; |
1004 | 135M | SKIP_FOOTER |
1005 | 135M | } |
1006 | 135M | while (--num != 0); |
1007 | 1.00M | } |
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 | | |
1030 | | static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num) |
1031 | 140k | { |
1032 | 140k | do |
1033 | 3.21M | { |
1034 | 3.21M | UInt32 h2, h3; |
1035 | 3.21M | UInt32 *hash; |
1036 | 3.21M | SKIP_HEADER(4) |
1037 | 3.21M | HASH4_CALC; |
1038 | 3.21M | hash = p->hash; |
1039 | 3.21M | curMatch = (hash + kFix4HashSize)[hv]; |
1040 | 3.21M | hash [h2] = |
1041 | 3.21M | (hash + kFix3HashSize)[h3] = |
1042 | 3.21M | (hash + kFix4HashSize)[hv] = p->pos; |
1043 | 3.21M | p->son[p->cyclicBufferPos] = curMatch; |
1044 | 3.21M | MOVE_POS |
1045 | 3.21M | } |
1046 | 3.21M | while (--num != 0); |
1047 | 140k | } |
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 | | |
1071 | | void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num) |
1072 | 0 | { |
1073 | 0 | do |
1074 | 0 | { |
1075 | 0 | SKIP_HEADER(3) |
1076 | 0 | HASH_ZIP_CALC; |
1077 | 0 | curMatch = p->hash[hv]; |
1078 | 0 | p->hash[hv] = p->pos; |
1079 | 0 | p->son[p->cyclicBufferPos] = curMatch; |
1080 | 0 | MOVE_POS |
1081 | 0 | } |
1082 | 0 | while (--num != 0); |
1083 | 0 | } |
1084 | | |
1085 | | void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable) |
1086 | 23.5k | { |
1087 | 23.5k | vTable->Init = (Mf_Init_Func)MatchFinder_Init; |
1088 | 23.5k | vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes; |
1089 | 23.5k | vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos; |
1090 | 23.5k | if (!p->btMode) |
1091 | 2.82k | { |
1092 | | /* if (p->numHashBytes <= 4) */ |
1093 | 2.82k | { |
1094 | 2.82k | vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches; |
1095 | 2.82k | vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip; |
1096 | 2.82k | } |
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 | 2.82k | } |
1105 | 20.7k | else if (p->numHashBytes == 2) |
1106 | 7.09k | { |
1107 | 7.09k | vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches; |
1108 | 7.09k | vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip; |
1109 | 7.09k | } |
1110 | 13.6k | else if (p->numHashBytes == 3) |
1111 | 3.13k | { |
1112 | 3.13k | vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches; |
1113 | 3.13k | vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip; |
1114 | 3.13k | } |
1115 | 10.5k | else /* if (p->numHashBytes == 4) */ |
1116 | 10.5k | { |
1117 | 10.5k | vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches; |
1118 | 10.5k | vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip; |
1119 | 10.5k | } |
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 | 23.5k | } |