/***********************************************************
        encode.c -- sliding dictionary with percolating update
***********************************************************/
#include "ar.h"
#include <stdlib.h>
#include <string.h>  /* memmove() */

#define PERCOLATE  1
#define NIL        0
#define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX)

typedef short node;

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

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

static void allocate_memory(void)
{
        if (next != NULL) return;
    text = malloc(DICSIZ * 2 + MAXMATCH);
        level      = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
        childcount = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
        #if PERCOLATE
          position = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*position));
        #else
          position = malloc(DICSIZ * sizeof(*position));
        #endif
        parent     = malloc(DICSIZ * 2 * sizeof(*parent));
        prev       = malloc(DICSIZ * 2 * sizeof(*prev));
        next       = malloc((MAX_HASH_VAL + 1) * sizeof(*next));
        if (next == NULL) error("Out of memory.");
}

static void init_slide(void)
{
        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;
}

#define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2)

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

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

static void makechild(node q, uchar c, node r)
        /* Let r be q's child for character c. */
{
        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]++;
}

void split(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(void)
{
        node q, r, j, t;
        uchar 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 | PERC_FLAG;
                #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] & ~PERC_FLAG;
                }
                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(void)
{
        #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] & ~PERC_FLAG;
        #else
                t = position[r];
        #endif
        if (t >= pos) t -= DICSIZ;
        #if PERCOLATE
                s = t;  q = parent[r];
                while ((u = position[q]) & PERC_FLAG) {
                        u &= ~PERC_FLAG;  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 | PERC_FLAG;
                }
        #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(void)
{
        int n;

        remainder--;
        if (++pos == DICSIZ * 2) {
                memmove(&text[0], &text[DICSIZ], DICSIZ + MAXMATCH);
                n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, infile);
                remainder += n;  pos = DICSIZ;  putc('.', stderr);
        }
        delete_node();  insert_node();
}

void encode(void)
{
        int lastmatchlen;
        node lastmatchpos;

        allocate_memory();  init_slide();  huf_encode_start();
        remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, infile);
        putc('.', stderr);
        matchlen = 0;
        pos = DICSIZ;  insert_node();
        if (matchlen > remainder) matchlen = remainder;
        while (remainder > 0 && ! unpackable) {
                lastmatchlen = matchlen;  lastmatchpos = matchpos;
                get_next_match();
                if (matchlen > remainder) matchlen = remainder;
                if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD)
                        output(text[pos - 1], 0);
                else {
                        output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
                                   (pos - lastmatchpos - 2) & (DICSIZ - 1));
                        while (--lastmatchlen > 0) get_next_match();
                        if (matchlen > remainder) matchlen = remainder;
                }
        }
        huf_encode_end();
}