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