summaryrefslogtreecommitdiff
path: root/libs/subcircuit
diff options
context:
space:
mode:
authorClifford Wolf <clifford@clifford.at>2013-02-27 09:32:19 +0100
committerClifford Wolf <clifford@clifford.at>2013-02-27 09:32:19 +0100
commita321a5c412090d04dfaea4b4876c4901c42cfe44 (patch)
treeb08d286e0aea76be9aab7a543df0b51e76b6ede4 /libs/subcircuit
parent4f0c2862a0d7e1ca247e0a4d54301c7f8cc92fd8 (diff)
Moved stand-alone libs to libs/ directory and added libs/subcircuit
Diffstat (limited to 'libs/subcircuit')
-rw-r--r--libs/subcircuit/Makefile52
-rw-r--r--libs/subcircuit/README440
-rw-r--r--libs/subcircuit/demo.cc134
-rw-r--r--libs/subcircuit/scshell.cc235
-rw-r--r--libs/subcircuit/subcircuit.cc1264
-rw-r--r--libs/subcircuit/subcircuit.h139
-rw-r--r--libs/subcircuit/test_large.spl221
-rw-r--r--libs/subcircuit/test_macc22.txt48
-rw-r--r--libs/subcircuit/test_perm.pl108
-rw-r--r--libs/subcircuit/test_shorts.spl121
10 files changed, 2762 insertions, 0 deletions
diff --git a/libs/subcircuit/Makefile b/libs/subcircuit/Makefile
new file mode 100644
index 00000000..af745b4b
--- /dev/null
+++ b/libs/subcircuit/Makefile
@@ -0,0 +1,52 @@
+
+CONFIG := clang-debug
+# CONFIG := gcc-debug
+# CONFIG := profile
+# CONFIG := release
+
+CC = clang
+CXX = clang
+CXXFLAGS = -MD -Wall -Wextra -ggdb
+LDLIBS = -lstdc++
+
+ifeq ($(CONFIG),clang-debug)
+CXXFLAGS += -std=c++11 -O0
+endif
+
+ifeq ($(CONFIG),gcc-debug)
+CC = gcc
+CXX = gcc
+CXXFLAGS += -std=gnu++0x -O0
+endif
+
+ifeq ($(CONFIG),profile)
+CC = gcc
+CXX = gcc
+CXXFLAGS += -std=gnu++0x -Os -DNDEBUG
+endif
+
+ifeq ($(CONFIG),release)
+CC = gcc
+CXX = gcc
+CXXFLAGS += -std=gnu++0x -march=native -O3 -DNDEBUG
+endif
+
+all: demo scshell
+
+demo: demo.o subcircuit.o
+
+scshell: scshell.o subcircuit.o
+
+test: scshell
+ ./scshell < test_macc22.txt
+ perl test_perm.pl | ./scshell
+ splrun test_shorts.spl | ./scshell
+ splrun test_large.spl | ./scshell
+
+clean:
+ rm -f demo scshell *.o *.d
+
+.PHONY: all test clean
+
+-include *.d
+
diff --git a/libs/subcircuit/README b/libs/subcircuit/README
new file mode 100644
index 00000000..5c8a8a9e
--- /dev/null
+++ b/libs/subcircuit/README
@@ -0,0 +1,440 @@
+
+ **************************************************************************
+ * *
+ * The SubCircuit C++11 library *
+ * *
+ * An implementation of a modified Ullmann Subgraph Isomorphism Algorithm *
+ * for coarse grain logic networks. by Clifford Wolf *
+ * *
+ **************************************************************************
+
+============
+Introduction
+============
+
+This is a library that implements a modified Ullmann Subgraph Isomorphism
+Algorithm with additional features aimed at working with coarse grain logic
+networks.
+
+A simple command line tool that exposes the features of the library is also
+included.
+
+
+Under-Construction Warning
+--------------------------
+
+This work is under constructions. It is likely that they are bugs in the
+library that need fixing. Feel free to contact me at clifford@clifford.at
+if you have found a bug.
+
+
+C++11 Warning
+-------------
+
+This project is written in C++11. Use appropriate compiler switches to compile
+it. Tested with clang version 3.0 and option -std=c++11. Also tested with gcc
+version 4.6.3 and option -std=c++0x.
+
+
+========
+Features
+========
+
+The input is two graphs (needle and haystack) that represent coarse grain
+logic networks. The algorithm identifies all subgraphs of haystack that are
+isomorphic to needle.
+
+The following additional features over the regular Ullmann Subgraph Isomorphism
+Algorithm are provided by the library.
+
+ * The graphs are attributed hypergraphs capable of representing netlists:
+
+ - Nodes represent the logic cells:
+ - Nodes have types and only match compatible types
+ - Nodes have ports with variable bit-width
+
+ - Hyperedges represent the signals:
+ - Each hyperedge connects one to many bits on ports on nodes
+
+ - Callback functions for advanced attributes and compatibility rules:
+ Any set of node-node compatibility rules and edge-edge
+ compatibility rules can be implemented by providing
+ the necessary callback functions.
+
+ * The algorithm is very efficient when all or many bits of one port are
+ connected to bits of the same other port. This is usually the case
+ in coarse grain logic networks. But the algorithm does not add any
+ restrictions in this area; it is just optimized for this scenario.
+
+ * The algorithm can be configured to allow larger ports in needle cells to
+ match smaller ports in haystack cells in certain situations. This way it
+ is possible to e.g. have a 32-bit adder cell in the needle match a
+ 16-bit adder cell in the haystack.
+
+ * The algorithm can be configured to perform port-swapping on certain
+ ports on certain cell types to match commutative operations properly.
+
+ This is, however, not implemented very efficiently when a larger number
+ of permutations is possible on a cell type. Therefore it is recommended
+ to only use swap groups with only a few members and a few such groups
+ on one cell type type.
+
+ Also note, that the algorithm can not resolve complex dependencies
+ between the port swappings of different cells. Therefore it is
+ recommended to only use port swapping on input pins of commutative
+ operations, where such complex dependencies can not emerge.
+
+ * The algorithm can be configured to distinguish between internal signals
+ of the needle and externally visible signals. The needle will only
+ match a subgraph of the haystack if that subgraph does not expose the
+ internal signal to nodes in the haystack outside the matching subgraph.
+
+ * The algorithm can recognize a subcircuit even if some or all of its
+ inputs and/or outputs are shorted together.
+
+ * Explicit fast support for constant signals without extra nodes for
+ constant drivers.
+
+ * Support for finding only non-overlapping matches.
+
+ * The public API of the library is using std::string identifiers for
+ nodes, node types and ports. Internally the costly part of the
+ algorithm is only using integer values, thus speeding up the
+ algorithm without exposing complex internal encodings to the caller.
+
+
+=================
+API Documentation
+=================
+
+This section gives a brief overview of the API. For a working example, have a
+look at the demo.cc example program in this directory.
+
+
+Setting up graphs
+-----------------
+
+Instanciate the SubCircuit::Graph class and use the methods of this class to
+set up the circuit.
+
+ SubCircuit::Graph myGraph;
+
+For each node in the circuit call the createNode() method. Specify the
+identifier for the node and also the type of function implemented by the node.
+Then call createPort() for each port of this node.
+
+E.g. the following code adds a node "myAdder" of type "add" with three 32 bit
+wide ports "A", "B" and "Y". Note that SubCircuit does not care which port is
+an input and which port is an output. The last (and optional) argument to
+createPort() specifies the minimum number of bits required for this port in the
+haystack (this field is only used in the needle graph). So in this example the
+node would e.g. also match any adder with a bit width smaller 32.
+
+ myGraph.createNode("myAdder", "add");
+ myGraph.createPort("myAdder", "A", 32, 1);
+ myGraph.createPort("myAdder", "B", 32, 1);
+ myGraph.createPort("myAdder", "Y", 32, 1);
+
+The createConnection() method can be used to connect the nodes. It internally
+creates a hypergraph. So the following code does not only connect cell1.Y with
+cell2.A and cell3.A but also implicitly cell2.A with cell3.A.
+
+ myGraph.createConnection("cell1", "Y", "cell2", "A");
+ myGraph.createConnection("cell1", "Y", "cell3", "A");
+
+Redundent calls to createConnection() are ignored. As long as the method is
+called after the relevant nodes and ports are created, the order in which the
+createConnection() calls are performed is irrelevant.
+
+The createConnection() method can also be used to connect single bit signals.
+In this case the start bit for both ports must be provided as well as an
+optional width (which defaults to 1). E.g. the following calls can be used to
+connect the 32 bit port cell4.Y to the 32 bit port cell5.A with a one bit left
+rotate shift,
+
+ myGraph.createConnection("cell4", "Y", 0, "cell5", "A", 1, 31);
+ myGraph.createConnection("cell4", "Y", 31, "cell5", "A", 0);
+
+The method createConstant() can be used to add a constant driver to a signal.
+The signal value is encoded as one char by bit, allowing for multi-valued
+logic matching. The follwoing command sets the lowest bit of cell6.A to a
+logic 1:
+
+ myGraph.createConnection("cell6", "A", 0, '1');
+
+It is also possible to set an entire port to a integer value, using the
+encodings '0' and '1' for the binary digits:
+
+ myGraph.createConnection("cell6", "A", 42);
+
+The method markExtern() can be used to mark a signal as externally visible. In
+a needle graph this means, this signal may match a signal in the haystack that
+is used outside the matching subgraph. In a haystack graph this means, this
+signal is used outside the haystack graph. I.e. an internal signal of the
+needle won't match an external signal of the haystack regardless where the
+signal is used in the haystack.
+
+In some application one may disable this extern/intern checks. This can easily
+be achieved by marking all signals in the needle as extern. This can be done
+using the Graph::markAllExtern() method.
+
+
+Setting up and running solvers
+------------------------------
+
+To actually run the subgraph isomorphism algorithm, an instance of
+SubCircuit::Solver must be created.
+
+ SubCircuit::Solver mySolver;
+
+The addGraph() method can be used to register graphs with the solver:
+
+ mySolver.addGraph("graph1", myGraph);
+ mySolver.addGraph("graph2", myOtherGraph);
+
+Usually nodes in the needle and the haystack must have the same type identifier
+to match each other. Additionally pairs of compatible needle and haystack node
+pairs can be registered using the addCompatibleTypes() method:
+
+ mySolver.addCompatibleTypes("alu", "add");
+ mySolver.addCompatibleTypes("alu", "sub");
+ mySolver.addCompatibleTypes("alu", "and");
+ mySolver.addCompatibleTypes("alu", "or");
+ mySolver.addCompatibleTypes("alu", "xor");
+
+Note that nodes in needle and haystack must also use the same naming convention
+for their ports in order to be considered compatible by the algorithm.
+
+Similarly the method addCompatibleConstants() can be used the specify which
+constant values in the needle should match which constant value in the haystack.
+Equal values always do match.
+
+ mySolver.addCompatibleConstants('x', '0');
+ mySolver.addCompatibleConstants('x', '1');
+
+Some cells implement commutative operations that don't care if their input
+operands are swapped. For this cell types it is possible to register groups
+of swappable ports. Let's consider a cell "macc23" that implements the
+function Y = (A * B) + (C * D * E):
+
+ mySolver.addSwappablePorts("macc23", "A", "B");
+ mySolver.addSwappablePorts("macc23", "C", "D", "E");
+
+Sometimes the rules for port swapping are a more complicated and the swapping
+of one port is related to the swapping of another port. Let's consider a cell
+"macc22" that implements the function Y = (A * B) + (C * D):
+
+ mySolver.addSwappablePorts("macc22", "A", "B");
+ mySolver.addSwappablePorts("macc22", "C", "D");
+
+ std::map<std::string, std::string> portMapping;
+ portMapping["A"] = "C";
+ portMapping["B"] = "D";
+ portMapping["C"] = "A";
+ portMapping["D"] = "B";
+ mySolver.addSwappablePortsPermutation("macc22", portMapping);
+
+I.e. the method mySolver.addSwappablePortsPermutation() can be used to register
+additional permutations for a node type of which one or none is applied on top
+of the permutations yielded by the permutations generated by the swap groups.
+
+Note that two solutions that differ only in the applied port swapping are not
+reported as separate solutions. Instead only one of them is selected (in most
+cases the one with less port swapping as it is usually identified first).
+
+Once everything has been set up, the solve() method can be used to actually
+search for isomorphic subgraphs. The first argument to solve() is an
+std::vector<SubCircuit::Solver::Result> objects to which all found solutions
+are appended. The second argument is the identifier under which the needle
+graph has been registered and the third argument is the identifier under which
+the haystack graph has been registered:
+
+ std::vector<SubCircuit::Solver::Result> results;
+ mySolver.solve(results, "graph1", "graph2");
+
+The SubCircuit::Solver::Result object is a simple data structure that contains
+the mappings between needle and haystack nodes, port mappings after the port
+swapping and some additional metadata. See "subcircuit.h" and "demo.cc" for
+details.
+
+The solve() method has a third optional boolean argument. If it is set to
+false, solve will not return any solutions that contain haystack nodes that
+have been part of a previously found solution. This way it is e.g. easy
+to implement a greedy macro cell matching algorithm:
+
+ std::vector<SubCircuit::Solver::Result> results;
+ mySolver.solve(results, "macroCell1", "circuit", false);
+ mySolver.solve(results, "macroCell2", "circuit", false);
+ mySolver.solve(results, "macroCell3", "circuit", false);
+
+After this code has been executed, the results vector contains all
+non-overlapping matches of the three macrocells. The method
+clearOverlapHistory() can be used to reset the internal state used
+for this feature. The default value for the third argument to solve()
+is true (allow overlapping).
+
+The solve() method also has a fourth optional integer argument. If it is set to
+a positive integer, this integer specifies the maximum number of solutions to
+be appended to the results vector, i.e. to terminate the algorithm early when
+the set number of matches is found. When this fourth argument is negative or
+omitted all matches are found and appended.
+
+An alternative version of the solve() method supports an additional argument
+after they haystack graph identifier that specifies initial mappings for
+the algorithm. In the following example only the haystack nodes cell_1 and
+cell_2 are considered as mappings for the needle node cell_A:
+
+ std::map<std::string, std::set<std::string>> initialMappings;
+ initialMappings["cell_A"].insert("cell_1");
+ initialMappings["cell_A"].insert("cell_2");
+
+ std::vector<SubCircuit::Solver::Result> results;
+ mySolver.solve(results, "graph1", "graph2", initialMappings);
+
+The clearConfig() method can be used to clear all data registered using
+addCompatibleTypes(), addCompatibleConstants(), addSwappablePorts() and
+addSwappablePortsPermutation() but retaining the graphs and the overlap state.
+
+
+Using user callback function
+----------------------------
+
+For more complex tasks it is possible to derive a class from SubCircuit::Solver
+that overloads one or more of the following virtual methods. The userData
+arguments to the following methods are void pointers that can be passed as
+third argument to Graph::createNode() and are simly passed thru to the user
+callback functions together with the node id whenever a node is referenced.
+
+bool userCompareNodes(needleGraphId, needleNodeId, needleUserData, haystackGraphId, haystackNodeId, haystackUserData):
+
+ Perform additional checks on a pair of nodes (one from the needle, one
+ from the haystack) to determine if the nodes are compatible. The default
+ implementation always returns true.
+
+
+bool userCompareEdge(needleGraphId, needleFromNodeId, needleFromUserData, needleToNodeId, needleToUserData,
+ haystackGraphId, haystackFromNodeId, haystackFromUserData, haystackToNodeId, haystackToUserData):
+
+ Perform additional checks on a pair of a pair of adjacent nodes (one
+ adjacent pair from the needle and one adjacent pair from the haystack)
+ to determine wheter this edge from the needle is compatible with
+ that edge from the haystack. The default implementation always
+ returns true.
+
+bool userCheckSolution(result):
+
+ Perform additional checks on a solution before appending it to the
+ results vector. When this function returns false, the solution is
+ ignored. The default implementation always returns true.
+
+
+Debugging
+---------
+
+For debugging purposes the SubCircuit::Solver class implements a setVerbose()
+method. When called once, all further calls to the solve() method cause the
+algorithm to dump out a lot of debug information to stdout.
+
+In conjunction with setVerbose() one can also overload the userAnnotateEdge()
+method in order to add additional information about the edges to the debug
+output.
+
+
+===================
+Shell Documentation
+===================
+
+This package also contains a small command-line tool called "scshell" that can
+be used for experimentation with the algorithm. This program reads a series of
+commands from stdin and reports its findings to stdout on exit.
+
+ $ ./scshell < test_macc22.txt
+
+ ...
+
+ Match #3: (macc22 in macc4x2)
+ add_1 -> add_2 A:B B:A Y:Y
+ mul_1 -> mul_4 A:A B:B Y:Y
+ mul_2 -> mul_3 A:A B:B Y:Y
+
+The following commands can be used in scshell to specify graphs:
+
+ graph <graph_name>
+ ...
+ endgraph
+
+ Used to specify a graph with the given name. Only the commands
+ "node", "connect" and "extern" may be used within the graph ...
+ endgraph block.
+
+ node <node_name> [<port_name> [<bits> [<min_bits>]]]+
+
+ Used to create a node and ports. This command is a direct frontend
+ to the Graph::createNode() and Graph::createPort() methods.
+
+ connect <from_node> <from_port> <to_node> <to_port>
+ connect <from_node> <from_port> <from_bit> <to_node> <to_port> <to_bit>
+ connect <from_node> <from_port> <from_bit> <to_node> <to_port> <to_bit> <width>
+
+ Used to connect the nodes in the graph via Graph::createConnection().
+
+ constant <node> <port> [<bit>] <value>
+
+ Call Graph::createConstant().
+
+ extern <node> [<port> [<bit>]]+
+
+ Mark signals as extern via Graph::markExtern().
+
+ allextern
+
+ Mark all signals as extern via Graph::markAllExtern().
+
+The following commands can be used in scshell outside a graph ... endgraph block:
+
+ compatible <needle_type> <haystack_type>
+
+ Call Solver::addCompatibleTypes().
+
+ constcompat <needle_value> <haystack_value>
+
+ Call Solver::addCompatibleConstants().
+
+ swapgroup <needle_type> <port>+
+
+ Call Solver::addSwappablePorts().
+
+ swapperm <needle_type> <ports>+ : <ports>+
+
+ Call Solver::addSwappablePortsPermutation(). Both port lists must
+ have the same length and the second one must be a permutation of the
+ first one.
+
+ initmap <needle_node> <haystack_node>+
+
+ Add an entry to the initial mappings for the next solve command.
+ This mappings are automatically reset after the solve command.
+
+ solve <needle_graph> <haystack_graph> [<allow_overlap> [<max_solutions>]]
+
+ Call Solver::solve(). The <allow_overlap> must be "1" or "true"
+ for true and "0" or "false" for false.
+
+ expect <number>
+
+ Print all results so far since the last call to expect. Expect
+ <number> results and exit with error code 1 if a different number
+ of results have been found.
+
+ clearoverlap
+
+ Call Solver::clearOverlapHistory().
+
+ clearconfig
+
+ Call Solver::clearConfig().
+
+ verbose
+
+ Call Solver::setVerbose().
+
diff --git a/libs/subcircuit/demo.cc b/libs/subcircuit/demo.cc
new file mode 100644
index 00000000..149dc6aa
--- /dev/null
+++ b/libs/subcircuit/demo.cc
@@ -0,0 +1,134 @@
+#include "subcircuit.h"
+#include <stdio.h>
+
+#define VERBOSE
+
+int main()
+{
+ SubCircuit::Graph needle, haystack;
+
+ // create needle graph
+
+ needle.createNode("mul_1", "product");
+ needle.createPort("mul_1", "A", 4);
+ needle.createPort("mul_1", "B", 4);
+ needle.createPort("mul_1", "Y", 4);
+ needle.markExtern("mul_1", "A");
+ needle.markExtern("mul_1", "B");
+
+ needle.createNode("mul_2", "product");
+ needle.createPort("mul_2", "A", 4);
+ needle.createPort("mul_2", "B", 4);
+ needle.createPort("mul_2", "Y", 4);
+ needle.markExtern("mul_2", "A");
+ needle.markExtern("mul_2", "B");
+
+ needle.createNode("add_1", "sum");
+ needle.createPort("add_1", "A", 4);
+ needle.createPort("add_1", "B", 4);
+ needle.createPort("add_1", "Y", 4);
+ needle.markExtern("add_1", "Y");
+
+ needle.createConnection("mul_1", "Y", "add_1", "A");
+ needle.createConnection("mul_2", "Y", "add_1", "B");
+
+#ifdef VERBOSE
+ printf("\n");
+ needle.print();
+#endif
+
+ // create haystack graph
+
+#if 0
+ for (int i = 0; i < 4; i++) {
+ char id[100];
+ snprintf(id, 100, "mul_%d", i);
+ haystack.createNode(id, "mul");
+ haystack.createPort(id, "A", 4);
+ haystack.createPort(id, "B", 4);
+ haystack.createPort(id, "Y", 4);
+ haystack.markExtern(id, "A");
+ haystack.markExtern(id, "B");
+ }
+
+ for (int i = 0; i < 3; i++) {
+ char id[100];
+ snprintf(id, 100, "add_%d", i);
+ haystack.createNode(id, "add");
+ haystack.createPort(id, "A", 4);
+ haystack.createPort(id, "B", 4);
+ haystack.createPort(id, "Y", 4);
+ }
+
+ haystack.createConnection("mul_0", "Y", "add_0", "A");
+ haystack.createConnection("mul_1", "Y", "add_0", "B");
+
+ haystack.createConnection("mul_2", "Y", "add_1", "A");
+ haystack.createConnection("mul_3", "Y", "add_1", "B");
+
+ haystack.createConnection("add_0", "Y", "add_2", "A");
+ haystack.createConnection("add_1", "Y", "add_2", "B");
+ haystack.markExtern("add_2", "Y");
+#else
+ std::vector<std::string> cellIds;
+ srand48(12345);
+
+ for (int i = 0; i < 45; i++) {
+ char id[100];
+ snprintf(id, 100, "cell_%02d", i);
+ haystack.createNode(id, i < 30 ? "mul" : "add");
+ haystack.createPort(id, "A", 4);
+ haystack.createPort(id, "B", 4);
+ haystack.createPort(id, "Y", 4);
+ cellIds.push_back(id);
+ }
+
+ for (int i = 0; i < int(cellIds.size()); i++) {
+ if (lrand48() % (i < 20 ? 3 : 2) != 0)
+ continue;
+ const std::string &id = cellIds[i];
+ const std::string &id_left = cellIds[lrand48() % cellIds.size()];
+ const std::string &id_right = cellIds[lrand48() % cellIds.size()];
+ haystack.createConnection(id_left, "Y", id, "A");
+ haystack.createConnection(id_right, "Y", id, "B");
+ }
+#endif
+
+#ifdef VERBOSE
+ printf("\n");
+ haystack.print();
+#endif
+
+ // search needle in haystack
+
+ SubCircuit::Solver solver;
+ std::vector<SubCircuit::Solver::Result> results;
+
+#ifdef VERBOSE
+ solver.setVerbose();
+#endif
+
+ solver.addCompatibleTypes("product", "mul");
+ solver.addCompatibleTypes("sum", "add");
+
+ solver.addSwappablePorts("product", "A", "B");
+ solver.addSwappablePorts("sum", "A", "B");
+
+ solver.addGraph("needle", needle);
+ solver.addGraph("haystack", haystack);
+ solver.solve(results, "needle", "haystack");
+
+ for (int i = 0; i < int(results.size()); i++) {
+ printf("\nMatch #%d: (%s in %s)\n", i, results[i].needleGraphId.c_str(), results[i].haystackGraphId.c_str());
+ for (const auto &it : results[i].mappings) {
+ printf(" %s -> %s", it.first.c_str(), it.second.haystackNodeId.c_str());
+ for (const auto &it2 : it.second.portMapping)
+ printf(" %s:%s", it2.first.c_str(), it2.second.c_str());
+ printf("\n");
+ }
+ }
+
+ printf("\n");
+ return 0;
+}
+
diff --git a/libs/subcircuit/scshell.cc b/libs/subcircuit/scshell.cc
new file mode 100644
index 00000000..70afcfd4
--- /dev/null
+++ b/libs/subcircuit/scshell.cc
@@ -0,0 +1,235 @@
+#include "subcircuit.h"
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+std::vector<std::string> readLine()
+{
+ char buffer[4096];
+ std::vector<std::string> tokenList;
+
+ while (tokenList.size() == 0 && fgets(buffer, sizeof(buffer), stdin) != NULL) {
+ for (char *p = buffer; char *tok = strtok(p, " \t\r\n"); p = NULL) {
+ if (p != NULL && tok[0] == '#')
+ break;
+ tokenList.push_back(tok);
+ }
+ }
+
+ return tokenList;
+}
+
+int main()
+{
+ std::string graphId;
+ SubCircuit::Graph *graph = NULL;
+ SubCircuit::Solver solver;
+ std::map<std::string, std::set<std::string>> initialMappings;
+ std::vector<SubCircuit::Solver::Result> results;
+ std::vector<std::string> cmdBuffer;
+ bool lastCommandExpect = false;
+
+ while (1)
+ {
+ cmdBuffer = readLine();
+ if (cmdBuffer.empty())
+ break;
+
+ printf(graph == NULL || cmdBuffer[0] == "endgraph" ? ">" : "> ");
+ for (const auto &tok : cmdBuffer)
+ printf(" %s", tok.c_str());
+ printf("\n");
+
+ lastCommandExpect = false;
+
+ if (graph != NULL)
+ {
+ if (cmdBuffer[0] == "node" && cmdBuffer.size() >= 3) {
+ graph->createNode(cmdBuffer[1], cmdBuffer[2]);
+ for (int i = 3; i < int(cmdBuffer.size()); i++) {
+ std::string portId = cmdBuffer[i];
+ int width = 1, minWidth = -1;
+ if (i+1 < int(cmdBuffer.size()) && '0' <= cmdBuffer[i+1][0] && cmdBuffer[i+1][0] <= '9')
+ width = atoi(cmdBuffer[++i].c_str());
+ if (i+1 < int(cmdBuffer.size()) && '0' <= cmdBuffer[i+1][0] && cmdBuffer[i+1][0] <= '9')
+ minWidth = atoi(cmdBuffer[++i].c_str());
+ graph->createPort(cmdBuffer[1], portId, width, minWidth);
+ }
+ continue;
+ }
+
+ if (cmdBuffer[0] == "connect" && cmdBuffer.size() == 5) {
+ graph->createConnection(cmdBuffer[1], cmdBuffer[2], cmdBuffer[3], cmdBuffer[4]);
+ continue;
+ }
+
+ if (cmdBuffer[0] == "connect" && cmdBuffer.size() == 7) {
+ graph->createConnection(cmdBuffer[1], cmdBuffer[2], atoi(cmdBuffer[3].c_str()), cmdBuffer[4], cmdBuffer[5], atoi(cmdBuffer[6].c_str()));
+ continue;
+ }
+
+ if (cmdBuffer[0] == "connect" && cmdBuffer.size() == 8) {
+ graph->createConnection(cmdBuffer[1], cmdBuffer[2], atoi(cmdBuffer[3].c_str()), cmdBuffer[4], cmdBuffer[5], atoi(cmdBuffer[6].c_str()), atoi(cmdBuffer[7].c_str()));
+ continue;
+ }
+
+ if (cmdBuffer[0] == "constant" && cmdBuffer.size() == 5) {
+ int constValue = cmdBuffer[4].size() > 1 && cmdBuffer[4][0] == '#' ? atoi(cmdBuffer[4].c_str()+1) : cmdBuffer[4][0];
+ graph->createConstant(cmdBuffer[1], cmdBuffer[2], atoi(cmdBuffer[3].c_str()), constValue);
+ continue;
+ }
+
+ if (cmdBuffer[0] == "constant" && cmdBuffer.size() == 4) {
+ graph->createConstant(cmdBuffer[1], cmdBuffer[2], atoi(cmdBuffer[3].c_str()));
+ continue;
+ }
+
+ if (cmdBuffer[0] == "extern" && cmdBuffer.size() >= 3) {
+ for (int i = 2; i < int(cmdBuffer.size()); i++) {
+ std::string portId = cmdBuffer[i];
+ int bit = -1;
+ if (i+1 < int(cmdBuffer.size()) && '0' <= cmdBuffer[i+1][0] && cmdBuffer[i+1][0] <= '9')
+ bit = atoi(cmdBuffer[++i].c_str());
+ graph->markExtern(cmdBuffer[1], portId, bit);
+ }
+ continue;
+ }
+
+ if (cmdBuffer[0] == "allextern" && cmdBuffer.size() == 1) {
+ graph->markAllExtern();
+ continue;
+ }
+
+ if (cmdBuffer[0] == "endgraph" && cmdBuffer.size() == 1) {
+ solver.addGraph(graphId, *graph);
+ delete graph;
+ graph = NULL;
+ continue;
+ }
+ }
+ else
+ {
+ if (cmdBuffer[0] == "graph" && cmdBuffer.size() == 2) {
+ graph = new SubCircuit::Graph;
+ graphId = cmdBuffer[1];
+ continue;
+ }
+
+ if (cmdBuffer[0] == "compatible" && cmdBuffer.size() == 3) {
+ solver.addCompatibleTypes(cmdBuffer[1], cmdBuffer[2]);
+ continue;
+ }
+
+ if (cmdBuffer[0] == "constcompat" && cmdBuffer.size() == 3) {
+ int needleConstValue = cmdBuffer[1].size() > 1 && cmdBuffer[1][0] == '#' ? atoi(cmdBuffer[1].c_str()+1) : cmdBuffer[1][0];
+ int haystackConstValue = cmdBuffer[2].size() > 1 && cmdBuffer[2][0] == '#' ? atoi(cmdBuffer[2].c_str()+1) : cmdBuffer[2][0];
+ solver.addCompatibleConstants(needleConstValue, haystackConstValue);
+ continue;
+ }
+
+ if (cmdBuffer[0] == "swapgroup" && cmdBuffer.size() >= 4) {
+ std::set<std::string> ports;
+ for (int i = 2; i < int(cmdBuffer.size()); i++)
+ ports.insert(cmdBuffer[i]);
+ solver.addSwappablePorts(cmdBuffer[1], ports);
+ continue;
+ }
+
+ if (cmdBuffer[0] == "swapperm" && cmdBuffer.size() >= 4 && cmdBuffer.size() % 2 == 1 && cmdBuffer[cmdBuffer.size()/2 + 1] == ":") {
+ std::map<std::string, std::string> portMapping;
+ int n = (cmdBuffer.size()-3) / 2;
+ for (int i = 0; i < n; i++)
+ portMapping[cmdBuffer[i+2]] = cmdBuffer[i+3+n];
+ solver.addSwappablePortsPermutation(cmdBuffer[1], portMapping);
+ continue;
+ }
+
+ if (cmdBuffer[0] == "initmap" && cmdBuffer.size() >= 4) {
+ for (int i = 2; i < int(cmdBuffer.size()); i++)
+ initialMappings[cmdBuffer[1]].insert(cmdBuffer[i]);
+ continue;
+ }
+
+ if (cmdBuffer[0] == "solve" && 3 <= cmdBuffer.size() && cmdBuffer.size() <= 5) {
+ bool allowOverlap = true;
+ int maxSolutions = -1;
+ if (cmdBuffer.size() >= 4)
+ allowOverlap = cmdBuffer[3] == "true" || atoi(cmdBuffer[3].c_str()) ? true : false;
+ if (cmdBuffer.size() >= 5)
+ maxSolutions = atoi(cmdBuffer[4].c_str());
+ solver.solve(results, cmdBuffer[1], cmdBuffer[2], initialMappings, allowOverlap, maxSolutions);
+ initialMappings.clear();
+ continue;
+ }
+
+ if (cmdBuffer[0] == "clearoverlap" && cmdBuffer.size() == 1) {
+ solver.clearOverlapHistory();
+ continue;
+ }
+
+ if (cmdBuffer[0] == "clearconfig" && cmdBuffer.size() == 1) {
+ solver.clearConfig();
+ continue;
+ }
+
+ if (cmdBuffer[0] == "verbose" && cmdBuffer.size() == 1) {
+ solver.setVerbose();
+ continue;
+ }
+
+ if (cmdBuffer[0] == "expect" && cmdBuffer.size() == 2) {
+ int expected = atoi(cmdBuffer[1].c_str());
+ printf("\n-- Expected %d, Got %d --\n", expected, int(results.size()));
+ for (int i = 0; i < int(results.size()); i++) {
+ printf("\nMatch #%d: (%s in %s)\n", i, results[i].needleGraphId.c_str(), results[i].haystackGraphId.c_str());
+ for (const auto &it : results[i].mappings) {
+ printf(" %s -> %s", it.first.c_str(), it.second.haystackNodeId.c_str());
+ for (const auto &it2 : it.second.portMapping)
+ printf(" %s:%s", it2.first.c_str(), it2.second.c_str());
+ printf("\n");
+ }
+ }
+ printf("\n");
+ if (expected != int(results.size())) {
+ printf("^^ expected %d, Got %d ^^\n\n", expected, int(results.size()));
+ printf(" +----------------+\n");
+ printf(" | \\|/ ____ \\|/ |\n");
+ printf(" | \"@'/ ,. \\`@\" |\n");
+ printf(" | /_| \\__/ |_\\ |\n");
+ printf(" | \\__U_/ |\n");
+ printf(" | | | |\n");
+ printf(" +----------------+\n\n");
+ return 1;
+ }
+ results.clear();
+ lastCommandExpect = true;
+ continue;
+ }
+ }
+
+ printf("Invalid input command!\n");
+ return 1;
+ }
+
+ if (graph)
+ delete graph;
+
+ if (!lastCommandExpect) {
+ printf("\n-- Got %d --\n", int(results.size()));
+ for (int i = 0; i < int(results.size()); i++) {
+ printf("\nMatch #%d: (%s in %s)\n", i, results[i].needleGraphId.c_str(), results[i].haystackGraphId.c_str());
+ for (const auto &it : results[i].mappings) {
+ printf(" %s -> %s", it.first.c_str(), it.second.haystackNodeId.c_str());
+ for (const auto &it2 : it.second.portMapping)
+ printf(" %s:%s", it2.first.c_str(), it2.second.c_str());
+ printf("\n");
+ }
+ }
+ } else
+ printf("PASSED.\n");
+
+ printf("\n");
+
+ return 0;
+}
+
diff --git a/libs/subcircuit/subcircuit.cc b/libs/subcircuit/subcircuit.cc
new file mode 100644
index 00000000..b49fa97c
--- /dev/null
+++ b/libs/subcircuit/subcircuit.cc
@@ -0,0 +1,1264 @@
+/*
+ * SubCircuit -- An implementation of the Ullmann Subgraph Isomorphism
+ * algorithm for coarse grain logic networks
+ *
+ * Copyright (C) 2013 Clifford Wolf <clifford@clifford.at>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ */
+
+#include "subcircuit.h"
+
+#include <algorithm>
+#include <assert.h>
+#include <stdarg.h>
+#include <stdio.h>
+
+using namespace SubCircuit;
+
+static std::string stringf(const char *fmt, ...)
+{
+ std::string string;
+ char *str = NULL;
+ va_list ap;
+
+ va_start(ap, fmt);
+ if (vasprintf(&str, fmt, ap) < 0)
+ str = NULL;
+ va_end(ap);
+
+ if (str != NULL) {
+ string = str;
+ free(str);
+ }
+
+ return string;
+}
+
+bool SubCircuit::Graph::BitRef::operator < (const BitRef &other) const
+{
+ if (nodeIdx != other.nodeIdx)
+ return nodeIdx < other.nodeIdx;
+ if (portIdx != other.portIdx)
+ return portIdx < other.portIdx;
+ return bitIdx < other.bitIdx;
+}
+
+void SubCircuit::Graph::createNode(std::string nodeId, std::string typeId, void *userData)
+{
+ assert(nodeMap.count(nodeId) == 0);
+ nodeMap[nodeId] = nodes.size();
+ nodes.push_back(Node());
+
+ Node &newNode = nodes.back();
+ newNode.nodeId = nodeId;
+ newNode.typeId = typeId;
+ newNode.userData = userData;
+}
+
+void SubCircuit::Graph::createPort(std::string nodeId, std::string portId, int width, int minWidth)
+{
+ assert(nodeMap.count(nodeId) != 0);
+ int nodeIdx = nodeMap[nodeId];
+ Node &node = nodes[nodeIdx];
+
+ assert(node.portMap.count(portId) == 0);
+
+ int portIdx = node.ports.size();
+ node.portMap[portId] = portIdx;
+ node.ports.push_back(Port());
+ Port &port = node.ports.back();
+
+ port.portId = portId;
+ port.minWidth = minWidth < 0 ? width : minWidth;
+ port.bits.insert(port.bits.end(), width, PortBit());
+
+ for (int i = 0; i < width; i++) {
+ port.bits[i].edgeIdx = edges.size();
+ edges.push_back(Edge());
+ edges.back().portBits.insert(BitRef(nodeIdx, portIdx, i));
+ }
+}
+
+void SubCircuit::Graph::createConnection(std::string fromNodeId, std::string fromPortId, int fromBit, std::string toNodeId, std::string toPortId, int toBit, int width)
+{
+ assert(nodeMap.count(fromNodeId) != 0);
+ assert(nodeMap.count(toNodeId) != 0);
+
+ int fromNodeIdx = nodeMap[fromNodeId];
+ Node &fromNode = nodes[fromNodeIdx];
+
+ int toNodeIdx = nodeMap[toNodeId];
+ Node &toNode = nodes[toNodeIdx];
+
+ assert(fromNode.portMap.count(fromPortId) != 0);
+ assert(toNode.portMap.count(toPortId) != 0);
+
+ int fromPortIdx = fromNode.portMap[fromPortId];
+ Port &fromPort = fromNode.ports[fromPortIdx];
+
+ int toPortIdx = toNode.portMap[toPortId];
+ Port &toPort = toNode.ports[toPortIdx];
+
+ if (width < 0) {
+ assert(fromBit == 0 && toBit == 0);
+ assert(fromPort.bits.size() == toPort.bits.size());
+ width = fromPort.bits.size();
+ }
+
+ assert(fromBit >= 0 && toBit >= 0);
+ for (int i = 0; i < width; i++)
+ {
+ assert(fromBit + i < int(fromPort.bits.size()));
+ assert(toBit + i < int(toPort.bits.size()));
+
+ int fromEdgeIdx = fromPort.bits[fromBit + i].edgeIdx;
+ int toEdgeIdx = toPort.bits[toBit + i].edgeIdx;
+
+ if (fromEdgeIdx == toEdgeIdx)
+ continue;
+
+ // merge toEdge into fromEdge
+ if (edges[toEdgeIdx].isExtern)
+ edges[fromEdgeIdx].isExtern = true;
+ if (edges[toEdgeIdx].constValue) {
+ assert(edges[fromEdgeIdx].constValue == 0);
+ edges[fromEdgeIdx].constValue = edges[toEdgeIdx].constValue;
+ }
+ for (const auto &ref : edges[toEdgeIdx].portBits) {
+ edges[fromEdgeIdx].portBits.insert(ref);
+ nodes[ref.nodeIdx].ports[ref.portIdx].bits[ref.bitIdx].edgeIdx = fromEdgeIdx;
+ }
+
+ // remove toEdge (move last edge over toEdge if needed)
+ if (toEdgeIdx+1 != int(edges.size())) {
+ edges[toEdgeIdx] = edges.back();
+ for (const auto &ref : edges[toEdgeIdx].portBits)
+ nodes[ref.nodeIdx].ports[ref.portIdx].bits[ref.bitIdx].edgeIdx = toEdgeIdx;
+ }
+ edges.pop_back();
+ }
+}
+
+void SubCircuit::Graph::createConnection(std::string fromNodeId, std::string fromPortId, std::string toNodeId, std::string toPortId)
+{
+ createConnection(fromNodeId, fromPortId, 0, toNodeId, toPortId, 0, -1);
+}
+
+void SubCircuit::Graph::createConstant(std::string toNodeId, std::string toPortId, int toBit, int constValue)
+{
+ assert(nodeMap.count(toNodeId) != 0);
+ int toNodeIdx = nodeMap[toNodeId];
+ Node &toNode = nodes[toNodeIdx];
+
+ assert(toNode.portMap.count(toPortId) != 0);
+ int toPortIdx = toNode.portMap[toPortId];
+ Port &toPort = toNode.ports[toPortIdx];
+
+ assert(toBit >= 0 && toBit < int(toPort.bits.size()));
+ int toEdgeIdx = toPort.bits[toBit].edgeIdx;
+
+ assert(edges[toEdgeIdx].constValue == 0);
+ edges[toEdgeIdx].constValue = constValue;
+}
+
+void SubCircuit::Graph::createConstant(std::string toNodeId, std::string toPortId, int constValue)
+{
+ assert(nodeMap.count(toNodeId) != 0);
+ int toNodeIdx = nodeMap[toNodeId];
+ Node &toNode = nodes[toNodeIdx];
+
+ assert(toNode.portMap.count(toPortId) != 0);
+ int toPortIdx = toNode.portMap[toPortId];
+ Port &toPort = toNode.ports[toPortIdx];
+
+ for (int i = 0; i < int(toPort.bits.size()); i++) {
+ int toEdgeIdx = toPort.bits[i].edgeIdx;
+ assert(edges[toEdgeIdx].constValue == 0);
+ edges[toEdgeIdx].constValue = constValue % 2 ? '1' : '0';
+ constValue = constValue >> 1;
+ }
+}
+
+void SubCircuit::Graph::markExtern(std::string nodeId, std::string portId, int bit)
+{
+ assert(nodeMap.count(nodeId) != 0);
+ Node &node = nodes[nodeMap[nodeId]];
+
+ assert(node.portMap.count(portId) != 0);
+ Port &port = node.ports[node.portMap[portId]];
+
+ if (bit < 0) {
+ for (const auto portBit : port.bits)
+ edges[portBit.edgeIdx].isExtern = true;
+ } else {
+ assert(bit < int(port.bits.size()));
+ edges[port.bits[bit].edgeIdx].isExtern = true;
+ }
+}
+
+void SubCircuit::Graph::markAllExtern()
+{
+ allExtern = true;
+}
+
+void SubCircuit::Graph::print()
+{
+ for (int i = 0; i < int(nodes.size()); i++) {
+ const Node &node = nodes[i];
+ printf("NODE %d: %s (%s)\n", i, node.nodeId.c_str(), node.typeId.c_str());
+ for (int j = 0; j < int(node.ports.size()); j++) {
+ const Port &port = node.ports[j];
+ printf(" PORT %d: %s (%d/%d)\n", j, port.portId.c_str(), port.minWidth, int(port.bits.size()));
+ for (int k = 0; k < int(port.bits.size()); k++) {
+ int edgeIdx = port.bits[k].edgeIdx;
+ printf(" BIT %d (%d):", k, edgeIdx);
+ for (const auto &ref : edges[edgeIdx].portBits)
+ printf(" %d.%d.%d", ref.nodeIdx, ref.portIdx, ref.bitIdx);
+ if (edges[edgeIdx].isExtern)
+ printf(" [extern]");
+ printf("\n");
+ }
+ }
+ }
+}
+
+class SubCircuit::SolverWorker
+{
+ // basic internal data structures
+
+ typedef std::vector<std::map<int, int>> adjMatrix_t;
+
+ struct GraphData {
+ std::string graphId;
+ Graph graph;
+ adjMatrix_t adjMatrix;
+ std::vector<bool> usedNodes;
+ };
+
+ static void printAdjMatrix(const adjMatrix_t &matrix)
+ {
+ printf("%7s", "");
+ for (int i = 0; i < int(matrix.size()); i++)
+ printf("%4d:", i);
+ printf("\n");
+ for (int i = 0; i < int(matrix.size()); i++) {
+ printf("%5d:", i);
+ for (int j = 0; j < int(matrix.size()); j++)
+ if (matrix.at(i).count(j) == 0)
+ printf("%5s", "-");
+ else
+ printf("%5d", matrix.at(i).at(j));
+ printf("\n");
+ }
+ }
+
+ // helper functions for handling permutations
+
+ static const int maxPermutationsLimit = 1000000;
+
+ static int numberOfPermutations(const std::vector<std::string> &list)
+ {
+ int numPermutations = 1;
+ for (int i = 0; i < int(list.size()); i++) {
+ assert(numPermutations < maxPermutationsLimit);
+ numPermutations *= i+1;
+ }
+ return numPermutations;
+ }
+
+ static void permutateVectorToMap(std::map<std::string, std::string> &map, const std::vector<std::string> &list, int idx)
+ {
+ // convert idx to a list.size() digits factoradic number
+
+ std::vector<int> factoradicDigits;
+ for (int i = 0; i < int(list.size()); i++) {
+ factoradicDigits.push_back(idx % (i+1));
+ idx = idx / (i+1);
+ }
+
+ // construct permutation
+
+ std::vector<std::string> pool = list;
+ std::vector<std::string> permutation;
+
+ while (!factoradicDigits.empty()) {
+ int i = factoradicDigits.back();
+ factoradicDigits.pop_back();
+ permutation.push_back(pool[i]);
+ pool.erase(pool.begin() + i);
+ }
+
+ // update map
+
+ for (int i = 0; i < int(list.size()); i++)
+ map[list[i]] = permutation[i];
+ }
+
+ static int numberOfPermutationsArray(const std::vector<std::vector<std::string>> &list)
+ {
+ int numPermutations = 1;
+ for (const auto &it : list) {
+ int thisPermutations = numberOfPermutations(it);
+ assert(float(numPermutations) * float(thisPermutations) < maxPermutationsLimit);
+ numPermutations *= thisPermutations;
+ }
+ return numPermutations;
+ }
+
+ static void permutateVectorToMapArray(std::map<std::string, std::string> &map, const std::vector<std::vector<std::string>> &list, int idx)
+ {
+ for (const auto &it : list) {
+ int thisPermutations = numberOfPermutations(it);
+ int thisIdx = idx % thisPermutations;
+ permutateVectorToMap(map, it, thisIdx);
+ idx /= thisPermutations;
+ }
+ }
+
+ static void applyPermutation(std::map<std::string, std::string> &map, const std::map<std::string, std::string> &permutation)
+ {
+ std::vector<std::pair<std::string, std::string>> changeLog;
+ for (const auto &it : permutation)
+ if (map.count(it.second))
+ changeLog.push_back(std::pair<std::string, std::string>(it.first, map.at(it.second)));
+ else
+ changeLog.push_back(std::pair<std::string, std::string>(it.first, it.second));
+ for (const auto &it : changeLog)
+ map[it.first] = it.second;
+ }
+
+ // classes for internal digraph representation
+
+ struct DiBit
+ {
+ std::string fromPort, toPort;
+ int fromBit, toBit;
+
+ DiBit() : fromPort(), toPort(), fromBit(-1), toBit(-1) { }
+ DiBit(std::string fromPort, int fromBit, std::string toPort, int toBit) : fromPort(fromPort), toPort(toPort), fromBit(fromBit), toBit(toBit) { }
+
+ bool operator < (const DiBit &other) const
+ {
+ if (fromPort != other.fromPort)
+ return fromPort < other.fromPort;
+ if (toPort != other.toPort)
+ return toPort < other.toPort;
+ if (fromBit != other.fromBit)
+ return fromBit < other.fromBit;
+ return toBit < other.toBit;
+ }
+
+ std::string toString() const
+ {
+ return stringf("%s[%d]:%s[%d]", fromPort.c_str(), fromBit, toPort.c_str(), toBit);
+ }
+ };
+
+ struct DiNode
+ {
+ std::string typeId;
+ std::map<std::string, int> portSizes;
+
+ DiNode()
+ {
+ }
+
+ DiNode(const Graph &graph, int nodeIdx)
+ {
+ const Graph::Node &node = graph.nodes.at(nodeIdx);
+ typeId = node.typeId;
+ for (const auto &port : node.ports)
+ portSizes[port.portId] = port.bits.size();
+ }
+
+ bool operator < (const DiNode &other) const
+ {
+ if (typeId != other.typeId)
+ return typeId < other.typeId;
+ return portSizes < other.portSizes;
+ }
+
+ std::string toString() const
+ {
+ std::string str;
+ bool firstPort = true;
+ for (const auto &it : portSizes) {
+ str += stringf("%s%s[%d]", firstPort ? "" : ",", it.first.c_str(), it.second);
+ firstPort = false;
+ }
+ return typeId + "(" + str + ")";
+ }
+ };
+
+ struct DiEdge
+ {
+ DiNode fromNode, toNode;
+ std::set<DiBit> bits;
+ std::string userAnnotation;
+
+ bool operator < (const DiEdge &other) const
+ {
+ if (fromNode < other.fromNode || other.fromNode < fromNode)
+ return fromNode < other.fromNode;
+ if (toNode < other.toNode || other.toNode < toNode)
+ return toNode < other.toNode;
+ if (bits < other.bits || other.bits < bits)
+ return bits < other.bits;
+ return userAnnotation < other.userAnnotation;
+ }
+
+ bool compare(const DiEdge &other, const std::map<std::string, std::string> &mapFromPorts, const std::map<std::string, std::string> &mapToPorts) const
+ {
+ // Rules for matching edges:
+ //
+ // For all bits in the needle edge:
+ // - ignore if needle ports don't exist in haystack edge
+ // - otherwise: matching bit in haystack edge must exist
+ //
+ // There is no need to check in the other direction, as checking
+ // of the isExtern properties is already performed in node matching.
+ //
+ // Note: "this" is needle, "other" is haystack
+
+ for (auto bit : bits)
+ {
+ if (mapFromPorts.count(bit.fromPort) > 0)
+ bit.fromPort = mapFromPorts.at(bit.fromPort);
+ if (mapToPorts.count(bit.toPort) > 0)
+ bit.toPort = mapToPorts.at(bit.toPort);
+
+ if (other.fromNode.portSizes.count(bit.fromPort) == 0)
+ continue;
+ if (other.toNode.portSizes.count(bit.toPort) == 0)
+ continue;
+
+ if (bit.fromBit >= other.fromNode.portSizes.at(bit.fromPort))
+ continue;
+ if (bit.toBit >= other.toNode.portSizes.at(bit.toPort))
+ continue;
+
+ if (other.bits.count(bit) == 0)
+ return false;
+ }
+
+ return true;
+ }
+
+ bool compareWithFromAndToPermutations(const DiEdge &other, const std::map<std::string, std::string> &mapFromPorts, const std::map<std::string, std::string> &mapToPorts,
+ const std::map<std::string, std::set<std::map<std::string, std::string>>> &swapPermutations) const
+ {
+ if (swapPermutations.count(fromNode.typeId) > 0)
+ for (const auto &permutation : swapPermutations.at(fromNode.typeId)) {
+ std::map<std::string, std::string> thisMapFromPorts = mapFromPorts;
+ applyPermutation(thisMapFromPorts, permutation);
+ if (compareWithToPermutations(other, thisMapFromPorts, mapToPorts, swapPermutations))
+ return true;
+ }
+ return compareWithToPermutations(other, mapFromPorts, mapToPorts, swapPermutations);
+ }
+
+ bool compareWithToPermutations(const DiEdge &other, const std::map<std::string, std::string> &mapFromPorts, const std::map<std::string, std::string> &mapToPorts,
+ const std::map<std::string, std::set<std::map<std::string, std::string>>> &swapPermutations) const
+ {
+ if (swapPermutations.count(toNode.typeId) > 0)
+ for (const auto &permutation : swapPermutations.at(toNode.typeId)) {
+ std::map<std::string, std::string> thisMapToPorts = mapToPorts;
+ applyPermutation(thisMapToPorts, permutation);
+ if (compare(other, mapFromPorts, thisMapToPorts))
+ return true;
+ }
+ return compare(other, mapFromPorts, mapToPorts);
+ }
+
+ bool compare(const DiEdge &other, const std::map<std::string, std::set<std::set<std::string>>> &swapPorts,
+ const std::map<std::string, std::set<std::map<std::string, std::string>>> &swapPermutations) const
+ {
+ // brute force method for port swapping: try all variations
+
+ std::vector<std::vector<std::string>> swapFromPorts;
+ std::vector<std::vector<std::string>> swapToPorts;
+
+ // only use groups that are relevant for this edge
+
+ if (swapPorts.count(fromNode.typeId) > 0)
+ for (const auto &ports : swapPorts.at(fromNode.typeId)) {
+ for (const auto &bit : bits)
+ if (ports.count(bit.fromPort))
+ goto foundFromPortMatch;
+ if (0) {
+ foundFromPortMatch:
+ std::vector<std::string> portsVector;
+ for (const auto &port : ports)
+ portsVector.push_back(port);
+ swapFromPorts.push_back(portsVector);
+ }
+ }
+
+ if (swapPorts.count(toNode.typeId) > 0)
+ for (const auto &ports : swapPorts.at(toNode.typeId)) {
+ for (const auto &bit : bits)
+ if (ports.count(bit.toPort))
+ goto foundToPortMatch;
+ if (0) {
+ foundToPortMatch:
+ std::vector<std::string> portsVector;
+ for (const auto &port : ports)
+ portsVector.push_back(port);
+ swapToPorts.push_back(portsVector);
+ }
+ }
+
+ // try all permutations
+
+ std::map<std::string, std::string> mapFromPorts, mapToPorts;
+ int fromPortsPermutations = numberOfPermutationsArray(swapFromPorts);
+ int toPortsPermutations = numberOfPermutationsArray(swapToPorts);
+
+ for (int i = 0; i < fromPortsPermutations; i++)
+ {
+ permutateVectorToMapArray(mapFromPorts, swapFromPorts, i);
+
+ for (int j = 0; j < toPortsPermutations; j++) {
+ permutateVectorToMapArray(mapToPorts, swapToPorts, j);
+ if (compareWithFromAndToPermutations(other, mapFromPorts, mapToPorts, swapPermutations))
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ bool compare(const DiEdge &other, const std::map<std::string, std::string> &mapFromPorts, const std::map<std::string, std::set<std::set<std::string>>> &swapPorts,
+ const std::map<std::string, std::set<std::map<std::string, std::string>>> &swapPermutations) const
+ {
+ // strip-down version of the last function: only try permutations for mapToPorts, mapFromPorts is already provided by the caller
+
+ std::vector<std::vector<std::string>> swapToPorts;
+
+ if (swapPorts.count(toNode.typeId) > 0)
+ for (const auto &ports : swapPorts.at(toNode.typeId)) {
+ for (const auto &bit : bits)
+ if (ports.count(bit.toPort))
+ goto foundToPortMatch;
+ if (0) {
+ foundToPortMatch:
+ std::vector<std::string> portsVector;
+ for (const auto &port : ports)
+ portsVector.push_back(port);
+ swapToPorts.push_back(portsVector);
+ }
+ }
+
+ std::map<std::string, std::string> mapToPorts;
+ int toPortsPermutations = numberOfPermutationsArray(swapToPorts);
+
+ for (int j = 0; j < toPortsPermutations; j++) {
+ permutateVectorToMapArray(mapToPorts, swapToPorts, j);
+ if (compareWithToPermutations(other, mapFromPorts, mapToPorts, swapPermutations))
+ return true;
+ }
+
+ return false;
+ }
+
+ std::string toString() const
+ {
+ std::string buffer = fromNode.toString() + " " + toNode.toString();
+ for (const auto &bit : bits)
+ buffer += " " + bit.toString();
+ if (!userAnnotation.empty())
+ buffer += " " + userAnnotation;
+ return buffer;
+ }
+
+ static void findEdgesInGraph(const Graph &graph, std::map<std::pair<int, int>, DiEdge> &edges)
+ {
+ edges.clear();
+ for (const auto &edge : graph.edges) {
+ if (edge.constValue != 0)
+ continue;
+ for (const auto &fromBit : edge.portBits)
+ for (const auto &toBit : edge.portBits)
+ if (&fromBit != &toBit) {
+ DiEdge &de = edges[std::pair<int, int>(fromBit.nodeIdx, toBit.nodeIdx)];
+ de.fromNode = DiNode(graph, fromBit.nodeIdx);
+ de.toNode = DiNode(graph, toBit.nodeIdx);
+ std::string fromPortId = graph.nodes[fromBit.nodeIdx].ports[fromBit.portIdx].portId;
+ std::string toPortId = graph.nodes[toBit.nodeIdx].ports[toBit.portIdx].portId;
+ de.bits.insert(DiBit(fromPortId, fromBit.bitIdx, toPortId, toBit.bitIdx));
+ }
+ }
+ }
+ };
+
+ struct DiCache
+ {
+ std::map<DiEdge, int> edgeTypesMap;
+ std::vector<DiEdge> edgeTypes;
+ std::map<std::pair<int, int>, bool> compareCache;
+
+ void add(const Graph &graph, adjMatrix_t &adjMatrix, const std::string &graphId, Solver *userSolver)
+ {
+ std::map<std::pair<int, int>, DiEdge> edges;
+ DiEdge::findEdgesInGraph(graph, edges);
+
+ adjMatrix.clear();
+ adjMatrix.resize(graph.nodes.size());
+
+ for (auto &it : edges) {
+ const Graph::Node &fromNode = graph.nodes[it.first.first];
+ const Graph::Node &toNode = graph.nodes[it.first.second];
+ it.second.userAnnotation = userSolver->userAnnotateEdge(graphId, fromNode.nodeId, fromNode.userData, toNode.nodeId, toNode.userData);
+ }
+
+ for (const auto &it : edges) {
+ if (edgeTypesMap.count(it.second) == 0) {
+ edgeTypesMap[it.second] = edgeTypes.size();
+ edgeTypes.push_back(it.second);
+ }
+ adjMatrix[it.first.first][it.first.second] = edgeTypesMap[it.second];
+ }
+ }
+
+ bool compare(int needleEdge, int haystackEdge, const std::map<std::string, std::set<std::set<std::string>>> &swapPorts,
+ const std::map<std::string, std::set<std::map<std::string, std::string>>> &swapPermutations)
+ {
+ std::pair<int, int> key(needleEdge, haystackEdge);
+ if (!compareCache.count(key))
+ compareCache[key] = edgeTypes.at(needleEdge).compare(edgeTypes.at(haystackEdge), swapPorts, swapPermutations);
+ return compareCache[key];
+ }
+
+ bool compare(int needleEdge, int haystackEdge, const std::map<std::string, std::string> &mapFromPorts, const std::map<std::string, std::set<std::set<std::string>>> &swapPorts,
+ const std::map<std::string, std::set<std::map<std::string, std::string>>> &swapPermutations) const
+ {
+ return edgeTypes.at(needleEdge).compare(edgeTypes.at(haystackEdge), mapFromPorts, swapPorts, swapPermutations);
+ }
+
+ bool compare(int needleEdge, int haystackEdge, const std::map<std::string, std::string> &mapFromPorts, const std::map<std::string, std::string> &mapToPorts) const
+ {
+ return edgeTypes.at(needleEdge).compare(edgeTypes.at(haystackEdge), mapFromPorts, mapToPorts);
+ }
+
+ void printEdgeTypes() const
+ {
+ for (int i = 0; i < int(edgeTypes.size()); i++)
+ printf("%5d: %s\n", i, edgeTypes[i].toString().c_str());
+ }
+ };
+
+ // solver state variables
+
+ Solver *userSolver;
+ std::map<std::string, GraphData> graphData;
+ std::map<std::string, std::set<std::string>> compatibleTypes;
+ std::map<int, std::set<int>> compatibleConstants;
+ std::map<std::string, std::set<std::set<std::string>>> swapPorts;
+ std::map<std::string, std::set<std::map<std::string, std::string>>> swapPermutations;
+ DiCache diCache;
+ bool verbose;
+
+ // main solver functions
+
+ bool matchNodes(const Graph &needle, int needleNodeIdx, const Graph &haystack, int haystackNodeIdx) const
+ {
+ // Rules for matching nodes:
+ //
+ // 1. their typeId must be identical or compatible
+ // (this is checked before calling this function)
+ //
+ // 2. they must have the same ports and the haystack port
+ // widths must match the needle port width range
+ //
+ // 3. All edges from the needle must match the haystack:
+ // a) if the needle edge is extern:
+ // - the haystack edge must have at least as many components as the needle edge
+ // b) if the needle edge is not extern:
+ // - the haystack edge must have the same number of components as the needle edge
+ // - the haystack edge must not be extern
+
+ const Graph::Node &nn = needle.nodes[needleNodeIdx];
+ const Graph::Node &hn = haystack.nodes[haystackNodeIdx];
+
+ assert(nn.typeId == hn.typeId || (compatibleTypes.count(nn.typeId) > 0 && compatibleTypes.at(nn.typeId).count(hn.typeId) > 0));
+
+ if (nn.ports.size() != hn.ports.size())
+ return false;
+
+ for (int i = 0; i < int(nn.ports.size()); i++)
+ {
+ if (hn.portMap.count(nn.ports[i].portId) == 0)
+ return false;
+
+ const Graph::Port &np = nn.ports[i];
+ const Graph::Port &hp = hn.ports[hn.portMap.at(nn.ports[i].portId)];
+
+ if (int(hp.bits.size()) < np.minWidth || hp.bits.size() > np.bits.size())
+ return false;
+
+ for (int j = 0; j < int(hp.bits.size()); j++)
+ {
+ const Graph::Edge &ne = needle.edges[np.bits[j].edgeIdx];
+ const Graph::Edge &he = haystack.edges[hp.bits[j].edgeIdx];
+
+ if (ne.constValue || he.constValue) {
+ if (ne.constValue != he.constValue)
+ if (compatibleConstants.count(ne.constValue) == 0 || compatibleConstants.at(ne.constValue).count(he.constValue) == 0)
+ return false;
+ continue;
+ }
+
+ if (ne.isExtern || needle.allExtern) {
+ if (he.portBits.size() < ne.portBits.size())
+ return false;
+ } else {
+ if (he.portBits.size() != ne.portBits.size())
+ return false;
+ if (he.isExtern || haystack.allExtern)
+ return false;
+ }
+ }
+ }
+
+ return true;
+ }
+
+ void generateEnumerationMatrix(std::vector<std::set<int>> &enumerationMatrix, const GraphData &needle, const GraphData &haystack, const std::map<std::string, std::set<std::string>> &initialMappings) const
+ {
+ std::map<std::string, std::set<int>> haystackNodesByTypeId;
+ for (int i = 0; i < int(haystack.graph.nodes.size()); i++)
+ haystackNodesByTypeId[haystack.graph.nodes[i].typeId].insert(i);
+
+ enumerationMatrix.clear();
+ enumerationMatrix.resize(needle.graph.nodes.size());
+ for (int i = 0; i < int(needle.graph.nodes.size()); i++)
+ {
+ const Graph::Node &nn = needle.graph.nodes[i];
+
+ for (int j : haystackNodesByTypeId[nn.typeId]) {
+ const Graph::Node &hn = haystack.graph.nodes[j];
+ if (initialMappings.count(nn.nodeId) > 0 && initialMappings.at(nn.nodeId).count(hn.nodeId) == 0)
+ continue;
+ if (!matchNodes(needle.graph, i, haystack.graph, j))
+ continue;
+ if (userSolver->userCompareNodes(needle.graphId, nn.nodeId, nn.userData, haystack.graphId, hn.nodeId, hn.userData))
+ enumerationMatrix[i].insert(j);
+ }
+
+ if (compatibleTypes.count(nn.typeId) > 0)
+ for (const std::string &compatibleTypeId : compatibleTypes.at(nn.typeId))
+ for (int j : haystackNodesByTypeId[compatibleTypeId]) {
+ const Graph::Node &hn = haystack.graph.nodes[j];
+ if (initialMappings.count(nn.nodeId) > 0 && initialMappings.at(nn.nodeId).count(hn.nodeId) == 0)
+ continue;
+ if (!matchNodes(needle.graph, i, haystack.graph, j))
+ continue;
+ if (userSolver->userCompareNodes(needle.graphId, nn.nodeId, nn.userData, haystack.graphId, hn.nodeId, hn.userData))
+ enumerationMatrix[i].insert(j);
+ }
+ }
+ }
+
+ bool checkEnumerationMatrix(std::vector<std::set<int>> &enumerationMatrix, int i, int j, const GraphData &needle, const GraphData &haystack)
+ {
+ for (const auto &it_needle : needle.adjMatrix.at(i))
+ {
+ int needleNeighbour = it_needle.first;
+ int needleEdgeType = it_needle.second;
+
+ for (int haystackNeighbour : enumerationMatrix[needleNeighbour])
+ if (haystack.adjMatrix.at(j).count(haystackNeighbour) > 0) {
+ int haystackEdgeType = haystack.adjMatrix.at(j).at(haystackNeighbour);
+ if (diCache.compare(needleEdgeType, haystackEdgeType, swapPorts, swapPermutations)) {
+ const Graph::Node &needleFromNode = needle.graph.nodes[i];
+ const Graph::Node &needleToNode = needle.graph.nodes[needleNeighbour];
+ const Graph::Node &haystackFromNode = haystack.graph.nodes[j];
+ const Graph::Node &haystackToNode = haystack.graph.nodes[haystackNeighbour];
+ if (userSolver->userCompareEdge(needle.graphId, needleFromNode.nodeId, needleFromNode.userData, needleToNode.nodeId, needleToNode.userData,
+ haystack.graphId, haystackFromNode.nodeId, haystackFromNode.userData, haystackToNode.nodeId, haystackToNode.userData))
+ goto found_match;
+ }
+ }
+
+ return false;
+ found_match:;
+ }
+
+ return true;
+ }
+
+ bool pruneEnumerationMatrix(std::vector<std::set<int>> &enumerationMatrix, const GraphData &needle, const GraphData &haystack, int &nextRow)
+ {
+ bool didSomething = true;
+ while (didSomething)
+ {
+ nextRow = -1;
+ didSomething = false;
+ for (int i = 0; i < int(enumerationMatrix.size()); i++) {
+ std::set<int> newRow;
+ for (int j : enumerationMatrix[i]) {
+ if (checkEnumerationMatrix(enumerationMatrix, i, j, needle, haystack))
+ newRow.insert(j);
+ else
+ didSomething = true;
+ }
+ if (newRow.size() == 0)
+ return false;
+ if (newRow.size() >= 2 && (nextRow < 0 || needle.adjMatrix.at(nextRow).size() < needle.adjMatrix.at(i).size()))
+ nextRow = i;
+ enumerationMatrix[i].swap(newRow);
+ }
+ }
+ return true;
+ }
+
+ void printEnumerationMatrix(const std::vector<std::set<int>> &enumerationMatrix, int maxHaystackNodeIdx = -1) const
+ {
+ if (maxHaystackNodeIdx < 0) {
+ for (const auto &it : enumerationMatrix)
+ for (int idx : it)
+ maxHaystackNodeIdx = std::max(maxHaystackNodeIdx, idx);
+ }
+
+ printf(" ");
+ for (int j = 0; j < maxHaystackNodeIdx; j += 5)
+ printf("%-6d", j);
+ printf("\n");
+
+ for (int i = 0; i < int(enumerationMatrix.size()); i++)
+ {
+ printf("%5d:", i);
+ for (int j = 0; j < maxHaystackNodeIdx; j++) {
+ if (j % 5 == 0)
+ printf(" ");
+ printf("%c", enumerationMatrix[i].count(j) > 0 ? '*' : '.');
+ }
+ printf("\n");
+ }
+ }
+
+ bool checkPortmapCandidate(const std::vector<std::set<int>> &enumerationMatrix, const GraphData &needle, const GraphData &haystack, int idx, const std::map<std::string, std::string> &currentCandidate)
+ {
+ assert(enumerationMatrix[idx].size() == 1);
+ int idxHaystack = *enumerationMatrix[idx].begin();
+
+ for (const auto &it_needle : needle.adjMatrix.at(idx))
+ {
+ int needleNeighbour = it_needle.first;
+ int needleEdgeType = it_needle.second;
+
+ assert(enumerationMatrix[needleNeighbour].size() == 1);
+ int haystackNeighbour = *enumerationMatrix[needleNeighbour].begin();
+
+ assert(haystack.adjMatrix.at(idxHaystack).count(haystackNeighbour) > 0);
+ int haystackEdgeType = haystack.adjMatrix.at(idxHaystack).at(haystackNeighbour);
+ if (!diCache.compare(needleEdgeType, haystackEdgeType, currentCandidate, swapPorts, swapPermutations))
+ return false;
+ }
+ return true;
+ }
+
+ void generatePortmapCandidates(std::set<std::map<std::string, std::string>> &portmapCandidates, const std::vector<std::set<int>> &enumerationMatrix,
+ const GraphData &needle, const GraphData &haystack, int idx)
+ {
+ std::map<std::string, std::string> currentCandidate;
+
+ for (const auto &port : needle.graph.nodes[idx].ports)
+ currentCandidate[port.portId] = port.portId;
+
+ if (swapPorts.count(needle.graph.nodes[idx].typeId) == 0)
+ {
+ if (checkPortmapCandidate(enumerationMatrix, needle, haystack, idx, currentCandidate))
+ portmapCandidates.insert(currentCandidate);
+
+ if (swapPermutations.count(needle.graph.nodes[idx].typeId) > 0)
+ for (const auto &permutation : swapPermutations.at(needle.graph.nodes[idx].typeId)) {
+ std::map<std::string, std::string> currentSubCandidate = currentCandidate;
+ applyPermutation(currentSubCandidate, permutation);
+ if (checkPortmapCandidate(enumerationMatrix, needle, haystack, idx, currentSubCandidate))
+ portmapCandidates.insert(currentSubCandidate);
+ }
+ }
+ else
+ {
+ std::vector<std::vector<std::string>> thisSwapPorts;
+ for (const auto &ports : swapPorts.at(needle.graph.nodes[idx].typeId)) {
+ std::vector<std::string> portsVector;
+ for (const auto &port : ports)
+ portsVector.push_back(port);
+ thisSwapPorts.push_back(portsVector);
+ }
+
+ int thisPermutations = numberOfPermutationsArray(thisSwapPorts);
+ for (int i = 0; i < thisPermutations; i++)
+ {
+ permutateVectorToMapArray(currentCandidate, thisSwapPorts, i);
+
+ if (checkPortmapCandidate(enumerationMatrix, needle, haystack, idx, currentCandidate))
+ portmapCandidates.insert(currentCandidate);
+
+ if (swapPermutations.count(needle.graph.nodes[idx].typeId) > 0)
+ for (const auto &permutation : swapPermutations.at(needle.graph.nodes[idx].typeId)) {
+ std::map<std::string, std::string> currentSubCandidate = currentCandidate;
+ applyPermutation(currentSubCandidate, permutation);
+ if (checkPortmapCandidate(enumerationMatrix, needle, haystack, idx, currentSubCandidate))
+ portmapCandidates.insert(currentSubCandidate);
+ }
+ }
+ }
+ }
+
+ bool prunePortmapCandidates(std::vector<std::set<std::map<std::string, std::string>>> &portmapCandidates, std::vector<std::set<int>> enumerationMatrix, const GraphData &needle, const GraphData &haystack)
+ {
+ bool didSomething = false;
+
+ // strategy #1: prune impossible port mappings
+
+ for (int i = 0; i < int(needle.graph.nodes.size()); i++)
+ {
+ assert(enumerationMatrix[i].size() == 1);
+ int j = *enumerationMatrix[i].begin();
+
+ std::set<std::map<std::string, std::string>> thisCandidates;
+ portmapCandidates[i].swap(thisCandidates);
+
+ for (const auto &testCandidate : thisCandidates)
+ {
+ for (const auto &it_needle : needle.adjMatrix.at(i))
+ {
+ int needleNeighbour = it_needle.first;
+ int needleEdgeType = it_needle.second;
+
+ assert(enumerationMatrix[needleNeighbour].size() == 1);
+ int haystackNeighbour = *enumerationMatrix[needleNeighbour].begin();
+
+ assert(haystack.adjMatrix.at(j).count(haystackNeighbour) > 0);
+ int haystackEdgeType = haystack.adjMatrix.at(j).at(haystackNeighbour);
+
+ for (const auto &otherCandidate : portmapCandidates[needleNeighbour]) {
+ if (diCache.compare(needleEdgeType, haystackEdgeType, testCandidate, otherCandidate))
+ goto found_match;
+ }
+
+ didSomething = true;
+ goto purgeCandidate;
+ found_match:;
+ }
+
+ portmapCandidates[i].insert(testCandidate);
+ purgeCandidate:;
+ }
+
+ if (portmapCandidates[i].size() == 0)
+ return false;
+ }
+
+ if (didSomething)
+ return true;
+
+ // strategy #2: prune a single random port mapping
+
+ for (int i = 0; i < int(needle.graph.nodes.size()); i++)
+ if (portmapCandidates[i].size() > 1) {
+ // remove last mapping. this keeps ports unswapped in don't-care situations
+ portmapCandidates[i].erase(--portmapCandidates[i].end());
+ return true;
+ }
+
+ return false;
+ }
+
+ void ullmannRecursion(std::vector<Solver::Result> &results, std::vector<std::set<int>> &enumerationMatrix, int iter, const GraphData &needle, GraphData &haystack, bool allowOverlap, int limitResults)
+ {
+ int i = -1;
+ if (!pruneEnumerationMatrix(enumerationMatrix, needle, haystack, i))
+ return;
+
+ if (i < 0)
+ {
+ Solver::Result result;
+ result.needleGraphId = needle.graphId;
+ result.haystackGraphId = haystack.graphId;
+
+ std::vector<std::set<std::map<std::string, std::string>>> portmapCandidates;
+ portmapCandidates.resize(enumerationMatrix.size());
+
+ for (int j = 0; j < int(enumerationMatrix.size()); j++) {
+ Solver::ResultNodeMapping mapping;
+ mapping.needleNodeId = needle.graph.nodes[j].nodeId;
+ mapping.needleUserData = needle.graph.nodes[j].userData;
+ mapping.haystackNodeId = haystack.graph.nodes[*enumerationMatrix[j].begin()].nodeId;
+ mapping.haystackUserData = haystack.graph.nodes[*enumerationMatrix[j].begin()].userData;
+ generatePortmapCandidates(portmapCandidates[j], enumerationMatrix, needle, haystack, j);
+ result.mappings[needle.graph.nodes[j].nodeId] = mapping;
+ }
+
+ while (prunePortmapCandidates(portmapCandidates, enumerationMatrix, needle, haystack)) { }
+
+ for (int j = 0; j < int(enumerationMatrix.size()); j++) {
+ if (portmapCandidates[j].size() == 0) {
+ if (verbose) {
+ printf("\nSolution (rejected by portmapper):\n");
+ printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size());
+ }
+ return;
+ }
+ result.mappings[needle.graph.nodes[j].nodeId].portMapping = *portmapCandidates[j].begin();
+ }
+
+ if (!userSolver->userCheckSolution(result)) {
+ if (verbose) {
+ printf("\nSolution (rejected by userCheckSolution):\n");
+ printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size());
+ }
+ return;
+ }
+
+ for (int j = 0; j < int(enumerationMatrix.size()); j++)
+ haystack.usedNodes[*enumerationMatrix[j].begin()] = true;
+
+ if (verbose) {
+ printf("\nSolution:\n");
+ printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size());
+ }
+
+ results.push_back(result);
+ return;
+ }
+
+ if (verbose) {
+ printf("\n");
+ printf("Enumeration Matrix at recursion level %d (%d):\n", iter, i);
+ printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size());
+ }
+
+ std::set<int> activeRow;
+ enumerationMatrix[i].swap(activeRow);
+
+ for (int j : activeRow)
+ {
+ // found enough?
+ if (limitResults >= 0 && int(results.size()) >= limitResults)
+ return;
+
+ // already used by other solution -> try next
+ if (!allowOverlap && haystack.usedNodes[j])
+ continue;
+
+ // create enumeration matrix for child in recursion tree
+ std::vector<std::set<int>> nextEnumerationMatrix = enumerationMatrix;
+ for (int k = 0; k < int(nextEnumerationMatrix.size()); k++)
+ nextEnumerationMatrix[k].erase(j);
+ nextEnumerationMatrix[i].insert(j);
+
+ // recursion
+ ullmannRecursion(results, nextEnumerationMatrix, iter+1, needle, haystack, allowOverlap, limitResults);
+
+ // we just have found something -> unroll to top recursion level
+ if (!allowOverlap && haystack.usedNodes[j] && iter > 0)
+ return;
+ }
+ }
+
+ // interface to the public Solver class
+
+protected:
+ SolverWorker(Solver *userSolver) : userSolver(userSolver), verbose(false)
+ {
+ }
+
+ void setVerbose()
+ {
+ verbose = true;
+ }
+
+ void addGraph(std::string graphId, const Graph &graph)
+ {
+ assert(graphData.count(graphId) == 0);
+
+ GraphData &gd = graphData[graphId];
+ gd.graphId = graphId;
+ gd.graph = graph;
+ diCache.add(gd.graph, gd.adjMatrix, graphId, userSolver);
+ }
+
+ void addCompatibleTypes(std::string needleTypeId, std::string haystackTypeId)
+ {
+ compatibleTypes[needleTypeId].insert(haystackTypeId);
+ }
+
+ void addCompatibleConstants(int needleConstant, int haystackConstant)
+ {
+ compatibleConstants[needleConstant].insert(haystackConstant);
+ }
+
+ void addSwappablePorts(std::string needleTypeId, const std::set<std::string> &ports)
+ {
+ swapPorts[needleTypeId].insert(ports);
+ diCache.compareCache.clear();
+ }
+
+ void addSwappablePortsPermutation(std::string needleTypeId, const std::map<std::string, std::string> &portMapping)
+ {
+ swapPermutations[needleTypeId].insert(portMapping);
+ diCache.compareCache.clear();
+ }
+
+ void solve(std::vector<Solver::Result> &results, std::string needleGraphId, std::string haystackGraphId,
+ const std::map<std::string, std::set<std::string>> &initialMappings, bool allowOverlap, int maxSolutions)
+ {
+ assert(graphData.count(needleGraphId) > 0);
+ assert(graphData.count(haystackGraphId) > 0);
+
+ const GraphData &needle = graphData[needleGraphId];
+ GraphData &haystack = graphData[haystackGraphId];
+
+ std::vector<std::set<int>> enumerationMatrix;
+ generateEnumerationMatrix(enumerationMatrix, needle, haystack, initialMappings);
+
+ if (verbose)
+ {
+ printf("\n");
+ printf("Needle Adjecency Matrix:\n");
+ printAdjMatrix(needle.adjMatrix);
+
+ printf("\n");
+ printf("Haystack Adjecency Matrix:\n");
+ printAdjMatrix(haystack.adjMatrix);
+
+ printf("\n");
+ printf("Edge Types:\n");
+ diCache.printEdgeTypes();
+
+ printf("\n");
+ printf("Enumeration Matrix:\n");
+ printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size());
+ }
+
+ haystack.usedNodes.resize(haystack.graph.nodes.size());
+ ullmannRecursion(results, enumerationMatrix, 0, needle, haystack, allowOverlap, maxSolutions > 0 ? results.size() + maxSolutions : -1);
+ }
+
+ void clearOverlapHistory()
+ {
+ for (auto &it : graphData)
+ it.second.usedNodes.clear();
+ }
+
+ void clearConfig()
+ {
+ compatibleTypes.clear();
+ compatibleConstants.clear();
+ swapPorts.clear();
+ swapPermutations.clear();
+ diCache.compareCache.clear();
+ }
+
+ friend class Solver;
+};
+
+bool Solver::userCompareNodes(const std::string&, const std::string&, void*, const std::string&, const std::string&, void*)
+{
+ return true;
+}
+
+std::string Solver::userAnnotateEdge(const std::string&, const std::string&, void*, const std::string&, void*)
+{
+ return std::string();
+}
+
+bool Solver::userCompareEdge(const std::string&, const std::string&, void*, const std::string&, void*, const std::string&, const std::string&, void*, const std::string&, void*)
+{
+ return true;
+}
+
+bool Solver::userCheckSolution(const Result&)
+{
+ return true;
+}
+
+SubCircuit::Solver::Solver()
+{
+ worker = new SolverWorker(this);
+}
+
+SubCircuit::Solver::~Solver()
+{
+ delete worker;
+}
+
+void SubCircuit::Solver::setVerbose()
+{
+ worker->setVerbose();
+}
+
+void SubCircuit::Solver::addGraph(std::string graphId, const Graph &graph)
+{
+ worker->addGraph(graphId, graph);
+}
+
+void SubCircuit::Solver::addCompatibleTypes(std::string needleTypeId, std::string haystackTypeId)
+{
+ worker->addCompatibleTypes(needleTypeId, haystackTypeId);
+}
+
+void SubCircuit::Solver::addCompatibleConstants(int needleConstant, int haystackConstant)
+{
+ worker->addCompatibleConstants(needleConstant, haystackConstant);
+}
+
+void SubCircuit::Solver::addSwappablePorts(std::string needleTypeId, std::string portId1, std::string portId2, std::string portId3, std::string portId4)
+{
+ std::set<std::string> ports;
+ ports.insert(portId1);
+ ports.insert(portId2);
+ ports.insert(portId3);
+ ports.insert(portId4);
+ ports.erase(std::string());
+ addSwappablePorts(needleTypeId, ports);
+}
+
+void SubCircuit::Solver::addSwappablePorts(std::string needleTypeId, std::set<std::string> ports)
+{
+ worker->addSwappablePorts(needleTypeId, ports);
+}
+
+void SubCircuit::Solver::addSwappablePortsPermutation(std::string needleTypeId, std::map<std::string, std::string> portMapping)
+{
+ worker->addSwappablePortsPermutation(needleTypeId, portMapping);
+}
+
+void SubCircuit::Solver::solve(std::vector<Result> &results, std::string needleGraphId, std::string haystackGraphId, bool allowOverlap, int maxSolutions)
+{
+ std::map<std::string, std::set<std::string>> emptyInitialMapping;
+ worker->solve(results, needleGraphId, haystackGraphId, emptyInitialMapping, allowOverlap, maxSolutions);
+}
+
+void SubCircuit::Solver::solve(std::vector<Result> &results, std::string needleGraphId, std::string haystackGraphId,
+ const std::map<std::string, std::set<std::string>> &initialMappings, bool allowOverlap, int maxSolutions)
+{
+ worker->solve(results, needleGraphId, haystackGraphId, initialMappings, allowOverlap, maxSolutions);
+}
+
+void SubCircuit::Solver::clearOverlapHistory()
+{
+ worker->clearOverlapHistory();
+}
+
+void SubCircuit::Solver::clearConfig()
+{
+ worker->clearConfig();
+}
+
diff --git a/libs/subcircuit/subcircuit.h b/libs/subcircuit/subcircuit.h
new file mode 100644
index 00000000..da536ba0
--- /dev/null
+++ b/libs/subcircuit/subcircuit.h
@@ -0,0 +1,139 @@
+/*
+ * SubCircuit -- An implementation of the Ullmann Subgraph Isomorphism
+ * algorithm for coarse grain logic networks
+ *
+ * Copyright (C) 2013 Clifford Wolf <clifford@clifford.at>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ */
+
+#ifndef SUBCIRCUIT_H
+#define SUBCIRCUIT_H
+
+#include <string>
+#include <vector>
+#include <set>
+#include <map>
+
+namespace SubCircuit
+{
+ class SolverWorker;
+
+ class Graph
+ {
+ protected:
+ struct BitRef {
+ int nodeIdx, portIdx, bitIdx;
+ BitRef(int nodeIdx = -1, int portIdx = -1, int bitIdx = -1) : nodeIdx(nodeIdx), portIdx(portIdx), bitIdx(bitIdx) { };
+ bool operator < (const BitRef &other) const;
+ };
+
+ struct Edge {
+ std::set<BitRef> portBits;
+ int constValue;
+ bool isExtern;
+ Edge() : constValue(0), isExtern(false) { };
+ };
+
+ struct PortBit {
+ int edgeIdx;
+ PortBit() : edgeIdx(-1) { };
+ };
+
+ struct Port {
+ std::string portId;
+ int minWidth;
+ std::vector<PortBit> bits;
+ Port() : minWidth(-1) { };
+ };
+
+ struct Node {
+ std::string nodeId, typeId;
+ std::map<std::string, int> portMap;
+ std::vector<Port> ports;
+ void *userData;
+ Node() : userData(NULL) { };
+ };
+
+ bool allExtern;
+ std::map<std::string, int> nodeMap;
+ std::vector<Node> nodes;
+ std::vector<Edge> edges;
+
+ public:
+ Graph() : allExtern(false) { };
+
+ void createNode(std::string nodeId, std::string typeId, void *userData = NULL);
+ void createPort(std::string nodeId, std::string portId, int width = 1, int minWidth = -1);
+ void createConnection(std::string fromNodeId, std::string fromPortId, int fromBit, std::string toNodeId, std::string toPortId, int toBit, int width = 1);
+ void createConnection(std::string fromNodeId, std::string fromPortId, std::string toNodeId, std::string toPortId);
+ void createConstant(std::string toNodeId, std::string toPortId, int toBit, int constValue);
+ void createConstant(std::string toNodeId, std::string toPortId, int constValue);
+ void markExtern(std::string nodeId, std::string portId, int bit = -1);
+ void markAllExtern();
+ void print();
+
+ friend class SolverWorker;
+ };
+
+ class Solver
+ {
+ public:
+ struct ResultNodeMapping {
+ std::string needleNodeId, haystackNodeId;
+ void *needleUserData, *haystackUserData;
+ std::map<std::string, std::string> portMapping;
+ };
+ struct Result {
+ std::string needleGraphId, haystackGraphId;
+ std::map<std::string, ResultNodeMapping> mappings;
+ };
+
+ private:
+ SolverWorker *worker;
+
+ protected:
+ virtual bool userCompareNodes(const std::string &needleGraphId, const std::string &needleNodeId, void *needleUserData,
+ const std::string &haystackGraphId, const std::string &haystackNodeId, void *haystackUserData);
+
+ virtual std::string userAnnotateEdge(const std::string &graphId, const std::string &fromNodeId, void *fromUserData, const std::string &toNodeId, void *toUserData);
+
+ virtual bool userCompareEdge(const std::string &needleGraphId, const std::string &needleFromNodeId, void *needleFromUserData, const std::string &needleToNodeId, void *needleToUserData,
+ const std::string &haystackGraphId, const std::string &haystackFromNodeId, void *haystackFromUserData, const std::string &haystackToNodeId, void *haystackToUserData);
+
+ virtual bool userCheckSolution(const Result &result);
+
+ friend class SolverWorker;
+
+ public:
+ Solver();
+ ~Solver();
+
+ void setVerbose();
+ void addGraph(std::string graphId, const Graph &graph);
+ void addCompatibleTypes(std::string needleTypeId, std::string haystackTypeId);
+ void addCompatibleConstants(int needleConstant, int haystackConstant);
+ void addSwappablePorts(std::string needleTypeId, std::string portId1, std::string portId2, std::string portId3 = std::string(), std::string portId4 = std::string());
+ void addSwappablePorts(std::string needleTypeId, std::set<std::string> ports);
+ void addSwappablePortsPermutation(std::string needleTypeId, std::map<std::string, std::string> portMapping);
+
+ void solve(std::vector<Result> &results, std::string needleGraphId, std::string haystackGraphId, bool allowOverlap = true, int maxSolutions = -1);
+ void solve(std::vector<Result> &results, std::string needleGraphId, std::string haystackGraphId,
+ const std::map<std::string, std::set<std::string>> &initialMapping, bool allowOverlap = true, int maxSolutions = -1);
+ void clearOverlapHistory();
+ void clearConfig();
+ };
+}
+
+#endif /* SUBCIRCUIT_H */
diff --git a/libs/subcircuit/test_large.spl b/libs/subcircuit/test_large.spl
new file mode 100644
index 00000000..74a47d94
--- /dev/null
+++ b/libs/subcircuit/test_large.spl
@@ -0,0 +1,221 @@
+#!/usr/bin/env splrun
+
+var idx = 0;
+var count_nand = 0;
+var count_nor = 0;
+
+function makeNAND(net, id)
+{
+ count_nand++;
+
+ net["${id}_VDD"] = "${id}_pa S";
+ net["${id}_VSS"] = "${id}_nb S";
+
+ net["${id}_A"] = "${id}_pa G";
+ net["${id}_B"] = "${id}_pb G";
+ net["${id}_Y"] = "${id}_pb D";
+
+ return <:>
+ : node ${id}_pa pmos S 1 D 1 G 1
+ : node ${id}_pb pmos S 1 D 1 G 1
+ : node ${id}_na nmos S 1 D 1 G 1
+ : node ${id}_nb nmos S 1 D 1 G 1
+ : connect ${id}_pa S ${id}_pb S
+ : connect ${id}_pa D ${id}_pb D
+ : connect ${id}_pa D ${id}_na D
+ : connect ${id}_na S ${id}_nb D
+ : connect ${id}_pa G ${id}_na G
+ : connect ${id}_pb G ${id}_nb G
+ </>;
+}
+
+function makeNOR(net, id)
+{
+ count_nor++;
+
+ net["${id}_VDD"] = "${id}_pa S";
+ net["${id}_VSS"] = "${id}_nb S";
+
+ net["${id}_A"] = "${id}_pa G";
+ net["${id}_B"] = "${id}_pb G";
+ net["${id}_Y"] = "${id}_pb D";
+
+ return <:>
+ : node ${id}_pa pmos S 1 D 1 G 1
+ : node ${id}_pb pmos S 1 D 1 G 1
+ : node ${id}_na nmos S 1 D 1 G 1
+ : node ${id}_nb nmos S 1 D 1 G 1
+ : connect ${id}_pa D ${id}_pb S
+ : connect ${id}_pb D ${id}_na D
+ : connect ${id}_pb D ${id}_nb D
+ : connect ${id}_na S ${id}_nb S
+ : connect ${id}_pa G ${id}_na G
+ : connect ${id}_pb G ${id}_nb G
+ </>;
+}
+
+function makeGraph(seed, gates, primaryInputs, primaryOutputs)
+{
+ srand(seed);
+
+ var code = "";
+ var net, vdd, vss, outputs;
+ var unusedOutpus;
+ for (var i = 0; i < gates; i++)
+ {
+ var id = fmt("G%d", idx++);
+ if (rand(2) == 0)
+ code ~= makeNAND(net, id);
+ else
+ code ~= makeNOR(net, id);
+
+ if (i == 0) {
+ vdd = net["${id}_VDD"];
+ vss = net["${id}_VSS"];
+ } else {
+ code ~= <:>
+ : connect $vdd ${net["${id}_VDD"]}
+ : connect $vss ${net["${id}_VSS"]}
+ </>;
+ }
+
+ var inIdx1 = rand((elementsof outputs) + 1);
+ if (inIdx1 < elementsof outputs) {
+ code ~= " connect ${outputs[inIdx1]} ${net["${id}_A"]}\n";
+ delete unusedOutpus[outputs[inIdx1]];
+ } else
+ push primaryInputs, net["${id}_A"];
+
+ var inIdx2 = rand((elementsof outputs) + 1);
+ if (inIdx2 < elementsof outputs) {
+ code ~= " connect ${outputs[inIdx2]} ${net["${id}_B"]}\n";
+ delete unusedOutpus[outputs[inIdx2]];
+ } else
+ push primaryInputs, net["${id}_B"];
+
+ unusedOutpus[net["${id}_Y"]] = 1;
+ push outputs, net["${id}_Y"];
+ }
+
+ foreach netDecl (unusedOutpus)
+ push primaryOutputs, netDecl;
+
+ return code;
+}
+
+function makeConnections(fromNets, toNets)
+{
+ var code = "";
+ foreach[] toNet (toNets) {
+ var fromNet = fromNets[rand(elementsof fromNets)];
+ code != " connect $fromNet $toNet\n";
+ }
+ return code;
+}
+
+var numNodes;
+
+write(<:>
+ : graph nand
+ <?spl var net = []; ?>
+ ${makeNAND(net, "nand")}
+ : extern ${net["nand_VDD"]}
+ : extern ${net["nand_VSS"]}
+ : extern ${net["nand_A"]}
+ : extern ${net["nand_B"]}
+ : extern ${net["nand_Y"]}
+ : endgraph
+ :
+ : graph nor
+ ${makeNOR(net, "nor")}
+ : extern ${net["nor_VDD"]}
+ : extern ${net["nor_VSS"]}
+ : extern ${net["nor_A"]}
+ : extern ${net["nor_B"]}
+ : extern ${net["nor_Y"]}
+ : endgraph
+ :
+ : graph needle_1
+ <?spl var ports; ?>
+ ${makeGraph(1, 100, ports, ports)}
+ <?spl numNodes["needle_1"] = idx*4; ?>
+ <spl:foreach var="[]net" list="ports">
+ : extern $net
+ </spl:foreach>
+ : endgraph
+ :
+ : graph needle_2
+ <?spl var ports; ?>
+ ${makeGraph(2, 200, ports, ports)}
+ <?spl numNodes["needle_2"] = idx*4; ?>
+ <spl:foreach var="[]net" list="ports">
+ : extern $net
+ </spl:foreach>
+ : endgraph
+ :
+ : graph needle_3
+ <?spl var ports; ?>
+ ${makeGraph(3, 300, ports, ports)}
+ <?spl numNodes["needle_3"] = idx*4; ?>
+ <spl:foreach var="[]net" list="ports">
+ : extern $net
+ </spl:foreach>
+ : endgraph
+ :
+ : graph haystack
+
+ <?spl count_nand=0; count_nor=0; ?>
+
+ <?spl var inPorts1, outPorts1; ?>
+ ${makeGraph(1, 100, inPorts1, outPorts1)}
+
+ <?spl var inPorts2, outPorts2; ?>
+ ${makeGraph(2, 200, inPorts2, outPorts2)}
+
+ <?spl var inPorts3, outPorts3; ?>
+ ${makeGraph(3, 300, inPorts3, outPorts3)}
+
+ <?spl var inPorts4, outPorts4; ?>
+ ${makeGraph(2, 200, inPorts4, outPorts4)}
+
+ <?spl var inPorts5, outPorts5; ?>
+ ${makeGraph(1, 100, inPorts5, outPorts5)}
+ <?spl numNodes["haystack"] = idx*4; ?>
+
+ ${makeConnections(outPorts1, inPorts2)}
+ ${makeConnections(outPorts2, inPorts3)}
+ ${makeConnections(outPorts3, inPorts4)}
+ ${makeConnections(outPorts4, inPorts5)}
+
+ : endgraph
+ :
+ : solve nand haystack false
+ : expect $count_nand
+ : clearoverlap
+ :
+ : solve nor haystack false
+ : expect $count_nor
+ : clearoverlap
+ :
+ : solve needle_1 haystack false
+ : expect 2
+ :
+ : solve needle_2 haystack false
+ : expect 2
+ :
+ : solve needle_3 haystack false
+ : expect 1
+</>);
+
+numNodes["haystack"] -= numNodes["needle_3"];
+numNodes["needle_3"] -= numNodes["needle_2"];
+numNodes["needle_2"] -= numNodes["needle_1"];
+
+write(<:>
+ :
+ : # Needle_1: ${numNodes["needle_1"]} transistors
+ : # Needle_2: ${numNodes["needle_2"]} transistors
+ : # Needle_3: ${numNodes["needle_3"]} transistors
+ : # Haystack: ${numNodes["haystack"]} transistors
+</>);
+
diff --git a/libs/subcircuit/test_macc22.txt b/libs/subcircuit/test_macc22.txt
new file mode 100644
index 00000000..71938c1c
--- /dev/null
+++ b/libs/subcircuit/test_macc22.txt
@@ -0,0 +1,48 @@
+
+# verbose
+
+graph macc22
+ node mul_1 mul A 32 B 32 Y 32
+ node mul_2 mul A 32 B 32 Y 32
+ node add_1 add A 32 B 32 Y 32
+ connect mul_1 Y add_1 A
+ connect mul_2 Y add_1 B
+ extern mul_1 A B
+ extern mul_2 A B
+ extern add_1 Y
+endgraph
+
+graph macc4x2
+ node mul_1 mul A 32 B 32 Y 32
+ node mul_2 mul A 32 B 32 Y 32
+ node mul_3 mul A 32 B 32 Y 32
+ node mul_4 mul A 32 B 32 Y 32
+ node add_1 add A 32 B 32 Y 32
+ node add_2 add A 32 B 32 Y 32
+ node add_3 add A 32 B 32 Y 32
+ connect mul_1 Y add_1 A
+ connect mul_2 Y add_1 B
+ connect mul_3 Y add_2 A
+ connect mul_4 Y add_2 B
+ connect add_1 Y add_3 A
+ connect add_2 Y add_3 B
+ extern mul_1 A B
+ extern mul_2 A B
+ extern mul_3 A B
+ extern mul_4 A B
+ extern add_3 Y
+endgraph
+
+solve macc22 macc4x2
+expect 2
+
+swapgroup mul A B
+
+solve macc22 macc4x2
+expect 2
+
+swapperm add A B : B A
+
+solve macc22 macc4x2
+expect 4
+
diff --git a/libs/subcircuit/test_perm.pl b/libs/subcircuit/test_perm.pl
new file mode 100644
index 00000000..b4e05e35
--- /dev/null
+++ b/libs/subcircuit/test_perm.pl
@@ -0,0 +1,108 @@
+#!/usr/bin/perl -w
+
+use strict;
+
+# let "macc" implement a function like Y = (A*B) + (C*D)
+#
+# the following permutations of the input pins exist:
+#
+# g01 | A B C D | match
+# g02 | A B D C | match
+# g03 | A C B D | not
+# g04 | A C D B | not
+# g05 | A D B C | not
+# g06 | A D C B | not
+# g07 | B A C D | match
+# g08 | B A D C | match
+# g09 | B C A D | not
+# g10 | B C D A | not
+# g11 | B D A C | not
+# g12 | B D C A | not
+# g13 | C A B D | not
+# g14 | C A D B | not
+# g15 | C B A D | not
+# g16 | C B D A | not
+# g17 | C D A B | match
+# g18 | C D B A | match
+# g19 | D A B C | not
+# g20 | D A C B | not
+# g21 | D B A C | not
+# g22 | D B C A | not
+# g23 | D C A B | match
+# g24 | D C B A | match
+
+my @matches = qw/g01 g02 g07 g08 g17 g18 g23 g24/;
+my @non_matches = qw/g03 g04 g05 g06 g09 g10 g11 g12 g13 g14 g15 g16 g19 g20 g21 g22/;
+
+print "\n";
+
+for my $i (0..3) {
+for my $j (0..2) {
+for my $k (0..1) {
+ my @t = qw/A B C D/;
+ print "# ";
+ print splice(@t,$i,1),splice(@t,$j,1),splice(@t,$k,1),$t[0];
+ print "\n";
+}}}
+
+print "\n";
+
+my $iter = 1;
+for my $i (0..3) {
+for my $j (0..2) {
+for my $k (0..1) {
+ my @t = qw/A B C D/;
+ printf "graph g%02d\n", $iter++;
+ printf " node input input A 32 1 B 32 1 C 32 1 D 32 1\n";
+ printf " node macc macc A 32 1 B 32 1 C 32 1 D 32 1\n";
+ printf " connect input A macc %s\n", splice(@t,$i,1);
+ printf " connect input B macc %s\n", splice(@t,$j,1);
+ printf " connect input C macc %s\n", splice(@t,$k,1);
+ printf " connect input D macc %s\n", splice(@t,0,1);
+ printf "endgraph\n";
+ printf "\n";
+}}}
+
+$iter = 1;
+printf "graph gXL\n";
+for my $i (0..3) {
+for my $j (0..2) {
+for my $k (0..1) {
+ my $id = sprintf "_%02d", $iter++;
+ my @t = qw/A B C D/;
+ printf " node input$id input A 16 B 16 C 16 D 16\n";
+ printf " node macc$id macc A 16 B 16 C 16 D 16\n";
+ printf " connect input$id A macc$id %s\n", splice(@t,$i,1);
+ printf " connect input$id B macc$id %s\n", splice(@t,$j,1);
+ printf " connect input$id C macc$id %s\n", splice(@t,$k,1);
+ printf " connect input$id D macc$id %s\n", splice(@t,0,1);
+}}}
+printf "endgraph\n";
+printf "\n";
+
+
+printf "swapgroup macc A B\n";
+printf "swapgroup macc C D\n";
+printf "swapperm macc A B C D : C D A B\n";
+
+for my $i (@matches) {
+for my $j (@non_matches) {
+ printf "solve %s %s\n", $i, $j;
+}}
+printf "expect 0\n\n";
+
+for my $i (@matches) {
+for my $j (@matches) {
+ printf "solve %s %s\n", $i, $j;
+}}
+printf "expect %d\n\n", @matches*@matches;
+
+printf "solve g01 gXL false\n";
+printf "expect 8\n";
+
+printf "solve g03 gXL false\n";
+printf "expect 8\n";
+
+printf "solve g04 gXL false\n";
+printf "expect 8\n";
+
diff --git a/libs/subcircuit/test_shorts.spl b/libs/subcircuit/test_shorts.spl
new file mode 100644
index 00000000..f1cb4cfd
--- /dev/null
+++ b/libs/subcircuit/test_shorts.spl
@@ -0,0 +1,121 @@
+#!/usr/bin/env splrun
+//
+// Test procedure for matching Gates with shorted inputs, as suggested in
+// "SubCircuit Extraction with SubGraph Isomorphism. Zong Ling, Ph. D. IBM
+// Almaden Research Center -- EDA Shape Processing zling@us.ibm.com.":
+//
+// Four NAND gates and a NOR gate. One NAND gate (G1) has no shorted inputs,
+// one (G2) has an input shorted to VSS, one (G3) has an input shorted to VDD,
+// and one (G4) has both inputs shorted together. Th last gate (G5) is a NOR
+// gate.
+
+var net;
+
+function makeNAND(id)
+{
+ net["${id}_VDD"] = "${id}_pa S";
+ net["${id}_VSS"] = "${id}_nb S";
+
+ net["${id}_A"] = "${id}_pa G";
+ net["${id}_B"] = "${id}_pb G";
+ net["${id}_Y"] = "${id}_pb D";
+
+ return <:>
+ : node ${id}_pa pmos S 1 D 1 G 1
+ : node ${id}_pb pmos S 1 D 1 G 1
+ : node ${id}_na nmos S 1 D 1 G 1
+ : node ${id}_nb nmos S 1 D 1 G 1
+ : connect ${id}_pa S ${id}_pb S
+ : connect ${id}_pa D ${id}_pb D
+ : connect ${id}_pa D ${id}_na D
+ : connect ${id}_na S ${id}_nb D
+ : connect ${id}_pa G ${id}_na G
+ : connect ${id}_pb G ${id}_nb G
+ </>;
+}
+
+function makeNOR(id)
+{
+ net["${id}_VDD"] = "${id}_pa S";
+ net["${id}_VSS"] = "${id}_nb S";
+
+ net["${id}_A"] = "${id}_pa G";
+ net["${id}_B"] = "${id}_pb G";
+ net["${id}_Y"] = "${id}_pb D";
+
+ return <:>
+ : node ${id}_pa pmos S 1 D 1 G 1
+ : node ${id}_pb pmos S 1 D 1 G 1
+ : node ${id}_na nmos S 1 D 1 G 1
+ : node ${id}_nb nmos S 1 D 1 G 1
+ : connect ${id}_pa D ${id}_pb S
+ : connect ${id}_pb D ${id}_na D
+ : connect ${id}_pb D ${id}_nb D
+ : connect ${id}_na S ${id}_nb S
+ : connect ${id}_pa G ${id}_na G
+ : connect ${id}_pb G ${id}_nb G
+ </>;
+}
+
+write(<:>
+ : graph nand
+ : ${ makeNAND("G0") }
+ : extern ${net["G0_VDD"]}
+ : extern ${net["G0_VSS"]}
+ : extern ${net["G0_A"]}
+ : extern ${net["G0_B"]}
+ : extern ${net["G0_Y"]}
+ : endgraph
+ :
+ : graph nor
+ : ${ makeNOR("G0") }
+ : extern ${net["G0_VDD"]}
+ : extern ${net["G0_VSS"]}
+ : extern ${net["G0_A"]}
+ : extern ${net["G0_B"]}
+ : extern ${net["G0_Y"]}
+ : endgraph
+ :
+ : graph haystack
+ : ${ makeNAND("G1") }
+ : ${ makeNAND("G2") }
+ : ${ makeNAND("G3") }
+ : ${ makeNAND("G4") }
+ ${ makeNOR("G5") }
+ :
+ : node vdd vsupply V 1
+ : connect vdd V ${net["G1_VDD"]}
+ : connect vdd V ${net["G2_VDD"]}
+ : connect vdd V ${net["G3_VDD"]}
+ : connect vdd V ${net["G4_VDD"]}
+ : connect vdd V ${net["G5_VDD"]}
+ :
+ : node vss vsupply V 1
+ : connect vss V ${net["G1_VSS"]}
+ : connect vss V ${net["G2_VSS"]}
+ : connect vss V ${net["G3_VSS"]}
+ : connect vss V ${net["G4_VSS"]}
+ : connect vss V ${net["G5_VSS"]}
+ :
+ : connect ${net["G2_A"]} ${net["G1_A"]}
+ : connect ${net["G2_B"]} ${net["G2_VSS"]}
+ :
+ : connect ${net["G3_A"]} ${net["G1_VDD"]}
+ : connect ${net["G3_B"]} ${net["G2_Y"]}
+ :
+ : connect ${net["G4_A"]} ${net["G1_Y"]}
+ : connect ${net["G4_B"]} ${net["G1_Y"]}
+ :
+ : connect ${net["G5_A"]} ${net["G3_Y"]}
+ : connect ${net["G5_B"]} ${net["G4_Y"]}
+ : endgraph
+ :
+ : solve nand haystack false
+ : clearoverlap
+ : expect 4
+ :
+ : solve nor haystack false
+ : clearoverlap
+ : expect 1
+</>);
+