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 << 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 & 0xf0) >> 4;
      right := (node.siblings & 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:

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