|
rlm@1
|
1 // ImplodeHuffmanDecoder.cpp
|
|
rlm@1
|
2
|
|
rlm@1
|
3 #include "StdAfx.h"
|
|
rlm@1
|
4
|
|
rlm@1
|
5 #include "ImplodeHuffmanDecoder.h"
|
|
rlm@1
|
6
|
|
rlm@1
|
7 namespace NCompress {
|
|
rlm@1
|
8 namespace NImplode {
|
|
rlm@1
|
9 namespace NHuffman {
|
|
rlm@1
|
10
|
|
rlm@1
|
11 CDecoder::CDecoder(UInt32 numSymbols):
|
|
rlm@1
|
12 m_NumSymbols(numSymbols)
|
|
rlm@1
|
13 {
|
|
rlm@1
|
14 m_Symbols = new UInt32[m_NumSymbols];
|
|
rlm@1
|
15 }
|
|
rlm@1
|
16
|
|
rlm@1
|
17 CDecoder::~CDecoder()
|
|
rlm@1
|
18 {
|
|
rlm@1
|
19 delete []m_Symbols;
|
|
rlm@1
|
20 }
|
|
rlm@1
|
21
|
|
rlm@1
|
22 bool CDecoder::SetCodeLengths(const Byte *codeLengths)
|
|
rlm@1
|
23 {
|
|
rlm@1
|
24 // int lenCounts[kNumBitsInLongestCode + 1], tmpPositions[kNumBitsInLongestCode + 1];
|
|
rlm@1
|
25 int lenCounts[kNumBitsInLongestCode + 2], tmpPositions[kNumBitsInLongestCode + 1];
|
|
rlm@1
|
26 int i;
|
|
rlm@1
|
27 for(i = 0; i <= kNumBitsInLongestCode; i++)
|
|
rlm@1
|
28 lenCounts[i] = 0;
|
|
rlm@1
|
29 UInt32 symbolIndex;
|
|
rlm@1
|
30 for (symbolIndex = 0; symbolIndex < m_NumSymbols; symbolIndex++)
|
|
rlm@1
|
31 lenCounts[codeLengths[symbolIndex]]++;
|
|
rlm@1
|
32 // lenCounts[0] = 0;
|
|
rlm@1
|
33
|
|
rlm@1
|
34 // tmpPositions[0] = m_Positions[0] = m_Limitits[0] = 0;
|
|
rlm@1
|
35 m_Limitits[kNumBitsInLongestCode + 1] = 0;
|
|
rlm@1
|
36 m_Positions[kNumBitsInLongestCode + 1] = 0;
|
|
rlm@1
|
37 lenCounts[kNumBitsInLongestCode + 1] = 0;
|
|
rlm@1
|
38
|
|
rlm@1
|
39
|
|
rlm@1
|
40 UInt32 startPos = 0;
|
|
rlm@1
|
41 static const UInt32 kMaxValue = (1 << kNumBitsInLongestCode);
|
|
rlm@1
|
42
|
|
rlm@1
|
43 for (i = kNumBitsInLongestCode; i > 0; i--)
|
|
rlm@1
|
44 {
|
|
rlm@1
|
45 startPos += lenCounts[i] << (kNumBitsInLongestCode - i);
|
|
rlm@1
|
46 if (startPos > kMaxValue)
|
|
rlm@1
|
47 return false;
|
|
rlm@1
|
48 m_Limitits[i] = startPos;
|
|
rlm@1
|
49 m_Positions[i] = m_Positions[i + 1] + lenCounts[i + 1];
|
|
rlm@1
|
50 tmpPositions[i] = m_Positions[i] + lenCounts[i];
|
|
rlm@1
|
51
|
|
rlm@1
|
52 }
|
|
rlm@1
|
53
|
|
rlm@1
|
54 // if _ZIP_MODE do not throw exception for trees containing only one node
|
|
rlm@1
|
55 // #ifndef _ZIP_MODE
|
|
rlm@1
|
56 if (startPos != kMaxValue)
|
|
rlm@1
|
57 return false;
|
|
rlm@1
|
58 // #endif
|
|
rlm@1
|
59
|
|
rlm@1
|
60 for (symbolIndex = 0; symbolIndex < m_NumSymbols; symbolIndex++)
|
|
rlm@1
|
61 if (codeLengths[symbolIndex] != 0)
|
|
rlm@1
|
62 m_Symbols[--tmpPositions[codeLengths[symbolIndex]]] = symbolIndex;
|
|
rlm@1
|
63 return true;
|
|
rlm@1
|
64 }
|
|
rlm@1
|
65
|
|
rlm@1
|
66 UInt32 CDecoder::DecodeSymbol(CInBit *inStream)
|
|
rlm@1
|
67 {
|
|
rlm@1
|
68 UInt32 numBits = 0;
|
|
rlm@1
|
69 UInt32 value = inStream->GetValue(kNumBitsInLongestCode);
|
|
rlm@1
|
70 int i;
|
|
rlm@1
|
71 for(i = kNumBitsInLongestCode; i > 0; i--)
|
|
rlm@1
|
72 {
|
|
rlm@1
|
73 if (value < m_Limitits[i])
|
|
rlm@1
|
74 {
|
|
rlm@1
|
75 numBits = i;
|
|
rlm@1
|
76 break;
|
|
rlm@1
|
77 }
|
|
rlm@1
|
78 }
|
|
rlm@1
|
79 if (i == 0)
|
|
rlm@1
|
80 return 0xFFFFFFFF;
|
|
rlm@1
|
81 inStream->MovePos(numBits);
|
|
rlm@1
|
82 UInt32 index = m_Positions[numBits] +
|
|
rlm@1
|
83 ((value - m_Limitits[numBits + 1]) >> (kNumBitsInLongestCode - numBits));
|
|
rlm@1
|
84 if (index >= m_NumSymbols)
|
|
rlm@1
|
85 return 0xFFFFFFFF;
|
|
rlm@1
|
86 return m_Symbols[index];
|
|
rlm@1
|
87 }
|
|
rlm@1
|
88
|
|
rlm@1
|
89 }}}
|
