DIRECTORY
CD,
CDBasics,
CDPinObjects,
CDProperties,
CDRects,
Rope,
Route,
RouteChannel,
RoutePrivate,
RouteUtil;

RouteChannelRetrieveImpl: CEDAR PROGRAM
IMPORTS CDBasics, CDPinObjects, CDProperties, CDRects, Route, RouteChannel, RouteUtil
EXPORTS RouteChannel
SHARES Route = {

GetRouting: PUBLIC PROCEDURE[routingArea: Route.RoutingArea,
rect: Route.Rect,
properties: Route.PropList,
EnumSegments: RouteChannel.EnumSegmentsProc,
EnumPins: RouteChannel.EnumPinsProc,
EnumVias: RouteChannel.EnumViasProc,
EnumExits: RouteChannel.EnumExitsProc,
EnumIncompletes: RouteChannel.EnumIncompletesProc] RETURNS [externalConnections: Route.PinList _ NIL] = {

EachTrack: RouteChannel.EachTrackActionProc = {
FOR seg: RouteChannel.Segment _ RouteChannel.TrackSegAbs[routingArea, trackIndex], seg.nextSeg
WHILE seg # NIL DO

trackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, seg.trackNum];
leftPin: RouteChannel.ChanPin _ seg.exteriorPins[chanLeft];
rightPin: RouteChannel.ChanPin _ seg.exteriorPins[chanRight];
leftPinPosition: Route.Number _ PinPos[leftPin];
rightPinPosition: Route.Number _ PinPos[rightPin];
leftBranchWidth, rightBranchWidth: Route.Number _ 0;
segLayer: Route.Layer _ RouteUtil.RoutingLayerToLayer[routingArea, seg.routingLayer];
activeSegSpec.seg _ seg;

RouteChannel.CheckPins[seg, leftPin, chanRight];
RouteChannel.CheckPins[seg, rightPin, chanLeft];

leftBranchWidth _ AnalyzeBranch[routingArea, seg.exteriorPins[chanLeft].pinPosition, seg, chanLeft, chanRight];

FOR pinList: RouteChannel.ChanPinList _ seg.interiorPins, pinList.rest WHILE pinList # NIL DO
pin: RouteChannel.ChanPin _ pinList.first;
[] _ AnalyzeBranch[routingArea, pin.pinPosition, seg, chanLeft, chanRight];
ENDLOOP;

IF RouteChannel.FollowingSeg[routingArea, activeSegSpec, activeTrackSpec, FALSE] = NIL THEN
{IF seg.trackNum # 0 THEN
rightBranchWidth _ AnalyzeBranch[routingArea, rightPin.pinPosition, seg, chanRight, chanLeft]};

IF rightPinPosition > leftPinPosition THEN
EnumSegments[routingArea, seg.net.name, seg.net.netPart,
RouteUtil.PQToXY[routingArea, [leftPinPosition - leftBranchWidth/2, trackLoc]],
RouteUtil.PQToXY[routingArea, [rightPinPosition + rightBranchWidth/2, trackLoc]],
seg.qWidth, segLayer];

ENDLOOP};

PinPos: PROCEDURE[pin: RouteChannel.ChanPin] RETURNS [pos: Route.Number] = {
IF pin.kindOfPin # exitPin THEN pos _ pin.pinPosition.pLoc
ELSE {
pos _ IF pin.pinSide = chanLeft THEN pos1.p
ELSE IF pin.pinSide = chanRight THEN pos2.p
ELSE Route.Error[programmingError, "Invalid data. Call maintainer."]}};
EachPin: RouteChannel.EachPinActionProc = {

IF pin # NIL THEN
IF pin.kindOfPin # noPin THEN {
seg: RouteChannel.Segment _ pin.conctSeg[chanRight];
IF seg # NIL THEN {
leftPinPosition: Route.Number _ seg.exteriorPins[chanLeft].pinPosition.pLoc;
rightPinPosition: Route.Number _ seg.exteriorPins[chanRight].pinPosition.pLoc;
RouteChannel.CheckSegs[seg, pin];
IF (seg.trackNum = 0 AND leftPinPosition # rightPinPosition) OR seg.failed THEN {
qLoc: Route.Number _ IF seg.trackNum = 0 THEN 0
ELSE RouteChannel.TrackLoc[routingArea, seg.trackNum];
EnumIncompletes[routingArea, seg.net.name, seg.net.netPart,
RouteUtil.PQToXY[routingArea, [leftPinPosition, qLoc]],
RouteUtil.PQToXY[routingArea, [rightPinPosition, qLoc]]]}}}};

