| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Поиск последоват. байт с пропусками в байт массиве |
| Автор: supersonic 20.5.2013, 14:05 |
| Приветсвую! Есть задачка найти последоватательность байтов с пропусками в байтовом массиве, например есть такая последовательность, тут ?? означает любой байт ?? ?? ?? ?? ?? 1E 06 8C C8 8E D8 ?? ?? ?? 8E C0 50 BE ?? ?? 33 FF FC B6 длинна последовательности произвольная, количество и длинна пропусков также произвольны. Может есть какие то библиотеки для решения подобных задач ? Регулярки не подходят в виду того что для одного байт-массива будет выполнятся несколько тысяч таких поисков и время работы приложения значительно увеличится. |
| Автор: fish9370 20.5.2013, 15:04 |
| библиотек, таких не знаю, тут не так сложно написать самому, регулярные выражения для этой задачи не нужны исходя из задачи (как я ее понял) имеем три последовательности, которые идут в определенном порядке относительно друг друга 1) организуем поиск первой последовательности - тупой перебор до первого вхождения 2) перебор пока совпадают, иначе возврат к пункту 1 3) последовательность найдена - поиск следующей последовательности, переход к пункту 1 4) все последовательности найдены можно распараллелить поиск несколькими потоками, немного конечно будет сложнее |
| Автор: supersonic 20.5.2013, 17:08 |
| Общий принцип я примерно себе так и представлял, но условия вы немного не так поняли >>>>исходя из задачи (как я ее понял) имеем три последовательности, которые идут в определенном порядке относительно друг друга Длинна последовательности произвольная, количество и длинна пропусков также произвольны т.е. она может быть и такой (как в моем примере в 1м посте) ?? ?? ?? ?? ?? 1E 06 8C C8 8E D8 ?? ?? ?? 8E C0 50 BE ?? ?? 33 FF FC B6 а может быть и такой AD 4A 7B ?? ?? ?? ?? ?? 1E 06 8C ?? C8 8E D8 ?? ?? ?? 8E C0 50 BE ?? ?? 33 FF FC ?? ?? B6 |
| Автор: fish9370 20.5.2013, 19:42 |
| а в чем принципиальная разница? искомые последовательности нам известны целиком или есть еще какие-то условия? а, стоп, вроде врубился, т.е. совпадение может быть частичным? то что не отмечено вопросами нам неизвестно, правильно? |
| Автор: Arantir 20.5.2013, 20:15 | ||
| Выбросьте из искомой последовательности знаки вопроса и замените их соответствующими отступами. Организуйте обычный поиск, но ищите не целую последовательность, а интервалы соответствующей длины с соответствующими отступами между ними. Например:
Выбираем из массива первые 24 байта (0-23). Просто сравниваем 6-10, 14-17 и 20-23 байты. Если не сошлось — берем из массива 1-24 байты и сравниваем с теми же интервалами, добавляя смещение (7-11, 15-18, 21-24). По сути задача сводится к определению этих интервалов из входящего шаблона. В остальном можно использовать любой алгоритм поиска подмножества во множестве. |
| Автор: volatile 21.5.2013, 00:06 | ||||
если судить по дальнейши объяснениям, то неправильно вопрос задан. похоже вопрос должен звучать так:
где * - означает любое количество любых байтов. так? |
| Автор: supersonic 21.5.2013, 13:54 |
| Такс, может быть я немного не так пояснил - суть задачи заключается в поиске бинарных сигнатур внутри PE-файлов, сигнатуры могут быть т.н. разряженными, т.е. внутри сигнатуры может встретится любое количество "разрывов" произвольной длинны, тут "разрывы" - это любые байты, вот для примера одна сигнатура, взято с PeId [BeRoEXEPacker v1.00 -> BeRo / Farbrausch] signature=60 68 ?? ?? ?? ?? 68 ?? ?? ?? ?? 68 ?? ?? ?? ?? E8 ?? ?? ?? ?? BE ?? ?? ?? ?? B9 04 00 00 00 8B F9 81 FE ?? ?? ?? ?? 7F 10 AC 47 04 18 2C 02 73 F0 29 3E 03 F1 03 F9 EB E8 BA ?? ?? ?? ?? 8D B2 ep_only=1 т.е. это означает что PE файл начиная со своей точки входа имеет сначала 2 байта 60 68 потом 4 любых байта потом снова байт 68 потом снова 4 любых и снова после них 68 и так далее... ну и таких сигнатур более 7к, каждую последовательность нада проверить на более чем лям различных файлов. |
| Автор: volatile 21.5.2013, 14:05 |
| supersonic, пока вы сами не решите что вам нужно, никто вам не поможет. последний пост противоречит 2-му посту. |
| Автор: Dem_max 22.5.2013, 07:41 |
| ТС а ?? ?? ?? ?? ?? 1E 06 8C C8 8E D8 ?? ?? ?? 8E C0 50 BE ?? ?? 33 FF FC B6 и 1E 06 8C C8 8E D8 ?? ?? ?? 8E C0 50 BE ?? ?? 33 FF FC B6 не одно и тоже ?? |
| Автор: xvr 22.5.2013, 15:26 | ||
В таком случае именно регулярки вам и помогут. Только по ним надо построить конечный автомат, причем ровно один сразу по всем вашим 7к сигнатур |
