|
ARITH-N Listing
/************************* Start of ARITH-N.C **************************/
* * This is the order-n arithmetic coding module used in the final
* part of chapter 6.
*
* Compile with BITIO.C. ERRHAND.C, and either MAIN-C.C OR MAIN-E.C. This
* program should be compiled in large model. An even better alternative
* is a DOS extender.
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "errhand.h"
#include "bitio.h"
/*
* The SYMBOL structure is what is used to defined a symbol in
* arithmetic coding terms. A symbol is defined as a range between
* 0 and 1. Since we are using integer math, instead of using 0 and 1
* as our end points, we have an integer scale. The low_count and
* high_count define where the symbol falls in the range.
*/
typedef struct {
unsigned short int low_count;
unsigned short int high_count;
unsigned short int scale;
} SYMBOL;
#define MAXIMUM_SCALE 16383 /* Maximum allowed frequency count */
#define ESCAPE 256 /* The escape symbol */
#define DONE (-1) /* The output stream empty symbol */
#define FLUSH (-2) /* The symbol to flush the model */
/*
* Function prototypes.
*/
#ifdef __STDC__
void initialize_options( int argc, char **argv );
int check_compression( FILE *input, BIT_FILE *output );
void initialize_model( void );
void update_model( int symbol );
int convert_int_to_symbol( int symbol, SYMBOL *s );
void get_symbol_scale( SYMBOL *s );
int convert_symbol_to_int( int count, SYMBOL *s );
void add_character_to_model( int c );
void flush_model( void );
void initialize_arithmetic_decoder( BIT_FILE *stream ) ;
void remove_symbol_from_stream( BIT_FILE *stream, SYMBOL *s );
void initialize_arithmetic_encoder( void );
void encode_symbol( BIT_FILE *stream, SYMBOL *s );
void flush_arithmetic_encoder( BIT_FILE *stream );
short int get_current_count( SYMBOL *s );
#else
void initialize_options();
int check_compression();
void initialize_model();
void update_model();
int convert_int_to_symbol();
void get_symbol_scale();
int convert_symbol_to_int();
void add_character_to_model();
void flush_model();
void initialize_arithmetic_decoder();
void remove_symbol_from_stream();
void initialize_arithmetic_encoder();
void encode_symbol();
void flush_arithmetic_encoder();
short int get_current_count();
#endif
char *CompressionName = "Adaptive order n model with arithmetic coding";
char *Usage = "in-file out-file [ -o order ]\n\n";
int max_order = 3;
/*
* The main procedure is similar to the main found in ARITH1E.C. It has
* to initialize the coder and the model. It then sits in a loop reading
* input symbols and encoding them. One difference is that every 256
* symbols a compression check is performed. If the compression ratio
* falls below 10%, a flush character is encoded. This flushes the encod
* ing model, and will cause the decoder to flush its model when the
* file is being expanded. The second difference is that each symbol is
* repeatedly encoded until a successful encoding occurs. When trying to
* encode a character in a particular order, the model may have to
* transmit an ESCAPE character. If this is the case, the character has
* to be retransmitted using a lower order. This process repeats until a
* successful match is found of the symbol in a particular context.
* Usually this means going down no further than the order -1 model.
* However, the FLUSH and DONE symbols drop back to the order -2 model.
*
*/
void CompressFile( input, output, argc, argv )
FILE *input;
BIT_FILE *output;
int argc;
char *argv[];
{
SYMBOL s;
int c;
int escaped;
int flush = 0;
long int text_count = 0;
initialize_options( argc, argv );
initialize_model();
initialize-arithmetic_encoder();
for ( ; ; ) {
if ( ( ++text_count & 0x0ff ) == 0 )
flush = check_compression( input, output );
if ( !flush )
c = getc( input );
else
c = FLUSH;
if ( c == EOF )
c = DONE;
do {
escaped = convert_int_to_symbol( c, &s);
encode_symbol( output, &s );
} while ( escaped );
if ( c == DONE )
break;
if ( c == FLUSH ) {
flush_model();
flush = 0;
}
update_model( c );
add_character_to_model( c );
}
flush_arithmetic_encoder( output );
}
/*
* The main loop for expansion is very similar to the expansion
* routine used in the simpler compression program, ARITH1E.C. The
* routine first has to initialize the the arithmetic coder and the
* model. The decompression loop differs in a couple of respect.
* First of all, it handles the special ESCAPE character, by
* removing them from the input bit stream but just throwing them
* away otherwise. Secondly, it handles the special FLUSH character.
* Once the main decoding loop is done, the cleanup code is called,
* and the program exits.
*
*/
void ExpandFile( input, output, argc, argv )
BIT_FILE *input;
FILE *output;
int argc;
char *argv[];
{
SYMBOL s;
int c;
int count;
initialize_options( argc, argv );
initialize_model();
initialize_arithmetic_decoder( input );
for ( ; ; ) {
do {
get_symbol_scale( &s );
count = get_current_count( &s );
c = convert_symbol_to_int( count, &s );
remove_symbol_from_stream( input, &s );
} while ( c == ESCAPE );
if ( c == DONE )
break;
if ( c != FLUSH )
putc( (char) c, output );
else
flush_model();
update_model( c );
add_character_to_model( c );
}
}
/*
* This routine checks for command line options. At present, the only
* option being passed on the command line is the order.
*/
void initialize_options( argc, argv )
int argc;
char *argv[];
{
while ( argc–– > 0 ) {
if ( strcmp( *argv, "-o" ) == 0 ) {
argc––;
max_order = atoi( *++argv );
} else
printf( "Uknown argument on command line: %s\n", *argv );
argc––;
argv++;
}
}
/*
* This routine is called once every 256 input symbols. Its job is to
* check to see if the compression ratio falls below 10%. If the
* output size is 90% of the input size, it means not much compression
* is taking place, so we probably ought to flush the statistics in the
* model to allow for more current statistics to have greater impact.
* This heuristic approach does seem to have some effect.
*/
int check_compression( input, output )
FILE *input;
BIT_FILE *output;
{
static long local_input_marker = 0L;
static long local_output_marker = 0L;
long total_input_bytes;
long total_output_bytes;
int local_ratio;
total_input_bytes = ftell( input ) - local_input_marker;
total_output_bytes = ftell( output->file );
total_output_bytes -= local_output_marker;
if ( total_output_bytes == 0 )
total_output_bytes = 1;
local_ratio = (int)( ( total_output_bytes * 100 ) /
total_input_bytes );
local_input_marker = ftell( input );
local_output_marker = ftell( output->file );
return( local_ratio > 90 );
}
/*
*
* The next few routines contain all of the code and data used to
* perform modeling for this program. This modeling unit keeps track
* of all contexts from 0 up to max_order, which defaults to 3. In
* addition, there is a special context -1 which is a fixed model used
* to encode previously unseen characters, and a context -2 which is
* used to encode EOF and FLUSH messages.
*
* Each context is stored in a special CONTEXT structure, which is
* documented below. Context tables are not created until the context
* is seen, and they are never destroyed.
*
*/
/*
* A context table contains a list of the counts for all symbols
* that have been seen in the defined context. For example, a
* context of "Zor" might have only had 2 different characters
* appear. 't' might have appeared 10 times, and '1' might have
* appeared once. These two counts are stored in the context
* table. The counts are stored in the STATS structure. All of
* the counts for a given context are stored in and array of STATS.
* As new characters are added to a particular contexts, the STATS
* array will grow. Sometimes the STATS array will shrink
* after flushing the model.
*/
typedef struct {
unsigned char symbol;
unsigned char counts;
} STATS;
/*
* Each context has to have links to higher order contexts. These
* links are used to navigate through the context tables. For example,
* to find the context table for "ABC", I start at the order 0 table,
* then find the pointer to the "A" context table by looking through
* the LINKS array. At that table, we find the "B" link and go to
* that table. The process continues until the destination table is
* found. The table pointed to by the LINKS array corresponds to the
* symbol found at the same offset in the STATS table. The reason that
* LINKS is in a separate structure instead of being combined with
* STATS is to save space. All of the leaf context nodes don't need
* next pointers, since they are in the highest order context. In the
* leaf nodes, the LINKS array is a NULL pointer.
*/
typedef struct {
struct context *next;
} LINKS;
/*
* The CONTEXT structure holds all of the known information about
* a particular context. The links and stats pointers are discussed
* immediately above here. The max_index element gives the maximum
* index that can be applied to the stats or link array. When the
* table is first created, and stats is set to NULL, max_index is set
* to -1. As soon as single element is added to stats, max_index is
* incremented to 0.
*
* The lesser context pointer is a navigational aid. It points to
* the context that is one less than the current order. For example,
* if the current context is "ABC", the lesser_context pointer will
* point to "BC". The reason for maintaining this pointer is that
* this particular bit of table searching is done frequently, but
* the pointer only needs to be built once, when the context is
* created.
*/
typedef struct context {
int max_index;
LINKS *links;
STATS *stats;
struct context *lesser_context;
} CONTEXT;
/*
* *contexts[] is an array of current contexts. If I want to find
* the order 0 context for the current state of the model. I just
* look at contexts[0]. This array of context pointers is set up
* every time the model is updated.
*/
CONTEXT **contexts;
/*
* current_order contains the current order of the model. It starts
* at max_order, and is decremented every time an ESCAPE is sent. It
* will only go down to -1 for normal symbols, but can go to -2 for
* EOF and FLUSH.
*/
int current_order;
/*
* This table contains the cumulative totals for the current context.
* Because this program is using exclusion, totals has to be calculated
* every time a context is used. The scoreboard array keeps track of
* symbols that have appeared in higher order models, so that they
* can be excluded from lower order context total calculations.
*/
short int totals[ 258 ];
char scoreboard[ 256 ];
/*
* Local procedure declarations for modeling routines.
*/
#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
* to context "C" and the symbol 'D'. It then returns a pointer to
* "CD", which I use to create the "BCD" table. The recursion is
* guaranteed to end if it ever gets to order -1, because the null table
* is guaranteed to have a link for every symbol to the order 0 table.
* This is the most complicated part of the modeling program, but it is
* necessary for performance reasons.
*/
CONTEXT *shift_to_next_context( table, c, order )
CONTEXT *table;
int c;
int order;
{
int i;
CONTEXT *new_lesser;
/*
* First, try to find the new context by backing up to the lesser
* context and searching its link table. If I find the link, we take
* a quick and easy exit, returning the link. Note that there is a
* special kludge for context order 0. We know for a fact that
* the lesser context pointer at order 0 points to the null table,
* order -1, and we know that the -1 table only has a single link
* pointer, which points back to the order 0 table.
*/
table = table->lesser_context;
if ( order == 0 )
return( table->links[ 0 ].next );
for ( i = 0 ; i <= table->max_index ; i++ )
if ( table->stats[ i ].symbol == (unsigned char) c )
if ( table->links[ i ].next != NULL)
return( table->links[ i ].next );
else
break;
/*
* If I get here, it means the new context did not exist. I have to
* create the new context, add a link to it here, and add the backwards
* link to *his* previous context. Creating the table and adding it to
* this table is pretty easy, but adding the back pointer isn't. Since
* creating the new back pointer isn't easy, I duck my responsibility
* and recurse to myself in order to pick it up.
*/
new_lesser = shift_to_next_context( table, c, order-1 );
/*
* Now that I have the back pointer for this table, I can make a call
* to a utility to allocate the new table.
*/
table = allocate_next_order_table( table, c, new_lesser );
return( table );
}
/*
* Rescaling the table needs to be done for one of three reasons.
* First, if the maximum count for the table has exceeded 16383, it
* means that arithmetic coding using 16 and 32 bit registers might
* no longer work. Secondly, if an individual symbol count has
* reached 255, it will no longer fit in a byte. Third, if the
* current model isn't compressing well, the compressor program may
* want to rescale all tables in order to give more weight to newer
* statistics. All this routine does is divide each count by 2.
* If any counts drop to 0, the counters can be removed from the
* stats table, but only if this is a leaf context. Otherwise, we
* might cut a link to a higher order table.
*/
void rescale_table( table )
CONTEXT *table;
{
int i;
if ( table->max_index == -1 )
return;
for ( i = 0 ; i <= table->max_index ; i ++ )
table->stats[ i ].counts /= 2;
if ( table->stats[ table]>max_index ].counts == 0 &&
table->links == NULL ) {
while ( table->stats[ table->max_index ].counts == 0 &&
table->max_index >= 0 )
table->max_index––;
if ( table->max_index == -1 ) {
free( (char *) table->stats );
table->stats = NULL;
} else {
table->stats = (STATS *)
realloc( (char *) table->stats,
sizeof( STATS ) * ( table->max_index + 1 ) );
if ( table->stats == NULL )
fatal_error( "Error #11: reallocating stats space!" );
}
}
}
/*
* This routine has the job of creating a cumulative totals table for
* a given context. The cumulative low and high for symbol c are going to
* be stored in totals[c+2] and totals[c+1]. Locations 0 and 1 are
* reserved for the special ESCAPE symbol. The ESCAPE symbol
* count is calculated dynamically, and changes based on what the
* current context looks like. Note also that this routine ignores
* any counts for symbols that have already shown up in the scoreboard,
* and it adds all new symbols found here to the scoreboard. This
* allows us to exclude counts of symbols that have already appeared in
* higher order contexts, improving compression quite a bit.
*/
void totalize_table( table )
CONTEXT *table;
{
int i;
unsigned char max;
for ( ; ; ) {
max = 0;
i = table->max_index + 2;
totals[ i ] = 0;
for ( ; i > 1 ; i- ) {
totals[ i-1 ] = totals[ i ];
if ( table->stats[ i-2 ].counts )
if ( ( current_order == -2 ) ||
scoreboard[ table->stats[ i-2 ].symbol ] == 0 )
totals[ i-1 ] += table->stats[ i-2].counts;
if ( table->stats[ i-2 ].counts > max )
max = table->stats[ i-2 ].counts;
}
/*
* Here is where the escape calculation needs to take place.
*/
if ( max == 0 )
totals[ 0 ] = 1;
else {
totals[ 0 ] = (short int) ( 256 - table->max_index );
totals[ 0 ] *= table->max_index;
totals[ 0 ] /= 256;
totals[ 0 ] /= max;
totals[ 0 ]++;
totals[ 0 ] += totals[ 1 ];
}
if ( totals[ 0 ] < MAXIMUM_SCALE )
break;
rescale_table( table );
}
for ( i = 0 ; i < table->max_index ; i++ )
if (table->stats[i].counts != 0)
scoreboard[ table->stats[ i ].symbol ] = 1;
}
/*
* This routine is called when the entire model is to be flushed.
* This is done in an attempt to improve the compression ratio by
* giving greater weight to upcoming statistics. This routine
* starts at the given table, and recursively calls itself to
* rescale every table in its list of links. The table itself
* is then rescaled.
*/
void recursive_flush( table )
CONTEXT *table;
{
int i;
if ( table->links != NULL )
for ( i = 0 ; i <= table->max_index ; i++ )
if ( table->links[ i ].next != NULL )
recursive_flush( table->links[ i ].next );
rescale_table( table );
}
/*
* This routine is called to flush the whole table, which it does
* by calling the recursive flush routine starting at the order 0
* table.
*/
void flush_model()
{
putc( 'F', stdout );
recursive_flush( contexts[ 0 ] );
}
/*
* Everything from here down define 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 );
OutputBits( stream, 0L, 16 );
}
/*
* 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 ) + 1;
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 ) + 1;
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 &= 0x3fff;
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-N.C ***************************/
|