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