/***********************************************************
    slide.c -- sliding dictionary with percolating update
***********************************************************/
#include "lharc.h"
#include "slidehuf.h"
#include "intrface.h"

#define PERCOLATE  1
#define NIL        0

node *next = NULL;
int unpackable;
unsigned long origsize, compsize;
unsigned short dicbit;
unsigned short maxmatch;
unsigned long count;
unsigned short loc;
unsigned char *text;
int prev_char;

static struct encode_option encode_define[2] = {
#ifdef __STDC__
    /* lh1 */
    {(void(*)())output_dyn,
     (void(*)())encode_start_fix,
     (void(*)())encode_end_dyn},
    /* lh4, 5 */
    {(void(*)())output_st1,
     (void(*)())encode_start_st1,
     (void(*)())encode_end_st1}
#else
    /* lh1 */
    {(int(*)())output_dyn,
     (int(*)())encode_start_fix,
     (int(*)())encode_end_dyn},
    /* lh4, 5 */
    {(int(*)())output_st1,
     (int(*)())encode_start_st1,
     (int(*)())encode_end_st1}
#endif
};

static struct decode_option decode_define[7] = {
    /* lh1 */
    {decode_c_dyn, decode_p_st0, decode_start_fix},
    /* lh2 */
    {decode_c_dyn, decode_p_dyn, decode_start_dyn},
    /* lh3 */
    {decode_c_st0, decode_p_st0, decode_start_st0},
    /* lh4 */
    {decode_c_st1, decode_p_st1, decode_start_st1},
    /* lh5 */
    {decode_c_st1, decode_p_st1, decode_start_st1},
    /* lzs */
    {decode_c_lzs, decode_p_lzs, decode_start_lzs},
    /* lz5 */
    {decode_c_lz5, decode_p_lz5, decode_start_lz5}
};

static struct encode_option encode_set;
static struct decode_option decode_set;

static node pos, matchpos, avail,
*position, *parent, *prev;
static int remainder, matchlen;
static unsigned char *level, *childcount;
static unsigned short dicsiz;
static unsigned short max_hash_val;
static unsigned short hash1, hash2;

int encode_alloc(method)
int method;
{
    if (method == 1) {
        encode_set = encode_define[0];
        maxmatch = 60;
        dicbit = 12;
    } 
    else {
        encode_set = encode_define[1];
        maxmatch = MAXMATCH;
        dicbit = 13;
    }
    while (1) {
        dicsiz = 1 << dicbit;
        max_hash_val = 3 * dicsiz + (dicsiz / 512 + 1) * UCHAR_MAX;
        text = (unsigned char *)malloc(dicsiz * 2 + maxmatch);
        level = (unsigned char *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*level));
        childcount = (unsigned char *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*childcount));
#if PERCOLATE
        position = (node *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*position));
#else
        position = (node *)malloc(dicsiz * sizeof(*position));
#endif
        parent     = (node *)malloc(dicsiz * 2 * sizeof(*parent));
        prev       = (node *)malloc(dicsiz * 2 * sizeof(*prev));
        next       = (node *)malloc((max_hash_val + 1) * sizeof(*next));
        if (next == NULL || 
            method > 1 && alloc_buf() == NULL) {
            if (next) free(next);
            if (prev) free(prev);
            if (parent) free(parent);
            if (position) free(position);
            if (childcount) free(childcount);
            if (level) free(level);
            if (text) free(text);
        } 
        else {
            break;
        }
        if (--dicbit < 12 )
            /* error(MEMOVRERR, NULL); */
            exit( 207 );
    }
    if (method == 5)
        method = dicbit - 8;
    return method;
}

static void init_slide()
{
    node i;

    for (i = dicsiz; i <= dicsiz + UCHAR_MAX; i++) {
        level[i] = 1;
#if PERCOLATE
        position[i] = NIL;  /* sentinel */
#endif
    }
    for (i = dicsiz; i < dicsiz * 2; i++) parent[i] = NIL;
    avail = 1;
    for (i = 1; i < dicsiz - 1; i++) next[i] = i + 1;
    next[dicsiz - 1] = NIL;
    for (i = dicsiz * 2; i <= max_hash_val; i++) next[i] = NIL;
    hash1 = dicbit - 9;
    hash2 = dicsiz * 2;
}

