DIRECTORY
Basics,
CD,
CDPinObjects,
Convert,
Rope,
Route,
RouteChannel,
RouteDiGraph,
RoutePrivate,
RouteUtil,
TerminalIO;

RouteChannelTopolImpl: CEDAR PROGRAM
IMPORTS CD, CDPinObjects, Convert, Rope, Route, RouteChannel, RouteDiGraph, RoutePrivate, RouteUtil, TerminalIO
EXPORTS RouteChannel
SHARES Route =
BEGIN

SegProc: TYPE = PROC[seg: RouteChannel.Segment, activeTrackSpec: RouteChannel.ActiveTrackSpec] RETURNS [quit: BOOLEAN _ FALSE, segSpec: RouteChannel.ActiveSegSpec _ NIL];
debug: BOOLEAN _ FALSE;
stopTrack: NAT _ 50;

TopoWiring: PUBLIC PROCEDURE[routingArea: Route.RoutingArea, opt: Route.Optimization] RETURNS [bestResult: Route.RoutingResult] = {
lastMethod: RouteChannel.Method _ NEW[RouteChannel.MethodRec];
bestMethod: RouteChannel.Method;
result: Route.RoutingResult;
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
maxL: NAT = LAST[NAT];
bestResult _ NEW[Route.RoutingResultRec _ [routingArea, maxL, maxL, maxL, maxL, maxL, maxL, maxL, Route.Rect[maxL, maxL, maxL, maxL]]];

FOR method: RouteChannel.Method _ GetNextMethod[lastMethod], GetNextMethod[lastMethod] WHILE method # NIL DO
result _ RouteOneChan[routingArea, method];
lastMethod _ method;
IF debug THEN RouteChannel.WriteResult[result, method];

IF RouteUtil.CompareResult[result, bestResult] = less THEN
{bestResult _ result; bestMethod _ method};
IF opt = noIncompletes AND bestResult.numIncompletes = 0 THEN EXIT;
ENDLOOP;

IF bestMethod # lastMethod THEN
bestResult _ RouteOneChan[routingArea, bestMethod];

RouteChannel.WriteResult[bestResult, bestMethod]};

GetNextMethod: PROCEDURE [currentMethod: RouteChannel.Method]
RETURNS [nextMethod: RouteChannel.Method] = {

SELECT currentMethod.directionSequence FROM
start =>
nextMethod _ NEW[RouteChannel.MethodRec _ [outsideInTop, leftToRight]];
leftToRight =>
nextMethod _ NEW[RouteChannel.MethodRec _ [currentMethod.trackSequence, rightToLeft]];
rightToLeft =>
nextMethod _ NEW[RouteChannel.MethodRec _ [currentMethod.trackSequence, alternateLeft]];
alternateLeft =>
nextMethod _ NEW[RouteChannel.MethodRec _ [currentMethod.trackSequence, alternateRight]];
alternateRight =>
BEGIN
nextMethod _ NEW[RouteChannel.MethodRec _ [currentMethod.trackSequence, leftToRight]];
SELECT currentMethod.trackSequence FROM
start =>
nextMethod.trackSequence _ outsideInTop;
outsideInTop =>
nextMethod.trackSequence _ outsideInBottom;
outsideInBottom =>
nextMethod.trackSequence _ botToTop;
botToTop =>
nextMethod.trackSequence _ topToBot;
topToBot =>
nextMethod _ NIL;
ENDCASE;
END;
ENDCASE;

IF debug AND nextMethod # NIL THEN {
TerminalIO.WriteRope[Rope.Cat["\nNew method: ", RouteChannel.directionSequenceName[nextMethod.directionSequence], ", ", RouteChannel.trackSequenceName[nextMethod.trackSequence]]]};
};

RouteOneChan: PROCEDURE[routingArea: Route.RoutingArea, method: RouteChannel.Method]
RETURNS [result: Route.RoutingResult] = {

InitOneChan[routingArea];
PreAssignSegs[routingArea, method];
AssignVariableSegs[routingArea, method];
result _ AnalyzeResult[routingArea];
}; -- RouteOneChan

InitOneChan: PROCEDURE[routingArea: Route.RoutingArea] = {

SetTrackPos: RouteChannel.EachTrackActionProc = {
chanTracks.tracks[trackIndex].trackNum _ trackIndex;
chanTracks.tracks[trackIndex].firstSeg _ NIL;
chanTracks.tracks[trackIndex].keep _ FALSE};

ClearSegs: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
{FOR LRSide: RouteChannel.ChanLRSide IN RouteChannel.ChanLRSide DO
seg: RouteChannel.Segment _ pin.conctSeg[LRSide];
IF seg # NIL THEN
{seg.trackNum _ 0; seg.nextSeg _ NIL}
ENDLOOP}};

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks;
chanTracks.count _ chanTracks.maxCount;
[] _ RouteChannel.EnumTracks[routingArea, SetTrackPos];

FOR posIndex: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO
pinPos: RouteChannel.PinPosition _ chanPins.sides[posIndex];
[] _ RouteChannel.EnumPins[routingArea, pinPos, ClearSegs]
ENDLOOP}; -- InitOneChan

PreAssignSegs: PROCEDURE[routingArea: Route.RoutingArea, method: RouteChannel.Method] = {

PreSegProc: SegProc = {
IF seg # NIL THEN
IF seg.trackNum = 0 AND seg.trackConstraint # 0 AND ~seg.failed THEN {
segSpec _ NEW[RouteChannel.ActiveSegSpecRec _ [seg: seg, segLayer: CanConvert[routingArea, seg]]];
quit _ FitSegment[routingArea, segSpec, activeTrackSpec, FALSE]};
};
chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];

FOR activeTrackSpec: RouteChannel.ActiveTrackSpec _ NextTrack[routingArea, NIL, method], NextTrack[routingArea, activeTrackSpec, method] WHILE activeTrackSpec # NIL DO
FOR activeSegSpec: RouteChannel.ActiveSegSpec _ GetNextSegment[routingArea, NIL, activeTrackSpec, PreSegProc], GetNextSegment[routingArea, activeSegSpec, activeTrackSpec, PreSegProc] WHILE activeSegSpec # NIL DO

PlaceSegment[routingArea, activeSegSpec, activeTrackSpec];
ENDLOOP; -- FOR GetNextSegment

ENDLOOP; -- FOR activeTrackSpec:  
}; -- PreAssignSegs

AssignVariableSegs: PROCEDURE[routingArea: Route.RoutingArea, method: RouteChannel.Method] = {

AsgnSegProc: SegProc = {
IF seg # NIL THEN
IF seg.trackNum = 0 AND ~seg.failed THEN {
segSpec _ NEW[RouteChannel.ActiveSegSpecRec _ [seg: seg, segLayer: CanConvert[routingArea, seg]]];
quit _ FitSegment[routingArea, segSpec, activeTrackSpec, TRUE]};
};

moreToDo: BOOLEAN _ TRUE;
numTracksWOSegs: NAT _ 0;

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];

FOR activeTrackSpec: RouteChannel.ActiveTrackSpec _ NextTrack[routingArea, NIL, method], NextTrack[routingArea, activeTrackSpec, method] WHILE moreToDo AND activeTrackSpec # NIL DO
segOnThisTrack: BOOLEAN _ FALSE;
FOR activeSegSpec: RouteChannel.ActiveSegSpec _ GetNextSegment[routingArea, NIL, activeTrackSpec, AsgnSegProc], GetNextSegment[routingArea, activeSegSpec, activeTrackSpec, AsgnSegProc] WHILE activeSegSpec # NIL DO
stillGoing: BOOLEAN _ TRUE;
nextSegSpec: RouteChannel.ActiveSegSpec;

