Машина станів на чистому

Майже кожен микроконтроллерщик стикався з величезними 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
};



Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.