ARM Assembler - String im String suchen

[Valerio]

Sollen für ein Hochschulpraktikum ein Programm in ARM Assembler entwickeln, welches in einem vorgegebenem String einen String sucht und am Ende ausgibt wie viele "Matches" stattgefunden haben.

int searchStringInString(char*, char*);


int main (void)

{

	int Anzahl;

	char* Text="hallo Alles klar?";

	char* Suchstring="ll";

	char* Leerstring="";


	Anzahl = searchStringInString(Text, Suchstring);

	Anzahl = searchStringInString(Text, Leerstring);	

	Anzahl = searchStringInString(Leerstring, Suchstring);

	Anzahl = searchStringInString(Leerstring, Leerstring);

// Aufrufe funktionieren auch so..

	Anzahl = searchStringInString("aabaabaab", "ab");


	return 0;

}[/PHP]

An der "searchStringInString" würde er anschließend in mein Assembler Programm springen, das momentan so aussieht:

[PHP]
.file "searchStringInString.S"
.text
.align 2
.global searchStringInString
.type searchStringInString, %function

searchStringInString:

stmfd sp!, {lr}

MOV r4, r0 @lade anfangsadresse von StringD in r4
MOV r5, r1 @lade anfangsadresse von StringS in r5
BL search @springe zu "search"

ldmfd sp!, {pc}

search:

stmfd sp!, {lr} @sichere Rücksprungadresse

.L1:
LDRB r6, [r4], #1 @Lade zu vergleichende Byte in r6 und erhöhe dann Adresse
LDRB r7, [r5] @Lade zu vergleichende Byte in r7 (zu suchender Teil)
CMP r6, r7 @Vergleiche r6 und r7
BEQ match @Wenn gleich, springe zu match
B .L1 @Wenn != beginne suche von vorne

ldmfd sp!, {pc}


