[Scummvm-git-logs] scummvm master -> 0f57aea2df2a1272b57de896e2f6aad80809e5d3

bluegr bluegr at gmail.com
Sat Apr 13 15:24:30 CEST 2019


This automated email contains information about 2 new commits which have been
pushed to the 'scummvm' repo located at https://github.com/scummvm/scummvm .

Summary:
ae9eeb731f COMMON: Rework the BitStream class to improve its performance
0f57aea2df COMMON: Use a prefix table to speed up the Huffman decoder


Commit: ae9eeb731f435d16f2bb9ae69d48ce60c3a47fa3
    https://github.com/scummvm/scummvm/commit/ae9eeb731f435d16f2bb9ae69d48ce60c3a47fa3
Author: Bastien Bouclet (bastien.bouclet at gmail.com)
Date: 2019-04-13T16:24:25+03:00

Commit Message:
COMMON: Rework the BitStream class to improve its performance

* Fixed peekBits not to seek the underlying stream. Seeking can be slow
  when the stream is a file.
* Changed multi-bit  operations to work on multiple bits at once rather
  than iterating over single-bit operations.

This is an almost direct port of a patch for xoreos provided by DrMcCoy.

Changed paths:
    common/bitstream.h
    test/common/bitstream.h


diff --git a/common/bitstream.h b/common/bitstream.h
index 1fbc006..81976ef 100644
--- a/common/bitstream.h
+++ b/common/bitstream.h
@@ -20,7 +20,7 @@
  *
  */
 
-// Based on eos' BitStream implementation
+// Based on xoreos' BitStream implementation
 
 #ifndef COMMON_BITSTREAM_H
 #define COMMON_BITSTREAM_H
