DIRECTORY
CD, CDBasics, HashTable, List, PWObjects, Rope, Route, RouteChannel, RoutePrivate, RouteTechnology, RouteUtil;

RouteImpl: CEDAR PROGRAM 
IMPORTS CD, CDBasics, HashTable, PWObjects, Route, RouteChannel, RouteTechnology, RouteUtil
EXPORTS Route, RoutePrivate
SHARES Route = {


RoutingLayerName: PUBLIC ARRAY RoutePrivate.RoutingLayerOrNone OF Rope.ROPE _ ["trunk", "branch", "none"];

Error: PUBLIC ERROR[errorType: Route.ErrorType _ callingError, explanation: Rope.ROPE _ NIL] = CODE;

Signal: PUBLIC SIGNAL[errorType: Route.ErrorType _ callingError, explanation: Rope.ROPE _ NIL] = CODE;

trunkWidthKey: PUBLIC REF ATOM _ NEW[ATOM _ $trunkWidth];
branchWidthKey: PUBLIC REF ATOM _ NEW[ATOM _ $branchWidth];


CreateDesignRules: PUBLIC PROC [technologyKey: ATOM, horizLayer, vertLayer: Route.Layer, trunkDirection: Route.Direction, properties: Route.PropList _ NIL] RETURNS [dr: Route.DesignRules] = {

IF technologyKey # NIL THEN
{technology: CD.Technology _ CD.FetchTechnology[technologyKey];
dr _ NEW[Route.DesignRulesRec];
dr.CDLambda _ technology.lambda;
dr.technology _ technology;
dr.horizLayer _ horizLayer;  dr.vertLayer _ vertLayer;
SELECT trunkDirection FROM
horizontal =>
{dr.branchDirection _ vertical; dr.trunkDirection _ horizontal;
RouteTechnology.CmosDesignRules[dr, horizLayer, vertLayer]};
vertical =>
{dr.branchDirection _ horizontal; dr.trunkDirection _ vertical;
RouteTechnology.CmosDesignRules[dr, vertLayer, horizLayer]};
ENDCASE}

ELSE -- invalid technology
Error[callingError, "Invalid technology."]};

CreateRoutingBarrier: PUBLIC PROC [layer: Route.Layer, barrier: Route.RectList _ NIL, properties: Route.PropList _ NIL] RETURNS [routingBarrier: Route.RoutingBarrier] = {
routingBarrier _ NEW[Route.RoutingBarrierRec];
routingBarrier.layer _ layer;
routingBarrier.barrier _ barrier;
routingBarrier.properties _ properties};

IncludeRoutingAreaSide: PUBLIC PROC [routingArea: Route.RoutingArea, side: Route.Side, sideFiducial: Route.Position, barriers: Route.RoutingBarrierList _ NIL, properties: Route.PropList _ NIL] = {

routingSides: RoutePrivate.RoutingAreaSides _ NARROW[routingArea.routingSides];
IF routingSides[side] # NIL THEN
Route.Error[callingError, "Multiple side descriptions."]
ELSE
{routingAreaSide: RoutePrivate.RoutingAreaSide _ NEW[RoutePrivate.RoutingAreaSideRec];
routingAreaSide.side _ side;
routingAreaSide.sideFiducial _ sideFiducial;
routingAreaSide.properties _ properties;
routingAreaSide.barrierList _ barriers;
routingSides[side] _ routingAreaSide}};

CreateRoutingArea: PUBLIC PROC [routingAreaName: Rope.ROPE _ NIL, designRules: Route.DesignRules, properties: Route.PropList _ NIL] RETURNS [routingArea: Route.RoutingArea] = {

IF designRules = NIL THEN
Route.Error[callingError, "No design rules."]
ELSE {
routingSides: RoutePrivate.RoutingAreaSides _ NEW[RoutePrivate.RoutingAreaSidesRec _ [NIL, NIL, NIL, NIL]];
routingArea _ NEW[Route.RoutingAreaRec];
routingArea.name _ routingAreaName;
routingArea.rules _ designRules;
routingArea.properties _ properties;
routingArea.routingSides _ routingSides;
routingArea.parms _ NARROW[NEW[RoutePrivate.RoutingAreaParmsRec], RoutePrivate.RoutingAreaParms];

routingArea.nets _ NARROW[NEW[RoutePrivate.NetTabRec _ [size: RoutePrivate.maxNets, count: 0, n: ALL[NIL]]], RoutePrivate.NetTab]}};

CreatePin: PUBLIC PROC [cdPin: CD.Instance, side: Route.Side] RETURNS [pin: Route.Pin] = {
pin _ NEW[Route.PinRec _ [cdPin, side]]};

IncludeNet: PUBLIC PROC [routingArea: Route.RoutingArea, netName: Rope.ROPE, connections: Route.PinList, properties: Route.PropList _ NIL] = {

parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
netTab: RoutePrivate.NetTab _ NARROW[routingArea.nets, RoutePrivate.NetTab];
netPart: NAT _ 1;
nextNetNum: NAT _ netTab.count + 1;

FOR netIndex: RoutePrivate.ZMaxNets IN [1 .. netTab.count] DO
IF netTab.n[netIndex].name = netName THEN netPart _ netPart + 1;
ENDLOOP;

IF nextNetNum > netTab.size THEN
Route.Error[noResource, "Too many nets."]
ELSE {
channelDirection: Route.Direction _ routingArea.rules.trunkDirection;
trunkWidth, trunkWidthSpec, branchWidth, branchWidthSpec, widestBranchPin, widestTrunkPin: Route.Number;

[widestBranchPin, widestTrunkPin] _ RouteUtil.GetPinWidth[routingArea, connections, channelDirection];
trunkWidthSpec _ RouteUtil.GetNumberProp[properties, Route.trunkWidthKey, routingArea.rules.trunkWidth];
trunkWidth _ IF trunkWidthSpec > routingArea.rules.trunkWidth THEN
trunkWidthSpec
ELSE IF widestTrunkPin > 0 THEN MAX[routingArea.rules.trunkWidth, widestTrunkPin]
ELSE MAX[routingArea.rules.trunkWidth, widestBranchPin];

branchWidthSpec _ RouteUtil.GetNumberProp[properties, Route.branchWidthKey, routingArea.rules.branchWidth];
branchWidth _ IF branchWidthSpec > routingArea.rules.branchWidth THEN
branchWidthSpec
ELSE MAX[routingArea.rules.branchWidth, widestBranchPin, trunkWidth];

parms.widestTrunk _ MAX[trunkWidth, parms.widestTrunk];
parms.widestBranch _ MAX[branchWidth, parms.widestBranch];
parms.numTracksToUse _ parms.numTracksToUse + 2*RouteChannel.InfluenceTracks[routingArea, trunkWidth];
netTab.n[nextNetNum] _ NEW[RoutePrivate.NetRec _ [name: netName, netNum: nextNetNum, netPart: netPart, branchWidth: branchWidth, trunkWidth: trunkWidth, pinList: connections, properties: properties]];
netTab.count _ nextNetNum}};

ChannelRoute: PUBLIC PROC [routingArea: Route.RoutingArea, sideOrgins: Route.PositionVec, routingRect: Route.Rect, opt: Route.Optimization _ full, signalSinglePinNets, signalCoincidentPins: BOOLEAN _ TRUE] RETURNS [routingResult: Route.RoutingResult] = {

RouteChannel.InitChannel[routingArea, sideOrgins, routingRect, channel, signalSinglePinNets, signalCoincidentPins, FALSE, FALSE];
IF RouteChannel.GenerateConstraints[routingArea, channel] THEN
routingResult _ RouteChannel.TopoWiring[routingArea, opt]
ELSE
routingResult _ NEW[Route.RoutingResultRec _ [routingArea: routingArea, routingRect: EmptyRect[routingArea, routingRect]]]};

SwitchBoxRoute: PUBLIC PROC [routingArea: Route.RoutingArea, sideOrgins: Route.PositionVec, routingRect: Route.Rect, opt: Route.Optimization _ full, signalSinglePinNets, signalCoincidentPins: BOOLEAN _ TRUE, okToDiddleLLPins, okToDiddleURPins: BOOLEAN _ FALSE] RETURNS [routingResult: Route.RoutingResult] = {

RouteChannel.InitChannel[routingArea, sideOrgins, routingRect, switchBox, signalSinglePinNets, signalCoincidentPins, okToDiddleLLPins, okToDiddleURPins];
IF RouteChannel.GenerateConstraints[routingArea, switchBox] THEN
routingResult _ RouteChannel.TopoWiring[routingArea, opt]
ELSE
routingResult _ NEW[Route.RoutingResultRec _ [routingArea: routingArea, routingRect: routingRect]]};

MazeRoute: PUBLIC PROC [routingArea: Route.RoutingArea, sideCoords: Route.PositionVec, routingRect: Route.Rect, opt: Route.Optimization _ full] RETURNS [routingResult: Route.RoutingResult] = {

};

RetrieveRouting: PUBLIC PROC [routingResult: Route.RoutingResult, cellName: Rope.ROPE _ NIL, retrieveRect: Route.RefRect _ NIL, properties: Route.PropList _ NIL, viaTable: HashTable.Table _ NIL] RETURNS [object: Route.Object, externalConnections: Route.PinList] = {

parms: RoutePrivate.RoutingAreaParms _ NARROW[routingResult.routingArea.parms];
parms.viaTable _ IF viaTable # NIL THEN viaTable ELSE HashTable.Create[equal: EqualProc, hash: HashProc];
parms.entityTable _ HashTable.Create[equal: HashTable.RopeEqual, hash: HashTable.HashRope];

SELECT parms.routerUsed FROM
channel, switchBox => {
rect: Route.Rect _ IF retrieveRect = NIL THEN routingResult.routingRect
ELSE CDBasics.Surround[retrieveRect^, routingResult.routingRect];

externalConnections _ RouteChannel.GetRouting[routingResult.routingArea, rect, properties, RouteChannel.RetrieveSegments, RouteChannel.RetrievePins, RouteChannel.RetrieveVias, RouteChannel.RetrieveExits, RouteChannel.RetrieveIncompletes];

object _ PWObjects.CreateRouting[rect, CreateNodes[parms.entityTable]]};

maze => NULL;
ENDCASE};

Destroy: PUBLIC PROC [routingArea: Route.RoutingArea] ~ {
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
SELECT parms.routerUsed FROM
channel, switchBox => RouteChannel.Destroy[routingArea];
maze => NULL;
ENDCASE};

EqualProc: PROC [k1, k2: HashTable.Key] RETURNS [eq: BOOL] = {
p1: Route.Position _ NARROW[k1, REF Route.Position]^;
p2: Route.Position _ NARROW[k2, REF Route.Position]^;
eq _ p1.x = p2.x AND p1.y = p2.y};

HashProc: PROC [k: HashTable.Key] RETURNS [hash: CARDINAL] = {
size: Route.Position _ NARROW[k, REF Route.Position]^;
hash _ size.x + size.y};

PlOs: TYPE = REF PlORec;
PlORec: TYPE = RECORD[
list: LIST OF REF PWObjects.PlacedObject _ NIL];

CreateNodes: PROC [table: HashTable.Table] RETURNS [nodes: LIST OF PWObjects.Node _ NIL] = {
EachPair: HashTable.EachPairAction = {
name: Rope.ROPE = NARROW [key];
geometry: PlOs = NARROW [value];
node: PWObjects.Node = CreateNode[geometry.list, LIST [[key: $InstanceName, val: name], [key: $SignalName, val: name]]];
nodes _ CONS [node, nodes];
};
[] _ HashTable.Pairs[table, EachPair]};

CreateNode: PROC [geometry: LIST OF REF PWObjects.PlacedObject, properties: CD.PropList _ NIL] RETURNS [node: PWObjects.Node] = {
size: NAT _ 0;
FOR list: LIST OF REF PWObjects.PlacedObject _ geometry, list.rest WHILE list#NIL DO size _ size + 1 ENDLOOP;
node _ NEW [PWObjects.NodeRep[size]];
node.properties _ properties;
FOR i: NAT IN [0 .. size) DO node[i] _ geometry.first^; geometry _ geometry.rest ENDLOOP};

EmptyRect: PROC [routingArea: Route.RoutingArea, routingRect: Route.Rect] RETURNS [empty: Route.Rect] ~ {

nRect: Route.Rect _ CDBasics.ReInterpreteRect[routingRect];
upPos: RoutePrivate.PQPosition _ RouteUtil.XYToPQ[routingArea, [nRect.x2, nRect.y2]];
upXy: Route.Position _ RouteUtil.PQToXY[routingArea, [upPos.p, nRect.y1 + routingArea.rules.pinSpacing]];
empty _ [nRect.x1, nRect.y1, upXy.x, upXy.y]};
}. 