match:
LDRB r6, [r4],#1 @lade nächste bye in r6
LDRB r7, [r5,#1] @ "
CMP r6, r7 @vergleiche
ADDEQ r2, r2, #1 @wenn = dann addiere 1 zu r2 (r2=match-register)
B .L1







.size searchStringInString, .-searchStringInString

Momentan gehe ich so vor:

Ich vergleiche immer 1 Byte (1 Buchstaben - momentan das "L") so lange, bis er einmal fündig geworden ist und springe anschließend zu "Match", wo das nächste Byte auf Gleichheit vergleichen wird. Wenn es ebenfalls gleich ist, wurde 1 mal gematched ("LL" gefunden). Mein Problem momentan? Es ist einfach verdammt statisch.

Hätte jemand evtl eine Idee, wie ich das ganze Dynamisch halten könnte?

Danke im voraus!

MfG

Valerio

[flashpixx]

Stringmatching wird via regulärer Ausdrücke realisiert. Du müsstest eben anhand ein solches Konstrukt entsprechend codieren. Rein technisch muss man dann eben jeden Zustand des Automaten einer Speicheradresse zuweisen und dort den Code für das Matching hinterlegen. Anhand der Eingabe springt man dann in die passende Zustandsadresse, sobald man in einem Zustand ein unbekanntes Match hat, springt man eben zu einer definierten Adresse (Fehlerzustand)

[Valerio]

Das war jetzt glaub ich etwas viel aufeinmal.. hab's nich so ganz verstanden, tut mir leid

[Bubble]

Das war jetzt glaub ich etwas viel aufeinmal.. hab's nich so ganz verstanden, tut mir leid

Musst Du auch nicht verstanden haben.

Es ist mir allerdings nicht ganz klar, was Du mit "statisch" und "dynamisch" in dem Zusammenhang genau meinst.

Du hast Dich ja im Grunde schon für ein (einfaches) Verfahren entschieden. Wenn es nicht das Ziel ist, ein besonders effizientes Verfahren zu implementieren, dann kannst Du ja dabei bleiben.

Wenn Dir nicht klar ist, wie Du es in Assembler umsetzt, dann schreibst Du das komplette Verfahren erst einmal als Pseudocode auf oder formulierst es als C-Programm, welches Du ausprobieren kannst. Dies überträgst Du dann Schritt für Schritt in Assembler.

Bei größeren Problemen solltest Du Dich evtl. an den Ansprechpartner vor Ort wenden, der Euch betreut.

[Valerio]

Es ist mir allerdings nicht ganz klar, was Du mit "statisch" und "dynamisch" in dem Zusammenhang genau meinst.

Momentan wird halt nur nach 2 aufeinanderfolgenden Buchstaben gesucht. Wenn ich jetzt z.B. das oben gepostete C-Programm so abänder, dass ich anstatt nach "ll", nach "Hallo" suchen möchte, so würde nur nach "Ha" gesucht werden.

[Bubble]

Richtig. Das musst Du ändern. Wenn Dir nicht klar ist, wie Du das in Assembler machst, dann schreibe die Funktion vorher als Pseudocode oder als C-Programm ohne Verwendung von Bibliotheksfunktionen auf und portiere danach die Vorgehensweise.

[WEBERLARS]

Ich bin Ungarn, also Deutsch ist nicht mein Muttersprache!

Hier habe ich ein selbstgeschriebenes assembler PRG.

INPUT: reg0 Text Anfangsadresse wo gesucht werden soll

reg1 Text Endadresse wo gesucht werden soll

IF reg0 > reg1 then SWAP r1 r2

reg2 Text Anfangsadresse wonach gesucht werden

reg3 Text Endadresse wonach gesucht werden

( die Maximale textlange wird auf #253 stück

charakter beschrankt :-( )

If reg2 > reg3 then SWAP r2 r3

reg13 Stackpointer setzen, denn die Software wird

als Unterprogramm aufgerufen (BSR textsuchen)

und als Platz für die HilfsTabelle gebraucht.

reg14 Hier wird normaleweise die Rücksprungadresse

festgehalten (sollte auf ein Breakpoint zeigen)

OUTPUT: reg4 Wert #FFFFFFFF wenn Text nicht vorhanden

sonst die Adresse wo die gesuchte Text vorkommt

Die Software ist als Unterprogramm geschrieben. Sollte also mit Branch

Unterprogramm aufgerufen werden.

Remark: Das Programm ist für ARM CPU geschrieben!!!

Die Mnemonics sind MEIN EIGENE also nicht die von original!!!

Die finde ich Sch....! Ich nutze mein eigene. Die CODEs sind

aber 100 Prozent für ARM !!! (Kein Thumb und die CPU befindet

in Big Endian Mod -so dass man der Text in Speicher für die menschliche

Auge verstandlich ist)

Für das Programm noch zu bemerken: es vergleicht nicht Buchstabe für

Buchstabe (Naive Algotithmus) sondern habe ich schon ein bessere Algorithmus

in ARM umgesetzt.

*00 E1500001 TSUB 0 1 :textsuchen

*04 80200001 EOR.HI 0 1

*08 80211000 EOR.HI 1 0

*0C 80200001 EOR.HI 0 1 ; swap r0 r1

*10 E1520003 TSUB 2 3

*14 80222003 EOR.HI 2 3

*18 80233002 EOR.HI 3 2

*1C 80222003 EOR.HI 2 3 ; swap r2 r3

*20 E0433002 SUB 3 2

*24 E35330FD TSUB 3 #FD ; textlange auf max. 253 charakter

*28 90833002 ADD.LE 3 2

*2C 828230FD ADD.HI 3 2 #FD

*30 E8AD40E1 SRRMIAX 0567E D

*34 E0435002 SUB 5 3 2

*38 E0800005 ADD 0 5

*3C E2857002 ADD 7 5 #2

*40 E1877407 OR 7 SL #8

*44 E1877807 OR 7 SL #10

*48 E3A06040 LET 6 #40

*4C E48D7004 SRMIAX 7 D #4

*50 E2566001 SUBX 6 #1

*54 1AFFFFFC BNE *4C

*58 E7536005 LRMBDB 6 3 5

*5C E2855001 ADD 5 #1

*60 E74D5006 SRMBDB 5 D 6

*64 E2555002 SUBX 5 #2

*68 2AFFFFFA BHE *58

*6C E0435002 SUB 5 3 2

*70 E0414000 SUB 4 1 0

*74 E1500001 TSUB 0 1

*78 91550004 TSUB.LE 5 4

*7C 83E04000 LETN.HI 4 #0

*80 8A00000A BHI *B0

*84 E7506005 LRMBDB 6 0 5

*88 E7537005 LRMBDB 7 3 5

*8C E1360007 TEOR 6 7

*90 15D06001 LRMBIB.NE 6 0 #1

*94 175D6006 LRMBDB.NE 6 D 6

*98 10800006 ADD.NE 0 6

*9C 1AFFFFF2 BNE *6C

*A0 E2555001 SUBX 5 #1

*A4 2AFFFFF6 BHE *84

*A8 E0434002 SUB 4 3 2

*AC E0404004 SUB 4 0 4

*B0 E24DDF40 SUB D #100

*B4 E93D80E1 LRRMDBX F7650 D

; WEBERLARS.TATA@GMAIL.COM

; 2011.06.02. 23:47 PRGEND