#!/home/kragen/devel/luajit-2.0/src/luajit

-- Combinational logic simulator in Lua. Needs Mike Pall’s “bit”
-- library for bit operations, which is built into LuaJIT, but also
-- available for normal Lua.

-- I thought I would write a hardware definition language inspired by
-- the TECS “NAND-to-Tetris” course. Then it occurred to me that I
-- could probably use LuaJIT to JIT-compile my circuit descriptions to
-- machine code, and then they would probably run fast.

-- So far, I haven’t implemented sequential logic, so it’s impossible
-- to tell if the JIT would make the circuit run fast or not; it
-- doesn’t do enough work to detect. This whole program takes about
-- 5ms.

-- Next steps:

-- * Implement sequential logic. This adds a new dimension to circuit
--   inputs: they become waveforms over time rather than
--   bitvectors. This should slow stuff down a bit.

-- * Implement bitvectors again, but for real:
--     * N-wide NAND gates (like what we have now)
--     * check circuit input width at circuit input time (not every gate!)
--     * bit-range and concatenate operations on bitvectors
--     * arbitrary width implemented by doing the operations N-wide
--       at a time (53?)
--     * bitvector waveforms on input and output are tables
--       {"001", "010", ...} represented as strings rather than numbers 
--       for the sake of arbitrary width.

-- * Write a test-bench facility to enable easy testing of circuits.

-- * Some circuit analyses: gate count, path length.

-- * Further circuit analyses: redundant gate elimination (i.e. common
--   subexpression elimination) and computation of disjunctive normal
--   form to allow verification against Boolean equations

-- * Synthesis from Boolean equations

-- * Schematic generation (e.g. with graphviz dot?)

-- After the first three of these steps, this should be sufficient for
-- me to use for Calculus Vaporis design.



-- Generic Lua utility functions for set arithmetic etc. --
-----------------------------------------------------------

-- Given a table { a = b, c = d, ... } return { b = a, d = c, ... }
function invert(tbl)
   local inverted = {}
   for index, item in pairs(tbl) do inverted[item] = index end
   return inverted
end

-- Map a function over name-value pairs.
-- Given a table { a = b, c = d, ... } and a function f,
-- returns { f(a, b), f(c, d), ...}.
function tmap(tbl, func)
   local rv = {}
   for a, b in pairs(tbl) do table.insert(rv, func(a, b)) end
   return rv
end

-- Analogously, map a function over the values in a sequence.
function map(seq, func)
   local rv = {}
   for _, b in ipairs(seq) do table.insert(rv, func(b)) end
   return rv
end

-- Given a table { a = b, c = d, ... } return { a, c, ... }
function keys(tbl) return tmap(tbl, function(k, v) return k end) end

-- Given a table, return a string showing its keys and values.
function shallow_table_dump(tbl)
   function perline(n, v)
      return "    "..tostring(n).." = "..tostring(v)..",\n"
   end
   return "{\n"..table.concat(tmap(tbl, perline)).."}"
end

-- The next couple of functions deal with tables treated as sets: the
-- keys are the members of the set, and the values are merely any true
-- value.

-- return a set containing only the elements that are in both sets
function set_intersect(seta, setb)
   local rv = {}
   for member, _ in pairs(seta) do
      if setb[member] then rv[member] = true end
   end
   return rv
end

-- return true if a set is empty
function set_empty(set) return #keys(set) == 0 end



-- Basic types of wires: NAND gate outputs and circuit inputs. --
-----------------------------------------------------------------

-- In the netlist and the Lua code we use strings to represent wires
-- (instead of using wire objects). These functions produce those
-- strings.
function input(index) return "input" .. index end
function is_input(varname) return string.find(varname, "input") == 1 end
function gate(index) return "gate" .. index end


-- The following code produces the objects that get converted to those strings.

-- These objects have a couple of roles:

-- * As a signal source ("a wire"):
--     * produce the string that identifies that signal source in the netlist
--     * describe itself for debugging

-- * As a node in the network (NAND gates only):
--     * support traversal of the graph to find all the nodes for the netlist
--     * list its dependencies to support topological sorting

