Hello and welcome to the Modern Embedded Systems Programming course. My name is Miro Samek and in this fifth lesson on state machines, I'd like to show you the state machine implementation in C that I consider optimal according to the criteria that I'll enumerate. In the process, you will see how to build a reusable "event processor" to include this optimal state machine implementation strategy directly in the Micro-C-AO active object framework that you've been building in this segment of lessons. 

To allow you for a direct comparison with the other state machine implementations presented so far, today you will keep working with the same "TimeBomb" example you used before.

So, let's start with copying the previous lesson-38 directory and rename it to lesson-39. Get inside the new lesson-39 directory and double-clink on the project "lesson" to open it in the uVision IDE.


To remind you quickly what happened so far, in the previous couple of lessons you've learned a few state machine implementation strategies in C, such as the nested-switch statement and the state table technique.

All of them had drawbacks, but they also had some promising features. So, today you'll explore the ways to mix and match the nice properties while getting rid of the drawbacks.

But before all that, to arrive at an optimal solution, it often pays off to start with first imagining what that ideal should look like, and then to work *backwards* to the implementation in a programming language, like C in this case.

So, let's imagine that you are inventing a Domain Specific Language (DSL), not so much to implement state machines, but to *specify* them. Such a DSL will then be a textual representation of the state machine diagrams.

At this point, please don't even think of the C syntax. Let's just try to specify your TimeBomb state machine in the most clear and succinct way you can think of.

Well, in the state diagram, the most prominent elements you can see are states, so let's start with that...

The first state is wait4button, so here is the simplest possible way you can specify it as text.

This state has an entry action that you can specify as the word "Entry" followed by the actions, which you can simply copy over from the existing implementation in C.

The state has also also an exit action that you can specify in the similar way.

Finally, the state has a transition, triggered by the BUTTON_PRESSED event.

You can specify this by typing the name of the triggering event, followed by the actions in C. The state-table implementation explicitly assigned the state variable with the enumerated constant for that state. But this is neither the most concise nor it is consistent with your state names. So, let's specify the transition with the word "TRAN" followed by the target state name in parentheses, exactly as it is in your diagram.


Next is the blink state, which you specify the same way:

You just follow your simple patterns for specifying the entry action, exit action and the TIMEOUT transition to pause.



The pause state has only entry action and no exit.

But the TIMEOUT trigger leads to a choice point with guard conditions, which you can copy over from the previous C code:

Here, you only need to change the transition specifications.

The last state is boom, which has only an entry action, where it simulates an explosion.


So, this would be the specification of the TimeBomb state machine, except that you still need to add the top-most initial transition.

Here, you can reuse the generic state specification, because you can think of the initial transition as originating from the special "initial" pseudo-state – the black dot. This black-dot pseudostate has only one transition, which is not triggered by any event and which goes to state wait4button, in case of your TimeBomb state machine.

So, here it is: a Domain Specific Language – DSL for state machines that you've just invented. Such DSLs actually exist and most of them are similar to your invention.

For instance, there is special tool called the State Machine Compiler – SMC, which provides an "easy to understand language" for state machines. SMC then can translate that DSL into several programming languages, including C and C++.

So, for a direct comparison, here is the same TimeBomb state machine specified with the SMC DSL.

As you can see, the general structure is remarkably similar, with the states playing the central role and other internal elements like Entry/Exit actions, Transitions, and guards very similar to your DSL. The biggest differences are in the specification of actions, because SMC does not allow you to use C directly.

I will get back to the SMC example later in this lesson, because right now I have a bigger fish to fry. The idea is exactly NOT to use a special compiler, like SMC, but rather to add a minimal amount of syntax directly to your DSL to turn it into a legal C program. So let's see what you can do…


Well, the state specifications could be turned into C functions. This should make sense, because the main job of a state is to respond to events by executing action code, and executing code is exactly what function are for.

The syntax of your DSL is already pretty close to a C function. The missing piece in the signature is the list of parameters. But here, when you look at the actions, you can see that they need to access the "me" pointer and you also need the current event signal to determine what event you are getting. Therefore the state-handler functions need the same parameters as the action-handlers from the previous state-table implementation.

But now, the presence of the "me" pointer indicates that the state-handlers are not just any functions. Rather, they are *member* functions of the TimeBomb class, just like the action-handlers were before. The coding convention for member functions in C, which I introduced in the segment of lessons 29 through 32 about object-oriented programming, requires to add the class name prefix to all of the member functions. So, let's just do that.

Please note that you need to add the prefix also to the target states of transitions.

And finally, to finish off the signature, the word "State" now corresponds to the return value from the state-handler function. This could be the same status information used before for the action-handlers as to what happened inside the handler. So, let's rename Status to State, so that the specification for a state reads exactly as you originally designed. 

