/**************************************************************
	title   dhuf.c
***************************************************************
    Dynamic Huffman routine
                                                H.Yoshizaki
**************************************************************/
#include <stdio.h>
#include "lharc.h"
#include "slidehuf.h"

#define N_CHAR      (256 + 60 - THRESHOLD + 1)
#define TREESIZE_C  (N_CHAR * 2)
#define TREESIZE_P  (128 * 2)
#define TREESIZE    (TREESIZE_C + TREESIZE_P)
#define ROOT_C      0
#define ROOT_P      TREESIZE_C

unsigned int n_max;

static short child [TREESIZE],
			 parent[TREESIZE],
			 block [TREESIZE],
			 edge  [TREESIZE],
			 stock [TREESIZE],
			 dnode  [TREESIZE / 2];

static unsigned short freq[TREESIZE];

static unsigned short total_p;
static int avail, n1;
static int most_p, nn;
static unsigned long nextcount;

void start_c_dyn(void)
{
    int i, j, f, t;

    n1 = (n_max >= 256 + maxmatch - THRESHOLD + 1) ? 512 : n_max - 1;

    for (i = 0; i < TREESIZE_C; i++)
    {
	stock[i] = i;
	block[i] = 0;
    }

    t = n_max * 2 - 2;
    
    for (i = 0, j = t; i < n_max; i++, j--)
    {
	child[j] = ~i;
	dnode[i] = j;
	block[j] = freq[j] = 1;
    }

    avail = 2;
    edge[1] = n_max - 1;
    i = t;

    while (j >= 0)
    {
	f = freq[j] = freq[i] + freq[i - 1];
	child[j] = i;
	parent[i] = parent[i - 1] = j;
	if (f == freq[j + 1])
	{
	    edge[block[j] = block[j + 1]] = j;
	}
	else
	{
	    edge[block[j] = stock[avail++]] = j;
	}
	i -= 2;
	j--;
    }
}

STATIC void start_p_dyn(void)
{
	freq[ROOT_P] = 1;
	child[ROOT_P] = ~(N_CHAR);
	dnode[N_CHAR] = ROOT_P;
	edge[block[ROOT_P] = stock[avail++]] = ROOT_P;
	most_p = ROOT_P;
	total_p = 0;
	nn = 1 << dicbit;
	nextcount = 64;
}

void decode_start_dyn(void)
{
	n_max = 286;
	maxmatch = MAXMATCH;
	init_getbits();
	start_c_dyn();
	start_p_dyn();
}

STATIC void reconst( int start, int end )
{
    int i, j, k, l, b;
    unsigned int f, g;

    for (i = j = start; i < end; i++)
    {
	if ((k = child[i]) < 0)
	{
	    freq[j] = (freq[i] + 1) / 2;
	    child[j] = k;
	    j++;
	}
	if (edge[b = block[i]] == i) 
	{
	    stock[--avail] = b;
	}
    }

    j--;
    i = end - 1;
    l = end - 2;

    while (i >= start) 
    {
	if (i >= l) 
	{
	    int	t;
	    
	    t = i - l + 1;
	    
	    memmove(freq + i, freq + j, t);
	    memmove(child + i, child + j, t);
	    i -= t;
	    j -= t;
	}

	f = freq[l] + freq[l + 1];
	for (k = start; f < freq[k]; k++)
	    ;

        if (j >= k)
	{
	    int t;

	    t = j - k + 1;
	    
	    memmove(freq + i, freq + j, t);
	    memmove(child + i, child + j, t);
	    i -= t;
	    j -= t;
	}

	freq[i] = f;
	child[i] = l + 1;
	
	i--;
	l -= 2;
    }

    f = 0;

    for (i = start; i < end; i++)
    {
	if ((j = child[i]) < 0)
	    dnode[~j] = i;
	else
	    parent[j] = parent[j - 1] = i;

	if ((g = freq[i]) == f)
	{
	    block[i] = b;
	}
	else
	{
	    edge[b = block[i] = stock[avail++]] = i;
	    f = g;
	}
    }
}

STATIC int swap_inc(int p)
{
    int b, q, r, s;

    b = block[p];

    if ((q = edge[b]) != p)
    {				/* swap for leader */
	r = child[p];
	s = child[q];
	child[p] = s;
	child[q] = r;

	if (r >= 0)
	    parent[r] = parent[r - 1] = q;
	else
	    dnode[~r] = q;

	if (s >= 0)
	    parent[s] = parent[s - 1] = p;
	else
	    dnode[~s] = p;

	p = q;
	goto Adjust;
    }
    else
	if (b == block[p + 1])
	{
	  Adjust:
	    edge[b]++;

	    if (++freq[p] == freq[p - 1])
	    {
		block[p] = block[p - 1];
	    }
	    else
	    {
		edge[block[p] = stock[avail++]] = p; /* create block */
	    }
	}
	else
	    if (++freq[p] == freq[p - 1])
	    {
		stock[--avail] = b; /* delete block */
		block[p] = block[p - 1];
	    }
    return parent[p];
}

STATIC void update_c(int p)
{
    int q;

    if (freq[ROOT_C] == 0x8000)
    {
	reconst(0, n_max * 2 - 1);
    }
    freq[ROOT_C]++;
    q = dnode[p];

    do
    {
	q = swap_inc(q);
    }
    while (q != ROOT_C);
}

STATIC void update_p(int p)
{
    int q;

    if (total_p == 0x8000)
    {
	reconst(ROOT_P, most_p + 1);
	total_p = freq[ROOT_P];
	freq[ROOT_P] = 0xffff;
    }
    q = dnode[p + N_CHAR];
    while (q != ROOT_P)
    {
	q = swap_inc(q);
    }
    total_p++;
}

STATIC void make_new_dnode(int p)
{
    int q, r;

    r = most_p + 1; q = r + 1;
    dnode[~(child[r] = child[most_p])] = r;
    child[q] = ~(p + N_CHAR);
    child[most_p] = q;
    freq[r] = freq[most_p];
    freq[q] = 0;
    block[r] = block[most_p];

    if (most_p == ROOT_P)
    {
	freq[ROOT_P] = 0xffff;
	edge[block[ROOT_P]]++;
    }
    parent[r] = parent[q] = most_p;
    edge[block[q] = stock[avail++]] = dnode[p + N_CHAR] = most_p = q;
    update_p(p);
}

STATIC void encode_c_dyn(int c)
{
    unsigned int bits;
    int p, d, cnt;

    d = c - n1;
    if (d >= 0)
    {
	c = n1;
    }
    cnt = bits = 0;  
    p = dnode[c];
    do
    {
	bits >>= 1;
	if (p & 1)
	{
	    bits |= 0x8000;
	}
	if (++cnt == 16)
	{
	    putcode(16, bits);
	    cnt = bits = 0;
	}
    }
    while ((p = parent[p]) != ROOT_C);

    putcode(cnt, bits);
    if (d >= 0)
	putbits(8, d);
    update_c(c);
}

unsigned short decode_c_dyn(void)
{
    int c;
    short buf, cnt;

    c = child[ROOT_C];
    buf = bitbuf;
    cnt = 0;
    do
    {
	c = child[c - ((buf < 0) ? 1 : 0)];
	buf <<= 1;
	if (++cnt == 16)
	{
	    fillbuf(16);
	    buf = bitbuf; cnt = 0;
	}
    } while (c > 0);
    fillbuf(cnt);
    c = ~c;
    update_c(c);
    if (c == n1)
	c += getbits(8);
    return ((unsigned short)c);
}

unsigned short decode_p_dyn(void)
{
    int c;
    short buf, cnt;

    while (count > nextcount)
    {
	make_new_dnode(nextcount / 64);
	if ((nextcount += 64) >= nn)
	    nextcount = 0xffffffff;
    }
    c = child[ROOT_P];
    buf = bitbuf; cnt = 0;
    while (c > 0)
    {
	c = child[c - ((buf < 0) ? 1 : 0)];
	buf <<= 1;
	if (++cnt == 16)
	{
	    fillbuf(16);
	    buf = bitbuf; cnt = 0;
	}
    }
    fillbuf(cnt);
    c = (~c) - N_CHAR;
    update_p(c);

    return ((unsigned short)((c << 6) + getbits(6)));
}

void output_dyn( int code, unsigned int pos)
{
    encode_c_dyn(code);
    if (code >= 0x100)
    {
	encode_p_st0(pos);
    }
}

void encode_end_dyn(void)
{
    putcode(7, 0);
}
