SUBLEQ is Hard!

It all started so innocently! The LCM+L Employee Engagement Committee wanted something for employees who had gone beyond the call of duty, to be able to wear that would get people to ask why only they they had this thing. We thought maybe it might blink to catch folks attention. Sure, I can do that, no problem!

When I asked my boss: Stephen Jones about it, he said “Sure, but it has to be a fully programmable 9 bit computer with a complete front panel!”. Oh, he says, it should be able to make sounds too. Before it was “falling off a log”, for me, but now the log is 8 feet in the air, one must fall off carefully, and with forethought!

I made something the size of a business card, and it had a few problems: 1) I had messed up the multiplexing, and whenever you pushed on one of the data bit buttons both the data LED, and the address LED above it came on, whether I wanted them to or not. 2) The bit ordering on the LEDs and switches was backwards, requiring bit fiddling in the software. 3) It was almost all surface mount. This shouldn’t be a problem, right? Somewhere in here, someone asked, could we sell it as a kit? Could we teach a soldering class with it? A lot of the parts on this one were 0805 SMT parts, that means they are 0.08″ x 0.05″. That is the outline of the part, which is pretty small! Working with them requires tweezers and, at least for me, magnification.

The board grew a little bit to 2.5″ x 4.25″, and the LED’s and buttons went to through hole, to be big enough for beginners to solder. That is what the photo above shows, but I hadn’t mounted the speaker in that upper right circle when I took the picture. I did fix the multiplexing, and bit ordering problems in the process.

Some about the Bit Token: The processor on the board is the ATMEGA328, that is the heart of the Arduino Uno. I was a little short on pins, and brain cycles to use the ATMEGA32U2 or a CP2102 usb to serial chip to make it actually Arduino compatible. One can get a programmer widget for under $10 on Amazon.

The first thing I had to do, starting with the original board, was test the hardware. I started by writing code to blink the lights. Remember blinking the lights? That used to be the target! Pressing the “run” button while holding one or more of the data buttons will cause it to blink its lights in 10 different patterns. Pressing the “run” button again will stop that pattern, so you can try another.

Any computer needs to communicate, with more than just the lights, so the Bit Token has a TTL serial port. There is yet another widget to hook USB to a TTL serial port, and holding a couple of data buttons and poking the “run” button will cause it to send “Hello World!” to your terminal.

Now is where the log leaps off the ground, new target: A fully programmable 9 bit processor, with a complete working front panel! Everything till now has been playing with the ATMEGA, now I have to teach the ATMEGA to pretend to be a 9 bit computer. All the software I have written has been in “C”, using AtmelStudio 7, available from the Microchip website. ( Microchip bought Atmel a few years back.)

What kind of a processor do I create? I could do a 9 bit PDP-8, but HP already did a 16 bit PDP-8 called the HP-1000 series. I poked around a bit, and eventually decided to roll my own, which I call “NineBitter”, kind of a mish-mash of the German word for No, and the taste. Anyway a bunch of coding and debugging ensued, but eventually I have a computer with:

  • 4 registers
  • 512 9 bit words of memory
  • 38 instructions
  • 3 register instructions
  • 4 I/O ports

I guess I need some programs to demonstrate that it works. I did some programming in binary, but that got pretty tedious fast, so I implemented an assembler in PERL. It has warts, but it mostly works. Its weakest point is error reporting. The first serious program I wrote with the assembler is the boot loader, and I found a way for it to be there in RAM whenever you power up or reset the board! To test it, I had it load another copy of itself, and used the front panel to verify that it was correct.

The next program I wrote was a game: Kill the Bit! That was one of the earliest games folks played on the Altair 8800. The idea is there is a bit rotating through the data lights, and your goal is to press the button below the bit to stop it. If you miss, you get another bit lit, chasing the first. Here is the program:

;*****************************************************
; Kill The Bit:
; Author: Bruce Sherry
; Date: 3/31/2020 2:41:19 PM
;
; Stomp the bit with the buttons as it rotates around!
;*****************************************************
start:  org     0120
        xor     R0,R0,R0        ; clear register R0
        addi    R0,R1           ; make a Bit
loop:   out     R0,leds         ; display the results
        addi    R2,19           ; load a delay count
deloop: subi    R2,1            ; wait a while
        jnz     deloop
        in      R1,switches     ; Read the switches into register 1
        xor     R0,R0,R1        ; flip the bits
        rl      R0              ; rotate the bit
        jnz     loop            ; go back for more
        halt                    ; you win!

