|
rlm@1
|
1 // Compress/HuffmanDecoder.h
|
|
rlm@1
|
2
|
|
rlm@1
|
3 #ifndef __COMPRESS_HUFFMAN_DECODER_H
|
|
rlm@1
|
4 #define __COMPRESS_HUFFMAN_DECODER_H
|
|
rlm@1
|
5
|
|
rlm@1
|
6 #include "../../Common/Types.h"
|
|
rlm@1
|
7
|
|
rlm@1
|
8 namespace NCompress {
|
|
rlm@1
|
9 namespace NHuffman {
|
|
rlm@1
|
10
|
|
rlm@1
|
11 const int kNumTableBits = 9;
|
|
rlm@1
|
12
|
|
rlm@1
|
13 template <int kNumBitsMax, UInt32 m_NumSymbols>
|
|
rlm@1
|
14 class CDecoder
|
|
rlm@1
|
15 {
|
|
rlm@1
|
16 UInt32 m_Limits[kNumBitsMax + 1]; // m_Limits[i] = value limit for symbols with length = i
|
|
rlm@1
|
17 UInt32 m_Positions[kNumBitsMax + 1]; // m_Positions[i] = index in m_Symbols[] of first symbol with length = i
|
|
rlm@1
|
18 UInt32 m_Symbols[m_NumSymbols];
|
|
rlm@1
|
19 Byte m_Lengths[1 << kNumTableBits]; // Table oh length for short codes.
|
|
rlm@1
|
20
|
|
rlm@1
|
21 public:
|
|
rlm@1
|
22
|
|
rlm@1
|
23 bool SetCodeLengths(const Byte *codeLengths)
|
|
rlm@1
|
24 {
|
|
rlm@1
|
25 int lenCounts[kNumBitsMax + 1];
|
|
rlm@1
|
26 UInt32 tmpPositions[kNumBitsMax + 1];
|
|
rlm@1
|
27 int i;
|
|
rlm@1
|
28 for(i = 1; i <= kNumBitsMax; i++)
|
|
rlm@1
|
29 lenCounts[i] = 0;
|
|
rlm@1
|
30 UInt32 symbol;
|
|
rlm@1
|
31 for (symbol = 0; symbol < m_NumSymbols; symbol++)
|
|
rlm@1
|
32 {
|
|
rlm@1
|
33 int len = codeLengths[symbol];
|
|
rlm@1
|
34 if (len > kNumBitsMax)
|
|
rlm@1
|
35 return false;
|
|
rlm@1
|
36 lenCounts[len]++;
|
|
rlm@1
|
37 m_Symbols[symbol] = 0xFFFFFFFF;
|
|
rlm@1
|
38 }
|
|
rlm@1
|
39 lenCounts[0] = 0;
|
|
rlm@1
|
40 m_Positions[0] = m_Limits[0] = 0;
|
|
rlm@1
|
41 UInt32 startPos = 0;
|
|
rlm@1
|
42 UInt32 index = 0;
|
|
rlm@1
|
43 const UInt32 kMaxValue = (1 << kNumBitsMax);
|
|
rlm@1
|
44 for (i = 1; i <= kNumBitsMax; i++)
|
|
rlm@1
|
45 {
|
|
rlm@1
|
46 startPos += lenCounts[i] << (kNumBitsMax - i);
|
|
rlm@1
|
47 if (startPos > kMaxValue)
|
|
rlm@1
|
48 return false;
|
|
rlm@1
|
49 m_Limits[i] = (i == kNumBitsMax) ? kMaxValue : startPos;
|
|
rlm@1
|
50 m_Positions[i] = m_Positions[i - 1] + lenCounts[i - 1];
|
|
rlm@1
|
51 tmpPositions[i] = m_Positions[i];
|
|
rlm@1
|
52 if(i <= kNumTableBits)
|
|
rlm@1
|
53 {
|
|
rlm@1
|
54 UInt32 limit = (m_Limits[i] >> (kNumBitsMax - kNumTableBits));
|
|
rlm@1
|
55 for (; index < limit; index++)
|
|
rlm@1
|
56 m_Lengths[index] = (Byte)i;
|
|
rlm@1
|
57 }
|
|
rlm@1
|
58 }
|
|
rlm@1
|
59 for (symbol = 0; symbol < m_NumSymbols; symbol++)
|
|
rlm@1
|
60 {
|
|
rlm@1
|
61 int len = codeLengths[symbol];
|
|
rlm@1
|
62 if (len != 0)
|
|
rlm@1
|
63 m_Symbols[tmpPositions[len]++] = symbol;
|
|
rlm@1
|
64 }
|
|
rlm@1
|
65 return true;
|
|
rlm@1
|
66 }
|
|
rlm@1
|
67
|
|
rlm@1
|
68 template <class TBitDecoder>
|
|
rlm@1
|
69 UInt32 DecodeSymbol(TBitDecoder *bitStream)
|
|
rlm@1
|
70 {
|
|
rlm@1
|
71 int numBits;
|
|
rlm@1
|
72 UInt32 value = bitStream->GetValue(kNumBitsMax);
|
|
rlm@1
|
73 if (value < m_Limits[kNumTableBits])
|
|
rlm@1
|
74 numBits = m_Lengths[value >> (kNumBitsMax - kNumTableBits)];
|
|
rlm@1
|
75 else
|
|
rlm@1
|
76 for (numBits = kNumTableBits + 1; value >= m_Limits[numBits]; numBits++);
|
|
rlm@1
|
77 bitStream->MovePos(numBits);
|
|
rlm@1
|
78 UInt32 index = m_Positions[numBits] +
|
|
rlm@1
|
79 ((value - m_Limits[numBits - 1]) >> (kNumBitsMax - numBits));
|
|
rlm@1
|
80 if (index >= m_NumSymbols)
|
|
rlm@1
|
81 // throw CDecoderException(); // test it
|
|
rlm@1
|
82 return 0xFFFFFFFF;
|
|
rlm@1
|
83 return m_Symbols[index];
|
|
rlm@1
|
84 }
|
|
rlm@1
|
85 };
|
|
rlm@1
|
86
|
|
rlm@1
|
87 }}
|
|
rlm@1
|
88
|
|
rlm@1
|
89 #endif
|
