Yet Another Computer Build

[steve g]

It's been a while since I've posted anything. I know most of you are all playing latest builds of FTB, but since I'm stuck to a really old laptop that can barely handle Monster, I'm gonna have to bring you all down a few notches back to the days of 1.4.7. You got it, this map was designed in FTB Ultimate, and it is nearly 100% Redpower, with a bit of wireless redstone mixed in for convenience.

This is not a typical computer build. its built around a language some of you may have heard of called BrainF*ck. Its a language that has only 8 instructions:

+ : increment current cell ( mem[p]++ )
- : decrement current cell ( mem[p]-- )
> : move to next cell ( p++ )
< : move to previous cell ( p-- )
[ : if current cell is 0, jump to matching ] instruction, otherwise continue ( while (mem[p] != 0) )
] : if current cell is not 0, jump to matching [ instruction, otherwise continue ( end while )
. : output current cell value as ascii character ( putchar(mem[p]) )
, : input a character into current cell ( mem[p] = getchar() )

There are quite a few pages, references, wiki guides, code and interpreters written in many languages out on the web that can load and run a BF program. Keep in mind this is not a serious programming language, its very difficult to do anything useful (the biggest bf program i know of is a BF interpreter...written in BF itself, and a mandelbrot generator).

Typically, a BF environment provides about 30k of memory, usually unsigned bytes, and most agree on a few things like when the program should stop, how it behaves in certain conditions, etc. This map is a very
simple implementation of a BF 'computer' that can actually execute a valid BF program. The only thing it cant do is the input instruction, but im sure a little craftiness with a cc turtle can provide something useful. Maybe sometime I'll do it, but this is a very rough start

so on to the images:

Spoiler

this shows the entire map. flowing down from the middle to bottom left is the memory, 16 bytes of it. in
front of that is a single 8 bit register used as the 'p' variable in the pseudo code above, it handles selecting which byte is being written to/read from. next to the memory is the instruction circuits and motor control
circuits that drive a platform that reads the code set on that long strip you see on the top going to the right

Spoiler

this is the memory, all 16 bytes of it. these are just stacks of redpower multiplexors with adress control/clock logic underneath each stack. Thes address logic under each one uses bus transcievers to select which 8 bit register i want to read/write to, plus a reset line that will zero all the memory in one pulse.

Spoiler

in front of the memory is the 'index' register, this stores the address of the current byte im reading/writing to

Spoiler

attached to the register are 2 sets of adder circuits. one does a +1 operation, the other does a -1. They are all half adder circuits where the first bit is added with a constant 1, the rest are added to the last bit's carry. Theres a control line that will select which of these will be sent to the inputs of the register. The memory also has a pair of circuits exactly like this, also with a control line to select wether to do the +1/-1 operation. The adders take the output bits of the register/memory, and feed the result back into the register/memory input bits. clocking the register or memory will set the result. for the curious, the -1 circuit follows a simple formula: x -1 = not(not(x) + 1). hence all the not gates on the inputs and outputs.

Spoiler

connected to the memory output is a zero value circuit, this is used for the looping instructions. below that you can see the 4-16 decoder circuit, this takes the lowest 4 bits of the index register and enables a select line to the correct memory stack i want to read/write to

Spoiler

Here is where incoming instructions are decoded and sent down the proper path to execute. Executing an opcode is really just toggling 1 or 2 control lines like setting +1/-1 operation, clocking memory, and sending a pulse to the read head platform to read next instruction or start a looping task.

Spoiler

these are the platform control circuits. The platform is driven via wireless redstone. the rightmost circuit is a single step, it moves the platform ahead one tile, then starts the opcode execution. the middle circuit is for while loops, if the loop condition is 0, we need to advance the head up to the end loop instruction, then have it continue on the next instruction. the next circuit is the loop back, it moves the platform back to the top of the while loop. the rightmost circuit resets the platform back to the beginning of the code.

Spoiler

And the best part...this platform is what 'parses' the bf code into opcodes the computer can execute. There are 3 redstone tubes underneath the platform. as it moves over the stone strip, if there is a torch underneath that tube, it will send a signal up to the transmitter up on top of the platform. this lets us write the BF code, literally, onto the stone strip. This is similar to the punch card computers of old times, back before any form of magnetic media was even invented. each opcode is a 3 bit combination represented by the redstone torches. the opcodes are mapped out like this:

001 = +
010 = -
011 = >
100 = <
101 = [
110 = ]
111 = .

where 0 is air, 1 is a torch

on the back of the platform, there is an additional device. this is how i can handle loops. If a start loop instruction is found, a signal is sent to the platform to place a torch on that separate stone track. when an end loop instruction is found, the platform starts backing up. if a torch on that track is detected, it stops the platform. the loop instruction removes the torch, then places it again if the loop condition is true. If it is not true, then the platform is moved ahead until the end loop instruction and resumes normal execution. once an empty instruction is found, the platform stops.

so far, basic things work. There are still a few quirks, one big one being that for some reason, the platform will just...stop. I dont know whats causing it, i dont know if its my timing, a race condition, the frame motors acting stupid, i dont know. im still working on it, but for now, im happy with how it turned out. id love to do this in monster, see this done with project red and use mfr rednet cables to kill some of the lag, but without frames/motors..thats a tough call

 

[ratchet freak]

The instruction coding could be a bit simpler for the parser

100 = +
101 = -
010 = >
011 = <
110 = [
111 = ]

and
001 = .

that way the first 2 bits decide which type of instruction you need (inc/dec, move, loop or IO) and the last bit decides which of the 2 (which you could for example feed into a xor for the input and output of the adder circuit).

It'll save you a few gates

0-2 not gates and a AND to decide which type of instruction and then feeding the last bit into the circuit that does the operation

 

[steve g]

didnt think of it that way. ill try that.

finally worked out all the bugs. the read head doesnt 'stall' anymore and all instructions perform as advertised. at an amazingly fast speed of one op every 1.7 seconds (inchworm drives, each motor takes at least 0.8 seconds), and with no optimizations done to the code itself. an optimizing bf computer would be an interesting build

while the ram might be tight, its easily expandable to larger arrays with a little bit of extra wiring. there is no limit to the size of the program you can enter tho...the code 'tape' can be extended as far as you want.

the way its wired up now, this is what happens:

on op decode, it first goes through a 3-8 decoder, which in programming terms could be considered a switch statement.

so the 'switch' is setup like this:

   case 0: nothing, stop program; break;
+  case 1: clock mem; break; (clocking memory will automatically do a +1)
-  case 2: toggle from memory add 1 to sub 1 circuit; 
             clock mem; 
             toggle back to add 1 circuit; break;
>  case 3: clock index; break; (clocking index register automatically does a +1)
<  case 4: toggle from index add1 to sub 1 circuit; 
             clock index; 
             toggle back to add 1 circuit; break;
[  case 5: break torch on loop track;
             if (mem[p] != 0) {
                 place torch on loop track;
             } else {
                 send motor control to scan end of loop circuit
             }
             break;
]  case 6: send motor control to scan for top of loop circuit; break;
.  case 7: character output; break;

there are 4 motor circuits:

first does a single step and sends a pulse to the execution units. which ever one is selected by the 3-8 decoder is the one that will be executed.

second is a scan for top of loop controller. this one moves the head backwards and monitors the wireless redstone channel that is triggered by a torch on the loop track. when that happens, it stops moving the head and sends a signal to the op decode circuits, which should run the while loop command and resume control to the single step circuit

third is a scan for end of loop controller. this one moves the read head forward until it comes across the first end of loop instruction. once it does, it stops moving forward, and sends control back to the single step control circuit.

last is a reset circuit, this just moves the head back until it gets to a 0 (empty air) block, which should be at the top of the code track

 

[steve g]

and i see a big flaw already...with nested loops. the scan for end loop controller will fail because it stops at the first end of loop opcode it finds...not the one matched to the current loop instruction. ideas?

only one i can think of now is adding a counter, and incrementing that if a start loop instruction is found while scanning for end of loop...so if a end loop instruction is found and the counter is not 0, decrement it and keep going. thats gonna be fun to wire in....

cool thing is the track used for detecting top of while loops will do its thing properly for nested loops.