1 // QuantumDecoder.cpp
2
3 #include "StdAfx.h"
4
5 // #include <stdio.h>
6
7 #include "../../../C/Alloc.h"
8 #include "../../../C/CpuArch.h"
9
10 #include "../../Common/Defs.h"
11
12 #include "QuantumDecoder.h"
13
14 namespace NCompress {
15 namespace NQuantum {
16
17 static const unsigned kNumLenSymbols = 27;
18 static const unsigned kMatchMinLen = 3;
19 static const unsigned kNumSimpleLenSlots = 6;
20
21 static const unsigned kUpdateStep = 8;
22 static const unsigned kFreqSumMax = 3800;
23 static const unsigned kReorderCount_Start = 4;
24 static const unsigned kReorderCount = 50;
25
26
27 class CRangeDecoder
28 {
29 UInt32 Low;
30 UInt32 Range;
31 UInt32 Code;
32
33 unsigned _bitOffset;
34 const Byte *_buf;
35 const Byte *_bufLim;
36
37 public:
38
39 Z7_FORCE_INLINE
Init(const Byte * inData,size_t inSize)40 void Init(const Byte *inData, size_t inSize)
41 {
42 Code = ((UInt32)*inData << 8) | inData[1];
43 _buf = inData + 2;
44 _bufLim = inData + inSize;
45 _bitOffset = 0;
46 Low = 0;
47 Range = 0x10000;
48 }
49
50 Z7_FORCE_INLINE
WasExtraRead() const51 bool WasExtraRead() const
52 {
53 return _buf > _bufLim;
54 }
55
56 Z7_FORCE_INLINE
ReadBits(unsigned numBits)57 UInt32 ReadBits(unsigned numBits) // numBits > 0
58 {
59 unsigned bitOffset = _bitOffset;
60 const Byte *buf = _buf;
61 const UInt32 res = GetBe32(buf) << bitOffset;
62 bitOffset += numBits;
63 _buf = buf + (bitOffset >> 3);
64 _bitOffset = bitOffset & 7;
65 return res >> (32 - numBits);
66 }
67
68 // ---------- Range Decoder functions ----------
69
70 Z7_FORCE_INLINE
Finish()71 bool Finish()
72 {
73 const unsigned numBits = 2 + ((16 - 2 - _bitOffset) & 7);
74 if (ReadBits(numBits) != 0)
75 return false;
76 return _buf == _bufLim;
77 }
78
79 Z7_FORCE_INLINE
GetThreshold(UInt32 total) const80 UInt32 GetThreshold(UInt32 total) const
81 {
82 return ((Code + 1) * total - 1) / Range; // & 0xFFFF is not required;
83 }
84
85 Z7_FORCE_INLINE
Decode(UInt32 start,UInt32 end,UInt32 total)86 void Decode(UInt32 start, UInt32 end, UInt32 total)
87 {
88 // UInt32 hi = ~(Low + end * Range / total - 1);
89 UInt32 hi = 0 - (Low + end * Range / total);
90 const UInt32 offset = start * Range / total;
91 UInt32 lo = Low + offset;
92 Code -= offset;
93 UInt32 numBits = 0;
94 lo ^= hi;
95 while (lo & (1u << 15))
96 {
97 lo <<= 1;
98 hi <<= 1;
99 numBits++;
100 }
101 lo ^= hi;
102 UInt32 an = lo & hi;
103 while (an & (1u << 14))
104 {
105 an <<= 1;
106 lo <<= 1;
107 hi <<= 1;
108 numBits++;
109 }
110 Low = lo;
111 Range = ((~hi - lo) & 0xffff) + 1;
112 if (numBits)
113 Code = (Code << numBits) + ReadBits(numBits);
114 }
115 };
116
117
118 // Z7_FORCE_INLINE
119 Z7_NO_INLINE
Decode(CRangeDecoder * rc)120 unsigned CModelDecoder::Decode(CRangeDecoder *rc)
121 // Z7_NO_INLINE void CModelDecoder::Normalize()
122 {
123 if (Freqs[0] > kFreqSumMax)
124 {
125 if (--ReorderCount == 0)
126 {
127 ReorderCount = kReorderCount;
128 {
129 unsigned i = NumItems;
130 unsigned next = 0;
131 UInt16 *freqs = &Freqs[i];
132 do
133 {
134 const unsigned freq = *--freqs;
135 *freqs = (UInt16)((freq - next + 1) >> 1);
136 next = freq;
137 }
138 while (--i);
139 }
140 {
141 for (unsigned i = 0; i < NumItems - 1; i++)
142 {
143 UInt16 freq = Freqs[i];
144 for (unsigned k = i + 1; k < NumItems; k++)
145 if (freq < Freqs[k])
146 {
147 const UInt16 freq2 = Freqs[k];
148 Freqs[k] = freq;
149 Freqs[i] = freq2;
150 freq = freq2;
151 const Byte val = Vals[i];
152 Vals[i] = Vals[k];
153 Vals[k] = val;
154 }
155 }
156 }
157 unsigned i = NumItems;
158 unsigned freq = 0;
159 UInt16 *freqs = &Freqs[i];
160 do
161 {
162 freq += *--freqs;
163 *freqs = (UInt16)freq;
164 }
165 while (--i);
166 }
167 else
168 {
169 unsigned i = NumItems;
170 unsigned next = 1;
171 UInt16 *freqs = &Freqs[i];
172 do
173 {
174 unsigned freq = *--freqs >> 1;
175 if (freq < next)
176 freq = next;
177 *freqs = (UInt16)freq;
178 next = freq + 1;
179 }
180 while (--i);
181 }
182 }
183 unsigned res;
184 {
185 const unsigned freq0 = Freqs[0];
186 Freqs[0] = (UInt16)(freq0 + kUpdateStep);
187 const unsigned threshold = rc->GetThreshold(freq0);
188 UInt16 *freqs = &Freqs[1];
189 unsigned freq = *freqs;
190 while (freq > threshold)
191 {
192 *freqs++ = (UInt16)(freq + kUpdateStep);
193 freq = *freqs;
194 }
195 res = Vals[freqs - Freqs - 1];
196 rc->Decode(freq, freqs[-1] - kUpdateStep, freq0);
197 }
198 return res;
199 }
200
201
202 Z7_NO_INLINE
Init(unsigned numItems,unsigned startVal)203 void CModelDecoder::Init(unsigned numItems, unsigned startVal)
204 {
205 NumItems = numItems;
206 ReorderCount = kReorderCount_Start;
207 UInt16 *freqs = Freqs;
208 freqs[numItems] = 0;
209 Byte *vals = Vals;
210 do
211 {
212 *freqs++ = (UInt16)numItems;
213 *vals++ = (Byte)startVal;
214 startVal++;
215 }
216 while (--numItems);
217 }
218
219
Code(const Byte * inData,size_t inSize,UInt32 outSize,bool keepHistory)220 HRESULT CDecoder::Code(const Byte *inData, size_t inSize, UInt32 outSize, bool keepHistory)
221 {
222 if (inSize < 2)
223 return S_FALSE;
224 if (!keepHistory)
225 {
226 _winPos = 0;
227 m_Selector.Init(kNumSelectors, 0);
228 unsigned i;
229 for (i = 0; i < kNumLitSelectors; i++)
230 m_Literals[i].Init(kNumLitSymbols, i * kNumLitSymbols);
231 const unsigned numItems = (_numDictBits == 0 ? 1 : (_numDictBits << 1));
232 // const unsigned kNumPosSymbolsMax[kNumMatchSelectors] = { 24, 36, 42 };
233 for (i = 0; i < kNumMatchSelectors; i++)
234 {
235 const unsigned num = 24 + i * 6 + ((i + 1) & 2) * 3;
236 m_PosSlot[i].Init(MyMin(numItems, num), 0);
237 }
238 m_LenSlot.Init(kNumLenSymbols, kMatchMinLen + kNumMatchSelectors - 1);
239 }
240
241 CRangeDecoder rc;
242 rc.Init(inData, inSize);
243 const UInt32 winSize = _winSize;
244 Byte *pos;
245 {
246 UInt32 winPos = _winPos;
247 if (winPos == winSize)
248 {
249 winPos = 0;
250 _winPos = winPos;
251 _overWin = true;
252 }
253 if (outSize > winSize - winPos)
254 return S_FALSE;
255 pos = _win + winPos;
256 }
257
258 while (outSize != 0)
259 {
260 if (rc.WasExtraRead())
261 return S_FALSE;
262
263 const unsigned selector = m_Selector.Decode(&rc);
264
265 if (selector < kNumLitSelectors)
266 {
267 const unsigned b = m_Literals[selector].Decode(&rc);
268 *pos++ = (Byte)b;
269 --outSize;
270 // if (--outSize == 0) break;
271 }
272 else
273 {
274 unsigned len = selector - kNumLitSelectors + kMatchMinLen;
275
276 if (selector == kNumLitSelectors + kNumMatchSelectors - 1)
277 {
278 len = m_LenSlot.Decode(&rc);
279 if (len >= kNumSimpleLenSlots + kMatchMinLen + kNumMatchSelectors - 1)
280 {
281 len -= kNumSimpleLenSlots - 4 + kMatchMinLen + kNumMatchSelectors - 1;
282 const unsigned numDirectBits = (unsigned)(len >> 2);
283 len = ((4 | (len & 3)) << numDirectBits) - (4 << 1)
284 + kNumSimpleLenSlots
285 + kMatchMinLen + kNumMatchSelectors - 1;
286 if (numDirectBits < 6)
287 len += rc.ReadBits(numDirectBits);
288 }
289 }
290
291 UInt32 dist = m_PosSlot[(size_t)selector - kNumLitSelectors].Decode(&rc);
292
293 if (dist >= 4)
294 {
295 const unsigned numDirectBits = (unsigned)((dist >> 1) - 1);
296 dist = ((2 | (dist & 1)) << numDirectBits) + rc.ReadBits(numDirectBits);
297 }
298
299 if ((Int32)(outSize -= len) < 0)
300 return S_FALSE;
301
302 ptrdiff_t srcPos = (ptrdiff_t)(Int32)((pos - _win) - (ptrdiff_t)dist - 1);
303 if (srcPos < 0)
304 {
305 if (!_overWin)
306 return S_FALSE;
307 UInt32 rem = (UInt32)-srcPos;
308 srcPos += winSize;
309 if (rem < len)
310 {
311 const Byte *src = _win + srcPos;
312 len -= rem;
313 do
314 *pos++ = *src++;
315 while (--rem);
316 srcPos = 0;
317 }
318 }
319 const Byte *src = _win + srcPos;
320 do
321 *pos++ = *src++;
322 while (--len);
323 // if (outSize == 0) break;
324 }
325 }
326
327 _winPos = (UInt32)(size_t)(pos - _win);
328 return rc.Finish() ? S_OK : S_FALSE;
329 }
330
331
SetParams(unsigned numDictBits)332 HRESULT CDecoder::SetParams(unsigned numDictBits)
333 {
334 if (numDictBits > 21)
335 return E_INVALIDARG;
336 _numDictBits = numDictBits;
337 _winPos = 0;
338 _overWin = false;
339
340 if (numDictBits < 15)
341 numDictBits = 15;
342 _winSize = (UInt32)1 << numDictBits;
343 if (!_win || _winSize > _winSize_allocated)
344 {
345 MidFree(_win);
346 _win = NULL;
347 _win = (Byte *)MidAlloc(_winSize);
348 if (!_win)
349 return E_OUTOFMEMORY;
350 _winSize_allocated = _winSize;
351 }
352 return S_OK;
353 }
354
355 }}
356