One instruction set computer

Machine architecture

In a Turing-complete model, each memory location can store an arbitrary integer, and—depending on the model—there may be arbitrarily many locations. The instructions themselves reside in memory as a sequence of such integers.

There exists a class of universal computers with one instruction based on bit manipulation such as bit copying or bit inversion. Since their memory model is the same as the memory structure used in real computers, those bit manipulation machines are equivalent to real computers rather than to Turing machines.

Currently known OISCs can be roughly separated into three broad categories:

Bit-manipulating machines

Transport Triggered Architecture machines

Arithmetic-based Turing-Complete machines

Bit-manipulating machines

Bit-manipulating machines are the simplest class.

BitBitJump

A bit copying machine, called BitBitJump, copies one bit in memory and passes the execution unconditionally to the address specified by one of the operands of the instruction. This process turns out to be capable of universal computation (i.e. being able to execute any algorithm and to interpret any other universal machine) because copying bits can conditionally modify the code that will be subsequently executed.

Toga computer

Another machine, called the Toga computer, inverts a bit and passes the execution conditionally depending on the result of inversion.

Multi-bit copying machine

Yet another bit operating machine, similar to BitBitJump, copies several bits at the same time. The problem of computational universality is solved in this case by keeping predefined jump tables in the memory.

Transport Triggered Architecture

Transport Triggered Architecture (TTA) is a design in which computation is a side effect of data transport. Usually, some memory registers (triggering ports) within common address space perform an assigned operation when the instruction references them. For example, in an OISC using a single memory-to-memory copy instruction, this is done by triggering ports that perform arithmetic and instruction pointer jumps when written to.

Arithmetic-based Turing-complete machines

Arithmetic-based Turing-complete machines use an arithmetic operation and a conditional jump. Unlike the two previous universal computers, this class is also Turing-complete. The instruction operates on integers which may also be addresses in memory.

Currently there are several known OISCs of this class, based on different arithmetic operations:

addition (Addleq)

decrement (DJN)

increment (P1eq)

subtraction (Subleq).

The latter is the oldest, the most popular and, arguably, the most efficient.

Instruction types

Common choices for the single instruction are:

Subtract and branch if less than or equal to zero

Subtract and branch if negative

Reverse subtract and skip if borrow

Move (used as part of a transport triggered architecture)

Subtract and branch if non zero (SBNZ a, b, c, destination)

Cryptoleq (heterogeneous encrypted and unencrypted computation)

Only one of these instructions is used in a given implementation. Hence, there is no need for an opcode to identify which instruction to execute; the choice of instruction is inherent in the design of the machine, and an OISC is typically named after the instruction it uses (e.g., an SBN OISC, the SUBLEQ language, etc.). Each of the above instructions can be used to construct a Turing-complete OISC.

This article presents only subtraction-based instructions among those that are not transport triggered. However, it is possible to construct Turing complete machines using an instruction based on other arithmetic operations, e.g., addition. For example, one variation known as DLN (Decrement and jump if not zero) has only two operands and uses decrement as the base operation. For more information see Subleq derivative languages [1].

Subtract and branch if not equal to zero

The SBNZ a, b, c, d instruction ("Subtract and Branch if Not equal to Zero") subtracts the contents at address a from the contents at address b, stores the result at address c, and then, if the result is not 0, transfers control to address d (if the result is equal zero, execution proceeds to the next instruction in sequence).

Subtract and branch if less than or equal to zero

The subleq instruction ("SUbtract and Branch if Less than or EQual to zero") subtracts the contents at address a from the contents at address b, stores the result at address b, and then, if the result is not positive, transfers control to address c (if the result is positive, execution proceeds to the next instruction in sequence).

Pseudocode:

Conditional branching can be suppressed by setting the third operand equal to the address of the next instruction in sequence. If the third operand is not written, this suppression is implied.

A variant is also possible with two operands and an internal accumulator, where the accumulator is subtracted from the memory location specified by the first operand. The result is stored in both the accumulator and the memory location, and the second operand specifies the branch address:

Although this uses only two (instead of three) operands per instruction, correspondingly more instructions are then needed to effect various logical operations.

Synthesized instructions

It is possible to synthesize many types of higher-order instructions using only the subleq instruction.

Unconditional branch:

JMP c 

Addition can be performed by repeated subtraction, with no conditional branching; e.g., the following instructions result in the content at location a being added to the content at location b:

ADD a, b 

The first instruction subtracts the content at location a from the content at location Z (which is 0) and stores the result (which is the negative of the content at a) in location Z. The second instruction subtracts this result from b, storing in b this difference (which is now the sum of the contents originally at a and b); the third instruction restores the value 0 to Z.

