maze.java

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

				}
				sx = ex;
				sy = ey;
				break;
			}
		}
	}

	private int testPoint(int pt, int code)
	{
		// don't check other wavefront points
		if ((pt & SR_GWAVE) == 0)
		{
			// check for permanent grid object (blockage or port)
			if ((pt & SR_GSET) != 0)
			{
				// check for port
				if ((pt & SR_GPORT) != 0 && (pt & SR_GMASK) == code) return SRROUTED;
			} else
			{
				// not permanent, check for matching code
				if ((pt & SR_GMASK) == code) return SRSUCCESS;
			}
		}
		return SRUNROUTED;
	}

	private SRPATH getPath(SRPORT port, SRLAYER layer, boolean e1, boolean e2, int x1, int y1, int x2, int y2)
	{
		SRPATH path = new SRPATH();

		path.x[0] = x1; path.y[0] = y1;
		path.x[1] = x2; path.y[1] = y2;
		path.end[0] = e1; path.end[1] = e2;
		path.layer = layer;
		path.port = port;
		path.type = SRPROUTED;

		path.wx[0] = getWorldX(x1, layer); path.wy[0] = getWorldY(y1, layer);
		path.wx[1] = getWorldX(x2, layer); path.wy[1] = getWorldY(y2, layer);

		// insert the path at the end of the list
		path.next = null;
		if (port.lastpath == null) port.paths = path; else
			port.lastpath.next = path;
		port.lastpath = path;

		// now draw it
		setLine(path.layer, SR_GPORT | SR_GSET,
			path.wx[0], path.wy[0], path.wx[1], path.wy[1], true);

		return path;
	}

	private int examinePoint(SRPORT port, SRLAYER layer, int x, int y, int code)
	{
		// point is set
		if ((layer.grids[x][y] & SR_GWAVE) != 0)
		{
			// look for common point in this wavefront
			if (searchWavefront(port, layer, x, y) == null)
			{
				return SRROUTED;
			}
		} else if (layer.grids[x][y] == 0)
		{
			// point is not set
			addWavePoint(port, layer, x, y, code);
			return SRSUCCESS;
		}
		return SRBLOCKED;
	}

	private SRWAVEPT searchWavefront(SRPORT port, SRLAYER layer, int x, int y)
	{
		// scans port's wavefront for common point
		for (SRWAVEPT wavept = port.wavefront; wavept != null; wavept = wavept.next)
		{
			if (wavept.layer == layer && wavept.x == x && wavept.y == y) return wavept;
		}
		return null;
	}

	private void clearMaze(SRNET net)
	{
		// clear each region, and reset bounds
		for (int index = 0; index < SRMAXLAYERS; index++)
		{
			SRLAYER layer = net.region.layers[index];
			if (layer != null)
			{
				int mask = ~(SR_GMASK | SR_GWAVE);
				for (int x = layer.lx; x <= layer.hx; x++)
				{
					for (int y = layer.ly; y <= layer.hy; y++)
					{
						layer.grids[x][y] = (byte)(layer.grids[x][y] & mask);
					}
				}
				layer.lx = layer.wid; layer.ly = layer.hei;
				layer.hx = -1; layer.hy = -1;
			}
		}
		for (SRPORT port = net.ports; port != null; port = port.next)
		{
			port.wavefront = null;
		}
		return;
	}

	/************************************* CODE TO CREATE THE MAZE BUFFER *************************************/

	private SRREGION defineRegion(Cell cell, Network net, int lX, int lY, int hX, int hY, Set arcsToDelete, Set nodesToDelete)
	{
		// determine routing region bounds
		lX = lX - mazeBoundary;
		hX = hX + mazeBoundary;
		lY = lY - mazeBoundary;
		hY = hY + mazeBoundary;

		// allocate region and layers
		SRREGION region = getRegion(lX, lY, hX, hY);
		if (region == null)
		{
			System.out.println("Could not allocate routing region (" + lX + "<=X<=" + hX + " " + lY + "<=Y<=" + hY + ")");
			return null;
		}

		Rectangle2D searchBounds = new Rectangle2D.Double(lX, lY, hX-lX, hY-lY);
		Visitor wcVisitor = new Visitor(searchBounds, region, net);
		HierarchyEnumerator.enumerateCell(cell, VarContext.globalContext, wcVisitor);
		return region;
	}

	private class Visitor extends HierarchyEnumerator.Visitor
    {
		private Rectangle2D searchBounds;
		private SRREGION region;
		private int notThisNetID;

		public Visitor(Rectangle2D searchBounds, SRREGION region, Network net)
        {
			this.searchBounds = searchBounds;
			this.region = region;
			notThisNetID = net.getNetIndex();
        }

        public boolean enterCell(HierarchyEnumerator.CellInfo info) { return true; }

        public void exitCell(HierarchyEnumerator.CellInfo info)
        {
			Cell cell = info.getCell();
			Netlist nl = info.getNetlist();
			AffineTransform trans = info.getTransformToRoot();
			for(Iterator<ArcInst> it = cell.getArcs(); it.hasNext(); )
			{
				ArcInst ai = it.next();
				Network net = nl.getNetwork(ai, 0);
				int netID = info.getNetID(net);
				if (netID == notThisNetID) continue;
				Rectangle2D arcBounds = ai.getBounds();
				Rectangle2D bounds = new Rectangle2D.Double(arcBounds.getMinX(), arcBounds.getMinY(),
					arcBounds.getWidth(), arcBounds.getHeight());
				DBMath.transformRect(bounds, trans);
				if (bounds.intersects(searchBounds))
					drawArcInst(ai, trans, region);
			}
        }

        public boolean visitNodeInst(Nodable no, HierarchyEnumerator.CellInfo info)
        {
			AffineTransform trans = info.getTransformToRoot();
			Netlist nl = info.getNetlist();
			NodeInst ni = no.getNodeInst();
			Rectangle2D nodeBounds = ni.getBounds();
			Rectangle2D bounds = new Rectangle2D.Double(nodeBounds.getMinX(), nodeBounds.getMinY(),
				nodeBounds.getWidth(), nodeBounds.getHeight());
			DBMath.transformRect(bounds, trans);
			if (!bounds.intersects(searchBounds)) return false;

			if (!ni.isCellInstance())
			{
				PrimitiveNode pNp = (PrimitiveNode)ni.getProto();
				Technology tech = pNp.getTechnology();
				Poly [] nodeInstPolyList = tech.getShapeOfNode(ni, true, true, null);
				for(int i=0; i<nodeInstPolyList.length; i++)
				{
					Poly poly = nodeInstPolyList[i];
					PortProto pp = poly.getPort();
					Network net = nl.getNetwork(no, pp, 0);
					if (net != null)
					{
						int netID = info.getNetID(net);
						if (netID == notThisNetID) continue;
					}

					poly.transform(trans);
					drawPoly(poly, region, ALLLAYERS);
				}
			}
            return true;
        }
    }

	/**
	 * Method to draw an arcinst.  Returns indicator of what else needs to
	 * be drawn.  Returns negative if display interrupted
	 */
	private void drawArcInst(ArcInst ai, AffineTransform trans, SRREGION region)
	{
		// get the polygons of the arcinst, force line for path generation?
		if (ai.getProto() == Generic.tech().unrouted_arc) return;
		Technology tech = ai.getProto().getTechnology();
		Poly [] polys = tech.getShapeOfArc(ai);
		int total = polys.length;
		for (int j = 0; j < total; j++)
		{
			// generate a polygon
			Poly poly = polys[j];

			// transform the polygon
			poly.transform(trans);

			// draw the polygon
			Point2D [] points = poly.getPoints();
			if (points[0].getX() == points[1].getX())
			{
				drawPoly(poly, region, VERTLAYER);
			} else
			{
				if (points[0].getY() == points[1].getY())
					drawPoly(poly, region, HORILAYER); else
						drawPoly(poly, region, ALLLAYERS);
			}
		}
	}

	private SRPORT addPort(SRNET net, int layers, double cX, double cY, PortInst pi)
	{
		SRPORT port = new SRPORT();
		port.cX = cX;
		port.cY = cY;
		port.lx = (int)cX;   port.hx = (int)cX;
		port.ly = (int)cY;   port.hy = (int)cY;
		port.layers = layers;
		port.wavefront = null;

		for (int index = 0, mask = 1; index < SRMAXLAYERS; index++, mask = mask<<1)
		{
			if (layers != 0 & mask != 0 && net.region.layers[index] != null)
			{
				setBox(net.region.layers[index], SR_GPORT | SR_GSET,
					port.lx, port.ly, port.hx, port.hy, true);
			}
		}

		// link into net
		port.next = null;
		port.master = null;
		port.paths = null;
		port.lastpath = null;
		port.net = net;
		port.pi = pi;
		SRPORT lPort = net.ports;
		int index = 0;
		if (lPort == null)
		{
			net.ports = port;
		} else
		{
			index = 1;
			while (lPort.next != null) { index++;   lPort = lPort.next; }
			lPort.next = port;
		}
		port.index = index;
		return port;
	}

	private int determineDir(NodeInst ni, double cX, double cY)
	{
		if (ni == null) return 3;

		// get the center of the NODEINST
		double nCX = ni.getTrueCenterX();
		double nCY = ni.getTrueCenterY();

		// center, all edges
		if (nCX == cX && nCY == cY) return 3; // all layers
		double dX = ni.getBounds().getMaxX() - nCX;
		double dY = ni.getBounds().getMaxY() - nCY;
		double pDX = Math.abs(cX - nCX);
		double pDY = Math.abs(cY - nCY);

		/* consider a point on a triangle, if left/right the seq center, port,
		 * upper left/right edge will be counter-clockwise, if top/bottom the seq.
		 * will be clock-wise :
		 * x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1 == abs(area)
		 * where area < 0 == clockwise, area > 0 == counter-clockwise
		 */
		double area = pDX * dY - pDY * dX;

		if (area > 0.0) return 1;		// horizontal
		if (area < 0.0) return 2;		// vertical
		return 3;						// corner, all layers
	}

	/**
	 * routing definition functions
	 */
	private SRNET addNet(SRREGION region, Network eNet)
	{
		SRNET srNet = new SRNET();

		srNet.routed = false;
		srNet.eNet = eNet;
		srNet.ports = null;
		srNet.paths = null;
		srNet.lastpath = null;
		srNet.region = region;

		// link into region list
		srNet.next = region.nets;
		region.nets = srNet;

		return srNet;
	}

	/**
	 * Method to write polys into the maze buffer.
	 */
	private void drawPoly(Poly obj, SRREGION region, int layer)
	{
		// now draw the polygon
		if (obj.getLayer() != mazeVertLayer && obj.getLayer() != mazeHorizLayer) return;
		Point2D [] points = obj.getPoints();
		if (obj.getStyle() == Poly.Type.CIRCLE || obj.getStyle() == Poly.Type.THICKCIRCLE || obj.getStyle() == Poly.Type.DISC)
		{
			double radius = points[0].distance(points[1]);
			Rectangle2D circleBounds = new Rectangle2D.Double(points[0].getX()-radius, points[0].getY()-radius, radius*2, radius*2);
			drawBox(circleBounds, layer, region);
			return;
		}
		if (obj.getStyle() == Poly.Type.CIRCLEARC || obj.getStyle() == Poly.Type.THICKCIRCLEARC)
		{
			// arcs at [i] points [1+i] [2+i] clockwise
			if (points.length == 0) return;
			if ((points.length % 3) != 0) return;
			for (int i = 0; i < points.length; i += 3)
			{
				Point2D si = GenMath.computeArcCenter(points[i], points[i+1], points[i+2]);
				drawLine(points[i+1], si, layer, region);
				drawLine(si, points[i+2], layer, region);
			}
			return;
		}

		if (obj.getStyle() == Poly.Type.FILLED || obj.getStyle() == Poly.Type.CLOSED)
		{
			Rectangle2D objBounds = obj.getBox();
			if (objBounds != null)
			{
				drawBox(objBounds, layer, region);
				return;
			}
			for (int i = 1; i < points.length; i++)
				drawLine(points[i-1], points[i], layer, region);

			// close the region
			if (points.length > 2)
				drawLine(points[points.length-1], points[0], layer, region);
			return;
		}

		if (obj.getStyle() == Poly.Type.OPENED || obj.getStyle() == Poly.Type.OPENEDT1 ||
			obj.getStyle() == Poly.Type.OPENEDT1 || obj.getStyle() == Poly.Type.OPENEDT3)
		{
			Rectangle2D objBounds = obj.getBox();
			if (objBounds != null)
			{
				drawBox(objBounds, layer, region);
				return;
			}

			for (int i = 1; i < points.length; i++)
				drawLine(points[i-1], points[i], layer, region);
			return;
		}

		if (obj.getStyle() == Poly.Type.VECTORS)
		{
			for (int i = 1; i < points.length; i += 2)
				drawLine(points[i-1], points[i], layer, region);
			return;
		}
	}

	private void drawBox(Rectangle2D box, int layer, SRREGION region)
	{
		int lX = (int)Math.floor(box.getMinX()-mazeBloat);
		int hX = (int)Math.ceil(box.getMaxX()+mazeBloat);
		int lY = (int)Math.floor(box.getMinY()-mazeBloat);
		int hY = (int)Math.ceil(box.getMaxY()+mazeBloat);
		if (layer == HORILAYER || layer == ALLLAYERS)
			setBox(region.layers[HORILAYER], SR_GSET, lX, lY, hX, hY, false);
		if (layer == VERTLAYER || layer == ALLLAYERS)
			setBox(region.layers[VERTLAYER], SR_GSET, lX, lY, hX, hY, false);
	}

	private void drawLine(Point2D from, Point2D to, int layer, SRREGION region)
	{
		double wX1 = from.getX();
		double wY1 = from.getY();
		double wX2 = to.getX();
		double wY2 = to.getY();
		if (layer == HORILAYER || layer == ALLLAYERS)
			setLine(region.layers[HORILAYER], SR_GSET, wX1, wY1, wX2, wY2, false);
		if (layer == VERTLAYER || layer == ALLLAYERS)
			setLine(region.layers[VERTLAYER], SR_GSET, wX1, wY1, wX2, wY2, false);
	}

	private void setLine(SRLAYER layer, int type, double wX1, double wY1, double wX2, double wY2, boolean orMode)
	{
		// convert to grid coordinates
		int [] x = new int[2];
		int [] y = new int[2];
		x[0] = getGridX((int)wX1, layer);   x[1] = getGridX((int)wX2, layer);
		y[0] = getGridY((int)wY1, layer);   y[1] = getGridY((int)wY2, layer);
		int lx = 1, hx = 0;
		if (wX1 < wX2) { lx = 0; hx = 1; }
		int ly = 1, hy = 0;
		if (wY1 < wY2) { ly = 0; hy = 1; }

		// do obvious clip if completely outside of an edge
		if (x[hx] < 0 || x[lx] >= layer.wid || y[hy] < 0 || y[ly] >= layer.hei) return;

		// clip x
		if (x[lx] < 0)
		{
			y[lx] -= (y[hx] - y[lx]) * x[lx] / (x[hx] - x[lx]);
			x[lx] = 0;
		}
		if (x[hx] >= layer.wid)
		{
			y[hx] -= (y[hx] - y[lx]) * (x[hx] - (layer.wid-1)) / (x[hx] - x[lx]);
			x[hx] = layer.wid - 1;
		}

		// now clip y
		if (y[ly] < 0)
		{
			x[ly] -= (x[hy] - x[ly]) * y[ly] / (y[hy] - y[ly]);
			y[ly] = 0;
		}
		if (y[hy] >= layer.hei)
		{
			x[hy] -= (x[hy] - x[ly]) * (y[hy] - (layer.hei - 1)) / (y[hy] - y[ly]);
			y[hy] = layer.hei - 1;
		}

		// use Bresenham's algorithm to set intersecting grid points
		int dX = x[hx] - x[lx];