// (c) 1995-2007 Electronic Arts Inc.

#ifndef __BTRWRITE
#define __BTRWRITE 1

#include <string.h>
#include "codex.h"
#include "btreecodex.h"

/****************************************************************/
/*  Internal Functions                                          */
/****************************************************************/

#define BTREEWORD    short
#define BTREECODES   256
#define BTREEBIGNUM  32000
#define BTREESLOPAGE 16384

struct BTREEMemStruct
{
    char    *ptr;
    int len;
};

struct BTreeEncodeContext
{
    unsigned int    packbits;
    unsigned int    workpattern;
    unsigned char  *bufptr;
    unsigned int    ulen;
    unsigned int    masks[17];
    unsigned char   clueq[BTREECODES];
    unsigned char   right[BTREECODES];
    unsigned char   join[BTREECODES];
    unsigned int    plen;
    unsigned char  *bufbase;
    unsigned char  *bufend;
    unsigned char  *buffer;
    unsigned char  *buf1;
    unsigned char  *buf2;
};

static void BTREE_writebits(struct BTreeEncodeContext *EC,
                            struct BTREEMemStruct *dest,
                            unsigned int bitpattern,
                            unsigned int len)
{
    if (len > 16)
    {
        BTREE_writebits(EC,dest,(unsigned int) (bitpattern>>16), len-16);
        BTREE_writebits(EC,dest,(unsigned int) bitpattern, 16);
    }
    else
    {
        EC->packbits += len;
        EC->workpattern += (bitpattern & EC->masks[len]) << (24-EC->packbits);
        while (EC->packbits > 7)
        {
            *(dest->ptr+dest->len) = (unsigned char) (EC->workpattern >> 16);
            ++dest->len;

            EC->workpattern = EC->workpattern << 8;
            EC->packbits -= 8;
            ++EC->plen;
        }
    }
}


static void BTREE_adjcount(unsigned char *s, unsigned char *bend, BTREEWORD *count)
{

#ifdef __WATCOMC__

    union
    {
        unsigned char           b[4];
        int                     w;
    } i;

    #define COUNTADJ(j) i.b[1] = i.b[0]; i.b[0] = *(s+j); ++count[i.w];

    i.w = 0;
    i.b[0] = (unsigned BTREEWORD) *s++;

#else

    unsigned BTREEWORD      i;

    #define COUNTADJ(j) i = (BTREEWORD)(((i<<8) | *(s+j))); ++*(count+(int)i);

    i = (unsigned BTREEWORD) *s++;

#endif

    bend -= 16;

    if (s<bend)
    {
        do
        {
            COUNTADJ(0);
            COUNTADJ(1);
            COUNTADJ(2);
            COUNTADJ(3);

            COUNTADJ(4);
            COUNTADJ(5);
            COUNTADJ(6);
            COUNTADJ(7);

            COUNTADJ(8);
            COUNTADJ(9);
            COUNTADJ(10);
            COUNTADJ(11);

            COUNTADJ(12);
            COUNTADJ(13);
            COUNTADJ(14);
            COUNTADJ(15);
            s += 16;

        } while (s<bend);
    }

    bend += 16;

    if (s<bend)
    {
        do
        {
            COUNTADJ(0);
            ++s;

        } while (s<bend);
    }
}

/* Clear 128 ints (256 words). Done as ints for speed. */

static void BTREE_clearcount(unsigned char *tryq,BTREEWORD *countbuf)
{
    int     zero=0;
    int                 i;
    int                 j;
    int             *intptr;

    intptr = (int *) countbuf;
    j = 256;
    do
    {
        if (*tryq)
        {
            *tryq++ = 1;

            i = 8;
            do
            {
                *(intptr+0) = zero;
                *(intptr+1) = zero;
                *(intptr+2) = zero;
                *(intptr+3) = zero;

                *(intptr+4) = zero;
                *(intptr+5) = zero;
                *(intptr+6) = zero;
                *(intptr+7) = zero;

                *(intptr+8) = zero;
                *(intptr+9) = zero;
                *(intptr+10) = zero;
                *(intptr+11) = zero;

                *(intptr+12) = zero;
                *(intptr+13) = zero;
                *(intptr+14) = zero;
                *(intptr+15) = zero;
                intptr += 16;

            } while (--i);
        }
        else
        {
            ++tryq;
            intptr += 128;
        }
    } while (--j);
}

