Pfad: Home => AVR-Überblick => Binäre Berechnungen => 64-Bit Binär    (This page in English: Flag EN) Logo
AT90S8515

Binär-Berechnungen mit 64-Bit vorzeichenlosen Ganzzahlen in AVR-Assembler


Brauchst Du manchmal sehr große Ganzzahlen ohne Vorzeichen, so bis zu 18.446.744.073.709.551.615? Diese Seite demonstriert den Umgang mit solchen großen Zahlen in einem 8-Bit-AVR.

  1. Die Struktur von 64-Bit-Zahlen in einem 8-Bit-Controller
  2. Simulieren des Programmablaufs mit avr_sim
  3. Umwandlung von Dezimalzahlen-Zeichenfolgen in Binär
  4. Binäres Addieren von zwei großen Zahlen
  5. Subtrahieren einer großen Zahl von einer anderen großen Zahl
  6. Multiplikation einer großen Zahl mit einer 8-Bit Binärzahl
  7. Auflisten der Dezimalpotenzen in Binär
  8. Umwandlung von großen Zahlen in eine Dezimal-Zeichenfolge
  9. Zählen für lange Zeiten mit 64-bit-Zähler
  10. Schlussfolgerungen

1 Die Struktur von 64-Bit-Zahlen in einem 8-Bit-Controller

Ein 8-Bit-Controller kann nur 8 Bit große Zahlen verarbeiten? Ja und Nein: er kann immer nur acht Bits auf einmal, aber nacheinander kann er beliebig große Zahlen, solange der Speicherraum ausreicht.

16 Bits benötigen zwei Acht-Bit-Register, z B. die Register R0 und R1. In Assembler hat man die Freiheit, die 16 Bits in jeder beliebigen Reihenfolge an jeden beliebigen Speicherplatz zu legen. Ob man nun das Höherwertige der beiden Bytes (Most Significant Byte, MSB) in R0 oder in R1 ablegt, ist ganz egal und nur der Assembler-Programmierer muss sich das merken. Zum Hinschreiben benutzt er die Zeichenfolge R1:R0, wenn das MSB in R1 steht, oder R0:R1, wenn das MSB in R0 steht.

Die Erweiterung von 16 Bits auf 64 Bits ist simpel: man braucht nur mehr Register. Die 64 Bits passen gut in die Registerfolge R7:R6:R5:R4:R3:R2:R1:R0. Man kann sie aber genauso gut in R3:R7:R6:R0:R2:R1:R4:R3:R5 legen, wenn man sich nur diese Reihenfolge merken könnte. Man kann sich das Leben auch schwerer machen als nötig, dem Prozessor ist es hingegen völlig wurscht.

Um verständlichen Code zu schreiben habe ich die Register R7:R6:R5:R4:R3:R2:R1:R0 verwendet und als N1 bezeichnet. Als Kürzel ist auch die Schreibweise R7:...:R0 verwendet. Wenn man eine zweite 64-Bit-Zahl braucht, ist R15:R14:R13:R12:R11:R10:R9:R8 oder kurz N2 eine gute Wahl, auch als R15:...:R8 abgekürzt.

Da die AVRs viele Register zur Verfügung haben (nicht so bei anderen Prozessoren wie den PICs oder in den 3GHz-Monstern im PC), ist es nicht nötig solche Zahlen in das SRAM auszulagern, denn mit Registern lässt es sich wunderbar schnell und einfach rechnen. Falls aber die Register nicht reichen, kann man die Zahlen doch noch in das SRAM kopieren. Wenn wir den Speicherplatz dort mit sN1 bezeichnen und dies im Datensegment mit .DSEG auch so definieren, können wir die Register R0 bis R7 mit dem folgenden Code dort ablegen: 

  sts sN1,R0 ; Speichere Register R0 im SRAM an der Adresse sN1
  sts sN1+1,R1
  sts sN1+2,R2
  sts sN1+3,R3
  sts sN1+4,R4
  sts sN1+5,R5
  sts sN1+6,R6
  sts sN1+7,R7
Wenn Du die 64 Bits an einer anderen Adresse, z. B. sN2, hinlegen willst, musst Du diesen Code kopieren und sN1 durch sN2 ersetzen.

