DIRECTORY
DABasics, Rope, SC, SCNetUtil, SCPrivate, SCExprRoutePinsUtil;

SCExprRoutePinsUtilImpl: CEDAR PROGRAM
IMPORTS Rope, SC, SCNetUtil
EXPORTS SCExprRoutePinsUtil
SHARES SC = {

InitGetChanPins: PUBLIC PROCEDURE [handle: SC.Handle, rowChan: SCPrivate.RowChan] = {

InitNet: SCNetUtil.EachNetProc = {net.netDat _ NIL};

chanDat: SCExprRoutePinsUtil.ChanDat _ NEW[SCExprRoutePinsUtil.ChanDatRec];
chanDat.head _ chanDat.tail _ NEW[SCExprRoutePinsUtil.PinInChanRec _ [min: FIRST[INT], max: FIRST[INT], depth: 0, layer: 0]];
rowChan.chanDat _ chanDat;
rowChan.wireLength _ rowChan.chanDensity _ rowChan.chanWidth _ 0;
[] _ SCNetUtil.EnumerateNets[handle, InitNet]};

TermGetChanPins: PUBLIC PROCEDURE [handle: SC.Handle, rowChan: SCPrivate.RowChan] = {

TermNet: SCNetUtil.EachNetProc = {
netDat: SCExprRoutePinsUtil.NetDat _ NARROW[net.netDat];
IF netDat # NIL THEN {
chanNetDat: SCExprRoutePinsUtil.ChanNetDat _ netDat[rowChan.chanNum];
IF chanNetDat # NIL THEN
chanNetDat.firstPin _ chanNetDat.lastPin _ chanNetDat.leftmost _ chanNetDat.rightmost _ chanNetDat.exits[left] _ chanNetDat.exits[right] _ NIL;
net.netDat _ NIL};
net.pinList _ NIL;
net.edgeList _ NIL};

EachPin: SCExprRoutePinsUtil.EachPinProc = {
pin.prevPinInChan _ pin.nextPinInNet _ NIL};

EnumPinsInChan[rowChan, EachPin];
[] _ SCNetUtil.EnumerateNets[handle, TermNet];
rowChan.chanDat _ NIL};

EnterPin: PUBLIC PROCEDURE[rowChan: SCPrivate.RowChan, min, max, depth: SC.Number, layer: SC.Layer, net: SCPrivate.Net, side: DABasics.TBSide, alwaysUse: BOOLEAN] RETURNS[pinInChan: SCExprRoutePinsUtil.PinInChan] = {
chanDat: SCExprRoutePinsUtil.ChanDat _ NARROW[rowChan.chanDat];
tail: SCExprRoutePinsUtil.PinInChan _ chanDat.tail;
chanDat.tail _ tail.nextPinInChan _ pinInChan _ NEW[SCExprRoutePinsUtil.PinInChanRec _ [
layer: layer,
net: net,
chanNet: NIL,
min: min, max: max, depth: depth,
pinClass: isPin,
chanSide: side,
nextPinInChan: NIL,
prevPinInChan: tail,
pinConn: unconnected,
nextPinInNet: NIL,  prevPinInNet:  NIL,
localDensity: 0 ,
alwaysUse: alwaysUse,
chanNum: rowChan.chanNum]];
rowChan.chanDat _ chanDat};
EnterExit: PUBLIC PROCEDURE[rowChan: SCPrivate.RowChan, pos: SC.Number, layer: SC.Layer, net: SCPrivate.Net, side: DABasics.LRSide] RETURNS[pinInChan: SCExprRoutePinsUtil.PinInChan] = {

chanDat: SCExprRoutePinsUtil.ChanDat _ NARROW[rowChan.chanDat];
tail: SCExprRoutePinsUtil.PinInChan _ chanDat.tail;
chanDat.tail _ tail.nextPinInChan _ pinInChan _ NEW[SCExprRoutePinsUtil.PinInChanRec _ [
layer: layer,
net: net,
chanNet: NIL,
min: pos, max: pos, depth: 0,
pinClass: isExit,
chanSide: side,
nextPinInChan: NIL,
prevPinInChan: tail,
pinConn: unconnected,
nextPinInNet: NIL,  prevPinInNet:  NIL,
localDensity: 0 ,
alwaysUse: TRUE,
chanNum: rowChan.chanNum]];
rowChan.chanDat  _ chanDat};

