Shannon–Fano Decompress

Shannon–Fano is data compression algorithm, which replaces each symbol with an alternate binary representation. Common symbols are represented by few bits and uncommon symbols are represented by many bits.

For Shannon–Fano Compress algorithm click here.

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

									private const int MAX_TREE_NODES = 511;

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

public struct Symbol
{
	public uint Sym;
	public uint Count;
	public uint Code;
	public uint Bits;
}

public class TreeNode
{
	public TreeNode ChildA;
	public TreeNode ChildB;
	public int Symbol;
}

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

private static uint readBit(ref BitStream stream)
{
	byte[] buffer = stream.BytePointer;
	uint bit = stream.BitPosition;
	uint x = (uint)(Convert.ToBoolean(buffer[stream.Index] & (1 << (int)(7 - bit))) ? 1 : 0);
	bit = (bit + 1) & 7;

	if (!Convert.ToBoolean(bit))
	{
		++stream.Index;
	}

	stream.BitPosition = bit;

	return x;
}

private static uint read8Bits(ref BitStream stream)
{
	byte[] buffer = stream.BytePointer;
	uint bit = stream.BitPosition;
	uint x = (uint)((buffer[stream.Index] << (int)bit) | (buffer[stream.Index + 1] >> (int)(8 - bit)));
	++stream.Index;

	return x;
}

private static TreeNode recoverTree(TreeNode[] nodes, ref BitStream stream, ref uint nodeNumber)
{
	TreeNode thisNode;

	thisNode = nodes[nodeNumber];
	nodeNumber = nodeNumber + 1;

	thisNode.Symbol = -1;
	thisNode.ChildA = null;
	thisNode.ChildB = null;

	if (Convert.ToBoolean(readBit(ref stream)))
	{
		thisNode.Symbol = (int)read8Bits(ref stream);
		return thisNode;
	}

	if (Convert.ToBoolean(readBit(ref stream)))
	{
		thisNode.ChildA = recoverTree(nodes, ref stream, ref nodeNumber);
	}

	if (Convert.ToBoolean(readBit(ref stream)))
	{
		thisNode.ChildB = recoverTree(nodes, ref stream, ref nodeNumber);
	}

	return thisNode;
}

public static void Decompress(byte[] input, byte[] output, uint inputSize, uint outputSize)
{
	TreeNode[] nodes = new TreeNode[MAX_TREE_NODES];

	for (int counter = 0; counter < nodes.Length; counter++)
	{
		nodes[counter] = new TreeNode();
	}

	TreeNode root, node;
	BitStream stream = new BitStream();
	uint i, nodeCount;
	byte[] buffer;

	if (inputSize < 1) return;

	initBitStream(ref stream, input);

	nodeCount = 0;
	root = recoverTree(nodes, ref stream, ref nodeCount);
	buffer = output;

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

		while (node.Symbol < 0)
		{
			if (Convert.ToBoolean(readBit(ref stream)))
				node = node.ChildB;
			else
				node = node.ChildA;
		}

		buffer[i] = (byte)node.Symbol;
	}
}
								

Example

									byte[] decompressedData = new byte[originalDataSize];

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