Pfad: Home => AVR-Überblick => Programmiertechniken => Durch 10 teilen    (This page in English: Flag EN) Logo

Programmiertechnik für Anfänger in AVR Assemblersprache

Dividieren durch 10 in Assemblersprache

Das kommt sehr oft vor: eine Binärzahl muss durch 10 dividiert werden. Teilen durch Acht ist einfach: drei mal rechts schieben, fertig. Aber durch 10?

Nun: es gibt zwei Methoden:
  1. Man zieht immerzu 10 ab und zählt mit, bis ein Unterlauf auftritt. Das ist bei kleinen Zahlen mit 8 Bit Breite noch machbar, aber führt bei großen Zahlen (16 oder mehr Bits) zu einem langwierigen Unterfangen.
  2. Der zweiten Methode ist es weitgehend egal, wie groß die Zahl ist, 8 oder 16 Bit unterscheiden sich nur mit dem Faktor 2 und bei der gleichen Anzahl Bits dauert es immer gleich lang. Dafür ist diese Methode hier exklusiv und vom Scheff der Webseite selber gemacht.

Teilen durch 10 mit Zählschleife

Dazu braucht es bei 8-Bit-Zahlen ein einziges zusätzliches Register. Das wird mit ldi rZaehl,0xFF oder mit ser rZaehl oder auch, wenn es R0 bis R15 ist, mit clr rZaehl und dec rZaehl auf Minus 1 gesetzt. In einer Schleife wird dieses mit inc rZaehl um Eins nach oben gezählt. Dann wird die Zahl mit subi rZahl,10 um zehne verringert. Ist danach die Carry-Flagge nicht gesetzt, wird diese Schleife so oft wiederholt, bis das der Fall ist. Das Ergebnis der Division steht dann im Zählregister.

Jeder Durchlauf durch diese Schleife braucht vier Takte, bis auf den letzten: der braucht nur drei Takte. Die Gesamtanzahl an Takten ist daher
nTakte = 4 * Zahl / 10 + 3

Bei 255 sind das 103 Takte.

Bei 16-Bit-Zahlen braucht es einen 16-Bit-Zahlenspeicher und einen 16-Bit-Zähler. Das können im Prinzip beliebige Register sein. Sind es R25:R24 oder XH:XL oder YH:YL oder ZH:ZL, dann kann man das Hochzählen mit ADIW R24,1 und das Abziehen von 10 mit SBIW XL,10) erledigen. Das Abziehen geht aber auch mit subi rZahlL,10 für das LSB und mit sbci rZahlH,0 für das MSB, wenn beide Register ab R16 sind.

Mit ADIW und SBIW dauert die Schleife sechs Takte pro Durchlauf, der letzte fünf. Für das Dividieren von 65.535 durch 10 dauert es
nTakte = 6 * 65535 / 10 + 5 = 39.323 Takte

und liegt daher im Bereich von vielen Millisekunden. Das ist für den Prozessor nicht viel, aber für den Ästheten ein ziemlicher Graus. Und bei 24-Bit-Zahlen sind wir endgültig im Bereich des Unmöglichen angekommen.

Es muss aber noch ganz anders und viel schneller gehen. Und das geht so.

Ebenfalls klassisch: Binäre Division

Register fuer klassische Division Die klassische Division durch 10 arbeitet folgendermaßen. Die Register, die zu dividieren sind (hier 16-Bit) werden durch ein weiteres Register ergänzt, hier rN2. Es beginnt mit dem Laden der beiden Register mit der Zahl und dem Nullsetzen der Zusatzzahl rN2. Dann wird Bit 15 in das Zusatzregister geschoben und alle niedrigeren Bits um eine Position nach links. Von der Zusatzzahl wird 10 subtrahiert. Ist danach die Carry-Flagge gesetzt, wird diese Subtraktion rückgängig gemacht (durch Subtrahieren von -10) und die Carry-Flagge gelöscht, um eine Null in das Ergebnis zu rotieren. War nach dem Subtrahieren von 10 die Carry-Flagge nicht gesetzt, bleibt es beim Abziehen und die Carry-Flagge wird auf Eins gesetzt, um eine Eins in das Ergebnis zu schieben.

Ergebnisregister fuer klassisches Dividieren Nun kommen die zusätzlichen Ergebnisregister rR1:rR0 ins Spiel. Für 16 Bit braucht es deren zwei. Sie werden zu Beginn Null gesetzt und das niedrigste Bit wird Eins (wir werden später sehen, wozu das gut ist).

