Forum: Mikrocontroller und Digitale Elektronik 80 Bit x 80 Bit auf dem AVR multiplizieren


von Sven P. (Gast)


Lesenswert?

Hi,

aus einem kleinen Projekt die Problemstellung: 80 Bit mal 80 Bit = 80 
Bit, auf einem AVR (klar, gehen unter Umständen Bits verloren, weil das 
Ergebnis nur 80 Bit breit ist).

Meine Ansätze wären da gewesen:
- Addierschleife -- Scherz, haha.

- Schieben und Addieren, wäre dann eine konstante Laufzeit, dazu 
bräuchte ich aber mindestens drei 80 Bit breite Register: Eines fürs 
Ergebnis und jeweils eines für die beiden Faktoren, die werden ja nach 
rechts bzw. links verschoben.

- zusammengesetzte Rechnung, also nach Schema (A1 * 265 + A2) * (B1 * 
265 + B2) und dann brav ausmultiplizieren -- ergäbe einen riesigen Code, 
aber machbar.

- Multiplikation nach Booth; bräuchte man wieder drei 2*80-Bit-Register 
und noch eines für das einsame Bit. Wobei man eines davon einsparen 
könnte, denn der AVR kann direkt subtrahieren.

Platz im Programmspeicher und SRAM ist genügend vorhanden, der 
Algorithmus kann gerne 2kB belegen.

Wie würdet ihr sowas realisieren, ungeachtet dessen, ob das nun 
weltfremd ist, oder eher nicht? :-)

Danke und viele Grüße,
Kama

von Helmut L. (helmi1)


Lesenswert?

Schau doch mal in der Codesammlung fuer AVR Arithmetik

http://www.mikrocontroller.net/articles/AVR_Arithmetik#24_Bit_.2A_24_Bit

Da habe ich mal eine Routine fuer 24 x 24 mit 48 Bit Ergebnis 
reingestellt.
Nach dem gleichen Schema kannst du das ganze dann fuer 80 Bit erweitern.

von Michael U. (amiga)


Lesenswert?

Hallo,

warum nicht ganz üblich?

80 Bit sind 11 Speicheradressen im Ram

11 + 11 + 22 (für das Ergebnis) = 44 Byte ram.

Multiplakationsroutine erweitern, X, Y, Z geschickt einsetzen.

32x32 Bit sind bei mir rund 30 Zeilen ASM.
1
;*********************************************************************
2
;  32*32 Bit Multiplikation In RX0...3, RY0...4, Out RX0...7
3
;
4
;  Scratch-Reg: -
5
;*********************************************************************
6
;--------------------------------------------------------------------
7
;-- RX[64] = RX[32] * RY[32]
8
;--------------------------------------------------------------------
9
mul32:
10
  push  TEMP_0
11
12
  clr    RX7
13
  clr    RX6
14
  clr    RX5
15
  sub    RX4,RX4        ; RX4=0, C=0
16
  ldi    TEMP_0,32+1      ; im ersten Durchlauf wird immer gesprungen
17
18
mul32_loop:
19
  brcc  mul32_noadd
20
21
  add    RX4,RY0
22
  adc    RX5,RY1
23
  adc    RX6,RY2
24
  adc    RX7,RY3
25
26
mul32_noadd:
27
  ror    RX7
28
  ror    RX6
29
  ror    RX5
30
  ror    RX4
31
  ror    RX3
32
  ror    RX2
33
  ror    RX1
34
  ror    RX0
35
36
  dec    TEMP_0
37
  brne  mul32_loop
38
39
  pop    TEMP_0
40
41
  ret

Gruß aus Berlin
Michael

von spess53 (Gast)


Lesenswert?

Hi

AppNote AVR201

http://www.atmel.com/dyn/resources/prod_documents/doc1631.pdf

Lässt sich eigentlich beliebig erweitern.

MfG Spess

von Sven P. (Gast)


Lesenswert?

Helmut:
Genauso sieht mein dritter Vorschlag aus -- das artet halt insofern 
etwas aus, als dass es dann 100 Multiplikationen sind ;-)

