| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Поиск в бинарном файле [D5, WinXP]
Dimaxx © (2004-09-24 23:32:00)
Страницы: < 1 2 ... 5 6 7 8 9 10 11 12 13 14 >
Сабж. Нужен алгоритм действительно быстрого поиска последовательности байт любой длины в файлах любого размера (до гигабайта). Читать кусками по-деревенски не катит. Раньше у меня был алгоритм, но с падением Фуджика все пропало.
GuAV (2004-09-27 22:50:00) [181]Раз возвращаете 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:32:00) [182]
> Так или иначе, это не имеет значения, т.к. проверка на 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:26:00) [183]
> результат поиска строки "01wbcb" в файле gladiator.avi (726Mb)
> с учетом что такой строки в файле нет, а есть множество
> строк "01wb" составил - 22.34 сек, при повторном запуске
> - 13.71 сек. проверял на компе с 512Mb памяти (т.е. файл
> не мог полностью разместиться в кеше).
Это мысль ! Буфер надо не 1ГБ а где-то 16..32 кБ
Defunct (2004-09-27 22:23:00) [184]GuAV © (27.09.04 22:08) [79]
не столь важно, поймите я не хочу вас оскорбить или сказать, что вы плохо разбираетесь в асме, просто заметил ошибку, исправил привел вариант [74] так что не зацикливайтесь на одном месте. Хотите продолжить оптимизацию, продолжайте с [74]
Defunct (2004-09-27 22:19:00) [185]GuAV © (27.09.04 21:38) [77]
> Repe CmpsD, а CmpsB - остаток
Уже рассматривал, этот вариант. Мне не хватает одного РОНа, чтобы сделать с Cmps D. Приходится юзать стек, значительно проиграем на коротких строках. либо придется использовать регисты 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 если найду время.
GuAV (2004-09-27 22:08:00) [186]
> Код [69] не рабочий.
>
И после [70] ?
GuAV (2004-09-27 21:38:00) [187]
> 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:00) [188]из справки:
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
Defunct (2004-09-27 20:52:00) [189]результат поиска строки "01wbcb" в файле gladiator.avi (726Mb) с учетом что такой строки в файле нет, а есть множество строк "01wb" составил - 22.34 сек, при повторном запуске - 13.71 сек. проверял на компе с 512Mb памяти (т.е. файл не мог полностью разместиться в кеше).
Defunct (2004-09-27 19:41:00) [190]Забыл добавить описание:
Function ConstantPos(const Constant: string;
Buffer: Pointer; BufSize: Integer): Integer; Assembler;
{ -> EAx - указатель на строку поиска (константа)
EDx - указатель на буфер, в котором требуется найти строку поиска
ECx - длина буфера
<- EAx - Позиция строки поиска в буфере
(-1) если строки в буфере нет
}
Defunct (2004-09-27 19:25:00) [191]Эта функция работает почти в два раза быстрее чем стандартная функция 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 18:03:00) [192]
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 17:19:00) [193]
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
Defunct (2004-09-27 16:39:00) [194]Код [69] не рабочий.
Project .... failed with message "privileged instruction at address ..." process stopped use RUN to continue
Вашу идею с объединением функций подхватил, сейчас попробую сделать рабочим.
GuAV (2004-09-27 13:13:00) [195]
> { 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);
GuAV (2004-09-27 13:03:00) [196]
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:01:00) [197]изучил код.
счас выложу оптимизированный.
сначала кометарий об ошибке
> 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.
Defunct (2004-09-27 02:53:00) [198]Тут после всего залез в модуль System функция _Pos (для ShortString) работает по алгоритму [1] (если отбросить часть которая относится к файлам).
Defunct (2004-09-27 01:51:00) [199]GuAV © (27.09.04 00:30) [64]
Дык, все неточности, что вы видите - исправьте. Полную версию вашего оптимизированного кода выложете.
В чужем глазу соринку видим, в своем не заметим и бревна(С) народная мудрость. Так что я нисколько не сомневаюсь, что вы в состоянии значительно улучшить код [40]
> а попробуйте не выносить LoadBuffer, окажется всё проще
Это тому яркое подтверждение, я туда и не посмотрел бы.
> 4. как обрабатывается строка длинее MaxBufferSize ?
с помощью Norton FileCompare или как оно там называется ;)
Зы, а код этот думаю для многих пригодится, так как тема быстрого поиска весьма актуальна. может стоит в кладовку выложить?
GuAV (2004-09-27 00:40:00) [200]:)
4. как обрабатывается строка длинее MaxBufferSize ?
| |
