logigate/app/lib/logic/wide.ts

157 lines
6.1 KiB
TypeScript
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

// 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 }
}