Reverse Engineering 'A Link to the Past (GBA)' ep 2

During the last post we saw how to find, understand and patch some small parts of the game code to create cheats. This project was nice in itself but in the end it didn’t give us much insight on the game mechanics as we only guessed what a handful of instructions did to the game. In this post we will dig a bit deeper into the game code and uncover the inner workings of some game mechanics.

Where do we start ?

I recently read a pretty interesting article by Hugo Landau about reverse-engineering Broadcom BCM5719 firmware. The situation described in his post is pretty similar to ours, we only have a huge blob of binary code without any symbols and we have to make sense of it. One sentence in particular hit me:

There’s only one way to get started: try and find a clue, any clue, about what any part of it does, even just one part of it, and try and use that to infer what other parts of it do, and so on. The realisations tend to “snowball”; you figure out what one register does, and then suddenly you understand what another (previously unknown) block of code, which interacts with that register, does, which in turn results in you suddenly understanding what another register which that same block of (now comprehended) code relates to, and so on. Then at some point this “avalanching” process ends and you have to find a new “thread” to pull on to get it started again.

Last time we uncovered a few interesting functions inside the binary touching on Link’s attributes, but also touching on game entities attributes. We can try bootstrapping on the understanding (and the context) we got from the function we reversed and pull on these “threads” to make our work easier.

The entity system

The entity system is an interesting first target as functions from last time directly interact with it. Before trying to reverse the collision system, the spawning system or any other complex subsystem we need to make baby steps and gather more information. As Hugo said, the idea is to start small, try to make sense of a small part of the system and hope that our discoveries will snowball.

Going up the callstack

To start small we will attempt to find the number of entities in the system as it could give us good insight on data structures in memory down the road (think about array sizes). We can get our first constraint from the entity id at the top of the link_deal_dmg function (0x080c2160).

Graph dmg top

We know that this r5 value may represent the entity id as it is used as an index into an array to get the entity’s health (some part reversed last time). This r5 value is derived from r0, which is the only argument to the function (as r1 is overwriten before being read afterwards). The value in r0 is shifted left by 0x18 and then right by the same number which means that the top 24 bits of r0 are cleared, leaving us with only 8 bits for the entity id.

This gives us two important pieces of information. The entity id for now has a maximum range of 0-255 and the function’s argument is the current id. It means that if we go back the call stack we can gather more information.

Parent functions

The parent basic block containing the call is interesting.

Graph parent d1 call

The argument passed to our damage function is r4. This r4 represents the entity id and is used everywhere in the function. If we trace back where it is defined we get all the way up to the first block were we find a similar construct to the previous function. The entity id is not defined in this function but is agin passed as an argument.

Graph parent d1 top

The pattern is the same in the parent function, so we just go one level up the callstack again. This time the situation is different.

Graph parent d3 loop

The first block initializes the values used in the second block, we can already see the structure of a loop. The most important value is r1. It is set to 0xf (15) and the loop variable in the second block (r4) uses it to set its own value . The loop variable starts at 15 and decreases until it reaches 0 (as per the loop condition at 0x80c1c62). The loop counter is passed as an argument to the parent_d2 function … And this argument is nothing else than the entity id ! All this block does is iterate through all possible ids and call functions handling some npc related events (such as player <-> npc damage events). We now know that the maximum number of entities (NPCs) running concurently in the game is 16.

Entity types

We found interesting pieces of information by going up the callstack, let’s try to do the opposite now by analysing further the link_deal_dmg function.

Graph deal dmg full

By completely reading the damage block we can already guess what the last part of this function is about.

Graph deal dmg dmg

r4 contains a pointer to the array of hp values. The value is read and damage is substracted from it. The result is stored back in the array. The r0 at the end of our block contains the hp after damage. If the hp is below 0 the execution goes into the mess of spaghetti code, so this code must handle the death related events.

The second part of the code is nothing more than a huge switch case matching on a single value, we can guess that this must be the entity type id (as a boss would not die in the same fashion as common mob). We can put a breakpoint on the following block that is loading the matched value, load the game and kill a few enemies.

Graph deal dmg switch

