Placement
MajorArrayStats: TYPE = REF MajorArrayStatsRec;
MajorArrayStatsRec:
TYPE =
RECORD [
combinatorials: NAT ← 0,
sequentials: NAT ← 0,
minors: NAT ← 0,
horizontals: NAT ← 0,
verticals: NAT ← 0,
netInputs: ARRAY InputCount OF NAT ← ALL[0]];
InputCount: TYPE = [0..20];
MajorArray: TYPE = REF MajorArrayRec;
MajorArrayRec:
TYPE =
RECORD [
root: Core.CellType ← NIL,
a, b: NAT ← 8,
c, d: INT ← 0,
minors: MinorArrays ← NIL,
lastMinor: MinorArrays ← NIL,
enumerationState: EnumerationState,
outputs: RefTab.Ref ← NIL];
EnumerationState: TYPE = {left, down, right, up};
MinorArrays: TYPE = LIST OF MinorArray;
MinorArray: TYPE = REF MinorArrayRec;
MinorArrayRec:
TYPE =
RECORD [
position: MajorGridPosition,
combinatorials: ARRAY Orientation OF CombinatorialElements ← ALL[NIL],
sequentials: SequentialElements ← NIL,
firstFreeSequentialElement: NAT ← 0];
MajorGridPosition:
TYPE =
RECORD [
x: CIndex ← 0,
y: DIndex ← 0];
CombinatorialElements: TYPE = REF CombinatorialElementsRec;
CombinatorialElementsRec:
TYPE =
RECORD [
elements: SEQUENCE size: CARDINAL OF CombinatorialElement]; -- ABIndex
CombinatorialElement: TYPE = REF CombinatorialElementRec;
CombinatorialElementRec:
TYPE =
RECORD [
c: CoreFlat.FlatCellType,
o: Label ← NIL,
i: Label ← NIL,
ip: InputPositions ← NIL]; -- inputs required for o
InputPositions:
TYPE =
LIST
OF ABIndex;
SequentialElements: TYPE = REF SequentialElementsRec;
SequentialElementsRec: TYPE = RECORD [elements: SEQUENCE size: CARDINAL OF SequentialElement]; -- AIndex
SequentialElement: TYPE = REF SequentialElementRec;
SequentialElementRec:
TYPE =
RECORD [
c: CoreFlat.FlatCellType,
i: Label ← NIL,
o: Label ← NIL];
Orientation: TYPE = {vertical, horizontal};
AIndex: TYPE = NAT;
BIndex: TYPE = NAT;
ABIndex: TYPE = NAT;
CIndex: TYPE = INT;
DIndex: TYPE = INT;
RopeList:
TYPE =
LIST
OF Rope.
ROPE;
Labels: TYPE = CoreFlat.FlatWires;
Label:
TYPE = CoreFlat.FlatWire;
SoftHdwCoreA, SoftHdwCoreF, and SoftHdwCoreK are not handled by the following classification.
primitiveTypes: SymTab.Ref ← SymTab.Create[];
PrimitiveType: TYPE = {ignore, equate, simple, xor2, a22o2i, a21o2i, ff, ffEn, tstDriver};
LoadPrimitiveTypes:
PROC = {
InsertList:
PROC [ropes: RopeList, type: PrimitiveType] = {
FOR rl: RopeList ← ropes, rl.rest
UNTIL rl=
NIL
DO
Insert[rl.first, type];
ENDLOOP;
};
Insert:
PROC [rope: Rope.
ROPE, type: PrimitiveType] = {
[] ← SymTab.Insert[primitiveTypes, rope, NEW[PrimitiveType ← type]];
};
InsertList[LIST["pd", "pdw", "puw"], ignore];
InsertList[LIST["inv", "invBuffer", "rec2V"], equate];
InsertList[LIST["and2", "and3", "and4", "nand2", "nand3", "nand4", "or2", "or3", "or4", "nor2", "nor3", "nor4"], simple];
InsertList[LIST["xor2", "xnor2"], xor2];
InsertList[LIST["a22o2i", "o22a2i"], a22o2i];
InsertList[LIST["a21o2i", "o21a2i"], a21o2i];
Insert["ff", ff];
Insert["ffEn", ffEn];
Insert["tstDriver", tstDriver];
};
PackArrayStats:
PROC [major: MajorArray]
RETURNS [stats: MajorArrayStats] = {
CountInput:
PROC [flatWire: CoreFlat.FlatWire] = {
IF flatWire#
NIL
THEN {
count: REF NAT ← NARROW[RefTab.Fetch[flatInputCounts, flatWire].val];
IF count=
NIL
THEN {
count ← NEW[NAT ← 0];
IF NOT RefTab.Insert[flatInputCounts, flatWire, count] THEN ERROR;
};
count^ ← count^ + 1;
};
};
BinInput: RefTab.EachPairAction = {
count: REF NAT ← NARROW[val];
index: InputCount ← IF count^>LAST[InputCount] THEN LAST[InputCount] ELSE count^;
stats.netInputs[index] ← stats.netInputs[index] + 1;
};
flatInputCounts: RefTab.Ref ← RefTab.Create[hash: CoreFlat.FlatWireHash, equal: CoreFlat.FlatWireEqual];
stats ← NEW[MajorArrayStatsRec];
FOR ml: MinorArrays ← major.minors, ml.rest
UNTIL ml=
NIL
DO
m: MinorArray ← ml.first;
stats.minors ← stats.minors + 1;
FOR aIndex: AIndex
IN [0..major.a)
DO
IF m.combinatorials[vertical].elements[aIndex].o#
NIL
THEN {
stats.combinatorials ← stats.combinatorials + 1;
stats.verticals ← stats.verticals + 1;
};
CountInput[m.combinatorials[vertical].elements[aIndex].i];
IF m.sequentials[aIndex]#NIL THEN CountInput[m.sequentials[aIndex].i];
ENDLOOP;
FOR bIndex: BIndex
IN [0..major.b)
DO
IF m.combinatorials[horizontal].elements[bIndex].o#
NIL
THEN {
stats.combinatorials ← stats.combinatorials + 1;
stats.horizontals ← stats.horizontals + 1;
};
CountInput[m.combinatorials[horizontal].elements[bIndex].i];
ENDLOOP;
stats.sequentials ← stats.sequentials + m.firstFreeSequentialElement;
ENDLOOP;
[] ← RefTab.Pairs[flatInputCounts, BinInput];
};
TriData: TYPE = REF TriDataRec;
TriDataRec:
TYPE =
RECORD [
count: NAT ← 0,
lastInput: CoreFlat.FlatWire ← NIL,
next: CoreFlat.FlatWire ← NIL];
PackArray:
PROC [root: Core.CellType, a, b:
NAT ← 8]
RETURNS [major: MajorArray] = {
Equate: CoreFlat.BoundFlatCellProc = {
EquateWire:
PROC [from, to: Rope.
ROPE] = {
fromWire: Core.Wire ← CoreOps.FindWire[cell.public, from];
flatFrom: CoreFlat.FlatWire ← CanonizeWire[bindings, flatCell, fromWire];
toWire: Core.Wire ← CoreOps.FindWire[cell.public, to];
flatTo: CoreFlat.FlatWire ← CanonizeWire[bindings, flatCell, toWire];
IF fromWire=NIL OR toWire=NIL THEN ERROR;
[] ← RefTab.Insert[equivalence, flatFrom, flatTo];
};
name: Rope.ROPE ← CoreOps.GetCellTypeName[cell];
primitiveType: REF PrimitiveType ← NARROW[SymTab.Fetch[primitiveTypes, name].val];
IF primitiveType=NIL THEN CoreFlat.NextBoundCellType[cell, target, flatCell, instance, index, parent, flatParent, data, bindings, Equate]
ELSE
SELECT primitiveType^
FROM
ff => EquateWire["NQ", "Q"];
equate => EquateWire["X", "I"];
tstDriver => {
x: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "X"];
i: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "I"];
triData: TriData ← NARROW[RefTab.Fetch[triDataTable, x].val];
IF triData=
NIL
THEN {
triData ← NEW[TriDataRec];
IF NOT RefTab.Store[triDataTable, x, triData] THEN ERROR;
};
triData.lastInput ← i;
triData.count ← triData.count + 1;
};
ENDCASE;
};
EquateTristate: RefTab.EachPairAction = {
x: CoreFlat.FlatWire ← NARROW[key];
triData: TriData ← NARROW[val];
IF triData.count<2 THEN [] ← RefTab.Insert[equivalence, x, triData.lastInput]
ELSE triData.next ← x;
};
Flatten: CoreFlat.BoundFlatCellProc = {
name: Rope.ROPE ← CoreOps.GetCellTypeName[cell];
primitiveType: REF PrimitiveType ← NARROW[SymTab.Fetch[primitiveTypes, name].val];
IF primitiveType=NIL THEN CoreFlat.NextBoundCellType[cell, target, flatCell, instance, index, parent, flatParent, data, bindings, Flatten]
ELSE
SELECT primitiveType^
FROM
ignore, equate => NULL;
simple => {
flatOutput: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "X"];
flatInputs: CoreFlat.FlatWires ← NIL;
Combinatorial.MakeCombinatorial[cell];
FOR wl: Core.Wires ← Combinatorial.GetTypedWires[cell, input], wl.rest
UNTIL wl=
NIL
DO
flatInput: CoreFlat.FlatWire ← CanonizeWire[bindings, flatCell, wl.first];
flatInput ← GetEquivalent[flatInput];
flatInputs ← CONS[flatInput, flatInputs];
ENDLOOP;
PackCombinatorialElement[major, flatCell, flatOutput, flatInputs];
};
xor2 => {
a: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "I-A"];
b: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "I-B"];
x: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "X"];
i1: CoreFlat.FlatWire ← CreateWire[flatCell];
i2: CoreFlat.FlatWire ← CreateWire[flatCell];
PackCombinatorialElement[major, flatCell, i1, LIST[a, b]];
PackCombinatorialElement[major, flatCell, i2, LIST[a, b]];
PackCombinatorialElement[major, flatCell, x, LIST[i1, i2]];
};
a22o2i => {
a: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "A"];
b: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "B"];
c: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "C"];
d: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "D"];
x: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "X"];
i1: CoreFlat.FlatWire ← CreateWire[flatCell];
i2: CoreFlat.FlatWire ← CreateWire[flatCell];
PackCombinatorialElement[major, flatCell, i1, LIST[a, b]];
PackCombinatorialElement[major, flatCell, i2, LIST[c, d]];
PackCombinatorialElement[major, flatCell, x, LIST[i1, i2]];
};
a21o2i => {
a: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "A"];
b: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "B"];
c: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "C"];
x: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "X"];
i: CoreFlat.FlatWire ← CreateWire[flatCell];
PackCombinatorialElement[major, flatCell, i, LIST[a, b]];
PackCombinatorialElement[major, flatCell, x, LIST[i, c]];
};
ff => {
d: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "D"];
q: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "Q"];
PackSequentialElement[major, flatCell, q, d];
};
ffEn => {
en: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "en"];
d: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "D"];
q: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "Q"];
i1: CoreFlat.FlatWire ← CreateWire[flatCell];
i2: CoreFlat.FlatWire ← CreateWire[flatCell];
i3: CoreFlat.FlatWire ← CreateWire[flatCell];
PackCombinatorialElement[major, flatCell, i1, LIST[en, d]];
PackCombinatorialElement[major, flatCell, i2, LIST[en, q]];
PackCombinatorialElement[major, flatCell, i3, LIST[i1, i2]];
PackSequentialElement[major, flatCell, q, i3];
};
tstDriver => {
x: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "X"];
triData: TriData ← NARROW[RefTab.Fetch[triDataTable, x].val];
IF triData.count>1
THEN {
i: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "I"];
en: CoreFlat.FlatWire ← GetNamedWire[bindings, cell.public, flatCell, "EN"];
i1: CoreFlat.FlatWire ← CreateWire[flatCell];
i2: CoreFlat.FlatWire ← CreateWire[flatCell];
previous: CoreFlat.FlatWire ← IF triData.count=2 THEN GetEquivalent[triData.lastInput] ELSE CreateWire[flatCell];
PackCombinatorialElement[major, flatCell, i1, LIST[en, i]];
PackCombinatorialElement[major, flatCell, i2, LIST[en, previous]];
PackCombinatorialElement[major, flatCell, triData.next, LIST[i1, i2]];
triData.count ← triData.count - 1;
triData.next ← previous;
};
};
ENDCASE => ERROR;
};
CreateWire:
PROC [flatCell: CoreFlat.FlatCellTypeRec]
RETURNS [flatWire: CoreFlat.FlatWire] = {
flatWire ← NEW[CoreFlat.FlatWireRec];
flatWire.flatCell ← flatCell;
flatWire.wire ← CoreOps.CreateWire[];
};
GetNamedWire:
PROC [bindings: CoreFlat.Bindings, public: Core.Wire, flatCell: CoreFlat.FlatCellTypeRec, name: Rope.
ROPE]
RETURNS [flatWire: CoreFlat.FlatWire] = {
wire: Core.Wire ← CoreOps.FindWire[public, name];
flatWire ← CanonizeWire[bindings, flatCell, wire];
flatWire ← GetEquivalent[flatWire];
};
GetEquivalent:
PROC [from: CoreFlat.FlatWire]
RETURNS [to: CoreFlat.FlatWire] = {
WHILE from#
NIL
DO
to ← from;
from ← NARROW[RefTab.Fetch[equivalence, from].val]
ENDLOOP;
};
CanonizeWire:
PROC [bindings: CoreFlat.Bindings, flatCell: CoreFlat.FlatCellTypeRec, wire: Core.Wire]
RETURNS [flatWire: CoreFlat.FlatWire] = {
flatWire ← NARROW[RefTab.Fetch[bindings, wire].val];
IF flatWire=
NIL
THEN {
flatWire ← NEW[CoreFlat.FlatWireRec];
flatWire.flatCell ← flatCell;
flatWire.wire ← wire;
};
};
equivalence: RefTab.Ref ← RefTab.Create[hash: CoreFlat.FlatWireHash, equal: CoreFlat.FlatWireEqual];
triDataTable: RefTab.Ref ← RefTab.Create[hash: CoreFlat.FlatWireHash, equal: CoreFlat.FlatWireEqual];
major ← NEW[MajorArrayRec];
major.a ← a;
major.b ← b;
major.outputs ← RefTab.Create[hash: CoreFlat.FlatWireHash, equal: CoreFlat.FlatWireEqual];
major.root ← root;
Equate[root];
[] ← RefTab.Pairs[triDataTable, EquateTristate];
Flatten[root];
major.root ← root;
};
PackCombinatorialElement:
PROC [major: MajorArray, c: CoreFlat.FlatCellTypeRec, o: Label, li: Labels] = {
minor: MinorArray;
t: Orientation;
minorIndex: ABIndex;
lip: InputPositions ← NIL;
IF CheckOutput[major, o] THEN RETURN;
FOR lm: MinorArrays ← major.minors, lm.rest
UNTIL lm=
NIL
DO
minor ← lm.first;
FOR t
IN Orientation
DO
FOR minorIndex
IN [0..
IF t=vertical
THEN major.a
ELSE major.b)
DO
IF minor.combinatorials[t].elements[minorIndex].o=
NIL
THEN {
KillInputAssignments:
PROC = {
FOR kl: InputPositions ← klip, kl.rest
UNTIL kl=
NIL
DO
inputScan[kl.first].i ← NIL;
ENDLOOP;
lip ← NIL;
};
inputScan: CombinatorialElements ← minor.combinatorials[IF t=vertical THEN horizontal ELSE vertical];
klip: InputPositions ← NIL;
FOR ll: Labels ← li, ll.rest
UNTIL ll=
NIL
DO
FOR inputIndex: ABIndex
IN [0..
IF t=vertical
THEN major.b
ELSE major.a)
DO
IF inputScan[inputIndex].i=
NIL
OR CoreFlat.FlatWireEqual[inputScan[inputIndex].i, ll.first]
THEN {
lip ← CONS[inputIndex, lip];
IF inputScan[inputIndex].i=NIL THEN klip ← CONS[inputIndex, klip];
inputScan[inputIndex].i ← ll.first;
EXIT;
};
REPEAT
FINISHED => {
KillInputAssignments[];
EXIT;
};
ENDLOOP;
REPEAT
FINISHED => {
FOR otherIndex: ABIndex
IN [0..
IF t=vertical
THEN major.b
ELSE major.a)
DO
IF inputScan[otherIndex].o#
NIL
THEN {
thisInOther: BOOL ← IndexInList[minorIndex, inputScan[otherIndex].ip];
otherInThis: BOOL ← IndexInList[otherIndex, lip];
IF (thisInOther
AND
NOT otherInThis)
OR (
NOT thisInOther
AND otherInThis)
THEN {
KillInputAssignments[];
EXIT;
}
};
REPEAT FINISHED => GOTO foundOne;
ENDLOOP;
};
ENDLOOP;
};
ENDLOOP;
ENDLOOP;
REPEAT
foundOne => NULL;
FINISHED => {
firstFreeInput: ABIndex ← 0;
CreateMinorArray[major];
minor ← major.lastMinor.first;
t ← horizontal;
minorIndex ← 0;
FOR ll: Labels ← li, ll.rest
UNTIL ll=
NIL
DO
lip ← CONS[firstFreeInput, lip];
firstFreeInput ← firstFreeInput + 1;
ENDLOOP;
IF firstFreeInput > major.a THEN ERROR;
};
ENDLOOP;
minor.combinatorials[t].elements[minorIndex].c ← NEW[CoreFlat.FlatCellTypeRec ← c];
minor.combinatorials[t].elements[minorIndex].o ← o;
minor.combinatorials[t].elements[minorIndex].ip ← lip;
};
IndexInList:
PROC [index: ABIndex, list: InputPositions]
RETURNS [
BOOL] = {
FOR ipl: InputPositions ← list, ipl.rest
UNTIL ipl=
NIL
DO
IF index=list.first THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE];
};
Legal:
PROC [major: MajorArray, minor: MinorArray, t: Orientation, minorIndex: ABIndex, o: Label, i: Labels]
RETURNS [
BOOL] = {
RETURN[TRUE];
};
PackSequentialElement:
PROC [major: MajorArray, c: CoreFlat.FlatCellTypeRec, o: Label, i: Label] = {
IF CheckOutput[major, o] THEN RETURN;
FOR lm: MinorArrays ← major.minors, lm.rest
UNTIL lm=
NIL
DO
minor: MinorArray ← lm.first;
IF minor.firstFreeSequentialElement<major.a
THEN {
minor.sequentials[minor.firstFreeSequentialElement] ← NEW[SequentialElementRec ← [c: NEW[CoreFlat.FlatCellTypeRec ← c], i: i, o: o]];
minor.firstFreeSequentialElement ← minor.firstFreeSequentialElement + 1;
EXIT;
};
REPEAT
FINISHED => {
minor: MinorArray;
CreateMinorArray[major];
minor ← major.lastMinor.first;
minor.sequentials[0] ← NEW[SequentialElementRec ← [c: NEW[CoreFlat.FlatCellTypeRec ← c], i: i, o: o]];
minor.firstFreeSequentialElement ← 1;
};
ENDLOOP;
};
CreateMinorArray:
PROC [major: MajorArray] = {
m: MinorArray ← NEW[MinorArrayRec];
m.position ← [major.c, major.d];
m.combinatorials[vertical] ← NEW[CombinatorialElementsRec[major.a]];
FOR aIndex: AIndex
IN [0..major.a)
DO
m.combinatorials[vertical].elements[aIndex] ← NEW[CombinatorialElementRec];
ENDLOOP;
m.combinatorials[horizontal] ← NEW[CombinatorialElementsRec[major.b]];
FOR bIndex: BIndex
IN [0..major.b)
DO
m.combinatorials[horizontal].elements[bIndex] ← NEW[CombinatorialElementRec];
ENDLOOP;
m.sequentials ← NEW[SequentialElementsRec[major.a]];
FOR ei: AIndex
IN [0..major.a)
DO
m.sequentials[ei] ← NIL;
ENDLOOP;
IF major.lastMinor=NIL THEN major.lastMinor ← major.minors ← LIST[m]
ELSE {
major.lastMinor.rest ← LIST[m];
major.lastMinor ← major.lastMinor.rest;
};
update major.c and major.d in spiral pattern
IF major.d>=0
AND major.c=major.d
THEN {
major.d ← major.d + 1;
major.enumerationState ← left;
}
ELSE {
IF ABS[major.c]=ABS[major.d] THEN major.enumerationState ← SUCC[major.enumerationState];
SELECT major.enumerationState
FROM
left => major.c ← major.c - 1;
down => major.d ← major.d - 1;
right => major.c ← major.c + 1;
up => major.d ← major.d + 1;
ENDCASE;
};
};
CheckOutput:
PROC [major: MajorArray, o: Label]
RETURNS [found:
BOOL] = {
found ← RefTab.Fetch[major.outputs, o].found;
IF found THEN TerminalIO.PutF["\nMultiply driven output: %g", IO.rope[CoreFlat.WirePathRope[major.root, o^]]]
ELSE IF NOT RefTab.Insert[major.outputs, o, $Driven] THEN ERROR;
};
Routing
Surface: TYPE = REF SurfaceRec;
SurfaceRec:
TYPE =
RECORD [
major: MajorArray,
size: MajorGridPosition ← [0, 0],
channelSizes: ARRAY Orientation OF ChannelSizes,
flatWires: RefTab.Ref, -- maps CoreFlat.FlatWire to NetEnds
nodes: RefTab.Ref]; -- maps NodePosition to Node
ChannelSizes: TYPE = REF ChannelSizesRec;
ChannelSizesRec:
TYPE =
RECORD [
elements: SEQUENCE size: CARDINAL OF NAT]; -- surface.size.? + 1
NetEnds: TYPE = REF NetEndsRec;
NetEndsRec:
TYPE =
RECORD [
output: Node ← NIL,
inputs: Nodes ← NIL];
Nodes: TYPE = LIST OF Node;
Node: TYPE = REF NodeRec;
NodeRec:
TYPE =
RECORD [
position: NodePosition,
flatCell: CoreFlat.FlatCellType ← NIL,
flatWire: CoreFlat.FlatWire ← NIL,
back: Node ← NIL,
neighbors: SEQUENCE size: NodeIndex OF Node];
NodePositions: TYPE = LIST OF NodePosition;
NodePosition: TYPE = REF NodePositionRec;
NodePositionRec:
TYPE =
RECORD [
type: NodeType,
majorPosition: MajorGridPosition,
minorPosition: ABIndex ← 0];
NodeType:
TYPE = {horizontalShort, verticalShort, horizontalLong, verticalLong, horizontalOutput, verticalOutput, sequentialIn, sequentialOut};
majorPosition is dependent on type. If type is horizontalLong then majorPosition.x is invalid. If type is verticalLong then majorPosition.y is invalid.
NodeIndex:
TYPE =
CARDINAL;
ChannelSizesFromList:
PROC [sl:
LIST
OF
NAT]
RETURNS [cs: ChannelSizes] = {
index: CARDINAL ← 0;
FOR l:
LIST
OF
NAT ← sl, l.rest
UNTIL l=
NIL
DO
index ← index + 1;
ENDLOOP;
cs ← NEW[ChannelSizesRec[index]];
index ← 0;
FOR l:
LIST
OF
NAT ← sl, l.rest
UNTIL l=
NIL
DO
cs[index] ← l.first;
index ← index + 1;
ENDLOOP;
};
CreateChanneledSurface:
PROC [major: MajorArray, channelSize:
NAT ← 1]
RETURNS [surface: Surface] = {
minx, miny: INT ← LAST[INT];
maxx, maxy: INT ← FIRST[INT];
csv, csh: ChannelSizes;
FOR lm: MinorArrays ← major.minors, lm.rest
UNTIL lm=
NIL
DO
m: MinorArray ← lm.first;
minx ← MIN[minx, m.position.x];
miny ← MIN[miny, m.position.y];
maxx ← MAX[maxx, m.position.x];
maxy ← MAX[maxy, m.position.y];
ENDLOOP;
csv ← NEW[ChannelSizesRec[maxx - minx + 2]];
csh ← NEW[ChannelSizesRec[maxy - miny + 2]];
FOR index:
NAT
IN [0..csv.size)
DO
csv[index] ← channelSize;
ENDLOOP;
FOR index:
NAT
IN [0..csh.size)
DO
csh[index] ← channelSize;
ENDLOOP;
surface ← CreateSurface[major, [csv, csh]];
};
CreateSurface:
PROC [major: MajorArray, channelSizes:
ARRAY Orientation
OF ChannelSizes]
RETURNS [surface: Surface] = {
LookupNodePosition:
PROC [position: NodePositionRec]
RETURNS [node: Node] = {
nodePosition^ ← position;
node ← NARROW[RefTab.Fetch[surface.nodes, nodePosition].val];
IF node=NIL THEN ERROR;
};
FetchNetEnds:
PROC [flatWire: CoreFlat.FlatWire]
RETURNS [ne: NetEnds] = {
ne ← NARROW[RefTab.Fetch[surface.flatWires, flatWire].val];
IF ne=
NIL
THEN {
ne ← NEW[NetEndsRec];
IF NOT RefTab.Insert[surface.flatWires, flatWire, ne] THEN ERROR;
};
};
MajorToSurface:
PROC [major: MajorGridPosition]
RETURNS [surface: MajorGridPosition] = {
adjustedx: NAT ← major.x - minx;
adjustedy: NAT ← major.y - miny;
surface.x ← adjustedx;
surface.y ← adjustedy;
FOR i:
NAT
IN [0..adjustedx]
DO
surface.x ← surface.x + channelSizes[vertical][i];
ENDLOOP;
FOR i:
NAT
IN [0..adjustedy]
DO
surface.y ← surface.y + channelSizes[horizontal][i];
ENDLOOP;
};
minx, miny: INT ← LAST[INT];
maxx, maxy: INT ← FIRST[INT];
nodePosition: NodePosition ← NEW[NodePositionRec];
surface ← NEW[SurfaceRec];
surface.major ← major;
surface.channelSizes ← channelSizes;
surface.flatWires ← RefTab.Create[hash: CoreFlat.FlatWireHash, equal: CoreFlat.FlatWireEqual];
surface.nodes ← RefTab.Create[hash: NodePositionHash, equal: NodePositionEqual];
surface.size.x ← ComputeSize[channelSizes[vertical]];
surface.size.y ← ComputeSize[channelSizes[horizontal]];
FOR lm: MinorArrays ← major.minors, lm.rest
UNTIL lm=
NIL
DO
m: MinorArray ← lm.first;
minx ← MIN[minx, m.position.x];
miny ← MIN[miny, m.position.y];
maxx ← MAX[maxx, m.position.x];
maxy ← MAX[maxy, m.position.y];
ENDLOOP;
IF (maxx - minx + 2) # channelSizes[vertical].size THEN ERROR;
IF (maxy - miny + 2) # channelSizes[horizontal].size THEN ERROR;
AllocateNodesAndArcs[surface];
FOR lm: MinorArrays ← major.minors, lm.rest
UNTIL lm=
NIL
DO
minor: MinorArray ← lm.first;
position: MajorGridPosition ← MajorToSurface[minor.position];
FOR ei: AIndex
IN [0..minor.sequentials.size)
DO
se: SequentialElement ← minor.sequentials[ei];
IF se#
NIL
THEN {
in: Node ← LookupNodePosition[[sequentialIn, position, ei]];
out: Node ← LookupNodePosition[[sequentialOut, position, ei]];
inNetEnds: NetEnds ← FetchNetEnds[se.i];
outNetEnds: NetEnds ← FetchNetEnds[se.o];
inNetEnds.inputs ← CONS[in, inNetEnds.inputs];
in.flatCell ← se.c;
in.flatWire ← se.i;
IF outNetEnds.output#NIL THEN ERROR;
outNetEnds.output ← out;
out.flatCell ← se.c;
out.flatWire ← se.o;
};
ENDLOOP;
FOR t: Orientation
IN Orientation
DO
elements: CombinatorialElements ← minor.combinatorials[t];
FOR ei: ABIndex
IN [0..elements.size)
DO
IF elements[ei].i#
NIL
THEN {
node: Node ← LookupNodePosition[[IF t=vertical THEN verticalShort ELSE horizontalShort, position, ei]];
ne: NetEnds ← FetchNetEnds[elements[ei].i];
ne.inputs ← CONS[node, ne.inputs];
node.flatWire ← elements[ei].i;
};
IF elements[ei].o#
NIL
THEN {
node: Node ← LookupNodePosition[[IF t=vertical THEN verticalOutput ELSE horizontalOutput, position, ei]];
ne: NetEnds ← FetchNetEnds[elements[ei].o];
IF ne.output#NIL THEN ERROR;
ne.output ← node;
node.flatCell ← elements[ei].c;
node.flatWire ← elements[ei].o;
};
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
AllocateNodesAndArcs:
PROC [surface: Surface] = {
LookupNodePosition:
PROC [position: NodePositionRec]
RETURNS [node: Node] = {
nodePosition^ ← position;
node ← NARROW[RefTab.Fetch[surface.nodes, nodePosition].val];
IF node=NIL THEN ERROR;
};
nodePosition: NodePosition ← NEW[NodePositionRec];
major: MajorArray ← surface.major;
FOR x:
INT
IN [0..surface.size.x)
DO
FOR a: AIndex
IN [0..major.a)
DO
CreateNode[surface, verticalLong, [x, 0], a, 2*surface.size.y];
ENDLOOP;
ENDLOOP;
FOR y:
INT
IN [0..surface.size.y)
DO
FOR b: BIndex
IN [0..major.b)
DO
CreateNode[surface, horizontalLong, [0, y], b, surface.size.x];
ENDLOOP;
ENDLOOP;
FOR x:
INT
IN [0..surface.size.x)
DO
FOR y:
INT
IN [0..surface.size.y)
DO
FOR a: AIndex
IN [0..major.a)
DO
shortNeighbors: NAT ← IF y=0 OR y=surface.size.y-1 THEN 1 ELSE 2;
seqNeighbors: NAT ← IF y=0 THEN 1 ELSE 2;
CreateNode[surface, verticalShort, [x, y], a, shortNeighbors+seqNeighbors+1+major.b];
CreateNode[surface, verticalOutput, [x, y], a, shortNeighbors+seqNeighbors+2];
CreateNode[surface, sequentialIn, [x, y], a, 0];
CreateNode[surface, sequentialOut, [x, y], a, (IF y=surface.size.y-1 THEN 1 ELSE 2)+1];
ENDLOOP;
FOR b: BIndex
IN [0..major.b)
DO
shortNeighbors: NAT ← IF x=0 OR x=surface.size.x-1 THEN 1 ELSE 2;
CreateNode[surface, horizontalShort, [x, y], b, shortNeighbors+1+major.a];
CreateNode[surface, horizontalOutput, [x, y], b, shortNeighbors+2];
ENDLOOP;
ENDLOOP;
ENDLOOP;
FOR x:
INT
IN [0..surface.size.x)
DO
FOR a: AIndex
IN [0..major.a)
DO
long: Node ← LookupNodePosition[[verticalLong, [x, 0], a]];
FOR y:
INT
IN [0..surface.size.y)
DO
short: Node ← LookupNodePosition[[verticalShort, [x, y], a]];
out: Node ← LookupNodePosition[[verticalOutput, [x, y], a]];
sIn: Node ← LookupNodePosition[[sequentialIn, [x, y], a]];
sOut: Node ← LookupNodePosition[[sequentialOut, [x, y], a]];
CreateArc[surface, short, long];
CreateArc[surface, long, short];
CreateArc[surface, out, short];
CreateArc[surface, out, long];
CreateArc[surface, long, sIn];
CreateArc[surface, short, sIn];
CreateArc[surface, out, sIn];
CreateArc[surface, sOut, long];
CreateArc[surface, sOut, short];
IF y>0
THEN {
neighbor: Node ← LookupNodePosition[[verticalShort, [x, y-1], a]];
CreateArc[surface, neighbor, short];
neighbor ← LookupNodePosition[[verticalOutput, [x, y-1], a]];
CreateArc[surface, neighbor, short];
};
IF y<surface.size.y-1
THEN {
neighbor: Node ← LookupNodePosition[[verticalShort, [x, y+1], a]];
CreateArc[surface, neighbor, short];
CreateArc[surface, neighbor, sIn];
CreateArc[surface, sOut, neighbor];
neighbor ← LookupNodePosition[[verticalOutput, [x, y+1], a]];
CreateArc[surface, neighbor, short];
CreateArc[surface, neighbor, sIn];
};
ENDLOOP;
ENDLOOP;
ENDLOOP;
FOR y:
INT
IN [0..surface.size.y)
DO
FOR b: BIndex
IN [0..major.b)
DO
long: Node ← LookupNodePosition[[horizontalLong, [0, y], b]];
FOR x:
INT
IN [0..surface.size.x)
DO
short: Node ← LookupNodePosition[[horizontalShort, [x, y], b]];
out: Node ← LookupNodePosition[[horizontalOutput, [x, y], b]];
CreateArc[surface, short, long];
CreateArc[surface, long, short];
CreateArc[surface, out, short];
CreateArc[surface, out, long];
IF x>0
THEN {
neighbor: Node ← LookupNodePosition[[horizontalShort, [x-1, y], b]];
CreateArc[surface, neighbor, short];
neighbor ← LookupNodePosition[[horizontalOutput, [x-1, y], b]];
CreateArc[surface, neighbor, short];
};
IF x<surface.size.x-1
THEN {
neighbor: Node ← LookupNodePosition[[horizontalShort, [x+1, y], b]];
CreateArc[surface, neighbor, short];
neighbor ← LookupNodePosition[[horizontalOutput, [x+1, y], b]];
CreateArc[surface, neighbor, short];
};
ENDLOOP;
ENDLOOP;
ENDLOOP;
FOR x:
INT
IN [0..surface.size.x)
DO
FOR y:
INT
IN [0..surface.size.y)
DO
FOR a: AIndex
IN [0..major.a)
DO
verticalShort: Node ← LookupNodePosition[[verticalShort, [x, y], a]];
verticalOutput: Node ← LookupNodePosition[[verticalOutput, [x, y], a]];
FOR b: BIndex
IN [0..major.b)
DO
horizontalShort: Node ← LookupNodePosition[[horizontalShort, [x, y], b]];
horizontalOutput: Node ← LookupNodePosition[[horizontalOutput, [x, y], b]];
CreateArc[surface, verticalShort, horizontalOutput];
CreateArc[surface, horizontalShort, verticalOutput];
ENDLOOP;
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
CreateNode:
PROC [surface: Surface, type: NodeType, majorPosition: MajorGridPosition, minorPosition: ABIndex, arcCount:
NAT] = {
node: Node ← NEW[NodeRec[arcCount]];
node.position ← NEW[NodePositionRec ← [type, majorPosition, minorPosition]];
FOR arcIndex:
NAT
IN [0..arcCount)
DO
node[arcIndex] ← NIL;
ENDLOOP;
IF NOT RefTab.Insert[surface.nodes, node.position, node] THEN ERROR;
};
CreateArc:
PROC [surface: Surface, source, destination: Node] = {
FOR nodeIndex:
NAT
IN [0..source.size)
DO
IF source[nodeIndex]=
NIL
THEN {
source[nodeIndex] ← destination;
RETURN;
};
ENDLOOP;
ERROR;
};
NodePositionHash: RefTab.HashProc = {
nodePosition: NodePosition ← NARROW[key];
hash: CARDINAL ← Basics.LowHalf[nodePosition.minorPosition];
bigHash: CARD32 ← LOOPHOLE[Basics.DoubleXor[LOOPHOLE[nodePosition.majorPosition.x], LOOPHOLE[nodePosition.majorPosition.y]]];
hash ← Basics.BITXOR[hash, Basics.LowHalf[bigHash]];
hash ← Basics.BITXOR[hash, Basics.HighHalf[bigHash]];
RETURN[hash];
};
NodePositionEqual: RefTab.EqualProc = {
np1: NodePosition ← NARROW[key1];
np2: NodePosition ← NARROW[key2];
RETURN[np1^=np2^];
};
ComputeSize:
PROC [channelSizes: ChannelSizes]
RETURNS [size:
INT ← -1] = {
FOR ci:
CARDINAL
IN [0..channelSizes.size)
DO
size ← size + channelSizes[ci] + 1;
ENDLOOP;
};
RouteSurface:
PROC [surface: Surface]
RETURNS [incomplete: CoreFlat.FlatWires] = {
RouteWire: RefTab.EachPairAction = {
wire: CoreFlat.FlatWire ← NARROW[key];
ne: NetEnds ← NARROW[RefTab.Fetch[surface.flatWires, wire].val];
inputs: Nodes ← ne.inputs;
IF inputs#
NIL
THEN {
seed: Node;
IF ne.output=
NIL
THEN {
seed ← inputs.first;
inputs ← inputs.rest;
}
ELSE seed ← ne.output;
IF inputs#
NIL
THEN {
FIFOQueue.Include[fifo, seed];
UNTIL FIFOQueue.IsEmpty[fifo]
DO
FOR il: Nodes ← inputs, il.rest
UNTIL il=
NIL
DO
IF il.first.back=NIL THEN EXIT;
REPEAT
FINISHED => {
FOR il: Nodes ← inputs, il.rest
UNTIL il=
NIL
DO
nodeCount: NAT ← 0;
assign: Node ← il.first;
UNTIL assign=
NIL
DO
assign.flatWire ← wire;
assign ← assign.back;
nodeCount ← nodeCount + 1;
ENDLOOP;
maxNodeCount ← MAX[maxNodeCount, nodeCount];
ENDLOOP;
EXIT;
};
ENDLOOP;
{
current: Node ← NARROW[FIFOQueue.Remove[fifo]];
FOR ni: NodeIndex
IN [0..current.size)
DO
neighbor: Node ← current[ni];
IF (neighbor.flatWire=
NIL
OR (neighbor#seed
AND CoreFlat.FlatWireEqual[neighbor.flatWire, wire]))
AND neighbor.back=
NIL
THEN {
neighbor.back ← current;
FIFOQueue.Include[fifo, neighbor];
};
ENDLOOP;
};
REPEAT FINISHED => incomplete ← CONS[wire, incomplete];
ENDLOOP;
CleanUpBackPointers[fifo, seed];
};
};
};
fifo: FIFOQueue.Queue ← FIFOQueue.Create[];
[] ← RefTab.Pairs[surface.flatWires, RouteWire];
};
CleanUpBackPointers:
PROC [fifo: FIFOQueue.Queue, seed: Node] = {
FIFOQueue.Flush[fifo];
FIFOQueue.Include[fifo, seed];
UNTIL FIFOQueue.IsEmpty[fifo]
DO
current: Node ← NARROW[FIFOQueue.Remove[fifo]];
FOR ni: NodeIndex
IN [0..current.size)
DO
neighbor: Node ← current[ni];
IF neighbor.back#
NIL
THEN {
neighbor.back ← NIL;
FIFOQueue.Include[fifo, neighbor];
};
ENDLOOP;
ENDLOOP;
};
Display
SurfaceViewer: TYPE = REF SurfaceViewerRec;
SurfaceViewerRec:
TYPE =
RECORD [
surface: Surface ← NIL,
completed: BOOL ← TRUE, -- nodes assigned to wires
allocated: BOOL ← FALSE, -- all allocated nodes
flatWires: CoreFlat.FlatWires ← NIL]; -- net endpoints
surfaceViewerAtom: ATOM = $SurfaceViewer;
surfaceViewerClass: ViewerClasses.ViewerClass ←
NEW [ViewerClasses.ViewerClassRec ← [paint: PaintSurfaceViewer]];
AllWires:
PROC [surface: Surface]
RETURNS [wires: CoreFlat.FlatWires ←
NIL] = {
AddWire: RefTab.EachPairAction = {
wire: CoreFlat.FlatWire ← NARROW[key];
wires ← CONS[wire, wires];
};
[] ← RefTab.Pairs[surface.flatWires, AddWire];
};
DisplayWires:
PROC [surface: Surface, endpoints: CoreFlat.FlatWires ←
NIL, completed:
BOOL ←
TRUE, allocated:
BOOL ←
FALSE] = {
viewer: ViewerClasses.Viewer;
surfaceViewer: SurfaceViewer ← NEW[SurfaceViewerRec];
surfaceViewer.surface ← surface;
surfaceViewer.allocated ← allocated;
surfaceViewer.completed ← completed;
surfaceViewer.flatWires ← endpoints;
viewer ← ViewerOps.CreateViewer[
flavor: surfaceViewerAtom,
info: [
name: CoreOps.GetCellTypeName[surface.major.root],
iconic: FALSE,
column: color,
border: TRUE,
data: surfaceViewer
]
];
};
PaintSurfaceViewer: ViewerClasses.PaintProc = {
ToVec:
PROC [pos: NodePosition]
RETURNS [vec: Imager.
VEC] = {
p1, p2: Imager.VEC;
[p1, p2] ← ToVecPair[pos];
vec.x ← (p1.x + p2.x) / 2.0;
vec.y ← (p1.y + p2.y) / 2.0;
};
ToVecPair:
PROC [pos: NodePosition]
RETURNS [p1, p2: Imager.
VEC] = {
minorAdjust: REAL ← (1+4*pos.minorPosition)*minorGrid;
p1 ← [bounds.x + pos.majorPosition.x*grid, bounds.y + pos.majorPosition.y*grid];
SELECT pos.type
FROM
verticalLong => {
p1.x ← p1.x + minorAdjust;
p1.y ← bounds.y;
p2.x ← p1.x;
p2.y ← p1.y + size.y*grid;
};
sequentialIn, verticalShort => {
p1.x ← p1.x + minorAdjust + minorGrid;
p2.x ← p1.x;
p2.y ← p1.y + grid;
};
sequentialOut, verticalOutput => {
p1.x ← p1.x + minorAdjust + 2.0*minorGrid;
p2.x ← p1.x;
p2.y ← p1.y + grid;
};
horizontalLong => {
p1.y ← p1.y + minorAdjust;
p1.x ← bounds.x;
p2.y ← p1.y;
p2.x ← p1.x + size.x*grid;
};
horizontalShort => {
p1.y ← p1.y + minorAdjust + minorGrid;
p2.y ← p1.y;
p2.x ← p1.x + grid;
};
horizontalOutput => {
p1.y ← p1.y + minorAdjust + 2.0*minorGrid;
p2.y ← p1.y;
p2.x ← p1.x + grid;
};
ENDCASE => ERROR;
};
PaintNode: RefTab.EachPairAction = {
node: Node ← NARROW[val];
IF node.flatWire#
NIL
THEN {
p1, p2: Imager.VEC;
[p1, p2] ← ToVecPair[node.position];
Imager.MaskVector[context, p1, p2];
};
};
surfaceViewer: SurfaceViewer ← NARROW[self.data];
size: MajorGridPosition ← surfaceViewer.surface.size;
xChannels: ChannelSizes ← surfaceViewer.surface.channelSizes[vertical];
yChannels: ChannelSizes ← surfaceViewer.surface.channelSizes[horizontal];
bounds: Imager.Rectangle ← ImagerBackdoor.GetBounds[context];
grid: REAL ← MIN[bounds.w, bounds.h]/MAX[size.x, size.y];
minorGrid: REAL ← (grid/surfaceViewer.surface.major.a)/4.0;
xpos: REAL ← bounds.x;
IF clear
THEN {
Imager.SetColor[context, Imager.white];
Imager.MaskRectangle[context, bounds];
};
Imager.SetColor[context, Imager.black];
Imager.SetStrokeWidth[context, grid/10.0];
FOR x: INT IN [0..xChannels.size-1) DO
ypos: REAL ← bounds.y;
xpos ← xpos + grid*xChannels[x];
FOR y: INT IN [0..yChannels.size-1) DO
xr, yu: REAL;
ypos ← ypos + grid*yChannels[y];
xr ← xpos + grid;
yu ← ypos + grid;
Imager.MaskVector[context, [xpos, ypos], [xr, ypos]];
Imager.MaskVector[context, [xpos, ypos], [xpos, yu]];
Imager.MaskVector[context, [xr, yu], [xr, ypos]];
Imager.MaskVector[context, [xr, yu], [xpos, yu]];
ypos ← ypos + grid;
ENDLOOP;
xpos ← xpos + grid;
ENDLOOP;
Imager.SetStrokeWidth[context, grid/40.0];
Imager.SetColor[context, Imager.black];
FOR wl: CoreFlat.FlatWires ← surfaceViewer.flatWires, wl.rest
UNTIL wl=
NIL
DO
ne: NetEnds ← NARROW[RefTab.Fetch[surfaceViewer.surface.flatWires, wl.first].val];
inputs: Nodes ← ne.inputs;
IF inputs#
NIL
THEN {
firstPos: Imager.VEC;
IF ne.output=
NIL
THEN {
firstPos ← ToVec[inputs.first.position];
inputs ← inputs.rest;
}
ELSE firstPos ← ToVec[ne.output.position];
FOR il: Nodes ← inputs, il.rest
UNTIL il=
NIL
DO
inputPos: Imager.VEC ← ToVec[il.first.position];
Imager.MaskVector[context, firstPos, inputPos];
ENDLOOP;
};
ENDLOOP;
Imager.SetGray[context, 0.5];
IF surfaceViewer.completed THEN [] ← RefTab.Pairs[surfaceViewer.surface.nodes, PaintNode];
IF surfaceViewer.allocated
THEN {
fifo: FIFOQueue.Queue ← FIFOQueue.Create[];
seedPosition: NodePosition ← NEW[NodePositionRec ← [horizontalShort, [0, 0], 0]];
seed: Node ← NARROW[RefTab.Fetch[surfaceViewer.surface.nodes, seedPosition].val];
FIFOQueue.Include[fifo, seed];
UNTIL FIFOQueue.IsEmpty[fifo]
DO
current: Node ← NARROW[FIFOQueue.Remove[fifo]];
FOR ni: NodeIndex
IN [0..current.size)
DO
neighbor: Node ← current[ni];
IF neighbor.back=
NIL
THEN {
p1, p2: Imager.VEC;
[p1, p2] ← ToVecPair[neighbor.position];
Imager.MaskVector[context, p1, p2];
neighbor.back ← current;
FIFOQueue.Include[fifo, neighbor];
};
ENDLOOP;
ENDLOOP;
CleanUpBackPointers[fifo, seed];
};
};