C-Funktionen direkt hintereinander legen / Sprungtabellen

Schnelle objektorientierte, kompilierende Programmiersprache.
Antworten
Benutzeravatar
naums
Beiträge: 740
Registriert: Sa Jan 02, 2010 10:40 pm
Kontaktdaten:

C-Funktionen direkt hintereinander legen / Sprungtabellen

Beitrag von naums » Fr Okt 14, 2016 4:34 pm

Ahoi.

Ich arbeite derzeit an einem Projekt, welches verlangt, dass ich eine generische Funktion habe und je nachdem welcher Datentyp tatsächlich vorliegt in eine andere Funktion springe. Bspw. habe ich die Funktion brighten. Die such anhand der Information ob ein RGB, RGBA, CMYK, ...-Bild vorliegt nach der passenden Funktion und führt die dann aus. Das Ganze soll natürlich in O(1) laufen. Außerdem will ich zur Programmierzeit recht leicht neue Funktionen hinzufügen können bzw. durch Setzen von Konstanten zur Compilezeit Typen entfernen lassen können.

Mein aktueller Ansatz wäre ein enum zu haben mit den Bilddatentypen (RGB=0, RGBA=1, ..) und entweder ein struct oder ein Array von Funktionen derart:

Code: Alles auswählen

struct brighten {
    void (*brightenRGB) (struct Image* img, ...);
    void (*brightenRGBA) (struct Image* img,... );
    // ...
};

