I know I haven’t posted anything since months and in the mean time, my post on the flipping mechanics in Super Paper Mario just got a lot of views due to large interest on reddit, thank you on that btw 🙂

But considering what I am writing on right now, trust me, it was worth the wait.

One of the most fascinating glitches I could ever learn about are those that are in theory so undefined that you have to wonder how in the world the game wouldn’t crash and even worse, could even be with practical researches defined enough to have the glitch work in your favor through some clever manipulation of it.  This is why I still think the most fascinating glitch I learned about is the missingno glitch which I talk more about in this post .  The key part that I find it fascinating is how small the error is, but how elaborated it can become once you know about it.

The force 20 glitch from a game called Gotcha Force is a really great candidate for this description.  In fact, to get why, I think it’s better to just show it.  Here is a video made by the Dolphin emulator channel on YouTube showing an accurate emulation of the glitch and a crash that comes from it:

The first time JMC47 (the main Dolphin tester) showed this to me as a suggestion for me to research on it, I instantly knew: this is going to be awesome to research!

How research for such complex glitches is done

When I explained about how glitch hunting works, this applies to most glitches you would find and this one was probably found by luck (because I mean it’s not this hard to do it accidentally).  For researching them, it’s usually not a problem especially if you have access to a relatively accurate emulator and a ram search program (here, Cheat Engine).

But I think this should already be obvious in the video: this is just not enough.  I mean if you are aware of the memory, their positions and their data representation, how can you explain the fact that you COULD pick something that should have been empty and how can you explain the fact that putting the Borgs (the toys are called Borgs) in these particular slots for some reasons causes undefined behaviour?

The only thing a ramsearch will allow you to get is the effect in memory, not the source of the problem which is the interaction with the memory.  Not even manually hacking values within the ramsearch is enough, you would really need to dive into the execution of the game because it is that complex.

Enter a tool that you only see in these complex researches, the debugger.  A debugger for those who are unfamiliar with programming is basically a program that can be attached to the program you want to debug and control its execution.  For example, in software development, using a debugger is very useful to spot problems like seeing the execution flow is wrong, a crash occurs at a given line or you have doubts on the sanity of the variables, it really allows a lot of control of the execution of whatever you are programming.

Since we can’t have the game source code here, we have no choice but to debug in the language that we have now which is actually PowerPC assembly, aka, the most low-level language you can get before machine code.  It means it’s very complex to research and you basically have to know what you are doing because first, you need to know the language and second, it’s so primitive, you need hours to analyse something that could have been written with 10 lines in 30 minutes on a modern programming language like C++.  And I don’t even mention how this being the output of a compiler is just making it even harder to understand at times because of the optimizations.

luckily, dolphin does have an integrated debugger that……I actually worked on the past 2 months to try to make it NOT broken because 2 months ago, it wasn’t just unstable it was actually lacking very crucial features that either didn’t work or they do, but they cause crashes.  So because of this, I could research this.

After 7 hours in a row of streaming my research on my Twitch channel, I finally figured everything out and to better start to understand, I first need to explain the context.

Context of this game

It’s a very obscure game in North America, but apparently it was popular in Japan.  The basic idea of the game is you have these toys called Borgs which you use them in battles.  The game tbh is mostly good for its multiplayer features because the story mode…..ehhh is kinda lacking in my opinion.

But the main idea that’s very important here is the force mechanic.  You need to create groups of Borgs called “force” that you can choose from before a battle.  The force edit menu provides the options to do this and it is in that mode that I mainly will talk about.

gg4e08-5
A typical view of the force edit mode

The grid you see is called the box area, 200 slots where each of them can contain a Borg.  You use these slots to put them in the force on the right (the yellow hexagons slots).  The game allows to have maximum 20 forces each forces can be made up of 30 Borgs.

