|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
|||
|
|||
Быстрый поиск HEX строки в файле
Помогите пожалуйста реализовать быстрый поиск HEX строки в файле... Все методы которые я нашел в интернете довольнотаки медленные (можно сказать очень медленные) особенно для больших файлов, а например антивирус clamav использует HEX строки как сигнатуры вирусов, и поиск порядка 40000 сигнатур в одном файле занимает у него довольно мало времени (100 - 200ms) помогите реализовать такойже быстрый поиск на Delphi...
|
#2
|
||||
|
||||
Если бы ты внимательно посмотрел пример поиска Массива в Массиве, то увидел бы, что точно так же можно искать НЕХ - последовательность в файле.
Что касается Антивирусов, то они поступают следующим образом - 1. Генерируют базу данных с КОНТРОЛЬНЫМИ СУММАМИ сигнатур. 2. Сканируют НЕ весь файл, а только некоторую часть от Точки Входа + РЕ заголовок. 3. Из того, что они насканировали вычисляют контрольную суму 4. Сравнивают полученную контрольную сумму с теми, что находятся в базе данных Поэтому он так быстро и работают. А если бы они сканировали и сравнивали непосредственно сигнатуры, то и файл с антивирусными базами занимал бы сотни мегабайт. (Одна сигнатурка занимает порядка 2-4 кбайт, а если их 40 тысяч, то файл соответственно будет 80-160 Мб) Хорошо написанная программа не требует документации ICQ 9-184-668. Последний раз редактировалось Thrasher, 07.03.2008 в 10:11. |
#3
|
|||
|
|||
Цитата:
|
#4
|
|||
|
|||
Про остальные антивирусы не знаю, а конкретно в clamav сканируется весь файл, тем более Точка Входа + РЕ заголовок существуют только у PE файлов, а сканируются файлы всех типов...
Например если приписать вот такую последовательность (890eb301b801039c2eff1ebb017216b801035a52b600b9010 00e078d1e00019c2eff1ebb01) к любому авишному файлу куданить в самый конец файла то clamav увидит в нем вирус (Gen.3Devils.B), значит он сканирует весь файл, и с очень большой скоростью! |
#5
|
||||
|
||||
Да очень просто все! Бери и читай весь файл в массив, а потом ищи в нем необходимую последовательность!
Хорошо написанная программа не требует документации ICQ 9-184-668. |
#6
|
|||
|
|||
Цитата:
Да пробовал я читать файл в массив а потом прогонять поиск... но скорость ужасная! раз в 15 - 20 медленнее чем у clamav... Может алгоритм какой надо использовать??? или может ктонить знает как реализован поиск в кламе??? Подскажите... |
#7
|
||||
|
||||
Может он проверяет несколько файлов сразу. Или он проверяет не весь файл сразу, а разбивает его на части и сканирует каждую из них. Может даже и то, и другое одновременно. =)
Что делать, когда сломался комп: 1. Если вы юзер - делать ноги. 2. Если ремонтник - делать деньги. 3. Если вы программист - делать вид, что так было задумано. |
#8
|
|||
|
|||
Ну незнаю... я многопоточности в кламе не замечал...
Сейчас я использую следующий код для поиска НЕХ строки, может в нем можно чего ускорить??? Код:
type SBMTable = array [0..255] of Byte; ... procedure MakeBMTableEx( var BMT : SBMTable; const P : array of byte; Len: integer); var I : Byte; begin for i := 0 to 255 do BMT[i] := Len; for i := Len downto 0 do if BMT[(P[i])] = Len then BMT[(P[i])] := Len - i; end; function BMSearchEx( StartPos : Integer; const S, P : array of byte; const BMT : SBMTable) : Integer; var Pos, lp : INTEGER; I : INTEGER; begin lp := Length(P)-1; Pos := StartPos + lp -1; while Pos < Length(S) do if P[lp] <> S[Pos] then Pos := Pos + BMT[S[Pos]] else for i := lp - 1 downto 0 do if P[i] <> S[Pos - lp + i] then begin Inc(Pos); Break; end else if i = 1 then begin Result := Pos - lp + 1; Exit; end; Result := -1; end; function SearchInFileEx(Hex: AnsiString): integer; var I : BYTE; MB : SBMTable; InputArrayLength: BYTE; InputArray : Buffer; B : integer; begin InputArrayLength := Length(Hex) div 2; SetLength(InputArray,InputArrayLength); for I := 0 to Length(InputArray)-1 do InputArray[i]:=StrToInt('$'+Copy(Hex, (I+1) * 2 - 1, 2)); MakeBMTableEX(MB,InputArray,Length(InputArray)-1); B := BMSearchEx(0,BUF,InputArray,MB); if B > -1 then Result := B else Result := -1; Finalize(InputArray); end; ... procedure TForm1.Button1Click(Sender: TObject); var I,T,T1: integer; B: integer; begin T := GetTickCount; FS := TMemoryStream.Create; FS.LoadFromFile(Edit1.Text); SetLength(BUF,FS.size); FS.Read(BUF[0],FS.SIZE); for i := 0 to 1000 do begin searchinfileex(Edit2.Text); //Edit2 - НЕХ строка... Label1.Caption := inttostr(i); Update; end; B := searchinfileex(Edit2.Text); if B > 0 then Memo1.Lines.Add('Find at pos: '+inttostr(B)) else Memo1.Lines.Add('Not Find'); FS.Free; Finalize(BUF); T1 := GetTickCount; Memo1.Lines.Add('Speed :' + inttostr(t1-t)+'ms'); end; |
#9
|
||||
|
||||
может эта статья поможет?:
http://www.noil.pri.ee/?mod=art/art&id=154 |
#10
|
|||
|
|||
Народ ну помогите же!!! Мне курсовик сдавать через две недели... а быстрый поиск реализовать немогу... =(
|
#11
|
||||
|
||||
загляни сюда
http://delphiworld.narod.ru/base/search_text.html по моему даже с некоторой текстовкой для курсовой ток немного переделать и поменьше: http://delphiworld.narod.ru/base/str_find.html http://delphiworld.narod.ru/base/sea...text_file.html может что подойдет а так еще бы вставочку на ассемблере |
#12
|
|||
|
|||
Спасибо конечно, но во всех ссылках приведен алгоритм Бойера-Мура, а я его и так использую в коде который я привел выше...
|
#13
|
||||
|
||||
Я те ссылки краем глаза глянул, но вроде там были еще какие-то таблицы векторов. (пропустил твой последний код - действительно )
Да и думал, что для курсовой главное какойто творческий (описательный) процесс (уже подзабываю учебу ). в реале (по моим рассуждениям проблеммой основательно не занимался) - либо ассемблерная вставка (даже не либо а как дополнение для быстродействия) - либо идти на разработку однопроходной (всмысле без вложенного цикла) схеме тоесть попытаться в основном цыкле проверять 2, 3.... байты и одновременно искать следующие вхождения (типа ротора получится)( в место индекса в искомом цикле попытаться массив индексов) - еще можно попробовать разделить массив где ищут на несколько частей ( Код:
d := length/3 {или побольше} ; pos1 := 0; pos2 := d; pos3 := 2*d; // а в цикле одновременно if P[pos1] = S[i] if P[pos2] = S[i] ) К сожалению немогу гарантировать что будет быстрее и у самого со временнем напряженка чтоб основательно повозится. Надеюсь что чтонибудь пригодится. Удачи |
#14
|
|||
|
|||
К сожалению у меня быстрее чем в прошлом моем коде не получается... =(
Уже незнаю что и делать... Может кто кодом выручит (Разумеется не за отдельное "спасибо"!)... |
#15
|
||||
|
||||
Я в файле ищю нужный мне буфер данных через TMemoryStream или TFileStream. Выглядит примерно так.
var InFile:TMemoryStream; Pos:LongWord; Temp:Array[0..100]Of Byte; FindCount:Word; begin InFile:=TMemoryStream.Create(); InFile.LoadFromFile('Твой файл.bin'); FindCount:={Длина поисковой строки} While Pos<>InFile.Size Do Begin InFile.ReadBuffer(Temp,FindCount) InFile.Position:=Pos; If Temp={То что тыищеш}Then ... End; InFile.Free; |