Hello and welcome to the Modern Embedded Systems Programming course. My name is Miro Samek and in this forth lesson on state machines you'll learn about state tables. In the process, you will see how to implement state tables in C and how to extend this implementation to add state entry and exit actions.


So far in this segment about state machines you've learned the most straightforward nested-switch statement implementation in C. For example, the time-bomb project from lesson 36 was implemented that way.

The whole state machine was coded in just one dispatch function and consisted of the switch statement that discriminated based on the state-variable. Each case handled a separate state. Within each state, you had another, nested switch that discriminated based on the event signal. The cases were all events handled by this particular state.

A variation of this implementation technique was also applicable to the input-driven state machines that you've learned in the previous lesson-37. For instance, the Blinky-Button project from that lesson was again coded with the switch statement around the state-variable. But because the whole state machine handled essentially just one event – the low-quality SAMPLE-event-- there was no need for the second level of nested switch based on the event. Instead, each state contained guard conditions that checked the event parameters to discover the truly interesting events.

But, as I mentioned in those previous lessons, this particular state machine implementation is not the most efficient or elegant. It's just the most straightforward and therefore the most common.

So, today I'd like to show you another implementation of a different kind, based on state tables. Again, I don't think that this technique is the most elegant or efficient either, but it demonstrates a different way of thinking about the problem and therefore is a good stepping stone to understanding other state machine implementations. Also, state tables are a quite popular representation of state machines, so you definitely need to know how they work.

Actually, you've already seen some state tables in the last lesson-37 in the part about Mealy and Moore state machines for describing electronic circuits. Because the inputs to those state machines were logic signals, the tables were Truth Tables, but they can be easily generalized to events.

For example, if we just use the already assigned names for states and name the events, LOW for 0 and HIGH for 1, we can re-write the Truth Table as follows:

But then, notice that for every state in this one dimensional table you repeat all the events. This means that you can re-organize the same information into a two-dimensional table.

You leave the states as they are, but you list events along the second, horizontal dimension. Now, every cell in the two-dimensional table contains the pair: next-state and action to be performed for the given event in a given state.

So, these are the state tables: 1-dimensional and 2-dimensional. They both contain exactly the same information, and both correspond one-to-one to the state diagram, just as the original Truth Table did.


Alright, so now, let's apply the same technique to represent the Time-Bomb software state machine from lesson 36 as the two-dimensional state table.

First, open up the project from lesson 36 and look up all events that are posted to the TimeBomb. These events are enumerated in the bsp.h header file and are: BUTTON_PRESSED, BUTTON_RELEASED, and TIMEOUT.

Now, let's open up the model of TimeBomb, and see which states you have in your state machine there. These states are: wait4button, blink, pause, and boom.

For each state, you look whether it handles a given event. For example, state "wait4button" handles the BUTTON_PRESSED event, so you put the next state and actions in the corresponding cell of the table.

For all events not found in the given state, you put "ignore", or alternatively, you can put "error" if you believe that a given event should never arrive at that state. 

You do the same for the "blink" state, which handles only the TIMEOUT event.

Now, in state "pause" there is a problem, because this state has a guard condition with one transition going to the "blink" state and the other going to the "boom" state. Here, I just put both these next-states, but with the question marks. These are then further explained as a footnote to the state table.

An alternative notation is to put the whole guard conditions directly in the table, but that leads to quite a clutter. You'll see how to work around it in the actual code.

Which leads to the most interesting question for today: how to use the state table representation as a basis for the actual implementation?

So, for the coding exercise in this lesson, let's start with the TimeBomb from lesson-36, which I showed already to remind you about the nested-switch statement state machine implementation.

So, for today, copy lesson-36 directory to lesson-38, get inside the new directory and double-click on the project lesson to open it in the micro-Vision IDE.


The first question in implementing the state table is how to represent it in code.

Well, the C language supports two-dimensional arrays directly.

So, you can have the "TimeBomb_table" array, with the first dimension corresponding to the number of your states and second dimension to the number of your events.

