PBJ NES Compression

A peanut butter
and jelly sandwich
.

In August I spent a lot of time crunching numbers to try to find a way to better compress CHR data. Ultimately that effort failed because the LZMPi like bit-streams I was coming up with would bloat the decoder complexity too much for my tastes, but I found out that the core PB8 routine of PB53 was surprisingly effective. So late November I decided to upgrade my nametable compression format by having such a PB8 mode. The first thing I changed was to repurpose the relatively useless transparency mode in favor of PB8. I then proceeded to rearrange the codespace to make a much more efficient decoder.

Right away I noticed that there would be duplicate encodings for encoding a run of 8 bytes and for 8 literals. I also saw that the PB8 codewords for those were either all 1 or 0 bits, which efficiently is detected by the 6502 CPU as a side effect of normal computations. So I re-purposed those for short encodings of whole 8 byte blank planes which appears in tiles that use only 2 colors. Finally I chose 0xff as the stream end byte as that's the value of an unwritten flash byte, and thus be safety-net for when the decoder loses sync.

Initially starts in PB8 mode.
In PB8 mode:
  00000000        : 0x00 8 times.
  01111111        : 0xff 8 times.
  0xxxxxxx ...    : For each bit in the PB8 control byte,
                    0 is a new byte, 1 is the previous byte.
In BG mode:
  0nnnnnnn        : 128-N Run of BG
In both modes:
  10011111 xx     : Switch to BG mode and set BG to X.
  100nnnnn xx     : 32-N incrementing run starting at X.
  10111111        : Switch to PB8 mode.
  10111110 xx yy  : Set PPU_ADDR to yyxx
  101nnnnn xx yy  : For 32-N times, emit alternately X and Y.
  110nnnnn ...    : 32-N literal bytes.
  11111111        : End stream.
  111nnnnn xx     : 32-N run of X.
PBJ Stream format

PB8 is the peanut butter, RLEINC2 the jelly, and my old nametable compression the bread that combines it all together into .pbj files.

The decoder assembles to 156 bytes of ROM and uses 5 bytes of RAM. The current encoder is a bit dumb as it's only able to use either pb8 planes or everything else but not both.

Example file sizes: The pbj picture in this post: 4513 bytes The gus portrait from 240p test suite: 2297 bytes The title screen from Zooming sectary: 1423 bytes