Konstanten im Flash

International Deutsch
1

Hi,

ich hatte früher, bis vor ca. 12 Jahren, mit AVR-ASM gebastelt und jetzt vor 2 Monaten bin ich wieder mit der Arduino-IDE langsam in die Thematik eingestiegen. Habe natürlich vieles vergessen und die Arduino-IDE ist mir immer noch neu.
Für Bewegungs-Animationen (LED-Strip) möchte ich eine schnelle Sinus-Funktion in den ATMega 32U4 einbauen welche per Gradzahl einen Multiplikator zurück gibt.
Beim kramen in meiner Bibliothek von damals habe ich folgendes gefunden:

GetSC3:	lsl	WinkelL
	ldiw	z,SinCosTab*2
	add	zl,WinkelL
	adc	zh,null
	lpmw	SinCos
	ret

SinCosTab:
.dw 0
.dw 572,1144,1715,2286,2856,3425,3993,4560,5126,5690
.dw 6252,6813,7371,7927,8481,9032,9580,10126,10668,11207
.dw 11743,12275,12803,13328,13848,14365,14876,15384,15886,16384
.dw 16877,17364,17847,18324,18795,19261,19720,20174,20622,21063
.dw 21498,21926,22348,22763,23170,23571,23965,24351,24730,25102
.dw 25466,25822,26170,26510,26842,27166,27482,27789,28088,28378
.dw 28660,28932,29197,29452,29698,29935,30163,30382,30592,30792
.dw 30983,31164,31336,31499,31651,31795,31928,32052,32166,32270
.dw 32365,32449,32524,32588,32643,32688,32723,32748,32763,32768

Wie bekomme ich es mit der Arduino-IDE hin die Tabelle wie oben in den Flash zu schreiben und, vor allem, dann darauf zuzugreifen.
Kann mir dabei jemand helfen?
Wenn ich das habe, sind die Codes für die Auswertungen für die Vorzeichen und die Tabelle zur Nutzung für Sinus und Cosinus ein Klacks. Nur die Arduino-IDE stellt mir gerade ein Bein.

Vielen Dank im Voraus

2

Haribo68:
Wie bekomme ich es mit der Arduino-IDE hin die Tabelle wie oben in den Flash zu schreiben und, vor allem, dann darauf zuzugreifen.

Guck mal hier (unten, Abschnitt „knapper Speicher“). Vielleicht hilft das.

Gruß

Gregor

3

OK, vielen Dank!
Werde ich mir mal reinziehen und hoffentlich nutzt es keinen RAM als Puffer.

MfG
Andi

4 
const uint16_t sTable[90] PROGMEM = {
  572, 1144, 1715, 2286, 2856, 3425, 3993, 4560, 5126, 5690,
  6252, 6813, 7371, 7927, 8481, 9032, 9580, 10126, 10668, 11207,
  11743, 12275, 12803, 13328, 13848, 14365, 14876, 15384, 15886, 16384,
  16877, 17364, 17847, 18324, 18795, 19261, 19720, 20174, 20622, 21063,
  21498, 21926, 22348, 22763, 23170, 23571, 23965, 24351, 24730, 25102,
  25466, 25822, 26170, 26510, 26842, 27166, 27482, 27789, 28088, 28378,
  28660, 28932, 29197, 29452, 29698, 29935, 30163, 30382, 30592, 30792,
  30983, 31164, 31336, 31499, 31651, 31795, 31928, 32052, 32166, 32270,
  32365, 32449, 32524, 32588, 32643, 32688, 32723, 32748, 32763, 32768
};

void setup() {
  Serial.begin(250000);
  for (byte i = 0; i < 90; i++) {
    Serial.print(i);
    Serial.print(F(" Grad "));
    Serial.println(pgm_read_word_near(&sTable[i]));
  }
}
void loop() {}

0 Grad 572
1 Grad 1144
2 Grad 1715
3 Grad 2286
4 Grad 2856
5 Grad 3425
6 Grad 3993
7 Grad 4560
8 Grad 5126
9 Grad 5690
10 Grad 6252
11 Grad 6813
12 Grad 7371
13 Grad 7927
14 Grad 8481
15 Grad 9032
16 Grad 9580
17 Grad 10126
.....

:wink:

5

Whandall:
const uint16_t sTable[90] PROGMEM

Das haut wohl nicht so ganz perfekt hin, mit der Unterschlagung von Null als Anfangswert.

Der Threadstarter hat eine Tabelle mit 91 Werten gepostet, weil er offenbar den Sinus von 0° bis 90° einschließlich nachschlagen möchte, und dazu braucht er 91 Werte in der Nachschlagetabelle. Du hast in Deinem PROGMEM Array den Wert 0 unterschlagen, der im Ausgangsposting noch enthalten war.

6

Es sollte das Prinzip gezeigt werden, die Null habe ich unterschlagen, stimmt.

Problematischer erscheint mir der letzte Wert von 32768 als einzig negativer.
Die Tabelle könnte also ein Bit genauer sein.

const uint16_t sTable[90] PROGMEM = {
  572, 1144, 1715, 2286, 2856, 3425, 3993, 4560, 5126, 5690,
  6252, 6813, 7371, 7927, 8481, 9032, 9580, 10126, 10668, 11207,
  11743, 12275, 12803, 13328, 13848, 14365, 14876, 15384, 15886, 16384,
  16877, 17364, 17847, 18324, 18795, 19261, 19720, 20174, 20622, 21063,
  21498, 21926, 22348, 22763, 23170, 23571, 23965, 24351, 24730, 25102,
  25466, 25822, 26170, 26510, 26842, 27166, 27482, 27789, 28088, 28378,
  28660, 28932, 29197, 29452, 29698, 29935, 30163, 30382, 30592, 30792,
  30983, 31164, 31336, 31499, 31651, 31795, 31928, 32052, 32166, 32270,
  32365, 32449, 32524, 32588, 32643, 32688, 32723, 32748, 32763, 32768
};

void setup() {
  Serial.begin(250000);
  for (byte i = 0; i <= 90; i++) {
    Serial.print(i);
    Serial.print(F(" Grad "));
    Serial.println(i ? pgm_read_word_near(&sTable[i - 1]) : 0);
  }
}
void loop() {}

0 Grad 0
1 Grad 572
2 Grad 1144
3 Grad 1715
4 Grad 2286
5 Grad 2856
6 Grad 3425
7 Grad 3993
...
83 Grad 32524
84 Grad 32588
85 Grad 32643
86 Grad 32688
87 Grad 32723
88 Grad 32748
89 Grad 32763
90 Grad 32768
7

Ja, die 32768 könnten ein Problem werden welche ich auch auf 32767 machen kann.
Vielleicht ändere ich es auch von 0 bis 127/128, LEDs sind ja nicht so fein aufgelöst ^^
Der Code von damals war für AVR-ASM und für Kreis- und glaucbe auch die ersten Ansetze für 3D-Funktionen.
Wahrscheinlich wars mir dann zu hoch geworden und dann war schluss... ^^
Hatte mir damals einiges an kleine Makros gebastelt, sowas wie ADDW, ADDL, SUBIW, MULW, Register zusammengefast etc. um mir das Leben in ASM zu erleichtern und vielleicht hatte ich, da ja in ASM und jeder Takt bekannt ist, das mit LONG gerechnet bzw. hatte auch Makros wie MUL24, also 3 Register für einen Wert.

8

Whandall:
Problematischer erscheint mir der letzte Wert von 32768 als einzig negativer.
Die Tabelle könnte also ein Bit genauer sein.

Wie meinen?

Ein "unsigned" Datentyp ist NIE negativ.

Und uint16_t reicht zur Aufnahme von Zahlen bis zu 65535 aus, da ist 32768 überhaupt kein Problem.

9

Da das Sinuswerte werden sollen, also von -1 bis +1, signed,
finde ich die Ver(sch)wendung des obersten Bits schon relevant.

10

