Стоит ли напрягаться со строками (поиск/сравнение)? Обычный Си
Вот несколько дней обсасываю способ поиска соответствия строк с заданными при компиляции.
Значит проблема в следующем, есть ограниченный набор строк (около 13ти), из которых формируется команда, в ответ приходит сначала та же строка, что я посылал в устройство, а затем ответные значения, среди которых встречается часть строки запроса, конкретно - имя команды без префикса, затем двоеточие, пробел и ответ.
Возможно я бы и обошелся какими-либо быстрыми поисками ключевых символов, но есть одно НО, иногда устройство может выплюнуть сообщение с определенными данными, опять же с командой, двоеточием итд, но вот команда другая, чем я отправлял, а затем идут данные от моей команды, опять же по формату. Это выплевывание непредсказуемо, и документировано в описании устройства, поэтому его переделать не получится.
Внимание - вопрос:
Возможно ли сделать быстрый поиск команд в ответной строке? Думал про сравнение в лоб каждой строчки, но это не самый красивый способ, хотя что то в нем есть.
Основная проблема, что на каждую команду нужен свой обработчик ответа, ибо интерфейс устройства разрабатывался еще в лохматые годы и ориентирован на человека, поэтому весь обмен идет в текстовом режиме, другого нет. А задача как раз и состоит в автоматизации.
Длинна команды (искомой строчки) - 4 символа, правда есть одна на 3 символа, но это мелочь.
Буду признателен за дельные советы. API и прочую "ересь" с привязкой к ОС или внешним программам не предлагать.
Ресурсы жутко ограничены, так что чем проще решение, тем лучше.
Внимание - вопрос:
Возможно ли сделать быстрый поиск команд в ответной строке? Думал про сравнение в лоб каждой строчки, но это не самый красивый способ, хотя что то в нем есть.
Ничего не понял из описания, но "лобовое" сравнение для 13 строк по 4 символа (при том, что совпадение ищется в начале строки) в принципе хорошее решение даже для компьютеров 20-летней давности.
А что конкретно не понятно? есть 12 строчек, по 4 символа и одна в 3 символа, девайс выплевывает ответы на команды, где содержится одна из 13ти строчек, требуется найти соответствие и запустить функцию-обработчик ответа. Вопрос, как отделаться минимальными потерями времени на поиск соответствия строки.
Меня посещала идея, относительно подсчета контрольной суммы этих 4х символов, а потом брать из массива указатель на функцию-обработчик, но не смог добиться уникальности сумм. Главное, чтобы значений сумм не было больше 15ти.
А что конкретно не понятно? есть 12 строчек, по 4 символа и одна в 3 символа, девайс выплевывает ответы на команды, где содержится одна из 13ти строчек,
Делается все в принципе за один проход по потоку. Начинаем читать поток, как только наткнулись на двоеточие (или какой там разделитель после названия команды) - ищем в предыдущих 3-4х символах команду, если соответствие найдено - ура, мы наткнулись на ответ команды. Ну и возвращаем код команды, по которому можно вызывать функцию по таблице.
4 символа - это 32битный регистр (число). Делайте выводы ;).
1) Вы не называли модели контроллера
2) Я не являюсь специалистом в программировании микроконтроллеров
3) Без разницы в том, сколько битов в регистрах на целевой машине, ваша задача будет сводится к сравнению (проверки равенства) N-разрядных чисел (в данном случае 32х).
union
{
char str[4];
unsigned long var;
}t_prien_u;
/////////////
t_prien_u *priem_u = (t_prien_u*)&Buf[0];
в любой момент можно обратиться или к строке или к переменной а главный вопрос не в том что я буду сравнивать, а в том, как это сравнивать. Если сравнивать последовательно 13 строчек то, чтобы добраться до последней строчки, надо перебрать все 12 строк, я же пытаюсь узнать есть ли способ быстро найти искомую строчку, или же делать перебор 12ти строчек. В идеале должна получиться формула вида F(str) = &Func_Obrab(), сию формулу требуется читать в обратном порядке - функция от строчки дает адрес обрабатывающей функции.
1) Сделать влоб тупым сравнением
2) Измерить производительность - и если ее нехватит то сделать решатель на свичах, последовательно сравнивающих символы.
Это будет натуральная реализация ДКА, которую делают компиляторы регулярных выражений.
Еще возник вопрос расширения, если потребуется добавить новые команды, то switch разрастется до невообразимых размеров, уже пройденный этап, вот и решил спросить у других людей, может кто встречал.
Кстати тут вы писали, что не специалист в программировании контроллеров, но подобная задача может возникнуть не только в контроллерах, любой критический участок кода может потребовать решения подобной задачи.
Кстати тут вы писали, что не специалист в программировании контроллеров, но подобная задача может возникнуть не только в контроллерах, любой критический участок кода может потребовать решения подобной задачи.
В .NET я наверное бы на регулярном выражении сделал. На C++ можно и Boost::Spirit2 попробовать.
А в общем виде такие задачи как правило решаются с применением генераторов парсеров, типа ANTLR, COCO/R и прочих Bison'ов. Эти инструменты сами строят подобные деревья разбора.
Я бы сделал switch по символам, строки же регистрозависимые?
простите, ошибся, разумеется вместо strcat надо было написать strstr, или strcmp это от реализации зависит.
Уточню, что имел ввиду преобразование 4 символов в int32 и по нему уже switch.
Жаль, что switch преобразуется в конструкцию if else if... если смотреть в ассемблере, то будет достаточно громоздко, да и опять получится, что чтобы добраться до последнего слова программе придется перебрать все комбинации.
Если какие-то команды выполняются чаще - почему бы не сделать тест на них сперва, а самые редкие сдвинуть вниз?
На C++ наверное проще использовать тупо std::map. Ключ - команда, значение - ответ. При большом числе команд это может быть более оптимальным.
Возможно, надо поискать реализацию аналога на C. Куда-то в сторону хеш-функций копать. Вроде бы у Кернигана и Пайка (Практика программирования) что-то такое было.
Для разбора строк, как класса задач, построение парсера предпочтительнее всего. Прежде чем выяснять с какой командой дело мы имеем ее нужно сперва вычленить из строки, вот для этого и есть специализированные инструменты - регулярные выражения или же PEG-парсеры для нерегулярных языков.
В данной задаче вычленять команду вполне можно и без регулярных выражений и уж тем более без синтаксических анализаторов. Неужели к такой копеечной проблеме уже Bison требуется?
В том то и дело что почти равновероятно для каждой команды. Ну есть, конечно исключения, но это 1-2 команды.
Туда и смотрю, был бы уникальный хэш на 15 значений, было бы проще. Типа CRC4 но такого вроде не встречал.
ТС спросил об общем случае - он и получил ответ об общем случае. ;)
Для 1-4х символьных строк они сами и есть уникальные хэши. Если нужно хэш на 1 или 2 байта можно просто последовательно перемножить символы. Проверить уникальность можно экспериментально.
Плавали, знаем. Копал я в ту сторону, пока безрезультатно, не могу добиться уникальности.
Жаль, что switch преобразуется в конструкцию if else if... если смотреть в ассемблере, то будет достаточно громоздко, да и опять получится, что чтобы добраться до последнего слова программе придется перебрать все комбинации.
Не всегда. Грамотный компилятор оптимизирует switch бинарным поиском.
Если выделить для массива память 2^32 + 2^24 + 2^16 +2^8 ?
Кстати, если учесть что для команд будет использоваться не все 256 вариантов байта, а только буквы, то массив будет меньше. Где-то 2^20, опять же в общем случае. Но боюсь что в используемом контроллере и для массива поменьше памяти не хватит.
Ещё можно выделить все варианты для первой буквы (всех имеющихся команд), для второй, и т.д. и рассчитывать только на эти варианты. Тогда памяти нужно будет ещё меньше.
только грамотных компиляторов для avr архитектуры нет. К сожалению.
..............
Ещё можно выделить все варианты для первой буквы (всех имеющихся команд), для второй, и т.д. и рассчитывать только на эти варианты. Тогда памяти нужно будет ещё меньше.
У меня столько памяти нет, тем более, что помимо общения с девайсом программа выполняет еще кучу функций.
вот примерно второй вариант и реализовал пока что, может еще что надумаю. Там получилось несколько switch вообще, и по вариантам букв, для второй (первые не шибко отличаются, всего 2 варианта, решил просто опустить) 7 case'ов, а в остальных случаях как получится, иногда 4 варианта, тогда еще switch если 2 варианта, то if, а иногда и первого варианта было достаточно.
Но я продолжаю поиски оптимального решения, подобная конструкция меня не устраивает, по эстетическим соображениям.
Я на то и намекал. С другой стороны, какой смысл разводить теоретические разговоры. Выдал бы свой набор 32-разрядных чисел - может кто-то и подобрал хорошую хэш-функцию. Может бы спортивный интерес появился.
EOIJ
EOIT
EOIU
EPOC
EPOK
ERCU
ERKP
EROU
ETGI
EUS
EUOU
UEKF
UNOU
Я даже в алфавитном порядке расположил, может кто заметит какую закономерность. Но тут есть один "подвох", возможно разработчики протокола и сделали какую закономерность, но для этого надо анализировать все команды, а я их не использую в таких объемах, ибо полная функциональность девайса мне не особо нужна. Но как я понял, изучая документацию, разработчики просто сокращали команды до 4х букв, без особой системы, хотя может я слишком узко смотрел. К сожалению документация грифованая, не могу ее выложить, как и копировать частями.
если я правильно перевёл (в нужном порядке байтов) и числа такие:
1179209541, 1246318405, 1414090565, 1430867781, 1129271365, 1263489093, 1430475333, 1347113541, 1431261765, 1229411397, 5461317, 1431262533, 1179338069, 1431260757
то можно взять остатки от деления на 67 и получить следующее:
33, 36, 49, 7, 11, 13, 24, 16, 17, 22, 56, 57, 27, 60
потом вычесть 7 и поделить на 2. В результате будет:
13, 14, 21, 0, 2, 3, 8, 4, 5, 7, 24, 25, 10, 26
То есть будет массивчик на 27 ячеек с дырками (не безупречно, да). Время на нахождение ответов будет одинаково для всех команд.
Предвижу, что в контроллере разделены память данных и память программ. При чем, память программ намного больше. В случае со switch строки ответа легко могли браться из памяти программ, в случае с хэш-функцией придётся хитрить.
Да, в контроллере флеш 128к против 4к оперативки, константы можно хранить на флешке, для остального есть оперативка, причем я еще подключил внешнюю на 32к, но в ней лежат буфера посылок, причем гигантские, ничего не могу с ними поделать, нужны.
А с цифрами, интересная мысль, надо попробовать рассмотреть в подобном аспекте. Немного напрягает операция деления, надо посмотреть сколько тактов она жреть, на 8МГц не шибко разбежишься с наборами команд. Хотя, по сути, выполняться данная операция будет редко. В общем попробую оценить возможности.
Посмотрел техдок на контроллер, про обычное деление написано, что выполняется за 2 такта, про вычисление остатка от деления - ничего, рискну предположить, что тактов 16 максимум, в той метрике, которая используется в документации. Завтра проверю во что преобразуется сишный код, дома нет компилятора, да и отладчик прогонит по тактам, буду точно знать сколько тиков ушло на выполнение.
Я ни в коем случае не придираюсь к способу или методу, просто проверяю, вдруг где пригодится, когда это будет именно критичный ко времени участок кода.
сорри, ошибся, смутило меня, что 2 такта на деление, перепроверил, не туда посмотрел, это умножение 2 такта, обычного деления в ассемблере контроллера нет. Рискну предположить, что вместо деления происходит умножение с обратным, дополненным до единицы. Завтра уточню.
Герцы тут ни при чём, но не важно.
Вместо деления можно попытаться использовать XOR-ы, сдвиги и всякие битовые маски. Но тут нужен метод подбора оптимальной функции, нужны удобные инструменты.
Например, удобно использовать контейнер для данных типа set в котором не может быть двух одинаковых цифр. С его помощью можно определять, правильно ли сработала подбираемая хэш-функция.
В си такого типа нет, поэтому лучше использовать другой язык, хотя бы C++.
Удобно, если в языке есть функции для определения минимума и максимума какой-либо последовательности. То есть, максимальный ключ нам покажет приблизительный размер необходимой памяти. Я сразу и не могу вспомнить, есть ли в си такие функции. Хотя, конечно, можно и самоделку сделать, например, использовав qsort.
Это я к чему говорю? Никто не захотел соревноваться в подборе лучшей хэш-функции (ибо switch кажется более правильным). Поэтому вам придётся подбирать функцию самостоятельно.
Да, хорошо бы использовать C++, но нет такого компилятора для микроконтроллеров.
При чём тут микроконтроллер? Я говорю, что C++ нужен для подбора функции, а не для микроконтроллера. Вот откуда я взял делитель 67? Не вручную же подбирал. Я программно перебрал все числа от 5461317 (меньшего числа из диапазона) до 1, и программно же оценивал удовлетворительность результата.
Можно перебирать какие-нибудь функции типа:
(s[a] << n) ^ (s[a+1] << m) ^ (s[a+3] << k) & mask
тут деления нет, но могут получиться небольшие уникальные результаты. Другое дело, что функции выглядят громоздкими. Так что, скорее всего, лучше не морочиться и использовать switch.
Да, хорошо бы использовать C++, но нет такого компилятора для микроконтроллеров.
Я не специалист по контроллерам, но есть компилятор IAR, который поддерживает C++. Хоть там и не полный C++: нет исключений, локалей и еще чего то.
Да и стоит этот компилятор под сотню тысяч за лицензию. Мне работодатель такого не купит.
Вообще процессору без разницы на каком языке написана программа, это более важно программисту.
Сорри за оффтоп.