JavaScript RLE algorithm v3 - Bit-Level RLE

As promised, new post in the series of Run-Length Encoding (RLE) compression. List of all posts:

1. JavaScript Run-Length Encoding for Arcade Sprites
2. JavaScript RLE algorithm v2 - Sprite Tiles
3. JavaScript RLE algorithm v3 - Bit-Level RLE

One note before getting into details and numbers: The code I've built supports from 2 up to 16 colour images, but to keep things simple I will stick to the 4 colours of the original GameBoy.

In the last post, we saw that reordering sprite tiles initially was not a big deal. The extra logic (and effort re-assembling them) looks like not worth it. So a different path that we can explore is, going back to working with full sprites, go down to bit-level and apply there the RLE encoding algorithm.

When we switch to counting streaks of zeros and ones, there are multiple approaches that we can take. As my base scenario is quite compact, having only 4 colours (2 bits: 00, 01, 10 and 11), I decided to apply a variant of the Code RLE "system": I assume my images will plenty of zeros, so I take 00 as an RLE packet, and the other values as data packets; An RLE Packet will include the identifier (00) and a length, meanwhile a data packet means "simply write those bits as they are" (01, 10 and 11).

The logic becomes basic, as a packet will be either 2 or 8 bits: First we read two bits and check: if 00, read another 6 bits for size (up to 64 repetitions) and write the value; else, write the value and repeat read (until finished). This means that I am potentially wasting space when we have long streaks of plain-coloured images (other colours apart from the first/background colour), but on the other hand, detailed pixel sprites and dithering patterns will be very optimally stored. [1]

In this v3, the main logic both compares in-memory compression, and writes to disk (as a .bin file) that immediately reads back and unpacks into memory (and for manual comparison, writes the resulting png). The binary file contains a tiny header: the 1st byte stores the image width and the 2nd byte stores the height; then, just the RLE-encoded data (byte-aligned and padded).

With the two sample GameBoy images, we achieve a reduction from 1600 bytes (source image, in-memory) to 402 bytes (in memory bytes and .bin file size), and from 3080 to 772; That's a remarkable 25% of the original size in both cases!

To expand the experiment, I've also added one Street Fighter II sprite, which being 16 colours also fits in the current implementation. We get a 50% reduction in size (vs 32% in the normal indexed-palette RLE version), not bad!

In the screenshot we see leftmost the original images, followed by a PNG export of the in-memory encoded & decoded RLE, followed by a PNG export of the file written & read RLE. All exact pixel by pixel copies.

When we run the main program, the debug information now shows also a bit-level RLE representation of the encoded image, which is simple to follow: the first digit is always the colour number/index, and if an asterisk follows, then what remains is the hexadecimal value of the number of repetitions. As we only repeat the first colour, effectively 0*xx for RLE packets, and 1, 2 or 3 for data packets.

As I mention just below in the footnote, once you get down to bit-level RLE, you unveil numerous new possibilities and potential optimizations. I'm enjoying this learning so much that I might actually write a v4, to switch the current code to do delta RLE encoding, and see how good it gets.

As usual, the code is available at my GitHub, specifically at https://github.com/Kartones/JSAssorted/tree/master/rle/v3.

[1] There are many alternatives. I could set a single bit to differentiate RLE and data packets, which would save space for long streaks of 0 repetitions, but waste extra for the data packets; I could also support streaks of consecutive 1s; I could explore more advanced paths like delta-encoding... So many interesting things!

UPDATE: Added screenshot and brief description of how the RLE encoded representation should be interpreted.