untitled

Size: px

Start display at page:

Download "untitled"

攸均刘
5 years ago
Views:

1 ()PLD [1] Miro Samek, Ph.D Practical Statecharts in C/C++ Quantum Programming for Embedded Systems [2] OpenFans FSM Finite State Machine HSM Hierarchical State Machine OOP Object Oriented Programming UML Unified Modeling Language LSP Liskov Substitution Principle PoC push to talk over cellular

3 FSM FSM FSM State() Guard() Event() Action() Transition FSM FSM C Parser() Calc() HSM programming-by-difference HSM HSM OOP state inheritance and class inheritance Entry/Exit Actions and Construction/Destruction(/ /) programming-by-difference abstraction() HSM Calc Transition HSM PoC Audio Player PoC Call Control FSM nestted switch statement switch state table() i

4 7.3 Function Address As State() QFSM frame(qfsm ) HSM ii

5 2-1 Keyboard FSM in UML format Keyboard FSM in UML format C comment parser (CParser) FSM Basic Calc Example Basic Calc FSM Basic Calc FSM add Result state Basic Calc FSM add Result state and Cancel event Simple Calc HSM HSM conception substate of operandx Full Calc HSM State Tree of Calc HSM of audio Player HSM of Call Control i

7 1 20 David Harel UML FSM HSM FSM HSM C 1-1

9 2FSM 2.1 FSM 2.2 FSM State() State() Guard() guardguard Event() Event Action() EventAction() Event 2-1

10 2.2.5 Transition Transition triggering event trigger 2.3 FSM 2-1UML FSM initial transition final transition state ANY_KEY / generate lowercase code default ANY_KEY [ keystrokes > ] CAPS_LOCK CAPS_LOCK State transition capslocked ANY_KEY [ keystrokes > ] ANY_KEY / generate uppercase code Self transition guard trigger action list 2-1 Keyboard FSM in UML format 1 Statestate 2-2

11 2 FSM TransitionEvent [guard]/action Initial Transition Initial TransitionFSM initial transitionevent action Final Transition FSM Internal Transition UML state state internal-transition Keyboard FSM in UML format 2 2-3

13 3FSM 2 FSM 3.1 C Parser().C.C C /* *//* */ code// (1) a = b * c / d; /* calc expression is b*c/d. **/ (2) Event CHAR SLASH STAR (3) Initial Transition code idle code (4) state transition code CHAR STAR code SLASH SLASH slash slash STAR STAR comment CHAR SLASH SLASH code code comment code star slash 3-1

14 SLASH code CHAR, STAR CHAR SLASH star slash STAR CHAR STAR STAR SLASH comment CHAR, SLASH 3-1 C comment parser (CParser) FSM 3.2 Calc() operand1 operator operand2 '=' operand1 operand2 + - * /C CEClear Entry

15 3 FSM 3-2 Basic Calc Example 1 expression ::= operand1 operator operand2 '=' 2 operand1 ::= expression ['+' ' '] number 3 operand2 ::= ['+' ' '] number 4 number ::= {'0' '1'... '9'* ['.' {'0' '1'... '9'*] 5 operator ::= '+' ' ' '*' '/' (1) operand1 operator operand2 '=' 1+2= operand1 1 OpEntered operand

16 (2) Initial Transition operand1 (3) Event Transition operand1 operator+ - * / opentered operand20~9 operand2 operand2 operand1 = operand1 3-3 operand1 PLUS, MINUS, MULTIPLY, DIVIDE opentered EQUALS 0~9, POINT operand2 3-3 Basic Calc FSM (4) 3-3= operand1 3-4

17 3 FSM resultresult3 1) operatoroperand1 2) Cancel 3) operand * /OPER operand1 0~9, POINT OPER C opentered OPER result 0~9, POINT EQUALS operand2 3-4 Basic Calc FSM add Result state (5) 3-4Cancelresult Cancel

18 3-5 Basic Calc FSM add Result state and Cancel event (6) 3-5Cancel HSM FSMFSM HSM