-- Construct a NAND gate node used to represent circuits.
function nand_gate(left_input, right_input)
   -- This error occurs if you misspell an input wire or don’t connect it.
   if left_input  == nil then error("left input nil") end
   if right_input == nil then error("right input nil") end

   local rv = { left_input = left_input,
                right_input = right_input,
                earlier_gates = {},
                is_a_gate = true }

   if left_input.is_a_gate  then rv.earlier_gates[left_input]  = true end
   if right_input.is_a_gate then rv.earlier_gates[right_input] = true end

   function rv:place(mapping) return gate(mapping[self]) end
   function rv:describe() 
      return (tostring(self).." is nand("..tostring(self.left_input)..
                                     ", "..tostring(self.right_input)..")")
   end

   return rv
end


-- circuit_inputs.foo returns the input to the whole circuit named "foo".

circuit_input_metatable = {
   __index = function(table, key) 
                return { 
                   name = key,
                   place = function(self, mapping) return input(self.name) end,
                   describe = function(self) return "input "..self.name end
                }
             end,
}

circuit_inputs = {}
setmetatable(circuit_inputs, circuit_input_metatable)


-- An “outputs” object holds two or more output wires.

function outputs(tbl)
   tbl._wires = tmap(tbl, function(_, wire) return wire end)
   return tbl
end



-- Actual hierarchical circuit designs look like this: --
---------------------------------------------------------

function not_gate(x)   return nand_gate(x, x) end
function or_gate(a, b) return nand_gate(not_gate(a), not_gate(b)) end
function and_gate(a, b) return not_gate(nand_gate(a, b)) end

function xor_gate(a, b)
   local not_a, not_b = not_gate(a), not_gate(b)
   local a_or_not_b = nand_gate(not_a, b)
   local b_or_not_a = nand_gate(not_b, a)
   return nand_gate(a_or_not_b, b_or_not_a)
end

function half_adder(a, b) 
   return outputs { sum = xor_gate(a, b), carry = and_gate(a, b) }
end

function full_adder(inputs)
   local ha1 = half_adder(inputs.a, inputs.b)
   local ha2 = half_adder(ha1.sum, inputs.carry)
   return outputs { sum = ha2.sum, carry = or_gate(ha1.carry, ha2.carry) }
end

-- A two-way multiplexor that takes two input select signals that are
-- complements of each other. Less convenient to use than mux2, but
-- can save gates:
function hairy_mux2(inputs)
   -- Now we make ignored (and inverted) versions of the two inputs.
   -- gated_a is not a, except when b is selected, when it’s 1.
   local gated_a = nand_gate(inputs.a, inputs.select_a)
   local gated_b = nand_gate(inputs.b, inputs.select_b)
   -- Now we have one signal that’s 1 and the other signal that’s the
   -- negated input we want. So we NAND them.
   return nand_gate(gated_a, gated_b)
end

-- A two-way multiplexor.
function mux2(inputs)
   return hairy_mux2 {
      a = inputs.a,
      b = inputs.b,
      select_a = inputs.select_a,
      select_b = not_gate(inputs.select_a),
   }
end

-- A four-way multiplexor.
-- I looked up TTL datasheets to see what mux inputs were normally
-- called, but the 74151 calls its address lines A, B, and C, and the
-- input lines D0 through D8. I think these names are better.
function mux4(inputs)
   local not_addr_lo = not_gate(inputs.addr_lo)
   local mux_ab = hairy_mux2 {
      select_a = inputs.addr_lo,
      select_b = not_addr_lo,
      a = inputs.d_11,
      b = inputs.d_10,
   }

   local mux_cd = hairy_mux2 {
      select_a = inputs.addr_lo,
      select_b = not_addr_lo, 
      a = inputs.d_01, 
      b = inputs.d_00,
   }

   return mux2 { select_a = inputs.addr_hi, a = mux_ab, b = mux_cd }
end

-- (Also I would like some XXX D flip-flops and some way to deal with
-- known-size bitvectors, so you can design a ripple-carry multi-bit
-- adder.)



-- Code to linearize the circuit graph into a netlist. --
---------------------------------------------------------

-- Find all the gates that are needed to produce the outputs in the
-- sequence orig_wires.
function walk_circuit(orig_wires)
   local wires = {}
   for _, wire in pairs(orig_wires) do table.insert(wires, wire) end

   local gates = {}
   while #wires > 0 do
      local wire = table.remove(wires)

      if wire.is_a_gate then
         if not gates[wire] then
            gates[wire] = true
            table.insert(wires, wire.left_input)
            table.insert(wires, wire.right_input)
         end
      end
   end

   return keys(gates)
end

