<> <> <> <> <> <> DIRECTORY Buttons, Commander, Containers, FS, IO, Rope, Rules, VFonts, ViewerClasses, ViewerIO, ViewerOps, ViewerTools; FSMTool: CEDAR PROGRAM IMPORTS Buttons, Commander, Containers, FS, IO, Rope, Rules, VFonts, ViewerIO, ViewerOps, ViewerTools = BEGIN entryHeight: CARDINAL = 15; -- how tall to make each line of items entryVSpace: CARDINAL = 8; -- vertical leading space between lines entryHSpace: CARDINAL = 10; -- horizontal space between items in a line viewerout,in,out,tempfile,results: IO.STREAM; MaxPos: INT = 70; MaxSet: INT = 70; setcnt,noutputs: INT _ 0; nspos,fileindex: INT; vnames: ARRAY [0..MaxPos) OF Rope.ROPE; sset: ARRAY [0..MaxSet] OF Rope.ROPE; filename: Rope.ROPE; MaxFact: INT = 25; MaxPI: INT = 30; MaxTerm: INT = 30; MaxInTerm: INT = 30; DontCare: INT = 0; TrueTerm: INT = 1; FalseTerm: INT = 2; EndList: INT = -1; NotCore: INT = -1; NoMerge: INT = -1; exp: REF ExpRep _ NEW[ExpRep]; ExpRep: TYPE = ARRAY [0..MaxTerm+MaxInTerm) OF ARRAY [0..MaxFact) OF INT; ptr: REF PtrRep _ NEW[PtrRep]; PtrRep: TYPE = ARRAY [0..MaxInTerm) OF INT; prodofsums: REF ProdofsumsRep _ NEW[ProdofsumsRep]; ProdofsumsRep: TYPE = ARRAY [0..MaxTerm) OF ARRAY[0..MaxPI) OF INT; ninpterms: INT; Handle: TYPE = REF FSMToolRec; FSMToolRec: TYPE = RECORD [ -- the data for a particular tool instance outer: Containers.Container _ NIL, -- handle for the enclosing container height: CARDINAL _ 0, -- height measured from the top of the container fsm: FSMViewer]; -- the FSM viewer's state MakeFSMTool: Commander.CommandProc = BEGIN my: Handle _ NEW[FSMToolRec]; my.outer _ Containers.Create[[-- construct the outer container name: "FSM Tool", iconic: TRUE, column: left, scrollable: FALSE ]]; MakeFSM[my]; ViewerOps.SetOpenHeight[my.outer, my.height]; ViewerOps.PaintViewer[my.outer, all]; END; FSMViewer: TYPE = RECORD [ input: ViewerClasses.Viewer _ NIL, output: IO.STREAM]; MakeFSM: PROC [handle: Handle] = BEGIN promptButton, computeButton: Buttons.Button; rule: Rules.Rule; handle.height _ handle.height + entryVSpace; promptButton _ Buttons.Create[ info: [ name: "Filename:", wy: handle.height, wh: entryHeight, parent: handle.outer, border: FALSE ], proc: Prompt, clientData: handle]; handle.fsm.input _ ViewerTools.MakeNewTextViewer[ [ parent: handle.outer, wx: promptButton.wx + promptButton.ww + entryHSpace, wy: handle.height+2, ww: 40*VFonts.CharWidth['0], wh: entryHeight, scrollable: FALSE, border: FALSE]]; computeButton _ Buttons.Create[ info: [ name: "Compute State Equations", wx: handle.fsm.input.wx + handle.fsm.input.ww + entryHSpace, wy: handle.height, ww:, wh: entryHeight, parent: handle.outer, border: TRUE], clientData: handle, proc: ComputeStateEquations]; handle.height _ handle.height + entryHeight + entryVSpace; rule _ Rules.Create[ [ -- create a bar to separate sections 1 and 2 parent: handle.outer, wy: handle.height, ww: handle.outer.cw, wh: 2]]; Containers.ChildXBound[handle.outer, rule]; -- constrain rule to be width of parent [ , viewerout] _ ViewerIO.CreateViewerStreams[name:"Fred", viewer:ViewerOps.CreateViewer[flavor: $TypeScript, info:[parent: handle.outer, wy: handle.height+2, ww: 100*VFonts.CharWidth['0], wh: 56 * entryHeight, scrollable: TRUE, border: FALSE]]]; handle.height _ handle.height + 10 * entryHeight; END; Prompt: Buttons.ButtonProc = BEGIN <> handle: Handle _ NARROW[clientData]; -- get our data ViewerTools.SetSelection[handle.fsm.input]; -- force the selection END; ComputeStateEquations: Buttons.ButtonProc = BEGIN handle: Handle _ NARROW[clientData]; i,j,nterms,minterms: INT; k: INT _ 0; headerFile: IO.STREAM; filename _ ViewerTools.GetContents[handle.fsm.input]; in _ FS.StreamOpen[Rope.Cat[filename, ".fsm"]]; out _ FS.StreamOpen["eqns.tmp", $create]; nspos _ Parsenames[]; FOR i IN [0..noutputs) DO setcnt _ 0; <> Findterms[Getvarpos[vnames[i+1]],"0"]; tempfile _ FS.StreamOpen["state.tmp", $create]; Termstofile[]; Convert[]; IO.Close[tempfile]; ENDLOOP; IO.Close[in]; in _ out; IO.SetIndex[in,0]; fileindex _ IO.GetIndex[in]; <> results _ FS.StreamOpen[Rope.Cat[filename, ".pal"], $create]; IO.PutF[results, Rope.Cat["\n-- File: ", filename, ".pal\n-- Created by FSMTool %g"], IO.time[]]; headerFile _ FS.StreamOpen[Rope.Cat[filename, ".hdr"]]; WHILE NOT IO.EndOf[headerFile] DO IO.PutChar[results, IO.GetChar[headerFile]]; ENDLOOP; IO.Close[headerFile]; IO.PutF[results,"BEGIN\n\n"]; WHILE (nterms _ Getexp[]) # 0 DO FOR i IN [0..MaxInTerm) DO ptr[i] _ 0; ENDLOOP; FOR i IN [0..MaxTerm) DO FOR j IN [0..MaxPI) DO prodofsums[i] [j] _ 0; ENDLOOP; ENDLOOP; ninpterms _ nterms; FOR i IN [0..nterms) DO FOR j IN [0..MaxFact) DO exp[MaxTerm + i] [j] _ exp[i] [j]; ENDLOOP; ENDLOOP; minterms _ Minimize[nterms]; IO.PutF[viewerout, "Number of terms required for %g = %g\n", IO.rope[vnames[k_k+1]], IO.int[minterms]]; Report[0,minterms,k]; ENDLOOP; IO.PutF[results,"\nEND\n"]; IO.PutF[viewerout, "\nResults are in file %g.pal\n\n", IO.rope[filename]]; IO.Close[results]; IO.Close[in]; END; SkipOver: PROC [stream: IO.STREAM, breakProc: IO.BreakProc] RETURNS [] = { c: CHAR; DO IF IO.EndOf[stream] THEN RETURN; SELECT breakProc[c _ IO.GetChar[stream]] FROM break => {IO.Backup[stream, c]; EXIT}; other => {IO.Backup[stream, c]; EXIT}; sepr => NULL ENDCASE => ERROR; ENDLOOP; }; WSButNotCR: IO.BreakProc = TRUSTED { RETURN[SELECT char FROM IO.SP, IO.TAB => sepr, ENDCASE => other]; }; NotWhiteSpace: IO.BreakProc = TRUSTED { RETURN[SELECT char FROM IO.SP, IO.TAB, IO.CR => other, ENDCASE => sepr]; }; NotCR: IO.BreakProc = TRUSTED { RETURN[SELECT char FROM IO.CR => other, ENDCASE => sepr]; }; Parsenames: PROC [] RETURNS [pos: INTEGER _ -1] = { buf: Rope.ROPE; <<--WHILE (Rope.Compare[s1:buf _ IO.GetSequence[stream: in, charProc: IO.LineAtATime], s2:"Transition", case:TRUE] < equal) AND (IO.EndOf[in] = FALSE) DO>> <<--IO.PutF[viewerout, "%g\n", IO.rope[buf]];>> <<--ENDLOOP;>> [] _ IO.SkipWhitespace[in]; DO IF IO.PeekChar[in] = IO.CR THEN { IF noutputs = 0 THEN { IO.PutF[viewerout, "Input/Output seperator '|' not found\n"]; ERROR; }; fileindex _ IO.GetIndex[in]; EXIT; }; pos _ pos+1; [buf,] _ IO.GetTokenRope [in]; IF Rope.Equal[buf,"|"] THEN { pos _ pos-1; noutputs _ pos; } ELSE { vnames[pos] _ buf; IF Duplicate[pos] THEN IO.PutF[viewerout,"%g is multiply defined at [%g]\n", IO.rope[vnames[pos]], IO.int[IO.GetIndex[in]]]; }; SkipOver[in, WSButNotCR]; ENDLOOP; }; Duplicate: PROC [n: INT] RETURNS [BOOL] = { i: INT; FOR i IN [0..n) DO IF Rope.Equal[vnames[i],vnames[n]] THEN RETURN [TRUE]; ENDLOOP; RETURN [FALSE]; }; Findterms: PROC [pos: INT, val: Rope.ROPE] = { i: INT; buf0,buf1: Rope.ROPE; IO.SetIndex[in,fileindex]; DO buf0 _ Readfield[]; IF buf0 = NIL THEN EXIT; FOR i IN [1..pos) DO Skipfield[]; ENDLOOP; buf1 _ Readfield[]; IF Rope.Equal[buf1, val] THEN Insertset[buf0]; SkipOver[in, NotCR]; ENDLOOP; }; Readfield: PROC RETURNS [Rope.ROPE] = { field: Rope.ROPE; [] _ IO.SkipWhitespace[in]; IF IO.EndOf[in] THEN RETURN[NIL]; [field,] _ IO.GetTokenRope[in]; RETURN[field]; }; Skipfield: PROC = { [] _ IO.SkipWhitespace[in]; SkipOver[in, NotWhiteSpace]; }; Insertset: PROC [t:Rope.ROPE] = { IF ~Inset[t] THEN { sset[setcnt] _ t; setcnt _ setcnt+1; }; }; Inset: PROC [t:Rope.ROPE] RETURNS [BOOL] = { i: INT; FOR i IN [0..setcnt) DO IF Rope.Equal[sset[i], t] THEN RETURN[TRUE]; ENDLOOP; RETURN[FALSE]; }; Getvarpos: PROC [buf:Rope.ROPE] RETURNS [INT] = { i: INT; FOR i IN [0..nspos] DO IF Rope.Equal[buf,vnames[i]] THEN RETURN[i]; ENDLOOP; IO.PutF[viewerout, "%g not found\n", IO.rope[buf]]; ERROR; }; Termstofile: PROC [] = { pos: INT _ -1; c: CHAR; buf,line: Rope.ROPE; IO.SetIndex[in,fileindex]; DO IF IO.EndOf[in] THEN EXIT; c _ IO.GetChar[in]; SELECT c FROM IO.CR => {IF pos >= 0 AND pos < nspos THEN IO.PutF[viewerout, "ERROR: Not enough Boolean entries at [%g]\n", IO.int[IO.GetIndex[in]]]; pos _ -1; line _ NIL; }; IO.SP, IO.TAB => NULL; ENDCASE => { pos _ pos + 1; IF pos > nspos THEN IO.PutF[viewerout, "ERROR: Too many Boolean entries at [%g]\n", IO.int[IO.GetIndex[in]]]; IF pos = nspos OR pos = 0 THEN { IO.Backup[in, c]; buf _ Readfield[]; line _ Rope.Cat[line,buf," "]; IF pos = nspos AND Inset[buf] THEN { IO.PutF[tempfile,line]; IO.PutF[tempfile, "\n"]; }; } ELSE { SELECT c FROM '0 => line _ Rope.Cat[line,"0 "]; '1 => line _ Rope.Cat[line,"1 "]; 'x,'X => line _ Rope.Cat[line,"X "]; ENDCASE => IO.PutF[viewerout, "ERROR: Illegal Boolean value at [%g]\n", IO.int[IO.GetIndex[in]]]; IF IO.EndOf[in] THEN EXIT; c _ IO.PeekChar[in]; IF c#IO.SP AND c#IO.CR AND c#IO.TAB THEN IO.PutF[viewerout, "ERROR: Illegal Boolean value at [%g]\n", IO.int[IO.GetIndex[in]]]; }; }; ENDLOOP; }; Convert: PROC [] = { pos: INT _ -1; c: CHAR; first: BOOL _ TRUE; needcr: BOOL _ FALSE; IO.SetIndex[tempfile,0]; DO IF IO.EndOf[tempfile] THEN EXIT; c _ IO.GetChar[tempfile]; SELECT c FROM IO.CR => { first _ TRUE; pos _ -1; }; IO.SP, IO.TAB => NULL; '0, '1 => { pos _ pos + 1; IF ~first THEN IO.PutF[out, " & "] ELSE { IF needcr THEN IO.PutF[out, " +\n"]; needcr _ FALSE; first _ FALSE; }; needcr _ TRUE; IF c = '0 THEN IO.PutF[out, "N"] ELSE IO.PutF[out, "A"]; IO.PutF[out, "%g", IO.int[pos]]; }; ENDCASE => { pos _ pos + 1; SkipOver[tempfile, NotWhiteSpace]; }; ENDLOOP; IO.PutF[out, ";\n\n"]; }; Getexp: PROC [] RETURNS [INT] = { i,j: INT; FOR i IN [0..MaxTerm+MaxInTerm) DO FOR j IN [0..MaxFact) DO exp[i] [j] _ 0; ENDLOOP; ENDLOOP; [] _ IO.SkipWhitespace[in]; IF IO.EndOf[in] THEN RETURN[0]; i _ 0; WHILE Getterm[i] AND (i < (MaxTerm - 1)) DO i _ i + 1; ENDLOOP; RETURN[i+1]; }; Getterm: PROC [i: INT] RETURNS[BOOL] = { k: INT; c: CHAR; WHILE (k _ Getfact[]) # 0 DO IF (k >= MaxFact) OR (k <= -MaxFact) THEN { IO.PutF[viewerout, "Factor number too big: %g\n", IO.int[k]]; ERROR; }; IF k >= 0 THEN exp[i] [k - 1] _ TrueTerm ELSE exp[i] [-(k + 1)] _ FalseTerm; [] _ IO.SkipWhitespace[in]; c _ Getop[]; SELECT c FROM '+ => RETURN[TRUE]; '; => RETURN[FALSE]; '& => NULL; ENDCASE => { IO.PutF[viewerout, "Invalid operator: %g\n", IO.char[c]]; ERROR; }; ENDLOOP; RETURN[FALSE]; }; Getfact: PROC [] RETURNS [INT] = { c: CHAR; [] _ IO.SkipWhitespace[in]; IF IO.EndOf[in] THEN RETURN[0]; c _ IO.GetChar[in]; IF c = 'a OR c = 'A THEN RETURN[IO.GetInt[in] + 1]; IF c = 'n OR c = 'N THEN RETURN[-(IO.GetInt[in] + 1)]; IO.PutF[viewerout, "Invalid operand: %g\n", IO.char[c]]; ERROR; }; Getop: PROC [] RETURNS[CHAR] = { c: CHAR; [] _ IO.SkipWhitespace[in]; IF IO.EndOf[in] THEN ERROR; c _ IO.GetChar[in]; IF c = '+ OR c = '& OR c = '; THEN RETURN[c]; IO.PutF[viewerout, "Invalid Operator: %g\n", IO.char[c]]; ERROR; }; Minimize: PROC [nterms: INT] RETURNS[INT] = { nprimes: INT; nprimes _ Findprimes[nterms]; RETURN[Selectprimes[nprimes]]; }; Findprimes: PROC [nterms: INT] RETURNS[INT] = { merged,addterm: BOOL; i,j,nt: INT; k: INT; addterm _ TRUE; WHILE addterm = TRUE DO merged _ TRUE; WHILE merged = TRUE DO merged _ FALSE; i _ 0; WHILE i < (nterms-1) DO j _ i+1; WHILE j < nterms DO IF (k _ Combine[i,j]) # NoMerge THEN { merged _ TRUE; Remove[j,nterms]; nterms _ nterms - 1; j _ j - 1; exp[i] [k] _ DontCare; }; j _ j+1; ENDLOOP; i _ i+1; ENDLOOP; ENDLOOP; nt _ nterms; FOR i IN [0..(nterms-1)) DO FOR j IN [i+1..nterms) DO IF Formcon[i,j,nt] AND Addcon[nt] THEN { IF nt < MaxTerm - 1 THEN nt _ nt+1 ELSE { IO.PutF[viewerout, "Table overflow\n"]; ERROR; }; }; ENDLOOP; ENDLOOP; addterm _ (nt # nterms); nterms _ Compact[nt]; ENDLOOP; RETURN[nterms]; }; Formcon: PROC [i,j: INT, k: INT] RETURNS [BOOL] = { ncomps: INT _ 0; m: INT; FOR m IN [0..MaxFact) DO IF exp[i] [m] = exp[j] [m] THEN exp[k] [m] _ exp[i] [m] ELSE IF exp[i] [m] = DontCare THEN exp[k] [m] _ exp[j] [m] ELSE IF exp[j] [m] = DontCare THEN exp[k] [m] _ exp[i] [m] ELSE { ncomps _ ncomps + 1; exp[k] [m] _ DontCare; }; ENDLOOP; RETURN[ncomps = 1]; }; Addcon: PROC [nt: INT] RETURNS [BOOL] = { i: INT; FOR i IN [0..nt) DO IF Subsume[nt,i] THEN RETURN[FALSE]; ENDLOOP; RETURN[TRUE]; }; Compact: PROC [nterms: INT] RETURNS [INT] = { i: INT; j: INT; i _ 0; WHILE i < (nterms-1) DO j _ i+1; WHILE j < nterms DO IF Subsume[j,i] THEN { Remove[j,nterms]; j _ j-1; nterms _ nterms-1; } ELSE IF Subsume[i,j] THEN { Remove[i,nterms]; nterms _ nterms-1; i _ i-1; EXIT; }; j _ j+1; ENDLOOP; i _ i+1; ENDLOOP; RETURN[nterms]; }; Combine: PROC [i,j: INT] RETURNS [INT] = { k,ksave: INT; ncomps: INT _ 0; FOR k IN [0..MaxFact) DO IF exp[i] [k] # exp[j] [k] THEN { IF (exp[i] [k] = TrueTerm AND exp[j] [k] = FalseTerm) OR (exp[i] [k] = FalseTerm AND exp[j] [k] = TrueTerm) THEN { ksave _ k; ncomps _ ncomps+1; } ELSE RETURN[NoMerge]; }; ENDLOOP; IF ncomps = 1 THEN RETURN[ksave]; RETURN[NoMerge]; }; Subsume: PROC [i,j: INT] RETURNS [BOOL] = { k: INT; FOR k IN [0..MaxFact) DO IF (exp[i] [k] # exp[j] [k]) AND (exp[j] [k] # DontCare) THEN RETURN[FALSE]; ENDLOOP; RETURN[TRUE]; }; Add: PROC [k,nterms: INT] RETURNS [INT] = { i: INT; IF nterms >= (MaxTerm-1) THEN { IO.PutF[viewerout, "Too many terms: %g\n", IO.int[nterms]]; ERROR; }; FOR i IN [0..MaxFact) DO exp[nterms] [i] _ exp[k] [i]; ENDLOOP; RETURN[1]; }; Remove: PROC [k,nterms: INT] = { i,j: INT; FOR i IN [k..(nterms-1)) DO FOR j IN [0..MaxFact) DO exp[i] [j] _ exp[i+1] [j]; ENDLOOP; ENDLOOP; }; Selectprimes: PROC [nprimes: INT] RETURNS [INT] = { ncore: INT; ncore _ Findcore[nprimes]; IF nprimes = ncore THEN RETURN[ncore]; nprimes _ Tossaepi[nprimes,ncore]; nprimes _ Pickrest[nprimes,ncore]; RETURN[nprimes]; }; Findcore: PROC [nprimes: INT] RETURNS [INT] = { i: INT; ncore: INT _ 0; k: INT; FOR i IN [0..ninpterms) DO IF (k _ Essentialpi[i,nprimes]) # NotCore THEN { IF k > ncore THEN Swapprime[k,ncore]; IF k >=ncore THEN ncore _ ncore+1; }; ENDLOOP; RETURN[ncore]; }; Swapprime: PROC [i,j: INT] = { temp,k: INT; FOR k IN [0..MaxFact) DO temp _ exp[i] [k]; exp[i] [k] _ exp[j] [k]; exp[j] [k] _ temp; ENDLOOP; }; Essentialpi: PROC [inpterm,nprimes: INT] RETURNS[INT] = { i,k: INT; ncover: INT _ 0; FOR i IN [0..nprimes) DO IF Subsume[MaxTerm+inpterm,i] THEN { ncover _ ncover+1; k _ i; }; ENDLOOP; IF ncover = 1 THEN RETURN[k]; RETURN[NotCore]; }; Tossaepi: PROC [nprimes,ncore: INT] RETURNS [INT] = { i: INT; j: INT; corecovered,covers: BOOL; i _ 0; WHILE i < ninpterms DO corecovered _ FALSE; FOR j IN [0..ncore) DO corecovered _ corecovered OR Subsume[MaxTerm+i,j]; ENDLOOP; IF corecovered = TRUE THEN { Remove[MaxTerm+i,MaxTerm+ninpterms]; ninpterms _ ninpterms-1; i _ i-1; }; i _ i+1; ENDLOOP; i _ ncore; WHILE i < nprimes DO covers _ FALSE; FOR j IN [0..ninpterms) DO covers _ covers OR Subsume[MaxTerm+j,i]; ENDLOOP; IF covers = FALSE THEN { Remove[i,nprimes]; nprimes _ nprimes-1; i _ i-1; }; i _ i+1; ENDLOOP; RETURN[nprimes]; }; Pickrest: PROC [nprimes,ncore: INT] RETURNS[INT] = { i,j,k,min: INT; more: BOOL; save,used: ARRAY [0..MaxPI) OF BOOL; FOR i IN [0..ninpterms) DO k _ 0; FOR j IN [ncore..nprimes) DO IF Subsume[MaxTerm+i,j] THEN { prodofsums[i] [k] _ j; k _ k+1; }; ENDLOOP; IF k = 0 THEN { IO.PutF[viewerout, "Input term %g not covered by PI\n", IO.int[i]]; ERROR; }; prodofsums[i] [k] _ EndList; ENDLOOP; more _ TRUE; min _ MaxPI; FOR i IN [0..ninpterms) DO ptr[i] _ 0; ENDLOOP; WHILE more = TRUE DO FOR i IN [ncore..nprimes) DO used[i] _ FALSE; ENDLOOP; k _ 0; FOR i IN [0..ninpterms) DO IF used[prodofsums[i] [ptr[i]]] = FALSE THEN { used[prodofsums[i] [ptr[i]]] _ TRUE; k _ k+1; }; ENDLOOP; IF k < min THEN FOR i IN [ncore..nprimes) DO save[i] _ used[i]; min _ k; ENDLOOP; more _ Stepptr[ninpterms]; ENDLOOP; k _ ncore; FOR i IN [ncore..nprimes) DO IF save[i] = TRUE THEN k _ k+1 ELSE Remove[k,nprimes]; ENDLOOP; RETURN[k]; }; Stepptr: PROC [n: INT] RETURNS [BOOL] = { i: INT; FOR i IN [0..n) DO IF prodofsums[i] [(ptr[i] _ ptr[i]+1)] # EndList THEN RETURN[TRUE] ELSE ptr[i] _ 0; ENDLOOP; RETURN[FALSE]; }; Report: PROC [nstart,nstop,nout: INT] = { i: INT; IO.PutF[results,"\n/%g ^ \n", IO.rope[vnames[nout]]]; FOR i IN [nstart..nstop) DO Printterm[i]; IF i # (nstop-1) THEN IO.PutF[results," +\n"]; ENDLOOP; IO.PutF[results,";\n\n"]; }; Printterm: PROC [i: INT] = { j: INT; first: BOOL _ TRUE; FOR j IN [0..MaxFact) DO IF exp[i] [j] = TrueTerm THEN { IF first = TRUE THEN first _ FALSE ELSE IO.PutF[results," "]; IO.PutF[results,"%g",IO.rope[vnames[j]]]; }; IF exp[i] [j] = FalseTerm THEN { IF first = TRUE THEN first _ FALSE ELSE IO.PutF[results," "]; IO.PutF[results,"/%g",IO.rope[vnames[j]]]; }; ENDLOOP; }; Commander.Register[key: "///Commands/FSMTool", proc: MakeFSMTool, doc: "Create a Finite State Machine tool" ]; [ ] _ MakeFSMTool[NIL]; -- and create an instance END.