mirror of
https://github.com/MacPaw/XADMaster.wiki
synced 2025-08-29 10:43:58 +02:00
15 lines
No EOL
972 B
Markdown
15 lines
No EOL
972 B
Markdown
# Description #
|
|
|
|
This algorithm simply uses Huffman encoding to encode individual bytes. The data begins with a header specifying the Huffman tree, followed by a bit stream of Huffman codes. All values are read most significant bit first, starting from the most significant bit of each consecutive byte.
|
|
|
|
# Header #
|
|
|
|
The bit stream begins with a header encoding the tree of Huffman codes. To read it, read the root node using this node-reading algorithm:
|
|
|
|
* Read a single bit from the input stream.
|
|
* If this bit is 1, the node being read is a leaf node. Read 8 bits to find the byte value of this leaf.
|
|
* If the bit is 0, the node being read is a branch node. Read the 0-branch node followed by the 1-branch node.
|
|
|
|
# Decoding #
|
|
|
|
To read a byte from the input stream, start at the top node of the Huffman tree. Read a bit, and take the 0 or 1 branch of the tree depending. When you end up at a leaf node, you have the byte value. Do this for all bytes in the stream. |