Here are how and why the future sprite format is defined for bitbox sprites.
Here are the sprite format properties, why they are needed and what impacts it had on the format
- binary based format
- line-based blitting
- no transparent color
- run-length encoding and packbits algorithm
Coding same color ranges into one (color, number of pixels) pair is named RLE. It's the first useful compression one can use, it's fast and straightforward. It's also good for bitbox, since it's coherent with line-based blitting. It's also very fast because you just have one read and N writes for 2*N pixels if you're blitting 16bpp.
We can also group single pixels, since you generally have many similar pixels then a bunch of single pixels. In that case you can avoid transmitting (1,color) (1,color2) (1,color3).
- back references
Another way to improve compression for "free" (on decompression side) is to avoid coding twice the same run of pixels. If you can retrieve a past group of pixels already encoded, it's not very expensive to blit from this address instead of the current address. Of course, this is only interesting if you're going to encode less than the size you'd need for encoding the address itself. This is in fact how deflate, gzip and other LZ77 encoders work; but with a modification : in lz77 you can reference the past blit (ie data already extracted). Here we're blitting sprites but once a line has been written, another object can have written over it for the next line, so you can't reference past blitted lines. You have to reference the source data, worsening a bit you ratio. You could reference the same line but generally the interesting parts - non handled by RLE- are in previous lines.
- explicit EOL encoding
- extensible size encoding.
But then you have to cut large blits into smaller ones, which can be slower to blit and decode the header, and bigger at the same time.
What's used here is a variable length encoding similar to LZ4 :you use 5 bits for the base and then if the len you want to encode is more than that, you add a byte of data (and another while you don't have to).
By example,
15 is encoded as 15,
30 as 30,
200 as 31 + another byte with 200-31 = 169
31 as 31 + another zero byte yes it's a useless zero byte but that's rare.
All of this leads to a 'blits' encoding, where we store blits with a header and some data.
Header is :
2 bits for the type of blit,
1 bit for end of line
5 bits for length
+ N bytes extra for length as needed
Data is :
blit "Skip" : nothing
blit "Fill" : color to blit with
blit "data" : "length" pixels encoding
blit "back reference" : 2 bytes as back reference in bytes since the current bytes. This sliding window allows for more than 64k resources
For encoding pixels, you can of course use raw u16 pixels which are quite big.
- pixel palette can be slow but dense, but there is a better way.
In order to reduce the storage of individual pixels, you can use less colors and thus less bits per pixel. using 256 colors you can reduce your storage by two comarped to raw 15bpp, when using 16 colors you can reduce by four(but this will have an impact on what you can provide). A global 8bpp encoding is available for either the bitbox micro or the a global 8bpp palette reduction.
Pixel palette is not a panacea however, since it needs much longer to blit. While we can memcpy (setting aside alignment operations) one word at a time (i.e. one u32 word read and one write per couple of pixels), now need one read for 4 u8 pixels, but four reads (one of each palette lookup), adding to the contention of memory buses. What can be done is making a table for multiple pixels lookup but for 256 colors you'd need 65536 entries. Better to limit that number.
What's interesting is that generally you don't use the whole number of different couples for a given set of colors. Not every couple is used, and it's generally much better to limit oneself to 256 couples than 16 individual colors. And in that case, we have 8 pixels for 32 bits of data + one read + one write for 2 pixels, which is very close to the raw pixel encoding speed.
Couples also adds the possibility to allow run-length encoding of dithered patterns which in pixel art and limited color can be useful.
To encode such a picture, I made a small encoder which can extract common couples like you do with the same algorithms for color quantization, except it's now couples quantization.
Frame encoding :
- multi-frame format & skiplist
Our format should be used to encode not a single image, but multiple frames animations.
First, it's generally simpler to manage one file per animation than one file per image.
Then you generally produce the content that way.
And then an animation generally contains many slightly different frames but not entirely different frames and colors, so you gain in not having to repeat the palette and the blits.
We do this by specifying a frame size and putting all the frames vertically.
What you need is then an index of each frame start since each frame is not the same size, in order to be able to skip directly to this and not having to unroll the whole sprite from frame zero. So we add a table with skip frame indices. We use a simple u32 list to allow big files, and direct access - we could use a delta encoded u16 since no frame is larger than 64k generally but the next paragraph will explain why - it's not very heavy generally.
- frame deduplication
Also, your frame step can be the same length and you can repeat a want a frame to be longer.
That means that frames are no longer unique or the frame index monotonous and cannot be delta-encoded efficiently.
