CPP/7zip/Compress/LzxDecoder.cpp

   1 // LzxDecoder.cpp\r
   2 \r
   3 #include "StdAfx.h"\r
   4 \r
   5 #include "../../Common/Defs.h"\r
   6 \r
   7 #include "LzxDecoder.h"\r
   8 \r
   9 namespace NCompress {\r
  10 namespace NLzx {\r
  11 \r
  12 const int kLenIdNeedInit = -2;\r
  13 \r
  14 CDecoder::CDecoder(bool wimMode):\r
  15   _keepHistory(false),\r
  16   _skipByte(false),\r
  17   _wimMode(wimMode)\r
  18 {\r
  19   m_x86ConvertOutStreamSpec = new Cx86ConvertOutStream;\r
  20   m_x86ConvertOutStream = m_x86ConvertOutStreamSpec;\r
  21 }\r
  22 \r
  23 void CDecoder::ReleaseStreams()\r
  24 {\r
  25   m_OutWindowStream.ReleaseStream();\r
  26   m_InBitStream.ReleaseStream();\r
  27   m_x86ConvertOutStreamSpec->ReleaseStream();\r
  28 }\r
  29 \r
  30 STDMETHODIMP CDecoder::Flush()\r
  31 {\r
  32   RINOK(m_OutWindowStream.Flush());\r
  33   return m_x86ConvertOutStreamSpec->Flush();\r
  34 }\r
  35 \r
  36 UInt32 CDecoder::ReadBits(unsigned numBits) { return m_InBitStream.ReadBits(numBits); }\r
  37 \r
  38 #define RIF(x) { if (!(x)) return false; }\r
  39 \r
  40 bool CDecoder::ReadTable(Byte *lastLevels, Byte *newLevels, UInt32 numSymbols)\r
  41 {\r
  42   Byte levelLevels[kLevelTableSize];\r
  43   UInt32 i;\r
  44   for (i = 0; i < kLevelTableSize; i++)\r
  45     levelLevels[i] = (Byte)ReadBits(kNumBitsForPreTreeLevel);\r
  46   RIF(m_LevelDecoder.SetCodeLengths(levelLevels));\r
  47   unsigned num = 0;\r
  48   Byte symbol = 0;\r
  49   for (i = 0; i < numSymbols;)\r
  50   {\r
  51     if (num != 0)\r
  52     {\r
  53       lastLevels[i] = newLevels[i] = symbol;\r
  54       i++;\r
  55       num--;\r
  56       continue;\r
  57     }\r
  58     UInt32 number = m_LevelDecoder.DecodeSymbol(&m_InBitStream);\r
  59     if (number == kLevelSymbolZeros)\r
  60     {\r
  61       num = kLevelSymbolZerosStartValue + (unsigned)ReadBits(kLevelSymbolZerosNumBits);\r
  62       symbol = 0;\r
  63     }\r
  64     else if (number == kLevelSymbolZerosBig)\r
  65     {\r
  66       num = kLevelSymbolZerosBigStartValue + (unsigned)ReadBits(kLevelSymbolZerosBigNumBits);\r
  67       symbol = 0;\r
  68     }\r
  69     else if (number == kLevelSymbolSame || number <= kNumHuffmanBits)\r
  70     {\r
  71       if (number <= kNumHuffmanBits)\r
  72         num = 1;\r
  73       else\r
  74       {\r
  75         num = kLevelSymbolSameStartValue + (unsigned)ReadBits(kLevelSymbolSameNumBits);\r
  76         number = m_LevelDecoder.DecodeSymbol(&m_InBitStream);\r
  77         if (number > kNumHuffmanBits)\r
  78           return false;\r
  79       }\r
  80       symbol = Byte((17 + lastLevels[i] - number) % (kNumHuffmanBits + 1));\r
  81     }\r
  82     else\r
  83       return false;\r
  84   }\r
  85   return true;\r
  86 }\r
  87 \r
  88 bool CDecoder::ReadTables(void)\r
  89 {\r
  90   Byte newLevels[kMaxTableSize];\r
  91   {\r
  92     if (_skipByte)\r
  93       m_InBitStream.DirectReadByte();\r
  94     m_InBitStream.Normalize();\r
  95 \r
  96     unsigned blockType = (unsigned)ReadBits(kNumBlockTypeBits);\r
  97     if (blockType > kBlockTypeUncompressed)\r
  98       return false;\r
  99     if (_wimMode)\r
 100       if (ReadBits(1) == 1)\r
 101         m_UnCompressedBlockSize = (1 << 15);\r
 102       else\r
 103         m_UnCompressedBlockSize = ReadBits(16);\r
 104     else\r
 105       m_UnCompressedBlockSize = m_InBitStream.ReadBitsBig(kUncompressedBlockSizeNumBits);\r
 106 \r
 107     m_IsUncompressedBlock = (blockType == kBlockTypeUncompressed);\r
 108 \r
 109     _skipByte = (m_IsUncompressedBlock && ((m_UnCompressedBlockSize & 1) != 0));\r
 110 \r
 111     if (m_IsUncompressedBlock)\r
 112     {\r
 113       ReadBits(16 - m_InBitStream.GetBitPosition());\r
 114       if (!m_InBitStream.ReadUInt32(m_RepDistances[0]))\r
 115         return false;\r
 116       m_RepDistances[0]--;\r
 117       for (unsigned i = 1; i < kNumRepDistances; i++)\r
 118       {\r
 119         UInt32 rep = 0;\r
 120         for (unsigned j = 0; j < 4; j++)\r
 121           rep |= (UInt32)m_InBitStream.DirectReadByte() << (8 * j);\r
 122         m_RepDistances[i] = rep - 1;\r
 123       }\r
 124       return true;\r
 125     }\r
 126     m_AlignIsUsed = (blockType == kBlockTypeAligned);\r
 127     if (m_AlignIsUsed)\r
 128     {\r
 129       for (unsigned i = 0; i < kAlignTableSize; i++)\r
 130         newLevels[i] = (Byte)ReadBits(kNumBitsForAlignLevel);\r
 131       RIF(m_AlignDecoder.SetCodeLengths(newLevels));\r
 132     }\r
 133   }\r
 134 \r
 135   RIF(ReadTable(m_LastMainLevels, newLevels, 256));\r
 136   RIF(ReadTable(m_LastMainLevels + 256, newLevels + 256, m_NumPosLenSlots));\r
 137   for (UInt32 i = 256 + m_NumPosLenSlots; i < kMainTableSize; i++)\r
 138     newLevels[i] = 0;\r
 139   RIF(m_MainDecoder.SetCodeLengths(newLevels));\r
 140 \r
 141   RIF(ReadTable(m_LastLenLevels, newLevels, kNumLenSymbols));\r
 142   return m_LenDecoder.SetCodeLengths(newLevels);\r
 143 }\r
 144 \r
 145 class CDecoderFlusher\r
 146 {\r
 147   CDecoder *m_Decoder;\r
 148 public:\r
 149   bool NeedFlush;\r
 150   CDecoderFlusher(CDecoder *decoder): m_Decoder(decoder), NeedFlush(true) {}\r
 151   ~CDecoderFlusher()\r
 152   {\r
 153     if (NeedFlush)\r
 154       m_Decoder->Flush();\r
 155     m_Decoder->ReleaseStreams();\r
 156   }\r
 157 };\r
 158 \r
 159 \r
 160 void CDecoder::ClearPrevLevels()\r
 161 {\r
 162   unsigned i;\r
 163   for (i = 0; i < kMainTableSize; i++)\r
 164     m_LastMainLevels[i] = 0;\r
 165   for (i = 0; i < kNumLenSymbols; i++)\r
 166     m_LastLenLevels[i] = 0;\r
 167 }\r
 168 \r
 169 \r
 170 HRESULT CDecoder::CodeSpec(UInt32 curSize)\r
 171 {\r
 172   if (_remainLen == kLenIdNeedInit)\r
 173   {\r
 174     _remainLen = 0;\r
 175     m_InBitStream.Init();\r
 176     if (!_keepHistory || !m_IsUncompressedBlock)\r
 177       m_InBitStream.Normalize();\r
 178     if (!_keepHistory)\r
 179     {\r
 180       _skipByte = false;\r
 181       m_UnCompressedBlockSize = 0;\r
 182       ClearPrevLevels();\r
 183       UInt32 i86TranslationSize = 12000000;\r
 184       bool translationMode = true;\r
 185       if (!_wimMode)\r
 186       {\r
 187         translationMode = (ReadBits(1) != 0);\r
 188         if (translationMode)\r
 189         {\r
 190           i86TranslationSize = ReadBits(16) << 16;\r
 191           i86TranslationSize |= ReadBits(16);\r
 192         }\r
 193       }\r
 194       m_x86ConvertOutStreamSpec->Init(translationMode, i86TranslationSize);\r
 195       \r
 196       for (unsigned i = 0 ; i < kNumRepDistances; i++)\r
 197         m_RepDistances[i] = 0;\r
 198     }\r
 199   }\r
 200 \r
 201   while (_remainLen > 0 && curSize > 0)\r
 202   {\r
 203     m_OutWindowStream.PutByte(m_OutWindowStream.GetByte(m_RepDistances[0]));\r
 204     _remainLen--;\r
 205     curSize--;\r
 206   }\r
 207 \r
 208   while (curSize > 0)\r
 209   {\r
 210     if (m_UnCompressedBlockSize == 0)\r
 211       if (!ReadTables())\r
 212         return S_FALSE;\r
 213     UInt32 next = (Int32)MyMin(m_UnCompressedBlockSize, curSize);\r
 214     curSize -= next;\r
 215     m_UnCompressedBlockSize -= next;\r
 216     if (m_IsUncompressedBlock)\r
 217     {\r
 218       while (next > 0)\r
 219       {\r
 220         m_OutWindowStream.PutByte(m_InBitStream.DirectReadByte());\r
 221         next--;\r
 222       }\r
 223     }\r
 224     else while (next > 0)\r
 225     {\r
 226       UInt32 number = m_MainDecoder.DecodeSymbol(&m_InBitStream);\r
 227       if (number < 256)\r
 228       {\r
 229         m_OutWindowStream.PutByte((Byte)number);\r
 230         next--;\r
 231       }\r
 232       else\r
 233       {\r
 234         UInt32 posLenSlot = number - 256;\r
 235         if (posLenSlot >= m_NumPosLenSlots)\r
 236           return S_FALSE;\r
 237         UInt32 posSlot = posLenSlot / kNumLenSlots;\r
 238         UInt32 lenSlot = posLenSlot % kNumLenSlots;\r
 239         UInt32 len = kMatchMinLen + lenSlot;\r
 240         if (lenSlot == kNumLenSlots - 1)\r
 241         {\r
 242           UInt32 lenTemp = m_LenDecoder.DecodeSymbol(&m_InBitStream);\r
 243           if (lenTemp >= kNumLenSymbols)\r
 244             return S_FALSE;\r
 245           len += lenTemp;\r
 246         }\r
 247         \r
 248         if (posSlot < kNumRepDistances)\r
 249         {\r
 250           UInt32 distance = m_RepDistances[posSlot];\r
 251           m_RepDistances[posSlot] = m_RepDistances[0];\r
 252           m_RepDistances[0] = distance;\r
 253         }\r
 254         else\r
 255         {\r
 256           UInt32 distance;\r
 257           unsigned numDirectBits;\r
 258           if (posSlot < kNumPowerPosSlots)\r
 259           {\r
 260             numDirectBits = (unsigned)(posSlot >> 1) - 1;\r
 261             distance = ((2 | (posSlot & 1)) << numDirectBits);\r
 262           }\r
 263           else\r
 264           {\r
 265             numDirectBits = kNumLinearPosSlotBits;\r
 266             distance = ((posSlot - 0x22) << kNumLinearPosSlotBits);\r
 267           }\r
 268 \r
 269           if (m_AlignIsUsed && numDirectBits >= kNumAlignBits)\r
 270           {\r
 271             distance += (m_InBitStream.ReadBits(numDirectBits - kNumAlignBits) << kNumAlignBits);\r
 272             UInt32 alignTemp = m_AlignDecoder.DecodeSymbol(&m_InBitStream);\r
 273             if (alignTemp >= kAlignTableSize)\r
 274               return S_FALSE;\r
 275             distance += alignTemp;\r
 276           }\r
 277           else\r
 278             distance += m_InBitStream.ReadBits(numDirectBits);\r
 279           m_RepDistances[2] = m_RepDistances[1];\r
 280           m_RepDistances[1] = m_RepDistances[0];\r
 281           m_RepDistances[0] = distance - kNumRepDistances;\r
 282         }\r
 283 \r
 284         UInt32 locLen = len;\r
 285         if (locLen > next)\r
 286           locLen = next;\r
 287 \r
 288         if (!m_OutWindowStream.CopyBlock(m_RepDistances[0], locLen))\r
 289           return S_FALSE;\r
 290 \r
 291         len -= locLen;\r
 292         next -= locLen;\r
 293         if (len != 0)\r
 294         {\r
 295           _remainLen = (int)len;\r
 296           return S_OK;\r
 297         }\r
 298       }\r
 299     }\r
 300   }\r
 301   return S_OK;\r
 302 }\r
 303 \r
 304 HRESULT CDecoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream,\r
 305     const UInt64 *, const UInt64 *outSize, ICompressProgressInfo *progress)\r
 306 {\r
 307   if (outSize == NULL)\r
 308     return E_INVALIDARG;\r
 309   UInt64 size = *outSize;\r
 310 \r
 311   RINOK(SetInStream(inStream));\r
 312   m_x86ConvertOutStreamSpec->SetStream(outStream);\r
 313   m_OutWindowStream.SetStream(m_x86ConvertOutStream);\r
 314   RINOK(SetOutStreamSize(outSize));\r
 315 \r
 316   CDecoderFlusher flusher(this);\r
 317 \r
 318   const UInt64 start = m_OutWindowStream.GetProcessedSize();\r
 319   for (;;)\r
 320   {\r
 321     UInt32 curSize = 1 << 18;\r
 322     UInt64 rem = size - (m_OutWindowStream.GetProcessedSize() - start);\r
 323     if (curSize > rem)\r
 324       curSize = (UInt32)rem;\r
 325     if (curSize == 0)\r
 326       break;\r
 327     RINOK(CodeSpec(curSize));\r
 328     if (progress != NULL)\r
 329     {\r
 330       UInt64 inSize = m_InBitStream.GetProcessedSize();\r
 331       UInt64 nowPos64 = m_OutWindowStream.GetProcessedSize() - start;\r
 332       RINOK(progress->SetRatioInfo(&inSize, &nowPos64));\r
 333     }\r
 334   }\r
 335   flusher.NeedFlush = false;\r
 336   return Flush();\r
 337 }\r
 338 \r
 339 HRESULT CDecoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,\r
 340     const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress)\r
 341 {\r
 342   try { return CodeReal(inStream, outStream, inSize, outSize, progress); }\r
 343   catch(const CLzOutWindowException &e) { return e.ErrorCode; }\r
 344   catch(...) { return S_FALSE; }\r
 345 }\r
 346 \r
 347 STDMETHODIMP CDecoder::SetInStream(ISequentialInStream *inStream)\r
 348 {\r
 349   m_InBitStream.SetStream(inStream);\r
 350   return S_OK;\r
 351 }\r
 352 \r
 353 STDMETHODIMP CDecoder::ReleaseInStream()\r
 354 {\r
 355   m_InBitStream.ReleaseStream();\r
 356   return S_OK;\r
 357 }\r
 358 \r
 359 STDMETHODIMP CDecoder::SetOutStreamSize(const UInt64 *outSize)\r
 360 {\r
 361   if (outSize == NULL)\r
 362     return E_FAIL;\r
 363   _remainLen = kLenIdNeedInit;\r
 364   m_OutWindowStream.Init(_keepHistory);\r
 365   return S_OK;\r
 366 }\r
 367 \r
 368 HRESULT CDecoder::SetParams(unsigned numDictBits)\r
 369 {\r
 370   if (numDictBits < kNumDictionaryBitsMin || numDictBits > kNumDictionaryBitsMax)\r
 371     return E_INVALIDARG;\r
 372   UInt32 numPosSlots;\r
 373   if (numDictBits < 20)\r
 374     numPosSlots = 30 + (numDictBits - 15) * 2;\r
 375   else if (numDictBits == 20)\r
 376     numPosSlots = 42;\r
 377   else\r
 378     numPosSlots = 50;\r
 379   m_NumPosLenSlots = numPosSlots * kNumLenSlots;\r
 380   if (!m_OutWindowStream.Create(kDictionarySizeMax))\r
 381     return E_OUTOFMEMORY;\r
 382   if (!m_InBitStream.Create(1 << 16))\r
 383     return E_OUTOFMEMORY;\r
 384   return S_OK;\r
 385 }\r
 386 \r
 387 }}\r