/**************************************************************
    title   dhuf.c
***************************************************************
    Dynamic Huffman routine
                                                H.Yoshizaki
**************************************************************/
#include <stdio.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],
             node  [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()
{
    int i, j, f;

    n1 = (n_max >= 256 + maxmatch - THRESHOLD + 1) ? 512 : n_max - 1;
    for (i = 0; i < TREESIZE_C; i++) {
        stock[i] = i;
        block[i] = 0;
    }
    for (i = 0, j = n_max * 2 - 2; i < n_max; i++, j--) {
        freq[j] = 1;
        child[j] = ~i;
        node[i] = j;
        block[j] = 1;
    }
    avail = 2;
    edge[1] = n_max - 1;
    i = n_max * 2 - 2;
    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()
{
    freq[ROOT_P] = 1;
    child[ROOT_P] = ~(N_CHAR);
    node[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()
{
    n_max = 286;
    maxmatch = MAXMATCH;
    init_getbits();
    start_c_dyn();
    start_p_dyn();
}

static void reconst( start , end )
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) {
        while (i >= l) {
            freq[i] = freq[j]; 
            child[i] = child[j];
            i--, j--;
        }
        f = freq[l] + freq[l + 1];
        for (k = start; f < freq[k]; k++);
        while(j >= k) {
            freq[i] = freq[j]; 
            child[i] = child[j];
            i--, j--;
        }
        freq[i] = f; 
        child[i] = l + 1;
        i--;
        l -= 2;
    }
    f = 0;
    for (i = start; i < end; i++) {
        if ((j = child[i]) < 0) node[~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(p)
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        node[~r] = q;
        if (s >= 0)    parent[s] = parent[s - 1] = p;
        else        node[~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(p)
int p;
{
    int q;

    if (freq[ROOT_C] == 0x8000) {
        reconst(0, n_max * 2 - 1);
    }
    freq[ROOT_C]++;
    q = node[p];
    do {
        q = swap_inc(q);
    } 
    while (q != ROOT_C);
}

static void update_p(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 = node[p + N_CHAR];
    while (q != ROOT_P) {
        q = swap_inc(q);
    }
    total_p++;
}

static void make_new_node(p)
int p;
{
    int q, r;

    r = most_p + 1; 
    q = r + 1;
    node[~(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++]] = node[p + N_CHAR] = most_p = q;
    update_p(p);
}

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

    d = c - n1;
    if (d >= 0) {
        c = n1;
    }
    cnt = bits = 0;  
    p = node[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()
{
    int c;
    short buf, cnt;

    c = child[ROOT_C];
    buf = bitbuf;
    cnt = 0;
    do {
        c = child[c - (buf < 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 c;
}

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

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

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

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

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