1 // ZDecoder.cpp
2
3 #include "StdAfx.h"
4
5 // #include <stdio.h>
6
7 #include "../../../C/Alloc.h"
8
9 #include "../Common/InBuffer.h"
10 #include "../Common/OutBuffer.h"
11
12 #include "ZDecoder.h"
13
14 namespace NCompress {
15 namespace NZ {
16
17 static const size_t kBufferSize = 1 << 20;
18 static const Byte kNumBitsMask = 0x1F;
19 static const Byte kBlockModeMask = 0x80;
20 static const unsigned kNumMinBits = 9;
21 static const unsigned kNumMaxBits = 16;
22
Free()23 void CDecoder::Free()
24 {
25 MyFree(_parents); _parents = NULL;
26 MyFree(_suffixes); _suffixes = NULL;
27 MyFree(_stack); _stack = NULL;
28 }
29
~CDecoder()30 CDecoder::~CDecoder() { Free(); }
31
Code(ISequentialInStream * inStream,ISequentialOutStream * outStream,ICompressProgressInfo * progress)32 HRESULT CDecoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,
33 ICompressProgressInfo *progress)
34 {
35 try {
36 // PackSize = 0;
37
38 CInBuffer inBuffer;
39 COutBuffer outBuffer;
40
41 if (!inBuffer.Create(kBufferSize))
42 return E_OUTOFMEMORY;
43 inBuffer.SetStream(inStream);
44 inBuffer.Init();
45
46 if (!outBuffer.Create(kBufferSize))
47 return E_OUTOFMEMORY;
48 outBuffer.SetStream(outStream);
49 outBuffer.Init();
50
51 Byte buf[kNumMaxBits + 4];
52 {
53 if (inBuffer.ReadBytes(buf, 3) < 3)
54 return S_FALSE;
55 if (buf[0] != 0x1F || buf[1] != 0x9D)
56 return S_FALSE;
57 }
58 const Byte prop = buf[2];
59
60 if ((prop & 0x60) != 0)
61 return S_FALSE;
62 const unsigned maxbits = prop & kNumBitsMask;
63 if (maxbits < kNumMinBits || maxbits > kNumMaxBits)
64 return S_FALSE;
65 const UInt32 numItems = (UInt32)1 << maxbits;
66 // Speed optimization: blockSymbol can contain unused velue.
67
68 if (maxbits != _numMaxBits || !_parents || !_suffixes || !_stack)
69 {
70 Free();
71 _parents = (UInt16 *)MyAlloc(numItems * sizeof(UInt16)); if (!_parents) return E_OUTOFMEMORY;
72 _suffixes = (Byte *)MyAlloc(numItems * sizeof(Byte)); if (!_suffixes) return E_OUTOFMEMORY;
73 _stack = (Byte *)MyAlloc(numItems * sizeof(Byte)); if (!_stack) return E_OUTOFMEMORY;
74 _numMaxBits = maxbits;
75 }
76
77 UInt64 prevPos = 0;
78 const UInt32 blockSymbol = ((prop & kBlockModeMask) != 0) ? 256 : ((UInt32)1 << kNumMaxBits);
79 unsigned numBits = kNumMinBits;
80 UInt32 head = (blockSymbol == 256) ? 257 : 256;
81 bool needPrev = false;
82 unsigned bitPos = 0;
83 unsigned numBufBits = 0;
84
85 _parents[256] = 0; // virus protection
86 _suffixes[256] = 0;
87 HRESULT res = S_OK;
88
89 for (;;)
90 {
91 if (numBufBits == bitPos)
92 {
93 numBufBits = (unsigned)inBuffer.ReadBytes(buf, numBits) * 8;
94 bitPos = 0;
95 const UInt64 nowPos = outBuffer.GetProcessedSize();
96 if (progress && nowPos - prevPos >= (1 << 13))
97 {
98 prevPos = nowPos;
99 const UInt64 packSize = inBuffer.GetProcessedSize();
100 RINOK(progress->SetRatioInfo(&packSize, &nowPos))
101 }
102 }
103 const unsigned bytePos = bitPos >> 3;
104 UInt32 symbol = buf[bytePos] | ((UInt32)buf[(size_t)bytePos + 1] << 8) | ((UInt32)buf[(size_t)bytePos + 2] << 16);
105 symbol >>= (bitPos & 7);
106 symbol &= ((UInt32)1 << numBits) - 1;
107 bitPos += numBits;
108 if (bitPos > numBufBits)
109 break;
110 if (symbol >= head)
111 {
112 res = S_FALSE;
113 break;
114 }
115 if (symbol == blockSymbol)
116 {
117 numBufBits = bitPos = 0;
118 numBits = kNumMinBits;
119 head = 257;
120 needPrev = false;
121 continue;
122 }
123 UInt32 cur = symbol;
124 unsigned i = 0;
125 while (cur >= 256)
126 {
127 _stack[i++] = _suffixes[cur];
128 cur = _parents[cur];
129 }
130 _stack[i++] = (Byte)cur;
131 if (needPrev)
132 {
133 _suffixes[(size_t)head - 1] = (Byte)cur;
134 if (symbol == head - 1)
135 _stack[0] = (Byte)cur;
136 }
137 do
138 outBuffer.WriteByte((_stack[--i]));
139 while (i > 0);
140 if (head < numItems)
141 {
142 needPrev = true;
143 _parents[head++] = (UInt16)symbol;
144 if (head > ((UInt32)1 << numBits))
145 {
146 if (numBits < maxbits)
147 {
148 numBufBits = bitPos = 0;
149 numBits++;
150 }
151 }
152 }
153 else
154 needPrev = false;
155 }
156 // PackSize = inBuffer.GetProcessedSize();
157 const HRESULT res2 = outBuffer.Flush();
158 return (res == S_OK) ? res2 : res;
159
160 }
161 catch(const CInBufferException &e) { return e.ErrorCode; }
162 catch(const COutBufferException &e) { return e.ErrorCode; }
163 catch(...) { return S_FALSE; }
164 }
165
166
CheckStream(const Byte * data,size_t size)167 bool CheckStream(const Byte *data, size_t size)
168 {
169 if (size < 3)
170 return false;
171 if (data[0] != 0x1F || data[1] != 0x9D)
172 return false;
173 const Byte prop = data[2];
174 if ((prop & 0x60) != 0)
175 return false;
176 const unsigned maxbits = prop & kNumBitsMask;
177 if (maxbits < kNumMinBits || maxbits > kNumMaxBits)
178 return false;
179 const UInt32 numItems = (UInt32)1 << maxbits;
180 const UInt32 blockSymbol = ((prop & kBlockModeMask) != 0) ? 256 : ((UInt32)1 << kNumMaxBits);
181 unsigned numBits = kNumMinBits;
182 UInt32 head = (blockSymbol == 256) ? 257 : 256;
183 unsigned bitPos = 0;
184 unsigned numBufBits = 0;
185 Byte buf[kNumMaxBits + 4];
186 data += 3;
187 size -= 3;
188 // printf("\n\n");
189 for (;;)
190 {
191 if (numBufBits == bitPos)
192 {
193 const unsigned num = (numBits < size) ? numBits : (unsigned)size;
194 memcpy(buf, data, num);
195 data += num;
196 size -= num;
197 numBufBits = num * 8;
198 bitPos = 0;
199 }
200 const unsigned bytePos = bitPos >> 3;
201 UInt32 symbol = buf[bytePos] | ((UInt32)buf[bytePos + 1] << 8) | ((UInt32)buf[bytePos + 2] << 16);
202 symbol >>= (bitPos & 7);
203 symbol &= ((UInt32)1 << numBits) - 1;
204 bitPos += numBits;
205 if (bitPos > numBufBits)
206 {
207 // printf(" OK", symbol);
208 return true;
209 }
210 // printf("%3X ", symbol);
211 if (symbol >= head)
212 return false;
213 if (symbol == blockSymbol)
214 {
215 numBufBits = bitPos = 0;
216 numBits = kNumMinBits;
217 head = 257;
218 continue;
219 }
220 if (head < numItems)
221 {
222 head++;
223 if (head > ((UInt32)1 << numBits))
224 {
225 if (numBits < maxbits)
226 {
227 numBufBits = bitPos = 0;
228 numBits++;
229 }
230 }
231 }
232 }
233 }
234
235 }}
236