--routedefs.mesa

DIRECTORY  IODefs;

RouteDefs:DEFINITIONS = BEGIN

--ROUTEDEFS

Circuit:TYPE=INTEGER;
RunNo:TYPE=INTEGER;
bigRun:RunNo=10000;
EventNo:TYPE=INTEGER;
ChannelNo:TYPE=INTEGER;
InterNo:TYPE=INTEGER;
Lambda:TYPE=INTEGER;
bigLambda:Lambda=32000;
NetNo:TYPE=INTEGER;
JoinType:TYPE=INTEGER;
InterType:TYPE=INTEGER;
noOffset:INTEGER=1000;

CoordL:TYPE=RECORD[x,y:INTEGER←0]; --in lambda
CoordC:TYPE=RECORD[x,y:INTEGER←0]; --in events
nilG:Link=[];
outOfSight:CoordL=[-20,-20];

BoolPtr:TYPE=POINTER TO BOOLEAN;
ProcedureDescriptor:TYPE=RECORD[doit,printIt:PROCEDURE,enabler:BoolPtr];
Where:TYPE={top,bottom,left,right}←top;
What:TYPE={blue,red,both};
Level:TYPE={red,blue};
ConnKind:TYPE={none,left,right,tee,edge}←none;
Side:TYPE={n,s,e,w,x}←x;
Turn:TYPE={se,sw,ne,nw,hor,vert}; --relative to inter
RectKind:TYPE={none,cell,channel,inter,culDeSacR,culDeSacL,box,bend5,bend9,bend6,bend10,wallL,wallR};
Orient:TYPE={unknown,hor,vert,inter,bend};
Huggers:TYPE=RECORD[ch,n,s,e,w:Side←x,valid:BOOLEAN←FALSE];
Levelers:TYPE=RECORD[n,s,e,w:[0..6]←0];
Margins:TYPE=RECORD[n,s,e,w:[0..16)←3];

--LOOK HERE !!

Problem:TYPE=RECORD[cells:CellListPtr←NIL, chipSize:CoordL←[],
  wirelist:NetListPtr←NIL];

Rectangle:TYPE=RECORD[
  pos:CoordL,                   --Rectangle.CreateRectangle, Rectless.Compress
  sizeL:CoordL,                 --Rectangle.CreateRectangle, Rectless.Compress
  l:Link←[],                    --Rectless.CreateSecondaryLists
  n,s,e,w:RectanglePtr←NIL,     --Rectless.Compress
  nw,sw,ne,se,en,wn,es,ws:Lambda←0,
  nSource,sSource,              --Rectangle.CreateRectangle
  wSource,eSource:BOOLEAN←FALSE,--Rectangle.CreateRectangle
  channelNo:ChannelNo←0,        --Rectangle.CreateRectangle
  sizeC:CoordC,                 --Rectless.ComputeSizeC
  junction:JunctionPtr←NIL,     --Rectless.CreateSecondaryLists
  events:EventListPtr←NIL,      --Rectangle.AddEvent, Rectless.Compress
  orient:Orient←unknown,        --Rectless.MarkNatureAndOrientAndWhere
  nature:RectKind←none,         --Rectless.MarkNatureAndOrientAndWhere
  runs:RunListPtr←NIL,          --Runs.AddRun
  conns:ConnListPtr←NIL,
  levelers:Levelers,            --Rectless.*MakeLevelers*
  margins:Margins,
  used:INTEGER←0,
  avail:INTEGER←0,
  usedCircuit:INTEGER←0
  ];

Event:TYPE=RECORD[
  index:INTEGER←-1,              --Rectless.SetEventNumbers
  circuit:Circuit←0,             --Rectangle.AddEvent
  where:Where,                   --Rectless.xxx
  side:Side,                     --Rectangle.AddEvent
  level:What←both,
  offset:Lambda←noOffset,        --Rectangle.AddEvent, Rectless.AdjustOffset
  net:NetPtr←NIL,                --Rectangle.AddEvent
  opposite:EventPtr←NIL,         --Rectless.SetEventNumbers
  next,prev:EventPtr←NIL,        --Rectless.SetnextAndPrevEvents
  conn:ConnPtr←NIL               --Conn.MakeEdgeConn
  ];

--  Source1 = Runs.MakeRun, Runs.FixUpJunctionWithInters, Crosses.SplitCon

