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

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

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 18:54) [41]

лучше.

я ещё могу немного оптимизировать, самую малость...

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;
так оно корректнее а на произв-ть не влияет, т.к. только один раз делается.
> Вместо "наездов" на код, за то же время могли бы его оптимизировать
> сами, или написать свой.

понимаете счас у меня нет дельфи...

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

ну не знаю. сказал же, что в Вашей области не разбираюсь...
этот код в прочем не относится к сабжу.
в яндексе искать в падлу, обзаву его "ДизАсмНаёмка" :)

← →
GuAV © (2004-09-26 18:58) [42]

finally Close(F); end; finally

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

GuAV © (26.09.04 18:54) [41, 42]

Поправки принимаются все кроме:

> Const MaxBufferSize = 1048576 // привязывайсь к физ размеру кластера и страницы памяти...

Лучше уже привязываться к объему L2 кеша процессора, а если нет тогда все равно кратно двум или нет. К кластеру привязываться смысла нет - в ОС есть механизм упреждающего чтения.

> да и не надо FileExists(FileName), всё равно он может существовать и не открыться.

Файл может и не существовать, проверка будет нелишней.

← →
GuAV © (2004-09-26 19:52) [44]

> Лучше уже привязываться к объему L2 кеша процессора, а если
> нет тогда все равно кратно двум или нет. К кластеру привязываться
> смысла нет - в ОС есть механизм упреждающего чтения.

ок принято.

> Файл может и не существовать, проверка будет нелишней.

Если процедура написана по правильному, т.е. чтение в блоке try то в ситуации когда файл не существует, исключение подумется при первом чтении.

Возможна ситуация когда файл существует но почему-то не читается.

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

по части оскорблений - мне не понравился код из за использование сег. регистров, также бросилось в глаза Mov Result, EAx. N.к. я знаю что это всё ни нужно, я усомнился в качесте кода, Вы сослались на доку [22], я тоже [23], после чего в [24] - первое оскорбление в мой адрес (необоснованный "наезд"). в [26] же я усомнившись в Вашем опыте привел свой аргумент который Вы не опровергли.
ну то есть что я хочу сказать: требуй вежливости - будь вежлив сам.

← →
GuAV © (2004-09-26 19:59) [45]

> Если процедура написана по правильному, т.е. чтение в блоке
> try то в ситуации когда файл не существует, исключение подумется
> при первом чтении.

разумеется, оно подымется в любом случае.
просто оно будет правильно обработано,
> Если процедура написана по правильному
.

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

← →
Defunct © (2004-09-26 20:12) [46]

> Если процедура написана по правильному, т.е. чтение в блоке try то в ситуации когда файл не существует, исключение подумется при первом чтении.

Кто-то, конечно же это были не вы, а ваш двойник, в смежной ветке с заголовком New() сказал золотую фразу:

GuAV © (26.09.04 02:01) [50]
> т.е. способ try..except - пример неправильного написания программы.

Вы сами себе противоречите.

PS: пора заканчивать, уже над нами наверно весь форум смеется "hot china guys", ICQ у меня указан в анкете.

← →
Sergey_Masloff (2004-09-26 20:18) [47]

>уже над нами наверно весь форум смеется
Если вы когда меряетесь еще и код будете продолжать приводить то лучше здесь продолжайте. Неожиданно интересная ветка оказалась...
В любом случае спасибо. Интерес конечно чисто академический но читать (не ругань а код и комментарии) мне например было очень интересно. Так что в любом случае спасибо ;-)

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

> Неожиданно интересная ветка оказалась...

поэтому продолжаю здесь

Defunct © (26.09.04 20:12) [46]

Я имел ввиду там способ проверки валидности указателя через try... except, который неправильный. тут я предлагаю использовать конструкцию try..finally и хранить исключения для вызавашего кода. Это вещи разные, имхо даже противоположные. Вызывающая подпрограмма не должна также использовать try..except в том виде в каком Вы предложили её в той ветке.

> (не ругань а код и комментарии) мне например было очень
> интересно.

:) мне тоже особенно
Mov Result, EAx // This is odd when optimization is on
т.к. любая функция Delphi, возвращающая Integer возвращает его в EAX. (кроме D1, где в AX)
<off>имхо неверный коментарий более грубая ошибка чем неверный код</off>

по поводу развития мысли кода:

DWORD вариант я пока не отмёл, т.к. можно не сдвигать строку, а пройти буфер 4 раза с разными младшими битами ESi и EDi.

Даже не было опровержение метода предолженного default (c)

Сейчас поставил Delphi, попробую этот код в работе...

> уже над нами наверно весь форум смеется

я кажется не говорю ничего смешного.
моё упорство может показаться кому-то смешным, ну вот такой я есть.

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

> ESi и EDi.

только EDi точнее.

← →
Dimaxx (2004-09-26 22:13) [50]

Только отлучился, а тут уже темку раздули... :-)

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

> Я имел ввиду там способ проверки валидности указателя через try... except, который неправильный.

Так то были вы? :)
Извините, но мне так понравилась эта фраза, что я ее еще раз повторю.

GuAV © (26.09.04 02:01) [50]
> т.е. способ try..except - пример неправильного написания программы.

> DWORD вариант я пока не отмёл, т.к. можно не сдвигать строку, а пройти буфер 4 раза с разными младшими битами ESi и EDi.

Удачи. потестируем ваше решение, смотрится хорошо но существенного выиграша в скрости не даст, см [32] пункты "что мы проиграем? - 1,3" плюс добавляется еще чаcтный случай сброса поиска.

Mov Result, EAx // This is odd when optimization is on
т.к. любая функция Delphi, возвращающая Integer возвращает его в EAX. (кроме D1, где в AX)
<off>имхо неверный коментарий более грубая ошибка чем неверный код</off>

Вы кстатити как поняли коментарий?
Там написано "при оптимизации - это лишнее"
далее смотрите пост [16], где я отмечаю, что код требует оптимизации, жаль автору такая интересная задачка недосталась.

Function ...;assembler;safecall;
Function ...;assembler;pascal;
Мало ли что, может захочется в DLLку вставить этот код и использоваться safecall. Кстати, вполне актуальное место для приведенного [15] кода.

> Даже не было опровержение метода предолженного default (c)
Какого метода? Ссылку давайте, сыт погорло голословными утверждениями.

> Сейчас поставил Delphi, попробую этот код в работе...
аж дух затаил, жду с нетерпением что скажет Guru AV.

← →
GuAV © (2004-09-26 23:06) [52]

Defunct © (26.09.04 22:22) [51]

Про safecall может и так, но это было бы не правильное её применение.

т.к. любая функция Delphi, возвращающая Integer возвращает его в EAX

{$O-} {$OPTIMIZATION OFF} function Return555: Integer; stdcall; assembler; // или pascal анаолгично asm MOV EAX, 555; end; procedure TForm1.FormCreate(Sender: TObject); begin Caption:=IntToStr(Return555); end;

> Guru AV

:) Это идея.

← →
Anatoly Podgoretsky © (2004-09-26 23:21) [53]

GuAV © (26.09.04 23:06) [52]
Guru AV

Вопрос в толковании

← →
GuAV © (2004-09-26 23:25) [54]

<off>

> Вопрос в толковании

да, я про 216 :)
</off>

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

любителям стрёмного асм-кода посвящается...
Function CharPos:Integer;Assembler; { in: AL: Char EDI: Pointer to buffer ECX: Size of buffer out: EAX: Result ECX: Size of buffer } Asm // Xchg EDx, EDi Push ECx Repne ScasB MOV EAX, [ESP] // Pop EAx Jnz @@NotMatch Sub EAx, ECx // Xchg EDx, Edi POP ECX Ret @@NotMatch: Xor EAx, EAx Dec EAx // Xchg EDx, Edi POP ECX End; Function CompareStrings(Constant: string; 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

← →
Defunct © (2004-09-26 23:33) [56]

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

С моей точки зрения, фукция должна игнорировать сей факт, ее назначение поиск строки в файле. А раз нет файла, то нет и строки, все четко. Не надо никаких исключений, от них только программа захламляется.

PS: Как код?
сравните оба по скорости, [15] и [40] разницы практически нет.

PPS: to GuruAV, прочитайте [10] сверьте время [10] и [15] сколько ушло на реализацию алгоритма (писал с нуля), посмотрите цель написания кода[10] и прочитайте [16]. теперь скажите, как бы на моем месте вы среагировали на [21].

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

← →
Defunct © (2004-09-26 23:41) [57]

GuAV © (26.09.04 23:26) [55]

Вот, давно пора было.
Это из серии анекдотов про Илью Муромца, "Как трезвый так золотой человек, как выпьет ну просто хавайся"

Любителям стремного кода надо еще добавить флаг C вместо проверки EAX на -1

