1 #define STARTL1 2
2 static unsigned int DecL1[]={0x8000,0xa000,0xc000,0xd000,0xe000,0xea00,
3 0xee00,0xf000,0xf200,0xf200,0xffff};
4 static unsigned int PosL1[]={0,0,0,2,3,5,7,11,16,20,24,32,32};
5
6 #define STARTL2 3
7 static unsigned int DecL2[]={0xa000,0xc000,0xd000,0xe000,0xea00,0xee00,
8 0xf000,0xf200,0xf240,0xffff};
9 static unsigned int PosL2[]={0,0,0,0,5,7,9,13,18,22,26,34,36};
10
11 #define STARTHF0 4
12 static unsigned int DecHf0[]={0x8000,0xc000,0xe000,0xf200,0xf200,0xf200,
13 0xf200,0xf200,0xffff};
14 static unsigned int PosHf0[]={0,0,0,0,0,8,16,24,33,33,33,33,33};
15
16
17 #define STARTHF1 5
18 static unsigned int DecHf1[]={0x2000,0xc000,0xe000,0xf000,0xf200,0xf200,
19 0xf7e0,0xffff};
20 static unsigned int PosHf1[]={0,0,0,0,0,0,4,44,60,76,80,80,127};
21
22
23 #define STARTHF2 5
24 static unsigned int DecHf2[]={0x1000,0x2400,0x8000,0xc000,0xfa00,0xffff,
25 0xffff,0xffff};
26 static unsigned int PosHf2[]={0,0,0,0,0,0,2,7,53,117,233,0,0};
27
28
29 #define STARTHF3 6
30 static unsigned int DecHf3[]={0x800,0x2400,0xee00,0xfe80,0xffff,0xffff,
31 0xffff};
32 static unsigned int PosHf3[]={0,0,0,0,0,0,0,2,16,218,251,0,0};
33
34
35 #define STARTHF4 8
36 static unsigned int DecHf4[]={0xff00,0xffff,0xffff,0xffff,0xffff,0xffff};
37 static unsigned int PosHf4[]={0,0,0,0,0,0,0,0,0,255,0,0,0};
38
39
Unpack15(bool Solid,bool SuspendAfterInit)40 void Unpack::Unpack15(bool Solid,bool SuspendAfterInit)
41 {
42 UnpInitData(Solid);
43 UnpInitData15(Solid);
44 UnpReadBuf();
45 if (!Solid)
46 {
47 InitHuff();
48 UnpPtr=0;
49 }
50 else
51 UnpPtr=WrPtr;
52 --DestUnpSize;
53
54 if (SuspendAfterInit)
55 Suspended = true;
56
57 if (DestUnpSize>=0)
58 {
59 GetFlagsBuf();
60 FlagsCnt=8;
61 }
62
63 while (DestUnpSize>=0)
64 {
65 UnpPtr&=MaxWinMask;
66
67 if (Inp.InAddr>ReadTop-30 && !UnpReadBuf())
68 break;
69 if (((WrPtr-UnpPtr) & MaxWinMask)<270 && WrPtr!=UnpPtr)
70 UnpWriteBuf20();
71 if (StMode)
72 {
73 HuffDecode();
74 continue;
75 }
76
77 if (--FlagsCnt < 0)
78 {
79 GetFlagsBuf();
80 FlagsCnt=7;
81 }
82
83 if (FlagBuf & 0x80)
84 {
85 FlagBuf<<=1;
86 if (Nlzb > Nhfb)
87 LongLZ();
88 else
89 HuffDecode();
90 }
91 else
92 {
93 FlagBuf<<=1;
94 if (--FlagsCnt < 0)
95 {
96 GetFlagsBuf();
97 FlagsCnt=7;
98 }
99 if (FlagBuf & 0x80)
100 {
101 FlagBuf<<=1;
102 if (Nlzb > Nhfb)
103 HuffDecode();
104 else
105 LongLZ();
106 }
107 else
108 {
109 FlagBuf<<=1;
110 ShortLZ();
111 }
112 }
113 }
114 UnpWriteBuf20();
115 }
116
117
118 #define GetShortLen1(pos) ((pos)==1 ? Buf60+3:ShortLen1[pos])
119 #define GetShortLen2(pos) ((pos)==3 ? Buf60+3:ShortLen2[pos])
120
ShortLZ()121 void Unpack::ShortLZ()
122 {
123 static unsigned int ShortLen1[]={1,3,4,4,5,6,7,8,8,4,4,5,6,6,4,0};
124 static unsigned int ShortXor1[]={0,0xa0,0xd0,0xe0,0xf0,0xf8,0xfc,0xfe,
125 0xff,0xc0,0x80,0x90,0x98,0x9c,0xb0};
126 static unsigned int ShortLen2[]={2,3,3,3,4,4,5,6,6,4,4,5,6,6,4,0};
127 static unsigned int ShortXor2[]={0,0x40,0x60,0xa0,0xd0,0xe0,0xf0,0xf8,
128 0xfc,0xc0,0x80,0x90,0x98,0x9c,0xb0};
129
130
131 unsigned int Length,SaveLength;
132 unsigned int LastDistance;
133 unsigned int Distance;
134 int DistancePlace;
135 NumHuf=0;
136
137 unsigned int BitField=Inp.fgetbits();
138 if (LCount==2)
139 {
140 Inp.faddbits(1);
141 if (BitField >= 0x8000)
142 {
143 CopyString15((unsigned int)LastDist,LastLength);
144 return;
145 }
146 BitField <<= 1;
147 LCount=0;
148 }
149
150 BitField>>=8;
151
152 // not thread safe, replaced by GetShortLen1 and GetShortLen2 macro
153 // ShortLen1[1]=ShortLen2[3]=Buf60+3;
154
155 if (AvrLn1<37)
156 {
157 for (Length=0;;Length++)
158 if (((BitField^ShortXor1[Length]) & (~(0xff>>GetShortLen1(Length))))==0)
159 break;
160 Inp.faddbits(GetShortLen1(Length));
161 }
162 else
163 {
164 for (Length=0;;Length++)
165 if (((BitField^ShortXor2[Length]) & (~(0xff>>GetShortLen2(Length))))==0)
166 break;
167 Inp.faddbits(GetShortLen2(Length));
168 }
169
170 if (Length >= 9)
171 {
172 if (Length == 9)
173 {
174 LCount++;
175 CopyString15((unsigned int)LastDist,LastLength);
176 return;
177 }
178 if (Length == 14)
179 {
180 LCount=0;
181 Length=DecodeNum(Inp.fgetbits(),STARTL2,DecL2,PosL2)+5;
182 Distance=(Inp.fgetbits()>>1) | 0x8000;
183 Inp.faddbits(15);
184 LastLength=Length;
185 LastDist=Distance;
186 CopyString15(Distance,Length);
187 return;
188 }
189
190 LCount=0;
191 SaveLength=Length;
192 Distance=OldDist[(OldDistPtr-(Length-9)) & 3];
193 Length=DecodeNum(Inp.fgetbits(),STARTL1,DecL1,PosL1)+2;
194 if (Length==0x101 && SaveLength==10)
195 {
196 Buf60 ^= 1;
197 return;
198 }
199 if (Distance > 256)
200 Length++;
201 if (Distance >= MaxDist3)
202 Length++;
203
204 OldDist[OldDistPtr++]=Distance;
205 OldDistPtr = OldDistPtr & 3;
206 LastLength=Length;
207 LastDist=Distance;
208 CopyString15(Distance,Length);
209 return;
210 }
211
212 LCount=0;
213 AvrLn1 += Length;
214 AvrLn1 -= AvrLn1 >> 4;
215
216 DistancePlace=DecodeNum(Inp.fgetbits(),STARTHF2,DecHf2,PosHf2) & 0xff;
217 Distance=ChSetA[DistancePlace];
218 if (--DistancePlace != -1)
219 {
220 LastDistance=ChSetA[DistancePlace];
221 ChSetA[DistancePlace+1]=LastDistance;
222 ChSetA[DistancePlace]=Distance;
223 }
224 Length+=2;
225 OldDist[OldDistPtr++] = ++Distance;
226 OldDistPtr = OldDistPtr & 3;
227 LastLength=Length;
228 LastDist=Distance;
229 CopyString15(Distance,Length);
230 }
231
232
LongLZ()233 void Unpack::LongLZ()
234 {
235 unsigned int Length;
236 unsigned int Distance;
237 unsigned int DistancePlace,NewDistancePlace;
238 unsigned int OldAvr2,OldAvr3;
239
240 NumHuf=0;
241 Nlzb+=16;
242 if (Nlzb > 0xff)
243 {
244 Nlzb=0x90;
245 Nhfb >>= 1;
246 }
247 OldAvr2=AvrLn2;
248
249 unsigned int BitField=Inp.fgetbits();
250 if (AvrLn2 >= 122)
251 Length=DecodeNum(BitField,STARTL2,DecL2,PosL2);
252 else
253 if (AvrLn2 >= 64)
254 Length=DecodeNum(BitField,STARTL1,DecL1,PosL1);
255 else
256 if (BitField < 0x100)
257 {
258 Length=BitField;
259 Inp.faddbits(16);
260 }
261 else
262 {
263 for (Length=0;((BitField<<Length)&0x8000)==0;Length++)
264 ;
265 Inp.faddbits(Length+1);
266 }
267
268 AvrLn2 += Length;
269 AvrLn2 -= AvrLn2 >> 5;
270
271 BitField=Inp.fgetbits();
272 if (AvrPlcB > 0x28ff)
273 DistancePlace=DecodeNum(BitField,STARTHF2,DecHf2,PosHf2);
274 else
275 if (AvrPlcB > 0x6ff)
276 DistancePlace=DecodeNum(BitField,STARTHF1,DecHf1,PosHf1);
277 else
278 DistancePlace=DecodeNum(BitField,STARTHF0,DecHf0,PosHf0);
279
280 AvrPlcB += DistancePlace;
281 AvrPlcB -= AvrPlcB >> 8;
282 while (1)
283 {
284 Distance = ChSetB[DistancePlace & 0xff];
285 NewDistancePlace = NToPlB[Distance++ & 0xff]++;
286 if (!(Distance & 0xff))
287 CorrHuff(ChSetB,NToPlB);
288 else
289 break;
290 }
291
292 ChSetB[DistancePlace & 0xff]=ChSetB[NewDistancePlace];
293 ChSetB[NewDistancePlace]=Distance;
294
295 Distance=((Distance & 0xff00) | (Inp.fgetbits() >> 8)) >> 1;
296 Inp.faddbits(7);
297
298 OldAvr3=AvrLn3;
299 if (Length!=1 && Length!=4)
300 if (Length==0 && Distance <= MaxDist3)
301 {
302 AvrLn3++;
303 AvrLn3 -= AvrLn3 >> 8;
304 }
305 else
306 if (AvrLn3 > 0)
307 AvrLn3--;
308 Length+=3;
309 if (Distance >= MaxDist3)
310 Length++;
311 if (Distance <= 256)
312 Length+=8;
313 if (OldAvr3 > 0xb0 || AvrPlc >= 0x2a00 && OldAvr2 < 0x40)
314 MaxDist3=0x7f00;
315 else
316 MaxDist3=0x2001;
317 OldDist[OldDistPtr++]=Distance;
318 OldDistPtr = OldDistPtr & 3;
319 LastLength=Length;
320 LastDist=Distance;
321 CopyString15(Distance,Length);
322 }
323
324
HuffDecode()325 void Unpack::HuffDecode()
326 {
327 unsigned int CurByte,NewBytePlace;
328 unsigned int Length;
329 unsigned int Distance;
330 int BytePlace;
331
332 unsigned int BitField=Inp.fgetbits();
333
334 if (AvrPlc > 0x75ff)
335 BytePlace=DecodeNum(BitField,STARTHF4,DecHf4,PosHf4);
336 else
337 if (AvrPlc > 0x5dff)
338 BytePlace=DecodeNum(BitField,STARTHF3,DecHf3,PosHf3);
339 else
340 if (AvrPlc > 0x35ff)
341 BytePlace=DecodeNum(BitField,STARTHF2,DecHf2,PosHf2);
342 else
343 if (AvrPlc > 0x0dff)
344 BytePlace=DecodeNum(BitField,STARTHF1,DecHf1,PosHf1);
345 else
346 BytePlace=DecodeNum(BitField,STARTHF0,DecHf0,PosHf0);
347 BytePlace&=0xff;
348 if (StMode)
349 {
350 if (BytePlace==0 && BitField > 0xfff)
351 BytePlace=0x100;
352 if (--BytePlace==-1)
353 {
354 BitField=Inp.fgetbits();
355 Inp.faddbits(1);
356 if (BitField & 0x8000)
357 {
358 NumHuf=StMode=0;
359 return;
360 }
361 else
362 {
363 Length = (BitField & 0x4000) ? 4 : 3;
364 Inp.faddbits(1);
365 Distance=DecodeNum(Inp.fgetbits(),STARTHF2,DecHf2,PosHf2);
366 Distance = (Distance << 5) | (Inp.fgetbits() >> 11);
367 Inp.faddbits(5);
368 CopyString15(Distance,Length);
369 return;
370 }
371 }
372 }
373 else
374 if (NumHuf++ >= 16 && FlagsCnt==0)
375 StMode=1;
376 AvrPlc += BytePlace;
377 AvrPlc -= AvrPlc >> 8;
378 Nhfb+=16;
379 if (Nhfb > 0xff)
380 {
381 Nhfb=0x90;
382 Nlzb >>= 1;
383 }
384
385 Window[UnpPtr++]=(byte)(ChSet[BytePlace]>>8);
386 --DestUnpSize;
387
388 while (1)
389 {
390 CurByte=ChSet[BytePlace];
391 NewBytePlace=NToPl[CurByte++ & 0xff]++;
392 if ((CurByte & 0xff) > 0xa1)
393 CorrHuff(ChSet,NToPl);
394 else
395 break;
396 }
397
398 ChSet[BytePlace]=ChSet[NewBytePlace];
399 ChSet[NewBytePlace]=CurByte;
400 }
401
402
GetFlagsBuf()403 void Unpack::GetFlagsBuf()
404 {
405 unsigned int Flags,NewFlagsPlace;
406 unsigned int FlagsPlace=DecodeNum(Inp.fgetbits(),STARTHF2,DecHf2,PosHf2);
407
408 // Our Huffman table stores 257 items and needs all them in other parts
409 // of code such as when StMode is on, so the first item is control item.
410 // While normally we do not use the last item to code the flags byte here,
411 // we need to check for value 256 when unpacking in case we unpack
412 // a corrupt archive.
413 if (FlagsPlace>=sizeof(ChSetC)/sizeof(ChSetC[0]))
414 return;
415
416 while (1)
417 {
418 Flags=ChSetC[FlagsPlace];
419 FlagBuf=Flags>>8;
420 NewFlagsPlace=NToPlC[Flags++ & 0xff]++;
421 if ((Flags & 0xff) != 0)
422 break;
423 CorrHuff(ChSetC,NToPlC);
424 }
425
426 ChSetC[FlagsPlace]=ChSetC[NewFlagsPlace];
427 ChSetC[NewFlagsPlace]=Flags;
428 }
429
430
UnpInitData15(int Solid)431 void Unpack::UnpInitData15(int Solid)
432 {
433 if (!Solid)
434 {
435 AvrPlcB=AvrLn1=AvrLn2=AvrLn3=NumHuf=Buf60=0;
436 AvrPlc=0x3500;
437 MaxDist3=0x2001;
438 Nhfb=Nlzb=0x80;
439 }
440 FlagsCnt=0;
441 FlagBuf=0;
442 StMode=0;
443 LCount=0;
444 ReadTop=0;
445 }
446
447
InitHuff()448 void Unpack::InitHuff()
449 {
450 for (unsigned int I=0;I<256;I++)
451 {
452 ChSet[I]=ChSetB[I]=I<<8;
453 ChSetA[I]=I;
454 ChSetC[I]=((~I+1) & 0xff)<<8;
455 }
456 memset(NToPl,0,sizeof(NToPl));
457 memset(NToPlB,0,sizeof(NToPlB));
458 memset(NToPlC,0,sizeof(NToPlC));
459 CorrHuff(ChSetB,NToPlB);
460 }
461
462
CorrHuff(ushort * CharSet,byte * NumToPlace)463 void Unpack::CorrHuff(ushort *CharSet,byte *NumToPlace)
464 {
465 int I,J;
466 for (I=7;I>=0;I--)
467 for (J=0;J<32;J++,CharSet++)
468 *CharSet=(*CharSet & ~0xff) | I;
469 memset(NumToPlace,0,sizeof(NToPl));
470 for (I=6;I>=0;I--)
471 NumToPlace[I]=(7-I)*32;
472 }
473
474
CopyString15(uint Distance,uint Length)475 void Unpack::CopyString15(uint Distance,uint Length)
476 {
477 DestUnpSize-=Length;
478 while (Length--)
479 {
480 Window[UnpPtr]=Window[(UnpPtr-Distance) & MaxWinMask];
481 UnpPtr=(UnpPtr+1) & MaxWinMask;
482 }
483 }
484
485
DecodeNum(uint Num,uint StartPos,uint * DecTab,uint * PosTab)486 uint Unpack::DecodeNum(uint Num,uint StartPos,uint *DecTab,uint *PosTab)
487 {
488 int I;
489 for (Num&=0xfff0,I=0;DecTab[I]<=Num;I++)
490 StartPos++;
491 Inp.faddbits(StartPos);
492 return(((Num-(I ? DecTab[I-1]:0))>>(16-StartPos))+PosTab[StartPos]);
493 }
494