Arrays kompakter im Flash speichern

[Stefan F. (Gast)]

Hallo Leute,
vielleicht hat jemand spontan eine Idee, wie ich mit die Füll-Byte bei 
folgendem 5x8 Pixel-Font sparen kann.

static const uint8_t font [] PROGMEM = {
    2, 0x00, 0x00, 0x00, 0x00, 0x00, // space
    2, 0x5f, 0x00, 0x00, 0x00, 0x00, // !
    3, 0x07, 0x00, 0x07, 0x00, 0x00, // "
    5, 0x14, 0x7f, 0x14, 0x7f, 0x14, // #
    5, 0x24, 0x2a, 0x7f, 0x2a, 0x12, // $
    5, 0x62, 0x64, 0x08, 0x13, 0x23, // %
    5, 0x36, 0x49, 0x55, 0x22, 0x50, // &
    ... }

Das erste Byte jeder Zeile gibt an, wie breit das Zeichen ist. Danach 
folgen entsprechend viele sichtbare Bytes, und dann ggf. Füllbytes. Um 
ein char c darzustellen, gehe ich so vor:

size_t index = ((c - 32)*6) & 0xFFFF;
uint_fast8_t n = pgm_read_byte(&font[index]);

Danach gebe ich n Bytes ab font[index+1] aus.

Nun würde ich mir gerne die Füllbytes sparen, wenn das mit vertretbarem 
Aufwand machbar ist. Allerdings habe ich keinen Plan, wie ich dann den 
Index zügig ermitteln kann.

Irgendwelche Ideen?

[Falk B. (falk)]

Stefan F. schrieb:
> Hallo Leute,
> vielleicht hat jemand spontan eine Idee, wie ich mit die Füll-Byte bei
> folgendem 5x8 Pixel-Font sparen kann.

Und wozu? Wieviele GB willst du damit sparen?

> Nun würde ich mir gerne die Füllbytes sparen, wenn das mit vertretbarem
> Aufwand machbar ist. Allerdings habe ich keinen Plan, wie ich dann den
> Index zügig ermitteln kann.

Dann musst du die Infos in ein getrenntes Array legen. Und die 
Startpunkte der Zeichen mit variabler Länge in ein getrenntes Array, 
quasi ein Index.

[Stefan F. (Gast)]

Falk B. schrieb:
> Dann musst du die Infos in ein getrenntes Array legen.

Dachte ich mir schon. Dann brauche ich aber ca. 100 Pointer. Die belegen 
allerdings mehr Platz, als die paar Füllbytes, die ich dabei einspare.

Also lasse ich besser, wie es ist?

[C-hater (c-hater)]

Stefan F. schrieb:
> Nun würde ich mir gerne die Füllbytes sparen, wenn das mit vertretbarem
> Aufwand machbar ist.

Ist es nicht. Du bräuchtest eine zusätzliche Indextabelle. Die kostet 
mit einiger Wahrscheinlichkeit mehr Speicher, als du durch das Wegfallen 
des Padding einsparst, gerade bei so winzigen Fonts, wo die meisten 
Zeichen eh' die ganze Breite ausnutzen (müssen).

Aaaber: Bei dem Umfang der Texte, die man üblicherweise auf µC 
verwendet, kann man den Index auch einsparen. Alle nötige Information 
steckt ja bereits in den Längenbytes. Statt also einfach per Index 
zuzugreifen, muss man dann für jedes Zeichen über die Tabelle iterieren. 
Das kostet natürlich Rechenzeit.

Insgesamt also der übliche tradeoff: Speicherbedarf vs. Geschwindigkeit.

[Falk B. (falk)]

Stefan F. schrieb:
> Dachte ich mir schon. Dann brauche ich aber ca. 100 Pointer. Die belegen
> allerdings mehr Platz, als die paar Füllbytes, die ich dabei einspare.
>
> Also lasse ich besser, wie es ist?

Was machst du mit 100 gesparten BYTEs im Flash? Dafür gibt es keine Geld 
zurück.

[Stefan F. (Gast)]

Falk B. schrieb:
> Was machst du mit 100 gesparten BYTEs im Flash?
> Dafür gibt es keine Geld zurück.

War nur so eine fixe Idee, weil es AVR mit nur 1 kB Flash gibt. 
Allerdings würde man daran wohl eh kein solches Grafikdisplay 
anschließen, solange man noch alle Tassen im Schrank hat.

[Gerhard O. (gerhard_)]

Hallo Stefan,

Wenn fast alle Zeichen eine Breite von 5 Pixel haben, würde ich fast 
dazu neigen, einfach die Ausnahmen mit entsprechendem Test isolieren und 
die Zeichenbreiten Bytes wegzulassen, rät mir mein "einfach denkendes 
Gehirn". Wie viele nicht "5er" Zeichen gibt es? Wahrscheinlich nur ein 
paar wie "Ii.," u.ä. Ein einfacher Test jann dann die Breiten Daten 
liefern.