PlaceSegment[routingArea, activeSegSpec, activeTrackSpec]; segOnThisTrack _ TRUE;
nextSegSpec _ FollowingSeg[routingArea, activeSegSpec, activeTrackSpec, TRUE];
WHILE nextSegSpec # NIL AND stillGoing DO
fits: BOOLEAN;
nextSegSpec.segLayer _ CanConvert[routingArea, nextSegSpec.seg];
fits _ FitSegment[routingArea, nextSegSpec, activeTrackSpec, TRUE];
IF fits THEN
{PlaceSegment[routingArea, nextSegSpec, activeTrackSpec];
nextSegSpec _ FollowingSeg[routingArea, nextSegSpec, activeTrackSpec, TRUE]}
ELSE
stillGoing _ FALSE;
ENDLOOP; -- WHILE nextSeg # NIL
ENDLOOP; -- FOR GetNextSegment

IF segOnThisTrack THEN {numTracksWOSegs _ 0; moreToDo _ TRUE}
ELSE {
numTracksWOSegs _ numTracksWOSegs+ 1;
IF parms.routerUsed = channel AND numTracksWOSegs >= chanData.chanParms.emptyTrackLimit THEN
moreToDo _ FALSE};
ENDLOOP; -- WHILE moreToDo
}; -- AssignVariableSegs

NextTrack: PROCEDURE[routingArea: Route.RoutingArea, activeTrackSpec: RouteChannel.ActiveTrackSpec, method: RouteChannel.Method]
RETURNS [nextTrackSpec: RouteChannel.ActiveTrackSpec] = {

OutsideInTopStop: PROCEDURE[track: RouteChannel.MaxTracks] RETURNS [BOOLEAN] = {
IF chanTracks.count MOD 2 # 0 THEN RETURN[track = chanTracks.count/2 + 1]
ELSE RETURN[track = chanTracks.count/2]};

OutsideInBottomStop: PROCEDURE[track: RouteChannel.MaxTracks] RETURNS [BOOLEAN] = {
RETURN[track = chanTracks.count/2 + 1]};

trialTrack: RouteChannel.ZMaxTracks;
freeArea: RouteChannel.AboveOrBelow;
going: RouteChannel.GoingDirection;
chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks;
IF activeTrackSpec = NIL THEN {
SELECT method.trackSequence FROM
outsideInTop => {trialTrack _ chanTracks.count; freeArea _ below};
outsideInBottom => {trialTrack _ 1; freeArea _ above};
botToTop => {trialTrack _ 1; freeArea _ above};
topToBot => {trialTrack _ chanTracks.count; freeArea _ below};
ENDCASE => Route.Error[programmingError, "Pack direction error"];

SELECT method.directionSequence FROM
leftToRight, alternateLeft => going _ leftToRight;
rightToLeft, alternateRight => going _ rightToLeft;
ENDCASE => Route.Error[programmingError, "Pack direction error"]}

ELSE { -- keep going
IF ~(activeTrackSpec.track IN RouteChannel.MaxTracks) THEN
Route.Error[programmingError, "Invalid track state"];
SELECT method.trackSequence FROM
outsideInTop =>
IF OutsideInTopStop[activeTrackSpec.track] THEN trialTrack _ 0
ELSE IF activeTrackSpec.track > chanTracks.count/2 THEN
{trialTrack _ chanTracks.count - activeTrackSpec.track + 1; freeArea _ above}
ELSE
{trialTrack _ chanTracks.count - activeTrackSpec.track; freeArea _ below};
outsideInBottom =>
IF OutsideInBottomStop[activeTrackSpec.track] THEN trialTrack _ 0
ELSE IF activeTrackSpec.track <= chanTracks.count/2 THEN
{trialTrack _ chanTracks.count - activeTrackSpec.track + 1; freeArea _ below}
ELSE
{trialTrack _ chanTracks.count - activeTrackSpec.track + 2; freeArea _ above};
botToTop =>
IF activeTrackSpec.track >= chanTracks.count THEN trialTrack _ 0 
ELSE
{trialTrack _ activeTrackSpec.track + 1; freeArea _ above};
topToBot =>
IF activeTrackSpec.track <= 1 THEN trialTrack _ 0
ELSE
{trialTrack _ activeTrackSpec.track - 1; freeArea _ below};
ENDCASE => Route.Error[programmingError, "Pack direction error"];

SELECT method.directionSequence FROM
leftToRight => going _ leftToRight;
rightToLeft => going _ rightToLeft;
alternateLeft =>
IF activeTrackSpec.going = leftToRight THEN going _ rightToLeft
ELSE going _ leftToRight;
alternateRight =>
IF activeTrackSpec.going = rightToLeft THEN going _ leftToRight
ELSE going _ rightToLeft;
ENDCASE => Route.Error[programmingError, "Pack direction error"]};

IF ~(trialTrack IN [1 .. chanTracks.count]) THEN nextTrackSpec _ NIL
ELSE
{nextTrackSpec _ NEW[RouteChannel.ActiveTrackSpecRec];
BuildTrackSpec[routingArea, trialTrack, chanTracks.count, going, freeArea, nextTrackSpec];
IF debug THEN
{TerminalIO.WriteRope[Rope.Cat["\n   New track: ", Convert.RopeFromInt[trialTrack], ", min Act: ", Convert.RopeFromInt[nextTrackSpec.minActTrack]]];
TerminalIO.WriteRope[Rope.Cat[", max Act: ", Convert.RopeFromInt[nextTrackSpec.maxActTrack]]];
TerminalIO.WriteRope[Rope.Cat["\n   going: ", RouteChannel.GoingName[going], ", free area: ", RouteChannel.AboveOrBelowName[freeArea]]]}};
}; -- NextTrack

PlaceSegment: PROCEDURE[routingArea: Route.RoutingArea, activeSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks;
track: RouteChannel.ZMaxTracks _ activeTrackSpec.track;
mustKeep: RouteChannel.ZMaxTracks _ RouteChannel.InfluenceTracks[routingArea, activeSegSpec.seg.net.trunkWidth];
lowerTrack: RouteChannel.ZMaxTracks _ MAX[track - mustKeep, 1];
upperTrack: RouteChannel.ZMaxTracks _ MIN[track + mustKeep, chanTracks.count];
firstSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[routingArea, track];

IF activeSegSpec.seg.trackNum # 0 THEN Route.Error[programmingError, "Track state error"]
ELSE activeSegSpec.seg.trackNum _ track;

activeSegSpec.seg.routingLayer _ activeSegSpec.segLayer;
FOR keepTrack: RouteChannel.ZMaxTracks IN [lowerTrack .. upperTrack] DO
chanTracks.tracks[keepTrack].keep _ TRUE
ENDLOOP;

IF firstSeg = NIL THEN {
activeSegSpec.seg.nextSeg _ NIL;
chanTracks.tracks[track].firstSeg _ activeSegSpec.seg}

ELSE IF activeSegSpec.seg.exteriorPins[chanRight].pinPosition.pLoc <= firstSeg.exteriorPins[chanLeft].pinPosition.pLoc THEN {
activeSegSpec.seg.nextSeg _ firstSeg;
chanTracks.tracks[track].firstSeg _ activeSegSpec.seg}

ELSE {
nextSeg: RouteChannel.Segment;
lastSeg: RouteChannel.Segment _ firstSeg;
FOR nextSeg _ lastSeg.nextSeg, lastSeg.nextSeg WHILE nextSeg # NIL DO

IF lastSeg.exteriorPins[chanRight].pinPosition.pLoc <= activeSegSpec.seg.exteriorPins[chanLeft].pinPosition.pLoc THEN
EXIT;
lastSeg _ nextSeg;
ENDLOOP;
lastSeg.nextSeg _ activeSegSpec.seg;
activeSegSpec.seg.nextSeg _ nextSeg}}; -- PlaceSegment
FitSegment: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec, useConstraints: BOOLEAN]
RETURNS [fitsSoFar: BOOLEAN _ FALSE] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track;
blocked: BOOLEAN _ chanData.chanTracks.tracks[trackNum].blocked;
trackConstraint: RouteChannel.ZMaxTracks _ nextSegSpec.seg.trackConstraint;
IF (trackConstraint # 0 AND trackConstraint # activeTrackSpec.track) OR blocked THEN
RETURN[fitsSoFar]; 
fitsSoFar _ FitSegmentThisTrack[routingArea, nextSegSpec, activeTrackSpec];
IF fitsSoFar THEN
fitsSoFar _ FitSegmentAdjTracks[routingArea, nextSegSpec, activeTrackSpec, chanData.chanTracks.count];
IF fitsSoFar AND useConstraints THEN
fitsSoFar _ FitSegmentConstraints[routingArea, nextSegSpec, activeTrackSpec];

RETURN[fitsSoFar]}; -- FitSegment

