# Computer build from first principals

Back to overview

Complete computer build from the logic to the compiler and operating system.

• 1
Boolean Logic HDL
```/**
* 16-bit bitwise And:
* for i = 0..15: out[i] = (a[i] and b[i])
*/

CHIP And16 {
IN a[16], b[16];
OUT out[16];

PARTS:
And (a=a[0], b=b[0], out=out[0]);
And (a=a[1], b=b[1], out=out[1]);
And (a=a[2], b=b[2], out=out[2]);
And (a=a[3], b=b[3], out=out[3]);
And (a=a[4], b=b[4], out=out[4]);
And (a=a[5], b=b[5], out=out[5]);
And (a=a[6], b=b[6], out=out[6]);
And (a=a[7], b=b[7], out=out[7]);
And (a=a[8], b=b[8], out=out[8]);
And (a=a[9], b=b[9], out=out[9]);
And (a=a[10], b=b[10], out=out[10]);
And (a=a[11], b=b[11], out=out[11]);
And (a=a[12], b=b[12], out=out[12]);
And (a=a[13], b=b[13], out=out[13]);
And (a=a[14], b=b[14], out=out[14]);
And (a=a[15], b=b[15], out=out[15]);
}
/**
* And gate:
* out = 1 if (a == 1 and b == 1)
*       0 otherwise
*/

CHIP And {
IN a, b;
OUT out;

PARTS:
Nand(a=a, b=b, out=aNandb);
Nand(a=aNandb, b=aNandb, out=out);
}
/**
* 4-way demultiplexor:
* {a, b, c, d} = {in, 0, 0, 0} if sel == 00
*                {0, in, 0, 0} if sel == 01
*                {0, 0, in, 0} if sel == 10
*                {0, 0, 0, in} if sel == 11
*/

CHIP DMux4Way {
IN in, sel[2];
OUT a, b, c, d;

PARTS:
DMux(in=in, sel=sel[1], a=inZero, b=inOne);
DMux(in=inZero, sel=sel[0], a=a, b=b);
DMux(in=inOne, sel=sel[0], a=c, b=d);
}
/**
* 8-way demultiplexor:
* {a, b, c, d, e, f, g, h} = {in, 0, 0, 0, 0, 0, 0, 0} if sel == 000
*                            {0, in, 0, 0, 0, 0, 0, 0} if sel == 001
*                            etc.
*                            {0, 0, 0, 0, 0, 0, 0, in} if sel == 111
*/

CHIP DMux8Way {
IN in, sel[3];
OUT a, b, c, d, e, f, g, h;

PARTS:
DMux(in=in, sel=sel[2], a=inZero, b=inOne);
DMux4Way(in=inZero, sel=sel[0..1], a=a, b=b, c=c, d=d);
DMux4Way(in=inOne, sel=sel[0..1], a=e, b=f, c=g, d=h);
}
`/**
* Demultiplexor:
* {a, b} = {in, 0} if sel == 0
*          {0, in} if sel == 1
*/

CHIP DMux {
IN in, sel;
OUT a, b;

PARTS:
Nand(a=sel, b=sel, out=notSel);
Nand(a=notSel, b=in, out=notSelNandb);
Nand(a=notSelNandb, b=notSelNandb, out=a);
Nand(a=in, b=sel, out=inAndSel);
Nand(a=inAndSel, b=inAndSel, out=b);
}
/**
* 16-bit multiplexor:
* for i = 0..15 out[i] = a[i] if sel == 0
*                        b[i] if sel == 1
*/

CHIP Mux16 {
IN a[16], b[16], sel;
OUT out[16];

PARTS:
Mux (a=a[0], b=b[0], sel=sel, out=out[0]);
Mux (a=a[1], b=b[1], sel=sel, out=out[1]);
Mux (a=a[2], b=b[2], sel=sel, out=out[2]);
Mux (a=a[3], b=b[3], sel=sel, out=out[3]);
Mux (a=a[4], b=b[4], sel=sel, out=out[4]);
Mux (a=a[5], b=b[5], sel=sel, out=out[5]);
Mux (a=a[6], b=b[6], sel=sel, out=out[6]);
Mux (a=a[7], b=b[7], sel=sel, out=out[7]);
Mux (a=a[8], b=b[8], sel=sel, out=out[8]);
Mux (a=a[9], b=b[9], sel=sel, out=out[9]);
Mux (a=a[10], b=b[10], sel=sel, out=out[10]);
Mux (a=a[11], b=b[11], sel=sel, out=out[11]);
Mux (a=a[12], b=b[12], sel=sel, out=out[12]);
Mux (a=a[13], b=b[13], sel=sel, out=out[13]);
Mux (a=a[14], b=b[14], sel=sel, out=out[14]);
Mux (a=a[15], b=b[15], sel=sel, out=out[15]);
}
/**
* 4-way 16-bit multiplexor:
* out = a if sel == 00
*       b if sel == 01
*       c if sel == 10
*       d if sel == 11
*/

