brainfuck-cpu

This repo contains a Logisim schematic file for a programmable circuit implementing a 24-bit-datapath 24-bit-mempath Brainfuck computer.

Structure:

• main: contains everything that functions as a "complete" "computer", including:
  • 1 24-bit ROM: contains 4-bit units of data. In each unit, bits 2:0 are encoded as BFC instructions. See the encoding specification below. Bit 3 is the special "shutdown" signal that hangs the clock.
  • 1 24-bit RAM: contains 8-bit units of data, serving as the memory byte array for the Brainfuck environment.
  • 1 main clock: the clock that regulates the synchronization of the whole system. This implementation should be synchronous
  • 1 stdin ROM: a counter+ROM complex providing the stdin pipe for the Brainfuck environment. It reads bytes from its ROM backend, incrementing the address when the CPU signals that a byte has been read.
  • 1 stdout RAM: a counter+RAM complex providing the stdout pipe for the Brainfuck environment. It appends bytes to its RAM backend.
  • 1 CPU: the instruction processor
• brainfuck/cpu:
  • Inputs:
    • clk (boolean): for synchronization with the main clock
    • instr (instr_size): current instruction to execute
    • instr_ptr (datapath_size): the pointer to the current instruction
    • mem (cell_size): the value of the current memory cell
    • mem_ptr (mempath_size): the pointer to the current memory cell
    • stdin (cell_size): the stdin value to read, if needed
  • Outputs:
    • instr_ptr (datapath_size): the pointer to the next instruction
    • mem_ptr (mempath_size): the pointer to the next memory cell
    • writing_mem (boolean): a boolean indicating whether the current memory cell should be updated to set_mem (according to the Brainfuck language, an instruction that updates a memory cell would not update the memory pointer, so it is not necessary to distinguish it as the cell before or the cell after the instruction)
    • set_mem (cell_size): the value to be set into memory if writing_mem is 1
    • stdout_ready (boolean): a boolean indicating whether the "stdout" output should be appended to the stdout pipe
    • stdout (cell_size): the value to be appended to the stdout pipe if stdout_ready is 1
    • stdin_read (boolean): a boolean indicating whether a new cell should be pulled from the stdin pipe, i.e. the current one has been consumed
  • Internal registers:
    • a 6-bit counter used for finding the matching ] when [ is executed with memory 0 (i.e. a while loop has broken)
    • a Register24Stack64 subcircuit for storing pointers to previous [ instructions.
• Register24Stack64:
  • Uses a 6-bit-mempath 24-bit-cell RAM
  • Implements a first-in-last-out "stack" data structure for 24-bit data cells
  • Has 3 valid input combinations:
    • ~push & ~pop: PEEK action, not modifying the RAM. Outputs the tail entry (last-inserted entry) in the stack.
    • push & ~pop: PUSH action, appending insert_data to the stack. Output is undefined.
    • ~push & pop: POP action, removing the last-inserted entry from the stack. Output is undefined.
  • Needs formal proof to determine if brainfuck/cpu might experience bugs due to a PUSH/POP action not being able to output the tail value in the same tick. If issues exist, may need doueble-ticking.

BFC 3-bit encoding

BFC means "Brainfuck compiled". It is a simple mapping of Brainfuck instructions into 3-bit units. The following bitsets correspond to symbolic instructions in the Brainfuck language:

Bitset (2:0)	Symbol	Synopsis
000	>	Increments the memory pointer
001	<	Decrements the memory pointer
010	+	Increments the memory value
011	-	Decrements the memory value
100	.	Sends the current memory value to stdout
101	,	Consumes the current stdin value and stores it in the current memory value
110	[	If current memory value is 0, skips to the matching ] behind, which is not necessarily the immediately following one
111	]	If current memory value is not 0, jumps back to the matching [ before

Memory allocation

• boolean: 1 bit
• instr_size: 3 bits
• datapath_size: 24 bits
• mempath_size: 24 bits
• cell_size: 8 bits

Synchronization

The whole circuit is currently synchronous with the same main clock. However, constraints in stdin and Register24Stack64 may require double-ticking. Formal proof is required to confirm.

RESET

This implementation defines that all memory cells start at 0.

The bfc utility

bfc.cpp is a standalone C++ file that can be compiled to build Brainfuck programs.

Accepting the argument FILE_BASENAME, bfc will parse the {FILE_BASENAME}.bf file

Then it will emit the following files:

• {FILE_BASENAME}.min.bf: The syntactically minified Brainfuck program code, i.e. only instruction bytes are left.
• {FILE_BASENAME}.bfc: The Brainfuck code is compiled into binary form, equivalent what is loaded inside the instruction ROM. The higher 4 bits (7:4) are unused. Bit 3 is the shutdown bit. The lower 3 bits (2:0) are BFC-encoded instructions.
• {FILE_BASENAME}.bfc.txt: The BFC file converted into plaintext, compatible with Logisim ROM imports.