logigate/app/lib/logic/wide.ts

157 lines
6.1 KiB
TypeScript
Raw Permalink Normal View History

// Gates with more inputs. A two-input gate that can be chained (AND, OR,
// XOR) or is the inverse of one (NAND, NOR) gets a wide version with up to
// 16 inputs, built as a balanced tree of the two-input gate itself. So the
// transistor count stays honest, and a change to your AND reaches every
// wide AND built from it. Wide versions are ordinary components, made once
// per gate and width and reused.
import { compile } from './compile'
import { chipPins, type DefLookup } from './geometry'
import { lookup, uid, uniqueName } from './ops'
import { Simulator } from './sim'
import type { CircuitNode, ComponentDef, Project, SymbolKind, Wire } from './types'
export const MAX_GATE_INPUTS = 16
/** The NAND primitive as a base, where a component id would go. */
export const NAND_BASE = 'nand'
/**
* How a two-input, one-output gate widens: "chain" when f(f(a,b),c) is
* f(a,f(b,c)) and f(0,0) = 0 (AND, OR, XOR); "inverted" when it is the
* NOT of such a gate and f(x,x) = NOT x (NAND, NOR); otherwise null.
*/
export type Family = 'chain' | 'inverted'
function table(get: DefLookup, base: string): number[] | null {
if (base === NAND_BASE) return [1, 1, 1, 0]
const def = get(base)
if (!def) return null
const pins = chipPins(def)
if (pins.inputs.length !== 2 || pins.outputs.length !== 1) return null
const nl = compile(get, base)
if (nl.errors.length || nl.clocks.length) return null
const sim = new Simulator(nl)
const out: number[] = []
for (let i = 0; i < 4; i++) {
sim.setSource(pins.inputs[0]!.key, (i & 2) !== 0)
sim.setSource(pins.inputs[1]!.key, (i & 1) !== 0)
if (!sim.run(200_000)) return null
out.push(sim.output(pins.outputs[0]!.key))
}
return out
}
const chains = (t: number[]) => {
const f = (a: number, b: number) => t[a * 2 + b]!
if (t[1] !== t[2] || t[0] !== 0) return false
for (let i = 0; i < 8; i++) {
const [a, b, c] = [(i >> 2) & 1, (i >> 1) & 1, i & 1]
if (f(f(a, b), c) !== f(a, f(b, c))) return false
}
return true
}
export function gateFamily(get: DefLookup, base: string): Family | null {
const t = table(get, base)
if (!t) return null
if (chains(t)) return 'chain'
if (t[0] === 1 && t[3] === 0 && chains(t.map(v => v ^ 1))) return 'inverted'
return null
}
/** The two-input gate behind a placed part: itself, or the gate its wide version is built from. */
export function baseOf(node: CircuitNode, get: DefLookup): string | null {
if (node.kind === 'nand') return NAND_BASE
if (node.kind !== 'chip' || !node.chip) return null
return get(node.chip)?.wide?.base ?? node.chip
}
/** Number of inputs of a placed gate. */
export function inputCount(node: CircuitNode, get: DefLookup): number {
if (node.kind === 'nand') return 2
const def = node.chip ? get(node.chip) : undefined
return def ? chipPins(def).inputs.length : 0
}
const LETTERS = 'ABCDEFGHIJKLMNOP'
/** Builds the wide version of a gate with `n` inputs. */
function buildWide(project: Project, base: string, n: number, family: Family): ComponentDef {
const get = lookup(project)
const baseDef = base === NAND_BASE ? undefined : get(base)
const pins = baseDef ? chipPins(baseDef) : { inputs: [{ key: 'a' }, { key: 'b' }], outputs: [{ key: 'q' }] }
const [inA, inB] = [pins.inputs[0]!.key, pins.inputs[1]!.key]
const out = pins.outputs[0]!.key
const nodes: CircuitNode[] = []
const wires: Wire[] = []
interface Sig {
node: string
pin: string
col: number
y: number
}
const gate = (a: Sig, b: Sig): Sig => {
const col = Math.max(a.col, b.col) + 1
const y = Math.round((a.y + b.y) / 2)
const id = uid('n')
nodes.push(base === NAND_BASE ? { id, kind: 'nand', x: col * 8, y } : { id, kind: 'chip', chip: base, x: col * 8, y })
wires.push({ id: uid('w'), from: { node: a.node, pin: a.pin }, to: { node: id, pin: inA } })
wires.push({ id: uid('w'), from: { node: b.node, pin: b.pin }, to: { node: id, pin: inB } })
return { node: id, pin: out, col, y }
}
// "Inverted" gates (NAND, NOR) make the plain one first: the gate, then the gate as a NOT.
const plain = (a: Sig, b: Sig): Sig => {
const g = gate(a, b)
return family === 'chain' ? g : gate(g, g)
}
const tree = (list: Sig[]): Sig => {
if (list.length === 1) return list[0]!
const mid = Math.ceil(list.length / 2)
return plain(tree(list.slice(0, mid)), tree(list.slice(mid)))
}
const ins: Sig[] = []
for (let i = 0; i < n; i++) {
const id = uid('n')
nodes.push({ id, kind: 'input', x: 0, y: i * 3, label: LETTERS[i]! })
ins.push({ node: id, pin: 'q', col: 0, y: i * 3 })
}
const mid = Math.ceil(n / 2)
const left = tree(ins.slice(0, mid))
const right = tree(ins.slice(mid))
// The root is the gate itself, so NAND and NOR stay inverted.
const root = gate(left, right)
const qid = uid('n')
nodes.push({ id: qid, kind: 'output', x: (root.col + 1) * 8, y: root.y, label: 'Q' })
wires.push({ id: uid('w'), from: { node: root.node, pin: root.pin }, to: { node: qid, pin: 'a' } })
const name = baseDef?.name ?? 'NAND'
const symbol: SymbolKind = baseDef?.symbol ?? 'nand'
return {
id: uid('c'),
name: uniqueName(project, `${name} ×${n}`),
symbol,
group: 'Wide gates',
description: `${name} with ${n} inputs, built from ${name} gates with two inputs.`,
wide: { base, n },
nodes,
wires,
}
}
/**
* The component to place for a gate with `n` inputs: the base itself for 2,
* otherwise its wide version, made now if the project has none yet.
* Returns null when the gate can't be widened.
*/
export function wideGate(project: Project, base: string, n: number): { kind: 'nand' } | { kind: 'chip'; chip: string } | null {
const get = lookup(project)
const family = gateFamily(get, base)
if (!family || n < 2 || n > MAX_GATE_INPUTS) return null
if (n === 2) return base === NAND_BASE ? { kind: 'nand' } : { kind: 'chip', chip: base }
const existing = project.components.find(d => d.wide?.base === base && d.wide.n === n)
if (existing) return { kind: 'chip', chip: existing.id }
const def = buildWide(project, base, n, family)
project.components.push(def)
return { kind: 'chip', chip: def.id }
}