String-Descriptor-Stack

Aus C64-Wiki
Wechseln zu: Navigation, Suche

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. Grundlegende Aufgabe des Stapels ist die Unterstützung bei der Auswertung von Zeichenkettenausdrücken oder Zeichenketten-Funktionen.


Aufbau[Bearbeiten]

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[Bearbeiten]

Interpreter[Bearbeiten]

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

  • Initialisieren[1]
  • Element auf den SDS legen (mit Überprüfung auf Überlauf)[2]
  • Element vom SDS nehmen[3]

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[Bearbeiten]

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

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

Garbage Collection[Bearbeiten]

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[4] 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 eintreten eine Korrumpierung am String-Heap passieren: 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[Bearbeiten]

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

Quellen[Bearbeiten]

  1. AAY64 BASIC ROM: $E3BF/58303: Initialize BASIC RAM Sprache:englisch
  2. AAY64 BASIC ROM: $B4D5/46293: Save String Descriptor Sprache:englisch als Teil von $B487/46215: Set Up String Sprache:englisch
  3. AAY64 BASIC ROM: $B6DB/46811: Clean Descriptor Stack Sprache:englisch
  4. BSOS-8296 auf GitHub Sprache:englisch