Das sind sowieso erst mal Werte zum rechnen über 0.
Nach dem rauspicken wird je nach Eingangswert und ob Sinus oder Cosinus das Vorzeichen besrimmt und dan erst von der übergeortneten Funktion damit gerechnet. Möglichst mit 256er Teilung wegen Tempo. Deshalb auch das mit der Tabelle statt Standard-Sinus.

11

Whandall:
finde ich die Ver(sch)wendung des obersten Bits schon relevant.

OK, eine unsigned 16-bit Tabelle sollte von 0 bis 65535 gehen, damit alle Bits genutzt werden. Also ungefähr so:

// 91 x 2 bytes ==> 182 bytes
unsigned int isinTable16[] = { 
 0, 1144, 2287, 3430, 4571, 5712, 6850, 7987, 9121, 10252, 11380, 
 12505, 13625, 14742, 15854, 16962, 18064, 19161, 20251, 21336, 22414, 
 23486, 24550, 25607, 26655, 27696, 28729, 29752, 30767, 31772, 32768, 

 33753, 34728, 35693, 36647, 37589, 38521, 39440, 40347, 41243, 42125, 
 42995, 43851, 44695, 45524, 46340, 47142, 47929, 48702, 49460, 50203, 
 50930, 51642, 52339, 53019, 53683, 54331, 54962, 55577, 56174, 56755, 

 57318, 57864, 58392, 58902, 59395, 59869, 60325, 60763, 61182, 61583, 
 61965, 62327, 62671, 62996, 63302, 63588, 63855, 64103, 64331, 64539, 
 64728, 64897, 65047, 65176, 65286, 65375, 65445, 65495, 65525, 65535, 
 };

Das belegt gerade mal 182 Bytes im RAM. Dafür braucht man eigentlich kein PROGMEM.
Und schneller wird es mit PROGMEM statt RAM beim Tabellen-Lookup auch nicht.

12

Haribo68:
Das sind sowieso erst mal Werte zum rechnen über 0.
Nach dem rauspicken wird je nach Eingangswert und ob Sinus oder Cosinus das Vorzeichen besrimmt und dan erst von der übergeortneten Funktion damit gerechnet. Möglichst mit 256er Teilung wegen Tempo. Deshalb auch das mit der Tabelle statt Standard-Sinus.

Brauchst Du den Sinus am Ende als Gleitkommazahl (float)? Oder als unsigned int?

Und der Eingangsparameter bei Deiner schnellen Sinusfunktion soll was sein?

  • ganze Gradzahl als 'long'?
  • oder eine Gradzahl als 'float')?
    -oder ein Winkel im Bogenmaß(radians) Gleitkommazahl für Aufrufkompatibilität mit sin()?
13

jurs:
Das belegt gerade mal 182 Bytes im RAM. Dafür braucht man eigentlich kein PROGMEM.

Na ja, das sind fast 9% des Gesamtspeichers von 2048 Bytes bei 'normalen' Arduinos,
wenn man den Platz über hat, spricht nichts dagegen ihn so zu verwenden.

jurs:
Und schneller wird es mit PROGMEM statt RAM beim Tabellen-Lookup auch nicht.

Nee, wird sogar langsamer, insgesamt aber immer noch sehr viel schneller als berechnet.

Man bekommt nichts umsonst (hier: weniger RAM Verbrauch führt zu höherer Ausführungszeit).

14

jurs:
Das belegt gerade mal 182 Bytes im RAM. Dafür braucht man eigentlich kein PROGMEM.
Und schneller wird es mit PROGMEM statt RAM beim Tabellen-Lookup auch nicht.

Die Tabelle muß erst einmal ins RAM kommen, entweder durch Kopieren aus dem Flash, oder durch Berechnung in setup(). Eine Tabelle im RAM kostet also auch noch Flash Speicher.

Die Zugriffe aufs RAM sind zwar schneller, aber mit unsigned int hat jemand nicht zu Ende gedacht. Die Sinus-Funktion geht ja von -1 bis +1, und die negativen Werte passen dann nicht mehr in 16 Bit. Vor der Verwendung der Tabellenwerte muß also noch in long oder float konvertiert werden, was auch wieder Zeit kostet. Wenn mit float weitergerechnet werden soll, dann würde ich die Tabelle gleich als float ins PROGMEM legen, und wenn dort noch genügend Platz frei ist, gleich für alle vier Quadranten, dann spart man beim Zugriff jegliche Konvertierung.

15

DrDiettrich:
Die Zugriffe aufs RAM sind zwar schneller, aber mit unsigned int hat jemand nicht zu Ende gedacht. Die Sinus-Funktion geht ja von -1 bis +1, und die negativen Werte passen dann nicht mehr in 16 Bit. Vor der Verwendung der Tabellenwerte muß also noch in long oder float konvertiert werden, was auch wieder Zeit kostet. Wenn mit float weitergerechnet werden soll, dann würde ich die Tabelle gleich als float ins PROGMEM legen, und wenn dort noch genügend Platz frei ist, gleich für alle vier Quadranten, dann spart man beim Zugriff jegliche Konvertierung.

OK, ich habe heute mal ein paar Tests mit verschiedenen Funktionen gemacht und die Ausführungsgeschwindigkeit gemessen. Gerade die Messung der Ausführungsgeschwindigkeit ist aber auf einem System mit optimierenden Compiler wie AVR GCC gar nicht so einfach. Aber das sind meine Erkenntnisse mit drei verschiedenen Funktionen und Sinusberechnung für ganzzahlige Gradzahlen:

a) die originale "sin()" Funktion: Ausführungsdauer 120µs (einschließlich Umrechnung der Gradzahl ins Bogenmaß)

b)eigene -Sinusfunktion mit Nachschlagetabelle bestehend aus 91 'unsigned int'' Werten in einem array im RAM und mit abschließender Umrechnung von unsigned int in 'float' für das Ergebnis: 16µs

c) nachschlagen in einer Nachschlagetabelle aus 361 'float' Werten im PROGMEM: 8µs

Also wenn man den Sinus nur für ganzzahlige Gradzahlen braucht, kann man die Ausführungsdauer von 120 auf 8 Mikrosekunden drücken. Wenn man allerdings als Winkelparameter eine float Variable verwenden möchte, zur Berechnung des Sinus für gebrochene Gradzahlen, müßte man hinterher noch interpolieren, was wieder extra Zeit kostet und einen Teil der Zeitersparnis wieder zunichte machen würde.

c)

16

Hi,

habe es hinbekommen, danke Whandall.
Es ist sau schnell.
Mit allem drum und dran sind bis zu 21000 Sinusfunktionen/s drin, also mit allem anderem was man noch sonst zur Pixelausgabe macht.
Da wäre noch mehr möglich wenn die WS2812 nicht so lahm wären.

Vielen Dank

MfG
Andi

17

Hi,

hier mal die ausgearbeitete Funktion für schnelles Sinus und Cosinus:

const PROGMEM uint16_t SinCosTab[91] =
{0,572,1144,1715,2286,2856,3425,3993,4560,5126,5690,
6252,6813,7371,7927,8481,9032,9580,10126,10668,11207,
11743,12275,12803,13328,13848,14365,14876,15384,15886,16384,
16877,17364,17847,18324,18795,19261,19720,20174,20622,21063,
21498,21926,22348,22763,23170,23571,23965,24351,24730,25102,
25466,25822,26170,26510,26842,27166,27482,27789,28088,28378,
28660,28932,29197,29452,29698,29935,30163,30382,30592,30792,
30983,31164,31336,31499,31651,31795,31928,32052,32166,32270,
32365,32449,32524,32588,32643,32688,32723,32748,32763,32768};

