SCI/Specifications/Resource files/Decompression algorithms/HUFFMAN

From ScummVM :: Wiki
< SCI‎ | Specifications‎ | Resource files‎ | Decompression algorithms
Revision as of 09:09, 31 January 2009 by Timofonic (talk | contribs) (Improved table formatting)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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