DIRECTORY Atom, Boole, Core, CoreFlat, CoreIO, CoreOps, FiniteStateAutomata, HashTable, IO, Ports, Rope, Rosemary, TerminalIO; FiniteStateAutomataImpl: CEDAR PROGRAM IMPORTS Atom, Boole, CoreFlat, CoreIO, CoreOps, HashTable, IO, Ports, Rope, Rosemary, TerminalIO EXPORTS FiniteStateAutomata = BEGIN OPEN FiniteStateAutomata; CreateError: PUBLIC SIGNAL [msg: ROPE] = CODE; NewMachine: PUBLIC PROC [states: LIST OF ATOM] RETURNS [fsa: StateMachine] = { fsa _ NEW[StateMachineRec]; FOR s: LIST OF ATOM _ states, s.rest UNTIL s=NIL DO fsa.states _ CONS[NEW[StateRec _ [name: s.first]], fsa.states]; ENDLOOP; }; NewTransition: PUBLIC PROC [fsa: StateMachine, from, to: ATOM, expr: Expression] = { fromState: State _ FindState[fsa, from]; toState: State _ FindState[fsa, to]; fromState.transitions _ CONS[NEW[TransitionRec _ [expr, toState]], fromState.transitions]; }; NewTransitions: PUBLIC PROC [fsa: StateMachine, from: ATOM, transitions: TransitionLiterals] = { FOR t: TransitionLiterals _ transitions, t.rest UNTIL t=NIL DO NewTransition[fsa, from, t.first.to, t.first.expr]; ENDLOOP; }; FindState: PUBLIC PROC [fsa: StateMachine, state: ATOM] RETURNS [stateRef: State] = { FOR s: States _ fsa.states, s.rest UNTIL s=NIL DO IF s.first.name=state THEN { stateRef _ s.first; EXIT; }; REPEAT FINISHED => ERROR CreateError[Rope.Cat["Can't find state ", Atom.GetPName[state]]]; ENDLOOP; }; StateSeq: PUBLIC PROC [states: LIST OF ATOM, root: ROPE, count: NAT] RETURNS [newStates: LIST OF ATOM] = { newStates _ states; FOR i: NAT IN [0..count) DO newStates _ CONS[Atom.MakeAtom[IO.PutFR["%g%g", IO.rope[root], IO.card[i]]], newStates]; ENDLOOP; }; Mealy: PUBLIC PROC [fsa: StateMachine, state: ATOM, outputs: LIST OF Core.Wire, transitions: TransitionLiterals] = { statePtr: State _ FindState[fsa, state]; NewTransitions[fsa, state, transitions]; FOR o: LIST OF Core.Wire _ outputs, o.rest UNTIL o=NIL DO FOR out: Outputs _ fsa.outputs, out.rest UNTIL out=NIL DO IF o.first=out.first.output THEN { out.first.expr _ Boole.Or[out.first.expr, statePtr]; EXIT; }; REPEAT FINISHED => fsa.outputs _ CONS[[output: o.first, expr: statePtr], fsa.outputs]; ENDLOOP; ENDLOOP; }; fsaClass: Core.CellClass _ CoreIO.RegisterClass[ Rosemary.BindCellClass[NEW [Core.CellClassRec _ [name: "FSA", recast: RecastFSA, layersProps: FALSE]], Rosemary.Register["FSARoseClass", InitFSA, EvalFSA]], WriteFSA, ReadFSA]; WriteFSA: CoreIO.ClassWriteProc = { WriteExpression: PROC [expr: Boole.Expression] = { WriteVariable: PROC [out: Core.STREAM, var: Boole.Variable] = { WITH var SELECT FROM w: Core.Wire => { CoreIO.WriteID[h, "w"]; CoreIO.WriteWire[h, wireIDTab, w]; }; s: State => { CoreIO.WriteID[h, "s"]; CoreIO.WriteAtom[h, s.name]; }; ENDCASE => ERROR; }; Boole.PutExpr[out: h.stream, expr: expr, putRefAny: WriteVariable]; CoreIO.WriteID[h, NIL]; }; fsa: StateMachine _ NARROW[cellType.data]; count: INT _ 0; FOR sl: States _ fsa.states, sl.rest UNTIL sl=NIL DO count _ count + 1; ENDLOOP; CoreIO.WriteInt[h, count]; FOR sl: States _ fsa.states, sl.rest UNTIL sl=NIL DO IF sl.first.name=NIL THEN ERROR; CoreIO.WriteAtom[h, sl.first.name]; ENDLOOP; FOR sl: States _ fsa.states, sl.rest UNTIL sl=NIL DO count _ 0; FOR tl: Transitions _ sl.first.transitions, tl.rest UNTIL tl=NIL DO count _ count + 1; ENDLOOP; CoreIO.WriteInt[h, count]; FOR tl: Transitions _ sl.first.transitions, tl.rest UNTIL tl=NIL DO WriteExpression[tl.first.expr]; CoreIO.WriteAtom[h, tl.first.target.name]; ENDLOOP; ENDLOOP; count _ 0; FOR ol: Outputs _ fsa.outputs, ol.rest UNTIL ol=NIL DO count _ count + 1; ENDLOOP; CoreIO.WriteInt[h, count]; FOR ol: Outputs _ fsa.outputs, ol.rest UNTIL ol=NIL DO CoreIO.WriteWire[h, wireIDTab, ol.first.output]; WriteExpression[ol.first.expr]; ENDLOOP; CoreIO.WriteAtom[h, fsa.initialState.name]; }; ReadFSA: CoreIO.ClassReadProc = { ReadExpression: PROC RETURNS [expr: Boole.Expression] = { ReadVariable: PROC [in: Core.STREAM] RETURNS [var: Boole.Variable] = { type: ROPE _ CoreIO.ReadID[h]; var _ SELECT TRUE FROM Rope.Equal["w", type] => CoreIO.ReadWire[h, wireIDTab], Rope.Equal["s", type] => FindState[fsa, CoreIO.ReadAtom[h]], ENDCASE => ERROR; }; expr _ Boole.GetExpr[in: h.stream, getRefAny: ReadVariable]; }; fsa: StateMachine; count: INT _ CoreIO.ReadInt[h]; states: LIST OF ATOM _ NIL; FOR sc: INT IN [0..count) DO states _ CONS[CoreIO.ReadAtom[h], states]; ENDLOOP; fsa _ NewMachine[states]; FOR sl: States _ fsa.states, sl.rest UNTIL sl=NIL DO count: INT _ CoreIO.ReadInt[h]; FOR tc: INT IN [0..count) DO expr: Boole.Expression _ ReadExpression[]; target: ATOM _ CoreIO.ReadAtom[h]; NewTransition[fsa, sl.first.name, target, expr]; ENDLOOP; ENDLOOP; count _ CoreIO.ReadInt[h]; FOR oc: INT IN [0..count) DO wire: Core.Wire _ CoreIO.ReadWire[h, wireIDTab]; expr: Boole.Expression _ ReadExpression[]; fsa.outputs _ CONS[[wire, expr], fsa.outputs]; ENDLOOP; fsa.initialState _ FindState[fsa, CoreIO.ReadAtom[h]]; cellType.data _ fsa; }; FSAState: TYPE = REF FSAStateRec; FSAStateRec: TYPE = RECORD [ fsa: StateMachine _ NIL, lastClock: Ports.Level _ X, masterReset: Ports.Level _ X, masterState: State _ NIL, slaveState: State _ NIL, masterOutputs: Ports.LevelSequence _ NIL, slaveOutputs: Ports.LevelSequence _ NIL, resetPort: NAT _ 0, clockPort: NAT _ 0, ioPorts: HashTable.Table _ NIL, outputPorts: SEQUENCE size: NAT OF Ports.Port]; InitFSA: Rosemary.InitProc = { BindIO: Ports.EachWirePortPairProc = { IF port.levelType#composite THEN { IF port.levelType#l THEN ERROR; [] _ HashTable.Insert[state.ioPorts, wire, port] }; }; state: FSAState; fsa: StateMachine _ NARROW[cellType.data]; ffOut: NAT _ 0; FOR outs: Outputs _ fsa.outputs, outs.rest UNTIL outs=NIL DO ffOut _ ffOut + 1; ENDLOOP; state _ NEW[FSAStateRec[ffOut]]; state.fsa _ fsa; state.masterOutputs _ NEW[Ports.LevelSequenceRec[ffOut]]; state.slaveOutputs _ NEW[Ports.LevelSequenceRec[ffOut]]; FOR i: NAT IN [0..ffOut) DO state.masterOutputs[i] _ state.slaveOutputs[i] _ X; ENDLOOP; state.resetPort _ Ports.PortIndex[cellType.public, "Reset"]; state.clockPort _ Ports.PortIndex[cellType.public, "Clock"]; state.ioPorts _ HashTable.Create[]; IF Ports.VisitBinding[cellType.public, p, BindIO] THEN ERROR; ffOut _ 0; FOR outs: Outputs _ fsa.outputs, outs.rest UNTIL outs=NIL DO state.outputPorts[ffOut] _ NARROW[HashTable.Fetch[state.ioPorts, outs.first.output].value]; state.outputPorts[ffOut].d _ drive; ffOut _ ffOut + 1; ENDLOOP; IF ffOut#state.size THEN ERROR; stateAny _ state; }; EvalFSA: Rosemary.EvalProc = { EvalStateOrWire: PROC [var: Boole.Variable] RETURNS [expr: Expression] = { WITH var SELECT FROM s: State => expr _ SELECT TRUE FROM state.masterReset=H => IF s=fsa.initialState THEN Boole.true ELSE Boole.false, state.masterState=NIL => NIL, s=state.masterState => Boole.true, ENDCASE => Boole.false; w: Core.Wire => { p: Ports.Port _ NARROW[HashTable.Fetch[state.ioPorts, w].value]; expr _ SELECT p.l FROM L => Boole.false, H => Boole.true, X => NIL, ENDCASE => ERROR; }; ENDCASE => ERROR; }; EvalExpr: PROC [expr: Expression] RETURNS [level: Ports.Level] = { level _ SELECT Boole.FullEval[expr, EvalStateOrWire] FROM NIL => X, Boole.true => H, Boole.false => L ENDCASE => ERROR; }; state: FSAState _ NARROW[stateAny]; fsa: StateMachine _ state.fsa; SELECT TRUE FROM p[state.clockPort].l=L => { outs: Outputs _ fsa.outputs; state.masterReset _ p[state.resetPort].l; state.masterState _ NIL; IF state.slaveState#NIL AND state.masterReset=L THEN { FOR trans: Transitions _ state.slaveState.transitions, trans.rest UNTIL trans=NIL DO transVal: Ports.Level _ EvalExpr[trans.first.expr]; SELECT TRUE FROM transVal=X OR (transVal=H AND state.masterState#NIL AND state.masterState#trans.first.target) => { state.masterState _ NIL; EXIT; }; transVal=H => state.masterState _ trans.first.target; ENDCASE; ENDLOOP; }; FOR out: NAT IN [0..state.masterOutputs.size) DO state.masterOutputs[out] _ EvalExpr[outs.first.expr]; outs _ outs.rest; ENDLOOP; }; state.lastClock=L AND p[state.clockPort].l=H => { FOR out: NAT IN [0..state.slaveOutputs.size) DO state.slaveOutputs[out] _ state.masterOutputs[out]; ENDLOOP; state.slaveState _ SELECT state.masterReset FROM H => fsa.initialState, L => state.masterState, X => NIL, ENDCASE => ERROR; }; ENDCASE; FOR out: NAT IN [0..state.slaveOutputs.size) DO state.outputPorts[out].l _ state.slaveOutputs[out]; ENDLOOP; state.lastClock _ p[state.clockPort].l; }; RecastFSA: Core.RecastProc = { ERROR; }; StateMachineCell: PUBLIC PROC [public: Core.Wire, fsa: StateMachine, name: ROPE _ NIL, props: Core.Properties _ NIL, completeCheck: BOOL _ FALSE, assert: Boole.Expression _ Boole.true] RETURNS [cellType: Core.CellType] = { CheckPublic: PROC [var: Boole.Variable] = { IF NOT ISTYPE[var, Core.Wire] THEN SIGNAL CreateError["Some transition variable is not a wire"]; IF NOT CoreOps.RecursiveMember[public, NARROW[var]] THEN SIGNAL CreateError["Some wire variable is not a member of the public"]; }; CheckStateOrPublic: PROC [var: Boole.Variable] = { WITH var SELECT FROM s: State => FOR states: States _ fsa.states, states.rest UNTIL states=NIL DO IF s=states.first THEN EXIT; REPEAT FINISHED => SIGNAL CreateError["Some expression state is not a state of the state machine"]; ENDLOOP; w: Core.Wire => CheckPublic[var]; ENDCASE => SIGNAL CreateError["Some variable is not a state or public wire"]; }; SetL: PROC [wire: Core.Wire] = {[] _ Ports.InitPort[wire, l]}; targetStates: HashTable.Table _ HashTable.Create[]; CoreOps.VisitRootAtomics[public, SetL]; cellType _ CoreOps.CreateCellType[class: fsaClass, public: public, data: fsa, name: name, props: props]; [] _ CoreFlat.CellTypeCutLabels[cellType, "FSA"]; IF CoreOps.GetWireIndex[cellType.public, "Reset"]<0 THEN SIGNAL CreateError["Cannot find Reset in public"]; IF CoreOps.GetWireIndex[cellType.public, "Clock"]<0 THEN SIGNAL CreateError["Cannot find Clock in public"]; FOR outs: Outputs _ fsa.outputs, outs.rest UNTIL outs=NIL DO IF NOT CoreOps.RecursiveMember[public, outs.first.output] THEN SIGNAL CreateError["Some output is not a member of the public"]; Boole.EnumerateVars[outs.first.expr, CheckStateOrPublic]; ENDLOOP; FOR states: States _ fsa.states, states.rest UNTIL states=NIL DO IF states.first.transitions=NIL THEN SIGNAL CreateError["Some state is not a source state"]; FOR trans: Transitions _ states.first.transitions, trans.rest UNTIL trans=NIL DO Boole.EnumerateVars[trans.first.expr, CheckPublic]; [] _ HashTable.Insert[targetStates, trans.first.target, $Target]; ENDLOOP; ENDLOOP; FOR states: States _ fsa.states, states.rest UNTIL states=NIL DO IF HashTable.Fetch[targetStates, states.first].value=NIL AND states.first#fsa.initialState THEN SIGNAL CreateError["Some state is not a target state"]; ENDLOOP; IF completeCheck THEN ValidateFSA[CoreOps.InheritCellTypeName[cellType], fsa, assert]; }; ValidateFSA: PROC [name: ROPE, fsa: StateMachine, assert: Expression _ Boole.true] ~ { FOR states: States _ fsa.states, states.rest WHILE states#NIL DO from: State = states.first; all: Expression _ Boole.Not[assert]; FOR transitions: Transitions _ from.transitions, transitions.rest WHILE transitions#NIL DO e1: Expression = transitions.first.expr; s1: State = transitions.first.target; all _ Boole.Or[all, e1]; FOR others: Transitions _ transitions.rest, others.rest WHILE others#NIL DO e2: Expression = others.first.expr; s2: State = others.first.target; IF ~Boole.Equal[Boole.And[e1, e2, assert], Boole.false] THEN { TerminalIO.PutF["Conflicting transition from %g to %g and %g because %g is not FALSE in cell type %g\n", IO.atom[from.name], IO.atom[s1.name], IO.atom[s2.name], IO.rope[FSAExprToRope[Boole.Not[Boole.And[e1, e2, assert]]]], IO.rope[name]]; SIGNAL CreateError["See terminal"]; }; ENDLOOP; ENDLOOP; IF ~Boole.Equal[all, Boole.true] THEN { TerminalIO.PutF["Transitions from %g do not cover all cases because %g is not TRUE in cell type %g\n", IO.atom[from.name], IO.rope[FSAExprToRope[all]], IO.rope[name]]; SIGNAL CreateError["See terminal"]; }; ENDLOOP; }; FSAExprToRope: PROC [expr: Expression] RETURNS [ROPE] = { PrintVar: PROC [out: IO.STREAM, var: Boole.Variable] ~ { out.Put1[WITH var SELECT FROM w: Core.Wire => IO.rope[CoreOps.GetShortWireName[w]], s: State => IO.atom[s.name], ENDCASE => IO.rope["???"] ]; }; out: IO.STREAM _ IO.ROS[]; Boole.PutExpr[out: out, expr: expr, putRefAny: PrintVar]; RETURN [IO.RopeFromROS[out]]; }; END. ÒFiniteStateAutomataImpl.mesa Copyright c 1986 by Xerox Corporation. All rights reserved. Barth, November 3, 1986 11:03:16 am PST Bertrand Serlet December 17, 1986 6:45:55 am PST Creation WREqual: PROC [wr1, wr2: CoreCreate.WR] RETURNS [yes: BOOL] = { yes _ WITH wr1 SELECT FROM w1: CoreCreate.Wire => WITH wr2 SELECT FROM w2: CoreCreate.Wire => w1=w2, r2: ROPE => Rope.Equal[CoreOps.GetShortWireName[w1], r2], t2: REF TEXT => Rope.Equal[CoreOps.GetShortWireName[w1], Rope.FromRefText[t2]], ENDCASE => ERROR, r1: ROPE => WITH wr2 SELECT FROM w2: CoreCreate.Wire => Rope.Equal[r1, CoreOps.GetShortWireName[w2]], r2: ROPE => Rope.Equal[r1, r2], t2: REF TEXT => Rope.Equal[r1, Rope.FromRefText[t2]], ENDCASE => ERROR, t1: REF TEXT => WITH wr2 SELECT FROM w2: CoreCreate.Wire => Rope.Equal[Rope.FromRefText[t1], CoreOps.GetShortWireName[w2]], r2: ROPE => Rope.Equal[Rope.FromRefText[t1], r2], t2: REF TEXT => Rope.Equal[Rope.FromRefText[t1], Rope.FromRefText[t2]], ENDCASE => ERROR, ENDCASE => ERROR; }; Core Connection fsaClass: Core.CellClass _ CoreIO.RegisterClass[ Rosemary.BindCellClass[NEW [Core.CellClassRec _ [name: "FSA", recast: RecastFSA, properties: CoreProperties.Props[[PWCore.layoutAtomProp, $Recast]]]], Rosemary.Register["FSARoseClass", InitFSA, EvalFSA]], WriteFSA, ReadFSA]; [h: Handle, cellType: Core.CellType, wireIDTab: HashTable.Table, clientData: REF ANY _ NIL]; [h: Handle, cellType: Core.CellType, wireIDTab: HashTable.Table, clientData: REF ANY _ NIL]; Ê>˜codešœ™Kšœ Ïmœ1™K˜3Kšžœ˜—Kšœ˜J˜—š Ÿ œžœžœžœžœ˜Ušžœ žœžœž˜1šžœžœ˜K˜Kšžœ˜K˜—KšžœžœžœB˜ZKšžœ˜—Kšœ˜J˜—šŸœžœžœ žœžœžœžœ žœžœ žœžœžœ˜jKšœ˜šžœžœžœ ž˜Kš œ žœžœžœ žœ˜XKšžœ˜—Kšœ˜J˜—š Ÿœžœžœžœžœ™?šœžœžœž™šœžœžœž™+Kšœ™Kšœžœ1™9KšœžœC™OKšžœžœ™—šœžœžœžœž™ KšœD™DKšœžœ™Kšœžœ)™5Kšžœžœ™—šœžœžœžœž™$KšœV™VKšœžœ)™1Kšœžœ;™GKšžœžœ™—Kšžœžœ™—Kšœ™J™—š Ÿœžœžœžœ žœžœ0˜tK˜(K˜(š žœžœžœžœžœž˜9šžœ&žœžœž˜9šžœžœ˜"Kšœ4˜4Kšžœ˜K˜—Kšžœžœžœ1˜VKšžœ˜—Kšžœ˜—Kšœ˜J˜——™šœ0™0Jšœžœ²™ÌJšœ™J™—šœ0˜0JšœžœDžœ9˜œJšœ˜J™—šŸœ˜#KšœMžœžœžœ™\J˜šŸœžœ˜2šŸ œžœ žœ˜?šžœžœž˜šœ˜Jšœ˜Jšœ"˜"J˜—šœ ˜ Jšœ˜Jšœ˜J˜—Jšžœžœ˜—J˜—KšœC˜CKšœžœ˜J˜J˜—Jšœžœ˜*Jšœžœ˜šžœ"žœžœž˜4J˜Jšžœ˜—J˜šžœ"žœžœž˜4Jšžœžœžœžœ˜ J˜#Jšžœ˜—šžœ"žœžœž˜4J˜ šžœ1žœžœž˜CJ˜Jšžœ˜—J˜šžœ1žœžœž˜CJ˜Jšœ*˜*Jšžœ˜—Jšžœ˜—J˜ šžœ$žœžœž˜6J˜Jšžœ˜—J˜šžœ$žœžœž˜6Jšœ0˜0Jšœ˜Jšžœ˜—Jšœ+˜+K˜K™—šŸœ˜!KšœMžœžœžœ™\J˜šŸœžœžœ˜9šŸ œžœ žœžœ˜FKšœžœ˜šœžœžœž˜Jšœ7˜7Jšœ<˜K˜3Kšœ'˜'Kšœh˜hKšœ1˜1Kšžœ2žœžœ,˜kKšžœ2žœžœ,˜kšžœ(žœžœž˜Kš œižœžœžœžœ<žœ ˜îKšžœ˜#K˜—Kšžœ˜—Kšžœ˜—šžœžœž˜'Kšœgžœžœžœ ˜§Kšžœ˜#K˜—Kšžœ˜—K˜K˜—šŸ œžœžœžœ˜9šŸœžœžœžœ˜8šœ žœžœž˜Kšœžœ#˜5Kšœ žœ˜Kšžœžœ ˜Kšœ˜—K˜—Jš œžœžœžœžœ˜Jšœ9˜9Jšžœžœ˜J˜J˜—Kšžœ˜—…—0HFX