Доброго времени суток. Необходимо найти повторяющиеся байтовые сигнатуры в hex файле объёмом до 1 Гб. при этом изначально не известно какие они будут. нужно найти все возможные варианты. Самая большая загвоздка для меня в том что эти сигнатуры могут иметь вид bytes==0x2c && bytes[i+2]==0x5f && bytes[i+4]==0x65 && bytes[i+6] = 0x89 etc. соответственно bytes[i+1], bytes[i+3], bytes[i+5]- могут быть любыми значениями минимальная длинна 4 повторяющихся байта(то есть либо 0x2c 0x5f 0x65 0x89, либо 0x2c 0x01 0x5f 0x02 0x65 0x03 0x89) Еще добавлю, что не может быть смешанных видов сигнатур. То есть если они повторяются по порядку, то во всем файле. Если повторяются через один байт, то также во всём файле. Если в одном месте имеем определённые байты по порядку, а вдругом эти же байты встетились через один, то это не наш случай. Существуют ли инструменты которые позволяют делать подобный анализ данных? Если нет, то подскажите оптимальный алгос для решения этой задачи буду пилить прогу сам.
Такой поиск можно реализовать при помощи регулярных выражений. Например, регулярное выражение для первого случая записывается так: \x2c.\x5f.\x65.\x89 А потестировать можно так: Code: perl -0777 -ne 'printf "%v02x\n", $_ for /\x2c.\x5f.\x65.\x89/gs' file.bin
А если мы не знаем какие повторяющиеся значения будут попадаться. Если сигнатура известна, то проблем нет. Если же не известна, то это мой случай. я там значения для примера привёл. фактически же не повторяющиеся байты не известны
Не совсем понял, вы ищите сигнатуры/патерны которые повторяются во всём файле? Т.е. 0x2c 0xXX 0x5f 0xXX 0x65 0xXX 0x89 повторяется до конца файла или же они где-то повторяются, но не везде? И где они начинаются, всегда в одном месте или смещено?
Мне нужно найти повторяющиеся байты в файле. Какие это байты, я заранее не знаю. Они могут повторяться во всём файле от самых первых до последних. Смысл такой, в файле хранятся зашифрованные заголовки блоков данных. Их нужно найти. Они разные для каждого файла, но точно имеют одинаковый вид внутри одного файла.
Ну тогда как идея, если байты повторяются, но вы не знаете какие, то если их заксорить (XOR) Code: 0x2c 0x01 0x5f 0x02 0x65 0x03 0x89 XOR 0x2c 0x61 0x5f 0x42 0x65 0x31 0x89 -------------------------------------------------- 0x00 0x60 0x00 0x40 0x00 0x32 0x00 то должно выходить каждый второй байт будет 0, а потом уже вытаскивать саму сигнатуру. Сам ХОR должен очень быстро проходить. Т.е. алгоритм где-то такой: 1 задаёте длину сигнатуры в байтах (минимум 4 байта) и максимум скажем 128, 2 затем по длину всего файла 3 берёте 2 куска заданной длины и делаете XOR, 4 сравниваете результат, содержит ли он каждый второй байт 0. 5 Если да, то это ваш кандидат, записывайте в список. -> вы получаете длину сигнатуры и саму сигнатуру. Как-то так
Допустим, исходный файл начинается так 00 11 22 33 44 55 66 77 88 99 и мы ищем паттерн XX __ YY __ ZZ __ WW (буквы - неизвестные байты, имеющие значение, подчеркивание - байты значение которых не важно) Выписываем все четвёрки байт таким образом 00 22 44 66 11 33 55 77 22 44 66 88 ... После чего сортируем эту таблицу с подсчётом частоты появления каждой четвёрки, в результате видим наиболее часто встречающиеся паттерны (их может быть несколько из-за коллизий). Ну, а далее -
Если честно, то мне было влом сильно ломать мозг и я решил задачу в лоб: string file = @"file......."; byte[] data = File.ReadAllBytes(file); for(int i = 0; i< data.Length-8; i++) { byte sb1 = data; byte sb2 = data[i+ 1]; byte sb3 = data[i+ 2]; byte sb4 = data[i + 3]; byte sb5 = data[i + 4]; byte sb6 = data[i + 5]; byte sb7 = data[i + 6]; byte sb8 = data[i + 7]; if (sb2==0x02 || sb2 == 0x04 || sb2 == 0x06 || sb2 == 0x08 || (sb1 == sb2 && sb2 == sb3 && sb3 == sb4)) continue; // тут всякие условия чтобы откинуть мусор if (sb2 == 0xff || sb2 == 0x00 ) continue; if (sb4 == 0xff || sb4 == 0x00 ) continue; if (sb6 == 0xff || sb6 == 0x00 ) continue; if (sb8 == 0xff || sb8 == 0x00 ) continue; if (sb1 != 0x00 || sb3 != 0x00 || sb5!=0x00 || sb7!=0x00) continue; for (int j = 0; j < data.Length-8; j++) { if (data[j] == sb1 && data[j + 1] == sb2 && data[j + 2] == sb3 && data[j + 3] == sb4 && data[j + 4] == sb5 && data[j + 5] == sb6 && data[j + 6] == sb7 && data[j + 7] == sb8 && j != i * 4) { Debug.WriteLine($"Find 0x{sb1.ToString("X2")},0x{sb2.ToString("X2")},0x{sb3.ToString("X2")},0x{sb4.ToString("X2")},0x{sb5.ToString("X2")},0x{sb6.ToString("X2")},0x{sb7.ToString("X2")},0x{sb8.ToString("X2")} in position {j}"); } } Console.WriteLine($"{i} from {data.Length}"); } работает долго. но мои паттерны нашла.
В худшем случае тупой перебор. Первый байт - 4F. Ищем 4F во всем файле. Находим первое совпадение - берем второй байт. 4F 2C. Не подходит - создаем ветвь для 2С ищем дальше. Решение - дерево. Памяти займет хрен знает сколько, решение в лоб - но решается.
Хотя даже не обязательно дерево. С деревьями можно делать магию но можно просто для каждого случая создавать отдельного потомка. Работать будет долго - но работать будет. Х/з как быстрее. Надо думать.
Так тебе надо 8 байт искать конкретно совпадающих ? Тогда напрасный труд ты запилил. Если не только - то оно вообще не будет работать...
Вместо того чтобы писать byte sb1 = data; byte sb2 = data[i+ 1]; byte sb3 = data[i+ 2]; byte sb4 = data[i + 3]; byte sb5 = data[i + 4]; byte sb6 = data[i + 5]; byte sb7 = data[i + 6]; byte sb8 = data[i + 7]; Тебе надо создать соответствующую структуру и делать это одним присваиванием адреса. Если ушь так. Работать будет НАМНОГО быстрее.
ну труд не напрасный, вопрос то решен. А так начал с 4-х, потом 6, потом 8 и тут вариантов оказалось всего несколько десятков
согласен. идея была чтобы ещё записывалась частота попаданий , offset от начала файла. и ещё на с++ будет быстрее.