@@ -43,14 +43,14 @@ namespace Common {
  * for valueBits, isLE and isMSB2LSB, reads 32bit little-endian values
  * from the data stream and hands out the bits in the order of LSB to MSB.
  */
-template<class STREAM, int valueBits, bool isLE, bool isMSB2LSB>
+template<class STREAM, int valueBits, bool isLE, bool MSB2LSB>
 class BitStreamImpl {
 private:
 	STREAM *_stream;			///< The input stream.
 	DisposeAfterUse::Flag _disposeAfterUse; ///< Should we delete the stream on destruction?
 
-	uint32 _value;   ///< Current value.
-	uint8  _inValue; ///< Position within the current value.
+	uint64 _bitContainer; ///< The currently available bits.
+	uint8  _bitsLeft; ///< Number of bits currently left in the bit container.
 	uint32 _size;    ///< Total bitstream size (in bits)
 	uint32 _pos;     ///< Current bitstream position (in bits)
 
@@ -76,37 +76,76 @@ private:
 		return 0;
 	}
 
-	/** Read the next data value. */
-	inline void readValue() {
-		if (_size - _pos < valueBits)
-			error("BitStreamImpl::readValue(): End of bit stream reached");
+	/** Fill the container with at least min bits. */
+	inline void fillContainer(size_t min) {
+		while (_bitsLeft < min) {
 
-		_value = readData();
-		if (_stream->err() || _stream->eos())
-			error("BitStreamImpl::readValue(): Read error");
+			uint64 data;
+			if (_pos + _bitsLeft + valueBits <= _size) {
+				data = readData();
+			} else {
+				// Peeking data out of bounds is well defined and returns 0 bits.
+				// This is for convenience when using speed-up techniques reading
+				// more bits than actually available. Users should call eos() to
+				// check if data was actually read out of bounds. Peeking out of
+				// bounds does not set the eos flag.
+				data = 0;
+			}
+
+			// Move the data value to the right position in the bit container
+			if (MSB2LSB)
+				_bitContainer |= data << (64 - valueBits - _bitsLeft);
+			else
+				_bitContainer |= data << _bitsLeft;
 
-		// If we're reading the bits MSB first, we need to shift the value to that position
-		if (isMSB2LSB)
-			_value <<= 32 - valueBits;
+			_bitsLeft += valueBits;
 		}
+}
+
+	/** Get n bits from the bit container. */
+	inline static uint32 getNBits(uint64 value, size_t n) {
+		if (n == 0)
+			return 0;
+
+		const size_t toShift = 64 - n;
+
+		if (MSB2LSB)
+			return value >> toShift;
+		else
+			return (value << toShift) >> toShift;
+	}
+
+	/** Skip already read bits. */
+	inline void skipBits(size_t n) {
+		assert(n <= _bitsLeft);
+
+		// Shift to the next bit
+		if (MSB2LSB)
+			_bitContainer <<= n;
+		else
+			_bitContainer >>= n;
+
+		_bitsLeft -= n;
+		_pos += n;
+	}
 
 public:
 	/** Create a bit stream using this input data stream and optionally delete it on destruction. */
 	BitStreamImpl(STREAM *stream, DisposeAfterUse::Flag disposeAfterUse = DisposeAfterUse::NO) :
-		_stream(stream), _disposeAfterUse(disposeAfterUse), _value(0), _inValue(0), _pos(0) {
+	    _stream(stream), _disposeAfterUse(disposeAfterUse), _bitContainer(0), _bitsLeft(0), _pos(0) {
 
 		if ((valueBits != 8) && (valueBits != 16) && (valueBits != 32))
-			error("BitStreamImpl: Invalid memory layout %d, %d, %d", valueBits, isLE, isMSB2LSB);
+			error("BitStreamImpl: Invalid memory layout %d, %d, %d", valueBits, isLE, MSB2LSB);
 
 		_size = (_stream->size() & ~((uint32) ((valueBits >> 3) - 1))) * 8;
 	}
 
 	/** Create a bit stream using this input data stream. */
 	BitStreamImpl(STREAM &stream) :
-		_stream(&stream), _disposeAfterUse(DisposeAfterUse::NO), _value(0), _inValue(0), _pos(0) {
+	    _stream(&stream), _disposeAfterUse(DisposeAfterUse::NO), _bitContainer(0), _bitsLeft(0), _pos(0) {
 
 		if ((valueBits != 8) && (valueBits != 16) && (valueBits != 32))
-			error("BitStreamImpl: Invalid memory layout %d, %d, %d", valueBits, isLE, isMSB2LSB);
+			error("BitStreamImpl: Invalid memory layout %d, %d, %d", valueBits, isLE, MSB2LSB);
 
 		_size = (_stream->size() & ~((uint32) ((valueBits >> 3) - 1))) * 8;
 	}
@@ -116,41 +155,36 @@ public:
 			delete _stream;
 	}
 
-private:
-	uint32 getBit_internal() {
-		// Get the current bit
-		uint32 b = 0;
-		if (isMSB2LSB)
-			b = ((_value & 0x80000000) == 0) ? 0 : 1;
-		else
-			b = ((_value & 1) == 0) ? 0 : 1;
-
-		// Shift to the next bit
-		if (isMSB2LSB)
-			_value <<= 1;
-		else
-			_value >>= 1;
+	/** Read a bit from the bit stream, without changing the stream's position. */
+	uint peekBit() {
+		fillContainer(1);
 
-		return b;
+		return getNBits(_bitContainer, 1);
 	}
 
-public:
 	/** Read a bit from the bit stream. */
-	uint32 getBit() {
-		// Check if we need the next value
-		if (_inValue == 0)
-			readValue();
+	uint getBit() {
+		const uint b = peekBit();
 
-		uint32 b = getBit_internal();
-
-		// Increase the position within the current value
-		_inValue = (_inValue + 1) % valueBits;
-		_pos++;
+		skipBits(1);
 
 		return b;
 	}
 
 	/**
+	 * Read a multi-bit value from the bit stream, without changing the stream's position.
+	 *
+	 * The bit order is the same as in getBits().
+	 */
+	uint32 peekBits(size_t n) {
+		if (n > 32)
+			error("BitStreamImpl::peekBits(): Too many bits requested to be peeked");
+
+		fillContainer(n);
+		return getNBits(_bitContainer, n);
+	}
+
+	/**
 	 * Read a multi-bit value from the bit stream.
 	 *
 	 * The value is read as if just taken as a whole from the bitstream.
@@ -160,91 +194,15 @@ public:
 	 * If the bitstream is MSB2LSB, the 4-bit value would be 0101.
 	 * If the bitstream is LSB2MSB, the 4-bit value would be 0011.
 	 */
-	uint32 getBits(uint8 n) {
-		if (n == 0)
-			return 0;
-
+	uint32 getBits(size_t n) {
 		if (n > 32)
 			error("BitStreamImpl::getBits(): Too many bits requested to be read");
 
-		// Read the number of bits
-		uint32 v = 0;
-
-		uint8 nOrig = n;
-		if (_inValue) {
-			int count = MIN((int)n, valueBits - _inValue);
-			for (int i = 0; i < count; ++i) {
-				if (isMSB2LSB) {
-					v = (v << 1) | getBit_internal();
-				} else {
-					v = (v >> 1) | (getBit_internal() << 31);
-				}
-			}
-
-			n -= count;
-		}
-
-		while (n > 0) {
-			// NB: readValue doesn't care that _inValue is incorrect here
-			readValue();
-
-			int count = MIN((int)n, valueBits);
-			for (int i = 0; i < count; ++i) {
-				if (isMSB2LSB) {
-					v = (v << 1) | getBit_internal();
-				} else {
-					v = (v >> 1) | (getBit_internal() << 31);
-				}
-			}
-
-			n -= count;
-		}
-
-		_inValue = (_inValue + nOrig) % valueBits;
-		_pos += nOrig;
-
-		if (!isMSB2LSB)
-			v >>= (32 - nOrig);
-
-		return v;
-	}
-
-	/** Read a bit from the bit stream, without changing the stream's position. */
-	uint32 peekBit() {
-		uint32 value   = _value;
-		uint8  inValue = _inValue;
-		uint32 curStreamPos  = _stream->pos();
-		uint32 curPos = _pos;
-
-		uint32 v = getBit();
-
-		_pos     = curPos;
-		_stream->seek(curStreamPos);
-		_inValue = inValue;
-		_value   = value;
+		const uint32 b = peekBits(n);
 
-		return v;
-	}
-
-	/**
-	 * Read a multi-bit value from the bit stream, without changing the stream's position.
-	 *
-	 * The bit order is the same as in getBits().
-	 */
-	uint32 peekBits(uint8 n) {
-		uint32 value   = _value;
-		uint8  inValue = _inValue;
-		uint32 curStreamPos  = _stream->pos();
-		uint32 curPos = _pos;
+		skipBits(n);
 
-		uint32 v = getBits(n);
-
-		_pos     = curPos;
-		_stream->seek(curStreamPos);
-		_inValue = inValue;
-		_value   = value;
-
-		return v;
+		return b;
 	}
 
 	/**
@@ -262,7 +220,7 @@ public:
 		if (n >= 32)
 			error("BitStreamImpl::addBit(): Too many bits requested to be read");
 
-		if (isMSB2LSB)
+		if (MSB2LSB)
 			x = (x << 1) | getBit();
 		else
 			x = (x & ~(1 << n)) | (getBit() << n);
@@ -272,21 +230,29 @@ public:
 	void rewind() {
 		_stream->seek(0);
 
-		_value   = 0;
-		_inValue = 0;
-		_pos     = 0;
+		_bitContainer = 0;
+		_bitsLeft     = 0;
+		_pos          = 0;
 	}
 
 	/** Skip the specified amount of bits. */
 	void skip(uint32 n) {
-		while (n-- > 0)
-			getBit();
+		while (n > 32) {
+			fillContainer(32);
+			skipBits(32);
+			n -= 32;
+		}
+
+		fillContainer(n);
+		skipBits(n);
 	}
 
 	/** Skip the bits to closest data value border. */
 	void align() {
-		while (_inValue)
-			getBit();
+		uint32 bitsAfterBoundary = _pos % valueBits;
+		if (bitsAfterBoundary) {
+			skip(valueBits - bitsAfterBoundary);
+		}
 	}
 
 	/** Return the stream position in bits. */
@@ -302,6 +268,10 @@ public:
 	bool eos() const {
 		return _stream->eos() || (_pos >= _size);
 	}
+
+	static bool isMSB2LSB() {
+		return MSB2LSB;
+	}
 };
 
 
diff --git a/test/common/bitstream.h b/test/common/bitstream.h
index 0488169..742f0c1 100644
--- a/test/common/bitstream.h
+++ b/test/common/bitstream.h
@@ -50,7 +50,7 @@ public:
 private:
 	template<class MS, class BS>
 	void tmpl_skip() {
-		byte contents[] = { 'a', 'b' };
+		byte contents[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
 
 		MS ms(contents, sizeof(contents));
 
@@ -61,6 +61,8 @@ private:
 		bs.skip(4);
 		TS_ASSERT_EQUALS(bs.pos(), 9u);
 		TS_ASSERT_EQUALS(bs.getBits(3), 6u);
+		bs.skip(65);
+		TS_ASSERT_EQUALS(bs.pos(), 77u);
 		TS_ASSERT(!bs.eos());
 	}
 public:
@@ -133,7 +135,7 @@ private:
 		TS_ASSERT_EQUALS(bs.pos(), 3u);
 		bs.skip(8);
 		TS_ASSERT_EQUALS(bs.pos(), 11u);
-		TS_ASSERT_EQUALS(bs.peekBits(5), 2u);
+		TS_ASSERT_EQUALS(bs.peekBits(6), 4u);
 		TS_ASSERT(!bs.eos());
 	}
 public:
@@ -203,7 +205,7 @@ private:
 		TS_ASSERT_EQUALS(bs.pos(), 3u);
 		bs.skip(8);
 		TS_ASSERT_EQUALS(bs.pos(), 11u);
-		TS_ASSERT_EQUALS(bs.peekBits(5), 12u);
+		TS_ASSERT_EQUALS(bs.peekBits(20), 12u);
 		TS_ASSERT(!bs.eos());
 	}
 public:
@@ -211,4 +213,46 @@ public:
 		tmpl_peek_bits_lsb<Common::MemoryReadStream, Common::BitStream8LSB>();
 		tmpl_peek_bits_lsb<Common::BitStreamMemoryStream, Common::BitStreamMemory8LSB>();
 	}
+
+private:
+	template<class MS, class BS>
+	void tmpl_align() {
+		byte contents[] = { 'a', 'b' };
+
+		MS ms(contents, sizeof(contents));
+
+		BS bs(ms);
+		TS_ASSERT_EQUALS(bs.pos(), 0u);
+		bs.align();
+		TS_ASSERT_EQUALS(bs.pos(), 0u);
+		bs.skip(3);
+		bs.align();
+		TS_ASSERT_EQUALS(bs.pos(), 8u);
+	}
+public:
+	void test_align() {
+		tmpl_align<Common::MemoryReadStream, Common::BitStream8LSB>();
+		tmpl_align<Common::BitStreamMemoryStream, Common::BitStreamMemory8LSB>();
+	}
+
+private:
+	template<class MS, class BS>
+	void tmpl_align_16() {
+		byte contents[] = { 'a', 'b' };
+
+		MS ms(contents, sizeof(contents));
+
+		BS bs(ms);
+		TS_ASSERT_EQUALS(bs.pos(), 0u);
+		bs.align();
+		TS_ASSERT_EQUALS(bs.pos(), 0u);
+		bs.skip(3);
+		bs.align();
+		TS_ASSERT_EQUALS(bs.pos(), 16u);
+	}
+public:
+	void test_align_16() {
+		tmpl_align_16<Common::MemoryReadStream, Common::BitStream16BELSB>();
+		tmpl_align_16<Common::BitStreamMemoryStream, Common::BitStreamMemory16BELSB>();
+	}
 };


Commit: 0f57aea2df2a1272b57de896e2f6aad80809e5d3
    https://github.com/scummvm/scummvm/commit/0f57aea2df2a1272b57de896e2f6aad80809e5d3
Author: Bastien Bouclet (bastien.bouclet at gmail.com)
Date: 2019-04-13T16:24:25+03:00

Commit Message:
COMMON: Use a prefix table to speed up the Huffman decoder

Symbols for codes shorter than the prefix table index width are stored
in the table. All the entries in the table with an index starting with
the code are set to the symbol value. That way, when decoding it is
possible to get the number of bits corresponding to the table width from
the bitstream and directly find the symbol value. Longer code still need
to be searched for in the codes list.

Changed paths:
  R common/huffman.cpp
    common/huffman.h
    common/module.mk
    image/codecs/svq1.cpp
    image/codecs/svq1.h
    test/common/huffman.h
    video/bink_decoder.cpp
    video/bink_decoder.h
    video/psx_decoder.cpp
    video/psx_decoder.h


diff --git a/common/huffman.cpp b/common/huffman.cpp
deleted file mode 100644
index 3268ddf..0000000
--- a/common/huffman.cpp
+++ /dev/null
@@ -1,71 +0,0 @@
-/* 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(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.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;
-}
-
-} // End of namespace Common
diff --git a/common/huffman.h b/common/huffman.h
index b4de5ab..052c7bf 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
diff --git a/common/module.mk b/common/module.mk
index 6742fef..f456604 100644
--- a/common/module.mk
+++ b/common/module.mk
@@ -49,7 +49,6 @@ MODULE_OBJS += \
 	cosinetables.o \
 	dct.o \
 	fft.o \
-	huffman.o \
 	rdft.o \
 	sinetables.o
 
diff --git a/image/codecs/svq1.cpp b/image/codecs/svq1.cpp
index 2d86070..eba5fb8 100644
--- a/image/codecs/svq1.cpp
+++ b/image/codecs/svq1.cpp
@@ -56,16 +56,16 @@ SVQ1Decoder::SVQ1Decoder(uint16 width, uint16 height) {
 	_last[2] = 0;
 
 	// Setup Variable Length Code Tables
-	_blockType = new Common::Huffman(0, 4, s_svq1BlockTypeCodes, s_svq1BlockTypeLengths);
+	_blockType = new HuffmanDecoder(0, 4, s_svq1BlockTypeCodes, s_svq1BlockTypeLengths);
 
 	for (int i = 0; i < 6; i++) {
-		_intraMultistage[i] = new Common::Huffman(0, 8, s_svq1IntraMultistageCodes[i], s_svq1IntraMultistageLengths[i]);
-		_interMultistage[i] = new Common::Huffman(0, 8, s_svq1InterMultistageCodes[i], s_svq1InterMultistageLengths[i]);
+		_intraMultistage[i] = new HuffmanDecoder(0, 8, s_svq1IntraMultistageCodes[i], s_svq1IntraMultistageLengths[i]);
+		_interMultistage[i] = new HuffmanDecoder(0, 8, s_svq1InterMultistageCodes[i], s_svq1InterMultistageLengths[i]);
 	}
 
-	_intraMean = new Common::Huffman(0, 256, s_svq1IntraMeanCodes, s_svq1IntraMeanLengths);
-	_interMean = new Common::Huffman(0, 512, s_svq1InterMeanCodes, s_svq1InterMeanLengths);
-	_motionComponent = new Common::Huffman(0, 33, s_svq1MotionComponentCodes, s_svq1MotionComponentLengths);
+	_intraMean = new HuffmanDecoder(0, 256, s_svq1IntraMeanCodes, s_svq1IntraMeanLengths);
+	_interMean = new HuffmanDecoder(0, 512, s_svq1InterMeanCodes, s_svq1InterMeanLengths);
+	_motionComponent = new HuffmanDecoder(0, 33, s_svq1MotionComponentCodes, s_svq1MotionComponentLengths);
 }
 
 SVQ1Decoder::~SVQ1Decoder() {
diff --git a/image/codecs/svq1.h b/image/codecs/svq1.h
index 148501d..4a00576 100644
--- a/image/codecs/svq1.h
+++ b/image/codecs/svq1.h
@@ -27,6 +27,7 @@
 #include "image/codecs/codec.h"
 
 namespace Common {
+template <class BITSTREAM>
 class Huffman;
 struct Point;
 }
@@ -53,12 +54,14 @@ private:
 
 	byte *_last[3];
 
-	Common::Huffman *_blockType;
-	Common::Huffman *_intraMultistage[6];
-	Common::Huffman *_interMultistage[6];
-	Common::Huffman *_intraMean;
-	Common::Huffman *_interMean;
-	Common::Huffman *_motionComponent;
+	typedef Common::Huffman<Common::BitStream32BEMSB> HuffmanDecoder;
+
+	HuffmanDecoder *_blockType;
+	HuffmanDecoder *_intraMultistage[6];
+	HuffmanDecoder *_interMultistage[6];
+	HuffmanDecoder *_intraMean;
+	HuffmanDecoder *_interMean;
+	HuffmanDecoder *_motionComponent;
 
 	bool svq1DecodeBlockIntra(Common::BitStream32BEMSB *s, byte *pixels, int pitch);
 	bool svq1DecodeBlockNonIntra(Common::BitStream32BEMSB *s, byte *pixels, int pitch);
diff --git a/test/common/huffman.h b/test/common/huffman.h
index 53353aa..3e3956a 100644
--- a/test/common/huffman.h
+++ b/test/common/huffman.h
@@ -32,7 +32,7 @@ class HuffmanTestSuite : public CxxTest::TestSuite {
 		const uint32 codes[]  = {0x2, 0x3, 0x3, 0x0, 0x2};
 		const uint32 symbols[]  = {0xA, 0xB, 0xC, 0xD, 0xE};
 
-		Common::Huffman h(maxLength, codeCount, codes, lengths, symbols);
+		Common::Huffman<Common::BitStream8MSB> h(maxLength, codeCount, codes, lengths, symbols);
 
 		byte input[] = {0x4F, 0x20};
 		// Provided input...
@@ -78,7 +78,7 @@ class HuffmanTestSuite : public CxxTest::TestSuite {
 		const uint8 lengths[] = {3,3,2,2,2};
 		const uint32 codes[]  = {0x2, 0x3, 0x3, 0x0, 0x2};
 
-		Common::Huffman h(0, codeCount, codes, lengths, 0);
+		Common::Huffman<Common::BitStream8MSB> h(0, codeCount, codes, lengths, 0);
 
 		byte input[] = {0x4F, 0x20};
 		uint32 expected[] = {0, 1, 2, 3, 4, 3 ,3};
@@ -94,51 +94,4 @@ class HuffmanTestSuite : public CxxTest::TestSuite {
 		TS_ASSERT_EQUALS(h.getSymbol(bs), expected[5]);
 		TS_ASSERT_EQUALS(h.getSymbol(bs), expected[6]);
 	}
-
-	void test_get_after_set_symbols() {
-
-		/*
-		 * Another variation of test_get_with_full_symbols.
-		 * I use the setSymbols method to define, a posteriori,
-		 * an alphabet to be used in place of array indices.
-		 * The encoding is, at first,
-		 * 0=010
-		 * 1=011
-		 * 2=11
-		 * 3=00
-		 * 4=10
-		 * (=array indices).
-		 */
-
-		uint32 codeCount = 5;
-		const uint8 lengths[] = {3,3,2,2,2};
-		const uint32 codes[]  = {0x2, 0x3, 0x3, 0x0, 0x2};
-
-		Common::Huffman h(0, codeCount, codes, lengths, 0);
-
-		const uint32 symbols[]  = {0xA, 0xB, 0xC, 0xD, 0xE};
-		h.setSymbols(symbols);
-
-		byte input[] = {0x4F, 0x20};
-		uint32 expected[] = {0xA, 0xB, 0xC, 0xD, 0xE, 0xD, 0xD};
-
-		Common::MemoryReadStream ms(input, sizeof(input));
-		Common::BitStream8MSB bs(ms);
-
-		/* New symbols:
-		 * A=010
-		 * B=011
-		 * C=11
-		 * D=00
-		 * E=10
-		 */
-
-		TS_ASSERT_EQUALS(h.getSymbol(bs), expected[0]);
-		TS_ASSERT_EQUALS(h.getSymbol(bs), expected[1]);
-		TS_ASSERT_EQUALS(h.getSymbol(bs), expected[2]);
-		TS_ASSERT_EQUALS(h.getSymbol(bs), expected[3]);
-		TS_ASSERT_EQUALS(h.getSymbol(bs), expected[4]);
-		TS_ASSERT_EQUALS(h.getSymbol(bs), expected[5]);
-		TS_ASSERT_EQUALS(h.getSymbol(bs), expected[6]);
-	}
 };
