Previous | Table of Contents | Next

### The Code

    /*********************** Start of LZSS.C ***********************
    *
    * This is the LZSS module, which implements an LZ77 style compression
    * algorithm. As implemented here it uses a 12 bit index into the sliding
    * window, and a 4 bit length, which is adjusted to reflect phrase
    * lengths of between 2 and 17 bytes.
    */

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    #include "bitio.h"

    /*
    * Various constants used to define the compression parameters. The
    * INDEX_BIT_COUNT tells how many bits we allocate to indices into the
    * text window. This directly determines the WINDOW_SIZE. The
    * LENGTH_BIT_COUNT tells how many bits we allocate for the length of
    * an encode phrase. This determines the size of the look-ahead buffer.
    * The TREE_ROOT is a special node in the tree that always points to
    * the root node of the binary phrase tree. END_OF_STREAM is a special
    * index used to flag the fact that the file has been completely
    * encoded, and there is no more data. UNUSED is the null index for
    * the tree. MOD_WINDOW() is a macro used to perform arithmetic on tree
    * indices.
    *
    */

    #define INDEX_BIT_COUNT       12
    #define LENGTH_BIT_COUNT      4
    #define WINDOW_SIZE           ( 1 << INDEX_BIT_COUNT )
    #define RAW_LOOK_AHEAD_SIZE   ( 1 << LENGTH_BIT_COUNT )
    #define BREAK_EVEN            ( ( 1 + INDEX_BIT_COUNT +
                                  LENGTH_BIT_COUNT ) / 9 )

    #define LOOK_AHEAD_SIZE       (RAW_LOOK_AHEAD_SIZE + BREAK_EVEN)
    #define TREE_ROOT             WINDOW_SIZE
    #define END_OF_STREAM         0
    #define UNUSED                0
    #define MOD_WINDOW( a )       ( ( a ) & ( WINDOW_SIZE - 1 ) )

    char *CompressionName = "LZSS Encoder";
    char *Usage      = "in-file out-file\n\n";

    /*
    * These are the two global data structures used in this program.
    * The window[] array is exactly that, the window of previously seen
    * text, as well as the current look-ahead text. The tree[] structure
    * contains the binary tree of all of the strings in the window sorted
    * in order.
    */

    unsigned char window WINDOW_SIZE ];

    struct {
     int parent;
     int smaller_child;
     int larger_child;
    } tree WINDOW_SIZE + 1 ];

    /*
    * Function prototypes for both ANSI C compilers and their K&R brethren.
    */

    #ifdef __STDC__

    void InitTree( int r );
    void ContractNode( int old_node, int new_node );
    void ReplaceNode( int old_node, int new_node );
    int FindNextNode( int node );
    void DeleteString( int p );
    int AddString( int new_node, int *match_position );
    void CompressFile( FILE *input, BIT_FILE *output,
                       int argc, char *argv[] );
    void ExpandFile( BIT_FILE *input, FILE *output, int argc, char *argv[] );

    #else

    void InitTree();
    void ContractNode();
    void ReplaceNode();
    int FindNextNode();
    void DeleteString();
    int AddString();
    void CompressFile();
    void ExpandFile();

    #endif

    /*
    * Since the tree is static data, it comes up with every node
    * initialized to 0, which is good, since 0 is the UNUSED code.
    * However, to make the tree really usable, a single phrase has to be
    * added to the tree so it has a root node. That is done right here.
    */
    void InitTree( r )
    int r;
    {
     tree[ TREE_ROOT ].larger_child = r;
     tree[ r ].parent = TREE_ROOT;
     tree[ r ].larger_child = UNUSED;
     tree[ r ].smaller_child = UNUSED;
    }

    /*
    * This routine is used when a node is being deleted. The link to
    * its descendant is broken by pulling the descendant in to overlay
    * the existing link.
    */
    void ContractNode( old_node, new_node )
    int old_node;
    int new_node;
    {
     tree[ new_node ].parent = tree[ old_node ]. parent;
     if ( tree[ tree[ old_node ].parent ].larger_child == old_node )
      tree[ tree[ old_node ].parent ].larger_child = new_node;
     else
      tree[ tree[ old_node ].parent ].smaller_child = new_node;
     tree[ old_node ].parent = UNUSED;
    }

    /*
    * This routine is also used when a node is being deleted. However,
    * in this case, it is being replaced by a node that was not previously
    * in the tree.
    */
    void ReplaceNode( old_node, new_node )
    int old_node;
    int new_node;
    {
     int parent;

     parent = tree[ old_node ].parent;
     if ( tree[ parent ].smaller_child == old_node )
      tree[ parent ].smaller_child = new_node;
     else
      tree[ parent ].larger_child = new_node;
     tree[ new_node ] = tree[ old_node ];
     tree[ tree[ new_node ].smaller_child ].parent = new_node;
     tree[ tree[ new_node ].larger_child ].parent = new_node;
     tree[ old_node ].parent = UNUSED;
    }

    /*
    * This routine is used to find the next smallest node after the node
    * argument. It assumes that the node has a smaller child. We find
    * the next smallest child by going to the smaller_child node, then
    * going to the end of the larger_child descendant chain.
    */
    int FindNextNode( node )
    int node;
    {
     int next;

     next = tree[ node ].smaller_child;
     while ( tree[ next ].larger_child != UNUSED )
      next = tree[ next ].larger_child;
     return( next );
    }

    /*
    * This routine performs the classic binary tree deletion algorithm.
    * If the node to be deleted has a null link in either direction, we
    * just pull the non-null link up one to replace the existing link.
    * If both links exist, we instead delete the next link in order, which
    * is guaranteed to have a null link, then replace the node to be deleted
    * with the next link.
    */
    void DeleteString( p )
    int p;
    {
     int replacement;

     if ( tree[ p ].parent == UNUSED )
      return;
     if ( tree[ p ].larger_child == UNUSED )
      ContractNode( p, tree[ p ].smaller_child );
     else if ( tree[ p ].smaller_child == UNUSED )
      ContractNode( p, tree[ p ].larger_child );
     else {
      replacement = FindNextNode( p );
      DeleteString( replacement );
      ReplaceNode( p, replacement );
     }
    }

    /*
    * This where most of the work done by the encoder takes place. This
    * routine is responsible for adding the new node to the binary tree.
    * It also has to find the best match among all the existing nodes in
    * the tree, and return that to the calling routine. To make matters
    * even more complicated, if the new_node has a duplicate in the tree,
    * the old_node is deleted, for reasons of efficiency.
    */

    int AddString( new_node, match_position )
    int mew_node;
    int *match_position;
    {
     int i;
     int test_node;
     int delta;
     int match_length;
     int *child;

     if ( new_node == END_OF_STREAM )
      return( 0 );
     test_node = tree[ TREE_ROOT ].larger_child;
     match_length = 0;
     for ( ; ; ) {
      for ( i = 0 ; i < LOOK_AHEAD_SIZE ; i++ ) {
         delta = window[ MOD_WINDOW( new_node + i ) ] -
             window[ MOD_WINDOW( test_node + i ) ];
         if ( delta != 0 )
             break;
      }
      if ( i >= match_length ) {
       match_length = i;
       *match_position = test_node;
       if ( match_length >= LOOK_AHEAD_SIZE ) {
        ReplaceNode( test_node, new_node );
        return( match_length );
       }
      }
      if ( delta >= 0 )
       child = &tree[ test_node ]. larger_child;
      else
       child = &tree[ test_node ].smaller-child;
      if ( *child == UNUSED ) {
       *child = new_node;
       tree[ new_node ].parent = test_node;
       tree[ new_node ].larger_child = UNUSED;
       tree[ new_node ].smaller_child = UNUSED;
       return( match_length );
      }
      test_node = *child;
     }
    }

    /*
    * This is the compression routine. It has to first load up the look
    * ahead buffer, then go into the main compression loop. The main loop
    * decides whether to output a single character or an index/length
    * token that defines a phrase. Once the character or phrase has been
    * sent out, another loop has to run. The second loop reads in new
    * characters, deletes the strings that are overwritten by the new
    * character, then adds the strings that are created by the new
    * character.
    */

    void CompressFile( input, output, argc, argv )
    FILE *input;
    BIT_FILE *output;
    int argc;
    char *argv[];
    {
     int i;
     int c;
     int look_ahead_bytes;
     int current_position;
     int replace_count;
     int match_length;
     int match_position;

     current_position = 1;
     for ( i = 0 ; i < LOOK_AHEAD_SIZE ; i++ ) {
      if ( ( c = getc( input ) ) == EOF )
       break;
      window[ current_position + i ] = (unsigned char) c;
     }
     look_ahead_bytes = 1;
     InitTree( current_position );
     match_length = 0;
     match_position = 0;
     while ( look_ahead_bytes > 0 ) {
      if ( match_length > look_ahead_bytes )
       match_length = look_ahead_bytes;
      if ( match_length <= BREAK_EVEN ) {
       replace_count = 1;
       OutputBit( output, 1 );
       OutputBits( output,
            (unsigned long)window[ current_position ], 8 );
      } else {
       OutputBit( output, 0 );
       OutputBits( output,
            (unsigned long) match_position, INDEX_BIT_COUNT );
       OutputBits( output,
            (unsigned long) ( match_length - ( BREAK_EVEN + 1 ) ),
            LENGTH_BIT_COUNT );
       replace_count = match_length;
      }
      for ( i = 0 ; i < replace_count ; i++ ) {
       DeleteString( MOD_WINDOW( current_position + LOOK_AHEAD-SIZE ) );
       if ( ( c = getc( input ) ) == EOF )
        look_ahead_bytes--;
       else
        window[ MOD_WINDOW ( current_position + LOOK_AHEAD_SIZE ) ]
                  = (unsigned char) c;
       current position = MOD_WINDOW( current_position + 1 );
       if ( look ahead_bytes )
        match_length = AddString( current_position, &match_position );
      }
     }
     OutputBit( output, 0 );
     OutputBits( output,
             (unsigned long) END_OF_STREAM, INDEX_BIT_COUNT);
     while ( argc-- > 0 )
      printf( "Unknown argument: %s\n", *argv++ );
    }

    /*
    * This is the expansion routine for the LZSS algorithm. All it has
    * to do is read in flag bits, decide whether to read in a character or
    * a index/length pair, and take the appropriate action.
    */

    void ExpandFile( input, output, argc, argv )
    BIT_FILE *input;
    FILE *output;
    int argc;
    char *argv[];
    {
      int i;
      int current_position;
      int c;
      int match_length;
      int match_ position;

      current_position = 1;
      for ( ; ; ) {
       if ( InputBit( input ) ) {
        c = (int) InputBits( input, 8 );
        putc( c, output );
        window[ current_position ] = (unsigned char) c;
        current_position = MOD_WINDOW( current_position + 1 );
       } else {
        match_position = (int) InputBits( input, INDEX_BIT_COUNT );
        if ( match_position == END_OF_STREAM )
         break;
        match_length = (int) InputBits( input, LENGTH_BIT_COUNT );
        match_length += BREAK_EVEN;
       for ( i = 0 ; i <= match_length ; i++ ) {
        c = window[ MOD_WINDOW( match_position + i ) ];
        putc( c, output );
        window[ current_position ] = (unsigned char) c;
        current_position = MOD_WINDOW( current_position + 1 );
       }
      }
     }
     while ( argc-- > 0 )
      printf( "Unknown argument: %s\n", *argv++ );
    }

    /************************* End of LZSS.C *************************/

Previous | Table of Contents | Next