Log In  


zep

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

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

PX9 tries to predict the colour of each pixel based on the values of its top and left neighbours (this is why vget() as well as vset() is needed in the decompression function). For each combination of top and left values, a list of values is stored in the order they were last encountered (a "vlist"). This means than only an index into the vlist is required to specify the output colour (or an index into a single global vlist if there are no predictions for that neighbour combination yet). Furthermore, PX9 alternates between storing spans of successfully predicted values (index==0) or unsuccessfully (index>0). For the predicted spans, only the length of the span is needed. For non-predicted spans, the length of the span, and then a prediction list index for each pixel is stored.

Both span lengths and indices are stored in the same way: a sequence of n-bit little-endian integers where n = {1,2,3..}. The stored value is taken to be the sum of these integers, and the list is terminated when the last integer has at least one bit that is not set. i.e. is less than (2^num_bits)-1

So, values are stored in the bit stream like this:

0: 0
1: 1 00
2: 1 10
3: 1 01
4: 1 11 000
5: 1 11 100
6: 1 11 010
..

This distribution of encoded lengths works well for pixel&map values and span lengths, as both predictions and near-predictions (index==1) can be stored with single bits, and typical source data roughly produces a log2n distribution in most cases otherwise.

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)

P#63989 2019-04-26 18:34 ( Edited 2019-05-09 02:40)


MBoffin
:: MBoffin

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

P#63991 2019-04-26 20:01

Felice
:: Felice
2

@zep

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


I just want to take this opportunity to point out that leaving the tab-width default at 1 has the hazard that people, like you yourself, don't differentiate between tabs and spaces, and so they write code that intermingles the two arbitrarily.

This PX9 code you've uploaded here looks strange when loaded with tab-width set to 2. Try it yourself, you'll see. Or just click Code under the web player above, where the tab width is 4. Indenting is all over the place.

Do you really think it's better to doom future carts to loading weirdly, rather than dooming some older carts to loading weirdly? I'd favor the future, personally.

If you set the default to 2 spaces, this won't happen nearly as much. People will be able to see the difference and will more actively use spaces instead of tabs if they want 1-space indenting.

(Side note: A "visible whitespace" option would be nice.)

Oh, and sorry for the derailment. To others: please don't respond to this one way or the other, I only wanted to point this out in a way that was ... conveniently visible, let's say ... to zep. In fact, maybe I should put this in hidden tags. Yeah, I'll do that.

P#63993 2019-04-27 02:28 ( Edited 2019-04-27 07:48)

Catatafish
:: Catatafish

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).

P#64004 2019-04-27 17:05 ( Edited 2019-04-27 17:33)

Felice
:: Felice

@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.)

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

P#64049 2019-04-29 06:04

zep
:: zep

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.

P#64249 2019-05-09 02:58 ( Edited 2019-05-09 02:59)

Catatafish
:: Catatafish
1

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

P#65378 2019-06-24 00:57 ( Edited 2019-06-29 02:39)

[Please log in to post a comment]

About | Contact | Updates | Terms of Use
Follow Lexaloffle:        
Generated 2019-11-21 07:49 | 0.061s | 4194k | Q:50