A Brainfuck CPU in FPGA
19 January 2013 (programming haskell brainfuck FPGA electronics ISC) (49 comments)About two and a half years ago, a wave of interest in electronics swept across the Budapest office of Intentional. We desperately wanted to create something tangible from first principles. The idea we settled on was to design and eventually build a CPU that uses Brainfuck as its machine language.
Looking back, it really was a case of people with insufficient knowledge trying to use inappropriate tools. But damn if we didn't have fun during the process! After filling a couple of notebooks with sketches, we ended up with an initial design in Logisim. It had horrible timing problems, of course, since too much of it was asynchronous. Before ironing out all the wrinkles, though, I remember Maya pointing at one of the lines tangled up on the screen, and saying "You guys realise this single line will be 16 wires if we actually want to solder this together, right?" So basically we gave up on building the thing. Later on, Maya and Encsé went on to enroll to a bachelor's program in EE as a hobby; and I decided to stick to discrete logic, ordered a bunch of 7400 TTL's and some LEDs and seven-segment displays and started wiring together much simpler circuits on breadboards. I never got to soldering, not to mention getting access to anything that could produce PCB's, Then as I moved to Singapore, I left all my electronics stuff at home, and put the whole electronics thing on the backburner indefinitely.
Then, a couple months ago I discovered the Papilio FPGA platform, which has this collection of nice IO daughterboards (called "wings") that snap right into it, no soldering or even wiring required. I ordered one with the LogicStart IO board which features, among other, more advanced stuff, eight toggle switches and four seven-segment displays. Perfect for my baby steps into the world of FPGA's!
So what else could my Hello World project have had been, than the Brainfuck CPU.
Basic design
We can use the Harvard architecture: since the Brainfuck language has no reflection capabilities, the program can be stored in ROM with no programmable access. Memory is implemented as a RAM of 32K 8-bit bytes. The CPU also has several internal registers:
- Internal state: As we will see, it takes several clock cycles for the CPU to execute a given Brainfuck opcode. Rather unfortunately, I ended up with 9 states, so I need 4 bits to store it.
- Program counter (PC): directly connected to the address pin of the ROM.
- Opcode register: loaded from the data pin of the ROM in the Fetch state.
- Memory pointer (idx): a 15-bit register that is directly connected to the address pin of the RAM.
- Data out register: for simplicity's sake, new values for RAM[idx], and the write enable leg of the RAM, are buffered
- Depth counter (DC): Used in the implementation of the [ and ] opcodes (see below)
Output is implemented by an 9-bit signal: 8 bits of data and an enable bit. When a . opcode is encountered, the CPU sets these 9 bits, and enters a special state until it receives an acknowledgment signal. Input is implemented similarily. On the actual board, the output signals are connected to the seven-segment display, the input signals are fed from the eight toggle switches, and the directional "mini-joystick" is used to acknowledge input/output.
Implementing [ and ]
Compared to a normal machine language, it's really just [ and ] that requires special handling. Everything else is just straightforward manipulation of either idx or RAM[idx] via incrementing/decrementing; or pushing data between RAM[idx] and the IO port. [ and ] are tricky because we need to search for their matching pairs, and pre-processing the Brainfuck program to attach pair addresses would be against the spirit of this (self-imposed) challange.
One solution would be to maintain a stack in a separate RAM, and push PC into it whenever a [ is encountered. In that case, ] is a simple matter of popping PC if RAM[idx] does not equal 0. However, here we've basically changed [/] from a while loop to a do while loop. So if RAM[idx] is 0 when we first enter the [, we have to scan the program forward to find its matching ].
For simplicity's sake, I decided not to worry about performance and skip the stack part, and just implement scanning in both directions. Scanning is where the DC register is used (explained here for [, but ] is similar): if the opcode is [ and RAM[idx] is 0, DC is set to 1, and the CPU enters a special skip-forward state from the next opcode. In this state, only [ and ] opcodes have any effect: they increment and decrement, respectively, the DC register. When DC gets to 0, we know we've found the matching ], and so we can go back to the regular fetch-execute cycle.
Lava → VHDL → Xilinx
I originally planned to implement the whole thing in VHDL, and compile that using the Xilinx synthesizer tools (since the Papilio One board uses a Xilinx FPGA chip). However, I've found VHDL to be quite a horrible language from a software programmer's point of view. The whole point, for me, of going from physical chips to FPGA's was to enable using abstractions to manage complexity; so why settle for a poor language like VHDL? Fortunately, there's a whole family of Haskell-embedded DSLs for hardware description called Lava. Of these, Kansas Lava seemed the only one actively maintained, and it already had support for a Xilinx dev board; so adding support for the Papilio was straightforward (see my kansas-lava-papilio package).
The complete code for my Brainfuck CPU (including IO via the LogicStart daughterboard) is available on GitHub. There are quite some rough edges left to file off; I'd say the most pressing is adding the ability to synthesize the program ROM separately from the CPU definition.
Videos
This first video shows a simple countdown (actually, count-up) program: ,[>+.<-]. I had to record these slightly out-of-focus, otherwise the seven-segment LEDs were hard to read.
Next up is "Hello world!":
And the final one shows Maya's solution to the 9-digit problem. This one really shows how slow this naïve, stackless implementation is.
Luis Fernando 2013-01-20 15:54:57
very nice
I made a very complex brainfuck program a few years ago. Actually, it's the most complex brainfuck program I know ever existed
It's a factorial that works with base-10 internally (it obviously would be easier to work with base-1, but how fun would that be?)
If you wanna check/try to run it, http://pastebin.com/f59e7a219 and lemme know please :)
-- Luis Fernando
Eduardo Corpeño (http://kuashio.blogspot.com) 2013-01-20 20:12:42
Hey, I made a similar processor (harvard also) in verilog. I presented it at a tech conference we host at out university in Guatemala.
It's called brainfuckuP. I'll make a blog post about it soon.
cactus 2013-01-21 01:24:10
Eduardo: Looking forward to it!
Luis: if you check out under the "brainfuck" tag on my blog, you can find a two-parter about compiling register machines to BF. Using that technique, it's not hard to arrive at huge BF programs -- for example, a straightforward register machine implementation of the 9-digit problem resulted in half a meg of BF code... the ROM probably wouldn't even fit on my board.
Nevertheless, once I implement loops with a proper stack, I'll look into running your program.
arlington locksmith (http:// http://www.locksmith-arlingtonva.com/) 2013-04-22 10:14:30
Awesome post, thanks so much for sharing this with us!
bethesda locksmith (http://bethesda-locksmith.net/) 2013-04-22 12:21:17
Thanks, I was looking for information and your blog really helped me.
locksmith in va (http://va-locksmith.com/) 2013-04-22 13:26:48
Thanks, I was looking for information and your blog really helped me.
movers dundalk md (http://originalvanlines.com/movers-dundalk-md.php) 2013-04-22 14:39:46
Good info and Thanks for sharing this with us.
best vitamin supplements (http://www.vitaminshub.com/) 2013-04-22 15:32:48
Hey … it's an amazing information dude. Thnx! For sharing this great.
best herbal supplements (http://www.vitaminshub.com/Herbal_Supplements_s/26.htm) 2013-04-22 17:19:43
I found this Information very interesting and informative! Keep sharing!
movers arlington va (http://www.dclocalmovers.com/) 2013-04-22 18:22:03
The positive comments and do well wishes are very motivational and greatly appreciated.
pandawill 2013-04-23 04:54:00
z The Pandawill an online store, operates various brands,a variety of a variety of large-screen smart phones and tablet PCs,and the necessities of life.JXD S602
the best china wholesale 2013-04-23 05:28:01
Y Tablets, smart phones, online sales, the cheapest electronic wholesale market, China - pandawill.comLenovo K800
movers fairfax va (http://dcofficemovers.com/fairfax-va-office-movers) 2013-04-23 11:00:54
Good info and Thanks for sharing this with us.
maryland movers (http://www.maryland-movers.us/) 2013-04-25 15:08:38
Hello, an amazing Information dude. Thanks for sharing this nice information with us.
locksmith va (http://va-locksmith.com/) 2013-04-25 16:34:24
I just want to thank you for sharing your information and your site or blog this is simple but nice Information I’ve ever seen i like it i learn something today.
buy natural supplements (http://www.greennaturalsupplements.com/) 2013-04-25 18:41:51
Thank you. I will be passing this along, I am very happy to get this post and comment here.
buy best supplements (http://greenbestsupplements.com/) 2013-04-26 11:14:44
Great Information, very interesting and useful for me. Thanks!
best vitamins for hair loss (http://www.greenorganicvitamins.com/Hair-Loss-Control) 2013-04-26 11:39:41
I am so happy to read this. This is the kind of manual that needs to be given and not the random misinformation that's at the other blogs. Thanks for sharing this.
natural weight loss supplements (http://www.greenorganicvitamins.com/natural-weight-loss-supplements) 2013-04-26 11:55:29
I was always in search of such useful information you have shared in this blog. This will help me in my working.
adrenal fatigue supplements (http://www.greenorganicvitamins.com/adrenal-fatigue-supplements) 2013-04-26 11:59:04
It is my pleasure that I have the unique opportunity to comment on this awesome post.
woodbridge locksmith (http://woodbridgelocksmith.us/) 2013-04-27 12:43:46
Hello Dear, Really your blog is very interesting.... it contains great and unique information. I enjoyed to visiting your blog. It's just amazing.... Thanks very much.
woodbridge locksmith
kohlis 2013-04-27 13:52:33
I like this blog thanks for such a great Information.
superfoods
kohlis 2013-04-27 16:00:24
Thanks for the great post. You have a well written and informative blog especially for us.
change a lock
kohlis 2013-04-27 16:50:08
This is good site to spent time; I just stumbled upon your informative blog and wanted to say that I have really enjoyed reading your very well written blog posts. I will be your frequent visitor, that's for sure.
wholesale health products
movers dc (http://moversdc.us/) 2013-04-27 17:38:07
Amazing! I like to share it with all my friends and hope they will like this information.
kohlis 2013-04-27 17:42:33
Wonderful site and I wanted to post a note to let you know, ""Good job""! I’m glad I found this blog. Brilliant and wonderful job! Your blog site has presented me most of the strategies which I like. Thanks for sharing this.
24 hour locksmith queens
http://www.oakleywomenssunglasses.com/ (http://www.oakleywomenssunglasses.com/) 2013-04-28 08:59:12
We appreciate for sharing the good products with us. Without a pair of dark glasses, <strong>oakley womens sunglasses</strong> don't say you really understand fashion, even if you just used to play the model case, so what? In Europe and the star is not that right, no matter indoor or outdoor, <strong>Oakley Special Edition Sunglass sunglasses</strong> are always hand a big fly, want to know that the sunglasses Yu Mingxing, like in a girlfriend, in a quarterly is definitely not stingy.<br> For boys go sell of course,<strong> oakley sunglasses men</strong> the most popular, a big glasses. Romantic love in the film "brokenhearted 33 days", the article plays wang, and he wears a black big glasses of restoring ancient ways is nifty and fashion. However, not everyone is suitable.<p href="http://www.oakleywomenssunglasses.com/" href="http://www.oakleywomenssunglasses.com/specials.html" href="http://www.oakleywomenssunglasses.com/products_new.html" class="STYLE1">Color too deep sunglasses will probably because of the traffic signal recognition and accidents, <strong>Oakley M Frame Sunglass </strong>poor ability of color too shallow sunglasses there is less than the role of keep out sunshine, at present only for red, green and yellow colors of sunglasses made strict rules traffic signal recognition ability, <strong>oakley mens sunglasses</strong> other color is not relevant provision, but there is a recruit, <strong>Oakley Batwolf Sunglass</strong> you might as well give it a try: when choosing sunglasses that is must try when buy, oakley sunglasses womens look around the environment change size color, color difference changes little sunglasses in general its color is more appropriate. As we all know, <strong>Oakley Asian Fit Sunglass</strong> sunglasses is the most one to one function is the uv protection.</p> cxf </br>
ルイ・ヴィトン (http://www.louisvuitonshopjp.com) 2013-04-28 11:03:32
<p><strong>louis vuitton</strong></p><p><strong>バーバリー財布</strong></p><p><strong>louis vuitton</strong></p><p><strong>louis vuitton outlet</strong></p><p><strong>louis vuitton</strong></p><p><strong>louis vuitton bags</strong></p><p><strong>louis vuitton</strong></p><p><strong>coach outlet store online</strong></p><p><strong>michael kors</strong></p><p><strong>coach factory outlet</strong></p><p><strong>louis vuitton outlet</strong></p><p><strong>バーバリー</strong></p><p><strong>coach outlet</strong></p><p><strong>coach handbags new 2012</strong></p><p><strong>ルイヴィトン 財布</strong></p><p><strong>michael kors outlet</strong></p><p><strong>coach outlet store online</strong></p><p><strong>ルイ・ヴィトン</strong></p>
dafadga 2013-04-29 07:17:38
K The gradual improvement of living standards, demand for mobile phones is not limited to communications, is the pursuit of the appearance of the phone and entertainment properties, then in the end what kind of phone is able to meet all these requirements? Pandawill special launch lifestylish digital shopping guide series, holding a purse you accurate shot, to buy their favorite products. tablet china
louis vuitton outlet (http://www.louisvuittonoutlet-cfm.com) 2013-04-29 09:53:52
A3 - Stuart Weitzman 5050·Waterproof, fireproof louis vuitton outlet legend louis vuitton outlet Louis Weedon, the true extent of difficult to pursue, but it does not need the leather or other ordinary leather, but with a painting, called louis vuitton handbags usa outlet Canvas canvas material, and a layer of waterproof PVC, did make it bag Griselda, not easy to wear. In addition to "durable", has one hundred and fifty years of history of Louis louis vuitton handbags usa outlet Weedon, began to specialize in the royal family and nobles of the market, and make the brand stand up not down.In 1888, Louis Weedon in a square pattern Louis vuitton handbags uk to replace the original rice, brown stripes, Louis vuitton handbags uk and add to the registered trademark, but still full of counterfeit goods in the world; as the sole inheritor of famous brand Louis Vuitton group, George on 1896 in Anel quiet office, designed the famous louis vuitton outlet brand brand Louis Vuitton logo. In January 11, 1897 in the Conciliation Commission louis vuitton outlet registered and officially put into use. Strange combination of the letters and quatrefoil flowers intertwined, diamond Louis Vuitton Damier Ebene Canvas will flourish around brown background. Four leaf pattern may be Louis Vuitton Damier Ebene Canvas from the governor's palace acrobatics wolf. Fancy pattern idea maybe from the Edo period. And around the concave four stellate, looks and Han China flag pattern similarity. Or no poetic said, floor Louis vuitton Canada tile design ideas from George and Josephine Weedon kitchen.
kohlis 2013-04-29 11:10:50
I am so glad this internet thing works and your Information really helped me. Might take you up on that home advice you.
locksmith in west chester
kohlis 2013-04-29 11:11:47
I am so glad this internet thing works and your Information really helped me. Might take you up on that home advice you.
locksmith in west chester
change locks west chester (http://locksmith888.com/) 2013-04-29 12:02:23
Hey … it's an amazing information dude. Thnx! For sharing this great.
kohlis 2013-04-29 12:06:06
Really your blog is very interesting.... it contains great and unique information. I enjoyed to visiting your blog. It's just amazing.... Thanks very much.
movers bethesda md
angle harri 2013-04-29 12:08:09
I already saw many blogs but I like this commenting platform. Thanks a lot for your guidance and sharing information.moving companies washington dc
kohlis 2013-04-29 12:52:40
Thanks for sharing it. I found this Information very interesting and informative! Keep sharing!
natural supplements
angle harri 2013-04-29 13:45:04
Really your blog is very interesting.... it contains great and unique information. I enjoyed to visiting your blog. It's just amazing.... Thanks very much.dc locksmith
angle harri 2013-04-29 13:53:40
Thank you, I have recently been searching for information about this topic for ages and yours is the best I have discovered so far.best locksmith in virgina
angle harri 2013-04-29 16:23:14
Very interesting thanks. I believe there's even more that could be on there! Keep it up.
Coffee bean extract
angle harri 2013-04-29 16:32:25
This was a really outstanding post. In theory I would like to compose like this too - taking time and real effort to make solid Information.
movers alexandria va
Cheap Hermes Belts on sale (http://www.designerbeltsmall.com/) 2013-04-30 09:24:16
One can't be proven to as fashionable once they does not own high quality cheap Hermes Belts . Individuals who're acknowledged being popular have sufficient discount Burberry Belts inside their closet. Because cheap Gucci Belts on sale will be the primary add-ons which are needed being fashionable. Belts could create numerous looks for your outfit and may really add spice for the boring outfit. By simply obtaining a cheap Louis Vuitton Belt , you will observe the means by which might help your outfit in the more intriguing, notable and even more fashionable one. You might have a dress-up costume-up costume which will surely stick out as the saying goes only use the most effective type of belt.
エルメス激安コピー (http://www.johins.net/) 2013-04-30 10:32:22
严宽はわが国の男子俳優たちは彼の深いの五感と貴族の雰囲気にされていた人物が「杀阵第一美男」だった。最近严宽撮影した最新一组ファッション巨編ひとのサラリーマンたちの组み合わせてテクニックだクリスチャンルブタン 通販。男装以下は小编misa帯をみんなで一緒に写真だろう。
見ているけど、ファッション大作映画のうち、男性スター严宽白いシャツ上オレンジ色のセーターを着て、地面に黒い外套や茶色裤装など、全般的な取り组み无比太陽格好良かったです。
严宽オシャレ大作映画の中で、黒のスーツの男性长款コート上白いシャツと黒いスーツは、白黒の取り组みは経典大方で椅子をビジネスイケ味です。
严宽黒のスーツ上粉紫色のシャツブランド腕時計コピー新作、茶色の裤装、単調なポイントのネクタイは身に火をともす全体を取り组み立てて、個性ファッションの魅力を披露。
时进プリント背広の上着はファッショナブルな个性、取り组みで白いシャツと绿のネクタイなど、ブランド靴新作コピー全般的な取り组みを际立熟した男の味を落ち着いて成熟した感じがします。
最新のファッション大作映画のうち、男性スター严宽黒のスーツ上波時シャツなど、全般的な取り组み経典をまた谨厳でおしゃれを飾った。会社員の男性早く来て勉强してください。
URL:<B>http://www.enegkd.net/</B>
Jragger001 (http://www.pandoracanadaofficia.com/) 2013-05-04 11:35:09
A vast choice of quality Pandora Silver Beads and Pandora Gold Beads Online can be found at footballshirts.com now. What’s more important, you can enjoy the best Cheap Pandora Beads With Stones at really low price.
Adidas Jeremy Scott 2013-05-13 10:44:44
Polarized solar shades will be likely if you are enduring observation problems involving long-distance vision suchashypermetropia plus presbyopia, that nevertheless wish to take advantage of the thrills with voyage sports activities. There are particular limitations regarding polarized solar shades. People being dressed in polarized solar shades most likely are not competent to see a number of alleviation attributes in environments, while it hinders a nice selection of Orange Beats By Dre belonging to the lighting sun rays highlighting traditional hunting had. This tends to always be risky in small its polar environment. One more element in opposition to polarized solar shades is the fact these people make LCDs just about invisible out of selected perspectives seeing that LCDs can also be polarized lighting. Genital herpes solar shades are designed for many who get observation problems, however that tend not to need to don monotonous specs. They've got your corrective tools electrical power including the lenses involving specs plus lenses however are designed in a very lustrous cool way that additionally caters towards the fashion sense involving the particular using the shoe. Genital herpes solar shades will be acquired as outlined by the ability involving the particular contact when recommended by way of a great oculist. They'll both magnify or maybe diminish images when dictated through the requires belonging to the using the shoe. Genital herpes solar shades can be obtained pertaining to lots of folks who need smaller main span lenses and also those that need huge solutions. Also bifocals will be availablehttp://beatsbydremart.blogspot.com/ that empower the particular using the shoe to find out close to plus remote materials evidently. Appearing solar shades, genital herpes solar shades besides greater the particular vision, however additionally safeguard the particular eyes through the dangerous ultraviolet radiations belonging to the sunshine. Polarized genital herpes shades safeguard the particular eyes out of intense glares out of normal water surfaces, environments or maybe wide open driveways. Overlook the particular Jimmy Choos, the particular Armani meets plus Christian Dior perfumes. In case you are searching for affordable high-class, high-end fashion buildings this promote their own items with unholy selling prices will be genuinely certainly not worth every penny. Settling to a great extent merely and that means you might get Zebra Print Beats By Dre your nice tire maker computer painted over a small jar involving perfume or maybe with your event travelling bag is a thing that stars on it's own is able. Pertaining to smaller mortals like you and me, there is always trendy eye wear. The particular cliché that claims bogus could be the sincerest type of flattery is geared pertaining to solar shades, too. Many significant sunglass suppliers amount their own goods consequently huge so it translates into your demand from customers interested in low cost flea-market replicas. Most of these look-alike solar shades appear almost the same plus are made of almost the same elements, however do they furnish identical protection or maybe workmanship since the originals. Replicas may well offer short-lived fulfillment http://adidasjeremyscottstore.webs.com/ with a incredibly low cost priceFree Reprint Reports, however it is far from recommended to look pertaining to like counterfeits when they offer less protection towards the eyes. It will always be greater that will shell some more bucks while the particular protection involving eyes is anxious. Totes plus sneakers will be consequently passé. Most of these a short time, lots of consumers are partner finder their own solar shades towards the ensemble belonging to the time. When you are interested in a great monetary plus affordable approach to revise your current look, next, begin assembling your sunglass wardrobe, using many variations, seems plus shades involving solar shades. That is additionally the smallest amount of overpriced technique to keep up with the newest vogue craze while having superb awareness Beats By Dre Blue including a stunning individuality. Put that in to the contemporary scenario involving being dressed in nice bling, plus the outcome is dazzling plus eye-catching! Think my home, if you ever surface pertaining to production in diamond-encrusted solar shades, consumers are bound to remain upwards plus take notice. Plus make a number of psychological paperwork! Isn’t that precisely what fashion is focused on?
http://talktodate.com/member/blog_post_view.php?postId=31928 http://www.oshomo.com/member/blog_post_view.php?postId=45599
Louis Vuitton Polos T-Shirts (http://www.usbrandtshirtspolos.com/) 2013-05-14 05:34:49
<p>Cheap Gucci Sunglasses displays, if done correctly, will invariably draw an individual's eyes towards them with no consumer even recognizing it. Easier in theory. Consideration must be taken into consideration when selecting the style of your shows, because differing types serve well in various situations. For instance, standing shelves are perfect for situations where there's open space on the floor that should be filled. Clients who're really trying to find Gucci Belts on sale will have the ability to browse standing shelves easily. If space on the floor isn't confined, wall-mounted shelves could be a terrific way to showcase a wide range of various items simultaneously. Other kinds of discount Gucci Polos T-Shirts displays include more compact counter top models that the hurried customer may have time for you to observe, possibly making an impulse purchase. </p>
Apart from the size and shape, cheap Louis Vuitton Belts displays are available in a variety of manufacturing options. They may be produced from plastic, metal, or wood (the choice is yours!), which enables you to definitely match a method using the fittings of the store. You will find choices for rotating models, multi-purpose shows, as well as glass cases that lock to be able to promote and safeguard your most valued products. Color and logo design personalization enables you to definitely personalize your shows making the Louis Vuitton Polos T-Shirts on sale jump out much more towards the customer. Regardless of what your needs are, you will find always producers who'll create your own specific discount Hermes Belts displays.
Ultrafire Q5 2013-05-16 03:32:50
H I just wanted to comment on your blog and say I really enjoyed reading your blog here. It was very informative and I also digg the way you write! Keep it up and I'll be back soon to find out more mate.Ultrafire Q5
Adeel 2013-05-16 12:07:34
This is exactly what I was looking for. Thanks for sharing this great Information! That is very interesting smile I love reading and I am always searching for informative information like this! You are bookmarked!Buy twitter followers
bench underwear (http://www.pandahope.com/tag/bench-underwear) 2013-05-19 05:19:42
Shopping for 2013 New bench underwear - PandaHope.com
Baltimore business appraisal (http://quantivevaluations.com/valuations-in/152-business-valuations-in-baltimore.html) 2013-05-19 12:49:06
In genuineness prosperous content and very helpful in sequence. I got it my elucidation from over here. I very much urge his/her workings with the constructive enlightening information. Thanks a lot………..
Baltimore business appraisal
New comment