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