BrainFucker: Homebrew Processor That Runs BrainFuck As Assembly

[straight_stewie]

[4/22/17] Just for giggles, I've decided that I want to build a homebrew processor that runs BrainFuck as it's assembly language. This thread will be kind of like a build log for this project. Updates to this thread may be sporadic, but I will update atleast every Saturday night (or Sunday morning).

 

 So far I have a working high level state machine and some architecture diagrams. I have not completed the controller design yet, although I have completed the Instruction Path and Data Path component designs. The designs I have now are not as optimized as they could be (for example, I could completely get rid of the Data Memory Address Register, this would save one register, but also save 5 states). There is a list of planned optimizations that will appear in a later update once I have "finalized" it.

First, some notes on BrainFuck. 

Spoiler

BrainFuck is a Turing Complete esoteric programming language (just for fun or challenge) language. The language gives you 8 instructions, an array of 30,000 unsigned bytes, and a pointer into the array. All characters that are not explicit instructions are ignored. The instructions are:

• > Increment the data pointer
• < Decrement the data pointer
• + Increment the data at the pointer
• - Decrement the data at the pointer
• . Output the byte at the pointer
• , Input a byte to the pointer
• [ If the byte at the pointer is zero, jump to the instruction after the matching ]. Otherwise, execute the following instruction (Also known as branch if zero)
• ] Jump back to the matching [

Here is a simple code example that demos addition and subtraction of user input numbers.

,>,<[->+<]. Addition of two numbers

,>,<[->-<]. Subtraction of two numbers

Here is an online BrainFuck interpreter that you can use to experiment with the language if you like: Online BrainFuck Visualizer

There is currently one modification that I have made to the standard definition of BrainFuck. Firstly, following every [ instruction are two bytes that represent the address of the matching ] instruction. This number must have one added to it to obtain the correct address of the next instruction to run, but this happens when the program counter is incremented during the fetch cycle. 

Following is a write up which specifies the steps that must be taken to execute each instruction, what the Instruction Path has, what the Data Path has, what the Controller (currently incomplete) has, as well as the master high level state machine diagram and architecture diagrams for the Instruction Path and Data Path.

Spoiler

Notes

• This is a Harvard Architecture Machine. Instructions are stored in a ROM, data is stored in a RAM.
• It looks like this:

 

Instruction Path Architecture and Description

• Components
  • Data ROM
  • Program Counter
  • Instruction Memory Address Register
  • Instruction Decoder
  • Stack
  • Address Builder
  • Address Incrementor/Decrementor
• Outputs
  • Instruction Decoder Byte (Ordered as bits in the following order): ><+-.,[]
• Inputs
  • Program Counter Increment
  • Program Counter Set
  • Program Counter Out Enable
  • Instruction Memory Address Register Set
  • Data ROM Out Enable
  • Instruction Decoder Set
  • Stack Push
  • Stack Pop
  • Address Incrementor/Decrementor Set
  • Address Incrementor/Decrementor Increment
  • Address Incrementor/Decrementor Decrement
  • Address Incrementor/Decrementor Out Enable
  • Address Builder Lower Set
  • Address Builder Upper Set
  • Address Builder Out Enable
• Architecture
  • Purple is control inputs
  • Red is single bit outputs

 

Data Path Architecture and Description

• Components
  • Data RAM
  • Data Pointer
  • Data Incrementor/Decrementor
  • Data Memory Address Register
  • Data Comparator
  • Input Register
  • Output Register
• Outputs
  • Input Register Set Bit
  • Data Comparator Zero Bit
  • Out Byte
• Inputs
  • Data Pointer Increment
  • Data Pointer Decrement
  • Data Pointer Out Enable
  • Data RAM Write Enable
  • Data RAM Read Enable
  • Data Memory Address Register Set
  • Input Register Data (8 bits)
  • Input Register Out Enable
  • Output Register Set
  • Data Incrementor/Decrementor Set
  • Data Incrementor/Decrementor Out Enable
  • Data Incrementor/decrementor Increment
  • Data Incrementor/Decrementor Decrement
  • Data Comparator Set
• Architecture

 

Controller

• The Controller will be a Mealy Machine. I have not yet implemented the controller.

 

Instructions and Their Definition

• ">": Increment Data Pointer
  1. Fetch Cycle
  2. Increment Data Pointer
• "<": Decrement Data Pointer
  1. Fetch Cycle
  2. Decrement Data Pointer
• "+": Increment Data at Pointer
  1. Fetch Cycle
  2. Move Pointer to Data Memory Address Register
  3. Move Data Memory to Incrementor
  4. Increment Incrementor
  5. Move Incrementor to Data Memory
• "-": Decrement Data at Pointer
  1. Fetch Cycle
  2. Move Pointer to Data Memory Address Register
  3. Move Data Memory to Decrementor
  4. Decrement Decrementor
  5. Move Decrementor to Data Memory
• ",": Input Data to Byte at Pointer
  1. Fetch Cycle
  2. Move Pointer to Data Memory Address Register
  3. Wait for Input Register Bit Set
  4. Move Input Register to Data Memory
• ".": Output Byte at Pointer
  1. Fetch Cycle
  2. Move Pointer to Data Memory Address Register
  3. Move Data Memory to Output Register
• "[": Branch if Zero
  1. Fetch Cycle
  2. Move Pointer to Data Memory Address Register
  3. Move Data Memory to Comparator
  4. If byte is Zero, Comparator is 1
     1. Increment Program Counter
     2. Move Program Counter to Instruction Memory Address Register
     3. Move Instruction Memory to Instruction Address Builder Lower
     4. Increment Program Counter
     5. Move Program Counter to Instruction Memory Address Register
     6. Move Instruction Memory to Instruction Address Builder Upper
     7. Move Instruction Address Builder to Program Counter
  5. Else, Byte is not Zero
     1. Move Program Counter to Subtractor
     2. Subtract 1 from Subtractor
     3. Push Subtractor onto Stack
• "]": Jump to "["

1. Fetch Cycle
2. Pop Stack to Program Counter

• Fetch Cycle

1. Increment Program Counter
2. Move Program Counter to Instruction Memory Address Register
3. Move Instruction Memory to Instruction Decoder

HLSM:

• The state machine describing the entire machine is very large, I have included an Image here, but it may be hard to read.

There are more optimizations that can be made, but those will be saved for future versions of the processor. I am looking forward to finishing the state table and design of the controller. Feel free to follow if you want, this is shaping up to be a very fun project.

P.S If you know of a program that can take either RTF, DOCX, PDF, or HTML file and convert it to BBCODE without loosing simple text formatting, nested lists, and numbered lists, please let me know. A thorough Google search and a try of a multitude of different methods yielded poor results. I fear that I may have to make my own converter.

[Spork829]

Looks super cool, though I can't say for sure, considering I'm not smart enough to understand any of this

[kurtstir]

That looks beautiful I hope you make it open source on completion!

[Nikolithebear]

Followed.  

[comicsansms]

A friend of mine made a CPU in Minecraft (using redstone) that comprehended Brainfuck.

 

I am certainly interested in your project. 

[straight_stewie]

Sorry for my lack of posts. I kind of started this project in the middle of finals week, and then as soon as I came home from university there was an injury in the family that took me away from personal projects for a while. I'm getting back to work on the project this week, but first, some news:

I reviewed my work from the previous post and realized that there were a few mistakes (actually only one type of mistake, but that mistake was repeated all over the place). Basically, every time the processor needs to make a decision on some data (or an instruction) you need to have an empty clock cycle for the register transfer to actually take place before the decision is made. I had neglected this.

I will also be working on implementing some minor and major improvements to the general design that have nothing to do with errors in the traditional sense. The two major improvements are:

• The data RAM will no longer have an address register. Instead the Pointer register will be the address register.
• Instead of having to potentially deal with math when branching, the language specification will now include 2 bytes after a branch if zero instruction ( "[" ) which specify the instruction to jump to if the byte being branched on is zero, and the jump back instruction ( "]" ) will have 2 bytes following it which represent the matching branch if zero instruction. This will also allow the compiler to determine if there are mismatched branching instructions (although it could be useful to use mismatched branches, so that feature will be able to be turned off).

I'm sorry for the interruption in new updates, especially at the very beginning of a project, but I hope that it will still prove to be an interesting project. The next post will include an updated version of the specification as well as the new datapath, instruction path, and state machine.