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?
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.
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.
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);
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.
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.
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?
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'.
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.
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.
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:
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.
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.
Ersetze A und B durch ihren jeweiligen Absolutbetrag.
Berechne M = f[A+B] - f[A-B].
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).
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.
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?
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!
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.
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.
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.
