lzhuf.cpp

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

        }
    }
}

// Initalization of tree
static void StartHuff ()
{
    int i, j;

    for (i = 0; i < N_CHAR; i++)
    {
        freq[i] = 1;
        son[i] = i + T;
        prnt[i + T] = i;
    }
    i = 0;
    j = N_CHAR;
    while (j <= R)
    {
        freq[j] = freq[i] + freq[i + 1];
        son[j] = i;
        prnt[i] = prnt[i + 1] = j;
        i += 2;
        ++j;
    }
    freq[T] = 0xFFFF;
    prnt[R] = 0;
}

// reconstruction of tree
static void reconst()
{
    int i, j, k;
    unsigned f, l;

    // collect leaf nodes in the first half of the table and replace the
    // freq by (freq + 1) / 2.
    j = 0;
    for (i = 0; i < T; i++)
    {
        if (son[i] >= T)
        {
            freq[j] = (freq[i] + 1) / 2;
            son[j] = son[i];
            ++j;
        }
    }
    // begin constructing tree by connecting sons
    for (i = 0, j = N_CHAR; j < T; i += 2, j++)
    {
        k = i + 1;
        f = freq[j] = freq[i] + freq[k];
        for (k = j - 1; f < freq[k]; k--)
            ;
        ++k;
        l = (j - k) * 2;
        memmove (&freq[k + 1], &freq[k], l);
        freq[k] = f;
        memmove (&son[k + 1], &son[k], l);
        son[k] = i;
    }
    // connect prnt
    for (i = 0; i < T; i++)
    {
        if ((k = son[i]) >= T)
            prnt[k] = i;
        else
            prnt[k] = prnt[k + 1] = i;
    }
}

// increment frequency of given code by one, and update tree
static void update(int c)
{
    int i, j, k, l;

    if (freq[R] == MAX_FREQ)
        reconst();
    c = prnt[c + T];
    do
    {
        k = ++freq[c];

        // if the order is disturbed, exchange nodes
        if (k > (signed)freq[l = c + 1])
        {
            while (k > (signed)freq[++l])
                ;
            --l;
            freq[c] = freq[l];
            freq[l] = k;

            i = son[c];
            prnt[i] = l;
            if (i < T)
                prnt[i + 1] = l;

            j = son[i];
            son[l] = i;

            prnt[j] = c;
            if (j < T)
                prnt[j + 1] = c;
            son[c] = j;

            c = l;
        }
    } while ((c = prnt[c]) != 0);       // repeat up to root
}

static unsigned code, len;

static void EncodeChar (unsigned c)
{
    unsigned i;
    int j, k;

    i = 0;
    j = 0;
    k = prnt[c + T];

    // travel from leaf to root
    do
    {
        i >>= 1;

        // if address of node is odd-numbered, choose larger borther node
        if (k & 1)
            i += 0x8000;

        ++j;
    } while ((k = prnt[k]) != R);
    Putcode(j, i);
    code = i;
    len = j;
    update(c);
}

static void EncodePosition(unsigned c)
{
    unsigned i;

    // output upper 6 bits by table lookup
    i = c >> 6;
    Putcode(p_len[i], (unsigned)p_code[i] << 8);

    // output lower 6 bits verbatim
    Putcode(6, (c & 0x3F) << 10);
}

static void EncodeEnd()
{
    if (putlen)
        write_byte(putbuf >> 8);
    ++codesize;
}

static int DecodeChar()
{
    unsigned c;

    c = son[R];

    // Travel from root to leaf, choosing the smaller child node (son[]) if
    // the read bit is 0, the bigger (son[] + 1) if 1
    while (c < T)
    {
        c += GetBit();
        c = son[c];
    }
    c -= T;
    update(c);
    return c;
}

static int DecodePosition()
{
    unsigned i, j, c;

    // recover upper 6 bits from table
    i = GetByte();
    c = (unsigned)d_code[i] << 6;
    j = d_len[i];

    // read lower 6 bits verbatim
    j -= 2;
    while (j--)
    {
        i = (i << 1) + GetBit();
    }
    return c | (i & 0x3F);
}

// ********** LZHUF Compression ******

// Compresses using LZHUF method
void EXPORT lzhuf_encode ()
{
    int i, c, len, r, s, last_match_length;

    textsize = stream_size();
    // Output size of text
    i = textsize & 0x000000FF; write_byte(i);
    i = textsize & 0x0000FF00; write_byte(i);
    i = textsize & 0x00FF0000; write_byte(i);
    i = textsize & 0xFF000000; write_byte(i);
    if (!textsize)
        return;


    beginning_of_data();
    textsize = 0;
    StartHuff();
    InitTree();
    s = 0;
    r = N - F;
    for (i = s; i < r; i++)
        text_buf[i] = ' ';
    for (len = 0; len < F && !end_of_data(); len++)
        text_buf[r + len] = c = read_byte();
    textsize = len;
    for (i = 1; i <= F; i++)
        InsertNode(r - i);
    InsertNode(r);
    do
    {
        if (match_length > len)
            match_length = len;
        if (match_length <= THRESHOLD)
        {
            match_length = 1;
            EncodeChar(text_buf[r]);
        } else {
            EncodeChar(255 - THRESHOLD + match_length);
            EncodePosition(match_position);
        }
        last_match_length = match_length;
        for (i = 0; i < last_match_length && !end_of_data(); i++)
        {
            DeleteNode(s);
            text_buf[s] = c = read_byte();
            if (s < F - 1)
                text_buf[s + N] = c;
            s = (s + 1) & (N - 1);
            r = (r + 1) & (N - 1);
            InsertNode(r);
        }
        while (i++ < last_match_length)
        {
            DeleteNode(s);
            s = (s + 1) & (N - 1);
            r = (r + 1) & (N - 1);
            if (--len)
                InsertNode(r);
        }
    } while (len > 0);
    EncodeEnd();
}

// Decompress a LZHUF compressed file
void EXPORT lzhuf_decode()
{
    int i, j, k, r, c;
    unsigned long count;

    c = read_byte(); *(&textsize + 0) = c;
    c = read_byte(); *(&textsize + 1) = c;
    c = read_byte(); *(&textsize + 2) = c;
    c = read_byte(); *(&textsize + 3) = c;

    if (!textsize)
        return;

    StartHuff();
    for (i = 0; i < N - F; i++)
        text_buf[i] = ' ';
    r = N - F;
    for (count = 0; count < textsize; )
    {
        c = DecodeChar();
        if (c < 256)
        {
            write_byte(c);
            text_buf[r++] = c;
            r &= (N - 1);
            ++count;
        } else {
            i = (r - DecodePosition() - 1) & (N - 1);
            j = c - 255 + THRESHOLD;
            for (k = 0; k < j; k++)
            {
                c = text_buf[(i + k) & (N - 1)];
                write_byte(c);
                text_buf[r++] = c;
                r &= (N - 1);
                ++count;
            }
        }
    }
}