Design State Machine Engine for embedded system development

• Download install pack - 1.15 Mb

Introduction

Embedded systems are some special purpose computers that are used inside of devices. Embedded systems generally use micro controllers that contain many functions of a computer on a single device. Embedded systems have to tightly work together with special hardware. They have to respond to external interactions in a predetermined amount of time. Usually embedded systems are real time. Many embedded system applications are natural candidates for being organized as a state machine. A program that must sequence a series of actions, or handle inputs differently depending on what state it's in, is often best implemented as a state machine.

In general, a state machine is any device that stores the status of something at a given time and can operate on input to change the status and/or cause an action or output to take place for any given change. In practice, however, state machines are used to develop and describe specific device or program interactions.

Hierarchical state machine

In general, a state machine is any device that stores the status of something at a given time and can operate on input to change the status and/or cause an action or output to take place for any given change.

To summarize it, a state machine can be described as:

• A set of states.
• An initial state or record of something stored somewhere.
• A set of input events.
• A set of output events.
• A set of actions or output events that maps the states and input to output (which is called a state event handler).
• A set of actions or output events that maps the states and inputs to states (which is called a state transition).

Usually, state machines allow users to model complex behavior via composite state with more than one hierarchy level. The state machine state hierarchy is based on a parent-child relationship:

• Similar sub-states are grouped into a composite state (nesting hierarchy is a tree);
• Composite states can have transitions, entry/exit actions, ...(transitions can connect states from different nesting levels);
• Sub-states "inherit" from the composite state;
• The active state denotes a path from a top-level state to a leaf node in the state hierarchy;
• There must be an initial sub-state in every composite state. On entering a compose state or sub-state, both of them are activated. The order of entry functions is from top to bottom.
• On exiting a composite state, exit the active sub-state as well. The order of exit functions is from bottom to top.

Type definitions

//// State Definition
typedef short SME_STATE_T; 
#define SME_APP_STATE 0
#define SME_INVALID_STATE -1 
//// Event Definition
// Positive 32-bit integer values are user-defined 
// event identifiers.
// Negative 32-bit integer values are state machine 
// engine defined event identifiers.
typedef long SME_EVENT_ID_T;
#define SME_INVALID_EVENT_ID -1
#define SME_EVENT_KILL_FOCUS -2
#define SME_EVENT_SET_FOCUS -3 
typedef enum
{
    SME_EVENT_CAT_UI=0,
    SME_EVENT_CAT_OTHER,
};
typedef unsigned char SME_EVENT_CAT_T; 
typedef enum
{
    SME_EVENT_ORIGIN_INTERNAL=0,
    SME_EVENT_ORIGIN_EXTERNAL,
};
typedef unsigned char SME_EVENT_ORIGIN_T; 
typedef enum
{
    SME_EVENT_DATA_FORMAT_INT=0,
    SME_EVENT_DATA_FORMAT_PTR,
};
typedef unsigned char SME_EVENT_DATA_FORMAT_T; 
typedef struct SME_INT_DATA_T
{
    unsigned long nParam1;
    unsigned long nParam2;
} SME_INT_DATA_T; 
typedef struct SME_PTR_DATA_T
{
    void* pData;
    unsigned long nSize;
} SME_PTR_DATA_T; 
union SME_EVENT_DATA_T
{
    SME_INT_DATA_T Int;
    SME_PTR_DATA_T Ptr;
}; 
typedef struct SME_EVENT_T
{
    SME_EVENT_ID_T nEventID;
    unsigned long nSequenceNum;
    struct SME_EVENT_T *pNext;
    /* Provide 2 data formats: integer or pointer */
    union SME_EVENT_DATA_T Data;
    struct SME_APP_T *pDestApp; /* The destination application.*/
    unsigned long nOrigin :8; /* */
    unsigned long nCategory :8; /* Category of this event. */
    unsigned long nDataFormat :8; /* Flag for this event. */
    unsigned long bIsConsumed :8; /* Is comsumed. */
}SME_EVENT_T; 
typedef struct SME_APP_T
{
    const char * sAppName;
    struct SME_APP_T *pParent; /* Who starts me */
    struct SME_APP_T *pNext; /* Applications are linked together.*/
    unsigned long nPortId;
    void * pPortHandle;
    void * pData;
    const struct SME_STATE_TREE_TABLE_T *pStateTree;
    SME_STATE_T nAppState;
}SME_APP_T; 
#define SME_APP_DATA(app) (app.pData)
#define SME_IS_ACTIVATED(app) (app->nAppState != SME_INVALID_STATE) 
typedef int (* SME_EVENT_HANDLER_T)(SME_APP_T *, SME_EVENT_T *); 
#define SME_INTERNAL_TRAN SME_INVALID_STATE 
typedef struct SME_EVENT_TABLE_T {
    SME_EVENT_ID_T nEventID;
    SME_EVENT_HANDLER_T pHandler;
    SME_STATE_T nNewState;
}SME_EVENT_TABLE_T; 
typedef struct SME_STATE_TREE_TABLE_T{
    SME_EVENT_TABLE_T *pEventTable;
    SME_STATE_T nState;
    SME_STATE_T nParentState;
    SME_STATE_T nDefSubState;
}SME_STATE_TREE_TABLE_T;

