/***********************************************************
    maketbl.c -- makes decoding table
***********************************************************/
#include "slidehuf.h"

#if 0
static short c, n, tblsiz, len, depth, maxdepth, avail;
static unsigned short codeword, bit, *tbl;
static unsigned char *blen;

static short mktbl()
{
    short i;

    if (len == depth) {
        while (++c < n)
            if (blen[c] == len) {
                i = codeword;  
                codeword += bit;
                if (codeword > tblsiz) error(BROKENARC, "Bad table (1)");
                while (i < codeword) tbl[i++] = c;
                return c;
            }
        c = -1;  
        len++;  
        bit >>= 1;
    }
    depth++;
    if (depth < maxdepth) {
        (void) mktbl();  
        (void) mktbl();
    } 
    else if (depth > USHRT_BIT) {
        error(BROKENARC, "Bad table (2)");
    } 
    else {
        if ((i = avail++) >= 2 * n - 1) error(BROKENARC, "Bad table (3)");
        left[i] = mktbl();  
        right[i] = mktbl();
        if (codeword >= tblsiz) error(BROKENARC, "Bad table (4)");
        if (depth == maxdepth) tbl[codeword++] = i;
    }
    depth--;
    return i;
}

void make_table(short nchar, unsigned char bitlen[],
short tablebits, unsigned short table[])
{
    n = avail = nchar;  
    blen = bitlen;  
    tbl = table;
    tblsiz = 1U << tablebits;  
    bit = tblsiz / 2;
    maxdepth = tablebits + 1;
    depth = len = 1;  
    c = -1;  
    codeword = 0;
    (void) mktbl();  /* left subtree */
    (void) mktbl();  /* right subtree */
    if (codeword != tblsiz) error(BROKENARC, "Bad table (5)");
}
#else
void make_table(nchar, bitlen, tablebits, table)
short nchar;
unsigned char bitlen[];
short tablebits;
unsigned short table[];
{
    unsigned short count[17];  /* count of bitlen */
    unsigned short weight[17]; /* 0x10000ul >> bitlen */
    unsigned short start[17];  /* first code of bitlen */
    unsigned short total;
    unsigned int i;
    int j, k, l, m, n, avail;
    unsigned short *p;

    avail = nchar;

    /* initialize */
    for (i = 1; i <= 16; i++) {
        count[i] = 0;
        weight[i] = 1 << (16 - i);
    }

    /* count */
    for (i = 0; i < nchar; i++) count[bitlen[i]]++;

    /* calculate first code */
    total = 0;
    for (i = 1; i <= 16; i++) {
        start[i] = total;
        total += weight[i] * count[i];
    }
    if ((total & 0xffff) != 0)
        error("Bad table (5)\n");

    /* shift data for make table. */
    m = 16 - tablebits;
    for (i = 1; i <= tablebits; i++) {
        start[i] >>= m;
        weight[i] >>= m;
    }

    /* initialize */
    j = start[tablebits + 1] >> m;
    k = 1 << tablebits;
    if (j != 0)
        for (i = j; i < k; i++) table[i] = 0;

    /* create table and tree */
    for (j = 0; j < nchar; j++) {
        k = bitlen[j];
        if (k == 0) continue;
        l = start[k] + weight[k];
        if (k <= tablebits) {
            /* code in table */
            for (i = start[k]; i < l; i++) table[i] = j;
        } 
        else {
            /* code not in table */
            p = &table[(i = start[k]) >> m];
            i <<= tablebits;
            n = k - tablebits;
            /* make tree (n length) */
            while (--n >= 0) {
                if (*p == 0) {
                    right[avail] = left[avail] = 0;
                    *p = avail++;
                }
                if (i & 0x8000) p = &right[*p];
                else            p = &left[*p];
                i <<= 1;
            }
            *p = j;
        }
        start[k] = l;
    }
}
#endif