Forum: Mikrocontroller und Digitale Elektronik Suche Assembler Routine für Multiplikation signed24bit * signed16bit(1.15)


von Gerhard (Gast)


Lesenswert?

Hallo Leute ,

wie im Betreff schon geschrieben suche ich eine
Assembler Routine für eine Multiplikation
signed24bit oder signed32bit Zahl * signed16bit(1.15)fractional
Laufen soll das ganze mal auf einem AVR m328 ,
also mit Hilfe des Hardware multiplier.
Danke für jede Hilfe bzw. Tipps ...

BG Gerhard

von Falk B. (falk)


Lesenswert?

Muluwuw

Keine Ahnung ob dir das was nützt ;-)

von Christoph db1uq K. (christoph_kessler)


Lesenswert?

https://www.mikrocontroller.net/articles/AVR_Arithmetik#Multiplikation
bis zu "Signed Multiply von 2 24Bit breiten Zahlen mit 48Bit Ergebnis"

ohne Hardware-Multiplier, von 1999-2002 für den AVR 8515:
http://avr-asm.tripod.com/math32x.html

: Bearbeitet durch User
von Gerhard (Gast)


Lesenswert?

Hallo,

danke für die Links.
Konnte aber nicht um's Verrecken eine Multiplikationsroutine  für 
vorzeichenbehaftete Zahlen finden:
Hier meine funktionierende "Lösung":
Hab eine u16*u24bit Routine im Netz gefunden (...danke) und um meinen 
Funktionswunsch erweitert.
Bitte nicht schimpfen :) , bin kein Assembler Profi.
Bin aber für Verbesserungsvorschläge sehr dankbar.
Code ist für Bascom Inline Assembler.
Hier die Multiplikationsroutine für signed16bit * signed24bit
1
Mul_s16_s24:
2
'  r25:24 * r23:22:21 = r20:19:18:17:16
3
'  1. 16bit pos_neg testen
4
'  2. 24bit pos_neg testen
5
6
16_test:
7
        clt
8
        tst r25                         'prüfen ob negativ
9
        brpl 16_is_positiv
10
          com r25
11
          neg r24
12
          sbci r25,-1
13
          Set                          'T Flag im Statusregister
14
16_is_positiv:
15
'wenn 16bit = positiv --> T=0  'wenn 16bit = negativ --> T=1
16
24_test:
17
        tst r26                        'r26= MSB von 32bit(long)
18
        brpl 24_is_positiv             '3Byte Zahl negieren
19
          com r23
20
          com r22
21
          neg r21
22
          sbci r22,-1
23
            brts _end_pos_neg
24
            Set
25
            Rjmp _end_pos_neg  
26
24_is_positiv:
27
            brtc _end_pos_neg
28
            Set                
29
_end_pos_neg:
30
31
' Clear registers
32
        clr r16                         ' clear result registers
33
        clr r17
34
        clr r18
35
        clr r19
36
        clr r20
37
        clr r2                          ' clear help register
38
'; Multiply
39
        mul r25,r23                     '; term 1
40
        add r19,R0                      '; add to result
41
        adc r20,R1
42
        mul r25,r22                     '; term 2
43
        add r18,R0
44
        adc r19,R1
45
        adc r20,r2                      '; (add possible carry)
46
        mul r25,r21                     '; term 3
47
        add r17,R0
48
        adc r18,R1
49
        adc r19,r2
50
        adc r20,r2
51
        mul r24,r23                      '; term 4
52
        add r18,R0
53
        adc r19,R1
54
        adc r20,r2
55
        mul r24,r22                       '; term 5
56
        add r17,R0
57
        adc r18,R1
58
        adc r19,r2
59
        adc r20,r2
60
        mul r24,r21                        '; term 6
61
        add r16,R0
62
        adc r17,R1
63
        adc r18,r2
64
        adc r19,r2
65
        adc r20,r2
66
        ' Multiply done.
67
_zruck_wandeln:                             'wenn's T_flag g'setzt is ...
68
        brtc mul_t_flag
69
        com r20                                             
70
        com r19                                             
71
        com r18                                             
72
        com r17                                             
73
        neg r16                                             
74
        sbci r17,-1                                         
75
Mul_t_flag:
76
ret

Das Ergebnis liegt nun in r20:r19:r18:r17:r16
Ich brauche den Integer Teil als vorzeichenbehaftete 4Byte Zahl.
(In Bascom als "Long")
Hier meine Umwandlung:
1
'Test neg_pos
2
  clt
