river.java

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

				{
					System.out.println("River router: Ports not design rule distance apart");
					return false;
				}
			}

			// not far enough apart
			lastFrom = (lList.from.side == RPOINT.SIDE1) ? lList.from : null;
			lastTo = (lList.to.side == RPOINT.SIDE3) ? lList.to : null;
		}

		// matrix to take route back to original coordinate system
		xfInverse.t11 = tMatrix.t11;       xfInverse.t12 = tMatrix.t21;
		xfInverse.t21 = tMatrix.t12;       xfInverse.t22 = tMatrix.t22;
		fromLine = val1;   toLine = val2;
		return true;
	}

	private void clipWire(RPOINT p, double b1, double b2)
	{
		double diff1 = Math.abs(b1 - p.first);
		double diff2 = Math.abs(b2 - p.first);
		if (diff1 < diff2)
		{
			p.first = b1;   p.side = RPOINT.SIDE4;
		} else
		{
			p.first = b2;   p.side = RPOINT.SIDE2;
		}
	}

	private void setWiresToRails(List<RDESC> lists)
	{
		for(RDESC r : lists)
		{
			double fVal = pointVal(r.from, routDirection);
			double tVal = pointVal(r.to, routDirection);
			if ((fVal != fromLine && tVal == fromLine) ||
				(tVal != toLine && fVal == toLine))
					swapPoints(r);
		}
	}

	private void swapPoints(RDESC r)
	{
		if (r.from.side != RPOINT.SIDE1 || r.to.side != RPOINT.SIDE3)
			System.out.println("River router: Unexpected side designation");

		RPOINT tmp = r.from;   r.from = r.to;   r.to = tmp;

		r.from.side = RPOINT.SIDE1;   r.to.side = RPOINT.SIDE3;
		ArcInst tmpwire = r.unroutedWire1;   int tmpe = r.unroutedEnd1;
		r.unroutedWire1 = r.unroutedWire2;   r.unroutedEnd1 = r.unroutedEnd2;
		r.unroutedWire2 = tmpwire;           r.unroutedEnd2 = tmpe;
	}

	private double pointVal(RPOINT rp, int xx)
	{
		return xx == ROUTEINX ? rp.x : rp.y;
	}

	private void figureOutRails(int total)
	{
		RCOORD lX = largest(xAxis);
		RCOORD lY = largest(yAxis);
		RCOORD nLX = nextLargest(xAxis, lX);
		RCOORD nLY = nextLargest(yAxis, lY);

		// determine the type of route
		RCOORD from = null;
		RCOORD to = null;
		int fxx = ILLEGALROUTE;
		if (lX != null && nLX != null && lX.total == total && nLX.total == total)
		{
			from = lX;   to = nLX;
			fxx = ROUTEINX;
		} else if (lY != null && nLY != null && lY.total == total && nLY.total == total)
		{
			from = lY;   to = nLY;
			fxx = ROUTEINY;
		} else if (lX != null && lX.total == (2*total))
		{
			from = to = lX;
			fxx = ROUTEINX;
		} else if (lY != null && lY.total == (2*total))
		{
			from = to = lY;
			fxx = ROUTEINY;
		}

		if (fxx == ILLEGALROUTE)
		{
			if (lX.total >= total)
			{
				// lX.total == total --- the other one an unusual case
				// lX.total > total  --- both go to the same line
				fxx = ROUTEINX;   from = lX;
				to = (lX.total > total ? lX : nLX);
			} else if (lY.total >= total)
			{
				// lY.total == total --- the other one an unusual case
				// lY.total > total  --- both go to the same line
				fxx = ROUTEINY;   from = lY;
				to = (lY.total > total ? lY : nLY);
			} else
			{
				fxx = (((lY.total+nLY.total)>=(lX.total+nLX.total)) ? ROUTEINY : ROUTEINX);
				from = (fxx == ROUTEINY ? lY : lX);
				to = (fxx == ROUTEINY ? nLY : nLX);
			}
		}

		if (to.val < from.val)
		{
			RCOORD tmp = from;   from = to;   to = tmp;
		}

		routDirection = fxx;
		fromLine = from.val;   toLine = to.val;
	}

	private RCOORD largest(RCOORD cc)
	{
		RCOORD largest = cc;

		for(; cc != null; cc = cc.next)
		{
			if (cc.total > largest.total) largest = cc;
		}
		return largest;
	}

	private RCOORD nextLargest(RCOORD cc, RCOORD largest)
	{
		RCOORD nLargest = null;

		for( ; cc != null; cc = cc.next)
		{
			if (nLargest == null && cc != largest) nLargest = cc; else
				if (nLargest != null && cc != largest && cc.total > nLargest.total) nLargest = cc;
		}
		return nLargest;
	}

	/**
	 * for every layer (or arcproto) that this PORT allows to connect to it,
	 * increment the flag bits (temp1) IN the prototype thus indicating that
	 * this river route point is allowed to connect to it
	 */
	private void sumUp(PortInst pi, HashMap<ArcProto,GenMath.MutableInteger> arcProtoUsage)
	{
		ArcProto [] possibleArcs = pi.getPortProto().getBasePort().getConnections();
		for(int i=0; i<possibleArcs.length; i++)
		{
			ArcProto ap = possibleArcs[i];
			if (ap.getTechnology() == Generic.tech()) continue;
			GenMath.MutableInteger mi = arcProtoUsage.get(ap);
			if (mi == null)
			{
				mi = new GenMath.MutableInteger(0);
				arcProtoUsage.put(ap, mi);
			}
			mi.increment();
		}
	}

	private void initialize()
	{
		rightP = null;
		leftP = null;
		fromLine = toLine = Double.MIN_VALUE;
		startRight = Double.MIN_VALUE;
		startLeft = Double.MIN_VALUE;
		height = Double.MIN_VALUE;
		routDirection = ILLEGALROUTE;

		xAxis = null;
		yAxis = null;
		for(RCOORD c = xAxis; c != null; c = c.next) c.total = -1;
		for(RCOORD c = yAxis; c != null; c = c.next) c.total = -1;
		moveCell = null;   moveCellValid = true;
	}

	/**
	 * figure out the wires to route at all
	 */
	private void addWire(List<RDESC> list, ArcInst ai, HashSet<ArcInst> arcsSeen)
	{
		if (!isInterestingArc(ai, arcsSeen)) return;

		arcsSeen.add(ai);
		ArcInst ae1 = ai;   int e1 = 0;
		for(;;)
		{
			NodeInst ni = ae1.getPortInst(e1).getNodeInst();
			if (!isUnroutedPin(ni)) break;
			ArcInst oAi = null;
			for(Iterator<Connection> it = ni.getConnections(); it.hasNext(); )
			{
				Connection con = it.next();
				oAi = con.getArc();
				if (!arcsSeen.contains(oAi)) break;
				oAi = null;
			}
			if (oAi == null) break;
			arcsSeen.add(oAi);
			if (oAi.getPortInst(0).getNodeInst() == ni) e1 = 1; else e1 = 0;
			ae1 = oAi;
		}
		ArcInst ae2 = ai;   int e2 = 1;
		for(;;)
		{
			NodeInst ni = ae2.getPortInst(e2).getNodeInst();
			if (!isUnroutedPin(ni)) break;
			ArcInst oAi = null;
			for(Iterator<Connection> it = ni.getConnections(); it.hasNext(); )
			{
				Connection con = it.next();
				oAi = con.getArc();
				if (!arcsSeen.contains(oAi)) break;
				oAi = null;
			}
			if (oAi == null) break;
			arcsSeen.add(oAi);
			if (oAi.getPortInst(0).getNodeInst() == ni) e2 = 1; else e2 = 0;
			ae2 = oAi;
		}

		PortInst pi1 = ae1.getPortInst(e1);
		Poly poly1 = pi1.getPoly();
		double bx = poly1.getCenterX();
		double by = poly1.getCenterY();
		PortInst pi2 = ae2.getPortInst(e2);
		Poly poly2 = pi2.getPoly();
		double ex = poly2.getCenterX();
		double ey = poly2.getCenterY();
		RDESC rd = new RDESC(bx, by, RPOINT.SIDE1, ex, ey, RPOINT.SIDE3, ae1, e1, ae2, e2);
		list.add(rd);
		vote(rd.from.x, rd.from.y, rd.to.x, rd.to.y);
	}

	private void vote(double ffx, double ffy, double ttx, double tty)
	{
		xAxis = tallyVote(xAxis, ffx);
		yAxis = tallyVote(yAxis, ffy);
		xAxis = tallyVote(xAxis, ttx);
		yAxis = tallyVote(yAxis, tty);
	}

	/**
	 * Figure out which way to route (x and y) and the top coordinate and
	 * bottom coordinate
	 */
	private RCOORD tallyVote(RCOORD cc, double c)
	{
		if (cc == null)
		{
			cc = new RCOORD(c);
			cc.total = 1;
			return cc;
		}

		RCOORD ccInit = cc;
		RCOORD ccLast = null;
		for( ; (cc != null && cc.total >= 0 && cc.val != c); ccLast = cc, cc = cc.next) ;
		if (cc == null)
		{
			cc = new RCOORD(c);
			ccLast.next = cc;
			cc.total = 1;
			return ccInit;
		}

		if (cc.total < 0)
		{
			cc.val = c;
			cc.total = 1;
		} else cc.total++;
		return ccInit;
	}

	private boolean isInterestingArc(ArcInst ai, HashSet arcsSeen)
	{
		// skip arcs already considered
		if (arcsSeen.contains(ai)) return false;

		// only want "unrouted" arc in generic technology
		if (ai.getProto() != Generic.tech().unrouted_arc) return false;

		return true;
	}

	/**
	 * Method to return true if nodeinst "ni" is an unrouted pin
	 */
	private boolean isUnroutedPin(NodeInst ni)
	{
		// only want the unrouted pin
		if (ni.getProto() != Generic.tech().unroutedPinNode &&
			ni.getProto() != Generic.tech().universalPinNode) return false;

		// found one
		return true;
	}

	/*************************************** CODE TO GENERATE CIRCUITRY ***************************************/

	private void makeTheGeometry(Cell cell)
	{
		HashSet<ArcInst> arcsToDelete = new HashSet<ArcInst>();
		HashSet<NodeInst> nodesToDelete = new HashSet<NodeInst>();
		for(RDESC q : rightP)
		{
			makeGeometry(q, cell);
			markToBeDeleted(q.unroutedWire1, arcsToDelete, nodesToDelete);
			if (q.unroutedWire1 != q.unroutedWire2) markToBeDeleted(q.unroutedWire2, arcsToDelete, nodesToDelete);
		}
		for(RDESC q : leftP)
		{
			makeGeometry(q, cell);
			markToBeDeleted(q.unroutedWire2, arcsToDelete, nodesToDelete);
			if (q.unroutedWire1 != q.unroutedWire2) markToBeDeleted(q.unroutedWire2, arcsToDelete, nodesToDelete);
		}
		killWires(cell, arcsToDelete, nodesToDelete);
	}

	private void markToBeDeleted(ArcInst ai, HashSet<ArcInst> arcsToDelete, HashSet<NodeInst> nodesToDelete)
	{
		if (!isInterestingArc(ai, arcsToDelete)) return;

		setFlags(ai, arcsToDelete, nodesToDelete);
		ArcInst ae = ai;  int e = 0;
		for(;;)
		{
			NodeInst ni = ae.getPortInst(e).getNodeInst();
			if (!isUnroutedPin(ni)) break;
			ArcInst oAi = null;
			for(Iterator<Connection> it = ni.getConnections(); it.hasNext(); )
			{
				Connection con = it.next();
				oAi = con.getArc();
				if (!arcsToDelete.contains(oAi)) break;
				oAi = null;
			}
			if (oAi == null) break;
			setFlags(oAi, arcsToDelete, nodesToDelete);
			if (oAi.getPortInst(0).getNodeInst() == ae.getPortInst(e).getNodeInst()) e = 1; else e = 0;
			ae = oAi;
		}
		ae = ai;  e = 1;
		for(;;)
		{
			NodeInst ni = ae.getPortInst(e).getNodeInst();
			if (!isUnroutedPin(ni)) break;
			ArcInst oAi = null;
			for(Iterator<Connection> it = ni.getConnections(); it.hasNext(); )
			{
				Connection con = it.next();
				oAi = con.getArc();
				if (!arcsToDelete.contains(oAi)) break;
				oAi = null;
			}
			if (oAi == null) break;
			setFlags(oAi, arcsToDelete, nodesToDelete);
			if (oAi.getPortInst(0).getNodeInst() == ae.getPortInst(e).getNodeInst()) e = 1; else e = 0;
			ae = oAi;
		}
	}

	private void setFlags(ArcInst ai, HashSet<ArcInst> arcsToDelete, HashSet<NodeInst> nodesToDelete)
	{
		arcsToDelete.add(ai);
		NodeInst niH = ai.getHeadPortInst().getNodeInst();
		if (isUnroutedPin(niH)) nodesToDelete.add(niH);
		NodeInst niT = ai.getTailPortInst().getNodeInst();
		if (isUnroutedPin(niT)) nodesToDelete.add(niT);
	}

	private void killWires(Cell cell, HashSet<ArcInst> arcsToDelete, HashSet<NodeInst> nodesToDelete)
	{
		for(ArcInst ai : arcsToDelete)
		{
			ai.kill();
		}
		for(NodeInst ni : nodesToDelete)
		{
			if (isUnroutedPin(ni))
				delNodeInst(ni);
		}
	}

	private void delNodeInst(NodeInst ni)
	{
		// see if any arcs connect to this node
		if (ni.hasConnections()) return;

		// see if this nodeinst is a portinst of the cell
		if (ni.hasExports()) return;

		// now erase the nodeinst
		ni.kill();
	}

	/**
	 * make electric geometry
	 */
	private void makeGeometry(RDESC rd, Cell cell)
	{
		RPATH path = rd.path;

		Poly poly1 = rd.unroutedWire1.getPortInst(rd.unroutedEnd1).getPoly();
		wireBoundLX = poly1.getCenterX();
		wireBoundLY = poly1.getCenterY();
		Poly poly2 = rd.unroutedWire2.getPortInst(rd.unroutedEnd2).getPoly();
		wireBoundHX = poly2.getCenterX();
		wireBoundHY = poly2.getCenterY();

		NodeProto defNode = path.pathType.findPinProto();
		PortProto defPort = defNode.getPort(0); // there is always only one

		RPOINT prev = path.pathDesc;
		NodeInst prevNodeInst = theNode(rd, defNode, prev, cell);
		PortProto prevPort = thePort(defPort, rd, prev);
		PortInst prevPi = prevNodeInst.findPortInstFromProto(prevPort);

		for(RPOINT rp = prev.next; rp != null; rp = rp.next)
		{
			if (rp.next != null)
			{
				if (prev.x == rp.x && rp.x == rp.next.x) continue;
				if (prev.y == rp.y && rp.y == rp.next.y) continue;
			}
			NodeInst rpNodeInst = theNode(rd, defNode, rp, cell);
			PortProto rpPort = thePort(defPort, rd, rp);
			PortInst rpPi = rpNodeInst.findPortInstFromProto(rpPort);

			ArcInst.makeInstanceBase(path.pathType, path.width, prevPi, rpPi);
//			ArcInst.makeInstanceFull(path.pathType, path.width, prevPi, rpPi);
			prev = rp;   prevPi = rpPi;
		}
	}

	private NodeInst theNode(RDESC rd, NodeProto dn, RPOINT p, Cell cell)
	{
		if (p.x == wireBoundLX && p.y == wireBoundLY)
			return rd.unroutedWire1.getPortInst(rd.unroutedEnd1).getNodeInst();

		if (p.x == wireBoundHX && p.y == wireBoundHY)
			return rd.unroutedWire2.getPortInst(rd.unroutedEnd2).getNodeInst();

		double wid = dn.getDefWidth();
		double hei = dn.getDefHeight();
		NodeInst ni = NodeInst.makeInstance(dn, new Point2D.Double(p.x, p.y), wid, hei, cell);
		return ni;
	}

	private PortProto thePort(PortProto dp, RDESC rd, RPOINT p)
	{
		if (p.x == wireBoundLX && p.y == wireBoundLY)
			return rd.unroutedWire1.getPortInst(rd.unroutedEnd1).getPortProto();

		if (p.x == wireBoundHX && p.y == wireBoundHY)
			return rd.unroutedWire2.getPortInst(rd.unroutedEnd2).getPortProto();

		return dp;
	}

	private boolean moveInstance()
	{
		NodeInst ni = moveCell;
		if (!moveCellValid || ni == null)
		{
			System.out.println("River router: Cannot determine cell to move");
			return false;
		}

		double lx = (routDirection == ROUTEINX ? height + ni.getAnchorCenterX() - toLine : ni.getAnchorCenterX());
		double ly = (routDirection == ROUTEINY ? height + ni.getAnchorCenterY() - toLine : ni.getAnchorCenterY());
		if (lx == ni.getAnchorCenterX() && ly == ni.getAnchorCenterY()) return true;
		ni.move(lx - ni.getAnchorCenterX(), ly - ni.getAnchorCenterY());
		return true;
	}
}