1 // QuantumDecoder.cpp
2
3 #include "StdAfx.h"
4
5 #include "../../Common/Defs.h"
6
7 #include "QuantumDecoder.h"
8
9 namespace NCompress {
10 namespace NQuantum {
11
12 static const unsigned kNumLenSymbols = 27;
13 static const unsigned kMatchMinLen = 3;
14 static const unsigned kNumSimplePosSlots = 4;
15 static const unsigned kNumSimpleLenSlots = 6;
16
17 static const UInt16 kUpdateStep = 8;
18 static const UInt16 kFreqSumMax = 3800;
19 static const unsigned kReorderCountStart = 4;
20 static const unsigned kReorderCount = 50;
21
Init(unsigned numItems)22 void CModelDecoder::Init(unsigned numItems)
23 {
24 NumItems = numItems;
25 ReorderCount = kReorderCountStart;
26 for (unsigned i = 0; i < numItems; i++)
27 {
28 Freqs[i] = (UInt16)(numItems - i);
29 Vals[i] = (Byte)i;
30 }
31 Freqs[numItems] = 0;
32 }
33
Decode(CRangeDecoder * rc)34 unsigned CModelDecoder::Decode(CRangeDecoder *rc)
35 {
36 UInt32 threshold = rc->GetThreshold(Freqs[0]);
37 unsigned i;
38 for (i = 1; Freqs[i] > threshold; i++);
39
40 rc->Decode(Freqs[i], Freqs[(size_t)i - 1], Freqs[0]);
41 unsigned res = Vals[--i];
42
43 do
44 Freqs[i] = (UInt16)(Freqs[i] + kUpdateStep);
45 while (i--);
46
47 if (Freqs[0] > kFreqSumMax)
48 {
49 if (--ReorderCount == 0)
50 {
51 ReorderCount = kReorderCount;
52 for (i = 0; i < NumItems; i++)
53 Freqs[i] = (UInt16)(((Freqs[i] - Freqs[(size_t)i + 1]) + 1) >> 1);
54 for (i = 0; i < NumItems - 1; i++)
55 for (unsigned j = i + 1; j < NumItems; j++)
56 if (Freqs[i] < Freqs[j])
57 {
58 UInt16 tmpFreq = Freqs[i];
59 Byte tmpVal = Vals[i];
60 Freqs[i] = Freqs[j];
61 Vals[i] = Vals[j];
62 Freqs[j] = tmpFreq;
63 Vals[j] = tmpVal;
64 }
65
66 do
67 Freqs[i] = (UInt16)(Freqs[i] + Freqs[(size_t)i + 1]);
68 while (i--);
69 }
70 else
71 {
72 i = NumItems - 1;
73 do
74 {
75 Freqs[i] = (UInt16)(Freqs[i] >> 1);
76 if (Freqs[i] <= Freqs[(size_t)i + 1])
77 Freqs[i] = (UInt16)(Freqs[(size_t)i + 1] + 1);
78 }
79 while (i--);
80 }
81 }
82
83 return res;
84 }
85
86
Init()87 void CDecoder::Init()
88 {
89 m_Selector.Init(kNumSelectors);
90 unsigned i;
91 for (i = 0; i < kNumLitSelectors; i++)
92 m_Literals[i].Init(kNumLitSymbols);
93 unsigned numItems = (_numDictBits == 0 ? 1 : (_numDictBits << 1));
94 const unsigned kNumPosSymbolsMax[kNumMatchSelectors] = { 24, 36, 42 };
95 for (i = 0; i < kNumMatchSelectors; i++)
96 m_PosSlot[i].Init(MyMin(numItems, kNumPosSymbolsMax[i]));
97 m_LenSlot.Init(kNumLenSymbols);
98 }
99
100
CodeSpec(const Byte * inData,size_t inSize,UInt32 outSize)101 HRESULT CDecoder::CodeSpec(const Byte *inData, size_t inSize, UInt32 outSize)
102 {
103 if (inSize < 2)
104 return S_FALSE;
105
106 CRangeDecoder rc;
107 rc.Stream.SetStreamAndInit(inData, inSize);
108 rc.Init();
109
110 while (outSize != 0)
111 {
112 if (rc.Stream.WasExtraRead())
113 return S_FALSE;
114
115 unsigned selector = m_Selector.Decode(&rc);
116
117 if (selector < kNumLitSelectors)
118 {
119 Byte b = (Byte)((selector << (8 - kNumLitSelectorBits)) + m_Literals[selector].Decode(&rc));
120 _outWindow.PutByte(b);
121 outSize--;
122 }
123 else
124 {
125 selector -= kNumLitSelectors;
126 unsigned len = selector + kMatchMinLen;
127
128 if (selector == 2)
129 {
130 unsigned lenSlot = m_LenSlot.Decode(&rc);
131 if (lenSlot >= kNumSimpleLenSlots)
132 {
133 lenSlot -= 2;
134 unsigned numDirectBits = (unsigned)(lenSlot >> 2);
135 len += ((4 | (lenSlot & 3)) << numDirectBits) - 2;
136 if (numDirectBits < 6)
137 len += rc.Stream.ReadBits(numDirectBits);
138 }
139 else
140 len += lenSlot;
141 }
142
143 UInt32 dist = m_PosSlot[selector].Decode(&rc);
144
145 if (dist >= kNumSimplePosSlots)
146 {
147 unsigned numDirectBits = (unsigned)((dist >> 1) - 1);
148 dist = ((2 | (dist & 1)) << numDirectBits) + rc.Stream.ReadBits(numDirectBits);
149 }
150
151 unsigned locLen = len;
152 if (len > outSize)
153 locLen = (unsigned)outSize;
154 if (!_outWindow.CopyBlock(dist, locLen))
155 return S_FALSE;
156 outSize -= locLen;
157 len -= locLen;
158 if (len != 0)
159 return S_FALSE;
160 }
161 }
162
163 return rc.Finish() ? S_OK : S_FALSE;
164 }
165
Code(const Byte * inData,size_t inSize,ISequentialOutStream * outStream,UInt32 outSize,bool keepHistory)166 HRESULT CDecoder::Code(const Byte *inData, size_t inSize,
167 ISequentialOutStream *outStream, UInt32 outSize,
168 bool keepHistory)
169 {
170 try
171 {
172 _outWindow.SetStream(outStream);
173 _outWindow.Init(keepHistory);
174 if (!keepHistory)
175 Init();
176
177 HRESULT res = CodeSpec(inData, inSize, outSize);
178 HRESULT res2 = _outWindow.Flush();
179 return res != S_OK ? res : res2;
180 }
181 catch(const CLzOutWindowException &e) { return e.ErrorCode; }
182 catch(...) { return S_FALSE; }
183 }
184
SetParams(unsigned numDictBits)185 HRESULT CDecoder::SetParams(unsigned numDictBits)
186 {
187 if (numDictBits > 21)
188 return E_INVALIDARG;
189 _numDictBits = numDictBits;
190 if (!_outWindow.Create((UInt32)1 << _numDictBits))
191 return E_OUTOFMEMORY;
192 return S_OK;
193 }
194
195 }}
196