Asm // Xchg EDx, EDi Push ECx Repne ScasB MOV EAX, [ESP] // Pop EAx Jnz @@NotMatch Sub EAx, ECx // Xchg EDx, Edi POP ECX CLC Ret @@NotMatch: // Xor EAx, EAx // Dec EAx STC // Xchg EDx, Edi POP ECX End; Call CharPos // Pop ECx // Xchg EDx, EDi Jnc @@CompareNextChars Sub ECx,EAx Cmp ECx,EBx Jb @@Exit_False // Cmp EAx, 0FFFFFFFFh // Jnz @@CompareNextChars

Естессно оптимизировать мона и дальше

← →
GuAV © (2004-09-26 23:47) [58]

> С моей точки зрения, фукция должна игнорировать сей факт,
> ее назначение поиск строки в файле. А раз нет файла, то
> нет и строки, все четко. Не надо никаких исключений, от
> них только программа захламляется.

Не согласен. Исключения полезны, особенно если умеешь с ними обращася.

> Естессно оптимизировать мона и дальше

Да.

Вопросы по коду (что я не понял):

1. Как обрабатывается буфер нулевой длины ?
2. (самое интересное) как обрабатывается ситуация когда часть строки в одном буфере, часть в другом ?
3. Зачем танцы с SeekPos учитывая что строка одна ?

← →
GuAV © (2004-09-26 23:48) [59]

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

Вот тут безоговорочно согласен!

← →
GuAV © (2004-09-26 23:59) [60]

> PPS: to GuruAV, прочитайте [10] сверьте время [10] и [15]
> сколько ушло на реализацию алгоритма (писал с нуля), посмотрите
> цель написания кода[10] и прочитайте [16]. теперь скажите,
> как бы на моем месте вы среагировали на [21].

Ок. Я Вас понял. Поймите и меня: мне код в [15] показался стрёмным именно из-за [21] [26] и особенно [27] в начале. Из-за этго показалось, что писал чайник. Я высказал свои опасения в [21].

зы: перерегистрироваться не хочу, лучше воспользуюсь полем реальное имя.

← →
Defunct © (2004-09-27 00:02) [61]

GuAV © (26.09.04 23:47) [58]

Ха, наконец-то интересный разговор.

2. (самое интересное) как обрабатывается ситуация когда часть строки в одном буфере, часть в другом ?

вот ответ:
.. Sub ECx,EAx Cmp ECx,EBx Jb @@Exit_False .. .. SeekPos := SeekPos - Length(Constant); ..

3. Зачем танцы с SeekPos учитывая что строка одна ?
Думаю это отпадает после ответа на 2.

1. Как обрабатывается буфер нулевой длины ?
Не учтено. проверка должна быть в CharPos.
В измененном варинте добавляю проверку:

Asm // Xchg EDx, EDi Push ECx Test ECx,ECx Jz @@NotMatch Repne ScasB MOV EAX, [ESP] // Pop EAx Jnz @@NotMatch Sub EAx, ECx // Xchg EDx, Edi POP ECX CLC Ret @@NotMatch: // Xor EAx, EAx // Dec EAx STC // Xchg EDx, Edi POP ECX End;

Это было действительно дельное замечание. спасибо.

← →
Defunct © (2004-09-27 00:07) [62]

>Не учтено. проверка должна быть в CharPos. >В измененном варинте добавляю проверку:

Test ECx,ECx Jz @@NotMatch

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

If BufSize> Length(Constant) Then Result := CompareStrings(@Constant[1], Buffer, BufSize);

← →
Defunct © (2004-09-27 00:23) [63]

Вот и закончились выходные...

2 Dimaxx спасибо за вопрос

← →
GuAV © (2004-09-27 00:30) [64]

Defunct © (27.09.04 00:02) [61]

понял.
а попробуйте не выносить LoadBuffer, окажется всё проще:
Repeat BlockRead(F, Buffer^, MaxBufferSize, BufSize); Result := CompareStrings(Constant, Buffer, BufSize); Seek(F, FilePos(F) - Length(Constant)); Until Result Or (BufSize<MaxBufferSize);

в своём подобном коде на pascal я просто запоминал позицию в искомой строке.
дело в том что он был не на асм. а в этом я искал того же.

> Вот и закончились выходные...

а у нас ещё полчаса выходных.

← →
GuAV © (2004-09-27 00:40) [65]

:)
4. как обрабатывается строка длинее MaxBufferSize ?

← →
Defunct © (2004-09-27 01:51) [66]

GuAV © (27.09.04 00:30) [64]