so eben fiel mir aber noch eine Möglichkeit ein. Wie wäre es die Ascii 
Längen Information der Zeichen in 32bit long ints zu speichern und dann 
als Ascii Nummer auswerten. Allerdings brauchst Du dann sprintf oder ä.

Z.B. in Deiner Tabelle fängt es mit 22355... an. Wenn Du jetzt diese 
Sequenz als long int speicherst, z.B. ascii 
"23555555355"(0x8C66ECCF)dann komprimierst Du die Nummer der notwendigen 
Bytes. Mit einem pointer kann man dann bequem auf jede Ascii Nummer 
zugreifen und durch Subtraktion in einen uint8_t verwandeln. Wäre nicht 
zu aufwendig. Mit dieser Methode lässt sich also viel Platz sparen. In 
dem obigen Beispiel können 11 Zeichen mit 4Bytes Speicher auskommen. 
Wenn Du dann die Zeichen Codierung in einem Array speicherst, dann 
kannst Du mit einem Pointer sofort auf die Bewertung zugreifen, was 
schnell geht.
Mit 6 Long ints könntest Du 64 Zeichen unterstützen.

Gruß,
Gerhard

[Falk B. (falk)]

https://www.mikrocontroller.net/articles/AVR-GCC-Codeoptimierung#Prinzipien_der_Optimierung

Gilt fast immer.

[Stefan F. (Gast)]

Gerhard O. schrieb:
> Wenn fast alle Zeichen eine Breite von 5 Pixel haben

Das ist der Fall, nur wenige Zeichen sind schmaler.

[Gerhard O. (gerhard_)]

Stefan F. schrieb:
> Gerhard O. schrieb:
>> Wenn fast alle Zeichen eine Breite von 5 Pixel haben
>
> Das ist der Fall, nur wenige Zeichen sind schmaler.

Dann könnte ein einfacher Test der betreffenden Zeichen ausreichen.

[C-hater (c-hater)]

Gerhard O. schrieb:

> Stefan F. schrieb:
>> Gerhard O. schrieb:
>>> Wenn fast alle Zeichen eine Breite von 5 Pixel haben
>>
>> Das ist der Fall, nur wenige Zeichen sind schmaler.
>
> Dann könnte ein einfacher Test der betreffenden Zeichen ausreichen.

Nein. Dieser Ansatz löst natürlich garnix. Es stimmen dann auch alle 
Indizes für die "höheren" Zeichen nicht mehr. Eine Abwandlung davon 
würde allerdings funktionieren: eine zusätzliche Tabelle mit den 
Ausnahmen. Auch über die müsste für jedes auszugebende Zeichen iteriert 
werden, aber sie wäre immerhin sehr viel kürzer als die "Haupttabelle", 
die Iteration wäre also rechenzeitmäßig deutlich billiger.

[Stefan F. (Gast)]

Ich habe nachgezählt, es geht um 59 Füllbytes und 102 Längenbytes.

[Gerhard O. (gerhard_)]

Hmmm...

Man könnte aber jeweils das unterste bit in jeder Spalte als 
Längenkodierung mißbrauchen, wenn man sich auf 5x7 Matrix beschränkt und 
das letzte Bit einfach ANDen.

[Stefan F. (Gast)]

Gerhard O. schrieb:
> Man könnte aber jeweils das unterste bit in jeder Spalte als
> Längenkodierung mißbrauchen, wenn man sich auf 5x7 Matrix beschränkt und
> das letzte Bit einfach ANDen.

Ich dachte gerade an etwas ähnliches. Ich könnte anstelle der 
Längenbytes einen reservierten Wert (der sonst nicht vorkommt) als 
Ende-Markierung nutzen.

[Gerhard O. (gerhard_)]

Stefan F. schrieb:
> Gerhard O. schrieb:
>> Man könnte aber jeweils das unterste bit in jeder Spalte als
>> Längenkodierung mißbrauchen, wenn man sich auf 5x7 Matrix beschränkt und
>> das letzte Bit einfach ANDen.
>
> Ich dachte gerade an etwas ähnliches. Ich könnte anstelle der
> Längenbytes einen reservierten Wert (der sonst nicht vorkommt) als
> Ende-Markierung nutzen.

Es sieht so aus, daß diese Richtung sich praktisch bewähren könnte.

Muß jetzt weg frühstücken gehen:-)

[MaWin O. (mawin_original)]

Stefan F. schrieb:
> es geht um 59 Füllbytes

Und die brauchst du ganz dringend für etwas?
Oder wären die gewonnenen Bytes dann einfach unbenutzt?

[Falk B. (falk)]

MaWin O. schrieb:
> Und die brauchst du ganz dringend für etwas?

Man könnte ja seinen Kontostand dort speichern. Oder Hochzeitstag. Oder 
Tage bis zur Rente . . .

> Oder wären die gewonnenen Bytes dann einfach unbenutzt?

First World Problems

[MaWin O. (mawin_original)]

Falk B. schrieb:
> Man könnte ja seinen Kontostand dort speichern

59 Bytes reichen leider nur für arme Schlucker.

> First World Problems

