| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Поиск в бинарном файле [D5, WinXP]
Dimaxx © (2004-09-24 23:32:00)
Страницы: < 1 2 ... 5 6 7 8 9 10 11 12 13 14 >
Сабж. Нужен алгоритм действительно быстрого поиска последовательности байт любой длины в файлах любого размера (до гигабайта). Читать кусками по-деревенски не катит. Раньше у меня был алгоритм, но с падением Фуджика все пропало.
GuAV (2004-09-26 19:52:00) [221]
> Лучше уже привязываться к объему L2 кеша процессора, а если
> нет тогда все равно кратно двум или нет. К кластеру привязываться
> смысла нет - в ОС есть механизм упреждающего чтения.
ок принято.
> Файл может и не существовать, проверка будет нелишней.
Если процедура написана по правильному, т.е. чтение в блоке try то в ситуации когда файл не существует, исключение подумется при первом чтении.
Возможна ситуация когда файл существует но почему-то не читается.
Код же имхо должен работать быстро в случае нормальной ситуации, следует оптимизировать этот случай даже за счет увеличения времени обработки ненормальной.
по части оскорблений - мне не понравился код из за использование сег. регистров, также бросилось в глаза Mov Result, EAx. N.к. я знаю что это всё ни нужно, я усомнился в качесте кода, Вы сослались на доку [22], я тоже [23], после чего в [24] - первое оскорбление в мой адрес (необоснованный "наезд"). в [26] же я усомнившись в Вашем опыте привел свой аргумент который Вы не опровергли.
ну то есть что я хочу сказать: требуй вежливости - будь вежлив сам.
Defunct (2004-09-26 19:18:00) [222]GuAV © (26.09.04 18:54) [41, 42]
Поправки принимаются все кроме:
> Const MaxBufferSize = 1048576 // привязывайсь к физ размеру кластера и страницы памяти...
Лучше уже привязываться к объему L2 кеша процессора, а если нет тогда все равно кратно двум или нет. К кластеру привязываться смысла нет - в ОС есть механизм упреждающего чтения.
> да и не надо FileExists(FileName), всё равно он может существовать и не открыться.
Файл может и не существовать, проверка будет нелишней.
GuAV (2004-09-26 18:58:00) [223]
finally
Close(F);
end;
finally
GuAV (2004-09-26 18:54:00) [224]лучше.
я ещё могу немного оптимизировать, самую малость...
CompareStrings(const Constant: string; Buffer ...и при вызове соотв
CompareStrings(Constant, ...
это уберет немного лишнего кода в месте вызова.
Const MaxBufferSize = 1048576 // привязывайсь к физ размеру кластера и страницы памяти...
да и не надо FileExists(FileName), всё равно он может существовать и не открыться.
потом так ещё не мешало бы
New(Buffer);
try
Assign(F, FileName);
Reset(F,1);
try
finally
Close(F);
finally
Dispose(Buffer);
end;
так оно корректнее а на произв-ть не влияет, т.к. только один раз делается.
> Вместо "наездов" на код, за то же время могли бы его оптимизировать
> сами, или написать свой.
понимаете счас у меня нет дельфи...
> почти правильно, за исключением того, что у этого кода есть
> строго определенное назначение (попросту его больше не для
> чего применять кроме как ....). Я хотел от вас услышать
> именно это назначение.
ну не знаю. сказал же, что в Вашей области не разбираюсь...
этот код в прочем не относится к сабжу.
в яндексе искать в падлу, обзаву его "ДизАсмНаёмка" :)
Defunct (2004-09-26 17:55:00) [225]
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]
Вместо "наездов" на код, за то же время могли бы его оптимизировать сами, или написать свой.
>И код применим как элемент "защиты", где смысл в том что одни и те же бинарные даммые соответствуют разным инструкциям, что может вызвать затруднения при дизасеблировании?
почти правильно, за исключением того, что у этого кода есть строго определенное назначение (попросту его больше не для чего применять кроме как ....). Я хотел от вас услышать именно это назначение.
GuAV (2004-09-26 17:06:00) [226]
> всё равно используется модель register и параметры передаются
> через регистры.
по умолчанию, разумеется, можно явно написать pascal
GuAV (2004-09-26 16:59:00) [227]>{этот код работает только при компиляции на D7 с включенной оптимизацией}
Для тех кто на бронепоезде, повторяю
для asm подпрограмм оптимизация не влияет, параметры всё равно используется модель register и параметры передаются через регистры.
однако это уже выглядит лучше, хотя не проверяю.
Defunct © (26.09.04 15:23) [37] Вероятно Вы имеете ввиду, что вход может быть и сразу в SubEnable?
И код применим как элемент "защиты", где смысл в том что одни и те же бинарные даммые соответствуют разным инструкциям, что может вызвать затруднения при дизасеблировании?
я не разбираюсь в этом, может это и зачем-то надо.
Но по части обычного использованияассемблера в Дельфи
> с BASM у Вас похоже трабл
Defunct (2004-09-26 15:23:00) [228]GuAV © (26.09.04 14:49) [35]
1. Ответ неверный.
2. Не раскрыта область применения кода.
Defunct (2004-09-26 15:19:00) [229]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;
GuAV (2004-09-26 14:49:00) [230]
> вначале [31]
сначала это
MOV ax, 03E2Dh
JMP @SubEnable,
потом
sub ax, 0EB3Eh
cld
я не сомневаюсь что Вы знаете asm, но с BASM у Вас похоже трабл
Defunct (2004-09-26 14:43:00) [231]GuAV © (26.09.04 13:26) [33]
вначале [31]
GuAV (2004-09-26 13:26:00) [232]
> // This is odd when optimization is on
Это нафиг не нужно ни при оптимизации ни без неё
> флаг может измениться, а может и не измениться, зависит
> от ветра в поле.
подпрограммы на Дельфи должны следить за тем что флаг не установовлен. т.е. ставишь - будб добр збрасывай. см. SysUtils - там видно моного процедур которые расссчитывают на то что он не установлен.
> 1. Нельзя найти строки состоящие из 3-х и менее символов.
для них оставить SCASB
> строка может быть смещена на 1,2 или 3 байта от начала границы
> DWORD. следовательно придется отказаться от быстрой функции
> REPNE SCAS
перебор вариантов можно оставить в CompareStrings
> Это на чем захотел на том и сделал, на скорость эта процедура
> практически не влияет. А автору вопроса думаю будет понятней
> на Delphi.
в случае достаточно длинной строки это может выбросить все прелести asm кода.
> для обоих опций компилятора с оптимизацией и без. Найдете?
вы про
Mov Al , AChar
для asm подпрограмм оптимизация не влияет, параметры всё равно через регистры.
Defunct (2004-09-26 06:09:00) [233]Я проанализировал варинт работы с 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, пользуйтесь
Defunct (2004-09-26 03:49:00) [234]2 GuAV, когда разберетесь в коде приведенном ниже, и скажете где он может использоваться, тогда будем с вами говорить об опыте. А так кроме, голословных утверждений и оскорблений я от вас пока ничего не услышал.
Start:
Db 0B8H
SubEnable:
Db 2dH
Db 3eH
Db 0EBH
Db 0FCH
Ret
Defunct (2004-09-26 03:34:00) [235]> 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
фраза вызывает улыбку
Defunct (2004-09-26 03:18:00) [236]> однако нужно ещё и учитывать особенности ОС и компилятора.
учтены особенности как ОС так и компилятора, причем для обоих опций компилятора с оптимизацией и без. Найдете?
> свой я уже писал, но он сейчас не доступен а то я бы выложил.
голословное утверждение.
> в случае реализации этого алгоритма я предпочёл бы писать сам а не видеть этот пример, потому что алгоритм достаточно простой, а код достаточно плохой.
Учитывая что и алгоритм[1], и код[15] были предложены мной, записано на личный счет в качестве необоснованного оскорбления.
GuAV (2004-09-26 03:10:00) [237]
> Cld
и это лишнее. эот флаг сохраняется неустановленным.
посмотри SysUtils для примеров.
GuAV (2004-09-26 03:07:00) [238]
> 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:03:00) [239]
> Mov Al , AChar
> Mov ECx, Size
это уже говорит о недостатке опыта в BASM
GuAV (2004-09-26 03:00:00) [240]
> сомнительно
зря.
в BP я так и писал.
> Я сам такие доки пишу, опираясь на документацию к процессорам.
однако нужно ещё и учитывать особенности ОС и компилятора.
> Да.. на фоне всего кода это очень серъезное замечание.
первое подвернувшееся.
> С какой радости я должен забесплатно писать или делиться
> оптимальным кодом поиска?
правильно, не стоило ваще этот код выкладывать.
свой я уже писал, но он сейчас не доступен а то я бы выложил.
> Жаль только у вас будет пример перед глазами, какой-никакой,
> а все же рабочий.
в случае реализации этого алгоритма я предпочёл бы писать сам а не видеть этот пример, потому что алгоритм достаточно простой, а код достаточно плохой.
| |