Here’s the part that can be confusing if you don’t know about it, you can put the same Borg from the same box slot in multiple forces, but you cannot put the same Borg from the same slots multiple time in the force.  If you want multiple of the same Borg, you need multiple of them in the box.  To indicate that the Borg is already used in the current force (they update when you change the current force), a little number pads showing the slot number the Borg was put in appears in its slot.

And that’s pretty much all you need to know about the game.  Of course the individual Borgs has different stats, but you don’t really need to know how it works to understand the glitch.  You do however need to know some technicalities about the data of this game which I am about to explain now.

The memory organisation

Each slots in the box contains not only the ID of the Borgs, but also several other things such as levels, a flag set when it is new, etc….  Because of this, each slots takes 32 bytes in memory.  The only attributes I am going to talk about from the slot is the first 2 bytes tells the ID of the Borg, literally a number that tells which Borg it is.  The other one is a 4 bytes array located at halfway (so 16th byte) of the slots.  This array basically tells within its bits of all the 20 forces that exists, which one this Borg is currently in.  I am not going to detail how binary works with this but essentially, imagine you have 20 binairy numbers in a row so they can be either 0 or 1.  When you put a Borg in a force, the corresponding bit will be set to 1 and if you remove it, it sets to 0.  You need more than 16 bits so you need at least 3 bytes, but this game uses 4 (it’s easier to use multiple of 2 so…).  The rest of the slots aren’t really needed to understand the glitch as far as the box slots are concerned.

But what about the force slots?  These are very different, each of them are not 32, but rather 2 bytes.  The only thing they have is the index of the slot number from the box area.

If you didn’t get what I just said, you need to understand how static arrays works, it’s quite simple, but fundamental in this glitch.

How arrays of data are done with computers.

Let’s say you wanted to store 10 numbers and you already know you need 10 numbers.  You could say to allocate memory for each of them, but considering they could be scattered all over the place in the actual ram….this might not be a good idea especially if you want to keep some orders within them (like sorting them for examples).  The solution is to allocate all the numbers at once in a contiguous array.  So in the ram, literally, all your numbers will be in a row.

But since we have made the assumption they are contiguous, this means you don’t even need to know the addresses of ALL 10 numbers, you actually just need the first one and then guess where are the others.

How it works?  it’s pretty simple really, here’s a very toned down way to know it: you pick the number of the data you want in the array (say we want the sixth), you multiply it by the size of each of the array slots (let’s assume it’s 4 bytes here) and you add that to the address of the first slot.  The only trick is you start to count at 0 (this is because of how 0 is a possible number so why not take it?) so the sixth slot will actually be 5 * 4 + the first slot address.  So you start to see that if you just want the first one, it’s going to be the first one + 0, which is what you want.

That number you use to multiply with the size, this is called the index.  It is a way with a single number to identify where is the slot you want.  This number will become a very fundamental concept later so as long as you get the idea, you are fine.

But just as a reminder, the force slots contains only that index of the box slot it references.  So if 0 is in there, it means this particular slot references the first slot in the box.  This is how the game knows which slots are put in which Borgs at any given time.

Sounds solid, so what’s wrong?

Well I said 0 would be in the force slot when it references the first slot.  For the box slots, 0 is actually the first Borg ID.  So some people might be wondering:

What about an empty slot?

Yeah about that…..since 0 is taken well the best choice would be the last number you can represent with 2 bytes which is in hex 0xFFFF or 65535 in decimal……if you omit the sign because there’s 2 types pf integers: unsigned and signed.  The former is quite simple, the range is from 0 to whatever is the number of possibilities minus 1 (so 65535).  The later however, it allows to have negative numbers at the expense of half of the max ranges.  You still have the same amount of possibilities, but you can’t represent large numbers.  Due to the way of how they are encoded, you kinda have to read 0xFFFF backward, you are 1 away from 0 so it’s -1.  If you have trouble to understand, just understand that this number is taken as signed so it’s -1 in theory.

Ok, now this is obviously unbreakable, you just make sure it’s not -1 right?

Yes you are correct…..

As long as you indeed check that because there’s one place the game where it omits that and it serves as the foundation of the glitch.

The actual source of the glitch (it gets worse from now on)

So if you try to pick up something to move it, the game needs to do some sanity checks and it clearly does the check to make sure what you are trying to pick up isn’t in the current force, it just won’t let you have it.  The reality however is it forgets to checks if what you are trying to pick up is empty so only the force flags check is done.

What NORMALLY happens is when you are trying to pick something, it gets the selected box index, times that by 32 (the size of a slot) and add this to the first slot address and magic, you now have the address of the concerned slot’s force array flags and you can perform your sanity checks there.

But for an empty slots, since they forgot to do the -1 check, everything goes wrong.  It takes the index of the selected slot……which is empty so it takes -1, times that by 32 so it gives -32 and add that to the address of the first slot…….wait the freak?

Yes, it will actually go backward and go 32 bytes before the address of the first box slot’s force flags and worse, it will read the 4 bytes in there and thinks it’s the force flags of the selected slot!

This phenomenon is more commonly refered as a buffer underflow, you essentially go out of the boundaries of the buffer of data you should have been writing by going before (under) the actual buffer.  There’s the buffer overflow which is the same, but it goes too far from the buffer.

When you have this in a game, this can be dangerous, it can read invalid data causing an unhandled exception which results in a crash or in very worse case scenario, it won’t crash, but it will do something clearly wrong.

Fortunately, it does the latter for our interests because what happens to be 32 bytes before the first slot force flags is……

The slots 23 and 24 of the 20th force

Yes, the forces array is right next to the box array, because of this coincidence, it checks a bit from these 2 slots thinking it is the force flags of the slot you are trying to pick up.

If these 2 are empty, it’s all 0xFF which btw, in binary, all bits are set to 1 so what this means is it literally thinks that the slot is in every force which as silly as it sounds, it accidentally allows this bug to stay dormant as long as these 2 slots are untouched!

More precisely, because it only happens with the force 20, it will only compare a specific bit from these 2 slots.  Without going into why it happens to be that one, the math at the end says that the bit being checked is the 4th one of the second byte which is basically the second byte of the slot 23 in force 20.  So in practice, slot 24 doesn;t matter, all its bits could be 0, it doesn’t matter, the only bit that matter is the 4th one of slot 23 which is the one that worth 8 in decimal btw.  Since you CAN put something in that slot…….why not?

Consequences of messing up the location of the bit to check

As I said earlier, the forces slots only contains the index of the concerned box slots in 2 bytes.  The first byte isn’t normally used because you need an array of more than 255 slots for this but we are dealing with a 200 slots array.  So to simplify ourselves, let’s just imagine it was a byte for a moment.

I said the 4th bit is worth 8 in decimal.  So you basically need any index number that you don’t need the number 8 to express when you convert to binary form.

Again, I will spare you the math, but what I am telling is not all slots index with give the same results.  Index 0 to 7 will succeed the bit check and allow to pickup empty, but index 8 to 15 will fail the check because they have that bit on.  And this patterns recycle with 16 where it will succeed the checks and etc…

So if you systematically pick a working index from a box slot, place the Borg there, then place it in the slot 23 of force 20, this will make the game vulnerable because it will now allow you to pickup slots who have empty contents!

Wait empty contents?  it;s -1 in this game so….

oh oh…

It gets worse when you pickup 0xFFFF aka -1

So as if this wouldn’t get any worse, this is where the killer effects is.  Since this game defined that everything empty is 0xFFFF or -1, it is considered to be the “slot index” you are trying to pick.  And the thing is the game needs to know the location of the slot you are picking up because it needs to prepare for possible copy of data when you are going to move it somewhere else and swap the contents of the slots.  So, same thing as earlier, normally, it takes the index of the slot you are picking up, times that by 32, add that to this time the address of the first box slot.  The only difference is it’s the first byte of the slot, earlier, it was the force flags array which was 16 byte later than the first byte of the slot.

