path: root/huffman.c

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

#include "nmglobal.h"
#include "randnum.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 clock_t 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);


/**************
** 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)
{
        const char*     context = "CPU:Huffman";
        HuffStruct*     lochuffstruct = &global_huffstruct;
        clock_t         total_time = 0;
        int             iterations = 0;
        char*           comparray = NULL;
        char*           decomparray = NULL;
        char*           plaintext = NULL;


        /*
        ** 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 == FALSE) {
                lochuffstruct->adjust = TRUE;
                /*
                ** 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 = 100; lochuffstruct->loops < MAXHUFFLOOPS; lochuffstruct->loops += 10) {
                        if (DoHuffIteration(plaintext, comparray, decomparray, lochuffstruct->arraysize, lochuffstruct->loops, hufftree) > global_min_ticks) {
                                break;
                        }
                }
        }

        do {
                total_time += DoHuffIteration(plaintext, comparray, decomparray, lochuffstruct->arraysize, lochuffstruct->loops, hufftree);
                iterations += lochuffstruct->loops;
        } while (total_time < lochuffstruct->request_secs * CLOCKS_PER_SEC);

        free(plaintext);
        free(comparray);
        free(decomparray);
        free(hufftree);

        lochuffstruct->results = (double)(iterations * CLOCKS_PER_SEC) / (double)total_time;
}

/*********************
** 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 = 0;        /* # of characters so far */
long tomove;            /* # of characters to move */
char myword[40];        /* Local buffer for words */
char *wordptr;       /* Pointer to word from catalog */

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

char * wordcatarray[WORDCATSIZE] = {
        "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"
};

do {
/*
** Grab a random word from the wordcatalog
*/
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 clock_t
DoHuffIteration(char *plaintext, char *comparray, char *decomparray, unsigned long arraysize, unsigned long nloops, huff_node *hufftree)
{
        clock_t start, stop;
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 */

        start = clock();

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); /* FIXME: replace bzero with memset? */
/*
** 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;

	textoffset++;
} while(bitoffset<maxbitoffset);

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

        stop = clock();

        return stop - start;
}

/***************
** 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] );
}