QFTASM

Quest for Tetris Assembly is a form of assembly primarily used as part of the Quest for Tetris project, the goal of which is to build a computer inside of Conway's Game of Life capable of running Tetris.

Architecture Overview

Rough diagram of the processor architecture.

The QFTASM processor uses a 16-bit RISC Harvard architecture. "RISC" in this case means that all instruction types perform simple operations and are executed in a very similar manner. "Harvard" in this case means that all program instructions are stored in ROM and all processable data is stored in RAM. The program counter (PC) is memory-mapped to RAM address 0, and other than that all RAM addresses are created equal. There are no special internal registers that need to be loaded to, any instruction can be performed on any address.

Like many simple RISC architectures, there is a branch delay slot, meaning that the command immediately after a jump is executed regardless of whether the jump is taken. Additionally, jumps occur to the line immediately after the line number specified as an operand. This is a result of the instruction pipeline:

1. Read the data for the current instruction's arguments from RAM
2. Increment the program counter
3. Fetch the next instruction from ROM
4. Write the result (if necessary) of the current instruction to RAM

The processor is also asynchronous, meaning that there is no central clock. Rather, a "clock signal" travels in parallel with the data, which indicates when data is arriving. This considerably simplified the timing of the processor.

Language Documentation

Any QFTASM program is written as a series of instructions, one per line. Each instruction corresponds to a single complete cycle of the CPU.

Each instruction should be formatted like this:

    [line numbering] [opcode] [arg1] [arg2] [arg3]; [optional comment]

When translated to machine code, the opcode is 4 bits, and each argument is 18 bits (2 bits addressing mode + 16 bits data). Additionally on the physical processor the opcode is placed after the arguments.

Opcode List

Here is a list of instructions along with their arguments, as listed by the online interpreter.

   MNZ [test] [value] [dest]  – Move if not zero; sets [dest] to [value] if [test] is not zero.
   MLZ [test] [value] [dest]  – Move if less than zero; sets [dest] to [value] if [test] is less than zero.
   ADD [val1] [val2] [dest]   – Add; adds [val1] to [val2] and stores the result in [dest].
   SUB [val1] [val2] [dest]   – Subtract; subtracts [val2] from [val1] and stores the result in [dest].
   AND [val1] [val2] [dest]   – Bitwise AND; bitwise ANDs together [val1] and [val2] and stores the result in [dest].
   OR [val1] [val2] [dest]    – Bitwise OR; bitwise ORs together [val1] and [val2] and stores the result in [dest].
   XOR [val1] [val2] [dest]   – Bitwise XOR; bitwise XORs together [val1] and [val2] and stores the result in [dest].
   ANT [val1] [val2] [dest]   – Bitwise AND-NOT; bitwise ANDs together [val1] and (NOT [val2]) and stores the result in [dest].
   SL [val1] [val2] [dest]    – Shift left; shifts [val1] left by [val2] bits and stores the result in [dest].
   SRL [val1] [val2] [dest]   – Shift right (logical); shifts [val1] right by [val2] bits and stores the result in [dest]. Doesn't preserve sign.

There is one additional instruction that is supported by the interpreters but is not physically supported on the processor:

   SRA [val1] [val2] [dest]   – Shift right (arithmetic); shifts [val1] right by [val2] bits and stores the result in [dest], while preserving sign.

Addressing Modes

Each of the three operands of an instruction has an addressing mode, which is usually indicated by a 1-letter prefix before the value of the operand. This mode is physically implemented as a 2-bit counter indicating the number of times the value of the operand should be sent around a RAM read loop.

• Mode 0 is used for any constant hardcoded into RAM, and is written without a prefix. For example, ADD 4 5 6 always stores the value 9 in RAM location 6.

• Mode 1 is used for single-dereferencing, and is written with prefix A. For example, ADD A7 A8 A9 reads the contents of RAM location 7 and location 8, and adds those values, placing the result in the location determined by the contents of location 9. The code ADD A2 1 2 increments the value in location 2. This mode is useful for reading from single-word variables and writing to arrays/stacks.

• Mode 2 is double-dereferencing and uses the prefix B. It is useful for reading from arrays/stacks.

• Mode 3 is triple-dereferencing and uses the prefix C.

Jumps

In order to conserve opcodes and maintain a simple processor design, the two conditional move commands (MNZ and MLZ) are used for conditional absolute jumps as well. Any command that writes to RAM location 0 serves as a jump, so ADD and SUB can serve as unconditional relative jumps.

Compilers

A few compiler projects are underway. The first attempt for a higher-level language was Cogol, and since then development has shifted to a more complex higher-level language. There is also ongoing work on a potential LLVM backend.

Example Code

Compute primes via trial subtraction:

   0. MLZ -1 3 3;
   1. MLZ -1 7 6; preloadCallStack
   2. MLZ -1 2 1; beginDoWhile0_infinite_loop
   3. MLZ -1 1 4; beginDoWhile1_trials
   4. ADD A4 2 4;
   5. MLZ -1 A3 5; beginDoWhile2_repeated_subtraction
   6. SUB A5 A4 5;
   7. SUB 0 A5 2;
   8. MLZ A2 5 0;
   9. MLZ 0 0 0; endDoWhile2_repeated_subtraction
   10. MLZ A5 3 0;
   11. MLZ 0 0 0; endDoWhile1_trials
   12. SUB A4 A3 2;
   13. MNZ A2 15 0; beginIf3_prime_found
   14. MLZ 0 0 0;
   15. MLZ -1 A3 1; endIf3_prime_found
   16. ADD A3 2 3;
   17. MLZ -1 3 0; 
   18. MLZ -1 1 4; endDoWhile0_infinite_loop

This was compiled from the following Cogol source code:

   # Computes prime numbers by trial subtraction
   display = 2;
   my candidate = 3;
   my divisor;
   my remainder;
   do infinite loop {
     divisor = 1;
     do trials {
       divisor += 2;
       remainder = candidate;
       do repeated subtraction {
         remainder -= divisor;
       } while (remainder > 0);
     } while (remainder < 0);
     if (divisor == candidate) prime found {
       display = candidate;
     }
     candidate += 2;
   } while (1);

Resources

Online interpreter by El'endia Starman.

GitHub organization with repositories for the interpreter, some compilers, and the actual processor.