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

SIZE = 128 * 1024
APACK = 2

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()

def reverse(str):
	rev = ""
	for f in str:
		rev = f + rev
	return rev

def checksum(str):
	sum = 0
	for i in range(128):
		sum += unpack("<I", str[i*128:i*128+4])[0]
	return (sum & 0xffffffff)

class apack:
	def setbit(self, str):
		for f in str:
			if self.ormask == 1:
				self.out += chr(self.flags) + self.lastchunk
				self.ormask = 128
				self.flags = 0
				self.lastchunk = ""
			else:
				self.ormask >>= 1
			if f == "1":
				self.flags |= self.ormask
	def bits(self, value, length):
		str = ""
		for i in range(length):
			if (value&1):
				str += "1"
			else:
				str += "0"
			value >>= 1
		return reverse(str)
	def tobits(self, value):
		str = ""
		while value:
			if (value&1):
				str += "1"
			else:
				str += "0"
			value >>= 1
		return reverse(str)
	def togamma(self, value):
		if value < 2:
			print "Error: Gamma passed %d" % value
			Exception()
		str = self.tobits(value)[1:]
		gamma = ""
		for f in range(len(str)-1):
			gamma += str[f] + "1"
		gamma += str[-1] + "0"
		return gamma
	def search(self, string, start):
		length = 1
		index = string.find(string[start], 0, start)
		if index != -1:
			while index != -1:
				old_index = index
				length <<= 1
				if start + length > self.lenz:
					index = -1
				else:
					index = string.find(string[start:start+length], old_index, start + length - 1)
			left = old_index
			old_length = length>>1
			old_index = string.rfind(string[start:start+old_length], left, start + old_length - 1)
			high_length = length
			if high_length > self.lenz - start:
				high_length = self.lenz - start
			length = (old_length + high_length)>>1
			while old_length != length:
				index = string.rfind(string[start:start+length], left, start + length - 1)
				if index != -1:
					old_index = index
					old_length = length
				else:
					high_length = length
				length = (old_length + high_length)>>1
			return (old_index, old_length)
		else:
			return (start, 1)
	def compress(self, z):
		'''the actual apack compressor

		   returns compressed string'''
		self.ormask = 256
		self.flags = 0
		self.lastchunk = ""
		self.lenz = len(z)
		self.flags = 0
		self.out = z[0]
		lwm = 0
		recentoff = -1
		index = 1
		while index < self.lenz:
			rindex, rlength = self.search(z, index)
			if rlength > 1 and rlength < 4 and (index - rindex) < 128:
				self.setbit("110")
				if rlength == 3:
					gamma = 1
				else:
					gamma = 0
				recentoff = index - rindex
				gamma += recentoff<<1 
				self.lastchunk += chr(gamma)
				lwm = 1
			elif rlength > 1 and lwm == 0:
				ro = index - rindex
				if ro == recentoff:
					self.setbit("1000")
					self.setbit(self.togamma(rlength))
					lwm = 1
				else:
					rl = rlength
					if ro >= 32000:
						rl -= 1
					if ro >= 1280:
						rl -= 1
					if ro < 128:
						rl -= 2
					if rl > 1:
						gm = (ro>>8) + 3
						self.setbit("10")
						self.setbit(self.togamma(gm))
						self.lastchunk += chr(ro & 255)
						self.setbit(self.togamma(rl))
						recentoff = ro
						lwm = 1
					else:
						rlength = 1
						self.setbit("0")
						self.lastchunk += z[index]
						lwm = 0
			elif rlength > 1:
				ro = index - rindex
				gm = (ro>>8) + 2
				rl = rlength
				if ro >= 32000:
					rl -= 1
				if ro >= 1280:
					rl -= 1
				if ro < 128:
					rl -= 2
				if rl > 1:
					self.setbit("10")
					self.setbit(self.togamma(gm))
					self.lastchunk += chr(ro & 255)
					self.setbit(self.togamma(rl))
					recentoff = ro
				else:
					rlength = 1
					self.setbit("0")
					self.lastchunk += z[index]
					lwm = 0
			elif index != rindex and (index - rindex) < 16:
				self.setbit("111")
				self.setbit(self.bits(index-rindex, 4))
				rlength = 1
				lwm = 0
			elif z[index] == 0:
				self.setbit("1110000")
				rlength = 1
				lwm = 0
			else:
				rlength = 1
				self.setbit("0")
				self.lastchunk += z[index]
				lwm = 0

			index += rlength
		self.setbit("110")
		self.lastchunk += "\0"
		self.out += chr(self.flags) + self.lastchunk
		return self.out

def npc(filein, fileout):
	prgcmp, chrcmp = "", ""
	size, contents = readfile(filein)
	if not (ord(contents[4])&0x80) and not (ord(contents[5])&0x80):
		header = contents[0:8][:]
		prg_size = ord(header[4])*16384
		chr_size = ord(header[5])*8192
		prog = contents[16:prg_size+16]
		char = contents[16+prg_size:16+prg_size+chr_size]
		header += pack("<II", checksum(prog), 0)
		free_space = SIZE
		if prg_size and prg_size <= SIZE:
			prgcmp = apack().compress(prog)
			prgcmp += "\0"*((4-(len(prgcmp)&3))&3)
			prgcmp = pack("<II", len(prgcmp) + 8, APACK) + prgcmp
		if chr_size and chr_size <= SIZE:
			chrcmp = apack().compress(char)
			chrcmp += "\0"*((4-(len(chrcmp)&3))&3)
			chrcmp = pack("<II", len(chrcmp) + 8, APACK) + chrcmp
		if prgcmp or chrcmp:
			if prgcmp and chrcmp and prg_size + chr_size > SIZE:
				if prg_size - len(prgcmp) > chr_size - len(chrcmp):
					prog = prgcmp
					header = header[0:4] + chr(ord(header[4])|0x80) + header[5:]
				else:
					char = chrcmp
					header = header[0:5] + chr(ord(header[5])|0x80) + header[6:]
			else:
				if prgcmp:
					prog = prgcmp
					header = header[0:4] + chr(ord(header[4])|0x80) + header[5:]
				if chrcmp:
					char = chrcmp
					header = header[0:5] + chr(ord(header[5])|0x80) + header[6:]
			newfile = header + prog + char
			writefile(fileout, newfile)
		else:
			print "Unable to compress."


if __name__ == "__main__":
	if len(argv) == 3:
		npc(argv[1], argv[2])
		#profile.run('npc(argv[1], argv[2])')