// Created:09-24-98
// By Jeff Connelly

// Huffman compression.

// Original code: ORIGSRC\CODHUFF.C and ORIGSRC\DCODHUFF.C written by
// David Bourgin

// Note: The compiler must have been configured for a stack size of at
//       minimum 20K.

#include "stdafx.h"
#define EXPORTING
#include "comprlib.h"
#include "huffman.h"

#include <string.h>
#include <stdlib.h>

static unsigned char bit_counter_to_write = 0;
static unsigned int val_to_write = 0;

#define dfunc(n)   static int DEBUG_COUNTER = 0; printf ("%s(): %d\n", n, DEBUG_COUNTER++);
#define dend(n)    printf ("End %s()\n", n);

// Writes the value binary-coded into 'bin_val'
static void write_bin_val(t_bin_val bin_val)
{
    dfunc("write_bin_val");
    unsigned char bin_pos, byte_pos;

    byte_pos = (BITS_NB_BIN_VAL(bin_val) + 7) >> 3;
    bin_pos = BITS_NB_BIN_VAL(bin_val) & 7;
    if (bin_pos)
    {
        --byte_pos;
        val_to_write = (val_to_write << bin_pos) | BITS_BIN_VAL(bin_val)
                        [byte_pos];
        bit_counter_to_write += bin_pos;
        if (bit_counter_to_write >= 8)
        {
            bit_counter_to_write -= 8;
            write_byte((unsigned char)
                       (val_to_write >> bit_counter_to_write));
            val_to_write &= ((1 << bit_counter_to_write) - 1);
        }
     }
     while (byte_pos)
     {
         --byte_pos;
         val_to_write = (val_to_write << 8) | BITS_BIN_VAL(bin_val)[byte_pos];
         write_byte((unsigned char)(val_to_write >> bit_counter_to_write));
         val_to_write &= ((1 << bit_counter_to_write) - 1);
     }
     dend("write_bin_val");
}

// Fills the last byte to write with zero values
static void fill_encoding()
{
    dfunc("fill_encoding");
    if (bit_counter_to_write)
        write_byte(val_to_write << (8 - bit_counter_to_write));
    dend("fill_encoding");
}

// Writes the header in the stream of codes
static void write_header (t_bin_val codes_table[257])
{
    dfunc("write_header");
    register unsigned int i, j;

    // Used to send in binary mode via write_bin_val
    t_bin_val bin_val_to_0, bin_val_to_1, bin_val;

    *BITS_BIN_VAL(bin_val_to_0) = 0;
    BITS_NB_BIN_VAL(bin_val_to_0) = 1;
    *BITS_BIN_VAL(bin_val_to_1) = 1;
    BITS_NB_BIN_VAL(bin_val_to_1) = 1;

    for (i = 0, j = 0; j <= 0xFF; j++)
        if (BITS_NB_BIN_VAL(codes_table[j]))
            ++i;

    // From there, 'i' contains the number of bytes of the several non-null
    // occurences to encode.  First part of header specifies the bytes that
    // appear in the source of encoding

    if (i < 32)
    {
        write_bin_val(bin_val_to_0);
        BITS_NB_BIN_VAL(bin_val) = 5;
        *BITS_BIN_VAL(bin_val) = (unsigned char)(i - 1);
        write_bin_val(bin_val);
        BITS_NB_BIN_VAL(bin_val) = 8;
        for (j = 0; j <= 0xFF; j++)
            if BITS_NB_BIN_VAL(codes_table[j])
            {
                *BITS_BIN_VAL(bin_val) = (unsigned char)j;
                write_bin_val(bin_val);
            }
    } else {
        write_bin_val(bin_val_to_1);
        for (j = 0; j <= 0xFF; j++)
            if BITS_NB_BIN_VAL(codes_table[j])
                write_bin_val(bin_val_to_1);
            else
                write_bin_val(bin_val_to_0);
    };
    // Second part of header specifies the encoding of the bytes
    // (fictive or not) that appear in the source of encoding

    for (i = 0; i <= 0x100; i++)
    {
        if (j = BITS_NB_BIN_VAL(codes_table[i]))
            if (j < 33)
            {
                write_bin_val(bin_val_to_0);
                BITS_NB_BIN_VAL(bin_val) = 5;
            } else {
                write_bin_val(bin_val_to_1);
                BITS_NB_BIN_VAL(bin_val) = 8;
            }
            *BITS_BIN_VAL(bin_val) = (unsigned char)(j - 1);
            write_bin_val(bin_val);
            write_bin_val(codes_table[i]);
    }
    dend ("write_header");
}

