#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;
}