A noteworthy trick to codify these dimensions is to place a special constant at the very end of the enumeration for states, which I call MAX_STATE

and another in bsp.h at the end of the enumeration for event signals: MAX_SIG.

If you keep these MAX constants at the end, you will automatically keep track of any changes inside your enumerations.

Now, the most interesting decision is about the type of the entries in your TimeBomb_table.

Well, some state table implementations make each entry in such state table to be a struct, with a whole bunch of members like: guard condition, new state, transition action, and other elements.

However, this abundant information in each and every cell of the state table makes the table very complex to initialize, takes a lot of memory, and, most importantly, makes even a simple state machine implementation fragmented into literally hundreds of little functions.

So, instead I recommend a much simpler solution, in which every cell in the array simply holds an action, named here TimeBombAction. This action function can then evaluate guards and can also change the state internally, so no separate next-state information needs to be stored.

The TimeBombAction is a pointer to function to be called when a given event arrives in the given state. I already used pointers to functions in several lessons in this video course, for example in lesson-15 about the startup code and vector table initialization, in lesson-23 about real-time operating system, and in lesson-32 about polymorphism in C.   

The best way to specify a pointer to function in C is through a typedef. The actual pointer to function must be in parentheses followed by the parameter list.

The action function will return void.

To get easy access to data members of the TimeBomb, the action function will take the pointer "me", and to get access to the event parameters, it will also take the event pointer "e".

With this definition, you can now start filling up your state table.

Please note that the state table is completely known at design time and fixed at runtime. Consequently, it can and should be constant. This is not only safer, because the compiler will not allow you to change the const state table, but it will also allow the state table to be placed in ROM, instead of taking up space in the precious RAM.

But a constant object has to be initialized right away, at its definition. The only way to perform this in C is by using the C array initializer.

For a two-dimensional array like this one, you initialize entire rows determined by the last dimension, which are the event signals.

To simplify the job and to avoid mistakes, let me place comments with the labels for all the signals enumerated in bsp.h and all states enumerated inside the TimeBomb class.

But your have to be very careful here, because the indexes into the state table array must be consecutive and start at zero. However, the signals in BSP-dot-H don't start at zero, but rather are offset by the USER_SIG constant. This offset is then defined in Micro-C-AO dot-H header file, where you see that the very first signal with the default value zero is INIT_SIG.


So, the complete list of signals in your state table must include INIT_SIG at the beginning.

Now, you can fill out the table cells, per the state table you've designed before, except the INIT_SIG, which will be handled only in the "wait4button" state in the TimeBomb_init function.

For each signal-state combination that *is* being handled, you insert a pointer to function with the name TimeBomb followed by the state name followed by the signal name. For example, the state "wait4button" handles the BUTTON_PRESSED event, so you insert here pointer to function TimeBomb-underscroe-wait4button-underscore-PRESSED.

If a given signal-state combination should be ignored, you insert the TimeBomb_ignore function pointer.

You proceed like this, effectively copying your initial design, until you fill out the entire TimeBomb_table array.


The last step is then to define all the functions used in the table.

So, starting with the TimeBomb_init, you provide the prototype corresponding to your TimeBombAction pointer to function and just copy the actions from the original top-most initial transition.

As you are at the initialization, the state variable me-state must be initialized to the WAIT4BUTTON state in the constructor. This is because me-state will be used as an index into the state table, so it has to have a well-defined value. 

The action function for the "wait4button" state and BUTTON_PRESSED event is implemented the same way. Again, you just copy the action from the original nested-switch statement.

The ignore action is just an empty function. 

The blink-TIMEOUT action function is done the same way.

And so it the pause-TIMEOUT action function. You just copy over the corresponding case from the nested-switch statement.

So now, you can clean up the old code inside the TimeBomb-dispatch function and re implement it with the state table.

The code here is remarkably simple and elegant. You take your TimeBomb_table and index into it with the me-state variable and the e-sig signal. Then you cal the selected action function via a pointer. You pass the "me" pointer and "e" pointer as parameters to the call.

