DIRECTORY  CD, CoreFlat, RefTab, SoftHdwBasics, SoftHdwAssembly, SoftHdwCompiler, TerminalIO;

SoftHdwRouterOutput: CEDAR PROGRAM
IMPORTS RefTab, SoftHdwAssembly, SoftHdwBasics
EXPORTS SoftHdwCompiler
= BEGIN OPEN SoftHdwCompiler;

MarkedPlaceAndRoute: PUBLIC PROC [placement: Placement, route: RefTab.Ref, incompleteNetEnds: NetEndList, sizes: ArrayPosition] = {
ColorPosition: PROC [node: Node] = TRUSTED {
position: SoftHdwAssembly.ArrayPosition _ NEW[SoftHdwAssembly.ArrayPositionRec];
position^ _ node.position;
positions _ CONS[[red, position], positions];
};
program: SoftHdwAssembly.Program _ ProgramFromPlaceAndRoute[placement, route, incompleteNetEnds];
design: CD.Design _ SoftHdwAssembly.PrintAndDraw[sizes, program];
positions: SoftHdwAssembly.ColoredArrayPositions _ NIL;
FOR ine: NetEndList _ incompleteNetEnds, ine.rest UNTIL ine=NIL DO
ColorPosition[ine.first.source];
FOR nl: Nodes _ ine.first.destinations, nl.rest UNTIL nl=NIL DO
ColorPosition[nl.first];
ENDLOOP;
ENDLOOP;
SoftHdwAssembly.HighlightDesign[design, sizes, positions];
};

ProgramFromPlaceAndRoute: PUBLIC PROC [placement: Placement, route: RefTab.Ref, incompleteNetEnds: NetEndList] RETURNS [program: SoftHdwAssembly.Program] = {
ParsePlacement: RefTab.EachPairAction = {
p: Primitive _ NARROW[key];
pa: PrimitiveAssignment _ NARROW[val];
grain: INT;
position^ _ pa.position^;
position.type _ InputEnabled;
FOR index: CARDINAL IN [0..pa.size) DO
grain _ pa[index];
SELECT position.orientation FROM
Vertical =>  position.grain.y _ grain;
Horizontal => position.grain.x _ grain;
ENDCASE => ERROR;
program.tiles _ CONS[CopyPosition[position], program.tiles];
ENDLOOP;
IF p.flatClock#NIL THEN {
flop: ArrayPosition _ CopyPosition[pa.position];
flop.type _ FlipFlop;
program.tiles _ CONS[flop, program.tiles]; 
};
};
ParseRoute: RefTab.EachPairAction = {
path: Path _ NARROW[val];
ParsePath[path]
};
ParsePath: PROC [path: Path] = {
pos, nextPos: ArrayPosition;
FOR index: CARDINAL IN [0..path.size) DO
pos _ path[index];
IF index<path.size-1 THEN {
nextPos _ path[index+1];
CreateArc[pos, nextPos];
};
ENDLOOP;
IF path.subPaths#NIL THEN FOR index: CARDINAL IN [0..path.subPaths.size) DO
ParsePath[path.subPaths[index]];
pos _ path[path.size-1];
nextPos _ path.subPaths[index][0];
CreateArc[pos, nextPos];
ENDLOOP;
};
CreateArc: PROC [from, to: ArrayPosition] = {
position^ _ from^;
nextPosition^ _ to^;
position.type _ SelectArcType[from, to];
position.minorArray.x _ MAX[from.minorArray.x, to.minorArray.x];
position.minorArray.y _ MAX[from.minorArray.y, to.minorArray.y];
IF position.type=InputEnabled THEN {
position.orientation _ to.orientation;
SELECT from.orientation FROM 
Vertical => {
position.grain.x _ from.grain.x;
position.grain.y _ to.grain.y };
Horizontal => { 
position.grain.y _ from.grain.y;
position.grain.x _ to.grain.x };
ENDCASE => ERROR; };
program.tiles _ CONS[CopyPosition[position], program.tiles];
};
position: ArrayPosition _ NEW[ArrayPositionRec];
nextPosition: ArrayPosition _ NEW[ArrayPositionRec];
program _ SoftHdwAssembly.Create[NIL, NIL, MinorArray, NIL];
[] _ RefTab.Pairs[placement.positions, ParsePlacement];
[] _ RefTab.Pairs[route, ParseRoute];
FixUpPathInversions[placement, route, program];
};

