172-200.html

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

*/
#ifdef __STDC__
void update_table( CONTEXT *table, int symbol );
void rescale_table( CONTEXT *table );
void totalize_table( CONTEXT *table );
CONTEXT *shift_to_next_context( CONTEXT *table, int c, int order );
CONTEXT *allocate_next_order_table( CONTEXT *table,
                                    int symbol,
                                    CONTEXT *lesser_context );
void recursive_flush( CONTEXT *table );
#else
void update_table();
void rescale_table();
void totalize_table();
CONTEXT *shift_to_next_context();
CONTEXT *allocate_next_order_table();
void recursive_flush();
#endif

/*
* This routine has to get everything set up properly so that
* the model can be maintained properly.  The first step is to create
* the *contexts[] array used later to find current context tables.
* The *contexts[] array indices go from -2 up to max_order, so
* the table needs to be fiddled with a little.  This routine then
* has to create the special order -2 and order -1 tables by hand,
* since they aren't quite like other tables.  Then the current
* context is set to \0, \0, \0, ... and the appropriate tables
* are built to support that context.  The current order is set
* to max_order, the scoreboard is cleared, and the system is
* ready to go.
*/

void initialize_model()
{
     int i;
     CONTEXT *null_table;
     CONTEXT *control_table;

     current_order = max_order;
     contexts = (CONTEXT **) calloc( sizeof( CONTEXT * ), 10 );
     if ( contexts == NULL )
       fatal_error( "Failure #1:  allocating context table!" );
     context += 2;
     null_table = (CONTEXT *) calloc( sizeof( CONTEXT ), 1 );
     if ( null_table == NULL )
       fatal_error( "Failure #2:  allocating null table!" );
     null_table->max_index = -1;
     contexts[ -1 ] = null_table;
     for ( i = 0 ; i <= max_order ; 1++ )
        contexts[ i ] = allocate_next_order_table( contexts[ i-1 ],
                                                   0,
                                                   contexts[ i-1 ] );
     free( (char *) null_table->stats );
     null_table->stats =
       (STATS &) calloc( sizeof( STATS ), 256 );
     if ( null_table->stats == NULL )
       fatal_error( "Failure #3:  allocating null table!" );
     null_table->max_index = 255;
     for ( i=0 ; i < 256 ; i++ ) {
       null_table->stats[ i ].symbol = (unsigned char) i;
       null_table->stats[ i ].counts = 1;
     }

     control_table = (CONTEXT *) calloc( sizeof(CONTEXT), 1 );
     if ( control_table == NULL )
       fatal_error( "Failure #4:  allocating null table!" );
     control_table->stats =
       (STATS *) calloc( sizeof( STATS ), 2 );
     if ( control_table->stats == NULL )
       fatal_error( "Failure #5:  allocating null table!" );
     contexts[ -2 ] = control_table;
     control_table->max_index = 1;
     control_table->stats[ 0 ].symbol = -FLUSH;
     control_table->stats[ 0 ].counts = 1;
     control_table->stats[ 1 ].symbol =– DONE;
     control_table->stats[ 1 ].counts = 1;

     for ( i = 0 ; i < 256 ; i++ )
       scoreboard[ i ] = 0;
}

/*
* This is a utility routine used to create new tables when a new
* context is created.  It gets a pointer to the current context,
* and gets the symbol that needs to be added to it.  It also needs
* a pointer to the lesser context for the table that is to be
* created.  For example, if the current context was "ABC", and the
* symbol 'D' was read in, add_character_to_model would need to
* create the new context "BCD".  This routine would get called
* with a pointer to "BC", the symbol 'D', and a pointer to context
* "CD".  This routine then creates a new table for "BCD", adds it
* to the link table for "BC", and gives "BCD" a back pointer to
* "CD".  Note that finding the lesser context is a difficult
* task, and isn't done here.  This routine mainly worries about
* modifying the stats and links fields in the current context.
*/

CONTEXT *allocate_next_order_table( table, symbol, lesser_context )
CONTEXT *table;
int symbol;
CONTEXT *lesser_context;
{
     CONTEXT *new_table;
     int i;
     unsigned int new_size;

     for ( i = 0 ; i <= table->max_index ; i++ )
       if (table->stats[ i ].symbol == (unsigned char) symbol )
         break;
       if ( i > table->max_index ) {
         table->max_index++;
         new_size = sizeof( LINKS );
         new_size *= table->max_index + 1;
         if ( table->links == NULL )
           table->links = (LINKS *) calloc( new_size, 1 );
         else
           table->links = (LINKS *)
             realloc( (char *) table->links, new_size );
         new_size = sizeof( STATS );
         new_size *= table->max_index + 1;
         if ( table->stats == NULL )
           table->stats = (STATS *) calloc( new_size, 1 );
         else
           table->stats = (STATS *)
             realloc( (char *) table->stats, new_size );
         if ( table->links == NULL )
           fatal_error( "Failure #6:  allocating new table" );
         if ( table->stats == NULL )
           fatal_error( "Failure #7:  allocating new table" );
         table->stats[ i ].symbol = (unsigned char) symbol;
         table->stats[ i ].counts = 0;
     }
     new_table = (CONTEXT *) calloc(sizeof( CONTEXT ), 1 );
     if ( new_table == NULL )
       fatal_error( "Failure #8:  allocating new table" );
     new_table->max_index = -1;
     table->links[ i ].next = new_table;
     new_table->lesser_context = lesser_context;
     return( new_table );
}

