Dynamic Sprite Spawn Overflow

From ALttP Speedrunning Wiki
Revision as of 10:22, 26 February 2020 by Kan (talk | contribs) (Fmp moved page Dynamic Sprite Spawn Underflow to Dynamic Sprite Spawn Overflow without leaving a redirect)
Jump to: navigation, search

The long and short of this glitch is that if all sprite slots are occupied when certain dynamic sprite spawns are called, the intended sprite will not spawn; instead, a completely different sprite will spawn. This happens because the CPU goes through all the sprite indices and underflows to $FF. Most dynamic sprite spawns take this into account, and use $FF to indicate failure; however, some sprites ignore that possibility, and continue on with the invalid index.

This glitch is actually relatively easy to explain, and we will use the first version discovered to explain it in detail.

Phantom Ganon Stal Spawn

If all sprite slots are occupied when Agahnim 2 attempts to spawn phantom Ganon, he will instead spawn a hopping bush stal with 255 HP.

We can begin explaining this glitch looking right at the routine Sprite_SpawnPhantomGanon ($1D88A1).

	LDA #$C9
	JSL Sprite_SpawnDynamically ($1D:F65D)

This routine begins by loading the value $C9 into the accumulator (henceforth A) and then jumping to the routine Sprite_SpawnDynamically ($1DF65D). $C9 is the sprite ID for the phantom Ganon bat, the sprite that is intended to spawn. At the beginning of the dynamic spawn routine, the value $0F is loaded into the Y index register (henceforth Y), and the accumulator is pushed to the stack. Following that is a loop to check the status of all 16 sprites, starting with sprite $F and ending with sprite $0.

	Sprite_SpawnDynamically: ; $1DF65D
		LDY #$0F
		PHA

	--	LDA $0DD0, Y : BEQ ++
		DEY : BPL --

		PLA : TYA
		RTL

If the slot being checked is deemed empty, the CPU will branch ahead to continue the routine. Otherwise, Y is decremented, and if the new value of Y is greater than or equal to 0 (i.e. the most significant bit is off), then the CPU will branch backwards to perform another iteration of the loop. When all sprite slots are filled, Y reaches $FF, or −1, meaning the branch instruction for trying again is ignored. When that happens, the top of the stack is popped into A just to balance the earlier push and then the Y register is transferred to A before finally returning to the location that called this routine.

The intent here seems to be some method of forcing the index of the sprite slot (−1 always in this case) to be last value looked at by the status register. This allows an easy way to determine if a spawn failed or succeeded. And, indeed, when it is successful, the sprite slot used ends up in the accumulator as well. If a search is performed for jumps to this routine, you will find that most are followed immediately by a BMI (branch if negative) or, less commonly, BPL (branch if positive).

The phantom Ganon spawn routine (along with every other culprit of this glitch) does something different. It assumes the spawn was successful, which is fairly reasonable for normal gameplay. After all, if there were problems with this assumption in general, this glitch would have been discovered earlier. But what exactly causes the bad spawn? Because the previous routine is assumed to always be successful, the game just continues on, where it jumps immediately to another routine, regardless of the outcome.

	JSL Sprite_SetSpawnedCoords ($09:AE64)

This routine is as such:

Sprite_SetSpawnedCoords: ; $09AE64
	LDA $00 : STA $0D10, Y
	LDA $01 : STA $0D30, Y
	LDA $02 : STA $0D00, Y
	LDA $03 : STA $0D20, Y
	LDA $04 : STA $0F70, Y
	RTL

Let's consider the routine's normal functionality first:

All 5 instructions are loading a value from scratch space and storing it to the sprite data arrays, using Y as an offset. Under normal circumstances, Y holds the index of some sprite. In our case, it is expected to contain the index of the newly spawned phantom Ganon.

