The kill-screen in the
original arcade version of Pac-Man is a classic example of a side effect
due to unintended integer overflow. If you manage to reach level 256,
the entire right side of the screen turns into a garbled mess and
it is impossible to clear the stage. You would think something as static
as the level layout wouldn’t be dependent on what level you are
on, so let’s find out exactly why this happens. <font color="#FFFF00">♪ [intro jingle] ♪ </font><font color="#FFFFFF"></font> Pac-Man is a relatively simple game,
and each level is pretty much the same apart
from more difficult enemy movement. The only thing on the screen
that changes depending on what level you are on
is the level counter in the bottom right, represented by these fruits. If you’re not familiar
with how the fruits represent the level, here’s
a short explanation. The first level is a cherry;
the second is a strawberry; the third and fourth are peaches;
the fifth and sixth are apples, the seventh and eighth are melons,
the ninth and tenth are Galaxian flagships,
the eleventh and twelfth are bells, and the thirteenth
and onward are all keys. The game only shows
the current level’s icon and the past six levels for a total of seven icons
shown at once. This means that once
you get to level 19, you will just see seven keys
for the rest of the game. Internally,
the game stores these icons in a table that is 20 elements long. It includes each of the fruits, one per level,
and then the final key eight times. In order to draw the corresponding
level icons on the screen, a range from one to seven of
these elements are chosen to be drawn one
after the other. The algorithm that determines
this range is split into three different cases. In Case A,
the level number is less than 8. This corresponds to the fact that the range may include
fewer than seven fruits. The start of this range is always
the cherry, and the end of the range
is determined by the level number. If we aren’t on level
7, then extra spaces are erased--the number of blank spaces is just 7
minus the level number. In Case B, the level is greater than
7, but less than 19. This corresponds to the fact
that there are exactly seven icons to draw,
but which ones depends on the level. The end of the range
is still determined by the level number,
but the start of the range is now also determined by the level number,
just 6 fewer. And finally in Case C,
the level number is greater than 18. This means that all of the icons
will always be keys. The range in this case is fixed
to always go from element 13 to 19, which is the last set of keys. There is actually one more key
at the end of the table that is never used, which suggests
that possibly eight icons were shown at a time
instead of just seven. If we iterate through
all the levels from 1 to 20, you can see how smoothly
the level counter represents the current level
in a nice, intuitive manner. So, what causes level 256
to confuse the level counter and destroy the map? 256 is greater than 18 after all, so you would expect it to follow Case
C and display seven keys. The tiny bit of information
that you need to know to understand what goes wrong is that the level
number is represented as a zero-based index
instead of a one-based index. This means that level 1
is represented as 0, level 2 is represented as 1
and so on. The algorithm
for drawing the level counter adds one to this value
to get the actual level number. This number is treated as an 8-bit
byte, which means the values
it can hold range from 0 to 255. A zero is represented
by setting all eight bits to zero, and when all the bits are set to one,
it represents 255. If you try to add 1 to 255,
all of the bits flip and roll over back to zero,
since 256 would be represented as a one in the ninth bit,
which doesn’t exist here. So this effectively means
that level 256 is actually treated as level number 0
for all intents and purposes. What does this mean for the level
counter display function? Well 0 is less than 8, so Case A will be executed
instead of Case C like we wanted. So the range of fruits to draw
will start at 1, the cherry, and end at 0, the... hmm. What does it mean to end at an index
that is less than the starting point? Let’s look at another example. If we were on level 3,
the range of fruits to draw would be from 1 to 3. The process is: draw fruit #1, add one to get 2, draw
fruit #2, add one to get 3, then draw fruit #3. This fruit is the last one
in the range, so we stop there. If we extend this process to the case
where the end of the range is 0, it would seem like it would never end
and we would just be drawing fruits forever. But, just like the level number
itself, the temporary value that holds the index of the fruit
to draw is also an 8-bit value. Which means it also has the property
that when you add one to 255, it overflows back to zero. So the process would be:
draw fruit #1, add one to get 2, draw fruit #2, add one to get 3,
and so on. Then eventually, draw fruit #254, add one to get 255, draw fruit #255, add one to get zero, and draw
fruit #0. At this point
the fruit we just drew matches the end of the range,
so we stop there. This means that on level
0, 256 fruit are drawn in total. Which is kind of a problem,
because if you remember, the table containing
the fruits is only 20 elements long. Now let’s
get into the more technical stuff. The table that holds the level
icon data is stored at ¤3B08 in memory,
and each of the 20 entries is two bytes long; one determines the icon’s
graphics and the other its palette. For example, the cherry’s graphics start at tile #¤90,
and it uses palette #¤14. Normally, this table is indexed
from entry 0 to 19. If you try to read entry #20, you get data that doesn’t
have to do with the fruits at all; in fact is mostly music
and sound effect data. Whatever data gets read will be
treated as a graphics tile number that is most likely not going
to correspond to that of a fruit. This is how the kill screen gets
its glitchy-tile aesthetic. As for how these glitchy tiles
get strewn all of the right side of the screen, we have to take a look
at the tilemap. The tilemap for the entire screen
is stored in memory at address ¤4000. 1024 bytes
correspond to each tiles’ number, and then 1024 more bytes
for each tiles’ color. The way that the bytes map to
the screen is a little odd, in that the first group of bytes
control the bottom margin of the screen
from right to left, row by row. The majority of the rest control
the main map in the center of the screen
from top to bottom, column by column. And finally the last group controls
the top margin where the scores are shown. Each fruit takes up four tiles, and normally
they are drawn on the bottom margin. The intended space for the level
counter is from address ¤4004 to ¤4011 for the top row and ¤4024 to ¤4031 for the bottom. The top right corner
of the first fruit sits at ¤4004, the second at ¤4006, then ¤4008 and so on; just add two
to get the position of the next one. Let’s see what happens when we try
to draw our all 256 of our fruit. The cherry is first drawn at ¤4004. The other three tiles of each fruit
are found by adding 1 to the address to get the top left tile,
then adding ¤20 or ¤21 to get the bottom right
or bottom left quarters. Then, the strawberry, two peaches, two apples,
and a melon are drawn next in line. So far so good--if we stopped here, this is exactly what level
7 would look like. But we still have 249 fruit to draw,
so let’s keep going. The other melon, the two Galaxians,
the two bells, and one key are drawn with no issues,
other than that they have escaped the intended bounds
for the level counter. The next key is drawn
with no problems as well, but since this part of the tilemap isn’t drawn to the screen,
you can’t actually see it. The third key is the first icon
that starts going wrong. Its top right
corner should be located at ¤4020, which means its other three
tiles are stored at ¤4021, ¤4040, and ¤4041. But once we hit ¤4040, tiles begin being drawn
on the top of the actual map. Since the map main is stored
in columns instead of rows, the bottom two tiles of this key
end up above one another at the top
right of the screen. As we continue to draw the other five
keys, more of the main
map becomes obscured. The top half of the keys
are still being drawn on the bottom of the screen, overwriting the bottom
half of the already drawn fruit. Then finally we hit the 21st
entry in the table, and begin to draw garbage
tiles onto the screen. The rest of the bottom row of the screen is overwritten,
as well as the right side of the map. The 31st icon is drawn at ¤4040, ¤4041, ¤4060, and ¤4061. Now the entire icon
is on the main map. The rest of the glitched tiles are
drawn down the right side of the map, making their way
towards the middle of the screen. Since each icon overwrites
half of one of the previous ones, after the drawing is complete,
every pair of tiles corresponds to one of these fake icons. These aren’t just false graphics either--since
the tilemap is also responsible for how Pac-Man and the ghosts
interact with the map physically. Most of the tiles that aren’t
supposed to show up on the map are free to move over,
but some of them act like walls. Eventually, all 256 fruit are drawn, and the entire right
half of the screen is scrambled. If you
remember, the last step of Case A was to draw blank tiles
if we weren’t on level 7 yet. Well since the game thinks we are on
level 0, it draws 7 minus 0 equals
7 blank spaces after the fruits. This completes the malfunctioning of them algorithm,
and the damage has been done. Afterwards,
the number of remaining lives is drawn on the bottom
left of the screen, which hides
most of the level counter down there. It is because of this
that the resulting screen doesn’t make it plainly obvious what is going
on--the remaining part of the level counter on the bottom is disguised
within the glitchy mess. The level begins, and now you are
stuck on level 256 forever. You can only move onto the next level
when Pac-Man eats 244 pellets, but most of them
have been destroyed by the garbage. There are a few pellets
mixed up in the glitchy mess if you can find them,
and they even respawn after you die. Unfortunately with a maximum of five
extra lives, this limits the number of pellets
you can eat to 168. Interestingly,
this means the entire game is finite, and the maximum score
possible is 3,333,360 points. It takes even the most skilled players over 3
and a half hours to pull this off. The current world record
as of when this video was made is 3:28:49 by Dave Race.
