DIRECTORY
CD,
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: 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];

ActiveTrackSpec: TYPE = REF ActiveTrackSpecRec;
ActiveTrackSpecRec: TYPE = RECORD[
track, minActTrack, maxActTrack: RouteChannel.ZMaxTracks _ 0,
going: RouteChannel.GoingDirection _ leftToRight,
freeArea: RouteChannel.AboveOrBelow _ below];

ActiveSegSpec: TYPE = REF ActiveSegSpecRec;
ActiveSegSpecRec: TYPE = RECORD[
seg: RouteChannel.Segment _ NIL,
segLayer: RoutePrivate.RoutingLayerOrNone _ trunk];

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

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

CleanUp: PROC [routingArea: Route.RoutingArea];

ClearChan: PUBLIC 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];

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

FollowingSeg: PROCEDURE [routingArea: Route.RoutingArea, activeSegSpec: ActiveSegSpec,
activeTrackSpec: ActiveTrackSpec, includeUnPlaced: BOOLEAN]
RETURNS [nextSegSpec: RouteChannel.ActiveSegSpec];

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

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.
VRouteChannel.mesa   ///Route/RouteChannel.mesa
Bryan Preas August 13, 1985 4:21:04 pm PDT
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   July 10, 1985 6:57:07 pm PDT
active routing track specification
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)
find how far a wire can influence anything else ( in units)
convert a position from x-y to p-q space.

convert a position from p-q to x-y space.
return the following segment in the current direction
if includeUnPlaced then tracknum must be 0
if ~includeUnPlaced, return the segment present irrespective of wheather its placed
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
Κ
˜š
œ.™.Icode™*—˜Jšœ
Οm
œ1™<Jš
œ.™.Jš
œ9™9—J˜š
Οk	˜	Jšžœ
˜J˜Jš
œ˜Jš
œ
˜
Jš
œ
˜
J˜—šœžœ
žœ˜!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š
œ1˜1Jš
œ-˜-J˜—Jšœžœžœ˜+šœžœžœ
˜ Jšœžœ
˜ Jš
œ3˜3—J˜Jšœ	žœžœ˜šœžœžœ˜Jš
œ˜Jšœžœžœžœ˜?—J˜Jš
œ™Jšœžœ>˜QJšœžœD˜[Jšœžœžœ˜šœžœžœ
˜Jš
œ&˜&Jš
œ.˜.—J˜Jšœžœžœžœ
˜AJšœžœ žœžœ
˜IJ˜šΟnœž	œ~˜”
Jš
œ™J™—š 
œžœ:žœ"˜sJš
œ>™>J™&J™—š œž	œFžœžœ˜„
Jš
œ$™$Jš
œ<™<J™—š 
œž	œ:žœ&˜|J™J˜—š
 
œžœCžœžœžœ˜sJ˜—š œžœžœGžœžœžœ˜‡
J˜—š
 œžœ[žœžœžœ˜‰
J˜—š
 
œžœOžœžœžœ˜‚
J˜—š œžœžœIžœžœžœ˜‡
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˜—š 	œžœ!˜<Jš
œ"™"J™—š œžœBžœ˜lJš
œ#™#J˜—š œžœAžœ˜nJš
œ(™(J˜—š œžœAžœ˜qJš
œC™CJ˜—š œžœ"žœ˜KJ™J˜—š œžœ;žœ˜gJš
œ=™=J˜—š 
œžœ;žœ˜eJš
œ;™;J˜—š œžœ7žœ"˜vJ™)J™—š œžœBžœ˜vJ™)—J˜š œž	œ?˜VJšœ3žœ
˜;Jšžœ+˜2š
œ5™5Jš
œ*™*Jš
œS™S——J˜š œžœ˜3Jš
œ*™*J˜—š œžœžœ˜AJš
œ*™*J˜—š œžœžœ˜AJš
œ*™*J˜—š œžœ"˜=Jš
œ$™$J˜—š œžœ"žœ˜QJ™1—J˜š œžœžœ˜@J™/J™—š œž	œ/˜EJš
œ™J™—š œžœžœ˜QJš
œ™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˜—Kš 
œžœ=žœžœ˜yJ˜Jšžœ
˜——…—)>=€