
/* This program contains the source code from the 1987 CACM
   article by Witten, Neal, and Cleary. */

#include <stdio.h>
#include <stdlib.h>

/* The indata and outdata buffer, defined and allocated in "uncompress.c" */
extern unsigned char *in;
extern unsigned char *deari;

/* Positions in buffers */
unsigned int in_pos;
unsigned int deari_pos;

unsigned int in_size;

/* THE SET OF SYMBOLS THAT MAY BE ENCODED. */

#define No_of_chars 256                 /* Number of character symbols      */
#define EOF_symbol (No_of_chars+1)      /* Index of EOF symbol              */

#define No_of_symbols (No_of_chars+1)   /* Total number of symbols          */


/* TRANSLATION TABLES BETWEEN CHARACTERS AND SYMBOL INDEXES. */

int char_to_index[No_of_chars];         /* To index from character          */
unsigned char index_to_char[No_of_symbols+1]; /* To character from index    */

int freq[No_of_symbols+1];      /* Symbol frequencies                       */
int cum_freq[No_of_symbols+1];  /* Cumulative symbol frequencies            */

/* CUMULATIVE FREQUENCY TABLE. */

#define Max_frequency 16383             /* Maximum allowed frequency count  */

/* DECLARATIONS USED FOR ARITHMETIC ENCODING AND DECODING */


/* SIZE OF ARITHMETIC CODE VALUES. */

#define Code_value_bits 16              /* Number of bits in a code value   */
typedef long code_value;                /* Type of an arithmetic code value */

#define Top_value (((long)1<<Code_value_bits)-1)      /* Largest code value */


/* HALF AND QUARTER POINTS IN THE CODE VALUE RANGE. */

#define First_qtr (Top_value/4+1)       /* Point after first quarter        */
#define Half      (2*First_qtr)         /* Point after first half           */
#define Third_qtr (3*First_qtr)         /* Point after third quarter        */


/* BIT INPUT ROUTINES. */

/* THE BIT BUFFER. */

int buffer;                     /* Bits waiting to be input                 */
int bits_to_go;                 /* Number of bits still in buffer           */
int garbage_bits;               /* Number of bits past end-of-file          */


/* INITIALIZE BIT INPUT. */

static void start_inputing_bits( void )
{   bits_to_go = 0;                             /* Buffer starts out with   */
    garbage_bits = 0;                           /* no bits in it.           */
}


/* INPUT A BIT. */

static int input_bit( void )
{
  int t;
  if (bits_to_go==0) {
    if (in_pos<in_size)                      /* Read the next byte if no */
      buffer = in[in_pos++];                 /* bits are left in buffer. */
    else {
      garbage_bits += 1;                      /* Return arbitrary bits*/
      if (garbage_bits>Code_value_bits-2) {   /* after eof, but check */
	fprintf(stderr,"Bad input file\n");   /* for too many such.   */
	exit(-1);
      }
    }
    bits_to_go = 8;
  }
  t = buffer&1;                               /* Return the next bit from */
  buffer >>= 1;                               /* the bottom of the byte.  */
  bits_to_go -= 1;
  return t;
}


static void start_model( void );
static void start_decoding( void );
static int decode_symbol( int cum_freq[] );
static void update_model( int symbol );

unsigned int do_deari(unsigned int insize)
{
  in_size = (unsigned int)insize;    
  
  in_pos = 0;
  deari_pos = 0;

  start_model();                              /* Set up other modules.    */
  start_inputing_bits();
  start_decoding();
  for (;;) {                                  /* Loop through characters. */
    int ch; int symbol;
    symbol = decode_symbol(cum_freq);       /* Decode next symbol.      */
    if (symbol==EOF_symbol) break;          /* Exit loop if EOF symbol. */
    ch = index_to_char[symbol];             /* Translate to a character.*/
    deari[deari_pos++]=(unsigned char)ch;   /* Write that character.    */
    update_model(symbol);                   /* Update the model.        */
  }
  
  return deari_pos;
}

/* ARITHMETIC DECODING ALGORITHM. */

/* CURRENT STATE OF THE DECODING. */

