NewBasicRosemaryImpl.mesa
Copyright Ó 1988 by Xerox Corporation. All rights reserved.
Barth, June 10, 1988 1:15:29 pm PDT
DIRECTORY BrineIO, Core, CoreClasses, CoreFlat, CoreIO, CoreOps, CoreProperties, IO, NewBasicRosemary, RefTab, Rope;
NewBasicRosemaryImpl: CEDAR PROGRAM
IMPORTS BrineIO, CoreClasses, CoreFlat, CoreIO, CoreOps, CoreProperties, IO, RefTab, Rope
EXPORTS NewBasicRosemary
= BEGIN OPEN NewBasicRosemary;
roseFixedWireProp: ATOM = CoreIO.RegisterProperty[prop: CoreProperties.RegisterProperty[prop: $RoseFixedWire, properties: CoreProperties.Props[[CoreProperties.propPrint, NEW[CoreProperties.PropPrintProc ← RoseFixedWirePrint]]]], write: RoseFixedWireWrite, read: RoseFixedWireRead];
RoseFixedWirePrint: CoreProperties.PropPrintProc = {
lev: REF Level ← NARROW[val];
CoreOps.PrintIndent[indent, to];
IO.PutF[to, "%g: ", IO.atom[roseFixedWireProp]];
IO.PutRope[to, levelNames[lev^]];
};
RoseFixedWireWrite: CoreIO.PropWriteProc = {
level: REF Level ← NARROW[value];
BrineIO.WriteID[stream, levelNames[level^]];
};
RoseFixedWireRead: CoreIO.PropReadProc = {
level: REF Level ← NEW[Level];
level^ ← FindLevel[BrineIO.ReadID[stream]];
value ← level;
};
Instantiation and Relaxation
SetFixedWire: PUBLIC PROC [wire: Core.Wire, level: Level ← L] RETURNS [sameWire: Core.Wire] = {
CoreProperties.PutWireProp[on: wire, prop: roseFixedWireProp, value: NEW[Level ← level]];
sameWire ← wire;
};
SetNamedFixedWire: PUBLIC PROC [cellType: Core.CellType, name: Rope.ROPE, level: Level ← L] RETURNS [sameWire: Core.Wire] = {
sameWire ← SetFixedWire[CoreOps.FindWire[cellType.public, name], level];
};
Instantiate: PUBLIC PROC [cellType: Core.CellType] RETURNS [simulation: RoseSimulation] = {
FlattenCell: CoreFlat.BoundFlatCellProc = {
SELECT TRUE FROM
cell.class=CoreClasses.transistorCellClass => {
public: Core.Wire ← cell.public;
coreTransistor: CoreClasses.Transistor ← NARROW[cell.data];
roseTransistor: RoseTransistor ← NEW[RoseTransistorRec];
roseTransistor.gate ← LookUpRoseWire[public[gate], bindings];
roseTransistor.gate.gates ← CONS[roseTransistor, roseTransistor.gate.gates];
roseTransistor.ch1 ← LookUpRoseWire[public[ch1], bindings];
roseTransistor.ch1.channels ← CONS[roseTransistor, roseTransistor.ch1.channels];
roseTransistor.ch1.notOffChannels ← CONS[roseTransistor, roseTransistor.ch1.notOffChannels];
roseTransistor.ch2 ← LookUpRoseWire[public[ch2], bindings];
roseTransistor.ch2.channels ← CONS[roseTransistor, roseTransistor.ch2.channels];
roseTransistor.ch2.notOffChannels ← CONS[roseTransistor, roseTransistor.ch2.notOffChannels];
roseTransistor.transistorType ← coreTransistor.type;
roseTransistor.flatCellType ← flatCell;
};
cell.class=CoreClasses.recordCellClass => {
AllocateWire: PROC [coreWire: Core.Wire] = {
flatWire: CoreFlat.FlatWire ← IF bindings=NIL THEN NIL ELSE NARROW[RefTab.Fetch[x: bindings, key: coreWire].val];
IF flatWire=NIL THEN {
wireKey.flatCell ← flatCell;
wireKey.wire ← coreWire;
IF RefTab.Fetch[x: simulation.coreToRoseWires, key: wireKey].val=NIL THEN {
wireFixedRef: REF Level ← NARROW[CoreProperties.GetWireProp[from: coreWire, prop: roseFixedWireProp]];
roseWire: RoseWire ← NEW[RoseWireRec];
roseWire.flatWire ← wireKey^;
Perturb[simulation, roseWire];
IF wireFixedRef#NIL THEN {
roseWire.wireSize ← infinite;
roseWire.wireLevel ← wireFixedRef^
};
IF NOT RefTab.Insert[x: simulation.coreToRoseWires, key: roseWire, val: roseWire] THEN ERROR;
};
};
};
cellTypeRCT: CoreClasses.RecordCellType ← NARROW[cell.data];
CoreOps.VisitRootAtomics[cellTypeRCT.internal, AllocateWire];
CoreFlat.NextBoundCellType[cell, target, flatCell, instance, index, parent, flatParent, data, bindings, FlattenCell];
};
ENDCASE => CoreFlat.NextBoundCellType[cell, target, flatCell, instance, index, parent, flatParent, data, bindings, FlattenCell];
};
LookUpRoseWire: PROC [wire: Core.Wire, bindings: RefTab.Ref] RETURNS [roseWire: RoseWire ← NIL] = {
leftUpper: CoreFlat.FlatWire ← NARROW[RefTab.Fetch[x: bindings, key: wire].val];
roseWire ← NARROW[RefTab.Fetch[x: simulation.coreToRoseWires, key: leftUpper].val];
};
ComputeMaxVicinity: RefTab.EachPairAction = {
roseWire: RoseWire ← NARROW[val];
IF roseWire.wireSize#infinite AND NOT roseWire.mark THEN maxVicinity ← MAX[maxVicinity, CountVicinity[roseWire]];
};
CountVicinity: PROC [wire: RoseWire, currentCount: NAT ← 0] RETURNS [newCount: NAT] = {
wire.mark ← TRUE;
newCount ← currentCount + 1;
FOR rts: RoseTransistors ← wire.channels, rts.rest UNTIL rts=NIL DO
tran: RoseTransistor ← rts.first;
otherWire: RoseWire ← tran.ch1;
IF otherWire=wire THEN otherWire ← tran.ch2;
IF otherWire.wireSize#infinite AND NOT otherWire.mark THEN newCount ← CountVicinity[otherWire, newCount];
ENDLOOP;
};
gate: NAT = CoreClasses.TransistorPort.gate.ORD;
ch1: NAT = CoreClasses.TransistorPort.ch1.ORD;
ch2: NAT = CoreClasses.TransistorPort.ch2.ORD;
wireKey: CoreFlat.FlatWire ← NEW[CoreFlat.FlatWireRec];
maxVicinity: NAT ← 0;
simulation ← NEW[RoseSimulationRec];
simulation.cellType ← cellType;
simulation.coreToRoseWires ← RefTab.Create[mod: 1019, equal: RoseWireEqual, hash: RoseWireHash];
FlattenCell[cell: cellType];
[] ← RefTab.Pairs[x: simulation.coreToRoseWires, action: ComputeMaxVicinity];
FOR strength: Drive IN Drive DO
simulation.vicinityByStrength[strength].wires ← NEW[RoseWireSeq[maxVicinity]];
ENDLOOP;
};
Settle: PUBLIC PROC [simulation: RoseSimulation] = {
simulation.settle ← simulation.settle+1;
UNTIL simulation.perturbed=NIL DO
simulation.step ← simulation.step+1;
UpdatePerturbed[simulation: simulation];
ENDLOOP;
};
UpdatePerturbed: PROC [simulation: RoseSimulation] = {
PushWireByStrength: PROC [wire: RoseWire, thisDrive: Drive] = {
simulation.vicinityByStrength[thisDrive].wires[ simulation.vicinityByStrength[thisDrive].firstFree] ← wire;
simulation.vicinityByStrength[thisDrive].firstFree ← simulation.vicinityByStrength[thisDrive].firstFree+1;
};
PushWhat: TYPE = {switch, up, down};
FindVicinity: PROC [wire: RoseWire, what: PushWhat] = {
UpDownStrength: PROC [notLevel: Level] RETURNS [strength: Drive] = {
strength ← IF wire.wireLevel=notLevel THEN none ELSE wire.wireSize;
};
wireSize: Drive ← SELECT what FROM
switch => wire.wireSize,
up => UpDownStrength[L],
down => UpDownStrength[H],
ENDCASE => ERROR;
wire.mark ← TRUE;
FOR rts: RoseTransistors ← wire.notOffChannels, rts.rest UNTIL rts=NIL DO
tran: RoseTransistor ← rts.first;
tranCond: Conductance ← TranOn[tran, tran.gate.wireLevel];
otherWire: RoseWire ← tran.ch1;
IF otherWire=wire THEN otherWire ← tran.ch2;
IF otherWire.wireSize=infinite THEN {
IF ((what=switch AND tranCond=on) OR (what=up AND otherWire.wireLevel#L) OR (what=down AND otherWire.wireLevel#H)) AND wireSize < tran.conductivity THEN wireSize ← tran.conductivity;
}
ELSE IF NOT otherWire.mark THEN FindVicinity[otherWire, what];
ENDLOOP;
FOR rps: RoseProbePrimitives ← wire.probes, rps.rest UNTIL rps=NIL DO
probe: RoseProbePrimitive ← rps.first;
IF ((what=switch AND probe.drive>none) OR (what=up AND probe.level#L) OR (what=down AND probe.level#H)) AND wireSize < probe.drive THEN wireSize ← probe.drive;
ENDLOOP;
IF what#switch AND wireSize < wire.switchDrive THEN wireSize ← none;
PushWireByStrength[wire, wireSize];
SELECT what FROM
switch => wire.switchDrive ← wireSize;
up => wire.upDrive ← wireSize;
down => wire.downDrive ← wireSize;
ENDCASE => ERROR;
};
PushStrength: PROC [what: PushWhat] = {
FOR thisDrive: Drive DECREASING IN [none..infinite) DO
firstFreeWire: CARDINAL;
UNTIL (firstFreeWire ← simulation.vicinityByStrength[thisDrive].firstFree)=0 DO
wire: RoseWire ← simulation.vicinityByStrength[thisDrive].wires[ firstFreeWire-1];
wire.mark ← FALSE;
simulation.vicinityByStrength[thisDrive].firstFree ← firstFreeWire-1;
IF thisDrive=none OR thisDrive < (SELECT what FROM
switch => wire.switchDrive,
up => wire.upDrive,
down => wire.downDrive,
ENDCASE => ERROR) THEN LOOP;
FOR rts: RoseTransistors ← wire.notOffChannels, rts.rest UNTIL rts=NIL DO
tran: RoseTransistor ← rts.first;
tranCond: Conductance ← TranOn[tran, tran.gate.wireLevel];
driveThrough: Drive ← MIN[thisDrive, tran.conductivity];
otherWire: RoseWire ← tran.ch1;
IF otherWire=wire THEN otherWire ← tran.ch2;
SELECT what FROM
switch => IF tranCond=on AND driveThrough > otherWire.switchDrive THEN {
otherWire.switchDrive ← driveThrough;
PushWireByStrength[otherWire, driveThrough];
};
up => IF driveThrough >= otherWire.switchDrive AND driveThrough > otherWire.upDrive THEN {
otherWire.upDrive ← driveThrough;
PushWireByStrength[otherWire, driveThrough];
};
down => IF driveThrough >= otherWire.switchDrive AND driveThrough > otherWire.downDrive THEN {
otherWire.downDrive ← driveThrough;
PushWireByStrength[otherWire, driveThrough];
};
ENDCASE => ERROR;
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
UpdateRecomputed: PROC = {
FOR thisWire: RoseWire ← recomputed, thisWire.nextRecomputed UNTIL thisWire=NIL DO
wireLevel: Level ← SELECT TRUE FROM
thisWire.upDrive=none AND thisWire.downDrive>=force => L,
thisWire.downDrive=none AND thisWire.upDrive>=force => H,
ENDCASE => X;
IF thisWire.wireLevel#wireLevel THEN {
FOR rts: RoseTransistors ← thisWire.gates, rts.rest UNTIL rts=NIL DO
CheckAddOrRemove: PROC [channel: RoseWire] = {
IF channel.channels#NIL THEN SELECT TRUE FROM
wasNotOff AND NOT isNotOff => {
trail: RoseTransistors ← NIL;
FOR rts: RoseTransistors ← channel.notOffChannels, rts.rest UNTIL rts=NIL DO
IF rts.first=tran THEN {
IF trail=NIL THEN channel.notOffChannels ← rts.rest
ELSE trail.rest ← rts.rest;
EXIT;
};
trail ← rts;
REPEAT FINISHED => ERROR;
ENDLOOP;
};
NOT wasNotOff AND isNotOff => channel.notOffChannels ← CONS[tran, channel.notOffChannels];
ENDCASE;
};
tran: RoseTransistor ← rts.first;
wasNotOff: BOOL ← TranOn[tran, thisWire.wireLevel]#off;
isNotOff: BOOL ← TranOn[tran, wireLevel]#off;
Perturb[simulation, tran.ch1];
Perturb[simulation, tran.ch2];
CheckAddOrRemove[tran.ch1];
CheckAddOrRemove[tran.ch2];
ENDLOOP;
thisWire.wireLevel ← wireLevel;
};
ENDLOOP;
};
recomputed: RoseWire ← NIL;
UNTIL simulation.perturbed=NIL DO
FastFindVicinity: PROC [wire: RoseWire] = {
wire.mark ← TRUE;
IF wire.wireLevel#sameValue OR wire.probes#NIL THEN {
allSameValue ← FALSE;
singleInfiniteNoUnknownConductance ← FALSE;
};
FOR rts: RoseTransistors ← wire.notOffChannels, rts.rest UNTIL rts=NIL DO
tran: RoseTransistor ← rts.first;
tranCond: Conductance ← TranOn[tran, tran.gate.wireLevel];
otherWire: RoseWire ← tran.ch1;
IF otherWire=wire THEN otherWire ← tran.ch2;
IF tranCond=unknown THEN singleInfiniteNoUnknownConductance ← FALSE;
IF otherWire.wireSize=infinite THEN {
IF infiniteFound AND infiniteValue#otherWire.wireLevel THEN singleInfiniteNoUnknownConductance ← FALSE;
infiniteFound ← TRUE;
infiniteValue ← otherWire.wireLevel;
IF otherWire.wireLevel#sameValue THEN allSameValue ← FALSE;
}
ELSE IF NOT otherWire.mark THEN FastFindVicinity[otherWire];
ENDLOOP;
{
next: RoseWire ← wire.nextPerturbedWire;
previous: RoseWire ← wire.previousPerturbedWire;
IF next#NIL THEN next.previousPerturbedWire ← previous;
IF previous#NIL THEN previous.nextPerturbedWire ← next;
IF simulation.perturbed=wire THEN simulation.perturbed ← next;
wire.nextPerturbedWire ← NIL;
wire.previousPerturbedWire ← NIL;
wire.nextRecomputed ← recomputed;
recomputed ← wire;
wire.nextVicinityWire ← vicinityWire;
vicinityWire ← wire;
};
};
ForceUpDown: PROC [up, down: Drive] = {
FOR thisWire: RoseWire ← vicinityWire, thisWire.nextVicinityWire UNTIL thisWire=NIL DO
thisWire.mark ← FALSE;
thisWire.upDrive ← up;
thisWire.downDrive ← down;
ENDLOOP;
};
wire: RoseWire ← simulation.perturbed;
vicinityWire: RoseWire ← NIL;
infiniteFound: BOOL ← FALSE;
infiniteValue: Level ← X;
singleInfiniteNoUnknownConductance: BOOL ← TRUE;
allSameValue: BOOL ← TRUE;
sameValue: Level ← wire.wireLevel;
FastFindVicinity[wire];
SELECT TRUE FROM
infiniteFound AND singleInfiniteNoUnknownConductance => {
SELECT infiniteValue FROM
L => ForceUpDown[none, infinite];
H => ForceUpDown[infinite, none];
ENDCASE => ERROR;
};
allSameValue => {
strength: Drive ← IF infiniteFound THEN infinite ELSE charge;
SELECT sameValue FROM
L => ForceUpDown[none, strength];
H => ForceUpDown[strength, none];
X => ForceUpDown[strength, strength];
ENDCASE => ERROR;
}
ENDCASE => {
FOR thisWire: RoseWire ← vicinityWire, thisWire.nextVicinityWire UNTIL thisWire=NIL DO
thisWire.mark ← FALSE;
ENDLOOP;
FindVicinity[wire, switch];
PushStrength[switch];
FindVicinity[wire, up];
PushStrength[up];
FindVicinity[wire, down];
PushStrength[down];
};
ENDLOOP;
UpdateRecomputed[];
};
Conductance: TYPE = {on, off, unknown};
TranOn: PROC [tran: RoseTransistor, gateValue: Level] RETURNS [cond: Conductance] = {
cond ← SELECT tran.transistorType FROM
nE => SELECT gateValue FROM
L => off,
H => on,
X => unknown,
ENDCASE => ERROR,
pE => SELECT gateValue FROM
L => on,
H => off,
X => unknown,
ENDCASE => ERROR,
nD => on,
ENDCASE => ERROR;
};
Perturb: PROC [simulation: RoseSimulation, wire: RoseWire] = {
IF wire.nextPerturbedWire=NIL AND wire.previousPerturbedWire=NIL AND simulation.perturbed#wire AND wire.wireSize<infinite THEN {
currentHead: RoseWire ← simulation.perturbed;
wire.nextPerturbedWire ← currentHead;
IF currentHead#NIL THEN currentHead.previousPerturbedWire ← wire;
simulation.perturbed ← wire;
};
};
Probe
Creation
CreateProbe: PUBLIC PROC [simulation: RoseSimulation, flatWire: CoreFlat.FlatWireRec] RETURNS [probe: RoseProbe] = {
fw: CoreFlat.FlatWire ← NEW[CoreFlat.FlatWireRec];
fw^ ← flatWire;
This is an interim hack that requires the argument to be an atomic, canonical wire.
probe ← NEW[RoseProbeSeq[1]];
probe[0] ← NEW[RoseProbePrimitiveRec];
probe[0].wire ← NARROW[RefTab.Fetch[x: simulation.coreToRoseWires, key: fw].val];
IF probe[0].wire=NIL THEN ERROR;
probe[0].wire.probes ← CONS[probe[0], probe[0].wire.probes];
};
BindProbe: PUBLIC PROC [simulation: RoseSimulation, cellType: Core.CellType, name: Rope.ROPE, flatCell: CoreFlat.FlatCellTypeRec ← CoreFlat.rootCellType] RETURNS [probe: RoseProbe] = {
probe ← CreateProbe[simulation, [flatCell: flatCell, wire: CoreOps.FindWire[cellType.public, name]]];
};
BindProbes: PUBLIC PROC [simulation: RoseSimulation, cellType: Core.CellType, n0, n1, n2, n3, n4: Rope.ROPE ← NIL, flatCell: CoreFlat.FlatCellTypeRec ← CoreFlat.rootCellType] RETURNS [p0, p1, p2, p3, p4: RoseProbe ← NIL] = {
IF n0#NIL THEN p0 ← BindProbe[simulation, cellType, n0, flatCell];
IF n1#NIL THEN p1 ← BindProbe[simulation, cellType, n1, flatCell];
IF n2#NIL THEN p2 ← BindProbe[simulation, cellType, n2, flatCell];
IF n3#NIL THEN p3 ← BindProbe[simulation, cellType, n3, flatCell];
IF n4#NIL THEN p4 ← BindProbe[simulation, cellType, n4, flatCell];
};
Sample
GetLevel, GL: PUBLIC PROC [p: RoseProbe] RETURNS [v: Level] = {
IF p.size#1 THEN ERROR;
v ← p[0].wire.wireLevel;
};
GetBool, GB: PUBLIC PROC [p: RoseProbe] RETURNS [v: BOOL] = {
ERROR;
};
GetInt, GI: PUBLIC PROC [p: RoseProbe] RETURNS [v: INT32] = {
ERROR;
};
GetCardinal, GC: PUBLIC PROC [p: RoseProbe] RETURNS [v: CARD32] = {
ERROR;
};
Drive
PutLevel, PL: PUBLIC PROC [p: RoseProbe, v: Level, d: Drive ← drive] = {
FOR i: NAT IN [0..p.size) DO
p[i].level ← v;
p[i].drive ← d;
ENDLOOP;
};
PutBool, PB: PUBLIC PROC [p: RoseProbe, v: BOOL, d: Drive ← drive] = {
ERROR;
};
PutInt, PI: PUBLIC PROC [p: RoseProbe, v: INT32, d: Drive ← drive] = {
ERROR;
};
PutCardinal, PC: PUBLIC PROC [p: RoseProbe, v: CARD32, d: Drive ← drive] = {
ERROR;
};
Access
GetProbeDrive, GPD: PUBLIC PROC [p: RoseProbe, index: NAT ← 0] RETURNS [d: Drive] = {
ERROR;
};
GetProbeLevel, GPL: PUBLIC PROC [p: RoseProbe] RETURNS [v: Level] = {
ERROR;
};
GetProbeBool, GPB: PUBLIC PROC [p: RoseProbe] RETURNS [v: BOOL] = {
ERROR;
};
GetProbeInt, GPI: PUBLIC PROC [p: RoseProbe] RETURNS [v: INT32] = {
ERROR;
};
GetProbeCardinal, GPC: PUBLIC PROC [p: RoseProbe] RETURNS [v: CARD32] = {
ERROR;
};
Utilities
FindLevel: PUBLIC PROC [levelID: Rope.ROPE] RETURNS [level: Level] = {
FOR lev: Level IN Level DO
IF Rope.Equal[levelNames[lev], levelID] THEN {level ← lev; EXIT};
REPEAT FINISHED => ERROR;
ENDLOOP;
};
FindDrive: PUBLIC PROC [driveID: Rope.ROPE] RETURNS [drive: Drive] = {
FOR drv: Drive IN Drive DO
IF Rope.Equal[driveNames[drv], driveID] THEN {drive ← drv; EXIT};
REPEAT FINISHED => ERROR;
ENDLOOP;
};
Data Structures
levelNames: PUBLIC ARRAY Level OF Rope.ROPE ← ["L", "H", "X"];
driveNames: PUBLIC ARRAY Drive OF Rope.ROPE ← [
"inspect", "e", "n", "cw", "cmw", "c", "cms", "cs", "f", "dw", "dmw", "d", "dms", "ds", "i"];
Hash Table Utilities
RoseWireHashNarrow: PROC [key: REF ANY] RETURNS [flat: CoreFlat.FlatWireRec] = {
WITH key SELECT FROM
wireKey: CoreFlat.FlatWire => flat ← wireKey^;
wireKey: RoseWire => flat ← wireKey.flatWire;
ENDCASE => ERROR;
};
RoseWireHash: PROC [key: REF ANY] RETURNS [hash: CARDINAL] = {
hash ← CoreFlat.FlatWireHashRec[RoseWireHashNarrow[key]];
};
RoseWireEqual: PROC [key1, key2: REF ANY] RETURNS [equal: BOOL] = {
equal ← CoreFlat.FlatWireEqualRec[RoseWireHashNarrow[key1], RoseWireHashNarrow[key2]];
};
END.