compaction.java

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

		/**
		 * Method finds the minimum distance which is necessary between polygon
		 * "obj" (from object "object" on layer "nLayer" with network connectivity
		 * "nIndex") and the previous line in "line".  It returns the amount
		 * to move this object to get it closest to the line (DEFAULT_VAL if they can
		 * overlap).  The object "reason" is set to the object that is causing the
		 * constraint.
		 */
		private double minSeparate(GeomObj object, Layer nLayer, PolyList nPolys, Line line, Cell cell)
		{
			Poly nPoly = nPolys.poly;
			Technology tech = nPolys.tech;
			int nIndex = nPolys.networkNum;

			// see how far around the box it is necessary to search
			double bound = DRC.getMaxSurround(nLayer, Double.MAX_VALUE);

			// if there is no separation, allow them to sit on top of each other
			if (bound < 0) return DEFAULT_VAL;

			// can only handle orthogonal rectangles for now
			Rectangle2D nbox = nPoly.getBox();
			if (nbox == null) return bound;

			double bestMotion = DEFAULT_VAL;
			double geomLow = object.lowy;
			if (curAxis == Axis.HORIZONTAL) geomLow = object.lowx;

			// search the line
			for(GeomObj curObject = line.firstObject; curObject != null; curObject = curObject.nextObject)
			{
				if (curAxis == Axis.HORIZONTAL)
				{
					if (!isInBound(nbox.getMinY()-bound, nbox.getMaxY()+bound, curObject.outerLowy, curObject.outerHighy)) continue;
				} else
				{
					if (!isInBound(nbox.getMinX()-bound, nbox.getMaxX()+bound, curObject.outerLowx, curObject.outerHighx)) continue;
				}

				// examine every layer in this object
				for(PolyList polys = curObject.firstPolyList; polys != null; polys = polys.nextPolyList)
				{
					// don't check between technologies
					if (polys.tech != tech) continue;

					Poly poly = polys.poly;
					Layer layer = poly.getLayer().getNonPseudoLayer();
					int pIndex = polys.networkNum;

					// see whether the two objects are electrically connected
					boolean con = false;
					if (pIndex == nIndex && pIndex != -1)
					{
						Layer.Function nFun = nLayer.getFunction();
						Layer.Function fun = layer.getFunction();
						if (!nFun.isSubstrate() && !fun.isSubstrate())
							con = true;
					}
					Rectangle2D polyBox = poly.getBox();
					if (polyBox == null)
					{
						double niHigh = curObject.outerHighy;
						if (curAxis == Axis.HORIZONTAL) niHigh = curObject.outerHighx;

						double thisMotion = geomLow - niHigh - bound;
						if (thisMotion == DEFAULT_VAL) continue;
						if (thisMotion < bestMotion || bestMotion == DEFAULT_VAL)
						{
							bestMotion = thisMotion;
						}
						continue;
					}

					// see how close they can get
					double dist = -1;
					DRCTemplate rule = DRC.getSpacingRule(nLayer, null, layer, null, con, -1, 0, 0);
					if (rule != null) dist = rule.getValue(0);
					if (dist < 0) continue;

					/*
					 * special rule for ignoring distance:
					 *   the layers are the same and either:
					 *     they connect and are *NOT* contact layers
					 *   or:
					 *     they don't connect and are implant layers (substrate/well)
					 */
					if (nLayer == layer)
					{
						Layer.Function fun = nLayer.getFunction();
						if (con)
						{
							if (!fun.isContact()) continue;
						} else
						{
							if (fun.isSubstrate()) continue;
						}
					}

					// if the two layers are offset on the axis so that there is no possible contraint between them
					if (curAxis == Axis.HORIZONTAL)
					{
						if (!isInBound(nbox.getMinY()-dist, nbox.getMaxY()+dist, polyBox.getMinY(), polyBox.getMaxY())) continue;
					} else
					{
						if (!isInBound(nbox.getMinX()-dist, nbox.getMaxX()+dist, polyBox.getMinX(), polyBox.getMaxX())) continue;
					}

					// check the distance
					double thisMotion = checkLayers(nLayer, nIndex, object, polyBox, layer, pIndex, curObject, nbox, dist);
					if (thisMotion == DEFAULT_VAL) continue;
					if (thisMotion < bestMotion || bestMotion == DEFAULT_VAL)
					{
						bestMotion = thisMotion;
					}
				}
			}
			return bestMotion;
		}

		/**
		 * Method to see if the object in "object1" on layer "layer1" with electrical
		 * index "index1" comes within "dist" from the object in "object2" on layer
		 * "layer2" with electrical index "index2" in the perpendicular axis to "axis".
		 * The bounds of object "object1" are (lx1-hx1,ly1-hy1), and the bounds of object
		 * "object2" are (lx2-hx2,ly2-hy2).  If the objects are in bounds, the spacing
		 * between them is returned.  Otherwise, DEFAULT_VAL is returned.
		 */
		private double checkLayers(Layer layer1, int index1, GeomObj object1, Rectangle2D bound1,
			Layer layer2, int index2, GeomObj object2, Rectangle2D bound2, double dist)
		{
			// crop out parts of a box covered by a similar layer on the other node
			if (object1.inst instanceof NodeInst)
			{
				if (cropNodeInst(object1.firstPolyList, bound2, layer2, index2))
					return DEFAULT_VAL;
			}
			if (object2.inst instanceof NodeInst)
			{
				if (cropNodeInst(object2.firstPolyList, bound1, layer1, index1))
					return DEFAULT_VAL;
			}

			// now compare the box extents
			if (curAxis == Axis.HORIZONTAL)
			{
				if (bound1.getMaxY()+dist > bound2.getMinY() && bound1.getMinY()-dist < bound2.getMaxY())
				{
					double spacing = bound2.getMinX() - bound1.getMaxX() - dist;
					return spacing;
				}
			} else if (bound1.getMaxX()+dist > bound2.getMinX() && bound1.getMinX()-dist < bound2.getMaxX())
			{
				double spacing = bound2.getMinY() - bound1.getMaxY() - dist;
				return spacing;
			}
			return DEFAULT_VAL;
		}

		/**
		 * Method to crop the box on layer "nLayer", electrical index "nIndex"
		 * and bounds (lx-hx, ly-hy) against the nodeinst "ni".  Only those layers
		 * in the nodeinst that are the same layer and the same electrical index
		 * are checked.  The routine returns true if the bounds are reduced
		 * to nothing.
		 */
		private boolean cropNodeInst(PolyList polys, Rectangle2D bound, Layer nLayer, int nIndex)
		{
			for(PolyList curPoly = polys; curPoly != null; curPoly = curPoly.nextPolyList)
			{
				if (curPoly.networkNum != nIndex) continue;
				if (curPoly.poly.getLayer() != nLayer) continue;
				Rectangle2D polyBox = curPoly.poly.getBox();
				if (polyBox == null) continue;
				int temp = Poly.cropBox(bound, polyBox);
				if (temp > 0) return true;
			}
			return false;
		}

		private boolean isInBound(double ll, double lh, double rl, double rh)
		{
			if (rh > ll && rl < lh) return true;
			return false;
		}

		/**
		 * moves a object of instances distance (movex, movey), and returns a true if
		 * there is actually a move
		 */
		private boolean moveLine(Line line, double moveX, double moveY, boolean change)
		{
			double move = moveX;
			if (moveX == 0) move = moveY;
			if (line == null) return false;
			if (!change && move != 0) change = true;

			for(GeomObj curObject = line.firstObject; curObject != null; curObject = curObject.nextObject)
			{
				if (curObject.inst instanceof NodeInst)
				{
					NodeInst ni = (NodeInst)curObject.inst;
					ni.move(-moveX, -moveY);
					break;
				}
			}

			for(GeomObj curObject = line.firstObject; curObject != null; curObject = curObject.nextObject)
			{
				curObject.lowx -= moveX;
				curObject.highx -= moveX;
				curObject.lowy -= moveY;
				curObject.highy -= moveY;

				curObject.outerLowx -= moveX;
				curObject.outerHighx -= moveX;
				curObject.outerLowy -= moveY;
				curObject.outerHighy -= moveY;
				for(PolyList polys = curObject.firstPolyList; polys != null; polys = polys.nextPolyList)
				{
					Point2D [] points = polys.poly.getPoints();
					for(int i=0; i<points.length; i++)
					{
						polys.poly.setPoint(i, points[i].getX() - moveX, points[i].getY() - moveY);
					}
				}
			}
			line.high -= move;
			line.low -= move;
			return change;
		}

		/**
		 * Method to find least low of the line.
		 * re-set first line low in the list
		 * finds the smallest low value (lowx for VERTICAL, lowy for HORIZ case)
		 * stores it in line->low.
		 */
		private double findLeastLow(Line line)
		{
			if (line == null) return 0;

			// find smallest low for the each object
			boolean first = true;
			double low = 0;
			for(GeomObj curObject = line.firstObject; curObject != null; curObject = curObject.nextObject)
			{
				if (!(curObject.inst instanceof NodeInst)) continue;
				double thisLow = curObject.lowy;
				if (curAxis == Axis.HORIZONTAL) thisLow = curObject.lowx;

				if (!first) low = Math.min(low, thisLow); else
				{
					low = thisLow;
					first = false;
				}
			}
			line.low = low;
			return low;
		}

		/**
		 * Method to temporarily make all arcs in fixline rigid and those
		 * in nfixline nonrigid in order to move fixline over
		 */
		private void setupTemporaryRigidity(Line fixLine, Line lineStretch)
		{
			for(Line curLine = fixLine; curLine != null; curLine = curLine.nextLine)
			{
				for(GeomObj curObject = curLine.firstObject; curObject != null; curObject = curObject.nextObject)
				{
					if (!(curObject.inst instanceof NodeInst))    // arc rigid
					{
						Layout.setTempRigid((ArcInst)curObject.inst, true);
					}
				}
			}
			for(Line curLine = lineStretch; curLine != null; curLine = curLine.nextLine)
			{
				for(GeomObj curObject = curLine.firstObject; curObject != null; curObject = curObject.nextObject)
				{
					if (!(curObject.inst instanceof NodeInst))   // arc unrigid
					{
						Layout.setTempRigid((ArcInst)curObject.inst, false);
					}
				}
			}
		}

		/**
		 * set the CANTSLIDE bit of userbits for each object in line so that this
		 * line will not slide.
		 */
		private HashSet<ArcInst> ensureSlidability(Line line)
		{
			HashSet<ArcInst> clearedArcs = new HashSet<ArcInst>();
			for(Line curLine = line; curLine != null; curLine = curLine.nextLine)
			{
				for(GeomObj curObject = curLine.firstObject; curObject != null;
				curObject = curObject.nextObject)
				{
					if (!(curObject.inst instanceof NodeInst))
					{
						ArcInst ai = (ArcInst)curObject.inst;
						if (ai.isSlidable())
						{
							ai.setSlidable(false);
							clearedArcs.add(ai);
						}
					}
				}
			}
			return clearedArcs;
		}

		/**
		 * restore the CANTSLIDE bit of userbits for each object in line
		 */
		private void restoreSlidability(HashSet<ArcInst> clearedArcs)
		{
			for(ArcInst ai : clearedArcs)
			{
				ai.setSlidable(true);
			}
		}

		private void computeLineHiAndLow(Line line)
		{
			// find smallest and highest vals for the each object
			boolean first = true;
			double lx = 0, hx = 0, ly = 0, hy = 0;
			for(GeomObj curObject = line.firstObject; curObject != null; curObject = curObject.nextObject)
			{
				if (!(curObject.inst instanceof NodeInst)) continue;
				if (first)
				{
					lx = curObject.outerLowx;
					hx = curObject.outerHighx;
					ly = curObject.outerLowy;
					hy = curObject.outerHighy;
					first = false;
				} else
				{
					if (curObject.outerLowx < lx) lx = curObject.outerLowx;
					if (curObject.outerHighx > hx) hx = curObject.outerHighx;
					if (curObject.outerLowy < ly) ly = curObject.outerLowy;
					if (curObject.outerHighy > hy) hy = curObject.outerHighy;
				}
			}
			if (curAxis == Axis.HORIZONTAL)
			{
				line.low = lx;
				line.high = hx;
			} else
			{
				line.low = ly;
				line.high = hy;
			}
		}

		/**
		 * Method to sort line by center val from least to greatest
		 */
		private Line sortLines(Line line)
		{
			if (line == null)
			{
				System.out.println("Error: sortLines called with null argument");
				return null;
			}

			// first figure out the weighting factor that will be sorted
			for(Line curLine = line; curLine != null; curLine = curLine.nextLine)
			{
				double ave = 0, totalLen = 0;
				for(GeomObj curObject = curLine.firstObject; curObject != null; curObject = curObject.nextObject)
				{
					double ctr = 0;
					if (curAxis == Axis.HORIZONTAL)
					{
						ctr = (curObject.lowx+curObject.highx) / 2;
					} else
					{
						ctr = (curObject.lowy+curObject.highy) / 2;
					}
					totalLen++;
					ave += ctr;
				}
				if (totalLen != 0) ave /= totalLen;
				curLine.val = ave;
			}

			// now sort on the "val" field
			Line newLine = null;
			for(;;)
			{
				if (line == null) break;
				boolean first = true;
				double bestVal = 0;
				Line bestLine = null;
				for(Line curLine = line; curLine != null; curLine = curLine.nextLine)
				{
					if (first)
					{
						bestVal = curLine.val;
						bestLine = curLine;
						first = false;
					} else if (curLine.val > bestVal)
					{
						bestVal = curLine.val;
						bestLine = curLine;
					}
				}

				// remove bestLine from the list
				if (bestLine.prevLine == null) line = bestLine.nextLine; else
					bestLine.prevLine.nextLine = bestLine.nextLine;
				if (bestLine.nextLine != null)
					bestLine.nextLine.prevLine = bestLine.prevLine;

				// insert at the start of this list
				if (newLine != null) newLine.prevLine = bestLine;
				bestLine.nextLine = newLine;
				bestLine.prevLine = null;