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