The QSIS-16

The Quite Simple Instruction Set (16-bit) is an instruction set architecture for a custom reduced instruction set computer. It has a word size of 16 bits and is intentionally designed to be very limited in terms of the functionality the processor/assembler provides out of the box: its goal is to provoke computational thinking in reducing a problem down to this limited set of operations, with the set of operations themselves being easy to understand.

Interface

This web interface allows a user to write code that is then assembled and emulated by the server. It's written in Rust and uses Microsoft's Monaco editor, plus a bit of JavaScript and HTML (using Bootstrap) to submit code to the server and display the various panels. This is the information panel, to the right is the code window and on the far right is the output. Have a go running the example program - it prints the prime numbers below 100. Change the green number on line 2 to increase the upper limit it searches in.

Code is autosaved so that when you return to the site you can pick up where you left off. Be sure to use the Save/Load file buttons for big projects, though. Toggle dark theme using the moon crescent button, and run code either with Alt+Enter or the button.

Challenge Ideas

  • Count from 1 to 10
  • Output the powers of 2 below a limit
  • Output the Fibonacci numbers below a limit
  • Print the first N square numbers
  • Print the first N triangle numbers
  • Find the integer square root of a given number
  • Print the factors of a given number
  • By copying the program counter, implement the concept of subroutines

Instructions

Instructions can have up to 3 parameters. If the parameter begins with a $, it requires a register so use a $ followed by a register identifier. If there's no $, use a number between 0 and 15 inclusive - this is called an immediate. Such a number can be expressed using a series of digits: if prefixed by 0b then they are treated as binary, if prefixed by 0x they are treated as hexadecimal. Otherwise they're treated as a regular decimal number.

There are three types of registers that you can use:

  • General purpose: $a-$m inclusive. Like a variable.
  • Zero register: $0. Always contains the value 0 and storing to it silently fails.
  • Program counter: $pc. Contains the address of the next instruction to be executed.

Arithmetic Operations

add $x $y $z

$z = $x + $y

Take the value in register X, add the value in register Y and store the result in register Z.

mul $x $y $z

$z = ($x * $y) & 0xffff

Take the value in register X, multiply by the value in register Y and store the lower 16 bits of the result in register Z.

mulh $x $y $z

$z = ($x * $y) >> 16

Take the value in register X, multiply by the value in register Y and store the upper 16 bits of the result in register Z.

div $x $y $z

$z = $x / $y

Take the value in register X, integer divide by the value in register Y and store the result in register Z.

mod $x $y $z

$z = $x % $y

Take the value in register X, divide by the value in register Y and store the remainder in register Z.

Immediate Arithmetic Operations

addi y $z

$z += y

Take the value in register Z and add the number Y, storing in register Z.

subi y $z

$z += y

Take the value in register Z and subtract the number Y, storing in register Z.

shl y $z

$z <<= y

Take the value in register Z and shift left by the number Y, store back in register Z.

shr y $z

$z <<= y

Take the value in register Z and shift right by the number Y, store back in register Z.

rol y $z

$z <<= y (rot)

Take the value in register Z and rotate left by the number Y, store back in register Z.

ror y $z

$z >>= y (rot)

Take the value in register Z and rotate right by the number Y, storing in register Z.

neg $z

$z = (¬$z) + 1

Perform a two's complement negation of the value in register Z, storing in register Z.

Logical Operations

or $x $y $z

$z = $x | $y

Take the value in register X, bitwise OR by the value in register Y and store the result in register Z.

xor $x $y $z

$z = $x ^ $y

Take the value in register X, bitwise XOR by the value in register Y and store the result in register Z.

and $x $y $z

$z = $x & $y

Take the value in register X, bitwise AND by the value in register Y and store the result in register Z.

not $z

$z = ¬$z

Perform a bitwise NOT on the value of register Z and store the result in register Z.

Data Processing Operations

ld $x y $z

$z = MEM[$x + y]

Add the value in register X to the number Y. Fetch the data at that address in memory and store in register Z.

sto $x y $z

MEM[$x + y] = $z

Add the value in register X to the number Y. Store the value of register Z at that address in memory.

imm y $z

$z = y

Store the number Y in register Z. Important: this instruction is an exception to the 0-15 number requirement. Here, the number Y can be up to 16 bits (or 0-65535 inclusive) OR it can be a label, in which case the address of the label will be stored.

mov $y $z

$z = $y

Copy the value in register Y to register Z.

out $z

print(Itoa($z))

Print out the value in register Z as a number.

Control Flow Operations

nop

{}

Do nothing (reserved for future use).

hlt

exit()

Halt execution, end the program.

beq $x $y [label]

if ($x == $y) $pc = [label]

If the value in register X is equal to the value in register Y, jump to the label specified and continue the program from there.

blt $x $y [label]

if ($x < $y) $pc = [label]

If the value in register X is less than the value in register Y, jump to the label specified and continue the program from there.

jmp [label]

$pc = [label]

Jump to the label specified and continue the program from there.

Labels

A label is a human-readable address of a particular instruction. You can code a label like this: .[label]: on its own line, directly before the instruction you want to label. When the program is assembled, the assembler will replace the label with the address of that particular instruction. This way, you can jump to a point in a program without having to calculate the address it will end up at: just use the label. For example:
.loop:
  nop
  jmp loop
Is an infinite loop. Note that whitespace is ignored but adding a tab before instructions looks better.

5 plus 3

  1.   imm 5 $a
  2.   imm 3 $b
  3.   add $a $b $c
  4.   sto $pc 1 $c
  5.   hlt
  6.   nop

