HSV->RGB-Methode: Speicherplatz optimieren

[matze (Gast)]

Hallo,

ich benutze eine Funktion, welche HSV-Koordinaten in RGB-Koordinaten 
umrechnet. Leider ist diese Funktion 378 Byte groß, was auf einem 
ATtiny13 deutlich zu viel ist (damit der Rest des Programms auch noch 
Platz hat).

Daher würde ich diese Methode optimieren, finde aber keinen 
Optimierungsspielraum mehr:

void setColorHSV(char hue, char saturation, char value)
{
    unsigned char i, f;
    unsigned int  p, q, t;
    unsigned char red = 0, green = 0, blue = 0;

    if (saturation == 0)  // Farbsättigung ist Null -> Grau
    {
        red = green = blue = 0;
    }
    else                  // Farbsättigung ist nicht Null -> Einteilen in 60°-Winkel des Farbtons
    {
        i = hue / 43;
        f = hue % 43;
        p = (value * (255 - saturation)) / 256;
        q = (value * ((10710 - (saturation * f)) / 42)) / 256;
        t = (value * ((10710 - (saturation * (42 - f))) / 42)) / 256;

        switch (i)
        {
            case 0: red = value;   green = t;     blue = p;   break;
            case 1: red = q;     green = value;   blue = p;   break;
            case 2: red = p;     green = value;   blue = t;   break;
            case 3: red = p;     green = q;     blue = value; break;      
            case 4: red = t;     green = p;     blue = value; break;        
            case 5: red = value;  green = p;     blue = q;    break;
      }
      setColorRGB(red, green, blue);
   }
}

P.S.: Die Größe der Funktion habe ich ermittelt indem ich einmal mit 
obigem Code kompiliert habe und einmal nachdem ich den gesamten Inhalt 
des Funktionsrumpfes auskommentiert hatte.

[Gast (Gast)]

    if (saturation == 0)  // Farbsättigung ist Null -> Grau
        return;

Ich weiß nicht, obs was bring. Je nach Optimierung vielleicht. Du setzt 
die Variablen bereits auf Null.

[Gast (Gast)]

Müssen p, q, t alle int sein?
Du weist sie ja später eh einem unsigned char zu.

[matze (Gast)]

@Gast:

In der Tat müssen sie keine 16-Bit-Variablen sein. Daher habe ich

unsigned int  p, q, t;

ersetzt durch

unsigned char  p, q, t;

Der benötigte Flash-Speicherplatz reduziert sich jedoch nicht. Ich 
vermute, dass es daran liegt, dass während der Berechnung von p,q,t 
große Zahlen verwendet werden.

[Läubi .. (laeubi)]

Das teilen durch 256 erscheint mir hier merkwürdig ist das korrekt?
Und ich würde mir da mal das ASM listing ansehen da kannst du dann sehen 
wo er wirklich was verbraucht.

[Gast (Gast)]

Dann bleibt wohl oder überl nur noch Assembler übrig.

[Reinhard Kern (Gast)]

Hallo,

du verwendest ja alle 4 Grundrechenarten plus MOD und DIV, da ist das 
doch nicht viel, also wird sich auch kaum noch was wegoptimieren lassen.

Ich versuche bei µC oft, alle (!) Divisionen zu vermeiden, weil das die 
aufwendigste Operation ist. Also statt / 43 verwende ich * 0,023; das 
ist natürlich nur bei Konstanten sinnvoll. Es kann aber auch nach hinten 
losgehen, je nach Library und Linker, also ausprobieren.

Gruss Reinhard

[matze (Gast)]

Wie komme ich am schnellsten an den ASM-Code dieser Funktion?

Ich nutze das AVR-Studio.

[/* Kommentator */ (Gast)]

Strg-F7
Alt V a

oder via GUI: Build&Run, View:Disassembler

[Fabian B. (fabs)]

AVR Studio + GCC legt im Arbeitsordner einen Ordner "default" an und 
darin sollte eine .lss Datei sein. Falls nicht, kannst du dem Compiler 
im AVRStudio unter Project->Conf.Options sagen, er solle bitte eins 
erstellen.

Gruß
Fabian

[holger (Gast)]

>Der benötigte Flash-Speicherplatz reduziert sich jedoch nicht. Ich
>vermute, dass es daran liegt, dass während der Berechnung von p,q,t
>große Zahlen verwendet werden.

Bei den meisten der Multiplikationen drohen Überläufe.
8 Bit x 8Bit kann größer als 8 Bit werden. Da fehlen
dann noch geeignete casts. Dadurch wird der
Code aber noch größer.

[holger (Gast)]

So, ich hab mal ein bißchen rumgespielt:

Casting für die Multiplikationen eingesetzt und ein bißchen
ausgeklammert. Ist dabei von 514 auf 436 Bytes runter gegangen.
Komischerweise schrumpft der Code durch das Casting sogar;)

void setColorHSV(unsigned char hue, unsigned char saturation, unsigned char value)
{
    unsigned char i, f;
    unsigned char  p, q, t;
    unsigned char red = 0, green = 0, blue = 0;

    if (saturation == 0)  // Farbsättigung ist Null -> Grau
    {
        red = green = blue = 0;
    }
    else                  // Farbsättigung ist nicht Null -> Einteilen in 60°-Winkel des Farbtons
    {
        i = hue / 43;
        f = hue % 43;
        p = ((unsigned int)value * (255 - saturation)) / 256;
        q = (value * (10710 - ( (unsigned int)saturation * f) ) ) / 256 / 42;
        t = (value * (10710 - ((unsigned int)saturation * (42 - f)) ) ) / 256 / 42;

        switch (i)
        {
            case 0: red = value;   green = t;     blue = p;   break;
            case 1: red = q;     green = value;   blue = p;   break;
            case 2: red = p;     green = value;   blue = t;   break;
            case 3: red = p;     green = q;     blue = value; break;      
            case 4: red = t;     green = p;     blue = value; break;        
            case 5: red = value;  green = p;     blue = q;    break;
      }

      setColorRGB(red, green, blue);
   }
}

[holger (Gast)]

Ach shit:

        q = (value * (10710 - ( (unsigned int)saturation * f) ) ) / 256 
/ 42;

value * (10710 - ( (unsigned int)saturation * f)

Könnte wieder größer unsigned int werden.
Dann das ausklammern der 42 rückgängig machen.

[holger (Gast)]

Neuer Versuch;)

void setColorHSV(unsigned char hue, unsigned char saturation, unsigned char value)
{
    unsigned char i, f;
    unsigned char  p, q, t;
    unsigned char red = 0, green = 0, blue = 0;

    if (saturation == 0)  // Farbsättigung ist Null -> Grau
    {
        red = green = blue = 0;
    }
    else                  // Farbsättigung ist nicht Null -> Einteilen in 60°-Winkel des Farbtons
    {
        i = hue / 43;
        f = hue % 43;
        p = ((unsigned int)value * (unsigned char)(255 - saturation)) / 256;
        q = (value * ((10710 - ( (unsigned int)saturation * f) )  / 42) ) / 256;
        t = (value * ((10710 - ((unsigned int)saturation * (unsigned char)(42 - f)) )  / 42) ) / 256;

        switch (i)
        {
            case 0: red = value;   green = t;     blue = p;   break;
            case 1: red = q;     green = value;   blue = p;   break;
            case 2: red = p;     green = value;   blue = t;   break;
            case 3: red = p;     green = q;     blue = value; break;      
            case 4: red = t;     green = p;     blue = value; break;        
            case 5: red = value;  green = p;     blue = q;    break;
      }

      setColorRGB(red, green, blue);
   }
}

Ergibt nur noch 434 Bytes. Besser als 514 allemal.

[avr (Gast)]

Hallo Holger,

hier hast du eine Vorbelegung

    unsigned char red = 0, green = 0, blue = 0;

und hier wird im If diese bestädigt

    if (saturation == 0)  // Farbsättigung ist Null -> Grau
    {
        red = green = blue = 0;
    }
    else                  // Farbsättigung ist nicht Null -> Einteilen in 60°-Winkel des Farbtons

Besser:

    unsigned char red = 0, green = 0, blue = 0;

    if (saturation != 0)  // Farbsättigung ist nicht Null -> Einteilen in 60°-Winkel des Farbtons
    {

avr

[holger (Gast)]

>Hallo Holger,
>
>hier hast du eine Vorbelegung

Die ist nicht von mir;)

>    if (saturation != 0)  // Farbsättigung ist nicht Null -> Einteilen in 
>60°-Winkel des Farbtons

Ok, ausprobiert, bleibt bei 434 Bytes.

[holger (Gast)]

Schmeisst man das komplett raus

    if (saturation == 0)  // Farbsättigung ist Null -> Grau

Gibts noch mal 6 Bytes geschenkt.
Macht man aus dem switch() einen if(i==x) Spaghetti Code
nochmal 4 Bytes.

Ich glaub das wars dann aber auch. 424 Bytes.

[Läubi .. (laeubi)]

Ich würde es trozdem mal mit 255 anstelle von 256 versuchen... Das 
sollte dir auf jedenfall ein 16bit Division erstparen und das Ergebnis 
nicht merklich beeinflussen.
Ebenso die gemsichten 42/43 kommen mir komisch vor.
Kompilierst du auch mit Optimierung auf Platz?

