Конечный автомат для распознавания последовательности
Всем привет! Пытаюсь реализовать конечный автомат для следующей задачи. По 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 шт):
По 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-красив. Первое условие обязательно вообще для его жизни, ибо иначе зачем он нужен. Второе и третье повышают читабельность и понимание, а соответственно и поддерживаемость. Я, как руководитель, следую этим критериям именно в этой последовательности и не допускаю иного. А команда растёт в профессиональном плане и довольна таким подходом. Иные не задерживаются, чему все, включая их самих довольны.
Если что не так, простите, накипело.