Форум: "Основная";
Текущий архив: 2004.10.24;
Скачать: [xml.tar.bz2];
Вниз
Поиск в бинарном файле Найти похожие ветки
← →
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 для примеров.
← →
Defunct © (2004-09-26 03:18) [29]> однако нужно ещё и учитывать особенности ОС и компилятора.
учтены особенности как ОС так и компилятора, причем для обоих опций компилятора с оптимизацией и без. Найдете?
> свой я уже писал, но он сейчас не доступен а то я бы выложил.
голословное утверждение.
> в случае реализации этого алгоритма я предпочёл бы писать сам а не видеть этот пример, потому что алгоритм достаточно простой, а код достаточно плохой.
Учитывая что и алгоритм[1], и код[15] были предложены мной, записано на личный счет в качестве необоснованного оскорбления.
← →
Defunct © (2004-09-26 03:34) [30]> 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:49) [31]2 GuAV, когда разберетесь в коде приведенном ниже, и скажете где он может использоваться, тогда будем с вами говорить об опыте. А так кроме, голословных утверждений и оскорблений я от вас пока ничего не услышал.
Start:
Db 0B8H
SubEnable:
Db 2dH
Db 3eH
Db 0EBH
Db 0FCH
Ret
← →
Defunct © (2004-09-26 06:09) [32]Я проанализировал варинт работы с 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, пользуйтесь
← →
GuAV © (2004-09-26 13:26) [33]
> // 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 14:43) [34]GuAV © (26.09.04 13:26) [33]
вначале [31]
← →
GuAV © (2004-09-26 14:49) [35]
> вначале [31]
сначала это
MOV ax, 03E2Dh
JMP @SubEnable,
потом
sub ax, 0EB3Eh
cld
я не сомневаюсь что Вы знаете asm, но с BASM у Вас похоже трабл
← →
Defunct © (2004-09-26 15:19) [36]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;
← →
Defunct © (2004-09-26 15:23) [37]GuAV © (26.09.04 14:49) [35]
1. Ответ неверный.
2. Не раскрыта область применения кода.
← →
GuAV © (2004-09-26 16:59) [38]>{этот код работает только при компиляции на D7 с включенной оптимизацией}
Для тех кто на бронепоезде, повторяю
для asm подпрограмм оптимизация не влияет, параметры всё равно используется модель register и параметры передаются через регистры.
однако это уже выглядит лучше, хотя не проверяю.
Defunct © (26.09.04 15:23) [37] Вероятно Вы имеете ввиду, что вход может быть и сразу в SubEnable?
И код применим как элемент "защиты", где смысл в том что одни и те же бинарные даммые соответствуют разным инструкциям, что может вызвать затруднения при дизасеблировании?
я не разбираюсь в этом, может это и зачем-то надо.
Но по части обычного использованияассемблера в Дельфи
> с BASM у Вас похоже трабл
← →
GuAV © (2004-09-26 17:06) [39]
> всё равно используется модель register и параметры передаются
> через регистры.
по умолчанию, разумеется, можно явно написать pascal
← →
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 на -1Asm
// 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.
← →
GuAV © (2004-09-27 13:03) [69]
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;
← →
GuAV © (2004-09-27 13:13) [70]
> { 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);
← →
Defunct © (2004-09-27 16:39) [71]Код [69] не рабочий.
Project .... failed with message "privileged instruction at address ..." process stopped use RUN to continue
Вашу идею с объединением функций подхватил, сейчас попробую сделать рабочим.
← →
Defunct © (2004-09-27 17:19) [72]
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] если в буфере встречается много одинаковых "обрезков" искомой строки.
← →
Defunct © (2004-09-27 18:03) [73]
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, которая четно говоря мне там не нравится..
← →
Defunct © (2004-09-27 19:25) [74]Эта функция работает почти в два раза быстрее чем стандартная функция 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;
← →
Defunct © (2004-09-27 19:41) [75]Забыл добавить описание:
Function ConstantPos(const Constant: string;
Buffer: Pointer; BufSize: Integer): Integer; Assembler;
{ -> EAx - указатель на строку поиска (константа)
EDx - указатель на буфер, в котором требуется найти строку поиска
ECx - длина буфера
<- EAx - Позиция строки поиска в буфере
(-1) если строки в буфере нет
}
← →
Defunct © (2004-09-27 20:52) [76]результат поиска строки "01wbcb" в файле gladiator.avi (726Mb) с учетом что такой строки в файле нет, а есть множество строк "01wb" составил - 22.34 сек, при повторном запуске - 13.71 сек. проверял на компе с 512Mb памяти (т.е. файл не мог полностью разместиться в кеше).
← →
GuAV © (2004-09-27 21:38) [77]
> Xor EAx,EAx
> Dec EAx // True = (-1) check delphi help for more
> info
заблуждаетесь.
F1 - Boolean types
> Repe CmpsB
Repe CmpsD, а CmpsD - остаток
← →
GuAV © (2004-09-27 21:38) [78]из справки:
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
← →
GuAV © (2004-09-27 22:08) [79]
> Код [69] не рабочий.
>
И после [70] ?
← →
Defunct © (2004-09-27 22:19) [80]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 если найду время.
← →
Defunct © (2004-09-27 22:23) [81]GuAV © (27.09.04 22:08) [79]
не столь важно, поймите я не хочу вас оскорбить или сказать, что вы плохо разбираетесь в асме, просто заметил ошибку, исправил привел вариант [74] так что не зацикливайтесь на одном месте. Хотите продолжить оптимизацию, продолжайте с [74]
← →
GuAV © (2004-09-27 22:26) [82]
> результат поиска строки "01wbcb" в файле gladiator.avi (726Mb)
> с учетом что такой строки в файле нет, а есть множество
> строк "01wb" составил - 22.34 сек, при повторном запуске
> - 13.71 сек. проверял на компе с 512Mb памяти (т.е. файл
> не мог полностью разместиться в кеше).
Это мысль ! Буфер надо не 1ГБ а где-то 16..32 кБ
← →
GuAV © (2004-09-27 22:32) [83]
> Так или иначе, это не имеет значения, т.к. проверка на True
> все равно делается командой Test(будь там -1 или +1 результат
> не изменится, а по скорости Dec и Inc идентичны)
Не всегда, на пример я сослался в
GuAV © (27.09.04 13:01) [68]
т.е. с Boolean вольности не допускаются
> Возможно, а возможно и нет, читал совсем недавно 1-2 месяца
> назад, в справке по Delphi тока не помню где именно (удивлялся).
> Там еще были примеры с приведением типов Integer -> Boolean,
> Boolean -> Integer, Boolean -> Byte, Byte -> Boolean, и
> вот осело в памяти $FFFFFFFF = True.
Ну, в книгах бывают опечатки. Я думал тоже в EAX Integer-результат всегда, а оказывается к safecall это неприменимо.
$FFFFFFFF = True
Насколько я поню, это так в VisualBasic
в Delphi SizeOf(Boolean) = 1 байт. ord(True)=1
есть типы ByteBool, LongBool, WordBool в которых допускаются вольности по части ord(True). в Window.pas кажется или ещё где то объявлен тип BOOL=LongBool
← →
GuAV © (2004-09-27 22:50) [84]Раз возвращаете Integer, возвращайте уже позицию в файле.
Function ConstantExists(FileName, Constant: String): Int64;
Var
Buffer : PBuffer;
F : File;
BufSize : Integer;
BufPos : Integer;
Begin
Result:=0;
New(Buffer);
try
AssignFile(F, FileName);
Reset(F,1);
try
Repeat
BlockRead(F, Buffer^, MaxBufferSize, BufSize);
If BufSize < Length(Constant) Then Break;
BufPos := ConstantPos(Constant, Buffer, BufSize);
if BufPos > 0 then
begin
Inc(Result, BufPos);
Exit;
end;
Inc(Result, BufSize);
Seek(F, FilePos(F) - Length(Constant));
Until (BufSize<MaxBufferSize);
Result := -1;
finally
CloseFile(F);
end;
finally
Dispose(Buffer);
end;
End;
> Буфер надо не 1ГБ а где-то 16..32 кБ
вечер плохого дня...
← →
GuAV © (2004-09-27 22:59) [85]
> if BufPos > 0 then
BufPos => 0 или BufPos <> -1.
← →
GuAV © (2004-09-27 23:03) [86]такой вариант принимается ?
@@CompareWholeString:
Mov ECx, Ebx // ECx - constant chars amount
shr ECx, 2 // ECx - constant chars amount div 4
Repe CmpsD
Jz @@Constant_Exists
Mov ECx, Ebx
and ECx, 3
Repe CmpsB
Jz @@Constant_Exists
или наоборот, сначала B а потом DMov ECx, Ebx // ECx - constant chars amount
shr EBx, 2 // EBx - constant chars amount div 4
and ECx, 3
Repe CmpsB
Jz @@Constant_Exists
Mov ECx, Ebx
Repe CmpsD
Jz @@Constant_Exists
← →
Defunct © (2004-09-27 23:13) [87][84]
Поправлю, вы забыли учесть откат на Length(Constant):Function ConstantExists(FileName, Constant: String): Int64;
Var
Buffer : PBuffer;
F : File;
BufSize : Integer;
BufPos : Integer;
Begin
BufPos := -1;
New(Buffer);
try
AssignFile(F, FileName);
Reset(F,1);
try
Repeat
Result := FilePos(F);
BlockRead(F, Buffer^, MaxBufferSize, BufSize);
If BufSize >= Length(Constant) Then
BufPos := ConstantPos(Constant, Buffer, BufSize);
Result := Result + BufPos;
Seek(F, FilePos(F) - Length(Constant));
Until (BufPos>0) or (BufSize<MaxBufferSize);
finally
CloseFile(F);
end;
finally
If BufPos < 0 Then Result := -1;
Dispose(Buffer);
end;
End;
← →
GuAV © (2004-09-27 23:26) [88]
> If BufSize >= Length(Constant) Then
> BufPos := ConstantPos(Constant, Buffer, BufSize);
> Result := Result + BufPos;
Result будет накапливать -1.
← →
GuAV © (2004-09-27 23:29) [89]
> Поправлю, вы забыли учесть откат на Length(Constant):
ТогдаFunction ConstantExists(FileName, Constant: String): Int64;
Var
Buffer : PBuffer;
F : File;
BufSize : Integer;
BufPos : Integer;
Begin
New(Buffer);
try
AssignFile(F, FileName);
Reset(F,1);
try
Repeat
Result := FilePos(F);
BlockRead(F, Buffer^, MaxBufferSize, BufSize);
If BufSize < Length(Constant) Then Break;
BufPos := ConstantPos(Constant, Buffer, BufSize);
if BufPos > 0 then
begin
Inc(Result, BufPos);
Exit;
end;
{Inc(Result, BufSize);}
Seek(F, FilePos(F) - Length(Constant));
Until (BufSize<MaxBufferSize);
Result := -1;
finally
CloseFile(F);
end;
finally
Dispose(Buffer);
end;
End;
← →
Defunct © (2004-09-27 23:38) [90]GuAV © (27.09.04 23:03) [86]
принимается с поправками, а то получим нехилую ошибку при Length(Constant)<=6 и при (Length(Constant)) mod 4 = 0.
@@CompareWholeString:
Mov ECx, Ebx // ECx - constant chars amount
shr ECx, 2 // ECx - constant chars amount div 4
jz @@SkipDTest
Repe CmpsD
Jnz @@SkipBTest
@@SkipDTest:
Mov ECx, Ebx
and ECx, 3
jz @@SkipBTest
Repe CmpsB
Jz @@Constant_Exists
@@SkipBTest:
Mov ESi, EBp // restore pointer to 2nd char of constant
В общем, получилось просто отлично. на том же файле (gladiator.avi) строка поиска ("01wbcb") время просмотра всего файла - 13.43 сек (было 13.71). Для больших строк конечно же ускорение будет выше.
Попробовал поиграться с размером буфера:
- 10MB скорость падает
- делаю 512Kb - скорость падает.
(Кеш L2 у меня 1Mb) потому 1Mb - оптимально как для машины на которой проводил тесты.
← →
Defunct © (2004-09-27 23:45) [91]GuAV © (27.09.04 23:26) [88]
Дык, в секции finally посмотрите If bufpos<0....
и сброс перед поиском Result := FilePos
← →
GuAV © (2004-09-27 23:57) [92]Mov ECx, Ebx // ECx - constant chars amount
shr ECx, 2 // ECx - constant chars amount div 4
jz @@SkipDTest
Repe CmpsD
Jnz @@SkipBTest
@@SkipDTest:
Mov ECx, Ebx
and ECx, 3
jz @@Constant_Exists // two least significant bits
// of amount is zero so the Constant matches
Repe CmpsB
Jz @@Constant_Exists
@@SkipBTest:
?
← →
GuAV © (2004-09-27 23:58) [93]сорри, Ж нажал вместо КОД
Mov ECx, Ebx // ECx - constant chars amount
shr ECx, 2 // ECx - constant chars amount div 4
jz @@SkipDTest
Repe CmpsD
Jnz @@SkipBTest
@@SkipDTest:
Mov ECx, Ebx
and ECx, 3
jz @@Constant_Exists // two least significant bits
// of amount is zero so the Constant matches
Repe CmpsB
Jz @@Constant_Exists
@@SkipBTest:
принято ?
← →
GuAV © (2004-09-28 00:09) [94]
> GuAV © (27.09.04 23:26) [88]
>
> Дык, в секции finally посмотрите If bufpos<0....
> и сброс перед поиском Result := FilePos
ок.
Всё же вариант [89] ничем не хуже, только проще.
If BufPos < 0 Then Result := -1;
кстати подобный код следует размещать после until перед finally, но не в finally. дело в том, что в случае отсутствия исключения он и так выполнится. в случае исключения результат функции не нужен, более того я даже не вижу возможности им воспользоваться.
← →
Defunct © (2004-09-28 00:32) [95]GuAV © (27.09.04 23:58) [93]
конечно принято!
GuAV © (28.09.04 00:09) [94]
> в случае исключения результат функции не нужен
почему бы не перестраховаться. пусть возвращает правильный результат даже в исключительной ситуации. (нам тока спасибо скажут)
> более того я даже не вижу возможности им воспользоваться.
А я вижу, когда "наплевать" на исключения, их просто проигнорируют, а результат функции будет верным.
Тока не надо говорить, что так делать не правильно, сам знаю, но все равно делаю ;)
← →
GuAV © (2004-09-28 00:38) [96]
> > более того я даже не вижу возможности им воспользоваться.
> А я вижу, когда "наплевать" на исключения, их просто проигнорируют,
> а результат функции будет верным.
> Тока не надо говорить, что так делать не правильно, сам
> знаю, но все равно делаю ;)
например если
I:=MyFunc
и в MyFunc - исключение, то в I остаётся старое значение
я не пробовал, но даже немного сомневаюсь что возможно получить результат в этом случае. если можете - покажите как Вы бы это делали.
← →
Defunct © (2004-09-28 00:56) [97]> я не пробовал, но даже немного сомневаюсь что возможно получить результат в этом случае. если можете - покажите как Вы бы это делали.
Беру функцию [87]
Использую ее так:
procedure TForm1.Button1Click(Sender: TObject);
Var Position : Int64;
begin
Try
Position := ConstantExists(Edit1.Text, Edit2.Text);
Except
End;
If Position>0 Then
ShowMessage("Found")
Else
ShowMessage("Not Found");
End;
end;
В Edit1 ввожу какую-то лабуду типа "sdfsdf.asdasd" в Edit2 - "Test String" возникает исключение на экране вижу "Not Found". Хотя понятно, тест синтетический проще было бы в обработчике исключения написать, что файла с таким именем нет. ;)
← →
GuAV © (2004-09-28 00:59) [98]Defunct © (28.09.04 00:56) [97]
Это похоже на уровне "повезло", попробуйте
Var Position : Int64; - глобальная переменная.
← →
Defunct © (2004-09-28 01:00) [99]PS: код [97] серьезно не воспринимать, правильно должно быть так:
procedure TForm1.Button1Click(Sender: TObject);
begin
Try
If ConstantExists(Edit1.Text, Edit2.Text)>0 Then
ShowMessage("Found")
Else
ShowMessage("Not Found");
Except
ShowMessage("file "+Edit1.Text+" not found");
End;
end;
← →
Defunct © (2004-09-28 01:03) [100]GuAV © (28.09.04 00:59) [98]
Ок, убедили, признаю - страдать фигней незачем.
← →
GuAV © (2004-09-28 01:21) [101]знаете, как можно узнать про флаг D, отсутсвие результата при exception и т.д. ?
посмотреть исходники VCL, найти места где Вы не согласны с Borland и разобраться почему они всё же правы.
см. мою анкету -
F1 - интересно, Ctrl+Click - ещё интереснее,
Defunct © (28.09.04 01:00) [99]
на самом деле, лучше вообще без except. тогда будет выведен текст исключения в сообщении, почему именно не получилось. может не файл не найден а ещё что-то. хотя бы EOutOfMemory.
или уже например что-то типаTry
If ConstantExists(Edit1.Text, Edit2.Text)>0 Then
ShowMessage("Found")
Else
ShowMessage("Not Found");
Except
on EInOutError do ShowMessage("file "+Edit1.Text+" not found");
End;
except без on следует использовать только если внутри raise; - т.е. исключение сохранится для дальнейшего использования.
← →
Defunct © (2004-09-28 02:29) [102]> найти места где Вы не согласны с Borland и разобраться почему они всё же правы.
Знаете, не надо так свято верить в правоту Borland, функция [74] - быстрее Pos, а та к которой мы с вами в итоге пришли после усовершенствования [74] работает более чем в два раза быстрее чем встроенная функция поиска подстроки в строке: Pos. И это не первая функция на моем счету, которая доказывает, что не все решения от Borland оптимальны.
> F1 - интересно, Ctrl+Click - ещё интереснее,
Хелп сделан хорошо, здесь упреков нет.
> на самом деле, лучше вообще без except. тогда будет выведен текст исключения в сообщении
Это уж кому как, я предпочту чтобы программа умолчала об исключении вместо того чтобы показала, что исключение в ней не обрабатывается.
> почему именно не получилось. может не файл не найден а ещё что-то. хотя бы EOutOfMemory.
Ну что ж тогда увы и ах..:
<begin offtop>
.. в одном отдаленном селе Василий Певченко скачал шареварную версию нового "PuperCommander". С возгласом:
- ну наконец-то, догожданная новая версия,
Василий принялся изучать Readme файл со списоком новых возможностей и улучшений...
- О! быстрый поиск строки, сейчас посмотрю, что они там намутили, - улыбнулся Василий, который несколько лет ждал именно эту фичу.
Он задавал имя файла и ввел "смешные анеГДОТЫ" в раскрашенном поле строки поиска, к его глубочайшему удивлению на экране возникало сообщение "Да ну нет такого файла!". Василий повторял ввод имени раз за разом, раз за разом, но на экране в также весело красовалась пестрая надпись с заголовком PuperCommander, уведомляющая, что такого файла нет. Василий вспомнил, что вчера выпил не мало, об этом напиминали трясущиеся руки, и решил скопировать имя файла прямо из проводника самой модной операционки "ГунДоус" от корпорации "МодныйСофт". А на экране все также пестрилась веселая надпись "Да не найден, надо меньше пить". В гневе Василий нажал кнопку "ПЫтание" на корпусе своего модного компутера "ИВМ" от фирмы "Красночух Электроникс", замигали лампочки, в динамиках раздался приятный женский голос "подождите пожалуйста, ГунДоус приступил к первой фазе подготовки к выполнению завершения вашей работы". Василий ждал..
.....
...
..
Экран засветился, потом погас, потом опять засветился на этот раз с надписью "Красночух Электроникс БИОС, ждите", замигали лампочки. Василий потихоньку приходил в себя, он взял очередную бутылочку пива из холодильника и удобно развалился на кресле с мягкой спинкой. Наблюдая за меняющимися картинками, которыми обычно сопровождается загрузка модной системы "ГунДоус", он размышлял о том, что он самый счастливый человек на свете. Теперь у него есть "PuperCommander" и он сможет с гордостью похвастаться об этом своим друзьям. "ГунДоус" пригласил Василия ввести пароль, после чего Василий сразу же запустил "PuperCommander" ввели имя файла и.... О чудо! ни каких надписей, пестрая табличка с вопросом "смешные анеГДОТЫ найдены, показать?".
- Глючный ГунДоус, - подумал Василий, - когда уже эти олухи из корпорации "МодныйСофт" сделают что-то нормальное..
<end offtop>
И в чем-то Василий будет прав.
В данном конкретном случае меня не интересуют другие ошибки кроме "файл не найден" так как логически там их быть не может, кроме случая - ошибка ОС.
← →
jack128 © (2004-09-28 02:42) [103]Defunct © (28.09.04 2:29) [102]
работает более чем в два раза быстрее чем встроенная функция поиска подстроки в строке:
Ага, сели два чела, 4 дня провозились и еще и удивляются, как же у них получилась функция, которая быстрее стандартной реализации ;-)
зы Pos - не ориентирован на поиск подстроки в 1Гб файле. Насколько она быстрее при работе с обычными строками (длиной 30-100 символов)
ззы вашу функцию нужно в базу знаний отправить.
← →
Defunct © (2004-09-28 03:06) [104]> Насколько она быстрее при работе с обычными строками (длиной 30-100 символов)
Pos будет медленнее, так как в стадартной функции Pos две пары Push/Pop в основном цикле поиска и не рассмотривается вариант отбраковки подстроки по первому и последнему символам.
На сколько медленнее сказать сейчас не могу. На маленьких строках тяжело точно измерить скорость, куча побочных эффектов, например, просто факт вызова функции (команда Call) отнимает примерно столько времени сколько потребуется на просмотр 2-5 символов, согласитесь немало при длинне строки в 30 символов.
← →
Defunct © (2004-09-28 10:46) [105]2 GuruAV.
Подумайте как можно применить следущее:
скажем есть возможность получать такие последовательности (командаPCMPEQB mmreg, mmreg/rel32}
на входе:->
54h 34h 34h 45h 35h 43h 64h 70h 65h 70h
34h 34h 34h 34h 34h 34h 34h 34h 34h 34h
на выходе:<-
00h FFh FFh 00h 00h 00h 00h 00h 00h 00h
за один такт.
Как бы это применить к нашему сабжу.. Хочется избавиться от ScasB
← →
Defunct © (2004-09-28 11:49) [106]вот наброски, черт его знает стоит ли оно того, что-то уж сильно много кода получается
...
{$ifdef MMX}
MovQ MM0, [Edi] // load prefics
PCMPEQB MM0, MM6 // make a mask (mm6 filled by 1st char of da constant)
MovD EAx, MM0
Test EAx,EAx
Jnz @@Char_somewhere??
PSRLQ MM0,32 // mm0 := mm0 div 2^32
MovD EAx, MM0
Test EAx, EAx
Jnz @@Char_Somewhere??
Add EDi,8
Sub ECx,8
Jns @@Scan
{$else}
Repne ScasB
{$endif}
...
...
@@Leave_Proc:
{$ifdef MMX}
EMMS
{$endif}
← →
Игорь Шевченко © (2004-09-28 12:30) [107]MMF оно проще...
← →
Sha © (2004-09-28 12:34) [108]Ага, никакого буфера.
И простым циклом на Паскале.
← →
GuAV © (2004-09-28 22:12) [109]
> И это не первая функция на моем счету, которая доказывает,
> что не все решения от Borland оптимальны.
Однако они почти все верны. Т.к. умные люди писали и их очень многие используют.
Ну могут быть и не оптимальны, т.к. они и не особо стремятся - они вероятно такой фигнёй не страдают.
> Это уж кому как, я предпочту чтобы программа умолчала об
> исключении вместо того чтобы показала, что исключение в
> ней не обрабатывается.
Ну вот допустим памяти не хватило. Тогда файл не найден.
А он не найден потому что его нет или памяти нехватило, или ошибка чтения файла - угадай-ка ? :)
Если же речь идет об ошибке ОС, то показ текста выданого самой ОС - ИМХО лучшая обработка.
> меня не интересуют другие ошибки кроме "файл не найден"
> так как логически там их быть не может, кроме случая - ошибка
> ОС
Может и не интересуют, но они могут в принципе быть.
И потом, ошибка файл не найден должна обрабатываться не этой функцией, а вызывающей её функцией и если хотите всё же её обрабатывать, то GuAV © (28.09.04 01:21) [101] .
Ошибки могут быть даже там где их логически быть не может.
jack128 ©
> Ага, сели два чела, 4 дня провозились и еще и удивляются,
> как же у них получилась функция, которая быстрее стандартной
> реализации ;-)
я вообще-то не особо возился :) заметь, несмотря на то что я поставил Дельфи, я ни разу не выполнял этот код. Так чит
Поэтому больше благодари Defunct ©
> ззы вашу функцию нужно в базу знаний отправить.
Почему-то мне кажется что там такое уже есть.
Если конечно Defunct © напишет версию через продвинутый набор комманд, то этой может там ещё не быть.
Кстати, согласно моей информации (изрядно впрочем устаревшей), MOV и PUSH работают одинаково быстро (если в качестве операнда push РОН). XCHG же работает медленнее. Может на современных процессорах это не так, тогда был бы рад информации.PUSH reg16 ¦ push dx ¦ 88/86 11 (88=15)
PUSH reg32* ¦ ¦ 286 3
PUSHW reg16 ¦ ¦ 386 2
PUSHD reg16* ¦ ¦ 486 1
PUSHD reg32* ¦ ¦
MOV reg,reg ¦ mov dh,bh ¦ 88/86 2
¦ mov dx,cx ¦ 286 2
¦ mov bp,sp ¦ 386 2
¦ ¦ 486 1
XCHG reg,reg ¦ xchg cx,dx ¦ 88/86 4
¦ xchg dl,dh ¦ 286 3
¦ xchg al,ah ¦ 386 3
¦ ¦ 486 3
> MMF оно проще...
- Cолдаты! берите ломы и копайте яму 2 на 2!
- Товарищь прапорщик, а не лучше ли взять лопаты?
- А мне не нужно лучше, мне нужно чтоб вы за... (замучились) !
← →
Defunct © (2004-09-29 02:06) [110]XCHG reg32,reg32 ¦ xchg eax,edx ¦ P-Pro and higher - 1/2
← →
Fedia (2004-09-29 02:56) [111]To Defunct and GuAV.
Даже несмотря на то, что большинство кода на ASM для меня оставалось загадкой, все равно с удовольствием почитал ветку.
А итоговую процедуру поиска с удовольствием буду использовать.
Просто хотел поблагодарить GuAV за настойчивость, а Defunct за терпение :)
← →
Defunct © (2004-09-29 03:23) [112]Кому интересно, поиск строки с использованием MMX. Ускорен поиск на 10-20% (скорость зависимосит от частоты появлнеия первого символа искомой строки в буфере поиска). Результат пересмотра буфера объемом- 2.5Gb (25Mb 100 раз подряд) составляет 9.123 сек, в то время как без MMX - 10.238 сек.
{$define MMX}
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 Al, [ESi] // Store first char of the constant in AL
Mov EBX, [ESI-4]
Dec EBX
{$ifdef MMX}
Mov Ah, Al // Spreading char to 32bit register
Push Ax
Push Ax
Pop EAx
MovD MM6, EAx
PSLLQ MM6,MM6 // Spreading char to mmx register
PXOR MM5,MM5 // Z mask for later calculations
MovD MM6, EAx
{$endif}
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 EDx,ECx // EDx - Stored residual buffer size
Inc ESi
Mov EBp, ESi // EBp - stored pointer to 2nd char of constant
{$ifdef MMX}
MovD MM4, EAx // store EAx in MM buffer
{$endif}
@@Scan:
{$ifdef MMX}
MovQ MM7, [Edi] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
PCMPGTD MM7, MM5 // make a dword mask
PUNPCKHBW MM7, MM7 // mix 2 dwords into a qword
MovD EAx, MM7 // get mixed dword
Test EAx, EAx // was there at least 1 bit set?
Jnz @@CharFound // yes - 1st char of the constant was found
Add EDi,8 // correct index
Sub ECx,8 // and buffer size
Jns @@Scan // continue scan if buffer not empty
Jmp @@Exit_False // otherwise - leave with no result
@@CharFound:
MovD EAx, MM4 // restore EAx (1st and last chars of the constant)
{$endif}
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
shr ECx, 2 // ECx - constant chars amount div 4
jz @@SkipDTest
Repe CmpsD
Jnz @@SkipBTest
@@SkipDTest:
Mov ECx, Ebx
and ECx, 3
jz @@Constant_Exists // two least significant bits
// of amount are zero so the Constant matches
Repe CmpsB
Jz @@Constant_Exists
@@SkipBTest:
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:
{$ifdef MMX}
EMMS // finish mmx operations
{$endif}
Pop EBp
Pop EBx
Pop ESi
Pop EDi
End;
← →
Defunct © (2004-09-29 03:36) [113]> - А мне не нужно лучше, мне нужно чтоб вы за... (замучились) !
Отож простые задачи - неитересны, и даже скучны.
← →
Defunct © (2004-09-29 04:30) [114]Так работает немножко быстрее, на 0.5-1%
...
{$ifdef MMX}
MovQ MM7, [Edi] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
PCMPGTD MM7, MM5 // make a dword mask
PUNPCKHWD MM7, MM7 // mix 2 dwords into a qword
...
...
{$endif}
Repne ScasB
{$ifndef MMX}
JNE @@Exit_False // no 1st char of the constant found = exit_false
{$endif}
...
>> меня не интересуют другие ошибки кроме "файл не найден"
>> так как логически там их быть не может, кроме случая - ошибка
>> ОС
> Может и не интересуют, но они могут в принципе быть.
> Ну вот допустим памяти не хватило. Тогда файл не найден.
> А он не найден потому что его нет или памяти нехватило, или
> ошибка чтения файла - угадай-ка ? :)
PS: GuruAV как вам рассказик [102]? там все сказано об этом.
← →
Defunct © (2004-09-29 04:50) [115]> Ну могут быть и не оптимальны, т.к. они и не особо стремятся - они вероятно такой фигнёй не страдают.
Вот потому все серьезные проекты, которые требуют скорости и пишутся на C++, а компилируются или MS Visual Studio .Net или интеловский компилятором.
← →
Игорь Шевченко © (2004-09-29 10:22) [116]
> Вот потому все серьезные проекты, которые требуют скорости
> и пишутся на C++, а компилируются или MS Visual Studio .Net
> или интеловский компилятором.
Лажу гнать не надо, а ?
← →
Defunct © (2004-09-29 18:14) [117]Игорь Шевченко © (29.09.04 10:22) [116]
в чем лажа?
← →
GuAV © (2004-09-29 22:10) [118]
> PS: GuruAV как вам рассказик [102]? там все сказано об этом.
Не понял что Вы хотели им сказать. Однако
[101] и
> Может и не интересуют, но они могут в принципе быть.
> Ну вот допустим памяти не хватило. Тогда файл не найден.
> А он не найден потому что его нет или памяти нехватило, или
> ошибка чтения файла - угадай-ка ? :)
в силе.
Defunct © (29.09.04 03:23) [112]
c00l !
Напишите ещё и {$else} и выделите не MMX код туда, а то совсем прочитать не могу
← →
Defunct © (2004-09-29 23:16) [119]> Напишите ещё и {$else} и выделите не MMX код туда, а то совсем прочитать не могу
Не, там все должно быть как есть. с помощью MMX делается только определение наличия символа в QWORD, дальше repne scas просматривает только цепочку из 8-ми байт.
Из старого кода выбрасывается только одна команда, смотреть поправку [114] секция {$ifndef}
Уберете {define MMX} будет работать старая функция, оставите - будет сканироваться по 8 байт.
← →
Sha © (2004-09-30 09:24) [120]> Defunct
Попробуй написать аналог Борландовской Pos на базе своей функции и померяйся с вот этим:
//(c) John O"Harrow
function PosJOH_MMX(const SubStr : AnsiString; const Str : AnsiString) : Integer;
asm
test eax, eax
jz @NotFoundExit {Exit if SurStr = ""}
test edx, edx
jz @NotFound {Exit if Str = ""}
mov ecx, [edx-4] {Length(Str)}
cmp [eax-4], 1 {Length SubStr = 1?}
je @SingleChar {Yes - Exit via CharPos}
jl @NotFound {Exit if Length(SubStr) < 1}
sub ecx, [eax-4] {Subtract Length(SubStr), -ve handled by
CharPos}
add ecx, 1 {Number of Chars to Check for 1st Char}
push esi {Save Registers}
push edi
push ebx
push ebp
mov esi, eax {Start Address of SubStr}
mov edi, ecx {Initial Remainder Count}
mov eax, [eax] {AL = 1st Char of SubStr}
mov ebp, edx {Start Address of Str}
mov ebx, eax {Maintain 1st Search Char in BL}
@StrLoop:
mov eax, ebx {AL = 1st char of SubStr}
mov ecx, edi {Remaining Length}
push edx {Save Start Position}
call @CharPos {Search for 1st Character}
pop edx {Restore Start Position}
test eax, eax {Result = 0?}
jz @StrExit {Exit if 1st Character Not Found}
mov ecx, [esi-4] {Length SubStr}
add edx, eax {Update Start Position for Next Loop}
sub edi, eax {Update Remaining Length for Next Loop}
sub ecx, 1 {Remaining Characters to Compare}
@StrCheck:
mov al, [edx+ecx-1] {Compare Next Char of SubStr and Str}
cmp al, [esi+ecx]
jne @StrLoop {Different - Return to First Character Search}
sub ecx, 1
jnz @StrCheck {Check each Remaining Character}
mov eax, edx {All Characters Matched - Calculate Result}
sub eax, ebp
@StrExit:
pop ebp {Restore Registers}
pop ebx
pop edi
pop esi
ret
@NotFound:
xor eax, eax {Return 0}
@NotFoundExit:
ret
@SingleChar:
mov al, [eax] {Search Character}
@CharPos:
CMP ECX, 8
JG @@NotSmall
@@Small:
or ecx, ecx
jle @@NotFound {Exit if Length <= 0}
CMP AL, [EDX]
JZ @Found1
DEC ECX
JZ @@NotFound
CMP AL, [EDX+1]
JZ @Found2
DEC ECX
JZ @@NotFound
CMP AL, [EDX+2]
JZ @Found3
DEC ECX
JZ @@NotFound
CMP AL, [EDX+3]
JZ @Found4
DEC ECX
JZ @@NotFound
CMP AL, [EDX+4]
JZ @Found5
DEC ECX
JZ @@NotFound
CMP AL, [EDX+5]
JZ @Found6
DEC ECX
JZ @@NotFound
CMP AL, [EDX+6]
JZ @Found7
DEC ECX
JZ @@NotFound
CMP AL, [EDX+7]
JZ @Found8
@@NotFound:
XOR EAX, EAX
RET
@Found1:
MOV EAX, 1
RET
@Found2:
MOV EAX, 2
RET
@Found3:
MOV EAX, 3
RET
@Found4:
MOV EAX, 4
RET
@Found5:
MOV EAX, 5
RET
@Found6:
MOV EAX, 6
RET
@Found7:
MOV EAX, 7
RET
@Found8:
MOV EAX, 8
RET
@@NotSmall: {Length(Str) > 8}
MOV AH, AL
ADD EDX, ECX
MOVD MM0, EAX
PUNPCKLWD MM0, MM0
PUNPCKLDQ MM0, MM0
PUSH ECX {Save Length}
NEG ECX
@@First8:
MOVQ MM1, [EDX+ECX]
ADD ECX, 8
PCMPEQB MM1, MM0 {Compare All 8 Bytes}
PACKSSWB MM1, MM1 {Pack Result into 4 Bytes}
MOVD EAX, MM1
TEST EAX, EAX
JNZ @@Matched {Exit on Match at any Position}
CMP ECX, -8 {Check if Next Loop would pass String End}
JGE @@Last8
@@Align: {Align to Previous 8 Byte Boundary}
LEA EAX, [EDX+ECX]
AND EAX, 7 {EAX -> 0 or 4}
SUB ECX, EAX
@@Loop:
MOVQ MM1, [EDX+ECX]
ADD ECX, 8
PCMPEQB MM1, MM0 {Compare All 8 Bytes}
PACKSSWB MM1, MM1 {Pack Result into 4 Bytes}
MOVD EAX, MM1
TEST EAX, EAX
JNZ @@Matched {Exit on Match at any Position}
CMP ECX, -8 {Check if Next Loop would pass String End}
{$IFNDEF NoUnroll}
JGE @@Last8
MOVQ MM1, [EDX+ECX]
ADD ECX, 8
PCMPEQB MM1, MM0 {Compare All 8 Bytes}
PACKSSWB MM1, MM1 {Pack Result into 4 Bytes}
MOVD EAX, MM1
TEST EAX, EAX
JNZ @@Matched {Exit on Match at any Position}
CMP ECX, -8 {Check if Next Loop would pass String End}
{$ENDIF}
JL @@Loop
@@Last8:
MOVQ MM1, [EDX-8] {Position for Last 8 Used Characters}
POP EDX {Original Length}
PCMPEQB MM1, MM0 {Compare All 8 Bytes}
PACKSSWB MM1, MM1 {Pack Result into 4 Bytes}
MOVD EAX, MM1
TEST EAX, EAX
JNZ @@Matched2 {Exit on Match at any Position}
EMMS
RET {Finished - Not Found}
@@Matched: {Set Result from 1st Match in EDX}
POP EDX {Original Length}
ADD EDX, ECX
@@Matched2:
EMMS
SUB EDX, 8 {Adjust for Extra ADD ECX,8 in Loop}
TEST AL, AL
JNZ @@MatchDone {Match at Position 1 or 2}
TEST AH, AH
JNZ @@Match1 {Match at Position 3 or 4}
SHR EAX, 16
TEST AL, AL
JNZ @@Match2 {Match at Position 5 or 6}
SHR EAX, 8
ADD EDX, 6
JMP @@MatchDone
@@Match2:
ADD EDX, 4
JMP @@MatchDone
@@Match1:
SHR EAX, 8 {AL <- AH}
ADD EDX, 2
@@MatchDone:
XOR EAX, 2
AND EAX, 3 {EAX <- 1 or 2}
ADD EAX, EDX
end;
← →
Игорь Шевченко © (2004-09-30 10:18) [121]Defunct © (29.09.04 18:14) [117]
В процитированном
← →
Romkin © (2004-09-30 10:31) [122]Sha © (30.09.04 09:24) [120] Бррр...
Может, так достаточно? http://delphibase.endimus.ru/?action=viewfunc&topic=strsearch&id=10271
Интересно, и насколько отстает?
← →
Sha © (2004-09-30 16:44) [123]Romkin © (30.09.04 10:31) [122]
Вот и мне интересно, насколько Defunct отстанет.
Думаю, в среднем по разным длинам, отстанет прилично.
А в 2 слишним раза перекрыть RTL можно и на Паскале:
function PosShaPas(const SubStr: AnsiString; const Str: AnsiString): Integer;
var
len, lenSub: integer;
ch: char;
p, pSub, pStart, pEnd: pchar;
label
Ret, Ret0, Ret1, Next0, Next1;
begin;
p:=pointer(Str);
pSub:=pointer(SubStr);
//if you need pure Pascal uncomment this paragraph
//and comment out the next 3 paragraphs
{
len:=length(Str);
lenSub:=length(SubStr);
pEnd:=p+len;
pStart:=p;
pEnd:=pEnd-lenSub;
if (len<=0) or (lenSub<=0) or (p>pEnd) then begin;
Result:=0;
exit;
end;
}
if (p=nil) or (pSub=nil) then begin;
Result:=0;
exit;
end;
len:=pinteger(p-4)^;
lenSub:=pinteger(pSub-4)^;
if (len<lenSub) or (lenSub<=0) then begin;
Result:=0;
exit;
end;
pEnd:=p+len;
pStart:=p;
pEnd:=pEnd-lenSub;
ch:=pSub[0];
if lenSub=1 then begin;
repeat;
if ch=p[0] then goto Ret0;
if ch=p[1] then goto Ret1;
p:=p+2;
until p>pEnd;
Result:=0;
exit;
end;
repeat;
if ch=p[0] then begin;
len:=lensub;
repeat;
if psub[len-1]<>p[len-1] then goto Next0;
if psub[len-2]<>p[len-2] then goto Next0;
len:=len-2;
until len<2;
goto Ret0;
Next0:end;
if ch=p[1] then begin;
len:=lensub;
repeat;
if psub[len-1]<>p[len] then goto Next1;
if psub[len-2]<>p[len-1] then goto Next1;
len:=len-2;
until len<2;
goto Ret1;
Next1:end;
p:=p+2;
until p>pEnd;
Result:=0;
exit;
Ret1:
inc(pEnd);
p:=p+2;
if p<=pEnd then goto Ret;
Result:=0;
exit;
Ret0:
inc(p);
Ret:
Result:=p-pStart;
end;
← →
Defunct © (2004-09-30 21:05) [124]Sha © (30.09.04 09:24) [120]
Пока не не адаптировал фукнкцию к Ansi String, но к приведенной вами функции - Respect.
строка SubString = "Test Stringx" - 12 симоволов.
5.978/ 4.153 / 3.900 ([120]/[123]/[112]).
строка SubString = "Test String" - 11 симоволов.
6.278/ 4.753 / 4.085 ([120]/[123]/[112]).
Но это и понятно, там рассмотрены почти все частные случаи.
Попробую и своего зверька [112] привести к нормальному виду.
To Sha: За счет чего достигается такое быстродействие в [123]?
← →
GuAV © (2004-09-30 21:20) [125]У меня быстрее [120], [123] немного медленнее.
на коротком файле (autoecex.bat) быстрее всего [112].
Celeron 2000, win9x.
не ММХ - ф-ция ваще в пролёте.
← →
Defunct © (2004-09-30 21:37) [126]Defunct © (30.09.04 21:05) [124]
опечатка:
строка SubString = "Test Stringx" - 12 симоволов.
5.978/ 4.153 / 3.900 ([112]/[120]/[123]).
строка SubString = "Test String" - 11 симоволов.
6.278/ 4.753 / 4.085 ([112]/[120]/[123]).
← →
Sha © (2004-09-30 22:22) [127]> Defunct © (30.09.04 21:05) [124]
> За счет чего достигается такое быстродействие в [123]?
За счет алгоритма, основанного на использовании внутреннего представления AnsiString, двухкратного развертывания циклов поиска первого совпадения и сравнения последующих символов, а также маленькой хитрости - изменения направления сравнения.
Так что дело тут, как видишь, совсем не в выборе языка :)
← →
Defunct © (2004-09-30 22:24) [128]С вот таким вот изменением, скорость [112] сравнялась с [120]
@@Scan:
{$ifdef MMX}
MovD MM7, [Edi] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
// PCMPGTD MM7, MM5 // make a dword mask
// PUNPCKHWD MM7, MM7 // mix 2 dwords into a qword
MovD EAx, MM7 // get mixed dword
Test EAx, EAx // was there at least 1 bit set?
Jnz @@CharFound // yes - 1st char of the constant was found
Add EDi,4 // correct index
Sub ECx,4 // and buffer size
Jns @@Scan // continue scan if buffer not empty
Jmp @@Exit_False // otherwise - leave with no result
@@CharFound:
MovD EAx, MM4 // restore EAx (1st and last chars of the constant)
{$endif}
Repne ScasB
{$ifndef MMX}
JNE @@Exit_False // no 1st char of the constant found = exit_false
{$endif}
Я даже не думал, что MovQ работает настолько медленней чем 2 MovD
[123] действительно получается в пролете.
строка SubString = "Test String" - 11 симоволов.
4.078/4.085/4.753 ([112 с указанным изменением]/[120]/[123])
Просмотренный буфер - 2.5Gb (читался порциями по 1Mb, файл 25Mb, 100 раз подряд).
← →
Defunct © (2004-09-30 22:26) [129]> а также маленькой хитрости - изменения направления сравнения.
О, стоит применить к [112] ;)
← →
Sha © (2004-09-30 22:27) [130]> Defunct © (30.09.04 22:24) [128]
Дай полный код своего аналога Pos. Я его завтра потестирую.
← →
GuAV © (2004-09-30 22:40) [131]
> Пока не не адаптировал фукнкцию к Ansi String
для своих тестов я так сделал:Function DefunctMMX(const Constant: string;
const Buffer: string): Integer; Assembler;
Asm
Push EDi
Push ESi
Push EBx
Push EBp
// a fix to make this fcn Pos compatible
MOV ECX, [EDX-4] // should not affect perfomance much
Push ECx // store total buffer size for later calculation pos
← →
Defunct © (2004-09-30 23:22) [132]> Дай полный код своего аналога Pos. Я его завтра потестирую.
unit Search;
interface
{$define MMX}
Function ConstantPos(const Constant, Buffer: string): Integer;
implementation
Function ConstantPos(const Constant, Buffer: string): Integer; Assembler;
Asm
Push EDi
Push ESi
Push EBx
Push EBp
MOV ESI, EAX // ESi pointer to constant
Mov EDi, EDx // EDi pointer to buffer
Mov ECx, [EDi-4]
Push ECx // store total buffer size for later calculation pos
Mov EBX, [ESI-4]
Dec EBX
Mov Al, [ESi] // Store first char of the constant in AL
{$ifdef MMX}
Mov Ah, Al // Spreading char to 32bit register
Push Ax
Push Ax
Pop EAx
MovD MM6, EAx
PSLLQ MM6,MM6 // Spreading char to mmx register
MovD MM6, EAx
PXOR MM5,MM5 // Z mask for later calculations
{$endif}
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 EDx,ECx // EDx - Stored residual buffer size
Inc ESi
Mov EBp, ESi // EBp - stored pointer to 2nd char of constant
{$ifdef MMX}
MovD MM4, EAx // store EAx in MM buffer
{$endif}
@@Scan:
{$ifdef MMX}
MovQ MM7, [Edi] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
PCMPEQD MM7, MM5 // make a dword mask
PCMPEQD MM7, MM5 // invert dword mask
PSLLQ MM7,16 // mix 2 dwords into a qword
MovD EAx, MM7 // get mixed dword
Test EAx, EAx // was there at least 1 bit set?
Jnz @@CharFound // yes - 1st char of the constant was found
Add EDi,8 // correct index
Sub ECx,8 // and buffer size
Jns @@Scan // continue scan if buffer not empty
Jmp @@Exit_False // otherwise - leave with no result
@@CharFound:
MovD EAx, MM4 // restore EAx (1st and last chars of the constant)
{$endif}
Repne ScasB
{$ifndef MMX}
JNE @@Exit_False // no 1st char of the constant found = exit_false
{$endif}
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
shr ECx, 2 // ECx - constant chars amount div 4
jz @@SkipDTest
Repe CmpsD
Jnz @@SkipBTest
@@SkipDTest:
Mov ECx, Ebx
and ECx, 3
jz @@Constant_Exists // two least significant bits
// of amount are zero so the Constant matches
Repe CmpsB
Jz @@Constant_Exists
@@SkipBTest:
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:
{$ifdef MMX}
EMMS // finish mmx operations
{$endif}
Pop EBp
Pop EBx
Pop ESi
Pop EDi
End;
end.
← →
Defunct © (2004-09-30 23:46) [133]Вот более достоверные результаты (просмотр 25Gb):
[132] - 42.230 сек
[120] - 38.800 сек
[123] - 46.831 сек
Опять же скорость сильно зависит от частоты появления первого символа искомой подстроки, причем для всех трех функций.
2 Sha, если вашу функцию сделать в MMX исполнении, она поидее побъет всех ;) т.к. [132] без MMX - 65.453
← →
Sha © (2004-09-30 23:53) [134]> Defunct
1. Функция не является полным аналогом Pos.
Не будет работать для пустых строк, т.к. за длиной строки полезет по адресу (0-4)=FFFFFFFC.
2. Не корректно замерять скорость Pos на файлах или на буфере длиной 2Gb. Погрешности за счет дисковых очень велики и не предсказуемы.
← →
GuAV © (2004-09-30 23:58) [135]Sha © (30.09.04 23:53) [134]
Какие размеры для замера предлагаете?
имхо 0, 128 байт, 1 кБ и 1 МБ.
← →
Sha © (2004-10-01 00:12) [136]> Defunct
3. Оригинальная Pos из RTL в случае неуспеха возвращает 0, твоя -1:@@Exit_False:
Pop EAx
Xor EAx,EAx // False = (0), check delphi help for more info
Dec EAx
Jmp @@Leave_Proc
4. Оригинальная Pos никогда не тестирует символы, идущие за терминатором. Твоя тестирует, что теоретически может вызвать AV.
← →
Sha © (2004-10-01 00:16) [137]> GuAV © (30.09.04 23:58) [135]
> Какие размеры для замера предлагаете?
Предлагаю использовать неплохой (хотя и не без нереканий) вариант
http://dennishomepage.gugs-cats.dk/PosBV45.zip
← →
Sha © (2004-10-01 00:38) [138]> Defunct
5. Похоже, твоя функция иногда будет выдавать неверный результат (следствие пункта 4):ConstantPos(#0,"Мы находим даже терминатор")>0
← →
Defunct © (2004-10-01 02:25) [139]Ок, со всем здесь услышанным, подправил [132], так, что возвращается "0" если строка не найдена, подправлена работа со строками нулевой длинны, и плюс сделал выравнивание адреса как в [120] (спасибо за пример [120]).
Ну теперь получается по скорости, на некоторых строках выигрывает новая функция, на некоторых - [120]. По времени, приблизительно получилось следующее:
на разных строках функция [120] (1.25Gb пересмотр).
результат от 19.069 сек до 19.984.
новая функция тестировалась в тех же условиях (1.25Gb пересмотр)
результат от 18.768 сек до 20.364.
Буфер поиска - 1Mb.
Следует отметить неоспоримое преимущество приведенной здесь функции, она в отличие от [120] способна работать на процессорах у которых нет MMX.unit Search;
interface
{$define MMX}
Function ConstantPos(const Constant, Buffer: string): Integer;
implementation
Function ConstantPos(const Constant, Buffer: string): Integer; Assembler;
Asm
Push EDi
Push ESi
Push EBx
Push EBp
MOV ESI, EAX // ESi pointer to constant
Mov EDi, EDx // EDi pointer to buffer
Mov ECx, [EDi-4]
Push ECx // store total buffer size for later calculation pos
Test ECx,ECx
Jz @@Exit_False
Mov EBX, [ESI-4]
Test EBx,EBx
Jz @@Exit_False
Dec EBX
Mov Al, [ESi] // Store first char of the constant in AL
{$ifdef MMX}
Mov Ah, Al // Spreading char to 32bit register
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
PXOR MM5,MM5 // Z mask for later calculations
Dec EBx // EBx - length of the constant w/o 1st and last chars
Mov Ax,[ESi+EBx]
Dec EBx
{$endif}
{$ifndef MMX}
Mov Ah, [ESi+EBx] // Store last char of the constant in AH
{$endif}
Mov EDx,ECx // EDx - Stored residual buffer size
Inc ESi
Mov EBp, ESi // EBp - stored pointer to 2nd char of constant
{$ifdef MMX}
MovD MM4, EAx // store EAx in MM buffer
{$endif}
@@Scan:
{$ifdef MMX}
MovQ MM7, [Edi] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
PACKSSWB MM7, MM7
MovD EAx, MM7 // get mixed dword
Test EAx, EAx // was there at least 1 bit set?
Jnz @@CharFound // yes - 1st char of the constant was found
Add EDi, 8
Mov EAx, Edi
And EAx, 7
Sub EDi,EAx // Aligning index
Sub ECx,8
Add ECx,EAx // and correcting buffer size
Js @@Exit_False
@@Scan2:
MovQ MM7, [Edi] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
PACKSSWB MM7,MM7
MovD EAx, MM7 // get mixed dword
Test EAx, EAx // was there at least 1 bit set?
Jnz @@CharFound // yes - 1st char of the constant was found
Add EDi,8 // correct index
Sub ECx,8 // and buffer size
Jns @@Scan2 // continue scan if buffer not empty
Jmp @@Exit_False // otherwise - leave with no result
@@CharFound:
MovQ MM7, [Edi] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
MovD EAx, MM7
Test EAx, EAx
Jnz @@Loop1
PSRLQ MM7,32
MovD EAx, MM7
@@Loop1:
inc EDi
dec Ecx
Shr EAx,8
Jz @@ContinueHere
jmp @@Loop1
{$endif}
Repne ScasB
{$ifndef MMX}
JNE @@Exit_False // no 1st char of the constant found = exit_false
{$else}
@@ContinueHere:
MovD EAx, MM4 // restore EAx (1st and last chars of the constant)
{$endif}
@@CheckLastChar: // as proposed in Boyer-Mur alhorithm
{$ifndef MMX}
Cmp Ah, [EBx+Edi] // check found substring with last char of the constant
{$else}
Cmp Ax, [EBx+EDi]
{$endif}
Jz @@CompareWholeString // not match - continue searching
Jmp @@Scan
@@Exit_False:
Pop EAx
Xor EAx,EAx // 0 if constant was not found
Jmp @@Leave_Proc
@@CompareWholeString:
Mov EDx, ECx // store new residual buffer size
Cmp EDx, EBx // constant still can be settled in buffer
Jna @@Exit_False // no - exit with false result
Mov ECx, Ebx // ECx - constant chars amount
shr ECx, 2 // ECx - constant chars amount div 4
jz @@SkipDTest
Repe CmpsD
Jnz @@SkipBTest
@@SkipDTest:
Mov ECx, Ebx
and ECx, 3
jz @@Constant_Exists // two least significant bits
// of amount are zero so the Constant matches
Repe CmpsB
Jz @@Constant_Exists
@@SkipBTest:
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:
{$ifdef MMX}
EMMS // finish mmx operations
{$endif}
Pop EBp
Pop EBx
Pop ESi
Pop EDi
End;
end.
На будущее думаю попробовать сделать поиск через SSE/SSE2
> 4. Оригинальная Pos никогда не тестирует символы, идущие за терминатором. Твоя тестирует, что теоретически может вызвать AV.
ни старая, ни исправленная функции не выходили за границу буфера.
← →
Defunct © (2004-10-01 02:28) [140]> [139] (1.25Gb пересмотр).
не там точку поставил.
12.5Gb пересмотр.
← →
Defunct © (2004-10-01 03:14) [141]посмотрел тест [137] недостаток теста в том, что он был нацелен именно, на поиск подстроки в строке. Функция же [139] больше нацелена на поиск подстроки в файле, т.е. предполагается просмотр не одного буфера а немкольких. Поэтому по одному тесту скорости у нее высокая оценка (SubBench2), а по второму (SubBench1) - низкая, суммарная оценка получалась лучше чем RTL/RTLa/b но значительно хуже чем у PosJoh и PosSha, сейчас внесу поправки с учетом изменения задачи.
← →
Defunct © (2004-10-01 06:17) [142]> Sha
Провозился всю ночь с этой функцией, выкладывать пока не буду так как еще не доделал. Есть вопрос, что в вашем тесте означает SubBench1 и SubBench2?
В изначальном варианте [139] было:
SubBench1 = 261
SubBench2 = 159
Сейчас почемуто получается:
SubBench1 = 295
SubBench2 = 121
Суммарный Bench индекс практически не изменился все на том же уровне 410-420.
В функциях PosJoh_MMX и PosSha наблюдаю примерно такую картину:
SubBench1 = 177, 180
SubBench2 = 147, 152
SubBench1 относится к маленьким строкам я правильно понимаю?
← →
Sha © (2004-10-01 09:44) [143]> Defunct
> Буфер поиска - 1Mb.
Многовато будет :) Наиболее частое применение Pos - поиск первого вхождения в строке до 100 символов. В случае успеха в среднем результат поиска не превышает 40. Именно для этих условий и должна проводиться оптимизация. Для других условий пишутся другие функции, которые сравнивать с Pos будет неверно.
> Следует отметить неоспоримое преимущество приведенной здесь
> функции, она в отличие от [120] способна работать на
> процессорах у которых нет MMX.
По приведенной мной ссылке ты можешь найти реализации Pos на любой вкус.
> ни старая, ни исправленная функции не выходили за границу буфера.
Извини, значит, я был недостаточно внимателен. Тогда пункты 4 и 5 снимаются.
> посмотрел тест [137] недостаток теста в том, что он был
> нацелен именно, на поиск подстроки в строке. Функция же [139]
> больше нацелена на поиск подстроки в файле, т.е.
> предполагается просмотр не одного буфера а немкольких
Вот это я совсем не понял.
> SubBench1 относится к маленьким строкам я правильно понимаю?
Поиск малых строк среди малых строк (первые 35 тестов).
← →
Defunct © (2004-10-01 10:27) [144]> посмотрел тест [137] недостаток теста в том, что он был
> нацелен именно, на поиск подстроки в строке. Функция же [139]
> больше нацелена на поиск подстроки в файле, т.е.
> предполагается просмотр не одного буфера а немкольких
Имел в виду, что тест не полностью отражает возможности функций. Не учитывается скорость поиска в больших см. сабж до 1Gb строках.
> Поиск малых строк среди малых строк (первые 35 тестов).
Я так и думал. Крутил и так и сяк, на малых строках существенно проигрываю, PosJoh и PosSha. (в PosJoh заметил ведется отдельная обработка маленьких строк)
Зато на больших строках получилось обогнать все функции:
просматриваемый буфер делится на 2 кадра, в каждом кадре просмотр ведется в двух направлениях.
> Для других условий пишутся другие функции, которые сравнивать с Pos будет неверно.
согласен, но так или иначе, даже с оптимизацией совсем под другую задачу (сабж) результат сравнения с Pos тоже не плох, индекс 416 (как я понял в 3 раза быстрее стандартной Pos) по вашему тесту дают не многие функции.
← →
Sha © (2004-10-01 10:41) [145]> Defunct © (01.10.04 10:27) [144]
> Зато на больших строках получилось обогнать все функции
Наверное, точнее так: на больших строках с образом в конце.
Не забывай, что просто для таких строк Джон еще не написал свою функцию :)
PS. Твой результат действительно очень хорош.
Не желаешь принять участие в FastCode?
← →
Defunct © (2004-10-01 11:44) [146]> Не желаешь принять участие в FastCode?
на тему?
← →
Sha © (2004-10-01 11:52) [147]Тем там много...
Можно заново открыть PosChallenge, если ты усовершенствуешь свою функцию.
Кстати, было бы неплохо выложить здесь окончательный вариант.
← →
Defunct © (2004-10-01 12:01) [148]> Тем там много...
это хорошо
> Кстати, было бы неплохо выложить здесь окончательный вариант.
Не вопрос, как только закончу, и тест покажет что функция прошла Validate тест сразу выложу.
← →
GuAV © (2004-10-01 20:32) [149]
> функция прошла Validate
вот, например
const S1="AV"; S2="Guru AV";
procedure TForm1.Button1Click(Sender: TObject);
begin
Caption := Format("Sha = %d, Pos = %d, defunct = %d",
[PosShaPas(S1, S2), Pos(S1, S2), ConstantPos(S1, S2)]);
// Sha = 6, Pos = 6, defunct = 0
end;
← →
Alekc (2004-10-01 20:38) [150]Кто-то спрашивал почему у борланда такие неоптимальные функции: если тут столько народу одну Pos так долго оптимизирует, то сколько б времени у Borland"ы ушло на всё RTL/VCL ? 10 лет ? :о)
← →
Defunct © (2004-10-02 01:50) [151]> Sha
Я не понимаю, что я делаю не так, для маленьких строк никак не могу улучшить показания теста. Привожу функцию, которая прошла все 11 Validate тестов. Гляньте, может заметите, что там не так при маленьких строках. На больших строках эта функция побила все, в т.ч. и PosJohMMX_a.Function ConstantPos(const Constant, Buffer: string): Integer; Assembler;
Asm
Test eax, eax
Jz @@NotFound_Exit {Exit if SubStr = ""}
Test edx, edx
Jz @@NotFound_Exit {Exit if Str = ""}
Mov ECx, [EDx-4]
Test ECx, ECx
Jz @@NotFound_Exit
Cmp [EAx-4],1
Jnz @@WideSearch
Cmp ECx,8
Ja @@WideScan
// CharPos
@@Scan4:
Mov Al,[EAx]
Push EDi
Add EDx, ECx
Xchg EDi, EDx
Mov EDx, ECx
Not ECx
Inc ECx
@@SLoop4:
Cmp AL, [EDi+ECx]
Jz @@Found4
Inc ECx
Jnz @@SLoop4
Xor EAx, EAx
Pop EDi
Ret
@@Found4:
Mov EAx, EDx
Add EAx, ECx
Inc EAx
Pop EDi
Ret
@@WideScan:
Mov Al,[EAx]
Mov Ah, Al // Spreading char to 32bit register
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
Push ECx
@@Scan5:
MovQ MM7, [EDx] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
PACKSSWB MM7, MM7
MovD EAx, MM7 // get mixed dword
Test EAx, EAx // was there at least 1 bit set?
Jnz @@CharFound2 // yes - 1st char of the constant was found
Add EDx,8 // correct index
Sub ECx,8 // and buffer size
Jns @@Scan5 // continue scan if buffer not empty
@@Exit_False2:
Emms
Pop EAx
Xor EAx, EAx
Ret
@@CharFound2:
MovQ MM7, [EDx] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
MovD EAx, MM7
Test EAx, EAx
Jnz @@Loop2
Sub ECx,4
PSRLQ MM7,32
MovD EAx, MM7
@@Loop2:
Dec Ecx
Test Al,Al
Js @@Check2
Shr EAx,8
Jmp @@Loop2
@@Check2:
Test ECx,ECx
Js @@Exit_False2
Emms
Pop EAx
Sub EAx, ECx
Ret
@@WideSearch:
Push EDi
Push ESi
Push EBx
Push EBp
MOV ESI, EAX // ESi pointer to constant
Mov EDi, EDx // EDi pointer to buffer
Push ECx // store total buffer size for later calculation pos
Mov EBX, [ESI-4]
Test EBx, EBx
Jz @@Exit_False
Mov Al, [ESi] // Store first char of the constant in AL
Cmp EBx, ECx
Ja @@Exit_False
Jnz @@Normal_Work
Cmp AL, [Edi]
Jnz @@Exit_False
@@Normal_Work:
Dec EBX
Mov Ah, [ESi+EBx] // Store last char of the constant in AH
Dec EBx
Mov EDx,ECx // EDx - Stored residual buffer size
Inc ESi
Mov EBp, ESi // EBp - stored pointer to 2nd char of constant
Cmp ECx, 8
Ja @@Wide_String
@@Scan3:
Xor ECx, ECx
@@SLoop:
Cmp AL, [Edi+ECx]
Jz @@Found
Inc ECx
Cmp ECx, EDx
Jb @@SLoop
Jmp @@Exit_False
@@Found:
Inc ECx
Add EDi,ECx
Sub EDx, ECx
Mov ECx, EDx
Cmp EBx, EDx
Jge @@Exit_False
Jmp @@CheckLastChar
{}
@@Wide_String:
MovD MM4, EAx // store EAx in MM buffer
Mov Ah, Al // Spreading char to 32bit register
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
PXOR MM5,MM5 // Z mask for later calculations
@@Scan:
MovQ MM7, [Edi] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
PACKSSWB MM7,MM7
MovD EAx, MM7 // get mixed dword
Test EAx, EAx // was there at least 1 bit set?
Jnz @@CharFound // yes - 1st char of the constant was found
Add EDi,8 // correct index
Sub ECx,8 // and buffer size
Jns @@Scan // continue scan if buffer not empty
Jmp @@Exit_False // otherwise - leave with no result
@@CharFound:
MovQ MM7, [Edi] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
MovD EAx, MM7
Test EAx, EAx
Jnz @@Loop1
Add EDi,4
Sub ECx,4
PSRLQ MM7,32
MovD EAx, MM7
@@Loop1:
inc EDi
dec Ecx
Test Al,Al
Js @@Check
Shr EAx,8
Jmp @@Loop1
@@Check:
MovD EAx, MM4 // restore EAx (1st and last chars of the constant)
@@CheckLastChar: // as proposed in Boyer-Mur alhorithm
Mov EDx, ECx // store new residual buffer size
Test EDx, EDx
Js @@Exit_False
Test EBx, EBx
Js @@Constant_Exists
Cmp Ah, [EBx+Edi] // check found substring with last char of the constant
Jz @@CompareWholeString // not match - continue searching
Cmp EDx,8
Jnb @@Scan
Jmp @@Scan3
@@Exit_False:
Pop EAx
Xor EAx,EAx // False = (0), check delphi help for more info
Jmp @@Leave_Proc
@@NotFound_Exit:
Xor EAx, EAx
Ret
@@CompareWholeString:
Test EBx, EBx
Jz @@Constant_Exists
Cmp EDx, EBx // constant still can be settled in buffer
Jna @@Exit_False // no - exit with false result
Push EDi
Mov ECx, Ebx // ECx - constant chars amount
shr ECx, 2 // ECx - constant chars amount div 4
jz @@SkipDTest
Repe CmpsD
Jnz @@SkipBTest
@@SkipDTest:
Mov ECx, Ebx
and ECx, 3
jz @@Constant_Exists2 // two least significant bits
// of amount are zero so the Constant matches
Repe CmpsB
Jz @@Constant_Exists2
@@SkipBTest:
Pop EDi
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
Cmp EDx,8
Jb @@Scan3
Jmp @@Scan
@@Constant_Exists2:
Add ESp, 4
@@Constant_Exists:
Pop EAx
Sub EAx, EDx
@@Leave_Proc:
EMMS // finish mmx operations
Pop EBp
Pop EBx
Pop ESi
Pop EDi
End;
← →
Sha © (2004-10-02 11:18) [152]>Defunct © (02.10.04 01:50) [151]
1. Главное, что отличает функцию-победитель от других - очень быстрая выдача результата в случае нахождения образца в первых 8 позициях после начала сканирования первого символа. Анализ этих позиций вынесен из цикла и проводится очень быстро. Это позволяет отложить подготовительные действия для организации цикла (и сам цикл) до тех пор пока они действительно не потребуются, или иногда вообще их не выполнять.
В результате, даже, если даже цикл и будет выполняться, то будет сэкономлено несколько команд перехода и насыщение цикла наступит позднее.
Также имей ввиду, что использование MMX для строк короче 20 сиволов неоправданно из-за больших расходов на подготовку.
2. В следующем цикле@@SLoop4:
Cmp AL, [EDi+ECx]
Jz @@Found4
Inc ECx
Jnz @@SLoop4
имеет смысл "inc ecx" заменить на "add ecx,1". После такой замены состояние регистра флагов для второго сравнения будет полностью определяться предыдущей командой, а не формироваться как результат выполнения cmp и inc.
Еще лучше развернуть цикл в 2 или 4 раза.
3. Этот цикл тоже лучше развернуть.@@SLoop:
Cmp AL, [Edi+ECx]
Jz @@Found
Inc ECx
Cmp ECx, EDx
Jb @@SLoop
← →
GuAV © (2004-10-02 15:33) [153]так имхо немного быстрее будет CompareWholeString -
поиск в обратном порядке.@@CompareWholeString:
Test EBx, EBx
Jz @@Constant_Exists
Cmp EDx, EBx // constant still can be settled in buffer
Jna @@Exit_False // no - exit with false result
// Push EDi
MOV ECX, EBX
@@CW_Loop:
SUB ECX, 4
JZ @@CW_LastDWord
JL @@CW_Last123bytes
MOV EAX, [ESi+ECx]
CMP EAX, [EDi+ECx]
JNE @@SkipBTest
JMP @@CW_Loop
@@CW_LastDWord:
MOV EAX, [ESi]
CMP EAX, [EDi]
JNE @@SkipBTest
JMP @@Constant_Exists
@@CW_Last123bytes:
ADD ECX, 2
JZ @@Last2
JNS @@Last3
JS @@Last1
@@Last3:
MOV AX, [ESi]
CMP AX, [EDi]
JNE @@SkipBTest
MOV AL, [ESi+2]
CMP AL, [EDi+2]
JNE @@SkipBTest
JMP @@Constant_Exists
@@Last2:
MOV AX, [ESi]
CMP AX, [EDi]
JNE @@SkipBTest
JMP @@Constant_Exists
@@Last1:
MOV AX, [ESi]
CMP AX, [EDi]
JNE @@SkipBTest
JMP @@Constant_Exists
@@SkipBTest:
// Pop EDi
// 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
Cmp EDx,8
Jb @@Scan3
Jmp @@Scan
@@Constant_Exists:
Pop EAx
Sub EAx, EDx
← →
GuAV © (2004-10-02 15:43) [154]
> @@Last1:
> MOV AX, [ESi]
> CMP AX, [EDi]
> JNE @@SkipBTest
> JMP @@Constant_ExistsMOV AL, [ESi] // Of course a byte-sized operand is meant
CMP AL, [EDi] // That"s a kinda ctrl-C+ctrl-V eror :)
← →
Sha © (2004-10-02 18:31) [155]> GuAV
Сейчас я сижу за K6 и не могу проверить скорость на P4,
но два перехода подряд приводят к потерям тактов.
← →
GuAV © (2004-10-02 18:34) [156]Sha © (02.10.04 18:31) [155]
ок. не знал. у меня целерон. ща оптимизирую.
← →
GuAV © (2004-10-02 18:50) [157]Вот... тестить ща не могу... могут быть ошибки..
@@CompareWholeString:
Test EBx, EBx
Jz @@Constant_Exists
Cmp EDx, EBx // constant still can be settled in buffer
Jna @@Exit_False // no - exit with false result
// Push EDi
MOV ECX, EBX
@@CW_Loop:
SUB ECX, 4
JL @@CW_Last123bytes
MOV EAX, [ESi+ECx]
JZ @@CW_LastDWord // SUB ECX, 4 result was 0
CMP EAX, [EDi+ECx]
JE @@CW_Loop
Mov ECx, EDx
JMP @@SkipBTest1
@@CW_LastDWord:
// MOV EAX, [ESi]
CMP EAX, [EDi]
JE @@Constant_Exists
Mov ECx, EDx
JMP @@SkipBTest1
@@CW_Last123bytes:
ADD ECX, 2
JS @@Last1
// JNS @@Last3
@@Last3:
MOV AX, [ESi]
JZ @@Last2
CMP AX, [EDi]
JNE @@SkipBTest
MOV AL, [ESi+2]
CMP AL, [EDi+2]
JE @@Constant_Exists
Mov ECx, EDx
JMP @@SkipBTest1
@@Last2:
// MOV AX, [ESi]
CMP AX, [EDi]
JE @@Constant_Exists
Mov ECx, EDx
JMP @@SkipBTest1
@@Last1:
MOV AL, [ESi]
CMP AL, [EDi]
//JNE @@SkipBTest
JE @@Constant_Exists
@@SkipBTest:
// Pop EDi
// 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
@@SkipBTest1: // Mov ECx, EDx moved to places to jump from
Cmp EDx,8
Jb @@Scan3
Jmp @@Scan
← →
GuAV © (2004-10-03 00:34) [158]
@@WideScan:
Mov Al,[EAx]
Mov Ah, Al // Spreading char to 32bit register
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
Push ECx
@@Scan5:
MovQ MM7, [EDx] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
PACKSSWB MM7, MM7
MovD EAx, MM7 // get mixed dword
Test EAx, EAx // was there at least 1 bit set?
Jnz @@CharFound2 // yes - 1st char of the constant was found
Add EDx,8 // correct index
Sub ECx,8 // and buffer size
Jns @@Scan5 // continue scan if buffer not empty
тут, в слуаче ECx<8 выход за пределы буфера, причём аж до 7 байт.
при Validate test надо делать как нибудь чтобы нельзя было читать из S[Length(S)+1], где S это и Constant и Buffer
У меня сейчас две идеи: или Break Point на чтение данных или VirtualProtect...
возможно с WideSearch то же, этого кода я вообще не понял...
← →
Sha © (2004-10-03 08:33) [159]GuAV © (03.10.04 00:34) [158]
Я делал проверку через VirtualProtect в одном из Challenge, не помню в каком. Надо порыться... Позже...
← →
Sha © (2004-10-03 11:35) [160]> GuAV © (03.10.04 00:34) [158]
> тут, в слуаче ECx<8 выход за пределы буфера, причём аж до 7 байт.
Я тут по такому случаю написал еще одну процедуру проверки.
Поразительно, но данный тест ConstantPos проходит.
Разберусь в понедельник если время будет, сейчас еду на дачу.//Protect/unprotect 4k-block at the end of string
procedure SetStringProtected(var s: string; var flags: dword);
const
block= 4*1024;
var
p, q: pchar;
begin
if (flags and PAGE_NOACCESS)<>0
then begin;
SetLength(s,3*block);
FillChar(s[1],Length(s),0);
end;
p:=pointer(s);
integer(q):=(integer(p) and -block) + 2*block;
if (flags and PAGE_NOACCESS)<>0
then pinteger(p-4)^:=(q-p)-1 //Trunk the string
else pinteger(p-4)^:=3*block; //Restore string length
VirtualProtect(pchar(q),1,flags,@flags); //Set protection flags
end;
function TMainForm.Validate0: boolean;
var
s: string;
p: pchar;
q: pointer;
flags: dword;
len: integer;
begin;
flags:=PAGE_NOACCESS;
SetStringProtected(s, flags);
try
len:=Length(s); //Now Length(s)>4k.
s[len-0]:="h";
s[len-1]:="g";
s[len-2]:="f";
s[len-3]:="e";
s[len-4]:="d";
s[len-5]:="c";
s[len-6]:="b";
s[len-7]:="a";
Result:=(PosFunction("abcdefgh", s)=len-7)
and (PosFunction("bcdefgh", s)=len-6)
and (PosFunction("cdefgh", s)=len-5)
and (PosFunction("defgh", s)=len-4)
and (PosFunction("efgh", s)=len-3)
and (PosFunction("fgh", s)=len-2)
and (PosFunction("gh", s)=len-1)
and (PosFunction("h", s)=len-0)
and (PosFunction("abcdefg9", s)=0)
and (PosFunction("bcdefg9", s)=0)
and (PosFunction("cdefg9", s)=0)
and (PosFunction("defg9", s)=0)
and (PosFunction("efg9", s)=0)
and (PosFunction("fg9", s)=0)
and (PosFunction("g9", s)=0)
and (PosFunction("9", s)=0)
and (PosFunction("9h", s)=0)
and (PosFunction("9gh", s)=0)
and (PosFunction("9fgh", s)=0)
and (PosFunction("9efgh", s)=0)
and (PosFunction("9defgh", s)=0)
and (PosFunction("9cdefgh", s)=0)
and (PosFunction("9bcdefgh", s)=0);
//Construct the string inplace.
p:=pchar(pointer(s))+(len+1-8); //Set address
pInteger(p-4)^:=7; //Set length
pInteger(p-8)^:=1; //Set reference count
q:=p;
Result:=Result
and (PosFunction("bcdefgh", string(q))=1)
and (PosFunction("cdefgh", string(q))=2)
and (PosFunction("defgh", string(q))=3)
and (PosFunction("efgh", string(q))=4)
and (PosFunction("fgh", string(q))=5)
and (PosFunction("gh", string(q))=6)
and (PosFunction("h", string(q))=7)
and (PosFunction("bcdefg9", string(q))=0)
and (PosFunction("cdefg9", string(q))=0)
and (PosFunction("defg9", string(q))=0)
and (PosFunction("efg9", string(q))=0)
and (PosFunction("fg9", string(q))=0)
and (PosFunction("g9", string(q))=0)
and (PosFunction("9", string(q))=0)
and (PosFunction("9h", string(q))=0)
and (PosFunction("9gh", string(q))=0)
and (PosFunction("9fgh", string(q))=0)
and (PosFunction("9efgh", string(q))=0)
and (PosFunction("9defgh", string(q))=0)
and (PosFunction("9cdefgh", string(q))=0);
except
Result:=false;
end;
SetStringProtected(s, flags);
if Result then begin;
ErrorEdit0.Text := "Passed Validate0";
ErrorEdit0.Color := clGreen;
end
else begin;
ErrorEdit0.Text := "Failed Validate0";
ErrorEdit0.Color := clRed;
end;
Update;
end;
← →
GuAV © (2004-10-03 12:46) [161]Ха. этот тест функция Defunct проходит.
Нужно запретить к части данных находящейся не по смещению кратному 8 от начала строки. Лучше даже не кратному 4.
← →
Sha © (2004-10-04 00:39) [162]GuAV © (03.10.04 12:46) [161]
По смещению 4 тоже проходит. Можешь убедиться, если добавишь такой код:
p:=pchar(pointer(s))+(len+1-4);
pInteger(p-4)^:=3;
pInteger(p-8)^:=1;
q:=p;
Result:=Result
and (PosFunction("fgh", string(q))=1)
and (PosFunction("gh", string(q))=2)
and (PosFunction("h", string(q))=3)
and (PosFunction("fg9", string(q))=0)
and (PosFunction("g9", string(q))=0)
and (PosFunction("9", string(q))=0)
and (PosFunction("9h", string(q))=0)
and (PosFunction("9gh", string(q))=0)
А доступ по смещению, не кратному 4, запретить нельзя. В Wintel можно запретить доступ к одному или нескольким выровненным на границу 4k блокам размером 4k.
Кроме того, ANSI-строки всегда располагаются менеджером памяти Delphi выровненными на границу слова. Можно конечно вручную сконструировать невыровненную строку, но вряд ли это будет честно :)
← →
GuAV © (2004-10-04 02:22) [163]
> Можно конечно вручную сконструировать невыровненную строку,
> но вряд ли это будет честно :)
А разве выходить за буфер честно ? :)
попробовал жетскую систему допинг котнтроля.
Оказывается, даже если нет 0-терминатора все функции её проходят кроме Defunct и ShaPas. Если есть 0-терминатор, то ShaPas проходит, но Defunct - нет. AV именно там где я ожидал. Вот код:const
block= 4*1024;
type
TBlocks = array[0..2] of array[0..block-1] of Byte;
function ProtectedStringCreate(const Source: string): string;
var
L: Cardinal;
Blocks, AlBlocks: ^TBlocks;
begin
New(Blocks);
AlBlocks:=pointer(integer(@Blocks[1]) and not $FFF);
Result:="";
L:=Length(Source);
Pointer(Result):=@(AlBlocks^[1, 0]);
Dec(integer(Result), L);
PDWORD(integer(Result)-8)^:=1; // Fake Ref Count;
PDWORD(integer(Result)-4)^:=L; // Length
PPointer(integer(Result)-12)^:=Blocks; // Unaligned ptr 2 free
VirtualProtect(@AlBlocks[1, 0], block, PAGE_NOACCESS, PDWORD(integer(Result)-16)^);
Move(Source[1], PDWORD(integer(Result))^, L);
// PBYTE(integer(Result)+L)^:=0; // attempt to write null-terminator should not work
end;
procedure ProtectedStringFree(var S: string);
var
Blocks: ^TBlocks;
begin
Blocks:=PPointer(integer(S)-12)^;
VirtualProtect(@Blocks[1], block, PDWORD(integer(S)-16)^, nil);
FreeMem(Blocks);
Pointer(S):=nil;
end;
function TMainForm.Validate0: boolean;
var
s: string;
p: pchar;
q: pointer;
flags: dword;
len: integer;
begin;
s:=ProtectedStringCreate("12345678abcdefg");
try
Result:=(PosFunction("abcdefg", s)=1+8)
and (PosFunction("bcdefg", s)=2+8)
and (PosFunction("cdefg", s)=3+8)
and (PosFunction("defg", s)=4+8)
and (PosFunction("efg", s)=5+8)
and (PosFunction("fg", s)=6+8)
and (PosFunction("g", s)=7+8)
and (PosFunction("", s)=0)
and (PosFunction("abcdef9", s)=0)
and (PosFunction("bcdef9", s)=0)
and (PosFunction("cdef9", s)=0)
and (PosFunction("def9", s)=0)
and (PosFunction("ef9", s)=0)
and (PosFunction("f9", s)=0)
and (PosFunction("9", s)=0)
and (PosFunction("", s)=0)
and (PosFunction("9", s)=0)
and (PosFunction("9g", s)=0)
and (PosFunction("9fg", s)=0)
and (PosFunction("9efg", s)=0)
and (PosFunction("9defg", s)=0)
and (PosFunction("9cdefg", s)=0)
and (PosFunction("9bcdefg", s)=0);
except
Result:=false;
end;
ProtectedStringFree(s);
if Result then begin;
ErrorEdit0.Text := "Passed Validate0";
ErrorEdit0.Color := clGreen;
end
else begin;
ErrorEdit0.Text := "Failed Validate0";
ErrorEdit0.Color := clRed;
end;
Update;
end;
← →
Sha © (2004-10-04 11:04) [164]> GuAV © (04.10.04 02:22) [163]
> Оказывается, даже если нет 0-терминатора все функции её проходят кроме Defunct и ShaPas.
Отсутствие терминатора означает нарушение формата ANSI-строки.
Сама Delphi считает, что он обязан присутствовать.
Попробуй, например, выполнить такой код:
procedure TMainForm.Button1Click(Sender: TObject);
var
s: string;
begin
s:="abc";
s[4]:="d";
ShowMessage(s);
end;
>> Можно конечно вручную сконструировать невыровненную строку,
>> но вряд ли это будет честно :)
> А разве выходить за буфер честно ? :)
В коде RTL присутствует неявное предположение о выравнивании ANSI-строк на границу.
Во первых менеджер памяти выделяет выровненную память, а префикс строки объявлен следующим образом:
type
PStrRec = ^StrRec;
StrRec = packed record
refCnt: Longint;
length: Longint;
end;
Во-вторых, в коде _LStrCmp из System.pas есть совершенно замечательный кусок:
@@cmpRest:
POP EDX
AND EDX,3
JE @@equal
MOV ECX,[ESI]
MOV EBX,[EDI]
CMP CL,BL
JNE @@exit
DEC EDX
JE @@equal
CMP CH,BH
JNE @@exit
DEC EDX
JE @@equal
AND EBX,$00FF0000
AND ECX,$00FF0000
CMP ECX,EBX
JNE @@exit
Этот кусок используется для сравнения хвостов строк. Можно заметить, что если длина строки равна 4*N+1, то для сравнения одного последнего байта Delphi считывает из памяти двойное слово. Ясно, что этот код безопасен только в том случае, если строки выровнены на границу dword и что вполне допустимо читать двойное слово, содержащее последний значимый байт (не терминатор). Доступ к самому терминатору (и даже следующему за ним байту), естественно, тоже допустим иначе, как создать ANSI-строку).
Только не удалось пока уличить Delphi в доступе ко второму слову в двойном слове, начинающемся с терминатора. Но раз выделено, наверное тоже можно. Хотя ни одна из тестирумых программ этого не делает.
Так что не удастся тебе стать святее Папы Римского:
твой тест не прошла бы даже Delphi RTL :)
← →
Суслик © (2004-10-04 11:07) [165]
> а префикс строки объявлен следующим образом:
>
> type
> PStrRec = ^StrRec;
> StrRec = packed record
> refCnt: Longint;
> length: Longint;
> end;
в пятом дельфи в префиксе еще 4 байта есть.
← →
Sha © (2004-10-04 11:09) [166]читать
(и даже следующему за ним байту для wide-строк)
← →
Sha © (2004-10-04 11:13) [167]> Суслик © (04.10.04 11:07) [165]
> в пятом дельфи в префиксе еще 4 байта есть.
Это длина выделенного блока. Она в 6-ой просто не описана, т.к. при манипуляции со строками не используется. Но она там, естественно осталась, и хакеры могут ее использовать.
← →
Суслик © (2004-10-04 11:15) [168]
> [167] Sha © (04.10.04 11:13)
> Это длина выделенного блока.
Т.е. в этих 4х байтах хранится кол-во выделенных байт плюс к тем 4ем байтам, которые в заголовке выделенного блока хранит дельфовый менеджер памяти?
← →
Суслик © (2004-10-04 11:19) [169]
> Но она там, естественно осталась, и хакеры могут ее использовать.
Вот это мне не понятно. Что значит осталась? Судя по СPU под эти 4 байта память не выделяется.
← →
Sha © (2004-10-04 11:41) [170]> Суслик © (04.10.04 11:19) [169]
Да, действительно, не выделяется.
Похоже, был не прав.
Память подвела :)
← →
Суслик © (2004-10-04 11:50) [171]
> [170] Sha © (04.10.04 11:41)
> > Суслик © (04.10.04 11:19) [169]
>
> Да, действительно, не выделяется.
> Похоже, был не прав.
> Память подвела :)
Мы об этом недавно поспорили с АП - оба оказались правы - в Д5 есть 4 байта, в Д6 - нет. Потому и удивлен вашему ответу.
← →
Defunct © (2004-10-04 12:21) [172]Зы. померял свою функцию [151] на P2, без последних изменений внесенных GuraAV, поимела все функции по Overall Bechmark"у.
ps: насчет выхода за границу буфера ничего страшного в этом, хотя раз уж зашла речь об этом вечером посмотрю, что можно сделать. И выложу новый вариант.
← →
kaZaNoVa © (2004-10-04 12:32) [173]2алл - плиз, выложите окончательный вариант функции - замены POS ;)
- а так у меня в памяти POS пашет ~120 мб/сек .. :))
при скорости винта 20~30 мб/сек, имхо даже у POS потрясающее быстродействие %)))
← →
GuAV © (2004-10-04 14:25) [174]
> Так что не удастся тебе стать святее Папы Римского:
> твой тест не прошла бы даже Delphi RTL :)
Я же сказал, все проходят, кроме Вашей и Defunct, и даже ShowMessage работает! Попробуйте сами.
Defunct © (04.10.04 12:21) [172]
А Вы всё же попробуйте применить их. Ещё быстрее будет. И мой код не читает за буфером.
← →
Sha © (2004-10-04 14:37) [175]> GuAV © (04.10.04 14:25) [174]
Ты не понял, речь о том, что валидацию с твоим вариантом ProtectedStringCreate [163] не пройдет Delphi RTL, а потому он неверный.
← →
Sha © (2004-10-04 14:51) [176]Иными словами, если сама Delphi при работе с ANSI-строками предполагает, что они выровнены на границу двойного слова, читает и записывает терминатор, читает последнее двойное слово, содержащее символы строки, то почему это должно быть запрещено для сторонних строковых функций?
← →
GuAV © (2004-10-04 19:45) [177]Sha © (04.10.04 14:51) [176]
Ок. с нуль терминатором Ваша проходит, но Defunct нет.
Pos из RTL работает.
Что не будет работать искать не буду, поверю на слово.
> они выровнены на границу двойного слова
у Defunct предполагается, что на границу 8. Как Вам это ?
Будет ли тогда мой тест корректным если дать выравинвание на дв. слово но не на четверное и добавить нуль терминатор?
← →
GuAV © (2004-10-04 21:19) [178]Этио создаст DWORD-aligned строку с 0 теминатором, однако фция Defunct не пройдёт
constblock= 4*1024;
type
TBlocks = array[0..2] of array[0..block-1] of Byte;
function ProtectedStringCreate(const Source: string): string;
var
L: Cardinal;
Blocks, AlBlocks: ^TBlocks;
begin
New(Blocks);
AlBlocks:=pointer(integer(@Blocks[1]) and not $FFF);
Result:="";
L:=Length(Source);
Pointer(Result):=@(AlBlocks^[1, 0]);
Dec(integer(Result), L+1);
PDWORD(integer(Result)-8)^:=1; // Fake Ref Count;
PDWORD(integer(Result)-4)^:=L; // Length
PPointer(integer(Result)-12)^:=Blocks; // Unaligned ptr 2 free
VirtualProtect(@AlBlocks[1, 0], block, PAGE_NOACCESS, PDWORD(integer(Result)-16)^);
Move(Source[1], PDWORD(integer(Result))^, L);
PBYTE(integer(Result)+L)^:=0;
ShowMessage(result);
end;
procedure ProtectedStringFree(var S: string);
var
Blocks: ^TBlocks;
begin
Blocks:=PPointer(integer(S)-12)^;
VirtualProtect(@Blocks[1], block, PDWORD(integer(S)-16)^, nil);
FreeMem(Blocks);
Pointer(S):=nil;
end;
function TMainForm.Validate0: boolean;
var
s: string;
p: pchar;
q: pointer;
flags: dword;
len: integer;
begin;
s:=ProtectedStringCreate("1234abcdefg");
try
Result:=(PosFunction("abcdefg", s)=1+4)
and (PosFunction("bcdefg", s)=2+4)
and (PosFunction("cdefg", s)=3+4)
and (PosFunction("defg", s)=4+4)
and (PosFunction("efg", s)=5+4)
and (PosFunction("fg", s)=6+4)
and (PosFunction("g", s)=7+4)
and (PosFunction("", s)=0)
and (PosFunction("abcdef9", s)=0)
and (PosFunction("bcdef9", s)=0)
and (PosFunction("cdef9", s)=0)
and (PosFunction("def9", s)=0)
and (PosFunction("ef9", s)=0)
and (PosFunction("f9", s)=0)
and (PosFunction("9", s)=0)
and (PosFunction("", s)=0)
and (PosFunction("9", s)=0)
and (PosFunction("9g", s)=0)
and (PosFunction("9fg", s)=0)
and (PosFunction("9efg", s)=0)
and (PosFunction("9defg", s)=0)
and (PosFunction("9cdefg", s)=0)
and (PosFunction("9bcdefg", s)=0);
except
Result:=false;
end;
ProtectedStringFree(s);
if Result then begin;
ErrorEdit0.Text := "Passed Validate0";
ErrorEdit0.Color := clGreen;
end
else begin;
ErrorEdit0.Text := "Failed Validate0";
ErrorEdit0.Color := clRed;
end;
Update;
end;
здесь Guru AV выделил место AV :Mov Ah, Al // Spreading char to 32bit register
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
PXOR MM5,MM5 // Z mask for later calculations
@@Scan:
MovQ MM7, [Edi] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
PACKSSWB MM7,MM7
MovD EAx, MM7 // get mixed dword
Test EAx, EAx // was there at least 1 bit set?
Jnz @@CharFound // yes - 1st char of the constant was found
Add EDi,8 // correct index
Sub ECx,8 // and buffer size
Jns @@Scan // continue scan if buffer not empty
Jmp @@Exit_False // otherwise - leave with no result
← →
Defunct © (2004-10-04 21:27) [179]> у Defunct предполагается, что на границу 8. Как Вам это ?
Важна скорость или синтетический AV?
Если вынести проверку вперед (перед чтением, а не после как сейчас), тогда потеряется скорость из-за дергания индекса. Немного ускорил функцию еще на пару процентов, за счет чтения DWORD для маленьких строк, и раскрутки циклов.
2 Sha:
Inc работает быстрее чем Add Reg,1
Inc Inc - быстрее чем Add Reg,2
а вот 3 Inc будет уже медленнее чем Add Reg,3
> Будет ли тогда мой тест корректным если дать выравинвание на дв. слово но не на четверное и добавить нуль терминатор?
вопрос - зачем?
сравните мою раскрутку для маленьких строк, с раскруткой от John [120]:@@Scan4:
Mov Ch,[EAx]
// Ch - char
// EDx - pointer to buffer
// cl - length
@@CharPos:
Mov EAx,[EDx]
Cmp Ch,Al
Jz @Found1
cmp Ch,Ah
Jz @Found2
Shr EAx,16
Cmp Ch,Al
Jz @Found3
Cmp Ch,Ah
Jz @Found4
Cmp Cl,4
Jna @NotFound
Mov EAx,[EDx+4]
Cmp Ch, Al
Jz @Found5
Cmp Ch, Ah
Jz @Found6
Shr EAx, 16
Cmp Ch, Al
Jz @Found7
Cmp Ch, Ah
Jz @Found8
@NotFound:
XOr EAx, EAx
Ret
@Found1:
Mov EAx,1
Jmp @Validation
@Found2:
Mov EAx,2
Jmp @Validation
@Found3:
Mov EAx,3
Jmp @Validation
@Found4:
Mov EAx,4
Jmp @Validation
@Found5:
Mov EAx,5
Jmp @Validation
@Found6:
Mov EAx,6
Jmp @Validation
@Found7:
Mov EAx,7
Jmp @Validation
@Found8:
Mov EAx,8
Jmp @Validation
@Validation:
Cmp Al,Cl
Ja @NotFound
Ret
← →
Defunct © (2004-10-04 21:36) [180]GuAV © (04.10.04 21:19) [178]
Я это рассматривал, следующий вариант пройдет ваш тест, но будет работать медленнее
@@Scan:
Cmp ECx, 8
Jb @@Scan3
MovQ MM7, [Edi] // load a part of buffer that needs to be scaned
...
← →
Defunct © (2004-10-04 21:41) [181][180]
И еще уберете лишний Jump, Jmp в конце цикла установить на начало.
вместо Jns @@Scan - написать Jmp @@Scan, Jmp @@Exit_False выбросить.
только так функция, будет работать на пару процентов медленнее.
← →
Defunct © (2004-10-04 21:55) [182]Еще один забавный факт.. не знаю даже как его проекоментировать.
Новая функция работает быстрее по обеим тестам (как для маленьких строк, так и для больших) причем с приличным отрывом (на 10% быстрее чем PosJoh-MMX для малых строк и 20% - для больших, в 4.5 раза быстрее чем PosRTL) чем все функции в тесте на процессорах:
P-MMX
P2-MMX
P3-Coppermine
Celeron (P3)-Coppermine
НО, САМОЕ ИНТЕРЕСНОЕ, НА P4-HT функция почему-то проигрывает примерно на 10% на малых строках, а на больших строках отрыв сократился до 5-7% в сравнении с PosJoh-MMX.
Видно что-то я не учел именно под P4..
← →
Sha © (2004-10-04 22:24) [183]> GuAV © (04.10.04 19:45) [177]
> Будет ли тогда мой тест корректным если дать выравинвание на
> дв. слово но не на четверное и добавить нуль терминатор?
Да.
← →
GuAV © (2004-10-04 22:53) [184]Defunct © (04.10.04 21:36) [180]
Таких мест у Вас несколько.
Defunct © (04.10.04 21:55) [182]
> Новая функция работает быстрее по обеим тестам
Какая именно ?
← →
Defunct © (2004-10-04 22:59) [185]> Какая именно ?
[151] с раскрытыми циклами.
← →
Sha © (2004-10-04 23:00) [186]> Defunct © (04.10.04 21:27) [179]
> Важна скорость или синтетический AV?
Если ты пишешь только для себя, то это твое личное дело.
Если для других, то даже ничтожная вероятность AV, перечеркивает твой труд. Вряд ли кто захочет использовать ненадежную фукцию,
когда есть чуть более медленная, но надежная.
> Inc работает быстрее чем Add Reg,1
> Inc Inc - быстрее чем Add Reg,2
> а вот 3 Inc будет уже медленнее чем Add Reg,3
Раньше действительно так было. На современных процессорах inc и add работают одинаково быстро. Однако, add часто предпочтительнее, если надо устранить зависимость регистра флагов от результата предыдущей команды. Обычно это требуется когда inc или dec - предпоследняя команда в цикле.
> сравните мою раскрутку для маленьких строк, с раскруткой от John [120]
На P4 сдвиг - сравнительно медленная U-команда, загрузка - быстрая (UV).
Кроме того, сдвиг подразумевает зависимость последующего кода от результата сдвига, а загрузка позволяет распараллелить выполнение за счет переназначения регистров. Так что сдвиги без необходимости использовать не стоит.
> НО, САМОЕ ИНТЕРЕСНОЕ, НА P4-HT функция почему-то проигрывает
Джон как раз оптимизирует свои программы под P4. Советую приглядеться к его коду.
← →
Sha © (2004-10-04 23:37) [187]Здесь имеется ввиду, что загрузка - пересылка память-регистр (mov reg,[mem])
← →
Defunct © (2004-10-04 23:59) [188]> Если для других, то даже ничтожная вероятность AV, перечеркивает твой труд. Вряд ли кто захочет использовать ненадежную фукцию,
когда есть чуть более медленная, но надежная.
Одно дело ничтожная вероятность AV, другое дело синтетически созданная ситуация, имитирующая AV. Ну да ладно с этим разберусь, там только 2 места с выходом за пределы буфера максимум на 7 байт.
> На современных процессорах inc и add работают одинаково быстро.
А размер?
Add reg32, 1 (5 байт)
Inc reg (1 байт)
> Однако, add часто предпочтительнее, если надо устранить зависимость регистра флагов от результата предыдущей команды.
О какой зависимости идет речь?
Inc/Dec Flags Affected:
The CF flag is not affected. The OF, SF, ZF, AF, and PF flags are set according to the result.
О CF помним, но в циклах, как правило, проверяются SF/ZF так что чихать на зависимоть. С учетом меньшего размера 1 байт против 5-ти, сэкономим время на загрузку другой команды.
> Кроме того, сдвиг подразумевает зависимость последующего кода от результата сдвига, а загрузка позволяет распараллелить выполнение за счет переназначения регистров. Так что сдвиги без необходимости использовать не стоит.
не хватит АЛБ чтобы все распараллелить. в P4 если мне не изменяет память 2 АЛБ (В AMD64 - 3). В раскрученных циклах идет по два сравнения, которые чудесно параллелятся AH/AL без лишних обращений к кешу данных. Этот код [179] работает быстрее чем [120] там где было 8*([cmp reg, rel32],[jz],[dec]). Зависимость от сдвига не играет роли из-за количества физических АЛБ.
Причина замедления, сразу скажу, кроется в поиске подстроки Length(SubString)>1 и Length(S)<8.
← →
Sha © (2004-10-05 00:28) [189]> Defunct © (04.10.04 23:59) [188]
>> На современных процессорах inc и add работают одинаково быстро.
> А размер?
А что размер? Мы оптимизируем скорость, а не экономим несколько байт в exe.
> О какой зависимости идет речь?
> О CF помним, но в циклах, как правило, проверяются SF/ZF так
> что чихать на зависимоть. С учетом меньшего размера 1 байт
> против 5-ти, сэкономим время на загрузку другой команды.
Ты не совсем прав. Partial flags stalls действительно не возникает в случае проверки на равенство. Однако часто проверяется и флаг С - а там уж точно задержка возникнет.
А время загрузки команды в цикле почти всегда значения не имеет.
> В раскрученных циклах идет по два сравнения, которые чудесно
> параллелятся AH/AL без лишних обращений к кешу данных.
> Зависимость от сдвига не играет роли из-за количества
> физических АЛБ.
Оба конвейера будут ждать завершения сдига. Это 3 такта.
> Этот код [179] работает быстрее чем [120] там где было
> 8*([cmp reg, rel32],[jz],[dec]).
Надо бы проверить.
> Причина замедления, сразу скажу, кроется в поиске подстроки
> Length(SubString)>1 и Length(S)<8.
Ну так исправь - и ты победитель :)
← →
GuAV © (2004-10-05 00:41) [190]икто не проверил на Р4 [157] ?
← →
Sha © (2004-10-05 00:45) [191]Так это ж не конец :)
← →
Defunct © (2004-10-05 02:20) [192]> Однако часто проверяется и флаг С - а там уж точно задержка возникнет.
Помним и об этом, поэтому JA/JB после Inc/Dec никогда не используем. Только JZ/JS.
> Ну так исправь - и ты победитель :)
Дык, над этим и работаю в свободное время. ;)
Функция уже ~400 строк, начинаю малость теряться.
GuAV © (05.10.04 00:41) [190]
> никто не проверил на Р4 [157] ?
5 баллов GuruAV! (3-5)% ускорение на больших строках по сравнению с [151] и даже на мелких строках ускорение на лицо - (5-10)%
← →
Defunct © (2004-10-05 04:39) [193]Итак долгожданный победитель заезда ;)
Function ConstantPos(const Constant, Buffer: string): Integer; Assembler;
Asm
Test eax, eax
Jz @@NotFound_Exit
Test edx, edx
Jz @@NotFound_Exit
Mov ECx, [EDx-4]
Test ECx, ECx
Jz @@NotFound_Exit
Cmp [EAx-4],1
Jnz @@WideSearch
Cmp ECx,8
Ja @@WideScan
// CharPos
@@Scan4:
Mov Ch,[EAx]
// Ch - char
// EDx - pointer to buffer
// cl - length
@@CharPos:
Mov EAx,[EDx]
Cmp Ch,Al
Jz @Found1
cmp Ch,Ah
Jz @Found2
Shr EAx,16
Cmp Ch,Al
Jz @Found3
Cmp Ch,Ah
Jz @Found4
Cmp Cl,4
Jna @NotFound
Mov EAx,[EDx+4]
Cmp Ch, Al
Jz @Found5
Cmp Ch, Ah
Jz @Found6
Shr EAx, 16
Cmp Ch, Al
Jz @Found7
Cmp Ch, Ah
Jz @Found8
@NotFound:
XOr EAx, EAx
Ret
@Found1:
Mov EAx,1
Jmp @Validation
@Found2:
Mov EAx,2
Jmp @Validation
@Found3:
Mov EAx,3
Jmp @Validation
@Found4:
Mov EAx,4
Jmp @Validation
@Found5:
Mov EAx,5
Jmp @Validation
@Found6:
Mov EAx,6
Jmp @Validation
@Found7:
Mov EAx,7
Jmp @Validation
@Found8:
Mov EAx,8
Jmp @Validation
@Validation:
Cmp Al,Cl
Ja @NotFound
ret
nop
nop // alignment for better performance
@@SmallScan:
Push ECx
Mov Ch,[EAx]
@@Scan8:
Push ECx
Call @@CharPos
Pop ECx
Test EAx, EAx
Jz @Validation3
Sub Cl, Al
Pop EAx
Sub Al, Cl
Ret
@Validation3:
Sub Cl, 8
Add EDx, 8
Cmp Cl, 0
Jg @@Scan8
Add ESP, 4
Ret
@@LastDword2:
Test ECx, ECx
Js @@Exit_False2
Jz @@Exit_False2
MovD MM7, [EDx] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
MovD EAx, MM7 // get mixed dword
Test EAx, EAx
Jnz @@Loop2
Jz @@Exit_False2
@@WideScan:
Cmp ECx, 16
Jb @@SmallScan
Mov Al,[EAx]
Mov Ah, Al
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
Push ECx
@@Scan5:
MovQ MM7, [EDx]
PCMPEQB MM7, MM6
PACKSSWB MM7, MM7
MovD EAx, MM7
Test EAx, EAx
Jnz @@CharFound2
Add EDx,8
Sub ECx,8
Cmp ECx,4
Jg @@Scan5
Jmp @@LastDword2
@@Exit_False2:
Emms
Pop EAx
Xor EAx, EAx
Ret
@@CharFound2:
MovQ MM7, [EDx]
PCMPEQB MM7, MM6
MovD EAx, MM7
Test EAx, EAx
Jnz @@Loop2
Sub ECx,4
PSRLQ MM7,32
MovD EAx, MM7
@@Loop2:
Dec Ecx
Test Al,Al
Js @@Check2
Shr EAx,8
Jmp @@Loop2
@@Check2:
Test ECx,ECx
Js @@Exit_False2
Emms
Pop EAx
Sub EAx, ECx
Ret
@Small_String:
Cmp ECx, [EAx-4]
Jb @NotFound
Mov Ch, [EAx]
Push ECx
Push EBx
Push ESi
Mov ESi, EAx
Mov EBx,[ESi-4]
Dec EBx
@Scan6:
Push ECx
@Scan7:
Call @@CharPos
Pop ECx
Test EAx, EAx
Jz @Validation2
Sub Cl, Al
Add EDx, EAx
Cmp Cl, Bl
Jb @NotFound2
Push ECx
Mov ECx, EBx
@Loop2:
Mov Al, [ESi+ECx]
Cmp Al, [EDx+ECx-1]
Jnz @Scan7
Loop @Loop2
Pop ECx
Mov Ah, 0
Pop ESi
Pop EBx
Pop EAx
Sub EAx, ECx
ret
@Validation2:
Sub Cl, 8
Add EDx, 8
Cmp Cl, 0
Jg @Scan6
@NotFound2:
Pop ESi
Pop EBx
Add ESp, 4
Xor EAx, EAx
Ret
nop // code alignment
nop
@@WideSearch:
Cmp ECx,32
Jb @Small_String
Push EDi
Push ESi
Push EBx
Push EBp
MOV ESI, EAX
Mov EDi, EDx
Push ECx
Mov EBX, [ESI-4]
Test EBx, EBx
Jz @@Exit_False
Mov Al, [ESi]
Cmp EBx, ECx
Ja @@Exit_False
Jnz @@Normal_Work
Cmp AL, [Edi]
Jnz @@Exit_False
@@Normal_Work:
Dec EBX
Mov Ah, [ESi+EBx]
Dec EBx
Mov EDx,ECx
Inc ESi
Mov EBp, ESi
Cmp ECx, 8
Ja @@Wide_String
@@Scan3:
Push EAx
Mov Ch, Al
Mov EDx, EDi
Call @@CharPos
Mov Ch, 0
Sub ECx, EAx
Add EDi, EAx
Pop EDx
Test EAx,EAx
Jz @@Exit_False
Xchg EAx, EDx
Jmp @@CheckLastChar
nop
nop
@@LastDword:
Test ECx, ECx
Js @@Exit_False
Jz @@Exit_False
MovD MM7, [Edi]
PCMPEQB MM7, MM6
MovD EAx, MM7
Test EAx, EAx
Jz @@Exit_False
Jmp @@Loop1
nop
nop // Aligning code for greater performance
@@Wide_String:
MovD MM4, EAx
Mov Ah, Al
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
@@Scan:
MovQ MM7, [Edi]
PCMPEQB MM7, MM6
PACKSSWB MM7, MM7
MovD EAx, MM7
Test EAx, EAx
Jnz @@CharFound
Add EDi, 8
Mov EAx, Edi
And EAx, 7
Sub EDi,EAx // Aligning index
Sub ECx,8
Add ECx,EAx
Cmp ECx,4
Jnge @@LastDword
@@Scan2:
MovQ MM7, [Edi]
PCMPEQB MM7, MM6
PACKSSWB MM7,MM7
MovD EAx, MM7
Test EAx, EAx
Jnz @@CharFound
Add EDi,8
Sub ECx,8
Cmp ECx,4
Jg @@Scan
Jmp @@LastDword
@@CharFound:
MovQ MM7, [Edi]
PCMPEQB MM7, MM6
MovD EAx, MM7
Test EAx, EAx
Jnz @@Loop1
Add EDi,4
Sub ECx,4
PSRLQ MM7,32
MovD EAx, MM7
@@Loop1:
inc EDi
dec Ecx
Test Al,Al
Js @@Check
Shr EAx,8
Jmp @@Loop1
@@Check:
MovD EAx, MM4
@@CheckLastChar: // as proposed in Boyer-Mur alhorithm
Mov EDx, ECx // store new residual buffer size
Test EDx, EDx
Js @@Exit_False
Test EBx, EBx
Js @@Constant_Exists
Cmp Ah, [EBx+Edi]
Jz @@CompareWholeString
Cmp EDx,4
Jg @@Scan
Jmp @@LastDWord
@@Exit_False:
Pop EAx
Xor EAx,EAx
Jmp @@Leave_Proc
@@NotFound_Exit:
Xor EAx, EAx
Ret
@@CompareWholeString:
Test EBx, EBx
Jz @@Constant_Exists
Cmp EDx, EBx
Jna @@Exit_False
MOV ECX, EBX
@@CW_Loop:
SUB ECX, 4
JL @@CW_Last123bytes
MOV EAX, [ESi+ECx]
JZ @@CW_LastDWord
CMP EAX, [EDi+ECx]
JE @@CW_Loop
Mov ECx, EDx
JMP @@SkipBTest1
@@CW_LastDWord:
CMP EAX, [EDi]
JE @@Constant_Exists
Mov ECx, EDx
JMP @@SkipBTest1
@@CW_Last123bytes:
ADD ECX, 2
JS @@Last1
@@Last3:
MOV AX, [ESi]
JZ @@Last2
CMP AX, [EDi]
JNE @@SkipBTest
MOV AL, [ESi+2]
CMP AL, [EDi+2]
JE @@Constant_Exists
Mov ECx, EDx
JMP @@SkipBTest1
@@Last2:
CMP AX, [EDi]
JE @@Constant_Exists
Mov ECx, EDx
JMP @@SkipBTest1
@@Last1:
MOV AL, [ESi]
CMP AL, [EDi]
JE @@Constant_Exists
@@SkipBTest:
Mov ECx, EDx
@@SkipBTest1:
Cmp EDx,4
Jg @@Scan
Jmp @@LastDWord
@@Constant_Exists2:
Add ESp, 4
@@Constant_Exists:
Pop EAx
Sub EAx, EDx
@@Leave_Proc:
EMMS
Pop EBp
Pop EBx
Pop ESi
Pop EDi
End;
← →
Defunct © (2004-10-05 04:55) [194]Результаты тестирования на P4-2.8
Функция Смещ. SB1 SB2 Overall
PosDef_MMX C 194 139 333
PosShaPas_b 8 194 169 362
PosJOH_MMX_a 4 200 164 364
PosJOH_MMX_b 4 202 162 364
PosShaPas_a 4 198 167 366
PosJOH_SSE_a 4 198 175 373
PosJOH_SSE_b C 198 175 373
PosJOH_IA32_b 0 194 183 377
PosJOH_IA32_a C 197 183 380
PosJOH_SSE2_b 0 213 169 381
PosJOH_SSE2_a 4 214 169 383
PosJOH_PAS_a 4 309 255 564
PosJOH_PAS_b 0 320 250 570
PosDKC65_b 0 366 267 633
PosDKC65_a 8 394 267 661
PosRL1_b C 420 480 900
PosRTL 4 530 628 1158
Результаты тестирования на P2-400:
Функция Смещ. SB1 SB2 Overall
PosDef_MMX C 1168 699 1867
PosJOH_IA32_b 0 1115 964 2079
PosJOH_MMX_a 4 1164 925 2089
PosJOH_MMX_b 4 1176 927 2103
PosJOH_IA32_a C 1128 989 2117
PosShaPas_a 4 1120 1345 2464
PosShaPas_b 8 1111 1386 2497
PosDKC65_b 0 1468 1319 2787
PosDKC65_a 8 1486 1336 2822
PosJOH_PAS_a 4 1512 2009 3521
PosJOH_PAS_b 0 1558 2058 3616
PosRL1_b C 1423 2904 4327
PosRTL 4 1703 3238 4940
PosRTL 4 1721 3224 4945
SB1 - Время прохождения теста работы с маленькими строками (до 8-ми символов)
SB2 - Время прохождения теста работы с большими строками (больше 8-ми символов)
Надеюсь таблица нормально запостится.
← →
Defunct © (2004-10-05 05:06) [195][194] зззз.. так и знал..
Результаты тестирования на P4-2.8
Функция Смещ. SB1 SB2 Overall
PosDef_MMX.......C....194...139...333
PosShaPas_b......8....194...169...362
PosJOH_MMX_a.....4....200...164...364
PosJOH_MMX_b.....4....202...162...364
PosShaPas_a......4....198...167...366
PosJOH_SSE_a.....4....198...175...373
PosJOH_SSE_b.....C....198...175...373
PosJOH_IA32_b....0....194...183...377
PosJOH_IA32_a....C....197...183...380
PosJOH_SSE2_b....0....213...169...381
PosJOH_SSE2_a....4....214...169...383
PosJOH_PAS_a.....4....309...255...564
PosJOH_PAS_b.....0....320...250...570
PosDKC65_b.......0....366...267...633
PosDKC65_a.......8....394...267...661
PosRL1_b.........C....420...480...900
PosRTL...........4....530...628...1158
Результаты тестирования на P2-400:
Функция Смещ. SB1 SB2 Overall
PosDef_MMX.......C....1168...699....1867
PosJOH_IA32_b....0....1115...964....2079
PosJOH_MMX_a.....4....1164...925....2089
PosJOH_MMX_b.....4....1176...927....2103
PosJOH_IA32_a....C....1128...989....2117
PosShaPas_a......4....1120...1345...2464
PosShaPas_b......8....1111...1386...2497
PosDKC65_b.......0....1468...1319...2787
PosDKC65_a.......8....1486...1336...2822
PosJOH_PAS_a.....4....1512...2009...3521
PosJOH_PAS_b.....0....1558...2058...3616
PosRL1_b.........C....1423...2904...4327
PosRTL...........4....1721...3224...4945
вот теперь можно спокойно идти спать с чуством выполненного долга
;)
← →
Sha © (2004-10-05 10:42) [196]> Defunct © (05.10.04 05:06) [195]
Поздравляю! Пора заново открывать PosChallenge.
Кстати, в FastCode намечается StringReplaceChallenge, можешь применить свои наработки там.
← →
GuAV © (2004-10-05 12:19) [197]Defunct © (05.10.04 05:06) [195]
Не всё так однозначно...
PosJOH_SSE_a 4 193 186 379
PosJOH_SSE_b C 198 181 379
PosDefunct 4 220 165 385
PosJOH_MMX_b 4 203 187 390
PosJOH_MMX_a 4 203 192 395
PosJOH_SSE2_a 4 214 187 401
PosJOH_SSE2_b 0 214 187 401
ps: Celeron 2000 MHz Northwood L2=128 kB
Sha © (05.10.04 10:42) [196]
У них там случайно Case-unsensitive Pos нету ?
← →
Sha © (2004-10-05 12:25) [198]> Defunct © (05.10.04 04:39) [193]
Подправь свою функцию, чтобы проходила тест Validation0 (здесь учтены предложения GuAV):
procedure SetStringProtected(var s: string; var flags: dword);
const
block= 4*1024;
var
p, q: pchar;
begin
if (flags and PAGE_NOACCESS)<>0 then SetLength(s,3*block);
p:=pointer(s);
integer(q):=(integer(p) and -block) + 2*block;
if (flags and PAGE_NOACCESS)<>0
then pinteger(p-4)^:=(q-p)-1
else pinteger(p-4)^:=3*block;
VirtualProtect(q,1,flags,@flags);
end;
function ValidateStringProtected(var s: string; LengthToValidate: integer): boolean;
var
len: integer;
p: pointer;
begin;
len:=Length(s);
if ((LengthToValidate and 3)<>3)
or (LengthToValidate<3)
or (LengthToValidate>len-8) then begin;
Result:=false;
exit;
end;
FillChar(s[1],len,0);
s[len-0]:="g";
s[len-1]:="f";
s[len-2]:="e";
s[len-3]:="d";
s[len-4]:="c";
s[len-5]:="b";
s[len-6]:="a";
p:=pchar(pointer(s))+(len-LengthToValidate);
pInteger(pchar(p)-4)^:=LengthToValidate;
pInteger(pchar(p)-8)^:=1;
Result:=(PosFunction("abcdef9", string(p))=0)
and (PosFunction("bcdef9", string(p))=0)
and (PosFunction("cdef9", string(p))=0)
and (PosFunction("def9", string(p))=0)
and (PosFunction("ef9", string(p))=0)
and (PosFunction("f9", string(p))=0)
and (PosFunction("9", string(p))=0)
and (PosFunction("9g", string(p))=0)
and (PosFunction("9fg", string(p))=0)
and (PosFunction("9efg", string(p))=0)
and (PosFunction("9defg", string(p))=0)
and (PosFunction("9cdefg", string(p))=0)
and (PosFunction("9bcdefg", string(p))=0)
and (PosFunction("g", string(p))=LengthToValidate-0)
and (PosFunction("fg", string(p))=LengthToValidate-1)
and (PosFunction("efg", string(p))=LengthToValidate-2)
and ((LengthToValidate=3)
or (PosFunction("defg", string(p))=LengthToValidate-3)
and (PosFunction("cdefg", string(p))=LengthToValidate-4)
and (PosFunction("bcdefg", string(p))=LengthToValidate-5)
and (PosFunction("abcdefg", string(p))=LengthToValidate-6));
end;
function TMainForm.Validate0: boolean;
var
s: string;
flags: dword;
begin;
flags:=PAGE_NOACCESS;
SetStringProtected(s, flags);
try
Result:=ValidateStringProtected(s, 3)
and ValidateStringProtected(s, 7)
and ValidateStringProtected(s, 11)
and ValidateStringProtected(s, 15)
and ValidateStringProtected(s, 1023)
and ValidateStringProtected(s, 1027);
except
Result:=false;
end;
SetStringProtected(s, flags);
if Result then begin;
ErrorEdit1.Text := "Passed Validate0";
ErrorEdit1.Color := clGreen;
end
else begin;
ErrorEdit1.Text := "Failed Validate0";
ErrorEdit1.Color := clRed;
end;
Update;
end;
← →
Sha © (2004-10-05 12:29) [199]> GuAV © (05.10.04 12:19) [197]
> Не всё так однозначно...
про Celeron скоро можно будет забыть
> У них там случайно Case-unsensitive Pos нету ?
Нет. Все, что есть, здесь http://dennishomepage.gugs-cats.dk/FastCodeProject.htm
← →
Defunct © (2004-10-05 13:50) [200]> Поздравляю! Пора заново открывать PosChallenge.
пасиба
GuAV © (05.10.04 12:19) [197]
> Не всё так однозначно...
Попробуйте для Celeron"a найти наилучшее соотношение символов в строке, которое обробатывается как маленькая строка. Поменяйте цифры в сл. коде:
....
Cmp ECx,32
Jb @Small_String
...
...
Cmp ECx, 16
Jb @@SmallScan
Sha © (05.10.04 12:25) [198]
> Подправь свою функцию, чтобы проходила тест Validation0 (здесь учтены предложения GuAV):
Ок вечерком, посмотрю.
← →
GuAV © (2004-10-05 22:15) [201]
> Попробуйте для Celeron"a найти наилучшее соотношение символов
> в строке, которое обробатывается как маленькая строка. Поменяйте
> цифры в сл. коде:
Лучше не становится, только хуже.
ИМХО, ещё быстрее будет, если искать в обратном порядке. Можно сначала что-то типа And ECx, 7 и просмотреть остаток, потом вернуть ECx и сделать And ECx not 7 и искать строку используя ММХ... это ИМХО сделает запрет выхода за буфер проще.... попробую сам сделать... если получится, выложу.
← →
Defunct © (2004-10-05 23:31) [202]> ИМХО, ещё быстрее будет, если искать в обратном порядке.
Не совсем понял вашу идею. Можно пояснить? мы же ищем первое вхождение, а если сканировать в обратном порядке, тогда можно получить неверный результат.
PS: для инициализации MMX требуется значительное время, сканирование целесообразно делать на MMX только для больших строк.
← →
GuAV © (2004-10-06 01:03) [203]
> а если сканировать в обратном порядке, тогда можно получить
> неверный результат
Я сам уже понял, когда написал WideScan а он не хочет проходить валидацию. Вот код, если интересно:
@@WideScan:
Cmp ECx, 16
Jb @@SmallScan
Mov Al,[EAx]
Mov Ah, Al
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
Push EBx
Push ECx
Mov EBx, ECx
And EBx, not 7
And ECx, 7
Jz @@ReverseScan
Xor ECx, ECx
@@RemainingDword:
MovD MM7, [EDx+EBx] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
MovD EAx, MM7 // get mixed dword
Test EAx, EAx
Jnz @@FoundInDWord
Add ECx, 4
Jna @@ReverseScan
MovD MM7, [EDx+EBx+4] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
MovD EAx, MM7 // get mixed dword
Test EAx, EAx
Jnz @@FoundInDWord
Jmp @@ReverseScan
@@FoundInDWord:
Inc Ecx
Test Al,Al
Js @@InDWord_pos
Shr EAx,8
Jmp @@FoundInDWord
@@InDWord_pos:
Emms
Pop EAx
Test ECx, ECx
Js @@InDWord_Failed
Mov EAx, ECx
Add EAx, EBx
Pop EBx
Ret
@@InDWord_Failed:
Xor EAx, EAx
Pop EBx
Ret
@@ReverseScan:
Mov ECx, EBx
@@ScanLoop:
Sub ECx, 8
Js @@ScanLoopExit
MovQ MM7, [EDx+ECx]
PCMPEQB MM7, MM6
PACKSSWB MM7, MM7
MovD EAx, MM7
Test EAx, EAx
Jz @@ScanLoop
@@ScanLoopFound:
MovQ MM7, [EDx+ECx]
PCMPEQB MM7, MM6
MovD EAx, MM7
Test EAx, EAx
Jnz @@SLFoundInDword
Add ECx,4
PSRLQ MM7,32
MovD EAx, MM7
@@SLFoundInDword:
Inc Ecx
Test Al,Al
Js @@SLInDWord_pos
Shr EAx,8
Jmp @@SLFoundInDword
@@SLInDWord_pos:
Mov EAx, ECx
Pop ECx
Pop EBx
Emms
Ret
@@ScanLoopExit:
Pop ECx
Pop EBx
Xor EAx, EAx
Emms
Ret
← →
Ihor Osov'yak © (2004-10-06 01:06) [204]Ребята, влом отслеживать полет изменений кода.. :-)
Если можно, полный код в студию...
← →
GuAV © (2004-10-06 01:16) [205]Ihor Osov"yak © (06.10.04 01:06) [204]
пока что [193]. Однако он ещё не проходит тест на выход из буфера.
[203] - я привел ошибочный код. как сейчас понял зря.
← →
Ihor Osov'yak © (2004-10-06 01:20) [206]2 [205] GuAV © (06.10.04 01:16)
ок, либо подожду, либо когда-то повожусь с вашим кодом. может. если будет время и энтузиазм..
← →
GuAV © (2004-10-06 01:28) [207]Хотя в тесте от Sha тоже ошибка. Или фича. Мы ведь договорились, что строка начинается на границе двойного слова или как ? [183]
Видимо прийдётся делать Validate для Validate 0 8-))
← →
Ihor Osov'yak © (2004-10-06 01:49) [208]2 [207] GuAV © (06.10.04 01:28)
ну, иногда лучше перебдить, чем недобдить..
Предположим фантастический вариант - я содал тело строки ручками.. не на границе двойного слова. И передал как параметр.. :-)
Лично я не сторонник таких финтов, но в принцыпе такое может быть. Поэтому я бы дал предпочтение функции, прошедшей валидацию от Sha.
← →
GuAV © (2004-10-06 01:58) [209]Тогда берите любую функцию от JOH. Они прошли даже мой агрессивный тест, когда даже к 0-терминатору обратится нельзя.
← →
GuAV © (2004-10-06 02:07) [210]Хотя поскольку ошибка приведёт AV именно в месте его причины, а не далеко после процедуры можно просто завернуть её в
try... except on EAccesViolation do Result:=0 end;
Этот код может кому-то не понравится, но он нужен только в случае вольностей упомянутых в [208], в "нормальном" режиме функция не приводит к AV.
← →
GuAV © (2004-10-06 03:12) [211]Тут появиась мысль, ка сделать фцию, проходящую любые подобные validate0. Надо сделать вначале test edx, 3; jnz odd_align и там обработать такую ситуацию, обработав эти 1..3 байт и вернуться. Код обработки может быть и не оптимальным, лишь бы он корректно работал.
← →
Sha © (2004-10-06 09:47) [212]> GuAV © (06.10.04 01:28) [207]
> Хотя в тесте от Sha тоже ошибка. Или фича. Мы ведь
> договорились, что строка начинается на границе двойного слова или как ? [183]
У меня так и сделано.
Длина строки = 4n+3.
Конец строки (терминатор) фиксирован на нижней границе страницы.
Начало строки плавает. Но всегда находится на грацице двойного слова.
← →
Sha © (2004-10-06 09:48) [213]Конец строки (терминатор) фиксирован на верхней границе страницы.
← →
GuAV © (2004-10-06 12:13) [214]Sha © (06.10.04 09:47) [212]
Я поняла в чём дело.Call @@CharPos
Отсюда вход с not alined EDX.
← →
GuAV © (2004-10-06 12:13) [215]Sha © (06.10.04 09:47) [212]
Я понял в чём дело.Call @@CharPos
Отсюда вход с not alined EDX.
← →
Defunct © (2004-10-06 16:33) [216]>Sha [198]
Функция [193] прошла тест [198] так что можете смело использовать.
> Ihor Osov"yak © (06.10.04 01:06) [204]
[193] - полный рабочий вариант кода.
[195] - тесты PosDef_MMX = [193]
← →
Sha © (2004-10-06 17:02) [217]> Defunct © (06.10.04 16:33) [216]
> Функция [193] прошла тест [198] так что можете смело использовать.
На моем компьютере не проходит.
← →
Defunct © (2004-10-06 17:25) [218]> Sha
хм..
if Validate0 {[198]} and
Validate1 and
Validate2 and
Validate3 and
Validate4 and
Validate5 and
Validate6 and
Validate7 and
Validate8 and
Validate9 and
Validate10 and
Validate11 then
PosDef_MMX Passed
Если вас не затруднит, можете посмотреть где именно происходит выход за границу последнего Dword, потому как проверял на разных компах, везде проходит. (сам я не могу найти).
← →
Sha © (2004-10-06 17:43) [219]> Defunct © (06.10.04 17:25) [218]
> if Validate0 {[198]} and
Такой if встречается в 2-х местах (Validate & ValidateAll).
Исправил оба?
> Если вас не затруднит, ...
Давай на "ты". Конечно, посмотрю. Но чуть позже.
← →
Defunct © (2004-10-06 17:51) [220]> Такой if встречается в 2-х местах (Validate & ValidateAll).
Исправил оба?
Исправил только ValidateAll,
все теперь порядок, вижу где выходит.
сейчас подправлю.
← →
Jeer © (2004-10-06 18:04) [221]Грандиозно мужики !
Живо мне напомнило успешные попытки втиснуть в 64K и добиться нужного быстродействия для бортового компьютера на i8080 (580)
решения навигационных задач подводного средства движения в далекие 70-е годы.
Так держать !
← →
Defunct © (2004-10-06 18:07) [222]Или я что-то там не понял, или тест работает не совсем корректно.
Хочу немного уточнить задачу.
Допустим строка из одного символа "a", она ведь поидее выровняна до DWord т.е. реальная длинна = |-8| + 4 = 12
-8 Dword
-4 Dword
0 "a"
1 0
2 мусор
3 мусор
У меня происходит чтение строки
@CharPos:
Mov EAx, [EDx]
за DWord выхода нет, но Validation0 вызывает исключение именно на этой строчке. Поставил проверку на 0 (думал может туда случайно проходит вызов при буфере = 0) ничего не изменилось.
← →
Sha © (2004-10-06 18:13) [223]> Defunct
Ломается при таком обращении ConstantPos("ef9","efg").
Первая пересылка@@Scan4:
Mov Ch,[EAx]
проходит нормально, т.к. адрес в edx выровнен.
При заходе на вторую пересылку адрес в edx уже на 1 больше.
Старший байт читаемого слова лежит на защищенной странице => AV.
← →
Sha © (2004-10-06 18:18) [224]Defunct © (06.10.04 18:07) [222]
Строку из одного "a" тест никогда не генерирует.
В тесте используются строки длиной 4*n+3 - они с учетом
терминатора всегда занимают целое число двойных слов.
← →
Defunct © (2004-10-06 18:26) [225]Еще один загадочный эксепшин. Идет проверка, не выходит ли подстрока за границу буфера, и если не выходит, тогда происходит сканирование в обратном порядке (с конца строки). Опять же Exception?
Cmp Cl, Bl <-- проверка на выход за границу буфера
Jb @NotFound2 <-- буфер меньше длинны подстроки - выход
Push ECx
Mov ECx, EBx
@Loop2:
Mov Al, [ESi+ECx]
Cmp Al, [EDx+ECx-1] <--- Exceptoin здесь
Jnz @Scan7
Loop @Loop2
100% где-то в тесте что-то не учтено.
← →
Sha © (2004-10-06 18:27) [226]в Sha © (06.10.04 18:13) [223] случайно выкусил не тот код.
Ошибка происходит, там где ты ее нашел.
← →
Defunct © (2004-10-06 18:29) [227]> При заходе на вторую пересылку адрес в edx уже на 1 больше.
Понял
← →
Sha © (2004-10-06 18:32) [228]> Defunct © (06.10.04 18:26) [225]
> 100% где-то в тесте что-то не учтено.
При этом хорошо бы еще сказать что именно не учтено :)
Давай начнем с исправления очевидной ошибки в ConstantPos("ef9","efg");
← →
GuAV © (2004-10-06 22:19) [229]Такой WideScan не вылазит за буфер ни на байт.
Имхо надо сделать остальное типа так же.@@WideScan:
Cmp ECx, 16
Jb @@SmallScan
Mov Al,[EAx]
Mov Ah, Al
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
Push EBx
Push EDx
Mov EBx, ECx
And EBx, not 7
Add EBx, EDx
@@WSc_Scan5:
MovQ MM7, [EDx]
PCMPEQB MM7, MM6
PACKSSWB MM7, MM7
MovD EAx, MM7
Test EAx, EAx
Jnz @@WSc_QFound
Add EDx, 8
Cmp EDx, EBx
Jl @@WSc_Scan5
Mov EBx, ECx
And EBx, 7 // is anything left ?
Jz @@WSc_Done
Test EBx, 4 // dword or more left ?
Jz @@WSc_Last123
@@WSc_LastDword2:
MovD MM7, [EDx] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
MovD EAx, MM7 // get mixed dword
Test EAx, EAx
Jnz @@WSc_DFound
Add EDx, 4
@@WSc_Last123:
MovD EAx, MM6 // no MMX anymore
Test EBx, 2
Jz @@WSc_LastOne
Cmp AL, [EDx]
Jz @@WSc_AtLast1
Inc EDx
Cmp AL, [EDx]
Jz @@WSc_AtLast1
Inc EDx
@@WSc_LastOne:
Test EBx, 1
Jz @@WSc_Done
Cmp AL, [EDx]
Jz @@WSc_AtLast1
@@WSc_Done:
Pop EDx
Xor EAx, EAx
Pop EBx
Emms
Ret
@@WSc_AtLast1:
Inc EDx
@@WSc_AtLast:
Mov EAx, EDx
Pop EDx
Sub EAx, EDx
Pop EBx
Emms
Ret
@@WSc_QFound:
MovQ MM7, [EDx]
PCMPEQB MM7, MM6
MovD EAx, MM7
Test EAx, EAx
Jnz @@WSc_DFound
Add EDx,4
PSRLQ MM7,32
MovD EAx, MM7
@@WSc_DFound:
Inc EDx
Test EAx, $000000FF
Jnz @@WSc_AtLast
Inc EDx
Test EAx, $0000FF00
Jnz @@WSc_AtLast
Inc EDx
Test EAx, $00FF0000
Jnz @@WSc_AtLast
Inc EDx
Jmp @@WSc_AtLast
@Small_String:
← →
GuAV © (2004-10-06 23:22) [230]Мой smallscan тоже не выходит за буфер. кроме того вместе с предыдущим кодом у меня быстрее чем [193]
@@SmallScan:
Mov Al, [EAx]
Push ECx
Xchg EDx, EDi
Shr ECx, 2
Jz @@SSc_SkipD
Repne ScasD
Je @@SSc_D
@@SSc_SkipD:
Mov ECx, [ESp]
And ECx, 3
Jz @@SSc_Done
Repne ScasB
Jne @@SSc_Done
Xchg EDx, EDi
Pop EAx
Sub EAx, ECx
Ret
@@SSc_Done:
Xchg EDx, EDi
Pop EAx
Xor EAx, EAx
Ret
@@SSc_D:
Add ECx, ECx
Xchg EDx, EDi
Add ECx, ECx
Pop EAx
Sub EAx, ECx
Ret
Проверте на Р4, плиз.
← →
kaZaNoVa © (2004-10-06 23:24) [231]2ALL выложите плиз полный окончательный вариант "ускоренной POS" ;)
← →
GuAV © (2004-10-06 23:42) [232][230] не то выложил. не работает. вот что имелось ввиду:
@@SmallScan:
Mov Al, [EAx]
Push ECx
Xchg EDx, EDi
Repne ScasB
Jne @@SSc_Done
Xchg EDx, EDi
Pop EAx
Sub EAx, ECx
Ret
@@SSc_Done:
Xchg EDx, EDi
Pop EAx
Xor EAx, EAx
Ret
← →
GuAV © (2004-10-06 23:49) [233]kaZaNoVa © (06.10.04 23:24) [231]
Как только, так сразу.
← →
Defunct © (2004-10-07 00:00) [234]2 GuruAV
На P4 - очень хорошо:PosGuru&Def 4 188 134 322
PosDef_MMX C 194 139 333
на P2 тоже стало лучше но не на много:PosGuru&Def 4 1148 692 1840
PosDef_MMX C 1168 699 1867
PosJOH_MMX_a 8 1139 933 2072
← →
Defunct © (2004-10-07 00:03) [235]с новым SmallScan [232] стало гораздо хуже:
PosGuru&Def 4 194 134 328
← →
Defunct © (2004-10-07 00:14) [236]Guru, а вы учитываете выравнивание на границу QWord при MMX сканировании? На очень больших строках будет существенный проигрыш если не учитываете.
Это же было не от фонаря сделано [193]:
MovQ MM7, [Edi]
PCMPEQB MM7, MM6
PACKSSWB MM7, MM7
MovD EAx, MM7
Test EAx, EAx
Jnz @@CharFound
Add EDi, 8
Mov EAx, Edi
And EAx, 7
Sub EDi,EAx // Aligning index
Sub ECx,8
Add ECx,EAx
Cmp ECx,4
Jnge @@LastDword
У меня получалось добиться индекса 133 в SB2, но тогда мой тест (просмотр 12.5Gb) выполнялся на 2 секунды дольше.
← →
GuAV © (2004-10-07 00:33) [237]Defunct © (07.10.04 00:14) [236]
не знал про это. тогда так:@@WideScan:
Cmp ECx, 16
Jb @@SmallScan
Mov Al,[EAx]
Mov Ah, Al
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
Push EBx
Push EDx
Mov EBx, ECx
And EBx, not 7
Add EBx, EDx
Test EDx, 4
Jz @@WSc_Scan5
MovD MM7, [EDx] // load a part of buffer that needs to be scaned
PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)
MovD EAx, MM7 // get mixed dword
Test EAx, EAx
Jnz @@WSc_DFound
Add EDx, 4
Sub EBx, 4 // do not check dword again
@@WSc_Scan5:
MovQ MM7, [EDx]
и далее по тексту.
то есть, если был DWord align, то при WSc_Scan5 будет QWord align, а не быть его может только в извращённых условиях типа validate0, под которые подстраиваемся, но не оптимизируем.
← →
Defunct © (2004-10-07 01:09) [238]У меня промелькнула идея которая не только может значительно ускорить функцию, но и решит проблему с validate 0. Как вы думаете, если при MMX сканировании и при CharPos (раскрученном цикле) формировать массив найденных символов и потом с ним и работать. (т.е. например, просмотрели 8 символов, нашли 3 совпадения и дальше уже работает с совпадениями, все найденные совпадения не подходят - тогда продолжаем смотреть следующие 8 символов).
PS: меня сейчас время поджимает, смогу рассмотреть эту идею только на выходных, если у вас есть время можете попробовать раньше.
← →
GuAV © (2004-10-07 01:49) [239]
@@CompareWholeString:
Test EBx, EBx
Jz @@Constant_Exists
Cmp EDx, EBx
Jna @@Exit_False
MOV ECX, EBX
@@CWs_1:
Test ECx, 1
Jz @@CWs_2
MOV AL, [ESi+ECx]
CMP AL, [EDi+ECx]
Sub ECx, 1
@@CWs_2:
Test ECx, 2
Jz @@CWs_4
MOV AX, [ESi+ECx]
CMP AX, [EDi+ECx]
Sub ECx, 4
@@CWs_4:
Test ECx, 4
Jz @@CWs_8
MOV EAX, [ESi+ECx]
CMP EAX, [EDi+ECx]
Sub ECx, 8
@@CWs_8:
@@CW_Loop:
SUB ECX, 8
JL @@Constant_Exists
MovQ MM3, [ESi+ECx]
MovQ MM2, [EDi+ECx]
PCMPEQB MM3, MM2
PACKSSWB MM3, MM3
MovD EAX, MM3
Cmp EAX, -1
JE @@CW_Loop
@@SkipBTest:
Mov ECx, EDx
Cmp EDx,4
Jg @@Scan
Jmp @@LastDWord
@@Constant_Exists:
Pop EAx
Sub EAx, EDx
Defunct © (07.10.04 01:09) [238]
Не думаю что я справлюсь раньше. Пока я ещё не полностью понимаю работу имеющесйся. Однако, завтра у меня будет много времени.
← →
GuAV © (2004-10-07 02:05) [240][239] опять не рабочий код дал, блин... вот рабочий:
@@CompareWholeString:
Test EBx, EBx
Jz @@Constant_Exists
Cmp EDx, EBx
Jna @@Exit_False
MOV ECX, EBX
@@CWs_1:
Test ECx, 1
Jz @@CWs_2
Sub ECx, 1
MOV AL, [ESi+ECx]
CMP AL, [EDi+ECx]
JNE @@SkipBTest
@@CWs_2:
Test ECx, 2
Jz @@CWs_4
Sub ECx, 2
MOV AX, [ESi+ECx]
CMP AX, [EDi+ECx]
JNE @@SkipBTest
@@CWs_4:
Test ECx, 4
Jz @@CWs_8
Sub ECx, 4
MOV EAX, [ESi+ECx]
CMP EAX, [EDi+ECx]
JNE @@SkipBTest
@@CWs_8:
@@CW_Loop:
SUB ECX, 8
JL @@Constant_Exists
MovQ MM3, [ESi+ECx]
MovQ MM2, [EDi+ECx]
PCMPEQB MM3, MM2
PACKSSWB MM3, MM3
MovD EAX, MM3
Cmp EAX, -1
JE @@CW_Loop
@@SkipBTest:
Mov ECx, EDx
Cmp EDx,4
Jg @@Scan
Jmp @@LastDWord
@@Constant_Exists:
Pop EAx
Sub EAx, EDx
← →
GuAV © (2004-10-07 02:23) [241]
@@CompareWholeString:
Test EBx, EBx
Jz @@Constant_Exists
Cmp EDx, EBx
Jna @@Exit_False
Push ESi
Push EDi
Add EDi, EBx
Add ESi, EBx
@@CWs_1:
Test EBx, 1
Jz @@CWs_2
Sub ESi, 1
Sub EDi, 1
MOV AL, [ESi]
CMP AL, [EDi]
JNE @@SkipBTest1
@@CWs_2:
Test EBx, 2
Jz @@CWs_4
Sub ESi, 2
Sub EDi, 2
MOV AX, [ESi]
CMP AX, [EDi]
JNE @@SkipBTest1
@@CWs_4:
Test EBx, 4
Jz @@CWs_8
Sub ESi, 4
Sub EDi, 4
MOV EAX, [ESi]
CMP EAX, [EDi]
JNE @@SkipBTest1
@@CWs_8:
MOV ECX, EBX
@@CW_Loop:
SUB ECX, 8
JL @@Constant_Exists1
SUB ESi, 8
SUB EDi, 8
MovQ MM3, [ESi]
MovQ MM2, [EDi]
PCMPEQB MM3, MM2
PACKSSWB MM3, MM3
MovD EAX, MM3
Cmp EAX, -1
JE @@CW_Loop
@@SkipBTest:
Mov ECx, EDx
@@SkipBTest1:
Cmp EDx,4
Pop EDi
Pop ESi
Jg @@Scan
Jmp @@LastDWord
@@Constant_Exists1:
Pop EDi
Pop ESi
@@Constant_Exists:
Pop EAx
Sub EAx, EDx
← →
GuAV © (2004-10-07 16:10) [242]По поводу поиска по восем байт без AV мысль такая.
сначала Test Buffer, 7 и если не нуль то
{
читать в mmreg 8 байт из [Buffer and (not 7)]
в начало могут попасть байты из длины и счета ссылок, чтобы их проигнорировать, тестить результатPCMPEQB / PACKUSWBвот такой маской (адресовать в самой маске по [Buffer and 7)])SmallTestArray: array[0..7] of LongWord =поправить буфер Buffer:=Buffer and (not 7)
($00000000,
$F0000000,
$FF000000,
$FFF00000,
$FFFF0000,
$FFFFF000,
$FFFFFF00,
$FFFFFFF0);
}
потом читать по 8 байт из буфера (он уже QWord aligned)
потом читать остаток, если он есть. Причём 8 байт, хотя осталось меньше. Тестить масокй из аналогичного массива. Буфер остался QWord Aligned, поэтому чтение не пересечет 4к-границу, т.е. AV не будет.
← →
Defunct © (2004-10-07 19:33) [243]2 GuruAV: я смотрю вы из Харькова, не хотите быть соавтором статьи в ВАКовском журнале "Проблемы программирования"? Если да, тогда давайте пересечемся в аське.
← →
GuAV © (2004-10-07 20:11) [244]Реализация [242] для поиска из [193]
@@WideScan:
Cmp ECx, 16
Jb @@SmallScan
Mov Al,[EAx]
Mov Ah, Al
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
Push ECx
Test EDx, 7
Jz @@Scan5
Mov ECx, EDx
And ECx, 7
And EDx, not 7
MovQ MM7, [EDx]
PCMPEQB MM7, MM6
PACKSSWB MM7, MM7
MovD EAx, MM7
And EAx, SmallTestArray[ECx*4].DWord
Jnz @@1stbytes
Mov EAx, ECx
Mov ECx, [ESp]
Add EDx, 8
Sub ECx, EAx
@@Scan5:
MovQ MM7, [EDx]
PCMPEQB MM7, MM6
PACKSSWB MM7, MM7
MovD EAx, MM7
Test EAx, EAx
Jnz @@CharFound2
Add EDx,8
Sub ECx,8
Jg @@Scan5
@@Exit_False2:
Emms
Pop EAx
Xor EAx, EAx
Ret
@@1stbytes:
Mov [ESp], ECx
Mov ECx, 8
@@CharFound2:
Dec Ecx
Test EAx,0Fh
Jnz @@Check2
Shr EAx,4
Jmp @@CharFound2
@@Loop2:
Dec Ecx
Test Al,Al
Js @@Check2
Shr EAx,8
Jmp @@Loop2
@@Check2:
Test ECx,ECx
Js @@Exit_False2
Emms
Pop EAx
Sub EAx, ECx
Ret
> пересечемся в аське
никак. только мыло.
← →
Defunct © (2004-10-08 20:21) [245]> никак. только мыло.
чего так? религия запрещает? как насчет MSN
← →
GuAV © (2004-10-08 23:16) [246]<off>
> чего так? религия запрещает? как насчет MSN
То запрещает, что у меня так:
соединился, проверил почту, скачал интересные ветки, отключился.
написал ответы, соединился, отправил всё, отключился.
Ибо время-деньги. Это называется диал-ап.
Кстати, что я могу написать про "Проблемы программирования", если я не программист ?
</off>
← →
Defunct © (2004-10-09 00:19) [247]> Ибо время-деньги. Это называется диал-ап.
думаю 30 мин нам хватит. а там уже можно и почтой.
> Кстати, что я могу написать про "Проблемы программирования", если я не программист ?
Писать надо не про проблемы программирования, а про ускорение поиска подстроки в строке. "Проблемы программирования" - это просто название журнала.
ВАК = Высшая Аттестационная Комиссия.
Судя по анкете вы еще учитесь, научная статья вам повредит? Материала в этой ветке уже предостаточно для хорошей статьи.
PS: завтра попробую [244] и займусь реализацией [238].
← →
GuAV © (2004-10-09 00:28) [248]Defunct © (09.10.04 00:19) [247]
Ок. завтра во второй половине дня или послезавтра пересечёмся.
Хотя имхо если по этой ветке, то надо сначало довести начатое дело.
Да. Я действительно ещё учусь.
← →
GuAV © (2004-10-09 00:29) [249]
> завтра
то есть не завтра, а в субботу, т.е. сегодня уже. на время не глянул.
← →
GuAV © (2004-10-09 15:49) [250]Мой ICQ в анкете...
← →
Defunct © (2004-10-09 16:57) [251][244]
WideScan - поиск символа, и он используется только при длинне подстроки = 1 (подстрока состоит из одного символа). Первый найденный символ и будет результатом. Менять с учетом [238] надо было WideSearch, именно в нем надо просматривать сразу все возможные вхождения первого символа нарушения QWord Align.
← →
GuAV © (2004-10-10 14:30) [252]Для коротких строк в [193] после проверки возврат на цикл уже длиных строк, это иожет привести к потере быстродействия и явно создаёт проблемы для дальнейшей оптимизации. предлагаю вынести __WideScan; и __WideString; и разделить CompareWholeString для них.
procedure __WideScan;
asm
Mov Al,[EAx]
Mov Ah, Al
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
Push ECx
Test EDx, 7
Jz @@Scan5
Mov ECx, EDx
And ECx, 7
And EDx, not 7
MovQ MM7, [EDx]
PCMPEQB MM7, MM6
PACKSSWB MM7, MM7
MovD EAx, MM7
And EAx, SmallTestArray[ECx*4].DWord
Jnz @@1stbytes
Mov EAx, ECx
Mov ECx, [ESp]
Add EDx, 8
Sub ECx, EAx
@@Scan5:
MovQ MM7, [EDx]
PCMPEQB MM7, MM6
PACKSSWB MM7, MM7
MovD EAx, MM7
Test EAx, EAx
Jnz @@CharFound2
Add EDx,8
Sub ECx,8
Jg @@Scan5
@@Exit_False2:
Emms
Pop EAx
Xor EAx, EAx
Ret
@@1stbytes:
Mov [ESp], ECx
Mov ECx, 8
Jmp @@CharFound2
@@CharFound21:
Shr EAx,4
@@CharFound2:
Dec Ecx
Test EAx,0Fh
Jz @@CharFound21
@@Check2:
Test ECx,ECx
Js @@Exit_False2
Emms
Pop EAx
Sub EAx, ECx
end;
procedure __WideString;
asm
MovD MM4, EAx
Mov Ah, Al
MovD MM6, EAx
PUNPCKLWD MM6, MM6
PUNPCKLDQ MM6, MM6
@@Scan:
MovQ MM7, [Edi]
PCMPEQB MM7, MM6
PACKSSWB MM7, MM7
MovD EAx, MM7
Test EAx, EAx
Jnz @@CharFound
Add EDi, 8
Mov EAx, Edi
And EAx, 7
Sub EDi, EAx // Aligning index
Sub ECx, 8
Add ECx, EAx
@@Scan2:
MovQ MM7, [Edi]
PCMPEQB MM7, MM6
PACKSSWB MM7,MM7
MovD EAx, MM7
Test EAx, EAx
Jnz @@CharFound
Add EDi,8
Sub ECx,8
Jg @@Scan
Jmp @@Exit_False
@@CharFound:
MovQ MM7, [Edi]
PCMPEQB MM7, MM6
MovD EAx, MM7
Test EAx, EAx
Jnz @@Loop1
Add EDi,4
Sub ECx,4
PSRLQ MM7,32
MovD EAx, MM7
@@Loop1:
inc EDi
dec Ecx
Test Al,Al
Js @@Check
Shr EAx,8
Jmp @@Loop1
@@Check:
MovD EAx, MM4
@@CheckLastChar: // as proposed in Boyer-Mur alhorithm
Mov EDx, ECx // store new residual buffer size
Test EDx, EDx
Js @@Exit_False
Test EBx, EBx
Js @@Constant_Exists
Cmp Ah, [EBx+Edi]
Jz @@CompareWholeString
Test EDx, EDx
Jg @@Scan
@@Exit_False:
Pop EAx
Xor EAx,EAx
Jmp @@Leave_Proc
@@NotFound_Exit:
Xor EAx, EAx
Ret
@@CompareWholeString:
Test EBx, EBx
Jz @@Constant_Exists
Cmp EDx, EBx
Jna @@Exit_False
MOV ECX, EBX
@@CWs_1:
Test ECx, 1
Jz @@CWs_2
Sub ECx, 1
MOV AL, [ESi+ECx]
CMP AL, [EDi+ECx]
JNE @@SkipBTest
@@CWs_2:
Test ECx, 2
Jz @@CWs_4
Sub ECx, 2
MOV AX, [ESi+ECx]
CMP AX, [EDi+ECx]
JNE @@SkipBTest
@@CWs_4:
Test ECx, 4
Jz @@CWs_8
Sub ECx, 4
MOV EAX, [ESi+ECx]
CMP EAX, [EDi+ECx]
JNE @@SkipBTest
@@CWs_8:
@@CW_Loop:
SUB ECX, 8
JL @@Constant_Exists
MovQ MM3, [ESi+ECx]
MovQ MM2, [EDi+ECx]
PCMPEQB MM3, MM2
PACKSSWB MM3, MM3
MovD EAX, MM3
Cmp EAX, -1
JE @@CW_Loop
@@SkipBTest:
Mov ECx, EDx
@@SkipBTest1:
Test EDx, EDx
Jg @@Scan
Jmp @@Exit_False
@@Constant_Exists:
Pop EAx
Sub EAx, EDx
@@Leave_Proc:
EMMS
Pop EBp
Pop EBx
Pop ESi
Pop EDi
End;
// продолжение следующим постом
← →
GuAV © (2004-10-10 14:32) [253]
Function PosDefunct_a(const Constant, Buffer: string): Integer; Assembler;
Asm
Test eax, eax
Jz @@NotFound_Exit
Test edx, edx
Jz @@NotFound_Exit
Mov ECx, [EDx-4]
Test ECx, ECx
Jz @@NotFound_Exit
Cmp [EAx-4],1
Jnz @@WideSearch
Cmp ECx, 8
Ja @@SmallScan
// CharPos
@@Scan4:
Mov Ch,[EAx]
// Ch - char
// EDx - pointer to buffer
// cl - length
@@CharPos:
Mov EAx,[EDx]
Cmp Ch,Al
Jz @Found1
cmp Ch,Ah
Jz @Found2
Shr EAx,16
Cmp Ch,Al
Jz @Found3
Cmp Ch,Ah
Jz @Found4
Cmp Cl,4
Jna @NotFound
Mov EAx,[EDx+4]
Cmp Ch, Al
Jz @Found5
Cmp Ch, Ah
Jz @Found6
Shr EAx, 16
Cmp Ch, Al
Jz @Found7
Cmp Ch, Ah
Jz @Found8
@NotFound:
XOr EAx, EAx
Ret
@Found1:
Mov EAx,1
Jmp @Validation
@Found2:
Mov EAx,2
Jmp @Validation
@Found3:
Mov EAx,3
Jmp @Validation
@Found4:
Mov EAx,4
Jmp @Validation
@Found5:
Mov EAx,5
Jmp @Validation
@Found6:
Mov EAx,6
Jmp @Validation
@Found7:
Mov EAx,7
Jmp @Validation
@Found8:
Mov EAx,8
Jmp @Validation
@Validation:
Cmp Al,Cl
Ja @NotFound
ret
nop
nop // alignment for better performance
@@SmallScan:
Cmp ECx, 16
Ja __WideScan
Push ECx
Mov Ch,[EAx]
@@Scan8:
Push ECx
Call @@CharPos
Pop ECx
Test EAx, EAx
Jz @Validation3
Sub Cl, Al
Pop EAx
Sub Al, Cl
Ret
@Validation3:
Sub Cl, 8
Add EDx, 8
Cmp Cl, 0
Jg @@Scan8
Add ESP, 4
Ret
/////////////////////////////////////////////
@Small_String:
Cmp ECx, [EAx-4]
Jb @NotFound
Mov Ch, [EAx]
Push ECx
Push EBx
Push ESi
Mov ESi, EAx
Mov EBx,[ESi-4]
Dec EBx
@Scan6:
Push ECx
@Scan7:
Call @@CharPos
Pop ECx
Test EAx, EAx
Jz @Validation2
Sub Cl, Al
Add EDx, EAx
Cmp Cl, Bl
Jb @NotFound2
Push ECx
Mov ECx, EBx
@Loop2:
Mov Al, [ESi+ECx]
Cmp Al, [EDx+ECx-1]
Jnz @Scan7
Loop @Loop2
Pop ECx
Mov Ah, 0
Pop ESi
Pop EBx
Pop EAx
Sub EAx, ECx
ret
@Validation2:
Sub Cl, 8
Add EDx, 8
Cmp Cl, 0
Jg @Scan6
@NotFound2:
Pop ESi
Pop EBx
Add ESp, 4
Xor EAx, EAx
Ret
@@WideSearch:
Cmp ECx,32
Jb @Small_String
Push EDi
Push ESi
Push EBx
Push EBp
MOV ESI, EAX
Mov EDi, EDx
Push ECx
Mov EBX, [ESI-4]
Test EBx, EBx
Jz @@Exit_False
Mov Al, [ESi]
Cmp EBx, ECx
Ja @@Exit_False
Jnz @@Normal_Work
Cmp AL, [Edi]
Jnz @@Exit_False
@@Normal_Work:
Dec EBX
Mov Ah, [ESi+EBx]
Dec EBx
Mov EDx,ECx
Inc ESi
Mov EBp, ESi
Cmp ECx, 8
Ja __WideString
@@Scan3:
Push EAx
Mov Ch, Al
Mov EDx, EDi
Call @@CharPos
Mov Ch, 0
Sub ECx, EAx
Add EDi, EAx
Pop EDx
Test EAx,EAx
Jz @@Exit_False
Xchg EAx, EDx
// Jmp @@CheckLastChar
//@@CheckLastChar: // as proposed in Boyer-Mur alhorithm
Mov EDx, ECx // store new residual buffer size
Test EDx, EDx
Js @@Exit_False
Test EBx, EBx
Js @@Constant_Exists
Cmp Ah, [EBx+Edi]
Jz @@CompareWholeString
Test EDx, EDx
Jg @@Scan3
@@Exit_False:
Pop EAx
Xor EAx,EAx
Jmp @@Leave_Proc
@@NotFound_Exit:
Xor EAx, EAx
Ret
@@CompareWholeString:
Test EBx, EBx
Jz @@Constant_Exists
Cmp EDx, EBx
Jna @@Exit_False
MOV ECX, EBX
@@CW_Loop:
SUB ECX, 4
JL @@CW_Last123bytes
MOV EAX, [ESi+ECx]
JZ @@CW_LastDWord
CMP EAX, [EDi+ECx]
JE @@CW_Loop
Mov ECx, EDx
JMP @@SkipBTest1
@@CW_LastDWord:
CMP EAX, [EDi]
JE @@Constant_Exists
Mov ECx, EDx
JMP @@SkipBTest1
@@CW_Last123bytes:
ADD ECX, 2
JS @@Last1
@@Last3:
MOV AX, [ESi]
JZ @@Last2
CMP AX, [EDi]
JNE @@SkipBTest
MOV AL, [ESi+2]
CMP AL, [EDi+2]
JE @@Constant_Exists
Mov ECx, EDx
JMP @@SkipBTest1
@@Last2:
CMP AX, [EDi]
JE @@Constant_Exists
Mov ECx, EDx
JMP @@SkipBTest1
@@Last1:
MOV AL, [ESi]
CMP AL, [EDi]
JE @@Constant_Exists
@@SkipBTest:
Mov ECx, EDx
@@SkipBTest1:
Test EDx, EDx
Jg @@Scan3
Jmp @@Exit_False
@@Constant_Exists:
Pop EAx
Sub EAx, EDx
@@Leave_Proc:
Pop EBp
Pop EBx
Pop ESi
Pop EDi
End;
← →
GuAV © (2004-10-10 15:05) [254]Моя версия SmallScan:
@@SmallScan:
Cmp ECx, 16
Ja __WideScan
Mov Ch,[EAx]
Push ECx
Call @@CharPos
Pop ECx
Test EAx, EAx
Jnz @@SmallDone
Add EDx, 8
Sub ECx, 8
Call @@CharPos
Test EAx, EAx
Jz @@SmallDone
Add EAx, 8
@@SmallDone:
Ret
← →
Sha © (2004-10-11 12:58) [255]> Defunct
> GuAV
Скорость - это хорошо.
Но хочется все-таки увидеть функцию, прошедшую тест Validate0.
← →
Defunct © (2004-10-11 17:00) [256]> Но хочется все-таки увидеть функцию, прошедшую тест Validate0.
Работаем над этим, попутно делаем описание.
К концу недели должна быть функция прошедшая validate0 и без потерь в скорости.
← →
Sha © (2004-10-11 21:35) [257]Defunct © (11.10.04 17:00) [256]
OK.
Попробую пока переделать свою с Pascal на Asm.
Потом сравним ;)
← →
GuAV © (2004-10-12 00:46) [258]
> маленькой хитрости - изменения направления сравнения.
Почему это усокряет функцию ?
← →
Defunct © (2004-10-12 01:06) [259]>> маленькой хитрости - изменения направления сравнения.
> Почему это усокряет функцию ?
Я вам пытался об этом сказать, но вы не хотели слушать мотивируя примером с наперсточником, пятью наперстками и шариком. ;)
У вас в аське есть ответ на этот вопрос.
Помните, что главной задачей является поиск несовпадения, а не наоборот. Чем быстрее отбракуем строку, тем быстрее продолжим линейный поиск символа.
Вот строки для сравнения, какой способ определит несовпадение быстрее всего? С конца, с начала, или в двух направлениях, или в четырех?
[xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
[xxbxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
[xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
[xxxxxxxxxxxxxxxxxxxxxxxxxxxxcxx]
[xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
[xxxxxxxxxxxxxcxxxxxxxxxxxxxxxxx]
← →
GuAV © (2004-10-12 01:51) [260]
//Нет не в том дело.
//попробуйте такое:
const Len = 1024*256;
var TestArray: array[0..Len] of Byte;
procedure P1;
asm
MOV ECX, Len
@@1:
MOV AL, TestArray[ECX].Byte
DEC ECX
CMP ECX, 0
JNZ @@1
end;
procedure P2;
asm
MOV ECX, 0
@@1:
MOV AL, TestArray[ECX].Byte
INC ECX
CMP ECX, Len
JNZ @@1
end;
procedure TForm1.Button1Click(Sender: TObject);
var I, T1, T2: Integer;
begin
T1:=GetTickCount;
for I:=1 to 1000 do
P1;
T1:=GetTickCount-T1;
T2:=GetTickCount;
for I:=1 to 1000 do
P2;
T2:=GetTickCount-T2;
Memo1.Lines.Add("P1="+IntToStr(T1));
Memo1.Lines.Add("P2="+IntToStr(T2));
end;
procedure TForm1.Button2Click(Sender: TObject);
var I, T1, T2: Integer;
begin
T2:=GetTickCount;
for I:=1 to 1000 do
P2;
T2:=GetTickCount-T2;
T1:=GetTickCount;
for I:=1 to 1000 do
P1;
T1:=GetTickCount-T1;
Memo1.Lines.Add("P1="+IntToStr(T1));
Memo1.Lines.Add("P2="+IntToStr(T2));
end;
ps на [258] хотел получить ответ Sha ©
← →
Defunct © (2004-10-12 01:58) [261][260]
ну и?
на P4 одинаково.
← →
GuAV © (2004-10-12 02:05) [262]У меня нет. Но я понял уже почему нет (разное кодирование CMP). Таки наверное Вы правы. Не буду больше сбивать Вас с верного пути...
← →
GuAV © (2004-10-12 11:26) [263]Думал над идеей Defunct, обратном порядке и напрестке.
Вывод. Поскольку обратный порядок существенно быстрее чем прямой, данный тест необъективен.
Объективный тест:
Строка случайной длины.
Берется случайная подстрока из этой строки (с приоритетом в сторону коротких строк).
Иногда в ней делаются различия случайные (с приоритетом в сторону неболшого числа различий).
← →
GuAV © (2004-10-12 11:33) [264]Естественно всем тогда одинаковый RandSeed
Страницы: 1 2 3 4 5 6 7 вся ветка
Форум: "Основная";
Текущий архив: 2004.10.24;
Скачать: [xml.tar.bz2];
Память: 1.56 MB
Время: 0.044 c
