right

Data Redundancy Errors Explained

There are a lot of variables and objects in a game's internal state.

And more importantly, there are a lot of relationships and connections between these variables and

objects.

In order to have the game run effectively without slowing down, calculations done between

these variables need to be done efficiently.

It is common to sacrifice some memory usage and overall code compactness in order to have

it run faster or be easier to understand.

However, using this extra, redundant data to help code run more effectively comes with

some drawbacks.

Mainly, that it becomes more difficult to retain a consistant, defined state.

Since code efficiency is what's at stake here, error checking is minimal.

Therefore, the code needs to be extra careful that it can't enter an invalid state that

would cause catastrophic errors and glitches.

In this video, we'll look at a couple design patterns that revolve around data redundancy

and then look at some example case studies and see exactly how things can go wrong.

Let's first look at a very simple example of data redundancy.

Suppose you just needed to keep track of a list of items.

It doesn't matter what they are, or even what order they are in.

The only thing you need to know is whether an item is in the list or not, and you should

be able to figure out how many items are in the list.

Say, a list of video game consoles you own.

You would write down each console you own right this moment.

If you ever sold one or gave one away, you would remove it from the list.

And if you ever bought a new one, you would add it to the list.

Easy, right?

If you ever want to know how many consoles you own, you just have to count how many items

are on the list.

One, two, three, four, five, six, seven.

Okay, but what if instead of seven items in a list, you had seven hundred, or seven million?

It would be quite the task to count every item in the list each time you wanted to know

how many there were.

So, to be more time efficient, you could also keep track of how many items are in the list

in conjunction with the list itself.

This is the data redundancy I'm talking about.

You don't necessarily need to keep track of how many items are in the list--it's an intrinsic

property of the list itself.

While it does take up resources to include this metadata in the data structure, the trade

off is well worth it in terms of time needed to query the property of the structure.

But there's additional work you have to do if you provide a shortcut like this.

You have to make sure the new property is valid at all times.

Since we are essentially taking an intrinsic property of this list and copying its value

into a separate field, the value has to be updated accordingly if the base property of

the list changes.

What that means for us is that we have to update our length property each time something

is added or removed from the list.

If we don't, then we risk being out of sync with the data structure.

Therefore, if something is added to the list, we add one to the length, and if something

is removed, we subtract one.

Otherwise, the length property will not match the actual length of the list.

This could cause some serious issues, especially around the edge cases where the list is empty,

or where the list is full (if it has a maximum size).

And as you could probably guess where this was going, this is exactly the sort of problem

that can occur in the item lists in the first generation Pokémon games.

This applies to both the player's item bag as well as the PC's item storage.

Let's look at the exact structure these item lists use in the game.

The very first byte in the list structure holds how many item stacks are currently in

the list.

Then each item in the list is specified one after the other.

Each item element consists of two bytes: one byte for the item's unique ID, and another

byte for the number of items in that stack.

The player's item bag allocated room for 20 item stacks, taking up 40 bytes, while the

PC's item storage has room for 50 item stacks, taking up 100 bytes.

Then, there was a single byte at the end of the list used for marking the end of the list.

Just as a reminder, the data redundancy here has to do with the size of the list, or put

in a different way, finding the end of the list.

The end of the list can be found by either querying the first byte of the structure,

or by just scanning through all the items in the list itself before hitting the terminator

byte.

Actually, let's look at exactly how this terminator works, because it will be useful to know to

understand how the item list can become desynched.

Each item is given a unique ID, starting from 1 and going up to 97 as well as 196 through

250.

And then the quantity for each item stack can be anywhere from 1 to 99.

The terminator is just a special item in the list with the ID of 255, the greatest number

you can represent with 8 bits.

Unlike all the other items, this item, which gets displayed as 'CANCEL' in the item list,

has no quantity associated with it.

This is why the list structure has this odd byte at the end.

When the list is full, the terminator fills this last byte, and it doesn't require a quantity,

saving one byte of memory.

When the list is not full, anything in this region of memory that comes after the terminator

is ignored.

Let's see how the game handles adding and removing items from the list.