Michael U. schrieb:
> Hallo,
>
> warum nicht ganz üblich?
>
> 80 Bit sind 11 Speicheradressen im Ram
> [...]
Und dann klassisches Schieben und Addieren, oder wie stellst du dir den 
konkreten Algorithmus vor?

von Unbekannter (Gast)


Lesenswert?

Was ist der Sinn, 80Bit x 80bit zu multiplizieren, wenn das Resultat nur 
80 Bit breit ist? Entweder 160Bit für das Resultat benutzen, was dann 
auch stimmt, oder man kann den 80bit im Multiplikator zuvor die 
hintersten 40 Bit wegschneiden, da die sowieso wegfallen.
Zur Multiplikation dann den Hardwaremultiplier und Karatsuba Algorithmus 
benutzen, geht vermutlich am schnellsten.

von Sven P. (Gast)


Lesenswert?

spess53 schrieb:
> Hi
>
> AppNote AVR201
>
> http://www.atmel.com/dyn/resources/prod_documents/doc1631.pdf
>
> Lässt sich eigentlich beliebig erweitern.
Hm, den hab ich überlesen -- aber ja, da fällt so langsam ein Groschen 
bei mir :-)

von Martin (Gast)


Lesenswert?

... 80 Bit sind 11 Speicheradressen im Ram ...

Wie kommst du denn auf dieses putzige Idee?

von Sven P. (Gast)


Lesenswert?

Aber noch eine Überlegung, die mir gerade in den Sinn kommt:
Wenn es sich bei den 80 Bit um Festkommazahlen handelt, muss ja 
anschließend noch zurückgeschoben (geteilt) werden, wobei einige 
Nachkommastellen flöten gehen.

Sehe ich das dann richtig, dass etwa der kleinste Term im Produkt (quasi 
LSB * LSB, B=Byte) sich nur noch über das Carry-Flag aufs Ergebnis 
auswirken kann?

von Sven P. (Gast)


Lesenswert?

Michael U. schrieb:
> 32x32 Bit sind bei mir rund 30 Zeilen ASM.
> [...]
Statt den Faktor zu schieben, lieber das Ergebnis rotieren. Das werde 
ich mir näher ansehen, danke!

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Sven P. schrieb:
> Michael U. schrieb:
>> Hallo,
>>
>> warum nicht ganz üblich?
>>
>> 80 Bit sind 11 Speicheradressen im Ram
>> [...]
> Und dann klassisches Schieben und Addieren, oder wie stellst du dir den
> konkreten Algorithmus vor?

80/8 sind immer noch 10 ;-)

Man rechnet ganz einfach Ziffernweise. Wenn ein HW-Multiplikator 
verfügbar ist, etwa 8*8=16, dann ist die sinnigste Zifferngröße 1 Byte.

Für 10*10 Bytes ist jedes mit jedem zu multiplizieren, das sind 55 
Multiplikationen a[i]*b[j], die ab c[i+j] aufzuaddieren sind mit
i=0..9
j=0..9
i+j <= 9

Hier kann Arbeit bei der Addition gespart werden, indem man 
Teilsummenden bildet: bei
1
a[0]*b[0]*B^0 + a[0]*b[2]*B^2 + a[0]*b[4]*B^4 +...
mit der Basis B (hier 256) gibt es keine Überläufe von einer 
Doppelziffer (B^2) zur nächsten. Dito für
1
a[1]*b[0]*B^1 + a[1]*b[2]*B^3 + a[1]*b[4]*B^5 +...
etc.

...und das alles natürlich in einer Schleife, nicht explizit austexten 
:-)

Falls kein Multiplikationsbefehl vorhanden ist, geht es wohl am 
komfortabelsten mit B=2, d.h. Schulmultiplpikation und -addition auf 
Binärebene.

von Martin (Gast)


Lesenswert?

... Für 10*10 Bytes ist jedes mit jedem zu multiplizieren, das sind 55
Multiplikationen ...

Hier ein Beipsiel mit 3 'Bytes' x 3 'Bytes'. Das sind 9 
Multiplikationen.