State machine data construction

We could define a set of specific macros as state machine mapping data. These macros map to state enumerations, event handler function declarations, event handler table for a state, state tree definition and application variable definition.

1. State enumeration

   #define SME_BEGIN_STATE_DECLARE(_app) \
   enum _app##_state_enum_t \
   {
       #define SME_STATE_DECLARE(_state) _state, 
       #define SME_MAX_STATE(_app) _app##_max_state 
       #define SME_END_STATE_DECLARE };

2. State event handler table definition

   #define SME_ENTRY_FUNC_IDX 0
   #define SME_EXIT_FUNC_IDX 1
   #define SME_EVENT_HANDLER_FUNC_IDX 2 
   #define SME_BEGIN_STATE_DEF(_app,_state) \
   static const SME_EVENT_TABLE_T _app##_state##_event_hdl_tbl[] \
       ={ 
           #define SME_STATE_ENTRY_FUNC( _EntryFunc) \
           { SME_INVALID_EVENT_ID, _EntryFunc, 0},
           #define SME_STATE_EXIT_FUNC( _ExitFunc) \
           { SME_INVALID_EVENT_ID, _ExitFunc, 0}, 
           #define SME_ON_EVENT(_EventID, _Handler, _NewState) \
           { _EventID, _Handler, _NewState}, 
           #define SME_END_STATE_DEF 
           { SME_INVALID_EVENT_ID, 0, SME_INVALID_STATE}
       };

3. State tree definition

   #define SME_BEGIN_STATE_TREE_DEF(_app) \
   extern const SME_STATE_TREE_TABLE_T _app##_state_tree[] = \
   { 
       #define SME_STATE(_app,_state,_state_parent,_def_substate) \
       {(SME_EVENT_TABLE_T *)_app##_state##_event_hdl_tbl, 
                              _state,_state_parent,_def_substate}, 
       #define SME_END_STATE_TREE_DEF 
   };

4. Application definition

   #define SME_APPLICATION_DEF(_app,_app_name) \
   struct SME_APP_T _app##App = { \
       _app_name, NULL, NULL, 0, NULL, NULL, _app##_state_tree, 
       SME_INVALID_STATE};
   
   /* Get application variable name. */
   #define SME_GET_APP_VAR(_app) _app##App 
   /* Declare application variable that has external linkage. */
   #define SME_DEC_EXT_APP_VAR(_app) extern SME_APP_T _app##App;

Event dispatch

