1 // Rar1Decoder.cpp
2 // According to unRAR license, this code may not be used to develop
3 // a program that creates RAR archives
4
5 #include "StdAfx.h"
6
7 #include "Rar1Decoder.h"
8
9 namespace NCompress {
10 namespace NRar1 {
11
12 static const unsigned kNumBits = 12;
13
14 static const Byte kShortLen1[16 * 3] =
15 {
16 0,0xa0,0xd0,0xe0,0xf0,0xf8,0xfc,0xfe,0xff,0xc0,0x80,0x90,0x98,0x9c,0xb0,0,
17 1,3,4,4,5,6,7,8,8,4,4,5,6,6,0,0,
18 1,4,4,4,5,6,7,8,8,4,4,5,6,6,4,0
19 };
20
21 static const Byte kShortLen2[16 * 3] =
22 {
23 0,0x40,0x60,0xa0,0xd0,0xe0,0xf0,0xf8,0xfc,0xc0,0x80,0x90,0x98,0x9c,0xb0,0,
24 2,3,3,3,4,4,5,6,6,4,4,5,6,6,0,0,
25 2,3,3,4,4,4,5,6,6,4,4,5,6,6,4,0
26 };
27
28 static const Byte PosL1[kNumBits + 1] = { 0,0,2,1,2,2,4,5,4,4,8,0,224 };
29 static const Byte PosL2[kNumBits + 1] = { 0,0,0,5,2,2,4,5,4,4,8,2,220 };
30
31 static const Byte PosHf0[kNumBits + 1] = { 0,0,0,0,8,8,8,9,0,0,0,0,224 };
32 static const Byte PosHf1[kNumBits + 1] = { 0,0,0,0,0,4,40,16,16,4,0,47,130 };
33 static const Byte PosHf2[kNumBits + 1] = { 0,0,0,0,0,2,5,46,64,116,24,0,0 };
34 static const Byte PosHf3[kNumBits + 1] = { 0,0,0,0,0,0,2,14,202,33,6,0,0 };
35 static const Byte PosHf4[kNumBits + 1] = { 0,0,0,0,0,0,0,0,255,2,0,0,0 };
36
37 static const UInt32 kHistorySize = (1 << 16);
38
CDecoder()39 CDecoder::CDecoder():
40 _isSolid(false),
41 _solidAllowed(false)
42 { }
43
ReadBits(unsigned numBits)44 UInt32 CDecoder::ReadBits(unsigned numBits) { return m_InBitStream.ReadBits(numBits); }
45
CopyBlock(UInt32 distance,UInt32 len)46 HRESULT CDecoder::CopyBlock(UInt32 distance, UInt32 len)
47 {
48 if (len == 0)
49 return S_FALSE;
50 if (m_UnpackSize < len)
51 return S_FALSE;
52 m_UnpackSize -= len;
53 return m_OutWindowStream.CopyBlock(distance, len) ? S_OK : S_FALSE;
54 }
55
56
DecodeNum(const Byte * numTab)57 UInt32 CDecoder::DecodeNum(const Byte *numTab)
58 {
59 /*
60 {
61 // we can check that tables are correct
62 UInt32 sum = 0;
63 for (unsigned i = 0; i <= kNumBits; i++)
64 sum += ((UInt32)numTab[i] << (kNumBits - i));
65 if (sum != (1 << kNumBits))
66 throw 111;
67 }
68 */
69
70 UInt32 val = m_InBitStream.GetValue(kNumBits);
71 UInt32 sum = 0;
72 unsigned i = 2;
73
74 for (;;)
75 {
76 UInt32 num = numTab[i];
77 UInt32 cur = num << (kNumBits - i);
78 if (val < cur)
79 break;
80 i++;
81 val -= cur;
82 sum += num;
83 }
84 m_InBitStream.MovePos(i);
85 return ((val >> (kNumBits - i)) + sum);
86 }
87
88
ShortLZ()89 HRESULT CDecoder::ShortLZ()
90 {
91 NumHuf = 0;
92
93 if (LCount == 2)
94 {
95 if (ReadBits(1))
96 return CopyBlock(LastDist, LastLength);
97 LCount = 0;
98 }
99
100 UInt32 bitField = m_InBitStream.GetValue(8);
101
102 UInt32 len, dist;
103 {
104 const Byte *xors = (AvrLn1 < 37) ? kShortLen1 : kShortLen2;
105 const Byte *lens = xors + 16 + Buf60;
106 for (len = 0; ((bitField ^ xors[len]) >> (8 - lens[len])) != 0; len++);
107 m_InBitStream.MovePos(lens[len]);
108 }
109
110 if (len >= 9)
111 {
112 if (len == 9)
113 {
114 LCount++;
115 return CopyBlock(LastDist, LastLength);
116 }
117
118 LCount = 0;
119
120 if (len == 14)
121 {
122 len = DecodeNum(PosL2) + 5;
123 dist = 0x8000 + ReadBits(15) - 1;
124 LastLength = len;
125 LastDist = dist;
126 return CopyBlock(dist, len);
127 }
128
129 UInt32 saveLen = len;
130 dist = m_RepDists[(m_RepDistPtr - (len - 9)) & 3];
131
132 len = DecodeNum(PosL1);
133
134 if (len == 0xff && saveLen == 10)
135 {
136 Buf60 ^= 16;
137 return S_OK;
138 }
139 if (dist >= 256)
140 {
141 len++;
142 if (dist >= MaxDist3 - 1)
143 len++;
144 }
145 }
146 else
147 {
148 LCount = 0;
149 AvrLn1 += len;
150 AvrLn1 -= AvrLn1 >> 4;
151
152 unsigned distancePlace = DecodeNum(PosHf2) & 0xff;
153
154 dist = ChSetA[distancePlace];
155
156 if (distancePlace != 0)
157 {
158 PlaceA[dist]--;
159 UInt32 lastDistance = ChSetA[(size_t)distancePlace - 1];
160 PlaceA[lastDistance]++;
161 ChSetA[distancePlace] = lastDistance;
162 ChSetA[(size_t)distancePlace - 1] = dist;
163 }
164 }
165
166 m_RepDists[m_RepDistPtr++] = dist;
167 m_RepDistPtr &= 3;
168 len += 2;
169 LastLength = len;
170 LastDist = dist;
171 return CopyBlock(dist, len);
172 }
173
174
LongLZ()175 HRESULT CDecoder::LongLZ()
176 {
177 UInt32 len;
178 UInt32 dist;
179 UInt32 distancePlace, newDistancePlace;
180 UInt32 oldAvr2, oldAvr3;
181
182 NumHuf = 0;
183 Nlzb += 16;
184 if (Nlzb > 0xff)
185 {
186 Nlzb = 0x90;
187 Nhfb >>= 1;
188 }
189 oldAvr2 = AvrLn2;
190
191 if (AvrLn2 >= 64)
192 len = DecodeNum(AvrLn2 < 122 ? PosL1 : PosL2);
193 else
194 {
195 UInt32 bitField = m_InBitStream.GetValue(16);
196 if (bitField < 0x100)
197 {
198 len = bitField;
199 m_InBitStream.MovePos(16);
200 }
201 else
202 {
203 for (len = 0; ((bitField << len) & 0x8000) == 0; len++);
204
205 m_InBitStream.MovePos(len + 1);
206 }
207 }
208
209 AvrLn2 += len;
210 AvrLn2 -= AvrLn2 >> 5;
211
212 {
213 const Byte *tab;
214 if (AvrPlcB >= 0x2900) tab = PosHf2;
215 else if (AvrPlcB >= 0x0700) tab = PosHf1;
216 else tab = PosHf0;
217 distancePlace = DecodeNum(tab); // [0, 256]
218 }
219
220 AvrPlcB += distancePlace;
221 AvrPlcB -= AvrPlcB >> 8;
222
223 distancePlace &= 0xff;
224
225 for (;;)
226 {
227 dist = ChSetB[distancePlace];
228 newDistancePlace = NToPlB[dist++ & 0xff]++;
229 if (dist & 0xff)
230 break;
231 CorrHuff(ChSetB,NToPlB);
232 }
233
234 ChSetB[distancePlace] = ChSetB[newDistancePlace];
235 ChSetB[newDistancePlace] = dist;
236
237 dist = ((dist & 0xff00) >> 1) | ReadBits(7);
238
239 oldAvr3 = AvrLn3;
240
241 if (len != 1 && len != 4)
242 {
243 if (len == 0 && dist <= MaxDist3)
244 {
245 AvrLn3++;
246 AvrLn3 -= AvrLn3 >> 8;
247 }
248 else if (AvrLn3 > 0)
249 AvrLn3--;
250 }
251
252 len += 3;
253
254 if (dist >= MaxDist3)
255 len++;
256 if (dist <= 256)
257 len += 8;
258
259 if (oldAvr3 > 0xb0 || (AvrPlc >= 0x2a00 && oldAvr2 < 0x40))
260 MaxDist3 = 0x7f00;
261 else
262 MaxDist3 = 0x2001;
263
264 m_RepDists[m_RepDistPtr++] = --dist;
265 m_RepDistPtr &= 3;
266 LastLength = len;
267 LastDist = dist;
268
269 return CopyBlock(dist, len);
270 }
271
272
HuffDecode()273 HRESULT CDecoder::HuffDecode()
274 {
275 UInt32 curByte, newBytePlace;
276 UInt32 len;
277 UInt32 dist;
278 unsigned bytePlace;
279 {
280 const Byte *tab;
281
282 if (AvrPlc >= 0x7600) tab = PosHf4;
283 else if (AvrPlc >= 0x5e00) tab = PosHf3;
284 else if (AvrPlc >= 0x3600) tab = PosHf2;
285 else if (AvrPlc >= 0x0e00) tab = PosHf1;
286 else tab = PosHf0;
287
288 bytePlace = DecodeNum(tab); // [0, 256]
289 }
290
291 if (StMode)
292 {
293 if (bytePlace == 0)
294 {
295 if (ReadBits(1))
296 {
297 NumHuf = 0;
298 StMode = false;
299 return S_OK;
300 }
301 len = ReadBits(1) + 3;
302 dist = DecodeNum(PosHf2);
303 dist = (dist << 5) | ReadBits(5);
304 if (dist == 0)
305 return S_FALSE;
306 return CopyBlock(dist - 1, len);
307 }
308 bytePlace--; // bytePlace is [0, 255]
309 }
310 else if (NumHuf++ >= 16 && FlagsCnt == 0)
311 StMode = true;
312
313 bytePlace &= 0xff;
314 AvrPlc += bytePlace;
315 AvrPlc -= AvrPlc >> 8;
316 Nhfb += 16;
317
318 if (Nhfb > 0xff)
319 {
320 Nhfb = 0x90;
321 Nlzb >>= 1;
322 }
323
324 m_UnpackSize--;
325 m_OutWindowStream.PutByte((Byte)(ChSet[bytePlace] >> 8));
326
327 for (;;)
328 {
329 curByte = ChSet[bytePlace];
330 newBytePlace = NToPl[curByte++ & 0xff]++;
331 if ((curByte & 0xff) <= 0xa1)
332 break;
333 CorrHuff(ChSet, NToPl);
334 }
335
336 ChSet[bytePlace] = ChSet[newBytePlace];
337 ChSet[newBytePlace] = curByte;
338 return S_OK;
339 }
340
341
GetFlagsBuf()342 void CDecoder::GetFlagsBuf()
343 {
344 UInt32 flags, newFlagsPlace;
345 UInt32 flagsPlace = DecodeNum(PosHf2); // [0, 256]
346
347 if (flagsPlace >= ARRAY_SIZE(ChSetC))
348 return;
349
350 for (;;)
351 {
352 flags = ChSetC[flagsPlace];
353 FlagBuf = flags >> 8;
354 newFlagsPlace = NToPlC[flags++ & 0xff]++;
355 if ((flags & 0xff) != 0)
356 break;
357 CorrHuff(ChSetC, NToPlC);
358 }
359
360 ChSetC[flagsPlace] = ChSetC[newFlagsPlace];
361 ChSetC[newFlagsPlace] = flags;
362 }
363
364
CorrHuff(UInt32 * CharSet,UInt32 * NumToPlace)365 void CDecoder::CorrHuff(UInt32 *CharSet,UInt32 *NumToPlace)
366 {
367 int i;
368 for (i = 7; i >= 0; i--)
369 for (int j = 0; j < 32; j++, CharSet++)
370 *CharSet = (*CharSet & ~0xff) | i;
371 memset(NumToPlace, 0, sizeof(NToPl));
372 for (i = 6; i >= 0; i--)
373 NumToPlace[i] = (7 - i) * 32;
374 }
375
376
377
CodeReal(ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo *)378 HRESULT CDecoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream,
379 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo * /* progress */)
380 {
381 if (!inSize || !outSize)
382 return E_INVALIDARG;
383
384 if (_isSolid && !_solidAllowed)
385 return S_FALSE;
386
387 _solidAllowed = false;
388
389 if (!m_OutWindowStream.Create(kHistorySize))
390 return E_OUTOFMEMORY;
391 if (!m_InBitStream.Create(1 << 20))
392 return E_OUTOFMEMORY;
393
394 m_UnpackSize = *outSize;
395
396 m_OutWindowStream.SetStream(outStream);
397 m_OutWindowStream.Init(_isSolid);
398 m_InBitStream.SetStream(inStream);
399 m_InBitStream.Init();
400
401 // InitData
402
403 FlagsCnt = 0;
404 FlagBuf = 0;
405 StMode = false;
406 LCount = 0;
407
408 if (!_isSolid)
409 {
410 AvrPlcB = AvrLn1 = AvrLn2 = AvrLn3 = NumHuf = Buf60 = 0;
411 AvrPlc = 0x3500;
412 MaxDist3 = 0x2001;
413 Nhfb = Nlzb = 0x80;
414
415 {
416 // InitStructures
417 for (unsigned i = 0; i < kNumRepDists; i++)
418 m_RepDists[i] = 0;
419 m_RepDistPtr = 0;
420 LastLength = 0;
421 LastDist = 0;
422 }
423
424 // InitHuff
425
426 for (UInt32 i = 0; i < 256; i++)
427 {
428 Place[i] = PlaceA[i] = PlaceB[i] = i;
429 UInt32 c = (~i + 1) & 0xff;
430 PlaceC[i] = c;
431 ChSet[i] = ChSetB[i] = i << 8;
432 ChSetA[i] = i;
433 ChSetC[i] = c << 8;
434 }
435 memset(NToPl, 0, sizeof(NToPl));
436 memset(NToPlB, 0, sizeof(NToPlB));
437 memset(NToPlC, 0, sizeof(NToPlC));
438 CorrHuff(ChSetB, NToPlB);
439 }
440
441 if (m_UnpackSize > 0)
442 {
443 GetFlagsBuf();
444 FlagsCnt = 8;
445 }
446
447 while (m_UnpackSize != 0)
448 {
449 if (!StMode)
450 {
451 if (--FlagsCnt < 0)
452 {
453 GetFlagsBuf();
454 FlagsCnt = 7;
455 }
456
457 if (FlagBuf & 0x80)
458 {
459 FlagBuf <<= 1;
460 if (Nlzb > Nhfb)
461 {
462 RINOK(LongLZ());
463 continue;
464 }
465 }
466 else
467 {
468 FlagBuf <<= 1;
469
470 if (--FlagsCnt < 0)
471 {
472 GetFlagsBuf();
473 FlagsCnt = 7;
474 }
475
476 if ((FlagBuf & 0x80) == 0)
477 {
478 FlagBuf <<= 1;
479 RINOK(ShortLZ());
480 continue;
481 }
482
483 FlagBuf <<= 1;
484
485 if (Nlzb <= Nhfb)
486 {
487 RINOK(LongLZ());
488 continue;
489 }
490 }
491 }
492
493 RINOK(HuffDecode());
494 }
495
496 _solidAllowed = true;
497 return m_OutWindowStream.Flush();
498 }
499
500
Code(ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo * progress)501 STDMETHODIMP CDecoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,
502 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress)
503 {
504 try { return CodeReal(inStream, outStream, inSize, outSize, progress); }
505 catch(const CInBufferException &e) { return e.ErrorCode; }
506 catch(const CLzOutWindowException &e) { return e.ErrorCode; }
507 catch(...) { return S_FALSE; }
508 }
509
SetDecoderProperties2(const Byte * data,UInt32 size)510 STDMETHODIMP CDecoder::SetDecoderProperties2(const Byte *data, UInt32 size)
511 {
512 if (size < 1)
513 return E_INVALIDARG;
514 _isSolid = ((data[0] & 1) != 0);
515 return S_OK;
516 }
517
518 }}
519