static void BTREE_joinnodes(struct BTreeEncodeContext *EC,
                            unsigned char *cluep,
                            unsigned char *rightp,
                            unsigned char *joinp,
                            unsigned int  clue)
{
    unsigned char           *s;
    unsigned char           *d;
    unsigned char           *bend;
    unsigned int            i;

    /* pack file */

    s = EC->bufbase;
    if (s==EC->buf1)
    {
        d = EC->buf2;
    }
    else
    {
        d = EC->buf1;
    }
    EC->bufbase = d;
    bend = EC->bufend;

    *bend = (unsigned char) clue;
    while (s<=bend)
    {
        while (!cluep[(unsigned int) (*d++ = *s++)])
            ;

        i = (unsigned int) *(s-1);

        if (cluep[i]==1)
        {   if (*s==rightp[i])
            {   *(d-1) = joinp[i];
                ++s;
            }
        }
        else
        {   if (cluep[i]==3)
            {   *(d-1) = (unsigned char) clue;
                *d++ = *(s-1);
            }
            else
                *d++ = *s++;
        }
    }
    EC->bufend = d-2;
}


/* find 48 most common nodes */

static unsigned int BTREE_findbest(BTREEWORD     *countptr,
                                   unsigned char *tryq,
                                   unsigned int  *bestn,
                                   unsigned int  *bestval,
                                   int            ratio)
{
    unsigned int                i;
    unsigned int                i1;
    unsigned int                i2;
    unsigned int                bestsize;

    unsigned int                i3;
    unsigned int                l;

    bestsize = 1;
    i = 3;
    l = 0;
    for (i2=0;i2<256;++i2)
    {
        if (tryq[i2])
        {   for (i1=0;i1<256;++i1)
            {
                if (*countptr++>(BTREEWORD)i)
                {
                    if (tryq[i1])
                    {   i = *(countptr-1);
                        i3=bestsize;
                        while (bestval[i3-1]<i)
                        {
                            bestn[i3] = bestn[i3-1];
                            bestval[i3] = bestval[i3-1];
                            --i3;
                        }
                        bestn[i3] = l+i1;
                        bestval[i3] = i;
                        if (bestsize<48)
                            ++bestsize;
                        while (bestval[bestsize-1]<(bestval[1]/ratio))
                            --bestsize;
                        if (bestsize<48)
                            i = bestval[1]/ratio;
                        else
                            i = bestval[bestsize-1];
                    }
                }
            }
        }
        else
            countptr += 256;
        l += 256;
    }
    return(bestsize);
}

static void BTREE_treepack(struct BTreeEncodeContext *EC,
                           struct BTREEMemStruct *dest,
                           unsigned int     passes,
                           unsigned int     multimax,
                           unsigned int     quick,
                          int                zerosuppress)
{

    unsigned char   *bend;
    unsigned char   *ptr1;
    unsigned char   *treebuf;
    BTREEWORD       *count;
    unsigned int    i;
    unsigned int    i1;

    int             joinnode, leftnode, rightnode;
    int             ratio;
    unsigned int    domore;
    unsigned int    cost, save;
    unsigned int    tcost, tsave;
    unsigned int    clue;

    unsigned int    freeptr;
    unsigned int    count2[BTREECODES];
    unsigned char   tryq[BTREECODES];
    unsigned char   freeq[BTREECODES];

    unsigned int    bestsize;
    unsigned char   bestjoin[BTREECODES];
    unsigned int    bestn[BTREECODES];
    unsigned int    bestval[BTREECODES];

    unsigned int    bt_size;
    unsigned int    bt_node[BTREECODES];
    unsigned int    bt_left[BTREECODES];
    unsigned int    bt_right[BTREECODES];
    unsigned int    sortptr[BTREECODES];

    int         treebufsize;
    int         buf1size;
    int         buf2size;

    // 3/2 allows for worst case, where 2nd most popular
    treebufsize = 65536L*sizeof(BTREEWORD);  /* 131K */
    buf1size = EC->ulen*3/2+(int)BTREESLOPAGE;
    buf2size = EC->ulen*3/2+(int)BTREESLOPAGE;

    treebuf =   (unsigned char *) galloc(treebufsize);
    if (!treebuf)
        return; /* failure Insufficient memory for work buffer */

    EC->buf1 =  (unsigned char *) galloc(buf1size);
    if (!EC->buf1)
        return; /* failure Insufficient memory for work buffer */

    EC->buf2 =  (unsigned char *) galloc(buf2size);
    if (!EC->buf2)
        return; /* failure Insufficient memory for work buffer */

    memcpy(EC->buf1, EC->buffer, EC->ulen); /* copy to scratch buffer */

    EC->buffer = EC->buf1;
    EC->bufptr = EC->buf1+EC->ulen;

    EC->bufbase = EC->buffer;
    EC->bufend = EC->bufptr;

    count = (BTREEWORD *) treebuf;

    if (quick)  ratio = quick;
    else        ratio = 2;

/*** count file ***/

    for (i=0; i<BTREECODES; ++i)
        count2[i] = 0;

    i1 = 0;
    bend = EC->bufptr;
    ptr1 = EC->buffer;
    while (ptr1<bend)
    {   i = (unsigned int) *ptr1++;
        i1 = i1 + i;
        ++count2[i];
    }

/* init clue array */

    for (i=0;i<BTREECODES;++i)
        EC->clueq[i] = 0;

/* get a clue byte (forced) */

    for(i=0; i<BTREECODES; ++i)
    {   freeq[i] = 1;
        if (count2[i]>3)
            tryq[i] = 1;
        else
            tryq[i] = 0;
    }

/* don't use 0 for clue or node (so that [clue][0] is reserved for EOF) */

    count2[0] = BTREEBIGNUM;        /* don't use for clue or node */

/* asciiz btree suppress packing of 0..31 */

    if (zerosuppress)
    {
        for (i=0; i<32; ++i)
        {
            count2[i] = BTREEBIGNUM;        /* don't use for nodes */
            tryq[i] = 0;            /* don't try to pack */
            freeq[i] = 0;           /* don't try to pack */
        }
    }


/* sort codes with least used codes first */
/* primary key is count, secondary key is higher code */

/* registers vars usage
    i  - code
    i1 - done flag/swap temp
*/

    for (i=0;i<BTREECODES;++i)
        sortptr[i] = i;

    i1=1;
    while (i1)
    {
        i1 = 0;
        for (i=1; i<BTREECODES; ++i)
        {
            if (count2[sortptr[i]]<count2[sortptr[i-1]] || ((count2[sortptr[i]]==count2[sortptr[i-1]]) && (sortptr[i]>sortptr[i-1])))
            {
                i1 = sortptr[i];
                sortptr[i] = sortptr[i-1];
                sortptr[i-1] = i1;
                i1 = 1;
            }
        }
    }

    freeptr = 0;
    i = sortptr[freeptr++];
    clue = (unsigned char) i;
    freeq[i] = 0;
    tryq[i] = 0;
    EC->clueq[i] = 3;

    if (count2[i])
        BTREE_joinnodes(EC,EC->clueq, EC->right, EC->join, clue);

    EC->clueq[i] = 2;

/* init best array */

    bestval[0] = (unsigned int) -1;


/* count file (pass 2) */

    bt_size = 0;
    domore = passes;
    while (domore)
    {

/* clear count array */

        BTREE_clearcount(tryq,count);

/* do an adjacency count */

        ptr1 = EC->bufbase;
        bend = EC->bufend;

        BTREE_adjcount(ptr1, bend, count);

/* find most common nodes */

        bestsize = BTREE_findbest(count,tryq,bestn,bestval,ratio);

/* decide which nodes should be joined to what */

        domore = 0;
        if (bestsize>1)
        {
            tcost = tsave = 0;
            i = i1 = domore = 1;
            while (domore)
            {
                leftnode = (bestn[i]>>8)&255;
                rightnode = bestn[i]&255;

                if ((tryq[leftnode]==1) && (tryq[rightnode]==1))
                {
                    domore = 0;
                    while ((freeptr<BTREECODES) && (!freeq[sortptr[freeptr]]))
                        ++freeptr;

                    if (freeptr<BTREECODES)
                    {
                        joinnode = sortptr[freeptr];

                        cost = 3+count2[joinnode];
                        save = bestval[i];

                        if (cost<save)
                        {
                            tcost += cost;
                            tsave += save;

                            bestjoin[i1] = (unsigned char) joinnode;
                            bestn[i1] = bestn[i];
                            ++i1;

                            freeq[joinnode] = 0;
                            tryq[joinnode] = 2;
                            EC->clueq[joinnode] = 3;

                            freeq[leftnode] = 0;
                            tryq[leftnode] = 2;
                            EC->clueq[leftnode] = 1;
                            EC->right[leftnode] = (unsigned char) rightnode;
                            EC->join[leftnode] =  (unsigned char) joinnode;

                            freeq[rightnode] = 0;
                            tryq[rightnode] = 2;

                            bt_node[bt_size] = joinnode;
                            bt_left[bt_size] = leftnode;
                            bt_right[bt_size] = rightnode;
                            ++bt_size;

                            if (i1<=multimax)
                                domore = 1;
                        }
                    }
                }

                ++i;
                if (i>=bestsize)
                    domore = 0;
            }

            bestsize = i1;

            if (bestsize>1)
            {
                /* multijoin nodes */

                BTREE_joinnodes(EC,EC->clueq, EC->right, EC->join, clue);

                /* restore clue table */

                for(i=1;i<bestsize;++i)
                {   leftnode = (bestn[i]>>8)&255;
                    joinnode = bestjoin[i];
                    EC->clueq[leftnode] = EC->clueq[joinnode] = 0;
                }

                domore = --passes;
            }

        }

    }
    EC->bufptr = EC->bufend;

/* write header */

    BTREE_writebits(EC,dest,(unsigned int) clue, 8);    /* clue byte */
    BTREE_writebits(EC,dest,(unsigned int) bt_size, 8); /* tree size */

    for (i=0; i<bt_size;++i)
    {   BTREE_writebits(EC,dest,(unsigned int) bt_node[i], 8);
        BTREE_writebits(EC,dest,(unsigned int) bt_left[i], 8);
        BTREE_writebits(EC,dest,(unsigned int) bt_right[i], 8);
    }

/*** write packed file ***/

    ptr1 = EC->bufbase;
    bend = EC->bufend;

    while (ptr1<bend)
        BTREE_writebits(EC,dest,(unsigned int) *ptr1++, 8);

    BTREE_writebits(EC,dest,(unsigned int) clue, 8);
    BTREE_writebits(EC,dest,(unsigned int) 0, 8);

    BTREE_writebits(EC,dest,0L,7);  /* flush bits */

    gfree(EC->buf2);
    gfree(EC->buf1);
    gfree(treebuf);
}

