51

I am trying to explain segmentation faults to someone, and I was thinking about the level 256 kill-screen in Pacman, and how it's triggered by integer overflow, and how similar the behavior is to the "unknown state" oft-described in a segmentation fault.

I want to say this is a good example of what I call an "unhandled segfault", but I would rather get a second opinion before I potentially spread misinformation.

I tried looking it up, but all I'm getting are documents on the bug itself, as well as that collab between Hipster Whale and Namco.

So, would you consider the behavior in level 256 of Pacman to be an example of unhandled segmentation violation?

Improve this question
5
  • 3
    Here's an exact description of the bug, together with a patch to fix it: donhodges.com/how_high_can_you_get2.htm
    – abligh
    Jan 25, 2016 at 16:16
  • 26
    Segmentation faults are raised by the hardware, to avoid illegal memory access. I'm no expert on Pacman, but the hardware it ran on almost certainly didn't have this safety feature to begin with.
    – BlueRaja - Danny Pflughoeft
    Jan 25, 2016 at 19:30
  • 3
    According to wikipedia Pacman used a Z80. Z80s definitely did not have memory protection.
    – Gort the Robot
    Jan 25, 2016 at 21:04
  • It's not a segfault—the system did not have any form of memory protection. The fault Pac-Man experiences at level 256 is simply an integer overflow that is not correctly handled by the game's code.
    – bwDraco
    Jan 26, 2016 at 0:45
  • 3
    FYI, I dont think this qualifies as a bug. A bug is failure or fault in a computer program or system that causes it to produce an incorrect or unexpected result, or to behave in unintended ways. It was intentionally programmed that way, since it was felt that no one would get to that level. In reality, its just poor software design.
    – Keltari
    Jan 26, 2016 at 17:44

5 Answers 5

Reset to default
113

Definitely not.

Accessing a memory address you didn't allocate is always a programming error. And acting on the information you get out of it produces undefined behavior, that much is accurate. I have no idea what platform the original Pac-man was written for, but I'm pretty sure it exhibited this behavior just like any other von Neumann machine.

However, "segmentation fault" is a technical term for a much more specific condition. It happens when the computer automatically detects that this happened and terminates the process rather than allow undefined behavior to occur. This requires a specific (segmented) memory model with sophisticated ownership tagging. I don't think 1980 arcade games had that, and in fact the behavior of the game suggests that the error was not detected, and the undefined behavior did occur.

Improve this answer
18
  • 19
    @B1KMusic: You're really asking "is this code 'bug' an example of invoking undefined behaviour through out-of-bounds memory access", and the answer is "yes". Any rationalisations about catching, ignoring, not getting a SIGSEGV signal is just confusing matters.
    – Lightness Races in Orbit
    Jan 25, 2016 at 11:29
  • 5
    @B1KMusic not all buffer overruns result in a segfault. It depends on how the memory was allocated. If the memory is statically allocated (one big buffer manually split up in different zones) and the area immediately behind the last level was used for something (like sprite graphics) then it wouldn't segfault.
    – ratchet freak
    Jan 25, 2016 at 11:36
  • 6
    Those old arcade systems used primitive OSes that gave the game pretty much full control over the hardware, similar to early versions of DOS. The idea of a segfault in that type of architecture is a non-starter, because it assumes the one running process (Pac-Man) does not own all of the memory. For more information, one can read up on the MAME project and its history.
    – user22815
    Jan 25, 2016 at 15:03
  • 20
    Undefined behavior is not a property of von Neumann machines, it is a property of C, the programming language. Programs written in assembly language cannot exhibit undefined behavior, because the behavior of assembly language instructions is always well-defined (even if the results are sometimes unspecified).
    – Dietrich Epp
    Jan 25, 2016 at 18:29
  • 8
    @Snowman there is no such layer on a Pac-Man machine. There's no loader — the game is in execute-in-place ROM. There's no memory management — everything is static. There's no "services"; the game accesses hardware directly and there isn't a byte of code on the system that isn't part of the game and written for the game.
    – hobbs
    Jan 26, 2016 at 0:41
38

It looks like you're confusing "undefined behaviour" and "segmentation fault".

There is no such thing as an unhandled segfault. A segmentation fault is error handling, by definition.

If you don't have an OS that detected the bad memory access and terminated the process for safety, then you don't have a segmentation fault.

If anything, then, this is a pretty good example of how UB doesn't always result in a segfault.

Improve this answer
12
  • 2
    To be precise the OS may decide to kill (i.e. irrecoverably) the process. Modern OSs instead prefer to terminate it, which may be caught and handled, FWIW.
    – edmz
    Jan 25, 2016 at 19:14
  • @black: Isn't that what I said?
    – Lightness Races in Orbit
    Jan 25, 2016 at 20:46
  • 15
    It may not even be "undefined behavior". If Pacman was written in pure assembly, then the code did exactly what it was told to do in an utterly defined way. Not undefined behavior, but merely a bug. As such, the code would run the exact same way running on any system that had a perfect port of the underlying chipset.
    – Gort the Robot
    Jan 25, 2016 at 21:15
  • @StevenBurnap: That is true.
    – Lightness Races in Orbit
    Jan 25, 2016 at 21:23
  • @black What is the difference between 'kill' and 'terminate'? Other than the fact that 'kill' is normally UNIX vocabulary, and 'terminate' is more Windows-y?
    – Brandin
    Jan 26, 2016 at 9:44
24

Neither of these terms is appropriate for a bug in an arcade game that was programmed in assembly language and runs without benefit of memory-protection hardware or operating system.

"Undefined behaviour" is a term-of-art in C and related languages, coined by the C standards committee back in 1989. Code has undefined behavior when the language specification doesn't define what it will do. There is no such thing in Z80 assembly language: the effect of every opcode with every possible input is well-defined. The conventional English meaning of "undefined behavior" can be read to apply -- the kill screen is behavior not defined by the people who wrote the game -- but I wouldn't use it in this context because it's too likely to give the wrong impression.

"Segmentation fault" is a term-of-art in POSIX, derived ultimately from PDP system programming jargon. Segmentation faults happen when a program attempts to access a memory address that isn't "mapped" to anything: the hardware and operating system detect this and shut down the malfunctioning program, in a carefully-defined way that allows the program a chance to recover. Something like this could have happened as a result of a bug in the Pac-Man game program, because the Pac-Man circuit board only populates a little less than half of the Z80's 64kB address space with ROM, RAM, and peripherals, but I haven't been able to find out what the real hardware would do if the software attempted to access unmapped memory. Whatever it would do, though, it would be inappropriate to describe as a "segmentation fault", because the "operating system" for Pac-Man (to the extent it even has one) is not an implementation of Unix and, again, it would give the wrong impression.

The level 256 bug, meanwhile, does not access unmapped memory, so it's moot.

It is accurate to say that the game has a bug which manifests upon advancing to level 256. It is also accurate to say that the root cause of the bug is an integer overflow, and that its consequences are memory corruption (or, equivalently, violations of memory and type safety). These are all general-purpose CS terms defined without reference to any particular language or OS environment.

It's also accurate to observe that the effects of the bug are similar to the effects, within a modern environment, of memory-corruption bugs that don't provoke segmentation faults. If you read any of the Project Zero exploit writeups, you will see a remarkable similarity to Don Hodges' analysis of the Pac-Man kill screen.

Note that an emulator that doesn't faithfully reproduce the kill screen when fed the Pac-Man ROMs is not emulating the game hardware correctly.

Improve this answer
3
  • The phrase, "undefined behavior" may not have been used in print in that exact way before 1989, but the idea that that phrase describes is as old as programming itself. Common Lisp: The Language (Digital Press, 1984; ISBN 0-932376-41-X) used the words "it is an error" to mean exactly the same thing. E.g., "It is an error to call this function with x<0" meant that the programmer should not allow the function to be called with x<0 and, that the implementation was allowed to do literally anything the implementer wanted it to do if the application programmer did not comply.
    – Solomon Slow
    Jan 25, 2016 at 18:54
  • 5
    @jameslarge I understand what you mean, but I still think it is a mistake to apply this concept to Pac-Man. We can say that the kill screen is a bug because the game is clearly not behaving as the designer intended. We can't say that the game has provoked undefined behavior, because there's no language specification to say "under no circumstances may the programmer do X" for any value of X. (I suppose use of the Z80 undocumented opcodes might qualify, except that plenty of arcade games did use those and AFAIK they all have predictable effects.)
    – zwol
    Jan 25, 2016 at 19:11
  • 1
    This is the best answer. "Undefined behavior" means that the coder wrote code for which the result cannot be foretold based on the standard. If Pacman is written in Z80 assembly (and I believe it was) then the code written had an entirely defined meaning regardless of whether the program did something the coder didn't intend.
    – Gort the Robot
    Jan 25, 2016 at 21:18
8

The level-256 bug in Pac Man results in the program reading data which is beyond the end of the intended table, but is still readable storage, and writing to portions of the screen which are beyond those which the program intends to write, but are still well within the areas of the screen that the program is allowed to write. No other areas of memory are affected.

The reason that the bug renders the game unplayable is that the machine determines when a player is eating dots by examining what's on the screen, and decides that a level is complete when the player has eaten 244 dots. By overwriting part of the screen, the bug makes it impossible for the player to eat 244 dots; consequently, the game will never credit the player with completing the level and reload the screen with dots.

Improve this answer
8
  • 1
    When you kill yourself in level 256, the dots respawn, but you don't lose any.
    – ave
    Jan 26, 2016 at 8:56
  • @ardaozkal: The level-draw routine erases more than 100 dots and draws a few. If a player had enough lives, it would eventually be possible to eat enough dots to advance a level, but that would require more than 30 lives.
    – supercat
    Jan 26, 2016 at 16:49
  • I remember watching a video where the player had enough lives, and he managed it... and I just found it.
    – ave
    Jan 26, 2016 at 17:19
  • @ardaozkal: How many lives are required to clear the level, and how many lives can a player get on an unmodified machine?
    – supercat
    Jan 26, 2016 at 17:26
  • You can't even get to level 256 on an unmodified machine.
    – ave
    Jan 26, 2016 at 17:35
1

As said before no it's not a seg fault. I'll add why the problem occurs: it's an overflow.

Level number are store on a byte so the range is 0-255. Each time you complete a level the counter is incremented. At level 256 the counter is in fact 0 due to the overflow.

However the game try to display some fruits on the bottom of the level. The fruit number/type depend on the level. The formula display one fruit per finished level under level 8. According to the counter you are on level 0 so under 8. The test is true then and you have to print 255 fruits (the old level value). Which is impossible and gives this glitched screen.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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