/*  Source Control
$RCS

$version 0.1

$date Thu Jun 27 16:13:44 1991

$changes :

Revision 0.1	Jim Thu Jun 27 16:13:44 1991
compression code copied from Alexa, text handlers moved from support.c

Revision 0.0	Jim Thu Jun 27 16:13:33 1991
Added to RCS

*/

/*
 * text handling routines. Modified for fortune!
 */

#include <exec/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <libraries/dos.h>
#include <proto/all.h>

static int Oct=0;
static int ONibct=0;
static int Ct=0;
static int Nibct=0;

static UBYTE Hoffstr[8000];

#define	MSGLISTNUM	31
#define	MAX_TEXT_SIZE	4000

/*
 * Huffman code compression routines
 * ---------------------------------
 *
 * 	The compression used is a simple adaptive huffman code. Firstly,
 * the text must be analysed. The algorithm is:
 *
 * clearhuffman()			-- clear the character frequency table
 * for each text do
 * 		addtohuffman(text)	-- increment the counts for the chars that
 * 							-- appear in this string
 * end
 * genhuffman()				-- sort the frequency table and generate the
 * 							-- huffman compression table.
 * freehuffman()			-- free the frequency table.
 *
 *	The next step is to save the huffman compression table. Assuming a file
 * has been opened, you can do this with savehuffman(filepointer).
 *
 * 	Then compress your text. For each text, compress(charptr) returns
 * a character pointer to a text compressed using the current table,
 * generated by the above code.
 *
 * 	To decompress a text, you open the file and do loadhuffman(fileptr).
 * This reads the appropriate compression table into memory. Then read the
 * string from the file, and call uncompress(charptr) to get a pointer to
 * the uncompressed string.
 *
 */

static UBYTE Hoffarr[20][16];	/* 20 just in case */

/* Add a nybble to a string */
static void puthoff(UBYTE n)
{
	if(Nibct==0)
	{
		Hoffstr[Ct]=0;
		Hoffstr[Ct] |= n<<4;
		Nibct++;
	}
	else
	{
		Hoffstr[Ct] |= n&0x0f;
		Nibct=0;
		Ct++;
	}
}


static int getarray(UBYTE *a,UBYTE *p,UBYTE c)
{
	register UBYTE i,j;

	if(!c)
	{
		*a=0;
		*p=0;
		return(1);
	}
	for(i=0;i<20;i++)
		for(j=2;j<16;j++)
		{
			if(Hoffarr[i][j]==c)
			{
				*a=i;
				*p=j;
				return(0);
			}
		}
	printf("Compression error: Character not found in tables- %c(%x)\n",
	c,c);
	exit(0);
}

/* get a nybble from a string */
static UBYTE gethoff(UBYTE *a)
{
	register UBYTE q;
	if(ONibct==0)
	{
		ONibct++;
		q=(a[Oct]&0xf0)>>4;
	}
	else
	{
		ONibct=0;
		q=a[Oct++]&0x0f;
	}
	return(q);
}


/*
 * Compress a null-terminated string down to another null-terminated string
 * using an adaptive huffman code. The table must be initialised, usually
 * with addtohuffman and genhuffman.
 *
 */

UBYTE *compress(UBYTE *a)
{
	register int i;
	UBYTE ar,pos,end;
	Ct=0; Nibct=0;

	for(i=0;;i++)
	{
		/* What array is the letter a[i] in? */
		end=getarray(&ar,&pos,a[i]);

		/* output the appropriate number of zeroes */

		for(;ar>0;ar--)
		{
			puthoff(1);
		}

		/* output the position */

		puthoff(pos);
		if(end)break;
	}
	puthoff(0);
	puthoff(0);
	return(Hoffstr);
}

/*
 * Decompress a string. The table must be initialised, usually with
 * loadhuffman() in this case.
 *
 */

UBYTE *uncompress(UBYTE *a)
{
	int i,ct=0;
	UBYTE ar,pos;

	Oct=0; ONibct=0;

	for(i=0;;i++)
	{
		ar=0;
		while((pos=gethoff(a))==1) ar++;
		if(pos==0)break;
		Hoffstr[ct++]=Hoffarr[ar][pos];
		if(ct>1998)
		{
			printf("Error in text docompression - too long!\n");
			exit(0);
		}
	}
	Hoffstr[ct]=NULL;
	return(Hoffstr);
}


/*
 * Routines for ADAPTIVE huffman coding
 *
 */

struct charcnt
{
	UBYTE c;
	long n;
};
static struct charcnt *CharCounts=NULL;

/*
 * clear character counts
 *
 */
void clearhuffman(void)
{
	int i;

	if(!CharCounts)CharCounts=(struct charcnt *)
		malloc(256*sizeof(struct charcnt));

	for(i=0;i<256;i++){CharCounts[i].n=0; CharCounts[i].c=i;};
}

void freehuffman(void)
{
	free(CharCounts); CharCounts=NULL;
}

/*
 * process ready for coding
 *
 */

void addtohuffman(UBYTE *s)
{
	while(*s)CharCounts[*(s++)].n++;
}

/*
 * and generate the tables
 *
 */

static int compare(struct charcnt *a,struct charcnt *b)
{
	return(b->n - a->n);
}

void genhuffman(void)
{
	int tabl=0,slot=2,i;

	/* sort the table */
	/* This is the lattice QuickSort function. It sorts an array:
		The format is -
		qsort(pointer to table,	number of elements,
			size of each element, pointer to comparison function)

		One problem is that is takes a lot of stack. You'll have to increase
		your stack size quite a lot with the AmigaDOS 'stack' command.
	*/

	qsort((UBYTE *)CharCounts,256,sizeof(struct charcnt),&compare);

	for(i=0;;i++)
	{
		if(!CharCounts[i].n)break;
		Hoffarr[tabl][slot]=CharCounts[i].c;
		if(++slot>15){tabl++,slot=2;};
		if(tabl>19)exit(0);
	}
}

/*
 * Save and load huffman tables
 *
 */

void savehuffman(BPTR a)
{
	Write(a,&Hoffarr,sizeof(Hoffarr));
}

void loadhuffman(BPTR a)
{
	Read(a,&Hoffarr,sizeof(Hoffarr));
}

int readshort(BPTR a)
{
	short n;
	int m;
	Read(a,&n,sizeof(short));
	m=(int)n;
	return(m);
}

long readlong(BPTR a)
{
	long n;
	Read(a,&n,sizeof(long));
	return(n);
}

void writelong(BPTR a,long n)
{
	Write(a,&n,sizeof(long));
}

void writeshort(BPTR a,int n)
{
	short m;

	m=(short)n;
	Write(a,&m,sizeof(short));
}

UBYTE *readstring(UBYTE *buf,int len,BPTR a)
{
	int n,i;
	for(i=0;i<len;i++)
	{
		n=Read(a,buf+i,1);
		if(!n||(buf[i]==NULL))break;
	}
	return(!n?NULL:buf);
}