Hallo,

wie ich schon schrieb baue ich zur Übung gerade an einem kleinen eigenen
BASIC-Interpreter für ATmegas. Ursprünglich wollte ich darin
float-Zahlen verarbeiten können, aber float war zu fett. Also Fixpoint,
aber im Web fand ich keine fertige Bibliothek, also schrieb ich selber
ein paar rudimentäre Fixpoint-Arithmetik-Routinen. Ich habe den
Quellcode hier als Anhang mitgeschickt, und sie zum Testen (wiedermal)
in ein Apfelmännchenprogramm verpackt.

Bitte schaut Euch das mal an.

Meine Fixpoint-Routinen sind etwa um 3KB kleiner als die entsprechenden
float-Routinen, und um ein vielfaches schneller, ABER sie sind höllisch
ungenau, und auf einen Wertebereich von -32767.000 bis 32767.000
begrenzt.

Ein Apfelmännchen in Buchstabengrafik kann man damit aber einigermaßen
gut berechnen. Später poste ich dasselbe nochmal mit float-Arithmetik
zum Vergleich.

viel Spaß mit dem Code,
Grüße Ralf

Darf ich mäkeln?

In fixpointtoa()

      size_t len = strlen (str);
      str [len++] = '.';

      uint16_t p = nk * 10;
      uint16_t t = 1024;
   
      while (p < t)
      {
         str [len++] = '0';
         p *= 10;
      }

      itoa (snk, str + len, 10);   
   }
   
   return result;
} 

Den len brauchst du, da du nicht weist, wie lange der String
ist, den der vorhergehende itoa erzeugt hast. Allerdings
hängst du an den String nur noch Zeichen dran. Das len
brauchst du eigentlich nicht wirklich:

   // Das Ende des bisherigen Strings suchen
   while( *str++ )
     ;

   *str++ = '.';

   uint16_t p = nk * 10;
   uint16_t t = 1024;
 
   while (p < t)
   {
      *str++ = '0';
      p *= 10;
   }

   itoa (snk, str, 10);   

Für atofixpoint() solltest du dir mal die Funktion strtol
anschauen. Die konvertiert eine Ganzzahl und liefert die
Position im String an der sie abbrechen musste. Dadurch
könntest du dir das auseinanderpfriemeln des Strings in
einen Vorkomma und einen Nachkommaanteil sparen.
Alternativ könnte man auch für den Vorkommaanteil
Folgendes machen:
atoi() mal auf den Vorkommaanteil im String ansetzen und
den mal (inklusive Vorzeichen) umwandeln lassen. Danach
im String nach einem '.' suchen und dahinter mit den
Nachkommastellen wie gehabt weiter machen.

Ich würde wahrscheinlich letzteres wählen, da atoi()
sowieso schon verwendet wird.

Jetzt muss ich nur noch ergründen was es mit den
17/16 auf sich hat.

Aus Symetriegründen, ohne gross darüber nachgedacht zu
haben:

fixpointtoa

      snk = (nk*29)/28;  //--- 512 -> 500 ---
      snk = (snk*17)/18; //--- gut genug so ---

atofixpoint

         sr = (sr*17)/16; //--- 500 -> 512 ---
         sr = (sr*28)/29; //--- gut genug so ---

Hmm das eine mal sind es 17/18, in der Umkehrung aber
nur noch 17/16. Eigentlich hätte ich da aus Symetriegründen
18/17 erwartet.

Aber wie gesagt: Ist mir nur aufgefallen und ich hab noch
nicht darüber nachgedacht, ob da ein tieferer Sinn dahinter
steckt (irgendwelche Rundungssachen).

Hi,

Dies
>snk = (nk*29)/28;  //--- 512 -> 500 ---
>      snk = (snk*17)/18; //--- gut genug so ---

und das
>         sr = (sr*17)/16; //--- 500 -> 512 ---
>         sr = (sr*28)/29; //--- gut genug so ---