Alright, so now you need to adjust the syntax inside your states-handler functions. For this, you can reuse the design from the nested-switch statement technique you've learned back in lesson-36.

Specifically, each of your state-handler functions now corresponds to a case statement at the first level of the nested switch. 

The second level of the switch, based on the event-signal, corresponds then to the inside of each state. This inside structure is exactly what you need now, so you can just copy it over.

As far as the entry and exit actions are concerned, the nested-switch technique didn't support them. But they can be handled similarly as you already did in the state-table technique, by means of the special, reserved event signals: ENTRY_SIG and EXIT_SIG that are already defined in your Micro-C-AO header file.

Putting this all together, this is how the internal implementation of a state-handler function could look like:

But according to the signature, your state-handler function needs to return the status information. For example, after handling an Entry or Exit action, you should return the HANDLED_STATUS.

But having multiple returns from a function is against some popular, embedded coding standards, such as MISRA-C. So, to avoid violating such rules, you can declare an automatic variable 'status', which you will then set in every case statement and return at the end of the function.

Here you need to be careful not to forget to return the IGNORED_STATUS, when an event is NOT handled. You can do this either by initializing the status variable, or by providing the default case.

I prefer to leave status uninitialized and provide the default case, because then the compiler could issue a warning if I forget to set the status variable in some cases.

This particular compiler will do this when you provide the minus-W conditional-uninitialized and minus-W-sometimes-uninitialized options.


Which leads to the case where you don't yet set the status – that is when a state transition is taken.

Here, the TRAN() facility is perhaps the most interesting aspect of the design. It is closely related to the internal representation of the state variable, because transition means changing the state variable.

Previously, in all your state machine implementations, the state variable was an enumeration of states.

But today, it must be directly related to the state-handler functions, because they are provided as the parameter to the TRAN() facility.

Well, this is a classic use case for a pointer-to-function, which can point at different times to all the different state-handler functions comprising your state machine.

So in your C code, you need to typedef the StateHandler as a pointer-to-function, which has the signature of your state handler-function.

Now, you need to move the State enumeration before the StateHandler typedef.

And you also need to move around the typedefs for TimeBomb, so that they appear in the right order.

So, finally, you can define the TRAN() facility as a macro with the parameter target_, which it would simply assign to the state variable.

But, it would be also nice if the macro could take on the value of TRAN_STATUS, so that you can directly assign this to the status variable, like so.

This is possible by means of the C-language comma-operator, which evaluates expressions from left-to-right and takes on the value last expression. So, the following will assign the parameter target_ to me?state and it will take on the value TRAN_STATUS, which is exactly what you want.

This completes the transformation of the "wait4button" state specification to a state-handler function in C, so let me quickly apply the same syntax changes to all the other states in your state machine.

In the special initial pseudostate, you can simply return the TRAN() status.

The last problem is that the TRAN() macro references the state-handler functions that are often not yet known to the compiler, because they are defined later. You can easily fix this by providing the prototypes of all state-handlers right after the TimeBomb stuct. This list of all state-handler functions roughly corresponds to your previous enumeration of all states.

So, now you can delete the previous state-table-based code. But before you do, just note that your implementation based on state-handlers falls in the sweet spot, between the action-handlers that are too fine in granularity and the monolithic nested-switch implementation.

You also no longer need the problematic state-table, which was often sparse and thus wasteful, and discouraged developers from adding new states or new events. The state-handlers are much more maintainable.

But their greatest advantage lies in readability, because now the state-handlers directly represent the main components of a state machine: the states. Inside those states, you can very easily recognize other state machine elements, such as entry/exit actions, state transitions, and guard conditions.

In fact, I really hope that you view the state-handlers as a domain-specific language that works directly at the higher-level of abstraction of state machine elements, not the low-level C instructions.


Alright, but you are not quite done yet, because you still need to adjust the dispatch() operation from the previous lesson to work with state-handlers rather than the state-table.

First, change the type Status to State consistently with your new definition.

Next, change the type of prev_state to StateHandler pointer-to-function.

In the assertion, change the check of the state variable to make sure that it is not zero, meaning that it is initialized.

Now, in the call to the state handler you just remove the indirection layer of the state-table and all the indexing. Your state pointer-to-function variable offers a faster, immediate access to the current state handler.

When the state-handler reports that a transition has been taken…

You again adjust the assertion to make sure that the new state is valid.

And you again remove the indirection layer of the state-table in the calls to the state-handlers to process the exit of the previous state and entry to the new state.

Here, you cannot pass NULL-pointers for events, because your state handler always de-references the event-pointer parameter. 

But instead, you can use the immutable, static and const events with the reserved ENTRY_SIG and EXIT_SIG signals.

So, you pass the exit event to the previous state-handler and the entry event to the new state-handler.

Finally, you need to change the handling of the initial transition, because your initial state handler does not return the INIT_STATUS anymore.