Weil das Kopieren der 64-Bit-Zahl aus den Registern in das SRAM immer diese acht Bytes transferieren muss, kann man auch den folgenden Code verwenden. Er arbeitet mit Zeigerregistern anstelle von festen Adressen: Das Zeigen von X auf das Register R0 ist simpel: dessen Adresse ist 0. Also einfach die Instruktionen clr XH und clr XL verwenden. Mit der Instruktion ld R16,X+ wird der Inhalt von Register R0 in das Register R16 befördert, mit st Z+,R16 dessen Inhalt an die Adresse im SRAM befördert, auf die der Zeiger Z zeigt. Das "+" in X+ und Z+ bewirkt die automatische Erhöhung der Zeigeradresse nach dem Lesen mit LD und Schreiben mit ST. Wenn X nach dem Lesen 8 erreicht, ist die Kopieraktion zu Ende, andernfalls wiederholt sich die Schleife.

Der Assembler-Quellcode hier stellt eine solche Routine zur Verfügung, sie heißt CopyN1ToSramN1: und kopiert N1 in das SRAM ab Adresse sN1: 

; Copy N1 to SRAM location
CopyN1ToSramN1:
  ldi ZH,High(sN1) ; Point Z to Sram N1, MSB
  ldi ZL,Low(sN1) ; dto., LSB
CopyN1ToSram:
  clr XH ; Point X to N1, MSB
  clr XL ; dto., LSB
CopyN1ToSram1:
  ld rmp,X+ ; Read register
  st Z+,rmp ; Write to SRAM
  cpi XL,8 ; All 8 bytes copied?
  brne CopyN1ToSram1
  ret
Das Vielzweckregister rmp ist vorher mit .def rmp = R16 auf R16 gelegt worden.

Diese Routine ist rasend schnell: bei einem Takt von 1 MHz braucht sie einschließlich dem RCALL und dem RET 68 µs. Und sie kann für jede SRAM-Position verwendet werden: einfach Z an eine andere Position zeigen lassen und CopyN1ToSram: aufrufen, dann kommt N1 woanders hin.