19 3 FSM Calc operand1 OPER 0~9, POINT C opentered OPER result 0~9, POINT EQUALS operand2 3-6 Simple Calc HSM HSM 3-7

21 4HSM 4.1 programming-by-difference HSM programming-by-difference 4-1 GUI system GUI MS-Windows GUI GUI GUI MS-Windows MS-Windows GUI GUI look and feel David Harel FSM HSM 4.2 HSM HSM 4-2 A) 4-2 B) 2-1, 2-2 superstate substate 4-1

22 4-2 HSM conception Event Event substate substate Event superstate 4.3 HSM OOP HSM OOP OOP 3 abstraction inheritancepolymorphism state inheritance and class inheritance OOP class inheritance behavioral inheritance 4-2 substate superstate substate superstate, substate superstate 4-2

23 4 HSM failed substate unsafe unsafe failed is-in-a-state is-a-kind-of 4-3 Example of HSM Entry/Exit Actions and Construction/Destruction(/ /) Entry Exit ConstructionDestruction Construction Destruction Entry Exit programming-by-difference 4-3

24 4.3.4 abstraction() OOP HSM zoom in zoom out 4-4

25 5HSM HSM 5.1 Calc Calc HSM (7) operand1 operand2 0 operandx substate of operandx (8) CECancel Entry Calc HSM

26 C IDCANCEL Calc ready negated1 Entry/ result begin OPER[keyid == PLUS] OPER[keyid==MINUS] CE Entry/ CE POINT POINT operand1 OPER zero1 int1 1~9 POINT 0/ 1...9/ 0/ 1...9/ frac1 EQUALS POINT OPER opentered OPER[keyid==MINUS] nagated2 CE Entry/ OPER CE POINT POINT operand2 zero2 int2 1~9 POINT 0/ 1...9/ 0/ 1...9/ frac2 POINT 5-2

27 5 HSM 5-2 Full Calc HSM 5-2 zoom inzoom out level HSM 5.2 Liskov Substitution Principle LSPLSP LSP LSP HSM Event Action Transition, LSP LSP HSM LSP zoom out 5-3

28 LSP 1988 B. Meyer Design by ContractDBC 1) (Pre-condition) 2) (Post-condition) 3) (Invariant) LSP LSP 5-2 LSP begin OPER[key==MINUS] ready OPER LSP Transition entry/exit HSM FSM 5-2 state

29 5 HSM 5-3 State Tree of Calc least common ancestorlca LCA exit transition action LCA entry int2 result int2 exitoperand2 exit ready entryresult entry 5-5

30 6HSM PoC HSM 6.1 PoC Audio Player audio player audio handle audio buffer audio audio playerplay audio R:ReceiveS:Send (1) Initial transitionidle (2) idlepoc_audio_start_play_req dejitter (3) dejitter timertimeraudio handle bufferaudio StartPlay POC_AUDIO_PLAY_OK_INDdejitter buffer guard PlayDone internal-transition (4) PlayDonePOC_AUDIO_START_PLAY_REQ StartPlay 6-6

