-         

Seite 1 von 4 123 ... LetzteLetzte
Ergebnis 1 bis 10 von 31

Thema: Festpunktarithmetik

  1. #1
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    21.10.2005
    Ort
    Erde
    Alter
    50
    Beiträge
    1.195

    Festpunktarithmetik

    Anzeige

    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.
    Angehängte Dateien Angehängte Dateien

  2. #2
    Erfahrener Benutzer Robotik Einstein Avatar von SprinterSB
    Registriert seit
    09.06.2005
    Ort
    An der Saar
    Beiträge
    2.801
    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 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.
    Disclaimer: none. Sue me.

  3. #3
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    21.10.2005
    Ort
    Erde
    Alter
    50
    Beiträge
    1.195
    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?

  4. #4
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    21.10.2005
    Ort
    Erde
    Alter
    50
    Beiträge
    1.195
    Hier jetzt das update. Die von Dir verwendete - wie ich finde schönere - Notation %[c-name] ist noch nicht drin. Kommt aber noch...
    Angehängte Dateien Angehängte Dateien

  5. #5
    Erfahrener Benutzer Robotik Einstein Avatar von SprinterSB
    Registriert seit
    09.06.2005
    Ort
    An der Saar
    Beiträge
    2.801
    Zitat 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 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 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...
    Disclaimer: none. Sue me.

  6. #6
    Erfahrener Benutzer Robotik Einstein Avatar von SprinterSB
    Registriert seit
    09.06.2005
    Ort
    An der Saar
    Beiträge
    2.801
    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.
    Disclaimer: none. Sue me.

  7. #7
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    21.10.2005
    Ort
    Erde
    Alter
    50
    Beiträge
    1.195
    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

  8. #8
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    21.10.2005
    Ort
    Erde
    Alter
    50
    Beiträge
    1.195
    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?

  9. #9
    Erfahrener Benutzer Robotik Einstein Avatar von SprinterSB
    Registriert seit
    09.06.2005
    Ort
    An der Saar
    Beiträge
    2.801
    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.
    Disclaimer: none. Sue me.

  10. #10
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    21.10.2005
    Ort
    Erde
    Alter
    50
    Beiträge
    1.195
    Ja sicher, Du hast recht.

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

Seite 1 von 4 123 ... LetzteLetzte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •