Skip to navigation

⌂ ∞ Elite on the BBC Micro and NES

Image and data compression

How images and data are compressed in NES Elite

One of the advantages of running Elite on the NES is the vastly increased amount of program space compared to earlier versions. The NES Elite ROM cartridge contains 128K of ROM, and that's just for the program code; in comparison the original BBC Micro version used pretty much every spare byte and had to squeeze the game binary into a relatively tiny 21K (see the BBC Micro cassette Elite memory map for details). To authors who were so used to chasing down every single free byte, that 128K of NES ROM must have felt endless.

But as we all know, storage space has a habit of filling itself up, and if you take all the extra languages and sophisticated graphics routines and multi-layer images and try to squeeze them into 128K, they just don't fit, and by quite a long way too. It turns out that 128K isn't as large as it first seems, especially when you're playing with fancy graphics like the Elite logo on the Start screen:

The Start screen in NES Elite

As a result, Elite on the NES contains routines to unpack compressed blocks of data, which take up less space than they otherwise would. The tokenised text system that the authors developed for the original BBC Micro version is still present and correct, but these new routines decompress images and other binary data, unpacking the results into RAM or directly into the PPU.

We'll take a look at the algorithm in a moment, but first let's see how well it works on the data in Elite. Meanwhile, if you want to see what the unpacked images look like, check out the images folder in the accompanying repository, where you can also find Python scripts that implement the unpacking process and combine the results into image files.

Compression statistics
----------------------

The unpacking routines are at UnpackToRAM and UnpackToPPU, but before we pull them apart, let's take a look at how much memory they actually save.

The biggest single-use chunk of memory in NES Elite is taken up by the 15 system images in ROM bank 5, which gobble up 16,043 bytes between them (leaving precious little space out of the ROM bank's total size of 16,384 bytes). These 16,043 bytes contains the packed images, so let's see how the packed and unpacked versions compare.

Each system image unpacks to take up 1792 bytes (that's 896 bytes for each of the two layers in each image - see the deep dive on displaying two-layer images for details of how these images work). This is how the packed and unpacked file sizes compare:

ImagePacked sizeUnpacked sizeReduced to (%)
systemImage01080179260.3%
systemImage11007179256.2%
systemImage21473179282.2%
systemImage31240179269.2%
systemImage4908179250.7%
systemImage51060179259.2%
systemImage61024179257.1%
systemImage71112179262.1%
systemImage8809179245.1%
systemImage9967179254.0%
systemImage101096179261.2%
systemImage111042179258.1%
systemImage121171179265.3%
systemImage131090179260.8%
systemImage14964179253.8%
Totals16,04326,88059.7%

So on average, the images are being reduced to around 60% of their original size, bringing the total unpacked size of 26,880 bytes down to a more manageable 16,043 bytes. That's not too shabby.

The unpacking routine can be applied to any data. Some data is very suitable for packing and other data is less so, and a good example of this is in the view attribute variables. These 24 variables each contain 64 bytes for the view attributes, but their packing ratios vary wildly.

For example, viewAttributes19 packs those 64 bytes down to 13, which is just 20.3% of the original size, but viewAttributes18 only manages to pack them down to 50 bytes, which is 78.1% of the original. Looking at the unpacked data gives us a clue as to why. Here's the attribute data that packs down a lot:

  AF 5F 5F 5F 5F 5F 5F 5F
  FB FA F5 F5 F5 F5 F5 F5
  FF FF FF FF FF FF FF FF
  FF FF FF FF FF FF FF FF
  FF FF FF FF FF FF FF FF
  FF FF FF FF FF FF FF FF
  FF FF FF FF FF FF FF FF
  0F 0F 0F 0F 0F 0F 0F 0F

And here's the data that doesn't pack as well:

  FF FF FF FF FF FF FF FF
  73 50 50 A0 A0 60 50 50
  77 00 99 AA AA 66 55 55
  73 50 50 AA AA 66 55 55
  77 55 99 AA AA 66 55 55
  37 05 09 8A AA A6 A5 A5
  F3 F0 F0 F8 FA FA FA FF
  FF FF FF FF FF FF FF FF

The first set of attributes contains lots of similar values, while the second contains far fewer repeats, and that gives us a big clue as to how the packing algorithm works.

It isn't all good news, though. The large logo on the Start screen, as shown above, turns out to be a terrible candidate for packing. The unpacked binary is 1664 bytes, but when it's packed and put into the game at bigLogoImage, it actually increases by 64%, with a packed size of 2736 bytes. I wonder why it wasn't simply included in its unpacked state? It's all a bit of a mystery...

The unpacking algorithm
-----------------------

The unpacking routines at UnpackToRAM and UnpackToPPU both use the exact same algorithm to unpack data on the fly, with one unpacking to RAM and the other to the PPU's VRAM (via the PPU registers).

UnpackToRAM reads packed data from V(1 0) and writes unpacked data to SC(1 0) by fetching bytes one at a time from V(1 0), incrementing V(1 0) after each fetch, and unpacking and writing the data to SC(1 0) as it goes. The data is typically nametable or single-bitplane pattern data that is unpacked into the nametable or pattern buffers.

UnpackToPPU does the same thing, except it sends it straight to the PPU. The data is typically nametable or four-colour pattern data that is unpacked into the PPU's nametable or pattern tables.

The idea behind the unpacking algorithm is to work our way through the packed data one byte at a time, interpreting each byte according to the following rules:

  $00 = unchanged
  $0x = output 0 for $0x bytes
  $10 = unchanged
  $1x = output $FF for $0x bytes
  $20 = unchanged
  $2x = output the next byte for $0x bytes
  $30 = unchanged
  $3x = output the next $0x bytes unchanged
  $40 and above = unchanged

So bytes like $63, $10 and $43 pass through the unpacker unchanged, but as soon as we bump into value with a special meaning, we apply the relevant rule. Here are some examples:

  • If we come across $04 then we output $00 $00 $00 $00
  • If we come across $13 then we output $FF $FF $FF
  • If we come across $25 $1F then we output $1F $1F $1F $1F $1F
  • If we come across $34 $01 $12 $23 $34 then we output $01 $12 $23 $34

You can see that the algorithm is designed to efficiently pack data with lots of repeated values, especially $00 and $FF, but if the data doesn't contain many repeats but does contain quite a few values under $40, the packed version will actually get longer. Images with large areas of the same colour are therefore excellent candidates for packing, but if we look at the big logo image, which contains its data as PPU-ready patterns, we can see why it doesn't pack well at all, as it's all over the place:

The big logo image in NES Elite

Here's the unpacking algorithm itself, as implemented in the UnpackToRAM routine. If we fetch byte $xx from V(1 0), then we unpack it as follows:

  • If $xx >= $40, output byte $xx as it is and move on to the next byte.
  • If $xx = $x0, output byte $x0 as it is and move on to the next byte.
  • If $xx = $3F, stop and return from the subroutine, as we have finished.
  • If $xx >= $20, jump to upac6 to do the following:
    • If $xx >= $30, jump to upac7 to output the next $0x bytes from V(1 0) as they are, incrementing V(1 0) as we go.
    • If $xx >= $20, fetch the next byte from V(1 0), increment V(1 0), and output the fetched byte for $0x bytes.
  • If $xx >= $10, jump to upac5 to output $FF for $0x bytes.
  • If $xx < $10, output $00 for $0x bytes.

Let's finish off with a list of all the packed data in NES Elite.

List of packed data
-------------------

The following images and binaries are unpacked from the game binary using the above algorithm:

All other images and data blocks (such as the icon bar images) are included in the source code without being packed.