A theme we have at LCM+L is “Hello World!” which comes from the “C Programming Language” manual by Kernighan and Ritchie. The first program in the book merely types “Hello World!” when you run it, so that program had to be written too:

;***********************************************************
; Hello World!:
; Author: Bruce Sherry
; Date: 4/21/2020 10:59:24 AM
;
; Say hi to the world on the other side of the serial port.
;***********************************************************
NL:     equ     012
CR:     equ     015
LF:     equ     012
start:  org     0120
        xor     R0,R0,R0            ; clear out the reg
        xor     R3,R3,R3
        addi    R3,message          ; get the start of the message
charloop:
        loadn   R1,R3,0             ; use reg 1 as temp
        addi    R3,1                ; step to the next location
        or      R2,R1,R1            ; set the flags, and save it in 2
        jz      done
        subi    R2,NL
        jz      newline
        out     R1,serial           ; send the character
        jmp     charloop
newline:
        sub     R2,R2,R2            ; clear 2
        ori     R2,CR
        out     R2,serial           ; send a carriage return
        out     R1,serial           ; and the line feed
        jmp     charloop
done:   halt
        jmp     start
message: string "Hello World!\n"

Most people (at least the ones that have seen “2001, A Space Odessy”) know that the first song a computer learns is “Daisy, Daisy”, so I taught NineBitter to play that.

You are probably wondering where the title of this blog entry came from. Another of the targets for this project to hit came from the idea that we could teach some computer science with this little thing. Besides having the ATMEGA and NineBitter, we needed Another architecture to play with.

A friend of mine, Bryan, sent me a link to an article called “Surprisingly Turing-Complete”, which sent me down a very deep rabbit hole, where I found a few pages about something called an OISC, or a One Instruction Set Computer. A computer with ONLY ONE instruction. It seems to be possible to make a computer without any instructions, but we will leave that as an excersise for the reader.

On one of the OISC pages I found http://mazonka.com/subleq/ which is about SUBLEQ, which stands for SUBtract and Branch if Less than or EQual to Zero. There is a Challenge! A SUBLEQ instruction uses 3 memory locations: <address1> <address2> <jump target>. The contents of the location pointed to by <address1>, is subtracted from the location pointed to by <address2>. The result is stored in <address2>, then if the result is less than or equal to zero the next instruction is taken from the <jump target> otherwise it is just the next location.

Here is the first program the papers describe:

0: 3 4 6
3: 7 7 7
6: 3 4 0

The number on the left, with the colon, is the address in memory, then we get the contents of 3 locations. The first instruction takes the contents of location 3, which is a 7, subtracts it from the contents of location 4, which is also a 7, leaving 0, which gets stored in location 4. Since the result is zero, it jumps to location 6.

Location 6 does the same thing, but instead jumps back to location 0, but this result is -7. Location 0 does it again with the result being -14, then location 6 changes it to -21. As long as the result is negative, everything is fine.

Most folks seem to implement a 32 bit version of SUBLEQ, so they don’t run into what happens when numbers change sign. In order to get it to run properly on my SUBLEQ processor, called “NinetyOne”, I had to change it to:

In SUBLEQ assembly:

# Loop Minus 7 Fixed
# had to add the two z z instructions to handle positive numbers
begin:  x y again
        z z again
        x:7 y:7 z:0
again:  x y begin
        z z begin

Which assembles to:

 0: 6 7 9
 3: 8 8 9
 6: 7 7 0
 9: 6 7 0
12: 8 8 0

I will let you peruse the various InterNet pages about SUBLEQ to understand what all that gobbledegook means. Another good page to look at is: https://esolangs.org/wiki/Subleq

Now the HARD part: I want to write KillTheBit, HelloWorld, and DaisyDaisy in SUBLEQ. For KillTheBit, I need an XOR operation, and getting boolean operations out of only Subtract is hurting my head! I need the I/O ports too, and I probably don’t have the emulation correct for that. I guess I just have to put my nose to the grindstone, my shoulder to the wheel, my eye on the ball, and try to figure this out in that position.

Let us know if you think owning your own Bit Token computer would be fun. It is looking like the kit might cost around $54.95.

If you have any suggestions or solutions, please let me know,

Bruce Sherry