AnalyzeBranch: PROCEDURE[routingArea: Route.RoutingArea,
branchPos: RouteChannel.PinPosition,
segmentLink: RouteChannel.Segment,
branchSide, segmentSide: RouteChannel.ChanLRSide] RETURNS [branchWidth: Route.Number] = {

AnalyzeEachPin: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN {
SELECT pin.kindOfPin FROM

chanConnect, compPin => {
seg: RouteChannel.Segment _ pin.conctSeg[segmentSide];
IF seg # NIL THEN {
segLength: Route.Number _ RouteChannel.Length[seg];
IF seg = segmentLink THEN
{trackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, seg.trackNum];
otherSeg: RouteChannel.Segment;
qLoc: Route.Number;
pLoc: Route.Number _ pin.pinPosition.pLoc;
newPin: Route.Pin;

SELECT pin.pinSide FROM
chanTop => {
qLoc _ topLoc + pin.qLoc;
upperMaxQ _ MAX[upperMaxQ, qLoc];
upperMinQ _ MIN[upperMinQ, qLoc];
upperBranchWidth _ MAX[upperBranchWidth, pin.pWidth]};

chanBottom => {
qLoc _ bottomLoc + pin.qLoc;
lowerMaxQ _ MAX[lowerMaxQ, qLoc];
lowerMinQ _ MIN[lowerMinQ, qLoc];
lowerBranchWidth _ MAX[lowerBranchWidth, pin.pWidth]};
ENDCASE;

newPin _ BuildPin[routingArea, pin, seg, [pLoc, qLoc]];
EnumPins[routingArea, seg.net.name, seg.net.netPart, RouteUtil.PQToXY[routingArea, [pLoc, qLoc]], branchL, newPin];
IF seg.routingLayer = trunk AND segLength > 0 THEN
EnumVias[routingArea, seg.net.name, seg.net.netPart,
RouteUtil.PQToXY[routingArea, [pin.pinPosition.pLoc, trackLoc]],
RouteUtil.PQToXY[routingArea, [pin.pWidth, seg.qWidth]],
trunkL, branchL];

otherSeg _ pin.conctSeg[branchSide];
IF otherSeg # NIL THEN
IF otherSeg.trackNum # 0 THEN {
otherTrackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, otherSeg.trackNum];

IF (otherTrackLoc # 0) AND (otherTrackLoc # trackLoc OR otherSeg.routingLayer # segmentLink.routingLayer) THEN {
otherSegLength: Route.Number _ RouteChannel.Length[otherSeg];
upperMaxQ _ MAX[upperMaxQ, otherTrackLoc + otherSeg.qWidth/2];
upperMinQ _ MIN[upperMinQ, otherTrackLoc - otherSeg.qWidth/2];
lowerMaxQ _ MAX[lowerMaxQ, otherTrackLoc + otherSeg.qWidth/2];
lowerMinQ _ MIN[lowerMinQ, otherTrackLoc - otherSeg.qWidth/2];
IF otherSeg.routingLayer = trunk AND otherSegLength > 0 THEN
EnumVias[routingArea, seg.net.name,
seg.net.netPart,
RouteUtil.PQToXY[routingArea, [pin.pinPosition.pLoc, otherTrackLoc]],
RouteUtil.PQToXY[routingArea, [pin.pWidth, seg.qWidth]],
trunkL, branchL];
}}}};
};

