lzw.cpp

非常好用的五子棋游戏源码

// Created:09-21-98
// By Jeff Connelly

// LZW compression

// Based on ORIGSRC\COdLZW.C written by David Bourgin

#include "stdafx.h"
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define EXPORTING
#include "comprlib.h"
#include "lzw.h"

static unsigned long val_to_read = 0, val_to_write = 0;
static unsigned char bit_counter_to_read = 0, bit_counter_to_write = 0;

#define CHAR_DIC_VAL(ptr_dic) ((*(ptr_dic)).character)
#define CODE_DIC_VAL(ptr_dic) ((*(ptr_dic)).code)
#define PLEFT_DIC_VAL(ptr_dic) ((*(ptr_dic)).left_ptr)
#define PRIGHT_DIC_VAL(ptr_dic) ((*(ptr_dic)).right_ptr)

// Enforces including marker codes and initalization_code and
// end_information_code. Comment out to not do that.
#define TYPE_GIF_ENCODING

// Word counter already known in dictionary
static unsigned int index_dic;
// Bit counter in encoding
static unsigned char bit_counter_encoding;

// 2 ^ EXP2_DIC_MAX gives the maximum word counter in the dictionary
// during all the compressions.   Possible values: 3 to 25
// Note: Higher than 12 can make some memory allocation errors depending
// on compiler and computer.
#define EXP2_DIC_MAX    12

// Maxium word counter in dictionary during one compression.  Ranges from
// end_information_code to 2 ^ EXP2_DIC_MAX
static unsigned int index_dic_max;

// Bit counter for each data input.  If input_bit_counter = 1, we can
// compress/decompress monochrome pictures if with input_bit_counter = 8
// 256-color (8-bit) pictures or any kind of files can be handled.
static unsigned char input_bit_counter;

// Bit counter to encode "initalization_code"
static unsigned char bit_counter_min_encoding;
 
// Both are consecutive coming up just after the last known word in the
// inital dictionary.
static unsigned int initialization_code, end_information_code;

static p_dic_val dictionary[1 << EXP2_DIC_MAX];

// First initalization of the dictionary
static void init_dictionary1()
{
    register unsigned int i;

    index_dic_max = 1 << 12;  // Possible values: 2 ^ 3 to 2 ^ EXP2_DIC_MAX
    input_bit_counter = 8;    // Can be 1 to EXP2_DIC_MAX - 1

    if (input_bit_counter == 1)
        bit_counter_min_encoding = 3;
    else
        bit_counter_min_encoding = input_bit_counter + 1;
    initialization_code = 1 << (bit_counter_min_encoding - 1);

#ifdef TYPE_GIF_ENCODING
    end_information_code = initialization_code + 1;
#else
    end_information_code = initialization_code - 1;
#endif

    for (i = 0; i <= end_information_code; i++)
    {
        if ((dictionary[i] = (p_dic_val)malloc(sizeof(t_dic_val))) == NULL)
        {
            while (i)
            {
                --i;
                free (dictionary[i]);
            }
            EXCEPTION (ERR_MEMORY, "Memory allocation for dictionary failed",
                                   "init_dictionary1()");
        }
        CHAR_DIC_VAL (dictionary[i]) = i;
        CODE_DIC_VAL (dictionary[i]) = i;
        PLEFT_DIC_VAL(dictionary[i]) = NULL;
        PRIGHT_DIC_VAL(dictionary[i]) = NULL;
    }
    for (; i < index_dic_max; i++)
        dictionary[i] = NULL;
    index_dic = end_information_code + 1;
    bit_counter_encoding = bit_counter_min_encoding;
}

// Initalization of the dictionary during encoding
static void init_dictionary2 ()
{
    register unsigned int i;
    for (i = 0; i < index_dic_max; i++)
        PLEFT_DIC_VAL(dictionary[i]) = PRIGHT_DIC_VAL(dictionary[i]) = NULL;
    index_dic = end_information_code + 1;
    bit_counter_encoding = bit_counter_min_encoding;
}

// Frees memory allocated for the dictionary
static void remove_dictionary ()
{
    register unsigned int i;
    for (i = 0; (i < index_dic_max) && (dictionary[i] != NULL); i++)
        free (dictionary[i]);
}

// Looks for symbol from current_node.  Made from the left pointer of
// current_node and move right until we reach the node containing symbol or
// the left ne width right pointer is NULL
static p_dic_val find_node (p_dic_val current_node, unsigned int symbol)
{
    p_dic_val new_node;

    if (!(PLEFT_DIC_VAL(current_node)))
        return current_node;
    else
    {
        new_node = PLEFT_DIC_VAL(current_node);
        while ((CHAR_DIC_VAL(new_node) != symbol) && (PRIGHT_DIC_VAL(new_node)))
            new_node = PRIGHT_DIC_VAL(new_node);
        return new_node;
    }
}

