1 #define UNP_READ_SIZE_MT 0x400000
2 #define UNP_BLOCKS_PER_THREAD 2
3
4
5 struct UnpackThreadDataList
6 {
7 UnpackThreadData *D;
8 uint BlockCount;
9 };
10
11
THREAD_PROC(UnpackDecodeThread)12 THREAD_PROC(UnpackDecodeThread)
13 {
14 UnpackThreadDataList *DL=(UnpackThreadDataList *)Data;
15 for (uint I=0;I<DL->BlockCount;I++)
16 DL->D->UnpackPtr->UnpackDecode(DL->D[I]);
17 }
18
19
InitMT()20 void Unpack::InitMT()
21 {
22 if (ReadBufMT==NULL)
23 {
24 // Even getbits32 can read up to 3 additional bytes after current
25 // and our block header and table reading code can look much further.
26 // Let's allocate the additional space here, so we do not need to check
27 // bounds for every bit field access.
28 const size_t Overflow=1024;
29
30 ReadBufMT=new byte[UNP_READ_SIZE_MT+Overflow];
31 memset(ReadBufMT,0,UNP_READ_SIZE_MT+Overflow);
32 }
33 if (UnpThreadData==NULL)
34 {
35 uint MaxItems=MaxUserThreads*UNP_BLOCKS_PER_THREAD;
36 UnpThreadData=new UnpackThreadData[MaxItems];
37 memset(UnpThreadData,0,sizeof(UnpackThreadData)*MaxItems);
38
39 for (uint I=0;I<MaxItems;I++)
40 {
41 UnpackThreadData *CurData=UnpThreadData+I;
42 if (CurData->Decoded==NULL)
43 {
44 // Typical number of items in RAR blocks does not exceed 0x4000.
45 CurData->DecodedAllocated=0x4100;
46 CurData->Decoded=(UnpackDecodedItem *)malloc(CurData->DecodedAllocated*sizeof(UnpackDecodedItem));
47 if (CurData->Decoded==NULL)
48 ErrHandler.MemoryError();
49 }
50 }
51 }
52 }
53
54
Unpack5MT(bool Solid)55 void Unpack::Unpack5MT(bool Solid)
56 {
57 InitMT();
58 UnpInitData(Solid);
59
60 for (uint I=0;I<MaxUserThreads*UNP_BLOCKS_PER_THREAD;I++)
61 {
62 UnpackThreadData *CurData=UnpThreadData+I;
63 CurData->LargeBlock=false;
64 CurData->Incomplete=false;
65 }
66
67 UnpThreadData[0].BlockHeader=BlockHeader;
68 UnpThreadData[0].BlockTables=BlockTables;
69 uint LastBlockNum=0;
70
71 int DataSize=0;
72 int BlockStart=0;
73
74
75 // 'true' if we found a block too large for multithreaded extraction,
76 // so we switched to single threaded mode until the end of file.
77 // Large blocks could cause too high memory use in multithreaded mode.
78 bool LargeBlock=false;
79
80 bool Done=false;
81 while (!Done)
82 {
83 // Data amount, which is guaranteed to fit block header and tables,
84 // so we can safely read them without additional checks.
85 const int TooSmallToProcess=1024;
86
87 int ReadSize=UnpIO->UnpRead(ReadBufMT+DataSize,(UNP_READ_SIZE_MT-DataSize)&~0xf);
88 if (ReadSize<0)
89 break;
90 DataSize+=ReadSize;
91 if (DataSize==0)
92 break;
93 if (ReadSize>0 && DataSize<TooSmallToProcess)
94 continue;
95
96 bool BufferProcessed=false;
97 while (BlockStart<DataSize && !Done)
98 {
99 uint BlockNumber=0,BlockNumberMT=0;
100 while (BlockNumber<MaxUserThreads*UNP_BLOCKS_PER_THREAD)
101 {
102 UnpackThreadData *CurData=UnpThreadData+BlockNumber;
103 LastBlockNum=BlockNumber;
104 CurData->UnpackPtr=this;
105
106 // 'Incomplete' thread is present. This is a thread processing block
107 // in the end of buffer, split between two read operations.
108 if (CurData->Incomplete)
109 CurData->DataSize=DataSize;
110 else
111 {
112 CurData->Inp.SetExternalBuffer(ReadBufMT+BlockStart);
113 CurData->Inp.InitBitInput();
114 CurData->DataSize=DataSize-BlockStart;
115 if (CurData->DataSize==0)
116 break;
117 CurData->DamagedData=false;
118 CurData->HeaderRead=false;
119 CurData->TableRead=false;
120 }
121
122 // We should not use 'last block in file' block flag here unless
123 // we'll check the block size, because even if block is last in file,
124 // it can exceed the current buffer and require more reading.
125 CurData->NoDataLeft=(ReadSize==0);
126
127 CurData->Incomplete=false;
128 CurData->ThreadNumber=BlockNumber;
129
130 if (!CurData->HeaderRead)
131 {
132 CurData->HeaderRead=true;
133 if (!ReadBlockHeader(CurData->Inp,CurData->BlockHeader))
134 {
135 Done=true;
136 break;
137 }
138 }
139
140 // To prevent too high memory use we switch to single threaded mode
141 // if block exceeds this size. Typically RAR blocks do not exceed
142 // 64 KB, so this protection should not affect most of valid archives.
143 const int LargeBlockSize=0x20000;
144 if (LargeBlock || CurData->BlockHeader.BlockSize>LargeBlockSize)
145 LargeBlock=CurData->LargeBlock=true;
146 else
147 BlockNumberMT++; // Number of normal blocks processed in MT mode.
148
149 BlockStart+=CurData->BlockHeader.HeaderSize+CurData->BlockHeader.BlockSize;
150
151 BlockNumber++;
152
153 int DataLeft=DataSize-BlockStart;
154 if (DataLeft>=0 && CurData->BlockHeader.LastBlockInFile)
155 break;
156
157 // For second and following threads we move smaller blocks to buffer
158 // start to ensure that we have enough data to fit block header
159 // and tables.
160 if (DataLeft<TooSmallToProcess)
161 break;
162 }
163
164 //#undef USE_THREADS
165 UnpackThreadDataList UTDArray[MaxPoolThreads];
166 uint UTDArrayPos=0;
167
168 uint MaxBlockPerThread=BlockNumberMT/MaxUserThreads;
169 if (BlockNumberMT%MaxUserThreads!=0)
170 MaxBlockPerThread++;
171
172 // Decode all normal blocks until the first 'large' if any.
173 for (uint CurBlock=0;CurBlock<BlockNumberMT;CurBlock+=MaxBlockPerThread)
174 {
175 UnpackThreadDataList *UTD=UTDArray+UTDArrayPos++;
176 UTD->D=UnpThreadData+CurBlock;
177 UTD->BlockCount=Min(MaxBlockPerThread,BlockNumberMT-CurBlock);
178
179 #ifdef USE_THREADS
180 if (BlockNumber==1)
181 UnpackDecode(*UTD->D);
182 else
183 UnpThreadPool->AddTask(UnpackDecodeThread,(void*)UTD);
184 #else
185 for (uint I=0;I<UTD->BlockCount;I++)
186 UnpackDecode(UTD->D[I]);
187 #endif
188 }
189
190 if (BlockNumber==0)
191 break;
192
193 #ifdef USE_THREADS
194 UnpThreadPool->WaitDone();
195 #endif
196
197 bool IncompleteThread=false;
198
199 for (uint Block=0;Block<BlockNumber;Block++)
200 {
201 UnpackThreadData *CurData=UnpThreadData+Block;
202 if (!CurData->LargeBlock && !ProcessDecoded(*CurData) ||
203 CurData->LargeBlock && !UnpackLargeBlock(*CurData) ||
204 CurData->DamagedData)
205 {
206 Done=true;
207 break;
208 }
209 if (CurData->Incomplete)
210 {
211 int BufPos=int(CurData->Inp.InBuf+CurData->Inp.InAddr-ReadBufMT);
212 if (DataSize<=BufPos) // Thread exceeded input buffer boundary.
213 {
214 Done=true;
215 break;
216 }
217 IncompleteThread=true;
218 memmove(ReadBufMT,ReadBufMT+BufPos,DataSize-BufPos);
219 CurData->BlockHeader.BlockSize-=CurData->Inp.InAddr-CurData->BlockHeader.BlockStart;
220 CurData->BlockHeader.HeaderSize=0;
221 CurData->BlockHeader.BlockStart=0;
222 CurData->Inp.InBuf=ReadBufMT;
223 CurData->Inp.InAddr=0;
224
225 if (Block!=0)
226 {
227 // Move the incomplete thread entry to the first position,
228 // so we'll start processing from it. Preserve the original
229 // buffer for decoded data.
230 UnpackDecodedItem *Decoded=UnpThreadData[0].Decoded;
231 uint DecodedAllocated=UnpThreadData[0].DecodedAllocated;
232 UnpThreadData[0]=*CurData;
233 UnpThreadData[0].Decoded=Decoded;
234 UnpThreadData[0].DecodedAllocated=DecodedAllocated;
235 CurData->Incomplete=false;
236 }
237
238 BlockStart=0;
239 DataSize-=BufPos;
240 break;
241 }
242 else
243 if (CurData->BlockHeader.LastBlockInFile)
244 {
245 Done=true;
246 break;
247 }
248 }
249
250 if (IncompleteThread || Done)
251 break; // Current buffer is done, read more data or quit.
252 else
253 {
254 int DataLeft=DataSize-BlockStart;
255 if (DataLeft<TooSmallToProcess)
256 {
257 if (DataLeft<0) // Invalid data, must not happen in valid archive.
258 {
259 Done=true;
260 break;
261 }
262
263 // If we do not have incomplete thread and have some data
264 // in the end of buffer, too small for single thread,
265 // let's move it to beginning of next buffer.
266 if (DataLeft>0)
267 memmove(ReadBufMT,ReadBufMT+BlockStart,DataLeft);
268 DataSize=DataLeft;
269 BlockStart=0;
270 break; // Current buffer is done, try to read more data.
271 }
272 }
273 }
274 }
275 UnpWriteBuf();
276
277 BlockHeader=UnpThreadData[LastBlockNum].BlockHeader;
278 BlockTables=UnpThreadData[LastBlockNum].BlockTables;
279 }
280
281
282 // Decode Huffman block and save decoded data to memory.
UnpackDecode(UnpackThreadData & D)283 void Unpack::UnpackDecode(UnpackThreadData &D)
284 {
285 if (!D.TableRead)
286 {
287 D.TableRead=true;
288 if (!ReadTables(D.Inp,D.BlockHeader,D.BlockTables))
289 {
290 D.DamagedData=true;
291 return;
292 }
293 }
294
295 if (D.Inp.InAddr>D.BlockHeader.HeaderSize+D.BlockHeader.BlockSize)
296 {
297 D.DamagedData=true;
298 return;
299 }
300
301 D.DecodedSize=0;
302 int BlockBorder=D.BlockHeader.BlockStart+D.BlockHeader.BlockSize-1;
303
304 // Reserve enough space even for filter entry.
305 int DataBorder=D.DataSize-16;
306 int ReadBorder=Min(BlockBorder,DataBorder);
307
308 while (true)
309 {
310 if (D.Inp.InAddr>=ReadBorder)
311 {
312 if (D.Inp.InAddr>BlockBorder || D.Inp.InAddr==BlockBorder &&
313 D.Inp.InBit>=D.BlockHeader.BlockBitSize)
314 break;
315
316 // If we do not have any more data in file to read, we must process
317 // what we have until last byte. Otherwise we can return and append
318 // more data to unprocessed few bytes.
319 if ((D.Inp.InAddr>=DataBorder) && !D.NoDataLeft || D.Inp.InAddr>=D.DataSize)
320 {
321 D.Incomplete=true;
322 break;
323 }
324 }
325 if (D.DecodedSize>D.DecodedAllocated-8) // Filter can use several slots.
326 {
327 D.DecodedAllocated=D.DecodedAllocated*2;
328 D.Decoded=(UnpackDecodedItem *)realloc(D.Decoded,D.DecodedAllocated*sizeof(UnpackDecodedItem));
329 if (D.Decoded==NULL)
330 ErrHandler.MemoryError();
331 }
332
333 UnpackDecodedItem *CurItem=D.Decoded+D.DecodedSize++;
334
335 uint MainSlot=DecodeNumber(D.Inp,&D.BlockTables.LD);
336 if (MainSlot<256)
337 {
338 if (D.DecodedSize>1)
339 {
340 UnpackDecodedItem *PrevItem=CurItem-1;
341 if (PrevItem->Type==UNPDT_LITERAL && PrevItem->Length<3)
342 {
343 PrevItem->Length++;
344 PrevItem->Literal[PrevItem->Length]=(byte)MainSlot;
345 D.DecodedSize--;
346 continue;
347 }
348 }
349 CurItem->Type=UNPDT_LITERAL;
350 CurItem->Literal[0]=(byte)MainSlot;
351 CurItem->Length=0;
352 continue;
353 }
354 if (MainSlot>=262)
355 {
356 uint Length=SlotToLength(D.Inp,MainSlot-262);
357
358 uint DBits,Distance=1,DistSlot=DecodeNumber(D.Inp,&D.BlockTables.DD);
359 if (DistSlot<4)
360 {
361 DBits=0;
362 Distance+=DistSlot;
363 }
364 else
365 {
366 DBits=DistSlot/2 - 1;
367 Distance+=(2 | (DistSlot & 1)) << DBits;
368 }
369
370 if (DBits>0)
371 {
372 if (DBits>=4)
373 {
374 if (DBits>4)
375 {
376 Distance+=((D.Inp.getbits32()>>(36-DBits))<<4);
377 D.Inp.addbits(DBits-4);
378 }
379 uint LowDist=DecodeNumber(D.Inp,&D.BlockTables.LDD);
380 Distance+=LowDist;
381 }
382 else
383 {
384 Distance+=D.Inp.getbits32()>>(32-DBits);
385 D.Inp.addbits(DBits);
386 }
387 }
388
389 if (Distance>0x100)
390 {
391 Length++;
392 if (Distance>0x2000)
393 {
394 Length++;
395 if (Distance>0x40000)
396 Length++;
397 }
398 }
399
400 CurItem->Type=UNPDT_MATCH;
401 CurItem->Length=(ushort)Length;
402 CurItem->Distance=Distance;
403 continue;
404 }
405 if (MainSlot==256)
406 {
407 UnpackFilter Filter;
408 ReadFilter(D.Inp,Filter);
409
410 CurItem->Type=UNPDT_FILTER;
411 CurItem->Length=Filter.Type;
412 CurItem->Distance=Filter.BlockStart;
413
414 CurItem=D.Decoded+D.DecodedSize++;
415
416 CurItem->Type=UNPDT_FILTER;
417 CurItem->Length=Filter.Channels;
418 CurItem->Distance=Filter.BlockLength;
419
420 continue;
421 }
422 if (MainSlot==257)
423 {
424 CurItem->Type=UNPDT_FULLREP;
425 continue;
426 }
427 if (MainSlot<262)
428 {
429 CurItem->Type=UNPDT_REP;
430 CurItem->Distance=MainSlot-258;
431 uint LengthSlot=DecodeNumber(D.Inp,&D.BlockTables.RD);
432 uint Length=SlotToLength(D.Inp,LengthSlot);
433 CurItem->Length=(ushort)Length;
434 continue;
435 }
436 }
437 }
438
439
440 // Process decoded Huffman block data.
ProcessDecoded(UnpackThreadData & D)441 bool Unpack::ProcessDecoded(UnpackThreadData &D)
442 {
443 UnpackDecodedItem *Item=D.Decoded,*Border=D.Decoded+D.DecodedSize;
444 while (Item<Border)
445 {
446 UnpPtr&=MaxWinMask;
447 if (((WriteBorder-UnpPtr) & MaxWinMask)<MAX_LZ_MATCH+3 && WriteBorder!=UnpPtr)
448 {
449 UnpWriteBuf();
450 if (WrittenFileSize>DestUnpSize)
451 return false;
452 }
453
454 if (Item->Type==UNPDT_LITERAL)
455 {
456 #if defined(LITTLE_ENDIAN) && defined(PRESENT_INT32) && defined(ALLOW_MISALIGNED)
457 if (Item->Length==3 && UnpPtr<MaxWinSize-4)
458 {
459 *(uint32 *)(Window+UnpPtr)=*(uint32 *)Item->Literal;
460 UnpPtr+=4;
461 }
462 else
463 #endif
464 for (uint I=0;I<=Item->Length;I++)
465 Window[UnpPtr++ & MaxWinMask]=Item->Literal[I];
466 }
467 else
468 if (Item->Type==UNPDT_MATCH)
469 {
470 InsertOldDist(Item->Distance);
471 LastLength=Item->Length;
472 CopyString(Item->Length,Item->Distance);
473 }
474 else
475 if (Item->Type==UNPDT_REP)
476 {
477 uint Distance=OldDist[Item->Distance];
478 for (uint I=Item->Distance;I>0;I--)
479 OldDist[I]=OldDist[I-1];
480 OldDist[0]=Distance;
481 LastLength=Item->Length;
482 CopyString(Item->Length,Distance);
483 }
484 else
485 if (Item->Type==UNPDT_FULLREP)
486 {
487 if (LastLength!=0)
488 CopyString(LastLength,OldDist[0]);
489 }
490 else
491 if (Item->Type==UNPDT_FILTER)
492 {
493 UnpackFilter Filter;
494
495 Filter.Type=(byte)Item->Length;
496 Filter.BlockStart=Item->Distance;
497
498 Item++;
499
500 Filter.Channels=(byte)Item->Length;
501 Filter.BlockLength=Item->Distance;
502
503 AddFilter(Filter);
504 }
505 Item++;
506 }
507 return true;
508 }
509
510
511 // For large blocks we decode and process in same function in single threaded
512 // mode, so we do not need to store intermediate data in memory.
UnpackLargeBlock(UnpackThreadData & D)513 bool Unpack::UnpackLargeBlock(UnpackThreadData &D)
514 {
515 if (!D.TableRead)
516 {
517 D.TableRead=true;
518 if (!ReadTables(D.Inp,D.BlockHeader,D.BlockTables))
519 {
520 D.DamagedData=true;
521 return false;
522 }
523 }
524
525 if (D.Inp.InAddr>D.BlockHeader.HeaderSize+D.BlockHeader.BlockSize)
526 {
527 D.DamagedData=true;
528 return false;
529 }
530
531 int BlockBorder=D.BlockHeader.BlockStart+D.BlockHeader.BlockSize-1;
532
533 // Reserve enough space even for filter entry.
534 int DataBorder=D.DataSize-16;
535 int ReadBorder=Min(BlockBorder,DataBorder);
536
537 while (true)
538 {
539 UnpPtr&=MaxWinMask;
540 if (D.Inp.InAddr>=ReadBorder)
541 {
542 if (D.Inp.InAddr>BlockBorder || D.Inp.InAddr==BlockBorder &&
543 D.Inp.InBit>=D.BlockHeader.BlockBitSize)
544 break;
545
546 // If we do not have any more data in file to read, we must process
547 // what we have until last byte. Otherwise we can return and append
548 // more data to unprocessed few bytes.
549 if ((D.Inp.InAddr>=DataBorder) && !D.NoDataLeft || D.Inp.InAddr>=D.DataSize)
550 {
551 D.Incomplete=true;
552 break;
553 }
554 }
555 if (((WriteBorder-UnpPtr) & MaxWinMask)<MAX_LZ_MATCH+3 && WriteBorder!=UnpPtr)
556 {
557 UnpWriteBuf();
558 if (WrittenFileSize>DestUnpSize)
559 return false;
560 }
561
562 uint MainSlot=DecodeNumber(D.Inp,&D.BlockTables.LD);
563 if (MainSlot<256)
564 {
565 Window[UnpPtr++]=(byte)MainSlot;
566 continue;
567 }
568 if (MainSlot>=262)
569 {
570 uint Length=SlotToLength(D.Inp,MainSlot-262);
571
572 uint DBits,Distance=1,DistSlot=DecodeNumber(D.Inp,&D.BlockTables.DD);
573 if (DistSlot<4)
574 {
575 DBits=0;
576 Distance+=DistSlot;
577 }
578 else
579 {
580 DBits=DistSlot/2 - 1;
581 Distance+=(2 | (DistSlot & 1)) << DBits;
582 }
583
584 if (DBits>0)
585 {
586 if (DBits>=4)
587 {
588 if (DBits>4)
589 {
590 Distance+=((D.Inp.getbits32()>>(36-DBits))<<4);
591 D.Inp.addbits(DBits-4);
592 }
593 uint LowDist=DecodeNumber(D.Inp,&D.BlockTables.LDD);
594 Distance+=LowDist;
595 }
596 else
597 {
598 Distance+=D.Inp.getbits32()>>(32-DBits);
599 D.Inp.addbits(DBits);
600 }
601 }
602
603 if (Distance>0x100)
604 {
605 Length++;
606 if (Distance>0x2000)
607 {
608 Length++;
609 if (Distance>0x40000)
610 Length++;
611 }
612 }
613
614 InsertOldDist(Distance);
615 LastLength=Length;
616 CopyString(Length,Distance);
617 continue;
618 }
619 if (MainSlot==256)
620 {
621 UnpackFilter Filter;
622 if (!ReadFilter(D.Inp,Filter) || !AddFilter(Filter))
623 break;
624 continue;
625 }
626 if (MainSlot==257)
627 {
628 if (LastLength!=0)
629 CopyString(LastLength,OldDist[0]);
630 continue;
631 }
632 if (MainSlot<262)
633 {
634 uint DistNum=MainSlot-258;
635 uint Distance=OldDist[DistNum];
636 for (uint I=DistNum;I>0;I--)
637 OldDist[I]=OldDist[I-1];
638 OldDist[0]=Distance;
639
640 uint LengthSlot=DecodeNumber(D.Inp,&D.BlockTables.RD);
641 uint Length=SlotToLength(D.Inp,LengthSlot);
642 LastLength=Length;
643 CopyString(Length,Distance);
644 continue;
645 }
646 }
647 return true;
648 }
649