> b 0x80c2398
> load 3
> c
Hit breakpoint at 0x080C2398
 r0: 0000004B   r1: 0000004B   r2: 03002230   r3: 00000FF2
 r4: 0300322E   r5: 0000000C   r6: 03002230   r7: 00000FF2
 r8: 00000000   r9: 0000075C  r10: 0000075C  r11: 00000000
r12: 00000005  r13: 03007E4C  r14: 0812C8A1  r15: 080C239A
cpsr: 0000003F [------T]
080C2398:  28EC     	cmp r0, #236
> c
Hit breakpoint at 0x080C2398
 r0: 00000042   r1: 00000042   r2: 03002230   r3: 00000FF2
 r4: 0300322F   r5: 0000000D   r6: 03002230   r7: 00000FF2
 r8: 00000000   r9: 0000077A  r10: 0000077A  r11: 00000000
r12: 00000006  r13: 03007E4C  r14: 0812C8A1  r15: 080C239A
cpsr: 0000003F [------T]
080C2398:  28EC     	cmp r0, #236
> c
Hit breakpoint at 0x080C2398
 r0: 0000004B   r1: 0000004B   r2: 03002230   r3: 00000FF2
 r4: 0300322D   r5: 0000000B   r6: 03002230   r7: 00000FF2
 r8: 00000000   r9: 00000769  r10: 00000769  r11: 00000000
r12: 00000005  r13: 03007E4C  r14: 0812C8A1  r15: 080C239A
cpsr: 0000003F [------T]
080C2398:  28EC     	cmp r0, #236

For this example I used the caste yard and killed all three npcs (2 normal guards and 1 strong guard) and we see only two types. So a normal guard’s type id is 0x4b while a strong guard’s type id is 0x42. We will check all of this in the next part.

The drop system

To check our hypothesis we will try to reverse-engineer the drop system. When a npc dies it can drop items. If we assume that the type system is shared between all game objects (npcs and items) we may be able to have a reliable way of dropping any object of our choosing (and thus test our assumptions about npcs type ids). To target the drop logic I used the same method as last time based on trace diffing. I added a small feature displaying the number of hits on each block as a comment, you will quickly see how it is useful.

In the trace I recorded I killed 6 npcs and got 5 drops, let’s load it in binja. We are looking for exactly two things. The first one is a block with a hitcount of 5 and the second one is that this block’s parent should have a hitcount of 6 (as we killed 6 npcs). This way we will see exactly where the random decision behind a drop is made. We are lucky with the diffed trace as it only contains a handful of blocks with a hitcount of 5. We can save their address and explore the result in the full trace to find the right block. After a few minutes we finally find the one, which is the block at address 0x80c6a10.

Item drop cond

All this code does is calling rand_byte and checking if the lsb is clear. If it is we jump to the code handling the item drop. If we dump the first few bytes of memory at r1 we see this:

0x0817216F: 01 01 01 00 01 01 01 DC E1 D9 E6 D8 D8 D8 D8 D9

The r5 in most of my test was constant and always indexing a 0x01 value. We can guess from this dump that r5 will only take values in the range [0-6]. r5 = 3 might be used to prevent drops in some situations.

As r5 will be constant in most cases we can say that item drops should be triggered about 50% of the time (as it only checks if the random byte is odd). Let’s do our first patch here. Having a 100% drop rate will make our debugging work easier. To do this we will simply replace the conditional jump at address 0x80c69f4 by an absolute jump, here is the r2 command:

r2 -w -qc "wx 0ce0 @ 0x80c69f4" <your rom>

With this out of the way let’s start reversing the child functions.

First child function

drop child d3

There is not much to see here. This function only casts the two arguments it got as parameters to u8 (using the same left/right shifting trick)

Second child function

drop child d2

As you can see from the number of comments, this function looks way more interesting. The arguments also look promising, they were guessed using the debugger and also from the context we will get in the next function. There is a lot to unpack here and sometimes the instruction are evaluated in a weird order, source code would be easier to read. You can decompile this with Ghidra/IDA but here I chose to do it by hand because it is small enough and a good learning experience. To do this we first start by translating the assembly statements directly into their equivalent C statements and we get this:

Afterwards we take this C code and refine it. We can replace the bit shifting operations by simpler and more explicit operation, keeping the same semantics. We can also combine the statements in a way that looks more like real code and rename the variables. We get the following code.

