Reverse Engineering a Gameboy Advance Game: Let’s Paint our Website! — Part 7
This post is part of a series entitled Reverse Engineering a Gameboy Advance Game. Read the introduction here. Read the previous post here.
Follow me on Twitter to more computer fun 🐦
We dove deep into reverse engineering and only touched a little bit on JS in the past couple of chapters… but this post will be completely different: let’s go down the slope of web development, so applying everything we discovered to our level editor.
Hereafter I will point out the most relevant decisions in the programming of klo-gba.js, justifying why it had to be so, what I gained, and what I learned with it. I don’t want any “I don’t know, I just know that’s how it was” here.
Unlike the other posts, in which I told the story chronologically, I won’t do the same here. In each section I will describe a design decision, from the largest to the smallest.
A disclaimer: klo-gba.js is a personal project, that is, developed in my free time and as a pure hobby! So some of the decisions and justifications are influenced by hobbyism!
Web App?
Since the introduction I talked about developing a web app… But you’ve probably asked why I’m talking about the web? In general, reverse engineering tools are desktop apps. Even No$GBA is a desktop app. The level editors for the Pokémon GBA games are also desktop apps. The most popular Switch and 3DS emulators are desktop apps. Even this simple program to verify the integrity of Switch files is a desktop app. Why are we doing something different?
Well, the main reason I’m doing a web app is very simple: I’m in love with the web. Just as Gabriel Guimarães, one of the engineering managers at unicorn startup Brex, said, “the Internet is a code delivery tool”: the user only needs to access a URL and can immediately use a service. It is an open environment where everyone can coexist and apply their technologies.
It would be a complete waste to make a desktop application when we can provide everything through a simple URL. This way we don’t compel the user to download software just to play a bit with our map editor. It even allows more users to iterate on alpha versions of the editor.
The latest advances make it increasingly possible to develop true web applications — it would be very difficult if we made our application 10 years ago, for example. WebGL and libraries like React facilitate a lot, and make all of this possible.
JS?
Okay. Let’s make a web app… but… writing in JS? There are so many better things in 2019… Languages like TypeScript, ClojureScript, ReasonML…
Well, in that regard I must admit: JS was a terrible choice and I regret it.
I chose to develop in JS only because I was already used to it, and the libraries I intended to use worked better with JS, such as the functional library Ramda. Another example library is the UI library which I had already decided to use, Former-Kit, which is not typed, which decreases the gains from using languages like TS.
Another thing that made me opt for JS was that I was hoping, by using a more popular language, it would attract more people to eventually collaborate on the project. Well, I received a few PRs from other people, but they were very few, which didn’t make up for the investment of using JS.
Even dealing with a simple personal project, I frequently make mistakes which languages with static typing, TS and ReasonML, could avoid (what is it this object can receive? What are the possible states of this enum?).
One curiosity is that, by dealing with a completely personal project, I have a lot more freedom to try out different ideas and technologies. One of those was experimenting with the babel pipe-operator plugin. This made the JS code more digestible.
This plugin works very well with Ramda, as all of the Ramda functions are curried. We’ll see a small example of that a bit later.
100% Static Application
Since starting development I had the vision of wanting to develop a 100% static application. I’ve already suffered experiences with my personal blog, the first version of which required me to maintain a server, and it only caused maintenance problems. When I switched to only using GitHub Pages and outsourced parts which required a server (such as comments), I never had to worry about it. It just works.
Therefore, why a server? All of the operations we’ll need (load the ROM, draw the map, edit it, and save the customized ROM) can be done directly by the client. In other words: we don’t need a server. So why have one? It would just be one more abstraction to worry about maintaining.
For example, we’d have to worry more about security when communicating between the client and server… Ultimately, not having a server is beneficial for this application!
Since I’d already used GitHub to store my code, and already had good experiences with GitHub Pages, I decided to also use it to host the site. Of course, I could use anything else, such as Now, which I’ve also had good experiences with.
Making GitHub Pages deployment was very trivial, since there’s already an NPM package which does everything for me, gh-pages. This is the PR (pull request) which implements it (note: when studying my PRs, look at it commit by commit! I always try to create atomic commits, and I ask everyone to do the same).
React
I’ve developed with React professionally for some time, and I like it a lot. The form of thinking of the frontend as a set of components, with each one having a set of possible states, and writing declarative code in the UI, always made a lot of sense to me.
That’s why I didn’t have much difficulty in choosing React. A small spoiler: later we’ll see that it’s not always good to use React in certain parts of the frontend.
As the component library, I chose Former-Kit. That’s the component library from a company I worked at before, and it’s entirely open source. Using it in the project gives me a lot of agility (since I already have experience in it and my friends who developed it can help me) and flexibility (since I know how to mess around with the library to customize it and open PRs, which happened a few times in the course of the project).
Besides that, this library works very well with UIs based on cards, and it makes sense to me to design the interface of klo-gba.js as being composed of various cards. One card for showing the tilemap, another card for showing an object’s details…
Finally, there’s also a more personal reason: collaborating on Former-Kit, developing it and promoting it, make me happy and more motivated as a programmer, since I have a special fondness for my friends who developed it.
Monorepo
An interesting point of the project is the monorepo architecture. In other words, a single repository which stores more than one project. That is a good way to have a clearer division of responsibility among parts of the application, since the division is explicit in the code.
But how come two projects? Aren’t we making just one web app? Keep calm… it will be clearer soon.
klo-gba.js was initially composed of only two projects: 🖌 brush and ✂️ scissors. The first is responsible for all of the UI, that is, with what the user interacts with directly in the browser, with what the user sees. The second would be the “backend”, or rather, it’s what’s responsible for manipulating the ROM data, storing information about the levels…
For example, brush is what maps each tile type to a color, while scissors is what maps the tile ID to its type. scissors doesn’t even know what React is, while brush doesn’t know how to manipulate the ROM buffer.
scissors stores JSON-like files with the data for each level (like the tilemap address, the size of the level, etc.) scissors processes this data to respond to what brush requests.
Doing this with monorepo, instead of two separate repositories, helps to have a healthy level of encapsulation. For example, it facilitates when I go to open a PR or analyze the commit history of the repository — which gives an agility boost. If a PR affects both projects, it’s not necessary to open two PRs in separate repositories, but just one PR which edits both.
As the application keeps growing, we can have more projects. For example, if we’re going to develop a new and complex UI component, instead of developing it inside of brush, we can develop it as a separate project and import it as a dependency in brush. Or we can decouple an existing component from brush by creating a new project in the monorepo.
That in fact was something that happened after several months of development. When I decided to add a GBA emulator within the page, I created a new project in the monorepo, 🕹 react-gbajs, which helped to reduce the complexity of brush.
Another case is that I want to decouple the Tilemap component from brush, so it will be an isolated React component, in order to make it available to the community. However, an intermediate step to arrive at that result would be to create it as a new project inside of klo-gba.js, and only after the Tilemap component is stable would it be moved to a new repository. This intermediate step would be good to gain agility during development.
Ah yes, and to avoid losing the commit history when we move to a new repository we can use the command git subtree.
One disadvantage of the monorepo is that it increases the complexity of the build process, since we now need to compile two projects and link them “somehow”. There are different ways to do this. The one I initially applied in klo-gba.js is one of the simplest possible: I just imported scissors into brush using its relative path:
"dependencies": {
...
"scissors": "file:../scissors"
},At the other extreme of complexity, another monorepo approach for many projects is to use Lerna, which is a tool to generate the dependencies among the projects of a monorepo, including generating the dependencies within each project.
One of the things it does is, for example, if many projects require the exact same dependency, instead of downloading it multiple times, it downloads it once and creates a symbolic link to it.
Clearly, as klo-gba.js is very simple, I didn’t see a need to use Lerna.
When there were only two projects, using NPM linking the dependency with file: was satisfactory, however, when I went to add the third project inside the monorepo, looking to facilitate and speed up the adding of dependencies, I migrated to using Yarn’s Workspaces, and the change was made in this PR.
The dashboard of the company I worked for also uses the approach of a monorepo through Yarn’s Workspace. Since it’s open source you can study its code here.
Tilemap
The first component to be developed was the Tilemap, even before klo-gba.js had a name. It is, without a doubt, the most complex component of the application. Curiously, it represents about 35% of brush’s codebase. This component has two big responsibilities: plot the tilemap with the objects and allow the user to customize it.
Remember those proof-of-concepts we developed to draw the level to an image file? Well, from there I started to think about how to develop Tilemap. The clearest vision I had, besides the code which drew a BMP, was to simply draw in the browser using canvas, and so I started to develop it. For that, I chose to use the konva lib and the react-konva wrapper.
That way, I made each tile a point on the canvas, and each point was a React component. That facilitated a lot for implementing interactions with the mouse.
And it worked! However… it performed very poorly, since it had to render many components. Just to give you an idea, the second level contains 18000 tiles, that is, around 18000 React components are created!
The first render of the level took ~3 seconds, and switching to another level took ~13 seconds!! This significant delay when switching the level probably happens because React tries to utilize components already on the screen, however, since it’s dealing with an entire level switch, all of its attempts to reuse the tiles would fail, and so it took much more time to update the virtual DOM and, afterwards, draw the screen.
As I said, besides rendering the level it is also necessary to update the color of a tile when it is modified, and obviously it wouldn’t be enjoyable to have to wait several seconds for each click on the map. So, I wrote some extremely bizarre code using refs to avoid re-rendering the Tilemap when changing the color of one point. Even so, it continued to take several seconds to render the tilemap.
So I kept looking for a way to optimize it, and this algorithm caught my attention. If you look at the image below you’ll get the idea. With this algorithm we can have fewer components on the screen and, with fewer components on the screen, we succeed in rendering more quickly!
The implementation of this algorithm wasn’t easy, not only because of the challenge to “expand the component up to the best possible size”, but also because it increased the complexity of painting a tile. Here is the PR that implements a simplified version of this algorithm. After this optimization, I managed to reduce the first render to 1.8 seconds and the following renders to 3.6 seconds. Even though it’s still a bit slow, it’s good progress, right? But now the code is so much more complex…
Aiming to get feedback and preparing to lecture about this project at a conference, I gave a talk about klo-gba.js for the first time at a ReactSP#35 meetup. I devoted one section of the talk to explaining the complexity of the Tilemap component, and then everyone strongly recommended that I abandon Canvas and replace it with WebGL.
Okay. Listing the feedback, I decided to refactor everything to use WebGL, this time using the @inlet/react-pixi library, which uses pixi.js under the hood. Just by replacing Canvas with WebGL, and still keeping the same architecture, I already got a performance boost. The first render was now taking 1.6 seconds, and the following renders were 2.8 seconds! This is the PR that made this change.
Then as a next step, still following the feedback, I decided to reduce the absurd number of components on screen. Instead of each tile being a React component, I decided to render just one component and, within it, have WebGL paint all the tiles. With this approach, I ended up with much more readable and optimized code! The first render now takes a measly 0.625 seconds and the following renders take 0.536 seconds. This is the PR with the implementation.
Yeah, it’s obvious that if I’d started using WebGL from the beginning, I would’ve had many fewer problems with this component, but it was the first time that I really developed anything using these technologies. It was all a process of learning and discovery.
Furthermore I hope to have time in future to uncouple the Tilemap component into a new React component, because I think that it’ll be useful to other community projects.
Provider Pattern
Something very popular when developing with React is to use “Redux-something” to manage the global state of the application. Okay, I was developing a new project from scratch, however, I had some doubts whether I would need to apply Redux or not.
Discussing with people with more frontend experience, we arrived at the conclusion that we didn’t need Redux. klo-gba.js’s frontend is too simple to need the complexity which Redux adds.
We have very few IO-bound operations. We don’t even have a single server to communicate with. Besides that we have few components which mess with the global state of the application.
Therefore, we can use a simpler approach, since our problem is equally simple. So we opted to use the Provider Pattern. With this architecture we define a context which components use to obtain the global state and, in case they want to modify the global state, they request that the provider make the change.
This is a good way to avoid the problem of explicitly needing to go through several properties in various levels of the component hierarchy, which is called prop drilling.
Since the start of the application I already knew that the component for selecting a level (SelectVision) would affect the global state of the application, since all of the other components need to update according to the level selected by the user.
Applying the Provider Pattern, the SelectVision needs to communicate with the provider responsible for storing the information about the selected level (VisionProvider). All of the logic for updating the level information remains in the provider, not in the component!
Thus, when the VisionProvider is updated, all of the components which listen to that provider are also re-rendered. This is something to be careful with, since if we have a bad plan, undesirable re-renders can occur!
Something important when you’re developing using Provider Pattern is to try to break the providers up and isolate the branches of components affected by any given provider, in order to reduce the number of unnecessary re-renders, just as Dan Abramov himself explained. Therefore klo-gba.js currently only has around 3 providers:
ROMProvider, which stores the ROM buffer (a ROM was uploaded? The function for updating the ROM…);VisionProvider, which stores information about the currently selected level (tilemap and object buffers, the functions for updating the level…);DisplayMapOptionsProvider, which stores the options for showing the map (show grid? hide the objects?)
An annoying problem I had is that, in react-konva as well as @inlet/react-pixi, it’s not possible to pass contexts created externally. This comment better explains that bug.
The solution I had was, in the Tilemap, just extract all of the data needed in the contexts and pass them as props to each of its children.
WebAssembly
So, let’s end this chapter with the golden key! This is my favorite part and one of the biggest hypes in the project.
You remember that in the fourth chapter, Where is the Tilemap in the ROM?, we used an old project written in C to decompress the tilemap extracted from the ROM? Well, that works perfectly when doing the decompression process manually… but how can we automate the decompression, and besides that, run it in the browser? After all, a web page can’t run C code!
Rewriting all that C code to JS would take a lot of time, and I was already confident that the C code worked perfectly for the tilemap files in the game.
So what about compiling the C code into WebAssembly, and then loading it in the browser?
I’d never used WebAssembly before, I only knew the gist of it. So I had to learn a bit more before getting my hands dirty. In these studies, I found the popular project Emscripten. It’s already very mature and old; it existed since the time when it was popular to compile for asm.js, which is basically a subset of JS, focused on being much more optimized to process.
Although it was not our objective, another gain from using WebAssembly is better performance, as WebAssembly manages to perform very well in CPU-bound operations, which is exactly the case when we decompress the tilemap.
To compile using Emscripten, just run emcc -s WASM=1 mySource.c. When compiling, besides generating the .wasm file, it also generates a wrapper written in JS, which makes integrating the WebAssembly with the rest of the codebase much easier.
The wrapper already loads the .wasm and exposes its functions for use.
Another wonder of Emscripten is that it manages to emulate the file system. Why do we need that? Well… the original code in C uses the file system to read and write the data buffer to be compressed and decompressed. In order to use it we need to pass a file path. Since I really didn’t want to mess with the C code, since it could be error-prone, I sought to keep this same behavior.
Studying more about Emscripten, I saw that it’s possible to pass a compiler flag to it to emulate the file system, and it even adds functions to the wrapper for manipulating this emulated file system! With that, it was possible to preserve the maximum possible amount of the original code.
The flag to use is -s EXTRA_EXPORTED_RUNTIME_METHODS=["FS"].
However, it’s not all sunshine and rainbows…
I managed to successfully compile the C decompression code, and it runs in the example project which Emscripten generates with no problems, but when trying to use it in klo-gba.js, it didn’t work! I was stuck for some time without knowing what was happening, until I understood that the problem is the Webpack. What!? The Webpack?? Yes. The very same.
One of the Webpack configurations is to rename files to avoid cache problems in the browser. So, the file which before was called lzss.wasm would end up being called something like 0b549596b.wasm. When renaming these assets, Webpack also updates the imports within the code, however, that doesn’t work for the wrapper generated by Emscripten, so it fails to find the .wasm. That same error had already affected other people, and the solution they found was basically to use file-loader and patch the locateFile function of the wrapper. And so we have:
const huffmanWasm = require('./wasm/huffman.wasm')
const huffmanModule = require('./wasm/huffman.js')({
locateFile (path) {
if (path.endsWith('.wasm')) {
return `node_modules/scissors/dist/${huffmanWasm}`
}return path
},
})...
The reason for adding node_modules/scissors/dist/ before the filename is because scissors is a project which is a dependency of brush, and that is where the .wasm files will be from brush’s viewpoint.
The PR which adds these crazy features with WebAssembly is right here.
At that moment, it appeared to me that everything was working perfectly, however, I realized that I had a problem when doing deployment.
The reason is, when doing the production build and deploy, there is no path called node_modules/scissors/dist/. Therefore, we need to use the copy-webpack-plugin loader to copy the .wasm files into scissors and move them to brush. This commit is what does that fix. (See the PR for that commit to have better context.)
Honestly, I didn’t like that fix very much, since it created an encapsulation in the build between brush and scissors. One of the ideas I’ve had for resolving that bug better is to disable the file renaming that Webpack does, but I haven’t tested that approach (I accept collaborations on the project!).
After creating a small module encapsulating the logic of interacting with the WebAssembly, the function for extracting a level is very clean:
const extractTilemap = (romBuffer, [addressStart, addressEnd]) =>
romBuffer.slice(addressStart, addressEnd)
|> huffmanDecode
|> lzssDecodeNotice that the function for extracting a level is a mere three lines! Ah, and notice how elegant the pipe operator is =^-^=
From that moment, the foundation was already working, in the end, we succeeded in decompressing a level from the game in the browser. But how about we improve it a bit more?
The process for compiling using Emscripten implies that the person has it on their computer and executes some commands… then how about automating that using a shellscript and Docker? So I found an Emscripten image made by the community (no official one exists), and I wrote the following shellscript:
function docker_run_emscripten {
local filename="$1"echo "Compiling $filename..."docker run \
--rm -it \
-v $(pwd)/scissors/src/wasm:/src \
trzeci/emscripten \
emcc -s WASM=1 -s ALLOW_MEMORY_GROWTH=1 -s MODULARIZE=1 -s EXTRA_EXPORTED_RUNTIME_METHODS=[\"FS\"] -s EXPORT_NAME=\"$filename\" -o ./$filename.js $filename.c
}docker_run_emscripten huffman
docker_run_emscripten lzss
With that, it’s now a lot easier to install the environment for running klo-gba.js!
In Conclusion…
Okay, we saw various decisions made during the development of klo-gba.js, and from that moment we had our web app for customizing levels from the game Klonoa working! How cool!
Is there anything else missing? Well, let’s say yes…
At the moment we’ve managed to customize a level and save it in the ROM, however, with the following limitation: the level following the customized level doesn’t work any more! That is, if we modify level N, we can play our custom level N, but the game crashes when loading level N+1.
What’s the reason for that bug, and can we fix it? In the next chapter (the next-to-last!) we’ll discuss that in detail, and talk a little about the frontend as well as returning to some more reverse engineering.
