Using a Debugger to Figure out Game Mechanics

Reaper man
Ok, so the past couple if days I decided to learn how to use a debuggger, as I was playing a game where I wanted to find out how a specific portion of the game worked. Anyway, I succeeded and was able to find out what I wanted. now I'm going to show you a helpful guide on how to do it. We'll be using Breath of Fire IV (PSX) running under pSX emulator as the game and I'll be trying to get a goo King to drop its sword using the spell charm. Here we will find how charm plays a part in item rarity and the exact drop rates for items.

Slight word of caution. I'm going to be going through some really technical stuff here, and basic knowledge of hex and bit operations as well as basic programming is essential, but not exactly necessary, to understand what's going on. If you need any extra clarification, comment and I'll try to explain further.

First off, let's get familiar with the pSX's r3000 debugger, shall we?


here it is, in "all" its glory...

ok, I said "all" because there are windows that could be there, but aren't since they are irrelevant (GPU, call stack, CDROM, etc). The ones we care about are shown above, and they are:

Memory: ok, this is where all the code and data needed for the game to run AT THAT PARTICULAR POINT is stored. when a game is "loading," all of the data needed to play the level gets transferred to here.

Breakpoints: ok in debugging, breakpoints are specific "rules" where when the rules are met, the CPU stops what it's doing (otherwise known as breaking, hence the term "breakpoint"). For example, I could have it to where whenever a certain value in memory is read by the code in the game (which will be explained in a bit), it'll stop it whenever it does. Also, I can add extra rules, called "conditions" to further refine the breakpoint. So lets say I want it to break when a certain place in memory is read but ONLY when another memory location equals x value, I can do that too. I can also alter the count which is how many times should the rules be "triggered" before actually breaking. Breakpoints are essential for finding algorithms in the game.

Disassembly: Ah here it is, the actual code of the game. This is where are the instructions are shown(think of them as "commands" being executed one by one.) Some of these do math and bit calculations. Others load and store data to and from memory. Others jump to other "commands" in memory, or jump only under certain conditions. Some of these commands will be explained in detail later.

