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}
795