Mercurial > vba-linux

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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
importing src directory
author Robert McIntyre <rlm@mit.edu>
date Sat, 03 Mar 2012 10:31:27 -0600
parents
children
rev   line source
rlm@1 1 // Implode/Decoder.cpp
rlm@1 2
rlm@1 3 #include "StdAfx.h"
rlm@1 4
rlm@1 5 #include "ImplodeDecoder.h"
rlm@1 6 #include "Common/Defs.h"
rlm@1 7
rlm@1 8 namespace NCompress {
rlm@1 9 namespace NImplode {
rlm@1 10 namespace NDecoder {
rlm@1 11
rlm@1 12 class CException
rlm@1 13 {
rlm@1 14 public:
rlm@1 15 enum ECauseType
rlm@1 16 {
rlm@1 17 kData
rlm@1 18 } m_Cause;
rlm@1 19 CException(ECauseType cause): m_Cause(cause) {}
rlm@1 20 };
rlm@1 21
rlm@1 22 static const int kNumDistanceLowDirectBitsForBigDict = 7;
rlm@1 23 static const int kNumDistanceLowDirectBitsForSmallDict = 6;
rlm@1 24
rlm@1 25 static const int kNumBitsInByte = 8;
rlm@1 26
rlm@1 27 // static const int kLevelStructuresNumberFieldSize = kNumBitsInByte;
rlm@1 28 static const int kLevelStructuresNumberAdditionalValue = 1;
rlm@1 29
rlm@1 30 static const int kNumLevelStructureLevelBits = 4;
rlm@1 31 static const int kLevelStructureLevelAdditionalValue = 1;
rlm@1 32
rlm@1 33 static const int kNumLevelStructureRepNumberBits = 4;
rlm@1 34 static const int kLevelStructureRepNumberAdditionalValue = 1;
rlm@1 35
rlm@1 36
rlm@1 37 static const int kLiteralTableSize = (1 << kNumBitsInByte);
rlm@1 38 static const int kDistanceTableSize = 64;
rlm@1 39 static const int kLengthTableSize = 64;
rlm@1 40
rlm@1 41 static const UInt32 kHistorySize =
rlm@1 42 (1 << MyMax(kNumDistanceLowDirectBitsForBigDict,
rlm@1 43 kNumDistanceLowDirectBitsForSmallDict)) *
rlm@1 44 kDistanceTableSize; // = 8 KB;
rlm@1 45
rlm@1 46 static const int kNumAdditionalLengthBits = 8;
rlm@1 47
rlm@1 48 static const UInt32 kMatchMinLenWhenLiteralsOn = 3;
rlm@1 49 static const UInt32 kMatchMinLenWhenLiteralsOff = 2;
rlm@1 50
rlm@1 51 static const UInt32 kMatchMinLenMax = MyMax(kMatchMinLenWhenLiteralsOn,
rlm@1 52 kMatchMinLenWhenLiteralsOff); // 3
rlm@1 53
rlm@1 54 // static const UInt32 kMatchMaxLenMax = kMatchMinLenMax + (kLengthTableSize - 1) + (1 << kNumAdditionalLengthBits) - 1; // or 2
rlm@1 55
rlm@1 56 enum
rlm@1 57 {
rlm@1 58 kMatchId = 0,
rlm@1 59 kLiteralId = 1
rlm@1 60 };
rlm@1 61
rlm@1 62
rlm@1 63 CCoder::CCoder():
rlm@1 64 m_LiteralDecoder(kLiteralTableSize),
rlm@1 65 m_LengthDecoder(kLengthTableSize),
rlm@1 66 m_DistanceDecoder(kDistanceTableSize)
rlm@1 67 {
rlm@1 68 }
rlm@1 69
rlm@1 70 void CCoder::ReleaseStreams()
rlm@1 71 {
rlm@1 72 m_OutWindowStream.ReleaseStream();
rlm@1 73 m_InBitStream.ReleaseStream();
rlm@1 74 }
rlm@1 75
rlm@1 76 bool CCoder::ReadLevelItems(NImplode::NHuffman::CDecoder &decoder,
rlm@1 77 Byte *levels, int numLevelItems)
rlm@1 78 {
rlm@1 79 int numCodedStructures = m_InBitStream.ReadBits(kNumBitsInByte) +
rlm@1 80 kLevelStructuresNumberAdditionalValue;
rlm@1 81 int currentIndex = 0;
rlm@1 82 for(int i = 0; i < numCodedStructures; i++)
rlm@1 83 {
rlm@1 84 int level = m_InBitStream.ReadBits(kNumLevelStructureLevelBits) +
rlm@1 85 kLevelStructureLevelAdditionalValue;
rlm@1 86 int rep = m_InBitStream.ReadBits(kNumLevelStructureRepNumberBits) +
rlm@1 87 kLevelStructureRepNumberAdditionalValue;
rlm@1 88 if (currentIndex + rep > numLevelItems)
rlm@1 89 throw CException(CException::kData);
rlm@1 90 for(int j = 0; j < rep; j++)
rlm@1 91 levels[currentIndex++] = (Byte)level;
rlm@1 92 }
rlm@1 93 if (currentIndex != numLevelItems)
rlm@1 94 return false;
rlm@1 95 return decoder.SetCodeLengths(levels);
rlm@1 96 }
rlm@1 97
rlm@1 98
rlm@1 99 bool CCoder::ReadTables(void)
rlm@1 100 {
rlm@1 101 if (m_LiteralsOn)
rlm@1 102 {
rlm@1 103 Byte literalLevels[kLiteralTableSize];
rlm@1 104 if (!ReadLevelItems(m_LiteralDecoder, literalLevels, kLiteralTableSize))
rlm@1 105 return false;
rlm@1 106 }
rlm@1 107
rlm@1 108 Byte lengthLevels[kLengthTableSize];
rlm@1 109 if (!ReadLevelItems(m_LengthDecoder, lengthLevels, kLengthTableSize))
rlm@1 110 return false;
rlm@1 111
rlm@1 112 Byte distanceLevels[kDistanceTableSize];
rlm@1 113 return ReadLevelItems(m_DistanceDecoder, distanceLevels, kDistanceTableSize);
rlm@1 114 }
rlm@1 115
rlm@1 116 class CCoderReleaser
rlm@1 117 {
rlm@1 118 CCoder *m_Coder;
rlm@1 119 public:
rlm@1 120 CCoderReleaser(CCoder *coder): m_Coder(coder) {}
rlm@1 121 ~CCoderReleaser() { m_Coder->ReleaseStreams(); }
rlm@1 122 };
rlm@1 123
rlm@1 124 HRESULT CCoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream,
rlm@1 125 const UInt64 * /* inSize */, const UInt64 *outSize, ICompressProgressInfo *progress)
rlm@1 126 {
rlm@1 127 if (!m_InBitStream.Create(1 << 20))
rlm@1 128 return E_OUTOFMEMORY;
rlm@1 129 if (!m_OutWindowStream.Create(kHistorySize))
rlm@1 130 return E_OUTOFMEMORY;
rlm@1 131 if (outSize == NULL)
rlm@1 132 return E_INVALIDARG;
rlm@1 133 UInt64 pos = 0, unPackSize = *outSize;
rlm@1 134
rlm@1 135 m_OutWindowStream.SetStream(outStream);
rlm@1 136 m_OutWindowStream.Init(false);
rlm@1 137 m_InBitStream.SetStream(inStream);
rlm@1 138 m_InBitStream.Init();
rlm@1 139 CCoderReleaser coderReleaser(this);
rlm@1 140
rlm@1 141 if (!ReadTables())
rlm@1 142 return S_FALSE;
rlm@1 143
rlm@1 144 while(pos < unPackSize)
rlm@1 145 {
rlm@1 146 if (progress != NULL && pos % (1 << 16) == 0)
rlm@1 147 {
rlm@1 148 UInt64 packSize = m_InBitStream.GetProcessedSize();
rlm@1 149 RINOK(progress->SetRatioInfo(&packSize, &pos));
rlm@1 150 }
rlm@1 151 if(m_InBitStream.ReadBits(1) == kMatchId) // match
rlm@1 152 {
rlm@1 153 UInt32 lowDistBits = m_InBitStream.ReadBits(m_NumDistanceLowDirectBits);
rlm@1 154 UInt32 distance = m_DistanceDecoder.DecodeSymbol(&m_InBitStream);
rlm@1 155 if (distance >= kDistanceTableSize)
rlm@1 156 return S_FALSE;
rlm@1 157 distance = (distance << m_NumDistanceLowDirectBits) + lowDistBits;
rlm@1 158 UInt32 lengthSymbol = m_LengthDecoder.DecodeSymbol(&m_InBitStream);
rlm@1 159 if (lengthSymbol >= kLengthTableSize)
rlm@1 160 return S_FALSE;
rlm@1 161 UInt32 length = lengthSymbol + m_MinMatchLength;
rlm@1 162 if (lengthSymbol == kLengthTableSize - 1) // special symbol = 63
rlm@1 163 length += m_InBitStream.ReadBits(kNumAdditionalLengthBits);
rlm@1 164 while(distance >= pos && length > 0)
rlm@1 165 {
rlm@1 166 m_OutWindowStream.PutByte(0);
rlm@1 167 pos++;
rlm@1 168 length--;
rlm@1 169 }
rlm@1 170 if (length > 0)
rlm@1 171 m_OutWindowStream.CopyBlock(distance, length);
rlm@1 172 pos += length;
rlm@1 173 }
rlm@1 174 else
rlm@1 175 {
rlm@1 176 Byte b;
rlm@1 177 if (m_LiteralsOn)
rlm@1 178 {
rlm@1 179 UInt32 temp = m_LiteralDecoder.DecodeSymbol(&m_InBitStream);
rlm@1 180 if (temp >= kLiteralTableSize)
rlm@1 181 return S_FALSE;
rlm@1 182 b = (Byte)temp;
rlm@1 183 }
rlm@1 184 else
rlm@1 185 b = (Byte)m_InBitStream.ReadBits(kNumBitsInByte);
rlm@1 186 m_OutWindowStream.PutByte(b);
rlm@1 187 pos++;
rlm@1 188 }
rlm@1 189 }
rlm@1 190 if (pos > unPackSize)
rlm@1 191 return S_FALSE;
rlm@1 192 return m_OutWindowStream.Flush();
rlm@1 193 }
rlm@1 194
rlm@1 195 STDMETHODIMP CCoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,
rlm@1 196 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress)
rlm@1 197 {
rlm@1 198 try { return CodeReal(inStream, outStream, inSize, outSize, progress); }
rlm@1 199 catch(const CLzOutWindowException &e) { return e.ErrorCode; }
rlm@1 200 catch(...) { return S_FALSE; }
rlm@1 201 }
rlm@1 202
rlm@1 203 STDMETHODIMP CCoder::SetDecoderProperties2(const Byte *data, UInt32 size)
rlm@1 204 {
rlm@1 205 if (size < 1)
rlm@1 206 return E_INVALIDARG;
rlm@1 207 Byte flag = data[0];
rlm@1 208 m_BigDictionaryOn = ((flag & 2) != 0);
rlm@1 209 m_NumDistanceLowDirectBits = m_BigDictionaryOn ?
rlm@1 210 kNumDistanceLowDirectBitsForBigDict:
rlm@1 211 kNumDistanceLowDirectBitsForSmallDict;
rlm@1 212 m_LiteralsOn = ((flag & 4) != 0);
rlm@1 213 m_MinMatchLength = m_LiteralsOn ?
rlm@1 214 kMatchMinLenWhenLiteralsOn :
rlm@1 215 kMatchMinLenWhenLiteralsOff;
rlm@1 216 return S_OK;
rlm@1 217 }
rlm@1 218
rlm@1 219 }}}