diff options
author | Igor Pavlov <ipavlov@users.sourceforge.net> | 2015-09-22 03:00:00 +0300 |
---|---|---|
committer | Kornel LesiĆski <kornel@geekhood.net> | 2016-05-28 02:16:55 +0300 |
commit | f6444c32568553e0261ca0105083658f12be6284 (patch) | |
tree | 8f4eb80f6accd2a9d0759e2564fd6a2b00836e02 /CPP/7zip/Compress | |
parent | cba375916fb18db8b9101aedf4fa079e019311b3 (diff) |
15.0715.07
Diffstat (limited to 'CPP/7zip/Compress')
-rw-r--r-- | CPP/7zip/Compress/BZip2Decoder.cpp | 4 | ||||
-rw-r--r-- | CPP/7zip/Compress/DeflateDecoder.cpp | 93 | ||||
-rw-r--r-- | CPP/7zip/Compress/DeflateDecoder.h | 4 | ||||
-rw-r--r-- | CPP/7zip/Compress/HuffmanDecoder.h | 247 | ||||
-rw-r--r-- | CPP/7zip/Compress/LzhDecoder.cpp | 10 | ||||
-rw-r--r-- | CPP/7zip/Compress/LzmsDecoder.cpp | 573 | ||||
-rw-r--r-- | CPP/7zip/Compress/LzmsDecoder.h | 271 | ||||
-rw-r--r-- | CPP/7zip/Compress/Lzx.h | 68 | ||||
-rw-r--r-- | CPP/7zip/Compress/Lzx86Converter.cpp | 90 | ||||
-rw-r--r-- | CPP/7zip/Compress/Lzx86Converter.h | 45 | ||||
-rw-r--r-- | CPP/7zip/Compress/LzxDecoder.cpp | 626 | ||||
-rw-r--r-- | CPP/7zip/Compress/LzxDecoder.h | 249 | ||||
-rw-r--r-- | CPP/7zip/Compress/QuantumDecoder.cpp | 225 | ||||
-rw-r--r-- | CPP/7zip/Compress/QuantumDecoder.h | 228 | ||||
-rw-r--r-- | CPP/7zip/Compress/Rar2Decoder.cpp | 74 | ||||
-rw-r--r-- | CPP/7zip/Compress/Rar3Decoder.cpp | 80 | ||||
-rw-r--r-- | CPP/7zip/Compress/Rar5Decoder.cpp | 21 | ||||
-rw-r--r-- | CPP/7zip/Compress/XpressDecoder.cpp | 129 | ||||
-rw-r--r-- | CPP/7zip/Compress/XpressDecoder.h | 13 |
19 files changed, 2107 insertions, 943 deletions
diff --git a/CPP/7zip/Compress/BZip2Decoder.cpp b/CPP/7zip/Compress/BZip2Decoder.cpp index db4d0933..04222e49 100644 --- a/CPP/7zip/Compress/BZip2Decoder.cpp +++ b/CPP/7zip/Compress/BZip2Decoder.cpp @@ -173,7 +173,7 @@ HRESULT CBase::ReadBlock(UInt32 *charCounters, UInt32 blockSizeMax, CBlockProps } for (; i < kMaxAlphaSize; i++) lens[i] = 0; - if (!m_HuffmanDecoders[t].SetCodeLengths(lens)) + if (!m_HuffmanDecoders[t].Build(lens)) return S_FALSE; } while (++t < numTables); @@ -205,7 +205,7 @@ HRESULT CBase::ReadBlock(UInt32 *charCounters, UInt32 blockSizeMax, CBlockProps if (BitDecoder.ExtraBitsWereRead_Fast()) break; - UInt32 nextSym = huffmanDecoder->DecodeSymbol(&BitDecoder); + UInt32 nextSym = huffmanDecoder->Decode(&BitDecoder); if (nextSym < 2) { diff --git a/CPP/7zip/Compress/DeflateDecoder.cpp b/CPP/7zip/Compress/DeflateDecoder.cpp index 5e2d5d3e..5c097f13 100644 --- a/CPP/7zip/Compress/DeflateDecoder.cpp +++ b/CPP/7zip/Compress/DeflateDecoder.cpp @@ -26,39 +26,51 @@ Byte CCoder::ReadAlignedByte() return m_InBitStream.ReadAlignedByte(); } -bool CCoder::DeCodeLevelTable(Byte *values, unsigned numSymbols) +bool CCoder::DecodeLevels(Byte *levels, unsigned numSymbols) { unsigned i = 0; + do { - UInt32 number = m_LevelDecoder.DecodeSymbol(&m_InBitStream); - if (number < kTableDirectLevels) - values[i++] = (Byte)number; - else if (number < kLevelTableSize) + UInt32 sym = m_LevelDecoder.Decode(&m_InBitStream); + if (sym < kTableDirectLevels) + levels[i++] = (Byte)sym; + else { - if (number == kTableLevelRepNumber) + if (sym >= kLevelTableSize) + return false; + + unsigned num; + unsigned numBits; + Byte symbol; + + if (sym == kTableLevelRepNumber) { if (i == 0) return false; - unsigned num = ReadBits(2) + 3; - for (; num > 0 && i < numSymbols; num--, i++) - values[i] = values[i - 1]; + numBits = 2; + num = 0; + symbol = levels[i - 1]; } else { - unsigned num; - if (number == kTableLevel0Number) - num = ReadBits(3) + 3; - else - num = ReadBits(7) + 11; - for (; num > 0 && i < numSymbols; num--) - values[i++] = 0; + sym -= kTableLevel0Number; + sym <<= 2; + numBits = 3 + (unsigned)sym; + num = ((unsigned)sym << 1); + symbol = 0; } + + num += i + 3 + ReadBits(numBits); + if (num > numSymbols) + return false; + do + levels[i++] = symbol; + while (i < num); } - else - return false; } while (i < numSymbols); + return true; } @@ -116,10 +128,10 @@ bool CCoder::ReadTables(void) if (m_InBitStream.ExtraBitsWereRead()) return false; - RIF(m_LevelDecoder.SetCodeLengths(levelLevels)); + RIF(m_LevelDecoder.Build(levelLevels)); Byte tmpLevels[kFixedMainTableSize + kFixedDistTableSize]; - if (!DeCodeLevelTable(tmpLevels, numLitLenLevels + _numDistLevels)) + if (!DecodeLevels(tmpLevels, numLitLenLevels + _numDistLevels)) return false; if (m_InBitStream.ExtraBitsWereRead()) @@ -129,8 +141,8 @@ bool CCoder::ReadTables(void) memcpy(levels.litLenLevels, tmpLevels, numLitLenLevels); memcpy(levels.distLevels, tmpLevels + numLitLenLevels, _numDistLevels); } - RIF(m_MainDecoder.SetCodeLengths(levels.litLenLevels)); - return m_DistDecoder.SetCodeLengths(levels.distLevels); + RIF(m_MainDecoder.Build(levels.litLenLevels)); + return m_DistDecoder.Build(levels.distLevels); } HRESULT CCoder::CodeSpec(UInt32 curSize, bool finishInputStream) @@ -161,6 +173,7 @@ HRESULT CCoder::CodeSpec(UInt32 curSize, bool finishInputStream) { if (m_InBitStream.ExtraBitsWereRead()) return S_FALSE; + if (_needReadTable) { if (m_FinalBlock) @@ -194,43 +207,44 @@ HRESULT CCoder::CodeSpec(UInt32 curSize, bool finishInputStream) if (m_InBitStream.ExtraBitsWereRead_Fast()) return S_FALSE; - UInt32 number = m_MainDecoder.DecodeSymbol(&m_InBitStream); - if (number < 0x100) + UInt32 sym = m_MainDecoder.Decode(&m_InBitStream); + + if (sym < 0x100) { - m_OutWindowStream.PutByte((Byte)number); + m_OutWindowStream.PutByte((Byte)sym); curSize--; continue; } - else if (number == kSymbolEndOfBlock) + else if (sym == kSymbolEndOfBlock) { _needReadTable = true; break; } - else if (number < kMainTableSize) + else if (sym < kMainTableSize) { - number -= kSymbolMatch; + sym -= kSymbolMatch; UInt32 len; { unsigned numBits; if (_deflate64Mode) { - len = kLenStart64[number]; - numBits = kLenDirectBits64[number]; + len = kLenStart64[sym]; + numBits = kLenDirectBits64[sym]; } else { - len = kLenStart32[number]; - numBits = kLenDirectBits32[number]; + len = kLenStart32[sym]; + numBits = kLenDirectBits32[sym]; } len += kMatchMinLen + m_InBitStream.ReadBits(numBits); } UInt32 locLen = len; if (locLen > curSize) locLen = (UInt32)curSize; - number = m_DistDecoder.DecodeSymbol(&m_InBitStream); - if (number >= _numDistLevels) + sym = m_DistDecoder.Decode(&m_InBitStream); + if (sym >= _numDistLevels) return S_FALSE; - UInt32 distance = kDistStart[number] + m_InBitStream.ReadBits(kDistDirectBits[number]); + UInt32 distance = kDistStart[sym] + m_InBitStream.ReadBits(kDistDirectBits[sym]); if (!m_OutWindowStream.CopyBlock(distance, locLen)) return S_FALSE; curSize -= locLen; @@ -248,7 +262,7 @@ HRESULT CCoder::CodeSpec(UInt32 curSize, bool finishInputStream) if (finishInputStream && curSize == 0) { - if (m_MainDecoder.DecodeSymbol(&m_InBitStream) != kSymbolEndOfBlock) + if (m_MainDecoder.Decode(&m_InBitStream) != kSymbolEndOfBlock) return S_FALSE; _needReadTable = true; } @@ -260,6 +274,7 @@ HRESULT CCoder::CodeSpec(UInt32 curSize, bool finishInputStream) return S_OK; } + #ifdef _NO_EXCEPTIONS #define DEFLATE_TRY_BEGIN @@ -275,6 +290,7 @@ HRESULT CCoder::CodeSpec(UInt32 curSize, bool finishInputStream) #endif + HRESULT CCoder::CodeReal(ISequentialOutStream *outStream, const UInt64 *outSize, ICompressProgressInfo *progress) { @@ -285,6 +301,7 @@ HRESULT CCoder::CodeReal(ISequentialOutStream *outStream, const UInt64 inStart = _needInitInStream ? 0 : m_InBitStream.GetProcessedSize(); const UInt64 start = m_OutWindowStream.GetProcessedSize(); + for (;;) { UInt32 curSize = 1 << 18; @@ -311,12 +328,14 @@ HRESULT CCoder::CodeReal(ISequentialOutStream *outStream, RINOK(progress->SetRatioInfo(&inSize, &nowPos64)); } } + if (_remainLen == kLenIdFinished && ZlibMode) { m_InBitStream.AlignToByte(); for (unsigned i = 0; i < 4; i++) ZlibFooter[i] = ReadAlignedByte(); } + flusher.NeedFlush = false; res = Flush(); if (res == S_OK && _remainLen != kLenIdNeedInit && InputEofError()) @@ -337,7 +356,7 @@ HRESULT CCoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStr STDMETHODIMP CCoder::GetInStreamProcessedSize(UInt64 *value) { - if (value == NULL) + if (!value) return E_INVALIDARG; *value = m_InBitStream.GetProcessedSize(); return S_OK; diff --git a/CPP/7zip/Compress/DeflateDecoder.h b/CPP/7zip/Compress/DeflateDecoder.h index 856a5771..0b29737f 100644 --- a/CPP/7zip/Compress/DeflateDecoder.h +++ b/CPP/7zip/Compress/DeflateDecoder.h @@ -36,7 +36,7 @@ class CCoder: NBitl::CDecoder<CInBuffer> m_InBitStream; NCompress::NHuffman::CDecoder<kNumHuffmanBits, kFixedMainTableSize> m_MainDecoder; NCompress::NHuffman::CDecoder<kNumHuffmanBits, kFixedDistTableSize> m_DistDecoder; - NCompress::NHuffman::CDecoder<kNumHuffmanBits, kLevelTableSize> m_LevelDecoder; + NCompress::NHuffman::CDecoder7b<kLevelTableSize> m_LevelDecoder; UInt32 m_StoredBlockSize; @@ -56,7 +56,7 @@ class CCoder: UInt32 ReadBits(unsigned numBits); - bool DeCodeLevelTable(Byte *values, unsigned numSymbols); + bool DecodeLevels(Byte *levels, unsigned numSymbols); bool ReadTables(); HRESULT Flush() { return m_OutWindowStream.Flush(); } diff --git a/CPP/7zip/Compress/HuffmanDecoder.h b/CPP/7zip/Compress/HuffmanDecoder.h index 65e0f93c..04364c14 100644 --- a/CPP/7zip/Compress/HuffmanDecoder.h +++ b/CPP/7zip/Compress/HuffmanDecoder.h @@ -8,42 +8,89 @@ namespace NCompress { namespace NHuffman { -const unsigned kNumTableBits = 9; - -template <unsigned kNumBitsMax, UInt32 m_NumSymbols> +template <unsigned kNumBitsMax, UInt32 m_NumSymbols, unsigned kNumTableBits = 9> class CDecoder { - UInt32 m_Limits[kNumBitsMax + 1]; // m_Limits[i] = value limit for symbols with length = i - UInt32 m_Positions[kNumBitsMax + 1]; // m_Positions[i] = index in m_Symbols[] of first symbol with length = i - UInt32 m_Symbols[m_NumSymbols]; - Byte m_Lengths[1 << kNumTableBits]; // Table of length for short codes - + UInt32 _limits[kNumBitsMax + 2]; + UInt32 _poses[kNumBitsMax + 1]; + UInt16 _lens[1 << kNumTableBits]; + UInt16 _symbols[m_NumSymbols]; public: - bool SetCodeLengths(const Byte *lens) + bool Build(const Byte *lens) throw() { UInt32 lenCounts[kNumBitsMax + 1]; - UInt32 tmpPositions[kNumBitsMax + 1]; + UInt32 tmpPoses[kNumBitsMax + 1]; unsigned i; - for (i = 1; i <= kNumBitsMax; i++) + for (i = 0; i <= kNumBitsMax; i++) lenCounts[i] = 0; - UInt32 symbol; + UInt32 sym; + + for (sym = 0; sym < m_NumSymbols; sym++) + lenCounts[lens[sym]]++; + + lenCounts[0] = 0; + _poses[0] = 0; + _limits[0] = 0; + UInt32 startPos = 0; + const UInt32 kMaxValue = (UInt32)1 << kNumBitsMax; - for (symbol = 0; symbol < m_NumSymbols; symbol++) + for (i = 1; i <= kNumBitsMax; i++) { - unsigned len = lens[symbol]; - if (len > kNumBitsMax) + startPos += lenCounts[i] << (kNumBitsMax - i); + if (startPos > kMaxValue) return false; - lenCounts[len]++; - m_Symbols[symbol] = 0xFFFFFFFF; + _limits[i] = startPos; + _poses[i] = _poses[i - 1] + lenCounts[i - 1]; + tmpPoses[i] = _poses[i]; + } + + _limits[kNumBitsMax + 1] = kMaxValue; + + for (sym = 0; sym < m_NumSymbols; sym++) + { + unsigned len = lens[sym]; + if (len == 0) + continue; + + unsigned offset = tmpPoses[len]; + _symbols[offset] = (UInt16)sym; + tmpPoses[len] = offset + 1; + + if (len <= kNumTableBits) + { + offset -= _poses[len]; + UInt32 num = (UInt32)1 << (kNumTableBits - len); + UInt16 val = (UInt16)((sym << 4) | len); + UInt16 *dest = _lens + (_limits[len - 1] >> (kNumBitsMax - kNumTableBits)) + (offset << (kNumTableBits - len)); + for (UInt32 k = 0; k < num; k++) + dest[k] = val; + } } + return true; + } + + bool BuildFull(const Byte *lens, UInt32 numSymbols = m_NumSymbols) throw() + { + UInt32 lenCounts[kNumBitsMax + 1]; + UInt32 tmpPoses[kNumBitsMax + 1]; + + unsigned i; + for (i = 0; i <= kNumBitsMax; i++) + lenCounts[i] = 0; + + UInt32 sym; + + for (sym = 0; sym < numSymbols; sym++) + lenCounts[lens[sym]]++; + lenCounts[0] = 0; - m_Positions[0] = m_Limits[0] = 0; + _poses[0] = 0; + _limits[0] = 0; UInt32 startPos = 0; - UInt32 index = 0; const UInt32 kMaxValue = (UInt32)1 << kNumBitsMax; for (i = 1; i <= kNumBitsMax; i++) @@ -51,44 +98,160 @@ public: startPos += lenCounts[i] << (kNumBitsMax - i); if (startPos > kMaxValue) return false; - m_Limits[i] = (i == kNumBitsMax) ? kMaxValue : startPos; - m_Positions[i] = m_Positions[i - 1] + lenCounts[i - 1]; - tmpPositions[i] = m_Positions[i]; - if (i <= kNumTableBits) + _limits[i] = startPos; + _poses[i] = _poses[i - 1] + lenCounts[i - 1]; + tmpPoses[i] = _poses[i]; + } + + _limits[kNumBitsMax + 1] = kMaxValue; + + for (sym = 0; sym < numSymbols; sym++) + { + unsigned len = lens[sym]; + if (len == 0) + continue; + + unsigned offset = tmpPoses[len]; + _symbols[offset] = (UInt16)sym; + tmpPoses[len] = offset + 1; + + if (len <= kNumTableBits) { - UInt32 limit = (m_Limits[i] >> (kNumBitsMax - kNumTableBits)); - for (; index < limit; index++) - m_Lengths[index] = (Byte)i; + offset -= _poses[len]; + UInt32 num = (UInt32)1 << (kNumTableBits - len); + UInt16 val = (UInt16)((sym << 4) | len); + UInt16 *dest = _lens + (_limits[len - 1] >> (kNumBitsMax - kNumTableBits)) + (offset << (kNumTableBits - len)); + for (UInt32 k = 0; k < num; k++) + dest[k] = val; } } - for (symbol = 0; symbol < m_NumSymbols; symbol++) + return startPos == kMaxValue; + } + + template <class TBitDecoder> + UInt32 Decode(TBitDecoder *bitStream) const throw() + { + UInt32 val = bitStream->GetValue(kNumBitsMax); + + if (val < _limits[kNumTableBits]) { - unsigned len = lens[symbol]; - if (len != 0) - m_Symbols[tmpPositions[len]++] = symbol; + UInt32 pair = _lens[val >> (kNumBitsMax - kNumTableBits)]; + bitStream->MovePos((unsigned)(pair & 0xF)); + return pair >> 4; } + + unsigned numBits; + for (numBits = kNumTableBits + 1; val >= _limits[numBits]; numBits++); - return true; + if (numBits > kNumBitsMax) + return 0xFFFFFFFF; + + bitStream->MovePos(numBits); + UInt32 index = _poses[numBits] + ((val - _limits[numBits - 1]) >> (kNumBitsMax - numBits)); + return _symbols[index]; } template <class TBitDecoder> - UInt32 DecodeSymbol(TBitDecoder *bitStream) + UInt32 DecodeFull(TBitDecoder *bitStream) const throw() { - unsigned numBits; UInt32 val = bitStream->GetValue(kNumBitsMax); - if (val < m_Limits[kNumTableBits]) - numBits = m_Lengths[val >> (kNumBitsMax - kNumTableBits)]; - else - for (numBits = kNumTableBits + 1; val >= m_Limits[numBits]; numBits++); + if (val < _limits[kNumTableBits]) + { + UInt32 pair = _lens[val >> (kNumBitsMax - kNumTableBits)]; + bitStream->MovePos((unsigned)(pair & 0xF)); + return pair >> 4; + } + + unsigned numBits; + for (numBits = kNumTableBits + 1; val >= _limits[numBits]; numBits++); bitStream->MovePos(numBits); - UInt32 index = m_Positions[numBits] + ((val - m_Limits[numBits - 1]) >> (kNumBitsMax - numBits)); - if (index >= m_NumSymbols) - // throw CDecoderException(); // test it - return 0xFFFFFFFF; - return m_Symbols[index]; + UInt32 index = _poses[numBits] + ((val - _limits[numBits - 1]) >> (kNumBitsMax - numBits)); + return _symbols[index]; + } +}; + + + +template <UInt32 m_NumSymbols> +class CDecoder7b +{ + Byte _lens[1 << 7]; +public: + + bool Build(const Byte *lens) throw() + { + const unsigned kNumBitsMax = 7; + + UInt32 lenCounts[kNumBitsMax + 1]; + UInt32 tmpPoses[kNumBitsMax + 1]; + UInt32 _poses[kNumBitsMax + 1]; + UInt32 _limits[kNumBitsMax + 1]; + + unsigned i; + for (i = 0; i <= kNumBitsMax; i++) + lenCounts[i] = 0; + + UInt32 sym; + + for (sym = 0; sym < m_NumSymbols; sym++) + lenCounts[lens[sym]]++; + + lenCounts[0] = 0; + _poses[0] = 0; + _limits[0] = 0; + UInt32 startPos = 0; + const UInt32 kMaxValue = (UInt32)1 << kNumBitsMax; + + for (i = 1; i <= kNumBitsMax; i++) + { + startPos += lenCounts[i] << (kNumBitsMax - i); + if (startPos > kMaxValue) + return false; + _limits[i] = startPos; + _poses[i] = _poses[i - 1] + lenCounts[i - 1]; + tmpPoses[i] = _poses[i]; + } + + for (sym = 0; sym < m_NumSymbols; sym++) + { + unsigned len = lens[sym]; + if (len == 0) + continue; + + unsigned offset = tmpPoses[len]; + tmpPoses[len] = offset + 1; + + { + offset -= _poses[len]; + UInt32 num = (UInt32)1 << (kNumBitsMax - len); + Byte val = (Byte)((sym << 3) | len); + Byte *dest = _lens + (_limits[len - 1]) + (offset << (kNumBitsMax - len)); + for (UInt32 k = 0; k < num; k++) + dest[k] = val; + } + } + + { + UInt32 limit = _limits[kNumBitsMax]; + UInt32 num = ((UInt32)1 << kNumBitsMax) - limit; + Byte *dest = _lens + limit; + for (UInt32 k = 0; k < num; k++) + dest[k] = (Byte)(0x1F << 3); + } + + return true; + } + + template <class TBitDecoder> + UInt32 Decode(TBitDecoder *bitStream) const throw() + { + UInt32 val = bitStream->GetValue(7); + UInt32 pair = _lens[val]; + bitStream->MovePos((unsigned)(pair & 0x7)); + return pair >> 3; } }; diff --git a/CPP/7zip/Compress/LzhDecoder.cpp b/CPP/7zip/Compress/LzhDecoder.cpp index bf4a0b68..b0aa7536 100644 --- a/CPP/7zip/Compress/LzhDecoder.cpp +++ b/CPP/7zip/Compress/LzhDecoder.cpp @@ -71,7 +71,7 @@ bool CCoder::ReadTP(unsigned num, unsigned numBits, int spec) if (!CheckCodeLens(lens, NPT)) return false; - return _decoderT.SetCodeLengths(lens); + return _decoderT.Build(lens); } } @@ -101,7 +101,7 @@ bool CCoder::ReadC() { UInt32 c = (unsigned)_symbolT; if (_symbolT < 0) - c = _decoderT.DecodeSymbol(&_inBitStream); + c = _decoderT.Decode(&_inBitStream); if (c <= 2) { @@ -129,7 +129,7 @@ bool CCoder::ReadC() if (!CheckCodeLens(lens, NC)) return false; - return _decoderC.SetCodeLengths(lens); + return _decoderC.Build(lens); } } @@ -169,7 +169,7 @@ HRESULT CCoder::CodeReal(UInt64 rem, ICompressProgressInfo *progress) UInt32 number = (unsigned)_symbolC; if (_symbolC < 0) - number = _decoderC.DecodeSymbol(&_inBitStream); + number = _decoderC.Decode(&_inBitStream); if (number < 256) { @@ -182,7 +182,7 @@ HRESULT CCoder::CodeReal(UInt64 rem, ICompressProgressInfo *progress) UInt32 dist = (unsigned)_symbolT; if (_symbolT < 0) - dist = _decoderT.DecodeSymbol(&_inBitStream); + dist = _decoderT.Decode(&_inBitStream); if (dist > 1) { diff --git a/CPP/7zip/Compress/LzmsDecoder.cpp b/CPP/7zip/Compress/LzmsDecoder.cpp new file mode 100644 index 00000000..1f83b63d --- /dev/null +++ b/CPP/7zip/Compress/LzmsDecoder.cpp @@ -0,0 +1,573 @@ +// LzmsDecoder.cpp +// The code is based on LZMS description from wimlib code + +#include "StdAfx.h" + +#include "../../../C/Alloc.h" + +#include "LzmsDecoder.h" + +namespace NCompress { +namespace NLzms { + +static UInt32 g_PosBases[k_NumPosSyms /* + 1 */]; + +static Byte g_PosDirectBits[k_NumPosSyms]; + +static const Byte k_PosRuns[31] = +{ + 8, 0, 9, 7, 10, 15, 15, 20, 20, 30, 33, 40, 42, 45, 60, 73, + 80, 85, 95, 105, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 +}; + +static UInt32 g_LenBases[k_NumLenSyms]; + +static const Byte k_LenDirectBits[k_NumLenSyms] = +{ + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, + 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 6, + 7, 8, 9, 10, 16, 30, +}; + +static struct CInit +{ + CInit() + { + { + unsigned sum = 0; + for (unsigned i = 0; i < sizeof(k_PosRuns); i++) + { + unsigned t = k_PosRuns[i]; + for (unsigned y = 0; y < t; y++) + g_PosDirectBits[sum + y] = (Byte)i; + sum += t; + } + } + { + UInt32 sum = 1; + for (unsigned i = 0; i < k_NumPosSyms; i++) + { + g_PosBases[i] = sum; + sum += (UInt32)1 << g_PosDirectBits[i]; + } + // g_PosBases[k_NumPosSyms] = sum; + } + { + UInt32 sum = 1; + for (unsigned i = 0; i < k_NumLenSyms; i++) + { + g_LenBases[i] = sum; + sum += (UInt32)1 << k_LenDirectBits[i]; + } + } + } +} g_Init; + +static unsigned GetNumPosSlots(size_t size) +{ + if (size < 2) + return 0; + + size--; + + if (size >= g_PosBases[k_NumPosSyms - 1]) + return k_NumPosSyms; + unsigned left = 0; + unsigned right = k_NumPosSyms; + for (;;) + { + unsigned m = (left + right) / 2; + if (left == m) + return m + 1; + if (size >= g_PosBases[m]) + left = m; + else + right = m; + } +} + + +static const Int32 k_x86_WindowSize = 65535; +static const Int32 k_x86_TransOffset = 1023; + +static const size_t k_x86_HistorySize = (1 << 16); + +static void x86_Filter(Byte *data, UInt32 size, Int32 *history) +{ + if (size <= 17) + return; + + Byte isCode[256]; + memset(isCode, 0, 256); + isCode[0x48] = 1; + isCode[0x4C] = 1; + isCode[0xE8] = 1; + isCode[0xE9] = 1; + isCode[0xF0] = 1; + isCode[0xFF] = 1; + + { + for (size_t i = 0; i < k_x86_HistorySize; i++) + history[i] = -(Int32)k_x86_WindowSize - 1; + } + + size -= 16; + const unsigned kSave = 6; + const Byte savedByte = data[size + kSave]; + data[size + kSave] = 0xE8; + Int32 last_x86_pos = -k_x86_TransOffset - 1; + + // first byte is ignored + Int32 i = 0; + + for (;;) + { + const Byte *p = data + (UInt32)i; + + for (;;) + { + if (isCode[*(++p)]) break; + if (isCode[*(++p)]) break; + } + + i = (Int32)(p - data); + if ((UInt32)i >= size) + break; + + UInt32 codeLen; + + Int32 maxTransOffset = k_x86_TransOffset; + + Byte b = p[0]; + + if (b == 0x48) + { + if (p[1] == 0x8B) + { + if ((p[2] & 0xF7) != 0x5) + continue; + // MOV RAX / RCX, [RIP + disp32] + } + else if (p[1] == 0x8D) // LEA + { + if ((p[2] & 0x7) != 0x5) + continue; + // LEA R**, [] + } + else + continue; + codeLen = 3; + } + else if (b == 0x4C) + { + if (p[1] != 0x8D || (p[2] & 0x7) != 0x5) + continue; + // LEA R*, [] + codeLen = 3; + } + else if (b == 0xE8) + { + // CALL + codeLen = 1; + maxTransOffset /= 2; + } + else if (b == 0xE9) + { + // JUMP + i += 4; + continue; + } + else if (b == 0xF0) + { + if (p[1] != 0x83 || p[2] != 0x05) + continue; + // LOCK ADD [RIP + disp32], imm8 + // LOCK ADD [disp32], imm8 + codeLen = 3; + } + else + // if (b == 0xFF) + { + if (p[1] != 0x15) + continue; + // CALL [RIP + disp32]; + // CALL [disp32]; + codeLen = 2; + } + + Int32 *target; + { + const Byte *p2 = p + codeLen; + UInt32 n = GetUi32(p2); + if (i - last_x86_pos <= maxTransOffset) + { + n -= i; + SetUi32(p2, n); + } + target = history + (((UInt32)i + n) & 0xFFFF); + } + + i += codeLen + sizeof(UInt32) - 1; + + if (i - *target <= k_x86_WindowSize) + last_x86_pos = i; + *target = i; + } + + data[size + kSave] = savedByte; +} + + + +static const int kLenIdNeedInit = -2; + +CDecoder::CDecoder(): + _x86_history(NULL) +{ +} + +CDecoder::~CDecoder() +{ + ::MidFree(_x86_history); +} + +#define RIF(x) { if (!(x)) return false; } + +#define LIMIT_CHECK if (_bs._buf < _rc.cur) return S_FALSE; +// #define LIMIT_CHECK + +#define READ_BITS_CHECK(numDirectBits) \ + if (_bs._buf < _rc.cur) return S_FALSE; \ + if ((size_t)(_bs._buf - _rc.cur) < (numDirectBits >> 3)) return S_FALSE; + + +#define HUFF_DEC(sym, pp) \ + sym = pp.DecodeFull(&_bs); \ + pp.Freqs[sym]++; \ + if (--pp.RebuildRem == 0) pp.Rebuild(); + + +HRESULT CDecoder::CodeReal(const Byte *in, size_t inSize, Byte *_win, size_t outSize) +{ + // size_t inSizeT = (size_t)(inSize); + // Byte *_win; + // size_t _pos; + _pos = 0; + + CBitDecoder _bs; + CRangeDecoder _rc; + + if (inSize < 8 || (inSize & 1) != 0) + return S_FALSE; + _rc.Init(in, inSize); + if (_rc.code >= _rc.range) + return S_FALSE; + _bs.Init(in, inSize); + + { + { + unsigned i; + for (i = 0 ; i < k_NumReps + 1; i++) + _reps[i] = i + 1; + + for (i = 0 ; i < k_NumReps + 1; i++) + _deltaReps[i] = i + 1; + + mainState = 0; + matchState = 0; + + { for (size_t i = 0; i < k_NumMainProbs; i++) mainProbs[i].Init(); } + { for (size_t i = 0; i < k_NumMatchProbs; i++) matchProbs[i].Init(); } + + { + for (size_t k = 0; k < k_NumReps; k++) + { + lzRepStates[k] = 0; + for (size_t i = 0; i < k_NumRepProbs; i++) + lzRepProbs[k][i].Init(); + } + } + { + for (size_t k = 0; k < k_NumReps; k++) + { + deltaRepStates[k] = 0; + for (size_t i = 0; i < k_NumRepProbs; i++) + deltaRepProbs[k][i].Init(); + } + } + + m_LitDecoder.Init(); + m_LenDecoder.Init(); + m_PowerDecoder.Init(); + unsigned numPosSyms = GetNumPosSlots(outSize); + if (numPosSyms < 2) + numPosSyms = 2; + m_PosDecoder.Init(numPosSyms); + m_DeltaDecoder.Init(numPosSyms); + } + } + + { + unsigned prevType = 0; + + while (_pos < outSize) + { + if (_rc.Decode(&mainState, k_NumMainProbs, mainProbs) == 0) + { + UInt32 number; + HUFF_DEC(number, m_LitDecoder); + LIMIT_CHECK + _win[_pos++] = (Byte)number; + prevType = 0; + } + else if (_rc.Decode(&matchState, k_NumMatchProbs, matchProbs) == 0) + { + UInt32 distance; + + if (_rc.Decode(&lzRepStates[0], k_NumRepProbs, lzRepProbs[0]) == 0) + { + UInt32 number; + HUFF_DEC(number, m_PosDecoder); + LIMIT_CHECK + + unsigned numDirectBits = g_PosDirectBits[number]; + distance = g_PosBases[number]; + READ_BITS_CHECK(numDirectBits); + distance += _bs.ReadBits32(numDirectBits); + // LIMIT_CHECK + _reps[3] = _reps[2]; + _reps[2] = _reps[1]; + _reps[1] = _reps[0]; + _reps[0] = distance; + } + else + { + if (_rc.Decode(&lzRepStates[1], k_NumRepProbs, lzRepProbs[1]) == 0) + { + if (prevType != 1) + distance = _reps[0]; + else + { + distance = _reps[1]; + _reps[1] = _reps[0]; + _reps[0] = distance; + } + } + else if (_rc.Decode(&lzRepStates[2], k_NumRepProbs, lzRepProbs[2]) == 0) + { + if (prevType != 1) + { + distance = _reps[1]; + _reps[1] = _reps[0]; + _reps[0] = distance; + } + else + { + distance = _reps[2]; + _reps[2] = _reps[1]; + _reps[1] = _reps[0]; + _reps[0] = distance; + } + } + else + { + if (prevType != 1) + { + distance = _reps[2]; + _reps[2] = _reps[1]; + _reps[1] = _reps[0]; + _reps[0] = distance; + } + else + { + distance = _reps[3]; + _reps[3] = _reps[2]; + _reps[2] = _reps[1]; + _reps[1] = _reps[0]; + _reps[0] = distance; + } + } + } + + UInt32 lenSlot; + HUFF_DEC(lenSlot, m_LenDecoder); + LIMIT_CHECK + + UInt32 len = g_LenBases[lenSlot]; + { + unsigned numDirectBits = k_LenDirectBits[lenSlot]; + READ_BITS_CHECK(numDirectBits); + len += _bs.ReadBits32(numDirectBits); + } + // LIMIT_CHECK + + if (len > outSize - _pos) + return S_FALSE; + + if (distance > _pos) + return S_FALSE; + + Byte *dest = _win + _pos; + const Byte *src = dest - distance; + _pos += len; + do + *dest++ = *src++; + while (--len); + + prevType = 1; + } + else + { + UInt64 distance; + + UInt32 power; + UInt32 distance32; + + if (_rc.Decode(&deltaRepStates[0], k_NumRepProbs, deltaRepProbs[0]) == 0) + { + HUFF_DEC(power, m_PowerDecoder); + LIMIT_CHECK + + UInt32 number; + HUFF_DEC(number, m_DeltaDecoder); + LIMIT_CHECK + + unsigned numDirectBits = g_PosDirectBits[number]; + distance32 = g_PosBases[number]; + READ_BITS_CHECK(numDirectBits); + distance32 += _bs.ReadBits32(numDirectBits); + // LIMIT_CHECK + + distance = ((UInt64)power << 32) | distance32; + + _deltaReps[3] = _deltaReps[2]; + _deltaReps[2] = _deltaReps[1]; + _deltaReps[1] = _deltaReps[0]; + _deltaReps[0] = distance; + } + else + { + if (_rc.Decode(&deltaRepStates[1], k_NumRepProbs, deltaRepProbs[1]) == 0) + { + if (prevType != 2) + distance = _deltaReps[0]; + else + { + distance = _deltaReps[1]; + _deltaReps[1] = _deltaReps[0]; + _deltaReps[0] = distance; + } + } + else if (_rc.Decode(&deltaRepStates[2], k_NumRepProbs, deltaRepProbs[2]) == 0) + { + if (prevType != 2) + { + distance = _deltaReps[1]; + _deltaReps[1] = _deltaReps[0]; + _deltaReps[0] = distance; + } + else + { + distance = _deltaReps[2]; + _deltaReps[2] = _deltaReps[1]; + _deltaReps[1] = _deltaReps[0]; + _deltaReps[0] = distance; + } + } + else + { + if (prevType != 2) + { + distance = _deltaReps[2]; + _deltaReps[2] = _deltaReps[1]; + _deltaReps[1] = _deltaReps[0]; + _deltaReps[0] = distance; + } + else + { + distance = _deltaReps[3]; + _deltaReps[3] = _deltaReps[2]; + _deltaReps[2] = _deltaReps[1]; + _deltaReps[1] = _deltaReps[0]; + _deltaReps[0] = distance; + } + } + distance32 = (UInt32)_deltaReps[0] & 0xFFFFFFFF; + power = (UInt32)(_deltaReps[0] >> 32); + } + + UInt32 dist = (distance32 << power); + + UInt32 lenSlot; + HUFF_DEC(lenSlot, m_LenDecoder); + LIMIT_CHECK + + UInt32 len = g_LenBases[lenSlot]; + { + unsigned numDirectBits = k_LenDirectBits[lenSlot]; + READ_BITS_CHECK(numDirectBits); + len += _bs.ReadBits32(numDirectBits); + } + // LIMIT_CHECK + + if (len > outSize - _pos) + return S_FALSE; + + if (dist > _pos) + return S_FALSE; + size_t span = (size_t)1 << power; + Byte *dest = _win + _pos - span; + const Byte *src = dest - dist; + _pos += len; + do + { + *(dest + span) = (Byte)(*(dest) + *(src + span) - *(src)); + src++; + dest++; + } + while (--len); + + prevType = 2; + } + } + } + + _rc.Normalize(); + if (_rc.code != 0) + return S_FALSE; + if (_rc.cur > _bs._buf || + _rc.cur == _bs._buf && _bs._bitPos != 0) + return S_FALSE; + + /* + int delta = (int)(_bs._buf - _rc.cur); + if (_bs._bitPos != 0) + delta--; + if ((delta & 1)) + delta--; + printf("%d ", delta); + */ + + return S_OK; +} + +HRESULT CDecoder::Code(const Byte *in, size_t inSize, Byte *out, size_t outSize) +{ + if (!_x86_history) + { + _x86_history = (Int32 *)::MidAlloc(sizeof(Int32) * k_x86_HistorySize); + if (!_x86_history) + return E_OUTOFMEMORY; + } + HRESULT res; + // try + { + res = CodeReal(in, inSize, out, outSize); + } + // catch (...) { res = S_FALSE; } + x86_Filter(out, (UInt32)_pos, _x86_history); + return res; +} + +}} diff --git a/CPP/7zip/Compress/LzmsDecoder.h b/CPP/7zip/Compress/LzmsDecoder.h new file mode 100644 index 00000000..510d3389 --- /dev/null +++ b/CPP/7zip/Compress/LzmsDecoder.h @@ -0,0 +1,271 @@ +// LzmsDecoder.h +// The code is based on LZMS description from wimlib code + +#ifndef __LZMS_DECODER_H +#define __LZMS_DECODER_H + +// #define SHOW_DEBUG_INFO + +#ifdef SHOW_DEBUG_INFO +#include <stdio.h> +#define PRF(x) x +#else +// #define PRF(x) +#endif + +#include "../../../C/CpuArch.h" +#include "../../../C/HuffEnc.h" + +#include "../../Common/MyBuffer.h" +#include "../../Common/MyCom.h" + +#include "../ICoder.h" + +#include "HuffmanDecoder.h" + +namespace NCompress { +namespace NLzms { + +class CBitDecoder +{ +public: + const Byte *_buf; + unsigned _bitPos; + + void Init(const Byte *buf, size_t size) throw() + { + _buf = buf + size; + _bitPos = 0; + } + + UInt32 GetValue(unsigned numBits) const + { + UInt32 v = ((UInt32)_buf[-1] << 16) | ((UInt32)_buf[-2] << 8) | (UInt32)_buf[-3]; + v >>= (24 - numBits - _bitPos); + return v & ((1 << numBits) - 1); + } + + void MovePos(unsigned numBits) + { + _bitPos += numBits; + _buf -= (_bitPos >> 3); + _bitPos &= 7; + } + + UInt32 ReadBits32(unsigned numBits) + { + UInt32 mask = (((UInt32)1 << numBits) - 1); + numBits += _bitPos; + const Byte *buf = _buf; + UInt32 v = GetUi32(buf - 4); + if (numBits > 32) + { + v <<= (numBits - 32); + v |= (UInt32)buf[-5] >> (40 - numBits); + } + else + v >>= (32 - numBits); + _buf = buf - (numBits >> 3); + _bitPos = numBits & 7; + return v & mask; + } +}; + + +const unsigned k_NumLitSyms = 256; +const unsigned k_NumLenSyms = 54; +const unsigned k_NumPosSyms = 799; +const unsigned k_NumPowerSyms = 8; + +const unsigned k_NumProbBits = 6; +const unsigned k_ProbLimit = 1 << k_NumProbBits; +const unsigned k_InitialProb = 48; +const UInt32 k_InitialHist = 0x55555555; + +const unsigned k_NumReps = 3; + +const unsigned k_NumMainProbs = 16; +const unsigned k_NumMatchProbs = 32; +const unsigned k_NumRepProbs = 64; + +const unsigned k_NumHuffmanBits = 15; + +template <UInt32 m_NumSyms, UInt32 m_RebuildFreq, unsigned numTableBits> +class CHuffDecoder: public NCompress::NHuffman::CDecoder<k_NumHuffmanBits, m_NumSyms, numTableBits> +{ +public: + UInt32 RebuildRem; + UInt32 NumSyms; + UInt32 Freqs[m_NumSyms]; + + void Generate() throw() + { + UInt32 vals[m_NumSyms]; + Byte levels[m_NumSyms]; + + // We need to check that our algorithm is OK, when optimal Huffman tree uses more than 15 levels !!! + Huffman_Generate(Freqs, vals, levels, NumSyms, k_NumHuffmanBits); + + /* + for (UInt32 i = NumSyms; i < m_NumSyms; i++) + levels[i] = 0; + */ + this->BuildFull(levels, NumSyms); + } + + void Rebuild() throw() + { + Generate(); + RebuildRem = m_RebuildFreq; + UInt32 num = NumSyms; + for (UInt32 i = 0; i < num; i++) + Freqs[i] = (Freqs[i] >> 1) + 1; + } + +public: + void Init(UInt32 numSyms = m_NumSyms) throw() + { + RebuildRem = m_RebuildFreq; + NumSyms = numSyms; + for (UInt32 i = 0; i < numSyms; i++) + Freqs[i] = 1; + // for (; i < m_NumSyms; i++) Freqs[i] = 0; + Generate(); + } +}; + + +struct CProbEntry +{ + UInt32 Prob; + UInt64 Hist; + + void Init() + { + Prob = k_InitialProb; + Hist = k_InitialHist; + } + + UInt32 GetProb() const throw() + { + UInt32 prob = Prob; + if (prob == 0) + prob = 1; + else if (prob == k_ProbLimit) + prob = k_ProbLimit - 1; + return prob; + } + + void Update(unsigned bit) throw() + { + Prob += (Int32)(Hist >> (k_ProbLimit - 1)) - (Int32)bit; + Hist = (Hist << 1) | bit; + } +}; + + +struct CRangeDecoder +{ + UInt32 range; + UInt32 code; + const Byte *cur; + // const Byte *end; + + void Init(const Byte *data, size_t /* size */) throw() + { + range = 0xFFFFFFFF; + code = (((UInt32)GetUi16(data)) << 16) | GetUi16(data + 2); + cur = data + 4; + // end = data + size; + } + + void Normalize() + { + if (range <= 0xFFFF) + { + range <<= 16; + code <<= 16; + // if (cur >= end) throw 1; + code |= GetUi16(cur); + cur += 2; + } + } + + unsigned Decode(UInt32 *state, UInt32 numStates, struct CProbEntry *probs) + { + UInt32 st = *state; + CProbEntry *entry = &probs[st]; + st = (st << 1) & (numStates - 1); + + UInt32 prob = entry->GetProb(); + + if (range <= 0xFFFF) + { + range <<= 16; + code <<= 16; + // if (cur >= end) throw 1; + code |= GetUi16(cur); + cur += 2; + } + + UInt32 bound = (range >> k_NumProbBits) * prob; + + if (code < bound) + { + range = bound; + *state = st; + entry->Update(0); + return 0; + } + else + { + range -= bound; + code -= bound; + *state = st | 1; + entry->Update(1); + return 1; + } + } +}; + + +class CDecoder +{ + // CRangeDecoder _rc; + // CBitDecoder _bs; + size_t _pos; + + UInt32 _reps[k_NumReps + 1]; + UInt64 _deltaReps[k_NumReps + 1]; + + UInt32 mainState; + UInt32 matchState; + UInt32 lzRepStates[k_NumReps]; + UInt32 deltaRepStates[k_NumReps]; + + struct CProbEntry mainProbs[k_NumMainProbs]; + struct CProbEntry matchProbs[k_NumMatchProbs]; + + struct CProbEntry lzRepProbs[k_NumReps][k_NumRepProbs]; + struct CProbEntry deltaRepProbs[k_NumReps][k_NumRepProbs]; + + CHuffDecoder<k_NumLitSyms, 1024, 9> m_LitDecoder; + CHuffDecoder<k_NumPosSyms, 1024, 9> m_PosDecoder; + CHuffDecoder<k_NumLenSyms, 512, 8> m_LenDecoder; + CHuffDecoder<k_NumPowerSyms, 512, 6> m_PowerDecoder; + CHuffDecoder<k_NumPosSyms, 1024, 9> m_DeltaDecoder; + + Int32 *_x86_history; + + HRESULT CodeReal(const Byte *in, size_t inSize, Byte *out, size_t outSize); +public: + CDecoder(); + ~CDecoder(); + + HRESULT Code(const Byte *in, size_t inSize, Byte *out, size_t outSize); + const size_t GetUnpackSize() const { return _pos; } +}; + +}} + +#endif diff --git a/CPP/7zip/Compress/Lzx.h b/CPP/7zip/Compress/Lzx.h index 09ab7f07..29ca4cac 100644 --- a/CPP/7zip/Compress/Lzx.h +++ b/CPP/7zip/Compress/Lzx.h @@ -6,55 +6,51 @@ namespace NCompress { namespace NLzx { +const unsigned kBlockType_NumBits = 3; +const unsigned kBlockType_Verbatim = 1; +const unsigned kBlockType_Aligned = 2; +const unsigned kBlockType_Uncompressed = 3; + const unsigned kNumHuffmanBits = 16; -const UInt32 kNumRepDistances = 3; +const unsigned kNumReps = 3; -const UInt32 kNumLenSlots = 8; -const UInt32 kMatchMinLen = 2; -const UInt32 kNumLenSymbols = 249; -const UInt32 kMatchMaxLen = kMatchMinLen + (kNumLenSlots - 1) + kNumLenSymbols - 1; +const unsigned kNumLenSlots = 8; +const unsigned kMatchMinLen = 2; +const unsigned kNumLenSymbols = 249; +const unsigned kMatchMaxLen = kMatchMinLen + (kNumLenSlots - 1) + kNumLenSymbols - 1; +const unsigned kNumAlignLevelBits = 3; const unsigned kNumAlignBits = 3; -const UInt32 kAlignTableSize = 1 << kNumAlignBits; - -const UInt32 kNumPosSlots = 50; -const UInt32 kNumPosLenSlots = kNumPosSlots * kNumLenSlots; - -const UInt32 kMainTableSize = 256 + kNumPosLenSlots; -const UInt32 kLevelTableSize = 20; -const UInt32 kMaxTableSize = kMainTableSize; - -const unsigned kNumBlockTypeBits = 3; -const unsigned kBlockTypeVerbatim = 1; -const unsigned kBlockTypeAligned = 2; -const unsigned kBlockTypeUncompressed = 3; +const unsigned kAlignTableSize = 1 << kNumAlignBits; -const unsigned kUncompressedBlockSizeNumBits = 24; +const unsigned kNumPosSlots = 50; +const unsigned kNumPosLenSlots = kNumPosSlots * kNumLenSlots; -const unsigned kNumBitsForPreTreeLevel = 4; +const unsigned kMainTableSize = 256 + kNumPosLenSlots; +const unsigned kLevelTableSize = 20; +const unsigned kMaxTableSize = kMainTableSize; -const unsigned kLevelSymbolZeros = 17; -const unsigned kLevelSymbolZerosBig = 18; -const unsigned kLevelSymbolSame = 19; +const unsigned kNumLevelBits = 4; -const unsigned kLevelSymbolZerosStartValue = 4; -const unsigned kLevelSymbolZerosNumBits = 4; +const unsigned kLevelSym_Zero1 = 17; +const unsigned kLevelSym_Zero2 = 18; +const unsigned kLevelSym_Same = 19; -const unsigned kLevelSymbolZerosBigStartValue = kLevelSymbolZerosStartValue + - (1 << kLevelSymbolZerosNumBits); -const unsigned kLevelSymbolZerosBigNumBits = 5; +const unsigned kLevelSym_Zero1_Start = 4; +const unsigned kLevelSym_Zero1_NumBits = 4; -const unsigned kLevelSymbolSameNumBits = 1; -const unsigned kLevelSymbolSameStartValue = 4; +const unsigned kLevelSym_Zero2_Start = kLevelSym_Zero1_Start + (1 << kLevelSym_Zero1_NumBits); +const unsigned kLevelSym_Zero2_NumBits = 5; -const unsigned kNumBitsForAlignLevel = 3; - -const unsigned kNumDictionaryBitsMin = 15; -const unsigned kNumDictionaryBitsMax = 21; -const UInt32 kDictionarySizeMax = (1 << kNumDictionaryBitsMax); +const unsigned kLevelSym_Same_NumBits = 1; +const unsigned kLevelSym_Same_Start = 4; + +const unsigned kNumDictBits_Min = 15; +const unsigned kNumDictBits_Max = 21; +const UInt32 kDictSize_Max = (UInt32)1 << kNumDictBits_Max; const unsigned kNumLinearPosSlotBits = 17; -const UInt32 kNumPowerPosSlots = 0x26; +const unsigned kNumPowerPosSlots = 38; }} diff --git a/CPP/7zip/Compress/Lzx86Converter.cpp b/CPP/7zip/Compress/Lzx86Converter.cpp deleted file mode 100644 index 3a63057a..00000000 --- a/CPP/7zip/Compress/Lzx86Converter.cpp +++ /dev/null @@ -1,90 +0,0 @@ -// Lzx86Converter.cpp - -#include "StdAfx.h" - -#include "../../Common/Defs.h" - -#include "Lzx86Converter.h" - -namespace NCompress { -namespace NLzx { - -static const UInt32 kResidue = 6 + 4; - -void Cx86ConvertOutStream::MakeTranslation() -{ - if (_pos <= kResidue) - return; - UInt32 numBytes = _pos - kResidue; - Byte *buf = _buf; - for (UInt32 i = 0; i < numBytes;) - { - if (buf[i++] == 0xE8) - { - Int32 absValue = 0; - unsigned j; - for (j = 0; j < 4; j++) - absValue += (UInt32)buf[i + j] << (j * 8); - Int32 pos = (Int32)(_processedSize + i - 1); - if (absValue >= -pos && absValue < (Int32)_translationSize) - { - UInt32 offset = (absValue >= 0) ? - absValue - pos : - absValue + _translationSize; - for (j = 0; j < 4; j++) - { - buf[i + j] = (Byte)(offset & 0xFF); - offset >>= 8; - } - } - i += 4; - } - } -} - -STDMETHODIMP Cx86ConvertOutStream::Write(const void *data, UInt32 size, UInt32 *processedSize) -{ - if (processedSize) - *processedSize = 0; - if (!_translationMode) - return _stream->Write(data, size, processedSize); - UInt32 realProcessedSize = 0; - while (realProcessedSize < size) - { - UInt32 writeSize = MyMin(size - realProcessedSize, kUncompressedBlockSize - _pos); - memcpy(_buf + _pos, (const Byte *)data + realProcessedSize, writeSize); - _pos += writeSize; - realProcessedSize += writeSize; - if (_pos == kUncompressedBlockSize) - { - RINOK(Flush()); - } - } - if (processedSize) - *processedSize = realProcessedSize; - return S_OK; -} - -HRESULT Cx86ConvertOutStream::Flush() -{ - if (_pos == 0) - return S_OK; - if (_translationMode) - MakeTranslation(); - UInt32 pos = 0; - do - { - UInt32 processed; - RINOK(_stream->Write(_buf + pos, _pos - pos, &processed)); - if (processed == 0) - return E_FAIL; - pos += processed; - } - while (pos < _pos); - _processedSize += _pos; - _pos = 0; - _translationMode = (_translationMode && (_processedSize < ((UInt32)1 << 30))); - return S_OK; -} - -}} diff --git a/CPP/7zip/Compress/Lzx86Converter.h b/CPP/7zip/Compress/Lzx86Converter.h deleted file mode 100644 index 1e531d1a..00000000 --- a/CPP/7zip/Compress/Lzx86Converter.h +++ /dev/null @@ -1,45 +0,0 @@ -// Lzx86Converter.h - -#ifndef __LZX_86_CONVERTER_H -#define __LZX_86_CONVERTER_H - -#include "../../Common/MyCom.h" - -#include "../IStream.h" - -namespace NCompress { -namespace NLzx { - -const unsigned kUncompressedBlockSize = (unsigned)1 << 15; - -class Cx86ConvertOutStream: - public ISequentialOutStream, - public CMyUnknownImp -{ - ISequentialOutStream *_stream; - UInt32 _processedSize; - UInt32 _pos; - UInt32 _translationSize; - bool _translationMode; - Byte _buf[kUncompressedBlockSize]; - - void MakeTranslation(); -public: - void SetStream(ISequentialOutStream *outStream) { _stream = outStream; } - void Init(bool translationMode, UInt32 translationSize) - { - _translationMode = translationMode; - _translationSize = translationSize; - _processedSize = 0; - _pos = 0; - } - HRESULT Flush(); - - MY_UNKNOWN_IMP - - STDMETHOD(Write)(const void *data, UInt32 size, UInt32 *processedSize); -}; - -}} - -#endif diff --git a/CPP/7zip/Compress/LzxDecoder.cpp b/CPP/7zip/Compress/LzxDecoder.cpp index acf3b037..8bdcc307 100644 --- a/CPP/7zip/Compress/LzxDecoder.cpp +++ b/CPP/7zip/Compress/LzxDecoder.cpp @@ -2,394 +2,528 @@ #include "StdAfx.h" -#include "../../Common/Defs.h" +#include <string.h> + +// #define SHOW_DEBUG_INFO + +#ifdef SHOW_DEBUG_INFO +#include <stdio.h> +#define PRF(x) x +#else +#define PRF(x) +#endif + +#include "../../../C/Alloc.h" #include "LzxDecoder.h" namespace NCompress { namespace NLzx { -const int kLenIdNeedInit = -2; +static void x86_Filter(Byte *data, UInt32 size, UInt32 processedSize, UInt32 translationSize) +{ + const UInt32 kResidue = 10; + if (size <= kResidue) + return; + size -= kResidue; + + Byte save = data[size + 4]; + data[size + 4] = 0xE8; + + for (UInt32 i = 0;;) + { + const Byte *p = data + i; + for (;;) + { + if (*p++ == 0xE8) break; + if (*p++ == 0xE8) break; + if (*p++ == 0xE8) break; + if (*p++ == 0xE8) break; + } + + i = (UInt32)(p - data); + + if (i > size) + break; + { + Int32 v = GetUi32(p); + Int32 pos = (Int32)((Int32)1 - (Int32)(processedSize + i)); + i += 4; + if (v >= pos && v < (Int32)translationSize) + { + v += (v >= 0 ? pos : translationSize); + SetUi32(p, v); + } + } + } + + data[size + 4] = save; +} + CDecoder::CDecoder(bool wimMode): - _keepHistory(false), - _skipByte(false), - _wimMode(wimMode) + _win(NULL), + _keepHistory(false), + _skipByte(false), + _wimMode(wimMode), + _numDictBits(15), + _unpackBlockSize(0), + _x86_buf(NULL), + _x86_translationSize(0), + KeepHistoryForNext(true), + NeedAlloc(true), + _unpackedData(NULL) { - m_x86ConvertOutStreamSpec = new Cx86ConvertOutStream; - m_x86ConvertOutStream = m_x86ConvertOutStreamSpec; } -/* -void CDecoder::ReleaseStreams() +CDecoder::~CDecoder() { - m_OutWindowStream.ReleaseStream(); - m_InBitStream.ReleaseStream(); - m_x86ConvertOutStreamSpec->ReleaseStream(); + if (NeedAlloc) + ::MidFree(_win); + ::MidFree(_x86_buf); } -*/ -STDMETHODIMP CDecoder::Flush() +HRESULT CDecoder::Flush() { - RINOK(m_OutWindowStream.Flush()); - return m_x86ConvertOutStreamSpec->Flush(); + if (_x86_translationSize != 0) + { + Byte *destData = _win + _writePos; + UInt32 curSize = _pos - _writePos; + if (KeepHistoryForNext) + { + if (!_x86_buf) + { + // we must change it to support another chunk sizes + const size_t kChunkSize = (size_t)1 << 15; + if (curSize > kChunkSize) + return E_NOTIMPL; + _x86_buf = (Byte *)::MidAlloc(kChunkSize); + if (!_x86_buf) + return E_OUTOFMEMORY; + } + memcpy(_x86_buf, destData, curSize); + _unpackedData = _x86_buf; + destData = _x86_buf; + } + x86_Filter(destData, (UInt32)curSize, _x86_processedSize, _x86_translationSize); + _x86_processedSize += (UInt32)curSize; + if (_x86_processedSize >= ((UInt32)1 << 30)) + _x86_translationSize = 0; + } + + return S_OK; } -UInt32 CDecoder::ReadBits(unsigned numBits) { return m_InBitStream.ReadBits(numBits); } + +UInt32 CDecoder::ReadBits(unsigned numBits) { return _bitStream.ReadBitsSmall(numBits); } #define RIF(x) { if (!(x)) return false; } -bool CDecoder::ReadTable(Byte *lastLevels, Byte *newLevels, UInt32 numSymbols) +bool CDecoder::ReadTable(Byte *levels, unsigned numSymbols) { - Byte levelLevels[kLevelTableSize]; - UInt32 i; - for (i = 0; i < kLevelTableSize; i++) - levelLevels[i] = (Byte)ReadBits(kNumBitsForPreTreeLevel); - RIF(m_LevelDecoder.SetCodeLengths(levelLevels)); - unsigned num = 0; - Byte symbol = 0; - for (i = 0; i < numSymbols;) { - if (num != 0) + Byte levels2[kLevelTableSize]; + for (unsigned i = 0; i < kLevelTableSize; i++) + levels2[i] = (Byte)ReadBits(kNumLevelBits); + RIF(_levelDecoder.Build(levels2)); + } + + unsigned i = 0; + do + { + UInt32 sym = _levelDecoder.Decode(&_bitStream); + if (sym <= kNumHuffmanBits) { - lastLevels[i] = newLevels[i] = symbol; - i++; - num--; + int delta = (int)levels[i] - (int)sym; + delta += (delta < 0) ? (kNumHuffmanBits + 1) : 0; + levels[i++] = (Byte)delta; continue; } - UInt32 number = m_LevelDecoder.DecodeSymbol(&m_InBitStream); - if (number == kLevelSymbolZeros) - { - num = kLevelSymbolZerosStartValue + (unsigned)ReadBits(kLevelSymbolZerosNumBits); - symbol = 0; - } - else if (number == kLevelSymbolZerosBig) + + unsigned num; + Byte symbol; + + if (sym < kLevelSym_Same) { - num = kLevelSymbolZerosBigStartValue + (unsigned)ReadBits(kLevelSymbolZerosBigNumBits); + sym -= kLevelSym_Zero1; + num = kLevelSym_Zero1_Start + ((unsigned)sym << kLevelSym_Zero1_NumBits) + + (unsigned)ReadBits(kLevelSym_Zero1_NumBits + sym); symbol = 0; } - else if (number == kLevelSymbolSame || number <= kNumHuffmanBits) + else if (sym == kLevelSym_Same) { - if (number <= kNumHuffmanBits) - num = 1; - else - { - num = kLevelSymbolSameStartValue + (unsigned)ReadBits(kLevelSymbolSameNumBits); - number = m_LevelDecoder.DecodeSymbol(&m_InBitStream); - if (number > kNumHuffmanBits) - return false; - } - symbol = Byte((17 + lastLevels[i] - number) % (kNumHuffmanBits + 1)); + num = kLevelSym_Same_Start + (unsigned)ReadBits(kLevelSym_Same_NumBits); + sym = _levelDecoder.Decode(&_bitStream); + if (sym > kNumHuffmanBits) + return false; + int delta = (int)levels[i] - (int)sym; + delta += (delta < 0) ? (kNumHuffmanBits + 1) : 0; + symbol = (Byte)delta; } else return false; + + unsigned limit = i + num; + if (limit > numSymbols) + return false; + + do + levels[i++] = symbol; + while (i < limit); } + while (i < numSymbols); + return true; } + bool CDecoder::ReadTables(void) { - Byte newLevels[kMaxTableSize]; { if (_skipByte) - m_InBitStream.DirectReadByte(); - m_InBitStream.Normalize(); + { + if (_bitStream.DirectReadByte() != 0) + return false; + } + + _bitStream.NormalizeBig(); - unsigned blockType = (unsigned)ReadBits(kNumBlockTypeBits); - if (blockType > kBlockTypeUncompressed) + unsigned blockType = (unsigned)ReadBits(kBlockType_NumBits); + if (blockType > kBlockType_Uncompressed) return false; - if (_wimMode) - if (ReadBits(1) == 1) - m_UnCompressedBlockSize = (1 << 15); - else - m_UnCompressedBlockSize = ReadBits(16); - else - m_UnCompressedBlockSize = m_InBitStream.ReadBitsBig(kUncompressedBlockSizeNumBits); + + _unpackBlockSize = (1 << 15); + if (!_wimMode || ReadBits(1) == 0) + { + _unpackBlockSize = ReadBits(16); + // wimlib supports chunks larger than 32KB (unsupported my MS wim). + if (!_wimMode || _numDictBits >= 16) + { + _unpackBlockSize <<= 8; + _unpackBlockSize |= ReadBits(8); + } + } + + PRF(printf("\nBlockSize = %6d %s ", _unpackBlockSize, (_pos & 1) ? "@@@" : " ")); - m_IsUncompressedBlock = (blockType == kBlockTypeUncompressed); + _isUncompressedBlock = (blockType == kBlockType_Uncompressed); - _skipByte = (m_IsUncompressedBlock && ((m_UnCompressedBlockSize & 1) != 0)); + _skipByte = false; - if (m_IsUncompressedBlock) + if (_isUncompressedBlock) { - ReadBits(16 - m_InBitStream.GetBitPosition()); - if (!m_InBitStream.ReadUInt32(m_RepDistances[0])) + _skipByte = ((_unpackBlockSize & 1) != 0); + + PRF(printf(" UncompressedBlock ")); + if (_unpackBlockSize & 1) + { + PRF(printf(" ######### ")); + } + + if (!_bitStream.PrepareUncompressed()) return false; - m_RepDistances[0]--; - for (unsigned i = 1; i < kNumRepDistances; i++) + if (_bitStream.GetRem() < kNumReps * 4) + return false; + + for (unsigned i = 0; i < kNumReps; i++) { - UInt32 rep = 0; - for (unsigned j = 0; j < 4; j++) - rep |= (UInt32)m_InBitStream.DirectReadByte() << (8 * j); - m_RepDistances[i] = rep - 1; + UInt32 rep = _bitStream.ReadUInt32(); + if (rep > _winSize) + return false; + _reps[i] = rep; } + return true; } - m_AlignIsUsed = (blockType == kBlockTypeAligned); - if (m_AlignIsUsed) + + _numAlignBits = 64; + + if (blockType == kBlockType_Aligned) { + Byte levels[kAlignTableSize]; + _numAlignBits = kNumAlignBits; for (unsigned i = 0; i < kAlignTableSize; i++) - newLevels[i] = (Byte)ReadBits(kNumBitsForAlignLevel); - RIF(m_AlignDecoder.SetCodeLengths(newLevels)); + levels[i] = (Byte)ReadBits(kNumAlignLevelBits); + RIF(_alignDecoder.Build(levels)); } } - RIF(ReadTable(m_LastMainLevels, newLevels, 256)); - RIF(ReadTable(m_LastMainLevels + 256, newLevels + 256, m_NumPosLenSlots)); - for (UInt32 i = 256 + m_NumPosLenSlots; i < kMainTableSize; i++) - newLevels[i] = 0; - RIF(m_MainDecoder.SetCodeLengths(newLevels)); - - RIF(ReadTable(m_LastLenLevels, newLevels, kNumLenSymbols)); - return m_LenDecoder.SetCodeLengths(newLevels); -} - -class CDecoderFlusher -{ - CDecoder *m_Decoder; -public: - bool NeedFlush; - CDecoderFlusher(CDecoder *decoder): m_Decoder(decoder), NeedFlush(true) {} - ~CDecoderFlusher() - { - if (NeedFlush) - m_Decoder->Flush(); - // m_Decoder->ReleaseStreams(); - } -}; - - -void CDecoder::ClearPrevLevels() -{ - unsigned i; - for (i = 0; i < kMainTableSize; i++) - m_LastMainLevels[i] = 0; - for (i = 0; i < kNumLenSymbols; i++) - m_LastLenLevels[i] = 0; + RIF(ReadTable(_mainLevels, 256)); + RIF(ReadTable(_mainLevels + 256, _numPosLenSlots)); + unsigned end = 256 + _numPosLenSlots; + memset(_mainLevels + end, 0, kMainTableSize - end); + RIF(_mainDecoder.Build(_mainLevels)); + RIF(ReadTable(_lenLevels, kNumLenSymbols)); + return _lenDecoder.Build(_lenLevels); } HRESULT CDecoder::CodeSpec(UInt32 curSize) { - if (_remainLen == kLenIdNeedInit) + if (!_keepHistory || !_isUncompressedBlock) + _bitStream.NormalizeBig(); + + if (!_keepHistory) { - _remainLen = 0; - m_InBitStream.Init(); - if (!_keepHistory || !m_IsUncompressedBlock) - m_InBitStream.Normalize(); - if (!_keepHistory) + _skipByte = false; + _unpackBlockSize = 0; + + memset(_mainLevels, 0, kMainTableSize); + memset(_lenLevels, 0, kNumLenSymbols); + { - _skipByte = false; - m_UnCompressedBlockSize = 0; - ClearPrevLevels(); - UInt32 i86TranslationSize = 12000000; - bool translationMode = true; + _x86_translationSize = 12000000; if (!_wimMode) { - translationMode = (ReadBits(1) != 0); - if (translationMode) + _x86_translationSize = 0; + if (ReadBits(1) != 0) { - i86TranslationSize = ReadBits(16) << 16; - i86TranslationSize |= ReadBits(16); + UInt32 v = ReadBits(16) << 16; + v |= ReadBits(16); + _x86_translationSize = v; } } - m_x86ConvertOutStreamSpec->Init(translationMode, i86TranslationSize); - for (unsigned i = 0 ; i < kNumRepDistances; i++) - m_RepDistances[i] = 0; + _x86_processedSize = 0; } - } - while (_remainLen > 0 && curSize > 0) - { - m_OutWindowStream.PutByte(m_OutWindowStream.GetByte(m_RepDistances[0])); - _remainLen--; - curSize--; + _reps[0] = 1; + _reps[1] = 1; + _reps[2] = 1; } while (curSize > 0) { - if (m_UnCompressedBlockSize == 0) + if (_bitStream.WasExtraReadError_Fast()) + return S_FALSE; + + if (_unpackBlockSize == 0) + { if (!ReadTables()) return S_FALSE; - UInt32 next = (Int32)MyMin(m_UnCompressedBlockSize, curSize); - curSize -= next; - m_UnCompressedBlockSize -= next; - if (m_IsUncompressedBlock) + continue; + } + + UInt32 next = _unpackBlockSize; + if (next > curSize) + next = curSize; + + if (_isUncompressedBlock) { - while (next > 0) + size_t rem = _bitStream.GetRem(); + if (rem == 0) + return S_FALSE; + if (next > rem) + next = (UInt32)rem; + _bitStream.CopyTo(_win + _pos, next); + _pos += next; + curSize -= next; + _unpackBlockSize -= next; + + /* we don't know where skipByte can be placed, if it's end of chunk: + 1) in current chunk - there are such cab archives, if chunk is last + 2) in next chunk - are there such archives ? */ + + if (_skipByte + && _unpackBlockSize == 0 + && curSize == 0 + && _bitStream.IsOneDirectByteLeft()) { - m_OutWindowStream.PutByte(m_InBitStream.DirectReadByte()); - next--; + _skipByte = false; + if (_bitStream.DirectReadByte() != 0) + return S_FALSE; } + + continue; } - else while (next > 0) + + curSize -= next; + _unpackBlockSize -= next; + + Byte *win = _win; + + while (next > 0) { - UInt32 number = m_MainDecoder.DecodeSymbol(&m_InBitStream); - if (number < 256) + if (_bitStream.WasExtraReadError_Fast()) + return S_FALSE; + + UInt32 sym = _mainDecoder.Decode(&_bitStream); + + if (sym < 256) { - m_OutWindowStream.PutByte((Byte)number); + win[_pos++] = (Byte)sym; next--; + continue; } - else { - UInt32 posLenSlot = number - 256; - if (posLenSlot >= m_NumPosLenSlots) + sym -= 256; + if (sym >= _numPosLenSlots) return S_FALSE; - UInt32 posSlot = posLenSlot / kNumLenSlots; - UInt32 lenSlot = posLenSlot % kNumLenSlots; + UInt32 posSlot = sym / kNumLenSlots; + UInt32 lenSlot = sym % kNumLenSlots; UInt32 len = kMatchMinLen + lenSlot; + if (lenSlot == kNumLenSlots - 1) { - UInt32 lenTemp = m_LenDecoder.DecodeSymbol(&m_InBitStream); + UInt32 lenTemp = _lenDecoder.Decode(&_bitStream); if (lenTemp >= kNumLenSymbols) return S_FALSE; - len += lenTemp; + len = kMatchMinLen + kNumLenSlots - 1 + lenTemp; } - if (posSlot < kNumRepDistances) + UInt32 dist; + + if (posSlot < kNumReps) { - UInt32 distance = m_RepDistances[posSlot]; - m_RepDistances[posSlot] = m_RepDistances[0]; - m_RepDistances[0] = distance; + dist = _reps[posSlot]; + _reps[posSlot] = _reps[0]; + _reps[0] = dist; } else { - UInt32 distance; unsigned numDirectBits; + if (posSlot < kNumPowerPosSlots) { numDirectBits = (unsigned)(posSlot >> 1) - 1; - distance = ((2 | (posSlot & 1)) << numDirectBits); + dist = ((2 | (posSlot & 1)) << numDirectBits); } else { numDirectBits = kNumLinearPosSlotBits; - distance = ((posSlot - 0x22) << kNumLinearPosSlotBits); + dist = ((posSlot - 0x22) << kNumLinearPosSlotBits); } - if (m_AlignIsUsed && numDirectBits >= kNumAlignBits) + if (numDirectBits >= _numAlignBits) { - distance += (m_InBitStream.ReadBits(numDirectBits - kNumAlignBits) << kNumAlignBits); - UInt32 alignTemp = m_AlignDecoder.DecodeSymbol(&m_InBitStream); + dist += (_bitStream.ReadBitsSmall(numDirectBits - kNumAlignBits) << kNumAlignBits); + UInt32 alignTemp = _alignDecoder.Decode(&_bitStream); if (alignTemp >= kAlignTableSize) return S_FALSE; - distance += alignTemp; + dist += alignTemp; } else - distance += m_InBitStream.ReadBits(numDirectBits); - m_RepDistances[2] = m_RepDistances[1]; - m_RepDistances[1] = m_RepDistances[0]; - m_RepDistances[0] = distance - kNumRepDistances; + dist += _bitStream.ReadBitsBig(numDirectBits); + + dist -= kNumReps - 1; + _reps[2] = _reps[1]; + _reps[1] = _reps[0]; + _reps[0] = dist; } - UInt32 locLen = len; - if (locLen > next) - locLen = next; + if (len > next) + return S_FALSE; - if (!m_OutWindowStream.CopyBlock(m_RepDistances[0], locLen)) + if (dist > _pos && !_overDict) return S_FALSE; - len -= locLen; - next -= locLen; - if (len != 0) + Byte *dest = win + _pos; + const UInt32 mask = (_winSize - 1); + UInt32 srcPos = (_pos - dist) & mask; + + next -= len; + + if (len > _winSize - srcPos) + { + _pos += len; + do + { + *dest++ = win[srcPos++]; + srcPos &= mask; + } + while (--len); + } + else { - _remainLen = (int)len; - return S_OK; + ptrdiff_t src = (ptrdiff_t)srcPos - (ptrdiff_t)_pos; + _pos += len; + const Byte *lim = dest + len; + *(dest) = *(dest + src); + dest++; + do + *(dest) = *(dest + src); + while (++dest != lim); } } } } + + if (!_bitStream.WasFinishedOK()) + return S_FALSE; + return S_OK; } -HRESULT CDecoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream, - const UInt64 *, const UInt64 *outSize, ICompressProgressInfo *progress) + +HRESULT CDecoder::Code(const Byte *inData, size_t inSize, UInt32 outSize) { - if (outSize == NULL) - return E_INVALIDARG; - UInt64 size = *outSize; + if (_pos == _winSize) + { + _pos = 0; + _overDict = true; + } - // RINOK(SetInStream(inStream)); - m_InBitStream.SetStream(inStream); - m_x86ConvertOutStreamSpec->SetStream(outStream); - m_OutWindowStream.SetStream(m_x86ConvertOutStream); - RINOK(SetOutStreamSize(outSize)); + if (!_keepHistory) + { + _pos = 0; + _overDict = false; + } - CDecoderFlusher flusher(this); + _writePos = _pos; + _unpackedData = _win + _pos; + + if (outSize > _winSize - _pos) + return S_FALSE; - const UInt64 start = m_OutWindowStream.GetProcessedSize(); - for (;;) + PRF(printf("\ninSize = %d", inSize)); + if ((inSize & 1) != 0) { - UInt32 curSize = 1 << 18; - UInt64 rem = size - (m_OutWindowStream.GetProcessedSize() - start); - if (curSize > rem) - curSize = (UInt32)rem; - if (curSize == 0) - break; - RINOK(CodeSpec(curSize)); - if (progress != NULL) - { - UInt64 inSize = m_InBitStream.GetProcessedSize(); - UInt64 nowPos64 = m_OutWindowStream.GetProcessedSize() - start; - RINOK(progress->SetRatioInfo(&inSize, &nowPos64)); - } + PRF(printf(" ---------")); } - flusher.NeedFlush = false; - return Flush(); -} -HRESULT CDecoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream, - const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress) -{ - try { return CodeReal(inStream, outStream, inSize, outSize, progress); } - catch(const CLzOutWindowException &e) { return e.ErrorCode; } - catch(...) { return S_FALSE; } -} + if (inSize < 1) + return S_FALSE; -/* -STDMETHODIMP CDecoder::SetInStream(ISequentialInStream *inStream) -{ - m_InStreamRef = inStream; - m_InBitStream.SetStream(inStream); - return S_OK; -} + _bitStream.Init(inData, inSize); -STDMETHODIMP CDecoder::ReleaseInStream() -{ - m_InStreamRef.Release(); - return S_OK; + HRESULT res = CodeSpec(outSize); + HRESULT res2 = Flush(); + return (res == S_OK ? res2 : res); } -*/ -STDMETHODIMP CDecoder::SetOutStreamSize(const UInt64 *outSize) + +HRESULT CDecoder::SetParams2(unsigned numDictBits) { - if (outSize == NULL) - return E_FAIL; - // flush calls m_x86ConvertOutStreamSpec->flush, so we must init x86Convert. - if (!_keepHistory) - m_x86ConvertOutStreamSpec->Init(false, 0); - _remainLen = kLenIdNeedInit; - m_OutWindowStream.Init(_keepHistory); + _numDictBits = numDictBits; + if (numDictBits < kNumDictBits_Min || numDictBits > kNumDictBits_Max) + return E_INVALIDARG; + unsigned numPosSlots = (numDictBits < 20) ? + numDictBits * 2 : + 34 + ((unsigned)1 << (numDictBits - 17)); + _numPosLenSlots = numPosSlots * kNumLenSlots; return S_OK; } + -HRESULT CDecoder::SetParams(unsigned numDictBits) +HRESULT CDecoder::SetParams_and_Alloc(unsigned numDictBits) { - if (numDictBits < kNumDictionaryBitsMin || numDictBits > kNumDictionaryBitsMax) - return E_INVALIDARG; - UInt32 numPosSlots; - if (numDictBits < 20) - numPosSlots = 30 + (numDictBits - 15) * 2; - else if (numDictBits == 20) - numPosSlots = 42; - else - numPosSlots = 50; - m_NumPosLenSlots = numPosSlots * kNumLenSlots; - if (!m_OutWindowStream.Create(kDictionarySizeMax)) - return E_OUTOFMEMORY; - if (!m_InBitStream.Create(1 << 16)) - return E_OUTOFMEMORY; + RINOK(SetParams2(numDictBits)); + + UInt32 newWinSize = (UInt32)1 << numDictBits; + + if (NeedAlloc) + { + if (!_win || newWinSize != _winSize) + { + ::MidFree(_win); + _winSize = 0; + _win = (Byte *)::MidAlloc(newWinSize); + if (!_win) + return E_OUTOFMEMORY; + } + } + + _winSize = (UInt32)newWinSize; return S_OK; } diff --git a/CPP/7zip/Compress/LzxDecoder.h b/CPP/7zip/Compress/LzxDecoder.h index 62d5b488..b06d5948 100644 --- a/CPP/7zip/Compress/LzxDecoder.h +++ b/CPP/7zip/Compress/LzxDecoder.h @@ -3,155 +3,240 @@ #ifndef __LZX_DECODER_H #define __LZX_DECODER_H -#include "../ICoder.h" +#include "../../../C/CpuArch.h" -#include "../Common/InBuffer.h" +#include "../../Common/MyCom.h" #include "HuffmanDecoder.h" -#include "LzOutWindow.h" #include "Lzx.h" -#include "Lzx86Converter.h" namespace NCompress { namespace NLzx { -namespace NBitStream { - -const unsigned kNumBigValueBits = 8 * 4; -const unsigned kNumValueBits = 17; -const UInt32 kBitDecoderValueMask = (1 << kNumValueBits) - 1; - -class CDecoder +class CBitDecoder { - CInBuffer _stream; - UInt32 _value; unsigned _bitPos; + UInt32 _value; + const Byte *_buf; + const Byte *_bufLim; + UInt32 _extraSize; public: - CDecoder() {} - bool Create(UInt32 bufSize) { return _stream.Create(bufSize); } - - void SetStream(ISequentialInStream *s) { _stream.SetStream(s); } - void Init() + void Init(const Byte *data, size_t size) { - _stream.Init(); - _bitPos = kNumBigValueBits; + _buf = data; + _bufLim = data + size - 1; + _bitPos = 0; + _extraSize = 0; } - UInt64 GetProcessedSize() const { return _stream.GetProcessedSize() - ((kNumBigValueBits - _bitPos) >> 3); } + size_t GetRem() const { return _bufLim + 1 - _buf; } + bool WasExtraReadError_Fast() const { return _extraSize > 4; } + + bool WasFinishedOK() const + { + if (_buf != _bufLim + 1) + return false; + if ((_bitPos >> 4) * 2 != _extraSize) + return false; + unsigned numBits = _bitPos & 15; + return (((_value >> (_bitPos - numBits)) & (((UInt32)1 << numBits) - 1)) == 0); + } - unsigned GetBitPosition() const { return _bitPos & 0xF; } + void NormalizeSmall() + { + if (_bitPos <= 16) + { + UInt32 val; + if (_buf >= _bufLim) + { + val = 0xFFFF; + _extraSize += 2; + } + else + { + val = GetUi16(_buf); + _buf += 2; + } + _value = (_value << 16) | val; + _bitPos += 16; + } + } - void Normalize() + void NormalizeBig() { - for (; _bitPos >= 16; _bitPos -= 16) + if (_bitPos <= 16) { - Byte b0 = _stream.ReadByte(); - Byte b1 = _stream.ReadByte(); - _value = (_value << 8) | b1; - _value = (_value << 8) | b0; + UInt32 val; + if (_buf >= _bufLim) + { + val = 0xFFFF; + _extraSize += 2; + } + else + { + val = GetUi16(_buf); + _buf += 2; + } + _value = (_value << 16) | val; + _bitPos += 16; + if (_bitPos <= 16) + { + UInt32 val; + if (_buf >= _bufLim) + { + val = 0xFFFF; + _extraSize += 2; + } + else + { + val = GetUi16(_buf); + _buf += 2; + } + _value = (_value << 16) | val; + _bitPos += 16; + } } } UInt32 GetValue(unsigned numBits) const { - return ((_value >> ((32 - kNumValueBits) - _bitPos)) & kBitDecoderValueMask) >> (kNumValueBits - numBits); + return (_value >> (_bitPos - numBits)) & (((UInt32)1 << numBits) - 1); } void MovePos(unsigned numBits) { - _bitPos += numBits; - Normalize(); + _bitPos -= numBits; + NormalizeSmall(); } - UInt32 ReadBits(unsigned numBits) + UInt32 ReadBitsSmall(unsigned numBits) { - UInt32 res = GetValue(numBits); - MovePos(numBits); - return res; + _bitPos -= numBits; + UInt32 val = (_value >> _bitPos) & (((UInt32)1 << numBits) - 1); + NormalizeSmall(); + return val; } UInt32 ReadBitsBig(unsigned numBits) { - unsigned numBits0 = numBits / 2; - unsigned numBits1 = numBits - numBits0; - UInt32 res = ReadBits(numBits0) << numBits1; - return res + ReadBits(numBits1); + _bitPos -= numBits; + UInt32 val = (_value >> _bitPos) & (((UInt32)1 << numBits) - 1); + NormalizeBig(); + return val; } - bool ReadUInt32(UInt32 &v) + bool PrepareUncompressed() { - if (_bitPos != 0) + if (_extraSize != 0) + return false; + unsigned numBits = _bitPos - 16; + if (((_value >> 16) & (((UInt32)1 << numBits) - 1)) != 0) return false; - v = ((_value >> 16) & 0xFFFF) | ((_value << 16) & 0xFFFF0000); - _bitPos = kNumBigValueBits; + _buf -= 2; + _bitPos = 0; return true; } - Byte DirectReadByte() { return _stream.ReadByte(); } + UInt32 ReadUInt32() + { + UInt32 v = GetUi32(_buf); + _buf += 4; + return v; + } + + void CopyTo(Byte *dest, size_t size) + { + memcpy(dest, _buf, size); + _buf += size; + } + bool IsOneDirectByteLeft() const { return _buf == _bufLim && _extraSize == 0; } + + Byte DirectReadByte() + { + if (_buf > _bufLim) + { + _extraSize++; + return 0xFF; + } + return *_buf++; + } }; -} -class CDecoder : - public ICompressCoder, + +class CDecoder: + public IUnknown, public CMyUnknownImp { - // CMyComPtr<ISequentialInStream> m_InStreamRef; - NBitStream::CDecoder m_InBitStream; - CLzOutWindow m_OutWindowStream; - - UInt32 m_RepDistances[kNumRepDistances]; - UInt32 m_NumPosLenSlots; + CBitDecoder _bitStream; + Byte *_win; + UInt32 _pos; + UInt32 _winSize; - bool m_IsUncompressedBlock; - bool m_AlignIsUsed; + bool _overDict; + bool _isUncompressedBlock; + bool _skipByte; + unsigned _numAlignBits; - NCompress::NHuffman::CDecoder<kNumHuffmanBits, kMainTableSize> m_MainDecoder; - NCompress::NHuffman::CDecoder<kNumHuffmanBits, kNumLenSymbols> m_LenDecoder; - NCompress::NHuffman::CDecoder<kNumHuffmanBits, kAlignTableSize> m_AlignDecoder; - NCompress::NHuffman::CDecoder<kNumHuffmanBits, kLevelTableSize> m_LevelDecoder; + UInt32 _reps[kNumReps]; + UInt32 _numPosLenSlots; + UInt32 _unpackBlockSize; - Byte m_LastMainLevels[kMainTableSize]; - Byte m_LastLenLevels[kNumLenSymbols]; +public: + bool KeepHistoryForNext; + bool NeedAlloc; +private: + bool _keepHistory; + bool _wimMode; + unsigned _numDictBits; + UInt32 _writePos; - Cx86ConvertOutStream *m_x86ConvertOutStreamSpec; - CMyComPtr<ISequentialOutStream> m_x86ConvertOutStream; + Byte *_x86_buf; + UInt32 _x86_translationSize; + UInt32 _x86_processedSize; - UInt32 m_UnCompressedBlockSize; + Byte *_unpackedData; + + NHuffman::CDecoder<kNumHuffmanBits, kMainTableSize> _mainDecoder; + NHuffman::CDecoder<kNumHuffmanBits, kNumLenSymbols> _lenDecoder; + NHuffman::CDecoder7b<kAlignTableSize> _alignDecoder; + NHuffman::CDecoder<kNumHuffmanBits, kLevelTableSize, 7> _levelDecoder; - bool _keepHistory; - int _remainLen; - bool _skipByte; + Byte _mainLevels[kMainTableSize]; + Byte _lenLevels[kNumLenSymbols]; - bool _wimMode; + HRESULT Flush(); UInt32 ReadBits(unsigned numBits); - bool ReadTable(Byte *lastLevels, Byte *newLevels, UInt32 numSymbols); + bool ReadTable(Byte *levels, unsigned numSymbols); bool ReadTables(); - void ClearPrevLevels(); HRESULT CodeSpec(UInt32 size); - - HRESULT CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream, - const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress); + HRESULT SetParams2(unsigned numDictBits); public: CDecoder(bool wimMode = false); + ~CDecoder(); MY_UNKNOWN_IMP - // void ReleaseStreams(); - STDMETHOD(Flush)(); + HRESULT SetExternalWindow(Byte *win, unsigned numDictBits) + { + NeedAlloc = false; + _win = win; + _winSize = (UInt32)1 << numDictBits; + return SetParams2(numDictBits); + } - STDMETHOD(Code)(ISequentialInStream *inStream, ISequentialOutStream *outStream, - const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress); + void SetKeepHistory(bool keepHistory) { _keepHistory = keepHistory; } - // STDMETHOD(SetInStream)(ISequentialInStream *inStream); - // STDMETHOD(ReleaseInStream)(); - STDMETHOD(SetOutStreamSize)(const UInt64 *outSize); + HRESULT SetParams_and_Alloc(unsigned numDictBits); - HRESULT SetParams(unsigned numDictBits); - void SetKeepHistory(bool keepHistory) { _keepHistory = keepHistory; } + HRESULT Code(const Byte *inData, size_t inSize, UInt32 outSize); + + bool WasBlockFinished() const { return _unpackBlockSize == 0; } + const Byte *GetUnpackData() const { return _unpackedData; } + const UInt32 GetUnpackSize() const { return _pos - _writePos; } }; }} diff --git a/CPP/7zip/Compress/QuantumDecoder.cpp b/CPP/7zip/Compress/QuantumDecoder.cpp index b184dfb6..2adb9053 100644 --- a/CPP/7zip/Compress/QuantumDecoder.cpp +++ b/CPP/7zip/Compress/QuantumDecoder.cpp @@ -9,13 +9,81 @@ namespace NCompress { namespace NQuantum { -static const int kLenIdNeedInit = -2; - static const unsigned kNumLenSymbols = 27; static const unsigned kMatchMinLen = 3; static const unsigned kNumSimplePosSlots = 4; static const unsigned kNumSimpleLenSlots = 6; +static const UInt16 kUpdateStep = 8; +static const UInt16 kFreqSumMax = 3800; +static const unsigned kReorderCountStart = 4; +static const unsigned kReorderCount = 50; + +void CModelDecoder::Init(unsigned numItems) +{ + NumItems = numItems; + ReorderCount = kReorderCountStart; + for (unsigned i = 0; i < numItems; i++) + { + Freqs[i] = (UInt16)(numItems - i); + Vals[i] = (Byte)i; + } + Freqs[numItems] = 0; +} + +unsigned CModelDecoder::Decode(CRangeDecoder *rc) +{ + UInt32 threshold = rc->GetThreshold(Freqs[0]); + unsigned i; + for (i = 1; Freqs[i] > threshold; i++); + + rc->Decode(Freqs[i], Freqs[i - 1], Freqs[0]); + unsigned res = Vals[--i]; + + do + Freqs[i] += kUpdateStep; + while (i--); + + if (Freqs[0] > kFreqSumMax) + { + if (--ReorderCount == 0) + { + ReorderCount = kReorderCount; + for (i = 0; i < NumItems; i++) + Freqs[i] = (UInt16)(((Freqs[i] - Freqs[i + 1]) + 1) >> 1); + for (i = 0; i < NumItems - 1; i++) + for (unsigned j = i + 1; j < NumItems; j++) + if (Freqs[i] < Freqs[j]) + { + UInt16 tmpFreq = Freqs[i]; + Byte tmpVal = Vals[i]; + Freqs[i] = Freqs[j]; + Vals[i] = Vals[j]; + Freqs[j] = tmpFreq; + Vals[j] = tmpVal; + } + + do + Freqs[i] = (UInt16)(Freqs[i] + Freqs[i + 1]); + while (i--); + } + else + { + i = NumItems - 1; + do + { + Freqs[i] >>= 1; + if (Freqs[i] <= Freqs[i + 1]) + Freqs[i] = (UInt16)(Freqs[i + 1] + 1); + } + while (i--); + } + } + + return res; +} + + void CDecoder::Init() { m_Selector.Init(kNumSelectors); @@ -29,156 +97,97 @@ void CDecoder::Init() m_LenSlot.Init(kNumLenSymbols); } -HRESULT CDecoder::CodeSpec(UInt32 curSize) + +HRESULT CDecoder::CodeSpec(const Byte *inData, size_t inSize, UInt32 outSize) { - if (_remainLen == kLenIdNeedInit) - { - _rangeDecoder.Init(); - _remainLen = 0; - } - if (curSize == 0) - return S_OK; + if (inSize < 2) + return S_FALSE; - while (_remainLen > 0 && curSize > 0) - { - _remainLen--; - Byte b = _outWindowStream.GetByte(_rep0); - _outWindowStream.PutByte(b); - curSize--; - } + CRangeDecoder rc; + rc.Stream.SetStreamAndInit(inData, inSize); + rc.Init(); - while (curSize > 0) + while (outSize != 0) { - if (_rangeDecoder.Stream.WasFinished()) + if (rc.Stream.WasExtraRead()) return S_FALSE; - unsigned selector = m_Selector.Decode(&_rangeDecoder); + unsigned selector = m_Selector.Decode(&rc); + if (selector < kNumLitSelectors) { - Byte b = (Byte)((selector << (8 - kNumLitSelectorBits)) + m_Literals[selector].Decode(&_rangeDecoder)); - _outWindowStream.PutByte(b); - curSize--; + Byte b = (Byte)((selector << (8 - kNumLitSelectorBits)) + m_Literals[selector].Decode(&rc)); + _outWindow.PutByte(b); + outSize--; } else { selector -= kNumLitSelectors; unsigned len = selector + kMatchMinLen; + if (selector == 2) { - unsigned lenSlot = m_LenSlot.Decode(&_rangeDecoder); + unsigned lenSlot = m_LenSlot.Decode(&rc); if (lenSlot >= kNumSimpleLenSlots) { lenSlot -= 2; - int numDirectBits = (int)(lenSlot >> 2); + unsigned numDirectBits = (unsigned)(lenSlot >> 2); len += ((4 | (lenSlot & 3)) << numDirectBits) - 2; if (numDirectBits < 6) - len += _rangeDecoder.Stream.ReadBits(numDirectBits); + len += rc.Stream.ReadBits(numDirectBits); } else len += lenSlot; } - UInt32 rep0 = m_PosSlot[selector].Decode(&_rangeDecoder); - if (rep0 >= kNumSimplePosSlots) + + UInt32 dist = m_PosSlot[selector].Decode(&rc); + + if (dist >= kNumSimplePosSlots) { - int numDirectBits = (int)((rep0 >> 1) - 1); - rep0 = ((2 | (rep0 & 1)) << numDirectBits) + _rangeDecoder.Stream.ReadBits(numDirectBits); + unsigned numDirectBits = (unsigned)((dist >> 1) - 1); + dist = ((2 | (dist & 1)) << numDirectBits) + rc.Stream.ReadBits(numDirectBits); } + unsigned locLen = len; - if (len > curSize) - locLen = (unsigned)curSize; - if (!_outWindowStream.CopyBlock(rep0, locLen)) + if (len > outSize) + locLen = (unsigned)outSize; + if (!_outWindow.CopyBlock(dist, locLen)) return S_FALSE; - curSize -= locLen; + outSize -= locLen; len -= locLen; if (len != 0) - { - _remainLen = (int)len; - _rep0 = rep0; - break; - } + return S_FALSE; } } - return _rangeDecoder.Stream.WasFinished() ? S_FALSE : S_OK; + + return rc.Finish() ? S_OK : S_FALSE; } -HRESULT CDecoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream, - const UInt64 *, const UInt64 *outSize, ICompressProgressInfo *progress) +HRESULT CDecoder::Code(const Byte *inData, size_t inSize, + ISequentialOutStream *outStream, UInt32 outSize, + bool keepHistory) { - if (outSize == NULL) - return E_INVALIDARG; - UInt64 size = *outSize; - - // SetInStream(inStream); - _rangeDecoder.SetStream(inStream); - - _outWindowStream.SetStream(outStream); - SetOutStreamSize(outSize); - CDecoderFlusher flusher(this); - - const UInt64 start = _outWindowStream.GetProcessedSize(); - for (;;) + try { - UInt32 curSize = 1 << 18; - UInt64 rem = size - (_outWindowStream.GetProcessedSize() - start); - if (curSize > rem) - curSize = (UInt32)rem; - if (curSize == 0) - break; - RINOK(CodeSpec(curSize)); - if (progress != NULL) - { - UInt64 inSize = _rangeDecoder.GetProcessedSize(); - UInt64 nowPos64 = _outWindowStream.GetProcessedSize() - start; - RINOK(progress->SetRatioInfo(&inSize, &nowPos64)); - } + _outWindow.SetStream(outStream); + _outWindow.Init(keepHistory); + if (!keepHistory) + Init(); + + HRESULT res = CodeSpec(inData, inSize, outSize); + HRESULT res2 = _outWindow.Flush(); + return res != S_OK ? res : res2; } - flusher.NeedFlush = false; - return Flush(); -} - -STDMETHODIMP CDecoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream, - const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress) -{ - try { return CodeReal(inStream, outStream, inSize, outSize, progress); } - catch(const CInBufferException &e) { return e.ErrorCode; } - catch(const CLzOutWindowException &e) { return e.ErrorCode; } + catch(const CLzOutWindowException &e) { return e.ErrorCode; } catch(...) { return S_FALSE; } } -/* -STDMETHODIMP CDecoder::SetInStream(ISequentialInStream *inStream) -{ - m_InStreamRef = inStream; - _rangeDecoder.SetStream(inStream); - return S_OK; -} - -STDMETHODIMP CDecoder::ReleaseInStream() -{ - m_InStreamRef.Release(); - return S_OK; -} -*/ - -STDMETHODIMP CDecoder::SetOutStreamSize(const UInt64 *outSize) -{ - if (outSize == NULL) - return E_FAIL; - _remainLen = kLenIdNeedInit; - _outWindowStream.Init(_keepHistory); - if (!_keepHistory) - Init(); - return S_OK; -} - -HRESULT CDecoder::SetParams(int numDictBits) +HRESULT CDecoder::SetParams(unsigned numDictBits) { if (numDictBits > 21) return E_INVALIDARG; _numDictBits = numDictBits; - if (!_outWindowStream.Create((UInt32)1 << _numDictBits)) - return E_OUTOFMEMORY; - if (!_rangeDecoder.Create(1 << 20)) + if (!_outWindow.Create((UInt32)1 << _numDictBits)) return E_OUTOFMEMORY; return S_OK; } diff --git a/CPP/7zip/Compress/QuantumDecoder.h b/CPP/7zip/Compress/QuantumDecoder.h index c18ea2aa..afeba708 100644 --- a/CPP/7zip/Compress/QuantumDecoder.h +++ b/CPP/7zip/Compress/QuantumDecoder.h @@ -5,92 +5,94 @@ #include "../../Common/MyCom.h" -#include "../ICoder.h" - -#include "../Common/InBuffer.h" - #include "LzOutWindow.h" namespace NCompress { namespace NQuantum { -class CStreamBitDecoder +class CBitDecoder { UInt32 Value; - CInBuffer Stream; + bool _extra; + const Byte *_buf; + const Byte *_bufLim; public: - bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); } - void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); } - // void ReleaseStream() { Stream.ReleaseStream(); } - - void Finish() { Value = 0x10000; } - - void Init() + void SetStreamAndInit(const Byte *inData, size_t inSize) { - Stream.Init(); + _buf = inData; + _bufLim = inData + inSize; Value = 0x10000; + _extra = false; } - UInt64 GetProcessedSize() const { return Stream.GetProcessedSize(); } - bool WasFinished() const { return Stream.WasFinished(); } + bool WasExtraRead() const { return _extra; } + + bool WasFinishedOK() const + { + return !_extra && _buf == _bufLim; + } UInt32 ReadBit() { if (Value >= 0x10000) - Value = 0x100 | Stream.ReadByte(); + { + Byte b; + if (_buf >= _bufLim) + { + b = 0xFF; + _extra = true; + } + else + b = *_buf++; + Value = 0x100 | b; + } UInt32 res = (Value >> 7) & 1; Value <<= 1; return res; } - UInt32 ReadBits(int numBits) // numBits > 0 + UInt32 ReadStart16Bits() + { + // we use check for extra read in another code. + UInt32 val = ((UInt32)*_buf << 8) | _buf[1]; + _buf += 2; + return val; + } + + UInt32 ReadBits(unsigned numBits) // numBits > 0 { UInt32 res = 0; do res = (res << 1) | ReadBit(); - while (--numBits != 0); + while (--numBits); return res; } }; -const unsigned kNumLitSelectorBits = 2; -const unsigned kNumLitSelectors = (1 << kNumLitSelectorBits); -const unsigned kNumLitSymbols = 1 << (8 - kNumLitSelectorBits); -const unsigned kNumMatchSelectors = 3; -const unsigned kNumSelectors = kNumLitSelectors + kNumMatchSelectors; -const unsigned kNumSymbolsMax = kNumLitSymbols; // 64 - -namespace NRangeCoder { -class CDecoder +class CRangeDecoder { UInt32 Low; UInt32 Range; UInt32 Code; public: - CStreamBitDecoder Stream; - bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); } - void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); } - // void ReleaseStream() { Stream.ReleaseStream(); } + CBitDecoder Stream; void Init() { - Stream.Init(); Low = 0; Range = 0x10000; - Code = Stream.ReadBits(16); + Code = Stream.ReadStart16Bits(); } - void Finish() + bool Finish() { - // we need these extra two Bit_reads - Stream.ReadBit(); - Stream.ReadBit(); - Stream.Finish(); + // do all streams use these two bits at end? + if (Stream.ReadBit() != 0) return false; + if (Stream.ReadBit() != 0) return false; + return Stream.WasFinishedOK(); } - UInt64 GetProcessedSize() const { return Stream.GetProcessedSize(); } - UInt32 GetThreshold(UInt32 total) const { return ((Code + 1) * total - 1) / Range; // & 0xFFFF is not required; @@ -119,148 +121,52 @@ public: } }; -const UInt16 kUpdateStep = 8; -const UInt16 kFreqSumMax = 3800; -const UInt16 kReorderCountStart = 4; -const UInt16 kReorderCount = 50; + +const unsigned kNumLitSelectorBits = 2; +const unsigned kNumLitSelectors = (1 << kNumLitSelectorBits); +const unsigned kNumLitSymbols = 1 << (8 - kNumLitSelectorBits); +const unsigned kNumMatchSelectors = 3; +const unsigned kNumSelectors = kNumLitSelectors + kNumMatchSelectors; +const unsigned kNumSymbolsMax = kNumLitSymbols; // 64 + class CModelDecoder { unsigned NumItems; unsigned ReorderCount; UInt16 Freqs[kNumSymbolsMax + 1]; - Byte Values[kNumSymbolsMax]; + Byte Vals[kNumSymbolsMax]; public: - void Init(unsigned numItems) - { - NumItems = numItems; - ReorderCount = kReorderCountStart; - for (unsigned i = 0; i < numItems; i++) - { - Freqs[i] = (UInt16)(numItems - i); - Values[i] = (Byte)i; - } - Freqs[numItems] = 0; - } - - unsigned Decode(CDecoder *rangeDecoder) - { - UInt32 threshold = rangeDecoder->GetThreshold(Freqs[0]); - unsigned i; - for (i = 1; Freqs[i] > threshold; i++); - rangeDecoder->Decode(Freqs[i], Freqs[i - 1], Freqs[0]); - unsigned res = Values[--i]; - do - Freqs[i] += kUpdateStep; - while (i-- != 0); - - if (Freqs[0] > kFreqSumMax) - { - if (--ReorderCount == 0) - { - ReorderCount = kReorderCount; - for (i = 0; i < NumItems; i++) - Freqs[i] = (UInt16)(((Freqs[i] - Freqs[i + 1]) + 1) >> 1); - for (i = 0; i < NumItems - 1; i++) - for (unsigned j = i + 1; j < NumItems; j++) - if (Freqs[i] < Freqs[j]) - { - UInt16 tmpFreq = Freqs[i]; - Byte tmpVal = Values[i]; - Freqs[i] = Freqs[j]; - Values[i] = Values[j]; - Freqs[j] = tmpFreq; - Values[j] = tmpVal; - } - do - Freqs[i] = (UInt16)(Freqs[i] + Freqs[i + 1]); - while (i-- != 0); - } - else - { - i = NumItems - 1; - do - { - Freqs[i] >>= 1; - if (Freqs[i] <= Freqs[i + 1]) - Freqs[i] = (UInt16)(Freqs[i + 1] + 1); - } - while (i-- != 0); - } - } - return res; - } + void Init(unsigned numItems); + unsigned Decode(CRangeDecoder *rc); }; -} class CDecoder: - public ICompressCoder, - // public ICompressSetInStream, - // public ICompressSetOutStreamSize, + public IUnknown, public CMyUnknownImp { - CLzOutWindow _outWindowStream; - // CMyComPtr<ISequentialInStream> m_InStreamRef; - NRangeCoder::CDecoder _rangeDecoder; + CLzOutWindow _outWindow; + unsigned _numDictBits; - UInt64 _outSize; - int _remainLen; // -1 means end of stream. // -2 means need Init - UInt32 _rep0; + CModelDecoder m_Selector; + CModelDecoder m_Literals[kNumLitSelectors]; + CModelDecoder m_PosSlot[kNumMatchSelectors]; + CModelDecoder m_LenSlot; - int _numDictBits; - bool _keepHistory; - - NRangeCoder::CModelDecoder m_Selector; - NRangeCoder::CModelDecoder m_Literals[kNumLitSelectors]; - NRangeCoder::CModelDecoder m_PosSlot[kNumMatchSelectors]; - NRangeCoder::CModelDecoder m_LenSlot; void Init(); - HRESULT CodeSpec(UInt32 size); + HRESULT CodeSpec(const Byte *inData, size_t inSize, UInt32 outSize); public: MY_UNKNOWN_IMP - /* - MY_UNKNOWN_IMP2( - ICompressSetInStream, - ICompressSetOutStreamSize) - void ReleaseStreams() - { - _outWindowStream.ReleaseStream(); - ReleaseInStream(); - } - */ - - class CDecoderFlusher - { - CDecoder *_decoder; - public: - bool NeedFlush; - CDecoderFlusher(CDecoder *decoder): _decoder(decoder), NeedFlush(true) {} - ~CDecoderFlusher() - { - if (NeedFlush) - _decoder->Flush(); - // _decoder->ReleaseStreams(); - } - }; + HRESULT Code(const Byte *inData, size_t inSize, + ISequentialOutStream *outStream, UInt32 outSize, + bool keepHistory); - HRESULT Flush() { return _outWindowStream.Flush(); } - - HRESULT CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream, - const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress); + HRESULT SetParams(unsigned numDictBits); - STDMETHOD(Code)(ISequentialInStream *inStream, ISequentialOutStream *outStream, - const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress); - - // STDMETHOD(SetInStream)(ISequentialInStream *inStream); - // STDMETHOD(ReleaseInStream)(); - STDMETHOD(SetOutStreamSize)(const UInt64 *outSize); - - HRESULT SetParams(int numDictBits); - void SetKeepHistory(bool keepHistory) { _keepHistory = keepHistory; } - CDecoder(): _keepHistory(false) {} + CDecoder(): _numDictBits(0) {} virtual ~CDecoder() {} }; diff --git a/CPP/7zip/Compress/Rar2Decoder.cpp b/CPP/7zip/Compress/Rar2Decoder.cpp index 5082ded3..4d1bd6b2 100644 --- a/CPP/7zip/Compress/Rar2Decoder.cpp +++ b/CPP/7zip/Compress/Rar2Decoder.cpp @@ -122,21 +122,21 @@ bool CDecoder::ReadTables(void) unsigned i; for (i = 0; i < kLevelTableSize; i++) levelLevels[i] = (Byte)ReadBits(4); - RIF(m_LevelDecoder.SetCodeLengths(levelLevels)); + RIF(m_LevelDecoder.Build(levelLevels)); i = 0; while (i < numLevels) { - UInt32 number = m_LevelDecoder.DecodeSymbol(&m_InBitStream); - if (number < kTableDirectLevels) + UInt32 sym = m_LevelDecoder.Decode(&m_InBitStream); + if (sym < kTableDirectLevels) { - newLevels[i] = (Byte)((number + m_LastLevels[i]) & kLevelMask); + newLevels[i] = (Byte)((sym + m_LastLevels[i]) & kLevelMask); i++; } else { - if (number == kTableLevelRepNumber) + if (sym == kTableLevelRepNumber) { unsigned t = ReadBits(2) + 3; for (unsigned reps = t; reps > 0 && i < numLevels; reps--, i++) @@ -145,9 +145,9 @@ bool CDecoder::ReadTables(void) else { unsigned num; - if (number == kTableLevel0Number) + if (sym == kTableLevel0Number) num = ReadBits(3) + 3; - else if (number == kTableLevel0Number2) + else if (sym == kTableLevel0Number2) num = ReadBits(7) + 11; else return false; @@ -160,13 +160,13 @@ bool CDecoder::ReadTables(void) if (m_AudioMode) for (i = 0; i < m_NumChannels; i++) { - RIF(m_MMDecoders[i].SetCodeLengths(&newLevels[i * kMMTableSize])); + RIF(m_MMDecoders[i].Build(&newLevels[i * kMMTableSize])); } else { - RIF(m_MainDecoder.SetCodeLengths(&newLevels[0])); - RIF(m_DistDecoder.SetCodeLengths(&newLevels[kMainTableSize])); - RIF(m_LenDecoder.SetCodeLengths(&newLevels[kMainTableSize + kDistTableSize])); + RIF(m_MainDecoder.Build(&newLevels[0])); + RIF(m_DistDecoder.Build(&newLevels[kMainTableSize])); + RIF(m_LenDecoder.Build(&newLevels[kMainTableSize + kDistTableSize])); } memcpy(m_LastLevels, newLevels, kMaxTableSize); @@ -182,7 +182,7 @@ bool CDecoder::ReadLastTables() // if (m_InBitStream.GetProcessedSize() + 2 <= m_PackSize) // test it: probably incorrect; if (m_AudioMode) { - UInt32 symbol = m_MMDecoders[m_MmFilter.CurrentChannel].DecodeSymbol(&m_InBitStream); + UInt32 symbol = m_MMDecoders[m_MmFilter.CurrentChannel].Decode(&m_InBitStream); if (symbol == 256) return ReadTables(); if (symbol >= kMMTableSize) @@ -190,10 +190,10 @@ bool CDecoder::ReadLastTables() } else { - UInt32 number = m_MainDecoder.DecodeSymbol(&m_InBitStream); - if (number == kReadTableNumber) + UInt32 sym = m_MainDecoder.Decode(&m_InBitStream); + if (sym == kReadTableNumber) return ReadTables(); - if (number >= kMainTableSize) + if (sym >= kMainTableSize) return false; } return true; @@ -216,7 +216,7 @@ bool CDecoder::DecodeMm(UInt32 pos) { while (pos-- > 0) { - UInt32 symbol = m_MMDecoders[m_MmFilter.CurrentChannel].DecodeSymbol(&m_InBitStream); + UInt32 symbol = m_MMDecoders[m_MmFilter.CurrentChannel].Decode(&m_InBitStream); if (symbol == 256) return true; if (symbol >= kMMTableSize) @@ -238,23 +238,23 @@ bool CDecoder::DecodeLz(Int32 pos) { while (pos > 0) { - UInt32 number = m_MainDecoder.DecodeSymbol(&m_InBitStream); + UInt32 sym = m_MainDecoder.Decode(&m_InBitStream); UInt32 length, distance; - if (number < 256) + if (sym < 256) { - m_OutWindowStream.PutByte(Byte(number)); + m_OutWindowStream.PutByte(Byte(sym)); pos--; continue; } - else if (number >= kMatchNumber) + else if (sym >= kMatchNumber) { - number -= kMatchNumber; - length = kNormalMatchMinLen + UInt32(kLenStart[number]) + - m_InBitStream.ReadBits(kLenDirectBits[number]); - number = m_DistDecoder.DecodeSymbol(&m_InBitStream); - if (number >= kDistTableSize) + sym -= kMatchNumber; + length = kNormalMatchMinLen + UInt32(kLenStart[sym]) + + m_InBitStream.ReadBits(kLenDirectBits[sym]); + sym = m_DistDecoder.Decode(&m_InBitStream); + if (sym >= kDistTableSize) return false; - distance = kDistStart[number] + m_InBitStream.ReadBits(kDistDirectBits[number]); + distance = kDistStart[sym] + m_InBitStream.ReadBits(kDistDirectBits[sym]); if (distance >= kDistLimit3) { length += 2 - ((distance - kDistLimit4) >> 31); @@ -263,20 +263,20 @@ bool CDecoder::DecodeLz(Int32 pos) // length++; } } - else if (number == kRepBothNumber) + else if (sym == kRepBothNumber) { length = m_LastLength; if (length == 0) return false; distance = m_RepDists[(m_RepDistPtr + 4 - 1) & 3]; } - else if (number < kLen2Number) + else if (sym < kLen2Number) { - distance = m_RepDists[(m_RepDistPtr - (number - kRepNumber + 1)) & 3]; - number = m_LenDecoder.DecodeSymbol(&m_InBitStream); - if (number >= kLenTableSize) + distance = m_RepDists[(m_RepDistPtr - (sym - kRepNumber + 1)) & 3]; + sym = m_LenDecoder.Decode(&m_InBitStream); + if (sym >= kLenTableSize) return false; - length = 2 + kLenStart[number] + m_InBitStream.ReadBits(kLenDirectBits[number]); + length = 2 + kLenStart[sym] + m_InBitStream.ReadBits(kLenDirectBits[sym]); if (distance >= kDistLimit2) { length++; @@ -289,14 +289,14 @@ bool CDecoder::DecodeLz(Int32 pos) } } } - else if (number < kReadTableNumber) + else if (sym < kReadTableNumber) { - number -= kLen2Number; - distance = kLen2DistStarts[number] + - m_InBitStream.ReadBits(kLen2DistDirectBits[number]); + sym -= kLen2Number; + distance = kLen2DistStarts[sym] + + m_InBitStream.ReadBits(kLen2DistDirectBits[sym]); length = 2; } - else if (number == kReadTableNumber) + else if (sym == kReadTableNumber) return true; else return false; diff --git a/CPP/7zip/Compress/Rar3Decoder.cpp b/CPP/7zip/Compress/Rar3Decoder.cpp index 81eb8285..496400a4 100644 --- a/CPP/7zip/Compress/Rar3Decoder.cpp +++ b/CPP/7zip/Compress/Rar3Decoder.cpp @@ -568,26 +568,26 @@ HRESULT CDecoder::ReadTables(bool &keepDecompressing) } levelLevels[i] = (Byte)length; } - RIF(m_LevelDecoder.SetCodeLengths(levelLevels)); + RIF(m_LevelDecoder.Build(levelLevels)); i = 0; while (i < kTablesSizesSum) { - UInt32 number = m_LevelDecoder.DecodeSymbol(&m_InBitStream.BitDecoder); - if (number < 16) + UInt32 sym = m_LevelDecoder.Decode(&m_InBitStream.BitDecoder); + if (sym < 16) { - newLevels[i] = Byte((number + m_LastLevels[i]) & 15); + newLevels[i] = Byte((sym + m_LastLevels[i]) & 15); i++; } - else if (number > kLevelTableSize) + else if (sym > kLevelTableSize) return S_FALSE; else { int num; - if (((number - 16) & 1) == 0) + if (((sym - 16) & 1) == 0) num = ReadBits(3) + 3; else num = ReadBits(7) + 11; - if (number < 18) + if (sym < 18) { if (i == 0) return S_FALSE; @@ -612,10 +612,10 @@ HRESULT CDecoder::ReadTables(bool &keepDecompressing) } */ - RIF(m_MainDecoder.SetCodeLengths(&newLevels[0])); - RIF(m_DistDecoder.SetCodeLengths(&newLevels[kMainTableSize])); - RIF(m_AlignDecoder.SetCodeLengths(&newLevels[kMainTableSize + kDistTableSize])); - RIF(m_LenDecoder.SetCodeLengths(&newLevels[kMainTableSize + kDistTableSize + kAlignTableSize])); + RIF(m_MainDecoder.Build(&newLevels[0])); + RIF(m_DistDecoder.Build(&newLevels[kMainTableSize])); + RIF(m_AlignDecoder.Build(&newLevels[kMainTableSize + kDistTableSize])); + RIF(m_LenDecoder.Build(&newLevels[kMainTableSize + kDistTableSize + kAlignTableSize])); memcpy(m_LastLevels, newLevels, kTablesSizesSum); return S_OK; @@ -687,38 +687,38 @@ HRESULT CDecoder::DecodeLZ(bool &keepDecompressing) if (InputEofError_Fast()) return S_FALSE; - UInt32 number = m_MainDecoder.DecodeSymbol(&m_InBitStream.BitDecoder); - if (number < 256) + UInt32 sym = m_MainDecoder.Decode(&m_InBitStream.BitDecoder); + if (sym < 256) { - PutByte((Byte)number); + PutByte((Byte)sym); continue; } - else if (number == kSymbolReadTable) + else if (sym == kSymbolReadTable) { RINOK(ReadEndOfBlock(keepDecompressing)); break; } - else if (number == 257) + else if (sym == 257) { if (!ReadVmCodeLZ()) return S_FALSE; continue; } - else if (number == 258) + else if (sym == 258) { if (length == 0) return S_FALSE; } - else if (number < kSymbolRep + 4) + else if (sym < kSymbolRep + 4) { - if (number != kSymbolRep) + if (sym != kSymbolRep) { UInt32 distance; - if (number == kSymbolRep + 1) + if (sym == kSymbolRep + 1) distance = rep1; else { - if (number == kSymbolRep + 2) + if (sym == kSymbolRep + 2) distance = rep2; else { @@ -731,32 +731,32 @@ HRESULT CDecoder::DecodeLZ(bool &keepDecompressing) rep0 = distance; } - UInt32 number = m_LenDecoder.DecodeSymbol(&m_InBitStream.BitDecoder); - if (number >= kLenTableSize) + UInt32 sym = m_LenDecoder.Decode(&m_InBitStream.BitDecoder); + if (sym >= kLenTableSize) return S_FALSE; - length = 2 + kLenStart[number] + m_InBitStream.BitDecoder.ReadBits(kLenDirectBits[number]); + length = 2 + kLenStart[sym] + m_InBitStream.BitDecoder.ReadBits(kLenDirectBits[sym]); } else { rep3 = rep2; rep2 = rep1; rep1 = rep0; - if (number < 271) + if (sym < 271) { - number -= 263; - rep0 = kLen2DistStarts[number] + m_InBitStream.BitDecoder.ReadBits(kLen2DistDirectBits[number]); + sym -= 263; + rep0 = kLen2DistStarts[sym] + m_InBitStream.BitDecoder.ReadBits(kLen2DistDirectBits[sym]); length = 2; } - else if (number < 299) + else if (sym < 299) { - number -= 271; - length = kNormalMatchMinLen + (UInt32)kLenStart[number] + m_InBitStream.BitDecoder.ReadBits(kLenDirectBits[number]); - UInt32 number = m_DistDecoder.DecodeSymbol(&m_InBitStream.BitDecoder); - if (number >= kDistTableSize) + sym -= 271; + length = kNormalMatchMinLen + (UInt32)kLenStart[sym] + m_InBitStream.BitDecoder.ReadBits(kLenDirectBits[sym]); + UInt32 sym = m_DistDecoder.Decode(&m_InBitStream.BitDecoder); + if (sym >= kDistTableSize) return S_FALSE; - rep0 = kDistStart[number]; - int numBits = kDistDirectBits[number]; - if (number >= (kNumAlignBits * 2) + 2) + rep0 = kDistStart[sym]; + int numBits = kDistDirectBits[sym]; + if (sym >= (kNumAlignBits * 2) + 2) { if (numBits > kNumAlignBits) rep0 += (m_InBitStream.BitDecoder.ReadBits(numBits - kNumAlignBits) << kNumAlignBits); @@ -767,13 +767,13 @@ HRESULT CDecoder::DecodeLZ(bool &keepDecompressing) } else { - UInt32 number = m_AlignDecoder.DecodeSymbol(&m_InBitStream.BitDecoder); - if (number < (1 << kNumAlignBits)) + UInt32 sym = m_AlignDecoder.Decode(&m_InBitStream.BitDecoder); + if (sym < (1 << kNumAlignBits)) { - rep0 += number; - PrevAlignBits = number; + rep0 += sym; + PrevAlignBits = sym; } - else if (number == (1 << kNumAlignBits)) + else if (sym == (1 << kNumAlignBits)) { PrevAlignCount = kNumAlignReps; rep0 += PrevAlignBits; diff --git a/CPP/7zip/Compress/Rar5Decoder.cpp b/CPP/7zip/Compress/Rar5Decoder.cpp index 9e3ff3e4..19b40f39 100644 --- a/CPP/7zip/Compress/Rar5Decoder.cpp +++ b/CPP/7zip/Compress/Rar5Decoder.cpp @@ -304,6 +304,7 @@ HRESULT CDecoder::AddFilter(CBitDecoder &_bitStream) // if (f.Size > ((UInt32)1 << 16)) _unsupportedFilter = true; f.Type = (Byte)_bitStream.ReadBits9fix(3); + f.Channels = 0; if (f.Type == FILTER_DELTA) f.Channels = (Byte)(_bitStream.ReadBits9fix(5) + 1); f.Start = _lzSize + blockStart; @@ -408,7 +409,7 @@ HRESULT CDecoder::ReadTables(CBitDecoder &_bitStream) if (_bitStream.IsBlockOverRead()) return S_FALSE; - RIF(m_LevelDecoder.SetCodeLengths(lens2)); + RIF(m_LevelDecoder.Build(lens2)); } Byte lens[kTablesSizesSum]; @@ -424,7 +425,7 @@ HRESULT CDecoder::ReadTables(CBitDecoder &_bitStream) return S_FALSE; } - UInt32 sym = m_LevelDecoder.DecodeSymbol(&_bitStream); + UInt32 sym = m_LevelDecoder.Decode(&_bitStream); if (sym < 16) lens[i++] = (Byte)sym; @@ -466,10 +467,10 @@ HRESULT CDecoder::ReadTables(CBitDecoder &_bitStream) if (_bitStream.InputEofError()) return S_FALSE; - RIF(m_MainDecoder.SetCodeLengths(&lens[0])); - RIF(m_DistDecoder.SetCodeLengths(&lens[kMainTableSize])); - RIF(m_AlignDecoder.SetCodeLengths(&lens[kMainTableSize + kDistTableSize])); - RIF(m_LenDecoder.SetCodeLengths(&lens[kMainTableSize + kDistTableSize + kAlignTableSize])); + RIF(m_MainDecoder.Build(&lens[0])); + RIF(m_DistDecoder.Build(&lens[kMainTableSize])); + RIF(m_AlignDecoder.Build(&lens[kMainTableSize + kDistTableSize])); + RIF(m_LenDecoder.Build(&lens[kMainTableSize + kDistTableSize + kAlignTableSize])); _useAlignBits = false; // _useAlignBits = true; @@ -601,7 +602,7 @@ HRESULT CDecoder::DecodeLZ() } } - UInt32 sym = m_MainDecoder.DecodeSymbol(&_bitStream); + UInt32 sym = m_MainDecoder.Decode(&_bitStream); if (sym < 256) { @@ -638,7 +639,7 @@ HRESULT CDecoder::DecodeLZ() rep0 = dist; } - UInt32 sym = m_LenDecoder.DecodeSymbol(&_bitStream); + UInt32 sym = m_LenDecoder.Decode(&_bitStream); if (sym >= kLenTableSize) break; // return S_FALSE; len = SlotToLen(_bitStream, sym); @@ -669,7 +670,7 @@ HRESULT CDecoder::DecodeLZ() _reps[1] = rep0; len = SlotToLen(_bitStream, sym - (kSymbolRep + kNumReps)); - rep0 = m_DistDecoder.DecodeSymbol(&_bitStream); + rep0 = m_DistDecoder.Decode(&_bitStream); if (rep0 >= 4) { @@ -690,7 +691,7 @@ HRESULT CDecoder::DecodeLZ() { // if (numBits > kNumAlignBits) rep0 += (_bitStream.ReadBits32(numBits - kNumAlignBits) << kNumAlignBits); - UInt32 a = m_AlignDecoder.DecodeSymbol(&_bitStream); + UInt32 a = m_AlignDecoder.Decode(&_bitStream); if (a >= kAlignTableSize) break; // return S_FALSE; rep0 += a; diff --git a/CPP/7zip/Compress/XpressDecoder.cpp b/CPP/7zip/Compress/XpressDecoder.cpp new file mode 100644 index 00000000..a4d45335 --- /dev/null +++ b/CPP/7zip/Compress/XpressDecoder.cpp @@ -0,0 +1,129 @@ +// XpressDecoder.cpp + +#include "StdAfx.h" + +// #include <stdio.h> + +#include "../../../C/CpuArch.h" + +#include "HuffmanDecoder.h" + +namespace NCompress { +namespace NXpress { + +struct CBitStream +{ + UInt32 Value; + unsigned BitPos; + + UInt32 GetValue(unsigned numBits) const + { + return (Value >> (BitPos - numBits)) & ((1 << numBits) - 1); + } + + void MovePos(unsigned numBits) + { + BitPos -= numBits; + } +}; + +#define BIT_STREAM_NORMALIZE \ + if (bs.BitPos < 16) { \ + if (in >= lim) return S_FALSE; \ + bs.Value = (bs.Value << 16) | GetUi16(in); \ + in += 2; bs.BitPos += 16; } + +const unsigned kNumHuffBits = 15; +const unsigned kNumLenSlots = 16; +const unsigned kNumPosSlots = 16; +const unsigned kNumSyms = 256 + kNumPosSlots * kNumLenSlots; + +HRESULT Decode(const Byte *in, size_t inSize, Byte *out, size_t outSize) +{ + NCompress::NHuffman::CDecoder<kNumHuffBits, kNumSyms> huff; + + if (inSize < kNumSyms / 2 + 4) + return S_FALSE; + { + Byte levels[kNumSyms]; + for (unsigned i = 0; i < kNumSyms / 2; i++) + { + Byte b = in[i]; + levels[i * 2] = (Byte)(b & 0xF); + levels[i * 2 + 1] = (Byte)(b >> 4); + } + if (!huff.BuildFull(levels)) + return S_FALSE; + } + + + CBitStream bs; + + const Byte *lim = in + inSize - 1; + + in += kNumSyms / 2; + bs.Value = (GetUi16(in) << 16) | GetUi16(in + 2); + in += 4; + bs.BitPos = 32; + + size_t pos = 0; + + for (;;) + { + // printf("\n%d", pos); + UInt32 sym = huff.DecodeFull(&bs); + // printf(" sym = %d", sym); + BIT_STREAM_NORMALIZE + + if (pos >= outSize) + return (sym == 256 && in == lim + 1) ? S_OK : S_FALSE; + + if (sym < 256) + out[pos++] = (Byte)sym; + else + { + sym -= 256; + UInt32 dist = sym / kNumLenSlots; + UInt32 len = sym & (kNumLenSlots - 1); + + if (len == kNumLenSlots - 1) + { + if (in > lim) + return S_FALSE; + len = *in++; + if (len == 0xFF) + { + if (in >= lim) + return S_FALSE; + len = GetUi16(in); + in += 2; + } + else + len += kNumLenSlots - 1; + } + + bs.BitPos -= dist; + dist = (UInt32)1 << dist; + dist += ((bs.Value >> bs.BitPos) & (dist - 1)); + + BIT_STREAM_NORMALIZE + + if (len > outSize - pos) + return S_FALSE; + if (dist > pos) + return S_FALSE; + + Byte *dest = out + pos; + const Byte *src = dest - dist; + pos += len + 3; + len += 1; + *dest++ = *src++; + *dest++ = *src++; + do + *dest++ = *src++; + while (--len); + } + } +} + +}} diff --git a/CPP/7zip/Compress/XpressDecoder.h b/CPP/7zip/Compress/XpressDecoder.h new file mode 100644 index 00000000..cada85bf --- /dev/null +++ b/CPP/7zip/Compress/XpressDecoder.h @@ -0,0 +1,13 @@ +// XpressDecoder.h + +#ifndef __XPRESS_DECODER_H +#define __XPRESS_DECODER_H + +namespace NCompress { +namespace NXpress { + +HRESULT Decode(const Byte *in, size_t inSize, Byte *out, size_t outSize); + +}} + +#endif |