brainwagon

A couple of weeks ago, I noticed a bunch of links to a 16 bit ALU designed to operate using blocks which are defined in the game Minecraft. It got me thinking, and ordered the book that inspired that work. It contains the specification for an ALU which is very simple, and yet surprisingly powerful ALU (at least, considering the number of gates that it would take to implement it).

Here’s a C function that implements the ALU. I went ahead and just used the integer type, rather than the 16 bits specified in the Hack computer, but it doesn’t really matter what the word size is.

[sourcecode lang=”C”]
#define ZERO_X (1<<0)
#define COMP_X (1<<1)
#define ZERO_Y (1<<2)
#define COMP_Y (1<<3)
#define OP_ADD (1<<4)
#define COMP_O (1<<5)

unsigned int
alu(unsigned int x, unsigned int y, int flags)
{
unsigned int o ;

if (flags & ZERO_X) x = 0 ;
if (flags & ZERO_Y) y = 0 ;
if (flags & COMP_X) x = ~x ;
if (flags & COMP_Y) y = ~y ;
if (flags & OP_ADD)
o = x + y ;
else
o = x & y ;
if (flags & COMP_O) o = ~o ;
return o ;
}
[/sourcecode]

The function takes in two operands (x and y) and a series of six bit flags. The ZERO_X and ZERO_Y say that the X input and Z input should be set to zero. The COMP_X, COMP_Y, and COMP_O flags say that the X, Y, and output values should be bitwise negated (all the zeros become ones, and the ones zeros). The OP_ADD flag chooses one of two functions: when set, it means that the two operands should be added, otherwise, the two operands are combined with bitwise AND.

There are a surprisingly large number of interesting functions that can be calculated from this simple ALU. Well, perhaps not surprising to the hardware engineers out there, but I’ve never really thought about it. It’s obvious that you can compute functions like AND and ADD. Let’s write some defines:

[sourcecode lang=”C”]
#define AND(x,y) alu(x, y, 0)
#define ADD(x,y) alu(x, y, OP_ADD)
[/sourcecode]

You can also compute functions like OR using DeMorgan’s Law: OR(x,y) = ~(~X AND ~Y).

[sourcecode lang=”C”]
#define OR(x,y) alu(x, y, COMP_X|COMP_Y|COMP_O)
[/sourcecode]

You can make some constants such as zero and one. Zero is particularly easy, but one requires an interesting trick using twos-complement arithmetic.

[sourcecode lang=”C”]
#define ZERO(x,y) alu(x, y, ZERO_X|ZERO_Y|OP_ADD)
#define ONE(x,y) alu(x, y, ZERO_X|COMP_X|ZERO_Y|COMP_Y|OP_ADD|COMP_O)
[/sourcecode]

To make sense of the definition of ONE, you need to know that in twos-complement arithmetic, -x = ~x + 1, or in other words, -x – 1 = ~x. Look at the definition of ONE, it computes ~(~0 + ~0). After the addition, the register contains all 1s, except for the low order bit. Negating that builds a one. You can also build a -1, or even a -2.

You can also obviously get either operand, or their logical complements. There are even multiple implementations:

[sourcecode lang=”C”]
#define NOTX(x,y) alu(x, y, COMP_X|ZERO_Y|COMP_Y)
#define NOTX(x,y) alu(x, y, COMP_X|ZERO_Y|OP_ADD)
#define NOTX(x,y) alu(x, y, ZERO_Y|COMP_Y|COMP_O)
#define NOTX(x,y) alu(x, y, ZERO_Y|OP_ADD|COMP_O)
[/sourcecode]

We saw how we could add, we could also construct a subtractor:

[sourcecode lang=”C”]
#define SUB(x,y) alu(x, y, COMP_X|OP_ADD|COMP_O)
[/sourcecode]

We saw how we could compute +1 and -1, but we can also add these constants to X or Y..

[sourcecode lang=”C”]
#define DECY(x,y) alu(x, y, ZERO_X|COMP_X|OP_ADD)
#define DECX(x,y) alu(x, y, ZERO_Y|COMP_Y|OP_ADD)
#define INCY(x,y) alu(x, y, ZERO_X|COMP_X|COMP_Y|OP_ADD|COMP_O)
#define INCX(x,y) alu(x, y, COMP_X|ZERO_Y|COMP_Y|OP_ADD|COMP_O)
[/sourcecode]

I thought it was pretty neat or such a small implementation. The hardest part to implement is the adder, all the rest is a pretty trivial number of gates. If you use a simple ripple adder, even the adder is pretty small.

Addendum: Here’s a more (but not entirely) exhaustive list of functions that are implemented.

[sourcecode lang=”C”]
#define ADD(x,y) alu(x, y, OP_ADD)
#define AND(x,y) alu(x, y, 0)
#define DECX(x,y) alu(x, y, ZERO_Y|COMP_Y|OP_ADD)
#define DECY(x,y) alu(x, y, ZERO_X|COMP_X|OP_ADD)
#define INCX(x,y) alu(x, y, COMP_X|ZERO_Y|COMP_Y|OP_ADD|COMP_O)
#define INCY(x,y) alu(x, y, ZERO_X|COMP_X|COMP_Y|OP_ADD|COMP_O)
#define MINUS1(x,y) alu(x, y, COMP_X|ZERO_Y|COMP_O)
#define MINUS1(x,y) alu(x, y, ZERO_X|COMP_O)
#define MINUS1(x,y) alu(x, y, ZERO_X|COMP_X|ZERO_Y|COMP_O)
#define MINUS1(x,y) alu(x, y, ZERO_X|COMP_X|ZERO_Y|COMP_Y)
#define MINUS1(x,y) alu(x, y, ZERO_X|COMP_X|ZERO_Y|OP_ADD)
#define MINUS1(x,y) alu(x, y, ZERO_X|COMP_Y|COMP_O)
#define MINUS1(x,y) alu(x, y, ZERO_X|ZERO_Y|COMP_O)
#define MINUS1(x,y) alu(x, y, ZERO_X|ZERO_Y|COMP_Y|COMP_O)
#define MINUS1(x,y) alu(x, y, ZERO_X|ZERO_Y|COMP_Y|OP_ADD)
#define MINUS1(x,y) alu(x, y, ZERO_X|ZERO_Y|OP_ADD|COMP_O)
#define MINUS1(x,y) alu(x, y, ZERO_Y|COMP_O)
#define MINUS2(x,y) alu(x, y, ZERO_X|COMP_X|ZERO_Y|COMP_Y|OP_ADD)
#define NAND(x,y) alu(x, y, COMP_O)
#define NOR(x,y) alu(x, y, COMP_X|COMP_Y)
#define NOTX(x,y) alu(x, y, COMP_X|ZERO_Y|COMP_Y)
#define NOTX(x,y) alu(x, y, COMP_X|ZERO_Y|OP_ADD)
#define NOTX(x,y) alu(x, y, ZERO_Y|COMP_Y|COMP_O)
#define NOTX(x,y) alu(x, y, ZERO_Y|OP_ADD|COMP_O)
#define NOTY(x,y) alu(x, y, ZERO_X|COMP_X|COMP_O)
#define NOTY(x,y) alu(x, y, ZERO_X|COMP_X|COMP_Y)
#define NOTY(x,y) alu(x, y, ZERO_X|COMP_Y|OP_ADD)
#define NOTY(x,y) alu(x, y, ZERO_X|OP_ADD|COMP_O)
#define ONE(x,y) alu(x, y, ZERO_X|COMP_X|ZERO_Y|COMP_Y|OP_ADD|COMP_O)
#define OR(x,y) alu(x, y, COMP_X|COMP_Y|COMP_O)
#define RSUB(x,y) alu(x, y, COMP_Y|OP_ADD|COMP_O)
#define SUB(x,y) alu(x, y, COMP_X|OP_ADD|COMP_O)
#define X(x,y) alu(x, y, COMP_X|ZERO_Y|COMP_Y|COMP_O)
#define X(x,y) alu(x, y, COMP_X|ZERO_Y|OP_ADD|COMP_O)
#define X(x,y) alu(x, y, ZERO_Y|COMP_Y)
#define X(x,y) alu(x, y, ZERO_Y|OP_ADD)
#define XANDNOTY(x,y) alu(x, y, COMP_Y)
#define XORNOTY(x,y) alu(x, y, COMP_X|COMP_O)
#define Y(x,y) alu(x, y, ZERO_X|COMP_X)
#define Y(x,y) alu(x, y, ZERO_X|COMP_X|COMP_Y|COMP_O)
#define Y(x,y) alu(x, y, ZERO_X|COMP_Y|OP_ADD|COMP_O)
#define Y(x,y) alu(x, y, ZERO_X|OP_ADD)
#define YANDNOTX(x,y) alu(x, y, COMP_X)
#define YORNOTX(x,y) alu(x, y, COMP_Y|COMP_O)
#define ZERO(x,y) alu(x, y, COMP_X|ZERO_Y)
#define ZERO(x,y) alu(x, y, ZERO_X)
#define ZERO(x,y) alu(x, y, ZERO_X|COMP_X|ZERO_Y)
#define ZERO(x,y) alu(x, y, ZERO_X|COMP_X|ZERO_Y|COMP_Y|COMP_O)
#define ZERO(x,y) alu(x, y, ZERO_X|COMP_X|ZERO_Y|OP_ADD|COMP_O)
#define ZERO(x,y) alu(x, y, ZERO_X|COMP_Y)
#define ZERO(x,y) alu(x, y, ZERO_X|ZERO_Y)
#define ZERO(x,y) alu(x, y, ZERO_X|ZERO_Y|COMP_Y)
#define ZERO(x,y) alu(x, y, ZERO_X|ZERO_Y|COMP_Y|OP_ADD|COMP_O)
#define ZERO(x,y) alu(x, y, ZERO_X|ZERO_Y|OP_ADD)
#define ZERO(x,y) alu(x, y, ZERO_Y)
[/sourcecode]