Conception de la machine à états C

Je réalise un petit projet en C et C ++ mixtes. Je construis une petite machine d’état au cœur de mon thread de travail.

Je me demandais si les gourous de SO partageraient vos techniques de conception de machines à états.

REMARQUE: je suis principalement après des techniques d’implémentation éprouvées.

MISE À JOUR: Sur la base de toutes les informations recueillies sur SO, je me suis installé sur cette architecture:

entrer la description de l'image ici

Les machines d’état que j’ai conçues auparavant (C, pas C ++) sont toutes passées à un tableau struct et à une boucle. La structure consiste essentiellement en un état et un événement (pour la recherche) et une fonction qui renvoie le nouvel état, quelque chose comme:

 typedef struct { int st; int ev; int (*fn)(void); } tTransition; 

Ensuite, vous définissez vos états et événements avec des définitions simples (les ANY sont des marqueurs spéciaux, voir ci-dessous):

 #define ST_ANY -1 #define ST_INIT 0 #define ST_ERROR 1 #define ST_TERM 2 : : #define EV_ANY -1 #define EV_KEYPRESS 5000 #define EV_MOUSEMOVE 5001 

Ensuite, vous définissez toutes les fonctions appelées par les transitions:

 static int GotKey (void) { ... }; static int FsmError (void) { ... }; 

Toutes ces fonctions sont écrites pour ne prendre aucune variable et renvoyer le nouvel état pour la machine à états. Dans cet exemple, les variables globales sont utilisées pour transmettre toute information dans les fonctions d’état si nécessaire.

L’utilisation de globales n’est pas aussi grave que cela en a l’air puisque le FSM est généralement enfermé dans une seule unité de compilation et que toutes les variables sont statiques (c’est pourquoi j’ai utilisé des guillemets autour de “global”). FSM, que vraiment mondial). Comme avec tous les globals, cela nécessite des soins.

Le tableau des transitions définit alors toutes les transitions possibles et les fonctions appelées pour ces transitions (y compris le tout dernier attrape-tout):

 tTransition trans[] = { { ST_INIT, EV_KEYPRESS, &GotKey}, : : { ST_ANY, EV_ANY, &FsmError} }; #define TRANS_COUNT (sizeof(trans)/sizeof(*trans)) 

Cela signifie que si vous êtes dans l’état ST_INIT et que vous recevez l’événement EV_KEYPRESS , appelez GotKey .

Le fonctionnement du FSM devient alors une boucle relativement simple:

 state = ST_INIT; while (state != ST_TERM) { event = GetNextEvent(); for (i = 0; i < TRANS_COUNT; i++) { if ((state == trans[i].st) || (ST_ANY == trans[i].st)) { if ((event == trans[i].ev) || (EV_ANY == trans[i].ev)) { state = (trans[i].fn)(); break; } } } } 

Comme mentionné ci-dessus, notez l'utilisation de ST_ANY comme caractères ST_ANY , permettant à un événement d'appeler une fonction, quel que soit l'état actuel. EV_ANY fonctionne également de manière similaire, permettant à tout événement à un état spécifique d'appeler une fonction.

Cela peut également garantir que, si vous atteignez la fin du tableau des transitions, vous obtenez une erreur indiquant que votre FSM n'a pas été correctement construit (en utilisant la combinaison ST_ANY/EV_ANY .

J'ai utilisé un code similaire pour cela sur un grand nombre de projets de communication, tels que l'implémentation précoce de stacks de communications et de protocoles pour les systèmes embarqués. Le grand avantage était sa simplicité et sa relative facilité à modifier le tableau des transitions.

Je ne doute pas qu'il y aura des abstractions de niveau supérieur qui pourraient être plus appropriées de nos jours, mais je pense qu'elles se résumeront toutes à cette même structure.


Et, comme l'indique ldog dans un commentaire, vous pouvez éviter les globales en transmettant un pointeur de structure à toutes les fonctions (et en l'utilisant dans la boucle d'événement). Cela permettra à plusieurs machines à états de fonctionner côte à côte sans interférence.

Il suffit de créer un type de structure qui contient les données spécifiques à la machine (état minimum) et les utilise plutôt que les globales.

La raison pour laquelle j'ai rarement fait cela est simplement parce que la plupart des machines d'état que j'ai écrites étaient des types singleton (one-off, at-process-start, lecture de fichier de configuration par exemple), sans avoir à exécuter plus d'une instance . Mais cela a de la valeur si vous devez en utiliser plus d’un.

Les autres réponses sont bonnes, mais une implémentation très “légère” que j’ai utilisée lorsque la machine à états est très simple ressemble à:

 enum state { ST_NEW, ST_OPEN, ST_SHIFT, ST_END }; enum state current_state = ST_NEW; while (current_state != ST_END) { input = get_input(); switch (current_state) { case ST_NEW: /* Do something with input and set current_state */ break; case ST_OPEN: /* Do something different and set current_state */ break; /* ... etc ... */ } } 

J’utiliserais ceci quand la machine d’état est assez simple pour que l’approche de la table de transition d’état et de pointeur de fonction soit exagérée. Ceci est souvent utile pour l’parsing syntaxique caractère par mot ou mot par mot.

Pardonnez-moi de briser toutes les règles de l’informatique, mais une machine à états est l’une des rares (je ne peux compter que deux endroits) où une goto est non seulement plus efficace, mais rend également votre code plus lisible. Parce que les goto sont basées sur des lettres, vous pouvez nommer vos états au lieu de devoir suivre un tas de chiffres ou utiliser un enum. Cela donne aussi un code beaucoup plus propre puisque vous n’avez pas besoin de toutes les tâches supplémentaires des pointeurs de fonction ou des énormes instructions de commutation et des boucles while. Ai-je mentionné que c’est aussi plus efficace?

Voici à quoi peut ressembler une machine à états:

 void state_machine() { first_state: // Do some stuff here switch(some_var) { case 0: goto first_state; case 1: goto second_state; default: return; } second_state: // Do some stuff here switch(some_var) { case 0: goto first_state; case 1: goto second_state; default: return; } } 

Vous obtenez l’idée générale. Le fait est que vous pouvez implémenter la machine à états de manière efficace et relativement facile à lire et crier au lecteur qu’il examine une machine à états. Notez que si vous utilisez les goto , vous devez toujours faire attention car il est très facile de se tirer dans le pied tout en faisant cela.

Vous pourriez envisager le compilateur de machines à états http://smc.sourceforge.net/

Ce splendide utilitaire open source accepte une description d’un automate dans un langage simple et le comstack dans une douzaine de langages, y compris C et C ++. L’utilitaire lui-même est écrit en Java et peut être inclus dans une construction.

La raison pour cela, plutôt que de coder manuellement en utilisant le modèle d’état GoF ou toute autre approche, est qu’une fois que votre machine à états est exprimée en code, la structure sous-jacente a tendance à disparaître sous le poids du passe-partout à générer. En utilisant cette approche, vous obtenez une excellente séparation des préoccupations et vous conservez la structure de votre machine à états “visible”. Le code généré automatiquement entre dans les modules que vous n’avez pas besoin de toucher, de sorte que vous pouvez revenir en arrière et manipuler la structure de la machine d’état sans affecter le code de support que vous avez écrit.

Désolé, je suis trop enthousiaste et sans aucun doute, tout le monde est parti. Mais c’est un utilitaire de premier ordre, et bien documenté aussi.

Assurez-vous de vérifier le travail de Miro Samek (blog State Space , site Web State Machines & Tools ), dont les articles du C / C ++ Users Journal étaient excellents.

Le site Web contient une implémentation complète (C / C ++) sous licence open source et commerciale d’une structure de machine à états (QP Framework) , un gestionnaire d’événements (QEP) , un outil de modélisation de base (QM) et un outil de suivi (QSpy). permet de dessiner des machines à états, de créer du code et de les déboguer.

Le livre contient une explication détaillée du pourquoi / du pourquoi de la mise en œuvre et de la manière de l’utiliser et constitue également un excellent matériel pour comprendre les principes fondamentaux des machines à états hiérarchiques et finis.

Le site Web contient également des liens vers plusieurs packages de support de carte pour l’utilisation du logiciel avec des plates-formes intégrées.

J’ai fait quelque chose de similaire à ce que décrit paxdiablo, au lieu d’un tableau de transitions d’état / d’événement, j’ai configuré un tableau bidimensionnel de pointeurs de fonction, avec la valeur d’événement comme index d’un axe et la valeur d’état actuelle L’autre. Ensuite, je viens d’appeler state = state_table[event][state](params) et la bonne chose arrive. Les cellules représentant des combinaisons état / événement invalides obtiennent un pointeur sur une fonction qui le dit, bien sûr.

Évidemment, cela ne fonctionne que si les valeurs d’état et d’événement sont les deux plages contiguës et commencent à 0 ou suffisamment proches.

Stefan Heinzmann présente dans son article une très belle machine à états C ++ basée sur des modèles.

Comme il n’y a pas de lien vers un téléchargement complet du code dans l’article, j’ai pris la liberté de coller le code dans un projet et de le vérifier. Les éléments ci-dessous sont testés et comprennent les quelques pièces manquantes mineures mais assez évidentes.

La principale innovation est que le compilateur génère un code très efficace. Les actions d’entrée / de sortie vides sont gratuites. Les actions d’entrée / sortie non vides sont insérées. Le compilateur vérifie également l’exhaustivité de l’organigramme. Les actions manquantes génèrent des erreurs de liaison. La seule chose qui n’est pas prise est le Top::init manquant.

Ceci est une très bonne alternative à l’implémentation de Miro Samek, si vous pouvez vivre sans ce qui manque – c’est loin d’être une implémentation complète de Statechart UML, bien qu’elle implémente correctement la sémantique UML, / actions d’entrée dans le bon ordre.

Si ce code fonctionne pour ce que vous devez faire et que vous avez un compilateur C ++ décent pour votre système, il fonctionnera probablement mieux que l’implémentation C / C ++ de Miro. Le compilateur génère pour vous une implémentation aplatie de la machine d’état de transition O (1). Si l’audit de la sortie de l’assemblage confirme que les optimisations fonctionnent comme vous le souhaitez, vous êtes proche des performances théoriques. Meilleure partie: le code est relativement petit et facile à comprendre.

 #ifndef HSM_HPP #define HSM_HPP // This code is from: // Yet Another Hierarchical State Machine // by Stefan Heinzmann // Overload issue 64 december 2004 // http://accu.org/index.php/journals/252 /* This is a basic implementation of UML Statecharts. * The key observation is that the machine can only * be in a leaf state at any given time. The composite * states are only traversed, never final. * Only the leaf states are ever instantiated. The composite * states are only mechanisms used to generate code. They are * never instantiated. */ // Helpers // A gadget from Herb Sutter's GotW #71 -- depends on SFINAE template class IsDerivedFrom { class Yes { char a[1]; }; class No { char a[10]; }; static Yes Test(B*); // undefined static No Test(...); // undefined public: enum { Res = sizeof(Test(static_cast(0))) == sizeof(Yes) ? 1 : 0 }; }; template class Bool {}; // Top State, Composite State and Leaf State template  struct TopState { typedef H Host; typedef void Base; virtual void handler(Host&) const = 0; virtual unsigned getId() const = 0; }; template  struct CompState; template  > > struct CompState : B { typedef B Base; typedef CompState This; template  void handle(H& h, const X& x) const { Base::handle(h, x); } static void init(H&); // no implementation static void entry(H&) {} static void exit(H&) {} }; template  struct CompState > : TopState { typedef TopState Base; typedef CompState This; template  void handle(H&, const X&) const {} static void init(H&); // no implementation static void entry(H&) {} static void exit(H&) {} }; template  > > struct LeafState : B { typedef H Host; typedef B Base; typedef LeafState This; template  void handle(H& h, const X& x) const { Base::handle(h, x); } virtual void handler(H& h) const { handle(h, *this); } virtual unsigned getId() const { return id; } static void init(H& h) { h.next(obj); } // don't specialize this static void entry(H&) {} static void exit(H&) {} static const LeafState obj; // only the leaf states have instances }; template  const LeafState LeafState::obj; // Transition Object template  // Current, Source, Target struct Tran { typedef typename C::Host Host; typedef typename C::Base CurrentBase; typedef typename S::Base SourceBase; typedef typename T::Base TargetBase; enum { // work out when to terminate template recursion eTB_CB = IsDerivedFrom::Res, eS_CB = IsDerivedFrom::Res, eS_C = IsDerivedFrom::Res, eC_S = IsDerivedFrom::Res, exitStop = eTB_CB && eS_C, entryStop = eS_C || eS_CB && !eC_S }; // We use overloading to stop recursion. // The more natural template specialization // method would require to specialize the inner // template without specializing the outer one, // which is forbidden. static void exitActions(Host&, Bool) {} static void exitActions(Host&h, Bool) { C::exit(h); Tran::exitActions(h, Bool()); } static void entryActions(Host&, Bool) {} static void entryActions(Host& h, Bool) { Tran::entryActions(h, Bool()); C::entry(h); } Tran(Host & h) : host_(h) { exitActions(host_, Bool()); } ~Tran() { Tran::entryActions(host_, Bool()); T::init(host_); } Host& host_; }; // Initializer for Compound States template  struct Init { typedef typename T::Host Host; Init(Host& h) : host_(h) {} ~Init() { T::entry(host_); T::init(host_); } Host& host_; }; #endif // HSM_HPP 

Le code de test suit.

 #include  #include "hsm.hpp" #include "hsmtest.hpp" /* Implements the following state machine from Miro Samek's * Practical Statecharts in C/C++ * * |-init-----------------------------------------------------| * | s0 | * |----------------------------------------------------------| * | | * | |-init-----------| |-------------------------| | * | | s1 |---c--->| s2 | | * | |----------------|<--c----|-------------------------| | * | | | | | | * |<-d-| |-init-------| | | |-init----------------| | | * | | | s11 |<----f----| | s21 | | | * | /--| |------------| | | |---------------------| | | * | a | | | | | | | | | * | \->| | |------g--------->|-init------| | | | * | | |____________| | | |-b->| s211 |---g--->| * | |----b---^ |------f------->| | | | | * | |________________| | |<-d-|___________|<--e----| * | | |_____________________| | | * | |_________________________| | * |__________________________________________________________| */ class TestHSM; typedef CompState Top; typedef CompState S0; typedef CompState S1; typedef LeafState S11; typedef CompState S2; typedef CompState S21; typedef LeafState S211; enum Signal { A_SIG, B_SIG, C_SIG, D_SIG, E_SIG, F_SIG, G_SIG, H_SIG }; class TestHSM { public: TestHSM() { Top::init(*this); } ~TestHSM() {} void next(const TopState& state) { state_ = &state; } Signal getSig() const { return sig_; } void dispatch(Signal sig) { sig_ = sig; state_->handler(*this); } void foo(int i) { foo_ = i; } int foo() const { return foo_; } private: const TopState* state_; Signal sig_; int foo_; }; bool testDispatch(char c) { static TestHSM test; if (c<'a' || 'h' template inline void State::handle(TestHSM& h, const X& x) const HSMHANDLER(S0) { switch (h.getSig()) { case E_SIG: { Tran t(h); printf("s0-E;"); return; } default: break; } return Base::handle(h, x); } HSMHANDLER(S1) { switch (h.getSig()) { case A_SIG: { Tran t(h); printf("s1-A;"); return; } case B_SIG: { Tran t(h); printf("s1-B;"); return; } case C_SIG: { Tran t(h); printf("s1-C;"); return; } case D_SIG: { Tran t(h); printf("s1-D;"); return; } case F_SIG: { Tran t(h); printf("s1-F;"); return; } default: break; } return Base::handle(h, x); } HSMHANDLER(S11) { switch (h.getSig()) { case G_SIG: { Tran t(h); printf("s11-G;"); return; } case H_SIG: if (h.foo()) { printf("s11-H"); h.foo(0); return; } break; default: break; } return Base::handle(h, x); } HSMHANDLER(S2) { switch (h.getSig()) { case C_SIG: { Tran t(h); printf("s2-C"); return; } case F_SIG: { Tran t(h); printf("s2-F"); return; } default: break; } return Base::handle(h, x); } HSMHANDLER(S21) { switch (h.getSig()) { case B_SIG: { Tran t(h); printf("s21-B;"); return; } case H_SIG: if (!h.foo()) { Tran t(h); printf("s21-H;"); h.foo(1); return; } break; default: break; } return Base::handle(h, x); } HSMHANDLER(S211) { switch (h.getSig()) { case D_SIG: { Tran t(h); printf("s211-D;"); return; } case G_SIG: { Tran t(h); printf("s211-G;"); return; } } return Base::handle(h, x); } #define HSMENTRY(State) \ template<> inline void State::entry(TestHSM&) { \ printf(#State "-ENTRY;"); \ } HSMENTRY(S0) HSMENTRY(S1) HSMENTRY(S11) HSMENTRY(S2) HSMENTRY(S21) HSMENTRY(S211) #define HSMEXIT(State) \ template<> inline void State::exit(TestHSM&) { \ printf(#State "-EXIT;"); \ } HSMEXIT(S0) HSMEXIT(S1) HSMEXIT(S11) HSMEXIT(S2) HSMEXIT(S21) HSMEXIT(S211) #define HSMINIT(State, InitState) \ template<> inline void State::init(TestHSM& h) { \ Init i(h); \ printf(#State "-INIT;"); \ } HSMINIT(Top, S0) HSMINIT(S0, S1) HSMINIT(S1, S11) HSMINIT(S2, S21) HSMINIT(S21, S211) 

La technique que j’aime pour les machines à états (du moins pour le contrôle des programmes) consiste à utiliser des pointeurs de fonctions. Chaque état est représenté par une fonction différente. La fonction prend un symbole d’entrée et retourne le pointeur de fonction pour l’état suivant. Les parsings de la boucle de répartition centrale prennent l’entrée suivante, la transfère à l’état actuel et traite le résultat.

Le fait de taper sur celui-ci devient un peu étrange, puisque C n’a aucun moyen d’indiquer les types de pointeurs de fonction qui se retournent, de sorte que les fonctions d’état renvoient un void* . Mais vous pouvez faire quelque chose comme ceci:

 typedef void* (*state_handler)(input_symbol_t); void dispatch_fsm() { state_handler current = initial_handler; /* Let's assume returning null indicates end-of-machine */ while (current) { current = current(get_input); } } 

Ensuite, vos fonctions d’état individuelles peuvent activer leur entrée pour traiter et renvoyer la valeur appropriée.

Cas le plus simple

 enum event_type { ET_THIS, ET_THAT }; union event_parm { uint8_t this; uint16_t that; } static void handle_event(enum event_type event, union event_parm parm) { static enum { THIS, THAT } state; switch (state) { case THIS: switch (event) { case ET_THIS: // Handle event. break; default: // Unhandled events in this state. break; } break; case THAT: // Handle state. break; } } 

Points: State est privé, non seulement à l’unité de compilation mais également à event_handler. Les cas particuliers peuvent être traités séparément du commutateur principal en utilisant la construction jugée nécessaire.

Cas plus complexe

Lorsque le commutateur devient plus grand qu’un couple d’écrans pleins, divisez-le en fonctions qui gèrent chaque état, en utilisant une table d’état pour rechercher directement la fonction. L’état est toujours privé pour le gestionnaire d’événements. Les fonctions du gestionnaire d’état renvoient l’état suivant. Si nécessaire, certains événements peuvent toujours recevoir un traitement spécial dans le gestionnaire d’événements principal. J’aime lancer des pseudo-événements pour l’entrée et la sortie d’état, et peut-être pour démarrer une machine à états:

 enum state_type { THIS, THAT, FOO, NA }; enum event_type { ET_START, ET_ENTER, ET_EXIT, ET_THIS, ET_THAT, ET_WHATEVER, ET_TIMEOUT }; union event_parm { uint8_t this; uint16_t that; }; static void handle_event(enum event_type event, union event_parm parm) { static enum state_type state; static void (* const state_handler[])(enum event_type event, union event_parm parm) = { handle_this, handle_that }; enum state_type next_state = state_handler[state](event, parm); if (NA != next_state && state != next_state) { (void)state_handler[state](ET_EXIT, 0); state = next_state; (void)state_handler[state](ET_ENTER, 0); } } 

Je ne suis pas sûr d’avoir défini la syntaxe, en particulier en ce qui concerne le tableau des pointeurs de fonctions. Je n’ai pas exécuté cela via un compilateur. Après examen, j’ai remarqué que j’avais oublié de supprimer explicitement l’état suivant lors de la gestion des pseudo-événements (la parenthèse (vide) avant l’appel à state_handler ()). C’est quelque chose que j’aime faire même si les compilateurs acceptent l’omission en silence. Il indique aux lecteurs du code que “oui, j’ai effectivement voulu appeler la fonction sans utiliser la valeur de retour”, et cela pourrait empêcher les outils d’parsing statique d’en avertir. Cela peut être idiosyncratique parce que je ne me souviens pas d’avoir vu quelqu’un d’autre le faire.

Points: l’ajout d’un tout petit peu de complexité (en vérifiant si l’état suivant est différent du courant) peut éviter le code dupliqué ailleurs, car les fonctions du gestionnaire d’état peuvent profiter des pseudo-événements qui surviennent lorsqu’un état est entré et laissé. Rappelez-vous que cet état ne peut pas changer lors du traitement des pseudo-événements, car le résultat du gestionnaire d’état est ignoré après ces événements. Vous pouvez bien entendu choisir de modifier le comportement.

Un gestionnaire d’état devrait ressembler à ceci:

 static enum state_type handle_this(enum event_type event, union event_parm parm) { enum state_type next_state = NA; switch (event) { case ET_ENTER: // Start a timer to do whatever. // Do other stuff necessary when entering this state. break; case ET_WHATEVER: // Switch state. next_state = THAT; break; case ET_TIMEOUT: // Switch state. next_state = FOO; break; case ET_EXIT: // Stop the timer. // Generally clean up this state. break; } return next_state; } 

Plus de complexité

Lorsque l’unité de compilation devient trop grande (peu importe ce que vous ressentez, je devrais dire environ 1000 lignes), placez chaque gestionnaire d’état dans un fichier séparé. Lorsque chaque gestionnaire d’état devient plus long que deux écrans, séparez chaque événement dans une fonction distincte, de la même manière que le commutateur d’état a été divisé. Vous pouvez le faire de plusieurs manières, indépendamment de l’état ou en utilisant une table commune, ou en combinant différents schémas. Certains d’entre eux ont été couverts ici par d’autres. Triez vos tables et utilisez la recherche binary si la vitesse est une exigence.

Programmation générique

Je voudrais que le préprocesseur traite des problèmes tels que le sorting des tables ou même la génération de machines d’état à partir de descriptions, ce qui vous permet “d’écrire des programmes sur les programmes”. Je crois que c’est ce que les gens de Boost exploitent pour les modèles C ++, mais je trouve la syntaxe cryptique.

Tables bidimensionnelles

J’ai utilisé des tables d’état / d’événement dans le passé mais je dois dire que pour les cas les plus simples, je ne les trouve pas nécessaires et je préfère la clarté et la lisibilité de l’instruction même si elle dépasse un écran entier. Pour les cas plus complexes, les tableaux deviennent rapidement incontrôlables, comme d’autres l’ont noté. Les idiomes que je vous présente ici vous permettent d’append un grand nombre d’événements et d’états lorsque vous en avez envie, sans avoir à gérer un tableau consommant de la mémoire (même si c’est la mémoire du programme).

Avertissement

Des besoins spéciaux peuvent rendre ces expressions moins utiles, mais je les ai trouvées très claires et maintenables.

Extrêmement non testé, mais amusant à coder, maintenant dans une version plus raffinée que ma réponse originale; des versions à jour peuvent être trouvées sur mercurial.intuxication.org :

sm.h

 #ifndef SM_ARGS #error "SM_ARGS undefined: " \ "use '#define SM_ARGS (void)' to get an empty argument list" #endif #ifndef SM_STATES #error "SM_STATES undefined: " \ "you must provide a list of comma-separated states" #endif typedef void (*sm_state) SM_ARGS; static const sm_state SM_STATES; #define sm_transit(STATE) ((sm_state (*) SM_ARGS)STATE) #define sm_def(NAME) \ static sm_state NAME ## _fn SM_ARGS; \ static const sm_state NAME = (sm_state)NAME ## _fn; \ static sm_state NAME ## _fn SM_ARGS 

exemple.c

 #include  #define SM_ARGS (int i) #define SM_STATES EVEN, ODD #include "sm.h" sm_def(EVEN) { printf("even %i\n", i); return ODD; } sm_def(ODD) { printf("odd %i\n", i); return EVEN; } int main(void) { int i = 0; sm_state state = EVEN; for(; i < 10; ++i) state = sm_transit(state)(i); return 0; } 

I really liked paxdiable’s answer and decided to implement all the missing features for my application like guard variables and state machine specific data.

I uploaded my implementation to this site to share with the community. It has been tested using IAR Embedded Workbench for ARM.

https://sourceforge.net/projects/compactfsm/

Another interesting open source tool is Yakindu Statechart Tools on statecharts.org . It makes use of Harel statecharts and thus provides hierarchical and parallel states and generates C and C++ (as well as Java) code. It does not make use of libraries but follows a ‘plain code’ approach. The code basically applies switch-case structures. The code generators can also be customized. Additionally the tool provides many other features.

Coming to this late (as usual) but scanning the answers to date I thinks something important is missing;

I have found in my own projects that it can be very helpful to not have a function for every valid state/event combination. I do like the idea of effectively having a 2D table of states/events. But I like the table elements to be more than a simple function pointer. Instead I try to organize my design so at it’s heart it comsockets a bunch of simple atomic elements or actions. That way I can list those simple atomic elements at each intersection of my state/event table. The idea is that you don’t have to define a mass of N squared (typically very simple) functions. Why have something so error-prone, time consuming, hard to write, hard to read, you name it ?

I also include an optional new state, and an optional function pointer for each cell in the table. The function pointer is there for those exceptional cases where you don’t want to just fire off a list of atomic actions.

You know you are doing it right when you can express a lot of different functionality, just by editing your table, with no new code to write.

Alrght, I think mine’s just a little different from everybody else’s. A little more separation of code and data than I see in the other answers. I really read up on the theory to write this, which implements a full Regular-language (without regular expressions, sadly). Ullman, Minsky, Chomsky. Can’t say I understood it all, but I’ve drawn from the old masters as directly as possible: through their words.

I use a function pointer to a predicate that determines the transition to a ‘yes’ state or a ‘no’ state. This facilitates the creation of a finite state acceptor for a regular language that you program in a more assembly-language-like manner. Please don’t be put-off by my silly name choices. ‘czek’ == ‘check’. ‘grok’ == [go look it up in the Hacker Dictionary].

So for each iteration, czek calls a predicate function with the current character as argument. If the predicate returns true, the character is consumed (the pointer advanced) and we follow the ‘y’ transition to select the next state. If the predicate returns false, the character is NOT consumed and we follow the ‘n’ transition. So every instruction is a two-way branch! I must have been reading The Story of Mel at the time.

This code comes straight from my postscript interpreter , and evolved into its current form with much guidance from the fellows on comp.lang.c. Since postscript basically has no syntax (only requiring balanced brackets), a Regular Language Accepter like this functions as the parser as well.

 /* currentstr is set to the start of ssortingng by czek and used by setrad (called by israd) to set currentrad which is used by israddig to determine if the character in question is valid for the specified radix -- a little semantic checking in the syntax! */ char *currentstr; int currentrad; void setrad(void) { char *end; currentrad = strtol(currentstr, &end, 10); if (*end != '#' /* just a sanity check, the automaton should already have determined this */ || currentrad > 36 || currentrad < 2) fatal("bad radix"); /* should probably be a simple syntaxerror */ } /* character classes used as tests by automatons under control of czek */ char *alpha = "0123456789" "ABCDE" "FGHIJ" "KLMNO" "PQRST" "UVWXYZ"; #define EQ(a,b) a==b #define WITHIN(a,b) strchr(a,b)!=NULL int israd (int c) { if (EQ('#',c)) { setrad(); return true; } return false; } int israddig(int c) { return strchrnul(alpha,toupper(c))-alpha <= currentrad; } int isdot (int c) {return EQ('.',c);} int ise (int c) {return WITHIN("eE",c);} int issign (int c) {return WITHIN("+-",c);} int isdel (int c) {return WITHIN("()<>[]{}/%",c);} int isreg (int c) {return c!=EOF && !isspace(c) && !isdel(c);} #undef WITHIN #undef EQ /* the automaton type */ typedef struct { int (*pred)(int); int y, n; } test; /* automaton to match a simple decimal number */ /* /^[+-]?[0-9]+$/ */ test fsm_dec[] = { /* 0*/ { issign, 1, 1 }, /* 1*/ { isdigit, 2, -1 }, /* 2*/ { isdigit, 2, -1 }, }; int acc_dec(int i) { return i==2; } /* automaton to match a radix number */ /* /^[0-9]+[#][a-Z0-9]+$/ */ test fsm_rad[] = { /* 0*/ { isdigit, 1, -1 }, /* 1*/ { isdigit, 1, 2 }, /* 2*/ { israd, 3, -1 }, /* 3*/ { israddig, 4, -1 }, /* 4*/ { israddig, 4, -1 }, }; int acc_rad(int i) { return i==4; } /* automaton to match a real number */ /* /^[+-]?(d+(.d*)?)|(d*.d+)([eE][+-]?d+)?$/ */ /* represents the merge of these (simpler) expressions [+-]?[0-9]+\.[0-9]*([eE][+-]?[0-9]+)? [+-]?[0-9]*\.[0-9]+([eE][+-]?[0-9]+)? The complexity comes from ensuring at least one digit in the integer or the fraction with optional sign and optional optionally-signed exponent. So passing isdot in state 3 means at least one integer digit has been found but passing isdot in state 4 means we must find at least one fraction digit via state 5 or the whole thing is a bust. */ test fsm_real[] = { /* 0*/ { issign, 1, 1 }, /* 1*/ { isdigit, 2, 4 }, /* 2*/ { isdigit, 2, 3 }, /* 3*/ { isdot, 6, 7 }, /* 4*/ { isdot, 5, -1 }, /* 5*/ { isdigit, 6, -1 }, /* 6*/ { isdigit, 6, 7 }, /* 7*/ { ise, 8, -1 }, /* 8*/ { issign, 9, 9 }, /* 9*/ { isdigit, 10, -1 }, /*10*/ { isdigit, 10, -1 }, }; int acc_real(int i) { switch(i) { case 2: /* integer */ case 6: /* real */ case 10: /* real with exponent */ return true; } return false; } /* Helper function for grok. Execute automaton against the buffer, applying test to each character: on success, consume character and follow 'y' transition. on failure, do not consume but follow 'n' transition. Call yes function to determine if the ending state is considered an acceptable final state. A transition to -1 represents rejection by the automaton */ int czek (char *s, test *fsm, int (*yes)(int)) { int sta = 0; currentstr = s; while (sta!=-1 && *s) { if (fsm[sta].pred((int)*s)) { sta=fsm[sta].y; s++; } else { sta=fsm[sta].n; } } return yes(sta); } /* Helper function for toke. Interpret the contents of the buffer, trying automatons to match number formats; and falling through to a switch for special characters. Any token consisting of all regular characters that cannot be interpreted as a number is an executable name */ object grok (state *st, char *s, int ns, object *src, int (*next)(state *,object *), void (*back)(state *,int, object *)) { if (czek(s, fsm_dec, acc_dec)) { long num; num = strtol(s,NULL,10); if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) { error(st,limitcheck); /* } else if (num > INT_MAX || num < INT_MIN) { */ /* error(limitcheck, OP_token); */ } else { return consint(num); } } else if (czek(s, fsm_rad, acc_rad)) { long ra,num; ra = (int)strtol(s,NULL,10); if (ra > 36 || ra < 2) { error(st,limitcheck); } num = strtol(strchr(s,'#')+1, NULL, (int)ra); if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) { error(st,limitcheck); /* } else if (num > INT_MAX || num < INT_MAX) { */ /* error(limitcheck, OP_token); */ } else { return consint(num); } } else if (czek(s, fsm_real, acc_real)) { double num; num = strtod(s,NULL); if ((num==HUGE_VAL || num==-HUGE_VAL) && errno==ERANGE) { error(st,limitcheck); } else { return consreal(num); } } else switch(*s) { case '(': { int c, defer=1; char *sp = s; while (defer && (c=next(st,src)) != EOF ) { switch(c) { case '(': defer++; break; case ')': defer--; if (!defer) goto endstring; break; case '\\': c=next(st,src); switch(c) { case '\n': continue; case 'a': c = '\a'; break; case 'b': c = '\b'; break; case 'f': c = '\f'; break; case 'n': c = '\n'; break; case 'r': c = '\r'; break; case 't': c = '\t'; break; case 'v': c = '\v'; break; case '\'': case '\"': case '(': case ')': default: break; } } if (sp-s>ns) error(st,limitcheck); else *sp++ = c; } endssortingng: *sp=0; return cvlit(consssortingng(st,s,sp-s)); } case '<': { int c; char d, *x = "0123456789abcdef", *sp = s; while (c=next(st,src), c!='>' && c!=EOF) { if (isspace(c)) continue; if (isxdigit(c)) c = strchr(x,tolower(c)) - x; else error(st,syntaxerror); d = (char)c << 4; while (isspace(c=next(st,src))) /*loop*/; if (isxdigit(c)) c = strchr(x,tolower(c)) - x; else error(st,syntaxerror); d |= (char)c; if (sp-s>ns) error(st,limitcheck); *sp++ = d; } *sp = 0; return cvlit(consssortingng(st,s,sp-s)); } case '{': { object *a; size_t na = 100; size_t i; object proc; object fin; fin = consname(st,"}"); (a = malloc(na * sizeof(object))) || (fatal("failure to malloc"),0); for (i=0 ; objcmp(st,a[i]=toke(st,src,next,back),fin) != 0; i++) { if (i == na-1) (a = realloc(a, (na+=100) * sizeof(object))) || (fatal("failure to malloc"),0); } proc = consarray(st,i); { size_t j; for (j=0; j= nbuf-1) return false; *s++ = c; } *s = 0; if (!isspace(c) && c != EOF) back(st,c,src); /* eat interstice */ return true; } /* Helper function for Stoken Ftoken. Read a token from src using next and back. Loop until having read a bona-fide non-whitespace non-comment character. Call puff to read into buffer up to next delimiter or space. Call grok to figure out what it is. */ #define NBUF MAXLINE object toke (state *st, object *src, int (*next)(state *, object *), void (*back)(state *, int, object *)) { char buf[NBUF] = "", *s=buf; int c,sta = 1; object o; do { c=next(st,src); //if (c==EOF) return null; if (c=='%') { if (DUMPCOMMENTS) fputc(c, stdout); do { c=next(st,src); if (DUMPCOMMENTS) fputc(c, stdout); } while (c!='\n' && c!='\f' && c!=EOF); } } while (c!=EOF && isspace(c)); if (c==EOF) return null; *s++ = c; *s = 0; if (!isdel(c)) sta=puff(st, s,NBUF-1,src,next,back); if (sta) { o=grok(st,buf,NBUF-1,src,next,back); return o; } else { return null; } } 

boost.org comes with 2 different state chart implementations:

  • Meta State Machine
  • Statechart

As always, boost will beam you into template hell.

The first library is for more performance-critical state machines. The second library gives you a direct transition path from a UML Statechart to code.

Here’s the SO question asking for a comparison between the two where both of the authors respond.

This series of Ars OpenForum posts about a somewhat complicated bit of control logic includes a very easy-to-follow implementation as a state machine in C.

Saw this somewhere

 #define FSM #define STATE(x) s_##x : #define NEXTSTATE(x) goto s_##x FSM { STATE(x) { ... NEXTSTATE(y); } STATE(y) { ... if (x == 0) NEXTSTATE(y); else NEXTSTATE(x); } } 

Given that you imply you can use C++ and hence OO code, I would suggest evaluating the ‘GoF’state pattern (GoF = Gang of Four, the guys who wrote the design patterns book which brought design patterns into the limelight).

It is not particularly complex and it is widely used and discussed so it is easy to see examples and explanations on line.

It will also quite likely be recognizable by anyone else maintaining your code at a later date.

If efficiency is the worry, it would be worth actually benchmarking to make sure that a non OO approach is more efficient as lots of factors affect performance and it is not always simply OO bad, functional code good. Similarly, if memory usage is a constraint for you it is again worth doing some tests or calculations to see if this will actually be an issue for your particular application if you use the state pattern.

The following are some links to the ‘Gof’ state pattern, as Craig suggests:

Your question is quite generic,
Here are two reference articles that might be useful,

  1. Embedded State Machine Implementation

    This article describes a simple approach to implementing a state machine for an embedded system. For purposes of this article, a state machine is defined as an algorithm that can be in one of a small number of states. A state is a condition that causes a prescribed relationship of inputs to outputs, and of inputs to next states.
    A savvy reader will quickly note that the state machines described in this article are Mealy machines. A Mealy machine is a state machine where the outputs are a function of both present state and input, as opposed to a Moore machine, in which the outputs are a function only of state.

    • Coding State Machines in C and C++

      My preoccupation in this article is with state-machine fundamentals and some straightforward programming guidelines for coding state machines in C or C++. I hope that these simple techniques can become more common, so that you (and others) can readily see the state-machine structure right from the source code.

I have used State Machine Comstackr in Java and Python projects to with success.

This is an old post with lots of answers, but I thought I’d add my own approach to the finite state machine in C. I made a Python script to produce the skeleton C code for any number of states. That script is documented on GituHub at FsmTemplateC

This example is based on other approaches I’ve read about. It doesn’t use goto or switch statements but instead has transition functions in a pointer masortingx (look-up table). The code relies on a big multi-line initializer macro and C99 features (designated initializers and compound literals) so if you don’t like these things, you might not like this approach.

Here is a Python script of a turnstile example which generates skeleton C-code using FsmTemplateC :

 # dict parameter for generating FSM fsm_param = { # main FSM struct type ssortingng 'type': 'FsmTurnstile', # struct type and name for passing data to state machine functions # by pointer (these custom names are optional) 'fopts': { 'type': 'FsmTurnstileFopts', 'name': 'fopts' }, # list of states 'states': ['locked', 'unlocked'], # list of inputs (can be any length > 0) 'inputs': ['coin', 'push'], # map inputs to commands (next desired state) using a transition table # index of array corresponds to 'inputs' array # for this example, index 0 is 'coin', index 1 is 'push' 'transitiontable': { # current state | 'coin' | 'push' | 'locked': ['unlocked', ''], 'unlocked': [ '', 'locked'] } } # folder to contain generated code folder = 'turnstile_example' # function prefix prefix = 'fsm_turnstile' # generate FSM code code = fsm.Fsm(fsm_param).genccode(folder, prefix) 

The generated output header contains the typedefs:

 /* function options (EDIT) */ typedef struct FsmTurnstileFopts { /* define your options struct here */ } FsmTurnstileFopts; /* transition check */ typedef enum eFsmTurnstileCheck { EFSM_TURNSTILE_TR_RETREAT, EFSM_TURNSTILE_TR_ADVANCE, EFSM_TURNSTILE_TR_CONTINUE, EFSM_TURNSTILE_TR_BADINPUT } eFsmTurnstileCheck; /* states (enum) */ typedef enum eFsmTurnstileState { EFSM_TURNSTILE_ST_LOCKED, EFSM_TURNSTILE_ST_UNLOCKED, EFSM_TURNSTILE_NUM_STATES } eFsmTurnstileState; /* inputs (enum) */ typedef enum eFsmTurnstileInput { EFSM_TURNSTILE_IN_COIN, EFSM_TURNSTILE_IN_PUSH, EFSM_TURNSTILE_NUM_INPUTS, EFSM_TURNSTILE_NOINPUT } eFsmTurnstileInput; /* finite state machine struct */ typedef struct FsmTurnstile { eFsmTurnstileInput input; eFsmTurnstileCheck check; eFsmTurnstileState cur; eFsmTurnstileState cmd; eFsmTurnstileState **transition_table; void (***state_transitions)(struct FsmTurnstile *, FsmTurnstileFopts *); void (*run)(struct FsmTurnstile *, FsmTurnstileFopts *, const eFsmTurnstileInput); } FsmTurnstile; /* transition functions */ typedef void (*pFsmTurnstileStateTransitions)(struct FsmTurnstile *, FsmTurnstileFopts *); 
  • enum eFsmTurnstileCheck is used to determine whether a transition was blocked with EFSM_TURNSTILE_TR_RETREAT , allowed to progress with EFSM_TURNSTILE_TR_ADVANCE , or the function call was not preceded by a transition with EFSM_TURNSTILE_TR_CONTINUE .
  • enum eFsmTurnstileState is simply the list of states.
  • enum eFsmTurnstileInput is simply the list of inputs.
  • The FsmTurnstile struct is the heart of the state machine with the transition check, function lookup table, current state, commanded state, and an alias to the primary function that runs the machine.
  • Every function pointer (alias) in FsmTurnstile should only be called from the struct and has to have its first input as a pointer to itself so as to maintain a persistent state, object-oriented style.

Now for the function declarations in the header:

 /* fsm declarations */ void fsm_turnstile_locked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts); void fsm_turnstile_locked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts); void fsm_turnstile_unlocked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts); void fsm_turnstile_unlocked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts); void fsm_turnstile_run (FsmTurnstile *fsm, FsmTurnstileFopts *fopts, const eFsmTurnstileInput input); 

Function names are in the format {prefix}_{from}_{to} , where {from} is the previous (current) state and {to} is the next state. Note that if the transition table does not allow for certain transitions, a NULL pointer instead of a function pointer will be set. Finally, the magic happens with a macro. Here we build the transition table (masortingx of state enums) and the state transition functions look up table (a masortingx of function pointers):

 /* creation macro */ #define FSM_TURNSTILE_CREATE() \ { \ .input = EFSM_TURNSTILE_NOINPUT, \ .check = EFSM_TURNSTILE_TR_CONTINUE, \ .cur = EFSM_TURNSTILE_ST_LOCKED, \ .cmd = EFSM_TURNSTILE_ST_LOCKED, \ .transition_table = (eFsmTurnstileState * [EFSM_TURNSTILE_NUM_STATES]) { \ (eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \ EFSM_TURNSTILE_ST_UNLOCKED, \ EFSM_TURNSTILE_ST_LOCKED \ }, \ (eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \ EFSM_TURNSTILE_ST_UNLOCKED, \ EFSM_TURNSTILE_ST_LOCKED \ } \ }, \ .state_transitions = (pFsmTurnstileStateTransitions * [EFSM_TURNSTILE_NUM_STATES]) { \ (pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \ fsm_turnstile_locked_locked, \ fsm_turnstile_locked_unlocked \ }, \ (pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \ fsm_turnstile_unlocked_locked, \ fsm_turnstile_unlocked_unlocked \ } \ }, \ .run = fsm_turnstile_run \ } 

When creating the FSM, the macro FSM_EXAMPLE_CREATE() has to be used.

Now, in the source code every state transition function declared above should be populated. The FsmTurnstileFopts struct can be used to pass data to/from the state machine. Every transition must set fsm->check to be equal to either EFSM_EXAMPLE_TR_RETREAT to block it from transitioning or EFSM_EXAMPLE_TR_ADVANCE to allow it to transition to the commanded state. A working example can be found at (FsmTemplateC)[ https://github.com/ChisholmKyle/FsmTemplateC%5D .

Here is the very simple actual usage in your code:

 /* create fsm */ FsmTurnstile fsm = FSM_TURNSTILE_CREATE(); /* create fopts */ FsmTurnstileFopts fopts = { .msg = "" }; /* initialize input */ eFsmTurnstileInput input = EFSM_TURNSTILE_NOINPUT; /* main loop */ for (;;) { /* wait for timer signal, inputs, interrupts, whatever */ /* optionally set the input (my_input = EFSM_TURNSTILE_IN_PUSH for example) */ /* run state machine */ my_fsm.run(&my_fsm, &my_fopts, my_input); } 

All that header business and all those functions just to have a simple and fast interface is worth it in my mind.

You could use the open source library OpenFST .

OpenFst is a library for constructing, combining, optimizing, and searching weighted finite-state transducers (FSTs). Weighted finite-state transducers are automata where each transition has an input label, an output label, and a weight. The more familiar finite-state acceptor is represented as a transducer with each transition’s input and output label equal. Finite-state acceptors are used to represent sets of ssortingngs (specifically, regular or rational sets); finite-state transducers are used to represent binary relations between pairs of ssortingngs (specifically, rational transductions). The weights can be used to represent the cost of taking a particular transition.

 void (* StateController)(void); void state1(void); void state2(void); void main() { StateController=&state1; while(1) { (* StateController)(); } } void state1(void) { //do something in state1 StateController=&state2; } void state2(void) { //do something in state2 //Keep changing function direction based on state transition StateController=&state1; } 

I personally use self referencing structs in combination with pointer arrays. I uploaded a tutorial on github a while back, link:

https://github.com/mmelchger/polling_state_machine_c

Note: I do realise that this thread is quite old, but I hope to get input and thoughts on the design of the state-machine as well as being able to provide an example for a possible state-machine design in C.