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:

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ß.