{ "metadata": { "name": "", "signature": "sha256:82cbd6782523400278014e29f730545a45f9c9173d9301751efdb3b5652ad09d" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# My Brainfuck CPU - A simple Processor in Python via MyHDL (part 1)\n", "\n", "### Abstract\n", "\n", "Brainfuck is a very simple but Turing-complete programming language (hereafter referred to as 'BF' for the sake of brevity and propriety), consisting of only eight commands. These posts are a record of my attempt to build a simple processor capable of correctly executing BF programs directly/natively (ie: in hardware, ultimately running on an FPGA).\n", "\n", "#### Why the hell would you do such a thing?\n", "\n", "You've never met me or worked with me, have you? ;)\n", "\n", "- Knowledge - this little mini-project ties together a whole bunch of different things that pique my interest, including:\n", " - hardware, at the diy-eeng level\n", " - digital circuit design (something I knew, and still know, very little about)\n", " - FPGAs / ASICs\n", " - MyHDL (python library for hardware simulation/design, converting software to FPGA/ASIC designs, etc)\n", " - iPython Notebook (ie: this format you're reading/in which all the software work was done)\n", " - etc\n", " \n", "- Fun - yes, my mind is warped enough by long years of programming, and I have more than enough OCD/other neuroses, that this kind of thing drops lots of dopamine into my brain :)\n", "\n", "### Who are you?\n", "\n", "I'm [sandbender](https://github.com/sandbender) on github and [SandbenderCa](https://twitter.com/sandbenderca) on Twitter... Rudy X. Desjardins for those still lost in meatspace ;)\n", "\n", "### Enough preamble, where's the meat?\n", "\n", "Right. Let's get the links out of the way first, do a quick overview of the BF language/machine, then we'll dive into design and code for our BF processor...\n", "\n", "- [Brainfuck @ Wikipedia](http://en.wikipedia.org/wiki/Brainfuck)\n", "- [MyHDL Documentation](http://docs.myhdl.org)\n", "- [Register-Transfer Level design @ Wikipedia](http://en.wikipedia.org/wiki/Register-transfer_level)\n", "- [Sequential Logic @ Wikipedia](http://en.wikipedia.org/wiki/Sequential_logic)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### BF instruction set:\n", "\n", "```\n", "> Increment data pointer by one (move to the \"right\")\n", "< Decrement data pointer by one (move to the \"left\")\n", "+ Increment byte at data pointer\n", "- Decrement byte at data pointer\n", ", Read one byte of input into byte at data pointer\n", ". Output byte at data pointer\n", "[ if byte at data pointer is zero, jump to instruction beyond matching ] *\n", "] if byte at data pointers is nonzero, jump to instruction after matching [ *\n", "\n", "* Brackets can be nested, and it is illegal for an open- or close-bracket to be used\n", " without it's match.\n", "```\n", "\n", "Note that any non-command character in the program is simply ignored (a noop).\n", "\n", "Also note that we are **not** concerned (yet) with verifying that the input program is sane - this is assumed to be the case.\n", "\n", "### The BF Machine\n", "\n", "The BF spec/description only calls for a minimal set of resources:\n", "- memory of some form to hold the program\n", "- an instruction pointer into the program memory\n", "- an array of at least (only?) 30,000 data cells (bytes)\n", "- a data pointer into the array of data memory\n", "- two byte streams, one each for input and output\n", "\n", "Program execution begins with the first (\"leftmost\") instruction in the program (instruction pointer is initialized to zero) and proceeds sequentially to the right until the last instruction has been executed (except for cases where the instruction being executed results in a different movement of the instruction pointer, ie: the looping instructions).\n", "\n", "### Our Proposed Design\n", "\n", "Our hardware design will consist of a slightly more complex setup compared to the theoretical BF machine model, out of necessity (we're trying to design for actual hardware here, not just a theoretical soft model). Since MyHDL allows us to mix and match regular/high-level Python with lower level mechanisms which would mirror actual hardware components... we _could_ just pipe the BF input through a function that maps it's instructions directly to normal/high-level python code and be done with it.\n", "\n", "But that would defeat the whole purpose of this excercise, which is to simulate actual hardware that will be implement-able on a real world FPGA.\n", "\n", "As such, we're going to stick to something called _Register Transfer Level_ mechanisms in our simulation - MyHDL constructs which map more or less directly to low-level hardware abstractions at the level of basic logic and signals that will be present in a real digital circuit.\n", "\n", "### Sequential vs. Combinatorial Logic\n", "\n", "Quick primer on the difference: combinatorial logic elements have output which depends **solely** on their inputs. Sequential logic elements, in contrast, have outputs which depend on their inputs **and** prior state. Ie: sequential logic elements have/use memory/storage.\n", "\n", "Example Sequential Operations:\n", "- Incrementing or Decrementing a value (depends on prior value)\n", "- Looping (depends on location of begin/end of loop, nesting, etc)\n", "- Writing data to memory (depends on value of a data pointer (address) already being set/stable)\n", "\n", "Example Combinatorial Operations:\n", "- Reading instructions/data onto a bus (output to bus is linked directly to input address)\n", "\n", "MyHDL provides both - the ```@always_comb``` decorator is used to produce combinatorial elements, and ```@always_seq``` is used for sequential (usage/etc for both will be explained later).\n", "\n", "### Timing\n", "\n", "We're going to model a very simple system where both data and instruction buses are loaded immediately (ie: in a combinatorial fashion) whenever their respective pointers change - if you increment the data pointer, the data byte on the bus is automatically updated, etc.\n", "\n", "We'll have a simple symmetrical clock signal to drive the sequential elements, which will be: the writing of any data to memory (if necessary) at the end of a clock cycle, the execution of the current instruction at the beginning of a clock cycle, and the advancement of the instruction pointer at the end of a cycle.\n", "\n", "### Registers:\n", "\n", "We'll need a set of registers to hold various state inside the processor. In the interest of keeping most of the background detail in one place, I've listed them **all** here with brief descriptions; each will be further explained later as we come across them.\n", "\n", "The following registers are all boolean in nature (flags):\n", "```\n", "CLK Our clock signal.\n", "SE \"Scan Enable\" - signifies that we're performing a search through the instructions to\n", " find matching brackets for the purpose of looping.\n", "SD \"Scan Direction\" - indicates whether we're moving forwards or backwards when\n", " advancing the instruction pointer (IP).\n", "WE \"Write Enable\" - indicates when the current byte on the data bus (DBUS) should be\n", " written to memory at DP.\n", "```\n", "\n", "We will also need the following single-byte registers:\n", "```\n", "IP Instruction pointer\n", "DP Data pointer\n", "SA Scan accumulator - keeps track of how many open/close brackets we've seen while scanning for a match.\n", "```\n", "\n", "And these single-byte buses:\n", "```\n", "IBUS Holds the current instruction.\n", "DBUS Holds the current data byte.\n", "```\n", "\n", "### Let's start building!\n", "\n", "First we need to import all the necessary pieces from the ```myhdl``` package:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "from myhdl import Signal, Simulation, StopSimulation, always, always_comb, always_seq, delay, enum, intbv, traceSignals" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 1 }, { "cell_type": "markdown", "metadata": {}, "source": [ "These are all the bits of hardware simulation we'll need from MyHDL... I won't bother describing them all here - you're encouraged to browse the MyHDL documentation, or keep reading for explanations below as each is introduced.\n", "\n", "Next we'll setup some boilerplate:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "# self-explanatory constants \n", "HIGH = 1\n", "LOW = 0\n", "\n", "\n", "ops_map = {\n", " '+': 'INC',\n", " '-': 'DEC',\n", " '>': 'INC_DP',\n", " '<': 'DEC_DP',\n", " ',': 'READ',\n", " '.': 'WRITE',\n", " '[': 'OPEN_LOOP',\n", " ']': 'CLOSE_LOOP'\n", "}\n", "valid_ops = ops_map.keys()\n", "ops = enum(*(ops_map.values()))\n", "\n", "def bf_to_native(program):\n", " '''\n", " 'program' is a string.\n", " \n", " Any non-BF characters are pruned.\n", " '''\n", " return [ops.__getattribute__(ops_map[x]) for x in filter(lambda x: x in valid_ops, program)]" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 2 }, { "cell_type": "markdown", "metadata": {}, "source": [ "The ```enum(...)``` type is provided by MyHDL. We can use this as a convenient way of passing around labelled members of a set with the underlying implementation corresponding to integers. Here, we're setting up the set of valid instructions supported by the BF language.\n", "\n", "We've also just made a few concessions for the sake of convenience: The ```ops_map``` dict maps string representations of the actual BF instructions to the names of the corresponding members of our ```enum```. This in turn enables the ```bf_to_native``` function, which converts a string-based BF program to a sequence of 'native' instructions for our fledgling CPU.\n", "\n", "Next, let's setup the python-based arrays to be used as the BF data array (memory), program memory, input and output buffers...\n", "\n", "_Note that for this phase of the BF CPU madness, we're only concerned with the core processor itself, and are basically ignoring memory (program & data chunks) as well as \"real\" I/O. This is to keep this phase of the hardware design simple - once (if?) I get to the point where I'm implementing something physical, I'll worry about adding in sub-designs to handle things like I/O and actual storage implementations. For now, it's *just* the processor we're modelling, so the rest will be left as simple, high-level Python stuff without any directly corresponding hardware modelling._" ] }, { "cell_type": "code", "collapsed": false, "input": [ "# BF spec requires 30000 bytes of data memory\n", "bf_data = [0 for i in xrange(30000)]\n", "\n", "# Our program - \"Hello World!\\n\" to output\n", "bf_program = \"++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.\"\n", "\n", "bf_program = bf_to_native(bf_program)\n", "\n", "bf_input, bf_output = [], []" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 3 }, { "cell_type": "markdown", "metadata": {}, "source": [ "The \"Hello World!\" program above is courtesy of the BF Wikipedia page (see the links section above).\n", "\n", "Now we get to the real meat...\n", "\n", "### The Clock" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def clock_driver(clk, we):\n", " '''\n", " Symmetrical clock signal, high then low then repeat, update/change every iteration of the sim.\n", " \n", " We also set we (write enable) low when the clock goes low, regardless of whether it's already\n", " high or not.\n", " '''\n", " \n", " @always(delay(1))\n", " def _drive_clock():\n", " if clk:\n", " we.next = LOW\n", " \n", " clk.next = not clk\n", " \n", " return _drive_clock" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 4 }, { "cell_type": "markdown", "metadata": {}, "source": [ "At a basic level, the clock driver component simply toggles a clock signal on each iteration of the simulation.\n", "\n", "However there's a bunch of MyHDL-isms introduced here which warrant some explanation...\n", "\n", "#### Signals\n", "\n", "All \"paths\" between hardware components are modelled using MyHDL's ```Signal``` objects. In the case of our clock driver above, the ```clk``` and ```we``` arguments are both ```Signal``` objects. These objects are passed to any hardware component which requires read or write access to them at the time that component is instantiated. Any component driven by the main clock will be passed the same ```Signal``` object for it's ```clk``` argument, etc... this 'connects' the components via the Signal.\n", "\n", "#### MyHDL decorators, and the ```delay``` function\n", "\n", "All hardware components in a MyHDL simulation are modelled using specialized generator functions. You can manually craft a generator function and mark it as a hardware component with the ```@instance``` decorator. More often though, you'll use one of the other decorators which accept classic (non-generator) functions and automatically add the appropriate generator behaviour.\n", "\n", "The value ```yield```'ed from a MyHDL generator controls when the component will be resumed. Typically this will either be a length of time like we do here with ```@always(delay(1))``` (which says \"run this function every time 1 iteration of the sim has elapsed... ie: every iteration), or a ```Signal``` edge as we'll see shortly with sequential decorators.\n", "\n", "Hardware component models are built using top-level functions which **return** generators when called. Any parameters to the component (```Signal```s and any other arguments used for conditional instantiation, etc) are passed to the **top-level** function. The inner generator function which is returned takes **no** arguments.\n", "\n", "#### ```Signal.next```\n", "\n", "This is the mechanism for specifying what the value of a ```Signal``` should be during the next iteration of a sim. Ie: to change a ```Signal```'s value, you assign the new value to ```.next```.\n", "\n", "It's worth noting here that digital circuits are massively concurrent by nature (which is kinda the point from the context of a programmer interested in ASIC/FPGA circuit design... performance right?).\n", "\n", "When writing software, regardless of the language and programming style, at the end of the day you have an abstraction of some kind in your head roughly corresponding to some incarnation of 'first this happens, then this...'. With a digital circuit, all the pieces are potentially active all the time. **Every** component whose output is updated on the rising edge of a clock signal will 'run' every time the clock goes high, etc. The sequential aspect is still present in the form of sequential logic elements whose output depends on prior state, but that's as far as it goes at a low level. Every time the state/system updates, everything updates all together. The mental model is very different from how you may picture a piece of software.\n", "\n", "### The data-reading component" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def read_data(dp, dbus):\n", " @always_comb\n", " def _read_data():\n", " dbus.next = bf_data[dp]\n", " \n", " return _read_data" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 5 }, { "cell_type": "markdown", "metadata": {}, "source": [ "This component simply places the appropriate byte on the data bus whenever the data pointer (address) changes.\n", "\n", "#### The ```@always_comb``` decorator\n", "\n", "This is the MyHDL mechanism for specifying a combinatorial element; there is no clock required here, the element does not depend on any prior state - the output (```dbus.next```) simply changes immediately as soon as the input (```dp```) changes. You can think of the output being a function of the input which is constantly being evaluated.\n", "\n", "MyHDL **automatically** infers which arguments to the top-level function are inputs, you don't need to specify which are which.\n", "\n", "### The data-writing component" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def write_data(dp, dbus, we):\n", " '''\n", " Write data byte to memory at DP whenever the write enable signal goes from high to low.\n", " '''\n", " \n", " @always_seq(we.negedge, reset=None)\n", " def _write_data():\n", " bf_data[dp] = int(dbus.val) # Need to get a COPY of the data, not a ref! (int() usage)\n", " \n", " return _write_data" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 6 }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is an example of a sequential logic component - it's sensitive to the falling edge of the ```we``` signal, meaning that whenever the we signal goes low, the output will update (not necessarily change - depends on input).\n", "\n", "The ```reset``` argument to the decorator can be used to specify a different signal which will reset the sequential component - MyHDL apparently figures out what to reset/how automatically, although there's an alternate method of accomplishing the same thing manually. Our simple processor model doesn't use any resets in this first iteration, so I'll say no more about that feature as I haven't used or fully grokked it yet.\n", "\n", "### The instruction pointer advancer" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def instruction_advance(ip, sd, clk):\n", " '''\n", " Update the instruction pointer on every falling clock edge.\n", " '''\n", " \n", " @always_seq(clk.negedge, reset=None)\n", " def _advance_instruction():\n", " if sd:\n", " ip.next = ip + 1\n", " else:\n", " ip.next = ip - 1\n", " \n", " return _advance_instruction" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 7 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pretty obvious... advances ```ip``` appropriately for either forward or backward processing/scanning. (Backwards scanning is used when returning to the beginning of a loop \"block\".)\n", "\n", "### The instruction reader" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def instruction_read(ip, ibus):\n", " '''\n", " Read instruction from program at instruction pointer onto ibus.\n", " \n", " Stop (\"exit\") if we've reached the end of the program.\n", " '''\n", " \n", " @always_comb\n", " def _read_instruction():\n", " if ip == len(bf_program):\n", " raise StopSimulation\n", " \n", " ibus.next = bf_program[ip]\n", " \n", " return _read_instruction" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 8 }, { "cell_type": "markdown", "metadata": {}, "source": [ "If ```ip``` points beyond the end of the program, exit the simulation (we're done). The rest of that should be self-explanatory at this point. Moving on...\n", "\n", "### The instruction executor" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def process(ip, ibus, dp, dbus, we, se, sd, sa, clk):\n", " '''\n", " Meat.\n", " \n", " Execute the instruction on ibus.\n", " '''\n", " \n", " @always_seq(clk.posedge, reset=None)\n", " def _process():\n", " if ibus == ops.OPEN_LOOP:\n", " if not se and 0 == dbus: # New forward scan\n", " se.next = HIGH\n", " sd.next = HIGH\n", " sa.next = 1\n", " elif se: # Existing scan\n", " if sd: # Forwards\n", " sa.next = sa + 1\n", " else:\n", " sa.next = sa - 1\n", " \n", " if 1 == sa: # This is the droid you are looking for\n", " se.next = LOW\n", " \n", " # For finalizing backward scans, we need to reset SD\n", " # so that regular instruction advancing moves *forwards*\n", " sd.next = HIGH\n", " elif ibus == ops.CLOSE_LOOP:\n", " if not se and 0 != dbus: # New backward scan\n", " se.next = HIGH\n", " sd.next = LOW\n", " sa.next = 1\n", " elif se: # Existing scan\n", " if not sd: # Backwards\n", " sa.next = sa + 1\n", " else:\n", " sa.next = sa - 1\n", " \n", " if 1 == sa: # This is the droid you are looking for\n", " se.next = LOW\n", " elif not se:\n", " if ibus == ops.INC:\n", " dbus.next = dbus + 1\n", " we.next = HIGH\n", " elif ibus == ops.DEC:\n", " dbus.next = dbus - 1\n", " we.next = HIGH\n", " elif ibus == ops.INC_DP:\n", " dp.next = dp + 1\n", " elif ibus == ops.DEC_DP:\n", " dp.next = dp - 1\n", " elif ibus == ops.READ:\n", " dbus.next = ord(bf_input.pop(0)) # consume head of input array\n", " we.next = HIGH\n", " elif ibus == ops.WRITE:\n", " bf_output.append(int(dbus.val))\n", " \n", " return _process" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 9 }, { "cell_type": "markdown", "metadata": {}, "source": [ "The core of our processor, this is the module which performs the core logic, ie: executes instructions.\n", "\n", "#### Looping\n", "\n", "We start off by checking whether the instruction is either a start- or end-loop command. If **not**, the rest of the instruction types will be executed only if there isn't a loop-scan in progress; if there **is** a loop-scan in progress, no commands are executed, the instruction pointer simply moves until it reaches it's destination (start/end of the loop).\n", "\n", "Open-loop commands are ignored if the byte on the data bus is nonzero, and close-loop commands are ignored if the data byte is zero - in both these cases, it's basically a noop.\n", "\n", "If we *do* need to scan (to jump to the end of the loop, or the beginning), we basically step through in the appropriate direction, counting open/close braces appropriately until we find our match. This is facilitated via ```se``` (\"scan enable\" - indicates no non-loop processing should happen), ```sa``` (\"scan accumulator\" - used to count brackets) and ```sd``` (\"scan direction\" - used to control which way the ```ip``` advances while scanning).\n", "\n", "The OPEN_LOOP logic is basically a mirror of CLOSE_LOOP, with one small exception: since the ```sd``` flag is used for loop scanning **and** regular ```ip``` advancement, at the end of a **backwards** scan we need to reset it to ```HIGH``` so that the next instruction advancement (normal non-looping program progression) will proceed in the right direction.\n", "\n", "#### Writing the byte on the data bus back to memory\n", "\n", "For the operations which modify the byte on the data bus (INC, DEC and READ), we perform the appropriate operation by setting ```dbus.next```, and then set ```we.next``` (\"write enable\") to HIGH so that it'll be stored in memory at the appropriate spot (```dp```) on the falling edge of the ```we``` signal, which is set LOW by the clock at the same time that the main clock goes LOW.\n", "\n", "### Putting it all together..." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def cpu():\n", " # Boolean signals\n", " clk, se, we = [Signal(bool(0)) for i in range(3)]\n", " sd = Signal(bool(1))\n", " \n", " # Byte signals\n", " ip, dp, sa = [Signal(0) for i in range(3)]\n", " \n", " # Buses\n", " ibus = Signal(bf_program[0])\n", " dbus = Signal(intbv(bf_data[0], min=0, max=255))\n", "\n", " # Instantiate all our hardware components...\n", " clock = clock_driver(clk, we)\n", " data_reader = read_data(dp, dbus)\n", " data_writer = write_data(dp, dbus, we)\n", " op_advancer = instruction_advance(ip, sd, clk)\n", " op_reader = instruction_read(ip, ibus)\n", " op_process = process(ip, ibus, dp, dbus, we, se, sd, sa, clk)\n", " \n", " return clock, data_reader, data_writer, op_advancer, op_reader, op_process" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 10 }, { "cell_type": "markdown", "metadata": {}, "source": [ "The ```system``` function instantiates all our ```Signal```s, instantiates all the hardware components and passes each the appropriate ```Signal``` set, and then returns all the component instances. This is how you build a compound component in MyHDL - a component is either a list of instances or a function which will return an instance, so we build the cpu by building all the sub-components and returning them as a set.\n", "\n", "Last but not least, the following little block demonstrates how to instantiate the cpu, wrapping it with traceSignals so that a simulation run will output a .vcd file that we can import in gtkwave to view the waveform, and how to execute the simulation (which returns when a StopSimulation exception is raised from a component within):" ] }, { "cell_type": "code", "collapsed": false, "input": [ "cpu_instance = traceSignals(cpu)\n", "\n", "Simulation(cpu_instance).run()\n", "\n", "# This is pure high-level python so we get/see human-readable output (ASCII bytes)\n", "print(''.join(chr(x) for x in bf_output[:12]))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Hello World!\n" ] } ], "prompt_number": 11 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### gtkwave screenshot sample\n", "\n", "The following is a partial screenshot of the view of the signals in gtkwave, loaded from the .vcd file generated by ```traceSignals(...)```\n", "\n", "![gtkwave sample screenshot](https://raw.githubusercontent.com/sandbender/BF_CPU/master/gtkwave_hello_world.png \"Sample gtkwave screenshot\")\n", "\n", "### And that's it!\n", "\n", "Hope you enjoyed part 1 of my BF cpu build... stay tuned for further installments!" ] } ], "metadata": {} } ] }