Compression Test

Cart File | Forum Post |

	More cartridges by zep

More Cartridges [View All]

 

Compression Test

by zep

Cart #11383 | 2015-06-25 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

12

This is a quick demo of cart data compression, in order to fit more gfx / maps / music / whatever on a single cart. It's not set up to be a useful tool yet, but you can adapt it if you're keen!

It comes with two functions: comp and decomp that can be used to compress a section of memory to another location, and then back again. You'd only need to include decomp() in the release version of your cart, which is around 95 tokens.

comp(source_addr, destination_addr, length) 
decomp(source_addr, destination_addr, length) 

If you'd like to try it on your own data to see what kind of compression ratios you can get, copy and paste the program into your cart and then change this line near the end:

len = comp(0x2000,0x6000,0x1000)

0x2000 is where to compress from (in this case, the map -- see pico8.txt and search for memory layout)
0x6000 where to compress to. In this case, the screen -- as a way to visualize what's going on
0x1000 the length of the data to compress. 0x1000 (4k) is the top half of the map.

So if you want to try compressing the first 16 SFXs (68 bytes each), use:

len = comp(0x3200, 0x6000, 68*16)

Hi Zep, potentially a dumb question but how do you copy and paste the program into a cart?

You can copy and paste the text in the code section: load my cart, select all the code (CTRL+A), copy it (CTRL+C), load the second (your) cart, delete everything in the code section and then paste (CTRL+V).

(Be careful you don't accidentally save over your original cart!)

Here's the program for convenience:

-- compression test
-- by zep

-- testing compression
-- performance vs. token size
-- of decompression code

-- decomp
-- assume will fit in dest
col = 8
function decomp(src, dest, len)
 pos = 0
 for i=0,len/2 do

  a=peek(src)   -- offset
  b=peek(src+1) -- len
  src += 2

  if (a == 0) then
   -- literal
   poke(dest, b)
   dest += 1
  else
   -- block
   memcpy(dest,dest-a,b)

   for k=dest,dest+b-1 do
   -- poke(k,col+col*16) 
   end
   col += 1
   if (col == 16) col = 8

   dest += b

  end
 end
end

function find_block(dat,pos,len)
 local maxlen = min(255, len-pos)
 local maxlen = min(maxlen, pos)
 local best_len = 0
 local best_i   = 0

 for i= pos-maxlen,pos-1 do
  local j=i

  while ((j-i) < maxlen and
   j < pos and
   peek(dat+j) == 
   peek(dat+pos+j-i))
   do j+=1 end

  if (j-i > best_len) then
   best_len = j-i
   best_i = i
  end
 end

 return best_len, (pos-best_i)
end

function comp(src, dest, len)
 pos = 0
 dest0 = dest
 num_blocks=0
 num_literals=0

 while (pos < len) do
  blen, boff = 
   find_block(src,pos,len)

  if (blen > 1) then
   -- block
   poke(dest, boff)
   poke(dest+1, blen)
   pos += blen
   num_blocks += 1
  else
   -- literal
   poke(dest, 0)
   poke(dest+1, peek(src+pos))
   pos += 1
   num_literals += 1
  end
  dest += 2

  --spr(0, 0,0,16,8)

 end

 print("blocks "..num_blocks)
 print("lit "..num_literals)

 return dest-dest0
end

cls()
cursor(0,80)

len = comp(0x2000,0x6000,0x1000)
print ("len "..len)
print ("orig "..0x1000)

Note that this compression code is not super-efficient, and is designed for byte-wise data. So it works well on maps and audio, but not on gfx which is 4-bit. I get around 80% reduction for typical map data and 60% for audio.

Ah of course :D Cheers.

So how would one use this to fit more maps into a single cart?

Do you first build the map then run the compress tool on the data?

I assume you're going to use this with Jelpi.

yeah that's pretty much it: you build the map, and then you run the compress code and store the map data somewhere, probably at 0x1000 (shared data).

actually I could make a nice little tool for that. pico8 tools could be really nice.

It will be a bit easier to make tools like this in the future, as I plan to extend load() and save() to support partial data transfer. e.g. you can load just the map from a cart with load("map1.p8", 0x2000, 0x2000, 0x1000). An example workflow would be something like:

1. create one map per cartridge
2. load the maps from external cartridges during development for convenience
3. make a cartridge that loads all the maps and compresses them to a single file
4. modify the primary cart's map loading code to decompress maps as needed from within the same cart (rather than loading external maps)

I am VERY interested in this too! :) any idea when it'll be possible to do partial data transfer with load() and save(), zep?

Anyhow, if I got it right, this does not make it possible to keep for example more uncompressed map data in the base ram than usual, right?
Hm. In that case, I wonder if it'd be viable to store the extra map data in the sfx region or anywhere else that's vacant.

Hello, how would I go about modifying comp() so instead of putting it into memory, it'd output string of numbers separated by semicolon? So for example if compressed data has following bytes: 60,34,56,76,23 "comp_str" would return "60;34;56;76;23"?

The reason I'm asking is that I can't really use shared map data and sfx/music data is virtually full so I've figured I'd first compress maps using this function but then store this as strings and unpack into memory as needed.

Of course I could write a "crutch" that then peeks destination area and put it into a string, but such crutch would hurt later on in development when I running out of tokens, but still need compression routines, so I'd rather modify original compress function to output it as string instead of working like memcpy ;).

Here's another proof of concept, this time RLE encoding that works ok on maps and gfx but not sfx. I'll brush this one up and post it along with 0.1.4 which will have a complementary feature intended for such tools: saving/loading sections of carts.

Compression Test: RLE

by zep

Cart #16167 | 2015-11-03 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

The goal here is to get reasonable compression without using too many tokens on decompress. This decomp() will take around 256 tokens and gets compressed ratios of between 0.4 and 0.6 for gfx and between 0.2 and 0.6 for maps, depending on how dense they are. This means that you'd typically be able to store around 2x sprites and 3x map data on a single cart without doing too much trickery.

@pedroavelar
Yes, it will be possible to store any data anywhere you like within the ~16k outside of codespace, and then copy/decompress it into the useable memory areas when initializing each level or whatever. Unfortunately there's still a bug in 0.1.3 preventing writing every bit to the sfx area though, which will be fixed in 0.1.4.

@darkhog
The final version will have a custom putvalue() function so that you can output the data however you like. Note that you probably don't need to include the compression code in the release version of your cartridge though, just the decompression! If you're storing data in strings you could also modify getbit() to read from the string instead of base ram.