Array-Alternative

[Zulakis]

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

[markusj]

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

[Zulakis]

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.

[PicNick]

Naja, "selten" heisst, es kommt ja doch vor. Und dann brauchst du den Platz. d.h. du kannst ihn nicht anderweitig verbraten.

[Zulakis]

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.

[markusj]

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

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

[drew]

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?

[Zulakis]

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?

[rossir]

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}};