Tips und Tricks für Programmierer

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