Have you found yourself in the all too familiar situation lately, where you have had to dig up some old code from the archives, just to find out that you do not understand a thing? There is no design documentation, no useful code comments and the code has a completely undecipherable structure. Perhaps it is even your own two year old code! If the program flow of the application resembles a state machine design, we could have helped you to avoid this situation.
State machines exist in every embedded programmer's toolbox. Many problems are best solved by viewing the implementation as moving trough a set of distinct states. Sometimes this is expressed in code that shows at least some similarity to an existing pattern for a state machine implementation. Sometimes the written code bears no resemblance at all to a state machine pattern, but still behaves like a state machine.The most common state machine patterns used by C programmers are variations of the following:
Nested switch statements that switch on the current state and latest event from the environment. A mix of switch statements and if statements, that also keep track of the current state and last received event.
A table-driven approach where the transitions of the state machine are encoded in a table and an accompanying driver that processes events and deducts the next state from the information in the table.
All these patterns have their merits if the state machine is small and simple. The problem is that it is only natural to sometimes take the easy road and modify a part of the code locally, inserting a fix or a feature to make things work again as fast as possible. When this has happened a few times, the code structure starts to deteriorate and after that it is usually downhill.
A state machine can have hundreds of states and still be simple to understand if the transition pattern is trivial, for example, if one state is only connected to one other state that is in turn connected to just one other state etc, so the states form an ordered sequence.
But a state machine with more than approximately 15 states, more than one region, that is hierarchical and has an irregular transition pattern can be considered to be complex. If such a state machine is only expressed through uncommented code, it can be virtually impossible to understand how the implementation corresponds to the high-level behavior of the application. This can be OK as long as everything works, but if there are problems or if the feature set needs to be extended, you are in trouble. Adding code to a structure you do not really understand can be thrilling at best and a real nightmare at worst, especially when deadlines are looming or one of your most important customers is stuck with no workaround.
What's more, as the code is handwritten, the design perhaps does not use things like regions or hierarchy, thus complicating things by creating artificial dependencies among logically separable parts.
Just imagine the code for a complex state machine with 50 or 500 states and the difficulties involved in maintaining and enhancing it!
Of course, some of the problems described above can be avoided with strict design and coding rules. But face it: coding rules that are not enforced by tools will be violated occasionally.
Consider the following situation: You have been assigned the task of fixing a critical problem in one of your otherwise fairly stable products. Because the product has not been touched for a while, this is your first encounter with the code, and the original designer is no longer with company.
The documentation is exemplary with a clear structure and notes explaining the purpose of most constructs. However, the documents are four years old and the latest code revision is merely 1.5 yearsold. Something is missing.
Furthermore, when you examine the code you find sections that are not documented. You now have two alternatives:
1. Decipher the meaning of the undocumented code and update the documentation, and then do some re-factoring to clean up the code structure before adding your solution.
2. Ignore the discrepancies between the design and the code, fit your changes into the existing structure in the fastest and most convenient way and move on.
As a responsible and conscientious developer, of course you always pick alternative 1. The problem is that a previous developer did not choose alternative 1, and given a firm deadline it can be very tempting to go for alternative 2 even now.
The dangers of always going for number 2 are obvious: the code quality deteriorates slowly (or very fast!) to a point where each new attempt to fix a problem will inadvertently create a new set of problems. In the most extreme case this might force the company to withdraw the product from the market, since it can no longer be maintained.
Testing an application based on state machines can be a real challenge. Consider the following questions:
How do I force the state machine into that particular state? Is it possible to find an event sequence that takes the machine to the desired state by ocular inspection? If the state machine is made up of more than one parallel region and maybe contains some hierarchy—how do I ensure that there are no dead-locks or unreachable parts of the state machine? How do I keep track of which states and transitions I have actually activated with my test vectors? How do I try out my design ideas when the hardware is not even available yet? When the hardware is ready and my application is almost finished, how do I weed out the remaining functional issues without drowning in low-level C or C++ implementation details?
By using a design tool with code generation facilities you gain at least two things:
To illustrate the value of deterministic translation, consider the situation where a working application must be extended. If the existing code is not rigidly structured and guarded by strict coding rules, there will always be the question of exactly how to merge the new functionality into the old code. Do I put this new logic here or there, or even in both places? Automatic code generation solves this problem by always following the same pattern for generating the code from the specification.
The value of ensuring that design and code stay in sync is hard to overestimate. By always making changes in the design and then generate the code, the resulting code will always be consistent with the design. Spending time on design specifications that are not kept up to date with the actual implementation is a huge waste of time, for a number of reasons:
To sum it up: Automatic code generation gives you the combined benefits of automatic deterministic code generation from state machine specifications and the ability to trust the design specification.
There is a tool from IAR Systems that will help you with everything we have discussed above: visualSTATE. It will help you with documentation, with code/design consistency, and with code generation. And as we shall see, it will help you with testing as well.
With the help of formal methods like model checking, it is possible to find a number of unwanted properties in the design, for example dead-locks and unreachable regions. The verification is performed by encoding the state machine as a set of Boolean equations that describes the complete state machine system. In this set of equations, unwanted properties can be found by applying Boolean operators following different algorithms. Different methods can be used to balance the need for verification results against the time and computer resources available.
Imagine a fairly complex state machine with a small number of parallel regions, but with some dependencies between regions:
For example, a transition in one region can be dependent on another region being or not being in a particular state etc. If there are more than one such dependency between regions, there is a possibility that there are dead-locks in the design such that a particular state or set of states, cannot be left once entered.
Or the opposite can occur, so that a particular state or set of states can never be activated due to the blocking transition condition.
Other situations might also imply dead-locks or unreachable parts of the design. Transition conditions that will never be met, for example if a variable in the transition can never be assigned a value to fulfill the condition. If a transition condition can never be fulfilled, this might cause either a dead-lock situation or create an unreachable part of the design. (Even if it doesn't, it is still an indication that some assumption in the model is wrong—if the transition can never be activated, why is it there?)
Formal methods only answer the question is this particular property present in the design? To test thefunctional behavior, you must use tests based on the functional specification. The easy part is probably to cover all the "middle-of-the-road" cases; it is more difficult to validate what happens when the execution reaches the dark corners of the design. Test facilities such as those found in visualSTATE, will help you to start simulating the design as soon as you have saved the very first design draft.
You can record test sequences to play back later, or get statistics about which states you have visited and which transitions you have activated and the frequency of visits or activations. The Verificator can even suggest event sequences to bring the design into a specific state configuration. This way you canensure that the state machine design works as intended even before the hardware design is started! By combining this with high-level GUI/Front panel builders you can even show off a GUI design with functionality to the marketing department at an early stage.
The unique integration between the IAR Embedded Workbench debugger C-SPY and visualSTATE makes it possible to reduce the time needed to find the remaining functional errors, once the design is nearing completion. You can follow the application logic on the design level, instead of on the C level—without writing support code for communication etc!
Breakpoints can be set on everything from specific states and transitions to complete state configurations. If full-speed execution is crucial, the system state can be updated only when the execution is stopped by the user, or hitting a normal C breakpoint.
All technical solutions that make the life of programmers easier come at a price. There is either a steep learning curve or restrictions on what and how things can be expressed.
However, the cost of using a tool like visualSTATE is small compared to the gains:
The slope of the learning curve is gentle and the time needed is small. You are up and running at fullspeed in just a few days. You do not have to take the impact of full UML—which seldom brings that much added value for a small- to medium-sized embedded system anyway.
The UML state machine subset is an aid to help you separate the pure state machine logic from the intended side effects. This in turn will have the effect that your application is very portable to new hardware, as typically all hardware dependencies will be isolated in just a few places. The price to pay is that sometimes you will have to think through your solution an extra time, since your first idea might be easy to express in straight code but difficult to express in a formal state machine language, like the UML subset used by visualSTATE.
This article is written by Anders Holmberg at IAR Systems.