Rice Decompress

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

									/*****Please include following header files*****/
// stdint.h
/***********************************************/

#define RICE_HISTORY 16
#define RICE_THRESHOLD 8

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

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

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

int readBit(BitStream* stream)
{
	uint32_t x;
	uint32_t index = stream->BitPosition >> 3;

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

	return x;
}

uint32_t decodeWord(int k, BitStream* stream)
{
	uint32_t x;
	uint32_t q = 0;
	int i;

	while (readBit(stream))
	{
		++q;
	}

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

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

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

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

	return x;
}

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

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

	if (outputCount == 0)
	{
		return;
	}

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

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

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

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

Example

									/*****Please include following header files*****/
// stdlib.h
/***********************************************/

uint8_t* decompressedData = (uint8_t*)malloc(originalDataSize);

Decompress(compressedData, decompressedData, compressedDataSize, originalDataSize);