Конечный автомат (он же машина состояний) на чистом С

Почти каждый микроконтроллерщик сталкивался с громадными switch-case и мучительно их отлаживал.
И много кто, начиная писать реализацию какого-либо протокола, задумывался как написать её красиво, изящно, так чтобы через месяц было понятно что ты имел в виду, чтобы она не отжирала всю память и вообще какала бабочками.
И вот тут на помощь приходят машины состояний, они же конечные автоматы (те самые которые используются в регулярных выражениях).

Собственно через регулярные выражения я к ним и пришёл.

Недавно мне потребовалось реализовать несложную функциональность устройства с 4-мя кнопками — выделение в потенциально хаотичных нажатиях кнопок двух кодовых последовательностей и выполнение определённых действий, когда последовательность найдена.

Поясню на примере: есть 4 кнопки — A, B, C, D и кодовая последовательность ACDA. Тогда при последовательном нажатии B, C, A, D, A, C, D, A, B, устройство должно зажечь лампочку после 8-го (предпоследнего) нажатия. С точки зрения регулярных выражений задача проста — ищем во входной строке подстроку «ACDA». Как только нашли — зажигаем лампочку. Но тащить в микроконтроллер какую-нибудь библиотеку по работе с regexp не хотелось. Я чувствовал что всё можно сделать самому и проще. Тогда я решил попробовать самостоятельно реализовать конечный автомат соответствующий поиску данной подпоследовательности.

А теперь — немного теории и практики:

Основная черта конечных автоматов — они описываются набором возможных состояний, набором сигналов (событий) и таблицей переходов. Таблица переходов — это сопоставление паре из текущего состояния и пришедшего сигнала нового состояния.

Представим, что у нас есть автомат с 3 состояниями и 3 сигналами, которые нужно обрабатывать. По приходу каждого сигнала автомат совершает переходит в новое состояние.

Наиболее интуитивный, но громоздкий код для подобной задачи:

enum states
{
    initial = 0,
    state_1,
    state_final
};

enum signals
{
    sign0,
    sign1,
    sign_N
};

enum signals getSignal();

void doFSM()
{
    enum states current_state = initial;
    while (1)
    {
        enum signals current_signal = getSignal();
        switch (current_state)
        {
            case initial:
                switch (current_signal)
                {
                    case sign0:
                        current_state = state_1;
                        break;
                    case sign1:
                        current_state = initial;
                        break;
                    case signN:
                        current_state = state_1;
                        break;
                }
                break;
            case state_1:
                switch (current_signal)
                {
                    case sign0:
                        current_state = initial;
                        break;
                    case sign1:
                        current_state = state_1;
                        break;
                    case signN:
                        current_state = state_final;
                        break;
                }
                break;
            case state_final:
                switch (current_signal)
                {
                    case sign0:
                        current_state = initial;
                        break;
                    case sign1:
                        current_state = initial;
                        break;
                    case signN:
                        current_state = initial;
                        break;
                }
                break;
        }
    }
}

Очевидно что данный код не очень удобочитаем и будет катастрофически разрастаться с увеличением количества состояний и сигналов.
Кроме того, если мы захотим в каждый переход добавить какое-либо однотипное действие (например логирование — что-то вроде

printf("Current = %d, signal = %d\n", current_state, current_signal);

), то это породит кучу изменений в коде. При редактировании таких изменений почти наверняка будет допущена какая-нибудь ошибка и отладка превратится в ад.

Заметим, что суть двух вложенных switch — это выбор из таблицы (по колонке и по столбцу) и вспомним что формально конечные автоматы удобно записывать в виде таблицы переходов где каждая строка соответствует сигналу, каждый столбец — состоянию, а на пересечении записано состояние в которое переходит автомат.

Попробуем упростить имеющийся код, задав таблицу переходов, извините за тафтологию, таблицей.

enum states FSM_table[3][3] = {
    [initial][sign0] = state_1,
    [initial][sign1] = initial,
    [initial][sign_N] = state_1,
    [state_1][sign0] = initial,
    [state_1][sign1] = state_1,
    [state_1][sign_N] = state_final,
    [state_final][sign0] = initial,
    [state_final][sign1] = initial,
    [state_final][sign_N] = initial
};

Продемонстрированый вид инициализации даннных известен как designated inits и был введён в С99.

теперь надо полученную структуру данных обработать — пишем функцию doFSM_table:

void doFSM_table()
{
    enum states current_state = initial;
    while (1)
    {
        enum signals current_signal = getSignal();
        current_state = FSM_table[current_state][current_signal];
    }
}

Код получился проще и понятнее, правда?
Теперь ещё несколько бонусов подобной записи:

• нет ничего проще, чем добавить отладочный вывод к каждому шагу автомата:
  
  doFSM_table с отладочным выводом

  void doFSM_table()
  {
      enum states current_state = initial;
      while (1)
      {
          enum signals current_signal = getSignal();
          enum states new_state = FSM_table[current_state][current_signal];
          printf("Current = %d, signal = %d, new = %d\n", current_state, current_signal, new_state);
          current_state = new_state;
      }
  }
  

  
  
  
  
• собранный бинарный код существенно уменьшится, что бывает очень полезно в микроконтроллерах
• при необходимости таблицу переходов можно изменить прямо во время выполнения, например при загрузке новой конфигурации

Чтобы сделать получившийся автомат ещё более универсальным и придать ему возможность совершать какие-то действия кроме перехода по состояниям добавим в таблицу указатели на функции-обработчики, соответствующие переходам:

Автомат с произвольными действиями на каждом переходе

typedef void (*transition_callback)(enum states state, enum signals signal);

struct transition
{
    enum states new_state;
    transition_callback worker;
};

void initial_1_fxn(enum states state, enum signals signal);
void initial_1N_fxn(enum states state, enum signals signal);
void fxn2(enum states state, enum signals signal);
void fxn3(enum states state, enum signals signal);
void to_initial_fxn(enum states state, enum signals signal);

struct transition FSM_table[3][3] = {
    [initial][sign0] = {state_1, initial_1_fxn},
    [initial][sign1] = {initial, NULL},
    [initial][sign_N] = {state_1, initial_1N_fxn},
    [state_1][sign0] = {initial, fxn2},
    [state_1][sign1] = {state_1, fxn3},
    [state_1][sign_N] = {state_final, NULL},
    [state_final][sign0] = {initial, to_initial_fxn},
    [state_final][sign1] = {initial, to_initial_fxn},
    [state_final][sign_N] = {initial, to_initial_fxn}
};

void doFSM_table()
{
    enum states current_state = initial;
    while (1)
    {
        enum signals current_signal = getSignal();
        enum states new_state = FSM_table[current_state][current_signal].new_state;
        transition_callback worker = FSM_table[current_state][current_signal].worker;
        if (worker != NULL)
        {
            worker(current_state, current_signal);
        }
        current_state = new_state;
    }
}

Вообще улучшать данный механизм можно долго, но данная статья ставит своей целью не разработать универсальную библиотеку для реализации конечных автоматов, а продемонстрировать как некоторые задачи могут быть решены значительно проще и компактнее чем «в лоб», при этом не прибегая ни к каким замысловатым библиотекам или языкам.

В заключение приведу таблицу, получившуюся для задача поиска подпоследовательности, с которой я начинал:

Получившаяся таблица состояний:

enum states FSM_table[9][4] = {
    [initial ... sACDA][bA ... bD] = initial, //для всех сигналов кроме описанных ниже возвращаемся в исходное состояние.
    [initial][bA] = sA, //распознали начало последовательности
    
    //ветка для последовательности ABADC
    [sA][bB] = sAB,
    [sAB][bA] = sABA,
    [sABA][bD] = sABAD,
    [sABAD][bC] = sABADC,
    
    //ветка для последовательности ACDA
    [sA][bC] = sAC,
    [sAC][bD] = sACD,
    [sACD][bA] = sACDA
};