Galaga Stage 0

Galaga's Stage 0 Analyzed and Fixed

by Don Hodges
Posted June 14 , 2008
Updated 11/7/2017

Read all about the Galaga No-Fire Cheat by Christopher Cantrell

The 1981 arcade game Galaga has a kill screen that players encounter if they should pass stage 255. The counter for the level variable wraps around to zero and causes unexpected behavior when stage 0 is played. What happens on this kill screen depends upon the difficulty setting of the machine: On the easy skill, the game resets. On the medium skill, stage 0 plays as a strange cross between the 2nd challenging stage and a regular level where the enemies shoot. You can see a YouTube video of this embedded below, or here: http://www.youtube.com/watch?v=FZHqlfQnR9I. On the hard skill, the words "Stage 0" stay on the screen forever and no more enemies ever appear. On the hardest skill, stage 0 plays like stage 1, but it is still as difficult as stage 255.

The Problem

After lots of digging around in the assembly language code, we discover the source of the problem.

There is a subroutine which uses the level number and the skill setting to determine which enemy formations appear. These formations are stored in two tables. One table is used for regular stages, and the other is used for challenging stages.

This subroutine exhibits bad behavior when stage 0 is reached during a game. The subroutine is not expecting 0, and during an instruction that is supposed to take the level number and change it into a number between 0 and 16, the output instead rolls back down from 0 to 255 (FF hex). This causes a chain reaction and the game then gets incorrect values for the start of these tables.

There are four variables that are used for this routine. One input to the routine is the STAGE. The other input is the DIFFICULTY, which is coded as follows: 0 = MEDIUM, 1 = HARD, 2 = VERY HARD, 3 = EASY. The output of the routine are pointers to two tables, TABLE1 AND TABLE2. For both challenging stages and regular stages, TABLE2 is set to either one value or another. For normal stages, TABLE1 is set based on the LEVEL and the DIFFICULTY. For challenging stages, TABLE1 is set based on which challenging stage it is, which is derived from the LEVEL. For clarity, I have decompiled the original assembly language subroutine (about 30 lines of code) into pseudo code shown below.

A = STAGE ;
WHILE (A >= 23) DO
	A = A – 4 ;
LOOP
IF ((A+1) MOD 4) == 0 THEN
	TABLE1 = #26EC ; 			// CHALLENGING STAGES
	TABLE2 = #27DE ;
	A = (STAGE DIV 4) MOD 8 ;
ELSE 						// NORMAL STAGES
	TABLE1 = #26A8 + 17 * DIFFICULTY ;
	TABLE2 = #26F4 ;
	A = (A - (A DIV 4)) -1 ;
END IF
TABLE1 += A;

The problem occurs in the highlighted line. Stage 0 is not expected and when one is subtracted from it, the variable (actually a Z80 register) rolls backwards from 0 to to 255 (FF hex), instead of the expected range of 0 to 16. This then causes the TABLE1 to be pointing to an area of memory that is not expecting to be used for this purpose, producing the various Stage 0 bugs. This also explains why this bug varies depending on difficulty setting. This bug turns out to be very similar to the one we encountered for Level 0 of Dig Dug, and similar to the problem found in Pac-Man's split screen.

The Fix, version 1

There are probably many ways a fix could be implemented. We want to make Stage 0 playable if possible, so a first attempt to fix this bug results in the following. We insert a subroutine which specifically checks for underflow. So, right after the highlighted statement above, a line is added to the program.

Fixed pseudo code:

A = (A - (A DIV 4)) -1 ;  // Original code
IF A == 255 THEN A = 14 ; // New code to check for underflow

Original assembly code:

25D0: 3D 	DEC A 		; Decrease by 1
25D1: 18 0D 	JR $25E0 	; Jump ahead

Fixed assembly code:

25D0: C3 F5 2F 	JP #2FF5 	; Jump to check for underflow for level 0
...
2FF5: 3D 	DEC A 		; Decrease by 1.  Did A just roll back to #FF ?
2FF6: F2 E0 25 	JP P #25E0 	; No, it is OK, return to program
2FF9: 3E 0E 	LD A, #0E 	; Else load A with a corrected value
2FFB: C3 E0 25 	JP #25E0 	; Return to program

To keep the checksum subroutine happy, we also need to change a checksum byte at location 2FFF, from 74 to 9E.

