Tree Warp

Tree warp, or Dynamic Sprite Spawn Overflow (DSSO) for the glitch in general, is a strong contender for the coolest glitch. I've explained it before using the Agahnim 2 stal, but for this explanation, I'll be focusing on tree warp.

Sprite spawning

There's a lot to discuss with how sprites spawn, but let's focus on the basics for this. The basics are all we really need. There are 16 active sprite slots in WRAM, and there are 3 ways to spawn sprites:

Static spawning
is how sprites are spawned in the underworld. Every room has a list of up to 16 sprites, and they are all loaded into the active sprites array when the room is loaded.
Semi-static spawning
is how sprites are spawned on the overworld. Every overworld area has a list of sprites, but it doesn't have the same 16 sprite limit in ROM that the underworld does. Instead, sprite references are first loaded into a buffer where they don't actually run code. When you get close to where a sprite is placed, then it is pulled out of the buffer and put into the active sprites array, assuming there's room. If there's no room, it just doesn't spawn.
Dynamic spawning
covers everything else. When some routine wants to spawn a sprite when an area has already loaded or under specific circumstances, the sprite's ID is loaded into a CPU register and the routine Sprite_SpawnDynamically is called.

When a sprite is spawned, no matter what method, it undergoes certain preparations to set its coordinates, AI pointers, etc., along with a routine that each sprite has specifically designated to it. Sprite prep happens exactly once.

Dinomaniac spawning

As mentioned before, there are only 16 slots for active sprites to be in. To make sure there's room, Sprite_SpawnDynamically starts an index register at 15 and uses it to count down through all the sprite slots by looking for a sprite that is totally inactive and dead. If it finds an empty slot, it jumps ahead to set its properties and run its prep routine. Actually, it branches ahead, but if I said "branches", anyone who doesn't understand assembly terminology might get confused. Or maybe not, I'm sure the context makes it obvious.

Ahem…

If there was no room, then our index register hits −1, which for an 8-bit two's-complement is $FF, equivalent to an unsigned value of 255. If we go negative, the search loop is broken and the CPU returns to wherever the routine was called from. And that's all it does when there's no room. Handling the case of "there's no room, buster" is left to the whatever wanted the sprite to spawn in the first place.

And handle that they do. For the most part. Almost every call to this routine is followed by the instruction BMI, which means, in some sense, "go here if the last number we saw was negative, otherwise just ignore me". A couple are followed by the opposite, BPL, which means to follow where it's pointing when the number is not negative. It's the Master Sword, okay. The Master Sword, scourge of evil, was programmed by a got dang intern. But at least that intern had the sense to include the failsafe used everywhere else.

Arbor Day 2019

The same can't be said for whatever intern coded the talking tree sprite. These guys break so many rules. First of all, these guys use 3 sprite slots. 1 for the mouth, 2 for the eyes. Secondly, they have the persistence bit set. You see, on the overworld, when most sprites go off screen, they have the decency to deactivate themselves and return to the buffer. This allows other sprites to spawn in their place. Not talking trees. Once those 3 sprites are in their slots, they grasp onto them until you transition. If you visit both trees in the Village of Outcasts, you now have tree rudely hogging 40% of your sprites.

And finally (for the sake of time), trees spawn their eyeballs recklessly. Only the mouth is a semi-static spawn. When it's spawned into the main list, its prep routine performs 2 calls of Sprite_SpawnDynamically, one for each eye. What it doesn't do is check for success. Talking trees are of a small handful of sprites that assume that there will always be a free sprite slot. Of that group, it's probably also the most careless to have made that assumption. Tree warp specifically happens when there is exactly 1 free sprite slot; i.e. the mouth takes the last available slot, leaving nowhere for the eyeballs to go.

The Overflow

What exactly happens when this assumption is made depends on where it was made, but in every case, just spawning a sprite is not good enough. Now that the sprite is spawned, routines continue prepping it in whatever ways are needed. There's just one itsy-bitsy problem: our index is out of whack. Remember that failure is indicated by an index of $FF being reached, that means we're waaaay out of bounds, and whatever we do will be operating on the invalid sprite slot 255.

