Rice Compress

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

For Rice Decompress algorithm click here.

• C#
• VB.Net
• C
• C++

									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 void writeBit(ref BitStream stream, int x)
{
	uint index = stream.BitPosition >> 3;

	if (index < stream.NumBytes)
	{
		uint bit = 7 - (stream.BitPosition & 7);
		uint mask = (uint)(0xff ^ (1 << (int)bit));
		uint set = (uint)((x & 1) << (int)bit);
		stream.BytePointer[index] = (byte)((stream.BytePointer[index] & mask) | set);
		++stream.BitPosition;
	}
}

private static void encodeWord(uint x, int k, ref BitStream stream)
{
	int j;
	uint q = x >> k;

	if (q > RICE_THRESHOLD)
	{
		for (j = 0; j < RICE_THRESHOLD; ++j)
		{
			writeBit(ref stream, 1);
		}

		q -= RICE_THRESHOLD;

		int o = numBits(q);

		for (j = 0; j < o; ++j)
		{
			writeBit(ref stream, 1);
		}

		writeBit(ref stream, 0);

		for (j = o - 2; j >= 0; --j)
		{
			writeBit(ref stream, (int)((q >> j) & 1));
		}
	}
	else
	{
		for (uint i = 0; i < q; ++i)
		{
			writeBit(ref stream, 1);
		}

		writeBit(ref stream, 0);
	}

	for (j = k - 1; j >= 0; --j)
	{
		writeBit(ref stream, (int)((x >> j) & 1));
	}
}

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

	uint incount = inputSize / (wordSize >> 3);

	if (incount == 0)
	{
		return 0;
	}

	initBitStream(ref stream, output, inputSize + 1);
	k = 0;

	for (i = 0; (i < RICE_HISTORY) && (i < incount); ++i)
	{
		n = (uint)numBits(input[i]);
		k += n;
	}

	k = (k + (i >> 1)) / i;

	if (k == 0)
		k = 1;

	output[0] = (byte)k;
	stream.BitPosition = 8;

	for (i = 0; (i < incount) && ((stream.BitPosition >> 3) <= inputSize); ++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 = input[i];
		encodeWord(x, (int)k, ref stream);
		histogram[i % RICE_HISTORY] = (uint)numBits(x);
	}

	if (i < incount)
	{
		output[0] = 0;
		stream.BitPosition = 8;

		for (i = 0; i < incount; ++i)
		{
			x = input[i];

			for (j = (int)wordSize - 1; j >= 0; --j)
			{
				writeBit(ref stream, (int)((x >> j) & 1));
			}
		}
	}

	return (int)((stream.BitPosition + 7) >> 3);
}
								

Example

									string str = "This is an example for Rice coding";
byte[] originalData = Encoding.Default.GetBytes(str);
uint originalDataSize = (uint)str.Length;
byte[] compressedData = new byte[originalDataSize + 1];

int compressedDataSize = Compress(originalData, compressedData, originalDataSize);