static code_value value;        /* Currently-seen code value                */
static code_value low, high;    /* Ends of current code region              */

/* START DECODING A STREAM OF SYMBOLS. */

static void start_decoding( void )
{   int i;
    value = 0;                                  /* Input bits to fill the   */
    for (i = 1; i<=Code_value_bits; i++) {      /* code value.              */
        value = 2*value+input_bit();
    }
    low = 0;                                    /* Full code range.         */
    high = Top_value;
}


/* DECODE THE NEXT SYMBOL. */

static int decode_symbol( int cum_freq[] )
{   long range;                 /* Size of current code region              */
    int cum;                    /* Cumulative frequency calculated          */
    int symbol;                 /* Symbol decoded                           */
    range = (long)(high-low)+1;
    cum = (int)                                 /* Find cum freq for value. */
      ((((long)(value-low)+1)*cum_freq[0]-1)/range);
    for (symbol = 1; cum_freq[symbol]>cum; symbol++) ; /* Then find symbol. */
    high = low +                                /* Narrow the code region   */
      (range*cum_freq[symbol-1])/cum_freq[0]-1; /* to that allotted to this */
    low = low +                                 /* symbol.                  */
      (range*cum_freq[symbol])/cum_freq[0];
    for (;;) {                                  /* Loop to get rid of bits. */
        if (high<Half) {
            /* nothing */                       /* Expand low half.         */
        }
        else if (low>=Half) {                   /* Expand high half.        */
            value -= Half;
            low -= Half;                        /* Subtract offset to top.  */
            high -= Half;
        }
        else if (low>=First_qtr                 /* Expand middle half.      */
              && high<Third_qtr) {
            value -= First_qtr;
            low -= First_qtr;                   /* Subtract offset to middle*/
            high -= First_qtr;
        }
        else break;                             /* Otherwise exit loop.     */
        low = 2*low;
        high = 2*high+1;                        /* Scale up code range.     */
        value = 2*value+input_bit();            /* Move in next input bit.  */
    }
    return symbol;
}

/* THE ADAPTIVE SOURCE MODEL */

/* INITIALIZE THE MODEL. */

static void start_model( void )
{   int i;
    for (i = 0; i<No_of_chars; i++) {           /* Set up tables that       */
        char_to_index[i] = i+1;                 /* translate between symbol */
        index_to_char[i+1] = (unsigned char) i; /* indexes and characters.  */
    }
    for (i = 0; i<=No_of_symbols; i++) {        /* Set up initial frequency */
        freq[i] = 1;                            /* counts to be one for all */
        cum_freq[i] = No_of_symbols-i;          /* symbols.                 */
    }
    freq[0] = 0;                                /* Freq[0] must not be the  */
}                                               /* same as freq[1].         */


/* UPDATE THE MODEL TO ACCOUNT FOR A NEW SYMBOL. */

static void update_model( int symbol )
{   int i;                      /* New index for symbol                     */
    if (cum_freq[0]==Max_frequency) {           /* See if frequency counts  */
        int cum;                                /* are at their maximum.    */
        cum = 0;
        for (i = No_of_symbols; i>=0; i--) {    /* If so, halve all the     */
            freq[i] = (freq[i]+1)/2;            /* counts (keeping them     */
            cum_freq[i] = cum;                  /* non-zero).               */
            cum += freq[i];
        }
    }
    for (i = symbol; freq[i]==freq[i-1]; i--) ; /* Find symbol's new index. */
    if (i<symbol) {
        int ch_i, ch_symbol;
        ch_i = index_to_char[i];                /* Update the translation   */
        ch_symbol = index_to_char[symbol];      /* tables if the symbol has */
        index_to_char[i] = (unsigned char) ch_symbol; /* moved.             */
        index_to_char[symbol] = (unsigned char) ch_i;
        char_to_index[ch_i] = symbol;
        char_to_index[ch_symbol] = i;
    }
    freq[i] += 1;                               /* Increment the frequency  */
    while (i>0) {                               /* count for the symbol and */
        i -= 1;                                 /* update the cumulative    */
        cum_freq[i] += 1;                       /* frequencies.             */
    }
}