Why does Ms. Pac-man turn upside down?

Ms. Pac-man is a game where you navigate a small yellow circle around a maze, collecting dots and fruit whilst avoiding brightly-coloured monsters, or ghosts. This time, however, the yellow dot has an eye, a red bow, some lipstick and a "beauty spot". Apart from a few minor visual glitches, there was nothing really wrong with the game; at least until you got to level 130 or so. Then this happened:

Surely this can't be a simple overflow glitch; it must have taken organised sabotage to produce such an error.

Why, out of all things that could happen, would this occur?

The reason for this glitch is rather obscure; it's not surprising that the developers didn't catch it. It all starts with the tunnels on the sides of the screen. These tunnels allow Ms. Pac-man and the ghosts to move from one side of the screen to the other. But, somewhere in development, somebody decided that the ghosts were moving too quickly through them. Their solution? Create "slow tiles" on the tunnel spaces.

In this image, squares with black borders represent the "slow tiles". These had the otherwise unused bit 6 of their bytes on the colour grid set, causing the ghosts to slow down slightly whilst moving going over them. This itself didn't cause the glitch; the main fault was elsewhere.

To store the "slow tiles", the game uses a very sophisticated compression algorithm; it stores the distance to the next "slow tile" as a single byte value, where a `00` byte marks the end of the table. Although there are three layouts in the game, the first two have tunnels in the same places and so can use the same "slow tile" table. The algorithm the game uses to paint the "slow tiles" is as follows:

1. `LD A,(#4E13)`: Load the current level number into `A`.
2. `CP #03`: Is `A < 3`?
3. `JP P,#2534`: If not, jump elsewhere (return).
4. `LD HL,#95DF`: Load the "show tiles" table address.
5. `CALL #94BD`: Loads a pointer to either the first or second table into `BC` depending on level type.
6. `LD HL,#4400`: Loads the start of colour memory into `HL`.
7. `LD A,(BC)`: Set `A` to the memory value pointed to by `BC`.
8. `INC BC`: Increment `BC`.
9. `AND A`: Is `A == 0x00`?
10. `JP Z,#2534`: If so, jump elsewhere (return).
11. `RST #10`: Increment `HL` by `A` and set `A` to the memory value pointed to by `HL + A`.
12. `SET 6,(HL)`: Set bit 6 of the memory value pointed to by `HL` - paint the "slow tile".
13. `JR #95D4`: Jump back to instruction 7.

If you are observant you may have noticed some "slow tiles" along the outside of the top maze border. These are there because the maximum distance between two "slow tiles" is `0xFF`, or 255, due to the way that their positions are compressed in memory. In order to reach from the right-hand side to the left-hand side of the screen, the pointer needs to span some `0x0300` memory values. This number is clearly larger than `0xFF`, so the developers bridged this gap in a series of `0xA0`-sized jumps along the outside of the maze, where the "slow tiles" would not affect the ghosts.

There is, however, a flaw in this algorithm. In the third instruction, the developers checked the "Positive" bit (`JP P,#2534`) instead of the "Carry" bit (`JP NC,#2534`) (note that it would have to check if the carry bit was not set). This means that the value of `A` is treated as a signed integer during the comparison, and so values `128` and above are treated as if they are negative. Negative numbers are, indeed, less than three.

As a result of this, an invalid, or "garbage", pointer is loaded into the register in instruction 5. This in turn causes the following loop to process something that is not a table. For example: on level 134, this is the "table" read:

``````7F 7F 7F 7F 7F 7F 7F 7F C9 C9 C9 C9 C9 C9 C9 C9
C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9
C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9
C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9
C9 C9 C9 C9 C9 C9 C9 C9 00 00 00 00 00 00 00 00
``````

As you might have guessed, this causes the pointer to go significantly past the colour memory, overwriting the sixth bit of every 201st memory value as it goes. Notably it writes to memory value `5D2B`, which causes the majority of the screen to flip upside down.

Eventually, enough arbitrary memory values are written to to cause the game to reset. It is possible to fix this programming error, but that uncovers a whole other set of errors and it is not in the scope of this answer to explain those. For that, you will have to ask another question.

I have made up the term "slow tiles" for this answer; I do not know what these are actually called. A lot of information was sourced from donhodges.com.

• A bit causing the game to flip may seem strange but many arcade games have this feature to support cocktail cabinets where the two players would sit at opposite sides of a small table with the screen between them. When player 2's turn came the display would be rendered "upside down" so they wouldn't have to play it upside down. In this case the memory stomp hit a bit to draw the playfield upside side down but didn't hit anything to draw the sprites upside down. Commented Nov 2, 2016 at 22:28
• @GeorgePhillips I thought that was the reason! Do you know where the bit to flip the sprites is? Commented Nov 3, 2016 at 7:08
• BTW, the "sophisticated compression algorithm" is a variant of Run-length Encoding. Commented Nov 3, 2016 at 7:52
• For cocktail mode the software handles the flipping of the sprites by "inverting" their Y position and individually mirroring them horizontally and vertically. This is only done when player 2 is active and \$4e72 is 1 indicating a cocktail cabinet. \$4e72 is a RAM variable initialized from a DIP switch setting. So unlike bit 0 of \$5d2b (an alias of the official \$5003 address) which controls hardware, a memory stomp of \$4e72 would never affect the first player. Commented Nov 3, 2016 at 18:38