<> <> <> <<>> DIRECTORY Basics, Combinatorial, Core, CoreFlat, CoreOps, FIFOQueue, Imager, ImagerBackdoor, IO, RefTab, Rope, SymTab, TerminalIO, ViewerClasses, ViewerOps; SoftHdwPlacement: CEDAR PROGRAM IMPORTS Basics, Combinatorial, CoreFlat, CoreOps, FIFOQueue, Imager, ImagerBackdoor, IO, RefTab, SymTab, TerminalIO, ViewerOps EXPORTS = BEGIN <> 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; CDIndex: TYPE = INT; RopeList: TYPE = LIST OF Rope.ROPE; Labels: TYPE = CoreFlat.FlatWires; Label: TYPE = CoreFlat.FlatWire; <> 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 { 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; }; <> 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; }; <> 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}; <> <<>> 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 y0 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 { 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; }; <> 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.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]; }; }; <> LoadPrimitiveTypes[]; ViewerOps.RegisterViewerClass[surfaceViewerAtom, surfaceViewerClass]; END.