[GBA] Donkey Kong Country 2: Progress and LZ77 Hell

[Homer177]

Progress so far

I've officially gotten back into improving DKC2 on the GBA and it's been...interesting. You could say it's one step forward and several steps backward. I managed to improve palettes up to Barrel Bayou. The interesting part is that I managed to improve palettes themselves via the Curves tool in GIMP, with surprisingly good results. I've done my best to restore them to SNES quality, but I'm not sure that's doable, not entirely anyway. That being said, I like the results I've gotten so far.

I've also hit a wall when it comes to dealing with LZ77 compression. Using LZ77 Restructor2, I managed to extract all the palettes for the levels, but the problem is when I go to insert palette binaries edited through YY-CHR's palette editor, other binaries for level palettes are lost entirely. Can anyone tell me why this happens and how to work through it? I can't move further until I resolve this.

I might have to consider posting some video of what I've done so far as I don't think images do it justice.

[Solid One]

When you deal with compressed data, you need to worry about the size of the compressed data: If, after editing the palettes and recompressing them back, the size of the compressed data is bigger than the original, then you might have problems if forcing the insertion. You might be overriding other palettes in this step.

You might consider inserting the new palettes to the end of the ROM and then editing its pointers to point to the new address. That's what I did on some GBA translations in the past.

[Homer177]

It's times like that I'm glad I keep a backup. How would I go about inserting at the end of the rom and then edit the pointers? Is this something I can do in Restructor or do I actually need to program it?

[FAST6191]

Still surprised to see compressed palettes -- they are usually not worth compressing (random colours tending not to make for good compression ratios) so devs rarely do. Is what it is though.

Shouldn't be a programming thing. Indeed it might even be one of the few times where a basic hex editor is the tool for the job.

If you know where they are in the base ROM then chances are will be something in the form 08?????? where the ?? are the location in the ROM give or take flipping because big vs little endian. GBA pointers are a bit more complicated than that if you want to get down to it but in terms of practical reality 90% of ROMs and hacks thereof are sub 16 megabytes (though above just means 09?????? becomes a thing) and the upper mirrors (which by default have a lesser wait priority, though could be changed) are basically unused, while memory addresses are less common (the GBA cartridges are actually quite far when all is said and done, hence the cost of flash carts) so "08 in front of the address" is a good enough shorthand.

