diff options
Diffstat (limited to 'common/huffman.h')
-rw-r--r-- | common/huffman.h | 118 |
1 files changed, 94 insertions, 24 deletions
diff --git a/common/huffman.h b/common/huffman.h index b4de5ab483..052c7bf825 100644 --- a/common/huffman.h +++ b/common/huffman.h @@ -20,7 +20,7 @@ * */ -// Based on eos' Huffman code +// Based on xoreos' Huffman code #ifndef COMMON_HUFFMAN_H #define COMMON_HUFFMAN_H @@ -31,12 +31,22 @@ 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. @@ -48,47 +58,107 @@ public: * @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); - ~Huffman(); - - /** Modify the codes' symbols. */ - void setSymbols(const uint32 *symbols = nullptr); /** Return the next symbol in the bitstream. */ - template<class BITSTREAM> - uint32 getSymbol(BITSTREAM &bits) const { - uint32 code = 0; - - for (uint32 i = 0; i < _codes.size(); i++) { - bits.addBit(code, i); - - for (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; - } + uint32 getSymbol(BITSTREAM &bits) const; private: struct Symbol { uint32 code; uint32 symbol; - Symbol(uint32 c, uint32 s); + Symbol(uint32 c, uint32 s) : code(c), symbol(s) {} }; typedef List<Symbol> CodeList; typedef Array<CodeList> CodeLists; - typedef Array<Symbol *> SymbolList; /** Lists of codes and their symbols, sorted by code length. */ CodeLists _codes; - /** Sorted list of pointers to the symbols. */ - SymbolList _symbols; + /** 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 |