Jump to content
43oh

Recommended Posts

Hi all,

 

Just put together a basic state machine tutorial with portable C programming code, I have also made a small 4 state project with a basic user interface (LCD and 4 buttons), all based on a MSP430G2234.

 

Would be interested in anyone's views on it's readability and maybe even improvements?

 

State machine tutorial and C programming code:

 

http://coder-tronics.com/state-machine-tutorial-pt1/

http://coder-tronics.com/state-machine-tutorial-pt2/

 

Youtube video with MSP430 state machine (tutorial and all code to follow) :

 

https://www.youtube.com/watch?v=JzDn6SKjBxE

 

Cheers,

 

Ant

Link to post
Share on other sites

Looking nice. I do have some suggestions for enhancement.

 

First, I try to adhere to the dependency injection / global is evil mantra. This means I try to avoid any kind of global state (if it is at all reasonable).

As a concept, the Next_State should be a return value from the state machine logic; the loop where it is called can be viewed as the synchronous state machine tick and thus the maintainer thereof.

/*****
* Main function starts here
*****/
int main()
{
    enum states Current_State = S_OFF;

    while ( Current_State != S_MAX )
    {
        // Function call for the state machine, which then calls the read keys function and waits for the value returned
        Current_State = StateMachine( ReadKeyInput(), Current_State );
    }
 
    return 0;
}

As a result hereof, the Next_State must be returned:

enum states StateMachine(enum events event, enum states Current_State)
{
    int Next_State = Current_State;
 
    switch ( Current_State )
    {
        // all the state transition stuff
    }
 
    if (Next_State != Current_State)
    {
        // Function call for Upon Exit function, it can be omitted but allows extra functionality
        UponExit(Current_State);
        // Function call for Upon Enter function, it can be omitted but allows extra functionality
        UponEnter(Next_State);
    }
    else // I think ActionWhileInState should only be called when NOT doing a transition!
     {
        if ( event != E_MAX) ActionWhileInState( Current_State );
    }
    return Next_State;
}

Second: you have an UponEnter, ActionWhileInState and UponExit which all take the current state. In the case of C++ one would make a class hereof, in C, this is best done using a prefix or postix, combined with a lookup table.

typedef void (* const voidFunc)(void);
void hEnter_OFF(void);   void hEnter_ON(void);   void hEnter_PROCESS(void);
void hInState_OFF(void); void hInState_ON(void); void hInState_PROCESS(void);
void hExit_OFF(void);    void hExit_ON(void);    void hExit_PROCESS(void);

voidFunc UponEnter[S_MAX] =          {hEnter_OFF,   hEnter_ON,   hEnter_PROCESS};
voidFunc ActionWhileInState[S_MAX] = {hInState_OFF, hInState_ON, hInState_PROCESS};
voidFunc UponExit[S_MAX] =           {hExit_OFF,    hExit_ON,    hExit_PROCESS};

enum states StateMachine(enum events event, enum states Current_State)
{
    int Next_State = Current_State;
 
    switch ( Current_State )
    {
        // all the state transition stuff
    }
 
    if (Next_State != Current_State)
    {
        // Function call for Upon Exit function, it can be omitted but allows extra functionality
        UponExit[Current_State]();
        // Function call for Upon Enter function, it can be omitted but allows extra functionality
        if (Next_State != S_MAX) UponEnter[Next_State]();
    }
    else // I think ActionWhileInState should only be called when NOT doing a transition!
     {
        if ( event != E_MAX) ActionWhileInState[Current_State]();
    }
    return Next_State;
}

Now, while this may seem to only clutter things, it will save you the excessive switch statements to split the states again each time:

void hEnter_OFF(void)
{
  // Code to execute when entering the OFF state
}

You will get a load of functions, but each function will only handle a single task, making each function itself more readable.

For convenience, you may want to make a single placeholder handler as well

void hEmpty(void)
{
  // This function is empty and will be called for each event that I don't want to write a handler for.
}
Link to post
Share on other sites

Thanks for sharing.

 

I'm using FSM for my robotics models. Parallel processes managed by the same MCU are coordinated with FSM. The same approach was later extended to different MCUs through a Bluetooth LAN.

 

post-12238-0-80835100-1375207579_thumb.jpg

 

I read the training Electrical Engineering and Computer Science from the 1756491_orig.gif

 

I describe the whole approach in Dealing with Very Large Models.

Link to post
Share on other sites

@Roadrunner thanks for the tips and quite agree globals are best avoided if possible, I will implement the first step you suggested into the tutorial.  Regarding your second suggestion is this purely for C++ ?  

