#include "freeze.h"
#include "lz.h"

/*----------------------------------------------------------------------*/
/*                                                                      */
/*                          LZSS ENCODING                               */
/*                                                                      */
/*----------------------------------------------------------------------*/

uc_t    text_buf[N2 + F2 - 1];          /* cyclic buffer with an overlay */
int     match_position, match_length;   /* current characteristics of a
						matched pattern */
int     chain_length;                   /* max_chain_length ==
						CHAIN_THRESHOLD / greedy */


/*      next[N+1..] is used as hash table,
	the rest of next is a link down,
	prev is a link up.
*/

hash_t             prev[N2 + 1];

#ifndef __XENIX__
#ifdef __TURBOC__
us_t huge * next = (us_t huge *) NULL;
#else  /* __TURBOC__ */
us_t next[array_size];       /* a VERY large array :-) */
#endif /* __TURBOC__ */
#else  /* __XENIX__ */
#if parts == 2
us_t next0[32768L], next1[8193];
#else
us_t next0[32768L], next1[32768L], next2[8193];
#endif  /* parts */

/* A list of `next's parts */

us_t *next[parts] = {
next0, next1
#if parts != 2          /* was: parts > 2. Doesn't work on X286 cpp */
,next2
#endif
};
#endif  /* __XENIX__ */

#ifdef GATHER_STAT
long node_matches, node_compares, node_prolongations;
#endif  /* GATHER_STAT */

/* Initialize the data structures and allocate memory, if needed.
	Although there is no more trees in the LZ algorithm
	implementation, routine name is kept intact :-)
*/

void InitTree ()
{
	hash_t i;
#ifdef GATHER_STAT
	node_matches = node_compares = node_prolongations = 0;
#endif  /* GATHER_STAT */

#ifdef __TURBOC__
	if (!next && (next = (us_t huge *) farmalloc(
		(ul_t)array_size * sizeof(us_t))) == NULL) {

		fprintf(stderr, "Not enough memory (%luK wanted)\n",
			(ul_t)array_size * sizeof(us_t) / 1024);
		exit(3);
	}
#endif  /* __TURBOC__ */

	for (i = N2 + 1; i < array_size; i++ )
		nextof(i) = NIL;
	for (i = 0; i < sizeof(prev)/sizeof(*prev); i++ )
		prev[i] = NIL;
	switch (greedy) {
	case 0:
		chain_length = CHAIN_THRESHOLD;
		break;
	case 1:
		chain_length = 3;
		break;
	default:
		chain_length = 1;
	}
}

/* Get the longest (longer than `match_length' when entering in subroutine)
	nearest match of the string beginning in text_buf[r]
	to the cyclic buffer. Result (length & position) is returned
	in correspondent global variables (`match_length' &
	`match_position'). Unchanged `match_length' denotes failure and
	`match_position' contains garbage !!
	In order to achieve faster operation, `match_length' is shifted
	down to F2.
*/

#ifndef FAST
void get_next_match (r)
	int r;
{
	register int p = r;
	register int m;
	register uc_t lastbyte;
	register uc_t  *key FIX_SI, *pattern FIX_DI;
	int     chain_count = chain_length;

#ifdef GATHER_STAT
	node_matches++;
#endif

	key = text_buf + r + F2;
	match_length -= F2;

	for(;chain_count--;) {

		lastbyte = key[match_length];

		do {
			pattern = text_buf + match_length + F2;

			do {
				if ((p = nextof(p)) == NIL) {
					match_length += F2;
					match_position = ((r - match_position) & (N2 - 1)) - 1;
					return;
				}
			} while (pattern[p] != lastbyte);

			pattern = text_buf + p + F2;

#ifdef GATHER_STAT
		node_compares++;
#endif

			for (m = -F2; key[m] == pattern[m] && ++m < 0;);

		} while (m < match_length);

		if (m == 0) {

/* There are two equal F-char sequences, the oldest one must be
	deleted from the list.
*/

#ifdef DEBUG
	if (verbose)
		fprintf(stderr, "Replacing node: %d -> %d\n", p, r);
#endif
			nextof(prev[p]) = nextof(p);
			prev[nextof(p)] = prev[p];
			prev[p] = NIL;  /* remove p, it is further than r */
			match_length = F2;
			match_position = ((r - p) & (N2 - 1)) - 1;
			return;
		}

		match_length = m;       /* remember new results */
		match_position = p;

#ifdef GATHER_STAT
		node_prolongations++;
#endif
	}

	/* chain length exceeded */

	match_length += F2;
	match_position = ((r - match_position) & (N2 - 1)) - 1;
}
#endif