Log In  

Cart #px9-5 | 2020-05-29 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
26

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

v4: // More improvements by @Felice & @Catatafish
Fixed the bit-flushing bug at EOF
Perf should be better in 0.2.0
Down to 274 tokens

P#63989 2019-04-26 18:34 ( Edited 2020-05-29 09:19)

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

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

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

P#64049 2019-04-29 06:04
:: 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)
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)
:: sparr

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

P#73088 2020-02-14 03:55

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.

P#73095 2020-02-14 07:42 ( Edited 2020-02-15 18:44)

I would love to check out the code, but PICO-8 "CANNOT CONNECT TO BBS" for some reason. is the code snippet you posted in the description all I need to compress and decompress? and am I too late to make PICO-Art? (Hee Hee! PICO-8 PICO-Art!) Thanks!

P#74783 2020-04-15 21:10
:: zep

Hi -- the site was down for a few moments while doing some maintenance. Please try again now!

yes, those snippets plus the contents of the cart are all you need (tab 1 for decompression and tab 2 for compression)

P#74785 2020-04-15 21:16

That was fast. I accidentally closed this tab and when I reopened the tab I saw your comment. Anyway, I tried to run a game I have never played, unable to connect to bbs. I try to download a game, download failed. I also tried reinstalling both pico-8s (yes, I have two PICO-8s on the sidebar (mainly cuz I have two screens)) but, nope. thanks for speed-replying!

P#74786 2020-04-15 21:27

I wonder why all my comments are so long.

P#74787 2020-04-15 21:27

Oh, and it didn't work on my second pico-8 either.

P#74788 2020-04-15 21:29

wow, 3 comments in a row that's a first. oh after I post this it will be four.

P#74789 2020-04-15 21:30

and for the PICO-Art, can I use the SECRET COLORS?

P#74790 2020-04-15 21:37

Ooh! just noticed the new CIRCLE TOOL! gonna be a big help in art.

P#74791 2020-04-15 21:40
:: mrh

Hey @zep, I think I've encountered a bug where the returned length of compressed data is reported 1 byte too short, and I was chopping off this extra byte which lead to some corruption when decompressing.

Just incrementing clen immediately after compressing works around this issue (but sometimes uses 1 extra unnecessary byte I think).

I may be able to come up with an example if that's helpful.

P#76892 2020-05-19 09:20
:: Felice
5

I have a version of this that's been updated for 0.2.0 functionality/performance and has the optimizations @Catatafish made above.

Now that @mrh has pointed out the bit-flushing bug at the end of the file, I've also fixed that in my version.

I don't mean to step on @zep's toes, but I think I should just offer up this version, since it's a rollup of everything that could have been done to PX9 since zep's last official version.

Notes:

  • Functionality is should be identical
  • Fixed the bit-flushing bug at EOF
  • Perf should be better in 0.2.0
  • Down to 273 tokens
  • Some code rework because I'm OCD (sorry zep)

Here's the cart:

Cart #mayobagegu-0 | 2020-05-29 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
5

P#77342 2020-05-29 00:21 ( Edited 2020-05-29 11:48)
:: zep
1

Thanks @mrh, I just updated the cart with @Felice's fix (cheers Felice!)

P#77349 2020-05-29 04:09 ( Edited 2020-05-29 04:09)
1

First off, thanks for the awesome tool!

Gratuitous feature request:

Is there an easy way to extend this to compress to and decompress from strings? (e.g. the decompress function could use a vget function to access the string, but the compress function just stores to cart memory.)
With the vget vset functions, can this be extended to compress to or decompress from strings?

1) compress from spritesheet to file on disk using (printh str [filename] [overwrite])
2) decompress from string in code section to spritesheet.

--end gratuitous feature request that I am just being too lazy to code myself

P#77351 2020-05-29 04:25
:: mrh
1

I've updated to the new version, removing my workaround, and everything seems to be happy. Thanks for the bugfix @Felice & @zep.

The compression is working nicely and I'm going to be able to cram a lot of content into this cart by the looks of things.

P#77357 2020-05-29 10:12
:: Felice

Thanks for testing, @mrh, glad to hear I didn't break it. :)

By the way, I typo'ed the token count above. I said it was down to 274 but it's actually 273. Hey, every token counts, right? :)

P#77361 2020-05-29 11:49
:: Felice
1

@electricgryphon, @zep, et al

I wrote a version of the decomp that can read from a base128 string or from memory, depending on whether its passed a string or a numeric address as the src. It's 320 tokens vs. 273 for just memory, which is a fair bit more, so here's a cart with all three versions of the decompressor, with a compressor that can write to memory or strings.

