Reverse Engineering a Gameboy Advance game: Where is the Tilemap in the ROM? — Part 4

Bruno Macabeus
Nov 7 · 9 min read

This post is part of a series entitled Reverse Engineering a Gameboy Advance Game. Read the introduction here. Read the previous post here.

Translated by Benjamin Stauffer 💙


In the last chapter we managed to find where the tilemap is stored in Slow WRAM. Cool!
But where does that data come from? Considering that there is no other “WRAM” besides Slow and Fast, a good guess would be that the source of the data would be the game cartridge itself, that is, the ROM!

If this hypothesis is confirmed, that would be especially important and useful for us, since we need to have a file with this data to draw the tilemap in the editor. In this case, we must extract the data using IDA since, unlike No$GBA, IDA has a feature which makes it possible to extract data from memory to a file.
Therefore, let’s continue the flow we were walking: starting from B to find the origin A! The flows are more or less like this:

Philosophically speaking, this flow is infinite in both directions. We could stretch to the left including the electronics of the cartridge or the thinking of the level designer who designed such a level, just as we could stretch to the right with the player seeing the level. However, this subset is sufficient for our case.
In this way, we need to find where the level is stored in the ROM — and understand the way it’s stored. After all, it will probably be compressed, since developers are often compress a game’s assets.

Talking to a few colleagues, they always said it would be a challenge to deal with the compression of the tilemap, because besides identifying where the tilemap is stored, I would need to discover which compression algorithm was used, since I would need to reproduce it in order to extract the data from the ROM, and also in the level editor tool.
Well… But IDA shows an interesting graph of the memory use on the cartridge, and something that caught my attention was that there was a large gap space. So I thought, “Hey, could the tilemap not be compressed? After all, there’s a bunch of gap space…”

Graph showing the distribution of data stored in the ROM. The part in black is the gap space.

To confirm this hypothesis, I copied a part of the tilemap that I saw in No$GBA and searched for it in the ROM memory in IDA, using the Sequence of bytes (Alt+B) feature.
And unfortunately, I didn’t find it. Well, then it really must be compressed… and using some compression algorithm which I don’t yet know…
The closest we got to the source of the tilemap is the Slow WRAM, and that the tiles of our bridge are located at 02008432. Okay, so we’re going to eyeball it to infer where the tilemap starts in Slow WRAM (as I already explained, a tilemap represents a very characteristic structure: it’s spaced out with a lot of zeros, leaving a small set of different bytes and various bytes of the same values repeated in sequence). With this, I was able to infer that it starts at 020039EB, or at some address nearby.

Therefore, let’s continue our classic and boring step-by-step debugging… This time we need to start a level in the game and find when the tilemap starts to be drawn.
Doing that, I arrived at an important instruction at address 08051440: swi 0x11. Soon after that, a part of the tilemap is written:

Shortly after the highlighted instruction is executed, the tilemap is written. The beginning of the tilemap is highlighted in the lower panel.

Do you remember swi? I already spoke briefly about this instruction before, and now I need to explain it in more detail, since we’ll use it a lot from now on.

swi” is an abbreviation for software interrupts (which is also called BIOS calls) — that already gives you a clue, right? The GameBoy Advance has a BIOS. In general computer architectural terms, the BIOS is a firmware whose objective is to initialize the physical components of the system it’s connected to, as well as also mapping them to the system which will operate the device.
These “physical components” mentioned may be for example, a keyboard and mouse. However, the device may be made up of other more specialized hardware, which is exposed as “functions” to the system, being very fast since they are very close to the metal. In the case of the GBA, which is a hardware specialized for games, the BIOS exposes various functions frequently used in games, such as controlling music and calculating arctangents… and among these functions, there is also a data compressor and decompressor included! Each function has an associated numerical value, which must be passed as a parameter to the swi instruction.

In this case, the instruction swi 0x11 exposes the decompression algorithm LZ77, which is very useful when there are portions of repeated data (and in a tilemap we have exactly that!). It’s very curious to think that the GBA, a relatively small and cheap console, already had powerful compression algorithms being executed in the hardware level in the year 2000s. The way to “pass parameters” and “get the function return” for the swi instructions is very peculiar: basically it’s done through registers. Look at an example in the div function (swi 0x06):

Input:
- R0: numerator
- R1: denominator

Output:
- R0: numerator / denominator
- R1: numerator % denominator
- R2: abs(numerator / denominator)

In case you want a more general view of swi, you can read this chapter in the GBA manual.

With all of that explanation, let’s analyze that instruction we found: swi 0x11.
According to the GBA specification, 0x11 refers to LZ77UnCompWram. The address where it will collect the data to be decompressed is defined in R0, while the destination where the result will be written is the address specified in R1.
The pieces of the puzzle begin to fit together when looking at the values of these registers shortly before the swi 0x11 is executed:

