The first part of the Legend of Zelda is an immortal classic. An ordinary player needs a couple of days to complete, and for the most experienced speed runners, this is a matter of half an hour. However, a very confusing and complex bug, opened by Sockfolder , allows the user to execute arbitrary code directly from the game to complete the game in less than three minutes.

In short, it happens like this:
')

1. Enter the code on the name entry screen.
2. We enter the second dungeon, take the whistle.
3. Go to the cemetery, we call ten ghosts.
4. We wait for the necessary conditions, we pause the game, when the creatures are in certain places.
5. Remove the pause, press A and B simultaneously, and that's it!

Yes, it's awesome. Now let's take a closer look at what happens in the game and how this amazing Legend of Zelda bug is executed.

How to cause an error

So first we enter the code on the name entry screen. File names are stored in memory, and each character corresponds to a specific byte in memory. We give strange names to files, because in fact we write the necessary bytes into memory, which then become assembly code. There are only two limitations:

• we can work only with three files, that is, the program can contain only 3 * 8 characters = 24 bytes;
• we need to enter as the first five characters of one of the ZELDA files if we want to start with the second quest.

We need to start with the second quest for a reason that I will explain later. We call the first ZELDA file, because this name is best suited. Now let's start the game. Before we get to the cemetery, our behavior is almost the same as a normal game. The main thing that we need to do is try not to die twice. Under the "die" refers to death itself, and the frequent transition to the menu. You will understand why this is so from further explanation.



After we got the whistle, we go to this cemetery screen to complete the bug. The error is triggered here, because when using the whistle, an object is created from the tombstone that opens the hidden ladder. This is necessary for the appearance of the bug. And all this is due to the limitations of sprites. In Legend of Zelda on the screen at the same time can be no more than 11 sprites. If you try to create a 12th sprite, the game will not allow it. To reproduce the error, we break the overflow limit and create the 12th sprite.



When you create an object "whistle", the game "forgets" to check how many sprites were on the screen before. So when we create the maximum number of sprites, a sprite is created outside the sprites table, the memory is overwritten, and an unexpected state occurs.

There is a small fragment in memory, starting at offset 350, which stores the identifiers of eleven sprites. Sprite is created when loading the screen, starting from the position with the smallest possible sprite offset. This means that the sprites are looking for a position with a minimum offset, starting at offset 350 and beyond. When a sprite is to be created, the game searches for an empty value in the sprite table to replace it with the sprite identifier, thus creating it. Unlike creating sprites when loading a screen, when trying to create a sprite, the game looks for a position with a maximum offset for the sprite. This means that it first checks whether it is possible to create a sprite at position 10 (0A). If not, then it checks position 9 (09), i.e. offset 359, and so on. If all the positions of the sprites are occupied, then the game "gives up" and does not create a sprite.



However, the developers forgot to perform a border check so that the game could “surrender” when attempting to create a “whistle” object, and the game continues to search for bytes with the value 00 in a place outside the sprites table in order to write the object identifier there. But where does she look for this value first? In fact, this table is part of a larger array that stores information about sprites. When the whistle finds a place to create at the beginning of the table, it starts searching for positions with a value of 00 from the end of the array.

On the cemetery screen, this fragment of the array contains information about the current state of ghost actions. Let's talk now about the ghost action states. Ghosts created in a graveyard move erratically. This is because their actions are controlled by their behavior, determined by their state of action. These action states can have any value from 0 (00) to 5 (05), depending on the actions of the ghost. They are written at the end of an array containing information about sprites.

In general, all these action states correspond to the position in the table of functions defining the actions of ghosts. Since states can have as few as 6 values, the table has the size needed to store all six actions. Here, the state of action 0 (00) corresponds to the acceleration of the ghost. This is important because when the whistle starts searching for a place to create its sprite, it will fill the first position found in the memory with the value 00. The acceleration of the ghost corresponds to action 0, which is written in the code with the value 00, therefore the game considers it to be an empty position and writes the identifier to it whistle 5e.



Then the game tries to execute the code in position 5E of the table, but since the table contains only values ​​up to 05, the game executes garbage data as a code far beyond the table. If you do everything correctly, the "junk" data will lead us to the code that we recorded with the symbols of the files, the game will go to Zelda, and we will go through the game.

However, in order for the bug to work, we need to damage the third action state in the table. So the third created ghost should accelerate, and all subsequent ones should perform other actions (the code of which is not equal to 00). This is important information. Now let's see what happens when we execute the bug.

Making a bug

If we did everything right, the game tries to execute the data in position 5E of the table. It starts reading data as a code, starting at offset 602. The memory at offset 602 and 603 stores information related to the state of Link's action, so we can manage it. When Link is standing, the values ​​at offsets 602 and 603 will be 00. But when we press the B button to use the whistle, the value in 602 will be 10, and when we press A to use the sword, the value in 603 will be 01.



Therefore, when we press both of these buttons at the same time, the adjacent data will be 10 01. The game interprets this data as a BPL branch command to go to offset 605 and execute the data in it as a code. The values ​​in 605 and 606 will be equal to 00 if our health is not too low, and equal to 40 if our health is low. To quickly pass the game, these values ​​must be equal to 00, so you need to try to keep healthy until the bug is executed. The value 00 corresponds to the BRK instruction (break, interrupt). Since it does nothing here, we need the values ​​to be 00 and the game continue to execute the code.