31 6 HSM (5) PlayingStartPlay PlayDonePOC_STOP_PLAY_REQ audio handlelsp (6) audiostartplay POC_SPEECH_PLAYER_SET_PARAM_REQ audio Player internal-transition Player R:POC_SPEECH_PLAYER_SET_PARAM_REQ/ Idle R:POC_CLOSE_PLAYER_HANDLE_CNF / ClosePlayerHandle R:POC_STOP_PLAY_REQ R:POC_AUDIO_START_PLAY_REQ / R:POC_AUDIO_PLAYER_STOP_CNF / POCADAP_AudioClosePlayerHandle() Dejitter Entry/StartTimer Exit/StopTimer StopPlay R:POC_DEJITTER_TIME_OUT_IND / POCADAP_AudioCreatePlayerHandle() And POCADAP_AudioStartPlay() R:POC_STOP_PLAY_REQ / POCADAP_AudioStopPlay() Playing StartPlay R:POC_AUDIO_PLAY_OK_IND / FreePlayedData() and If (has_data_to_play) POCADAP_AudioSetDataAndPlay() R:POC_SPEECH_PLAYER_SET_PARAM_REQ/ POCADAP_AudioSetPlayerParams R:POC_AUDIO_PLAY_OK_IND / FreePlayedData() and If (has_no_data_to_play) R:POC_SPEECH_PLAY_REQ / If (has_data_to_play) POCADAP_AudioSetDataAndPlay() PlayDone R:POC_AUDIO_START_PLAY_REQ / If (has_no_data_to_play) 6-1 HSM of audio Player POC_STOP_PLAY_REQ POC_SPEECH_PLAYER_SET_PARAM_REQ 6.2 PoC Call Control Call Control (SIP POC ) 6-7

32 Call R:POC_MOCALL_REQ Idle R:SIP_CALL_DISCONNECT_IND / S:POC_CALL_DISCONNECT_IND And S:POC_CP_SESSION_RELEASE_IND R:SIP_LEAVE_CALL_OK_CNF / S:POC_CALL_DISCONNECT_IND And Enter RelResource R:POC_MOCALL_REQ / POCADAP_SIPMakeCall() R:SIP_MTCALL_IND / R:SIP_TEMP_UNAVAILABLE_IND S:POC_MTCALL_IND / Or R:SIP_REQUEST_TIME_OUT / Or R:SIP_MOCALL_FAIL_CNF / S:POC_MOCALL_ESTABLISH_FAIL_IND R:POC_REJECT_MTCALL_RSP / POCADAP_SIPRejectCall() R: POC_PENDING_MT_TIME_OUT_IND/ S:POC_MTCALL_ESTABLISH_FAIL_IND POCADAP_SIPMTCallTimeOut() IncomingMT PendingRelease PendingMO R:SIP_CALL_TRYING_IND/ S:POC_MOCALL_PROCESSING_IND SIP_CALL_RINGING_IND/ S:POC_MOCALL_RINGING_IND Entry/ StartTimer Exi/ StopTimer R:POC_ANSWER_MTCALL_RSP / POCADAP_SIPAnswerCall() PendingMTAnswer R:POC_LEAVE_CALL_REQ/ POCADAP_SIPLeaveCall() And S:POC_CP_SESSION_REL_STEP1_IND R:SIP_MOCALL_OK_CNF / S: POC_MOCALL_ESTABLISH_CNF And S:POC_CP_MO_ESTABLISH_IND R:SIP_MTCALL_ACK / S:POC_MTCALL_ESTABLISH_CNF And S:POC_CP_MT_ESTABLISH_IND Estab R:SIP_REFRESH_SESSION_IND/ POCADAP_SIPRefreshSession() R:SIP_LEAVE_CALL_IND/S:POC_LEAVE_CALL_IND 6-2 HSM of Call Control (1)POC_MOCALL_REQ HSM PendingRelease Callaction (2) SIP_CALL_DISCONNECT_INDidleevent 6-8

