huge state machine

Go To Last Post
22 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This is not GCC, but a general programming question.

What do you use for huge finite state machines? I've wrote this huge state machine with about 20 states (it will probably grow as I add new features), with about 500 lines long (including comments) but I don't quite like how huge it is.

Felipe Maimon

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

fmaimon wrote:
This is not GCC, but a general programming question.

What do you use for huge finite state machines? I've wrote this huge state machine with about 20 states (it will probably grow as I add new features), with about 500 lines long (including comments) but I don't quite like how huge it is.

May I ask what the code does?

20 states isn't THAT much, but I guess you can always find a way to rewrite some of the states as variables and/or flags, thus reducing the number of "apparent" states. Or you can make two parallel FSM's.

Not sure it would always make things easier though. It depends on the overall logic of the application.

/Jakob Selbing

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

A common solution is to use a table processor and state tables rather than doing all the state transitions programmatically.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

hierarchical state machine?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

jaksel wrote:
May I ask what the code does?

20 states isn't THAT much, but I guess you can always find a way to rewrite some of the states as variables and/or flags, thus reducing the number of "apparent" states. Or you can make two parallel FSM's.

Not sure it would always make things easier though. It depends on the overall logic of the application.

The state machine parses commands received by uart (char by char) of my VFD display/boost converter circuit. I may be able to divide it in two, one for each section (VFD or boost), but I don't think it will help that much.

One thing I'm thinking about is creating a inline function for each big state and calling it instead of leaving the code inside the switch statement. As the function is inline, it won't have any penalty in execution.

Felipe Maimon

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
A common solution is to use a table processor and state tables rather than doing all the state transitions programmatically.

Can you please elaborate? Is it something like this?

Felipe Maimon

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Broxbourne wrote:
hierarchical state machine?

This is kind of dividing the state machine, right?

Felipe Maimon

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Do you use a big switch statement for the state machine?

When I desigin a state machine I usually give each state of the state machine it's own function.

The current state is remembered via a function pointer, the switch statement is completely eliminated. Just execute the function to which the function pointer points.

The context of the state machine can be put in some global variables.

Or you can put the whole context in a structure and pass a pointer to that stucture to the current state.

This gives you the flexibility of running multiple state machines at the same time (concurrently?) with different contexts.

You can find a complete example with source code and some documentation on my website

http://www.hoevendesign.com/#Net...

Doing magic with a USD 7 Logic Analyser: https://www.avrfreaks.net/comment/2421756#comment-2421756

Bunch of old projects with AVR's: http://www.hoevendesign.com

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

20 states is not such a big state machine. I've been working on an SDI-12 interface with about that many. Yes, it gets awkward and difficult to manage, but that the case with any project that gets big.

Jim

 

Until Black Lives Matter, we do not have "All Lives Matter"!

 

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

Is it something like this?

Yes,

Another good example is the menu processing in Atmel's Butterfly application.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you are using gcc, labels as values can be handy-
https://www.avrfreaks.net/index.p...

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
but I don't quite like how huge it is.

A complex system will always have a lot of code.
A FSM will help break down complexity.
You may have many states & sub-states but the code will be simple.
It will be easier to expand & maintain.
It will be more robust and easier to debug.
A FSM with 20 states whist not trivial, is not huge.

What is it that you don't like? The number of lines of code, the size of the code produced, to slow, maintaining/understanding it without a proper state diagram and design, the abstraction of FSM's?

Quote:
about 500 lines long (including comments)

As the comments are probably a third of the number of lines of code I would call the size of it very small.

Charles Darwin, Lord Kelvin & Murphy are always lurking about!
Lee -.-
Riddle me this...How did the serpent move around before the fall?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

LDEVRIES wrote:
What is it that you don't like? The number of lines of code, the size of the code produced, to slow, maintaining/understanding it without a proper state diagram and design, the abstraction of FSM's?

Too many lines of code inside a single function makes it hard to follow. I like small simple functions, but looks like I won't have that with a switch statement FSM. I just wanted to check if there were any other way of doing it...

Quote:
Quote:
about 500 lines long (including comments)

As the comments are probably a third of the number of lines of code I would call the size of it very small.

Actually most of the comments are in the same line of the code, so i'm guessing about 400 lines of code.

Felipe Maimon

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

