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

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

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
			sys.exit(1)
		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, dict, string, index):
		longest_length = 1
		longest_index = index
		char = string[index]
		if char in dict:
			for f in dict[char]:
				start = f + 1
				count = 1
				pos = index + 1
				while pos < self.lenz and string[start] == string[pos]:
					start += 1
					pos += 1
					count += 1
				if count >= longest_length:
					longest_length = count
					longest_index = f
		return (longest_index, longest_length)
	def compress(self, z):
		'''the actual apack compressor

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

			for f in range(rlength):
				char = z[index]
				if char in dict:
					dict[char].append(index)
				else:
					dict[char] = [index]
				index += 1
		self.setbit("110")
		self.lastchunk += "\0"
		self.out += chr(self.flags) + self.lastchunk
		return self.out

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