[holger (Gast)]

>Ich würde es trozdem mal mit 255 anstelle von 256 versuchen... Das
>sollte dir auf jedenfall ein 16bit Division erstparen und das Ergebnis
>nicht merklich beeinflussen.

Bloß das nicht! Mit 256 zieht er sich nur das Highbyte des
Ergebnisses rein. Passt schon. Bei 255 müsste wirklich
dividiert werden.

>Kompilierst du auch mit Optimierung auf Platz?

Ja, Os.

[holger (Gast)]

>Bloß das nicht! Mit 256 zieht er sich nur das Highbyte des
>Ergebnisses rein. Passt schon. Bei 255 müsste wirklich
>dividiert werden.

So, kurz ausprobiert, 438 Bytes.

[matze (Gast)]

Also erst einmal vielen Dank! Das ist in jedem Fall eine verbesserung, 
wenn auch eine kleine. Tatsächlich hat sich in der If-Bedingung ein 
Programmierfehler eingeschlichen, den aber keiner bemerkt hat:

void setColorHSV(unsigned char hue, unsigned char saturation, unsigned char value)
{
    unsigned char i, f;
    unsigned char  p, q, t;
    unsigned char red = 0, green = 0, blue = 0;

    if (saturation == 0)  // Farbsättigung ist Null -> Grau
    {
        red = green = blue = value;
    }
    else                  // Farbsättigung ist nicht Null -> Einteilen in 60°-Winkel des Farbtons
    {
        i = hue / 43;
        f = hue % 43;
        p = ((unsigned int)value * (unsigned char)(255 - saturation)) / 256;
        q = (value * ((10710 - ( (unsigned int)saturation * f) )  / 42) ) / 256;
        t = (value * ((10710 - ((unsigned int)saturation * (unsigned char)(42 - f)) )  / 42) ) / 256;

        switch (i)
        {
            case 0: red = value;   green = t;       blue = p;     break;
            case 1: red = q;       green = value;   blue = p;     break;
            case 2: red = p;       green = value;   blue = t;     break;
            case 3: red = p;       green = q;       blue = value; break;      
            case 4: red = t;       green = p;       blue = value; break;        
            case 5: red = value;   green = p;       blue = q;     break;
      }

      setColorRGB(red, green, blue);
   }
}

Das ist der Code mit Fehlerkorrektur und der Behebung des 
Programmierfehlers.


Ich bedanke mich für eure Unterstützung, möchte aber gleichzeitig auf 
keinen Fall dem Ehrgeiz einiger hier (insbesondere Holgers) einen 
Abbruch tun. Wenns noch besser geht, dann gerne! :-)

[avr (Gast)]

Etwas geht noch:

void setColorHSV(unsigned char hue, unsigned char saturation, unsigned char value)
{
    unsigned char i, f;
    unsigned char  p, q, t;
    unsigned char red, green, blue;

        red = green = blue = value;  //**  neue Vorbesetzung

//    if (saturation != 0)  //Farbsättigung ist nicht Null -> Einteilen in 60°-Winkel des Farbtons
//    {
        i = hue / 43;
        f = hue % 43;
        p = ((unsigned int)value * (unsigned char)(255 - saturation)) / 256;
        q = (value * ((10710 - ( (unsigned int)saturation * f) )  / 42) ) / 256;
        t = (value * ((10710 - ((unsigned int)saturation * (unsigned char)(42 - f)) )  / 42) ) / 256;

        switch (i)
        {        
                         // vorbesetzte Farben nutzen
            case 0:              green = t;       blue = p;  break;
            case 1: red = q;                      blue = p;  break;
            case 2: red = p;                      blue = t;  break;
            case 3: red = p;     green = q;                  break;      
            case 4: red = t;     green = p;                  break;        
            case 5:              green = p;       blue = q;  break;
      }

      setColorRGB(red, green, blue);
  // }
}

man kann durch die Vorbesetzung mit Value ganz auf
die If verzichten da das Case selektiert (hier nur mit //).

avr

[S. T. (cmdrkeen)]

eine division durch 256 ist gleichbedeutend mit x>>8  8 bits nach rechts 
schieben, falls dein compiler das nicht schon macht ... probiers doch 
mal :)

[Klaus (Gast)]

> eine division durch 256 ist gleichbedeutend mit x>>8  8 bits nach rechts
> schieben, falls dein compiler das nicht schon macht ... probiers doch
> mal :)

Das is so ziemlich die älteste Optimierung, die ein Compiler von selber 
macht...

[Frank N. (betafrank)]

An anderen Stellen kann ja auch noch was rausgeholt werden:

int main(void) __attribute__((noreturn)); //Spart 32 Byte
int main(void){ ... }

[matze (Gast)]

