Moin, Ich haett' gerne mal folgendes Problem: Einen AVR core, der keine Multiplikationsbefehle hat, wie z.b. der attiny. Und auf dem Dingens moecht ich gerne moeglichst hurtig in asm eine 8x8 bit signed Multiplikation durchfuehren. Also sowas wie : A x B = CD wobei A und B jeweils 8bit Register mit Zweierkomplementzahlen sind, und CD dann ein 16 bit Wert auch im Zweierkomplement darstellt. "Zufaellig" hab' ich "hinten im Flash" schon zwei Tabellen a 256 Byte stehen, mit jeweils Low- und Highbyte des Quadrats des (unsigned) Indexes. Kann also einigermassen schnell mittels Z-Register einen unsigned 8bit Wert quadrieren. Jetzt hab' ich irgendwo schon mal sowas gesehen, weiss aber nicht mehr wo, wo man die Multiplikaton von A und B mittels der ersten und zweiten binomischen Formel geloest hat: also einmal A+B quadriert und einmal A-B quadriert, die Ergebnisse voneinander abziehen und es bleibt 4 x A x B uebrig, was nach 2x rechtsschieben das Ergebnis der gewuenschten Multiplikation ist. (Bei den Werten A+B und A-B interessiert auch nur der Betrag, weil die ja eh' quadriert werden). Jetzt fress ich doch einen Besen, wenn das nicht schonmal wer programmiert hat, mutmasslich vielleicht sogar hier irgendwo im Forum. Nur tu' ich mir da mit Suchen etwas schwer...weiss da wer was? Gruss WK
Naja, wenn ich selber darueber nicht nachdenlen wollte, wuerde ich das mal als C Code eintippen und den Compiler seine Arbeit machen lassen. Eine der Compileroptionen ist es, ein Listingfile zu erzeugen. Das sollte dann genug Inspiration bieten... Falls der Compiler die Library aus der er sein Wissen bezogen hat nicht als Listing preisgeben will: obj-dump (oder so aehnlich) kann auch Compilat in ein Listing verwandeln. Ansonsten: Einfach einen Controller mit "mul" benutzen. Die gibt es auch in 8 Pin und 8 bit.
P.S. Wobei die (8x8) Multiplikation ja noch trivial ist. 16 bit schieben und fallweise etwas dazuaddieren. Das mit den Quadraten faellte bestuemmpt komplizierter aus. Und die Einsparung ist wieder dahin.
Hier haben sich schon manche Gedanke dazu gemacht: https://stackoverflow.com/questions/29935050/tinyavr-best-known-multiplication-routines-for-8-bit-and-16-bit-factors
Dergute W. schrieb: > Und auf dem Dingens moecht ich gerne moeglichst hurtig Das sind ja mal wieder super konkrete Angaben. Du kannst den AVR-GCC multiplizieren lassen und Dir das Assemblerlisting ausgeben lassen.
Moin, Peter D. schrieb: > Das sind ja mal wieder super konkrete Angaben. OK, dann halt: -O9 (statt -Os) Ja, klar habbich dem gcc schon zugeschaut, was der so macht. Fuer die Multiplikation ruft der halt stumpf __mulhi3 auf, und da wird sich klassisch in einer loop aus der Welt geshiftet. Ich seh' schon: Gesamtproblem ist zu komplex, also brech' ichs mal runter: ich will in asm hurtig erstmal nur folgendes loesen: (uint8_t)x = abs((int8_t)a + (int8_t)b);
1 | /* compile with: avr-gcc -Wall -Wextra -O3 -g -mmcu=attiny13a -c plus.c */
|
2 | #include <inttypes.h> |
3 | #include <stdlib.h> /* abs() */ |
4 | |
5 | uint8_t plus(int8_t a, int8_t b) { |
6 | return (uint8_t)abs((int16_t)a + (int16_t)b); |
7 | // return abs(a + b);
|
8 | }
|
Dann macht mir der gcc diesen Apparillo draus (und zwar egal ob mit oder ohne cast-Orgie):
1 | plus.o: file format elf32-avr |
2 | |
3 | |
4 | Disassembly of section .text: |
5 | |
6 | 00000000 <plus>: |
7 | 0: 77 27 eor r23, r23 |
8 | 2: 67 fd sbrc r22, 7 |
9 | 4: 70 95 com r23 |
10 | 6: 9b 01 movw r18, r22 |
11 | 8: 28 0f add r18, r24 |
12 | a: 31 1d adc r19, r1 |
13 | c: 87 fd sbrc r24, 7 |
14 | e: 3a 95 dec r19 |
15 | 10: c9 01 movw r24, r18 |
16 | 12: 37 ff sbrs r19, 7 |
17 | 14: 08 95 ret |
18 | 16: 91 95 neg r25 |
19 | 18: 81 95 neg r24 |
20 | 1a: 91 09 sbc r25, r1 |
21 | 1c: 08 95 ret |
Der macht da dann also eine schoene 16bit addition draus. Mit Faxen davor und danach. Wird er wohl bei C auch machen muessen, denn die Summe aus 2 8bit Zahlen hat nunmal 9 bit. Und C weiss nix von Carry- oder Signed- oder Overflowflags. Ich aber schon. Nur eher prinzipiell, ich programmiere eher selten in avr assembler. Und aus meinem gefaehrlichen Halbwissen schoepfe ich die Hoffnung, dass dieser Spezialfall (abs(a+b)) doch simpler(=schneller=weniger Zyklen) zu machen ist, als der gcc hier vorschlaegt. Fuer abs(a-b) wirds aehnlich laufen. Gruss WK
Von Multiplikation zu abs() ist es aber schon recht weit, meinste nicht? Und wie willst du anhand des Carry Flags alleine entscheiden ob du einen Überlauf bei der Addition (-128 + (-1)) Oder einfach nur einen Vorzeichenwechsel (-64 + 127) hattest? Was soll überhaupt das 8 Bit Ergebniss von abs(-128-128) sein? Der Compiler macht hier exakt das, was du von Ihm verlangst.
Ist das jetzt ein akademisches Problem? Oder suchst du tatsächlich eingesparte Takte? Wenn ja - wieviel wäre denn "hurtig" genug? War früher auch gerne mal ein Hobby von mir, mehr um sich selbst zu zeigen dass es schneller geht. Der Aufwand steht i.a. in keinem Verhältnis zum Nutzen. Oft genug sogar völlig sinnlos, weil die eingesparte Zeit dann doch wieder irgendwo vertrödelt wure. Ist es tatsächlich eng bis sehr eng, anderen MC benutzen, fertig. Selbst wenn man so ein Problem gerade noch gebacken bekommt sitzt man bei der nächsten kleineren Erweiterung wieder da.
Moin, Andreas M. schrieb: > Und wie willst du anhand des Carry Flags alleine entscheiden Will ich garnicht. Ich erwaehnte auch andere Flags. Andreas M. schrieb: > Was soll überhaupt das 8 Bit > Ergebniss von abs(-128-128) sein? Guter Punkt. Dann definiert sich der kleine wimalopaan in mir halt einen eigenen 8bit signed Bereich, der nur von -127 bis +127 reicht ;-) Andreas M. schrieb: > Der Compiler macht hier exakt das, was du von Ihm verlangst. Das bezweifle ich auch nicht. Ich bezweifle nur, dass hier "gucken, was der Compiler macht" die beste Idee ist. H.Joachim S. schrieb: > Ist das jetzt ein akademisches Problem? Das ist nichtmal akademisch. Das ist die Sorte Problem, ueber die man beim Besuch der sanitaeren Anlagen nachdenken kann. Und natuerlich reinem Spass' an der Freud'. Aber vielleicht kommt neben warmer, aromatisierter Luft auch mal ein komplexer IQ Mischer oder ein Moppedladestromregler dabei raus - wer weiss? H.Joachim S. schrieb: > Der Aufwand steht i.a. in keinem > Verhältnis zum Nutzen. > Oft genug sogar völlig sinnlos, weil die eingesparte Zeit dann doch > wieder irgendwo vertrödelt wure. Ja, klar. So wie z.b. Minigolf spielen oder Serien glotzen. Trotzdem machen das die Leut'. Gruss WK
Dergute W. schrieb: > Einen AVR core, der keine Multiplikationsbefehle hat, wie z.b. der > attiny. > Und auf dem Dingens moecht ich gerne moeglichst hurtig in asm eine 8x8 > bit signed Multiplikation durchfuehren. > Also sowas wie : A x B = CD In der Atmel-App-Note AVR200.PDF nebst Source-Code AVR200.ZIP ist auch diese Variante beschrieben.
Moin, Eberhard H. schrieb: > In der Atmel-App-Note AVR200.PDF nebst Source-Code AVR200.ZIP ist auch > diese Variante beschrieben. Ich vermag da keine speed-optimierte 8x8 signed Multiplikationsapplikation zu erkennen. Weder im pdf noch im zip. Gruss WK
Beitrag #7521257 wurde vom Autor gelöscht.
Dergute W. schrieb: > H.Joachim S. schrieb: >> Ist das jetzt ein akademisches Problem? > Das ist nichtmal akademisch. Das ist die Sorte Problem, ueber die man > beim Besuch der sanitaeren Anlagen nachdenken kann. Na dann mach doch doch. Allein Gibt es einen besonderen Grund warum wir deine Lokus-Gedanken mit dir teilen sollen? Ganz abgesehen davon, eine Multiplikation 8x8 macht man am schnellsten ganz klassisch zu Fuß. Die beiden Quadrierungen werden nur schnell mit Lookup-Tabellen. Und die 16-Bit Subtrahierung und Shifts für das Ergebnis gibt es auch nicht umsonst. Alles in allem würde es mich sehr wundern, wenn du dadurch was sparst. Codegröße schon mal definitiv nicht.
Axel S. schrieb: > Ganz abgesehen davon, eine Multiplikation 8x8 macht man am schnellsten > ganz klassisch zu Fuß. [...] > Alles in allem würde es mich sehr > wundern, wenn du dadurch was sparst. Codegröße schon mal definitiv > nicht. Codegröße natürlich nicht, dagegen spricht schon die nötige Tabelle. Rechenzeit hingegen schon. MULU8X8 zu Fuß werden 40T. MULU8x8 mit dem Ansatz im OT werden 24T. Sprich: 40%(!) Rechenzeit gespart. Wenn das Programm rechenzeittechnisch betrachtet im Wesentlichen nur aus Multiplikationen besteht (in der Signalverarbeitung kein ganz unübliches Szenario), dann kann das schon einen massiven Unterschied machen und leicht über das "geht" oder "geht nicht" der Gesamtlösung entscheiden. @Dergute W.: In dem hier geposteten Quelltext stecken ein MULU8X8- und ein MULSU10X8-Macro (in synthesizer.asm), die beide nach dem gewünschten Prinzip arbeiten: Beitrag "Re: Westminster Soundgenerator mit ATtiny85" Es sollte sich mit diesen Vorlagen leicht ein auf dein konkretetes Mul-Problem angepaßtes Macro (respektive Inline-Asm-Funktion) basteln lassen.
Recht alt 1999-2003), für AVR ohne Multiplizierbefehle in Assembler https://avr-asm.tripod.com/math32x.html allerdings eher 32 bit und unsigned
:
Bearbeitet durch User
Christoph db1uq K. schrieb: > Recht alt 1999-2003), für AVR ohne Multiplizierbefehle in Assembler > https://avr-asm.tripod.com/math32x.html > allerdings eher 32 bit und unsigned Da ist nur das primitive Schiebe- und Addierspiel drinne. Was rechenzeittechnisch halt suboptimal ist und auch genau das war, was der TO ausdrücklich NICHT wollte.
Dergute W. schrieb: > wo man die Multiplikaton von A und B mittels der ersten und zweiten > binomischen Formel geloest hat: > also einmal A+B quadriert und einmal A-B quadriert, die Ergebnisse > voneinander abziehen und es bleibt 4 x A x B uebrig, was nach 2x > rechtsschieben das Ergebnis der gewuenschten Multiplikation ist. Da braucht's dann aber 18 Bits für's Zwischenergebnis, und eine Tabelle mit den Qadraten von 0...255 ist nicht ausreichend; es braucht dann eine Tabelle der Quadrate von 0...511. Alternative ist: a = u - v b = u + v ==> ab = (u-v)(u+v) = u² - v² wobei u = (a + b) >> 1 v = |a - b| >> 1 Falls a und b beide (un)gerade sind, ist man fertig. Ansonsten überlegt man sich, welche Anpassung notwendig ist weil das Rechts-Schieben ja ein Bit unter den Tisch hat fallen lassen. Wegen (u + 1/2)² ≈ u² + u addiert man u aufs Ergebnis wenn a+b ungerade ist. Eine ähnliche Überlegung gilt für v.
Konkret kann man es so machen: 1) Berechne das Vorzeichen S von A * B. 2) Ersetze A und B durch ihren jeweiligen Absolutbetrag. 3) Berechne M = f[A+B] - f[A-B]. 4) Return S * M. f[] ist eine Lookup-Tabelle mit Vierteln von Quadraten: f = [n*n div 4 for n in 0...256] Wenn man sich dann nicht komplett ungeschickt anstellt, braucht eine entsprechende Implementierung durchschnittlich weniger als 50 Ticks (inclusive CALL + RET). Schritt 3 berechnet also
Wegen (A+B)² = (A-B)² mod 4 enthalten die unteren beiden Bits keine Information, und es genügt die Viertel der Quadrate zu speichern. Dies spart den Rechts-Shift am Ende, und außerdem passt 256² / 4 = 0x4000 in die Tabelle; während 256² = 0x10000 nicht in 16 Bits passen würde und man einen Spezialfall für -128 * -128 bräuchte.
Moin, Axel S. schrieb: > Na dann mach doch doch. Allein > > Gibt es einen besonderen Grund warum wir deine Lokus-Gedanken mit dir > teilen sollen? Gibt es einen besonderen Grund, warum du hier rummopperst, anstatt einfach zu Themen zu schreiben, die dich interessieren? Oder einfach mal rausgehen und einen Apfel essen? Axel S. schrieb: > Die beiden Quadrierungen werden nur schnell mit > Lookup-Tabellen. Oder zumindest mal sinnerfassend liest, was ich im 1. Post geschrieben habe? Dergute W. schrieb: > "Zufaellig" hab' ich "hinten im Flash" schon zwei Tabellen a 256 Byte > stehen, mit jeweils Low- und Highbyte des Quadrats des (unsigned) > Indexes. Fuer die konstruktiven Beitraege hier vielen Dank. Insbesondere Johann L. schrieb: > Wegen (A+B)² = (A-B)² mod 4 enthalten die unteren beiden Bits keine > Information, das ist im Nachhinein voellig klar; da ich aber einfach gestrickt bin, ist eben genau so ein Hinweis das, was mir aus einem Forum weiterhilft und die Sorte Tip, die ich mir erhofft habe. Nochmal Danke! Gruss WK
:
Bearbeitet durch User
Also sorry, aber das ist wirklich absolut sinnfreie Zeitverschwendung. Wenn ich schon von vornerein weiss, dass ich ein rechenlastiges Projekt vor mir haben, werde ich bestimmt keinen attiny nehmen, sondern nen xmega (da ich avr fanboy bin). Für die 99% aller anderen Projekte ist es sowas von egal, ob der für die einmalige Multiplikation 250ns oder 5us braucht.
Angehängte Dateien:
Christian schrieb: > ob der für die einmalige Multiplikation 250ns oder 5us braucht. A multiplication takes two CPU clock cycles.
Georg M. schrieb: > A multiplication takes two CPU clock cycles. Er will wohl nur die alten ATtiny nehmen (ATtiny13, 26, 2313 usw.), die hatten noch kein MUL.
Ich hatte mal nach Karazuba avr in der üblichen Suchhilfe nachgeschaut. Nicht direkt so, aber für korrekte Begrifflichkeiten ist ja so eine Suchhilfe auch ganz gut. http://mhutter.org/research/avr/ Mit Sourcecode zum herunterladen So generell gibt es eine ganze Menge recht interessanter Seiten (z.B. https://eprint.iacr.org/2014/817) Theorie: Binomische Formeln sind ja irgendwie so Dreieckszahlen, nicht direkt 1,3,6, 10 aber sie hängen irgendwie mit drin im Pascalschen Dreieck https://de.wikipedia.org/wiki/Pascalsches_Dreieck
Rbx schrieb: > Ich hatte mal nach Karazuba avr in der üblichen Suchhilfe nachgeschaut. > > http://mhutter.org/research/avr/ Karatsuba ist eher was für große[tm] Zahlen: >> Karatsuba multiplication technique and covers input >> sizes of 48, 64, 96, 128, 160, 192, and 256 bits.
Peter D. schrieb: > Georg M. schrieb: >> A multiplication takes two CPU clock cycles. > > Er will wohl nur die alten ATtiny nehmen (ATtiny13, 26, 2313 usw.), die > hatten noch kein MUL. Richtig, dabei waren zumindest die ATtinyX5 und auch die ATtinyX41 ansonsten ziemlich interessante Teile, wenn auch aus verschiedenen Gründen. Und zumindest für diese beiden Familien wäre es garnicht so einfach, adäquaten Ersatz unter den neuzeitlichen Tinys zu finden, die zwar alle Hardwaremultiplikation und auch sonst einen Haufen Features bieten, aber eben doch auch einiges an Features vermissen lassen, die diese "ollen" Teile haben.
Ob S. schrieb: > aber eben doch auch einiges an Features vermissen lassen, die diese > "ollen" Teile haben. Was sindn das für tolle olle Features?
Johann L. schrieb: > Ob S. schrieb: >> aber eben doch auch einiges an Features vermissen lassen, die diese >> "ollen" Teile haben. > > Was sindn das für tolle olle Features? Suche einfach selber eine Ersatz unter den neuzeitlichen Tinys dafür. Dann kommst du schon dahinter. Selber...
Thread beobachten
Seitenaufteilung abschaltenBitte 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.