1 // LzmsDecoder.h
2 // The code is based on LZMS description from wimlib code
3 
4 #ifndef __LZMS_DECODER_H
5 #define __LZMS_DECODER_H
6 
7 // #define SHOW_DEBUG_INFO
8 
9 #ifdef SHOW_DEBUG_INFO
10 #include <stdio.h>
11 #define PRF(x) x
12 #else
13 // #define PRF(x)
14 #endif
15 
16 #include "../../../C/CpuArch.h"
17 #include "../../../C/HuffEnc.h"
18 
19 #include "../../Common/MyBuffer.h"
20 #include "../../Common/MyCom.h"
21 
22 #include "../ICoder.h"
23 
24 #include "HuffmanDecoder.h"
25 
26 namespace NCompress {
27 namespace NLzms {
28 
29 class CBitDecoder
30 {
31 public:
32   const Byte *_buf;
33   unsigned _bitPos;
34 
Init(const Byte * buf,size_t size)35   void Init(const Byte *buf, size_t size) throw()
36   {
37     _buf = buf + size;
38     _bitPos = 0;
39   }
40 
GetValue(unsigned numBits)41   UInt32 GetValue(unsigned numBits) const
42   {
43     UInt32 v = ((UInt32)_buf[-1] << 16) | ((UInt32)_buf[-2] << 8) | (UInt32)_buf[-3];
44     v >>= (24 - numBits - _bitPos);
45     return v & ((1 << numBits) - 1);
46   }
47 
MovePos(unsigned numBits)48   void MovePos(unsigned numBits)
49   {
50     _bitPos += numBits;
51     _buf -= (_bitPos >> 3);
52     _bitPos &= 7;
53   }
54 
ReadBits32(unsigned numBits)55   UInt32 ReadBits32(unsigned numBits)
56   {
57     UInt32 mask = (((UInt32)1 << numBits) - 1);
58     numBits += _bitPos;
59     const Byte *buf = _buf;
60     UInt32 v = GetUi32(buf - 4);
61     if (numBits > 32)
62     {
63       v <<= (numBits - 32);
64       v |= (UInt32)buf[-5] >> (40 - numBits);
65     }
66     else
67       v >>= (32 - numBits);
68     _buf = buf - (numBits >> 3);
69     _bitPos = numBits & 7;
70     return v & mask;
71   }
72 };
73 
74 
75 const unsigned k_NumLitSyms = 256;
76 const unsigned k_NumLenSyms = 54;
77 const unsigned k_NumPosSyms = 799;
78 const unsigned k_NumPowerSyms = 8;
79 
80 const unsigned k_NumProbBits = 6;
81 const unsigned k_ProbLimit = 1 << k_NumProbBits;
82 const unsigned k_InitialProb = 48;
83 const UInt32 k_InitialHist = 0x55555555;
84 
85 const unsigned k_NumReps = 3;
86 
87 const unsigned k_NumMainProbs  = 16;
88 const unsigned k_NumMatchProbs = 32;
89 const unsigned k_NumRepProbs   = 64;
90 
91 const unsigned k_NumHuffmanBits = 15;
92 
93 template <UInt32 m_NumSyms, UInt32 m_RebuildFreq, unsigned numTableBits>
94 class CHuffDecoder: public NCompress::NHuffman::CDecoder<k_NumHuffmanBits, m_NumSyms, numTableBits>
95 {
96 public:
97   UInt32 RebuildRem;
98   UInt32 NumSyms;
99   UInt32 Freqs[m_NumSyms];
100 
Generate()101   void Generate() throw()
102   {
103     UInt32 vals[m_NumSyms];
104     Byte levels[m_NumSyms];
105 
106     // We need to check that our algorithm is OK, when optimal Huffman tree uses more than 15 levels !!!
107     Huffman_Generate(Freqs, vals, levels, NumSyms, k_NumHuffmanBits);
108 
109     /*
110     for (UInt32 i = NumSyms; i < m_NumSyms; i++)
111       levels[i] = 0;
112     */
113     this->BuildFull(levels, NumSyms);
114   }
115 
Rebuild()116   void Rebuild() throw()
117   {
118     Generate();
119     RebuildRem = m_RebuildFreq;
120     UInt32 num = NumSyms;
121     for (UInt32 i = 0; i < num; i++)
122       Freqs[i] = (Freqs[i] >> 1) + 1;
123   }
124 
125 public:
throw()126   void Init(UInt32 numSyms = m_NumSyms) throw()
127   {
128     RebuildRem = m_RebuildFreq;
129     NumSyms = numSyms;
130     for (UInt32 i = 0; i < numSyms; i++)
131       Freqs[i] = 1;
132     // for (; i < m_NumSyms; i++) Freqs[i] = 0;
133     Generate();
134   }
135 };
136 
137 
138 struct CProbEntry
139 {
140   UInt32 Prob;
141   UInt64 Hist;
142 
InitCProbEntry143   void Init()
144   {
145     Prob = k_InitialProb;
146     Hist = k_InitialHist;
147   }
148 
GetProbCProbEntry149   UInt32 GetProb() const throw()
150   {
151     UInt32 prob = Prob;
152     if (prob == 0)
153       prob = 1;
154     else if (prob == k_ProbLimit)
155       prob = k_ProbLimit - 1;
156     return prob;
157   }
158 
UpdateCProbEntry159   void Update(unsigned bit) throw()
160   {
161     Prob += (Int32)(Hist >> (k_ProbLimit - 1)) - (Int32)bit;
162     Hist = (Hist << 1) | bit;
163   }
164 };
165 
166 
167 struct CRangeDecoder
168 {
169   UInt32 range;
170   UInt32 code;
171   const Byte *cur;
172   // const Byte *end;
173 
InitCRangeDecoder174   void Init(const Byte *data, size_t /* size */) throw()
175   {
176     range = 0xFFFFFFFF;
177     code = (((UInt32)GetUi16(data)) << 16) | GetUi16(data + 2);
178     cur = data + 4;
179     // end = data + size;
180   }
181 
NormalizeCRangeDecoder182   void Normalize()
183   {
184     if (range <= 0xFFFF)
185     {
186       range <<= 16;
187       code <<= 16;
188       // if (cur >= end) throw 1;
189       code |= GetUi16(cur);
190       cur += 2;
191     }
192   }
193 
DecodeCRangeDecoder194   unsigned Decode(UInt32 *state, UInt32 numStates, struct CProbEntry *probs)
195   {
196     UInt32 st = *state;
197     CProbEntry *entry = &probs[st];
198     st = (st << 1) & (numStates - 1);
199 
200     UInt32 prob = entry->GetProb();
201 
202     if (range <= 0xFFFF)
203     {
204       range <<= 16;
205       code <<= 16;
206       // if (cur >= end) throw 1;
207       code |= GetUi16(cur);
208       cur += 2;
209     }
210 
211     UInt32 bound = (range >> k_NumProbBits) * prob;
212 
213     if (code < bound)
214     {
215       range = bound;
216       *state = st;
217       entry->Update(0);
218       return 0;
219     }
220     else
221     {
222       range -= bound;
223       code -= bound;
224       *state = st | 1;
225       entry->Update(1);
226       return 1;
227     }
228   }
229 };
230 
231 
232 class CDecoder
233 {
234   // CRangeDecoder _rc;
235   // CBitDecoder _bs;
236   size_t _pos;
237 
238   UInt32 _reps[k_NumReps + 1];
239   UInt64 _deltaReps[k_NumReps + 1];
240 
241   UInt32 mainState;
242   UInt32 matchState;
243   UInt32 lzRepStates[k_NumReps];
244   UInt32 deltaRepStates[k_NumReps];
245 
246   struct CProbEntry mainProbs[k_NumMainProbs];
247   struct CProbEntry matchProbs[k_NumMatchProbs];
248 
249   struct CProbEntry lzRepProbs[k_NumReps][k_NumRepProbs];
250   struct CProbEntry deltaRepProbs[k_NumReps][k_NumRepProbs];
251 
252   CHuffDecoder<k_NumLitSyms, 1024, 9> m_LitDecoder;
253   CHuffDecoder<k_NumPosSyms, 1024, 9> m_PosDecoder;
254   CHuffDecoder<k_NumLenSyms, 512, 8> m_LenDecoder;
255   CHuffDecoder<k_NumPowerSyms, 512, 6> m_PowerDecoder;
256   CHuffDecoder<k_NumPosSyms, 1024, 9> m_DeltaDecoder;
257 
258   Int32 *_x86_history;
259 
260   HRESULT CodeReal(const Byte *in, size_t inSize, Byte *out, size_t outSize);
261 public:
262   CDecoder();
263   ~CDecoder();
264 
265   HRESULT Code(const Byte *in, size_t inSize, Byte *out, size_t outSize);
GetUnpackSize()266   size_t GetUnpackSize() const { return _pos; }
267 };
268 
269 }}
270 
271 #endif
272