#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

	//Global
	vector<string> name_list;

	// BMP Structures
	typedef struct
	{
	   unsigned short type;						/* Magic identifier            */
	   unsigned int size;                       /* File size in bytes          */
	   unsigned short reserved1;
	   unsigned short reserved2;
	   unsigned int offset;                     /* Offset to image data, bytes */
	} HEADER;


	typedef struct
	{
	   unsigned int size;               /* Header size in bytes      */
	   int width,height;                /* Width and height of image */
	   unsigned short int planes;       /* Number of colour planes   */
	   unsigned short int bits;         /* Bits per pixel            */
	   unsigned int compression;        /* Compression type          */
	   unsigned int imagesize;          /* Image size in bytes       */
	   int xresolution,yresolution;     /* Pixels per meter          */
	   unsigned int ncolours;           /* Number of colours         */
	   unsigned int importantcolours;   /* Important colours         */
	} INFOHEADER;


	void write_uint(ofstream& ofile, unsigned int uint) 
    {
		ofile.put(uint);
		ofile.put(uint >> 8);
		ofile.put(uint >> 16);
		ofile.put(uint >> 24);
		return;
    }

	void write_ushort(ofstream& ofile, unsigned short ushort) 
    {
		ofile.put(ushort);
		ofile.put(ushort >> 8);
		return;
    }

	string getExtension(const string& file)
	{
		int pos = file.find_last_of(".");
		if (pos > -1)
		{
			string ext = file.substr(pos, file.length() - file.find_last_of(".") + 1);
			return ext;
		}
		else
		{
			return "";
		}
	}

	string removeExtension(const string& file)
	{
		int pos = file.find_last_of(".");
		if (pos > -1)
		{
			string ext = file.substr(0, pos);
			return ext;
		}
		else
		{
			return "";
		}
	}



	// Builds Header (note first 4 bytes are the # of files in this PAK
	// Structure :
	//		Filename - 16 bytes
	//		Size - 4 bytes
	//		Flag - 4 bytes
	//		Offset - 4 bytes
	int BuildHeader(string filename, ofstream &pak_file)
	{
		pak_file.write(filename.c_str(), filename.length());
		
		for (int i = 0; i < (16 - filename.length()); i++)
		{
			pak_file.put(0x00);
		}

		write_uint(pak_file, 0); // Size
		write_uint(pak_file, 0); // Flag
		write_uint(pak_file, 0); // Offset

		return 0;
	}

	int BuildC16(string inFile, ofstream &pak_file, int file_num)
	{
		ifstream c16_file(inFile.c_str());

		if (c16_file.is_open())
		{
			char c16[2048];
			for (int i = 0; i < 1024; i++)
			{
				c16[i] = 0;
			}


			for (int i = 0; i < 1024 && !c16_file.eof(); i++)
			{
				c16[4 * i] = i;
				c16[(4 * i) + 1] = c16_file.get();
				c16[(4 * i) + 2] = c16_file.get();
				c16[(4 * i) + 3] = c16_file.get();
				
				c16_file.get();
			}

			write_ushort(pak_file, 256);

			for(int i = 0; i < 1024; i++)
			{
				pak_file.write(&c16[i], 1);
			}

			int prev_pos = pak_file.tellp();

			// (((Name + Size + Flag + Offset) * (# of file were on + 1)) + 4 for # of files) - (Size + Flag + Offset))
			int size_pos = ((28 * (file_num + 1)) - 8); 

			pak_file.seekp(size_pos);
			write_uint(pak_file, 1024);
			write_uint(pak_file, 0);
			write_uint(pak_file, prev_pos - 1024 - 2); // Last write pos - size - (palette size)
		
			pak_file.seekp(prev_pos);

		}

		c16_file.close();

		return 0;
	}

	int BuildC16(char palette[1024], ofstream &pak_file, int file_num)
	{
			char c16[1024];
			for (int i = 0; i < 1024; i++)
			{
				c16[i] = 0;
			}


			for (int i = 0; i < 256; i++)
			{
				c16[4 * i] = i;
				c16[(4 * i) + 1] = palette[(4 * i)];
				c16[(4 * i) + 2] = palette[(4 * i) + 1];
				c16[(4 * i) + 3] = palette[(4 * i) + 2];
				
			}

			write_ushort(pak_file, 256);

			for(int i = 0; i < 1024; i++)
			{
				pak_file.write(&c16[i], 1);
			}

			int prev_pos = pak_file.tellp();

			// (((Name + Size + Flag + Offset) * (# of file were on + 1)) + 4 for # of files) - (Size + Flag + Offset))
			int size_pos = ((28 * (file_num + 1)) - 8); 

			pak_file.seekp(size_pos);
			write_uint(pak_file, 1024);
			write_uint(pak_file, 0);
			write_uint(pak_file, prev_pos - 1024 - 2); // Last write pos - size - (palette size)
		
			pak_file.seekp(prev_pos);

		return 0;
	}

	int BuildGRP(string inFile, ofstream &pak_file)
	{
		return 0;
	}

	int BuildBMP(string inFile)
	{
 		ifstream BMP(inFile.c_str(), ios::in|ios::binary|ios::ate);
		int size = BMP.tellg();
		BMP.seekg (0, ios::beg);
		

		//Load the header here
		HEADER header;
		BMP.read(reinterpret_cast < char * > (&header.type), sizeof(header.type));
		BMP.read(reinterpret_cast < char * > (&header.size), sizeof(header.size));
		BMP.read(reinterpret_cast < char * > (&header.reserved1), sizeof(header.reserved1));
		BMP.read(reinterpret_cast < char * > (&header.reserved2), sizeof(header.reserved2));
		BMP.read(reinterpret_cast < char * > (&header.offset), sizeof(header.offset));
	 
		INFOHEADER infoheader;	   
		BMP.read(reinterpret_cast < char * > (&infoheader.size), sizeof(infoheader.size));
		BMP.read(reinterpret_cast < char * > (&infoheader.width), sizeof(infoheader.width));
		BMP.read(reinterpret_cast < char * > (&infoheader.height), sizeof(infoheader.height));
		BMP.read(reinterpret_cast < char * > (&infoheader.planes), sizeof(infoheader.planes));
		BMP.read(reinterpret_cast < char * > (&infoheader.bits), sizeof(infoheader.bits));
		BMP.read(reinterpret_cast < char * > (&infoheader.compression), sizeof(infoheader.compression));
		BMP.read(reinterpret_cast < char * > (&infoheader.imagesize), sizeof(infoheader.imagesize));
		BMP.read(reinterpret_cast < char * > (&infoheader.xresolution), sizeof(infoheader.xresolution));
		BMP.read(reinterpret_cast < char * > (&infoheader.yresolution), sizeof(infoheader.yresolution));
		BMP.read(reinterpret_cast < char * > (&infoheader.ncolours), sizeof(infoheader.ncolours));
		BMP.read(reinterpret_cast < char * > (&infoheader.importantcolours), sizeof(infoheader.importantcolours));

		char palette[1024];

		BMP.read(palette, 1024);

		ofstream c16((removeExtension(inFile) + ".c16").c_str(), ios::binary);
		c16.write(palette, 1024);
		c16.close();

		ofstream grp((removeExtension(inFile) + ".grp").c_str(), ios::binary);
		
		write_uint(grp, 0x00);
		write_ushort(grp, infoheader.width);

		if (infoheader.height > 0)
		{
			write_ushort(grp, (infoheader.height));
		}
		else
		{
			write_ushort(grp, (infoheader.height * -1));
		}

		//int left = size - BMP.tellg();
		//char* BMP_data = new char[left];


		//BMP.read(BMP_data, left);
		//for(int i = left - 1; i >= 0; i--)
		//{
		//	grp.write(&BMP_data[i], 1);
		//}


		char c;
		//int i = 0;
		while(!BMP.eof())
		{
			BMP.read(&c, 1);
			grp.write(&c, 1);
		}


		grp.close();
	
		BMP.close();
		return 0;
	}

	// Applies LZSS compression, as well as builds the PAK file
	int CompressAndBuild(string inFile, ofstream &pak_file, int file_num)
	{
		char slidingWindow[0x800];
		int swPos = 0;
		int swSize = 0x800;

		char uncodedInput[0x800];
		int uiPos = 0;
		int uiSize = 0x800;

		char encodedInput[0x800];  // Overkill, but eh, it works...
		int eiPos = 0;
		int eiSize = 0x800;

		int minMatch = 3;
		int maxMatch = 0x111;

		unsigned char flag = 0x00;
		unsigned char flagPos = 0x01;

		int left_over = 0;

		ifstream uncomp_file (inFile.c_str(), ios::in|ios::binary|ios::ate);
		int size = uncomp_file.tellg();
		uncomp_file.seekg (0, ios::beg);

		char* output = new char[size + ((size / 8) + 1)]; // Worse case scenario, we can't compress it at all
		int oPos = 0;

		//Step 1. Initialize the dictionary to a known value.
		for(int i = 0; i < swSize; i++)
		{
			slidingWindow[i] = 0xFF;
		}

		//Step 2. Read an uncoded string that is the length of the maximum allowable match.
		for(int i = 0; i < uiSize && !uncomp_file.eof(); i++)
		{
			uncodedInput[i] = uncomp_file.get();
			left_over++;
		}

		//Step 3. Search for the longest matching string in the dictionary.
		while((left_over - 1) > 0)
		{	

			int match_length = 0;
			int match_pos = -1;

			int i, j = 0;
			i = swPos;

			while(true)
			{
				if (slidingWindow[i % swSize] == uncodedInput[uiPos])
				{
					j = 1;

					while(slidingWindow[ (i + j) % swSize ] == uncodedInput[(uiPos + j) % uiSize])
					{
						if (j >= maxMatch)
						{
							break;
						}
						j++;
					}

					if (match_length < j)
					{
						match_pos = i;
						match_length = j;
					}
				}

				i = (i + 1) % swSize;
				if (i == swPos)
				{
					break;
				}

			}

		//Step 4. If a match is found greater than or equal to the minimum allowable match length:
		//	Step 4a. Write the encoded flag, then the offset and length to the encoded output.
		//	Step 4b. Otherwise, write the uncoded flag and the first uncoded symbol to the encoded output.
		if (match_length >= minMatch)
		{
			if (match_length <= 0x11)
			{
				encodedInput[eiPos++] = ((unsigned char)((match_pos & 0x000F) << 4) | 
					(match_length - (minMatch)));

				encodedInput[eiPos++] = (unsigned char)((match_pos >> 4) & 0x00FF);
			}
			else
			{
				encodedInput[eiPos++] = ((unsigned char)((match_pos & 0x000F) << 4) | 
					(0xF));

				encodedInput[eiPos++] = (unsigned char)((match_pos >> 4) & 0x00FF);

				encodedInput[eiPos++] = (unsigned char)(match_length - 0x12);

			}
		}
		else
		{
			encodedInput[eiPos++] = uncodedInput[uiPos];
			flag |= flagPos;
			match_length = 1;
		}

		if (flagPos == 0x80)
		{
			
			output[oPos++] = flag;

			for(int i = 0; i < eiPos; i++)
			{
				output[oPos++] = encodedInput[i];
			}

			flag = 0;
			flagPos = 0x01;
			eiPos = 0;
		}
		else
		{
			flagPos <<= 1;
		}


		//Step 5. Shift a copy of the symbols written to the encoded output from the unencoded string to the dictionary.
		for(int i = 0; i < match_length; i++)
		{
			slidingWindow[swPos] = uncodedInput[ (uiPos + i) % uiSize];
			swPos = (swPos + 1) % swSize;
			left_over--;
		}


		//Step 6. Read a number of symbols from the uncoded input equal to the number of symbols written in Step 4.
		int a = 0;
		for(; a < match_length && !uncomp_file.eof(); a++)
		{
			uncodedInput[uiPos] = uncomp_file.get();
			uiPos = (uiPos + 1) % uiSize;
			left_over++;
		}

		if (uncomp_file.eof())
		{
			for(; a < match_length; a++)
			{
				uiPos = (uiPos + 1) % uiSize;
			}
		}

		//Step 7. Repeat from Step 3, until all the entire input has been encoded.
		}

		if (eiPos > 0)
		{
			output[oPos++] = flag;

			for(int i = 0; i < eiPos; i++)
			{
				output[oPos++] = encodedInput[i];
			}
		}

		write_uint(pak_file, oPos + 8);
		write_uint(pak_file, size);
		pak_file.write(output, oPos);

		int prev_pos = pak_file.tellp();

		// (((Name + Size + Flag + Offset) * (# of file were on + 1)) + 4 for # of files) - (Size + Flag + Offset))
		int size_pos = ((28 * (file_num + 1)) - 8); 

		pak_file.seekp(size_pos);
		write_uint(pak_file, oPos + 8);
		write_uint(pak_file, 0);
		write_uint(pak_file, prev_pos - oPos - 8); // Last write pos - size - (compressed size + uncompressed size)
	
		pak_file.seekp(prev_pos);
		
		delete[] output;

		uncomp_file.close();

		return 0;
	}

	int main(int argc, char *argv[])
	{
		if (argc != 2)
		{
			cout << "Must specify a file to decompress." << endl;
			return 0;
		}

		string file = argv[1];

		ifstream list(file.c_str());

		vector<string> name_list;

		if (list.is_open())
		{

			char outFile[256];
			
			if (!list.eof())
			{
				
				char outFileFiles[17];

				list.getline(outFile,17);

				while(!list.eof())
				{
					list.getline(outFileFiles, 17);
					name_list.push_back(outFileFiles);
				}
			}

			list.close();

			ofstream pak_file(outFile, ios::binary);
			write_uint(pak_file, name_list.size() - 1);
			
			for(int i = 0; i < name_list.size() - 1; i++)
			{
				BuildHeader(name_list[i], pak_file);
			}
				
			for(int i = 0; i < name_list.size(); i++)
			{
				if (name_list[i] != "")
				{
					if (getExtension(name_list[i]) == ".bmp")
					{
						BuildBMP("leaf.bmp");
					}
					else if (getExtension(name_list[i]) == ".c16")
					{
						BuildC16(name_list[i], pak_file, i);
					}
					else
					{
						CompressAndBuild(name_list[i], pak_file, i);
					}
				}
			}

			

			pak_file.close();
		}

		return 0;
	}