Arbitrary Code Execution

Figured out by TrogWW, ShadowQCD, MrCheeze, LegendofLinkk, LagoLunatic, minimini352, EJ125, azer67

Description

Arbitrary Code Execution (or ACE for short) is what happens when a glitch allows directly modifying the games code to anything we would like. This is sort of the "ultimate" glitch, as it allows almost anything to become possible : creating new actors or stages, modifying existing actor behaviour and so much more. Due to how degenerate this is, this glitch is generally banned in every speedrun category except any%.

The current entry point for ACE in The Wind Waker is through a glitch called Text Stacking. That glitch essentially allows one to have two textboxes on screen (and in memory) loaded at once, which is normally impossible. This leads to a pointer becoming stale and with the right manipulation of the games memory, this can be heavily abused.

Technical Explanation

When a textbox is created normally, the NPC is assigned a pointer called d_msg::sScreen. sScreen is used to tell the NPC where the screen data for a textbox is loaded into memory. The game never expects more than one textbox to ever be loaded at a time, and never anticipated a need to use more than one sScreen pointer. After performing text stacking, both NPCs will share the same value for sScreen and now believe that their screen data are in the EXACT same place in memory. This can be exploited to trigger Arbitrary Code Execution.

On the US version, by performing the text stacking glitch on Outset or Windfall, the d_msg::sScreen pointer will be dangling and will consistently point to address 81579F34, which is in the FopMsg heap (where hub elements such as textboxes and pictographs load). When pulling out the pictobox, this address corresponds to pixel data from the third saved picture. By having the 4 bytes of pixel data at 81579F34 write a valid address and then performing the text stacking glitch and triggering the crash while the pictobox is out, we can instead jump to the address written with that pixel data +8.

These are the exact steps for the text stacking setup and what happens internally:

