DIRECTORY
Basics, CD, CDBasics, CDCells, CDRects, CDSymbolicObjects, CDProperties, D2Orient, HashTable, Properties, Real, RealOps, Rope, Route, RoutePrivate, RouteChannel, RouteTechnology, RouteUtil, RTBasic;

RouteUtilImpl: CEDAR PROGRAM
IMPORTS CDBasics, CDCells, CDRects, CDSymbolicObjects, CDProperties, HashTable, Properties, Real, RealOps, Route, RouteChannel, RouteTechnology, RouteUtil, RTBasic
EXPORTS RouteUtil =
BEGIN

LayerToRoutingLayer: PUBLIC PROC [routingArea: Route.RoutingArea, layer: Route.Layer] RETURNS [routingLayer: RoutePrivate.RoutingLayer] =
BEGIN
trunkLayer: Route.Layer _ routingArea.rules.trunkLayer;
branchLayer: Route.Layer _ routingArea.rules.branchLayer;
IF layer = trunkLayer THEN routingLayer _ trunk
ELSE IF layer = branchLayer THEN routingLayer _ branch
ELSE Route.Error[programmingError, "Invalid layer"];
END;

RoutingLayerToLayer: PUBLIC PROC [routingArea: Route.RoutingArea, routingLayer: RoutePrivate.RoutingLayer] RETURNS [layer: Route.Layer] =
BEGIN
trunkLayer: Route.Layer _ routingArea.rules.trunkLayer;
branchLayer: Route.Layer _ routingArea.rules.branchLayer;
IF routingLayer = trunk THEN layer _ trunkLayer
ELSE IF routingLayer = branch THEN layer _ branchLayer
ELSE Route.Error[programmingError, "Invalid routing layer"];
END;

GetNumberProp: PUBLIC PROC [properties: Route.PropList, key: REF ATOM, default: Route.Number] RETURNS [Route.Number] =
BEGIN
valRef: REF ANY _ Properties.GetProp[properties, key];
IF valRef # NIL THEN default _ NARROW[valRef, REF Route.Number]^;
RETURN [default];
END;

PutNumberProp: PUBLIC PROC [properties: Route.PropList, key: REF ATOM, number: Route.Number] RETURNS [Route.PropList] =
BEGIN
valRef: REF Route.Number _ NEW[Route.Number _ number];
RETURN[Properties.PutProp[properties, key, valRef]];
END;

Length: PUBLIC PROC [pos1, pos2: Route.Position] RETURNS [length: Route.Number] = {
length _ Real.RoundLI[Real.SqRt[Real.FAdd[Real.FMul[Real.FSub[pos1.x, pos2.x], Real.FSub[pos1.x, pos2.x]], Real.FMul[Real.FSub[pos1.y, pos2.y], Real.FSub[pos1.y, pos2.y]]]]]};

XYToPQ: PUBLIC PROC [routingArea: Route.RoutingArea, pos: Route.Position] RETURNS [pqPos: RoutePrivate.PQPosition] =
BEGIN
chanDirection: Route.Direction _ routingArea.rules.trunkDirection;
SELECT chanDirection FROM
horizontal => RETURN[[pos.x, pos.y]];
vertical => RETURN[[pos.y, pos.x]];
ENDCASE;
END;

PQToXY: PUBLIC PROC [routingArea: Route.RoutingArea, pqPos: RoutePrivate.PQPosition] RETURNS [pos: Route.Position] =
BEGIN
chanDirection: Route.Direction _ routingArea.rules.trunkDirection;
SELECT chanDirection FROM
horizontal => RETURN[[pqPos.p, pqPos.q]];
vertical => RETURN[[pqPos.q, pqPos.p]];
ENDCASE;
END;

SimpleCompare: PUBLIC PROCEDURE [result1, result2: Route.Number]
RETURNS [result: Basics.Comparison] = {

result _ IF result1 < result2 THEN less
ELSE IF result1 > result2 THEN greater
ELSE equal
};

