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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
/* ScummVM - Graphic Adventure Engine
*
* ScummVM is the legal property of its developers, whose names
* are too numerous to list here. Please refer to the COPYRIGHT
* file distributed with this source distribution.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
*/
// Based on xoreos' Huffman code
#ifndef COMMON_HUFFMAN_H
#define COMMON_HUFFMAN_H
#include "common/array.h"
#include "common/list.h"
#include "common/types.h"
namespace Common {
inline uint32 REVERSEBITS(uint32 x) {
x = (((x & ~0x55555555) >> 1) | ((x & 0x55555555) << 1));
x = (((x & ~0x33333333) >> 2) | ((x & 0x33333333) << 2));
x = (((x & ~0x0F0F0F0F) >> 4) | ((x & 0x0F0F0F0F) << 4));
x = (((x & ~0x00FF00FF) >> 8) | ((x & 0x00FF00FF) << 8));
return((x >> 16) | (x << 16));
}
/**
* Huffman bitstream decoding
*
* Used in engines:
* - scumm
*/
template<class BITSTREAM>
class Huffman {
public:
/** Construct a Huffman decoder.
*
* @param maxLength Maximal code length. If 0, it's searched for.
* @param codeCount Number of codes.
* @param codes The actual codes.
* @param lengths Lengths of the individual codes.
* @param symbols The symbols. If 0, assume they are identical to the code indices.
*/
Huffman(uint8 maxLength, uint32 codeCount, const uint32 *codes, const uint8 *lengths, const uint32 *symbols = nullptr);
/** Return the next symbol in the bitstream. */
uint32 getSymbol(BITSTREAM &bits) const;
private:
struct Symbol {
uint32 code;
uint32 symbol;
Symbol(uint32 c, uint32 s) : code(c), symbol(s) {}
};
typedef List<Symbol> CodeList;
typedef Array<CodeList> CodeLists;
/** Lists of codes and their symbols, sorted by code length. */
CodeLists _codes;
/** Prefix lookup table used to speed up the decoding of short codes. */
struct PrefixEntry {
uint32 symbol;
uint8 length;
PrefixEntry() : length(0xFF) {}
};
static const uint8 _prefixTableBits = 8;
PrefixEntry _prefixTable[1 << _prefixTableBits];
};
template <class BITSTREAM>
Huffman<BITSTREAM>::Huffman(uint8 maxLength, uint32 codeCount, const uint32 *codes, const uint8 *lengths, const uint32 *symbols) {
assert(codeCount > 0);
assert(codes);
assert(lengths);
if (maxLength == 0)
for (uint32 i = 0; i < codeCount; i++)
maxLength = MAX(maxLength, lengths[i]);
assert(maxLength <= 32);
// Codes that don't fit in the prefix table are stored in the _codes array
_codes.resize(MAX(maxLength - _prefixTableBits, 0));
for (uint i = 0; i < codeCount; i++) {
uint8 length = lengths[i];
// The symbol. If none were specified, just assume it's identical to the code index
uint32 symbol = symbols ? symbols[i] : i;
if (length <= _prefixTableBits) {
// Short codes go in the prefix lookup table. Set all the entries in the table
// with an index starting with the code to the symbol value.
uint32 startIndex;
if (BITSTREAM::isMSB2LSB()) {
startIndex = codes[i] << (_prefixTableBits - length);
} else {
startIndex = REVERSEBITS(codes[i]) >> (32 - _prefixTableBits);
}
uint32 endIndex = startIndex | ((1 << (_prefixTableBits - length)) - 1);
for (uint32 j = startIndex; j <= endIndex; j++) {
uint32 index = BITSTREAM::isMSB2LSB() ? j : REVERSEBITS(j) >> (32 - _prefixTableBits);
_prefixTable[index].symbol = symbol;
_prefixTable[index].length = length;
}
} else {
// Put the code and symbol into the correct list for the length
_codes[lengths[i] - 1 - _prefixTableBits].push_back(Symbol(codes[i], symbol));
}
}
}
template <class BITSTREAM>
uint32 Huffman<BITSTREAM>::getSymbol(BITSTREAM &bits) const {
uint32 code = bits.peekBits(_prefixTableBits);
uint8 length = _prefixTable[code].length;
if (length != 0xFF) {
bits.skip(length);
return _prefixTable[code].symbol;
} else {
bits.skip(_prefixTableBits);
for (uint32 i = 0; i < _codes.size(); i++) {
bits.addBit(code, i + _prefixTableBits);
for (typename CodeList::const_iterator cCode = _codes[i].begin(); cCode != _codes[i].end(); ++cCode)
if (code == cCode->code)
return cCode->symbol;
}
}
error("Unknown Huffman code");
return 0;
}
} // End of namespace Common
#endif // COMMON_HUFFMAN_H
|
