What data compression did Donkey Kong Country use?

Question

Donkey Kong Country was among the most ambitious, popular and influential of Super Nintendo games. Technically, its big trick was taking animations rendered on Silicon Graphics workstations and putting them on the cartridge to be displayed as SNES sprites.

The cartridge was 32 megabits (4 MB). That was pretty big for a fourth-generation game cartridge, and ROM chips were a significant contributing factor to total cost. If I were the developer, I would have tried very hard to compress the animations, background images and other data on the cartridge, decompressing them into console RAM for use. I'm sure the developers at the time must've thought of it.

What data compression techniques did they use?

Answer 1

I know this is an older question, but as somebody who has spent a considerable amount of time on this game I am going to place my notes on the decompression routine below. This isn't going to be so much a full description of the underlying algorithm (which is LZ-like), but rather a focus on the actual commands and structure used.

DKC2 is particularly interesting as the commands get encoded into the addresses of jump instructions in the same code bank. This doesn't have any impact on the size of compressed data, but it is an interesting design choice compared to alternatives like jump tables.

The below table is a summary of the operations possible within the compressed data stream. There are two sets of 16 operations broken into two tables. This split is because the compression stream works on 4 bit blocks at a time. While many of the commands between the two commands sets function the same, they are not all identical. The table is formatted into blocks of 4 bits being read into various parameters, and then the logical operations applied to each. This may not be the clearest visualization, but its meant as a compact summary to avoid this post getting excessively long. I will include a link to some (ancient) C++ decompression code I wrote and a fully commented copy of the ASM used to decompress data. The decompression route assembly commenting is quite detailed and goes into much more depth than this post.

Rough definitions:

• Copy: copy data from compressed stream to decompression stream
• Write: directly write the decoded byte, sequential writes decode additional bytes
• Backcopy: copy from a previous location in the decompression buffer to the current location
• Fill: Copy a byte N times (RLE)

You will notice command sets will toggle based on if an even or odd number of nibbles are read. This is why all of the secondary command set ignore the first nibble, as this corresponds to a nibble from the previous command set 1 instruction.

        case 0x00: cccc oooo                        if(oooo) copy(oooo) && executecmdset1() else exit()
        case 0x04: cccc oooo pppp                   write(oooopppp) && executecmdset2()
        case 0x08: cccc oooo pppp qqqq rrrr         write(oooopppp) && write(qqqqrrrr) && executecmdset2()
        case 0x0C: cccc oooo pppp qqqq              fill(ppppqqqq, oooo+3) && executecmdset1()
        case 0x10: cccc oooo                        fill(byte2, oooo+3) && executecmdset1()
        case 0x14: cccc oooo                        fill(byte2, oooo+3) && executecmdset1()
        case 0x18: cccc                             writeword(directword) && executecmdset2()
        case 0x1C: cccc                             write(directbyte1) && executecmdset2()
        case 0x20: cccc                             write(directbyte2) && executecmdset2()
        case 0x24: cccc oooo                        backcopy(oooo + 2, 2) && executecmdset2()
        case 0x28: cccc oooo pppp qqqq              backcopy(ppppqqqq + oooo + 3, oooo + 3) && executecmdset1()
        case 0x2C: cccc oooo pppp qqqq rrrr         backcopy(ppppqqqqrrrr + 0x0103, oooo + 3) && executecmdset2()
        case 0x30: cccc oooo pppp qqqq rrrr ssss    backcopy(ppppqqqqrrrrssss, oooo + 3) && executecmdset1()
        case 0x34: cccc                             backcopy(1, 1) && executecmdset2()
        case 0x38: cccc                             backcopy(2, 2) && executecmdset2()
        case 0x3C: cccc oooo                        copy(oooo << 1 + 7, 2) && executecmdset1()
        
        //be careful as oooo is the `high` nibble here
        case 0x3F: ---- cccc                             if(oooo) nibblecopy(oooo) && executecmdset2() else exit()
        case 0x43: ---- cccc                             copy(stream, 1) && executecmdset1()
        case 0x47: ---- cccc                             copy(stream, 2) && executecmdset1()
        case 0x4B: ---- cccc oooo pppp qqqq              fill(ppppqqqq, oooo + 3) && executecmdset2()
        case 0x4F: ---- cccc oooo                        fill(fillbyte1, oooo + 3) && executecmdset2()
        case 0x53: ---- cccc oooo                        fill(fillbyte2, oooo + 3) && executecmdset2()
        case 0x57: ---- cccc                             writeword(directword) && executecmdset1()
        case 0x5B: ---- cccc                             write(directbyte1) && executecmdset1()
        case 0x5F: ---- cccc                             write(directbyte2) && executecmdset1
        case 0x63: ---- cccc oooo                        backcopy(oooo + 2, 2) && executecmdset2()
        case 0x67: ---- cccc oooo pppp qqqq              backcopy(ppppqqqq + oooo + 3, oooo + 3) && executecmdset2()
        case 0x6B: ---- cccc oooo pppp qqqq rrrr         backcopy(ppppqqqqrrrr + 0x0103, oooo + 3) && executecmdset1()
        case 0x6F: ---- cccc oooo pppp qqqq rrrr ssss    backcopy(ppppqqqqrrrrssss, oooo + 3)  && executecmdset2()
        case 0x73: ---- cccc                             backcopy(1, 1) && executecmdset1()
        case 0x77: ---- cccc                             backcopy(2, 2) && executecmdset1()
        case 0x7B: ---- cccc oooo                        copy(oooo << 1 + 7, 2) && executecmdset1()

Here are the promised links:

Decompression routine in ASM (disassembled and commented): https://gist.github.com/p4plus2/c5c372fc00d55e05a6e116180c007099 (Can also be found in my disassembly linked in the comments of the initial post)

C++ implementation (This code is about 15 years old, use with caution!) https://gist.github.com/p4plus2/3fc958805defa74d4f8d7a216792ae33

I hope this has been interesting!

EDIT:

Some quick fun facts:

• Sprite graphics are not compressed, they are in the standard 4BPP format
• Animations are controlled via a loose "scripting" byte language
• Each frame of graphics encodes its collision data and other properties

Answer 2

A lot of the search engine results discuss compressing ROM files rather than how developers used techniques, algorithms, or special cart hardware to account for space limitations. MVG (Modern Vintage Gamer) has some really insightful videos regarding titles toward the end of the SNES' life that used tricks to crank out titles that went head to head with PSX ports at the time (Street Fighter Alpha 3 is a great example of this - https://www.youtube.com/watch?v=fB9GlZUYNUQ&t=8s).

1 or 2 specialized cartridge chips were created for realtime/fast decompression (https://en.wikipedia.org/wiki/List_of_Super_NES_enhancement_chips this was used in SA2 as mentioned above). CRT technology displayed low-resolution images quite well, so the lack of fidelity was not as jarring as when you display titles like DKC/Killer Instinct on panel tech. The cartoonish models they used were simple enough to translate well into 16-bit sprites. DKC2 and 3 appear to have some custom compression algorithms documented in various places online (google is your friend here). For the most part though, some wise choices are able to keep even some of the largest games under the 4MB ceiling.