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).
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.
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.
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.
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.
By completely reading the damage block we can already guess what the last part of
this function is about.
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.
> 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.
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
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
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 |
| Drop |
 |
|
|
|
 |
|
|
|
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.
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:
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):
Or we can spawn chickens, because who doesn’t like chickens:
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
- If you look for the first bytes of the drop table in the SNES rom of the game you will notice that they are present. The SNES
version has exactly the same drop tables as the gba.
- If you go up a few blocks from the random drop block (0x80c69e4) you will find where the game checks if a drop should be scripted
or not. The only supported scripted drops are the green rupee (0xd9), the small key (0xe4) and the boss key (0xe5).
- Entity id 0x05 allows you to teleport from top to bottom. It could be a staircase without climbing animation.
Conclusion
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.
Useful Links