// Returns a negative, zero or positive integer depending on the weight
// of 'tree2' is less than, equal to, or greater than the weight of 'tree1',
// respectivly.
// static int weight_tree_comp (p_tree* tree1, p_tree* tree2)
static int weight_tree_comp (const void* ptree1, const void* ptree2)
{
	p_tree* tree1 = (p_tree*)ptree1;
	p_tree* tree2 = (p_tree*)ptree2;
    dfunc ("weight_tree_comp");
    return (WEIGHT_OF_TREE(*tree2) ^ WEIGHT_OF_TREE(*tree1)) ?
            ((WEIGHT_OF_TREE(*tree2) < WEIGHT_OF_TREE(*tree1))
             ? -1 : +1) : 0;
    dend ("weight_tree_comp");
}

// supresses the allocation memory for 'tree'
static void suppress_tree (p_tree tree)
{
    dfunc ("suppress_tree");
    if (tree != NULL)
    {
        suppress_tree (LEFTPTR_OF_TREE(tree));
        suppress_tree (RIGHTPTR_OF_TREE(tree));
        free (tree);
    }
    dend ("suppress_tree");
}

// Creates a Huffman encoding tree based on the data from the input stream
static p_tree build_tree_encoding()
{
    dfunc ("build_tree_encoding()");
    register unsigned int i;
    p_tree occurrences_table[257], ptr_fictive_tree;

    // Set up the occurrences number of all bytes to zero
    for (i = 0; i <= 0x100; i++)
    {
        if ((occurrences_table[i] = (p_tree)malloc(sizeof(t_tree))) == NULL)
        {
            for (; i; i--)
                free(occurrences_table[i - 1]);
            EXCEPTION (ERR_MEMORY, "Failed to allocate memory for"
                                   "occurrences table to build tree",
                                   "build_tree_encoding()");
        }
        BYTE_OF_TREE(occurrences_table[i]) = i;
        WEIGHT_OF_TREE(occurrences_table[i]) = 0;
        LEFTPTR_OF_TREE(occurrences_table[i]) = NULL;
        RIGHTPTR_OF_TREE(occurrences_table[i]) = NULL;
    }

    if (!end_of_data())
    {
        while (!end_of_data())
        {
            i = read_byte();
            WEIGHT_OF_TREE(occurrences_table[i])++;
        }
        WEIGHT_OF_TREE(occurrences_table[0x100]) = 1;
        // Sort the occurrences table depending on the weight of each
        // byte.
        (void)qsort(
			(void*)(const void*)occurrences_table,
			257, sizeof(p_tree),
			weight_tree_comp);
			//((int)(*weight_tree_comp)(const void*, const void*)));
        for (i = 0x100; (i != 0) && (!WEIGHT_OF_TREE(occurrences_table[i]));
             i--);
            free(occurrences_table[i]);
        ++i;
        // From here, 'i' gives the number of different bytes with a null
        // occurrence in the input stream.  Look up (i + 1) / 2 times
        // the occurrences table to link the nodes in a unique tree
        while (i > 0)
        {
            if((ptr_fictive_tree = (p_tree)malloc(sizeof(t_tree))) == NULL)
            {
                for (i = 0; i <= 0x100; i++)
                    suppress_tree (occurrences_table[i]);
                EXCEPTION (ERR_MEMORY, "Failed to allocate memory to build"
                                       "fictive tree",
                                       "build_tree_encoding()");
            }
            BYTE_OF_TREE(ptr_fictive_tree) = 257;
            WEIGHT_OF_TREE(ptr_fictive_tree) =
                        WEIGHT_OF_TREE(occurrences_table[--i]);
            LEFTPTR_OF_TREE(ptr_fictive_tree) = occurrences_table[i];
            if (i)
            {
                --i;
                WEIGHT_OF_TREE(ptr_fictive_tree) +=
                            WEIGHT_OF_TREE(occurrences_table[i]);
                RIGHTPTR_OF_TREE(ptr_fictive_tree) = occurrences_table[i];
            } else
                RIGHTPTR_OF_TREE(ptr_fictive_tree) = NULL;
            occurrences_table[i] = ptr_fictive_tree;
            (void)qsort(occurrences_table, i + 1, sizeof(p_tree),
                    weight_tree_comp);
            // Is there another node in the occurrences table? 
            if (i)
                ++i;  // Yes, then takes care to the fictive node
        }
    }
    dend ("build_tree_encoding");
    return (*occurrences_table);
}

