AVR-Tutorial: Mehrfachverzweigung

Aus der Mikrocontroller.net Artikelsammlung, mit Beiträgen verschiedener Autoren (siehe Versionsgeschichte)
Wechseln zu: Navigation, Suche

Einleitung

Oft ist es in einem Programm notwendig, eine Variable auf mehrere Werte zu prüfen und abhängig vom Ergebnis verschiedene Aktionen auszulösen. Diese Konstruktion nennt man Mehrfachverzweigung. In einem Struktogramm sieht das so aus:

Mv struktogramm.png

In C gibt es direkt dafür eine Konstruktion namens switch. 

switch (variable) {
  case 1:       // Anweisungen für diesen Zweig, wenn variable == 1
    break;
  case 17:      // Anweisungen für diesen Zweig, wenn variable == 17
    break;
  case 33:      // Anweisungen für diesen Zweig, wenn variable == 33
    break;
  case 9:       // Anweisungen für diesen Zweig, wenn variable == 9
    break;
  case 22:      // Anweisungen für diesen Zweig, wenn variable == 22
    break;
  default:      // Anweisungen wenn keine der oben definierten Bedingungen erfüllt ist
    break;
}

In Assembler muss man so etwas „zu Fuß“ programmieren. Die verschiedenen Lösungen sollen hier betrachtet werden.

Einfacher Ansatz

Im einfachsten Fall verwendet man eine lange Kette von cpi- und brne-Befehlen. Für jeden Zweig benötigt man zwei Befehle. 

; Mehrfachverzweigung Version A

; Einfacher Ansatz, mit vielen CPI

start_vergleich:

    cpi     r16, 1
    brne    zweig_0

; hier stehen jetzt alle Anweisungen für diesen Zweig r16=1

    rjmp    ende_vergleich
zweig_0:
    cpi     r16, 17
    brne    zweig_1

; hier stehen jetzt alle Anweisungen für diesen Zweig r16=17

    rjmp    ende_vergleich
zweig_1:
    cpi     r16, 33
    brne    zweig_2

; hier stehen jetzt alle Anweisungen für diesen Zweig r16=33

    rjmp    ende_vergleich
zweig_2:
    cpi     r16, 9
    brne    zweig_3

; hier stehen jetzt alle Anweisungen für diesen Zweig r16=9

    rjmp    ende_vergleich
zweig_3:
    cpi     r16, 22
    brne    kein_Treffer

; hier stehen jetzt alle Anweisungen für diesen Zweig r16=22

    rjmp    ende_vergleich
kein_Treffer:

; hier stehen jetzt alle Anweisungen für den Fall, dass keiner der Vergleiche erfolgreich war

ende_vergleich:

    rjmp    ende_vergleich          ; nur für Simulationszwecke! ENTFERNEN!

Eigenschaften

  • Programmspeicherbedarf: 6·N Bytes (N = Anzahl der Zweige)
  • Laufzeit: 3·n−1, Nicht gefunden: 3·N (N = Anzahl der Zweige, n = ausgewählter Zweig)

Vorteile

  • leicht verständlich
  • Es können beliebige Vergleichswerte geprüft werden

Nachteile

  • relativ hoher Programmspeicherbedarf
  • die Größe der Zweige ist stark begrenzt, weil der Befehl brne maximal 63 Worte weit springen kann!
  • die einzelnen Zweige haben unterschiedliche Durchlaufzeiten, der letzte Zweig ist am langsamsten
  • nur bedingt übersichtlicher Quellcode

Sprungtabelle

Oft liegen die einzelnen Vergleichswerte nebeneinander (z. B. 7…15), z. B. bei der Übergabe von Parametern, Zustandsautomaten, Menüeinträgen etc. In so einem Fall kann man mittels einer Sprungtabelle das Programm verkürzen, beschleunigen und übersichtlicher gestalten. 

.include "m8def.inc"

; Mehrfachverzweigung Version B

; Clevere Version mit Sprungtabelle
; minimum und maximum sind auf 0..255 begrenzt!

.equ minimum = 3
.equ maximum = 7

start_vergleich:

    subi    r16, minimum                ; Nullpunkt verschieben
    cpi     r16, (maximum-minimum+1)    ; Index auf Maximum prüfen
    brsh    kein_Treffer                ; Index zu groß -> Fehler
    ldi     ZL, low(Sprungtabelle)      ; Tabellenzeiger laden, 16 Bit
    ldi     ZH, high(Sprungtabelle)
    add     ZL, r16                     ; Index addieren, 16 Bit
    ldi     r16, 0
    adc     ZH, r16
    ijmp                                ; indirekter Sprung in Sprungtabelle