The values loaded and stored are as follows:

  • $00 to $0D10, Y : Low byte of X coordinate
  • $01 to $0D30, Y : High byte of X coordinate
  • $02 to $0D00, Y : Low byte of Y coordinate
  • $03 to $0D20, Y : High byte of Y coordinate
  • $04 to $0F70, Y : Height (Z coordinate)

That seems fairly straightforward, but there are 2 problems. First off, nothing is done to verify or fix the Y register (remember that we assumed the spawn was successful). So instead of writing to an address that is at most offset by 15 bytes from the start of the array, we are writing to an address that is offset by 255. This means our modified addresses are as follows:

For Y=$FF (255):

  • $0D10, Y$0E0F, 1st slot from the back of sprite auxiliary timers
  • $0D30, Y$0E2F, 1st slot from the back of sprite ID
  • $0D00, Y$0DFF, 1st slot from the back of general timer
  • $0D20, Y$0E1F, 1st slot from the back of more auxiliary timers
  • $0F70, Y$106F, data point in a DMA buffer

Notice $0D30, Y and where it writes. Instead of writing the high byte of the X coordinate, we end up writing the value to the last sprite ID slot. Except we didn't actually load the high byte of the X coordinate. The values looked for at those addresses ($00$04) are written later in the Sprite_SpawnDynamically routine, only when a sprite slot is found. That means these addresses hold something else.

If we look back just a little, we'll see that address $01 was last set at $008793, part of the routine UseImplicitRegIndexedLocalJumpTable ($008781) used to take a value and then decide on a jump location, with the addresses defined as words following the call. This routine was last called in Agahnim's general behavior routine, at $1ED34F

	LDA $0D80, X

	JSL UseImplicitRegIndexedLocalJumpTable
		dw $D4EC ; for $0D80,X = 0
		dw $D4F6 ; 1
		dw $D524 ; 2
		dw $D566 ; 3
		dw $D630 ; 4
		dw $D708 ; 5
		dw $D45E ; 6
		dw $D47C ; 7
		dw $D3DA ; 8
		dw $D408 ; 9
		dw $D376 ; 10

What we need to know here is that LDA $0D80, X is loading the AI subroutine pointer for Agahnim, which, at this point, is 8. Without getting into the complexity of the jump table function, it can be said that the word at index 8 (starting from 0) is stored to address $00. Because it's 2 bytes in little endian format, address $00 takes the lower byte ($DA), and address $01 takes the higher byte $D3.

This operated exactly as intended, taking us to Agahnim's death subroutine that calls Sprite_SpawnPhantomGanon; but, what it also did was set up values that would later be used to create a sprite at the erroneous index 255. We can see here that it was ultimately the high byte of the subroutine address pointer ($D3) being stored to the 1st sprite ID slot from the back. $D3 is the sprite ID for the hopping bush stal.

And to wrap things up, what sprite did this bush stal overwrite? It overwrote a sprite with the ID $C1, a cutscene Agahnim. When Agahnim warps around, those ghost images are all their own sprite. They spawn with 255 HP, likely as just a placeholder. A number of sprite properties are never overwritten by the stal spawn, which is why it has 255 HP and spawns where it does. It inherited these properties from the Agahnim it overwrote. All other addresses that were written to by this invalid index were inconsequential.

Tree Warp

Very similarly, the talking trees in dark world can be manipulated to spawn a wallmaster, which immediately takes Link to the last entrance he used. What's slightly different is that this glitch is triggered when all but one sprite slot is filled. This is because the tree uses 3 sprite slots—one for its mouth, two for its eyes. The eyes routine assumes that if the mouth is loaded, then it's safe to load the eyes. If all sprite slots are filled when a talking tree is brought on screen, it will simply not spawn. We also only get the wall master from the first eye. The 2nd eye will have the high byte of the 1st eye's X coordinate loaded as the new sprite.

For the tree, the wallmaster comes from loading the value $90 from address $01, which was put there by UseImplicitRegIndexedLocalJumpTable again. This time, the target address for the jump was local address $9043, which is routine SpritePrep_TalkingTree.