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