| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Поиск в бинарном файле [D5, WinXP]
Dimaxx © (2004-09-24 23:32:00)
Страницы: < 1 2 ... 5 6 7 8 9 10 11 12 13 14 >
Сабж. Нужен алгоритм действительно быстрого поиска последовательности байт любой длины в файлах любого размера (до гигабайта). Читать кусками по-деревенски не катит. Раньше у меня был алгоритм, но с падением Фуджика все пропало.
Defunct (2004-09-30 21:05:00) [141]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]?
Sha (2004-09-30 16:44:00) [142]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;
Romkin (2004-09-30 10:31:00) [143]Sha © (30.09.04 09:24) [120] Бррр...
Может, так достаточно? http://delphibase.endimus.ru/?action=viewfunc&topic=strsearch&id=10271
Интересно, и насколько отстает?
Игорь Шевченко (2004-09-30 10:18:00) [144]Defunct © (29.09.04 18:14) [117]
В процитированном
Sha (2004-09-30 09:24:00) [145]> 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;
Defunct (2004-09-29 23:16:00) [146]> Напишите ещё и {$else} и выделите не MMX код туда, а то совсем прочитать не могу
Не, там все должно быть как есть. с помощью MMX делается только определение наличия символа в QWORD, дальше repne scas просматривает только цепочку из 8-ми байт.
Из старого кода выбрасывается только одна команда, смотреть поправку [114] секция {$ifndef}
Уберете {define MMX} будет работать старая функция, оставите - будет сканироваться по 8 байт.
GuAV (2004-09-29 22:10:00) [147]
> PS: GuruAV как вам рассказик [102]? там все сказано об этом.
Не понял что Вы хотели им сказать. Однако
[101] и
> Может и не интересуют, но они могут в принципе быть.
> Ну вот допустим памяти не хватило. Тогда файл не найден.
> А он не найден потому что его нет или памяти нехватило, или
> ошибка чтения файла - угадай-ка ? :)
в силе.
Defunct © (29.09.04 03:23) [112]
c00l !
Напишите ещё и {$else} и выделите не MMX код туда, а то совсем прочитать не могу
Defunct (2004-09-29 18:14:00) [148]Игорь Шевченко © (29.09.04 10:22) [116]
в чем лажа?
Игорь Шевченко (2004-09-29 10:22:00) [149]
> Вот потому все серьезные проекты, которые требуют скорости
> и пишутся на C++, а компилируются или MS Visual Studio .Net
> или интеловский компилятором.
Лажу гнать не надо, а ?
Defunct (2004-09-29 04:50:00) [150]> Ну могут быть и не оптимальны, т.к. они и не особо стремятся - они вероятно такой фигнёй не страдают.
Вот потому все серьезные проекты, которые требуют скорости и пишутся на C++, а компилируются или MS Visual Studio .Net или интеловский компилятором.
Defunct (2004-09-29 04:30:00) [151]Так работает немножко быстрее, на 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
PUNPCKHWDMM7, 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 03:36:00) [152]> - А мне не нужно лучше, мне нужно чтоб вы за... (замучились) !
Отож простые задачи - неитересны, и даже скучны.
Defunct (2004-09-29 03:23:00) [153]Кому интересно, поиск строки с использованием 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;
Fedia (2004-09-29 02:56:00) [154]To Defunct and GuAV.
Даже несмотря на то, что большинство кода на ASM для меня оставалось загадкой, все равно с удовольствием почитал ветку.
А итоговую процедуру поиска с удовольствием буду использовать.
Просто хотел поблагодарить GuAV за настойчивость, а Defunct за терпение :)
Defunct (2004-09-29 02:06:00) [155]XCHG reg32,reg32 ¦ xchg eax,edx ¦ P-Pro and higher - 1/2
GuAV (2004-09-28 22:12:00) [156]
> И это не первая функция на моем счету, которая доказывает,
> что не все решения от 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!
- Товарищь прапорщик, а не лучше ли взять лопаты?
- А мне не нужно лучше, мне нужно чтоб вы за... (замучились) !
Sha (2004-09-28 12:34:00) [157]Ага, никакого буфера.
И простым циклом на Паскале.
Игорь Шевченко (2004-09-28 12:30:00) [158]MMF оно проще...
Defunct (2004-09-28 11:49:00) [159]вот наброски, черт его знает стоит ли оно того, что-то уж сильно много кода получается
...
{$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}
Defunct (2004-09-28 10:46:00) [160]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
| |
