Awake -- Gameboy decompiler and Zelda reversing project

Started by devdri, June 10, 2012, 08:02:28 AM

Previous topic - Next topic

devdri

OK, so I'm finally getting some cool results, so I figured I'd post here.

I've always had this special nostalgia for the original Zelda Link's Awakening and after making an emulator few years ago, I wanted to go further.
So I started this project to automate ROM reverse engineering.

https://dl.dropbox.com/u/11808662/awake/awake01.png

Here is a screenshot of the setup. Code at top of page is with all optimizations, code below is without most.
As you can see, loops are reconstructed and call parameters are annotated next to call instructions.
The rightmost image is the current state of Zelda analysis. Green means known code, blue is obvious data (text and sprites) and dark blue is 0xFF padding.

Features:

  • static decompilation (no emulation/tracing, all code paths treated equally)
  • expression reconstruction - sequences of instructions are replaced with c-style assignments.
    For example: LD A, 0x30; LD [0xFF00], A is replaced with [0xFF00] = 0x30. This also works across jump boundaries.
  • register lifetime analysis - this enables two things: unneeded flag calculations are stripped away and also I get all ins and outs of a procedure, which helps analysis at global scope.
  • bank switching analysis - direct consequence of the above. I treat rombank as just another register and can recover ambiguous calls this way. In Zelda, bank switching occurs very often, so I get nice results from this. For 2000 procedures analysed (that's much, but I got this number with aggressive procedure splitting) only around 15 contain calls that couldn't be followed.
  • control structure recovery - probably the coolest. Finds loops and forks and uses some heuristics to generate nice if/else and do/while. Some gotos remain, but usually the code is nice.
  • switch statement/jumptables - Zelda really abuses this construct - I found more than 200 jumptables. Heuristics decide on jumptable sizes, sometimes giving false positives, but overall it is helpful.
  • procedure references - For each procedure I get a list of callers. This can also output call graph to GraphViz, but at the moment it is too big to be useful.
  • data references - most recent feature, currently works only for fixed addresses. For each global variable I get a list of procedures that access it. Ultimate helper. Refs to 0xFF00? Yeah, here must be the joypad routine.
  • written in Python, GUI is served as HTML. Allows assigning names to procedures, etc.
  • output is not really C at the moment, but gives an idea of what's going on in the code.

TODO:

  • recognize array indexing
  • obtain full code coverage with no more ambiguous calls. I believe I've got around 90% of procedures now.
  • find a way to cope with so many small procedures.
  • a lot of other work...

I would like to release it one day, but it is very custom right now and requires coding Python to do stuff. Maybe when I improve the algorithms I can drop some hardcoded Zelda stuff and it will be useful for other Roms too.

Also, source: https://github.com/devdri/awake

devdri

henke37

Just give us the address of the source control repository. Unfinished code is better than no code.

devdri

Pushed to Github and updated first post. Also, I put together a small readme to help you get started.

mlemaudit

Hello,

Is there someone here who was able to make this python project run ?

Thanks.

Lin

How have I not seen this? It's been an idea I've had flowing my mind for a good while now but I never actually thought it would be practical. The features you have listed so far sound great and and I'm a bit disappointed to see it's over a year old. Keep up the good work anyway.

mlemaudit

Quote from: mlemaudit on September 18, 2013, 08:10:39 AM
Hello,

Is there someone here who was able to make this python project run ?

Thanks.

OK, I'm responding to myself, but anyway, I managed to get something working...
Cool.  ;D

mcmustang51

Quote from: mlemaudit on September 18, 2013, 12:32:02 PM
OK, I'm responding to myself, but anyway, I managed to get something working...
Cool.  ;D

What did you get to work??

mlemaudit

Quote from: mcmustang51 on September 26, 2013, 09:04:01 PM
What did you get to work??

Sorry for the late answer...  ::)
Well I managed to make it compile on my computer.
And I got some answers like the ones shown on the screen shot provided by devdri (https://dl.dropbox.com/u/11808662/awake/awake01.png) when I followed the steps provided in the readme file of the project. Which are :
- put zelda.gb into roms
- run python main.py
- browse to http://localhost:8888/proc/0000:0150

I Hope this will answer your question.  :)

devdri

Sorry for the waiting, this forum needs email alerts. It's very nice seeing that somebody actually checked out this project. I found that I had some uncommitted changes from long ago, mostly heuristic improvements for Ages. I remember also trying to make a proper GUI, but lost the prototype.

I committed everything to Github and resumed work. First I added a nice GUI in Tkinter for exporting the disassembly. The idea is to move away from the browser and make the program more user friendly. I'll soon include selecting the rom and running the server from GUI and later a main window with much more dynamic, realtime information than the browser based version. For example seeing the number of procedures grow live as more code gets discovered.

Anyway, here's a little teaser:

Doomed

Looks neat! I'll have to download Python and poke around sometime. This post comes at an interesting time.

I'm complete garbage at hacking, but I've been trying to get a text speed hack for Link's Awakening DX. I tested the following on the DX ROM (Revision B) but it probably works on the regular ROM as well.

Change 0x58164 from BA to BB, then walk one screen down from the starting location (Marin / Tarin's house). Tarin's "wait!" text will display, automatically scrolling by quickly. Some graphics are garbled. The game then restarts and the colors go weird.

If one could reverse-engineer what causes the text on this screen to scroll quickly, they should be able to make a text speed hack. The original game's text speed is painfully slow.

If you know anything about what governs the text speed, I'd love to hear it. The Game Boy Color games, Oracle of Ages / Seasons, have text speed options on a per-save basis. Presumably those games are based on the Link's Awakening engine.

devdri

Hi,
I remember once finding the text routine (in original non-dx), but I don't have it in my notes. Everything in the game runs on counters, that are incremented each frame. Then at say, 10th frame the counter is reset and the next character is copied to the spritesheet. It's probably not that hard to change once you find the right 'update' routine (I expect that text is just another type of object like enemies, but don't remember for sure). I could find the object id in debugger once I have a bit more free time. With the id just look up the address in a giant jump table and you get the right routine.

As for the Oracles - they have totally different engine, just reuse the graphics. There are some similarities in code 'style' (probably from the Nintendo SDK, although it's totally different from Pokemon 'style'), but it looks like Capcom didn't reuse any of the LA code.

cret

I'm working on esil-strings for gb, that might be interessting for you:
http://runas-racer.com/foo/esil_gb.png
https://github.com/radare/radare2/wiki/ESIL

the main advantage of parsing those esil-strings would be, that they include the mbc-logic,

I'm mostly done with that. I have to set more flags and the you could use it for your work. r2 has python-bindings
go r2, use debug. .... White hand was fainted