Mercurial > vba-linux
comparison src/win32/7zip/7z/CPP/7zip/Compress/Rar1Decoder.cpp @ 1:f9f4f1b99eed
importing src directory
author | Robert McIntyre <rlm@mit.edu> |
---|---|
date | Sat, 03 Mar 2012 10:31:27 -0600 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
0:8ced16adf2e1 | 1:f9f4f1b99eed |
---|---|
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 UInt32 PosL1[]={0,0,0,2,3,5,7,11,16,20,24,32,32, 256}; | |
13 static UInt32 PosL2[]={0,0,0,0,5,7,9,13,18,22,26,34,36, 256}; | |
14 static UInt32 PosHf0[]={0,0,0,0,0,8,16,24,33,33,33,33,33, 257}; | |
15 static UInt32 PosHf1[]={0,0,0,0,0,0,4,44,60,76,80,80,127, 257}; | |
16 static UInt32 PosHf2[]={0,0,0,0,0,0,2,7,53,117,233, 257,0}; | |
17 static UInt32 PosHf3[]={0,0,0,0,0,0,0,2,16,218,251, 257,0}; | |
18 static UInt32 PosHf4[]={0,0,0,0,0,0,0,0,0,255, 257,0,0}; | |
19 | |
20 static const UInt32 kHistorySize = (1 << 16); | |
21 | |
22 class CCoderReleaser | |
23 { | |
24 CDecoder *m_Coder; | |
25 public: | |
26 CCoderReleaser(CDecoder *coder): m_Coder(coder) {} | |
27 ~CCoderReleaser() { m_Coder->ReleaseStreams(); } | |
28 }; | |
29 | |
30 CDecoder::CDecoder(): m_IsSolid(false) { } | |
31 | |
32 void CDecoder::InitStructures() | |
33 { | |
34 for(int i = 0; i < kNumRepDists; i++) | |
35 m_RepDists[i] = 0; | |
36 m_RepDistPtr = 0; | |
37 LastLength = 0; | |
38 LastDist = 0; | |
39 } | |
40 | |
41 UInt32 CDecoder::ReadBits(int numBits) { return m_InBitStream.ReadBits(numBits); } | |
42 | |
43 HRESULT CDecoder::CopyBlock(UInt32 distance, UInt32 len) | |
44 { | |
45 m_UnpackSize -= len; | |
46 return m_OutWindowStream.CopyBlock(distance, len) ? S_OK : S_FALSE; | |
47 } | |
48 | |
49 | |
50 UInt32 CDecoder::DecodeNum(const UInt32 *posTab) | |
51 { | |
52 UInt32 startPos = 2; | |
53 UInt32 num = m_InBitStream.GetValue(12); | |
54 for (;;) | |
55 { | |
56 UInt32 cur = (posTab[startPos + 1] - posTab[startPos]) << (12 - startPos); | |
57 if (num < cur) | |
58 break; | |
59 startPos++; | |
60 num -= cur; | |
61 } | |
62 m_InBitStream.MovePos(startPos); | |
63 return((num >> (12 - startPos)) + posTab[startPos]); | |
64 } | |
65 | |
66 static Byte kShortLen1[] = {1,3,4,4,5,6,7,8,8,4,4,5,6,6 }; | |
67 static Byte kShortLen1a[] = {1,4,4,4,5,6,7,8,8,4,4,5,6,6,4 }; | |
68 static Byte kShortLen2[] = {2,3,3,3,4,4,5,6,6,4,4,5,6,6 }; | |
69 static Byte kShortLen2a[] = {2,3,3,4,4,4,5,6,6,4,4,5,6,6,4 }; | |
70 static UInt32 kShortXor1[] = {0,0xa0,0xd0,0xe0,0xf0,0xf8,0xfc,0xfe,0xff,0xc0,0x80,0x90,0x98,0x9c,0xb0}; | |
71 static UInt32 kShortXor2[] = {0,0x40,0x60,0xa0,0xd0,0xe0,0xf0,0xf8,0xfc,0xc0,0x80,0x90,0x98,0x9c,0xb0}; | |
72 | |
73 HRESULT CDecoder::ShortLZ() | |
74 { | |
75 UInt32 len, saveLen, dist; | |
76 int distancePlace; | |
77 Byte *kShortLen; | |
78 const UInt32 *kShortXor; | |
79 NumHuf = 0; | |
80 | |
81 if (LCount == 2) | |
82 { | |
83 if (ReadBits(1)) | |
84 return CopyBlock(LastDist, LastLength); | |
85 LCount = 0; | |
86 } | |
87 | |
88 UInt32 bitField = m_InBitStream.GetValue(8); | |
89 | |
90 if (AvrLn1 < 37) | |
91 { | |
92 kShortLen = Buf60 ? kShortLen1a : kShortLen1; | |
93 kShortXor = kShortXor1; | |
94 } | |
95 else | |
96 { | |
97 kShortLen = Buf60 ? kShortLen2a : kShortLen2; | |
98 kShortXor = kShortXor2; | |
99 } | |
100 | |
101 for (len = 0; ((bitField ^ kShortXor[len]) & (~(0xff >> kShortLen[len]))) != 0; len++); | |
102 m_InBitStream.MovePos(kShortLen[len]); | |
103 | |
104 if (len >= 9) | |
105 { | |
106 if (len == 9) | |
107 { | |
108 LCount++; | |
109 return CopyBlock(LastDist, LastLength); | |
110 } | |
111 if (len == 14) | |
112 { | |
113 LCount = 0; | |
114 len = DecodeNum(PosL2) + 5; | |
115 dist = 0x8000 + ReadBits(15) - 1; | |
116 LastLength = len; | |
117 LastDist = dist; | |
118 return CopyBlock(dist, len); | |
119 } | |
120 | |
121 LCount = 0; | |
122 saveLen = len; | |
123 dist = m_RepDists[(m_RepDistPtr - (len - 9)) & 3]; | |
124 len = DecodeNum(PosL1) + 2; | |
125 if (len == 0x101 && saveLen == 10) | |
126 { | |
127 Buf60 ^= 1; | |
128 return S_OK; | |
129 } | |
130 if (dist >= 256) | |
131 len++; | |
132 if (dist >= MaxDist3 - 1) | |
133 len++; | |
134 } | |
135 else | |
136 { | |
137 LCount = 0; | |
138 AvrLn1 += len; | |
139 AvrLn1 -= AvrLn1 >> 4; | |
140 | |
141 distancePlace = DecodeNum(PosHf2) & 0xff; | |
142 dist = ChSetA[distancePlace]; | |
143 if (--distancePlace != -1) | |
144 { | |
145 PlaceA[dist]--; | |
146 UInt32 lastDistance = ChSetA[distancePlace]; | |
147 PlaceA[lastDistance]++; | |
148 ChSetA[distancePlace + 1] = lastDistance; | |
149 ChSetA[distancePlace] = dist; | |
150 } | |
151 len += 2; | |
152 } | |
153 m_RepDists[m_RepDistPtr++] = dist; | |
154 m_RepDistPtr &= 3; | |
155 LastLength = len; | |
156 LastDist = dist; | |
157 return CopyBlock(dist, len); | |
158 } | |
159 | |
160 | |
161 HRESULT CDecoder::LongLZ() | |
162 { | |
163 UInt32 len; | |
164 UInt32 dist; | |
165 UInt32 distancePlace, newDistancePlace; | |
166 UInt32 oldAvr2, oldAvr3; | |
167 | |
168 NumHuf = 0; | |
169 Nlzb += 16; | |
170 if (Nlzb > 0xff) | |
171 { | |
172 Nlzb = 0x90; | |
173 Nhfb >>= 1; | |
174 } | |
175 oldAvr2=AvrLn2; | |
176 | |
177 if (AvrLn2 >= 122) | |
178 len = DecodeNum(PosL2); | |
179 else if (AvrLn2 >= 64) | |
180 len = DecodeNum(PosL1); | |
181 else | |
182 { | |
183 UInt32 bitField = m_InBitStream.GetValue(16); | |
184 if (bitField < 0x100) | |
185 { | |
186 len = bitField; | |
187 m_InBitStream.MovePos(16); | |
188 } | |
189 else | |
190 { | |
191 for (len = 0; ((bitField << len) & 0x8000) == 0; len++) | |
192 ; | |
193 m_InBitStream.MovePos(len + 1); | |
194 } | |
195 } | |
196 | |
197 AvrLn2 += len; | |
198 AvrLn2 -= AvrLn2 >> 5; | |
199 | |
200 if (AvrPlcB > 0x28ff) | |
201 distancePlace = DecodeNum(PosHf2); | |
202 else if (AvrPlcB > 0x6ff) | |
203 distancePlace = DecodeNum(PosHf1); | |
204 else | |
205 distancePlace = DecodeNum(PosHf0); | |
206 | |
207 AvrPlcB += distancePlace; | |
208 AvrPlcB -= AvrPlcB >> 8; | |
209 for (;;) | |
210 { | |
211 dist = ChSetB[distancePlace & 0xff]; | |
212 newDistancePlace = NToPlB[dist++ & 0xff]++; | |
213 if (!(dist & 0xff)) | |
214 CorrHuff(ChSetB,NToPlB); | |
215 else | |
216 break; | |
217 } | |
218 | |
219 ChSetB[distancePlace] = ChSetB[newDistancePlace]; | |
220 ChSetB[newDistancePlace] = dist; | |
221 | |
222 dist = ((dist & 0xff00) >> 1) | ReadBits(7); | |
223 | |
224 oldAvr3 = AvrLn3; | |
225 if (len != 1 && len != 4) | |
226 if (len == 0 && dist <= MaxDist3) | |
227 { | |
228 AvrLn3++; | |
229 AvrLn3 -= AvrLn3 >> 8; | |
230 } | |
231 else | |
232 if (AvrLn3 > 0) | |
233 AvrLn3--; | |
234 len += 3; | |
235 if (dist >= MaxDist3) | |
236 len++; | |
237 if (dist <= 256) | |
238 len += 8; | |
239 if (oldAvr3 > 0xb0 || AvrPlc >= 0x2a00 && oldAvr2 < 0x40) | |
240 MaxDist3 = 0x7f00; | |
241 else | |
242 MaxDist3 = 0x2001; | |
243 m_RepDists[m_RepDistPtr++] = --dist; | |
244 m_RepDistPtr &= 3; | |
245 LastLength = len; | |
246 LastDist = dist; | |
247 return CopyBlock(dist, len); | |
248 } | |
249 | |
250 | |
251 HRESULT CDecoder::HuffDecode() | |
252 { | |
253 UInt32 curByte, newBytePlace; | |
254 UInt32 len; | |
255 UInt32 dist; | |
256 int bytePlace; | |
257 | |
258 if (AvrPlc > 0x75ff) bytePlace = DecodeNum(PosHf4); | |
259 else if (AvrPlc > 0x5dff) bytePlace = DecodeNum(PosHf3); | |
260 else if (AvrPlc > 0x35ff) bytePlace = DecodeNum(PosHf2); | |
261 else if (AvrPlc > 0x0dff) bytePlace = DecodeNum(PosHf1); | |
262 else bytePlace = DecodeNum(PosHf0); | |
263 if (StMode) | |
264 { | |
265 if (--bytePlace == -1) | |
266 { | |
267 if (ReadBits(1)) | |
268 { | |
269 NumHuf = StMode = 0; | |
270 return S_OK; | |
271 } | |
272 else | |
273 { | |
274 len = (ReadBits(1)) ? 4 : 3; | |
275 dist = DecodeNum(PosHf2); | |
276 dist = (dist << 5) | ReadBits(5); | |
277 return CopyBlock(dist - 1, len); | |
278 } | |
279 } | |
280 } | |
281 else if (NumHuf++ >= 16 && FlagsCnt == 0) | |
282 StMode = 1; | |
283 bytePlace &= 0xff; | |
284 AvrPlc += bytePlace; | |
285 AvrPlc -= AvrPlc >> 8; | |
286 Nhfb+=16; | |
287 if (Nhfb > 0xff) | |
288 { | |
289 Nhfb=0x90; | |
290 Nlzb >>= 1; | |
291 } | |
292 | |
293 m_UnpackSize --; | |
294 m_OutWindowStream.PutByte((Byte)(ChSet[bytePlace] >> 8)); | |
295 | |
296 for (;;) | |
297 { | |
298 curByte = ChSet[bytePlace]; | |
299 newBytePlace = NToPl[curByte++ & 0xff]++; | |
300 if ((curByte & 0xff) > 0xa1) | |
301 CorrHuff(ChSet, NToPl); | |
302 else | |
303 break; | |
304 } | |
305 | |
306 ChSet[bytePlace] = ChSet[newBytePlace]; | |
307 ChSet[newBytePlace] = curByte; | |
308 return S_OK; | |
309 } | |
310 | |
311 | |
312 void CDecoder::GetFlagsBuf() | |
313 { | |
314 UInt32 flags, newFlagsPlace; | |
315 UInt32 flagsPlace = DecodeNum(PosHf2); | |
316 | |
317 for (;;) | |
318 { | |
319 flags = ChSetC[flagsPlace]; | |
320 FlagBuf = flags >> 8; | |
321 newFlagsPlace = NToPlC[flags++ & 0xff]++; | |
322 if ((flags & 0xff) != 0) | |
323 break; | |
324 CorrHuff(ChSetC, NToPlC); | |
325 } | |
326 | |
327 ChSetC[flagsPlace] = ChSetC[newFlagsPlace]; | |
328 ChSetC[newFlagsPlace] = flags; | |
329 } | |
330 | |
331 void CDecoder::InitData() | |
332 { | |
333 if (!m_IsSolid) | |
334 { | |
335 AvrPlcB = AvrLn1 = AvrLn2 = AvrLn3 = NumHuf = Buf60 = 0; | |
336 AvrPlc = 0x3500; | |
337 MaxDist3 = 0x2001; | |
338 Nhfb = Nlzb = 0x80; | |
339 } | |
340 FlagsCnt = 0; | |
341 FlagBuf = 0; | |
342 StMode = 0; | |
343 LCount = 0; | |
344 } | |
345 | |
346 void CDecoder::CorrHuff(UInt32 *CharSet,UInt32 *NumToPlace) | |
347 { | |
348 int i; | |
349 for (i = 7; i >= 0; i--) | |
350 for (int j = 0; j < 32; j++, CharSet++) | |
351 *CharSet = (*CharSet & ~0xff) | i; | |
352 memset(NumToPlace, 0, sizeof(NToPl)); | |
353 for (i = 6; i >= 0; i--) | |
354 NumToPlace[i] = (7 - i) * 32; | |
355 } | |
356 | |
357 void CDecoder::InitHuff() | |
358 { | |
359 for (UInt32 i = 0; i < 256; i++) | |
360 { | |
361 Place[i] = PlaceA[i] = PlaceB[i] = i; | |
362 PlaceC[i] = (~i + 1) & 0xff; | |
363 ChSet[i] = ChSetB[i] = i << 8; | |
364 ChSetA[i] = i; | |
365 ChSetC[i] = ((~i + 1) & 0xff) << 8; | |
366 } | |
367 memset(NToPl, 0, sizeof(NToPl)); | |
368 memset(NToPlB, 0, sizeof(NToPlB)); | |
369 memset(NToPlC, 0, sizeof(NToPlC)); | |
370 CorrHuff(ChSetB, NToPlB); | |
371 } | |
372 | |
373 HRESULT CDecoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream, | |
374 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo * /* progress */) | |
375 { | |
376 if (inSize == NULL || outSize == NULL) | |
377 return E_INVALIDARG; | |
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_UnpackSize = (Int64)*outSize; | |
385 m_OutWindowStream.SetStream(outStream); | |
386 m_OutWindowStream.Init(m_IsSolid); | |
387 m_InBitStream.SetStream(inStream); | |
388 m_InBitStream.Init(); | |
389 | |
390 CCoderReleaser coderReleaser(this); | |
391 InitData(); | |
392 if (!m_IsSolid) | |
393 { | |
394 InitStructures(); | |
395 InitHuff(); | |
396 } | |
397 if (m_UnpackSize > 0) | |
398 { | |
399 GetFlagsBuf(); | |
400 FlagsCnt = 8; | |
401 } | |
402 | |
403 while (m_UnpackSize > 0) | |
404 { | |
405 if (StMode) | |
406 { | |
407 RINOK(HuffDecode()); | |
408 continue; | |
409 } | |
410 | |
411 if (--FlagsCnt < 0) | |
412 { | |
413 GetFlagsBuf(); | |
414 FlagsCnt=7; | |
415 } | |
416 | |
417 if (FlagBuf & 0x80) | |
418 { | |
419 FlagBuf <<= 1; | |
420 if (Nlzb > Nhfb) | |
421 { | |
422 RINOK(LongLZ()); | |
423 } | |
424 else | |
425 { | |
426 RINOK(HuffDecode()); | |
427 } | |
428 } | |
429 else | |
430 { | |
431 FlagBuf <<= 1; | |
432 if (--FlagsCnt < 0) | |
433 { | |
434 GetFlagsBuf(); | |
435 FlagsCnt = 7; | |
436 } | |
437 if (FlagBuf & 0x80) | |
438 { | |
439 FlagBuf <<= 1; | |
440 if (Nlzb > Nhfb) | |
441 { | |
442 RINOK(HuffDecode()); | |
443 } | |
444 else | |
445 { | |
446 RINOK(LongLZ()); | |
447 } | |
448 } | |
449 else | |
450 { | |
451 FlagBuf <<= 1; | |
452 RINOK(ShortLZ()); | |
453 } | |
454 } | |
455 } | |
456 if (m_UnpackSize < 0) | |
457 return S_FALSE; | |
458 return m_OutWindowStream.Flush(); | |
459 } | |
460 | |
461 STDMETHODIMP CDecoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream, | |
462 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress) | |
463 { | |
464 try { return CodeReal(inStream, outStream, inSize, outSize, progress); } | |
465 catch(const CInBufferException &e) { return e.ErrorCode; } | |
466 catch(const CLzOutWindowException &e) { return e.ErrorCode; } | |
467 catch(...) { return S_FALSE; } | |
468 } | |
469 | |
470 STDMETHODIMP CDecoder::SetDecoderProperties2(const Byte *data, UInt32 size) | |
471 { | |
472 if (size < 1) | |
473 return E_INVALIDARG; | |
474 m_IsSolid = (data[0] != 0); | |
475 return S_OK; | |
476 } | |
477 | |
478 }} |