@Frank:

Hat das irgendwelche Nebenwirkungen? Warum macht das der Compiler nicht 
selbst? Und: Bei mir spart das genau 8 Byte.

[Vlad T. (vlad_tepesch)]

der compiler ist sogar noch schlauer, der schiebt gar nicht, der nimmt 
einfach das obere byte

[Anja (Gast)]

hallo,

die beiden Zeilen
((10710 - ( (unsigned int)saturation * f) )  / 42) )
((10710 - ((unsigned int)saturation * (unsigned char)(42 - f)) )  / 42)
ergänzen sich zu einer Konstanten:
-> die 2. Zeile ist durch simple Subtraktion der 1. Zeile von einer 
Konstanten (255/256) möglich.

[Vlad T. (vlad_tepesch)]

matze schrieb:
> @Frank:
>
> Hat das irgendwelche Nebenwirkungen? Warum macht das der Compiler nicht
> selbst? Und: Bei mir spart das genau 8 Byte.

das spart ein wenig am epilog der main-funktion, der ja nicht gebraucht 
wird, da ja normalerweise eine endlosschleife in der main werkeln.
aber wieviel es spart hängt glaub ich auch aein wenig vom controller ab, 
auf nem tiny13 hat mir das glaub ich 12 Byte gespart. auf nem mega88 
warns nur 8B

[Frank N. (betafrank)]

Wie Vlad sagt, auf einem µC braucht main nichts zurückgeben. Wieviel man 
spart, hängt wohl von Compilerversion, Controller etc. ab.

Vielleicht läßt sich auch am makefile noch tunen. Eventuell erlaubt die 
Anwendung:

CFLAGS += -mtiny-stack    #Stack auf 256 begrenzt (GCC 4.3.0)

[yalu (Gast)]

Hallo matze,

ich habe mal die Numerik etwas optimiert, den Switch von avr und den
noreturn von Frank übernommen:

#include <stdio.h>
#include <stdint.h>

volatile uint8_t dummy;

void setColorRGB(uint8_t r, uint8_t g, uint8_t b) {
  dummy = r; dummy = g; dummy = b;
}

void setColorHSV4(uint8_t h, uint8_t s, uint8_t v) {
  uint16_t vs=v*s, h6=6*h, f;
  uint8_t i, p, u, r=v, g=v, b=v;

  p = (v<<8)-vs >> 8;
  i = h6 >> 8;
  f = ((i|1)<<8) - h6;
  if(i&1)
    f = -f;
  u = ((uint32_t)v<<16) - (uint32_t)vs*f >> 16;
  switch(i) {
    case 0: g = u; b =  p; break;
    case 1: r = u; b =  p; break;
    case 2: r =  p; b = u; break;
    case 3: r =  p; g = u; break;
    case 4: r = u; g =  p; break;
    case 5: g =  p; b = u; break;
  }
  setColorRGB(r, g, b);
}

int main(void) __attribute__((noreturn));
int main(void) {
  int h=100, s=250, v=255;
  setColorHSV4(h, s, v);
  for(;;);
}

Man kommt jetzt ohne die Divisionen aus, und die Ergebnisse sind
genauer. Da aber statt der Division nun eine 32-Bit-Multiplikation
benötigt wird, ist der Code-Größe gegenüber der Version von avr kaum
geschrumpft, mit dem GCC 5.3.4 ist er sogar ein ganzes Stück größer
geworden.

Die folgenden Codegrößen beziehen sich jeweils auf das fertig gelinkte
Programm incl. der obigen Dummy-setColorRGB-Funktion, dem obigen Main
und den benötigten Bibliotheksfunktionen. Bei der Originalversion habe
ich den Datentyp der Argumente von char in unsigned char geändert, da
sonst nicht richtig gerechnet wird.

------------------------------------
AVR-GCC          4.2.4  4.3.4  4.4.2
------------------------------------
Original          506    476    458
Version von avr   438    412    398
meine Version     442    454    390
------------------------------------

Die Diagramme im Anhang zeigen die Abweichungen der Ergebnisse von
matzes ("deins") und meinem ("meins") Programm zum jeweils exakten Wert,
den ich mit Double-Genauigkeit berechnen lassen habe. Dabei ist s=250,
v=255, h läuft von 0 bis 255.

Ich habe mein Programm nur auf dem PC getestet, dabei aber durch
Einfügen zusätzlicher Casts die 16-Bit-Integer-Rechengenauigkeit des AVR
simuliert. Deswegen vermute ich, dass das Programm auch auf dem AVR
richtig rechnet, aber ganz sicher bin ich mir nicht ;-)

Falls Fehler auftreten, einfach meckern! Vielleicht kann ich dann noch
etwas geradebiegen.