CompareResult: PUBLIC PROCEDURE [result1, result2: Route.RoutingResult]
RETURNS [result: Basics.Comparison] =  {

result _ RouteUtil.SimpleCompare[result1.numIncompletes, result2.numIncompletes];
IF result # equal THEN RETURN;

result _ RouteUtil.SimpleCompare[result1.numTrunkTracks, result2.numTrunkTracks];
IF result # equal THEN RETURN;

result _ RouteUtil.SimpleCompare[result1.polyLength, result2.polyLength];
IF result # equal THEN RETURN;

result _ RouteUtil.SimpleCompare[result1.polyToMetal, result2.polyToMetal];
IF result # equal THEN RETURN;

result _ RouteUtil.SimpleCompare[result1.metalToMetal2, result2.metalToMetal2];
IF result # equal THEN RETURN;

result _ RouteUtil.SimpleCompare[result1.metalLength, result2.metalLength];
IF result # equal THEN RETURN;

result _ RouteUtil.SimpleCompare[result1.metal2Length, result2.metal2Length];
RETURN;
}; -- CompareResult

CreateCDPin: PUBLIC PROC [name: Rope.ROPE, rect: CD.Rect, lev: CD.Layer] RETURNS [cdPin: CD.Instance] = {
r: CD.Rect _ CDBasics.ReInterpreteRect[rect];
cdPinObj: Route.Object _ CDSymbolicObjects.CreatePin[[r.x2-r.x1, r.y2-r.y1]];
cdPin _ CDSymbolicObjects.CreateSymInst[name, r, 0, lev];
CDSymbolicObjects.SetName[cdPin, name];
CDSymbolicObjects.SetLayer[cdPin, lev]};


GetPinWidth: PUBLIC PROC [routingArea: Route.RoutingArea, connections: Route.PinList, channelDirection: Route.Direction] RETURNS [widestBranchPin, widestTrunkPin: Route.Number _ 0] = {

FOR list: Route.PinList _ connections, list.rest WHILE list # NIL DO
old: Route.Pin _ list.first;
oldWidth: Route.Number;
chanSide: RouteChannel.ChanSide _ RouteChannel.ExtSideToIntSide[routingArea, old.side];
size: CD.Position _ CDBasics.OrientedSize[CDBasics.SizeOfRect[old.pin.ob.bbox], old.pin.trans.orient];

SELECT old.side FROM
bottom, top => oldWidth _ size.x;
left, right => oldWidth _ size.y;
ENDCASE;

SELECT chanSide FROM
chanBottom, chanTop => widestBranchPin _ MAX[widestBranchPin, oldWidth];
chanLeft, chanRight => widestTrunkPin _ MAX[widestTrunkPin, oldWidth];
ENDCASE;
ENDLOOP};

Include: PUBLIC PROC [cell: CD.Object_NIL, ob: CD.Object, 
position: CD.Position_[0, 0], orientation: D2Orient.Orientation_original] RETURNS [application: CD.Instance] = {

application _ CDCells.IncludeOb[design: NIL, cell: cell, ob: ob, trans: [off: position, orient: orientation], mode: dontResize].newInst};

AddPin: PUBLIC PROC [obj: Route.Object, pin: Route.Pin] = {

pinLayer: Route.Layer _ CDSymbolicObjects.GetLayer[pin.pin];
pinName: Rope.ROPE _ CDSymbolicObjects.GetName[pin.pin];
size: CD.Position _ CDBasics.SizeOfRect[pin.pin.ob.bbox];
location: CD.Position _ CDBasics.BaseOfRect[CDBasics.MapRect[pin.pin.ob.bbox, pin.pin.trans]];
pinObj: Route.Object _ CDSymbolicObjects.CreatePin[size];
application: CD.Instance _ RouteUtil.Include[obj, pinObj, location]; 
CDSymbolicObjects.SetName[application, pinName];
CDSymbolicObjects.SetLayer[application, pinLayer]};

