#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//-----------------------------------------------------------------------------
#define N			4096
#define F			18
#define THRESHOLD	2
#define	BUF_SIZE	65536
//-----------------------------------------------------------------------------
static int				i, j, k, c, len, r, s;
static int				last_match_length, code_buf_ptr;
static unsigned char	mask;
static char				code_buf[17];
static int				match_position;
static int				match_length;
static int				lson[N+1];
static int				rson[N+257];
static int				dad[N+1];
static unsigned char	text_buf[N+F-1];
static int				flags;
static int				Mode = 0;
//-----------------------------------------------------------------------------
static void				Usage(char *programName);
static int				HandleOptions(int argc, char *argv[]);
static void				lzss_inittree(void);
static void				lzss_insertnode(int r);
static void				lzss_deletenode(int p);
static int				lzss_pack(unsigned char *src, int size, FILE *dst);
static int				lzss_unpack(unsigned char *src, int s, FILE *dst);
//-----------------------------------------------------------------------------
void Usage(char *programName)
{
		printf("Usage:\n%s (-p|-u) input-file output-file\n", programName);
}
//-----------------------------------------------------------------------------
int HandleOptions(int argc, char *argv[])
{
	int	i, firstnonoption=0;

	for (i = 1;i < argc;i++)
	{
		if (argv[i][0] == '-')
		{
			switch (argv[i][1])
		    {
				case '?':
					Usage(argv[0]);
					break;

				case 'h':
				case 'H':
					if (!strcasecmp(argv[i]+1,"help"))
						Usage(argv[0]);
					break;

				case 'p':
					Mode = 0;
					break;

				case 'u':
					Mode = 1;
					break;

				default:
					printf("unknown option %s\n",argv[i]);
					break;
			}
		}
		else {
			firstnonoption = i;
			break;
		}
	}
	return firstnonoption;
}
//-----------------------------------------------------------------------------
int main(int argc,char *argv[])
{
	FILE			*in, *out;
	int				filesize, first_non_option;
	char			*buffer;
	unsigned int	dwResult;
	
	first_non_option = HandleOptions(argc,argv);

	if (((argc - first_non_option)<2)||(first_non_option == 0))
	{
		Usage(argv[0]);
		return 1;
	}

	in = fopen(argv[first_non_option], "rb");
	if (in == NULL)
	{
		printf("%s: File not found !\n", argv[first_non_option]);
		return 1;
	}

	fseek(in, 0, SEEK_END);
	filesize = ftell(in);
	fseek(in, 0, SEEK_SET);
	
	buffer = malloc(filesize);
	if (buffer == NULL)
	{
		printf("Could not allocate memory ! (%d bytes)\n", filesize);
		fclose(in);
		return 1;
	}

	fread(buffer, filesize, 1, in);

	out = fopen(argv[first_non_option+1], "wb");
	if (out == NULL)
	{
		printf("%s: Cannot open file for writing !\n", argv[first_non_option+1]);
		free(buffer);
		fclose(in);
		return 1;
	}
	
	if (Mode)
	{
		dwResult = lzss_unpack(buffer, filesize, out);

		printf("Unpacked %d bytes.\n", dwResult);
	}
	else
	{
		dwResult = lzss_pack(buffer, filesize, out);

		printf("Packed %d bytes into %d bytes. (%d%%)\n", filesize, dwResult, dwResult * 100/filesize);
	}
	
	fclose(in);
	fclose(out);
	free(buffer);
	
	return 0;
}
//-----------------------------------------------------------------------------
static void lzss_inittree(void)
{
	register int x;
	
	memset(lson, 0, sizeof(lson));

	for (x=N+1; x<=N+256; x++)
		rson[x] = N;

	for (x=0; x<N; x++)
		dad[x] = N;
}
//-----------------------------------------------------------------------------
static void lzss_insertnode(int r)
{
	int 	x, p, cmp;
	unsigned char	*key;

	cmp = 1;
	key = &text_buf[r];
	p = N + 1 + key[0];
	rson[r] = lson[r] = N;
	match_length = 0;

	while(1)
	{
		if (cmp >= 0)
		{
			if (rson[p] != N)
				p = rson[p];
			else
			{
				rson[p] = r;
				dad[r] = p;
				return;
			}
		}
		else
		{
			if (lson[p] != N)
				p = lson[p];
			else
			{
				lson[p] = r;
				dad[r] = p;
				return;
			}
		}

		for (x = 1; x < F; x++)
			if ((cmp = key[x] - text_buf[p + x]) != 0)
				break;

		if (x > match_length)
		{
			match_position = p;
			if ((match_length = x) >= F)
				break;
		}
	}

	dad[r] = dad[p];
	lson[r] = lson[p];
	rson[r] = rson[p];
	dad[lson[p]] = r;
	dad[rson[p]] = r;

	if (rson[dad[p]] == p)
		rson[dad[p]] = r;
	else
		lson[dad[p]] = r;

	dad[p] = N;
}
//-----------------------------------------------------------------------------
static void lzss_deletenode(int p)
{
	int q;

	if (dad[p] == N)
		return;

	if (rson[p] == N)
		q = lson[p];
	else
	{
		if (lson[p] == N)
			q = rson[p];
		else
		{
			q = lson[p];
			if (rson[q] != N)
			{
				do
				{
					q = rson[q];
				} while (rson[q] != N);

				rson[dad[q]] = lson[q];
				dad[lson[q]] = dad[q];
				lson[q] = lson[p];
				dad[lson[p]] = q;
			}

			rson[q] = rson[p];
			dad[rson[p]] = q;
		}
	}

	dad[q] = dad[p];
	if (rson[dad[p]] == p)
		rson[dad[p]] = q;
	else
		lson[dad[p]] = q;

	dad[p] = N;
}
//-----------------------------------------------------------------------------
int lzss_pack(unsigned char *src, int size, FILE *dst)
{
	int	s = 0, x = 0;

	i = c = len = last_match_length = code_buf[0] = 0;
	code_buf_ptr = mask = 1;
	r = N - F;

	lzss_inittree();

	for (len=0; (len < F) && (size > 0); len++)
    {
		text_buf[r+len] = *(src++);
                size--;
    }

	if (!len)
		goto getout;

	for (i=1; i <= F; i++)
		lzss_insertnode(r-i);

	lzss_insertnode(r);

	do
	{
		if (match_length > len)
			match_length = len;

		if (match_length <= THRESHOLD)
		{
			match_length = 1;
			code_buf[0] |= mask;
			code_buf[code_buf_ptr++] = text_buf[r];
		}
		else
		{
			code_buf[code_buf_ptr++] = (unsigned char)match_position;
			code_buf[code_buf_ptr++] = (unsigned char)(((match_position >> 4) & 0xF0) |
											(match_length - (THRESHOLD + 1)));
		}

		if ((mask <<= 1) == 0)
		{
			for (i=0; i<code_buf_ptr; i++)
			{
				fwrite(&code_buf[i], 1, 1, dst);
				x++;
			}

			code_buf[0] = 0;
			code_buf_ptr = mask = 1;
		}

		last_match_length = match_length;

		for (i=0; (i < last_match_length) && (size > 0); i++)
		{
			c = *(src++);
                        size--;

			lzss_deletenode(s);
			text_buf[s] = c;
			if (s < F-1)
				text_buf[s+N] = c;

			s = (s+1) & (N-1);
			r = (r+1) & (N-1);

			lzss_insertnode(r);
		}

		while (i++ < last_match_length)
		{
			lzss_deletenode(s);
			s = (s+1) & (N-1);
			r = (r+1) & (N-1);
			if (--len)
				lzss_insertnode(r);
		}
	} while (len > 0);

	if (code_buf_ptr > 1)
	{
		for (i=0; i<code_buf_ptr; i++)
		{
			fwrite(&code_buf[i], 1, 1, dst);
			x++;
		}
	}

getout:
	return	x;
}
//-----------------------------------------------------------------------------
int lzss_unpack(unsigned char *src, int s, FILE *dst)
{
	int		size = 0, s2 = 0;

	i = j = k = c = flags = 0;
	r = N-F;

	memset(text_buf, 0, sizeof(text_buf));

	while(1)
	{
		if (size >= s)
			goto getout;

		if (((flags >>= 1) & 256) == 0)
		{
			c = *(src++);
			size++;
			
			flags = c | 0xFF00;
		}

		if (flags & 1)
		{
			c = *(src++);
			size++;
			
			text_buf[r++] = c;
			r &= (N - 1);
			fwrite(&c, 1, 1, dst);
			s2++;
		}
		else
		{
			i = *(src++);
			j = *(src++);
			size += 2;

			i |= ((j & 0xF0) << 4);
			j = (j & 0x0F) + THRESHOLD;

			for (k=0; k <= j; k++)
			{
				c = text_buf[(i + k) & (N - 1)];
				text_buf[r++] = c;
				r &= (N - 1);
				fwrite(&c, 1, 1, dst);
				s2++;
			}
		}
	}

getout:
	return s2;
}
