<> <> <> DIRECTORY CD, CDBasics, CornerStitching, CDOrient, CDCells, Recognizer, TerminalIO; RecognizerImpl: CEDAR PROGRAM IMPORTS CD, CDBasics, CornerStitching, CDCells, TerminalIO EXPORTS Recognizer = BEGIN PossibleProcedureRec: TYPE = RECORD [ technology: CD.Technology, rectCount: INT, instProc: Recognizer.PossibleInstanceProc --the procedure that will return possible instances ]; possibleProcedureList: LIST OF REF PossibleProcedureRec _ NIL; --Contains registered possible procedures ActiveLayersRec: TYPE = RECORD [ technology: CD.Technology, active1: CD.Layer, active2: CD.Layer, layerList: LIST OF CD.Layer ]; activeLayersList: LIST OF REF ActiveLayersRec _ NIL; --Contains registered active layer pairs DataRecPtr: TYPE = REF DataRec; DataRec: TYPE = RECORD [ design: CD.Design, cellOb: CD.Object, cellPtr: CD.CellPtr, active1: CD.Layer _ CD.combined, active2: CD.Layer _ CD.combined, overlapPlane: REF CornerStitching.Tesselation _ NIL, active1CheckTess: REF CornerStitching.Tesselation _ NIL, active2CheckTess: REF CornerStitching.Tesselation _ NIL, coveredList: LIST OF REF CornerStitching.Region _ NIL, matches: BOOLEAN _ TRUE, layerPlanes: ARRAY CD.Layer OF REF CornerStitching.Tesselation _ ALL[NIL] ]; RegionList: TYPE = LIST OF REF CornerStitching.Region; RecognizeObjects: PUBLIC PROC [design: CD.Design, cellOb: CD.Object] = BEGIN FOR activeList: LIST OF REF ActiveLayersRec _ activeLayersList, activeList.rest WHILE activeList #NIL DO IF activeList.first.technology = design.technology THEN { passTessInfo: DataRecPtr _ NEW[DataRec _ [design, cellOb, NARROW[cellOb.specificRef]]]; passTessInfo.active1 _ activeList.first.active1; passTessInfo.active2 _ activeList.first.active2; passTessInfo.layerPlanes[passTessInfo.active1] _ CornerStitching.NewTesselation[]; passTessInfo.layerPlanes[passTessInfo.active2] _ CornerStitching.NewTesselation[]; FOR layerList: LIST OF CD.Layer _ activeList.first.layerList, layerList.rest WHILE layerList #NIL DO passTessInfo.layerPlanes[layerList.first] _ CornerStitching.NewTesselation[]; ENDLOOP; FillPlanesByDrawingRects[design, passTessInfo]; passTessInfo.overlapPlane _ CornerStitching.NewTesselation[]; FormOverlapPlane[plane1: passTessInfo.layerPlanes[passTessInfo.active1], plane2: passTessInfo.layerPlanes[passTessInfo.active2], overlapPlane: passTessInfo.overlapPlane]; [] _ CornerStitching.EnumerateArea [plane: passTessInfo.overlapPlane, rect: CDBasics.universe, backgroundValue: $none, perTile: GrowTransistorTile, data: passTessInfo]; }; [] _ CDCells.RepositionCell[cellOb, design]; ENDLOOP; END; FillPlanesByDrawingRects: PROC [design: CD.Design, passTessInfo: DataRecPtr] = BEGIN pr: CD.DrawRef _ CD.CreateDrawRef[passTessInfo.design]; pr.devicePrivate _ passTessInfo; pr.drawRect _ DrawRectIntoPlane; FOR instanceList: CD.InstanceList _ passTessInfo.cellPtr.contents, instanceList.rest WHILE instanceList#NIL DO IF instanceList.first.ob.class.wireTyped THEN instanceList.first.ob.class.drawMe[inst: instanceList.first, pos: instanceList.first.location, orient: instanceList.first.orientation, pr: pr]; ENDLOOP; END; DrawRectIntoPlane: PROC [r: CD.Rect, l: CD.Layer, pr: CD.DrawRef] = BEGIN passTessInfo: DataRecPtr _ NARROW[pr.devicePrivate]; IF passTessInfo.layerPlanes[l] #NIL THEN CornerStitching.ChangeRect [plane: passTessInfo.layerPlanes[l], rect: r, newValue: $cover]; END; FormOverlapPlane: PUBLIC PROC [plane1, plane2, overlapPlane: REF CornerStitching.Tesselation] = <<--Overlapping regions between plane1 and plane2 will be added to the overlapPlane>> BEGIN FOR regionList1: RegionList _ NARROW[CornerStitching.EnumerateArea[plane: plane1, rect: CDBasics.universe, backgroundValue: $none]], regionList1.rest WHILE regionList1 #NIL DO IF regionList1.first.value = $cover THEN FOR overlapList: RegionList _ NARROW[CornerStitching.EnumerateArea[plane: plane2, rect: regionList1.first.rect, backgroundValue: $none]], overlapList.rest WHILE overlapList #NIL DO IF overlapList.first.value = $cover THEN CornerStitching.ChangeRect [plane: overlapPlane, rect: overlapList.first.rect, newValue: $cover]; ENDLOOP; ENDLOOP; END; GrowTransistorTile: PROC [tile: CornerStitching.TilePtr, data: REF ANY] = <<--A new tesselation called currentTess is formed which contains the maximum connected region that has the same value as tile and contains tile.>> BEGIN IF tile.value = $cover THEN { currentTess: REF CornerStitching.Tesselation _ CornerStitching.NewTesselation[]; passTessInfo: DataRecPtr _ NARROW [data]; tileList: LIST OF CornerStitching.TilePtr _ LIST[tile]; WHILE tileList #NIL DO tile: CornerStitching.TilePtr _ tileList.first; tileList _ tileList.rest; IF tile.value #$done THEN { tileList _ GetNeighborsSameAsMe[tile, passTessInfo.overlapPlane, tileList]; CornerStitching.ChangeRect [currentTess, CornerStitching.Area[tile], $cover]; tile.value _ $done; }; ENDLOOP; AnalyzeTransistor[currentTess,passTessInfo]; } END; GetNeighborsSameAsMe: PROC [tile: CornerStitching.TilePtr, tess: REF CornerStitching.Tesselation, tileList: LIST OF CornerStitching.TilePtr] RETURNS [newList: LIST OF CornerStitching.TilePtr] = <<--Returns all tiles adjacent to tile that have the same value as tile>> BEGIN currentTile: CornerStitching.TilePtr; newList _ tileList; currentTile _ CornerStitching.ENorthNeighbour[tile]; WHILE CornerStitching.WSouthNeighbour[currentTile] = tile DO IF currentTile.value = tile.value THEN newList _ CONS[currentTile, newList]; currentTile _ CornerStitching.SWestNeighbour[currentTile]; ENDLOOP; IF currentTile.value = tile.value THEN newList _ CONS[currentTile, newList]; currentTile _ CornerStitching.SWestNeighbour[tile]; WHILE CornerStitching.NEastNeighbour[currentTile] = tile DO IF currentTile.value = tile.value THEN newList _ CONS[currentTile, newList]; currentTile _ CornerStitching.ENorthNeighbour[currentTile]; ENDLOOP; IF currentTile.value = tile.value THEN newList _ CONS[currentTile, newList]; currentTile _ CornerStitching.WSouthNeighbour[tile]; WHILE CornerStitching.ENorthNeighbour[currentTile] = tile DO IF currentTile.value = tile.value THEN newList _ CONS[currentTile, newList]; currentTile _ CornerStitching.NEastNeighbour[currentTile]; ENDLOOP; IF currentTile.value = tile.value THEN newList _ CONS[currentTile, newList]; currentTile _ CornerStitching.NEastNeighbour[tile]; WHILE CornerStitching.SWestNeighbour[currentTile] = tile DO IF currentTile.value = tile.value THEN newList _ CONS[currentTile, newList]; currentTile _ CornerStitching.WSouthNeighbour[currentTile]; ENDLOOP; IF currentTile.value = tile.value THEN newList _ CONS[currentTile, newList]; END; AnalyzeTransistor: PROC [currentTess: REF CornerStitching.Tesselation, passTessInfo: DataRecPtr] = <<--Enumerates currentTess, counting the covered regions and storing the covered regions on passTessInfo.coveredList. The count and technology are used to select the proper Possible Instance Procedures to call. The Possible Instance Procedures return a list of possible instances which are then searched for a match.>> BEGIN currentList: RegionList _ NARROW[CornerStitching.EnumerateArea [plane: currentTess, rect: CDBasics.universe, backgroundValue: $none]]; count: INT _ 0; possibleInstListPtr: REF Recognizer.InstAndForbidLayerList _ NEW[Recognizer.InstAndForbidLayerList _ NIL]; passTessInfo.coveredList _ NIL; FOR countList: RegionList _ currentList, countList.rest WHILE countList #NIL DO IF countList.first.value #NIL THEN { count _ count + 1; passTessInfo.coveredList _ CONS[countList.first, passTessInfo.coveredList]; }; ENDLOOP; FOR instanceProcList: LIST OF REF PossibleProcedureRec _ possibleProcedureList, instanceProcList.rest WHILE instanceProcList #NIL DO IF instanceProcList.first.technology = passTessInfo.design.technology AND instanceProcList.first.rectCount = count THEN instanceProcList.first.instProc[passTessInfo.active1, passTessInfo.active2, passTessInfo.coveredList, possibleInstListPtr]; ENDLOOP; WHILE possibleInstListPtr^ #NIL DO IF InstanceMatches[possibleInstListPtr^.first.instance, passTessInfo] AND NoForbiddenOverlap[possibleInstListPtr^.first.forbidLayerList, passTessInfo] THEN { newInst: CD.Instance _ CDCells.IncludeOb[ design: passTessInfo.design, cell: passTessInfo.cellOb, ob: possibleInstListPtr^.first.instance.ob, position: possibleInstListPtr^.first.instance.location, orientation: possibleInstListPtr^.first.instance.orientation, cellCSystem: cdCoords, obCSystem: cdCoords, mode: dontPropagate ].newInst; newInst.selected _ TRUE; EXIT; } ELSE possibleInstListPtr^ _ possibleInstListPtr^.rest; ENDLOOP; END; InstanceMatches: PROC [instance: CD.Instance, passTessInfo: DataRecPtr] RETURNS [BOOLEAN _ FALSE] = <<--Draws the instance using the instances drawMe procedure>> BEGIN pr: CD.DrawRef _ CD.CreateDrawRef[passTessInfo.design]; pr.devicePrivate _ passTessInfo; pr.drawRect _ DrawRectAgainstTess; passTessInfo.matches _ TRUE; passTessInfo.active1CheckTess _ CornerStitching.NewTesselation[]; passTessInfo.active2CheckTess _ CornerStitching.NewTesselation[]; instance.ob.class.drawMe[inst: instance, pos: instance.location, orient: instance.orientation, pr: pr]; IF passTessInfo.matches THEN RETURN[OverlapRegionsMatch[passTessInfo]]; --Reaching here means that the instance drawn against the design matched. However it is still neccessary to make sure that the overlapping region in the instance matches what is on the coveredList. This guarantees that the matching instance is exactly the same size as the overlapping region in question in the design. END; DrawRectAgainstTess: PROC [r: CD.Rect, l: CD.Layer, pr: CD.DrawRef] = <<--The rect is enumerated against its layer plane, if it is not covered then passTessInfo.matches is set to false.>> BEGIN passTessInfo: DataRecPtr _ NARROW[pr.devicePrivate]; checkAgainstTess: REF CornerStitching.Tesselation _ passTessInfo.layerPlanes[l]; IF CDBasics.NonEmpty[r] THEN { IF l = passTessInfo.active1 THEN CornerStitching.ChangeRect[passTessInfo.active1CheckTess, r, $cover] ELSE IF l = passTessInfo.active2 THEN CornerStitching.ChangeRect[passTessInfo.active2CheckTess, r, $cover]; IF checkAgainstTess = NIL THEN { passTessInfo.matches _ FALSE; TerminalIO.WriteRope["Unexpected Layer Encountered\n"]; TerminalIO.WriteRope["An instance tried to draw on an unregistered layer\n"]; RETURN }; FOR checkList: RegionList _ NARROW[CornerStitching.EnumerateArea[plane: checkAgainstTess, rect: r, backgroundValue: $none]], checkList.rest WHILE checkList #NIL DO IF checkList.first.value = NIL THEN { passTessInfo.matches _ FALSE; RETURN } ENDLOOP; } END; OverlapRegionsMatch: PROC [passTessInfo: DataRecPtr] RETURNS [BOOLEAN _ TRUE] = <<--Forms the overlap of what is stored in active1CheckTess and active2CheckTess and makes sure that everthing on the coveredList is really covered by the overlap>> BEGIN checkTess: REF CornerStitching.Tesselation _ CornerStitching.NewTesselation[]; FOR active1List: RegionList _ NARROW[CornerStitching.EnumerateArea[plane: passTessInfo.active1CheckTess, rect: CDBasics.universe, backgroundValue: $none]], active1List.rest WHILE active1List #NIL DO IF active1List.first.value #NIL THEN FOR overlapList: RegionList _ NARROW[CornerStitching.EnumerateArea[plane: passTessInfo.active2CheckTess, rect: active1List.first.rect, backgroundValue: $none]], overlapList.rest WHILE overlapList #NIL DO IF overlapList.first.value #NIL THEN CornerStitching.ChangeRect[checkTess, overlapList.first.rect, $cover]; ENDLOOP; ENDLOOP; RETURN [RegionAndTessOverlapCompletely[passTessInfo.coveredList, checkTess]]; END; NoForbiddenOverlap: PROC [layerList: LIST OF CD.Layer, passTessInfo: DataRecPtr] RETURNS [BOOLEAN _ TRUE] = <<--passTessInfo.coveredList is enumerated against the layerList. Returns FALSE if any piece of the coveredList is covered on any of the layers.>> BEGIN WHILE layerList #NIL DO IF passTessInfo.layerPlanes[layerList.first] = NIL THEN { TerminalIO.WriteRope["Unexpected Layer Encountered\n"]; TerminalIO.WriteRope["A forbidden layer was encountered that was not registered\n"]; RETURN [FALSE]; } ELSE IF RegionAndTessIntersect[passTessInfo.coveredList, passTessInfo.layerPlanes[layerList.first]] THEN RETURN [FALSE] ELSE layerList _ layerList.rest; ENDLOOP; END; RegionAndTessOverlapCompletely: PROC [checkList: RegionList, tess: REF CornerStitching.Tesselation] RETURNS [BOOLEAN _ TRUE] = <<--Returns true if everything on checkList is covered on the Tesselation>> BEGIN WHILE checkList #NIL DO FOR intersectingList: RegionList _ NARROW[CornerStitching.EnumerateArea[plane: tess, rect: checkList.first.rect, backgroundValue: $none]], intersectingList.rest WHILE intersectingList #NIL DO IF intersectingList.first.value = NIL THEN RETURN[FALSE] ENDLOOP; checkList _ checkList.rest ENDLOOP; END; RegionAndTessIntersect: PROC [checkList: RegionList, tess: REF CornerStitching.Tesselation] RETURNS [BOOLEAN _ FALSE] = <<--Returns true if the intersection between items on the checklist and the tesselation is non-empty>> BEGIN WHILE checkList #NIL DO FOR intersectingList: RegionList _ NARROW[CornerStitching.EnumerateArea[plane: tess, rect: checkList.first.rect, backgroundValue: $none]], intersectingList.rest WHILE intersectingList #NIL DO IF intersectingList.first.value #NIL THEN RETURN[TRUE]; ENDLOOP; checkList _ checkList.rest; ENDLOOP; END; RegisterPossibleInstanceProc: PUBLIC PROC [technology: CD.Technology, rectCount: INT, instProc: Recognizer.PossibleInstanceProc] = BEGIN possibleProcedureList _ CONS[NEW[PossibleProcedureRec _ [technology, rectCount, instProc]], possibleProcedureList]; END; RegisterLayerList: PUBLIC PROC [technology: CD.Technology, active1, active2: CD.Layer, layerList: LIST OF CD.Layer] = BEGIN activeLayersList _ CONS[NEW[ActiveLayersRec _ [technology, active1, active2, layerList]], activeLayersList]; END; END.