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