Registers: These are 32bit values stored in the CPU itself. Think of these as the CPU's... workbench. This is where things are taken from memory, manipulated, compared to, etc, and spat back out. Basically all the variables that the code is currently using for calculations and such are stored here. As a lot of stuff happens here obviously, so it's important to look at (you'll see why in a bit)

ok, now that we've gotten that taken cared of, now we shall discuss how I found the algorithm in the first place. Okay, so first I had to figure out where the battle data was, so I got into battle and dump the memory. I first had to find out how large the PSX RAM was (2MB) and dump it to a file (which can be done by going to the debugger and selecting File --> save binary.) At first it was saving the wrong size. It took me a while to realize that I was inputting the size of the dump in hex, and it was interpreting it in decimal (I'll later find out that in order to input anything in hex, you need to put a "0x" in front of it(ie: 0x1c345.) I should have known that, oops.) Anyway with proper dumps in order, I had to find where the enemy data was(which actually, I was wrong... I actually wanted to find the battle data, haha, which is what I actually found first ;p.) I already knew that game strings(think chunks of text) were plain ASCII, so it wasn't hard to do a search for the enemy name. Once I found the enemy (and boy was I confused when searching again popped up a different entry, which was what I was looking for in the first place, until I realized that I was looking for the wrong thing all along and that the first entry I had was what I actually wanted that I managed to find by mistake). So after my "duh, I should have been looking for battle data instead" moment I started capturing memory from before and after charm was cast. Needless to say, when comparing the two (that is, after cropping the data to where only battle data is left) I saw a decent number of changes, almost all of which were not related to the casting of charm, so I had an idea. In another, similar battle, I did nothing but defend, and dumped the memory and the end of the turn. I then compared that dump to the "before charm" dump and the same byes that showed changes now, than before were the ones I obviously didn't want. Only one byte was left after that, which kinda surprised me. See all this time I thought chard directly alters the item drop chance in memory and then sets a status, but in fact setting the status is the only thing the spell does, and looking back on it, i can see why. See if it just went out and changed the rate directly, then it would become easier to steal as well, which is not the purpose of charm. So, with the charm flag set and everything, I had to figure out how the game used the flag in the item drop algorithm. This was where I figured i had to learn breakpoints. So, I open up the breakpoints window and I set the memory offset of the charm flag and have it break whenever there was a read or write, just to test(actually I tried a few different read/write combinations, but that's the basic gist). I go and cast charm... nothing. I go and win the battle, still nothing. Puzzled, I go and ask pSXAuthor (who is obviously the developer of pSX emulator)for help. He suggest that I need to force a break first (which can be done under debug --> break) before adding a breakpoint. Ok, well I do that and, still nothing. At this point I'm getting rather confused. It was at this point where I thought "you know, a lot of these values in the data are actually 2 bytes large instead of one byte" so looking at my break point, I alter it to where it's looking at the charm byte and the byte before it, on a hunch. I go and start to steal (I was fighting a goo king at the time, and bingo. I got it to break. Now when the execution is broke, you have to manually rerun it. well, needless to say, the game tends to load those two values rather often. So here I am thinking "hmm, how am I going to isolate when it actually checks charm for the item drop?" And then, it dawned on me. It should calculate the item drop when the enemy dies! Perfect! So my next task was finding where in the battle data is the enemy's remaining HP stored. This was rather trivial, as I just watched the bytes whenever I made an attack and found one of which was going down with each hit, and went to 0 when I defeated it. so, how am I supposed to break on a memory address if and only if the remaining enemy's HP equals 0? Well, with conditions, of course! Sadly, at this point I didn't know how to implement them. I had to go and ask pSXAuthor how. With some help from him, I added my condition read_long(0x1C7138)==0x0, which is the second enemy's remaining HP (I was using the second enemy as the goo king was always in the second position). So I ran it, and right when the enemy bit the dust, BOOM, it breaks. Now it breaks here twice, once for the first item and once for the second item. And finally, here's the charm specific code. (yeah it took a lot to get here, hahahaha)


Code:

001b72b4: 9482015a lhu r2,0x015a(r4)
001b72b8: 00000000 nop
001b72bc: 30420100 andi r2,r2,0x0100
001b72c0: 10400007 beq r2,r0,0x001b72e0
001b72c4: 00000000 nop
001b72c8: 26100001 addiu r16,r16,0x0001
001b72cc: 320200ff andi r2,r16,0x00ff
001b72d0: 2c420008 sltiu r2,r2,0x0008
001b72d4: 14400002 bne r2,r0,0x001b72e0
001b72d8: 00000000 nop
001b72dc: 24100007 addiu r16,r0,0x0007
001b72e0: 0c05bce1 jal 0x0016f384

Ok, so that first column is the memory offset (basically where you'll find the instruction in memory.) The second column is the instuction in hex, otherwise known as machine code. This is what the PSX actually executes. The third, is the hex code in a more readable format, known as assembler. The first and third columns are what we care about most, so lets look at each one step by step to see how the game handles charm.


001b72b4: 9482015a lhu r2,0x015a(r4)


Ok, so this is the command that triggered the breakpoint in the first place. it's an lhu command, which means "load halfword unsigned." Basically it loads a halfword value (don't worry about it saying it's unsigned. It has no bearing on what we are doing here) from the memory over into a register (remember that workbench we were talking about?). In this example it's taking the memory value at the base offset stored at r4 (register 4) + another offset (0x015a), and storing it at r2 (register 2). That offset happens to of course be the charm offset which value is 0x0001. Now if you look at register 2, you'll see it stored as 0x00000100. This is because the game uses little endian for storing values in memory. Basically what this means is it stores values with the least significant byte first, while we of course read values the opposite way, so think of it as the byte in memory being reversed from what we are used to. Okay, so we have the charm status in register 2, now what?


 001b72b8: 00000000 nop


 No operation. Basically self explanatory. It does nothing. I'll be omitting any further nops from this point forward.


 001b72bc: 30420100 andi r2,r2,0x0100


 Ok, this one is AND immediate. If you don't know what "and" is in the computing/logic sense, it's a logic operator. Ok, the best way to describe this is say you have light switch A and light switch B. Light bulb C will only turn on if both light switch A and be are flipped on, otherwise it's off. Ok, so these values we are working with have 16 of these switches. the AND operation works like this: AND C, A, B. This means that we are going to AND r2 which is 0x0100 with basically the same value and store it back into r2. This is a binary operation so here's what it looks like:

A 0000 0001 0000 0000 AND
B 0000 0001 0000 0000 ==
C 0000 0001 0000 0000

So here we are left with the exact same result we came with, BUT what if charm was never cast? Well it would look something like this:

A 0000 0000 0000 0000 AND
B 0000 0001 0000 0000 ==
C 0000 0000 0000 0000

and well, again, R2 would remain the same, so why even bother? Well, remember that we loaded TWO bytes into the register. What if the other byte was used for something else? Let's say that it was and it was turned on as well as charm giving us a value of 0x0101. now it would look something like this:

A 0000 0001 0000 0001 AND
B 0000 0001 0000 0000 ==
C 0000 0001 0000 0000

Therefore by using AND, we can effectively filter out the bits we don't want. In computing this is known as a bit mask. So basically what this command does is say "HEY, I only care about the charm status here, and throw away everything else!" Moving on...


 001b72c0: 10400007 beq r2,r0,0x001b72e0


This really important instruction here is branch on equal. What this does is it compares two registers (r2 and r0 in this case,) and if true jumps over to the instruction at the specified address. Now we all know that r2 is where charm is being stored, and r0 is 0 (in fact it's always 0, no exceptions). This means that if charm was never cast, it's going to jump to 0x001b72e0, which as you can see is the end of this code, meaning that everything in between won't get executed. If r2 = anything other than 0, then it'll continue on its merry way. See why the AND command before it was so important now? if that other byte was set, and charm wasn't then the branch wouldn't be set at all, even though charm wasn't cast on the enemy.

Basically, this instruction says "was charm cast? If so, carry on, if not, skip past all the charm based instructions and go to the next portion of the algorithm..."


 001b72c8: 26100001 addiu r16,r16,0x0001


ADD immediate unsigned. Here we are seeing 0x0001 being added to r16 and then stored in r16. What is r16 you may ask? Simple, it's the rarity value of course that was added to r16 a few instructions before we started (think you can find out which one, and what the instructions before and after do? Free cookie for the first to figure it out!) So anyway yes, THIS is what charm does. It increments the steal rate by one. So here, as you can see we are past that instruction and r16 is currently 2. It was 1 before.

Basic explanation: item drop + 1

ok, so charm has done its thing, but why are there 4 extra instructions to deal with? (the 5th is the instruction that gets executed regardless....) What's going on?

 Once looked at, it's very simple really...


 001b72cc: 320200ff andi r2,r16,0x00ff


 Ah, our friend ADD Immediate again. This time, it only cares about that last byte in r16 (where the item drop is) and copying it to r2. Pretty much that's what AND is being used for, and a copy paste instruction. cute huh? "But wait, that's where the charm status is kept" Not any more it isn't. See charm did its job and it isn't needed anymore. now it's the item drop's turn to get some calculations done on it...


 001b72d0: 2c420008 sltiu r2,r2,0x0008


Here's a new one. Set On Less Than Immediate Unsigned. So here's what this does. It takes R2 and 0x0008 and if R2 < 0x0008 then R1 == 0x0001, otherwise, R2 == 0x0000

Here's the funny part. You could have easily (I believe) had the instruction sltiu r2,r16,0x0008 and completely would have done away with the previous ADD instruction. Think about it. So why take the extra step? It's probably because of an unoptimized compiler, but yeah, you could easily optimize this algorithm to use one less instruction... anyway, onto the next instruction...


 001b72d4: 14400002 bne r2,r0,0x001b72e0


ok, this one is Branch on NOT Equal, so this does the exact opposite as BEQ. Once more it's comparing to 0, and we know that r2 is essentially "r16 < 8." So basically it means:

if r16 < 8 == true (1) then it's not equal to 0 and therefore skip past the next instruction to the one after it (0x001b72e0) otherwise, continue onward...


 001b72dc: 24100007 addiu r16,r0,0x0007


ok so this is the sole instruction that gets executed if r16 is greater than or equal to 8. as you can see it adds 0x0007 to r0 (nothing) and sets it to r16. So yeah, this 4 instruction is a basic if-> then statement which looks something like this:if item.droprate > 7 then item.droprate = 7

see, if you recall, the item drop rate is a "level based" system where 0-7 signifies the overall rarity of the item, with 0 being no chance at all while 7 being 100%. but what rates are 1-6? After finding out what charm does and still being inside the algorithm, I decided to find out...


 001b72e0: 0c05bce1 jal 0x0016f384


This is where all the branches jump to. This is basically a linked jump (meaning when it's done jumping it'll eventually return back here) to another portion of the code somewhere. This also marks the end of the charm part of the algorithm.

ok, so now we know with definite certainty that charm increases the drop rate level by 1, but we still don't know exactly what those drop rates are exactly. Well, we do know that the rate is still being stored at r16, and the game still has to figure out whether to drop the item or not, so we KNOW that r16 is going to be read again eventually, so what we need to do is execute the code line by line until we encounter it. This is achieved by the step into command on the debugger (debug -->step into.) For those wondering, step over does the same thing, but it won't jump to various addresses, it just plows through, and we don't want that. So after stepping into a bunch of commands, jumping from place to place in memory, we FINALLY reach the algorithm we want.



 Ok, now this time around, I did a bit of highlighting so that hopefully it'll be easier to follow. Also, I'll be going over the same similar instructions, so for those I won't be explaining what they do... ok, first up is the instructions hilighted in green. Here we go!


 001b7308: 320200ff andi r2,r16,0x00ff


 Ah yes, you remember this one, don't you? It's the "lets copy one byte from one register to another" command. Here we see register 16 (which as you recall is the item rarity "level") being copied over to register 2. Ok so now r2 is the item rarity level, now what?


 001b730c: 00021040 sll r2,r2,0x01 


Oh hey look! A new command! Fun! This happy little instruction is called "Shift Word Left Logical," and basically what this does is shift all the bits to the left by a certain number. So the format for this goes x = y with its bits shifted to the left by z. Knowing this we know that r2 is going to equal r2 with its bits shifted to the left by one. so let's take the byte value 2 "which is what we are working with) and bitshift it.

0000 0010 ok this is the value of 2 in binary. Bit shift, GO!
0000 0100 it's now the value of 4...

Did you notice something? It doubled! For the most part (there are exceptions, but for what we're dealing with, we need not worry about it), each time you bit shift to the left by one, the value is doubled.

Ok, so now our drop "level" has doubled in value, but why? At first this doesn't seem to make too much sense, that is until you look at the instruction after it. I'll be honest, until I looked at the next instruction it had me scratching my head. Anyway, it's no longer a "level" anymore...


 001b7310: 00441021 addu r2,r2,r4


ok, so here we see r4 add to r2, where it'll be stored, pretty much. So what's r4? r4 is seen with a value of 801C641C. What is this you may ask? It's a memory address (when you remove the "80" part). So here we have 0x1C641C. Where does that point to? Take a look at the area highlighted in yellow. That my friends is the lookup table for the item rarity levels. Now remember that r2 was doubled. well, ok it is now the offset of the table. So why did it need to be doubled? Well remember that there are 8 possible rates that the enemy's item can have. As you can see, the table is 16 bytes long, meaning that each value is 2 bytes each, which is why it needed to be doubled, so that it can line up with its corresponding value. Ok, so we add 0x4 to 0x801C641C to get 0x801C6420. This is the new offset stored in r2.


 001b7314: 94420000 lhu r2,0x0000(r2)


Ah, this command is fairly simple. Take the 2 byte value stored at the offset value stored at r2 + 0x0000 (so basically just r2), and set it to r2.

The value at 0x801C6420 is 0x0004 (it looks like 0x0400 in memory due to it being little endian) so that value is now stored in r2. Finally we have the real drop rate loaded.

Before I continue further, I want to point your attention to the two bytes in memory highlighted in red. Remember how I was saying how important the item rarity level was kept below 8? This is why. See, if there wasn't anything put into place to prevent it from going to 8, when it came time to read from the table, it would have read in the red area shown, which would have been a bad thing(TM). Now sure, if you study the algorithm, chances are that nothing bad would have come from this, but what if that bad value was say 0000? Charm would have then had an OPPOSITE effect on the item drop rate making something that would drop always into something that would never drop at all! Now that we have that clarified, let's continue on...

So what's next? well, it's the two instructions (in cyan) that are what really determine if it's going to drop or not, since they are both very similar I'm just going to group both together and attempt to explain what I believe is going on.


001b7318: 00a31823 subu r3,r5,r3
001b731c: 00621823 subu r3,r3,r2


Ok these are both subtraction commands which follows the format x = y-z. Pretty simple huh? So here we see in the first instruction that r3 is being subtracted from r5 and the result being stored back in r3. The real question though, is what are r5 and r3? Well, from what I can gather (I never watched these registers, so to be honest I'm not 100% certain on this), r5 is a snapshot of the random number generator in the game, and r3 contains the upper byte we want to get rid of, since for this, all we care about is the lower byte. So if we subtract the upper byte from the total, all we get is the lower byte. So now that we have the lower byte isolated, we can actually do the "calculate if item will actually be dropped" instruction. Here we see the item drop value (r2 or 0x04) being subtracted from the random 1 byte number (r3 or 0xea) where it'll be stored back in r3. Once this is executed, you are left with r3 being 0xe6. Now depending on the values of the random number and the item drop rate, you are going to be left with either a positive or negative number. In this case, we have positive number. Whether it's positive or negative is important for the next, final instruction... (highlighted in magenta...)


 001b7320: 0461001a bgez r3,0x001b738c


Ok, so this instruction is "branch on greater than or equal to 0." What this basically means is "hey, if r3 is positive or 0, then branch over to 0x001b738c. Otherwise, continue onward." Since our result was positive, that's exactly what it's going to do. Now as you recall, usually when you see a branch it means that if true, it's going to skip over some code. Guess what code it's skipping? Well, it's skipping over the "place the item into the battle spoils" code. In other words, because the r3 result was positive, I'm not getting my item... boo. :< In order to get the item, when r3 was being subtracted by the item rate, it would have needed to have been a value of 0x00-0x03 for the result to be negative and for me to get my item. That's only 4 possible values out of a possible 256. So each time you try to get an item with an item chance level of "2," you'll only have a 1/64th chance (around 1.56%) of getting it. For those wondering/haven't figured out what item I was trying to get, I was trying to get a GooKingSword from a charmed Goo King. Needless to say, I was VERY far away from getting it. Even if I somehow managed to get my item drop level to 6 (impossible without hacking), I STILL wouldn't have gotten it.

So that does it.... item drops explained using assembly. If you have any questions or comments, please leave a reply. (it took a lot of work and time to type all this up, so please at least comment or something so that I know my work is appreciated ;p)