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 MAX_TREE_NODES As Integer = 511

Public Class BitStream
	Public BytePointer As Byte()
	Public BitPosition As UInteger
	Public Index As UInteger
End Class

Public Structure Symbol
	Public Sym As UInteger
	Public Count As UInteger
	Public Code As UInteger
	Public Bits As UInteger
End Structure

Public Class TreeNode
	Public ChildA As TreeNode
	Public ChildB As TreeNode
	Public Symbol As Integer
End Class

Private Shared Sub initBitStream(ByRef stream As BitStream, buffer As Byte())
	stream.BytePointer = buffer
	stream.BitPosition = 0
End Sub

Private Shared Function readBit(ByRef stream As BitStream) As UInteger
	Dim buffer As Byte() = stream.BytePointer
	Dim bit As UInteger = stream.BitPosition
	Dim x As UInteger = CUInt(If(Convert.ToBoolean(buffer(stream.Index) And (1 << CInt(7 - bit))), 1, 0))
	bit = (bit + 1) And 7

	If Not Convert.ToBoolean(bit) Then
		stream.Index += 1
	End If

	stream.BitPosition = bit

	Return x
End Function

Private Shared Function read8Bits(ByRef stream As BitStream) As UInteger
	Dim buffer As Byte() = stream.BytePointer
	Dim bit As UInteger = stream.BitPosition
	Dim x As UInteger = CUInt((buffer(stream.Index) << CInt(bit)) Or (buffer(stream.Index + 1) >> CInt(8 - bit)))
	stream.Index += 1

	Return x
End Function

Private Shared Function recoverTree(nodes As TreeNode(), ByRef stream As BitStream, ByRef nodeNumber As UInteger) As TreeNode
	Dim thisNode As TreeNode

	thisNode = nodes(nodeNumber)
	nodeNumber = nodeNumber + 1

	thisNode.Symbol = -1
	thisNode.ChildA = Nothing
	thisNode.ChildB = Nothing

	If Convert.ToBoolean(readBit(stream)) Then
		thisNode.Symbol = CInt(read8Bits(stream))
		Return thisNode
	End If

	If Convert.ToBoolean(readBit(stream)) Then
		thisNode.ChildA = recoverTree(nodes, stream, nodeNumber)
	End If

	If Convert.ToBoolean(readBit(stream)) Then
		thisNode.ChildB = recoverTree(nodes, stream, nodeNumber)
	End If

	Return thisNode
End Function

Public Shared Sub Decompress(input As Byte(), output As Byte(), inputSize As UInteger, outputSize As UInteger)
	Dim nodes As TreeNode() = New TreeNode(MAX_TREE_NODES - 1) {}

	For counter As Integer = 0 To nodes.Length - 1
		nodes(counter) = New TreeNode()
	Next

	Dim root As TreeNode, node As TreeNode
	Dim stream As New BitStream()
	Dim i As UInteger, nodeCount As UInteger
	Dim buffer As Byte()

	If inputSize < 1 Then
		Return
	End If

	initBitStream(stream, input)

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

	For i = 0 To outputSize - 1
		node = root

		While node.Symbol < 0
			If Convert.ToBoolean(readBit(stream)) Then
				node = node.ChildB
			Else
				node = node.ChildA
			End If
		End While

		buffer(i) = CByte(node.Symbol)
	Next
End Sub
								

Example

									Dim decompressedData As Byte() = New Byte(originalDataSize - 1) {}

Decompress(compressedData, decompressedData, CUInt(compressedDataSize), originalDataSize)