river.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: River.java
 * Routing tool: River Routing (busses).
 * Original C Code written by Telle Whitney, Schlumberger Palo Alto Research
 * 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.hierarchy.Cell;
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.Geometric;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.database.topology.PortInst;
import com.sun.electric.database.variable.EditWindow_;
import com.sun.electric.database.variable.UserInterface;
import com.sun.electric.technology.ArcProto;
import com.sun.electric.technology.Layer;
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.menus.MenuCommands;

import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/**
 * Class to do river routing.
 * <P>
 * River Routing takes two sets of parallel points (connectors, ports, etc) and routes wires
 * between them.  All wires are routed in a single layer with non intersecting lines.
 * <PRE>
 *                       p1        p2         p3      p4
 *                        |        |           |       |  /\ cell_off2
 *                       _|        |           |   ____|  \/
 *                      |          |           |  |
 *                    __|    ______|           |  |
 *                   |      |                  |  |
 *                   |   ___|      ____________|  |
 *                   |  |         | /\ pitch      |
 *                 __|  |      ___| \/____________|
 *  cell_off1 /\  |     |     |    <>|
 *            \/  |     |     |      |
 *               a1    a2    a3     a4
 * </PRE>
 * Restrictions:
 * <UL>
 * <LI>The distance between the ports (p1..pn) and (a1..an) is >= "pitch"</LI>
 * <LI>The parameter "width" specifies the width of all wires<BR>
 *     The parameter "space" specifies the distance between wires<BR>
 *     pitch = 2*(width/2) + space = space + width</LI>
 * </UL>
 * The sides:
 * <PRE>
 *                        SIDE3
 *       ________________________________________
 *       |  route  |                  |  route  |
 *     S |  right  |                  |  left   | S
 *     I | (last)  |   normal right   | (last)  | I
 *     D |_________|  and left route  |_________| D
 *     E |  route  |     (middle)     |  route  | E
 *     4 |  left   |                  |  right  | 2
 *       | (first) |                  | (first) |
 *       |_________|__________________|_________|
 *                        SIDE1
 * </PRE>
 */
public class River
{
	private static final int ROUTEINX     = 1;
	private static final int ROUTEINY     = 2;
	private static final int ILLEGALROUTE = -1;
//	/** bottom to top  -- side 1 to side 3 */			private static final int BOTTOP   = 1;
//	/** side   to top  -- side 2 or side 4 to side 3 */	private static final int FROMSIDE = 2;
//	/** bottom to side -- side 1 to side 3 or side 2 */	private static final int TOSIDE   = 3;

	/** list of RDESC objects */						private List<RDESC> rightP, leftP;
	/** the initial coordinate of the route */			private double      fromLine;
	/** final coordinate of the route */				private double      toLine;
	/**  ROUTEINX route in X, ROUTEINY route in Y */	private int         routDirection;
	/** where to start wires on the right */			private double      startRight;
	/** where to start wires on the left */				private double      startLeft;
	/** linked list of possible routing coordinates */	private RCOORD      xAxis, yAxis;
	private double   height;
	private double   routBoundLX, routBoundLY, routBoundHX, routBoundHY;
	private double   wireBoundLX, wireBoundLY, wireBoundHX, wireBoundHY;
	private NodeInst moveCell;
	private boolean  moveCellValid;

	/**
	 * Class for transformations.
	 */
	static class TRANSFORM
	{
		private double t11, t12;
		private double t21, t22;

		TRANSFORM(double t11, double t12, double t21, double t22)
		{
			this.t11 = t11;
			this.t12 = t12;
			this.t21 = t21;
			this.t22 = t22;
		}
	};
	/** X increasing, y2>y1 */							private static final TRANSFORM xfNoRot        = new TRANSFORM( 1,  0,  0,  1);
	/** Y decreasing, x2>x1 */							private static final TRANSFORM xfRot90        = new TRANSFORM( 0,  1, -1,  0);
	/** X decreasing, y2<y1 */							private static final TRANSFORM xfRot180       = new TRANSFORM(-1,  0,  0, -1);
	/** Y increasing, x2<x1 or rot -90 */				private static final TRANSFORM xfRot270       = new TRANSFORM( 0, -1,  1,  0);
	/** X decreasing, y2>y1 mirror X, around Y axis */	private static final TRANSFORM xfMirrorX      = new TRANSFORM(-1,  0,  0,  1);
	/** Y increasing, x2>x1 rot90 and mirror X */		private static final TRANSFORM xfRot90MirrorX = new TRANSFORM( 0,  1,  1,  0);
	/** X increasing, y2<y1 mirror Y, around X axis */	private static final TRANSFORM xfMirrorY      = new TRANSFORM( 1,  0,  0, -1);
	/** Y decreasing, x2<x1 mirror X, rot90 */			private static final TRANSFORM xfMirrorXRot90 = new TRANSFORM( 0, -1, -1,  0);
	/** tx,ty */										private static final TRANSFORM xfInverse      = new TRANSFORM( 1,  0,  0,  1);

