maze.java

The ElectricTM VLSI Design System is an open-source Electronic Design Automation (EDA) system that c

/* -*- tab-width: 4 -*-
 *
 * Electric(tm) VLSI Design System
 *
 * File: Maze.java
 * Routing tool: Maze routing
 * Original C Code written by Glen M. Lawson
 * Translated to Java by Steven M. Rubin, Sun Microsystems.
 *
 * Copyright (c) 2004 Sun Microsystems and Static Free Software
 *
 * Electric(tm) is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Electric(tm) is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Electric(tm); see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, Mass 02111-1307, USA.
 */
package com.sun.electric.tool.routing;

import com.sun.electric.database.geometry.GenMath;
import com.sun.electric.database.geometry.Poly;
import com.sun.electric.database.geometry.DBMath;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.hierarchy.HierarchyEnumerator;
import com.sun.electric.database.hierarchy.Nodable;
import com.sun.electric.database.network.Netlist;
import com.sun.electric.database.network.Network;
import com.sun.electric.database.prototype.NodeProto;
import com.sun.electric.database.prototype.PortProto;
import com.sun.electric.database.topology.ArcInst;
import com.sun.electric.database.topology.Connection;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.database.topology.PortInst;
import com.sun.electric.database.topology.RTBounds;
import com.sun.electric.database.variable.EditWindow_;
import com.sun.electric.database.variable.UserInterface;
import com.sun.electric.database.variable.VarContext;
import com.sun.electric.technology.ArcProto;
import com.sun.electric.technology.DRCTemplate;
import com.sun.electric.technology.Layer;
import com.sun.electric.technology.PrimitiveNode;
import com.sun.electric.technology.PrimitivePort;
import com.sun.electric.technology.Technology;
import com.sun.electric.technology.technologies.Generic;
import com.sun.electric.tool.Job;
import com.sun.electric.tool.JobException;
import com.sun.electric.tool.drc.DRC;
import com.sun.electric.tool.user.User;

import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/**
 * Class to do maze routing (single wire at a time).
 */
public class Maze
{
	/** bit width of long word */		private static final int SRMAXLAYERS = 64;
	/** maximum size of maze */			private static final int MAXGRIDSIZE = 1000;
	/** max grid points to "excavate" for initial grid access from a port */	private static final int BLOCKAGELIMIT =  10;

	/** draw only on vertical layer */	private static final int HORILAYER = 0;
	/** draw all layers */				private static final int VERTLAYER = 1;
	/** draw all layers */				private static final int ALLLAYERS = 2;

	// common bit masks
	/** grid set (permanent) */			private static final int SR_GSET   = 0x80;
	/** is a wavefront point */			private static final int SR_GWAVE  = 0x20;
	/** is a port */					private static final int SR_GPORT  = 0x10;

	// for maze cells
	/** mask 4 bits */					private static final int SR_GMASK  = 0x0F;
	/** maximum mark value */			private static final int SR_GMAX   = 15;
	/** start value */					private static final int SR_GSTART = 1;

	// miscellaneous defines, return codes from expandWavefront
	private static final int SRSUCCESS  = 0;
	private static final int SRERROR    = 1;
	private static final int SRROUTED   = 2;
	private static final int SRBLOCKED  = 3;
	private static final int SRUNROUTED = 4;

	/** the arc used for vertical wires */			private ArcProto mazeVertWire;
	/** the arc used for horizontal wires */		private ArcProto mazeHorizWire;
	/** the pin used to join arcs */				private NodeProto mazeSteinerNode;
	/** the layer used for vertical wires */		private Layer mazeVertLayer;
	/** the layer used for horizontal wires */		private Layer mazeHorizLayer;
	/** half the width of wires (for DRC bloat) */	private double mazeBloat;
	/** the routing region with all data */			private SRREGION theRegion = null;
	/** The netlist for the cell being routed */	private Netlist netList;
	/** Space around net to build search grid */	private int mazeBoundary = 20;

