-- File: DJExtGeom.mesa
-- routines which look at geometry for the disjoint circuit extractor
-- Written by Martin Newell/Dan Fitzpatrick July 1981
-- Last edited: 13-Aug-81 17:52:11

DIRECTORY

DJExtAllocDefs: FROM "DJExtAllocDefs" USING [AllocateNodeSegment, FreeNodeSegment],
DJExtractDefs: FROM "DJExtractDefs" USING [Interrupt, RecordNodeLoc],
DJExtCapDefs: FROM "DJExtCapDefs" USING [AddCapArea, AddCapPerim, FindCap],
DJExtCombineDefs: FROM "DJExtCombineDefs" USING [Combine],
DJExtDebugDefs: FROM "DJExtDebugDefs" USING [Debug],
DJExtGeomDefs: FROM "DJExtGeomDefs",
DJExtGraphicsDefs: FROM "DJExtGraphicsDefs" USING [DrawRectangle, DrawLongDecimal],
DJExtMergeDefs: FROM "DJExtMergeDefs" USING [GenNodeNumber],
DJExtSortDefs: FROM "DJExtSortDefs" USING [In, DumpSorter],
DJExtTransDefs: FROM "DJExtTransDefs" USING [AddDiff, FindTransistor],
DJExtTypes: FROM "DJExtTypes" USING [NodeNumber, NodeSegment, Node, poly, metal, diff, gate, cut, implant],
DJExtUtilsDefs: FROM "DJExtUtilsDefs" USING [Error],
JaMFnsDefs: FROM "JaMFnsDefs" USING [GetJaMBreak];

DJExtGeom: PROGRAM
IMPORTS DJExtAllocDefs, DJExtractDefs, DJExtCapDefs, DJExtCombineDefs, DJExtDebugDefs, DJExtGraphicsDefs, DJExtMergeDefs, DJExtSortDefs, DJExtTransDefs, DJExtUtilsDefs, JaMFnsDefs
EXPORTS DJExtGeomDefs =
BEGIN
OPEN DJExtAllocDefs, DJExtractDefs, DJExtCapDefs, DJExtCombineDefs, DJExtDebugDefs, DJExtGraphicsDefs, DJExtMergeDefs, DJExtSortDefs, DJExtTransDefs, DJExtTypes, DJExtUtilsDefs, JaMFnsDefs;

ExtractGeometry: PUBLIC PROCEDURE =
BEGIN
debug ← Debug[];
firstNodeSeg ← lastNodeSeg ← oldSegList ← ALL[NIL];
DumpSorter[];
-- free segments
FOR layer:INTEGER IN [0..MaxLayer) DO
oldSeg:NodeSegment ← oldSegList[layer];
UNTIL oldSeg = NIL DO
tmp:NodeSegment ← oldSeg;
oldSeg ← oldSeg.next;
FreeNodeSegment[tmp];
ENDLOOP;
oldSegList[layer] ← firstNodeSeg[layer] ← NIL;
ENDLOOP;
END;

NewSwath: PUBLIC PROCEDURE [ycur:REAL] =
BEGIN
height ← ycur - y;
FinishOldSwath[y,ycur];
y ← ycur;
firstNodeSeg ← lastNodeSeg ← ALL[NIL];
count ← ALL[0];
nodeNum ← ALL[0];
IF GetJaMBreak[] THEN SIGNAL Interrupt;
END;

StartRec: PUBLIC PROCEDURE [left:REAL, layer:INTEGER] =
BEGIN
count[layer] ← count[layer] + 1;
SELECT layer FROM
poly => {
IF In[diff] THEN {
IF Left[diff] # left OR nodeNum[diff] # 0 THEN EndRec[left,diff];
StartRec[left,gate];
};
Left[layer] ← left;
};
diff => {
IF In[poly] THEN {
StartRec[left,gate];
RETURN;
};
Left[layer] ← left;
};
gate => IF count[layer] # 1 THEN RETURN
ELSE Left[layer] ← left;
ENDCASE => Left[layer] ← left;
END;

EndRec: PUBLIC PROCEDURE [right:REAL, layer:INTEGER] =
BEGIN
count[layer] ← count[layer] - 1;
SELECT layer FROM
poly => IF In[diff] THEN {
EndRec[right,gate];
StartRec[right,diff];
};
diff => IF In[poly] THEN {
EndRec[right,gate];
RETURN;
}
-- be careful of bogus diffusion regions
ELSE IF Left[diff] = right AND nodeNum[diff] = 0 THEN RETURN;
gate => IF count[layer] # 0 THEN RETURN
ENDCASE;
MakeNodeSegment[Left[layer],right,nodeNum[layer],layer];
nodeNum[layer] ← 0;
END;

SetNodeNumber: PUBLIC PROCEDURE [node:NodeNumber, layer:INTEGER] =
BEGIN
IF nodeNum[layer] = 0 THEN nodeNum[layer] ← node
ELSE nodeNum[layer] ← Combine[nodeNum[layer],node];
END;

MakeNodeSegment: PROCEDURE [left,right:REAL, node:NodeNumber, layer:INTEGER] =
BEGIN
seg: NodeSegment ← AllocateNodeSegment[];
seg↑ ← [
next: NIL,
node: node,
layer: layer,
left: left,
right: right
];
IF lastNodeSeg[layer] = NIL THEN firstNodeSeg[layer] ← seg
ELSE lastNodeSeg[layer].next ← seg;
lastNodeSeg[layer] ← seg;
END;

FinishOldSwath: PROCEDURE [bottom,top: REAL] =
BEGIN
oldSeg:NodeSegment;
Top ← top;
Bottom ← bottom;
Center ← (Top+Bottom)/2;
-- run down two lists looking for overlaps, propagating node numbers upward
FOR layer:INTEGER IN [0..MaxLayer) DO
IF Active[layer] THEN
IF layer = gate THEN PropagateTrans[layer]
ELSE Propagate[layer];
ENDLOOP;
-- free up old segments, and update old swath
FOR layer:INTEGER IN [0..MaxLayer) DO
oldSeg ← oldSegList[layer];
UNTIL oldSeg = NIL DO
tmp: NodeSegment ← oldSeg;
oldSeg ← oldSeg.next;
FreeNodeSegment[tmp];
ENDLOOP;
oldSegList[layer] ← firstNodeSeg[layer];
ENDLOOP;
-- propagate through contact cuts
PropagateByCut[];
END;

Propagate: PROCEDURE[layer:INTEGER] =
BEGIN

Draw: PROC [seg: NodeSegment] = INLINE
BEGIN
IF NOT debug THEN RETURN;
DrawRectangle[seg.left,Bottom,seg.right,Top,Stipple[seg.layer]];
DrawLongDecimal[seg.node,(seg.left+seg.right)/2,Center];
END;

cap: Node;
newSeg:NodeSegment ← firstNodeSeg[layer];
oldSeg:NodeSegment ← oldSegList[layer];
UNTIL newSeg = NIL OR oldSeg = NIL DO
IF newSeg.right < oldSeg.left THEN {
IF newSeg.node = 0 THEN {
newSeg.node ← GenNodeNumber[];
RecordNodeLoc[newSeg.node,(newSeg.left+newSeg.right)/2,Center];
};
Draw[newSeg];
cap ← FindCap[newSeg.node];
AddCapArea[cap,layer,height*(newSeg.right-newSeg.left)];
AddCapPerim[cap,layer,2*(height+newSeg.right-newSeg.left)];
newSeg ← newSeg.next;
LOOP;
};
IF oldSeg.right < newSeg.left THEN {
oldSeg ← oldSeg.next;
LOOP;
};
-- if we get this far then we have an overlap
-- (we know: oldSeg.left <= newSeg.right & newSeg.left <= oldSeg.right)
IF newSeg.node = 0 THEN newSeg.node ← oldSeg.node
ELSE newSeg.node ← Combine[oldSeg.node,newSeg.node];
cap ← FindCap[newSeg.node];
AddCapPerim[cap,layer,
2*(MAX[oldSeg.left,newSeg.left]-MIN[oldSeg.right,newSeg.right])];
IF oldSeg.right = newSeg.right THEN {
-- if right sides are equal the advance both pointers
oldSeg ← oldSeg.next;
Draw[newSeg];
cap ← FindCap[newSeg.node];
AddCapArea[cap,layer,height*(newSeg.right-newSeg.left)];
AddCapPerim[cap,layer,2*(height+newSeg.right-newSeg.left)];
newSeg ← newSeg.next;
LOOP;
}
ELSE IF oldSeg.right < newSeg.right THEN {
oldSeg ← oldSeg.next;
LOOP;
}
ELSE {
Draw[newSeg];
cap ← FindCap[newSeg.node];
AddCapArea[cap,layer,height*(newSeg.right-newSeg.left)];
AddCapPerim[cap,layer,2*(height+newSeg.right-newSeg.left)];
newSeg ← newSeg.next;
LOOP;
};
ENDLOOP;
UNTIL newSeg = NIL DO
IF newSeg.node = 0 THEN {
newSeg.node ← GenNodeNumber[];
RecordNodeLoc[newSeg.node, (newSeg.left+newSeg.right)/2, Center];
};
Draw[newSeg];
cap ← FindCap[newSeg.node];
AddCapArea[cap,layer,height*(newSeg.right-newSeg.left)];
AddCapPerim[cap,layer,2*(height+newSeg.right-newSeg.left)];
newSeg ← newSeg.next;
ENDLOOP;
END;

