22

(This question also applies to other Game Boy games, but Pokémon seems to be one of the best-documented.)

Pokémon Red & Blue (Red & Green in Japan) is a pair of Game Boy games about capturing "Pocket Monsters", or "Pokémon", by fighting them with other Pokémon. Since its release lots of bugs and glitches have been found[1], many of which are caused by overflow errors.

The Game Boy contained a Sharp LR35902 CPU, a Z80 derivative that was a little bit of a combination between the Z80 and 8080:

This processor is similar to an Intel 8080 in that none of the registers introduced in the Z80 are present. However, some of the Z80's instruction set enhancements over the stock 8080, particularly bit manipulation, are present. Still other instructions are unique to this particular flavor of Z80 CPU.[2]

Both the Intel 8080[3] and, by extension, the 8080-compatible Zilog Z80[4] have a carry bit that is set on operations that overflow. A derivative of these chips would also have these; indeed this is not documented as a difference between the Z80 and the LR35902[5].

To the part that is confusing me: the LR35902 CPU had an overflow flag, and there are many exploitable glitches in Pokémon Red that are caused by overflows; there are glitches caused by overflows in most places that overflows can occur. There must be a reason that the developers didn't use this flag on so many occasions, but I can't work out what it is.

Why are there so many overflow bugs in Pokémon Red?

  • 5
    At least in the US games, you have to do some pretty non-obvious work in order to trigger these bugs, so they likely wouldn't be found by manual testing (or maybe even automatic testing). – Batman Oct 30 '16 at 18:26
  • 1
    @Batman Well, the "wet" 255 item glitch doesn't require you to do too much (buy a drink, chuck the drink, give the drink away, chuck everything else, modify lots and lots of memory values). – wizzwizz4 Oct 30 '16 at 18:31
  • 10
    Just a thought - I would consider the popularity of Pokemon Red and Blue to be a significant factor to the number of their known bugs. Another way of saying this is that perhaps the number of bugs in the Pokemon games is not that different from an average Game Boy game, but there are more people who are actively looking for them, and more people who are interested in exploiting them. – tehDorf Nov 2 '16 at 23:52
  • 4
    BTW pokemon was not an early game boy game. It was a relatively late and big game (some gameboy carts are only 32K, Pokemon R/B/Y was a megabyte) – Peter Green Sep 9 '17 at 12:37
  • 4
    It was Game Freak's first project. They just were sloppy programmers. This function merely divides by four, in the usual Game Freak style of doing things. – NieDzejkob Jun 6 '18 at 16:35
18

I cannot speak about Pokémon in particular, but as a programmer for ~30 years, I'll answer thus: either laziness, incorrect assumption, or surprise.

  • Laziness
    After an operation that overflows, you need to write extra code to check for the overflow, and then decide what to do about it. That's extra time, and extra work.

  • Incorrect assumption
    (Often characterised by "That'll never happen!") Have you ever visited a website, or used a program, and an error box popped up with something like "User won't see this"? That's because the programmer may have considered the overflow case, but decided it wouldn't happen so didn't code for it (other than put in a debug statement that they forgot to remove). Needless to say...

  • Surprise
    For example, just say at a point early on in the game you can do something that trebles your points. Because it's early, the programmer doesn't even consider checking for overflow because the current score isn't that high yet. But if a high-scoring player works their way back to that point and triggers it then, then it might overflow the score. The player surprised the programmer.

There are a couple of other, lesser reasons: maybe they ran out of code room on the ROM and had to strip out error handling code; or maybe they wanted those Easter Eggs to be found; but it's almost always one of the top three.

  • 1
    So... nothing specific to the Game Boy? Huh. I assumed there would be. – wizzwizz4 Oct 29 '16 at 14:08
  • 3
    "This will never happen" (and variants thereof) feel to me like the worst possible assumption to make in programming. Either it can happen, and if so it might be worth checking for; or it can't happen, and there's no point in checking for it (if it happens anyway, depending on capabilities, either crash hard or muddle through). – a CVn Sep 9 '17 at 16:59
  • 1
    @MichaelKjörling And yet people do it all the time. The most egregious example in my experience was a web portal where there was a theoretical chance that two people could be served the same session id due to it consisting of two application servers. The developer calculated the chance of a clashing id and came up with the answer of billions to one, forgetting the "birthday paradox" effect and that hundreds of people were using the system every day and this made a clash virtually inevitable. The consequence was one user seeing the confidential data of another user. – JeremyP Sep 13 '17 at 9:53
  • @aCVn: Many programs are subject to the constraints: (1) given valid data, produce correct (and thus valid) results; (2) given maliciously-constructed data, don't do anything harmful, but behave arbitrarily otherwise. Ensuring fully-predictable behavior when given invalid inputs requires a lot of validation code, but merely ensuring harmless behavior generally requires much less. Problems primarily arise when there's confusion about which parts of the code are responsible for the small amount of validation that is necessary. – supercat Apr 11 at 15:34
  • Obligatory xkcd: xkcd.com/2200 – John Burger Sep 10 at 0:15
18

Overflow doesn't mean what you think. That flag exposes the internal ALU carry from bit 6 -> bit 7. It's needed when you are handling the most significant byte of a 2-complement number, because you can't use the carry for that purpose here: it's jumbled by the MSB sign bit.