10 Bytes x 10 Bytes sind 100 Multiplikationen.


   123 * 456
  -----------
        12
        8
       4
         15
        10
        5
          18
         12
         6
  --------------
       56088

von magnetus (Gast)


Lesenswert?

Martin schrieb:
> ... Für 10*10 Bytes ist jedes mit jedem zu multiplizieren, das sind 55
> Multiplikationen ...

Martin schrieb:
> 10 Bytes x 10 Bytes sind 100 Multiplikationen.

Wat denn nu?  ;o)

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

magnetus schrieb:

> Wat denn nu?  ;o)

Braucht man im Ergebnis nur 10 Bytes -> 55
Braucht man im Ergebnis alle 20 Bytes -> 100

von Nobody (Gast)


Lesenswert?

@  Sven P.
Mal ne Frage: Welche von den 160 Ergebnisbits brauchst Du denn?

von Crest (Gast)


Lesenswert?

Martin schrieb:
> ... 80 Bit sind 11 Speicheradressen im Ram ...
>
> Wie kommst du denn auf dieses putzige Idee?

Na ist klar Ints sind doch nullterminiert ;-)

von Martin (Gast)


Lesenswert?

...
Für 10*10 Bytes ist jedes mit jedem zu multiplizieren, das sind 55
Multiplikationen a[i]*b[j], die ab c[i+j] aufzuaddieren sind mit
i=0..9
j=0..9
...

Du schreibst zwar von 55 Multiplikationen, dein 'Algorithmus' umfasst 
jedoch 100 Multiplikationen, da i und j von 0 bis 9 laufen und die 
Multiplikation a[i]*b[j] ausgeführt wird.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Martin schrieb:
> ...
> Für 10*10 Bytes ist jedes mit jedem zu multiplizieren, das sind 55
> Multiplikationen a[i]*b[j], die ab c[i+j] aufzuaddieren sind mit
> i=0..9
> j=0..9
> ...
>
> Du schreibst zwar von 55 Multiplikationen, dein 'Algorithmus' umfasst
> jedoch 100 Multiplikationen, da i und j von 0 bis 9 laufen und die
> Multiplikation a[i]*b[j] ausgeführt wird.

Da steht dann noch ein "i+j <= 9". Wenn schon zitieren, dann nicht das 
wegsnippen, was dann angemäkelt wird ;-)

...und es ist kein Algorithmus, sondern lediglich eine Skizze dessen.

von Martin (Gast)


Lesenswert?

Prinzipiell kann man die Multiplikationen nur sparen, wenn man 
ausschließlich die 'unteren' 80 Bits berechnet, so wie das bei einer 16 
Bit Integer Multiplikation gemacht wird: die 4 Bytes der Multiplikation 
ab x cd erfordern zwar für ein 32 Bit Ergebnis 4 Teilmultiplikationen, 
da die Teilmultiplikation a x c immer ein Ergebnis größer 16 Bit hat, 
lässt man sie weg und kommt mit 3 Multiplikationen aus.

von Martin (Gast)


Lesenswert?

... und es ist kein Algorithmus, sondern lediglich eine Skizze dessen 
...

... Da steht dann noch ein "i+j <= 9". Wenn schon zitieren, dann nicht 
das
wegsnippen, was dann angemäkelt wird ...


Johann - bist du tatsächlich so boniert?

EOT

von Peter D. (peda)


Lesenswert?

Kommt drauf an, ob der AVR ein ATtiny oder ATmega ist.

Beim ATtiny geht der Klassiker: Schieben und addieren.
Du brauchst 31 Register, also überhaupt kein Problem.

Man kann dann noch optimieren. Wenn das Ergebnis nur 80 Bit sein darf, 
muß ein Faktor kleiner 40 Bit sein. D.h. Du brauchst nur ne 40*80=80Bit 
Multiplikation. Davor testen und gegebenenfalls die Faktoren 
vertauschen.

Bei den ATmega kann man auch den Multiplikationsbefehl benutzen. Der 
Code wird schneller, aber auch größer.


Peter

