2026-10-20 18:09:23 +00:00
|
|
|
|
// 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
|
2026-10-23 10:24:35 +00:00
|
|
|
|
out.push(sim.output(pins.outputs[0]!.key))
|
2026-10-20 18:09:23 +00:00
|
|
|
|
}
|
|
|
|
|
|
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 }
|
|
|
|
|
|
}
|