1 // Compress/HuffmanDecoder.h
2 
3 #ifndef __COMPRESS_HUFFMAN_DECODER_H
4 #define __COMPRESS_HUFFMAN_DECODER_H
5 
6 #include "../../Common/MyTypes.h"
7 
8 namespace NCompress {
9 namespace NHuffman {
10 
11 const unsigned kNumPairLenBits = 4;
12 const unsigned kPairLenMask = (1 << kNumPairLenBits) - 1;
13 
14 template <unsigned kNumBitsMax, UInt32 m_NumSymbols, unsigned kNumTableBits = 9>
15 class CDecoder
16 {
17 public:
18   UInt32 _limits[kNumBitsMax + 2];
19   UInt32 _poses[kNumBitsMax + 1];
20   UInt16 _lens[1 << kNumTableBits];
21   UInt16 _symbols[m_NumSymbols];
22 
Build(const Byte * lens)23   bool Build(const Byte *lens) throw()
24   {
25     UInt32 counts[kNumBitsMax + 1];
26 
27     unsigned i;
28     for (i = 0; i <= kNumBitsMax; i++)
29       counts[i] = 0;
30 
31     UInt32 sym;
32 
33     for (sym = 0; sym < m_NumSymbols; sym++)
34       counts[lens[sym]]++;
35 
36     const UInt32 kMaxValue = (UInt32)1 << kNumBitsMax;
37 
38     _limits[0] = 0;
39 
40     UInt32 startPos = 0;
41     UInt32 sum = 0;
42 
43     for (i = 1; i <= kNumBitsMax; i++)
44     {
45       const UInt32 cnt = counts[i];
46       startPos += cnt << (kNumBitsMax - i);
47       if (startPos > kMaxValue)
48         return false;
49       _limits[i] = startPos;
50       counts[i] = sum;
51       _poses[i] = sum;
52       sum += cnt;
53     }
54 
55     counts[0] = sum;
56     _poses[0] = sum;
57     _limits[kNumBitsMax + 1] = kMaxValue;
58 
59     for (sym = 0; sym < m_NumSymbols; sym++)
60     {
61       unsigned len = lens[sym];
62       if (len == 0)
63         continue;
64 
65       unsigned offset = counts[len]++;
66       _symbols[offset] = (UInt16)sym;
67 
68       if (len <= kNumTableBits)
69       {
70         offset -= _poses[len];
71         UInt32 num = (UInt32)1 << (kNumTableBits - len);
72         UInt16 val = (UInt16)((sym << kNumPairLenBits) | len);
73         UInt16 *dest = _lens + (_limits[(size_t)len - 1] >> (kNumBitsMax - kNumTableBits)) + (offset << (kNumTableBits - len));
74         for (UInt32 k = 0; k < num; k++)
75           dest[k] = val;
76       }
77     }
78 
79     return true;
80   }
81 
82 
throw()83   bool BuildFull(const Byte *lens, UInt32 numSymbols = m_NumSymbols) throw()
84   {
85     UInt32 counts[kNumBitsMax + 1];
86 
87     unsigned i;
88     for (i = 0; i <= kNumBitsMax; i++)
89       counts[i] = 0;
90 
91     UInt32 sym;
92 
93     for (sym = 0; sym < numSymbols; sym++)
94       counts[lens[sym]]++;
95 
96     const UInt32 kMaxValue = (UInt32)1 << kNumBitsMax;
97 
98     _limits[0] = 0;
99 
100     UInt32 startPos = 0;
101     UInt32 sum = 0;
102 
103     for (i = 1; i <= kNumBitsMax; i++)
104     {
105       const UInt32 cnt = counts[i];
106       startPos += cnt << (kNumBitsMax - i);
107       if (startPos > kMaxValue)
108         return false;
109       _limits[i] = startPos;
110       counts[i] = sum;
111       _poses[i] = sum;
112       sum += cnt;
113     }
114 
115     counts[0] = sum;
116     _poses[0] = sum;
117     _limits[kNumBitsMax + 1] = kMaxValue;
118 
119     for (sym = 0; sym < numSymbols; sym++)
120     {
121       unsigned len = lens[sym];
122       if (len == 0)
123         continue;
124 
125       unsigned offset = counts[len]++;
126       _symbols[offset] = (UInt16)sym;
127 
128       if (len <= kNumTableBits)
129       {
130         offset -= _poses[len];
131         UInt32 num = (UInt32)1 << (kNumTableBits - len);
132         UInt16 val = (UInt16)((sym << kNumPairLenBits) | len);
133         UInt16 *dest = _lens + (_limits[(size_t)len - 1] >> (kNumBitsMax - kNumTableBits)) + (offset << (kNumTableBits - len));
134         for (UInt32 k = 0; k < num; k++)
135           dest[k] = val;
136       }
137     }
138 
139     return startPos == kMaxValue;
140   }
141 
142 
143   template <class TBitDecoder>
144   MY_FORCE_INLINE
Decode(TBitDecoder * bitStream)145   UInt32 Decode(TBitDecoder *bitStream) const
146   {
147     UInt32 val = bitStream->GetValue(kNumBitsMax);
148 
149     if (val < _limits[kNumTableBits])
150     {
151       UInt32 pair = _lens[val >> (kNumBitsMax - kNumTableBits)];
152       bitStream->MovePos((unsigned)(pair & kPairLenMask));
153       return pair >> kNumPairLenBits;
154     }
155 
156     unsigned numBits;
157     for (numBits = kNumTableBits + 1; val >= _limits[numBits]; numBits++);
158 
159     if (numBits > kNumBitsMax)
160       return 0xFFFFFFFF;
161 
162     bitStream->MovePos(numBits);
163     UInt32 index = _poses[numBits] + ((val - _limits[(size_t)numBits - 1]) >> (kNumBitsMax - numBits));
164     return _symbols[index];
165   }
166 
167 
168   template <class TBitDecoder>
169   MY_FORCE_INLINE
DecodeFull(TBitDecoder * bitStream)170   UInt32 DecodeFull(TBitDecoder *bitStream) const
171   {
172     UInt32 val = bitStream->GetValue(kNumBitsMax);
173 
174     if (val < _limits[kNumTableBits])
175     {
176       UInt32 pair = _lens[val >> (kNumBitsMax - kNumTableBits)];
177       bitStream->MovePos((unsigned)(pair & kPairLenMask));
178       return pair >> kNumPairLenBits;
179     }
180 
181     unsigned numBits;
182     for (numBits = kNumTableBits + 1; val >= _limits[numBits]; numBits++);
183 
184     bitStream->MovePos(numBits);
185     UInt32 index = _poses[numBits] + ((val - _limits[(size_t)numBits - 1]) >> (kNumBitsMax - numBits));
186     return _symbols[index];
187   }
188 };
189 
190 
191 
192 template <UInt32 m_NumSymbols>
193 class CDecoder7b
194 {
195   Byte _lens[1 << 7];
196 public:
197 
Build(const Byte * lens)198   bool Build(const Byte *lens) throw()
199   {
200     const unsigned kNumBitsMax = 7;
201 
202     UInt32 counts[kNumBitsMax + 1];
203     UInt32 _poses[kNumBitsMax + 1];
204     UInt32 _limits[kNumBitsMax + 1];
205 
206     unsigned i;
207     for (i = 0; i <= kNumBitsMax; i++)
208       counts[i] = 0;
209 
210     UInt32 sym;
211 
212     for (sym = 0; sym < m_NumSymbols; sym++)
213       counts[lens[sym]]++;
214 
215     const UInt32 kMaxValue = (UInt32)1 << kNumBitsMax;
216 
217     _limits[0] = 0;
218 
219     UInt32 startPos = 0;
220     UInt32 sum = 0;
221 
222     for (i = 1; i <= kNumBitsMax; i++)
223     {
224       const UInt32 cnt = counts[i];
225       startPos += cnt << (kNumBitsMax - i);
226       if (startPos > kMaxValue)
227         return false;
228       _limits[i] = startPos;
229       counts[i] = sum;
230       _poses[i] = sum;
231       sum += cnt;
232     }
233 
234     counts[0] = sum;
235     _poses[0] = sum;
236 
237     for (sym = 0; sym < m_NumSymbols; sym++)
238     {
239       unsigned len = lens[sym];
240       if (len == 0)
241         continue;
242 
243       unsigned offset = counts[len]++;
244 
245       {
246         offset -= _poses[len];
247         UInt32 num = (UInt32)1 << (kNumBitsMax - len);
248         Byte val = (Byte)((sym << 3) | len);
249         Byte *dest = _lens + (_limits[(size_t)len - 1]) + (offset << (kNumBitsMax - len));
250         for (UInt32 k = 0; k < num; k++)
251           dest[k] = val;
252       }
253     }
254 
255     {
256       UInt32 limit = _limits[kNumBitsMax];
257       UInt32 num = ((UInt32)1 << kNumBitsMax) - limit;
258       Byte *dest = _lens + limit;
259       for (UInt32 k = 0; k < num; k++)
260         dest[k] = (Byte)(0x1F << 3);
261     }
262 
263     return true;
264   }
265 
266   template <class TBitDecoder>
Decode(TBitDecoder * bitStream)267   UInt32 Decode(TBitDecoder *bitStream) const
268   {
269     UInt32 val = bitStream->GetValue(7);
270     UInt32 pair = _lens[val];
271     bitStream->MovePos((unsigned)(pair & 0x7));
272     return pair >> 3;
273   }
274 };
275 
276 }}
277 
278 #endif
279