Culture / Development

Rust Developer Explores the Lessons Learned from a Famous Pokemon Glitch

13 Sep 2020 6:00am, by

Sian Griffin at Rust Conf 2020 (glad we don't have to hand roll assembly)

As August came to a close, the annual Rust developers conference went virtual, featuring not only online presentations but also digital breakout sessions and meetups.

But there was a special closing keynote from Siân Griffin, who co-leads the team managing Rust’s crates.io package repository. (The conference site’s speaker profile describes Griffin as “the person who gets woken up at 3 a.m. if the service goes down.”) Griffin also created the Rust query-building/object-relational-mapping tool Diesel, and co-hosts a podcast for developers called “The Yak Shave.” For the virtual conference attendees, Griffin brought an instructive tale about glitches from the history of computer programming.

And it came straight from the world of Pokemon.

“Oh, hi. I didn’t see you there,” Griffin began casually while dressed in a yellow Pikachu costume — adding, “I want to tell you a story.”

A World Before Rust

Griffin began by looking back at the late 1990s, when “‘Just use Rust’ wasn’t an option.” The story was about a Nintendo 64 Pokemon game — and the assembly programmers who’d coded it. Griffin tells the audience that the international releases of Pokemon Red and Pokemon Blue in 1998 became two of the best-selling videogames of all time. But a slide of the most famous Pokemon ever — Pikachu – was followed by a slide of the second-most famous: the Glitch Pokemon, which could only be encountered because of a unique combination of errors by the games’ programmers.

Griffin later calls it “one of the most famous glitches of all time.”

The talk focused on what we can learn about programming from this famous glitch. “As with most major glitches, there’s no single bug that’s responsible here. This happens because of a bunch of different bugs. And in most cases, you can’t even really call them bugs, just properties of the code being used in unexpected ways.”

Though the talk contains some speculation, Griffin also “spent a lot of time” looking at “disassemblies” of the game’s original code, “and I think we can infer a lot about what was intended from reading the code and knowing about the constraints that they worked under.”

Throughout the presentation, Griffin demonstrates how the code worked by showing a translation of the code to Rust. Griffin calls the first bug “the easiest to scoff at” today for Rust programmers — but then explains why you’d code differently if you were writing in assembly language in the late 1990s. “In assembly, you don’t just have however many local variables you want,” they said.

In fact, the Z80 assembly used by the GameBoy only had four general-purpose registers for global variables — all of which were in use.

“When you write a program in Rust, the compiler’s going to determine where to store every variable that you write. It’s either going to assign it to a register, a sort of global variable that your CPU uses, or it’s going to put it on the stack. Now in the Pokemon games they did have a stack, but it was really tiny — only 207 bytes. So they basically never used it unless it was absolutely necessary. The main place it was used was for audio playback,” Griffin said.

This meant the game included lines of code where some variables were just reinitialized later — and in one oversight there were two lines that both acted on the same variable — 50 lines apart. “That alone, to me, makes it much more reasonable that this would’ve just slipped through code review,” they noted.

The second bug just fails to clear the value for a variable, leaving it with data from earlier in the game. But that could be exploited by making sure it got data with an unexpected value — for example, the control character that signaled the end of the name for a non-playable character who could train your Pokemon for you.

“Every single one of us has worked on a project where two days before the deadline, the requirements change out from underneath you.”– Siân Griffin.

But even better, one in-game tutorial would trigger the storing of a player’s name in that same location. This meant savvy players could set the value of that variable to whatever they wanted — by choosing their desired value as the name of their character, and then performing that in-game tutorial.

Since it was ultimately a player’s own user name that determined what kinds of Glitch Pokemon would appear, any name with an even number of letters meant the crucial end-of-name character would eventually appear in the Pokemon column — and trigger the appearance of Glitch Pokemon. So would the uppercase letters S, H, or M — and most lowercase vowels. Some Glitch Pokemon would only show up if you had a lowercase w, x, or y in your username.

But this glitch brought other unintended consequences. The code includes an array tracking the Pokemon seen throughout the game — with values for whether or not the player has captured them. But when players see a Glitch Pokemon, the code tries to record it in a position that’s far beyond the end of the array — specifically, in the data for the player’s inventory of items. (And more specifically, in the high-bit portion of 13th byte indicating the quantity of that inventory’s sixth item.) “It adds 128 of that item — as long as you had less than 128 before,” Griffin explained. Players began joyfully exploiting the glitch to magically produce a glorious bounty of their favorite Pokemon items.

Sian Griffin at Rust Conf 2020 (on glitches in Pokemon Blue)

But out-of-bound errors affected the game in other ways too. The sprite showing the appearance of the Glitch Pokemon ends up taking more space than the game’s other sprites, and it ultimately overwrote the data for the game-ending “Hall of Fame.” Griffin noted that everything in the game had to be optimized to save space, so there was no bound-checking code. It was written on the assumption it would always be receiving “trusted input,” and “The only reason this code misbehaved was because of a completely unrelated bug that caused it to get garbage data.”

Griffin paused to explain where the image of the Glitch was coming from. While somewhere in the program there’s a handy lookup table for each Pokemon’s image, the code accessing it had its own bug. Griffin showed the line of code where to get a position in an array, one was subtracted from a number which indicated its position in an index. But for never-defined values, this meant subtracting one from… zero. And since this involved unsigned eight-bit integers, the end result was a value that was one less than 256 — so, 255. This sent the program on a wild search for the picture of the glitch, far beyond the end of the array of available pictures. What it found instead was some data for the non-playable trainer characters, which was interpreted as a pointer, leading it off to code for yet another area — the Safari Zone.

And then it attempts to interpret that code as an image.

Pokemon Post-Mortems

The talk concludes with a thoughtful analysis on the real lessons we can learn from the great Pokemon glitch.

The talk was titled “Learning Empathy from Pokemon Blue,” and Griffin reminded the audience that the code was painstakingly created in assembly, “under massive space constraints. Every instruction mattered.” But more important is the law of unintended consequences. “Now that we’ve seen every piece of this glitch, we can see that it was just a bunch of small, seemingly benign interactions between unrelated bits of code. No individual piece of this glitch stands out to me as insane or something that obviously would’ve been stopped in code review.” It’s not the result of bad coding or lack of QA, they emphasized. “Every piece of this glitch by itself was relatively benign.”

And yet something powerful still happens when you put them all together. “When you combine all this together, you get one of the most famous glitches of all time.”

While some people have described the game as “completely broken,” Griffin argues that’s a phrase that should be removed from everyone’s vocabulary. “In this case and many others where you would try to use that terminology, it’s more likely the software is developed under some constraints that you weren’t aware of, and you wouldn’t do better in the same circumstances. Sure, these days there are less likely to be technological constraints, but every single one of us has worked on a project where two days before the deadline, the requirements change out from underneath you. Or your company suddenly pivots, and now you do medical services, and you have to figure out how to make a bunch of code relevant for that.”

“To me, though, a lot of this glitch just boiled down to, ‘Because assembly.’ It’s really easy for us to take the technologies we have at our disposal today for granted.” Today code size is rarely a constraint, and when it is it’s usually just because of CPU caches, “and it’s a thing we find while optimizing our code.” Plus our modern-day machines have the power to run “all sorts of safety checks.”

“But in 1996, ‘Just use Rust’ wasn’t an option. And even using C wasn’t an option.

“I’m really glad that we don’t live in that world anymore.”

Screenshot from RustConf dot com


WebReduce

A newsletter digest of the week’s most important stories & analyses.