model.c

一个含有compress、expand、lzw等等压缩算法的源码

                        break;
        }
}


/*
        Initialize tables at start of dictionary scan
        Establish counts based on low order tables
*/

static void clear_context (void)

{
        int i;

        for (i = 2; i < max_order + 2; i ++)
        {
                active_state.order_sym_count [i] = 0;
                active_state.order_cum_freq [i] = 0;
        }

        active_state.order_sym_count [1] = sym_count_zero;
        active_state.order_sym_count [0] = MAX_SYM - sym_count_zero;

        active_state.order_cum_freq [1] = cum_freq_zero;
        active_state.order_cum_freq [0] = MAX_SYM - sym_count_zero;

        movmem (freq_zero, freq, sizeof freq);
        movmem (order_zero, level, sizeof level);
}



/*
        Perform search of dictionary to locate active contexts
        Accumulate freqencies for all symbols encounered
        Use initial character of input string to select the starting table value
*/

static void scan_dict (int base_char)

{
        unsigned int k;
        unsigned int jnode;
        int ch;
        int n;

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

        while (jnode != NIL_DICT_PTR)
        {
                ch = dict [jnode];
                for (n = 2; n < max_order + 1; n ++)
                {
                        if (dict [node - n] != dict [jnode - n]) break;
                }

                switch (string_state)
                {
                        case STRING_SEARCH:
                        case STRING_START:
                                test_string_start (jnode, n);
                                break;

                        case STRING_COMP:
                                test_string_resume (jnode, n);
                                break;
                }

                if (base_level [jnode] <= n)
                {
                        k = level [ch];
                        if (k < n)
                        {
                                active_state.order_cum_freq [k] -= freq [ch];
                                active_state.order_sym_count [k] --;

                                active_state.order_cum_freq [n] ++;
                                active_state.order_sym_count [n] ++;

                                if (ch < base_char)
                                {
                                        base_freq [k] -= freq [ch];
                                        base_freq [n] ++;
                                }

                                level [ch] = n;
                                freq [ch] = 1;

                                if (n > active_state.initial_level) active_state.initial_level = n;
                        }
                        else
                        if (k == n)
                        {
                                active_state.order_cum_freq [n] ++;
                                freq [ch] ++;
                                if (ch < base_char) base_freq [n] ++;
                        }
                }

                last_search_node = jnode;
                jnode = NEXT_DICT (jnode);
        }
}



/*
        Test for continued text substring
        Executed before the start of each dictionary scan during compression
*/

static void check_string_cont (void)

{
        int j;

        j = string_pos + string_len;
        if (j >= MAX_DICT) j -= NDICT;

        if (dict [node - 1] == dict [j])
                string_len ++;
        else
                string_state = STRING_COMP;
}



/*
        Test for start of potential text substring
        Executed during dictionary scan based on string state variable
*/

static void test_string_start (unsigned pos, int n)

{
        if (n > MIN_STR)
        {
                string_pos = pos;
                if (string_pos < MIN_STR + MAX_ORDER) string_pos += NDICT;
                string_pos -= MIN_STR;
                string_len = MIN_STR;
                string_state = STRING_START;
        }
}



static void test_string_resume (unsigned pos, int n)

{
        if (n > string_len + 1)
        {
                string_state = STRING_ACTIVE;
                string_len ++;
                string_pos = pos;
                if (string_pos < string_len + MAX_ORDER) string_pos += NDICT;
                string_pos -= string_len;
        }
        else
        if (n == max_order + 1)
        {
                unsigned i2, j2, n2;

                i2 = node - max_order - 1;
                j2 = pos - max_order - 1;

                for (n2 = max_order + 1; n2 <= string_len + 1; n2 ++)
                {
                        if (i2 < MAX_ORDER) i2 += NDICT;
                        if (j2 < MAX_ORDER) j2 += NDICT;
                        if (dict [i2 --] != dict [j2 --]) break;
                }

                if (n2 > string_len + 1)
                {
                        string_state = STRING_ACTIVE;
                        string_len ++;
                        string_pos = pos;
                        if (string_pos < string_len + MAX_ORDER) string_pos += NDICT;
                        string_pos -= string_len;
                }
        }
}



/*
        Test status of text substring match procedure
        Performed after each dictionary scan
*/

static void test_string_state (void)

{
        switch (string_state)
        {
                case STRING_WAIT:
                        save_state [string_start].mod = active_state;
                        SaveCoderState (&save_state [string_start].cs);

                        if (++ string_start == MAX_STR_SAVE) string_start = 0;
                        if (-- skip_count == 0) string_state = STRING_SEARCH;
                        break;

                case STRING_SEARCH:
                        save_state [string_start].mod = active_state;
                        SaveCoderState (&save_state [string_start].cs);
                        if (++ string_start == MAX_STR_SAVE) string_start = 0;
                        break;

                case STRING_ACTIVE:
                        if (string_len > MAX_STR)
                        {
                                string_len --;
                                clear_text_string ();
                        }
                        break;

                case STRING_COMP:
                        clear_text_string ();
                        break;
        }
}