IsPathSegmentInverting: PROC [from, to: ArrayPosition] RETURNS [invert: BOOL] ~{
invert _ SELECT from.type FROM
Input => SELECT to.type FROM
Output => TRUE,
ENDCASE => ERROR,
Interchip => ERROR,
Long => SELECT to.type FROM
Input => FALSE,
ENDCASE => ERROR,
Output => SELECT to.type FROM
Input => FALSE,
Long => FALSE,
LeftDown => TRUE,
RightUp => TRUE,
ENDCASE => ERROR,
LeftDown => SELECT to.type FROM
Input => FALSE,
LeftDown => TRUE,
ENDCASE => ERROR,
RightUp => SELECT to.type FROM
Input => FALSE,
RightUp => TRUE,
ENDCASE => ERROR,
ENDCASE => ERROR;
};

SelectArcType: PROC [from, to: ArrayPosition] RETURNS [type: NodeType] ~{
type _ SELECT from.type FROM
Input => SELECT to.type FROM
Output => IF (from.orientation=to.orientation) THEN ParallelInput ELSE  InputEnabled,
ENDCASE => ERROR,
Interchip => ERROR,
Long => SELECT to.type FROM
Input => LToI,
ENDCASE => ERROR,
Output => SELECT to.type FROM
Input => IF ((from.minorArray.x=to.minorArray.x) AND from.orientation=Horizontal) 
OR ((from.minorArray.y=to.minorArray.y) AND from.orientation=Vertical) THEN ORUToI ELSE OLDToI,
Long => ORUToL,
LeftDown => ORUToLD,
RightUp => OLDToRU,
ENDCASE => ERROR,
LeftDown => SELECT to.type FROM
Input => LDToI,
LeftDown => LDToLD,
ENDCASE => ERROR,
RightUp => SELECT to.type FROM
Input => RUToI,
RightUp => RUToRU,
ENDCASE => ERROR,
ENDCASE => ERROR;
};

CopyPosition: PROC [pos: ArrayPosition] RETURNS [newpos: ArrayPosition] ~ {
newpos _ NEW[ArrayPositionRec _ pos^]; };

FixUpPathInversions: PROC [placement: Placement, route: RefTab.Ref, program: SoftHdwAssembly.Program] ~ {
flatCell: FlatCell _ placement.flatCell;
EachWire: RefTab.EachPairAction ~ {
wire: CoreFlat.FlatWire _ NARROW[key];
primitive: Primitive _ NARROW[val];
primitiveAssignment: PrimitiveAssignment _ NARROW[RefTab.Fetch[placement.positions, primitive].val];
primitivePosition: ArrayPosition _ primitiveAssignment.position;
pathInverted, outputInverted, inputInverted, totalInversion, completed: BOOL;
FOR index: CARDINAL IN [0..primitive.size) DO
inputGrainIndex: CARDINAL _ primitiveAssignment[index];
polarizedInput: PolarizedInputRec _ primitive[index];
source: Primitive _ polarizedInput.source;
path: Path;
IF source#NIL THEN {
path _ NARROW[RefTab.Fetch[route, source.flatOutput].val];
IF path=NIL THEN RETURN;
inputPos^ _ primitivePosition^;
SELECT primitivePosition.orientation FROM 
Horizontal => { inputPos.orientation _ Vertical;
inputPos.grain.y _ 0; 
inputPos.grain.x _ inputGrainIndex};
Vertical => { inputPos.orientation _ Horizontal;
inputPos.grain.x _ 0;
inputPos.grain.y _ inputGrainIndex};
ENDCASE => ERROR;
[completed, pathInverted] _ IsPathInverting[path, inputPos];
inputInverted _ polarizedInput.negate;
outputInverted _ primitive.negateOutput;
totalInversion _ pathInverted#(inputInverted#outputInverted);
IF totalInversion THEN ProgramInverterForInput[inputPos, program];
};
ENDLOOP;
};
inputPos: ArrayPosition _ NEW[ArrayPositionRec];
[] _ RefTab.Pairs[flatCell.wires, EachWire];
};

ProgramInverterForInput: PROC [inputPos: ArrayPosition, program: SoftHdwAssembly.Program] ~ {
position: ArrayPosition _ CopyPosition[inputPos];
position.type _ Inverter;
program.tiles _ CONS[position, program.tiles]; 
};

