! ILAP routers

%include "nmos.inc"
%external %string (255) %fn %spec ItoS (%integer I, P)

{#########################################################################}
{#                                                                       #}
{#      This program is part of the ILAP library, and was written in     #}
{#   The Department of Computer Science at the University of Edinburgh   #}
{#       (James Clerk Maxwell Building, Kings Buildings, Edinburgh)      #}
{#                                                                       #}
{#   This software is available free to other educational establisments  #}
{#   but the University of Edinburgh, retains all commercial rights.     #}
{#   It is a condition of having this software is that the sources are   #}
{#   not passed on to any other site, and that Edinburgh University is   #}
{#   given credit in any re-implementations of any of the algorithms     #}
{#   used, or articles published which refer to the software.            #}
{#                                                                       #}
{#   There is no formal support for this software, but any bugs should   #}
{#   be reported to Gordon Hughes or David Rees at the above address,    #}
{#   and these are likely to be fixed in a future release.               #}
{#                                                                       #}
{#########################################################################}

%routine fault (%string (31) name, %string (255) mess)
   warning("Routing symbol """.name.""" : ".mess)
%end

%external %integer %function route %alias "ILAP_ROUTE" (%string (31) name,
   %record (port) %array %name a,%record (port) %array %name b,
    %integer n, %string (4) lay,%integer twid, tsep, sepn)
%integerarray ap(1:n,1:n)
%integerarray apl(1:n)
%integer i,j,k,l,p,q,x,sep,tws
  %for p=1,1,n %cycle
    %if a(p)_w<twid %then fault(name, "A port ".itos(p,0)." too narrow")
    %if b(p)_w<twid %then fault(name, "B port ".itos(p,0)." too narrow")
  %repeat
  %for p=1,1,n-1 %cycle
    %if a(p)_x+a(p)_w+tsep>a(p+1)_x %then fault(name, "A ports ".itos(p,0). %c
      " and ".itos(p+1,0)." too close")
    %if b(p)_x+b(p)_w+tsep>b(p+1)_x %then fault(name, "B ports ".itos(p,0). %c
      " and ".itos(p+1,0)." too close")
  %repeat
  tws=twid+tsep
  sep=1
  %for p=1,1,n %cycle
    %if a(p)_x>=b(p)_x %and a(p)_x+a(p)_w<=b(p)_x+b(p)_w %then %c
      apl(p)=0 %and %continue    ;! b port overlaps a port
    %if a(p)_x<b(p)_x %then %start
      i=1
      %for j=p+1,1,n %cycle
        x=a(j)_x-i*tws
        %if x>=b(p)_x %then %exit
        ap(p,i)=x
        i=i+1
      %repeat
      ap(p,i)=b(p)_x
      apl(p)=i
    %finish %else %start
      i=1
      %for j=p-1,-1,1 %cycle
        x=a(j)_x+a(j)_w+i*tws
        %if x<=b(p)_x+b(p)_w %then %exit
        ap(p,i)=x
        i=i+1
      %repeat
      ap(p,i)=b(p)_x+b(p)_w
      apl(p)=-i
    %finish
    %if i>sep %then sep=i
  %repeat
  sep=tws*sep-tsep
  %if sepn>0 %then %start
    %if sepn<sep %then fault(name, "separation too small")
    sep=sepn
  %finish
  symbol(name)
  layer(lay) ; width(twid)
  %for p=1,1,n %cycle
    l=apl(p)
    %if l=0 %then box(a(p)_x,0,a(p)_x+twid,sep) %and %continue
    %if l>0 %then i=a(p)_x %and j=twid %else %c
      i=a(p)_x+a(p)_w %and j=-twid %and l=-l
    wirex(i,0,j) ; i=i+j
    %for q=1,1,l %cycle
      k=i
      i=ap(p,q)+j
      %if i#k %then ax(i)
      %if q<l %then dy(tws) %else ay(sep)
    %repeat
  %repeat
  endsymbol
  %result=sep
%end

%external %routine croute %alias "ILAP_CROUTE" (%string(31) name,
   %record(port)%arrayname a, %record(port)%arrayname b,
    %integer n, ya, xb, %string (4) lay, %integer twid, tsep)
%integerarray cx,cy(1:n,1:2*n)    {for corner coordinates}
%integerarray cp(0:n)    {for numbers of corners}
%integer i,j,k,l,p,tws,twidy,twsy,yb,xa,twidx,tsepx,twsx,yas
  %for p=1,1,n %cycle
    %if a(p)_w<twid %then fault(name, "A port ".itos(p,0)." too narrow")
    %if b(p)_w<twid %then fault(name, "B port ".itos(p,0)." too narrow")
  %repeat
  %if a(1)_x<a(n)_x %then j=1 %and k=1 %and l=n-1 %else j=n %and k=-1 %and l=2
  %for p=j,k,l %cycle
    %if a(p)_x+a(p)_w+tsep>a(p+k)_x %then fault(name, "A ports ".itos(p,0). %c
      " and ".itos(p+k,0)." too close")
  %repeat
  %if b(1)_x<b(n)_x %then j=1 %and k=1 %and l=n-1 %else j=n %and k=-1 %and l=2
  %for p=j,k,l %cycle
    %if b(p)_x+b(p)_w+tsep>b(p+k)_x %then fault(name, "B ports ".itos(p,0). %c
      " and ".itos(p+k,0)." too close")
  %repeat
  %if a(1)_x<a(n)_x %and xb>a(1)_x %then fault(name, "corner too far right")
  %if a(1)_x>a(n)_x %and xb<a(1)_x+a(1)_w %then fault(name, "corner too far left")
  %if b(1)_x<b(n)_x %and ya>b(1)_x %then fault(name, "corner too high")
  %if b(1)_x>b(n)_x %and ya<b(1)_x+b(1)_w %then fault(name, "corner too low")
  tws=twid+tsep
  symbol(name)
  layer(lay) ; width(twid)
  cp(0)=0
  %if xb>a(1)_x %then {right} twidx=twid %and tsepx=tsep %and twsx=tws %c
    %else {left} twidx=-twid %and tsepx=-tsep %and twsx=-tws
  %if ya<=b(1)_x %then {up} twidy=twid %and twsy=tws %and yas=ya %c
    %else {down} twidy=-twid %and twsy=-tws %and yas=ya-twid
  %for p=1,1,n %cycle
    %if twidx=twid %then {right} xa=a(p)_x %else {left} xa=a(p)_x+a(p)_w
    wirex(xa,yas,twidx)     {start wire off to right (left)}
    cx(p,1)=xa ; cy(p,1)=ya+twidy    {first new corner}
    %for i=1,1,cp(p-1) %cycle
      ax(cx(p-1,i)-tsepx)    {to right (left) as far as possible}
      ay(cy(p-1,i)+twsy)       {up (down) as little as possible}
      cx(p,i+1)=cx(p-1,i)-twsx
      cy(p,i+1)=cy(p-1,i)+twsy
    %repeat
    i=cp(p-1)    {just to make sure!}
    ax(xb)    {go to corner line}
    %if twidy=twid %then {up} yb=b(p)_x+b(p)_w %else {down} yb=b(p)_x
    %if cy(p,i+1)=yb %then cp(p)=i+1 %else %start
      ay(yb)
      cx(p,i+2)=xb-twidx
      cy(p,i+2)=yb
      cp(p)=i+2
    %finish
  %repeat
  endsymbol
hamish 1:
%end

%external %routine sroute %alias "ILAP_SROUTE" (%string(31) name,
   %record(port)%arrayname a,
   %record(port)%arrayname b,
   %record(port)%arrayname c,
   %record(port)%arrayname d,
   %integer ac, ab, bc, cd, da, ya, xb, yc, xd,
   %string (4) lay, %integer twid, tsep)
%integer tws,i,j,k,l,ap,cp,faulty,acl,acr,acm
%integerarray abx,aby(0:ac,1:2*ab+ac),abp(0:ac)
%integerarray bcx,bcy(0:0,0:2*bc),bcp(0:0)
%integerarray cdx,cdy(0:0,0:2*cd),cdp(0:0)
%integerarray dax,day(0:ac,1:2*da+ac),dap(0:ac)
%integer abcp,bccp,cdcp,dacp
%routinespec checkr(%integerarray(2)%name ax,ay,%integerarrayname ap(0:*),
  %integer app,%integerarray(2)%name bx,by,%integerarrayname bp(0:*),%integer bpp)
%routinespec checkl(%integerarray(2)%name ax,ay,%integerarrayname ap(0:*),
  %integer app,%integerarray(2)%name bx,by,%integerarrayname bp(0:*),%integer bpp)
%routinespec error(%string(31) s,%integer i)
%routinespec croute(%string(31) name,%record(port)%arrayname a(1:*),b(1:*),
  %integer n,ya,xb,%string(4) lay,%integer twid,tsep, %c
  %integerarray(2)%name ccx,ccy,%integerarrayname ccp(0:*))
  faulty=0
  %if da+ac+ab>0 %then %start
    %for i=1,1,da+ac+ab-1 %cycle
      %if a(i)_x+a(i)_w>a(i+1)_x %then error("A",i)
    %repeat
  %finish
  %if ab+bc>0 %then %start
    %for i=1,1,ab+bc-1 %cycle
      %if b(i)_x+b(i)_w>b(i+1)_x %then error("B",i)
    %repeat
  %finish
  %if cd+ac+bc>0 %then %start
    %for i=1,1,cd+ac+bc-1 %cycle
      %if c(i)_x+c(i)_w>c(i+1)_x %then error("C",i)
    %repeat
  %finish
  %if cd+da>0 %then %start
    %for i=1,1,cd+da-1 %cycle
      %if d(i)_x+d(i)_w>d(i+1)_x %then error("D",i)
    %repeat
  %finish
  %if faulty#0 %then disaster ("Unable to route """.name.""" because of errors")
  tws=twid+tsep
  %if ab>0 %then %start    {generate ab corner routing network}
    %begin
      %record(port)%array aba,abb(1:ab)
      %integer i
      %for i=1,1,ab %cycle    {set up ports for corner router}
        aba(i)=a(da+ac+ab-i+1)
        abb(i)=b(i)
      %repeat
      croute(name."#ab",aba,abb,ab,ya,xb,lay,twid,tsep,abx,aby,abp)
    %end
  %finish %else abp(0)=0
  %if bc>0 %then %start    {generate bc corner routing network}
    %begin
      %record(port)%array bca,bcb(1:bc)
      %integer i
      %for i=1,1,bc %cycle    {set up ports for corner router}
        bca(i)=c(cd+ac+bc-i+1)
        bcb(i)=b(ab+bc-i+1)
      %repeat
      croute(name."#bc",bca,bcb,bc,yc,xb,lay,twid,tsep,bcx,bcy,bcp)
    %end
  %finish %else bcp(0)=0
  %if cd>0 %then %start    {generate cd corner routing network}
    %begin
      %record(port)%array cda,cdb(1:cd)
      %integer i
      %for i=1,1,cd %cycle
        cda(i)=c(i)
        cdb(i)=d(da+cd-i+1)
      %repeat
      croute(name."#cd",cda,cdb,cd,yc,xd,lay,twid,tsep,cdx,cdy,cdp)
    %end
  %finish %else cdp(0)=0
  %if da>0 %then %start    {generate da corner routing network}
    %begin
      %record(port)%array daa,dab(1:da)
      %integer i
      %for i=1,1,da %cycle
        daa(i)=a(i)
        dab(i)=d(i)
      %repeat
      croute(name."#da",daa,dab,da,ya,xd,lay,twid,tsep,dax,day,dap)
    %end
  %finish %else dap(0)=0

  {find no of wires to route to left}
  acl=ac
  %for i=1,1,acl %cycle
    ap=da+i ; cp=cd+i
    %if a(ap)_x<=c(cp)_x %or a(ap)_x+a(ap)_w<=c(cp)_x+c(cp)_w %then %c
      acl=i-1 %and %exit
  %repeat

  %if acl=0 %then ->endl
  symbol(name."#acl")
    layer(lay) ; width(twid)
    %for i=1,1,acl %cycle
      ap=da+i ; cp=cd+i
      wirex(a(ap)_x+a(ap)_w,ya,-twid)
      dax(i,1)=a(ap)_x+a(ap)_w ; day(i,1)=ya+twid    {first new corner}
      l=c(cp)_x+c(cp)_w-twid
      %for j=1,1,dap(i-1) %cycle
        k=dax(i-1,j)+tsep
        %if k<l %then ax(l) %and ay(yc) %and dap(i)=j %and ->nextwl
        ax(k)
        ay(day(i-1,j)+tws)
        dax(i,j+1)=dax(i-1,j)+tws
        day(i,j+1)=day(i-1,j)+tws
      %repeat
      ax(l)
      ay(yc)
      dap(i)=dap(i-1)+1
nextwl:%repeat
  endsymbol
endl:

  {find no of wires to route to right}
  acr=ac-acl
  %for i=ac,-1,ac-acr+1 %cycle
    ap=da+i ; cp=cd+i
    %if a(ap)_x+a(ap)_w>=c(cp)_x+c(cp)_w %or a(ap)_x>=c(cp)_x %then %c
      acr=ac-i %and %exit
  %repeat

  %if acr=0 %then ->endr
  symbol(name."#acr")
    layer(lay) ; width(twid)
    %for i=1,1,acr %cycle
      ap=da+ac-i+1 ; cp=cd+ac-i+1
      wirex(a(ap)_x,ya,twid)
      abx(i,1)=a(ap)_x ; aby(i,1)=ya+twid    {first new corner}
      l=c(cp)_x+twid
      %for j=1,1,abp(i-1) %cycle
        k=abx(i-1,j)-tsep
        %if k>l %then ax(l) %and ay(yc) %and abp(i)=j %and ->nextwr
        ax(k)
        ay(aby(i-1,j)+tws)
        abx(i,j+1)=abx(i-1,j)-tws
        aby(i,j+1)=aby(i-1,j)+tws
      %repeat
      ax(l)
      ay(yc)
      abp(i)=abp(i-1)+1
nextwr:%repeat
  endsymbol
endr:

  acm=ac-acl-acr
  %if acm=0 %then ->endm
  %begin
  %record(port)%array aa,bb(1:acm)
  %integer i,sep
    %for i=1,1,acm %cycle
      aa(i)=a(da+acl+i)
      bb(i)=c(cd+acl+i)
    %repeat
    sep=route(name."#acm",aa,bb,acm,lay,twid,tsep,yc-ya)
  %end
endm:

  symbol(name)
    %if acl>0 %then draw(name."#acl",0,0)
    %if acm>0 %then draw(name."#acm",0,ya)
    %if acr>0 %then draw(name."#acr",0,0)
    %if ab>0 %then draw(name."#ab",0,0)
    %if bc>0 %then draw(name."#bc",0,0)
    %if cd>0 %then draw(name."#cd",0,0)
    %if da>0 %then draw(name."#da",0,0)
  endsymbol


{if acl>0 & acr>0 no checks necessary}
  %if acr=0 %then %start
    %if acm=0 %then checkr(dax,day,dap,acl,bcx,bcy,bcp,0) %else %start
      %begin
{hack}%integerarray mx,my(0:0,1:acm),mp(0:0)
{hack}%integer i,j,k,l
        mx(0,1)=a(da+ac)_x+a(da+ac)_w ; my(0,1)=ya+twid
        %for i=1,1,acm-1 %cycle
          ap=da+ac-i
          mx(0,i+1)=a(ap)_x+a(ap)_w+i*tws
          my(0,i+1)=my(0,i)+tws
        %repeat
        mp(0)=acm
        checkr(mx,my,mp,0,bcx,bcy,bcp,0)
      %end
    %finish
  %finish
  %if acl=0 %then %start
    %if acm=0 %then checkl(abx,aby,abp,acr,cdx,cdy,cdp,0) %else %start
      %begin
      %integerarray mx,my(0:0,1:acm),mp(0:0)
      %integer i
        mx(0,1)=a(da+1)_x ; my(0,1)=ya+twid
        %for i=1,1,acm-1 %cycle
          ap=da+i+1
          mx(0,i+1)=a(ap)_x-i*tws
          my(0,i+1)=my(0,i)+tws
        %repeat
        mp(0)=acm
        checkl(mx,my,mp,0,cdx,cdy,cdp,0)
      %end
    %finish
  %finish

%routine checkr(%integerarray(2)%name ax,ay,%integerarrayname ap(0:*),
                %integer app,
                %integerarray(2)%name bx,by,%integerarrayname bp(0:*),
                %integer bpp)
%integer i,j
  %for i=1,1,ap(app) %cycle
    %for j=1,1,bp(bpp) %cycle
      %if bx(bpp,j)>ax(app,i)+tsep %then %continue
      %if by(bpp,j)<ay(app,i)+tsep %then %start    {a little too stringent!}
        print string("networks too close at ")
        write(ax(app,i),0)
        print symbol(',')
        write(ay(app,i),0)
        newline
      %finish
    %repeat
  %repeat
%end

%routine checkl(%integerarray(2)%name ax,ay,%integerarrayname ap(0:*),%integer app, %c
               %integerarray(2)%name bx,by,%integerarrayname bp(0:*),%integer bpp)
%integer i,j
  %for i=1,1,ap(app) %cycle
    %for j=1,1,bp(bpp) %cycle
      %if bx(bpp,j)<ax(app,i)-tsep %then %continue
      %if by(bpp,j)<ay(app,i)+tsep %then %start   {also too stringent!}
        print string("networks too close at ")
        write(ax(app,i),0)
        print symbol(',')
        write(ay(app,i),0)
        newline
      %finish
    %repeat
  %repeat
%end

%routine error (%string(31) s, %integer i)
   warning ("Routing symbol """.name.""" :". %c
             s." port ".itos(i,0)." too close to port ".itos(i+1,0))
  faulty=1
%end

%routine croute(%string(31) name,%record(port)%arrayname a(1:*),b(1:*),
  %integer n,ya,xb,%string(4) lay,%integer twid,tsep,
  %integerarray(2)%name ccx,ccy,%integerarrayname ccp(0:*))
%integerarray cx,cy(1:n,1:2*n)    {for corner coordinates}
%integerarray cp(0:n)    {for numbers of corners}
%integer i,j,k,l,p,tws,twidy,twsy,yb,xa,twidx,tsepx,twsx,yas
  %for p=1,1,n %cycle
    %if a(p)_w<twid %then fault(name, "A port ".itos(p,0)." too narrow")
    %if b(p)_w<twid %then fault(name, "B port ".itos(p,0)." too narrow")
  %repeat
  %if a(1)_x<a(n)_x %then j=1 %and k=1 %and l=n-1 %else j=n %and k=-1 %and l=2
  %for p=j,k,l %cycle
    %if a(p)_x+a(p)_w+tsep>a(p+k)_x %then fault(name, "A ports ".itos(p,0). %c
      " and ".itos(p+k,0)." too close")
  %repeat
  %if b(1)_x<b(n)_x %then j=1 %and k=1 %and l=n-1 %else j=n %and k=-1 %and l=2
  %for p=j,k,l %cycle
    %if b(p)_x+b(p)_w+tsep>b(p+k)_x %then fault(name, "B ports ".itos(p,0). %c
      " and ".itos(p+k,0)." too close")
  %repeat
  %if a(1)_x<a(n)_x %and xb>a(1)_x %then fault(name, "corner too far right")
  %if a(1)_x>a(n)_x %and xb<a(1)_x+a(1)_w %then fault(name, "corner too far left")
  %if b(1)_x<b(n)_x %and ya>b(1)_x %then fault(name, "corner too high")
  %if b(1)_x>b(n)_x %and ya<b(1)_x+b(1)_w %then fault(name, "corner too low")
  tws=twid+tsep
  symbol(name)
  layer(lay) ; width(twid)
  cp(0)=0
  %if xb>a(1)_x %then {right} twidx=twid %and tsepx=tsep %and twsx=tws %c
    %else {left} twidx=-twid %and tsepx=-tsep %and twsx=-tws
  %if ya<=b(1)_x %then {up} twidy=twid %and twsy=tws %and yas=ya %c
    %else {down} twidy=-twid %and twsy=-tws %and yas=ya-twid
  %for p=1,1,n %cycle
    %if twidx=twid %then {right} xa=a(p)_x %else {left} xa=a(p)_x+a(p)_w
    wirex(xa,yas,twidx)     {start wire off to right (left)}
    cx(p,1)=xa ; cy(p,1)=ya+twidy    {first new corner}
    %for i=1,1,cp(p-1) %cycle
      ax(cx(p-1,i)-tsepx)    {to right (left) as far as possible}
      ay(cy(p-1,i)+twsy)       {up (down) as little as possible}
      cx(p,i+1)=cx(p-1,i)-twsx
      cy(p,i+1)=cy(p-1,i)+twsy
    %repeat
    i=cp(p-1)    {just to make sure!}
    ax(xb)    {go to corner line}
    %if twidy=twid %then {up} yb=b(p)_x+b(p)_w %else {down} yb=b(p)_x
    %if cy(p,i+1)=yb %then cp(p)=i+1 %else %start
      ay(yb)
      cx(p,i+2)=xb-twidx
      cy(p,i+2)=yb
      cp(p)=i+2
    %finish
  %repeat
  ccp(0)=cp(n)
  ccx(0,i)=cx(n,i) %and ccy(0,i)=cy(n,i) %for i=1,1,ccp(0)
  endsymbol
%end
%end

%endoffile