Deconstructing Pokémon glitches?

问题:

(I apologize if this is the wrong place to ask this. I think it's definitely programming related, though if this belongs on some other site please let me know)

I grew up playing Pokémon Red and Blue, games that were great fun but are somewhat notorious for having numerous exploitable glitches (for example, see this ridiculous speedrun of the game that uses memory corruption to turn the item screen into a hex editor).

Recently, I found an interesting speedrun of the game that uses a glitch called the "ZZAZZ glitch" to corrupt important memory locations and allow the player to almost immediately win the game. According to the author's description of the speedrun, the ZZAZZ glitch works as follows:

To start a Trainer battle, the game needs to load a lot of data, such as [...] the money he'll concede if defeated. When it loads the money is where things can get really ugly. For reasons that are beyond me, money is stored in a completely different manner, the game uses a data structure of three bytes and instead of converting the value to binary, it stores it in "human" representation. For example, $123456 would be stored as 0x123456 instead of 0x01E240, the proper conversion.

[Some invalid entries in the Trainer table] point to location with invalid money data. When the game tries to perform arithmetic with these data in said structure, it goes nuts and starts overwriting huge portions of RAM. More specifically, for every block of three bytes, two of them will contain 0x9999 (the maximum amount of money a trainer could give). This pattern repeats itself many times through RAM. To see this better, I recommend pausing the video on the emulator after the ZZAZZ trainer is faced and set VBA's memory viewer to 0xD070.

This analysis makes sense, but as I programmer I can't help but wonder how on earth the programmers wrote the code that would make this possible. No approach I can think of for writing a function that converts a hexadecimal-encoded decimal number to decimal would ever start filling random blocks of memory with 0x9999 if the input wasn't a valid hexadecimal-encoded decimal number.

My question is - without specifically designing the algorithm to fail this way, is there a straightforward implementation of a conversion from hexadecimal-coded decimal to decimal that could result in this sort of memory corruption when fed in an invalid value?

Again, if this is off-topic, my apologies. My thoughts are that other programmers on this site may have also grown up playing this game, and it sounds like an interesting exercise in reverse-engineering to try to figure out how a glitch like this could be possible.

回答1:

Honestly, my guess is that this is just a stupid, nasty glitch by someone writing one of their first games on target. Pokemon Red/Blue were the first of the series and had so many other glitches that Nintendo would normally kick out of lot-testing, that I wonder how it got through. The scroll screen shift issue is the one that gets me. Anyways, who knows what they were thinking. Perhaps this area was written to via script and therefore stored things differently. Perhaps the bit pattern 0x0101 was used to show memory was freed and that code accidentally goes bonkers in weird places. I could pour over the Z80 code and relive my own game development time on that platform, but meh. Too much work to try and decrypt what the blazes they were thinking.

It sure made a ton of money though...

Edit 1:

Ok, you bountied it. I spent a bit more time pouring over my memory and found a tidbit for you. The GBC/DMG has an opcode called DAA. Decimal Adjust Accumulator (A). What this does is convert a value in the accumulator into BCD format. The areas in memory you are seeing are already in BCD format: http://en.wikipedia.org/wiki/Binary-coded_decimal

Now I can tell you, in the 4 years or so when I was hand coding Z80 assembler for games, I never once had a need for this opcode, and only seen it used once in a baseball game we made for displaying some scores. While it is a 1 cycle arithmetic instruction, I could never really find a good use for it in normal coding. Hmm. I actually still have the DMG tech docs from Nintendo. Go figure ;) Anyways, nothing exciting there about it either except that it messes with a number of flags in funky ways.

My guess is that table is assumed to be in BCD format. Changing it to something outside of that format causes the internal math to go extremely haywire - Carry and Zero flags set when they aren't supposed to be. This causes overflow from one column to the next, causing very large numbers to be calculated. Without looking directly at the opcodes in question that read this area, I can't say for certain, but my guess is there is a catch all check here that says if carry is still set upon completion of the BCD math, set a max value instead of storing a negative or out of bounds value. That or the DAA instruction, when receiving garbage data is returning 0x99 for it return value, though I'm less sure about that.

Hope this helps...

回答2:

I can think of an algorithm (although I feel sorry for whoever might have written it):

• Assume the input is a 32-bit decimal digit in hex notation, little endian (e.g. 0x56 0x34 0x12 0x00).

• Now loop through every byte, while you haven't reached a zero byte. (This should never happen, if 0x999999 is indeed guaranteed to be the max... but alas, it's not.)

• On every loop, calculate the actual value and write the data back into the integer (or into some other buffer, where you do a "loop-while" rather than something like "for i = 0 to 4").

You can see how you can get a glitch, if your value doesn't have 0x00 at the end (i.e. the 32-bit "decimal" integer is larger than 0x999999).

Of course, this is a rather obscure way of calculating the value, but I think it's quite possible that someone did a while/do-while loop rather than a bounded for loop for this.

Edit 1:

At first I thought this would have the "advantage" of allowing the string to be shown directly to the user (since it would be null-terminated), but of course that doesn't work with little endian. They could've done something similar with big endian, but that would require a backwards loop to overflow, which I find to be a less likely mistake for someone to make.

Edit 2:

Perhaps it was a compiler optimization due to undefined behavior (which the programmer was unaware of, like an invalid pointer cast or an aliasing issue)?

回答3:

Mystery solved! It looks like user TheZZAZZGlitch figured out what causes this.

The glitch is triggered when the game tries to compute an extremely large integer. Internally, the game has a routine that repeatedly adds values to simulate a multiplication. It seems to write bytes as it goes, shifting over an output write position. The code is designed to cut off any value that exceeds 0x009999 so that the player doesn't earn more than $9999 from a trainer battle (the values are stored in hexadecimally-coded decimal). However, the game forgets to reset the output pointer when this occurs, so if an extremely large number is generated, the game will repeatedly write the pattern 0x009999 across RAM by shifting the write pointer over and writing 0x99 to two out of every three bytes.

Hope this helps!