Since we used the sword, the game will continue to execute the instruction in the next odd byte. The following instruction, which is not BRK, is at offset 08, but since we used the sword, the game jumps over it and executes the code at 09 and 0A. The value in byte 09 is always 10, which means that we are again dealing with the BPL branch instruction. Bytes at offset 623 (62E) are related to music. She tries to increase in the process of playing music, but sometimes jumps to smaller values.

This means that in order to make a bug, we need to apply it to a specific piece of music. If the value is small, we have a chance to jump in memory to a region with significantly varying values. They change so chaotically that we cannot control them in order to receive in real time the instructions that the game must carry out. Therefore, the transition here is likely to lead to the hang of the game.



However, after these chaotic data there is a safe data area. Therefore, we will try to jump there. We need more data in the 60A in order to accurately skip the insecure area and get to the permanent, safe data. If we went there, then everything is in order. But at offset 630, there is a Link Death Count. If Link died twice, this value will be 02, which forms the instruction and stops the game. That is why it is important that you do not die twice. So, as a result, we move on to offset 638, which is the beginning of the table that stores the file names. If we get here, the game will execute the code that we entered on the file screen. And here it begins ...

Code

File names are stored in memory in order. This means that the first bytes that we execute is a file named ZELDA. Fortunately, the code executed by these bytes is safe, so we can move on to the rest. Since the name ZELDA is not important, let's consider what the rest of the code does. First we execute three PLP commands (pull from stack, extract from the stack). When we call a function, it writes two values ​​to the stack. These values ​​correspond to where you were in the code when you performed the function. So the game can find out where to return to it after performing the function.

We start by retrieving three values ​​from the stack, and then we perform the return function. We do this in order to return to the place where we were before carrying the bug. Otherwise, the game will not finish executing the data as a code and will freeze as a result. But before we get to the code that damages the memory and ends the game, we need to talk about a few more meanings.

The values ​​in offset 10 of memory correspond to the number of the world in which we are. If we are in the supermundane world, the value is 00. For the first dungeon, the value is 01, for the second, 02, and so on. Since Zelda is in the ninth dungeon, we need this value to be 09. However, we perform a bug in the aboveground world and the value is 00. So we need to find a way to equate it to 09. The value in offset 11 corresponds to some data about the state of the game. When the game is loading, the value is 00, when the game is not loading - 01. We need to load the ninth dungeon, so this value must be equal to 00.

The value at offset 12 corresponds to some part of the state. When the screen is loading, the value is usually 02, when it is not loading - usually 05. Since we want to load the dungeon, this value should be 02.

The last value we want to change corresponds to the quest in which we are. The value in offset 62D corresponds to the first or second quest, and has the value 00 or 01. We started with the second quest, but we want to finish in the first quest, because this way we will confuse the game. Therefore, we need to change this value to 00. This will put us in a strange hybrid of the first and second quests. We need this hybrid state to execute code for a specific purpose. We will look at it when we explain what the code does.



Okay, we set ourselves goals, let's move on to the code. First we have the LSR function (logical shift to the right, logical right shift) for offset 11. This function divides the value in half and writes the remainder to the transfer. 11 is the place in memory that stores the value corresponding to the state of the game, and before this instruction its value is 01. When we divide by two, we get 00 with the remainder 01, because the division is integer. The offset 11 recorded the value 00, and the transfer - 01.

Then we have the ROX function to offset 0D (rotate left, turn left) with the index X. Since we rewrote the state of the third ghost created by us, X is equal to three. 0D + X is equal to 0D + 03, which is equal to hexadecimal 10. Therefore, this function turns left at offset 10. This function multiplies the value at offset 10 by 2 and adds to the carry. The value starts from 0. Zero multiplied by 2 is 0, and 0 + 1 is 1, so the value is written to offset 10.

Now the ROX operation is repeated for offset 0D with index X. The value of X has not changed, it is still three, so this is another turn to the left at offset 10. 1 * 2 = 2, and since we already used the transfer, its value is 0. 2 + 0 = 2, so the value 2 is written to offset 2.

Next we have the third ROX operation to offset 0D. 2 * 2 = 4, and 4 + 0 = 4, so the value 4 is written in offset 10.

The next instruction is LSR at offset 12. We start with a value of 5, so dividing by two gives us the remainder 1. 2 is written to offset 12, and 1 to transfer.

Then the last ROX turn is performed to the left at offset 10. 4 * 2 = 8. The transfer value is 1, we add it to the product, getting 9.

The last instruction before returning is a logical right shift at offset 62D. The value here is 1, because we are in the second quest. And since we are divided by 2, the value will be equal to 0. So we got into the hybrid quest mode.

Now we perform the return function and the game updates the values ​​of its state with the values ​​written in our code. This bug is complete, and we get into the room Zelda. We get there because the hybrid quest confuses the game. She doesn't know where to put Link exactly. And so we find ourselves in the room of Zelda, passing this way the game.



I hope this helps you to understand what is happening inside the Legend of Zelda game when executing an arbitrary code and performing a quick passage of the game.