dogLeg => {
segList: RouteChannel.SegmentList _ RouteChannel.GetSegsOnPin[pin];
FOR segs: RouteChannel.SegmentList _ segList, segs.rest WHILE segs # NIL DO
seg: RouteChannel.Segment _ segs.first;
IF seg.trackNum # 0 THEN {
trackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, seg.trackNum];
IF trackLoc # 0 THEN
{lowerBranchWidth _ MAX[lowerBranchWidth, pin.pWidth];
upperBranchWidth _ MAX[upperBranchWidth, pin.pWidth];
upperMaxQ _ MAX[upperMaxQ, trackLoc + seg.qWidth/2];
upperMinQ _ MIN[upperMinQ, trackLoc - seg.qWidth/2];
lowerMaxQ _ MAX[lowerMaxQ, trackLoc + seg.qWidth/2];
lowerMinQ _ MIN[lowerMinQ, trackLoc - seg.qWidth/2];
IF seg.routingLayer = trunk THEN
EnumVias[routingArea, seg.net.name,
seg.net.netPart,
RouteUtil.PQToXY[routingArea, [pin.pinPosition.pLoc, trackLoc]],
RouteUtil.PQToXY[routingArea, [pin.pWidth, seg.qWidth]],
trunkL, branchL];
}};
ENDLOOP};

exitPin => {
seg: RouteChannel.Segment _ pin.conctSeg[segmentSide];
IF seg # NIL THEN
IF seg = segmentLink AND seg.trackNum # 0 THEN {
exitP: Route.Number _ PinPos[pin];
exitQ: Route.Number _ RouteChannel.TrackLoc[routingArea, seg.trackNum];
exitPos: Route.Position _ RouteUtil.PQToXY[routingArea, [exitP, exitQ]];
layer: Route.Layer _ RouteUtil.RoutingLayerToLayer[routingArea, seg.routingLayer];
newPin: Route.Pin _ BuildPin[routingArea, pin, seg, [exitP, exitQ]];
externalConnections _ CONS[newPin, externalConnections];
EnumExits[routingArea, seg.net.name, seg.net.netPart, exitPos, layer, newPin, seg.exitBreak]}};
ENDCASE}};

trackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, segmentLink.trackNum];
trunkL: Route.Layer _ RouteUtil.RoutingLayerToLayer[routingArea, trunk];
branchL: Route.Layer _ RouteUtil.RoutingLayerToLayer[routingArea, branch];
lowerMaxQ, upperMaxQ: Route.Number _ trackLoc + segmentLink.qWidth/2;
lowerMinQ, upperMinQ: Route.Number _ trackLoc - segmentLink.qWidth/2;
lowerBranchWidth, upperBranchWidth: Route.Number  _ 0;

[] _ RouteChannel.EnumPins[routingArea, branchPos, AnalyzeEachPin];

IF lowerMaxQ > lowerMinQ + segmentLink.qWidth AND lowerBranchWidth > 0 THEN
EnumSegments[routingArea, segmentLink.net.name, segmentLink.net.netPart,
RouteUtil.PQToXY[routingArea, [branchPos.pLoc, lowerMinQ]],
RouteUtil.PQToXY[routingArea, [branchPos.pLoc, lowerMaxQ]],
lowerBranchWidth, branchL];
IF upperMaxQ > upperMinQ + segmentLink.qWidth AND upperBranchWidth > 0 AND (lowerMaxQ # upperMaxQ OR lowerMinQ # upperMinQ) THEN
EnumSegments[routingArea, segmentLink.net.name, segmentLink.net.netPart,
RouteUtil.PQToXY[routingArea, [branchPos.pLoc, upperMinQ]],
RouteUtil.PQToXY[routingArea, [branchPos.pLoc, upperMaxQ]],
upperBranchWidth, branchL];
branchWidth _ MAX[lowerBranchWidth, upperBranchWidth];
}; -- AnalyzeBranch

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks;
chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
nRect: Route.Rect _ CDBasics.NormalizeRect[rect];
pos1: RoutePrivate.PQPosition _ RouteUtil.XYToPQ[routingArea, [nRect.x1, nRect.y1]];
pos2: RoutePrivate.PQPosition _ RouteUtil.XYToPQ[routingArea, [nRect.x2, nRect.y2]];
bottomLoc: Route.Number _ pos1.q - chanData.chanSides[chanBottom].routeAreaCoord;
topLoc: Route.Number _ MAX[pos2.q, RouteChannel.ChannelWidth[routingArea]];
activeSegSpec: RouteChannel.ActiveSegSpec _ NEW[RouteChannel.ActiveSegSpecRec];
activeTrackSpec: RouteChannel.ActiveTrackSpec _ NEW[RouteChannel.ActiveTrackSpecRec];