Vielleicht könnte man bei Microchip Geld zurück verlangen. Oder eine 
Ehrenurkunde für den besten Speichersparer bekommen. Die bekommt man 
aber nur, wenn der notwendige zusätzliche Code den Speichergewinn nicht 
wieder auffrisst.

[C-hater (c-hater)]

Hallodri schrieb:
> eine zusätzliche Tabelle mit den
> Ausnahmen. Auch über die müsste für jedes auszugebende Zeichen iteriert
> werden, aber sie wäre immerhin sehr viel kürzer als die "Haupttabelle",
> die Iteration wäre also rechenzeitmäßig deutlich billiger.

Dieser Ansatz ist auch insofern geil, weil in der "Haupttabelle" das 
Längenbyte entfallen könnte. Da könnte man also tatsächlich deutlich 
Speicher sparen und auch der Mehraufwand an Rechenzeit wäre relativ 
gering.

[C-hater (c-hater)]

Stefan F. schrieb:

> Ich habe nachgezählt, es geht um 59 Füllbytes und 102 Längenbytes.

Du hast den eigentlichen Knackpunkt nicht erkannt, nämlich:

Wie viele von deinen 102 unterstützten Zeichen haben die volle Breite 
und wie viele wären dementsprechend Ausnahmen. DAS sind die 
entscheidenden Kenngrößen. Damit kann man nämlich unmittelbar den 
Speicherbedarf und den (mittleren) Rechenzeitbedarf einer jeden 
denkbaren (einfachen *) Lösung ermitteln.

(*) Sachen wie Komprimierung sind bei dieser Sache natürlich aussen vor. 
Der Codeaufwand würde den Speicherplatzbedarf für die 
Konstanten-Tabellen sicher mehr als auffressen.

[Gerhard O. (gerhard_)]

Wenn die unterste Pixelreihe (MSb) ohnehin unbenutzt ist, dann lohnt es 
sich vielleicht doch noch, diese Ressource für die Zeichen 
Breitenerkennung auszunutzen. Der Code Overhead würde sich in Grenzen 
halten und ist einfachst machbar. Je weniger kompliziert, desto besser.

[C-hater (c-hater)]

Gerhard O. schrieb:
> Wenn die unterste Pixelreihe (MSb) ohnehin unbenutzt ist, dann lohnt es
> sich vielleicht doch noch, diese Ressource für die Zeichen
> Breitenerkennung auszunutzen. Der Code Overhead würde sich in Grenzen
> halten und ist einfachst machbar. Je weniger kompliziert, desto besser.

Nein. Es ist selten bis nie sinnvoll, Metadaten in potentiellen Inhalten 
unterzubringen. Spätestens der erste Zeichensatz mit Unterlängen zeigt 
das dann...

[MaWin O. (mawin_original)]

Gustl B. schrieb im Beitrag #7358896:
> Es funktioniert nicht

Natürlich kann das je nach Situation funktionieren.
Das kommt ganz auf die Umstände und Randbedingungen an.

[MaWin O. (mawin_original)]

Hallodri schrieb:
> Es ist selten bis nie sinnvoll, Metadaten in potentiellen Inhalten
> unterzubringen

außer, wenn man den freien Platz in den Inhalten nutzen will. Und darum 
geht es hier.

[Stefan F. (Gast)]

Ich habe mir einen (sonst ungenutzten) Wert als Füllbyte festgelegt. Die 
Längenangaben entfallen dadurch, was immerhin 100 Bytes ausmacht. Für 
jedes Zeichen werden nun immer 5 Bytes ausgegeben, oder weniger wenn er 
dabei auf ein Füllbyte stößt.

// 5x8 font with variable width 
// 0x88 are invisible filler bytes
static const uint8_t oled_font [] PROGMEM = {
    0x00, 0x00, 0x88, 0x88, 0x88, // space
    0x5F, 0x88, 0x88, 0x88, 0x88, // !
    0x07, 0x00, 0x07, 0x88, 0x88, // "
    0x14, 0x7F, 0x14, 0x7F, 0x14, // #
    0x24, 0x2A, 0x7F, 0x2A, 0x12, // $
    0x62, 0x64, 0x08, 0x13, 0x23, // %
    0x36, 0x49, 0x55, 0x22, 0x50, // &
    ...

So wird jetzt ein Zeichen c ausgegeben:

    size_t font_index = ((c - 32)*5) & 0xFFFF;
    for (uint_fast8_t i=0; i<5; i++)
    {
        uint8_t b = pgm_read_byte(&oled_font[font_index++]);

        // Skip filler bytes
        if (b == 0x88)
        {
            break;
        }
     
        draw_byte(x, y, b);
        x++;
    }

War doch ganz einfach :-)

[Falk B. (falk)]

Ohhhhh, die 88 ist gaaanz bööööööse!!!! ;-)

https://www.politische-bildung-brandenburg.de/themen/die-extreme-rechte/lifestyle/kfz-kennzeichen

[Stefan F. (Gast)]

Jetzt habe ich zwar immer noch die Füllbytes im Zeichensatz, aber dafür 
brauche ich keine Längen-Bytes mehr, was viel Platz spart.

Danke für eure Anregungen.