Ganzahl MULtiplikation und DIVision
Hier geht es zwar nicht um die höhere Mathematik, aber etwas Erfahrung mit dem Assembler und der Programmierung solltet ihr bereits haben.
Die Mnemonics, Zahlensysteme, Wie der Rechner rechnet und kleinere Programmieraufgaben stellen für euch sicher kein Problem mehr dar, sonst würdet ihr euch doch bestimmt nicht mit der Multiplikation und Division beschäftigen.
Bevor gleich jemand meint…
„Das kann man aber besser bzw. schneller lösen!“ – JA, das stimmt!
Es geht hier auch nicht um die perfekte Lösung, sondern um das grundsätzliche Verständnis.
Leider muss ich euch, wie bereits an anderer Stelle erwähnt, enttäuschen. Der 6510 (6502) besitzt weder für die Multiplikation noch für die Division entsprechende Mnemonics. Es gibt es also keinen MUL– oder DIV-Befehl. Wir müssen uns daher eigene Routinen schreiben, um diese Aufgaben zu erledigen.
Du lügst oder es gibt sie doch!
Wenn euch, wie ich hoffe, die verfügbaren Mnemonics gut bekannt sind, dann werdet ihr bei meiner Einleitung wohl gedacht haben, so ganz stimmt das aber nicht.
Eine Befehlsgruppe ermöglicht die Multiplikation und Division. Dabei handelt es sich zwar nur um einen Sonderfall, aber der ist häufig hilfreich. Gemeint sind die Verschiebebefehle asl / lsr sowie die Rotationsbefehle rol / ror (vorsicht mit dem Carry-Flag). Mit diesen Befehlen könnt ihr durch eine Verschiebung der Bits nach links eine Multiplikation mit zwei und durchs Verschieben nach rechts eine Division durch zwei erreichen. Durch mehrfaches Anwenden eines Befehls könnt ihr so MULtiplikationen & DIVisionen mit 2, 4, 8, 16 usw. vornehmen und das sehr flott. Über das C-Flag könnt ihr bei einer Verschiebung nach rechts sogar den Rest ermitteln. Auch wenn wir die Befehle gleich verwenden, möchte ich hier nicht erneut auf deren genaue Funktionsweise eingehen. Solltet ihr damit nicht so ganz vertraut sein, dann schaut euch besser nochmal die Erklärungen zum LSR und ROL an.
Das Rahmenprogramm
Um unsere Ergebnisse zu kontrollieren, schlage ich folgendes Progrämmchen als „Gerüst“ vor:
ZP_MULTIPLIKATOR = $fb ZP_DIVIDEND = ZP_MULTIPLIKATOR ZP_MULTIPLIKANT = $fc ZP_DIVISOR = ZP_MULTIPLIKANT ZP_ERGEBNIS = $fd ZP_HELP = $02 OFFSET = $28 ;Offset für die BS-Ausgabe ;*** Startadresse BASIC-Zeile *=$0801 !word asmStart-2,2018 !text $9e," 2062",$00,$00,$00 !zone asmStart asmStart cld ;zur Sicherheit D-Flag löschen jsr clrScreen ;BS löschen lda #$83 ;Multiplikator / Dividend sta ZP_MULTIPLIKATOR ;sta ZP_DIVIDEND ldy #OFFSET + $00 jsr hexOut ;ausgeben lda #$17 ;Multiplikant / Divisor sta ZP_MULTIPLIKANT ;sta ZP_DIVISOR ldy #OFFSET + $06 jsr hexOut ;ausgeben lda #"*" sta $0404+OFFSET lda #"=" sta $040a+OFFSET ;*** Rechenfunktion aufrufen ldy #OFFSET + $0c ;Position festlegen lda ZP_ERGEBNIS+1 ;Ergebnis (MSB) jsr hexOut ;inkl. $ ausgeben ldy #OFFSET + $0e ;Position festlegen lda ZP_ERGEBNIS ;Ergebnis (LSB) jsr hexOut2 ;OHNE $ ausgeben rts ;zurück zum BASIC ;******************************************************************************* ;*** Bildschirm löschen (füllen) ;******************************************************************************* ;*** Übergabe: - ;******************************************************************************* ;*** Rückgabe: - ;******************************************************************************* ;*** ändert : A, X, SR ;******************************************************************************* !zone clrScreen clrScreen ldx #$00 ;256 Durchläufe lda #" " ;Zeichen zum Löschen (Füllen) .loop sta $0400,x ;1. Page des BS-Speichers sta $0500,x ;2. Page sta $0600,x ;3. Page sta $0700-24,x ;4. Page (Sprite-Pointer beachten) dex bne .loop rts ;zurück ;******************************************************************************* ;*** Eine Zahl hexadezimal ausgeben ;******************************************************************************* ;*** Übergabe: A = Zahl ;*** Y = Position ab $0400 ;******************************************************************************* ;*** Rückgabe: - ;******************************************************************************* ;*** ändert : X, Y, SR ;******************************************************************************* !zone hexOut hexOut pha lda #"$" ;$ ausgeben sta $0400,Y pla hexOut2 ;start für Zahlen über 8-Bit pha pha and #%00001111 tax lda hexvalues,x sta $0402,y ;unteres Nibble ausgeben pla lsr lsr lsr lsr tax lda hexvalues,x sta $0401,y ;oberes Nibble ausgeben pla rts ;zurück hexvalues !scr "0123456789abcdef" ;Text für die Ausgabe
Wir verwenden gleich die Zero-Page, um dort unsere Zahlen abzulegen und das Ergebnis zu speichern. In unseren Beispielen rechnen wir immer mit 8-Bitzahlen. Dabei teilen sich Multiplikator und Dividend sowie Multiplikant und Divisior je eine Speicherstelle. Ich habe hier extra verschiedene Namen für die selbe Speicherstelle gewählt, damit in den Funktionen klarer wird, was wir dort gerade machen. Außerdem sehen wir noch jeweils 16-BIT für eine Hilfsvariable und das Ergebnis vor. Über die Konstante OFFSET könnt ihr die Ausgabe etwas verschieben. Beachtet aber, dass sie sich immer komplett in der ersten Page des Bildschirmspeichers befinden muss.
Dann haben wir einen Hauptteil, der einfach den BS löscht, unsere Zahlen in die Zero-Page schreibt, die Rechenfunktion (kommt gleich) startet und schließlich das Ergebnis ausgibt.
Als Hilfsfunktionen verwenden wir clrScreen (löscht den Bildschirm) und hexOut (Hex-Ausgabe).
Jetzt sollten wir mal etwas rechnen…
Brute-Force Methode
Eine funktionierende Möglichkeit wäre es, die Multiplikation und Division über Schleifen zu lösen. Dabei verwenden wir für MUL die wiederholte Addition und für DIV die Subtraktion. Um erstmal lauffähige Funktionen zu erhalten, setzen wir das einfach in die Tat um. Einen solchen Ansatz bezeichnet man häufig als Brute-ForceBrute-ForceUmgangssprachlich: In der Informatik eine zwar funktionierende, aber nicht besonders elegante / effiziente Lösung für ein Problem finden.. Laßt uns auf diese Art einfach mal zwei 8-Bit Zahlen multiplizieren.
Brute-Force Muliplikation
Nehmt diese Funktion in das Rahmenprogramm (z. B. vor clrScreen) auf.
;******************************************************************************* ;*** Brute-Force: 8-BIT Multiplikation durch wiederholte Addition ;******************************************************************************* ;*** Übergabe: ZP_MULTIPLIKATOR ;*** ZP_MULTIPLIKANT ;******************************************************************************* ;*** Rückgabe: ZP_ERGEBNIS (16-BIT) ;******************************************************************************* ;*** ändert : A, X, SR ;******************************************************************************* !zone bruteforce_mul bruteforce_mul lda #$00 ;Ergebnis auf 0 setzen sta ZP_ERGEBNIS sta ZP_ERGEBNIS+1 ldx ZP_MULTIPLIKATOR ;Multiplikator als Schleifenzähler bne .loop ;wenn größer 0 'rechnen' rts ;sonst zurück zum Aufrufer .loop lda ZP_MULTIPLIKANT ;Multiplikant in den Akku clc ;C-Flag löschen adc ZP_ERGEBNIS ;Akku zum LSB addieren sta ZP_ERGEBNIS ;und speichern lda ZP_ERGEBNIS+1 ;MSB in den Akku adc #$00 ;0 addieren (wg. Carry) sta ZP_ERGEBNIS+1 ;speichern dex ;Schleifenzähler (MULTIPLIKATOR) verringern bne .loop ;solange größer 0, nochmal rts ;zurück zum Aufrufer
Wir legen Multiplikator und Multiplikant als 8-Bit auf der Zero-Page ab, dort finden wir zum Schluß ebenfalls das 16-Bit Ergebnis. Zu Beginn von bruteforce_mul setzen wir das Ergebnis erstmal auf Null. Wir benötigen für die Multiplikation zweier 8-Bit Zahlen, natürlich ein 16-Bit großes Ergebnis. Dann laden wir den Multiplikator ins X-Register und prüfen, ob dieser ungleich null ist. Falls ja geht es zur Schleife, sonst verlassen wir die Funktion direkt wieder. Diese Prüfung ist wichtig, da sonst statt 0 mit 256 multipliziert wird.
In der .loop-Schleife, wird zunächst der Multiplikant in den Akku geholt und zum LSB vom Ergebnis addiert. Den Akkuinhalt schreiben wir dann zurück und holen das MSB. Um das Carry-Flag zu verarbeiten, addieren wir anschließend einfach eine 0 und schreiben das MSB zurück in den Speicher. Dann wird das X-Register verringert und wir wiederholen das Ganze, solange X größer 0 ist. Somit wurde der Multiplikant, so oft, wie es der Multiplikator vorgibt, zum Ergebnis addiert.
Schon ist die Routine fertig! Ruft diese Funktion jetzt noch im Hauptteil (hinter ;*** Rechenfunktion aufrufen) mit jsr bruteforce_mul auf und startet das Programm.
Sofern ihr die Werte aus meinem Beispiel beibehalten habt, sollte eure Ausgaben dieser gleichen.
Probiert jetzt mal verschiedene Werte für den Multipliaktor und Multiplikanten aus.
Wenn man diese Holzhammer-Methode verwenden möchtet, bieten sich durchaus noch Verbesserungen im Detail an. Vielleicht fallen euch ja welche ein und ihr setzt sie um (denkt z. B. mal über die Schleifen-Anzahl und Sonderfälle nach).
Brute-Force Division
Die Division kann man auf die gleiche Weise angehen. Nur wird diesmal die Subtraktion benötigt. Teilen wir zwei 8-BIT-Zahlen…
;******************************************************************************* ;*** Brute-Force: 8-BIT Division durch wiederholte Subtraktion ;******************************************************************************* ;*** Übergabe: ZP_DIVIDEND ;*** ZP_DIVISOR ;******************************************************************************* ;*** Rückgabe: ZP_ERGEBNIS (8-BIT) ;*** ZP_DIVIDEND (8-BIT) enthält den evtl. Rest ;******************************************************************************* ;*** ändert : A, X, SR ;******************************************************************************* !zone bruteforce_div bruteforce_div lda #$00 sta ZP_ERGEBNIS ;Ergebnis auf 0 setzen lda ZP_DIVISOR ;wenn durch 0 geteilt wird beq .exit ;raus (eigentlich einen Fehler anzeigen) lda ZP_DIVIDEND ;falls 0 geteilt werden soll beq .exit ;raus (Ergebnis wäre wieder 0) .skip cmp ZP_DIVISOR ;vergleiche Dividend und Divisior bcs .skip1 ;wenn der Dividend größer oder gleich ist, weitermachen sta ZP_DIVIDEND ;sonst Rest merken .exit rts ;zurück zum Aufrufer .skip1 sec ;C-Flag für Subtraktion setzen sbc ZP_DIVISOR ;Divisor vom Dividend abziehen inc ZP_ERGEBNIS ;Ergebnis um 1 erhöhen jmp .skip ;nochmal versuchen
Auch hier verwenden wir wieder die Zero-Page, dort speichern wir Dividend, Divisor und das Ergebnis. Dieses Mal reichen aber drei 8-Bit Speicherstellen. Gleich am Anfang von bruteforce_div setzen wir das Ergebnis natürlich wieder auf 0. Danach prüfen wir, ob „durch 0“ geteilt werden soll. Wir verlassen die Funktion dann einfach, eigentlich gehört dort eine Fehlermeldung „Division durch null“ oder zumindest ein Fehler-Kennzeichen hin. Falls der Dividend 0 ist, brauchen wir nicht zu teilen und können die Routine direkt wieder verlassen. Sind alle Voraussetzungen gegeben, dann beginnen wir bei .skip mit dem Teilen. Wir werden gleich laufend den Divisior vom Dividend abziehen, aber nur solange der Dividend größer oder gleich dem Divisor ist. Das prüfen wir als erstes, ist er größer oder gleich, geht es bei .skip1 weiter, sonst wird der Rest, der sich im Akku befindet, in die Zero-Page nach ZP_DIVIDEND zurückgeschrieben. Bei .skip1 subtrahieren wir vom Akku einfach den Divisor und erhöhen unser Ergebnis um eins. Nun springen wir wieder nach .skip, wo erneut geprüft wird, ob der „restliche“ Dividend (immer noch) größer als der Divisor (oder zumindest gleich groß) ist.
Am Schluß findet ihr in ZP_ERGEBNIS den ganzzahligen Quotinenten und in ZP_DIVIDEND den eventuellen Rest. Wer die original Werte nicht verändern möchte, kann den Rest natürlich auch anderweitig speichern.
Da wir jetzt auch noch den Rest ausgeben wollen, habe ich das Rahmenprogramm etwas umgebaut.
ZP_MULTIPLIKATOR = $fb ZP_DIVIDEND = ZP_MULTIPLIKATOR ZP_MULTIPLIKANT = $fc ZP_DIVISOR = ZP_MULTIPLIKANT ZP_ERGEBNIS = $fd ZP_HELP = $02 OFFSET = $28 ;Offset für die BS-Ausgabe DOMUL = 1 ;Für DIVision auskommentieren! ;*** Startadresse BASIC-Zeile *=$0801 !word asmStart-2,2018 !text $9e," 2062",$00,$00,$00 !zone asmStart asmStart cld ;zur Sicherheit D-Flag löschen jsr clrScreen ;BS löschen lda #$83 ;Multiplikator / Dividend !ifdef DOMUL { sta ZP_MULTIPLIKATOR } else { sta ZP_DIVIDEND } ldy #OFFSET + $00 jsr hexOut ;ausgeben lda #$17 ;Multiplikant / Divisor !ifdef DOMUL { sta ZP_MULTIPLIKANT } else { sta ZP_DIVISOR } ldy #OFFSET + $06 jsr hexOut ;ausgeben lda #"*" sta $0404+OFFSET lda #"=" sta $040a+OFFSET ;*** Rechenfunktion aufrufen !ifdef DOMUL { jsr bruteforce_mul ;*** Ausgabe der Multiplikation lda #'*' sta $0404 + OFFSET ldy #OFFSET + $0c ;Position festlegen lda ZP_ERGEBNIS+1 ;Ergebnis (MSB) jsr hexOut ;inkl. $ ausgeben ldy #OFFSET + $0e ;Position festlegen lda ZP_ERGEBNIS ;Ergebnis jsr hexOut2 ;OHNE $ ausgeben } else { jsr bruteforce_div ;*** Ausgabe der Division ldy #OFFSET + $0c ;Position festlegen lda ZP_ERGEBNIS ;Ergebnis jsr hexOut ;inkl. $ ausgeben ldy #OFFSET + $15 ;Position festlegen lda ZP_DIVIDEND ;Rest jsr hexOut ;inkl. $ ausgeben lda #":" sta $0404 + OFFSET lda #$12 ;R sta $0410 + OFFSET lda #$05 ;E sta $0411 + OFFSET lda #$13 ;S sta $0412 + OFFSET lda #$14 ;T sta $0413 + OFFSET } rts ;zurück zum BASIC
Ich verwende hier die „bedingte Assemblierung“.
Mit !ifdef <KONSTANTE> { … } else { … } können wir den Assembler dazu bringen, dass nur aktuell benötigte Befehle ins endgültige Programm übernommen werden. Ich habe hier die Konstante DOMUL für die Prüfungen festgelegt und auf 1 gesetzt, der Wert ist vollkommen willkürlich und hat keinen Einfluss auf die !ifdef-Prüfung. Sobald diese Konstante definiert ist (unabhängig vom zugewiesenen Wert), werden die Anweisungen zwischen den geschweiften Klammern { … } hinter !ifdef DOMUL assembliert. Ist die Konstante nicht definiert, dann wird der Block hinter !ifdef komplett ignoriert. Sollte es (wie hier) einen else-Block geben, dann werden stattdessen die Anweisungen zwischen den geschweiften Klammern hinter else ins Programm übernommen. Ihr müsst also nur ein Semikolon ; vor die Zeile DOMUL = 1 ;Für DIVision auskommentieren! schreiben, damit die DIVision, statt der MULtiplikation ausgeführt wird.
Ein kleines Beispiel
Wir gehen davon aus, dass DOMUL definiert ist... lda #$83 !ifdef DOMUL { sta ZP_MULTIPLIKATOR } else { sta ZP_DIVIDEND } ldy #OFFSET + $00 Durch die bedingte Assemblierung sieht der Quellcode für den Assembler bei der Programmerstellung so aus: lda #$83 sta ZP_MULTIPLIKATOR ldy #OFFSET + $00 Die Zeile sta ZP_DIVIDEND wird überhaupt nicht beachtet. Kommentieren wir DOMUL = 1 aus und lassen das Programm erstellen, dann ignoriert der Assembler sta ZP_MULTIPLIKATOR lda #$83 sta ZP_DIVIDEND ldy #OFFSET + $00
Dieses Vorgehen ist immer dann interessant, wenn ihr z. B. Testausgaben in euer Programm aufnehmen wollt oder verschiedene Fassungen (z. B. für PAL oder NTSC) benötigt. Dann könnt ihr durch die bedingte Assemblierung alles in den Source aufnehmen und braucht vor der Erstellungen nur die entsprechenden „Schalter“ zu setzen, sprich die Konstanten ein- oder auskommentieren (z. B. DEBUG = 1 oder ;DEBUG = 1).
Ihr könnt nun DOMUL = 1 einfach ein- oder auskommentieren, um die jeweilige Rechenfunktion auszuführen. Wir wollen nun die Division kontrollieren, achtet also auf das Semikolon ;DOMUL = 1 und startet dann das Programm.
Wie ihr seht, passt die $17 fünf mal in $83 ($05 * $17 = $73) es bleibt also ein Rest von $10, der nicht verteilt werden konnte (wir rechnen hier ja nur mit Ganzahlen).
Damit haben wir jetzt schon zwei einfache Möglichkeiten, um Zahlen zu multiplizieren oder zu teilen. Diese lassen sich natürlich noch etwas optimieren oder für größere Zahlen umbauen. Um mal schnell (OK, kurz) etwas zu berechnen reichen diese Funktionen evtl. aus, aber sollten sie häufiger oder in zeitkritischen Situationen benötigt werden, dann wäre ein eleganterer und vor allem schnellerer Ansatz wünschenswert.
Optimierte MUL & DIV-Funktionen
Die Brute-Force-Funktionen klappen zwar, benötigen aber ggf. unverschämt viel Rechenzeit (zählt mal die Taktzyklen für 255 * 255). Schade, dass nicht alles so schnell, wie mit den Verschiebe- / Rotations-Befehlen geht. Gibt es evtl. einen Weg die obige Addition- und Subtraktion-Methode damit zu kombinieren?
Vielleicht sollten wir erstmal klären, wie man Binärzahlen überhaupt multipliziert. Bitte nicht lachen, eigentlich kennt ihr dass aus der Grundschule. Um das Beispiel übersichtlich zu halten, nehmen wir nur zwei Nibble.
Rechnen wir einfach: %1100 * %0011 (also 12 * 3) ---- ------- 1 0011 1 3 1 0011 2 6 0 0000 == 0 0000 36 ======= | 0100100 <------------
Wir gehen also genau so vor, wie wir es in der Schule, beim schriftlichen Multiplizieren gelernt, haben. Es wird die erste Stelle des Multiplikators mit dem Multiplikanten multipliziert (watn Satz 😉 ), dann die nächste und das Ergebnis um eine Stelle nach rechts verschoben usw. Hier ist es sogar noch einfacher, da wir nur 0 und 1 haben. Zum Schluß werden dann die einzelnen Werte wieder addiert.
MUL mit Shift & Rotate
Dass schreit doch förmlich nach den Schiebe- & Rotations-Befehlen, oder? Laßt uns also eine neue Funktion entwickeln.
;******************************************************************************* ;*** 8-BIT Multiplikation durch Bitverschiebung ;******************************************************************************* ;*** Übergabe: ZP_MULTIPLIKATOR ;*** ZP_MULTIPLIKANT ;******************************************************************************* ;*** Rückgabe: ZP_ERGEBNIS (16-BIT) ;******************************************************************************* ;*** ändert : A, X, SR ;******************************************************************************* !zone shift_mul shift_mul lda ZP_MULTIPLIKANT ;Multiplikant sta ZP_HELP+1 ;ins MSB der Hilfsvariablen lda #$00 ;auf null setzen: sta ZP_HELP ;LSB der Hilfsvaribalen sta ZP_ERGEBNIS ;Ergebnis sta ZP_ERGEBNIS+1 ldx #$08 ;8-BIT, also 8 Durchläufe .loop lsr ZP_HELP+1 ;Hilfsvariable nach ror ZP_HELP ;rechts shiften asl ZP_MULTIPLIKATOR ;Multiplikator <- shiften bcc .skip ;prüfe ob höchstes BIT gesetzt war ;falls nicht -> .skip (keine Addition) clc ;sonst für Addition C-Flag löschen lda ZP_HELP ;LSB von Hilfsvariablen adc ZP_ERGEBNIS ;und Ergebnis addieren sta ZP_ERGEBNIS ;und speichern lda ZP_HELP+1 ;jetzt ist das MSB inkl. Carry-Flag dran adc ZP_ERGEBNIS+1 sta ZP_ERGEBNIS+1 .skip dex ;Schleifenzähler verringern bne .loop ;solange nicht 0 nochmal -> .loop rts ;sonst zurück zum Aufrufer
Die Funktion ist eigentlich ganz einfach. Sie legt den Multiplikanten in einem 16-Bit Hilfsregister ab. Dabei wird der Multiplikant ins MSB geschrieben und das LSB auf 0 gesetzt. Auch das Ergebnis setzen wir natürlich auf 0. Da wir eine 8-Bit-Multiplikation vornehmen, muss unsere Schleife max. 8 mal durchlaufen werden, das X-Register dient als Schleifenvariable. Bei .loop beginnt nun die Schleife für die Multiplikation. Als erstes wird die 16-Bit-Hilfsvariable um ein Bit nach rechts „geshiftet“. Dann wird der Multiplikator um ein BIT nach links geshiftet und kontrolliert, ob das herausgefallene Bit eine 1 war (die landet dann ja im Carry-Flag). War es eine 1, dann müssen wir die Hilfsvariable zum Ergebnis addieren, sonst geht es direkt bei .skip weiter. Dort angekommen wird die Schleifenvariable im X-Register verringert und solange zu .loop gesprungen, bis X null ist. Dann sind wir auch schon fertig.
Auf den ersten Blick sieht die Funktion aufwändiger, als die Brute-Force-Methode aus. Sie benötigt in dieser Form auch mehr Speicher und in bestimmten Fällen sogar mehr Taktzyklen als die BF-Funktion.
Werft mal einen Blick auf die Taktzyklen:
Aufgabe (HEX) | Brute-Force | Shift 00*00 | 19 TZ | 208 TZ 01*01 | 43 TZ | 227 TZ 02*01 | 67 TZ | 227 TZ 1F*01 | 763 TZ | 303 TZ 80*80 | 3091 TZ | 227 TZ FF*FF | 6139 TZ | 360 TZ Brute-Force TZ-Berechnung: Läßt man den Sonderfall 0 mal außer Acht, dann werden 20 + (MULTIPLIKATOR * 24) - 1 Taktzyklen benötigt. Shift Berechnung: Die Berechnung ist etwas aufwendiger, die Anzahl der Zyklen hängt von der Anzahl Nullen und Einsen im MULTIPLIKATOR ab. 25 + (0_BITs * 23) + (1_BITs * 42) - 1
Wie ihr seht bewegen sich die Zeiten für die Shift-Version in einem überschaubaren Rahmen, bei Brute-Force explodieren sie geradezu. Ich hoffe zwar, dass ich mich oben nicht verzählt habe, aber es kommt nicht wirklich auf die korrekte Anzahl Taktzyklen an. Wichtig ist zu erkennen, dass die Brute-Force-Version ab einem bestimmten Punkt (hier sobald der Multiplikant größer als 14 $0E ist) immer mehr Zeit als die Shift-Fassung benötigt.
Wir rechnen hier nur mit 8-BIT Zahlen, wenn wir zwei 16- oder gar 32-Bit Zahlen multiplizieren wollen, wird die BF-Funktion endgültig unbrauchbar. Dort müssten im „worst case“ bei 16-Bit schon 65535, bei 32-Bit sogar 4294967295 Schleifendurchläufe getätigt werden. Bei der Shift-Fassung bräuchte die Schleife nur max. 16 oder 32 mal durchlaufen werden. Es ist klar, dass beide Routinen dafür noch angepasst werden müssten und dann natürlich auch mehr TZ benötigen!
Diese Fassung ist zwar nicht das Optimum, aber als Ausgangspunkt für eure eigenen Routinen schon mal ein Anfang.
Ihr müsst nun nur statt jsr bruteforce_mul die neue Funktion mit jsr shift_mul aufrufen. Ein Start sollte keinen erkennbaren Unterschied zeigen. Warum auch, dass Ergebnis ist ja gleich. Aber es greifen die eben erwähnten Vorteile.
DIV mit Shift & Rotate
Dass ihr eigentlich auch die Division von zwei Binärzahlen schon seit der Grundschule beherrscht, sollte euch jetzt nicht mehr überraschen.
Rechnen wir einfach: %01111010 / %0011 (also 122 / 3) %0 = %0 1 = 0 %01 = %00 12 = 04 %011 = %001 002 = 040 %0001 = %0010 Rest: 2 %00011 = %00101 %000000 = %001010 %0000001 = %0010100 %00000010 = %00101000 Rest: %00000010 zur Übung nochmal: %10101010 / %1100 (also 170 / 12) %1 = %0 1 = 0 %10 = %00 17 = 01 %101 = %000 -12 %1010 = %0000 === %10101 = %00001 50 = 014 -%01100 Rest: 2 ====== %010010 = %000011 -%001100 ======= %0001101 = %0000111 -%0001100 ======== %00000010 = %00001110 Rest: %00000010
Das sollte jetzt kein Problem mehr darstellen, also direkt auf zur neuen Funktion shift_div. Um nicht zu Copy & Paste Programmieren zu werden, solltet ihr mal selbst versuchen, die benötigte Funktion zu schreiben. Denn das bedeutet Programmieren eigentlich. Eine gegebene Aufgabe in ein eigenes Programm umwandeln. Setzt einfach obiges Vorgehen Schritt für Schritt um. Es kommt dabei nicht auf Eleganz oder eine optimale Lösung an.
Eine Möglichkeit findet ihr sonst hier, dieses Mal sollten die Kommentare im Source als Erklärung reichen.
;******************************************************************************* ;*** 8-BIT Division durch Bitverschiebung ;******************************************************************************* ;*** Übergabe: ZP_DIVIDEND ;*** ZP_DIVISOR ;******************************************************************************* ;*** Rückgabe: ZP_ERGEBNIS (8-BIT) ;*** ZP_DIVIDEND (8-BIT) enthält den evtl. Rest ;******************************************************************************* ;*** ändert : A, X, SR ;******************************************************************************* !zone shift_div shift_div lda #$00 ;erstmal eine 0 sta ZP_ERGEBNIS ;ins Ergebnis sta ZP_HELP ;und in die Hilfsvariable lda ZP_DIVISOR ;prüfen ob durch 0 geteilt werden soll beq .exit ;falls ja -> .exit ldx #$08 ;acht Schleifendurchläufe .loop asl ZP_DIVIDEND ;höchstes BIT ins Carry-Flag shiften rol ZP_HELP ;C-Flag ins niedrigste BIT rotieren lda ZP_HELP ;ZP_HELP in den Akku cmp ZP_DIVISOR ;prüfen ob ZP_HELP größer/gleich Divisor bcc .skip ;falls nein -> weiter bei .skip sbc ZP_DIVISOR ;sonst Divisor vom Akku abziehen sta ZP_HELP ;Akku bei ZP_HELP speichern .skip rol ZP_ERGEBNIS ;C-Flag ins Ergebnis rotieren dex ;Schleifenzähler verringern bne .loop ;solange größer 0, nochmal -> .loop .exit lda ZP_ERGEBNIS ;falls das Ergbnis 0 ist, enthält der Dividend beq .skip1 ;den Rest, also -> RAUS lda ZP_HELP ;sonst das LSB der Hilfsvariablen in den sta ZP_DIVIDEND ;Dividend kopieren .skip1 rts ;zurück zum Aufrufer
Ich hoffe ihr habt erfolgreich eure eigene Routine entwickelt, das war es dann auch schon mit der Division.
Wo ist eigentlich das Vorzeichen?
Ist euch aufgefallen, dass wir bisher keine Rücksicht auf das Vorzeichen genommen haben? Solange wir nur mit Zahlen größer/gleich Null arbeiten, ist alles kein Problem. Rechnen wir aber -1 * -1 (in Hex bei 8-Bit $FF * $FF) dann erhalten wir $FE01, das kann so nicht stimmen, richtig wäre 1. Auch bei der Division gibt es Probleme. Teilen wir die Zahlen von eben, dann kommt sogar das Richtige raus: -1 / -1 $FF / $FF ergibt 1. Aber schon bei 1 / -1 $01 / $FF kommen wir auf 0 mit dem Rest 1.
Was kann man nun dagegen machen?
Frei nach „minus mal minus ergibt plus“ können wir die beiden Zahlen positiv betrachten und dann beim Ergebnis und ggf. beim Rest das Vorzeichen wieder umkehren, falls diese vorher unterschiedlich waren.
Hier die umgebaute Multiplikation:
;******************************************************************************* ;*** Vorzeichenbehaftete 8-BIT Multiplikation durch Bitverschiebung ;******************************************************************************* ;*** Übergabe: ZP_MULTIPLIKATOR ;*** ZP_MULTIPLIKANT ;******************************************************************************* ;*** Rückgabe: ZP_ERGEBNIS (16-BIT) ;******************************************************************************* ;*** ändert : A, X, Y, SR ;******************************************************************************* shift_mul_signed: ldy #$00 ;im Y-Reg. merken obs Vorzeich umgekehrt werden muss bit ZP_MULTIPLIKATOR ;Multiplikator negativ? bpl @skip: ;falls nicht -> @skip: ldx ZP_MULTIPLIKATOR ;sonst den Multiplikator in eine dex ;positive Zahl umwandeln txa eor #%11111111 sta ZP_MULTIPLIKATOR ;und speichern iny ;Y erhöhen (wenn ungleich 0 Verzeichen verschieden) @skip: bit ZP_MULTIPLIKANT ;Multiplikant negativ? bpl @skip1: ;falls nicht -> @skip1: ldx ZP_MULTIPLIKANT ;sonst wie eben Vorzeichen umkehren dex txa eor #%11111111 sta ZP_MULTIPLIKANT ;speichern dey ;und Y um eins verringern ;war der Multiplikator auch negativ, dann hat ;Y wieder den Wert 0 und wir brauchen das ;Ergebnis später nicht zu ändern. @skip1: jsr shift_mul: ;'normale' MUL-Funktion starten cpy #$00 ;falls Y 0 ist, bleibt das Vorzeichen erhalten beq @exit: ;dann raus -> @exit: lda ZP_ERGEBNIS+1 ;sonst das Vorzeichen vom Ergebnis ändern eor #%11111111 sta ZP_ERGEBNIS+1 lda ZP_ERGEBNIS eor #%11111111 clc adc #$01 sta ZP_ERGEBNIS lda ZP_ERGEBNIS+1 adc #$00 sta ZP_ERGEBNIS+1 @exit: rts ;zurück
Die Funktion sollte mittlerweile selbsterklärend sein. Das Umwandlung einer negativen in eine positive Zahl erfolgt durch Umkehrung der Schritte für das Zweierkomplement. Die Division anzupassen überlasse ich nun euch.
Eine weitere schöne Übung wäre es, die Bildschirmausgabe von hex auf dezimal umzustellen (da ihr nun durch 10 teilen könnt, läßt sich das relativ einfach bewerkstelligen) und dabei sollte natürlich auch das Vorzeichen beachtet werden.
Wie immer liegt es natürlich bei euch bzw. an eurem Programm, ob ihr Vorzeichen benötigt oder nicht.
Fazit
Damit sind wir am Ende der Ganzahl Multiplikation und Division angelangt.
Nun wisst ihr also, wie man mit dem 6510 (6502) multipliziert und dividiert. Mit obigen Routinen solltet ihr für die Zukunft ( Zukunft bei so einer alten Kiste) gewappnet sein. Es gibt natürlich noch andere Wege, wie man diese Rechnungen vornehmen kann. Einige erkaufen sich z. B. Geschwindigkeit, durch vorberechnete Tabellen (die zum Teil einige KB im Speicher belegen). Wenn man den Platz hat und eine flottere Berechnung benötigt ist das sicher eine Alternative.
Hallo Jörn,
Vielen Dank für Dein Assembler Tutorial!
Mir ist folgendes aufgefallen (korrigiere mich, falls ich falsch liege):
Die Compiler-Direktive “ifdef” prüft doch nur auf Definiertheit, oder?
Es sollte doch egal sein, welchen Wert DOMUL hat.
Solange es definiert ist, wird der Codeteil mit der Multiplikation eineblendet.
Sobald ich DOMUL auskommentiere, sollte wieder der Divisionsteil eingeblended werden.
Zumindest der Assembler im CBM prg studio verhält sich so.
natürlich hast du prinzipiell recht, aber…
Als ich den Beitrag Ende 2013 geschrieben habe, hat sich das zu der Zeit aktuelle CBM prg Studio, wie im Text beschrieben, verhalten.
Erst mit der Version 3.3.0 wurde dies geändert:
Bugs Fixed:
Assembler:
Wrong rules for ifdef when variable is zero.
Um solchen Problemen auf die Spur zu kommen, bin ich auf die Mithilfe der Leser angewiesen.
Daher vielen Dank fürs Melden und ich habe den Text eben überarbeitet.
Gruß,
Jörn
Hallo Jörn,
in die Routine zum Löschen des Bildschirms hat sich ein kleiner Fehler eingeschlichen. Die 3. Page des Bildschirmspeichers muss mit “sta $0600,X” beschrieben werden und nicht mit “sta $0500,X”.
Schöne Grüße
Alex