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

← →
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 не пройдёт
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+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.

> 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.

Ну так исправь - и ты победитель :)

икто не проверил на Р4 [157] ?

Так это ж не конец :)

> Однако часто проверяется и флаг С - а там уж точно задержка возникнет.
Помним и об этом, поэтому JA/JB после Inc/Dec никогда не используем. Только JZ/JS.

> Ну так исправь - и ты победитель :)

Дык, над этим и работаю в свободное время. ;)
Функция уже ~400 строк, начинаю малость теряться.

GuAV © (05.10.04 00:41) [190]
> никто не проверил на Р4 [157] ?

5 баллов GuruAV! (3-5)% ускорение на больших строках по сравнению с [151] и даже на мелких строках ускорение на лицо - (5-10)%

Итак долгожданный победитель заезда ;)

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;

Результаты тестирования на 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-ми символов)

Надеюсь таблица нормально запостится.

[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

вот теперь можно спокойно идти спать с чуством выполненного долга
;)

> Defunct © (05.10.04 05:06) [195]

Поздравляю! Пора заново открывать PosChallenge.

Кстати, в FastCode намечается StringReplaceChallenge, можешь применить свои наработки там.

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 нету ?

> 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;

> GuAV © (05.10.04 12:19) [197]

> Не всё так однозначно...
про Celeron скоро можно будет забыть

> У них там случайно Case-unsensitive Pos нету ?
Нет. Все, что есть, здесь http://dennishomepage.gugs-cats.dk/FastCodeProject.htm

> Поздравляю! Пора заново открывать 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):

Ок вечерком, посмотрю.

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