GeneralsZeroHour/Generals/Code/Libraries/Source/Compression/EAC/btreeencode.cpp

/*
**	Command & Conquer Generals(tm)
**	Copyright 2025 Electronic Arts Inc.
**
**	This program is free software: you can redistribute it and/or modify
**	it under the terms of the GNU General Public License as published by
**	the Free Software Foundation, either version 3 of the License, or
**	(at your option) any later version.
**
**	This program is distributed in the hope that it will be useful,
**	but WITHOUT ANY WARRANTY; without even the implied warranty of
**	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
**	GNU General Public License for more details.
**
**	You should have received a copy of the GNU General Public License
**	along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

// Copyright (C) Electronic Arts Canada Inc. 1995-2002.  All rights reserved.

#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	hlen;
	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);
	}

	hlen = EC->plen;

/*** 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