I looked at tokumaru's rewrite of the Codemasters Markov CHR codec. I noticed that it essentially transforms runs of identical pixels into a unary code: 0 represents one pixel, 10 represents two, 110 represents three, etc.
Dwedit has noticed that this scheme doesn't perform so well on tiles with 1 bit per pixel. These tiles are seen in text fonts and in decorative tiles representing things that are in the far background. Encoding run lengths in unary doesn't save any bits over not compressing the 1-bit tile at all: each pixel has one bit for whether it's the same color as the pixel to its left or the other color. In fact, there are two additional bits of overhead per line: one to state that the row isn't repeated, and one because the first pixel is always literal (not compressed), even in a tile with two colors mode 1 and the others mode 0.
I'm playing with the following techniques and seeing 15 to 20 percent off a font:
I'll release a demo once I have an encoder and decoder finalized.
Dwedit has noticed that this scheme doesn't perform so well on tiles with 1 bit per pixel. These tiles are seen in text fonts and in decorative tiles representing things that are in the far background. Encoding run lengths in unary doesn't save any bits over not compressing the 1-bit tile at all: each pixel has one bit for whether it's the same color as the pixel to its left or the other color. In fact, there are two additional bits of overhead per line: one to state that the row isn't repeated, and one because the first pixel is always literal (not compressed), even in a tile with two colors mode 1 and the others mode 0.
I'm playing with the following techniques and seeing 15 to 20 percent off a font:
- Encoding 32x8 pixel areas instead of 8x8, to be rearranged by the unrolled code that copies the result to VRAM. This allows for capturing longer run lengths, such as the 1-pixel-tall gap at the bottom of glyphs with no descender or the 2-pixel-tall gap at the top of lowercase glyphs with no ascender.
- Gamma coding the run lengths. It slightly outperforms Golomb(M=2), which significantly outperforms unary.
- Swapping the code for the most common run length with the code for run length 1 pixel. This saves on (for example) fonts with lots of vertical strokes 2 pixels thick.
I'll release a demo once I have an encoder and decoder finalized.