[] _ RouteChannel.EnumTracks[routingArea, EachTrack];
FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO
[] _ RouteChannel.EnumPins[routingArea, chanPins.sides[index], EachPin];
ENDLOOP};

BuildPin: PROCEDURE[routingArea: Route.RoutingArea, iPin: RouteChannel.ChanPin, seg: RouteChannel.Segment, pos: RoutePrivate.PQPosition] RETURNS [pin: Route.Pin] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
pinName: Rope.ROPE;
layer: Route.Layer;
loc: Route.Rect;
side: Route.Side;
cdPin: CD.Instance;
p1, p2: Route.Position;
p, q, pO, qO: Route.Number;
iSide: RouteChannel.ChanSide;

IF iPin.pin = NIL THEN { -- this is a constructed pin
iSide _ IF pos.p <= chanPins.cEnd1 THEN chanLeft ELSE chanRight;
side _ RouteChannel.IntSideToExtSide[routingArea, iSide];
q _ seg.net.trunkWidth/2;
p _ routingArea.rules.CDLambda/2;
layer _ RouteUtil.RoutingLayerToLayer[routingArea, trunk];
pinName _ seg.net.name}

ELSE { -- this exit came from the client
iSide _ iPin.pinSide;
IF iSide = chanBottom OR iSide = chanTop THEN
{p _ iPin.pWidth/2; q _ routingArea.rules.CDLambda/2}
ELSE {
p _ routingArea.rules.CDLambda/2; q _ seg.net.trunkWidth/2};
side _ RouteChannel.IntSideToExtSide[routingArea, iPin.pinSide];
layer _ RouteUtil.RoutingLayerToLayer[routingArea, iPin.pin.layer];
pinName _ iPin.pin.name};

SELECT iSide FROM
chanBottom => {pO _ 0; qO _ q};
chanRight => {pO _ -p; qO _ 0};
chanTop => {pO _ 0; qO _ -q};
chanLeft => {pO _ p; qO _ 0};
ENDCASE;

p1 _ RouteUtil.PQToXY[routingArea, [pos.p - p + pO, pos.q - q + qO]];
p2 _ RouteUtil.PQToXY[routingArea, [pos.p + p + pO, pos.q + q + qO]];
loc _ [p1.x, p1.y, p2.x, p2.y];
cdPin _ RouteUtil.CreateCDPin[pinName, loc, layer];
pin _ NEW[Route.PinRec _ [cdPin, side]];
};

RetrieveSegments: PUBLIC RouteChannel.EnumSegmentsProc = {

application: CD.Instance;
ob: CD.Object;
rectSize, position: CD.Position;
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
[position, rectSize] _RouteUtil.LineToRect[pos1, pos2, width];
ob _ CDRects.CreateRect[rectSize, layer];
application _ RouteUtil.Include[parms.object, ob, position]; 
CDProperties.PutPropOnInstance[application, $SignalName, name]};

RetrieveVias: PUBLIC RouteChannel.EnumViasProc ={

parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
RouteUtil.AddVia[parms.object, name, pos, size, layer1, layer2]};

RetrievePins: PUBLIC RouteChannel.EnumPinsProc = {

pinLayer: Route.Layer _ CDPinObjects.GetLayer[pin.pin];
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
RouteUtil.AddPin[parms.object, pin];
IF pinLayer # layer THEN
Route.Signal[errorType: callingError, explanation: "Pin on invalid layer"]};