Das ermittelte Carry-Ergebnis wird nun in diese beiden Register von rechts her eingeschoben. Wenn das in das Carry geschobene höchste Bit eine Null war, dann wird die ganze Prozedur (Linksschieben und -rotieren der Zahl, Abziehen von 10, Linksrotieren des Ergebnisses) einfach weiter wiederholt. Rollt eine Eins heraus, ist das Dividieren zu Ende: die zu Beginn in das niedrigste Bit geschobene Eins zählt einfach die Bits, die schon geteilt wurden.

Das Register rN2 wird dann zum Runden verwendet: ist es größer oder gleich 5, wird das Ergebnis in 16-Bit-Manier um Eins erhöht. Das Ergebnis wird dann in das Registerpaar rN1:rN0 kopiert. Wenn die drei zusätzlichen Register auch noch für andere Zwecke Verwendung finden sollen, müssen diese vorher auf dem Stapel gesichert und nun am Ende wiederhergestellt werden.

Division durch 10 - die klassische Methode Der Quellcode dazu ist hier. Die Ergebnisse für die gezeigten Zahlen zeigen, dass die Rundung korrekt erfolgt. Die Ausführungszeiten bewegen sich zwischen 204 und 218 Taktzyklen. Das ist etwas länger als die erste beschriebene Methode oben, wenn es um 8 Bits geht. Bei 16 Bits und mehr ist diese Methode jedoch bei Weitem überlegen.

Teilen durch 10 nach Schmidt

Und nun nicht etwa das Allerschnellste, sondern eher etwas für den Forschergeist: meine ganz eigene Methode. Trotzdem ganz fix.

Teilt man die Zahl durch Acht, kommt schon eine gute erste Näherung heraus. So ist 100 / 8 = 12 (genauer: 12,5), also schon recht nah am Ergebnis 10. Welche weiteren Teiler (durch 16, durch 32, durch 64, etc.) muss man von der 12 abziehen, um zur 10 zu kommen?

Division durch 10 Man erkennt an dieser Reihe, dass wir schon nach Abziehen von Zahl / 64 bei 10 sind. Da das aber nur für 100 gilt (bei 255 müssten wir auch noch Zahl / 128 abziehen, damit das Ergebnis stimmt).

Interessant ist die Zahlenreihe in Spalte 3 der Tabelle, die angibt, ob die durch die Zweierpotenz geteilte Zahl abgezogen werden muss (1) oder nicht (0). Beginnend mit 16 werden zwei geteilte Zahlen nicht abgezogen (16 und 32), dann die beiden Folgenden (64 und 128) abgezogen und danach immer weiter so in gleicher Weise. Egal, von welcher Zahl man ausgeht, diese Reihe aus 0011 bleibt immer die Gleiche.

Division durch 10 Zum Beweis hier die Reihe mit 55.000. Jetzt müssen statt 15 mal teilen noch acht Teilungen mehr dran, also 23.

Auch hier ergibt sich die gleiche Reihe: zweimal nicht subtrahieren, gefolgt von zweimal Subtrahieren. Ich überlasse es Mathematikern, herauszufinden, warum das so schön regelmäßig ist. Mir reicht es, wenn es funkioniert.

Die Bildung der durch steigende Zweierpotenzen geteilten Zahl braucht bei 8 Bit ein zusätzliches, bei 16 Bit zwei Register. Die Subtraktion benötigt bei 8 Bit zusätzlich zwei, bei 16 Bit vier Register.

Weil das Teilen der Zahl durch die Zweierpotenzen und das Subtrahieren immer die gleichen Instruktionen durchlaufen, ist die Ausführungsdauer auch immer die gleiche, egal welche Zahl gerade beteilt wird.

Ausführungszeiten

Ich habe mit diesem Assemblerprogramm hier alle beiden Ausführungsarten für 8 und 16 Bit ausführbar gemacht und mit dem Simulator avr_sim getestet, wie lange sie bei verschiedenen Zahlen brauchen. Das sind die Ergebnisse:

BitsMethodeZahlTakte
8Fortgesetztes Abziehen10056
255116
Binärdivision10099
255101
Schmidtegal59
16Fortgesetztes Abziehen10.0006.025
65.53539.344
Binärdivision10.000220
65.535220
Schmidtegal144


Bei der Simulation habe ich alle zusätzlichen verwendeten Register auf dem Stapel abgelegt und am Ende wieder hergestellt. Das sorgt für faire Vergleichsbedingungen (Strafzyklen für zusätzliche Register). Wer Register satt übrig hat, braucht das natürlich nicht und kann so noch ein paar Takte sparen.

Korrektes Runden mit Schmidt's Methode

Ein wichtiger Aspekt beim Dividieren durch 10 ist korrektes Runden: wenn der Divisionsrest gleich oder größer ist als 0,5, wird das Ergebnis aufgerundet.

