1 /* LzFindMt.c -- multithreaded Match finder for LZ algorithms
2 2008-10-04 : Igor Pavlov : Public domain */
3
4 #include "LzHash.h"
5
6 #include "LzFindMt.h"
7
MtSync_Construct(CMtSync * p)8 void 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
MtSync_GetNextBlock(CMtSync * p)21 void 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
MtSync_StopWriting(CMtSync * p)49 void 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
MtSync_Destruct(CMtSync * p)72 void 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
MtSync_Create2(CMtSync * p,unsigned (MY_STD_CALL * startAddress)(void *),void * obj,UInt32 numBlocks)100 static 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
MtSync_Create(CMtSync * p,unsigned (MY_STD_CALL * startAddress)(void *),void * obj,UInt32 numBlocks)122 static 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
MtSync_Init(CMtSync * p)130 void MtSync_Init(CMtSync *p) { p->needStart = True; }
131
132 #define kMtMaxValForNormalize 0xFFFFFFFF
133
134 #define DEF_GetHeads2(name, v, action) \
135 static void GetHeads ## name(const Byte *p, UInt32 pos, \
136 UInt32 *hash, UInt32 hashMask, UInt32 *heads, UInt32 numHeads, const UInt32 *crc) \
137 { action; for (; numHeads != 0; numHeads--) { \
138 const UInt32 value = (v); p++; *heads++ = pos - hash[value]; hash[value] = pos++; } }
139
140 #define DEF_GetHeads(name, v) DEF_GetHeads2(name, v, ;)
141
142 DEF_GetHeads2(2, (p[0] | ((UInt32)p[1] << 8)), hashMask = hashMask; crc = crc; )
143 DEF_GetHeads(3, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8)) & hashMask)
144 DEF_GetHeads(4, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5)) & hashMask)
145 DEF_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
HashThreadFunc(CMatchFinderMt * mt)148 void 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
MatchFinderMt_GetNextBlock_Hash(CMatchFinderMt * p)218 void 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
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)234 Int32 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
BtGetMatches(CMatchFinderMt * p,UInt32 * distances)311 void 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
BtFillBlock(CMatchFinderMt * p,UInt32 globalBlockIndex)380 void 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
BtThreadFunc(CMatchFinderMt * mt)405 void 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
MatchFinderMt_Construct(CMatchFinderMt * p)431 void MatchFinderMt_Construct(CMatchFinderMt *p)
432 {
433 p->hashBuf = 0;
434 MtSync_Construct(&p->hashSync);
435 MtSync_Construct(&p->btSync);
436 }
437
MatchFinderMt_FreeMem(CMatchFinderMt * p,ISzAlloc * alloc)438 void MatchFinderMt_FreeMem(CMatchFinderMt *p, ISzAlloc *alloc)
439 {
440 alloc->Free(alloc, p->hashBuf);
441 p->hashBuf = 0;
442 }
443
MatchFinderMt_Destruct(CMatchFinderMt * p,ISzAlloc * alloc)444 void 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
HashThreadFunc2(void * p)454 static unsigned MY_STD_CALL HashThreadFunc2(void *p) { HashThreadFunc((CMatchFinderMt *)p); return 0; }
BtThreadFunc2(void * p)455 static 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
MatchFinderMt_Create(CMatchFinderMt * p,UInt32 historySize,UInt32 keepAddBufferBefore,UInt32 matchMaxLen,UInt32 keepAddBufferAfter,ISzAlloc * alloc)465 SRes 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 */
MatchFinderMt_Init(CMatchFinderMt * p)490 void 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 */
MatchFinderMt_ReleaseStream(CMatchFinderMt * p)515 void MatchFinderMt_ReleaseStream(CMatchFinderMt *p)
516 {
517 MtSync_StopWriting(&p->btSync);
518 /* p->MatchFinder->ReleaseStream(); */
519 }
520
MatchFinderMt_Normalize(CMatchFinderMt * p)521 void 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
MatchFinderMt_GetNextBlock_Bt(CMatchFinderMt * p)527 void 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
MatchFinderMt_GetPointerToCurrentPos(CMatchFinderMt * p)539 const 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
MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt * p)546 UInt32 MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt *p)
547 {
548 GET_NEXT_BLOCK_IF_REQUIRED;
549 return p->btNumAvailBytes;
550 }
551
MatchFinderMt_GetIndexByte(CMatchFinderMt * p,Int32 index)552 Byte MatchFinderMt_GetIndexByte(CMatchFinderMt *p, Int32 index)
553 {
554 return p->pointerToCurPos[index];
555 }
556
MixMatches2(CMatchFinderMt * p,UInt32 matchMinPos,UInt32 * distances)557 UInt32 * 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
MixMatches3(CMatchFinderMt * p,UInt32 matchMinPos,UInt32 * distances)577 UInt32 * 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 /*
612 UInt32 *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
MatchFinderMt2_GetMatches(CMatchFinderMt * p,UInt32 * distances)667 UInt32 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
MatchFinderMt_GetMatches(CMatchFinderMt * p,UInt32 * distances)685 UInt32 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 do { GET_NEXT_BLOCK_IF_REQUIRED
715 #define SKIP_HEADER(n) SKIP_HEADER2 if (p->btNumAvailBytes-- >= (n)) { const Byte *cur = p->pointerToCurPos; UInt32 *hash = p->hash;
716 #define SKIP_FOOTER } INCREASE_LZ_POS p->btBufPos += p->btBuf[p->btBufPos] + 1; } while (--num != 0);
717
MatchFinderMt0_Skip(CMatchFinderMt * p,UInt32 num)718 void MatchFinderMt0_Skip(CMatchFinderMt *p, UInt32 num)
719 {
720 SKIP_HEADER2 { p->btNumAvailBytes--;
721 SKIP_FOOTER
722 }
723
724 void MatchFinderMt2_Skip(CMatchFinderMt *p, UInt32 num)
725 {
726 SKIP_HEADER(2)
727 UInt32 hash2Value;
728 MT_HASH2_CALC
729 hash[hash2Value] = p->lzPos;
730 SKIP_FOOTER
731 }
732
733 void MatchFinderMt3_Skip(CMatchFinderMt *p, UInt32 num)
734 {
735 SKIP_HEADER(3)
736 UInt32 hash2Value, hash3Value;
737 MT_HASH3_CALC
738 hash[kFix3HashSize + hash3Value] =
739 hash[ hash2Value] =
740 p->lzPos;
741 SKIP_FOOTER
742 }
743
744 /*
745 void MatchFinderMt4_Skip(CMatchFinderMt *p, UInt32 num)
746 {
747 SKIP_HEADER(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
755 }
756 */
757
758 void 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