/*
* This routine is called to increment the counts for the current
* contexts.  It is called after a character has been encoded or
* decoded.  All it does is call update_table for each of the
* current contexts, which does the work of incrementing the count.
* This particular version of update_model() practices update exclusion,
* which means that if lower order models weren't used to encode
* or decode the character, they don't get their counts updated.
* This seems to improve compression performance quite a bit.
* To disable update exclusion, the loop would be changed to run
* from 0 to max_order, instead of current_order to max_order.
*/
void update_model( symbol )
int symbol;
{

     int i;
     int local_order;

     if ( current_order < 0 )
       local_order = 0;
     else
       local_order = current_order;
     if ( symbol >= 0 ) {
       while ( local_order <= max_order ) {
         if ( symbol >= 0 )
           update_table( contexts[ local_order ], symbol );
         local_order++;
        }
     }
     current_order = max_order;
     for ( i = 0 ; i < 256 ; i++ )
       scoreboard[ i ] = 0;
}

/*
* This routine is called to update the count for a particular symbol
* in a particular table.  The table is one of the current contexts,
* and the symbol is the last symbol encoded or decoded.  In principle
* this is a fairly simple routine, but a couple of complications make
* things a little messier.  First of all, the given table may not
* already have the symbol defined in its statistics table.  If it
* doesn't, the stats table has to grow and have the new guy added
* to it.  Secondly, the symbols are kept in sorted order by count
* in the table so that the table can be trimmed during the flush
* operation.  When this symbol is incremented, it might have to be moved
* up to reflect its new rank.  Finally, since the counters are only
* bytes, if the count reaches 255, the table absolutely must be rescaled
* to get the counts back down to a reasonable level.
*/

void update_table( table, symbol )
CONTEXT *table;
int symbol;
{
     int i;
     int index;
     unsigned char temp;
     CONTEXT *temp_ptr;
     unsigned int new_size;
/*
* First, find the symbol in the appropriate context table.  The first
* symbol in the table is the most active, so start there.
*/

     index = 0;
     while ( index <= table->max_index &&
          table->stats[index].symbol != (unsigned char) symbol )
       index++;
     if ( index > table->max_index ) {
       table->max_index++;
       new_size = sizeof( LINKS );
       new_size *= table->max_index + 1;
       if ( current_order < max_order ) {
         if ( table->max_index == 0 )
           table->links - (LINKS *) calloc( new_size, 1 );
         else
           table->links = (LINKS *)
             realloc( (char *) table->links, new_size );
         if (  table->links == NULL )
           fatal_error( "Error #9:  reallocating table space!" );
         table->links[ index ].next = NULL;
     }
     new_size = sizeof( STATS );
     new_size *= table->max_index + 1;
     if (table->max_index==0)
       table->stats = (STATS *) calloc( new_size, 1 );
     else
       table->stats = (STATS *)
         realloc( (char *) table->stats, new_size );
     if ( table->stats == NULL )
       fatal_error( "Error #10:  reallocating table space!" );
     table->stats[ index ].symbol = (unsigned char) symbol;
     table->stats[ index ].counts = 0;
   }
/*
* Now I move the symbol to the front of its list.
*/

     i = index;
     while ( i > 0 &&
       table->stats[ index ]. counts == table->stats[ i-1 ].counts )
       i--;
     if ( i != index ) {
       temp = table->stats[ index ].symbol;
       table->stats[ index ].symbol = table->stats[ i ].symbol;
       table->stats[ i ].symbol = temp;
       if ( table->links != NULL ) {
         temp_ptr = table->links[ index ].next;
         table->links[ index ].next = table->links[ i ].next;
         table->links[ i ].next = temp_ptr;
       }
       index = 1;
  }
/*
* The switch has been performed, now I can update the counts
*/
  table->stats[ index ].counts++;
  if ( table->stats[ index ].counts == 255 )
    rescale_table( table );
}
/*
* This routine is called when a given symbol needs to be encoded.
* It is the job of this routine to find the symbol in the context
* table associated with the current table, and return the low and
* high counts associated with that symbol, as well as the scale.
* Finding the table is simple.  Unfortunately, once I find the table,
* I have to build the table of cumulative counts, which is
* expensive, and is done elsewhere.  If the symbol is found in the
* table, the appropriate counts are returned.  If the symbol is
* not found, the ESCAPE symbol probabilities are returned, and
* the current order is reduced.  Note also the kludge to support
* the order -2 character set, which consists of negative numbers
* instead of unsigned chars.  This insures that no match will ever
* be found for the EOF or FLUSH symbols in  any "normal" table.
*/
int convert_int_to_symbol( c, s )
int c;
SYMBOL *s;
{
     int i;
     CONTEXT *table;

     table = contexts[ current_order ];
     totalize_table( table );
     s->scale = totals[ 0 ];
     if ( current_order == –2 )
       c = -c;
     for ( i = 0 ; i <= table->max_index ; i++ ) {
       if ( c == (int) table->stats[ i ].symbol ) {
         if ( table->stats[ i ].counts == 0 )
           break;
         s->low_count = totals[ i+2 ];
         s->high_count = totals[ i+1 ];
         return( 0 );
       }
     }
     s->low_count = totals[ 1 ];
     s->high-count = totals[ 0 ];
     current_order––;
     return( 1 );
}
/*
* This routine is called when decoding an arithmetic number.  In
* order to decode the present symbol, the current scale in the
* model must be determined.  This requires looking up the current
* table, then building the totals table.  Once that is done, the
* cumulative total table has the symbol scale at element 0.
*/

