Top.Mail.Ru
Мастера DELPHI, Delphi programming community Титульная страница Поиск, карта сайта Написать письмо 
| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL |
| Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Поиск в бинарном файле [D5, WinXP]


Страницы:   1 2 3 4 5 6 7 8 9 10 ... 13 14

Dimaxx ©   (2004-09-24 23:32:00) 

Сабж. Нужен алгоритм действительно быстрого поиска последовательности байт любой длины в файлах любого размера (до гигабайта). Читать кусками по-деревенски не катит. Раньше у меня был алгоритм, но с падением Фуджика все пропало.

GuAV   (2004-10-04 22:53:00) [81]

Defunct ©   (04.10.04 21:36) [180]
Таких мест у Вас несколько.

Defunct ©   (04.10.04 21:55) [182]

> Новая функция работает быстрее по обеим тестам

Какая именно ?

Sha   (2004-10-04 22:24:00) [82]

> GuAV ©   (04.10.04 19:45) [177]
> Будет ли тогда мой тест корректным если дать выравинвание на
> дв. слово но не на четверное и добавить нуль терминатор?

Да.

Defunct   (2004-10-04 21:55:00) [83]

Еще один забавный факт.. не знаю даже как его проекоментировать.
Новая функция работает быстрее по обеим тестам (как для маленьких строк, так и для больших) причем с приличным отрывом (на 10% быстрее чем PosJoh-MMX для малых строк и 20% - для больших, в 4.5 раза быстрее чем PosRTL) чем все функции в тесте на процессорах:
P-MMX
P2-MMX
P3-Coppermine
Celeron (P3)-Coppermine

НО, САМОЕ ИНТЕРЕСНОЕ, НА P4-HT функция почему-то проигрывает примерно на 10% на малых строках, а на больших строках отрыв сократился до 5-7% в сравнении с PosJoh-MMX.

Видно что-то я не учел именно под P4..

Defunct   (2004-10-04 21:41:00) [84]

[180]
И еще уберете лишний Jump, Jmp в конце цикла установить на начало.

вместо Jns @@Scan - написать Jmp @@Scan, Jmp @@Exit_False выбросить.

только так функция, будет работать на пару процентов медленнее.

Defunct   (2004-10-04 21:36:00) [85]

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:27:00) [86]

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

GuAV   (2004-10-04 21:19:00) [87]

Этио создаст 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

GuAV   (2004-10-04 19:45:00) [88]

Sha ©   (04.10.04 14:51) [176]

Ок. с нуль терминатором Ваша проходит, но Defunct нет.
Pos из RTL работает.
Что не будет работать искать не буду, поверю на слово.


> они выровнены на границу двойного слова

у Defunct предполагается, что на границу 8. Как Вам это ?

Будет ли тогда мой тест корректным если дать выравинвание на дв. слово но не на четверное и добавить нуль терминатор?

Sha   (2004-10-04 14:51:00) [89]

Иными словами, если сама Delphi при работе с ANSI-строками предполагает, что они выровнены на границу двойного слова, читает и записывает терминатор, читает последнее двойное слово, содержащее символы строки, то почему это должно быть запрещено для сторонних строковых функций?

Sha   (2004-10-04 14:37:00) [90]

> GuAV ©   (04.10.04 14:25) [174]

Ты не понял, речь о том, что валидацию с твоим вариантом ProtectedStringCreate [163] не пройдет Delphi RTL, а потому он неверный.

GuAV   (2004-10-04 14:25:00) [91]


> Так что не удастся тебе стать святее Папы Римского:
> твой тест не прошла бы даже Delphi RTL :)

Я же сказал, все проходят, кроме Вашей и Defunct, и даже ShowMessage работает! Попробуйте сами.
Defunct ©   (04.10.04 12:21) [172]
А Вы всё же попробуйте применить их. Ещё быстрее будет. И мой код не читает за буфером.

kaZaNoVa   (2004-10-04 12:32:00) [92]

2алл - плиз, выложите окончательный вариант функции - замены POS  ;)
- а так у меня в памяти POS пашет ~120 мб/сек .. :))
при скорости винта 20~30 мб/сек, имхо даже у POS потрясающее быстродействие %)))

Defunct   (2004-10-04 12:21:00) [93]

Зы. померял свою функцию [151] на P2, без последних изменений внесенных GuraAV, поимела все функции по Overall Bechmark'у.

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

Суслик   (2004-10-04 11:50:00) [94]


>  [170] Sha ©   (04.10.04 11:41)
> > Суслик ©   (04.10.04 11:19) [169]
>
> Да, действительно, не выделяется.
> Похоже, был не прав.
> Память подвела :)

Мы об этом недавно поспорили с АП - оба оказались правы - в Д5 есть 4 байта, в Д6 - нет. Потому и удивлен вашему ответу.

Sha   (2004-10-04 11:41:00) [95]

> Суслик ©   (04.10.04 11:19) [169]

Да, действительно, не выделяется.
Похоже, был не прав.
Память подвела :)

Суслик   (2004-10-04 11:19:00) [96]


>  Но она там, естественно осталась, и хакеры могут ее использовать.

Вот это мне не понятно. Что значит осталась? Судя по СPU под эти 4 байта память не выделяется.

Суслик   (2004-10-04 11:15:00) [97]


>  [167] Sha ©   (04.10.04 11:13)


> Это длина выделенного блока.

Т.е. в этих 4х байтах хранится кол-во выделенных байт плюс к тем 4ем байтам, которые в заголовке выделенного блока хранит дельфовый менеджер памяти?

Sha   (2004-10-04 11:13:00) [98]

> Суслик ©   (04.10.04 11:07) [165]
> в пятом дельфи в префиксе еще 4 байта есть.

Это длина выделенного блока. Она в 6-ой просто не описана, т.к. при манипуляции со строками не используется. Но она там, естественно осталась, и хакеры могут ее использовать.

Sha   (2004-10-04 11:09:00) [99]

читать
(и даже следующему за ним байту для wide-строк)

Суслик   (2004-10-04 11:07:00) [100]


> а префикс строки объявлен следующим образом:
>
> type
>  PStrRec = ^StrRec;
>  StrRec = packed record
>    refCnt: Longint;
>    length: Longint;
>  end;

в пятом дельфи в префиксе еще 4 байта есть.

Страницы:   1 2 3 4 5 6 7 8 9 10 ... 13 14

Наверх

Титульная страница Поиск, карта сайта Написать письмо