maze.java

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

		}

		// remove marked networks
		for(ArcInst ai : arcsToDelete)
		{
			ai.kill();
		}
        cell.killNodes(nodesToDelete);

		return false;
	}

	/************************************* CODE TO TRAVERSE THE MAZE BUFFER *************************************/

	private boolean routeANet(SRNET net)
	{
		// initialize all layers and ports for this route
		boolean ret = false;
		for (int index = 0; index < SRMAXLAYERS; index++)
		{
			SRLAYER layer = net.region.layers[index];
			if (layer != null)
			{
				// unused bounds
				layer.lx = layer.wid; layer.hx = -1;
				layer.ly = layer.hei; layer.hy = -1;

				// now set the vertical and horizontal preference
				int count = 0;
				for (int x = 0; x < layer.wid; x++)
				{
					if ((layer.vused[x] & SR_GSET) != 0)
					{
						if (count != 0)
						{
							for (int i = 1, prio = count>>1; i <= count; i++, prio--)
								layer.vused[x-i] = (byte)Math.abs(prio);
							count = 0;
						}
					} else count++;
				}

				// get the remainder
				if (count != 0)
				{
					for (int i = 1, prio = count>>1; i < count; i++)
					{
						layer.vused[layer.wid-i] = (byte)Math.abs(prio);
						if (--prio == 0 && (count&1) == 0) prio = -1;
					}
				}

				// now horizontal tracks
				count = 0;
				for (int y = 0; y < layer.hei; y++)
				{
					if ((layer.hused[y] & SR_GSET) != 0)
					{
						if (count != 0)
						{
							for (int i = 1, prio = count>>1; i <= count; i++, prio--)
								layer.hused[y-i] = (byte)Math.abs(prio);
							count = 0;
						}
					} else count++;
				}

				// and the remainder ...
				if (count != 0)
				{
					for (int i = 1, prio = count>>1; i < count; i++)
					{
						layer.hused[layer.hei-i] = (byte)Math.abs(prio);
						if (--prio == 0 && (count&1) == 0) prio = -1;
					}
				}
			}
		}

		// prepare each port for routing
		int pCount = 0;
		for (SRPORT port = net.ports; port != null; port = port.next, pCount++)
		{
			createWavefront(port);
		}

		// now begin routing until all ports merged
		int code = SR_GSTART;
		do
		{
			if (++code > SR_GMAX) code = SR_GSTART;
			int blocked = 0;
			int status = 0;
			SRPORT port = null;
			for (port = net.ports; port != null; port = port.next)
			{
				// if part of other wavefront, get the next one
				if (port.master != null) continue;

				// expand the wavefront
				status = expandWavefront(port, code);
				if (status == SRERROR) return true;
				if (status == SRROUTED) break;
				if (status == SRBLOCKED) blocked++;
			}

			// check for successful routing
			if (port != null && status == SRROUTED)
			{
				// now clear routing region and restart expansion
				clearMaze(net);
				if (--pCount > 1)
				{
					// prepare each port for routing
					for (port = net.ports; port != null; port = port.next)
						createWavefront(port);
				}
				code = SR_GSTART;
			} else
			{
				// check for blocked net
				if (blocked == pCount)
				{
					ret = true;
					clearMaze(net);
					break;
				}
			}
		} while (pCount > 1);

		// move all the port paths to the net
		for (SRPORT port = net.ports; port != null; port = port.next)
		{
			if (net.lastpath == null)
			{
				net.paths = port.paths;
				if (net.paths != null) net.lastpath = port.lastpath;
			} else
			{
				net.lastpath.next = port.paths;
				if (net.lastpath.next != null) net.lastpath = port.lastpath;
			}
			port.paths = null;
			port.lastpath = null;
		}
		if (!ret) net.routed = true;
		return ret;
	}

	private void createWavefront(SRPORT port)
	{
		SRPORT master = port.master;
		if (master == null) master = port;

		// first assign each layer of the port as wavefront points
		for (int index = 0, mask = 1; index < SRMAXLAYERS; index++, mask = mask<<1)
		{
			if ((mask & port.layers) != 0)
			{
				SRLAYER layer = port.net.region.layers[index];
				if (layer == null) continue;

				// convert to grid points
				int lx = getGridX(port.lx, layer);   int ly = getGridY(port.ly, layer);
				int hx = getGridX(port.hx, layer);   int hy = getGridY(port.hy, layer);
				if (lx >= layer.wid || hx < 0 || ly >= layer.hei || hy < 0) continue;

				// clip to window
				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;

				/*
				 * added detection of immediate blockage ... smr
				 */
				boolean onEdge = false;
				for (int x = lx; x <= hx; x++)
				{
					for (int y = ly; y <= hy; y++)
					{
						addWavePoint(master, layer, x, y, SR_GSTART);
						if (x < layer.wid-1 && layer.grids[x+1][y] == 0) onEdge = true;
						if (x > 0 && layer.grids[x-1][y] == 0) onEdge = true;
						if (y < layer.hei-1 && layer.grids[x][y+1] == 0) onEdge = true;
						if (y > 0 && layer.grids[x][y-1] == 0) onEdge = true;
					}
				}
				if (!onEdge)
				{
					// port is inside of blocked area: search for opening
					int cx = (lx + hx) / 2;
					int cy = (ly + hy) / 2;
					PrimitivePort prP = port.pi.getPortProto().getBasePort();
					int angRange = prP.getAngleRange();
					int ang = prP.getAngle();
					NodeInst ni = port.pi.getNodeInst();
					ang += (ni.getAngle()+5) / 10;
					if (ni.isMirroredAboutXAxis() != ni.isMirroredAboutYAxis()) { ang = 270 - ang; if (ang < 0) ang += 360; }
					if (angleDiff(ang, 0) <= angRange)
					{
						// port faces right
						for(int spread=1; spread<BLOCKAGELIMIT; spread++)
						{
							if (hx+spread >= layer.wid) break;
							if (layer.grids[hx+spread][cy] == 0) { onEdge = true;   break; }
							layer.grids[hx+spread][cy] = 0;
						}
					}
					if (angleDiff(ang, 90) <= angRange)
					{
						// port faces up
						for(int spread=1; spread<BLOCKAGELIMIT; spread++)
						{
							if (hy+spread >= layer.hei) break;
							if (layer.grids[cx][hy+spread] == 0) { onEdge = true;   break; }
							layer.grids[cx][hy+spread] = 0;
						}
					}
					if (angleDiff(ang, 180) <= angRange)
					{
						// port faces left
						for(int spread=1; spread<BLOCKAGELIMIT; spread++)
						{
							if (lx-spread < 0) break;
							if (layer.grids[lx-spread][cy] == 0) { onEdge = true;   break; }
							layer.grids[lx-spread][cy] = 0;
						}
					}
					if (angleDiff(ang, 270) <= angRange)
					{
						// port faces down
						for(int spread=1; spread<BLOCKAGELIMIT; spread++)
						{
							if (ly-spread < 0) break;
							if (layer.grids[cx][ly-spread] == 0) { onEdge = true;   break; }
							layer.grids[cx][ly-spread] = 0;
						}
					}
					if (!onEdge)
					{
						System.out.println("Node " + ni.describe(false) + ", port " +
							port.pi.getPortProto().getName() + " is blocked");
						return;
					}
				}
			}
		}

		// now assign the paths of the port
		for (SRPATH path = port.paths; path != null; path = path.next)
		{
			// note paths are always in the working area
			if (path.x[0] == path.x[1])
			{
				// vertical path
				int dy = -1;
				if (path.y[0] < path.y[1]) dy = 1;
				for (int x = path.x[0], y = path.y[0];
					(dy < 0) ? y >= path.y[1] : y <= path.y[1]; y += dy)
				{
					addWavePoint(master, path.layer, x, y, SR_GSTART);
				}
			} else if (path.y[0] == path.y[1])
			{
				// horizontal path
				int dx = -1;
				if (path.x[0] < path.x[1]) dx = 1;
				for (int y = path.y[0], x = path.x[0];
					(dx < 0) ? x >= path.x[1] : x <= path.x[1]; x += dx)
				{
					addWavePoint(master, path.layer, x, y, SR_GSTART);
				}
			} else
			{
				// a 45 degree path, note assume x,y difference is equal
				int dx = -1;
				if (path.x[0] < path.x[1]) dx = 1;
				int dy = -1;
				if (path.y[0] < path.y[1]) dy = 1;

				for (int x = path.x[0], y = path.y[0];
					(dx < 0) ? x >= path.x[1] : x <= path.x[1]; x += dx, y += dy)
				{
					addWavePoint(master, path.layer, x, y, SR_GSTART);
				}
			}
		}
	}

	/**
	 * routing commands
	 */
	private void addWavePoint(SRPORT port, SRLAYER layer, int x, int y, int code)
	{
		SRWAVEPT wavePt = new SRWAVEPT();
		wavePt.x = x;
		wavePt.y = y;

		// set the grid
		layer.grids[x][y] = (byte)((layer.grids[x][y] & ~SR_GMASK) | code | SR_GWAVE);
		wavePt.layer = layer;

		// set maze bounds
		if (layer.lx > x) layer.lx = x;
		if (layer.hx < x) layer.hx = x;
		if (layer.ly > y) layer.ly = y;
		if (layer.hy < y) layer.hy = y;

		wavePt.prev = null;
		if (port.master != null)
		{
			wavePt.port = port.master;
			wavePt.next = port.master.wavefront;
			port.master.wavefront = wavePt;
		} else
		{
			wavePt.port = port;
			wavePt.next = port.wavefront;
			port.wavefront = wavePt;
		}
		if (wavePt.next != null)
			wavePt.next.prev = wavePt;
	}

	private int angleDiff(int ang1, int ang2)
	{
		int diff = Math.abs(ang1 - ang2);
		if (diff > 180) diff = 360 - diff;
		return diff;
	}

	private int expandWavefront(SRPORT port, int code)
	{
		// begin expansion of all wavepts
		// disconnect wavepts from the port
		SRWAVEPT wavePt = port.wavefront;
		if (wavePt == null) return SRBLOCKED;

		SRWAVEPT next = null;
		int status = SRSUCCESS;
		boolean found = false;
		int bx = 0, by = 0;
		SRLAYER bLayer = null;
		SRWAVEPT bWavePt = new SRWAVEPT();
		for (wavePt = port.wavefront; wavePt != null ; wavePt = next)
		{
			boolean connected = false;
			SRLAYER layer = wavePt.layer;
			if (layer.dir == SRALL || layer.dir == SRHORIPREF)
			{
				// try horizontal route
				int x = wavePt.x + 1;
				if (x != layer.wid)
				{
					status = examinePoint(port, layer, x, wavePt.y, code);
					if (status == SRROUTED)
					{
						// "bWavePt" used in proper order
						if (!found || (layer.hused[bWavePt.y] & SR_GSET) != 0 ||
							((layer.hused[wavePt.y] & SR_GSET) == 0 &&
							layer.hused[wavePt.y] < layer.hused[bWavePt.y]))
						{
							bWavePt.x = wavePt.x;   bWavePt.y = wavePt.y;   
							bWavePt.layer = wavePt.layer;   bWavePt.port = wavePt.port;
							bx = x;  by = wavePt.y;
							bLayer = layer;
						}
						found = true;
						connected = true;
					}
				}
				if (!connected && (x = wavePt.x - 1) >= 0)
				{
					status = examinePoint(port, layer, x, wavePt.y, code);
					if (status == SRROUTED)
					{
						if (!found ||
							(layer.hused[bWavePt.y] & SR_GSET) != 0  ||
							((layer.hused[wavePt.y] & SR_GSET) == 0 &&
							layer.hused[wavePt.y] < layer.hused[bWavePt.y]))
						{
							bWavePt.x = wavePt.x;   bWavePt.y = wavePt.y;   
							bWavePt.layer = wavePt.layer;   bWavePt.port = wavePt.port;
							bx = x; by = wavePt.y;
							bLayer = layer;
						}
						found = true;
						connected = true;
					}
				}
			}
			if (layer.dir == SRALL || layer.dir == SRVERTPREF)
			{
				// try vertical route
				int y = wavePt.y + 1;
				if (!connected && y != layer.hei)
				{
					status = examinePoint(port, layer, wavePt.x, y, code);
					if (status == SRROUTED)
					{
						if (!found ||
							(layer.vused[bWavePt.x] & SR_GSET) != 0  ||
							((layer.vused[wavePt.x] & SR_GSET) == 0 &&
							layer.vused[wavePt.x] < layer.vused[bWavePt.x]))
						{
							bWavePt.x = wavePt.x;   bWavePt.y = wavePt.y;   
							bWavePt.layer = wavePt.layer;   bWavePt.port = wavePt.port;
							bx = wavePt.x; by = y;
							bLayer = layer;
						}
						found = true;
						connected = true;
					}
				}
				if (!connected && (y = wavePt.y - 1) >= 0)
				{
					status = examinePoint(port, layer, wavePt.x, y, code);
					if (status == SRROUTED)
					{
						if (!found ||
							(layer.vused[bWavePt.x] & SR_GSET) != 0  ||
							((layer.vused[wavePt.x] & SR_GSET) == 0 &&
							layer.vused[wavePt.x] < layer.vused[bWavePt.x]))
						{
							bWavePt.x = wavePt.x;   bWavePt.y = wavePt.y;   
							bWavePt.layer = wavePt.layer;   bWavePt.port = wavePt.port;
							bx = wavePt.x; by = y;
							bLayer = layer;
						}
						found = true;
						connected = true;
					}
				}
			}
			if (!connected && layer.up != null)
			{
				// try via up
				status = examinePoint(port, layer.up, wavePt.x, wavePt.y, code);
				if (status == SRROUTED)
				{
					if (!found)
					{
						bWavePt.x = wavePt.x;   bWavePt.y = wavePt.y;   
						bWavePt.layer = wavePt.layer;   bWavePt.port = wavePt.port;
						bx = wavePt.x; by = wavePt.y;
						bLayer = layer.up;
					}
					found = true;
					connected = true;
				}
			}
			if (!connected && layer.down != null)
			{
				// try via down
				status = examinePoint(port, layer.down, wavePt.x, wavePt.y, code);
				if (status == SRROUTED)
				{
					if (!found)
					{
						bWavePt.x = wavePt.x;   bWavePt.y = wavePt.y;