Festpunktarithmetik

**ogni42** · 22.03.2007, 08:09

Liebes Roboternetz,

attached meine Routinen zur Fixpunktarithmetik. Die nutzen die in den
neuen ATMegas vorhandenen Fixpunkt Assembler-Befehle und sind daher
recht kompakt.

Wertebereich ist immer [-1, 1[. Implementiert sind die Funktionen für
verschiedene Ein- und Ausgabegrößen sowie für die Operationen add, sub,
mul, mac (Multiply and Accumulate). Bei positiven und negativen
Überläufen wird das Ergebnis auf 1-eps bzw. -1+eps beschränkt.

Ich benutze die für Signalverarbeitung, daher das Clipping der Wertebereiche. Über Rückmeldungen würde ich mich freuen.

EDIT: Habe den Code auch im mikrocontroller.net mal hinterlegt. Mehr Augen finden vielleicht vorhandene Bugs eher als wenige.

**SprinterSB** · 22.03.2007, 09:27

Da hab ich direkt mal ein paar Fragen zu deinen Konstrukten

--1--

Code:

(op1 == op2 == 0x80)

Ist gleichbedeutend mit

Code:

(op1 == (op2 == 0x80))

und nicht mit

Code:

(op1 == 0x80 && op2 == 0x80)

oder

Code:

(op1 == 0x80 || op2 == 0x80)

Ist das gewollt?

Zitat von GCC

fixedPointArithmetics.c:88: warning: comparisons like X<=Y<=Z do not have their mathematical meaning

--2--
Die Constraints

Code:

: "=r" (result), "=r" (op1)
        : "0" (op1), "r" (op2)

und das damit verbundene Aliasing wirken recht abenteuerlich

Auf jeden Fall muss die Constraint mindestens "d" heissen, wenn auf ein Operanden LDI angewendt wird, und nicht "r". Dies könnte ansonsten zu einem Fehler im Asembler führen (immerhin kein Laufzeitfehler

) weil nicht alle GPR für LDI zulässig sind:

Code:

uint8_t fsub8(uint8_t op1, uint8_t op2)
{
    uint8_t result;

    // clipping:
    // C=1 & V=1 -> pos overflow, result = 0x7f
    // C=0 & V=1 -> neg overflow, result = 0x80
    asm volatile (
        "sub %[result], %[op2]"    "\n\t"
        "brvc 0f"                  "\n\t" // no overflow -> done
        "ldi %[result], 0x81"      "\n\t" // overflow -> set min neg value (might still be positive overflow)
        "brcc 0f"                  "\n\t" // no carry (thus no positive overflow) -> done
        "ldi %[result], 0x7f"      "\n\t" // positive overflow -> set max pos value
        "0:"
        : [result] "=d" (result), "=d" (op1)
        : "0" (op1), [op2] "r" (op2)
    );
    return result;
}

Bei die kommt der Fehler nicht zum tragen, weil nie geinlint wird (siehe -4-).
--3--
Wo wird %A0 in fadd816/fsub816 belegt?

--4--
Wozu extern inline? Sehe ich jetzt keinen Nutzen... Innerhalb des Moduls wird keine deiner Funktionen aufgerufen; geinlint wird also nie werden.

**ogni42** · 22.03.2007, 10:57

Hi Sprinter,

danke für das Feedback. Es ist immer gut, wenn jemand drüber schaut. Ein update poste ich, wenn wir alle Fehler raus haben.

--1--
Stimmt, ist falsch. Wird geändert. Komisch, bei mir hat trotz -Wall der Compiler kein warning geworfen. Compiliert wird mit

Code:

avr-gcc.exe  -mmcu=atmega168 -Wall -gdwarf-2 -std=gnu99   -mcall-prologues    -DF_CPU=184320UL -Os -fsigned-char -MD -MP -MT fixedPointArithmetics.o -MF dep/fixedPointArithmetics.o.d  -c  ../fixedPointArithmetics.c

--2--
Stimmt, die müssen angepasst werden. Da habe ich beim Testen wohl einfach nur Glück gehabt.

--3--
pwned

Gar nicht. Ist schon in Änderung...

--4--
Laut GCC doku soll man vor die Deklaration (im Header) das inline schreiben. Falls das nicht richtig ist, wo soll es sonst hin?

**ogni42** · 22.03.2007, 11:19

Hier jetzt das update. Die von Dir verwendete - wie ich finde schönere - Notation %[c-name] ist noch nicht drin. Kommt aber noch...

**SprinterSB** · 22.03.2007, 15:56

Zitat von ogni42

Komisch, bei mir hat trotz -Wall der Compiler kein warning geworfen. Compiliert wird mit...

Hi, hier meine build-options

Code:

avr-gcc -mmcu=atmega88 -S fixedPointArithmetics.c -dp -save-temps -fverbose-asm -Wall -Os -morder1 -W -Winline -fno-keep-inline-functions -DF_CPU=1000000 -fno-common -Wstrict-prototypes

Aber selbst damit bekommst du noch lange nicht alle Warnungen...

Zitat von ogni42

--2--
Stimmt, die müssen angepasst werden. Da habe ich beim Testen wohl einfach nur Glück gehabt.

Das kommt deshalb hin, weil die Funktionen nie geinlinet werden und die Register-Allokierung von avr-gcc eben so ist, daß die Register immer in der passenden Klasse liegen.

Zitat von ogni42

--4--
Laut GCC doku soll man vor die Deklaration (im Header) das inline schreiben. Falls das nicht richtig ist, wo soll es sonst hin?

Falsch ist es ja nicht, nur werden die Funktionen so nie geinlinet...

Funktionen können nur dann geinlint werden, wenn dem Compiler der Quellcode der zu inlinenden Funktionen bekannt ist. Du gibt dem Compiler aber lediglich via #include "foo.h" das Interface zu sehen!

Das "extern" bewirkt hier nur, daß die so deklarierten Inline-Funktionen vom Compiler implementiert werden und als Object zur Verfügung stehen, wenn das Symbol gebraucht wird (Funktionsaufruf von ausserhalb, Funktionsadresse nehmen, etc).

Damit der Code tatsächlich geinlint wird, muss er also im Header (und damit im C-Modul, das das Zeug verwendet) sichtbar sein.

Du kannst also die Implementierungen in den Header schreiben und die Funktionen als static inline deklarieren und dann implementieren.

GCC hat allerdings eine recht genaue Vorstellung davon, für welche Funkrtionen ein inline lohnt und wann nicht (Größe des Tree, Anzahl insns, ...). inline ist also nur eine Empfehlung, ein heherer Wunsch an GCC. Wenn auf jeden Fall (vorausgesetzt immer, daß es prinzipiell möglich ist) geinlint werden soll, dann gibt man der Funktion das Attribut always_inline:

Code:

#define INLINE __attribute__((always_inline))
static INLINE ...

Ob das in Deinem Fall notwendig ist kann ich nicht sagen, weil ich nicht weiß, wie GCC asm behandelt (GCC kann nicht wissen, wieviel/was für'n Code sich darin verbirgt).

Allerdings wirst du beobachten, daß der Code nicht so optimal ist, wie du dir wünscht. Ursache dafür ist die argument und return parameter promotion die erfolgt und die auch nicht umgangen werden kann. Du wirst also ständig überflüssige zeroextends vorfinden, d.h. 8-Bit-Werte werden zu 16-Bit-Werten expandiert, obwohl nie per 16 Bit auf den Wert zugegriffen wird. Das gibt viel Overhead in Laufzeit und Code, vorallem weil das Inlinen als Multiplikator wirkt.

Promotion kannst du nur dadurch vermeiden, indem du den Code -- zugegeben nicht sonderlich hübsch -- in Makros steckst, etwa als valued block.

Noch besser und wirklich optimalen Code bekommst du, wenn GCC eine Vorstellung davon hat, was er da treibt. Das würde bedeuten, die Funktionen als builtins (intrinsics) zur Verfügung zu stellen...

**SprinterSB** · 22.03.2007, 17:29

Nochwas: Momentan hast du einige Constraints zu eng. Bei mac müssen nur die in-ops des MUL "a" sein, op3 und result darf "r" sein (bzw "d" bei LDI).

Anstatt

Code:

	ldi r24, 0x01	 ;  result
	ldi r25, 0x80	 ;  result
	brcc 0f
	ldi r24, 0xff	 ;  result
	ldi r25, 0x7f	 ;  result

Spart folgendes (bei gleiche Laufzeit) 2 Bytes:

Code:

	ldi r24, 0x01	 ;  result
	ldi r25, 0x80	 ;  result
	brcc 0f
	sbiw r24, 2	 ;  result

Für weitere Tipps wär es auch hilfreich zu wissen, wohin Du optimieren willst (optimieren willst Du, sonst würdest Du kein asm anfassen).

Also: Größe oder Zeit. Klar, man will beides und mit Geschick bekommt man auch beides zu einem gewissen Grad, aber ab einem gewissen Punkt muss man sich dann entscheiden...

Interessant wäre auch, die Saturierung der 16-Bit-Werte in einem sibling call zu machen

Das Ärgernis dabei ist, daß es keine Registerklasse für das return-Register r25:r24 gibt.

**ogni42** · 24.03.2007, 15:06

Hi Georg-Johann,

vielen Dank für Dein ausführliches Feedback. Das hilft mir sehr weiter. Die Constraints werde ich noch anpassen.

Den sbiw baue ich bein den sub und add noch ein. (Da ich die ganze Woche unterwegs war, ist der Code noch auf einem anderen Rechner)

Was ist die Idee hinter dem Ganzen?

Klassisch gibt es zwei Möglichkeiten Signalverarbeitungsroutinen auf Non-DSPs zu implementieren, Fließpunkt- oder Festpunktarithmetik. Floats sind auf dem AVR Overkill und der Flash/RAM sind schnell aufgebraucht. Daher kommt eigentlich nur Festpunktarithmetik in Frage. Die AVRs bieten Festpunktbefehle in Assembler an, aber es gibt keinen Weg, von aus C da ran zu kommen - außer per inline Assembler eben.

Der Vorteil der fmulx Opcodes ist, dass der Wertebereich immer [-1, 1[ bzw [0, 2[ angenommen wird. Daher sind Multiplikationen immer ohne Überläufe zu handhaben. Des weiteren ist der FixpointMultiplyAndAccumulate für viele Signalverarbeitungsalgorithmen hilfreich. Division kommt eher selten vor. Atmel bietet ja ein paar Beispiele zur Nutzung von FMAC etc., die haben aber m.E. zwei wesentliche Nachteile:
- kein Clipping, Bereichsüberläufe werden nicht behandelt, die sind aber wichtig
- Die Atmel Implementierung nimmt keine Rücksicht auf die Genauigkeit und verschwendet dadurch Rechenzeit (aus zwei 16 bit Werten wird ein 32bit Wert dessen untere 16 bit aber nicht weiter helfen).

Für meine Anwendung ist dann die Balance zwischen Speicherverbrauch und Geschwindigkeit zu halten. Inline C-Funktionen scheinen mir da am Besten geeignet. Wenn der Flash eng wird, kommt das inline raus und weiter gehts.

Die Routinen sind einerseits bei für mich ausreichender (hoffe ich) Genauigkeit erheblich schneller als eine Implementierung in C andererseits noch so kompakt, dass sie für einen Assembler-Laien wie mich überschaubar bleiben. Mit der Parameter-Promotion muss ich da wohl leben. Die Alternative mit #defines finde so fies, dass ich nur in der größten Not darauf zurück greifen möchte.

Hab' auch nochmal die GCC Doku etwas genauer gelesen. An einer Stelle steht inline in der declaration an anderer inline in der definition, die dann im Header landen soll. Letzteres funktioniert dann auch (wie Du bereits geschrieben hast)

Ingo

**ogni42** · 26.03.2007, 12:47

Das mit dem SBIW habe ich noch nicht ganze verstanden.

Beispiel für subtraktion 4 - (-7) (bei 4bit Zahlen, der Einfachheit halber)

Code:

 0100
-1001

Umwandlung des Comp_2
 0100
+0111

ergibt

1011

jetzt SBIW r, 2

 1011
-0010

macht

 1001

Es sollte aber 0111 (MAXPOSINT) als Ergebnis da stehen. Habe ich was falsch verstanden?

**SprinterSB** · 26.03.2007, 13:27

Das Schnippsel

Code:

	ldi r24, 0x01	 ;  result
	ldi r25, 0x80	 ;  result
	brcc 0f
	ldi r24, 0xff	 ;  result
	ldi r25, 0x7f	 ;  result

in pseudo bedeutet doch

Code:

x := 0x8001
IF carry != 0
THEN
    x := 0x7fff
FI

was gleichbedeutend ist mit

Code:

x := 0x8001
IF carry != 0
THEN
    x := x-2
FI

100% gleich ist's allerdings nicht, weil die Maschine danach einen anderen Status hat. Der Maschinenstatus wird danach jedoch nicht mehr verwendet.

**ogni42** · 26.03.2007, 20:11

Ja sicher, Du hast recht.

Baue ich ein und mache dicken Kommentar dahinter, sonst verstehe ich das in zwei Jahren nicht mehr sofort.

Thema: Festpunktarithmetik

Themen-Optionen

Thema durchsuchen

Anzeige

Festpunktarithmetik

Lesezeichen

Lesezeichen

Berechtigungen