6 minute read

Daily dispatches from my 12 weeks at the Recurse Center in Summer 2023

Here’s an ALU.

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 the x input, otherwise leave x as is
  • nx: if this is 1, negate the x input, otherwise leave as is
  • zy: if this is 1, zero the y input, otherwise leave y as is
  • ny: if this is 1, negate the y input, otherwise leave y as is
  • f: function selector – if 1, then return x + y, otherwise return x & y
  • no: 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 no
  • zr: 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:

ALU schematic

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 (x or y) as one of their inputs and 0 as their other, so that if zx/zy is toggled off, the x/y input is selected, otherwise the 0s 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/ny bit.
  • The results of the x->zx->nx and y->zy->ny operations are both added together and ANDed together, and these two results are fed into yet another Mux 16, which is toggled by the f selector bit. If f is 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 no bit 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 OR all 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. Because zr is 1 if all the bits are 0, we have to negate the result.
  • As for the ng flag, 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 and ng too should be set to 1. Otherwise, the output is positive and ng will 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 installing vim-plug for a vim plugin manager which I am now using to manage vim-just, my new syntax highlighter. Also ripgrep which seems useful.