	static class SRDIRECTION {}
	SRDIRECTION SRVERTPREF = new SRDIRECTION();
	SRDIRECTION SRHORIPREF = new SRDIRECTION();
	SRDIRECTION SRALL = new SRDIRECTION();

	static class SRPTYPE {}
	SRPTYPE SRPFIXED = new SRPTYPE();
	SRPTYPE SRPROUTED = new SRPTYPE();

	/**
	 * Defines a routing region to the router
	 */
	static class SRREGION
	{
		/** lower bound of the region */	int        lx, ly;
		/** upper bound of the region */	int        hx, hy;
		/** the array of layers */			SRLAYER [] layers;
		/** the list of nets */				SRNET      nets;

		SRREGION()
		{
			layers = new SRLAYER[SRMAXLAYERS];
		}
	};

	static class SRLAYER
	{
												byte     [] hused, vused;
		/** the layer index (sort order) */		int         index;
		/** the layer mask */					long        mask;
		/** translation value for grid */		int         transx, transy;
		/** the width and height of the grid */	int         wid, hei;
		/** bounds of the current maze */		int         lx, ly, hx, hy;
		/** the two dimensional grid array */	byte   [][] grids;
		/** up/down pointer to next layer */	SRLAYER     up, down;
		/** allowed direction of routes */		SRDIRECTION dir;
	};

	/**
	 * Defines a net in a region. Note that no existing segments of a net is predefined.
	 * Only ports are allowed. Not all nets in region need to be defined.
	 */
	static class SRNET
	{
		/** route state flag */				boolean  routed;
		/** the Network object */			Network  eNet;
		/** the parent region */			SRREGION region;
		/** the list of ports on the net */	SRPORT   ports;
		/** the list of paths */			SRPATH   paths;
		/** the last path in the list */	SRPATH   lastpath;
		/** next in the list of nets */		SRNET    next;
	};

	/**
	 * Defines a port on a net. Bounds of the port are in grid units.
	 * An index of 0 means all layers, 1 = 1st layer, 2 = 2nd layer, 4 - 3rd layer, etc.
	 */
	static class SRPORT
	{
		/** the port index */					int       index;
		/** the layer mask */					long      layers;
		/** true center of the port */			double    cX, cY;
		/** bounds of the port */				int       lx, ly, hx, hy;
		/** where this port comes from */		PortInst  pi;
		/** the master (connected) port */		SRPORT    master;
		/** the list of connected paths */		SRPATH    paths;
		/** the last path in the list */		SRPATH    lastpath;
		/** the current wave front */			SRWAVEPT  wavefront;
		/** the parent net */					SRNET     net;
		/** next in the list of ports */		SRPORT    next;
	};

	static class SRPATH
	{
		/** end points of the path */		int []   x, y;
		/** end pt in world units */		double []   wx, wy;
		/** the layer of the path */		SRLAYER  layer;
		/** end style of the path */		boolean [] end;
		/** the type of path */				SRPTYPE  type;
		/** the port path is attached to */	SRPORT   port;
		/** next in the list of paths */	SRPATH   next;

		SRPATH()
		{
			x = new int[2];
			y = new int[2];
			wx = new double[2];
			wy = new double[2];
			end = new boolean[2];
		}
	};

	/**
	 * routing data types
	 */
	static class SRWAVEPT
	{
		/** x y location of the point */		int      x, y;
		/** the layer for the point */			SRLAYER  layer;
		/** the port for this point */			SRPORT   port;
		/** next/prev in the list of points */	SRWAVEPT next, prev;
	};

	/************************************* TOP-LEVEL CONTROL CODE *************************************/