Дык, все неточности, что вы видите - исправьте. Полную версию вашего оптимизированного кода выложете.

В чужем глазу соринку видим, в своем не заметим и бревна(С) народная мудрость. Так что я нисколько не сомневаюсь, что вы в состоянии значительно улучшить код [40]

> а попробуйте не выносить LoadBuffer, окажется всё проще
Это тому яркое подтверждение, я туда и не посмотрел бы.

> 4. как обрабатывается строка длинее MaxBufferSize ?
с помощью Norton FileCompare или как оно там называется ;)

Зы, а код этот думаю для многих пригодится, так как тема быстрого поиска весьма актуальна. может стоит в кладовку выложить?

← →
Defunct © (2004-09-27 02:53) [67]

Тут после всего залез в модуль System функция _Pos (для ShortString) работает по алгоритму [1] (если отбросить часть которая относится к файлам).

← →
GuAV © (2004-09-27 13:01) [68]

изучил код.
счас выложу оптимизированный.
сначала кометарий об ошибке
> Xor EAx,EAx
> Dec EAx
> End;

Xor EAx,EAx
INC EAX
end;

дело в том, что ord(True) равно 1. Даже есть код, например в Dialogs.pas который использует конструкцию
const C: array[Boolean] of DWORD = (A, B);
естественно он не будет готов обработать -1.

Const MaxBufferSize = 1024*1024; Type TBuffer = Array[0..MaxBufferSize-1] of byte; PBuffer = ^TBuffer; Function CompareStrings(const Constant: string; Buffer: Pointer; BufSize: Integer): Boolean; Assembler; Asm Push EDi Push ESi {Xchg EAx, ESi} MOV ESI, EAX // Eax is not preserved anyway Mov EDi, EDx { EDx is not used to pass buffer pointer anymore Hehce we can use EDx here and keep EBx unused } {Xchg EDx, EBx} {Mov EBx, [ESi-4]} MOV EDX, [ESI-4] {Dec EBx} DEC EDX @@Scan: Mov Al, [ESi] {Xchg EDx, EDi} {Push ECx} {Xchg EDx, EDi} Push ECx Repne ScasB JNE @@NotMatch { as we"ve moved CharPos here we can now jump almost right to Exit_False } {Pop EAx} {Jnz @@NotMatch} MOV EAX, [ESP] Sub EAx, ECx {Xchg EDx, Edi} {Ret} {JMP @@ScanDone @@NotMatch: Xor EAx, EAx Dec EAx } {Xchg EDx, Edi} @@ScanDone: Pop ECx {Xchg EDx, EDi} Sub ECx,EAx Cmp ECx, EDX Jb @@Exit_False { Cmp EAx, 0FFFFFFFFh Jnz @@CompareNextChars } @@NotMatch: POP ECX @@Exit_False: Pop ESi Pop EDi {Xchg EDx, Ebx} Xor EAx,EAx Ret @@CompareNextChars: Push ECx Mov ECx, EDX 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 INC EAx End; Function ConstantExists(FileName, Constant: String):Boolean; Var Buffer : PBuffer; F : File; BufSize : Integer; Begin Result := False; New(Buffer); try Assign(F, FileName); Reset(F,1); try Repeat BlockRead(F, Buffer^, MaxBufferSize, BufSize); Result := CompareStrings(Constant, Buffer, BufSize); Seek(F, FilePos(F) - Length(Constant)); Until Result Or (BufSize<MaxBufferSize); finally Close(F); end; finally Dispose(Buffer); end; End;

> { Cmp EAx, 0FFFFFFFFh
> Jnz @@CompareNextChars }

случайно закоментировал, не надо кометировать это
Cmp EAx, 0FFFFFFFFh
Jnz @@CompareNextChars

и ещё

Repeat
BlockRead(F, Buffer^, MaxBufferSize, BufSize);
if Bufsize=0 then Exit;
Result := CompareStrings(Constant, Buffer, BufSize);
Seek(F, FilePos(F) - Length(Constant));
Until Result Or (BufSize<MaxBufferSize);

Код [69] не рабочий.

Project .... failed with message "privileged instruction at address ..." process stopped use RUN to continue

Вашу идею с объединением функций подхватил, сейчас попробую сделать рабочим.