Woher habe ich die 68 µs? Man kann natürlich Takte zählen. Der Aufruf mit RCALL braucht drei Takte. Zwei LDI brauchen 2 Takte, zwei CLR ebenfalls. Sieben Durchläufe durch die Schleife brauchen jeweils sieben Takte (je zwei für LD und ST, einen für CPI und zwei Takte für BRNE mit der Verzweigung. Der letzte Schleifendurchgang verzweigt nicht und braucht daher bloß sechs Takte. Das abschließende RET braucht noch vier Takte. Macht zusammen
n = 3 + 2 + 2 + 7 * 7 + 6 + 4 = 66 Takte

Die zwei Extratakte entstehen aus dem Überspringen der beiden Alternativ-Formulierungen im Quellcode.

2 Simulieren des Programmablaufs mit avr_sim

Dieses Taktzählen war schon etwas aufwändig, ging aber noch. Das Zählen der Takte wird natürlich um so mühsamer je weiter verzweigt Abläufe werden. Das geht dann einfacher durch Simulieren des Programmablaufs.

Simulieren geht folgendermaßen: Das war die Kurzversion der Einführung in die Simulation. Der Simulator kann aber noch ganz viel mehr als nur Takte zählen. Wer noch mehr darüber wissen will, lädt sich das Handbuch des Simulators herunter.

3 Umwandlung von Dezimalzahlen-Zeichenketten in Binärformat

Große Zahlen mit 64 Bits lassen sich in Assembler nicht mit der .EQU-Direktive definieren, weil dieser intern nur mit 32-Bit-Vorzeichenzahlen arbeitet. Wie kann man also die Zahl 123.456.789.012.345.678 definieren?

Nun, die Lösung ist simpel: wir schreiben sie als Zeichenkette in den Quellcode: 

ANumber1:

.db "123,456,789,012,345,678",0 ; A very large first number
Das platziert eine Zeichenkatte mit ASCII-Zeichen in den Flashspeicher an die Adresse ab ANumber1:, beginnend mit der '1' als LSB und der '2' als MSB (der Flashspeicher ist wortweise organisiert), und weiter bis ans Ende der Zahl und dann eine Null als Binär-Null 0x00. Die Zeichenkette ist damit null-terminiert, damit man beim Lesen weiß wo das Ende ist. Die Umwandlungsroutine Dec2BinN1: im Quellcode erkennt daran das Ende. Wenn die Anzahl der Zeichen in der .db-Zeile ungerade ist (Assembler-Meldung beachten), kann man eine weitere Null anfügen oder ein führendes Leerzeichen vor die Zahl schreiben, damit die Meldung verschwindet.

Die Routine akzeptiert Kommata, Punkte oder auch Leerzeichen als Tausender-Trennzeichen, und überliest diese Füllzeichen.

Das Lesen der Zahl beginnt damit, dass N1 (R7:...:R0) auf Null gesetzt wird. Das Zeiger-Registerpaar Z zeigt auf das erste Zeichen im Flash, wegen der wortweisen Organisation des Flashspeichers auf die verdoppelte Adresse von ANumber1:. Mit LPM wird das erste Zeichen aus dem Flash geholt. Ist das eine Null (0x00), ist die Zahlumwandlung zu Ende. Nachdem alle Tausender-Trennzeichen abgeklappert sind (falls: einfach das nächste Zeichen holen), werden hexadezimal 0x30 von dem Zeichen abgezogen. Ergibt das einen Unterlauf (Carry-Flagge gesetzt), handelt es sich nicht um ein ASCII-Zeichen für eine Ziffer und die Routine kehrt mit gesetztem Carry-Flag zurück (Fehler im Zeichen). Ist das Subtraktionsergebnis größer als Neun, dann ebenfalls.

Bevor das Zeichen weiter verarbeitet wird, wird der bisherige Inhalt der 64-Bit-Zahl mit zehn multipliziert. Und das geht so:
  1. Kopieren der acht Bytes der bisherigen Zahl an einen anderen Ort, hier R15:...:R8, oder auch ins SRAM),
  2. Multiplikation von N1 mit zwei (Linksschieben von R0, dann Linksrotieren aller Register R1 bis R7 mit Einschieben des Carry-Flags als Bit 0),
  3. falls beim letzten Rotieren ein gesetztes Carry herauskam, liegt ein Fehler vor: die Zahl ist zu groß für 64 Bits, Überlauf-Fehler,
  4. dann erneute Multiplikation mit Zwei (Ausgangszahl mal vier) durch nochmaliges Linksschieben und siebenfaches Linksrotieren und erneute Überlauf-Prüfung,
  5. nun wird die vorher kopierte Ausgangszahl addiert (Ausgangszahl mal fünf), indem deren LSB mit add R0,R8 und die darauf folgenden Register mit adc R1,R9 etc. addiert, was auch noch Überläufe aus der unteren Addition mit dazu addiert, auch hier wird der letzte Schritt auf einen Überlauf geprüft,
  6. danach noch mal mit Zwei malnehmen und fertig ist das Zehnfache der 64-Bit-Zahl N1.
Mit add R0,R16 kann nun die gelesene und umgewandelte Ziffer hinzuaddiert werden. Da auch hierbei ein Überlauf vorkommen kann, wird R16 auf Null gesetzt (mit LDI R16,0, nicht mit CLR R16, da dieses das Carry-Flag löschen würde) und die Null mit adc Rn,R16 anschließend zu allen nachfolgenden Registern hinzuaddiert.

Wenn das gelesene Zeichen 0x00 auftaucht, ist Ende und es wird mit gelöschtem Carry zurückgekehrt.

Um die Umwandlung von 123.456.789.012.345.678 in eine 64-Bit-Binärzahl zu simulieren, kann man den Code einfach loslaufen lassen. Er braucht 2,235 Millisekunden oder vollführt 2.235 Instruktionen, etwas zu viel um die Dauer mit Taktabzählen zu ermitteln.

Weiter unten im Quellcode wird eine etwas kleinere Zahl von Dezimal-ASCII nach Binär konvertiert und benötigt etwas kürzere Ausführungszeit. Näherungsweise steigt die Zeit linear mit der Anzahl an Stellen, da die Multiplikation mit 10 der längste Teilschritt ist.