CHIP Mux4Way16 {
IN a[16], b[16], c[16], d[16], sel[2];
OUT out[16];

PARTS:
Mux16(a=a, b=b, sel=sel[0], out=aMuxbSel);
Mux16(a=c, b=d, sel=sel[0], out=cMuxdSel);
Mux16(a=aMuxbSel, b=cMuxdSel, sel=sel[1], out=out);
}/**
* 8-way 16-bit multiplexor:
* out = a if sel == 000
*       b if sel == 001
*       etc.
*       h if sel == 111
*/

CHIP Mux8Way16 {
IN a[16], b[16], c[16], d[16],
e[16], f[16], g[16], h[16],
sel[3];
OUT out[16];

PARTS:
Mux4Way16(a=a, b=b, c=c, d=d, sel=sel[0..1], out=abcd);
Mux4Way16(a=e, b=f, c=g, d=h, sel=sel[0..1], out=efgh);
Mux16(a=abcd, b=efgh, sel=sel[2], out=out);
}
/**
* Multiplexor:
* out = a if sel == 0
*       b otherwise
*/

CHIP Mux {
IN a, b, sel;
OUT out;

PARTS:
Nand(a=sel, b=sel, out=notSel);
Nand(a=a, b=notSel, out=aNotSel);
Nand(a=b, b=sel, out=aNandb);
Nand(a=aNotSel, b=aNandb, out=out);
}/**
* 16-bit Not:
* for i=0..15: out[i] = not in[i]
*/

CHIP Not16 {
IN in[16];
OUT out[16];

PARTS:
Not (in=in[0], out=out[0]);
Not (in=in[1], out=out[1]);
Not (in=in[2], out=out[2]);
Not (in=in[3], out=out[3]);
Not (in=in[4], out=out[4]);
Not (in=in[5], out=out[5]);
Not (in=in[6], out=out[6]);
Not (in=in[7], out=out[7]);
Not (in=in[8], out=out[8]);
Not (in=in[9], out=out[9]);
Not (in=in[10], out=out[10]);
Not (in=in[11], out=out[11]);
Not (in=in[12], out=out[12]);
Not (in=in[13], out=out[13]);
Not (in=in[14], out=out[14]);
Not (in=in[15], out=out[15]);
}
/**
* Not gate:
* out = not in
*/

CHIP Not {
IN in;
OUT out;

PARTS:
Nand(a=in, b=in, out=out);
}
/**
* 16-bit bitwise Or:
* for i = 0..15 out[i] = (a[i] or b[i])
*/

CHIP Or16 {
IN a[16], b[16];
OUT out[16];

PARTS:
Or (a=a[0], b=b[0], out=out[0]);
Or (a=a[1], b=b[1], out=out[1]);
Or (a=a[2], b=b[2], out=out[2]);
Or (a=a[3], b=b[3], out=out[3]);
Or (a=a[4], b=b[4], out=out[4]);
Or (a=a[5], b=b[5], out=out[5]);
Or (a=a[6], b=b[6], out=out[6]);
Or (a=a[7], b=b[7], out=out[7]);
Or (a=a[8], b=b[8], out=out[8]);
Or (a=a[9], b=b[9], out=out[9]);
Or (a=a[10], b=b[10], out=out[10]);
Or (a=a[11], b=b[11], out=out[11]);
Or (a=a[12], b=b[12], out=out[12]);
Or (a=a[13], b=b[13], out=out[13]);
Or (a=a[14], b=b[14], out=out[14]);
Or (a=a[15], b=b[15], out=out[15]);
}/**
* 8-way Or:
* out = (in[0] or in[1] or ... or in[7])
*/

CHIP Or8Way {
IN in[8];
OUT out;

PARTS:
Or (a=in[0], b=in[1], out=out1);
Or (a=in[2], b=in[3], out=out2);
Or (a=in[4], b=in[5], out=out3);
Or (a=in[6], b=in[7], out=out4);
Or (a=out1, b=out2, out=outa);
Or (a=out3, b=out4, out=outb);
Or (a=outa, b=outb, out=out);
}
/**
* Or gate:
* out = 1 if (a == 1 or b == 1)
*       0 otherwise
*/

CHIP Or {
IN a, b;
OUT out;

PARTS:
Nand(a=a, b=a, out=nota);
Nand(a=b, b=b, out=notb);
Nand(a=nota, b=notb, out=out);
}
/**
* Exclusive-or gate:
* out = not (a == b)
*/

CHIP Xor {
IN a, b;
OUT out;

PARTS:
Nand(a=a, b=b, out=aNandb);
Nand(a=a, b=aNandb, out=aNandNotb);
Nand(a=aNandb, b=b, out=notaNandb);
Nand(a=aNandNotb, b=notaNandb, out=out);
}
```
• 2
Arithmetic HDL for ALU.
```/**
* The most significant carry bit is ignored.
*/

IN a[16], b[16];
OUT out[16];

PARTS:
}
/**
* Computes the sum of three bits.
*/

IN a, b, c;  // 1-bit inputs
OUT sum,     // Right bit of a + b + c
carry;   // Left bit of a + b + c

PARTS:
Or(a=coutab, b=coutcab, out=carry);
}/**
* Computes the sum of two bits.
*/

IN a, b;    // 1-bit inputs
OUT sum,    // Right bit of a + b
carry;  // Left bit of a + b

PARTS:
Xor(a=a, b=b, out=sum);
And(a=a, b=b, out=carry);
}
/**
* 16-bit incrementer:
* out = in + 1 (arithmetic addition)
*/

CHIP Inc16 {
IN in[16];
OUT out[16];

PARTS:
}```
• 3
The ALU
```/**
* The ALU (Arithmetic Logic Unit).
* Computes one of the following functions:
* x+y, x-y, y-x, 0, 1, -1, x, y, -x, -y, !x, !y,
* x+1, y+1, x-1, y-1, x&y, x|y on two 16-bit inputs,
* according to 6 input bits denoted zx,nx,zy,ny,f,no.
* In addition, the ALU computes two 1-bit outputs:
* if the ALU output == 0, zr is set to 1; otherwise zr is set to 0;
* if the ALU output < 0, ng is set to 1; otherwise ng is set to 0.
*/

// Implementation: the ALU logic manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) set x = 0        // 16-bit constant
// if (nx == 1) set x = !x       // bitwise not
// if (zy == 1) set y = 0        // 16-bit constant
// if (ny == 1) set y = !y       // bitwise not
// if (f == 1)  set out = x + y  // integer 2's complement addition
// if (f == 0)  set out = x & y  // bitwise and
// if (no == 1) set out = !out   // bitwise not
// if (out == 0) set zr = 1
// if (out < 0) set ng = 1

CHIP ALU {
IN
x[16], y[16],  // 16-bit inputs
zx, // zero the x input?
nx, // negate the x input?
zy, // zero the y input?
ny, // negate the y input?
f,  // compute out = x + y (if 1) or x & y (if 0)
no; // negate the out output?

OUT
out[16], // 16-bit output
zr, // 1 if (out == 0), 0 otherwise
ng; // 1 if (out < 0),  0 otherwise

PARTS:
// zx
And16(a=x, b=false, out=zxTrue);
Mux16(a=x, b=zxTrue, sel=zx, out=zerox);

// nx
Not16(in=zerox, out=notx);
Mux16(a=zerox, b=notx, sel=nx, out=negx);

// zy
And16(a=y, b=false, out=zyTrue);
Mux16(a=y, b=zyTrue, sel=zy, out=zeroy);

// ny
Not16(in=zeroy, out=noty);
Mux16(a=zeroy, b=noty, sel=ny, out=negy);

// f
And16(a=negx, b=negy, out=andfxy);