Suche Assembler Routine für Multiplikation signed24bit * signed16bit(1.15)

[Gerhard (Gast)]

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

[Falk B. (falk)]

Muluwuw

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

[Christoph db1uq K. (christoph_kessler)]

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

[Gerhard (Gast)]

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

Mul_s16_s24:
'  r25:24 * r23:22:21 = r20:19:18:17:16
'  1. 16bit pos_neg testen
'  2. 24bit pos_neg testen

16_test:
        clt
        tst r25                         'prüfen ob negativ
        brpl 16_is_positiv
          com r25
          neg r24
          sbci r25,-1
          Set                          'T Flag im Statusregister
16_is_positiv:
'wenn 16bit = positiv --> T=0  'wenn 16bit = negativ --> T=1
24_test:
        tst r26                        'r26= MSB von 32bit(long)
        brpl 24_is_positiv             '3Byte Zahl negieren
          com r23
          com r22
          neg r21
          sbci r22,-1
            brts _end_pos_neg
            Set
            Rjmp _end_pos_neg  
24_is_positiv:
            brtc _end_pos_neg
            Set                
_end_pos_neg:

' Clear registers
        clr r16                         ' clear result registers
        clr r17
        clr r18
        clr r19
        clr r20
        clr r2                          ' clear help register
'; Multiply
        mul r25,r23                     '; term 1
        add r19,R0                      '; add to result
        adc r20,R1
        mul r25,r22                     '; term 2
        add r18,R0
        adc r19,R1
        adc r20,r2                      '; (add possible carry)
        mul r25,r21                     '; term 3
        add r17,R0
        adc r18,R1
        adc r19,r2
        adc r20,r2
        mul r24,r23                      '; term 4
        add r18,R0
        adc r19,R1
        adc r20,r2
        mul r24,r22                       '; term 5
        add r17,R0
        adc r18,R1
        adc r19,r2
        adc r20,r2
        mul r24,r21                        '; term 6
        add r16,R0
        adc r17,R1
        adc r18,r2
        adc r19,r2
        adc r20,r2
        ' Multiply done.
_zruck_wandeln:                             'wenn's T_flag g'setzt is ...
        brtc mul_t_flag
        com r20                                             
        com r19                                             
        com r18                                             
        com r17                                             
        neg r16                                             
        sbci r17,-1                                         
Mul_t_flag:
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:

'Test neg_pos
  clt
   tst r20
   brpl _r20_is_positiv
     ser r21
     rjmp _ende_r20_pos_neg
_r20_is_positiv:
     clr r21
_ende_r20_pos_neg:


'1 x Alles linksschieben , (wegen fract s.15)
lsl r16
rol r17
rol r18
rol r19
rol r20
'...und die unteren 2 Bytes vergessen ....(wegen fract s.15)
STS {s},R18
STS {s+1},R19
STS {s+2},R20
STS {s+3},R21

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

[Sebastian S. (amateur)]

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.

[Peter D. (peda)]

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.

[c-hater (Gast)]

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:

[Peter D. (peda)]

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.

[Gerhard (Gast)]

Hallo c-hater,

danke für den Code.
Hab den schon eingebaut , super.
Kleiner Hinweis: anstatt sbrc -->

sbrs faktor1msb,7

sbrs faktor2msb,7

BG Gerhard

[c-hater (Gast)]

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...

[eProfi (Gast)]

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

'; Multiply
    mul r24,r21  '; term 6
    movw R0,R16
    mul r24,r23  '; term 4
    movw R0,R18

    mul r24,r22  '; term 5
    add r17,R0   '; add to result
    adc r18,R1
    rol r2       '; save carry-flag
    mul r25,r23  '; term 1
    ror r2       '; restore carry-flag
    adc r19,R0   '; add to result
    adc r20,R1

    clr r2
    mul r25,r21  '; term 3
    add r17,R0   '; add to result
    adc r18,R1
    adc r19,R2
    adc r20,R2

    mul r25,r22  '; term 2
    add r18,R0   '; add to result
    adc r19,R1
    adc r20,R2
'; Multiply done.

[eProfi (Gast)]

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:

'; Multiply
    mul r24,r21  '; term 6
    movw R16,R0
    mul r24,r23  '; term 4
    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.

[eProfi (Gast)]

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.

[eProfi (Gast)]

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:

  rol r17    ';Bit7 ins Carry
  adc r18,r2 ';Carry in r18 addieren

[eProfi (Gast)]

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

[Steffen H. (avrsteffen)]

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