/*********************************************************************
* DESCRIPTION: Dispatch the incoming event to an 
* application if it is specified, otherwise
* dispatch to all active applications untile it is consumed. 
* INPUT: 
* 1) pEvent: Incoming event 
* 2) pApp: The destination application that event will be dispatched.
* OUTPUT: None.
* NOTE: 
* 1) Call exit functions in old state 
* 2) Call event handler functions 
* 3) Call entry functions in new state 
* 4) Transit from one state region to another state region. All states 
* exit functions that jump out the old region will be called. And all 
* states exit functions that jump in the new region will be called.
* 5) Although there is a property pEvent->pDestApp in SME_EVENT_T, this 
* function will ignore this one, because if pEvent->pDestApp is NULL, 
* this event have to dispatch to all active applications.
**************************************************************************/
BOOL SmeDispatchEvent(struct SME_EVENT_T *pEvent, struct SME_APP_T *pApp)
{
    SME_STATE_T nOldState; /* Old state should be a leaf.*/
    SME_STATE_T nState;
    SME_STATE_T nNewState;
    int i;
    BOOL bFoundHandler=FALSE;
    SME_EVENT_HANDLER_T pHandler = NULL;
    SME_STATE_T OldStateStack[SME_MAX_STATE_TREE_DEPTH];
    SME_STATE_T NewStateStack[SME_MAX_STATE_TREE_DEPTH];
    SME_STATE_T nOldStateStackTop =0;
    SME_STATE_T nNewStateStackTop =0;
    /* Trace back from leaf to root, so as to retrieve 
    all event handler tables. Find what nNewState is */
    struct SME_EVENT_TABLE_T *pStateEventTable;
    if (pEvent==NULL || pApp==NULL) return FALSE;
    nOldState = pApp->nAppState; /* Old state should be a leaf.*/
    nState = nOldState;
    pStateEventTable = pApp->pStateTree[nOldState].pEventTable;
    /************************************************************
    Check the state's event handler table from leaf to root.
    If find it, stop searching, no matter there is another 
    handler in parent sate's event table.
    */
    while (TRUE)
    {
        /* Check the current state's event handler table.*/
        i=SME_EVENT_HANDLER_FUNC_IDX;
        while (pStateEventTable[i].nEventID != SME_INVALID_EVENT_ID)
        {
            if (pStateEventTable[i].nEventID == pEvent->nEventID)
            {
                nNewState=pStateEventTable[i].nNewState;
                bFoundHandler = TRUE;
                pHandler = pStateEventTable[i].pHandler;
                break;
            } else
            i++;
        }
        
        if (bFoundHandler || (nState == SME_APP_STATE)) break;
        /* Get the parent state's event handler table. */
        nState = pApp->pStateTree[nState].nParentState; 
        pStateEventTable = pApp->pStateTree[nState].pEventTable;
    }
    
    if (!bFoundHandler) return FALSE;
    /****************************************************************/
    if (nNewState != SME_INTERNAL_TRAN)
    {
        /* It is a state transition.
        Push all old state's ancestors.
        */
        nState = nOldState;
        while (nState!=SME_APP_STATE)
        {
            OldStateStack[nOldStateStackTop++] = nState;
            nState=pApp->pStateTree[nState].nParentState;
            if (nOldStateStackTop >= SME_MAX_STATE_TREE_DEPTH)
                return FALSE;
        }
        /* Push all new state's ancestors. */
        nState = nNewState;
        while (nState!=SME_APP_STATE)
        {
            NewStateStack[nNewStateStackTop++] = nState;
            nState=pApp->pStateTree[nState].nParentState;
            if (nNewStateStackTop >= SME_MAX_STATE_TREE_DEPTH)
                return FALSE;
        }
        /* Pop all equal states except the last one.
        Special case 1: self transition state1->state1, 
                        leave one item in each stack.
        Special case 2: parent state transits to child state, 
                        leave one item in parent state stack.
        */
        while ((nOldStateStackTop>1) && (nNewStateStackTop>1)
             && (OldStateStack[nOldStateStackTop-1] == 
                         NewStateStack[nNewStateStackTop-1]))
        {
            nOldStateStackTop--;
            nNewStateStackTop--;
        }
        /* Get the leaf of the old state.
        Note: Old state should be a leaf state.
        Call exit functions from leaf nState to old state stacks top.
        */
        for (i=0; i<nOldStateStackTop; i++)
        {
          nState = OldStateStack[i];
          if(pApp->pStateTree[nState].pEventTable[SME_EXIT_FUNC_IDX].pHandler)
            pApp->pStateTree[nState].pEventTable[SME_EXIT_FUNC_IDX].pHandler(
                                                                  pApp,pEvent);
        };
    }; /* end of not internal transition.*/
    /**************************************************************************
    Call event handler function if given enent 
    handler is available and handler is not empty.
    Maybe their is a transition, however handler is empty.
    */
    if (bFoundHandler && pHandler)
    {
        (*pHandler)(pApp,pEvent);
    };
    /**************************************************************************
    Call entry functions from new state stack's top to leaf state. */
    if (nNewState != SME_INTERNAL_TRAN)
    {
        /* It is a state transition.
        Call entry functions from ancestor to new state.
        */
        for (i=nNewStateStackTop-1; i>=0; i--)
        {
          nState = NewStateStack[i];
          if(pApp->pStateTree[nState].pEventTable[SME_ENTRY_FUNC_IDX].pHandler)
            pApp->pStateTree[nState].pEventTable[SME_ENTRY_FUNC_IDX].pHandler(
                                                                   pApp,pEvent);
        };
        /* Call entry functions from new state's child to leaf. */
        nState=nNewState;
        /* It is not a leaf. */
        while (pApp->pStateTree[nState].nDefSubState != SME_INVALID_STATE) 
        {
           nState=pApp->pStateTree[nState].nDefSubState;
           /* Call default sub-state's entry function.*/
           if(pApp->pStateTree[nState].pEventTable[SME_ENTRY_FUNC_IDX].pHandler)
             pApp->pStateTree[nState].pEventTable[SME_ENTRY_FUNC_IDX].pHandler(
                                                                    pApp,pEvent);
        }
        pApp->nAppState = nState; /* New application state is the 
                                     destination state's leaf. */
    };
    /***************************************************************************
    Call event handle hook function if given enent handler is available 
    and no matter whether handler is empty or not.
    */
    if (bFoundHandler && g_fnOnEventHandleHook)
          (*g_fnOnEventHandleHook)((SME_EVENT_ORIGIN_T)(pEvent->nOrigin), 
          pEvent, pApp, pApp->nAppState);
        return TRUE;
}

