There is nothing like finding an arguably fun example to support any of the arid concepts populating the fields of digital electronics, computing and signal processing. Some time ago, I came across a fantastic video published by the IEEE Spectrum Magazine (Five Infamous Arcade-Game Glitches), devoted to programming mistakes (i.e. glitches) in arcade videogames: Asteroids (Atari), Donkey Kong (Nintendo), Sinistar (Williams Electronics), Ms. Pacman (Midway) and Centipede (Atari) .
Sinistar’s glitch got my attention, and it seemed handy to explain two’s complement arithmetic, which is essential in the digital systems domain. In this game, it was possible to go from having 1 life to enjoy 255 lives. And all due to a programming absent-mindedness and to the behavior of binary arithmetic. By the way, let me clarify that what goes next is quite simple, but fun.
First I will briefly explain some concepts about binary. If you think that this is too basic you can go straight to the heart of the issue clicking here.
Binary code
First we have to see what the binary code is and my elaboration will be focused on using binary to represent numbers. The binary system is a base-2 positional numeral system. A base-B positional numeral system represents numbers with digits that can have values from 0 to B-1 (from 0 to 1 for binary; from 0 to 9 for decimal, etc.), and they are written one after the other. A digit is in a position i which in turn determines its weight. Assuming that the digit located to the right of the number has position 0 and that the digit located to the left of the number has position N-1 (because there are N digits), the weight of each digit is B^i. Given that an N-digit number with values b_i (b_i\in [0\ldots B-1] and i\in [0\ldots N-1]), its value can be computed as:
value = \sum_{i=0}^{N-1} b_i\cdot 2^i = b_{N-1}2^{N-1}+b_{N-2}2^{N-2}+\ldots +b_{1}2^{1}+b_{0}2^{0}.
For instance, the binary number 10011_2 has a decimal value of 1\cdot2^4+0\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0=16+2+1=19_{10}. Binary might seem strange to us for start, while we feel quite confortable with decimal numbers. It would be ridiculous to apply the previous summation to evaluate number 21 represented with base 10: 21_{10}=2\cdot10^1+1\cdot2^0=20+1=21. The reason for that is that we spent our holw life using base 10, thus decimal number look “natural” to us. Binary would natural instead if we were to count in binary since our childhood and decimal would look artificial. OK, I will no extend on this, but Mayans had a vigesimal number system where digits went from 0 to 19, and I think that they used base 20 numbers with no problems at all. Having said that, it is not chance that we use base 10, since we have 10 fingers in our hands and we use them to count (a word digit means both finger and the figure/numeral that conforms numbers).
Adding through substracting
We are going to talk a little bit (:)) about how to substract, since in videogames, it is common to reduce the number of lives of a player when it gets hit. In particular, we focus on how to substract by adding number. If we imagine that we only have 3 decimal digits to represent numbers (the range would be from 000_{10} up to 999_{10}), a way to substract one unit would be to add the number 999. For instance, if number (005) is added 999 the result is 1004, that if represented with 3 digits leads to number 1004, that is, 4. Summarizing, adding the biggest possible number, given the available number of digits, to a number is equivalent to subtract one unit. In binary, we can also apply this idea. If we use 8 bits, the representable number go from 0 to 2^8-1=255 and subtracting one unit is equivalent to adding number 255. If we add 255_{10}=11111111_2 to number 5_{10}=00000101_2 the result is number 100000100_2 and removing the ninth digit (the one most to the left) leads to number 00000100_2=4_{10}. This happens to be part of the so-called modular arithmetic, but I have to leave some stuff out of the post 🙂 .
It’s funny, but everything I had just described can be explained by means of two’s complement (2C) arithmetic – I leave out the general concept of the complement to the base, and I focus on base-2 complement (2C) to keep the post reasonably short. In 2C’s representation, the most significant bit (the one most to the left) is the sign bit. Positive numbers would have this bit to zero and negative numbers to one. The value of the number can be obtained like this: valor = -b_{N-1}\cdot 2^{N-1} + {\sum_{i=0}^{N-2} b_i\cdot 2^i} = -b_{N-1}2^{N-1}+b_{N-2}2^{N-2}+\ldots +b_{1}2^{1}+b_{0}2^{0}.
So, number 3 would be represented with 8 bits as 00000011 and number -3 as 11111101. Do the maths to check that it fits. An interesting property of 2C numbers is that we can add them no matter their sign: the results will be positive of negative directly, and it will be correct (given that the result can be represented with the available bits). As aforementioned, I have to limit the scope of this post, but you can easily check that if we add 3 and -3 in 2C the result is zero (00000011+11111101 = 100000000, dicarding the ninth bit). Thus, substracting one unit to a number is the same as adding -1, than in 2C binary turns out to be the number 11111111, which is compatible with the idea of adding number 255.
Let’s get to the point: What happened with the 255 lives of Sinistar?
Wikipedia tells us that the arcade machine Sinistar was created in 1982 by the company Williams Electronics. The people resposible of the game were Sam Dicker, Jack Haeger, Noah Falstein (he developed several point and click adventures for Lucas Film Games) , RJ Mical, Python Anghelo and Richard Witt. The game was about piloting a spaceship dodging the attack of enemy ships, while collecting crystal from asteroids that allowed us to emseble bombs, that later on will be used to fight a terrifying cosmic force with the shape of a skull called Sinistar. When Sinistar was on the screen it produced a scary sound – basically due to due to the low quality of the audio (you can listen to it in this video and there are audio samples here) – and our mission was to use the collected bombs to destroy the final boss, with care no to get trapped in its gravity field. If this were to happen, we would be inevitably dragged towards its gravity centre and out ship would explote, losing one life.
It is in this last point were lays the trick to obtain 255 lives. If our ship gets trapped in the gravity field of Sinistar and, while it was being slowly dragged towards its centre, it was hit by an enemy laser, the life counter turned to be 255. It’s quite funny to listen to one of the programmers (Robert Mical) talk about this topic.
We know enough know to provide a sensible explanation:
- The fact that the life counter turns 255, tells us that an 8-bit variable is used (255 is the biggest number that can be represented with 8 bits), and it sounds good given the dates.
- Robert Mical mentioned that once our ship is captured by Sinistar, the enemy shot would be ignored. However, the enemy missiles that were already fired before our ship being attracted by the final boss’ field could destroy us. For me this is a little bit confusing, in fact, the safest way would be to reproduce the situation by playing the game (if you manage to do it please let me know 😉 ).
- It seems that during the ship capture the routine to check collisions with projectiles was still being called and if this happened, one life was substracted. After the unavoidable explosion, an extra live was subtracted as part of the gravity attraction routine and the life counter was positioned at 255 lives.
- If we consider that the game was over when the life counter was zero, then, the game continued since this the condition was not fullfilled.
- Considering another approach, where instead of checking if the counter is zero, the counter was checked to be less than one, this will not be true either. Here we have to highlight that 2555 is also -1 if using 2C with 8 bits, but this depend on the way that the programmer interpret the number, thus the program must include specific intructions to operate numbers with or without sign. This is very important since the instructions executed by the CPU to check if the number of lives is smaller than one are different for unsigned and signed numbers.
- If intructions for unsigned numbers are used and the lives counter is 255, then the system will never detect the end of the game, since 255 is not smaller than one, regardless us knowing that this number is also -1 in 2C.
- Had instructions for signed numbers been used, then, it would have been possible to detect that the number of lives was -1. But ¿what was the point in doing so if the counter was supposed to be always positive? It is here where lies the problem with glitches (or bugs), that is that they happen because not all possible cases are considered. Moreover, they are difficult to detect.
- As a last task, I wanted to find out the microprocessor used by this arcade machine. The instruction manual from https://www.arcade-museum.com indicates that there are to Motorola microprocessor: 6809E and 6808. It is pointed out that the 6809E is part of the video system, while the 6808 is part of the audio system. But, where does the program run? The manual provide scarce details, but there is a board that is metioned to contain the CPU and the ROM chips. However the provided schematic only shows ROMs.
Williams Electronics (c) 1983
I found at eBay some photos of the boardas and I could check that the CPU is the microprocessor 6809E. All in all, a little bit confusing. Let’s stress that this microrprocessor, that combined 8- and 16-bit operations, was used in computer such as Tandy TRS-80 Color Computer and Dragon 32, in the console Vectrex and in the arcade machines Defender, Gyruss, etc.
Finally, I conclude this post. Leaving aside the basic ideas of the glitch, that I hope that you enkoyed, once more it has become apparent how difficult is to find details as simple as the CPU in an arcade machine. Time goes by and these details would get lost if we do not preserve them.
So, let’s play a little while with Sinistar!
