This document details the process involved in programming the Snake game into a spanish Pokemon Crystal game, in actual hardware, through arbitrary code execution exploits found in the game. While arbitrary code execution (ACE) in Pokemon has been exploited to no end in recent years (see the 8F item in Pokemon Red/Blue or the Coin Case glitch in Pokemon Gold/Silver), the switch from an emulator to actual hardware in order to implement a relatively complex program proved challenging.
Before moving on, you are encouraged to watch this proof of concept video if you haven't already. The last five minutes of the video are just a less detailed explanation of what you're going to find in this page, so feel free to skip that part.
The whole process of implementing Snake into Pokemon Crystal can be separated into seven main steps, some more complex and time-consuming than others. Only a single step of the seven involves actually writing the payload of the Snake game; the previous five are just intended to optimize and ease up writing the lengthy program, always limited by what the hardware and the Pokemon Crystal glitches allow to do.
The way I apporached the different parts of this project is by no means the only way I could've done it. In fact, at some points I was mostly improvising and coming up with slight improvements and workarounds to unexpected obstacles on the fly. Maybe there are significantly easier paths to accomplish certains things, that I couldn't come up with.
Also, it should be stressed that this was set up in order to work in the spanish version of Pokemon Crystal, and it's not directly compatible with other localizations. While the principle of the different steps is the same, some intermediate measures would need to be adjusted in order to accomodate to the differences found in each localization (for example, the distribution and availability of text characters when they are used to spell out assembly code).
STEP 1 - PROGRAMMING A MEMORY EDITOR
The only known (at least by me) arbitrary code execution exploit in Pokemon Crystal that doesn't require communication with a Geneation 1 game involves the use bad clones. For those that aren't familiar with them, they are a subset of the cloning exploit in Generation 2, that involves turning off the power as the game data is being saved. By turning of the power within a ~10-20 milisecond interval, it's possible to obtain something known as a bad clone, that is, a clone of an original Pokemon with an empty nickname. These empty nicknames are unterminated strings, and may lead to different buffer overflows that, if manipulated correctly, can be exploited to make the game execute arbitrary code from RAM. The following paragraphs will detail how this glitch can be utilized in order to execute the names of the first PC boxes as assembly code.
The basis of this glitch is that, when the game tries to read an unterminated string, it will keep interpreting unrelated data in memory beyond the string buffer as text charaters until a byte that matches the terminator character (0x50) is randomly found. Then, the game will attempt to print this string into the screen, corrupting memory past the screen tilemap if said string is long enough.
If the game happens to encounter the sequence of 0x15 0x00 this way, it will execute an unused mobile function (0x15) with a parameter (0x00) not accounted for in its error-checking measures. This will make the game jump to RAM address CD52, which holds some data related to the map tiles. By moving in a specific pattern before triggering the glitch, we can spell out a ret nc instruction that will bring the program counter back to the address after where the 0x15 0x00 sequence was encountered, which is also RAM. From this point, we will have to find a way to jump to DB75, which is the memory address where box name data begins.
Firstly, we will be using a Max Elixer (Elixir Máx) item is order to describe the 0x15 0x00 sequence. By viewing the Max Elixer (index number 0x15) in the bag, and then exiting the bag menu, the 0x15 0x00 sequence gets written to D106 (current item id) and D107. By saving and resetting the game just before doing this, we ensure that no terminator character will be encountered between the string buffer and address D106.
Given that the program counter will eventually return to D108 then, our goal now is to spell out a jump instruction to address DB75 (FB75 would also work, because E000-FDFF is a mirror of C000-DDFF). We can take advantage of the fact that there is a buffer at D10E that temporarily stores data of a Pokemon. A Wobbuffet holding Miracle Seed (Sem. Milagro) and with Safeguard (Velo Sagrado) as the first move will translate to the following three bytes in memory: CA 75 DB. This is effectively read as jp z, DB75, and can therefore be used to make the game jump to the start of the box name data.
We stumble upon another problem though. After viewing the stats page of our Wobbuffet, its species number (0xCA) will not only be written to D10E, but also to D108. This would make the game execute a jump instruction to an unrelated address before successfully reaching D10E. We can get around this by scrolling the cursor to another Pokemon, but without opening its stats page. In my case, I used a Furret, but other Pokemon with index numbers that translate to instructions that do not alter the code flow or reset the z flag would also be compatible. Since just scrolling the cursor to our second Pokemon also updates the item id at D10F, we make sure to give the Miracle Seed to Furret instead. It's also important to make sure that Wobbuffet's last move is not more than 10 characters long, so we need to move Counter (Contador) to the fourth position of its moveset.
Steps to make the game execute code from DB75, recorded in
an emulator. It's necessary to begin by resetting the game
and to move to the PC in the pattern being shown.
Now that we've found a way to make the game execute code from the names of the PC boxes, we can start renaming them to spell out the desired code. We also need to meet certain requirements before returning from our custom code in order to allow the game to return to a regular state properly. Given that not all numbers between 0 and 255 have a text symbol assigned to them, and that not all of them are available when we're naming a box, there are many instructions that will be impossible to spell out. In addition, a 0x50 byte necessarily comes every 10 characters, in order to terminate the name of each box. Therefore, we'll have to adjust to these restrictions when writing our code.
Visual representation of the available assembly instructions in a spanish Pokemon Crystal. Original source: http://pastraiser.com/cpu/gameboy/gameboy_opcodes.html
The objective now will be to make a program that allows us to write any value into any given memory address, in order to be used in subsequent steps. In particular, this program will work by reading the first six characters of the name of the 13th box, and then decoding them in a way that any 8-bit value and any 16-bit memory address can be specified. The index numbers of the first pair of character are added up modulo 256 with the result idenifying the higher byte of the memory address. Similarly, the index numbers of second pair of characters are added up modulo 256, resulting in the lower byte of the memory address. Finally, the result of adding up modulo 256 the index numbers of the third pair of characters outputs the value to be written into the memory address, overwriting its current value.
Consider the following example, where we want to write D8 into address F895.
The sum of the index numbers of characters 6 and 6 outputs 1F8.
The sum of the index numbers of characters W and 9 outputs 195.
The sum of the index numbers of characters ' and 2 outputs 1D8.
Therefore, by renaming box 13 as 66W9'2, then executing the bad clones ACE glitch as seen in the above video, we can change the content of address F895 to D8.
Follow this link for a full hexadecimal to text symbol pair conversion list: http://pastebin.com/ttKLqTjY
Visual representation of the character map in spanish Pokemon Crystal. Index numbers
start from 0x80 (A) and finish with 0xFF (9). Some are unavailable (crossed out ones).
Now that we know what we want to do, it's time to implement it! Since I couldn't find a way to spell out the whole program with just text characters, I had to make a small patch using the items stored in the PC.
This is the routine that I designed for this purpose (starting from address DB75 or FB75):
Where FBE1 to FBE6 are the first six text characters of box 13, and F8F4 corresponds to the RAM address of the second PC item, which was setup to translate to this assembly code:
Finally, the following edited screenshot illustrates how the first five PC boxes need to be renamed so that their text symbols translate to the code described before:
STEP 2 - OBTAINING MORE ARBITRARY CODE EXECUTION SOURCES
Arbitrary code execution with bad clones is not very versatile; it can only be used in front of a PC and requires quite a bit of time to execute, especially considering that we have reset the game prior to doing it. Overall, it may not seem like a lot of time, but when you throw into the mix the fact that we're eventually going to memory hack plenty of RAM addresses for different purposes, it becomes evident that a faster and more accessible ACE exploit would be more than welcome. Moreover, if we could find different sources to execute arbitrary code, we could assign each of them its own purpose and code. This is also going to prove extremely useful sooner than later.
Having a functional memory editor ready to use anytime opens up a lot of possibilities. To being with, we can turn any of our items in the bag into whichever item we want to. Why is this useful, you ask? This allows us to hack TM items into the medicine pocket of the bag, something that wouldn't be possible in regular gameplay. In this pocket, these items have a USE option that is not accounted for in the game; normally there is a function associated to each item supposed to have a USE option, but the TM items don't have it, instead following out of bounds pointers that can make the game jump anywhere. Some of them jump to suitable places in WRAM and can be used to execute arbitrary code.
There are three TMs worth noting. These are TM15, TM17, and TM25, which jump to FA10, FA47, and FA69, respectively (hence, effectively also to DA10, DA47, and DA69). They all point to addresses in the range between FA0E and FA71, an area in RAM that was reserved for map script flags, but that in the end was not used. What is so good about it is that this data is preserved by saving the game, and also that no regular action in the game can modify its content.
Without further ado, we proceed to hack ourselves these three items in the medicine pocket of the bag. For example, we can put a dummy item in the second position, and then just use the memory editor we programmed in Step 1, to turn that item into the corresponding TM. This can be accomplished with the three following memory edits:
This means that we need to execute the memory editor routine using ACE with bad clones a total of three times, one for each item, remembering to switch the newly obtained TM out of the second position in the bag between each iteration. The resulting box 13 names for each iteration are:
Now we have three items that can be used (literally) to execute arbitrary code!
STEP 3 - SETTING UP TM25 AS A MEMORY EDITOR
This step is very simple. Now that we can use items from the bag to execute arbitrary code, we can adopt one of them to execute the memory editor routine and forget about the annoying limitations of the bad clones ACE exploit. I decided to use TM25 for this, given that it's very close to the end of the "safe" memory area that expands up to FA71. This will just require to write a 3-byte jump instruction to DB75 or FB75 at DA69 or FA69. This means that we need to make use of bad clones ACE one last time to code the instruction jp FB75 in three iterations:
Once completed, TM25 can be used as a memory editor, in a similar manner to how we've been utilizing the bad clones exploit so far.
STEP 4 - SETTING UP TM15 TO WALK THROUGH WALLS
While being able to walk through walls may seem irrelevant towards our final goal, it will significantly help speed up the process of writing the lengthy payload of the Snake program. As we've seen, writing a very long program byte by byte with the memory editor setup can be incredibly tedious and error-prone even after upgrading from bad clones ACE to TM25 ACE. The ability to walk through walls will be a requirement for the next step, where we will discuss a much more efficient way of writing the Snake game or any given ambitious program.
Unfortunately, achieving the ability to walk through walls is not a straightforward task. The game determines whether we're able to move in a specific direction using something known as tile collisions. This way, if we are trying to take a step in a direction where there is any kind of obstacle, the game won't let us advance. Collisions are kept track in four memory address, between C2FA and C2FD, one for each direction. A value of 0 determines that the player is able to walk in that direction, while any other value identifies some kind of collision. These registers are updated by the game constantly in order to reflect the four collisions correctly at all times, so using our current memory editor tool to change them to 0 won't be of any help, given that they will change again before we're able to do anything worthwile.
Therefore, we have to find a way to zero those collision registers with enough regularity so that they effectively always contain 0. So it's when we ask ourselves, is there any instance where the game is constantly executing code from writable RAM? Luckily, the answer is yes; in particular, the OAM routine at FF80 is executed as much as once per frame. This procedure is used by the game to transfer sprite data from regular RAM to the OAM memory, and to wait until the transfer is complete. Since during this period the CPU can only access HRAM (FF80-FFFE), there is no other option than to copy this short OAM procedure somewhere in this area, calling it once per frame in order to update the sprite data in the screen.
So the objective is clear now. We have to append a little program to this OAM routine that zeroes the four tile collision memory addresses between C2FA and C2FD. But there are at least two more issues to work out though. The first one is that we cannot rewrite any memory address past the 10-byte space reserved for the OAM procedure between FF80 and FF8A, and the second one is that data in HRAM is not saved; if we turn off the game at any given moment, anything that we've modified in the OAM function will be reverted back to normal.
Let's first try to get around the first problem. The way to circumvent the first issue would be to use the last three bytes of the original OAM function to write a jump instruction to somewhere else in RAM, and finish up our modified routine there. It should be noted that not all WRAM space can be accessed safely when this OAM routine is being executed by the game; the area between D000 and DFFF corresponds to the switchable RAM bank, and it cannot be guaranteed that the same bank is always loaded there. Therefore, we'll have to stick to using the fixed RAM bank area between C000 and CFFF. In particular, I chose the unused memory addresses between CFF3 and CFFA.
Keep in mind that apart from the new duty of zeroing the collision registers, the OAM routine should also fulfill its original task, or else sprites will become invisible, making the following steps of the process of programming Snake into the game far more difficult and error-prone. With these considerations, after trying my best to optimize the required code, this is what I came up with:
add hl, bc
add hl, bc
ld de, cff3
call CopyBytes ; 3010
ld de, ff84
ld c, 8
jp CopyBytes ; 3010
.bytes ; fa20
db 21, FA, C2, 22, 22, 22, 22, C9
db 3D, 20, FD, C3, F3, CF
The code above has been optimized by making use the existing Pokemon Crystal function CopyBytes, and by taking advantage of the initial state of the registers. Particularly:
These 30 bytes will need to be written to DA10 or FA10, using the memory editor that we set up before. This requires a total of 30 TM25 uses, with the corresponding box 13 names:
Given the amount of iterations needed, it could be argued that coding a more dedicated memory editor optimized to rewrite successive memory addresses could've been preferable. In the end I didn't think about it too much and took this route, though. Whatever the case, when we're done writing all 30 bytes (provided we didn't make any mistakes!), we can gain the ability to walk through walls by just using TM15, even after turning off and on the game. This makes us ready to move on to the next step!
STEP 5 - SETTING UP TM17 AS A DEDICATED SNAKE WRITER
Writing a 30-byte program is one thing, but writing a 251-byte program -what the Snake game eventually will occupy- is a very different story. Using our current memory editor to write the final program would be way too time-consuming and error-prone. Our goal in this step will be to implement a more efficient memory editor to write the Snake game or any given lengthy program we can come up with.
Given that the final program will be written in successive memory addresses, it would be ideal if we could find a way to avoid having to specify the memory address for every byte, instead using an unrelated variable to keep track of the memory address coming next, therefore working as an offset. Apart from that, it would also be great if we could input the byte to write without having to rename a box to a meaningless string (even if short) everytime.
With these considerations, I chose to do the following. I designed a small program that reads the X and Y coordinates of the player within the current map, and uses them to spell out the desired byte. The Y coordinate will determine the first four bits, while the X coordinate will determine the lower nybble, always assuming that the player is within the coordinates (0,0) and (15,15). In addition, this program will also read and update another memory address, which will store the 8-bit offset that determines where the next byte is going to be written to.
We will be using TM17 for this purpose, so we will be writing this program to DA47/FA47. This is achieved by using TM25 again to write this function byte by byte. The memory address chosen to store the offset is DDF2, which corresponds to the least significant byte of the sixth party Pokemon current HP. This choice was made because the HP of a Pokemon is a value that can be easily kept track of and monitored (by having a party of 6 Pokemon), which should contribute to the prevention of making mistakes in the future. In addition, our Snake program will start in the very next address (DDF3). We will discuss why the memory area starting from DDF3 was chosen eventually, but first, let's focus on implementing the new optimized memory editor. Here's the assembly code:
Where DCB7 is the player's Y coordinate and DCB8 is the player's X coordinate. The first instruction may seem useless right now, but will have a purpose eventually.
The resulting bytes of the above code are:
And finally, the required box 13 names for each TM25 execution:
We shouldn't forget to zero the sixth Pokemon's HP, which can also be done with TM25:
Once finished, we will be able to write data starting from address DDF3 by simply using TM17. We should also see the sixth Pokemon's HP incrementing after each TM17 use.
STEP 6 - WRITING THE SNAKE GAME OR OUR CUSTOM PROGRAM
Now that we can achieve the ability to walk through walls and can quickly write bytes based on the map coordinates, we're almost ready to start writing the payload of our kick-ass game! Still, it's very important to choose carefully the map where we are going to write it. It should be noted that our walk through walls capability isn't perfect; it has the following two flaws:
With this in mind, I analyzed the maps that are have at least a size of 16x16, and chose the Ecruteak City map for the following reasons:
We left an unanswered question in the previous step. Why was DDF3 chosen to write the final program, and what data does it contain? DDF3 through DDFE are the stats of the sixth party Pokemon. Since the final Snake program will be 251 bytes long, it will extend up to address DEEE. This includes the OT (Original Trainer) names of all party Pokemon, the nicknames of all party Pokemon, the Pokedex data corresponding to the seen and caught Pokemon, as well as part of the Unown Pokedex data. Therefore, all this data will become corrupted as we write our program in these memory addresses.
This block of memory was chosen due to being by far the largest usable RAM area that can be preserved by saving the game, and that is not subject to modifications during the procedure invloved in writing the final program. For example, if I had used the full party Pokemon data to store the program (DCDF through DDFE), the happiness values of each Pokemon could change after taking a certain amount of steps, which in turn would've corrupted up to 6 bytes of our program in the process.
As a result, it's essential that, during the execution of Step 6, we do not modify our party Pokemon data in any way, and that we do not perform any action that could affect the Pokedex data. If we stick to moving across the map and opening the bag to use TM17, we'll be completely safe. In addition, it's also safe, as far as the integrity of the final program is concerned, to save and reset the game, as well as to check our party Pokemon or the Pokedex. This can be significantly useful to analyze the progress periodically, in order to compare it with how the affected data looks like in an emulator with the Snake game properly set up. In my case, it proved useful in order to pinpoint an error that I had made in one of the TM17 writes, which I could then fix by making use of the memory editor functionality offered by TM25.
It should be noted that the party data or Pokedex data cannot be used to perfectly describe the payload of our program. For example, the Pokedex won't display caught Pokemon that aren't registered as seen, and, due to the corruption involved in the Pokedex data, this will be the case for many Pokedex entries. In addition, there is always the chance that the unterminated nickname of any party Pokemon crashes the game when its stats page is viewed (the nicknames in the party menu appear as a single ? symbol), so it's more than recommended to save the game before doing so. Furthermore, OT names in the stats page will simply show as a single ? symbol, so it's not possible to contrast this data with that of an emulator.
The way I approached the implementation of the Snake game was to first separate the whole 251-byte load into chunks of 10 bytes. I would write the first chunk, check that the sixth party Pokemon HP reflects the correct value after each chunk (e.g. 10, 20, 30...), and, if so, save the game, and continue with the next chunk. Obviously, the last chunk contained 11 bytes.
Example of how to write the sequence of bytes 01 14 00 3E in Ecruteak
City with TM17, using TM15 first to gain the ability to walk through walls.
Source code of the Snake game: http://pastebin.com/Uxr8G4t7
Resulting raw bytes, arranged in blocks of 50 bytes and sub-blocks of 10 bytes: http://pastebin.com/srxqYZER
STEP 7 - EXECUTING THE SNAKE GAME OR OUR CUSTOM PROGRAM
Once we are done writing the whole program, we are ready to execute it! In order to achieve this, an arbitrary code execution source to execute code from DDFB (the Snake game's entry point) was needed. Since we don't have any more suitable TMs to execute arbitrary code, reusing one of the three that we have is necessary. Luckily, we were aware of this little problem, and prepared TM17 in Step 5 to adapt to this new functionality quickly. In particular, we wrote its original function with a starting instruction of ld hl, DDFB, which, at the time, seemed pointless. However, we can now turn it into a jp DDFB instruction by just changing a single byte! This is resolved by replacing the 0x21 byte at DA47/FA47 with a 0xC3 byte. Again, we can make use of TM25 for this task:
Personally, I decided to change the box 13 name to the above string, and then save the game before using TM25. This way, TM17 could retain its main functionality in case something went wrong with the Snake game, and a game reset was needed. It turned out that I had made I mistake, but, luckily, I could identify it within the memory area of the Pokedex caught data by contrasting it with the game properly running in an emulator. I fixed it by rewriting the 20 bytes of this program corresponding to the Pokedex caught data again, for which I first used TM25 to change the sixth Pokemon HP back to the corresponding value. In the end, I managed to fix it and get the Snake game running in my Game Boy!
The only way to exit the Snake game, or any given program that we code using this procedure is by turning off the power. However, the next time we will only need to use TM25 followed by TM17 to make the program run again, assuming we saved the game with box 13 renamed to 77oZPkMn.