--routeChecker.mesa

DIRECTORY  RouteDefs, IODefs;

RouteChecker:PROGRAM IMPORTS RouteDefs EXPORTS RouteDefs=BEGIN
OPEN RouteDefs;

Error:SIGNAL=CODE;--internal consistancy
CheckerComplaint:SIGNAL=CODE;

testList:SiliconListPtr←NIL;
start:Silicon←[];
solid:BOOLEAN;
Ugly:TYPE=RECORD[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p:BOOLEAN←FALSE];
circuitsTested:ARRAY [0..100) OF Ugly;

CheckLayout:PUBLIC CtlProc=BEGIN
ShowLabel["CHECKER"];
IF layout=NIL THEN RETURN[-1];
IF testList#NIL THEN Error;
circuitsTested←ALL[[]];
EnumerateSilicon[InitSilicon];
EnumerateAllSignals[DoTheWork];
EnumerateSilicon[LogOpens];
RETURN[-1];
END;

InitSilicon:PROCEDURE[s:SiliconPtr]={s.circuit←0; s.solid←FALSE};

LogOpens:PROCEDURE[s:SiliconPtr]={IF ~s.solid THEN LogWire[s,"loose wire!"]};

DoTheWork:PROCEDURE[c:CellPtr,s:SignalPtr]=
  {FollowCircuit[GetSeed[c,s]]};

GetSeed:PROCEDURE[cell:CellPtr,signal:SignalPtr]
  RETURNS[SiliconPtr]=BEGIN
width:Lambda=SELECT signal.level FROM red=>2, blue=>3,
     ENDCASE=>4;
a,b:CoordL←cell.pos;
IF signal.circuit=0 OR testList#NIL THEN Error;
SELECT signal.side FROM
      e=>a←[a.x+cell.sizeL.x-1, a.y+signal.offset];
      w=>a←[a.x, a.y+signal.offset];
      n=>a←[a.x+signal.offset, a.y+cell.sizeL.y-1];
      s=>a←[a.x+signal.offset, a.y];
      ENDCASE=>Error;
SELECT signal.side FROM
   e,w=>b←[a.x+1,a.y+width]; ENDCASE=>b←[a.x+width,a.y+1];
start←[a,b,both,TRUE,signal.circuit];
RETURN[@start];
END;

FollowCircuit:PROCEDURE[sil:SiliconPtr]=BEGIN
VerifyCellContact:PROCEDURE[cell:CellPtr]=BEGIN
  IF ~Overlap2[cell,this] THEN RETURN ELSE BEGIN
  onE:BOOLEAN=cell.pos.x+cell.sizeL.x=this.pos.x;
  onW:BOOLEAN=cell.pos.x=this.pos2.x;
  onN:BOOLEAN=cell.pos.y+cell.sizeL.y=this.pos.y;
  onS:BOOLEAN=cell.pos.y=this.pos2.y;
  FOR sl:SignalListPtr←cell.signals,sl.t UNTIL sl=NIL DO
    signal:SignalPtr=sl.h;
    IF signal.circuit=this.circuit THEN BEGIN
      yAll:BOOLEAN=cell.pos.y+signal.offset IN [this.pos2.y-4..this.pos.y];
      xAll:BOOLEAN=cell.pos.x+signal.offset IN [this.pos2.x-4..this.pos.x];
      SELECT signal.side FROM
        e=>IF onE  AND yAll THEN RETURN;
        w=>IF onW AND yAll THEN RETURN;
        n=>IF onN  AND xAll THEN RETURN;
        s=>IF onS AND xAll THEN RETURN;
      ENDCASE=>{Return[]; ShowString["short to cell"L]};
      END;
    ENDLOOP;
  END; END;
this:SiliconPtr;
circuit:Circuit←sil.circuit;
old:BOOLEAN←SetBit[circuit];
Push[sil];
UNTIL (this←Pop[])=NIL DO
  IF this.circuit#circuit THEN Error;
  FOR sl:SiliconListPtr←layout,sl.t UNTIL sl=NIL DO
    s:SiliconPtr=sl.h;
    IF s=this OR s.circuit=circuit AND s.solid OR ~Overlap[s,this]
       THEN LOOP;
    IF s.circuit#0 AND s.circuit#circuit THEN
      {LogWire[this," shorted to "]; ShowWire[s]; LOOP};
    s.circuit←circuit;
    s.solid←solid;--set by Overlap
    IF solid AND old THEN {LogWire[this," open"]; old←FALSE};
    IF solid THEN Push[s];
    ENDLOOP;
  EnumerateCells[VerifyCellContact];
  ENDLOOP;