AddVia: PUBLIC PROC [obj: Route.Object, name: Rope.ROPE, pos, size: Route.Position, layer1,  layer2: Route.Layer, cdLambda: Route.Number, viaTable: HashTable.Table] = {

value: HashTable.Value _ IF viaTable = NIL THEN NIL ELSE HashTable.Fetch[viaTable, NEW[Route.Position _ size]].value;
cell: Route.Object _ IF value # NIL THEN NARROW[value, Route.Object]
ELSE StitchVias[size, layer1, layer2, cdLambda, viaTable];
ReallyAddVia[obj, cell, name, pos]};

GetVia: PUBLIC PROC [size: Route.Position, layer1,  layer2: Route.Layer, cdLambda: Route.Number] RETURNS [cell: Route.Object _ NIL] = {


minBigContact: Route.Object _ RouteTechnology.GetBigContact[[1, 1], layer1, layer2];
IF minBigContact = NIL THEN
cell _ RouteTechnology.GetContact[layer1, layer2]
ELSE { -- big contact exists, determine size to use
contactSize: CD.Position _ CDBasics.SizeOfRect[minBigContact.bbox];
IF contactSize.x <= size.x AND contactSize.y <= size.y THEN {
perim2x2: Route.Number _ RealOps.RoundLI[size.x/(6*cdLambda), RealOps.FixMode]*RealOps.RoundLI[size.y/(6*cdLambda), RealOps.FixMode]*8*cdLambda;  -- 2x2 contacts go in a 6x6 square
perim3x3: Route.Number _ RealOps.RoundLI[size.x/(7*cdLambda), RealOps.FixMode]*RealOps.RoundLI[size.y/(7*cdLambda), RealOps.FixMode]*12*cdLambda;  -- 3x3 contacts go in a 7x7 square
perim4x4: Route.Number _ RealOps.RoundLI[size.x/(8*cdLambda), RealOps.FixMode]*RealOps.RoundLI[size.y/(8*cdLambda), RealOps.FixMode]*16*cdLambda;  -- 4x4 contacts go in a 8x8 square
SELECT TRUE FROM
perim4x4 >= perim2x2 AND perim4x4 >= perim3x3 =>
cell _ RouteTechnology.GetBigContact[[8*cdLambda, 8*cdLambda], layer1, layer2];
perim3x3 >= perim2x2 AND perim3x3 >= perim4x4 =>
cell _ RouteTechnology.GetBigContact[[7*cdLambda, 7*cdLambda], layer1, layer2];
perim2x2 >= perim4x4 AND perim2x2 >= perim3x3 =>
cell _ RouteTechnology.GetBigContact[[6*cdLambda, 6*cdLambda], layer1, layer2];
ENDCASE}
ELSE  -- big contact too big, must do it with small ones
cell _ RouteTechnology.GetContact[layer1, layer2]
}};

StitchVias: PUBLIC PROC [size: Route.Position, layer1, layer2: Route.Layer, cdLambda: Route.Number, viaTable: HashTable.Table] RETURNS [obj: Route.Object] = {

contact: Route.Object _ GetVia[size, layer1, layer2, cdLambda];
contactSize: CD.Position _ CDBasics.SizeOfRect[contact.bbox];
minSize: Route.Number _ 6*cdLambda; -- technology dependent!!! this needs to be fixed
value: HashTable.Value _ IF viaTable = NIL THEN NIL ELSE HashTable.Fetch[viaTable, NEW[Route.Position _ size]].value;
IF value # NIL THEN obj _ NARROW[value]
ELSE IF contactSize.x >= size.x AND contactSize.y >= size.y THEN
obj _ contact -- special case for performance
ELSE { 
sizeX: Route.Number _ MAX[contactSize.x, minSize];
sizeY: Route.Number _ MAX[contactSize.y, minSize];
numYInts: Route.Number _ MAX[1, size.y/sizeY];
lastYLoc: Route.Number _ 0;
lastXLoc: Route.Number;
cover: Route.Position;
obj _ CDCells.CreateEmptyCell[];
FOR index: Route.Number IN [1 .. numYInts] DO
numXInts: Route.Number _ MAX[1, size.x/sizeX];
lastXLoc _ 0;
FOR index: Route.Number IN [1 .. numXInts] DO
[] _ RouteUtil.Include[obj, contact, [lastXLoc, lastYLoc]];
lastXLoc _ lastXLoc +  sizeX;
ENDLOOP;
lastYLoc _ lastYLoc + sizeY;
ENDLOOP;
cover  _ [lastXLoc - sizeX + contactSize.x, lastYLoc - sizeY + contactSize.y];
[] _ RouteUtil.Include[obj, CDRects.CreateRect[cover, layer1]];
[] _ RouteUtil.Include[obj, CDRects.CreateRect[cover, layer2]];
RTBasic.RepositionCell[obj]}};

