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] =
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] =
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] =
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] =
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] =
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] =
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] =
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] =
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] =
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] =
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.


pRecognizerImpl.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
--Overlapping regions between plane1 and plane2 will be added to the overlapPlane
--A new tesselation called currentTess is formed which contains the maximum connected region that has the same value as tile and contains tile.
--Returns all tiles adjacent to tile that have the same value as tile
--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.
--Draws the instance using the instances drawMe procedure
--The rect is enumerated against its layer plane, if it is not covered then passTessInfo.matches is set to false.
--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
--passTessInfo.coveredList is enumerated against the layerList.  Returns FALSE if any piece of the coveredList is covered on any of the layers.
--Returns true if everything on checkList is covered on the Tesselation
--Returns true if the intersection between items on the checklist and the tesselation is non-empty
�Ê€˜š
œ™Jš
œ4™4Jš
œ3™3—J˜š
Ïk	˜	Jš�œ
˜Jš
œ	˜	Jš
œ˜J˜	J˜Jš
œ˜Jš
œ˜—J˜J˜šÏbœ�œ
�˜Jš�œ
�œ0˜:Jš�œ˜—Jš�œ
˜J˜šœ�œ�œ˜%Jšœ�œ˜Jšœ�œ
˜Jšœ+Ïc3˜^J˜—J˜Jš
œ�œ
�œ
�œ�œŸ)˜iJ˜šœ�œ�œ˜ Jšœ�œ˜Jšœ	�œ˜Jšœ	�œ˜Jšœ�œ
�œ
�œ˜J˜—J˜Jš
œ�œ
�œ
�œ�œŸ(˜^J˜Jšœ�œ�œ	˜šœ	�œ�œ˜Jšœ�œ	˜Jšœ�œ˜Jšœ	�œ	˜Jšœ	�œ	�œ
˜ Jšœ	�œ	�œ
˜ Jšœ�œ�œ
˜4Jšœ�œ�œ
˜8Jšœ�œ�œ
˜8Jš	œ
�œ
�œ
�œ�œ˜8Jšœ	�œ�œ
˜Jš
œ
�œ
�œ�œ
�œ�œ
�œ
˜IJ˜—J˜Jš	œ�œ�œ
�œ
�œ˜6J˜š
Ïnœ�œ
�œ
�œ�œ
˜FJš
�˜š
�œ
�œ
�œ
�œ5�œ
�œ
�˜hš�œ1�œ˜9Jšœ�œ:˜XJ˜0J˜0J˜RJ˜Rš
�œ�œ
�œ
�œ4�œ�œ
�˜dJ˜MJš�œ
˜—J˜/J˜=J˜«
J˜©
J˜—J˜,Jš�œ
˜—Jš�œ
˜—J˜šÐbnœ�œ
�œ$˜NJš
�˜Jšœ�œ�œ$˜7J˜ J˜ š	�œ�œA�œ�œ
�˜nš�œ'�œ
˜.J˜�
—Jš�œ˜	—Jš�œ
˜J˜—š
¡œ�œ�œ
�œ�œ˜CJš
�˜Jšœ�œ˜4š�œ�œ
�˜(Jš
œ\˜\—Jš�œ
˜—J˜š¡œ�œ
�œ �œ˜_J™QJš
�˜š	�œ�œr�œ�œ
�˜¯
š�œ"�œ
˜)Jš�œ�œ.˜RšœI�œ�œ
�˜bš�œ"�˜(J˜a—Jš�œ
˜——Jš�œ
˜—Jš�œ
˜—J˜š¡œ�œ'�œ
�œ˜IJš
œ�
™�
Jš
�˜š�œ�œ˜Jšœ
�œ@˜PJšœ�œ˜)Jšœ
�œ
�œ�œ˜7š�œ�œ
�œ
˜J˜/J˜š�œ�œ˜J˜KJ˜MJ˜J˜—Jš�œ
˜—J˜,J˜
—Jš�œ
˜—J˜š¡œ�œ(�œ(�œ
�œ�œ�œ
�œ˜Â
Jš
œE™EJš
�˜J˜%J˜J˜4š�œ5�˜<š�œ �˜&Jšœ
�œ˜%—J˜:Jš�œ
˜—Jš�œ �œ�œ˜LJ˜3š�œ4�˜;š�œ �˜&Jšœ
�œ˜%—J˜;Jš�œ
˜—Jš�œ �œ�œ˜LJ˜4š�œ5�˜<š�œ �˜&Jšœ
�œ˜%—J˜:Jš�œ
˜—Jš�œ �œ�œ˜LJ˜3š�œ4�˜;š�œ �˜&Jšœ
�œ˜%—J˜;Jš�œ
˜—Jš�œ �œ�œ˜LJš�œ
˜J˜—J˜š¡œ�œ�œ9˜bJš
œ»™»Jš
�˜Jšœ�œf˜†
Jšœ�œ˜Jšœ�œ%�œ%�œ˜jJšœ�œ
˜š�œ6�œ�œ
�œ
˜Qš�œ�œ
�œ˜$J˜Jšœ�œ,˜KJ˜—Jš�œ
˜—š
�œ�œ
�œ
�œE�œ�œ
�˜„
š�œD�œ*�œ
˜xJš
œ{˜{—Jš�œ
˜—š�œ�œ
�˜"š�œD�œN�œ˜�
šœ	�œ˜)Jš
œ˜Jš
œ˜Jš
œ,˜,Jš
œ8˜8Jš
œ>˜>Jš
œ˜Jš
œ˜J˜Jš
œ
˜
—Jšœ�œ
˜Jš�œ
˜J˜
—š
�˜J˜1—Jš�œ
˜—Jš�œ
˜J˜—š¡œ�œ�œ%�œ�œ�œ˜cJš
œ9™9Jš
�˜Jšœ�œ�œ$˜7J˜ J˜"Jšœ�œ
˜J˜AJ˜AJ˜gš�œ�œ˜Jš�œ%˜+Jš
Ÿ¿˜¿—Jš�œ
˜—J˜š
¡œ�œ�œ
�œ�œ˜EJš
œq™qJš
�˜Jšœ�œ˜4Jšœ�œ;˜Pš�œ�œ˜š�œ�œ
˜!Jš
œF˜F—š
�˜š�œ�œ
˜!J˜E——Jš�œ�œ
�œ˜ šœ�œ
˜ J˜9Jš
œM˜MJš
�˜J˜—š	�œ�œj�œ�œ
�˜£
š�œ�œ
�œ˜%Jšœ�œ
˜Jš
�˜J˜
—Jš�œ
˜—Jš
œ
˜
—Jš�œ
˜J˜—š
¡œ�œ�œ�œ�œ˜OJš
œ 
™ 
Jš
�˜Jšœ�œ@˜Nš	�œ�œ‰
�œ�œ
�˜Æ
š�œ�œ
�œ
˜%š	�œ�œŽ
�œ�œ
�˜Ë
š�œ�œ
�˜$J˜F—Jš�œ
˜——Jš�œ
˜—Jš�œG˜MJš�œ
˜—J˜J˜š¡œ�œ
�œ
�œ
�œ"�œ�œ�œ˜kJ™�
Jš
�˜š�œ�œ
�˜š�œ-�œ
�œ˜9J˜9J˜TJš�œ�œ˜J˜
—š
�˜š�œ]�˜cJšœ
�œ�œ
˜—š
�˜J˜——Jš�œ
˜—Jš�œ
˜J˜—š¡œ�œ�œ�œ�œ�œ˜~Jš
œG™GJš
�˜š�œ�œ
�˜š	�œ �œx�œ�œ
�˜¿
š�œ �œ
�œ
˜+Jš�œ
�œ
˜
—Jš�œ
˜—Jš
œ˜Jš�œ
˜—Jš�œ
˜—J˜š¡œ�œ�œ�œ�œ�œ˜wJš
œb™bJš
�˜š�œ�œ
�˜š	�œ �œx�œ�œ
�˜¿
š�œ�œ
�œ
˜*Jš�œ
�œ˜
—Jš�œ
˜—J˜Jš�œ
˜—Jš�œ
˜J˜—š
¡œ�œ
�œ�œ�œ0˜„
Jš
�˜Jšœ�œ
�œS˜sJš�œ
˜—J˜š¡œ�œ
�œ�œ�œ�œ
�œ
�œ
˜vJš
�˜Jšœ�œ
�œQ˜lJš�œ
˜—J˜Jš�œ
˜Jš
œ
˜
—…—0îBÞ