For those of you who are interested in learning about understanding assembly and how common programming construct look like when compiled, I highly encourage you to read the Reverse-Engineering for Beginners book.

This code contains a lot of interesting facts about the drop system. First, we notice the multiplication by 8 when indexing the array. It means that our array is not a 1d array (conceptually) but a 2d array containing slices of 8 elements. Each slice represents a drop table for an entity drop class (the drop_table_type argument). Another fact is that the drop in itself is not random (only whether there is a drop or not is). It is only based on your current number of kills modulo 8, something we can quickly guess through debugging. What this means in practice is that you can accurately predict what the next drop will be ! As an example, here is the drop table for the guards:

Kill count 0 1 2 3 4 5 6 7

You can test this yourself on an emulator or real hardware. The only constraint is that entities must share the same drop class, as the kill count is not shared between classes. If you want to study the drop tables you can find them starting at address 0x817217a.

You can see at the end of the function that the selected item is passed as an argument to the function sub_080c66a4, so let’s analyse it !

Third child function

We know from decompiling the previous function that the first argument is the entity id (r0) and the second argument is the drop id (r1). The first block of the function is pretty explicit about the drop logic.

drop d1 top

What happens is that the killed entity is replaced in the entity array by the item type id. Which seems to confirm that the type ids are shared between game objects (nps/items). The second part of the code is pretty interesting. At 0x80c66c6, r7 which contains the drop type id is compared against specific values, if one of these values matches, the codepath taken is different. Let’s patch the rom and see what these special values are ! We are going to replace the instruction at 0x80c66ba by movs r7, 0xe4, here is the r2 command:

r2 -w -qc "wx e427 @ 0x80c66ba" <your rom>

Combine this with the first patch for a better debugging experience.

Here is the result:

drop keys gif

What we have now is a reliable way of spawning any of the game entities. We can verify our previous assumption by replacing the drop type id by 0x42 (Strong guard):

drop guards

Or we can spawn chickens, because who doesn’t like chickens:

drop chicken gif

If you try this at home you may experience graphical glitches on most entities. I suppose the cause is that some graphical properties may not be initialized properly (the game may use the ones from the dead entity instead of the new one such as the palette).

Here is a small list of type ids if you want to reverse-engineer the drop tables or have fun:

Entity Name Entity type ID
Chicken 0x0b
Big sword guard (Purple) 0x41
Big sword guard (Green) 0x42
Small sword guard 0x4b
Spike ball guard 0x6a
Zelda 0x76
Agahnim 0x7a
Heart 0xd8
Green rupee 0xd9
Blue rupee 0xda
Red rupee 0xdb
1 Bomb 0xdc
Heart 0xdd
8 Bombs 0xde
Heart 0xdf
Small magic potion 0xe0
5 Arrows 0xe1
10 Arrows 0xe2
Fairy 0xe3
Small key 0xe4
Boss key 0xe5

Who let the guards out ?

Right now we have access to a lot of interesting data. In the last post we discovered where the entities hp values were stored and in this post we discovered the entity types. We only have one important piece of information missing, the entities positions.

A tale of two bytes

A lot of the reverse-engineering process is guided by assumptions about what the code does and how memory is organized. Through experience you build a mental library of common patterns and in most cases they will help you reverse-engineer faster. But in some cases every assumptions you made are wrong and you need to start over from scratch.

Everything started when I made the assumption that entities positions were stored as 16-bit values. It felt right for the position value to be on 16 bits since this game is a port from a 16-bit console (the SNES). I started looking for Link’s position values based on that assumption and soon after it was confirmed. Link’s position was stored as two 16-bit values (X and Y coordinates at addresses 0x30038f4 and 0x30038f0 respectively). The logical next step was to record a trace of execution and look for 16-bit load/store instructions (ldrh/strh) to find the entities positions and the associated arrays. Our work here is basically done right ? Wrong ! As it turned out the results gathered were meaningless, the few 16-bit load/store instructions were used for completely unrelated purposes. It made no sense at first. Entity positions could not be stored as 8-bit values as it would have been way too small and 32 bit values did not feel right as the original game used 16-bit ints. The fact that Link’s position was stored as a 16-bit value further added to the confusion. There were only a few possibilites. I decided to ditch the code tracing and rely on memory search.