int SinCos(int Winkel, int x, byte Cos){
  int winkel=Winkel;
  while(Winkel>360)Winkel-=360;
  if(Cos)goto GetCos;
GetSin:
  Winkel-=90;               //  subiw Winkel,90
  if(Winkel<0)goto GetSC1;  //  brcs  GetSC1
GetCos:
  Winkel-=90;               //  subiw Winkel,90
  if(Winkel<0)goto GetSC2;  //  brcs  GetSC2
  goto GetSin;              //  rjmp  GetSin
GetSC1:
  Winkel+=90;               //  addi  WinkelL,90
  goto GetSC3;              //  rjmp  GetSC3
GetSC2:
  Winkel=-Winkel;           //  neg WinkelL
GetSC3:
  x=(long)x*pgm_read_word(SinCosTab+Winkel)>>15;
  if(Cos){if(winkel<90 or winkel>270)return x;}
  else {if(winkel<180)return x;}
  return -x;
}

Ich habe das aus dem damaligen ASM-Code ziemlich direkt übernommen - die meisten ASM-Befehle stehen an den Zeilenenden - weil es sehr einfach und effektiv ist darauf zu kommen welcher Quarter behandelt werden muss, also von unten nach oben oder umgekehrt ausgelesen werden muss.
Bin aber für Optimierungen des C-Codes sehr aufgeschlossen.
3 Parameter werden übergeben: Der Winkel von 0 - 360°, der zu drehende Wert x und Cos (true oder nicht 0) für Cosinus statt Sinus.
Die Funktion kann nur ganzzahlige Gradschritte und ist gedacht für grafische Animationen die auch schnell gehen sollten in z. B. einem ATMega32u4 ohne Co-Prozessor wo es auf hundertstel Grad auch nicht ankommt.

MfG
Andi

18

Ich würde den Sin/Cos Ausgleich gleich am Anfang durchführen, und für Cos 90° addieren. Dann erst den Winkel auf <= 360° begrenzen.

Die Berechnung des Rückgabewerts sollte nochmal überprüft werden. Der Winkel wurde ja schon vorher umgerechnet, die Abfrage if(Cos) erscheint mir hier völlig falsch.

Zu prüfen wäre auch noch, ob der letzte Tabelleneintrag (8000 hex) richtig funktioniert, und nicht versehentlich als negativ interpretiert wird.

19

DrDiettrich:
Ich würde den Sin/Cos Ausgleich gleich am Anfang durchführen, und für Cos 90° addieren. Dann erst den Winkel auf <= 360° begrenzen.

Da hast du den Code noch nicht richtig verstanden. Da der Code zwischen den Marken GetCos und GetSC1 sowohl für ein Sinus- als auch Cosinusquarter hergenommen wird war das in ASM und wie ich finde auch in C die elegannteste und einfachste Methode für Cosinus genau gleich zu GetCOS zu springen, eben um 90° verschoben.

DrDiettrich:
Die Berechnung des Rückgabewerts sollte nochmal überprüft werden. Der Winkel wurde ja schon vorher umgerechnet, die Abfrage if(Cos) erscheint mir hier völlig falsch.

Am Ende, nach dem Auslesen des Multiplikators und der Multiplikation dessen mit X etc., geht es nur darum, ob der errechnete Wert negiert wird wenn für Cosinus Winkel > 90 und < 270° ist und bei Sinus der Winkel > 180° ist. Und winkel ist nicht gleich Winkel. Man kann Winkel auf 64 Arten in C schreiben, jedes ist für uns gleich :slight_smile:

DrDiettrich:
Zu prüfen wäre auch noch, ob der letzte Tabelleneintrag (8000 hex) richtig funktioniert, und nicht versehentlich als negativ interpretiert wird.

Das passt schon. Da der Wert im Flash ein unsigned ist wird dort auch nicht mit signed multipliziert. Habe das schon überprüft.

20

Hallo,

ausgehend eines Posts unten auf Seite 1 habe ich mir auch Gedanken gemacht über die Performance und nach dem basteln einer Testroutine im Setup-Abschnitt noch etwas Performance rausbekommen.
Somit ist die Anzahl an Sinus-/Cosinusfunktionen je Sekunde von durchschnittlich 65000 auf 130000 gestiegen.

Hier die neue "Fast-Sinus-Cosinus-Funktion" :slight_smile:

const PROGMEM uint16_t SinCosTab[91] =
{0,572,1144,1715,2286,2856,3425,3993,4560,5126,5690,
6252,6813,7371,7927,8481,9032,9580,10126,10668,11207,
11743,12275,12803,13328,13848,14365,14876,15384,15886,16384,
16877,17364,17847,18324,18795,19261,19720,20174,20622,21063,
21498,21926,22348,22763,23170,23571,23965,24351,24730,25102,
25466,25822,26170,26510,26842,27166,27482,27789,28088,28378,
28660,28932,29197,29452,29698,29935,30163,30382,30592,30792,
30983,31164,31336,31499,31651,31795,31928,32052,32166,32270,
32365,32449,32524,32588,32643,32688,32723,32748,32763,32768};

int SinCos(int Winkel, int x, byte Cos){
  int winkel=Winkel;
  while(Winkel>360)Winkel-=360;
  if(Cos)goto GetCos;
GetSin:
  Winkel-=90;               //  subiw Winkel,90
  if(Winkel<0)goto GetSC1;  //  brcs  GetSC1
GetCos:
  Winkel-=90;               //  subiw Winkel,90
  if(Winkel<0)goto GetSC2;  //  brcs  GetSC2
  goto GetSin;              //  rjmp  GetSin
GetSC1:
  Winkel+=90;               //  addi  WinkelL,90
  goto GetSC3;              //  rjmp  GetSC3
GetSC2:
  Winkel=-Winkel;           //  neg WinkelL
GetSC3:
  x=(long)x*(pgm_read_word(SinCosTab+Winkel))<<1>>16;
  if(Cos){if(winkel<90 or winkel>270)return x;}
  else {if(winkel<180)return x;}
  return -x;
}

Bei der Berechnung x*(pgm_read... erzwinge ich den Compiler dazu das er nicht 15 mal (/32768) 4 Register über Carry-Flag nach rechts schiebt sondern das durch <<1 (*2) nur ein mal nach links geschoben wird und mittels >>16 (/65536) ein Register-Swap, sowas wie mov r0,r2 und mov r1,r3 durchgeführt wird.
Ich vermute, das durch ein >>15, wie vorher, der Compiler eine 15ner Schleife gebaut hat in der 4 Register (Long-Byte) Bit für Bit geschoben wurden.
Jedenfalls ist es nun wirklich schnell.
Eine Routine in der mein 32u4 vorher 23ms für 255 Objekte benötigt hat sind es nun 19ms was der Framerate zu gute kommt.

Hier noch das Testtool zum ermitteln der Performance:

#define uintB uint8_t
#define uintW uint16_t
#define uintL uint32_t

  TCCR1A = 0;
  TCCR1B = (1<<CS11|1<<CS10);   // 64 als Prescale-Wert

  uintW Winkel=0;
  uintW rx=375;
  uintB Cos=0;
  uintW Tset;

loop:
  uintL SinCnt=0;
  for(byte n=0;n<4;n++){
    cli();
    Tset=TCNT1+2;
    while(Tset>TCNT1);

    TCNT1 = 0;
    while(TCNT1<62500){    //entspricht 250ms
      uintW x=SinCos(Winkel++,rx,Cos);
      while(Winkel>359)Winkel-=360;
      SinCnt++;
    }
  }
  sei();

  Serial.begin(2500000);
  while(!Serial);
  if(Cos)Serial.print("Cosinus");
    else Serial.print("Sinus");
  Serial.print("berechnungen/s: ");
  Serial.println(SinCnt);
  Serial.end();

goto loop;

In die Variable rx ist der zu "drehende" Wert, Winkel ist klar (0-360), mit Tset wird der Timer1 kalibriert.
Mit Cos bestimmt man ob Sinus (0) oder Cosinus (1).
Der Timer1 bekommt einen Prescaler von 64. 250 T1-Takte entsprechen genau 1ms, 250ms (1/4s) sind dann 62500 T1-Takte und das 4 mal eine Sekunde. SinCnt zählt die Operationen durch.
Vorsicht mit dem sei();. Nicht nach unten verschieben sonst wird es sehr schwer einen 32u4 wieder zu flaschen ^^

MfG
Andi