Okay, so we're way out of bounds, but what exactly are we writing? Let's go through the routine in plain English:

  1. Put the sprite index for the talking tree and the eyeball id (0 or 1) we're working with in a safe place so we can't forget them.
  2. Tell the dynamic spawn routine to create sprite id $25, which is a talking tree.
  3. Failsafe? Screw that. I am the greetest, so I know there will always be an empty sprite slot.
  4. Get the eyeball number from the safe place and put it on the sprite we just spawned as a property.
  5. Load the value in address $00, which holds the low byte of the tree's mouth's X-coordinate. I know that's for sure what the address holds, because I'm an expert.
  6. Add to it the value −4 if our eyeball number is 0, or 14 if our eyeball number is 1. Store that to the new sprite's X-coordinate, based on its index.
  7. Load the value in address $01, which holds the high byte of the tree's mouth's X-coordinate. I know that's for sure what the address holds, because I'm a torpedo.
  8. Add to it the value −1 if our eyeball number is 0, or 0 if our eyeball number is 1. Store that.
  9. Get what is "definitely" the low byte of the mouth's low Y-coordinate and add the value −11. Store that.
  10. Get the totally not possibly incorrect value of the mouth's high Y-coordinate. Store that.
  11. Set a property to 1 on the sprite to indicate that it is ocular, rather than oral.
  12. Get the mouth sprite index from the safe place.
  13. Exit routine.

I kept the rest of the steps brief, because I feel like you already had the idea. I kept going, because it felt wrong to not describe the whole routine.

But, developer ol' buddy, you're wrong. That failsafe is important. You're not loading an X-coordinate, nor are you putting it anywhere near where an X-coordinate can be. But if it's not an X-coordinate, what is it? Well, it's a little complicated, but bear with me.

Tracing backwards, the last time that addresses $00 and friends were modified was when we were running the sprite prep routine for the tree's mouth. It took the sprite ID and then called UseImplicitRegIndexedLocalJumpTable. That's a long name, and a fairly intricate routine if you're not familiar with assembly, but it basically is a way for the CPU to take a value and then pick a routine from a table based on that value. It does so by taking the 24-bit address of the routine and putting it in memory at $00, $01, and $02 and jumping from there.

In the case of tree warp, the routine we jump to is SpritePrep_TalkingTree, which is at $06:904A. So we have $4A in address $00, $90 in $01, and $06 in $02. There's also something in $03, but no one really cares. It won't even be consistent.

So we know what wrong values we have, but where are they writing? Mostly inconsequential places, really. Mostly. Offsetting 255 into most of the properties gives us a write to some timer, or the DMA buffer. You might cause a jerk in some sprite's behavior, but nothing that big. The DMA buffer is just going to be updated before it's needed, so it doesn't cause issues either.

The problem child is that high byte of the X-coordinate. From everything explained above, we know that this value is loaded from $01, but that this address will contain the value $90 from a previous routine. The X-coordinate high byte array begins at $0D30, so we need to see what address is that offset by 255. Whip out calculator.exe and set it to programming mode, and you'll find the answer to be $0E2F. That's the Fth sprite slot.

You're getting grabby

We are writing $90, the sprite ID for wallmasters, into memory that holds a sprite's ID. It doesn't matter what sprite was in that slot before, it is now a wallmaster. It's really hard to pinpoint why the wallmaster grabs you right away and instantly fades to black, but the most common scenario seems to, once again, involve the tree. This time, it has to do with how trees never go inactive.

Let's quickly explain how wallmaster grabbing works: If the wallmaster is alive, it doesn't let go of Link. If it's active, it can execute its code. If the address $0D9x is nonzero, then Link is considered grabbed. Got it? Good.

Simply by how semi-static spawning works, it is very likely that a tree's eyeball will be in sprite slot 15. This means sprite slot 15 will already be set as active, permantently at that. For some reason that I'm too scared to learn, the routine outlined above also stores each coordinate in another address. In the case of the X-coordinate, this address is $0D9x, the same array of values used by wallmasters to indicate that they have grabbed Link.

So that means we're not just spawning a wallmaster. We are spawning a super wallmaster. One from which there is no escape.

In cases where there is not an eyeball as the last sprite, it seems the wallmaster just behaves normally. If it's offscreen, it will despawn to free up space, but, being a dynamically spawned bastard, it will find no home in the buffer. If it's onscreen, you may catch a glimpse of it flying away. I've seen it only once, but it was a magical moment.

When things go terribly wrong

Tree warp works when only 1 sprite slot is free before spawning the mouth. When 2 slots are free, things go really really wrong and the game crashes.

This crash is purely bad luck with ROM data. If 2 slots are free, that means the mouth takes one and eyeball 0 takes the other. So eyeball 0 spawns successfully, in the correct slot, and due to the prep that happens in Sprite_SpawnDynamically, we now have a new value in $01: 3. Eyeball 1 ends up overflowing, writing 3 to the last sprite slot.

