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