static int BTREE_compressfile(struct BTreeEncodeContext *EC,
                               struct BTREEMemStruct *infile,
                               struct BTREEMemStruct *outfile,
                               int           ulen,
                               int               zerosuppress)
{
    unsigned int    i;

    unsigned int    passes;
    unsigned int    multimax;
    int         flen;

/* set defaults */

    EC->packbits = 0;

    EC->workpattern = 0L;
    passes = 256;
    multimax = 32;
    EC->masks[0] = 0;
    for (i=1;i<17;++i)
        EC->masks[i] = (EC->masks[i-1] << 1) + 1;

/* read in a source file */

    EC->buffer = (unsigned char *) (infile->ptr);
    flen = infile->len;

    EC->ulen = flen;
    EC->bufptr = EC->buffer + flen;

/* pack a file */

    outfile->ptr = outfile->ptr;
    outfile->len = 0L;

    EC->packbits = 0;
    EC->workpattern = 0L;
    EC->plen = 0L;

/* write standard header stuff (type/signature/ulen/adjust) */

    /* simple fb6 header */

    if (ulen==infile->len)
    {
        BTREE_writebits(EC,outfile,(unsigned int) 0x46fb, 16);
        BTREE_writebits(EC,outfile,(unsigned int) infile->len, 24);
    }

    /* composite fb6 header */

    else
    {
        BTREE_writebits(EC,outfile,(unsigned int) 0x47fb, 16);
        BTREE_writebits(EC,outfile,(unsigned int) ulen, 24);
        BTREE_writebits(EC,outfile,(unsigned int) infile->len, 24);
    }

    BTREE_treepack(EC,outfile,passes, multimax, 0, zerosuppress);

    return(outfile->len);
}



/****************************************************************/
/*  Encode Function                                             */
/****************************************************************/

int GCALL BTREE_encode(void *compresseddata, const void *source, int sourcesize, int *opts)
{
    int   plen;
    struct BTREEMemStruct infile;
    struct BTREEMemStruct outfile;
    struct BTreeEncodeContext EC;
    int opt=0;
    if (opts)
        opt = opts[0];

    infile.ptr = (char *)source;
    infile.len = sourcesize;
    outfile.ptr = (char *)compresseddata;
    outfile.len = sourcesize;

    plen = BTREE_compressfile(&EC,&infile, &outfile, sourcesize, opt);

    return(plen);
}

#endif