When it comes to sprite IDs, 3 is particularly evil. There isn't actually a sprite with that ID. That slot in the sprite prep routines table just contains a pointer to $0000. That's the same $00 we were storing scratch data in, but now we are executing it as code. And because it's consistent from the previous routines, I can tell you exactly what the CPU is doing:

$68 |
PLA
$03 $50 |
ORA $50, S
$09 $00 |
ORA #$00
$00 $00 |
BRK $00
$82 $68 $03 |
BRL $0368

And that's where Mr. Smith hits the fan. BRK is an instruction inherited from the WDC 65c816, which the SNES's Ricoh 5A22 is based on. The instruction is meant to be used in a debugging environment on a computer's operating system to track down bugs and errors. That obviously is of no use for a cartridge game running on a console, so the developers replaced the break vector with $FFFF, just a filler value. The CPU doesn't know that though, so it follows it blindly. The byte at $00:FFFF is $82, which is the byte for a branch long instruction (BRL). But this is the end of the bank, so the operand of this instruction is read by wrapping around back to $0000. Data we executed as code is now being used as a relative pointer for the CPU to follow. It's telling us to branch forward $0368 bytes and resume execution at $036A. This address is related to lifting tiles, and it will hold a value based on the last liftable tile you touched. Long story short, there's no predicting what happens next.

What else can we spawn?

You're in for a challenge if you want to overflow any of your other spawns. I will cover the ones that are reasonably doable.

The second easiest DSSO to perform is the digging game. Not even a perfect TAS can dig up enough prizes fast enough to fill the sprite list unassisted. I've tried. Although, with a little help from Qirn, you can bring a cucco down to the digging game and smack it silly until it summons a swarm. For this DSSO, the sprite spawned is based on your X-coordinate. You'll get sprite $00 (crow) on the west half of the screen and sprite $01 (vulture) on the east half.

With perfect timing, you can mess with the clone animations in the Agahnim 2 fight and have them fill every slot. If the main Agahnim spawns the phantom Ganon then, he'll end up creating a hopping bush stal instead (sprite $D3). This is the original DSSO discovered, during the making of the 100% Glitched TAS.

I've not actually seen it done, but it should be possible to bring enough sprites on screen on Death Mountain so that when the old man tagalong turns into a sprite, he DSSOs himself. In this case, you just softlock your game. The old man sprite is what gives you control of Link by ending the cutscene. It's sort of like returning him in the rain state without an overlord, but slightly less funny, because there's no geezer wandering off into infinity.

Was it really that stupid?

Except for the tree warp, everywhere else that a dynamic sprite spawn underflow can occur is pretty difficult to pull off. For the most part, it's a fair assumption that there would be room somewhere. After all, if that assumption were bad, it wouldn't have taken 27 years for this glitch to be discovered. Actually it was just under 27 years. I found this on 12 November 2018, 9 days before LTTP's birthday. It also only happened during trial and error optimization of a TAS, and it was difficult to reproduce at first.

Hey dummy, you missed something

Ya, kinda. I sort of glossed over the fact that while we have $90, we're adding the value $FF to it. I quietly ignored this because it's difficult to explain without breaking the flow of that already messy paragraph. In 65816 assembly, addition is always done with a carry. It's like "carrying the 1" you learned as a 5-year-old. For our coordinates, we're working with 16-bits in 2 segmented bytes. Before we do the high byte, we're adding $FC to whatever was in our low byte. For tree warp, our low byte was $4A, so the sum is $146. That's bigger than what you can express with 8 bits, so the accumulator holds $46 and the carry flag is set. When we deal with the high byte, we leave the carry alone to use it in our calculation. This means our full equation is $90+(−1)+1. The carry flag cancels with the −1, and we're left with our original $90. This also applies to the explanation of the game crash when tree warp fails.

I bet you feel bad now for calling me a dummy even though it was me who called me dummy.

Summary

For some stupid reason, the talking tree is composed of 3 permanently active sprites—1 mouth, 2 eyes. The eyes are spawned dynamically by the mouth. When spawning sprites dynamically, the caller of the routine is left with the responsibility for adding a failsafe when all slots are full. Trees don't.

If the mouth spawns into the last available sprite slot, the eyes will end up in slot $FF. Part of these invalid writes loads a value from scratch space to use for the X-coordinate. The value it loads ends up being part of the tree's spawn routine address ($90), and it gets written to the last slot in sprite ID. This is the ID for a wallmaster, which ends up inheriting the properties of whatever sprite was in that slot. In the consistent set ups, this sprite is part of the other talking tree in Village of Outcasts, so the wallmaster is always active. And by sheer coincidence, it spawns immediately in the "grabbed player" mode.