assemblerbot • 2021-03-27*2021-03-27 10:23* •

Hello,
as any of you guys I need some decent picture compression for the Pico Off Road game I'm making. PX-9 is very good choice but one of my passions always were compression algorithms. So I've decided to implement one myself. Sometimes is better and sometimes is worse than other available algorithms here. Consider it as my addition to the community and use it wherever you need.

Algorithm

LZ77 is very simple compression method that works similar to RLE with the exception: while RLE copies the same character N times LZ77 copies chunk of already decoded data of length N. I've used 3 different blocks: direct color output, offset + length block and just length for coherent rows (sequence that starts on the same X position but in previous row). Compression allows self-overlapping (for example offset 3 and length 20 is valid, it just copies itself with offset).

For more information check https://en.wikipedia.org/wiki/LZ77_and_LZ78#LZ77

Limits

designed for PICO-8 pictures only (or any arrays of values in interval 0..15), don't try it on map or other binary data
picture size limit is 128x128
compression uses simple brute force search and can be very slow (up to a minute on fast PC), but who cares?
decompressor is 131 tokens long and is relatively fast
it's guaranteed that the compressed stream never contains ] character so it's safe to keep it in [[..]] raw lua string
compressed stream doesn't contain capital letters (A..Z)
size of the picture is not in the compressed stream so you have to know it ahead

Tips

LZ77 from it's nature is good for compressing repeated patterns. For example images that use 2 color gradients with Bayer-Matrix dithering have usually much better compression ratios than images with random dithering.

Large blocks of single color are also compressed with high rations but expect much longer compression times.

Example

Load cartridge, import yourimage.png, in function _init edit w,h (width and height of the area you want to compress) and run. Result is written to compressed.txt.
For example following image is ideal for LZ77 - compressed size is just 1157 bytes.

Code

Whole code including cartridge and test picture is on Git (license CC0) https://github.com/assemblerbot/pico8-lz77 .

If you want to copy-paste it, here it is:

Compressor

max_run_len=100

function lz77_out_a(value) -- 0..15
	if value<0 or value>15 then
		stop("value 𝘢 out of range! "..value)
	end

	return chr(value+32)
end

function lz77_out_b(value) -- 0..178
	if value<0 or value>178 then
		stop("value 𝘣 out of range! "..value)
	end

	if value<17 then
		return chr(value+48)
	else
		return chr(value+94-17)
	end
end

function lz77_out_c(value) -- 0..194
	if value<0 or value>194 then
		stop("value 𝘤 out of range! "..value)
	end

	if value<33 then
		return chr(value+32)
	else
		return chr(value+94-33)
	end
end

function lz77_comp(x0,y0,w,h,vget)
	local pixels={}
	for y=0,h-1 do
		for x=0,w-1 do
			add(pixels,vget(x0+x,y0+y))
		end
	end

	local out=""
	local i=1
	while i<=#pixels do
		local p=pixels[i]

		local run=0
		local ofs=0
		for j=max(1,i-195),i-1 do
			local k=0
			while i+k<=#pixels and pixels[i+k]==pixels[j+k] do k+=1 end
			if k>run or (k>=run-1 and i-j==w) then
				run=k
				ofs=i-j
			end
		end

		if run<2 or (run==2 and ofs~=w) then
			-- direct pixel output
			out=out..lz77_out_a(p)
			i+=1
		elseif ofs==w then
			-- row with coherence
			run=min(run,178-(max_run_len+1)+2)

			out=out..lz77_out_b(run-2+max_run_len+1)
			i+=run
		else
			-- run
			run=min(run,max_run_len+2)

			out=out..lz77_out_b(run-2)
			out=out..lz77_out_c(ofs-1)

			i+=run
		end
	end
	return out
end

Decompressor

function lz77_decomp(x0,y0,w,h,src,vset)
	local i,d=1,{}
	while i<=#src do
		local c=ord(src,i)
		if c<48 then
			add(d,c-32)
		else
			local ofs,run=w,c-46
			if c>=94 then
				run-=29
			end
			if run>=103 then
				run-=101
			else
				i+=1
				ofs=ord(src,i)-31
				if ofs>=63 then
					ofs-=29
				end
			end
			local pos=#d-ofs
			for j=1,run do
				add(d,d[pos+j])
			end
		end
		i+=1
	end
	for i=0,w*h-1 do
		vset(i%w+x0,i\w+y0,d[i+1])
	end
end

Main

function _init()
	local x,y=0,0 --source position
	local w,h=128,128 --source size

	local lz77=lz77_comp(x,y,w,h,sget)
	print("size="..#lz77)
	printh(lz77,"compressed.txt")
	--lz77_decomp(x,y,w,h,lz77,pset)
	flip()
	stop()
end

Have fun! :-)

compression

JadeLombax • 2021-03-28*2021-03-28 20:47*

Thanks for posting,

I've been tinkering with various permutations on RLE and working on encoding runs of patterns instead of just solid colors, but haven't made the jump to something like this yet, so this will be interesting to dissect.

I've been doing some comparison tests between image compression algorithms on Pico-8, and I've found some surprising things. First is that the integrated code compression is pretty impressive, and its effects on actual space on cartridge are really big.

To illustrate, I just made a new algorithm that encodes runs of bytes instead of pixels, and running your test image through it, I get a raw string size of 2991 characters vs. just 1157 for your LZ77 codec, but the compressed size is actually smaller, at 923 bytes vs. 1064.

I guess it depends on whether or not you're going to store compressed data in string form or in binary, but if the former, it seems like optimizing file size is largely about figuring out what works the best with the compression systems already at play. This does make things more complicated, but I guess extra compression always helps.