The value of R1 (the address of the decompression output) is very close to what we have said is the address where the tilemap starts, 020039CC to 020039EB! But now we need to understand where the data input came from, the address pointed to by R0: 0200F698

Looking at the assembly, something that caught my attention was the line a bit before the swi 0x11, the instruction swi 0x13:

Looking at the spec, the swi 0x13 refers to HuffUnComp, which deals with decompression using another algorithm: Huffman. It also uses R0 as the address of the input and R1 as the address of the output.
And putting a breakpoint there, check it out: it writes exactly to where the other swi instruction will read shortly after! Besides that, it gets its data directly from the ROM, at address 0x81B27FC!!
In other words: the game developers decided to compress the level using two compression algorithms, and between the execution of one and the other a temporary buffer is used.

Studying and talking with other people, the combination of Huffman and LZ77 is very popular. While LZ77 removes repetition in a portion of data, Huffman reduces the quantity of symbols in a sequence proportional to its frequency. This answer on Stack Overflow clarifies why the developers chose to use both in the game Klonoa. There is a very popular algorithm which exactly addresses the use of these two algorithms together: deflate. This algorithm is used in formats like ZIP and PNG.

Okay. Let’s go to the address in the ROM which serves as the source for the decompression of the tilemap, that is, the address 0x81B27FC.

Note that IDA Pro has very good static analysis, such that it’s sufficient to leave your cursor on one of the lines of assembly, or on one of the bytes of the address when you’re in the Hex View mode, and it already says how far this memory dump goes. And we easily manage to extract this to a file, using the Export data (shift + e) tool!

But there isn’t much benefit in having just the compressed binary of the tilemap, right? And so we need to find a way to decompress it!
The first idea that came to mind to accomplish this was to study the two compression algorithms used… and… well… My head was spinning just trying to understand them, and so imagine when it comes to implementing all this?? And besides that, the GBA could use a different version of these algorithms, which would complicate it even more…
And then I thought of a better idea: let’s use one of the biggest advantages of developing something using a very popular console, the community!
So I started looking around to see if anyone had already developed some code to compress/decompress data using the algorithms of the GBA… and look, someone has already done exactly that!

Someone in 2011–2012 wrote open source C code with the different algorithms for compression/decompression for the GBA, you just have to pass the compressed file’s path to an executable and it will be overwritten with the decompressed version. Fantastic, no? So let’s use it!
We need to recreate exactly the same steps done in the game: first decompress using the Huffman, and then using the LZ77.

When I went to decompress the binary using ./huffman.exe -d dump, I got the message “WARNING: unexpected end of encoded file!” … well … for the moment, I ignored it, let’s go ahead and see what happens.
When I went to decompress the LZ77, I noticed there were multiple similar executables: lze, lzss, and lzx. As I had some doubt about which one would be correct, I tested the decompression with all of them, and only the lzss worked correctly (I believe that lzss = lz seven-seven = LZ77) using the command ./lzss.exe -d dump, but again I got that same alert: “WARNING: unexpected end of encoded file!”
Again I got the message saying it got an unexpected end… and I saw that the file resulting from the decompression, while correct, was incomplete: it contained the start of the level tilemap, but it wasn’t complete.
Connecting that fact with the warning messages, it’s very clear that it’s because it’s missing data to decompress, but that’s strange, since I’d extracted the entire portion that IDA selected automatically!! Could it be that I needed to extract a bit more? It doesn’t cost anything to test that hypothesis, so let’s go!

Just as I described, after putting the breakpoint on the swi 0x11 instruction, I managed to see when it started to decompress the tilemap. And here’s an additional detail: this instruction is called more than once. So certainly there’s one more dump in the ROM that we need to extract. So I used IDA to extract next to the auto-selected region at 0x81B27FC all of the auto-selected portion after it. Extracting these two regions of memory, I was able to run the decompression executables without receiving any alerts!

And now, comparing the binary with what I see in memory in No$GBA, the tilemap is completely extracted!!

On the left side is No$GBA with the memory region of the tilemap, and on the right is IDA showing the decompressed tilemap.

This is completely fantastic, as we’ve now managed to extract the tilemap from ROM, as well as understand how it works!!! Now we’re closer than ever to plotting the tilemap in our editor to create custom levels! But always remember: this all started with a very simple question, “how can I stretch the bridge?”

Of course, there are still many questions to answer, like for example, “we have a ‘linear’ memory dump, so how do we plot the tilemap, which is a 2D plane?” and also a much more obvious question comes to mind, “how are we going to plot all this?”

We’re going to answer all of those questions in our next chapter!

Next post: Making the tilemap! (available when the translation is finished)

Source of images used in the flow graph:
- Gameboy:
unixtitan.net/explore/gameboy-vector-old/
- Memory:
flaticon.com/free-icon/ram_173754
- Cartridge:
iconfinder.com/icons/1531694/cart_cartridge_chip_game_nintendo_retro_snes_icon

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade