# -*- coding: iso-8859-2 -*- 
# wm, 01.02.2007

db = 13
bb = 16-db
nd = 2**db	# rozmiar słownika
nb = 2**bb	# rozmiar bufora (wejściowego/wyjściowego)

size = db + bb

def best_match(dictionary, buffer):
	n = len(buffer)
	assert n > 0

	for k in xrange(n, 0, -1):
		tmp   = buffer[:k]
		index = (dictionary+tmp).find(tmp)
		if -1 < index < nd:
			return (index, k)
	
	return (0, 0)


def LZSS_encode(data):
	assert len(data) > nb

	a = data[0]

	data   = data[1:]
	buffer = a*nd + data[:nb]
	data   = data[nb:]
	result = []
	while len(buffer) > nd:
		tmp    = buffer[nd:]
		(P, C) = best_match(buffer, tmp)
		if C*8 > size:
			result.append( (0, P, C) )
		else:
			result.append( (1, buffer[nd]) )
			C = 1
		
		S = min(C, len(data))
	
		buffer = buffer[C:] + data[:S]
		data   = data[S:]

	return (a, result)


def LZSS_decode(fs, data):
	result = [fs]
	buffer = fs*nd
	for item in data:
		if len(item) == 3:
			_, P, C = item
			if P+C > nd:
				tmp = (buffer[P:]*C)[:C]
			else:
				tmp = buffer[P:P+C]
		else: # len(item) == 2:
			_, S = item
			tmp = S
			C   = 1
		
		result.append(tmp)
		buffer = buffer[C:] + tmp

	return ''.join(result)

if __name__ == '__main__':
	import sys
	from math import log, ceil

	if len(sys.argv) < 2:
		print "Podaj nazwę pliku"
		sys.exit(1)

	data   = open(sys.argv[1]).read()
	comp   = LZSS_encode(data)
	decomp = LZSS_decode(*comp)

	if data == decomp:
		k1 = sum(1 for item in comp[1] if len(item)==2)
		k2 = sum(1 for item in comp[1] if len(item)==3)
		n1 = db + bb + 1
		n2 = 8 + 1

		l1 = len(data)
		l2 = (k1*n1 + k2*n2 + 7)/8 + 8

		print "Liczba dwójek: %d" % k1
		print "Liczba trójek: %d" % k2
		print "Liczba danych: %d + %d = %d" % (k1, k2, k1 + k2)
		print "Liczba bitów potrzebna do zapisania dwójki: %d" % n1
		print "Liczba bitów potrzebna do zapisania trójki: %d" % n2
		print "Rozmiar danych wejściowych: %d bajtów" % l1
		print "Rozmiar danych skompresowanych: %d bajtów" % l2
		print "Stopień kompresji: %.2f%%" % (100.0*(l1-l2)/l1)
		# print data
		# print decomp
	else:
		print "Wystąpił jakiś błąd!"