Common choices for the single instruction are: •
Subtract and branch if less than or equal to zero •
Subtract and branch if negative •
Subtract if positive else branch •
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, A 32-bit Subleq computer with a graphic display and a keyboard called
Izhora has been constructed by
Yoel Matveyev as a large
cellular automaton pattern.
Compilation There is a
compiler called
Higher Subleq written by Oleg Mazonka that compiles a simplified C program into code. Alternatively there is a self hosting
Forth implementation written by Richard James Howe that runs on top of a Subleq VM and is capable of interactive programming of the Subleq machine
Subtract and branch if negative The instruction ("
subtract and branch if negative"), also called , is defined similarly to : In order to keep all numbers positive and mimic a human operator computing on a real world abacus, the test is performed before any subtraction. Pseudocode:
Instruction melzak X, Y, Z, n, y
if (Mem[X] multiply: melzak P, ONE, S, stop ; Move 1 counter from P to S. If not possible, move to stop. melzak S, Q, ANS, multiply, multiply ; Move q counters from S to ANS. Move to the first instruction. stop: where the memory location P is
p, Q is
q, ONE is 1, ANS is initially 0 and at the end
pq, and S is a large number. He mentions that it can easily be shown using the elements of recursive functions that every number calculable on the arithmetic machine is computable. A proof of which was given by Lambek on an equivalent two instruction machine : X+ (increment X) and X− else T (decrement X if it not empty, else jump to T).
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.
Instruction rssb x ACCUM = Mem[x] - ACCUM Mem[x] = ACCUM
if (ACCUM • First, move z to the destination location x. RSSB temp # Three instructions required to clear acc, temp [See Note 1] RSSB temp RSSB temp RSSB x # Two instructions clear acc, x, since acc is already clear RSSB x RSSB y # Load y into acc: no borrow RSSB temp # Store -y into acc, temp: always borrow and skip RSSB temp # Skipped RSSB x # Store y into x, acc • Second, perform the operation. RSSB temp # Three instructions required to clear acc, temp RSSB temp RSSB temp RSSB z # Load z RSSB x # x = y - z [See Note 2] • [Note 1] If the value stored at "temp" is initially a negative value and the instruction that executed right before the first "RSSB temp" in this routine borrowed, then four "RSSB temp" instructions will be required for the routine to work. • [Note 2] If the value stored at "z" is initially a negative value then the final "RSSB x" will be skipped and thus the routine will not work.
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 combining with the current content of the new location:
Instruction movx a, b (also written
a ->
b) OP = GetOperation(Mem[
b]) Mem[
b] := OP(Mem[
a], Mem[
b]) The operation performed is defined by the destination memory cell. Some cells are specialized in addition, some other in multiplication, etc. So memory cells are not simple store but coupled with an
arithmetic logic unit (ALU) setup to perform only one sort of operation with the current value of the cell. Some of the cells are
control flow instructions to alter the program execution with jumps,
conditional execution,
subroutines,
if-then-else,
for-loop, etc... 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 similar to Subleq. It consists of one
eponymous instruction and is capable of performing general-purpose computation on encrypted programs. Cryptoleq works on continuous cells of memory using direct and indirect addressing, and performs two operations and on three values A, B, and C:
Instruction cryptoleq a, b, c Mem[b] = O1(Mem[a], Mem[b])
if O2(Mem[b]) ≤ 0 IP = c
else IP = IP + 3 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 and are defined as follows: :\begin{array}{lcl} O_1(x,y) & = & x^{-1} y \,\bmod\, N^2 \end{array} :\begin{array}{lcl} O_2(x) & = & \left \lfloor \frac{x-1}{N} \right \rfloor \end{array} The main difference with Subleq is that in Subleq, simply subtracts from and equals to . Cryptoleq is also homomorphic to Subleq, modular inversion and multiplication is homomorphic to subtraction and the operation of corresponds the Subleq test if the values were unencrypted. A program written in Subleq can run on a Cryptoleq machine, meaning backwards compatibility. However, Cryptoleq implements fully homomorphic calculations and is capable of 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 operation: :G(x,y) = \begin{cases} \tilde{0}, & \text{if }O_2(\bar{x})\text{ }\leq 0 \\ \tilde{y}, & \text{otherwise} \end{cases} where \tilde{y} is the re-encrypted value of and \tilde{0} is encrypted zero. is the encrypted value of a variable, let it be , and \bar{x} equals . 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. == See also ==