/*
        End of text substring
        Test for minimum code length of dtring versus coded symbols
        Reposition output and write string selection if less
        Set up for start of next string
*/

static void clear_text_string (void)

{
        int nbits;
        int i;

        if (string_len >= MIN_STR)
        {
                nbits = find_string_len ();
                if (nbits > 0)
                {
                        replace_text_string ();

                        i = node;
                        if (i <= string_len) i += NDICT;
                        i -= string_len + 1;
                }
        }

        save_state [string_start].mod = last_state;
        SaveCoderState (&save_state [string_start].cs);

        if (++ string_start == MAX_STR_SAVE) string_start = 0;

        encode_symbol (&last_state);

        save_state [string_start].mod = active_state;
        SaveCoderState (&save_state [string_start].cs);

        if (++ string_start == MAX_STR_SAVE) string_start = 0;
        skip_count = MIN_STR - 2;
        string_len = 0;

        string_state = STRING_WAIT;
}



/*
        Estimate size of string reference
        Returns size relative to actual length used by coded symbols
*/

static int find_string_len (void)

{
        int nbits;
        unsigned f;

        struct model start_context;
        unsigned i;
        unsigned n;
        unsigned j;
        int m;
        unsigned c1;

        nbits = 0;
        f = 0;

        new_symbol_count = MAX_SYM;
        m = save_state [string_start].mod.match_level;
        start_context = save_state [string_start].mod;

/*
        Accumulate switch characters for default context
        Include start of string symbol
*/

        do
        {
                new_symbol_count -= start_context.order_sym_count [m];

                c1 = start_context.order_cum_freq [m];
                n = switch_char_freq (start_context.order_sym_count [m], c1);

                update_bit_len (n, c1 + n, &nbits, &f);
        } while (-- m > 0);

        c1 = start_context.order_cum_freq [0];
        update_bit_len (1, c1, &nbits, &f);

/*
        Include string length
*/

        nbits += 6;
        if (string_len - MIN_STR >= 63) nbits += 8;

/*
        Calculate relative location of start of string
        Output as bit count and offset
*/

        update_bit_len (1, max_pos_size, &nbits, &f);

        i = string_pos + string_len;
        if (i >= MAX_DICT) i -= NDICT;
        j = i < node ? node - i - 1 : node + NDICT - 1 - i;
        nbits += log2 (j);

        return CodeLength (&save_state [string_start].cs) - nbits;
}



/*
        Generate coded symbols for text substring
        Used when string length is less length used by actual symbols
*/

static void replace_text_string (void)

{
        struct model start_context;
        unsigned n;
        unsigned i, j;

        RestoreCoderState (&save_state [string_start].cs);

        new_symbol_count = MAX_SYM;
        start_context = save_state [string_start].mod;

/*
        Output switch codes for default context and start string symbol
*/

        start_context.match_level = 0;
        start_context.base_count = start_context.order_cum_freq [0] - 1;
        start_context.sym_freq = 1;

        encode_symbol (&start_context);

/*
        Output string length
*/
        n = string_len - MIN_STR;
        if (n < MAX_STR_CODE - 1)
                generate_value (n, MAX_STR_CODE);
        else
        {
                generate_value (MAX_STR_CODE - 1, MAX_STR_CODE);
                generate_value (n + 1 - MAX_STR_CODE, 256);
        }

/*
        Determine relative location of start of string
*/

        i = string_pos + string_len;
        if (i >= MAX_DICT) i -= NDICT;
        j = i < node ? node - i - 1 : node - i - 1 + NDICT;
        n = 2;
        if (j < 2)
                i = 0;
        else
        {
                for (i = 1; 2 * n <= j && n < 0x8000; i ++, n <<= 1);
                j -= n;
        }

/*
        Output bit length of relative string location
*/

        generate_value (i, max_pos_size);

/*
        Output string location in 8 bit pices if required
*/

        if (i > 8)
        {
                generate_value (j & 0xFF, 256);
                j >>= 8;
                n >>= 8;
        }

        generate_value (j, n);
}


/*
        Scale frequency tables if total cumulative frequency exceeds maximum
        Also recalculates frequencies for current input symbol
*/

static void scale_freq_tbl (int order, int ch)

{
        int i;
        unsigned cfreq;
        unsigned t;

        i = 0;
        cfreq = 0;

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