To add an item to the list, the size of the list is compared to the maximum possible size--20

for the bag and 50 for the PC.

If the size is exactly equal to this maximum size, the list is determined to be full and

the addition is aborted.

If it is not equal--not just less than, but not equal--then the item is added to the list.

The new item's unique ID is stored in the list at the index corresponding to the list's

current size, which is normally where the terminator is currently.

It's quantity is written in the byte after, and then a new terminator is written in the

byte after that.

Then, the size of the list is incremented by one.

This implementation of this function is adequate.

If the list starts in a valid state--that is, the number of items is between 0 and 20

(or 50) and the quantity for each item stack is between 1 and 99--it will always be in

a valid state after this function.

If the list starts in an invalid state, some unintended behavior could occur.

Suppose the redundant count property was lower than the actual number of items in the list.

When adding the new item, an existing item in the list will get overwritten.

And then every item after it will be lost since a new terminator gets appended to the

list data right after this newly added list entry.

After this though, the list is in a valid state again.

But suppose the redundant count property was higher than the actual number of items in

the list.

The data for the new item would get written to memory, but since this is after the list

terminator, it's not part of the valid part of the list.

Although as you'll see later, this item would still be accessible--you would just have to

scroll past the 'CANCEL' option in the menu.

But these conditions should never happen in the first place, so it's fine, right?

To remove an item from the list, the function responsible needs to be supplied with the

index of the item to remove.

So an index of 0 removes the first item, an index of 1 removes the second item, and so

on.

This index is never checked against any bounds, since it is assumed that it will always be

within the bounds of the size of the list.

The item at this index in the list is identified, along with the item directly after it.

Then the byte at the position of the second item is copied to the location of the first.

Both of these pointers to memory locations are incremented by one and this continues

for the rest of the list.

This effectively shifts all of the items up one position in the list, so that there are

no empty gaps in the data structure.

The item data continues to be shifted back two bytes until the terminator is shifted

over, at which the list size is decremented by one and the function completes.

This implementation of this function is completely adequate as well.

If the list starts in a valid state, it will always be in a valid state after this function.

There is one unintended behavior that is possible when the list starts in an invalid state which

is when there is an item with a quantity of 255.

When shifting the items back a slot, each byte is checked for the terminator, instead

of just the item ID.

So if an item has a quantity of 255, that 255 will be treated as the terminator itself.

This results in the item stack in question being duplicated, and all the items after

it in the list not moving.

This also means the size of the list becomes desynched.

The redundant size byte is still decremented by one, but the size of the list never actually

changed, since one item was removed and one item was duplicated.

But these conditions should never happen in the first place, so it's fine, right?

Well of course, there is a way to glitch an item to have a quantity of 255.

Encountering MissingNo.

sets the highest bit of the quantity of the item in the sixth slot of the bag.

Which happens by the way because the Pokédex registers each Pokémon that you've seen as

a single bit in a large table.

MissingNo.'s dex number of zero gets interpretted as 256, and this table is indexed out of bounds.

The bit that actually ends up being set corresponds to the highest bit of the item quantity of

the sixth item in the bag.

This has the result of adding 128 to the already existing quantity of that item.

So by encountering MissingNo.

once, then tossing enough of the item to get a quantity of 127, then encountering MissingNo.

again, the quantity will become 255.

With this glitched item, you can toss the same item stack over and over since it duplicates

itself.

This ultimately desynches the redundant size property and causes it to continue to decrease

even though the list isn't getting any smaller.

Eventually, this value becomes zero and wraps around to 255 with one more item removal.

With the redundant list size property being 255, you can now access the item list as if

it had 128 items, even though only 20 items worth of space is allocated to memory.

See, the list terminator in this case is only used in practice for drawing the word 'CANCEL'

in the item menu, and to aid with removing items from the list.

The redundant list size property is used for everything else, including acting as the bound

to check against for the cursor in the menu.

So in this state, the cursor can continue to be brought down past the intended limit

for the item list.

All of these glitch items are various other game variables being interpretted as items,

and they can be manipulated in any way that items in the bag can be manipulated, such

as swapping them around and tossing them.

