# -*- coding: iso-8859-2 -*- 
# wm, 02.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	# rozmiar trójki (minus bit)

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

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


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

	a = data[0]

	data       = data[1:]
	dictionary = a*nd
	result = []
	while data:
		(P, C) = best_match(dictionary, data[:nb])
		if C*8 > size:
			result.append( (0, P, C) )
		else:
			result.append( (1, data[0]) )
			C = 1
		
		S = min(C, len(data))
	
		dictionary = dictionary[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
			assert P+C <= nd
			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!"