base_freq [order] = cfreq;

                t = (freq [i] + 1) >> 1;
                freq [i] = t;
                i ++;

                cfreq += t;
        }

        for (; i < MAX_CHAR_CODE; i ++)
        {
                if (level [i] == order)
                {
                        t = (freq [i] + 1) >> 1;
                        freq [i] = t;
                        cfreq += t;
                }
        }

        active_state.order_cum_freq [order] = cfreq;
}


/*
        Determine symbol frequency counts for coder
*/

static void calc_symbol_freq (int ch)

{
        int i;

        active_state.match_level = level [ch];
        active_state.sym_freq = freq [ch];

        if (active_state.match_level > 1)
                active_state.base_count = base_freq [active_state.match_level];
        else
        {
                active_state.base_count = 0;
                for (i = 0; i < ch; i ++)
                {
                        if (level [i] == active_state.match_level)
                                active_state.base_count += freq [i];
                }
        }
}


/*
        Select state structure containing symbol to be output
        Generate coded symbol value if required

        Note that there is a one character delay during substring matching
        so that the non matching character at end of string is not output
        until after string replacement has occurred
*/

static void select_output_symbol (void)

{
        switch (string_state)
        {
                case STRING_START:
                        last_state = active_state;
                        string_state = STRING_ACTIVE;
                        break;

                case STRING_ACTIVE:
                        encode_symbol (&last_state);
                        last_state = active_state;
                        break;

                default:
                        encode_symbol (&active_state);
                        break;
        }
}


/*
        Generate coded value for symbol defined by input state variable
        State includes symbol frequencies and all values used by coder
*/

static void encode_symbol (struct model *cptr)

{
        int i;

        new_symbol_count = MAX_SYM;
        i = cptr -> match_level;
        while (i < cptr -> initial_level)
        {
                new_symbol_count -= cptr -> order_sym_count [cptr -> initial_level];
                generate_switch_code (cptr);
                cptr -> initial_level --;
        }

        new_symbol_count -= cptr -> order_sym_count [i];
        generate_symbol_code (cptr);
}


/*
        Generate code for switch character to select next lower context
        Input consists of state variable for symbol
*/

static void generate_switch_code (struct model *cptr)

{
        unsigned c1;
        unsigned n, m;

        n = cptr -> initial_level;
        c1 = cptr -> order_cum_freq [n];
        m = switch_char_freq (cptr -> order_sym_count [n], c1);

        EncodeArith (c1, m, c1 + m);
}


/*
        Generate code for symbol defined by input state variable
*/

static void generate_symbol_code (struct model *cptr)

{
        unsigned int c1, c2, c3;
        int n;

        n = cptr -> initial_level;
        c1 = cptr -> base_count;
        c2 = cptr -> sym_freq;
        c3 = cptr -> order_cum_freq [n];

        if (n > 0) c3 += switch_char_freq (cptr -> order_sym_count [n], c3);

        EncodeArith (c1, c2, c3);
}



/*
        Estimate frequency to be allocated to the switch character
        Use number of symbols referenced in current context and the
        number of unreferenced symbols so far

        Value should reflect probability of encountering a symbol
        already present in the active context
*/

static unsigned switch_char_freq (unsigned scount, unsigned cmax)

{       unsigned n;

        n = (scount + 1) * new_symbol_count / (scount + new_symbol_count);
        if (n + cmax > MAX_CUM_FREQ) n = MAX_CUM_FREQ + 1 - cmax;

        return n;
}


/*
        End of compression procedure
        Terminate active substring processing
        Close arithmetic coder and flush output
*/

void CloseModel (void)

{
        if (string_state == STRING_ACTIVE) clear_text_string ();
        CloseCoder ();
}



/*
        Decode next input symbol from input stream
        Test for context switch and repeat until non switch symbol encountered
*/

static int decode_symbol (void)

{
        int ch;

        new_symbol_count = MAX_SYM;
        active_state.match_level = active_state.initial_level;

        new_symbol_count -= active_state.order_sym_count [active_state.match_level];
        ch = decode_active_state ();

        while (ch == SWITCH_SYM)
        {
                active_state.match_level --;
                new_symbol_count -= active_state.order_sym_count [active_state.match_level];
                ch = decode_active_state ();
        }

        if (ch == START_STRING) ch = start_decode_string ();

        return ch;
}



/*
        Start of string symbol encountered
        Extract string length and position from input stream
        Returns first character in string
*/

static int start_decode_string (void)

