14 | October | 2010 | 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.

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:

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..

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.

Congrats, glad to hear all is well.

Thanks for reading. Yes, Node Red can be a bit of a resource hog, but it can be run on…

Glad to see an update. Tasmota is a great system, and does indeed greatly simplify many things. Of course best…

I would often look at the Brainwagon link on the SolderSmoke blog and just sigh. It had been so long!…

The older layout was much easier to navigate.

brainwagon

"There is much pleasure in useless knowledge." — Bertrand Russell

Daily Archives: 10/14/2010

Design of a simple ALU…