#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int ofs; /* Offset into data buffer */
	char len; /* Length of data. If 1 then 'ofs' is the data itself, else must be between 3 and 18 inclusive */
} bbrec;

bbrec r[8];
int ri; /* Current record index */
int rd; /* Data byte for 8 record group */

int size; /* File size */
char *f; /* The file */
int i; /* Current index into file */

inline char lookup(short ofs)
{
	return (ofs+i < 0 ? 0 : f[ofs+i]);
}

inline int translate_ofs(int ofs)
{
	/* transalte i-relative offset 'ofs' into a data buffer index */
	return (i+ofs+(4096-18)) & 0xFFF;
}

#define MIN(x,y) ((x) < (y) ? x : y)

int main(int argc,char **argv)
{
	FILE *in;
	FILE *out;
	int long_ofs,long_len;
	int ofs,len;
	int skip;
	if (argc < 3)
	{
		fprintf(stderr,"Usage: BBImplode <infile> <outfile>\n");
		exit(1);
	}
	in = fopen(argv[1],"rb");
	if (in == 0)
	{
		fprintf(stderr,"Unable to open input\n");
		exit(1);
	}
	if (fseek(in,0,SEEK_END) || ((size = ftell(in)) == -1) || fseek(in,0,SEEK_SET))
	{
		fclose(in);
		fprintf(stderr,"Unable to determine file size\n");
		exit(1);
	}
	f = malloc(size+18); /* Overrun space */
	if (f == 0)
	{
		fclose(in);
		fprintf(stderr,"Not enough memory\n");
		exit(1);
	}
	if (fread(f,size,1,in) != 1)
	{
		free(f);
		fclose(in);
		fprintf(stderr,"Error reading file\n");
		exit(1);
	}
	fclose(in);
	out = fopen(argv[2],"wb");
	if (out == 0)
	{
		free(f);
		fprintf(stderr,"Unable to open output\n");
		exit(1);
	}
	i = ri = rd = 0;
	while (i < size)
	{
		/* Search for longest repeating block */
		long_ofs = long_len = 0;
		/* Find out how far we can move forward after each match, by the minimum distance needed to reach the next f[i] */
		for (skip=1;skip<18;skip++)
			if (f[i+skip] == f[i])
				break;
		/* We can now move forward MIN(skip,len) as opposed to 1, since if >=skip chars match we know that the sequence can't possibly start again until ofs+skip */
		for (ofs=MIN(-4096,i-19);ofs<0;ofs+=MIN(skip,len))
		{
			for (len=0;(len<18) && (lookup(ofs+len) == f[i+len]);len++);
			if (len > long_len)
			{
				long_len = len;
				long_ofs = ofs;
				if (long_len == 18)
					break;
			}
			else if (len == 0)
				len = 1; /* Ensure we move forwards at least 1 */
		}
		if (i+long_len > size)
			long_len = size-i; /* Cut down to size if needed */
		if (long_len < 3)
		{
			/* Only output one, incase the next one is the start of a sequence */
			rd |= 1 << ri; /* set 'single item' bit */
			r[ri].len = 1;
			r[ri++].ofs = f[i++];
		}
		else
		{
			r[ri].len = long_len;
			r[ri++].ofs = translate_ofs(long_ofs);
			i+=long_len;
		}
		if (ri == 8)
		{
			fputc(rd,out);
			for (ri=0;ri<8;ri++)
				if (r[ri].len == 1)
					fputc(r[ri].ofs,out);
				else
				{
					fputc(r[ri].ofs & 0xFF,out);
					fputc(((r[ri].ofs & 0xF00) >> 4) + r[ri].len - 3,out);
				}
			ri = rd = 0;
		}
	}
	if (ri > 0)
	{
		fputc(rd,out);
		for (i=0;i<ri;i++)
			if (r[i].len == 1)
				fputc(r[i].ofs,out);
			else
			{
				fputc(r[i].ofs & 0xFF,out);
				fputc(((r[i].ofs & 0xF00) >> 4) + r[i].len - 3,out);
			}
	}
	fclose(out);
	free(f);
	return 0;
}
