--routeInter.mesa DIRECTORY RouteDefs; RouteInter:PROGRAM IMPORTS RouteDefs EXPORTS RouteDefs=BEGIN OPEN RouteDefs; --RouteIntersections figures out the intersection --InterSilicon turns the internal representation into rectangles --WhereIs takes a path and a side and returns the runNo of that wire -- WhereIs returns the first matching path among equals --the circuit in IWire is the current assignment. -1 means unassigned Error:SIGNAL=CODE; spaceB:Lambda←0; RouteIntersections:PUBLIC CtlProc=BEGIN ShowLabel["INTERSECTIONS"]; EnumerateRectangles[SetSizeC]; EnumerateInters[MakeIWires]; --sets type,h,wire,path EnumerateInters[AssignIWires]; --sets nx,sx,ey,wy EnumerateAllIWire[CheckInter]; EnumerateInters[ShowInter]; EnumerateInters[ShowIWire]; RETURN[-1]; END; EnumerateAllPaths:PROCEDURE[c:PROCEDURE[PathPtr]]=BEGIN FOR wl:PathwayListPtr←paths, wl.t UNTIL wl=NIL DO FOR pl:PathListPtr←wl.h.path, pl.t UNTIL pl=NIL DO c[pl.h]; ENDLOOP; ENDLOOP; END; EnumerateIWire:PROCEDURE[r:RectanglePtr, c:PROCEDURE[RectanglePtr,IWirePtr]]= {FOR l:IWireListPtr←r.junction.iwires,l.t UNTIL l=NIL DO c[r,l.h]; ENDLOOP}; EnumerateAllIWire:PROCEDURE[c:PROCEDURE[RectanglePtr,IWirePtr]]=BEGIN Sub:PROCEDURE[rect:RectanglePtr]={EnumerateIWire[rect,c]}; EnumerateInters[Sub]; END; SetSizeC:PROCEDURE[rect:RectanglePtr]=BEGIN ew:INTEGER=(East[rect]-West[rect]+4)/7; ns:INTEGER=(North[rect]-South[rect]+4)/7; IF rect.orient=inter THEN {rect.sizeC.x←ew; rect.sizeC.y←ns} ELSE rect.sizeC.y←IF rect.orient=hor THEN ns ELSE ew; END; MakeIWires:PROCEDURE[inter:RectanglePtr]=BEGIN AddIWire:PROCEDURE[path:PathPtr]=BEGIN IF path.inter#inter THEN RETURN ELSE BEGIN h:Huggers=path.huggers; type:InterType=MakeType[n:path.n#NIL,e:path.e#NIL,s:path.s#NIL,w:path.w#NIL]; list:IWireListPtr←AllocateList[]; wire:IWirePtr←AllocateIWire[]; wire.type←type; wire.h←h; wire.path←path; path.wire←wire; list↑←[wire,inter.junction.iwires]; inter.junction.iwires←list; wire.be1←wire.h.n#w OR wire.h.s#w; wire.be2←wire.h.n#w AND wire.h.s#w; wire.bn1←wire.h.e=n OR wire.h.w=n; wire.bn2←wire.h.e=n AND wire.h.w=n; wire.nx←wire.sx←wire.ey←wire.wy←-1; END; END; EnumerateAllPaths[AddIWire]; END; RR:TYPE=PROCEDURE[r:RectanglePtr] RETURNS[x:Lambda]; South:RR={x←r.pos.y+r.levelers.s+r.margins.s}; West:RR ={x←r.pos.x+r.levelers.w+r.margins.w}; North:RR={x←r.pos.y+r.sizeL.y-r.levelers.n-r.margins.n}; East:RR ={x←r.pos.x+r.sizeL.x-r.levelers.e-r.margins.e}; AlreadyUsed:PROCEDURE[s:Side,junct:JunctionPtr,x:RunNo] RETURNS[BOOLEAN]= BEGIN t:BOOLEAN←FALSE; FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO w:IWirePtr=iwl.h; y:RunNo=SELECT s FROM n=>w.nx, s=>w.sx, e=>w.ey, ENDCASE=>w.wy; IF y=x THEN {IF t THEN RETURN[TRUE]; t←TRUE}; ENDLOOP; RETURN[FALSE]; END; AssignIWires:PROCEDURE[rect:RectanglePtr]=BEGIN junct:JunctionPtr=rect.junction; rw:RectanglePtr=IF rect.w=NIL THEN rect ELSE rect.w; re:RectanglePtr=IF rect.e=NIL THEN rect ELSE rect.e; rn:RectanglePtr=IF rect.n=NIL THEN rect ELSE rect.n; rs:RectanglePtr=IF rect.s=NIL THEN rect ELSE rect.s; ssw:RunNo←MAX[0,(West[rs]-West[rect]+6)/7]; sse:RunNo←MAX[0,(East[rect]-East[rs]+6)/7]; nnw:RunNo←MAX[0,(West[rn]-West[rect]+6)/7]; nne:RunNo←MAX[0,(East[rect]-East[rn]+6)/7]; wsw:RunNo←MAX[0,(South[rw]-South[rect]+6)/7]; ese:RunNo←MAX[0,(South[re]-South[rect]+6)/7]; wnw:RunNo←MAX[0,(North[rect]-North[rw]+6)/7]; ene:RunNo←MAX[0,(North[rect]-North[re]+6)/7]; Setnx:PROCEDURE[b:BOOLEAN]=BEGIN IF w.nx#-1 THEN RETURN; IF nne+nnw=topx+1 THEN Error ELSE IF b THEN {w.nx←topx-nne; nne←nne+1} ELSE {w.nx←nnw; nnw←nnw+1}; IF rect.n.orient=inter AND AlreadyUsed[n,junct,w.nx] THEN {w.nx←-1; Setnx[b]}; END; Setsx:PROCEDURE[b:BOOLEAN]=BEGIN IF w.sx#-1 THEN RETURN; IF sse+ssw=topx+1 THEN Error ELSE IF b THEN {w.sx←topx-sse; sse←sse+1} ELSE {w.sx←ssw; ssw←ssw+1}; IF rect.s.orient=inter AND AlreadyUsed[s,junct,w.sx] THEN {w.sx←-1; Setsx[b]}; END; Setey:PROCEDURE[b:BOOLEAN]=BEGIN IF w.ey#-1 THEN RETURN; IF ene+ese=topy+1 THEN Error ELSE IF b THEN {w.ey←topy-ene; ene←ene+1} ELSE {w.ey←ese; ese←ese+1}; IF rect.e.orient=inter AND AlreadyUsed[e,junct,w.ey] THEN {w.ey←-1; Setey[b]}; END; Setwy:PROCEDURE[b:BOOLEAN]=BEGIN IF w.wy#-1 THEN RETURN; IF wnw+wsw=topy+1 THEN Error ELSE IF b THEN {w.wy←topy-wnw; wnw←wnw+1} ELSE {w.wy←wsw; wsw←wsw+1}; IF rect.w.orient=inter AND AlreadyUsed[w,junct,w.wy] THEN {w.wy←-1; Setwy[b]}; END; ThruNS:PROCEDURE[z:BOOLEAN]={Setnx[z]; Setsx[z]}; ThruEW:PROCEDURE[z:BOOLEAN]={Setwy[z]; Setey[z]}; topx:RunNo←rect.sizeC.x-1; topy:RunNo←rect.sizeC.y-1; w:IWirePtr←NIL; FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO w←iwl.h; SELECT w.type FROM 05=>{Setnx[TRUE]; Setey[TRUE]}; 06=>{Setsx[TRUE]; Setey[FALSE]}; 09=>{Setnx[FALSE]; Setwy[TRUE]}; 10=>{Setsx[FALSE]; Setwy[FALSE]}; ENDCASE; ENDLOOP; FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO w←iwl.h; SELECT w.type FROM 07=>Setey[w.h.e=n]; 11=>Setwy[w.h.w=n]; 13=>Setnx[w.h.n#w]; 14=>Setsx[w.h.s#w]; ENDCASE; ENDLOOP; nne←sse←MAX[nne,sse]; nnw←ssw←MAX[nnw,ssw]; ese←wsw←MAX[ese,wsw]; ene←wnw←MAX[ene,wnw]; FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO w←iwl.h; SELECT w.type FROM 07=>ThruNS[w.be1]; 11=>ThruNS[w.be2]; 13=>ThruEW[w.bn1]; 14=>ThruEW[w.bn2]; ENDCASE; ENDLOOP; FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO w←iwl.h; IF w.type=15 THEN {ThruNS[w.be1]; ThruEW[w.bn1]}; ENDLOOP; FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO w←iwl.h; IF w.type=03 THEN ThruNS[w.be1]; IF w.type=12 THEN ThruEW[w.bn1]; ENDLOOP; junct.bridgeNS←nne; junct.bridgeEW←ese; FixNeighbor[rect]; END; FixNeighbor:PROCEDURE[rect:RectanglePtr]=BEGIN rw:RectanglePtr=IF rect.w=NIL THEN rect ELSE rect.w; re:RectanglePtr=IF rect.e=NIL THEN rect ELSE rect.e; rn:RectanglePtr=IF rect.n=NIL THEN rect ELSE rect.n; rs:RectanglePtr=IF rect.s=NIL THEN rect ELSE rect.s; deltxN:RunNo=West[rn]-West[rect]; deltxS:RunNo=West[rs]-West[rect]; deltxE:RunNo=South[re]-South[rect]; deltxW:RunNo=South[rw]-South[rect]; deltaN:RunNo=IF deltxN>=0 THEN (deltxN+6)/7 ELSE (deltxN-6)/7; deltaS:RunNo=IF deltxS>=0 THEN (deltxS+6)/7 ELSE (deltxS-6)/7; deltaE:RunNo=IF deltxE>=0 THEN (deltxE+6)/7 ELSE (deltxE-6)/7; deltaW:RunNo=IF deltxW>=0 THEN (deltxW+6)/7 ELSE (deltxW-6)/7; Sub:PROCEDURE[rect:RectanglePtr,w:IWirePtr]=BEGIN IF w.path.n#NIL AND w.path.n.wire#NIL AND w.path.n.wire.sx=-1 THEN w.path.n.wire.sx←w.nx-deltaN; IF w.path.s#NIL AND w.path.s.wire#NIL AND w.path.s.wire.nx=-1 THEN w.path.s.wire.nx←w.sx-deltaS; IF w.path.e#NIL AND w.path.e.wire#NIL AND w.path.e.wire.wy=-1 THEN w.path.e.wire.wy←w.ey-deltaE; IF w.path.w#NIL AND w.path.w.wire#NIL AND w.path.w.wire.ey=-1 THEN w.path.w.wire.ey←w.wy-deltaW; END; EnumerateIWire[rect,Sub]; END; CheckInter:PROCEDURE[rect:RectanglePtr,w:IWirePtr]=BEGIN lastx:INTEGER=rect.sizeC.x-1; realType:InterType=MakeType[n:w.nx#-1,e:w.ey#-1,s:w.sx#-1,w:w.wy#-1]; IF w.type#realType THEN Error; IF w.sx NOT IN [-1..rect.sizeC.x) THEN Error; IF w.nx NOT IN [-1..rect.sizeC.x) THEN Error; IF w.ey NOT IN [-1..rect.sizeC.y) THEN Error; IF w.wy NOT IN [-1..rect.sizeC.y) THEN Error; IF w.sx#-1 AND w.nx#-1 AND w.sx#w.nx THEN Error; IF w.ey#-1 AND w.wy#-1 AND w.ey#w.wy THEN Error; FOR iwl2:IWireListPtr←rect.junction.iwires,iwl2.t UNTIL iwl2=NIL DO w2:IWirePtr=iwl2.h; IF w2=w THEN EXIT; IF w.nx=w2.nx AND w.nx#-1 THEN Error; IF w.sx=w2.sx AND w.sx#-1 THEN Error; IF w.ey=w2.ey AND w.ey#-1 THEN Error; IF w.wy=w2.wy AND w.wy#-1 THEN Error; ENDLOOP; END; ShowInter:PROCEDURE[rect:RectanglePtr]=BEGIN junct:JunctionPtr=rect.junction; LineHor:PROCEDURE[lev,st,end:INTEGER]=BEGIN IF end=-1 THEN end←lasty; lev←2*lev+2; st←2*st+2; end←2*end+2; FOR j:INTEGER IN [st..end] DO Store[lev,j]; ENDLOOP; END; LineVer:PROCEDURE[lev,st,end:INTEGER]=BEGIN IF end=-1 THEN end←lastx; lev←2*lev+2; st←2*st+2; end←2*end+2; FOR j:INTEGER IN [st..end] DO Store[j,lev]; ENDLOOP; END; Store:PROCEDURE[x,y:INTEGER]=BEGIN IF x NOT IN [0..size/2) THEN {x←x-2*lastx-2+size-1; IF x NOT IN [size/2..size) THEN RETURN}; IF y NOT IN [0..size/2) THEN {y←y-2*lasty-2+size-1; IF y NOT IN [size/2..size) THEN RETURN}; copout[x][y]←TRUE; END; size:INTEGER=28; copout:ARRAY [0..size) OF ARRAY [0..size) OF BOOLEAN←ALL[ALL[FALSE]]; topY:INTEGER←0; lastx:INTEGER=rect.sizeC.x-1; lasty:INTEGER=rect.sizeC.y-1; Return[]; ShowDecimal[rect.channelNo,"Int "L]; Return[]; FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO w:IWirePtr=iwl.h; SELECT w.type FROM 03=> LineVer[w.sx,-1,-1]; 05=>{LineHor[w.ey,w.nx,-1]; LineVer[w.nx,w.ey,-1]}; 06=>{LineHor[w.ey,w.sx,-1]; LineVer[w.sx,-1,w.ey]}; 07=>{LineHor[w.ey,w.sx,-1]; LineVer[w.nx,-1,-1]}; 09=>{LineHor[w.wy,-1,w.nx]; LineVer[w.nx,w.wy,-1]}; 10=>{LineHor[w.wy,-1,w.sx]; LineVer[w.sx,-1,w.wy]}; 11=>{LineHor[w.wy,-1,w.sx]; LineVer[w.sx,-1,-1]}; 12=> LineHor[w.wy,-1,-1]; 13=>{LineHor[w.wy,-1,-1]; LineVer[w.nx,w.wy,-1]}; 14=>{LineHor[w.wy,-1,-1]; LineVer[w.sx,-1,w.wy]}; 15=>{LineHor[w.wy,-1,-1]; LineVer[w.sx,-1,-1]}; ENDCASE=>Error; ENDLOOP; Return[]; FOR i:INTEGER DECREASING IN [0..size) DO found:BOOLEAN←FALSE; FOR j:INTEGER IN [0..size) DO IF copout[i][j] THEN found←TRUE; EXIT; ENDLOOP; IF found THEN {topY←i+1; EXIT}; ENDLOOP; FOR i:INTEGER DECREASING IN [0..topY) DO y:INTEGER=i; --y:INTEGER=SELECT i FROM 0=>0, 2*lasty+2=>i-2, ENDCASE=>i-1; Return[]; FOR j:INTEGER IN [0..size) DO --z:INTEGER=SELECT j FROM 0=>0, 2*lastx+2=>j-2, ENDCASE=>j-1; z:INTEGER=j; ShowChar[IF copout[y][z] THEN 'b ELSE ' ]; ENDLOOP; ENDLOOP; END; ShowIWire:PROCEDURE[inter:RectanglePtr]=BEGIN Return[]; FOR wl:IWireListPtr←inter.junction.iwires,wl.t UNTIL wl=NIL DO wire:IWirePtr=wl.h; Return[]; ShowDecimal[wire.type, " type: "]; ShowDecimal[wire.nx, " nx: "]; ShowDecimal[wire.sx, " sx "]; ShowDecimal[wire.ey, " ey: "]; ShowDecimal[wire.wy, " wy: "]; ENDLOOP; END; InterSilicon:PUBLIC PROCEDURE[rect:RectanglePtr]=BEGIN junct:JunctionPtr=rect.junction; sB:Lambda←spaceB←rect.margins.s+rect.levelers.s; x:Lambda=rect.pos.x; width:Lambda=rect.sizeL.x; lastx:INTEGER=rect.sizeC.x-1; edge:Lambda=East[rect]-Across[lastx]-3; y:Lambda=rect.pos.y; LineHor:PROCEDURE[lev,st,end:INTEGER]=BEGIN yy:Lambda=y+AcrossS[lev]; xBot:Lambda=IF st=-1 THEN x ELSE edge+Across[st]; xTop:Lambda=IF end=-1 THEN x+rect.sizeL.x ELSE edge+Across[end]+3; MakeBlue[TRUE,xBot,yy,xTop-xBot]; END; LineVer:PROCEDURE[lev,st,end:INTEGER]=BEGIN xx:Lambda=edge+Across[lev]; yBot:Lambda=IF st=-1 THEN 0 ELSE AcrossS[st]; yTop:INTEGER=IF end=-1 THEN rect.sizeL.y ELSE AcrossS[end]+3; MakeBlue[FALSE,xx,y+yBot,yTop-yBot]; END; MakeBridge[rect]; FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO w:IWirePtr=iwl.h; SELECT w.type FROM 03=> LineVer[w.sx,-1,-1]; 05=>{LineHor[w.ey,w.nx,-1]; LineVer[w.nx,w.ey,-1]}; 06=>{LineHor[w.ey,w.sx,-1]; LineVer[w.sx,-1,w.ey]}; 07=>{LineHor[w.ey,w.sx,-1]; LineVer[w.nx,-1,-1]}; 09=>{LineHor[w.wy,-1,w.nx]; LineVer[w.nx,w.wy,-1]}; 10=>{LineHor[w.wy,-1,w.sx]; LineVer[w.sx,-1,w.wy]}; 11=>{LineHor[w.wy,-1,w.sx]; LineVer[w.sx,-1,-1]}; 12=> LineHor[w.wy,-1,-1]; 13=>{LineHor[w.wy,-1,-1]; LineVer[w.nx,w.wy,-1]}; 14=>{LineHor[w.wy,-1,-1]; LineVer[w.sx,-1,w.wy]}; 15=>{LineHor[w.wy,-1,-1]; LineVer[w.sx,-1,w.wy]; LineVer[w.sx,w.wy,-1];}; ENDCASE=>Error; ENDLOOP; END; Bridge:TYPE=ARRAY[0..4) OF Span←ALL[[]]; Span:TYPE=RECORD[none,hRed:BOOLEAN←TRUE,n,e:Lambda←-1,s,w:Lambda←bigRun]; SpanPtr:TYPE=POINTER TO Span; MakeBridge:PUBLIC PROCEDURE[rect:RectanglePtr]=BEGIN j:JunctionPtr=rect.junction; x:Lambda=rect.pos.x; y:Lambda=rect.pos.y; l:INTEGER; lastx:INTEGER=rect.sizeC.x-1; edge:Lambda=x+rect.sizeL.x-Across[lastx]-rect.margins.e-rect.levelers.e-3; bridge←ALL[[]]; FOR iwl:IWireListPtr←j.iwires,iwl.t UNTIL iwl=NIL DO w:IWirePtr=iwl.h; a,b,c,d:INTEGER←-1; SELECT w.type FROM 03=>{a←IF w.be1 THEN 2 ELSE 0; b←a+1}; 05=>IF w.nx>=j.bridgeNS THEN {IF w.ey<j.bridgeEW THEN {a←c←2; b←3}} ELSE IF w.ey<j.bridgeEW THEN {b←d←0; a←1; c←2} ELSE {d←3; a←c←1}; 06=>IF w.sx>=j.bridgeNS THEN {IF w.ey>=j.bridgeEW THEN {a←c←3; b←2}} ELSE IF w.ey>=j.bridgeEW THEN {b←d←1; a←0; c←3} ELSE {d←2; a←c←0}; 07=>{a←IF w.be1 THEN 2 ELSE 0; b←a+1; c←IF w.h.e=n THEN 3 ELSE 2; IF a=0 THEN d←c-2}; 09=>IF w.nx<j.bridgeNS THEN {IF w.wy<j.bridgeEW THEN {a←c←0; b←1}} ELSE IF w.wy<j.bridgeEW THEN {b←d←2; a←3; c←0} ELSE {d←1; a←c←3}; 10=>IF w.sx<j.bridgeNS THEN {IF w.wy>=j.bridgeEW THEN {a←c←1; b←0}} ELSE IF w.wy>=j.bridgeEW THEN {b←d←3; a←2; c←1} ELSE {d←0; a←c←2}; 11=>{a←IF w.be2 THEN 2 ELSE 0; b←a+1; d←IF w.h.w=n THEN 1 ELSE 0; IF a=2 THEN d←c+2}; 12=>{c←IF w.bn1 THEN 1 ELSE 0; d←c+2}; 13=>{c←IF w.bn1 THEN 1 ELSE 0; d←c+2; b←IF w.h.n#w THEN 3 ELSE 1; IF c=1 THEN a←b-1}; 14=>{c←IF w.bn2 THEN 1 ELSE 0; d←c+2; a←IF w.h.s#w THEN 2 ELSE 0; IF c=0 THEN a←b+1}; 15=>{a←IF w.be1 THEN 2 ELSE 0; b←a+1; c←IF w.bn1 THEN 1 ELSE 0; d←c+2}; ENDCASE=>LOOP; IF a#-1 THEN {l←w.sx; IF l=-1 OR l=bigRun THEN l←w.nx; bridge[a].e←MAX[bridge[a].e,l]; bridge[a].w←MIN[bridge[a].w,l]}; IF b#-1 THEN {l←w.sx; IF l=-1 OR l=bigRun THEN l←w.nx; bridge[b].e←MAX[bridge[b].e,l]; bridge[b].w←MIN[bridge[b].w,l]}; IF c#-1 THEN {l←w.ey; IF l=-1 OR l=bigRun THEN l←w.wy; bridge[c].s←MIN[bridge[c].s,l]; bridge[c].n←MAX[bridge[c].n,l]}; IF d#-1 THEN {l←w.ey; IF l=-1 OR l=bigRun THEN l←w.wy; bridge[d].s←MIN[bridge[d].s,l]; bridge[d].n←MAX[bridge[d].n,l]}; ENDLOOP; FOR i:INTEGER IN [0..4) DO span:SpanPtr←@bridge[i]; IF span.e=-1 OR span.n=-1 OR span.w=bigRun OR span.s=bigRun THEN LOOP; span.w←MAX[edge+Across[span.w]-3,x-4]; span.e←MIN[edge+Across[span.e]+7,x+rect.sizeL.x]; span.s←MAX[y+AcrossS[span.s]-3,y-4]; span.n←MIN[y+AcrossS[span.n]+7,y+rect.sizeL.y]; span.none←FALSE; ENDLOOP; Return[]; ShowDecimal[rect.channelNo, "bridge "]; FOR i:INTEGER IN [0..4) DO span:SpanPtr←@bridge[i]; Return[]; ShowString[IF span.none THEN " off " ELSE IF span.hRed THEN " hor " ELSE " vert "]; ShowDecimal[span.w, " w "]; ShowDecimal[span.e, " e "]; ShowDecimal[span.n, " n "]; ShowDecimal[span.s, " s "]; ENDLOOP; END; MakeBlue:PROCEDURE[hor:BOOLEAN,x,y,l:Lambda]=BEGIN IF l<0 THEN {IF hor THEN x←x+l ELSE y←y+l; l←-l}; IF hor THEN FOR i:INTEGER IN [0..4) DO s:SpanPtr←@bridge[i]; x1,x2:Lambda; IF s.none OR ~s.hRed THEN LOOP; IF y NOT IN [s.s..s.n) THEN LOOP; IF x NOT IN (s.w-l..s.e] THEN LOOP; IF ~s.hRed THEN BEGIN IF x IN (s.w..s.e] THEN MakeContact[x,y]; IF x+l IN (s.w..s.e] THEN MakeContact[x+l-3,y]; LOOP; END; x1←IF x<s.w+3 THEN s.w-4 ELSE x; x2←IF x+l>s.e-3 THEN s.e ELSE x+l-4; IF x<s.w THEN MakeBlueWire[TRUE,x,y,s.w-x]; MakeContact[x1,y]; MakeContact[x2,y]; MakeRedWire[TRUE,x1,y,x2-x1]; IF x+l<=s.e-3 THEN RETURN; l←x+l-s.e; x←s.e; ENDLOOP ELSE FOR i:INTEGER IN [0..4) DO s:SpanPtr←@bridge[i]; y1,y2:Lambda; IF s.none THEN LOOP; IF x NOT IN [s.w..s.e) THEN LOOP; IF s.hRed THEN BEGIN IF y IN (s.s..s.n] THEN MakeContact[x,y]; IF y+l IN (s.s..s.n] THEN MakeContact[x,y+l-3]; LOOP; END; IF y NOT IN (s.s-l..s.n] THEN LOOP; y1←IF y<s.s+3 THEN s.s-4 ELSE x; y2←IF y+l>s.n-3 THEN s.n ELSE y+l-4; IF y<s.s THEN MakeBlueWire[FALSE,x,y,s.s-y]; MakeContact[x,y1]; MakeContact[x,y2]; MakeRedWire[FALSE,x,y1,y2-y1]; IF y+l<=s.n-3 THEN RETURN; l←y+l-s.n; y←s.n; ENDLOOP; MakeBlueWire[hor,x,y,l]; END; bridge:Bridge; WhereIs:PUBLIC PROCEDURE[p:PathPtr,ss:Side,desired:RunNo] RETURNS[RunNo]=BEGIN i:RectanglePtr=p.inter; top:RunNo=i.sizeC.x-1; j:RectanglePtr=SELECT ss FROM n=>i.n, s=>i.s, e=>i.e, ENDCASE=>i.w; excessL:Lambda=SELECT ss FROM n,s=>East[i]-East[j], ENDCASE=>South[j]-South[i]; excessC:RunNo=excessL/7; desNo:RunNo=SELECT ss FROM n,s=>top-desired-excessC, ENDCASE=>excessC+desired; w:IWirePtr←FindOne[p,ss,desNo]; IF w=NIL OR j=NIL THEN {Error; RETURN[0]}; w.circuit←p.circuit; BEGIN myNo:RunNo=SELECT ss FROM n=>top-w.nx, s=>top-w.sx, e=>w.ey, ENDCASE=>w.wy; IF excessC>myNo THEN Error; RETURN[myNo-excessC]; END; END; FindOne:PUBLIC PROCEDURE[p:PathPtr,ss:Side,desired:RunNo] RETURNS[w:IWirePtr]=BEGIN best:INTEGER←10000; i:RectanglePtr=p.inter; ns:BOOLEAN=ss=n OR ss=s; type:InterType=MakeType[n:p.n#NIL,e:p.e#NIL,s:p.s#NIL,w:p.w#NIL]; FOR iwl:IWireListPtr←i.junction.iwires,iwl.t UNTIL iwl=NIL DO ww:IWirePtr←iwl.h; IF ww.type=type AND ww.circuit=p.circuit THEN RETURN[ww]; ENDLOOP; w←NIL; FOR iwl:IWireListPtr←i.junction.iwires,iwl.t UNTIL iwl=NIL DO ww:IWirePtr←iwl.h; IF ww.type=type AND ww.circuit=-1 -- AND EquivalentHugs[p.huggers,ww.h] THEN BEGIN this:RunNo=SELECT ss FROM e=>ww.ey, w=>ww.wy, n=>ww.nx, ENDCASE=>ww.sx; IF this=desired THEN RETURN[ww]; SELECT ABS[this-desired]-best FROM <0 => {w←ww; best←ABS[this-desired]}; -- 0 =>IF (SELECT type FROM -- 03=>ww.be1, 05=>ns, 06=>TRUE, 10=>~ns, 12=>~ww.bn1, -- 07=>IF ns THEN ww.be1 ELSE ww.h.e#n, -- 11=>IF ns THEN ww.be2 ELSE ww.h.w#n, -- 13=>IF ~ns THEN ~ww.bn1 ELSE ww.h.n#w, -- 14=>IF ~ns THEN ~ww.bn2 ELSE ww.h.s#w, -- 15=>IF ~ns THEN ~ww.bn1 ELSE ww.be1, -- ENDCASE=>FALSE)=(this<desired) THEN {w←ww; best←ABS[this-desired]}; ENDCASE; END; ENDLOOP; IF w=NIL THEN {Error; RETURN[NIL]}; END; EquivalentHugs:PROCEDURE[a,b:Huggers] RETURNS[BOOLEAN]=BEGIN RETURN[a.ch=b.ch AND (a.n#w)=(b.n#w) AND (a.s#w)=(b.s#w) AND (a.e#n)=(b.e#n) AND (a.w#n)=(b.w#n)]; END; Across:PROCEDURE[run:RunNo] RETURNS[Lambda]=BEGIN IF run=bigRun THEN Error; RETURN[7*run]; END; AcrossS:PROCEDURE[run:RunNo] RETURNS[Lambda]=BEGIN IF run=bigRun THEN Error; RETURN[7*run+spaceB]; END; END. Timing: Make - Inter*All PAths + AllIWires Silicon - Inter x 4 x IWires Where - IWire