Rice Decompress

Rice is data compression algorithm. This is most useful for compressing data like image and audio.

									private const int RICE_HISTORY = 16;
private const int RICE_THRESHOLD = 8;

public class BitStream {
	public byte[] BytePointer;
	public uint BitPosition;
	public uint NumBytes;
}

private static int numBits(uint x)
{
	int n;
	for (n = 32; !Convert.ToBoolean(x & 0x80000000) && (n > 0); --n) x <<= 1;
	return n;
}

private static void initBitStream(ref BitStream stream, byte[] buffer, uint bytes)
{
	stream.BytePointer = buffer;
	stream.BitPosition = 0;
	stream.NumBytes = bytes;
}

private static int readBit(ref BitStream stream)
{
	uint x;
	uint index = stream.BitPosition >> 3;

	if (index < stream.NumBytes)
	{
		uint bit = 7 - (stream.BitPosition & 7);
		x = (uint)((stream.BytePointer[index] >> (int)bit) & 1);
		++stream.BitPosition;
	}
	else
	{
		x = 0;
	}

	return (int)x;
}

private static uint decodeWord(int k, ref BitStream stream)
{
	uint x;
	uint q = 0;
	int i;

	while (Convert.ToBoolean(readBit(ref stream)))
	{
		++q;
	}

	if (q > RICE_THRESHOLD)
	{
		int o = (int)(q - RICE_THRESHOLD);
		x = 1;

		for (i = 0; i < o - 1; ++i)
		{
			x = (uint)((int)(x << 1) | readBit(ref stream));
		}

		x += RICE_THRESHOLD;
	}
	else
	{
		x = q;
	}

	for (i = k - 1; i >= 0; --i)
	{
		x = (uint)((int)(x << 1) | readBit(ref stream));
	}

	return x;
}

public static void Decompress(byte[] input, byte[] output, uint inputSize, uint outputSize)
{
	BitStream stream = new BitStream();
	uint i, x, k, wordSize = 8;
	uint[] histogram = new uint[RICE_HISTORY];
	int j;

	uint outputCount = outputSize / (wordSize >> 3);

	if (outputCount == 0)
	{
		return;
	}

	initBitStream(ref stream, input, inputSize);
	k = (uint)input[0];
	stream.BitPosition = 8;

	if (k == 0)
	{
		for (i = 0; i < outputCount; ++i)
		{
			x = 0;

			for (j = (int)wordSize - 1; j >= 0; --j)
			{
				x = (uint)((int)(x << 1) | readBit(ref stream));
			}

			output[i] = (byte)x;
		}
	}
	else
	{
		for (i = 0; i < outputCount; ++i)
		{
			if (i >= RICE_HISTORY)
			{
				k = 0;

				for (j = 0; j < RICE_HISTORY; ++j)
				{
					k += histogram[j];
				}

				k = (k + (RICE_HISTORY >> 1)) / RICE_HISTORY;
			}

			x = decodeWord((int)k, ref stream);
			output[i] = (byte)x;
			histogram[i % RICE_HISTORY] = (uint)numBits(x);
		}
	}
}

Example

									byte[] decompressedData = new byte[originalDataSize];

Decompress(compressedData, decompressedData, (uint)compressedDataSize, originalDataSize);