habe ich mit einem Brute-Force-Hilfsprogramm ermittelt. Es suchte nach
den geeignetsten Faktoren und Divisoren, mit denen man mit
Integer-Multiplikation und Integer-Division ohne allzugroße Verluste von
512 auf 500 kommt und umgekehrt.

Das ist meine Lösung zum Umwandeln der 10Bit Nachkommastellen nach
Dezimal und zurück. Wahrscheinlich gibts auch andere Verfahren, die sind
mir aber nicht eingefallen.

und dann noch
>Darf ich mäkeln?

klaro, (u.a.) dehalb hab ich den Code hier gepostet.

>str [len++] = '0';
und
>*str++ = '0';

ich habs nicht disassembliert, wird die zweite Zeile tatsächlich zu
effektiverem Code compiliert, oder ist der gcc inzwischen so schlau,
dass beides in etwa gleichen Assemblercode liefert? Ehrlichgesagt würde
ich meine Variante mit dem Array-Index bevorzugen, weil ich den Eindruck
habe, solchen Code bei späterem Reinschauen wieder leichter durchblicken
zu können, als Code mit "wandernden" Pointern. Das ist aber reine
Ansichtssache (hoffentlich).

Grüße Ralf

Ralf Rosenkranz wrote:

>>str [len++] = '0';
> und
>>*str++ = '0';
>
> ich habs nicht disassembliert,

Ich auch nicht :-)

> wird die zweite Zeile tatsächlich zu
> effektiverem Code compiliert, oder ist der gcc inzwischen so schlau,
> dass beides in etwa gleichen Assemblercode liefert? Ehrlichgesagt würde
> ich meine Variante mit dem Array-Index bevorzugen, weil ich den Eindruck
> habe, solchen Code bei späterem Reinschauen wieder leichter durchblicken
> zu können, als Code mit "wandernden" Pointern.

Na ja. In dem Fall mach es schon einen Unterschied.
Da ist ja auch noch der Aufruf von strlen() der dann
wegfallen würde. Statt dessen kommt dann die Schleife, aber
die Subtraktion im strlen() die ausrechnet wieviele Zeichen
das jetzt sind, würde wegfallen, weil, wie gesagt: Im Grunde
braucht diese konkrete Zahl keiner.

> Das ist aber reine
> Ansichtssache (hoffentlich).

Ich habs nur vorgeschlagen, weil du am Anfang das hier
machst :-)

   if (f < 0)
   {
      f = - f;
      *str++ = '-';
   }

>Ich habs nur vorgeschlagen, weil du am Anfang das hier
>machst :-)
>
>   if (f < 0)
>   {
>      f = - f;
>      *str++ = '-';
>   }

oh, das hab ich gemacht? - tatsächlich #-)

Grüße Ralf

die oben angekündigte float-Version wird noch etwas dauern, denn ich
hatte leider großes Pech: Mein AVR-Dragon ist heute abend "abgeraucht"
(ganau so wie sich das für einen Drachen gehört).

Ich hatte nichts weiter gemacht als das Programmierkabel abzuziehen, und
wollte gleich den Rechner ausschalten, als das Teil plötzlich qualmte.
Vielleicht war elektrostatische Aufladung schuld, die vielleicht ein
LatchUp oder so verursachte, oder vielleicht war es ein winziger
Matallkrümel (der Dragon ist nämlich nackt), der sich in die Elektronik
verkrümelt hatte, vielleicht auch was ganz anderes.

Jedenfalls ist mein schönes Programmiergerät jetzt kaputt, und ich muß
warten, bis ich ein neues bekomme. Danach dann gibts hier die
float-Version vom Apfelmännchenprogramm.

Grüße Ralf

Hallo nochmal,

hier ist nun die äquivalente "float"-Version des Apfelmännchenprogramms.
Man kann sehen, dass das Ergebnis gegenüber der Fixpoint-Version
deutlich symmetrischer wird, aber auch dass es etwa fünfmal so lange
dauert, bis es fertig ist.

genau wie in dem anderen Programm habe ich "*", "/" und "atofloat"
ausgelagert, damit beide vergleichbar bleiben. Die Funktion floattoa
wird hier nicht verwendet, aber ich dachte, eventuell kann sie jemand
gebrauchen (vielleicht ist sie aber auch viel zu umständlich
programmiert, weiss nicht).

@Karl heinz Buchegger
in den beiden Funktionen atofloat und floattoa gibts bestimmt auch
wieder etwas zum mäkeln zu finden ;))

Das Programm müßte auf diversen AVRs laufen können, getestet habe ich
ATmaga8, ATmega168 und ATmega32. Als Terminal-Programm benutzte ich
Windows-Hyperterminal mit 9600Baud, 8,n,1 keine Flusssteuerung.

Würde mich interessieren, ob jemand die beiden Programme mal ausprobiert
hat ...

Grüße Ralf

fünfmal so lange?

Schau mal in http://www.avrfreaks.net/ nach meinem Projekt "float
arithmetics" und binde die Quellen _addsf3.s _mulsf3.s _divsf3.s und
_floatsi.s in Dein Projekt ein.

@Hans-jürgen Herbert,

> Schau mal in http://www.avrfreaks.net/ nach meinem Projekt "float
> arithmetics" und binde die Quellen _addsf3.s _mulsf3.s _divsf3.s und
> _floatsi.s in Dein Projekt ein.

ok, soweit bin ich gekommen:
- http://www.avrfreaks.net/ aufgerufen
- unter search "float arithmetics" eingegeben
- einiges gefunden aber wohl nicht das richtige dabei
- ah, da gibts ja auch einen Reiter "projects", draufklick
- passwort nötig, also registriert
- jetzt dort nochmal gesucht und gefunden
http://www.avrfreaks.net/index.php?module=Freaks%2...
- gedonloadet, ausgepackt und ... - viele Verzeichnisse
- _addsf3.s gesucht und unter "home\cc\lq" gefunden
- doku unter home/html/hjh/cc/deutsch/lq/_addsf3.htm gelesen

... aber weiß trotzdem nicht weiter.
Wie verwende ich _addsf3.s _mulsf3.s _divsf3.s und _floatsi.s?
(Und wofür sind all die anderen Files?)

Grüße Ralf

Die Dateien sind für avr-gcc
Einfach einbinden, wie eigene Quellen, dann werden die entsprechenden
Programme aus der libc (oder ist es libm) nicht mehr vom Linker
angebunden.

Dafür habe ich die entsprechenden Programme  Quellen  Objects im
makefile und in makedefs angegeben.

Dia anderen Files hatte ich zum Testen gebraucht. Falls jemand etwas
verbessern (beschleunigen, korrigieren) will, kann er die Testumgebung
mitbenutzen.

1.
Das Multiplikationsprogramm rechnet 63.999 * 63.999 = 4092 anstatt
4095.872001

31.999 (00007FFF) * 31.999 (00007FFF)  = 1022.000 sollte :1023.9375
ERROR
63.999 (0000FFFF) * 63.999 (0000FFFF)  = 4092.000 sollte :4095.8750
ERROR
0.124 (0000007F) * 8191.999 (007FFFFF)  = 767.997 sollte :1015.9998
ERROR



2.
Die Zahlenumwandlung kann statt durch Verschieben auch durch
Multiplizieren mit

#define fixpointEins (1<<pixpointFractShift) // bei 10 ist das 1024

erfolgen


3. Die Division durch 0 könnte man abfangen.
Die Bitzählerei sollt ersetzt werden durch eine Suche nach Bereichen


4. fixpointtoa

16 bit sind nicht genug für die Vorkommastellen

uint16_t vk = f >> pixpointFractShift;

sollte sein

uint32_t vk = f >> pixpointFractShift;


Die Umwandlung der Vorkommastellen geht schneidet sonst die obersten 6
bits ab.

5. Die Division macht folgende Beispiele falsch

8191.999 (007FFFFF) / 0.006 (00000007)  = 2097151.999 sollte
:1.1983725E+06 ERROR
131071.999 (07FFFFFF) / 0.124 (0000007F)  = 0.009 sollte :1.0568325E+06
ERROR
131072.000 (08000000) / 32.000 (00008000)  = 0.000 sollte :4096 ERROR


6. Die Umwandlung der Nachkommastellen nach ASCII durch Multiplikation
finde ich schöner



7. Das Stück

b = atofixpoint ("1.1"); b > atofixpoint ("-1.2"); b = b - atofixpoint
("0.1")

kann ersetzt werden durch

b = (fixpoint)(1.1/fixpointEins) ; b > (fixpoint)(-1.2/fixpointEins) ; b
= b - (fixpoint)(-0.1/fixpointEins)


Was macht der Compiler avr-gcc daraus?
       for (b = floatToFixpoint(1.1); b > floatToFixpoint(-1.2); b = b -
floatToFixpoint(0.1))
     648:  26 e6         ldi  r18, 0x66  ; 102
     64a:  34 e0         ldi  r19, 0x04  ; 4
     64c:  40 e0         ldi  r20, 0x00  ; 0
     64e:  50 e0         ldi  r21, 0x00  ; 0
     650:  2d a7         std  Y+45, r18  ; 0x2d
     652:  3e a7         std  Y+46, r19  ; 0x2e
     654:  4f a7         std  Y+47, r20  ; 0x2f
     656:  58 ab         std  Y+48, r21  ; 0x30
Weil alles zur Compilierzeit schon berechnet werden kann
Schneller gehts nur noch in Assembler



Anwendungen von Festkommazahlen.
Ich stelle mir vor, dass Festkommazahlen in Berechnungen von
Werten verwendet werden, die vom ADC hereingelesen wurden.
0Volt = 0 = -40 grad C
2.56Volt = 32767 = 160 grad C
Vielleicht mache ich dafür mal einige Festpunkt - Programme.

@Hans-jürgen Herbert

oops, Du hast mein Programm ja radikal umgeschrieben. Und jede Menge
Rechenfehler gefunden, wie ich sehe. Das schaue ich mir später noch
einmal im Detail an, das braucht wohl mehr Zeit.

Das meine Fixpoint-Routinen ungenau sind, hatte ich schon zu Anfang
geschrieben:

> ... ABER sie sind höllisch ungenau,
> und auf einen Wertebereich von
> -32767.000 bis 32767.000 begrenzt.

Mein Ziel war es gewesen, mit maximal vier Byte beim Rechnen mit meinen
Fixpointzahlen auszukommen, und da bei Multiplikation und Division die
Zwischenergebnisse recht groß werden können, habe ich den Wertebereich
auf o.g. int-Bereich begrenzt, und habe die oberen sechs Bit für große
Zwischenergebnisse reserviert. Es war mir wichtig "int64_t" komplett zu
vermeiden, da ich Platz sparen musste. Unter diesen Gesichtspunkten sind
meine Fixpointroutinen gar nicht mal so schlecht.

später noch mehr ...

Grüße Ralf

Hans-jürgen Herbert wrote:
> fünfmal so lange?
>
> Schau mal in http://www.avrfreaks.net/ nach meinem Projekt "float
> arithmetics" und binde die Quellen _addsf3.s _mulsf3.s _divsf3.s und
> _floatsi.s in Dein Projekt ein.

Hmm.
Die Timing Zahlen sind ja echt beeindruckend.

Ne blöde Frage: Wo liegt der Pferdefuss?

Ich meine: Es muss doch einen Grund geben, warum die
original gcc Funktionen im Vergleich dazu alt aussehen.

Ne andere Frage: Warum werden die gcc-Funktionen nicht durch
deine ersetzt?

1. hat mir Jörg Wunsch im avrfreak.net geantwortet, dass die float-
Arithmetic gerade umgearbeitet wird.
Wir schauen uns dann die nächste Version 1.5 an.

2. Der größte Teil der Zeitersparnis liegt am Normieren nach der
Rechnung.
Weil ich nicht EIN Normierungsprogramm für alle 5 Programme benutze, ist
die Normierung für mul  div  add unterschiedlich.
(Nach Addition KANN das Ergebnis nicht kleiner werden als eine der
Zahlen - also braucht nur 0 oder 1 mal nach rechts geschoben werden).

