Pokemon Gen 1 and 2 had save corruption, so why not Gen 3? :)
Game objectives
- Emulator used: BizHawk 2.11.1
- Beat the game as fast as possible
- Use save corruption!
Save Corruption
The Save Medium
Gen 1 and 2 were on the GB/C, which mean save data could (typically) only be stored on battery backed SRAM. Battery backed SRAM effectively acts like normal RAM, so reading and writing is nearly identical compared to doing so against WRAM and such.
Gen 3 is on the GBA, which means games had more save data options readily available to them. Gen 3 games also have very large save files compared to most GBA games, resulting in them needing to use Flash for their save medium, which offers more storage than SRAM. Flash can only be written to using "commands" against the flash chip.
Flash is divided into "sectors" which can only be written to after doing an erase command on them, setting all bytes in the sector to 0xFF. This is needed as the flash write byte command can only clear bits, it cannot set bits. This means that resetting in the middle of a sector being written to will result in the latter parts being 0xFFs.
While save corruption in Gen 1 and 2 could just reset at any point in the process, Gen 3 cannot do that, due to its save format and how Flash works.
Gen 3 reserves the first 3968 bytes of a sector for save data, while leaving the latter 128 bytes for a "footer" (of which, only the last 12 bytes are actually used). This footer contains a "magic number" along with a checksum. While in theory save data in a sector could potentially be manipulated to match a checksum of 0xFFFF, the magic number check will always fail if it's 0xFFFF, meaning a save will always be seen as corrupt if a reset occurs in the middle of writing a sector. This itself effectively means there's no point in using checksum collision (as the checksum would be written right before the magic number is written).
However, this doesn't eliminate the possibility of resetting between sectors being written to.
All Gen 3 games use the same basic structure for save data. There are two "save blocks" filled with game information, then there is the Pokemon storage system as its own block. These blocks have to be divided up in order to fit into multiple sectors. There is no checksum for the entire save, just a checksum for each sector.
At a glance, it would seem save corruption would just be as simple as mashing two saves together, just at sector boundaries. Surely there are no other quirks with saving that would interfere with this.
Save Chunk Rotation
Normally, there are 14 sectors used for a full save. Each sector here can be understood to have a "save chunk." If saving was simple, save chunk 0 goes to save sector 0, save chunk 1 goes to save sector 1, and so on until save chunk 13 goes to save sector 13.
However, Gen 3 decides to not be this simple. It decides to rotate the save chunks. So, while on save number X, save chunk 0 goes to save sector 0, save chunk 1 goes to save sector 1, and so on until save chunk 13 goes to save sector 13. On save number X+1, save chunk 0 goes to save sector 1, save chunk 1 goes to save sector 2, and so on until save chunk 12 goes to save sector 13 and save chunk 13 goes to save sector 0.
Additionally, for determining is a save is corrupt or not, the game verifies that a save contains all save chunks. So if two sectors end up having the same save chunk ID, that means at least save chunk ID will be missing, resulting in the save being flagged as corrupt.
Backup Saves
Gen 3 offers a silver lining however, with its backup save system. The game stores two full saves, using two "save slots." Each save alternates the save slot used. So, on save number X, the save goes into save slot 1. On save number X+1, the save goes into save slot 2. On save number X+2, the save goes into save slot 1.
If the latest save slot is corrupted, but the older save slot is intact, the game will proceed to load that older save slot.
Clearing Save Data
There isn't an obvious way to get the latest save slot corrupted to "go back a save." The game could be saved again and reset during saving, but that just corrupts the "older" save (before it can become the "newer" save), so that is not useful for save corruption.
Gen 3 offers a simple solution, however, in the form of clearing all save data. On the title screen, the player can press Up+B+Select to bring up the clear save data screen. Clearing save data proceeds to erase all sectors, each using the erase sector command. The first sector erased is always sector 0. This is always in save slot 1, but due to the save rotation quirk, the save chunk erased here could be any save chunk, depending on how many times the save has been rotated.
In any case, save slot 1 will be seen as corrupted, forcing the game to load up save slot 2. If save slot 2 is older than save slot 1, this means game is loading an older save, thus making the next save have the same sector rotation as the existing save data in save slot 1. As long as the save is reset after the save chunk that was corrupted is saved completely and the reset occurs between save sectors being saved, then the save will be seen as non-corrupt and will be loaded, thus allowing for save corruption to take place.
The Sector Split
A save slot contains two save blocks and the Pokemon storage system. These have to be divided up into 14 save chunks to fit in the 14 save sectors. The exact division, however, is very basic. It does not attempt to "round" the data being saved. It is perfectly fine with splitting up data within a save block or Pokemon storage into separate sectors. At most, it will immediately move on to the next sector upon going from one save block to the next, along with going from the second save block saved to the Pokemon storage system, which nicely makes save corruption using the Pokemon storage system identical across all Gen 3 games.
The Pokemon storage system takes 9 sectors to store, using save chunks 5-13. Pokemon data is split as follows:
Box 2 Slot 20 | Chunks 5-6 | 44 / 36 bytes
Box 4 Slot 10 | Chunks 6-7 | 12 / 68 bytes
Box 5 Slot 29 | Chunks 7-8 | 60 / 20 bytes
Box 7 Slot 19 | Chunks 8-9 | 28 / 52 bytes
Box 9 Slot 8 | Chunks 9-10 | 76 / 4 bytes
Box 10 Slot 28 | Chunks 10-11 | 44 / 36 bytes
Box 12 Slot 18 | Chunks 11-12 | 12 / 68 bytes
Box 14 Slot 7 | Chunks 12-13 | 60 / 20 bytes
Boxes 2, 7, and 10 have the most obvious potential here, as these boxes have slots where a potential target Pokemon can have their PID and OTID overwritten by a newer Pokemon, while leaving the raw Pokemon data of an older Pokemon intact.
Creating a Pokemon From Nothing
This TAS does a neat trick here, as the "older Pokemon" used in the corruption setup is empty data. No Pokemon is used as the older Pokemon. This is effectively applying a PID and OTID against empty data.
The PID and OTID of a Pokemon is used for Pokemon's "encryption" system. The PID and OTID is xor'd together to create an encryption key, and this encryption key is xor'd against every word of raw Pokemon data in order to encrypt/decrypt the raw data.
When the PID and OTID is 0, the encryption key is 0, which does nothing with a xor operation, resulting in the raw Pokemon data of 0s remaining 0s.
By using save corruption, the PID and OTID can be set to any arbitrary values (as long as RNG allows for such). When such values get applied to the raw Pokemon data of 0s, the game ends up "decrypting" these 0s into non-0s, which can potentially result in useful data, such as changing the species ID.
The checksum would almost always fail however. Luckily, the checksum is weak, it's just a 16 bit checksum that's the sum of all the decrypted half-words of Pokemon data. With a proper encryption key, any species could be obtained while still satisfying the checksum. Even nicer, all species will have 2 encryption keys that work for this purpose (along with technically 2 others, but those keys will result in an egg, which is undesirable for obvious reasons).
Grab ACE
With a glitchmon in tow, there comes the question of how to obtain ACE. The simple answer is using Grab ACE, an ACE exploit available in all Gen 3 games.
Grab ACE was discovered over 2 years ago, and is mainly used in FireRed/LeafGreen No Save Corruption. This ACE exploit is the result of a classic buffer overflow. The game has a buffer for holding Pokemon storage state, and this includes the Pokemon currently displayed in the PC. This buffer holds various strings, most of which are properly sanitized to avoid a buffer overflow, except the species name. Invalid species names can overflow this string buffer, and very nearby this string buffer is a function pointer called when grabbing Pokemon. With some invalid species names, this function pointer can be overwritten to point to Pokemon storage data in EWRAM, which eventually slides down into box names.
There are many glitchmons available which work for Grab ACE, although the exact list ends up varying depending on the game (although oddly enough, Ruby and Sapphire are identical, while FireRed and LeafGreen vary). The exact glitchmon that ends up being used mainly depends on which one is fastest to obtain with RNG manipulation.
Off By One Sidenote
An interesting sidenote here, there is an off by one when the game handles save slots and save chunk rotation. You might think the first save is in save slot 1 and there is no rotation present, but the game increments these counters before the save. As such, the first save is actually in save slot 2, and there is 1 rotation present in this save.
Subframe Resets
This run uses subframe resets. This is needed specifically for resetting after sector 0 is erased when clearing save data. This is more just needed due to emulator having bad Flash timings. On a real cartridge (at least nowadays), erasing a sector takes roughly 7 frames to complete. On mGBA, it takes less than a frame, so much so multiple sectors get erased in a single frame.
The Actual Run
Initial Seed Manip
Emerald comes after FireRed/LeafGreen, which means coming back from a no RTC game to an RTC game.
With this move, RNG surely should be seeded with RTC like in Ruby/Sapphire, right?
However, no such seeding ends up taking place. As such, the RNG seed is left uninitialized (which ends up being 0, as the game clears RAM on startup).
However, like FireRed/LeafGreen, RNG is seeded when choosing the player name. This is done like FireRed/LeafGreen, using Timer1, one of the GBA hardware timers. Timer1 can be set to different frequencies, although in this case the game chooses 16MiHz, i.e. it ticks every CPU cycle.
After choosing the player name, RNG is seeded with 0x0481. This initial seed also forms the TID (thus the TID is also 0x0481). This initial seed is chosen to have minimal delay to manipulate the SID and starter PID.
Setting Options
The run would want to set options before any fights, as the time it takes to set options is saved from turning off battle animations. It also wants to set text speed to Fast as Medium text speed loses a frame with every textbox.
Changing the options before New Game is technically slower than doing it after New Game. However, in this case it is faster due to the delay needed to manipulate the TID/SID.
Boy vs Girl
Picking the boy is slightly faster here, due to the girl rival having much less dialogue for this short of a run, and the rival fight being faster against the girl compared to the boy.
TID/SID
The player has a visible 16-bit TID and a hidden 16-bit SID. Together, these make the 32-bit OTID of Pokemon caught. The TID equals the initial seed when choosing the player name, while the SID is a later RNG call, so all TID/SID combinations can be manipulated. However, only some can be quickly manipulated, so the TID/SID combination has to be chosen carefully.
This run uses a TID of 0x0481 and an SID of 0x7BDB, resulting in an OTID of 0x7BDB0481.
PID
A Pokemon has a 32-bit PID, used for various misc things like gender, nature, and ability number. More importantly for this run, this value is used with the OTID to create the Pokemon's encryption key.
The starter is manipulated to have a PID of 0xE8DAA87E. This OTID and PID results in an encryption key of 0x9301ACFF.
Starter
The starter chosen is Mudkip. This starter completes the rival fight as fast as possible compared to the other starters.
The starter is not nicknamed, as it isn't seen enough times to save time with a 1 character name.
Rival Fight
The one Rival fight is not particularly eventful. A crit and non-crit can take out Treecko.
Treecko has a Lonely nature here, which lowers defense. This is only with the girl Rival, the boy Rival has another nature, which forces 2 crits to take out Treecko instead of 1.
Poke Balls
With Poke Balls, another Pokemon can be caught.
A second Pokemon needs to be obtained in order to use the PC. This Pokemon can be any Pokemon, so this run catches the fastest Pokemon it can.
Saving Outside The Pokemon Center
For the save corruption to work, sector 0 needs to have a save chunk either at or before save chunk 11. This takes 4 saves to do.
Saving outside of the Pokemon Center is slightly faster than saving inside the Pokemon Center.
Box Names
The box names have a simple payload, it just jumps to the GameClear function.
The box names are as follows:
KFDHQTBH
TBHR BFO
AI
Which executes the following payload:
adcgts r12, lr, #0xC5
adcgts r12, r12, #0xCB0
adcgts r12, r12, #0xFF0
adcgts r0, r12, r12, asr #1
movgts pc, #0x324
0x324 is in the BIOS and has a bx r0. r0 holds the address to the GameClear function, so this ends up jumping to that function.
Accepted to Standard
