compaction.java

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

				newLine = bestLine;
			}
			return newLine;
		}

		/**
		 * create a new line with the element object and add it to the beginning of
		 * the given line
		 */
		private Line makeObjectLine(Line line, List<GeomObj> objectList)
		{
			Line newLine = new Line();
			newLine.nextLine = line;
			newLine.prevLine = null;
			newLine.firstObject = null;
			GeomObj lastObject = null;
			for(GeomObj gO : objectList)
			{
				if (lastObject == null) newLine.firstObject = gO; else
					lastObject.nextObject = gO;
				lastObject = gO;
			}
			if (line != null) line.prevLine = newLine;
			return newLine;
		}

		private void createObjects(NodeInst ni, List<GeomObj> thisObject, List<GeomObj> otherObject, HashSet<NodeInst> nodesSeen,
			HashMap<ArcInst,Integer> arcIndices, HashMap<PortProto,Integer> portIndices)
		{
			// if node has already been examined, quit now
			if (nodesSeen.contains(ni)) return;
			nodesSeen.add(ni);

			// if this is the first object, add it
			if (thisObject.size() == 0)
				thisObject.add(makeNodeInstObject(ni, null, GenMath.MATID, 0,0,0,0, arcIndices, portIndices));
			GeomObj firstObject = thisObject.get(0);
			double stLow, stHigh;
			if (curAxis == Axis.HORIZONTAL)
			{
				stLow = firstObject.lowx;
				stHigh = firstObject.highx;
			} else
			{
				stLow = firstObject.lowy;
				stHigh = firstObject.highy;
			}

			// for each arc on node, find node at other end and add to object
			for(Iterator<Connection> it = ni.getConnections(); it.hasNext(); )
			{
				Connection con = it.next();
				ArcInst ai = con.getArc();
				NodeInst otherEnd = ai.getTailPortInst().getNodeInst();
				if (otherEnd == ni) otherEnd = ai.getHeadPortInst().getNodeInst();

				// stop if other end has already been examined
				if (nodesSeen.contains(otherEnd)) continue;
				GeomObj newObject = makeArcInstObject(ai, null, GenMath.MATID, 0,0,0,0, arcIndices);

				GeomObj secondObject = makeNodeInstObject(otherEnd, null, GenMath.MATID, 0,0,0,0, arcIndices, portIndices);

				double bdLow, bdHigh;
				boolean partOfLine = false;
				if (curAxis == Axis.HORIZONTAL)
				{
					bdLow = secondObject.lowx;
					bdHigh = secondObject.highx;
					if (ai.getHeadLocation().getX() == ai.getTailLocation().getX()) partOfLine = true;
					if (DBMath.doublesEqual(ni.getAnchorCenterX(), otherEnd.getAnchorCenterX())) partOfLine = true;
				} else
				{
					bdLow = secondObject.lowy;
					bdHigh = secondObject.highy;
					if (ai.getHeadLocation().getY() == ai.getTailLocation().getY()) partOfLine = true;
					if (DBMath.doublesEqual(ni.getAnchorCenterY(), otherEnd.getAnchorCenterY())) partOfLine = true;
				}
				if (bdHigh > stLow && bdLow < stHigh) partOfLine = true;
				if (partOfLine)
				{
					thisObject.add(newObject);
					thisObject.add(secondObject);
					createObjects(otherEnd, thisObject, otherObject, nodesSeen, arcIndices, portIndices);
				} else
				{
					// arcs in object to be used later in fixed_non_fixed
					otherObject.add(newObject);
				}
			}
		}

		/**
		 * Method to build a object describing node "ni" in axis "axis".  If "object"
		 * is null, this node is at the top level, and a new GeomObj should be
		 * constructed for it.  Otherwise, the node is in a subcell and it must be
		 * transformed through "newTrans" and clipped to the two protection frames
		 * defined by "low1" to "high1" and "low2" to "high2" before being added to
		 * "object".
		 */
		private GeomObj makeNodeInstObject(NodeInst ni, GeomObj object, AffineTransform newTrans,
			double low1, double high1, double low2, double high2, HashMap<ArcInst,Integer> arcIndices, HashMap<PortProto,Integer> portIndices)
		{
			GeomObj newObject = object;
			if (newObject == null)
			{
				newObject = new GeomObj();
				newObject.inst = ni;
				newObject.nextObject = null;
				newObject.firstPolyList = null;
				Rectangle2D bounds = ni.getBounds();
				newObject.outerLowx = bounds.getMinX();
				newObject.outerHighx = bounds.getMaxX();
				newObject.outerLowy = bounds.getMinY();
				newObject.outerHighy = bounds.getMaxY();
				if (ni.isCellInstance())
				{
					newObject.lowx = newObject.outerLowx;
					newObject.highx = newObject.outerHighx;
					newObject.lowy = newObject.outerLowy;
					newObject.highy = newObject.outerHighy;
				} else
				{
                    Rectangle2D bound = ni.getBaseShape().getBounds2D();
//					double cX = ni.getTrueCenterX();
//					double cY = ni.getTrueCenterY();
//					double sX = ni.getXSize();
//					double sY = ni.getYSize();
//					SizeOffset so = ni.getSizeOffset();
//					double lX = cX - sX/2 + so.getLowXOffset();
//					double hX = cX + sX/2 - so.getHighXOffset();
//					double lY = cY - sY/2 + so.getLowYOffset();
//					double hY = cY + sY/2 - so.getHighYOffset();
//					Rectangle2D bound = new Rectangle2D.Double(lX, lY, hX-lX, hY-lY);
//					GenMath.transformRect(bound, ni.rotateOut());
					newObject.lowx = bound.getMinX();
					newObject.highx = bound.getMaxX();
					newObject.lowy = bound.getMinY();
					newObject.highy = bound.getMaxY();
				}
			}

			// propagate global network info to local port prototypes on "ni"
			HashMap<PortProto,Integer> localPortIndices = fillNode(ni, arcIndices, portIndices);

			// create pseudo-object for complex ni
			if (ni.isCellInstance())
			{
				Cell subCell = (Cell)ni.getProto();

				// compute transformation matrix from subnode to this space
				AffineTransform trans = ni.translateOut(newTrans);

				/*
				 * create a line for cell "ni->proto" at the current location and
				 * translation.  Put only the instances which are within maxBoundary
				 * of the perimeter of the cell.
				 */
				HashMap<ArcInst,Integer> localArcIndices = subCellSmash(subCell, localPortIndices);

				// compute protection frame if at the top level
				if (object == null)
				{
					Rectangle2D bounds = ni.getBounds();
					if (curAxis == Axis.HORIZONTAL)
					{
						low1 = bounds.getMinX();
						high1 = bounds.getMinX() + maxBoundary;
						low2 = bounds.getMaxX() - maxBoundary;
						high2 = bounds.getMaxX();
					} else
					{
						low1 = bounds.getMinY();
						high1 = bounds.getMinY() + maxBoundary;
						low2 = bounds.getMaxY() - maxBoundary;
						high2 = bounds.getMaxY();
					}
				}

				// include polygons from those nodes and arcs in the protection frame
				for(Iterator<NodeInst> it = subCell.getNodes(); it.hasNext(); )
				{
					NodeInst subNi = it.next();
					makeNodeInstObject(subNi, newObject, trans,
						low1, high1, low2, high2, localArcIndices, localPortIndices);
				}
				for(Iterator<ArcInst> it = subCell.getArcs(); it.hasNext(); )
				{
					ArcInst subAi = it.next();
					makeArcInstObject(subAi, newObject, trans,
						low1, high1, low2, high2, localArcIndices);
				}
			} else
			{
				AffineTransform trans = ni.rotateOut(newTrans);
				Technology tech = ni.getProto().getTechnology();
				Poly [] polys = tech.getShapeOfNode(ni, true, true, null);
				int tot = polys.length;
				for(int j=0; j<tot; j++)
				{
					Poly poly = polys[j];
					poly.transform(trans);

					// make sure polygon is within protection frame
					if (object != null)
					{
						Rectangle2D bounds = poly.getBounds2D();
						if (curAxis == Axis.HORIZONTAL)
						{
							if ((bounds.getMaxX() < low1 || bounds.getMinX() > high1) &&
								(bounds.getMaxX() < low2 || bounds.getMinX() > high2)) continue;
						} else
						{
							if ((bounds.getMaxY() < low1 || bounds.getMinY() > high1) &&
								(bounds.getMaxY() < low2 || bounds.getMinY() > high2)) continue;
						}
					}

					int pIndex = -1;
					if (poly.getPort() != null)
					{
						Integer i = localPortIndices.get(poly.getPort());
						if (i != null) pIndex = i.intValue();
					}
					addPolyToPolyList(poly, newObject, pIndex, tech);
				}
			}
			return newObject;
		}

		private HashMap<PortProto,Integer> fillNode(NodeInst ni, HashMap<ArcInst,Integer> arcIndices, HashMap<PortProto,Integer> portIndices)
		{
			// initialize network information for this node instance
			HashMap<PortProto,Integer> localPortIndices = new HashMap<PortProto,Integer>();

			// set network numbers from arcs
			for(Iterator<Connection> it = ni.getConnections(); it.hasNext(); )
			{
				Connection con = it.next();
				ArcInst ai = con.getArc();
				PortProto pp = con.getPortInst().getPortProto();
				if (localPortIndices.get(pp) != null) continue;
				Integer aIndex = arcIndices.get(ai);
				localPortIndices.put(pp, aIndex);
			}

			// set network numbers from exports
			for(Iterator<Export> it = ni.getExports(); it.hasNext(); )
			{
				Export e = it.next();
				PortProto pp = e.getOriginalPort().getPortProto();
				if (localPortIndices.get(pp) != null) continue;
				Integer pIndex = portIndices.get(e);
				localPortIndices.put(pp, pIndex);
			}

			// look for unconnected ports and assign new network numbers
			Netlist nl = ni.getParent().getUserNetlist();
			for(Iterator<PortProto> it = ni.getProto().getPorts(); it.hasNext(); )
			{
				PortProto pp = it.next();
				if (localPortIndices.get(pp) != null) continue;

				// look for similar connected port
				boolean found = false;
				Network net = nl.getNetwork(ni, pp, 0);
				for(Iterator<PortProto> oIt = ni.getProto().getPorts(); oIt.hasNext(); )
				{
					PortProto oPp = oIt.next();
					Network oNet = nl.getNetwork(ni, oPp, 0);
					if (oNet == net)
					{
						Integer oIndex = localPortIndices.get(oPp);
						if (oIndex != null)
						{
							localPortIndices.put(pp, oIndex);
							found = true;
							break;
						}
					}
				}
				if (!found) localPortIndices.put(pp, new Integer(flatIndex++));
			}
			return localPortIndices;
		}

		/**
		 * Method to build a "object" structure that describes arc "ai".  If "object"
		 * is null, this arc is at the top level, and a new GeomObj should be
		 * constructed for it.  Otherwise, the arc is in a subcell and it must be
		 * transformed through "newTrans" and clipped to the two protection frames
		 * defined by "low1", "high1" and "low2", "high2" before being added to "object".
		 */
		private GeomObj makeArcInstObject(ArcInst ai, GeomObj object, AffineTransform newTrans,
			double low1, double high1, double low2, double high2, HashMap<ArcInst,Integer> arcIndices)
		{
			// create the object if at the top level
			GeomObj newObject = object;
			if (object == null)
			{
				newObject = new GeomObj();
				newObject.inst = ai;
				newObject.nextObject = null;
				newObject.firstPolyList = null;
                Poly poly = ai.makeLambdaPoly(ai.getGridBaseWidth(), Poly.Type.CLOSED);
				Rectangle2D bounds = poly.getBounds2D();
				newObject.lowx = bounds.getMinX();
				newObject.highx = bounds.getMaxX();
				newObject.lowy = bounds.getMinY();
				newObject.highy = bounds.getMaxY();

				poly = ai.makeLambdaPoly(ai.getGridFullWidth(), Poly.Type.CLOSED);
				bounds = poly.getBounds2D();
				newObject.outerLowx = bounds.getMinX();
				newObject.outerHighx = bounds.getMaxX();
				newObject.outerLowy = bounds.getMinY();
				newObject.outerHighy = bounds.getMaxY();
			}

			Technology tech = ai.getProto().getTechnology();
			Poly [] polys = tech.getShapeOfArc(ai);
			int tot = polys.length;
			for(int j=0; j<tot; j++)
			{
				Poly poly = polys[j];
				if (poly.getLayer() == null) continue;

				// make sure polygon is within protection frame
				if (object != null)
				{
					poly.transform(newTrans);
					Rectangle2D bounds = poly.getBounds2D();
					if (curAxis == Axis.HORIZONTAL)
					{
						if ((bounds.getMaxX() < low1 || bounds.getMinX() > high1) &&
							(bounds.getMaxX() < low2 || bounds.getMinX() > high2)) continue;
					} else
					{
						if ((bounds.getMaxY() < low1 || bounds.getMinY() > high1) &&
							(bounds.getMaxY() < low2 || bounds.getMinY() > high2)) continue;
					}
				}

				// add the polygon
				int aIndex = -1;
				Integer iv = arcIndices.get(ai);
				if (iv != null) aIndex = iv.intValue();
				addPolyToPolyList(poly, newObject, aIndex, tech);
			}
			return newObject;
		}

		/**
		 * Method to link polygon "poly" into object "object" with network number
		 * "networkNum"
		 */
		private void addPolyToPolyList(Poly poly, GeomObj object, int networkNum, Technology tech)
		{
			PolyList newPolyList = new PolyList();
			newPolyList.poly = poly;
			newPolyList.tech = tech;
			newPolyList.networkNum = networkNum;
			newPolyList.nextPolyList = object.firstPolyList;
			object.firstPolyList = newPolyList;
		}

		/**
		 * copy network information from ports to arcs in cell "topCell"
		 */
		private HashMap<ArcInst,Integer> subCellSmash(Cell topCell, HashMap<PortProto,Integer> portIndices)
		{
			Netlist nl = topCell.getUserNetlist();

			// first erase the arc node information
			HashMap<ArcInst,Integer> arcIndices = new HashMap<ArcInst,Integer>();

			// copy network information from ports to arcs
			for(Iterator<ArcInst> it = topCell.getArcs(); it.hasNext(); )
			{
				ArcInst ai = it.next();

				// ignore arcs that have already been numbered
				if (arcIndices.get(ai) != null) continue;

				// see if this arc connects to a port
				Network aNet = nl.getNetwork(ai, 0);
				boolean found = false;
				for(Iterator<PortProto> pIt = topCell.getPorts(); pIt.hasNext(); )
				{
					Export pp = (Export)pIt.next();
					Integer pIndex = portIndices.get(pp);
					Network pNet = nl.getNetwork(pp, 0);
					if (pNet == aNet)
					{
						// propagate port numbers into all connecting arcs
						for(Iterator<ArcInst> aIt = topCell.getArcs(); aIt.hasNext(); )
						{
							ArcInst oAi = aIt.next();
							Network oANet = nl.getNetwork(oAi, 0);
							if (oANet == aNet) arcIndices.put(oAi, pIndex);
						}
						found = true;
						break;
					}
				}

				// if not connected to a port, this is an internal network
				if (!found)
				{
					// copy new net number to all of these connected arcs
					Integer pIndex = new Integer(flatIndex++);
					for(Iterator<ArcInst> aIt = topCell.getArcs(); aIt.hasNext(); )
					{
						ArcInst oAi = aIt.next();
						Network oANet = nl.getNetwork(oAi, 0);
						if (oANet == aNet) arcIndices.put(oAi, pIndex);
					}
				}
			}
			return arcIndices;
		}
	}
}