Forum: Compiler & IDEs 16bit x 16bit ->32bit


von Benedikt K. (benedikt)


Lesenswert?

Gibt es einen Trick, um einen Compiler dazu zu bewegen, dass er 2 16bit 
Zahlen multipliziert, und ein 32bit Ergebnis erzeugt ?

Um z.B. zwei 16bit Zahlen x1, x2 zu multiplizieren, müsste man
y= (long)x1*x2;
schreiben, was aber leider zu 32bit=32bit*32bit wird, was bei einem AVR 
recht ineffizent ist. Gibt es einen einigermaßen ANSI C kompatiblen 
Trick um da zu umgehen ? Ich behelfe mir meist mit inline Assembler, was 
aber beim portieren aber ziemlich nervig ist.

von Uhu U. (uhu)


Lesenswert?

Nein, denn die Zwischenergebnisse einer 16x16-Bit Multiplikation sind 
fast alle länger als 16 Bit. Es muß also von Beginn an mit 32 Bit 
gerechnet werden.

Probiers einfach mal mit Papier und Bleistift aus...

von yalu (Gast)


Lesenswert?

Worauf Benedikt, glaube ich, hinaus will, dass man bei 32bit x 32bit
-> 32bit ca. 10 8-Bit-Multiplikationen benötigt (mit Tricks können's
eine oder zwei weniger sein), bei 16bit x 16bit -> 32bit aber nur 4.

Die Erweiterung der Operanden von 16 auf 32 Bits führt zu mehreren
Multiplikationen mit 0.

von Uhu U. (uhu)


Lesenswert?

Aber schon 16 Bit x 2 ergibt 17 Bit.

von Benedikt K. (benedikt)


Lesenswert?

yalu hat das genau richtig beschrieben.
z.B. ein AVR hat den mul Befehl, der 2 bit Zahlen multipliziert und eine 
16bit Zahl erzeugt. Da der Compiler intern sowiso mit 16bit rechnet, ist 
das ganze kein Problem, denn der Compiler erkennt, dass die Variablen 
8bit groß sind, und verwendet daher nur 1 mul.
Bei der int*int->long Version funktioniert das nicht, denn indem man auf 
long casted wird der Compiler gezwungen die int Werte schon vor der 
Berechnung auf long umzuwandeln.

Das einzige workaround das ich bisher anwende ist eine inline funktion 
long mul16(int,int), die genau das macht was ich vorhabe.

von yalu (Gast)


Lesenswert?

@Uhu

Schon klar, deswegen muss das Ergebnis 32 Bit sein, wenn man nicht
will, dass es abgeschnitten wird.

Folgendes stellt eine 16x16->32-Multiplikation dar:

  (0x100*a1 + a0) * (0x100*b1 + b0) =

= 0x10000*a1*b1 + 0x100*(a1*b0 + a0*b1) + a0*b0
            ^              ^       ^        ^

a1 und a0 sind die Bytes des ersten 16-Bit-Operanden, b1 und b0 die
Bytes vom zweiten. Jedes mit ^ gekennzeichnete * in der zweiten Zeile
ist eine 8x8->16-Multiplikation, für die ein ATmega einen fertigen
Befehl hat. Die Multiplikationen mit 0x100 und 0x10000 kosten keine
Zeit, da dies Potenzen von 2^8 sind und einfach durch die Speicher-/
Registeradressen beim Ablegen des Ergebnisses erschlagen werden.

Multipliziert man zwei 32-Bit-Werte und schneidet das Ergebnis auf 32
Bit ab, müssen die in der folgenden Tabelle mit * gekennzeichneten
Einzelmultiplikationen ausgeführt werden:

   b0 b1 b2 b3
a0        
a1      *  -
a2      -  -
a3  *  -  -  -

Die mit - gekennzeichneten Kombinationen wirken sich nur in einem
64-Bit-Ergebnis aus und können deswegen weggelassen werden. Es bleiben
also 10 Multiplikationen, was deutlich mehr sind als 4.

Wie schon erwähnt, können mit einem coolen Trick die 10 Multiplika-
tionen auf 9 oder 8 reduziert werden, ich habe ihn aber gerade nicht
im Kopf.

@Benedikt:
> Das einzige workaround das ich bisher anwende ist eine inline funktion
> long mul16(int,int), die genau das macht was ich vorhabe.

In Assembler, oder wie realisierst du die?

von Benedikt K. (benedikt)


Lesenswert?

yalu wrote:
>> Das einzige workaround das ich bisher anwende ist eine inline funktion
>> long mul16(int,int), die genau das macht was ich vorhabe.
>
> In Assembler, oder wie realisierst du die?

Genau, ich habe einfach eine 16bit x 16bit -> 32bit Funktion als inline 
Assembler geschrieben. Da der AVR mir jetzt zu langsam ist, wollte ich 
einen 16bit µC verwendet, der einen 16x16->32bit hardware Multiplizierer 
besitzt, aber auch hier habe ich wieder das gleiche Problem. Das ganze 
ist die Umrechnung von x,y Pixelkoordinaten in eine lineare 
Speicheradresse. Bei 640x480 Auflösung erhält man ein Ergebnis mit etwa 
19bit.

