nesdev.com

How can using tile compression on the NES actually work at all?

I mean, if I had some DOS game in mode 13h, then I would understand it:

Every pixel is one byte, so instead of saving graphics as

red, red, red, red, blue, blue, white, white, white

you simply save it as

4, red, 2, blue, 3, white

But on the NES, a pixel consists of merely two bits.

How shall compression in this system ever pay off?

I mean, you can still treat the pixels in chunks of bytes, but this works only if patterns of four pixels repeat themselves. Which should be more the exception than the rule.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg

If you just compress individual tiles by themselves, you're right, it'll never pay off. Therefore, you should compress groups of tiles, even entire pattern tables of tiles, and the payoff will be better. Another thing is that tile compression often operates in a bit stream, rather than a byte stream.

A tile is 16 bytes. A tile that is mostly zeros could be represted (in compression) by 8 bytes.

A pattern of tile 3, tile 4...3,4,3,4,3,4...repeated frequently, could be represented in 1 byte, rather than 2, saving 50% here, and any similar pattern.

A tile pattern of repeats, 3,3,3,3,3,4 could be represented by 3 (repeat key) 5 x, 4 = 4 bytes vs 6, save 33%.

Etc.

_________________
nesdoug.com -- blog/tutorial on programming for the NES

Much tile compression on the NES, Game Boy, and Super NES works by repeating entire bytes. This works on tiles with blank areas or vertical lines.


This glyph for 'A' transforms into the following tile data:


The PB53 codec first looks for consecutively repeated bytes within each 8-byte run, which roughly correspond to a pixel row being the same as the row above it:


Then it encodes which bytes are repeats:


Interleaving these with the bytes that aren't consecutive repeats gives the isolated packet PB8 representation:


But because some specific data patterns for a single plane (all $00, all $FF, identical to the first, or the ones' complement of the first) are so common, PB53 has short codes for them. The code for eight $00 bytes is $80, producing the following 7-byte PB53 representation:


The compression format used in Codemasters games (cracked by tokumaru) and an improved format designed by tokumaru are more horizontal level pixel RLE. Because they run once for each pixel rather than each byte, they take longer to decompress, but in some cases, they perform better.

Compression is a much wider topic than just RLE, like in the OP. "Handbook of data compression" was a nice read, though bit heavy at 1370 pages.

As long as there's redundancy, there's potential for compression. Even at the byte level there's a lot of redundancy in NES tiles, but you'll find even more at the bit level. Even if there isn't much redundancy within individual tiles, there are always compression schemes that reuse previously processed data (in this case, tiles).

Here's a cool article about 2-bit graphics compression at the pixel level.

Even in a highly irregular glyph set like the wrecking balls font, many lines are shared between glyphs. C, G, O, P, Q, R share the same two top lines, for example. Had the type face been a regular serif, it would also have included E, F, and S, and possibly T, J. Numbers can be even more uniform. Would it be worth it customizing a compression format for a generic numeroalphabet? (Given that versals only is a pretty small thing to compress in the first place).


EDIT: If the numeroalphabet is 2 colours only, they could be stored on top of each other in different bit planes.
Here's Z and H (selected because of different looking properties):

_________________
http://www.frankengraphics.com - personal NES blog

Storing them in different planes probably wouldn't gain you anything if you were already compressing. Most generic compression techniques will very effectively compress an empty bitplane already. (A long string of 0s has a very obvious redundancy to it.)

It is helpful once uncompressed, though, if you're trying to cram more data into the available 256 uncompressed tiles. Tepples has used this to render variable width font text in some of his stuff, at the expense of available palettes (example: RHDE).


When trying to come up with a compression scheme, you might think of ways that your data looks repetitive/redundant. A lot of obvious ways tend to be picked up easily by existing generic compression methods, though, so if you know about how they work you can use or adapt an existing technique to fit the types of redundancies you think it has.

A lot of times, a compression techniques involves automated analysis, which can find specific redundancies that wouldn't be easy to generate by human analysis. E.g. computing letter frequency within a text has a lot of applications, but to get the ideal encoding your compressor should probably be re-computing it and adapting its encoding every time the data changes.

That sounds like a good use for it. Sometimes, 'distant' background structures won't use more than two colours aswell, so reserving a field for graphics like that could potentially help giving scenes more richer/more varied detail.

I'm assuming decoding bitplane-storage is much faster than uncompressing?
Another use on the top of my head could be upper/lower case storage. A and a, B and b, etc, would be conveniently stored at the same cell address but at different planes, while 0-9 stores special symbols.

I'm also wondering if there's any good use for assymetrical bitplane storage (3 for 2 , rather than 1 for 1; crossing tile boundaries) although that seems unintuitive.

_________________
http://www.frankengraphics.com - personal NES blog

In some forms of compression, it might be able to make better predictions about 2-bit pixels in a bitmap or about 2 x 1-bit bitmaps of planes instead, in others it might not make a lot of difference. I don't think it'd make a big deal in the long run, probably more of a specific implementation convenience.

RAM usage often rules out the effective use of certain forms of compression. Like if your data doesn't unpack into a stream similar to what you have to send directly to $2007, you might need to buffer pieces of it, or even all of it, to reconstitute back into the native format. You could also use the CHR-RAM directly, just it'll be really slow trying to read it back in random access patterns.

Some compression methods, like the LZ ones, are more effective with more RAM, encoding redundancies by referencing data previously decoded but remembered. PNG compression, for example, requires up to 32k for its decompression algorithms.

I just realized i mixed up a few things. 'storage' should imply prg/chr rom. What i meant was pattern memory (in my native language, the corresponding terms are often mixed up in daily speech, even though there's appropriate technical terms).

So the question was meant as "keeping bitplanes asymmetrically in a portion of the pattern memory", ie. not really concerning compression. And "decoding bit-plane storage" was meant to be meaning "decoding bit-plane partitioned pattern memory". Pardon the mess...

_________________
http://www.frankengraphics.com - personal NES blog

Another possible compression scheme, is to first compare an 8x1 sliver with the one above. It can either be the same or different. If it is different, than it will divide the 8x1 sliver in half, and compare each half with the half above. Then if the 4x1 half slivers don't match, it will divide them in half again and compare it with the 2 pixels above. Then if the 2 pixels don't both match the 2 pixels above, it checks both pixels if they match or not.

If you need to do some per pixel compression, here's an efficient routine to convert between packed and planar for the NES.



In other words, it lines up the pixels into 2 bytes, and uses both bytes as X and Y indexes to a look up table.

Unfortunately I can't think of an easy way to do this with the SNES format.

6502 doesn't do that, you need to ASL twice.

Anyway, the pixel-oriented compression scheme I reverse engineered (from Codemasters) wrote bits directly to a planar buffer. If you can avoid such conversions in the first place, that'd be better.

This takes 9.75 cycles per pixel, whereas doing the typical shifting takes 14 cycles per pixel.