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.
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...
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.
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.
@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?
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.
> 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.
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 ?
> 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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.