[Из песочницы] Машина состояний на чистом С
Почти каждый микроконтроллерщик сталкивался с громадными 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 };
