Difference between revisions of "Dynamic Sprite Spawn Overflow"

From ALttP Speedrunning Wiki
Jump to: navigation, search
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{Technical}}
+
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 overflows to {{HEX2|FF}}. Most dynamic sprite spawns take this into account, and use {{HEX2|FF}} to indicate failure; however, some sprites ignore that possibility, and continue on with the invalid index. One of these writes is to the 255th sprite's X-coordinate high byte, which doesn't exist and actually writes to the slot F sprite ID.
  
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 {{HEX2|FF}}. Most dynamic sprite spawns take this into account, and use {{HEX2|FF}} to indicate failure; however, some sprites ignore that possibility, and continue on with the invalid index.
+
For a more in-depth technical break down, see [https://spannerisms.github.io/treewarp this page].
 
 
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 <code>Sprite_SpawnPhantomGanon</code> ({{HEXA|1D88A1}}).
 
<pre>
 
LDA #$C9
 
JSL Sprite_SpawnDynamically ($1D:F65D)
 
</pre>
 
 
 
This routine begins by loading the value {{HEX2|C9}} into the accumulator (henceforth <code>A</code>) and then jumping to the routine <code>Sprite_SpawnDynamically</code> ({{HEXA|1DF65D}}). {{HEX2|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 {{HEX2|0F}} is loaded into the <code>Y</code> index register (henceforth <code>Y</code>), and the accumulator is pushed to the stack. Following that is a loop to check the status of all 16 sprites, starting with sprite {{HEX2|F}} and ending with sprite {{HEX2|0}}.
 
 
 
<pre>
 
Sprite_SpawnDynamically: ; $1DF65D
 
LDY #$0F
 
PHA
 
 
 
-- LDA $0DD0, Y : BEQ ++
 
DEY : BPL --
 
 
 
PLA : TYA
 
RTL
 
</pre>
 
 
 
If the slot being checked is deemed empty, the CPU will branch ahead to continue the routine. Otherwise, <code>Y</code> is decremented, and if the new value of <code>Y</code> 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, <code>Y</code> reaches {{HEX2|FF}}, or −1, meaning the branch instruction for trying again is ignored. When that happens, the top of the stack is popped into <code>A</code> just to balance the earlier push and then the <code>Y</code> register is transferred to <code>A</code> 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 <code>BMI</code> (branch if negative) or, less commonly, <code>BPL</code> (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.
 
 
 
<pre>
 
JSL Sprite_SetSpawnedCoords ($09:AE64)
 
</pre>
 
 
 
This routine is as such:
 
 
 
<pre>
 
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
 
</pre>
 
 
 
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 <code>Y</code> as an offset. Under normal circumstances, <code>Y</code> 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:
 
* {{HEX2|00}} to {{HEXA|0D10|s=, Y}} : Low byte of X coordinate
 
* {{HEX2|01}} to {{HEXA|0D30|s=, Y}} : High byte of X coordinate
 
* {{HEX2|02}} to {{HEXA|0D00|s=, Y}} : Low byte of Y coordinate
 
* {{HEX2|03}} to {{HEXA|0D20|s=, Y}} : High byte of Y coordinate
 
* {{HEX2|04}} to {{HEXA|0F70|s=, Y}} : Height (Z coordinate)
 
 
 
That seems fairly straightforward, but there are 2 problems. First off, nothing is done to verify or fix the <code>Y</code> 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 <code>Y=$FF</code> (255):
 
* {{HEXA|0D10|s=, Y}} → {{HEXA|0E0F}}, 1st slot from the back of sprite auxiliary timers
 
* {{HEXA|0D30|s=, Y}} → {{HEXA|0E2F}}, 1st slot from the back of sprite ID
 
* {{HEXA|0D00|s=, Y}} → {{HEXA|0DFF}}, 1st slot from the back of general timer
 
* {{HEXA|0D20|s=, Y}} → {{HEXA|0E1F}}, 1st slot from the back of more auxiliary timers
 
* {{HEXA|0F70|s=, Y}} → {{HEXA|106F}}, data point in a DMA buffer
 
 
 
Notice {{HEXA|0D30|s=, 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 ({{HEXA|00}}–{{HEXA|04}}) are written later in the <code>Sprite_SpawnDynamically</code> 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 {{HEXA|01}} was last set at {{HEXA|008793}}, part of the routine <code>UseImplicitRegIndexedLocalJumpTable</code> ({{HEXA|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 {{HEXA|1ED34F}}
 
 
 
<pre>
 
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
 
</pre>
 
 
 
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 {{HEXA|00}}. Because it's 2 bytes in little endian format, address {{HEXA|00}} takes the lower byte ({{HEX2|DA}}), and address {{HEXA|01}} takes the higher byte {{HEX2|D3}}.
 
 
 
This operated exactly as intended, taking us to Agahnim's death subroutine that calls <code>Sprite_SpawnPhantomGanon</code>; 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 ({{HEX2|D3}}) being stored to the 1st sprite ID slot from the back. {{HEX2|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 {{HEX2|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 ==
 
== Tree Warp ==
Line 103: Line 9:
 
|float = right
 
|float = right
 
}}
 
}}
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.
+
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 {{HEX2|90}} from address {{HEXA|01}}, which was put there by <code>UseImplicitRegIndexedLocalJumpTable</code> again. This time, the target address for the jump was local address {{HEX2|9043}}, which is routine <code>SpritePrep_TalkingTree</code>.
 
For the tree, the wallmaster comes from loading the value {{HEX2|90}} from address {{HEXA|01}}, which was put there by <code>UseImplicitRegIndexedLocalJumpTable</code> again. This time, the target address for the jump was local address {{HEX2|9043}}, which is routine <code>SpritePrep_TalkingTree</code>.
  
 
[[Category:Major Glitches]]
 
[[Category:Major Glitches]]

Latest revision as of 11:57, 27 August 2021

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 overflows 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. One of these writes is to the 255th sprite's X-coordinate high byte, which doesn't exist and actually writes to the slot F sprite ID.

For a more in-depth technical break down, see this page.

Tree Warp

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.