Getting started in Reverse Engineering

In this post, I’m going to outline a few areas of study that will help you get started reverse engineering a game, and outline the method I took with World Warrior. I won’t be going into too much detail that can already be found elsewhere, only pointing you in the right direction so you can do your own googling 🙂

To get stated, especially using the MAME debugger, you’ll at least need to become familiar with the 68000 CPU assembly instructions and how the processor works. While it’s hard to write code in assembly, it’s not actually that hard to learn the instructions and what they do.

Once you’ve learned the basic instructions, such as MOVE, TST, ADD, SUB, and Bcc, you’ll be able to play around in the MAME debugger to get familiar with how the CPU processes the instructions, what effect the different instructions have on the CPU status register, and how the different branch (Bcc) instructions work.

Next, you should learn about breakpoints and watchpoints in the MAME debugger. Breakpoints stop the debugger whenever execution reaches the address where you’ve set the breakpoint. You can use this to help confirm whether a piece of code does what you think it does – the breakpoint will “hit” (and the emulator will pause) whenever that address is reached.

For example, if you suspect a piece of code is responsible for creating a fireball, you can set a breakpoint at that address, and play the game, ideally in 2P mode so you don’t have to worry about a computer opponent acting by themselves. See if the breakpoint:
1) Always gets hit whenever you execute a fireball
2) Never gets in any other cases

If both of these are true, you’ve probably confirmed your suspicion, but keep an open mind: Does it only hit for Ryu’s fireball? Does it hit for Ryu and Ken? Or does it hit for general projectiles being fired for any player? Always be careful in your assumptions. As you progress you’ll make notes of the different things you’ll find. Make sure you’re not misleading your future self reading these notes again months, maybe years later, well after you’ve forgotten the context in which you wrote them.

The MAME Cheat XML files will be a lot of help to you, as they reveal the addresses of variable for things such as energy levels, time remaining, etc. which will be valuable in deciphering the code. This brings us to Watchpoints.

Watchpoints are similar to breakpoints, except they involve variables instead of instructions. Maybe you want to learn about how a player’s energy is adjusted. A good place to start might be to set a watchpoint on the address that holds that energy variable, and you can learn many such addresses from a cheat file.

When you set up a watchpoint, you can tell the debugger whether you want it to stop whenever that variable is written, read, or both. A ‘write’ watchpoint is useful to finding out what code is making changes to that variable, while a ‘read’ watchpoint can help you find what code is using that variable later on.

For example, a write WP on the energy variable will probably reveal the code that calculates damage, while a read WP is likely to be hit by a graphics routine that draws the players energy bar on screen (and also a number of other things, such as AI routines that make decisions based on how much energy their opponent has. Again, be careful in your assumptions).

Lastly, you’ll want to build a Memory Map of the game. This is a table of address ranges and what they are connected to. Looking at the MAME source for the driver of your game will help you with this, and they will be similar for all games on the same platform type.

A CPS1 game will have a memory map like this:

0x000000 to 0x3fffff Game ROM
0x800000 to 0x800040 Player inputs, coin counters, etc.
0x800100 to 0x80017f CPS chipset functions
0x800180 to 0x80018f Commands to the sound CPU
0x900000 to 0x92ffff Graphics RAM
0xff0000 to 0xffffff RAM

Keep a text editor window handy with this memory map until you memorise it. Eventually you’ll instinctively see a write to some address in 0x900000 and know it’s a graphics write you’re looking at.

That’s all for today. In my next post, we’ll take the bull by the horns and generate a machine language dump of the whole ROM set.

Advertisements
Getting started in Reverse Engineering

I’m back!

I’ve had a bit of contact through the blog lately, and have been helping someone who’s starting out on reverse engineering another game but doesn’t have much reveng experience, so I’m going to compile my communications with him into a series on how to get started on a project like this.

Most of it will be specific to m68k CPS1 games since that’s where I’ve got the most experience, but some of it might be useful for other CPUs and platforms.

I’m back!

Behind the name

I saw this blog got a lot of attention in the last few days, so I though I’d at least post to say I’m still around, even if I haven’t done much recently. I even woke up the old twitter account, so you can follow me there if you like:

https://twitter.com/sf2platinum

Here’s the story behind the name: Back in 2011 the 20th anniversary of SF2 was coming up, and I wanted to get a release of my own SF2 implementation out in time, ‘platinum’ being the stone associated with 20th anniversaries.

Unfortunately, life took a few turns that saw me far too busy to come through with it, and it never panned out. Sorry.

Since then I’ve come back to the project from time to time, but never as dedicated as I was in 2011. I’d like to keep making progress whenever I can, but things are still pretty busy with other projects that pay the bills.

Behind the name

The AI Engine

By today’s standards, the Artificial Intelligence in Street Fighter 2 World Warrior isn’t very sophisticated. These days, when most people talk about AI they’re talking about machine learning. There’s not any of that in SF2. Anyone looking for some insight into how to write an AI engine for a game today will be disappointed.

Moves made by computer opponents are not made independently but are instead grouped into small scripts, written in a bytecode similar to machine language. A computer avatar has a repertoire of different scripts for each opponent they could face in the game*, and set of circumstances, such as a nearby fireball.

Instructions in the scripts can command the avatar to execute an attack (punch/kick/special/throw), walk or jump somewhere, and wait – either for a timer, or some condition such as the ability to throw another fireball.

Other instructions can directly manipulate variables in the AI state machine, test for certain conditions, and form primitive IF…END blocks. Here’s one of Ryu’s typical ‘easy’ attack routines: Throw three fireballs at you, and if you’re somehow silly enough to catch all three and get dizzy, run up to you and throw you.

ORG 0x99c88 sf2ua.bin
0x02,                   ; script header, type 2 
0x10, 0x50, 0x04, 0x00, ; throw a hi str fireball
0x00, 0x80,             ; wait until I have no fireball
0x10, 0x50, 0x04, 0x00, ; another hi str fireball
0x00, 0x80,             ; wait again
0x10, 0x50, 0x04, 0x00, ; another hi str fireball
0x92,                   ; are they dizzy?
0x04, 0x00, 0x18,       ;    walk until we're within 24 pixels  
0x00, 0x82,             ;    wait if they're still getting up
0x10, 0x84, 0x00, 0x00, ;    throw(4)
0x94,                   ; end if
0x00, 0x00, 
0x00, 0x00,             ; wait four frames
0x00, 0x00, 
0x00, 0x00, 
0x86,                   ; chain to another randomly chosen script

Apart from the header byte, the first byte of each row is the instruction byte. Instructions are grouped into avatar commands (0x0-0x7f) and control flow / variable access (0x80 – 0xff). Each of them mostly have a fixed number of parameters, for example the Attack instruction (0x10) always take three:

  1. The attack type (special moves are 0x50, 0x52, 0x54…, throws are 0x80, 0x82, 0x84…).
  2. The strength of the attack (in this case it’s a strong / fast fireball)
  3. A repetition count for attacks involving holds and multiple hits. (unused here)

 

The Wait (0x00) instruction usually takes one parameter, decoded as:

  • 0x0 – 0x7f: Wait for N frames
  • 0x80: Wait until I am able to throw a fireball
  • 0x81: Wait until opponent is within M pixels (additional second parameter)
  • 0x82: Wait until my opponent is attackable
  • 0xc0: Wait until opponent’s jump reaches height M (second param)

All of the instructions and many of the parameters are even multiples of two (there is no 0x01 instruction, for instance) so that they can be used directly against 16-bit jump tables. Low/mid/high strength translate to 0, 2 and 4, as are most internals in the game. Any odd numbers would cause a CPU bus error exception, which would result in the SF2 ROM restarting.

The AI engine has three main modes of operation:

  1. Waiting for an attack. Simple scripts are chosen at random which consist mainly of walking backwards/forwards small amounts.
  2. Actively attacking. Scripts such as the one above are selected.
  3. Reacting to an attack. Scripts suitable for countering the attack are selected. Sometimes. Depending on the AI difficulty setting the computer lets plenty of attacks through unguarded, of course.

For the first two modes, there are 8 levels of scripts, which are chosen based on how much time is left in the round. When reacting to an attack the scripts are chosen based on something called a yoke.

Each frame of animation for both avatars and projectiles contains a value for the yoke in the metadata, which the AI peeks at to select a script suitable for responding to that attack. The computer sees the yoke of your move as soon as you have input it, before the first animation frame has even displayed. As such it gets one more frame of advantage on top of your reaction time.

A question addressed in an earlier post in this blog was whether the AI “cheats”, and it certainly does. Charge moves such as blade kicks are simply executed as instructions, so they cannot fail. Guile can do a bladekick from a standing position simply because that’s what’s in the script. It’s probably possible for the AI to command special moves in the air. One instruction is available to disable collisions against the computer player for a certain number of frames. Using it, you could write a script to simply walk through an approaching fireball.

One of the (more hidden) test screens in the game performs a sanity check on the AI bytecode. It’s not immediately obvious what it’s for as it just displays “OK” and nothing else, but the disassembly reveals the developers were perhaps testing and developing the AI code on CPS machines. The error messages in the test code reveal names for some of the instructions as MOSI, KON, KYON, TIGA, TAN, GTAN and END IF, but apart from the obvious latter name I haven’t figured what they might mean.

Viewers at home can find Ryu’s AI bytecode starting at ROM address 0x9966e on sf2ua. Set a breakpoint at 0x2ad2a to stop at the main entry to the AI code. Avatar AI state variables start at 0x200 from the player struct (0x5c6 and 0x8c6 for P1/2 respectively on sf2ua).

[* WW contains no scripts for battling the four bosses since that shouldn’t happen, and in any case the formulae for each of the opponents are all the same anyway! Maybe the developers ran out of ROM space or time, but the WW computer players use the same formula no matter who they’re fighting]

The AI Engine

Not just code, but data too

Originally the project included a lot of data structures dumped directly from the ROMs, such as sprite animation, palettes, hitboxes, AI bytecode and more. The only data not ported were the actual tiles; the game depended on four tile ROMs from the original game to be present.

