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