#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#		"End of shell archive."
# Contents:  adaptive_model.c arithmetic_coding.h arithmetic_decode.c
#   arithmetic_encode.c bit_input.c bit_output.c decode.c encode.c
#   makefile model.h
# Wrapped by ian@cpsc.ucalgary.ca on Tue May 14 21:59:24 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'adaptive_model.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'adaptive_model.c'\"
else
echo shar: Extracting \"'adaptive_model.c'\" \(1963 characters\)
sed "s/^X//" >'adaptive_model.c' <<'END_OF_FILE'
X/* THE ADAPTIVE SOURCE MODEL */
X
X#include "model.h"
X
Xint freq[No_of_symbols+1];	/* Symbol frequencies                       */
X
X
X/* INITIALIZE THE MODEL. */
X
Xstart_model()
X{   int i;
X    for (i = 0; i<No_of_chars; i++) {		/* Set up tables that       */
X        char_to_index[i] = i+1;			/* translate between symbol */
X        index_to_char[i+1] = i;			/* indexes and characters.  */
X    }
X    for (i = 0; i<=No_of_symbols; i++) {	/* Set up initial frequency */
X        freq[i] = 1;				/* counts to be one for all */
X        cum_freq[i] = No_of_symbols-i;		/* symbols.                 */
X    }
X    freq[0] = 0;				/* Freq[0] must not be the  */
X}						/* same as freq[1].         */
X
X
X/* UPDATE THE MODEL TO ACCOUNT FOR A NEW SYMBOL. */
X
Xupdate_model(symbol)
X    int symbol;			/* Index of new symbol                      */
X{   int i;			/* New index for symbol                     */
X    if (cum_freq[0]==Max_frequency) {		/* See if frequency counts  */
X        int cum;				/* are at their maximum.    */
X        cum = 0;
X        for (i = No_of_symbols; i>=0; i--) {	/* If so, halve all the     */
X            freq[i] = (freq[i]+1)/2;		/* counts (keeping them     */
X            cum_freq[i] = cum; 			/* non-zero).               */
X            cum += freq[i];
X        }
X    }
X    for (i = symbol; freq[i]==freq[i-1]; i--) ;	/* Find symbol's new index. */
X    if (i<symbol) {
X        int ch_i, ch_symbol;
X        ch_i = index_to_char[i];		/* Update the translation   */
X        ch_symbol = index_to_char[symbol];	/* tables if the symbol has */
X        index_to_char[i] = ch_symbol;           /* moved.                   */
X        index_to_char[symbol] = ch_i;
X        char_to_index[ch_i] = symbol;
X        char_to_index[ch_symbol] = i;
X    }
X    freq[i] += 1;				/* Increment the frequency  */
X    while (i>0) {				/* count for the symbol and */
X        i -= 1;					/* update the cumulative    */
X        cum_freq[i] += 1;			/* frequencies.             */
X    }
X}
END_OF_FILE
if test 1963 -ne `wc -c <'adaptive_model.c'`; then
    echo shar: \"'adaptive_model.c'\" unpacked with wrong size!
fi
# end of 'adaptive_model.c'
fi
if test -f 'arithmetic_coding.h' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'arithmetic_coding.h'\"
else
echo shar: Extracting \"'arithmetic_coding.h'\" \(586 characters\)
sed "s/^X//" >'arithmetic_coding.h' <<'END_OF_FILE'
X/* DECLARATIONS USED FOR ARITHMETIC ENCODING AND DECODING */
X
X
X/* SIZE OF ARITHMETIC CODE VALUES. */
X
X#define Code_value_bits 16		/* Number of bits in a code value   */
Xtypedef long code_value;		/* Type of an arithmetic code value */
X
X#define Top_value (((long)1<<Code_value_bits)-1)      /* Largest code value */
X
X
X/* HALF AND QUARTER POINTS IN THE CODE VALUE RANGE. */
X
X#define First_qtr (Top_value/4+1)	/* Point after first quarter        */
X#define Half	  (2*First_qtr)		/* Point after first half           */
X#define Third_qtr (3*First_qtr)		/* Point after third quarter        */
END_OF_FILE
if test 586 -ne `wc -c <'arithmetic_coding.h'`; then
    echo shar: \"'arithmetic_coding.h'\" unpacked with wrong size!
