AVR-Tutorial: Arithmetik8
Eine der Hauptaufgaben eines Mikrokontrollers bzw. eines Computers allgemein, ist es, irgendwelche Berechnungen anzustellen. Der Löwenanteil an den meisten Berechnungen entfällt dabei auf einfache Additionen bzw. Subtraktionen. Multiplikationen bzw. Divisionen kommen schon seltener vor, bzw. können oft durch entsprechende Additionen bzw. Subtraktionen ersetzt werden. Weitergehende mathematische Konstrukte werden zwar auch ab und an benötigt, können aber in der Assemblerprogrammierung durch geschickte Umformungen oft vermieden werden.
Hardwareunterstützung
Praktisch alle Mikroprozessoren unterstützen Addition und Subtraktion direkt in Hardware, das heißt: Sie haben eigene Befehle dafür. Einige bringen auch Unterstützung für eine Hardwaremultiplikation mit (so zum Beispiel der ATmega8), während Division in Hardware schon seltener zu finden ist.
8 Bit versus 16 Bit
In diesem Abschnitt des Tutorials wird gezielt auf 8-Bit-Arithmetik eingegangen, um zunächst die Grundlagen des Rechnens mit einem µC zu zeigen. Die Erweiterung von 8-Bit- auf 16-Bit-Arithmetik ist in einigen Fällen wie Addition und Subtraktion trivial, kann sich aber bei Multiplikation und Division in einem beträchtlichen Codezuwachs niederschlagen.
Der im Tutorial verwendete ATmega8 besitzt eine sogenannte 8-Bit-Architektur. Das heißt, dass seine Rechenregister (mit Ausnahmen) nur 8 Bit breit sind und sich daher eine 8-Bit-Arithmetik als die natürliche Form der Rechnerei auf diesem Prozessor anbietet. Berechnungen, die mehr als 8 Bit erfordern, müssen dann durch Kombinationen von Rechenvorgängen realisiert werden. Eine Analogie wäre z. B. das Rechnen, wie wir alle es in der Grundschule gelernt haben. Auch wenn wir in der Grundschule (in den Anfängen) nur die Additionen mit Zahlen kleiner als 10 auswendig gelernt haben, so können wir dennoch durch die Kombination von mehreren derartigen Additionen beliebig große Zahlen addieren. Das gleiche gilt für Multiplikationen. In der Grundschule musste wohl jeder von uns das „Kleine Einmaleins“ auswendig lernen, um Multiplikationen im Zahlenraum bis 100 quasi „in Hardware“ zu berechnen. Und doch können wir durch Kombinationen solcher Einfachmultiplikationen und zusätzlichen Additionen in beliebig große Zahlenräume vorstoßen.
Die Einschränkung auf 8 Bit ist also keineswegs eine Einschränkung in dem Sinne, dass es eine prinzipielle Obergrenze für Berechnungen gäbe. Sie bedeutet lediglich eine obere Grenze dafür, bis zu welchen Zahlen in einem Rutsch gerechnet werden kann. Alles, was darüber hinausgeht, muss dann mittels Kombinationen von Berechnungen gemacht werden.
8-Bit-Arithmetik ohne Berücksichtigung eines Vorzeichens
Die Bits des Registers besitzen dabei eine Wertigkeit, die sich aus der Stelle des Bits im Byte ergibt. Dies ist völlig analog zu dem uns vertrauten Dezimalsystem. Auch dort besitzt eine Ziffer in einer Zahl eine bestimmte Wertigkeit, je nachdem, an welcher Position diese Ziffer in der Zahl auftaucht. So hat z. B. die Ziffer 1 in der Zahl 12 die Wertigkeit „zehn“, während sie in der Zahl 134 die Wertigkeit „hundert“ besitzt. Und so wie im Dezimalsystem die Wertigkeit einer Stelle immer das Zehnfache der Wertigkeit der Stelle unmittelbar rechts von ihr ist, so ist im Binärsystem die Wertigkeit einer Stelle immer das 2-fache der Stelle rechts von ihr.
Die Zahl 4632 im Dezimalsystem kann also so aufgefasst werden:
4632 = 4 * 1000 ( 1000 = 10 hoch 3 )
+ 6 * 100 ( 100 = 10 hoch 2 )
+ 3 * 10 ( 10 = 10 hoch 1 )
+ 2 * 1 ( 1 = 10 hoch 0 )
Die Umwandlung vom Binär- in das Dezimalystem
Völlig analog ergibt sich daher folgendes für z. B. die 8-Bit-Binärzahl 0b10011011 (um Binärzahlen von Dezimalzahlen zu unterscheiden, wird ein 0b vorangestellt):
0b10011011 = 1 * 128 ( 128 = 2 hoch 7 )
+ 0 * 64 ( 64 = 2 hoch 6 )
+ 0 * 32 ( 32 = 2 hoch 5 )
+ 1 * 16 ( 16 = 2 hoch 4 )
+ 1 * 8 ( 8 = 2 hoch 3 )
+ 0 * 4 ( 4 = 2 hoch 2 )
+ 1 * 2 ( 2 = 2 hoch 1 )
+ 1 * 1 ( 1 = 2 hoch 0 )
Ausgerechnet (um die entsprechende Dezimalzahl zu erhalten) ergibt das
128 + 16 + 8 + 2 + 1 = 155. Die Binärzahl 0b10011011 entspricht also der Dezimalzahl 155. Es ist wichtig, sich klar zu machen, dass es zwischen Binär- und Dezimalzahlen keinen grundsätzlichen Unterschied gibt. Beides sind nur verschiedene Schreibweisen für das Gleiche: Eine Zahl. Während wir Menschen an das Dezimalsystem gewöhnt sind, ist das Binärsystem für einen Computer geeigneter, da es nur aus den zwei Ziffern 0 und 1 besteht, welche sich leicht in einem Computer darstellen lassen (Spannung, keine Spannung).
Welches ist nun die größte Zahl, die mit 8 Bit dargestellt werden kann? Dabei handelt es sich offensichtlich um die Zahl 0b11111111. In Dezimalschreibweise wäre das die Zahl
0b11111111 = 1 * 128
+ 1 * 64
+ 1 * 32
+ 1 * 16
+ 1 * 8
+ 1 * 4
+ 1 * 2
+ 1 * 1
oder ausgerechnet: 255.
Wird also mit 8 Bit Arithmetik betrieben, wobei alle 8 Bit als signifikante Ziffern benutzt werden (also kein Vorzeichenbit, dazu später mehr), so kann damit im Zahlenraum 0 bis 255 gerechnet werden.
Binär Dezimal Binär Dezimal
0b00000000 0 0b10000000 128
0b00000001 1 0b10000001 129
0b00000010 2 0b10000010 130
0b00000011 3 0b10000011 131
0b00000100 4 0b10000100 132
0b00000101 5 0b10000101 133
... ...
0b01111100 124 0b11111100 252
0b01111101 125 0b11111101 253
0b01111110 126 0b11111110 254
0b01111111 127 0b11111111 255
Die Umwandlung vom Dezimal- in das Binärsystem
Aus dem vorhergehenden ergibt sich völlig zwanglos die Vorschrift, wie Binärzahlen ins Dezimalsystem umgewandelt werden können (nicht vergessen: Die Zahl selber wird ja gar nicht verändert. Binär- und Dezimalsystem sind ja nur verschiedene Schreibweisen): Durch Anwendung der Vorschrift, wie denn eigentlich ein Stellenwertsystem aufgebaut ist. Aber wie macht man den umgekehrten Schritt, die Wandlung vom Dezimal- ins Binärsystem. Der Weg führt über die Umkehrung des vorhergehenden Prinzips: fortgesetzte Division durch 2.
Es sei die Zahl 92 ins Binärsystem zu wandeln.
92 / 2 = 46 Rest 0
46 / 2 = 23 Rest 0
23 / 2 = 11 Rest 1
11 / 2 = 5 Rest 1
5 / 2 = 2 Rest 1
2 / 2 = 1 Rest 0
1 / 2 = 0 Rest 1
Die Division wird solange durchgeführt, bis sich ein Divisionsergebnis von 0 ergibt. Die Reste, von unten nach oben gelesen, ergeben dann die Binärzahl. Die zu 92 gehörende Binärzahl lautet also 1011100. Es wird noch eine führende 0 ergänzt, um sie auf die standardmäßigen 8 Bit zu bringen: 0b01011100.
8-Bit-Arithmetik mit Berücksichtigung eines Vorzeichens
Soll mit Vorzeichen (also positiven und negativen Zahlen) gerechnet werden, so erhebt sich die Frage: Wie werden eigentlich positive bzw. negative Zahlen dargestellt? Alles was wir haben sind ja 8 Bit in einem Byte.
Problem der Kodierung des Vorzeichens
Die Lösung des Problems besteht darin, dass ein Bit zur Anzeige des Vorzeichens benutzt wird. Im Regelfall wird dazu das am weitesten links stehende Bit benutzt. Von den verschiedenen Möglichkeiten, die sich hiermit bieten, wird in der Praxis fast ausschließlich mit dem sogenannten 2er-Komplement gearbeitet, da es Vorteile bei der Addition bzw. Subtraktion von Zahlen bringt. In diesem Fall muß nämlich das Vorzeichen einer Zahl überhaupt nicht berücksichtigt werden. Durch die Art und Weise der Bildung von negativen Zahlen kommt am Ende das Ergebnis mit dem korrekten Vorzeichen heraus.
2er-Komplement
Das 2er-Komplement verwendet das höchstwertige Bit eines Byte, das sog. MSB (= Most Significant Bit) zur Anzeige des Vorzeichens. Ist dieses Bit 0, so ist die Zahl positiv. Ist es 1, so handelt es sich um eine negative Zahl. Die 8-Bit-Kombination 0b10010011 stellt also eine negative Zahl dar, wenn und nur wenn diese Bitkombination überhaupt als vorzeichenbehaftete Zahl aufgefasst werden soll. Anhand der Bitkombination alleine ist es also nicht möglich, eine definitive Aussage zu treffen, ob es sich um eine vorzeichenbehaftete Zahl handelt oder nicht. Erst wenn durch den Zusammenhang klar ist, dass man es mit vorzeichenbehafteten Zahlen zu tun hat, bekommt das MSB die Sonderbedeutung des Vorzeichens.
Um bei einer Zahl das Vorzeichen zu wechseln, geht man wie folgt vor:
- Zunächst wird das 1er-Komplement gebildet, indem alle Bits umgekehrt werden: aus 0 wird 1 und aus 1 wird 0.
- Danach wird aus diesem Zwischenergebnis das 2er-Komplement gebildet, indem noch 1 addiert wird.
Diese Vorschrift kann immer dann benutzt werden, wenn das Vorzeichen einer Zahl gewechselt werden soll. Er macht aus positiven Zahlen negative und aus negativen Zahlen positive.
Beispiel: Es soll die Binärdarstellung für −92 gebildet werden. Dazu benötigt man zunächst die Binärdarstellung für +92, welche 0b01011100 lautet. Diese wird jetzt nach der Vorschrift für 2er-Komplemente negiert und damit negativ gemacht.
0b01011100 Ausgangszahl 0b10100011 1er-Komplement, alle Bits umgekehrt 0b10100100 noch 1 addiert
Die Binärdarstellung für −92 lautet also 0b10100100. Das gesetzte MSB weist diese Binärzahl auch tatsächlich als negative Zahl aus.
Beispiel: Gegeben sei die Binärzahl 0b00111000, welche als vorzeichenbehaftete Zahl anzusehen ist. Welcher Dezimalzahl entspricht diese Binärzahl?
Da das MSB nicht gesetzt ist, handelt es sich um eine positive Zahl und die Umrechnung kann wie im Fall der vorzeichenlosen 8-Bit-Zahlen erfolgen. Das Ergebnis lautet also +56 (= 0 * 128 + 0 * 64 + 1 * 32 + 1 * 16 + 1 * 8 + 0 * 4 + 0 * 2 + 0 * 1).
Beispiel: Gegeben sei die Binärzahl 0b10011001, welche als vorzeichenbehaftete Zahl anzusehen ist. Welcher Dezimalzahl entspricht diese Binärzahl?
Da das MSB gesetzt ist, handelt es sich um eine negative Zahl. Daher wird diese Zahl zunächst negiert, um dadurch eine positive Zahl zu erhalten.
0b10011001 Originalzahl 0b01100110 1er-Komplement, alle Bits umgekehrt 0b01100111 2er-Komplement, noch 1 addiert
Die zu 0b10011001 gehörende positive Binärzahl lautet also 0b01100111. Da es sich um eine positive Zahl handelt, kann sie wiederum ganz normal, wie vorzeichenlose Zahlen, in eine Dezimalzahl umgerechnet werden. Das Ergebnis lautet 103 (= 0 * 128 + 1 * 64 + 1 * 32 + 0 * 16 + 0 * 8 + 1 * 4 + 1 * 2 + 1 * 1). Da aber von einer negativen Zahl ausgegangen wurde, ist 0b10011001 die binäre Darstellung der Dezimalzahl −103.
Beispiel: Gegeben sei dieselbe Binärzahl 0b10011001. Aber diesmal sei sie als vorzeichenlose Zahl aufzufassen. Welcher Dezimalzahl entspricht diese Binärzahl?
Da die Binärzahl als vorzeichenlose Zahl aufzufassen ist, hat das MSB keine spezielle Bedeutung. Die Umrechnung erfolgt also ganz normal: 0b10011001 = 1 * 128 + 0 * 64 + 0 * 32 + 1 * 16 + 1 * 8 + 0 * 4 + 0 * 2 + 1 * 1 = 153.
Beispiel: Wie lautet die Binärzahl zu −74?
Da es sich hier offensichtlich um eine vorzeichenbehaftete Zahl handelt, müssen die Regeln des 2er-Komplements angewendet werden. Zunächst ist also die Binärrepräsentierung von +74 zu bestimmen, welche dann durch Anwendung des 2er-Komplements negiert wird.
74 / 2 = 37 Rest 0 37 / 2 = 18 Rest 1 18 / 2 = 9 Rest 0 9 / 2 = 4 Rest 1 4 / 2 = 2 Rest 0 2 / 2 = 1 Rest 0 1 / 2 = 0 Rest 1
Die Binärdarstellung für +74 lautet daher 0b01001010.
0b01001010 +74 0b10110101 1er-Komplement, alle Bits umgekehrt 0b10110110 noch 1 addiert
Die Binärdarstellung für −74 lautet somit 0b10110110.
Arithmetikflags
Im Statusregister des Prozessors gibt es eine Reihe von Flags, die durch Rechenergebnisse beeinflusst werden, bzw. in Berechnungen einfließen können.
Carry
Das Carry-Flag C zeigt an, ob bei einer Berechnung mit vorzeichenlosen Zahlen ein Über- oder Unterlauf erfolgt ist, d. h. das Ergebnis der Berechnung liegt außerhalb des darstellbaren Bereiches 0…255.
Wie das?
Angenommen, es müssen zwei 8-Bit-Zahlen addiert werden.
10100011 + 11110011 --------- 110010110
Das Ergebnis der Addition umfasst neun Bit und liegt außerhalb des in einem Register darstellbaren Zahlenbereiches 0…255; die Addition ist übergelaufen.
Werden dieselben Zahlen subtrahiert,
10100011 − 11110011 --------- 10110000
verbleibt an der höchstwertigen Stelle ein „geborgtes“ Bit, welches durch das Carry angezeigt wird.
Signed- und Overflowflag
Wird mit vorzeichenbehafteten Zahlen gerechnet, so wird das Verlassen des 8-Bit-Zahlenbereiches −128…+127 durch die Flags S und V angezeigt. Der Prozessor selbst unterscheidet nicht zwischen vorzeichenlosen und -behafteten Zahlen. Der Programmierer legt durch Wahl der ausgewerteten Flags (C bei vorzeichenlosen bzw. S/V bei vorzeichenbehafteten) die Interpretation der Zahlen fest.
Weitere Flags
Das Zero-Flag Z wird gesetzt, wenn das 8-Bit-Ergebnis der Berechnung null ist. Dies kann bei der Addition auch durch Überlauf geschehen, was durch ein zusätzliches Carryflag angezeigt wird.
Das Negative-Flag N wird gesetzt, wenn im Ergebnis das höchstwertige Bit gesetzt ist. Bei vorzeichenbehafteter Arithmetik ist dies als negative Zahl zu interpretieren, sofern nicht durch das V-Flag ein Verlassen des Zahlbereichs angezeigt wird.
Das Half-Carry-Flag H zeigt, analog zum Carry-Flag, einen Übertrag zwischen Bit 3 und 4 an. Dies kann in speziellen Anwendungen (z. B. zwei simultane Vier-Bit-Berechnungen mit einem Befehl) nützlich sein.
Übersicht über die arithmetischen Flags
Ergebnis des Befehls ADD Rd, Rr
Rr| 0 | 1 | 64 | 127 | 128 | 129 | 192 | 255 Rd |( +0)|( +1)|( +64)|(+127)|(−128)|(−127)|( −64)|( −1) ----------+------+------+------+------+------+------+------+------ 0 ( +0)| Z | | | |S N |S N |S N |S N 1 ( +1)| | | | VN |S N |S N |S N | CZ 64 ( +64)| | | VN | VN |S N |S N | CZ | C 127 (+127)| | VN | VN | VN |S N | CZ | C | C 128 (−128)|S N |S N |S N |S N |SV CZ |SV C |SV C |SV C 129 (−127)|S N |S N |S N | CZ |SV C |SV C |SV C |S NC 192 ( −64)|S N |S N | CZ | C |SV C |SV C |S NC |S NC 255 ( −1)|S N | CZ | C | C |SV C |S NC |S NC |S NC
Man erkennt: C=1 genau dann, wenn die Addition Rd + Rr mit vorzeichenlosen Zahlen überläuft. V=1 genau dann, wenn die Addition mit vorzeichenbehafteten Zahlen überläuft.
Ergebnis des Befehls SUB Rd, Rr bzw. CP Rd, Rr
Rr| 0 | 63 | 64 | 127 | 128 | 191 | 192 | 255 Rd |( +0)|( +63)|( +64)|(+127)|(−128)|( −65)|( −64)|( −1) ----------+------+------+------+------+------+------+------+------ 0 ( +0)| Z |S NC |S NC |S NC | VNC | C | C | C 63 ( +63)| | Z |S NC |S NC | VNC | VNC | C | C 64 ( +64)| | | Z |S NC | VNC | VNC | VNC | C 127 (+127)| | | | Z | VNC | VNC | VNC | VNC 128 (−128)|S N |SV |SV |SV | Z |S NC |S NC |S NC 191 ( −65)|S N |S N |SV |SV | | Z |S NC |S NC 192 ( −64)|S N |S N |S N |SV | | | Z |S NC 255 ( −1)|S N |S N |S N |S N | | | | Z
Man erkennt: C=1 genau dann, wenn die Subtraktion Rd − Rr mit vorzeichenlosen Zahlen unterläuft; äquivalent dazu ist Rd < Rr (vorzeichenlos). S=1 genau dann, wenn die Subtraktion mit vorzeichenbehafteten Zahlen unterläuft bzw. Rd > Rr (vorzeichenbehaftet).
Inkrementieren / Dekrementieren
Erstaunlich viele Operationen in einem Computer-Programm entfallen auf die Operationen „zu einer Zahl 1 addieren“ bzw. „von einer Zahl 1 subtrahieren“. Dementsprechend enthalten die meisten Mikroprozessoren die Operationen Inkrementieren (um 1 erhöhen) bzw. Dekrementieren (um 1 verringern) als eigenständigen Assemblerbefehl. So auch der ATmega8.
AVR-Befehle
inc r16
bzw.
dec r16
Die Operation ist einfach zu verstehen. Das jeweils angegebene Register (hier wieder am Register r16 gezeigt) wird um 1 erhöht bzw. um 1 verringert. Dabei wird die Zahl im Register als vorzeichenlose Zahl angesehen. Enthält das Register bereits die größtmögliche Zahl (0b11111111 oder dezimal 255), so erzeugt ein weiteres Inkrementieren die kleinstmögliche Zahl (0b00000000 oder dezimal 0) bzw. umgekehrt dekrementiert 0 zu 255. Es gilt jedoch zu beachten, dass bei diesen Befehlen dass Carry-Bit nicht beeinflusst wird!
Addition
Auf einem ATmega8 gibt es nur eine Möglichkeit, um eine Addition durchzuführen: Die beiden zu addierenden Zahlen müssen in zwei Registern stehen.
AVR-Befehle
add r16, r17 ; Addition der Register r16 und r17. Das Ergebnis wird
; im Register r16 abgelegt.
adc r16, r17 ; Addition der Register r16 und r17, wobei das Carry-Bit
; noch zusätzlich mit addiert wird.
Bei der Addition zweier Register wird ein möglicher Überlauf in allen Fällen im Carry-Bit abgelegt. Daraus erklärt sich dann auch das Vorhandensein eines Additionsbefehls, der das Carry-Bit noch zusätzlich mitaddiert: Man benötigt ihn zum Aufbau einer Addition, die mehr als 8 Bit umfasst. Die niedrigstwertigen Bytes werden mit einem add addiert und alle weiteren höherwertigen Bytes werden, vom Niedrigstwertigen zum Höchstwertigen, mittels adc addiert. Dadurch werden eventuelle Überträge automatisch berücksichtigt.
Subtraktion
Subtraktionen können auf einem AVR in zwei unterschiedlichen Arten ausgeführt werden. Entweder es werden zwei Register voneinander subtrahiert oder es wird von einem Register eine konstante Zahl abgezogen. Beide Varianten gibt es wiederum in den Ausführungen mit und ohne Berücksichtigung des Carry-Flags.
AVR-Befehle
sub r16, r17 ; Subtraktion des Registers r17 von r16. Das Ergebnis wird
; im Register r16 abgelegt.
sbc r16, r17 ; Subtraktion des Registers r17 von r16, wobei das Carry-Bit
; noch zusätzlich mit subtrahiert wird. Das Ergebnis wird
; im Register r16 abgelegt.
subi r16, zahl ; Die Zahl (als Konstante) wird vom Register r16 subtrahiert.
; Das Ergebnis wird im Register r16 abgelegt.
sbci r16, zahl ; Subtraktion einer konstanten Zahl vom Register r16, wobei
; zusätzlich noch das Carry-Bit mit subtrahiert wird.
; Das Ergebnis wird im Register r16 abgelegt.
Multiplikation
Multiplikation kann auf einem AVR je nach konkretem Typ auf zwei unterschiedliche Arten ausgeführt werden. Während die größeren ATmega-Prozessoren über einen Hardwaremultiplizierer verfügen, ist dieser bei den kleineren ATtiny-Prozessoren nicht vorhanden. Hier muß die Multiplikation quasi zu Fuß durch entsprechende Addition von Teilresultaten erfolgen.
Hardwaremultiplikation
Vorzeichenbehaftete und vorzeichenlose Zahlen werden unterschiedlich multipliziert. Denn im Falle eines Vorzeichens darf ein gesetztes 7. Bit natürlich nicht in die eigentliche Berechnung mit einbezogen werden. Statt dessen steuert dieses Bit (eigentlich die beiden MSB der beiden beteiligten Zahlen) das Vorzeichen des Ergebnisses. Die Hardwaremultiplikation ist auch dahingehend eingeschränkt, dass das Ergebnis einer Multiplikation immer in den Registerpärchen r0 und r1 zu finden ist. Dabei steht das LowByte (also die unteren 8 Bit) des Ergebnisses in r0 und das HighByte in r1.
AVR-Befehl
mul r16, r17 ; Multipliziert r16 mit r17. Beide Registerinhalte werden
; als vorzeichenlose Zahlen aufgefasst.
; Das Ergebnis der Multiplikation ist in den Registern r0 und r1
; zu finden.
muls r16, r17 ; Multipliziert r16 mit r17. Beide Registerinhalte werden
; als vorzeichenbehaftete Zahlen aufgefasst.
; Das Ergebnis der Multiplikation ist in den Registern r0 und r1
; zu finden und stellt ebenfalls eine vorzeichenbehaftete
; Zahl dar.
mulsu r16, r17 ; Multipliziert r16 mit r17, wobei r16 als vorzeichenbehaftete
; Zahl aufgefasst wird und r17 als vorzeichenlose Zahl.
; Das Ergebnis der Multiplikation ist in den Registern r0 und r1
; zu finden und stellt eine vorzeichenbehaftete Zahl dar.
Multiplikation in Software
Multiplikation in Software ist nicht weiter schwierig. Man erinnere sich daran, wie Multiplikationen in der Grundschule gelehrt wurden: Zunächst stand da das kleine Einmaleins, welches auswendig gelernt wurde. Mit diesen Kenntnissen konnten dann auch größere Multiplikationen angegangen werden, indem der Multiplikand mit jeweils einer Stelle des Multiplikators multipliziert wurde und die Zwischenergebnisse, geeignet verschoben, addiert wurden. Die Verschiebung um eine Stelle entspricht dabei einer Multiplikation mit 10.
Beispiel: Zu multiplizieren sei 3456 · 7812.
3456 · 7812
---------------
24192 <-+|||
+ 27648 <--+||
+ 3456 <---+|
+ 6912 <----+
--------
26998272
Im Binärsystem funktioniert Multiplikation völlig analog. Nur ist hier das kleine Einmaleins sehr viel einfacher! Es gibt nur 4 Multiplikationen (anstatt 100 im Dezimalsystem):
0 · 0 = 0 0 · 1 = 0 1 · 0 = 0 1 · 1 = 1
Es gibt lediglich einen kleinen Unterschied gegenüber dem Dezimalsystem: Anstatt zunächst alle Zwischenergebnisse aufzulisten und erst danach die Summe zu bestimmen, werden wir ein neues Zwischenergebnis gleich in die Summe einrechnen. Dies deshalb, da Additionen von mehreren Zahlen im Binärsystem im Kopf sehr leicht zu Flüchtigkeitsfehlern führen (durch die vielen 0-en und 1-en). Weiters wird eine einfache Tatsache benutzt: 1 mal eine Zahl ergibt wieder die Zahl, während 0 mal eine Zahl immer 0 ergibt. Dadurch braucht man im Grunde bei einer Multiplikation überhaupt nicht zu multiplizieren, sondern eigentlich nur die Entscheidung treffen: Muss die Zahl geeignet verschoben addiert werden oder nicht?
0b00100011 · 0b10001001
--------------------------------
00100011 <--+|||||||
+ 00000000 <---+||||||
--------- ||||||
001000110 ||||||
+ 00000000 <----+|||||
---------- |||||
0010001100 |||||
+ 00000000 <-----+||||
----------- ||||
00100011000 ||||
+ 00100011 <------+|||
------------ |||
001001010011 |||
+ 00000000 <-------+||
------------- ||
0010010100110 ||
+ 00000000 <--------+|
-------------- |
00100101001100 |
+ 00100011 <---------+
---------------
001001010111011
Man sieht auch, wie bei der Multiplikation zweier 8-Bit-Zahlen sehr schnell ein 16-Bit-Ergebnis entsteht. Dies ist auch der Grund, warum die Hardwaremultiplikation immer zwei Register zur Aufnahme des Ergebnisses benötigt.
Ein Assemblercode, der diese Strategie im Wesentlichen verwirklicht, sieht z. B. so aus. Dieser Code wurde nicht auf optimale Laufzeit getrimmt, sondern es soll im Wesentlichen eine 1:1-Umsetzung des oben gezeigten Schemas sein. Einige der verwendeten Befehle wurden im Rahmen dieses Tutorials an dieser Stelle noch nicht besprochen. Speziell die Schiebe- (lsl) und Rotier- (rol) Befehle sollten in der AVR-Befehlsübersicht genau studiert werden, um ihr Zusammenspiel mit dem Carry-Flag zu verstehen. Nur soviel als Hinweis: Das Carry-Flag dient in der lsl/rol-Sequenz als eine Art Zwischenspeicher, um das höchstwertige Bit aus dem Register r0 beim Verschieben in das Register r1 verschieben zu können. Der lsl verschiebt alle Bits des Registers um 1 Stelle nach links, wobei das vorhergehende MSB ins Carry-Bit wandert und rechts ein 0-Bit nachrückt. Der rol verschiebt ebenfalls alle Stellen eines Registers um 1 Stelle nach links. Diesmal wird aber rechts nicht mit einem 0-Bit aufgefüllt, sondern an dieser Stelle wird der momentane Inhalt des Carry-Bits eingesetzt.
ldi r16, 0b00100011 ; Multiplikator
ldi r17, 0b10001001 ; Multiplikand
; Berechne r16 · r17
ldi r18, 8 ; 8-mal verschieben und gegebenenfalls addieren
clr r19 ; 0 wird für die 16-Bit-Addition benötigt
clr r0 ; Ergebnis Low Byte auf 0 setzen
clr r1 ; Ergebnis High Byte auf 0 setzen
mult:
lsl r0 ; r1:r0 einmal nach links verschieben
rol r1
lsl r17 ; Das MSB von r17 ins Carry schieben
brcc noadd ; Ist dieses MSB (jetzt im Carry) eine 1?
add r0,r16 ; Wenn ja, dann r16 zum Ergebnis addieren
adc r1,r19
noadd:
dec r18 ; Wurden alle 8 Bit von r17 abgearbeitet?
brne mult ; Wenn nicht, dann ein erneuter Verschiebe/Addier-Zyklus
; r0 enthält an dieser Stelle den Wert 0b10111011
; r1 enthält 0b00010010
; Gemeinsam bilden r1 und r0 also die Zahl
; 0b0001001010111011
Division
Anders als bei der Multiplikation gibt es auch auf einem ATmega-Prozessor keine hardwaremäßige Divisionseinheit. Divisionen müssen also in jedem Fall mit einer speziellen Routine, die im wesentlichen auf Subtraktionen beruht, erledigt werden.
Division in Software
Um die Vorgangsweise bei der binären Division zu verstehen, wollen wir wieder zunächst anhand der gewohnten dezimalen Division untersuchen, wie sowas abläuft.
Angenommen, es soll dividiert werden: 938 / 4 ( 938 ist der Dividend, 4 ist der Divisor)
Wie haben Sie es in der Grundschule gelernt? Wahrscheinlich so wie der Autor auch:
938 : 4 = 234
---
−8
----
1
13
−12
---
1
18
−16
--
2 Rest
Der Vorgang war: Man nimmt die erste Stelle des Dividenden (9) und ruft seine gespeicherte Einmaleins-Tabelle ab, um festzustellen, wie oft der Divisor in dieser Stelle enthalten ist. In diesem konkreten Fall ist die erste Stelle 9 und der Divisor 4. 4 ist in 9 zweimal enthalten. Also ist 2 die erste Ziffer des Ergebnisses. 2 mal 4 ergibt aber 8 und diese 8 werden von den 9 abgezogen, übrig bleibt 1. Aus dem Dividenden wird die nächste Ziffer (3) heruntergezogen und man erhält mit der 1 aus dem vorhergehenden Schritt 13. Wieder dasselbe Spiel: Wie oft ist 4 in 13 enthalten? 3-mal (3 ist die nächste Ziffer des Ergebnisses) und 3 · 4 ergibt 12. Diese 12 von den 13 abgezogen macht 1. Zu dieser 1 gesellt sich wieder die nächste Ziffer des Dividenden, 8, um so 18 zu bilden. Wie oft ist 4 in 18 enthalten? 4 mal (4 ist die nächste Ziffer des Ergebnisses), denn 4 mal 4 macht 16, und das von den 18 abgezogen ergibt 2. Da es keine nächste Ziffer im Dividenden mehr gibt, lautet also das Resultat: 938 : 4 ergibt 234 und es bleibt der Rest 2.
Die binäre Division funktioniert dazu völlig analog. Es gibt nur einen kleinen Unterschied, der einem sogar das Leben leichter macht. Es geht um den Schritt: Wie oft ist x in y enthalten? Dieser Schritt ist in der binären Division besonders einfach, da das Ergebnis dieser Fragestellung nur 0 oder 1 sein kann. Das bedeutet aber auch: Entweder ist der Divisior in der zu untersuchenden Zahl enthalten, oder er ist es nicht. Das kann aber ganz leicht entschieden werden: Ist die Zahl größer oder gleich dem Divisor, dann ist der Divisor enthalten und zum Ergebnis kann eine 1 hinzugefügt werden. Ist die Zahl kleiner als der Divisor, dann ist der Divisor nicht enthalten und die nächste Ziffer des Ergebnisses ist eine 0.
Beispiel: Es soll die Division 0b01101100 : 0b00001001 ausgeführt werden.
Es wird wieder mit der ersten Stelle begonnen und die oben ausgeführte Vorschrift angewandt.
0b01101101 : 0b00001001 = 0b00001100
^^^^^^^^
||||||||
0 ---------+||||||| 1001 ist in 0 0-mal enthalten
−0 |||||||
-- |||||||
0 |||||||
01 ----------+|||||| 1001 ist in 1 0-mal enthalten
− 0 ||||||
-- ||||||
01 ||||||
011 -----------+||||| 1001 ist in 11 0-mal enthalten
− 0 |||||
--- |||||
011 |||||
0110 ------------+|||| 1001 ist in 110 0-mal enthalten
− 0 ||||
---- ||||
0110 ||||
01101 -------------+||| 1001 ist in 1101 1-mal enthalten
− 1001 |||
----- |||
0100 |||
01001 --------------+|| 1001 ist in 1001 1-mal enthalten
− 1001 ||
----- ||
00000 ||
000000 ---------------+| 1001 ist in 0 0-mal enthalten
− 0 |
------ |
0000001 ----------------+ 1001 ist in 1 0-mal enthalten
− 0
-------
1 Rest
Die Division liefert also das Ergebnis 0b00001100, wobei ein Rest von 1 bleibt. Der Dividend 0b01101101 entspricht der Dezimalzahl 109, der Divisor 0b00001001 der Dezimalzahl 9. Und wie man sich mit einem Taschenrechner leicht überzeugen kann, ergibt die Division von 109 durch 9 einen Wert von 12, wobei 1 Rest bleibt. Die Binärzahl für 12 lautet 0b00001100, das Ergebnis stimmt also.
ldi r16, 109 ; Dividend
ldi r17, 9 ; Divisor
; Division r16 : r17
ldi r18, 8 ; 8-Bit-Division
clr r19 ; Register für die Zwischenergebnisse / Rest
clr r20 ; Ergebnis
divloop:
lsl r16 ; Zwischenergebnis mal 2 nehmen und das
rol r19 ; nächste Bit des Dividenden anhängen
lsl r20 ; Das Ergebnis auf jeden Fall mal 2 nehmen,
; das hängt effektiv eine 0 an das Ergebnis an.
; Sollte das nächste Ergebnis-Bit 1 sein, dann wird
; diese 0 in Folge durch eine 1 ausgetauscht.
cp r19, r17 ; Ist der Divisor größer?
brlo div_zero ; Wenn nein, dann bleibt die 0.
sbr r20, 1 ; Wenn ja, dann jetzt die 0 durch eine 1 austauschen ...
sub r19, r17 ; ... und den Divisor abziehen.
div_zero:
dec r18 ; Das Ganze 8-mal wiederholen.
brne divloop
; In r20 steht das Ergebnis der Division.
; In r19 steht der bei der Division entstehende Rest.
Arithmetik mit mehr als 8 Bit
Es gibt eine Sammlung von Algorithmen zur AVR-Arithmetik mit mehr als 8 Bit, deren Grundprinzipien im wesentlichen identisch zu den in diesem Teil ausgeführten Prinzipien sind.
Literatur
- Application Note AVR201: Using the 8-bit AVR Hardware Multiplier