arith.cpp

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

// Created:10-30-98
// By Jeff Connelly

// Arithmetic encoding

#include "stdafx.h"
#include <stdio.h>
#define EXPORTING
#include "comprlib.h"

#define MAXIMUM_SCALE   16383   // Maximum allowed frequency count
#define ESCAPE            256   // Escape symbol
#define DONE               -1   // Output stream empty smymbol
#define FLUSH              -2   // Symbol to flush model

// A symbol can be represented as an 'int', or a pair of counts on a scale.
typedef struct
{
    unsigned short low_count;
    unsigned short high_count;
    unsigned short scale;
} SYMBOL;

// Prototypes
static void initialize_arithmetic_decoder();
static void remove_symbol_from_stream(SYMBOL* s);
static void initialize_arithmetic_encoder();
static void encode_symbol(SYMBOL* s);
static void flush_arithmetic_encoder();
static short get_current_count(SYMBOL* s);

// Bit I/O
static short input_bit();
static void initialize_output_bitstream();
static void output_bit(int bit);
static void flush_output_bitstream();
static void initialize_input_bitstream();
static long bit_ftell_output();
static long bit_ftell_input();

#define BUFFER_SIZE   0x100
static char buffer[BUFFER_SIZE + 2];        // I/O buffer
static char* current_byte;                  // Pointer to current byte
static int output_mask;                     // Mask applied to output byte
static int input_bytes_left;                // Variables that keep track of
static int input_bits_left;                 // the input state and end-of-
static int past_eof;                        // file (actually stream) status.

static void initialize_output_bitstream()
{
    current_byte = buffer;
    *current_byte = 0;
    output_mask = 0x80;
}

static void output_bit(int bit)
{
    register int i = 0;

    if (bit)
        *current_byte |= output_mask;
    output_mask >>= 1;
    if (!output_mask)
    {
        output_mask = 0x80;
        ++current_byte;
        if (current_byte == (buffer + BUFFER_SIZE))
        {
            for (i = 0; i < BUFFER_SIZE; ++i)
            {
                write_byte(*(buffer + i));
            }
            current_byte = buffer;
        }
        *current_byte = 0;
    }
}

static void flush_output_bitstream()
{
    register int i;
    for (i = 0; i < (current_byte - buffer) + 1; ++i)
    {
        write_byte(*(buffer + i));
    }
    current_byte = buffer;
}

static void initialize_input_bitstream()
{
    input_bits_left = 0;
    input_bytes_left = 1;
    past_eof = 0;
}

static short input_bit()
{
    register int i = 0;

    if (!input_bits_left)
    {
        ++current_byte;
        --input_bytes_left;
        input_bits_left = 8;
        if (!input_bytes_left)
        {
            input_bytes_left = 0;
            for (input_bytes_left = 0; input_bytes_left < BUFFER_SIZE &&
                 !end_of_data(); ++i)
            {
                buffer[i] = read_byte();
            }
            if (!input_bytes_left)
            {
                if (past_eof)
                {
                    EXCEPTION(ERR_NOTCOMPR, "Bad input file", "input_bit()");
                } else {
                    past_eof = 1;
                    input_bytes_left = 2;
                }
            }
            current_byte = buffer;
        }
    }
    --input_bits_left;
    return ((*current_byte >> input_bits_left) & 1);
}

// State of encoder/decoder
static unsigned short int code;     // Present input code value
static unsigned short int low;      // Start of current code range
static unsigned short int high;     // End of current code range
static long underflow_bits;         // Number of underflow bits pending

// Initialize encoding process
static void initialize_arithmetic_encoder()
{
    low = 0;
    high = 0xFFFF;
    underflow_bits = 0;
}

// Encodes a symbol
static void encode_symbol(SYMBOL* s)
{
    long range;

    // The tree lines below rescale high and low for the new symbol
    range = (long)(high - low) + 1;
    high = low + (unsigned short)
                 ((range * s->high_count) / s->scale - 1);
    low = low + (unsigned short)
                ((range * s->low_count) / s->scale);

    // This loop turns out news bits until high and low are far enough to be
    // stable.
    while (true)
    {
        // If this test pasts, it means most-significant-digits match, and
        // can be sent to the output stream
        if ((high & 0x8000) == (low & 0x8000))
        {
            output_bit(high & 0x8000);
            while (underflow_bits > 0)
            {
                output_bit(~high & 0x8000);
                --underflow_bits;
            }
        } else if ((low & 0x4000) && !(high & 0x4000)) {
            // The numbers are in danger of underflow because the most
            // significant digits do not mast, and because the second digits
            // are just one apart.
            underflow_bits += 1;
            low &= 0x3FFFF;
            high |= 0x4000;
        } else
            return;
        low <<= 1;
        high <<= 1;
        high |= 1;
    }
}

