Rosio Pavoris

Why Black Sunday happened

Sword-and-Martini GuyI’m refering, of course, to the event in KoL in August 2004, not to the various other, and rather more serious, Black Sundays there have been.
What happened was that some players found a bug that allowed them to get less than 0 meat, which somehow gave them close to the maximum amount they could possibly have. (Actually, Black Sunday was a culmination of a number of different bugs, but this meat bug was perhaps the most significant, and certainly the most well-known.)
To understand why this happened, we must first know how numbers are stored on a computer; in particular, integers.

As you undoubtedly know, computers only work with binary (base 2) numbers. Decimal (base 10) numbers from input are converted to binary for storage and use, and are (usually) converted back to decimal before they’re displayed.
This happens for various reasons, not the least of which are that it’s easier to store something in binary (given that each bit is either on or off, rather than any of ten possible states), and it’s easier to do calculations with them because of the way transistors and Boolean logic work.

This works quite well for natural numbers (non-negative integers), but what about negative numbers? How do you represent them?
What you could do is reserve a bit to indicate the sign of the number. Knowing that computers work with units of a fixed number of bits (units of eight bits are called a byte, units of 16 a word, units of 32 a double-word, &c.—actually, it depends on the processor architecture; confusingly, “word” is also used to describe whatever the amount of bits you’re working with at the time is, so you could say you’re counting with numbers using a word length of 8 bits), you could always just use the first bit for that.
For example, if you’re working with bytes, you could use 0000 0001 for 1, and 1000 0001 for -1. (I’m grouping the bits in fours for ease of reading. This is usually done because it’s easy to convert to hexadecimal notation, since one character in hexadecimal notation represents the numbers 0 through 15, and so do four bits; the hexadecimal way of writing 0110 1101, for example, would be 6D.)

This is somewhat difficult to count with, though. The processor would need to know what word lengths it’s dealing with, and if it’s dealing with signed or unsigned integers (because presumably, if you didn’t need negative numbers, it would make sense not to have that first bit just be useless).
Consider this, though: if you have a binary number 1111 1111, and you add 0000 0001, what do you get? 1 0000 0000, you say, but a number can’t be longer than the fixed length, so it would be cropped to 0000 0000 (and the overflow flag would be set, but that’s not important). So does it make sense to say that 1111 1111 is actually equal to -1?

Yes, it turns out. It’s easy to count with, because the processor doesn’t have to know anything, just perform the actions. It has the benefit of the other system, in that the first bit still indicates the sign of the number, but it has the added benefit that that bit is never going to waste, even if you’re dealing with unsigned integers. The CPU doesn’t have to keep track of whether it’s dealing with negative numbers or not, the software does it for it, when it converts back to decimal.

But you can see what caused the problem with KoL now. The amount of meat a player had was stored as an unsigned integer, so when a player had 0 meat and lost 1, he went from 0000 0000 to 1111 1111, or 255 meat!
Or would have if it had been stored as tinyint, which has a word length of 8 bits. Instead, it was stored as bigint, which has a word length of 64 bits! So when a player went to -1 meat, he actually had 264 - 1, or 18,446,744,073,709,551,615 meat! (That’s 18 trillion in long (European) scale, or 18 quintillion in short (American) scale. See here.)

Whether or not this is a bug in MySQL is open to debate. Some say the value should’ve remained at 0, and certainly that’s the behavior Jick expected. Others say that the behavior was to be expected, and should have been predictable to anyone who understands how computers work with numbers, and I’m inclined to agree.
Either way.

Consider yourself educated. I’ve only dealt with whole numbers, because floating point numbers are a different (and more complicated) matter entirely. Possibly I’ll do a post about those eventually, if anyone cares.

1 Comment

  1. echomikeromeo said,

    That was actually interesting. But only because it had to do with KoL. Would that all comp sci could be explained like that.

Post a Comment

RSS feed for comments on this post · TrackBack URL