[Vlad_88]

Помогите пожалуйста реализовать быстрый поиск HEX строки в файле... Все методы которые я нашел в интернете довольнотаки медленные (можно сказать очень медленные) особенно для больших файлов, а например антивирус clamav использует HEX строки как сигнатуры вирусов, и поиск порядка 40000 сигнатур в одном файле занимает у него довольно мало времени (100 - 200ms) помогите реализовать такойже быстрый поиск на Delphi...

[Thrasher]

Если бы ты внимательно посмотрел пример поиска Массива в Массиве, то увидел бы, что точно так же можно искать НЕХ - последовательность в файле.

Что касается Антивирусов, то они поступают следующим образом -
1. Генерируют базу данных с КОНТРОЛЬНЫМИ СУММАМИ сигнатур.
2. Сканируют НЕ весь файл, а только некоторую часть от Точки Входа + РЕ заголовок.
3. Из того, что они насканировали вычисляют контрольную суму
4. Сравнивают полученную контрольную сумму с теми, что находятся в базе данных

Поэтому он так быстро и работают.
А если бы они сканировали и сравнивали непосредственно сигнатуры, то и файл с антивирусными базами занимал бы сотни мегабайт. (Одна сигнатурка занимает порядка 2-4 кбайт, а если их 40 тысяч, то файл соответственно будет 80-160 Мб)

[Phedor]

Сообщение от Vlad_88

Помогите пожалуйста реализовать быстрый поиск HEX строки в файле... Все методы которые я нашел в интернете довольнотаки медленные (можно сказать очень медленные) особенно для больших файлов, а например антивирус clamav использует HEX строки как сигнатуры вирусов, и поиск порядка 40000 сигнатур в одном файле занимает у него довольно мало времени (100 - 200ms) помогите реализовать такойже быстрый поиск на Delphi...

Кто мешает преобразовать HEX во что-то удобоваримое?

[Vlad_88]

Про остальные антивирусы не знаю, а конкретно в clamav сканируется весь файл, тем более Точка Входа + РЕ заголовок существуют только у PE файлов, а сканируются файлы всех типов...
Например если приписать вот такую последовательность (890eb301b801039c2eff1ebb017216b801035a52b600b9010 00e078d1e00019c2eff1ebb01) к любому авишному файлу куданить в самый конец файла то clamav увидит в нем вирус (Gen.3Devils.B), значит он сканирует весь файл, и с очень большой скоростью!

[Thrasher]

Да очень просто все! Бери и читай весь файл в массив, а потом ищи в нем необходимую последовательность!

[Vlad_88]

Сообщение от Thrasher

Да очень просто все! Бери и читай весь файл в массив, а потом ищи в нем необходимую последовательность!

Да пробовал я читать файл в массив а потом прогонять поиск... но скорость ужасная! раз в 15 - 20 медленнее чем у clamav... Может алгоритм какой надо использовать??? или может ктонить знает как реализован поиск в кламе??? Подскажите...

[The Shadow]

Может он проверяет несколько файлов сразу. Или он проверяет не весь файл сразу, а разбивает его на части и сканирует каждую из них. Может даже и то, и другое одновременно. =)

[Vlad_88]

Ну незнаю... я многопоточности в кламе не замечал...
Сейчас я использую следующий код для поиска НЕХ строки, может в нем можно чего ускорить???

Код:

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;

[s0Creator]

может эта статья поможет?:
http://www.noil.pri.ee/?mod=art/art&id=154

[Vlad_88]

Народ ну помогите же!!! Мне курсовик сдавать через две недели... а быстрый поиск реализовать немогу... =(

[s0Creator]

загляни сюда
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

может что подойдет
а так еще бы вставочку на ассемблере

[Vlad_88]

Спасибо конечно, но во всех ссылках приведен алгоритм Бойера-Мура, а я его и так использую в коде который я привел выше...

[s0Creator]

Я те ссылки краем глаза глянул, но вроде там были еще какие-то таблицы векторов. (пропустил твой последний код - действительно )
Да и думал, что для курсовой главное какойто творческий (описательный) процесс (уже подзабываю учебу ).

в реале (по моим рассуждениям проблеммой основательно не занимался)
- либо ассемблерная вставка (даже не либо а как дополнение для быстродействия)
- либо идти на разработку однопроходной (всмысле без вложенного цикла) схеме тоесть попытаться в основном цыкле проверять 2, 3.... байты и одновременно искать следующие вхождения (типа ротора получится)( в место индекса в искомом цикле попытаться массив индексов)
- еще можно попробовать разделить массив где ищут на несколько частей
(

Код:

d := length/3 {или побольше} ; pos1 := 0; pos2 := d; pos3 := 2*d; 
// а в цикле одновременно
if P[pos1] = S[i]
if P[pos2] = S[i]

...
)
К сожалению немогу гарантировать что будет быстрее и у самого со временнем напряженка чтоб основательно повозится.
Надеюсь что чтонибудь пригодится.
Удачи

[Vlad_88]

К сожалению у меня быстрее чем в прошлом моем коде не получается... =(
Уже незнаю что и делать...

Может кто кодом выручит (Разумеется не за отдельное "спасибо"!)...

[M.A.D.M.A.N.]

Я в файле ищю нужный мне буфер данных через 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;