The fix can be coded into a MAME cheat as follows: Learn more about MAME cheats at cheat.retrogames.com

:galaga:A0600001:25D0:00C3F53F:00FFFFFF:Fix Kill Screen
:galaga:A0710001:3FF5:3DF2E025:FFFFFFFF:Fix Kill Screen (2/4)
:galaga:A0710001:3FF9:3E0EC3E0:FFFFFFFF:Fix Kill Screen (2/4)
:galaga:A0610001:3FFD:0025FF9E:00FFFFFF:Fix Kill Screen (2/4)

Alternately, the Galaga ROM file named gg1-3.2m could be changed as follows. This is the ROM located at position 3L on the logic board of the game.

5D0:  C3 F5 2F
FF5:  3D F2 E0 25 3E 0E C3 E0 25 FF 9E

This fixes the program by changing 3 bytes of code and adding 9 bytes of code, plus 1 byte for the checksum. The problem with this method of fixing the problem is that in order to add this code to the program, unused memory locations must be found and utilized, and a hook inserted into the original subroutine to jump out to the new code, and then jump back. While this fix works perfectly, there is another, perhaps more elegant way to approach the solution.

The Fix, version 2

After looking carefully at the code, we discover that there is another way to fix the bug. It turns out that this method still results in slightly strange behavior when stage 0 is reached on the Medium skill, but it works perfectly for the three other difficulty settings.

What we do is this. Instead of subtracting 1 in the highlighted line, which makes A between 0 and 16, we instead subtract 1 from the original address used in the solution, and leave A to be between 1 and 17. This way, when stage 0 is reached, it uses the last wave from the previous skill level listed in the table.

Original code:

TABLE1 = #26A8 + 17 * DIFFICULTY ;
...
A = (A - (A DIV 4)) -1 ;

Fixed Code:

TABLE1 = #26A7 + 17 * DIFFICULTY ;
...
A = A - (A DIV 4)    ;

You can see that we have removed the subtraction and changed the original address to one less than what is was. A minor problem with this is that when stage 0 is reached on medium skill, the value for TABLE1 becomes #26A7 which is not intended to be used for this purpose. By stroke of luck, the value in this memory cell allows this stage to be playable, although there are only four groups of enemies that enter instead of the expected five. The screen shot below shows the formation after it has entered; you can see it is missing a few columns of the blue enemies.

Galaga Stage 0 Medium Skill
With the Underflow bug fixed, Stage 0 on medium skill is still missing a few enemies.

Next we look at the original assembly language coding of the game instead of my pseudo code and implement the fixes there:

Original Code:

25C3: 21 A8 26 	LD HL,$26A8 	; Load HL with #26A8
...
25D0: 3D 	DEC A		; Decrease by 1

Fixed Code:

25C3: 21 A7 26 	LD HL,$26A7 	; Load HL with #26A7
...
25D0: 00 	NOP		; No Operation

To keep the checksum subroutine happy, we also need to change a checksum byte at location 2FFF, from 74 to B2.

This fix can be implemented by using a MAME cheat code as follows. Learn more about MAME cheats at cheat.retrogames.com

:galaga:20000001:2FFF:000000B2:000000FF:Fix Kill Screen V2
:galaga:20410001:25D0:00000000:000000FF:Fix Kill Screen V2 (2/3)
:galaga:20010001:25C4:000000A7:000000FF:Fix Kill Screen V2 (3/3)

Alternately, the Galaga ROM file named gg1-3.2m could be changed as follows. This is the ROM located at position 3L on the logic board of the game.

5C4:  A7
5D0:  00
FFF:  B2

This fix is implemented by changing just two bytes of code, plus one byte for a checksum fix.

Comments and Conclusions

Without cheating, this game is pretty difficult and it is forgivable that this bug was not discovered during play testing. I rather like the extremely short (2 byte) patch that I was able to create for this game.

In my youth, probably in '83 or '84, I found out about the no-fire cheat that this game has, and was able to reach the kill screen a couple of times. One day I was able to reach stage 0 after about two hours of play. The difficulty must have been set to HARD, because I remember getting to where "Stage 0" stayed on the screen forever. I showed this to the arcade attendant who promptly refunded my quarter and proceeded to power cycle the game in order to get it working again.

Coming Next: Debunking the myth that you can get extra shields by shooting Darth Vader many times in Star Wars.