Arecibo message, surbroutines, and the COSMAC 1802

In the "cosmacelf" Yahoo group for the 1802, on April 7th 2010, Steve Gemeny offered a bit of assembly code into their files archive called "arecibo". It blinks out the binary "Arecibo" message" sent by that radio telescope back in 1974. (See Wikipedia for the history of that event and details of the message.) The Q output, attached to an LED, does the job. The code was a little larger than 256 bytes. See Steve's code and further explanations in the Cosmacelf file archive under that name.

When asked for details, Steve posted: "I have my basic ELF sitting on the bookcase behind my desk, blinking away... When asked what it is, I answer, 'That's a 70's vintage interstellar communications system.' " When asked what's it doing, I answer 'sending a message from earth to M13 in the Taurus cluster', sometimes I pull out the graphic image and talk about what's in the message (Geek Alert!)."

Steve continued: "But if you are thinking of a receiver, remember there is no clock sent along with the data. That means the 0s have no transitions and there are quite a few of them. Timing would need to be rather tight unless differential encoding was added in the sending side. The easiest decoder might be to connect the Q to something a PC could sense and decode it on screen. That isn't my thing though".

"Another idea for improvement is squeezing some "air" out of the data and making the complete image fit into a quarter K. In the data format I chose there are 73 wasted bits... Squeeze them out and there is more room for data. 8 bytes down, 37 to go... That only leaves 36 Bytes for the code, could be tough."

"I'm interested to see if anyone else runs it on some other machine too.- Enjoy, Steve"

On April 10th, Dennis Boone got Steve's code down to 251 bytes. He said to me later: "Steve had to leave out part of the message due to space constraints. By bumming the code down (39 bytes) and storing the data more efficiently (210 bytes), I got all of it in. The tradeoff, of course, is some non-obvious shenanigans and the requirement that it run in page 0." Here's the assembled listing.

In response on May 2010, I saw one correction on Dennis' code, and how to add a clock to blinking the Q LED. The correction was on an extra branch (Dennis confirmed the fix.). Here's what Dennis does on toggling Q:


	(get bit)
	BNF WAIT ; If it's not 0...
	SEQ ; ...turn on the LED
WAIT:
	GHI 6 ; Handy spare 00 into D
SPIN:
	SMI 1 ; Waste some time subtracting 1
	BNZ SPIN
	REQ ; Turn off the LED
	(loop to get next bit)

This means the LED is off or on for long strings of consecutive 1's or 0's. It's possible to "lose count", and if your "signal" is lost you don't know if that's a run of zeros or not. In the signal trade we call that a lack of a "clock" signal. You want to send something all the time, if you want to "include" a clock.

A change to the clock code I came up with, is as follows:


	(get bit)
	BNF WAIT ; If it's not 0...
	SEQ ; ...turn on the LED 1/3 time if a 1
WAIT:
	GHI 6 ; Handy spare 00 into D
SPIN:
	SMI 1 ; Waste some time subtracting 1 from D
	BNZ SPIN ; LED is on or off 1/3 time

	SEQ ; ...turn on the LED 
SPIN2:
	SMI 1 ; 1/3 time with LED on 
	BNZ SPIN2

	REQ ; Turn off the LED
SPIN3:
	SMI 1 ; 1/3 time with LED ALWAYS off
	BNZ SPIN3

..so a 1 is when the LED is on 2/3 time, and a 0 is when the LED is on 1/3 time. So you always have a "signal". For Morse code enthusiasts, this is a series of "dits" and "dahs" (and space) for zero and one.

That's not hard to "detect" at the other end - measure the length of the pulses, and you'll see two kinds, "short" and "long". A simple timer set to a length between the "short" and "long" pulses will see a 1 or 0.

But I can't make my version's code "fit" the 256 byte space. The SMI 1/BNZ SPINx code is four bytes, it adds up! Is there a shorter way to make a timed loop? Can a coroutine save space? I'm not a good enough 1802 programmer to know, but it's so few bytes that most tricks don't seem to be productive.

Again, Dennis Boone responded on Sept 2 and produced this version which compressed my clocking scheme. I edited his code slightly to provide more explanation. Here's my edited version and also here's the assembled result and the hex file. One other difference between the two sources, is that I use R0 for the program counter - default after reset - while Dennis uses R3.

Dennis implemented a subroutine call/return to save space, among other tricks, as follows:

	;set R0 to program counter (reset)
	;load accumulator with SPININ address
	PLO 8 ;store SPININ addr in R8

;bit loop
	;set or reset Q depending on bit
	GHI 6 ; Handy spare 00 for accum
	SEP 8 ; Waste some time, "call" SPIN
	SEQ ; set Q
	SEP 8 ; Waste some time, "call" SPIN
	REQ ; reset Q
	SEP 8 ; Waste some time, "call" SPIN
	... loop and get more bits
	....

SPIN:   ;"called" with accum = 0 for max delay
	SMI 1  ; delay by decr accum
	BNZ SPIN
	SEP 0  ; "return" via R0 as PC; R8 -> next instruction
SPININ: ; Sub entry past end of subroutine
	BR SPIN

The subroutine register R8 is set to the BR SPIN instruction at the END of the SPIN subroutine. Before the call, the accumulator is set to zero for the routine's use. The "call" consists of SEP-switching the PC to R8. Execution goes to the BR instruction, which runs the routine (decrement the accumulator through to zero). The end of the routine will SEP-switch the PC back to R0, which is already pointing past the prior "call" instruction. Likewise, R8 is pointing past the SEP 0 instruction back to...the BR SPIN instruction!

Dennis comments: "This goes back to the SCRT (System Call/Return Technique). Traditionally it's done in this order, I think:

RET:   SEP   0
FUNC:  ; do something useful here
       ;
       ;
       BR    RET

"Either way you reset the PC for this sub just before returning, but as you saw, I needed the entry to be 2 bytes before the data, so I flipped it over."

There's a few other tricks to gain a few more bytes. Look in Dennis code, or my edited version which I hope explains them correctly!

Herb Johnson

Contact information:

Herb Johnson
New Jersey, USA