16Bit x 16Bit = 32Bit schnelle Multiplikation für 8Bit AVR in C

[Alexander E. (alex-rt)]

Hier ein C-Code für die Multiplikation von 16Bit Zahlen und als Ergebnis 
erhält man eine 32Bit Zahl:
uint32_t mul16(uint16_t, uint16_t) ersetzt folgenden Ausdruck:
32Bit = 16Bit * 16Bit
Mit Optimierung -0s dauert die Multiplikation 37 Taktzyklen (inklusive 
pop und push der Register). Der Quellcode enthält Inline-Assembler 
Anteile, was die Multiplikatin beschleunigt.
Damit ist es mögliche alle Arten von Zahlen (Ganzzahl und 
Fließkommahzahlen bis 255) zu rechnen die 16Bit brauchen.
Um Fließkommazahlen zu multiplieren müssen diese natürlich erst ins 
Binäre umgerechnet werden. Dies wird so durchgeführt:
Den Ganzzahlligen Dezimalwert in die oberen 8Bit hineinschreiben und den 
Dezimalen Kommawert mit 2^8 multiplizieren und diesen Wert in die 
unteren 8Bit hinein schreiben. Anschließend steht im 32Bit Ergebnis in 
den oberen 16Bit die Ganzzahl und in den unteren 16Bit die Kommazahl. 
Der Kommawert ist aber nicht Dezimal. Dieser wird Dezimal dadurch 
dargestellt, dass der Kommawert mit 1/(2^16) multipliziert wird.
Als Beispiel: Die Zahl 1,1 gibt in Hex: 0x0119 = 1 im oberen Byte und 25 
im niederen Byte.
Dadurch hat man zwar eine Auflösung von nur 0,0039 in Dezimal, aber für 
viele Regelungstechnische Aufgaben oder Filter reicht es aus. Da hier 
die Geschwindigkeit im vordergrund steht.
Verbesserungen und Optimierungen sind erwünscht.
Gruß Alex.

[Johann L. (gjlayde)]

Hi, das ist so nicht korrekt, weil Register verändert werden, von denen 
der Compiler nix mitbekommt.

Ausserdem übergibst Du besser die Werte wie sie sind ohne sie von Hand 
zu zerbröseln, also

[erg] "+r" (res.wert32)   // Zugriff mit %A[erg], %B[erg], ...

ist zudem besser lesbar als Operanden-Nummern.

[Johann L. (gjlayde)]

...und noch ein Fehler: R1 muss am Ende auf 0 gesetzt werden!

[Johann L. (gjlayde)]

Ich denke es muss heissen

adc %C0,R1

anstatt

add %C0,R1

[Alexander E. (alex-rt)]

Danke für den Hinweis.
Hier ist die korrigierte Version.

[Johann L. (gjlayde)]

Ok, nur noch ein Schönheitsfehler:

result ist uninitialisierte Eingabe von asm, eigentlich sollte gcc das 
anwarnen. Die korrekte Out-Constraint ist hier "=&r" und nicht "+r".

[Alexander E. (alex-rt)]

Danke für den Tip. Im Anhang ist die neue multi16.c
Dadurch ist nur ein schreiben der Register möglich.
Während "+r" für Ein- und Ausgabe dient.
Gruß Alex

[Johann L. (gjlayde)]

Oder gleich in avr-gcc einbauen :-)

(define_insn "umulhisi3"
  [(set (match_operand:SI 0 "register_operand" "=&r")
        (mult:SI (zero_extend:SI (match_operand:HI 1 "register_operand" "r"))
                 (zero_extend:SI (match_operand:HI 2 "register_operand" "r"))))]
  "AVR_HAVE_MUL && !(optimize_size)"
  "mul %B1,%B2
   movw %C0,r0
   mul %A1,%A2
   movw %A0,r0
   mul %B1,%A2
   add %B0,r0
   adc %C0,r1
   clr __zero_reg__
   adc %D0,__zero_reg__
   mul %A1,%B2
   add %B0,r0
   adc %C0,r1
   clr __zero_reg__
   adc %D0,__zero_reg__"
  [(set_attr "length" "14")
   (set_attr "cc" "clobber")])

Wobei bei solch langen Pattern irgendwann die Schmerzgrenze erreicht 
ist...

[Alexander E. (alex-rt)]

Die Aufnahme in die AVR Bibliothek wäre sehr gut.
Von den Pattern habe ich leider keine Ahnung, wie die funktionieren und 
wie diese Aufgebaut sind.
Gruß Alex.