Instead, for now, you can just check if the event passed to the dispatch operation has the reserved INIT_SIG, and if so, you skip the exit from the previous state.

The state machine initialization aspect will be re-designed in the next step, but right now you just want something that works.

The last thing you need to change is the initialization of the state variable in the constructor. Here, you set it to the initial pseudostate-handler.

Now, you can re-build the project and...,

what do you know -- the compiler reports no errors and no warnings.

By the way, let's check if the compiler notices an uninitialized case of the status variable...

Well, it actually does.


I'm sure you're curious how it works on your TivaC LanuchPad, so let's load it and test.

Reset – green light.

Button press – five, four, three, two, one, BOOM!

It works!


Alright! This is very encouraging. But you can still do much better than that!

Because, as it turns out, the dispatch operation for your new state-handler implementation is completely generic. There is really nothing specific to the TimeBomb sate machine there and the exact same implementation would work for any other state machine, like for example Blinky or something much more interesting.

So, there is an opportunity here to improve the design and include the generic state machine management right into your Micro-C-AO framework.

Specifically, the current design is that your Micro-C-AO active object framework provides the Active base class, which you then inherit in your application-level classes, like your TimeBomb, or Blinky, or other such classes.

So, now, you can exploit this inheritance to consolidate the common elements, like the state machine management shown in blue, in the  "Active" base class to be inherited rather than repeated. This is exactly what inheritance is for. By the way, if you missed my lessons about object-oriented-programming in C, inheritance is discussed in lesson-30.

But you can go even smarter about it. You can create even more useful class hierarchy by adding the FSM (for Finite State Machine) base class, which then will be inherited by Active and also, indirectly, by TimeBomb and Blinky.

The advantage of separating FSM from Active is that FSM can then be used by itself, for passive state machines that are not necessarily active objects. Such FSMs could be then useful for example inside interrupt service routines.

OK, this sounds like a plan, so let's try to code it.

So, the first set of changes will be in the Micro-C-AO-dot-H header file, where you need to declare the Fsm class based on the TimeBomb class.

By the way, this type of code modification, where you want to improve the design but without really changing the behavior is called "Refactoring.  

The TRAN() macro will require some changes, but let's leave it for later when the context will become clearer.

Inside the Fsm base class, all you really need is the state variable typed as the StateHandler pointer-to-function.

As far as the member functions of the Fsm class are concerned:

The constructor will take the initial state-handler in the specific subclass, such as the TimeBomb_initial.

The init operation will execute the initial transition and also an entry action to the first state.


The dispatch operation will handle all subsequent events.


Now, you need to adjust the Active class to inherit Fsm.

Here you no longer need to remember the dispatch operation, because this will be handled by the Fsm_dispatch.

Instead, you need to adjust the signature of the Active constructor to take the initial pseudo-state, just like in the Fsm constructor.

OK, so let's copy the FSM class declaration and open the Micro-C-AO-dot-C source file to add the implementation of this class.

Get rid of the unnecessary stuff and start defining the member functions.

The FSM constructor simply initializes the me-state variable to the initial pseudostate.

Let's skip the init operation for now…

And go straight to the dispatch operation:

which you already implemented for the TimeBomb state machine.

The only change here is getting rid of the check for the initial transition, because this has been redesigned and now is handled in the init() operation.

Speaking of which, the init operation is similar to dispatch, but it is simpler, because after executing the initial transition you can simply enter the new state.

But to enter a state, you need the immutable (static and const) entryEvt, which is local to the dispatch operation. To avoid duplicating this event, you can promote the immutable events to the file scope.


Now, you need to adjust the Active class constructor, because Active now inherits FSM, so the Active constructor must call the FSM's constructor.

And finally, in the Active start operation, you need to adjust the initialization of the state machine.

Here, you call the FSM-init operation, whereas you can pass a NULL event pointer, because initial transition is not triggered by an event and this parameter is passed to the initial pseduo-state handler only to conform with the StateHandler signature.

The previous, generic dispatch via a pointer-to-function becomes now the specific FSM_dispatch().

The framework update is now finished, so let's check whether the file Micro-C-AO-dot-C compiles.

Alright, so let's move on to the TimeBomb implementation, which needs a few tweaks due to the framework refactoring that you just did. 

You need to delete the typedefs that were moved up to the framework.

And you also need to delete the state variable from the TimeBomb class, because it is now inherited from the Active and indirectly from the Fsm superclass.

The last change will be in the TimeBomb constructor, due to the changed constructor of the Active superclass.

Here, you need to pass on TimeBomb_initial state-handler instead of the deleted TimeBomb_dispatch operation, and you don't need to initialize the state variable, because this is already done in the constructors of subperclasses.

That should be all, so let's try to compile the updated TimeBomb implementation.

Well, the compiler complains about the TRAN macro, because it cannot find the member "state" in the "me" struct. 

This is because now state is no longer a direct member of the TimeBomb class, but rather it is inherited from the Fsm super-super class.

The remedy is to modify the TRAN() macro to explicitly up-cast the "me" pointer to the Fsm superclass. As you remember from lessons about object-oriented programming, such upcasting is always legal and OOP languages, like C++ perform them automatically.

And as your are at it, you also need to cast the target parameter to StateHandler, because of the slight differences in the parameter list. Specifically, the "me" pointer of all TimeBomb state handlers points to the TimeBomb subclass, whereas the StateHandler pointer-to-function type expects the "me" pointer of the Fsm type, of the superclass.


OK, so after these final tweaks, the whole project builds cleanly.

Of course, the first order of business now is to check whether your TimeBomb still works…

Button press: five, four, three, two, one, BOOM! It works!

Alright, but as you already have your new state-handler implementation in the debugger, I though that you might be interested in quantifying the execution speed, especially because I claim that this method is "optimal".

For this, you might use an interesting feature supported by your TivaC Cortex-M4 processor, which allows you to measure the number of clock cycles taken by code execution. Specifically, the CPU has a hardware block called DWT (Data Watchpoint and Trace), where there is a cycle counter register.

So, here is how you can use this:

After resetting the CPU, open the Micro-C-AO-dot-C file and set a breakpoint at Fsm_dispatch. Your goal will be to time this function.

Now, run the code free and press the button. The breakpoint is hit, because you are about to dispatch the BUTTON_PRESSED event to your state machine.

Open a memory view and point it to the address of the DWT at hex-E000 1000. The cycle counter is the second word. Click on it and type zero to clear it.

Now, step OVER the Fsm_dispatch call. The cycle-counter register reads now hex-DF, which is the number of CPU clock cycles it took. This is 226 cycles in decimal.

Assuming 40 MHz CPU clock, this is about 5 microseconds. But more meaningful would be the relative comparison to the other state machine implementations.

So for example, I performed the same experiment, for the same transition, with the state-table implementation from lesson-38, and it executed in about 206 cycles. This is only 10% better than state-handlers, even though state-table is generally advertised as the fastest, because it avoids the switch statements.

As it tuns out, the new state-handler method is almost as fast, while being much more readable, maintainable, and significantly smaller in terms of memory, because you don't need the big and sparse state-table.

The nested-switch statement method from lesson 36 performed the fastest, at only 146 cycles, but this version didn't support entry and exit actions (which are both present in the measured transition), so this is not really comparable.


I'm unfortunately running out of my time budget for this lesson, but I still promised to show you the State Machine Compiler, SMC as yet another state machine implementation technique.

So, let me open the second project, lesson-39-smc, that will be also included in the download for this lesson. This second project contains fully functional TimeBomb for your TivaC LauchPad board with SMC.

The central piece of the SMC project is the file timebomb-dot-sm, containing the TimeBomb state machine specification in the SMC domain specific language.

Frankly, to me, such a DSL makes little sense, because the SMC language is still just textual representation not really simpler or more expressive than the direct state-handler-based implementation in C. I mention it here, only because various DSLs and special compilers have been quite popular back in the day, so you should know about this approach.

The dot-SM file requires an additional step of compiling it into the C code, and the Micro-Vision IDE offers you a way to assign the pre-processing tool to such custom files. Here, you assign the SMC compiler, which is included in the project. The only requirement is that you have java installed on your machine.

So now, when you build the project, the SMC compiler is invoked and it re-generates the files timebomb-unerscore-sm-dot-h and dot-c.

These files are included in the project, so you need to re-fresh them in the editor.

So, here is the C code generated by the SMC compiler. You can examine it by yourself, but it is obviously much more complex than your state-handlers.

The SMC code is based on the object-oriented State Pattern, with several classes, including every state being a separate class. There is also a special Context class for managing the state objects. 

Overall, the State-Pattern belongs to the category of the Data-Based strategies, which tend to be complex.

In contrast, the State-Handlers belong to the Code-Based strategies, which tend to be simpler.


This concludes this overview of the various state implementation strategies. Of course, there many more variants, but they all tend to be combinations of the basic techniques that you've just learned.

My clear preference and recommendation is the state-handler method, because I consider it the most readable and maintainable with good performance both in memory use and in CPU time.

That's why, this "optimal" implementation is now built into your Micro-C-AO framework.


In the next lesson, I'll move on to the modern, hierarchical state machines, which are perhaps the most powerful design tool I've ever used.


If you like this channel, please give this video a like and subscribe to stay tuned. You can also visit state-machine.com/video-course for the class notes and project file downloads.

Finally, all the projects are also available on GitHub in the Quantum Leaps repository "modern embedded programming course". Tanks for watching!