See the first tab for updated usage details in the big comment block, but here's the TL;DR:

  • 320 tokens for px9_decomp(), which can now take an address or a string.
  • 273 tokens for px9_mdecomp(), which was the existing memory-only decompressor.
  • 283 tokens for px9_sdecomp(), which is a string-only decompressor.
  • Compressor can now take nil as a dest addr, causing it to return a string instead of compressed len. Use #str to get compressed len.

Gryph, regarding writing to disk, you'd obviously just printh() the resulting string yourself.

Edit 1: Hotfix for a bug @electricgryphon reported below.

Edit 2: After investigation, we've found that some images encoded as raw hex strings will produce smaller carts after .p8.png compression than using PX9-compressed strings. The sample image in zep's cart is smaller via PX9 string, while @electricgryphon's test image below is smaller via raw hex string. The hot take here seems to be that an image with a lot of patterns will make a smaller cart with raw hex, while an image with a lot of solid areas will make a smaller cart with PX9. So people might need to pick and choose when it comes to string encoding. Memory encoding will always benefit from PX9 though.

Cart #suyanuroge-2 | 2020-05-30 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
1

P#77380 2020-05-29 15:04 ( Edited 2020-05-30 01:51)

Thanks a bunch! Gonna try this out now.

P#77386 2020-05-29 17:15

Found a typo in px9_decomp, line 272

cache|=(((ord(sub(str,i,i))) or 0)&127)>>>16-cache_bits
should read
cache|=(((ord(sub(src,i,i))) or 0)&127)>>>16-cache_bits

With that change, this works awesome!

Out of curiosity, the output string is mostly symbols and kanji. Is there a reason to use this for encoding data as opposed to ASCII? (eg:"◝◝◝♥◝◝◝♥ョ⧗🅾️◝★スすクュ..." vs "sdf53RG4rads#$T%$..." )

P#77399 2020-05-29 20:24 ( Edited 2020-05-29 20:32)

Well, for my particular target image (ordered 8x8 dither with no solid areas) this doesn't look like a good compression fit when I look at compressed code size after storing as a string in the code section.
(It does take up less space in the gfx section of the file though, just not in the code section, if that makes sense.)

                              Total    Delta (compressed code)
Initial compressed code size = 9122    0
String compressed code =      15045    5923
Hex compressed code    =      15286    6164
Raw (uncompressed hex) =      12901    3779

So for this particular image/use case, I'd be better off pasting the image as a raw hex string.

Here's the image:

P#77403 2020-05-29 22:13
:: Felice
1

@electricgryphon

Wait, how the heck is it even working with the wrong variable name there?

...

OH!

Okay, I see, the test code actually, by complete coincidence, used a global called "str" to hold the compressed data, which is what "src" points to inside decomp. So it works, but fails if I change the global to "image". What a devious little bug! It was in sdecomp as well, sigh.

Thanks for catching that! I've fixed, tested, and updated my version of the cart. :)


I used chars 128-255 instead of alphanumerics because it meant I could use the whole continuous range, storing the value raw with its top bit set, so I could just clear the top bit during decode, no worrying about which chars are legal in strings (e.g. single/double quote, backslash) and closing gaps or table lookups and stuff like that. It looks funky but with the current cart format there's no compressed-size hazard in using the upper range anymore.


Also, I guess I'm not surprised that your image fares better as a raw hex string. The .p8.png compressor is much better than it used to be while PX9 seems to do well mainly with large continuous blocks of color. It might only matter if the hex-string version of your raw data is too big for the source code window or something.

Maybe try your method with other bases than 16? Like base64 or my version of base128, for instance. Encode/decode is pretty simple. I'm curious whether or not changing the bit stride like that will mask patterns out and make the .p8.png cart compression worse.

P#77412 2020-05-30 00:09 ( Edited 2020-05-30 00:17)
:: Felice

@electricgryphon

Actually, I tried the test I suggested above. Base64 and base128 both cause the compressed size to increase, so yes, they do obscure the patterns the .p8.png compressor is able to make good use of.

So yeah, I agree: if you can afford the space in your 64k source code window, a simple hex encoding that gets compressed by the built-in source code compressor is probably the best bet for your kind of image.

I'm not sure if this will be true for all image types, though. Yours has a lot of regular noise to simulate RGB, but most games use more cartoony visuals, like zep's sample image, whose px9 string performs markedly better after p8.png compression than a raw hex string version does. If you or anyone else has some real-world game image samples for me to try, let me know and I'll run them through this little base16/64/128 test bench I wrote to see, because if the string encoding isn't worth it, I should just remove that and de-complicate the library.

(Side note: interestingly, if I encode almost 32k worth of graphic data similar to yours into an almost-64k source hex string, it compresses to just about the compressed p8.png size limit. Nice work, @zep!)

P#77414 2020-05-30 01:10 ( Edited 2020-05-30 01:35)

[Please log in to post a comment]

Follow Lexaloffle:        
Generated 2020-08-14 16:36 | 0.123s | 2097k | Q:142