02. Boolean Arithmetic
ALU
ALU（Algorithmic Logic Unit）算术逻辑单元，将所有的基础算术操作和逻辑操作都封装起来。
MSB（Most Significant Bits）最高有效位。
LSB（Least Significant Bits）最低有效位。
Chip API
chip
芯片名： HalfAdder
输入： a, b
输出： sum, carry
功能： sum = LSB of a + b
carry = MSB of a + bchip
芯片名： FullAdder
输入： a, b, c
输出： sum, carry
功能： sum = LSB of a + b + c
carry = MSB of a + b + cchip
芯片名： Add16
输入： a[16], b[16]
输出： out[16]
功能： out = a + b
说明： 2 补码的整数加法，不处理溢出的情况chip
芯片名： Inc16
输入： in[16]
输出： out[16]
功能： out = in + 1
说明： 2 补码的整数加法，不处理溢出的情况chip
芯片名： ALU
输入： x[16], y[16], // 两个 16 位数据输入
zx, // x 输入置零
nx, // x 输入取反
zy, // y 输入置零
ny, // y 输入取反
f, // 功能码：为 1 代表 Add，为 0 则代表 And
no // out 输出取反
输出： out[16], // 16 位输出
zr, // 当 out=0 则为 True，否则 False
ng // 当 out<0 则为 True，否则 False
功能： if zx then x = 0 // 16 位常量 0
if nx then x = !x // 按位取反
if zy then y = 0 // 16 位常量 0
if ny then y = !y // 按位取反
if f then out = x + y else out = x & y // 2 补码的整数加法，按位与运算 And
if no then out = !out // 按位取反
if out = 0 then zr = 1 else zr = 0 // 16 位 eq，比较
if out < 0 then ng = 1 else ng = 0 // 16 位 neg，比较
说明： 不处理溢出的情况Adder
https://www.codehiddenlanguage.com/Chapter14
Project 02
ALU 只要注意控制位的顺序就很简单。zx/nx/zy/ny 先把两个输入整理成想要的形态，f 决定走加法还是与运算，no 最后决定是否翻转输出。
zr 和 ng 是输出之外的状态信息。ng 直接取最高位来判断正负；zr 则要把 16 位分组 Or 起来，再整体取反来判断是否为零。
hdl
/**
* Computes the sum of two bits.
*/
CHIP HalfAdder {
IN a, b; // 1-bit inputs
OUT sum, // Right bit of a + b
carry; // Left bit of a + b
PARTS:
And(a=a, b=b, out=carry);
Xor(a=a, b=b, out=sum);
}hdl
/**
* Computes the sum of three bits.
*/
CHIP FullAdder {
IN a, b, c; // 1-bit inputs
OUT sum, // Right bit of a + b + c
carry; // Left bit of a + b + c
PARTS:
HalfAdder(a=a, b=b, sum=sum1, carry=carry1);
HalfAdder(a=sum1, b=c, sum=sum, carry=carry2);
Or(a=carry1, b=carry2, out=carry);
}hdl
/**
* 16-bit adder: Adds two 16-bit two's complement values.
* The most significant carry bit is ignored.
*/
CHIP Add16 {
IN a[16], b[16];
OUT out[16];
PARTS:
FullAdder(a=a[0], b=b[0], c=false, sum=out[0], carry=carry0);
FullAdder(a=a[1], b=b[1], c=carry0, sum=out[1], carry=carry1);
FullAdder(a=a[2], b=b[2], c=carry1, sum=out[2], carry=carry2);
FullAdder(a=a[3], b=b[3], c=carry2, sum=out[3], carry=carry3);
FullAdder(a=a[4], b=b[4], c=carry3, sum=out[4], carry=carry4);
FullAdder(a=a[5], b=b[5], c=carry4, sum=out[5], carry=carry5);
FullAdder(a=a[6], b=b[6], c=carry5, sum=out[6], carry=carry6);
FullAdder(a=a[7], b=b[7], c=carry6, sum=out[7], carry=carry7);
FullAdder(a=a[8], b=b[8], c=carry7, sum=out[8], carry=carry8);
FullAdder(a=a[9], b=b[9], c=carry8, sum=out[9], carry=carry9);
FullAdder(a=a[10], b=b[10], c=carry9, sum=out[10], carry=carry10);
FullAdder(a=a[11], b=b[11], c=carry10, sum=out[11], carry=carry11);
FullAdder(a=a[12], b=b[12], c=carry11, sum=out[12], carry=carry12);
FullAdder(a=a[13], b=b[13], c=carry12, sum=out[13], carry=carry13);
FullAdder(a=a[14], b=b[14], c=carry13, sum=out[14], carry=carry14);
FullAdder(a=a[15], b=b[15], c=carry14, sum=out[15], carry=carry15);
}hdl
/**
* 16-bit incrementer:
* out = in + 1
*/
CHIP Inc16 {
IN in[16];
OUT out[16];
PARTS:
Add16(a=in, b[0]=true, b[1..15]=false, out=out);
}hdl
/**
* ALU (Arithmetic Logic Unit):
* Computes out = one of the following functions:
* 0, 1, -1,
* x, y, !x, !y, -x, -y,
* x + 1, y + 1, x - 1, y - 1,
* x + y, x - y, y - x,
* x & y, x | y
* on the 16-bit inputs x, y,
* according to the input bits zx, nx, zy, ny, f, no.
* In addition, computes the two output bits:
* if (out == 0) zr = 1, else zr = 0
* if (out < 0) ng = 1, else ng = 0
*/
// Implementation: Manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) sets x = 0 // 16-bit constant
// if (nx == 1) sets x = !x // bitwise not
// if (zy == 1) sets y = 0 // 16-bit constant
// if (ny == 1) sets y = !y // bitwise not
// if (f == 1) sets out = x + y // integer 2's complement addition
// if (f == 0) sets out = x & y // bitwise and
// if (no == 1) sets out = !out // bitwise not
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) or (out = x & y)?
no; // negate the out output?
OUT
out[16], // 16-bit output
zr, // if (out == 0) equals 1, else 0
ng; // if (out < 0) equals 1, else 0
PARTS:
Mux16(a=x, b=false, sel=zx, out=x1);
Not16(in=x1, out=notx1);
Mux16(a=x1, b=notx1, sel=nx, out=x2);
Mux16(a=y, b=false, sel=zy, out=y1);
Not16(in=y1, out=noty1);
Mux16(a=y1, b=noty1, sel=ny, out=y2);
Add16(a=x2, b=y2, out=addxy);
And16(a=x2, b=y2, out=andxy);
Mux16(a=andxy, b=addxy, sel=f, out=fout);
Not16(in=fout, out=notfout);
Mux16(a=fout, b=notfout, sel=no, out=out, out[15]=ng, out[0..7]=low, out[8..15]=high);
Or8Way(in=low, out=orlow);
Or8Way(in=high, out=orhigh);
Or(a=orlow, b=orhigh, out=nzr);
Not(in=nzr, out=zr);
}