Eine einfache und billige Methode dafür ist es, fünf zu der Zahl hinzu zu addieren. Da dies aber dazu führt, dass Zahlenwerte ab 65.531 und darüber nicht mehr korrekt verarbeitet werden können, muss das Addieren erst dann erfolgen, wenn die Zahl bereits durch acht geteilt ist. Dann droht kein Überlauf mehr. Da die Zahl bereits durch acht geteilt ist, müssen die fünf ebenfalls durch acht geteilt und erst dann addiert werden. Bei acht Bit muss daher mindestens 5 / 8 * 256 = 160 = 0x00A0 hinzu addiert werden. Bei 16 Bit sind es 5 / 8 * 65.536 = 0x0000A000. Experimentell hat sich herausgestellt, dass das Addieren von bis zu 5,9988 korrekt funktioniert. Ein vernünftiger Additionswert, der am meisten Abstand zu den Grenzen ergibt, wäre daher 5,5 oder hexadezimal 0x0000AFFB.

Hier gibt es den Quellcode für diese Methode für 16 Bit. Da die Reihe 0011 immer wieder auftaucht, ist das Dividieren durch 2, 4, 8 und 16 (zwei mal ohne und zwei mal mit Subtraktion) in einer Schleife ausgeführt. Beendet wird die Schleife, wenn nichts mehr zum Abziehen übrig ist. Kleinere Zahlen machen daher weniger Durchläufe (mindestens vier) als große, maximal werden acht Schleifendurchläufe mit 32 Divisionen durch zwei absolviert.

Der Code umfasst nur 54 Instruktionsworte und ist daher sehr kompakt. Dass alle drei untersten Register auf Null abgefragt werden, ist reine Vorsicht, eigentlich reichen dafür die zwei untersten aus. Es kann aber vereinzelt Fälle geben, bei denen es, nach Rundungsansatz, die beiden untersten Register Null sind, sich aber im dritten Register noch Bits befinden. Die Reihenfolge der drei Abfragen richtet sich nach der Häfigkeit.

Noch mehr Runden

Um es ganz genau zu machen, müssten auch Überläufe beim Dividieren der Zahl durch Zwei mit ror rN0 aufgerundet werden. Da das Aufrunden sich bis in das vierte Byte fortsetzen kann, sind entsprechende Rundungsketten zu absolvieren, falls beim INC das Byte Null wird. Dies führt übrigens dazu, dass sich ein leichter Überschuss beim Subtrahieren ergibt. Um das zu korrigieren, wird nicht Fünf sondern Sechs addiert (0xC0 zu Byte 1 der durch acht dividierten Zahl addieren).

Division der 16-Bit-Zahl durch 10 mit korrekter Rundung Den Assembler-Quellcode dafür gibt es hier. Eingang des Quellcodes wird die zu dividierende Zahl als Konstante definiert, das Ergebnis erscheint in dem Registerpaar R17:R16.

Der Code ist im Vergleich zur eingangs verwendeten Variante optimiert. Auch hier werden Schleifen verwendet. Bitte hier beachten, dass die relative Sprungdistanz schon nahezu ausgeschöpft ist, daher können nur noch ganz wenige Worte eingefügt werden, ohne dass die Sprungkonstruktion geändert werden muss.

Die grundlegende Entscheidung, das Durchlaufen des Loops von der Zahlengröße abhängig zu machen, bedingt natürlich auch hier, dass die Ausführungsdauer von der Zahl abhängig wird. Das kann man in der Tabelle sehen: die kürzeste Dauer hat die Null (mit 182 Instruktionszyklen), die längste 65.535. Jeder Schleifendurchlauf frisst ca. 47 Zyklen.

Was man auch aus der Tabelle sieht, ist, dass das Runden auch hier absolut korrekt erfolgt, egal ob die Zahl klein oder groß ist.

Bedingt durch die Optimierung hat der Quellcode nur 90 Worte. Das passt auch in einen sehr kleinen Flash-Speicher noch mit dazu. Bitte beachten, dass benötigte Register hier nicht gesichert und wiederhergestellt werden. Wer das braucht, fügt zu Beginn ein paar PUSH hinzu und am Ende gleich viele POPs (und natürlich den Stapelzeiger).

Bedingt durch die Rundungsoperationen braucht diese Version etwas länger als die Binärdivision und die erste Rundungsvariante. Da ist aber noch viel Optimierungspotenzial.

Fazit:
  1. Sind die Zahlen unter 100 und ausschließlich 8 Bit breit, führt man mit der Methode fortgesetztes Abziehen am besten.
  2. Ab 100 oder mit mehr als 8 Bits ist meine neue Methode jeweils die schnellste, die klassische Binärdivision ist hingegen etwas langwieriger.


Zum Seitenanfang

©2021 by http://www.avr-asm-tutorial.net