/*
  "Fire Emblem: Fuuin No Tsurugi" LZ compressor
  By Tristan Wilkinson

  Used for compressing the graphics that needed to be changed.

  Last modified: 26/03/2005
*/

/* Preprocessor */
#include <stdio.h>
#include <stdlib.h>

#include "gcomp.h"


/* Function Definitions */
void findlongrun(unsigned int areastart, unsigned int areaend);


/* Globals */
unsigned	char    *sourcebuff;
unsigned	int		 dataend;
unsigned	int		 datastart;
			CHAIN	*first;


/* Main */
int main(int argc, char* argv[])
{
	/* Locals */
	char	 index;
	unsigned char	 indexmask;
	char	 temp;
	CHAIN	*blockstart;
	CHAIN	*curlink;
	CHAIN	 final;
	FILE    *outfile;
	FILE    *sourcefile;
	int		 i;
	int      sourcelen;

	if(argc != 3)
	{
		fprintf(stderr, "gcomp usage:\n\tgcomp sourcefile destfile\n");
		return 1;
	}

	//open source file
	sourcefile = fopen(argv[1], "rb");
	if(!sourcefile)
	{
		fprintf(stderr, "Source file, %s, could not be opened.\n", argv[1]);
		return 1;
	}


	//get length of source
	fseek(sourcefile, 0, SEEK_END);
	sourcelen = ftell(sourcefile);
	fseek(sourcefile, 0, SEEK_SET);

	//prep source buffer
	sourcebuff = (unsigned char*)malloc(sourcelen);
	if(!sourcebuff)
	{
		fprintf(stderr, "Not enough room to store source file. Quitting...\n");
		fclose(sourcefile);
		return 1;
	}

	//read in source
	fread(sourcebuff, 1, sourcelen, sourcefile);

	//close file
	fclose(sourcefile);

	//open output file
	outfile = fopen(argv[2], "wb");
	if(!outfile)
	{
		fprintf(stderr, "Output file, %s, could not be opened.\n", argv[2]);
		return 1;
	}

	//initialize chain
	final.length = 0;
	final.offset = 0xFFFFFFFF;
	final.next = 0;

	first = &final;

	datastart = 0;
	dataend = sourcelen - 1;

	findlongrun(datastart, dataend);


	index = 0x00;
	indexmask = 0x80;
	curlink = first;
	blockstart = first;

	//write out
	do
	{
		//check length (1 = literal)
		if(curlink->length > 1)
			index |= indexmask;

		indexmask >>= 1;

		if(!indexmask)		//one block done
		{
			//write index
			fputc(index, outfile);
			
			//reset index
			index = 0x00;
			indexmask = 0x80;

			//brink back curlink
			curlink = blockstart;

			//write out block data
			for(i = 0; i < 8; i++)
			{
				if(curlink->length == 1)	//literal
					fputc(sourcebuff[curlink->offset], outfile);
				else						//diction
				{
					temp = (char)(curlink->length - 3) << 4;
					temp += (char)(((curlink->diff - 1) & 0x0F00) >> 8);
					fputc(temp, outfile);
					temp = (char)(curlink->diff - 1) & 0x00FF;
					fputc(temp, outfile);
				}
				curlink = curlink->next;
			}
			blockstart = curlink;

			//if this is the end, skip the next bit
			if(curlink->offset == 0xFFFFFFFF)
				goto fill;
		}
		else
			curlink = curlink->next;

	}
	while(curlink->offset != 0xFFFFFFFF);

	//deal with any leftovers
	fputc(index, outfile);

	//brink back curlink
	curlink = blockstart;

	do
	{
		if(curlink->length == 1)	//literal
			fputc(sourcebuff[curlink->offset], outfile);
		else						//diction
		{
			temp = (char)(curlink->length - 3) << 4;
			temp += (char)(((curlink->diff - 1) & 0x0F00) >> 8);
			fputc(temp, outfile);
			temp = (char)(curlink->diff - 1) & 0x00FF;
			fputc(temp, outfile);
		}
		curlink = curlink->next;
	}
	while(curlink->offset != 0xFFFFFFFF);

fill:

	while(ftell(outfile) % 0x04)
		fputc(0, outfile);

	fclose(outfile);


}

