406-456.html

The primary purpose of this book is to explain various data-compression techniques using the C progr

* This routine is called to write out the current Global header block
* to the output CAR file. It employs the same packing mechanism
* discussed earlier. This routine also calculates the CRC of the
* header, which is sometimes not necessary.
*/

void WriteFileHeader()
{
 unsigned char header_data[ 17 ];
 int i;

 for ( i = 0 ; ; ) {
  putc( Header.file_name[ i ], OutputCarFile );
  if ( Header.file_name[ i++ ] == '\0' )
   break;
}
Header.header_crc = CalculateBlockCRC32( i, CRC_MASK,
                     Header.file_name );
PackUnsignedData( 1, (long)
                     Header.compression_method,header_data + 0 );
PackUnsignedData( 4, Header.original_size,    header_data + 1 );
PackUnsignedData( 4, Header.compressed_size,  header_data + 5 );
PackUnsignedData( 4, Header.original_crc,     header_data + 9 );
Header.header_crc = CalculatedBlockCRC32( 13, Header.header_crc,
                                         header_data );
Header.header_crc ^= CRC_MASK;
 PackUnsignedData( 4, Header.header_crc, header_data + 13 );
 fwrite( header_data, 1, 17, OutputCarFile );
}

/*
* This is the routine used to pack integers and longs into a character
* array. The character array is what eventually gets written out to the
* CAR file. The data is always written out with the least significant
* bytes of the integers or long integers going first.
*/

void PackUnsignedData( number_of_bytes, number, buffer )
int number_of_bytes;
unsigned long number;
unsigned char *buffer;
{
 while ( number_of_bytes-- > 0 ) {
  *buffer++ = ( unsigned char ) number & Oxff;
  number >>= 8;
 }
}

/*
* The last header in a CAR file is defined by the fact that it has
* a file name length of zero. Since the file name is the
* first element to be written out, we can create the final header
* by just writing out a null termination character. This technique
* saves a little bit of space.
*/

void WriteEndOfCarHeader()
{
 fputc( 0, OutputCarFile );
}

/*
* This is the routine called by the main processing loop and the
* Addfiles routine. It takes an input file and writes the header and
* file data to the Output CAR file. There are several complications that
* the routine has to deal with. First of all, the header information
* it gets when it first starts is incomplete. For instance, we don't
* know how many bytes the file will take up when it is compressed.
* Because of this, the position of the header is stored, and the
* incomplete copy is written out. After the compression routine finishes,
* the header is now complete. In order to put the correct header into
* the output CAR file, this routine seeks back in the file to the
* original header position and rewrites it.
*
* The second complication lies in the fact that some files are not very
* compressible. In fact, for some files the LZSS algorithm may actually
* cause the file to expand. In these cases, the compression routine
* gives up and passes a failure code back to Insert(). When this
* happens, the routine has to seek back to the start of the file, rewind
* the input file, and store it instead of compressing it. Because of
* this, the starting position of the file in the output CAR file is also
* stored when the routine starts up.
*/

void Insert( input_text_file, operation )
FILE *input_text_file;
char *operation;
{
 long saved_position_of_header;
 long saved_position_of_file;

 fprintf( stderr, "%s %-20s", operation, Header, file_name );
 saved_position_of_header = ftell( OutputCarFile );
 Header.compression_method = 2;
 WriteFileHeader();
 saved_position_of_file = ftell(OutputCarFile);
 fseek( input_text_file, OL, SEEK_END );
 Header.original_size = ftell( input_text_file );
 fseek( input_text_file, OL, SEEK_SET );
 if ( !LZSSCompress( input_text_file ) ) {
  Header.compression_method = 1;
  fseek( OutputCarFile, saved_position_of_file, SEEK_SET );
  rewind( input_text_file );
  Store( input_text_file );
 }
 fclose( input_text_file );
 fseek( OutputCarFile, saved_position_of_header, SEEK_SET );
 WriteFileHeader();
 fseek( OutputCarFile, OL, SEEK_END );
 printf( "%d%%\n", RatioInPercent( Header.compressed_size,
                     Header.original_size ) );
}

/*
* The Extract routine can be called for one of three reasons. If the
* file in the CAR is truly being extracted, Extract() is called with
* no destination specified. In this case, the Extract routine opens the
* file specified in the header and either unstores or decompresses the
* file from the CAR file. If the archive is being tested for veracity,
* the destination file will have been opened up earlier and specified as
* the null device. Finally, the 'Print' option may have been selected,
* in which case the destination file will be extracted to stdout.
*/

