wie "erzwinge" ich eine 16bit*16bit = 32bit Multiplikation?

[Jörg H. (idc-dragon)]

Ich caste mir mit AVR gcc gerade den Wolf, aber es will nicht klappen:
Ich brauche eine Multiplikation von zwei uint16_t, das Ergebnis davon 
hat 32 bit Breite. Von diesem will ich ferner nur die obere Hälfte 
weiterverwenden, die untere ist sozusagen der Nachkommateil.

Etwa in der Art:

uint16_t a;
uint16_t b;
uint16_t c;
...
c = (a*b) >> 16;

Der Compiler sieht das so wohl als Multiplikation mit 16 Bit 
Ergebnisbreite an. Außerdem erkennt er, das anschließend die 16 gültigen 
Ergebnisbits rausgeschoben werden, und optimiert die Multiplikation weg. 
Hieraus entsteht also gar kein Code.

Wenn ich in einem hilflosen Versuch z.B. einen Operanden auf 32 bit 
caste,

c = ((uint32_t)a*b) >> 16;

dann wird gleich die Bibliotheksfunktion __mulsi3 instantiiert und 
aufgerufen, das ist volle Breitseite 32*32 bit.
Habe ich eine Chance, das hier effizienterer Code erzeugt wird?

[Jörg H. (idc-dragon)]

Auf 32Bit Prozessoren geht das mitunter, in etwas anderer Form. Man 
kommt mit 32 Bit Variablen (=Maschinenworten) an. Wenn man weiß das nur 
die untere Hälfte belegt ist und 16*16Bit ausreicht kann man die 
Operanden im Multiplikationsterm auf 16 Bit casten. Der Compiler fügt 
dann eine kleinere Multiplikation ein, aber liefert 32 bit Ergebnis:

uint32_t a;
uint32_t b;
uint32_t c;
...
c = (uint16_t)a * (uint16_t)b;

Daher meine Hoffnung, daß ich meinen Fall auf dem 8bitter dem Compiler 
das irgendwie verständlich casten kann.

[Detlef _. (detlef_a)]

Vielleicht so:
a=(a1*2^8+a2);
b=(b1*2^8+b2);
also
c=(a*b)/2^16=(a1*b1*2^6+(a1b2+b1a2)*2^8+a2b2)/2^16=
a1b1+(a1b2/2^8+b1a2/2^8)

c=(a>>8)*(b>>8)+((a>>8)*(b&255))>>8+((b>>8)*(a&255))>>8;

gute Nacht
Detlef

[Jörg H. (idc-dragon)]

Nanu, der Thread ist etwas entstellt, wo sind denn die Postings von 
Andreas Kaiser (a-k) hin?

Zu der gcc-Optimierung: Sowas kann man nur bauen, wenn es einen Weg für 
den Compiler gibt das zu erkennen. Wie sagt man ihm also korrekt, das er 
16*16->32 multiplizieren soll? Mich wundert offengestanden schon, das es 
keine ensprechende Bibliotheksfunktion geben soll. Ich habe eine 
Auflistung derselben gesucht, aber nicht gefunden.

"Zu Fuß" multiplizieren wie von Detlef angeregt könnte schon eine Lösung 
sein. Muß mal nachgucken wie das ging, ist ja wie schriftlich 
multiplizieren, ist schon eine Weile her...

[Andreas K. (a-k)]

Jörg Hohensohn wrote:

> Nanu, der Thread ist etwas entstellt, wo sind denn die Postings von
> Andreas Kaiser (a-k) hin?

Kein Interesse, mich auf dem Niveau von JfK rumzuärgern.

[Jörg H. (idc-dragon)]

Andreas Kaiser wrote:

> Kein Interesse, mich auf dem Niveau von JfK rumzuärgern.

Ja, schade. Durch Löschen der "guten" Anteile sieht es aber auch nicht 
besser aus.

Ich hab kurz in Richtung Detlef weiterprobiert. Der Term stimmte so noch 
nicht ganz. Es sind 4 Teilmultiplikationen, 8*8->16. Die Ergebnisse 
davon muß man wegen möglicher Überläufer schon 32bittig addieren, darf 
erst zum Schluß die unteren 16 Bit wegschneiden.

uint16_t mul16x16h(uint16_t a, uint16_t b)
{
    uint32_t c;
    c = (a>>8)*(b>>8)<<16 + (a>>8)*(b&255)<<8 + (a&255)*(b>>8)<<8 + (a&255)*(b&255);
    return c >> 16;
}

Ich krieg es dem Compliler aber auch hier noch nicht beigebogen, sich 
auch so zu verhalten, casts der Multplikationsanteile auf uint32_t 
halfen nicht.

Ich hoffe immer noch auf eine "fertige" 16*16->32 Multiplikation aus der 
Library...

[Detlef _. (detlef_a)]

>>Die Ergebnisse davon muß man wegen möglicher Überläufer schon 32bittig 
>>addieren,

naja, wie immer kann man Genauigkeit gegen Aufwand handeln: 
(a&255)*(b&255) kann maximal 255^2 groß werden, das beeinflußt also 
höchstens Bit Nummer 16 deines 32 Bit Ergebnis, der gemischte Term kann 
maximal 2*255^2 werden, geht also maximal in Bit 16/17 ein. Wenn Dir 
also das LSB Deines geschobenen c egal ist kannst Du die Berechnung 
(a&255)*(b&255) weglassen, wenn Dir die beiden unteren Bit egal sind 
reicht es (a>>8)*(b>>8) zu berechnen.

Cheers
Detlef

[Jörg H. (idc-dragon)]

Es gibt tatsächlich keine Bibliotheksfunktion, gerade habe ich die Doku 
gefunden (libgcc war das Zauberwort):
http://gcc.gnu.org/onlinedocs/gccint/Integer-library-routines.html#Integer-library-routines
Die liefern alle die gleiche Breite zurück, die reingesteckt wurde.

Detlef, du hast recht, das mit der Genauigkeit ist schon erstaunlich. 
16*16 Bit für meine Festkommaarithmetik liefert mir letztlich nur 2 Bit 
mehr Ergebnis als 8*8 Bit, hmm.