// At the end of encoding, there are still significant bits left in the
// high and low variables, we output two bits, plus as many underflow bits
// as needed.
static void flush_arithmetic_encoder()
{
    output_bit(low & 0x4000);
    ++underflow_bits;
    while (underflow_bits-- > 0)
        output_bit(~low & 0x4000);
}

// Called to figure out which symbol is waiting to be decoded.  Model scale
// is in 's->scale', and returns count that corresponds to the floating
// point code 'code = count / s->scale'
static short get_current_count(SYMBOL* s)
{
    long range;
    short count;

    range = (long)(high - low) + 1;
    count = (short)
            ((((long)(code - low) + 1) * s->scale - 1) / range);

    return count;
}

static void initialize_arithmetic_decoder()
{
    int i;

    code = 0;

    for (i = 0; i < 0x10; ++i)
    {
        code <<= 1;
        code += input_bit();
    }
    low = 0;
    high = 0xFFFF;
}

// After the character has been decoded, this function should be called to
// remove it
static void remove_symbol_from_stream(SYMBOL* s)
{
    long range;

    // First the range is expanded to account for symbol removal
    range = (long(high - low) + 1);
    high = low + (unsigned short)
                 ((range * s->high_count) / s->scale - 1);
    low = low + (unsigned short)
                ((range * s->low_count) / s->scale);

    // Ship out any possible bits
    while (true)
    {
        if ((high & 0x8000) == (low & 0x8000))
        {
        } else if ((low & 0x4000) == 0x4000 && (high & 0x4000) == 0) {
            code ^= 0x4000;
            low &= 0x3FFF;
            high |= 0x4000;
        } else
            return;     // Nothing can be shifted out

        low <<= 1;
        high <<= 1;
        high |= 1;
        code <<= 1;
        code += input_bit();
    }
}

// Probabilities of characters
static struct
{
    char c;
    unsigned short low;
    unsigned short high;
} probabilities[] = { 0, 0, 0 };

// Builds the probability table from the input stream
static void build_probability_table()
{
    register char c;
    register short high = 1, low = 0, i = 0;
    long freq[0x100] = { 0, 0 };       // Frequency table

    // Build the frequency table 'freq' that contains frequencys of chars
    beginning_of_data();
    while (!end_of_data())
    {
        c = read_byte();
        ++freq[c];
    }

    beginning_of_data();

    // Now build it
    for (i = 0; i < 0x100; ++i)
    {
        high += (short)freq[i];
        low += (short)freq[i];
        probabilities[i].high = high;
        probabilities[i].low = low;
    }
}

// Converts a character to a SYMBOL type.
static void convert_int_to_symbol (char c, SYMBOL* s)
{
    register int i = 0;

    while (true)
    {
        if (c == probabilities[i].c)
        {
            s->low_count = probabilities[i].low;
            s->high_count = probabilities[i].high;
            s->scale = (unsigned short)stream_size();
            return;
        }
        ++i;
    }
}

static char convert_symbol_to_int (unsigned int count, SYMBOL* s)
{
    register int i = 0;

    while (true)
    {
        if (count >= probabilities[i].low &&
            count < probabilities[i].high)
        {
            s->low_count = probabilities[i].low;
            s->high_count = probabilities[i].high;
            s->scale = (unsigned short)stream_size();
            return probabilities[i].c;
        }
        ++i;
    }
}

// Compress using arithmetic compression
void EXPORT arithmetic_encode()
{
    register char c;
    SYMBOL s;

    initialize_output_bitstream();
    initialize_arithmetic_encoder();

    build_probability_table();

    while (!end_of_data())
    {
        c = read_byte();
        convert_int_to_symbol (c, &s);
        encode_symbol (&s);
    }
    flush_arithmetic_encoder();
    flush_output_bitstream();
}

void EXPORT arithmetic_decode()
{
    SYMBOL s;
    register char c;
    int count;
    initialize_input_bitstream();
    initialize_arithmetic_decoder();
    while (true)
    {
        s.scale = (unsigned short)stream_size();
        count = get_current_count (&s);
        c = convert_symbol_to_int(count, &s);
        if (end_of_data())
            break;
        remove_symbol_from_stream(&s);
        write_byte(c);
    }
}