import os,profile
from stat import *
from sys import argv
from struct import pack

def readfile(name):
	fd = open(name, "rb")
	contents = fd.read()
	fd.close()
	return os.stat(name)[ST_SIZE], contents

def writefile(name, contents):
	fd = open(name, "wb")
	fd.write(contents)
	fd.close()

class lz77_gba:
	MAXWINDOW = 4096
	MATCHLEN = 18
	def search(self, window_dict, string, index):
		substr = string[index:index+3]
		if substr in window_dict:
			longest_length = 0
			longest_index = index
			for f in window_dict[substr]:
				start = f + 3
				count = 3
				pos = index + 3
				while pos < len(string) and count < self.MATCHLEN and string[start] == string[pos]:
					start += 1
					pos += 1
					count += 1
				if count > longest_length:
					longest_length = count
					longest_index = f
		else:
			return (index, 1)
		return (longest_index, longest_length)
	def compress(self, z):
		'''the actual lz77 gba compressor

		   returns compressed string'''
		window_dict = {}
		flags = 0
		index = 0
		lenz = len(z)
		#revstdrange = range(self.MATCHLEN,2,-1)
		#stdrange = range(3,self.MATCHLEN)
		#tag header as lz77 compressed along with size
		compressed = pack("<I", (lenz<<8)+0x10)
		flags = 0
		lastchunk = ""
		if index < lenz:
			ormask = 256
			while index < lenz:
				ormask >>= 1
				if ormask == 0:
					ormask = 128
					#append to the final compressed string once we
					#have the flags done for this chunk
					compressed += chr(flags)
					compressed += lastchunk
					flags = 0
					lastchunk = ""
				if index + 3 <= lenz:
					rindex, rlength = self.search(window_dict, z, index)
				else:
					rindex, rlength = index, 1
				if rlength > 2:
					flags |= ormask
					displacement = index - rindex - 1
					#pack compression tag
					cvalue = ((displacement & 0xff) << 8) | \
								(displacement >> 8) | \
								((rlength - 3) << 4)
					lastchunk += pack("<h", cvalue) 
				else:
					lastchunk += z[index]
					#rest rlength, since the match string was too short
					#for compression, so we did a byte (ie, one) copy
					rlength = 1
				for f in range(rlength):
					start = index - self.MAXWINDOW
					#only remove outside-of-window stuff
					if start >= 0:
						substr = z[start:start+3]
						#print "<", substr, start
						window_dict[z[start:start+3]].pop(0)
					start = index - 1
					#only add if the string start is in the window
					if start >= 0 and start+3 <= lenz:
						substr = z[start:start+3]
						if substr in window_dict:
							window_dict[substr].append(start)
						else:
							window_dict[substr] = [start]
						#print ">", substr, ",", window_dict[substr]
					index += 1
		#add partial flag and chunk
		compressed += chr(flags)
		compressed += lastchunk
		data = len(compressed)
		#and word align the size
		newlength = (data + 3) & ~3
		while data < newlength:
			compressed += "\0"
			data += 1
		return compressed

if __name__ == "__main__":
	if len(argv) == 3:
		size, contents = readfile(argv[1])
		writefile(argv[2], lz77_gba().compress(contents))