FitSegmentThisTrack: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec]
RETURNS [fitsSoFar: BOOLEAN _ TRUE] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks;
rules: Route.DesignRules _ routingArea.rules;
trialSeg: RouteChannel.Segment _ nextSegSpec.seg;
trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track;
segLayer: RoutePrivate.RoutingLayerOrNone _ nextSegSpec.segLayer;

FOR existingSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[routingArea, trackNum], existingSeg.nextSeg
WHILE existingSeg # NIL AND fitsSoFar DO

IF existingSeg.net.netNum # trialSeg.net.netNum OR
existingSeg.net.netPart # trialSeg.net.netPart THEN {
trunkTrunk: Route.Number _ rules.contactToContact - rules.branchSpacing;
trunkBranch: Route.Number _ rules.branchToContact - rules.branchSpacing;
branchBranch: Route.Number _ rules.branchSpacing;
SELECT TRUE FROM
segLayer = trunk AND existingSeg.routingLayer = trunk =>
fitsSoFar _ ~OverlapCheck[existingSeg, trialSeg, trunkTrunk];
segLayer = trunk AND existingSeg.routingLayer = branch =>
fitsSoFar _ ~EndOverlapCheck[existingSeg, trialSeg, trunkBranch];
segLayer = branch AND existingSeg.routingLayer = trunk =>
fitsSoFar _ ~EndOverlapCheck[trialSeg, existingSeg, trunkBranch];
segLayer = branch AND existingSeg.routingLayer = branch =>
fitsSoFar _ ~OverlapCheck[existingSeg, trialSeg, branchBranch];
ENDCASE};
ENDLOOP}; -- FitSegmentThisTrack

FitSegmentAdjTracks: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec, maxTrack: RouteChannel.ZMaxTracks]
RETURNS [fitsSoFar: BOOLEAN _ TRUE] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks;
firstPass: BOOLEAN _ TRUE;
rules: Route.DesignRules _ routingArea.rules;
trialSeg: RouteChannel.Segment _ nextSegSpec.seg;
pinsOnTrialSeg: RouteChannel.ChanPinList;
trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track;
trialPos: Route.Number _ RouteChannel.TrackLoc[routingArea, trackNum];
edgeSpacing: Route.Number _ rules.trunkSpacing;
maxPos: Route.Number _ RouteChannel.TrackLoc[routingArea, maxTrack] + rules.trunkToEdge - edgeSpacing;
minPos: Route.Number _ RouteChannel.TrackLoc[routingArea, 1] - rules.trunkToEdge + edgeSpacing;
segLayer: RoutePrivate.RoutingLayerOrNone _ nextSegSpec.segLayer;
qTrunkTrunk: Route.Number _ rules.trunkSpacing;
IF maxPos < trialPos + trialSeg.qWidth/2 OR trialPos - trialSeg.qWidth/2  < minPos THEN
fitsSoFar _ FALSE;

FOR adjTrack: RouteChannel.MaxTracks IN [activeTrackSpec.minActTrack .. activeTrackSpec.maxActTrack] WHILE fitsSoFar DO
IF adjTrack # activeTrackSpec.track THEN {
adjTrackPos: Route.Number _ RouteChannel.TrackLoc[routingArea, adjTrack];
contactToContact: Route.Number _ rules.contactToContact;
IF firstPass THEN { -- don't get pinsOnTrialSeg until needed
firstPass _ FALSE; 
pinsOnTrialSeg _ RouteChannel.GetPinsOnSeg[trialSeg]};
FOR existingSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[routingArea, adjTrack], existingSeg.nextSeg
WHILE existingSeg # NIL AND fitsSoFar DO
IF existingSeg.net.netNum # trialSeg.net.netNum OR
existingSeg.net.netPart # trialSeg.net.netPart THEN
{-- check to see if contacts interfere with each other
IF segLayer = trunk AND existingSeg.routingLayer =  trunk THEN {
pinsOnExistSeg: RouteChannel.ChanPinList _ RouteChannel.GetPinsOnSeg[existingSeg];
FOR trialPins: RouteChannel.ChanPinList _ pinsOnTrialSeg, trialPins.rest WHILE trialPins # NIL AND fitsSoFar DO
trialPin: RouteChannel.ChanPin _ trialPins.first;
FOR existPins: RouteChannel.ChanPinList _ pinsOnExistSeg, existPins.rest WHILE existPins # NIL AND fitsSoFar DO
existPin: RouteChannel.ChanPin _ existPins.first;
fitsSoFar _ ~ContactCheck[trialPin, trialPos, existPin, adjTrackPos, contactToContact];
ENDLOOP;
ENDLOOP};

IF ABS[trialPos - adjTrackPos] < trialSeg.qWidth/2 + qTrunkTrunk + existingSeg.qWidth/2 THEN
fitsSoFar _ ~OverlapCheck[existingSeg, trialSeg, qTrunkTrunk]};
ENDLOOP};
ENDLOOP}; -- FitSegmentAdjTracks

FitSegmentConstraints: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec]
RETURNS [fitsSoFar: BOOLEAN _ TRUE] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
graph: RouteDiGraph.Graph _ chanData.constraints;
trialSeg: RouteChannel.Segment _ nextSegSpec.seg;
IF activeTrackSpec.freeArea = above THEN {
IF fitsSoFar THEN
fitsSoFar _ ~ConstraintCheck[graph, trialSeg, below, activeTrackSpec.track, TRUE];
IF fitsSoFar THEN
fitsSoFar _ ~ConstraintCheck[graph, trialSeg, above, activeTrackSpec.track, FALSE]};

IF activeTrackSpec.freeArea = below THEN {
IF fitsSoFar THEN
fitsSoFar _ ~ConstraintCheck[graph, trialSeg, above, activeTrackSpec.track, TRUE];
IF fitsSoFar THEN
fitsSoFar _ ~ConstraintCheck[graph, trialSeg, below, activeTrackSpec.track, FALSE]};
RETURN[fitsSoFar]}; -- FitSegmentConstraints

