#pragma ident "@(#)cgphuffman.c	1.7 98/08/25 SMI"

/*
 * Copyright (c) 1997 by Sun Microsystems, Inc.
 * All Rights Reserved
 */


/*
 ***********************************************************************
 *
 *  hs_huffman.c
 *
 *      @(#)hs_huffman.c 1.5 95/03/24 22:14:15
 *
 *  Copyright (c) 1993 by Sun Microsystems, Inc.
 *
 *
 *  HoloSketch Huffman table encoding routine.
 *
 *  First created Aaron Wynn, 12/94
 *  Updated, integreated into HoloSketch MFD 12/94
 *
 ***********************************************************************
 */

#include <stdio.h>
#include <sys/types.h>
#include <sys/time.h>
#include "cgpi.h"
#include "cgpstream.h"
#include "cgpcompress.h"

/*
 *  The Huffman process generates a variable length (but unique within
 *  the variable length) series of code (tag) values, where each code value
 *  is associated with a particular symbol.  The process is optimized
 *  such that the more frequent symbols get the codes with the fewest
 *  number of bits.
 *  
 *  For our purposes, the symbols are the integers (v) representing the number
 *  of bits of our variable length data (usually, but not always, deltas).
 *
 *  freq[v] = frequency of occurrance of data element of size 'v' bits.
 *  
 *  codesize[v] = code size of symbol v.
 *
 *  others[v] = indirection link for code tree.
 *
 *  code_table[v] = Huffman code asigned to symbol v.
 *
 *  code_size_table[v] = size in bits of Huffman code code_table[v].
 *
 *  data_size_table[v] = size in bits of the data elements now associated
 *			 with v.  This is *not* just v, because of merges.
 *
 *  n is the number of elements in vector 'freq'
 *  (between 1 and MAX_CODE_SIZE-1).
 *  (Sticking to C array index conventions, freq[0] exists, but is unused.)
 *
 */

/*
 *  The procedure cgpCompHuffman takes in freq[] and n, and outputs
 *  into the huffman_stats structure the arrays
 *  code_table[], code_size_table[], and data_size_table[], as the
 *  (~optimal) tag encodings of the variable length data fields.
 */