ReallyAddVia : PROC [obj: Route.Object, cell: Route.Object, name: Rope.ROPE, pos: Route.Position] = {
cellSize: CD.Position _ CDBasics.SizeOfRect[cell.bbox];
position: CD.Position _ [pos.x - cellSize.x/2, pos.y - cellSize.y/2];
application: CD.Instance _ RouteUtil.Include[obj, cell, position];
CDProperties.PutProp[application, $SignalName, name]};

LineToRect: PUBLIC PROC [pos1, pos2: Route.Position, width: Route.Number] RETURNS [position: CD.Position, size: CD.Position] = {

SELECT TRUE FROM
pos1.x = pos2.x => { -- line is vertical
size _ [width, ABS[pos1.y - pos2.y]];
position _ [pos1.x - width/2, MIN[pos1.y, pos2.y]]};
pos1.y = pos2.y => { -- line is horizontal
size _ [ABS[pos1.x - pos2.x], width];
position _ [MIN[pos1.x, pos2.x], pos1.y - width/2]};
ENDCASE => Route.Error[programmingError, "Diagional lines not allowed."]};
END. 


RouteUtilImpl.mesa
Copyright c 1985, 1987 by Xerox Corporation.  All rights reserved.
by Bryan Preas   July 10, 1985 6:57:00 pm PDT 
last edited by Bryan Preas   February 5, 1987 8:08:43 pm PST
return lent of line segment from pos1 to pos2.

convert a position from x-y to p-q space.

convert a position from p-q to x-y space.

Create a ChipNDale pin.  Calls CDSymbolicObjects.CreatePin but normalizes th rectangle first.

