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