von magnetus (Gast)


Lesenswert?

Peter Dannegger schrieb:
> Man kann dann noch optimieren. Wenn das Ergebnis nur 80 Bit sein darf,
> muß ein Faktor kleiner 40 Bit sein. D.h. Du brauchst nur ne 40*80=80Bit
> Multiplikation.

Das verstehe ich jetzt nicht...

Beispiel: FFFFFFFFFF * 0002 = 1FFFFFFFFFE
            80 Bit     16 Bit    81 Bit

Gruß,
Magnetus

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

magnetus schrieb:
> Peter Dannegger schrieb:
>> Man kann dann noch optimieren. Wenn das Ergebnis nur 80 Bit sein darf,
>> muß ein Faktor kleiner 40 Bit sein. D.h. Du brauchst nur ne 40*80=80Bit
>> Multiplikation.
>
> Das verstehe ich jetzt nicht...
>
> Beispiel: FFFFFFFFFF * 0002 = 1FFFFFFFFFE
>             80 Bit     16 Bit    81 Bit

Peter sagt, daß wenn man weiß, daß kein Überlauf auftreten wird, 
mindestens einer der Faktoren höchstens 40 Bit haben kann.

In deinem Fall ist aber ein Überlauf aufgetreten (Falls "F" für 10 Bits 
steht).

von Peter D. (peda)


Lesenswert?

magnetus schrieb:
> Das verstehe ich jetzt nicht...

Ganz einfach, wenn beide 41bit groß sind, gibts einen Überlauf und das 
Ergebnis ist ungültig.
Also lohnt es sich nicht, 41*41Bit zu rechnen, es kann nie in 80 Bit 
passen.


Peter

von Sven P. (Gast)


Lesenswert?

Verzeihung für die späte Antwort.

Nun, für einen ganz konkreten Fall:
- Prozessor hat Multiplikationsbefehl (ATmega)
- Zahlen liegen als 80-Bit-Festkommazahlen vor und das Ergebnis soll 
auch derart herauskommen, dabei S40.40, also vorzeichenbehaftet und 
jeweils 40 Bits vor- und nach dem Komma.

Das mit dem Vorzeichen dürfte kein Problem sein, zumindest klappt meine 
Negieren-Funktion hervorragend :->

Meine Vermutung wäre dann: Wenigstens der kleinste Term, also das 
Produkt der beiden LSB (B=Bytes), kann sich nur noch über das Carry aufs 
Endergebnis auswirken, da die beiden Ergebnisbytes selbst ohnehin im 
Anschluss an die Multiplikation weggeschoben werden.

von Peter D. (peda)


Lesenswert?

Sven P. schrieb:
> - Zahlen liegen als 80-Bit-Festkommazahlen vor und das Ergebnis soll
> auch derart herauskommen, dabei S40.40, also vorzeichenbehaftet und
> jeweils 40 Bits vor- und nach dem Komma.

Dann müssen beide Faktoren aber immer als S60.20 vorliegen.
Ich würde die Zahlen der Einfachheit halber erstmal als Ganzzahl ansehen 
und erst zum Schluß die Skalierung vornehmen.


Peter

von Sven P. (Gast)


Lesenswert?

Peter Dannegger schrieb:
> Sven P. schrieb:
>> - Zahlen liegen als 80-Bit-Festkommazahlen vor und das Ergebnis soll
>> auch derart herauskommen, dabei S40.40, also vorzeichenbehaftet und
>> jeweils 40 Bits vor- und nach dem Komma.
>
> Dann müssen beide Faktoren aber immer als S60.20 vorliegen.
So?

Meine Auffassung davon war bisher: 40.40 x 40.40 ergibt 80.80, das muss 
ich dann nach rechts schieben, sodass 40 Nachkommastellen flöten gehen. 
Einen Überlauf produziert es, wenn die oberen 40 Bits vor dem Komma 
nicht allesamt Null sind.

Oder missverstehe ich das?

von Peter D. (peda)


Lesenswert?