RetrieveExits: PUBLIC RouteChannel.EnumExitsProc = {

pinLayer: Route.Layer _ CDPinObjects.GetLayer[pin.pin];
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
RouteUtil.AddPin[parms.object, pin];
IF pinLayer # layer THEN
Route.Signal[errorType: callingError, explanation: "Channel or switchBox exit on invalid layer"]};

RetrieveIncompletes: PUBLIC RouteChannel.EnumIncompletesProc = {};

}.



®RouteChannelRetrieveImpl.mesa   ///Route/RouteChannelRetrieveImpl.mesa
Bryan Preas February 13, 1986 7:26:57 pm PST
Copyright c 1985, 1986 by Xerox Corporation.  All rights reserved.
by Bryan Preas   July 26, 1985 2:29:20 pm PDT 
last edited by Bryan Preas   July 26, 1985 2:29:22 pm PDT
Enumerate routing results entities

run through the segments on the track
audit the pins to which this segment point
figure out the left branch
process the interior pins
do the right branch if no following segment
enumerate trunk segment

pin is present, look at the segments on the right side
a routing failure

analyze the branch for this segment
problems with dogleg outside pin range
lowerBranchWidth _ MAX[lowerBranchWidth, pin.pWidth];
upperBranchWidth _ MAX[upperBranchWidth, pin.pWidth];
analyze component pin branches
enumerate this branch segment

