Donut NES CHR compression

A place where you can keep others updated about your NES-related projects through screenshots, videos or information in general.

Moderator: Moderators

JRoatch
Formerly 43110
Posts: 422
Joined: Wed Feb 05, 2014 7:01 am
Contact:

Donut NES CHR compression

Post by JRoatch »

(2023 Update)
Donut is the sequel to my previous codec Bagel.

Donut is a CHR compression with a fixed block size of 64 bytes, and saves about 45% in size. Compared to 47% saved by Tokumaru's compression. Donut is also Fast enough to decode directly into a PPU buffer format for games like RHDE. Famously used for the menu Action 53 Vol. 4: Actually 54.

Attached is the 2023 update which is data compatible with the format used in Action 53.

More info at https://jroatch.nfshost.com/donut-nes/
Attachments
2023-12-21_donut-nes.zip
(94.69 KiB) Downloaded 18 times
Last edited by JRoatch on Wed Dec 20, 2023 8:43 pm, edited 3 times in total.
User avatar
pubby
Posts: 583
Joined: Thu Mar 31, 2016 11:15 am

Re: Donut NES CHR compression

Post by pubby »

up-to-date version is on github, for anyone looking

https://github.com/jroatch/donut-nes
User avatar
slembcke
Posts: 172
Joined: Fri Nov 24, 2017 2:40 pm
Location: Minnesota

Re: Donut NES CHR compression

Post by slembcke »

I'm really fascinated by this. So far I've been using lz4 for all of my compression needs. Simple and ubiquitous. On the other hand, it doesn't do a great job compressing character tables compared to name/attribute data. My thoughts about how to improve the situation haven't gone much further than "uh... preprocess with XOR maybe?"

Donut gives slightly better compression than straight lz4, using only ~20 bytes more code. If I had 3 full character tables, it would even pay off to have both compressors for different types of data. Additionally, lz4 really requires turning off the PPU while decompressing. Donut on the other hand seems to work with a small CPU side buffer and looks relatively easy to put in a coroutine and pause for the NMI when the buffer gets full. Maybe it's even fast enough to stream a couple tiles per frame?
JRoatch
Formerly 43110
Posts: 422
Joined: Wed Feb 05, 2014 7:01 am
Contact:

Re: Donut NES CHR compression

Post by JRoatch »

Thanks,
Working with some form of coroutines was part of my thinking when designing this (and the codec it descended from).

but in practice there is is one complication I've found with it's current design, the requirement to retain the buffer for the "Reuse/Duplicate previous block" feature. In my usage I found that It gets largely used to code a sequence solid color blocks, since solid color blocks takes 2 bytes, but duplicate blocks takes only 1 byte.

I'm contemplating making a breaking change where I get rid of "Duplicate blocks", and make solid color blocks only 1 byte. That will remove the requirement to save the 64 byte buffer, making it easier for further routines to transform the uncompressed data.
(C encoder easier to program as well)

I'm not sure about using it directly in vblank as each (non duplicate) 64 byte block takes 1293~7247 cycles.

------
I'm also glad to hear about the viability of lz4 on the NES.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Donut NES CHR compression

Post by tepples »

Duplicates were important for the Action 53 data set. Games with CHR ROM often have duplicate "X" tiles to mark unused tiles, and there was an intent to interleave different 4K or 8K CHR banks in case a game uses $2000 bit 4 (background pattern table base address) or CNROM to animate a subset of the tiles.

Would it be better to make a format option to allow or disallow dupes?
JRoatch
Formerly 43110
Posts: 422
Joined: Wed Feb 05, 2014 7:01 am
Contact:

Re: Donut NES CHR compression

Post by JRoatch »

And that was precisely the reason I held on to it for as long as I did.

but even the way I'm doing it now (comparing a match of 64 bytes) is subpar when compared to pb53 (matches of 16 bytes).
I can do better, and I have plenty of codec header space to do it with (all header bytes >= 0xc0).

and even if I don't make up better compression schemes, I believe I have the option to just turn those X tiles to solid black ones.

Edit: didn't see the second half of your post

I have some ideas about now to handle duplicates between pages, and I think taking out the duplicate block feature in the core decoder will help with how that will work.
User avatar
slembcke
Posts: 172
Joined: Fri Nov 24, 2017 2:40 pm
Location: Minnesota

Re: Donut NES CHR compression