	/**
	 * Class for points in the river routing.
	 */
	static class RPOINT
	{
		private static final int NOSIDE = -1;
		private static final int SIDE1  = 1;
		private static final int SIDE2  = 2;
		private static final int SIDE3  = 3;
		private static final int SIDE4  = 4;

		/** the side this point is on */	private int    side;
		/** points coordinates */			private double x, y;
		/** nonrotated coordinates */		private double first, second;
		/** next one in the list */			private RPOINT next;

		static String sideName(int side)
		{
			switch (side)
			{
				case SIDE1: return "bottom";
				case SIDE2: return "right";
				case SIDE3: return "top";
				case SIDE4: return "left";
			}
			return "unknown";
		}

		RPOINT(double xV, double yV, int s)
		{
			side = s;
			x = xV;
			y = yV;
			first = 0;
			second = 0;
			next = null;
		}

		RPOINT(RPATH rp, double fir, double sec, RPOINT next)
		{
			side = NOSIDE;
			x = 0;
			y = 0;
			first = fir;
			second = sec;
			this.next = next;
			if (next != null) return;
			rp.lastP = this;
		}
	};

	/**
	 * Class for paths in the river routing.
	 */
	static class RPATH
	{
		/** the width of this path */			private double   width;
		/** the paty type for this wire */		private ArcProto pathType;
		/** the path */							private RPOINT   pathDesc;
		/** the last point on the path */		private RPOINT   lastP;

		RPATH(double wid, ArcProto ptype)
		{
			width = wid;
			pathType = ptype;
			pathDesc = null;
			lastP = null;
		}
	};

	/**
	 * Class for river routing.
	 */
	static class RDESC
	{
		private RPOINT  from;
		private RPOINT  to;
		private double  sortVal;
		private ArcInst unroutedWire1;
		private ArcInst unroutedWire2;
		private int     unroutedEnd1;
		private int     unroutedEnd2;
		private RPATH   path;

		RDESC(double fx, double fy, int fside, double sx, double sy, int sside,
			ArcInst ai1, int ae1, ArcInst ai2, int ae2)
		{
			from = new RPOINT(fx, fy, fside);
			to = new RPOINT(sx, sy, sside);
			unroutedWire1 = ai1;   unroutedEnd1 = ae1;
			unroutedWire2 = ai2;   unroutedEnd2 = ae2;
			path = null;
		}
	};

	/**
	 * Class for coordinate values in the river routing.
	 */
	static class RCOORD
	{
		/** the coordinate */								private double val;
		/** number of wires voting for this coordinate */	private int    total;
															private RCOORD next;

		RCOORD(double c)
		{
			this.val = c;
			this.total = 0;
			this.next = null;
		}
	};

	/*************************************** MAIN CONTROL CODE ***************************************/

	public static void riverRoute()
	{
		UserInterface ui = Job.getUserInterface();
		Cell curCell = ui.needCurrentCell();
		if (curCell == null) return;
		new RiverRouteJob(curCell);
	}

	private static class RiverRouteJob extends Job
	{
		private Cell cell;

		protected RiverRouteJob(Cell cell)
		{
			super("River Route", Routing.getRoutingTool(), Job.Type.CHANGE, null, null, Job.Priority.USER);
			this.cell = cell;
			startJob();
		}

		public boolean doIt() throws JobException
		{
			River router = new River();
			router.river(cell);
			return true;
		}

        public void terminateOK()
        {
			UserInterface ui = Job.getUserInterface();
			EditWindow_ wnd = ui.getCurrentEditWindow_();
	        if (wnd != null)
	        {
	        	wnd.clearHighlighting();
	        	wnd.finishedHighlighting();
	        }
        }
	}

	/**
	 * This is the public interface for River Routing when done in batch mode.
	 * @param cell the cell to be River-routed.
	 */
	public void river(Cell cell)
	{
		// locate wires
		if (findWires(cell))
		{
			// make wires
			for(RDESC q : rightP)
			{
				checkTheCell(q.unroutedWire2.getPortInst(q.unroutedEnd2).getNodeInst());
			}
			for(RDESC q : leftP)
			{
				checkTheCell(q.unroutedWire2.getPortInst(q.unroutedEnd2).getNodeInst());
			}

			// if there is motion to be done, do it
			if (moveCellValid && moveCell != null)
			{
				if (moveInstance()) makeTheGeometry(cell);
			} else makeTheGeometry(cell);
		}
	}

	/*************************************** CODE TO DO RIVER ROUTING ***************************************/

	/**
	 * once the route occurs, make some geometry and move some cells around
	 */
	private void checkTheCell(NodeInst ni)
	{
		if (ni.isCellInstance())
		{
			// the node is nonprimitive
			if (!moveCellValid) return;
			if (moveCell == null)  // first one
				moveCell = ni;
			else if (moveCell != ni) moveCellValid = false;
		}
	}