• When storing the first NPC textbox, proc_msg actor 1 gets created and creates a new J2DScreen and stores it to sScreen.
• When storing the second NPC textbox, proc_msg actor 2 gets created and creates a new J2DScreen and stores it to sScreen, overwriting the value from actor 1 (it's a static so it is shared between all of the messages, since the game never expects more than one message actor to be loaded at a time).
• Both textboxes are closed while the actors that created the texboxes are culled. The actors wont call the delete function until the culled actors are back on screen. We uncull actor 2 so that it requests the proc_msg actor 2 to be deleted: sScreen then tells dMsg_delete that it needs to run code at whatever value sScreen is +8 in order to actually delete the screen from memory. This deletes the instance in the FopMsg heap and frees the memory in the heap, but does not null out the pointer. The space that was occupied by that screen is now free to be used by other UI (user interface) elements. The game is still waiting for actor 1 to get unculled before deleting his text.
• By rotating the camera in a precise way by pulling out the pictobox, the following 2 things happen in 2 consecutive frames. First, the pictobox J2D elements get loaded into the freed space within the FopMsg heap, and the 3rd image data just so happens to load into the same area in the heap as the address sScreen points to. Next, actor 1 unculls and the proc_msg actor 1 will call dMsg_delete to attempt to delete itself. It doesn't know that msg actor 2 overwrote its sScreen value, so it frees the same J2DScreen thinking it's the one created by itself (it has a check to not do this if sScreen is null, but it never gets nulled out). The pictobox data has however already been written into the FopMsg heap on the previous frame, and the game will use the pictobox data to look up what address to branch to for deleting the J2DScreen element. More precisely, it will use pixel data from the third saved pictograph picture.

By taking a picture of a bush on Windfall with the exact right position and angle, it is possible to write 80ABBDFF in the pixel data of the third picture. This will make the code jump to that address +8, which corresponds in the early game to the address of the 4th bytes of Link's X position in Link's actor instance in the Zelda heap.

We can then use the 4th byte of Link's X position and the first 3 bytes of Link's Y position to write another address and jump to it. This time, we write down the address of the inputs from controllers 2 to 4 : 803F0F3C, and jump to it. In order to write this address, we need the last byte of Link's X position to be equal to 0x80, and then stand on the shore with a Y position in the [0.5595093 ; 0.5595245] range in order to write 0x3F0F3C.

Now that we've jumped to the address of controllers 2-4, we have full control over enough consecutive bytes to write meaningful code to break the game. By having these controllers performing the exact inputs we want, we can write data we can make the game read as code. The current payload that allows warping to the credits is the following:

This payload replaces a comparison check to see if it should or shouldn't play the credits upon stage transition with a nop, then branches to a safe location that avoids freeing all of dMsg (and not just the obviously invalid stuff that crashes) to avoid messing up the heaps and prevent a crash. This particular payload uses controller 3 to jump to a gadget (an area of existing code that happens to perform useful instructions without needing to write them via the payload itself) at 80040FA0 that ORs r0 with r3 to make r0=0x81579F36, and then the next line of the gadget writes the last byte 0x36 to an address given by r5, which we manipulate with controllers 2 and 4 to point to the first byte of the "branch to avoid credits" instruction at 80234C7C, overwriting it and turning it into a harmless addition instruction

The line of code that is nop-ed out

To summarize, this is how to perform a Credits Warp in The Wind Waker using Arbitrary Code Execution:

• Play the game on the US version to have the text stacking glitch align favorably with the third picture pixel data.
• Take a precise picture in the pictograph's third slot so that the pixel at 81579F34 (when the pictobox is out) writes 80ABBDFF.
• Perform the text stacking glitch on Outset or Windfall, but don't trigger the crash yet.
• Stand in a precise spot so that Link's X position 4th byte and the first 3 bytes of Link's Y position write 803F0F3C.
• Have controllers 2-4 hold the inputs used to write the payload.
• Pull the pictobox and trigger the dMsg_delete crash. Due to the precise pixel data in the 3rd picture, the game will jump to the adress of Link's coordinates, which will cause a jump to the address of the controller inputs, and will then execute the code written with the controllers. The payload will avoid the crash and allow the next loading zone to load the credits.
• Enter a loading zone to warp to the credits.

Video Demonstration

Notes:

• It is important for the code that is executed to be 4 bytes aligned, meaning executing data as code can only be done if that data is found in RAM at an address that ends with digits 0, 4, 8 or C. The game will crash otherwise.
• This setup currently only works on the US version. On the japanese version, the dangling pointer lines up with the third picture palette data which is harder to make use of, and on the PAL version the dangling pointer does not line up with anything that can be used.
• If actor 2 is not unculled exactly one frame after the pictobox elements are loaded, a different crash will be triggered from the message actor calling dMsg_execute, instead of dMsg_delete. This crash can also potentially be used for ACE, but the dangling pointer is not the same and points too early in the FopMsg heap to be able to line up with pictobox data on all versions. The dangling pointer is found inside the first proc_msg instance and is called mpPane in field 0x49C.
• If you are still lost after reading this attempt at an explanation, you can also read TrogWW's version here (external link).

Setups for RTA

Setup to get 0x80ABBDFF in the 3rd picture data

How to perform the text stacking glitch on Outset

Faster end to text stacking

Setup to have Link's position on Outset write 0x803F0F3C to jump to controller inputs

Setup to get 0x80AAD5AF in the 3rd picture data with deluxe pictobox (alternate way to do ACE after beating FF1)

Setup to have Link's position on Windfall write 0x803C52B8 to jump to figurine address (alternate way to do ACE with figurine payload)

Other Payloads

The payloads in the table below use the usual controller setup, described above, to write the payload.

Any% Credits Warp (ShadowQCD)
Controllers (0x803F0F3C)	Instructions	Hex Code
2	lwz r5, 0x0010(r12)	0x80AC0010
3	b -> 0x80040FA0	0x4BC5005C
4	N/A	0x80234B78
Credits Warp No Post-Credits Crash (ShadowQCD)
Controllers (0x803F0F3C)	Instructions	Hex Code
2	lis r3,0x8023	0x3C608023
3	stw r5,0x4C7C(r3)	0x90A34C7C
4	b -> 0x80215664	0x4BE24718
Map Select on Soft Reset (LegendofLinkk)
Controllers (0x803F0F3C)	Instructions	Hex Code
2 (analog)	lwz r29, -0x50B4(r31)	0x83BFAF4C
3 (buttons)	mulli r4, r0, 3	0x1C800003
3 (analog)	stb r4, -0x3C3D(r29)	0x989DC3C3
4 (analog)	b -> 0x8021566C	0x4BE24720
Map Select on Stage Load (LegendofLinkk)
Controllers (0x803F0F3C)	Instructions	Hex Code
2	li r3, 6	0x38600006
3	stb r3, 0x5D1B(r28)	0x987C5D1B
4	b -> 0x80215664	0x4BE24718

There are alternate ways to write a payload that do not involve precise controller inputs. By standing in a different position, we can make code jump to other addresses, one of them being figurine data. A payload can then be written by collecting very specific figurines. Writing a specific payload with this method is much harder because figurines can have dependencies.

Figurines Credits Warp (ShadowQCD)
Figurines (0x803C52B8)	Instructions	Hex Code
Baito Figurines & co	addis r16,r28,0x1F	0x3E1C001F
Mako Figurine & co	stw r5,0x7AA0(r16)	0x90B07AA0
Mila Figurine & co + Koroks	b -> 0x80215664	0x4BE503A4

This payload corresponds to the collection of the following figurines highlighted in blue, and you get to pick between the green/yellow/orange pairs.

After beating FF1, the pixel data of 80ABBDFF will no longer line up with Link's position data. In this instance it is needed to get a different picture. Another pixel that can be saved for that case is 80AAD5AF, which will line up on Windfall.

Total Control ACE

Discovered by ShadowQCD

With every setup discussed up until now, we were limited to only a couple instructions for our payload. Being able to write as many instructions as we would like would allow much more degenerate applications of ACE. This is called Total Control ACE, and there are a few ways to do it.

After performing the ACE setup, if you have the controller 4 instruction be a branch to the following 4-instruction pattern (which is found over 700 times in the game's code, here at 0x80215688), then the game will loop through controllers 2 to 4 indefinitely, as long as Link doesn't move (otherwise the game would crash). This allows writing as many instructions as we would like, at the rate of 2 instructions per frame.

Another, more efficient, method of Total Control ACE is to have controller 4 branch to controller 2 directly. This creates an infinite loop which freezes the game. This prevents the game from refreshing the controller data's instruction cache however, so we need controller 3 to do that, and this only leaves controller 2 for useful writes. We can run a payload this way (which requires being able to perform several hundreds inputs per second, so it is extremely unrealistic to do humanly). Once the payload is over, controller 4 can change inputs to branch back to gameplay, past the point where Text Stacking would normally crash.