Run:TYPE=RECORD[
  circuit:Circuit←0,             --Source1
  run:RunNo←0,                   --Runs.AssignCulDeSac/TopDown/BottomUpRunNo
  start,end:EventNo←0,           --Source1
  startOff,endOff:INTEGER←0,     --Crosses.SetRunOffset
  chan:RectanglePtr←NIL,         --Source1
  path:PathPtr←NIL,              --Runs.MakeRun/FixUpJunctionWithInters
  order:BOOLEAN←FALSE,
  stU,stD,stL:BOOLEAN←FALSE,     --Runs.MakeRun/FixUpJunctionWithInters,
  endU,endD,endL:BOOLEAN←FALSE,  --Runs.MakeRun/FixUpJunctionWithInters
  startOffX,endOffX:Lambda←0,
  startConn,endConn:ConnPtr←NIL  --Conn.Make..Conn, Crosses.SplitCon
  ];

-- Crosses.SplitConn copies a whole conn, as well as changing fields

Conn:TYPE=RECORD[
  circuit:Circuit←0,             --Conn.Make..Conn
  start,end:RunNo←0,             --Conn.Make..Conn, Crosses.Split
  event:EventNo←0,               --Conn.Make..Conn
  level:Level←red,               --Conn.FixJogColor
  startKind,endKind:ConnKind,    --Crosses.InitConn, Crosses.Split
  offset:INTEGER←noOffset,       --Conn.Offset..
  eventPtr:EventPtr←NIL,         --Conn.Make..Conn
  lambdaX:Lambda←-1,
  startRun,endRun:RunPtr←NIL,    --Conn.Make..Conn
  closeS,closeE:BOOLEAN←FALSE    --Conn.FixJogColor
  ];

Cell:TYPE=RECORD[sizeL,pos:CoordL←[], signals:SignalListPtr←NIL,
    cellNo:INTEGER←0];
Signal:TYPE=RECORD[name:STRING←NIL,circuit:Circuit←0,side:Side←n,
    level:What←both,offset:Lambda←0,net:NetPtr←NIL];
Net:TYPE=RECORD[number:Circuit←0,name:STRING←NIL,netNo:NetNo←0];
Link:TYPE=RECORD[channel:RectanglePtr←NIL,inter:RectanglePtr←NIL];
Topology:TYPE=RECORD[one,two:RectanglePtr←NIL,oneToTwo:Side←e];
Path:TYPE=RECORD[n,s,e,w:PathPtr←NIL,
  channel:RectanglePtr←NIL, inter:RectanglePtr←NIL,
  index:EventPtr←NIL, pathNo:INTEGER←0, started:BOOLEAN←FALSE,
  circuit:Circuit←-1, wire:IWirePtr, huggers:Huggers←[]];
Pathway:TYPE=RECORD[circuit:Circuit←0,path:PathListPtr←NIL];
Silicon:TYPE=RECORD[pos,pos2:CoordL←[0,0],level:What←both,
  solid:BOOLEAN←FALSE, circuit:Circuit←0];
Junction:TYPE=RECORD[iwires:IWireListPtr←NIL,ne,nw,se,sw:Bridge←[], bridgeNS,bridgeEW:RunNo←0];
IWire:TYPE=RECORD[type:InterType←0,ey,wy,nx,sx:RunNo←-1,
  circuit:Circuit←-1,h:Huggers←[],be1,be2,bn1,bn2:BOOLEAN←FALSE,
  path:PathPtr];
Bridge:TYPE=RECORD[x,y:RunNo←-1,hor:BOOLEAN←TRUE];

--place and grid internal to Paths, here only for allocation

Place:TYPE=RECORD[pos:CoordL←[0,0],score:Lambda←0,circuit:Circuit←0,
  back,n,s,e,w:PlacePtr←NIL, perm:BOOLEAN←FALSE, done:BOOLEAN←FALSE,
  un,us,ue,uw:RectanglePtr←NIL];
Grid:TYPE=RECORD[a,b:PlacePtr←NIL,above,below:Link←nilG,hor,done,hi,lo:BOOLEAN←FALSE];



RectanglePtr:TYPE=LONG POINTER TO Rectangle←NIL;
ConnPtr:TYPE=LONG POINTER TO Conn←NIL;
EventPtr:TYPE=LONG POINTER TO Event←NIL;
RunPtr:TYPE=LONG POINTER TO Run←NIL;
CellPtr:TYPE=LONG POINTER TO Cell←NIL;
SignalPtr:TYPE=LONG POINTER TO Signal←NIL;
NetPtr:TYPE=LONG POINTER TO Net←NIL;
TopologyPtr:TYPE=LONG POINTER TO Topology←NIL;
PathPtr:TYPE=LONG POINTER TO Path←NIL;
PathwayPtr:TYPE=LONG POINTER TO Pathway←NIL;
PlacePtr:TYPE=LONG POINTER TO Place←NIL;
GridPtr:TYPE=LONG POINTER TO Grid←NIL;
SiliconPtr:TYPE=LONG POINTER TO Silicon←NIL;
JunctionPtr:TYPE=LONG POINTER TO Junction←NIL;
IWirePtr:TYPE=LONG POINTER TO IWire←NIL;