First, we load the value 5 into register A and the value 3 into register B. On line 3, we take the value in register A and add it to the value in register B, storing the result (which happens to be 8) in register C. Then, we store the value in register C in the memory address $pc + 1 (which is on line 6, as the $pc will point to line 5 as it's the next instruction to be executed). Finally, we stop execution. If we were to examine the memory after this program has been run, we'd find that line 6 wouldn't contain the code for a nop: it would contain the value 8.

Zeta's prime finder

  1.   imm 3 $a
  2.   imm 2 $b
  3.   imm 0 $c
  4.   imm 100 $e
  5.   out $b
    .testprm:
  6.   mod $a $b $d
  7.   beq $d $0 newprm
  8.   addi 1 $b
  9.   beq $a $b outprm
  10.   jmp testprm
    .outprm:
  11.   out $a
    .newprm:
  12.   addi 1 $a
  13.   imm 2 $b
  14.   blt $a $e testprm
  15.   hlt

First, we load some values into various registers. A contains 3, B contains 2, C contains 0 (although registers always start at 0) and E contains 100. We output the value of B so the first line of output is the nuber 2, our first prime.
We now enter the testprm routine. We take the value in A and divide it by the value in B, storing the remainder in D. In this routine, A is the prime number candidate we're testing and B will have all the numbers we test it with. If any of those numbers wholly divide A, then A must not be a prime. Therefore, on line 7, if the remainder was 0 (if D is equal to the zero register) we jump to the newprm routine. If this wasn't the case, we're just going to continue on to line 8 and add the value 1 to B (the number we check with).
However, if the number we check with is now equal to the number we're checking (line 9: A == B) we know we have a prime number: if it had factors we would have broken out of this testprm loop before using line 7. So we can jump to the outprm routine. If not, we have to keep checking with the new value of B so we jump back to testprm.
The outprm routine simply outputs the prime number candidate in A. It then continues to line 12 and into the newprm routine (labels don't stop programs from continuing to execute), where we add the value 1 to A: we're now testing the next number up to see if it's prime. We reset B to 2 and we go back to testprm if our new prime number candidate is lower than our limit in E. If it's not lower, then the processor halt.
Note: This is the same algorithm as the default program loaded in the code editor, but implemented in a more concise way.

Nim's subroutine PoC

  1.   imm 81 $m
  2.   mov $m $g
  3.   mov $pc $f
  4.   addi 2 $f
  5.   jmp sqrt
  6.   out $j
  7.   hlt
    .sqrt:
  8.   imm 0 $h
  9.   imm 1 $i
  10.   imm 0 $j
    .loopsqrt:
  11.   add $h $i $h
  12.   addi 2 $i
  13.   addi 1 $j
  14.   blt $h $g loopsqrt
  15.   mov $f $pc

The first line loads the value we want to square root into register M. Then, M is copied to G and the program counter is copied into register F. F is incremented by two to skip over the jmp instruction (since it is double width, see the Advanced tab): this program was made before v0.2.0 in which labels were added as a valid argument to immediate, so having to manually set the return pointer should not be needed. Then we jump to the sqrt label: which is our subroutine. We can consider the content of register G to be the argument to the subroutine - and on line 2 our input was indeed copied to register G. The content of F is the return pointer.

In the subroutine sqrt, registers H = 0, I = 1 and J = 0. Then the loopsqrt section is entered: lines 12 and 13 create a sequence of the square numbers in register H and register J tracks the square root of H. If H is less than the number we want to square root we loop, otherwise the stored address is moved back into the program counter and execution continues. That jumps to line 6, we output the result, and halt.

Notes

The imm instruction is double width to allow a full 16 bit value to be loaded into a register. beq, blt and jmp are technically pseudo-instructions provided by the assembler: jmp is an imm into the $pc and the two branches are actually two instructions each: an imm into a temporary register (it's $n which I haven't said you can use, explore it if you want) followed by the branch instruction which is like a conditional mov into the $pc.

Source code is available on GitHub, where you can also download assembler and emulator binaries. Briefly, the assembler takes a filename and writes a machine code file called a.out, and the emulator takes a file name of the machine code file to run and writes to stdout. Additional debugging output is provided such as memory and register dumps.

I've set an execution cap of 5 million cycles for running code online - there is no such limit if you run the emulator locally. Output is also trimmed online if it's longer than 10k characters.

Next steps

  • Better debugging messages
  • Separation of program output to debug messages
  • Ability to take input
  • More assembler directives like storing data
  • Assembler to set up a stack and offer pop/push/ret/jsr instructions
  • Printing null-terminated ASCII strings in memory
  • Assemble and emulate in WASM

Not next steps

  • Increase word size: there's a good challenge in making programs work with this small constraint
  • Floating point operations: keep it simple. User can code them if they wish
  • Threading: I want this to stay close to von Neumann
  • Breadboard version: it would be cool, but money doesn't grow on trees
  • X86 $a $b: I'm sorry Dave, I'm afraid I can't do that


Thank you to my long-suffering friends in CD who put up with my stupid web development questions.

0.2.3

  • Makes code and theme choice persistent in local storage
  • Adds Alt+Enter as a shortcut to run code
  • Updates Cargo dependencies to patch vulnerabilities

0.2.2

  • Major: Allows numerical values to be expressed using a prefix of 0b for binary and 0x for hexadecimal
  • Adds dark theme
  • Adds a button to load code from a file
  • Increases execution cap to 5 million instructions

0.2.1

  • Fixes errors when writing memory not yet initialised
  • Adds to Examples section
  • Updates imm description with label feature
  • Repo fixes: make Rust Cargo files use this version, add README, stop using CRLF, add favicon

0.2.0

  • Major: Allows addressing of memory outside of code section, up to 0xFFFF
  • Major: Allows imm instruction to take a label as the value
  • Enforces labels being non-numeric
  • Improves error messages
  • Adds Changelog section
  • Fixes typos and grammatical errors

0.1.0

Initial release.