/***********************************************************
	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 unsigned long encoded_origsize;

static struct encode_option encode_define[2] = {
#if defined(__STDC__) || defined(AIX)
/* 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(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;
	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(void)
{
	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(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] & 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(void)
{
	int n;

	remainder--;
	if (++pos == dicsiz * 2) {
		bcopy(&text[dicsiz], &text[0], dicsiz + maxmatch);
		n = fread_crc(&text[dicsiz + maxmatch], dicsiz, infile);
		encoded_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;
	origsize = interface -> original;
	compsize = count = 0L;
	crc = 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);
	encoded_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 = encoded_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];
	crc = 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);
}