Retrochallenge 2016/10:
Ironic Computer Space Simulator (ICSS)

Episode 2: Stars & Sync

We start our efforts on the code with amazing news: In case we succeed, we may have a realistic chance that the code may be run on the only operational PDP-1 existing, the restored PDP-1 at the CHM. Reason enough to get going…

Computer Space: Background stars and PCB stack

Computer Space background stars and PCB stack.
(Screenshot by Ed Fries, 2015; photo of PCB stack, two-players version: KLOV;
schematics of single-player version of the Sync-star board: Nutting Associates, 1971.)

The single-player version of Computer Space (there's a one-or-two-player version too, the origin of which is somewhat subject to debate) consists of 3 PCBs: The Sync-star board, the memory board and the motion board. The first of them the Sync-star board is the only board that can be run without the other twos, providing — as may be guessed from its name — the basic synchronization (required to feed a video signal to the TV) and the background starfield.

This may be a good starting point for our project, too. Well set up a basic program with main loop to be executed for each frame and populate this with a starfield to be used as a backdrop for the game. Let's have a closer look at the background stars of Computer Space:

Computer Space: background starfield

The background stars of Computer Space.
(Image: Computer Space Simulator by Mike "Moose" O'Malley.)

Oops — Lots of stars! A rough estimate is about 250 of them. (Bet, it's 256?) In comparision our reference application for the PDP-1, Spacewar!, has about 40 of them concurrently on the screen. As already mentioned, display commands are our major bottleneck and we simply cannot afford that many dots to be drawn each frame. So we may have to think about something different, involving less of these celestial blips.

The pattern of the background stars of Computer Space is always the same, it's hard-wired on the board. We enjoy a bit more of freedom here, and we may want to go with a random starfield that is set up individually at the beginning of each game. And maybe, we'll also add a little extra.

But before we actually start, we'll have to spend some words on the Macro assembler. (This episode may be rather extensive, but as we go along, we'll be able to reduce our explanatory comments quite a bit.)

The Macro Assembler

MIT's Macro assembler has its root on the TX-0, and even the output format is similar on the PDP-1. It's a straight forward two-pass assembler and we may provide the most essential rules in just a few lines:

As for the instruction codes, we'll discuss them, as we'll encounter them. However, I've prepared an overview of the PDP-1's instruction list and there's also a short version of it provided in a tab at the bottom right of this page, expanding for quick reference.

Open in a new tab/window:   PDP-1 Instruction List

A PDP-1 Assembler Code Boilerplate

Let's start with the basic layout of any PDP-1 macro-code. Most programs start at address 4 — for a reason:
The PDP-1 has a Sequence Break System (by moderns banally called a system interrupt). In case a Sequence Break occurs, the PDP-1 dumps th contents of the accumulator (AC) in address 0, the contents of the program counter (PC) in address 1, and the contents of the in-out register (IO) in address 2. Then it executes the instruction currently in location 3. Thus the first 4 addresses (0...3) are reserved for the purpose of the Sequence Break System and the first location available to our program is address 4.

Lets have a look at basic Sequence Break handling (this is the one found in Spacewar!):

/routine to flush sequence breaks, if they occur.

sbf,	tyi		/ reset console typewriter
	lio 2		/ restore io (fom contents of addr. 2)
	lac 0		/ restore ac (fom contents of addr. 0)
	lsm		/ leave sequence break mode
	jmp i 1		/ resume: indirect jump to address in loc 1

Here, "sbf" is the first example of a label (it's 3 characters and followed by comma), marking the location of instruction "tyi". This one resets the internal state for the communication with the console typewrite (Soroban), because, it's 100:1 that — once again — someone couldn't resist to tap a key. Then we restore the contents of the registers from where the Sequence Break System has dumped them, instruct the machine to leave the break-mode (because our interrupt handler has finished) and pick up, where we were interrupted by an indirect jump to the value in address 1. — The most simple code to just ignore the break.

Of course, we've to insert a jump vector to our sequence break routine at address 3. Putting it all together, we arrive at the following basic layout:

title of my great program

/insert some macro definitions here?

/set program counter to 3 and insert jump vector to squence break routine
/followed by a jump to the main program (here a0) at 4

3/	jmp sbf		/ ignore seq. break
	jmp a0		/ start addr, jmp to a0

/routine to flush sequence breaks, if they occur.

sbf,	tyi
	lio 2
	lac 0
	lsm
	jmp i 1

/maybe some other macros and parameter definitions?

/main program

a0,	....		/snip

/insert constants and variables, end of program

	constants
	variables

	start 4

Pretty easy. If we risk a further look at addr. 3, this is what the assembler produces as an output listing:

    8 00003             3/	jmp sbf		/ ignore seq. break
      00003 600005

The first line gives the line number and the current location (PC) followed by the source code, the second line the address and the value generated for it. As we may see, it just added up the instruction code for "jump" (octal 600000) and the value represented by the label "sbf" (here "5", since the jump to "a0" occurs at addr. 4 and our label "sbf" thus follows at 5). That's it.

Setting Up Some Stars

Time to actually venture into our program — let's set up some stars. For this it may be nice to know something about the display command (dpy) and how screen coordinates are transmitted.

Actually the command "dpy" is a subcode of the in-out transfer group "iot". It's basic instruction code is "720000", where the least significant triplets encode the target device or port. In the case of the "dpy" instruction it's 720007, or — as the Macro assembler defines it including the i-bit730007. We'll see in a moment why.

Remember the Sequence Break routine and the instrcution for resetting the console typewriter? This honorable device, named Soroban, was a glorified IBM Model B electric typewriter put on steroids by Soroban Engineering of Melbourne, FL. This "very intricate mechanical marvel"CHM) remoted keypresses by the help of selenoids and was the only standard peripheral equipment that came with the PDP-1, besides the iconic DEC-chair.
Now, the mechanism was known to be, as mentioned, intricate, to times even flaky, and every now and then a printout would stop. What to do? Simply press the last letter printed and the process would resume! (Thanks to Ken Sumrall from the PDP-1 Restoration Team for the story!) — What may we learn from this? There's a full-fledged echo communication going on between the PDP-1 and any of its peripheral devices, with buffer registers and checks. And even more, the communication is fully asynchronous.

The Soroban console typewriter of the PDP-1 (CHM)

The Soroban console typewriter.
(CHM, Catalog No. 102664302.)

On the side of the CPU — and, that is, the programmer — all this asynchronous control flow is abstracted into a single, universal completion pulse. And that is, what is controlled by the i-bit in conjunction with the in-out transfer commands. (This is an example of the marvel of computer engineering that is the PDP-1: Embedding a still simple and easy to use CPU into a system of memory and I/O control circuitry that is at least as complex as the machine that is facing the programmer by abstracting its complexity into an asynchron access scheme that is as simple as a single bit.)

The control of asynchronous I/O is done by setting bits 5 (i-bit) and bit 6. Generally, setting the i-bit results in a blocking operation by requesting a completion pulse from the I/O device and immediately halting to wait for it (in case of the dpy command this would occur 45 microseconds later), or just fire the command and continue (hoping the best).

A fully controlled asynchrounous communication can be established by the help of bit 6: If this XOR-ed with the i-bit is hi, a completion pulse is requested anyway, even, if the CPU does not block. Hence, we may (and have to) wait at any other time for the completion pulse by the "ioh" instruction.

So, there are the following viable options (mind that "dpy" is defined in the assembler including the i-bit):

i-bit  bit 6      effect       display command (in Macro)
  1      0        block             dpy
  0      0       no wait            dpy-i      (i: 10000)
  0      1       request cp         dpy-4000

sequence continue-&-request-cp ... wait:   dpy-4000 .... ioh

So, that we know this, how are coordinates transferred? By the means of AC (x) and IO (y). Just load those values into the respective registers and fire your "dpy" command. Only the most significant (highest) 10 bits are significant. (Using this format, we've established a fixed point fractional coordinate system for our game, already.)

Just for fun, we'll use a single 18-bit word to store the 2 coordinates. This may give a precision of just 9 bits, but we'll just assume the least significant bit being zero, since, we do not want to have any touching stars, anyway.

We start by declaring a symbol for the number of stars (we may decide to change this later), and then reserve a bit of space for the coordinates' table, a word per star:

/subroutines for background display

nos=77 	/number of stars

/table of stars coors (nos words, 9 bits x and 9 bits y)
bst,	. nos/

The label "bst" (background star table) now points to the first address of our table and the expression ". nos" adds the value of symbol "nos" to the current value of PC and reassignes it to this new vale. Thus, the next instruction will be assembled after a gap of nos (octal 77) locations.

Now, let's come to business. We'll need a random number generator and we'll steal our's recklessly from Spacewar!. (It may have been unique to Spacewar! or it may have been some kind of common code, anyway.) It's the macro definition "random", scrambling and modifying the bits in location "ran" (we'll have to declare this label) and also leaving the new random number in AC:

define random
	lac ran			/ load value of loc. ran in ac
	rar 1s			/ rotate ac right one bit
	xor (355670		/ xor ac with constant 355670
	add (355670		/ add constant 355670 to ac
	dac ran			/ deposit ac in loc. ran
	term			/ terminate (abrev.)

ran,	0			/ random number

/setup (nos random coors starting at bst)

bsi,	dap bsx			/ deposit return address
	law bst			/ load adddress of label bst into ac
	dap bsc			/ deposit ac in address part at label bsc
bsl,	random			/ get a new random number
bsc,	dac .			/ store it in current loc of st
	idx bsc			/ increment value in bsc, leave it in ac
	sas (dac bst+nos	/ is similar to (dac + bst + nos) ?
	jmp bsl			/ no, jump to bsl
bsx,	jmp .			/ return

The entry point to our subroutine is at label "bsi". That is, we are expected to call this by the instruction "jsp bsi". But how does a jump to subroutine work, without a CPU stack? Were to put the value of the return address? The PDP-1 puts it simply into AC and it's our job to take care of it. We'll use the instruction "dap" to just overwrite the address part (bits 6–17) of the target location with the contents of AC. The target is here the instruction "jmp ." at label "bsx". We're encountering here two conventions that are totally arbitrary: 1) a dot (.) as the lone address part of an instruction indicates that the address will be fixed up later (so, anything pointing to itself is a candidate for fix-up), and 2) all labels of a subroutine or task will start with the same character(s) and the label of the return instruction will end in "x".

(Note: There's also a practical aspect to using a dot (".") for the address part of a jump instruction that is to be fixed up: If we fail for some reason to set the return address, the machine will loop at this jump instruction to itself, thus identifying by the console lights, where we erred. If we left this blank, we would jump to location 0, regardless from where we came.)

The instructions "law" (load the literal value in the address part into AC, as opposed to lac loading the contents of the location provided in the address part) and "dap" (deposit AC in address part only) set up the address part of the location labeled "bsc" to the first address of our coordinates table.

Label "bsl" marks the start of our working loop, where the code of macro "random" is inserted in place. At the end of this macro, the newly generated random number is still in AC, and we deposit it in the location the address part of the "dac" instruction at label "bsc" is currently pointing to. — We've just stored our first coordinates!

Then the instruction "idx bsc" (index) increments the value in "bsc", in order to point to the next address in our table. As a side effect, the incremented value is also left in AC. So we may compare it to the last address (bst+nos) we have to vist. Since "bsc" also contains the instruction code for "dac", we'll compare it to the constant expression "(dac bst+nos". Instruction "sas" skips the next instruction, if the value is equal to the one in AC. If not, we've another iteration of the loop to do and jump back to "bcl". If we're done, the instruction "jmp bsl" will be skipped and we'll finally reach our fixed-up jump to return at label "bsx".

We may observe that this kind of code is notoriously self-modifying. It's true that we could have used some labeled pointers and indirect addressing instead, but this way we would have lost some precious instruction cycles for the additional memory lookups. However, this kind of code used to be common praxis.

Phew! — to make standard tasks a bit simpler, there's a set of common macros that we may use to substitute some of our instructions, generating the same code as above:

define initialize A,B
	law B
	dap A
	term

define index A,B,C
	idx A
	sas B
	jmp C
	term

/setup (nos random coors starting at bst)

bsi,	dap bsx				/ deposit return address
	init bsc, bst			/ deposit first addr of bst in bsc
bsl,	random				/ get a new random number
bsc,	dac .				/ store it in current loc of st
	index bsc, (dac bst+nos, bsl	/ increment bsl, repeat at bgl for nos times
bsx,	jmp .				/ return

We may observe that macros may take parameters. Parameters are upper-case and unique to individual macro definitions. Especially the makro "index" is quite versatile as it combines the count-up of loops with a condition to check the iterated value against a terminating expression. (Think of the the second and third part of a C-loop combined in a single pseudo-instruction.)

Displaying the Stars

We're still missing a routine to display our preciously defined stars. Here it is:

/display background stars (displays every 2nd frame only)

bg,	dap bgx				/ deposit return address
	isp bgc				/ increment bgc, skip on positive
bgx,	jmp .				/ return
	law i 2				/ load -2 into ac
	dac bgc				/ deposit in bgc to reset frame counter
	init bgl, bst			/ init bgl to first addr of stars table
bgl,	lac .				/ get coors of next star (x/y)
	cli				/ clear io
	scr 9s				/ shift low 9 bits in high 9 bits of io
	sal 9s				/ move remaining 9 bits in ac in high part
	dpy-i				/ display a dot at coors in ac (x) and io (y)
	index bgl, (lac bst+nos, bgl	/ repeat the loop at bgl nos times
	jmp bgx				/ return

bgc,	0

The first instruction is again the obligatory disposal of our return address. The next 4 instructions are dealing with displaying the stars every second frame only. The reason for this is the built-in brightnesses of the Type 30 CRT not really scaling well, also we may not want to spend every frame on the background display. (That is, we'll have slightly longer frames displaying the stars, followed by a slightly shorter frame skipping the display routine.) Thanks to the afterglow of the special long sustain phosphor of the Type 30 CRT the stars will be still visible, hopefully flickerfree (at least on the real machine), but they will be visually pushed back into the background.
(Woa — another Spacewar!-trick!)

To achieve this, we increment the value in the location labeled "bgc" (background counter) using the instruction "isp". This one is like "idx", which we've seen before, but also skips the next instruction, should the new vualue be a positive one. If not (i.e., it is negative), we immediately exit at "bgx". If it was positive, we load the literal value -2 into AC by the instruction "law i 2" (the i-bit here denotes a negative vale) and store this for the next call in "bgc". (The value in "bgc" will thus alternate after the increment between -2+1=-1 and -1+1=0.)

The insertion of macro "initialize" (short "init") sets up the address part at "bgl", the start of our display loop, to the first addres of the stars table (bst). The "lac" at "bgl" loads this 18-bit value into AC. "cli" clears IO to zero in preparation for the next steps. These are all about splitting these 18.bit word into two 9 bit values at the high end of AC and IO:

The PDP-1 has some very versatile rotate and shift instructions, micro programmed in a single shift group. While the op-code of the instruction indicates the kind of rotation or arithmetic shift and its direction, the lower 9 bits provide the number of bit-positions by which the value is to be moved. More precise, it's the number of hi-bits, as in 1, 3, ... 777. The Macro assembler provides for this a range of handy symbols, as in "s1", s2, ... s9.

Instruction "scr 9s" (shift combined registers right) combines AC and IO into a single 36-bit register and shifts its contents right by 9 bits, the maxiumum amount. Now, we've moved the lower part of AC into the highest position in IO and the remainder is now in the lower 9 bits of AC. "sal 9s" is the reverse shift to the left by 9 bits, but now on AC only, restoring the high-part of AC.

Now we're finally ready to display the star: Should we wait, or should we go (i.e., fire and forget)?

With a coarse look at our code, we're pretty sure that we pass more than 50 microseconds between display commands and opt for go, as in "dpy-i".

Follows the increment of the loop, same as in the setup routine, and, if we terminately fall through, we're jumping to the return at label "bgx".

Some Final Enhancements

By this, we've a static background display, just like the one of Computer Space, but with a little fewer stars. But, what about burn-in? The Type 30 CRT Display is precious equipment, even more now than then! We really should add some animation. We're yet undecided on the kind of animation or movement we'll want to apply for the stars, just scrolling them slowly around (like in Spacewar!), or, maybe, even some kind of parallax effect, relative to the movement of the player's rocket? (You'll bet on the latter!).

In order to do so, we add two further labeled locations at the end, namely "bgh" and "bgv" (for horizontal and vertical offsets, respectively) and add them to the coordinates.

Here, we encounter another essential macro, "swap". This swaps the values in AC and IO by rotating them as a combined 36-bit register twice by 9 bits (making 18 bit positions or a full word length in total). By this we get our final version of routine "bg":

define swap
	rcl 9s
	rcl 9s
	term

/display background stars (displays every 2nd frame only)

bg,	dap bgx				/ deposit return address
	isp bgc				/ increment bgc, skip on positive
bgx,	jmp .				/ return
	law i 2				/ load -2 into ac
	dac bgc				/ deposit in bgc to reset frame counter
	init bgl, bst			/ init bgl to first addr of stars table
bgl,	lac .				/ get coors of next star (x/y)
	cli				/ clear io
	scr 9s				/ shift low 9 bits in high 9 bits of io (x)
	sal 9s				/ move remaining 9 bits in ac in high part (y)
	add bgv				/ add vertical offset
	swap				/ swap contents of ac and io
	add bgh				/ add horizontal offset
	dpy-i				/ display a dot at coors in ac (x) and io (y)
	index bgl, (lac bst+nos, bgl	/ repeat the loop at bgl nos times
	jmp bgx				/ return

bgc,	0
bgh,	0
bgv,	0

Syncing Frames

Now, it's time for the main loop. The PDP-1 is built for realtime, but it is actually missing a major provision for this: the system clock. — So how may we sync our frames? Bet, we'll do it by a delay loop.

We'll declare a budget of instructions and — as our program will grow more complex — subtract certain amounts per task from it. Any remainder will be spent in a delay loop. And while there is no app for this, there's still another macro.

define count A,B
	isp A
	jmp B
	term

This will count up a negative value in A towards zero. If finished, we fall through at the exit, else we'll jump to location B to iterate. A quick look at the instruction list tells us that we'll spend 3 cycles per iteration.

And here is our main loop, currently just calling the background subroutine each frame:

/start a new run

a0,	jsp bsi				/ initial setup of bg-stars
	dzm bgh				/ reset offsets of stars to zero
	dzm bgv

/main loop

fr0,	load \ict, -4500		/ initial instruction budget (delay)

	jsp bg				/ display background

	count \ict, .			/ use up rest of time of main loop
	jmp fr0				/ next frame

At the start of the main program, at label "a0", the very label we jumped to at location 4 (our start address) calls the setup routine for the background. Also, we reset the contents of the vertical and horizontal offsets zo zero (instruction "dzm").

Label "fr0" marks the start of our frame, where macro "load" sets up the initial instruction count. Here is its definition:

define load A,B
	lio (B		/ load B as a constant into IO
	dio A		/ deposit IO in loc. A
	term

(Again, this a macro from the common "macro fio-dec system".)
The value (-4500 = 7,104 instructions = 35,520 microseconds) is quite arbitrarilly chosen (and may be adjusted later).

Inside this loop, we call the background routine ("jsp bg") and spend our time in the delay loop ("count \ict, .", expanding to "isp \ict" and "jmp .", where the dot denotes the insertion point or beginning of the macro, the very instruction "isp \ict").

You may have noticed the backslash in front of "\ict" — yes, this is our first assembler variable. It is managed like any labeled address, but it's address will be determined by the next occurrence of the pseudo-instruction "variables".

The Code, So Far

ironic computer space  0.01  nl 2016-10-12

define initialize A,B
	law B
	dap A
	term

define index A,B,C
	idx A
	sas B
	jmp C
	term

define swap
	rcl 9s
	rcl 9s
	term

define load A,B
	lio (B
	dio A
	term

define setup A,B
	law i B
	dac A
	term

define count A,B
	isp A
	jmp B
	term

define random
	lac ran
	rar 1s
	xor (355670
	add (355670
	dac ran
	term


3/	jmp sbf				/ ignore seq. break
	jmp a0				/ start addr, jmp to a0

ran,	0				/ random number


/routine to flush sequence breaks, if they occur.

sbf,	tyi
	lio 2
	lac 0
	lsm
	jmp i 1


/subroutines for background display

nos=77 	/number of stars

/table of stars coors (nos words, 9 bits x and 9 bits y)
bst,	. nos/

/setup (nos random coors starting at bst)

bsi,	dap bsx				/ deposit return address
	init bsc, bst			/ deposit first addr of bst in bsc
bsl,	random				/ get a new random number
bsc,	dac .				/ store it in current loc of st
	index bsc, (dac bst+nos, bsl	/ increment bsl, repeat at bgl for nos times
bsx,	jmp .				/ return


/display background stars (displays every 2nd frame only)

bg,	dap bgx				/ deposit return address
	isp bgc				/ increment bgc, skip on positive
bgx,	jmp .				/ return
	law i 2				/ load -2 into ac
	dac bgc				/ deposit in bgc to reset frame counter
	init bgl, bst			/ init bgl to first addr of stars table
bgl,	lac .				/ get coors of next star (x/y)
	cli				/ clear io
	scr 9s				/ shift low 9 bits in high 9 bits of io (x)
	sal 9s				/ move remaining 9 bits in ac in high part (y)
	add bgv				/ add vertical offset
	swap				/ swap contents of ac and io
	add bgh				/ add horizontal offset
	dpy-i				/ display a dot at coors in ac (x) and io (y)
	index bgl, (lac bst+nos, bgl	/ repeat the loop at bgl nos times
	jmp bgx				/ return

bgc,	0
bgh,	0
bgv,	0


/start a new run

a0,	jsp bsi				/ initial setup of bg-stars
	dzm bgh				/ reset offsets of stars to zero
	dzm bgv

/main loop

fr0,	load \ict, -4500		/ initial instruction budget (delay)

	jsp bg				/ display background

	count \ict, .			/ use up rest of time of main loop
	jmp fr0				/ next frame


/insert constants and variables, end of program

	constants
	variables

	start 4

Meanwhile, we've also prepared and set up our in-browser emulation (HTML5/JavaScript). We decide to render the screen at 640 × 640 pixels, so that we reveal plenty of detail in a format that should still fit most screens:

PDP-1 emulation dedicated to Ironic Computer Space

Our trusty emulator set up to run ICSS, head over to www.masswerk.at/icss/.

And this is what we get (see www.masswerk.at/icss/):

Ironic Computer Space: background stars

The background starfield.

That's all for this post.

 

Next:   Episode 3: Rocketry — Or, Fly Me to the Moon Stars

Previous:   Episode 1: Platform Considerations

Back to the index.

— This series is part of Retrochallenge 2016/10. —