#define HASH(p, c) ((p) + ((c) << hash1) + hash2)

static /* inline */ node child(q, c)
/* q's child for character c (NIL if not found) */
node q;
unsigned char c;
{
    node r;

    r = next[HASH(q, c)];
    parent[NIL] = q;  /* sentinel */
    while (parent[r] != q) r = next[r];
    return r;
}

static /* inline */ void makechild(q, c, r)
/* Let r be q's child for character c. */
node q;
unsigned char c;
node r;
{
    node h, t;

    h = HASH(q, c);
    t = next[h];  
    next[h] = r;  
    next[r] = t;
    prev[t] = r;  
    prev[r] = h;
    parent[r] = q;  
    childcount[q]++;
}

static /*inline*/ void split(old)
node old;
{
    node new, t;

    new = avail;  
    avail = next[new];  
    childcount[new] = 0;
    t = prev[old];  
    prev[new] = t;  
    next[t] = new;
    t = next[old];  
    next[new] = t;  
    prev[t] = new;
    parent[new] = parent[old];
    level[new] = matchlen;
    position[new] = pos;
    makechild(new, text[matchpos + matchlen], old);
    makechild(new, text[pos + matchlen], pos);
}

static void insert_node()
{
    node q, r, j, t;
    unsigned char c, *t1, *t2;

    if (matchlen >= 4) {
        matchlen--;
        r = (matchpos + 1) | dicsiz;
        while ((q = parent[r]) == NIL) r = next[r];
        while (level[q] >= matchlen) {
            r = q;  
            q = parent[q];
        }
#if PERCOLATE
        t = q;
        while (position[t] < 0) {
            position[t] = pos;  
            t = parent[t];
        }
        if (t < dicsiz) position[t] = pos | SHRT_MIN;
#else
        t = q;
        while (t < dicsiz) {
            position[t] = pos;  
            t = parent[t];
        }
#endif
    } 
    else {
        q = text[pos] + dicsiz;  
        c = text[pos + 1];
        if ((r = child(q, c)) == NIL) {
            makechild(q, c, pos);  
            matchlen = 1;
            return;
        }
        matchlen = 2;
    }
    for ( ; ; ) {
        if (r >= dicsiz) {
            j = maxmatch;  
            matchpos = r;
        } 
        else {
            j = level[r];
            matchpos = position[r] & SHRT_MAX;
        }
        if (matchpos >= pos) matchpos -= dicsiz;
        t1 = &text[pos + matchlen];  
        t2 = &text[matchpos + matchlen];
        while (matchlen < j) {
            if (*t1 != *t2) {  
                split(r);  
                return;  
            }
            matchlen++;  
            t1++;  
            t2++;
        }
        if (matchlen == maxmatch) break;
        position[r] = pos;
        q = r;
        if ((r = child(q, *t1)) == NIL) {
            makechild(q, *t1, pos);  
            return;
        }
        matchlen++;
    }
    t = prev[r];  
    prev[pos] = t;  
    next[t] = pos;
    t = next[r];  
    next[pos] = t;  
    prev[t] = pos;
    parent[pos] = q;  
    parent[r] = NIL;
    next[r] = pos;  /* special use of next[] */
}