von yalu (Gast)


Lesenswert?

> Das ganze ist die Umrechnung von x,y Pixelkoordinaten in eine
> lineare Speicheradresse. Bei 640x480 Auflösung erhält man ein
> Ergebnis mit etwa 19bit.

D.h., jedes Pixel wird als 1 Byte gespeichert und du brauchst eine
Multiplikation mit 640 (bei zeilenweiser Speicherung des Bilds)?

Die Zahl 640 enthält gerade einmal 2 gesetzte Bits in Binärdarstel-
lung, die auch noch ziemlich nahe an den Bytegrenzen liegen. Wäre
(zumindest beim AVR) vielleicht eine selbstgestrickte Konstanten-
multiplikation mit Schiebe- und Additionsoperation geschickt? Wird
natürlich nicht ganz einfach sein, mit dem Hardwaremultiplizierer zu
konkurrieren.

Beim 16-Bit-µC müsstest du aber mit der Inline-Assember-Lösung weit
kommen, da ja nur noch ein einziger Multiplikationsbefehl benötigt
wird.

von Benedikt K. (benedikt)


Lesenswert?

yalu wrote:
> D.h., jedes Pixel wird als 1 Byte gespeichert und du brauchst eine
> Multiplikation mit 640 (bei zeilenweiser Speicherung des Bilds)?

Genau. Allerdings ist die Auflösung nicht fest und kann nahezu jeden 
Wert annehmen. Daher würde ich schon gerne eine echte Multiplikation 
verwenden.

> Beim 16-Bit-µC müsstest du aber mit der Inline-Assember-Lösung weit
> kommen, da ja nur noch ein einziger Multiplikationsbefehl benötigt
> wird.

Ja. Warscheinlich wird es auch wieder auf inline Asm hinauslaufen, aber 
ich hätte es schon gerne einigermaßen Hardware unabhängig. Da es bisher 
aber keinen direkten Lösungsvorschlag gibt, gehe ich mal davon aus, dass 
dies in ANSI C alleine nicht möglich ist ?

von yalu (Gast)


Lesenswert?

> Da es bisher aber keinen direkten Lösungsvorschlag gibt, gehe ich
> mal davon aus, dass dies in ANSI C alleine nicht möglich ist ?

Sagen wir's mal so: Mit dem aktuellen AVR-GCC gibt es mit hoher
Wahrscheinlichkeit keine reine C-Lösung des Problems, die
laufzeitmäßig halbwegs mit der Assembler-Lösung mithalten kann.

Das hängt zum einen damit zusammen, dass bei arithmetischen Opera-
tionen in C grundsätzlich die Operanden vom gleichen Typ sein müssen
(wenn sie's nicht sind, werden sie's gemacht) und das Ergebnis
ebenfalls von diesem Typ ist. Damit lässt sich eine 16x16->32-
Multiplikation nicht mit Sprachmitteln erzwingen.

Der Compiler könnte aber so schlau sein, solche Fälle zu erkennen und
einfachere Rechenroutinen einzusetzen. Der GCC macht das offensicht-
lich bei 8x8-Multiplikationen, bei denen die Operanden eigentlich erst
in int umgewandelt werden, was zu einer 16x16-Multiplikationen führen
müsste. Der Compiler optimiert auch dann, wenn die 8-Bit-Operanden
explizit in 16-Bit-Typen gecastet werden. Bei einer 16x16-Multipli-
kation, bei dem die Operanden nach 32 Bit gecastet werden (eigentlich
fast die gleiche Situation), ist keine entsprechende Optimierung
vorgesehen, obwohl sie wahrscheinlich ähnlich wie die 8x8-Optimierung
zu implementieren wäre. Vielleicht kommt sie ja irgendwann in einer
der nächsten Releases.

Schön wäre auch die Optimierung von Multiplikation mit unterschiedlich
großen Operanden:

   8x16->16 mit 2 Einzelmultiplikationen
   8x16->32 mit 3 Einzelmultiplikationen
   8x32->32 mit 4 Einzelmultiplikationen
  16x32->32 mit 7 Einzelmultiplikationen

Gerade die ersten beiden hätte ich auch schon oft gebraucht.

Alle diese Optimierungen sind natürlich nur auf 8- und 16-Bit-
Prozessoren von Interesse. Da der GCC aber hauptsächlich auf
32-Bittern (bspw. i86, PPC und ARM) eingesetzt wird, haben solche
Verbesserungen verständlicherweise nicht die höchste Priorität.

> Allerdings ist die Auflösung nicht fest und kann nahezu jeden Wert
> annehmen. Daher würde ich schon gerne eine echte Multiplikation
> verwenden.

Schade. Aber auch die Konstantenmultiplikation hätte man wahrschein-
lich in Assembler machen müssen, wäre dann aber etwa doppelt so
schnell wie die variable Lösung.

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.