-- Returns a string for debugging the topologically_sort function.
function dumpgates(remaining_gates)
   function dumpgate(gate)
      local earlier_gates_str = map(keys(gate.earlier_gates), tostring)
      return tostring(gate)..' → '.. table.concat(earlier_gates_str, ', ')
   end
   return table.concat(map(keys(remaining_gates), dumpgate), ';\n')
end

-- Returns a topological sort of the gates in a combinational circuit.
-- There is a linear-time topological sort. This isn’t it, but that’s
-- probably okay.
function topologically_sort(gates)
   local remaining_gates, remaining_gates_count = invert(gates), #gates
   local sorted_order = {}

   while remaining_gates_count > 0 do
      local found_a_gate = false

      for gate, _ in pairs(remaining_gates) do
         if set_empty(set_intersect(gate.earlier_gates, remaining_gates)) then
            table.insert(sorted_order, gate)

            remaining_gates[gate] = nil
            remaining_gates_count = remaining_gates_count - 1

            found_a_gate = true
            break
         end
      end

      if not found_a_gate then
         error("circular dependency"..dumpgates(remaining_gates)) 
      end

   end

   return sorted_order
end

-- Given a circuit (a function from an input table to a wire or an
-- outputs) construct a topologically-sorted netlist representing that
-- circuit, and a table of the names of the outputs in the netlist.
function circuit_to_netlist(circuit)
   local output_spec = circuit(circuit_inputs)
   local output_wires
   if output_spec._wires then
      output_wires = output_spec._wires

   else -- one wire!
      output_wires = {output_spec}
      output_spec = {output = output_spec}
   end

   local gates = topologically_sort(walk_circuit(output_wires))

   local mapping = invert(gates)

   local netlist = map(gates, function(gate)
                                 return { gate.left_input:place (mapping),
                                          gate.right_input:place(mapping) }
                              end)

   local outputs = {}
   for name, wire in pairs(output_spec) do
      if name ~= "_wires" then  -- XXX, change the structure to avoid this?
         outputs[name] = wire:place(mapping)
      end
   end

   return netlist, outputs
end



-- Compiler from netlist into Lua code --
-----------------------------------------

function netlist2lua(circuit, outputs)
   local variable_index = 1
   local inputs = {}

   local statements = map(circuit, function(gatespec)
      local varname = gate(variable_index)
      variable_index = variable_index + 1

      local left, right = unpack(gatespec)
      if is_input(left)  then inputs[left]  = 1 end
      if is_input(right) then inputs[right] = 1 end

      return "local "..varname.." = bit.bnot(bit.band("..left..", "..right.."))"
   end)

   local return_variables = tmap(outputs, function(name, place)
                                             return name..' = '..place
                                          end)

   table.insert(statements, "return {"..table.concat(return_variables, ', ')..
                                   "}")

   tmap(inputs, function(input) 
      local name = string.sub(input, 6) -- XXX disgusting
      local from_expr = 'circuit_inputs.'..name
      table.insert(statements, 1, 'local '..input..' = '..from_expr)
      return 1
   end)
   table.insert(statements, 1, 'circuit_inputs = ...')

   return table.concat(statements, "\n")
end



-- UI convenience functions --
------------------------------

function binary(x) return tonumber(x, 2) end

function tobinary(n)
   local digits = {}
   local sign = ""

   if n < 0 then
      sign = "~"
      n = -n - 1
   end

   repeat
      table.insert(digits, tostring(bit.band(1, n)))
      n = math.floor(n/2)
   until n == 0

   return sign .. string.reverse(table.concat(digits))
end

function binary_dump(output_table)
   function outputline(n, v) return "    "..n.." = "..tobinary(v)..";\n" end
   return "{\n"..table.concat(tmap(output_table, outputline)).."}\n"
end



-- Demo script, when invoked from the command line --
-----------------------------------------------------

if #{...} then 
   local compiled = netlist2lua(circuit_to_netlist(mux4))
   print(compiled)
   circuit = loadstring(compiled)
   print(binary_dump(circuit { addr_hi = binary "111110000001111110000000",
                               addr_lo = binary "000000000001111111111111",
                               d_11    = binary "101000000000011100000000",
                               d_01    = binary "000110001010101010101010",
                               d_10    = binary "110111111111111101111111",
                               d_00    = binary "100000111100000000000000" }))
end

-- Local Variables:
-- compile-command: "./hdl.lua"
-- End: