Wie FSM mit Events in Tabelle umsetzen (C)?

[Flederdil (Gast)]

Weder im Wiki-Artikel noch in den gefundenen Threads habe ich eine 
Lösung gesehen, die eine tabellarische FSM mit mehreren Events pro 
Zustand abbildet.

Zwei Ansätze fallen mir ein:

Eine Event-Array bzw. ein Pointer dorthin (was es unübersichtlicher 
macht, da separat definiert)

    STATEx, [EVENTy->[FUNCTION,NEWSTATE], ...]
    ...

Entsprechend viele Einträge und eine Suche (größere Tabelle, langsamer, 
aber schön übersichtlich):

    STATE1, EVENT_A, FUNCTION, NEWSTATE
    STATE1, EVENT_B, FUNCTION, NEWSTATE
    ...

Ist der Ansatz brauchbar, wie geht's "besser"?

[Stephan (Gast)]

Hallo

wie gefällt dir so ein Ansatz:

    CREATE_FSM_TABLE(
        CREATE_STATE( STATE_IDLE,
            ADD_EVENT( EV_TWI_READ_DATA , STATE_WRITE_ADR , twi_read_wrAdr ),
            ADD_EVENT( EV_TWI_WRITE_DATA, STATE_WRITE_LINK, twi_write_link ),
        ),
        CREATE_STATE( STATE_WRITE_ADR,
            ADD_EVENT( EV_TWI_ADR_READY, STATE_READ_DATA, twi_read_data      ),
            ADD_EVENT( EV_TWI_I2C_ERROR, STATE_READ_WAIT, twi_startWaitTimer ),
            ADD_EVENT( EV_TWI_MAX_ERROR, STATE_IDLE     , twi_job_finished   ),
            ADD_EVENT( EV_TWI_DMA_ERROR, STATE_IDLE     , twi_job_finished   ),
        ),
        CREATE_STATE( STATE_READ_DATA,
            ADD_EVENT( EV_TWI_READ_READY   , STATE_READ_DATA, twi_read_data    ),
            ADD_EVENT( EV_TWI_READ_COMPLETE, STATE_IDLE     , twi_job_finished ),
        ),
        CREATE_STATE( STATE_READ_WAIT,
            ADD_EVENT( EV_TWI_TIMEOUT_OK, STATE_WRITE_ADR, twi_read_wrAdr ),
        ),
        CREATE_STATE( STATE_WRITE_LINK,
            ADD_EVENT( EV_TWI_WRITE_READY_DMA, STATE_WRITE_WAIT, twi_startWaitTimer ),
            ADD_EVENT( EV_TWI_MAX_ERROR      , STATE_IDLE      , twi_job_finished   ),
            ADD_EVENT( EV_TWI_I2C_ERROR      , STATE_WRITE_WAIT, twi_startWaitTimer ),
            ADD_EVENT( EV_TWI_DMA_ERROR      , STATE_IDLE      , twi_job_finished   ),
            ADD_EVENT( EV_TWI_WRITE_COMPLETE , STATE_IDLE      , twi_job_finished   ),
        ),
        CREATE_STATE( STATE_WRITE_WAIT,
            ADD_EVENT( EV_TWI_TIMEOUT_OK, STATE_WRITE_LINK, twi_write_link ),
        ),
    ),

[Programmierer (Gast)]

Sehr sauber lässt sich so etwas mit dem State Pattern lösen. Ist OOP und 
damit besser in C++ umzusetzen, aber wo C läuft läuft fast immer auch 
C++, und es vermeidet so ein Schlachtfeld an Makros. Es ist sehr 
flexibel und bietet die Möglichkeit, pro Zustand Daten abzulegen die 
auch nur für diesen Zustand gültig sind, beliebige individuelle 
Übergangsfunktionen oder -Bedingungen und nebenher ist es auch noch 100% 
typsicher ohne Casts umsetzbar.

[Flederdil (Gast)]

Das sieht gut aus (entspricht vermutlich meiner ersten Variante), aber 
für mich ist es leider nicht offensichtlich, wie die Makros (und Daten) 
dahinter aussehen.

Als Ergänzung zu meiner ersten Idee könnte man natürlich auch einfach 
eine Tabelle entsprechend der maximalen Anzahl von Events anlegen, und 
die "Platzverschwendung" in Kauf nehmen.

[Flederdil (Gast)]

https://de.wikipedia.org/wiki/Zustand_(Entwurfsmuster) sehe ich mir an, 
möchte mich aber auf C beschränken.

[Stephan (Gast)]

Flederdil schrieb:
> Als Ergänzung zu meiner ersten Idee könnte man natürlich auch einfach
> eine Tabelle entsprechend der maximalen Anzahl von Events anlegen, und
> die "Platzverschwendung" in Kauf nehmen.
das würde ich nicht tun, da du wirklich zu viel Platz verschenkst

[Flederdil (Gast)]

Stephan schrieb:
> das würde ich nicht tun, da du wirklich zu viel Platz verschenkst

Ich auch nicht - verrate doch bitte, wie die Makros funktionieren ;-)

[Stephan (Gast)]

Flederdil schrieb:
> Das sieht gut aus (entspricht vermutlich meiner ersten Variante), aber
> für mich ist es leider nicht offensichtlich, wie die Makros (und Daten)
> dahinter aussehen.

ich habe mir 3 Strukturen dafür aufgebaut.

// der Container für die Events
struct eventTransTab_s{
    void (*transFunc)( event_t* const e );         /* transition function */
    const uint16_t eventId;
    const uint16_t nextState;
};

// der Container für die States
struct fsm_state_data_s
{
    /* pointer auf ein Array */
    const struct    eventTransTab_s ( * const eventTable)[];
    const uint16_t  eventTableSize;
    const uint16_t  state;
};

// und die FSM
struct fsm
{
   const struct fsm_state_data_s ( * const stateTable )[];
   const size_t stateTableSize;
   uint16_t currState;
};

nun musst du nur die Strukturen mit Daten füllen.

#define ADD_EVENT( evNr, nextStNr, cbFunc )     \
    { .eventId= (event_id_t)evNr, .nextState = (uint16_t)nextStNr, .transFunc = cbFunc }

#define CREATE_STATE( stateNr, ...)                                    \
{ .state= stateNr, .eventTable= &(struct eventTransTab_s []){ ##__VA_ARGS__ },  \
  .eventTableSize = sizeof((struct eventTransTab_s []){ ##__VA_ARGS__ }) / sizeof( struct eventTransTab_s )}

#define CREATE_FSM_TABLE( ... )      .stateTableSize= sizeof((struct fsm_state_data_s []){ ##__VA_ARGS__ }) / sizeof( struct fsm_state_data_s ),\
                                .stateTable    = &(struct fsm_state_data_s []) { ##__VA_ARGS__ }

[Flederdil (Gast)]

Vielen Dank, ich seh's mir an!

[Stephan (Gast)]

und hier der Event-Handler:

// Return: False = Error
//         True  = alles Okay
bool_t fsm_state_handler( struct fsm* const fsm, event_t* const e)
{
    const event_id_t id = e->Id;
    const uint16_t   currState = fsm->currState;

    /*  Iterate through the state transition matrix, checking if there is both a match with the current state
        and the event
    */
    for( size_t i = (size_t)0; i < fsm->stateTableSize; i++ )
    {
        const struct fsm_state_data_s* tabState= &(*fsm->stateTable)[ i ];

        if ( tabState->state == currState )
        {
            /* hier die abgehenden Transitions prüfen */
            for( size_t x = (size_t)0; x < tabState->eventTableSize; x++ )
            {
                const struct eventTransTab_s* eventTransition = &(*tabState->eventTable)[ x ];
                if ( eventTransition->eventId == id )
                {
                    // Transition to the next state
                    fsm->currState = eventTransition->nextState;

                    // Call the function associated with transition
                    if ( eventTransition->transFunc != NULL_PTR )
                    {
                        eventTransition->transFunc( e );
                    }

                    return True;
                }
            }

            /* wir haben zwar den State gefunden aber kein passendes Event! */
            break;
        }
    }

    return False;
}

so das war es. Ich hoffe ich habe nichts Kaput gemacht oder vergessen zu 
kopieren. :-)

Es ist ein Ansatz, ob er dir gefällt und du diese Art der Programmierung 
mit den Macros mags, musst du entscheiden.

PS: Du kannst auch diese FSM-Macros umschreiben und mit Hilfe von 
Plantuml ein Diagramm zeichnen lassen. Es sieht nicht schön aus, bei 
mir, aber es hilft beim Programmieren.

[Programmierer (Gast)]

Stephan schrieb:
> size_t i = (size_t)0

Der Cast nach size_t beim Initialisieren ist unnötig.

[Programmierer (Gast)]

Stephan schrieb:
> if ( eventTransition->transFunc != NULL_PTR

Und warum nicht einfach NULL? Es gibt keine sinnvolle Situation in C in 
welcher man den Null-Pointer anders definieren würde als NULL, solche 
Konstrukte machen es nur schlechter lesbar & wartbar.

[EAF (Gast)]

Programmierer schrieb:
> Und warum nicht einfach NULL?
Warum überhaupt irgendeine Null zum Vergleich?

if ( eventTransition->transFunc )
sollte doch reichen.

[Flederdil (Gast)]

Stephan schrieb:
> Ich hoffe ich habe nichts Kaput gemacht oder vergessen zu
> kopieren. :-)

Es fehlen noch ein paar Typen.. Habe versucht, zu raten, aber das 
funktioniert noch nicht:

#include <stdint.h>

typedef enum {STATE_ZERO, STATE_ONE} state;
typedef enum {EV_ZERO, EV_ONE, EV_TWO} event_id_t;
typedef void* event_t;
typedef uint8_t size_t;

// der Container für die Events
struct eventTransTab_s{
    void (*transFunc)( event_t* const e );         /* transition function */
    const uint16_t eventId;
    const uint16_t nextState;
};

// der Container für die States
struct fsm_state_data_s
{
    /* pointer auf ein Array */
    const struct    eventTransTab_s ( * const eventTable)[];
    const uint16_t  eventTableSize;
    const uint16_t  state;
};

// und die FSM
struct fsm
{
   const struct fsm_state_data_s ( * const stateTable )[];
   const size_t stateTableSize;
   uint16_t currState;
};



#define ADD_EVENT( evNr, nextStNr, cbFunc )     \
    { .eventId= (event_id_t)evNr, .nextState = (uint16_t)nextStNr, .transFunc = cbFunc }

#define CREATE_STATE( stateNr, ...)                                    \
{ .state= stateNr, .eventTable= &(struct eventTransTab_s []){ ##__VA_ARGS__ },  \
  .eventTableSize = sizeof((struct eventTransTab_s []){ ##__VA_ARGS__ }) / sizeof( struct eventTransTab_s )}

#define CREATE_FSM_TABLE( ... )      .stateTableSize= sizeof((struct fsm_state_data_s []){ ##__VA_ARGS__ }) / sizeof( struct fsm_state_data_s ),\
                                .stateTable    = &(struct fsm_state_data_s []) { ##__VA_ARGS__ }

struct fsm test { 
CREATE_FSM_TABLE(
    CREATE_STATE( STATE_ZERO,
        ADD_EVENT( EV_ZERO , STATE_ONE, NULL ),
        ADD_EVENT( EV_ONE, STATE_ONE, NULL ),
    ),

    CREATE_STATE( STATE_ONE,
        ADD_EVENT( EV_TWO, STATE_ZERO, NULL),
    ),
),
.currState = STATE_ZERO;
};

Sollte ".eventId" nicht eigentlich auch event_id_t sein?

[Stephan (Gast)]

Flederdil schrieb:
> Stephan schrieb:
>> Ich hoffe ich habe nichts Kaput gemacht oder vergessen zu
>> kopieren. :-)
>
> Es fehlen noch ein paar Typen.. Habe versucht, zu raten, aber das
> funktioniert noch nicht:
>

#include <stdint.h>
 
typedef enum {STATE_ZERO, STATE_ONE} state;
typedef enum {EV_ZERO, EV_ONE, EV_TWO} event_id_t;
typedef void* event_t;
typedef uint8_t size_t;

> Sollte ".eventId" nicht eigentlich auch event_id_t sein?
Ja ist richtig. Das war mal ein Enum.

[Stephan (Gast)]

Programmierer schrieb:
> Stephan schrieb:
>> size_t i = (size_t)0
>
> Der Cast nach size_t beim Initialisieren ist unnötig.
Ich bekomme hier eine Warnung "Implizierter CAST". daher der cast von 
meiner Seite. Ich glaube, ich hätte auch "0UL" schreiben können.

Programmierer schrieb:
> Stephan schrieb:
>> if ( eventTransition->transFunc != NULL_PTR
>
> Und warum nicht einfach NULL? Es gibt keine sinnvolle Situation in C in
> welcher man den Null-Pointer anders definieren würde als NULL, solche
> Konstrukte machen es nur schlechter lesbar & wartbar.
Bei meinem Compiler ist NULL wirklich eine dezimale 0!
Daher würde das eine Warnung vom Compiler generieren!

#define NULL_PTR                ((void*)0)

Dies wird akzeptiert!

EAF schrieb:
> Programmierer schrieb:
>> Und warum nicht einfach NULL?
> Warum überhaupt irgendeine Null zum Vergleich?
>
> if ( eventTransition->transFunc )
> sollte doch reichen.
Die ist kein Boolesche Ausdruck und es gibt eine Warnung!

Mein Compiler hat ein paar MISRA Regeln mit eingebaut und prüft diese 
auch.
Die "##" musste ich bei meinen Compiler auch erstmal freigeben, sind 
auch nicht erlaubt!

[Programmierer (Gast)]

Stephan schrieb:
> Ich bekomme hier eine Warnung "Implizierter CAST".

Meines Wissens ist das eine Initialisierung und kein Cast, daher völlig 
legal. Das geht mit allen Integer-Typen.

Stephan schrieb:
> Bei meinem Compiler ist NULL wirklich eine dezimale 0!

Das ist auch legitim.

> Daher würde das eine Warnung vom Compiler generieren!

Nö, 0 ist implizit in jeden Pointer-Typ konvertierbar, daher kann man 
alle Pointer-Typen mit 0 vergleichen oder zuweisen. In aktuellen 
C++-Versionen ist es dank nullptr eleganter gelöst, aber in C geht es 
halt so. NULL ist explizit genau dafür gedacht, auf Pointer zugewiesen 
oder verglichen zu werden, daher macht es keinen Sinn etwas eigenes 
dafür zu definieren. Wenn der Compiler davor warnt, etwas genau dafür zu 
benutzen wofür es vorgesehen ist, stimmt mit dem was nicht.

Stephan schrieb:
> Die ist kein Boolesche Ausdruck und es gibt eine Warnung!

Es ist nach bool konvertierbar, und daher ist es absolut korrekt und 
wohldefiniert. Wer hier warnt, ist extrem paranoid, denn hier gibt es 
kein Fehlerpotenzial.

Stephan schrieb:
> Mein Compiler hat ein paar MISRA Regeln mit eingebaut und prüft diese
> auch.

Ah, MISRA. Dann haben wir hier ein paar tolle Beispiele, wie MISRA den 
Code schlechter macht - schlechte Lesbarkeit (NULL_PTR ???) kann eben 
auch Sicherheitsprobleme bewirken, weil man nicht mehr sieht, was 
passiert!

Stephan schrieb:
> Die "##" musste ich bei meinen Compiler auch erstmal freigeben, sind
> auch nicht erlaubt!

Ist auch absolut Standard und erlaubt. Sich so etwas erst zu verbieten 
und dann wieder zu aktivieren...

[Flederdil (Gast)]

Mit meinem obigen Versuch funktioniert es nicht, d.h. ich erhalte eine 
Reihe an solchen Fehlern:
    error: pasting "{" and "CREATE_STATE" does not give a valid 
preprocessing token

Flederdil schrieb:
> struct fsm test {

Hier fehlt wohl auch noch ein = ?

Und: gab es nicht einen Schalter für den Compiler (GCC), damit er den 
output nach dem Präprozessor nicht löscht? Ich würde mir gerne das 
Resultat ansehen...

[Stephan (Gast)]

Hi  Flederdil,

// hab den include hinzugefügt
#include <stdlib.h>
// '=' Zeichen fehlte
struct fsm test= {
// Da gehört ein *KOMMA* hin! :-)
.currState = STATE_ZERO,

Hier mal der Code von dir durch den Präprozessor gejagt:

struct fsm test= {
CREATE_FSM_TABLE(
    CREATE_STATE( STATE_ZERO,
        ADD_EVENT( EV_ZERO , STATE_ONE, NULL ),
        ADD_EVENT( EV_ONE, STATE_ONE, NULL ),
    ),
    CREATE_STATE( STATE_ONE,
        ADD_EVENT( EV_TWO, STATE_ZERO, NULL),
    ),
),
.currState = STATE_ZERO,
};

ergibt:

struct fsm test= {
    . stateTableSize= sizeof((struct fsm_state_data_s []){{ . state= STATE_ZERO, . eventTable= &(struct eventTransTab_s []){{ . eventId= (event_id_t)EV_ZERO, . nextState = (uint16_t)STATE_ONE, . transFunc = 0 }, { . eventId= (event_id_t)EV_ONE, . nextState = (uint16_t)STATE_ONE, . transFunc = 0 }, }, . eventTableSize = sizeof((struct eventTransTab_s []){{ . eventId= (event_id_t)EV_ZERO, . nextState = (uint16_t)STATE_ONE, . transFunc = 0 }, { . eventId= (event_id_t)EV_ONE, . nextState = (uint16_t)STATE_ONE, . transFunc = 0 }, }) / sizeof( struct eventTransTab_s )}, { . state= STATE_ONE, . eventTable= &(struct eventTransTab_s []){{ . eventId= (event_id_t)EV_TWO, . nextState = (uint16_t)STATE_ZERO, . transFunc = 0 }, }, . eventTableSize = sizeof((struct eventTransTab_s []){{ . eventId= (event_id_t)EV_TWO, . nextState = (uint16_t)STATE_ZERO, . transFunc = 0 }, }) / sizeof( struct eventTransTab_s )}, }) / sizeof( struct fsm_state_data_s ),
    . stateTable = &(struct fsm_state_data_s []) 
    {
        {   . state= STATE_ZERO, 
            . eventTable= &(struct eventTransTab_s [])
            {
                { . eventId= (event_id_t)EV_ZERO, . nextState = (uint16_t)STATE_ONE, . transFunc = 0 }, 
                { . eventId= (event_id_t)EV_ONE, . nextState = (uint16_t)STATE_ONE, . transFunc = 0 }, 
            }, 
            . eventTableSize = sizeof((struct eventTransTab_s []){{ . eventId= (event_id_t)EV_ZERO, . nextState = (uint16_t)STATE_ONE, . transFunc = 0 }, { . eventId= (event_id_t)EV_ONE, . nextState = (uint16_t)STATE_ONE, . transFunc = 0 }, }) / sizeof( struct eventTransTab_s )
        },         
        {   . state= STATE_ONE, 
            . eventTable= &(struct eventTransTab_s [])
            {
                { . eventId= (event_id_t)EV_TWO, . nextState = (uint16_t)STATE_ZERO, . transFunc = 0 }, 
            }, 
            . eventTableSize = sizeof((struct eventTransTab_s []){{ . eventId= (event_id_t)EV_TWO, . nextState = (uint16_t)STATE_ZERO, . transFunc = 0 }, }) / sizeof( struct eventTransTab_s )
        }, 
    },
    .currState = STATE_ZERO,
};

im Notepad++ sah der Text okay aus. wird hier nicht richtig angezeigt.
Kopiere den Text einfach nochmal.

[Flederdil (Gast)]

Danke dir, aber mein GCC mag es (Anhang) leider immer noch nicht. Die 
Fehler

    error: pasting "{" and "ADD_EVENT" does not give a valid 
preprocessing token

bleiben.

Vielleicht macht der Präprozessor nicht genügend Durchläufe?

gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=c:/mingw/bin/../libexec/gcc/mingw32/8.2.0/lto-wrapper.exe
Target: mingw32
Configured with: ../src/gcc-8.2.0/configure --build=x86_64-pc-linux-gnu --host=mingw32 --target=mingw32 --prefix=/mingw --disable-win32-registry --with-arch=i586 --with-tune=generic --enable-languages=c,c++,objc,obj-c++,fortran,ada --with-pkgversion='MinGW.org GCC-8.2.0-5' --with-gmp=/mingw --with-mpfr=/mingw --with-mpc=/mingw --enable-static --enable-shared --enable-threads --with-dwarf2 --disable-sjlj-exceptions --enable-version-specific-runtime-libs --with-libiconv-prefix=/mingw --with-libintl-prefix=/mingw --enable-libstdcxx-debug --with-isl=/mingw --enable-libgomp --disable-libvtv --enable-nls --disable-build-format-warnings
Thread model: win32
gcc version 8.2.0 (MinGW.org GCC-8.2.0-5)

[Stephan (Gast)]

HI,
dein Code läuft bei mir.
kannst du mal schauen was passiert wenn du die '##' vor dem 
'__VA_ARGS__' beim GCC weg lässt?

[Flederdil (Gast)]

Danke!

    gcc -E test.c > test_pre.txt

bricht nach den Ausgaben des Präprozessors ab.

[Stephan (Gast)]

Hallo,
so mit dem Code läuft es bei mir mit dieser Version:

gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)

gcc -save-temps test.c -o test1 -Wall -std=c11 -D__USE_MINGW_ANSI_STDIO

Sorry, habe das File doppelt angehängt.

[Flederdil (Gast)]

Hallo nochmal, ich habe mich wohl nicht klar ausgedrückt: es lief oben 
auch schon bei mir! Der Abbruch bezog sich auf die Ausgabe des 
"präprozessierten" Codes.
Nochmals besten Dank.