As I am just getting to grips with C at the moment and would sooner stick purely to C as not grasped some of the more in-depth concepts like pointers fully.

 

@@Rei Vilo no worries and thanks for the link to your tutorial will have a read of that, as looking to build milling machine for PCB's based on http://www.linuxcnc.org/ at somepoint, and sure it will aid me.

 

I need to look back at my MSP430 model of this now as have a few global variables acting as flags for functions, may post as is and then can get feedback on how to improve.

 

Cheers,

 

Ant

Link to post
Share on other sites

I found the following implementation structure to map nicely to UML state diagrams with entry, exit, and do behaviors.  Essentially it's a switch statement within a loop; on entry flags are set to execute the current state, and if that state has a transition enabled the flags will be updated to take it and execute the relevant behaviors.

Below is an excerpt of the technique.  It's fairly verbose and has a lot of apparent redundancy (entry/do/exit blocks present even if no behavior is required; setting flags only to have them cleared immediately; etc).  I prefer clarity to presuming that the compiler can't do its job and optimize out the irrelevant changes.  This code supports a "simulation" mode which simply runs through all the states to reach a target without actually executing any behaviors.  The feature was used by code I removed that aggregated per-stage timing estimates.

Unfortunately the complete code is very large, and the system for which it was developed didn't meet its requirements for reasons unrelated to the state machine implementation, so I'm not planning to release it.  Hopefully this is enough to get the general idea of the technique, though.

/** Bit set in state machine flags when entry behavior should be
 * executed. */
#define ST_ENTRY 0x0001
/** Bit set in state machine flags when state should execute its do
 * behaviors and take any enabled transitions. */
#define ST_EXECUTE 0x0002
/** Bit set in state machine flags when state should execute its exit
 * behavior and transition. */
#define ST_EXIT 0x0004
/** Bit set in state machine flags when transitions are being
 * simulated for the purpose of estimating time requirements; no side
 * effects should occur. */
#define ST_SIMULATE 0x0008

static int
stateMachine_rh (int target_state,
                 unsigned int st_flags)
{
  /* ... */
  this_state = hal.cc2520_state;
  while ((ST_EXECUTE & st_flags)
         || ((ST_SIMULATE & st_flags) && (target_state != this_state))) {
    ++nsteps;
    switch (this_state) {
      /* ... */
      case PSML_CC2520_STATE_WAIT_VREG:
        if (ST_ENTRY & st_flags) {
          st_flags &= ~ST_ENTRY;
        }
        if (ST_EXECUTE & st_flags) {
          /* Retain transition, not a target state */
          st_flags |= ST_EXIT;
        }
        if ((ST_SIMULATE | ST_EXIT) & st_flags) {
          this_state =  PSML_CC2520_STATE_WAIT_XOSC;
        }
        if (ST_EXIT & st_flags) {
          BSP430_CORE_DISABLE_INTERRUPT();
          TIME_STAGE_START();
          do {
            /* Take chip out of reset and wait for the crystal oscillator to
             * stabilize. */
            CC2520_DEASSERT_RESET_NI(&hal);
            reconfigureSPIforXOSC_ni();
            CC2520_ASSERT_CS_NI(&hal);
          } while (0);
          BSP430_CORE_RESTORE_INTERRUPT_STATE(istate);
          st_flags &= ~ST_EXIT;
          st_flags |= ST_ENTRY;
        }
        break;
      case PSML_CC2520_STATE_WAIT_XOSC:
        if (ST_ENTRY & st_flags) {
          st_flags &= ~ST_ENTRY;
        }
        if (ST_EXECUTE & st_flags) {
          st_flags &= ~ST_EXECUTE;
          BSP430_CORE_DISABLE_INTERRUPT();
          do {
            while (! (hal.flags_ni & CC2520_HAL_FLAG_SPI_XOSC)) {
              ; /* State invariant broken */
            }
            if (XOSC_IS_STABLE_NI(&hal)) {
              /* Condition met, enable transition and exit */
              st_flags |= ST_EXECUTE | ST_EXIT;
              }
          } while (0);
          BSP430_CORE_RESTORE_INTERRUPT_STATE(istate);
        }
        if ((ST_SIMULATE | ST_EXIT) & st_flags) {
          this_state = PSML_CC2520_STATE_CONFIGURE;
        }
        if (ST_EXIT & st_flags) {
          BSP430_CORE_DISABLE_INTERRUPT();
          do {
            /* CS deassert paired with CS assert in exit behavior of
             * whatever state led here: WAIT_VREG or LPM1. */
            CC2520_DEASSERT_CS_NI(&hal);
          } while (0);
          BSP430_CORE_RESTORE_INTERRUPT_STATE(istate);
          st_flags &= ~ST_EXIT;
          st_flags |= ST_ENTRY;
        }
        break;
      case PSML_CC2520_STATE_CONFIGURE:
        if (ST_ENTRY & st_flags) {
          st_flags &= ~ST_ENTRY;
        }
        if (ST_EXECUTE & st_flags) {
          /* Nonblocking, not target, retain and execute transition */
          st_flags |= ST_EXIT;
          restoreConfiguration_rh();
        }
        if ((ST_SIMULATE | ST_EXIT) & st_flags) {
          this_state =  PSML_CC2520_STATE_ACTIVE_IDLE;
        }
        if (ST_EXIT & st_flags) {
          st_flags &= ~ST_EXIT;
          st_flags |= ST_ENTRY;
        }
        break;
       /* ... */
     }
     /* ... */
  }
  rv = (target_state == this_state) ? 0 : nsteps;
  if (! (ST_SIMULATE & st_flags)) {
    hal.cc2520_state = this_state;
  }
  return rv;
}
Link to post
Share on other sites
As I am just getting to grips with C at the moment and would sooner stick purely to C as not grasped some of the more in-depth concepts like pointers fully.

