Archiv verlassen und diese Seite im Standarddesign anzeigen : Array-Alternative
Moin,
ich habe im Moment ein Array welches so aussieht: uint16_t BitMap[5][200][9]
Das ganze verbraucht nun 2*5*200*9 Bytes, was ja auf Microcontrollern schon gut spürbar ist. Der springende Punkt ist, dass das Array [200] nur selten voll aufgefüllt wird, häufig gerade mal 1-2 Einträge beinhaltet.
Gibt es eine Alternative, mit der ich nicht so schnell ans Speicherlimit stoße?
Viele Grüße
Das sieht etwas so aus, als ob du das falsche Mittel zum Zweck verwenden wolltest. Was soll es denn eigentlich sein, können und wie ist das Anforderungs/Nutzungsprofil? Evtl. wäre eine dynamische Datenstruktur für dich Interessant, da musst du dich halt selbst mit dem Speichermanagement herumschlagen.
mfG
Markus
Moin,
es geht um Speicherung von Frames einer 9x14 LED-Matrix. Es soll mehrere verschiedene Animationen, mit jeweils 1-200 Frames geben. In den letzten [9] stehen die jeweiligen Informationen zur Ansteuerung der LEDs drin.
Naja, "selten" heisst, es kommt ja doch vor. Und dann brauchst du den Platz. d.h. du kannst ihn nicht anderweitig verbraten.
Naja, "selten" heisst, es kommt ja doch vor. Und dann brauchst du den Platz. d.h. du kannst ihn nicht anderweitig verbraten.
Ja es kommt vor. Aber es wird auch bei 1-2 Frames der Platz für 200 Stück verbraucht, das ist das Problem.
Naja, du hast bei Mikrocontrolleranwendungen meist einen recht statischen Speicherverbrauch. Entweder alles was du brauchst passt rein, oder du musst dir was anderes überlegen. Es bringt dir nichts, irgend eine tolle Datenstruktur zu entwerfen und im Worst-Case brauchst du dennoch allen Platz (eher noch viel mehr) und Zeug das vorher funktionierte macht auf einmal Probleme, weil der Speicher nicht mehr länger nur knapp voll, sondern überbelegt ist.
mfG
Markus
.:Sebastian:.
02.01.2012, 14:05
Moin
Beschreibe doch mal genauer was du ablegen willst.
Ich vermute einfach mal :
5 Animationen mit 200 Frames wobei jedes Frame 9 * 16bit (oder Pixel) hat.
Jetzt ist die Frage ist das Array hardcoded (also schon zu Compilezeit fest) oder überträgst du es zu Laufzeit z.B. via UART zum uC ?
Ich vermute mal letzteres weil wenn das Array konstant wäre, konnte man es ja einfach kleiner machen in dem man die unnötigen Frames weglässt.
Wenn das ganze Laufzeit auf den uC übertragen wird, kannst du das ganze z.B. als verkettete Liste realisieren, musst dich aber selber um das beschaffen und freigeben von Speicher kümmern (siehe dazu malloc http://www.nongnu.org/avr-libc/user-manual/malloc.html und free http://tinyurl.com/7gdvqfc ).
Allerdings bekommst du damit auch nicht MEHR Speicher.
Es ist dann wie PicNick angedeutet hat. Da hast zwar freien Speicher, den musst du aber auch frei halten/kannst ihn nicht einfach benutzen, weil ja auch der "seltene" worstcase Fall eintreten kann,
das du tatsächlich alles brauchst.
Wenn du tatsächlich immer weniger Speicher benutzen möchtest, musst du deine Frames effizienter ablegen.
Also die 9*16 bit in weniger als 9*16bit speichern.
Das klappt aber nur wenn sich Frames wiederholen.
Als Ansatz würde ich da zu einer Shannon-Fano-Kodierung http://de.wikipedia.org/wiki/Shannon-Fano-Kodierung raten.
Die Idee dabei ist das einige Symbole (für dich Frames) häufiger auftreten als andere.
Deshalb bekommen die häufigstem Symbole die kürzesten Codes.
z.B. ein Frame was einen Smilie enthält bekommt als Code 01.
Die Codes sind dabei automatisch so gebaut, das in keinem anderen Code die Kombination 01 vorkommt.
Also kann man die Codewörtern einfach hintereinander in den Speicher knallen 0111001... man brauch keine Trenner zwischen den Codewörtern.
Irgendwo hast du dann eine Tabelle im Speicher die dir 01 zu einem bestimmten Frame zuordnet.
Hier liegt halt leider auch der Haken bei 200 unterschiedlichen Frames nützt die das grade mal rein garnichts, weil deine Dekodierungstabelle genauso groß ist,
weil die Animation (200 Frames).
Da kann man aber immernoch überlegen ob es sich lohnt einzelne Teile (z.b. 16bit Scheiben) eines Frames so abzulegen.
Weil wenn die Frames dann auch nur teilweise gleich sind kann man auch wieder Speicher sparen.
Übrigens Shannon-Fano-Kodierung hat (wenn sie richtig benutzt wird) eine optimale Entropy (gibts einen schönen Beweis dazu) also benutzt es optimal wenig Bits für jedes Codewort.
Falls du in die Richtung etwas implementieren willst, kann ich dir auch gerne den Trick verraten, wie man solche Kodierungen einfach mit einer Tabelle erzeugen kann (der steht nämlich nicht auf Wikipedia).
Gruß
Sebastian
Moin
Beschreibe doch mal genauer was du ablegen willst.
Ich vermute einfach mal :
5 Animationen mit 200 Frames wobei jedes Frame 9 * 16bit (oder Pixel) hat.
5 Animationen, von welchen die längste 200 Frames hat. Jeder Frame 9*16bit, genau.
Jetzt ist die Frage ist das Array hardcoded (also schon zu Compilezeit fest) oder überträgst du es zu Laufzeit z.B. via UART zum uC ?
Ich vermute mal letzteres weil wenn das Array konstant wäre, konnte man es ja einfach kleiner machen in dem man die unnötigen Frames weglässt.
Das ganze ist schon zur Compilezeit fest und wird in den PROGMEM geschrieben. (read-only)
Geistesblitz
02.01.2012, 14:23
Kannst du nicht für jede Animation ein eigenes Array mit der entsprechenden Framezahl erstellen?
Nein, weil die Anzahl der Animationen dynamisch ist.
.. ist schon zur Compilezeit fest und wird in den PROGMEM geschrieben
???
Warum dann nochmal in den SRAM ?
???
Warum dann nochmal in den SRAM ?
Es kommt nicht nochmal in den SRAM, sondern NUR in den PROGMEM.
Dann verstehe ich dein Problem nicht. Du kannst doch einfach mehrere Arrays mit genau der benötigten Länge im Flash ablegen und über Präprozessormakros, Konstanten oder sizeof (sollte auch gehen) auf die Länge des jeweiligen Arrays zugreifen. Wenn du ganz strukturiert rangehen willst, machst du dir eine Datenstruktur aus einem uint8 (Länge der Animation) + einem Pointer auf ein PROGMEM-Array und erzeugst ein Array aus solchen Strukturen, dann kannst du wieder über einen Index auf die jeweilige Animation zugreifen, erhältst die Länge + einen Zeiger auf die Animationsdaten und kannst all das Wissen dann zur Weiterverarbeitung der Daten nutzen.
mfG
Markus
Dann verstehe ich dein Problem nicht. Du kannst doch einfach mehrere Arrays mit genau der benötigten Länge im Flash ablegen und über Präprozessormakros, Konstanten oder sizeof (sollte auch gehen) auf die Länge des jeweiligen Arrays zugreifen. Wenn du ganz strukturiert rangehen willst, machst du dir eine Datenstruktur aus einem uint8 (Länge der Animation) + einem Pointer auf ein PROGMEM-Array und erzeugst ein Array aus solchen Strukturen, dann kannst du wieder über einen Index auf die jeweilige Animation zugreifen, erhältst die Länge + einen Zeiger auf die Animationsdaten und kannst all das Wissen dann zur Weiterverarbeitung der Daten nutzen.
mfG
Markus
Ich verstehe leider nicht wirklich was du meinst, bin relativ C-unerfahren. Meinst du sowas?
uint16_t t2[2][9] = {{0,864,2032,2032,992,448,128,0},{1,2,3,4,5,6,7,8, 8}};
uint16_t t1[] = {t2};
Hi,
wie wäre es, wenn Du das ganze Stück für Stück aufbaust?
Erst brauchst Du eine Struktur in der steht wieviele Frames die Animation hat und einen Zeiger auf die Frames:
typedef struct
{
uint16_t NumberOfFrames; // Anzahl der Frames
uint16_t * PointerToFrame; // Pointer zum FrameArray
} Frame;
Wenn Du die Frames einzeln ablegst:
uint16_t Frame1[20]={1,2,3,4,5,...};
uint16_t Frame2[100]={1,2,3,4,5,...};
...
und jetzt so was anlegest:
Frame MeineFrames[5] = {{20,Frame1},{100,Frame2},...};
solltest Du über MeineFrames auf alles zugreifen, was Du brauchst.
Ich hoffe, dass ich nicht all zu wirr klinge...
Drew
Ps: Ich glaube das ist das was markusj meint, oder?
Frames einzeln ablegen würde ich ungern machen, da das dann sehr schnell unübersichtlich wird.
Ginge es auch so, dass ich Animationen einzeln ablege?
Edit:
Ich habe jetzt folgendes:
typedef struct
{
uint16_t * PointerToFrame; // Pointer zum FrameArray
} Frame;
uint16_t Frame1[5]={1,2,3,4,5};
uint16_t Frame2[5]={1,2,3,4,5};
Frame Animation1[2] = {Frame1,Frame2};
Frame Animation2[2] = {Frame1,Frame2};
typedef struct
{
Frame * PointerToFrame; // Pointer zum FrameArray
} AnimationStack;
AnimationStack Animations[2] = { Animation1, Animation2};
Funktioniert zwar, ist aber seehr suboptimal weil ich jeden Frame einzeln anlegen muss und nicht einfach {{1,2,3},{1,2,3}} nutzen kann. Gibt es irgendeine Möglichkeit das ich die Frames gleich als {{},{}} in eine Animation kriege?
Schade, dass Du Deinen letzten Weg (ver-)editiert hast. Darauf aufbauend wäre das meine Vorschlag:
typedef uint16_t Frame[9];
typedef struct
{
uint16_t NumberOfFrames; // Anzahl der Frames
Frame * PointerToAnimation; // Pointer zum FrameArray
} Animationen;
uint16_t Animation1[][9]={{0,2,3,4,5,6,7,8,9}, {1,2,3,4,5,6,7,8,9}};
uint16_t Animation2[][9]={{3,2,3,4,5,6,7,8,9}};
Animationen Animations[2] = {{2, &Animation1}, {1, &Animation2}};
Schade, dass Du Deinen letzten Weg (ver-)editiert hast. Darauf aufbauend wäre das meine Vorschlag:
Ahh, verdammt ;-)
Ich bekomme bei deinem Vorschlag leider folgende Fehler:
cmd:30: error: cannot convert 'uint16_t (*)[2][9]' to 'uint16_t (*)[9]' in initialization
cmd:30: error: cannot convert 'uint16_t (*)[1][9]' to 'uint16_t (*)[9]' in initialization
Sieht ansonsten aber genau nach dem aus was ich versuche hinzukriegen!
Schade.
Vielleicht müssen wir mal Compilerversionen austauschen. Zunächst, bei mir liegt der Code in einer C-Datei (nicht C++-Datei).
1) Microsoft Visual C++ 2005.
2) WinAVR-20100110
a) bei mir funktioniert es mit beiden oben genannten Compilern.
b) auch folgende Variante funktioniert damit:
uint16_t Animation1[2][9]={{0,2,3,4,5,6,7,8,9}, {1,2,3,4,5,6,7,8,9}};
uint16_t Animation2[1][9]={{3,2,3,4,5,6,7,8,9}};
Animationen Animations[2] = {{2, Animation1}, {1, Animation2}};
Hmm, ich benutze das Standard Arduino-IDE (http://www.arduino.cc/en/Main/Software), welches laut http://www.arduino.cc/en/Hacking/BuildProcess mit dem avr-gcc compiled.
Ja drew, so war das gemeint. Folgender Code ist ungetestet, compiliert bei mir aber schon Mal:
#include <avr/io.h>
#include <avr/pgmspace.h>
#include <stdint.h>
typedef uint16_t Frame_t[9];
typedef struct {
uint8_t frameCount;
Frame_t * animation;
} AnimationData_t;
PROGMEM Frame_t Animation1[2] = { { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, { 11, 12, 13,
14, 15, 16, 17, 18, 19 } };
PROGMEM Frame_t Animation2[1] = { { 21, 22, 23, 24, 25, 26, 27, 28, 29 } };
AnimationData_t animations[2] = { { sizeof(Animation1), Animation1 }, {
sizeof(Animation2), Animation2 } };
int main(void) {
for (uint8_t i = 0; i < sizeof(animations); i++) {
for (uint8_t j = 0; j < animations[i].frameCount; j++) {
Frame_t * frames = animations[i].animation;
for (uint8_t k = 0; k < 9; k++) {
uint16_t frameWord;
frameWord = pgm_read_word(&frames[j][k]);
}
}
}
}
Später kann über animations zur Laufzeit fast wie auf ein Array zugegriffen werden, dieser Code legt die eigentlichen Bitmuster bereits im Flash ab.
mfG
Markus
Danke, deine Lösung macht genau was ich gesucht habe :-)
Freut mich wenn es funktioniert, ich wollte den Code noch via Simulation überprüfen, musste aber feststellen dass Eclipse + avr-gdb + simulavr wohl nicht so meins ist und ich demnächst irgendwie AVR Studio über ne Windows-VM oder Wine zum laufen kriegen muss.
Nein, nahe dran, aber so funktioniert das nicht denn mit sizeof() wird falsch umgegangen. Wird @zulakis wohl auch schon bemerkt haben. So will ich diesen Thread nicht enden lassen. (Schade auch, dass @markusj andere Typ- und Variablennamen eingesetzt hat. Das macht das gemeinsame arbeiten im Thread schwierig.) Ich habe mal alles zusammen gefasst und konnte Folgendes erfolgreich testen:
typedef uint16_t Frame_t[9];
typedef struct {
uint16_t NumberOfFrames; // Anzahl der Frames
Frame_t * PointerToAnimation; // Pointer zum FrameArray
} Animationen_t;
PROGMEM Frame_t animation1[] ={{0,2,3,4,5,6,7,8,9}, {1,2,3,4,5,6,7,8,9}};
PROGMEM Frame_t animation2[]={{3,2,3,4,5,6,7,8,9}};
PROGMEM Animationen_t animations[] = {{2, animation1}, {1, animation2}};
int main(void) {
int i, j, k;
for (i = 0; i < sizeof(animations)/sizeof(Animationen_t); i++) {
for (j = 0; j < pgm_read_word(&animations[i].NumberOfFrames); j++) {
Frame_t * frame = pgm_read_word(&animations[i].PointerToAnimation);
for (k = 0; k < 9; k++) {
uint16_t frameWord = pgm_read_word(&frame[j][k]);
//printf("%d, ", frameWord);
}
}
}
}
Sorry, mir fliegen hier im CODE immer die indent Spaces durcheinander. Was mach ich da falsch?
Ouch, dämlicher Fehler. Du hast natürlich Recht, sizeof gibt mir die Größe in Bytes was erst Mal wenig bringt ...
Ich hatte allerdings bewusst darauf verzichtet, die Indexstruktur im PROGMEM abzulegen, um unnötige Lesezugriffe auf den Flash (die das ganze verlangsamen und komplexer machen) zu vermeiden. Es wäre natürlich auch möglich, einfach immer nur den aktuell benötigten Index zu laden, dann hätte man alles im Flash liegen und dennoch einen effizienten Zugriff.
Ach ja: GCC beschwert sich über Arrays deren Größe nicht bei der Definition angegeben wird ...
mfG
Markus
PS: Auch wenn es ähnlich aussieht, ich hatte meinen Code einmal komplett neugeschrieben um alles (gut, bis auf sizeof *hust*) zu durchdenken, daher die Unterschiede.
PPS: Wie kriegst du deinen Code eigentlich farbig? Geht das manuell oder macht das Forum das automagisch?
Aaah, jetzt dämmert's mir. Danke @markusj. Die Farbigkeit des Codes habe ich immer als Feature der Forumsoftware angesehen. Ist aber nicht so! Sondern lag daran, dass ich den Code direkt aus Eclipse cut&paste! Dadurch kommt das syntaxcoloring von Eclipse mit ins Forum. Wenn ich das nicht tue (siehe Test unten) bleibt es schwarz/weiß. Und ... siehe da, mein indent Problem ist auch weg.
typedef uint16_t Frame_t[9];
typedef struct {
uint16_t NumberOfFrames; // Anzahl der Frames
Frame_t * PointerToAnimation; // Pointer zum FrameArray
} Animationen_t;
PROGMEM Frame_t animation1[] ={{0,2,3,4,5,6,7,8,9}, {1,2,3,4,5,6,7,8,9}};
PROGMEM Frame_t animation2[]={{3,2,3,4,5,6,7,8,9}};
PROGMEM Animationen_t animations[] = {{2, animation1}, {1, animation2}};
int main(void) {
int i, j, k;
for (i = 0; i < sizeof(animations)/sizeof(Animationen_t); i++) {
for (j = 0; j < pgm_read_word(&animations[i].NumberOfFrames); j++) {
Frame_t * frame = pgm_read_word(&animations[i].PointerToAnimation);
for (k = 0; k < 9; k++) {
uint16_t frameWord = pgm_read_word(&frame[j][k]);
//printf("%d, ", frameWord);
}
}
}
}
Powered by vBulletin® Version 4.2.5 Copyright ©2024 Adduco Digital e.K. und vBulletin Solutions, Inc. Alle Rechte vorbehalten.