From ccbd93f9c10998298b552fe71445449f8af91844 Mon Sep 17 00:00:00 2001 From: Nick Downing Date: Mon, 21 Jul 2025 00:23:29 +1000 Subject: [PATCH] Add subcircuit analysis, it can identify an XOR gate made from AND+NOR gates --- .gitignore | 1 + 8085/Makefile | 6 +- scripts/blocks.py | 29 ++++- scripts/blocks.sh | 2 +- scripts/circuits.py | 295 ++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 330 insertions(+), 3 deletions(-) create mode 100755 scripts/circuits.py diff --git a/.gitignore b/.gitignore index 7c911b7..bdac7ff 100644 --- a/.gitignore +++ b/.gitignore @@ -11,6 +11,7 @@ /8080/nets.txt /8080/sizes.txt /8085/buried.png +/8085/circuits.txt /8085/diff.png /8085/dot /8085/fets.txt diff --git a/8085/Makefile b/8085/Makefile index 6da6902..7f815f5 100644 --- a/8085/Makefile +++ b/8085/Makefile @@ -10,7 +10,7 @@ COLOURS=0,5,5,1,2,4,6,3,7 all: \ -gates.txt \ +circuits.txt \ node_sizes.txt \ node_gnd.png \ node_vcc.png \ @@ -25,6 +25,9 @@ layers_rev.png #poly2.png \ #vias2.png +circuits.txt: gates.txt + ../scripts/circuits.py gates.txt GND,VCC >$@ + gates.txt: fets.txt ../scripts/gates.py fets.txt GND,VCC >$@ @@ -150,6 +153,7 @@ pads.png \ poly.png \ split_diff.png \ vias.png \ +circuits.txt \ fets.txt \ gates.txt \ node_sizes.txt \ diff --git a/scripts/blocks.py b/scripts/blocks.py index 49ee272..5fd139e 100755 --- a/scripts/blocks.py +++ b/scripts/blocks.py @@ -5,7 +5,8 @@ import sys SYMBOL_TYPE_FET = 0 SYMBOL_TYPE_GATE = 1 -N_SYMBOL_TYPES = 2 +SYMBOL_TYPE_XOR = 2 +N_SYMBOL_TYPES = 3 if len(sys.argv) < 3: print(f'usage: {sys.argv[0]:s} symbols.txt dot_dir') @@ -74,6 +75,9 @@ with open(symbols_txt) as fin: assert len(line) expr.append(line.split()) + if output_net not in nets: + nets[output_net] = set() # blocks (of symbols) that the net visits + nets[output_net].add(block) for product in expr: for net in product: if net not in nets: @@ -81,6 +85,17 @@ with open(symbols_txt) as fin: nets[net].add(block) symbols.append((symbol_type, block, (output_net, expr))) + elif symbol_type == SYMBOL_TYPE_XOR: + assert len(fields) >= 3 + output_net = fields[2] + input_nets = fields[3:] + + for net in [output_net] + input_nets: + if net not in nets: + nets[net] = set() # blocks (of symbols) that the net visits + nets[net].add(block) + + symbols.append((symbol_type, block, (output_net, input_nets))) else: assert False @@ -180,5 +195,17 @@ for block, block_symbols in sorted(blocks.items()): fout.write(f' "{inner_node:s}" -> "{node:s}"\n') net_node = make_net_node(output_net) fout.write(f' "{node:s}" -> "{net_node:s}"\n') + elif symbol_type == SYMBOL_TYPE_XOR: + _, _, (output_net, input_nets) = symbols[i] + + node = f'xor:{output_net:s}' + fout.write(f' "{node:s}" [shape="invhouse", label="XOR"]\n') + for input_net in input_nets: + net_node = make_net_node(input_net) + fout.write(f' "{net_node:s}" -> "{node:s}"\n') + net_node = make_net_node(output_net) + fout.write(f' "{node:s}" -> "{net_node:s}"\n') + else: + assert False fout.write('}\n') diff --git a/scripts/blocks.sh b/scripts/blocks.sh index 170291f..653e1b1 100755 --- a/scripts/blocks.sh +++ b/scripts/blocks.sh @@ -2,7 +2,7 @@ if test $# -lt 1 then - echo "usage: $0 channels.txt|gates.txt" + echo "usage: $0 fets.txt|gates.txt|circuits.txt" exit 1 fi diff --git a/scripts/circuits.py b/scripts/circuits.py new file mode 100755 index 0000000..63008f0 --- /dev/null +++ b/scripts/circuits.py @@ -0,0 +1,295 @@ +#!/usr/bin/env python3 + +import itertools +import re +import sys + +SYMBOL_TYPE_FET = 0 +SYMBOL_TYPE_GATE = 1 +SYMBOL_TYPE_XOR = 2 +N_SYMBOL_TYPES = 3 + +CIRCUITS = [ + # (a AND b) NOR (a NOR b) => a XOR b + ( + [ + (SYMBOL_TYPE_GATE, (3, [[0, 1], [2]])), + (SYMBOL_TYPE_GATE, (2, [[0], [1]])), + ], + [ + (SYMBOL_TYPE_XOR, (3, [0, 1])), + ], + [False, False, True, False], + ), +] + +if len(sys.argv) < 3: + print(f'usage: {sys.argv[0]:s} symbols.txt net_gnd,net_vcc') + sys.exit(1) +symbols_txt = sys.argv[1] +[net_gnd, net_vcc] = sys.argv[2].split(',') + +nets = {} +symbols = [] +with open(symbols_txt) as fin: + line = fin.readline() + while len(line): + fields = line.split() + assert len(fields) >= 2 + symbol_type = int(fields[0]) + block = fields[1] + + if symbol_type == SYMBOL_TYPE_FET: + assert len(fields) == 8 + poly_net = fields[2] + n_diff_nets = int(fields[3]) + channel = fields[4] + x = float(fields[5]) + y = float(fields[6]) + mass = int(fields[7]) + + diff_nets = [] + r_matrix = [] + for i in range(n_diff_nets): + line = fin.readline() + assert len(line) + fields = line.split() + assert len(fields) == 1 + i + diff_nets.append(fields[0]) + r_matrix.append([float(j) for j in fields[1:]]) + + for net in [poly_net] + diff_nets: + if net not in nets: + nets[net] = set() # symbols that the net visits + nets[net].add(len(symbols)) + + symbols.append( + [ + symbol_type, # can be overwritten with -1 to delete the symbol + block, + (poly_net, diff_nets), + channel, + x, + y, + mass, + r_matrix + ] + ) + elif symbol_type == SYMBOL_TYPE_GATE: + assert len(fields) == 4 + output_net = fields[2] + n_products = int(fields[3]) + + expr = [] + for j in range(n_products): + line = fin.readline() + assert len(line) + expr.append(line.split()) + + if output_net not in nets: + nets[output_net] = set() # symbols that the net visits + nets[output_net].add(len(symbols)) + for product in expr: + for net in product: + if net not in nets: + nets[net] = set() # symbols that the net visits + nets[net].add(len(symbols)) + + symbols.append( + [ + symbol_type, # can be overwritten with -1 to delete the symbol + block, + (output_net, expr) + ] + ) + else: + assert False + + line = fin.readline() + +class Match(Exception): + pass + +for circuit_find, circuit_replace, circuit_internal in CIRCUITS: + assert len(circuit_find) + circuit_symbols = [-1] * len(circuit_find) + circuit_nets = [None] * len(circuit_internal) + + # recurse into symbol template looking for nets that already know (as we + # have unified against them already) and use them to narrow candidate set + def candidate_symbols(template): + #print('candidate_symbols', template) + candidates = None + for t in template: + #print('t', t) + if isinstance(t, tuple) or isinstance(t, list): + candidates1 = candidate_symbols(t) + else: # FIX THIS + #print('circuit_nets[t]', circuit_nets[t]) + if circuit_nets[t] is not None: + candidates1 = nets[circuit_nets[t]] + else: + continue + #print('candidates1', candidates1) + candidates = ( + candidates1 + if candidates is None else + candidates.intersection(candidates1) + ) + #print('candidate_symbols', template, 'returns', candidates) + return candidates + + # match either symbols or nets against template at top of stack, using + # the stack (tuple-chain) to follow the nested structure of the template, + # recursion to manage choicepoints and trailing, exception when matched + def match(level, stack): + while True: + if level == 0: # match symbols (top level) + i, template = stack + if i >= len(template): + # template unifies -- before raising a match we need to check that + # all nets flagged as internal are not connected to another symbol + symbols_internal = set(circuit_symbols) + for j in range(len(circuit_internal)): + if ( + circuit_internal[j] and + len(nets[circuit_nets[j]] - symbols_internal) + ): + #print('rejecting net', circuit_net[j]) + return + #print('match') + raise Match() + t = template[i] + assert isinstance(t[1], tuple) + stack = (i + 1, template) + candidates = candidate_symbols(t[1]) + #print('candidates', candidates) + for j in range(len(symbols)) if candidates is None else candidates: + a = symbols[j] + assert isinstance(a[2], tuple) + if t[0] == a[0] and len(t[1]) == len(a[2]): + #print('trying symbol', i, j) + circuit_symbols[i] = j + match(1, (0, t[1], a[2], stack)) + #print('failed symbol', i, j) + circuit_symbols[i] = -1 # not really necessary + return + + # match nets + i, template, actual, stack = stack + while i < len(template): + t = template[i] + a = actual[i] + #print('level', level, 'i', i, 't', t, 'a', a) + i += 1 + if isinstance(t, tuple): #or isinstance(t, list): + assert isinstance(a, tuple) + if len(t) != len(a): + #print('rejecting len(t)', len(t), 'len(a)', len(a)) + return + stack = (i, template, actual, stack) + # slow way: + #match(level + 1, (0, t, a, stack)) + #return + level += 1 + template = t + actual = a + i = 0 + elif isinstance(t, list): + assert isinstance(a, list) + if len(t) != len(a): + #print('rejecting len(t)', len(t), 'len(a)', len(a)) + return + stack = (i, template, actual, stack) + # for list try all permutations (only need to permute a) + for a1 in itertools.permutations(a): + #print('trying permutation', list(a1)) + match(level + 1, (0, t, list(a1), stack)) + #print('failed permutation', list(a1)) + return + elif isinstance(t, int): + assert isinstance(a, str) + if circuit_nets[t] != a: + if circuit_nets[t] is None: + #print('trying net', t, a) + stack = (i, template, actual, stack) + circuit_nets[t] = a + match(level, stack) + #print('failed net', t, a) + circuit_nets[t] = None + #else: + # print('rejecting circuit_nets[t]', circuit_nets[t]) + return + #else: + # print('matched circuit_nets[t]', circuit_nets[t]) + else: + assert False + level -= 1 + + # substitute the nets into one symbol of the replacement template + def substitute(template): + if isinstance(template, tuple): + return tuple(substitute(t) for t in template) + if isinstance(template, list): + return [substitute(t) for t in template] + if isinstance(template, int): + return circuit_nets[template] + assert False + + # outer search is special, as it keeps track of symbol we are up to, + # so we can restart from after that symbol after doing a replacement, + # it also resets the trail after each match so that the backtracking + # search does not need to untrail everything when a match is raised + t = circuit_find[0] + assert isinstance(t[1], tuple) + stack = (1, circuit_find) + for i in range(len(symbols)): + a = symbols[i] + assert isinstance(a[2], tuple) + if t[0] == a[0] and len(t[1]) == len(a[2]): + #print('trying symbol', 0, i) + circuit_symbols[0] = i + try: + match(1, (0, t[1], symbols[i][2], stack)) + #print('failed symbol', 0, i) + circuit_symbols[0] = -1 # not really necessary + except Match: + # block is taken from last template symbol (often the output) + block = symbols[circuit_symbols[-1]][1] + + # delete old symbols + for j in circuit_symbols: + symbols[j][0] = -1 + + # add new symbols + for symbol_type, template in circuit_replace: + symbols.append((symbol_type, block, substitute(template))) + + # continue search + circuit_symbols = [-1] * len(circuit_find) + circuit_nets = [None] * len(circuit_internal) + +for i in range(len(symbols)): + symbol_type = symbols[i][0] + if symbol_type == SYMBOL_TYPE_FET: + [ + _, + block, + (poly_net, diff_nets), + channel, + x, + y, + mass, + r_matrix + ] = symbols[i] + print(symbol_type, block, poly_net, len(diff_nets), channel, x, y, mass) + for i in range(len(diff_nets)): + print(' ' + diff_nets[i], ' '.join([str(j) for j in r_matrix[i]])) + elif symbol_type == SYMBOL_TYPE_GATE: + [_, block, (output_net, expr)] = symbols[i] + print(symbol_type, block, output_net, len(expr)) + for i in expr: + print(' ' + ' '.join(i)) + elif symbol_type == SYMBOL_TYPE_XOR: + [_, block, (output_net, input_nets)] = symbols[i] + print(symbol_type, block, output_net, ' '.join(input_nets)) -- 2.34.1