No, the code I wrote is pure C and is indeed heavily depending on pointers. In C++ these concepts would be much simpler (contrary to the actual code...), as you wouldn't need to do as much pointer magic; C++ hides a lot of pointer handling behind the class and object models.

 

In C++, a state machine would look more like this:

class State
{
  public:
    virtual void UponEnter();
    virtual void UponExit();
    virtual State& WhileInState(int inputs);
};

class _stateOFF: public State
{
  public:
    void UponEnter(){
      // code goes here
    }
    void UponExit(){
      // code goes here
    }
    State& WhileInState(int inputs);
} StateOFF;

class _stateON: public State
{
  public:
    void UponEnter(){
      // code goes here
    }
    void UponExit(){
      // code goes here
    }
    State& WhileInState(int inputs);
} StateON;

class _stateProcess: public State
{
  public:
    void UponEnter(){
      // code goes here
    }
    void UponExit(){
      // code goes here
    }
    State& WhileInState(int inputs);
} StatePROCESS;

State& _stateOFF::WhileInState(int inputs)
{
  // Code goes here
  return StateON;
}

State& _stateON::WhileInState(int inputs)
{
  // Code goes here
  return StatePROCESS;
}

State& _statePROCESS::WhileInState(int inputs)
{
  // Code goes here
  return StateOFF;
}

int main()
{
  sState* CurrentState = StateOFF;
  do
  {
    sState& NextState = CurrentState->WhileInState(keyPresses());
    if (NextState != *CurrentState)
    {
      CurrentState->UponExit();
      CurrentState = &NextState;
      CurrentState->UponEnter();
    }
  } while(1);
}

You could even move the UponExit() code into the WhileInState() code, since you know whether you'll be changing to another state or not. Alternatively you can 'new' the current state and 'delete' a state on exit, but for embedded systems with no real memory management, you'd better not.

Link to post
Share on other sites

@Roadrunner thanks again for the input.  One quick question springs to mind, you mention "Second: you have an UponEnter, ActionWhileInState and UponExit which all take the current state."  however the UponEnter acts on the Next_State variable?

I intend to write a third part to this tutorial with the basic state machine based on your C code example, the original gives a good overview for a beginner like me.  Do you have a website or something I can add a link to, just to serve as credit for your help?

Link to post
Share on other sites

 

Looking nice. I do have some suggestions for enhancement.

 

First, I try to adhere to the dependency injection / global is evil mantra. This means I try to avoid any kind of global state (if it is at all reasonable).

As a concept, the Next_State should be a return value from the state machine logic; the loop where it is called can be viewed as the synchronous state machine tick and thus the maintainer thereof.

/*****
* Main function starts here
*****/
int main()
{
    enum states Current_State = S_OFF;

    while ( Current_State != S_MAX )
    {
        // Function call for the state machine, which then calls the read keys function and waits for the value returned
        Current_State = StateMachine( ReadKeyInput() );
    }
 
    return 0;
}

As a result hereof, the Next_State must be returned:

enum states StateMachine(enum events event, enum states Current_State)
{
    int Next_State = Current_State;
 
