1 // ShrinkDecoder.cpp
2
3 #include "StdAfx.h"
4
5 #include "../../../C/Alloc.h"
6
7 #include "../Common/InBuffer.h"
8 #include "../Common/OutBuffer.h"
9
10 #include "BitlDecoder.h"
11 #include "ShrinkDecoder.h"
12
13 namespace NCompress {
14 namespace NShrink {
15
16 static const UInt32 kEmpty = 256; // kNumItems;
17 static const UInt32 kBufferSize = (1 << 18);
18 static const unsigned kNumMinBits = 9;
19
CodeReal(ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo * progress)20 HRESULT CDecoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream,
21 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress)
22 {
23 NBitl::CBaseDecoder<CInBuffer> inBuffer;
24 COutBuffer outBuffer;
25
26 if (!inBuffer.Create(kBufferSize))
27 return E_OUTOFMEMORY;
28 if (!outBuffer.Create(kBufferSize))
29 return E_OUTOFMEMORY;
30
31 inBuffer.SetStream(inStream);
32 inBuffer.Init();
33
34 outBuffer.SetStream(outStream);
35 outBuffer.Init();
36
37 {
38 for (unsigned i = 0; i < kNumItems; i++)
39 _parents[i] = kEmpty;
40 }
41
42 UInt64 outPrev = 0, inPrev = 0;
43 unsigned numBits = kNumMinBits;
44 unsigned head = 257;
45 int lastSym = -1;
46 Byte lastChar = 0;
47 bool moreOut = false;
48
49 HRESULT res = S_FALSE;
50
51 for (;;)
52 {
53 _inProcessed = inBuffer.GetProcessedSize();
54 const UInt64 nowPos = outBuffer.GetProcessedSize();
55
56 bool eofCheck = false;
57
58 if (outSize && nowPos >= *outSize)
59 {
60 if (!_fullStreamMode || moreOut)
61 {
62 res = S_OK;
63 break;
64 }
65 eofCheck = true;
66 // Is specSym(=256) allowed after end of stream ?
67 // Do we need to read it here ?
68 }
69
70 if (progress)
71 {
72 if (nowPos - outPrev >= (1 << 20) || _inProcessed - inPrev >= (1 << 20))
73 {
74 outPrev = nowPos;
75 inPrev = _inProcessed;
76 res = progress->SetRatioInfo(&_inProcessed, &nowPos);
77 if (res != SZ_OK)
78 {
79 // break;
80 return res;
81 }
82 }
83 }
84
85 UInt32 sym = inBuffer.ReadBits(numBits);
86
87 if (inBuffer.ExtraBitsWereRead())
88 {
89 res = S_OK;
90 break;
91 }
92
93 if (sym == 256)
94 {
95 sym = inBuffer.ReadBits(numBits);
96
97 if (inBuffer.ExtraBitsWereRead())
98 break;
99
100 if (sym == 1)
101 {
102 if (numBits >= kNumMaxBits)
103 break;
104 numBits++;
105 continue;
106 }
107 if (sym != 2)
108 {
109 break;
110 // continue; // info-zip just ignores such code
111 }
112 {
113 /*
114 ---------- Free leaf nodes ----------
115 Note : that code can mark _parents[lastSym] as free, and next
116 inserted node will be Orphan in that case.
117 */
118
119 unsigned i;
120 for (i = 256; i < kNumItems; i++)
121 _stack[i] = 0;
122 for (i = 257; i < kNumItems; i++)
123 {
124 unsigned par = _parents[i];
125 if (par != kEmpty)
126 _stack[par] = 1;
127 }
128 for (i = 257; i < kNumItems; i++)
129 if (_stack[i] == 0)
130 _parents[i] = kEmpty;
131 head = 257;
132 continue;
133 }
134 }
135
136 if (eofCheck)
137 {
138 // It's can be error case.
139 // That error can be detected later in (*inSize != _inProcessed) check.
140 res = S_OK;
141 break;
142 }
143
144 bool needPrev = false;
145 if (head < kNumItems && lastSym >= 0)
146 {
147 while (head < kNumItems && _parents[head] != kEmpty)
148 head++;
149 if (head < kNumItems)
150 {
151 /*
152 if (head == lastSym), it updates Orphan to self-linked Orphan and creates two problems:
153 1) we must check _stack[i++] overflow in code that walks tree nodes.
154 2) self-linked node can not be removed. So such self-linked nodes can occupy all _parents items.
155 */
156 needPrev = true;
157 _parents[head] = (UInt16)lastSym;
158 _suffixes[head] = (Byte)lastChar;
159 head++;
160 }
161 }
162
163 lastSym = (int)sym;
164 unsigned cur = sym;
165 unsigned i = 0;
166
167 while (cur >= 256)
168 {
169 _stack[i++] = _suffixes[cur];
170 cur = _parents[cur];
171 // don't change that code:
172 // Orphan Check and self-linked Orphan check (_stack overflow check);
173 if (cur == kEmpty || i >= kNumItems)
174 break;
175 }
176
177 if (cur == kEmpty || i >= kNumItems)
178 break;
179
180 _stack[i++] = (Byte)cur;
181 lastChar = (Byte)cur;
182
183 if (needPrev)
184 _suffixes[(size_t)head - 1] = (Byte)cur;
185
186 if (outSize)
187 {
188 const UInt64 limit = *outSize - nowPos;
189 if (i > limit)
190 {
191 moreOut = true;
192 i = (unsigned)limit;
193 }
194 }
195
196 do
197 outBuffer.WriteByte(_stack[--i]);
198 while (i);
199 }
200
201 RINOK(outBuffer.Flush())
202
203 if (res == S_OK)
204 if (_fullStreamMode)
205 {
206 if (moreOut)
207 res = S_FALSE;
208 const UInt64 nowPos = outBuffer.GetProcessedSize();
209 if (outSize && *outSize != nowPos)
210 res = S_FALSE;
211 if (inSize && *inSize != _inProcessed)
212 res = S_FALSE;
213 }
214
215 return res;
216 }
217
218
Z7_COM7F_IMF(CDecoder::Code (ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo * progress))219 Z7_COM7F_IMF(CDecoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,
220 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress))
221 {
222 try { return CodeReal(inStream, outStream, inSize, outSize, progress); }
223 // catch(const CInBufferException &e) { return e.ErrorCode; }
224 // catch(const COutBufferException &e) { return e.ErrorCode; }
225 catch(const CSystemException &e) { return e.ErrorCode; }
226 catch(...) { return S_FALSE; }
227 }
228
229
Z7_COM7F_IMF(CDecoder::SetFinishMode (UInt32 finishMode))230 Z7_COM7F_IMF(CDecoder::SetFinishMode(UInt32 finishMode))
231 {
232 _fullStreamMode = (finishMode != 0);
233 return S_OK;
234 }
235
236
Z7_COM7F_IMF(CDecoder::GetInStreamProcessedSize (UInt64 * value))237 Z7_COM7F_IMF(CDecoder::GetInStreamProcessedSize(UInt64 *value))
238 {
239 *value = _inProcessed;
240 return S_OK;
241 }
242
243
244 }}
245