#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <math.h>
#include <limits.h>

#include "nmglobal.h"
#include "nbench1.h"

/************************
** HUFFMAN COMPRESSION **
************************/

/*
** DEFINES
*/
#define EXCLUDED 32000L          /* Big positive value */

/*
** TYPEDEFS
*/
typedef struct {
	unsigned char c;                /* Byte value */
	float freq;             /* Frequency */
	int parent;             /* Parent node */
	int left;               /* Left pointer = 0 */
	int right;              /* Right pointer = 1 */
} huff_node;

/*
** GLOBALS
*/
static huff_node *hufftree;             /* The huffman tree */
static long plaintextlen;               /* Length of plaintext */

/*
** PROTOTYPES
*/
static void create_text_line(char *dt,long nchars);
static void create_text_block(char *tb, unsigned long tblen,
		unsigned short maxlinlen);
static unsigned long DoHuffIteration(char *plaintext,
	char *comparray, char *decomparray,
	unsigned long arraysize, unsigned long nloops, huff_node *hufftree);
static void SetCompBit(uint8_t *comparray, uint32_t bitoffset, char bitchar);
static int GetCompBit(uint8_t *comparray, uint32_t bitoffset);

/*
** Word catalog
*/
#define WORDCATSIZE 50

char *wordcatarray[WORDCATSIZE] = { /* FIXME: const? */
        "Hello",
	"He",
	"Him",
	"the",
	"this",
	"that",
	"though",
	"rough",
	"cough",
	"obviously",
	"But",
	"but",
	"bye",
	"begin",
	"beginning",
	"beginnings",
	"of",
	"our",
	"ourselves",
	"yourselves",
	"to",
	"together",
	"togetherness",
	"from",
	"either",
	"I",
	"A",
	"return",
	"However",
	"that",
	"example",
	"yet",
	"quickly",
	"all",
	"if",
	"were",
	"includes",
	"always",
	"never",
	"not",
	"small",
	"returns",
	"set",
	"basic",
	"Entered",
	"with",
	"used",
	"shown",
	"you",
	"know"
};

