1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/win32/7zip/7z/CPP/7zip/Compress/Rar1Decoder.cpp	Sat Mar 03 10:31:27 2012 -0600
     1.3 @@ -0,0 +1,478 @@
     1.4 +// Rar1Decoder.cpp
     1.5 +// According to unRAR license, this code may not be used to develop
     1.6 +// a program that creates RAR archives
     1.7 + 
     1.8 +#include "StdAfx.h"
     1.9 +
    1.10 +#include "Rar1Decoder.h"
    1.11 +
    1.12 +namespace NCompress {
    1.13 +namespace NRar1 {
    1.14 +
    1.15 +static UInt32 PosL1[]={0,0,0,2,3,5,7,11,16,20,24,32,32, 256};
    1.16 +static UInt32 PosL2[]={0,0,0,0,5,7,9,13,18,22,26,34,36, 256};
    1.17 +static UInt32 PosHf0[]={0,0,0,0,0,8,16,24,33,33,33,33,33, 257};
    1.18 +static UInt32 PosHf1[]={0,0,0,0,0,0,4,44,60,76,80,80,127, 257};
    1.19 +static UInt32 PosHf2[]={0,0,0,0,0,0,2,7,53,117,233, 257,0};
    1.20 +static UInt32 PosHf3[]={0,0,0,0,0,0,0,2,16,218,251, 257,0};
    1.21 +static UInt32 PosHf4[]={0,0,0,0,0,0,0,0,0,255, 257,0,0};
    1.22 +
    1.23 +static const UInt32 kHistorySize = (1 << 16);
    1.24 +
    1.25 +class CCoderReleaser
    1.26 +{
    1.27 +  CDecoder *m_Coder;
    1.28 +public:
    1.29 +  CCoderReleaser(CDecoder *coder): m_Coder(coder) {}
    1.30 +  ~CCoderReleaser() { m_Coder->ReleaseStreams(); }
    1.31 +};
    1.32 +
    1.33 +CDecoder::CDecoder(): m_IsSolid(false) { }
    1.34 +
    1.35 +void CDecoder::InitStructures()
    1.36 +{
    1.37 +  for(int i = 0; i < kNumRepDists; i++)
    1.38 +    m_RepDists[i] = 0;
    1.39 +  m_RepDistPtr = 0;
    1.40 +  LastLength = 0;
    1.41 +  LastDist = 0;
    1.42 +}
    1.43 +
    1.44 +UInt32 CDecoder::ReadBits(int numBits) { return m_InBitStream.ReadBits(numBits); }
    1.45 +
    1.46 +HRESULT CDecoder::CopyBlock(UInt32 distance, UInt32 len)
    1.47 +{
    1.48 +  m_UnpackSize -= len;
    1.49 +  return m_OutWindowStream.CopyBlock(distance, len) ? S_OK : S_FALSE;
    1.50 +}
    1.51 +
    1.52 +
    1.53 +UInt32 CDecoder::DecodeNum(const UInt32 *posTab)
    1.54 +{
    1.55 +  UInt32 startPos = 2;
    1.56 +  UInt32 num = m_InBitStream.GetValue(12);
    1.57 +  for (;;)
    1.58 +  {
    1.59 +    UInt32 cur = (posTab[startPos + 1] - posTab[startPos]) << (12 - startPos);
    1.60 +    if (num < cur)
    1.61 +      break;
    1.62 +    startPos++;
    1.63 +    num -= cur;
    1.64 +  }
    1.65 +  m_InBitStream.MovePos(startPos);
    1.66 +  return((num >> (12 - startPos)) + posTab[startPos]);
    1.67 +}
    1.68 +
    1.69 +static Byte kShortLen1[]  = {1,3,4,4,5,6,7,8,8,4,4,5,6,6 };
    1.70 +static Byte kShortLen1a[] = {1,4,4,4,5,6,7,8,8,4,4,5,6,6,4 };
    1.71 +static Byte kShortLen2[]  = {2,3,3,3,4,4,5,6,6,4,4,5,6,6 };
    1.72 +static Byte kShortLen2a[] = {2,3,3,4,4,4,5,6,6,4,4,5,6,6,4 };
    1.73 +static UInt32 kShortXor1[] = {0,0xa0,0xd0,0xe0,0xf0,0xf8,0xfc,0xfe,0xff,0xc0,0x80,0x90,0x98,0x9c,0xb0};
    1.74 +static UInt32 kShortXor2[] = {0,0x40,0x60,0xa0,0xd0,0xe0,0xf0,0xf8,0xfc,0xc0,0x80,0x90,0x98,0x9c,0xb0};
    1.75 +
    1.76 +HRESULT CDecoder::ShortLZ()
    1.77 +{
    1.78 +  UInt32 len, saveLen, dist;
    1.79 +  int distancePlace;
    1.80 +  Byte *kShortLen;
    1.81 +  const UInt32 *kShortXor;
    1.82 +  NumHuf = 0;
    1.83 +
    1.84 +  if (LCount == 2)
    1.85 +  {
    1.86 +    if (ReadBits(1))
    1.87 +      return CopyBlock(LastDist, LastLength);
    1.88 +    LCount = 0;
    1.89 +  }
    1.90 +
    1.91 +  UInt32 bitField = m_InBitStream.GetValue(8);
    1.92 +
    1.93 +  if (AvrLn1 < 37)
    1.94 +  {
    1.95 +    kShortLen = Buf60 ? kShortLen1a : kShortLen1;
    1.96 +    kShortXor = kShortXor1;
    1.97 +  }
    1.98 +  else
    1.99 +  {
   1.100 +    kShortLen = Buf60 ? kShortLen2a : kShortLen2;
   1.101 +    kShortXor = kShortXor2;
   1.102 +  }
   1.103 +
   1.104 +  for (len = 0; ((bitField ^ kShortXor[len]) & (~(0xff >> kShortLen[len]))) != 0; len++);
   1.105 +  m_InBitStream.MovePos(kShortLen[len]);
   1.106 +
   1.107 +  if (len >= 9)
   1.108 +  {
   1.109 +    if (len == 9)
   1.110 +    {
   1.111 +      LCount++;
   1.112 +      return CopyBlock(LastDist, LastLength);
   1.113 +    }
   1.114 +    if (len == 14)
   1.115 +    {
   1.116 +      LCount = 0;
   1.117 +      len = DecodeNum(PosL2) + 5;
   1.118 +      dist = 0x8000 + ReadBits(15) - 1;
   1.119 +      LastLength = len;
   1.120 +      LastDist = dist;
   1.121 +      return CopyBlock(dist, len);
   1.122 +    }
   1.123 +
   1.124 +    LCount = 0;
   1.125 +    saveLen = len;
   1.126 +    dist = m_RepDists[(m_RepDistPtr - (len - 9)) & 3];
   1.127 +    len = DecodeNum(PosL1) + 2;
   1.128 +    if (len == 0x101 && saveLen == 10)
   1.129 +    {
   1.130 +      Buf60 ^= 1;
   1.131 +      return S_OK;
   1.132 +    }
   1.133 +    if (dist >= 256)
   1.134 +      len++;
   1.135 +    if (dist >= MaxDist3 - 1)
   1.136 +      len++;
   1.137 +  }
   1.138 +  else
   1.139 +  {
   1.140 +    LCount = 0;
   1.141 +    AvrLn1 += len;
   1.142 +    AvrLn1 -= AvrLn1 >> 4;
   1.143 +    
   1.144 +    distancePlace = DecodeNum(PosHf2) & 0xff;
   1.145 +    dist = ChSetA[distancePlace];
   1.146 +    if (--distancePlace != -1)
   1.147 +    {
   1.148 +      PlaceA[dist]--;
   1.149 +      UInt32 lastDistance = ChSetA[distancePlace];
   1.150 +      PlaceA[lastDistance]++;
   1.151 +      ChSetA[distancePlace + 1] = lastDistance;
   1.152 +      ChSetA[distancePlace] = dist;
   1.153 +    }
   1.154 +    len += 2;
   1.155 +  }
   1.156 +  m_RepDists[m_RepDistPtr++] = dist;
   1.157 +  m_RepDistPtr &= 3;
   1.158 +  LastLength = len;
   1.159 +  LastDist = dist;
   1.160 +  return CopyBlock(dist, len);
   1.161 +}
   1.162 +
   1.163 +
   1.164 +HRESULT CDecoder::LongLZ()
   1.165 +{
   1.166 +  UInt32 len;
   1.167 +  UInt32 dist;
   1.168 +  UInt32 distancePlace, newDistancePlace;
   1.169 +  UInt32 oldAvr2, oldAvr3;
   1.170 +
   1.171 +  NumHuf = 0;
   1.172 +  Nlzb += 16;
   1.173 +  if (Nlzb > 0xff)
   1.174 +  {
   1.175 +    Nlzb = 0x90;
   1.176 +    Nhfb >>= 1;
   1.177 +  }
   1.178 +  oldAvr2=AvrLn2;
   1.179 +
   1.180 +  if (AvrLn2 >= 122)
   1.181 +    len = DecodeNum(PosL2);
   1.182 +  else if (AvrLn2 >= 64)
   1.183 +    len = DecodeNum(PosL1);
   1.184 +  else
   1.185 +  {
   1.186 +    UInt32 bitField = m_InBitStream.GetValue(16);
   1.187 +    if (bitField < 0x100)
   1.188 +    {
   1.189 +      len = bitField;
   1.190 +      m_InBitStream.MovePos(16);
   1.191 +    }
   1.192 +    else
   1.193 +    {
   1.194 +      for (len = 0; ((bitField << len) & 0x8000) == 0; len++)
   1.195 +        ;
   1.196 +      m_InBitStream.MovePos(len + 1);
   1.197 +    }
   1.198 +  }
   1.199 +
   1.200 +  AvrLn2 += len;
   1.201 +  AvrLn2 -= AvrLn2 >> 5;
   1.202 +
   1.203 +  if (AvrPlcB > 0x28ff)
   1.204 +    distancePlace = DecodeNum(PosHf2);
   1.205 +  else if (AvrPlcB > 0x6ff)
   1.206 +    distancePlace = DecodeNum(PosHf1);
   1.207 +  else
   1.208 +    distancePlace = DecodeNum(PosHf0);
   1.209 +
   1.210 +  AvrPlcB += distancePlace;
   1.211 +  AvrPlcB -= AvrPlcB >> 8;
   1.212 +  for (;;)
   1.213 +  {
   1.214 +    dist = ChSetB[distancePlace & 0xff];
   1.215 +    newDistancePlace = NToPlB[dist++ & 0xff]++;
   1.216 +    if (!(dist & 0xff))
   1.217 +      CorrHuff(ChSetB,NToPlB);
   1.218 +    else
   1.219 +      break;
   1.220 +  }
   1.221 +
   1.222 +  ChSetB[distancePlace] = ChSetB[newDistancePlace];
   1.223 +  ChSetB[newDistancePlace] = dist;
   1.224 +
   1.225 +  dist = ((dist & 0xff00) >> 1) | ReadBits(7);
   1.226 +
   1.227 +  oldAvr3 = AvrLn3;
   1.228 +  if (len != 1 && len != 4)
   1.229 +    if (len == 0 && dist <= MaxDist3)
   1.230 +    {
   1.231 +      AvrLn3++;
   1.232 +      AvrLn3 -= AvrLn3 >> 8;
   1.233 +    }
   1.234 +    else
   1.235 +      if (AvrLn3 > 0)
   1.236 +        AvrLn3--;
   1.237 +  len += 3;
   1.238 +  if (dist >= MaxDist3)
   1.239 +    len++;
   1.240 +  if (dist <= 256)
   1.241 +    len += 8;
   1.242 +  if (oldAvr3 > 0xb0 || AvrPlc >= 0x2a00 && oldAvr2 < 0x40)
   1.243 +    MaxDist3 = 0x7f00;
   1.244 +  else
   1.245 +    MaxDist3 = 0x2001;
   1.246 +  m_RepDists[m_RepDistPtr++] = --dist;
   1.247 +  m_RepDistPtr &= 3;
   1.248 +  LastLength = len;
   1.249 +  LastDist = dist;
   1.250 +  return CopyBlock(dist, len);
   1.251 +}
   1.252 +
   1.253 +
   1.254 +HRESULT CDecoder::HuffDecode()
   1.255 +{
   1.256 +  UInt32 curByte, newBytePlace;
   1.257 +  UInt32 len;
   1.258 +  UInt32 dist;
   1.259 +  int bytePlace;
   1.260 +
   1.261 +  if      (AvrPlc > 0x75ff)  bytePlace = DecodeNum(PosHf4);
   1.262 +  else if (AvrPlc > 0x5dff)  bytePlace = DecodeNum(PosHf3);
   1.263 +  else if (AvrPlc > 0x35ff)  bytePlace = DecodeNum(PosHf2);
   1.264 +  else if (AvrPlc > 0x0dff)  bytePlace = DecodeNum(PosHf1);
   1.265 +  else                       bytePlace = DecodeNum(PosHf0);
   1.266 +  if (StMode)
   1.267 +  {
   1.268 +    if (--bytePlace == -1)
   1.269 +    {
   1.270 +      if (ReadBits(1))
   1.271 +      {
   1.272 +        NumHuf = StMode = 0;
   1.273 +        return S_OK;
   1.274 +      }
   1.275 +      else
   1.276 +      {
   1.277 +        len = (ReadBits(1)) ? 4 : 3;
   1.278 +        dist = DecodeNum(PosHf2);
   1.279 +        dist = (dist << 5) | ReadBits(5);
   1.280 +        return CopyBlock(dist - 1, len);
   1.281 +      }
   1.282 +    }
   1.283 +  }
   1.284 +  else if (NumHuf++ >= 16 && FlagsCnt == 0)
   1.285 +    StMode = 1;
   1.286 +  bytePlace &= 0xff;
   1.287 +  AvrPlc += bytePlace;
   1.288 +  AvrPlc -= AvrPlc >> 8;
   1.289 +  Nhfb+=16;
   1.290 +  if (Nhfb > 0xff)
   1.291 +  {
   1.292 +    Nhfb=0x90;
   1.293 +    Nlzb >>= 1;
   1.294 +  }
   1.295 +
   1.296 +  m_UnpackSize --;
   1.297 +  m_OutWindowStream.PutByte((Byte)(ChSet[bytePlace] >> 8));
   1.298 +
   1.299 +  for (;;)
   1.300 +  {
   1.301 +    curByte = ChSet[bytePlace];
   1.302 +    newBytePlace = NToPl[curByte++ & 0xff]++;
   1.303 +    if ((curByte & 0xff) > 0xa1)
   1.304 +      CorrHuff(ChSet, NToPl);
   1.305 +    else
   1.306 +      break;
   1.307 +  }
   1.308 +
   1.309 +  ChSet[bytePlace] = ChSet[newBytePlace];
   1.310 +  ChSet[newBytePlace] = curByte;
   1.311 +  return S_OK;
   1.312 +}
   1.313 +
   1.314 +
   1.315 +void CDecoder::GetFlagsBuf()
   1.316 +{
   1.317 +  UInt32 flags, newFlagsPlace;
   1.318 +  UInt32 flagsPlace = DecodeNum(PosHf2);
   1.319 +
   1.320 +  for (;;)
   1.321 +  {
   1.322 +    flags = ChSetC[flagsPlace];
   1.323 +    FlagBuf = flags >> 8;
   1.324 +    newFlagsPlace = NToPlC[flags++ & 0xff]++;
   1.325 +    if ((flags & 0xff) != 0)
   1.326 +      break;
   1.327 +    CorrHuff(ChSetC, NToPlC);
   1.328 +  }
   1.329 +
   1.330 +  ChSetC[flagsPlace] = ChSetC[newFlagsPlace];
   1.331 +  ChSetC[newFlagsPlace] = flags;
   1.332 +}
   1.333 +
   1.334 +void CDecoder::InitData()
   1.335 +{
   1.336 +  if (!m_IsSolid)
   1.337 +  {
   1.338 +    AvrPlcB = AvrLn1 = AvrLn2 = AvrLn3 = NumHuf = Buf60 = 0;
   1.339 +    AvrPlc = 0x3500;
   1.340 +    MaxDist3 = 0x2001;
   1.341 +    Nhfb = Nlzb = 0x80;
   1.342 +  }
   1.343 +  FlagsCnt = 0;
   1.344 +  FlagBuf = 0;
   1.345 +  StMode = 0;
   1.346 +  LCount = 0;
   1.347 +}
   1.348 +
   1.349 +void CDecoder::CorrHuff(UInt32 *CharSet,UInt32 *NumToPlace)
   1.350 +{
   1.351 +  int i;
   1.352 +  for (i = 7; i >= 0; i--)
   1.353 +    for (int j = 0; j < 32; j++, CharSet++)
   1.354 +      *CharSet = (*CharSet & ~0xff) | i;
   1.355 +  memset(NumToPlace, 0, sizeof(NToPl));
   1.356 +  for (i = 6; i >= 0; i--)
   1.357 +    NumToPlace[i] = (7 - i) * 32;
   1.358 +}
   1.359 +
   1.360 +void CDecoder::InitHuff()
   1.361 +{
   1.362 +  for (UInt32 i = 0; i < 256; i++)
   1.363 +  {
   1.364 +    Place[i] = PlaceA[i] = PlaceB[i] = i;
   1.365 +    PlaceC[i] = (~i + 1) & 0xff;
   1.366 +    ChSet[i] = ChSetB[i] = i << 8;
   1.367 +    ChSetA[i] = i;
   1.368 +    ChSetC[i] = ((~i + 1) & 0xff) << 8;
   1.369 +  }
   1.370 +  memset(NToPl, 0, sizeof(NToPl));
   1.371 +  memset(NToPlB, 0, sizeof(NToPlB));
   1.372 +  memset(NToPlC, 0, sizeof(NToPlC));
   1.373 +  CorrHuff(ChSetB, NToPlB);
   1.374 +}
   1.375 +
   1.376 +HRESULT CDecoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream,
   1.377 +    const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo * /* progress */)
   1.378 +{
   1.379 +  if (inSize == NULL || outSize == NULL)
   1.380 +    return E_INVALIDARG;
   1.381 +
   1.382 +  if (!m_OutWindowStream.Create(kHistorySize))
   1.383 +    return E_OUTOFMEMORY;
   1.384 +  if (!m_InBitStream.Create(1 << 20))
   1.385 +    return E_OUTOFMEMORY;
   1.386 +
   1.387 +  m_UnpackSize = (Int64)*outSize;
   1.388 +  m_OutWindowStream.SetStream(outStream);
   1.389 +  m_OutWindowStream.Init(m_IsSolid);
   1.390 +  m_InBitStream.SetStream(inStream);
   1.391 +  m_InBitStream.Init();
   1.392 +
   1.393 +  CCoderReleaser coderReleaser(this);
   1.394 +  InitData();
   1.395 +  if (!m_IsSolid)
   1.396 +  {
   1.397 +    InitStructures();
   1.398 +    InitHuff();
   1.399 +  }
   1.400 +  if (m_UnpackSize > 0)
   1.401 +  {
   1.402 +    GetFlagsBuf();
   1.403 +    FlagsCnt = 8;
   1.404 +  }
   1.405 +
   1.406 +  while (m_UnpackSize > 0)
   1.407 +  {
   1.408 +    if (StMode)
   1.409 +    {
   1.410 +      RINOK(HuffDecode());
   1.411 +      continue;
   1.412 +    }
   1.413 +
   1.414 +    if (--FlagsCnt < 0)
   1.415 +    {
   1.416 +      GetFlagsBuf();
   1.417 +      FlagsCnt=7;
   1.418 +    }
   1.419 +
   1.420 +    if (FlagBuf & 0x80)
   1.421 +    {
   1.422 +      FlagBuf <<= 1;
   1.423 +      if (Nlzb > Nhfb)
   1.424 +      {
   1.425 +        RINOK(LongLZ());
   1.426 +      }
   1.427 +      else
   1.428 +      {
   1.429 +        RINOK(HuffDecode());
   1.430 +      }
   1.431 +    }
   1.432 +    else
   1.433 +    {
   1.434 +      FlagBuf <<= 1;
   1.435 +      if (--FlagsCnt < 0)
   1.436 +      {
   1.437 +        GetFlagsBuf();
   1.438 +        FlagsCnt = 7;
   1.439 +      }
   1.440 +      if (FlagBuf & 0x80)
   1.441 +      {
   1.442 +        FlagBuf <<= 1;
   1.443 +        if (Nlzb > Nhfb)
   1.444 +        {
   1.445 +          RINOK(HuffDecode());
   1.446 +        }
   1.447 +        else
   1.448 +        {
   1.449 +          RINOK(LongLZ());
   1.450 +        }
   1.451 +      }
   1.452 +      else
   1.453 +      {
   1.454 +        FlagBuf <<= 1;
   1.455 +        RINOK(ShortLZ());
   1.456 +      }
   1.457 +    }
   1.458 +  }
   1.459 +  if (m_UnpackSize < 0)
   1.460 +    return S_FALSE;
   1.461 +  return m_OutWindowStream.Flush();
   1.462 +}
   1.463 +
   1.464 +STDMETHODIMP CDecoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,
   1.465 +    const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress)
   1.466 +{
   1.467 +  try { return CodeReal(inStream, outStream, inSize, outSize, progress); }
   1.468 +  catch(const CInBufferException &e) { return e.ErrorCode; }
   1.469 +  catch(const CLzOutWindowException &e) { return e.ErrorCode; }
   1.470 +  catch(...) { return S_FALSE; }
   1.471 +}
   1.472 +
   1.473 +STDMETHODIMP CDecoder::SetDecoderProperties2(const Byte *data, UInt32 size)
   1.474 +{
   1.475 +  if (size < 1)
   1.476 +    return E_INVALIDARG;
   1.477 +  m_IsSolid = (data[0] != 0);
   1.478 +  return S_OK;
   1.479 +}
   1.480 +
   1.481 +}}