Boyer Moore Algorithmus

[Horst_]

Hallo,

die Asm Version hat ja einfach die Paramter vertauscht
SearchIn Searchfor und Suchtext,SuchWort... -> muss ja 0 werden.
Also EAX und EDX im zu Beginn ander sbehandeln, wieso habe ich nicht einfach ein
XCHG EAX,EDX davorgesetet....

Ich würde in der ASM Version mal an repne scasb //scasw in Betracht ziehen.
Bei Jaenicke's Version
http://www.entwickler-ecke.de/topic_..._91942,20.html , bringt es einiges ab 7 Buchstaben Abstand.

Hier die angepasste Unit1 für Version 5b.

Delphi-Quellcode:

unit Unit1;

{$mode objfpc}{$H+}
{$ASMMODE INTEL}
interface

uses
  Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls,
  strutils, Windows, SpeedSearchExt, BMH_CountStr;

type

  { TForm1 }

  TForm1 = class(TForm)
    Button1: TButton;
    Button2: TButton;
    Button3: TButton;
    ComboBox1: TComboBox;
    Edit2: TEdit;
    Edit3: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
  private
    { private declarations }
  public
    { public declarations }
  end;

var
  Form1: TForm1;


implementation

{$R *.lfm}

{ TForm1 }

const
  testtxt: string = 'Franz jagt im komplett verwahrlosten Taxi quer durch Bayern.' +
    #13#10;

var
  //Variablen für Zeittest
  freq: int64;
  startTime: int64;
  endTime: int64;
//ASM_ERGEBNIS_ASM : integer;

function CountStr(const SearchIn, SearchFor: string): integer; assembler;
      {$DEFINE ANSI}
asm
         TEST    EDX,EDX
         JE      @Ret // SearchFor leer
         mov     ECX,[EDX-4] // Length(SearchFor)
         PUSH    EBP
         PUSH    EBX
         PUSH    EDI
         PUSH    ESI

         PUSH    Dword 0 // Anzahl Zeichen
         //         MOV     ESI,0 ; MOV     ASM_ERGEBNIS_ASM,ESI

         TEST    EAX,EAX
         JE      @end // SearchIn leer
         mov     EBP,ECX // Length(SearchFor)
         MOV     EBX,[EAX-4] // Length(SearchIn)
         SUB     EBX,ECX // Length(SearchIn)-Length(SearchFor)
         JC      @end // SearchFor länger als SearchIn
      {$IFDEF ANSI}
         lea     ESI,[EDX+ECX] // Hinter SearchFor
         LEA     EDI,[EAX+ECX] // Hinter SearchIn[Length(SearchFor)]
      {$ELSE}
         LEA     ESI,[EDX+ECX*2] // Hinter SearchFor
         LEA     EDI,[EAX+ECX*2] // Hinter SearchIn[Length(SearchFor)]
      {$ENDIF}
         NEG     ECX
         JMP     @Entry
         @NextStart:
         SUB     EBX,1
         JC      @end // Alles durchsucht
      {$IFDEF ANSI}
         add EDI,1 // Nächste Startposition
      {$ELSE}
         ADD     EDI,2 // Nächste Startposition
      {$ENDIF}
         @Entry:
         MOV     EDX,ECX // Count
         @CharLoop:
      {$IFDEF ANSI}
         MOV     AL,[ESI+EDX*1] // SearchFor[edx]
         CMP     AL,[EDI+EDX*1] // SearchIn[edx]
      {$ELSE}
         MOV     AX,[ESI+EDX*2] // SearchFor[edx]
         CMP     AX,[EDI+EDX*2] // SearchIn[edx]
      {$ENDIF}
         JNE     @NextStart
         @NextChar:
         ADD     EDX,1 // Count
         JL      @CharLoop // nächstes Zeichen prüfen

         ADD    DWORD PTR [ESP],1 // Anzahl Fundstellen
         //INC     ASM_ERGEBNIS_ASM

     {$IFDEF ANSI}
         LEA     EDI,[EDI+EBP*1] // Um Length(SearchFor) weiter
     {$ELSE}
         LEA     EDI,[EDI+EBP*2] // Um Length(SearchFor) weiter
     {$ENDIF}
         SUB     EBX,EBP // Anzahl verfügbarer Zeichen
         JNC     @Entry // Noch Zeichen da
         @end:
         POP     EAX
         //         MOV     EAX,ASM_ERGEBNIS_ASM

         POP     ESI
         POP     EDI
         POP     EBX
         POP     EBP
         @Ret:
end;
{$UNDEF ANSI}

function CountWordsStd(const Text, wort: string): integer;
var
  i: integer;
begin  //Mit Standard PosEx zählen
  i := 1;
  Result := 0;
  repeat
    i := PosEx(wort, Text, i) + 1;
    if i > 1 then
      Inc(Result)
    else
      exit;
  until False;
end;


procedure TForm1.Button2Click(Sender: TObject); //Test starten
var
  Filestream: TFileStream;
  SuchWort, SuchText: string;
  i, Ergebnis, Durchlaeufe: integer;
begin
  SuchWort := ComboBox1.Text;
  Durchlaeufe := StrToInt(Edit3.Text);

  if not FileExists(ExtractFilePath(Application.ExeName) + '\test.txt') then
  begin
    ShowMessage('Erst Testdatei mit Button "Create TesFile" erstellen !');
    exit;
  end;

  Filestream := TFileStream.Create('test.txt', fmOpenRead);
  try
    SetLength(SuchText, Filestream.Size);
    Filestream.Read(SuchText[1], Length(SuchText));

    QueryPerformanceFrequency(freq);

    //------------------------------------------------------------------------------
    QueryPerformanceCounter(startTime);//start BMH
    for i := 1 to Durchlaeufe do
      Ergebnis := BMH_CountStr_1(SuchText, SuchWort);
    QueryPerformanceCounter(endTime);//stop

    Memo1.Lines.Add('BMH Count:         ' + IntToStr(Ergebnis) +
      ' in ' + IntToStr((endTime - startTime) * 1000 div freq) + 'ms');

    //------------------------------------------------------------------------------
    QueryPerformanceCounter(startTime);//start SpeedSearch
    for i := 1 to Durchlaeufe do
      Ergebnis := SpeedSearch(SuchText, SuchWort);
    QueryPerformanceCounter(endTime);//stop

    Memo1.Lines.Add('SP Search Count: ' + IntToStr(Ergebnis) + ' in ' +
      IntToStr((endTime - startTime) * 1000 div freq) + 'ms');

    //------------------------------------------------------------------------------
    QueryPerformanceCounter(startTime);//start Standard PosEx
    for i := 1 to Durchlaeufe do
      Ergebnis := CountWordsStd(SuchText, SuchWort);
    QueryPerformanceCounter(endTime);//stop

    Memo1.Lines.Add('Std PosEx Count: ' + IntToStr(Ergebnis) + ' in ' +
      IntToStr((endTime - startTime) * 1000 div freq) + 'ms');

    //------------------------------------------------------------------------------
    QueryPerformanceCounter(startTime);//start Standard PosEx
    for i := 1 to Durchlaeufe do
      Ergebnis := CountStr(SuchText, SuchWort);
    QueryPerformanceCounter(endTime);//stop

    Memo1.Lines.Add('Asm        Count: ' + IntToStr(Ergebnis) + ' in ' + IntToStr(
      (endTime - startTime) * 1000 div freq) + 'ms');
    Memo1.Lines.Add('');
    //------------------------------------------------------------------------------


  finally
    Filestream.Free;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  Memo1.Clear;
end;

procedure TForm1.Button3Click(Sender: TObject); //Testdatei erstellen
var
  Filestream: TFileStream;
  i, zeilen: integer;
begin
  zeilen := StrToInt(Edit2.Text);

  Filestream := TFileStream.Create('test.txt', fmCreate);
  try
    for i := 1 to zeilen do
      Filestream.Write(testtxt[1], Length(testtxt));
  finally
    Filestream.Free;
  end;
end;


end.

Das Motorrad ruft ....schon wieder

Gruß Horst