Rekursive programmierung in Assembler
Ein in höheren Programmiersprachen häufig eingesetzter Programmierstil ist die „rekursive Programmierung“.
Ein Unterprogramm ruft sich hierbei selber auf, bis ein Abbruchkriterium erreicht ist. auf Assembler-Ebene werden rekursive Algorithmen recht selten eingesetzt. Da der 68000-Prozessor des Atari ST bzw. der 68030 des TT diese Art der Programmierung jedoch durch spezielle Befehle unterstützt, ist es lohnenswert, sich einmal mit dieser Problematik auseinanderzusetzen.
Eine besonders gute Anwendung für rekursive Routinen ist das Durchsuchen einer Diskette oder Festplatte nach allen Dateien und Ordnern. Um alle Verzeichnisse eines Mediums unter die Lupe zu nehmen, ist rekursive Programmierung unumgänglich. Im Programmverlauf müssen alle Dateien überprüft werden. Stößt man dabei auf einen Ordner, muß man das entsprechende Verzeichnis öffnen. Die Suche erfolgt zunächst in diesem Verzeichnis. Stößt man dabei erneut auf einen Ordner, muß auch dieser geöffnet und durchsucht werden. Wurde ein Unterverzeichnis komplett bearbeitet, muß das Programm auf der nächsthöheren Verzeichnisebene Weiterarbeiten, und zwar genau dort, wo vorher abgebrochen werden mußte. Während ein Ordner durchsucht wird, dürfen die Daten, die für das Fortführen der Suche in der nächsthöheren Verzeichnisebene benötigt werden, nicht verlorengehen.
Welche Befehle stellt der MC68000 für die rekursive Programmierung zur Verfügung?
Es sind dies der LINK- sowie der UNLINK-Befehl. Mit ihnen kann für Unterprogramme ein eigener Stack-Bereich aufgebaut werdender ausschließlich diejenigen Daten enthält, die für das aktuelle Unterprogramm relevant sind. Für jedes Unterprogramm wird ein eigener Stack angelegt, so daß keinerlei Daten verlorengehen.
Nun zur Wirkungsweise des LINK-Befehls. Stößt der Prozessor z.B. auf die Anweisung
LINK #12,A6
so geschieht folgendes: Zunächst wird das Adreßregister A6 auf dem Stack abgelegt. Anschließend wird der Inhalt des Stackpointers (also Adreßregister A7) nach A6 übertragen. Nun wird noch der Befehlsparameter (also in diesem Fall die 12) auf den Stackpointer addiert. Nach diesen Operationen zeigt A6 auf einen freien Speicherbereich oberhalb des Stackpointers und unterhalb von A6, der eine Größe von 12 Bytes hat. In diesem Adreßbe-reich können nun lokale Variablen abgelegt werden, wobei A6 als Pointer auf diesen lokalen Bereich dient.
Mit dem UNLINK-Befehl kann der Stackbereich wieder abgebaut werden:
UNLINK A6.
Hierbei wird der alte Inhalt von A6 und A1 wiederhergestellt.
Ruft sich ein Unterprogramm mehrmals selber auf, so wird jeweils über die LINK-Anweisung Platz für die lokalen Variablen auf dem Stack geschaffen. Diese Variablen sind über negative Offsets in Verbindung mit A6 zu erreichen. Bei der Verwendung von LINK-Befeh-len muß man natürlich besonders darauf achten, daß der Speicherbereich, den das eigene Programm für den Stack reserviert, ausreichend dimensioniert ist.
Nun zurück zur eigentlichen Aufgabenstellung. Beim Durchsuchen eines Mediums ist es wichtig, beim Bearbeiten einer neuen Verzeichnisebene (also eines neuen Ordners) nicht aus den Augen zu verlieren, in welcher Ebene man sich vorher befunden hat. Alle Informationen, die hierzu benötigt werden, stellt GEMDOS uns im DTA-Puffer zur Verfügung, der wie folgt aufgebaut ist:
typedef struct {
char d_reserved[21];
/* für GEMDOS reserviert */
char d_attrib;
/* Dateiattribut */
int d_time;
/* Uhrzeit der Dateierstellung */
int d_date;
/* Datum der Dateierstellung */
long d_length;
/* Dateilänge in Bytes */
char d_fname[14];
/* Dateiname und Extension */
} DTA;
Die aktuelle Adresse dieser Struktur kann mittels Fgetdta vom GEMDOS erfragt werden. Um eine neue Adresse festzusetzen, existiert der Fsetdta-Aufruf. Die Daten in der DTA enthalten alle Informationen, die man benötigt, um ein komplettes Medium rekursiv durchsuchen zu können. Für jedes Verzeichnis, das durchsucht wird, muß eine eigene DTA bereitgestellt werden, die so lange benötigt wird, wie man sich innerhalb dieses Verzeichnisses befindet. Es ist somit sinnvoll, die DTA, die ja lokale Variablen enthält, innerhalb des Stack-Bereichs unterzubringen. Pro DTA werden 44 Bytes benötigt, so daß mit Hilfe des LINK-Befehls ein entsprechend großer lokaler Stack geschaffen werden muß.
******************************************
* Rekursives Durchsuchen von Directories *
* *
* in Assembler *
* by Uwe Seimet *
* (c) 1991 MAXON Computer *
******************************************
GEMDOS = 1
DSETDRV = 14
FSETDTA = 26
FGETDTA = 47
DSETPATH = 59
MSHRINK = 74
FSFIRST = 78
FSNEXT = 79
text
move.l sp,a0
lea stack+400,sp
move.l 4(a0),a0
move.l 12(a0),a1 ;Länge des TEXT-Segments
add.l 20(a0),a1 ;DATA-Segment
add.l 28(a0),a1 ;BSS-Segment
lea $100(a1),a1 ;für Basepage
move.l a1,-(sp)
move.l a0,-(sp)
clr -(sp)
move #MSHRINK,-(sp)
trap #GEMDOS ;nicht benötigten Speicher freigeben
lea 12(sp),sp
tst.1 d0
bmi.s error
bsr.s act
error: clr -(sp)
trap #GEMDOS
act:
lea path,a3
move.b #"\\",(a3)+
clr.b (a3)
move #FGETDTA,-(sp)
trap #GEMDOS
addq.l #2,sp
move.l d0,a4
next: pea path
move #DSETPATH,-(sp)
trap #GEMDOS
addq.l #6,sp
link a6,#-44 ;Stackbereich für DTA-Puffer
pea (a4) ;alter DTA-Bereich
lea 4(sp),a4
bsr.s setdta
move #$10,-(sp)
pea dummy(pc)
move #FSFIRST,-(sp)
trap #GEMDOS
addq.l #0,sp
bra.s free2
loop: move #FSNEXT,-(sp)
trap #GEMDOS
addq.l #2,sp
free2: tst.l d0 ;noch etwas gefunden?
bne.s free0 ;nein-
cmp.b #$e5,30(a4) ;gelöschter Eintrag?
beq loop ;ja-
btst #4,21(a4) ;Ordner?
bne.s folder ;ja-
bsr.s file
bra loop
folder: cmp.b #'.',30(a4) ; Verwaltungseintrag?
beq loop ;ja-
lea 30(a4),a0 ;Pointer auf Namen des Ordners
copy: move.b (a0)+,(a3)+ ;Pfad erweitern
bne copy
move.b #'\\',-1(a3)
clr.b (a3)
bsr next
bsr.s setdta
bra loop
free0: move.l (sp)+,a4 ;alter DTA-Bereich
unlk a6
subq.l #1, a3
cmp.l #path,a3 ;Ende der Suche?
beq.s ret ;ja-
lop: cmp.b #'\\’,-(a3)
bne lop
addq.l #1,a3
clr.b (a3)
ret: rts
setdta:
pea (a4) ;neuer DTA-Bereich
move #FSETDTA,-(sp)
trap #GEMDOS
addq.l #6,sp
rts
file:
rts
dummy: dc.b "*.*",0
bss
path: ds.b 130
stack: ds.l 100
Uwe Seimet