RouteChannelInitImpl.mesa
Copyright Ó 1985, 1987, 1988 by Xerox Corporation. All rights reserved.
by Bryan Preas July 10, 1985 6:57:00 pm PDT
last edited by Bryan Preas July 26, 1988 5:24:09 pm PDT
Christian Le Cocq January 19, 1988 9:52:19 am PST
DIRECTORY
Basics, CD, CDBasics, DABasics, List, Rope, Route, RouteChannel, RoutePrivate, RouteUtil, RTBasic;
RouteChannelInitImpl: CEDAR PROGRAM
IMPORTS CDBasics, List, Rope, Route, RouteChannel, RouteUtil, RTBasic
EXPORTS RouteChannel = {
ChanSideName: PUBLIC ARRAY RouteChannel.ChanSide OF Rope.ROPE ← ["chanBottom", "chanTop", "chanLeft", "chanRight"];
AboveOrBelowName: PUBLIC ARRAY RouteChannel.AboveOrBelow OF Rope.ROPE ← ["above", "below"];
GoingName: PUBLIC ARRAY RouteChannel.GoingDirection OF Rope.ROPE ← ["leftToRight", "rightToLeft"];
InitChannel: PUBLIC PROC [extSidesData: RoutePrivate.RoutingAreaSides,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
netTab: RoutePrivate.NetTab,
signalSinglePinNets,
signalCoincidentPins,
okToDiddleLLPins,
okToDiddleURPins: BOOLEAN]
RETURNS [chanData: RouteChannel.ChannelData] = {
Initialize for channel routing
nRect: DABasics.Rect ← CDBasics.ReInterpreteRect[parms.routingRect];
lowPos: RTBasic.PQPos ← RouteUtil.XYToPQ[rules, [nRect.x1, nRect.y1]];
upPos: RTBasic.PQPos ← RouteUtil.XYToPQ[rules, [nRect.x2, nRect.y2]];
rRect: RTBasic.PQRect ← [lowPos, upPos];
build the channel routing area; privatePart.constraints initialized in RouteChannelConstraintsImpl
chanData ← NEW[RouteChannel.ChannelDataRec];
chanData.constraints ← NIL;
chanData.chanSides[chanTop] ← NEW[RouteChannel.RoutingChannelSidesRec];
chanData.chanSides[chanBottom] ← NEW[RouteChannel.RoutingChannelSidesRec];
chanData.chanSides[chanLeft] ← NEW[RouteChannel.RoutingChannelSidesRec];
chanData.chanSides[chanRight] ← NEW[RouteChannel.RoutingChannelSidesRec];
chanData.chanTracks ← NEW[RouteChannel.RoutingChannelTracksRec];
chanData.chanPins ← NEW[RouteChannel.RoutingChannelPinsRec];
chanData.chanParms ← NEW[RouteChannel.ChanParmsRec];
chanData.chanParms.emptyTrackLimit ← MAX[2, RouteChannel.InfluenceTracks[rules, parms.widestTrunk]];
chanData.chanParms.maxToConvert ← 10*rules.branchToBranch;
convert sides to p-q space and build side data structures
ConvertSide[chanData, extSidesData, rules, chanBottom, rRect];
ConvertSide[chanData, extSidesData, rules, chanTop, rRect];
ConvertEnd[chanData, extSidesData, rules, chanLeft, rRect];
ConvertEnd[chanData, extSidesData, rules, chanRight, rRect];
fix up the routing area orgins
FixOrigins[chanData, rRect];
convert the nets from x-y space to p-q space
FOR netIndex: RoutePrivate.ZMaxNets IN [1 .. netTab.count] DO
InitNet[chanData, parms, rules, netTab, netTab.n[netIndex], signalSinglePinNets, signalCoincidentPins];
ENDLOOP;
SELECT parms.routerUsed FROM
switchBox => MakeSBTracks[chanData, rules, okToDiddleLLPins, okToDiddleURPins];
channel => MakeCRTracks[chanData.chanTracks, rules, parms.numTracksToUse];
ENDCASE => ERROR; --may be channel should be the default ?
IF parms.routerUsed = switchBox THEN MakeSBTracks[routingArea, okToDiddleLLPins, okToDiddleURPins]
ELSE MakeCRTracks[routingArea, parms.numTracksToUse];
DoTBBarriers[chanData, parms, rules, chanBottom];
DoTBBarriers[chanData, parms, rules, chanTop];
DoLRBarriers[chanData, chanLeft];
DoLRBarriers[chanData, chanRight];
};
ConvertSide: PROC [chanData: RouteChannel.ChannelData,
extSidesData: RoutePrivate.RoutingAreaSides,
rules: Route.DesignRules,
chanSide: RouteChannel.ChanSide,
routingRect: RTBasic.PQRect] = {
Convert a channel side to p-q space and set up side data
activeSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanSide];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
extSide: DABasics.Side ← RouteChannel.IntSideToExtSide[rules, chanSide];
extSideData: RoutePrivate.RoutingAreaSide ← extSidesData[extSide];
activeSide.enclosingBarrier ← [[0, 0], [0, 0]];
activeSide.extSide ← extSide;
chanPins.cEnd1 ← routingRect.c1.p; chanPins.cEnd2 ← routingRect.c2.p;
IF extSideData # NIL THEN {
encloseBranch: RTBasic.PQRect ← TranslateBarriers[extSidesData, rules, activeSide, branch];
encloseTrunk: RTBasic.PQRect ← TranslateBarriers[extSidesData, rules, activeSide, trunk];
activeSide.enclosingBarrier ← Surround[encloseBranch, encloseTrunk];
};
};
TranslateBarriers: PROC [extSidesData: RoutePrivate.RoutingAreaSides,
rules: Route.DesignRules,
activeSide: RouteChannel.RoutingChannelSides,
rLayer: RoutePrivate.RoutingLayer]
RETURNS [enclosingRect: RTBasic.PQRect ← [[0, 0], [0, 0]]] = {
convert routing barriers for a side
extSide: DABasics.Side ← activeSide.extSide;
extSideData: RoutePrivate.RoutingAreaSide ← extSidesData[extSide];
chanDirection: DABasics.Direction ← rules.trunkDirection;
IF extSideData # NIL THEN {
FOR bList: RoutePrivate.RoutingBarrierList ← extSideData.barrierList, bList.rest WHILE bList # NIL DO
barrierItem: RoutePrivate.RoutingBarrier ← bList.first;
generalLayer: CD.Layer ← barrierItem.layer;
IF generalLayer = CD.undefLayer OR RouteUtil.LayerToRoutingLayer[rules, generalLayer] = rLayer THEN {
FOR rList: LIST OF DABasics.Rect ← barrierItem.barrier, rList.rest WHILE rList # NIL DO
cleanRectangle: RTBasic.PQRectRef ← CheckRect[rules, rList.first, activeSide];
IF cleanRectangle # NIL THEN {
enclosingRect ← Surround[enclosingRect, cleanRectangle^];
activeSide.barrierList[rLayer] ← CONS[cleanRectangle^, activeSide.barrierList[rLayer]]};
ENDLOOP;
}
ENDLOOP;
};
};
CheckRect: PROC [rules: Route.DesignRules, rect: DABasics.Rect, activeSide: RouteChannel.RoutingChannelSides] RETURNS[cleanRect: RTBasic.PQRectRef] = {
clean up the rectangle and return it.
*** CHECK THAT PROC... ***
chanDirection: DABasics.Direction ← rules.trunkDirection;
c1: RTBasic.PQPos ← RouteUtil.XYToPQ[rules, [rect.x1, rect.y1]];
c2: RTBasic.PQPos ← RouteUtil.XYToPQ[rules, [rect.x2, rect.y2]];
RETURN[NEW[RTBasic.PQRect ← [c1, c2]]];
};
ConvertEnd: PROC [chanData: RouteChannel.ChannelData,
extSidesData: RoutePrivate.RoutingAreaSides,
rules: Route.DesignRules,
chanSide: RouteChannel.ChanSide,
routingRect: RTBasic.PQRect] = {
convert a channel end to p-q space and set up side data
activeSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanSide];
extSide: DABasics.Side ← RouteChannel.IntSideToExtSide[rules, chanSide];
extSideData: RoutePrivate.RoutingAreaSide ← extSidesData[extSide];
activeSide.extSide ← extSide;
activeSide.enclosingBarrier ← [[0, 0], [0, 0]];
IF extSideData # NIL THEN {
encloseBranch: RTBasic.PQRect ← TranslateBarriers[extSidesData, rules, activeSide, branch];
encloseTrunk: RTBasic.PQRect ← TranslateBarriers[extSidesData, rules, activeSide, trunk];
activeSide.enclosingBarrier ← Surround[encloseBranch, encloseTrunk];
};
};
FixOrigins: PROC [chanData: RouteChannel.ChannelData, routingRect: RTBasic.PQRect] = {
now that all side data is available, compute the routing area
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
leftSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanLeft];
rightSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanRight];
bottomSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanBottom];
topSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanTop];
zero: DABasics.Number ← 0; -- don't laugh
fix up the routing area
leftSide.routeAreaCoord ← chanPins.cEnd1;
rightSide.routeAreaCoord ← chanPins.cEnd2;
chanPins.cEnd1 ← chanPins.cEnd1 + MAX[zero, leftSide.enclosingBarrier.c2.p];
chanPins.cEnd2 ← chanPins.cEnd2 + MAX[zero, rightSide.enclosingBarrier.c1.p];
bottomSide.routeAreaCoord ← routingRect.c1.q;
topSide.routeAreaCoord ← routingRect.c2.q;
};
InitNet: PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
netTab: RoutePrivate.NetTab,
net: RoutePrivate.Net,
signalSinglePinNets, signalCoincidentPins: BOOLEAN] = {
Initialize for channel routing
PPinCompare: List.CompareProc = {
p1: DABasics.Number ← NARROW[ref1, RouteChannel.InternPin].location.p;
p2: DABasics.Number ← NARROW[ref2, RouteChannel.InternPin].location.p;
RETURN[IF p1 < p2 THEN Basics.Comparison.less
ELSE IF p1 = p2 THEN Basics.Comparison.equal
ELSE Basics.Comparison.greater];
};
mungedPinList, sortedPinList: List.LORA;
chanDirection: DABasics.Direction ← routingArea.rules.trunkDirection;
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
net.internPinList ← FixPins[chanData, parms, rules, net.pinList];
mungedPinList ← ConvertToLORA[NARROW[net.internPinList]];
sortedPinList ← List.Sort[mungedPinList, PPinCompare];
IF CheckChanPins[chanPins, rules, netTab, net, sortedPinList, signalSinglePinNets, signalCoincidentPins] THEN
BuildChanPinForDogleg[chanPins, parms, rules, net, sortedPinList]; -- Multiple segments per net
BuildChanPin[chanPins, parms, rules, net, sortedPinList]; -- Single segments per net
};
FixPins: PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
pList: Route.PinList]
RETURNS [fixedPins: -- List.LORA ← NIL -- RouteChannel.InternPinList ← NIL ] = {
Translate the pin coordinates from x-y space to p-q space.
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
routingRect: DABasics.Rect ← parms.routingRect;
FOR list: Route.PinList ← pList, list.rest WHILE list # NIL DO
old: Route.Pin ← list.first;
loc: RTBasic.PQPos;
new: RouteChannel.InternPin;
chanSide: RouteChannel.ChanSide ← RouteChannel.ExtSideToIntSide[rules, old.side];
activeSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanSide];
rLayer: RoutePrivate.RoutingLayer ← RouteUtil.LayerToRoutingLayer[rules, old.layer];
width: DABasics.Number ← old.max - old.min;
oldLoc: DABasics.Position ← SELECT old.side FROM
bottom => [old.min + width/2, routingRect.y1 - old.depth],
top => [old.min + width/2, routingRect.y2 + old.depth],
left => [routingRect.x1 - old.depth, old.min + width/2],
right => [routingRect.x2 + old.depth, old.min + width/2],
ENDCASE => Route.Error[programmingError, "not suppose to happen."];
SELECT chanSide FROM
chanBottom, chanTop => {
loc ← RouteUtil.XYToPQ[rules, oldLoc];
loc.q ← loc.q - activeSide.routeAreaCoord};
chanLeft => {
SELECT parms.routerUsed FROM
channel => {
loc ← [chanPins.cEnd1, 0];
width ← 0;
};
switchBox => {
loc ← RouteUtil.XYToPQ[rules, oldLoc];
loc.p ← chanPins.cEnd1};
ENDCASE => ERROR;
};
chanRight => {
SELECT parms.routerUsed FROM
channel => {
loc ← [chanPins.cEnd2, 0];
width ← 0;
};
switchBox => {
loc ← RouteUtil.XYToPQ[rules, oldLoc];
loc.p ← chanPins.cEnd2;
};
ENDCASE => ERROR;
};
ENDCASE;
new ← NEW[RouteChannel.InternPinRec ← [NIL, chanSide, loc, width, rLayer, old]];
fixedPins ← CONS[new, fixedPins];
ENDLOOP;
};
CheckChanPins: PROC [chanPins: RouteChannel.RoutingChannelPins,
rules: Route.DesignRules,
netTab: RoutePrivate.NetTab,
net: RoutePrivate.Net,
pinList: List.LORA -- RouteChannel.InternPinList --,
signalSinglePinNets, signalCoincidentPins: BOOLEAN]
RETURNS [ok: BOOLEANTRUE] = {
Check the pins for this net.
-- number of pins > 1
-- pins within range
-- pin overlap
-- pin spacing
-- max number of pins
numPins, numOverlaps: NAT ← 0;
leftExit, rightExit: BOOLEANFALSE;
branchLayer: CD.Layer ← rules.branchLayer;
trunkLayer: CD.Layer ← rules.trunkLayer;
previousPin: RouteChannel.InternPin ← NIL;
FOR pList: List.LORA -- RouteChannel.InternPinList -- ← pinList, pList.rest WHILE pList # NIL DO
this: RouteChannel.InternPin ← NARROW[pList.first];
numPins ← numPins + 1;
IF previousPin # NIL THEN { -- check for overlapping pins.
IF previousPin.chanSide = this.chanSide THEN {
rLast, rThis: RTBasic.Range;
IF previousPin.chanSide = chanBottom OR previousPin.chanSide = chanTop THEN {
rLast ← [previousPin.location.p - previousPin.pWidth/2, previousPin.location.p + previousPin.pWidth/2];
rThis ← [this.location.p - this.pWidth/2, this.location.p + this.pWidth/2]}
ELSE { -- chanSide = chanLeft OR chanSide = chanRight
rLast ← [previousPin.location.q - previousPin.pWidth/2, previousPin.location.q + previousPin.pWidth/2];
rThis ← [this.location.q - this.pWidth/2, this.location.q + this.pWidth/2]};
IF RTBasic.Overlaps[rLast, rThis] THEN {
numOverlaps ← numOverlaps + 1;
IF signalCoincidentPins OR ~(previousPin.location = this.location AND previousPin.pWidth = this.pWidth) THEN
Route.Signal[callingError, Rope.Cat[Rope.Cat["Pins overlap, net: ", net.name, ", pins: "], Rope.Cat[this.name, ", ", previousPin.name]]]; ok ← FALSE}}
};
SELECT this.chanSide FROM
chanBottom, chanTop => {
pos: DABasics.Number ← this.location.p;
IF chanPins.cEnd1 > pos OR chanPins.cEnd2 < pos THEN {
Route.Signal[callingError, Rope.Cat["Pin location out of range, net: ", net.name, ", pin: ", this.name]]; ok ← FALSE};
IF this.pin.layer # branchLayer THEN {
Route.Signal[callingError, Rope.Cat["Pin not on branch layer, net: ", net.name, ", pin: ", this.name]]; ok ← FALSE}};
chanLeft => {
IF this.pin.layer # trunkLayer THEN {
Route.Signal[callingError, Rope.Cat["Pin not on trunk layer, net: ", net.name, ", pin: ", this.name]]; ok ← FALSE};
IF leftExit THEN {
Route.Signal[callingError, Rope.Cat["Multiple channel exits: ", net.name, ", pin: ", this.name]]; ok ← FALSE};
leftExit ← TRUE};
chanRight => {
IF this.pin.layer # trunkLayer THEN {
Route.Signal[callingError, Rope.Cat["Pin not on trunk layer, net: ", net.name, ", pin: ", this.name]]; ok ← FALSE};
IF rightExit THEN {
Route.Signal[callingError, Rope.Cat["Multiple channel exits: ", net.name, ", pin: ", this.name]]; ok ← FALSE};
rightExit ← TRUE};
ENDCASE;
previousPin ← this;
ENDLOOP;
IF numPins - numOverlaps <= 1 THEN {
IF signalSinglePinNets THEN Route.Signal[callingError, Rope.Cat["Too few pins for net: ", net.name]];
ok ← FALSE};
IF netTab.count + numPins > netTab.size THEN {
Route.Signal[noResource, "Net table is too small"]; ok ← FALSE};
};
BuildChanPinForDogleg: PROC [chanPins: RouteChannel.RoutingChannelPins,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
net: RoutePrivate.Net,
pinList: List.LORA -- RouteChannel.InternPinList -- ] = {
NOTE: this is an experimental version for DogLeg testing. Must either be made permanent or discarded. Functionally replaces BuildChanPin. BTP July 26, 1988
build the channel pins data structure for this net.
NOTE: this assumes that CheckChanPins has been invoked and that the inputs are valid!!!
set up for the leftmost pin in the net
previousSeg: RouteChannel.Segment ← NIL;
previousPin: RouteChannel.InternPin ← NARROW[pinList.first];
previousPinPosition: RouteChannel.PinPosition ← chanPins.sides[FindPinPos[chanPins, previousPin.location.p]];
previousChanPin: RouteChannel.ChanPin ← BuildPin[parms, previousPin, previousPinPosition, rules.branchWidth];
SELECT previousPin.chanSide FROM
chanBottom, chanTop => IF ~PinViolation[chanPins, parms, rules, previousChanPin, net] THEN
previousPinPosition.pins[previousChanPin.pinSide] ← previousChanPin;
chanLeft, chanRight =>
previousPinPosition.innerPins ← CONS[previousChanPin, previousPinPosition.innerPins];
ENDCASE;
FOR pList: List.LORA -- RouteChannel.InternPinList -- ← pinList.rest, pList.rest WHILE pList # NIL DO
this: RouteChannel.InternPin ← NARROW[pList.first];
allPinsOverlap: BOOLEANTRUE;
useThisOne: BOOLEANTRUE;
rLast, rThis: RTBasic.Range;
IF previousPin.chanSide = chanBottom OR previousPin.chanSide = chanTop THEN {
rLast ← [previousPin.location.p - previousPin.pWidth/2, previousPin.location.p + previousPin.pWidth/2];
rThis ← [this.location.p - this.pWidth/2, this.location.p + this.pWidth/2]}
ELSE { -- chanSide = chanLeft OR chanSide = chanRight
rLast ← [previousPin.location.q - previousPin.pWidth/2, previousPin.location.q + previousPin.pWidth/2];
rThis ← [this.location.q - this.pWidth/2, this.location.q + this.pWidth/2]};
IF previousPin.chanSide = this.chanSide AND RTBasic.Overlaps[rLast, rThis] THEN
useThisOne ← FALSE;
IF this.chanSide = chanLeft OR this.chanSide = chanRight THEN
allPinsOverlap ← FALSE
ELSE
allPinsOverlap ← allPinsOverlap AND RTBasic.Equal[rLast, rThis];
IF useThisOne THEN { -- this pin is not a duplicate
seg: RouteChannel.Segment ← NEW[RouteChannel.SegmentRec ← [net: net]];
pinPosition: RouteChannel.PinPosition ← chanPins.sides[FindPinPos[chanPins, this.location.p]];
chanPin: RouteChannel.ChanPin ← BuildPin[parms, this, pinPosition, rules.branchWidth];
SELECT this.chanSide FROM
chanBottom, chanTop => IF ~PinViolation[chanPins, parms, rules, chanPin, net] THEN
pinPosition.pins[chanPin.pinSide] ← chanPin;
chanLeft, chanRight =>
pinPosition.innerPins ← CONS[chanPin, pinPosition.innerPins];
ENDCASE;
previousChanPin.conctSeg[chanLeft] ← previousSeg; previousChanPin.conctSeg[chanRight] ← seg;
chanPin.conctSeg[chanLeft] ← seg; chanPin.conctSeg[chanRight] ← NIL;
now update the segment
seg.exteriorPins[chanLeft] ← previousChanPin;
seg.exteriorPins[chanRight] ← chanPin;
seg.interiorPins ← NIL;
make a narrow trunk if pins overlap
seg.qWidth ← IF allPinsOverlap THEN rules.trunkWidth ELSE net.trunkWidth;
previousChanPin ← chanPin;
previousSeg ← seg;
};
previousPin ← this;
ENDLOOP;
};
BuildChanPin: PROC [chanPins: RouteChannel.RoutingChannelPins,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
net: RoutePrivate.Net,
pinList: List.LORA -- RouteChannel.InternPinList -- ] = {
build the channel pins data structure for this net.
NOTE: this assumes that CheckChanPins has been invoked and that the inputs are valid!!!
interiorPins: RouteChannel.ChanPinList ← NIL;
rightInternPin: RouteChannel.InternPin ← NARROW[List.NthElement[pinList, -1]];
previousPin: RouteChannel.InternPin ← NIL;
leftPin, rightPin: RouteChannel.ChanPin ← NIL;
allPinsOverlap: BOOLEANTRUE;
seg: RouteChannel.Segment ← NEW[RouteChannel.SegmentRec ← [net: net]];
FOR pList: List.LORA -- RouteChannel.InternPinList -- ← pinList, pList.rest WHILE pList # NIL DO
pinIndex: RouteChannel.ZMPinsOnCh;
pinPosition: RouteChannel.PinPosition;
chanPin: RouteChannel.ChanPin;
this: RouteChannel.InternPin ← NARROW[pList.first];
useThisOne: BOOLEANTRUE;
IF previousPin # NIL THEN {
rLast, rThis: RTBasic.Range;
IF previousPin.chanSide = chanBottom OR previousPin.chanSide = chanTop THEN {
rLast ← [previousPin.location.p - previousPin.pWidth/2, previousPin.location.p + previousPin.pWidth/2];
rThis ← [this.location.p - this.pWidth/2, this.location.p + this.pWidth/2]}
ELSE { -- chanSide = chanLeft OR chanSide = chanRight
rLast ← [previousPin.location.q - previousPin.pWidth/2, previousPin.location.q + previousPin.pWidth/2];
rThis ← [this.location.q - this.pWidth/2, this.location.q + this.pWidth/2]};
IF previousPin.chanSide = this.chanSide AND RTBasic.Overlaps[rLast, rThis] THEN
useThisOne ← FALSE;
IF this.chanSide = chanLeft OR this.chanSide = chanRight THEN
allPinsOverlap ← FALSE
ELSE
-- make a narrow trunk if pins overlap
allPinsOverlap ← allPinsOverlap AND RTBasic.Equal[rLast, rThis]
};
IF useThisOne THEN {
pinIndex ← FindPinPos[chanPins, this.location.p];
pinPosition ← chanPins.sides[pinIndex];
chanPin ← BuildPin[parms, this, pinPosition, rules.branchWidth];
SELECT this.chanSide FROM
chanBottom, chanTop => IF ~PinViolation[chanPins, parms, rules, chanPin, net] THEN
pinPosition.pins[chanPin.pinSide] ← chanPin;
chanLeft, chanRight =>
pinPosition.innerPins ← CONS[chanPin, pinPosition.innerPins];
ENDCASE;
IF leftPin = NIL THEN {
leftPin ← chanPin; chanPin.conctSeg[chanLeft] ← NIL; chanPin.conctSeg[chanRight] ← seg}
ELSE IF this = rightInternPin THEN {
rightPin ← chanPin; chanPin.conctSeg[chanRight] ← NIL; chanPin.conctSeg[chanLeft] ← seg}
ELSE {
interiorPins ← CONS[chanPin, interiorPins]; chanPin.conctSeg[chanRight] ← seg; chanPin.conctSeg[chanLeft] ← seg}};
previousPin ← this;
ENDLOOP;
now update the segment
seg.exteriorPins[chanLeft] ← leftPin;
seg.exteriorPins[chanRight] ← rightPin;
seg.interiorPins ← interiorPins;
seg.qWidth ← IF allPinsOverlap THEN rules.trunkWidth ELSE net.trunkWidth;
};
FindPinPos: PUBLIC PROC [chanPins: RouteChannel.RoutingChannelPins, thisPLoc: DABasics.Number] RETURNS [index: RouteChannel.ZMPinsOnCh ← 0] = {
build the PinPosition data structure for this pin at thisPLoc.
NOTE: this assumes that CheckChanPins has been invoked and that the inputs are valid!!!
found: BOOLEANFALSE;
FOR pIndex: RouteChannel.ZMPinsOnCh IN [1 .. chanPins.count] WHILE ~found DO
pLoc: DABasics.Number ← chanPins.sides[pIndex].pLoc;
IF pLoc > thisPLoc THEN
{ -- add a new pinPosition
found ← TRUE;
MovePins[chanPins, pIndex];
index ← pIndex;
chanPins.sides[pIndex] ← NEW[RouteChannel.PinPositionRec ← [index, thisPLoc]]}
ELSE IF pLoc = thisPLoc THEN
{ -- pin position already taken, use it
found ← TRUE;
index ← pIndex};
ENDLOOP;
IF ~found THEN { -- this pin goes after the last pin
chanPins.count ← chanPins.count +1;
index ← chanPins.count;
chanPins.sides[index] ← NEW[RouteChannel.PinPositionRec ← [index, thisPLoc]]};
};
MovePins: PROC [chanPins: RouteChannel.RoutingChannelPins, pIndex: RouteChannel.ZMPinsOnCh] = {
chanPins.count ← chanPins.count +1;
FOR index: RouteChannel.ZMPinsOnCh DECREASING IN [pIndex+1 .. chanPins.count] DO
pinPos: RouteChannel.PinPosition ← chanPins.sides[index-1];
pinPos.pinIndex ← index;
chanPins.sides[index] ← pinPos;
ENDLOOP;
};
BuildPin: PROC [parms: RoutePrivate.RoutingAreaParms, iPin: RouteChannel.InternPin, pinPosition: RouteChannel.PinPosition, pinWidth: DABasics.Number] RETURNS [pin: RouteChannel.ChanPin] = {
build the channel segment data structure for this net.
kindOfPin: RouteChannel.ChanPinType ←
IF iPin.chanSide = chanLeft OR iPin.chanSide = chanRight THEN exitPin
ELSE compPin;
thisPinWidth: DABasics.Number ←
IF kindOfPin = exitPin THEN iPin.pWidth
ELSE MAX[pinWidth, iPin.pWidth];
parms.widestPin ← MAX[thisPinWidth, parms.widestPin];
pin ← NEW[RouteChannel.ChanPinRec ← [
pinSide: iPin.chanSide,
qLoc: iPin.location.q,
pWidth: thisPinWidth,
kindOfPin: kindOfPin,
pinPosition: pinPosition,
pin: iPin
]];
};
PinViolation: PROC [chanPins: RouteChannel.RoutingChannelPins,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
pin: RouteChannel.ChanPin,
net: RoutePrivate.Net]
RETURNS [violation: BOOLEANFALSE] = {
check for pin to pin violations.
LimitProc: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
IF pin.pinSide = pinSide THEN
{width: DABasics.Number ← RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2;
pinPos: DABasics.Number ← pin.pinPosition.pLoc;
IF pinPos < pLoc THEN
quit ← pinPos + width + rules.branchSpacing > pLoc - pWidth
ELSE -- pinPos >= pLoc
quit ← pLoc + pWidth + rules.branchSpacing > pinPos - width};
IF quit THEN violationPin ← pin.pin};
pinSide: RouteChannel.ChanSide ← pin.pinSide;
pinIndex: RouteChannel.ZMPinsOnCh ← pin.pinPosition.pinIndex;
pLoc: DABasics.Number ← pin.pinPosition.pLoc;
pWidth: DABasics.Number ← RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2;
testWidth: DABasics.Number ← RouteUtil.GetWidthWithContact[rules, parms.widestPin] + rules.branchSpacing;
violationPin: RouteChannel.InternPin ← NIL;
count down from index to find the pin that can still effect index
iPos: DABasics.Number ← chanPins.sides[pinIndex].pLoc;
FOR limitIndex: RouteChannel.MPinsOnCh DECREASING IN [1 .. pinIndex] WHILE chanPins.sides[limitIndex].pLoc + testWidth > iPos AND ~violation DO
violation ← RouteChannel.EnumPins[chanPins.sides[limitIndex], LimitProc];
IF violation THEN
Route.Signal[callingError, Rope.Cat[Rope.Cat["Pins are too close. net 1: ", net.name, ", pin 1: ", pin.pin.name], Rope.Cat[ ", pin 2: ", violationPin.name]]];
ENDLOOP;
count up from index to find the pin that can still effect index
iPos ← chanPins.sides[pinIndex].pLoc;
FOR limitIndex: RouteChannel.MPinsOnCh IN [pinIndex .. chanPins.count] WHILE chanPins.sides[limitIndex].pLoc - testWidth < iPos AND ~violation DO
violation ← RouteChannel.EnumPins[chanPins.sides[limitIndex], LimitProc];
IF violation THEN
Route.Signal[callingError, Rope.Cat[Rope.Cat["Pins are too close. net 1: ", net.name, ", pin 1: ", pin.pin.name], Rope.Cat[ ", pin 2: ", violationPin.name]]];
ENDLOOP;
};
GetExitPins: PROC [chanPins: RouteChannel.RoutingChannelPins] RETURNS [exitPins: List.LORANIL] = {
get the exit pins for this net.
NOTE: this assumes that CheckChanPins has been invoked and that the inputs are valid!!!
ReallyGetExits: PROC [pinPos: RouteChannel.PinPosition] = {
IF pinPos # NIL THEN {
FOR pList: RouteChannel.ChanPinList ← pinPos.innerPins, pList.rest WHILE pList # NIL DO
this: RouteChannel.ChanPin ← pList.first;
SELECT this.pin.chanSide FROM
chanLeft, chanRight => exitPins ← CONS[this, exitPins];
ENDCASE;
ENDLOOP;
};
};
ReallyGetExits[chanPins.sides[1]];
IF chanPins.count > 0 THEN ReallyGetExits[chanPins.sides[chanPins.count]];
};
MakeSBTracks: PROC [chanData: RouteChannel.ChannelData,
rules: Route.DesignRules,
okToDiddleLLPins, okToDiddleURPins: BOOLEAN] = {
find the track positions
ExitPinCompare: List.CompareProc = {
q1: DABasics.Number ← NARROW[ref1, RouteChannel.ChanPin].pin.location.q;
q2: DABasics.Number ← NARROW[ref2, RouteChannel.ChanPin].pin.location.q;
RETURN[IF q1 < q2 THEN Basics.Comparison.less
ELSE IF q1 = q2 THEN Basics.Comparison.equal
ELSE Basics.Comparison.greater];
};
DoUp: PROC [thisPos: DABasics.Number]~ {
FOR trackPos: DABasics.Number ← lastPos + trackDist, trackPos + trackDist WHILE trackPos <= thisPos - trackDist DO
[] ← AddTrack[chanTracks, trackPos];
lastPos ← trackPos;
ENDLOOP;
};
ClosestTrack: PROC [thisPos: DABasics.Number] RETURNS [track: RouteChannel.Track ← NIL] ~ {
dist: INTLAST[INT];
FOR trackNum: INT IN [1 .. chanTracks.count] DO
trialTrack: RouteChannel.Track ← chanTracks.tracks[trackNum];
trialDist: INTABS[trialTrack.trackPos - thisPos];
IF trialDist < dist THEN {
track ← trialTrack;
dist ← trialDist}
ENDLOOP;
};
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
exitPinList: List.LORA ← GetExitPins[chanPins];
sortedExitPinList: List.LORA ← List.Sort[exitPinList, ExitPinCompare];
lastPos: DABasics.Number ← chanData.chanSides[chanBottom].routeAreaCoord;
previousPin: RouteChannel.ChanPin ← NIL;
trackDist: DABasics.Number ← rules.trunkToTrunk;
lastTrack: RouteChannel.Track ← NIL;
the complexity of this code comes from the requirement to move pins on the end of a switchbox under certain conditions (okToDiddleLLPins or okToDiddleURPins).
FOR pList: List.LORA -- RouteChannel.InternPinList -- ← sortedExitPinList, pList.rest WHILE pList # NIL DO
this: RouteChannel.ChanPin ← NARROW[pList.first];
thisPos: DABasics.Number ← this.pin.location.q;
pin2Name: Rope.ROPEIF previousPin = NIL THEN "none" ELSE previousPin.pin.name;
track: RouteChannel.Track ← NIL;
SELECT TRUE FROM
~okToDiddleLLPins AND ~okToDiddleURPins => { -- can't move any pins
IF thisPos = lastPos THEN -- already have a track here
track ← lastTrack
ELSE IF thisPos >= lastPos + trackDist THEN { -- lots of room here
DoUp[thisPos];
track ← AddTrack[chanTracks, thisPos]}
ELSE {
Route.Signal[callingError, Rope.Cat["Pins too close on ends of switchbox, pin 1: ", this.pin.name, ", pin 2: ", pin2Name]];
track ← AddTrack[chanTracks, thisPos]};
BindPinToTrack[this, track];
previousPin ← this;
lastTrack ← track;
lastPos ← thisPos};
okToDiddleLLPins AND okToDiddleURPins => { -- can move pins on both sides
IF thisPos = lastPos THEN -- already have a track here
track ← lastTrack
ELSE IF thisPos >= lastPos + trackDist THEN { -- lots of room here
DoUp[thisPos];
track ← AddTrack[chanTracks, thisPos]}
ELSE {
thisPos ← lastPos + trackDist;
track ← AddTrack[chanTracks, thisPos]};
BindPinToTrack[this, track];
previousPin ← this;
lastTrack ← track;
lastPos ← thisPos};
okToDiddleLLPins => { -- can move only pins on the left
IF this.pin.chanSide = chanRight THEN { -- this pin is on the right
IF thisPos >= lastPos + trackDist THEN -- lots of room here
DoUp[thisPos]
ELSE -- not enough room, error
Route.Signal[callingError, Rope.Cat["Pins too close on ends of switchbox, pin 1: ", this.pin.name, ", pin 2: ", pin2Name]];
track ← AddTrack[chanTracks, thisPos];
BindPinToTrack[this, track];
previousPin ← this;
lastTrack ← track;
lastPos ← thisPos;
};
};
okToDiddleURPins => { -- can move only pins on the right
IF this.pin.chanSide = chanLeft THEN { -- this pin is on the left
IF thisPos >= lastPos + trackDist THEN -- lots of room here
DoUp[thisPos]
ELSE -- not enough room, error
Route.Signal[callingError, Rope.Cat["Pins too close on ends of switchbox, pin 1: ", this.pin.name, ", pin 2: ", pin2Name]];
track ← AddTrack[chanTracks, thisPos];
BindPinToTrack[this, track];
previousPin ← this;
lastTrack ← track;
lastPos ← thisPos;
};
};
ENDCASE;
ENDLOOP;
run the tracks to the top of the switchbox
IF previousPin # NIL AND lastPos > chanData.chanSides[chanTop].routeAreaCoord - trackDist THEN {
Route.Signal[callingError, Rope.Cat["Pins too close on ends of switchbox, pin : ", previousPin.pin.name]]};
FOR trackPos: DABasics.Number ← lastPos + trackDist, trackPos + trackDist WHILE trackPos < chanData.chanSides[chanTop].routeAreaCoord - trackDist DO
[] ← AddTrack[chanTracks, trackPos];
lastPos ← trackPos;
ENDLOOP;
chanTracks.maxCount ← chanTracks.count;
IF okToDiddleLLPins # okToDiddleURPins THEN {
fix up the other side now
FOR pList: List.LORA -- RouteChannel.InternPinList -- ← sortedExitPinList, pList.rest WHILE pList # NIL DO
this: RouteChannel.ChanPin ← NARROW[pList.first];
thisPos: DABasics.Number ← this.pin.location.q;
pin2Name: Rope.ROPEIF previousPin = NIL THEN "none" ELSE previousPin.pin.name;
track: RouteChannel.Track;
SELECT TRUE FROM
okToDiddleLLPins => { -- can move only pins on the left
IF this.pin.chanSide = chanLeft THEN { -- this pin is on the left
track ← ClosestTrack[thisPos];
BindPinToTrack[this, track]};
};
okToDiddleURPins => { -- can move only pins on the right
IF this.pin.chanSide = chanRight THEN { -- this pin is on the right
track ← ClosestTrack[thisPos];
BindPinToTrack[this, track]};
};
ENDCASE;
ENDLOOP;
};
};
MakeCRTracks: PROC [chanTracks: RouteChannel.RoutingChannelTracks,
rules: Route.DesignRules,
maxTracksRequired: NAT] = {
find the track positions
trackLimit: RouteChannel.ZMaxTracks ← MIN[chanTracks.size, maxTracksRequired];
loc: DABasics.Number ← rules.trunkToEdge;
FOR trackIndex: RouteChannel.ZMaxTracks IN [1 .. trackLimit] DO
loc: DABasics.Number ← rules.trunkToEdge + (trackIndex - 1) * rules.trunkToTrunk;
[] ← AddTrack[chanTracks, loc];
loc ← loc + rules.trunkToTrunk;
ENDLOOP;
chanTracks.maxCount ← chanTracks.count;
};
AddTrack: PROC [chanTracks: RouteChannel.RoutingChannelTracks, trackPos: DABasics.Number] RETURNS [track: RouteChannel.Track] = {
insert a track at the position
IF chanTracks.count >= RouteChannel.maxTrack THEN
Route.Signal[noResource, "Too many tracks needed, call implementor"];
chanTracks.count ← chanTracks.count + 1;
track ← chanTracks.tracks[chanTracks.count] ← NEW[RouteChannel.TrackRec ← [trackNum: chanTracks.count, trackPos: trackPos]]};
BindPinToTrack: PROC [pin: RouteChannel.ChanPin, track: RouteChannel.Track] ~ {
IF pin # NIL THEN {
update the track constraints for the segments attached to the pin
sList: RouteChannel.SegmentList ← RouteChannel.GetSegsOnPin[pin];
pin.trackConstraint ← track.trackNum;
FOR segs: RouteChannel.SegmentList ← sList, segs.rest WHILE segs # NIL DO
seg: RouteChannel.Segment ← segs.first;
IF seg # NIL THEN {
IF seg.trackConstraint = 0 THEN seg.trackConstraint ← track.trackNum
ELSE seg.secTrackConstraint ← track.trackNum}; 
ENDLOOP;
};
};
DoTBBarriers: PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
chanSide: RouteChannel.ChanSide] = {
Block the tracks covered by the layer.
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
activeSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanSide];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
trackDist: DABasics.Number ← rules.trunkToTrunk;
FOR rlayer: RoutePrivate.RoutingLayer IN [trunk .. branch] DO
FOR bList: RTBasic.PQRectList ← activeSide.barrierList[rlayer], bList.rest WHILE bList # NIL DO
BlockProc: RouteChannel.EachTrackActionProc = {
trackPos: DABasics.Number ← RouteChannel.TrackLoc[chanTracks, parms, rules, trackIndex];
IF minQ < trackPos - trackDist AND trackPos + trackDist < maxQ THEN
track.blocked ← TRUE};
barrierItem: RTBasic.PQRect ← bList.first;
minQ: DABasics.Number ← MIN[barrierItem.c1.q, barrierItem.c2.q];
maxQ: DABasics.Number ← MAX[barrierItem.c1.q, barrierItem.c2.q];
[] ← RouteChannel.EnumTracks[chanTracks, BlockProc];
ENDLOOP;
ENDLOOP;
};
DoLRBarriers: PROC [chanData: RouteChannel.ChannelData,
chanSide: RouteChannel.ChanSide] = {
Block the tracks covered by the layer.
activeSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanSide];
FOR rlayer: RoutePrivate.RoutingLayer IN [trunk .. branch] DO
FOR bList: RTBasic.PQRectList ← activeSide.barrierList[rlayer], bList.rest WHILE bList # NIL DO
BlockProc: RouteChannel.EachTrackActionProc = { NULL };
barrierItem: RTBasic.PQRect ← bList.first;
minQ: DABasics.Number ← MIN[barrierItem.c1.q, barrierItem.c2.q];
maxQ: DABasics.Number ← MAX[barrierItem.c1.q, barrierItem.c2.q];
[] ← RouteChannel.EnumTracks[chanData.chanTracks, BlockProc];
ENDLOOP;
ENDLOOP;
};
Surround: PROC [r1, r2: RTBasic.PQRect] RETURNS [RTBasic.PQRect] =
INLINE {
RETURN [RTBasic.PQRect[
[MIN[r1.c1.p, r2.c1.p], MIN[r1.c1.q, r2.c1.q]],
[MAX[r1.c2.p, r2.c2.p], MAX[r1.c2.q, r2.c2.q]]]]};
ConvertToLORA: PROC [list: RouteChannel.InternPinList] RETURNS[val: List.LORA] = {
val ← NIL;
UNTIL list = NIL DO
val ← CONS[list.first, val];
list ← list.rest;
ENDLOOP;
RETURN[val];
}; -- of ConvertToLORA
}.