Sven P. schrieb:
> Meine Auffassung davon war bisher: 40.40 x 40.40 ergibt 80.80, das muss
> ich dann nach rechts schieben, sodass 40 Nachkommastellen flöten gehen.

Hängt eben davon ab, wo Du abschneidest.
Dann muß man aber immer beachten, daß man nicht auch unten zuviel 
abschneidet.

Ich finds einfacher, immer nur oben abzuschneiden und einzuschätzen, daß 
man keinen Überlauf macht.
Jedesmal Überlauf und Unterlauf beachten zu müssen, ist mir zu 
aufwendig.


Peter

von Sven P. (Gast)


Lesenswert?

Naja, was will ich machen?

Das Dingen werkelt in einer Art 'Taschenrechner', soll also einen 
möglichst breiten, aber wenigstens definierten Zahlenbereich erschlagen.

Setz ich da S40.40, dann ist das von der Auflösung ausreichend genau 
(daher ists kein großer Verlust, wenn das Ergebnis der Multiplikation 
auf von .80 auf .40 gerundet wird), und von der Magnitute sind 40 Bit 
vor dem Komma ebenfalls ausreichend.

Vorallem aber rechnets immer gleichbleibend (=absehbar) genau.

von Peter D. (peda)


Lesenswert?

Sven P. schrieb:
> Das Dingen werkelt in einer Art 'Taschenrechner'

Dann ist ja die Eingabezeit des Menschen der einzig limitierende Faktor.
D.h. Du könntest auch 800*800=1600Bit rechnen, ohne das es auffällt.


Peter

von Sven P. (Gast)


Lesenswert?

Peter Dannegger schrieb:
> Sven P. schrieb:
>> Das Dingen werkelt in einer Art 'Taschenrechner'
>
> Dann ist ja die Eingabezeit des Menschen der einzig limitierende Faktor.
> D.h. Du könntest auch 800*800=1600Bit rechnen, ohne das es auffällt.
Ja natürlich, aber dafür müsste ich mir erstmal vollkommen klar werden, 
wie ich das bewerkstellige :-D

Sollte dann mal CORDIC o.ä. dazukommen, sieht das wieder anders aus, 
wenn man Resultate in endlicher Zeit erwarten möchte.
Ist halt mal eine Konzeptstudie.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Am naheliegendsten ist doch, die Multiplikation als 40.40*40.40 = 40.80 
auszuführen und die Nachkommastellen, die nicht in .40 reinpassen, 
wegzuwerfen (evtl. nach Rundung). Was am MSB überläuft wird weggeworfen 
bzw. zur Überlauferkennung verwendet.

Sooo zeitkritisch ist das alles ja nicht, und wenn sich später 
rausstellt, daß es zu zäh ist weil es durch darauf aufbauende Funktionen 
wie log, sin, ... sehr oft aufgerufen wird, lässt sich immer noch 
Optimierungspotential ausnutzen.

Zuerst geht's also um eine einfache Implementierung der 
Schul-Multiplikation.

von Sven P. (Gast)


Lesenswert?

Johann L. schrieb:
> Am naheliegendsten ist doch, die Multiplikation als 40.40*40.40 = 40.80
> auszuführen und die Nachkommastellen, die nicht in .40 reinpassen,
> wegzuwerfen (evtl. nach Rundung). Was am MSB überläuft wird weggeworfen
> bzw. zur Überlauferkennung verwendet.
Ganz genau das habe ich vor.

> Zuerst geht's also um eine einfache Implementierung der
> Schul-Multiplikation.
Ich hab einfach mal die Lösung von Michael U. (amiga) implementiert, das 
funktioniert soweit.
Das 10-Byte-Register für den ersten Faktor habe ich mit weiteren 10 
Bytes aufgeblasen (gesichert auf dem Stack), so ists zugleich das 
temporäre Ergebnisregister. Den zweiten Faktor lade ich bei jedem der 80 
Durchläufe direkt aus dem SRAM.
Im Anschluss an die Schleife schiebe ich das temporäre Ergebnis um 5 
Bytes nach rechts, so gehen die kleinen Nachkommastellen flöten. Zuletzt 
wird geprüft, ob eines der oberen fünf Bytes ungleich Null ist, was dann 
durch das Carry-Flag als Überlauf angezeigt wird.