/**************
** DoHuffman **
***************
** Execute a huffman compression on a block of plaintext.
** Note that (as with IDEA encryption) an iteration of the
** Huffman test includes a compression AND a decompression.
** Also, the compression cycle includes building the
** Huffman tree.
*/
void DoHuffman(void)
{
HuffStruct *lochuffstruct;      /* Loc pointer to global data */
char *context;
int systemerror;
unsigned long accumtime;
double iterations;
char *comparray = NULL;
char *decomparray = NULL;
char *plaintext = NULL;

/*
** Link to global data
*/
lochuffstruct=&global_huffstruct;

/*
** Set error context.
*/
context="CPU:Huffman";

/*
** Allocate memory for the plaintext and the compressed text.
** We'll be really pessimistic here, and allocate equal amounts
** for both (though we know...well, we PRESUME) the compressed
** stuff will take less than the plain stuff.
** Also note that we'll build a 3rd buffer to decompress
** into, and we preallocate space for the huffman tree.
** (We presume that the Huffman tree will grow no larger
** than 512 bytes.  This is actually a super-conservative
** estimate...but, who cares?)
*/
plaintext = malloc(lochuffstruct->arraysize);
if (!plaintext) {
        fprintf(stderr, "Error in %s, could not allocate memory. Exitting...\n", context);
        exit(1);
}

comparray = malloc(lochuffstruct->arraysize);
if (!comparray) {
        fprintf(stderr, "Error in %s, could not allocate memory. Exitting...\n", context);
        free(plaintext);
        exit(1); /* FIXME: do I need exits here? */
}

decomparray = malloc(lochuffstruct->arraysize);
if (!decomparray) {
        fprintf(stderr, "Error in %s, could not allocate memory. Exitting...\n", context);
        free(plaintext);
        free(comparray);
        exit(1);
}

hufftree = malloc(sizeof(huff_node) * 512);
if (!hufftree) {
        fprintf(stderr, "Error in %s, could not allocate memory. Exitting...\n", context);
        free(plaintext);
        free(comparray);
        free(decomparray);
        exit(1);
}

/*
** Build the plaintext buffer.  Since we want this to
** actually be able to compress, we'll use the
** wordcatalog to build the plaintext stuff.
*/
/*
** Reset random number generator so things repeat.
** added by Uwe F. Mayer
*/
randnum((int32_t)13);
create_text_block(plaintext,lochuffstruct->arraysize-1,(unsigned short)500);
plaintext[lochuffstruct->arraysize-1L]='\0';
plaintextlen=lochuffstruct->arraysize;

/*
** See if we need to perform self adjustment loop.
*/
if(lochuffstruct->adjust==0)
{
	/*
	** Do self-adjustment.  This involves initializing the
	** # of loops and increasing the loop count until we
	** get a number of loops that we can use.
	*/
	for(lochuffstruct->loops=100L;
	  lochuffstruct->loops<MAXHUFFLOOPS;
	  lochuffstruct->loops+=10L)
		if(DoHuffIteration(plaintext,
			comparray,
			decomparray,
		  lochuffstruct->arraysize,
		  lochuffstruct->loops,
		  hufftree)>global_min_ticks) break;
}

/*
** All's well if we get here.  Do the test.
*/
accumtime=0L;
iterations=(double)0.0;

do {
	accumtime+=DoHuffIteration(plaintext,
		comparray,
		decomparray,
		lochuffstruct->arraysize,
		lochuffstruct->loops,
		hufftree);
	iterations+=(double)lochuffstruct->loops;
} while(TicksToSecs(accumtime)<lochuffstruct->request_secs);

/*
** Clean up, calculate results, and go home.  Be sure to
** show that we don't have to rerun adjustment code.
*/
free(plaintext);
free(comparray);
free(decomparray);
free(hufftree);
lochuffstruct->iterspersec=iterations / TicksToFracSecs(accumtime);

if(lochuffstruct->adjust==0)
	lochuffstruct->adjust=1;

}

/*********************
** create_text_line **
**********************
** Create a random line of text, stored at *dt.  The line may be
** no more than nchars long.
*/
static void create_text_line(char *dt,
			long nchars)
{
long charssofar;        /* # of characters so far */
long tomove;            /* # of characters to move */
char myword[40];        /* Local buffer for words */
char *wordptr;       /* Pointer to word from catalog */

charssofar=0;

do {
/*
** Grab a random word from the wordcatalog
*/
/* wordptr=wordcatarray[abs_randwc((long)WORDCATSIZE)];*/
wordptr=wordcatarray[abs_randwc((int32_t)WORDCATSIZE)];
memmove(myword, wordptr, strlen(wordptr) + 1);

/*
** Append a blank.
*/
tomove=strlen(myword)+1;
myword[tomove-1]=' ';

/*
** See how long it is.  If its length+charssofar > nchars, we have
** to trim it.
*/
if((tomove+charssofar)>nchars)
	tomove=nchars-charssofar;
/*
** Attach the word to the current line.  Increment counter.
*/
memmove(dt, myword, tomove);
charssofar+=tomove;
dt+=tomove;

/*
** If we're done, bail out.  Otherwise, go get another word.
*/
} while(charssofar<nchars);

return;
}