	public static void mazeRoute()
	{
		UserInterface ui = Job.getUserInterface();
		Cell cell = ui.needCurrentCell();
		if (cell == null) return;
		EditWindow_ wnd = ui.getCurrentEditWindow_();
		if (wnd == null) return;

		Netlist netList = cell.acquireUserNetlist();
		if (netList == null)
		{
			System.out.println("Sorry, a deadlock aborted routing (network information unavailable).  Please try again");
			return;
		}
		Set<Network> nets = wnd.getHighlightedNetworks();

		// turn the set of Nets back into a list of Arcs to route
		List<ArcInst> arcsToRoute = new ArrayList<ArcInst>();
		for(Iterator<ArcInst> it = cell.getArcs(); it.hasNext(); )
		{
			ArcInst ai = it.next();
			if (ai.getProto() != Generic.tech().unrouted_arc) continue;
			Network net = netList.getNetwork(ai, 0);
			if (nets.contains(net))
			{
				arcsToRoute.add(ai);
				nets.remove(net);
			}
		}

		// turn off highlighting
		wnd.clearHighlighting();
		wnd.finishedHighlighting();

		new MazeRouteJob(cell, arcsToRoute);
	}

	private static class MazeRouteJob extends Job
	{
		private Cell cell;
		private List<ArcInst> arcs;

		protected MazeRouteJob(Cell cell, List<ArcInst> arcs)
		{
			super("Maze Route", Routing.getRoutingTool(), Job.Type.CHANGE, null, null, Job.Priority.USER);
			this.cell = cell;
			this.arcs = arcs;
			startJob();
		}

		public boolean doIt() throws JobException
		{
			Maze router = new Maze();
			router.routeSelected(cell, arcs);
			return true;
		}
	}

	/**
	 * This is the public interface for Maze Routing when done in batch mode.
	 * It replaces the selected unrouted arcs with routed geometry
	 * @param cell the cell to be Maze-routed.
	 */
	public void routeSelected(Cell cell, List<ArcInst> arcsToRoute)
	{
		if (arcsToRoute.size() == 0)
		{
			netList = cell.acquireUserNetlist();
			Set<Network> nets = new HashSet<Network>();
			for (Iterator<ArcInst> it = cell.getArcs(); it.hasNext();)
			{
				ArcInst ai = it.next();
				if (ai.getProto() != Generic.tech().unrouted_arc) continue;
				Network net = netList.getNetwork(ai, 0);
				if (nets.contains(net)) continue;
				arcsToRoute.add(ai);
				nets.add(net);
			}
		}

		// now route each arc
		for(ArcInst ai : arcsToRoute)
		{
			// reacquire the netlist for the current configuration
			netList = cell.acquireUserNetlist();

			// route the unrouted arc
			Network net = netList.getNetwork(ai, 0);
			if (routeNet(net)) continue;
		}
	}

