| namespace third_party_unrar { |
| |
| #define UNP_READ_SIZE_MT 0x400000 |
| #define UNP_BLOCKS_PER_THREAD 2 |
| |
| |
| struct UnpackThreadDataList |
| { |
| UnpackThreadData *D; |
| uint BlockCount; |
| }; |
| |
| |
| THREAD_PROC(UnpackDecodeThread) |
| { |
| UnpackThreadDataList *DL=(UnpackThreadDataList *)Data; |
| for (uint I=0;I<DL->BlockCount;I++) |
| DL->D->UnpackPtr->UnpackDecode(DL->D[I]); |
| } |
| |
| |
| void Unpack::InitMT() |
| { |
| if (ReadBufMT==NULL) |
| { |
| // Even getbits32 can read up to 3 additional bytes after current |
| // and our block header and table reading code can look much further. |
| // Let's allocate the additional space here, so we do not need to check |
| // bounds for every bit field access. |
| const size_t Overflow=1024; |
| |
| ReadBufMT=new byte[UNP_READ_SIZE_MT+Overflow]; |
| memset(ReadBufMT,0,UNP_READ_SIZE_MT+Overflow); |
| } |
| if (UnpThreadData==NULL) |
| { |
| uint MaxItems=MaxUserThreads*UNP_BLOCKS_PER_THREAD; |
| UnpThreadData=new UnpackThreadData[MaxItems]; |
| memset(UnpThreadData,0,sizeof(UnpackThreadData)*MaxItems); |
| |
| for (uint I=0;I<MaxItems;I++) |
| { |
| UnpackThreadData *CurData=UnpThreadData+I; |
| if (CurData->Decoded==NULL) |
| { |
| // Typical number of items in RAR blocks does not exceed 0x4000. |
| CurData->DecodedAllocated=0x4100; |
| // It will be freed in the object destructor, not in this file. |
| CurData->Decoded=(UnpackDecodedItem *)malloc(CurData->DecodedAllocated*sizeof(UnpackDecodedItem)); |
| if (CurData->Decoded==NULL) |
| ErrHandler.MemoryError(); |
| } |
| } |
| } |
| } |
| |
| |
| void Unpack::Unpack5MT(bool Solid) |
| { |
| InitMT(); |
| UnpInitData(Solid); |
| |
| for (uint I=0;I<MaxUserThreads*UNP_BLOCKS_PER_THREAD;I++) |
| { |
| UnpackThreadData *CurData=UnpThreadData+I; |
| CurData->LargeBlock=false; |
| CurData->Incomplete=false; |
| } |
| |
| UnpThreadData[0].BlockHeader=BlockHeader; |
| UnpThreadData[0].BlockTables=BlockTables; |
| uint LastBlockNum=0; |
| |
| int DataSize=0; |
| int BlockStart=0; |
| |
| |
| // 'true' if we found a block too large for multithreaded extraction, |
| // so we switched to single threaded mode until the end of file. |
| // Large blocks could cause too high memory use in multithreaded mode. |
| bool LargeBlock=false; |
| |
| bool Done=false; |
| while (!Done) |
| { |
| // Data amount, which is guaranteed to fit block header and tables, |
| // so we can safely read them without additional checks. |
| const int TooSmallToProcess=1024; |
| |
| int ReadSize=UnpIO->UnpRead(ReadBufMT+DataSize,(UNP_READ_SIZE_MT-DataSize)&~0xf); |
| if (ReadSize<0) |
| break; |
| DataSize+=ReadSize; |
| if (DataSize==0) |
| break; |
| |
| // First read chunk can be small if we are near the end of volume |
| // and we want it to fit block header and tables. |
| if (ReadSize>0 && DataSize<TooSmallToProcess) |
| continue; |
| |
| while (BlockStart<DataSize && !Done) |
| { |
| uint BlockNumber=0,BlockNumberMT=0; |
| while (BlockNumber<MaxUserThreads*UNP_BLOCKS_PER_THREAD) |
| { |
| UnpackThreadData *CurData=UnpThreadData+BlockNumber; |
| LastBlockNum=BlockNumber; |
| CurData->UnpackPtr=this; |
| |
| // 'Incomplete' thread is present. This is a thread processing block |
| // in the end of buffer, split between two read operations. |
| if (CurData->Incomplete) |
| CurData->DataSize=DataSize; |
| else |
| { |
| CurData->Inp.SetExternalBuffer(ReadBufMT+BlockStart); |
| CurData->Inp.InitBitInput(); |
| CurData->DataSize=DataSize-BlockStart; |
| if (CurData->DataSize==0) |
| break; |
| CurData->DamagedData=false; |
| CurData->HeaderRead=false; |
| CurData->TableRead=false; |
| } |
| |
| // We should not use 'last block in file' block flag here unless |
| // we'll check the block size, because even if block is last in file, |
| // it can exceed the current buffer and require more reading. |
| CurData->NoDataLeft=(ReadSize==0); |
| |
| CurData->Incomplete=false; |
| CurData->ThreadNumber=BlockNumber; |
| |
| if (!CurData->HeaderRead) |
| { |
| CurData->HeaderRead=true; |
| if (!ReadBlockHeader(CurData->Inp,CurData->BlockHeader) || |
| (!CurData->BlockHeader.TablePresent && !TablesRead5)) |
| { |
| Done=true; |
| break; |
| } |
| TablesRead5=true; |
| } |
| |
| // To prevent too high memory use we switch to single threaded mode |
| // if block exceeds this size. Typically RAR blocks do not exceed |
| // 64 KB, so this protection should not affect most of valid archives. |
| const int LargeBlockSize=0x20000; |
| if (LargeBlock || CurData->BlockHeader.BlockSize>LargeBlockSize) |
| LargeBlock=CurData->LargeBlock=true; |
| else |
| BlockNumberMT++; // Number of normal blocks processed in MT mode. |
| |
| BlockStart+=CurData->BlockHeader.HeaderSize+CurData->BlockHeader.BlockSize; |
| |
| BlockNumber++; |
| |
| int DataLeft=DataSize-BlockStart; |
| if (DataLeft>=0 && CurData->BlockHeader.LastBlockInFile) |
| break; |
| |
| // For second and following threads we move smaller blocks to buffer |
| // start to ensure that we have enough data to fit block header |
| // and tables. |
| if (DataLeft<TooSmallToProcess) |
| break; |
| } |
| |
| //#undef USE_THREADS |
| UnpackThreadDataList UTDArray[MaxPoolThreads]; |
| uint UTDArrayPos=0; |
| |
| uint MaxBlockPerThread=BlockNumberMT/MaxUserThreads; |
| if (BlockNumberMT%MaxUserThreads!=0) |
| MaxBlockPerThread++; |
| |
| // Decode all normal blocks until the first 'large' if any. |
| for (uint CurBlock=0;CurBlock<BlockNumberMT;CurBlock+=MaxBlockPerThread) |
| { |
| UnpackThreadDataList *UTD=UTDArray+UTDArrayPos++; |
| UTD->D=UnpThreadData+CurBlock; |
| UTD->BlockCount=Min(MaxBlockPerThread,BlockNumberMT-CurBlock); |
| |
| #ifdef USE_THREADS |
| if (BlockNumber==1) |
| UnpackDecode(*UTD->D); |
| else |
| UnpThreadPool->AddTask(UnpackDecodeThread,(void*)UTD); |
| #else |
| for (uint I=0;I<UTD->BlockCount;I++) |
| UnpackDecode(UTD->D[I]); |
| #endif |
| } |
| |
| if (BlockNumber==0) |
| break; |
| |
| #ifdef USE_THREADS |
| UnpThreadPool->WaitDone(); |
| #endif |
| |
| bool IncompleteThread=false; |
| |
| for (uint Block=0;Block<BlockNumber;Block++) |
| { |
| UnpackThreadData *CurData=UnpThreadData+Block; |
| if ((!CurData->LargeBlock && !ProcessDecoded(*CurData)) || |
| (CurData->LargeBlock && !UnpackLargeBlock(*CurData)) || |
| CurData->DamagedData) |
| { |
| Done=true; |
| break; |
| } |
| if (CurData->Incomplete) |
| { |
| int BufPos=int(CurData->Inp.InBuf+CurData->Inp.InAddr-ReadBufMT); |
| if (DataSize<=BufPos) // Thread exceeded input buffer boundary. |
| { |
| Done=true; |
| break; |
| } |
| IncompleteThread=true; |
| memmove(ReadBufMT,ReadBufMT+BufPos,DataSize-BufPos); |
| CurData->BlockHeader.BlockSize-=CurData->Inp.InAddr-CurData->BlockHeader.BlockStart; |
| CurData->BlockHeader.HeaderSize=0; |
| CurData->BlockHeader.BlockStart=0; |
| CurData->Inp.InBuf=ReadBufMT; |
| CurData->Inp.InAddr=0; |
| |
| if (Block!=0) |
| { |
| // Move the incomplete thread entry to the first position, |
| // so we'll start processing from it. Preserve the original |
| // buffer for decoded data. |
| UnpackDecodedItem *Decoded=UnpThreadData[0].Decoded; |
| uint DecodedAllocated=UnpThreadData[0].DecodedAllocated; |
| UnpThreadData[0]=*CurData; |
| UnpThreadData[0].Decoded=Decoded; |
| UnpThreadData[0].DecodedAllocated=DecodedAllocated; |
| CurData->Incomplete=false; |
| } |
| |
| BlockStart=0; |
| DataSize-=BufPos; |
| break; |
| } |
| else |
| if (CurData->BlockHeader.LastBlockInFile) |
| { |
| Done=true; |
| break; |
| } |
| } |
| |
| if (IncompleteThread || Done) |
| break; // Current buffer is done, read more data or quit. |
| else |
| { |
| int DataLeft=DataSize-BlockStart; |
| if (DataLeft<TooSmallToProcess) |
| { |
| if (DataLeft<0) // Invalid data, must not happen in valid archive. |
| { |
| Done=true; |
| break; |
| } |
| |
| // If we do not have incomplete thread and have some data |
| // in the end of buffer, too small for single thread, |
| // let's move it to beginning of next buffer. |
| if (DataLeft>0) |
| memmove(ReadBufMT,ReadBufMT+BlockStart,DataLeft); |
| DataSize=DataLeft; |
| BlockStart=0; |
| break; // Current buffer is done, try to read more data. |
| } |
| } |
| } |
| } |
| UnpPtr&=MaxWinMask; // ProcessDecoded and maybe others can leave UnpPtr > MaxWinMask here. |
| UnpWriteBuf(); |
| |
| BlockHeader=UnpThreadData[LastBlockNum].BlockHeader; |
| BlockTables=UnpThreadData[LastBlockNum].BlockTables; |
| } |
| |
| |
| // Decode Huffman block and save decoded data to memory. |
| void Unpack::UnpackDecode(UnpackThreadData &D) |
| { |
| if (!D.TableRead) |
| { |
| D.TableRead=true; |
| if (!ReadTables(D.Inp,D.BlockHeader,D.BlockTables)) |
| { |
| D.DamagedData=true; |
| return; |
| } |
| } |
| |
| if (D.Inp.InAddr>D.BlockHeader.HeaderSize+D.BlockHeader.BlockSize) |
| { |
| D.DamagedData=true; |
| return; |
| } |
| |
| D.DecodedSize=0; |
| int BlockBorder=D.BlockHeader.BlockStart+D.BlockHeader.BlockSize-1; |
| |
| // Reserve enough space even for filter entry. |
| int DataBorder=D.DataSize-16; |
| int ReadBorder=Min(BlockBorder,DataBorder); |
| |
| while (true) |
| { |
| if (D.Inp.InAddr>=ReadBorder) |
| { |
| if (D.Inp.InAddr>BlockBorder || (D.Inp.InAddr==BlockBorder && |
| D.Inp.InBit>=D.BlockHeader.BlockBitSize)) |
| break; |
| |
| // If we do not have any more data in file to read, we must process |
| // what we have until last byte. Otherwise we can return and append |
| // more data to unprocessed few bytes. |
| if ((D.Inp.InAddr>=DataBorder && !D.NoDataLeft) || D.Inp.InAddr>=D.DataSize) |
| { |
| D.Incomplete=true; |
| break; |
| } |
| } |
| if (D.DecodedSize>D.DecodedAllocated-8) // Filter can use several slots. |
| { |
| D.DecodedAllocated=D.DecodedAllocated*2; |
| void *Decoded=realloc(D.Decoded,D.DecodedAllocated*sizeof(UnpackDecodedItem)); |
| if (Decoded==NULL) |
| ErrHandler.MemoryError(); // D.Decoded will be freed in the destructor. |
| D.Decoded=(UnpackDecodedItem *)Decoded; |
| } |
| |
| UnpackDecodedItem *CurItem=D.Decoded+D.DecodedSize++; |
| |
| uint MainSlot=DecodeNumber(D.Inp,&D.BlockTables.LD); |
| if (MainSlot<256) |
| { |
| if (D.DecodedSize>1) |
| { |
| UnpackDecodedItem *PrevItem=CurItem-1; |
| if (PrevItem->Type==UNPDT_LITERAL && PrevItem->Length<3) |
| { |
| PrevItem->Length++; |
| PrevItem->Literal[PrevItem->Length]=(byte)MainSlot; |
| D.DecodedSize--; |
| continue; |
| } |
| } |
| CurItem->Type=UNPDT_LITERAL; |
| CurItem->Literal[0]=(byte)MainSlot; |
| CurItem->Length=0; |
| continue; |
| } |
| if (MainSlot>=262) |
| { |
| uint Length=SlotToLength(D.Inp,MainSlot-262); |
| |
| uint DBits,Distance=1,DistSlot=DecodeNumber(D.Inp,&D.BlockTables.DD); |
| if (DistSlot<4) |
| { |
| DBits=0; |
| Distance+=DistSlot; |
| } |
| else |
| { |
| DBits=DistSlot/2 - 1; |
| Distance+=(2 | (DistSlot & 1)) << DBits; |
| } |
| |
| if (DBits>0) |
| { |
| if (DBits>=4) |
| { |
| if (DBits>4) |
| { |
| Distance+=((D.Inp.getbits32()>>(36-DBits))<<4); |
| D.Inp.addbits(DBits-4); |
| } |
| uint LowDist=DecodeNumber(D.Inp,&D.BlockTables.LDD); |
| Distance+=LowDist; |
| } |
| else |
| { |
| Distance+=D.Inp.getbits32()>>(32-DBits); |
| D.Inp.addbits(DBits); |
| } |
| } |
| |
| if (Distance>0x100) |
| { |
| Length++; |
| if (Distance>0x2000) |
| { |
| Length++; |
| if (Distance>0x40000) |
| Length++; |
| } |
| } |
| |
| CurItem->Type=UNPDT_MATCH; |
| CurItem->Length=(ushort)Length; |
| CurItem->Distance=Distance; |
| continue; |
| } |
| if (MainSlot==256) |
| { |
| UnpackFilter Filter; |
| ReadFilter(D.Inp,Filter); |
| |
| CurItem->Type=UNPDT_FILTER; |
| CurItem->Length=Filter.Type; |
| CurItem->Distance=Filter.BlockStart; |
| |
| CurItem=D.Decoded+D.DecodedSize++; |
| |
| CurItem->Type=UNPDT_FILTER; |
| CurItem->Length=Filter.Channels; |
| CurItem->Distance=Filter.BlockLength; |
| |
| continue; |
| } |
| if (MainSlot==257) |
| { |
| CurItem->Type=UNPDT_FULLREP; |
| continue; |
| } |
| if (MainSlot<262) |
| { |
| CurItem->Type=UNPDT_REP; |
| CurItem->Distance=MainSlot-258; |
| uint LengthSlot=DecodeNumber(D.Inp,&D.BlockTables.RD); |
| uint Length=SlotToLength(D.Inp,LengthSlot); |
| CurItem->Length=(ushort)Length; |
| continue; |
| } |
| } |
| } |
| |
| |
| // Process decoded Huffman block data. |
| bool Unpack::ProcessDecoded(UnpackThreadData &D) |
| { |
| UnpackDecodedItem *Item=D.Decoded,*Border=D.Decoded+D.DecodedSize; |
| while (Item<Border) |
| { |
| UnpPtr&=MaxWinMask; |
| if (((WriteBorder-UnpPtr) & MaxWinMask)<MAX_INC_LZ_MATCH && WriteBorder!=UnpPtr) |
| { |
| UnpWriteBuf(); |
| if (WrittenFileSize>DestUnpSize) |
| return false; |
| } |
| |
| if (Item->Type==UNPDT_LITERAL) |
| { |
| #if defined(LITTLE_ENDIAN) && defined(ALLOW_MISALIGNED) |
| if (Item->Length==3 && UnpPtr<MaxWinSize-4) |
| { |
| *(uint32 *)(Window+UnpPtr)=*(uint32 *)Item->Literal; |
| UnpPtr+=4; |
| } |
| else |
| #endif |
| for (uint I=0;I<=Item->Length;I++) |
| Window[UnpPtr++ & MaxWinMask]=Item->Literal[I]; |
| } |
| else |
| if (Item->Type==UNPDT_MATCH) |
| { |
| InsertOldDist(Item->Distance); |
| LastLength=Item->Length; |
| CopyString(Item->Length,Item->Distance); |
| } |
| else |
| if (Item->Type==UNPDT_REP) |
| { |
| uint Distance=OldDist[Item->Distance]; |
| for (uint I=Item->Distance;I>0;I--) |
| OldDist[I]=OldDist[I-1]; |
| OldDist[0]=Distance; |
| LastLength=Item->Length; |
| CopyString(Item->Length,Distance); |
| } |
| else |
| if (Item->Type==UNPDT_FULLREP) |
| { |
| if (LastLength!=0) |
| CopyString(LastLength,OldDist[0]); |
| } |
| else |
| if (Item->Type==UNPDT_FILTER) |
| { |
| UnpackFilter Filter; |
| |
| Filter.Type=(byte)Item->Length; |
| Filter.BlockStart=Item->Distance; |
| |
| Item++; |
| |
| Filter.Channels=(byte)Item->Length; |
| Filter.BlockLength=Item->Distance; |
| |
| AddFilter(Filter); |
| } |
| Item++; |
| } |
| return true; |
| } |
| |
| |
| // For large blocks we decode and process in same function in single threaded |
| // mode, so we do not need to store intermediate data in memory. |
| bool Unpack::UnpackLargeBlock(UnpackThreadData &D) |
| { |
| if (!D.TableRead) |
| { |
| D.TableRead=true; |
| if (!ReadTables(D.Inp,D.BlockHeader,D.BlockTables)) |
| { |
| D.DamagedData=true; |
| return false; |
| } |
| } |
| |
| if (D.Inp.InAddr>D.BlockHeader.HeaderSize+D.BlockHeader.BlockSize) |
| { |
| D.DamagedData=true; |
| return false; |
| } |
| |
| int BlockBorder=D.BlockHeader.BlockStart+D.BlockHeader.BlockSize-1; |
| |
| // Reserve enough space even for filter entry. |
| int DataBorder=D.DataSize-16; |
| int ReadBorder=Min(BlockBorder,DataBorder); |
| |
| while (true) |
| { |
| UnpPtr&=MaxWinMask; |
| if (D.Inp.InAddr>=ReadBorder) |
| { |
| if (D.Inp.InAddr>BlockBorder || (D.Inp.InAddr==BlockBorder && |
| D.Inp.InBit>=D.BlockHeader.BlockBitSize)) |
| break; |
| |
| // If we do not have any more data in file to read, we must process |
| // what we have until last byte. Otherwise we can return and append |
| // more data to unprocessed few bytes. |
| if ((D.Inp.InAddr>=DataBorder && !D.NoDataLeft) || D.Inp.InAddr>=D.DataSize) |
| { |
| D.Incomplete=true; |
| break; |
| } |
| } |
| if (((WriteBorder-UnpPtr) & MaxWinMask)<MAX_INC_LZ_MATCH && WriteBorder!=UnpPtr) |
| { |
| UnpWriteBuf(); |
| if (WrittenFileSize>DestUnpSize) |
| return false; |
| } |
| |
| uint MainSlot=DecodeNumber(D.Inp,&D.BlockTables.LD); |
| if (MainSlot<256) |
| { |
| Window[UnpPtr++]=(byte)MainSlot; |
| continue; |
| } |
| if (MainSlot>=262) |
| { |
| uint Length=SlotToLength(D.Inp,MainSlot-262); |
| |
| uint DBits,Distance=1,DistSlot=DecodeNumber(D.Inp,&D.BlockTables.DD); |
| if (DistSlot<4) |
| { |
| DBits=0; |
| Distance+=DistSlot; |
| } |
| else |
| { |
| DBits=DistSlot/2 - 1; |
| Distance+=(2 | (DistSlot & 1)) << DBits; |
| } |
| |
| if (DBits>0) |
| { |
| if (DBits>=4) |
| { |
| if (DBits>4) |
| { |
| Distance+=((D.Inp.getbits32()>>(36-DBits))<<4); |
| D.Inp.addbits(DBits-4); |
| } |
| uint LowDist=DecodeNumber(D.Inp,&D.BlockTables.LDD); |
| Distance+=LowDist; |
| } |
| else |
| { |
| Distance+=D.Inp.getbits32()>>(32-DBits); |
| D.Inp.addbits(DBits); |
| } |
| } |
| |
| if (Distance>0x100) |
| { |
| Length++; |
| if (Distance>0x2000) |
| { |
| Length++; |
| if (Distance>0x40000) |
| Length++; |
| } |
| } |
| |
| InsertOldDist(Distance); |
| LastLength=Length; |
| CopyString(Length,Distance); |
| continue; |
| } |
| if (MainSlot==256) |
| { |
| UnpackFilter Filter; |
| if (!ReadFilter(D.Inp,Filter) || !AddFilter(Filter)) |
| break; |
| continue; |
| } |
| if (MainSlot==257) |
| { |
| if (LastLength!=0) |
| CopyString(LastLength,OldDist[0]); |
| continue; |
| } |
| if (MainSlot<262) |
| { |
| uint DistNum=MainSlot-258; |
| uint Distance=OldDist[DistNum]; |
| for (uint I=DistNum;I>0;I--) |
| OldDist[I]=OldDist[I-1]; |
| OldDist[0]=Distance; |
| |
| uint LengthSlot=DecodeNumber(D.Inp,&D.BlockTables.RD); |
| uint Length=SlotToLength(D.Inp,LengthSlot); |
| LastLength=Length; |
| CopyString(Length,Distance); |
| continue; |
| } |
| } |
| return true; |
| } |
| |
| } // namespace third_party_unrar |