RecognizerImpl.mesa
Last Edited by: Gbier, July 11, 1985 12:18:45 pm PDT
Last Edited by: Gbier, July 26, 1985 1:41:17 pm PDT
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.