DIRECTORY CD, DABasics, Rope, Route, RouteDiGraph, RoutePrivate, RTBasic;

RouteChannel: CEDAR DEFINITIONS = {

maxTrack: NAT = 600; -- MUST be even!!!
maxPinsOnCh: NAT = 2000;

ZMaxTracks: TYPE = NAT[0 .. maxTrack];
MaxTracks: TYPE = NAT[1 .. maxTrack];
MPinsOnCh: TYPE = NAT[1 .. maxPinsOnCh];
ZMPinsOnCh: TYPE = NAT[0 .. maxPinsOnCh];

ChanSideOrNone: TYPE = {none, chanBottom, chanTop, chanLeft, chanRight};
ChanSide: TYPE = ChanSideOrNone[chanBottom .. chanRight];
ChanSideName: ARRAY ChanSide OF Rope.ROPE;
ChanLRSide: TYPE = ChanSide[chanLeft .. chanRight];
ChanTBSide: TYPE = ChanSide[chanBottom .. chanTop];
AboveOrBelow: TYPE = {above, below};
AboveOrBelowName: ARRAY AboveOrBelow OF Rope.ROPE;
GoingDirection: TYPE = {leftToRight, rightToLeft};
GoingName: ARRAY GoingDirection OF Rope.ROPE;

RoutingChannelSides: TYPE = REF RoutingChannelSidesRec;
RoutingChannelSidesRec: TYPE = RECORD [
routeAreaCoord: DABasics.Number _ 0,
extSide: DABasics.Side,
barrierList: ARRAY RoutePrivate.RoutingLayer OF RTBasic.PQRectList _ ALL[NIL],
enclosingBarrier: RTBasic.PQRect _ [[0, 0], [0, 0]]
];

RoutingChannelPins: TYPE = REF RoutingChannelPinsRec;
RoutingChannelPinsRec: TYPE = RECORD [
cEnd1, 
cEnd2: DABasics.Number _ 0,
count: ZMPinsOnCh _ 0,
size: ZMPinsOnCh _ maxPinsOnCh,
sides: ARRAY MPinsOnCh OF PinPosition _ ALL[NIL]
];

ChanParms: TYPE = REF ChanParmsRec;
ChanParmsRec: TYPE = RECORD [
maxToConvert, 
emptyTrackLimit: DABasics.Number
];

RoutingChannelTracks: TYPE = REF RoutingChannelTracksRec;
RoutingChannelTracksRec: TYPE = RECORD [
count, 
maxCount: ZMaxTracks _ 0,
size: ZMaxTracks _ maxTrack,
tracks: ARRAY MaxTracks OF Track
];

Track: TYPE = REF TrackRec;
TrackRec: TYPE = RECORD [
oldTrackNum, 
trackNum: ZMaxTracks _ 0,
trackPos, 
maxFeatureOnTrack: INT _ 0,
firstSeg: Segment _ NIL,
blocked: BOOLEAN _ FALSE,
keep: BOOLEAN _ FALSE
];

Segment: TYPE = REF SegmentRec;
SegmentRec: TYPE = RECORD [
exteriorPins: ARRAY ChanLRSide OF ChanPin _ ALL[NIL],
interiorPins: ChanPinList _ NIL,
routingLayer: RoutePrivate.RoutingLayer _ trunk,
qWidth: NAT _ 0,
constraintNode: RouteDiGraph.Node _ NIL,
trackNum, 
trackConstraint, 
secTrackConstraint: ZMaxTracks _ 0,
nextSeg: Segment _ NIL,
net: RoutePrivate.Net _ NIL,
part: INT _ 1,
failed, 
exitBreak: BOOLEAN _ FALSE
];
SegmentList: TYPE = LIST OF Segment;

SegmentConstraint: TYPE = REF SegmentConstraintRec;
SegmentConstraintRec: TYPE = RECORD [
name: Rope.ROPE _ NIL,
segment: Segment
];

PinPosition: TYPE = REF PinPositionRec;
PinPositionRec: TYPE = RECORD [
pinIndex: ZMPinsOnCh,
pLoc: DABasics.Number _ 0,
blocked: BOOLEAN _ FALSE,
pins: ARRAY ChanTBSide OF ChanPin _ ALL[NIL],
innerPins: ChanPinList _ NIL
];

ChanPinType: TYPE = {noPin, chanConnect, dogLeg, compPin, exitPin};
ChanPin: TYPE = REF ChanPinRec;
ChanPinRec: TYPE = RECORD [
pinSide: ChanSideOrNone,
qLoc: DABasics.Number _ 0, 
pWidth: NAT _ 0,
kindOfPin: ChanPinType,
pinPosition: PinPosition,
trackConstraint: ZMaxTracks _ 0,  -- track Consdtraint of segment attached to pin
conctSeg: ARRAY ChanLRSide OF Segment _ ALL[NIL],
altConctSeg: ARRAY ChanLRSide OF Segment _ ALL[NIL], -- used only if non pin dog leg outside range
pin: InternPin _ NIL
];
ChanPinList: TYPE = LIST OF ChanPin;

ChannelData: TYPE = REF ChannelDataRec;
ChannelDataRec: TYPE = RECORD [
constraints: RouteDiGraph.Graph _ NIL,
chanSides: ARRAY ChanSide OF RoutingChannelSides _ ALL[NIL],
chanTracks: RoutingChannelTracks _ NIL,
chanPins: RoutingChannelPins _ NIL,
chanParms: ChanParms _ NIL
];

InternPin: TYPE = REF InternPinRec;
InternPinRec: TYPE = RECORD[
name: Rope.ROPE,
chanSide: ChanSide,
location: RTBasic.PQPos,
pWidth: NAT,
layer: RoutePrivate.RoutingLayer,
pin: Route.Pin _ NIL
];
InternPinList: TYPE = LIST OF InternPin;

Density: TYPE = REF DensityRec;
DensityRec: TYPE = RECORD [
maxDensity: DABasics.Number _ 0,
values: ARRAY MPinsOnCh OF DABasics.Number _ ALL[0]
];

TrackSequence: TYPE = {start, outsideInTop, outsideInBottom, botToTop, topToBot};
DirectionSequence: TYPE = {start, leftToRight, rightToLeft, alternateLeft, alternateRight};
Method: TYPE = REF MethodRec;
MethodRec: TYPE = RECORD[
trackSequence: TrackSequence _ start, 
directionSequence: DirectionSequence _ start
];

trackSequenceName: ARRAY TrackSequence OF Rope.ROPE;
directionSequenceName: ARRAY DirectionSequence OF Rope.ROPE;

InitChannel: PROC [extSidesData: RoutePrivate.RoutingAreaSides,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
netTab: RoutePrivate.NetTab,
signalSinglePinNets, 
signalCoincidentPins: BOOLEAN _ TRUE, 
okToDiddleLLPins, 
okToDiddleURPins: BOOLEAN _ FALSE]
RETURNS [chanData: RouteChannel.ChannelData];
FindPinPos: PROC [chanPins: RoutingChannelPins, thisPLoc: DABasics.Number] RETURNS [index: ZMPinsOnCh];
GenerateConstraints: PROC [chanData: ChannelData, 
parms: RoutePrivate.RoutingAreaParms, 
rules: Route.DesignRules, 
routerUsed: RoutePrivate.RouterUsed] 
RETURNS [anythingToDo: BOOLEAN];
TopoWiring: PROC [chanData: RouteChannel.ChannelData, 
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
opt: Route.Optimization] 
RETURNS [routingResult: Route.ResultData];

EnumTracks: PROC [chanTracks: RoutingChannelTracks, eachAction: EachTrackActionProc] RETURNS [quit: BOOLEAN _ FALSE];

EachTrackActionProc: TYPE = PROC [track: Track, trackIndex: MaxTracks] RETURNS [quit: BOOLEAN _ FALSE];

EnumPins: PROC [pinPosition: PinPosition, eachAction: EachPinActionProc] RETURNS [quit: BOOLEAN _ FALSE];

EnumPinsOnSeg: PROC [seg: Segment, eachAction: EachPinActionProc] RETURNS [quit: BOOLEAN _ FALSE];

EachPinActionProc: TYPE = PROC[pinPosition: PinPosition, pin: ChanPin] RETURNS [quit: BOOLEAN _ FALSE];

EnumPinPositions: PROC [chanPins: RoutingChannelPins, eachAction: EachPinPositionActionProc] RETURNS [quit: BOOLEAN _ FALSE];

EachPinPositionActionProc: TYPE = PROC[pinPosition: PinPosition, pinIndex: MPinsOnCh] RETURNS [quit: BOOLEAN _ FALSE];

EnumSegmentsProc: TYPE = PROC [
parms: RoutePrivate.RoutingAreaParms,
name: Rope.ROPE,
pos1, pos2: DABasics.Position,
width: DABasics.Number, 
layer: CD.Layer]; -- Call back for wiring segments

EnumViasProc: TYPE = PROC [
parms: RoutePrivate.RoutingAreaParms,
name: Rope.ROPE,
pos, size: DABasics.Position, -- rectangle of size centered on pos
layer1, layer2: CD.Layer]; -- Call back for branch ends

EnumIncompletesProc: TYPE = PROC [
parms: RoutePrivate.RoutingAreaParms,
name: Rope.ROPE,
pos1, pos2: DABasics.Position]; -- Call back for incomplete connections

GetRouting: PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
rect: DABasics.Rect,
brokenNetName: Route.BrokenNetProc,
channelData: REF ANY,
enumSegments: EnumSegmentsProc, 
enumVias: EnumViasProc, 
enumIncompletes: EnumIncompletesProc];

RetrieveSegments: EnumSegmentsProc;
RetrieveVias: EnumViasProc;
RetrieveIncompletes: EnumIncompletesProc;

Destroy: PROC [chanData: ChannelData];

ClearChan: PROCEDURE[chanData: ChannelData];
TrackLoc: PROC [chanTracks: RoutingChannelTracks, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, track: ZMaxTracks] RETURNS [loc: DABasics.Number];

TrackSeg: PROC [chanTracks: RoutingChannelTracks, track: MaxTracks] RETURNS [Segment];

TrackSegAbs: PROC [chanTracks: RoutingChannelTracks, track: MaxTracks] RETURNS [Segment];

ChannelWidth: PROC [chanTracks: RoutingChannelTracks, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules] RETURNS [DABasics.Number];

InfluenceTracks: PROC [rules: Route.DesignRules, wireWidth: NAT] RETURNS [NAT];

ExtSideToIntSide: PROC [rules: Route.DesignRules, extSide: DABasics.Side] RETURNS [intSide: ChanSide];
IntSideToExtSide: PROC [rules: Route.DesignRules, intSide: ChanSide] RETURNS [extSide: DABasics.Side];

WriteConstraints: PROC [graph: RouteDiGraph.Graph];

GetPinsOnSeg: PROC [seg: Segment] RETURNS [pinList: ChanPinList];

GetSegsOnPin: PROC [pin: ChanPin] RETURNS [segList: SegmentList];

DestroyOldConstraints: PROC [chanData: ChannelData];

ComputeDensity: PROC [chanPins: RoutingChannelPins, rules: Route.DesignRules] RETURNS [density: Density];

Length: PROC [seg: Segment] RETURNS [DABasics.Number];
WriteResult: PROC [result: Route.ResultData, 
parms: RoutePrivate.RoutingAreaParms, 
rules: Route.DesignRules, 
method: Method];
FindConstraintLimits: PROC [
chanPins: RoutingChannelPins, 
parms: RoutePrivate.RoutingAreaParms, 
rules: Route.DesignRules, 
nextLower, nextHigher: MPinsOnCh, 
pinAction: EachPinActionProc] 
RETURNS [minLimit, maxLimit: MPinsOnCh];

CheckPins: PROCEDURE[seg: Segment, pin: ChanPin, sideOfSeg: ChanLRSide];

CheckSegs: PROCEDURE[seg: Segment, pin: ChanPin];

AuditPins: PROC [chanPins: RouteChannel.RoutingChannelPins];

AuditSegs: PROC [chanTracks: RoutingChannelTracks];

Combine: PROCEDURE [l1, l2, l3: ChanPinList] RETURNS [l: ChanPinList _ NIL];

MembRopeList: PROCEDURE [ref: Rope.ROPE, list: LIST OF Rope.ROPE] RETURNS [BOOL];

GetRange: PROC [pinList: ChanPinList] RETURNS [range: RTBasic.Range];

PinsOnSide: PROC [seg: Segment] RETURNS [left, top, right, bottom: BOOLEAN];

}.
ÒRouteChannel.mesa
Copyright Ó 1985, 1987 by Xerox Corporation.  All rights reserved.
by Bryan Preas   July 10, 1985 6:57:00 pm PDT 
last edited by Bryan Preas   April 3, 1987 3:22:10 pm PST
Christian Le Cocq February 10, 1988 12:29:56 pm PST
channel routing method
Initialize for channel routing

