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

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

ActiveTrackSpec: TYPE = REF ActiveTrackSpecRec;
ActiveTrackSpecRec: TYPE = RECORD[
track: 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];

SegProc: TYPE = PROC[seg: RouteChannel.Segment, activeTrackSpec: ActiveTrackSpec]
RETURNS [quit: BOOLEAN _ FALSE,
segment: RouteChannel.Segment,
segLayer: RoutePrivate.RoutingLayerOrNone];

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.PutRope[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;
chanTracks.tracks[trackIndex].maxFeatureOnTrack _ 0};

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 {
segment _ seg; segLayer _ CanConvert[routingArea, seg];
segSpec.seg _ segment; segSpec.segLayer _ segLayer;
quit _ FitSegment[routingArea, segSpec, activeTrackSpec, FALSE]};
};
chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
segSpec: ActiveSegSpec _ NEW[ActiveSegSpecRec];

FOR activeTrackSpec: ActiveTrackSpec _ NextTrack[routingArea, NIL, method], NextTrack[routingArea, activeTrackSpec, method] WHILE activeTrackSpec # NIL DO
FOR activeSegSpec: 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 {
segment _ seg; segLayer _ CanConvert[routingArea, seg];
segSpec.seg _ seg; segSpec.segLayer _ segLayer;
quit _ FitSegment[routingArea, segSpec, activeTrackSpec, TRUE]};
};

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

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
segSpec: ActiveSegSpec _ NEW[ActiveSegSpecRec];

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

PlaceSegment[routingArea, activeSegSpec, activeTrackSpec]; segOnThisTrack _ TRUE;
nextSegSpec _ FollowingSeg[routingArea, activeSegSpec, activeTrackSpec];
WHILE nextSegSpec # NIL AND stillGoing DO
nextSegSpec.segLayer _ CanConvert[routingArea, nextSegSpec.seg];
IF FitSegment[routingArea, nextSegSpec, activeTrackSpec, TRUE] THEN
{PlaceSegment[routingArea, nextSegSpec, activeTrackSpec];
nextSegSpec _ FollowingSeg[routingArea, nextSegSpec, activeTrackSpec]}
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: ActiveTrackSpec, method: RouteChannel.Method]
RETURNS [nextTrackSpec: 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[ActiveTrackSpecRec _ [trialTrack, going, freeArea]];
IF debug THEN
{TerminalIO.PutRope[Rope.Cat["\n   New track: ", Convert.RopeFromInt[trialTrack]]];
TerminalIO.PutRope[Rope.Cat["\n   going: ", RouteChannel.GoingName[going], ", free area: ", RouteChannel.AboveOrBelowName[freeArea]]]}};
}; -- NextTrack

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

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks;
track: RouteChannel.ZMaxTracks _ activeTrackSpec.track;
trackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, 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];
featureSize: Route.Number _ MAX[routingArea.rules.contactSize, activeSegSpec.seg.qWidth];
distance: Route.Number _ (featureSize + routingArea.rules.trunkSpacing + routingArea.rules.trunkToTrunk)/2;

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
IF ABS[trackLoc - RouteChannel.TrackLoc[routingArea, keepTrack]] < distance THEN 
chanTracks.tracks[keepTrack].keep _ TRUE
ENDLOOP;

chanTracks.tracks[track].maxFeatureOnTrack _ MAX[chanTracks.tracks[track].maxFeatureOnTrack, featureSize];

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: ActiveSegSpec, activeTrackSpec: 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: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec]
RETURNS [fitsSoFar: BOOLEAN _ TRUE] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
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 {
SELECT TRUE FROM
segLayer = trunk AND existingSeg.routingLayer = trunk =>
fitsSoFar _ ~OverlapCheck[routingArea, existingSeg, trialSeg, rules.branchSpacing];
segLayer = trunk AND existingSeg.routingLayer = branch =>
fitsSoFar _ ~EndOverlapCheck[routingArea, existingSeg, trialSeg, rules.branchSpacing];
segLayer = branch AND existingSeg.routingLayer = trunk =>
fitsSoFar _ ~EndOverlapCheck[routingArea, trialSeg, existingSeg, rules.branchSpacing];
segLayer = branch AND existingSeg.routingLayer = branch =>
fitsSoFar _ ~OverlapCheck[routingArea, existingSeg, trialSeg, rules.branchSpacing];
ENDCASE};
ENDLOOP}; -- FitSegmentThisTrack

