(note: I encoded a version of the input file that performs some more inputs during the credits)
Game objectives
- Aims for fastest time
- Corrupts save data
- Executes arbitrary code
- Uses a game restart sequence
- Heavy luck manipulation
- Takes damage to save time
Version Choice
The Japanese version is used because it allows us to write a more effective ACE payload. There are way more Japanese characters than there are alphanumeric ones and they occupy the high values ($60 - $FF), which are very useful for our purposes. It might be possible to do this run on other versions but it would be a lot more delicate and definitely slower.
In addition, the Japanese textboxes have fewer characters and the screen with the Nintendo and Capcom logos is skippable only on the Japanese version, making resets quicker (and there will be quite a few resets).
The Save Glitch
This is the central glitch of this run, which allows us to skip almost all of the game. The idea behind it is pretty simple and also not terribly original: We reset the console during the saving process, thus creating a "hybrid" savefile, one part of which comes from the new file and the other part from the old file. The data that will go in the savefile is stored in addresses $C5B0 - $CAFF in WRAM (the GameBoy's working memory) and when you save, it gets copied one byte at a time to addresses $A010 - $A55F in SRAM (the save memory on the cartridge). This means that we can choose any point between $C5B0 and $CAFF to "splice" the savefile and create a file for which all the values before the splice are the same as in the new file and all the values after are the same as in the old file.
At first, this doesn't seem too promising. For example, if we put the splice in the middle of the inventory, we couldn't just get new items that way. This is because if we want the hybrid file to have a certain item, at least one of the two files (old or new) needs to already have that item. We could duplicate an item and dual-wield it but that doesn't put us any closer to beating the game.
There is however one point in the save data where a splice has a great impact: the Death Respawn Buffer. It determines where Link respawns after dying or savewarping and consists of 13 frames starting at address $C62B. The disassembly describes those bytes as follows:
.STRUCT DeathRespawnStruct
group db ; C62B
room db ; C62C
stateModifier db ; C62D
facingDir db ; C62E
y db ; C62F
x db ; C630
rememberedCompanionId db ; C631
rememberedCompanionGroup db ; C632
rememberedCompanionRoom db ; C633
linkObjectIndex db ; C634
c635 db ; C635
rememberedCompanionY db ; C636
rememberedCompanionX db ; C637
.ENDST
We're only interested in the first two bytes. They determine which screen Link will appear on. Since there are more than 256 screens in the game, they have to be put into different groups. The first byte then tells us what group the screen is from and the second byte tells us the address of the screen within that group. So, if we splice the file exactly between those two bytes, we can combine the group from the new save with the address from the old one, warping us to a completely new place!
The screens in this game are categorized into 8 groups, although the last two are just duplicates of the previous two. We're left with these 6 groups:
(Some screens in the last two groups are cut off because they are larger than 10x8 tiles)
For the address, the high nibble denotes the row and the low nibble the column. So the screen we start the game at would be 0 8A. I will refer back to these images later when we actually do the warps.
Save Data Protections
So far I've pretended that we can just reset the console at any point in the saving process and the game won't take issue with it. In reality of course, developers aren't usually very fond of the save data getting corrupted, which could lead to the player losing all their progress if done accidentally. They therefore put safeguards in place to prevent this from happening. This game uses two such safeguards in the form of checks that are run on all files upon starting the game, as well as at other points:
- The first two addresses of the save data ($C5B0 and $C5B1) are a checksum. It is calculated by treating all the other addresses as two-byte words and simply adding them up. Upon booting the game, this checksum is calculated again and checked against the value that is actually stored in those two bytes.
- The next 8 addresses ($C5B2 - $C5B9) are a verification string. It is checked against the string "Z21216-0".
If either of these checks fails, the entire save data is deleted and then a backup, that was saved to a different location in SRAM before any of the addresses were overwritten, is loaded in its place.
The second check is not a problem for us. It would be a problem if we tried to delete our file, then reset during the deletion process. But the way we're trying to do it, both the old and the new file will have the correct string in the right place, so there is literally nothing that can go wrong here.
The first check it trickier. Since the checksum is calculated before the other addresses are overwritten, this means that our hybrid file will have the same checksum written at the beginning of the file as the new file, but the checksum that is calculated during boot-up will come partially from values of both files.
So it's our job to make sure those two different checksums just so happen to be the exact same. There are two important things to point out here:
- The addresses before the splice are identical between the new and hybrid files. This means that those addresses (which include the in-game clock) cannot be used to adjust the checksum.
- For the rest of the addresses, what really only matters is how they change between the two saves. For example, if we picked up some rupees before the first save, both the new and hybrid save would have those extra rupees. For it to make a difference we would have to pick them up after the first and before the second save.
So in summary, we're looking for addresses that come after $C62B and are also highly volatile. Fortunately for us, the addresses pertaining to the Pirate Ship fit the bill:
wPirateShipRoom: ; $C6EC
; Low room index the pirate ship is in
db
wPirateShipY: ; $C6ED
db
wPirateShipX: ; $C6EE
db
wPirateShipAngle: ; $C6EF
db
You won't actually see the Pirate Ship in this run but nevertheless the game keeps track of its position and for some reason even stores it in the save data. It moves one pixel every two frames and takes 1856 frames to do one full rotation. It only doesn't move during screen transitions, textboxes and menus.
The Pirate Ship is very useful for adjusting the checksum but another part of the save data that can be used for that purpose is the inventory. The items in our inventory are stored in addresses $C68A - $C699. The only thing we can affect here is the parity of the slot the items are in. So if we move the sword from slot 0 to slot 2, that won't change anything because its value is still added to $C5B0. However, if we move it to slot 1, it will instead be added to $C5B1.
There are two more addresses that we have a little bit of control over:
- $C65F and $C660 store a value called Gasha Maturity. This value continually increases as you play the game and when it crosses a certain threshold, a Gasha Nut can be harvested. Most importantly for our purposes, this value increases by 5 every time you do a screen transition.
- C6AA is Link's health. This is pretty straightforward, we can reduce this value by 2 by taking half a heart of damage.
To bring this all together I wrote a lua script that takes as input the checksum for the second part of the save data of the old save, as well as the first possible frame within the Pirate Ship's rotation that you can save the game at for both the first and second save. (I arbitrarily labeled the frame where the ship is in the top-left corner as frame 0.) The script returns all possible times that you have to wait before the first and second save so that the checksum will be correct and the splice will work. It does this based on all possible configurations of the inventory. We can load the script before doing the second save and play around with extra screen transitions or taking damage to see how the values change. This probably all sounds rather confusing at this point but I will point out what parameters to use for the different wrong warps in the run, so you can play around with it yourself. When you see the script in action this should all become a lot more clear.
With all this theory out of the way, we're finally ready to start the run.
The Run
We christen our hero ヌにゲゼテ. This will obviously be our ACE payload and will be explained later when it's relevant.
With perfect text mashing the text speed doesn't matter. It only affects how fast yes/no prompts come up and there won't be any in this run, so we just leave it at 3 and start the game.
The Pirate Ship starts moving as soon as we're in the game, so nothing we do in the intro matters as long as we make it to the first save in time. The only thing I had to pay attention to was keeping the Pirate Ship moving. During screen transitions and textboxes the in-game clock will keep moving but the Pirate Ship won't. Because the ship only moves when the parity of the clock is even, this means that if the ship doesn't move on the last possible frame before the transition/textbox and it also doesn't move on the first possible frame after, we just lost two frames. I checked all the transitions and textboxes in the run to make sure this doesn't happen.
We spend around half the run watching the intro cutscene. Afterwards, we get the sword and, more importantly, the ability to save the game. We could now go beat the final boss but that's not actually the fastest way to beat the game. Instead, we enter Vasu's shop and save the game. Then we enter Maku Road, save, and reset the GameBoy. Vasu's shop is screen 2 EE and the entrance of Maku Road is screen 4 04, so this warps us to screen 4 EE, which is part of the Black Tower.
The parameters for the script are 499, 743, 0xB4, and 0x9C. We see that we would have to wait a total of 862 frames for the warp to work. However, this is because we just barely take too long to get from the first save to the second. By doing 4 extra screen transitions, we can push the window for the second save back just enough so we make it in time. That way we only lose 286 frames plus the time it takes to do the transitions, for a total time loss of 482 frames.
Unfortunately, we spawn in the wrong version of the Black Tower, so we have to leave and reenter so we can get the shovel. You might be wondering why we're getting the shovel given that we could get literally any item in the game instead. The answer is that in order to do ACE later we need to be able to load a lot of objects into the game's memory. The mighty shovel is the only item that can do that by itself.
Right after that, we save, then leave the Black Tower, save again, and reset the console. The entrance to the Black Tower is screen 4 E7 and the exit is screen 1 76, which warps us to screen 1 E7, which is an out of bounds area south of the past overworld map. This area houses a well-known ACE exploit.
The parameters for the script this time around are 157, 441, 0x6E and 0x45. Despite having more inventory options available due to the shovel, we get a bit unlucky here and have to lose 718 frames. The best we can do is take half a heart of damage to prevent a further 4 frames of time loss.
Arbitrary Code Execution
The glitch we use to beat the game occurs when you select a certain out of bounds tile on the map. Since you're not supposed to be able to select it, it has undefined behaviour, which ends up causing a jump to address $FAD5 in Echo RAM (which is just a copy of WRAM). You can read this article for a more detailed explanation (only the first paragraph is relevant here).
When this glitch was first examined by sockfolder, they wrote the code to OAM (the GameBoy's sprite memory). However, this is very cumbersome because it only allows you to write one-byte instructions. This would be especially terrible with the limited tools we have available. The problem is that for most items we can dig up (namely rupees and hearts) we don't have a lot of control over their position. They always spawn in the middle of the tile, no matter where you dig, and they always fly the exact same distance. It might be possible to use fairies and enemies to write code here but even if this did work, it would be very slow because the drop rate for fairies and enemies from the ground is low.
We will instead write our code to the high addresses of Echo RAM. Since Echo RAM is the same as WRAM, this means that our code has to go after address $DB00. The memory between $D000 and $DFFF is used for the objects that are currently loaded on screen. Each object occupies 0x40 bytes. The game distinguishes between 4 types of objects that are all loaded into separate slots from one another. This means that we have to pick one of those types and then spawn a lot of objects of that type until the last one we spawn holds the code that we want to execute. Let's go through the 4 object types in order:
- Items are loaded in slots $DX00 - $DX3F. These are things like bombs and seeds. This is actually the easiest type to use IF you have enough of those items (and it is in fact how real-time runs beat the game). However, we have precisely 0 of those items, which means this type is out of the question for us.
- Interactions are loaded in slots $DX40 - $DX7F. These are things like the dirt that appears when you dig or the icon at the top of the screen that tells you what time period you are in. All of these disappear very quickly, making it impossible to spawn enough of them.
- Enemies are loaded in slots $DX80 - $DXBF. Since the shovel can dig up enemies, we can actually use this type. However, the drop rate for enemies is low so this just turns out to be slower than the last option.
- Parts are loaded in slots $DXC0 - $DXFF. This is a slightly confusingly named type of objects but it includes rupees, hearts and fairies, all of which can be spawned by the shovel and together have a much higher drop rate than enemies.
So we will use part objects to write the code. The problem with rupees and hearts is, as already mentioned, that we don't have a lot of control over their position and the object's position is the only part of the data that we can use to write meaningful code. The fairy however is different: Its movement depends on RNG so we can manipulate its position to be whatever we want it to be (as long as that position is on screen).
The RNG in this game is pretty annoying to manipulate in a TAS setting because it only advances when a random event happens. Luckily, the sword plays one of three random sounds when you swing it, so we can use that to manipulate RNG. In practice, manipulating the fairies movement was probably the most annoying part of the run but I was eventually able to write a full simulation and brute-force all possible sword-slash-sequences that will result in a position that causes a jump to the filename.
In summary, the plan is to spawn 11 part objects and then spawn a fairy as the 12th part in slot $DBC0 - $DBFF. Since we start executing code at $FAD5, in the middle of the 11th part which would cause a crash, we have to then collect the 11th part to free up that memory again. We then manipulate the fairy's position at $DBCA - $DBCD to be a jump to the filename at $C602 - $C606.
Let's talk about the filename now. After we jump to it, the registers look like this:
AF = 1510 (zero flag not set, carry flag set)
BC = 0001
DE = CDDB
HL = FAD5
SP = C214 (points to 61F5)
We can write all the values between $60 and $FF, as well as the two values $20 and $2D. Our goal is to trigger the credits cutscene. A cutscene can be triggered by writing to either $C2EF (Cutscene Index) or $CC04 (Cutscene Trigger). Since we can't write $04, we have to write to $C2EF. The credits cutscene is value $0A but the MSb is ignored, so value $8A will work as well.
The first order of business is putting either $0A or $8A in the A register. Given the values in the registers, it's not possible to do that by using only one byte but there are 18 possibilities to do it with two bytes. Out of these, the combination ヌに (C6 75 = ADD A, $75) was the fastest to type.
The next character has to be ゲ (EA = LD (a16), A) and the fourth character has to be the low byte of the address we want to write to, i.e. ゼ (EF).
For the last character, we have the choice between テ (C2) and ォ (E2). At first glance, テ seems like the obvious choice, being right next to セ. But at a second glance, you realize that the character we need is not セ but ゼ, meaning we have to add the dakuten and from there it's faster to go to ォ. But then a third glance reveals the left arrow in the bottom-left corner of the file name menu, which, unlike pressing the B-button, let's you go backwards in the filename without erasing the rightmost character. This means that we can type all the base characters and then add the dakuten to ケ and セ afterwards, making テ the faster choice after all.
That's all the characters we have, so there was no room to write a return opcode. This means that the game continues to execute code after the filename, which could potentially cause a crash. I could have used the in-game clock to write the return opcode but that wasn't even necessary because one of the later addresses returns us to ROM anyway.
Now that we understand what we have to do, we can return to the run. After the second wrong warp, the first thing we have to do is visit screen 1 E2. This screen corresponds to the magic map tile we have to select in order to trigger the ACE exploit and you can't select a tile on the map if you haven't visited its screen before. Starting from 1 E7 we have to simply walk 5 screens to the left. After that we're stuck in the wall, leaving us unable to perform the ACE setup so we have to save warp back to 1 E7.
RNG rolls once every frame on the title screen so we can delay pressing start for the right amount of frames here until we reach the RNG seed that allows us to dig up the first part object in a row of 12 that ends with a fairy. In this case the delay was 0 frames (lucky me).
We dig up 8 part objects and then a Rope. Ropes can drop fairies, which in this case turned out to be faster than digging it up. It also gives us more control over where the fairy spawns (digging it up would always make it spawn in the middle of the tile). We dig up two more hearts while walking up a bit so the Rope will charge at us when it's at the right Y-position. The Rope hits us and we dig up another rupee, the 11th part object. Then we hit the Rope straight up, which kills it and makes the fairy spawn in the right place. With the final boss of this run defeated, all that's left to do is picking up the rupee we just dug up and manipulating the fairy to move to the right place, then we open the map and select tile 1 E2, which is the last required input of the run. The game then runs the following code in RAM:
(All numbers in hex. Addresses omitted are all 00 (NOP).)
| Address | Name of the address | Value | Opcode | Comments |
|---|---|---|---|---|
| AF = D500 BC = 038D DE = CCDB HL = FAD5 | ||||
| FBC0 FBC1 FBC2 | Enabled ID SubID | 01 01 00 | LD BC, 0001 | Start of the fairy data BC = 0001 |
| FBC4 | State | 02 | LD (BC), A | |
| FBC6 FBC7 | Counter1 Counter2 | CE 40 | ADC A, 40 | A = 15 Carry flag set |
| FBC9 | Angle | 14 | INC D | DE = CDDB |
| FBCA FBCB FBCC | Y subpixel Y pixel X subpixel | DA 00 C6 | JP C, C600 | The jump to the filename |
| C602 C603 | byte 1 byte 2 | C6 75 | ADD A, 75 | Start of the filename A = 8A |
| C604 C605 C606 | byte 3 byte 4 byte 5 | EA EF C2 | LD (C2EF), A | Writes the credits cutscene to the Cutscene Index End of the filename |
| From here it's just random data executed as code | ||||
| C608 C609 C60A | (always 01) KidName byte 1 KidName byte 2 | 01 00 00 | LD BC, 0000 | |
| C611 C612 C613 | (always 01) FileIsLinkedGame FileIsHeroGame | 01 00 00 | LD BC, 0000 | |
| C620 C621 C622 | TotalEnemiesKilled low byte TotalEnemiesKilled high byte PlaytimeCounter LSB | 01 00 08 | LD BC, 0800 | |
| C623 | PlaytimeCounter byte 2 | 4E | LD C, (HL) | Our in-game time is 19976 frames (decimal) |
| C627 | TotalRupeesCollected low byte | 02 | LD (BC), A | |
| C629 | TextSpeed | 02 | LD (BC), A | |
| C62B C62C C62D | Group Room StateModifier | 01 E7 00 | LD BC, 00E7 | Start of DeathRespawnBuffer |
| C62F | Y | 95 | SUB L | |
| C630 | X | 78 | LD A, B | |
| C634 | linkObjectIndex | D0 | RET NC | Carry flag is set, so no return here |
| C637 | End of DeathRespawnBuffer | |||
| C63A C63B C63C | MinimapGroup MinimapRoom MinimapDungeonMapPosition | 01 E7 00 | LD BC, 00E7 | |
| C63E | PortalGroup | FF | RST 38 | This is set to FF at the beginning of the game |
| 0038 | Start of some unused code that pops all the registers and then returns | |||
| 003B | E1 | POP HL | ||
| 003C | D1 | POP DE | ||
| 003D | C1 | POP BC | ||
| 003E | F1 | POP AF | (SP) = 01F8 | |
| 003F | D9 | RETI |
And from here we're back in ROM and the game keeps running normally. Since the map never closed properly, the background map, tileset, and palettes of the map screen are still loaded, which leads to some glitchy textures. The music volume also never got reset to the normal level, so the music will continue being more quiet than usual for the entire credits.
After a while the screen goes black and the title card is supposed to load in. This doesn't happen however. The reason is that the background map for it is usually preloaded into addresses $9C00 - $9FFF at the end of the previous cutscene while the screen is still displaying the map in $9800 - $9BFF. Then at the beginning of the credits proper, the game just switches between the two. Since we never watched the previous cutscene, the second map is just filled with zeros and all we get is a unicoloured screen.
The cutscene after that already uses all available sprite slots under normal circumstances, so the fact that we spawned some extra enemies leads to some of the sprites disappearing. Other than that the credits continue as expected and we reach the end screen without incident.
Special Thanks
Stewmath for creating the Oracles disassembly!
Alyosha for bringing subframe inputs to the GameBoy!
ThunderAxe31: Claiming for judging.
ThunderAxe31: Correcting CycleCount value.
ThunderAxe31: Replacing movie file with an actually fixed one.
Great job! I see there was an extensive research behind it, and it's also very optimized. Accepting as a new branch.
fsvgm777: Processing.
feos: SubGBHawk doesn't assign CGB flag, adding it manually.
ThunderAxe31: Replacing movie file with a truly actually fixed one.
ThunderAxe31: Hopefully this is the last time.