void findlongrun(unsigned int areastart, unsigned int areaend)
{
	/* Locals */
				CHAIN	 curlongest;
				CHAIN	*newlink;
				CHAIN	*temp1 = 0;
				CHAIN	*temp2 = 0;
	unsigned	char	 curchar;
	unsigned	int		 curlen = 0;
	unsigned	int		 curoff;
	unsigned	int		 slidingoff;

	if(areaend < areastart)
	{
		//WTF?!?
		return;
	}

	if((areaend - areastart) < MIN_ENT_LENGTH)	//if there's less room than we're willing to compress
	{
		goto isuck;
		return;
	}

	//init chain
	curlongest.length = 0;
	curlongest.next = 0;
	curlongest.offset = 0;

	//find long run
	curoff = areastart;
	while(curoff < (areaend - MIN_ENT_LENGTH))
	{
		curchar = sourcebuff[curoff];
		//find longest match for this character
		slidingoff = ((curoff - MAX_SLIDE_BACK) > curoff) ? datastart : curoff - MAX_SLIDE_BACK;
		while(slidingoff < curoff)
		{
			curlen = 0;
			while(((curoff + curlen) < areaend) && (sourcebuff[slidingoff + curlen] == sourcebuff[curoff + curlen]) && (curlen < MAX_ENT_LENGTH))
				curlen++;
			if((curlen > curlongest.length) && (curlen > MIN_ENT_LENGTH))
			{
				if(curoff - slidingoff > 1)
				{
					//replace current longest
					curlongest.length = curlen;
					curlongest.offset = curoff;
					curlongest.diff = curoff - slidingoff;
				}
				else
					curlen = 0;
			}

			if(curlen == MAX_ENT_LENGTH)	//we have as long as we can handle
				break;						//so break out
			slidingoff++;
		}
		if(curlen == MAX_ENT_LENGTH)		//and again
			break;
		//next
		curoff++;
	}

	//add to chain
	if(curlongest.length)	//we got a match
	{
		newlink = (CHAIN*)malloc(sizeof(CHAIN));
		newlink->length = curlongest.length;
		newlink->offset = curlongest.offset;
		newlink->diff = curlongest.diff;

		//find location in chain
		temp1 = first;
		while(newlink->offset > temp1->offset)
		{
			temp2 = temp1;
			temp1 = temp1->next;
		}

		//temp1 will be the following link
		newlink->next = temp1;

		//temp2 will be the previous link, if it exists
		if(temp2)
			temp2->next = newlink;
		else			//this is a new first link
			first = newlink;
	}
	else	//no matches for the whole area :(
	{
isuck:
		//prepare chain for literal (last byte in area)
		newlink = (CHAIN*)malloc(sizeof(CHAIN));
		newlink->length = 1;
		newlink->offset = areaend;
		newlink->diff = 0;


		//find location in chain
		temp1 = first;
		while(newlink->offset > temp1->offset)
		{
			temp2 = temp1;
			temp1 = temp1->next;
		}

		//temp1 will be the following link
		newlink->next = temp1;

		//now that we're here, append all the previous bytes inthis area to the front
		curoff = areaend - 1;
		while((curoff >= areastart) && !(curoff > areaend))
		{
			temp1 = newlink;
			newlink = (CHAIN*)malloc(sizeof(CHAIN));
			newlink->length = 1;
			newlink->offset = curoff;
			newlink->diff = 0;

			newlink->next = temp1;

			curoff--;
		}

		//temp2 will be the previous link, if it exists
		if(temp2)
			temp2->next = newlink;
		else			//this is a new first link
			first = newlink;

		return;		//nothing left to have any matches in
	}
	//call self in top
	if(areastart != newlink->offset)
	{
		findlongrun(areastart, newlink->offset - 1);
	}
	//call self in bottom
	if(areaend != (newlink->offset + newlink->length - 1))
	{
		findlongrun(newlink->offset + newlink->length, areaend);
	}
	//return
}