Die Diskussion über die float-Programme wird ab jetzt im Forum "GCC",
unter "float arithmetic" weitergeführt.

> ... ABER sie sind höllisch ungenau,
> und auf einen Wertebereich von
> -32767.000 bis 32767.000 begrenzt.

hatte ich übersehen.

Hinweis zu fixpointMult() (Dein Original): beim Bitzählen von links
anfangen und beim ersten gesetzten Bit aufhören. Dann vor dem
Multiplizieren um 32-nbit oder 32-nbit-1 nach rechts schieben. Dann
sollte es besser klappen.
und sollte auch schneller werden als 64-Bit-Mutiplikation.

Oder Du schreibst ein Assemblerprogramm das 32 bit x 32 Bit rechnet,
dann kommen automatisch 64 bit heraus. (grundsätzlich hat das Ergebnis
einer Multiplikation immer erst doppelt so viele Bits wie die Operanten)

Wenn du schon am Bit-Verschieben bist, dann kannst Du gleich die Zahlen
addieren. Das IST dann das Multiplikationsprogramm: 32 bedingte
Additionen

Übrigens: zum Vortesten hab ich den normalen PC-Compiler benutzt. Geht
schneller. Erst danach für AVR übersetzt.
Drum die Header-#include, die Du nicht brauchst.


Gruß

Anbei meine Routinen zur Fixpoint-Arithmetik. 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.

(header kommt in separatem Posting)

hier der header

!!! Wow !!!

Sauberer inline-Code,  sauber dokumentiert.

Könnte man als Beispiel in das AVR gcc Tutorial übernehmen.
Und auch in ein (noch nicht vorhandenes) Dokumentations Tutorial.

Vielen Dank!

Gruß, Stefan

Danke für die Blumen :) Bevor das weiter kommuniziert wird, würde ich
mich freuen, wenn die Assembler-Experten mal drüber schauen würden. Ich
habe die zwar ausgiebig getestet, aber fremde Augen finden manche Fehler
besser als man selbst.

(Hab's auch mal im Roboternetz hinterlegt. Ich weiss - crossposting =
pfiu, aber so schauen vielleicht mehr Leute drüber und die Qualität
steigt).

Eine Frage:

Deine Routinen machen ja alle signed-Arithmetik. Wäre es nicht besser,
die Variablen-Definitionen entsprechend anzupassen, also:

int8_t, int16_t

Zum Einen ist die Lesbarkeit besser, zum Anderen kann man die Zahlen
auch besser vergleichen: ein

  int8_t my_fix_pos = 0x01;
  int8_t my_fix_neg = 0xFF;

  if (my_fix_pos > my_fix_neg){
  }

würde dann funktionieren.

Ev. wäre auch eine eigene Variablendefinition (fixp8_t, fixp_16_t,
ufixp_8_t, ufixp16_t) ganz sinnvoll. Dazu könnte vielleicht Jörg seinen
Senf dazugeben?!

Viele Grüße, Stefan

Ja, das mit den typedefs macht Sinn. Allerdings bringen es m.E. nur die
signed typen, also fixp8_t und fixp16_t. Da die Multiplikationsroutinen
immer Signed sind (gilt für Fließkommazahlen ja genau so).

Im Roboternetz hat SprinterSB schon ein paar Bugs gefunden. Ich bin
bereits bei der Korrektur und poste dann den Code (bzw. den Link zum
Thread) sobald alles fertig ist.

Ingo Elsen wrote:
> Ja, das mit den typedefs macht Sinn. Allerdings bringen es m.E. nur die
> signed typen, also fixp8_t und fixp16_t. Da die Multiplikationsroutinen
> immer Signed sind (gilt für Fließkommazahlen ja genau so).
>
> Im Roboternetz hat SprinterSB schon ein paar Bugs gefunden. Ich bin
> bereits bei der Korrektur und poste dann den Code (bzw. den Link zum
> Thread) sobald alles fertig ist.

