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