Tile compression: How can it ever pay off?
Moderator: Moderators
Tile compression: How can it ever pay off?
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.
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
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Re: Tile compression: How can it ever pay off?
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.
Re: Tile compression: How can it ever pay off?
A tile is 16 bytes. A tile that is mostly zeros could be represted (in compression) by 8 bytes.pixel consists of merely two bits
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
Re: Tile compression: How can it ever pay off?
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.
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
Code: Select all
3c 69 << 7e 69 << << 00 00 << << << << << << <<
Code: Select all
00100110 01111111 = 26 7f
Code: Select all
26 3c 69 7e 69 00 7f 00
Code: Select all
26 3c 69 7e 69 00 80
Re: Tile compression: How can it ever pay off?
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?
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.
Here's a cool article about 2-bit graphics compression at the pixel level.
- 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?
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).
Here's Z and H (selected because of different looking properties):
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):
- rainwarrior
- Posts: 8734
- Joined: Sun Jan 22, 2012 12:03 pm
- Location: Canada
- Contact:
Re: Tile compression: How can it ever pay off?
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.
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.
- 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?
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.rainwarrior wrote: if you're trying to cram more data into the available 256 uncompressed tiles.
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.
- rainwarrior
- Posts: 8734
- Joined: Sun Jan 22, 2012 12:03 pm
- Location: Canada
- Contact:
Re: Tile compression: How can it ever pay off?
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.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.
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.
- 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?
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...
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...
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
Re: Tile compression: How can it ever pay off?
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.
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
Re: Tile compression: How can it ever pay off?
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.
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
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?
6502 doesn't do that, you need to ASL twice.psycopathicteen wrote:Code: Select all
asl #2
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.
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
Re: Tile compression: How can it ever pay off?
This takes 9.75 cycles per pixel, whereas doing the typical shifting takes 14 cycles per pixel.