model.c

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

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

#include "comp.h"
#include "arith.h"


#define MAX_CUM_FREQ   0x4000   /* maximum cumulative frequency */

struct model

{
        int initial_level;
        int match_level;

        unsigned base_count;
        unsigned sym_freq;

        unsigned order_cum_freq [MAX_ORDER + 2];
        unsigned order_sym_count [MAX_ORDER + 2];
};



/*
        Define circular dictionary large enough to hold complete
        set of active input symbols.

        Extra entries are included in the dictionary corresponding
        to a string of length equal to the maximum order to facilitate
        searching across the end of the dictionary.  This extra space
        is allocated at the front of the dictionary, so that the first
        few entries are never referenced directly.

        An additional table is allocated consisting of one word entries
        used to link equivalent dictionary entries where a hash table is
        used to locate the start of each search chain.

        The last character of the test string is used locate the
        initial hash table entry.  The hash table entries are stored
        as an extension to the link table.

        The link table is accessed through the use of macros to allow
        easy access to this table when its size excceds 64K.
*/

#ifndef FAR_TABLES

static unsigned char dict [MAX_DICT];
static unsigned char base_level [MAX_DICT];
static unsigned int next_dict [MAX_DICT + HTBL1_SIZE];

#define DICT_WORD_PTR(i) ((unsigned *) (&dict [i]));
#define NEXT_DICT(i) next_dict [i]

#else

static unsigned char far *dict;
static unsigned char far *base_level;
#define DICT_WORD_PTR(i) ((unsigned far *) (&dict [i]));

#ifdef SPLIT_TABLES

static unsigned int far *next_dict [2];
#define NEXT_DICT(i) next_dict [i & 1] [i >> 1]

#else

static unsigned int far *next_dict;
#define NEXT_DICT(i) next_dict [i]

#endif
#endif


static unsigned int node;
static int new_symbol_count;
static unsigned int last_search_node;

static int max_order;
static int max_pos_size;

/*
        Define table of entries for each order giving number of symbols
        and total cumulative frequency for each order
*/

static struct model active_state;
static struct model last_state;


/*
        Define set of save areas for the state at the potential start any string
        The areas are used in rotation until a substring is matched equal to
        the minimum string length.  Normal symbol compression is performed
        during the time that the substring matches the input data.
                
        When the first non matching character is encountered, the lengths of
        the string and the compressed symbols are compared.  If the string
        length is less, the output is repositioned as specified by the
        state at the start of the string, and the string selection sequence
        overwrites the output.
*/

static struct

{
        int i;
        struct coder_state cs;
        struct model mod;
} save_state [MAX_STR_SAVE];


static int save_state_index;
static unsigned int string_pos;
static int string_len;
static int string_start;
static int skip_count;

/*
        States used while testing for text string replacements
*/

static enum
{
        STRING_WAIT,  STRING_SEARCH,  STRING_START,  STRING_ACTIVE,
        STRING_COMP,
} string_state;


/*
        Define combined set of tables giving the order and
        frequency count for each symbol encountered during dictionary scan
        Also accumulate base frequency values for each order
*/

static unsigned char level [MAX_SYM];
static unsigned int freq [MAX_SYM];
static unsigned int base_freq [MAX_ORDER + 2];

static unsigned int dup_count = 0;
static int dup_char = -1;

/*
        Build frequency table for zero and default orders
        Used to initialize state tables at start of each dictionary scan

        Always contains nonzero count for every symbol
        Includes order for each symbol selecting zero or default orders
        Initially set to all defaults with symbol frequency one
*/

static unsigned int sym_count_zero;
static unsigned int cum_freq_zero;
static unsigned int freq_zero [MAX_SYM];
static unsigned char order_zero [MAX_SYM];


/*
        Prototypes
*/

static void clear_context (void);
static void scan_dict (int);
static void scale_freq_tbl (int, int);
static void calc_symbol_freq (int);
static void select_output_symbol (void);
static int decode_symbol (void);
static void update_model (int);

static void encode_symbol (struct model *);
static void generate_switch_code (struct model *);
static void generate_symbol_code (struct model *);
static void generate_value (unsigned, unsigned);

static int start_decode_string (void);
static int decode_active_state (void);
static int decode_string_char (void);
static unsigned decode_value (unsigned);

static unsigned switch_char_freq (unsigned, unsigned);

static void delete_dict_entry (int);
static void test_string_state (void);
static void clear_text_string (void);

static void check_string_cont (void);
static void test_string_start (unsigned pos, int n);
static void test_string_resume (unsigned pos, int n);
static void replace_text_string (void);

static int log2 (unsigned);
static void scale_binary_value (long, int *, unsigned *);
static void update_bit_len (unsigned, unsigned, int *, unsigned *);
static int find_string_len (void);


/*
        Initialize model at start of compression or expansion
        Alocate and initialize tables
*/

void InitModel (int n)