33 7FSM FSM C CParser FSM 3-1 dispatch state transition Initial Transition CLASS SUBCLASS C++ 2 C STRUCTURE 7.1 nestted switch statement switch Cparser1.h enum Signal { /* enumeration for CParser signals */ CHAR_SIG, STAR_SIG, SLASH_SIG ; enum State { /* enumeration for CParser states */ CODE, SLASH, COMMENT, STAR ; struct CParser1 { enum State state ; /* the scalar state-variable */ long commentctr ; /* comment character counter */ /*... */ /* other CParser1 attributes */ ; #define CParser1Tran(me_, target_) ((me_)->state = target_) Cparser1.c void CParser1Dispatch(CParser1 *me, unsigned const sig) { switch (me->state ) { case CODE: switch (sig) { case SLASH_SIG: CParser1Tran(me, SLASH); /* transition to "slash" */ case SLASH: switch (sig) { case STAR_SIG: me->commentctr += 2; /* SLASH-STAR count as comment */ CParser1Tran(me, COMMENT); /* transition to "comment" */ case CHAR_SIG: CParser1Tran(me, CODE); /* go back to "code" */ case COMMENT: switch (sig) { 7-1

34 case STAR_SIG: CParser1Tran(me, STAR); /* transition to "star" */ case CHAR_SIG: case SLASH_SIG: ++me->commentctr ; /* count the comment char */ case STAR: switch (sig) { case STAR_SIG: ++me->commentctr ; /* count STAR as comment */ case SLASH_SIG: me->commentctr += 2; /* count STAR-SLASH as comment */ CParser1Tran(me, CODE); /* transition to "code" */ case CHAR_SIG: me->commentctr += 2; /* count STAR-? as comment */ CParser1Tran(me, COMMENT); /* go back to "comment" */ FSM 2 switch case switch case switch case 7.2 state table() Cparser2.h CLASS(Tran) Action action; unsigned nextstate; METHODS END_CLASS enum State { /* enumeration for CParser states */ CODE, SLASH, COMMENT, STAR, MAX_STATE ; Cparser2.c void StateTableDispatch(StateTable *me, unsigned const sig) { register Tran const *t = me->table + 7-2

35 7 FSM me->state *me->nsignals + sig; (t->action)(me); me->state = t->nextstate; void StateTableDoNothing(StateTable *me) { static Tran const loctable[max_state][max_sig] = { {{StateTableDoNothing, CODE, {StateTableDoNothing, CODE, {StateTableDoNothing, SLASH, {{StateTableDoNothing, CODE, {(Action)CParserA2, COMMENT, {StateTableDoNothing, CODE, {{(Action)CParserA1, COMMENT, {StateTableDoNothing,STAR, {(Action)CParserA1, COMMENT, {{(Action)CParserA2, COMMENT, {(Action)CParserA1, STAR, {(Action)CParserA2, CODE ; void CParserA1(CParser2 *me) { me->commentctr += 1; void CParserA2(CParser2 *me) { me->commentctr += 2; FSM nestted switch statement state event 2 action transition 7.3 Function Address As State() Cparser4.h typedef void /* return value */ (*State) /* pointer-to-member name */ (Fsm *me, /* class the function pointer is a member of */ unsigned const sig); /* the rest of the argument list */ struct Fsm { State state_; /* protected current state */ ; #define FsmDispatch(me_, sig_) ((*(me_)->state_)((me_), sig)) #define TRAN(target_) (((Fsm *)me)->state_ = (State)(target_)) EntryExit 7-3

36 #define TRAN(target_) do{ \ *((Fsm *)me)->state_)((me), EXIT_SIG); \ ((Fsm *)me)->state = (State)(target_); \ *((Fsm *)me)->state_)((me), ENTRY_SIG); \ while(0) Cparser4.c void CParser4code(CParser4 *me, unsigned const sig) { switch (sig) { case SLASH_SIG: TRAN(CParser4slash); /* transition to "slash" */ void CParser4slash(CParser4 *me, unsigned const sig) { switch (sig) { case STAR_SIG: me->commentctr += 2; /* SLASH-STAR chars count as comment */ TRAN(CParser4comment); /* transition to "comment" */ case CHAR_SIG: TRAN(CParser4code); /* go back to "code" */ void CParser4comment(CParser4 *me, unsigned const sig) { static const void (*lookup[])(cparser4 *) = { CParser4commentOnCHAR, CParser4commentOnSTAR, CParser4commentOnSLASH ; REQUIRE(sig <= SLASH_SIG); /* signal must be in range */ (*lookup[sig])(me); /* rapidly dispatch without 'switch' */ void CParser4star(CParser4 *me, unsigned const sig) { switch (sig) { case STAR_SIG: ++me->commentctr ; /* count '*' as comment character */ case CHAR_SIG: me->commentctr += 2; /* count STAR-? as comment */ TRAN(CParser4comment); /* go back to "comment" */ case SLASH_SIG: me->commentctr += 2; /* count STAR-SLASH as comment */ TRAN(CParser4code); /* transition to "code" */ FSM state (State) CParser4slash() CParser4slash slash 7-4

37 7 FSM event FsmDispatch() state entry/exit nestted switch statement state table 7.4 QFSM frame(qfsm ) qfsm.h SUBCLASS(QFsm, Object) /* Quantum Finite State Machine base class */ QFsmState state ; /* the active state */ VTABLE(QFsm, Object) #define QFsmDispatch(me_, e_) (*(me_)->state )((me_), (e_)) #define QFSM_TRAN(target_) \ (((QFsm *)me)->state = (QFsmState)(target_)) EntryExit QFSM_TRAN(me, target_) do{\ { \ QEvent e; \ e.sig = EXIT_SIG; \ (*(me)->state )((me), (e_)); \ ((QFsm *)me)->state = (QFsmState)(target_); \ e.sig = ENTRY_SIG; \ (*(me_)->state )((me), (e_)); \ while(0) Cparser5.h #include qfsm.h enum Event { /* enumeration for CParser events */ CHAR_SIG = Q_USER_SIG, STAR_SIG, SLASH_SIG ; SUBCLASS(CParser5, QFsm) long commentctr ; /* comment character counter */ METHODS CParser5 *CParser5Ctor(CParser5 *me); /* Ctor */ void CParser5initial(CParser5 *me, QEvent const *e); void CParser5code(CParser5 *me, QEvent const *e); void CParser5slash(CParser5 *me, QEvent const *e); void CParser5comment(CParser5 *me, QEvent const *e); void CParser5star(CParser5 *me, QEvent const *e); #define CParser5GetCommentCtr(me_) ((me_)->commentctr ) END_CLASS 7-5

38 Cparser5.c void CParser5code(CParser5 *me, QEvent const *e) { switch (e->sig) { case SLASH_SIG: QFSM_TRAN(CParser5slash); /* transition to "slash" */ void CParser5slash(CParser5 *me, QEvent const *e) { switch (e->sig) { case STAR_SIG: me->commentctr += 2; /* SLASH-STAR count as comment */ QFSM_TRAN(CParser5comment); /* transition to "comment" */ case CHAR_SIG: QFSM_TRAN(CParser5code); /* go back to "code" */ void CParser5comment(CParser5 *me, QEvent const *e) { switch (e->sig) { case STAR_SIG: QFSM_TRAN(CParser5star); /* transition to "star" */ case CHAR_SIG: case SLASH_SIG: ++me->commentctr ; /* count the comment character */ void CParser5star(CParser5 *me, QEvent const *e) { switch (e->sig) { case STAR_SIG: ++me->commentctr ; /* count '*' as comment character */ case CHAR_SIG: me->commentctr += 2; /* count STAR-? as comment */ QFSM_TRAN(CParser5comment); /* go back to "comment" */ case SLASH_SIG: me->commentctr += 2; /* count STAR-SLASH as comment */ QFSM_TRAN(CParser5code); /* transition to "code" */ QFSM Function Address As State fsm framework qfsm.h qfsm.c Miro Samek, Ph.D FSM UML code entry/exit 7-6

39 7 FSM 7-7

41 8HSM qhsm.h Calc HSM 5-2 QHSM QFSM initial transition SUBCLASS(QHsm, Object) /* Hierarchical State Machine base class */ QState state ; /* the active state */ QState source ; /* source state during a transiton */ VTABLE(QHsm, Object) void QHsmDispatch(QHsm *me, QEvent const *e); /* take RTC step */ #define Q_TRAN(target_) if (1) { \ static Tran_ t_; \ QHsmTranStat_((QHsm *)me, &t_, (QState)(target_));\ #define Q_TRAN_DYN(target_) \ QHsmTran_((QHsm *)me, (QState)(target_)) calc.h #include "qhsm.h" SUBCLASS(CalcEvt, QEvent) int keyid; /* ID of the key depressed */ METHODS END_CLASS SUBCLASS(Calc, QHsm) HWND hwnd_; /* the calculator window handle */ BOOL ishandled_; char display_[40]; char *ins_; double operand1_; double operand2_; int operator_; METHODS Calc *CalcCtor(Calc *me); void CalcXtor(Calc *me); Calc *CalcInstance(int id); /* static Singleton accessor method */ void Calc_initial(Calc *me, QEvent const *e); QSTATE Calc_calc(Calc *me, QEvent const *e); QSTATE Calc_ready(Calc *me, QEvent const *e); QSTATE Calc_result(Calc *me, QEvent const *e); QSTATE Calc_begin(Calc *me, QEvent const *e); QSTATE Calc_negated1(Calc *me, QEvent const *e); QSTATE Calc_operand1(Calc *me, QEvent const *e); QSTATE Calc_zero1(Calc *me, QEvent const *e); QSTATE Calc_int1(Calc *me, QEvent const *e); QSTATE Calc_frac1(Calc *me, QEvent const *e); QSTATE Calc_opEntered(Calc *me, QEvent const *e); QSTATE Calc_negated2(Calc *me, QEvent const *e); QSTATE Calc_operand2(Calc *me, QEvent const *e); QSTATE Calc_zero2(Calc *me, QEvent const *e); QSTATE Calc_int2(Calc *me, QEvent const *e); QSTATE Calc_frac2(Calc *me, QEvent const *e); 8-1

42 void CalcClear_(Calc *me); void CalcInsert_(Calc *me, int keyid); void CalcNegate_(Calc *me); void CalcEval_(Calc *me); void CalcDispState(Calc *me, char const *s); END_CLASS calc.c QFSMstate QSTATE Calc_ready(Calc *me, QEvent const *e) { BOOLEAN is_handled = TRUE; switch (e->sig) { case Q_ENTRY_SIG: CalcDispState(me, "ready"); case Q_INIT_SIG: Q_INIT(Calc_begin); case IDC_0: CalcClear_(me); Q_TRAN_DYN(Calc_zero1); case IDC_1_9: CalcClear_(me); CalcInsert_(me, ((CalcEvt *)e)->keyid); Q_TRAN_DYN(Calc_int1); case IDC_POINT: CalcClear_(me); CalcInsert_(me, IDC_0); CalcInsert_(me, ((CalcEvt *)e)->keyid); Q_TRAN_DYN(Calc_frac1); case IDC_OPER: sscanf(me->display_, "%lf", &me->operand1_); me->operator_ = ((CalcEvt *)e)->keyid; Q_TRAN_DYN(Calc_opEntered); default: is_handled = FALSE; if (is_handled) { return 0; else { return (QSTATE)Calc_calc; QHSM HSM qhsm.h qhsm.c QFSM frame 8-2

43 8 HSM HSM FSM ready Calc_ready QHSM HSM 2) SUPERCLASS QHsm Calc HSM instance QF 3) 0 ready event IDC_0 0 event Calc_calc Calc QF QTop() 4) QF Q_EMPTY_SIG = 0, // Q_INIT_SIG = 1,//initial transition readybeginstate transitionready begin Q_ENTRY_SIG = 2, //Entry Q_EXIT_SIG = 3 //Exit 5) Transition Q_TRAN_DYN QF Q_EXIT_SIG Q_ENTRY_SIG UML QHSM QHSM 8-3

45 9 CParser Calc SampleCode.rar 1

CC213

CC213 : (Ken-Yi Lee), E-mail: feis.tw@gmail.com 49 [P.51] C/C++ [P.52] [P.53] [P.55] (int) [P.57] (float/double) [P.58] printf scanf [P.59] [P.61] ( / ) [P.62] (char) [P.65] : +-*/% [P.67] : = [P.68] : ,