Laut Simulator macht das nun 276,4 Mikrosekunden pro Multiplikation, 
also locker 3,5kOp/s.
Mal sehen, ob ich noch einen der intelligenteren Vorschläge hier 
umgesetzt bekomme :->

von Sven P. (Gast)


Lesenswert?

Soderle, der Multiplizierer funktioniert scheinbar jetzt.
Ich habe Eure Vorschläge allesamt mal ausprobiert und bin dann beim 
Booth-Algorithmus hängen geblieben. Der liefert mit 80x80 Bit nun in 
rund 200 Mikrosekunden (16 MHz), also in etwa 3200 Takten.

Wenn ich das Dingen etwas aufgeräumt habe, stell ichs in die 
Codesammlung.

Die Appnote von Atmel (AVR200) enthält noch eine Bemerkung: Der 
Booth-Algorithmus soll versagen, wenn der erster Faktor ('multiplicand') 
der betragsmäßig größten negativen Zahl entspricht.
Woher diese Beschränkung? In meinen Büchern habe ich solch eine Warnung 
nämlich nicht gefunden --

Ich kann mir das bisher nur so erklären:
Der Booth-Algorithmus arbeitet ja nur mit Additionen, entsprechend 
verlangt er nach einer Zweierkomplement-Darstellung ('die zweite 
Zeile'), um zu subtrahieren. Nur das geht natürlich schief, da die 
betragsmäßig größte negative Zahl im Zweierkomplement bei fester 
Stellenzahl nicht negiert werden kann, da sie sonst überläuft.
Das Problem dürfte ich dann umgehen können, indem ich nicht das 
Zweierkomplement bilde und addiere, sondern den Subtrahier-Befehl 
verwende, ja?

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Sven P. schrieb:
> Das Problem dürfte ich dann umgehen können, indem ich nicht das
> Zweierkomplement bilde und addiere, sondern den Subtrahier-Befehl
> verwende, ja?

Zweierkomplement addieren oder originalen Wert abziehen bringt das 
gleiche Ergebnis, auch für 0x80...

Eher ist das Problem, das 0x80=-0x80 (bei 8 Bit, für mehr Bits analog). 
Demnach ist x+0x80 = x-0x80.

Btw: So wie ich Booth verstehe, arbeitet der auf der Binärdarstellung 
durch Zusammenfassen von Gruppen gleicher Bits. Intuitiv würd ich sagen, 
daß ne normale Schul-Multiplikation schneller ist, wenn man die 
MUL-Befehle von AVR verwendet. Und der Implementierung wird wohl auch 
übersichtlicher...offenbar tippst du in Assembler...

von Sven P. (Gast)


Lesenswert?

Johann L. schrieb:
> Sven P. schrieb:
>> Das Problem dürfte ich dann umgehen können, indem ich nicht das
>> Zweierkomplement bilde und addiere, sondern den Subtrahier-Befehl
>> verwende, ja?
>
> Zweierkomplement addieren oder originalen Wert abziehen bringt das
> gleiche Ergebnis, auch für 0x80...
Muss ich nochmal überdenken.

> Btw: So wie ich Booth verstehe, arbeitet der auf der Binärdarstellung
> durch Zusammenfassen von Gruppen gleicher Bits. Intuitiv würd ich sagen,
> daß ne normale Schul-Multiplikation schneller ist, wenn man die
> MUL-Befehle von AVR verwendet. Und der Implementierung wird wohl auch
> übersichtlicher...offenbar tippst du in Assembler...
Naja, dann programmier mal eine Schulmultiplikation mit 10x10 Bytes :-/

Aktueller Zustand, spaßeshalber mal in voller Schönheit im Text und 
nicht im Anhang:
1
; Multiplication
2
; W <-- W * [Y]
3
; Implemented using Booth's algorithm, according to ATMEL
4
; AVR Application Note #200.
5
mul80:
6
  push  TI
7
  push  Q0
8
  push  Q1
9
  push  Q2
10
  push  Q3
11
  push  Q4
12
  push  Q5
13
  push  Q6
14
  push  Q7
15
  push  Q8
16
  push  Q9    ; Second factor
17
  push  S0
18
  push  S1
19
  push  S2
20
  push  S3
21
  push  S4
22
  push  S5
23
  push  S6
24
  push  S7
25
  push  S8
26
  push  S9    ; High result
27
28
  ldd  Q0, Y+0
29
  ldd  Q1, Y+1
30
  ldd  Q2, Y+2
31
  ldd  Q3, Y+3
32
  ldd  Q4, Y+4
33
  ldd  Q5, Y+5
34
  ldd  Q6, Y+6
35
  ldd  Q7, Y+7
36
  ldd  Q8, Y+8    ; Load second factor
37
  ldd  Q9, Y+9    ; Do not overwrite YH:YL!
38
39
  clr  S0
40
  clr  S1
41
  clr  S2
42
  clr  S3
43
  clr  S4
44
  clr  S5
45
  clr  S6
46
  clr  S7
47
  clr  S8
48
  sub  S9, S9    ; S9 = 0, carry flag = 0
49
  
50
  ldi  TI, 80
51
52
mul80_loop:
53
  bst  W0, 0
54
  brcc  mul80_noadd  ; Add if second-to-last bit set
55
  brts  mul80_nosub  ; But do nothing if last bit set, too
56
57
  add  S0, Q0
58
  adc  S1, Q1
59
  adc  S2, Q2
60
  adc  S3, Q3
61
  adc  S4, Q4
62
  adc  S5, Q5
63
  adc  S6, Q6
64
  adc  S7, Q7
65
  adc  S8, Q8
66
  adc  S9, Q9
67
68
mul80_noadd:
69
  brtc  mul80_nosub  ; Subtract if last bit set
70
71
  sub  S0, Q0
72
  sbc  S1, Q1
73
  sbc  S2, Q2
74
  sbc  S3, Q3
75
  sbc  S4, Q4
76
  sbc  S5, Q5
77
  sbc  S6, Q6
78
  sbc  S7, Q7
79
  sbc  S8, Q8
80
  sbc  S9, Q9
81
82
mul80_nosub:
83
  asr  S9    ; Sign extension
84
  ror  S8
85
  ror  S7
86
  ror  S6
87
  ror  S5
88
  ror  S4
89
  ror  S3
90
  ror  S2
91
  ror  S1
92
  ror  S0
93
  ror  W9
94
  ror  W8
95
  ror  W7
96
  ror  W6
97
  ror  W5
98
  ror  W4
99
  ror  W3
100
  ror  W2
101
  ror  W1
102
  ror  W0
103
104
  dec  TI
105
  brne  mul80_loop
106
107
108
  mov  W0, W5
109
  mov  W1, W6
110
  mov  W2, W7
111
  mov  W3, W8
112
  mov  W4, W9
113
  mov  W5, S0
114
  mov  W6, S1
115
  mov  W7, S2
116
  mov  W8, S3
117
  mov  W9, S4    ; Adjust result
118
119
  clv
120
  cpse  S5, TI    ; TI = 0 from loop
121
  sev
122
  cpse  S6, TI
123
  sev
124
  cpse  S7, TI
125
  sev
126
  cpse  S8, TI
127
  sev
128
  cpse  S9, TI
129
  sev      ; Test overflow
130
131
  pop  S9
132
  pop  S8
133
  pop  S7
134
  pop  S6
135
  pop  S5
136
  pop  S4
137
  pop  S3
138
  pop  S2
139
  pop  S1
140
  pop  S0
141
  pop  Q9
142
  pop  Q8
143
  pop  Q7
144
  pop  Q6
145
  pop  Q5
146
  pop  Q4
147
  pop  Q3
148
  pop  Q2
149
  pop  Q1
150
  pop  Q0
151
  pop  TI
152
  ret

Bei ersten Tests funktionierte das, ich werde aber noch genauer 
hinschauen.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.