Alles ziemlich schnell für einen popeligen 8-Bit-Prozessor, oder?

4 Binäres Addieren zweier 64-Bit-Zahlen

Das ist eine ziemlich einfache Aufgabe: nur mit add R0,R8 und mit adc R1,R9 etc. alle weiteren Bytes bis R7/R15 addieren. Falls die letzte Addition mit gesetztem Carry-Flag endet, gab es einen Überlauffehler.

Das Addieren benötigt nur 16 µs und ist extrem schnell.

Im Quellcode hier wird das Ergebnis in das SRAM an die Stelle sN3 kopiert und kann mit den beiden Ausgangszahlen in sN1 und sN2 verglichen werden. Einfach beim Simulieren einen Breakpoint hinter die Überlauf-Prüfung brcs AddError setzen.

5 Subtrahieren einer großen Zahl von einer anderen

Das ist ebenfalls eine einfache Übung: statt add nun sub R0,R8 und statt adc nun sbc R1,R9 etc. verwenden. Auch hier zeigt das Carry-Flag am Ende an, ob die subtrahierte Zahl größer war.

Subtraktion braucht ebenfalls nur sehr schnelle 16 µs.

Das Ergebnis wird ebenfalls in sN3 im SRAM kopiert.

6 Multiplikation einer 64-Bit-Zahl mit einer 8-Bit-Binärzahl

Etwas ausgefeilter, aber auch noch relativ einfach, ist die Multiplikation. Im ersten Schritt wird dazu N1 in N2 kopiert und N1 auf Null gesetzt.

Dann wird Bit-für-Bit im Multiplikator R16 nach rechts in das Carry geschoben. Ist eine Eins im Carry, wird N2 zu N1 hinzuaddiert, natürlich wieder mit Überlaufprüfung. Ist R16 danach leer (Null), ist die Multiplikation beendet und kehrt mit gelöschtem Carry zurück.

Falls nicht, wird N2 mit zwei malgenommen (Linksschieben und Linksrotieren), ebenfalls wieder mit Carry-Prüfung, und mit dem nächsten Bit weitergemacht.

Multiplikation mit der 8-Bit Binärzahl 255 (alle Bits führen zu einer Addition) ist in sehr schnellen 205 µs erledigt. Ein Hardware-Multiplikator wäre kaum schneller als diese Software-Multiplikation.

Das Ergebnis wird wieder nach sN3 kopiert.

7 Auflisten der Zehnerpotenzen im Binärformat

Ein hilfreiches Werkzeug ist in der Routine ListDecimals:: gegeben: es berechnet alle Zehnerpotenzen ab 1 mit 10, 100, 1000, usw. und stellt sie im 64-Bit-Format in das SRAM. Es endet, wenn die Zehnerpotenz die 64-Bit-Grenze überschreitet. Weil verfügbare Rechentools (z. B. der Rechner in Windows 10) meist vorzeichenbehaftete 64-Bit-Ganzzahlen verwenden, lässt sich die hier ermittelte größte Zahl 1019 mit diesen gar nicht korrekt ausrechnen.

Berechnung und Auflistung brauchen 2,991 ms.

8 Umwandeln von 64-Bit-Binärzahlen in dezimale Zeichenketten

Zum Schluss noch die Königsdisziplin: aus 64 Bits wieder eine Dezimalzahl machen, aber mit Unterdrückung führender Nullen und mit Tausender-Trennzeichen und die Zeichenkette im Sram ablegen.

Dazu brauchen wir die bei der Liste oben generierten Zehnerpotenzen. Sie sind in der Tabelle DecimalTable: von oben nach unten enthalten, es fehlt nur die 100, dafür endet sie mit 0xFF, um das Ende anzuzeigen.