    switch ( Current_State )
    {
        // all the state transition stuff
    }
 
    if (Next_State != Current_State)
    {
        // Function call for Upon Exit function, it can be omitted but allows extra functionality
        UponExit(Current_State);
        // Function call for Upon Enter function, it can be omitted but allows extra functionality
        UponEnter(Next_State);
    }
    else // I think ActionWhileInState should only be called when NOT doing a transition!
     {
        if ( event != E_MAX) ActionWhileInState( Current_State );
    }
    return Next_State;
}

 

Just trying to implement the first fix to remove the global variable, I have the code as you wrote, but getting an error with the 

Current_State = StateMachine( ReadKeyInput() );    *The compiler is saying too few arguments.  I suspect this is to do with my forward function prototypes and also enum setup as I believe they need to be as follows:

 

enum states { S_OFF, S_ON, S_PROCESS, S_MAX, Current_State };

enum events { E_OFF, E_ON, E_START, E_MAX, event };

 

void StateMachine(enum events event, enum states Current_State);

Link to post
Share on other sites

Sorry, my bad. As you can see in the statemachine function declaration, it expects both the input events and the current state, so you should call it like this:

Current_State = StateMachine( ReadKeyInput(), Current_State);

 

The enums shouldn't be changed.

By the way, whenever you're using enums to enumerate something, also use them as type for the parameters to expect. I know C accepts an int to be passed an enum, but you shouldn't treat enums as ints ever.

Link to post
Share on other sites

A little on pointers, just for the fun of it.

 

Pointer may seem complex and intimidating at first, but if you keep a little track of the type of something, it's quite understandable.

 

C knows basically only one type: a scalar. This means that anything can be represented as a number. A string is a series of numbers representing letters, a boolean is a number (0 or 1), an integer is a number, a loating point is a set of numbers representing a fractional value and a pointer is a number of the address of something else in memory.

These numbers are very powerful and very versatile, this is why you need to take care that you know what a certain number means.

int x = 0; // x is an alias to a number; the number 0
int* p = 0; // p is a pointer to a number; the memory address 0
char s[] = "0"; // s is a pointer to a series of characters; the first character is the digit 0
char s2[] = "\0"; // s2 is a pointer to a series of characters; the first character is the NUL character

There are two special symbols associated with the use of pointers, the * (asterisk) and the & (ampersand). The confusing thing is that their meaning differs in the context.

int x;
int* p = &x; // int* is the type of p, this is "pointer to integer"

*p = 5; // *p means "use the value that p is pointing to". Since p is pointing to an integer, x in this case, x will become 5
p = 5; // WRONG: set p to point to memory address 5
p = &x; // &x means "use the address of x"; p will become the address of x; p points to x

int a[4]; // a is an array, this is equal to "a points to the start of a consecutive series of 4 unnamed integers"
p = a; // since both p is a pointer to int and a is a pointer to int, we can let p become a or "let the pointer p become the same address as the pointer a"
int b[4]; // b is also a pointer to a series of 4 integers
b = a; // WRONG: both b and a are pointers, so C won't complain, but you just lost a pointer to the series of 4 integers that b used to point to; this is called memory leak

int d[8];
p = a;
a = d;
d = p;
// since we used p as a temporary for a, we can use this to exchange the pointer values of a and d.
// note that since a pointed to a series of 4 and d pointed to a series of 8, that now the opposite is the case, I'm not sure how your compiler will behave:

int e[2];
void foo(void)
{
  int b[4];
  int* p;
  p = e;
  e = b;
  b = p;
  // normally the array b will be disposed of at function end, but will the compiler drop 4 integers or 2 integers?
  // best practice is to never assign to the array, but only to pointers
}

void bar(void)
{
  int b[4];
  int* p;
  int* q;
  p = e;
  q = b;
  // now use p and q where you wanted to use b and e.
}

As you can see, an array is secretly a pointer to a series of values, this means that we can use array indexing and * (pointer dereferencing) in mixed order:

int a[4];
int* p = a;
p[2] = 5; // a[2] will become 5
*a + 3 = 2; // a[3] will become 2

Things become really interesting when using arrays of pointers

int a=1;
int b=2;
int c=3;
int* q = &c; // q points to the address of c
int* p[3] = {&a, &b, q};
// p is an array of pointers to integers, so p points to a series of pointers to integers
int** r = p; // r is a pointer to a pointer to integers, so *r is a series of pointers to integers
*(*p + 1) = 5; // equal to *(p[1]) or even equal to p[1][0], all which are equal to b, since p[1] is a pointer to b
q = &a; // this only affects q, since p copied the address held by q, so p[2] still is equal to c
p[2]=4; // c becomes 4
*q = 0; // a becomes 0
q[0] = 3; // a becomes 3