RectangleList:TYPE=RECORD[h:RectanglePtr,t:RectangleListPtr];
ConnList:TYPE=RECORD[h:ConnPtr,t:ConnListPtr];
EventList:TYPE=RECORD[h:EventPtr,t:EventListPtr];
RunList:TYPE=RECORD[h:RunPtr,t:RunListPtr];
CellList:TYPE=RECORD[h:CellPtr,t:CellListPtr];
SignalList:TYPE=RECORD[h:SignalPtr,t:SignalListPtr];
NetList:TYPE=RECORD[h:NetPtr,t:NetListPtr];
TopologyList:TYPE=RECORD[h:TopologyPtr,t:TopologyListPtr];
PathList:TYPE=RECORD[h:PathPtr,t:PathListPtr];
PathwayList:TYPE=RECORD[h:PathwayPtr,t:PathwayListPtr];
PlaceList:TYPE=RECORD[h:PlacePtr,t:PlaceListPtr];
GridList:TYPE=RECORD[h:GridPtr,t:GridListPtr];
SiliconList:TYPE=RECORD[h:SiliconPtr,t:SiliconListPtr];
IWireList:TYPE=RECORD[h:IWirePtr,t:IWireListPtr];

RectangleListPtr:TYPE=LONG POINTER TO RectangleList;
ConnListPtr:TYPE=LONG POINTER TO ConnList;
EventListPtr:TYPE=LONG POINTER TO EventList;
RunListPtr:TYPE=LONG POINTER TO RunList;
CellListPtr:TYPE=LONG POINTER TO CellList;
SignalListPtr:TYPE=LONG POINTER TO SignalList;
NetListPtr:TYPE=LONG POINTER TO NetList;
TopologyListPtr:TYPE=LONG POINTER TO TopologyList;
PathListPtr:TYPE=LONG POINTER TO PathList;
PathwayListPtr:TYPE=LONG POINTER TO PathwayList;
PlaceListPtr:TYPE=LONG POINTER TO PlaceList;
GridListPtr:TYPE=LONG POINTER TO GridList;
SiliconListPtr:TYPE=LONG POINTER TO SiliconList;
IWireListPtr:TYPE=LONG POINTER TO IWireList;

CtlProc:TYPE=PROCEDURE RETURNS[INTEGER];


-- END OF TYPE DECLARATIONS

--Ctl Procs called by RouteControl

CreateCells:CtlProc;--RouteCells
CreateRectangles:CtlProc;--RouteRectangle
RectLess:CtlProc; --RouteRectLess
MakeLevelers:CtlProc; --RouteRectLess
CreateTopology:CtlProc;--RouteTopology
ChannelLevelRouting:CtlProc;--RoutePaths2
MakeHugs:CtlProc;--RouteHugs
RouteIntersections:CtlProc;--RouteInter
TheMainShowIsRouteRunsInChannels:CtlProc;--RouteRuns
InstallCrossChannelConnections:CtlProc;--RouteConn
InstallInternalContacts:CtlProc;--RouteCrosses
DoSilicon:CtlProc; --RouteSilicon
CheckLayout:CtlProc; --RouteChecker

--misc

ReducePath:PROCEDURE;--RoutePaths1
GetInput:PROCEDURE; --from RouteParse

--the following are all implemented in utilities

EnumerateChannels:PROCEDURE[PROCEDURE[RectanglePtr]];
EnumerateInters:PROCEDURE[PROCEDURE[RectanglePtr]];
EnumerateRectangles:PROCEDURE[PROCEDURE[RectanglePtr]];
EnumerateSignals:PROCEDURE[c:CellPtr,x:PROCEDURE[CellPtr,SignalPtr]];
EnumerateCells:PROCEDURE[PROCEDURE[CellPtr]];
EnumerateConns:PROCEDURE[RectanglePtr,PROCEDURE[RectanglePtr,ConnPtr]];
EnumerateEvents:PROCEDURE[RectanglePtr,PROCEDURE[RectanglePtr,EventPtr]];
EnumerateRuns:PROCEDURE[RectanglePtr,PROCEDURE[RectanglePtr,RunPtr]];
EnumerateAllSignals:PROCEDURE[PROCEDURE[CellPtr,SignalPtr]];
EnumerateAllRuns:PROCEDURE[c:PROCEDURE[RectanglePtr,RunPtr]];
EnumerateAllConns:PROCEDURE[call:PROCEDURE[RectanglePtr,ConnPtr]];
EnumerateSilicon:PROCEDURE[call:PROCEDURE[SiliconPtr]];