EndOverlapCheck: PROCEDURE[seg1, seg2: RouteChannel.Segment, dist: Route.Number]
RETURNS [overlap: BOOLEAN] = {

leftPin1: RouteChannel.ChanPin _ seg1.exteriorPins[chanLeft];
left1Loc: Route.Number _ leftPin1.pinPosition.pLoc - leftPin1.pWidth/2;
rightPin1: RouteChannel.ChanPin _ seg1.exteriorPins[chanRight];
right1Loc: Route.Number _ rightPin1.pinPosition.pLoc + rightPin1.pWidth/2;
leftPin2: RouteChannel.ChanPin _ seg2.exteriorPins[chanLeft];
left2Loc: Route.Number _ leftPin2.pinPosition.pLoc - leftPin2.pWidth/2;
rightPin2: RouteChannel.ChanPin _ seg2.exteriorPins[chanRight];
right2Loc: Route.Number _ rightPin2.pinPosition.pLoc + rightPin2.pWidth/2;

gap: RoutePrivate.Range _ RouteChannel.Gap[[left1Loc, right1Loc], [left2Loc, right2Loc]];
IF gap.l > gap.r THEN overlap _ TRUE
ELSE overlap _ gap.r - gap.l < dist};


OverlapCheck: PROCEDURE[seg1, seg2: RouteChannel.Segment, dist: Route.Number]
RETURNS [overlap: BOOLEAN] = {

overlap _ EndOverlapCheck[seg1, seg2, dist] OR EndOverlapCheck[seg2, seg1, dist]};

ContactCheck: PROCEDURE[pin1: RouteChannel.ChanPin, qPos1: Route.Number, pin2: RouteChannel.ChanPin, qPos2, dist: Route.Number] RETURNS [overlap: BOOLEAN _ FALSE] =

BEGIN
IF ABS[qPos1 - qPos2] < dist THEN {
left1Loc: Route.Number _ pin1.pinPosition.pLoc - pin1.pWidth/2;
right1Loc: Route.Number _ pin1.pinPosition.pLoc + pin1.pWidth/2;
left2Loc: Route.Number _ pin2.pinPosition.pLoc - pin2.pWidth/2;
right2Loc: Route.Number _ pin2.pinPosition.pLoc + pin2.pWidth/2;
gap: RoutePrivate.Range _ RouteChannel.Gap[[left1Loc, right1Loc], [left2Loc, right2Loc]];
IF gap.l > gap.r THEN overlap _ TRUE
ELSE overlap _ gap.r - gap.l < dist};
END; -- ContactCheck

ConstraintCheck: PROCEDURE[graph: RouteDiGraph.Graph, segment: RouteChannel.Segment,
direction: RouteChannel.AboveOrBelow, track: RouteChannel.MaxTracks, mustBePlaced: BOOLEAN]
RETURNS [constrained: BOOLEAN _ FALSE] = {


CheckConstraints: RouteDiGraph.EnumArcsFromNodeProc = {
nextNode: RouteDiGraph.Node _ IF direction = in THEN arc.inferiorNode ELSE arc.superiorNode;
nodeInfo: RouteChannel.SegmentConstraint _ NARROW[nextNode.nodeInfo];
segment: RouteChannel.Segment _ nodeInfo.segment;
IF segment.trackNum = 0 THEN {
IF mustBePlaced THEN quit _ TRUE} -- segment must be placed
ELSE {
IF direction = out THEN
quit _ track >= segment.trackNum
ELSE
quit _ track <= segment.trackNum};

IF ~quit THEN
quit _ RouteDiGraph.EnumArcsFromNode[graph, nextNode, direction, CheckConstraints]};

node: RouteDiGraph.Node _ segment.constraintNode;
gDirection: RouteDiGraph.Direction _ IF direction = above THEN out ELSE in;
constrained _ RouteDiGraph.EnumArcsFromNode[graph, node, gDirection, CheckConstraints];
};

GetNextSegment: PROCEDURE[routingArea: Route.RoutingArea, activeSegSpec: RouteChannel.ActiveSegSpec, activeTrackSpec: RouteChannel.ActiveTrackSpec, segProc: SegProc]
RETURNS [nextSegSpec: RouteChannel.ActiveSegSpec _ NIL] = {

CheckSegs: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN {
[quit, trialSegSpec] _ segProc[pin.conctSeg[whichSide], activeTrackSpec];
IF ~quit THEN [quit, trialSegSpec] _ segProc[pin.altConctSeg[whichSide], activeTrackSpec]}};

found: BOOLEAN _ FALSE;
whichSide: RouteChannel.ChanLRSide;
pinPos: RouteChannel.ZMPinsOnCh;
chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
lastIndex: RouteChannel.ZMPinsOnCh _ chanData.chanPins.count;
trialSegSpec: RouteChannel.ActiveSegSpec;

SELECT activeTrackSpec.going FROM
leftToRight => {
IF activeSegSpec = NIL THEN pinPos _ 1
ELSE pinPos _ activeSegSpec.seg.exteriorPins[chanLeft].pinPosition.pinIndex;
whichSide _ chanRight;
FOR posIndex: RouteChannel.MPinsOnCh IN [pinPos .. lastIndex] WHILE ~ found DO
pinPosition: RouteChannel.PinPosition _ chanData.chanPins.sides[posIndex];
found _ RouteChannel.EnumPins[routingArea, pinPosition, CheckSegs]
ENDLOOP};  -- posIndex

rightToLeft => {
IF activeSegSpec = NIL THEN pinPos _ lastIndex
ELSE pinPos _ activeSegSpec.seg.exteriorPins[chanRight].pinPosition.pinIndex;
whichSide _ chanLeft;
FOR posIndex: RouteChannel.MPinsOnCh DECREASING IN [pinPos .. 1] WHILE ~ found DO
pinPosition: RouteChannel.PinPosition _ chanData.chanPins.sides[posIndex];
found _ RouteChannel.EnumPins[routingArea, pinPosition, CheckSegs]
ENDLOOP};  -- posIndex
ENDCASE;

IF found THEN nextSegSpec _ trialSegSpec;
IF debug AND nextSegSpec # NIL THEN
IF nextSegSpec.seg # NIL THEN
{TerminalIO.WriteRope[Rope.Cat["\n      New segment: ", nextSegSpec.seg.net.name, ", ", RoutePrivate.RoutingLayerName[nextSegSpec.segLayer]]]};
}; -- GetNextSegment

FollowingSeg: PUBLIC PROCEDURE [routingArea: Route.RoutingArea, activeSegSpec: RouteChannel.ActiveSegSpec,
activeTrackSpec: RouteChannel.ActiveTrackSpec, includeUnPlaced: BOOLEAN]
RETURNS [nextSegSpec: RouteChannel.ActiveSegSpec _ NIL] = {

CheckFitSegs: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
{seg: RouteChannel.Segment _ pin.conctSeg[existingSide];
IF seg # NIL THEN 
IF seg = activeSegSpec.seg THEN
{trialSegSpec: RouteChannel.ActiveSegSpec _ NEW[RouteChannel.ActiveSegSpecRec _ [seg: pin.conctSeg[newSide]]];
IF trialSegSpec.seg # NIL THEN
IF ~includeUnPlaced OR trialSegSpec.seg.trackNum = 0 THEN nextSegSpec _ trialSegSpec;
quit _ TRUE}}};

existingSide, newSide: RouteChannel.ChanLRSide;
pinPos: RouteChannel.PinPosition;
found: BOOLEAN _ FALSE;

SELECT activeTrackSpec.going FROM
leftToRight =>
{pinPos _ activeSegSpec.seg.exteriorPins[chanRight].pinPosition;
existingSide _ chanLeft;
newSide _ chanRight};
rightToLeft =>
{pinPos _ activeSegSpec.seg.exteriorPins[chanLeft].pinPosition;
existingSide _ chanRight;
newSide _ chanLeft};
ENDCASE;

found _ RouteChannel.EnumPins[routingArea, pinPos, CheckFitSegs]
}; -- FollowingSeg


