| Новости | Поиск | 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) 

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

---

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

> 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 :)

---

GuAV   (2004-10-04 02:22:00) [102]

> Можно конечно вручную сконструировать невыровненную строку,
> но вряд ли это будет честно :)

А разве выходить за буфер честно ? :)
попробовал жетскую систему допинг котнтроля.
Оказывается, даже если нет 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 00:39:00) [103]

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-03 12:46:00) [104]

Ха. этот тест функция Defunct проходит.
Нужно запретить к части данных находящейся не по смещению кратному 8 от начала строки. Лучше даже не кратному 4.

---

Sha   (2004-10-03 11:35:00) [105]

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


---

Sha   (2004-10-03 08:33:00) [106]

GuAV ©   (03.10.04 00:34) [158]

Я делал проверку через VirtualProtect в одном из Challenge, не помню в каком. Надо порыться... Позже...

---

GuAV   (2004-10-03 00:34:00) [107]

@@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 то же, этого кода я вообще не понял...

---

GuAV   (2004-10-02 18:50:00) [108]

Вот... тестить ща не могу... могут быть ошибки..
@@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-02 18:34:00) [109]

Sha ©   (02.10.04 18:31) [155]

ок. не знал. у меня целерон. ща оптимизирую.

---

Sha   (2004-10-02 18:31:00) [110]

> GuAV

Сейчас я сижу за K6 и не могу проверить скорость на P4,
но два перехода подряд приводят к потерям тактов.

---

GuAV   (2004-10-02 15:43:00) [111]

>  @@Last1:
>  MOV   AX, [ESi]
>  CMP   AX, [EDi]
>  JNE   @@SkipBTest
>  JMP   @@Constant_Exists

MOV   AL, [ESi] // Of course a byte-sized operand is meant
CMP   AL, [EDi] // That's a kinda ctrl-C+ctrl-V eror :)

---

GuAV   (2004-10-02 15:33:00) [112]

так имхо немного быстрее будет 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

---

Sha   (2004-10-02 11:18:00) [113]

>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

---

Defunct   (2004-10-02 01:50:00) [114]

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

---

Alekc   (2004-10-01 20:38:00) [115]

Кто-то спрашивал почему у борланда такие неоптимальные функции: если тут столько народу одну Pos так долго оптимизирует, то сколько б времени у Borland'ы ушло на всё RTL/VCL ? 10 лет ? :о)

---

GuAV   (2004-10-01 20:32:00) [116]

> функция прошла 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;

---

Defunct   (2004-10-01 12:01:00) [117]

> Тем там много...
это хорошо

> Кстати, было бы неплохо выложить здесь окончательный вариант.
Не вопрос, как только закончу, и тест покажет что функция прошла Validate тест сразу выложу.

---

Sha   (2004-10-01 11:52:00) [118]

Тем там много...
Можно заново открыть PosChallenge, если ты усовершенствуешь свою функцию.
Кстати, было бы неплохо выложить здесь окончательный вариант.

---

Defunct   (2004-10-01 11:44:00) [119]

> Не желаешь принять участие в FastCode?

на тему?

---

Sha   (2004-10-01 10:41:00) [120]

> Defunct ©   (01.10.04 10:27) [144]
> Зато на больших строках получилось обогнать все функции

Наверное, точнее так: на больших строках с образом в конце.
Не забывай, что просто для таких строк Джон еще не написал свою функцию :)

PS. Твой результат действительно очень хорош.
Не желаешь принять участие в FastCode?

---

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

Наверх