A copy instruction can be implemented similarly; e.g., the following instructions result in the content at location b getting replaced by the content at location a, again assuming the content at location Z is maintained as 0:

MOV a, b 

Any desired arithmetic test can be built. For example, a branch-if-zero condition can be assembled from the following instructions:

BEQ b, c 

Subleq2 can also be used to synthesize higher-order instructions, although it generally requires more operations for a given task. For example, no fewer than 10 subleq2 instructions are required to flip all the bits in a given byte:

NOT a 

Emulation

The following program (written in pseudocode) emulates the execution of a subleq-based OISC:

This program assumes that memory[] is indexed by nonnegative integers. Consequently, for a subleq instruction (a, b, c), the program interprets a < 0, b < 0, or an executed branch to c < 0 as a halting condition. Similar interpreters written in a subleq-based language (i.e., self-interpreters, which may use self-modifying code as allowed by the nature of the subleq instruction) can be found in the external links below.

Compilation

There is a compiler called Higher Subleq written by Oleg Mazonka that compiles a simplified C program into subleq code.

Subtract and branch if negative

The subneg instruction ("SUbtract and Branch if NEGative"), also called SBN, is defined similarly to subleq:

Conditional branching can be suppressed by setting the third operand equal to the address of the next instruction in sequence. If the third operand is not written, this suppression is implied.

Synthesized instructions

It is possible to synthesize many types of higher-order instructions using only the subneg instruction. For simplicity, only one synthesized instruction is shown here to illustrate the difference between subleq and subneg.

Unconditional branch:

JMP c

where Z and POS are locations previously set to contain 0 and a positive integer, respectively;

Unconditional branching is assured only if Z initially contains 0 (or a value less than the integer stored in POS). A follow-up instruction is required to clear Z after the branching, assuming that the content of Z must be maintained as 0.

Reverse subtract and skip if borrow

In a Reverse Subtract and Skip if Borrow (RSSB) instruction, the accumulator is subtracted from the memory location and the next instruction is skipped if there was a borrow (memory location was smaller than the accumulator). The result is stored in both the accumulator and the memory location. The program counter is mapped to memory location 0. The accumulator is mapped to memory location 1.

Example

To set x to the value of y minus z:

Transport triggered architecture

A transport triggered architecture uses only the move instruction, hence it was originally called a "move machine". This instruction moves the contents of one memory location to another memory location:

move a to b ; Mem[b] := Mem[a]

sometimes written as:

a -> b ; Mem[b] := Mem[a]

Arithmetic is performed using a memory-mapped arithmetic logic unit and jumps are performed using a memory-mapped program counter.

A commercial transport triggered architecture microcontroller has been produced called MAXQ, which hides the apparent inconvenience of an OISC by using a "transfer map" that represents all possible destinations for the move instructions.

Cryptoleq

Cryptoleq is a language consisting of one, the eponymous, instruction, is capable of performing general-purpose computation on encrypted programs and is a close relative to Subleq. Cryptoleq works on continuous cells of memory using direct and indirect addressing, and performs two operations O₁ and O₂ on three values A, B, and C:

Cryptoleq a, b, c [b] = O₁([a],[b]) ; IP = c, if O₂[b] ≤ 0 IP = IP + 3, otherwise

where a, b and c are addressed by the instruction pointer, IP, with the value of IP addressing a, IP + 1 point to b and IP + 2 to c.

In Cryptoleq operations O₁ and O₂ are defined as follows:

O 1 ( x , y ) = x N 2 − 1 y mod N 2 O 2 ( x ) = ⌊ x − 1 N ⌋

The main difference with Subleq is that in Subleq, O₁(x,y) simply subtracts y from x and O₂(x) equals to x. Cryptoleq is also homomorphic to Subleq, modular inversion and multiplication is homomorphic to subtraction and the operation of O₂ corresponds the Subleq test if the values were unencrypted. A program written in Subleq can run on a Cryptoleq machine, meaning backwards compatibility. Cryptoleq though, implements fully homomorphic calculations and since the model is be able to do multiplications. Multiplication on an encrypted domain is assisted by a unique function G that is assumed to be difficult to reverse engineer and allows re-encryption of a value based on the O₂ operation:

G ( x , y ) = { 0 ~ , if  O 2 ( x ¯ )   ≤ 0 y ~ , otherwise

where y ~ is the re-encrypted value of y and 0 ~ is encrypted zero. x is the encrypted value of a variable, let it be m, and x ¯ equals N m + 1 .

The multiplication algorithm is based on addition and subtraction, uses the function G and does not have conditional jumps nor branches. Cryptoleq encryption is based on Paillier cryptosystem.