	/**
	 * Method to reroute a network.
	 * @param net the network to route.
	 * @return true on error.
	 */
	private boolean routeNet(Network net)
	{
		// get extent of net and mark nodes and arcs on it
		HashSet<ArcInst> arcsToDelete = new HashSet<ArcInst>();
		HashSet<NodeInst> nodesToDelete = new HashSet<NodeInst>();
		List<Connection> netEnds = Routing.findNetEnds(net, arcsToDelete, nodesToDelete, netList, true);
		int count = netEnds.size();
		if (count == 0) return false;
		if (count != 2)
		{
			System.out.println("Error: Network " + net.describe(false) + " has " + count +
				" ends, but can only route nets with 2 ends");
			return true;
		}

		// determine bounds of this networks
		Cell cell = net.getParent();
		Rectangle2D routingBounds = null;
		for(Iterator<ArcInst> it = cell.getArcs(); it.hasNext(); )
		{
			ArcInst ai = it.next();
			Network aNet = netList.getNetwork(ai, 0);
			if (aNet != net) continue;
			Rectangle2D arcBounds = ai.getBounds();
			if (routingBounds == null) routingBounds = arcBounds; else
			{
				Rectangle2D.union(routingBounds, arcBounds, routingBounds);
			}
		}
		if (routingBounds == null)
		{
			System.out.println("Internal error: no bounding area for routing");
			return true;
		}

		// determine arc to route
		ArcProto routingArc = User.getUserTool().getCurrentArcProto();
		if (routingArc == Generic.tech().unrouted_arc) routingArc = null;
		if (routingArc != null)
		{
			// see if the default arc can be used to route
			for(int i=0; i<count; i++)
			{
				Connection con = netEnds.get(i);
				boolean found = con.getPortInst().getPortProto().getBasePort().connectsTo(routingArc);
				if (!found) { routingArc = null;   break; }
			}
		}

		// if current arc cannot run, look for any that can
		if (routingArc == null)
		{
			// check out all arcs for use in this route
			HashSet<ArcProto> arcsUsed = new HashSet<ArcProto>();
			for(int i=0; i<count; i++)
			{
				Connection con = netEnds.get(i);
				ArcProto [] connections = con.getPortInst().getPortProto().getBasePort().getConnections();
				for(int j = 0; j < connections.length; j++)
				{
					ArcProto ap = connections[j];
					if (ap.getTechnology() == Generic.tech()) continue;
					arcsUsed.add(ap);
				}
			}
			for(Iterator<Technology> it = Technology.getTechnologies(); it.hasNext(); )
			{
				Technology tech = it.next();
				if (tech == Generic.tech()) continue;
				for(Iterator<ArcProto> aIt = tech.getArcs(); aIt.hasNext(); )
				{
					ArcProto ap = aIt.next();
					if (!arcsUsed.contains(ap)) continue;
					boolean allFound = true;
					for(int i=0; i<count; i++)
					{
						Connection con = netEnds.get(i);
						boolean found = con.getPortInst().getPortProto().getBasePort().connectsTo(ap);
						if (!found) { allFound = false;   break; }
					}
					if (allFound)
					{
						routingArc = ap;
						break;
					}
				}
				if (routingArc != null) break;
			}
		}
		if (routingArc == null)
		{
			System.out.println("Cannot find wire to route");
			return true;
		}
		mazeVertWire = routingArc;
		mazeHorizWire = routingArc;
		mazeSteinerNode = routingArc.findPinProto();
        mazeVertLayer = mazeVertWire.getLayer(0);
        mazeHorizLayer = mazeHorizWire.getLayer(0);
//		Iterator<ArcLayer> it = mazeVertWire.getArcLayers();
//		mazeVertLayer = it.next().getLayer();
//		it = mazeHorizWire.getArcLayers();
//		mazeHorizLayer = it.next().getLayer();
		mazeBloat = 0;
		double wid = 10, len = 100;
		DRCTemplate rule = DRC.getSpacingRule(mazeVertLayer, null, mazeVertLayer, null, false, 0, wid, len);
		if (rule != null) mazeBloat = rule.getValue(0) + mazeVertWire.getDefaultLambdaBaseWidth()/2;

		// now create the routing region
		int lx = (int)routingBounds.getMinX();
		int hx = (int)routingBounds.getMaxX();
		int ly = (int)routingBounds.getMinY();
		int hy = (int)routingBounds.getMaxY();
		SRREGION region = defineRegion(cell, net, lx, ly, hx, hy, arcsToDelete, nodesToDelete);
		if (region == null) return true;

		// create the net in the region
		SRNET srnet = addNet(region, net);
		if (srnet == null)
		{
			System.out.println("Could not allocate internal net");
			return true;
		}

		// add the ports to the net
		for(int i=0; i<count; i++)
		{
			Connection con = netEnds.get(i);
			PortInst pi = con.getPortInst();
			double cXD = con.getLocation().getX();
			double cYD = con.getLocation().getY();
			SRPORT fsp = addPort(srnet, determineDir(pi.getNodeInst(), cXD, cYD), cXD, cYD, pi);
			if (fsp == null)
			{
				System.out.println("Port could not be defined");
				return true;
			}
		}
//dumpLayer("BEFORE ROUTING", region, 0xFF);

		// do maze routing
		if (routeANet(srnet))
		{
			System.out.println("Could not route net " + srnet.eNet.describe(false));
			return true;
		}

		// extract paths to create arcs
		if (extractPaths(cell, srnet))
		{
			System.out.println("Could not create paths");
			return true;