Moved stand-alone libs to libs/ directory and added libs/subcircuit

1 files changed, 440 insertions, 0 deletions

diff --git a/libs/subcircuit/README b/libs/subcircuit/README
new file mode 100644
index 000000000..5c8a8a9e7
--- /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().
+