Festpunktarithmetik

[ogni42]

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]

Da hab ich direkt mal ein paar Fragen zu deinen Konstrukten O:)

--1--


(op1 == op2 == 0x80)


Ist gleichbedeutend mit


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

und nicht mit


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

oder


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

Ist das gewollt?

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


--2--
Die Constraints


: "=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:

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]

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



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 :oops: 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]

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

[SprinterSB]

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

Hi, hier meine build-options

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...


--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.


--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:

#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... :-b

[SprinterSB]

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).

:idea: Anstatt


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:


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]

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]

Das mit dem SBIW habe ich noch nicht ganze verstanden.

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


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]

Das Schnippsel

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

in pseudo bedeutet doch


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

was gleichbedeutend ist mit


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]

Ja sicher, Du hast recht.

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

[SprinterSB]

Nochwas zu Codegröße/Laufzeit:

IMHO wird eine Version mit normalen Funktionen (F-Version) keinen merklichen Vorteil an Flashverbrauch haben gegen eine Inline-Version (I-Version).

Grund: Es muss nicht nur Code für die Aufrufe erzeugt werden, sondern auch Code, um die callclobbered Register um einen Aufruf zu sichern und die Argumente/RetValue in die von der ABI dafür vorgesehenen Übergaberegister zu kopieren.

Ein Vergleich der beiden Versionen wäre dennoch interessant. Alle Implementierungen in den Header zu klatschen ist aber keine gute Idee, weil die Implementierungen in der F-Version dann mehrfach vorliegen, wenn die Fix-Arith in verschiedenen Modulen gebraucht wird.

Man könnte den Header so aufbauen:

#ifndef _FIX_ARITH_H_
...blabla

#ifdef SOME_SYMBOL
# define FIX_MEM_CLASS static inline // oder always_inline
#else
# define FIX_MEM_CLASS extern
#endif // SOME_SYMBOL

// prototypes
FIX_MEM_CLASS uint8_t foo (...);
...

#ifndef SOME_SYMBOL
#include "fix-arith.c"
#endif // !SOME_SYMBOL

...

fix-arith.c implementiert wie gewohnt und nur in der F-Version wird gegen fix-arith.o gelinkt. (Noch besser wäre ne feingranulierte Lib).

[ogni42]

Hier jetzt ein update. Nachdem ich zwei Versionen durcheinander gewürfelt hatte (Zeit für Subversion) ist jetzt hoffentlich alles im Lot

[SprinterSB]

Kontrollier das nochmal. Da gibt's einige Regressionen, zb

(a == b == c)

[ogni42]

