#include <stdafx.h>
#include "lzss.h"
#ifndef _AFX
#include "debug_new.h"
#endif
#include "memstream.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#endif

static u32 textsize = 0,    /* text size counter */
    codesize = 0;   /* code size counter */
static int  match_position, match_length,  /* of longest match.  These are
            set by the InsertNode() procedure. */
    lson[N + 1], rson[N + 257], dad[N + 1];  /* left & right children &
            parents -- These constitute binary search trees. */

static void InitTree(void)
{
    int  i;

    for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;
    for (i = 0; i < N; i++) dad[i] = NIL;
}

static void InsertNode(int r, u8 *text_buf)
{
    int  i, p, cmp;
    unsigned char  *key;

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

void DeleteNode(int p)
{
    int  q;

    if (dad[p] == NIL) return;  /* not in tree */
    if (rson[p] == NIL) q = lson[p];
    else if (lson[p] == NIL) q = rson[p];
    else
    {
        q = lson[p];
        if (rson[q] != NIL)
        {
            do {  q = rson[q];  } while (rson[q] != NIL);
            rson[dad[q]] = lson[q];  dad[lson[q]] = dad[q];
            lson[q] = lson[p];  dad[lson[p]] = q;
        }
        rson[q] = rson[p];  dad[rson[p]] = q;
    }
    dad[q] = dad[p];
    if (rson[dad[p]] == p) rson[dad[p]] = q;  else lson[dad[p]] = q;
    dad[p] = NIL;
}

int LzssEncode(u8* &dest, u8* src, int src_size)
{
    int dest_seek=4, src_seek=0;
    int  i, c, len, r, s, last_match_length, code_buf_ptr;
    u8 code_buf[17], mask;
    static u8   text_buf[N + F - 1];    /* ring buffer of size N,
            with extra F-1 bytes to facilitate string comparison */

    dest=new u8[src_size*2];
    InitTree();
    code_buf[0]=0;
    code_buf_ptr=mask=1;
    s=0;
    r=N-F;
    // clear the buffer with any character that will appear often
    memset(&text_buf[s],0,r);
    // read F bytes into the last F bytes of the buffer
    for(len=0; len<F && len<src_size; len++) text_buf[r+len]=src[src_seek++];
    // text of size zero
    if((textsize=len)==0) return 0;
    for(i=1; i<=F; i++) InsertNode(r-i,text_buf);
    InsertNode(r,text_buf);

    for(; len>0; )
    {
        if(match_length>len) match_length=len;

        if(match_length<=THRESHOLD)
        {
            match_length=1;  /* Not long enough match.  Send one byte. */
            code_buf[0]|=mask;  /* 'send one byte' flag */
            code_buf[code_buf_ptr++]=text_buf[r];  /* Send uncoded. */
        }
        else
        {
            code_buf[code_buf_ptr++]=match_position;
            code_buf[code_buf_ptr++]=((match_position >> 4) & 0xf0)|(match_length-(THRESHOLD+1));
        }
        // shift mask left one bit
        if((mask<<=1)==0)
        {
            for(i=0; i<code_buf_ptr; i++) dest[dest_seek++]=code_buf[i];
            codesize+=code_buf_ptr;
            code_buf[0]=0;
            code_buf_ptr=mask=1;
        }
        last_match_length=match_length;
        for(i=0; i<last_match_length; i++)
        {
            if(src_seek>=src_size) break;
            c=src[src_seek++];
            DeleteNode(s);      // delete old strings
            text_buf[s]=c;      // read new bytes
            if(s<F-1) text_buf[s+N]=c;
            s=(s+1)%N;
            r=(r+1)%N;
            InsertNode(r,text_buf);
        }
        while(i++<last_match_length)
        {
            DeleteNode(s);                  // no need to read, but
            s=(s+1)%N;
            r=(r+1)%N;
            if(--len) InsertNode(r,text_buf);       // buffer may not be empty
        }
    }

    // Send remaining code. */
    if(code_buf_ptr>1)
    {
        for(i=0; i<code_buf_ptr; i++) dest[dest_seek++]=code_buf[i];
        codesize+=code_buf_ptr;
    }

    *((u32*)&dest[0])=dest_seek-4;
    return dest_seek;
}

int LzssDecode(u8* &dest, u8* src, int src_size)
{
    int r, fpos;
    int dest_seek, src_seek;
    u8 flags, c;
    static u8   text_buf[N + F - 1];    /* ring buffer of size N,
            with extra F-1 bytes to facilitate string comparison */

    //dest=new u8[src_size*10];
    MEM_STREAM str;
    MemStreamCreate(&str);
    ZeroMemory(text_buf,N-F);

    for(fpos=0, r=N-F, flags=0, dest_seek=0, src_seek=4; src_seek-4<src_size; flags>>=1, fpos++)
    {
        // read flag
        if((fpos%=8)==0) flags=src[src_seek++];

        if(flags&1)
        {
            c=src[src_seek++];
            //dest[dest_seek++]=c;
            MemStreamWriteByte(&str,c);
            text_buf[r++]=c;
            r%=N;
        }
        else
        {
            int i=src[src_seek++];
            int j=src[src_seek++];

            i|=((j&0xf0)<<4);
            j=(j&0x0f)+THRESHOLD;
            // decompress string
            for(int k=0; k<=j; k++)
            {
                c=text_buf[(i+k)%N];
                //dest[dest_seek++]=c;
                MemStreamWriteByte(&str,c);
                text_buf[r++]=c;
                r%=N;
            }
        }
    }
    //return dest_seek;

    dest=str.data;
    return str.pos;
}