Before starting we must know what we are looking for. As seen previously most (if not all) entity attributes were placed contiguously in memory and indexed by their id. What we are looking for is an array of 16 elements of unknown size. This fact will help us filtering the results after the search as we will be able to tell the difference between an isolated value and a group of values by quickly eyeing the memory state. Another problem is that we don’t know what values we are looking for and unfortunately the built-in memory tool in mgba needs a starting value. For this I built a small script that you can find here. It accepts files as an input, a bit width and a variation pattern composed of +/-/= and will filter the interesting values accordingly. To find the positions I recorded a single entity moving, dumped the memory and noted where it went. For example if an entity were to go left, right on the x axis and then stop the pattern would be “-+=”. I started looking for 16 bit values and was surprised again. None of them followed the variation pattern. Only 32-bit and 8-bit values remained and soon only 8-bit values remained. It didn’t make any sense.

But after a few minutes (or hours?) squinting at my screen and making some tests it dawned on me, the game uses 16 bit values for entities … but split into two 8-bit arrays for low and high bytes ! For those interested here are the arrays positions:

Coordinate Address
Y pos (low byte) 0x3003102
X pos (low byte) 0x3003112
Y pos (high byte) 0x3003122
X pos (high byte) 0x3003132

The game combines the bytes from the different arrays into a single 16-bit value to do its computations. The real hero here is peripheral vision. By playing the game and checking for changes in the corner of your eye you can quickly spot which area is synchronized to npcs movements. Also notice that the difference between array offsets further proves that there can only be 16 entities at once.

With all these information we can create a nice command for our debugger to pretty print entity related information. Here is an example of executing the command in the castle front yard:

> show-entities
--- Game Entities ---
ID:   0 X =  2656 Y = 33792 HP =   4 TYPE_ID = 0x42 NAME = Big green guard
ID:   1 X =     8 Y =     0 HP =   4 TYPE_ID = 0x4b NAME = Small green guard
ID:   2 X =   800 Y =  3296 HP =   4 TYPE_ID = 0x4b NAME = Small green guard
ID:   3 X =   707 Y =  3504 HP =   0 TYPE_ID = 0x00 NAME = unknown
ID:   4 X =   834 Y =  3343 HP =   0 TYPE_ID = 0x00 NAME = unknown
ID:   5 X =     0 Y =     0 HP =   6 TYPE_ID = 0x41 NAME = Big purple guard
ID:   6 X =     0 Y =     0 HP =   6 TYPE_ID = 0x41 NAME = Big purple guard
ID:   7 X =   699 Y =  2914 HP =   6 TYPE_ID = 0x41 NAME = Big purple guard
ID:   8 X =   924 Y =  2998 HP =   6 TYPE_ID = 0x41 NAME = Big purple guard
ID:   9 X =   332 Y =  3284 HP =   6 TYPE_ID = 0x41 NAME = Big purple guard
ID:  10 X =  1912 Y =  1949 HP =   6 TYPE_ID = 0x41 NAME = Big purple guard
ID:  11 X =  2216 Y =  1971 HP =   4 TYPE_ID = 0x4b NAME = Small green guard
ID:  12 X =  2216 Y =  1949 HP =   4 TYPE_ID = 0x4b NAME = Small green guard
ID:  13 X =  2057 Y =  2034 HP =   4 TYPE_ID = 0x42 NAME = Big green guard
ID:  14 X =  2063 Y =  1937 HP =   0 TYPE_ID = 0xd8 NAME = Heart
ID:  15 X =  2032 Y =  1945 HP =   0 TYPE_ID = 0x6c NAME = unknown

Some values seem off, it may be due to some entities being dead, inactive or used for other purposes. But we can still find the guards as entities 11, 12 and 13.

Random discoveries


Through this post we built upon the discoveries from last time and we scratched the surface of the entity system. While this post was short, I still think that a lot of concepts were uncovered. We now know the amount of entities running, where some of their stats are stored, facts about the gameobjects (shared ids between npcs/items) and even how the drops are implemented in the game. I think the entity system still has a lot to offer, the spawning logic especially as it can be a possible entrypoint to the map system (loading/format/logic/etc…). I will surely tackle this next time.