AnalyzeResult: PROCEDURE[routingArea: Route.RoutingArea] RETURNS [result: Route.RoutingResult] = {

RemoveTrackIfPossible: PROCEDURE[routingArea: Route.RoutingArea, track, oldNumTracks: RouteChannel.MaxTracks]
RETURNS [numTracks: RouteChannel.ZMaxTracks] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks;
IF track = stopTrack THEN track _ stopTrack;

IF ~chanTracks.tracks[track].blocked AND ~chanTracks.tracks[track].keep THEN
numTracks _ RemoveTrack[routingArea, track, oldNumTracks] -- assume track can be removed
ELSE numTracks _ oldNumTracks};


CheckRules: PROCEDURE[routingArea: Route.RoutingArea, trackSpec: RouteChannel.ActiveTrackSpec, maxTrack: RouteChannel.ZMaxTracks]
RETURNS [fitsSoFar: BOOLEAN _ TRUE] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
rules: Route.DesignRules _ routingArea.rules;
track: RouteChannel.MaxTracks _ trackSpec.track;
FOR existingSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[routingArea, track], existingSeg.nextSeg WHILE existingSeg # NIL AND fitsSoFar DO
segSpec.seg _ existingSeg;
segSpec.segLayer _ existingSeg.routingLayer;
fitsSoFar _ FitSegmentAdjTracks[routingArea, segSpec, trackSpec, maxTrack];
ENDLOOP};

EnumExits: RouteChannel.EnumExitsProc = {
IF constructedExit THEN
IF ~RouteChannel.MembRopeList[name, breakAtExitList] THEN 
breakAtExitList _ CONS[name, breakAtExitList]};

EnumSegments: RouteChannel.EnumSegmentsProc = {

length: Route.Number _ RouteUtil.Length[pos1, pos2];
SELECT TRUE FROM
layer = metalLayer => metal1length _ metal1length + length;
layer = metal2Layer => metal2length _ metal2length + length;
layer = polyLayer => polyLength _ polyLength + length;
ENDCASE => otherLength _ otherLength + length};

EnumPins: RouteChannel.EnumPinsProc = {

pinLayer: Route.Layer _ CDPinObjects.GetLayer[pin.pin];
IF layer = polyLayer AND pinLayer = metalLayer OR layer = metalLayer AND pinLayer = polyLayer THEN
polyToMetal _ polyToMetal +1
ELSE IF layer = metalLayer AND pinLayer = metal2Layer OR layer = metal2Layer AND pinLayer = metalLayer THEN
metalToMetal2 _ metalToMetal2 +1};

EnumVias: RouteChannel.EnumViasProc = {
IF layer1 = polyLayer AND layer2 = metalLayer OR layer1 = metalLayer AND layer2 = polyLayer THEN
polyToMetal _ polyToMetal +1
ELSE IF layer1 = metalLayer AND layer2 = metal2Layer OR layer1 = metal2Layer AND layer2 = metalLayer THEN
metalToMetal2 _ metalToMetal2 +1};

EnumIncompletes: RouteChannel.EnumIncompletesProc = {
numIncompletes _ numIncompletes +1;
IF ~RouteChannel.MembRopeList[name, incompleteList] THEN 
incompleteList _ CONS[name, incompleteList]};

ElimUselessTracks: RouteChannel.EachTrackActionProc = {
IF RouteChannel.TrackSeg[routingArea, trackIndex] = NIL THEN  -- this track has no segments
numTracks _ RemoveTrackIfPossible[routingArea, trackIndex, numTracks]};

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks;
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
metal1length, metal2length, polyLength, otherLength: Route.Number _ 0;
polyToMetal, metalToMetal2, numIncompletes: NAT _ 0;
technology: CD.Technology _ NARROW[routingArea.rules.technology];
metalLayer: Route.Layer _ CD.FetchLayer[technology, $met];
metal2Layer: Route.Layer _ CD.FetchLayer[technology, $met2];
polyLayer: Route.Layer _ CD.FetchLayer[technology, $pol];
rect: Route.Rect;
loc1, loc2: Route.Position;
incompleteList: LIST OF Rope.ROPE _ NIL;
breakAtExitList: LIST OF Rope.ROPE _ NIL;
numTracks: RouteChannel.ZMaxTracks _ chanTracks.count;
lowerTrackSpec: RouteChannel.ActiveTrackSpec _ NEW[RouteChannel.ActiveTrackSpecRec];
upperTrackSpec: RouteChannel.ActiveTrackSpec _ NEW[RouteChannel.ActiveTrackSpecRec];
segSpec: RouteChannel.ActiveSegSpec _ NEW[RouteChannel.ActiveSegSpecRec];
IF parms.routerUsed = channel THEN {
[] _ RouteChannel.EnumTracks[routingArea, ElimUselessTracks];
chanTracks.count _ numTracks};

loc1 _ RouteUtil.PQToXY[routingArea, [chanData.chanPins.cEnd1, chanData.chanSides[chanBottom].routeAreaCoord]];
IF parms.routerUsed = channel THEN {
thisChanWidth: Route.Number _ RouteChannel.ChannelWidth[routingArea];
loc2 _ RouteUtil.PQToXY[routingArea, [chanData.chanPins.cEnd2, chanData.chanSides[chanBottom].routeAreaCoord + thisChanWidth]]}
ELSE IF parms.routerUsed = switchBox THEN
loc2 _ RouteUtil.PQToXY[routingArea, [chanData.chanPins.cEnd2, chanData.chanSides[chanTop].routeAreaCoord]];

rect _ [loc1.x, loc1.y, loc2.x, loc2.y];

[] _ RouteChannel.GetRouting[routingArea, rect, NIL, EnumSegments,
EnumPins, EnumVias, EnumExits, EnumIncompletes];

result _ NEW[Route.RoutingResultRec _ [routingArea, polyLength, metal1length, metal2length, polyToMetal, metalToMetal2, chanTracks.count, numIncompletes, rect, FALSE, incompleteList, breakAtExitList]];
}; -- AnalyzeResult

CanConvert: PROCEDURE[routingArea: Route.RoutingArea, seg: RouteChannel.Segment]
RETURNS [segLayer: RoutePrivate.RoutingLayerOrNone _ trunk] = {
-- see if this trunk routingLayer seg can be pulled down onto the branch routingLayer

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
leftPin: RouteChannel.PinPosition _ seg.exteriorPins[chanLeft].pinPosition;
rightPin: RouteChannel.PinPosition _ seg.exteriorPins[chanRight].pinPosition;
segLength: Route.Number _ rightPin.pLoc - leftPin.pLoc;

IF segLength <= chanData.chanParms.maxToConvert AND leftPin.pinIndex = rightPin.pinIndex + 1 THEN segLayer _ branch};

RemoveTrack: PROCEDURE [routingArea: Route.RoutingArea, track, oldNumTracks: RouteChannel.ZMaxTracks] RETURNS [numTracks: RouteChannel.ZMaxTracks] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks;
trackNum, oldTrackNum: RouteChannel.MaxTracks; 
FOR upperTrack: RouteChannel.MaxTracks DECREASING IN [track+1 .. chanTracks.count] DO
chanTracks.tracks[upperTrack].oldTrackNum _ chanTracks.tracks[upperTrack].trackNum;
chanTracks.tracks[upperTrack].trackNum _ chanTracks.tracks[upperTrack-1].trackNum;
ENDLOOP;
IF track # 1 THEN chanTracks.tracks[track].trackNum _ chanTracks.tracks[track-1].trackNum;