Since all this data from the code ROMs is a considerable part of the original code, I decided to pull it all out and require the entire ROM set to be present, basically as much as you’d need to run the game in Mame.

This has its own difficulties, for a start we need to do endian-swapping each time we read anything larger than a byte. I wondered how much this would impact performance, but it turns out not very much. Some CPUs even have special instructions just to do this.

It also has some benefits. Getting the data out of the ROMs and into C-style structs and byte arrays was error prone, and the utility I wrote to do this sometimes messed up and produced incomplete / corrupt data. Many arrays are jagged. Sometimes sentinel elements are used. Sometimes I had to guess lengths of arrays and got it wrong. Going to the ROMs for all this ensures nothing is missing.

I wrote a compatibility layer to take care of locating these structures and doing the necessary byte-swapping.

As an example, here’s how an 2D jagged array of words would be stored.

00001ff0 lea 0x2000(%pc), %a6    ;get address of row table
00001ff4 move.w (%pc, %d0), %d0  ;get offset of row pointed by %d0
00001ff8 lea (%d0, %a6), %a6     ;add offset to base address
00001ffc jmp some_routine_that_uses_this_data

00002000 dc.w 0x0008   ;first row starts at 0x2000 + 0x8 = 0x2008
00002002 dc.w 0x0018   ;next row starts at 0x2000 + 0x18 = 0x2018
00002004 dc.w 0x001a   ;and so on
00002006 dc.w 0x0020

00002008 dc.w 0x1234   ;first element of first row
0000200a dc.w 0x5678   ;second element of first row
....
00002016 dc.w 0x8888   ;last element of first row
00002018 dc.w 0x1235   ;first (and only) element of second row
....
0000201a dc.w 0x1236   ;first element of third row

I guess they did it this way to save a little space at the cost of a couple of extra instructions, as opposed to just using 32-bit pointers, although there was plenty of free space in the ROMs.

Switch-style statements are very similar (and very frequently used throughout the code). Case variables are often kept to even numbers to avoid having to do pointer arithmetic. An example from the state-machine:

000077dc  302d 000c   move.w (game_mode_3, %a5), %d0
000077e0  323b 0006   move.w (#6, %pc, %d0.w), %d1
000077e4  4efb 1002   jmp    (#2, %pc, %d1.w)
;the jump-offset table follows
000077e8  000a        dc.w 0x000a ;jump to 0x77f2
000077ea  0016        dc.w 0x0016 ;jump to 0x77fe
;... several more ...
; here is case 0:
000077f2  546d 000c   addq.w #2, (game_mode_3, %a5) ;next time do the next case
000077f6  4eb8 2794   jsr 0x2794   ; reset display state
000077fa  4ef8 2c8a   jmp 0x2c8a   ; initialize both players (tail call)

000077fe  546d 000c   addq.w #2, (game_mode_3, %a5) ;again, next time to the next case
00007802  4eb8 1698   jsr 0x1698   ; set up palettes
00007806  4ef8 1ae2   jmp 0x1ae2   ; set up scrolls (tail call again)

This is more or less equivalent to

switch (g_game_mode_3) {
    case 0:
        g_game_mode_3 += 2;
        reset_display_state();
        init_players();
        break;
    case 2:
        g_game_mode_3 += 2;
        set_up_palettes();
        set_up_scrolls();
        break;
    /* more cases */
}

If the case is odd, the machine will crash with a bus error exception. This is why 2 is added to g_game_mode_3. If the case is greater than the number of elements in the jump-offset table, the behaviour is undefined. I’ve put default clauses in all my switch statements to land in the debugger to let me know something’s up.

Not just code, but data too

Random number generator

The random number generator is pretty simple. A 16-bit seed is stored which for convenience in code is split into two 8-bit values. The routine is at 0xdd4 in the sf2ua ROM. Here’s the equivalent C code:

short sf2rand(void) {
    int x = (g.randSeed1 <> 8;
    g.randSeed2 += x;
    g.randSeed1  = x;
    return g.randSeed2;
}

As far as PRNGs go it’s pretty poor, but good enough for our purpose here. The output of it is often bitmasked to limit its values (e.g. masked with 0xf to get a number from 0-15, masked with 0xe to get an even number from 0-14, and so on), and also used as a bit index with the BTST instruction to get a 1-in-N chance.

For example, to get a 1-in-4 chance:

if( 0x88888888 & (1 << (sf2rand() & 0x1f)))

The RNG is seeded with exactly the same value every time the machine starts (there’s nothing else to seed it with, no RTC, nothing), so it always produces the same string of random numbers.

If you start the machine, wait for the player invite screen to start, insert a coin and play with Ryu, you will face Dhalsim on your first fight. If you insert your coin while the copyright warning is still printing, you’ll face Blanka instead.

One of these days I should analyse it to see when the seed returns to its initial value, i.e. when the sequence starts repeating.

EDIT: Make sure you check out DIVVS·IVLIVS’s comments below, who’s studied that output from the RNG in detail

Random number generator