I was working on developing some NES games. One of the things I needed was the compression of “nametables”, especially for static title screens that have many unique tiles. To that end I researched how efficient several compression formats were.
a NESdev forum user by the name of CartCollector collected a set of tile data called the NESdev Corpus so that others can test out the size and speed efficiency of various tile compression methods. A couple years after that, Tepples posts the quite efficient PB53 codec. So I too had gathered a set of data to test for nametable compression. The set consists of 64 title screens usually with relatively large graphics. I also chose screens constructed not only with background tiles but sprites as well. In the future I'll have to look into how to efficiently store sprite positioning.
For NES nametables, PackBits is a commonly chosen algorithm. It's a good choice that performs well because nametables often contains many runs, sometimes even large ones spanning multiple rows of 32 bytes.
If you were to look at the nametable data from NES picture drawing applications and generators, you might notice that there's multiple sequences that count upward by 1. This happens because the generator simply assigns the next available index for each unique tile. Several new schemes were developed that added a command suited for those sequences. File #08 is a good example of a picture that has these types of incrementing runs.
But even with that technique we have hard to encode pictures with long repeating patterns like with file #09. Joel Yliluoma, while working on his translation project, developed a compression scheme that handles repeating runs of 2 bytes well. It was then adapted for Bregalad's Compress Tools project.
I could try out LZSS based algorithms, but the NES is a memory constrained system, and I'm looking for simple formats. Efficiency isn't only about the compressed data size, it's also about the size and speed of decompression code. So considering all of this I decided to design a nametable compression format of my own. I gave this format a uncreative code name of "NTD" short for “Nametable format 'D'”.
In NTD I assigned most of the code points to runs of a background index, that way I retain the full benefits of PackBits but won't waste bytes by repeating the same index. Next I evenly split the remaining code points to the 4 different run types. The reason for negated numbers is so that 0 can never be a valid number. Also in assembly the run length can be retrieved with a simple
ora #$e0, as long as the count is incremented to 0. Finally I got creative with re-purposing the codes points that would have had the same effect as other codes point. The assembled size of the lite decoder variant comes out to 110 bytes.
To get some statistics from the various compression formats, I wrote encoders for each in python. 2 other compression formats (pb53 and LZMPi) are included as well. I wanted to also see how much of a effect sorting the tiles according to appearance in nametables would have. For LZMPi I used the LZMPi encoder that Joel Yliluoma programed.
|unsorted /w attr||65536||31046||31031||29602||25207||24843||24632||21795||19991||18793|
|sorted /w attr||65536||30056||29984||28589||23766||23427||22588||20972||19047||18256|
looking the “unsorted with attributes” row, the new NTD compression saves on average about 69% or 710 bytes per nametable. That's compared to PackBits which saves about 55% or 562 bytes per nametable. PB53 is not really meant for nametable data, but the NESdev wiki page says “it works fairly well on real tile data and OK on nametable data.”
I anticipate finding additional ways to reduce space, especially for data files #03 and #41. The result would likely be a very different format with things being packed into bits like in LZMPi.