void Extract( destination )
FILE *destination;
{
 FILE *output_text_file;
 unsigned long crc;
 int error;

 fprintf( stderr, "%-20s ", Header.file_name );
 error = 0;
 if ( destination == NULL ) {
 if ( ( output_text_file = fopen(Header.file_name, "wb")
                            ) == NULL ) {
  fprintf( stderr, "Can't open %s\n", Header.file_name );
  fprintf( stderr, "Not extracted\n" );
  SkipOverFileFromInputCar();
  return;
 }
} else
 output_text_file = destination;
switch( Header.compression_method ) {
 case 1 :
  crc = Unstore( output_text_file );
  break;
 case 2 :
  crc = LZSSExpand( output_text_file );
  break;
 default :
  fprintf( stderr, "Unknown method: %c\n",
   Header.compression_method );
  SkipOverFileFromInputCar();
  error = 1;
  crc = Header.original_crc;
  break;
 }
 if ( crc != Header.original_crc ) {
  fprintf( stderr, "CRC error reading data\n" );
  error = 1;
 }
 if ( destination == NULL ) {
    fclose( output_text_file );
    if ( error )
#ifdef __STDC__
    remove( Header.file_name );
#else
    unlink( Header.file_name );
#endif
    }
    if ( !error )
    fprintf( stderr, " OK\n" );
}

/*
* The CAR manager program is capable of handling many different forms of
* compression. All the compression program has to do is obey a few
* simple rules. First of all, the compression routine is required
* to calculate the 32-bit CRC of the uncompressed data, and store the
* result in the file Header, so it can be written out by the Insert()
* routine. The expansion routine calculates the CRC of the file it
* creates, and returns it to Extract() for a check against the Header
* value. Second, the compression routine is required to quit if its
* output is going to exceed the length of the input file. It needs to
* quit *before* the output length passes the input, or problems will
* result. The compression routine is required to return a true or false
* value indicating whether or not the compression was a success. And
* finally, the expansion routine is expected to leave the file pointer
* to the Input CAR file positioned at the first byte of the next file
* header. This means it has to read in all the bytes of the compressed
* data, no more or less.
*
* All these things are relatively easy to accomplish for Store() and
* Unstore(), since they do no compression or expansion.
*
*/
int Store( input_text_file )
FILE *input_text_file;
{
 unsigned int n;
 char buffer[ 256 ];
 int pacifier;

 pacifier = 0;
 Header.original_crc = CRC_MASK;

 while ( ( n = fread( buffer, 1, 256, input_text_file ) ) != 0 ) {
  fwrite( buffer, 1, n, OutputCarFile );
  Header.original_crc = CalculateBlockCRC32( n, Header.original_crc,
                                                       buffer );
  if ( ( ++pacifier & 15 ) == 0 )
   putc( '.', stderr );
 }
 Header.compressed_size = Header.original_size;
 Header.original_crc ^= CRC_MASK;
 return( 1 );
}

unsigned long Unstore( destination )
FILE *destination;
{
 unsigned long crc;
 unsigned int count;
 unsigned char buffer[ 256 ];
 int pacifier;

 pacifier = 0;
 crc = CRC_MASK;
 while ( Header.original_size != 0 ) {
  if ( Header.original_size > 256 )
   count = 256;
  else
   count = (int) Header.original_size;
  if ( fread( buffer, 1, count, InputCarFile ) != count )
   FatalError( "Can't read from input CAR file" );
  if ( fwrite( buffer, 1, count, destination ) != count ) {
   fprintf( stderr. "Error writing to output file" );
   return( ~Header.original_crc );
  }
  crc = CalculateBlockCRC32( count, crc, buffer );
  if ( destination != stdout && ( pacifier++ & 15 ) == 0 )
   putc( '.', stderr );
  Header.original_size -= count;
}
 return( crc ^ CRC_MASK );
}

/*
* The second set of compression routines is found here. These
* routines implement LZSS compression and expansion using 12-bit
* index pointers and 4-bit match lengths. These values were
* specifically chosen because they allow for "blocked I/O". Because
* of their values, we can pack match/length pairs into pairs of
* bytes, with characters that don't have matches going into single
* bytes. This helps increase I/O since single bit input and
* output does not have to be employed. Other than this single change,
* this code is identical to the LZSS code used earlier in the book.
*/

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

/*
* 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 InitOutputBuffer( void );
int FlushOutputBuffer( void );
int OutputChar( int data );
int OutputPair( int position, int length );
void InitInputBuffer( void );
int InputBit( void );

#else

void InitTree();
void ContractNode();
void ReplaceNode();
int FindNextNode();
void DeleteString();
int AddString();
void InitOutputBuffer();
int FlushOutputBuffer();
int OutputChar();
int OutputPair();
void InitInputBuffer();
int InputBit();

#endif

void InitTree( r )
int r;
{
 int i;

 for ( i = 0 ; i < ( WINDOW_SIZE + 1 ) ; i++ ) {
  tree[ i].parent = UNUSED;
  tree[ i].larger_child = UNUSED;
  tree[ i].smaller_child = UNUSED;
 }
 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