/* Aaron Logue 1999 */

typedef struct tagBIG_HUFFMAN_NODE * PBIG_HUFFMAN_NODE;
typedef struct tagBIG_HUFFMAN_NODE {
   unsigned char left;
   PBIG_HUFFMAN_NODE pleft;
   unsigned char right;
   PBIG_HUFFMAN_NODE pright;
} BIG_HUFFMAN_NODE;

/*
 * The character occurence counts, stored in the 'counted' array,
 * are coalesced into a single ACCUM structure with nptr pointing
 * at the root of the Huffman tree.  Before this process is begun,
 * we'll copy the elements of our sorted 'counted' array into an
 * array of BITCODES structures called 'bitcodes' that we'll use
 * to perform encoding.
 */
typedef struct tagBITCODES {
   unsigned int count;
   unsigned char * bitcode;
   unsigned int bitcount;
} BITCODES;

typedef struct tagHUFFMAN_NODE * PHUFFMAN_NODE;
typedef struct tagHUFFMAN_NODE {
   unsigned char left;        /* Either a character or the number of the next node, */
   unsigned char right;       /* specified by value of huffman tree node flag */
} HUFFMAN_NODE;

typedef struct tagHUFFMAN_DECODING_HANDLE {
   unsigned char flags;       /* First byte of file */
   unsigned char numnodes;    /* Second byte of file */
   PHUFFMAN_NODE tree;        /* Points at condensed huffman tree */
   unsigned char * tflags;    /* Points at condensed huffman tree node flags */
   unsigned long totalbytes;  /* Number of bytes decoded */
   unsigned int totalmod8;    /* Tells us how to stop on last bitstream byte */
   unsigned char * bitstream; /* bitstream buffer */
   unsigned int head;
   unsigned int tail;
   unsigned char * outbuf;    /* output buffer */
   unsigned int full;         /* count of bytes in output buffer */
} HUFFMAN_DECODING_HANDLE;


/*
 * We make a first pass on the uncompressed data to accumulate character
 * occurence counts in descending order of probability in an array that
 * we can use, by sequential coalescing, to build the Huffman tree with.
 */
typedef struct tagACCUM {
   unsigned char c;
   int count;
   PBIG_HUFFMAN_NODE nptr;
} ACCUM;

typedef struct tagHUFFMAN_ENCODING_HANDLE {
   unsigned int ocount;       /* How many unique 8-bit values in file */
   ACCUM counted[256];        /* Counts stored here, destroyed as tree is built */
   unsigned long totalbytes;
   unsigned char walkbits[32];/* Storage needed by a recursive tree walker */
   BITCODES bitcodes[256];    /* Character counts and bitcodes stored here */
   PHUFFMAN_NODE tree;        /* Points at condensed huffman tree */
   unsigned char * tflags;    /* Points at condensed huffman tree node flags */
} HUFFMAN_ENCODING_HANDLE;

/* Macros to set, clear, or test bit n of byte array b */
#define SET_HBIT(b,n) b[(n)>>3]|=(1<<((n)&7))
#define CLR_HBIT(b,n) b[(n)>>3]&=~(1<<((n)&7))
#define IS_HBIT(b,n)  (b[(n)>>3]&(1<<((n)&7)))