Tile compression: How can it ever pay off?

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Tile compression: How can it ever pay off?

Post by DRW »

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.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: Tile compression: How can it ever pay off?

Post by Drag »

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.
Last edited by Drag on Sat Jan 28, 2017 8:05 pm, edited 1 time in total.
User avatar
dougeff
Posts: 3079
Joined: Fri May 08, 2015 7:17 pm

Re: Tile compression: How can it ever pay off?

Post by dougeff »

pixel consists of merely two bits
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
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Tile compression: How can it ever pay off?

Post by tepples »

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.
pb53_illustrated.png
pb53_illustrated.png (1.44 KiB) Viewed 4462 times
This glyph for 'A' transforms into the following tile data:

Code: Select all

3c 69 69 7e 69 69 69 00  00 00 00 00 00 00 00 00
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:

Code: Select all

3c 69 << 7e 69 << << 00  00 << << << << << << <<
Then it encodes which bytes are repeats:

Code: Select all

00100110  01111111 = 26 7f
Interleaving these with the bytes that aren't consecutive repeats gives the isolated packet PB8 representation:

Code: Select all

26 3c 69 7e 69 00  7f 00
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:

Code: Select all

26 3c 69 7e 69 00  80
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.
calima
Posts: 1745
Joined: Tue Oct 06, 2015 10:16 am

Re: Tile compression: How can it ever pay off?

Post by calima »

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.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Tile compression: How can it ever pay off?

Post by tokumaru »

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.
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Re: Tile compression: How can it ever pay off?

Post by FrankenGraphics »

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).
wb_font.bmp
wb_font.bmp (8.12 KiB) Viewed 4388 times
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):
z_h.png
z_h.png (580 Bytes) Viewed 4382 times
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Tile compression: How can it ever pay off?

Post by rainwarrior »

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.
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Re: Tile compression: How can it ever pay off?

Post by FrankenGraphics »

rainwarrior wrote: if you're trying to cram more data into the available 256 uncompressed tiles.
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.
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Tile compression: How can it ever pay off?

Post by rainwarrior »

FrankenGraphics wrote: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.
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.
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Re: Tile compression: How can it ever pay off?

Post by FrankenGraphics »

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...
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Tile compression: How can it ever pay off?

Post by psycopathicteen »

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.
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Tile compression: How can it ever pay off?

Post by psycopathicteen »

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

Code: Select all

lda pixel_0
asl #2
ora pixel_2
asl #2
ora pixel_4
asl #2
ora pixel_6
tax

lda pixel_1
asl #2
ora pixel_3
asl #2
ora pixel_5
asl #2
ora pixel_7
tay

lda planar_lo,x
asl
ora planar_lo,y
sta bitplane_0

lda planar_hi,x
asl
ora planar_hi,x
sta bitplane_1
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.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Tile compression: How can it ever pay off?

Post by tokumaru »

psycopathicteen wrote:

Code: Select all

asl #2
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.
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Tile compression: How can it ever pay off?

Post by psycopathicteen »

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