DIRECTORY
Rope, Route, RouteDiGraph, RoutePrivate;

RouteChannel: CEDAR DEFINITIONS =

BEGIN

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 [
sideOrg, sideFiducial: RoutePrivate.PQPosition _ [0, 0],
routeAreaCoord: Route.Number _ 0,
extSide: Route.Side,
barrierList: ARRAY RoutePrivate.RoutingLayer OF RoutePrivate.PQRectList _ ALL[NIL],
enclosingBarrier: RoutePrivate.PQRect _ [[0, 0], [0, 0]],
properties: Route.PropList _ NIL];

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

ChanParms: TYPE = REF ChanParmsRec;
ChanParmsRec: TYPE = RECORD [
maxToConvert, emptyTrackLimit: Route.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: Route.Number _ 0,
firstSeg: Segment _ NIL,
blocked: BOOLEAN _ FALSE,
keep: BOOLEAN _ FALSE];

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

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

PinPosition: TYPE = REF PinPositionRec;
PinPositionRec: TYPE = RECORD [
pinIndex: ZMPinsOnCh,
pLoc: Route.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;
ChanPinList: TYPE = LIST OF ChanPin;
ChanPinRec: TYPE = RECORD [
pinSide: ChanSideOrNone,
qLoc, pWidth: Route.Number _ 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];

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;
InternPinList: TYPE = LIST OF InternPin;
InternPinRec: TYPE = RECORD[
name: Rope.ROPE,
chanSide: ChanSide,
location: RoutePrivate.PQPosition,
pWidth: Route.Number,
layer: RoutePrivate.RoutingLayer,
pin: Route.Pin _ NIL];

Density: TYPE = REF DensityRec;
DensityRec: TYPE = RECORD [
maxDensity: Route.Number _ 0,
values: ARRAY RouteChannel.MPinsOnCh OF Route.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 RouteChannel.TrackSequence OF Rope.ROPE;
directionSequenceName: ARRAY RouteChannel.DirectionSequence OF Rope.ROPE;

InitChannel: PROCEDURE[routingArea: Route.RoutingArea, sideOrgins: Route.PositionVec, routingRect: Route.Rect, routerUsed: RoutePrivate.RouterUsed, signalSinglePinNets, signalCoincidentPins: BOOLEAN _ TRUE, okToDiddleLLPins, okToDiddleURPins: BOOLEAN _ FALSE];
FindPinPos: PROC [routingArea: Route.RoutingArea, thisPLoc: Route.Number] RETURNS [index: RouteChannel.ZMPinsOnCh];
GenerateConstraints: PROCEDURE[routingArea: Route.RoutingArea, routerUsed: RoutePrivate.RouterUsed] RETURNS [anythingToDo: BOOLEAN];
TopoWiring: PROCEDURE[routingArea: Route.RoutingArea, opt: Route.Optimization] RETURNS [routingResult: Route.RoutingResult];

EnumTracks: PROC [routingArea: Route.RoutingArea, eachAction: EachTrackActionProc] RETURNS [quit: BOOLEAN _ FALSE];

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

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

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

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

EnumPinPositions: PROC [routingArea: Route.RoutingArea, eachAction: EachPinPositionActionProc] RETURNS [quit: BOOLEAN _ FALSE];

EachPinPositionActionProc: TYPE = PROC[routingArea: Route.RoutingArea, pinPosition: PinPosition, pinIndex: RouteChannel.MPinsOnCh] RETURNS [quit: BOOLEAN _ FALSE];

EnumSegmentsProc: TYPE = PROCEDURE[
routingArea: Route.RoutingArea,
name: Rope.ROPE,
netPart: NAT, 
pos1, pos2: Route.Position,
width: Route.Number, 
layer: Route.Layer]; -- Call back for wiring segments

EnumPinsProc: TYPE = PROCEDURE[
routingArea: Route.RoutingArea,
name: Rope.ROPE,
netPart: NAT, 
pos: Route.Position, 
layer: Route.Layer,
pin: Route.Pin]; -- Call back for channel pins

EnumViasProc: TYPE = PROCEDURE[
routingArea: Route.RoutingArea,
name: Rope.ROPE,
netPart: NAT, 
pos, size: Route.Position, -- rectangle of size centered on pos
layer1, layer2: Route.Layer]; -- Call back for branch ends

EnumExitsProc: TYPE = PROCEDURE[
routingArea: Route.RoutingArea,
name: Rope.ROPE,
netPart: NAT, 
pos: Route.Position, 
layer: Route.Layer,
pin: Route.Pin,
constructedExit: BOOLEAN]; -- Call back for channel exits

EnumIncompletesProc: TYPE = PROCEDURE[
routingArea: Route.RoutingArea,
name: Rope.ROPE,
netPart: NAT, 
pos1, pos2: Route.Position]; -- Call back for incomplete connections

GetRouting: PROCEDURE[
routingArea: Route.RoutingArea,
rect: Route.Rect,
properties: Route.PropList,
EnumSegments: EnumSegmentsProc, 
EnumPins: EnumPinsProc, 
EnumVias: EnumViasProc, 
EnumExits: EnumExitsProc, 
EnumIncompletes: EnumIncompletesProc] RETURNS [externalConnections: Route.PinList]; -- Enumerate routing results entities

RetrieveSegments: EnumSegmentsProc;
RetrieveVias: EnumViasProc;
RetrievePins: EnumPinsProc;
RetrieveExits: EnumExitsProc;
RetrieveIncompletes: EnumIncompletesProc;

Destroy: PROC [routingArea: Route.RoutingArea];

ClearChan: PROCEDURE[routingArea: Route.RoutingArea];
TrackLoc: PROC [routingArea: Route.RoutingArea, track: RouteChannel.ZMaxTracks] RETURNS [loc: Route.Number];

TrackSeg: PROC [routingArea: Route.RoutingArea, track: RouteChannel.MaxTracks] RETURNS [RouteChannel.Segment];

TrackSegAbs: PROC [routingArea: Route.RoutingArea, track: RouteChannel.MaxTracks] RETURNS [RouteChannel.Segment];

ChannelWidth: PROC [routingArea: Route.RoutingArea] RETURNS [Route.Number];

InfluenceTracks: PROC [routingArea: Route.RoutingArea, wireWidth: Route.Number] RETURNS [Route.Number];

ExtSideToIntSide: PROC [routingArea: Route.RoutingArea, extSide: Route.Side] RETURNS [intSide: RouteChannel.ChanSide];
IntSideToExtSide: PROC [routingArea: Route.RoutingArea, intSide: RouteChannel.ChanSide] RETURNS [extSide: Route.Side];

WriteConstraints: PROC [graph: RouteDiGraph.Graph];

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

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

DestroyOldConstraints: PROC [routingArea: Route.RoutingArea];

ComputeDensity: PROC [routingArea: Route.RoutingArea] RETURNS [density: Density];

Length: PROC [seg: RouteChannel.Segment] RETURNS [Route.Number];
WriteResult: PROCEDURE [result: Route.RoutingResult, method: Method];
Overlap: PROC [r1, r2: RoutePrivate.Range] RETURNS [overlap: RoutePrivate.Range];

Overlaps: PUBLIC PROC [r1, r2: RoutePrivate.Range] RETURNS [BOOL] =
INLINE {RETURN [(r1.l<=r2.r) AND (r2.l<=r1.r)]};

Equal: PUBLIC PROC [r1, r2: RoutePrivate.Range] RETURNS [BOOL] =
INLINE {RETURN [(r1.l=r2.l) AND (r1.r=r2.r)]};

Gap: PROC [r1, r2: RoutePrivate.Range] RETURNS [gap: RoutePrivate.Range];

Span: PROC [r1, r2: RoutePrivate.Range] RETURNS [result: RoutePrivate.Range];

AddPoints: PROC [p, s: RoutePrivate.PQPosition] RETURNS [RoutePrivate.PQPosition] =
INLINE {RETURN [RoutePrivate.PQPosition[p: p.p+s.p, q: p.q+s.q]]};

SubPoints: PROC [pos, neg: RoutePrivate.PQPosition] RETURNS [RoutePrivate.PQPosition] =
INLINE {RETURN [RoutePrivate.PQPosition[p: pos.p-neg.p, q: pos.q-neg.q]]};

FindConstraintLimits: PROC [routingArea: Route.RoutingArea, nextLower, nextHigher: RouteChannel.MPinsOnCh, pinAction: RouteChannel.EachPinActionProc] RETURNS [minLimit, maxLimit: RouteChannel.MPinsOnCh];

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

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

AuditPins: PROC [routingArea: Route.RoutingArea];

AuditSegs: PROC [routingArea: Route.RoutingArea];

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

MembRopeList: PROCEDURE [ref: Rope.ROPE, list: Route.RopeList] RETURNS [BOOL];

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

PinsOnSide: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment] RETURNS [left, top, right, bottom: BOOLEAN];

END.
ώRouteChannel.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
by Bryan Preas   July 10, 1985 6:57:00 pm PDT 
last edited by Bryan Preas   December 18, 1986 5:08:30 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
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

get the overlap of seg1, seg2
get the gap of seg1, seg2
determnie span of ranges 1 and 2
--p displaced by d
--pos displaced by -neg
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
ΚΨ˜Jš
œ™˜Jšœ
Οm
œ1™<Jš
œ.™.Jš
œ=™=—J˜š
Οk	˜	Jš
œ(˜(J˜—šΟnœžœ
žœ˜!J˜Jšžœ
˜Jšœ
žœΟc˜'Jšœ
žœ˜J˜Jšœžœžœ˜&Jšœžœžœ˜%Jšœžœžœ˜(Jšœžœžœ˜)J˜Jšœžœ4˜HJšœ
žœ+˜9JšŸœžœ
žœžœ
˜*Jšœžœ#˜3Jšœžœ#˜3Jšœžœ˜$JšŸœžœžœžœ
˜2Jšœžœ˜2JšŸ	œžœžœžœ
˜-J˜Jšœžœžœ˜7šœžœžœ˜'J˜8J˜!Jš
œ˜Jš	œ
žœžœžœ
žœ˜SJš
œ9˜9Jšœžœ˜"—J˜Jšœžœžœ˜5šœžœžœ˜&Jš
œ˜Jš
œ˜Jš
œ˜Jš	œžœžœžœ
žœ˜2J˜—Jšœžœžœ˜#šœžœžœ˜Jš
œ-˜-J˜—Jšœžœžœ˜9šœžœžœ˜(Jš
œ ˜ Jš
œ˜Jšœžœžœ˜"—J˜Jšœžœžœ
˜šœ
žœžœ˜Jš
œ&˜&Jš
œ.˜.Jšœžœ
˜Jšœ	žœžœ
˜Jšœžœžœ˜—J˜Jšœ	žœžœ˜Jšœ
žœžœ
žœ	˜$šœžœžœ˜Jš	œžœžœžœ
žœ˜5Jšœžœ
˜ Jš
œ1˜1J˜Jšœ$žœ˜)Jš
œ?˜?Jšœžœ˜Jšœžœ˜Jšœžœžœ˜$—J˜Jšœžœžœ˜3šœžœžœ˜%Jšœžœžœ
˜Jš
œ˜J˜—Jšœ
žœžœ˜'šœžœžœ˜Jš
œ˜Jš
œ˜Jšœ	žœžœ
˜Jš	œžœžœžœ
žœ˜-Jšœžœ˜J˜—Jšœ
žœ2˜CJšœ	žœžœ˜Jšœ
žœžœ
žœ	˜$šœžœžœ˜J˜J˜Jš
œ˜Jš
œ˜Jšœ" /˜QJš	œ
žœžœžœ
žœ˜1Jš
œ
žœžœžœ
žœ -˜bJšœžœ˜J˜—Jšœ
žœžœ˜'šœžœžœ˜Jšœ"žœ
˜&Jš	œžœ
žœžœ
žœ˜<Jšœ#žœ
˜'Jšœžœ
˜#Jšœžœ˜J˜—Jšœžœžœ˜#Jšœžœžœ
žœ˜(šœžœžœ
˜Jšœžœ
˜Jš
œ˜Jš
œ"˜"J˜Jš
œ!˜!Jšœžœ˜J˜—Jšœ	žœžœ˜šœžœžœ˜Jš
œ˜Jšœžœžœžœ˜?—J˜Jš
œ™Jšœžœ>˜QJšœžœD˜[Jšœžœžœ˜šœžœžœ
˜Jš
œ&˜&Jš
œ.˜.—J˜Jšœžœžœžœ
˜AJšœžœ žœžœ
˜IJ˜šŸœž	œ©
žœžœ$žœžœ˜„Jš
œ™J™—šŸ
œžœ:žœ"˜sJš
œ>™>J™&J™—šŸœž	œFžœžœ˜„
Jš
œ$™$Jš
œ<™<J™—šŸ
œž	œ:žœ&˜|J™J˜—š
Ÿ
œžœCžœžœžœ˜sJ˜JšœžœžœFžœžœžœ˜†
J˜—š
Ÿœžœ[žœžœžœ˜‰
J˜—š
Ÿ
œžœOžœžœžœ˜‚
J˜JšœžœžœIžœžœžœ˜‡
J˜—š
ŸœžœIžœžœžœ˜J˜Jšœžœžœ]žœžœžœ˜£
J˜—šœžœž	œ
˜#Jš
œ˜Jšœžœ
˜Jšœ	žœ˜Jš
œ˜Jš
œ˜Jšœ  ˜5J˜—šœžœž	œ
˜Jš
œ˜Jšœžœ
˜Jšœ	žœ˜Jš
œ˜Jš
œ˜Jšœ ˜.J˜—šœžœž	œ
˜Jš
œ˜Jšœžœ
˜Jšœ	žœ˜Jšœ $˜?Jšœ ˜:J˜—šœžœž	œ
˜ Jš
œ˜Jšœžœ
˜Jšœ	žœ˜Jš
œ˜Jš
œ˜Jš
œ˜Jšœžœ ˜9J˜—šœžœž	œ
˜&Jš
œ˜Jšœžœ
˜Jšœ	žœ˜Jšœ '˜D—J˜šŸ
œž	œ
˜Jš
œ˜Jš
œ˜Jš
œ˜JšŸœ˜ JšŸœ˜JšŸœ˜JšŸ	œ˜JšŸœžœ' %˜yJ˜—JšŸœ˜#JšŸœ˜JšŸœ˜JšŸ
œ˜JšŸœ˜)J˜šŸœžœ"˜/Jš
œ9™9J˜—šŸ	œž	œ!˜5Jš
œ"™"J™—šŸœžœBžœ˜lJš
œ#™#J˜—šŸœžœAžœ˜nJš
œ(™(J˜—šŸœžœAžœ˜qJš
œC™CJ˜—šŸœžœ"žœ˜KJ™J˜—šŸœžœ;žœ˜gJš
œ=™=J˜—šŸœžœ7žœ"˜vJ™)J™—šŸœžœBžœ˜vJ™)—J˜šŸœžœ˜3Jš
œ*™*J˜—šŸœžœžœ˜AJš
œ*™*J˜—šŸœžœžœ˜AJš
œ*™*J˜—šŸœžœ"˜=Jš
œ$™$J˜—šŸœžœ"žœ˜QJ™1—J˜šŸœžœžœ˜@J™/J™—šŸœž	œ/˜EJš
œ™J™—šŸœžœžœ˜QJš
œ™J˜—š
Ÿœžœ
žœžœžœ˜CJšžœžœžœ˜0—J˜š
Ÿœžœ
žœžœžœ˜@Jšžœžœžœ˜.J˜—šŸœžœžœ˜IJš
œ™J˜—šŸœžœžœ˜MJ™ J˜—šŸ	œžœ!žœ˜SJš
œ™Jšžœžœ4˜BJ˜—šŸ	œžœ%žœ˜WJš
œ™Jšžœžœ<˜J—J˜šŸœžœ|žœ.˜Λ
Jš
œ™—J˜šŸ	œž	œ˜/Jš
œ˜Jš
œ$˜$Jš
œ&™&J˜—šŸ	œž	œ˜/Jš
œ˜Jš
œ&™&—J˜šŸ	œžœ"˜1Jš
œ ™ J˜—šŸ	œžœ"˜1Jš
œ ™ —J˜šŸœž	œžœ žœ˜YJ˜—š
Ÿœž	œžœžœžœ˜NJ˜—šŸœžœžœ˜JJ™(J˜—IcodešŸ
œžœ=žœžœ˜yJ˜Jšžœ
˜——…—);Φ