Die Mathematik der Umwandlung geht so:
  1. Die 64-Bit-Repräsentation der Dezimalpotenz wird aus dem Flashspeicher in N2 gelesen. Ist das erste Byte 0xFF, ist die Zahlenumwandlung bei der letzten Dezimalziffer angelangt.
  2. N2 wird solange von N1 abgezogen, bis ein Unterlauf auftritt. Die Anzahl Subtraktionen wird gezählt.
  3. Die Anzahl Subtraktionen wird mit subi R16,-'0' in eine ASCII-Ziffer umgewandelt (was 0x30 dazu addiert).
  4. Dann wird geprüft, ob die T-Flagge im Statusregister gelöscht ist. Diese signalisiert, dass führende Nullen durch Leerzeichen ersetzt werden. Fall gelöscht, wird das Zeichen direkt in das SRAM geschrieben. Falls es gesetzt ist, wird überprüft, ob das Zeichen eine ASCII-Null ist. Falls ja, wird es durch ein Leerzeichen ersetzt und ausgegeben, falls nicht, wird die T-Flagge gelöscht und das Zeichen ausgegeben.
  5. Nach der Ausgabe wird ein Zähler abwärts gezählt. Erreicht dieser Null, wird bei gesetzter T-Flagge ein Leerzeichen und bei gelöschter T-Flagge ein Tausender-Trennzeichen in das SRAM eingefügt und der Zähler wieder auf drei gesetzt.
Die letzte Ziffer, die nach dem Abziehen aller Zehnerpotenzen noch in R0 verblieben ist, wird durch Addieren der ASCII-Null ausgegeben, unabhängig vom Zustand der T-Flagge.

Wenn die Zahl links-justiert benötigt wird, kopiert man den X-Zeiger in dem Moment wenn das T-Flag gelöscht wird. Zu Beginn sollte dieser Zeiger auf der letzten Stelle stehen, falls die Zahl kleiner als 10 sein sollte.

Die Umwandlung in den aus 26 Zeichen bestehenden Dezimal-ASCII dauert 2,682  für die größere und 2,052 ms für die kleinere Zahl.

9 Zählen für lange Zeiten mit 64 Bits

Wer seinen AVR für ein paar Stunden, Tage, Monate oder Jahre lang mit Zählen befassen möchte, um schließlich irgendein Gerät einzuschalten, ist mit einem 64 Bit weiten Zähler gut bedient: er kann auch noch 100 Jahre lang Takte zählen, ohne zu ermüden. 100 Jahre sind bei 1 MHz Takt
t [µs] = 100 [Jahre] * 365,25 [Tage/Jahr] * 24 [Stunden/Tag] * 60 [Minuten/Tag] * 60 [Sekunden/Minute] * 1.000.000 [µs/Sekunde] = 9.467.280.000.000.000
Schleifenzähler = t / 3 - t/3 DIV 256 - t/3 DIV 2562 - ... - t/3 DIV 2565 = 1.047.794.823.776.258 = 0x0003.B8F6.BE44.C802
und liegt daher noch immer um das 5.555-fache unter den in acht Bytes handhabbaren Maximalzahlen. Wenn nur die Batterie die 100 Jahre überstehen würde!

Hier gibt solche ewig langen Zeitschleifen und wie man sie berechnet und in Assembler programmiert.

10 Schlussfolgerungen

Der Umgang mit 64-Bit-Zahlen ist generell eine ziemlich einfache Angelegenheit: es braucht ein paar wenige Addier- und Subtrahierinstruktionen, ohne und mit Carry, und einige wenige Schiebe- und Rotierbefehle, und eine Menge Fehlererkennung. Nicht gerade Befehle, die das intellektuelle Vermögen von Java- oder C-Programmierern auslasten, die sich normalerweise um solche Niederungen wie Addieren, Subtrahieren und Multiplizieren nicht scheren, weil der Compiler das für sie erledigt.

Assembler produziert schnellen (im ms-Bereich) und äußerst effizienten Code um alles Nötige zu machen. Kein Grund, um ewig große Bibliotheken zu bemühen oder auf 16-, 32, 48- oder 64-Bit-Prozessoren umzusteigen.

Ein wichtiger Grund für diesen effizienten Code ist, dass die AVRs jede Menge Register haben und einen sehr effizienten Instruktionsset. Ohne das würden die Routinen viel länger werden, umständlicher arbeiten und viel mehr Zeit benötigen.

To the top of that page

(©)2019 by http://www.avr-asm-tutorial.net