Vermaledeites Hin- und herkopieren :( Als nächstes kümmere ich mich um einen subversion server.

[ogni42]

So, auf ein Neues.



Grund: Es muss nicht nur Code für die Aufrufe erzeugt werden, sondern auch Code, um die callclobbered Register um einen Aufruf zu sichern und die Argumente/RetValue in die von der ABI dafür vorgesehenen Übergaberegister zu kopieren.


Ich dachte, dass man zumindest das Retten/Restaurieren der Register durch die Option -mcall-prologues reduziert. Aber "Versuch macht kluch".

Hier jetzt die korrigierte Version.

[SprinterSB]

:75: "=d", "=d" &rarr; "=d", "=0"
:129: "=a" &rarr; "=&d"
:149: %A0 = ?
:236: "=&w" &rarr; "=&d"
:257: %1 ist kein IN-op
:266: "=w", "=w" &rarr; "=&d", "=0"
:281: %1 ist kein IN-op
:290: "=w", "=w" &rarr; "=&d", "=0"
:313: "=&a" &rarr; "=&r"
:344: "=&w" &rarr; "=&d"

[ogni42]

Hi,

vielen Dank. An ein paar Stellen habe ich Probleme/Fragen:

75, 266, 290
../fixedPointArithmetics.c:283: error: matching constraint not valid in output operand

236, 266, 344: erfordert m.E. "=w" wegen adiw bzw. sbiw Operation.

[SprinterSB]

Stimmt, da war was mit "=0"... hab grad keinen Compiler hier.

Dito mit "=w" bzw. "=&w"

Was mit nicht gefällt sind Konstrukte wie

: "=w" (result), "=w" (op1)
: "0" (op1), ...

Hier wüde ich lieber destruktiv auf op1 arbeiten, was ja auch dem Inhalt das asm entspricht.

Wenn man das so hinschreibt wie bisher, hat man zwar ne schönere C-Quelle, aber Magendrücken macht das schon.

Ausserdem belegt das unnötig eines der wertvollen w-Regs, von denen man nur 4 hat. Für deine Anwendung bleiben dann nur noch 2 Regs, Y wird vermutlich für den Frame verbraucht, so daß nur eines überbleibt.

zu -mcall-prologues:

Aus gcc-Sicht teilen sich die Register in (mindestens) 3 Gruppen:

-- fixed (wird nicht allokiert, zB r0, r1)
-- call saved (wird durch f() nicht zerstört, zB Y)
-- call clobbered (aka call used, f() hinterlässt nen Schweinestall, zB X, Z)

Falls eine Funktion ein call used Register verwendet, so muss sie dieses im Prolog sichern (push) und im Epilog wieder herstellen (pop).

Wenn das bei recht vielen Funktionen recht viele Register sind, dann kann man mit -mcall-prologues Platz sparen, weil Epilog und Prolog in eigene Funktionen ausgelagert werden. Diese Sicher-/Herstellfunktionen dauern aber recht lange, weil sie den Rundumschlag machen (müssen) und alle call clobbered register sichern und nicht nur die, welche die Funktion tatsächlich benutzt. -mcall-prologues wirkt also auf callees (aufgerufene) Funktionen.

Aus Sicht des Callers (Aufrufer) sieht das etwas anders aus. Hier bringt die Option nichts (ausser wenn die Funktion selber nen großen Prolog/Epilog hat und wir sie als callee betrachten).
Wenn der Caller eine Variable verwendet, die über einen Funktionsaufruf hinweg lebt, dann muss diese notwendigerweise call saved sein, trägt also u.U. zur Größe des Prolog/Epilog bei oder muss ständig zwischen call saved oder gar Frame (da lebt das Reg) und call used (parameter/ret-val) hin- und herkopiert werden.

Falls die Hardregs (GPRs) der Maschine nicht ausreichen, dann wird für die Funktion ein Frame angelegt und die überschüssigen Variablen leben im Frame. Von der Laufzeit her ist das übel, weil für jeden Zugriff ein Speicherzugriff notwendig ist. Zudem muss ein Framepointer (Y-Reg) angelegt werden, um in den Frame greifen zu können.

Man tut also gut daran, nicht allzu viele lokale Variablen zu haben. Wenn man zB ein lokales Array braucht, dann sollte man das als local static anlegen und nicht als local auto!

Ausserdem ist es günstig, möglichst viele leaf-Functions (Blätter) zu haben, also Funktionen, die keine andere Funktion aufrufen (nur callee sind, aber kein caller). Das kann dadurch gegeben sein, daß die Funktion keine Funktionen aufruft oder aller aufgerufenen Funktionen geinlinet werden oder dead Code sind, etc.

[ogni42]

Was mit nicht gefällt sind Konstrukte wie

Ich schau mal, was ich hinbekomme.

Bei den call-prologues muss ich halt einen Tod sterben. Derzeit ist Geschwindigkeit aber eher nicht mein Problem (zumindest nicht durch Funktionsaufrufe) da algorithmenbedingt in den Funktionen recht viel Zeit verbraucht wird. Sofern die Aufrufe auf fmacX zeitkritisch werden, pack' ich das in ein Macro.

[SprinterSB]

Für Codegröße lohnt es sich, die Saturierung auszulagern. Zumindest dann, wenn das öfter gebraucht wird, was ja wohl der Fall ist:


#include <avr/io.h>
#include <avr/interrupt.h>

#define inline __attribute__((always_inline))

#define MAX_FIX_VALUE 0x8001
#define MIN_FIX_VALUE 0x7fff

static inline uint8_t foo (uint8_t op1, uint8_t op2);
void __attribute__((naked)) saturate16 (void);

void saturate16 (void)
{
asm volatile ("; r27:r26 = sat(r1:r0), r1=0 " "\n\t"
"movw r26, r0" "\n\t"
"brvc 0f" "\n\t"
"ldi r26, lo8(%[max])" "\n\t"
"ldi r27, hi8(%[max])" "\n\t"
"brcc 0f" "\n\t"
"ldi r26, lo8(%[min])" "\n\t"
"ldi r27, hi8(%[min])" "\n"
"0:\tclr __zero_reg__" "\n\t"
"ret"
:: [max] "i" (MAX_FIX_VALUE), [min] "i" (MIN_FIX_VALUE) );
}

uint8_t foo (uint8_t op1, uint8_t op2)
{
uint16_t result;

asm volatile (
"muls %[op1], %[op2] " "\n\t"
"%~call saturate16 ; r27:r26 = sat(r1:r0), r1=0 "
: [result] "=x" (result)
: [op1] "a" (op1), [op2] "a" (op2)
);

return result;
}


uint8_t mul5 (uint8_t a, uint8_t b, uint8_t c, uint8_t d, uint8_t e)
{
uint8_t x = foo (a, b);

x = foo (x, c);
x = foo (foo (x, d), e);

return x;
}

SIGNAL (SIG_INTERRUPT0)
{
// all used GPRs are saved as desired :-)
foo (1, 2);
}

ergibt:


.file "fix.c"
.arch atmega8
__SREG__ = 0x3f
__SP_H__ = 0x3e
__SP_L__ = 0x3d
__tmp_reg__ = 0
__zero_reg__ = 1
.global __do_copy_data
.global __do_clear_bss
; GNU C version 3.4.6 (avr)
; compiled by GNU C version 3.3 20030226 (prerelease) (SuSE Linux).
; GGC heuristics: --param ggc-min-expand=99 --param ggc-min-heapsize=129491
; options passed: -fpreprocessed -mmcu=atmega8 -auxbase -Os
; -fverbose-asm
; options enabled: -feliminate-unused-debug-types -fdefer-pop
; -fomit-frame-pointer -foptimize-sibling-calls -funit-at-a-time
; -fcse-follow-jumps -fcse-skip-blocks -fexpensive-optimizations
; -fthread-jumps -fstrength-reduce -fpeephole -fforce-mem -ffunction-cse
; -fkeep-static-consts -fcaller-saves -freg-struct-return -fgcse
; -fgcse-lm -fgcse-sm -fgcse-las -floop-optimize -fcrossjumping
; -fif-conversion -fif-conversion2 -frerun-cse-after-loop
; -frerun-loop-opt -fdelete-null-pointer-checks -fsched-interblock
; -fsched-spec -fsched-stalled-insns -fsched-stalled-insns-dep
; -fbranch-count-reg -freorder-functions -fcprop-registers -fcommon
; -fverbose-asm -fregmove -foptimize-register-move -fargument-alias
; -fstrict-aliasing -fmerge-constants -fzero-initialized-in-bss -fident
; -fpeephole2 -fguess-branch-probability -fmath-errno -ftrapping-math
; -minit-stack=__stack -mmcu=atmega8

.text
.global saturate16
.type saturate16, @function
saturate16:
/* prologue: frame size=0 */
/* prologue: naked */
/* prologue end (size=0) */
/* #APP */
; r27:r26 = sat(r1:r0), r1=0
movw r26, r0
brvc 0f
ldi r26, lo8(-32767) ;
ldi r27, hi8(-32767) ;
brcc 0f
ldi r26, lo8(32767) ;
ldi r27, hi8(32767) ;
0: clr __zero_reg__
ret
/* #NOAPP */
/* epilogue: frame size=0 */
/* epilogue: naked */
/* epilogue end (size=0) */
/* function saturate16 size 20 (20) */
.size saturate16, .-saturate16
.global mul5
.type mul5, @function
mul5:
/* prologue: frame size=0 */
push r16
/* prologue end (size=1) */
mov r19,r22 ; b, b
mov r21,r18 ; d, d
mov r23,r24 ; , a
/* #APP */
muls r23, r19 ; , b
rcall saturate16 ; r27:r26 = sat(r1:r0), r1=0
/* #NOAPP */
movw r18,r26 ; result,
/* #APP */
muls r18, r20 ; result, c
rcall saturate16 ; r27:r26 = sat(r1:r0), r1=0
/* #NOAPP */
movw r18,r26 ; result,
/* #APP */
muls r18, r21 ; result, d
rcall saturate16 ; r27:r26 = sat(r1:r0), r1=0
/* #NOAPP */
movw r18,r26 ; result,
/* #APP */
muls r18, r16 ; result, e
rcall saturate16 ; r27:r26 = sat(r1:r0), r1=0
/* #NOAPP */
mov r24,r26 ; result, result
clr r25 ; <result>
/* epilogue: frame size=0 */
pop r16
ret
/* epilogue end (size=2) */
/* function mul5 size 27 (24) */
.size mul5, .-mul5
.global __vector_1
.type __vector_1, @function
__vector_1:
/* prologue: frame size=0 */
push __zero_reg__
push __tmp_reg__
in __tmp_reg__,__SREG__
push __tmp_reg__
clr __zero_reg__
push r18
push r19
push r26
push r27
/* prologue end (size=9) */
ldi r18,lo8(1) ; op1,
ldi r19,lo8(2) ; op2,
/* #APP */
muls r18, r19 ; op1, op2
rcall saturate16 ; r27:r26 = sat(r1:r0), r1=0
/* #NOAPP */
/* epilogue: frame size=0 */
pop r27
pop r26
pop r19
pop r18
pop __tmp_reg__
out __SREG__,__tmp_reg__
pop __tmp_reg__
pop __zero_reg__
reti
/* epilogue end (size=9) */
/* function __vector_1 size 24 (6) */
.size __vector_1, .-__vector_1
/* File "fix.c": code 71 = 0x0047 ( 50), prologues 10, epilogues 11 */

Sieht doch ganz gut aus.

Ich hoffe, ich verwirre dich nicht zu sehr :P

[ogni42]

Ich hoffe, ich verwirre dich nicht zu sehr Razz

Au contraire!
Ich lerne einiges dazu (auch Dank Deines schönen Inline-Assembler Artikels im Wiki).

Das mit dem Aufruf aus dem inline Assembler kannte ich noch nicht. Sehr chic! Damit die alten Ideen nicht verloren gehen packe ich das wahrscheinlich in ein neues File.

Ich tauche da zwar noch selber ein, aber auf die Schnelle: Wozu dient das r1 = 0 hinter r27:r26 = sat(r1:r0), r1=0 ?

[SprinterSB]

Das mit dem Aufruf aus dem inline Assembler kannte ich noch nicht. Sehr chic!

Ein solcher Funktionsaufruf innerhalb von asm ist transparent für gcc, d.g. er sieht die Funktion nicht, da sie ja nicht von C-Ebene aufgerufen wird. saturate16 von C aus aufzurufen ist sogar ein schwerer Fehler (überleg dir, warum).

Das unschöne an der Sache ist, daß man genau festlegen muss, in welchem Register der Wert ankommt, hier X. Dazu braucht man eine Registerklasse (also Constraint, hier "x"). Für 16-Bit-Werte ist das ok. Wenn Result allerdings nur ein 8-Bit-Wert wäre, dann muss im aufrufenden asm r27 geclobberd werden, damit gcc nicht auf die Idee kommt, result nach r27 zu reloaden! Man hat dann ein Register für nix verbraucht.

Für 8-Bit-Werte lohnt sich sowas hier vermutlich nicht, aber bei 16-Bit-Werten und vielen Aufrufen dürfte es zu einem deutlichen Code-Schrumpf führen. Selbst dann, wenn mehrere 16-Bit sat-Versionen gebraucht werden.


Wozu dient das r1 = 0 hinter r27:r26 = sat(r1:r0), r1=0 ?
Ist nur ein Kommentar, der sowohl auf C als auch auf asm Ebene sichtbar ist.

Falls es um den Code geht: In __zero_reg__ (r1) steht fast immer eine 0. Daher zB auch das clr __zero_reg__ in ISR-Prologues.

In größeren Funktionen ist es oft praktisch, die Konstante 0 zur Verfügung zu haben. Daher ist laut ABI (application binary interface) von avr-gcc in diesem Register immer die 0. Dieses Register ist (ebenso wie r0) ein fixed Register, daß heißt, gcc hat keine Vorstellung von diesen Registern und wird sie nie verwenden.

Das hört sich jetzt seltsam an, weil r1 und r0 in avr-gcc ja Verwendung finden. Allerdings tauchen diese Register in avr-gcc nur als Strings auf (ähnlich wie inline asm in C nur ein String ist) und gcc hat keine interne Vorstellung von den Registern.

Wenn also r1 einen anderen Wert bekommt (zB durch eine MUL), dann muss die Insn (oder inline asm), die das Register verändert hat, wieder den Wert 0 hineinschreiben. Das ist der Grund dafür, daß diese Insns als asm Befehl immer auch ein cli r1 enthalten und ein clobbern dieses Registers nicht den gewünschten Effekt zeigt, wie am Ende des Abschnitts

https://www.roboternetz.de/wissen/index.php/Inline-Assembler_in_avr-gcc#Clobbers

beschrieben.

[ogni42]

Falls es um den Code geht: In __zero_reg__ (r1) steht fast immer eine 0. Daher zB auch das clr __zero_reg__ in ISR-Prologues.


Das ist schon klar, aber: Nach dem Aufruf von muls steht in r1 das Ergebnis der Operation und wird ja auch so in saturate16 verwendet. Ist dann das r1=0 nicht irreführend?

[SprinterSB]

aber: Nach dem Aufruf von muls steht in r1 das Ergebnis der Operation und wird ja auch so in saturate16 verwendet. Ist dann das r1=0 nicht irreführend?

In C sähe das ja so aus:

foo_t fmul (foo_t a, foo_t b)
{
r1_r0 = a*b;
v = (|a*b| > 1); // oder so
saturate16 ();
return r27_r26;
}

// Inputs: r1_r0 und Overflow (v-Flag)
void saturate16 (void)
{
r27_r26 = sat16 (r0_r1, v);
r1 = 0;
}

saturate16 saturiert also nicht nur, sondern löscht zusätzlich r1. Dadurch entfällt das clr r1 im inline asm (wird kürzer) und daher der Kommentar r1=0 an saturate 16.

BTW: Wieso kann die Multiplikation überhaupt überlaufen? :-k

Wie ist da überhaupt die Darstellung der Fraction? Im Komplement oder als sign(a) : abs (a) ? Vermutlich ersteres, sonst wäre Strichrechnung ja recht aufwändig...

[ogni42]

Ah, ok.

Die Multiplikation kann nicht überlaufen. Die Sättigung ist ja nur bei den fadd, fsub und fmac Routinen drin. Die Darstellung ist im Comp_2.

Solche Ops kannte ich bisher nur von DSPs und dem MA16 (systolisches Feld). Bei vielen DSPs und dem MA16 ist die Sättigung für fmac aber IIRC in Hardware eingebaut.

[SprinterSB]

Und wozu das alles? Für PID-Regler oder so? Oder sin/cos?

Nette Spielwiese übrigens, hier der logarithmus dualis:


static inline uint8_t log_2 (uint8_t);

// log(x) / log(2) mit 1 <= x < 2
uint8_t log_2 (uint8_t x)
{
uint8_t log, cnt;
asm volatile ("; %[log] = log_2 (%[x]) " "\n\t"
"ldi %[cnt], 7" "\n\t"
"clr %[log]" "\n"
"0:" "\t"
"lsl %[log]" "\n\t"
"fmul %[x], %[x]" "\n\t"
"brcc 1f" "\n\t"
"ror r1" "\n\t"
"inc %[log]" "\n"
"1:" "\t"
"mov %[x], r1" "\n\t"
"dec %[cnt]" "\n\t"
"brne 0b" "\n\t"
"clr __zero_reg__"
: [log] "=r" (log), [x] "=a" (x), [cnt] "=d" (cnt)
: "1" (x)
);

return log;
}

[ogni42]

Bei mir im Moment im Wesentlichen für künstliche Neuronale Netze. Kann man aber auch für Filteroperationen in der Bildverarbeitung, FFT etc. gut einsetzen.

Schicke Lösung für den Log.

[SprinterSB]

künstliche Neuronale Netze

Ah. Kenn ich nur vom Hörensagen. Ich dachte, Neuronale Netze seien der Natur nachempfunden? Dort kann ich mir so harte Sachen wie einfach einen Wert abschneiden (Saturierung, clipping) schlecht vorstellen.

Wenn zwei Nervenzellen zB ihre Signale addieren, dann wäre folgendes doch viel "natürlicher":


+: [0,1] x [0,1] -> [0,1]
a + b := 1 - (1-a)*(1-b)


Für keine a, b ist das fast das gleiche wie a+b. Für größere a, b geht das schön langsam in die Sättigung und bleibt immer in [0,1]. Es ist monoton in beiden Argumenten, symmetrisch, assoziativ(!), glatt (beliebig oft diff'bar) und leicht zu berechnen.

Zudem geht keine Information verloren. Bei einem saturierten + kann es sein, daß a+b=a+c gilt aber daraus folgt *nicht*, daß b=c ist. Für das weiche + ist das der Fall, zumindest wenn a im Innern des Intervalls ist.

Man kann also sogar Inverse (also -) definieren und es gibt ein eindeutiges Neutrales (die 0), was bei einer normalen Saturierung nicht geht. Wenn der Wert oben angeschlagen ist, dann gibt es kein Zurück mehr...

[ogni42]

Die Idee hinter den meisten künstlichen Neuronalen Netzen ist, dass die Ausgabe von Neuronen mit einem synaptischen Gewicht multipliziert werden (entsprechend der Stärke der Verbindung zwischen zwei Nervenzellen). Die Summe aller Ausgaben der Vorgängerneuronen multipliziert mit den synaptischen Gewichten ist die Eingabeaktivierung des aktuellen Neurons. Das läßt sich sehr schön auf eine Matrixmultiplikation abbilden (nxm, mit n=Anzahl Neuronen der Schicht l-1 und m=Anz. N. der Schicht l) Für ein Neuron ergibt sich dessen Ausgabe aus der Stärke der Aktivierung am Eingang und einer Aktivierungsfunktion (z.B. tanh).

Ab einem gewissen Wert (positiv oder negativ) verändert sich die Aktivierung am Ausgang nur noch marginal. Daher funktioniert die Sättigung sehr gut.

Deine Formel setzt stets positive Aktivierungen voraus. Es gibt aber auch negative (Inhibition). Da fände sich vielleicht eine ähnliche Formel die [-1, 1[ x [-1, 1[ -> [-1, 1[ bewirkt, aber in der Regel reicht die einfache Sättigung aus (und ist schneller zu berechnen).

[SprinterSB]

Deine Formel setzt stets positive Aktivierungen voraus. Es gibt aber auch negative (Inhibition). Da fände sich vielleicht eine ähnliche Formel die [-1, 1[ x [-1, 1[ -> [-1, 1[ bewirkt, aber in der Regel reicht die einfache Sättigung aus (und ist schneller zu berechnen).

Ja stimmt. Das additiv Inverse zu a ist a/(1-a) und das ist kleiner 0, so daß man die negativen Zahlen hinzunehmen müsste.

Em Endeffekt ist es ja nur eine Transformation von [0, oo] auf [0, 1] und wäre dann eine Trafo (bzw. Isomorphismus) von R nach [-oo, 1].

Ich will ja keine neue Theorie aufstellen (wenn, wär sie nicht neu und gibt's bestimmt schon). Wollte einfach mal ein bisschen nachdenken drüber :-)

Ganz nett an [0,1] auch, daß man da (zumindest einen Teil) der Bool'schen Algebra hat: Mit

a AND b = ab
a OR b = a+b-ab
NOT a = 1-a

Hat man zB die De-Morgan'schen Regeln. Ist vielleicht eher was für die Fuzzi-Leute...

Mit tanh ist es natürlich viel simpler und man hat die "weiche" Sättigung unanhängig von der eigentlichen Operation.

[SprinterSB]

Hast du deine Lib inzwischen feingeschliffen? Würd mich auch interessieren :P