-- 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.
(672)\189b10B809b9B386b16B117i13I264b8B178b8B516b6B286i37I208b13B171b15B338b14B120i72I152i42I244i30I26b10B37b4B812i42I7i66I282i50I925b15B1076b15B102i37I46i27I46i19I46i24I45i27I48i22I72i29I6i39I163i28I175i28I205i56I295i5I5i17I7i5I5i21I178i9I5i26I211i9I5i27I97i34I313i38I79i25I77i29I112i36I518i14I66i40I54i39I53i40I118i46I