long __regargs	memwrite(char *,long);
void		compexit(void);
long		compinit(void);
long __regargs	compfiles(unsigned char *,long,unsigned char *,long);
long		compress(void);
void __regargs	output(long);
void		cl_block(void);
void		cl_hash(long);

#define BITS 12

#if BITS == 16
#	define HSIZE	69001 
#endif
#if BITS == 15
#	define HSIZE	35023 
#endif
#if BITS == 14
#	define HSIZE	18013 
#endif
#if BITS == 13
#	define HSIZE	9001 
#endif
#if BITS <= 12
#	define HSIZE	5003 
#endif

#define BLOCK_MASK	0x80
#define INIT_BITS	9 
#define htabof(i)	htab[i]
#define codetabof(i)	codetab[i]
#define MAXCODE(n_bits)	((1 << (n_bits)) - 1)
#define CHECK_GAP	10000
#define FIRST		257 
#define CLEAR		256 

#define myfgetc()	(reallyread++ >= watermark) ? EOF : *sect++
#define absmin(a,b)	((a > b) ? b : a)

long n_bits,maxcode,*htab,hsize,free_ent,clear_flg,ratio,checkpoint,offset,in_count,bytes_out,reallywritten,watermark,buffsize,reallyread;

unsigned char *buffstart,*sect;
unsigned short *codetab;

char buf[BITS];

const unsigned char lmask[9] = {0xFF,0xFE,0xFC,0xF8,0xF0,0xE0,0xC0,0x80,0x00};
const unsigned char rmask[9] = {0x00,0x01,0x03,0x07,0x0F,0x1F,0x3F,0x7F,0xFF};

long __regargs
memwrite(mem,size)
register char *mem;
register long size;
{
	register long byteswritten = 0;

	while(size-- > 0)
	{
		if(reallywritten++ < buffsize)
		{
			*buffstart++ = *mem++;
			byteswritten++;
		}
		else
			return(byteswritten);
	}

	return(byteswritten);
}

void
compexit()
{
	if(htab)
		FreeMem(htab,HSIZE * sizeof(long));

	if(codetab)
		FreeMem(codetab,HSIZE * sizeof(unsigned short));

	htab = NULL;
	codetab = NULL;
}

long
compinit()
{
	if(!(htab = (long *)AllocMem(HSIZE * sizeof(long),0)))
		return(FALSE);

	if(!(codetab = (unsigned short *)AllocMem(HSIZE * sizeof(unsigned short),0)))
	{
		FreeMem(htab,HSIZE * sizeof(long));

		htab = NULL;

		return(FALSE);
	}

	return(TRUE);
}

void __regargs
output(code)
long code;
{
	long r_off = offset, bits = n_bits;
	register char *bp = buf;

	if(code >= 0)
	{
		bp += (r_off >> 3);
		r_off &= 7;

		*bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];
		bp++;

		bits -= (8 - r_off);
		code >>= 8 - r_off;

		if(bits >= 8)
		{
			*bp++ = code;
			code >>= 8;
			bits -= 8;
		}

		if(bits)
			*bp = code;

		offset += n_bits;

		if(offset == (n_bits << 3))
		{
			bp = buf;
			bits = n_bits;
			bytes_out += bits;

			do
			{
				if(reallywritten++ < buffsize)
					*buffstart++ = *bp++;
			}
			while(--bits);

			offset = 0;
		}

		if(free_ent > maxcode || (clear_flg > 0))
		{
			if(offset > 0)
			{
				memwrite(buf,n_bits);
				bytes_out += n_bits;
			}

			offset = 0;

			if(clear_flg)
			{
				maxcode = MAXCODE(n_bits = INIT_BITS);
				clear_flg = 0;
			}
			else
			{
				n_bits++;

				if(n_bits == BITS)
					maxcode = (1 << BITS);
				else
					maxcode = MAXCODE(n_bits);
			}
		}
	}
	else
	{
		if(offset > 0)
			memwrite(buf,(offset + 7) / 8);

		bytes_out += (offset + 7) / 8;
		offset = 0;
	}
}

void
cl_block()
{ 
	register long rat;

	checkpoint = in_count + CHECK_GAP;

	if(in_count > 0x007FFFFF)
	{
		rat = bytes_out >> 8;

		if(rat == 0)
			rat = 0x7FFFFFFF;
		else
			rat = in_count /rat;
	}
	else
		rat = (in_count << 8) / bytes_out; 

	if(rat > ratio)
		ratio = rat;
	else
	{
		ratio = 0;

		cl_hash((long)hsize);

		free_ent = FIRST;
		clear_flg = 1;

		output((long)CLEAR);
	}
}

void
cl_hash(hashsize) 
long hashsize;
{
	register long *htab_p = &htab[hashsize],i;
	register unsigned short j;

	i = hashsize - 16;

	do
	{
		for(j = 16 ; j > 0 ; j--)
			*(htab_p - j) = -1;

		htab_p -= 16;
	}
	while((i -= 16) >= 0);

	for(i += 16 ; i > 0 ; i--)
		*--htab_p = -1;
}

long __regargs
compfiles(from,sectsize,to,maxsize)
unsigned char *from,*to;
long sectsize,maxsize;
{
	sect		= from;
	watermark	= sectsize;
	buffstart	= to;
	buffsize	= maxsize;
	reallywritten	= 0;
	reallyread	= 0;

	hsize		= HSIZE;
	free_ent	= 0;
	clear_flg	= 0;
	ratio		= 0;
	checkpoint	= CHECK_GAP;
	in_count	= 1; 

	if(sectsize < (1 << 12))
		hsize = absmin(5003, HSIZE);
	else if(sectsize < (1 << 13))
		hsize = absmin(9001, HSIZE);
	else if(sectsize < (1 << 14))
		hsize = absmin(18013, HSIZE);
	else if(sectsize < (1 << 15))
		hsize = absmin(35023, HSIZE);
	else if(sectsize < 47000)
		hsize = absmin(50021, HSIZE);

	compress();

	return(reallywritten);
}

long
compress()
{
	long fcode,i = 0,c,ent,disp,hsize_reg,hshift = 0;

	offset		= 0;
	bytes_out	= 3; 
	clear_flg	= 0;
	ratio		= 0;
	in_count	= 1;

	checkpoint = CHECK_GAP;
	maxcode = MAXCODE(n_bits = INIT_BITS);

	free_ent = ((BLOCK_MASK) ? FIRST : 256);

	ent = myfgetc();

	for(fcode = (long)hsize ; fcode < 65536L ; fcode *= 2L)
		hshift++;

	hshift = 8 - hshift; 
	hsize_reg = hsize;

	cl_hash((long)hsize_reg); 

	while((c = myfgetc()) != EOF)
	{
		in_count++;

		fcode = (long)(((long) c << BITS) + ent);

		i = ((c << hshift) ^ ent); 

		if(htabof(i) == fcode)
		{
			ent = codetabof(i);
			continue;
		}
		else
			if((long)htabof(i) < 0) 
				goto nomatch;

		disp = hsize_reg - i; 

		if(i == 0)
			disp = 1;

probe:		if((i -= disp) < 0)
			i += hsize_reg;

		if(htabof(i) == fcode)
		{
			ent = codetabof(i);
			continue;
		}

		if((long)htabof(i) > 0)
			goto probe;

nomatch:	output((long)ent);

		ent = c;

		if(free_ent < (1 << BITS))
		{
			codetabof(i) = free_ent++; 
			htabof(i) = fcode;
		}
		else
			if((long)in_count >= checkpoint && BLOCK_MASK)
				cl_block();
	}

	output((long)ent);
	output((long)-1);

	return(bytes_out);
}