1 /* LzFindMt.c -- multithreaded Match finder for LZ algorithms
2 2015-10-15 : Igor Pavlov : Public domain */
3
4 #include "Precomp.h"
5
6 #include "LzHash.h"
7
8 #include "LzFindMt.h"
9
MtSync_Construct(CMtSync * p)10 static void 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
MtSync_GetNextBlock(CMtSync * p)23 static void 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
MtSync_StopWriting(CMtSync * p)51 static void 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
MtSync_Destruct(CMtSync * p)74 static void 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
MtSync_Create2(CMtSync * p,THREAD_FUNC_TYPE startAddress,void * obj,UInt32 numBlocks)102 static 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
MtSync_Create(CMtSync * p,THREAD_FUNC_TYPE startAddress,void * obj,UInt32 numBlocks)124 static 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
MtSync_Init(CMtSync * p)132 void MtSync_Init(CMtSync *p) { p->needStart = True; }
133
134 #define kMtMaxValForNormalize 0xFFFFFFFF
135
136 #define DEF_GetHeads2(name, v, action) \
137 static void GetHeads ## name(const Byte *p, UInt32 pos, \
138 UInt32 *hash, UInt32 hashMask, UInt32 *heads, UInt32 numHeads, const UInt32 *crc) \
139 { action; for (; numHeads != 0; numHeads--) { \
140 const UInt32 value = (v); p++; *heads++ = pos - hash[value]; hash[value] = pos++; } }
141
142 #define DEF_GetHeads(name, v) DEF_GetHeads2(name, v, ;)
143
144 DEF_GetHeads2(2, (p[0] | ((UInt32)p[1] << 8)), UNUSED_VAR(hashMask); UNUSED_VAR(crc); )
145 DEF_GetHeads(3, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8)) & hashMask)
146 DEF_GetHeads(4, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5)) & hashMask)
147 DEF_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
HashThreadFunc(CMatchFinderMt * mt)150 static void 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 = Inline_MatchFinder_GetPointerToCurrentPos(mf);
177 ptrdiff_t offset;
178 MatchFinder_MoveBlock(mf);
179 offset = beforePtr - Inline_MatchFinder_GetPointerToCurrentPos(mf);
180 mt->pointerToCurPos -= offset;
181 mt->buffer -= offset;
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, (size_t)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
MatchFinderMt_GetNextBlock_Hash(CMatchFinderMt * p)220 static void 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
GetMatchesSpecN(UInt32 lenLimit,UInt32 pos,const Byte * cur,CLzRef * son,UInt32 _cyclicBufferPos,UInt32 _cyclicBufferSize,UInt32 _cutValue,UInt32 * _distances,UInt32 _maxLen,const UInt32 * hash,Int32 limit,UInt32 size,UInt32 * posRes)236 static Int32 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
BtGetMatches(CMatchFinderMt * p,UInt32 * distances)313 static void BtGetMatches(CMatchFinderMt *p, UInt32 *distances)
314 {
315 UInt32 numProcessed = 0;
316 UInt32 curPos = 2;
317 UInt32 limit = kMtBtBlockSize - (p->matchMaxLen * 2);
318
319 distances[1] = p->hashNumAvail;
320
321 while (curPos < limit)
322 {
323 if (p->hashBufPos == p->hashBufPosLimit)
324 {
325 MatchFinderMt_GetNextBlock_Hash(p);
326 distances[1] = numProcessed + p->hashNumAvail;
327 if (p->hashNumAvail >= p->numHashBytes)
328 continue;
329 distances[0] = curPos + p->hashNumAvail;
330 distances += curPos;
331 for (; p->hashNumAvail != 0; p->hashNumAvail--)
332 *distances++ = 0;
333 return;
334 }
335 {
336 UInt32 size = p->hashBufPosLimit - p->hashBufPos;
337 UInt32 lenLimit = p->matchMaxLen;
338 UInt32 pos = p->pos;
339 UInt32 cyclicBufferPos = p->cyclicBufferPos;
340 if (lenLimit >= p->hashNumAvail)
341 lenLimit = p->hashNumAvail;
342 {
343 UInt32 size2 = p->hashNumAvail - lenLimit + 1;
344 if (size2 < size)
345 size = size2;
346 size2 = p->cyclicBufferSize - cyclicBufferPos;
347 if (size2 < size)
348 size = size2;
349 }
350
351 #ifndef MFMT_GM_INLINE
352 while (curPos < limit && size-- != 0)
353 {
354 UInt32 *startDistances = distances + curPos;
355 UInt32 num = (UInt32)(GetMatchesSpec1(lenLimit, pos - p->hashBuf[p->hashBufPos++],
356 pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue,
357 startDistances + 1, p->numHashBytes - 1) - startDistances);
358 *startDistances = num - 1;
359 curPos += num;
360 cyclicBufferPos++;
361 pos++;
362 p->buffer++;
363 }
364 #else
365 {
366 UInt32 posRes;
367 curPos = limit - GetMatchesSpecN(lenLimit, pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue,
368 distances + curPos, p->numHashBytes - 1, p->hashBuf + p->hashBufPos, (Int32)(limit - curPos), size, &posRes);
369 p->hashBufPos += posRes - pos;
370 cyclicBufferPos += posRes - pos;
371 p->buffer += posRes - pos;
372 pos = posRes;
373 }
374 #endif
375
376 numProcessed += pos - p->pos;
377 p->hashNumAvail -= pos - p->pos;
378 p->pos = pos;
379 if (cyclicBufferPos == p->cyclicBufferSize)
380 cyclicBufferPos = 0;
381 p->cyclicBufferPos = cyclicBufferPos;
382 }
383 }
384
385 distances[0] = curPos;
386 }
387
BtFillBlock(CMatchFinderMt * p,UInt32 globalBlockIndex)388 static void BtFillBlock(CMatchFinderMt *p, UInt32 globalBlockIndex)
389 {
390 CMtSync *sync = &p->hashSync;
391 if (!sync->needStart)
392 {
393 CriticalSection_Enter(&sync->cs);
394 sync->csWasEntered = True;
395 }
396
397 BtGetMatches(p, p->btBuf + (globalBlockIndex & kMtBtNumBlocksMask) * kMtBtBlockSize);
398
399 if (p->pos > kMtMaxValForNormalize - kMtBtBlockSize)
400 {
401 UInt32 subValue = p->pos - p->cyclicBufferSize;
402 MatchFinder_Normalize3(subValue, p->son, (size_t)p->cyclicBufferSize * 2);
403 p->pos -= subValue;
404 }
405
406 if (!sync->needStart)
407 {
408 CriticalSection_Leave(&sync->cs);
409 sync->csWasEntered = False;
410 }
411 }
412
BtThreadFunc(CMatchFinderMt * mt)413 void BtThreadFunc(CMatchFinderMt *mt)
414 {
415 CMtSync *p = &mt->btSync;
416 for (;;)
417 {
418 UInt32 blockIndex = 0;
419 Event_Wait(&p->canStart);
420 Event_Set(&p->wasStarted);
421 for (;;)
422 {
423 if (p->exit)
424 return;
425 if (p->stopWriting)
426 {
427 p->numProcessedBlocks = blockIndex;
428 MtSync_StopWriting(&mt->hashSync);
429 Event_Set(&p->wasStopped);
430 break;
431 }
432 Semaphore_Wait(&p->freeSemaphore);
433 BtFillBlock(mt, blockIndex++);
434 Semaphore_Release1(&p->filledSemaphore);
435 }
436 }
437 }
438
MatchFinderMt_Construct(CMatchFinderMt * p)439 void MatchFinderMt_Construct(CMatchFinderMt *p)
440 {
441 p->hashBuf = NULL;
442 MtSync_Construct(&p->hashSync);
443 MtSync_Construct(&p->btSync);
444 }
445
MatchFinderMt_FreeMem(CMatchFinderMt * p,ISzAlloc * alloc)446 static void MatchFinderMt_FreeMem(CMatchFinderMt *p, ISzAlloc *alloc)
447 {
448 alloc->Free(alloc, p->hashBuf);
449 p->hashBuf = NULL;
450 }
451
MatchFinderMt_Destruct(CMatchFinderMt * p,ISzAlloc * alloc)452 void MatchFinderMt_Destruct(CMatchFinderMt *p, ISzAlloc *alloc)
453 {
454 MtSync_Destruct(&p->hashSync);
455 MtSync_Destruct(&p->btSync);
456 MatchFinderMt_FreeMem(p, alloc);
457 }
458
459 #define kHashBufferSize (kMtHashBlockSize * kMtHashNumBlocks)
460 #define kBtBufferSize (kMtBtBlockSize * kMtBtNumBlocks)
461
HashThreadFunc2(void * p)462 static THREAD_FUNC_RET_TYPE THREAD_FUNC_CALL_TYPE HashThreadFunc2(void *p) { HashThreadFunc((CMatchFinderMt *)p); return 0; }
BtThreadFunc2(void * p)463 static THREAD_FUNC_RET_TYPE THREAD_FUNC_CALL_TYPE BtThreadFunc2(void *p)
464 {
465 Byte allocaDummy[0x180];
466 unsigned i = 0;
467 for (i = 0; i < 16; i++)
468 allocaDummy[i] = (Byte)0;
469 if (allocaDummy[0] == 0)
470 BtThreadFunc((CMatchFinderMt *)p);
471 return 0;
472 }
473
MatchFinderMt_Create(CMatchFinderMt * p,UInt32 historySize,UInt32 keepAddBufferBefore,UInt32 matchMaxLen,UInt32 keepAddBufferAfter,ISzAlloc * alloc)474 SRes MatchFinderMt_Create(CMatchFinderMt *p, UInt32 historySize, UInt32 keepAddBufferBefore,
475 UInt32 matchMaxLen, UInt32 keepAddBufferAfter, ISzAlloc *alloc)
476 {
477 CMatchFinder *mf = p->MatchFinder;
478 p->historySize = historySize;
479 if (kMtBtBlockSize <= matchMaxLen * 4)
480 return SZ_ERROR_PARAM;
481 if (!p->hashBuf)
482 {
483 p->hashBuf = (UInt32 *)alloc->Alloc(alloc, (kHashBufferSize + kBtBufferSize) * sizeof(UInt32));
484 if (!p->hashBuf)
485 return SZ_ERROR_MEM;
486 p->btBuf = p->hashBuf + kHashBufferSize;
487 }
488 keepAddBufferBefore += (kHashBufferSize + kBtBufferSize);
489 keepAddBufferAfter += kMtHashBlockSize;
490 if (!MatchFinder_Create(mf, historySize, keepAddBufferBefore, matchMaxLen, keepAddBufferAfter, alloc))
491 return SZ_ERROR_MEM;
492
493 RINOK(MtSync_Create(&p->hashSync, HashThreadFunc2, p, kMtHashNumBlocks));
494 RINOK(MtSync_Create(&p->btSync, BtThreadFunc2, p, kMtBtNumBlocks));
495 return SZ_OK;
496 }
497
498 /* Call it after ReleaseStream / SetStream */
MatchFinderMt_Init(CMatchFinderMt * p)499 void MatchFinderMt_Init(CMatchFinderMt *p)
500 {
501 CMatchFinder *mf = p->MatchFinder;
502 p->btBufPos = p->btBufPosLimit = 0;
503 p->hashBufPos = p->hashBufPosLimit = 0;
504
505 /* Init without data reading. We don't want to read data in this thread */
506 MatchFinder_Init_2(mf, False);
507
508 p->pointerToCurPos = Inline_MatchFinder_GetPointerToCurrentPos(mf);
509 p->btNumAvailBytes = 0;
510 p->lzPos = p->historySize + 1;
511
512 p->hash = mf->hash;
513 p->fixedHashSize = mf->fixedHashSize;
514 p->crc = mf->crc;
515
516 p->son = mf->son;
517 p->matchMaxLen = mf->matchMaxLen;
518 p->numHashBytes = mf->numHashBytes;
519 p->pos = mf->pos;
520 p->buffer = mf->buffer;
521 p->cyclicBufferPos = mf->cyclicBufferPos;
522 p->cyclicBufferSize = mf->cyclicBufferSize;
523 p->cutValue = mf->cutValue;
524 }
525
526 /* ReleaseStream is required to finish multithreading */
MatchFinderMt_ReleaseStream(CMatchFinderMt * p)527 void MatchFinderMt_ReleaseStream(CMatchFinderMt *p)
528 {
529 MtSync_StopWriting(&p->btSync);
530 /* p->MatchFinder->ReleaseStream(); */
531 }
532
MatchFinderMt_Normalize(CMatchFinderMt * p)533 static void MatchFinderMt_Normalize(CMatchFinderMt *p)
534 {
535 MatchFinder_Normalize3(p->lzPos - p->historySize - 1, p->hash, p->fixedHashSize);
536 p->lzPos = p->historySize + 1;
537 }
538
MatchFinderMt_GetNextBlock_Bt(CMatchFinderMt * p)539 static void MatchFinderMt_GetNextBlock_Bt(CMatchFinderMt *p)
540 {
541 UInt32 blockIndex;
542 MtSync_GetNextBlock(&p->btSync);
543 blockIndex = ((p->btSync.numProcessedBlocks - 1) & kMtBtNumBlocksMask);
544 p->btBufPosLimit = p->btBufPos = blockIndex * kMtBtBlockSize;
545 p->btBufPosLimit += p->btBuf[p->btBufPos++];
546 p->btNumAvailBytes = p->btBuf[p->btBufPos++];
547 if (p->lzPos >= kMtMaxValForNormalize - kMtBtBlockSize)
548 MatchFinderMt_Normalize(p);
549 }
550
MatchFinderMt_GetPointerToCurrentPos(CMatchFinderMt * p)551 static const Byte * MatchFinderMt_GetPointerToCurrentPos(CMatchFinderMt *p)
552 {
553 return p->pointerToCurPos;
554 }
555
556 #define GET_NEXT_BLOCK_IF_REQUIRED if (p->btBufPos == p->btBufPosLimit) MatchFinderMt_GetNextBlock_Bt(p);
557
MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt * p)558 static UInt32 MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt *p)
559 {
560 GET_NEXT_BLOCK_IF_REQUIRED;
561 return p->btNumAvailBytes;
562 }
563
MixMatches2(CMatchFinderMt * p,UInt32 matchMinPos,UInt32 * distances)564 static UInt32 * MixMatches2(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)
565 {
566 UInt32 h2, curMatch2;
567 UInt32 *hash = p->hash;
568 const Byte *cur = p->pointerToCurPos;
569 UInt32 lzPos = p->lzPos;
570 MT_HASH2_CALC
571
572 curMatch2 = hash[h2];
573 hash[h2] = lzPos;
574
575 if (curMatch2 >= matchMinPos)
576 if (cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])
577 {
578 *distances++ = 2;
579 *distances++ = lzPos - curMatch2 - 1;
580 }
581
582 return distances;
583 }
584
MixMatches3(CMatchFinderMt * p,UInt32 matchMinPos,UInt32 * distances)585 static UInt32 * MixMatches3(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)
586 {
587 UInt32 h2, h3, curMatch2, curMatch3;
588 UInt32 *hash = p->hash;
589 const Byte *cur = p->pointerToCurPos;
590 UInt32 lzPos = p->lzPos;
591 MT_HASH3_CALC
592
593 curMatch2 = hash[ h2];
594 curMatch3 = hash[kFix3HashSize + h3];
595
596 hash[ h2] = lzPos;
597 hash[kFix3HashSize + h3] = lzPos;
598
599 if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])
600 {
601 distances[1] = lzPos - curMatch2 - 1;
602 if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2])
603 {
604 distances[0] = 3;
605 return distances + 2;
606 }
607 distances[0] = 2;
608 distances += 2;
609 }
610
611 if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0])
612 {
613 *distances++ = 3;
614 *distances++ = lzPos - curMatch3 - 1;
615 }
616
617 return distances;
618 }
619
620 /*
621 static UInt32 *MixMatches4(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)
622 {
623 UInt32 h2, h3, h4, curMatch2, curMatch3, curMatch4;
624 UInt32 *hash = p->hash;
625 const Byte *cur = p->pointerToCurPos;
626 UInt32 lzPos = p->lzPos;
627 MT_HASH4_CALC
628
629 curMatch2 = hash[ h2];
630 curMatch3 = hash[kFix3HashSize + h3];
631 curMatch4 = hash[kFix4HashSize + h4];
632
633 hash[ h2] = lzPos;
634 hash[kFix3HashSize + h3] = lzPos;
635 hash[kFix4HashSize + h4] = lzPos;
636
637 if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])
638 {
639 distances[1] = lzPos - curMatch2 - 1;
640 if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2])
641 {
642 distances[0] = (cur[(ptrdiff_t)curMatch2 - lzPos + 3] == cur[3]) ? 4 : 3;
643 return distances + 2;
644 }
645 distances[0] = 2;
646 distances += 2;
647 }
648
649 if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0])
650 {
651 distances[1] = lzPos - curMatch3 - 1;
652 if (cur[(ptrdiff_t)curMatch3 - lzPos + 3] == cur[3])
653 {
654 distances[0] = 4;
655 return distances + 2;
656 }
657 distances[0] = 3;
658 distances += 2;
659 }
660
661 if (curMatch4 >= matchMinPos)
662 if (
663 cur[(ptrdiff_t)curMatch4 - lzPos] == cur[0] &&
664 cur[(ptrdiff_t)curMatch4 - lzPos + 3] == cur[3]
665 )
666 {
667 *distances++ = 4;
668 *distances++ = lzPos - curMatch4 - 1;
669 }
670
671 return distances;
672 }
673 */
674
675 #define INCREASE_LZ_POS p->lzPos++; p->pointerToCurPos++;
676
MatchFinderMt2_GetMatches(CMatchFinderMt * p,UInt32 * distances)677 static UInt32 MatchFinderMt2_GetMatches(CMatchFinderMt *p, UInt32 *distances)
678 {
679 const UInt32 *btBuf = p->btBuf + p->btBufPos;
680 UInt32 len = *btBuf++;
681 p->btBufPos += 1 + len;
682 p->btNumAvailBytes--;
683 {
684 UInt32 i;
685 for (i = 0; i < len; i += 2)
686 {
687 *distances++ = *btBuf++;
688 *distances++ = *btBuf++;
689 }
690 }
691 INCREASE_LZ_POS
692 return len;
693 }
694
MatchFinderMt_GetMatches(CMatchFinderMt * p,UInt32 * distances)695 static UInt32 MatchFinderMt_GetMatches(CMatchFinderMt *p, UInt32 *distances)
696 {
697 const UInt32 *btBuf = p->btBuf + p->btBufPos;
698 UInt32 len = *btBuf++;
699 p->btBufPos += 1 + len;
700
701 if (len == 0)
702 {
703 /* change for bt5 ! */
704 if (p->btNumAvailBytes-- >= 4)
705 len = (UInt32)(p->MixMatchesFunc(p, p->lzPos - p->historySize, distances) - (distances));
706 }
707 else
708 {
709 /* Condition: there are matches in btBuf with length < p->numHashBytes */
710 UInt32 *distances2;
711 p->btNumAvailBytes--;
712 distances2 = p->MixMatchesFunc(p, p->lzPos - btBuf[1], distances);
713 do
714 {
715 *distances2++ = *btBuf++;
716 *distances2++ = *btBuf++;
717 }
718 while ((len -= 2) != 0);
719 len = (UInt32)(distances2 - (distances));
720 }
721 INCREASE_LZ_POS
722 return len;
723 }
724
725 #define SKIP_HEADER2_MT do { GET_NEXT_BLOCK_IF_REQUIRED
726 #define SKIP_HEADER_MT(n) SKIP_HEADER2_MT if (p->btNumAvailBytes-- >= (n)) { const Byte *cur = p->pointerToCurPos; UInt32 *hash = p->hash;
727 #define SKIP_FOOTER_MT } INCREASE_LZ_POS p->btBufPos += p->btBuf[p->btBufPos] + 1; } while (--num != 0);
728
MatchFinderMt0_Skip(CMatchFinderMt * p,UInt32 num)729 static void MatchFinderMt0_Skip(CMatchFinderMt *p, UInt32 num)
730 {
731 SKIP_HEADER2_MT { p->btNumAvailBytes--;
732 SKIP_FOOTER_MT
733 }
734
735 static void MatchFinderMt2_Skip(CMatchFinderMt *p, UInt32 num)
736 {
737 SKIP_HEADER_MT(2)
738 UInt32 h2;
739 MT_HASH2_CALC
740 hash[h2] = p->lzPos;
741 SKIP_FOOTER_MT
742 }
743
744 static void MatchFinderMt3_Skip(CMatchFinderMt *p, UInt32 num)
745 {
746 SKIP_HEADER_MT(3)
747 UInt32 h2, h3;
748 MT_HASH3_CALC
749 hash[kFix3HashSize + h3] =
750 hash[ h2] =
751 p->lzPos;
752 SKIP_FOOTER_MT
753 }
754
755 /*
756 static void MatchFinderMt4_Skip(CMatchFinderMt *p, UInt32 num)
757 {
758 SKIP_HEADER_MT(4)
759 UInt32 h2, h3, h4;
760 MT_HASH4_CALC
761 hash[kFix4HashSize + h4] =
762 hash[kFix3HashSize + h3] =
763 hash[ h2] =
764 p->lzPos;
765 SKIP_FOOTER_MT
766 }
767 */
768
769 void MatchFinderMt_CreateVTable(CMatchFinderMt *p, IMatchFinder *vTable)
770 {
771 vTable->Init = (Mf_Init_Func)MatchFinderMt_Init;
772 vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinderMt_GetNumAvailableBytes;
773 vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinderMt_GetPointerToCurrentPos;
774 vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt_GetMatches;
775
776 switch (p->MatchFinder->numHashBytes)
777 {
778 case 2:
779 p->GetHeadsFunc = GetHeads2;
780 p->MixMatchesFunc = (Mf_Mix_Matches)0;
781 vTable->Skip = (Mf_Skip_Func)MatchFinderMt0_Skip;
782 vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt2_GetMatches;
783 break;
784 case 3:
785 p->GetHeadsFunc = GetHeads3;
786 p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches2;
787 vTable->Skip = (Mf_Skip_Func)MatchFinderMt2_Skip;
788 break;
789 default:
790 /* case 4: */
791 p->GetHeadsFunc = p->MatchFinder->bigHash ? GetHeads4b : GetHeads4;
792 p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches3;
793 vTable->Skip = (Mf_Skip_Func)MatchFinderMt3_Skip;
794 break;
795 /*
796 default:
797 p->GetHeadsFunc = GetHeads5;
798 p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches4;
799 vTable->Skip = (Mf_Skip_Func)MatchFinderMt4_Skip;
800 break;
801 */
802 }
803 }
804