It is currently Wed Oct 18, 2017 10:43 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 20 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: Sat Jan 28, 2017 6:25 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1401
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


Top
 Profile  
 
PostPosted: Sat Jan 28, 2017 8:04 pm 
Offline

Joined: Mon Sep 27, 2004 2:57 pm
Posts: 1248
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.

Top
 Profile  
 
PostPosted: Sat Jan 28, 2017 8:04 pm 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 1772
Location: DIGDUG
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.

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


Top
 Profile  
 
PostPosted: Sat Jan 28, 2017 8:18 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19099
Location: NE Indiana, USA (NTSC)
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 1590 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.


Top
 Profile  
 
PostPosted: Sun Jan 29, 2017 3:47 am 
Offline

Joined: Tue Oct 06, 2015 10:16 am
Posts: 555
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.


Top
 Profile  
 
PostPosted: Sun Jan 29, 2017 5:36 am 
Offline
User avatar

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


Top
 Profile  
 
PostPosted: Sun Jan 29, 2017 5:37 am 
Offline
Formerly WheelInventor

Joined: Thu Apr 14, 2016 2:55 am
Posts: 898
Location: Gothenburg, Sweden
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 1515 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 1509 times ]

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


Top
 Profile  
 
PostPosted: Sun Jan 29, 2017 7:55 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5718
Location: Canada
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.


Top
 Profile  
 
PostPosted: Sun Jan 29, 2017 8:18 am 
Offline
Formerly WheelInventor

Joined: Thu Apr 14, 2016 2:55 am
Posts: 898
Location: Gothenburg, Sweden
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.

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


Top
 Profile  
 
PostPosted: Sun Jan 29, 2017 9:38 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5718
Location: Canada
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.


Top
 Profile  
 
PostPosted: Sun Jan 29, 2017 10:14 am 
Offline
Formerly WheelInventor

Joined: Thu Apr 14, 2016 2:55 am
Posts: 898
Location: Gothenburg, Sweden
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


Top
 Profile  
 
PostPosted: Sun Jan 29, 2017 5:50 pm 
Offline

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


Top
 Profile  
 
PostPosted: Fri Feb 10, 2017 10:55 pm 
Offline

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


Top
 Profile  
 
PostPosted: Sat Feb 11, 2017 9:44 am 
Offline
User avatar

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


Top
 Profile  
 
PostPosted: Sat Feb 11, 2017 10:03 am 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2286
This takes 9.75 cycles per pixel, whereas doing the typical shifting takes 14 cycles per pixel.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 20 posts ]  Go to page 1, 2  Next

All times are UTC - 7 hours


Who is online

Users browsing this forum: Bing [Bot], Google [Bot] and 6 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group