Inside Spacewar!
Intermission: Yet Another Patch
Spacewar! 2b SA 5 and the Secrets of PDP-1 Loaders
(Introduction · PDP-1 Loaders · Spacewar-SA-5's End · The Patches · Historical Considerations · Operational Notes)
Recently (while working on a more general read-in-memory routine for the emulator) I stumbled over some hidden bits on a digital image of a paper tape, namely of the tape "spaceWar_SA-5.bin". Until now, I believed this to be identical with the usual version Spacewar! 2b (as of April 2, 1962), and, indeed, identical code is loaded from this tape. The suffix "SA-5" merely seemed to preserve a handwritten note on the prespan of the tape, instructing an inclined operator to start the program at address 5 (the entry point for use with testword-controls) rather than using the default start address of 4.
A patch, a patch, we found a hidden patch …
Credits: Screen-shot by J.M. Graetz 1962; Type 30 CRT by CHM / Mark Richards 2013;
Photo of paper tape: unknown; Montage: Norbert Landsteiner 2015
This is about some tiny overhead left unread on the tape, when the loader routine automatically forwards to the usual start address of 4. And, when we inspect this little extra more closely, we'll find two reasons why this would be of some significance:
- Operational: There is an authentic patch to run Spacewar! 2b on a PDP-1 with the automatic hardware multiply/divide option (like the one at CHM).
(Even, if the ships won't instantly explode with the automatic hardware multiply/divide, there's still an issue with gravity. Compare the note at the end.) - Historical: This may be hard evidence of an early dissemination of the program.
(Spacewar! 2b was superceded by version 3 in September 1962, and there was no hardware/multiply upgrade at MIT even then. The upgrade wasn't seen until 1963 and the adoptions made for it in version 4.0 (February 2, 1962). Moreover, this tape is the rare example of an all-in-one tape with the starfield-data included, but lacks all the patches for auto-restart or hyperspace. This might date the tape to as early as April 1962.)
On the other hand, we may suppose that this was done lately, p.e. by the PDP-1 Restoration Team. But there are reasons to exlude any intermediary tempering with the program (see below).
In order to understand why these extra bits would have gone unnoticed at all, we have to dig into the loading procedures of the PDP-1 first:
PDP-1 Loaders
Some may remember the usual loading procedures with early machines: You would key in by hand a tiny loader into the memory of the machine in order to actually start loading something into it. (Veteran PDP-8 operators may recall the octal sequence, "7756 [LOAD AT/set PC], 6032 [DEP/deposit in memory], 6031 [DEP], 5357 [DEP], 6036 [DEP], 7106 [DEP], 7006 [DEP], 7510 [DEP], 5357 [DEP], 7006 [DEP], 6031 [DEP], 5367 [DEP], 6034 [DEP], 7420 [DEP], 3776 [DEP], 3376 [DEP], 5356 [DEP]", to be toggled in by setting up the program counter and then depositing the memory contents by means of the console switches.)
Not so with the PDP-1! — DEC's first wonder featured an automatic Read-In-Memory (RIM) mode, triggered by a dedicated console switch: If in RIM-mode, the machine would read a binary word from the paper tape, inspect it, and, if a dio instruction, it would set it up for execution after the next read (thus transferring the next data word into the memory location specified in the address part of the dio instruction), or, if a jmp instruction, it would execute the jump and transfer the control to the code just loaded at the given memory location.
(A binary read instruction, "rpb", reads a sequence of 3 lines of 6 significant bits each. Each line is to be marked by an octal 200 as a binary code — as in contrast to character data —, any lines lacking the binary mark will be ignored. The first line encountered makes up the highest 6 bits, the second one the middle 6 bits, and the third one, finally, the the lower 6 bits of an 18-bit word.)
Thus, a RIM-sequence may look like this:
data instruction semantics
------------------------------------------------------------------
327751 dio 7751 next address is 7751 (xct after next rpb)
730002 rpb put 'rpb' into location 7751
327752 dio 7752 next address is 7752
327760 dio 7760 put 'dio 7760' into location 7752
327753 dio 7753 next address is 7753
107760 xct 7760 put 'xct 7760' into location 7753
...
607751 jmp 7751 transfer control to pc = 7751
While this is certainly much better than manually keying in a loader and the solution is also favorable for it's decent demand for dedicated hardware, there are a few drawbacks: We'll need 2 words (6 lines) to load a single instruction and there is no provivision for integrity checks, like a checksum. Therefor, RIM-mode was usually used to load a more capable loader program that would do the actual job. Indeed, what we've seen above is the start of a tiny loader routine that is punched by the Macro assembler at the start of a tape. (The RIM-loader and the format used can be traced back to the
The Macro-loader is loaded into the very last addresses of the PDP-1 (7751-7777), and this is, what it looks like:
addr. instr. op-code disassembly ---------------------------------------------- 7751 730002 rpb in, rpb / read a binary word into IO 7752 327760 dio 7760 dio a / deposit IO in a ('dio startaddress') 7753 107760 xct 7760 xct a / execute it (if a jump, it's run.) 7754 327776 dio 7776 dio ck / deposit as first value for checksum 7755 730002 rpb rpb / read ('dio endaddress+1') 7756 327777 dio 7777 dio en1 / deposit in en1 7757 730002 rpb b, rpb / read loop: read next word 7760 000000 0 a, 0 / store it ('dio current-address') 7761 217760 lac i 7760 lac i a / load last value into AC (indirect) 7762 407776 add 7776 add ck / add checksum 7763 247776 dac 7776 dac ck / store the checksum 7764 447760 idx 7760 idx a / increment current address 7765 527777 sas 7777 sas en1 / is it now 'dio endaddress+1'? 7766 607757 jmp 7757 jmp b / no, read more ... 7767 207776 lac 7776 lac ck / load checksum 7770 407777 add 7777 add en1 / add last instruction 7771 730002 rpb rpb / read checksum from tape 7772 327776 dio 7776 dio ck / store it in ck 7773 527776 sas 7776 sas ck / checksums equal? 7774 760400 hlt 0 hlt / no, oops! (halt) 7775 607751 jmp 7751 jmp in / redo (execute next word from tape) 7776 000000 0 ck, 0 / checksum 7777 000000 0 en1, 0 / 'dio endaddress+1'
And this is what the payload data on the tape looks like:
dio STARTADDRESS
dio ENDADDRESS + 1
... DATA ...
CHECKSUM
dio STARTADDRESS#2
dio ENDADDRESS#2 + 1
... DATA ...
CHECKSUM
...
...
...
dio STARTADDRESS#n
dio ENDADDRESS#n + 1
... DATA ...
CHECKSUM
jmp 4 (run the program)
Starting at label in, the loader will read and execute the first instruction. Normally this will be an instruction to deposit the start address of the following data-block. The next instruction will be a dio-instruction for the end-address + 1, followed by the data block and the checksum. The command to deposit a data word, as read at label b, is set up and its address part incremented in label a. When the loader reaches the end of the data block, it compares the checksums. If everything is well and the sums equal, it returns to label in.
Now, the next instruction read from the tape will either be a dio, again, starting the next snippet of continuous data, or a jmp. If it's a jump, loading is done and the instruction "xct a" will transfer the control to the program at the given address (usually 4, the default start address).
In other words, each time the assembler encounters a pseudo-instruction to set the program counter (or when the buffers of the assembler are flushed otherwise), it will start a new data block. Once it encounters the final pseudo instruction "start", it will end the current block and punch a jmp to the start address of the program.
Spacewar-SA-5's End
Provided with this knowledge, we may have a look at the data at the end of the tape "spaceWar_SA-5.bin":
327700 dio 7700 startaddress last data-block 327751 dio 7751 enaddress+1 last data-block ... DATA .... 243056 checksum 600004 jmp 4 run at SA 4 320132 dio 132 start of extra bits 673777 rcr 777 320133 dio 133 673777 rcr 777 320134 dio 0134 540115 mus 115 320135 dio 135 600153 jmp 153 320243 dio 243 260253 dap 253 320244 dio 244 200242 lac 242 320245 dio 245 570253 dis i 253 320246 dio 246 600251 jmp 251 320247 dio 247 240254 dac 254 320250 dio 250 440253 idx 253 320251 dio 251 440253 idx 253 320252 dio 252 200254 lac 254 320253 dio 253 600000 jmp 0 320234 dio 234 260253 dap 253 600005 jmp 5 end-of-tape
As we may observe, the loader will hit the instruction "jmp 4" right after the last checksum and will thus transfer the control to the program, which is by now fully loaded. Since there aren't any rpb instructions in Spacewar!, the rest goes unnoticed and we'll never know that there's actually some data left on the tape.
On closer inspection, this trailing stream of data is an alternation of dio instructions (with mostly consecutive address parts) and instructions which seem to be some actual code, followed by a final jump to the very address 5 that was suggested by the tape's label. This pattern might remind us of a sequence meant for the RIM-mode of the PDP-1.
If we would halt the program, as started by the "jmp 4" at the end of the regular loader payload, and would engage RIM-mode again, this is what would be put into the memory of the PDP-1 by this sequence:
/ patches BBN multiply addr instr op-code disassembly 0132 673777 rcr 777 rcr 9s 0133 673777 rcr 777 rcr 9s 0134 540115 mus 115 mus mp2 0135 600153 jmp 153 jmp .+16 / patches BBN Divide addr instr op-code disassembly 0243 260253 dap 253 dap 253 0244 200242 lac 242 lac dvd 0245 570253 dis i 253 dis i 253 0246 600251 jmp 251 jmp 251 0247 240254 dac 254 dac 254 0250 440253 idx 253 idx 253 0251 440253 idx 253 idx 253 0252 200254 lac 254 lac 254 0253 600000 jmp 0 jmp 0234 260253 dap 253 dap 253 start 5
Lo and behold, this actually patches the arithmetical subroutines for multiply and divide!
The Patches
Let's inspect the damage done to the subroutines so thoughtly composed by BBN (Bolt, Beranek and Newman), which we've already explored in Part 6.
The Patch to BBN Multiply
The first patch overwrites the code beginning with the first of the mus instructions inserted by the pseudo-instruction "repeat 21, mus mp2":
/BBN multiply subroutine /Call: lac one factor, jda mpy or imp, lac other factor. /addr instr. disassembly -- patched -- 0103 0 imp, 0 /returns low 17 bits and sign in ac 0104 dap 105 dap im1 0105 xct im1, xct 0106 jda 116 jda mpy 0107 lac 103 lac imp 0110 idx 105 idx im1 0111 rir 1s rir 1s 0112 rcr 9s rcr 9s 0113 rcr 9s rcr 9s 0114 jmp i 105 jmp i im1 0115 mp2, 0 0116 0 mpy, 0 /returns 34 bits and 2 signs 0117 dap 125 dap mp1 0120 lac 116 lac mpy 0121 spa spa 0122 cma cma 0123 rcr 9s rcr 9s 0124 rcr 9s rcr 9s 0125 xct mp1, xct 0126 spa spa 0127 cma cma 0130 dac 115 dac mp2 0131 cla cla repeat 21, mus mp2 0132 mus 115 rcr 9s / patched 0133 mus 115 rcr 9s / patched 0134 mus 115 mus mp2 / patched 0135 mus 115 jmp .+16 / patched 0136 mus 115 0137 mus 115 0140 mus 115 0141 mus 115 0142 mus 115 0143 mus 115 0144 mus 115 0145 mus 115 0146 mus 115 0147 mus 115 0150 mus 115 0151 mus 115 0152 mus 115 0153 dac 115 dac mp2 / here from patched 'jmp' 0154 xct 125 xct mp1 0155 xor 116 xor mpy 0156 sma sma 0157 jmp 170 jmp mp3 0160 lac 115 lac mp2 0161 cma cma 0162 rcr 9s rcr 9s 0163 rcr 9s rcr 9s 0164 cma cma 0165 rcr 9s rcr 9s 0166 rcr 9s rcr 9s 0167 dac 115 dac mp2 0170 idx 125 mp3, idx mp1 0171 lac 115 lac mp2 0172 jmp i 125 jmp i mp1
We may recall that this sequence of mus instructions is applying a multiply-step for each of the bits in the double register AC and IO. There's just a single mus before we prematurely leave at the jmp instruction — won't this break anything? We may already nurture some suspicion, regarding this single mus instruction, or, is it rather a mul, sharing the same instruction code (54)?
(Veteran readers may recall that the instructions for hardware multiply/divide — mul and div — are reusing the instruction codes of their humbler single-step siblings mus and dis. These symbols are therefor always ambivalent.)
Let's have a look at the other patch:
The Patch to BBN Divide
Again, this is stripping all the dis instructions (opc. 56), just to insert a single one — or is it a div?
(The label dvx is a new label inserted for readability by me, N.L.)
/BBN Divide subroutine /calling sequence: lac hi-dividend, lio lo-dividend, jda dvd, lac divisor. /returns quot in ac, rem in io. /addr instr. disassembly -- patched -- 0233 0 idv, 0 /integer divide, dividend in ac. 0234 dap 244 dap dv1 dap dvx / patched (dvx: a new label) 0235 lac 233 lac idv 0236 scr 9s scr 9s 0237 scr 8s scr 8s 0240 dac 242 dac dvd 0241 jmp 244 jmp dv1 0242 0 dvd, 0 0243 dap 244 dap dv1 dap dvx / patched 0244 xct dv1, xct dv1, lac dvd / patched 0245 spa spa div i dvx / patched 0246 cma cma jmp .+3 / patched (here on overflow) 0247 dac 233 dac idv dac dvx+1 / patched (here on result) 0250 lac 242 lac dvd idx dvx / patched 0251 sma sma idx dvx / patched 0252 jmp 261 jmp dv2 lac dvx+1 / patched 0253 cma cma dvx, jmp / patched 0254 rcr 9s rcr 9s / will be affected 0255 rcr 9s rcr 9s 0256 cma cma 0257 rcr 9s rcr 9s 0260 rcr 9s rcr 9s 0261 sub 233 dv2, sub idv 0262 sma sma 0263 jmp 323 jmp dve repeat 22, dis idv 0264 dis 233 0265 dis 233 0266 dis 233 0267 dis 233 0270 dis 233 0271 dis 233 0272 dis 233 0273 dis 233 0274 dis 233 0275 dis 233 0276 dis 233 0277 dis 233 0300 dis 233 0301 dis 233 0302 dis 233 0303 dis 233 0304 dis 233 0305 dis 233 0306 add 233 add idv 0307 dio 233 dio idv 0310 cli cli 0311 rcr 1y rcr 1s 0312 lio 242 lio dvd 0313 spi spi 0314 cma cma 0315 dac 242 dac dvd 0316 xct 244 xct dv1 0317 xor 242 xor dvd 0320 rcr 9s rcr 9s 0321 rcr 9s rcr 9s 0322 idx 244 idx dv1 0323 idx 244 dve, idx dv1 0324 lac 233 lac idv 0325 spi spi 0326 cma cma 0327 lio 242 lio dvd 0330 jmp i 244 jmp i dv1
The evidence hardens — what we've found here, is a patch to run Spacewar! 2b on a PDP-1 with the hardware multiply/divide!
Historical Considerations
Now that we know what it does and that it does it well, there's one reasonable question left, namely, when this patch would have originated. What may we know about this?
Thanks to good luck and providence, we're provided with an original listing of Spacewar! 2b (25 Mar 62) — compare the addendum to the earlier Intermission and Part 8. This listing from the archives of Martin Graetz carries annotations, both contemporary and from a first attempt to resurrect the original game in 1980 (probably related to the Boston Computer Museum, Malboro, MA, which housed the CHM's PDP-1 before its restoration, and to the 20th anniversary of Spacewar!).
Thanks to these annotations, we know that the feat was attempted before:
A snippet from the listing of Spacewar! 2b (25 Mar 62), p. 4:
BBN multiply routine with annotations on the hardware multiply/divide.
As we may observe, there is a first annotation suggesting quite the same modifications as we've seen it in the patch at the very same spot of the original code. It only falls short an instruction count at the offset for the last jump (15 instead of 16, accidentally crash-landing at the last of the mus/mul instructions). This was commented on in 1980 (June 16th):
Note (16/6/80)
This was an attempt to get Spacewar working on a I with a hardware mul/div.
It didn't work.
There are annotations on the divide subroutine, too. While less organized and decided, they're telling the story of an attempt to dissect the subroutine in order to apply the required modifications:
Page 7 of Spacewar! 2b (25 Mar 62):
BBN division routine with annotations on the hardware multiply/divide.
The scribbled instructions, including the barely legible ones at the lower left, are apparently reading
xct jmp dve-1 jmp dve lac hi lio lo ril 9s div jmp i dv1
This is clearly not related to the modifications we've seen in our patch for the BBN divide routine.
But, there is an inserted page, paginated "6", which is coming up with a altogether different scheme:
Page 6 of Spacewar! 2b (25 Mar 62):
Suggested patch for division with the hardware multiply/divide.
This transliterates to:
spacewar patch for AFCRC divide
idv, 0
dap dv1
scr 9s
scr 8s
dv1, div . i
jmp .+2
idx dv1
idx dv1
dap .+1
jmp . i
(Note: There are essentially two problems here: The instruction "lac idv" for loading the address of the hi-dividend is missing and the "idx dv1" will overwrite the result in the accumulator. Our patch fixes both issues, see below.)
Guessing by the handwriting, this is part of the first set of annotations, predating 1980. Moreover, it's without question Martin Graetz's style of coding (mind the deferring i as a suffix to the address rather than a prefix, quite like we have seen it in his hyperspace-patch). This is rather close to what we've seen in our patch, but, again, not exactly the same.
For comparison, here's our patch again, formatted alike:
/patched BBN divide subroutine for automatic hardware multiply/divide
idv, 0
dap dvx / patch
lac idv
scr 9s
scr 8s
dac dvd
jmp dv1
dvd, 0
dap dvx / patch
dv1, lac dvd / patch
div i dvx / patch
jmp .+3 / patch
dac dvx+1 / patch
idx dvx / patch
idx dvx / patch
lac dvx+1 / patch
dvx, jmp / patch
0
To me, this close relation of the patch and the suggested code in the annotated listing suggests the patch to be a refined version of what had been attempted in the scribbled instructions before, but this time, it's perfectly working code.
Conslusions
So we've quite a guess on the who, but we haven't really covered the when, by now. The handwriting really suggests that all these annotations for a would-be-patch were made by Martin Graetz in not so a great distance to the actual coding of Spacewar! 2b. Moreover, the annotations from 1980 do not appear to be really interested in the subject. It's more a historical note, but there's no sign of an attempt to investigate the subject again.
So, could it have been someone who stumbled over the code and made it working? Probably, someone from the PDP-1 Restoration Team, around 2003? In order to consider this thoroughly, we have to know some about the provenance of the listing: It came from the belongings of Martin Graetz (where it had persumingly been for some years, if not decades — at least, it's his handwriting) and was given in the 1990s to Brian Silverman, who used a listing of Spacewar! 3.1 that came along with it for his seminal Java-emulator (Barry Silverman, Brian Silverman, Vadim Gerasimov, 1996). Later, in 2012 ca., Brian Silverman donated these listings (along with it came the listing of the original hyperspace patch, too) to the iMusée, the Musée de l'informatique du Quebec. So, we know quite well, where the listing has been, and it isn't that likely that it would have been available to the PDP-1 Restoration Team, or anyone else with a lively interest in providing an actually working patch for a PDP-1 with the automatic hardware multiply/divide option. (Moreover, there were other listings of Spacewar! 3.1 and Spacewar! 4 at hand, making version 2b not a prime candidate for a revival.)
Follows that the patch is genuine and timely near to Spacewar! 2b itself, dating it to a period when Spacewar! 2b was the latest cry. Notably, the version of Spacewar! on the main part of the tape is the version using the final polarities for the sense switch settings, "spacewar 2b, 2 apr 62". This gives us an earliest date, but we might consider it to be at least earlier than version 3, Sep 1962. This provides a window from late spring to summer 1962. And, if we would ask, why there aren't any of the "standard patches" on this all-in-one tape, we even may consider it to be more likely early than late.
Last but not least, for whom would it be made? As mentioned before, it's an all-in-one tape, quite contrary to the 2-parts tapes and the extra starfield data which seemed to be the norm at MIT. Then, the patch is, by the way it was recorded, an addendum to the tape, making it a tape for all purposes. And, if we would go into hardware-mul/div-mode by deploying RIM-mode again, we would start at address 5, the setup for testword controls only, because we would be at an installation outside of MIT and its control boxes. It's a tape for export, to be given away. It's a proof for an early dissemination of the program as early as spring/summer 1962. Where to? The usual suspects: BBN, Lincoln Lab, Stanford, DEC itself? — mind this promotinal brochure “PDP-1 Computer and Spacewar” — whoever there was with a newer or upgraded PDP-1 in 1962 …
Operational Notes
The patch illustrates quite well how complex the loading procedure had become over time. It would have looked somewhat like this:
- Load/RIM Spacewar! 2b (
spaceWar_SA-5.bin), starts at4. - Stop it.
- Engage RIM-mode again: loads mul/div patch, starts at
5(no control boxes). - Stop it.
- Load/RIM the hyperspace patch, starts at
4. - Stop it.
- Load/RIM the auto-restart patch, starts at
0. - Stop it.
- Start at
4or5.
As for our patch in the extra bits of tape "spaceWar_SA-5.bin", we have to note that it is solving just half the problem. True, the ships won't explode instantly in the heavy star or at the antipode (depending on the setting of sense switch 5) and there's no visible glitch at all, but, gravity is effectively disabled. — We may add some insights on this later.
We may add that the limited effectivity of the patch is another hint for an early origin at MIT, since it would have been coding by white paper with no option of actually testing it on a live machine, just hoping the best. Real-life testing had to be left to the "customer", and if it didn't work, retry. (An early example of "banana-ware", in this case of halfway to ripeness.)
*****
With this bombshell — oh, it's not about cars — we close our story of a tiny but significant overhead on a tape, in order to return to our scheduled program.
Vienna, March 2015
www.masswerk.at
In case you would have found any errors or inconsistencies, or would have additional information,
please contact me.
*****
◀ Previous: Part 9: Like a WW II Pilot’s Tally — The 4.8 Scorer Patch and Other Spacewar! 4 Oddities
▶ Next: Part 10: Spacewar 4.4 — A Twofold Stand; World's First Attempt at a (Planar) Multiplayer FPS Game
▲ Back to the index.