ArithmeticDecoder.cs

using System.IO;

/// <summary>
/// Represents an arithmetic decoder.
/// </summary>
public sealed class ArithmeticDecoder
{
	#region Fields

	/// <summary>
	/// Input stream.
	/// </summary>
	private readonly Stream stream;

	/// <summary>
	/// Current low of the coder.
	/// </summary>
	private uint low;

	/// <summary>
	/// Current range of the coder.
	/// </summary>
	private uint range;

	#endregion

	#region Properties

	/// <summary>
	/// Gets a value indicating whether the range decoder is finished.
	/// </summary>
	public bool Finished
	{
		get { return this.low == 0; }
	}

	#endregion

	#region Constructors

	/// <summary>
	/// Creates a new arithmetic decoder reading from the specified stream.
	/// </summary>
	/// <param name="stream">The stream to read from..</param>
	public ArithmeticDecoder(Stream stream)
	{
		this.stream = stream;
	}

	#endregion

	#region Methods

	/// <summary>
	/// Initializes the range decoder, reading a total of 5 bytes from the input stream where the first byte must be 0.
	/// </summary>
	public void Initialize()
	{
		// read the first byte.
		// this is always 0 to simplify the encoder code.
		// this byte COULD be skipped as it does not contribute to the actual coding.
		int input = this.stream.ReadByte();
		if (input < 0)
			throw new EndOfStreamException();
		if (input != 0)
			throw new InvalidDataException("Range decoder corrupted.");

		// initial values.
		this.range = 0xFFFFFFFF;
		this.low = 0;

		// initialize the range and low using the first 4 bytes (in order to fill the 32-bit integer).
		for (int i = 0; i < 4; i++)
		{
			input = this.stream.ReadByte();
			if (input < 0)
				throw new EndOfStreamException();
			this.low = (this.low << 8) | (byte)input;
		}

		// this is a sign of corruption.
		if (this.low == this.range)
			throw new InvalidDataException("Range decoder corrupted.");
	}

	/// <summary>
	/// Renormalizes the range decoder.
	/// </summary>
	private void normalize()
	{
		int input = this.stream.ReadByte();
		if (input < 0)
			throw new EndOfStreamException();

		this.range <<= 8;
		this.low = (this.low << 8) | (byte)input;
	}

	/// <summary>
	/// Decodes a symbol with the given probabilities.
	/// </summary>
	/// <param name="probabilities">The probabilities for all possible values..</param>
	/// <param name="probabilitySum">The sum of all probabilities.</param>
	/// <returns>The decoded value.</returns>
	public uint Decode(uint[] probabilities, uint probabilitySum)
	{
		uint rangeReduced = this.range / probabilitySum;

		// find the symbol whose low is less than the coder's low.
		uint symbol = 0;
		uint symbolRange;
		while (this.low >= (symbolRange = rangeReduced * probabilities[symbol]))
		{
			this.low -= symbolRange;
			symbol++;
		}

		// set range to symbol's range.
		this.range = symbolRange;

		// if the range is getting too small, renormalize.
		while (this.range <= 0xFFFFFFu)
			this.normalize();

		return symbol;
	}

	/// <summary>
	/// Decodes a value without probabilities.
	/// </summary>
	/// <param name="numSymbols">The number of possible values.</param>
	/// <returns>The decoded value.</returns>
	public uint DecodeDirect(uint numSymbols)
	{
		uint rangeReduced = this.range / numSymbols;

		// find the symbol whose low is greater than the coder's low.
		uint symbol = 0;
		while (this.low >= rangeReduced)
		{
			this.low -= rangeReduced;
			if (++symbol >= numSymbols)
				throw new InvalidDataException("Range decoder corrupted.");
		}

		// set range to symbol's range.
		this.range = rangeReduced;

		// if the range is getting too small, renormalize.
		while (this.range <= 0xFFFFFFu)
			this.normalize();

		return symbol;
	}

	/// <summary>
	/// Decodes the specified number of bits without probabilities.
	/// </summary>
	/// <param name="numBits">The number of bits to decode, max. 32.</param>
	/// <returns>The decoded value.</returns>
	public uint DecodeDirectBits(int numBits)
	{
		uint result = 0;

		while (numBits-- > 0)
		{
			// divide range by 2.
			this.range >>= 1;
			this.low -= this.range;

			uint mask = 0 - (this.low >> 31); // 0 if highest bit is not set, 0xFFFFFFFF if highest bit is set.
			this.low += this.range & mask;

			// this is a sign of decoder corruption.
			if (this.low == this.range)
				throw new InvalidDataException("Range decoder corrupted.");

			// if the range is getting too small, renormalize.
			while (this.range <= 0xFFFFFFu)
				this.normalize();

			// add bit to result.
			result <<= 1;
			result += mask + 1;
		}

		return result;
	}

	#endregion
}