ªRouteImpl.mesa
Copyright c 1985, 1987 by Xerox Corporation.  All rights reserved.
Bryan Preas, July 10, 1985 11:14:39 am PDT 
last edited Bryan Preas, February 5, 1987 8:27:21 pm PST
Define the routing design rules.  technologyKey values are predefinded for now.
Create a routing barrier for a layer.

Include a routing area side in a routing area. Each side has its own coordinate system: the barriers, pins and the *ChannelEnd's have coordinates with respect to the side.  fixedSide = TRUE -> the side should not be moved with respect to the routing area.
Create a RoutingArea.  The RoutingArea definition includes the design rules (conductor and via widths and spacings) and definition of the routing area sides.

set up the parameter data
set up the net data
Create a pin.  Use IncludeNet to specify the pins that are to be connected.

Create a net within the interconnection area.
Channel Route the routing area.
SwitchBox Route the routing area.
Maze Route the routing area.
Create a ChipNDale object and include the routing in the object. This object will be included in design if design # NIL.  RetreiveRouting is a separate procedure to allow routingArea size to be modified after routing is complete.
The externalConnections describe the location of a pin connecting the routingArea to the external environment.  Equivalent information is recorded as pins in the CND object.
Remove circular references so garbage collection can work

�ÊÁ˜
codeš
œ™Kšœ
Ïm
œ7™BKšœ'Ïkœ
™+Kšœž™8—K˜š
ž	˜	Kšžœl˜n—K˜šÐbn	œžœ
žœ
˜Kšžœ
žœQ˜[Kšžœ˜Kšžœ
˜K˜K˜Kš
Ïnœžœ
žœ!žœžœ˜jK˜Kš œžœ
žœ>žœžœžœ
˜dK˜Kš œžœ
žœ>žœžœžœ
˜fK˜Kšœžœ
žœ
žœžœ
žœ˜9Kšœžœ
žœ
žœžœ
žœ˜;K˜K˜š œžœ
žœžœdžœžœ˜¿
Kš
œO™OK˜šžœžœ
ž˜Kšœ
žœžœ ˜?Kšœžœ˜Kš
œ ˜ Kš
œ˜Kš
œ6˜6šžœž˜š
œ
˜
Kš
œ?˜?Kš
œ<˜<—š
œ˜Kš
œ?˜?Kš
œ<˜<—Kšžœ
˜K˜——šžœ
Ïc˜Kš
œ,˜,—K˜——š œžœ
žœ0žœžœžœ+˜ª
K™%K™Kšœžœ˜.Kš
œ˜Kš
œ!˜!Kš
œ(˜(—K˜š
 œžœ
žœwžœžœ˜Ä
Kšœ¹
žœB™ÿ
K˜Kšœ.žœ˜Ošžœžœ
ž˜ K˜8—š
ž˜Kšœ1žœ"˜VKš
œ˜Kš
œ,˜,Kš
œ(˜(Kš
œ'˜'Kš
œ'˜'——K˜š œžœ
žœžœžœ?žœžœ%˜°
K™�
K˜šžœžœ
ž˜K˜-—šžœ˜Kšœ.žœ%žœžœžœžœ˜kKšœžœ˜(Kš
œ#˜#Kš
œ ˜ Kš
œ$˜$Kš
œ(˜(K™Kš
œ™Kšœžœ
žœC˜aK˜Kš
œ™Kš	œžœ
žœDžœ
žœ˜„
——K˜š
 	œžœ
žœ	žœžœ˜ZKš
œK™KK™Kšœžœ ˜)K˜—š
 
œžœ
žœ0žœ;žœ˜Ž
Kš
œ-™-K˜Kšœ'žœ˜AKšœžœ(˜LKšœ	žœ˜Kšœžœ˜#K˜šžœ!žœž˜=Kšžœ#žœ˜@Kšžœ
˜K˜—šžœž˜ Kš
œ)˜)—šžœ˜Kš
œE˜EKš
œh˜hK˜Kš
œf˜fKš
œh˜hšœ
žœ/ž˜BKš
œ˜Kšžœ
žœžœ
žœ.˜QKšžœ
žœ0˜8—K˜Kš
œk˜kšœžœ1ž˜EKš
œ˜Kšžœ
žœ=˜E—K˜Kšœžœ ˜7Kšœžœ"˜:Kš
œf˜fKšœžœ®
˜È
Kš
œ˜——K˜š œžœ
žœ¥
žœžœžœ)˜þ
K™K˜Kšœsžœžœ˜�
šžœ8ž˜>Kš
œ9˜9—š
ž˜Kšœžœi˜|——K˜š œžœ
žœ¥
žœžœ&žœžœžœ)˜µK™!—˜Kš
Ϫ
˜™
šžœ:ž˜@Kš
œ9˜9—š
ž˜KšœžœQ˜d——K˜š 	œžœ
žœzžœ)˜À
K™—˜Kš
œ˜—K˜š œžœ
žœ5žœžœ žœžœžœžœ?˜‰Kšœtžœn™å
Kšœ¢
žœ™­
K˜Kšœ'žœ"˜OKš	œžœžœ
žœ
žœ4˜iKš
œ[˜[K˜šžœž˜š
œ˜Kšœžœžœ
žœ˜GKšžœ=˜AK˜Kš
ϕ
˜ï
Kš
œH˜H—K˜Kšœžœ
˜
Kšžœ˜	——K˜š œžœ
žœ%˜9Kš
œ9™9K™Kšœ'žœ˜Ašžœž˜Kš
œ8˜8Kšœžœ
˜
šžœ˜	K˜———š 	œžœžœžœ˜>Kšœžœ˜5Kšœžœ˜5Kšœžœ˜"K˜—š œžœžœžœ˜>Kšœžœ˜6Kš
œ˜K˜—Kš
œ˜šœž˜Kšœžœ
žœ#˜0K˜—š œžœžœ	žœ
žœžœ˜\š œ˜&Kšœžœžœ˜Kšœžœ	˜ Kšœ1žœC˜xKšœžœ˜K˜—Kš
œ'˜'K˜—š 
œžœžœ
žœ)žœžœžœ˜�
Jšœžœ˜Jšžœžœ
žœ2žœžœ
žœžœ
˜mJšœžœ˜%Kš
œ˜Kš
žœžœ
žœ
žœ5žœ˜ZK˜—š 	œžœ;žœ˜iK˜Kš
œ;˜;Kš
œU˜UKš
œi˜iKš
œ.˜.—Kš
œ˜K˜K˜K˜K˜—…—&j4Õ