kein_treffer:

; hier stehen jetzt alle Anweisungen für den Fall, dass keiner der Vergleiche erfolgreich war

    rjmp    ende_vergleich

Sprungtabelle:
    rjmp    zweig_0
    rjmp    zweig_1
    rjmp    zweig_2
    rjmp    zweig_3
    rjmp    zweig_4

zweig_0:

; hier stehen jetzt alle Anweisungen für diesen Zweig

    rjmp    ende_vergleich

zweig_1:

; hier stehen jetzt alle Awneisungen für diesen Zweig

    rjmp    ende_vergleich

zweig_2:

; hier stehen jetzt alle Anweisungen für diesen Zweig

    rjmp    ende_vergleich

zweig_3:

; hier stehen jetzt alle Anweisungen für diesen Zweig

    rjmp    ende_vergleich

zweig_4:

; hier stehen jetzt alle Anweisungen für diesen Zweig

    rjmp    ende_vergleich

ende_vergleich:

; hier geht das Programm weiter

    rjmp    ende_vergleich          ; nur für Simulationszwecke! ENTFERNEN!

Programmbeschreibung

Wie ist dieses Programm nun zu verstehen? Das Prinzip beruht darauf, daß in einer gleichmäßigen Tabelle Sprungbefehle auf einzelne Programmzweige abgelegt werden. Das ist praktisch genauso wie der AVR Interrupts verarbeitet. Über einen Index (0…N) wird ein Sprungbefehl ausgewählt und ausgeführt. Der entscheidende Befehl dazu ist ijmp.

Zunächst muss der Wertebereich, auf welchen die Variable geprüft werden soll (Minimum bis Maximum), normiert werden (0 bis (Maximum−Minimum)). Dazu wird einfach das Minimum subtrahiert. 

    subi    r16, minimum                ; Nullpunkt verschieben

Danach muss geprüft werden, ob der maximale Index nicht überschritten wird. Denn ein Sprung auf nichtexistierende Einträge oberhalb der Sprungtabelle wäre fatal! 

    cpi     r16, (maximum-minimum+1)    ; Index auf Maximum prüfen
    brsh    kein_Treffer                ; Index zu groß -> Fehler

Danach muss der indirekte Sprung vorbereitet werden. Dazu wird die Adresse der Sprungtabelle in das Z-Register geladen, welches ein 16-Bit-Register ist und gleichbedeutend mit r30 und r31. 

    ldi     ZL, low(Sprungtabelle)      ; Tabellenzeiger laden, 16 Bit
    ldi     ZH, high(Sprungtabelle)

Danach muss der Index addiert werden, dies ist eine 16-Bit-Addition. 

    add     ZL, r16                     ; Index addieren, 16 Bit
    ldi     r16, 0
    adc     ZH, r16

Zu guter Letzt wird der indirekte Sprung in die Sprungtabelle ausgeführt. 

    ijmp                                ; indirekter Sprung in Sprungtabelle

In der Sprungtabelle wird dann zum jeweiligen Zweig gesprungen. 

Sprungtabelle:
    rjmp    zweig_0
    rjmp    zweig_1
    rjmp    zweig_2
    rjmp    zweig_3
    rjmp    zweig_4

Der Zweig für einen ungültigen Index folgt direkt nach dem ijmp, weil der Befehl brsh nur maximal 63 Worte weit springen kann.

Eigenschaften

  • Programmspeicherbedarf: 4·N+18 Bytes (N = Anzahl der Zweige)
  • Laufzeit: 12, Nicht gefunden: 4
  • Maximale Gesamtgröße der Zweige wird durch den Befehl rjmp begrenzt (±4 kB). Das sollte aber nur in sehr wenigen Fällen ein Problem sein (Man wird kaum einen AVR mit 8 kB Flash mit einer einzigen Mehrfachverzweigung füllen!).

Vorteile

  • relativ niedriger Programmspeicherbedarf
  • Die einzelnen Zweige haben unabhängig von der Größe der Sprungtabelle eine konstante und kurze Durchlaufzeit von 12 Takten.
  • übersichtlicher Quellcode

Nachteile

  • Die Vergleichswerte müssen lückenlos aufeinander folgen.

Lange Sprungtabelle

Wenn man doch mal eine GIGA-Mehrfachverzweigung braucht, dann hilft die Version C. 

.include "m16def.inc"

; Mehrfachverzweigung Version C

; Clevere Version mit langer Sprungtabelle
; funktioniert nur mit AVRs mit mehr als 8 KB Flash
; minimum und maximum sind auf 0..127 begrenzt!

.equ minimum = 3
.equ maximum = 7

start_vergleich:

    subi    r16, minimum                ; Nullpunkt verschieben
    cpi     r16, (maximum-minimum+1)    ; Index auf Maximum prüfen
    brsh    kein_Treffer                ; Index zu groß -> Fehler
    ldi     ZL, low(Sprungtabelle*2)    ; Tabellenzeiger laden, 16 Bit
    ldi     ZH, high(Sprungtabelle*2)
    lsl     r16                         ; Index mit 2 multiplizieren
    add     zl, r16                     ; Index addieren, 16 Bit
    ldi     r16, 0
    adc     zh, r16
    lpm     r16, Z+                     ; Low Byte laden und Pointer erhöhen
    lpm     ZH, Z                       ; zweites Byte laden
    mov     ZL, r16                     ; erstes Byte in Z-Pointer kopieren
    ijmp                                ; indirekter Sprung

kein_treffer:

; hier stehen jetzt alle Anweisungen für den Fall, dass keiner der Vergleiche erfolgreich war

    jmp     ende_vergleich

Sprungtabelle:
.dw zweig_0
.dw zweig_1
.dw zweig_2
.dw zweig_3
.dw zweig_4

zweig_0:

; hier stehen jetzt alle Anweisungen für diesen Zweig

    jmp    ende_vergleich

zweig_1:

; hier stehen jetzt alle Awneisungen für diesen Zweig

    jmp    ende_vergleich

zweig_2:

; hier stehen jetzt alle Anweisungen für diesen Zweig

    jmp    ende_vergleich

zweig_3:

; hier stehen jetzt alle Anweisungen für diesen Zweig

    jmp    ende_vergleich

zweig_4:

; hier stehen jetzt alle Anweisungen für diesen Zweig

ende_vergleich:

; hier geht das Programm weiter

    jmp    ende_vergleich          ; nur für Simulationszwecke! ENTFERNEN!

Programmbeschreibung

Diese Version ist der Version B sehr ähnlich. Der Unterschied besteht darin, daß in Version B die Sprungtabelle mit Sprungbefehlen gefüllt ist (rjmp), während in Version C die Startadressen der Funktionen dort abgelegt sind. D. h. man kann nicht in die Sprungtabelle springen, sondern muss sich mit Hilfe des Index die richtige Adresse aus der Sprungtabelle lesen und mit ijmp anspringen. Klingt sehr ähnlich, ist aber dennoch verschieden.

Die ersten drei Befehle sind identisch, es wird der Index normiert und auf das Maximum geprüft. 

    subi    r16, minimum                ; Nullpunkt verschieben
    cpi     r16, (maximum-minimum+1)    ; Index auf Maximum prüfen
    brsh    kein_Treffer                ; Index zu groß -> Fehler

Die nächsten zwei Befehle laden wieder die Anfangsadresse der Sprungtabelle. Doch halt, hier wird die Adresse der Sprungtabelle mit zwei multipliziert. Des Rätsels Lösung gibt es weiter unten. 

    ldi     ZL, low(Sprungtabelle*2)    ; Tabellenzeiger laden, 16 Bit
    ldi     ZH, high(Sprungtabelle*2)

Der Index wird ebenfalls mit zwei multipliziert. 

    lsl     r16                         ; Index mit 2 multiplizieren

Danach erfolgt eine 16-Bit-Addition. 

    add     zl, r16                     ; Index addieren, 16 Bit
    ldi     r16, 0
    adc     zh, r16

Nun zeigt unser Z-Zeiger auf den richtigen Tabelleneintrag. Jetzt müssen zwei Bytes aus dem Flash-ROM geladen werden. Das geschieht mit Hilfe des lpm-Befehls (Load Program Memory). Hier wird die erweiterte Version des lpm-Befehls verwendet, wie sie nur auf größeren AVRs verfügbar ist. Dabei wird ein Byte in Register r16 geladen und gleichzeitig der Z-Pointer um eins erhöht. Damit zeigt er wunderbar auf das nächste Byte, welches auch geladen werden muss. 

    lpm     r16, Z+                     ; Low Byte laden und Zeiger erhöhen

