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++

									/*****Please include following header files*****/
// cstdint
/***********************************************/

#define RICE_HISTORY 16
#define RICE_THRESHOLD 8

typedef struct {
	uint8_t* BytePointer;
	uint32_t BitPosition;
	uint32_t NumBytes;
} BitStream;

static int numBits(uint32_t x)
{
	int n;
	for (n = 32; !(x & 0x80000000) && (n > 0); --n) x <<= 1;
	return n;
}

static void initBitStream(BitStream* stream, uint8_t* buffer, uint32_t bytes)
{
	stream->BytePointer = buffer;
	stream->BitPosition = 0;
	stream->NumBytes = bytes;
}

static void writeBit(BitStream* stream, int x)
{
	uint32_t index = stream->BitPosition >> 3;

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

static void encodeWord(uint32_t x, int k, BitStream* stream)
{
	int j;
	uint32_t q = x >> k;

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

		q -= RICE_THRESHOLD;

		int o = numBits(q);

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

		writeBit(stream, 0);

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

		writeBit(stream, 0);
	}

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

static int Compress(uint8_t* input, uint8_t* output, uint32_t inputSize)
{
	BitStream stream;
	uint32_t i, x, k, n, wordSize = 8;
	uint32_t histogram[RICE_HISTORY];
	int j;

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

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

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

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

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

	if (k == 0)
		k = 1;

	output[0] = 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, k, &stream);
		histogram[i % RICE_HISTORY] = numBits(x);
	}

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

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

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

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

Example

									/*****Please include following header files*****/
// cstring
/***********************************************/

char* str = "This is an example for Rice coding";
uint8_t* originalData = (uint8_t*)str;
int originalDataSize = strlen(str);
uint8_t* compressedData = new uint8_t[originalDataSize + 1];

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