Поиск в бинарном файле

← →
Dimaxx (2004-09-24 23:32) [0]

Сабж. Нужен алгоритм действительно быстрого поиска последовательности байт любой длины в файлах любого размера (до гигабайта). Читать кусками по-деревенски не катит. Раньше у меня был алгоритм, но с падением Фуджика все пропало.

← →
Defunct © (2004-09-25 01:33) [1]

S - строка поиска
I - текущий номер символа в строку поиска.

1. I := 1;
1. Создать буфер 1Mb или больше как вам нравится
2. Считать очередную порцию данных из файла.
3. Пока не вышли за границы буфера : Бежать по буферу в поисках S[1]
иначе - GOTO 7
4. Если нашли символ S[1] в буфере: тогда
For I:=2 to Length(S) do <сравниваем отсальные символы>
5. Совпадение - выход с результатом True
6. GOTO 3
7. Файл не закончился - GOTO 2
8. Выход с результатом False

← →
Defunct © (2004-09-25 01:36) [2]

[1] Алгоритм конечно же нуждается в поправках, но общий смысл такой.

← →
GuAV © (2004-09-25 01:37) [3]

> 1. Создать буфер 1Mb или больше как вам нравится

Сказали же

> Читать кусками по-деревенски не катит.

Хотя как без этого... ну низнаю :(

← →
Defunct © (2004-09-25 01:47) [4]

А где же там по-деревенски?

По-деревенски это будет примерно так:

S - строка поиска
S2 - буфер
Pos - позиция в файле

1. Pos := 0;
2. Seek(F, Pos)
3. считать в S2 Length(S) символов
4. Pos := Pos + 1;
5. S2=S - выход с результатом True
6. Pos + Length(S) < FileSize(F) - да GOTO 2
7. выход с результатом False

← →
Германн © (2004-09-25 02:08) [5]

А кто такой "Фуджик" и куда он упал?

← →
Defunct © (2004-09-25 02:39) [6]

Германн © (25.09.04 02:08) [5]

винт такой, они сейчас почти все сыпятся.

← →
Anatoly Podgoretsky © (2004-09-25 11:18) [7]

GuAV © (25.09.04 01:37) [3]
А раз не катит, то путей немного - все в память, можно через MMF

← →
TUser © (2004-09-25 15:06) [8]

См. например, алгоритм Кнута-Мориса-Пратта. Серьезные люди его придумали ...

← →
Dimaxx (2004-09-25 21:52) [9]

2 Defunct: Подобное делал. Туфта, ибо кусок в 1 метр файла просматривается около 2-5 секунд, а это очень много. А если мне нужно искать в одном файле несколько разных образцов? Тогда ваще тормоз получается. TotalCommander просматривает за это время 30-40 метров.

А хде посмотреть про алгоритм Кнута-Мориса-Пратта?

← →
Defunct © (2004-09-25 22:18) [10]

Dimaxx (25.09.04 21:52) [9]
Значит криво сделал.

Сейчас потрачу полчаса, и докажу обратное. Не может там тратиться 2-5 секунд.

← →
GuAV © (2004-09-25 22:34) [11]

> Dimaxx (25.09.04 21:52) [9]

Надо через SCASB/SCASW/SCASD искать первые 1/2/4
а потом CompareMem.

← →
default © (2004-09-25 22:41) [12]

конечно надо искать более серьёзные алгоритмы чем тупой перебор в данном случае...

← →
GuAV © (2004-09-25 22:44) [13]

> конечно надо искать более серьёзные алгоритмы чем тупой
> перебор в данном случае...

Может я и ошибаюсь, но имхо тупой перебор - самое быстрое.
При этом буфер большой, и за один такт перебора обрабатывать данные размером в машинное слово, т.е. 4 байта.

← →
default © (2004-09-25 22:45) [14]

http://www.3ka.mipt.ru/vlib/books/Programming/ComputerScience/StryngAnalysis/
вот тут недавно эту ссылку кидали

← →
Defunct © (2004-09-26 00:04) [15]

Держите, в 100 мегабайтном файле находит строку менее чем за 1 сек., возможно нужны поправки. Будут вопросы - задавайте.

Type TBuffer = Array[0..1000000-1] of byte; PBuffer = ^TBuffer; Function CharPos(AChar:Char; Buffer:Pointer; Size:Integer):Integer;Assembler; Asm Cld Push Es Push EDi Push Ds Pop Es Mov Al , AChar Mov EDi, Buffer Mov ECx, Size Push ECx Repne ScasB Pop EAx Jnz @@NotMatch Sub EAx, ECx Mov Result, EAx // This is odd when optimization is on Jmp @@Exit @@NotMatch: Mov Result, -1 @@Exit: Pop EDi Pop Es End; Function CompareStrings(Constant:String; Buffer:PBuffer):Boolean; Var I:Integer; Begin Result := True; I := 1; While Result and (I<Length(Constant)) Do Begin Inc(I); Result := Result and (Constant[i] = Chr(Buffer^[i-2])); End; End; Function LoadBuffer(var Buffer; var F:File; var SeekPos:Int64):Integer; Begin Seek(F, SeekPos); BlockRead(F, Buffer, 1000000, Result); SeekPos := FilePos(F); End; Function ConstantExists(FileName, Constant: String):Boolean; Var Buffer : PBuffer; SeekPos : Int64; F : File; BufSize : Integer; BufPos : Integer; SearchResult : Integer; Begin Result := False; If FileExists(FileName) Then Begin SeekPos := 0; New(Buffer); Assign(F, FileName); Reset(F,1); Repeat BufSize := LoadBuffer(Buffer^, F, SeekPos); BufPos := 0; While (Not Result) and (BufPos>=0) Do Begin SearchResult := CharPos( Constant[1], @Buffer^[BufPos], BufSize-BufPos ); If SearchResult>0 Then BufPos := BufPos + SearchResult Else BufPos := -1; If SearchResult<>-1 Then Begin Result := CompareStrings(Constant, @Buffer^[BufPos]); BufPos := BufPos + 1; End; If BufPos>=BufSize Then BufPos := -1; End; Until (BufSize=0) Or Result; Close(F); End; End; procedure TForm1.Button3Click(Sender: TObject); begin If ConstantExists(Edit1.Text, Edit2.Text) Then ShowMessage("Found") Else ShowMessage("Not Found"); end;

← →
Defunct © (2004-09-26 00:12) [16]

[15]

Оптимизпцией не занимался и не учитывал выход строки за границу буфера. Оставил эти задачи для вас.

← →
Defunct © (2004-09-26 00:26) [17]

> конечно надо искать более серьёзные алгоритмы чем тупой перебор в данном случае...

Это какие такие более серьезные алгоритмы позволят все просмотреть без пересмотра всего файла?

default © (25.09.04 22:45) [14]

Куча теории, мало практики. Ссылка ерундовая.
сходите лучше сюда:

www.intel.com
строка поиска:
Pentium Processor Family
Developers manual

← →
default © (2004-09-26 00:51) [18]

Defunct © (26.09.04 00:26) [17]
не понял "наезда"?
почему ерундовая ссылка?
вообще за что купил за то продал(я её тут взял)
"Это какие такие более серьезные алгоритмы позволят все просмотреть без пересмотра всего файла?"
не понял, вы хотите сказать что тот же к примеру алгоритм Бойера-Мура медленней обычного перебора Вами описанного в [1]?

← →
Defunct © (2004-09-26 01:01) [19]

> не понял "наезда"?

"наезд" был на ссылку, а не на вас.

> почему ерундовая ссылка?
потому что незная возможностей аппаратуры тобиш без практики, любая теория превращается в "пук".

> вообще за что купил за то продал(я её тут взял)

не спорю.

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

Естественно, алгоритм [1] будет быстрее работать чем алгоритм Бойра-Мура, потому что алгоритм [1] опирается на особенности архитектуры Intel x86 процессора, а господа Бойер и Мур сей особенности не знали и предложили сдвигать всю строку и искать с конца. таким образом в алгоритме Бойера-Мура нелья воспользоваться линейной строковой функцией Repne Scas.

← →
default © (2004-09-26 01:17) [20]

[19]
и всё-таки я сомневаюсь что Ваш вариант самый быстрый
скорее уверен что не самый

← →
GuAV © (2004-09-26 01:26) [21]

> Push Ds
> Pop Es

что то мне не нравится что сег регистры задействованы.

и ваще код не нравится... хотя алгоритм может быть и быстрый.

← →
Defunct © (2004-09-26 02:09) [22]

GuAV © (26.09.04 01:26) [21]
> что то мне не нравится что сег регистры задействованы.
см. документацию по команде STOS, работает с регистровой парой ES:[EDI]. на входе в функцию ES может отличаться от DS для этого приняты меры предосторожности.

> и ваще код не нравится...
хозяин-барин - напишите лучше.

default © (26.09.04 01:17) [20]
> и всё-таки я сомневаюсь что Ваш вариант самый быстрый
реализацию можно сделать быстрее почти на 30-40% если оперировать DWORD. Алгоритма более быстрого вы не найдете.

> скорее уверен что не самый
странно, что у вас доверие к алгоритмам 60-х годов выше чем к алгоритмам 2004 года.

← →
GuAV © (2004-09-26 02:16) [23]

> > что то мне не нравится что сег регистры задействованы.
> см. документацию по команде STOS, работает с регистровой
> парой ES:[EDI]. на входе в функцию ES может отличаться от
> DS для этого приняты меры предосторожности.

да я знаю, а Вы смотрите доку по BASM
Вы не должны никогда изменять содержимое сегментных регистров (ds, es и ss указывают на один и тот же сегмент; cs имеет свое собственное значение; fs используется Windows и gs резервирован).

> > и ваще код не нравится...
> хозяин-барин - напишите лучше.

> While Result and (I<Length(Constant)) Do
> Begin
> Inc(I);
> Result := Result and (Constant[i] = Chr(Buffer^[i-2]));
> End;

например здесь "Result and" - лишнее а Constant[i] содержит лишний UniqueString.
и потом я про

> быстрее почти на 30-40% если оперировать DWORD

← →
Defunct © (2004-09-26 02:52) [24]

GuAV © (26.09.04 02:16) [23]
> да я знаю

сомнительно

> а Вы смотрите доку по BASM

Я сам такие доки пишу, опираясь на документацию к процессорам.

> например здесь "Result and" - лишнее а Constant[i] содержит лишний UniqueString.

лишний что?

Да.. на фоне всего кода это очень серъезное замечание. см. [16]. Не нравится? напишете лучше, за то же время?
Жаль только у вас будет пример перед глазами, какой-никакой, а все же рабочий.

> и потом я про
>> быстрее почти на 30-40% если оперировать DWORD

Скажите вы меня считаете полным васей или наполовину? С какой радости я должен забесплатно писать или делиться оптимальным кодом поиска?

← →
GuAV © (2004-09-26 03:00) [25]

> сомнительно

зря.
в BP я так и писал.

> Я сам такие доки пишу, опираясь на документацию к процессорам.

однако нужно ещё и учитывать особенности ОС и компилятора.
> Да.. на фоне всего кода это очень серъезное замечание.

первое подвернувшееся.
> С какой радости я должен забесплатно писать или делиться
> оптимальным кодом поиска?

правильно, не стоило ваще этот код выкладывать.
свой я уже писал, но он сейчас не доступен а то я бы выложил.

> Жаль только у вас будет пример перед глазами, какой-никакой,
> а все же рабочий.

в случае реализации этого алгоритма я предпочёл бы писать сам а не видеть этот пример, потому что алгоритм достаточно простой, а код достаточно плохой.

← →
GuAV © (2004-09-26 03:03) [26]

> Mov Al , AChar

> Mov ECx, Size

это уже говорит о недостатке опыта в BASM

← →
GuAV © (2004-09-26 03:07) [27]

> Mov Result, EAx // This is odd when optimization is on

и это тоже.
этот код не был изначально для 32bit delphi и был тупо скопирован.

> BlockRead(F, Buffer, 1000000, Result);

лучше подобрать кратное степени 2
> Function CompareStrings(Constant:String; Buffer:PBuffer):Boolean;
> Var I:Integer;
> Begin
> Result := True;
> I := 1;
> While Result and (I<Length(Constant)) Do
> Begin
> Inc(I);
> Result := Result and (Constant[i] = Chr(Buffer^[i-2]));
> End;
> End;

это вообще нужно было на BASM.

← →
GuAV © (2004-09-26 03:10) [28]

> Cld

и это лишнее. эот флаг сохраняется неустановленным.
посмотри SysUtils для примеров.

> однако нужно ещё и учитывать особенности ОС и компилятора.

учтены особенности как ОС так и компилятора, причем для обоих опций компилятора с оптимизацией и без. Найдете?

> свой я уже писал, но он сейчас не доступен а то я бы выложил.

голословное утверждение.

> в случае реализации этого алгоритма я предпочёл бы писать сам а не видеть этот пример, потому что алгоритм достаточно простой, а код достаточно плохой.

Учитывая что и алгоритм[1], и код[15] были предложены мной, записано на личный счет в качестве необоснованного оскорбления.

> Mov Result, EAx // This is odd when optimization is on

>и это тоже.
>этот код не был изначально для 32bit delphi и был тупо скопирован.

i ignore this allegation due to your age dear friend. i"ve wrote the comment in english because the simple fact is well known, copy-paste doesnt work between Delphi editor and the editor here.

>> BlockRead(F, Buffer, 1000000, Result);
> лучше подобрать кратное степени 2

абсолютно без разницы, ОС при следующем обращении к файлу вытянет данные из кеша. На скорость никак не влияет.

> GuAV © (26.09.04 03:10) [28]

Это сугубо ваше мнение, флаг может измениться, а может и не измениться, зависит от ветра в поле. Обычно, никто не следит за содержимым флага D поэтому нелишней предосторожностью будет его сброс.

>> Function CompareStrings(Constant:String; Buffer:PBuffer):Boolean;
> это вообще нужно было на BASM.
Это на чем захотел на том и сделал, на скорость эта процедура практически не влияет. А автору вопроса думаю будет понятней на Delphi.

> это уже говорит о недостатке опыта в BASM
фраза вызывает улыбку

2 GuAV, когда разберетесь в коде приведенном ниже, и скажете где он может использоваться, тогда будем с вами говорить об опыте. А так кроме, голословных утверждений и оскорблений я от вас пока ничего не услышал.

Start: Db 0B8H SubEnable: Db 2dH Db 3eH Db 0EBH Db 0FCH Ret

Я проанализировал варинт работы с DWORD, ничего он не ускорит, наоборот замедлит поиск.

Спросите почему?

ответ прост, нам придется сдвигаться на 1 байт постоянно, так как строка может начинаться не обязательно точно на границе DWORD. строка может быть смещена на 1,2 или 3 байта от начала границы DWORD. следовательно придется отказаться от быстрой функции REPNE SCAS и код будет примерно таким:

@@Instead_RepneStos: SHL EAx, 8 LODSB CMP EAx, EDx ; EDx - DWORD constant Jnz @@Instead_RepneScas

Что мы выиграем?
1. Отпадает надобность проверки первых четырех символов в функции CompareString, для маленьких строк возможно ускорение на 2-3%.

Что мы проигрываем?
1. Нельзя найти строки состоящие из 3-х и менее символов.
2. для больших строк - замедление на 15-25% т.к. одна циклическая команда заменена 3-мя! (в основном цикле поиска), причем одна из команд - команда перехода (медленная по определению, т.к. вызывает сброс конвеера).
3. Функция CharPos увеличится, т.к. придется рассмотреть частный случай начальной загрузки первого DWORD"а, что приведет к заметному замедлению если в файле встречается много одинаковых подстрок, равных первому DWORD искомой строки.

А теперь взвесим все "ЗА" и "ПРОТИВ" и придем к логическому выводу: [1] - один из самых быстрых алгоритмов поиска для Intel x86 (если не самый быстрый). Код [15] требует оптимизации, но думаю выбрасывать байты из работающей программы, проще чем ковыряться с неработающей.

Так что - наздоровье Dimaxx, пользуйтесь

> // This is odd when optimization is on

Это нафиг не нужно ни при оптимизации ни без неё

> флаг может измениться, а может и не измениться, зависит
> от ветра в поле.

подпрограммы на Дельфи должны следить за тем что флаг не установовлен. т.е. ставишь - будб добр збрасывай. см. SysUtils - там видно моного процедур которые расссчитывают на то что он не установлен.

> 1. Нельзя найти строки состоящие из 3-х и менее символов.

для них оставить SCASB

> строка может быть смещена на 1,2 или 3 байта от начала границы
> DWORD. следовательно придется отказаться от быстрой функции
> REPNE SCAS

перебор вариантов можно оставить в CompareStrings

> Это на чем захотел на том и сделал, на скорость эта процедура
> практически не влияет. А автору вопроса думаю будет понятней
> на Delphi.

в случае достаточно длинной строки это может выбросить все прелести asm кода.

> для обоих опций компилятора с оптимизацией и без. Найдете?

вы про
Mov Al , AChar

для asm подпрограмм оптимизация не влияет, параметры всё равно через регистры.

> вначале [31]

сначала это
MOV ax, 03E2Dh
JMP @SubEnable,

потом
sub ax, 0EB3Eh
cld

я не сомневаюсь что Вы знаете asm, но с BASM у Вас похоже трабл

PS: Хотите оптимальную процедуру CharPos - пожалуйста:
но только c оговорками
{этот код работает только при компиляции на D7 с включенной оптимизацией} Function CharPos(AChar:Char; Buffer:Pointer; Size:Integer):Integer;Assembler; Asm Xchg EDx, EDi Push ECx Repne ScasB Pop EAx Jnz @@NotMatch Sub EAx, ECx Xchg EDx, Edi Ret @@NotMatch: Xor EAx, EAx Dec EAx Xchg EDx, Edi End;

>{этот код работает только при компиляции на D7 с включенной оптимизацией}
Для тех кто на бронепоезде, повторяю
для asm подпрограмм оптимизация не влияет, параметры всё равно используется модель register и параметры передаются через регистры.

однако это уже выглядит лучше, хотя не проверяю.

Defunct © (26.09.04 15:23) [37] Вероятно Вы имеете ввиду, что вход может быть и сразу в SubEnable?
И код применим как элемент "защиты", где смысл в том что одни и те же бинарные даммые соответствуют разным инструкциям, что может вызвать затруднения при дизасеблировании?

я не разбираюсь в этом, может это и зачем-то надо.

Но по части обычного использованияассемблера в Дельфи
> с BASM у Вас похоже трабл

> всё равно используется модель register и параметры передаются
> через регистры.

по умолчанию, разумеется, можно явно написать pascal

Const MaxBufferSize = 1000000; Type TBuffer = Array[0..MaxBufferSize-1] of byte; PBuffer = ^TBuffer; Function CharPos(AChar:Char; Buffer:Pointer; Size:Integer):Integer;Assembler; Asm Xchg EDx, EDi Push ECx Repne ScasB Pop EAx Jnz @@NotMatch Sub EAx, ECx Xchg EDx, Edi Ret @@NotMatch: Xor EAx, EAx Dec EAx Xchg EDx, Edi End; Function CompareStrings(Constant, Buffer:Pointer; BufSize:Integer):Boolean;Assembler; Asm Push EDi Push ESi Xchg EAx, ESi Mov EDi, EDx Xchg EDx, EBx Mov EBx, [ESi-4] Dec EBx @@Scan: Mov Al, [ESi] Xchg EDx, EDi Push ECx Call CharPos Pop ECx Xchg EDx, EDi Sub ECx,EAx Cmp ECx,EBx Jb @@Exit_False Cmp EAx, 0FFFFFFFFh Jnz @@CompareNextChars @@Exit_False: Pop ESi Pop EDi Xchg EDx, Ebx Xor EAx,EAx Ret @@CompareNextChars: Push ECx Mov ECx,EBx Push ESi Inc ESi Push EDi //Здесь можно предусмотреть пропуск просмотренных символов Repe CmpsB Pop EDi //будет работать немножко быстрее Pop ESi Pop ECx Jnz @@Scan Pop ESi Pop EDi Xchg EDx, Ebx Xor EAx,EAx Dec EAx End; Function LoadBuffer(var Buffer; var F:File; var SeekPos:Int64):Integer; Begin Seek(F, SeekPos); BlockRead(F, Buffer, MaxBufferSize, Result); SeekPos := FilePos(F); End; Function ConstantExists(FileName, Constant: String):Boolean; Var Buffer : PBuffer; SeekPos : Int64; F : File; BufSize : Integer; Begin Result := False; If FileExists(FileName) Then Begin SeekPos := 0; New(Buffer); Assign(F, FileName); Reset(F,1); Repeat BufSize := LoadBuffer(Buffer^, F, SeekPos); Result := CompareStrings(@Constant[1], Buffer, BufSize); SeekPos := SeekPos - Length(Constant); Until Result Or (BufSize<MaxBufferSize); Close(F); Dispose(Buffer); End; End;

Вот до чего мне удалось оптимизировать код[15], здесь учтен выход строки за границу буфера.

GuAV © (26.09.04 16:59) [38]
Вместо "наездов" на код, за то же время могли бы его оптимизировать сами, или написать свой.

>И код применим как элемент "защиты", где смысл в том что одни и те же бинарные даммые соответствуют разным инструкциям, что может вызвать затруднения при дизасеблировании?

почти правильно, за исключением того, что у этого кода есть строго определенное назначение (попросту его больше не для чего применять кроме как ....). Я хотел от вас услышать именно это назначение.

Поиск в бинарном файле Найти похожие ветки