ich meine natürlich in den hier angegebenen Routinen. Die Assembler
Instruktionen gibt es auch unsigned und signed mit unsigned. Mal sehen
ob das ergänzenswert ist.

Im vorliegenden Code muss allerdings uint8_t bzw. uint16_t verwendet
werden, da sonst der Compiler (berechtigerweise) bei der Überlaufprüfung
meckert.

Vielleicht kannst Du ein paar Anwendungsfälle auflisten für die die
anderen Routinen Sinn machen. Die Funktionen sind aus einer
Signalverarbeitungsanwendung geboren, bei der die Fixpunktwerte immer
vorzeichenbehaftet sind.

>Vielleicht kannst Du ein paar Anwendungsfälle auflisten für die die
>anderen Routinen Sinn machen. Die Funktionen sind aus einer
>Signalverarbeitungsanwendung geboren, bei der die Fixpunktwerte immer
>vorzeichenbehaftet sind.

Z.B. das Multiplizieren von Faderwerten am Mischpult. Praktisch ist es
dort, wenn man einen Wertebereich hat, der die 1.0 mit einschliesst.
Dann ergeben mehrere Multiplikationen von 100% Werten (== 1.0) am Ende
wieder 100% als Ergebnis. Also:

Kanalfader  Gruppenfader  Masterfader = Ergebnis

Weil mit VZ die 1.0 nicht mehr im Wertebereich ist, wird das Endergebnis
nach jeder Berechnung einen Tick kleiner sein.

Aber mach Dir keinen Kopf deswegen, wer das braucht, hat ja jetzt ein
gutes Beispiel, wie er es implementieren kann :-))

Kann S
Viele Grüße, Stefan

Noch eine andere Frage:

  "brcc 0f"    "\n\t"

Ist das 0f das handberechnete Sprungziel? Warum nicht per Label?


Viele Grüße, Stefan

Labels muss man im inline assembler entweder per textersetzung
konstruieren lassen oder man nimmt einfache zahlen plus sprungrichtung
(forward, backward) .
Also 0f (label '0' in Vorwärtsrichtung.

Ah, das mit dem

> (forward, backward) .

war mir neu. Ich kannte bisher nur diese

> "L_dl2%=:" "\n\t"

Definition aus dem ACR-libc Manual. Danke!


Gruß, Stefan

hier ist noch (als kleiner Nachtrag nach Monaten) eine neuere Version
der "Fixpoint-Arithmetik in C", diesmal nur das ".c" und das ".h" File,
ohne Testprogramm. In der Februar-Version waren noch einige Bugs drin,
jetzt sind es weniger.

Nochmal zur Erinnerung: Die Festkomma-Zahlen dieser Lib belegen 32 Bit,
mit zehn Bit als Nachkommastellen. Der Wertebereich ist -32767.0xx bis
32767.0xx. Die oberen (nur anscheinend unbenutzten) Bits werden in den
Berechnungen gebraucht. Das ".0xx" bedeutet, dass man bei der Umwandlung
von und nach Strings zwar drei dezimale Nachkommastellen zu sehen
bekommt, die letzten beiden Stellen aber eher als Pi mal Daumen Werte
anzusehen sind.

zur Umwandlung von und nach int16 gibt es:
int16ToFixpoint, fixpointToInt16,

zur Umwandlung von und nach Strings gibt es:
atofixpoint, fixpointtoa

und gerechnet wird hiermit:
fixpointAdd, fixpointSub,
fixpointMult, fixpointDiv,
fixpointSqr, fixpointSqrt

Wegen der geringen Zahl an Nachkommabits eignet sich diese Lib nur für
Anwendungen, wo es auf exakte Rechenergebnisse nicht so sehr ankommt.
ZB. bei solchen Fällen, bei denen Integer allein nicht ausreichen würde,
oder die float-Lib zu schwergewichtig wäre, könnte man es mal mit dieser
FixPointLib probieren. Würde mich über Rückmeldung freuen, wenns jemand
mal benutzt hat ...

Grüße Ralf