/**********************
** create_text_block **
***********************
** Build a block of text randomly loaded with words.  The words
** come from the wordcatalog (which must be loaded before you
** call this).
** *tb points to the memory where the text is to be built.
** tblen is the # of bytes to put into the text block
** maxlinlen is the maximum length of any line (line end indicated
**  by a carriage return).
*/
static void create_text_block(char *tb,
			unsigned long tblen,
			unsigned short maxlinlen)
{
unsigned long bytessofar;       /* # of bytes so far */
unsigned long linelen;          /* Line length */

bytessofar=0L;
do {

/*
** Pick a random length for a line and fill the line.
** Make sure the line can fit (haven't exceeded tablen) and also
** make sure you leave room to append a carriage return.
*/
linelen=abs_randwc(maxlinlen-6)+6;
if((linelen+bytessofar)>tblen)
	linelen=tblen-bytessofar;

if(linelen>1)
{
	create_text_line(tb,linelen);
}
tb+=linelen-1;          /* Add the carriage return */
*tb++='\n';

bytessofar+=linelen;

} while(bytessofar<tblen);

}

/********************
** DoHuffIteration **
*********************
** Perform the huffman benchmark.  This routine
**  (a) Builds the huffman tree
**  (b) Compresses the text
**  (c) Decompresses the text and verifies correct decompression
*/
static unsigned long DoHuffIteration(char *plaintext,
	char *comparray,
	char *decomparray,
	unsigned long arraysize,
	unsigned long nloops,
	huff_node *hufftree)
{
int i;                          /* Index */
long j;                         /* Bigger index */
int root;                       /* Pointer to huffman tree root */
float lowfreq1, lowfreq2;       /* Low frequency counters */
int lowidx1, lowidx2;           /* Indexes of low freq. elements */
long bitoffset;                 /* Bit offset into text */
long textoffset;                /* Char offset into text */
long maxbitoffset;              /* Holds limit of bit offset */
long bitstringlen;              /* Length of bitstring */
int c;                          /* Character from plaintext */
char bitstring[30];             /* Holds bitstring */
unsigned long elapsed;                  /* For stopwatch */
#ifdef DEBUG
int status=0;
#endif

/*
** Start the stopwatch
*/
elapsed=StartStopwatch();

/*
** Do everything for nloops
*/
while(nloops--)
{

/*
** Calculate the frequency of each byte value. Store the
** results in what will become the "leaves" of the
** Huffman tree.  Interior nodes will be built in those
** nodes greater than node #255.
*/
for(i=0;i<256;i++)
{
	hufftree[i].freq=(float)0.0;
	hufftree[i].c=(unsigned char)i;
}

for(j=0;j<arraysize;j++)
	hufftree[(int)plaintext[j]].freq+=(float)1.0;

for(i=0;i<256;i++)
	if(hufftree[i].freq != (float)0.0)
		hufftree[i].freq/=(float)arraysize;

/* Reset the second half of the tree. Otherwise the loop below that
** compares the frequencies up to index 512 makes no sense. Some
** systems automatically zero out memory upon allocation, others (like
** for example DEC Unix) do not. Depending on this the loop below gets
** different data and different run times. On our alpha the data that
** was arbitrarily assigned led to an underflow error at runtime. We
** use that zeroed-out bits are in fact 0 as a float.
** Uwe F. Mayer */
bzero((char *)&(hufftree[256]),sizeof(huff_node)*256);
/*
** Build the huffman tree.  First clear all the parent
** pointers and left/right pointers.  Also, discard all
** nodes that have a frequency of true 0.  */
for(i=0;i<512;i++)
{       if(hufftree[i].freq==(float)0.0)
		hufftree[i].parent=EXCLUDED;
	else {
		hufftree[i].right = -1;
		hufftree[i].left = -1;
		hufftree[i].parent = -1;
	}
}

/*
** Go through the tree. Finding nodes of really low
** frequency.
*/
root=255;                       /* Starting root node-1 */
while(1)
{
	lowfreq1=(float)2.0; lowfreq2=(float)2.0;
	lowidx1=-1; lowidx2=-1;
	/*
	** Find first lowest frequency.
	*/
	for(i=0;i<=root;i++)
		if(hufftree[i].parent<0)
			if(hufftree[i].freq<lowfreq1)
			{       lowfreq1=hufftree[i].freq;
				lowidx1=i;
			}

	/*
	** Did we find a lowest value?  If not, the
	** tree is done.
	*/
	if(lowidx1==-1) break;

	/*
	** Find next lowest frequency
	*/
	for(i=0;i<=root;i++)
		if((hufftree[i].parent<0) && (i!=lowidx1))
			if(hufftree[i].freq<lowfreq2)
			{       lowfreq2=hufftree[i].freq;
				lowidx2=i;
			}

	/*
	** If we could only find one item, then that
	** item is surely the root, and (as above) the
	** tree is done.
	*/
	if(lowidx2==-1) break;

	/*
	** Attach the two new nodes to the current root, and
	** advance the current root.
	*/
	root++;                 /* New root */
	hufftree[lowidx1].parent=root;
	hufftree[lowidx2].parent=root;
	hufftree[root].freq=lowfreq1+lowfreq2;
	hufftree[root].left=lowidx1;
	hufftree[root].right=lowidx2;
	hufftree[root].parent=-2;       /* Show root */
}

/*
** Huffman tree built...compress the plaintext
*/
bitoffset=0L;                           /* Initialize bit offset */
for(i=0;i<arraysize;i++)
{
	c=(int)plaintext[i];                 /* Fetch character */
	/*
	** Build a bit string for byte c
	*/
	bitstringlen=0;
	while(hufftree[c].parent!=-2)
	{       if(hufftree[hufftree[c].parent].left==c)
			bitstring[bitstringlen]='0';
		else
			bitstring[bitstringlen]='1';
		c=hufftree[c].parent;
		bitstringlen++;
	}

	/*
	** Step backwards through the bit string, setting
	** bits in the compressed array as you go.
	*/
	while(bitstringlen--)
	{       SetCompBit((uint8_t *)comparray,(uint32_t)bitoffset,bitstring[bitstringlen]);
		bitoffset++;
	}
}

/*
** Compression done.  Perform de-compression.
*/
maxbitoffset=bitoffset;
bitoffset=0;
textoffset=0;
do {
	i=root;
	while(hufftree[i].left!=-1)
	{       if(GetCompBit((uint8_t *)comparray,(uint32_t)bitoffset)==0)
			i=hufftree[i].left;
		else
			i=hufftree[i].right;
		bitoffset++;
	}
	decomparray[textoffset]=hufftree[i].c;

#ifdef DEBUG
	if(hufftree[i].c != plaintext[textoffset])
	{
		/* Show error */
		printf("Error at textoffset %ld\n",textoffset);
		status=1;
	}
#endif
	textoffset++;
} while(bitoffset<maxbitoffset);

}       /* End the big while(nloops--) from above */

/*
** All done
*/
#ifdef DEBUG
  if (status==0) printf("Huffman: OK\n");
#endif
return(StopStopwatch(elapsed));
}

/***************
** SetCompBit **
****************
** Set a bit in the compression array.  The value of the
** bit is set according to char bitchar.
*/
static void SetCompBit(uint8_t *comparray,
		uint32_t bitoffset,
		char bitchar)
{
uint32_t byteoffset;
int bitnumb;

/*
** First calculate which element in the comparray to
** alter. and the bitnumber.
*/
byteoffset=bitoffset>>3;
bitnumb=bitoffset % 8;

/*
** Set or clear
*/
if(bitchar=='1')
	comparray[byteoffset]|=(1<<bitnumb);
else
	comparray[byteoffset]&=~(1<<bitnumb);

return;
}

/***************
** GetCompBit **
****************
** Return the bit value of a bit in the comparession array.
** Returns 0 if the bit is clear, nonzero otherwise.
*/
static int GetCompBit(uint8_t *comparray,
		uint32_t bitoffset)
{
uint32_t byteoffset;
int bitnumb;

/*
** Calculate byte offset and bit number.
*/
byteoffset=bitoffset>>3;
bitnumb=bitoffset % 8;

/*
** Fetch
*/
return((1<<bitnumb) & comparray[byteoffset] );
}