Post by slembcke »

JRoatch wrote:the requirement to retain the buffer for the "Reuse/Duplicate previous block" feature
Not an issue if you reserve the buffer bytes exclusively for Donut though right?
JRoatch wrote:I'm not sure about using it directly in vblank as each (non duplicate) 64 byte block takes 1293~7247 cycles
Nah. I mean fill the buffer, yield, copy it to the PPU during NMI, then resume during the next frame. It would require modifications, but the source isn't that complicated. This is basically impossible with lz4 without extra work RAM.
JRoatch wrote:I'm contemplating making a breaking change
I'm sort of curious about that. Donut isn't really an archival format. Why worry too much about breaking changes? Speaking personally, since my tools are a build dependency, I keep them in the same repository as my project (or in a git submodule, etc).
JRoatch
Formerly 43110
Posts: 422
Joined: Wed Feb 05, 2014 7:01 am
Contact:

Re: Donut NES CHR compression

Post by JRoatch »

slembcke wrote:Donut isn't really an archival format. Why worry too much about breaking changes?
True.
It's from a mental habit I picked up from reading too many data format documents.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Donut NES CHR compression

Post by tepples »

slembcke wrote:
JRoatch wrote:the requirement to retain the buffer for the "Reuse/Duplicate previous block" feature
Not an issue if you reserve the buffer bytes exclusively for Donut though right?
It's 64 out of 2048 bytes that the rest of your program can't use while a decompression is running in the background.
User avatar
slembcke
Posts: 172
Joined: Fri Nov 24, 2017 2:40 pm
Location: Minnesota

Re: Donut NES CHR compression

Post by slembcke »

Sure, but you could say that about anything that uses RAM. If streaming to CHR RAM is considered important, 64 bytes of RAM might be considered a reasonable cost. It's not like it's being forced onto anybody. At this point I simply think it would be interesting if it could be done. :p
JRoatch
Formerly 43110
Posts: 422
Joined: Wed Feb 05, 2014 7:01 am
Contact:

Re: Donut NES CHR compression

Post by JRoatch »

Anyway I went ahead made some breaking changes in the basic block format, and edited the first post pointing to the current new locations.

I also managed to complete the C version of the encoder, and I really like the 1200x speedup compared to the python version.
User avatar
Goose2k
Posts: 320
Joined: Wed May 13, 2020 8:31 am
Contact:

Re: Donut NES CHR compression

Post by Goose2k »

The original links to this library appear to be dead. Is there a new home for donut? (the wiki links are also dead)
JRoatch
Formerly 43110
Posts: 422
Joined: Wed Feb 05, 2014 7:01 am
Contact:

Re: Donut NES CHR compression

Post by JRoatch »

I'm slowly working my way to re-posting this hopefully sometime before summer. In the mean time I found that the decoder in the Action 53 github repository is out of date compared to the published ROM of Volume 4. So at least for now, I posted the most recent version of the decoder to the wiki. It should be the same binary format as encoded by tools in Action 53
JRoatch
Formerly 43110
Posts: 422
Joined: Wed Feb 05, 2014 7:01 am
Contact:

Re: Donut NES CHR compression

Post by JRoatch »

So occasionally I check in the Nesdev Discord (with disposable sessions due to ... reasons) and there's concern about the copyright / IP licensing of all this. My intent has always been that the block format, and the ability to encode and decode the format, aught to be public domain and unencumbered software as much possible, free to incorporate in anything.

The GPL3 licence should only apply to the copyrighted text of some specific encoders and not to any underlying algorithm or idea. That being said I have laying on my hard disk a unfinished more moulder (single header style) C version of the encoder that I can polish up if a more liberally licensed file is needed.

I think held back on that updating donut due to being uncertain what people's actual needs were.
User avatar
pubby
Posts: 583
Joined: Thu Mar 31, 2016 11:15 am

Re: Donut NES CHR compression

Post by pubby »

Someone on the discord mentioned a bug in the decoder. donut_block_buffer does not refer to the actual buffer, but 64 bytes behind it.

I love/use donut, but it's been hard to find ever since it lost its Github page. The wiki has its merits, but donut is underused because most people have no clue it exists. This thread containing dead links isn't helping. Having a nicer presentation would go a long way. (e.g. https://bisqwit.iki.fi/source/tokumaru.html )
Post Reply