enumerate the incompletes and audit the segments
build a pin record for the external exit
�Ê
f˜š
œF™FIcode™,—˜Jšœ
Ïm
œ7™BJš
œ.™.Jš
œ9™9—J˜š
Ïk	˜	Jšžœ
˜J˜	J˜
Jš
œ
˜
J˜J˜Jš
œ˜J˜
J˜
Jš
œ
˜
J˜—šœžœ
ž˜'JšžœN˜UJšžœ
˜Jšžœ
˜J˜šÏn
œžœ
ž	œ ˜<Jš
œ˜Jš
œ˜Jš
œ,˜,Jš
œ$˜$Jš
œ$˜$Jš
œ&˜&Jšœ3žœ'žœ˜iJš
œ"™"J˜š
œ/˜/J™Jš
œ%™%šžœ[˜^Jšžœžœ
ž˜J˜Jš
œJ˜JJš
œ;˜;Jš
œ=˜=Jš
œ0˜0Jš
œ2˜2Jš
œ4˜4Jš
œU˜UJš
œ˜J˜Jš
œ*™*Jš
œ0˜0Jš
œ0˜0J˜Jš
œ™Jš
œo˜oJ˜Jš
œ™šžœDžœžœ
ž˜]Jš
œ*˜*Jš
œK˜KJšžœ
˜J˜—Jš
œ+™+šžœHžœžœ
ž˜[šœ
žœž˜Jš
œ_˜_——J˜Jš
œ™šžœ$ž˜*š
œ8˜8Jš
œO˜OJš
œQ˜QJš
œ˜——J˜Jšžœ˜	—J˜—šŸœž	œžœ˜LJšžœžœ˜:šžœ˜Jšœžœžœ˜+Jšžœ
žœžœ˜+JšžœC˜G—J™—š
œ+˜+J˜šžœžœ
ž˜šžœžœ˜Jš
œ6™6Jš
œ4˜4šžœžœ
žœ˜Jš
œL˜LJš
œN˜NJš
œ!˜!šžœžœ%žœžœ˜QJš
œ™šœžœžœ˜/Jšžœ2˜6—š
œ;˜;Jš
œ7˜7Jš
œ=˜=—————J˜—šŸ
œž	œ ˜8Jš
œ$˜$Jš
œ"˜"Jšœ2žœ ˜YJ™Jš
œ#™#J™&J˜˜2šžœžœ
žœ˜šžœž˜J˜š
œ˜Jš
œ6˜6šžœžœ
žœ˜Jš
œ3˜3šžœž˜Jš
œK˜KJš
œ˜Jš
œ˜Jš
œ*˜*J˜J˜šžœ
ž˜š
œ˜Jš
œ˜Jšœžœ˜!Jšœžœ˜!Jšœžœ ˜6—J˜š
œ˜Jš
œ˜Jšœžœ˜!Jšœžœ˜!Jšœžœ ˜6—Jšžœ
˜—J˜Jš
œ7˜7Jš
œs˜sšžœžœž˜2š
œ4˜4Jš
œ@˜@Jš
œ8˜8Jš
œ˜——J˜Jš
œ$˜$šžœžœ
ž˜šžœžœ˜Jš
œT˜TJ˜šžœžœžœ3žœ˜pJš
œ=˜=Jšœžœ/˜>Jšœžœ/˜>Jšœžœ/˜>Jšœžœ/˜>šžœžœž˜<š
œ#˜#Jš
œ˜Jš
œE˜EJš
œ8˜8Jš
œ˜——Jš
œ˜—————Jš
œ˜—J˜š
œ˜Jš
œC˜Cšžœ5žœžœ
ž˜KJš
œ'˜'šžœžœ˜Jš
œJ˜Jšžœž˜Jšœžœ˜6Jšœžœ˜5Jšœžœ%˜4Jšœžœ%˜4Jšœžœ%˜4Jšœžœ%˜4šžœž˜ š
œ#˜#Jš
œ˜Jš
œ@˜@Jš
œ8˜8Jš
œ˜——Jš
œ˜——Jšžœ˜	——J˜š
œ˜Jš
œ6˜6šžœžœ
ž˜šžœžœžœ˜0J˜"Jš
œG˜GJš
œH˜HJš
œR˜RJš
œD˜DJš
œ5™5Jš
œ5™5Jšœžœ˜8Jš
œ_˜_———Jšžœ˜
——J˜—Jš
œR˜RJš
œH˜HJš
œJ˜JJš
œE˜EJš
œE˜EJš
œ6˜6J˜Jš
œ™Jš
œC˜CJ˜Jš
œ™šžœ,žœž˜Kš
œH˜HJš
œ;˜;Jš
œ;˜;Jš
œ˜——š	žœ,žœžœžœž˜€
š
œH˜HJš
œ;˜;Jš
œ;˜;Jš
œ˜——Jšœžœ%˜6Jšž
œÏcŸ
˜—J˜Jšœ%žœ˜EJš
œD˜DJš
œ>˜>J˜1J˜TJ˜TJš
œQ˜QJšœžœ1˜KJšœ,žœ ˜OJšœ0žœ"˜UJ˜Jš
œ5˜5J™Jš
œ0™0šžœžœž˜=Jš
œH˜HJšžœ˜	——J˜šŸœž	œvžœ˜¥
J™(J˜Jšœ%žœ˜EJš
œ>˜>Jšœžœ
˜Jš
œ˜J˜Jš
œ˜Jšœžœ
˜Jš
œ˜J˜Jš
œ˜J˜šžœžœ
žœ ˜5Jšœžœžœ
žœ˜@Jš
œ9˜9J˜Jš
œ!˜!Jš
œ:˜:Jš
œ˜—šœ
žœ
 !˜)Jš
œ˜šžœžœž˜-Jš
œ5˜5—šžœ˜Jš
œ<˜<—Jš
œ@˜@Jš
œC˜CJš
œ˜—J˜šžœž˜J˜J˜J˜J˜Jšžœ
˜J˜—Jš
œE˜EJš
œE˜EJ˜Jš
œ3˜3Jšœžœ˜(Jš
œ˜—J˜šœžœ"˜:J˜Jšœ
žœ
˜Jšœžœ˜Jšœžœ
˜ Jšœ'žœ˜AJš
œ>˜>Jš
œ)˜)Jš
œ=˜=Jš
œ@˜@J˜—šœžœ˜1J˜Jšœ'žœ˜AJš
œA˜AJ˜—šœžœ˜2J˜Jš
œ7˜7Jšœ'žœ˜AJš
œ$˜$šžœž˜Jš
œL˜L—J˜—šœžœ˜4J˜Jš
œ7˜7Jšœ'žœ˜AJš
œ$˜$šžœž˜Jš
œb˜b—J˜—Jšœžœ'˜BJ˜Jš
œ˜—J˜J˜J˜—…—/Ä=Ø