This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Tile compression: How can it ever pay off?

Tile compression: How can it ever pay off?
by on (#187944)
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.
Re: Tile compression: How can it ever pay off?
by on (#187946)
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.
Re: Tile compression: How can it ever pay off?
by on (#187947)
Quote:
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.
Re: Tile compression: How can it ever pay off?
by on (#187950)
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.

Attachment:
pb53_illustrated.png
pb53_illustrated.png [ 1.44 KiB | Viewed 3375 times ]

This glyph for 'A' transforms into the following tile data:
Code:
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:
3c 69 << 7e 69 << << 00  00 << << << << << << <<


Then it encodes which bytes are repeats:
Code:
00100110  01111111 = 26 7f


Interleaving these with the bytes that aren't consecutive repeats gives the isolated packet PB8 representation:
Code:
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:
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.
Re: Tile compression: How can it ever pay off?
by on (#187962)
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.
Re: Tile compression: How can it ever pay off?
by on (#187964)
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.
Re: Tile compression: How can it ever pay off?
by on (#187965)
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).
Attachment:
wb_font.bmp
wb_font.bmp [ 8.12 KiB | Viewed 3300 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):
Attachment:
z_h.png
z_h.png [ 580 Bytes | Viewed 3294 times ]
Re: Tile compression: How can it ever pay off?
by on (#187975)
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.
Re: Tile compression: How can it ever pay off?
by on (#187979)
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.
Re: Tile compression: How can it ever pay off?
by on (#187985)
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.
Re: Tile compression: How can it ever pay off?
by on (#187987)
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...
Re: Tile compression: How can it ever pay off?
by on (#188023)
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.
Re: Tile compression: How can it ever pay off?
by on (#188944)
If you need to do some per pixel compression, here's an efficient routine to convert between packed and planar for the NES.

Code:
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.
Re: Tile compression: How can it ever pay off?
by on (#188951)
psycopathicteen wrote:
Code:
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.
Re: Tile compression: How can it ever pay off?
by on (#188952)
This takes 9.75 cycles per pixel, whereas doing the typical shifting takes 14 cycles per pixel.
Re: Tile compression: How can it ever pay off?
by on (#188953)
tokumaru wrote:
6502 doesn't do that, you need to ASL twice.

It's the same with the 65816. It's a pseudo opcode. I've also seen him do "adx", which isn't a real instruction (you need to transfer the data from an index register, add, and then transfer it back).
Re: Tile compression: How can it ever pay off?
by on (#188955)
I never used adx. Maybe you're thinking of inx #2.


I thought about another approach. If you're doing vertical RLE, you can designate 16 registers (32 in the case of the SNES), each with 1 bit. Update the bits when there is a vertical color change, and for every row (except for entire rows being copied) "asl" and "ora" with every bit (for SNES, 2 bits at once). Now that I think about it, you can do a hybrid of vertical and horizontal RLE, using this method too.
Re: Tile compression: How can it ever pay off?
by on (#188956)
psycopathicteen wrote:
This takes 9.75 cycles per pixel, whereas doing the typical shifting takes 14 cycles per pixel.

I know it's faster, but that's assuming you're working with packed pixels in the first place. If the algorithm outputs bits that you can buffer in planar form right away, there's no need for any conversions at all.
Re: Tile compression: How can it ever pay off?
by on (#188969)
tokumaru wrote:
psycopathicteen wrote:
Code:
asl #2

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

I assume this assembler has a nonstandard feature to turn asl #2 into 0A 0A or asl #3 into 0A 0A 0A.
Re: Tile compression: How can it ever pay off?
by on (#189025)
I got started working on an RLE-based compression scheme for the SNES that would be fast enough but compact enough to run Darkstalkers on the SNES. Not sure if it's possible or not.