Function CompareStrings(const Constant: string; Buffer: Pointer; BufSize: Integer): Boolean; Assembler; Asm Push EDi Push ESi Push EBx MOV ESI, EAX // ESi pointer to constant Mov EDi, EDx // EDi pointer to buffer Mov EBX, [ESI-4] Dec EBX Dec EBx // EBx - length of the constant w/o 1st and last chars Mov Al, [ESi] // Store first char of the constant in AL Mov Ah, [ESi+EBx+1]// Store last char of the constant in AH Mov EDx,ECx // EDx - Stored residual buffer size @@Scan: Repne ScasB JNE @@Exit_False // no 1st char of the constant found = exit_false Mov EDx, ECx // store new residual buffer size Cmp EDx, EBx // constant still can be settled in buffer Ja @@CheckLastChar // no - exit with false result @@Exit_False: Pop EBx Pop ESi Pop EDi {Xchg EDx, Ebx} Xor EAx,EAx // False = (0), check delphi help for more info Ret @@CheckLastChar: // as proposed in Boyer-Mur alhorithm Cmp Ah, [EDi+EBx] // check found substring with last char of the constant Jnz @@Scan // not match - continue searching @@CompareWholeString: Mov ECx, Ebx // ECx - constant chars amount Push ESi // store pointer to constant Inc ESi Push EDi //Çäåñü ìîæíî ïðåäóñìîòðåòü ïðîïóñê ïðîñìîòðåííûõ ñèìâîëîâ Repe CmpsB Pop EDi //áóäåò ðàáîòàòü íåìíîæêî áûñòðåå Pop ESi Mov ECx, EDx // restore residual buffer size to ECx Jnz @@Scan Pop EBx Pop ESi Pop EDi Xor EAx,EAx Dec EAx // True = (-1) check delphi help for more info End; Function ConstantExists(FileName, Constant: String):Boolean; Var Buffer : PBuffer; F : File; BufSize : Integer; Begin Result := False; New(Buffer); try Assign(F, FileName); Reset(F,1); try Repeat BlockRead(F, Buffer^, MaxBufferSize, BufSize); If BufSize< Length(Constant) Then Exit; Result := CompareStrings(Constant, Buffer, BufSize); Seek(F, FilePos(F) - Length(Constant)); Until Result Or (BufSize<MaxBufferSize); finally Close(F); end; finally Dispose(Buffer); end; End;

Немножко модифицировал алгоритм поиска взял проверку последнего символа из алгоритма Бойера-Мура, работает быстрее кода [40] если в буфере встречается много одинаковых "обрезков" искомой строки.

Function CompareStrings(const Constant: string; Buffer: Pointer; BufSize: Integer): Boolean; Assembler; Asm Push EDi Push ESi Push EBx MOV ESI, EAX // ESi pointer to constant Mov EDi, EDx // EDi pointer to buffer Mov EBX, [ESI-4] Dec EBX Mov Ah, [EBx+ESi] // Store last char of the constant in AH Dec EBx // EBx - length of the constant w/o 1st and last chars Mov Al, [ESi] // Store first char of the constant in AL Mov EDx,ECx // EDx - Stored residual buffer size @@Scan: Repne ScasB JNE @@Exit_False // no 1st char of the constant found = exit_false Mov EDx, ECx // store new residual buffer size Cmp EDx, EBx // constant still can be settled in buffer Ja @@CheckLastChar // no - exit with false result @@Exit_False: Pop EBx Pop ESi Pop EDi Xor EAx,EAx // False = (0), check delphi help for more info Ret @@CheckLastChar: // as proposed in Boyer-Mur alhorithm Cmp Ah, [EDi+EBx] // check found substring with last char of the constant Jnz @@Scan // not match - continue searching @@CompareWholeString: Mov ECx, Ebx // ECx - constant chars amount Push ESi // store pointer to constant Inc ESi Push EDi // Repe CmpsB Pop EDi // Pop ESi Mov ECx, EDx // restore residual buffer size to ECx Jnz @@Scan Pop EBx Pop ESi Pop EDi Xor EAx,EAx Dec EAx // True = (-1) check delphi help for more info End;

Вот, теперь вроде бы ничего лишнего нет, кроме пары Push/Pop, которая четно говоря мне там не нравится..

Эта функция работает почти в два раза быстрее чем стандартная функция Pos из модуля SYSTEM Delphi. За счет того, что в основном цикле поиска нет ни одного обращения к стеку, и минимизированы обращения к памяти.

