splay.cpp

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

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

// Splay compression

// ORIGSRC\SPLAY.C (original source) says:
/* File: splay.c
   Author: Jeffrey Chilton, PO Box 807, West Branch, IA 52358.
   Author: Douglas Jones, Dept. of Comp. Sci., U. of Iowa, Iowa City, IA 52242.
   Date: Oct. 6, 1994
	 (revision of Feb 14, 1990 to delete cryptographic options).
	 (minor revision of Feb. 20, 1989 to add exit(0) at end of program).
	 (minor revision of Nov. 14, 1988 to fix portability problems).
	 (minor revision of Aug. 8, 1988 to eliminate unused vars, fix -c).
   Copyright 1988 by Jeffrey Chilton and Douglas Jones.
	      Copies of this program and associated files may not be sold,
			nor may it (or parts of it) be incorporated into
			products which will be sold, without the express
			prior permission of the authors.
	      Permission is hereby granted to make copies of this program for
			research and personal use so long as this copyright
			notice is included in the copy and in any derived work.
   Language: C (UNIX)
   Purpose: Data compression program
   Algorithm: Uses a splay-tree based prefix code, with one splay tree per
			state in a Markov model.  The nature of the Markov
			model is determined by the splay procedure in the
			include file splay.i.
*/

#pragma warning(disable:4244)

// Also ORIGSRC\UNSPLAY.C was used:
/* File: unsplay.c
   Author: Jeffrey Chilton, PO Box 807, West Branch, IA 52358.
   Author: Douglas Jones, Dept. of Comp. Sci., U. of Iowa, Iowa City, IA 52242.
   Date: Oct. 6, 1994
	 (revision of Feb 14, 1990 to delete cryptographic options).
	 (minor revision of Feb. 20, 1989 to add exit(0) at end of program).
	 (minor revision of Nov. 14, 1988 to detect corrupt input better).
	 (minor revision of Aug. 8, 1988 to eliminate unused vars, fix -c).
   Copyright 1988 by Jeffrey Chilton and Douglas Jones.
	      Copies of this program and associated files may not be sold,
			nor may it (or parts of it) be incorporated into
			products which will be sold, without the express
			prior permission of the authors.
	      Permission is hereby granted to make copies of this program for
			research and personal use so long as this copyright
			notice is included in the copy and in any derived work.
   Language: C (UNIX)
   Purpose: Data uncompression program
   Algorithm: Uses a splay-tree based prefix code, with one splay tree per
			state in a Markov model.  The nature of the Markov
			model is determined by the splay procedure in the
			include file splay.i.
*/


#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>

#define EXPORTING
#include "comprlib.h"

#undef MAXCHAR
#define MAXCHAR    0x100
#define SUCCMAX    0x101
#define SUCCTWICE    514
#define TWICEMAX     513
#define ROOT           1
#define nokeydefault  32
#define keydefault     1

static short* left;
static short* right;
static short* up;



#define SPLAY(plain)                                \
        {                                           \
            register short* l;                      \
            register short* r;                      \
            register short* u;                      \
            register short a, b, c, d;              \
            l = &left[state * SUCCMAX];             \
            r = &right[state * SUCCMAX];            \
            u = &up[state * SUCCTWICE];             \
            a = (plain) + SUCCMAX;                  \
            do                                      \
            {                                       \
                if ((c = u[a]) != ROOT)             \
                {                                   \
                    d = u[c];                       \
                    b = l[d];                       \
                    if (c == b)                     \
                    {                               \
                        b = r[d];                   \
                        r[d] = a;                   \
                    } else {                        \
                        l[d] = a;                   \
                    }                               \
                    if (l[c] == a)                  \
                        l[c] = b;                   \
                    else                            \
                        r[c] = b;                   \
                    u[a] = d;                       \
                    u[b] = c;                       \
                    a = d;                          \
                } else {                            \
                    a = c;                          \
                }                                   \
            } while (a != ROOT);                    \
            state = (plain) % states;               \
        }

// Number of states, 0 means unknown
static int states = 0;
// Current splay tree, initally 0
static state = 0;