The whole ROM is visible in memory for all games save some homebrew, flash carts and real oddities ( https://mgba.io/2015/10/20/dumping-the-undumped/ ) so put it where you like, though common courtesy for flash cart users means try putting it at the end of the ROM data proper (things being made up to 4,8,16 or 32 megabytes with 00 or FF padding) rather than the size of the ROM as was done for a few things back when.

You can often find these pointers by simple searching in hex, indeed searching for 08 and finding a sea of them a relatively fixed number of bytes apart* will be how I find useful things (I don't know what** but I know it is something the devs/compiler presumably cared about and how big it is) but different topic there.
Though the easier way is to note where it is in the ROM, set a break on read to that area and working back a few steps will find the pointer you care about (presumably with another read to the ROM for that pointer a few steps before that but might be more calculated from a base). Change this pointer to be the end of the ROM and your space issues start to make more sense. Hopefully it is the one pointer (game internally doing some kind of for level 4 then take base pointer, add 4 x palette length to get final) or field thereof you can do an offset from (everything will presumably be shifted along by the same fixed amount after all)

*08080808 is a valid pointer, indeed perhaps more than some others -- graphics might need things on a 16 bit alignment where some general things go for 8, indeed this can be problem with the more automated compression searching tools as there are different compression flavours to reflect that (usually referred to as VRAM safe. http://members.iinet.net.au/~freeaxs/gbacomp/#BIOS%20Decompression%20Functions http://problemkaputt.de/gbatek.htm#biosdecompressionfunctions http://www.coranac.com/tonc/text/video.htm https://www.cs.rit.edu/~tjh8300/CowBite/CowBiteSpec.htm#Graphics%20Hardware%20Overview for some nice links). To that end while a gap of 3 bytes (or 4 depending upon your view, maybe more if the text or something includes formatting data between pointers) might be the generally expected pattern it might be less.

**though the values of the pointers themselves can give a clue -- text is fairly random in length (though depending upon if pointer = end of line or not then it can be more fixed, also shorter than say music), graphics is fairly fixed (8x8 and such tiles don't leave much possibility for variation), music

[[Unknown]]

In case it helps, I wrote my own LZ77 compressor that generally creates smaller output than others I've found.  It's still algorithmically compatible with the GBA decompressor, it just makes smarter decisions (plays chess a bit with early sacrifices.)

If your difference is just a few bytes, it might help.  Unfortunately, I didn't make a separate command line or anything, it's just a C++ function.

https://github.com/unknownbrackets/tomatotrans/blob/4d4447a965c59cbb0ccda1176ae83870ad116528/inserter/lz77.cpp

For example, `compressedData = compress_gba_lz77(data, LZ77_VRAM_SAFE)`.

In this patch, I used it to optimally replace tilesets (palettes were uncompressed in my case.)
https://github.com/unknownbrackets/tomatotrans/blob/d2127be933b697e0518ab2503c6c243d1f644353/inserter/images.cpp#L260-L262

In my case, I had free space, so if it's unable to compress a particular tileset I simply relocate it (modifying all places that reference it in the game code.)

-[Unknown]

[Cris1997XX]

I still pray for your success, hoping that Donkey Kong Country 2 GBA (And probably 3 as well) will finally receive the color restoration that they deserve. Good luck and keep doing God's work! P.S: Rare really loved palette compression, eh?

[Homer177]

@FAST6191 That's what I'm unsure about. As far as I can tell, the compression happens in-game while the raw data is uncompressed. Sprite palettes aren't treated in this way, though. In fact, I finished them some time ago but it doesn't feel right just releasing that without giving the levels the same treatment.

When I open up the rom in LZ77 Restructor, I notice several addresses that contain just one byte. What's that about?

[FAST6191]

Compression detection is not an exact science -- there is often a magic number and then a size, if that value (10h in early DS games which is the same style as/compatible with GBA stuff, 11h in later, 40h in some rare later cases for LZ, think it was mostly 10h for the GBA too) and a "valid" size appears then "there might be compression here" gets tripped. It only gets marginally more advanced when some things will support SWI logs (SWI = software interrupt, the technical name for what most of emulation, homebrew and ROM hacking will know as BIOS calls) as the destination and size of those is easy enough to log and feed to an external tool later, knowing you will get something interesting as well.

Compression in game would be very odd indeed as there is very little point. Palette animations are a thing and people can edit the palettes in real time to effect a change (I usually point people at Mr Driller 2 rainbow blocks and summon night 2 save swords, check whatever update in real time your emulator palette viewer has and it will soon become apparent).
Possible alternative. There is both a filtering and unpacking option available as part of the BIOS compression routines -- filtering reduces numbers to instead their differences and unpacking takes 1bpp (fonts being potentially two colour mean you can get away with that) and unpacks it to 4bpp that the hardware can use but I doubt that is the case for CGI generated/gradient sporting background colours. I have never seen huffman used for a palette before (while technically supported it is super rarely seen) but rebuilding that might be something as well.

[Homer177]

Interesting...I have tried editing the rom directly through GHex, but the results I get are somewhat weird given how the palettes are written in raw data. There are a lot of extra bytes that obscure what I'm looking for and that's difficult to work through.

[ShadowOne333]

Interesting...I have tried editing the rom directly through GHex, but the results I get are somewhat weird given how the palettes are written in raw data. There are a lot of extra bytes that obscure what I'm looking for and that's difficult to work through.

I remember stumbling upon this as well when trying to make a Colour Restoration for EarthBound's side of Mother 1+2 on GBA.

The thing is, I believe that the very same LZ77 compression used for palettes is what's giving you those odd resulsts with "extra bytes" in between. So you have like 3-4 palettes, and then some random byte (I believe it was sometimes a 00 or something) and that is enough to throw off the Hex editing.

I am not sure what tool could be used to handle these kind of palette compression.
I believe @marc_max was the one who did the DKC Colour Restoration with some custom tools he did, so perhaps contacting him would be a good idea to know how to handle this.

[Homer177]

I remember stumbling upon this as well when trying to make a Colour Restoration for EarthBound's side of Mother 1+2 on GBA.

The thing is, I believe that the very same LZ77 compression used for palettes is what's giving you those odd resulsts with "extra bytes" in between. So you have like 3-4 palettes, and then some random byte (I believe it was sometimes a 00 or something) and that is enough to throw off the Hex editing.

I am not sure what tool could be used to handle these kind of palette compression.
I believe @marc_max was the one who did the DKC Colour Restoration with some custom tools he did, so perhaps contacting him would be a good idea to know how to handle this.

I actually spoke to him about that before and he'd mentioned a tool he had used for the palettes of DKC1 on the GBA. Strangly enough Rare didn't use any kind of compression for that game.

LZ77 Restructor2 seemed to work but I ran into the problems mentioned above (other binaries disappearing). As far as I can make out, the level palettes are only contained in the first three binaries: 000EB140 contains palettes from Pirate Panic to Glimmer's Galleon, 000EC434 goes from Krockhead Klamber to Arctic Abyss, and 000EDBF4 contains the rest, including the Lost World levels.

Any time I insert the EB140 binary, 000EC434 goes missing outright. If I put that one back in, it messes up Barrell Bayou and Glimmer's Galleon, but levels from Krockhead Klamber on are unaffected. It should be worth noting that when I go to insert 000EB140, even VRAM safe, it appears to add around 700 bytes (4849 to 5531). That's probably the big issue, but I'm unsure exactly what the workaround is.

[ShadowOne333]

Have you tried seeing if you can find the pointers for each of the binaries?
Like doing a Hex search for "40 B1 0E", "34 C4 0E", "F4 DB 0E".

If you get a match for all three instances, try moving the entirety of the new palette data somewhere in the ROM where you think it's freespace (usually either a bunch of FFs or 00s), take note of the address where you're putting each new binary in, and modify the pointer values accordingly to your new addresses where you pasted the palette data.

[Homer177]

Have you tried seeing if you can find the pointers for each of the binaries?
Like doing a Hex search for "40 B1 0E", "34 C4 0E", "F4 DB 0E".

If you get a match for all three instances, try moving the entirety of the new palette data somewhere in the ROM where you think it's freespace (usually either a bunch of FFs or 00s), take note of the address where you're putting each new binary in, and modify the pointer values accordingly to your new addresses where you pasted the palette data.

I tried as you suggested in GHex (GNOME's native hex editor in Linux) and came up with nothing. However, 000EB140, 000EC434 and 000EDBF4 are memory addresses in the rom. That being said, just how would I point to a new addresses in a rom using Hex editing?