void
cgpCompHuffman(CGPtabledata *histo, int n)
{
    int freq[CGP_MAX_CODE_SIZE];	 /* local copy of histo array */
    int	huffsize[CGP_MAX_CODE_SIZE]; /* sizes of Huffman codes */
    int	huffcode[CGP_MAX_CODE_SIZE]; /* Huffman codes */
    int	huffval[CGP_MAX_CODE_SIZE]; /* vals to which Huffman codes correspond */
    int codesize[CGP_MAX_CODE_SIZE];
    int others[CGP_MAX_CODE_SIZE];
    int bits[CGP_MAX_CODE_SIZE];
    int i,j,k,min,v1,v2;
    int code,si;
    int min_size,min_index;
    int last, abs;
    int max_code_size, mcs_i;
    int first_time;
    int mustCreateEntry, entryToMerge, mustMerge;
    int lastk;

    /* Clamp n */
    if (n < 1) n = 1;
    if (n > CGP_MAX_CODE_SIZE) n = CGP_MAX_CODE_SIZE;

    /* Don't overwrite the input hhisto table; make a local copy into freq */
    for (i = 0; i < n; i++)
	freq[i] = histo[i].freq;


    /*=======================================================================*/
    /*  This section of code is based on section K.2 of the JPEG standard    */
    /*=======================================================================*/

    /* Initialize arrays */
    for (i = 0; i < CGP_MAX_CODE_SIZE; i++) {
	others[i] = -1;
	codesize[i] = 0;
	bits[i] = 0;
    }

    /*
     *  Determine sizes of Huffman codes based on frequency of occurrences.
     */
    first_time = 1;
    while (1) {

	/*
	 *  Find smallest frequency left in freq[] table,
	 *  placing its index into v1
	 */
	min = 0x7fffffff;  /* max positive 32-bit int */
	v1 = -1;	   /* initially, no min index found */
	for (i = 0; i < n; i++) {
	    if ((freq[i] > 0) && (freq[i] <= min)) {
		v1 = i;		/* New winner and current champ */
		min = freq[i];
	    }
	}

	/* Find second smallest frequency left in table, into index v2 */
	min = 0x7fffffff;  /* max positive 32-bit int */
	v2 = -1;           /* initially, no second min index found */
	for (i = 0; i < n; i++) {
	    if ((i != v1) && (freq[i] > 0) && (freq[i] <= min)) {
		v2 = i;
		min = freq[i];
	    }
	}

	/*
	 *  If no second smallest frequency exists, then we are finished.
	 */
	if (v2 < 0) {
		/* If only one frequency in table, give it codesize 0 */
		if (first_time) {
                    /* TODO: Work around AFB bug - it can't write to more */
                    /* 32 entries at a time.  Have to make minimum tag */
                    /* of 1 bit */
                    histo[v1].huffCode = 0;
                    histo[v1].huffCodeSize = 1;
		    return;
		}
		break;
	}
	first_time = 0;

	/*
	 *  Now to merge the two smallest nodes.
	 */
	freq[v1] += freq[v2];
	freq[v2] = 0;

	/* Update codesizes for v1's subtree */
	codesize[v1]++;
	while (others[v1] >= 0) {
	    v1 = others[v1];
	    codesize[v1]++;
	}

	others[v1] = v2;

	/* Update codesizes for v2's subtree */
	codesize[v2]++;
	while (others[v2] >= 0) {
	    v2 = others[v2];
	    codesize[v2]++;
	}
    }


    /*
     *  As of here, all the codes should be assigned.
     *
     *  However, more than our target (usually 6) number of bits of codes
     *  (tags) may have been used, so we need to re-ballance the tree so
     *  that the longest code size does not exceed the target.
     */


    /* Count number of codes of each size */
    for (i = 0; i < n; i++)
	if (codesize[i] != 0)
	    bits[codesize[i]]++;

    /*
     *	Code for rebalancing tree such that all codes are less than a certain
     *	size is not used.  After Huffman codes are generated, elements with
     *	longer codes are merged with those with shorter codes.
     */

#ifdef NOT_ALL_ONES
    /*
     *  Remove code for largest (sentinal) value,
     *  only if reserving all 1's code.
     */
    for (i = n-1; bits[i] == 0 && i>0; i--);  /* finds largest non zero code */
    bits[i]--;  /* take out its bits contributation */
#endif

    /*
     *  Sort codes based on size into huffval[] such that the one with
     *  the least number of bits becomes huffval[0], next huffval[1], etc.
     *  In case of ties, always choose smallest index.
     */
    for (i = 1, k = 0; i < CGP_MAX_CODE_SIZE; i++) {
	for (j = 0; j < n; ++j) {
	    if (codesize[j] == i) {
		huffval[k++] = j;
	    }
	}
    }


    /*=======================================================================*/
    /*  This section of code is based on section C.2 of the JPEG standard    */
    /*=======================================================================*/

    /* Generate size table for Huffman codes */
    for (k = 0, i = 1; i < CGP_MAX_CODE_SIZE; i++) {
	for (j = 1; j <= bits[i]; ++j) {
	    huffsize[k++] = i;
	}
    }
    huffsize[k] = 0;
    lastk = k;

    /* Generate Huffman codes */
    k = 0;
    code = 0;
    si = huffsize[0];
    while (huffsize[k]) {
	while (huffsize[k] == si) {
	    huffcode[k] = code;
	    ++code;
	    ++k;
	}

	code <<= 1;
	si++;
    }

    /*=====================================================================*/
    /* assign huffman info to stats data                                   */
    for (k = 0; k < lastk; k++)
    {
        histo[huffval[k]].huffCodeSize = huffsize[k];
        histo[huffval[k]].huffCode = huffcode[k];
    }

    /* merge all entries with huffCodeSize > 6 */
    /* this is done by simply finding the first entry with a huffman code */
    /* size less than or equal to 6 (the maximum allowed) and the same    */
    /* absolute/relative bit and mergeing all entries with huffman tag    */
    /* > 6 with that entry.  This could lead to cases where the frequency */
    /* of the combined entries is greater than freqnecies of some entries */
    /* with smaller huffman tags.  Perhaps some sort of iterative approach*/
    /* of mergeing and recomputing the huffman values would be better.    */
    /* Also if no tag <= 6 bits with a matching abs/rel bit is found then */
    /* all entries have to be moved one more time to open up an entry to  */
    /* create the needed abs/rel entry.                                   */
    for (abs = 0; abs < 2; abs++)
    {
        mustCreateEntry = 0;
        mustMerge = 0;

        /* after this loop if mustMerge is set there are entries with tags */
        /* > 6, these must be merged.  mustCreateEntry will be  non-zero   */
        /* if there are no entries of the given abs value with tags <= 6   */
        for (k = lastk - 1; k > 0; k--)
            if (histo[huffval[k]].abs == abs)
                if (huffsize[k] > 6)
                {
                    mustMerge = 1;
                    mustCreateEntry = abs + 1;
                }
                else
                {
                    mustCreateEntry = 0;
                    break;
                }

        /* k now points to largest huffCodeSize < 6 and same abs/rel */
        if (mustMerge && mustCreateEntry == 0)
        {
            /* need to merge all values > k with the k entry */
            for (i = lastk - 1; i > k; i--)
                if (histo[huffval[i]].abs == abs)
                {
                    histo[huffval[i]].merge = huffval[k];

                    if (histo[huffval[i]].shift < histo[huffval[k]].shift)
                        histo[huffval[k]].shift = histo[huffval[i]].shift;

                    if (histo[huffval[i]].len > histo[huffval[k]].len)
                        histo[huffval[k]].len = histo[huffval[i]].len;
                }
        }

    }

    /* all entries now fit, unless all abs or rel entries have tags */
    /* greater than 6.  If this is the case need to do 1 more merge */
    /* and use free'd up entry                                       */
    if (mustCreateEntry)
    {
        int entryToMerge;
        int firstEntry = 1;

        abs = mustCreateEntry - 1;

        /* find entry that will be used to create the needed abs type entry */
        for (entryToMerge = lastk - 1;
             (huffsize[entryToMerge] > 6 ||
             histo[huffval[entryToMerge]].abs == abs) &&
             entryToMerge > 0; entryToMerge--)
            ;

        /* merge with previous entry */
        for (i = lastk - 1; i >= entryToMerge; i--)
                if (histo[huffval[i]].abs != abs)
                {
                    if (histo[huffval[i]].shift <
                        histo[huffval[entryToMerge - 1]].shift)
                        histo[huffval[entryToMerge - 1]].shift =
                            histo[huffval[i]].shift;

                    if (histo[huffval[i]].len >
                        histo[huffval[entryToMerge - 1]].len)
                        histo[huffval[entryToMerge - 1]].len =
                                             histo[huffval[i]].len;

                    histo[huffval[i]].merge = huffval[entryToMerge - 1];
                }

        /* setup entry for new abs type */
        histo[huffval[entryToMerge]].abs = abs;
        for (i = lastk - 1; i > entryToMerge; i--)
                if (histo[huffval[i]].abs == abs)
                {
                    /* move entries into opened table position */
                    if (firstEntry)
                    {
                        histo[huffval[entryToMerge]].shift =
                          histo[huffval[i]].shift;

                        histo[huffval[entryToMerge]].len =
                          histo[huffval[i]].len;

                        histo[huffval[i]].merge = huffval[entryToMerge];

                        histo[huffval[entryToMerge]].merge = -1;

                        firstEntry = 0;
                    }
                    else
                    {
                        if (histo[huffval[i]].shift <
                            histo[huffval[entryToMerge]].shift)
                            histo[huffval[entryToMerge]].shift =
                                histo[huffval[i]].shift;

                        if (histo[huffval[i]].len >
                            histo[huffval[entryToMerge]].len)
                            histo[huffval[entryToMerge]].len =
                                       histo[huffval[i]].len;

                        histo[huffval[i]].merge = huffval[entryToMerge];
                    }
                }

        histo[huffval[entryToMerge]].amerge = huffval[entryToMerge - 1];
    }

}  /* end of cgpCompHuffman */

