extern void InitTree();

#ifndef BITS
#define BITS    14      /* for 16-bits machines */
#endif

#if BITS < 13
#undef BITS
#define BITS    13      /* 1:1 hash */
#endif

#if BITS > 16
#undef BITS
#define BITS    16      /* 128K hash table, if sizeof(us_t) == 2 */
#endif

/* The following hash-function isn't optimal but it is very fast:

	HASH =      ((first + (second << LEN0) +
		    (third << LEN1)) & ((1L << BITS) - 1);

  The difference of LENs is no more than one bit.
*/

#define LEN0    ((BITS-8)/2)
#define LEN1    (BITS-8)

#define NIL     N2

#if defined(M_XENIX) && !defined(M_I386) && (BITS > 14)
#define __XENIX__
#endif

/* `array_size' is the size of array `next', which contains
	the heads of linked lists and the references to
	next members of these lists.
*/

#define array_size      (N2 + 1 + (1L << BITS))

extern hash_t prev[];
extern int       match_position, match_length, chain_length;

#ifndef __XENIX__
#define nextof(i)       next[i]

#ifdef __TURBOC__
extern us_t huge * next;
#else   /* __TURBOC__ */
extern us_t next[];
#endif  /* __TURBOC__ */

#else   /* __XENIX__ */

/* We divide the array `next' in `parts' which fit into 286's segment */
/* There may be 2 or 3 parts, because BITS <= 16 now */

#define parts (array_size/32768L + 1)
#define nextof(i)       next[(i) >> 15][(i) & 0x7fff]
#if parts == 2
extern us_t next0[], next1[];
#else
extern us_t next0[], next1[], next2[];
#endif  /* parts */

extern us_t *next[];
#endif  /* __XENIX__ */

/* Some defines to eliminate function-call overhead */

/* Deleting of a node `n' from a linked list */

#define DeleteNode(n) \
{\
       nextof(prev[n]) = NIL;\
       prev[n] = NIL;\
}
/* Hash function */

#define hash(p)\
	((hash_t)(p)[0] + ((hash_t)(p)[1] << LEN0) +\
	((hash_t)(p)[2] << LEN1))

#ifdef FASTHASH
#define hashof(p)\
	(((p)[0] != (p)[1] ? hash(p) : hash(p) + hash((p) + 3)) &\
	((1L << BITS) - 1))
#else
#define hashof(p)\
	(hash(p) & ((1L << BITS) - 1))
#endif

/* Inserting of a node `r' into hashed linked list: `r' becomes
	the head of list.
*/

#define InsertNode(r)\
{\
	register hash_t p; register us_t first_son;\
	register uc_t  *key;\
	key = &text_buf[r];\
	p = N2 + 1 + hashof(key);\
	first_son = nextof(p);\
	nextof(r) = first_son;\
	nextof(p) = r;\
	prev[r] = p;\
	prev[first_son] = r;\
}

/* This routine inputs the char from stdin and does some other
	actions depending of this char's presence.
*/

#define Next_Char(N,F)\
if ((c = getchar()) != EOF) {\
	text_buf[s] = c;\
	if (s < F - 1)\
		text_buf[s + N] = c;\
	s = (s + 1) & (N - 1);\
	r = (r + 1) & (N - 1);\
	InsertNode(r);\
	in_count++;\
} else {\
	s = (s + 1) & (N - 1);\
	r = (r + 1) & (N - 1);\
	if (--len) InsertNode(r);\
}

#if defined(__GNUC__)
#if defined(__i386__)
/* Optimizer cannot allocate these registers correctly :( (v1.39) */
#define FIX_SI  asm("si")
#define FIX_DI  asm("di")
#else

/* GNU-style register allocations for other processors are welcome! */

#define FIX_SI
#define FIX_DI
#endif
#else

/* Dummy defines for non-GNU compilers */

#define FIX_SI
#define FIX_DI
#endif

#define CHAIN_THRESHOLD F2

#ifdef  FAST

/* Simple inline replacement for get_next_match; they match almost
literally except return --> goto quote(leave)l. No obfuscations !!
*/

#if defined(__STDC__) || defined (__TURBOC__)
#define LEAVE(num) leave##num
#else
#define quote(x)x
#define LEAVE(num) quote(leave)num
#endif

#define m_l match_length
#define t_b text_buf
#define m_p match_position

#define Get_Next_Match(r,l) {register p=r;register m;register uc_t lb;\
register uc_t *key FIX_SI, *pat FIX_DI;int cc=chain_length;\
key=t_b+r+F2;m_l-=F2;for(;cc--;){lb=key[m_l];do{pat=t_b+m_l+F2;do{\
if((p=nextof(p))==NIL){m_p=((r-m_p)&(N2-1))-1;m_l+=F2;goto LEAVE(l);}\
}while(pat[p]!=lb);pat=t_b+p+F2;for(m= -F2;key[m]==pat[m]&&++m<0;);\
}while(m<m_l);if(m==0){nextof(prev[p])=nextof(p);prev[nextof(p)]=prev[p];\
prev[p]=NIL;m_l=F2;m_p=((r-p)&(N2-1))-1;goto LEAVE(l);}m_l=m;m_p=p;}\
m_p=((r-m_p)&(N2-1))-1;m_l+=F2;LEAVE(l):;}

#else

#define Get_Next_Match(r,l)     get_next_match(r)
extern void get_next_match();

#endif

#ifdef GATHER_STAT
extern long node_matches, node_compares, node_prolongations;
#endif