fi
# end of 'arithmetic_coding.h'
fi
if test -f 'arithmetic_decode.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'arithmetic_decode.c'\"
else
echo shar: Extracting \"'arithmetic_decode.c'\" \(2117 characters\)
sed "s/^X//" >'arithmetic_decode.c' <<'END_OF_FILE'
X/* ARITHMETIC DECODING ALGORITHM. */
X
X#include "arithmetic_coding.h"
X
X
X/* CURRENT STATE OF THE DECODING. */
X
Xstatic code_value value;	/* Currently-seen code value                */
Xstatic code_value low, high;	/* Ends of current code region              */
X
X
X/* START DECODING A STREAM OF SYMBOLS. */
X
Xstart_decoding()
X{   int i;
X    value = 0;					/* Input bits to fill the   */
X    for (i = 1; i<=Code_value_bits; i++) {	/* code value.              */
X        value = 2*value+input_bit();
X    }
X    low = 0;					/* Full code range.         */
X    high = Top_value;
X}
X
X
X/* DECODE THE NEXT SYMBOL. */
X
Xint decode_symbol(cum_freq)
X    int cum_freq[];		/* Cumulative symbol frequencies            */
X{   long range;			/* Size of current code region              */
X    int cum;			/* Cumulative frequency calculated          */
X    int symbol;			/* Symbol decoded                           */
X    range = (long)(high-low)+1;
X    cum = 					/* Find cum freq for value. */
X      (((long)(value-low)+1)*cum_freq[0]-1)/range;
X    for (symbol = 1; cum_freq[symbol]>cum; symbol++) ; /* Then find symbol. */
X    high = low +				/* Narrow the code region   */
X      (range*cum_freq[symbol-1])/cum_freq[0]-1;	/* to that allotted to this */
X    low = low + 				/* symbol.                  */
X      (range*cum_freq[symbol])/cum_freq[0];
X    for (;;) {					/* Loop to get rid of bits. */
X        if (high<Half) {
X            /* nothing */			/* Expand low half.         */
X        } 
X        else if (low>=Half) {			/* Expand high half.        */
X            value -= Half;
X            low -= Half;			/* Subtract offset to top.  */
X            high -= Half;
X        }
X        else if (low>=First_qtr			/* Expand middle half.      */
X              && high<Third_qtr) {
X            value -= First_qtr;
X            low -= First_qtr;			/* Subtract offset to middle*/
X            high -= First_qtr;
X        }
X        else break;				/* Otherwise exit loop.     */
X        low = 2*low;
X        high = 2*high+1;			/* Scale up code range.     */
X        value = 2*value+input_bit();		/* Move in next input bit.  */
X    }
X    return symbol;
X}
END_OF_FILE
if test 2117 -ne `wc -c <'arithmetic_decode.c'`; then
    echo shar: \"'arithmetic_decode.c'\" unpacked with wrong size!
fi
# end of 'arithmetic_decode.c'
fi
if test -f 'arithmetic_encode.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'arithmetic_encode.c'\"
else
echo shar: Extracting \"'arithmetic_encode.c'\" \(2477 characters\)
sed "s/^X//" >'arithmetic_encode.c' <<'END_OF_FILE'
X/* ARITHMETIC ENCODING ALGORITHM. */
X
X#include "arithmetic_coding.h"
X
Xstatic void bit_plus_follow();	/* Routine that follows                     */
X
X
X/* CURRENT STATE OF THE ENCODING. */
X
Xstatic code_value low, high;	/* Ends of the current code region          */
Xstatic long bits_to_follow;	/* Number of opposite bits to output after  */
X				/* the next bit.                            */
X
X
X/* START ENCODING A STREAM OF SYMBOLS. */
X
Xstart_encoding()
X{   low = 0;					/* Full code range.         */
X    high = Top_value;
X    bits_to_follow = 0;				/* No bits to follow next.  */
X}
X
X
X/* ENCODE A SYMBOL. */
X
Xencode_symbol(symbol,cum_freq)
X    int symbol;			/* Symbol to encode                         */
X    int cum_freq[];		/* Cumulative symbol frequencies            */
X{   long range;			/* Size of the current code region          */
X    range = (long)(high-low)+1;
X    high = low +				/* Narrow the code region   */
X      (range*cum_freq[symbol-1])/cum_freq[0]-1;	/* to that allotted to this */
X    low = low + 				/* symbol.                  */
X      (range*cum_freq[symbol])/cum_freq[0];
X    for (;;) {					/* Loop to output bits.     */
X        if (high<Half) {
X            bit_plus_follow(0);			/* Output 0 if in low half. */
X        } 
X        else if (low>=Half) {			/* Output 1 if in high half.*/
X            bit_plus_follow(1);
X            low -= Half;
X            high -= Half;			/* Subtract offset to top.  */
X        }
X        else if (low>=First_qtr			/* Output an opposite bit   */
X              && high<Third_qtr) {		/* later if in middle half. */
X            bits_to_follow += 1;
X            low -= First_qtr;			/* Subtract offset to middle*/
X            high -= First_qtr;
X        }
X        else break;				/* Otherwise exit loop.     */
X        low = 2*low;
X        high = 2*high+1;			/* Scale up code range.     */
X    }
X}
X
X
X/* FINISH ENCODING THE STREAM. */
X
Xdone_encoding()
X{   bits_to_follow += 1;			/* Output two bits that     */
X    if (low<First_qtr) bit_plus_follow(0);	/* select the quarter that  */
X    else bit_plus_follow(1);			/* the current code range   */
X}						/* contains.                */
X
X
X/* OUTPUT BITS PLUS FOLLOWING OPPOSITE BITS. */
X
Xstatic void bit_plus_follow(bit)
X    int bit;