A good idea at this point is also to assert that the variables used as indexes into the array are in bounds.

As a final touch, you can add the static keyword to all your TimeBomb functions, just as it is already done for the dispatch function. This is a good programming practice, because the static keyword limits the visibility of the static elements inside the given module and prevents any accidental access to them from anywhere else.

Alright, so let's build the code and load it to the TivaC LaunchPad board.

Now: reset button – green light

SW1 button: five, four, three, two, one, BOOM!

OK, it works!


So now, in the second part of this lesson I'd like to introduce another big improvement in state machines, which can eliminate many annoying repetitions in both your designs and code.

For example, in your TimeBomb state machine, the state "blink" can be entered through two different transitions: The BUTTON_PRESSED transition from "wait4button" and the TIMEOUT transition with a guard from "pause".

In both of these transitions, there is a group of actions (Red-LED ON and arm Time-event for one-half second) that is repeated. This is because these actions are a required preparation for the "blink" state and so they must be executed whichever way the "blink" state is entered.

These actions logically belong to the "blink" state, and it would be much better if you could attach these actions explicitly to that state.

And this is exactly what entry and exit actions to states allow you to do.

Specifically, you can provide an entry action to state "blink" and put there the actions that always need to be executed upon the entry to that state. 

As you can see, the UML notation for this is the word "entry", or just the letter "e", inside the state shape, followed by the forward slash and a list of actions.

You can then remove these actions from all the incoming transitions.


But you don't need to apply the entry and exit mechanism just to the repeated actions on transitions. In fact, you should take a critical look at your entire state machine and check which actions would better fit into states rather than transitions.

For example, the action GreedLED-on in the top-most initial transition really belongs to the "wait4button" state, so you can put it in the entry action and remove it from the transition.

Now, whatever is done in the entry actions, often needs to be undone in the exit actions. For example, the Green-LED turned on upon the entry to "wait4button" needs to be turned off upon the exit, whichever way the exit happens. So, you should move that action from the BUTTON_PRESSED transition to the exit action from the state.

Similarly, if the "blink" state turns the Red-LED on in its entry action, it should turn it off in its exit action, instead of doing it on the transition.

On the other hand, the arming of the time event that also happens on that transition logically belongs to the "pause" state, because it determines how long the pause state will be active.

Finally, the action to turn all LEDs on to simulate the explosion logically belongs to the entry action to state "boom".

So, here it is: Your TimeBomb state machine version that performs most of the actions in states rather than transitions.

If you remember the last lesson, state machines that associate actions with states are called Moore machines and state machines that associated actions with transitions are called Mealy machines.

So, in a sense what you've just done is that you converted your TimeBomb state machine from Mealy-type into Moore-type.

But, I wouldn't take the Mealy-Moore classification from hardware state machines too far into the software domain. Because typically, software state machines have characteristics of both Mealy and Moore machines.

For example, your TimeBomb still performs some actions on transitions, such as the action on TIMEOUT transition in state "pause", and this is OK.

Having said that, my decades of experience with software state machines shows that Moore-type state machines with actions associated with states tend to be generally better, cleaner, more robust and more maintainable than Mealy machines with actions associated with transitions. 


So now, the last step in this lesson is obviously to implement your Moore-version of the TimeBomb state machine using the state table technique.

You have of course many options to incorporate entry and exit actions into the state table.

But one possibility is to apply the same idea that you already used for the initial transition, and that is to add two new special signals ENTRY and EXIT into the "uc_ao.h" header file.

Now, you immediately need to add these signals to the state table as well, because otherwise the table won't match your event enumeration.

And then, you need to insert entry and exit action functions for all states that handle them in your state diagram.

So for example: your state "wait4button" has an entry action and an exit action.

State "blink" has also both entry and exit actions.

On the other hand, state "pause" has only entry and ignores exit

and so does state "boom".

The next step is then to define the Entry and Exit action functions that you've already placed in your state table.

The "wait4button" state entry action turns the Green-LED on,

And the exit action turns the Green-LED off.