PropagateByCut: PROCEDURE =
-- propagate node numbers through contact cuts
BEGIN
cutSeg:NodeSegment;
metalSeg:NodeSegment ← oldSegList[metal];
polySeg:NodeSegment ← oldSegList[poly];
diffSeg:NodeSegment ← oldSegList[diff];
FOR cutSeg ← oldSegList[cut], cutSeg.next UNTIL cutSeg = NIL DO
UNTIL metalSeg = NIL OR cutSeg.right <= metalSeg.right DO
metalSeg ← metalSeg.next;
ENDLOOP;
IF metalSeg = NIL OR cutSeg.left < metalSeg.left THEN {
Error[(cutSeg.left+cutSeg.right)/2,Center,"Metal doesn’t surround contact cut"];
LOOP;
};
UNTIL diffSeg = NIL OR cutSeg.left <= diffSeg.right DO
diffSeg ← diffSeg.next;
ENDLOOP;
FOR p:NodeSegment ← diffSeg,p.next UNTIL p = NIL OR cutSeg.right < p.left DO
p.node ← metalSeg.node ← Combine[p.node,metalSeg.node];
diffSeg ← p;
ENDLOOP;
UNTIL polySeg = NIL OR cutSeg.left < polySeg.right DO
polySeg ← polySeg.next;
ENDLOOP;
FOR p:NodeSegment ← polySeg,p.next UNTIL p = NIL OR cutSeg.right < p.left DO
p.node ← metalSeg.node ← Combine[p.node,metalSeg.node];
polySeg ← p;
ENDLOOP;
ENDLOOP;
END;

PropagateTrans: PROCEDURE[layer:INTEGER] =
BEGIN
transistor: Node;
old:NodeSegment;
trans:NodeSegment;-- transistor segment from current swath
btrans:NodeSegment ← oldSegList[layer];-- transistor from swath below
apoly:NodeSegment ← firstNodeSeg[poly];-- poly from top swath
adiff:NodeSegment ← firstNodeSeg[diff];-- diffusion from top swath
bdiff:NodeSegment ← oldSegList[diff];-- diffusion from bottom swath
imp:NodeSegment ← firstNodeSeg[implant];-- implant from top swath

FOR trans ← firstNodeSeg[layer],trans.next UNTIL trans = NIL DO
-- find transistor below current
-- skip transistors to the left of current
UNTIL btrans = NIL OR trans.left <= btrans.right DO btrans ← btrans.next; ENDLOOP;
old ← btrans;
WHILE btrans # NIL AND btrans.left <= trans.right DO
-- propagate transistor upwards
IF trans.node = 0 THEN trans.node ← btrans.node
ELSE trans.node ← Combine[trans.node,btrans.node];
transistor ← FindTransistor[trans.node,trans.left,Bottom];
-- adjust perimeter information
transistor.perim ← transistor.perim - 2*(btrans.right - btrans.left);
old ← btrans;
btrans ← btrans.next;
ENDLOOP;
btrans ← old;
IF trans.node = 0 THEN trans.node ← GenNodeNumber[];

