src/third-party/lzma/LzFindMt.c (view raw)
1/* LzFindMt.c -- multithreaded Match finder for LZ algorithms
22014-12-29 : Igor Pavlov : Public domain */
3
4#include "Precomp.h"
5
6#include "LzHash.h"
7
8#include "LzFindMt.h"
9
10void MtSync_Construct(CMtSync *p)
11{
12 p->wasCreated = False;
13 p->csWasInitialized = False;
14 p->csWasEntered = False;
15 Thread_Construct(&p->thread);
16 Event_Construct(&p->canStart);
17 Event_Construct(&p->wasStarted);
18 Event_Construct(&p->wasStopped);
19 Semaphore_Construct(&p->freeSemaphore);
20 Semaphore_Construct(&p->filledSemaphore);
21}
22
23void MtSync_GetNextBlock(CMtSync *p)
24{
25 if (p->needStart)
26 {
27 p->numProcessedBlocks = 1;
28 p->needStart = False;
29 p->stopWriting = False;
30 p->exit = False;
31 Event_Reset(&p->wasStarted);
32 Event_Reset(&p->wasStopped);
33
34 Event_Set(&p->canStart);
35 Event_Wait(&p->wasStarted);
36 }
37 else
38 {
39 CriticalSection_Leave(&p->cs);
40 p->csWasEntered = False;
41 p->numProcessedBlocks++;
42 Semaphore_Release1(&p->freeSemaphore);
43 }
44 Semaphore_Wait(&p->filledSemaphore);
45 CriticalSection_Enter(&p->cs);
46 p->csWasEntered = True;
47}
48
49/* MtSync_StopWriting must be called if Writing was started */
50
51void MtSync_StopWriting(CMtSync *p)
52{
53 UInt32 myNumBlocks = p->numProcessedBlocks;
54 if (!Thread_WasCreated(&p->thread) || p->needStart)
55 return;
56 p->stopWriting = True;
57 if (p->csWasEntered)
58 {
59 CriticalSection_Leave(&p->cs);
60 p->csWasEntered = False;
61 }
62 Semaphore_Release1(&p->freeSemaphore);
63
64 Event_Wait(&p->wasStopped);
65
66 while (myNumBlocks++ != p->numProcessedBlocks)
67 {
68 Semaphore_Wait(&p->filledSemaphore);
69 Semaphore_Release1(&p->freeSemaphore);
70 }
71 p->needStart = True;
72}
73
74void MtSync_Destruct(CMtSync *p)
75{
76 if (Thread_WasCreated(&p->thread))
77 {
78 MtSync_StopWriting(p);
79 p->exit = True;
80 if (p->needStart)
81 Event_Set(&p->canStart);
82 Thread_Wait(&p->thread);
83 Thread_Close(&p->thread);
84 }
85 if (p->csWasInitialized)
86 {
87 CriticalSection_Delete(&p->cs);
88 p->csWasInitialized = False;
89 }
90
91 Event_Close(&p->canStart);
92 Event_Close(&p->wasStarted);
93 Event_Close(&p->wasStopped);
94 Semaphore_Close(&p->freeSemaphore);
95 Semaphore_Close(&p->filledSemaphore);
96
97 p->wasCreated = False;
98}
99
100#define RINOK_THREAD(x) { if ((x) != 0) return SZ_ERROR_THREAD; }
101
102static SRes MtSync_Create2(CMtSync *p, THREAD_FUNC_TYPE startAddress, void *obj, UInt32 numBlocks)
103{
104 if (p->wasCreated)
105 return SZ_OK;
106
107 RINOK_THREAD(CriticalSection_Init(&p->cs));
108 p->csWasInitialized = True;
109
110 RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->canStart));
111 RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->wasStarted));
112 RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->wasStopped));
113
114 RINOK_THREAD(Semaphore_Create(&p->freeSemaphore, numBlocks, numBlocks));
115 RINOK_THREAD(Semaphore_Create(&p->filledSemaphore, 0, numBlocks));
116
117 p->needStart = True;
118
119 RINOK_THREAD(Thread_Create(&p->thread, startAddress, obj));
120 p->wasCreated = True;
121 return SZ_OK;
122}
123
124static SRes MtSync_Create(CMtSync *p, THREAD_FUNC_TYPE startAddress, void *obj, UInt32 numBlocks)
125{
126 SRes res = MtSync_Create2(p, startAddress, obj, numBlocks);
127 if (res != SZ_OK)
128 MtSync_Destruct(p);
129 return res;
130}
131
132void MtSync_Init(CMtSync *p) { p->needStart = True; }
133
134#define kMtMaxValForNormalize 0xFFFFFFFF
135
136#define DEF_GetHeads2(name, v, action) \
137static void GetHeads ## name(const Byte *p, UInt32 pos, \
138UInt32 *hash, UInt32 hashMask, UInt32 *heads, UInt32 numHeads, const UInt32 *crc) \
139{ action; for (; numHeads != 0; numHeads--) { \
140const UInt32 value = (v); p++; *heads++ = pos - hash[value]; hash[value] = pos++; } }
141
142#define DEF_GetHeads(name, v) DEF_GetHeads2(name, v, ;)
143
144DEF_GetHeads2(2, (p[0] | ((UInt32)p[1] << 8)), hashMask = hashMask; crc = crc; )
145DEF_GetHeads(3, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8)) & hashMask)
146DEF_GetHeads(4, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5)) & hashMask)
147DEF_GetHeads(4b, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ ((UInt32)p[3] << 16)) & hashMask)
148/* DEF_GetHeads(5, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5) ^ (crc[p[4]] << 3)) & hashMask) */
149
150void HashThreadFunc(CMatchFinderMt *mt)
151{
152 CMtSync *p = &mt->hashSync;
153 for (;;)
154 {
155 UInt32 numProcessedBlocks = 0;
156 Event_Wait(&p->canStart);
157 Event_Set(&p->wasStarted);
158 for (;;)
159 {
160 if (p->exit)
161 return;
162 if (p->stopWriting)
163 {
164 p->numProcessedBlocks = numProcessedBlocks;
165 Event_Set(&p->wasStopped);
166 break;
167 }
168
169 {
170 CMatchFinder *mf = mt->MatchFinder;
171 if (MatchFinder_NeedMove(mf))
172 {
173 CriticalSection_Enter(&mt->btSync.cs);
174 CriticalSection_Enter(&mt->hashSync.cs);
175 {
176 const Byte *beforePtr = MatchFinder_GetPointerToCurrentPos(mf);
177 const Byte *afterPtr;
178 MatchFinder_MoveBlock(mf);
179 afterPtr = MatchFinder_GetPointerToCurrentPos(mf);
180 mt->pointerToCurPos -= beforePtr - afterPtr;
181 mt->buffer -= beforePtr - afterPtr;
182 }
183 CriticalSection_Leave(&mt->btSync.cs);
184 CriticalSection_Leave(&mt->hashSync.cs);
185 continue;
186 }
187
188 Semaphore_Wait(&p->freeSemaphore);
189
190 MatchFinder_ReadIfRequired(mf);
191 if (mf->pos > (kMtMaxValForNormalize - kMtHashBlockSize))
192 {
193 UInt32 subValue = (mf->pos - mf->historySize - 1);
194 MatchFinder_ReduceOffsets(mf, subValue);
195 MatchFinder_Normalize3(subValue, mf->hash + mf->fixedHashSize, mf->hashMask + 1);
196 }
197 {
198 UInt32 *heads = mt->hashBuf + ((numProcessedBlocks++) & kMtHashNumBlocksMask) * kMtHashBlockSize;
199 UInt32 num = mf->streamPos - mf->pos;
200 heads[0] = 2;
201 heads[1] = num;
202 if (num >= mf->numHashBytes)
203 {
204 num = num - mf->numHashBytes + 1;
205 if (num > kMtHashBlockSize - 2)
206 num = kMtHashBlockSize - 2;
207 mt->GetHeadsFunc(mf->buffer, mf->pos, mf->hash + mf->fixedHashSize, mf->hashMask, heads + 2, num, mf->crc);
208 heads[0] += num;
209 }
210 mf->pos += num;
211 mf->buffer += num;
212 }
213 }
214
215 Semaphore_Release1(&p->filledSemaphore);
216 }
217 }
218}
219
220void MatchFinderMt_GetNextBlock_Hash(CMatchFinderMt *p)
221{
222 MtSync_GetNextBlock(&p->hashSync);
223 p->hashBufPosLimit = p->hashBufPos = ((p->hashSync.numProcessedBlocks - 1) & kMtHashNumBlocksMask) * kMtHashBlockSize;
224 p->hashBufPosLimit += p->hashBuf[p->hashBufPos++];
225 p->hashNumAvail = p->hashBuf[p->hashBufPos++];
226}
227
228#define kEmptyHashValue 0
229
230/* #define MFMT_GM_INLINE */
231
232#ifdef MFMT_GM_INLINE
233
234#define NO_INLINE MY_FAST_CALL
235
236Int32 NO_INLINE GetMatchesSpecN(UInt32 lenLimit, UInt32 pos, const Byte *cur, CLzRef *son,
237 UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 _cutValue,
238 UInt32 *_distances, UInt32 _maxLen, const UInt32 *hash, Int32 limit, UInt32 size, UInt32 *posRes)
239{
240 do
241 {
242 UInt32 *distances = _distances + 1;
243 UInt32 curMatch = pos - *hash++;
244
245 CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
246 CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
247 UInt32 len0 = 0, len1 = 0;
248 UInt32 cutValue = _cutValue;
249 UInt32 maxLen = _maxLen;
250 for (;;)
251 {
252 UInt32 delta = pos - curMatch;
253 if (cutValue-- == 0 || delta >= _cyclicBufferSize)
254 {
255 *ptr0 = *ptr1 = kEmptyHashValue;
256 break;
257 }
258 {
259 CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
260 const Byte *pb = cur - delta;
261 UInt32 len = (len0 < len1 ? len0 : len1);
262 if (pb[len] == cur[len])
263 {
264 if (++len != lenLimit && pb[len] == cur[len])
265 while (++len != lenLimit)
266 if (pb[len] != cur[len])
267 break;
268 if (maxLen < len)
269 {
270 *distances++ = maxLen = len;
271 *distances++ = delta - 1;
272 if (len == lenLimit)
273 {
274 *ptr1 = pair[0];
275 *ptr0 = pair[1];
276 break;
277 }
278 }
279 }
280 if (pb[len] < cur[len])
281 {
282 *ptr1 = curMatch;
283 ptr1 = pair + 1;
284 curMatch = *ptr1;
285 len1 = len;
286 }
287 else
288 {
289 *ptr0 = curMatch;
290 ptr0 = pair;
291 curMatch = *ptr0;
292 len0 = len;
293 }
294 }
295 }
296 pos++;
297 _cyclicBufferPos++;
298 cur++;
299 {
300 UInt32 num = (UInt32)(distances - _distances);
301 *_distances = num - 1;
302 _distances += num;
303 limit -= num;
304 }
305 }
306 while (limit > 0 && --size != 0);
307 *posRes = pos;
308 return limit;
309}
310
311#endif
312
313void BtGetMatches(CMatchFinderMt *p, UInt32 *distances)
314{
315 UInt32 numProcessed = 0;
316 UInt32 curPos = 2;
317 UInt32 limit = kMtBtBlockSize - (p->matchMaxLen * 2);
318 distances[1] = p->hashNumAvail;
319 while (curPos < limit)
320 {
321 if (p->hashBufPos == p->hashBufPosLimit)
322 {
323 MatchFinderMt_GetNextBlock_Hash(p);
324 distances[1] = numProcessed + p->hashNumAvail;
325 if (p->hashNumAvail >= p->numHashBytes)
326 continue;
327 for (; p->hashNumAvail != 0; p->hashNumAvail--)
328 distances[curPos++] = 0;
329 break;
330 }
331 {
332 UInt32 size = p->hashBufPosLimit - p->hashBufPos;
333 UInt32 lenLimit = p->matchMaxLen;
334 UInt32 pos = p->pos;
335 UInt32 cyclicBufferPos = p->cyclicBufferPos;
336 if (lenLimit >= p->hashNumAvail)
337 lenLimit = p->hashNumAvail;
338 {
339 UInt32 size2 = p->hashNumAvail - lenLimit + 1;
340 if (size2 < size)
341 size = size2;
342 size2 = p->cyclicBufferSize - cyclicBufferPos;
343 if (size2 < size)
344 size = size2;
345 }
346 #ifndef MFMT_GM_INLINE
347 while (curPos < limit && size-- != 0)
348 {
349 UInt32 *startDistances = distances + curPos;
350 UInt32 num = (UInt32)(GetMatchesSpec1(lenLimit, pos - p->hashBuf[p->hashBufPos++],
351 pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue,
352 startDistances + 1, p->numHashBytes - 1) - startDistances);
353 *startDistances = num - 1;
354 curPos += num;
355 cyclicBufferPos++;
356 pos++;
357 p->buffer++;
358 }
359 #else
360 {
361 UInt32 posRes;
362 curPos = limit - GetMatchesSpecN(lenLimit, pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue,
363 distances + curPos, p->numHashBytes - 1, p->hashBuf + p->hashBufPos, (Int32)(limit - curPos) , size, &posRes);
364 p->hashBufPos += posRes - pos;
365 cyclicBufferPos += posRes - pos;
366 p->buffer += posRes - pos;
367 pos = posRes;
368 }
369 #endif
370
371 numProcessed += pos - p->pos;
372 p->hashNumAvail -= pos - p->pos;
373 p->pos = pos;
374 if (cyclicBufferPos == p->cyclicBufferSize)
375 cyclicBufferPos = 0;
376 p->cyclicBufferPos = cyclicBufferPos;
377 }
378 }
379 distances[0] = curPos;
380}
381
382void BtFillBlock(CMatchFinderMt *p, UInt32 globalBlockIndex)
383{
384 CMtSync *sync = &p->hashSync;
385 if (!sync->needStart)
386 {
387 CriticalSection_Enter(&sync->cs);
388 sync->csWasEntered = True;
389 }
390
391 BtGetMatches(p, p->btBuf + (globalBlockIndex & kMtBtNumBlocksMask) * kMtBtBlockSize);
392
393 if (p->pos > kMtMaxValForNormalize - kMtBtBlockSize)
394 {
395 UInt32 subValue = p->pos - p->cyclicBufferSize;
396 MatchFinder_Normalize3(subValue, p->son, p->cyclicBufferSize * 2);
397 p->pos -= subValue;
398 }
399
400 if (!sync->needStart)
401 {
402 CriticalSection_Leave(&sync->cs);
403 sync->csWasEntered = False;
404 }
405}
406
407void BtThreadFunc(CMatchFinderMt *mt)
408{
409 CMtSync *p = &mt->btSync;
410 for (;;)
411 {
412 UInt32 blockIndex = 0;
413 Event_Wait(&p->canStart);
414 Event_Set(&p->wasStarted);
415 for (;;)
416 {
417 if (p->exit)
418 return;
419 if (p->stopWriting)
420 {
421 p->numProcessedBlocks = blockIndex;
422 MtSync_StopWriting(&mt->hashSync);
423 Event_Set(&p->wasStopped);
424 break;
425 }
426 Semaphore_Wait(&p->freeSemaphore);
427 BtFillBlock(mt, blockIndex++);
428 Semaphore_Release1(&p->filledSemaphore);
429 }
430 }
431}
432
433void MatchFinderMt_Construct(CMatchFinderMt *p)
434{
435 p->hashBuf = 0;
436 MtSync_Construct(&p->hashSync);
437 MtSync_Construct(&p->btSync);
438}
439
440void MatchFinderMt_FreeMem(CMatchFinderMt *p, ISzAlloc *alloc)
441{
442 alloc->Free(alloc, p->hashBuf);
443 p->hashBuf = 0;
444}
445
446void MatchFinderMt_Destruct(CMatchFinderMt *p, ISzAlloc *alloc)
447{
448 MtSync_Destruct(&p->hashSync);
449 MtSync_Destruct(&p->btSync);
450 MatchFinderMt_FreeMem(p, alloc);
451}
452
453#define kHashBufferSize (kMtHashBlockSize * kMtHashNumBlocks)
454#define kBtBufferSize (kMtBtBlockSize * kMtBtNumBlocks)
455
456static THREAD_FUNC_RET_TYPE THREAD_FUNC_CALL_TYPE HashThreadFunc2(void *p) { HashThreadFunc((CMatchFinderMt *)p); return 0; }
457static THREAD_FUNC_RET_TYPE THREAD_FUNC_CALL_TYPE BtThreadFunc2(void *p)
458{
459 Byte allocaDummy[0x180];
460 allocaDummy[0] = 0;
461 allocaDummy[1] = allocaDummy[0];
462 BtThreadFunc((CMatchFinderMt *)p);
463 return 0;
464}
465
466SRes MatchFinderMt_Create(CMatchFinderMt *p, UInt32 historySize, UInt32 keepAddBufferBefore,
467 UInt32 matchMaxLen, UInt32 keepAddBufferAfter, ISzAlloc *alloc)
468{
469 CMatchFinder *mf = p->MatchFinder;
470 p->historySize = historySize;
471 if (kMtBtBlockSize <= matchMaxLen * 4)
472 return SZ_ERROR_PARAM;
473 if (p->hashBuf == 0)
474 {
475 p->hashBuf = (UInt32 *)alloc->Alloc(alloc, (kHashBufferSize + kBtBufferSize) * sizeof(UInt32));
476 if (p->hashBuf == 0)
477 return SZ_ERROR_MEM;
478 p->btBuf = p->hashBuf + kHashBufferSize;
479 }
480 keepAddBufferBefore += (kHashBufferSize + kBtBufferSize);
481 keepAddBufferAfter += kMtHashBlockSize;
482 if (!MatchFinder_Create(mf, historySize, keepAddBufferBefore, matchMaxLen, keepAddBufferAfter, alloc))
483 return SZ_ERROR_MEM;
484
485 RINOK(MtSync_Create(&p->hashSync, HashThreadFunc2, p, kMtHashNumBlocks));
486 RINOK(MtSync_Create(&p->btSync, BtThreadFunc2, p, kMtBtNumBlocks));
487 return SZ_OK;
488}
489
490/* Call it after ReleaseStream / SetStream */
491void MatchFinderMt_Init(CMatchFinderMt *p)
492{
493 CMatchFinder *mf = p->MatchFinder;
494 p->btBufPos = p->btBufPosLimit = 0;
495 p->hashBufPos = p->hashBufPosLimit = 0;
496 MatchFinder_Init(mf);
497 p->pointerToCurPos = MatchFinder_GetPointerToCurrentPos(mf);
498 p->btNumAvailBytes = 0;
499 p->lzPos = p->historySize + 1;
500
501 p->hash = mf->hash;
502 p->fixedHashSize = mf->fixedHashSize;
503 p->crc = mf->crc;
504
505 p->son = mf->son;
506 p->matchMaxLen = mf->matchMaxLen;
507 p->numHashBytes = mf->numHashBytes;
508 p->pos = mf->pos;
509 p->buffer = mf->buffer;
510 p->cyclicBufferPos = mf->cyclicBufferPos;
511 p->cyclicBufferSize = mf->cyclicBufferSize;
512 p->cutValue = mf->cutValue;
513}
514
515/* ReleaseStream is required to finish multithreading */
516void MatchFinderMt_ReleaseStream(CMatchFinderMt *p)
517{
518 MtSync_StopWriting(&p->btSync);
519 /* p->MatchFinder->ReleaseStream(); */
520}
521
522void MatchFinderMt_Normalize(CMatchFinderMt *p)
523{
524 MatchFinder_Normalize3(p->lzPos - p->historySize - 1, p->hash, p->fixedHashSize);
525 p->lzPos = p->historySize + 1;
526}
527
528void MatchFinderMt_GetNextBlock_Bt(CMatchFinderMt *p)
529{
530 UInt32 blockIndex;
531 MtSync_GetNextBlock(&p->btSync);
532 blockIndex = ((p->btSync.numProcessedBlocks - 1) & kMtBtNumBlocksMask);
533 p->btBufPosLimit = p->btBufPos = blockIndex * kMtBtBlockSize;
534 p->btBufPosLimit += p->btBuf[p->btBufPos++];
535 p->btNumAvailBytes = p->btBuf[p->btBufPos++];
536 if (p->lzPos >= kMtMaxValForNormalize - kMtBtBlockSize)
537 MatchFinderMt_Normalize(p);
538}
539
540const Byte * MatchFinderMt_GetPointerToCurrentPos(CMatchFinderMt *p)
541{
542 return p->pointerToCurPos;
543}
544
545#define GET_NEXT_BLOCK_IF_REQUIRED if (p->btBufPos == p->btBufPosLimit) MatchFinderMt_GetNextBlock_Bt(p);
546
547UInt32 MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt *p)
548{
549 GET_NEXT_BLOCK_IF_REQUIRED;
550 return p->btNumAvailBytes;
551}
552
553Byte MatchFinderMt_GetIndexByte(CMatchFinderMt *p, Int32 index)
554{
555 return p->pointerToCurPos[index];
556}
557
558UInt32 * MixMatches2(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)
559{
560 UInt32 hash2Value, curMatch2;
561 UInt32 *hash = p->hash;
562 const Byte *cur = p->pointerToCurPos;
563 UInt32 lzPos = p->lzPos;
564 MT_HASH2_CALC
565
566 curMatch2 = hash[hash2Value];
567 hash[hash2Value] = lzPos;
568
569 if (curMatch2 >= matchMinPos)
570 if (cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])
571 {
572 *distances++ = 2;
573 *distances++ = lzPos - curMatch2 - 1;
574 }
575 return distances;
576}
577
578UInt32 * MixMatches3(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)
579{
580 UInt32 hash2Value, hash3Value, curMatch2, curMatch3;
581 UInt32 *hash = p->hash;
582 const Byte *cur = p->pointerToCurPos;
583 UInt32 lzPos = p->lzPos;
584 MT_HASH3_CALC
585
586 curMatch2 = hash[ hash2Value];
587 curMatch3 = hash[kFix3HashSize + hash3Value];
588
589 hash[ hash2Value] =
590 hash[kFix3HashSize + hash3Value] =
591 lzPos;
592
593 if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])
594 {
595 distances[1] = lzPos - curMatch2 - 1;
596 if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2])
597 {
598 distances[0] = 3;
599 return distances + 2;
600 }
601 distances[0] = 2;
602 distances += 2;
603 }
604 if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0])
605 {
606 *distances++ = 3;
607 *distances++ = lzPos - curMatch3 - 1;
608 }
609 return distances;
610}
611
612/*
613UInt32 *MixMatches4(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)
614{
615 UInt32 hash2Value, hash3Value, hash4Value, curMatch2, curMatch3, curMatch4;
616 UInt32 *hash = p->hash;
617 const Byte *cur = p->pointerToCurPos;
618 UInt32 lzPos = p->lzPos;
619 MT_HASH4_CALC
620
621 curMatch2 = hash[ hash2Value];
622 curMatch3 = hash[kFix3HashSize + hash3Value];
623 curMatch4 = hash[kFix4HashSize + hash4Value];
624
625 hash[ hash2Value] =
626 hash[kFix3HashSize + hash3Value] =
627 hash[kFix4HashSize + hash4Value] =
628 lzPos;
629
630 if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])
631 {
632 distances[1] = lzPos - curMatch2 - 1;
633 if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2])
634 {
635 distances[0] = (cur[(ptrdiff_t)curMatch2 - lzPos + 3] == cur[3]) ? 4 : 3;
636 return distances + 2;
637 }
638 distances[0] = 2;
639 distances += 2;
640 }
641 if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0])
642 {
643 distances[1] = lzPos - curMatch3 - 1;
644 if (cur[(ptrdiff_t)curMatch3 - lzPos + 3] == cur[3])
645 {
646 distances[0] = 4;
647 return distances + 2;
648 }
649 distances[0] = 3;
650 distances += 2;
651 }
652
653 if (curMatch4 >= matchMinPos)
654 if (
655 cur[(ptrdiff_t)curMatch4 - lzPos] == cur[0] &&
656 cur[(ptrdiff_t)curMatch4 - lzPos + 3] == cur[3]
657 )
658 {
659 *distances++ = 4;
660 *distances++ = lzPos - curMatch4 - 1;
661 }
662 return distances;
663}
664*/
665
666#define INCREASE_LZ_POS p->lzPos++; p->pointerToCurPos++;
667
668UInt32 MatchFinderMt2_GetMatches(CMatchFinderMt *p, UInt32 *distances)
669{
670 const UInt32 *btBuf = p->btBuf + p->btBufPos;
671 UInt32 len = *btBuf++;
672 p->btBufPos += 1 + len;
673 p->btNumAvailBytes--;
674 {
675 UInt32 i;
676 for (i = 0; i < len; i += 2)
677 {
678 *distances++ = *btBuf++;
679 *distances++ = *btBuf++;
680 }
681 }
682 INCREASE_LZ_POS
683 return len;
684}
685
686UInt32 MatchFinderMt_GetMatches(CMatchFinderMt *p, UInt32 *distances)
687{
688 const UInt32 *btBuf = p->btBuf + p->btBufPos;
689 UInt32 len = *btBuf++;
690 p->btBufPos += 1 + len;
691
692 if (len == 0)
693 {
694 if (p->btNumAvailBytes-- >= 4)
695 len = (UInt32)(p->MixMatchesFunc(p, p->lzPos - p->historySize, distances) - (distances));
696 }
697 else
698 {
699 /* Condition: there are matches in btBuf with length < p->numHashBytes */
700 UInt32 *distances2;
701 p->btNumAvailBytes--;
702 distances2 = p->MixMatchesFunc(p, p->lzPos - btBuf[1], distances);
703 do
704 {
705 *distances2++ = *btBuf++;
706 *distances2++ = *btBuf++;
707 }
708 while ((len -= 2) != 0);
709 len = (UInt32)(distances2 - (distances));
710 }
711 INCREASE_LZ_POS
712 return len;
713}
714
715#define SKIP_HEADER2_MT do { GET_NEXT_BLOCK_IF_REQUIRED
716#define SKIP_HEADER_MT(n) SKIP_HEADER2_MT if (p->btNumAvailBytes-- >= (n)) { const Byte *cur = p->pointerToCurPos; UInt32 *hash = p->hash;
717#define SKIP_FOOTER_MT } INCREASE_LZ_POS p->btBufPos += p->btBuf[p->btBufPos] + 1; } while (--num != 0);
718
719void MatchFinderMt0_Skip(CMatchFinderMt *p, UInt32 num)
720{
721 SKIP_HEADER2_MT { p->btNumAvailBytes--;
722 SKIP_FOOTER_MT
723}
724
725void MatchFinderMt2_Skip(CMatchFinderMt *p, UInt32 num)
726{
727 SKIP_HEADER_MT(2)
728 UInt32 hash2Value;
729 MT_HASH2_CALC
730 hash[hash2Value] = p->lzPos;
731 SKIP_FOOTER_MT
732}
733
734void MatchFinderMt3_Skip(CMatchFinderMt *p, UInt32 num)
735{
736 SKIP_HEADER_MT(3)
737 UInt32 hash2Value, hash3Value;
738 MT_HASH3_CALC
739 hash[kFix3HashSize + hash3Value] =
740 hash[ hash2Value] =
741 p->lzPos;
742 SKIP_FOOTER_MT
743}
744
745/*
746void MatchFinderMt4_Skip(CMatchFinderMt *p, UInt32 num)
747{
748 SKIP_HEADER_MT(4)
749 UInt32 hash2Value, hash3Value, hash4Value;
750 MT_HASH4_CALC
751 hash[kFix4HashSize + hash4Value] =
752 hash[kFix3HashSize + hash3Value] =
753 hash[ hash2Value] =
754 p->lzPos;
755 SKIP_FOOTER_MT
756}
757*/
758
759void MatchFinderMt_CreateVTable(CMatchFinderMt *p, IMatchFinder *vTable)
760{
761 vTable->Init = (Mf_Init_Func)MatchFinderMt_Init;
762 vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinderMt_GetIndexByte;
763 vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinderMt_GetNumAvailableBytes;
764 vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinderMt_GetPointerToCurrentPos;
765 vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt_GetMatches;
766 switch(p->MatchFinder->numHashBytes)
767 {
768 case 2:
769 p->GetHeadsFunc = GetHeads2;
770 p->MixMatchesFunc = (Mf_Mix_Matches)0;
771 vTable->Skip = (Mf_Skip_Func)MatchFinderMt0_Skip;
772 vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt2_GetMatches;
773 break;
774 case 3:
775 p->GetHeadsFunc = GetHeads3;
776 p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches2;
777 vTable->Skip = (Mf_Skip_Func)MatchFinderMt2_Skip;
778 break;
779 default:
780 /* case 4: */
781 p->GetHeadsFunc = p->MatchFinder->bigHash ? GetHeads4b : GetHeads4;
782 /* p->GetHeadsFunc = GetHeads4; */
783 p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches3;
784 vTable->Skip = (Mf_Skip_Func)MatchFinderMt3_Skip;
785 break;
786 /*
787 default:
788 p->GetHeadsFunc = GetHeads5;
789 p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches4;
790 vTable->Skip = (Mf_Skip_Func)MatchFinderMt4_Skip;
791 break;
792 */
793 }
794}