Der zweite lpm-Befehl ist etwas ungewöhnlich, denn er überschreibt einen Teil des Z-Pointers! In den meisten Programmen wäre das ein Schuss ins Knie (Programmierfehler!), da wir aber den Z-Pointer danach sowieso mit neuen Daten laden, ist das OK. 

    lpm     ZH, Z                       ; zweites Byte laden

Das zuerst gelesene Byte wird in den Z-Pointer kopiert. Nun steht die Startadresse des gewählten Zweigs im Z-Pointer. 

    mov     ZL, r16                     ; erstes Byte in Z-Zeiger kopieren

Zu guter Letzt wird der indirekte Sprung ausgeführt und bringt uns direkt in den Programmzweig. 

    ijmp                                ; indirekter Sprung direkt in den Programmzweig

Der Zweig für einen ungültigen Index folgt direkt nach dem ijmp, weil der Befehl brsh nur maximal 63 Worte weit springen kann.

Eigenschaften

  • Programmspeicherbedarf: 6·N+26 Bytes (N = Anzahl der Zweige)
  • unbegrenzte Sprungweite

Vorteile

  • relativ niedriger Programmspeicherbedarf
  • Die einzelnen Zweige haben unabhängig von der Größe der Sprungtabelle eine konstante und kurze Durchlaufzeit von 18 Takten.
  • übersichtlicher Quellcode

Nachteile

  • Die Vergleichswerte müssen lückenlos aufeinander folgen.
  • geringfügig höherer Programmspeicherbedarf (8 Byte mehr) und längere Durchlaufzeit (6 Takte mehr) als Version B

Z-Pointer leicht verständlich

Auf den ersten Blick scheint es sonderbar, daß Version B die Adresse der Sprungtabelle direkt lädt, während Version C sowohl Anfangsadresse als auch Index mit zwei multipliziert. Warum ist das so?

Version B verwendet nur den Befehl ijmp. Dieser erwartet im Z-Register eine Adresse zur Programmausführung, eine Wort-Adresse. Da der Programmspeicher des AVR 16 Bit breit ist (=1 Wort = 2 Bytes), werden nur Worte adressiert, nicht jedoch Bytes! Genauso arbeitet der Assembler. Jedes Label entspricht einer Wort-Adresse. Damit kann man mit einer 12-Bit-Adresse 4.096 Worte adressieren (=8.192 Bytes). Wenn man sich die Befehle der einzelnen AVRs anschaut, wird klar, daß alle AVRs mit 8 KB und weniger Flash-ROM nur die Befehle rjmp und rcall besitzen. Denn sie brauchen nicht mehr! (Hinweis: Der ATmega8 besitzt die Befehle ijmp und icall.)

Mit 12 Adressbits, welche direkt in einem Wort im Befehl rjmp bzw. rcall kodiert sind, kann der gesamte Programmspeicher erreicht werden. Größere AVRs besitzen call und jmp, dort ist die Adresse als 22- bzw. 16-Bit-Zahl kodiert, deshalb brauchen diese Befehle auch 2 Worte Programmspeicher.

Der Befehl lpm dient zum Laden einzelner Bytes aus dem Programmspeicher. Das ist vor allem für Tabellen mit konstanten Werten sehr nützlich (7-Segment-Dekoder, Zeichensätze, Kennlinien, Parameter, Texte, etc.) Doch wie kommt man nun in dem wortweise adressierten Programmspeicher an einzelne Bytes? Ganz einfach. Der AVR „mogelt“ hier und erwartet im Z-Register eine Byte-Adresse. Von dieser Adresse bilden die Bits 15…1 die Wortadresse, welche zur Adressierung des Programmspeichers verwendet wird. Bit 0 entscheidet dann, ob das hoch- oder niederwertige Byte in das Zielregister kopiert werden soll (0: niederwertiges Byte; 1: höherwertiges Byte).

Darum muss bei Verwendung des Befehls lpm die Anfangsadresse immer mit zwei multipliziert werden. 

    ldi     ZL, low(Sprungtabelle*2)    ; Tabellenzeiger laden, 16 Bit
    ldi     ZH, high(Sprungtabelle*2)

In Version C muss zusätzlich der Index mit zwei multipliziert werden, weil jeder Tabelleneintrag (Adresse des Programmzweigs) ein Wort breit ist. Damit wird aus einem Index von 0, 1, 2, 3, 4 ein Offset von 0, 2, 4, 6, 8.

Abgerufen von „https://www.mikrocontroller.net/index.php?title=AVR-Tutorial:_Mehrfachverzweigung&oldid=105627“