static void delete_node()
{
#if PERCOLATE
    node q, r, s, t, u;
#else
    node r, s, t, u;
#endif

    if (parent[pos] == NIL) return;
    r = prev[pos];  
    s = next[pos];
    next[r] = s;  
    prev[s] = r;
    r = parent[pos];  
    parent[pos] = NIL;
    if (r >= dicsiz || --childcount[r] > 1) return;
#if PERCOLATE
    t = position[r] & SHRT_MAX;
#else
    t = position[r];
#endif
    if (t >= pos) t -= dicsiz;
#if PERCOLATE
    s = t;  
    q = parent[r];
    while ((u = position[q]) < 0) {
        u &= SHRT_MAX;  
        if (u >= pos) u -= dicsiz;
        if (u > s) s = u;
        position[q] = (s | dicsiz);  
        q = parent[q];
    }
    if (q < dicsiz) {
        if (u >= pos) u -= dicsiz;
        if (u > s) s = u;
        position[q] = (s | dicsiz) | SHRT_MIN;
    }
#endif
    s = child(r, text[t + level[r]]);
    t = prev[s];  
    u = next[s];
    next[t] = u;  
    prev[u] = t;
    t = prev[r];  
    next[t] = s;  
    prev[s] = t;
    t = next[r];  
    prev[t] = s;  
    next[s] = t;
    parent[s] = parent[r];  
    parent[r] = NIL;
    next[r] = avail;  
    avail = r;
}

/* static */void get_next_match()
{
    int n;

    remainder--;
    if (++pos == dicsiz * 2) {
        bcopy(&text[dicsiz], &text[0], dicsiz + maxmatch);
        n = fread_crc(&text[dicsiz + maxmatch], dicsiz, infile);
        origsize += n;
        remainder += n;  
        pos = dicsiz;
    }
    delete_node();  
    insert_node();
}

void encode(interface)
struct interfacing *interface;
{
    int lastmatchlen, dicsiz1;
    node lastmatchpos;

    infile = interface -> infile;
    outfile = interface -> outfile;
    compsize = count = 0L;
    mcrc = unpackable = 0;
    init_slide();  
    encode_set.encode_start();
    dicsiz1 = dicsiz - 1;
    pos = dicsiz + maxmatch;
    memset(&text[pos], ' ', dicsiz);
    remainder = fread_crc(&text[pos], dicsiz, infile);
    origsize = remainder;
    matchlen = 0;
    insert_node();
    while (remainder > 0 && ! unpackable) {
        lastmatchlen = matchlen;  
        lastmatchpos = matchpos;
        get_next_match();
        if (matchlen > remainder) matchlen = remainder;
        if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
            encode_set.output(text[pos - 1], 0);
            count++;
        } 
        else {
            encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
            (pos - lastmatchpos - 2) & dicsiz1);
            while (--lastmatchlen > 0) {
                get_next_match();
                count++;
            }
            if (matchlen > remainder) matchlen = remainder;
        }
    }
    encode_set.encode_end();
    interface -> packed = compsize;
    interface -> original = origsize;
}

void decode(interface)
struct interfacing *interface;
{
    int i, j, k, c, dicsiz1, offset;

    infile = interface -> infile;
    outfile = interface -> outfile;
    dicbit = interface -> dicbit;
    origsize = interface -> original;
    compsize = interface -> packed;
    decode_set = decode_define[interface -> method - 1];
    mcrc = 0;
    prev_char = -1;
    dicsiz = 1 << dicbit;
    text = (unsigned char *)malloc(dicsiz);
    if (text == NULL)
        /* error(MEMOVRERR, NULL); */
        exit( errno );
    memset(text, ' ', dicsiz);
    decode_set.decode_start();
    dicsiz1 = dicsiz - 1;
    offset = (interface -> method == 6) ? 0x100 - 2 : 0x100 - 3;
    count = 0;  
    loc = 0;
    while (count < origsize) {
        c = decode_set.decode_c();
        if (c <= UCHAR_MAX) {
            text[loc++] = c;
            if (loc == dicsiz) {
                fwrite_crc(text, dicsiz, outfile);
                loc = 0;
            }
            count++;
        } 
        else {
            j = c - offset;
            i = (loc - decode_set.decode_p() - 1) & dicsiz1;
            count += j;
            for (k = 0; k < j; k++) {
                c = text[(i + k) & dicsiz1];
                text[loc++] = c;
                if (loc == dicsiz) {
                    fwrite_crc(text, dicsiz, outfile);
                    loc = 0;
                }
            }
        }
    }
    if (loc != 0) {
        fwrite_crc(text, loc, outfile);
    }
    free(text);
}