View source for SCI/Specifications/Resource files/Decompression algorithms/HUFFMAN

== Decompression algorithm HUFFMAN ==

This is an implementation of a simple huffman token decoder, which looks up tokens in a huffman tree. A huffman tree is a hollow binary search tree. This means that all inner nodes, usually including the root, are empty, and have two siblings. The tree’s leaves contain the actual information.

<syntax type="pascal">
FUNCTION get_next_bit(): Boolean;
/* This function reads the next bit from the input stream. Reading starts at the MSB. */


FUNCTION get_next_byte(): Byte
VAR
    i: Integer;
    literal: Byte;
BEGIN
    literal := 0;
    FOR i := 0 to 7 DO
        literal := (literal &lt;&lt; 1) | get_next_bit();
    OD
    RETURN literal;
END


FUNCTION get_next_char(nodelist : Array of Nodes, index : Integer): (Char, Boolean)
VAR
    left, right: Integer;
    literal : Char;
    node : Node;
BEGIN
    Node := nodelist[index];

    IF node.siblings == 0 THEN
        RETURN (node.value, False);
    ELSE BEGIN
       left := (node.siblings &amp; 0xf0) &gt;&gt; 4;
       right := (node.siblings &amp; 0x0f);

       IF get_next_bit() THEN BEGIN
           IF right == 0 THEN /* Literal token */
               literal := ByteToChar(get_next_byte());

               RETURN (literal, True);
           ELSE
               RETURN get_next_char(nodelist, index + right)
        END ELSE
                RETURN get_next_char(nodelist, index + left)
    END
END
</syntax>

The function get_next_char() is executed until its second return value is True (i.e. if a value was read directly from the input stream) while the first return value equals a certain terminator character, which is the first byte stored in the compressed resource:

{| border="1"  cellspacing="0" cellpadding="5"
|+
|'''Offset'''
|'''Name'''
|'''Meaning'''
|----
|0
|terminator
|Terminator character
|----
|1
|nodes
|Number of nodes
|----
|2+i*2
|nodelist[i].value
|Value of node #i (0 ≤; i ≤
|----
|3 + i*2
|nodelist[i].siblings
|Siblings nodes of node #i
|----
|2+
|data[]
|The actual compressed data
|----
|}