maze.java

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

		int dY = y[hy] - y[ly];
		if (dY < dX)
		{
			// for 0 <= dY <= dX
			int e = (dY<<1) - dX;
			int yi = y[lx];
			int diff = 1;
			if (y[hx] < y[lx]) diff = -1;
			for (int xi = x[lx]; xi <= x[hx]; xi++)
			{
				setPoint(layer, type, xi, yi, orMode);
				if (e > 0)
				{
					yi += diff;
					e = e + (dY<<1) - (dX<<1);
				} else e = e + (dY<<1);
			}
		} else
		{
			// for 0 <= dX < dY
			int e = (dX<<1) - dY;
			int xi = x[ly];
			int diff = 1;
			if (x[hy] < x[ly]) diff = -1;
			for (int yi = y[ly]; yi <= y[hy]; yi++)
			{
				setPoint(layer, type, xi, yi, orMode);
				if (e > 0)
				{
					xi += diff;
					e = e + (dX<<1) - (dY<<1);
				} else e = e + (dX<<1);
			}
		}
	}

	private void setBox(SRLAYER layer, int type, int wX1, int wY1, int wX2, int wY2, boolean orMode)
	{
		int lX = getGridX(wX1, layer);   int lY = getGridY(wY1, layer);
		int hX = getGridX(wX2, layer);   int hY = getGridY(wY2, layer);
		if (lX > hX) { int x = lX; lX = hX; hX = x; }
		if (lY > hY) { int y = lY; lY = hY; hY = y; }

		if (hX < 0 || lX >= layer.wid || hY < 0 || lY >= layer.hei) return;

		// clip (simple orthogonal)
		if (lX < 0) lX = 0;
		if (hX >= layer.wid) hX = layer.wid - 1;
		if (lY < 0) lY = 0;
		if (hY >= layer.hei) hY = layer.hei - 1;

		// now fill the box
		for (int x = lX; x <= hX; x++)
			for (int y = lY; y <= hY; y++)
				setPoint(layer, type, x, y, orMode);
	}

	/**
	 * drawing function
	 */
	private void setPoint(SRLAYER layer, int type, int x, int y, boolean orMode)
	{
		if (orMode)
		{
			layer.grids[x][y] |= type;
			layer.vused[x] |= type;
			layer.hused[y] |= type;
		} else
		{
			layer.grids[x][y] = (byte)type;
			layer.vused[x] = (byte)type;
			layer.hused[y] = (byte)type;
		}
	}

	/** general control commands */
	private SRREGION getRegion(int wLX, int wLY, int wHX, int wHY)
	{
		if (wLX > wHX || wLY > wHY) return null;

		if (theRegion == null)
		{
			theRegion = new SRREGION();
			for (int index = 0; index < SRMAXLAYERS; index++)
				theRegion.layers[index] = null;
			theRegion.nets = null;
		} else
		{
			cleanoutRegion(theRegion);
		}

		// now set bounds
		theRegion.lx = wLX;
		theRegion.hx = wHX;
		theRegion.ly = wLY;
		theRegion.hy = wHY;

		SRLAYER hlayer = addLayer(theRegion, HORILAYER, SRHORIPREF);
		if (hlayer == null)
		{
			System.out.println("Could not allocate horizontal layer");
			return null;
		}
		SRLAYER vlayer = addLayer(theRegion, VERTLAYER, SRVERTPREF);
		if (vlayer == null)
		{
			System.out.println("Could not allocate vertical layer");
			return null;
		}

		return theRegion;
	}

	private void cleanoutRegion(SRREGION region)
	{
		region.nets = null;
	}

	private SRLAYER addLayer(SRREGION region, int index, SRDIRECTION direction)
	{
		// check for common index
		SRLAYER layer = region.layers[index];
		if (layer == null)
		{
			// allocate and initialize the layer
			layer = new SRLAYER();
			region.layers[index] = layer;
			layer.grids = null;
			layer.vused = null;
			layer.hused = null;
		}

		layer.index = index;
		layer.mask = 1<<index;
		layer.dir = direction;

		// determine the actual bounds of the world
		// round low bounds up, high bounds down
		int lX = region.lx - 1;
		int lY = region.ly - 1;
		int hX = region.hx + 1;
		int hY = region.hy + 1;

		// translate the region lx, ly into grid units
		layer.wid = (hX - lX) + 1;
		layer.hei = (hY - lY) + 1;
		layer.transx = lX;
		layer.transy = lY;

		// sensibility check
		if (layer.wid > MAXGRIDSIZE || layer.hei > MAXGRIDSIZE)
		{
			System.out.println("This route is too large to solve (limit is " + MAXGRIDSIZE + "x" + MAXGRIDSIZE +
				" grid, this is " + layer.wid + "x" + layer.hei + ")");
			return null;
		}

		// check that the hx, hy of grid is in bounds of region
		if (getWorldX(layer.wid - 1, layer) > region.hx) layer.wid--;
		if (getWorldY(layer.hei - 1, layer) > region.hy) layer.hei--;

		// now allocate a grid array
		layer.grids = new byte[layer.wid][];
		layer.vused = new byte[layer.wid];
		for (int x = 0; x < layer.wid; x++)
		{
			// get address for a column of grid points
			layer.grids[x] = new byte[layer.hei];

			// clear all points
			for (int y = 0; y < layer.hei; y++)
				layer.grids[x][y] = 0;

			// clear the V-used flags
			layer.vused[x] = 0;
		}

		// clear the H-used flags
		layer.hused = new byte[layer.hei];
		for (int y = 0; y < layer.hei; y++) layer.hused[y] = 0;

		// set up/down pointers
		layer.up = layer.down = null;
		if (index != 0)
		{
			SRLAYER alayer = region.layers[index-1];
			if (alayer != null)
			{
				layer.down = alayer;
				alayer.up = layer;
			}
		}
		if (index < SRMAXLAYERS - 1)
		{
			SRLAYER alayer = region.layers[index+1];
			if (alayer != null)
			{
				layer.up = alayer;
				alayer.down = layer;
			}
		}

		return layer;
	}

	private int getGridX(int Mv, SRLAYER Ml) { return Mv - Ml.transx; }

	private int getGridY(int Mv, SRLAYER Ml) { return Mv - Ml.transy; }

	private int getWorldX(int Mv, SRLAYER Ml) { return Mv + Ml.transx; }

	private int getWorldY(int Mv, SRLAYER Ml) { return Mv + Ml.transy; }

	/************************************* CODE TO CREATE RESULTS IN THE CIRCUIT *************************************/

	/**
	 * routing grid database methods
	 */
	private boolean extractPaths(Cell parent, SRNET net)
	{
		// adjust paths to account for precise port location
		double fX = 0, fY = 0;
		for (SRPATH path = net.paths; path != null; path = path.next)
		{
			if (path.type == SRPFIXED) continue;
			SRPORT port = path.port;
			fX = path.wx[0];   fY = path.wy[0];
			double oFX = fX, oFY = fY;
			if (path.end[0] && port.pi != null)
			{
//				fX = port.cX;   fY = port.cY;
//				if (fX != oFX || fY != oFY)
//				{
//					adjustPath(net.paths, path, 0, fX-oFX, fY-oFY);
//				}
				Poly portPoly = port.pi.getPoly();
				Point2D closest = portPoly.closestPoint(new Point2D.Double(fX, fY));
				if (closest.getX() != oFX || closest.getY() != oFY)
					adjustPath(net.paths, path, 0, closest.getX()-oFX, closest.getY()-oFY);
			} else
			{
				ArcProto ap = path.layer.index != 0 ? mazeVertWire : mazeHorizWire;
				List<PortInst> portInstList = findPort(parent, fX, fY, ap, net, true);
				if (portInstList.size() > 0)
				{
					PortInst pi = portInstList.get(0);
					Poly portPoly = pi.getPoly();
					Point2D closest = portPoly.closestPoint(new Point2D.Double(fX, fY));
					if (closest.getX() != oFX || closest.getY() != oFY)
						adjustPath(net.paths, path, 0, closest.getX()-oFX, closest.getY()-oFY);
				}
			}

			fX = oFX = path.wx[1];   fY = oFY = path.wy[1];
			if (path.end[1] && port.pi != null)
			{
//				fX = port.cX;   fY = port.cY;
//				if (fX != oFX || fY != oFY)
//				{
//					adjustPath(net.paths, path, 1, fX-oFX, fY-oFY);
//				}
				Poly portPoly = port.pi.getPoly();
				Point2D closest = portPoly.closestPoint(new Point2D.Double(fX, fY));
				if (closest.getX() != oFX || closest.getY() != oFY)
					adjustPath(net.paths, path, 1, closest.getX()-oFX, closest.getY()-oFY);
			} else
			{
				ArcProto ap = path.layer.index != 0 ? mazeVertWire : mazeHorizWire;
				List<PortInst> portInstList = findPort(parent, fX, fY, ap, net, true);
				if (portInstList.size() > 0)
				{
					PortInst pi = portInstList.get(0);
					Poly portPoly = pi.getPoly();
					Point2D closest = portPoly.closestPoint(new Point2D.Double(fX, fY));
					if (closest.getX() != oFX || closest.getY() != oFY)
						adjustPath(net.paths, path, 1, closest.getX()-oFX, closest.getY()-oFY);
				}
			}
		}

		// now do the routing
		for (SRPATH path = net.paths; path != null; path = path.next)
		{
			if (path.type == SRPFIXED) continue;
			ArcProto ap = path.layer.index != 0 ? mazeVertWire : mazeHorizWire;
			SRPORT port = path.port;

			// create arc between the end points
			List<PortInst> fromPortInstList = null;
			fX = path.wx[0];   fY = path.wy[0];
			if (path.end[0] && port.pi != null)
			{
				fromPortInstList = new ArrayList<PortInst>();
				fromPortInstList.add(port.pi);
			} else
			{
				fromPortInstList = findPort(parent, fX, fY, ap, net, false);
				if (fromPortInstList.size() == 0)
				{
					// create the from pin
					double xS = mazeSteinerNode.getDefWidth();
					double yS = mazeSteinerNode.getDefHeight();
					NodeInst ni = NodeInst.makeInstance(mazeSteinerNode, new Point2D.Double(fX, fY), xS, yS, parent);
					if (ni == null)
					{
						System.out.println("Could not create pin");
						return true;
					}
					fromPortInstList.add(ni.getPortInst(0));
				}
			}

			List<PortInst> toPortInstList = null;
			double tX = path.wx[1];   double tY = path.wy[1];
			if (path.end[1] && port.pi != null)
			{
				toPortInstList = new ArrayList<PortInst>();
				toPortInstList.add(port.pi);
			} else
			{
				toPortInstList = findPort(parent, tX, tY, ap, net, false);
				if (toPortInstList.size() == 0)
				{
					// create the from pin
					double xS = mazeSteinerNode.getDefWidth();
					double yS = mazeSteinerNode.getDefHeight();
					NodeInst ni = NodeInst.makeInstance(mazeSteinerNode, new Point2D.Double(tX, tY), xS, yS, parent);
					if (ni == null)
					{
						System.out.println("Could not create pin");
						return true;
					}
					toPortInstList.add(ni.getPortInst(0));
				}
			}

			// now connect (note only nodes for now, no bus like connections)
			if (fromPortInstList.size() > 0 && toPortInstList.size() > 0)
			{
				// now make the connection (simple wire to wire for now)
				PortInst fPi = fromPortInstList.get(0);
				PortInst tPi = toPortInstList.get(0);
				ArcInst ai = ArcInst.makeInstance(ap, fPi, tPi, new Point2D.Double(fX, fY), new Point2D.Double(tX, tY), null);
//				ArcInst ai = ArcInst.makeInstanceFull(ap, ap.getDefaultLambdaFullWidth(), fPi, tPi, new Point2D.Double(fX, fY), new Point2D.Double(tX, tY), null);
				if (ai == null)
				{
					System.out.println("Could not create path (arc)");
					return true;
				}
			}
		}

		return false;
	}

	/**
	 * Method to recursively adjust paths to account for port positions that may not
	 * be on the grid.
	 */
	private void adjustPath(SRPATH paths, SRPATH thisPath, int end, double dX, double dY)
	{
		if (dX != 0)
		{
			double formerThis = thisPath.wx[end];
			double formerOther = thisPath.wx[1-end];
			thisPath.wx[end] += dX;
			if (formerThis == formerOther)
			{
				double formerX = thisPath.wx[1-end];
				double formerY = thisPath.wy[1-end];
				thisPath.wx[1-end] += dX;
				for (SRPATH opath = paths; opath != null; opath = opath.next)
				{
					if (opath.wx[0] == formerX && opath.wy[0] == formerY)
					{
						adjustPath(paths, opath, 0, dX, 0);
						break;
					}
					if (opath.wx[1] == formerX && opath.wy[1] == formerY)
					{
						adjustPath(paths, opath, 1, dX, 0);
						break;
					}
				}
			}
		}

		if (dY != 0)
		{
			double formerThis = thisPath.wy[end];
			double formerOther = thisPath.wy[1-end];
			thisPath.wy[end] += dY;
			if (formerThis == formerOther)
			{
				double formerX = thisPath.wx[1-end];
				double formerY = thisPath.wy[1-end];
				thisPath.wy[1-end] += dY;
				for (SRPATH opath = paths; opath != null; opath = opath.next)
				{
					if (opath.wx[0] == formerX && opath.wy[0] == formerY)
					{
						adjustPath(paths, opath, 0, 0, dY);
						break;
					}
					if (opath.wx[1] == formerX && opath.wy[1] == formerY)
					{
						adjustPath(paths, opath, 1, 0, dY);
						break;
					}
				}
			}
		}
	}

	/**
	 * Method to locate the PortInsts corresponding to
	 * a direct intersection with the given point.
	 * @param cell the cell to search
	 * @param x X coordinate of the point to examine.
	 * @param y Y coordinate of the point to examine.
	 * @param ap the arc used to connect port (must match pp)
	 */
	private List<PortInst> findPort(Cell cell, double x, double y, ArcProto ap, SRNET srnet, boolean forceFind)
	{
		List<PortInst> portInstList = new ArrayList<PortInst>();
		Point2D searchPoint = new Point2D.Double(x, y);
		double bestDist = 0;
		PortInst closestPi = null;
		Rectangle2D searchBounds = new Rectangle2D.Double(x-0.5, y-0.5, 1, 1);
		for(Iterator<RTBounds> sea = cell.searchIterator(searchBounds); sea.hasNext(); )
		{
			RTBounds geom = sea.next();

			if (geom instanceof NodeInst)
			{
				// now locate a portproto
				NodeInst ni = (NodeInst)geom;
				for(Iterator<PortInst> it = ni.getPortInsts(); it.hasNext(); )
				{
					PortInst pi = it.next();
					Poly portPoly = pi.getPoly();
					if (portPoly.isInside(searchPoint))
					{
						// check if port connects to arc ...*/
						if (pi.getPortProto().getBasePort().connectsTo(ap))
						{
							portInstList.add(pi);
						}
					} else
					{
						double dist = portPoly.polyDistance(new Rectangle2D.Double(x, y, 0, 0));

						// LINTED "bestDist" used in proper order
						if (closestPi == null || dist < bestDist)
						{
							bestDist = dist;
							closestPi = pi;
						}