#include <stdio.h>
#include "cpt.h"
#include "masks.h"
#include "huffman.h"

unsigned char getb();
static void cpt_readHuff();
static int cpt_getbits();
void cpt_outch();
static int cpt_getbit();

static unsigned long cpt_newbits;
static int cpt_bitsavail;

/* Lengths is twice the max number of entries. */
static node cpt_Hufftree[512], cpt_LZlength[128], cpt_LZoffs[256];

void cpt_rle_lzh()
{
    int i, block_count;
    unsigned int bptr;
    int Huffchar, LZlength, LZoffs;

    get_bit = cpt_getbit;
    cpt_LZbuff[CIRCSIZE - 3] = 0;
    cpt_LZbuff[CIRCSIZE - 2] = 0;
    cpt_LZbuff[CIRCSIZE - 1] = 0;
    cpt_LZptr = 0;
    while(cpt_outlength != 0) {
	cpt_readHuff(256, cpt_Hufftree);
	cpt_readHuff(64, cpt_LZlength);
	cpt_readHuff(128, cpt_LZoffs);
	block_count = 0;
	cpt_newbits = (*cpt_char++ << 8);
	cpt_newbits = cpt_newbits | *cpt_char++;
	cpt_newbits = cpt_newbits << 16;
	cpt_bitsavail = 16;
	while(block_count < 0x1fff0 && cpt_outlength != 0) {
	    if(cpt_getbit()) {
		Huffchar = gethuffbyte(cpt_Hufftree);
		cpt_outch(Huffchar);
		block_count += 2;
	    } else {
		LZlength = gethuffbyte(cpt_LZlength);
		LZoffs = gethuffbyte(cpt_LZoffs);
		LZoffs = (LZoffs << 6) | cpt_getbits(6);
		bptr = cpt_LZptr - LZoffs;
		while(LZlength-- > 0) {
		    cpt_outch(cpt_LZbuff[bptr++ & (CIRCSIZE - 1)]);
		}
		block_count += 3;
	    }
	}
    }
}

/* Based on unimplod from unzip; difference are noted below. */
typedef struct sf_entry {
    int Value;
    int BitLength;
} sf_entry;

/* See routine LoadTree.  The parameter tree (actually an array and
   two integers) are only used locally in this version and hence locally
   declared.  The parameter nodes has been renamed Hufftree.... */
static void cpt_readHuff(size, Hufftree)
int size;
struct node *Hufftree;
{
    sf_entry tree_entry[256]; /* maximal number of elements */
    int tree_entries;
    int tree_MaxLength; /* finishes local declaration of tree */

    int treeBytes, i, len;  /* declarations from ReadLengths */

    /* declarations from SortLengths */
    sf_entry *ejm1;
    int j;
    sf_entry *entry;
/*  int i already above */
    sf_entry tmp;
    int entries;
    unsigned a, b;

    /* declarations from GenerateTrees */
    int codelen, lvlstart, next, parents;
/*  int i, j already above */
    /* end declarations */

    /* next paraphrased from ReadLengths with adaption for Compactor. */
    treeBytes = *cpt_char++;
    if(size < treeBytes * 2) { /* too many entries, something is wrong! */
	fprintf(stderr, "Bytes is: %d, expected: %d\n", treeBytes, size / 2);
	exit(1);
    }
    i = 0;
    tree_MaxLength = 0;
    tree_entries = 0;
    while(treeBytes-- > 0) { /* adaption for Compactor */
	len = (*cpt_char) >> 4;
	if(len != 0) { /* only if length unequal zero */
	    if(len > tree_MaxLength) {
		tree_MaxLength = len;
	    }
	    tree_entry[tree_entries].Value = i;
	    tree_entry[tree_entries++].BitLength = len;
	}
	i++;
	len = *cpt_char++ & NIBBLEMASK;
	if(len != 0) { /* only if length unequal zero */
	    if(len > tree_MaxLength) {
		tree_MaxLength = len;
	    }
	    tree_entry[tree_entries].Value = i;
	    tree_entry[tree_entries++].BitLength = len;
	}
	i++;
    }

    /* adaption from SortLengths */
    entry = &(tree_entry[0]);
    entries = tree_entries;
    for(i = 0; ++i < entries;) {
	tmp = entry[i];
	b = tmp.BitLength;
	j = i;
	while((j > 0) && ((a = (ejm1 = &(entry[j - 1]))->BitLength) >= b)) {
	    if((a == b) && (ejm1->Value <= tmp.Value)) {
		break;
	    }
	    *(ejm1 + 1) = *ejm1;
	    --j;
	}
	entry[j] = tmp;
    }

    /* Adapted from GenerateTrees */
    i = tree_entries - 1;
    /* starting at the upper end (and reversing loop) because of Compactor */
    lvlstart = next = size * 2 - 1;
    /* slight adaption because of different node format used */
    for(codelen = tree_MaxLength; codelen >= 1; --codelen) {
	while((i >= 0) && (tree_entry[i].BitLength == codelen)) {
	    Hufftree[next].byte = tree_entry[i].Value;
	    Hufftree[next].flag = 1;
	    next--;
	    i--;
	}
	parents = next;
	if(codelen > 1) {
	    /* reversed loop */
	    for(j = lvlstart; j > parents + 1; j-= 2) {
		Hufftree[next].one = &(Hufftree[j]);
		Hufftree[next].zero = &(Hufftree[j - 1]);
		Hufftree[next].flag = 0;
		next--;
	    }
	}
	lvlstart = parents;
    }
    Hufftree[0].one = &(Hufftree[next + 2]);
    Hufftree[0].zero = &(Hufftree[next + 1]);
    Hufftree[0].flag = 0;
}

static int cpt_getbits(num)
unsigned int num;
{
int b = 0, i;

    for(i = 0; i < num; i++) {
	b = (b << 1) | cpt_getbit();
    }
    return b;
}

static int cpt_getbit()
{
int b;

    b = (cpt_newbits >> 31) & 1;
    cpt_bitsavail--;
    if(cpt_bitsavail < 16) {
	cpt_newbits |= (*cpt_char++ << 8);
	cpt_newbits |= *cpt_char++;
	cpt_bitsavail += 16;
    }
    cpt_newbits <<= 1;
    return b;
}

