My BF CPU
Posted: Tue Dec 12, 2017 7:05 am
I decided to learn designing complex logic circuits by creating very simple and famous existing CPU, for which there are already many programs written (It'll be easier to debug it). It is BF.
At first, I've built it directly in Logiccircuit program and, somehow, I was lucky to debug it, and get it working! But then I realised, that input and output is very unhandy and I need an ASCII keyboard and ASCII display. And it has became a separate project (viewtopic.php?f=3&t=9730), even more complex than BF CPU! I've created a display, that draws ASCII symbols, but I stuck with scrolling up an entire screen when reaching the last line. And solving this was a really big step for me. It took me few monthes to understand how to do it. I leraned a lot and decided to redisign entire CPU to mutch my new style.
So here is an optimizing BF interpreter. It doesn't produce any intermediate code, like jit compilers do. It just executes instructions as they follow. So how does it optimize execution? On opening bracket it checks for zero, AND, if nonzero, it pushes the address of the next instruction after opening bracket to the stack and continue execution. On matching closing bracket it checks for zero, AND, if zero, it skips the closing bracket popping the stack, OR, if nonzero, it jumps back to pushed address. There are interpreters that just toggling dirrection and skipping back to the matching bracket. That is much slower! My interpreter only skips forward and doesn't skip backward. It even doesn't jump backward if not needed (if it was jumping and then checking for condition at opening bracket and it was zero, it would need to skip all again), since I check the condition at opening and at closing bracket, also.
The program ends successfully when zero byte is met AND there were no errors. OR, when the program is exactly 65536 bytes, AND the last instruction is reached, AND there were no errors.
It has 4 possible errors:
* Negative pointer
* Out of memory
* Unmatched "["
* Unmatched "]"
The first 2 errors are the same. The difference is that they happen from the different edges of the data tape. If you go under zero address - you'll get negative pointer. If you go beyond the "ffff" address - you'll get out of memory.
The BF standard says, that interpreter must check for matching brackets before it executes the first instruction. My interpreter dosn't do that. It starts executing directly, even if it will then stop due to unmatched bracket error.
You can find test programs in archive. And here is the site where I've found most of them:
http://www.hevanet.com/cristofd/brainfuck/
Please ask questions and report bugs here in this topic.
At first, I've built it directly in Logiccircuit program and, somehow, I was lucky to debug it, and get it working! But then I realised, that input and output is very unhandy and I need an ASCII keyboard and ASCII display. And it has became a separate project (viewtopic.php?f=3&t=9730), even more complex than BF CPU! I've created a display, that draws ASCII symbols, but I stuck with scrolling up an entire screen when reaching the last line. And solving this was a really big step for me. It took me few monthes to understand how to do it. I leraned a lot and decided to redisign entire CPU to mutch my new style.
So here is an optimizing BF interpreter. It doesn't produce any intermediate code, like jit compilers do. It just executes instructions as they follow. So how does it optimize execution? On opening bracket it checks for zero, AND, if nonzero, it pushes the address of the next instruction after opening bracket to the stack and continue execution. On matching closing bracket it checks for zero, AND, if zero, it skips the closing bracket popping the stack, OR, if nonzero, it jumps back to pushed address. There are interpreters that just toggling dirrection and skipping back to the matching bracket. That is much slower! My interpreter only skips forward and doesn't skip backward. It even doesn't jump backward if not needed (if it was jumping and then checking for condition at opening bracket and it was zero, it would need to skip all again), since I check the condition at opening and at closing bracket, also.
The program ends successfully when zero byte is met AND there were no errors. OR, when the program is exactly 65536 bytes, AND the last instruction is reached, AND there were no errors.
It has 4 possible errors:
* Negative pointer
* Out of memory
* Unmatched "["
* Unmatched "]"
The first 2 errors are the same. The difference is that they happen from the different edges of the data tape. If you go under zero address - you'll get negative pointer. If you go beyond the "ffff" address - you'll get out of memory.
The BF standard says, that interpreter must check for matching brackets before it executes the first instruction. My interpreter dosn't do that. It starts executing directly, even if it will then stop due to unmatched bracket error.
You can find test programs in archive. And here is the site where I've found most of them:
http://www.hevanet.com/cristofd/brainfuck/
Please ask questions and report bugs here in this topic.