When you don't add or subtract 2-complement numbers (MSB isn't meant as sign bit but just another bit), it has no meaning. It's not set on increment or decrement instructions when they wrap around 255->0 or 0->255 either.

  • I thought it exposed the internal ALU carry from bit 7 -> /dev/null. I'd say that this is the answer I'm looking for. – wizzwizz4 Oct 30 '16 at 16:49
  • 3
    @wizzwizz4: No, that one is the regular carry flag. Programmers could had (and should had ) checked that on the 8080 already. However, that's the general sloppyness John Burger mentioned. Meh, I just use INR and that's it. – Janka Oct 30 '16 at 16:53
  • 1
    @wizzwizz4: (and future readers) see Understanding Carry vs. Overflow conditions/flags for signed vs. unsigned. Most CPUs that have a CF and an OF set them this way. But there's a terminology gap here: "overflow" can also mean "exceeding the range of the type". For IEEE float, the overflow behaviour is saturation to +/-Infinity. For integers on normal CPUs, the overflow behaviour is wraparound (which you can detect with OF for signed wraparound or CF for unsigned wraparound). – Peter Cordes Dec 15 '17 at 4:45
  • Some CPUs have a saturating integer add, which is useful for audio/video for example. (multiply the brightness -> saturate to white instead of wrapping to black). Saturation is another kind of overflow behaviour. So it is correct to talk about unsigned overflow in a computer science sense. Anyway, detecting integer overflow efficiently is basically an unsolved problem in computing. Most languages don't provide checks, and in asm putting a conditional branch after most instructions would be horrible for perf and code-size (plus you need error-handling code as a branch target). – Peter Cordes Dec 15 '17 at 4:49
  • I'm still not sure that's an accurate description of overflow; -128 + -128 has no carry from bit 6 to bit 7 but generates overflow. The test for addition is: initial signs are the same, final sign is different. r = a + b; overflow = ~(a ^ b) & (a ^ r) & 0x80; – Tommy Apr 11 at 18:20
10

I think your premise is wrong.

Firstly "overflow" in most cases doesn't mean pure arithmetic overflow, it means overflow of some other limit, checking said limits would require more than a single extra instruction.

Secondly in many of the glitches involving overflow the overflow is a secondary part of the glitch.

  • Using a rare candy on a level 255 pokemon results in a level 0 pokemon, but the player isn't supposed to have a level 255 pokemon in the first place.
  • Encountering a "glitch pokemon" corrupts the hall of fame due to an overflow in the sprite decompresser but the player shouldn't be encountering glitch pokemon in the first place.
  • In psywave the pokemons level is multiplied by 1.5, this can only overflow if the pokemon is over level 100 which again should never happen.

As to the broader question of why pokemon Red/Blue has so many "interesting" glitches (rather than boring crash bugs) I think it's a combination of the large size of the game (a whole megabyte in size) with the limitations of 8 bit platforms.

The very limited total ram (8K video ram, 8K work ram, 4x8K cart ram, less than 1K high ram) along with the fact that it's generally faster to use hard-coded memory locations on 8-bit platforms means that the same hard-coded memory location will be used for different things in different contexts. If you can set a memory location in one context and then cause it to be read in another context you can end up with memory locations set to predictable values that were outside the ranges the developers believed they could have.

Combine that with a large non-linear game written on a platform where resources were precious (so you wouldn't initialise something or check something unless you thought it needed doing) and there are lots of opportunities for unexpected combinations.

  • 1
    BTW, I read of an interesting "virus" someone came up with for one of those games. When connecting to another cart it will effectively install a patch to the other cart in the ROM, which will hide a Pokemon under a truck that was rumored to have the Pokemon under it (but never did). The author pondered what would have happened if such a virus had been written back in the day when Nintendo was denying rumors of the hidden Pokemon. – supercat Sep 17 '17 at 0:59
  • I find that claim hard to believe. – Peter Green Sep 17 '17 at 1:18
  • 1
    I don't have the youtube link handy, but someone posted a description of the mechanisms used. IIRC, a substantial portion of the battery-backed storage in the cart isn't used by the game, and it's possible to corrupt some of the game data in such a way as to cause execution to transfer to the otherwise-unused space. If the video was a joke, the author went through an awful lot of trouble to concoct consistent technical explanations for how things tied together. – supercat Sep 17 '17 at 3:11
  • 1
    Writing to the rom is not possible, so the question then becomes can you find an exploit that lets you hook your code in at the right time to trigger the effect you want without having to effectively rewrite the game (which there is nowhere near enough space for). – Peter Green Mar 25 '18 at 1:58
  • 3
3

Electronic Gaming Monthly no. 124 from 1999 notes that the original Japanese Pokemon games had a long, difficult development process. The source code was so bad that when it came to doing the western versions the original Pokemon Red game was recreated using the newer Pokemon Green code, but even that was not an easy task.

When you have poor quality source code, cartridge size limitations, and a long development process which towards the end will inevitably focus on getting the game released rather than finding and fixing rare bugs, you end up with software like Pokemon Red and Blue. Brittle and full of obscure bugs.

Also note that both games were written in assembler, not a higher level language like C. At the time C compilers for embedded systems were not as advanced as they are now, and didn't support the Z80 all that well anyway, and tended to produce large and slow code. Most Gameboy games were written in assembler as a result, and prone to errors such as these.

  • 1
    This is an interesting point. I hadn't thought of that. – wizzwizz4 Apr 11 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.