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

									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 Integer
	Public Count As UInteger
	Public Code As UInteger
	Public Bits As UInteger
End Structure

Public Class DecodeNode
	Public ChildA As DecodeNode
	Public ChildB As DecodeNode
	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(CInt(buffer(stream.Index) << CInt(bit)) Or (CInt(buffer(stream.Index + 1)) >> CInt(8 - bit)))
	stream.Index += 1

	Return x
End Function

Private Shared Function recoverTree(nodes As DecodeNode(), ByRef stream As BitStream, ByRef nodenum As UInteger) As DecodeNode
	Dim thisNode As DecodeNode

	thisNode = nodes(nodenum)
	nodenum = nodenum + 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

	thisNode.ChildA = recoverTree(nodes, stream, nodenum)
	thisNode.ChildB = recoverTree(nodes, stream, nodenum)

	Return thisNode
End Function

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

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

	Dim root As DecodeNode, node As DecodeNode
	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) = node.Symbol And Byte.MaxValue
	Next
End Sub
								

Example

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

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