Capturing the Gameboy LCD with an FPGA (Part 2) - Compression

In Part 1 I explain how to capture the pixels being sent from the Gameboy GPU to the LCD. The FPGA board I'm using (Papilio Pro) is sending the captured data back to the PC via 2Mbaud serial (over USB). This isn't fast enough to stream frames in real time so only a about 15 frames would be captured and transmitted before the buffer on the FPGA overflowed.

So I implemented a simple lossless compressor to reduce the required data rate. The compressor is line-based: it chooses a reference line from the previous frame and only transmits the differences between that reference line and the current line. This introduces a fixed overhead of one byte per line to encode the location of the reference line and how the differences are encoded. But generally the lines are compressed by much more than one byte!

See the gbcap project for the code!

Compression details

The compressor can encode offsets in x & y between -4 and 4 pixels. This allows the reference line to be between 4 lines above and 4 lines below the line being compressed in the previous frame. It also allows the reference line to be shifted left or right by up to 4 pixels (0 pixels are shifted in to fill the gap).

A per-line prefix byte determines the encoding used for the line, of which there are three:

• A prefix byte of 0xFF means the line could not be compressed, there is no reference line and the next 40 bytes are the line data verbatim

Otherwise the 7 least-significant bits of the prefix byte encode the offset of the reference line, and the most-significant bit encodes whether the match is exact. The offset is encoded in the range 0..89 (so these two encodings do not overlap with the 0xFF encoding) by biasing both offsets by 4 to place them in the range 0..9, multiplying the x offset by 9 and adding the y offset (that is: ((x + 4) * 9) + (y + 4)).

• For an exact match (most-significant bit is set) the reference line is output verbatim.

• For a non-exact match (most-significant bit is not set) the prefix byte is followed by a 5-byte bitmask which encodes which of the 40 bytes of the reference line should be output. For every 0 in the mask a byte is read from the compressed stream and output, for every 1 in the mask a byte is read from the reference line and output.

The compressor selects the reference line with the highest number of matches. If there aren't any reference lines with more than 5 matching bytes then the compressor will output a no-match (0xFF prefix) line as that consumes fewer bytes than transmitting the mask and non-matching bytes in that case.