1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 // Based on xoreos' Huffman code
24
25 #ifndef COMMON_HUFFMAN_H
26 #define COMMON_HUFFMAN_H
27
28 #include "common/array.h"
29 #include "common/list.h"
30 #include "common/types.h"
31
32 namespace Common {
33
34 /**
35 * @defgroup common_huffmann Huffman bit stream decoding
36 * @ingroup common
37 *
38 * @brief API for operations related to Huffman bit stream decoding.
39 *
40 * @details Used in engines:
41 * - SCUMM
42 *
43 * @{
44 */
45
REVERSEBITS(uint32 x)46 inline uint32 REVERSEBITS(uint32 x) {
47 x = (((x & ~0x55555555) >> 1) | ((x & 0x55555555) << 1));
48 x = (((x & ~0x33333333) >> 2) | ((x & 0x33333333) << 2));
49 x = (((x & ~0x0F0F0F0F) >> 4) | ((x & 0x0F0F0F0F) << 4));
50 x = (((x & ~0x00FF00FF) >> 8) | ((x & 0x00FF00FF) << 8));
51
52 return((x >> 16) | (x << 16));
53 }
54
55 /**
56 * Huffman bit stream decoding.
57 *
58 */
59 template<class BITSTREAM>
60 class Huffman {
61 public:
62 /** Construct a Huffman decoder.
63 *
64 * @param maxLength Maximal code length. If 0, it is searched for.
65 * @param codeCount Number of codes.
66 * @param codes The actual codes.
67 * @param lengths Lengths of the individual codes.
68 * @param symbols The symbols. If 0, assume they are identical to the code indices.
69 */
70 Huffman(uint8 maxLength, uint32 codeCount, const uint32 *codes, const uint8 *lengths, const uint32 *symbols = nullptr);
71
72 /** Return the next symbol in the bit stream. */
73 uint32 getSymbol(BITSTREAM &bits) const;
74
75 private:
76 struct Symbol {
77 uint32 code;
78 uint32 symbol;
79
SymbolSymbol80 Symbol(uint32 c, uint32 s) : code(c), symbol(s) {}
81 };
82
83 typedef List<Symbol> CodeList;
84 typedef Array<CodeList> CodeLists;
85
86 /** Lists of codes and their symbols, sorted by code length. */
87 CodeLists _codes;
88
89 /** Prefix lookup table used to speed up the decoding of short codes. */
90 struct PrefixEntry {
91 uint32 symbol;
92 uint8 length;
93
PrefixEntryPrefixEntry94 PrefixEntry() : length(0xFF) {}
95 };
96
97 static const uint8 _prefixTableBits = 8;
98 PrefixEntry _prefixTable[1 << _prefixTableBits];
99 };
100
101 template <class BITSTREAM>
Huffman(uint8 maxLength,uint32 codeCount,const uint32 * codes,const uint8 * lengths,const uint32 * symbols)102 Huffman<BITSTREAM>::Huffman(uint8 maxLength, uint32 codeCount, const uint32 *codes, const uint8 *lengths, const uint32 *symbols) {
103 assert(codeCount > 0);
104
105 assert(codes);
106 assert(lengths);
107
108 if (maxLength == 0)
109 for (uint32 i = 0; i < codeCount; i++)
110 maxLength = MAX(maxLength, lengths[i]);
111
112 assert(maxLength <= 32);
113
114 // Codes that do not fit in the prefix table are stored in the _codes array.
115 _codes.resize(MAX(maxLength - _prefixTableBits, 0));
116
117 for (uint i = 0; i < codeCount; i++) {
118 uint8 length = lengths[i];
119
120 // The symbol. If none was specified, assume it is identical to the code index.
121 uint32 symbol = symbols ? symbols[i] : i;
122
123 if (length <= _prefixTableBits) {
124 // Short codes go in the prefix lookup table. Set all the entries in the table
125 // with an index starting with the code to the symbol value.
126 uint32 startIndex;
127 if (BITSTREAM::isMSB2LSB()) {
128 startIndex = codes[i] << (_prefixTableBits - length);
129 } else {
130 startIndex = REVERSEBITS(codes[i]) >> (32 - _prefixTableBits);
131 }
132
133 uint32 endIndex = startIndex | ((1 << (_prefixTableBits - length)) - 1);
134
135 for (uint32 j = startIndex; j <= endIndex; j++) {
136 uint32 index = BITSTREAM::isMSB2LSB() ? j : REVERSEBITS(j) >> (32 - _prefixTableBits);
137 _prefixTable[index].symbol = symbol;
138 _prefixTable[index].length = length;
139 }
140 } else {
141 // Put the code and symbol into the correct list for the length.
142 _codes[lengths[i] - 1 - _prefixTableBits].push_back(Symbol(codes[i], symbol));
143 }
144 }
145 }
146
147 template <class BITSTREAM>
getSymbol(BITSTREAM & bits)148 uint32 Huffman<BITSTREAM>::getSymbol(BITSTREAM &bits) const {
149 uint32 code = bits.peekBits(_prefixTableBits);
150
151 uint8 length = _prefixTable[code].length;
152
153 if (length != 0xFF) {
154 bits.skip(length);
155 return _prefixTable[code].symbol;
156 } else {
157 bits.skip(_prefixTableBits);
158
159 for (uint32 i = 0; i < _codes.size(); i++) {
160 bits.addBit(code, i + _prefixTableBits);
161
162 for (typename CodeList::const_iterator cCode = _codes[i].begin(); cCode != _codes[i].end(); ++cCode)
163 if (code == cCode->code)
164 return cCode->symbol;
165 }
166 }
167
168 error("Unknown Huffman code");
169 return 0;
170 }
171
172 /** @} */
173
174 } // End of namespace Common
175
176 #endif // COMMON_HUFFMAN_H
177