As you can see, you have to be very careful when using redundant data like this to control

how a data structure works, especially in a situation where you aren't going to have

any kind of error checking.

You have to be sure that every action taken on the structure updates all metadata properly

so that everything is in sync at all times.

This isn't to say that things can't go wrong when you don't create metadata shortcuts,

but that maintaining these properties can lead to errors that just can't exist without

them.

This is even more of the case when different metadata are used for different kinds of tasks.

Like in this example, where the terminator is used to reduce the size of the list, but

the redundant size property is used to expand it.

This leads to cases where items can be added without an issue, but can't be removed without

messing things up.

Let's look at another redundant data pattern that can cause a lot of issues when values

get desynched.

Again let's start super simple.

Suppose you have two data structures--whatever they may be--and they need to be linked in

some way.

Maybe this is a parent-child relationship where this object belongs to the other, or

maybe these are two similar objects that need to be paired off for some reason.

The simplest way of creating this link would be to store a pointer to one of the objects

inside the data structure of the other.

That is, the memory address that denotes where this object's data is stored in memory is

itself stored inside the data of the second object's data.

With this information, you can follow the pointer to access the data of the other object

if you are working with it first.

Now, if these objects belonged to a larger super-structure where you had access to them,

this one-way link would be sufficient for denoting this relationship.

If you were working with this object instead, you can't just follow the pointer backwards.

You would have to go to the super-structure and work your way to the first object, then

compare the value of its linking pointer and see if it matches the object in question's

memory address.

Sure, this would be pretty inefficient, especially if there were many other objects that could

also possibly relate to this one, but it wouldn't be impossible to figure out.

Therefore, in order to streamline this process, it is very common to actually include the

converse pointer from the second object back to the first.

This way you can hop back and forth from one object to the other without any complications.

When you do this though, one of these pointers becomes redundant, just like with the length

of the list in the previous example.

Now in order to modify this relationship, two pointers have to be updated instead of

just one, and they have to be done carefully at the same time.

For example, to change this relationship from between objects B and D here to B and C; first,

the pointer from B to D should be updated to go from B to C.

Then, the pointer from C needs to be created to point from C back to B.

And finally, the pointers from D to B and A to C need to be removed completely.

What used to be one or two operations is now three or four operations instead.

If any of these operations are done incorrectly, you can end up with a one-way relationship

where one object doesn't know about the other, a double relationship where two objects know

about the same object, or a disjoint relationship where the true link between objects is completely

mixed up.

There's an infamous glitch in Super Mario 64 that is a byproduct of this sort of error.

It's not quite as straight-forward as the super simple example we just saw, but it boils

down to the same principle.

First lets look at how objects are handled in the game's code.

A pointer to each currently loaded object can be found in a doubly linked list.

This includes enemies, certain platforms, items, effects, and even Mario himself.

When objects load in, they get added to this list--either appended to the end or inserted

in the middle depending on the order the objects should be processed.

And the opposite when objects unload, they get removed from the list.

However, there's a bit more going on during these two actions.

These structs that actually make up the list, object nodes as they are called, are always

present, even if the object corresponding to that node is not loaded.

And even these unloaded objects are still present in memory, just not being used anymore.

These nodes are marked as being available for newly loading objects--their data will

replace the existing data of the old object.

When an object is loaded, one of the available nodes is given the new object's data, and

it is inserted into the list where it belongs.

And when an object unloads, the node is marked as available for a new object, and it is moved

to the end of the list of currently loaded objects.

This means there is always a dividing line between objects that are currently loaded

and objects that no longer exist in the stage.

But it is important to know that the underlying data of the object is still there, since it

never actually gets deleted until a new object loads into that node.

The next thing to look at is how the game deals with Mario holding certain objects,

like boxes and Bob-ombs.

When an object is grabbed, it doesn't actually stick to Mario's hands.

Instead, it is just hidden from view and from interacting with anything in the stage.

And separately, Mario's model is updated to show the object in question, but this is just

a graphical change.

It's only when the object is thrown or dropped that the real object is unhidden and warps

to Mario's position.