FitSegmentAdjTracks: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: ActiveSegSpec, activeTrackSpec: 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;
trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track;
trialPos: Route.Number _ RouteChannel.TrackLoc[routingArea, trackNum];
maxPos: Route.Number _ RouteChannel.TrackLoc[routingArea, maxTrack] + rules.trunkToEdge - rules.trunkSpacing;
minPos: Route.Number _ RouteChannel.TrackLoc[routingArea, 1] - rules.trunkToEdge + rules.trunkSpacing;
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
influence: Route.Number _ RouteChannel.InfluenceTracks[routingArea, parms.widestTrunk/2] + RouteChannel.InfluenceTracks[routingArea, trialSeg.net.trunkWidth/2];
lowerTrack: RouteChannel.MaxTracks _ MAX[trackNum - influence, 1];
upperTrack: RouteChannel.MaxTracks _ MIN[trackNum + influence, chanTracks.count];
IF maxPos < trialPos + trialSeg.qWidth/2 OR trialPos - trialSeg.qWidth/2 < minPos THEN
fitsSoFar _ FALSE;

FOR adjTrack: RouteChannel.MaxTracks IN [lowerTrack .. upperTrack] WHILE fitsSoFar DO
IF adjTrack # activeTrackSpec.track THEN {
adjTrackPos: Route.Number _ RouteChannel.TrackLoc[routingArea, adjTrack];
distance: Route.Number _ ABS[adjTrackPos - trialPos] - chanTracks.tracks[adjTrack].maxFeatureOnTrack/2 - trialSeg.net.trunkWidth/2;
pinsOnTrialSeg: RouteChannel.ChanPinList;
IF distance < rules.trunkSpacing THEN {
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
contactToContact: Route.Number _ rules.contactToContact;
segLayer: RoutePrivate.RoutingLayerOrNone _ nextSegSpec.segLayer;
IF existingSeg.net.netNum # trialSeg.net.netNum OR
existingSeg.net.netPart # trialSeg.net.netPart THEN
{ -- check to see if wires interfere with each other
IF ABS[trialPos - adjTrackPos] < trialSeg.qWidth/2 + rules.trunkSpacing + existingSeg.qWidth/2 THEN
fitsSoFar _ ~OverlapCheck[routingArea, existingSeg, trialSeg, rules.branchSpacing]};

IF contactToContact > rules.trunkToTrunk THEN {
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[routingArea, trialPin, trialPos, existPin, adjTrackPos, rules.branchSpacing];
ENDLOOP;
ENDLOOP}};

ENDLOOP}};
ENDLOOP}; -- FitSegmentAdjTracks

FitSegmentConstraints: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: ActiveSegSpec, activeTrackSpec: 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[routingArea: Route.RoutingArea, branchSeg, trunkSeg: RouteChannel.Segment, dist: Route.Number]
RETURNS [overlap: BOOLEAN] = {

EachPin: RouteChannel.EachPinActionProc ~ {
leftTrunkPinLoc: Route.Number _ pin.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, pin.pWidth]/2;
rightTrunkPinLoc: Route.Number _ pin.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, pin.pWidth]/2;
gap: RoutePrivate.Range _ RouteChannel.Gap[[leftBranchLoc, rightBranchLoc], [leftTrunkPinLoc, rightTrunkPinLoc]];
IF gap.l > gap.r THEN overlap _ TRUE
ELSE overlap _ gap.r - gap.l < dist
};

leftBranchPin: RouteChannel.ChanPin _ branchSeg.exteriorPins[chanLeft];
leftBranchLoc: Route.Number _ leftBranchPin.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, leftBranchPin.pWidth]/2;
rightBranchPin: RouteChannel.ChanPin _ branchSeg.exteriorPins[chanRight];
rightBranchLoc: Route.Number _ rightBranchPin.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, rightBranchPin.pWidth]/2;

