gates1.java
Download: project files
gates1
is a gate-level logic simulator built on top of
the circuit and device objects contstructed for analog circuit
analysis.
One problem with this version is that new node values are used immediately each cycle. This makes the evaluation order sensitive. A better way would be to not alter node values until the end of each evaluation cycle.
This is a Java version of an earlier C++ project.
gates1.java
Gate.java
Node.java
Device.java
Circuit.java
gates1.java
001: // gates1.java 002: 003: import java.io.*; 004: import java.util.ArrayList; 005: 006: 007: // This class is a modified version of netlist3.java 008: public class gates1 { 009: 010: static public void main(String args[]) 011: { 012: String filename; 013: FileInputStream instream; 014: BufferedReader in; 015: 016: if (args.length < 1) { 017: System.err.println("usage: java gates1 source"); 018: System.exit(0); 019: } 020: try { 021: filename = args[0]; 022: instream = new FileInputStream(filename); 023: in = new BufferedReader(new InputStreamReader(instream)); 024: Circuit ckt = new Circuit(); 025: ckt.read(in); 026: in.close(); 027: System.out.println("\nDevice list:\n"); 028: ckt.list_devices(); 029: ckt.build_node_list(); 030: System.out.println("\nNode list:\n"); 031: ckt.list_nodes(); 032: if (ckt.inputs!=null || ckt.outputs!= null) System.out.println("\n\n"); 033: if (ckt.inputs!=null) show("inputs",ckt.inputs); 034: if (ckt.outputs!=null) show("outputs",ckt.outputs); 035: showTable(ckt); 036: } catch (IOException e) { 037: System.out.println( e); 038: } 039: } 040: 041: static void show(String name, String vals[]) 042: { 043: int j, nvals; 044: String str = name; 045: for (String val: vals) str += "\t" + val; 046: System.out.println(str); 047: } 048: 049: static void showTable(Circuit ckt) 050: { 051: String [] inputs = ckt.inputs; 052: String [] outputs = ckt.outputs; 053: int ninp = inputs.length; 054: int noup = outputs.length; 055: int ncases = (int) Math.pow(2,ninp); 056: int j, k, v; 057: String str = ""; 058: System.out.println("\n"); 059: for (j=0; j<ninp; j++) { 060: if (j>0) str += "\t" + inputs[j]; 061: else str = inputs[j]; 062: } 063: for (j=0; j<noup; j++) str += "\t" + outputs[j]; 064: System.out.println(str + "\tcycles\tmax_changed"); 065: 066: Node [] input_nodes = new Node[ninp]; 067: ArrayList<Node> changed_in = new ArrayList<Node>(); 068: ArrayList<Node> changed_out = new ArrayList<Node>(); 069: for (j=0; j<ninp; j++) { 070: Node node = ckt.find_node(inputs[j]); 071: if (node==null) System.err.printf("node %s not found\n",inputs[j]); 072: input_nodes[j] = node; 073: } 074: 075: Node [] output_nodes = new Node[noup]; 076: for (j=0; j<noup; j++) { 077: Node node = ckt.find_node(outputs[j]); 078: if (node==null) System.err.printf("node %s not found\n",outputs[j]); 079: output_nodes[j] = node; 080: } 081: // cycle through the possible input values (for a truth table) 082: for (k=0; k<ncases; k++) { 083: for (j = 0; j<ninp; j++) { 084: v = (k>>(ninp-1-j))&1; 085: if (j>0) str += "\t" + v; 086: else str = "" + v; 087: Node node = input_nodes[j]; 088: node.setValue(v); 089: changed_in.add(node); 090: 091: } 092: 093: // evaluate the circuit until nothing changes 094: int ncycles, change; 095: ncycles = 0; 096: change = ckt.eval(changed_in,changed_out); 097: int max_change = change; 098: while (change>0) { 099: ncycles++; 100: changed_in.clear(); 101: changed_in.addAll(changed_out); 102: changed_out.clear(); 103: change = ckt.eval(changed_in,changed_out); 104: if (change>max_change) max_change = change; 105: } 106: 107: // print the output values 108: for (j=0; j<noup; j++) str += "\t" + output_nodes[j].getLogic(); 109: System.out.println(str + "\t" + ncycles + "\t" + max_change); 110: } 111: } 112: 113: } 114: 115:
Gate.java
001: import java.util.ArrayList; 002: 003: 004: public class Gate extends Device 005: { 006: Gate(int n) 007: { 008: super(n); 009: } 010: 011: int eval(ArrayList<Node> nodes, ArrayList<Node> changed) { return -1; } 012: 013: // This version is like Device, except there is no "value" field. 014: public String toString() 015: { 016: String str = getCode() + "\t" + name; 017: for (String s: nodes) str += "\t" + s; 018: return str; 019: } 020: 021: public static Device getNewDevice(String type) 022: { 023: if (type.equals(Inverter.code)) return new Inverter(); 024: if (type.equals(And.code)) return new And(); 025: if (type.equals(Or.code)) return new Or(); 026: if (type.equals(Nand.code)) return new Nand(); 027: if (type.equals(Nor.code)) return new Nor(); 028: if (type.equals(Xor.code)) return new Xor(); 029: return null; 030: } 031: 032: static int aoi(Node arg[], int in, int out) 033: { 034: double result = (out>0? 0: 1); 035: double vin = in; 036: for (int i=1; i<3; i++) { 037: Node node = arg[i]; 038: if (node.isUnknown()) result = 0.5; 039: else if (node.equals(vin)) { 040: result = out; 041: break; 042: } 043: } 044: if (arg[0].equals(result)) return 0; 045: arg[0].setValue(result); 046: return 1; 047: } 048: } 049: 050: class Inverter extends Gate { 051: final static String code = "INV"; 052: Inverter() { 053: super(2); 054: } 055: String getType() { return "inverter"; } 056: String getCode() { return Inverter.code; } 057: int eval(ArrayList<Node> nodes, ArrayList<Node> changed) 058: { 059: Node inp = nodes.get(ndx[0]); 060: Node oup = nodes.get(ndx[1]); 061: double vout = 0.5; 062: if (inp.isLow()) vout = 1.0; 063: else if (inp.isHigh()) vout = 0.0; 064: if (oup.equals(vout)) return 0; 065: oup.setValue(vout); 066: changed.add(oup); 067: return 1; 068: } 069: } 070: 071: class And extends Gate { 072: final static String code = "AND"; 073: And() { 074: super(3); 075: } 076: String getType() { return "and"; } 077: String getCode() { return And.code; } 078: int eval(ArrayList<Node> nodes, ArrayList<Node> changed) 079: { 080: Node arg[] = new Node[3]; 081: for (int i=0; i<3; i++) arg[i] = nodes.get(ndx[i]); 082: int iret = Gate.aoi(arg,0,0); 083: if (iret>0) changed.add(arg[0]); 084: return iret; 085: } 086: } 087: 088: 089: class Or extends Gate { 090: final static String code = "OR"; 091: Or() { 092: super(3); 093: } 094: String getType() { return "or"; } 095: String getCode() { return Or.code; } 096: int eval(ArrayList<Node> nodes, ArrayList<Node> changed) 097: { 098: Node arg[] = new Node[3]; 099: for (int i=0; i<3; i++) arg[i] = nodes.get(ndx[i]); 100: int iret = Gate.aoi(arg,1,1); 101: if (iret>0) changed.add(arg[0]); 102: return iret; 103: } 104: } 105: 106: class Nand extends Gate { 107: final static String code = "NAND"; 108: Nand() { 109: super(3); 110: } 111: String getType() { return "nand"; } 112: String getCode() { return Nand.code; } 113: int eval(ArrayList<Node> nodes, ArrayList<Node> changed) 114: { 115: Node arg[] = new Node[3]; 116: for (int i=0; i<3; i++) arg[i] = nodes.get(ndx[i]); 117: int iret = Gate.aoi(arg,0,1); 118: if (iret>0) changed.add(arg[0]); 119: return iret; 120: } 121: } 122: 123: class Nor extends Gate { 124: final static String code = "NOR"; 125: Nor() { 126: super(3); 127: } 128: String getType() { return "nor"; } 129: String getCode() { return Nor.code; } 130: int eval(ArrayList<Node> nodes, ArrayList<Node> changed) 131: { 132: Node arg[] = new Node[3]; 133: for (int i=0; i<3; i++) arg[i] = nodes.get(ndx[i]); 134: int iret = Gate.aoi(arg,1,0); 135: if (iret>0) changed.add(arg[0]); 136: return iret; 137: } 138: } 139: 140: class Xor extends Gate { 141: final static String code = "XOR"; 142: Xor() { 143: super(3); 144: } 145: String getType() { return "xor"; } 146: String getCode() { return Xor.code; } 147: int eval(ArrayList<Node> nodes, ArrayList<Node> changed) 148: { 149: Node arg[] = new Node[3]; 150: for (int i=0; i<3; i++) arg[i] = nodes.get(ndx[i]); 151: double result = 0.5; 152: if (arg[1].isLow() && arg[2].isLow()) result = 0.0; 153: else if (arg[1].isHigh() && arg[2].isHigh()) result = 0.0; 154: else if (arg[1].isUnknown() || arg[2].isUnknown()) result = 0.5; 155: else result = 1.0; 156: if (arg[0].equals(result)) return 0; 157: arg[0].setValue(result); 158: changed.add(arg[0]); 159: return 1; 160: } 161: }
Node.java
01: import java.util.ArrayList; 02: 03: public class Node 04: { 05: String name; 06: int index; 07: double value; 08: static final double high = 0.7; 09: static final double low = 0.3; 10: ArrayList<Device> devices; 11: Node(String str) { 12: name = str; 13: value = 0.5; 14: index = 0; 15: devices = new ArrayList<Device>(); 16: } 17: 18: public String toString() 19: { 20: String str = name; 21: for (Device d: devices) str += "\t" + d.name; 22: return str; 23: } 24: public double getValue() { return value; } 25: public void setValue(double v) { value = v; } 26: public boolean isLow() { return value<low; } 27: public boolean isHigh() { return value>high; } 28: // returns true is value is neither low or high 29: public boolean isUnknown() 30: { 31: if (isLow()) return false; 32: return !isHigh(); 33: } 34: public boolean equals(double v) { return (Math.abs(value-v)<1e-5); } 35: public char getLogic() 36: { 37: if (isLow()) return '0'; 38: else if (isHigh()) return '1'; 39: else return 'X'; 40: } 41: } 42: 43: 44:
Device.java
01: import java.util.ArrayList; 02: 03: public abstract class Device { 04: String name; 05: String [] nodes; 06: int [] ndx; 07: double value; 08: 09: Device(int n) 10: { 11: nodes = new String[n]; 12: ndx = new int[n]; 13: value = 0.0; 14: } 15: 16: String getType() { return "device"; } 17: String getCode() { return "device_code"; } 18: 19: public void parse(String tok[]) 20: { 21: name = tok[1]; 22: int j, n, ntokens; 23: ntokens = tok.length; 24: n = nodes.length; 25: if (ntokens < n+2) { 26: System.out.printf("%d tokens %d needed\n",ntokens,n+2); 27: System.err.println("Input error - device has insufficient nodes"); 28: } 29: for (j=0; j<n; j++) nodes[j] = tok[2+j]; 30: n += 2; 31: if (ntokens<=n) return; 32: // logic may not have a value, but it might have an orientation 33: value = parseValue(tok[n]); 34: } 35: 36: public String toString() 37: { 38: String str = getType() + " " + getCode() + " " + name; 39: for (String s: nodes) str += " " + s; 40: str += " " + value; 41: return str; 42: } 43: 44: static public double parseValue(String str) 45: { 46: final String suffix = "afpnumkKMGT"; 47: final double scales[] = {1e-18, 1e-15, 1e-12, 1e-9, 1e-6, 1e-3, 1e3, 1e3, 1e6, 1e9, 1e12}; 48: char [] chars = str.toCharArray(); 49: int n = chars.length; 50: while (n>0) { 51: if (!Character.isLetter(chars[n-1])) break; 52: n--; 53: } 54: double v; 55: try { 56: if (n<chars.length) { 57: v = Double.parseDouble(str.substring(0,n)); 58: //System.out.printf("value %g suffix %s\n",v,str.substring(n)); 59: n = suffix.indexOf(chars[n]); 60: if (n<0) return v; 61: else v *= scales[n]; 62: } 63: else v = Double.parseDouble(str); 64: } 65: catch (NumberFormatException e) { 66: System.out.println(e); 67: v = 0.0; 68: } 69: return v; 70: } 71: }
Circuit.java
001: import java.io.*; 002: import java.util.ArrayList; 003: 004: public class Circuit 005: { 006: String name; 007: Node ref; 008: ArrayList<Node> nodes; 009: ArrayList<Device> devices; 010: String [] inputs; 011: String [] outputs; 012: 013: Circuit() 014: { 015: ref = new Node("0"); 016: devices = new ArrayList<Device>(); 017: nodes = new ArrayList<Node>(); 018: } 019: 020: public void read(BufferedReader inr) { 021: LineNumberReader in = new LineNumberReader(inr); 022: boolean done = false; 023: while (!done) { 024: int n = in.getLineNumber(); 025: try { 026: String inp = in.readLine(); 027: if (inp==null) break; 028: System.out.println("Line " + n + ": " + inp); 029: String [] str = inp.split("%"); // terminate at comment character 030: String [] tokens = str[0].split("\\s+"); 031: if (tokens.length>1) { 032: // This version just does gates 033: Device d = Gate.getNewDevice(tokens[0]); 034: if (d!=null) { 035: d.parse(tokens); 036: devices.add(d); 037: } 038: else if (tokens[0].equals("inputs")) inputs = saveTokens(tokens); 039: else if (tokens[0].equals("outputs")) outputs = saveTokens(tokens); 040: else System.out.println("Device not recognized: " + tokens[0] ); 041: } 042: } 043: catch (IOException e) { 044: System.out.println(e); 045: } 046: } 047: System.out.println(); 048: } 049: 050: String [] saveTokens(String tokens[]) 051: { 052: int i, ntokens; 053: ntokens = tokens.length; 054: String [] list = new String[ntokens-1]; 055: for (i=1; i<ntokens; i++) list[i-1] = tokens[i]; 056: return list; 057: } 058: 059: Node find_node(String str) 060: { 061: int ncount = nodes.size(); 062: for (int j=0; j<ncount; j++) { 063: Node node = nodes.get(j); 064: if (node.name.equals(str)) return node; 065: } 066: return null; 067: } 068: 069: 070: int add_node(String str, Device dev) 071: { 072: int i; 073: Node node; 074: int ncount = nodes.size(); 075: for (i=0; i<ncount; i++) { 076: node = nodes.get(i); 077: if (node.name.equals(str)) { 078: node.devices.add(dev); 079: return i; 080: } 081: } 082: node = new Node(str); 083: nodes.add(node); 084: node.devices.add(dev); 085: return ncount; 086: } 087: 088: void build_node_list() 089: { 090: int i, j; 091: Device dev; 092: int ndevices = devices.size(); 093: for (i=0; i<ndevices; i++) { 094: dev = devices.get(i); 095: int nodecount = dev.nodes.length; 096: for (j=0; j<nodecount; j++) dev.ndx[j] = add_node(dev.nodes[j],dev); 097: } 098: } 099: 100: void list_nodes() 101: { 102: for (Node node: nodes) System.out.println(node); 103: /* 104: int i; 105: int ncount = nodes.size(); 106: for (i=0; i<ncount; i++) { 107: Node node = nodes.get(i); 108: System.out.printf("%d\t %s\n",i,node); 109: } 110: */ 111: } 112: 113: 114: void list_devices() 115: { 116: for (Device d: devices) System.out.println(d); 117: } 118: 119: int eval(ArrayList<Node> changed_in, ArrayList<Node> changed_out) 120: { 121: ArrayList<Gate> devices = new ArrayList<Gate>(0); 122: Gate gate; 123: for (Node node: changed_in) { 124: for (Device dev: node.devices) { 125: gate = (Gate) dev; 126: // we only evaluate gates 127: if (!dev.getClass().isInstance(gate)) continue; 128: if (!devices.contains(gate)) devices.add(gate); 129: } 130: } 131: for (Gate dev: devices) dev.eval(nodes,changed_out); 132: return changed_out.size(); 133: } 134: }
Line 0: % simple gates Line 1: INV g1 A out1 Line 2: AND g2 out2 A B Line 3: OR g3 out3 A B Line 4: inputs A B Line 5: outputs out1 out2 out3 Device list: INV g1 A out1 AND g2 out2 A B OR g3 out3 A B Node list: A g1 g2 g3 out1 g1 out2 g2 B g2 g3 out3 g3 inputs A B outputs out1 out2 out3 A B out1 out2 out3 cycles max_changed 0 0 1 0 0 1 3 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1
Line 0: % simple gates Line 1: NAND g1 out1 A B Line 2: NOR g2 out2 A B Line 3: XOR g3 out3 A B Line 4: inputs A B Line 5: outputs out1 out2 out3 Device list: NAND g1 out1 A B NOR g2 out2 A B XOR g3 out3 A B Node list: out1 g1 A g1 g2 g3 B g1 g2 g3 out2 g2 out3 g3 inputs A B outputs out1 out2 out3 A B out1 out2 out3 cycles max_changed 0 0 1 1 0 1 3 0 1 1 0 1 1 2 1 0 1 0 1 0 0 1 1 0 0 0 1 2
Line 0: % simple gates Line 1: INV g1 A not_A Line 2: INV g2 B not_B Line 3: AND g3 w1 A not_B Line 4: AND g4 w2 B not_A Line 5: OR g5 out1 w1 w2 Line 6: XOR g6 out2 A B Line 7: inputs A B Line 8: outputs out1 out2 Line 9: Device list: INV g1 A not_A INV g2 B not_B AND g3 w1 A not_B AND g4 w2 B not_A OR g5 out1 w1 w2 XOR g6 out2 A B Node list: A g1 g3 g6 not_A g1 g4 B g2 g4 g6 not_B g2 g3 w1 g3 g5 w2 g4 g5 out1 g5 out2 g6 inputs A B outputs out1 out2 A B out1 out2 cycles max_changed 0 0 0 0 2 5 0 1 1 1 2 3 1 0 1 1 2 3 1 1 0 0 3 2
Maintained by John Loomis, updated Sun Mar 23 21:28:32 2008