String-Descriptor-Stack

Beim Temporary String Descriptor Stack (abgekürzt SDS) handelt es sich um einen Stapel, auf den der BASIC-Interpreter (in der Microsoft-Variante) zwischenspeichert, die bei der Verarbeitung von Zeichenketten mit flüchtigem Charakter auftreten. Solche Zeichenketten haben ihren bestimmenden String-Descriptor vorerst nur auf dem Stapel statt fest verankert in einer Variable oder einem Array. Ein Beispiel für einen temporären String ist die Zeichenfolge "HALLO" in der Anweisung PRINT "HALLO". Grundlegende Aufgabe des Stapels ist die Unterstützung bei der Auswertung von Zeichenkettenausdrücken oder Zeichenketten-Funktionen.

Aufbau

Bei BASIC V2 ist der SDS in der Zeropage positioniert und wächst (im Gegensatz zum Prozessorstack in Richtung steigender Adressen. Konkret ist er wie folgt aufgebaut:

    String am String-Heap, wenn der Descriptor eine Länge ungleich 0 hat.
                         ▲
                         │
$0022                    │
      ┌───────────────┐  │
$0021 │   High-Byte   │  │       Ende des Stapelbereichs
      ├─             ─┤  │
$0020 │    Low-Byte   │  │       3. Element (unbenutzter String-Descriptor)
      ├─             ─┤  │
$001F │     Länge     │  │
      ├───────────────┤  │
$001E │   High-Byte   │  │
      ├─             ─┤  │
$001D │    Low-Byte   │  │       2. Element (unbenutzter String-Descriptor)
      ├─             ─┤  │
$001C │    Länge      │ ◄───┐
      ├───────────────┤  │  │
$001B │  High-Byte    ││ │  │
      ├─             ─┤├─┘  │
$001A │   Low-Byte    ││    │    1. Element (benutzter String-Descriptor)
      ├─             ─┤     │
$0019 │    Länge      │ ◄─┐ │    Beginn des Stapelbereichs
      └───────────────┘   │ │
      ┌───────────────┐   │ │
$0018 │      $00      ││  │ │    TOSS (Top Of temporary String Stack)
      ├─             ─┤├──┘ │    16-Bit-Zeiger (High-Byte immer 0)
$0017 │      $19      ││    │    zeigt das letzte Element
      └───────────────┘     │
      ┌───────────────┐     │
$0016 │      $1C      │├────┘    TSSP (Temporary String Stack Pointer)
      └───────────────┘          zeigt auf das nächste freie Element 

In dieser Darstellung zeigt den SDS mit genau einem Element.

Die am SDS befindlichen Elemente sind String-Descriptoren. Ein Descriptor besteht aus 3 Bytes, enthält die Länge des Strings im Wertebereich von 0 bis 255 (ein Byte) und die Adresse des Strings am String-Heap (2 Bytes: Low-Byte und High-Byte).

Andere BASIC-Varianten

Andere CBM-BASIC-Varianten sind im Wesentlichen bis auf die konkreten Adressen gleich strukturiert, lediglich bei der CBM-II-Serie gibt es deutliche organisatorische Änderungen, wegen der universelleren Speicherarchitektur.

BASIC-Variante	TSSP	TOSS	Bereich	Elementanzahl (*)	Descriptor-Länge (Bytes)
BASIC 2.0	$16	$17/$18	$0019 − $0021	3	3
BASIC 4.0	$13	$14/$15	$0016 − $001E	3	3
BASIC 4.0+ 128K	$1D	$20/$21	$2:FAC8 − $2:FAD7	3	4
BASIC 4.0+ 256K	$1D	$20/$21	$4:FAC8 − $4:FAD7	3	4
BASIC 3.5	$16	$17/$18	$0019 − $0021	3	3
BASIC 7.0	$18	$19/$1A	$001B − $0023	3	3

(*) Die Elementanzahl laut "Stapeltiefe ermitteln".

Im Falle von BASIC 4.0+ handelt es sich um 3-Byte-Adressen, wobei der mit ":" getrennte Präfix die entsprechende Bank (siehe CBM-II-CPU-Architektur) angibt.

Verwendung

Interpreter

Die Manipulation des SDS erfolgt im BASIC-Interpreter über einige wenige Routinen, die folgende Operationen durchführen:

• Initialisieren
• Element auf den SDS legen (mit Überprüfung auf Überlauf)
• Element vom SDS nehmen

Bei der Assemblerprogrammierung kann auf den SDS bequem per Adressierungsart Zeropage X-indiziert zugegriffen werden, in dem das X-Register z.B. für das nächste freie Element mit dem Wert des TSSP geladen wird. Einzelne Komponenten können dann mit unterschiedlichem Offset angesprochen werden:

• 0,X für String-Länge,
• 1,X für String-Adresse Low-Byte,
• 2,X für String-Adresse High-Byte

Das Verändern des TSSP geht unkompliziert mit dreifachem INX oder DEX mit anschließendem Ablegen des geänderten Wertes in der Zeropage.

BASIC-Ebene

Der SDS wird bei der Auswertung von String-Ausdrücken in Anspruch genommen:

• Auswertung von String-Operationen, dem Zusammenfügen mittels "+"
• Auswertung von String-Funktionen, wie LEFT$, RIGHT$, MID$, STR$, CHR$

Ein Überlauf des SDS wird mit der Fehlermeldung ?FORMULA TOO COMPLEX ERROR quittiert.

Garbage Collection

Bei der Garbage Collection (GC) ist üblicherweise auch der SDS zu berücksichtigen. Nicht alle Implementierungen kommen dem nach. Speziell die Back-Pointer-Implementierungen in der Urvariante von BASIC 4.0 und die optimierte von BSOS-8296 verzichten auf die Behandlung des SDS. In allen zeitlich nach BASIC V2 folgenden Varianten, ist der SDS in der Implementierung eingebunden. Ohne die entsprechende Berücksichtigung, kann bei sehr beengten Verhältnissen eine Korrumpierung am String-Heap eintreten: In einer Ausdrucksauswertung kommt es zu einer Anforderung des Platzes für einen Ergebnis-String, welche die GC auslöst. Der geschaffene Platz liegt aber in dem Bereich der zuvor temporär angelegten Strings am SDS und das Ergebnis der Operation besteht dann aus teilweise überschriebenen Teilen der ursprünglichen Strings.

Stapeltiefe ermitteln

Hier wird ein Fehler des Interpreters ausgenutzt, bei dem die Funktion POS() inkorrekterweise den Argumenttyp nicht prüft, im String-Fall kein entsprechendes String-Cleanup durchführt und damit der temporär angelegte String am SDS liegen bleibt.

10 V=POS(""):C=C+1
20 GOTO 10

Ausgabe nach RUN:

?FORMULA TOO COMPLEX ERROR IN 10

PRINT C

liefert dann

3

Beim 4. Durchlauf, nach dem der SDS bereits drei Elemente aufgenommen hat, kommt es zum Abbruch mit obigem Fehler. Die Zählvariable C enthält dann die Anzahl der am SDS befindlichen Elemente.