Application manager

Programs on embedded system usually can be divided into a few applications. There are two kinds of mode for these applications: active or inactive. Active applications are exactly running on the state machine whereas inactive applications are not. In other words, only active applications can handle events. State machine engine is responsible for managing these applications and dispatching events to specific applications.

Embedded system program has to tightly co-work with the lower layer (other modules) or hardware, which are called service providers. A service is formally specified by a set of primitives (operations) available to the service users (applications). These primitives tell the service to perform some action or report on an action taken by a peer component/entity. The service primitives are classified to four categories: request, indication, response and confirm [Computer Networks, Andrew S.Tanenbaum]. The request and confirm primitives can be implemented in the form of service calls. The indication and response primitives can be implemented in the form of external event posting.

In a simulation environment, a developer can design a simulator using a Windows program as service providers. The interfaces of these simulators are identical to the interface of target service providers. In a target environment, a developer may take a little effort to integrate the state machine applications with these service providers to real environment. Active applications may make some service calls exported by the service providers, and meanwhile may receive some external events triggered by the service providers through the RTOS functions. There are many different RTOSs although they provide similar functions. RTOS virtual layer provides a set of platform independent functions so that it can be moved to other platforms without any change in the state machine application.

The communication between the applications and the service providers can be either in asynchronous mode or in synchronous mode. The applications run on application thread, at same time, the service providers run on service provider thread.

UML state machine wizard

When UML was first adopted, many embedded developers incorporated it through the static CASE technology to allow them to capture their systems and software architecture visually. One of the most popular CASE technologies with the early adoption of UML was the Rational Rose. However as the technology evolved, CASE tools like Rose could not provide the step up in development necessary to keep pace with the ongoing technology evolutions. The Mode-Driven Development (MDD) environments which provide clear model for code synchronization as well as automated base simulation and validation, has proved to be the key process enabler to keep the product development teams in step with the emerging technologies.

Visual C++ is a powerful software developing tool. However it aims at developing Windows-specific applications. UML State Machine Wizard acts as a Visual C++ add-in, which provides a UML (Unified Modeling Language) state machine programming mechanism in portable standard C for developing and simulating embedded systems in Visual C++ developer studio. After simulating and debugging, the developer can move the program to a destination working environment with little or no extra investment or effort.