The "blink" state entry action turns the Red-LED-on and arms the time event for one-half second

And the exit action turns the Red-LED-off.

The "pause" state entry action just arms the time event for one-half second.

The "boom" state entry action... 

Oh, wait, you need to remove the transition action already placed in the entry to "blink"

So, the "boom" entry action turns all the LEDs on.


And finally, in your dispatch function, you must actually call the correct exit and entry actions when the transitions are taken.

But here is a problem: how would you know that a transition was taken?

Well, one solution for this would be that the action handlers themselves would you "tell" you what just happened inside.

Specifically, an action handler could return an enumerated status information, such as:

TRAN_STATUS will tell you that a transition was taken;

HANDLED_STATUS will tell you that an action was handled but without taking a transition

IGNORED_STATUS will tell you that an event was ignored;

and finally, INIT_STATUS will tell you that the initial transition was taken


With this, you now need to add the Status return type to the signature of your action handler

And, of course, you need to go back and add the Status return to all your TimeBomb action handlers.

So, starting from the top: you need to add "return INIT_STATUS" to the initial transition.

You return the HANDLED_STATUS from the entry action.

And from the exit action as well.

You return TRAN_STATUS from a transition action that changes the state.

Again, you return the HANDLED_STATUS from the entry and exit actions…

And you return TRAN_STATUS from the transition actions.

Finally, you return the IGNORED_STATUS from the ignored action.


With that preparation, you can get to modify the dispatch operation to add calling the exit and entry actions on transitions.

First you define the status variable as well as the prev_state variable to save there the current state before any potential transition.

Next, you execute the appropriate action from your state table, but now you save the returned status into your variable.

But next, you check if the reported status corresponds to a transition.

If so, you assert that the new state is in range

and then you call the state table action corresponding to the previous state and the EXIT signal.

At this point it really doesn't matter which event you pass to the action, because the exit action should never use the event. It is there only for compliance with the action-handler signature. Therefore, you can pass here the zero pointer.

After the exit from the previous state, you need to enter the current state, so you call the state table action corresponding to the current state and the ENTRY signal.

Again, you can pass the zero pointer for the event parameter.


But you are not completely done yet, because you still need to correctly handle the state entry after initial transition.

So, if the returned status is INIT_STATUS, you just enter the new state, as before, but you don't exit any state.

And this is about it. You try to build the code and load it to the board...

Reset button: Green light

SW1: five, four, three, two, one, BOOM!

Well, it still works!


This concludes this lesson about state tables and entry/exit actions to states.

To summarize: The state table represents a different type of the state machine implementation strategy, because in contrast to the nested-switch that was pure code, state table is data-driven.

Specifically, the implementation is centered around the state table data structure, which is then indexed into by both states and event-signals. Other data-driven state machine implementations include representing states as data objects, which are then interconnected and traversed at run time to execute transitions.

The main advantage of the state table representation is the highly regular structure that forces you to consider all possible state and event combinations. Also, the implementation provides relatively good and deterministic runtime performance.

However, the technique has also many disadvantages.

The whole state machine code is highly fragmented into a large number of little "action handlers".

Also, state tables themselves tend to be sparse with a lot of gaps, like even in your case of a trivially simple TimeBomb state machine.

This is because the event-signals are used as indexes into the table and it is difficult to avoid gaps in the numerical values of the signals. For example, the event BUTTON_RELEASED is not handled by the current version of your TimeBomb. But it might be needed somewhere else in the system and it is generally difficult to optimize the numerical values of signals for multiple state machines.

But perhaps the biggest disadvantage of state tables is that they discourage adding new states and events, because that requires adding the whole new column or row into the table. Developers perceive this as a lot of overhead, and therefore they tend to avoid it. Instead, they add internal variables and guard conditions, which leads back to "spaghetti code" and defeats the purpose of using state machines that were exactly intended to avoid the "spaghetti".

In the next lesson, I will show you another state machine implementation strategy based on a reusable event processor that I consider most optimal. Stay tuned!


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!