3
   tst r20
4
   brpl _r20_is_positiv
5
     ser r21
6
     rjmp _ende_r20_pos_neg
7
_r20_is_positiv:
8
     clr r21
9
_ende_r20_pos_neg:
10
11
12
'1 x Alles linksschieben , (wegen fract s.15)
13
lsl r16
14
rol r17
15
rol r18
16
rol r19
17
rol r20
18
'...und die unteren 2 Bytes vergessen ....(wegen fract s.15)
19
STS {s},R18
20
STS {s+1},R19
21
STS {s+2},R20
22
STS {s+3},R21

[MOD: bitte beim nächsten Mal eigenständig die avrasm Tags verwenden. 
Siehe "Wichtige Regeln - erst lesen, dann posten!"]

: Bearbeitet durch Moderator
von Sebastian S. (amateur)


Lesenswert?

Als ich das letzte Mal bei AVRs zuhause war, wurde ich mit 
Beispielroutinen regelrecht erschlagen. Ist das seit MicroChip nicht 
mehr so?
Den jeweiligen Ansatz kann man aber auch in jede andere, 
prozessorspezifische Sprache übersetzen. Natürlich nur, wenn man den 
Befehlssatz kennt.

von Peter D. (peda)


Lesenswert?

Gerhard schrieb:
> Konnte aber nicht um's Verrecken eine Multiplikationsroutine  für
> vorzeichenbehaftete Zahlen finden:

Hat das Ergebnis die gleiche Breite, wie die Operanden, dann spielt das 
Vorzeichen keine Rolle. Der Fehler tritt erst in den höherwertigen Bits 
auf.

von c-hater (Gast)


Lesenswert?

Peter D. schrieb:

> Hat das Ergebnis die gleiche Breite, wie die Operanden, dann spielt das
> Vorzeichen keine Rolle. Der Fehler tritt erst in den höherwertigen Bits
> auf.

Das ist korrekt, aber auch C, wie es leibt und lebt. Praktisch ziemlich 
unbrauchbar. Denn natürlich braucht man auch für diesen Fall wenigstens 
eine zuverlässige Information, dass der mögliche Zahlenbereich des 
Ergebnisses verlassen wurde...

In Asm ist es jedenfalls ziemlich einfach (und nicht allzu teuer), 
das/die störenden Vorzeichen vor der eigentlichen Multiplikation mit der 
vollen Bitbreite zu eleminieren und hinterher wieder einzufügen. Man 
braucht nur ein einziges Bit, um die Information über die eigentliche 
Multiplikation hinweg zu retten, wofür sich natürlich das T-Flag 
anbietet.

Der worst case ist, dass ein Faktor und das Produkt negiert werden 
müssen. Dafür braucht man aber für die eigentliche Multiplikation nur 
eine Inkarnation (das ist besonders relevant für Targets ohne 
Hardware-Multiplikation, erleichtert es aber auch für Targets mit 
selbiger, denn da entfällt in der Multiplikation selber immerhin etwas 
Overhead und die Wahl der Register ist freier, was den Verlust durch die 
evtl. nötigen Negationen vor und nach der Multiplikation zumindest zum 
Teil kompensiert).

Wie auch immer, grundsätzlich ist die Struktur so:

 mov tmp, faktor1msb
 xor tmp, faktor2msb
 bst tmp,7             ;save result sign in T-Flag
 sbrc faktor1msb,7
 rjmp chkfaktor2
 [negate faktor1]
chkfaktor2:
 sbrc faktor2msb,7
 rjmp mulu
 [negate faktor2]
mulu:
 [perform the unsigned multiplikation]
 btrc done            ;check result sign
 [negate the product]
done:

von Peter D. (peda)


Lesenswert?

c-hater schrieb:
> Das ist korrekt, aber auch C, wie es leibt und lebt. Praktisch ziemlich
> unbrauchbar. Denn natürlich braucht man auch für diesen Fall wenigstens
> eine zuverlässige Information, dass der mögliche Zahlenbereich des
> Ergebnisses verlassen wurde...

Nenne mir auch nur einen Programmierer, der nach jedem Rechenschritt auf 
Überlauf prüft. Und was soll die CPU dann machen, anhalten?
Das Ergebnis ist in jedem Fall falsch.

Man macht daher beim Code planen eine Worst-Case Betrachtung, ob ein 
Überlauf möglich ist und begrenzt dann z.B. die Eingangswerte oder nimmt 
ein geeignetes Zahlenformat.

