/***********************************************************
    slide.c -- sliding dictionary by Brent's method
***********************************************************/
#include "ar.h"
#include <stdlib.h>
#include <string.h>  /* memmove() */

#define NIL        0
#define HASHMAX 0x1ff3
#define MAX_HASH_VAL (2 * DICSIZ + HASHMAX)

typedef short  node;

static uchar *text, *childcount;
static node pos, matchpos, avail,
            *position, *next = NULL;
static int remainder, matchlen;

#if MAXMATCH <= (UCHAR_MAX + 1)
    static uchar *len;
#else
    static ushort *len;
#endif

static void init_slide(void)
{
    node i;

    if (next == NULL) {
        position   = malloc(DICSIZ * 2 * sizeof(*position));
        len        = malloc(DICSIZ * 2 * sizeof(*len));
        next       = malloc(MAX_HASH_VAL * sizeof(*next));
        if (next == NULL) error("Out of memory.");
    }
    avail = 1;
    for (i = 1; i < DICSIZ * 2 - 1; i++) next[i] = i + 1;
    next[DICSIZ * 2 - 1] = NIL;
    for (i = DICSIZ * 2; i <= MAX_HASH_VAL; i++) next[i] = NIL;
}

int search(int h, int j, int m, int k1)
{
    int p, k, i;

    p = h + DICSIZ * 2;
    while ((p = next[p]) != NIL) {
        k = position[p];
        if (pos - k < DICSIZ) {
            if (len[p] == m) {
                if (k1 == k || memcmp(&text[j], &text[k], m + 1) == 0)
                    break;
            }
        }
    }
    return p;
}

void regist(int h, int j, int m)
{
    int new;

    h += DICSIZ * 2;
    if (avail == NIL) error("Hashing error.");
    new = avail; avail = next[new];
    next[new] = next[h]; next[h] = new;
    position[new] = j;
    len[new] = m;
}

void update(int h, int j, int m, int k1)
{
    int p;

    p = search(h, j, m, k1);
    if (p) {
        position[p] = j;
    } else {
        regist(h, j, m);
    }
}

void encode(void)
{
    int j1, k, m, h, h1, p, matchmax;
    long b;

    matchmax = MAXMATCH;
    text = malloc(DICSIZ * 2 + MAXMATCH);
    if (text == NULL) error("Out of memory.");
    init_slide();  encode_start();
    remainder = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, infile);
    putc('.', stderr);
    matchlen = 0;
    pos = DICSIZ + MAXMATCH;
    while (remainder > 0 && ! unpackable) {
        if (matchmax > remainder)
            matchmax = remainder;
        m = 1; matchlen = 0; h = text[pos]; matchpos = -1;
        do {
            h = (((long)h << 8) + text[pos + m]) % HASHMAX;
            p = search(h, pos, m, matchpos);
            if (p) {
                matchpos = position[p]; matchlen = ++m;
                position[p] = pos;
                h1 = (((long)h << 8) + text[matchpos + m]) % HASHMAX;
                update(h1, matchpos, m, matchpos);
            } else {
                regist(h, pos, m);
            }
        } while (p && m < matchmax);
        if (matchlen >= 2) {
            if (matchlen >= THRESHOLD) {
                output(matchlen + (256 - THRESHOLD), pos - matchpos - 1);
            } else {
                output(text[pos], 0);
                output(text[pos + 1], 0);
            }
            h = text[pos + matchlen]; b = 1L; m = 1;
            for (j1 = pos + matchlen - 1; j1 > pos; j1--) {
                b = (b << 8) % HASHMAX;
                h = (b * text[j1] + h) % HASHMAX;
                update(h, j1, m, -1);
                m++;
            }
            pos += matchlen;
            remainder -= matchlen;
        } else {
            output(text[pos], 0);
            pos++;
            remainder--;
        }
    }
    encode_end();  free(text);
}

void decode(void)
{
    int i, j, k, r, c;
    unsigned long count;

    text = malloc(DICSIZ);
    if (text == NULL) error("Out of memory.");
    decode_start();
    count = 0;  r = 0;
    while (count < origsize) {
        c = decode_c();
        if (c <= UCHAR_MAX) {
            text[r++] = c;
            if (r == DICSIZ) {
                if (outfile != stdout) putc('.', stderr);
                fwrite_crc(text, DICSIZ, outfile);
                r = 0;
            }
            count++;
        } else {
            j = c - (UCHAR_MAX + 1 - THRESHOLD);  count += j;
            i = (r - decode_p() - 1) & (DICSIZ - 1);
            for (k = 0; k < j; k++) {
                c = text[(i + k) & (DICSIZ - 1)];
                text[r++] = c;
                if (r == DICSIZ) {
                    if (outfile != stdout) putc('.', stderr);
                    fwrite_crc(text, DICSIZ, outfile);
                    r = 0;
                }
            }
        }
    }
    if (r != 0) {
        fwrite_crc(text, r, outfile);
        if (outfile != stdout) putc('.', stderr);
    }
    free(text);
}