FOR upperTrack: RouteChannel.MaxTracks IN [track+1 .. chanTracks.count] DO
trackNum _ chanTracks.tracks[upperTrack].trackNum;
oldTrackNum _ chanTracks.tracks[upperTrack].oldTrackNum;
chanTracks.tracks[trackNum].firstSeg _ chanTracks.tracks[oldTrackNum].firstSeg;
ENDLOOP;
IF track # chanTracks.count THEN {
oldTrackNum _ chanTracks.tracks[chanTracks.count].oldTrackNum;
chanTracks.tracks[oldTrackNum].firstSeg _ NIL};
numTracks _ oldNumTracks - 1};

PutBackTrack: PROCEDURE [routingArea: Route.RoutingArea, track, oldNumTracks: RouteChannel.ZMaxTracks] RETURNS [numTracks: RouteChannel.ZMaxTracks] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks;
trackNum, oldTrackNum: RouteChannel.MaxTracks;
IF track < chanTracks.count THEN
{actualTrack: RouteChannel.MaxTracks _ chanTracks.tracks[track+1].trackNum; 
FOR upperTrack: RouteChannel.MaxTracks DECREASING IN [track+1 .. chanTracks.count] DO
trackNum _ chanTracks.tracks[upperTrack].trackNum; 
oldTrackNum _ chanTracks.tracks[upperTrack].oldTrackNum; 
chanTracks.tracks[upperTrack].trackNum _ oldTrackNum;
chanTracks.tracks[oldTrackNum].firstSeg _ chanTracks.tracks[trackNum].firstSeg;
ENDLOOP;
chanTracks.tracks[actualTrack].firstSeg _ NIL};
numTracks _ oldNumTracks + 1};

BuildTrackSpec: PROCEDURE [routingArea: Route.RoutingArea, track, maxTracks: RouteChannel.ZMaxTracks, going: RouteChannel.GoingDirection, freeArea: RouteChannel.AboveOrBelow, trackSpec: RouteChannel.ActiveTrackSpec] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks;
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
influence: Route.Number _ RouteChannel.InfluenceTracks[routingArea, parms.widestTrunk] + 1;
trackSpec.minActTrack _ MAX[track - influence, 1];
trackSpec.maxActTrack _ MIN[track + influence, maxTracks];
trackSpec.track _ track;
trackSpec.going _ going;
trackSpec.freeArea _ freeArea};

END.



$RouteChannelTopolImpl.mesa   ///Route/RouteChannelTopolImpl.mesa
Bryan Preas February 27, 1986 11:20:46 am PST
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
channel route the routing area

start with a bad result
loop through the options
restore results of the best method
route this channel using the method described
initialize for one channel routing
empty all of the tracks of their segments
empty the segments attached to the pins
assign those segments that have fixed tracks
get next track to pack

put segments on active track
got segment, got track, place segment on track
route this channel using the method described
get next track to pack

put segments on active track
got segment, got track, place segment on track
check if we are finished
determine the next track to pack into
generate return varables
place this segment in this track
put track number in segment
link segment into list on track
no existing segments
this segment goes before first segment

check if this segment fits and satisfies the constraints

see if segments overlap in this track

see if segments interfere with each other

currently expanding up
check if this segment fits on this track
see if seg fits on this track
check if this segment fits on the adjacent tracks

check to see if wire interferes with edges
see if segments interfere with each other
check to see if wires interfere with each other
check if this segment satisfies the constraints
see if segments overlap in this track

currently expanding up
see if constraints below are satisfied: lower segs MUST be placed

if upper segments are placed, they must be above
currently expanding down
see if constraints above are satisfied: upper segs MUST be placed

if lower segments are placed, they must be below
recursively go through the constraints
return the next segment that fits and satisfies the constraints
got starting pin, scan the track
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
check the next seg basie on existingSide and newSide
check for design rule violations if track is removed
remove below after testing
okToRemove: BOOLEAN _ TRUE;
nextLowerTrack: RouteChannel.ZMaxTracks _ MAX[track - 1, 1];
nextUpperTrack: RouteChannel.ZMaxTracks _ MIN[track + 1, chanTracks.count];
IF nextLowerTrack # track THEN
{BuildTrackSpec [routingArea, nextLowerTrack, numTracks, leftToRight, above, lowerTrackSpec];
okToRemove _ CheckRules[routingArea, lowerTrackSpec, numTracks]};
IF nextUpperTrack # track AND okToRemove THEN
{BuildTrackSpec [routingArea, nextUpperTrack, numTracks, leftToRight, above, upperTrackSpec];
okToRemove _ CheckRules[routingArea, upperTrackSpec, numTracks]};
IF ~okToRemove THEN 
numTracks _ PutBackTrack[routingArea, track, numTracks]}};
check for design rule violations per trackSpec
do nothing, dont care about exits
count the vias
count the vias
count the incompletes

remove empty tracks if no design rule violation is created
AnalyzeResult