overlap _ RouteChannel.EnumPinsOnSeg[routingArea, trunkSeg, EachPin]};

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

leftPin1: RouteChannel.ChanPin _ seg1.exteriorPins[chanLeft];
left1Loc: Route.Number _ leftPin1.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, leftPin1.pWidth]/2;
rightPin1: RouteChannel.ChanPin _ seg1.exteriorPins[chanRight];
right1Loc: Route.Number _ rightPin1.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, rightPin1.pWidth]/2;
leftPin2: RouteChannel.ChanPin _ seg2.exteriorPins[chanLeft];
left2Loc: Route.Number _ leftPin2.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, leftPin2.pWidth]/2;
rightPin2: RouteChannel.ChanPin _ seg2.exteriorPins[chanRight];
right2Loc: Route.Number _ rightPin2.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, 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[routingArea: Route.RoutingArea, seg1, seg2: RouteChannel.Segment, dist: Route.Number]
RETURNS [overlap: BOOLEAN] = {

overlap _ HalfOverlapCheck[routingArea, seg1, seg2, dist] OR HalfOverlapCheck[routingArea, seg2, seg1, dist]};

ContactCheck: PROCEDURE[routingArea: Route.RoutingArea, 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 - RouteUtil.GetWidthWithContact[routingArea, pin1.pWidth]/2;
right1Loc: Route.Number _ pin1.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, pin1.pWidth]/2;
left2Loc: Route.Number _ pin2.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, pin2.pWidth]/2;
right2Loc: Route.Number _ pin2.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, 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: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec, segProc: SegProc]
RETURNS [nextSegSpec: ActiveSegSpec _ NIL] = {

CheckSegs: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN {
[quit, seg, segLayer] _ segProc[pin.conctSeg[whichSide], activeTrackSpec];
IF ~quit THEN [quit, seg, segLayer] _ 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;
seg: RouteChannel.Segment;
segLayer: RoutePrivate.RoutingLayerOrNone;

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 [1 .. pinPos] WHILE ~ found DO
pinPosition: RouteChannel.PinPosition _ chanData.chanPins.sides[posIndex];
found _ RouteChannel.EnumPins[routingArea, pinPosition, CheckSegs]
ENDLOOP}; -- posIndex
ENDCASE;

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

FollowingSeg: PROCEDURE [routingArea: Route.RoutingArea, activeSegSpec: ActiveSegSpec,
activeTrackSpec: ActiveTrackSpec]
RETURNS [nextSegSpec: 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: ActiveSegSpec _ NEW[ActiveSegSpecRec _ [seg: pin.conctSeg[newSide]]];
IF trialSegSpec.seg # NIL THEN
IF 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};

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 _ CDSymbolicObjects.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: ActiveTrackSpec _ NEW[ActiveTrackSpecRec];
upperTrackSpec: ActiveTrackSpec _ NEW[ActiveTrackSpecRec];
segSpec: ActiveSegSpec _ NEW[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.ChanPin _ seg.exteriorPins[chanLeft];
rightPin: RouteChannel.ChanPin _ seg.exteriorPins[chanRight];
leftPinPosition: RouteChannel.PinPosition _ leftPin.pinPosition;
rightPinPosition: RouteChannel.PinPosition _ rightPin.pinPosition;
segLength: Route.Number _ rightPinPosition.pLoc - leftPinPosition.pLoc;
IF leftPin.kindOfPin = exitPin OR rightPin.kindOfPin = exitPin THEN RETURN;

IF segLength <= chanData.chanParms.maxToConvert AND ABS[leftPinPosition.pinIndex - rightPinPosition.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};

END.



NRouteChannelTopolImpl.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   December 18, 1986 2:28:22 pm PST
active routing track specification
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
do the checks only if the tracks can interfere
check to see if contacts 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
reuse activeSegSpec to reduce allocations
return the following segment in the current direction
tracknum must be 0
check the next seg basie on existingSide and newSide
check for design rule violations if track is removed
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
ΚΫ˜š
œ@™@Icode™-—˜Jšœ
Οm
œ1™<Jš
œ.™.Jš
œ=™=—J˜š
Οk	˜	Jšœžœk˜uJ˜—šΟnœžœ
ž˜$Jšžœ
žœj˜tJšžœ
˜Jšžœ˜Jš
ž˜J˜Jš
œ"™"Jšœžœžœ˜/šœžœžœ
˜"Jš
œ#˜#Jš
œ1˜1Jš
œ-˜-J˜—Jšœžœžœ˜+šœžœžœ
˜ Jšœžœ
˜ Jš
œ3˜3J˜—šœ	žœžœ=˜Qšžœžœžœ
˜Jš
œ˜Jš
œ+˜+—J˜—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š
œ)™)šŸœ&˜1Jš
œ4˜4Jšœ)žœ
˜-Jšœ%žœ
˜+Jš
œ5˜5J˜—šŸ	œ$˜-šžœžœ
ž˜šœ
žœ
Ÿœžœž˜BJš
œ1˜1šžœžœ
ž˜Jšœ!žœ
˜%—Jšžœ˜
——J˜—Jšœ%žœ˜EJš
œ>˜>Jš
œD˜DJš
œ'˜'Jš
œ7˜7J˜Jš
œ'™'šžœ"žœž˜@Jš
œ<˜<Jš
œ:˜:Jšžœ ˜—J˜—šŸ
œž	œA˜YJ™,J˜šŸ
œ
˜šžœžœ
ž˜šžœžœžœ
žœ˜FJš
œ7˜7Jš
œ3˜3Jšœ9žœ˜A——Jš
œ˜—Jšœ%žœ˜EJšœ'žœ˜AJšœžœ˜/J˜Jš
œ™š	žœ;žœ;žœžœ
ž˜š
J™Jš
œ™š	žœ<žœhžœžœ
ž˜Ζ
Jš
œ.™.J˜Jš
œ:˜:Jšžœ ˜—J˜Jšžœ ˜"—Jšœ ˜J˜—šŸœž	œA˜^Jš
œ-™-J˜šŸœ
˜šžœžœ
ž˜šžœžœ
žœ˜*Jš
œ7˜7Jš
œ/˜/Jšœ9žœ˜@——Jš
œ˜—J˜Jšœ
žœžœ
˜Jšœžœ˜J˜Jšœ%žœ˜EJšœ'žœ˜AJšœžœ˜/J˜Jš
œ™šžœ;žœ;žœ
žœžœ
ž˜§
Jšœžœžœ
˜ J™Jš
œ™š	žœ<žœjžœžœ
ž˜Θ
Jš
œ.™.Jšœžœžœ
˜Jš
œ˜J˜JšœLžœ
˜QJš
œH˜Hšžœžœ
žœž˜)Jš
œ@˜@šžœ7žœž˜CJš
œ9˜9Jš
œF˜F—š
ž˜Jšœ
žœ
˜—Jšžœ ˜—Jšžœ ˜—J˜Jš
œ™Jšžœžœ"žœ
˜=šžœ˜Jš
œ%˜%šžœžœ7ž˜\Jšœžœ˜——Jšžœ ˜—Jšœ ˜J˜—šŸ	œž	œ_˜sJšžœ%˜,Jš
œ%™%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šœžœ5˜Išžœž˜
Jš
œS˜SJš
œˆ
˜ˆ
——Jšœ ˜J˜—Jš
œ ™ šŸœž	œd˜{J˜Jšœ%žœ˜EJš
œD˜DJš
œ7˜7Jš
œC˜CJš
œp˜pJšœ&žœ˜?Jšœ&žœ%˜NJš
œK˜KJšœžœ:˜YJš
œk˜kJ˜Jš
œ™Jšžœ žœ3˜YJšžœ$˜(J˜Jš
œ8˜8šžœ$žœž˜Gšžœ
žœFžœ
˜QKšœ$ž˜(—Kšžœ
˜K˜—Kšœ-žœ:˜jJ˜Jš
œ™šžœžœ
žœ˜Jš
œ™Jšœžœ
˜ Jš
œ6˜6J˜—šžœ
žœpžœ˜}Jš
œ&™&Jš
œ%˜%Jš
œ6˜6J˜—šžœ˜Jš
œ˜Jš
œ)˜)šžœ,žœžœ
ž˜EJ˜šžœož˜uJšžœ
˜—Jš
œ˜Jšžœ
˜—Jš
œ$˜$Jšœ' ˜6—J™—šŸ
œž	œožœ
˜Œ
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˜—šŸœž	œ^˜|Jšžœ
žœžœ˜'Jš
œ(™(J˜Jšœ%žœ˜EJš
œ-˜-Jš
œ1˜1Jš
œ9˜9Jš
œA˜AJ˜Jš
œ™šžœf˜iJšžœžœ
žœž˜(J˜šžœ.ž˜2Jšœ/žœ˜5šžœ
žœ
ž˜šœžœ$˜8Jš
œS˜S—šœžœ%˜9Jš
œV˜V—šœžœ$˜9Jš
œV˜V—šœžœ%˜:Jš
œS˜S—Jšžœ˜	——Jšžœ ˜ —J˜—šŸœž	œ
˜Ÿ
Jšžœ
žœžœ˜'Jš
œ1™1J˜Jšœ%žœ˜EJš
œD˜DJšœžœžœ
˜Jš
œ-˜-Jš
œ1˜1Jš
œ9˜9Jš
œF˜FJš
œm˜mJš
œf˜fJšœ'žœ˜AJš
œ 
˜ 
Jšœ%žœ˜BJšœ%žœ)˜QJ™Jš
œ*™*šžœ'žœ'ž˜VJšœžœ
˜—J˜Jš
œ)™)šžœ"žœžœž˜Ušžœ"žœ˜*Jš
œI˜IKšœžœg˜ƒ
Jš
œ)˜)šžœžœ˜'Jš
œ.™.šžœžœ (˜<Jšœžœ˜Jš
œ7˜7—šžœf˜iJšžœžœ
žœž˜(Jš
œ8˜8Jš
œA˜Ašžœ.ž˜2Jšœ/ž˜3Jšœ 2˜4šžœ
žœYž˜cJš
œT˜T—J˜Jš
œ2™2šžœ'žœ˜/šžœžœ"žœ˜?Jš
œR˜Rš	žœFžœ
žœ
žœž˜oJš
œ1˜1š	žœFžœ
žœ
žœž˜oJš
œ1˜1Jš
œg˜gJšžœ
˜—Jšžœ˜
J˜————Jšžœ˜
———Jšžœ ˜ —J˜—šŸœž	œ^˜~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˜—šŸœž	œ_˜yJšžœžœ˜J˜šŸœ$˜+Jš
œp˜pJš
œq˜qJš
œq˜qJšžœžœž˜$Jšžœ˜#Jš
œ˜J˜—Jš
œG˜GJš
œ‚
˜‚
Jš
œI˜IJš
œ…
˜…
J˜Jš
œF˜FJ˜—šŸœž	œV˜qJšžœžœ˜J˜Jš
œ=˜=Jš
œs˜sJš
œ?˜?Jš
œv˜vJš
œ=˜=Jš
œs˜sJš
œ?˜?Jš
œv˜vJ˜Jš
œY˜YJšžœžœž˜$Jšžœ!˜%J˜J˜—šŸœž	œV˜mJšžœžœ˜J˜Jšœ:žœ2˜nJ˜—š
Ÿœž	œ‰
žœžœžœ˜Δ
J˜Jš
ž˜šžœ
žœžœ˜#Jš
œk˜kJš
œl˜lJš
œk˜kJš
œl˜lJš
œY˜YJšžœžœž˜$Jšžœ!˜%—Jšžœ ˜J˜—šŸœž	œ:˜TJšœSžœ
˜[Jšžœžœžœ˜*J˜Jš
œ&™&J˜šŸœ'˜7Jšœžœžœžœ˜\Jšœ+žœ˜EJš
œ1˜1šžœžœ˜Jšžœžœžœ ˜;—šžœ˜šžœž˜Jš
œ ˜ —š
ž˜Jš
œ"˜"——J˜šžœž˜
Jš
œT˜T—J˜—Jš
œ1˜1Jšœ%žœžœžœ˜KJš
œW˜WJš
œ˜J˜—šŸœž	œr˜‹
Jšžœžœ˜.Jš
œ?™?J˜šŸ	œ$˜-šžœžœ
žœ˜Jš
œJ˜JJšžœžœP˜]—J˜—Jšœžœžœ
˜Jš
œ#˜#Jš
œ ˜ Jšœ%žœ˜EJš
œ=˜=Jš
œ˜Jš
œ*˜*J˜Jš
œ ™ šžœž˜!š
œ˜Jšžœžœ
žœ˜&JšžœH˜LJš
œ˜šžœ"žœžœ	ž˜NJš
œJ˜JJš
œB˜BJšžœ ˜——J˜š
œ˜Jšžœžœ
žœ˜.JšžœI˜MJš
œ˜š	žœ"ž
œ
žœžœ	ž˜QJš
œJ˜JJš
œB˜BJšžœ ˜——šžœ
˜J˜——šžœžœ˜Kš
œ)™)Kšœžœžœ
žœ
žœžœ˜SKš
œ8˜8—šžœžœžœ
ž˜#šžœžœ
ž˜Jš
œ
˜
——Jšœ ˜J˜—šŸœž	œ?˜VJš
œ!˜!Jšžœžœ˜.š
œ5™5Jš
œ™—J˜šŸœ$˜0šžœžœ
ž˜Jš
œ8˜8šžœžœ
žœ
˜šžœž˜Jšœžœ2˜Tšžœžœ
ž˜Jšžœžœ˜A—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˜šΠbn	œ ˜)J™!šžœž˜šžœ3žœ
˜:Jšœžœ˜/——J˜—š‘œ#˜/J˜Jš
œ4˜4šžœ
žœ
ž˜Jš
œ;˜;Jš
œ<˜<Jš
œ6˜6Jšžœ(˜/——J˜š‘œ˜'J˜Jš
œ™Jš
œ<˜<š	žœžœžœžœž˜bJš
œ˜—šžœ
žœžœžœžœž˜kJš
œ"˜"——J˜š‘œ˜'Jš
œ™š	žœžœžœžœž˜`Jš
œ˜—šžœ
žœžœžœžœž˜iJš
œ"˜"——J˜š‘œ&˜5Jš
œ™Jš
œ#˜#šžœ2žœ
˜9Jšœžœ˜-—J˜—š‘œ&˜7J™J™:šžœ2žœ
žœ
 ˜ZJš
œG˜G——J˜Jš
Ÿ
™
Jšœ%žœ˜EJš
œD˜DJšœ'žœ˜AJš
œF˜FJšœ,žœ˜4Jšœžœžœ˜AJšœžœ˜:Jšœžœ˜<Jšœžœ˜9J˜J˜Jš	œžœ
žœžœžœ
˜(Jš	œžœ
žœžœžœ
˜)Jš
œ6˜6Jšœ"žœ˜:Jšœ"žœ˜:Jšœžœ˜/J™J™™6Jš
œ)™)—šžœžœ˜$Jš
œ=˜=Jš
œ˜—J˜Jš
œo˜ošžœžœ˜$Jš
œE˜EJš
œ˜—šžœ
žœž˜)Jš
œl˜lJ˜—Jš
œ(˜(J˜šœ0žœ˜BJš
œ0˜0J˜—Jšœ	žœ”
žœ$˜Ι
Jšœ ˜J˜—šŸ
œž	œ;˜PJšžœ9 U˜•
J˜Jšœ%žœ˜EJš
œ;˜;Jš
œ=˜=Jš
œ@˜@Jš
œB˜BJš
œG˜GJšžœžœžœ
žœ
˜KJ˜Jšžœ.žœ
žœ<žœ˜‹
J˜—šŸœž	œ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˜—Jšžœ
˜—J˜J˜—…—₯1