1 // DeflateDecoder.cpp
2
3 #include "StdAfx.h"
4
5 #include "DeflateDecoder.h"
6
7 namespace NCompress {
8 namespace NDeflate {
9 namespace NDecoder {
10
CCoder(bool deflate64Mode)11 CCoder::CCoder(bool deflate64Mode):
12 _deflateNSIS(false),
13 _deflate64Mode(deflate64Mode),
14 _keepHistory(false),
15 _needFinishInput(false),
16 _needInitInStream(true),
17 _outSizeDefined(false),
18 _outStartPos(0)
19 {}
20
ReadBits(unsigned numBits)21 UInt32 CCoder::ReadBits(unsigned numBits)
22 {
23 return m_InBitStream.ReadBits(numBits);
24 }
25
ReadAlignedByte()26 Byte CCoder::ReadAlignedByte()
27 {
28 return m_InBitStream.ReadAlignedByte();
29 }
30
DecodeLevels(Byte * levels,unsigned numSymbols)31 bool CCoder::DecodeLevels(Byte *levels, unsigned numSymbols)
32 {
33 unsigned i = 0;
34
35 do
36 {
37 unsigned sym = m_LevelDecoder.Decode(&m_InBitStream);
38 if (sym < kTableDirectLevels)
39 levels[i++] = (Byte)sym;
40 else
41 {
42 if (sym >= kLevelTableSize)
43 return false;
44
45 unsigned num;
46 unsigned numBits;
47 Byte symbol;
48
49 if (sym == kTableLevelRepNumber)
50 {
51 if (i == 0)
52 return false;
53 numBits = 2;
54 num = 0;
55 symbol = levels[(size_t)i - 1];
56 }
57 else
58 {
59 sym -= kTableLevel0Number;
60 sym <<= 2;
61 numBits = 3 + (unsigned)sym;
62 num = ((unsigned)sym << 1);
63 symbol = 0;
64 }
65
66 num += i + 3 + ReadBits(numBits);
67 if (num > numSymbols)
68 return false;
69 do
70 levels[i++] = symbol;
71 while (i < num);
72 }
73 }
74 while (i < numSymbols);
75
76 return true;
77 }
78
79 #define RIF(x) { if (!(x)) return false; }
80
ReadTables(void)81 bool CCoder::ReadTables(void)
82 {
83 m_FinalBlock = (ReadBits(kFinalBlockFieldSize) == NFinalBlockField::kFinalBlock);
84 if (m_InBitStream.ExtraBitsWereRead())
85 return false;
86 const UInt32 blockType = ReadBits(kBlockTypeFieldSize);
87 if (blockType > NBlockType::kDynamicHuffman)
88 return false;
89 if (m_InBitStream.ExtraBitsWereRead())
90 return false;
91
92 if (blockType == NBlockType::kStored)
93 {
94 m_StoredMode = true;
95 m_InBitStream.AlignToByte();
96 m_StoredBlockSize = ReadAligned_UInt16(); // ReadBits(kStoredBlockLengthFieldSize)
97 if (_deflateNSIS)
98 return true;
99 return (m_StoredBlockSize == (UInt16)~ReadAligned_UInt16());
100 }
101
102 m_StoredMode = false;
103
104 CLevels levels;
105 if (blockType == NBlockType::kFixedHuffman)
106 {
107 levels.SetFixedLevels();
108 _numDistLevels = _deflate64Mode ? kDistTableSize64 : kDistTableSize32;
109 }
110 else
111 {
112 const unsigned numLitLenLevels = ReadBits(kNumLenCodesFieldSize) + kNumLitLenCodesMin;
113 _numDistLevels = (unsigned)ReadBits(kNumDistCodesFieldSize) + kNumDistCodesMin;
114 const unsigned numLevelCodes = ReadBits(kNumLevelCodesFieldSize) + kNumLevelCodesMin;
115
116 if (!_deflate64Mode)
117 if (_numDistLevels > kDistTableSize32)
118 return false;
119
120 Byte levelLevels[kLevelTableSize];
121 for (unsigned i = 0; i < kLevelTableSize; i++)
122 {
123 const unsigned position = kCodeLengthAlphabetOrder[i];
124 if (i < numLevelCodes)
125 levelLevels[position] = (Byte)ReadBits(kLevelFieldSize);
126 else
127 levelLevels[position] = 0;
128 }
129
130 if (m_InBitStream.ExtraBitsWereRead())
131 return false;
132
133 RIF(m_LevelDecoder.Build(levelLevels, false)) // full
134
135 Byte tmpLevels[kFixedMainTableSize + kFixedDistTableSize];
136 if (!DecodeLevels(tmpLevels, numLitLenLevels + _numDistLevels))
137 return false;
138
139 if (m_InBitStream.ExtraBitsWereRead())
140 return false;
141
142 levels.SubClear();
143 memcpy(levels.litLenLevels, tmpLevels, numLitLenLevels);
144 memcpy(levels.distLevels, tmpLevels + numLitLenLevels, _numDistLevels);
145 }
146 RIF(m_MainDecoder.Build(levels.litLenLevels))
147 return m_DistDecoder.Build(levels.distLevels);
148 }
149
150
InitInStream(bool needInit)151 HRESULT CCoder::InitInStream(bool needInit)
152 {
153 if (needInit)
154 {
155 // for HDD-Windows:
156 // (1 << 15) - best for reading only prefetch
157 // (1 << 22) - best for real reading / writing
158 if (!m_InBitStream.Create(1 << 20))
159 return E_OUTOFMEMORY;
160 m_InBitStream.Init();
161 _needInitInStream = false;
162 }
163 return S_OK;
164 }
165
166
CodeSpec(UInt32 curSize,bool finishInputStream,UInt32 inputProgressLimit)167 HRESULT CCoder::CodeSpec(UInt32 curSize, bool finishInputStream, UInt32 inputProgressLimit)
168 {
169 if (_remainLen == kLenIdFinished)
170 return S_OK;
171
172 if (_remainLen == kLenIdNeedInit)
173 {
174 if (!_keepHistory)
175 if (!m_OutWindowStream.Create(_deflate64Mode ? kHistorySize64: kHistorySize32))
176 return E_OUTOFMEMORY;
177 RINOK(InitInStream(_needInitInStream))
178 m_OutWindowStream.Init(_keepHistory);
179
180 m_FinalBlock = false;
181 _remainLen = 0;
182 _needReadTable = true;
183 }
184
185 // _remainLen >= 0
186 while (_remainLen && curSize)
187 {
188 _remainLen--;
189 const Byte b = m_OutWindowStream.GetByte(_rep0);
190 m_OutWindowStream.PutByte(b);
191 curSize--;
192 }
193
194 UInt64 inputStart = 0;
195 if (inputProgressLimit != 0)
196 inputStart = m_InBitStream.GetProcessedSize();
197
198 while (curSize || finishInputStream)
199 {
200 if (m_InBitStream.ExtraBitsWereRead())
201 return S_FALSE;
202
203 if (_needReadTable)
204 {
205 if (m_FinalBlock)
206 {
207 _remainLen = kLenIdFinished;
208 break;
209 }
210
211 if (inputProgressLimit != 0)
212 if (m_InBitStream.GetProcessedSize() - inputStart >= inputProgressLimit)
213 return S_OK;
214
215 if (!ReadTables())
216 return S_FALSE;
217 if (m_InBitStream.ExtraBitsWereRead())
218 return S_FALSE;
219 _needReadTable = false;
220 }
221
222 if (m_StoredMode)
223 {
224 if (finishInputStream && curSize == 0 && m_StoredBlockSize != 0)
225 return S_FALSE;
226 /* NSIS version contains some bits in bitl bits buffer.
227 So we must read some first bytes via ReadAlignedByte */
228 UInt32 num = m_StoredBlockSize;
229 if (num > curSize)
230 num = curSize;
231 m_StoredBlockSize -= num;
232 curSize -= num;
233 for (; num && m_InBitStream.ThereAreDataInBitsBuffer(); num--)
234 m_OutWindowStream.PutByte(ReadAlignedByte());
235 if (num)
236 {
237 #if 1
238 // fast code
239 do
240 {
241 size_t a;
242 Byte *buf = m_OutWindowStream.GetOutBuffer(a);
243 // a != 0
244 if (a > num)
245 a = num;
246 // a != 0
247 a = m_InBitStream.ReadDirectBytesPart(buf, a);
248 if (a == 0)
249 return S_FALSE;
250 m_OutWindowStream.SkipWrittenBytes(a);
251 num -= (UInt32)a;
252 }
253 while (num);
254 #else
255 // slow code:
256 do
257 m_OutWindowStream.PutByte(m_InBitStream.ReadDirectByte());
258 while (--num);
259 #endif
260 }
261 _needReadTable = (m_StoredBlockSize == 0);
262 continue;
263 }
264
265 while (curSize)
266 {
267 if (m_InBitStream.ExtraBitsWereRead_Fast())
268 return S_FALSE;
269 unsigned sym;
270 #if 0
271 sym = m_MainDecoder.Decode(&m_InBitStream);
272 #else
273 Z7_HUFF_DECODE_CHECK(sym, &m_MainDecoder, kNumHuffmanBits, kNumTableBits_Main, &m_InBitStream, { return S_FALSE; })
274 #endif
275
276 if (sym < 0x100)
277 {
278 m_OutWindowStream.PutByte((Byte)sym);
279 curSize--;
280 continue;
281 }
282 if (sym == kSymbolEndOfBlock)
283 {
284 _needReadTable = true;
285 break;
286 }
287 #if 0
288 if (sym >= kMainTableSize)
289 return S_FALSE;
290 #endif
291 {
292 sym -= kSymbolMatch;
293 UInt32 len;
294 {
295 unsigned numBits;
296 if (_deflate64Mode)
297 {
298 len = kLenStart64[sym];
299 numBits = kLenDirectBits64[sym];
300 }
301 else
302 {
303 len = kLenStart32[sym];
304 numBits = kLenDirectBits32[sym];
305 }
306 len += kMatchMinLen + m_InBitStream.ReadBits(numBits);
307 }
308
309 #if 0
310 sym = m_DistDecoder.Decode(&m_InBitStream);
311 if (sym >= _numDistLevels)
312 return S_FALSE;
313 #else
314 Z7_HUFF_DECODE_CHECK(sym, &m_DistDecoder, kNumHuffmanBits, kNumTableBits_Dist, &m_InBitStream, { return S_FALSE; })
315 #endif
316
317 #if 1
318 sym = kDistStart[sym] + m_InBitStream.ReadBits(kDistDirectBits[sym]);
319 #else
320 if (sym >= 4)
321 {
322 // sym &= 31;
323 const unsigned numDirectBits = (sym - 2) >> 1;
324 sym = (2u | (sym & 1)) << numDirectBits;
325 sym += m_InBitStream.ReadBits(numDirectBits);
326 }
327 #endif
328 UInt32 locLen = len;
329 if (locLen > curSize)
330 locLen = (UInt32)curSize;
331 if (!m_OutWindowStream.CopyBlock(sym, locLen))
332 return S_FALSE;
333 curSize -= locLen;
334 len -= locLen;
335 if (len != 0)
336 {
337 _remainLen = (Int32)len;
338 _rep0 = sym;
339 break;
340 }
341 }
342 }
343
344 if (finishInputStream && curSize == 0)
345 {
346 if (m_MainDecoder.Decode(&m_InBitStream) != kSymbolEndOfBlock)
347 return S_FALSE;
348 _needReadTable = true;
349 }
350 }
351
352 if (m_InBitStream.ExtraBitsWereRead())
353 return S_FALSE;
354
355 return S_OK;
356 }
357
358
359 #ifdef Z7_NO_EXCEPTIONS
360
361 #define DEFLATE_TRY_BEGIN
362 #define DEFLATE_TRY_END(res)
363
364 #else
365
366 #define DEFLATE_TRY_BEGIN try {
367 #define DEFLATE_TRY_END(res) } \
368 catch(const CSystemException &e) { res = e.ErrorCode; } \
369 catch(...) { res = S_FALSE; }
370
371 // catch(const CInBufferException &e) { res = e.ErrorCode; }
372 // catch(const CLzOutWindowException &e) { res = e.ErrorCode; }
373
374 #endif
375
376
CodeReal(ISequentialOutStream * outStream,ICompressProgressInfo * progress)377 HRESULT CCoder::CodeReal(ISequentialOutStream *outStream, ICompressProgressInfo *progress)
378 {
379 HRESULT res;
380
381 DEFLATE_TRY_BEGIN
382
383 m_OutWindowStream.SetStream(outStream);
384 CCoderReleaser flusher(this);
385
386 const UInt64 inStart = _needInitInStream ? 0 : m_InBitStream.GetProcessedSize();
387
388 for (;;)
389 {
390 const UInt32 kInputProgressLimit = 1 << 21;
391 UInt32 curSize = 1 << 20;
392 bool finishInputStream = false;
393 if (_outSizeDefined)
394 {
395 const UInt64 rem = _outSize - GetOutProcessedCur();
396 if (curSize >= rem)
397 {
398 curSize = (UInt32)rem;
399 if (_needFinishInput)
400 finishInputStream = true;
401 else if (curSize == 0)
402 break;
403 }
404 }
405
406 RINOK(CodeSpec(curSize, finishInputStream, progress ? kInputProgressLimit : 0))
407
408 if (_remainLen == kLenIdFinished)
409 break;
410
411 if (progress)
412 {
413 const UInt64 inSize = m_InBitStream.GetProcessedSize() - inStart;
414 const UInt64 nowPos64 = GetOutProcessedCur();
415 RINOK(progress->SetRatioInfo(&inSize, &nowPos64))
416 }
417 }
418
419 flusher.NeedFlush = false;
420 res = Flush();
421 if (res == S_OK && _remainLen != kLenIdNeedInit && InputEofError())
422 return S_FALSE;
423
424 DEFLATE_TRY_END(res)
425
426 return res;
427 }
428
429
Z7_COM7F_IMF(CCoder::Code (ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 *,const UInt64 * outSize,ICompressProgressInfo * progress))430 Z7_COM7F_IMF(CCoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,
431 const UInt64 * /* inSize */, const UInt64 *outSize, ICompressProgressInfo *progress))
432 {
433 SetInStream(inStream);
434 SetOutStreamSize(outSize);
435 const HRESULT res = CodeReal(outStream, progress);
436 ReleaseInStream();
437 /*
438 if (res == S_OK)
439 if (_needFinishInput && inSize && *inSize != m_InBitStream.GetProcessedSize())
440 res = S_FALSE;
441 */
442 return res;
443 }
444
445
Z7_COM7F_IMF(CCoder::SetFinishMode (UInt32 finishMode))446 Z7_COM7F_IMF(CCoder::SetFinishMode(UInt32 finishMode))
447 {
448 Set_NeedFinishInput(finishMode != 0);
449 return S_OK;
450 }
451
452
Z7_COM7F_IMF(CCoder::GetInStreamProcessedSize (UInt64 * value))453 Z7_COM7F_IMF(CCoder::GetInStreamProcessedSize(UInt64 *value))
454 {
455 *value = m_InBitStream.GetStreamSize();
456 return S_OK;
457 }
458
459
Z7_COM7F_IMF(CCoder::ReadUnusedFromInBuf (void * data,UInt32 size,UInt32 * processedSize))460 Z7_COM7F_IMF(CCoder::ReadUnusedFromInBuf(void *data, UInt32 size, UInt32 *processedSize))
461 {
462 AlignToByte();
463 UInt32 i = 0;
464 {
465 for (i = 0; i < size; i++)
466 {
467 if (!m_InBitStream.ReadAlignedByte_FromBuf(((Byte *)data)[i]))
468 break;
469 }
470 }
471 if (processedSize)
472 *processedSize = i;
473 return S_OK;
474 }
475
476
Z7_COM7F_IMF(CCoder::SetInStream (ISequentialInStream * inStream))477 Z7_COM7F_IMF(CCoder::SetInStream(ISequentialInStream *inStream))
478 {
479 m_InStreamRef = inStream;
480 m_InBitStream.SetStream(inStream);
481 return S_OK;
482 }
483
484
Z7_COM7F_IMF(CCoder::ReleaseInStream ())485 Z7_COM7F_IMF(CCoder::ReleaseInStream())
486 {
487 m_InStreamRef.Release();
488 m_InBitStream.ClearStreamPtr();
489 return S_OK;
490 }
491
492
SetOutStreamSizeResume(const UInt64 * outSize)493 void CCoder::SetOutStreamSizeResume(const UInt64 *outSize)
494 {
495 _outSizeDefined = (outSize != NULL);
496 _outSize = 0;
497 if (_outSizeDefined)
498 _outSize = *outSize;
499 m_OutWindowStream.Init(_keepHistory);
500 _outStartPos = m_OutWindowStream.GetProcessedSize();
501 _remainLen = kLenIdNeedInit;
502 }
503
504
Z7_COM7F_IMF(CCoder::SetOutStreamSize (const UInt64 * outSize))505 Z7_COM7F_IMF(CCoder::SetOutStreamSize(const UInt64 *outSize))
506 {
507 /*
508 18.06:
509 We want to support GetInputProcessedSize() before CCoder::Read()
510 So we call m_InBitStream.Init() even before buffer allocations
511 m_InBitStream.Init() just sets variables to default values
512 But later we will call m_InBitStream.Init() again with real buffer pointers
513 */
514 m_InBitStream.Init();
515 _needInitInStream = true;
516 SetOutStreamSizeResume(outSize);
517 return S_OK;
518 }
519
520
521 #ifndef Z7_NO_READ_FROM_CODER
522
Z7_COM7F_IMF(CCoder::Read (void * data,UInt32 size,UInt32 * processedSize))523 Z7_COM7F_IMF(CCoder::Read(void *data, UInt32 size, UInt32 *processedSize))
524 {
525 if (processedSize)
526 *processedSize = 0;
527 const UInt64 outPos = GetOutProcessedCur();
528
529 bool finishInputStream = false;
530 if (_outSizeDefined)
531 {
532 const UInt64 rem = _outSize - outPos;
533 if (size >= rem)
534 {
535 size = (UInt32)rem;
536 if (_needFinishInput)
537 finishInputStream = true;
538 }
539 }
540 if (!finishInputStream && size == 0)
541 return S_OK;
542
543 HRESULT res;
544 DEFLATE_TRY_BEGIN
545 m_OutWindowStream.SetMemStream((Byte *)data);
546 res = CodeSpec(size, finishInputStream);
547 DEFLATE_TRY_END(res)
548 {
549 const HRESULT res2 = Flush();
550 if (res2 != S_OK)
551 res = res2;
552 }
553 if (processedSize)
554 *processedSize = (UInt32)(GetOutProcessedCur() - outPos);
555 m_OutWindowStream.SetMemStream(NULL);
556 return res;
557 }
558
559 #endif
560
561
CodeResume(ISequentialOutStream * outStream,const UInt64 * outSize,ICompressProgressInfo * progress)562 HRESULT CCoder::CodeResume(ISequentialOutStream *outStream, const UInt64 *outSize, ICompressProgressInfo *progress)
563 {
564 SetOutStreamSizeResume(outSize);
565 return CodeReal(outStream, progress);
566 }
567
568 }}}
569