#include <windows.h>

#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define INCLUDE_HUFFSTUFF
#include <ttwcomp.h>

void HuffMemFill(FPVOID, USHORT, USHORT);

/* initialization of tree */

PHUFFSTUFF StartHuff(void)
{
    SHORT i, j;
         PHUFFSTUFF mypHS;
         HANDLE  hHS;

         hHS = GlobalAlloc(GMEM_MOVEABLE, sizeof(struct _HuffStuff));
         mypHS = (PHUFFSTUFF)GlobalLock(hHS);
    if (mypHS == NULL)
             return(NULL);

         _fmemset(mypHS, 0x00, sizeof(struct _HuffStuff));
    mypHS->textsize = mypHS->codesize = 0;
    mypHS->match_position = mypHS->match_length = 0;
    mypHS->getbuf = mypHS->putbuf = mypHS->code = mypHS->len = 0;
    mypHS->getlen = mypHS->putlen = 0;

    for (i = 0; i < N_CHAR; i++) {
        mypHS->freq[i] = 1;
        mypHS->son[i] = i + T;
        mypHS->prnt[i + T] = i;
    }
    i = 0; j = N_CHAR;
    while (j <= R) {
        mypHS->freq[j] = mypHS->freq[i] + mypHS->freq[i + 1];
        mypHS->son[j] = i;
        mypHS->prnt[i] = mypHS->prnt[i + 1] = j;
        i += 2; j++;
    }
    mypHS->freq[T] = 0xffff;
    mypHS->prnt[R] = 0;
         return(mypHS);
}

void EndHuff(PHUFFSTUFF pHS)
{
HANDLE  hHS;
         hHS = LOWORD(GlobalHandle(HIWORD((DWORD)(pHS))));
    while (GlobalFlags(hHS) & GMEM_LOCKCOUNT)
         GlobalUnlock(hHS);
    GlobalFree(hHS);
}

/* reconstruction of tree */

void ReConstructTree(PHUFFSTUFF pHS)
{
    SHORT i, j, k;
    USHORT 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 (pHS->son[i] >= T) {
            pHS->freq[j] = (pHS->freq[i] + 1) / 2;
            pHS->son[j] = pHS->son[i];
            j++;
        }
    }
    /* begin constructing tree by connecting sons */
    for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
        k = i + 1;
        f = pHS->freq[j] = pHS->freq[i] + pHS->freq[k];
        for (k = j - 1; f < pHS->freq[k]; k--);
        k++;
        l = (j - k) * 2;
        _fmemmove(&pHS->freq[k + 1], &pHS->freq[k], l);
        pHS->freq[k] = f;
        _fmemmove(&pHS->son[k + 1], &pHS->son[k], l);
        pHS->son[k] = i;
    }
    /* connect prnt */
    for (i = 0; i < T; i++) {
        if ((k = pHS->son[i]) >= T) {
            pHS->prnt[k] = i;
        } else {
            pHS->prnt[k] = pHS->prnt[k + 1] = i;
        }
    }
}


/* increment frequency of given code by one, and update tree */
void UpdateTree(PHUFFSTUFF pHS, SHORT c)
{
    SHORT i, j, l;
    USHORT k;

    if (pHS->freq[R] == MAX_FREQ) {
        ReConstructTree(pHS);
    }
    c = pHS->prnt[c + T];
    do {
        k = ++pHS->freq[c];

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

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

            j = pHS->son[l];
            pHS->son[l] = i;

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

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

void InitTree(PHUFFSTUFF pHS)  /* initialize trees */
{
    SHORT  i;

    for (i = N + 1; i <= N + 256; i++)
        pHS->rson[i] = NIL;        /* root */
    for (i = 0; i < N; i++)
        pHS->dad[i] = NIL;         /* node */

}

void InsertNode(PHUFFSTUFF pHS, SHORT r)  /* insert to tree */
{
    SHORT  i, p, cmp;
    FPCHAR  key;
    USHORT c;

    cmp = 1;
    key = &pHS->text_buf[r];
    p = N + 1 + key[0];
    pHS->rson[r] = pHS->lson[r] = NIL;
    pHS->match_length = 0;
    for ( ; ; ) {
        if (cmp >= 0) {
            if (pHS->rson[p] != NIL)
                p = pHS->rson[p];
            else {
                pHS->rson[p] = r;
                pHS->dad[r] = p;
                return;
            }
        } else {
            if (pHS->lson[p] != NIL)
                p = pHS->lson[p];
            else {
                pHS->lson[p] = r;
                pHS->dad[r] = p;
                return;
            }
        }
        for (i = 1; i < F; i++)
            if ((cmp = key[i] - pHS->text_buf[p + i]) != 0)
                break;
        if (i > THRESHOLD) {
            if (i > pHS->match_length) {
                pHS->match_position = ((r - p) & (N - 1)) - 1;
                if ((pHS->match_length = i) >= F)
                    break;
            }
            if (i == pHS->match_length) {
                if ((c = ((r - p) & (N - 1)) - 1) < (USHORT)pHS->match_position) {
                    pHS->match_position = c;
                }
            }
        }
    }
    pHS->dad[r] = pHS->dad[p];
    pHS->lson[r] = pHS->lson[p];
    pHS->rson[r] = pHS->rson[p];
    pHS->dad[pHS->lson[p]] = r;
    pHS->dad[pHS->rson[p]] = r;
    if (pHS->rson[pHS->dad[p]] == p)
        pHS->rson[pHS->dad[p]] = r;
    else
        pHS->lson[pHS->dad[p]] = r;
    pHS->dad[p] = NIL; /* remove p */
}

#pragma optimize("e",off)          /* Get around regMD, line 3837 bug */
                                                                         /* in both C600 and C600AX         */
void DeleteNode(PHUFFSTUFF pHS, SHORT p)  /* remove from tree */
{
    SHORT  q;

    if (pHS->dad[p] == NIL)
        return;         /* not registered */
    if (pHS->rson[p] == NIL)
        q = pHS->lson[p];
    else
    if (pHS->lson[p] == NIL)
        q = pHS->rson[p];
    else {
        q = pHS->lson[p];
        if (pHS->rson[q] != NIL) {
            do {
                q = pHS->rson[q];
            } while (pHS->rson[q] != NIL);
            pHS->rson[pHS->dad[q]] = pHS->lson[q];
            pHS->dad[pHS->lson[q]] = pHS->dad[q];
            pHS->lson[q] = pHS->lson[p];
            pHS->dad[pHS->lson[p]] = q;
        }
        pHS->rson[q] = pHS->rson[p];
        pHS->dad[pHS->rson[p]] = q;
    }
    pHS->dad[q] = pHS->dad[p];
    if (pHS->rson[pHS->dad[p]] == p)
        pHS->rson[pHS->dad[p]] = q;
    else
        pHS->lson[pHS->dad[p]] = q;
    pHS->dad[p] = NIL;
}