build the PinPosition data structure for this pin at thisPLoc.
NOTE: NOT intended for general use !!!

run through the pins on the channel,
create segment constraints from the pin to pin relationships

channel route the routing area
Enumerate routing results entities
Remove circular references so garbage collection can work
initialize for one channel routing

get location of the specified track
get first segment on the specified track
get first segment on the specified track without indirect reference
returns the width of th channel
find how far a track can influence another track ( in tracks)
convert a position from x-y to p-q space.

convert a position from p-q to x-y space.
write the constraint graph on the terminal
find all of the segments attached to a pin
find all of the segments attached to a pin
must explicitly destroy the old data
compute the track density for the current channel
return lenth of line segment from pos1 to pos2.

write the results

find the limits for constraints
make sure a pin points back to segment
make sure a segment points back to pin
make sure pin data is consistent
make sure seg data is consistent
get the range of the pins in the pinList
�Êd˜
codeš
œ™Kš
œB™BKš
œ.™.Kš
œ9™9K™3—K˜šÏk	œ@˜IK˜—šÐlnœ�œ
�œ�
œ˜$Kšœ
�œÏc˜'Kšœ
�œ˜K˜Kšœ�œ�œ˜&Kšœ�œ�œ˜%Kšœ�œ�œ˜(Kšœ�œ�œ˜)K˜Kšœ�œ4˜HKšœ
�œ+˜9Kšœ�œ
�œ�œ
˜*Kšœ�œ#˜3Kšœ�œ#˜3Kšœ�œ˜$Kšœ�œ�œ�œ
˜2Kšœ�œ˜2Kšœ�œ�œ�œ
˜-K˜šœ�œ�œ˜7šœ�œ�œ˜'Kš
œ$˜$Kš
œ˜Kš	œ
�œ�œ�œ
�œ˜NKš
œ3˜3Kš
œ˜——K˜šœ�œ�œ˜5šœ�œ�œ˜&Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš	œ�œ�œ�œ
�œ
˜0Kš
œ˜K˜——šœ�œ�œ˜#šœ�œ�œ˜Kš
œ˜Kš
œ ˜ Kš
œ˜K˜——šœ�œ�œ˜9šœ�œ�œ˜(Kš
œ˜Kš
œ˜Kš
œ˜Kšœ�œ�œ˜ Kš
œ˜——K˜šœ�œ�œ
˜šœ
�œ�œ˜Kš
œ
˜
Kš
œ˜Kš
œ
˜
Kšœ�œ˜Kšœ�œ
˜Kšœ	�œ�œ
˜Kšœ�œ�˜Kš
œ˜——K˜šœ	�œ�œ˜šœ�œ�œ˜Kš	œ�œ�œ�œ
�œ˜5Kšœ�œ
˜ Kš
œ0˜0Kšœ�œ˜Kšœ$�œ
˜(Kš
œ
˜
Kš
œ˜Kš
œ#˜#Kšœ�œ
˜Kšœ�œ
˜Kšœ�œ˜Kš
œ˜Kšœ�œ�˜Kš
œ˜——Kšœ
�œ�œ
�œ	˜$K˜šœ�œ�œ˜3šœ�œ�œ˜%Kšœ�œ�œ
˜Kš
œ˜Kš
œ˜K˜——šœ
�œ�œ˜'šœ�œ�œ˜Kš
œ˜Kš
œ˜Kšœ	�œ�œ
˜Kš	œ�œ�œ�œ
�œ˜-Kšœ�˜Kš
œ˜K˜——Kšœ
�œ2˜Cšœ	�œ�œ˜šœ�œ�œ˜K˜Kš
œ˜Kšœ�œ˜Kš
œ˜Kš
œ˜Kšœ"Ÿ/˜QKš	œ
�œ�œ�œ
�œ˜1Kš
œ
�œ�œ�œ
�œŸ-˜bKšœ�˜Kš
œ˜——Kšœ
�œ�œ
�œ	˜$K˜šœ
�œ�œ˜'šœ�œ�œ˜Kšœ"�œ
˜&Kš	œ�œ
�œ�œ
�œ˜<Kšœ#�œ
˜'Kšœ�œ
˜#Kšœ�˜Kš
œ˜K˜——šœ�œ�œ˜#šœ�œ�œ
˜Kšœ�œ
˜Kš
œ˜Kš
œ˜Kšœ�œ
˜Kš
œ!˜!Kšœ�˜Kš
œ˜——Kšœ�œ�œ
�œ˜(K˜šœ	�œ�œ˜šœ�œ�œ˜Kš
œ ˜ Kšœ�œ�œ�œ˜3Kš
œ˜——K˜Kš
œ™Kšœ�œ>˜QKšœ�œD˜[šœ�œ�œ˜šœ�œ�œ
˜Kš
œ&˜&Kš
œ,˜,Kš
œ˜——K˜Kšœ�œ�œ�œ
˜4Kšœ�œ�œ�œ
˜<K˜šÏnœ�œ-˜?Kš
œ%˜%Kš
œ˜Kš
œ˜Kš
œ˜Kšœ�œ�œ˜&Kš
œ˜Kšœ�œ�œ
˜"Kš�œ&˜-Kš
œ™K™—š 
œ�œ;�œ˜gKš
œ>™>Kš�œ�œ™&K™—š œ�œ˜2Kš
œ&˜&Kš
œ˜Kš
œ%˜%Kš�œ�œ˜ Kš
œ$™$Kš
œ<™<K™—š 
œ�œ%˜6Kš
œ%˜%Kš
œ˜Kš
œ˜Kš�œ#˜*K™K˜—š
 
œ�œE�œ�œ�œ˜uK˜Kšœ�œ�œ'�œ�œ�œ˜gK˜—š
 œ�œ;�œ�œ�œ˜iK˜—š
 
œ�œ/�œ�œ�œ˜bK˜Kšœ�œ�œ)�œ�œ�œ˜gK˜—š
 œ�œG�œ�œ�œ˜}K˜Kšœ�œ�œ0�œ�œ�œ˜vK˜—šœ�œ�œ
˜Kš
œ%˜%Kšœ�œ
˜Kš
œ˜Kš
œ˜Kšœ�œ	Ÿ ˜2K˜—šœ�œ�œ
˜Kš
œ%˜%Kšœ�œ
˜KšœŸ$˜BKšœ�œ	Ÿ˜7K˜—šœ�œ�œ
˜"Kš
œ%˜%Kšœ�œ
˜Kšœ Ÿ'˜G—K˜š 
œ�œ%˜5Kš
œ%˜%Kš
œ˜Kš
œ˜Kš
œ#˜#Kšœ
�œ
�œ
˜Kš
œ ˜ Kš
œ˜Kš
œ&˜&Kš
œ"™"K˜—Kš œ˜#Kš œ˜Kš œ˜)K˜š œ�œ˜&Kš
œ9™9K˜—š 	œ�	œ˜,Kš
œ"™"K™—š œ�œw�œ˜¤
Kš
œ#™#K˜—š œ�œ6�œ˜VKš
œ(™(K˜—š œ�œ6�œ˜YKš
œC™CK˜—š œ�œd�œ˜�
K™K˜—š
 œ�œ'�œ�œ�œ˜OKš
œ=™=K˜—š œ�œ4�œ˜fK™)K™—š œ�œ/�œ˜fK™)—K˜š œ�œ˜3Kš
œ*™*K˜—š œ�œ�œ˜AKš
œ*™*K˜—š œ�œ�œ˜AKš
œ*™*K˜—š œ�œ˜4Kš
œ$™$K˜—š œ�œ:�œ˜iK™1—K˜š œ�œ�œ˜6K™/K™—š œ�œ˜-Kš
œ&˜&Kš
œ˜Kš
œ˜Kš
œ™K™—š œ�œ˜Kš
œ˜Kš
œ&˜&Kš
œ˜Kš
œ"˜"Kš
œ˜Kš�œ!˜(Kš
œ™—K˜š 	œ�	œ4˜HKš
œ&™&K˜—š 	œ�	œ˜1Kš
œ&™&—K˜š 	œ�œ-˜<Kš
œ ™ K˜—š 	œ�œ$˜3Kš
œ ™ —K˜š œ�	œ�œ�œ˜LK˜—š œ�	œ�œ�œ
�œ�œ�œ�œ˜QK˜—š œ�œ�œ˜EK™(K˜—Kš 
œ�œ�œ�œ˜L—K˜Kš�
œ
˜—…—#d5š