A major factor of course is the number of inputs to the state machine and how much you are able to to simplify by
- having multiple state machines each with less inputs
- elimination of redundant/duplicated states states

Quote:
Too many lines of code inside a single function makes it hard to follow.

Maybe you should be following it on a state diagram instead of trying to design/follow it by looking at code. A picture is worth a thousand words.

Charles Darwin, Lord Kelvin & Murphy are always lurking about!
Lee -.-
Riddle me this...How did the serpent move around before the fall?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

State machine drawings - Anyone know of a free drawing software tool, or free add-on to MS office/Visio? I tried Visio, but too awkward.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you really want to dig into it, try LaTeX and the tikz package. LaTeX is a typesetting system using its own kind of markup language, you actually write source code for your document, which is then compiled to dvi, ps or pdf.

tikz is a drawing package for LaTeX, which can be used to draw state diagrams with all kinds of fancy additions.

The approach is totally different from any wysiwyg tool like word or visio, and the learning curve is very steep - but it's free and I'd always recommend it. It's free, customizable and extendable. You can use your favorite editor for coding. The source code can be split into several files, just as you would split up c code.

I tend to post off-topic replies when I've noticed some interesting detail.
Feel free to stop me.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'm not sure how it compares to Visio, but I've used Inkscape from time to time.

As of January 15, 2018, Site fix-up work has begun! Now do your part and report any bugs or deficiencies here

No guarantees, but if we don't report problems they won't get much of  a chance to be fixed! Details/discussions at link given just above.

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I use a lead pencil on A4 & an eraser for editing. Quick cheap & effective. Final product can be documented electronically using http://qfsm.sourceforge.net/scre... or just scanned into PDF for for subsequent filing if required.
Most packages just do not have a nice bezier curve drawing tool which will go from a state to previous state.

:idea: GUI FSM design interface for AVRStudio 5 :idea:

Edit.
I have just had a fiddle with Qfsm (after many years) and it now has a syntax checker & simulator. The bezier curves are easy to use.

Charles Darwin, Lord Kelvin & Murphy are always lurking about!
Lee -.-
Riddle me this...How did the serpent move around before the fall?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

stevech wrote:
State machine drawings - Anyone know of a free drawing software tool, or free add-on to MS office/Visio? I tried Visio, but too awkward.
Likely over-kill for what you want but this tool is new:
http://www.state-machine.com/qm/index.php
Notes:
UML-specific and QP-specific at that.
Non-open and has a EULA.
Only on Microsoft Windows.

Visio -
Quantum Leaps has Visio stencils to ease use of Visio
and has a link to an open UML tool:
http://www.state-machine.com/resources/goodies.php

"Dare to be naïve." - Buckminster Fuller

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Qsfm requires, (my win 7 PC) an install of QT and all its baggage. Is that onerous?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi Steve, I had Qt installed on my Windows 7 box anyway , but I never saw or have seen, a problem with it. I reckon that the next best thing to XP-SP3 is Windows7
Qfsm runs nicely on my box, but I still reckon I will do the design on paper and do the final drawing with Qfsm(if required)

I really think that the OP is probably getting confused because he is trying to understand whats going on by looking at code. Really hard to with more that 5 ot 6 states.

Charles Darwin, Lord Kelvin & Murphy are always lurking about!
Lee -.-
Riddle me this...How did the serpent move around before the fall?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yes, simple pencil and paper state diagrams is what I use to ensure the overall design makes sense - and so that I can see the big picture. With computer documents, I always feel like the view is via a soda-straw.

Even when the top level design gets to a B sized drawing, it's still better than a dozen little computer files on the LCD.

I have a professional endeavor now that is 10 or so independent state machines, each running under the supervision of a cooperative scheduler (single stack, to save RAM). This is a run-to-completion scheduler. Single stack means the state machines either use static variables (in C) or get some RAM, cast it to a struct of variables, and keep the pointer to that in the task's TCB - making the task's code reentrant.

Using a single stack eliminates the worry "is my stack big enough for the worst case nesting which may occur after I think I'm done testing?" and the "I don't have enough RAM - dare I make some stacks smaller?.

The scheduler for this is a later version of "OPEX", for which the source code is in the projects section on this forum. Lots of changes made, and a port to an ARM7 done.