Update: there is now a downloadable game downthread.
Like one or two other people, I saw (and ). I also wondered how it worked, or rather, how one might go around designing such a thing.
A few days later I bought Minecraft and started playing.
Today, I implemented what I believe is a functionally identical ALU in MCRedstoneSim. I shall now proceed to describe it in agonizing detail. Schematic files will be provided.
Some caveats:
[*:2j64g33d] I haven’t built any part of it in-game.
[*:2j64g33d] I haven’t attempted to analyse theinternetftw’s design, and I haven’t read The Elements of Computing Systems. My design is based on the control bits shown in the first video and an understanding of how they’d be used in programming.
[*:2j64g33d] I don’t claim to be a redstone wizard. Most of the components are based on designs from the forum and wiki. The original parts can probably be improved.
[*:2j64g33d] I haven’t included the data busses, which account for a lot of bulk in theinternetftw’s design.
[*:2j64g33d] The “output is zero” flag is not implemented. This is just a NOR of all the output bits, though.
The design took about six and a half hours. The result takes up 32×119×9 blocks (sixteen 6+1×27×5 logic elements, control busses and some interface), and uses 2237 wires and 687 torches.
Specification
The ALU takes two sixteen-bit inputs (X and Y) and six control bits, and produces a sixteen-bit output (OUT) plus an overflow flag. The control bits (with my names) are:
[*:2j64g33d] ZX: if 1, treat X as all-zeros.
[*:2j64g33d] NX: if 1, invert X (that is, flip all bits). Applied after ZX, so if both are set X is treated as all ones. The result of applying ZX and NX to X is referred to as X'.
[*:2j64g33d] ZY: like ZX, but for the Y input.
[*:2j64g33d] NY: guess.
[*:2j64g33d] F (function): if 0, the preliminary output O' is the bitwise AND of X' and Y'. If 1, O' is the low sixteen bits of the sum of X' and Y'. The seventeenth bit is the overflow flag, FO.
[*:2j64g33d] NO: if 0, the output OUT is equal to O'. If 1, OUT is the bitwise inverse of O'.
Currently, FO is not affected by NO, and is meaningless of F is 0.
High-level design
The design consists of sixteen identical logic elements, which each takes two input bits Xn and Yn, an input carry bit Ci for ripple-carry adding, and the six control bits on perpendicular buses. Each element produces an output bit On and an output carry bit Co. Getting the bits in and out of the ALU is beyond the scope of this project; I’m just using levers and trailing wires.
Input filters
The first thing the logic element needs to do is apply the ZX, NX, ZY and NY flags to the input. This requires two functionally identical circuits I call input filters.
The obvious way to implement this would be (X ∧ ¬ZX) ⊻ NX. However, an equivalent option with lower latency is (¬X ∨ ZX) = NX.
Quote from Digression »
To see this, first note that equality (aka XNOR) with one negated term implements inversion: if NX is 0, ¬X = NX is X, while if NX is 1, it’s ¬X. (X ∧ ¬ZX) = (¬X ∨ ZX) by De Morgan’s laws.
The wiki has several XNOR gates. I chose variant C for its compact design, low latency and narrow profile. By running the output across the top of the gate and the X input into an inverter attached to the side, the input filter including its three inputs is three wide and has a three-tick latency.
Quote from Digression »
If there was an input bus, some of the logic elements would be able to get pre-inverted inputs to save a tick. It would be best to arrange for the low-order logic element to be pre-inverted, because the overall latency of the addition operation depends on the half-add latency of the low-order element and the total carry latency across all elements.
Also, the three-tick latency is only incurred if the X goes low while NX is high. This could be avoided with a good instruction fetcher.
Here’s a model input filter. X is on the left, and the top two levers are ZX and NX in order.
I initially placed the two filters directly opposite each other, but I ended up staggering them by two blocks to be able to fit the four control bit inputs between them in a two-block space. The ZX and NX busses will run on bridges and connect to the north filter, while ZY and NY run in tunnels and connect to the south filter. ZY is provided by a torch immediately under the protruding wired block, while the others run on stairs. The buses and their controls are included in the schematic file but left out of the image for clarity.
Operations
The input filters produce the values X' and Y'. The next step is to add these and AND them. We'll select the appropriate value based on the F flag later.
The adder is vandrien’s 5×7×3 design with no modifications. (This is the niftiest part of the entire design – if I had to design my own adder the ALU would be twice as big and significantly slower. Thanks, vandrien!) The Y' line is rerouted slightly. The switch at the top is Ci, and the dangling wire at the bottom is Co.
Quote from Performance »
The worst-case latency of the adder is 5 ticks, but carries are generated, handled and propagated in two ticks. By the time the carry ripple reaches the high-order element, its half-add will be complete, so the carry latency is all that matters for overall time.
I originally had a separate NAND gate on top of the adder. While decomposing the design from this writeup, I noticed that the X' wire wasn’t connected, but it was working anyway. Turns out I was accidentally extracting an AND from the adder and then NANDing that with Y'… the revised design just uses the AND from the adder directly. The source is either of the two opposing torches on the input side of layer 2 of the adder.
Output muxer
The next step is to select the appropriate preliminary output, O'. This requires a selector (muxer) circuit which takes three inputs, A, B and S, and outputs A if S is 1 and B if S is 0 – that is, (A ∧ S) ∨ (B ∧ ¬S). Here, S is in the middle to avoid crossing anything. (It will be routed through a tunnel.)
Quote from Performance »
The latency of the muxer is three when changing S and 2 for anything else. In a full CPU, it’s reasonable to assume S (F) will be set before the other inputs are ready.
Output filter
The output filter is much like the input filter, but without a zero flag. It consists of an XNOR gate (wiki type C again) which takes O' from the muxer and ¬NO from a tunnelled bus.
And there you have it: a one-bit ALU. Here’s a block diagram:
(Wouldn’t it be nice if you could do that in the simulator?)
The complete sixteen-bit version consists of sixteen of these side by side, with their carry flags chained together (low-order bit at the top, high-order bit at the bottom). I’ll spare you the details of working out the control bus wiring and stuff. The final design consists of eight identical two-element modules, with one set of bus repeaters per module, so the bus latency averages one tick per bit. Here it is, calculating its own redstone cost (2237 + 687 = 2924, or 1000 1011 1101 + 0010 1010 1111 = 1011 0110 1100):
Operations
It may not be immediately obvious how an ALU with only two operations is enough for useful computation, but the input and output flags let you do quite a lot. Some examples:
[*:2j64g33d] The output muxer could probably be made smaller. It’s pretty much the first design that came to mind.
[*:2j64g33d] It looks like I could shave off two columns of length, one on each side of the op logic block. The output muxer would need to be flipped over, and the control bit bus negated.
[*:2j64g33d] The input filter section is seven wide (including insulation), while the other blocks are six. I think it’s possible to make the input filter section one block narrower by flipping the filters so the control inputs are on the outside, and sharing the inputs between adjacent elements. The input order would then alternate (the first element would have X₀ on top and Y₀ on the bottom, and the second would have Y₁ on top and X₁ on the bottom).
[*:2j64g33d] Performance profiling. An add should take about 40 ticks, but I haven’t timed it.
[*:2j64g33d] Carry look-ahead adder for moar faster. By which I mean “slightly less slow.”
[*:2j64g33d] Other computer components: program counter, I/O controller, RAM, ROM. I probably won’t bother with all of them.
FAQ
[*:2j64g33d] What’s the point?
I don’t understand the question.
Seriously, if you’re going to ask what the point is of doing something for fun in a game, why are you even on this forum?
Edit: adapted standard Hack flag names (mostly the same as I was using) and updated Operations section, based on this presentation (slide 24).
If anything, the main (Largest) piece of schematic could be refined slightly - I think itd be interesting to imitate the greatness by making a smaller, or even just a differently organised version of the same thing.
If anything, the main (Largest) piece of schematic could be refined slightly - I think itd be interesting to imitate the greatness by making a smaller, or even just a differently organised version of the same thing.
I’m not sure what you mean. Other than implementing the same operations, my design is unrelated to theinternetftw’s, so it’s at the very least “a differently organised version”. And I wasn’t going to make a point of it, but it’s a lot smaller.
Very impressive:) Much more logic than I was going to impament in mine. I remembered a while back a paper someone wrote on making a 32 micro-cell computer out of a CLPD. It wasn't much, but it was a good base for mine.
Basically, it had 4 instructions. ADD, NOR, STA, JNC. JNC would clear the carry regardless if it jumped or not. It was all indirect lookups to a 64 byte sram. The op and address fit in one 8-bit word and only took two clock cycles for each instruction (except for JNC) "This is it!", I said, "I can make this!"
Then I figured out its nearly imposable to make a damn sram cell in this damn game:P I changed it more toward a Harvard architecture. This made smaller and able to do a 4 bit computer with an AC and up to 16 registers (Only two extra's are made though). Still use 8 bits, but now the 5 bit is direct or indirect NOR to the AC. Or something, I haven't put down the control lines yet. The problem now is the damn PC. The original idea I had was to have this one huge shift register. Using only one latch per line of rom, it would just clock one pin to read the rom up an address and the other pin for the other way. The program would never know where it exactly was in the rom, but you could technically have an unlimited sized program rom. But, after days of trying, I still haven't come up with a good shift register that just moves a bit up and down the chain:P
Anyway, here is my schematic for my system. Nothing is labeled. so to describe from the switches to the left, top to bottom.
The four switches to the top is the data in from the rom for any ALU or ST function. Using your design for the adder, I added a NOR function to each line and tied the final carry to a RS latch.
Button: Resets the end carry latch.
Switch: Turns the output to the NOR or ADD functions.
Button: Resets the inverted data buffer. It locks the lines from a register. It MUST be pressed first before you do any ALU function.
Button: Moves the AC to the data buffer. Has to be pressed after all the math is done.
Button: Resets the data line display. Kind of a debug view, showing you whats on the line ready to be moved to a register or ALU.
Haven't tested the bottom part much
Button: This flashes the clock line to the two extra registers. If its on write, it will latch the data on the data bus, if its read, it will latch its data to the bus
Switch: Toggles between register R0 and R1
Switch: Toggles between reading the register or writing.
I know, I am looking at the design now and thinking I can get rid of the AC and just put some ram in there, but it needs to be rewired and I am tired:P
I'm back. I don't know how you inspired me, but I just created my sram module. One of the things that I was having problems with was that you cannot use the same line to read, set AND select without having way to many lines. After more web searching, I found this old technology called "Mercury Delay". Basicly, in my search for a ring counter, I found somone did it old tech style. Anyway, It helped me make This!
I have given up on the original PC less deisgn. I found a good link on somone building their own memory decoder here. Being an amatur I never would of thought of using a bus for a selecter! It even eliminates the need for a counter, I can do it with my ALU!
Here is the new design for the 4 to 16 decoder. Whats really nice about this design is you can put two of them side by side and suddenly have a 8-256. I doubt I will ever use that much ram though.
Going to start having to make a website to put these on. No one is updating the wiki and I am not much of a web poster:P
As a side note, Paint for Windows 7 is honestly not bad. Fairly decent for quick stuff.
Improved input filter (and control bus) design, as outlined in first post.
The input filters now have the control inputs outwards, with one space between them, allowing the entire element to be one block narrower. The staggering is also removed, saving two blocks of length, with the control bus zig-zagging instead. Control inputs are torches (for isolation) on top of one torch in the appropriate bus repeater. The busses are negated.
This arrangement increases control bit latency. Wiring the low-order bit’s input differently could eliminate this delay for the add operation.
Since control bits are shared between adjacent input filters in different cells, the input bit order alternates: X₀, Y₀, Y₁, X₁, X₂, Y₂, Y₃, X₃. This will be rather inconvenient to use directly, but will be hidden by appropriate input bus wiring. The control bit order has also changed, to ZX, ZY, NX, NY.
The outputs adder stage will be moved up and back three steps, eliminating the staircase.
I’m not sure what I’m going to do about the output side yet.
Flipping the output muxer over and smashing it into the side of the adder worked out nicely, saving two columns. The select input (circled) is again fed by the NO bus repeater. The bus itself runs at ground level.
The output negator XNOR can then be stuck right on the end of that, one step below, with no wiring gap. The control input is tunnelled, and connected to the circled block using two vertical torches. (The extra latency is not a problem, since the data has to go through all the previous blocks first.)
The logic element is now 5+1×19×8 blocks (down from 6+1×27×5).
Schematic (4 bits wide). I’ll expand to sixteen bits and test it properly when I’ve had a look at Hell. ;-)
While waiting for the update server to come back to life, I built a one-bit element in-game.
Totally legit! Many sheep were seriously annoyed in the making of this device. (Wooden parts are control lines, wool is the structure of the logic element, stone is support structure, access ladders and so forth.)
Here’s the full sixteen-bit schematic, again set to calculate its own component cost (including control interface): 1858 wires (0111 0100 0010) + 748 torches (0010 1110 1100) = 2606 redstone (1010 0010 1110). The 61 extra torches are the vertical-stack control line connections and input inverters, and the 379 fewer wires are space savings and simpler control busses.
The schematic is 26×104×12; 7 columns and 7 rows are interface, and 4 layers are control busses. The logic is 19×(5 × 16 + 17 = 97)×8.
In addition to the ALU instructions, the Hack architecture has only one more instruction, the @ instruction (or, more traditionally, “load immediate”). This loads a fifteen-bit value into register A. This can be integrated into the ALU by simply whacking another muxer on the end. This muxer takes the ALU output and the corresponding instruction bit (always zero for the high-order bit) as inputs, and the relevant control bit as the selector input.
Rather than add another switch to each element, I added a complete instruction bus. This can take either an @ instruction or an ALU instruction. Both use very simple encodings, so the decoder just has to run wires to the right control inputs. The instruction codings are as follows:
@ instruction:
0DDD DDDD DDDD DDDD
ALU: Copy the instruction word to the output bus.
Output controller: write ALU output to register A.
Program counter: increment unconditionally.
Logic instruction:
111A CCCC CCDD DJJJ
The bits in each field are numbered from left (high-order) to right, so C₁ is adjacent to A and C₆ is adjacent to D₁.
ALU: Set ZX to C₁, NX to C₂, ZY to C₃, NY to C₄, F to C₅, and NO to C₆.
Input controller: if A is 0, set Y to register A. Otherwise, set Y to the contents of memory at the address specified by register A (referred to as RAM[A] or M). (X is always set to register D).
Output controller: if D₁, write to register A. If D₂, write to register D. If D₃, write to RAM[A] (presumably the value of A before updating it). Any combination is valid.
Program counter: given condition bits NG (the high bit of the ALU output) and ZR (the NOR of all the output bits), jump to ROM[A] if (J₁ ∧ NG) ∨ (J₂ ∧ ZR) ∨ (J₃ ∧ (NG ⊽ ZR)), otherwise to the next instruction (dur). All combinations of J bits are valid.
(Note: RAM and ROM addresses are word addresses, or to put it differently, both the word size and the byte size is 16 bits.)
Here’s the instruction “DM=D+A” entered into the input bus (top right, levels 6–7):
The bits are in reverse order for routing reasons. (If you were standing in front of it facing south, it would be the right way around.) The three bits on the right are the logic instruction prefix (currently only the top bit matters, but the other two could be used for new instructions). The colour-coded ones are the control bits for logic ops; from right to left, ZX, NX, ZY, NY, F and NO. Destination bits D₂ and D₃ are set, but of course do nothing since there’s no output controller, and the condition bits are clear for no jump.
The logic element outputs are now in the middle of the schematic, so I added an output bus too (ending top right, layers 13-14). Here it is showing the value 5285 (0001 0100 1010 0101), once again backwards.
Schematic, set to calculate its own component cost in accordance with ancient tradition: 4232 wires (0001 0000 1000 1000) + 1053 torches (0000 0100 0001 1101) = 5285 redstone (0001 0100 1010 0101).
Design note: seven of the input bits are essentially duplicated in the control bit busses. This could be avoided, but the @ instruction would be slower, and it’s not clear that the recovered space could be used for anything since it’s underneath the output bus. I’ll revisit this if/when the other components are designed.
Yep, I knew that it wouldn't take long for someone to *greatly* improve on what I'd made. Mine's so large due to my experimental start: I built modular components one by one, making a 16-bit muxer, then a 16-bit adder, etc., and cobbled an ALU together out of various complete parts.
Plus I like being able to easily follow the signal through the machine; there's very little obfuscation through optimization.
Congratulations for shrinking it by so much, it's very impressive. I just hope nobody beats me to the punch of finishing the damn thing (though at the pace you churned out this ALU, that seems likely = / )
Yep, I knew that it wouldn't take long for someone to *greatly* improve on what I'd made. Mine's so large due to my experimental start: I built modular components one by one, making a 16-bit muxer, then a 16-bit adder, etc., and cobbled an ALU together out of various complete parts.
Plus I like being able to easily follow the signal through the machine; there's very little obfuscation through optimization.
I saw Vandrien’s tiny adder and felt it needed a suitable context. :-)
Quote from theinternetftw »
Congratulations for shrinking it by so much, it's very impressive. I just hope nobody beats me to the punch of finishing the damn thing (though at the pace you churned out this ALU, that seems likely = / )
I don’t currently intend to finish it, but then, I didn’t originally intend to build the busses either. Things like this tend to eat away at one’s mind… but I guess you’d know.
Like one or two other people, I saw (and ). I also wondered how it worked, or rather, how one might go around designing such a thing.
A few days later I bought Minecraft and started playing.
Today, I implemented what I believe is a functionally identical ALU in MCRedstoneSim. I shall now proceed to describe it in agonizing detail. Schematic files will be provided.
Some caveats:
[*:2j64g33d] I haven’t built any part of it in-game.
[*:2j64g33d] I haven’t attempted to analyse theinternetftw’s design, and I haven’t read The Elements of Computing Systems. My design is based on the control bits shown in the first video and an understanding of how they’d be used in programming.
[*:2j64g33d] I don’t claim to be a redstone wizard. Most of the components are based on designs from the forum and wiki. The original parts can probably be improved.
[*:2j64g33d] I haven’t included the data busses, which account for a lot of bulk in theinternetftw’s design.
[*:2j64g33d] The “output is zero” flag is not implemented. This is just a NOR of all the output bits, though.
The design took about six and a half hours. The result takes up 32×119×9 blocks (sixteen 6+1×27×5 logic elements, control busses and some interface), and uses 2237 wires and 687 torches.
Specification
The ALU takes two sixteen-bit inputs (X and Y) and six control bits, and produces a sixteen-bit output (OUT) plus an overflow flag. The control bits (with my names) are:
[*:2j64g33d] ZX: if 1, treat X as all-zeros.
Currently, FO is not affected by NO, and is meaningless of F is 0.[*:2j64g33d] NX: if 1, invert X (that is, flip all bits). Applied after ZX, so if both are set X is treated as all ones. The result of applying ZX and NX to X is referred to as X'.
[*:2j64g33d] ZY: like ZX, but for the Y input.
[*:2j64g33d] NY: guess.
[*:2j64g33d] F (function): if 0, the preliminary output O' is the bitwise AND of X' and Y'. If 1, O' is the low sixteen bits of the sum of X' and Y'. The seventeenth bit is the overflow flag, FO.
[*:2j64g33d] NO: if 0, the output OUT is equal to O'. If 1, OUT is the bitwise inverse of O'.
High-level design
The design consists of sixteen identical logic elements, which each takes two input bits Xn and Yn, an input carry bit Ci for ripple-carry adding, and the six control bits on perpendicular buses. Each element produces an output bit On and an output carry bit Co. Getting the bits in and out of the ALU is beyond the scope of this project; I’m just using levers and trailing wires.
Input filters
The first thing the logic element needs to do is apply the ZX, NX, ZY and NY flags to the input. This requires two functionally identical circuits I call input filters.
The obvious way to implement this would be (X ∧ ¬ZX) ⊻ NX. However, an equivalent option with lower latency is (¬X ∨ ZX) = NX.
The wiki has several XNOR gates. I chose variant C for its compact design, low latency and narrow profile. By running the output across the top of the gate and the X input into an inverter attached to the side, the input filter including its three inputs is three wide and has a three-tick latency.
Here’s a model input filter. X is on the left, and the top two levers are ZX and NX in order.
Schematic
I initially placed the two filters directly opposite each other, but I ended up staggering them by two blocks to be able to fit the four control bit inputs between them in a two-block space. The ZX and NX busses will run on bridges and connect to the north filter, while ZY and NY run in tunnels and connect to the south filter. ZY is provided by a torch immediately under the protruding wired block, while the others run on stairs. The buses and their controls are included in the schematic file but left out of the image for clarity.
Full schematic (Control bits in order: ZX, NX, ZY, NY)
Operations
The input filters produce the values X' and Y'. The next step is to add these and AND them. We'll select the appropriate value based on the F flag later.
The adder is vandrien’s 5×7×3 design with no modifications. (This is the niftiest part of the entire design – if I had to design my own adder the ALU would be twice as big and significantly slower. Thanks, vandrien!) The Y' line is rerouted slightly. The switch at the top is Ci, and the dangling wire at the bottom is Co.
I originally had a separate NAND gate on top of the adder. While decomposing the design from this writeup, I noticed that the X' wire wasn’t connected, but it was working anyway. Turns out I was accidentally extracting an AND from the adder and then NANDing that with Y'… the revised design just uses the AND from the adder directly. The source is either of the two opposing torches on the input side of layer 2 of the adder.
Full schematic
Output muxer
The next step is to select the appropriate preliminary output, O'. This requires a selector (muxer) circuit which takes three inputs, A, B and S, and outputs A if S is 1 and B if S is 0 – that is, (A ∧ S) ∨ (B ∧ ¬S). Here, S is in the middle to avoid crossing anything. (It will be routed through a tunnel.)
Schematic
Plugged in:
Full schematic (Control bits: ZX, NX, ZY, NY, F)
Output filter
The output filter is much like the input filter, but without a zero flag. It consists of an XNOR gate (wiki type C again) which takes O' from the muxer and ¬NO from a tunnelled bus.
Full schematic (Control bits: ZX, NX, ZY, NY, F, NO)
And there you have it: a one-bit ALU. Here’s a block diagram:
(Wouldn’t it be nice if you could do that in the simulator?)
The complete sixteen-bit version consists of sixteen of these side by side, with their carry flags chained together (low-order bit at the top, high-order bit at the bottom). I’ll spare you the details of working out the control bus wiring and stuff. The final design consists of eight identical two-element modules, with one set of bus repeaters per module, so the bus latency averages one tick per bit. Here it is, calculating its own redstone cost (2237 + 687 = 2924, or 1000 1011 1101 + 0010 1010 1111 = 1011 0110 1100):
Full schematic
Future directions
[*:2j64g33d] The output muxer could probably be made smaller. It’s pretty much the first design that came to mind.
[*:2j64g33d] It looks like I could shave off two columns of length, one on each side of the op logic block. The output muxer would need to be flipped over, and the control bit bus negated.
[*:2j64g33d] The input filter section is seven wide (including insulation), while the other blocks are six. I think it’s possible to make the input filter section one block narrower by flipping the filters so the control inputs are on the outside, and sharing the inputs between adjacent elements. The input order would then alternate (the first element would have X₀ on top and Y₀ on the bottom, and the second would have Y₁ on top and X₁ on the bottom).
[*:2j64g33d] Performance profiling. An add should take about 40 ticks, but I haven’t timed it.
[*:2j64g33d] Carry look-ahead adder for moar faster. By which I mean “slightly less slow.”
[*:2j64g33d] Other computer components: program counter, I/O controller, RAM, ROM. I probably won’t bother with all of them.
FAQ
[*:2j64g33d] What’s the point?
I don’t understand the question.
Seriously, if you’re going to ask what the point is of doing something for fun in a game, why are you even on this forum?
Edit: adapted standard Hack flag names (mostly the same as I was using) and updated Operations section, based on this presentation (slide 24).
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE
In any case, good luck!
http://www.youtube.com/user/Caeviens?fe ... 96B9817BC6
I’m not sure what you mean. Other than implementing the same operations, my design is unrelated to theinternetftw’s, so it’s at the very least “a differently organised version”. And I wasn’t going to make a point of it, but it’s a lot smaller.
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE
Basically, it had 4 instructions. ADD, NOR, STA, JNC. JNC would clear the carry regardless if it jumped or not. It was all indirect lookups to a 64 byte sram. The op and address fit in one 8-bit word and only took two clock cycles for each instruction (except for JNC) "This is it!", I said, "I can make this!"
Then I figured out its nearly imposable to make a damn sram cell in this damn game:P I changed it more toward a Harvard architecture. This made smaller and able to do a 4 bit computer with an AC and up to 16 registers (Only two extra's are made though). Still use 8 bits, but now the 5 bit is direct or indirect NOR to the AC. Or something, I haven't put down the control lines yet. The problem now is the damn PC. The original idea I had was to have this one huge shift register. Using only one latch per line of rom, it would just clock one pin to read the rom up an address and the other pin for the other way. The program would never know where it exactly was in the rom, but you could technically have an unlimited sized program rom. But, after days of trying, I still haven't come up with a good shift register that just moves a bit up and down the chain:P
Download here
Anyway, here is my schematic for my system. Nothing is labeled. so to describe from the switches to the left, top to bottom.
The four switches to the top is the data in from the rom for any ALU or ST function. Using your design for the adder, I added a NOR function to each line and tied the final carry to a RS latch.
Button: Resets the end carry latch.
Switch: Turns the output to the NOR or ADD functions.
Button: Resets the inverted data buffer. It locks the lines from a register. It MUST be pressed first before you do any ALU function.
Button: Moves the AC to the data buffer. Has to be pressed after all the math is done.
Button: Resets the data line display. Kind of a debug view, showing you whats on the line ready to be moved to a register or ALU.
Haven't tested the bottom part much
Button: This flashes the clock line to the two extra registers. If its on write, it will latch the data on the data bus, if its read, it will latch its data to the bus
Switch: Toggles between register R0 and R1
Switch: Toggles between reading the register or writing.
I know, I am looking at the design now and thinking I can get rid of the AC and just put some ram in there, but it needs to be rewired and I am tired:P
My new version of Redstone Simulator
Main Code Site: http://code.google.com/p/red-stone-simulator/
lets hope you dont get any in your code.
My new version of Redstone Simulator
Main Code Site: http://code.google.com/p/red-stone-simulator/
Almost makes me want to go study electrical engineering...
I have given up on the original PC less deisgn. I found a good link on somone building their own memory decoder here. Being an amatur I never would of thought of using a bus for a selecter! It even eliminates the need for a counter, I can do it with my ALU!
Here is the new design for the 4 to 16 decoder. Whats really nice about this design is you can put two of them side by side and suddenly have a 8-256. I doubt I will ever use that much ram though.
Going to start having to make a website to put these on. No one is updating the wiki and I am not much of a web poster:P
As a side note, Paint for Windows 7 is honestly not bad. Fairly decent for quick stuff.
My new version of Redstone Simulator
Main Code Site: http://code.google.com/p/red-stone-simulator/
The input filters now have the control inputs outwards, with one space between them, allowing the entire element to be one block narrower. The staggering is also removed, saving two blocks of length, with the control bus zig-zagging instead. Control inputs are torches (for isolation) on top of one torch in the appropriate bus repeater. The busses are negated.
This arrangement increases control bit latency. Wiring the low-order bit’s input differently could eliminate this delay for the add operation.
Since control bits are shared between adjacent input filters in different cells, the input bit order alternates: X₀, Y₀, Y₁, X₁, X₂, Y₂, Y₃, X₃. This will be rather inconvenient to use directly, but will be hidden by appropriate input bus wiring. The control bit order has also changed, to ZX, ZY, NX, NY.
The outputs adder stage will be moved up and back three steps, eliminating the staircase.
I’m not sure what I’m going to do about the output side yet.
Schematic
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE
The output negator XNOR can then be stuck right on the end of that, one step below, with no wiring gap. The control input is tunnelled, and connected to the circled block using two vertical torches. (The extra latency is not a problem, since the data has to go through all the previous blocks first.)
The logic element is now 5+1×19×8 blocks (down from 6+1×27×5).
Schematic (4 bits wide). I’ll expand to sixteen bits and test it properly when I’ve had a look at Hell. ;-)
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE
Totally legit! Many sheep were seriously annoyed in the making of this device. (Wooden parts are control lines, wool is the structure of the logic element, stone is support structure, access ladders and so forth.)
Here’s the full sixteen-bit schematic, again set to calculate its own component cost (including control interface): 1858 wires (0111 0100 0010) + 748 torches (0010 1110 1100) = 2606 redstone (1010 0010 1110). The 61 extra torches are the vertical-stack control line connections and input inverters, and the 379 fewer wires are space savings and simpler control busses.
The schematic is 26×104×12; 7 columns and 7 rows are interface, and 4 layers are control busses. The logic is 19×(5 × 16 + 17 = 97)×8.
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE
Rather than add another switch to each element, I added a complete instruction bus. This can take either an @ instruction or an ALU instruction. Both use very simple encodings, so the decoder just has to run wires to the right control inputs. The instruction codings are as follows:
@ instruction:
0DDD DDDD DDDD DDDD
ALU: Copy the instruction word to the output bus.
Output controller: write ALU output to register A.
Program counter: increment unconditionally.
Logic instruction:
111A CCCC CCDD DJJJ
The bits in each field are numbered from left (high-order) to right, so C₁ is adjacent to A and C₆ is adjacent to D₁.
ALU: Set ZX to C₁, NX to C₂, ZY to C₃, NY to C₄, F to C₅, and NO to C₆.
Input controller: if A is 0, set Y to register A. Otherwise, set Y to the contents of memory at the address specified by register A (referred to as RAM[A] or M). (X is always set to register D).
Output controller: if D₁, write to register A. If D₂, write to register D. If D₃, write to RAM[A] (presumably the value of A before updating it). Any combination is valid.
Program counter: given condition bits NG (the high bit of the ALU output) and ZR (the NOR of all the output bits), jump to ROM[A] if (J₁ ∧ NG) ∨ (J₂ ∧ ZR) ∨ (J₃ ∧ (NG ⊽ ZR)), otherwise to the next instruction (dur). All combinations of J bits are valid.
(Note: RAM and ROM addresses are word addresses, or to put it differently, both the word size and the byte size is 16 bits.)
Here’s the instruction “DM=D+A” entered into the input bus (top right, levels 6–7):
The bits are in reverse order for routing reasons. (If you were standing in front of it facing south, it would be the right way around.) The three bits on the right are the logic instruction prefix (currently only the top bit matters, but the other two could be used for new instructions). The colour-coded ones are the control bits for logic ops; from right to left, ZX, NX, ZY, NY, F and NO. Destination bits D₂ and D₃ are set, but of course do nothing since there’s no output controller, and the condition bits are clear for no jump.
The logic element outputs are now in the middle of the schematic, so I added an output bus too (ending top right, layers 13-14). Here it is showing the value 5285 (0001 0100 1010 0101), once again backwards.
Schematic, set to calculate its own component cost in accordance with ancient tradition: 4232 wires (0001 0000 1000 1000) + 1053 torches (0000 0100 0001 1101) = 5285 redstone (0001 0100 1010 0101).
Design note: seven of the input bits are essentially duplicated in the control bit busses. This could be avoided, but the @ instruction would be slower, and it’s not clear that the recovered space could be used for anything since it’s underneath the output bus. I’ll revisit this if/when the other components are designed.
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE
Schematic, set up to calculate 6357 (0001 1000 1101 0101) + 1177 (0000 0100 1001 1001) = 7534 (0001 1101 0110 1110).
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE
..... @.@
Plus I like being able to easily follow the signal through the machine; there's very little obfuscation through optimization.
Congratulations for shrinking it by so much, it's very impressive. I just hope nobody beats me to the punch of finishing the damn thing (though at the pace you churned out this ALU, that seems likely = / )
I saw Vandrien’s tiny adder and felt it needed a suitable context. :-)
I don’t currently intend to finish it, but then, I didn’t originally intend to build the busses either. Things like this tend to eat away at one’s mind… but I guess you’d know.
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE
Calculating 42-7 = 35 (100011).
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE