diff options
| -rw-r--r-- | common/huffman.cpp | 81 | ||||
| -rw-r--r-- | common/huffman.h | 77 | ||||
| -rw-r--r-- | common/module.mk | 1 |
3 files changed, 159 insertions, 0 deletions
diff --git a/common/huffman.cpp b/common/huffman.cpp new file mode 100644 index 0000000000..668e2216c9 --- /dev/null +++ b/common/huffman.cpp @@ -0,0 +1,81 @@ +/* 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 eos' Huffman code + +#include "common/huffman.h" +#include "common/util.h" +#include "common/textconsole.h" +#include "common/bitstream.h" + +namespace Common { + +Huffman::Symbol::Symbol(uint32 c, uint32 s) : code(c), symbol(s) { +} + + +Huffman::Huffman(uint8 maxLength, uint32 codeCount, const uint32 *codes, const uint8 *lengths, const uint32 *symbols) { + assert(maxLength > 0); + assert(codeCount > 0); + + assert(codes); + assert(lengths); + + _codes.resize(maxLength); + _symbols.resize(codeCount); + + for (uint32 i = 0; i < codeCount; i++) { + // The symbol. If none were specified, just assume it's identical to the code index + uint32 symbol = symbols ? symbols[i] : i; + + // Put the code and symbol into the correct list + _codes[lengths[i] - 1].push_back(Symbol(codes[i], symbol)); + + // And put the pointer to the symbol/code struct into the symbol list. + _symbols[i] = &_codes[lengths[i] - 1].back(); + } +} + +Huffman::~Huffman() { +} + +void Huffman::setSymbols(const uint32 *symbols) { + for (uint32 i = 0; i < _symbols.size(); i++) + _symbols[i]->symbol = symbols ? *symbols++ : i; +} + +uint32 Huffman::getSymbol(BitStream &bits) { + 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; +} + +} // End of namespace Common diff --git a/common/huffman.h b/common/huffman.h new file mode 100644 index 0000000000..9c88a37541 --- /dev/null +++ b/common/huffman.h @@ -0,0 +1,77 @@ +/* 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 eos' Huffman code + +#ifndef COMMON_HUFFMAN_H +#define COMMON_HUFFMAN_H + +#include "common/array.h" +#include "common/list.h" +#include "common/types.h" + +namespace Common { + +class BitStream; + +/** Decode a Huffman'd bitstream. */ +class Huffman { +public: + /** Construct a Huffman decoder. + * + * @param maxLength Maximal code length. + * @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 = 0); + ~Huffman(); + + /** Modify the codes' symbols. */ + void setSymbols(const uint32 *symbols = 0); + + /** Return the next symbol in the bitstream. */ + uint32 getSymbol(BitStream &bits); + +private: + struct Symbol { + uint32 code; + uint32 symbol; + + Symbol(uint32 c, uint32 s); + }; + + typedef Common::List<Symbol> CodeList; + typedef Common::Array<CodeList> CodeLists; + typedef Common::Array<Symbol *> SymbolList; + + /** Lists of codes and their symbols, sorted by code length. */ + CodeLists _codes; + + /** Sorted list of pointers to the symbols. */ + SymbolList _symbols; +}; + +} // End of namespace Common + +#endif // COMMON_HUFFMAN_H diff --git a/common/module.mk b/common/module.mk index d2791c4f9d..7716f74d34 100644 --- a/common/module.mk +++ b/common/module.mk @@ -13,6 +13,7 @@ MODULE_OBJS := \ file.o \ fs.o \ hashmap.o \ + huffman.o \ iff_container.o \ macresman.o \ math.o \ |