Function ConstantPos(const Constant: string; Buffer: Pointer; BufSize: Integer): Integer; Assembler; Asm Push EDi Push ESi Push EBx Push EBp Push ECx // store total buffer size for later calculation pos MOV ESI, EAX // ESi pointer to constant Mov EDi, EDx // EDi pointer to buffer Mov EBX, [ESI-4] Dec EBX Mov Ah, [ESi+EBx] // Store last char of the constant in AH Dec EBx // EBx - length of the constant w/o 1st and last chars Mov Al, [ESi] // Store first char of the constant in AL Mov EDx,ECx // EDx - Stored residual buffer size Inc ESi Mov EBp, ESi // EBp - stored pointer to 2nd char of constant @@Scan: Repne ScasB JNE @@Exit_False // no 1st char of the constant found = exit_false Mov EDx, ECx // store new residual buffer size Cmp EDx, EBx // constant still can be settled in buffer Ja @@CheckLastChar // no - exit with false result @@Exit_False: Pop EAx Xor EAx,EAx // False = (0), check delphi help for more info Dec EAx Jmp @@Leave_Proc @@CheckLastChar: // as proposed in Boyer-Mur alhorithm Cmp Ah, [EDi+EBx] // check found substring with last char of the constant Jnz @@Scan // not match - continue searching @@CompareWholeString: Mov ECx, Ebx // ECx - constant chars amount Repe CmpsB Jz @@Constant_Exists Mov ESi, EBp // restore pointer to 2nd char of constant Add EDx, ECx Sub EDx, EBx // correct residual buffer size Mov ECx, EDx // restore residual buffer size to ECx Jnz @@Scan @@Constant_Exists: Pop EAx Sub EAx, EDx @@Leave_Proc: Pop EBp Pop EBx Pop ESi Pop EDi End;

Использовать приминительно к сабжу можно так:

Function ConstantExists(FileName, Constant: String):Integer; Var Buffer : PBuffer; F : File; BufSize : Integer; Begin Result := -1; New(Buffer); try POs Assign(F, FileName); Reset(F,1); try Repeat BlockRead(F, Buffer^, MaxBufferSize, BufSize); If BufSize< Length(Constant) Then Exit; // Result := CompareStrings(Constant, Buffer, BufSize); Result := ConstantPos(Constant, Buffer, BufSize); Seek(F, FilePos(F) - Length(Constant)); Until (Result>0) Or (BufSize<MaxBufferSize); finally Close(F); end; finally Dispose(Buffer); end; End;

Забыл добавить описание:

Function ConstantPos(const Constant: string; Buffer: Pointer; BufSize: Integer): Integer; Assembler; { -> EAx - указатель на строку поиска (константа) EDx - указатель на буфер, в котором требуется найти строку поиска ECx - длина буфера <- EAx - Позиция строки поиска в буфере (-1) если строки в буфере нет }

результат поиска строки "01wbcb" в файле gladiator.avi (726Mb) с учетом что такой строки в файле нет, а есть множество строк "01wb" составил - 22.34 сек, при повторном запуске - 13.71 сек. проверял на компе с 512Mb памяти (т.е. файл не мог полностью разместиться в кеше).

> Xor EAx,EAx
> Dec EAx // True = (-1) check delphi help for more
> info

заблуждаетесь.
F1 - Boolean types

> Repe CmpsB

Repe CmpsD, а CmpsD - остаток

из справки:
Boolean ByteBool, WordBool, LongBool
False < True False <> True
Ord(False) = 0 Ord(False) = 0
Ord(True) = 1 Ord(True) <> 0
Succ(False) = True Succ(False) = True
Pred(True) = False Pred(False) = True

> Код [69] не рабочий.
>
И после [70] ?

GuAV © (27.09.04 21:38) [77]
> Repe CmpsD, а CmpsB - остаток

Уже рассматривал, этот вариант. Мне не хватает одного РОНа, чтобы сделать с CmpsD. Приходится юзать стек, значительно проиграем на коротких строках. либо придется использовать регисты MM0-MMX, тада возможен, как тут любят выражаться, "гимор" если в программе была арифметика с плавающей точкой.

> заблуждаетесь.
Возможно, а возможно и нет, читал совсем недавно 1-2 месяца назад, в справке по Delphi тока не помню где именно (удивлялся). Там еще были примеры с приведением типов Integer -> Boolean, Boolean -> Integer, Boolean -> Byte, Byte -> Boolean, и вот осело в памяти $FFFFFFFF = True. Так или иначе, это не имеет значения, т.к. проверка на True все равно делается командой Test(будь там -1 или +1 результат не изменится, а по скорости Dec и Inc идентичны)

Test Reg,Reg
Jnz @@True

PS: могу попробовать сделать поиск с использованием MMX если найду время.

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