'------------------------------------------------------------------
'
' This is an implementation of the LZW compression algorithm.
'
' The code tries to be as simple and small as possible.
'
' (c) Peter van Eerten 2018, MIT license
'
'------------------------------------------------------------------

' Get filename
IF AMOUNT(ARGUMENT$) < 2 THEN
	PRINT "Usage: ", ME$, " <file>"
	END 1
ENDIF

CHANGEDIR DIRNAME$(ME$)

file$ = TOKEN$(ARGUMENT$, 2)

DECLARE data TYPE unsigned char*

data = BLOAD(file$)

length = FILELEN(file$)

' Initialize first 256 elements
DECLARE dict ASSOC unsigned short
FOR nr = 0 TO 255
	dict("," & STR$(nr)) = nr
NEXT

result = MEMORY(length*2+SIZEOF(short))

FOR x = 0 TO length-1

	ch$ = "," & STR$((unsigned char)data[x])

	IF ISKEY(dict, buf$ & ch$) THEN
		buf$ = buf$ & ch$
	ELSE
		OPTION MEMTYPE unsigned short
		POKE result+byte, dict(buf$)

		INCR byte, 2

		IF nr < 65536 THEN
			dict(buf$ & ch$) = nr
			INCR nr
		ENDIF
		buf$ = ch$
	END IF
NEXT

POKE result+byte, dict(buf$)

BSAVE result TO file$ & ".lzw" SIZE byte+2

FREE data, result

PRINT "Done in ", TIMER, " msecs. New size is ", FILELEN(file$ & ".lzw")*100/length, "% from original."