// Build initial splay tree
static void initsplay()
{
    short int* l;
    short int* r;
    short int* u;
    left = (short*)malloc(states * SUCCMAX * sizeof(short));
    right = (short*)malloc(states * SUCCMAX * sizeof(short));
    up = (short*)malloc(states * SUCCTWICE * sizeof(short));
    for (state = 0; state < states; ++state)
    {
        short int i, j;
        l = &left[state * SUCCMAX];
        r = &right[state * SUCCMAX];
        u = &up[state * SUCCTWICE];
        for (i = 2; i <= TWICEMAX; ++i)
        {
            // Shifting is faster
            u[i] = i >> 1;            // i / 2
        }
        for (j = 1; j <= MAXCHAR; ++j)
        {
            l[j] = j << 2;          // 2 * j
            r[j] = j << 2 + 1;      // 2 * j + 1;
        }
    }
    state = 0;
}          






#define MAXBITCOUNTER    8
static short bitbuffer = 0;
static short bitcounter = 0;

#define TRANSMIT(b)                                 \
        {                                           \
            bitbuffer = (bitbuffer << 1) + b;       \
            if ((++bitcounter) == MAXBITCOUNTER)    \
            {                                       \
                write_byte(bitbuffer);              \
                bitcounter = bitbuffer = 0;         \
            }                                       \
        }

static short int stack[SUCCMAX];

#define COMPRESS(plain)                             \
        {                                           \
            short int* u;                           \
            short int* r;                           \
            short int sp = 0;                       \
            short int a = (plain) + SUCCMAX;        \
            r = &right[state * SUCCMAX];            \
            u = &up[state * SUCCTWICE];             \
            do                                      \
            {                                       \
                stack[sp] = r[u[a]] == a;           \
                ++sp;                               \
                a = u[a];                           \
            } while (a != ROOT);                    \
            do                                      \
            {                                       \
                TRANSMIT(stack[(--sp)]);            \
            } while (sp);                           \
            SPLAY((short)(plain));                  \
        }

// Compression function just uses COMPRESS macro
static void compress(short plain)
{
    COMPRESS(plain);
}

// Compress with 'splay' method
void EXPORT splay_encode()
{
    int plain;

    initsplay();

    if (states == 0x100)
        write_byte(NULL);
    else
        write_byte((char)states);

    // Begin compression
    while (true)
    {
        plain = read_byte();
        if (end_of_data())
            break;
        COMPRESS ((unsigned short)(plain & 0xFF));
    }
    compress (MAXCHAR);

    // Begin flushtransmit
    while (bitcounter)
    {
        TRANSMIT((unsigned short)0)
    }
}

#define TOPBITINBUFFER  0x80

#define RECEIVE(bit)                                                      \
        {                                                                 \
            short ch;                                                     \
            if (!bitcounter)                                              \
            {                                                             \
                ch = read_byte();                                         \
                if (end_of_data())                                        \
                    EXCEPTION(ERR_NOTCOMPR, "Not splay compressed: "      \
                                            "unexpected end of file",     \
                                            "RECEIVE() macro");           \
                bitbuffer = ch;                                           \
                bitcounter = MAXBITCOUNTER;                               \
            }                                                             \
            --bitcounter;                                                 \
            if ((bitbuffer & TOPBITINBUFFER))                             \
                bit = 1;                                                  \
            else                                                          \
                bit = 0;                                                  \
            bitbuffer = bitbuffer << 1;                                   \
        }

// Character that was just compressed
static short plain;

#define UNCOMPRESS()                                 \
        {                                            \
            short int* r;                            \
            short int* l;                            \
            short int bit, a = ROOT;                 \
            l = &left[state * SUCCMAX];              \
            r = &right[state * SUCCMAX];             \
                                                     \
            do                                       \
            {                                        \
                RECEIVE(bit);                        \
                if (!bit)                            \
                    a = l[a];                        \
                else                                 \
                    a = r[a];                        \
            } while (a <= MAXCHAR);                  \
            plain = a - SUCCMAX;                     \
            SPLAY(plain);                            \
        }


// Uncompress function
static void uncompress()
{
    UNCOMPRESS();
}

// Splay decompression
void EXPORT splay_decode()
{
    // Begin uncompression
    while (true)
    {
        UNCOMPRESS();
        if (plain != MAXCHAR)
            write_byte(plain);
        else
            break;
    }

    // Is it really end-of-file?
    if (!end_of_data())
        EXCEPTION(ERR_NOTCOMPR, "End-of-file code found before actual EOF",
                                "splay_decode()");
}


#pragma warning(default:4244)