	private boolean findWires(Cell cell)
	{
		initialize();

		// reset flags on all arcs in this cell
		HashSet<ArcInst> arcsSeen = new HashSet<ArcInst>();

		// make a list of RDESC objects
		List<RDESC> theList = new ArrayList<RDESC>();

		// get list of all highlighted arcs
		boolean foundSome = false;
		UserInterface ui = Job.getUserInterface();
		EditWindow_ wnd = ui.getCurrentEditWindow_();
		if (wnd != null)
		{
			Set<Network> nets = wnd.getHighlightedNetworks();
			if (nets.size() != 0)
			{
				Netlist netList = cell.acquireUserNetlist();
				if (netList == null)
				{
					System.out.println("Sorry, a deadlock aborted routing (network information unavailable).  Please try again");
					return false;
				}

				// add all highlighted arcs to the list of RDESC objects
				for(Iterator<ArcInst> it = cell.getArcs(); it.hasNext(); )
				{
					ArcInst ai = it.next();
					Network net = netList.getNetwork(ai, 0);
					if (nets.contains(net)) addWire(theList, ai, arcsSeen);
				}
				foundSome = true;
			}
		}
		if (!foundSome)
		{
			// add all arcs in the cell to the list of RDESC objects
			for(Iterator<ArcInst> it = cell.getArcs(); it.hasNext(); )
			{
				ArcInst ai = it.next();
				addWire(theList, ai, arcsSeen);
			}
		}

		// determine bounds of the routes
		boolean first = true;
		for(RDESC rdesc : theList)
		{
			if (first)
			{
				routBoundLX = Math.min(rdesc.from.x, rdesc.to.x);
				routBoundLY = Math.min(rdesc.from.y, rdesc.to.y);
				routBoundHX = Math.max(rdesc.from.x, rdesc.to.x);
				routBoundHY = Math.max(rdesc.from.y, rdesc.to.y);
			} else
			{
				routBoundLX = Math.min(Math.min(routBoundLX, rdesc.from.x), rdesc.to.x);
				routBoundLY = Math.min(Math.min(routBoundLY, rdesc.from.y), rdesc.to.y);
				routBoundHX = Math.max(Math.max(routBoundHX, rdesc.from.x), rdesc.to.x);
				routBoundHY = Math.max(Math.max(routBoundHY, rdesc.from.y), rdesc.to.y);
			}
		}

		// figure out which ArcProto to use
		HashMap<ArcProto,GenMath.MutableInteger> arcProtoUsage = new HashMap<ArcProto,GenMath.MutableInteger>();
		for(RDESC rd : theList)
		{
			sumUp(rd.unroutedWire1.getPortInst(rd.unroutedEnd1), arcProtoUsage);
			sumUp(rd.unroutedWire2.getPortInst(rd.unroutedEnd2), arcProtoUsage);
		}

		// find the most popular ArcProto
		ArcProto wantAp = null;
		int mostUses = -1;
		int total = 0;
		for(ArcProto ap : arcProtoUsage.keySet())
		{
			GenMath.MutableInteger mi = arcProtoUsage.get(ap);
			if (mi == null) continue;
			total += mi.intValue();
			if (mi.intValue() > mostUses)
			{
				mostUses = mi.intValue();
				wantAp = ap;
			}
		}
		if (wantAp == null)
		{
			System.out.println("River router: Cannot find arc that will connect");
			return false;
		}
		System.out.println("River routing with " + wantAp.describe() + " arcs");

		figureOutRails(total);
		setWiresToRails(theList);

		// figure out the worst design rule spacing for this type of arc
		Layer layer = wantAp.getLayerIterator().next();
		double amt = DRC.getMaxSurround(layer, Double.MAX_VALUE);
		if (amt < 0) amt = 1;
		return unsortedRivRot(wantAp, theList, wantAp.getDefaultLambdaBaseWidth(), amt, amt, amt);
	}

	/**
	 * takes two unsorted list of ports and routes between them
	 * warning - if the width is not even, there will be round off problems
	 */
	private boolean unsortedRivRot(ArcProto layerDesc, List<RDESC> lists, double width,
		double space, double cellOff1, double cellOff2)
	{
		for(RDESC rd : lists)
		{
			rd.sortVal = (routDirection != ROUTEINX ? rd.from.x : rd.from.y);
		}
		Collections.sort(lists, new SortRDESC());

		return sortedRivRot(layerDesc, lists, width, space, cellOff1, cellOff2);
	}

	private static class SortRDESC implements Comparator<RDESC>
	{
		public int compare(RDESC r1, RDESC r2)
		{
			if (r1.sortVal == r2.sortVal) return 0;
			if (r1.sortVal > r2.sortVal) return 1;
			return -1;
		}
	}

	/**
	 * takes two sorted list of ports and routes between them
	 * warning - if the width is not even, there will be round off problems
	 */
	private boolean sortedRivRot(ArcProto layerDesc, List<RDESC> listR, double width,
		double space, double cellOff1, double cellOff2)
	{