1 // Rar2Decoder.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 <stdlib.h>
8
9 #include "Rar2Decoder.h"
10
11 namespace NCompress {
12 namespace NRar2 {
13
14 namespace NMultimedia {
15
16 #define my_abs(x) (unsigned)abs(x)
17
Decode(int & channelDelta,Byte deltaByte)18 Byte CFilter::Decode(int &channelDelta, Byte deltaByte)
19 {
20 D4 = D3;
21 D3 = D2;
22 D2 = LastDelta - D1;
23 D1 = LastDelta;
24 const int predictedValue = ((8 * LastChar + K1 * D1 + K2 * D2 + K3 * D3 + K4 * D4 + K5 * channelDelta) >> 3);
25
26 const Byte realValue = (Byte)(predictedValue - deltaByte);
27
28 {
29 const int i = ((int)(signed char)deltaByte) << 3;
30
31 Dif[0] += my_abs(i);
32 Dif[1] += my_abs(i - D1);
33 Dif[2] += my_abs(i + D1);
34 Dif[3] += my_abs(i - D2);
35 Dif[4] += my_abs(i + D2);
36 Dif[5] += my_abs(i - D3);
37 Dif[6] += my_abs(i + D3);
38 Dif[7] += my_abs(i - D4);
39 Dif[8] += my_abs(i + D4);
40 Dif[9] += my_abs(i - channelDelta);
41 Dif[10] += my_abs(i + channelDelta);
42 }
43
44 channelDelta = LastDelta = (signed char)(realValue - LastChar);
45 LastChar = realValue;
46
47 if (((++ByteCount) & 0x1F) == 0)
48 {
49 UInt32 minDif = Dif[0];
50 UInt32 numMinDif = 0;
51 Dif[0] = 0;
52
53 for (unsigned i = 1; i < Z7_ARRAY_SIZE(Dif); i++)
54 {
55 if (Dif[i] < minDif)
56 {
57 minDif = Dif[i];
58 numMinDif = i;
59 }
60 Dif[i] = 0;
61 }
62
63 switch (numMinDif)
64 {
65 case 1: if (K1 >= -16) K1--; break;
66 case 2: if (K1 < 16) K1++; break;
67 case 3: if (K2 >= -16) K2--; break;
68 case 4: if (K2 < 16) K2++; break;
69 case 5: if (K3 >= -16) K3--; break;
70 case 6: if (K3 < 16) K3++; break;
71 case 7: if (K4 >= -16) K4--; break;
72 case 8: if (K4 < 16) K4++; break;
73 case 9: if (K5 >= -16) K5--; break;
74 case 10:if (K5 < 16) K5++; break;
75 }
76 }
77
78 return realValue;
79 }
80 }
81
82 static const UInt32 kHistorySize = 1 << 20;
83
84 // static const UInt32 kWindowReservSize = (1 << 22) + 256;
85
CDecoder()86 CDecoder::CDecoder():
87 _isSolid(false),
88 _solidAllowed(false),
89 m_TablesOK(false)
90 {
91 }
92
InitStructures()93 void CDecoder::InitStructures()
94 {
95 m_MmFilter.Init();
96 for (unsigned i = 0; i < kNumReps; i++)
97 m_RepDists[i] = 0;
98 m_RepDistPtr = 0;
99 m_LastLength = 0;
100 memset(m_LastLevels, 0, kMaxTableSize);
101 }
102
ReadBits(unsigned numBits)103 UInt32 CDecoder::ReadBits(unsigned numBits) { return m_InBitStream.ReadBits(numBits); }
104
105 #define RIF(x) { if (!(x)) return false; }
106
107 static const unsigned kRepBothNumber = 256;
108 static const unsigned kRepNumber = kRepBothNumber + 1;
109 static const unsigned kLen2Number = kRepNumber + kNumReps;
110 static const unsigned kReadTableNumber = kLen2Number + kNumLen2Symbols;
111 static const unsigned kMatchNumber = kReadTableNumber + 1;
112
113 // static const unsigned kDistTableStart = kMainTableSize;
114 // static const unsigned kLenTableStart = kDistTableStart + kDistTableSize;
115
116 static const UInt32 kDistStart [kDistTableSize] = {0,1,2,3,4,6,8,12,16,24,32,48,64,96,128,192,256,384,512,768,1024,1536,2048,3072,4096,6144,8192,12288,16384,24576,32768U,49152U,65536,98304,131072,196608,262144,327680,393216,458752,524288,589824,655360,720896,786432,851968,917504,983040};
117 static const Byte kDistDirectBits[kDistTableSize] = {0,0,0,0,1,1,2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16};
118
119 static const Byte kLen2DistStarts [kNumLen2Symbols]={0,4,8,16,32,64,128,192};
120 static const Byte kLen2DistDirectBits[kNumLen2Symbols]={2,2,3, 4, 5, 6, 6, 6};
121
122 static const UInt32 kDistLimit2 = 0x101 - 1;
123 static const UInt32 kDistLimit3 = 0x2000 - 1;
124 static const UInt32 kDistLimit4 = 0x40000 - 1;
125
126 // static const UInt32 kMatchMaxLen = 255 + 2;
127 // static const UInt32 kMatchMaxLenMax = 255 + 5;
128
129
ReadTables(void)130 bool CDecoder::ReadTables(void)
131 {
132 m_TablesOK = false;
133
134 const unsigned kLevelTableSize = 19;
135 Byte levelLevels[kLevelTableSize];
136 Byte lens[kMaxTableSize];
137
138 m_AudioMode = (ReadBits(1) == 1);
139
140 if (ReadBits(1) == 0)
141 memset(m_LastLevels, 0, kMaxTableSize);
142
143 unsigned numLevels;
144
145 if (m_AudioMode)
146 {
147 m_NumChannels = ReadBits(2) + 1;
148 if (m_MmFilter.CurrentChannel >= m_NumChannels)
149 m_MmFilter.CurrentChannel = 0;
150 numLevels = m_NumChannels * k_MM_TableSize;
151 }
152 else
153 numLevels = kHeapTablesSizesSum;
154
155 unsigned i;
156 for (i = 0; i < kLevelTableSize; i++)
157 levelLevels[i] = (Byte)ReadBits(4);
158 NHuffman::CDecoder256<kNumHufBits, kLevelTableSize, 6> m_LevelDecoder;
159 RIF(m_LevelDecoder.Build(levelLevels, NHuffman::k_BuildMode_Full))
160
161 i = 0;
162 do
163 {
164 const unsigned sym = m_LevelDecoder.DecodeFull(&m_InBitStream);
165 if (sym < 16)
166 {
167 lens[i] = (Byte)((sym + m_LastLevels[i]) & 15);
168 i++;
169 }
170 #if 0
171 else if (sym >= kLevelTableSize)
172 return false;
173 #endif
174 else
175 {
176 unsigned num;
177 Byte v;
178 if (sym == 16)
179 {
180 if (i == 0)
181 return false;
182 num = ReadBits(2) + 3;
183 v = lens[(size_t)i - 1];
184 }
185 else
186 {
187 num = (sym - 17) * 4;
188 num += num + 3 + ReadBits(3 + num);
189 v = 0;
190 }
191 num += i;
192 if (num > numLevels)
193 {
194 // return false;
195 num = numLevels; // original unRAR
196 }
197 do
198 lens[i++] = v;
199 while (i < num);
200 }
201 }
202 while (i < numLevels);
203
204 if (m_InBitStream.ExtraBitsWereRead())
205 return false;
206
207 if (m_AudioMode)
208 for (i = 0; i < m_NumChannels; i++)
209 {
210 RIF(m_MMDecoders[i].Build(&lens[(size_t)i * k_MM_TableSize]))
211 }
212 else
213 {
214 RIF(m_MainDecoder.Build(&lens[0]))
215 RIF(m_DistDecoder.Build(&lens[kMainTableSize]))
216 RIF(m_LenDecoder.Build(&lens[kMainTableSize + kDistTableSize]))
217 }
218
219 memcpy(m_LastLevels, lens, kMaxTableSize);
220
221 m_TablesOK = true;
222 return true;
223 }
224
225
ReadLastTables()226 bool CDecoder::ReadLastTables()
227 {
228 // it differs a little from pure RAR sources;
229 // UInt64 ttt = m_InBitStream.GetProcessedSize() + 2;
230 // + 2 works for: return 0xFF; in CInBuffer::ReadByte.
231 if (m_InBitStream.GetProcessedSize() + 7 <= m_PackSize) // test it: probably incorrect;
232 // if (m_InBitStream.GetProcessedSize() + 2 <= m_PackSize) // test it: probably incorrect;
233 {
234 if (m_AudioMode)
235 {
236 const unsigned symbol = m_MMDecoders[m_MmFilter.CurrentChannel].Decode(&m_InBitStream);
237 if (symbol == 256)
238 return ReadTables();
239 if (symbol >= k_MM_TableSize)
240 return false;
241 }
242 else
243 {
244 const unsigned sym = m_MainDecoder.Decode(&m_InBitStream);
245 if (sym == kReadTableNumber)
246 return ReadTables();
247 if (sym >= kMainTableSize)
248 return false;
249 }
250 }
251 return true;
252 }
253
254
DecodeMm(UInt32 pos)255 bool CDecoder::DecodeMm(UInt32 pos)
256 {
257 while (pos-- != 0)
258 {
259 const unsigned symbol = m_MMDecoders[m_MmFilter.CurrentChannel].Decode(&m_InBitStream);
260 if (m_InBitStream.ExtraBitsWereRead())
261 return false;
262 if (symbol >= 256)
263 return symbol == 256;
264 /*
265 Byte byPredict = m_Predictor.Predict();
266 Byte byReal = (Byte)(byPredict - (Byte)symbol);
267 m_Predictor.Update(byReal, byPredict);
268 */
269 const Byte byReal = m_MmFilter.Decode((Byte)symbol);
270 m_OutWindowStream.PutByte(byReal);
271 if (++m_MmFilter.CurrentChannel == m_NumChannels)
272 m_MmFilter.CurrentChannel = 0;
273 }
274 return true;
275 }
276
277
278 typedef unsigned CLenType;
279
SlotToLen(CBitDecoder & _bitStream,CLenType slot)280 static inline CLenType SlotToLen(CBitDecoder &_bitStream, CLenType slot)
281 {
282 const unsigned numBits = ((unsigned)slot >> 2) - 1;
283 return ((4 | (slot & 3)) << numBits) + (CLenType)_bitStream.ReadBits(numBits);
284 }
285
DecodeLz(Int32 pos)286 bool CDecoder::DecodeLz(Int32 pos)
287 {
288 while (pos > 0)
289 {
290 unsigned sym = m_MainDecoder.Decode(&m_InBitStream);
291 if (m_InBitStream.ExtraBitsWereRead())
292 return false;
293 UInt32 len, distance;
294 if (sym < 256)
295 {
296 m_OutWindowStream.PutByte(Byte(sym));
297 pos--;
298 continue;
299 }
300 else if (sym >= kMatchNumber)
301 {
302 if (sym >= kMainTableSize)
303 return false;
304 len = sym - kMatchNumber;
305 if (len >= 8)
306 len = SlotToLen(m_InBitStream, len);
307 len += 3;
308
309 sym = m_DistDecoder.Decode(&m_InBitStream);
310 if (sym >= kDistTableSize)
311 return false;
312 distance = kDistStart[sym] + m_InBitStream.ReadBits(kDistDirectBits[sym]);
313 if (distance >= kDistLimit3)
314 {
315 len += 2 - ((distance - kDistLimit4) >> 31);
316 // len++;
317 // if (distance >= kDistLimit4)
318 // len++;
319 }
320 }
321 else if (sym == kRepBothNumber)
322 {
323 len = m_LastLength;
324 if (len == 0)
325 return false;
326 distance = m_RepDists[(m_RepDistPtr + 4 - 1) & 3];
327 }
328 else if (sym < kLen2Number)
329 {
330 distance = m_RepDists[(m_RepDistPtr - (sym - kRepNumber + 1)) & 3];
331 len = m_LenDecoder.Decode(&m_InBitStream);
332 if (len >= kLenTableSize)
333 return false;
334 if (len >= 8)
335 len = SlotToLen(m_InBitStream, len);
336 len += 2;
337
338 if (distance >= kDistLimit2)
339 {
340 len++;
341 if (distance >= kDistLimit3)
342 {
343 len += 2 - ((distance - kDistLimit4) >> 31);
344 // len++;
345 // if (distance >= kDistLimit4)
346 // len++;
347 }
348 }
349 }
350 else if (sym < kReadTableNumber)
351 {
352 sym -= kLen2Number;
353 distance = kLen2DistStarts[sym] +
354 m_InBitStream.ReadBits(kLen2DistDirectBits[sym]);
355 len = 2;
356 }
357 else // (sym == kReadTableNumber)
358 return true;
359
360 m_RepDists[m_RepDistPtr++ & 3] = distance;
361 m_LastLength = len;
362 if (!m_OutWindowStream.CopyBlock(distance, len))
363 return false;
364 pos -= len;
365 }
366 return true;
367 }
368
CodeReal(ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo * progress)369 HRESULT CDecoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream,
370 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress)
371 {
372 if (!inSize || !outSize)
373 return E_INVALIDARG;
374
375 if (_isSolid && !_solidAllowed)
376 return S_FALSE;
377 _solidAllowed = false;
378
379 if (!m_OutWindowStream.Create(kHistorySize))
380 return E_OUTOFMEMORY;
381 if (!m_InBitStream.Create(1 << 20))
382 return E_OUTOFMEMORY;
383
384 m_PackSize = *inSize;
385
386 UInt64 pos = 0, unPackSize = *outSize;
387
388 m_OutWindowStream.SetStream(outStream);
389 m_OutWindowStream.Init(_isSolid);
390 m_InBitStream.SetStream(inStream);
391 m_InBitStream.Init();
392
393 // CCoderReleaser coderReleaser(this);
394 if (!_isSolid)
395 {
396 InitStructures();
397 if (unPackSize == 0)
398 {
399 if (m_InBitStream.GetProcessedSize() + 2 <= m_PackSize) // test it: probably incorrect;
400 if (!ReadTables())
401 return S_FALSE;
402 _solidAllowed = true;
403 return S_OK;
404 }
405 ReadTables();
406 }
407
408 if (!m_TablesOK)
409 return S_FALSE;
410
411 const UInt64 startPos = m_OutWindowStream.GetProcessedSize();
412 while (pos < unPackSize)
413 {
414 UInt32 blockSize = 1 << 20;
415 if (blockSize > unPackSize - pos)
416 blockSize = (UInt32)(unPackSize - pos);
417 UInt64 blockStartPos = m_OutWindowStream.GetProcessedSize();
418 if (m_AudioMode)
419 {
420 if (!DecodeMm(blockSize))
421 return S_FALSE;
422 }
423 else
424 {
425 if (!DecodeLz((Int32)blockSize))
426 return S_FALSE;
427 }
428
429 if (m_InBitStream.ExtraBitsWereRead())
430 return S_FALSE;
431
432 const UInt64 globalPos = m_OutWindowStream.GetProcessedSize();
433 pos = globalPos - blockStartPos;
434 if (pos < blockSize)
435 if (!ReadTables())
436 return S_FALSE;
437 pos = globalPos - startPos;
438 if (progress)
439 {
440 const UInt64 packSize = m_InBitStream.GetProcessedSize();
441 RINOK(progress->SetRatioInfo(&packSize, &pos))
442 }
443 }
444 if (pos > unPackSize)
445 return S_FALSE;
446
447 if (!ReadLastTables())
448 return S_FALSE;
449
450 _solidAllowed = true;
451
452 return m_OutWindowStream.Flush();
453 }
454
Z7_COM7F_IMF(CDecoder::Code (ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo * progress))455 Z7_COM7F_IMF(CDecoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,
456 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress))
457 {
458 try { return CodeReal(inStream, outStream, inSize, outSize, progress); }
459 catch(const CInBufferException &e) { return e.ErrorCode; }
460 catch(const CLzOutWindowException &e) { return e.ErrorCode; }
461 catch(...) { return S_FALSE; }
462 }
463
Z7_COM7F_IMF(CDecoder::SetDecoderProperties2 (const Byte * data,UInt32 size))464 Z7_COM7F_IMF(CDecoder::SetDecoderProperties2(const Byte *data, UInt32 size))
465 {
466 if (size < 1)
467 return E_INVALIDARG;
468 _isSolid = ((data[0] & 1) != 0);
469 return S_OK;
470 }
471
472 }}
473