dmc.cpp

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

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

// Dynamic Markov Compression (DMC)

// Original code (ORIGSRC\DMC.C) comment states:
/*   Dynamic Markov Compression (DMC)    Version 0.0.0
 
 
     Copyright 1993, 1987
 
     Gordon V. Cormack
     University of Waterloo
     [e-mail]
 
 
     All rights reserved.
 
     This code and the algorithms herein are the property of Gordon V. Cormack.
 
     Neither the code nor any algorithm herein may be included in any software,
     device, or process which is sold, exchanged for profit, or for which a
     licence or royalty fee is charged.
 
     Permission is granted to use this code for educational, research, or
     commercial purposes, provided this notice is included, and provided this
     code is not used as described in the above paragraph.
 
*/


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

void dmc_encode();
void dmc_decode();
static void pinit(int memsize);
static void pflush();
static void preset();
static float predict();
static void pupdate(int b);

static int memsize = 0x1000000;

void EXPORT dmc_encode()
{
    int max = 0x1000000, min = 0, mid = 0, c, i, inbytes = 0, outbytes = 3;
    int pout = 3, bit;

    pinit(memsize);

    while (true)
    {
        c = read_byte();
        if (end_of_data())
        {
            min = max - 1;
            break;
        }
        for (i = 0; i < 8; i++)
        {
            bit = (c << i) & 0x80;
            min = min + (max - min - 1) * (int)predict();
            pupdate(bit);
            if (mid == min)
                ++mid;
            if (mid == (max - 1))
                --mid;

            if (bit)
                min = mid;
            else
                max = mid;

            while ((max - min) < 0x100)
            {
                if (bit)
                    --max;
                write_byte(min >> 0x10);
                ++outbytes;
                min = (min << 8) & 0xFFFF00;
                max = ((max << 8) & 0xFFFF00);
                if (min >= max)
                    max = 0x1000000;
            }
        }

        if (!(++inbytes) & 0xFF)
        {
            if (!(inbytes & 0xFFFF))
            {
            }
            if (outbytes - pout > 0x100)        // Compression failing
                pflush();

            pout = outbytes;
        }
    }
    write_byte(min >> 0x10);
    write_byte((min >> 8) & 0xFF);
    write_byte(min & 0x00FF);
}

void EXPORT dmc_decode()
{
    int max = 0x1000000, min = 0, mid, val, i, inbytes = 3, pin = 3;
    int outbytes = 0, bit, c;

    pinit(memsize);

    val = read_byte() << 0xF;
    val += read_byte() << 8;
    val += read_byte();

    while (true)
    {
        c = 0;
        if (val == (max - 1))
        {
            // Decompression done
            break;
        }
        for (i = 0; i < 8; i++)
        {
            mid = min + (max - min - 1) * (int)predict();
            if (mid == min)
                ++mid;
            if (mid == (max - 1))
                --mid;
            if (val >= mid)
            {
                bit = 1;
                min = mid;
            } else {
                bit = 0;
                max = mid;
            }
            pupdate(bit);
            c = c + c + bit;
            while ((max - min) < 0x100)
            {
                if (bit)
                    --max;
                ++inbytes;
                val = (val << 8) & 0xFFFF00 | (read_byte() & 0xFF);
                min = (min << 8) & 0xFFFF00;
                max = ((max << 8) & 0xFFFF00);
                if (min >= max)
                    max = 0x1000000;
            }
        }
        write_byte(c);
        if (!(++outbytes & 0xFF))
        {
            if (inbytes - pin > 0x100)      // Compression was failing
                pflush();
        }
        pin = inbytes;
    }
}

typedef struct nnn
{
    float count[2];
    struct nnn* next[2];
} node;

static int threshold = 2, bigthresh = 2;

static node* p, *pnew, nodes[0x100][0x100];

static node* nodebuf;
static node* nodemaxp;
static node* nodesptr;

#include <malloc.h>

// Initalize
static void pinit(int memsize)
{
    nodebuf = (node*)malloc (memsize);
    if (nodebuf == (node*)NULL)
    {
        EXCEPTION(ERR_MEMORY, "Memory allocation for predictor memory failed",
                              "pinit()");
    }
    nodemaxp = nodebuf + (memsize / sizeof(node)) - 20;
    pflush();
}

// Flush buffer
static void pflush()
{
    register int i, j;
    for (j = 0; j < 0x100; j++)
    {
        for (i = 0; i < 0x7F; i++)
        {
            nodes[j][i].count[0] = (float)0.2;
            nodes[j][i].count[1] = (float)0.2;
            nodes[j][i].next[0] = &nodes[j][2 * i + 1];
            nodes[j][i].next[1] = &nodes[j][2 * i + 2];
        }
        for (i = 0x7F; i < 0xFF; i++)
        {
            nodes[j][i].count[0] = (float)0.2;
            nodes[j][i].count[1] = (float)0.2;
            nodes[j][i].next[0] = &nodes[i + 1][0];
            nodes[j][i].next[1] = &nodes[i - 0x7F][0];
        }
    }
    nodesptr = nodebuf;
    preset();
}

static void preset()
{
    p = &nodes[0][0];
}

static float predict()
{
    return p->count[0] / (p->count[0] + p->count[1]);
}

// Update
static void pupdate(int b)
{
    float r;
    if (p->count[b] >= threshold
        && p->next[b]->count[0] + p->next[b]->count[1] >=
        bigthresh + p->count[b])
    {
        pnew = nodesptr++;
        p->next[b]->count[0] -= pnew->count[0] =
            p->next[b]->count[0] *
            (r = p->count[b] / (p->next[b]->count[1] + p->
            next[b]->count[0]));
        p->next[b]->count[1] -= pnew->count[1] =
            p->next[b]->count[1] * r;
        pnew->next[0] = p->next[b]->next[0];
        pnew->next[1] = p->next[b]->next[1];
        p->next[b] = pnew;
    }
    p->count[b]++;
    p = p->next[b];
    if (nodesptr > nodemaxp)
    {
        // Flush needed
        pflush();
    }
}