Huffman Decompress

Huffman coding is a data compression algorithm. It is based on the idea that frequently-appearing letters should have shorter bit representations and less common letters should have longer representations.

For Huffman Compress algorithm click here.

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

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

#define MAX_TREE_NODES 511

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

typedef struct {
	int Symbol;
	uint32_t Count;
	uint32_t Code;
	uint32_t Bits;
} Symbol;

typedef struct decodeNode {
	struct decodeNode* ChildA;
	struct decodeNode* ChildB;
	int Symbol;
} DecodeNode;

static void initBitstream(BitStream* stream, uint8_t* buffer)
{
	stream->BytePointer = buffer;
	stream->BitPosition = 0;
}

static uint32_t readBit(BitStream* stream)
{
	uint8_t* buffer = stream->BytePointer;
	uint32_t bit = stream->BitPosition;

	uint32_t x = (*buffer & (1 << (7 - bit))) ? 1 : 0;
	bit = (bit + 1) & 7;

	if (!bit)
	{
		++buffer;
	}

	stream->BitPosition = bit;
	stream->BytePointer = buffer;

	return x;
}

static uint32_t read8Bits(BitStream* stream)
{
	uint8_t* buffer = stream->BytePointer;
	uint32_t bit = stream->BitPosition;
	uint32_t x = (*buffer << bit) | (buffer[1] >> (8 - bit));
	++buffer;
	stream->BytePointer = buffer;

	return x;
}

static DecodeNode* recoverTree(DecodeNode* nodes, BitStream* stream, uint32_t* nodenum)
{
	DecodeNode* thisNode;

	thisNode = &nodes[*nodenum];
	*nodenum = *nodenum + 1;
	thisNode->Symbol = -1;
	thisNode->ChildA = (DecodeNode *)0;
	thisNode->ChildB = (DecodeNode *)0;

	if (readBit(stream))
	{
		thisNode->Symbol = read8Bits(stream);
		return thisNode;
	}

	thisNode->ChildA = recoverTree(nodes, stream, nodenum);
	thisNode->ChildB = recoverTree(nodes, stream, nodenum);

	return thisNode;
}

static void Decompress(uint8_t* input, uint8_t* output, uint32_t inputSize, uint32_t outputSize)
{
	DecodeNode nodes[MAX_TREE_NODES], *root, *node;
	BitStream stream;
	uint32_t i, nodeCount;
	uint8_t* buffer;

	if (inputSize < 1)
		return;

	initBitstream(&stream, input);
	nodeCount = 0;
	root = recoverTree(nodes, &stream, &nodeCount);
	buffer = output;

	for (i = 0; i < outputSize; ++i)
	{
		node = root;

		while (node->Symbol < 0)
		{
			if (readBit(&stream))
				node = node->ChildB;
			else
				node = node->ChildA;
		}

		*buffer++ = (uint8_t)node->Symbol;
	}
}
								

Example

									uint8_t* decompressedData = new uint8_t[originalDataSize];

Decompress(compressedData, decompressedData, compressedDataSize, originalDataSize);