{
        unsigned i;

        InitCoder ();

        active_state.initial_level = 1;
        node = MAX_ORDER;
        max_pos_size = log2 (NDICT - 1) + 1;
        max_order = n;
        if (max_order == 0) max_order = 1;

        sym_count_zero = 0;
        cum_freq_zero = 0;

#ifdef FAR_TABLES

        dict = farmalloc (MAX_DICT * sizeof (unsigned char));
        base_level = farmalloc (MAX_DICT * sizeof (unsigned char));

#ifndef SPLIT_TABLES

        next_dict = farmalloc ((MAX_DICT + HTBL1_SIZE) * sizeof (unsigned int));

        if (dict == NULL || base_level == NULL || next_dict == NULL)
        {
                printf ("Memory allocation failure\n");
                exit (EXIT_FAILURE);
        }

#else

        next_dict [0] = farmalloc ((MAX_DICT + HTBL1_SIZE + 1) / 2 * sizeof (unsigned int));
        next_dict [1] = farmalloc ((MAX_DICT + HTBL1_SIZE + 1) / 2 * sizeof (unsigned int));

        if (dict == NULL || base_level == NULL || next_dict [1] == NULL)
        {
                printf ("Memory allocation failure\n");
                exit (EXIT_FAILURE);
        }

        #endif  /* SPLIT_TABLES */

#endif  /* FAR_TABLES */

        for (i = 0; i < MAX_SYM; i ++)
        {
                freq_zero [i] = 1;
                order_zero [i] = 0;
        }

        for (i = 0; i < MAX_DICT + HTBL1_SIZE; i ++)
                NEXT_DICT (i) = NIL_DICT_PTR;

        for (i = 0; i < MAX_DICT; i ++)
        {
                dict [i] = 0;
                base_level [i] = 0;
        }

        save_state_index = 0;
        string_pos = 0;
        string_len = 0;
        string_start = 0;
        skip_count = MIN_STR;
        string_state = STRING_WAIT;
}




/*
        Compress next symbol
*/

void CompressSymbol (int ch)

{
        int i;
        unsigned cfreq;

        if (string_state == STRING_ACTIVE) check_string_cont ();

        if (dup_count > max_order + 2)
        {
                ++ active_state.order_cum_freq [max_order + 1];
                ++ freq [dup_char];

                if (ch != dup_char)
                {
                        for (i = 0, cfreq = 0; i < ch; i ++)
                        {
                                if (level [i] == level [ch]) cfreq += freq [i];
                        }
                        
                        base_freq [level [ch]] = cfreq;
                }
        }
        else
        {
                clear_context ();
                for (i = 0; i < max_order + 2; i ++) base_freq [i] = 0;
                scan_dict (ch);
        }

        for (i = 1; i <= active_state.initial_level; i ++)
        {
                while (active_state.order_cum_freq [i] > MAX_CUM_FREQ)
                        scale_freq_tbl (i, ch);
        }

        test_string_state ();

        calc_symbol_freq (ch);
        select_output_symbol ();
        update_model (ch);
}



/*
        Expand next symbol from input stream
*/

int ExpandSymbol (void)

{
        int ch;

        if (dup_count > max_order + 2)
        {
                ++ active_state.order_cum_freq [max_order + 1];
                ++ freq [dup_char];
        }
        else
        {
                clear_context ();
                scan_dict (0);
        }

        ch = string_len == 0 ? decode_symbol () : decode_string_char ();
        update_model (ch);
        
        return ch;
}



/*
        Update tables used by model for new symbol
        Link new symbol into dictionary
        Delete oldest symbol in dictionary, if required
        Update zero order frequencies if no higher level context found
*/

static void update_model (int ch)

{
        int n;

        NEXT_DICT (node) = NIL_DICT_PTR;
        NEXT_DICT (last_search_node) = node;
        last_search_node = node;

        if (active_state.match_level < 2)
        {
                cum_freq_zero ++;
                if (order_zero [ch])
                        freq_zero [ch] ++;
                else
                {
                        order_zero [ch] = 1;
                        sym_count_zero ++;
                }
        }

        dict [node] = ch;
        if (ch == dup_char)
                dup_count ++;
        else
        {
                dup_char = ch;
                dup_count = 0;
        }

        n = active_state.match_level;
        if (n == 0) n = 1;
        base_level [node] = n;

        delete_dict_entry (node + max_order);

        active_state.initial_level = active_state.match_level;
        if (active_state.initial_level <= max_order)
                active_state.initial_level ++;

        if (++ node == MAX_DICT)
        {
                node = MAX_ORDER;
                for (n = 1; n <= max_order; n ++)
                        dict [MAX_ORDER - n] = dict [MAX_DICT - n];
        }
}



/*
        Delete oldest symbol from dictionary
        Update frequency counts if added for lower order
*/

static void delete_dict_entry (int i)

{
        unsigned int n;
        int j;

        n = i;
        if (n >= MAX_DICT) n -= NDICT;

        switch (base_level [n])
        {
                case 0:
                        break;

                case 1:
                        j = dict [n];
                        cum_freq_zero --;
                        if (-- freq_zero [j] == 0)
                        {
                                order_zero [j] = 0;
                                freq_zero [j] = 1;
                                sym_count_zero --;
                        }

                default:
                        j = dict [n - 1];
                        NEXT_DICT (j + MAX_DICT) = NEXT_DICT (n);