AVR-Tutorial: Mehrfachverzweigung
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:
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.