58 lines
1.9 KiB
Lua
58 lines
1.9 KiB
Lua
-- Build XOR from AND, OR and NOT
|
|
function xor (a, b) return (a and not b) or (b and not a) end
|
|
|
|
-- Can make half adder now XOR exists
|
|
function halfAdder (a, b) return xor(a, b), a and b end
|
|
|
|
-- Full adder is two half adders with carry outputs OR'd
|
|
function fullAdder (a, b, cIn)
|
|
local ha0s, ha0c = halfAdder(cIn, a)
|
|
local ha1s, ha1c = halfAdder(ha0s, b)
|
|
local cOut, s = ha0c or ha1c, ha1s
|
|
return cOut, s
|
|
end
|
|
|
|
-- Carry bits 'ripple' through adders, first returned value is overflow
|
|
function fourBitAdder (a3, a2, a1, a0, b3, b2, b1, b0) -- LSB-first
|
|
local fa0c, fa0s = fullAdder(a0, b0, false)
|
|
local fa1c, fa1s = fullAdder(a1, b1, fa0c)
|
|
local fa2c, fa2s = fullAdder(a2, b2, fa1c)
|
|
local fa3c, fa3s = fullAdder(a3, b3, fa2c)
|
|
return fa3c, fa3s, fa2s, fa1s, fa0s -- Return as MSB-first
|
|
end
|
|
|
|
-- Take string of noughts and ones, convert to native boolean type
|
|
function toBool (bitString)
|
|
local boolList, bit = {}
|
|
for digit = 1, 4 do
|
|
bit = string.sub(string.format("%04d", bitString), digit, digit)
|
|
if bit == "0" then table.insert(boolList, false) end
|
|
if bit == "1" then table.insert(boolList, true) end
|
|
end
|
|
return boolList
|
|
end
|
|
|
|
-- Take list of booleans, convert to string of binary digits (variadic)
|
|
function toBits (...)
|
|
local bStr = ""
|
|
for i, bool in pairs{...} do
|
|
if bool then bStr = bStr .. "1" else bStr = bStr .. "0" end
|
|
end
|
|
return bStr
|
|
end
|
|
|
|
-- Little driver function to neaten use of the adder
|
|
function add (n1, n2)
|
|
local A, B = toBool(n1), toBool(n2)
|
|
local v, s0, s1, s2, s3 = fourBitAdder( A[1], A[2], A[3], A[4],
|
|
B[1], B[2], B[3], B[4] )
|
|
return toBits(s0, s1, s2, s3), v
|
|
end
|
|
|
|
-- Main procedure (usage examples)
|
|
print("SUM", "OVERFLOW\n")
|
|
print(add(0001, 0001)) -- 1 + 1 = 2
|
|
print(add(0101, 1010)) -- 5 + 10 = 15
|
|
print(add(0000, 1111)) -- 0 + 15 = 15
|
|
print(add(0001, 1111)) -- 1 + 15 = 16 (causes overflow)
|