Things get a little confusing when we're talking about pointers to functions, this is because pointer dereference and address referencing is optional for functions.

void foo(void)
{
  // do something
}

foo(); // the compiler will save the current instruction pointer and load the address of foo in the instruction pointer
// then when foo is done, it will load the saved instruction pointer back to the instruction pointer, so execution continues just after the call to foo

void (* bar)(void); // this is a variable called bar, it is a pointer to a function that looks like void name(void)
bar = &foo; // bar is now pointing to the function foo
bar = foo; // C accepts omitting the & when talking function pointers, try to avoid this form if you're new to pointers
(*bar)(); // do a call to the function that bar points to; call foo
bar(); // C accepts omitting the * when talking function pointers, here again. So this also calls foo
bar = foo(); // WRONG: try to assign the return value of foo (void) to bar

typedef int number; // this is a type definition; the type number is now equal to the type int
typedef void(*voidfunc)(void); // this is a type definition; voidfunc is now equal to void(*name)(void)
voidfunc baz; // baz is a variable, it is a pointer to a function that looks like void name(void)

constant pointers and pointers to constants

Take notice that pointers don't need to point to the same value throughout the program, unlike variables (and just like variable values).

C has the keyword const to denote that a value may never change. In the case of the MSP430 this is also used to place a value in flash instead of ram (since you promised not to change it anyway, in AVR you must use the PROGMEM attribute to force a value to flash).

int x; // x holds a variable value;
const int y=5; // y hold a constant value 5, so y will never ever change
const int z; // WRONG: since z will never change, you must assign it a value at declaration

const int* p = &y; // p points to the constant integer y
int const* q = &y; // q points to the constant integer y
int * const r = &x; // r is a constant pointer to the integer x, so r will never change, but it's dereferenced value (the value of *r or x) may change
int * const s = &y; // WRONG: since y is a const int, s must be a pointer to constant integer, but it is a constant pointer to integer
const int * const t = &y; // t is a constant pointer to a constant integer; neither t nor *t (y) may change value

As you can see, the const keyword may come before or after the type int. But when placing the const keyword after the * it is a property of the pointer, not a property of the type int.

 

buffer overflow

Whenever you're working with arrays and/or pointers, take much care to not cross the boundaries of the actually allocated memory

int a[4]; // a is 4 integers long: a[0], a[1], a[2] and a[3].
int* p = a; // p points to a[0]
p[1] = 5; // p[1] is a[1] and becomes 5
p[4] = 4; // WRONG: p[4] is a[4] which is the memory location after a[3], but we've never allocated this memory. You might be overwriting something else!

void fillbuffer(int* buffer, int length, int value) // fill a buffer named buffer of length length with value value
{
  for(int iter = 0; iter <= length; iter++) // WRONG: iter should be less, not less or equal to length
  {
    *buffer = value; // write value to the element buffer is pointing to
    buffer++; // increment the address in buffer by 1 element
  }
}

const int len = 5;
int b[len]; // b is now 5 integers large
p =b;  // p now points to b[0]
fillbuffer(p, len, 0); // write the value 0 to all elements of p
//WARNING: are you sure that your function is doing what it should do?

void fillbuffer2(int* buffer, int max_elem, int value) // fill a buffer named buffer of length max_elem - 1 with value value
{
  for(int iter = 0; iter <= max_elem; iter++) // WARNING: will the user pass the right value to max_elem?
  {
    *buffer = value; // write value to the element buffer is pointing to
    buffer++; // increment the address in buffer by 1 element
  }
}

const int len2 = 5;
int b2[len2]; // b2 is now 5 integers large
p2 =b2;  // p2 now points to b[0]
fillbuffer2(p2, len2 - 1, 0); // write the value 0 to all elements of p2
//WARNING: these "off by 1" situations happen a lot! always be sure you're doing it right

I hope this sheds some light on the behaviour of pointers. It is a lot, and you need to be really sure to always use the right symbol at the right time. This is what makes C an unsafe language and what causes 90% of all security leaks in software. Languages like C# and Java try to fix this by monitoring memory overflows or restrict pointery stuff, in which they succeed for less than 100%. Javascript et al. do not support fixed-length arrays or pointers, which causes the language itself to be safe, but not all implementations are.

Link to post
Share on other sites
  • 2 weeks later...

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...