void get_symbol_scale( s)
SYMBOL *s;
{
     CONTEXT *table;

     table = contexts[ current_order ];
     totalize_table( table );
     s->scale = totals[ 0 ];
}
/*
* This routine is called during decoding.  It is given a count that
* came out of the arithmetic decoder, and has to find the symbol that
* matches the count.  The cumulative totals are already stored in the
* totals[] table, from the call to get_symbol-scale, so this routine
* just has to look through that table.  Once the match is found,
* the appropriate character is returned to the caller.  Two possible
* complications.  First, the character might be the ESCAPE character,
* in which case the current_order has to be decremented.  The other
* complication.  First, the character might be the ESCAPE character,
* in which case the current_order has to be decremented.  The other
* complication is that the order might be -2, in which case we return
* the negative of the symbol so it isn't confused with a normal
* symbol.
*/
int convert_symbol_to_int( count, s )
int count;
SYMBOL *s;
{
     int c;
     CONTEXT *table;

     table - contexts[ current_order ];
     for ( c = 0; count < totals[ c ] ; c++ )
       ;
     s->high_count = totals[ c - 1 ];
     s->low_count = totals[ c ]:
     if ( c == 1 ) {
       current_order––;
       return( ESCAPE );
     }
     if ( current_order < -1 )
       return( (int) -table->stats[ c-2 ].symbol );
     else
       return( table->stats[ c-2 ].symbol );
}

/*
* After the model has been updated for a new character, this routine
* is called to "shift" into the new context.  For example, if the
* last context was "ABC", and the symbol 'D' had just been processed,
* this routine would want to update the context pointers to that
* context[1]=="D", contexts[2]=="CD" and contexts[3]=="BCD".  The
* potential problem is that some of these tables may not exist.
* The way this is handled is by the shift_to_next_context routine.
* It is passed a pointer to the "ABC" context, along with the symbol
* 'D', and its job is to return a pointer to "BCD".  Once we have
* "BCD", we can follow the lesser context pointers in order to get
* the pointers to "CD" and "C".  The hard work was done in
* shift_to_context().
*/

void add_character_to_model( c )
int c;
{

     int i;
     if ( max_order < 0 || c < 0 )
       return;
     contexts[ max_order ] =
       shift_to_next_context( contexts[ max_order ], c, max_order );
     for ( i = max_order-1 ; i > 0 ; i–– )
       contexts[ i ] = contexts[ i+1 ]->lesser_context;
}

/*
* This routine is called when adding a new character to the model.  From
* the previous example, if the current context was "ABC", and the new
* symbol was 'D', this routine would get called with a pointer to
* context table "ABC", and symbol 'D', with order max_order.  What this
* routine needs to do then is to find the context table "BCD".  This
* should be an easy job, and it is if the table already exists.  All
* we have to in that case is follow the back pointer from "ABC" to "BC".
* We then search the link table of "BC" until we find the link to "D".
* That link points to "BCD", and that value is then returned to the
* caller.  The problem crops up when "BC" doesn't have a pointer to
* "BCD".  This generally means that the "BCD" context has not appeared
* yet.  When this happens, it means a new table has to be created and
* added to the "BC" table.  That can be done with a single call to
* the allocate_new_table routine.  The only problem is that the
* allocate_new_table routine wants to know what the lesser context for
* the new table is going to be.  In other words, when I create "BCD",
* I need to know where "CD" is located.  In order to find "CD", I
* have to recursively call shift_to_next_context, passing it a pointer