static void add_node (p_dic_val current_node, p_dic_val new_node,
               unsigned int symbol)
{
    if (!dictionary[index_dic])
    {
        if ((dictionary[index_dic] = (p_dic_val)malloc(sizeof(t_dic_val))) == NULL)
        {
            remove_dictionary ();
            EXCEPTION (ERR_MEMORY, "Memory allocation for adding new node failed",
                                   "add_node()");
        }
        CODE_DIC_VAL(dictionary[index_dic]) = index_dic;
        PLEFT_DIC_VAL(dictionary[index_dic]) = NULL;
        PRIGHT_DIC_VAL(dictionary[index_dic]) = NULL;
    }
    CHAR_DIC_VAL (dictionary[index_dic]) = symbol;
    if (current_node == new_node)
        PLEFT_DIC_VAL(new_node) = dictionary[index_dic];
    else
        PRIGHT_DIC_VAL(new_node) = dictionary[index_dic];
    ++index_dic;
    if ((signed)index_dic == (1 << bit_counter_encoding))
        ++bit_counter_encoding;
}

#define dictionary_sature() (index_dic == index_dic_max)

// Sends the value coded on bit_counter_encoding in the stream.  Bits are
// stored left to right.  For example, aaabbbbcccc is written:
// Bits     7 6 5 4 3 2 1 0
// Byte 1   a a a b b b b c
// Byte 2   c c c ? ? ? ? ?
static void write_code_lr (unsigned int value)
{
    val_to_write = (val_to_write << bit_counter_encoding) | value;
    bit_counter_to_write += bit_counter_encoding;
    while (bit_counter_to_write >= 8)
    {
        bit_counter_to_write -= 8;
        write_byte ((unsigned char)(val_to_write >> bit_counter_to_write));
        val_to_write &= ((1 << bit_counter_to_write) - 1);
    }
}

// Adds 0-bits to the last byte to write, if any.  To be considered with the
// function write_code_lr
static void complete_encoding_lr ()
{
    if (bit_counter_to_write > 0)
        write_byte ((unsigned char)
                    (val_to_write << (8 - bit_counter_to_write)));
    val_to_write = bit_counter_to_write = 0;
}

// Sends the value coded on bit_counter_encoding bits in the stream.  The Bits
// are stored from right to left.  Example: aaabbbbcccc becomes:
// Bits     7 6 5 4 3 2 1 0
// Byte 1   c b b b b a a a
// Byte 2   ? ? ? ? ? c c c
static void write_code_rl (unsigned int value)
{
    val_to_write |= ((unsigned long)value) << bit_counter_to_write;
    bit_counter_to_write += bit_counter_encoding;
    while (bit_counter_to_write >= 8)
    {
        bit_counter_to_write -= 8;
        write_byte ((unsigned char)(val_to_write & 0xFF));
        val_to_write = (val_to_write >> 8) & ((1 << bit_counter_to_write)
                        - 1);
    }
}

// Adds 0-bits to the lat byte to write, if any.  To be considered with
// write_code_rl
static void complete_encoding_rl ()
{
    if (bit_counter_to_write > 0)
        write_byte ((unsigned char)val_to_write);
    val_to_write = bit_counter_to_write = 0;
}

// Reads input_bit_counter via read_byte
static unsigned int read_input ()
{
    unsigned int read_code;
    while (bit_counter_to_read < input_bit_counter)
    {
        val_to_read = (val_to_read << 8) | read_byte ();
        bit_counter_to_read += 8;
    }
    bit_counter_to_read -= input_bit_counter;
    read_code = val_to_read >> bit_counter_to_read;
    val_to_read &= ((1 << bit_counter_to_read) - 1);
    return read_code;
}

#define end_input() ((bit_counter_to_read < input_bit_counter) && end_of_data())

// Call this to compress with LZW method
void EXPORT lzw_encode ()
{
    p_dic_val current_node, new_node;
    unsigned int symbol;

    if (!end_input())
    {
        init_dictionary1 ();
#ifdef TYPE_GIF_ENCODING
        write_code_lr (initialization_code);
#endif
        current_node = dictionary[read_input()];
        while (!end_input())
        {
            symbol = read_input ();
            new_node = find_node (current_node, symbol);
            if ((new_node != current_node) && (CHAR_DIC_VAL(new_node) == symbol))
                current_node = new_node;
            else
            {
                write_code_lr (CODE_DIC_VAL(current_node));
                add_node(current_node, new_node, symbol);
                if (dictionary_sature ())
                {
#ifdef TYPE_GIF_ENCODING
                    write_code_lr (initialization_code);
#endif
                    init_dictionary2();
                }
                current_node = dictionary[symbol];
            }
        }
        write_code_lr (CODE_DIC_VAL(current_node));
#ifdef TYPE_GIF_ENCODING
        write_code_lr (end_information_code);
#endif
        complete_encoding_lr ();
        remove_dictionary ();
    }
}