Registriert seit: 3. Jan 2007
Ort: Dresden
3.443 Beiträge
Delphi 7 Enterprise
|
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
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.
|