NULL

[Tutorial] Reverse Engineering Step by Step in Klonoa Game

Discussion in 'GBA - Game Development, ROM Hacks and Translations' started by akaishi, Feb 23, 2019.

  1. akaishi
    OP

    akaishi Member

    Newcomer
    1
    Dec 17, 2018
    Brazil
    [​IMG]

    Hello everyone!

    Some weeks ago I created a topic asking for help about how to create a level editor for a GBA game, because it's my first rom hacking and I didn't find much tutorials about how to start this project neither "how I should to think in order to do it".
    But since GBA is an old and very popular videogame, many fans written very good tutorials about this architecture as well as tools, such emulators and debuggers. But we still lacking a complete tutorial about ROM hacking.

    In order to resolve this lacking it and to teach how to do a ROM hacking, I'll explain how I'm doing the level editor for Klonoa: Empire of Dreams game!
    I'm writing this manual in Portuguese (my native language) and translating it to English. Feel free to fix my English, please.

    If do you want, you can follow this project more closely seeing the source code here: https://github.com/macabeus/klo-gba.js

    How is this game?

    [​IMG]

    It's a 2D platform/puzzle game.
    This game has many levels and mechanics that the difficulty increase as the player finish each level. This is an addictive game, but in a moment we finish all levels... them... if we could create the own levels?
    We already have a level editor for others games, for example, Pokemon has Advance Map. But I feel that lacking a level editor for this awesome Klonoa game. Then, we should to create one!

    Our tools

    [​IMG]

    We'll use two main software: no$gba, mainly to dynamic analysis, and IDA Pro, to static analysis.
    no$gba is very good for dynamic analysis, because we already have everything in a single tool. And since it is a reverse tool exclusively for GBA, it has very specific features, like viewer for tile map. But, the debugger for memory and code is very poor if compared to a more generic software like IDA Pro, that has very good tools for static analysis, like graph viewer and memory extractor.
    Then, we will use both softwares, because they are complementary.
    Okay, let's start!

    Part 1: Let's go to stretch the bridge
    Well... Our objective is to create a level editor, right? It is a very complex challenge, with many things to do... but let's start by the most obvious way: let's create our tiles on the map!

    An important thing when you are doing a reverse engineering is "find and follow the patterns". This is, instead of just "to create tiles" from nothing, let's start by a simpler way: we'll "repeat the tiles" in order to "stretch something on the level". Then a good fit is to find a good structure to stretch on the level, that is, a place which the tiles is regular (sequence of the same tiles), with vacant place around and should be easy to check that we made a change.
    Then, the first level has a very good structure: a floating bridge.

    One of no$gba tools, Vram Viewer (you can access it by F5), is very useful in our work. Using it you can see the different level background. At Gameboy Advance we have BG 0, BG 1, BG 2 and BG 3. You can see at BG 0 tab we have the blue sky, while at BG 1 we have the images of the second background (a big cactus?), and at BG 3 we have nothing.
    The only important to us is BG 2, which we can see the "walkable" tiles.

    [​IMG]

    When hover the mouse on a tile, we get many informations about it. Despite we have many infos, it has just two items really important for us:
    • Tile No: this is the tile ID. In this example, all tiles with the ID 9B is exactly this bridge part, which is the left corner. 9A is the ID of the continuous part of the bridge.
    • Map address: where the tile is stored in the memory. In this example, it is at 0600F1AD.
    Hey, I said a memory address! And this address is expected, because everything between 0600 and 0601 is a special section called VRAM (Video RAM). In this section is stored the background, sprites, as well the tile map, as we saw.
    Gameboy Advance has many memory sections, each having a different purpose and functionality. If you want to learn more about it, you can read here, but always when I say a new memory section I'll describe it briefly.

    Then we know that the address 0600F1AD is where this tile is stored. Nice. Let's go to this memory address!

    [​IMG]

    Amazing! You can see the bridge here in the bytes? Please, note that 00 is a vacant tile, while the others bytes are the tiles displayed at the screen. The sequence 9B 9A 9A ... is the bridge! Then, if we replace the 00s on the left of 9B following the pattern we can stretch the bridge? Let's try!

    [​IMG]

    We stretched the bridge at the memory, then let's run a single frame on the emulator (you can type / to do it)! Then we can see that we really stretched the bridge!! Yeah!

    [​IMG]

    But...... when we run one more frame, we can see that the bridge returns to the normal shape... well... why it happened? How to fix it?
     
    Last edited by akaishi, Mar 12, 2019
    zfreeman and Coto like this.
  2. ThoD

    ThoD GBATemp Addict (apparently), but more like "bored"

    Member
    10
    Sep 8, 2017
    Greece
    Interesting post, but in that second picture in your OP there's a watermark of a ROM site, which is against the rules, so make sure to remove it. Just be careful about that stuff.
     
    akaishi likes this.
  3. akaishi
    OP

    akaishi Member

    Newcomer
    1
    Dec 17, 2018
    Brazil
    Thank you. I replaced the image for another without a watermark.
     
  4. akaishi
    OP

    akaishi Member

    Newcomer
    1
    Dec 17, 2018
    Brazil
    I didn't post here at last days because I was very busy developing the code for the level editor, but finally I can made this tool be usable, then now the source code is open!
    You can see it here: https://github.com/macabeus/klo-gba.js. Please, give me a start

    [​IMG]

    Then now you can follow more closely the project developing and I can have more focus to write new sections about the reverse engineering.
     
  5. akaishi
    OP

    akaishi Member

    Newcomer
    1
    Dec 17, 2018
    Brazil
    Part 2: Understanding the mischievous DMA
    As well we seen, the bridge stretch that we made changing the WRAM memory just works for a single frame. Let's understand why it happens and how we can keep our tiles alive!

    The first step is understand better the memory region that we are changing, in this case, the VRAM (0600~0601).
    So, I "played" while I also seeing how it behaved, for example, if this region keeps all level tilemap or just the tilemap in the screen, or if it keeps only tilemap or something more.
    In this moment, we need use our creativity to infer, with the poor informations that we have, what this memory region do, what these bytes do.

    [​IMG]

    After the analyse, I reached at a conclusion that this region just keep the tilemap that the player is currently seeing. So, at each frame, VRAM pulls the tilemap at "some region that have it entire" the region that the player should see. Then, we need to write our tiles at the source that it pulls!
    But then the following questions arise: why it works with this way? How it writes at VRAM at each frame? And where is the source that has the entire tilemap?

    So I went to study a little more about how GBA works to can answer these questions. I stayed a while lost until find this fantastic manual about GBA!
    In this manual, when it explains how the tilemap works, it says that a good approach to update the VRAM where keeps the tilemap is using the DMA (Direct Memory Access). It's a resource that many computers has and it is very useful to copy quickly a continuous memory region from a place to another place.

    So an unknown region keeps the entire tilemap while, using DMA, copy a part of bytes from it to VRAM.
    And it make sense, because VRAM is useful just to show the tilemap in this moment, and the DMA is important to game don't have lag.

    When I say that "DMA is mischievous" is because, many time when you are doing a reverse engineering, it changes the values by a way that is hard to predict and also be hard to find the source of this value. There are moments that we believe that an instruction wrote a value, but the DMA that really wrote it, or then we think that DMA wrote, but an instruction that really wrote it.

    Fortunately, no$gba has a feature very useful to debug the DMA, called TTY Debug Window, because it prints the DMA logs.
    So, when we run a single frame, it'll give the following logs:

    Code:
    DMA3: 03000900 0600E000 80000400
    DMA3: 03001100 0600E800 80000400
    DMA3: 03004DB0 0600F000 80000200
    DMA3: 03004800 07000000 84000048
    
    DMA made various reads and writes... Nice...
    And since we know that the bytes of the bridge begin at 0600F1AD, the byte nearest with the limits is:

    Code:
    DMA3: 03004DB0 0600F000 80000200
    
    Then we need to see what has from 03004DB0 onwards, because it is the source of VRAM. Very nice!!
    This byte is inside the memory region called Fast WRAM (0300:256kb) and this region is very useful to keep datas with frequent reads - exactly the case of update the tilemap at each frame. This memory region also is called IWRAM, but in this manual I'll use "Fast WRAM" name, because it is the name used at no$gba.

    [​IMG]

    When we look at this region, the first thing that we can notice is that it's very like a tilemap, because there are many zeros and continuous bytes with the same value. And note it: when we look at bottom, we can see our bridge starting at 03004F5D address!
    Works if stretch in these address? Let's try...

    [​IMG]

    And look! It works!! The bridge was stretch! Now the DMA copy the values that we wrote to VRAM at each frame, so our tiles keeps alive.
    But we have an unexpected error... our tiles is "phantom"! We can see it, but these tiles doesn't have physic, then the Klonoa falls!! Crazy...

    [​IMG]

    Why we can see the tiles that we wrote but can't touch it, looking like a phantom? And how we can apply physic on it?
     
  6. akaishi
    OP

    akaishi Member

    Newcomer
    1
    Dec 17, 2018
    Brazil
    Part 3: Understanding the physics in the game
    In that moment I was really can't understand anything more neither what I should to do, because I didn't expect that Klonoa will falls across the bridge, because the tiles is there! We can see them, but can't standing at there! It's a crazy behaviour!!

    So I made a fast test: the tiles that I made keeps when it leaves the vision range?

    [​IMG]

    Making this very simple test, we can notice that the stretch tiles disappears when them leaves the vision range... Interesting... So there are more parts of the memory that keeping this data and they are the information source of Fast WRAM... But at this moment, I was really confused about how to going. (Thinking now when I'm writing it, maybe a better way would be see again the DMA logs, to find where it gets the data... but in this moment I didn't connect this facts, then I following by a harder way)

    Since I was with nothing a better idea, I chose to dig more in reverse engineering making a very complex step: understanding the logic about the physics in the game!
    The idea follow this premise: when Klonoa is falling, his position Y is updated until he arrives to floor. Then, there is a code in somewhere at assembly about this condition, to stop the Y update and, for some unknown reason, this condition isn't running with the tiles that we created, so Klonoa falls.
    If we can understand better how the physics works, we'll can fix our tiles to run this condition! With it in mind, let's understand how the physics in the game works to apply it in our tiles!

    In order to start, let's keep Klonoa falling and see the moment that the Y is update, okay?
    But before, I need to explain a very important concept in GBA: the OAM (Object Attribute Memory). Besides to show the tiles, we also can show objects at the screen. Some examples about objects is Klonoa himself, the monsters, the diamonds... in short, everything that is "dynamic". To do this dynamism, the console needs a way to manage it, updating the position, the sprite... This feature is a common requirement in many games and GBA is a hardware specialized to games, then itself has an architecture to manage it, called OAM.
    The OAM's memory region is 0700:1kb. If you want to learn more about the OAM, you can read it.

    As like the tilemap viewer, no$gba also has a good OAM debug tool, and we'll use it now!

    [​IMG]
    A curious detail is that Klonoa always is the first object stored at OAM, including at moments that he isn't showed, as like at title screen. Seeing the spec about OAM, we can find that the bytes responsible to define the Y at OAM is the first. Then, we know now that the Klonoa's Y position is always at bytes 07000000 - it'll facilitate our analysis, nice! Let's leave Klonoa falling and debug step by step until find the instruction that change these bytes.
    Debugging step by step, I noticed that the value is updated at a non-sense instruction: swi 5h
    I'll talk more about this instruction at another chapter, because we don't need know it now. Just one thing is important now: it is not related to changing memory values. Thinking a little more, I realized that the byte 07000000 probably is updated by the mischievous DMA!
    The game (probably) is writing at something place at memory region the new values of Klonoa and copying it to overwriting at positions from 0x0700 and onwards.

    Opening the TTY logs, we can confirm this hypothesis by the last line of logs:

    DMA3: 03000900 0600E000 80000400
    DMA3: 03001100 0600E800 80000400
    DMA3: 03004DB0 0600F000 80000200
    DMA3: 03004800 07000000 8400003E


    So we need check the updates at the byte 03004800! Remember: this byte is at the region called Fast WRAM.
    Going to this byte, one of most important tests that I made in order to understand it was changing its value and then run the game to see the implications.

    [​IMG]

    Then we can see an interesting effect: when we update it and run one frame, we really changes Klonoa's position, nice! But this effect keeps for just one frame, because in the next frame he falls from the previous position... In short, this byte really is important to set the Klonoa's position, but it is using as information source an unknown other byte that we need to find in order to understand how the physics works at the game.

    So I started to dig the flow of the byte 03004800, to find which instructions reads and writes there.
    Now I'll start to talk a lot about the values written at another memory region: 0800:32mb. This region represents the data stored at cartridge, that is, the game itself, which is the instructions (in the format ARMv4T) and the assets.

    Debugging step by step, something that caught my eye happens at the function called by byte 08005D00, because it overwrites the byte 03004800 and everything near to trash!
    And only forward, at the instruction at byte 0800696E, is overwrite the byte with the Klonoa's Y position, but with the value already updated!

    [​IMG]

    This was a very mysterious for me, and also it made me be confused because... what a fuck!? How it could updates the value using just a trash? Where it gets the old values to update it? Or it gets the value already updated "at some place" and only copied it here?
    In order to answer these questions, I did digging even more understanding the assembly just before by 0800696E. But no$gba is very limited to do this static analysis, even more so with this level of complexity - we can't write a simple comment using no$gba! Then, I started to use IDA to debug these instructions.
    Besides being able to write comments, another very useful feature at IDA is the graph viewer, which isolate the each part of the code with blocks and connect it by calls.

    [​IMG]

    After many hours debugging, I realised that to write the byte 03004800 it used as source the value at byte 03002926 that, debugging step by step, we can notice that it is wrote by instruction 0800A4C6. At this moment, I thought that the function where instruction 0800A4C6 is in was the answer for all my questions, so I debugged a lot it, but, after much hours debugging this assembly (plus the analysis that I'll talk soon), I realised that it just set the Klonoa's Y position for the camera! It really was a very frustrating...

    While I was analysing the byte 03002926, something that caught my eye by chance was the behaviour for some bytes that are by left of it. I noticed that, aways that I move the character, these values is updated by a very consistent way with the Klonoa's movement, but with a little subtleties.
    After thinking more, I realised a very important thing: the bytes 03002920:03002921 and 03002922:03002923 stored, respectively, the positions X and Y absolute for the map! It is exactly what we need!! I could realised it doing some tests, like as image following:


    [​IMG]

    You can see that I moved the character to an upper place at the level, then the Y absolute value decreased. But because Klonoa keeps at the same height for the camera, the respectively byte keep with the same value.

    In short, we finally found the bytes that set the Klonoa's position Y absolute for the map! And this logic fits very well, because we can go to an upper or downer place at the level, but the values stored at 03004800 (and consequently also by the 07000000) not changes proportionally, or continues the same.

    Okay, we finally found the bytes that really set the Y position that are important for us, 03002922:03002923, then now we need to debug step by step to find the moment that these bytes are updated.
    After I did this, I found an instruction at 0800FF16. This is always called and it increases the Klonoa's Y value, including when he is fixed at floor... well... it is a behaviour very strange for me. But, after that, an instruction 0801200E returns to the previous value, and this instruction is called only if the Klonoa is at the floor.
    In short, the logic is: please, Klonoa, come down, but if this new position is invalid, returns to the previous place.

    Then we need found where is the condition that decides to call or not the instruction at 0801200E! This condition will be the answer to "why our tile at the bridge doesn't have physic?"
    To find it, I used the graph viewer at IDA and I made a manual binary search, shall we say.

    [​IMG]

    The block highlighted at bottom is where fix the Klonoa's Y position, and the block highlighted at the top have the lasted instruction called when Klonoa is falling, in others words, is where have the logic that decides "the position should be fixed or not?".
    Now that we found where it is, let's decipher the assembly!

    [​IMG]

    After I analysed it, I see that the register R0 receives a constant value, 0x3D, and the register R6 loads the value stored at 03007C8C, which is the ID of the tile that Klonoa will try to enter. Then, this code will compare if the value at R6 is bigger than R0, and if it is true, it will move the instruction sequence to fix the Klonoa's position (in short, come back to the previous position, as like I already said).
    Remembering... empty tiles has the ID 00, and some tiles are background, such as the ropes at the bridge; using other words, tiles which ID is smaller than 3D should be "crossingable".

    The logic of the byte 03007C8C are written at the instruction 0800FF80, which it copies the value from the register R0. And I'll say a very important phrase: to get the ID of the tile, it uses the tilemap source stored at Slow WRAM (region 0200:256kb), which it stores the entire tilemap of the level, differentiating of we saw at Fast WRAM, which it only stores the frame currently visible by the player!
    Because Slow WRAM has a storage bigger than Fast WRAM, and the current visible frame is always read to be rendered, and we can to try the move Klonoa to a place isn't showed at the screen, this organization of the memory layout make sense.

    With this informations, we can answer our main question: the physics isn't applied at our tiles because we are written at the tilemap from Fast WRAM, and the physics logic uses the tilemap stored at Slow WRAM!
    The solution is very obvious: we should write our tiles at Slow WRAM, and we easily find the correct address to write reading the value at R0 before the instruction at 0800FF80. In the case of the bridge, it is at 02008432.

    [​IMG]

    Then finally we can create the tiles that really works!! õ/
    Moreover, our tiles keeps even when it leaves the vision range. So we can conclude that we really writing nearer the information source!

    I think that I need to write a brief annex... I was need some days to can decipher the logic until arrives the conclusions that I wrote here. One of the reasons that made me take so long, additionally my inexperience in the subject, was because I lost me confusing the bytes referentes to Klonoa's Y position to the camera instead of Y absolutes to the map - I lost me in many useless assembly codes that I deciphered after many hours, and I wrote here just a subset of it.
    Is important to say that, in a reverse engineer process, you'll lost many hours going to a wrong way and also need to take more some others hours to returns to correct place to finally find the correct way - I was need to go back several steps and then restart some times. It is very common and I already saw others authors saying the same.


    Furthermore, it is very nice that we finally can write tiles that has physics, then we can follow to the next step in the project, that is extract from ROM the tilemap to plot it, in order to edit it! At the next post I'll say how to do it! õ/
     
    Last edited by akaishi, Apr 14, 2019
Loading...