Unpack5(bool Solid)1 void Unpack::Unpack5(bool Solid)
2 {
3 FileExtracted=true;
4
5 if (!Suspended)
6 {
7 UnpInitData(Solid);
8 if (!UnpReadBuf())
9 return;
10
11 // Check TablesRead5 to be sure that we read tables at least once
12 // regardless of current block header TablePresent flag.
13 // So we can safefly use these tables below.
14 if (!ReadBlockHeader(Inp,BlockHeader) ||
15 !ReadTables(Inp,BlockHeader,BlockTables) || !TablesRead5)
16 return;
17 }
18
19 while (true)
20 {
21 UnpPtr&=MaxWinMask;
22
23 if (Inp.InAddr>=ReadBorder)
24 {
25 bool FileDone=false;
26
27 // We use 'while', because for empty block containing only Huffman table,
28 // we'll be on the block border once again just after reading the table.
29 while (Inp.InAddr>BlockHeader.BlockStart+BlockHeader.BlockSize-1 ||
30 Inp.InAddr==BlockHeader.BlockStart+BlockHeader.BlockSize-1 &&
31 Inp.InBit>=BlockHeader.BlockBitSize)
32 {
33 if (BlockHeader.LastBlockInFile)
34 {
35 FileDone=true;
36 break;
37 }
38 if (!ReadBlockHeader(Inp,BlockHeader) || !ReadTables(Inp,BlockHeader,BlockTables))
39 return;
40 }
41 if (FileDone || !UnpReadBuf())
42 break;
43 }
44
45 if (((WriteBorder-UnpPtr) & MaxWinMask)<MAX_INC_LZ_MATCH && WriteBorder!=UnpPtr)
46 {
47 UnpWriteBuf();
48 if (WrittenFileSize>DestUnpSize)
49 return;
50 if (Suspended)
51 {
52 FileExtracted=false;
53 return;
54 }
55 }
56
57 uint MainSlot=DecodeNumber(Inp,&BlockTables.LD);
58 if (MainSlot<256)
59 {
60 if (Fragmented)
61 FragWindow[UnpPtr++]=(byte)MainSlot;
62 else
63 Window[UnpPtr++]=(byte)MainSlot;
64 continue;
65 }
66 if (MainSlot>=262)
67 {
68 uint Length=SlotToLength(Inp,MainSlot-262);
69
70 uint DBits,Distance=1,DistSlot=DecodeNumber(Inp,&BlockTables.DD);
71 if (DistSlot<4)
72 {
73 DBits=0;
74 Distance+=DistSlot;
75 }
76 else
77 {
78 DBits=DistSlot/2 - 1;
79 Distance+=(2 | (DistSlot & 1)) << DBits;
80 }
81
82 if (DBits>0)
83 {
84 if (DBits>=4)
85 {
86 if (DBits>4)
87 {
88 Distance+=((Inp.getbits32()>>(36-DBits))<<4);
89 Inp.addbits(DBits-4);
90 }
91 uint LowDist=DecodeNumber(Inp,&BlockTables.LDD);
92 Distance+=LowDist;
93 }
94 else
95 {
96 Distance+=Inp.getbits32()>>(32-DBits);
97 Inp.addbits(DBits);
98 }
99 }
100
101 if (Distance>0x100)
102 {
103 Length++;
104 if (Distance>0x2000)
105 {
106 Length++;
107 if (Distance>0x40000)
108 Length++;
109 }
110 }
111
112 InsertOldDist(Distance);
113 LastLength=Length;
114 if (Fragmented)
115 FragWindow.CopyString(Length,Distance,UnpPtr,MaxWinMask);
116 else
117 CopyString(Length,Distance);
118 continue;
119 }
120 if (MainSlot==256)
121 {
122 UnpackFilter Filter;
123 if (!ReadFilter(Inp,Filter) || !AddFilter(Filter))
124 break;
125 continue;
126 }
127 if (MainSlot==257)
128 {
129 if (LastLength!=0)
130 if (Fragmented)
131 FragWindow.CopyString(LastLength,OldDist[0],UnpPtr,MaxWinMask);
132 else
133 CopyString(LastLength,OldDist[0]);
134 continue;
135 }
136 if (MainSlot<262)
137 {
138 uint DistNum=MainSlot-258;
139 uint Distance=OldDist[DistNum];
140 for (uint I=DistNum;I>0;I--)
141 OldDist[I]=OldDist[I-1];
142 OldDist[0]=Distance;
143
144 uint LengthSlot=DecodeNumber(Inp,&BlockTables.RD);
145 uint Length=SlotToLength(Inp,LengthSlot);
146 LastLength=Length;
147 if (Fragmented)
148 FragWindow.CopyString(Length,Distance,UnpPtr,MaxWinMask);
149 else
150 CopyString(Length,Distance);
151 continue;
152 }
153 }
154 UnpWriteBuf();
155 }
156
157
ReadFilterData(BitInput & Inp)158 uint Unpack::ReadFilterData(BitInput &Inp)
159 {
160 uint ByteCount=(Inp.fgetbits()>>14)+1;
161 Inp.addbits(2);
162
163 uint Data=0;
164 for (uint I=0;I<ByteCount;I++)
165 {
166 Data+=(Inp.fgetbits()>>8)<<(I*8);
167 Inp.addbits(8);
168 }
169 return Data;
170 }
171
172
ReadFilter(BitInput & Inp,UnpackFilter & Filter)173 bool Unpack::ReadFilter(BitInput &Inp,UnpackFilter &Filter)
174 {
175 if (!Inp.ExternalBuffer && Inp.InAddr>ReadTop-16)
176 if (!UnpReadBuf())
177 return false;
178
179 Filter.BlockStart=ReadFilterData(Inp);
180 Filter.BlockLength=ReadFilterData(Inp);
181 if (Filter.BlockLength>MAX_FILTER_BLOCK_SIZE)
182 Filter.BlockLength=0;
183
184 Filter.Type=Inp.fgetbits()>>13;
185 Inp.faddbits(3);
186
187 if (Filter.Type==FILTER_DELTA)
188 {
189 Filter.Channels=(Inp.fgetbits()>>11)+1;
190 Inp.faddbits(5);
191 }
192
193 return true;
194 }
195
196
AddFilter(UnpackFilter & Filter)197 bool Unpack::AddFilter(UnpackFilter &Filter)
198 {
199 if (Filters.Size()>=MAX_UNPACK_FILTERS)
200 {
201 UnpWriteBuf(); // Write data, apply and flush filters.
202 if (Filters.Size()>=MAX_UNPACK_FILTERS)
203 InitFilters(); // Still too many filters, prevent excessive memory use.
204 }
205
206 // If distance to filter start is that large that due to circular dictionary
207 // mode now it points to old not written yet data, then we set 'NextWindow'
208 // flag and process this filter only after processing that older data.
209 Filter.NextWindow=WrPtr!=UnpPtr && ((WrPtr-UnpPtr)&MaxWinMask)<=Filter.BlockStart;
210
211 Filter.BlockStart=uint((Filter.BlockStart+UnpPtr)&MaxWinMask);
212 Filters.Push(Filter);
213 return true;
214 }
215
216
UnpReadBuf()217 bool Unpack::UnpReadBuf()
218 {
219 int DataSize=ReadTop-Inp.InAddr; // Data left to process.
220 if (DataSize<0)
221 return false;
222 BlockHeader.BlockSize-=Inp.InAddr-BlockHeader.BlockStart;
223 if (Inp.InAddr>BitInput::MAX_SIZE/2)
224 {
225 // If we already processed more than half of buffer, let's move
226 // remaining data into beginning to free more space for new data
227 // and ensure that calling function does not cross the buffer border
228 // even if we did not read anything here. Also it ensures that read size
229 // is not less than CRYPT_BLOCK_SIZE, so we can align it without risk
230 // to make it zero.
231 if (DataSize>0)
232 memmove(Inp.InBuf,Inp.InBuf+Inp.InAddr,DataSize);
233 Inp.InAddr=0;
234 ReadTop=DataSize;
235 }
236 else
237 DataSize=ReadTop;
238 int ReadCode=0;
239 if (BitInput::MAX_SIZE!=DataSize)
240 ReadCode=UnpIO->UnpRead(Inp.InBuf+DataSize,BitInput::MAX_SIZE-DataSize);
241 if (ReadCode>0) // Can be also -1.
242 ReadTop+=ReadCode;
243 ReadBorder=ReadTop-30;
244 BlockHeader.BlockStart=Inp.InAddr;
245 if (BlockHeader.BlockSize!=-1) // '-1' means not defined yet.
246 {
247 // We may need to quit from main extraction loop and read new block header
248 // and trees earlier than data in input buffer ends.
249 ReadBorder=Min(ReadBorder,BlockHeader.BlockStart+BlockHeader.BlockSize-1);
250 }
251 return ReadCode!=-1;
252 }
253
254
UnpWriteBuf()255 void Unpack::UnpWriteBuf()
256 {
257 size_t WrittenBorder=WrPtr;
258 size_t FullWriteSize=(UnpPtr-WrittenBorder)&MaxWinMask;
259 size_t WriteSizeLeft=FullWriteSize;
260 bool NotAllFiltersProcessed=false;
261 for (size_t I=0;I<Filters.Size();I++)
262 {
263 // Here we apply filters to data which we need to write.
264 // We always copy data to another memory block before processing.
265 // We cannot process them just in place in Window buffer, because
266 // these data can be used for future string matches, so we must
267 // preserve them in original form.
268
269 UnpackFilter *flt=&Filters[I];
270 if (flt->Type==FILTER_NONE)
271 continue;
272 if (flt->NextWindow)
273 {
274 // Here we skip filters which have block start in current data range
275 // due to address wrap around in circular dictionary, but actually
276 // belong to next dictionary block. If such filter start position
277 // is included to current write range, then we reset 'NextWindow' flag.
278 // In fact we can reset it even without such check, because current
279 // implementation seems to guarantee 'NextWindow' flag reset after
280 // buffer writing for all existing filters. But let's keep this check
281 // just in case. Compressor guarantees that distance between
282 // filter block start and filter storing position cannot exceed
283 // the dictionary size. So if we covered the filter block start with
284 // our write here, we can safely assume that filter is applicable
285 // to next block on no further wrap arounds is possible.
286 if (((flt->BlockStart-WrPtr)&MaxWinMask)<=FullWriteSize)
287 flt->NextWindow=false;
288 continue;
289 }
290 uint BlockStart=flt->BlockStart;
291 uint BlockLength=flt->BlockLength;
292 if (((BlockStart-WrittenBorder)&MaxWinMask)<WriteSizeLeft)
293 {
294 if (WrittenBorder!=BlockStart)
295 {
296 UnpWriteArea(WrittenBorder,BlockStart);
297 WrittenBorder=BlockStart;
298 WriteSizeLeft=(UnpPtr-WrittenBorder)&MaxWinMask;
299 }
300 if (BlockLength<=WriteSizeLeft)
301 {
302 if (BlockLength>0) // We set it to 0 also for invalid filters.
303 {
304 uint BlockEnd=(BlockStart+BlockLength)&MaxWinMask;
305
306 FilterSrcMemory.Alloc(BlockLength);
307 byte *Mem=&FilterSrcMemory[0];
308 if (BlockStart<BlockEnd || BlockEnd==0)
309 {
310 if (Fragmented)
311 FragWindow.CopyData(Mem,BlockStart,BlockLength);
312 else
313 memcpy(Mem,Window+BlockStart,BlockLength);
314 }
315 else
316 {
317 size_t FirstPartLength=size_t(MaxWinSize-BlockStart);
318 if (Fragmented)
319 {
320 FragWindow.CopyData(Mem,BlockStart,FirstPartLength);
321 FragWindow.CopyData(Mem+FirstPartLength,0,BlockEnd);
322 }
323 else
324 {
325 memcpy(Mem,Window+BlockStart,FirstPartLength);
326 memcpy(Mem+FirstPartLength,Window,BlockEnd);
327 }
328 }
329
330 byte *OutMem=ApplyFilter(Mem,BlockLength,flt);
331
332 Filters[I].Type=FILTER_NONE;
333
334 if (OutMem!=NULL)
335 UnpIO->UnpWrite(OutMem,BlockLength);
336
337 UnpSomeRead=true;
338 WrittenFileSize+=BlockLength;
339 WrittenBorder=BlockEnd;
340 WriteSizeLeft=(UnpPtr-WrittenBorder)&MaxWinMask;
341 }
342 }
343 else
344 {
345 // Current filter intersects the window write border, so we adjust
346 // the window border to process this filter next time, not now.
347 WrPtr=WrittenBorder;
348
349 // Since Filter start position can only increase, we quit processing
350 // all following filters for this data block and reset 'NextWindow'
351 // flag for them.
352 for (size_t J=I;J<Filters.Size();J++)
353 {
354 UnpackFilter *flt=&Filters[J];
355 if (flt->Type!=FILTER_NONE)
356 flt->NextWindow=false;
357 }
358
359 // Do not write data left after current filter now.
360 NotAllFiltersProcessed=true;
361 break;
362 }
363 }
364 }
365
366 // Remove processed filters from queue.
367 size_t EmptyCount=0;
368 for (size_t I=0;I<Filters.Size();I++)
369 {
370 if (EmptyCount>0)
371 Filters[I-EmptyCount]=Filters[I];
372 if (Filters[I].Type==FILTER_NONE)
373 EmptyCount++;
374 }
375 if (EmptyCount>0)
376 Filters.Alloc(Filters.Size()-EmptyCount);
377
378 if (!NotAllFiltersProcessed) // Only if all filters are processed.
379 {
380 // Write data left after last filter.
381 UnpWriteArea(WrittenBorder,UnpPtr);
382 WrPtr=UnpPtr;
383 }
384
385 // We prefer to write data in blocks not exceeding UNPACK_MAX_WRITE
386 // instead of potentially huge MaxWinSize blocks. It also allows us
387 // to keep the size of Filters array reasonable.
388 WriteBorder=(UnpPtr+Min(MaxWinSize,UNPACK_MAX_WRITE))&MaxWinMask;
389
390 // Choose the nearest among WriteBorder and WrPtr actual written border.
391 // If border is equal to UnpPtr, it means that we have MaxWinSize data ahead.
392 if (WriteBorder==UnpPtr ||
393 WrPtr!=UnpPtr && ((WrPtr-UnpPtr)&MaxWinMask)<((WriteBorder-UnpPtr)&MaxWinMask))
394 WriteBorder=WrPtr;
395 }
396
397
ApplyFilter(byte * Data,uint DataSize,UnpackFilter * Flt)398 byte* Unpack::ApplyFilter(byte *Data,uint DataSize,UnpackFilter *Flt)
399 {
400 byte *SrcData=Data;
401 switch(Flt->Type)
402 {
403 case FILTER_E8:
404 case FILTER_E8E9:
405 {
406 uint FileOffset=(uint)WrittenFileSize;
407
408 const uint FileSize=0x1000000;
409 byte CmpByte2=Flt->Type==FILTER_E8E9 ? 0xe9:0xe8;
410 // DataSize is unsigned, so we use "CurPos+4" and not "DataSize-4"
411 // to avoid overflow for DataSize<4.
412 for (uint CurPos=0;CurPos+4<DataSize;)
413 {
414 byte CurByte=*(Data++);
415 CurPos++;
416 if (CurByte==0xe8 || CurByte==CmpByte2)
417 {
418 uint Offset=(CurPos+FileOffset)%FileSize;
419 uint Addr=RawGet4(Data);
420
421 // We check 0x80000000 bit instead of '< 0' comparison
422 // not assuming int32 presence or uint size and endianness.
423 if ((Addr & 0x80000000)!=0) // Addr<0
424 {
425 if (((Addr+Offset) & 0x80000000)==0) // Addr+Offset>=0
426 RawPut4(Addr+FileSize,Data);
427 }
428 else
429 if (((Addr-FileSize) & 0x80000000)!=0) // Addr<FileSize
430 RawPut4(Addr-Offset,Data);
431
432 Data+=4;
433 CurPos+=4;
434 }
435 }
436 }
437 return SrcData;
438 case FILTER_ARM:
439 {
440 uint FileOffset=(uint)WrittenFileSize;
441 // DataSize is unsigned, so we use "CurPos+3" and not "DataSize-3"
442 // to avoid overflow for DataSize<3.
443 for (uint CurPos=0;CurPos+3<DataSize;CurPos+=4)
444 {
445 byte *D=Data+CurPos;
446 if (D[3]==0xeb) // BL command with '1110' (Always) condition.
447 {
448 uint Offset=D[0]+uint(D[1])*0x100+uint(D[2])*0x10000;
449 Offset-=(FileOffset+CurPos)/4;
450 D[0]=(byte)Offset;
451 D[1]=(byte)(Offset>>8);
452 D[2]=(byte)(Offset>>16);
453 }
454 }
455 }
456 return SrcData;
457 case FILTER_DELTA:
458 {
459 // Unlike RAR3, we do not need to reject excessive channel
460 // values here, since RAR5 uses only 5 bits to store channel.
461 uint Channels=Flt->Channels,SrcPos=0;
462
463 FilterDstMemory.Alloc(DataSize);
464 byte *DstData=&FilterDstMemory[0];
465
466 // Bytes from same channels are grouped to continual data blocks,
467 // so we need to place them back to their interleaving positions.
468 for (uint CurChannel=0;CurChannel<Channels;CurChannel++)
469 {
470 byte PrevByte=0;
471 for (uint DestPos=CurChannel;DestPos<DataSize;DestPos+=Channels)
472 DstData[DestPos]=(PrevByte-=Data[SrcPos++]);
473 }
474 return DstData;
475 }
476
477 }
478 return NULL;
479 }
480
481
UnpWriteArea(size_t StartPtr,size_t EndPtr)482 void Unpack::UnpWriteArea(size_t StartPtr,size_t EndPtr)
483 {
484 if (EndPtr!=StartPtr)
485 UnpSomeRead=true;
486 if (EndPtr<StartPtr)
487 UnpAllBuf=true;
488
489 if (Fragmented)
490 {
491 size_t SizeToWrite=(EndPtr-StartPtr) & MaxWinMask;
492 while (SizeToWrite>0)
493 {
494 size_t BlockSize=FragWindow.GetBlockSize(StartPtr,SizeToWrite);
495 UnpWriteData(&FragWindow[StartPtr],BlockSize);
496 SizeToWrite-=BlockSize;
497 StartPtr=(StartPtr+BlockSize) & MaxWinMask;
498 }
499 }
500 else
501 if (EndPtr<StartPtr)
502 {
503 UnpWriteData(Window+StartPtr,MaxWinSize-StartPtr);
504 UnpWriteData(Window,EndPtr);
505 }
506 else
507 UnpWriteData(Window+StartPtr,EndPtr-StartPtr);
508 }
509
510
UnpWriteData(byte * Data,size_t Size)511 void Unpack::UnpWriteData(byte *Data,size_t Size)
512 {
513 if (WrittenFileSize>=DestUnpSize)
514 return;
515 size_t WriteSize=Size;
516 int64 LeftToWrite=DestUnpSize-WrittenFileSize;
517 if ((int64)WriteSize>LeftToWrite)
518 WriteSize=(size_t)LeftToWrite;
519 UnpIO->UnpWrite(Data,WriteSize);
520 WrittenFileSize+=Size;
521 }
522
523
UnpInitData50(bool Solid)524 void Unpack::UnpInitData50(bool Solid)
525 {
526 if (!Solid)
527 TablesRead5=false;
528 }
529
530
ReadBlockHeader(BitInput & Inp,UnpackBlockHeader & Header)531 bool Unpack::ReadBlockHeader(BitInput &Inp,UnpackBlockHeader &Header)
532 {
533 Header.HeaderSize=0;
534
535 if (!Inp.ExternalBuffer && Inp.InAddr>ReadTop-7)
536 if (!UnpReadBuf())
537 return false;
538 Inp.faddbits((8-Inp.InBit)&7);
539
540 byte BlockFlags=Inp.fgetbits()>>8;
541 Inp.faddbits(8);
542 uint ByteCount=((BlockFlags>>3)&3)+1; // Block size byte count.
543
544 if (ByteCount==4)
545 return false;
546
547 Header.HeaderSize=2+ByteCount;
548
549 Header.BlockBitSize=(BlockFlags&7)+1;
550
551 byte SavedCheckSum=Inp.fgetbits()>>8;
552 Inp.faddbits(8);
553
554 int BlockSize=0;
555 for (uint I=0;I<ByteCount;I++)
556 {
557 BlockSize+=(Inp.fgetbits()>>8)<<(I*8);
558 Inp.addbits(8);
559 }
560
561 Header.BlockSize=BlockSize;
562 byte CheckSum=byte(0x5a^BlockFlags^BlockSize^(BlockSize>>8)^(BlockSize>>16));
563 if (CheckSum!=SavedCheckSum)
564 return false;
565
566 Header.BlockStart=Inp.InAddr;
567 ReadBorder=Min(ReadBorder,Header.BlockStart+Header.BlockSize-1);
568
569 Header.LastBlockInFile=(BlockFlags & 0x40)!=0;
570 Header.TablePresent=(BlockFlags & 0x80)!=0;
571 return true;
572 }
573
574
ReadTables(BitInput & Inp,UnpackBlockHeader & Header,UnpackBlockTables & Tables)575 bool Unpack::ReadTables(BitInput &Inp,UnpackBlockHeader &Header,UnpackBlockTables &Tables)
576 {
577 if (!Header.TablePresent)
578 return true;
579
580 if (!Inp.ExternalBuffer && Inp.InAddr>ReadTop-25)
581 if (!UnpReadBuf())
582 return false;
583
584 byte BitLength[BC];
585 for (uint I=0;I<BC;I++)
586 {
587 uint Length=(byte)(Inp.fgetbits() >> 12);
588 Inp.faddbits(4);
589 if (Length==15)
590 {
591 uint ZeroCount=(byte)(Inp.fgetbits() >> 12);
592 Inp.faddbits(4);
593 if (ZeroCount==0)
594 BitLength[I]=15;
595 else
596 {
597 ZeroCount+=2;
598 while (ZeroCount-- > 0 && I<ASIZE(BitLength))
599 BitLength[I++]=0;
600 I--;
601 }
602 }
603 else
604 BitLength[I]=Length;
605 }
606
607 MakeDecodeTables(BitLength,&Tables.BD,BC);
608
609 byte Table[HUFF_TABLE_SIZE];
610 const uint TableSize=HUFF_TABLE_SIZE;
611 for (uint I=0;I<TableSize;)
612 {
613 if (!Inp.ExternalBuffer && Inp.InAddr>ReadTop-5)
614 if (!UnpReadBuf())
615 return false;
616 uint Number=DecodeNumber(Inp,&Tables.BD);
617 if (Number<16)
618 {
619 Table[I]=Number;
620 I++;
621 }
622 else
623 if (Number<18)
624 {
625 uint N;
626 if (Number==16)
627 {
628 N=(Inp.fgetbits() >> 13)+3;
629 Inp.faddbits(3);
630 }
631 else
632 {
633 N=(Inp.fgetbits() >> 9)+11;
634 Inp.faddbits(7);
635 }
636 if (I==0)
637 {
638 // We cannot have "repeat previous" code at the first position.
639 // Multiple such codes would shift Inp position without changing I,
640 // which can lead to reading beyond of Inp boundary in mutithreading
641 // mode, where Inp.ExternalBuffer disables bounds check and we just
642 // reserve a lot of buffer space to not need such check normally.
643 return false;
644 }
645 else
646 while (N-- > 0 && I<TableSize)
647 {
648 Table[I]=Table[I-1];
649 I++;
650 }
651 }
652 else
653 {
654 uint N;
655 if (Number==18)
656 {
657 N=(Inp.fgetbits() >> 13)+3;
658 Inp.faddbits(3);
659 }
660 else
661 {
662 N=(Inp.fgetbits() >> 9)+11;
663 Inp.faddbits(7);
664 }
665 while (N-- > 0 && I<TableSize)
666 Table[I++]=0;
667 }
668 }
669 TablesRead5=true;
670 if (!Inp.ExternalBuffer && Inp.InAddr>ReadTop)
671 return false;
672 MakeDecodeTables(&Table[0],&Tables.LD,NC);
673 MakeDecodeTables(&Table[NC],&Tables.DD,DC);
674 MakeDecodeTables(&Table[NC+DC],&Tables.LDD,LDC);
675 MakeDecodeTables(&Table[NC+DC+LDC],&Tables.RD,RC);
676 return true;
677 }
678
679
InitFilters()680 void Unpack::InitFilters()
681 {
682 Filters.SoftReset();
683 }
684