NoChange: PROCEDURE[mpin, pin: SCExprRoutePinsUtil.PinInChan] RETURNS[yes: BOOLEAN _ FALSE] = {
IF mpin.nextPinInNet # NIL THEN
yes _ (mpin.nextPinInNet.min = pin.min) AND (mpin.nextPinInNet.pinConn #unconnected);
IF mpin.prevPinInNet # NIL THEN
yes _  yes OR (mpin.prevPinInNet.min = pin.min) AND (mpin.prevPinInNet.pinConn # unconnected) };

MoveAPinInChan: PUBLIC PROCEDURE[rowChan: SCPrivate.RowChan, pin: SCExprRoutePinsUtil.PinInChan, deltaX: SC.Number]  RETURNS[scan: BOOLEAN _ FALSE] = {

next: SCExprRoutePinsUtil.PinInChan _ pin;
prev: SCExprRoutePinsUtil.PinInChan _ pin;
origX, currX, dX: SC.Number;

origX _ currX _ pin.min;
pin.min _ pin.min + deltaX;
pin.max _ pin.max + deltaX;
IF pin.min = rowChan.chanDensity THEN scan _ TRUE;
IF deltaX > 0 THEN  {
prev _ pin.prevPinInChan;
IF (prev # NIL) AND (prev.min = currX)  AND (pin.pinConn = left) THEN 
prev.localDensity _ prev.localDensity - 1;
WHILE (pin.nextPinInChan # NIL) AND (pin.nextPinInChan.min <= pin.min) DO
next _ pin.nextPinInChan;
IF next.localDensity = rowChan.chanDensity THEN scan _ TRUE;
dX _ next.min - currX;
currX _ next.min;
SwapTwoPins[pin, next];
SELECT pin.pinConn FROM
left => {
IF pin.net = next.net THEN {
SELECT next.pinConn FROM
interior => {
pin.pinConn _ interior;
next.pinConn _ left;
pin.chanNet.leftmost _ next};
right => {
pin.pinConn _ right;
next.pinConn _ left;
pin.chanNet.leftmost _ next;
pin.chanNet.rightmost _ pin};
ENDCASE};
rowChan.wireLength _ rowChan.wireLength - dX};
interior => {
IF pin.net = next.net THEN
IF next.pinConn = right THEN {
next.pinConn _ interior;
pin.pinConn _ right;
pin.chanNet.rightmost _ pin}};
right => {
rowChan.wireLength _ rowChan.wireLength + dX};
ENDCASE;
IF pin.net = next.net THEN 
SwapTwoPinsInNet[pin, next];
ENDLOOP;
dX _ pin.min - currX;
IF pin.pinConn = right THEN 
rowChan.wireLength _ rowChan.wireLength + dX;
IF pin.pinConn = left THEN
rowChan.wireLength _ rowChan.wireLength - dX; 
next _ pin.nextPinInChan}
ELSE IF deltaX < 0 THEN {
next _ pin.nextPinInChan;
IF (next # NIL) AND (next.min = currX)  AND (pin.pinConn = right) THEN 
next.localDensity _ next.localDensity  - 1;
WHILE (pin.prevPinInChan # NIL) AND (pin.prevPinInChan.min >= pin.min) DO
prev _ pin.prevPinInChan;
IF prev.localDensity = rowChan.chanDensity THEN scan _ TRUE;
dX _ currX - prev.min;
currX _ prev.min;
SwapTwoPins[prev, pin];
SELECT pin.pinConn FROM
right => {
IF pin.net = prev.net THEN {
SELECT prev.pinConn FROM
interior => {
pin.pinConn _ interior;
prev.pinConn _ right;
pin.chanNet.rightmost _ prev};
left => {
pin.pinConn _ left;
prev.pinConn _ right;
pin.chanNet.leftmost _ pin;
pin.chanNet.rightmost _ prev};
ENDCASE};
rowChan.wireLength _ rowChan.wireLength - dX};
interior => {
IF pin.net = prev.net THEN
IF prev.pinConn = left THEN {
prev.pinConn _ interior;
pin.pinConn _ left;
pin.chanNet.leftmost _ pin}};
left => {
rowChan.wireLength _ rowChan.wireLength + dX};
ENDCASE;
IF pin.net = prev.net THEN 
SwapTwoPinsInNet[prev, pin];
ENDLOOP;
dX _ currX - pin.min;
IF pin.pinConn = left THEN 
rowChan.wireLength _ rowChan.wireLength + dX;
IF pin.pinConn = right THEN
rowChan.wireLength _ rowChan.wireLength - dX}};

SortPins:  PROCEDURE[chanDat: SCExprRoutePinsUtil.ChanDat]  = {

stop: BOOLEAN _ FALSE;
temp: SCExprRoutePinsUtil.PinInChan;
head: SCExprRoutePinsUtil.PinInChan _ chanDat.head;

WHILE ~stop DO
rList: SCExprRoutePinsUtil.PinInChan _ head;
stop _ TRUE;
WHILE rList.nextPinInChan # NIL DO
temp _ rList.nextPinInChan;
IF rList.min > temp.min THEN {
stop _ FALSE;
SwapTwoPins[rList, temp]};
rList _ temp;
ENDLOOP;
ENDLOOP};

SwapTwoPins: PROCEDURE[pin1, pin2: SCExprRoutePinsUtil.PinInChan] = {
IF pin2.nextPinInChan # NIL  THEN
pin2.nextPinInChan.prevPinInChan _ pin1;
IF pin1.prevPinInChan # NIL THEN
pin1.prevPinInChan.nextPinInChan _ pin2;
pin1.nextPinInChan _ pin2.nextPinInChan;
pin2.prevPinInChan _ pin1.prevPinInChan;
pin1.prevPinInChan  _ pin2;
pin2.nextPinInChan _ pin1};

SwapTwoPinsInNet: PROCEDURE[pin1, pin2: SCExprRoutePinsUtil.PinInChan] = {
chanNetDat: SCExprRoutePinsUtil.ChanNetDat _ pin1.chanNet;
IF pin2.nextPinInNet # NIL  THEN
pin2.nextPinInNet.prevPinInNet _ pin1;
IF pin1.prevPinInNet # NIL THEN
pin1.prevPinInNet.nextPinInNet _ pin2;
pin1.nextPinInNet _ pin2.nextPinInNet;
pin2.prevPinInNet _ pin1.prevPinInNet;
pin1.prevPinInNet  _ pin2;
pin2.nextPinInNet _ pin1;
IF chanNetDat.firstPin = pin1 THEN chanNetDat.firstPin _ pin2;
IF chanNetDat.lastPin = pin2 THEN chanNetDat.lastPin _ pin1};

EnumPinsInChan: PUBLIC PROCEDURE[rowChan: SCPrivate.RowChan, doEachPin: SCExprRoutePinsUtil.EachPinProc] = {

chanDat: SCExprRoutePinsUtil.ChanDat _ NARROW[rowChan.chanDat];
IF chanDat # NIL THEN {
head: SCExprRoutePinsUtil.PinInChan _ chanDat.head;
FOR chanPin: SCExprRoutePinsUtil.PinInChan _ head.nextPinInChan, chanPin.nextPinInChan WHILE chanPin # NIL DO
doEachPin[rowChan, chanPin];
ENDLOOP}};

EnumAllPinsInNetChan: PUBLIC PROCEDURE[chanNetDat: SCExprRoutePinsUtil.ChanNetDat, doEachNetPin: SCExprRoutePinsUtil.EachNetPinProc] = {

IF chanNetDat # NIL THEN {
FOR chanPin: SCExprRoutePinsUtil.PinInChan _ chanNetDat.firstPin, chanPin.nextPinInNet WHILE chanPin # NIL DO
doEachNetPin[chanNetDat, chanPin];
ENDLOOP}};

EnumPinsInNetChan: PUBLIC PROCEDURE[chanNetDat: SCExprRoutePinsUtil.ChanNetDat, side: DABasics.Side, doEachNetPin: SCExprRoutePinsUtil.EachNetPinProc] = {

IF chanNetDat # NIL THEN {
FOR chanPin: SCExprRoutePinsUtil.PinInChan _ chanNetDat.firstPin, chanPin.nextPinInNet WHILE chanPin # NIL DO
IF chanPin.chanSide = side OR chanPin.pinClass = isExit THEN doEachNetPin[chanNetDat, chanPin];
ENDLOOP}};

CreateNetDat: PUBLIC PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan] = {

DoEachPin:  SCExprRoutePinsUtil.EachPinProc = {
net: SCPrivate.Net _ pin.net;
netDat: SCExprRoutePinsUtil.NetDat _ NARROW[net.netDat];
chanNum: NAT _ rowChan.chanNum;
chanNetDat: SCExprRoutePinsUtil.ChanNetDat _ NIL;
IF netDat = NIL THEN
net.netDat _ netDat _ NARROW[NEW[SCExprRoutePinsUtil.NetDatRec _ ALL[NIL]]];
IF netDat[chanNum] = NIL THEN
netDat[chanNum] _ NEW[SCExprRoutePinsUtil.ChanNetDatRec];
chanNetDat _ netDat[chanNum];
IF pin.pinClass = isExit THEN {
IF chanNetDat.exits[pin.chanSide] # NIL THEN
SC.Error[programmingError, "More than two exits for a net one side of a channel"]
ELSE chanNetDat.exits[pin.chanSide] _ pin};
IF chanNetDat.firstPin = NIL THEN {
chanNetDat.firstPin _ (chanNetDat.lastPin _ pin);
chanNetDat.net _ net}
ELSE {
pin.prevPinInNet _ chanNetDat.lastPin;
chanNetDat.lastPin.nextPinInNet _ pin;
chanNetDat.lastPin _ pin};
chanNetDat.pinCount _ chanNetDat.pinCount + 1;
pin.chanNet _ chanNetDat};

SortPins[NARROW[rowChan.chanDat]];
EnumPinsInChan[rowChan, DoEachPin]};

GetANetSegInChan: PUBLIC PROC [handle:  SC.Handle, rowChan: SCPrivate.RowChan, net: SCPrivate.Net, segProc: SCExprRoutePinsUtil.SegProc, pinProc: SCExprRoutePinsUtil.PinProc, exitProc: SCExprRoutePinsUtil.ExitProc] ~ {
layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows _ layoutData.lgRows;
netDat: SCExprRoutePinsUtil.NetDat _ NARROW[net.netDat];
chan: SCPrivate.ZMaxChanSr _ rowChan.chanNum;
segNum: SC.Number _ 1;
chanNetDat: SCExprRoutePinsUtil.ChanNetDat _ netDat[chan];

IF chanNetDat # NIL THEN {
firstPin: SCExprRoutePinsUtil.PinInChan _  chanNetDat.firstPin;
lastPin: SCExprRoutePinsUtil.PinInChan _ chanNetDat.lastPin;
pin: SCExprRoutePinsUtil.PinInChan _ firstPin;
IF firstPin # NIL THEN {
DO
IF pin.pinClass = isExit THEN 
{IF exitProc # NIL THEN exitProc[pin.chanSide, pin.layer, pin.net]}
ELSE IF pin.pinClass = isPin AND pin.pinConn # unconnected THEN 
{IF pinProc # NIL THEN pinProc[pin.min, pin.max, pin.depth, pin.chanSide, pin.layer, pin.net]};
IF pin.pinConn = right THEN {
segNum _ segNum + 1; 
IF segProc # NIL THEN segProc[segNum, net]};
IF pin = lastPin THEN EXIT
ELSE pin _ pin.nextPinInNet;
ENDLOOP}}};

GetAllNetSegInChan: PUBLIC PROC [handle: SC.Handle, rowChan: SCPrivate.RowChan, segProc: SCExprRoutePinsUtil.SegProc, pinProc: SCExprRoutePinsUtil.PinProc, exitProc: SCExprRoutePinsUtil.ExitProc] ~ {

EachNet: SCNetUtil.EachNetProc ~ {
IF net.netDat # NIL THEN
GetANetSegInChan[handle, rowChan, net, segProc, pinProc, exitProc]};

[] _ SCNetUtil.EnumerateNets[handle, EachNet]};

NextPinState: PROC [pinState: SCExprRoutePinsUtil.ConnectionType, pin: SCExprRoutePinsUtil.PinInChan] RETURNS [newPinState: SCExprRoutePinsUtil.ConnectionType] ~ {
IF pin.pinConn = unconnected THEN {  -- this pin is unconnected
newPinState _ unconnected;
IF pin.pinClass = isExit THEN
SC.Signal[programmingError, Rope.Cat["Exit is unconnected for wire: ", pin.net.name, ".  Call maintainer"]]}
ELSE IF pin.pinConn = interior THEN {	-- this pin is unconnected; determine which type
IF pinState = unconnected THEN		-- fitst pin we have come to
newPinState _ left 
ELSE newPinState _ interior}};

PosOfPin: PROC [chanPin: SCExprRoutePinsUtil.PinInChan] RETURNS [INT] ~ INLINE{
RETURN[(chanPin.min+chanPin.max)/2]};

}.

–SCExprRoutePinsUtilImpl.mesa
Copyright Σ 1987 by Xerox Corporation.  All rights reserved.
Jason Cong, August 25, 1987 6:10:14 pm PDT
last edited by Preas, August 4, 1987 10:59:25 am PDT
Bryan Preas August 25, 1987 10:58:04 am PDT
Jean-Marc Frailong October 11, 1987 10:12:38 pm PDT
initialize for determining the width of a channel 
terminate determining the width of a channel 
PROC[rowChan: SCPrivate.RowChan, pin: PinInChan];
enter a net on a channel into data structure 

enter exit data for a channel into routing data base 

enumerate all the pins on this channel (all nets)
enumerate the pins on this net on this channel (including exits)
enumerate the pins on this net on this channel on side (including exits)
initialize the data for a channel
EachPinProc: TYPE = PROC[rowChan: SCPrivate.RowChan, pin:PinInChan];

main body of 'CreateNetDat'
enter a net segment into chanNetDat, and enter pin connection info in pin.

main body of GetANetSegInChan
enter all net segment into the netDats, and enter pin connection info.
PROC [net: SCPrivate.Net] RETURNS [quit: BOOL _ FALSE];
compute connection of this pin as a function of its position and the previous state
Κ˜
codeš
œ™Kš
œ<™<Kš
œ*™*Kšœ1Οk™4Kš
œ+™+K™3K˜—š
	˜	Kšœœ,˜>K˜—šΟnœœ
˜&Kšœœ˜Kšœ˜Kšœ
œ˜
K˜—Kš
œ2™2šžœœ
	œ
œ(˜UK˜Kšžœ(œ˜4K˜Kšœ'œ!˜KJšœœ*œ
œœ
œ˜}J˜J˜AKš
œ/˜/K˜—Kš
œ-™-šžœœ
	œ
œ(˜UK˜šžœ˜"Kšœ%œ
˜8šœ
œ
œ˜Kš
œE˜Ešœœ
˜Kšœ‹
œ
˜
—Kšœ
œ˜—Kš
œ˜š
œ˜K˜——šžœ%˜,Kšœ-™1Kšœ'œ˜,K˜—Jš
œ!˜!Kš
œ.˜.Kšœœ˜K˜—Kš
œ-™-šžœœ
	œ.œœ>œœ.˜Ψ
Kšœ'œ˜?Kš
œ3˜3šœ0œ%˜XKš
œ
˜
J˜	Jšœ	œ
˜
Jš
œ!˜!Jš
œ˜Jš
œ˜Jšœœ
˜Jš
œ˜J˜Jšœœœ
˜'Jš
œ˜Jš
œ˜Jš
œ˜—Kš
œ˜—K™Kš
œ5™5šž	œœ
	œ"œœ3œ.˜Ή
K˜Kšœ'œ˜?Kš
œ3˜3šœ0œ%˜XKš
œ
˜
J˜	Jšœ	œ
˜
Jš
œ˜Jš
œ˜Jš
œ˜Jšœœ
˜Jš
œ˜J˜Jšœœœ
˜'Jš
œ˜Jšœœ
˜Jš
œ˜—Kš
œ˜K˜—š
žœ	œ+œœœ˜_šœœ
˜Kšœ(œ*˜U—šœœ
˜Kšœœ#œ-˜`—K˜—šžœœ
	œIœ
œœœ˜—
K˜Kš
œ*˜*Kš
œ*˜*Kšœœ˜K˜K˜K˜K˜Kšœœœ
˜2šœœ˜K˜š
œ	œœœœ
˜FK˜*—šœœœ$˜IK˜Kšœ)œœ
˜<K˜K˜K˜šœ
˜˜	šœœ˜šœ˜˜
K˜K˜K˜—˜
K˜K˜K˜K˜—Kšœ˜	——K˜.—˜
šœ˜šœœ˜K˜K˜K˜———˜
K˜.—Kšœ
˜—šœœ
˜K˜—Kšœ
˜—Kš
œ˜šœœ
˜Kš
œ-˜-—šœ˜Kš
œ.˜.—K˜—šœ
œœ˜K˜š
œ	œœœœ
˜GK˜+—šœœœ$˜IK˜Kšœ)œœ
˜<K˜K˜K˜šœ
˜˜
šœœ˜šœ˜˜
K˜K˜K˜—˜	K˜K˜K˜K˜—Kšœ˜	——K˜.—˜
šœ˜šœœ˜K˜K˜K˜———˜	K˜.—Kšœ
˜—šœœ
˜K˜—Kšœ
˜—K˜šœœ
˜Kš
œ-˜-—šœ˜Kš
œ/˜/——K˜—šžœ	œ+˜?K˜Kšœœœ
˜Kš
œ$˜$Kš
œ3˜3K˜šœ˜Kš
œ,˜,Kšœœ
˜šœœ
˜"K˜šœœ˜Kšœœ
˜
Kš
œ˜—K˜
Kšœ
˜—Kšœ˜	K˜——šžœ	œ/˜Ešœœ˜!K˜(—šœœ
˜ K˜(—K˜(K˜(K˜K˜K˜—šžœ	œ/˜JKš
œ:˜:šœœ˜ K˜&—šœœ
˜K˜&—K˜&K˜&K˜K˜Kšœœ˜>Kšœœ˜=K˜K™—Kš
œ1™1šžœœ
	œL˜lK˜Kšœ'œ˜?šœœ
œ˜Kš
œ3˜3šœTœœ
˜mKš
œ˜Kšœ˜
——K˜—Kš
œ@™@šžœœ
	œb˜ˆ
K˜šœœ
œ˜šœTœœ
˜mKš
œ"˜"Kšœ˜
——K˜—Kš
œH™Hšžœœ
	œw˜š
K˜šœœ
œ˜šœTœœ
˜mKšœœœ#˜_Kšœ˜
——K˜—Kš
œ!™!šžœœ
	œ	œ(˜QK˜šž	œ&˜/Kšœ
œœ,™DK™K˜Kšœ%œ
˜8Kšœ	œ˜Kšœ-œ
˜1šœ
œ
˜Kš	œœ
œ!œ
œ˜L—šœœ
˜Kšœœ$˜9—Kš
œ˜šœœ˜šœ"œ
˜,KšœO˜Q—Kšœ'˜+—šœœ
œ˜#K˜1K˜—šœ˜K˜&K˜&K˜—K˜.K˜—K˜Kš
œ™Kšœ	œ˜"K˜$K˜—J™Jšžœœ
œœ°
˜Ϊ
K™Kš
œ™Kšœ#œ˜=Kš
œ-˜-Kšœ%œ
˜8Kš
œ-˜-Kšœœ˜Kš
œ:˜:K˜šœœ
œ˜Kš
œ?˜?Kš
œ<˜<Kš
œ.˜.šœœ
œ˜š
˜šœœ
˜Kšœ
œœ
œ,˜C—šœ
œœœ
˜@Kšœ
œœ
œI˜_—šœœ˜Kš
œ˜Kšœœ
œ˜,—Kšœœ
˜Kšœ˜Kšœ˜——K˜——šžœœ
œ
œœ
˜Η
K˜J™Fšžœ˜"Kšœœœœ™7šœœ
˜Kš
œD˜D—K˜—Kš
œ/˜/K˜—šžœœTœ6˜£
Kš
œS™Sšœœ˜?Kš
œ˜šœ˜Kšœj˜l——šœ
œœ3˜Všœœ˜<Kš
œ˜—Kšœ˜—K˜—š
žœœ*œœœ
˜OKšœ˜%K˜š
œ˜K˜———…—-Κ>o