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

#define INCLUDE_HUFFSTUFF 
#include <huffman.h>

UCHAR p_len[64] = {
    0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
    0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
    0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
    0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
    0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
    0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
    0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
    0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
};
UCHAR p_code[64] = {
    0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
    0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
    0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
    0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
    0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
    0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
    0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
    0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
};


/* compression */

SHORT Compress(struct _HuffStuff * pHS)  /* compression */
{
    SHORT  i, c, len, r, s, last_match_length;

    pHS->textsize = 0;           /* rewind and re-read */
    InitTree(pHS);
    s = 0;
    r = N - F;
    for (i = s; i < r; i++)
        pHS->text_buf[i] = 0x20;
    for (len = 0; len < F && (c = pHS->fGetNextChar(pHS)) != EOF; len++)
        pHS->text_buf[r + len] = c;
    pHS->textsize = len;
    for (i = 1; i <= F; i++)
        InsertNode(pHS, r - i);
    InsertNode(pHS, r);
    do {
        if (pHS->match_length > len)
            pHS->match_length = len;
        if (pHS->match_length <= THRESHOLD) {
            pHS->match_length = 1;
            if (CompressChar(pHS, pHS->text_buf[r]))
	             return(HUFFMAN_FILE_WRITE_ERROR);

        } else {
            if (CompressChar(pHS, 255 - THRESHOLD + pHS->match_length))
	             return(HUFFMAN_FILE_WRITE_ERROR);
            if (CompressPosition(pHS, pHS->match_position))
	             return(HUFFMAN_FILE_WRITE_ERROR);

        }
        last_match_length = pHS->match_length;
        for (i = 0; i < last_match_length &&
                (c = pHS->fGetNextChar(pHS)) != EOF; i++) {
            DeleteNode(pHS, s);
            pHS->text_buf[s] = c;
            if (s < F - 1)
                pHS->text_buf[s + N] = c;
            s = (s + 1) & (N - 1);
            r = (r + 1) & (N - 1);
            InsertNode(pHS, r);
        }
        pHS->textsize += i;
        while (i++ < last_match_length) {
            DeleteNode(pHS, s);
            s = (s + 1) & (N - 1);
            r = (r + 1) & (N - 1);
            if (--len) InsertNode(pHS, r);
        }
    } while (len > 0);
    if (CompressEnd(pHS))
	     return(HUFFMAN_FILE_WRITE_ERROR);
	 EndHuff(pHS);
	 return(HUFFMAN_NO_ERROR);
}

SHORT CompressChar(struct _HuffStuff * pHS, USHORT c)
{
    USHORT i;
    SHORT j, k;

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

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

        /* if node's address is odd-numbered, choose bigger brother node */
        if (k & 1) i += 0x8000;

        j++;
    } while ((k = pHS->prnt[k]) != R);
    if (PutCode(pHS, j, i))
	     return(HUFFMAN_FILE_WRITE_ERROR);
    pHS->code = i;
    pHS->len = j;
    UpdateTree(pHS, c);
	 return(HUFFMAN_NO_ERROR);
}

SHORT CompressPosition(struct _HuffStuff * pHS, USHORT c)
{
    USHORT i;

    /* output upper 6 bits by table lookup */
    i = c >> 6;
    if (PutCode(pHS, p_len[i], (unsigned)p_code[i] << 8))
	     return(HUFFMAN_FILE_WRITE_ERROR);
    /* output lower 6 bits verbatim */
    if (PutCode(pHS, 6, (c & 0x3f) << 10))
	     return(HUFFMAN_FILE_WRITE_ERROR);
	 return(HUFFMAN_NO_ERROR);
}

SHORT CompressEnd(struct _HuffStuff * pHS)
{
    if (pHS->putlen) {
        if (pHS->fPutNextChar(pHS, pHS->putbuf >> 8) == EOF) {
	         return(HUFFMAN_FILE_WRITE_ERROR);
        }
        pHS->codesize++;
    }
	 return(HUFFMAN_NO_ERROR);
}



SHORT GetBit(struct _HuffStuff * pHS)    /* get one bit */
{
    USHORT i;

    while (pHS->getlen <= 8) {
        if ((SHORT)(i = pHS->fGetNextChar(pHS)) < 0) i = 0;
        pHS->getbuf |= i << (8 - pHS->getlen);
        pHS->getlen += 8;
    }
    i = pHS->getbuf;
    pHS->getbuf <<= 1;
    pHS->getlen--;
    return (int)((i & 0x8000) >> 15);
}

SHORT GetByte(struct _HuffStuff * pHS)   /* get one byte */
{
    USHORT i;

    while (pHS->getlen <= 8) {
        if ((SHORT)(i = pHS->fGetNextChar(pHS)) < 0) i = 0;
        pHS->getbuf |= i << (8 - pHS->getlen);
        pHS->getlen += 8;
    }
    i = pHS->getbuf;
    pHS->getbuf <<= 8;
    pHS->getlen -= 8;
    return (SHORT)((i & 0xff00) >> 8);
}