-- trans now has a node number, find it’s transistor record
transistor ← FindTransistor[trans.node,trans.left,Bottom];
-- compute perimeter & area information
transistor.area ← transistor.area + height*(trans.right - trans.left);
transistor.perim ← transistor.perim + 2*(trans.right - trans.left + height);

IF transistor.poly = 0 THEN {-- find apoly that overlaps it
-- skip apoly to the left of trans
UNTIL apoly = NIL OR trans.left <= apoly.right DO apoly ← apoly.next; ENDLOOP;
IF apoly # NIL AND apoly.left <= trans.right THEN transistor.poly ← apoly.node;
};

-- look for adiffusion to the left of trans
UNTIL adiff = NIL OR trans.left <= adiff.right DO adiff ← adiff.next; ENDLOOP;
IF adiff # NIL AND trans.left = adiff.right THEN {
AddDiff[transistor,adiff.node,height];
adiff ← adiff.next;
};
-- look for adiffusion to the right of trans
IF adiff # NIL AND adiff.left = trans.right THEN AddDiff[transistor,adiff.node,height];

-- look for diffusion below the trans
UNTIL bdiff = NIL OR trans.left <= bdiff.right DO bdiff ← bdiff.next; ENDLOOP;
old ← bdiff;
WHILE bdiff # NIL AND bdiff.left <= trans.right DO
AddDiff[transistor,bdiff.node,MIN[bdiff.right,trans.right]-MAX[bdiff.left,trans.left]];
old ← bdiff;
bdiff ← bdiff.next;
ENDLOOP;
bdiff ← old;

-- look for implant overlapping the trans
UNTIL imp = NIL OR trans.left <= imp.right DO imp ← imp.next; ENDLOOP;
-- test for partical overlap
IF imp # NIL AND imp.left <= trans.right THEN transistor.ion ← TRUE;
-- test for partical non-overlap
IF imp = NIL OR trans.left < imp.left OR imp.right < trans.right THEN transistor.nion ← TRUE;
ENDLOOP;
-- look for diffusion above transistors
adiff ← firstNodeSeg[diff];
FOR btrans ← oldSegList[layer],btrans.next UNTIL btrans = NIL DO
transistor ← FindTransistor[btrans.node,btrans.left,Bottom];
UNTIL adiff = NIL OR btrans.left <= adiff.right DO adiff ← adiff.next; ENDLOOP;
old ← adiff;
WHILE adiff # NIL AND adiff.left <= btrans.right DO
AddDiff[transistor,adiff.node,MIN[adiff.right,btrans.right]-MAX[adiff.left,btrans.left]];
old ← adiff;
adiff ← adiff.next;
ENDLOOP;
adiff ← old;
ENDLOOP;
END;

debug:BOOLEAN ← TRUE;-- debugging flag

y: REAL;

firstNodeSeg: ARRAY [0..MaxLayer) OF NodeSegment;-- pointer to first element of new seg list
lastNodeSeg: ARRAY [0..MaxLayer) OF NodeSegment;-- pointer to last element of new seg list
oldSegList: ARRAY [0..MaxLayer) OF NodeSegment;-- pointer to first element of old seg list
nodeNum: ARRAY [0..MaxLayer) OF NodeNumber;
Left: ARRAY [0..MaxLayer) OF REAL;

Bottom,Center,Top,height: REAL;-- bottom, center, top, & height of current swath

MaxLayer: CARDINAL = 10;

Active: ARRAY [0..MaxLayer) OF BOOLEAN ← ALL[FALSE];
count: ARRAY [0..MaxLayer) OF INTEGER;

Stipple: ARRAY [0..16) OF CARDINAL ← ALL[177777B];--undef

--Set up default stipples
Stipple[0] ← 000020B;--implant
Stipple[1] ← 040501B;--diffusion
Stipple[2] ← 014102B;--poly
Stipple[3] ← 165627B;--contact
Stipple[4] ← 000050B;--metal
Stipple[5] ← 001110B;--buried
Stipple[6] ← 001122B;--glass
Stipple[7] ← 177777B;--undef

Active[poly] ← Active[diff] ← Active[metal] ← Active[gate] ← TRUE;

END.