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