C wurde eben für den Praktiker geschrieben und nicht für Erbsenzähler.

Beitrag #6463729 wurde von einem Moderator gelöscht.
von Gerhard (Gast)


Lesenswert?

Hallo c-hater,

danke für den Code.
Hab den schon eingebaut , super.
Kleiner Hinweis: anstatt sbrc -->
1
sbrs faktor1msb,7
1
sbrs faktor2msb,7

BG Gerhard

von c-hater (Gast)


Lesenswert?

Gerhard schrieb:

> Kleiner Hinweis: anstatt sbrc -->
> sbrs faktor1msb,7
> sbrs faktor2msb,7

Jepp, das war falsch, außerdem auch:

> xor tmp, faktor2msb

muss natürlich heißen:

eor tmp, faktor2msb

Kommt davon, wenn man's einfach auf die Schnelle im Browser eintippt...

von eProfi (Gast)


Lesenswert?

die Multiplikation ist aber etwas altbacken, das geht besser:
Term1 und Term3 (oder Term2 und Term4) (oder Term4 und Term6) sind 
voneinander unabhängig, da braucht man nicht mehrfach addieren
Beitrag "Re: Rechnen mit AVR"
Beitrag "Re: Rechnen mit AVR"
hier:
'  r25:24 * r23:22:21 = r20:19:18:17:16
25x23 20:19 term1
25x22 19:18 term2
25x21 18:17 term3
24x23 19:18 term4
24x22 18:17 term5
24x21 17:16 term6
1
'; Multiply
2
    mul r24,r21  '; term 6
3
    movw R0,R16
4
    mul r24,r23  '; term 4
5
    movw R0,R18
6
7
    mul r24,r22  '; term 5
8
    add r17,R0   '; add to result
9
    adc r18,R1
10
    rol r2       '; save carry-flag
11
    mul r25,r23  '; term 1
12
    ror r2       '; restore carry-flag
13
    adc r19,R0   '; add to result
14
    adc r20,R1
15
16
    clr r2
17
    mul r25,r21  '; term 3
18
    add r17,R0   '; add to result
19
    adc r18,R1
20
    adc r19,R2
21
    adc r20,R2
22
23
    mul r25,r22  '; term 2
24
    add r18,R0   '; add to result
25
    adc r19,R1
26
    adc r20,R2
27
'; Multiply done.

von eProfi (Gast)


Lesenswert?

Der Code bezieht sich auf den Beitrag von Gerhard 03.11.2020 15:44
Habe aus dem Stegreif getippt und glatt die Register bei beiden MOVW 
vertauscht, daher ausgiebig testen :-)   Korrektur:
1
'; Multiply
2
    mul r24,r21  '; term 6
3
    movw R16,R0
4
    mul r24,r23  '; term 4
5
    movw R18,R0

Da der Inhalt von R2 beim Carry-Save-rol-r2 egal ist, kann der erste clr 
r2 (vor '; Multiply) entfallen, damit ist der Code um 27-21=6 Befehle 
kürzer und schneller.

von eProfi (Gast)


Lesenswert?

Es sind sogar 10 Befehle weniger, da man auch R16-R19 nicht löschen 
muss, nur R20. Und wenn der MUL das Carry in Ruhe lassen würde, wären es 
nochmal 2 weniger.

von eProfi (Gast)


Lesenswert?

Weitere Befehle lassen sich einsparen durch:
-- Weglassen von Term6, da die unteren beiden Bytes in dieser Anwendung 
nicht ins Endergebnis eingehen (nur ein evtl. Überlauf daraus -> geringe 
Ungenauigkeit)
-- Verwendung von MULS (signed), FMUL (fractional) und/oder FMULS

dafür lieber 2 Befehle zum (Auf-)Runden investieren:
nach den MULS und ADDs:
1
  rol r17    ';Bit7 ins Carry
2
  adc r18,r2 ';Carry in r18 addieren

von eProfi (Gast)


Angehängte Dateien:

Lesenswert?

Weil's thematisch dazupasst:
Im Anhang eine unsigned 40x40=80-bit-Multiplikation in 140 Cycles 
(Takten, Taktzyklen), mit Beispiel.

von Steffen H. (avrsteffen)


Lesenswert?

Ich habe mich auch schon mit diesem Thema neulich beschäftigt und einen 
Artikel angelegt.
[https://www.mikrocontroller.net/articles/Multiplikation_in_Assembler]

Ist ja gerade wieder/noch aktuell.

MfG Steffen

: Bearbeitet durch User
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.