[_CD4_]<datools7.0>Route25>RouteChannelInitImpl.mesa!5

RouteChannelInitImpl.mesa

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];

BuildChanPin[chanPins, parms, rules, net, sortedPinList];

};

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: BOOLEAN ← TRUE] = {

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: BOOLEAN ← FALSE;

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: BOOLEAN ← TRUE;

useThisOne: BOOLEAN ← TRUE;

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: BOOLEAN ← TRUE;

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: BOOLEAN ← TRUE;

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: BOOLEAN ← FALSE;

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: BOOLEAN ← FALSE] = {

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.LORA ← NIL] = {

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: INT ← LAST[INT];

FOR trackNum: INT IN [1 .. chanTracks.count] DO

trialTrack: RouteChannel.Track ← chanTracks.tracks[trackNum];

trialDist: INT ← ABS[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.ROPE ← IF 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.ROPE ← IF 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;

};

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;

};

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