{
        unsigned i, j, k;
        unsigned n;

        string_len = decode_value (MAX_STR_CODE);
        if (string_len == MAX_STR_CODE - 1) string_len += decode_value (256);
        string_len += MIN_STR;

        i = decode_value (max_pos_size);
        if (i == 0)
        {
                i = 2;
                j = decode_value (2);
        }
        else
        if (i > 8)
        {
                j = decode_value (256);
                i -= 8;
                n = 1 << i;
                k = decode_value (n);
                k += n;
                k <<= 8;
                j += k;
        }
        else
        {
                n = 1 << i;
                j = decode_value (n);
                j += n;
        }

        string_pos = node < j + MAX_ORDER ? node + NDICT - j : node - j;

        return decode_string_char ();
}



/*
        Locate next character in text substring
        Increment string pointers and decrement length
        Set parameters used for updating state variable
*/

static int decode_string_char (void)

{
        int ch;
        unsigned int j;

        ch = dict [string_pos];
        active_state.match_level = level [ch];

        string_len --;
        if (++ string_pos == MAX_DICT) string_pos = MAX_ORDER;

        last_search_node = dict [node - 1] + MAX_DICT;
        j = NEXT_DICT (last_search_node);

        while (j != NIL_DICT_PTR)
        {
                last_search_node = j;
                j = NEXT_DICT (j);
        }

        return ch;
}


/*
        Extract next value from input stream
        Search frequency tables to convert to symbol
        Update arithmetic decoder using symbol frequencies
*/

static int decode_active_state (void)

{
        unsigned c1, c2, c3;
        unsigned sym;
        unsigned m;
        int i;
        int n;

        n = active_state.match_level;
        c2 = active_state.order_cum_freq [n];

        while (c2 > MAX_CUM_FREQ)
        {
                scale_freq_tbl (n, END_OF_FILE);
                c2 = active_state.order_cum_freq [n];
        }

        m = n > 0 ? switch_char_freq (active_state.order_sym_count [n], c2) : 0;
        c3 = c2 + m;

        sym = DecodeArith (c3);
        if (sym < c2)
        {
                c1 = 0;
                for (i = 0; i < MAX_SYM; i ++)
                {
                        if (level [i] == n)
                        {
                                m = freq [i];
                                c1 += m;
                                if (sym < c1) break;
                        }
                }

                c1 -= m;
        }
        else
        {
                c1 = c2;
                i = SWITCH_SYM;
        }

        UpdateDecoder (c1, m, c3);

        return i;
}



/*
        Generate coded output for a constant value within a fixed range
        Value is treated as a symbol with frequency one
*/

static void generate_value (unsigned value, unsigned range)

{
        EncodeArith (value, 1, range);
}


/*
        Extract constant value within fixed range
        Each possible value is treated as symbol with frequency one
*/

static unsigned decode_value (unsigned range)

{       unsigned value;

        value = DecodeArith (range);
        UpdateDecoder (value, 1, range);

        return value;
}



/*
        Determine integer value of base 2 logarithm of integer value
        Use smallest power of two less than input value
*/

static int log2 (unsigned n)

{
        int i;

        for (i = 0; n > 1; i ++, n >>= 1);
        return i;
}



/*
        Scale binary value as part of log calulation
        Input is a binary fraction (32 bits, 16 binary places)
        Extract integer log to base 2
        Return fractional part and accumulate integer part
*/

static void scale_binary_value (long x, int *nbits, unsigned *frac)

{
        int i;

        i = log2 ((unsigned) (x >> 16));
        *nbits += i;
        *frac = (unsigned) (x >> i);
}


/*
        Estimate bit size of arithmetic coded values

        Input consists of symbol frequency (p) and cumulative frequency (q)
        Actual bit size is log to base 2 of (q / p)
        
        Maintain intermediate values as:
        
                n + log2 (1 + f)

        where n is integer and f is the remainder (between 0 and 1.0)
        stored as a 16 bit binary fraction.

        The pair (nbits, frac) contains the starting value for the bit length
        This is updated to include the latest symbol size
*/

static void update_bit_len (unsigned p, unsigned q, int *nbits, unsigned *frac)

{
        long x;
        unsigned f2;

        x = ((long) q << 16) / p;
        scale_binary_value (x, nbits, &f2);

        x = (long) f2 * (long) *frac;
        x >>= 16;
        x += f2;
        x += *frac;
        x += 0x10000L;
        scale_binary_value (x, nbits, frac);
}