Einzelnen Beitrag anzeigen

Benutzerbild von sirius
sirius

Registriert seit: 3. Jan 2007
Ort: Dresden
3.443 Beiträge
 
Delphi 7 Enterprise
 
#19

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 6. Dez 2007, 12:00
Delphi-Quellcode:
function QSString(const ssubstr,text:string):Integer;stdcall;
//Delphi fügt automatisch push ebp; mov ebp,esp; ein
asm
  push ebx //register retten
  push edi
  push esi

  mov eax,[ebp+8] //ssubbstr
  mov edx,[eax-4] //length(ssubstr)
  mov ebx,edx //ebx=length(ssubstr) (für später)
  sub edx,2 //edx=length(ssubstr)-2
  push edx //n2 = [ebp - 16] =length(ssubstr)-2
  movzx edx, byte ptr [eax]
  push edx //c1 = [ebp - 20] =ssubstr[1]
  movzx edx, byte ptr [eax+ebx-1]
  push edx //cp= [ebp - 24] =ssubstr[ length(ssubstr) ]


  mov cx,$0100 //array mit ebx=length(ssubstr)+1 füllen
  inc ebx
 @fillarray:
    push ebx
    dec cx
  jnz @fillarray
  dec ebx

  // For i := 0 To n-1 Do Skip[sSubStr[i]] := n - i;
  xor ecx,ecx
  mov edi,[ebp+8] //ssubstr
  push ebx //length(ssubstr) auf [esp] legen/retten
  mov esi,ebp
  sub esi,$41C //Zeiger auf Sprungtabelle
 @fillotherskip: //for i=ecx :=0 to ebx
    movzx eax, byte ptr [edi+ecx] //ssubstr[ecx+1] in eax
    mov [esi+eax*4],ebx //[sprungtabelle+xxx] := length(ssubstr)-i
    inc ecx
    dec ebx
  jnz @fillotherskip


  mov esi,[ebp+12] //Zeiger auf text

  mov ecx,[esi-4] //length(text) in ecx
  sub ecx,[esp] //ecx ist jetzt k (length(ssubstr) abgezogen)
  jle @endwhile //wenn k<=0 Schleife überspringen

  xor edi,edi //Zählvariable
  mov bl,[ebp-20] //c1 und
  mov bh,[ebp-24] //cp
  lea edx,[ebp-$41C] //Zeiger auf Sprungtabelle


  //in Schleife gilt:
  //edi ist Zähler i
  //esi ist Zeiger auf Text
  //ebx ist erster(bl) und letzter(bh) Char von substr
  //[esp] ist n (Länge von substr)
  //ecx ist k (Abbruchbedingung)
  //edx ist Zeiger auf Sprungtabelle

 @while:

    cmp [esi+edi],bl //Vergleich text[i] mit c1
    jnz @endif //wenn ungleich --> springen
    mov eax,[esp] //length(ssubstr) in eax
    add eax,edi //i addieren
    cmp [esi+eax-1],bh //Vergleich text[i+length(ssubstr)] mit cp
    jnz @endif

      cmp [esp],3 //length(ssubstr) mit 3 vergleichen
      jl @positiveExit //wenn kleiner 3 dann Ergebnis gefunden

      //comparemem
      push ecx //register retten
      push edx
      push edi
      push esi
      mov ecx,[ebp-16] //length(ssubstr)-2
      mov edx,ecx
      and edx,3
      add esi,edi
      inc esi
      mov edi,[ebp+8]
      inc edi
      shr ecx,2
      xor eax,eax
      repe cmpsd //Vergleich von DWORDs
      jne @endcmp
      mov ecx,edx
      repe cmpsb //Vergleich der restlichen Bytes
      jne @endcmp
      inc eax
     @endcmp:
      pop esi
      pop edi
      pop edx //register zurückholen
      pop ecx
      test al,al //Ergebnis von comparemem auswerten
      jnz @positiveExit

   @endif:
    mov eax,[esp] //length(ssubstr) nach eax
    add eax,edi //i dazuaddieren
    movzx eax, byte ptr [esi+eax] //test[i+length(ssubstr)+1]
    mov eax, [edx+eax*4] //Wert aus Sprungtabelle
    add edi, eax //..zu i dazuaddieren
    cmp edi, ecx //mit k vergleichen
  jle @while
 @endwhile:

  xor eax,eax //result:=0
  jmp @exit
@positiveExit:
  mov eax,edi //result:=i
  inc eax
@Exit:
  lea esp,ebp-12
  pop esi
  pop edi
  pop ebx
end;
Wenn ich mich nicht um +1 oder -1 mal verzählt habe, dürfte das stimmen.
Den letzten Absatz habe ich weggelassen.
Am meisten habe ich auf den Teil innerhalb der While-Schleife und darin außerhalb des IF-Blocks "optimiert".

Jetzt könnte man noch das cmp [esp],3 rausnehmen (weis nicht wieviel das bringt) und comparemem sozusagen als inline-Funktion reinschieben.
Aber erstmal testen, ob überhaupt alles richtig gemacht wird.

Edit: Fehler entfernt und Multiplikation entfernt
Dieser Beitrag ist für Jugendliche unter 18 Jahren nicht geeignet.
  Mit Zitat antworten Zitat