// bzw.
void* brighten_fct [ /** todo **/ ] = { (void*) brightenRGB, (void*) brightenRGBA, NULL, (void*) brightenCMYK };
Nachteil beim struct: irgendeiner(tm) muss zur Laufzeit die Elemente belegen. Nachteil beim Array: jedes einzelne Element müsste NULL gesetzt werden, wenn die Funktionalität nicht eingebaut werden soll (also 1 #ifdef pro Funktion!).

PS: Suchen gänge bei beiden mithilfe des Enum-Werts als Offset. Allerdings müssten bei Fehlen von Funktionen die höheren Enum-Werte trotzdem belegt werden, d.h. dürfen nicht weiter nach vorn rutschen. Das ist aber kein Problem.

PPS: Gesucht sind ausschließlich C99 Lösungen. Kein C++ und preferabel kein neueres C. Am liebsten auch keine stdlib.

Fällt jemandem von euch eine schlauere Idee ein? Alles was dynamisches Laden oder dynamisches Speichermanagment voraussetzt ist nicht möglich, weil ich die Library auch gerne low level einsetzen können will (mal sehen wie das ausgeht...)

MfG Naums
.globl truth
truth:
mov r0, #42
mov pc, lr

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: C-Funktionen direkt hintereinander legen / Sprungtabelle

Beitrag von cloidnerux » Sa Okt 15, 2016 5:49 pm

An sich hast du doch folgendes Problem:

Du bekommst ein Bild, dieses hat einen Farbraum(die Variable). Du willst jetzt je nach Farbraum eine andere Funktion aufrufen. Was du also brauchst, ist eine Liste an Tupeln Farbraum-Funktionspointer für deine diversen Funktionen.
Die Liste kannst du entweder hart codieren oder aus einer Einstellungsdatei laden.

Dann die frage: Warum bist du auf C99 gezwungen? Legacy code? Embedded Plattform?
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
naums
Beiträge: 740
Registriert: Sa Jan 02, 2010 10:40 pm
Kontaktdaten:

Re: C-Funktionen direkt hintereinander legen / Sprungtabelle

Beitrag von naums » So Okt 16, 2016 7:29 am

Problembeschreibung ist an sich richtig, aber: Finden von Funktionen in O(1), keine dyn. Speicherverwaltung.

C99 ist meine Wahl. Der Code sollte später(tm) teil eines "Betriebssystems" für Raspberry Pi werden, weshalb auch stdlib eigentlich rausfallen. Ich weiß, dass ich mir bspw. newlib reinbauen kann, aber das ist grade nicht Sinn der Übung. Wenn dann selbst machen.
.globl truth
truth:
mov r0, #42
mov pc, lr

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: C-Funktionen direkt hintereinander legen / Sprungtabelle

Beitrag von Xin » So Okt 16, 2016 1:31 pm

naums hat geschrieben:Ahoi.

Ich arbeite derzeit an einem Projekt, welches verlangt, dass ich eine generische Funktion habe und je nachdem welcher Datentyp tatsächlich vorliegt in eine andere Funktion springe.
Das ist klassisches OOP. Verpass Deinem Datentyp eine Sprungtabelle und frag diese nach der statischen Funktion "brighten", die als ersten Parameter die Instanz Deines Datentyps bekommt: "this".

Kein Suchen, O(1), alles was Du brauchst. Und Du kannst die Sprungtabelle nach belieben erweitern.
Siehe C++-Tutorial, da gibt es ein Beispiel, was 1:1 passt und in OOP einführt. Das Beispiel ist reines C.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
naums
Beiträge: 740
Registriert: Sa Jan 02, 2010 10:40 pm
Kontaktdaten:

Re: C-Funktionen direkt hintereinander legen / Sprungtabelle

Beitrag von naums » So Okt 16, 2016 8:55 pm

Was du meinst sind die vTables? Das könnte ich machen, die haben aber den Nachteil, dass ich die Zuordnung von Funktionen zum "Objekt" zur Laufzeit machen muss. D.h. wenn ein anderer Programmierer weitere Farbmodelle hinzufügt, dann muss der tiefer in meinen Code rein, nicht nur ein paar structs / arrays anpassen.

Weiter brauche ich, um die Initialisierungsfunktion halbwegs effizient programmieren zu können, immernoch ein Array bzw. struct mit den möglichen Werten für die Funktionspointer. Ich kann ja schlecht hart reinkodieren, dass für RGB bitte brightenRGB, für RGBA brightenRGBA, ... genommen wird. (technisch geht das, ist aber nicht sonderlich gut wartbar).

Ich sehe also den Vorteil nicht, die OOP-Variante zu nehmen, wenn ich Arrays aufbauen kann pro Operation mit allen verfügbaren Funktionen sortiert nach Farbmodell.
.globl truth
truth:
mov r0, #42
mov pc, lr

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: C-Funktionen direkt hintereinander legen / Sprungtabelle

Beitrag von Xin » So Okt 16, 2016 10:45 pm

naums hat geschrieben:Was du meinst sind die vTables? Das könnte ich machen, die haben aber den Nachteil, dass ich die Zuordnung von Funktionen zum "Objekt" zur Laufzeit machen muss. D.h. wenn ein anderer Programmierer weitere Farbmodelle hinzufügt, dann muss der tiefer in meinen Code rein, nicht nur ein paar structs / arrays anpassen.
Du musst so oder so jedem Objekt eine Kennung mitgeben, damit Du Dich für eine Funktion entscheiden kannst und die Kennung musst Du zur Laufzeit setzen. Du kannst ein enum setzen oder eben eine vTable.
naums hat geschrieben:Weiter brauche ich, um die Initialisierungsfunktion halbwegs effizient programmieren zu können, immernoch ein Array bzw. struct mit den möglichen Werten für die Funktionspointer. Ich kann ja schlecht hart reinkodieren, dass für RGB bitte brightenRGB, für RGBA brightenRGBA, ... genommen wird. (technisch geht das, ist aber nicht sonderlich gut wartbar).

Ich sehe also den Vorteil nicht, die OOP-Variante zu nehmen, wenn ich Arrays aufbauen kann pro Operation mit allen verfügbaren Funktionen sortiert nach Farbmodell.
Und das findest Du leichter wartbar...? ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
naums
Beiträge: 740
Registriert: Sa Jan 02, 2010 10:40 pm
Kontaktdaten:

Re: C-Funktionen direkt hintereinander legen / Sprungtabelle

Beitrag von naums » So Okt 16, 2016 11:22 pm

Xin hat geschrieben:
naums hat geschrieben:Was du meinst sind die vTables? Das könnte ich machen, die haben aber den Nachteil, dass ich die Zuordnung von Funktionen zum "Objekt" zur Laufzeit machen muss. D.h. wenn ein anderer Programmierer weitere Farbmodelle hinzufügt, dann muss der tiefer in meinen Code rein, nicht nur ein paar structs / arrays anpassen.
Du musst so oder so jedem Objekt eine Kennung mitgeben, damit Du Dich für eine Funktion entscheiden kannst und die Kennung musst Du zur Laufzeit setzen. Du kannst ein enum setzen oder eben eine vTable.
Ja, aber woher bekomme ich die Funktionen, die ich für genau diesen Bildtyp brauche, sodass ich schnell einen neuen Bildtyp hinzufügen kann? Dann brauche ich eben doch wieder eine Matrix oder mehrere Felder, was die Fkt-ptr enthält. Damit kann ich die Zuordnung zu einzelnen instantiierten structs sein lassen, wenn ich dieses Feld ohnehin brauche, und sowas wie Vererbung nicht stattfindet, d.h. für jedes struct dieses Farbmodells die gleiche Funktion zu nehmen ist.

Genau genommen wäre deine Variante generischer, weil sie mir erlaubt zur Laufzeit Funktionen auszutauschen, was die statische Array-Variante quasi verbietet, vor allem deshalb, weil ich das Array zur Laufzeit nicht verändern will, d.h. zur Compilezeit klar sein müsste, welche Funktionen da drin stehen.
Xin hat geschrieben:
naums hat geschrieben:Weiter brauche ich, um die Initialisierungsfunktion halbwegs effizient programmieren zu können, immernoch ein Array bzw. struct mit den möglichen Werten für die Funktionspointer. Ich kann ja schlecht hart reinkodieren, dass für RGB bitte brightenRGB, für RGBA brightenRGBA, ... genommen wird. (technisch geht das, ist aber nicht sonderlich gut wartbar).

Ich sehe also den Vorteil nicht, die OOP-Variante zu nehmen, wenn ich Arrays aufbauen kann pro Operation mit allen verfügbaren Funktionen sortiert nach Farbmodell.
Und das findest Du leichter wartbar...? ^^
Der Aufwand neue Farbmodelle bzw. Funktionen hinzuzufügen dürfte geringer sein als wenn ich eine vTable nehme und hardcodiere wann welche reingeschrieben wird. Quasi gleich beim hybriden Ansatz beides zu machen.

PS: Merke wie die struct-Idee verschwunden ist, Arrays bieten wahrsch. den eleganteren Zugriff und "bessere" Wartbartkeit.
.globl truth
truth:
mov r0, #42
mov pc, lr

Benutzeravatar
naums
Beiträge: 740
Registriert: Sa Jan 02, 2010 10:40 pm
Kontaktdaten:

Re: C-Funktionen direkt hintereinander legen / Sprungtabelle

Beitrag von naums » Do Okt 20, 2016 8:29 pm

Hallo.

Als Nachtrag bzw. Abschluss des Themas. Habe nun einen hybride Variante genommen, d.h. mithilfe der Funktionstabelle im struct, die dynamisch zur Laufzeit geändert werden könnte. Die Funktionen werden von generischen Funktionen aufgerufen, und durch eine init-Funktion gesetzt. Hier die Codeschnipsel. Unter https://github.com/naums/yailfc der vollständige wenn auch noch unvollständige Code.

Code: Alles auswählen

/// image.h:
struct ImageVTable
{
    void (*brighten) (struct Image*, int16_t);
    void (*contrast) (struct Image*, int16_t);
    int (*resize) (struct Image*, struct Image*, uint32_t, uint32_t, enum Interpolation_t);
    void (*swap) (struct Image*, int type);
    int (*rotate) (struct Image*, struct Image*, float, enum Interpolation_t);
    int (*printChar) (struct Image*, uint32_t, uint32_t, void*, const char);
} typedef ImageVTable;

struct Image
{
    enum ImageColor bitdepth;   ///< color model used for this image
    int32_t width;              ///< width of the image in pixel
    int32_t height;             ///< height of the image in pixel
    void *payload;              ///< one-dimensional array of pixel-data (hopefully big enough)
    struct ImageVTable vtable;
} typedef Image;

/// image.c
void (*fn_brighten[3]) (struct Image*, int16_t) = { brightenRGB, NULL, NULL };
void (*fn_contrast[3]) (struct Image*, int16_t) = { contrastRGB, NULL, NULL };
int (*fn_resize[3]) (struct Image*, struct Image*, uint32_t, uint32_t, enum Interpolation_t) = { resizeRGB, NULL, NULL };
void (*fn_swap[3]) (struct Image*, int) = {swapRGB, NULL, NULL};
int (*fn_rotate[3]) (struct Image*, struct Image*, float, enum Interpolation_t) = { rotateRGB, NULL, NULL };
int (*fn_printChar[3]) (struct Image*, uint32_t, uint32_t, void*, const char) = { printCharRGB, NULL, NULL };

struct Image createImage ( enum ImageColor bitdepth, int32_t w, int32_t h, void* payload )
{
    struct Image img;
    img.bitdepth = bitdepth;
    img.width = w;
    img.height = h;
    img.payload = payload;
    
    img.vtable.brighten = fn_brighten[(int) bitdepth];
    img.vtable.contrast = fn_contrast[(int) bitdepth];
    img.vtable.resize   = fn_resize  [(int) bitdepth];
    img.vtable.swap     = fn_swap    [(int) bitdepth];
    img.vtable.rotate   = fn_rotate  [(int) bitdepth];
    img.vtable.printChar = fn_printChar [(int) bitdepth];
    
    return img;
}

/// generische brighten-funktion
void brighten ( struct Image* img, int16_t value )
{
    if (img->vtable.brighten != NULL)
        img->vtable.brighten(img, value);
}
Nachteil der Vorgehensweise ist, dass in image.h und image.c die imageRGB.h eingebunden werden muss, weil die Funktionen brightenRGB, etc bekannt sein müssen. Das könnte man zwar über #ifdefs und Compiler-Paramter (-D..) lösen, aber das finde ich sehr schlecht lesbar.

Riesenvorteil: man könnte ein InPlace-Convert der Bilddaten vornehmen, d.h. von RGB auf YCbCr o.Ä. Das geht natürlich nur dann, wenn die Farbmodelle übereinander passen. Weiter wäre es möglich Bilder zu definieren, wo bspw. die brighten-Funktion bestimmte Eigenschaften enthält oder erhält, bspw. Ränder schwarz belässt, Wasserzeichen drübersetzt, etc.

Bei Fragen oder weiteren Anmerkungen könnte ich gern antworten und diskutieren, ob das so eine clevere Idee ist.
.globl truth
truth:
mov r0, #42
mov pc, lr

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: C-Funktionen direkt hintereinander legen / Sprungtabelle

Beitrag von Xin » Fr Okt 21, 2016 10:00 am

Und wo genau liegt jetzt der Unterschied zu einer C++-VTable bzw. wenn Du für jedes Objekt eine "ImageVTable" anlegen musst, wo liegt der Unterschied zu Funktionspointern?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
naums
Beiträge: 740
Registriert: Sa Jan 02, 2010 10:40 pm
Kontaktdaten:

Re: C-Funktionen direkt hintereinander legen / Sprungtabelle

Beitrag von naums » Mo Okt 24, 2016 4:44 pm

Ich verstehe die Frage nicht. Es ging mir darum halbwegs effizient neue Funktionen vor der/zur Compilezeit hinzufügen zu können.
.globl truth
truth:
mov r0, #42
mov pc, lr

Antworten