Now for some reasons, they AGAIN forgot to check if the slot you are picking up is -1 so yes, if the game allowed you prior to pick it up, you WILL pick it up.

But where does it position itself for copy?

It’s 16 bytes before the slots 23 of force 20 which is the slot 15 of force 20, but the last death sentence for the game is that it prepares to copy a box slots…..which is 32 bytes and 32 bytes starting from slot 15 of force 20 is basically from that point to the end of the force array so slot 30 of force 20…..

I am literally saying you are copying the last half of the force data!!!

And due to what I explained, if you pick up an empty slot (so the last half of the force 20 data) and place it on an existing slot that has other data…..

Fireworks! YAY!!!

gg4e08-6
The stability of this game is remarkable

Because it will (assuming you don;t crash) do a swap.  It will put the box slot data you chose into the last half of the force and the last half of the force data into the box slot you chose…..which in some conditions will do a crash because…….seriously, do you really expect the game to handle this?

But in some cases, it actually can 🙂

Going further, what this allows

Well since it is copying from the last half of force 20, you can manipulate its data by doing the same thing earlier, you just systematically choose which box index to place and where to place it, as long as it’s between slot 15 and 30 of force 20, it will have an influence.

Since the first 2 bytes is the Borg ID, it allows to decide a Borg by having its id stored in the slot 15 and then using that as a box slot copy.

You can even move the box data you copied within the force.  Which explains why a kinda weird procedure has been found in practice to obtain different Borgs, remember the force flags array?  You would take a given slot, systematically put it in some forces, do the force 20 glitch, but you copy from that box slot to the force.  So the force now has somewhere this flags array, you can put that in slot 15, pick up empty and then paste it on the same slot as earlier which will make the game interprets the Borg ID what should have been a flag array.

And the best part about it?  Since the box has 200 slots, each of them being 32 bytes, it gives a grand total of 6.25kB of data to mess with.  I don’t think I need to tell you how crazy insane this thing allows and all of this caused by a -1 that wasn’t checked.

Limitations associated with crashes

You can crash while doing this and even though I haven’t checked all the details of the reason of the crash, I so far found 3 rules of thumb to respect to avoid any crashes:

  1. Do not PLACE -1 to any slots that isn’t empty.  There are special cases where the game will empty the slot, but you can’t have it happen with this method or you crash.  This is why it’s safer to have a non empty slot 15 since it will be a sane number.
  2. Do not put invalid Borg ID in any slots of the box, you will crash otherwise.
  3. Do not make any slots of the force to reference indexes whose content is empty, but you can go over the boundary of the box array.

As for why you seemed to need proper MMU emulation as the Dolphin video says, it’s because these crashes are caused by invalid addresses reads that makes no sense so having this option makes Dolphin knows these are invalid.

Lesson to take from this glitch

That you really need to be sure the data you are about to handle is safe, even within the definition of your own system.  Doing such checks is actually just a simple if block in a modern programming language and from what I understand, 2 PowerPC instructions (one for the comparison, one for the conditional branch).  This is only coincidence that this glitch allows very fascinating effects, but as you saw, it’s picky with crashes.  Getting into undefined behaviour is always dangerous.

My experience of researching it

I can’t help, but be fascinated by when the undefined becomes possible to define.  With this explanation figured out, it can even allow more because now it’s known what is the cause and what could be possibly done.  To me, it’s very fascinating to learn about these glitches, but now that I got the experience of researching them, I want to do more, nothing can describe how happy I felt for these 7 hours of streaming.  The main points I love about it is the intensity that you have to think to eventually get it and when you get it, the “OMG I GOT IT!” moment is the best possible feeling I can ask for.

Now with a more stable debugger, I am hopping I would research these kind of glitches more, they are fascinating, but very pleasant to research on.

Little thanks to JMC47 for telling me about this glitch, I will remember it for sure, it’s quite high in my list of most fascinating glitches 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s