IsPathInverting: PROC [path: Path, inputPos: ArrayPosition] RETURNS [arrived: BOOL _ FALSE, invert: BOOL _ FALSE] ~ {
TracePath: PROC [path: Path, dest: ArrayPosition, inversion: BOOL]  RETURNS [BOOL, BOOL] ~ {
FOR index: CARDINAL IN [0..path.size) DO
position _ path[index];
IF SoftHdwBasics.ArrayPositionEqual[position, inputPos] THEN RETURN[TRUE, inversion];
IF index<path.size-1 THEN {
nextPosition _ path[index+1];
inversion _ inversion#IsPathSegmentInverting[position, nextPosition];
};
ENDLOOP;
IF path.subPaths = NIL THEN RETURN[FALSE, inversion] ELSE
 { FOR index: CARDINAL IN [0..path.subPaths.size) DO
foundDest, subPathInverts: BOOL;
[foundDest, subPathInverts] _ TracePath[path.subPaths[index], inputPos, FALSE];
position _ path[path.size-1];
nextPosition _ path.subPaths[index][0];
IF foundDest THEN 
 RETURN[TRUE, inversion#(subPathInverts#IsPathSegmentInverting[position, nextPosition])];
ENDLOOP; };
RETURN[FALSE,FALSE];
};
position: ArrayPosition;
nextPosition: ArrayPosition;
[arrived, invert] _ TracePath[path, inputPos, FALSE];
};

NthPath: PUBLIC PROC [route: RefTab.Ref, nth: INT] RETURNS [path: Path _ NIL]~ {
EachPath: RefTab.EachPairAction ~ {
IF index = nth THEN path _  NARROW[val];
index _ index+1; };
index: INT _ 0;
[] _ RefTab.Pairs[route, EachPath];
};

MakeColoredPositionPath: PUBLIC PROC [pathlist: ArrayPositions] RETURNS [SoftHdwAssembly.ColoredArrayPositions] ~ {
cpathlist: SoftHdwAssembly.ColoredArrayPositions _ NIL;
FOR poslist: ArrayPositions _ pathlist, poslist.rest WHILE poslist#NIL DO
cpathlist _ CONS[[color: red, position: poslist.first], cpathlist];
ENDLOOP;
RETURN[cpathlist];
};

ShowPath: PUBLIC PROC [design: CD.Design, sizes: ArrayPosition, route: RefTab.Ref, nthPath: INT] ~ {
HighlightPath[design, sizes, NthPath[route, nthPath]]; };


HighlightPath: PUBLIC PROC [design: CD.Design, sizes: ArrayPosition, path: Path] ~ {
pathList: ArrayPositions;
posList: SoftHdwAssembly.ColoredArrayPositions;
pathList _ FlattenPath[path];
posList _ MakeColoredPositionPath[pathList];
SoftHdwAssembly.HighlightDesign[design, sizes, NIL];
SoftHdwAssembly.HighlightDesign[design, sizes, posList, NIL,  "Critical Path"];
};

FlattenPath: PUBLIC PROC [path: Path] RETURNS [pathlist: ArrayPositions _ NIL] ~ {
position: ArrayPosition _ NEW[ArrayPositionRec];
nextPosition: ArrayPosition _ NEW[ArrayPositionRec];
TracePath: PROC [path: Path] = {
pos, nextPos: ArrayPosition;
FOR index: CARDINAL IN [0..path.size) DO
pos _ path[index];
pathlist _ CONS[CopyPosition[pos], pathlist];
IF index<path.size-1 THEN {
nextPos _ path[index+1];
CreateArc[pos, nextPos];
};
ENDLOOP;
IF path.subPaths#NIL THEN FOR index: CARDINAL IN [0..path.subPaths.size) DO
TracePath[path.subPaths[index]];
pos _ path[path.size-1];
nextPos _ path.subPaths[index][0];
CreateArc[pos, nextPos];
ENDLOOP;
};
CreateArc: PROC [from, to: ArrayPosition] = {
position^ _ from^;
nextPosition^ _ to^;
position.type _ SelectArcType[from, to];
position.minorArray.x _ MAX[from.minorArray.x, to.minorArray.x];
position.minorArray.y _ MAX[from.minorArray.y, to.minorArray.y];
IF position.type=InputEnabled THEN {
position.orientation _ to.orientation;
SELECT from.orientation FROM 
Vertical => {
position.grain.x _ from.grain.x;
position.grain.y _ to.grain.y };
Horizontal => { 
position.grain.y _ from.grain.y;
position.grain.x _ to.grain.x };
ENDCASE => ERROR; };
pathlist _ CONS[CopyPosition[position], pathlist];
};
TracePath[path];
};

END.
Š
SoftHdwRouterOutput.mesa
Copyright Σ 1988 by Xerox Corporation.  All rights reserved.
Minsky, July 26, 1989 10:07:25 am PDT
Barth, September 6, 1989 12:43:08 pm PDT

(... incompleteNetEnds is not yet used, but should be used to flag dangling wires. )
...Creates  a routing tile (or programming tile) for the arc between the from and to nodes.
Assign the ownership of routing tile to the rightmost or topmost minor array.
InputEnabled tile inherits orientation from Output node.
Look up the correct routing tile type to join the two nodes, from and to.
Look up the correct routing tile type to join the two nodes, from and to.
An Output to Input is either an ORUToI or else OLDToI
NodeType: TYPE =  {OToP, RUToP, LDToP, LToP, PToI, PToRU, PToLD, PToL, ORUToI, LDToLD, OLDToI, ORUToL, Tristate, RUToRU, ORUToLD, LDToI, OLDToRU, LToI, RUToI, Inverter, FlipFlop, ParallelInput, InputEnabled, RAMEven, RAMOdd, Master, Input, Interchip, Long, Output, LeftDown, RightUp};

Calculates the parity of each path destination input, and adds an inverter on the input if needed.
For each primitive, find the parity of the path to its inputs.
Iterate over all the inputs to this primitive, and trace the path from their source
XOR
Places an inverter tile in the program at the specified location
Traces a path recursively until it hits inputPos. Combines all inversions along the way
Did we find the inputPos on this path?
If the destination was never found, then that means we are using an incomplete path.
Maybe we should print something, or flag an error... 
Returns the Nth path in the table
Takes a flattened path, and returns it colored red.
Highlights a  path. 
returns a flattened list of array positions
Creates  a routing tile (or programming tile) for the arc between the from and to nodes.
Assign the ownership of routing tile to the rightmost or topmost minor array.
InputEnabled tile inherits orientation from Output node.
Κέ™š
œ™Icode™<Kš
œ%™%K™(K™—KšΟk	œT˜]K˜šΟnœœ
˜"Kšœ'˜.Kšœ˜Kšœœ˜—K˜šžœœc˜ƒ
šž
œœœ˜,Kšœ*œ#˜PKš
œ˜Kšœœ˜-K˜—Kš
œa˜aKšœœ7˜AKšœ3œ
˜7šœ/œœ
˜BKš
œ ˜ šœ-œœ
˜?Kš
œ˜Kšœ
˜—Kšœ
˜—Kš
œ:˜:K˜K˜—šžœœJœ'˜
Kš
œT™Tšžœ˜)Kšœœ˜Kšœœ˜&Kšœ˜K˜Kš
œ˜šœœ
œ˜&Kš
œ˜šœ˜ Kš
œ&˜&Kš
œ'˜'Kšœœ
˜—Kšœœ(˜<Kšœ
˜—šœ
œ
œ˜Kš
œ0˜0Kš
œ˜Kšœœ˜+K˜—K˜—šž
œ˜%Kšœ
œ˜Kš
œ˜K˜—šž	œœ˜ K˜šœœ
œ˜(Kš
œ˜šœœ˜Kš
œ˜Kš
œ˜K˜—Kšœ
˜—š
œœ
œ
œœ
œ˜KKš
œ ˜ Kš
œ˜Kš
œ"˜"Kš
œ˜Kšœ
˜—K˜—šž	œœ˜-K™[Kš
œ˜K˜Kš
œ(˜(K™MKšœœ%˜@Kšœœ%˜@šœ˜$K™8Kš
œ&˜&šœœ
˜š
œ
˜
Kš
œ ˜ Kš
œ ˜ —š
œ˜Kš
œ ˜ Kš
œ ˜ —Kšœœ
˜——Kšœœ(˜<K˜—Kšœœ˜0Kšœœ˜4Kšœ!œœœ˜<Kš
œ7˜7Kš
œ%˜%K˜/K˜K˜—šžœœœ
œ˜PK™Išœ	œ˜šœ	œ	˜Kšœ
œ
˜Kšœ˜—Kšœ
œ
˜šœœ	˜Kšœ	œ
˜Kšœ˜—šœ
œ	˜Kšœ	œ
˜Kšœœ
˜Kšœœ
˜Kšœœ
˜Kšœ˜—šœœ	˜Kšœ	œ
˜Kšœœ
˜Kšœ˜—šœœ	˜Kšœ	œ
˜Kšœœ
˜Kšœ˜—Kšœœ
˜—K˜K˜—šž
œœœ˜IK™Išœœ˜šœ	œ	˜Kšœ
œ#œœ˜UKšœ˜—Kšœ
œ
˜šœœ	˜Kš
œ˜Kšœ˜—šœ
œ	˜Kš
œ5™5šœ	œ&œ˜RKšœ&œœœ˜_—K˜K˜K˜Kšœ˜—šœœ	˜Kš
œ˜Kš
œ˜Kšœ˜—šœœ	˜Kš
œ˜Kš
œ˜Kšœ˜—Kšœœ
˜—K˜K˜—šœ
œŽ™œK™—šžœœœ˜KKšœ	œ˜)K˜—šžœœ)
œ&˜iK™bKš
œ(˜(šžœ˜#K™>Kšœœ˜&Kšœœ˜#Kšœ+œ3˜dKš
œ@˜@KšœH˜MK™Sšœœ
œ˜-Kšœœ˜7Kš
œ5˜5Kš
œ*˜*Kš
œ˜šœœ
˜Kšœœ-˜:Kšœœ
œ
œ
˜Kš
œ˜šœœ
˜*š
œ0˜0Kš
œ˜Kš
œ$˜$—š
œ0˜0Kš
œ˜Kš
œ$˜$—Kšœœ
˜—Kš
œ<˜<Kšœ
œ
œ˜&Kš
œ(˜(K™Kš
œ=˜=Kšœœ,˜BKšœ

˜—Kšœ
˜—K˜—Kšœœ˜0Kš
œ,˜,K˜K˜—šžœœ@˜]K™@Kš
œ1˜1Kš
œ˜Kšœœ˜/K˜K˜—šžœœ'œœœ
œœ˜uKš
œW™Wšž	œœ.œœœ
œ˜\šœœ
œ˜(Kš
œ˜Kšœ6œ
œ
œ
˜Ušœœ˜Kš
œ˜Itextš
œE˜EK˜—Kšœ
˜—K™&Kšœœ
œ
œ
œ
˜9šœœœ
œ˜4Kšœœ
˜ KšœHœ˜OKš
œ˜Kš
œ'˜'Kšœœ
˜Kšœ
œ
œM˜YKšœ˜—K™TK™5Kšœ
œ
œ˜K˜—Kš
œ˜Kš
œ˜Kšœ.œ
˜5K˜K˜—šžœœ
œœœœ˜PK™!šžœ˜#Kšœ
œ	œ˜(K˜—Kšœœ˜Kš
œ#˜#K˜K˜—šžœœ
œœ,˜sK™3Kšœ3˜7šœ2œ	˜IKšœœ3˜CKšœ
˜—Kšœ˜K˜—K˜š
žœœ
œ
œ;œ˜dKš
œ9˜9—˜K˜—šž
œœ
œ
œ.˜TK™K˜Kš
œ/˜/K˜Kš
œ,˜,Kšœ/œ˜4Kšœ8œ˜OKš
œ˜K˜—š
žœœ
œœœ˜RK™+Kšœœ˜0Kšœœ˜4šž	œœ˜ K˜šœœ
œ˜(Kš
œ˜Kšœœ˜-šœœ˜Kš
œ˜Kš
œ˜K˜—Kšœ
˜—š
œœ
œ
œœ
œ˜KKšž	œ˜ Kš
œ˜Kš
œ"˜"Kš
œ˜Kšœ
˜—K˜—šž	œœ˜-K™XKš
œ˜K˜Kš
œ(˜(K™MKšœœ%˜@Kšœœ%˜@šœ˜$K™8Kš
œ&˜&šœœ
˜š
œ
˜
Kš
œ ˜ Kš
œ ˜ —š
œ˜Kš
œ ˜ Kš
œ ˜ —Kšœœ
˜——Kšœœ#˜2K˜—Kš
œ˜K˜K˜—Kšœ
˜—…—&†9ν