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
Aus: ST-Computer 01 / 1992, Seite 96

Links

Copyright-Bestimmungen: siehe Über diese Seite