RC12. Building an ALU
Daily dispatches from my 12 weeks at the Recurse Center in Summer 2023
Here’s an ALU.
Looks confusing. And, well, it sort of is, at least at first. The ALU is the arithmetic logic unit, and it does all sorts of cool things. This one takes as its input two 16-bit numbers, x and y, as well as six 1-bit flags:
zx: if this is 1, zero thexinput, otherwise leavexas isnx: if this is 1, negate thexinput, otherwise leave as iszy: if this is 1, zero theyinput, otherwise leaveyas isny: if this is 1, negate theyinput, otherwise leaveyas isf: function selector – if 1, then returnx + y, otherwise returnx & yno: if this is 1, negate the output
This ALU also has three outputs:
- `f(x, y): this is the 16-bit integer that is the result of all of the above operations
ng: this is a flag that indicates whether the resulting output is a negative number – 1 means yes, 0 means nozr: this is a flag that indicates whether the resulting output is 0 – 1 means yes, 0 means no
As a result of the 6 input flags, an amazing number of operations can be performed on the incoming x and y integers. Here’s an abbreviated truth table that shows the various functions and outputs that can be toggled by turning on and off specific input flags:
| zx | nx | zy | ny | f | no | out |
|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | -1 |
| 0 | 0 | 1 | 1 | 0 | 0 | x |
| 1 | 1 | 0 | 0 | 0 | 0 | y |
| 0 | 0 | 1 | 1 | 0 | 1 | !x |
| 1 | 1 | 0 | 0 | 0 | 1 | !y |
| 0 | 0 | 1 | 1 | 1 | 1 | -x |
| 1 | 1 | 0 | 0 | 1 | 1 | -y |
| 0 | 1 | 1 | 1 | 1 | 1 | x+1 |
| 1 | 1 | 0 | 1 | 1 | 1 | y+1 |
| 0 | 0 | 1 | 1 | 1 | 0 | x-1 |
| 1 | 1 | 0 | 0 | 1 | 0 | y-1 |
| 0 | 0 | 0 | 0 | 1 | 0 | x+y |
| 0 | 1 | 0 | 0 | 1 | 1 | x-y |
| 0 | 0 | 0 | 1 | 1 | 1 | y-x |
| 0 | 0 | 0 | 0 | 0 | 0 | x&y |
| 0 | 1 | 0 | 1 | 0 | 1 | x|y |
What wasn’t immediately obvious to me until after implementing this is that the input integers x and y are fed through a kind of pipeline, zeroing them out and/or negating them per the nx, zx, ny, and zy flags, and then operated on according to the f flag, and then negated or not depending on the no flag, and then output in three different ways. As a diagram this flow of information is easier to follow:
Effectively what’s happening in the first few steps is that I’m using a series of Mux16s as almost conditional statements that choose between one of two inputs.
- The first, leftmost Mux16s, for instance, each take in an input integer (
xory) as one of their inputs and 0 as their other, so that ifzx/zyis toggled off, thex/yinput is selected, otherwise the0s are selected. - The next Mux16 pair is responsible for negating the input if needed, so each has the result of the previous Mux16 as one input and its negation for the other, and these are selected using the
nx/nybit. - The results of the
x->zx->nxandy->zy->nyoperations are both added together andANDed together, and these two results are fed into yet another Mux 16, which is toggled by thefselector bit. Iffis True/1, then the result of the adder is selected, otherwise the result of the And16 is selected. - Finally, we pass the result of the above Mux16 and its negation to one final Mux16, which is toggled with the
nobit and is responsible for selecting the negated or non-negated output.
At this point it’s just a matter of segmenting the output in a few ways: we output the 16-bit result (out) as well as flags to indicate whether the result is negative (ng) or zero (zr).
- To determine whether the result is zero, we simpy have to
ORall 16 bits together, which here I am using an Or16Way to accomplish. If any of the bits is 1, the result of this Or16Way will also be 1. Only if all the bits are zero (and thus the integer that they represent is also zero) will the result of this Or16Way be 0. Becausezris 1 if all the bits are 0, we have to negate the result. - As for the
ngflag, we simply need to return the most significant bit, which is the sign indicator here. If the most significant bit is 1, that means we’re dealing with a negative number andngtoo should be set to 1. Otherwise, the output is positive andngwill be 0.
Simulated Examples
Because following the diagram can be a bit tricky, I wrote a little simulator that shows the various transformations that are happening to the inputs. Let’s look at a few examples.
Example 1: f(x, y) = y - x
According to the chart, we should expect f(x, y) in this case to be y - x:
ALU_sim(x='10010111', y='00001010', zx=0, nx=0, zy=0, ny=1, f=1, no=1)
x y
INPUT: 10010111 => -105 00001010 => 10
| |
zx=0 10010111 => -105 |
| |
nx=0 10010111 => -105 |
| |
zy=0 | 00001010 => 10
| |
ny=1 | 11110101 => -11
| |
---------------------
|
|
f: + 10001100 => -116
|
no=1 01110011 => 115
|
---------------------
OUTPUT: | | |
ng 0 | |
| |
zr 0 |
|
f(x, y) 01110011 => 115
Example 2: f(x, y) = x - y
ALU_sim(x='11001011', y='00100011', zx=0, nx=1, zy=0, ny=0, f=1, no=1)
x y
INPUT: 11001011 => -53 00100011 => 35
| |
zx=0 11001011 => -53 |
| |
nx=1 00110100 => 52 |
| |
zy=0 | 00100011 => 35
| |
ny=0 | 00100011 => 35
| |
---------------------
|
|
f: + 01010111 => 87
|
no=1 10101000 => -88
|
---------------------
OUTPUT: | | |
ng 1 | |
| |
zr 0 |
|
f(x, y) 10101000 => -88
Example 3: f(x, y) = y + 1
ALU_sim(x='11001011', y='00100011', zx=1, nx=1, zy=0, ny=1, f=1, no=1)
x y
INPUT: 11001011 => -53 00100011 => 35
| |
zx=1 00000000 => 0 |
| |
nx=1 11111111 => -1 |
| |
zy=0 | 00100011 => 35
| |
ny=1 | 11011100 => -36
| |
---------------------
|
|
f: + 11011011 => -37
|
no=1 00100100 => 36
|
---------------------
OUTPUT: | | |
ng 0 | |
| |
zr 0 |
|
f(x, y) 00100100 => 36
Example 4: ` f(x, y) = -x`
ALU_sim(x='11000010', y='10011100', zx=0, nx=0, zy=1, ny=1, f=1, no=1)
x y
INPUT: 11000010 => -62 10011100 => -100
| |
zx=0 11000010 => -62 |
| |
nx=0 11000010 => -62 |
| |
zy=1 | 00000000 => 0
| |
ny=1 | 11111111 => -1
| |
---------------------
|
|
f: + 11000001 => -63
|
no=1 00111110 => 62
|
---------------------
OUTPUT: | | |
ng 0 | |
| |
zr 0 |
|
f(x, y) 00111110 => 62
Example 5: f(x, y) = x | y
ALU_sim(x='11000010', y='10011100', zx=0, nx=1, zy=0, ny=1, f=0, no=1)
x y
INPUT: 11000010 => -62 10011100 => -100
| |
zx=0 11000010 => -62 |
| |
nx=1 00111101 => 61 |
| |
zy=0 | 10011100 => -100
| |
ny=1 | 01100011 => 99
| |
---------------------
|
|
f: & 00100001 => 33
|
no=1 11011110 => -34
|
---------------------
OUTPUT: | | |
ng 1 | |
| |
zr 0 |
|
f(x, y) 11011110 => -34
There ya go! An ALU in action.
Etc.
Here’s what else went down today:
- excellent coffee chats
- compared ALUs in nand2tetris group
- made some fun leaps in Vim and CLI thanks to some tips from other recursers. Now I know about the ctrl-z / fg window toggling thing in vim. I also installed
just, the project-specific command manager, which led to installingvim-plugfor a vim plugin manager which I am now using to managevim-just, my new syntax highlighter. Alsoripgrepwhich seems useful.