Wednesday, February 13, 2013

I finally got to read the second part of Robey Pointer "How to add numbers" blog posts. Thinking about hardware "algorithms" can be interesting because distributed systems face similar problems sometimes. Below is my implementation of Kogge-Stone addition for 32 bits integers. Brent-Kung hybrid is very clever, but I couldn't figure out an obvious "step" for Brent-Kung that could be recursed into.
```def add(x: Int, y: Int, cin: Boolean) = {
def intToBooleanArray(n: Int): Array[Boolean] = {
(0 until 32 map ((1).<<) map (n.&) map (0.!=)).toArray
}

val xs: Array[Boolean] = intToBooleanArray(x)
val ys: Array[Boolean] = intToBooleanArray(y)

// P means cout depends on cin
// G means cout is 1 regardless of cin
case class PG(p: Boolean, g: Boolean)
def p(a: Boolean, b: Boolean) = a ^ b
def g(a: Boolean, b: Boolean) = a & b

// initial PG from input alone
val pg0 = (xs, ys).zipped map ((a, b) => PG(g = g(a, b), p = p(a, b)))

// Execute combine step until all PGs are final
def combStep(lastPGs: Array[PG], finalPGs: Array[PG], step: Int): Array[PG] = {
// Combines PGs formed by adjacent block of bits
def comb(pga: PG, pgb: PG): PG = PG(p = pgb.p & pga.p,
g = pgb.g | (pgb.p & pga.g))

if (lastPGs.isEmpty) finalPGs
else {
val (newFinalPGs, tempPGs) = lastPGs splitAt (step - step / 2)
val nextPGs = (finalPGs ++ lastPGs, tempPGs).zipped map comb

combStep(nextPGs, finalPGs ++ newFinalPGs, step << 1)
}
}

val pgs = combStep(pg0, finalPGs = Array.empty, step = 1)

// Carry for each bit
def cout(cin: Boolean)(pg: PG): Boolean = pg.g | (pg.p & cin)
val cn = pgs map cout(cin)

// Final result for each bit
val sn = (pg0 map (_.p), cin +: (cn take 31)).zipped map ((p, c) => p ^ c)

// Convert boolean array back into an int
val result = (sn.zipWithIndex map {
case (s, i) => if (s) 1 << i else 0
}).sum
(result, cn.last)
}
```