xref: /aosp_15_r20/external/lzma/CPP/7zip/Compress/LzmsDecoder.h (revision f6dc9357d832569d4d1f5d24eacdb3935a1ae8e6)
1 // LzmsDecoder.h
2 // The code is based on LZMS description from wimlib code
3 
4 #ifndef ZIP7_INC_LZMS_DECODER_H
5 #define ZIP7_INC_LZMS_DECODER_H
6 
7 #include "../../../C/CpuArch.h"
8 #include "../../../C/HuffEnc.h"
9 
10 #include "HuffmanDecoder.h"
11 
12 namespace NCompress {
13 namespace NLzms {
14 
15 const unsigned k_NumLitSyms = 256;
16 const unsigned k_NumLenSyms = 54;
17 const unsigned k_NumPosSyms = 799;
18 const unsigned k_NumPowerSyms = 8;
19 
20 const unsigned k_NumProbBits = 6;
21 const unsigned k_ProbLimit = 1 << k_NumProbBits;
22 const unsigned k_InitialProb = 48;
23 const UInt32 k_InitialHist = 0x55555555;
24 
25 const unsigned k_NumReps = 3;
26 
27 const unsigned k_NumMainProbs  = 16;
28 const unsigned k_NumMatchProbs = 32;
29 const unsigned k_NumRepProbs   = 64;
30 
31 const unsigned k_NumHuffmanBits = 15;
32 
33 template <UInt32 m_NumSyms, UInt32 m_RebuildFreq, unsigned numTableBits>
34 class CHuffDecoder: public NCompress::NHuffman::CDecoder<k_NumHuffmanBits, m_NumSyms, numTableBits>
35 {
36 public:
37   UInt32 RebuildRem;
38   UInt32 NumSyms;
39   UInt32 Freqs[m_NumSyms];
40 
Generate()41   void Generate() throw()
42   {
43     UInt32 vals[m_NumSyms];
44     Byte levels[m_NumSyms];
45 
46     // We need to check that our algorithm is OK, when optimal Huffman tree uses more than 15 levels !!!
47     Huffman_Generate(Freqs, vals, levels, NumSyms, k_NumHuffmanBits);
48 
49     for (UInt32 i = NumSyms; i < m_NumSyms; i++)
50       levels[i] = 0;
51 
52     this->Build(levels, /* NumSyms, */ NHuffman::k_BuildMode_Full);
53   }
54 
Rebuild()55   void Rebuild() throw()
56   {
57     Generate();
58     RebuildRem = m_RebuildFreq;
59     const UInt32 num = NumSyms;
60     for (UInt32 i = 0; i < num; i++)
61       Freqs[i] = (Freqs[i] >> 1) + 1;
62   }
63 
64 public:
throw()65   void Init(UInt32 numSyms = m_NumSyms) throw()
66   {
67     RebuildRem = m_RebuildFreq;
68     NumSyms = numSyms;
69     for (UInt32 i = 0; i < numSyms; i++)
70       Freqs[i] = 1;
71     // for (; i < m_NumSyms; i++) Freqs[i] = 0;
72     Generate();
73   }
74 };
75 
76 
77 struct CProbEntry
78 {
79   UInt32 Prob;
80   UInt64 Hist;
81 
InitCProbEntry82   void Init()
83   {
84     Prob = k_InitialProb;
85     Hist = k_InitialHist;
86   }
87 
GetProbCProbEntry88   UInt32 GetProb() const throw()
89   {
90     UInt32 prob = Prob;
91     if (prob == 0)
92       prob = 1;
93     else if (prob == k_ProbLimit)
94       prob = k_ProbLimit - 1;
95     return prob;
96   }
97 
UpdateCProbEntry98   void Update(unsigned bit) throw()
99   {
100     Prob += (UInt32)((Int32)(Hist >> (k_ProbLimit - 1)) - (Int32)bit);
101     Hist = (Hist << 1) | bit;
102   }
103 };
104 
105 
106 struct CRangeDecoder
107 {
108   UInt32 range;
109   UInt32 code;
110   const Byte *cur;
111   // const Byte *end;
112 
InitCRangeDecoder113   void Init(const Byte *data, size_t /* size */) throw()
114   {
115     range = 0xFFFFFFFF;
116     code = (((UInt32)GetUi16(data)) << 16) | GetUi16(data + 2);
117     cur = data + 4;
118     // end = data + size;
119   }
120 
NormalizeCRangeDecoder121   void Normalize()
122   {
123     if (range <= 0xFFFF)
124     {
125       range <<= 16;
126       code <<= 16;
127       // if (cur >= end) throw 1;
128       code |= GetUi16(cur);
129       cur += 2;
130     }
131   }
132 
DecodeCRangeDecoder133   unsigned Decode(UInt32 *state, UInt32 numStates, struct CProbEntry *probs)
134   {
135     UInt32 st = *state;
136     CProbEntry *entry = &probs[st];
137     st = (st << 1) & (numStates - 1);
138 
139     const UInt32 prob = entry->GetProb();
140 
141     if (range <= 0xFFFF)
142     {
143       range <<= 16;
144       code <<= 16;
145       // if (cur >= end) throw 1;
146       code |= GetUi16(cur);
147       cur += 2;
148     }
149 
150     const UInt32 bound = (range >> k_NumProbBits) * prob;
151 
152     if (code < bound)
153     {
154       range = bound;
155       *state = st;
156       entry->Update(0);
157       return 0;
158     }
159     else
160     {
161       range -= bound;
162       code -= bound;
163       *state = st | 1;
164       entry->Update(1);
165       return 1;
166     }
167   }
168 };
169 
170 
171 class CDecoder
172 {
173   // CRangeDecoder _rc;
174   size_t _pos;
175 
176   UInt32 _reps[k_NumReps + 1];
177   UInt64 _deltaReps[k_NumReps + 1];
178 
179   UInt32 mainState;
180   UInt32 matchState;
181   UInt32 lzRepStates[k_NumReps];
182   UInt32 deltaRepStates[k_NumReps];
183 
184   struct CProbEntry mainProbs[k_NumMainProbs];
185   struct CProbEntry matchProbs[k_NumMatchProbs];
186 
187   struct CProbEntry lzRepProbs[k_NumReps][k_NumRepProbs];
188   struct CProbEntry deltaRepProbs[k_NumReps][k_NumRepProbs];
189 
190   CHuffDecoder<k_NumLitSyms, 1024, 9> m_LitDecoder;
191   CHuffDecoder<k_NumPosSyms, 1024, 9> m_PosDecoder;
192   CHuffDecoder<k_NumLenSyms, 512, 8> m_LenDecoder;
193   CHuffDecoder<k_NumPowerSyms, 512, 6> m_PowerDecoder;
194   CHuffDecoder<k_NumPosSyms, 1024, 9> m_DeltaDecoder;
195 
196   Int32 *_x86_history;
197 
198   HRESULT CodeReal(const Byte *in, size_t inSize, Byte *out, size_t outSize);
199 public:
200   CDecoder();
201   ~CDecoder();
202 
203   HRESULT Code(const Byte *in, size_t inSize, Byte *out, size_t outSize);
GetUnpackSize()204   size_t GetUnpackSize() const { return _pos; }
205 };
206 
207 }}
208 
209 #endif
210