END;

Push:PROCEDURE[a:SiliconPtr]=BEGIN
t:SiliconListPtr←AllocateList[];
t↑←[a,testList];
testList←t;
END;

Pop:PROCEDURE RETURNS[a:SiliconPtr]=BEGIN
new:SiliconListPtr←testList;
IF new=NIL THEN RETURN[NIL];
a←new.h;
testList←new.t;
FreeList[new];
END;

Overlap:PROCEDURE[a,b:SiliconPtr] RETURNS[BOOLEAN]=BEGIN
dx,dy:Lambda;
width:Lambda=SELECT a.level FROM
  red=>IF b.level=blue THEN 0 ELSE 2,
  blue=>IF b.level=red THEN 0 ELSE 3,
  ENDCASE=>IF b.level=red THEN 2 ELSE 3;
IF width=0 THEN RETURN[FALSE];
IF a.pos.x>=b.pos2.x+width THEN RETURN[FALSE];
IF a.pos.y>=b.pos2.y+width THEN RETURN[FALSE];
IF b.pos.x>=a.pos2.x+width THEN RETURN[FALSE];
IF b.pos.y>=a.pos2.y+width THEN RETURN[FALSE];
dx←MIN[a.pos2.x,b.pos2.x]-MAX[a.pos.x,b.pos.x];
dy←MIN[a.pos2.y,b.pos2.y]-MAX[a.pos.y,b.pos.y];
solid←dx>=width AND dy>=0  OR dy>=width AND dx>=0;
RETURN[TRUE];
END;

Overlap2:PROCEDURE[a:CellPtr,b:SiliconPtr] RETURNS[BOOLEAN]=BEGIN
width:Lambda=IF b.level=red THEN 2 ELSE 3;
IF a.pos.x>=b.pos2.x+width THEN RETURN[FALSE];
IF a.pos.y>=b.pos2.y+width THEN RETURN[FALSE];
IF b.pos.x>=a.pos.x+a.sizeL.x+width THEN RETURN[FALSE];
IF b.pos.y>=a.pos.y+a.sizeL.y+width THEN RETURN[FALSE];
RETURN[TRUE];
END;

SetBit:PROCEDURE[c:[0..1600)]RETURNS[x:BOOLEAN]=BEGIN
index:[0..100)←c/16;
word:Ugly←circuitsTested[index];
SELECT c MOD 16 FROM
  0=>{x←word.a; word.a←TRUE};
  1=>{x←word.b; word.b←TRUE};
  2=>{x←word.c; word.c←TRUE};
  3=>{x←word.d; word.d←TRUE};
  4=>{x←word.e; word.e←TRUE};
  5=>{x←word.f; word.f←TRUE};
  6=>{x←word.g; word.g←TRUE};
  7=>{x←word.h; word.h←TRUE};
  8=>{x←word.i; word.i←TRUE};
  9=>{x←word.j; word.j←TRUE};
  10=>{x←word.k; word.k←TRUE};
  11=>{x←word.l; word.l←TRUE};
  12=>{x←word.m; word.m←TRUE};
  13=>{x←word.n; word.n←TRUE};
  14=>{x←word.o; word.o←TRUE};
  15=>{x←word.p; word.p←TRUE};
  ENDCASE=>Error;
circuitsTested[index]←word;
END;

first:BOOLEAN←TRUE;

LogWire:PROCEDURE[w:SiliconPtr,s:STRING]=BEGIN
IF NOT (w.pos2.y-w.pos.y=1 OR w.pos2.x-w.pos.x=1)
  AND first THEN {first←FALSE; CheckerComplaint};
Return[];
ShowWire[w];
ShowString[s];
END;

END.

Time: (layout+signals) squared
IDs: about 60
Space: about 100
CallStructure: Checklayout(GetSeed FollowCircuit(Push Pop SetBit Overlap
      VerifyCellContact(Overlap2)))
   everybody uses LogWire