1 // ImplodeDecoder.cpp
2
3 #include "StdAfx.h"
4
5 #include "../../Common/Defs.h"
6
7 #include "ImplodeDecoder.h"
8
9 namespace NCompress {
10 namespace NImplode {
11 namespace NDecoder {
12
Build(const Byte * lens,unsigned numSymbols)13 bool CHuffmanDecoder::Build(const Byte *lens, unsigned numSymbols) throw()
14 {
15 unsigned counts[kNumHuffmanBits + 1];
16
17 unsigned i;
18 for (i = 0; i <= kNumHuffmanBits; i++)
19 counts[i] = 0;
20
21 unsigned sym;
22 for (sym = 0; sym < numSymbols; sym++)
23 counts[lens[sym]]++;
24
25 const UInt32 kMaxValue = (UInt32)1 << kNumHuffmanBits;
26
27 // _limits[0] = kMaxValue;
28
29 UInt32 startPos = kMaxValue;
30 UInt32 sum = 0;
31
32 for (i = 1; i <= kNumHuffmanBits; i++)
33 {
34 const UInt32 cnt = counts[i];
35 const UInt32 range = cnt << (kNumHuffmanBits - i);
36 if (startPos < range)
37 return false;
38 startPos -= range;
39 _limits[i] = startPos;
40 _poses[i] = sum;
41 sum += cnt;
42 counts[i] = sum;
43 }
44
45 // counts[0] += sum;
46
47 if (startPos != 0)
48 return false;
49
50 for (sym = 0; sym < numSymbols; sym++)
51 {
52 unsigned len = lens[sym];
53 if (len != 0)
54 _symbols[--counts[len]] = (Byte)sym;
55 }
56
57 return true;
58 }
59
60
Decode(CInBit * inStream) const61 UInt32 CHuffmanDecoder::Decode(CInBit *inStream) const throw()
62 {
63 UInt32 val = inStream->GetValue(kNumHuffmanBits);
64 unsigned numBits;
65 for (numBits = 1; val < _limits[numBits]; numBits++);
66 UInt32 sym = _symbols[_poses[numBits] + ((val - _limits[numBits]) >> (kNumHuffmanBits - numBits))];
67 inStream->MovePos(numBits);
68 return sym;
69 }
70
71
72
73 static const unsigned kNumLenDirectBits = 8;
74
75 static const unsigned kNumDistDirectBitsSmall = 6;
76 static const unsigned kNumDistDirectBitsBig = 7;
77
78 static const unsigned kLitTableSize = (1 << 8);
79 static const unsigned kDistTableSize = 64;
80 static const unsigned kLenTableSize = 64;
81
82 static const UInt32 kHistorySize = (1 << kNumDistDirectBitsBig) * kDistTableSize; // 8 KB
83
84
CCoder()85 CCoder::CCoder():
86 _flags(0),
87 _fullStreamMode(false)
88 {}
89
90
BuildHuff(CHuffmanDecoder & decoder,unsigned numSymbols)91 bool CCoder::BuildHuff(CHuffmanDecoder &decoder, unsigned numSymbols)
92 {
93 Byte levels[kMaxHuffTableSize];
94 unsigned numRecords = (unsigned)_inBitStream.ReadAlignedByte() + 1;
95 unsigned index = 0;
96 do
97 {
98 unsigned b = (unsigned)_inBitStream.ReadAlignedByte();
99 Byte level = (Byte)((b & 0xF) + 1);
100 unsigned rep = ((unsigned)b >> 4) + 1;
101 if (index + rep > numSymbols)
102 return false;
103 for (unsigned j = 0; j < rep; j++)
104 levels[index++] = level;
105 }
106 while (--numRecords);
107
108 if (index != numSymbols)
109 return false;
110 return decoder.Build(levels, numSymbols);
111 }
112
113
CodeReal(ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo * progress)114 HRESULT CCoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream,
115 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress)
116 {
117 if (!_inBitStream.Create(1 << 18))
118 return E_OUTOFMEMORY;
119 if (!_outWindowStream.Create(kHistorySize << 1)) // 16 KB
120 return E_OUTOFMEMORY;
121 if (!outSize)
122 return E_INVALIDARG;
123
124 _outWindowStream.SetStream(outStream);
125 _outWindowStream.Init(false);
126 _inBitStream.SetStream(inStream);
127 _inBitStream.Init();
128
129 const unsigned numDistDirectBits = (_flags & 2) ?
130 kNumDistDirectBitsBig:
131 kNumDistDirectBitsSmall;
132 const bool literalsOn = ((_flags & 4) != 0);
133 const UInt32 minMatchLen = (literalsOn ? 3 : 2);
134
135 if (literalsOn)
136 if (!BuildHuff(_litDecoder, kLitTableSize))
137 return S_FALSE;
138 if (!BuildHuff(_lenDecoder, kLenTableSize))
139 return S_FALSE;
140 if (!BuildHuff(_distDecoder, kDistTableSize))
141 return S_FALSE;
142
143 UInt64 prevProgress = 0;
144 bool moreOut = false;
145 UInt64 pos = 0, unPackSize = *outSize;
146
147 while (pos < unPackSize)
148 {
149 if (progress && (pos - prevProgress) >= (1 << 18))
150 {
151 const UInt64 packSize = _inBitStream.GetProcessedSize();
152 RINOK(progress->SetRatioInfo(&packSize, &pos));
153 prevProgress = pos;
154 }
155
156 if (_inBitStream.ReadBits(1) != 0)
157 {
158 Byte b;
159 if (literalsOn)
160 {
161 UInt32 sym = _litDecoder.Decode(&_inBitStream);
162 // if (sym >= kLitTableSize) break;
163 b = (Byte)sym;
164 }
165 else
166 b = (Byte)_inBitStream.ReadBits(8);
167 _outWindowStream.PutByte(b);
168 pos++;
169 }
170 else
171 {
172 UInt32 lowDistBits = _inBitStream.ReadBits(numDistDirectBits);
173 UInt32 dist = _distDecoder.Decode(&_inBitStream);
174 // if (dist >= kDistTableSize) break;
175 dist = (dist << numDistDirectBits) + lowDistBits;
176 UInt32 len = _lenDecoder.Decode(&_inBitStream);
177 // if (len >= kLenTableSize) break;
178 if (len == kLenTableSize - 1)
179 len += _inBitStream.ReadBits(kNumLenDirectBits);
180 len += minMatchLen;
181
182 {
183 const UInt64 limit = unPackSize - pos;
184 if (len > limit)
185 {
186 moreOut = true;
187 len = (UInt32)limit;
188 }
189 }
190
191 while (dist >= pos && len != 0)
192 {
193 _outWindowStream.PutByte(0);
194 pos++;
195 len--;
196 }
197
198 if (len != 0)
199 {
200 _outWindowStream.CopyBlock(dist, len);
201 pos += len;
202 }
203 }
204 }
205
206 HRESULT res = _outWindowStream.Flush();
207
208 if (res == S_OK)
209 {
210 if (_fullStreamMode)
211 {
212 if (moreOut)
213 res = S_FALSE;
214 if (inSize && *inSize != _inBitStream.GetProcessedSize())
215 res = S_FALSE;
216 }
217 if (pos != unPackSize)
218 res = S_FALSE;
219 }
220
221 return res;
222 }
223
224
Code(ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo * progress)225 STDMETHODIMP CCoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,
226 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress)
227 {
228 try { return CodeReal(inStream, outStream, inSize, outSize, progress); }
229 // catch(const CInBufferException &e) { return e.ErrorCode; }
230 // catch(const CLzOutWindowException &e) { return e.ErrorCode; }
231 catch(const CSystemException &e) { return e.ErrorCode; }
232 catch(...) { return S_FALSE; }
233 }
234
235
SetDecoderProperties2(const Byte * data,UInt32 size)236 STDMETHODIMP CCoder::SetDecoderProperties2(const Byte *data, UInt32 size)
237 {
238 if (size == 0)
239 return E_NOTIMPL;
240 _flags = data[0];
241 return S_OK;
242 }
243
244
SetFinishMode(UInt32 finishMode)245 STDMETHODIMP CCoder::SetFinishMode(UInt32 finishMode)
246 {
247 _fullStreamMode = (finishMode != 0);
248 return S_OK;
249 }
250
251
GetInStreamProcessedSize(UInt64 * value)252 STDMETHODIMP CCoder::GetInStreamProcessedSize(UInt64 *value)
253 {
254 *value = _inBitStream.GetProcessedSize();
255 return S_OK;
256 }
257
258 }}}
259