LFSR CPU

This language consists of a Virtual Machine (VM) specification for a "weird" processor, and less of a language. What makes this processor weird is that instead of using a normal Program Counter (PC), one that increments with an adder to move to the next instruction, this processor uses a Linear Feedback Shift Register (LFSR) instead to move to the next instructions. This means instructions are executed in a Pseudo Random order and the execution order appears obfuscated or scrambled.

The language was create by howerj, much like Muxleq. An implementation in C is available at here and one that runs on an FPGA is at here.

This technique has been used in the past with real devices when gates and transistors were especially scarce. You can make a LFSR with fewer gates and (that operates at a faster speed) than with a normal Program Counter.

Despite this, this system is capable of running a full blown programming language, Forth.

The instruction layout is:

   +----------+---------------+-------------------+
   |  BIT 15  | BITS 12 to 14 |    BITS 0 to 11   |
   +----------+---------------+-------------------+
   | INDIRECT | INSTRUCTION   | VALUE   / ADDRESS |
   +----------+---------------+-------------------+

The INDIRECT flag determined whether bits 0 to 11 are treated as a value (not set) or an address (INDIRECT is set).

The INSTRUCTION field is 3-bits in size, the instructions are:

• 0 : XOR  : ACC = ACC ^ ARG
• 1 : AND  : ACC = ACC & ARG
• 2 : LLS1  : ACC = ARG << 1
• 3 : LRS1  : ACC = ARG >> 1
• 4 : LOAD  : ACC = MEM[ARG]
• 5 : STORE : MEM[ARG] = ACC
• 6 : JUMP  : PC = ARG
• 7 : JUMPZ : IF (ACC == 0) { PC = ARG }

The PC is only 8-bits in sizes and uses the polynomial 0xB8. A different polynomial results in a different execution order and maximum program size.

At least 0x1000 16-bit words are dedicated to the machine.

As the PC is only 8-bits in size the first 256 16-bit instructions are dedicated to implementing a VM that can be used to execute Forth, on top of which the Forth interpreter is built. The tool-chain for this system is written in Forth and is available here at here.