Find the widest pin in connections in channelDirection.
include an object in a design
this is technology dependent; this needs to be fixed
cmosB via rules are used if 'Big Contacts" exist
no big contacts, must do it with small ones
use 2, 3, or 4 lambda square vias tha give largest perimeter 
convert a line and a width to a rectangle and an orgin
Κ	&˜Icodeš
œ™˜Kšœ
Οm
œ7™BKšœ*Οkœ
™.Kšœž™<—K˜š
ž	˜	KšœžœΌ
˜Ζ
K˜—šΟn
œžœ
ž˜Kšžœœ
˜£
Kšžœ˜Kš
ž˜K˜šŸœžœ
žœ6žœ,˜‰
Kš
ž˜Kš
œ7˜7Kš
œ9˜9Kšžœžœ˜/Kšžœ
žœžœ˜6Kšžœ0˜4Kšžœ˜—šŸœžœ
žœKžœ˜‰
Kš
ž˜Kš
œ7˜7Kš
œ9˜9Kšžœžœ˜/Kšžœ
žœžœ˜6Kšžœ8˜<Kšžœ
˜—K˜šŸ
œžœ
žœ#žœ
žœžœ˜vKš
ž˜Kšœžœ
žœ'˜6Kš
žœ
žœ
žœžœ	žœ˜AKšžœ˜Kšžœ
˜—K˜šŸ
œžœ
žœ#žœ
žœžœ˜wKš
ž˜Kšœžœžœ˜6Kšžœ.˜4Kšžœ
˜—K˜šŸœžœ
žœžœ˜SK™.K™Kš
œ―
˜―
—K˜šŸœžœ
žœ7žœ#˜tK™)K™Kš
ž˜Kš
œB˜Bšžœž˜Kšœžœ˜%Kšœžœ˜#Kšžœ
˜—Kšžœ
˜K˜—šŸœžœ
žœBžœ˜tK™)K™Kš
ž˜Kš
œB˜Bšžœž˜Kšœžœ˜)Kšœžœ˜'Kšžœ
˜—Kšžœ
˜—K˜šŸ
œžœ
ž	œ!˜@Kšžœ ˜'K˜Kšœ	žœžœ˜'Kšžœ
žœžœ˜&Kšžœ˜
Kš
œ˜K˜—šŸ
œžœ
ž	œ(˜GKšžœ!˜(K˜Kš
œQ˜QKšžœžœ
žœ
˜K˜Kš
œQ˜Qšžœžœ
žœ
˜K˜—Kš
œI˜Išžœžœ
žœ
˜K˜—Kš
œK˜Kšžœžœ
žœ
˜K˜—Kš
œO˜Ošžœžœ
žœ
˜K˜—Kš
œK˜Kšžœžœ
žœ
˜K˜—Kš
œM˜MKšžœ
˜KšœΟc˜K˜—šŸœžœ
žœ
žœžœžœžœ	žœ˜iKš
œ]™]K™Kšœžœ(˜-Kš
œM˜MKš
œ9˜9Kš
œ'˜'Kš
œ(˜(K˜—K˜šΠbnœžœ
žœažœ8˜Έ
Kš
œ7™7K˜šžœ.žœžœ
ž˜DKš
œ˜K˜Kš
œW˜WKšœžœ^˜fK˜šžœ
ž˜Kš
œ!˜!Kš
œ!˜!Kšžœ
˜—K˜šžœ
ž˜Kšœ)žœ˜HKšœ(žœ˜FKšžœ
˜—Kšžœ˜	——K˜šŸœžœ
žœžœžœžœ	˜:Kšœ
žœ>žœžœ˜pK™K˜Kšœ(žœ^˜‰
—K˜šŸœžœ
žœ(˜;K˜Kš
œ<˜<Kšœžœ&˜8Kšœžœ1˜9Kšœ
žœR˜^Kš
œ9˜9Kšœ
žœ6˜EKš
œ0˜0Kš
œ3˜3K˜—šŸœžœ
žœ žœq˜¨
K˜Kš
œu˜uš	œžœ	žœ
žœ
žœ˜DKšžœ6˜:—Kš
œ$˜$K˜—š
Ÿœžœ
žœNžœžœ˜‡
K˜š
œ4™4Kš
œ0™0K˜—Kš
œT˜Tšžœžœ
ž˜Kš
œ+™+Kš
œ1˜1—šžœ ,˜3Kšœ
žœ4˜Cšžœžœžœ˜=Kš
œ=™=Kšœ’
 "˜΄
Kšœ“
 "˜΅
Kšœ“
 "˜΅
šžœ
žœ
ž˜šœžœ˜0Kš
œO˜O—šœžœ˜0Kš
œO˜O—šœžœ˜0Kš
œO˜O—Kšžœ
˜——šžœ 2˜8Kš
œ1˜1—Kš
œ˜—K˜—šŸ
œžœ
žœhžœ˜ž
K˜Kš
œ?˜?Kšœ
žœ.˜=Kšœ$ 1˜UKš
œu˜uKšžœ	žœ
žœžœ˜'šžœ
žœžœž˜@Kšœ ˜-—šžœ˜Kšœžœ˜2Kšœžœ˜2Kšœžœ˜.Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ ˜ šžœžœž˜-Kšœžœ˜.Kš
œ
˜
šžœžœž˜-Kš
œ;˜;Kš
œ˜Kšžœ
˜—Kš
œ˜Kšžœ
˜—Kš
œN˜NKš
œ?˜?Kš
œ?˜?Kš
œ˜—K˜—šŸœžœ4žœ˜eKšœ
žœ+˜7Kšœ
žœ9˜EKšœ
žœ3˜BKš
œ6˜6K˜—šŸ
œžœ
žœ3žœžœžœ˜€
Kš
œ6™6K˜šžœ
žœ
ž˜šœ ˜(Kšœžœ˜%Kšœžœ˜4—šœ ˜*Kšœžœ˜%Kšœžœ%˜4—KšžœC˜J——Kšžœ˜—K˜—…—'V3†