PX9 Data Compression

Cart File | Forum Post |

	More cartridges by zep

More Cartridges [View All]

 

PX9 Data Compression

by zep

Cart #px9-3 | 2019-05-09 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

20

PX9 is a lightweight gfx & map compression library, intended to replace PX8. It uses the same ideas and interface as px8, but is smaller (297 292 tokens to decompress), and requires zero configuration.

To compress some data:

px9_comp(x,y,w,h, dest_addr, vget)

returns the number of bytes written

x,y,w,h is the source rectangle (e.g. on the spritesheet or map)
dest_addr is where to write it in memory
vget is a function for reading values (e.g. sget when compressing from spritesheet)

To decompress it again:

px9_decomp(x,y,src_addr,vget,vset)

x,y where to decompress to
src_addr is a memory address where compressed data should be read from
vget, vset are functions for reading and writing the decompressed data 
  (e.g. pget and pset when decompressing to the screen)

Unlike px8, the vget function does not need to return 0 when x,y are outside the destination rectangle

Workflow

You can use px9.p8 as a utility for compressing other carts' data by replacing _init() with something like this:

reload(0x0, 0x0, 0x2000, "mycart.p8")
clen = px9_comp(0, 0, 128, 128, 0x2000, sget)
cstore(0x0, 0x2000, clen, "mycart_c.p8")

This would compress the spritesheet from mycart.p8 and store it in the spritesheet of mycart_c.p8, using memory from 0x2000.. as a temporary buffer. See the PICO-8 Manual for more information about reload() and cstore().

In the release cartridge, you only need the code from tab 1 (px9_decomp) in order to decompress, which should be 292 tokens.

The Algorithm

Slideshow Cart

I'd like to make a pixel art slideshow cart using PX9, with around 5~10 images -- if you have any 64x64 ~ 128x128 pico-8 palette images kicking around that you would like to include, or if you'd like to make one, please email them to me! (hey at lexaloffle dot com).

v3:
felice's getval() replacement
fixed px9_comp() return value (was returning one larger than needed when aligned to 8bit boundary)

This is really impressive. I imagine this would be super useful for people like @nextlevelbanana in making slideshow presentations based in PICO-8! :D

@zep

(Hiding this because it's off-topic and I don't want to derail the thread.)

Nice! That token saving is not to be sniffed at. Although px8 seems to do a better job at compressing the image in this cart - 1274 (px9) vs 1092 (px8) bytes?

It fared better against other image data I tried though (for some 128x128 sort-of perlin noise it did about 2.5kb vs px8's 2.9kb).

@zep

I replaced the logic for getval() in the decompressor and saved 4 tokens. I think it also might be slightly faster, especially when fetching larger bit strings, but not much.

(I also unified the tabs, just because it was driving me nuts.)

(zep's) PX9 Data Compression, 292 tokens

by Felice

Cart #sigunozego-0 | 2019-04-29 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

Nice one @Felice -- I included this version in px9-3.

@Skulhhead1924 The first two version (0, 1) were tests that I didn't post yet. Not sure what you meant, but you can always load the most recent version one from PICO-8 commandline with:
> LOAD #PX9

@Catatafish That's.. actually quite a surprising difference! I haven't done a thorough comparison, but in general their performance is similar, on average. It might be possible to sometimes squeeze a bit more out of px9 by using thing's like px8's remap() function (which reads pixels 8x8 sprite by sprite), but I imagine the smaller token count is more valuable.

I squeezed a few more tokens out of the decompressor, down to 277 in total. I had to minify it a bit so it'd actually fit in a project I'm using this in, sorry.

function px9_decomp(x0,y0,src,vget,vset)
 local function vlist_val(l,val)
  for i=1,#l do
   if l[i]==val then
    for j=i,2,0xffff do
     l[j]=l[j-1]
    end
    l[1]=val
    return i
   end
  end
 end
 local cache,cache_bits=0,0
 function getval(bits)
  if cache_bits<16 then
   cache+=lshr(peek2(src),16-cache_bits)
   cache_bits+=16
   src+=2
  end
  local val=lshr(shl(cache,32-bits),16-bits)
  cache=lshr(cache,bits)
  cache_bits-=bits
  return val
 end
 -- gnn?
 function gn1(tot)
  local bits=1
  while 1 do
   local vv=getval(bits)
   tot+=vv
   if (vv<2^bits-1) return tot
   bits+=1
  end
 end
 local w,h,b,el,pr,splen,mode=gn1"1",gn1"0",gn1"1",{},{},0
 for i=1,gn1"1" do
  add(el,getval(b))
 end
 for y=y0,y0+h do
  for x=x0,x0+w-1 do
   splen-=1
   if (splen<1) splen,mode=gn1"1",not mode
   local a=y>y0 and vget(x,y-1) or 0
   local l=pr[a]
   if not l then
    l={}
    for e in all(el) do
     add(l,e)
    end
    pr[a]=l
   end
   local v=l[mode and 1 or gn1"2"]
   vlist_val(l,v)
   vlist_val(el,v)
   vset(x,y,v)
   x+=1
   y+=flr(x/w)
   x%=w
  end
 end
end

Also, if you swap the serialization order of h and el b in the compression routine you can factor out h & save 2 more tokens in the decompressor.

edit: got my variables mixed up

@Catatafish Can you explain why a couple of your replaced gn1 calls start with tot==0 or 2 instead of 1?

The gn1"2" version is an optimization for gn1()+1 that rolls the +1 into the call. The h=gn1"0" version is the same thing, done to avoid a later use of h-1.