Конечный автомат для распознавания последовательности

Всем привет! Пытаюсь реализовать конечный автомат для следующей задачи. По Ethernet приходят пакеты с данными, необходимо распознать и вывести на экран следующую последовательность данных:

0x11, 0x25, 0x30, 0x31, 0x32, 0x33, 0x34, 0x41;

Здесь 0x11 - первый байт, означает начало последовательности. 0x25 второй байт, означает количество байт идущих за ним (в младших 4 битах, в данном примере их 5). Далее байты и наконец завершающий байт. Старшие разряды предназначены для того, чтобы различать слова между друг другом. Я начал с того чтобы выделить абстракцию данных, с которыми работаю.

struct word
{
    /* data */
    uint8_t data;
    /* methods */
    uint8_t word_count() const { return (data & 0xF); }
    uint8_t high_bits() const { return (data >> 4) & 0xF; }
};

Далее я ввожу новую абстракцию парсер:

enum class parser_state {
  S1_WAIT_FIRST_WORD,
  S2_WAIT_SECOND_WORD,
  S3_WAIT_N_WORDS,
  S4_WAIT_END_WORD,  
};


struct parser {
    /* data */
    parser_state state;
    uint8_t word_count = 0;
    uint8_t current_count = 0;
    /* methods */
    void next_word(word & w);
};

соответственно, у него есть состояния и функция, где будут описаны переходы.

void parser::next_word(word &w) {
    switch (state)
    {
    case parser_state::S1_WAIT_FIRST_WORD: 
        /* code */
        if (w.high_bits() == 0x1) {
            state = parser_state::S2_WAIT_SECOND_WORD;
            word_count = w.word_count();
        } else {
            // error: miss first word
        }
        break;
    case parser_state::S2_WAIT_SECOND_WORD:
        /* code */
        if (w.high_bits() == 0x2) 
            state = parser_state::S3_WAIT_N_WORDS;
        else
            // error: miss second word!
        break;
    case parser_state::S3_WAIT_N_WORDS:
        if (w.high_bits() == 0x3) {
            current_count++;
            // we receive all words!
            if (current_count >= word_count) {
                state = parser_state::S4_WAIT_END_WORD;
            }
        } else {
            // error: miss some word with 0x3 prefix!
        }
        break;
    case parser_state::S4_WAIT_END_WORD:
        if (w.high_bits() == 0x4) {
            state = parser_state::S1_WAIT_FIRST_WORD;
        } else {
            // error!
        }
    default:
        break;
    }
}

Тривиально, ждем первого слова с признаком 0x1, после чего второе слово с признаком 0x2 и счетчиком. наконец слова с признаком 0x3 (все!) и финальное слово, признак конца последовательности.

Проблема в том, что будет если часть слов из последовательности 0x3 не придет? в данном случае я просто прыгаю в состояние S1 и снова жду новой последовательности. Но что если я пропущу одно слово, а остальные придут, для отладки я хотел бы отобразить их + отобразить ошибку. С данной целью я добавил буффер в парсер и отдельную сущность работающую с входным потоком данных по Ethernet:

struct network {
    parser prs;
    /* methods */
    void next_data(std::vector<unsigned char> data);
};

void network::next_data(std::vector<unsigned char> data) {
    if (data.empty())
        return;

    for (auto byte : data) {
        word w{byte};
        prs.next_word(w);
    }
}

Не нравится, что она содержит в себе парсер (это ведь две разные сущности, но пока так)

struct parser {
    /* data */
    std::vector<word> words;

В функции парсинга, я просто добавлю слова в буффер парсера.

    case parser_state::S1_WAIT_FIRST_WORD: 
        /* code */
        if (w.high_bits() == 0x1) {
            state = parser_state::S2_WAIT_SECOND_WORD;
            words.push_back(w);

При ошибке я жду первого состояния и очищаю буффер. Но что делать в случае такой последовательности?

0x11, 0x25, 0x30, 0x31, 0x32, 0x33, 0x11, 0x25

Видно что не пришло слово 0x34 и сразу за ним началась новая последовательность. Если следовать моей логике, то я ожидаю 0x34 но получаю 0x11 очищу буффер (а значит 0x11 и 0x25 пропадут) а ведь эти данные могли быть началом нового пакета. Как быть? Также хотелось бы отображать данные, а я их теряю. Возможно спасет введение таблицы переходов, но пока не уверен как это правильно сделать.


Ответы (1 шт):

Автор решения: Solt

По Ethernet не приходят данные просто так, их кто-то посылает. И если речь об Ethernet, то для начала надо парсить заголовок и выяснять, ваш ли это пакет, пришёл ли он оттуда, где знают ваш протокол обмена, иначе это будет мусор, а не полезные данные. Кроме того, пакеты сопровождаются контрольной суммой, которая подтверждает, что он не испорчен. Дальнейшие проверки на несоответствие протоколу должны быть минимальными и сводиться к отказу общения с отправляющей стороной, не следующей оговоренным условиям.

Теперь о вашем протоколе. Ничего буферизовать не надо. Если поймали 1 - ожидаете следом 2, если это не 2, а опять 1 - ждём 2, либо снова ждём 1.

Надо полагать 1 и 2 - это обязательное начало пакета, а после его тела 4-его конец, возможно с контрольной суммой. Отправляющая сторона послав 1 и 2 точно послала дальше весь пакет. Если в его конце не 4, то он испорчен, но он был пакетом и возвращаться искать в нём новые 1 и 2 нет смысла. Просто начинаем ожидать снова 1 и 2. Добавлять же 3 к каждому байту полезных данных - эта ужасная избыточность, которая, кстати, позволяет не использовать три других байта.

Если это не так - ваш протокол плохой и нормально данных никогда не передаст.

А теперь посчитаем, насколько он плохой. Худший исход - с одним полезным байтом. В этом случае мы имеем 4 байта = 32 бита, из которых полезных всего 4 бита. Итого 12.5% пользы. Лучший - 1500 байтов Ethernet одним пакетом (иногда 9000, но в принципе хоть 100500). Если пренебречь тремя контрольными байтами, то имеем 50% пользы и никогда больше. В чём удовольствие от такого протокола?

Если задача учебная - слабенько там у вас учат. Первое, чему должен учиться программист - оптимизировать каждое своё действие и искать ещё более оптимального решения, чтобы не терять ценные ресурсы памяти, ЦП и трафика. А уж потом учиться писать хоть на бейсике, хоть на асме.

Так что двойка разработчику протокола. И описывать его парсинг - уже занятие на двойку.

А что касается программы, это, конечно хорошо, что вы умеете использовать С++ с его абстракциями, методами и другой дребеденью, но данная программа может быть написана на С одним циклом с десятком строк и всё. Чтобы соответствовать названию "абстракция:конечный автомат" ей достаточно считывать входные байты, иметь одну единственную переменную с состоянием и вызывать функцию, в которую отдавать пакеты. Это всё в десятке строк и так будет. Ведь абстракцию не обязательно формировать в коде на С++, достаточно в мозге ;•)

И немного лирики. Любой код должен быть 1-эффективен, 2-лаконичен, 3-красив. Первое условие обязательно вообще для его жизни, ибо иначе зачем он нужен. Второе и третье повышают читабельность и понимание, а соответственно и поддерживаемость. Я, как руководитель, следую этим критериям именно в этой последовательности и не допускаю иного. А команда растёт в профессиональном плане и довольна таким подходом. Иные не задерживаются, чему все, включая их самих довольны.

Если что не так, простите, накипело.

→ Ссылка