diff --git a/video/bink_decoder.cpp b/video/bink_decoder.cpp
index 406c6e4..4074043 100644
--- a/video/bink_decoder.cpp
+++ b/video/bink_decoder.cpp
@@ -594,7 +594,7 @@ void BinkDecoder::BinkVideoTrack::deinitBundles() {
 
 void BinkDecoder::BinkVideoTrack::initHuffman() {
 	for (int i = 0; i < 16; i++)
-		_huffman[i] = new Common::Huffman(binkHuffmanLengths[i][15], 16, binkHuffmanCodes[i], binkHuffmanLengths[i]);
+		_huffman[i] = new Common::Huffman<Common::BitStream32LELSB>(binkHuffmanLengths[i][15], 16, binkHuffmanCodes[i], binkHuffmanLengths[i]);
 }
 
 byte BinkDecoder::BinkVideoTrack::getHuffmanSymbol(VideoFrame &video, Huffman &huffman) {
diff --git a/video/bink_decoder.h b/video/bink_decoder.h
index 29d1602..1169431 100644
--- a/video/bink_decoder.h
+++ b/video/bink_decoder.h
@@ -46,6 +46,7 @@ class QueuingAudioStream;
 
 namespace Common {
 class SeekableReadStream;
+template <class BITSTREAM>
 class Huffman;
 
 class RDFT;
@@ -247,7 +248,7 @@ private:
 
 		Bundle _bundles[kSourceMAX]; ///< Bundles for decoding all data types.
 
-		Common::Huffman *_huffman[16]; ///< The 16 Huffman codebooks used in Bink decoding.
+		Common::Huffman<Common::BitStream32LELSB> *_huffman[16]; ///< The 16 Huffman codebooks used in Bink decoding.
 
 		/** Huffman codebooks to use for decoding high nibbles in color data types. */
 		Huffman _colHighHuffman[16];
diff --git a/video/psx_decoder.cpp b/video/psx_decoder.cpp
index 562da88..ef42a72 100644
--- a/video/psx_decoder.cpp
+++ b/video/psx_decoder.cpp
@@ -438,9 +438,9 @@ PSXStreamDecoder::PSXVideoTrack::PSXVideoTrack(Common::SeekableReadStream *first
 
 	_endOfTrack = false;
 	_curFrame = -1;
-	_acHuffman = new Common::Huffman(0, AC_CODE_COUNT, s_huffmanACCodes, s_huffmanACLengths, s_huffmanACSymbols);
-	_dcHuffmanChroma = new Common::Huffman(0, DC_CODE_COUNT, s_huffmanDCChromaCodes, s_huffmanDCChromaLengths, s_huffmanDCSymbols);
-	_dcHuffmanLuma = new Common::Huffman(0, DC_CODE_COUNT, s_huffmanDCLumaCodes, s_huffmanDCLumaLengths, s_huffmanDCSymbols);
+	_acHuffman = new HuffmanDecoder(0, AC_CODE_COUNT, s_huffmanACCodes, s_huffmanACLengths, s_huffmanACSymbols);
+	_dcHuffmanChroma = new HuffmanDecoder(0, DC_CODE_COUNT, s_huffmanDCChromaCodes, s_huffmanDCChromaLengths, s_huffmanDCSymbols);
+	_dcHuffmanLuma = new HuffmanDecoder(0, DC_CODE_COUNT, s_huffmanDCLumaCodes, s_huffmanDCLumaLengths, s_huffmanDCSymbols);
 }
 
 PSXStreamDecoder::PSXVideoTrack::~PSXVideoTrack() {
@@ -552,7 +552,7 @@ int PSXStreamDecoder::PSXVideoTrack::readDC(Common::BitStreamMemory16LEMSB *bits
 
 	// Version 3 has it stored as huffman codes as a difference from the previous DC value
 
-	Common::Huffman *huffman = (plane == kPlaneY) ? _dcHuffmanLuma : _dcHuffmanChroma;
+	HuffmanDecoder *huffman = (plane == kPlaneY) ? _dcHuffmanLuma : _dcHuffmanChroma;
 
 	uint32 symbol = huffman->getSymbol(*bits);
 	int dc = 0;
diff --git a/video/psx_decoder.h b/video/psx_decoder.h
index c966422..183b6da 100644
--- a/video/psx_decoder.h
+++ b/video/psx_decoder.h
@@ -36,6 +36,7 @@ class QueuingAudioStream;
 }
 
 namespace Common {
+template <class BITSTREAM>
 class Huffman;
 }
 
@@ -105,16 +106,18 @@ private:
 			kPlaneV = 2
 		};
 
+		typedef Common::Huffman<Common::BitStreamMemory16LEMSB> HuffmanDecoder;
+
 		uint16 _macroBlocksW, _macroBlocksH;
 		byte *_yBuffer, *_cbBuffer, *_crBuffer;
 		void decodeMacroBlock(Common::BitStreamMemory16LEMSB *bits, int mbX, int mbY, uint16 scale, uint16 version);
 		void decodeBlock(Common::BitStreamMemory16LEMSB *bits, byte *block, int pitch, uint16 scale, uint16 version, PlaneType plane);
 
 		void readAC(Common::BitStreamMemory16LEMSB *bits, int *block);
-		Common::Huffman *_acHuffman;
+		HuffmanDecoder *_acHuffman;
 
 		int readDC(Common::BitStreamMemory16LEMSB *bits, uint16 version, PlaneType plane);
-		Common::Huffman *_dcHuffmanLuma, *_dcHuffmanChroma;
+		HuffmanDecoder *_dcHuffmanLuma, *_dcHuffmanChroma;
 		int _lastDC[3];
 
 		void dequantizeBlock(int *coefficients, float *block, uint16 scale);





More information about the Scummvm-git-logs mailing list