Sortier-Algorithmus in Assembler
Wer öfter mit Tabellen arbeitet, weiß, wie zeitaufwendig eine Sortierung der darin befindlichen Daten ist. Eine kleine Routine in Assembler benötigt selbst für größere Mengen nur kurze Zeit. Wir verwenden den sogenannten »Bubble-Sort«-Algorithmus (Listing 1), der eine Tabelle von Zahlen nach steigendem Wert sortiert. Kleinere Zahlen gelangen dabei wie Blasen im Wasser nach oben. Das Programm verfolgt einen einfachen Algorithmus. Dieser vergleicht lediglich zwei aufeinander folgende Zahlen. War die zweite Zahl kleiner, werden die beiden Zahlen in der Tabelle vertauscht, das sog. Austausch-Bit gesetzt und die nächsten Zahlen bearbeitet. Der Sortiervorgang ist schließlich beendet, wenn ein Durchlauf ohne Vertauschung stattfindet. Die Routine benötigt folgende Parameter: die Anfangsadresse der Tabelle sowie deren Länge. Die Startadresse übergeben Sie in Adreßregister A1. Außerdem enthält der erste Tabelleneintrag die Anzahl der auf ihn folgenden Einträge. Die Routine liefert keinen Rückgabewert. Bitte beachten Sie, daß das Listing eine Tabelle mit Einträgen der Breite »Word« verarbeitet. Für andere Datentypen ist eine entsprechende Anpassung erforderlich. (ah)
Listing 1: Klein aber schnell: die Bubblesort-Routine
; Bubble-Sort
; Tabellenanfang in a1
sortierung:
movem.l d0-d2/a0-a1, -(sp) ; Register retten
s_begin:
move.w (a1), d0 ; Anzahl der Tabelleneintäge
lea 2(a1), a0
bclr #7, d2 ; Austausch-Bit löschen
subq.w #2, d0
s_loop:
move.w (a0)+, d1 ; Eintag i in d1
cmp.w (a0), d1 ; mit Eintrag i+1 vergleichen
ble.s s_ende ; falls i <= i+1, dann Ende
move.w (a0), -2(a0) ; Tabelleneinträge
move.w d1, (a0) ; vertauschen
bset #7, d2 ; Austausch-Bit setzen
s_ende:
dbra d0, s_loop
btst #7, d2 ; Austausch-Bit gesetzt?
bne.s s_begin ; Ja, dann nochmal
movem.l (sp)+, d0-d2/a0-a1 ; Register zurück
fertig:
rts
# Suchen einer beliebigen Zeichenkette
Für die Verwaltung einer großen Menge Textdaten ist es oftmals erforderlich, bestimmte Textpassagen zu suchen. Unsere Routine arbeitet nach einem einfachen aber effektiven Schema (Listing 2). Zunächst sucht sie den Speicher nach dem ersten Buchstaben des Suchstrings ab. Erst wenn dieser übereinstimmt, vergleicht die Routine jeden weiteren Buchstaben. Schlägt dieser Vergleich z.B. nach der vierten Stelle fehl, geht‘s wieder auf die Suche nach dem ersten Buchstaben, bis eine komplette Übereinstimmung vorhanden oder die Speichergrenze erreicht ist. Ein »:« muß den Suchstring beenden. Als Parameter erwartet die Routine die Startadresse des zu suchenden Textes in A1. Die Startadresse des Speicherbereichs, in dem die Suche stattfindet, übergeben Sie in A0. Das Ende dieses Bereiches muß mit einem »*« markiert sein. Bei erfolgreicher Suche gibt die Routine in A3 die Anfangsadresse des gefundenen Strings zurück.
(ah)
Listing 2: Gezielte Suche nach Textpassagen aller Art
; Routine zum Suchen eines Strings
; Startadresse des Suchstrings in A1
; Startadresse des Speicherbereichs in A0
movem.l d1/a2, -(sp) ; Register retten
movea.l a1, a2
cmpi.b #‘:‘, (a1) ; Enthält String ein Zeichen?
beq.s gotcha ; nein, dann raus
move.b (a1), d1 ; Erstes Zeichen nach d1
bra.s erster
wied:
movea.l a2, a1 ; Startadresse Suchstring
addq.l #1, a3 ; Ein Zeichen weiter
movea.l a2, a0 ; kopieren
erster:
cmp.b (a0)+, d1 ; 1. Buchstabe stimmt?
beq.s weiter
cmpi.b #‘*‘, (a0) ; Ende des Speicherbereiches
bne.s erster
bra.s nichts_da ; nein, dann wieder Suchen
weiter:
addq.l #1, a1 ; auf zweiten Buchstaben zeigen
movea.l a0, a3 ; Adresse kopieren
subq.l #1, a3
testen:
cmpi.b #‘:‘, (a1) ; Ende des Suchstrings?
beq.s gotcha ; Suche erfolgreich!
cmpi.b #‘*‘, (a0) ; Ende des Speicherbereiches?
beq.s nichts_da ; ja, dann nichts gefunden.
cmpm.b (a0)+, (a1)+ ; Vergleichen
beq.s testen ; falls gleich -> weiter machen
bra.s wied ; sonst wieder von vorne
nichts_da:
movea.l #0, a3
gotcha:
movem.l (sp)+, d1/a2 ; Register zurück
rts