remove useless tracks
later I need to add ability to do wiring improvements:
reduce poly length, reduce number of vias
move tracks above this one down
move tracks above this one down
Κn˜š
œ@™@Icode™-—˜Jšœ
Οm
œ1™<Jš
œ.™.Jš
œ9™9—J˜š
Οk	˜	J˜Jšžœ
˜J˜
J˜J˜Jš
œ˜J˜
J˜
J˜
Jš
œ
˜
Jš
œ˜J˜—šœžœ
ž˜$Jšžœ
žœe˜oJšžœ
˜Jšžœ˜Jš
ž˜J˜JšΟnœžœžœKžœžœžœ(žœ˜ͺ
Jšœžœžœ
˜Jšœžœ˜J˜šŸ
œžœ
ž	œ:žœ&˜ƒ
J™J™Jšœ"žœ˜>Jš
œ ˜ Jš
œ˜Jšœ'žœ˜AJš
œ™Jšœžœžœ
žœ˜Jšœ
žœw˜‡
J˜Jš
œ™šžœTžœ
žœ
ž˜lJš
œ+˜+Jš
œ˜Jšžœžœ*˜7J˜šžœ4ž˜:Jš
œ+˜+—Jšžœžœžœ
žœ
˜CJšžœ
˜J˜—Jš
œ"™"šžœž˜Jš
œ3˜3—J˜Jš
œ2˜2J˜—šŸ
œž	œ%˜=Jšžœ&˜-J˜šžœ!ž˜+š
œ˜Jšœ
žœ7˜G—š
œ˜Jšœ
žœF˜V—š
œ˜Jšœ
žœH˜X—š
œ˜Jšœ
žœI˜Y—š
œ˜Jš
ž˜Jšœ
žœF˜Všžœž˜'š
œ˜Jš
œ(˜(—š
œ˜Jš
œ+˜+—š
œ˜Jš
œ$˜$—š
œ˜Jš
œ$˜$—š
œ˜Jšœ
žœ
˜—Jšžœ
˜—Jšžœ
˜—Jšžœ
˜J˜šžœžœžœ
žœ˜$Jš
œ΄
˜΄
——Jš
œ˜J˜—šŸœž	œ=˜TJšžœ"˜)Jš
œ-™-J˜Jš
œ˜Jš
œ#˜#Jš
œ(˜(Jš
œ$˜$Jšž
œΟcŸ˜J˜—šŸœž	œ$˜:Jš
œ"™"J˜Jš
œ)™)š
œ1˜1Jš
œ4˜4Jšœ)ž˜-Jš
œ,˜,J˜—š
œ-˜-šžœžœ
ž˜šœ
žœ!žœž˜BJš
œ1˜1šžœžœ
ž˜Jšœ!žœ
˜%—Jšžœ˜
——J˜—Jšœ%žœ˜EJš
œ>˜>Jš
œD˜DJš
œ'˜'Jš
œ7˜7J˜Jš
œ'™'šžœ"žœž˜@Jš
œ<˜<Jš
œ:˜:Jšžœ Ÿ˜—J˜—šŸ
œž	œA˜YJ™,J˜š
œ˜šžœžœ
ž˜šžœžœžœ
žœ˜FJšœ
žœU˜bJšœ9žœ˜A——Jš
œ˜—Jšœ%žœ˜EJšœ'žœ˜AJ˜Jš
œ™š	žœHžœ;žœžœ
ž˜§
J™Jš
œ™š	žœIžœhžœžœ
ž˜Σ
Jš
œ.™.J˜Jš
œ:˜:Jšžœ ž 
œ˜—J˜Jšžœ žœ˜"—Jšž
œ Ÿ
˜J˜—šŸœž	œA˜^Jš
œ-™-J˜š
œ˜šžœžœ
ž˜šžœžœ
žœ˜*Jšœ
žœU˜bJšœ9žœ˜@——Jš
œ˜—J˜Jšœ
žœžœ
˜Jšœžœ˜J˜Jšœ%žœ˜EJšœ'žœ˜AJ˜Jš
œ™šžœHžœ;žœ
žœžœ
ž˜΄
Jšœžœžœ
˜ J™Jš
œ™š	žœIžœjžœžœ
ž˜Υ
Jš
œ.™.Jšœžœžœ
˜Jš
œ(˜(J˜JšœLžœ
˜QJšœHžœ˜Nšžœžœ
žœž˜)Jšœžœ
˜Jš
œ@˜@Jšœ=žœ˜Cšžœž˜Jš
œ9˜9JšœFžœ˜L—š
ž˜Jšœ
žœ
˜—Jšžœ ž 
œ ˜—Jšžœ ž 
œ˜—J˜Jš
œ™Jšžœžœ"žœ
˜=šžœ˜Jš
œ%˜%šžœžœ7ž˜\Jšœžœ˜——Jšžœ ž 
œ˜—Jšž
œ Ÿ˜J˜—šŸ	œž	œl˜€
Jšžœ2˜9Jš
œ%™%J˜šŸœž	œ žœžœ˜PJšžœžœžœ
žœ ˜IJšžœ
žœ˜)—J˜šŸœž	œ žœžœ˜SJšžœ"˜(—J˜Jš
œ$˜$Jš
œ$˜$Jš
œ#˜#Jšœ%žœ˜EJš
œD˜Dšžœžœ
žœ˜šžœž˜ Jš
œB˜BJš
œ6˜6Jš
œ/˜/Jš
œ>˜>Jšžœ:˜A—J˜šžœž˜$Jš
œ2˜2Jš
œ3˜3Jšžœ:˜A——J˜šžœ 
˜šžœžœž˜:Jš
œ5˜5—šžœž˜ š
œ˜Jšžœ)žœ˜>šžœ
žœ,ž˜7Jš
œM˜M—š
ž˜Jš
œJ˜J——š
œ˜Jšžœ,žœ˜Ašžœ
žœ-ž˜8Jš
œM˜M—š
ž˜Jš
œN˜N——š
œ˜Jšžœ+žœ˜Aš
ž˜Jš
œ;˜;——š
œ˜Jšžœžœ˜1š
ž˜Jš
œ;˜;——Jšžœ:˜A—J˜šžœž˜$Jš
œ#˜#Jš
œ#˜#š
œ˜Jšžœ%žœ˜?Jšžœ˜—š
œ˜Jšžœ%žœ˜?Jšžœ˜—Jšžœ;˜B——J˜Jš
œ™Jšžœžœžœž˜Dš
ž˜Jšœžœ"˜6Jš
œZ˜Zšžœž˜
Jš
œ”
˜”
Jš
œ^˜^Jš
œŠ
˜Š
——Jšž
œ Ÿ	˜J˜—Jš
œ ™ šŸœž	œ~˜•
J˜Jšœ%žœ˜EJš
œD˜DJš
œ7˜7Jš
œp˜pJš
œ?˜?Jš
œN˜NJš
œK˜KJ˜Jš
œ™Jšžœ žœ3˜YJšžœ$˜(J˜Jš
œ8˜8šžœ$žœž˜GKšœ$ž˜(Kšžœ
˜—J˜Jš
œ™šžœžœ
žœ˜Jš
œ™Jšœžœ
˜ Jš
œ6˜6J˜—šžœ
žœpžœ˜}Jš
œ&™&Jš
œ%˜%Jš
œ6˜6J˜—šžœ˜Jš
œ˜Jš
œ)˜)šžœ,žœžœ
ž˜EJ˜šžœož˜uJšžœ
˜—Jš
œ˜Jšžœ
˜—Jš
œ$˜$Jšœ#žœ Ÿ˜6—J™—šŸ
œž	œ‰
žœ
˜¦
Jšžœ
žœžœ˜(Jš
œ8™8J˜Jšœ%žœ˜EJš
œ9˜9Jšœ	žœ0˜@Jš
œK˜Kšžœžœ*žœ	ž˜TJšžœ
˜—J™Jš
œ%™%Jš
œK˜KJ™Jš
œ)™)šžœž˜Jš
œf˜f—J™Jš
œ™šžœžœž˜$Jš
œM˜M—J˜Jšžœž
œ Ÿ
˜!J˜—šŸœž	œx˜–
Jšžœ
žœžœ˜'Jš
œ(™(J˜Jšœ%žœ˜EJš
œD˜DJš
œ-˜-Jš
œ1˜1Jš
œ9˜9Jš
œA˜AJ˜Jš
œ™šžœf˜iJšžœžœ
žœž˜(J˜šžœ.ž˜2Jšœ/žœ˜5J˜HJ˜HJ˜1šžœ
žœ
ž˜šœžœ$˜8Jš
œ=˜=—šœžœ%˜9Jš
œA˜A—šœžœ$˜9Jš
œA˜A—šœžœ%˜:Jš
œ?˜?—Jšžœ˜	——Jšžœ Ÿ˜ —J˜—šŸœž	œ›
˜Ή
Jšžœ
žœžœ˜'Jš
œ1™1J˜Jšœ%žœ˜EJš
œD˜DJšœžœžœ
˜Jš
œ-˜-Jš
œ1˜1Jš
œ)˜)Jš
œ9˜9Jš
œF˜FJš
œ/˜/Jš
œf˜fJš
œ_˜_Jš
œA˜AJš
œ/˜/J™Jš
œ*™*šžœ'žœ(ž˜WJšœžœ
˜—J˜Jš
œ)™)šžœ"žœ>žœž˜wšžœ"žœ˜*Jš
œI˜IJš
œ8˜8šžœžœ (˜<Jšœžœ˜Jš
œ6˜6—šžœf˜iJšžœžœ
žœž˜(šžœ.ž˜2Jšœ/ž˜3Jšœ
 5˜6šžœžœ#žœ˜@Jš
œR˜Rš	žœFžœ
žœ
žœž˜oJš
œ1˜1š	žœFžœ
žœ
žœž˜oJš
œ1˜1Jš
œW˜WJšžœ
˜—Jšžœ˜	J˜——Jš
œ/™/šžœ
žœRž˜\Jš
œ?˜?——Jšžœ˜	——Jšžœ Ÿ˜ —J˜—šŸœž	œx˜˜
Jšžœ
žœžœ˜'Jš
œ/™/J˜Jš
œ%™%Jšœ%žœ˜EJš
œ1˜1Jš
œ1˜1J™Jš
œ™šžœ"žœ˜*Jš
œA™Ašžœž˜JšœLžœ˜R—J™J™0šžœž˜JšœLžœ˜TJ˜——Jš
œ™šžœ"žœ˜*Jš
œA™Ašžœž˜JšœLžœ˜R—J™J™0šžœž˜JšœLžœ˜T——Jšžœž
œ Ÿ˜,J˜—šŸœž	œ6˜PJšžœžœ˜J˜Jš
œ=˜=Jš
œG˜GJš
œ?˜?Jš
œJ˜JJš
œ=˜=Jš
œG˜GJš
œ?˜?Jš
œJ˜JJ˜Jš
œY˜YJšžœžœž˜$Jšžœ!˜%J˜J˜—šŸœž	œ6˜MJšžœžœ˜J˜Jšœ,žœ$˜RJ˜—š
Ÿœž	œižœžœžœ˜€
J˜Jš
ž˜šžœ
žœžœ˜#Jš
œ?˜?Jš
œ@˜@Jš
œ?˜?Jš
œ@˜@Jš
œY˜YJšžœžœž˜$Jšžœ!˜%—Jšžœ Ÿ˜J˜—šŸœž	œ:˜TJšœSžœ
˜[Jšžœžœžœ˜*J˜Jš
œ&™&J˜š
œ7˜7Jšœžœžœžœ˜\Jšœ+žœ˜EJš
œ1˜1šžœžœ˜Jšžœžœžœ
 ˜;—šžœ˜šžœž˜Jš
œ ˜ —š
ž˜Jš
œ"˜"——J˜šžœž˜
Jš
œT˜T—J˜—Jš
œ1˜1Jšœ%žœžœžœ˜KJš
œW˜WJš
œ˜J˜—šŸœž	œŒ
˜₯
Jšžœ,žœ˜;Jš
œ?™?J˜š
œ-˜-šžœžœ
žœ˜Jš
œI˜IJšžœžœO˜\—J˜—Jšœžœžœ
˜Jš
œ#˜#Jš
œ ˜ Jšœ%žœ˜EJš
œ=˜=Jš
œ)˜)J˜Jš
œ ™ šžœž˜!š
œ˜Jšžœžœ
žœ˜&JšžœH˜LJš
œ˜šžœ"žœžœ	ž˜NJš
œJ˜JJš
œB˜BJšžœ ˜——J˜š
œ˜Jšžœžœ
žœ˜.JšžœI˜MJš
œ˜š	žœ"ž
œ
žœžœ	ž˜QJš
œJ˜JJš
œB˜BJšžœ ˜——šžœ
˜J˜——Jšžœžœ˜)šžœžœžœ
ž˜#šžœžœ
ž˜Jš
œ
˜
——Jšž
œ Πcn˜J˜—šŸœžœ
ž	œL˜jJšœ@žœ
˜HJšžœ,žœ˜;š
œ5™5Jš
œ*™*Jš
œS™S—J˜š
œ0˜0šžœžœ
ž˜Jš
œ8˜8šžœžœ
žœ
˜šžœž˜Jšœ,žœ?˜nšžœžœ
ž˜Jšžœžœžœ˜U—Jšœžœ˜———J˜—Jš
œ/˜/Jš
œ!˜!Jšœžœžœ
˜J˜šžœž˜!š
œ˜Jš
œ@˜@Jš
œ˜Jš
œ˜—š
œ˜Jš
œ?˜?Jš
œ˜Jš
œ˜—šžœ
˜J˜——Jš
œ4™4Jš
œ@˜@Jšž
œ ‘˜J˜J˜—šŸ
œž	œ!žœ"˜bJ˜šŸœž	œM˜mJšžœ)˜0Jš
œ4™4J˜Jšœ%žœ˜EJš
œD˜DJšžœžœ˜,J˜šžœ#žœ ž˜LJšœ: ˜X—Jš
œ˜˜Jš
œ™Jšœžœžœ
™Jšœ*žœ™<Jšœ*žœ™Kšžœž™Jš
œ]™]Jš
œA™A—šžœžœž™-Jš
œ]™]Jš
œA™A—šžœ
žœ
™Jš
œ:™:———J˜šŸ
œž	œl˜
Jšžœ
žœžœ˜'Jš
œ.™.J˜Jšœ%žœ˜EJš
œ-˜-Jš
œ0˜0š	žœdžœžœ
žœž˜
Jš
œ˜Jš
œ,˜,Jš
œK˜KJšžœ˜	——J˜šΟb	œ ˜)J™!šžœž˜šžœ2žœ
˜:Jšœžœ˜/——J˜—š’œ#˜/J˜Jš
œ4˜4šžœ
žœ
ž˜Jš
œ;˜;Jš
œ<˜<Jš
œ6˜6Jšžœ(˜/——J˜š’œ˜'J˜Jš
œ™Jš
œ7˜7š	žœžœžœžœž˜bJš
œ˜—šžœ
žœžœžœžœž˜kJš
œ"˜"——J˜š’œ˜'Jš
œ™š	žœžœžœžœž˜`Jš
œ˜—šžœ
žœžœžœžœž˜iJš
œ"˜"——J˜š’œ&˜5Jš
œ™Jš
œ#˜#šžœ1žœ
˜9Jšœžœ˜-—J˜—š’œ&˜7J™J™:šžœ2žœ
žœ
 ˜[Jš
œG˜G——J˜Jš
Ÿ
™
Jšœ%žœ˜EJš
œD˜DJšœ'žœ˜AJš
œF˜FJšœ,žœ˜4Jšœžœžœ˜AJšœžœ˜:Jšœžœ˜<Jšœžœ˜9J˜J˜Jš	œžœ
žœžœžœ
˜(Jš	œžœ
žœžœžœ
˜)Jš
œ6˜6Jšœ/žœ"˜TJšœ/žœ"˜TJšœ&žœ ˜IJ™J™™6Jš
œ)™)—šžœžœ˜$Jš
œ=˜=Jš
œ˜—J˜Jš
œo˜ošžœžœ˜$Jš
œE˜EJš
œ˜—šžœ
žœž˜)Jš
œl˜lJ˜—Jš
œ(˜(J˜šœ0žœ˜BJš
œ0˜0J˜—Jšœ	žœ”
žœ$˜Ι
Jšž
œ Ÿ
˜J˜—šŸ
œž	œ;˜PJšžœ.žœ U˜•
J˜Jšœ%žœ˜EJš
œK˜KJš
œM˜MJš
œ7˜7J˜Jšžœ.žœ*žœ˜uJ˜—šŸœž	œPžœ)˜–
J˜Jš
œ™Jšœ%žœ˜EJš
œD˜DJš
œ/˜/šžœ$ž
œ
žœž˜UJš
œS˜SJš
œR˜RJšžœ
˜—JšžœžœI˜ZJ˜šžœ$žœž˜JJš
œ2˜2Jš
œ8˜8Jš
œO˜OJšžœ
˜—šžœžœ˜"Jš
œ>˜>Jšœ*žœ˜/—Jš
œ˜J˜—šŸœž	œPžœ)˜—
J˜Jš
œ™Jšœ%žœ˜EJš
œD˜DJš
œ.˜.šžœž˜ Jš
œL˜Lšžœ$ž
œ
žœž˜UJš
œ3˜3Jš
œ9˜9Jš
œ5˜5Jš
œO˜OJšžœ
˜—Jšœ*žœ˜/—Jš
œ˜J˜—šŸœž	œΒ
˜Ϋ
J˜Jšœ%žœ˜EJš
œD˜DJšœ'žœ˜AJš
œ[˜[Jšœžœ˜2Jšœžœ˜:Jš
œ˜Jš
œ˜Jš
œ˜J˜—Jšžœ
˜—J˜J˜—…—}¦§8