From b217a1d0e6ffffa776f21fac61ef35318dd64ab3 Mon Sep 17 00:00:00 2001 From: Nick Downing Date: Sun, 20 Jul 2025 15:30:53 +1000 Subject: [PATCH] Add /scripts/gates.py to analyze pulled-up networks and transform into gates --- .gitignore | 1 + 8085/Makefile | 13 ++-- 8085/node_names.txt | 2 + scripts/blocks.py | 154 +++++++++++++++++++++++++++++++++----------- scripts/blocks.sh | 11 +++- scripts/channels.py | 5 +- scripts/gates.py | 144 +++++++++++++++++++++++++++++++++++++++++ 7 files changed, 286 insertions(+), 44 deletions(-) create mode 100755 scripts/gates.py diff --git a/.gitignore b/.gitignore index abba946..304299f 100644 --- a/.gitignore +++ b/.gitignore @@ -14,6 +14,7 @@ /8085/channels.txt /8085/diff.png /8085/dot +/8085/gates.txt /8085/layers.png /8085/layers_rev.png /8085/metal.png diff --git a/8085/Makefile b/8085/Makefile index bea3d48..daf8b10 100644 --- a/8085/Makefile +++ b/8085/Makefile @@ -10,7 +10,7 @@ COLOURS=0,5,5,1,2,4,6,3,7 all: \ -channels.txt \ +gates.txt \ node_sizes.txt \ node_gnd.png \ node_vcc.png \ @@ -25,6 +25,9 @@ layers_rev.png #poly2.png \ #vias2.png +gates.txt: channels.txt + ../scripts/gates.py channels.txt GND,VCC >$@ + channels.txt: nodes.txt ../scripts/channels.py nodes.txt 1,4,5,6,7 >$@ @@ -38,10 +41,10 @@ node_vcc.png: nodes.txt ../scripts/node_image.py --adjacency nodes.txt VCC $@ ${COLOURS} node_phi0.png: nodes.txt - ../scripts/node_image.py --adjacency nodes.txt 3_0455_4632 $@ ${COLOURS} + ../scripts/node_image.py --adjacency nodes.txt phi0 $@ ${COLOURS} node_phi1.png: nodes.txt - ../scripts/node_image.py --adjacency nodes.txt 3_0304_3500 $@ ${COLOURS} + ../scripts/node_image.py --adjacency nodes.txt phi1 $@ ${COLOURS} nodes.txt: \ blocks.png \ @@ -132,7 +135,8 @@ vias2.png: vias1.png ../scripts/boolean.py 'vias.png^vias1.png' $@ clean: - rm -f \ + rm -rf \ +dot \ buried.png \ diff.png \ layers.png \ @@ -147,5 +151,6 @@ poly.png \ split_diff.png \ vias.png \ channels.txt \ +gates.txt \ node_sizes.txt \ nodes.txt diff --git a/8085/node_names.txt b/8085/node_names.txt index cf4e403..4fd8dcc 100644 --- a/8085/node_names.txt +++ b/8085/node_names.txt @@ -212,3 +212,5 @@ 2_5065_2576 pad_S0 2_5065_3034 pad_ALE 2_5073_5176 pad_READY +3_0455_4632 phi0 +3_0304_3500 phi1 diff --git a/scripts/blocks.py b/scripts/blocks.py index 958850a..91dcf64 100755 --- a/scripts/blocks.py +++ b/scripts/blocks.py @@ -9,16 +9,24 @@ if len(sys.argv) < 3: channels_txt = sys.argv[1] dot_dir = sys.argv[2] -blocks = {} nets = {} +blocks = {} channels = [] with open(channels_txt) as fin: line = fin.readline() - while len(line): + assert len(line) + fields = [int(i) for i in line.split()] + assert len(fields) >= 1 + n_channels = fields[0] + n_gates = fields[1] if len(fields) >= 2 else 0 + + for i in range(n_channels): + line = fin.readline() + assert len(line) fields = line.split() assert len(fields) == 7 - channel = fields[0] - block = fields[1] + block = fields[0] + channel = fields[1] poly_net = fields[2] n_diff_nets = int(fields[3]) x = float(fields[4]) @@ -26,61 +34,135 @@ with open(channels_txt) as fin: mass = int(fields[6]) diff_nets = [] r_matrix = [] - for i in range(n_diff_nets): + for j in range(n_diff_nets): line = fin.readline() assert len(line) fields = line.split() - assert len(fields) == 1 + i + assert len(fields) == 1 + j diff_nets.append(fields[0]) - r_matrix.append([float(j) for j in fields[1:]]) + r_matrix.append([float(k) for k in fields[1:]]) + + for net in [poly_net] + diff_nets: + if net not in nets: + nets[net] = set() # blocks (of channels/gates) that the net visits + nets[net].add(block) if block not in blocks: - blocks[block] = [] - blocks[block].append(len(channels)) + blocks[block] = ([], []) # channels, gates + blocks[block][0].append(len(channels)) channels.append( - (channel, block, poly_net, diff_nets, x, y, mass, r_matrix) + (block, channel, poly_net, diff_nets, x, y, mass, r_matrix) ) - for net in set([poly_net] + diff_nets): - if net not in nets: - nets[net] = set() # blocks (of the channels) that the net visits - nets[net].add(block) - + gates = [] + for i in range(n_gates): line = fin.readline() + assert len(line) + fields = line.split() + assert len(fields) == 3 + block = fields[0] + output_net = fields[1] + n_products = int(fields[2]) + + expr = [] + for j in range(n_products): + line = fin.readline() + assert len(line) + expr.append(line.split()) -for block, block_channels in sorted(blocks.items()): + for product in expr: + for net in product: + if net not in nets: + nets[net] = set() # blocks (of channels/gates) that the net visits + nets[net].add(block) + + if block not in blocks: + blocks[block] = ([], []) # channels, gates + blocks[block][1].append(len(gates)) + gates.append((block, output_net, expr)) + +for block, (block_channels, block_gates) in sorted(blocks.items()): with open(f'{dot_dir:s}/{block:s}.dot', 'w') as fout: fout.write(f'digraph "{block:s}" {{\n') net_nodes = set() - for channel_no in block_channels: - channel, block, poly_net, diff_nets, x, y, mass, r_matrix = \ - channels[channel_no] + disambiguator = 0 + def make_net_node(net): + global disambiguator + + if len(nets[net]) > 1: + # global net, make a new copy each time + net_node = f'net:{net:s}:{disambiguator:d}' + disambiguator += 1 + shape = 'box' + else: + # local net, make a shared copy + net_node = f'net:{net:s}' + shape = 'plaintext' + if net_node not in net_nodes: + net_nodes.add(net_node) + fout.write(f' "{net_node:s}" [shape={shape:s}, label="{net:s}"]\n') + return net_node + + for i in block_channels: + _, channel, poly_net, diff_nets, x, y, mass, r_matrix = channels[i] + + node = f'channel:{channel:s}' label = channel if len(r_matrix) == 2: label += f'\nR={r_matrix[1][0]:.3f}' else: label += f'\nC={mass / 2e4:.3f}' - fout.write(f' "{channel:s}" [label="{label:s}"]\n') - - def make_net_node(net): - if len(nets[net]) > 1: - # global net, make a new copy each time - net_node = f'{channel:s}:{net:s}' - shape = 'box' - else: - # local net, make a shared copy - net_node = net - shape = 'plaintext' - if net_node not in net_nodes: - net_nodes.add(net_node) - fout.write(f' "{net_node:s}" [shape={shape:s}, label="{net:s}"]\n') - return net_node + fout.write(f' "{node:s}" [label="{label:s}"]\n') net_node = make_net_node(poly_net) - fout.write(f' "{net_node:s}" -> "{channel:s}"\n') + fout.write(f' "{net_node:s}" -> "{node:s}"\n') for diff_net in diff_nets: net_node = make_net_node(diff_net) - fout.write(f' "{channel:s}" -> "{net_node:s}"\n') + fout.write(f' "{node:s}" -> "{net_node:s}" [arrowhead=none]\n') + + for i in block_gates: + _, output_net, expr = gates[i] + + node = f'gate:{output_net:s}' + if len(expr) == 1: + label = ( + 'FALSE' + if len(expr[0]) == 0 else + 'NOT' + if len(expr[0]) == 1 else + 'NAND' + ) + fout.write( + f' "{node:s}" [shape="invhouse", label="{label:s}"]\n' + ) + + for input_net in expr[0]: + net_node = make_net_node(input_net) + fout.write(f' "{net_node:s}" -> "{node:s}"\n') + else: + label = 'TRUE' if len(expr) == 0 else 'NOR' + fout.write( + f' "{node:s}" [shape="invhouse", label="{label:s}"]\n' + ) + + for j in range(len(expr)): + inner_node = f'{node:s}:{j:d}' + if len(expr[j]) == 1: + net_node = make_net_node(expr[j][0]) + fout.write(f' "{net_node:s}" -> "{node:s}"\n') + else: + label = 'TRUE' if len(expr[j]) == 0 else 'AND' + fout.write( + f' "{inner_node:s}" [shape="invhouse", label="{label:s}"]\n' + ) + + for input_net in expr[j]: + net_node = make_net_node(input_net) + fout.write(f' "{net_node:s}" -> "{inner_node:s}"\n') + 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') + fout.write('}\n') diff --git a/scripts/blocks.sh b/scripts/blocks.sh index 7c81bd7..9a1ce16 100755 --- a/scripts/blocks.sh +++ b/scripts/blocks.sh @@ -1,11 +1,18 @@ #!/bin/sh + +if test $# -lt 1 +then + echo "usage: $0 channels.txt|gates.txt" + exit 1 +fi + rm -rf dot mkdir dot -`dirname $0`/blocks.py channels.txt dot -( +`dirname $0`/blocks.py gates.txt dot && ( cd dot for i in *.dot do + echo $i dot -Tps -o `basename $i .dot`.ps $i done ) diff --git a/scripts/channels.py b/scripts/channels.py index 5a256ad..314488a 100755 --- a/scripts/channels.py +++ b/scripts/channels.py @@ -158,6 +158,7 @@ def resistor_solver(image): #print('R', 1. / sum_I2, 'squares') return 1. / sum_I2 +print(len(channels)) image = numpy.zeros((ys, xs), numpy.uint8) for (channel, (channel_items, channel_reports)) in sorted(channels.items()): #adjacent_nodes = set([items[item1][0] for _, item1 in channel_reports]) @@ -267,6 +268,6 @@ for (channel, (channel_items, channel_reports)) in sorted(channels.items()): r_matrix[-1].append(resistor_solver(image[min_y:max_y, min_x:max_x])) image[min_y:max_y, min_x:max_x] = 0 - print(channel, block, poly_net, len(diff_nets), x, y, mass) + print(block, channel, poly_net, len(diff_nets), x, y, mass) for i in range(len(diff_nets)): - print(diff_nets[i], ' '.join([str(j) for j in r_matrix[i]])) + print(' ' + diff_nets[i], ' '.join([str(j) for j in r_matrix[i]])) diff --git a/scripts/gates.py b/scripts/gates.py new file mode 100755 index 0000000..578b83c --- /dev/null +++ b/scripts/gates.py @@ -0,0 +1,144 @@ +#!/usr/bin/env python3 + +import re +import sys + +if len(sys.argv) < 3: + print(f'usage: {sys.argv[0]:s} channels.txt net_gnd,net_vcc') + sys.exit(1) +channels_txt = sys.argv[1] +[net_gnd, net_vcc] = sys.argv[2].split(',') + +nets = {} +channels = [] +with open(channels_txt) as fin: + line = fin.readline() + assert len(line) + [n_channels] = [int(i) for i in line.split()] + + for i in range(n_channels): + line = fin.readline() + assert len(line) + fields = line.split() + assert len(fields) == 7 + block = fields[0] + channel = fields[1] + poly_net = fields[2] + n_diff_nets = int(fields[3]) + x = float(fields[4]) + y = float(fields[5]) + mass = int(fields[6]) + 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] = [False, 0, []] # visited, n_connections, switches + nets[net][1] += 1 + + # make an index so we can quickly follow channels wired as switches + if len(diff_nets) == 2: + [diff_net0, diff_net1] = diff_nets + nets[diff_net0][2].append((len(channels), diff_net1)) + nets[diff_net1][2].append((len(channels), diff_net0)) + channels.append( + [True, block, channel, poly_net, diff_nets, x, y, mass, r_matrix] + ) # first element is valid flag, set to False to delete the channel + +# raised by follow() if pulled-up net doesn't appear to be a logic gate +class InvalidGate(Exception): + pass + +# routine to follow a net and find all the ways it could be pulled down +# expr is returned in and-or-invert format: list of list of net names +# inner list has nets to be ANDed together, outer list has products to +# be ORed together -- the OR of products, if true, pulls the output down +# note: expr of [] does not pull the output down, expr of [[]] does +def follow(del_channels, net, parent_net): + if net == net_gnd: + return [[]] + if net == net_vcc: + raise InvalidGate() # top level relies on this to skip the pull-up + if nets[net][1] != len(nets[net][2]): + raise InvalidGate() # internal net of gate can only connect to switches + + # check and set visited flag to avoid infinite recursion + if nets[net][0]: + raise InvalidGate() + nets[net][0] = True + + try: + expr = [] + for channel1, net1 in nets[net][2]: + if net1 != parent_net: + del_channels.append(channel1) + valid1, _, _, poly_net1, _, _, _, _, _ = channels[channel1] + if not valid1: + raise InvalidGate() + expr1 = follow(del_channels, net1, net) + expr.extend([i + [poly_net1] for i in expr1]) + return expr + finally: + nets[net][0] = False + +gates = [] +for i in range(len(channels)): + valid, block, channel, poly_net, diff_nets, _, _, _, _ = channels[i] + if valid: + # look for a channel wired as a pull-up to VCC (implied to be depletion) + if ( + poly_net != net_gnd and + poly_net != net_vcc and + (diff_nets == [poly_net, net_vcc] or diff_nets == [net_vcc, poly_net]) + ): + # the top level analysis ignores anything connected to the output that + # doesn't look like a pull-down (could be driving a transmission gate) + del_channels = [i] + expr = [] + nets[poly_net][0] = True # set visited flag to avoid infinite recursion + for channel1, net1 in nets[poly_net][2]: + valid1, _, _, poly_net1, _, _, _, _, _ = channels[channel1] + if valid1: + del_channels1 = [channel1] + try: + expr1 = follow(del_channels1, net1, poly_net) + del_channels.extend(del_channels1) + expr.extend([i + [poly_net1] for i in expr1]) + except InvalidGate: + pass + nets[poly_net][0] = False # set visited flag to avoid infinite recursion + + # don't allow constant expr (probably an error or analog circuit) + if expr != [] and expr != [[]]: + for channel1 in del_channels: + channels[channel1][0] = False + gates.append((block, poly_net, expr)) + +n_channels = sum([int(valid) for valid, _, _, _, _, _, _, _, _ in channels]) +print(n_channels, len(gates)) +for [ + valid, + block, + channel, + poly_net, + diff_nets, + x, + y, + mass, + r_matrix +] in channels: + if valid: + print(block, channel, poly_net, len(diff_nets), x, y, mass) + for i in range(len(diff_nets)): + print(' ' + diff_nets[i], ' '.join([str(j) for j in r_matrix[i]])) +for block, output_net, expr in gates: + print(block, output_net, len(expr)) + for i in expr: + print(' ' + ' '.join(i)) -- 2.34.1