Here at GAMBIT we've been working on a project that aims to replicate the first computer game written at MIT, Spacewar! In the process we've been learning a lot about the way that games were written for the machines in the pioneering days of computing.
Spacewar! is game of space combat created for the DEC PDP-1 by hackers at MIT, including Steve "Slug" Russell, Martin "Shag" Graetz, Wayne Witaenem, Alan Kotok, Dan Edwards, Peter Samson and Graetz. You can play the game running on a Java emulator here. You can also run the game on the Multiple Emulator Super System (MESS) implementation of a PDP-1 by following the instructions here. The Spacewar! source code we've taken as the base version of the game is also available through that site. Our goal, however, is to make a version of the game that runs on an Arduino that we can demonstrate in the foyer of the lab.
As part of this project we're trying to understand what's going on in the PDP-1 source code that the emulators use. This has meant teaching ourselves the PDP-1 assembly language MACRO from old manuals written in 1962. It's been slow going, because a lot of information is either buried in the technical documentation or was just assumed knowledge that has been lost over time. It's also been very rewarding though and creates a feeling of connection to the minds of those hackers back in the 60s.
Looking around on Google it seems there's not that much information on the Spacewar! source code, and in trying to understand it we've come up with a few tips that might help someone else out:
- Get the manuals for the PDP-1 and also for MACRO. They're available from the Bitsaver's archive and are very helpful. We have noticed that there seem to be errors in some of the example code in the MACRO manual, which were very confusing for me at first. The later examples, however, seem to be correct and are helpful in introducing some of the key concepts in the Spacewar! source.
- Look at the compiled version of source code. There are two listings of the Spacewar! source code. The spacewar.mac file is handy for reading clean code, but the spacewar.lst file contains translations of every instruction into machine code, which is very useful for understanding exactly what's going on with the layout of everything in memory, which in turn is critical for understanding a lot of the low level memory manipulation that the code does.
- MACRO inlines all macro definitions. The MACRO equivalent of functions are (somewhat confusingly) called macros. When you look through the .lst file you'll notice that wherever a macro was used in the .mac file MACRO has gone through and expanded it out inline by introducing temporary variables for each of the macro's arguments. This is what all the strange labels starting with "ZZ" are. Once you know this, reading the source code becomes a lot less confusing.
- All numbers are in octal by default. This took us a long time to work out, although we should have realized it sooner. Unless the MACRO directive "decimal" has been issued in a macro definition the assembler interprets all numbers as octal. All the machine code and addresses that are in the .lst file are expressed in octal.
- There is no stack. For programmers used to working at a C level of abstraction or higher, this was very confusing for us at first. As mentioned above, macros look like function when you write them, but when they are processed by the MACRO compiler they all get inlined. There is no stack pointer. There are no stack frames. Everything is just one big blob of data and instructions mushed together.
- Labels are used both for naming variables and controlling flow. This was very hard for us to wrap our heads around at first. As mentioned before, there is no separation in memory between data and instructions. A coder would just have to make sure that they never let the program counter point to a place in memory that contains data rather than an instruction. The Spacewar! coders will commonly use a label to name an address in memory that they want to jump the flow control to and they'll also use a label to refer to a memory location that they are only going to store data in. As far as we can tell there is no naming convention which distinguishes them. Sometimes data can be stored immediately next to instructions in memory. Thankfully, however, the majority of the game object data is stored in a big contiguous block of memory after the instructions, rather than being completely interleaved.
- Including the symbol "i" after an instruction makes it indirect. We never found an explicit statement of this, but I inferred it from looking at the opcodes in the .lst file. Indirect instructions take a memory address as an argument which tells them where to find the real argument. This idiom is very commonly used in Spacewar!
- Space delimiters mean addition. So for instance "law 1 3 5" is equivalent to "law 9". Plus symbols also mean addition!
- Parentheses define constants. MACRO automatically allocates some memory to hold the constant, stores its value there, and then replaces the constant symbols with the memory address of the constant. For instance when MACRO reads the instruction "lac (2000" in the preprocessing phase, it causes some memory to be allocated, say address 027703, and then stores 2000 in that address, replacing the original instruction with "lac 027703". This is all done prior to execution. We found this very confusing at first.
- Get used to seeing a lot of "dap". The instruction "dap x" deposits the accumulator contents into the argument portion of the memory address x. This lets you change the argument of the instruction stored at that memory address. One of the most common idioms that the Spacewar! programmers use is to manipulate the flow of the program by writing "jmp .", which is a command that says "jump to this address" (which would result in a tight infinite loop if it were actually execute) and then to use the dap instruction to overwrite the target of the jump from "." to some other address that they load into the accumulator. This makes it hard to look at the code and immediately tell what the flow control is going to look like without tracing the execution, since you need to know what the "." is going to be replaced by when the program is actually running. They use a similar idiom for loading data, for example writing "lac ." which if executed straight up would load the contents of the current address (i.e. the "lac ." instruction itself) into the accumulator, but they then use dap to conditionally change the target from "." to some other location that contains data that they want to operate on.
- Think in bits. Spacewar! is written very close to the machine. The programmers have used a frightening array of bitwise manipulation tricks that you don't often see in modern programming. They rotate bits in memory using bit-shifting so that they can store two short numbers in space normally used for one long number. They shift number representations around so that they're in the left or right side of a memory address depending on where a particular instruction call requires that it needs to be, which crops up quite frequently with the display instruction "dpy". They use clever number representations, such as 2's complement, to do fancy arithmetic tricks. They use MACRO to repeatedly double numbers in the preprocessing stage so that they get bit-shifted to the location in memory that they want before execution. They add together the bit codes of instructions to create combined instructions. These tricks are very rarely commented and working out exactly what this "clever" code is doing and why often requires a lot of poking around and reverse engineering.
- Use MESS as a debugger to understand what's going on. The MESS PDP-1 emulator maps ctrl + most of your keyboard buttons to the switches on the PDP-1. You can turn on the "single step" and "single inst." switches and then hit ctrl-p, which will cause the PDP-1 to go into debugging mode and let your step through the code line by line by repeatedly pressing ctrl-p. By reading off the "memory address" lights and converting from binary to octal you can look up where the program is up to in the .lst file and follow the program as it's being executed.
Working on Spacewar! is fascinating. The programming style is unlike anything we've ever worked on before and has certainly made us think about low level programming in a whole new way. For anyone who is interested in computing history and low-level programming we strongly recommend checking it out.