InitStorage,ReturnStorage:PROCEDURE;
AllocateList:PROCEDURE RETURNS[LONG POINTER];
AllocateRectangle:PROCEDURE RETURNS[RectanglePtr];
--AllocateChannel:PROCEDURE RETURNS[ChannelPtr];
AllocateEvent:PROCEDURE RETURNS[EventPtr];
AllocateRun:PROCEDURE RETURNS[RunPtr];
AllocateConn:PROCEDURE RETURNS[ConnPtr];
AllocateCell:PROCEDURE RETURNS[CellPtr];
AllocateSignal:PROCEDURE RETURNS[SignalPtr];
AllocateNet:PROCEDURE RETURNS[NetPtr];
AllocateTopology:PROCEDURE RETURNS[TopologyPtr];
AllocatePathway:PROCEDURE RETURNS[PathwayPtr];
AllocatePlace:PROCEDURE RETURNS[PlacePtr];
AllocatePath:PROCEDURE RETURNS[PathPtr];
AllocateGrid:PROCEDURE RETURNS[GridPtr];
AllocateSilicon:PROCEDURE RETURNS[SiliconPtr];
AllocateIWire:PROCEDURE RETURNS[IWirePtr];
AllocateJunction:PROCEDURE RETURNS[JunctionPtr];

FreeList:PROCEDURE[LONG POINTER];
FreePlace:PROCEDURE[PlacePtr];
FreePath:PROCEDURE[PathPtr];
FreePathway:PROCEDURE[PathwayPtr];
FreeGrid:PROCEDURE[GridPtr];
FreeRun:PROCEDURE[RunPtr];
FreeConn:PROCEDURE[ConnPtr];
FreeJunction:PROCEDURE[JunctionPtr];
FreeSilicon:PROCEDURE[SiliconPtr];

Return:PROCEDURE;
ShowLabel:PROCEDURE[STRING];
ShowString:PROCEDURE[STRING];
ShowChar:PROCEDURE[CHARACTER];
ShowDecimal:PROCEDURE[i:INTEGER,s:STRING←NIL];
ShowCircuit:PROCEDURE[c:Circuit] RETURNS[CHARACTER];
SameString:PUBLIC PROCEDURE[a,b:STRING] RETURNS[BOOLEAN];
WritePoint:PROCEDURE[x,y:INTEGER];
ShowPoint:PROCEDURE[s:STRING,x,y:INTEGER];
ShowWire:PROCEDURE[SiliconPtr];
Clear:PROCEDURE[s:STRING];
MakeType:PROCEDURE[n,e,s,w:BOOLEAN] RETURNS[InterType];

--from RouteMakeBlue

MakeBlue:PROCEDURE;

--from RouteSilicon

MakeBlueWire:PROCEDURE[hor:BOOLEAN,x,y,l:Lambda];
MakeRedWire:PROCEDURE[hor:BOOLEAN,x,y,l:Lambda];
MakeContact:PROCEDURE[x,y:Lambda];

--from RouteInter

InterSilicon:PROCEDURE[inter:RectanglePtr];
WhereIs:PROCEDURE[PathPtr,Side,RunNo] RETURNS[RunNo];

--from RouteChipmonkPlot

StartPlot,EndPlot:PROCEDURE;
PlotCell:PROCEDURE[CellPtr];
PlotBlueWire:PROCEDURE[hor:BOOLEAN,x,y,l:Lambda];
PlotRedWire:PROCEDURE[hor:BOOLEAN,x,y,l:Lambda];
PlotBlueRedContact:PROCEDURE[x,y:Lambda];
GetChipmonkString:PROCEDURE[result,prompt1:STRING,prompt2,prompt3:STRING←NIL];
Interrupt:ERROR; --raised by GetChipmonkString when push the rightmost
                 --unlabeled key, asking to abort;

allPaths:PathListPtr; --between paths1 and paths2

--all global variables are implemented in Utilities

channels:RectangleListPtr;    --Rectless.MakeSecondaryLists
problem:Problem;
example:INTEGER;
chipmonk,plot,print:BOOLEAN;
inters:RectangleListPtr;      --Rectless.MakeSecondaryLists
topology:TopologyListPtr;
paths:PathwayListPtr;
layout:SiliconListPtr;
rectangles:RectangleListPtr;  --Rectangle.NewRect


END.

Timing

key Parameters:  C: #cells   E: #events (sources) k1: # channels/circuit= 2
derived pars:
  RECT: # rectangles     = 4C
  CHAN: # channels       = 2C
  INTER: # intersections = 2C
  RUNS: # runs / channel = E/2C
  CONN: # conns / channel= E/C
  SILICON: # mask objects= 16E

Crosses: CHAN (CONN*CONN*RUN) = E (E/C)**2
Checker: (SILICON + ALLSIGNALS) squared = (17E)**2
Inter:   INTER (ALLPATHS + IWIRES) = E (4C+8)
MakeBlue: SILICON(SILICON + LIST(LIST+CELL)) = 16E(16E + *10(C+10))
Silicon: E(E/C+20)