static void encode_codes_table (p_tree tree, t_bin_val codes_table[257],
                                t_bin_val* code_val)
{
    dfunc ("encode_codes_table");
    register unsigned int i;
    t_bin_val tmp_code_val;

    if (BYTE_OF_TREE(tree) == 257)
    {
        if (LEFTPTR_OF_TREE(tree) != NULL)
        {
            // The sub-trees on left begin with a bit with value 1
            tmp_code_val = *code_val;
            for (i = 31; i > 0; i--)
                BITS_BIN_VAL(*code_val)[i] =
                    (BITS_BIN_VAL(*code_val)[i] << 1) |
                    (BITS_BIN_VAL(*code_val)[i - 1] >> 7);
            *BITS_BIN_VAL(*code_val) = (*BITS_BIN_VAL(*code_val) << 1) | 1;
            BITS_NB_BIN_VAL(*code_val)++;
            encode_codes_table (LEFTPTR_OF_TREE(tree), codes_table,
                                code_val);
            *code_val = tmp_code_val;
        };

        if (RIGHTPTR_OF_TREE(tree) != NULL)
        {
            tmp_code_val = *code_val;
            for (i = 31; i > 0; i--)
                BITS_BIN_VAL(*code_val)[i] = (BITS_BIN_VAL(*code_val)[i]
                    << 1) | (BITS_BIN_VAL(*code_val)[i - 1] >> 7);
            *BITS_BIN_VAL(*code_val) <<= 1;
            BITS_NB_BIN_VAL(*code_val)++;
            encode_codes_table(RIGHTPTR_OF_TREE(tree), codes_table, code_val);
            *code_val = tmp_code_val;
        };
    } else
        codes_table[BYTE_OF_TREE(tree)] = *code_val;
    dend ("encode_codes_table");
}

// Stores the encoding tree as a binary encoding table to speed up the
// access by caling encode_codes_table
static void create_codes_table(p_tree tree, t_bin_val codes_table[257])
{
    dfunc ("create_codes_table");
    t_bin_val code_val;

    (void)memset((char*)&code_val, 0, sizeof(code_val));
    (void)memset((char*)codes_table, 0, 257 * sizeof(*codes_table));
    encode_codes_table(tree, codes_table, &code_val);
    dend ("create_codes_table");
}

// Finally, the main encoding function!
void EXPORT  huffman_encode ()
{
    dfunc ("huffman_encode");
    p_tree tree;
    t_bin_val encoding_table[257];
    unsigned char byte_read;

    if (!end_of_data())         // Only output data if there is input data
    {
        // Build the tree
        tree = build_tree_encoding();
        create_codes_table(tree, encoding_table);   
        suppress_tree (tree);
        write_header(encoding_table);       // Write definition of encoding
        beginning_of_data();                // Actual compression begins
        while (!end_of_data())
        {
            byte_read = read_byte();
            write_bin_val(encoding_table[byte_read]);
        }
        write_bin_val(encoding_table[256]);     // Code of end of encoding
        fill_encoding();                        // Fill last byte, if any
    }
    dend ("huffman_encode");
}