Mercurial > vba-linux

annotate src/win32/7zip/7z/CPP/7zip/Compress/Rar1Decoder.cpp @ 1:f9f4f1b99eed

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