Previous | Table of Contents | Next |

/*********************** 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 |