So why exactly does it work this way?

Mario and the object he's holding have a relation just as discussed earlier.

While Mario keeps track of what object he is holding, each object keeps track of whether

it is being held separately.

Now in practice, there is a global struct responsible for identifying which object Mario

is currently holding.

But we can represent this more abstractly as an arrow pointing from the Mario object

to the held object.

And also in practice, objects only have a few states that signify if they are being

held or not.

But since there is only one possible option for what can be holding them--Mario--we can

represent this more abstractly as an arrow pointing from the held object to Mario.

This two-way relationship is what we are interested in.

Normally, when Mario grabs and object, this two-way link is created together, and when

the object is thrown, the two relations are removed together.

However, there are ways to have only one of these relations created or removed, resulting

in an inconsistant game state where Mario is holding an item that doesn't know it's

being held or where an item behaves as if it is being held when it isn't.

Let's look at the first case.

It turns out that the two parts of this relationship aren't created simultaneously when an object

is grabbed.

First, Mario grabs the object and the first relation is created.

But it's not for a few more frames that the converse relation is created--it takes a little

bit for the object to realize it has been grabbed.

This slight discrepency isn't really that much of an issue normally, but if the object

unloads during this small window, the relationship will break.

Mario still behaves as if he grabbed the object, but the object doesn't exist in the world

any more because it unloaded.

Now remember, that when and object unloads, its data isn't actually erased right away,

but only when another object loads into the same memory location.

For example, suppose Mario grabs this box right when it unloads.

It may look like he successfully grabbed the box, but the box has actually unloaded, and

this is just an old, dormant version of it.

The moment another object loads into that memory location, Mario will be holding it

instead.

Now, you'll notice that the coin here that loaded in is still present over here.

This is why this glitch is refered to as cloning, since it looks like there are two copies of

the object--it's a bit of a misnomer though because there is really only one copy of the

object, just being rendered in two places at once.

When the coin loaded in, it was never notified that Mario is holding it.

So it behaves as it would normally, justing sitting in the stage.

It's only until the object is thrown that it updates accordingly.

The other glitch to talk about will be about breaking the link in the opposite direction.

When Mario uses a teleport in a stage, he will be forced to not hold an object.

Now normally, the teleport won't even work if Mario is holding something, but there is

another glitch that let's Mario hold an object while being in an animation state other than

those that correspond with holding an object.

This is refered to as holding the object hands-free, since it's no longer attached to Mario's hands.

In this animation state however, the teleport will work, even if Mario is holding the object

hands-free.

After the teleport, the relation from Mario to the object in question will be removed,

but not the reverse relation.", This results in the object just being hidden

forever, since it still behaves as if it were being held, even though Mario isn't holding

anything anymore.

In this example, the box will never reappear even though it normally comes back after some

time.

This is because the box is programmed to never disappear if it is being held.

And if the box thinks it's being held always now, it will never unload and never respawn.

By the way, Mario can still establish new relations with other grabbable objects just

fine.

In fact, by grabbing another object, it can be said that two objects are being held by

Mario at one time.

I said that objects become completely hidden when they are grabbed, but there is one exception,

and that is the Bob-omb.

The reason for this is so that the smoke that comes out of the top of the Bob-omb renders

next to the one that is in Mario's hands, since it is the actual Bob-omb object, and

not the rendered copy in Mario's hands that can make smoke.

What this means is that if you try this hands-free teleport glitch with a Bob-omb, when you reload

the Bob-omb by revisiting the teleport you entered, it will start smoking as if Mario

were holding it.

And if you grab another object when you do this, Mario will be holding that object and

the Bob-omb's smoke will still show up.

He quickly drops it though because the two objects are colliding with each other.

And because of the Bob-omb's exception, it is the only object that can be regrabbed out

of this state, since it isn't completely hidden like any other object.

In order to figure out everything you saw here, I referenced a Pokemon Red disassembly

and Super Mario 64 decompilation which you can find links to in the description.

Also, thank you to JoshDuMan and Pannenkoek for their help and documentation regarding

Super Mario 64--that game is a beast to delve into.

And of course, thank you for watching!