|
(Moderator)
Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
Delphi 2007 Enterprise
|
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
8. Dez 2007, 20:08
Hi Amateurprofi. Natürlich ist meine Testumgebung sicher. Ich erzeuge einen Zufallsstring mit dem Alphabet X. Der Suchstring enthält Zeichen, die nicht in X sind.
Ich finde 7% auch sehr gut und daher wird deine Version -mit deiner Erlaubnis- in meine Unit übernommen.
Hier der FastPos-Code für Alle, bei denen der Download nicht klappt.
Delphi-Quellcode:
(******************************************************************************
* FastPos-Unit. Zusammenarbeit der Delphi-Praxis, FastCode-Challenge und *
* dem QuickSearch-Algorithmus von Daniel Sunday *
* *
* Stellt eine Funktion zum Suchen eines Teilstrings in einem String zur *
* Verfügung. Dabei wird, in Abhängigkeit der Stringlängen der jeweils beste *
* Algorithmus ausgewählt *
* Wenn der Suchstring aus einem Zeichen besteht, wird der Gewinner der *
* FastCode-Challenge 'CharPos' ([url]www.fastcode.org[/url]) aufgerufen *
* *
* Wenn der Suchstring aus 2 oder 3 Zeichen besteht, oder der zu durchsuchende*
* Text relativ kurz ist, dann wird der Gewinner der FastCode-Challenge 'Pos' *
* aufgerufen. *
* In allen anderen Fällen wird ein modifizierter QuickSearch-Algorithmus *
* verwendet, der mit einer Optimierung von Timo Raita arbeitet. *
* *
******************************************************************************)
Unit FastPosUnit;
Interface
Function DPPos( Const sSubStr, sString: String): Integer;
Implementation
Uses
SysUtils;
Function QPosEx(SearchFor, SearchIn: String; Start: integer): integer;
Asm
pushad // Alle Register auf Stack legen
sub esp,$400 // Platz für Skiptabelle schaffen
// Auf dem Stack liegen folgende Daten
// ESP : Skiptabelle
// ESP+$400..$410 : EDI, ESI, EBP, ESP, EBX
// ESP+$414 : EDX Adresse SearchIn
// ESP+$418 : ECX Start
// ESP+$41C : EAX Adresse SearchFor
// ESP+$420 : EBP
// ESP+$424 : Returnadresse
// Prüfen, ob SearchFor oder SearchIn leer ist, oder Start negativ ist
test eax,eax
je @Fail // SearchFor ist leer
test edx,edx
je @Fail // Searchin ist leer
mov ebx,[eax-4] // Länge SearchFor
test ebx,ebx
je @Fail // SearchFor ist leer
test ecx,ecx
js @Fail // Start ist negative
// Erste und letzte mögliche Fundstelle in ESI bzw. EBP
je @1
sub ecx,1 // =Start 0-basierend
@1: lea esi,[edx+ecx] // Ab hier soll gesucht werden
add edx,[edx-4]
mov ebp,edx
sub ebp,ebx // Bis hier soll gesucht werden
// Prüfen, ob Erste mögliche Fundstelle hinter letzter liegt
cmp esi,ebp
ja @Fail
// Prüfen, ob SearchFor nur 1 Zeichen ist
// Dann ist keine SkipTabelle erforderlich
cmp ebx,1
je @Search1
// Skiptabelle erstellen
// 1) for i:=0 to 255 do Skip[i]:=n+1
mov edi,esp
mov ecx,$100
mov eax,ebx
add eax,1 // Length(Searchfor)+1
rep stosd
// 2) For i:=0 To n-1 Do Skip[SearchFor[i]]:=n-i
mov edi,[esp+$41C] // Adresse SearchFor
mov eax,ebx // Length(Searchfor)
@FillSkip: movzx edx,[edi+ecx] // SearchFor[i]
mov [esp+edx*4],eax // Skip[SearchFor[i]]:=n-i
add ecx,1
sub eax,1
jne @FillSkip
// Erstes und Letztes Zeichen von SearchFor in AL/AH
mov al,[edi] // Erstes Zeichen SearchFor
mov ah,[edi+ebx-1] // Letzes Zeichen SearchFor
// Prüfen, ob Length(SearchFor) > 6 ist
cmp ebx,6
ja @SearchX
jmp @Vector.Pointer[ebx*4-8]
@Vector: dd @Search2
dd @Search3
dd @Search4
dd @Search4 // Länge=5
dd @Search6
// Länge Searchfor > 6
@SearchX: add edi,1 // Auf zweites Zeichen von SearchFor
mov [esp+$41C],edi // Merken für CompareMem
jmp @Search
// Länge SearchFor > 6
@SkipX: mov esi,edx // Aufruf ex CompareMem
@Skip: movzx edx,[esi+ebx]
add esi,[esp+edx*4]
cmp esi,ebp
ja @Fail
@Search: cmp [esi],al
jne @Skip
cmp [esi+ebx-1],ah
jne @Skip
// Zweites bis vorletzten Zeichen von SearchFor prüfen
mov edx,esi // ESI retten
mov edi,[esp+$41C] // Zeiger zweites Zeichen von SearchFor
add esi,1 // Zeiger Text auf nächstes Zeichen
mov ecx,ebx // Length(SearchFor)
sub ecx,2 // -2 (Erstes und letztes Zeichen)
shr ecx,2 // =Anzahl DWords
repe cmpsd // DWords vergleichen
jne @SkipX // Nicht gleich
mov ecx,ebx // Length(SearchFor)
sub ecx,2 // -2 (Erstes und letztes Zeichen)
and ecx,3 // =Anzahl restliche Bytes
repe cmpsb // Bytes vergleichen
jne @SkipX // Nicht gleich
mov esi,edx // Fundstelle
jmp @Found
// Länge SearchFor=1
@Search1: mov ecx,ebp // Letzte mögliche Fundstelle
sub ecx,esi // - Erste mögliche Fundstelle
add ecx,1 // = Anzahl zu prüfende Zeichen
neg ecx
sub esi,ecx
mov al,[eax] // zu suchendes Zeichen
@Loop: cmp al,[esi+ecx]
je @Found1
add ecx,1
jne @Loop
jmp @Fail
@Found1: lea esi,[esi+ecx] // ESI auf Fundstelle
jmp @Found
// Länge SearchFor=2
@Skip2: movzx edx,[esi+ebx]
add esi,[esp+edx*4]
cmp esi,ebp
ja @Fail
@Search2: cmp [esi],al
jne @Skip2
cmp [esi+ebx-1],ah
jne @Skip2
jmp @Found
// Länge SearchFor=3
@Skip3: movzx edx,[esi+ebx]
add esi,[esp+edx*4]
cmp esi,ebp
ja @Fail
@Search3: cmp [esi],al
jne @Skip3
cmp [esi+ebx-1],ah
jne @Skip3
mov dx,[edi]
cmp dx,[esi]
jne @Skip3
jmp @Found
// Länge SearchFor=4 oder 5
@Skip4: movzx edx,[esi+ebx]
add esi,[esp+edx*4]
cmp esi,ebp
ja @Fail
@Search4: cmp [esi],al
jne @Skip4
cmp [esi+ebx-1],ah
jne @Skip4
mov edx,[edi]
cmp edx,[esi]
jne @Skip4
jmp @Found
// Länge SearchFor=6
@Skip6: movzx edx,[esi+ebx]
add esi,[esp+edx*4]
cmp esi,ebp
ja @Fail
@Search6: cmp [esi],al
jne @Skip6
cmp [esi+ebx-1],ah
jne @Skip6
mov edx,[edi+1]
cmp edx,[esi+1]
jne @Skip6
jmp @Found
@Found: // Gefunden, Index berechnen
sub esi,[esp+$414]
add esi,1
jmp @SetRes
@Fail: // Nicht gefunden, Result=0
xor esi,esi
@SetRes: // Result speichern
mov [esp+$41C],esi
// Skiptabelle vom Stack nehmen
add esp,$400
// Register wieder herstellen, Result in EAX
popad
End;
Function CharPos_JOH_SSE2_1_b(Ch: Char; Const Str: AnsiString): Integer;
Asm
test edx, edx
jz @@NullString
mov ecx, [edx-4]
push ebx
mov ebx, eax
cmp ecx, 16
jl @@Small
@@NotSmall:
mov ah, al {Fill each Byte of XMM1 with AL}
movd xmm1, eax
pshuflw xmm1, xmm1, 0
pshufd xmm1, xmm1, 0
@@First16:
movups xmm0, [edx] {Unaligned}
pcmpeqb xmm0, xmm1 {Compare First 16 Characters}
pmovmskb eax, xmm0
test eax, eax
jnz @@FoundStart {Exit on any Match}
cmp ecx, 32
jl @@Medium {If Length(Str) < 32, Check Remainder}
@@Align:
sub ecx, 16 {Align Block Reads}
push ecx
mov eax, edx
neg eax
and eax, 15
add edx, ecx
neg ecx
add ecx, eax
@@Loop:
movaps xmm0, [edx+ecx] {Aligned}
pcmpeqb xmm0, xmm1 {Compare Next 16 Characters}
pmovmskb eax, xmm0
test eax, eax
jnz @@Found {Exit on any Match}
add ecx, 16
jle @@Loop
pop eax {Check Remaining Characters}
add edx, 16
add eax, ecx {Count from Last Loop End Position}
jmp dword ptr [@@JumpTable2-ecx*4]
nop
nop
@@NullString:
xor eax, eax {Result = 0}
ret
nop
@@FoundStart:
bsf eax, eax {Get Set Bit}
pop ebx
inc eax {Set Result}
ret
nop
nop
@@Found:
pop edx
bsf eax, eax {Get Set Bit}
add edx, ecx
pop ebx
lea eax, [eax+edx+1] {Set Result}
ret
@@Medium:
add edx, ecx {End of String}
mov eax, 16 {Count from 16}
jmp dword ptr [@@JumpTable1-64-ecx*4]
nop
nop
@@Small:
add edx, ecx {End of String}
xor eax, eax {Count from 0}
jmp dword ptr [@@JumpTable1-ecx*4]
nop
@@JumpTable1:
dd @@NotFound, @@01, @@02, @@03, @@04, @@05, @@06, @@07
dd @@08, @@09, @@10, @@11, @@12, @@13, @@14, @@15, @@16
@@JumpTable2:
dd @@16, @@15, @@14, @@13, @@12, @@11, @@10, @@09, @@08
dd @@07, @@06, @@05, @@04, @@03, @@02, @@01, @@NotFound
@@16:
add eax, 1
cmp bl, [edx-16]
je @@Done
@@15:
add eax, 1
cmp bl, [edx-15]
je @@Done
@@14:
add eax, 1
cmp bl, [edx-14]
je @@Done
@@13:
add eax, 1
cmp bl, [edx-13]
je @@Done
@@12:
add eax, 1
cmp bl, [edx-12]
je @@Done
@@11:
add eax, 1
cmp bl, [edx-11]
je @@Done
@@10:
add eax, 1
cmp bl, [edx-10]
je @@Done
@@09:
add eax, 1
cmp bl, [edx-9]
je @@Done
@@08:
add eax, 1
cmp bl, [edx-8]
je @@Done
@@07:
add eax, 1
cmp bl, [edx-7]
je @@Done
@@06:
add eax, 1
cmp bl, [edx-6]
je @@Done
@@05:
add eax, 1
cmp bl, [edx-5]
je @@Done
@@04:
add eax, 1
cmp bl, [edx-4]
je @@Done
@@03:
add eax, 1
cmp bl, [edx-3]
je @@Done
@@02:
add eax, 1
cmp bl, [edx-2]
je @@Done
@@01:
add eax, 1
cmp bl, [edx-1]
je @@Done
@@NotFound:
xor eax, eax
pop ebx
ret
@@Done:
pop ebx
End;
Procedure Filler2;
Asm
nop
End;
Function Pos_JOH_IA32_6( Const SubStr: AnsiString; Const Str: AnsiString): Integer;
Asm {Slightly Cut-Down version of PosEx_JOH_6}
push ebx
cmp eax, 1
sbb ebx, ebx {-1 if SubStr = '' else 0}
sub edx, 1 {-1 if S = ''}
sbb ebx, 0 {Negative if S = '' or SubStr = '' else 0}
jl @@InvalidInput
push edi
push esi
push ebp
push edx
mov edi, [eax-4] {Length(SubStr)}
mov esi, [edx-3] {Length(S)}
cmp edi, esi
jg @@NotFound {Offset to High for a Match}
test edi, edi
jz @@NotFound {Length(SubStr = 0)}
lea ebp, [eax+edi] {Last Character Position in SubStr + 1}
add esi, edx {Last Character Position in S}
movzx eax, [ebp-1] {Last Character of SubStr}
add edx, edi {Search Start Position in S for Last Character}
mov ah, al
neg edi {-Length(SubStr)}
mov ecx, eax
shl eax, 16
or ecx, eax {All 4 Bytes = Last Character of SubStr}
@@MainLoop:
add edx, 4
cmp edx, esi
ja @@Remainder {1 to 4 Positions Remaining}
mov eax, [edx-4] {Check Next 4 Bytes of S}
xor eax, ecx {Zero Byte at each Matching Position}
lea ebx, [eax-$01010101]
not eax
and eax, ebx
and eax, $80808080 {Set Byte to $80 at each Match Position else $00}
jz @@MainLoop {Loop Until any Match on Last Character Found}
bsf eax, eax {Find First Match Bit}
shr eax, 3 {Byte Offset of First Match (0..3)}
lea edx, [eax+edx-3] {Address of First Match on Last Character + 1}
@@Compare:
cmp edi, -4
jle @@Large {Lenght(SubStr) >= 4}
cmp edi, -1
je @@SetResult {Exit with Match if Lenght(SubStr) = 1}
movzx eax, word ptr [ebp+edi] {Last Char Matches - Compare First 2 Chars}
cmp ax, [edx+edi]
jne @@MainLoop {No Match on First 2 Characters}
@@SetResult: {Full Match}
lea eax, [edx+edi] {Calculate and Return Result}
pop edx
pop ebp
pop esi
pop edi
pop ebx
sub eax, edx {Subtract Start Position}
ret
@@NotFound:
pop edx {Dump Start Position}
pop ebp
pop esi
pop edi
@@InvalidInput:
pop ebx
xor eax, eax {No Match Found - Return 0}
ret
@@Remainder: {Check Last 1 to 4 Characters}
mov eax, [esi-3] {Last 4 Characters of S - May include Length Bytes}
xor eax, ecx {Zero Byte at each Matching Position}
lea ebx, [eax-$01010101]
not eax
and eax, ebx
and eax, $80808080 {Set Byte to $80 at each Match Position else $00}
jz @@NotFound {No Match Possible}
lea eax, [edx-4] {Check Valid Match Positions}
cmp cl, [eax]
lea edx, [eax+1]
je @@Compare
cmp edx, esi
ja @@NotFound
lea edx, [eax+2]
cmp cl, [eax+1]
je @@Compare
cmp edx, esi
ja @@NotFound
lea edx, [eax+3]
cmp cl, [eax+2]
je @@Compare
cmp edx, esi
ja @@NotFound
lea edx, [eax+4]
jmp @@Compare
@@Large:
mov eax, [ebp-4] {Compare Last 4 Characters of S and SubStr}
cmp eax, [edx-4]
jne @@MainLoop {No Match on Last 4 Characters}
mov ebx, edi
@@CompareLoop: {Compare Remaining Characters}
add ebx, 4 {Compare 4 Characters per Loop}
jge @@SetResult {All Characters Matched}
mov eax, [ebp+ebx-4]
cmp eax, [edx+ebx-4]
je @@CompareLoop {Match on Next 4 Characters}
jmp @@MainLoop {No Match}
End;
Function DPPos( Const sSubStr, sString: String): Integer;
Var
i: Integer;
c: Char;
Begin
Case Length(sSubStr) Of
0:
Result := 0;
1:
Result := CharPos_JOH_SSE2_1_b(sSubStr[1], sString);
2, 3:
Result := Pos_JOH_IA32_6(sSubStr, sString);
Else
If Length(sString) < 1000 Then // 1000 is ne Hausnummer
Result := Pos_JOH_IA32_6(sSubStr, sString)
Else
Result := QPosEx(sSubStr, sString,1); // Dann kann man auf das '(n<3) or' verzichten!
End
End;
End.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
|