136-152.html

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

* in a row.
*
* This is simple in concept, but it ends up being one of the most
* complicated routines in the whole program.  A routine that just
* writes out 256 values without attempting to optimize would be much
* simpler, but would hurt compression quite a bit on small files.
*
*/
void output_counts( output, scaled_counts )
FILE *output;
unsigned char scaled_counts[];
{
     int first;
     int last;
     int next;
     int i;

     first = 0;
     while ( first < 255 && scaled_counts[ first ] == 0 )
               first++;
/*
* Each time I hit the start of the loop, I assume that first is the
* number for a run of non-zero values.  The rest of the loop is
* concerned with finding the value for last, which is the end of the
* run, and the value of next, which is the start of the next run.
* At the end of the loop, I assign next to first, so it starts in on
* the next run.
*/
     for ( ; first < 256 ; first = next ) {
       last = first + 1;
       for ( ; ; ) {
         for ( ; last < 256 ; last++ )
           if ( scaled_counts[ last ] == 0 )
             break;
         last ––;
         for ( next = last + 1; next < 256 ; next++ )
           if ( scaled_counts[ next ] != 0 )
             break;
         if ( next > 255 )
           break;
         if ( ( next - last ) > 3 )
           break;
         last = next;
     };
/*
* Here is where I output first, last, and all the counts in between.
*/
        if ( putc( first, output ) != first )
          fatal_error( "Error writing byte counts\n" );
        if ( putc( last, output ) != last )
          fatal_error( "Error writing byte counts\n" );
        for ( i = first ; i <= last ; i++ ) {
          if ( putc( scaled_counts[ i ], output ) !=
            (int) scaled_counts[ i ] )
            fatal_error( "Error writing byte counts\n" );
        }
     }
     if ( putc( 0, output ) != 0 )
          fatal_error( "Error writing byte counts\n" );
}

/*
* When expanding, I have to read in the same set of counts.  This is
* quite a bit easier that the process of writing them out, since no
* decision making needs to be done.  All I do is read in first, check
* to see if I am all done, and if not, read in last and a string of
* counts.
*/

void input_counts( input )
FILE *input;
{
     int first;
     int last;
     int i;
     int c;
     unsigned char scaled_counts[ 256 ];
     for ( i = 0 ; i < 256 ; i++ )
       scaled_counts[ i ] = 0;
     if ( ( first = getc( input ) ) == EOF )
       fatal_error( "Error reading byte counts\n" );
     if ( ( last = getc( input ) ) == EOF )
       fatal_error( "Error reading byte counts\n" );
     for ( ; ; ) {
       for ( i = first ; i <= last ; i++ )
         if ( ( c = getc( input ) ) == EOF )
           fatal_error( "Error reading byte counts\n" );
         else
            scaled_counts[ i ] = (unsigned int) c;
       if ( ( first = getc( input ) ) == EOF )
         fatal_error( "Error reading byte counts\n" );
       if ( first == 0 )
         break;
       if ( ( last = getc( input ) ) == EOF )
         fatal_error( "Error reading byte counts\n" );
     }
     build_totals( scaled_counts );
}

/*
* Everything from here down defines the arithmetic coder section
* of the program.
*/

/*
* These four variables define the current state of the arithmetic
* coder/decoder.  They are assumed to be 16 bits long.  Note that
* by declaring them as short ints, they will actually be 16 bits
* on most 80X86 and 680X0 machines, as well as VAXen.
*/
static unsigned short int code;/* The present input code value     */
static unsigned short int low; /* Start of the current code range  */
static unsigned short int high;/* End of the current code range    */
long underflow_bits:           /* Number of underflow bits pending */

/*
* This routine must be called to initialize the encoding process.
* The high register is initialized to all 1s, and it is assumed that
* it has an infinite string of 1s to be shifted into the lower bit
* positions when needed.
*/
void initialize_arithmetic_encoder() {
     low = 0;
     high = 0xffff;
     underflow_bits = 0;
}

/*
* At the end of the encoding process, there are still significant
* bits left in the high and low registers.  We output two bits,
* plus as many underflow bits as are necessary.
*/
void flush_arithmetic_encoder( stream )
BIT_FILE *stream;
{
     OutputBit( stream, low & 0x4000 );
     underflow_bits++;
     while ( underflow_bits–– > 0 )
       OutputBit( stream, ~low & 0x4000 );
}

/*
* Finding the low count, high count, and scale for a symbol
* is really easy, because of the way the totals are stored.
* This is the one redeeming feature of the data structure used
* in this implementation.
*/
void convert_int_to_symbol( c, s )
int c;
SYMBOL *s;
}
     s->scale = totals[ END_OF_STREAM + 1];
     s->low_count = totals[ c ];
     s->high_count = totals[ c + 1 ];
}

/*
* Getting the scale for the current context is easy.
*/
void get_symbol_scale( s )
SYMBOL *s;
{
     s->scale = totals[ END_OF_STREAM + 1 ];
}

/*
* During decompression, we have to search through the table until
* we find the symbol that straddles the "count" parameter.  When
* it is found, it is returned.  The reason for also setting the
* high count and low count is so that symbol can be properly removed
* from the arithmetic coded input.
*/
int convert_symbol_to_int( count, s )
int count;
SYMBOL *s;
{
     int c;
     for ( c = END_OF_STREAM ; count < totals[ c ] ; c–– )
        ;
     s->high_count = totals[ c + 1 ];
     s->low_count = totals[ c ];
     return( c );
}

/*
* This routine is called to encode a symbol.  The symbol is passed
* in the SYMBOL structure as a low count, a high count, and a range,
* instead of the more conventional probability ranges.  The encoding
* process takes two steps.  First, the values of high and low are
* updated to take into account the range restriction created by the
* new symbol.  Then, as many bits as possible are shifted out to
* the output stream.  Finally, high and low are stable again and
* the routine returns.
*/
void encode_symbol( stream, s )
BIT_FILE *stream;
SYMBOL *s;
{
  long range;
/*
* These three lines rescale high and low for the new symbol.
*/
     range = (long) ( high-low ) + 1;
     high = low + (unsigned short int)
                   (( range * s->high_count ) / s->scale - 1 );
     low = low + (unsigned short int)
                   (( range * s->low_count ) / s->scale );
/*
* This loop turns out new bits until high and low are far enough
* apart to have stabilized.
*/
     for ( ; ; ) {
/*
* If this test passes, it means that the MSDigits match, and can
* be sent to the output stream.
*/
     if ( ( high & 0x8000 ) == (  low & 0x8000 ) ) {
       OutputBit( stream, high & 0x8000 );
       while ( underflow_bits > 0 ) {
         OutputBit( stream, ~high & 0x8000 );
         underflow_bits––;
       }
     }
/*
* If this test passes, the numbers are in danger of underflow, because
* the MSDigits don't match, and the 2nd digits are just one apart.
*/
     else if ( ( low & 0x4000 ) && !( high & 0x4000 )) {
       underflow_bits += 1;
       low &= 0x3fff;
       high |= 0x4000;
     } else
       return ;
     low <<= 1;
     high <<= 1;
     high |= 1;
   }
}

/*
* When decoding, this routine is called to figure out which symbol
* is presently waiting to be decoded.  This routine expects to get
* the current model scale in the s->scale parameter, and it returns
* a count that corresponds to the present floating point code;
*
* code = count / s->scale
*/
short int get_current_count( s )

SYMBOL *s;
{
     long range;
     short int count;

     range = (long) ( high - low ) + l;
     count = (short int)
             ((((long) ( code - low ) + 1 ) * s->scale-1 ) / range ) ;
     return( count );
}

/*
* This routine is called to initialize the state of the arithmetic
* decoder.  This involves initializing the high and low registers
* to their conventional starting values, plus reading the first
* 16 bits from the input stream into the code value.
*/
void initialize_arithmetic_decoder( stream )
BIT_FILE *stream;
{
     int i;
     code = 0;
     for ( i = 0 ; i < 16 ; i++ ) {
       code <<= 1;
       code += InputBit( stream );
     }
     low = 0;
     high = 0xffff;
}

/*
* Just figuring out what the present symbol is doesn't remove
* it from the input bit stream.  After the character has been
* decoded, this routine has to be called to remove it from the
* input stream.
*/
void remove_symbol_from_stream( stream, s )
BIT_FILE *stream;
SYMBOL *s;
{
     long range;

/*
* First, the range is expanded to account for the symbol removal.
*/
     range = (long)( high - low ) + l;
     high = low + (unsigned short int)
             (( range * s->high_count ) / s->scale - 1);
     low = low + (unsigned short int)
             (( range * s->low_count ) / s->scale );
*/
* Next, any possible bits are shipped out.
*/
     for ( ; ; ) {
/*
* If the MSDigits match, the bits will be shifted out.
*/
     if ( ( high & 0x8000 ) == ( low & 0x8000 ) ) {
     }
/*
* Else, if underflow is threatening, shift out the 2nd MSDigit.
*/
     else if ((low & 0x4000) == 0x4000  && (high & 0x4000) == 0 ) {
       code ^= 0x4000;
       low &= 0x3ffff;
       high |= 0x4000;
     } else
/*
* Otherwise, nothing can be shifted out, so I return.
*/
          return;
     low <<= 1;
     high <<= 1;
     high |= 1;
     code <<= 1;
     code += InputBit( stream );
   }
}
/*************************** End of ARITH.C ****************************/
</PRE>
<!--  END CODE //-->
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="133-136.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="../ch06/153-154.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>


</TD>
</TR>
</TABLE>

</BODY>
</HTML>