Compiler Konstanten berechnen lassen

[Illuminatus]

Hallo Leute,

ich bin noch relativ unerfahren, was Programmierung in C++ angeht und deshalb hat sich mir folgende Frage gestellt:

Konstanten müssen ja schon zur Compilezeit bekannt sein und definiert werden (stimmt das?), eine Schleife wird aber immer erst zur Laufzeit ausgeführt (stimmt das auch?).

Wie bringe ich nun den Compiler dazu, mir in einer Schleife zur Compilezeit ein Array aus Konstanten aus einer bestimmten Formel zu berechnen?

Ich hoffe, ihr könnt mir weiterhelfen!

Grüße
Illuminatus

[theta]

Wie bringe ich nun den Compiler dazu, mir in einer Schleife zur Compilezeit ein Array aus Konstanten aus einer bestimmten Formel zu berechnen

Mittels Template Metaprogramming - hier ein Buch falls Du es genauer wissen möchtest:
http://www.boostpro.com/mplbook/

[asc]

Illuminatus schrieb:

Konstanten müssen ja schon zur Compilezeit bekannt sein und definiert werden (stimmt das?),...

Nicht zwangsweise, das liegt auch an dem Gültigkeitsbereich der Konstante (z.B. Lokal definiert...), sowie die Art der Initialisierung (z.B. kann man durchaus auch das Ergebnis einer Funktion binden).

class A
{
  public:
    int const a;
    A(int a) : a(a) {}
};

Hier ist die Konstante an die Lebenszeit einer Klasseninstanz gebunden, und muss bei der Initialisierung festgelegt werden.

Illuminatus schrieb:

eine Schleife wird aber immer erst zur Laufzeit ausgeführt (stimmt das auch?).

Wenn man einmal von Templatetechniken absieht, ja.

Illuminatus schrieb:

Wie bringe ich nun den Compiler dazu, mir in einer Schleife zur Compilezeit ein Array aus Konstanten aus einer bestimmten Formel zu berechnen?

Zur Compilezeit garnicht (Außer über Templatetechniken).

[SeppJ]

Illuminatus schrieb:

Konstanten müssen ja schon zur Compilezeit bekannt sein und definiert werden (stimmt das?), eine Schleife wird aber immer erst zur Laufzeit ausgeführt (stimmt das auch?).

Nein, es gibt verschiedene Arten von Konstanten:
1. Compilezeitkonstanten: Ausdrücke und Konstanten, die schon zur Compilezeit bekannt sind.
Z.B.

int a = 42; // Das Literal 42 ist eine Compilezeitkonstante
const int b = 33;  // Auch b ist eine Compilezeitkonstante

2. Const-Variablen, Variablen deren Wert erst zur Laufzeit feststeht, aber bei denen der Compiler erzwingt, dass sie sich nicht ändern können.

int a,b;
cin >> a >> b;
const summe = a + b;
++summe;  // Compilerfehler

Wie bringe ich nun den Compiler dazu, mir in einer Schleife zur Compilezeit ein Array aus Konstanten aus einer bestimmten Formel zu berechnen?

Ui, das ist hart. Mit Templatemetaprogrammierung kannst du Code quasi zur Compilezeit ausführen um damit Compilezeitkonstanten auszurechnen, die sonst schwer hinzuschreiben sind. Klassisches Beispiel ist immer die Fakultät:

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

void foo()
{
    int x = Factorial<4>::value; // == 24, als Compilezeitkonstante
}

Aber das ist vermutlich eines der anspruchsvollsten Themen in C++ überhaupt. Beschreib mal dein Problem genauer, vielleicht gibt es einfachere Lösungen.

edit: Mal wieder zu langsam...

[Illuminatus]

Danke für eure Antworten erstmal!

An tiefergehende Templateprogrammierung trau ich mich noch nicht ran, ich versuch es noch simpel zu halten, sofern es geht.

Konkret arbeite ich zur Zeit an einer eigenen MD5-Implementierung um mich ein bisschen in alle Bereiche von C++ einzuarbeiten.
Dabei will ich die Rundenkonstanten nicht alle definieren, sondern sie berechnen lassen und in ein konstantes Array packen. Bei dem Array handelt es sich um ein Klassenmitglied meiner MD5-Klasse, welches natürlich static sein soll.
Aktuell lass ich diese Rundenkonstanten im Konstruktor generieren, kann sie aber aus diesem Grund auch nicht in einer const Variable speichern, da sie ja dazu über die Initialisierungsliste mitgegeben werden müssten.

Ich hoffe, ihr habt den Sachverhalt ungefähr verstanden!

[volkard]

Vielleicht bei Programmstart bauen lassen? Mußt mal schauen, wieviel const man noch reindrücken kann.

class Md5{
   static UInt32* table;
   ...
};
UInt32* Md5::table=calcDaTable();

UInt32* calcDaTable(){
   static UInt32 daTable[4711];
   for(...
   return daTable;
}

[tülüwülülü]

Warum muss es zur Compilezeit sein? Du kannst auch sowas in die MD5 Funktion machen.

static std::vector<int> foo = getRundenkonstanten();

[SeppJ]

Da es doch 'nur' so um die 64 kleine Zahlen sind und die Funktion zur Berechnung sich nicht ändern wird (was ist bei MD5 eigentlich die Funktion dahinter? Ich dachte die wären willkürlich gewählt), wäre es doch eine Überlegung wert, vermeintliche Eleganz sein zu lassen und die Werte einfach fest einzubauen. Das sollte wesentlich kürzer und übersichtlicher sein.

[Illuminatus]

const unsigned int * generateK();

class MD5
{
private:
static const unsigned int k[64] = generateK();
}

Das bringt mir jetzt folgenden Fehler:

'const unsigned int* generateK()' cannot appear in a constant-expression

Wo ist der Fehler?

@SeppJ: Ja, das wäre in diesem Fall sicher eine Überlegung wert und wird auch in vielen Implementationen so gehandhabt, aber ich will ja auch ein bisschen dabei lernen

[krümelkacker]

M A K E ( kennt das noch jemand? :p )

Makefile:

programm: programm.o
	$(CXX) -o $@ $^

programm.o: table.inc programm.cpp

table.inc: make_table
	./make_table > table.inc

make_table: make_table.o
	$(CXX) -o $@ $^

programm.cpp

#include <iostream>

const int tabelle[] = {
  #include "table.inc"
};

int main() {
  return 0;
}

[SeppJ]

Illuminatus schrieb:

Das bringt mir jetzt folgenden Fehler:

'const unsigned int* generateK()' cannot appear in a constant-expression

Wo ist der Fehler?

Ist doch ziemlich eindeutig. Links steht etwas, was du als Compilezeitkonstante kenntlich gemacht hast, rechts aber ein Laufzeitwert. In C++1 könnte man da evtl. was mit constexpr machen (bin mit den neuen Features von C++11 noch nicht so fit, weiß nicht ob das stimmt), falls das dein Compiler schon kann.

edit: Ja, constexpr müsste gehen, wenn du es explizit zur Initialisierung des Feldes benutzt und die Rechnung in eine einzige return-Anweisung quetschen kannst. Die dann weitere constexpr benutzen darf. Aber z.B. Schleifen werden schwierig, da sind wir schon fast wieder bei den Techniken der Templatemetaprogrammierung.

[Illuminatus]

SeppJ schrieb:

Ist doch ziemlich eindeutig. Links steht etwas, was du als Compilezeitkonstante kenntlich gemacht hast, rechts aber ein Laufzeitwert

Das leuchtet mir jetzt nicht ein. Wenn "const summe = a + b" funktioniert, warum funktioniert dann mein Ausdruck nicht? Warum ist mein Ausdruck unbedingt eine Compilezeitkonstante?

[Illuminatus]

Nachdem ich die Definition der Konstante außerhalb der Klasse vorgenommen habe und das ganze nicht als Array sondern als Pointer deklariert habe, funktioniert es. Mag mir das jemand erklären?

[SeppJ]

Illuminatus schrieb:

Das leuchtet mir jetzt nicht ein. Wenn "const summe = a + b" funktioniert, warum funktioniert dann mein Ausdruck nicht? Warum ist mein Ausdruck unbedingt eine Compilezeitkonstante?

Weil dein generateK() eine Funktion ist, const Rückgabewert hin oder her. Der Compiler kann/darf nicht in die Funktion gucken, ob der Ausdruck dort eine Compilezeitkonstante ist. Das const am Rückgabewert macht gar nichts. Folgendes ist absolut legal:

const int nicht_konstant()
{
 return rand();
}

Um trotzdem so etwas wie

int konstant()
{
 return 5;
}

// ...
const int = konstant(); // Geht nicht!

zu ermöglichen ist das schon erwähnte constexpr eingeführt worden:

constexpr int konstant()
{
 return 5;
}

// ...
const int = konstant(); // Geht auf den neuesten Compilern.

Im Zusammenspiel mit Arrays dürfte das jedoch etwas schwierig sein, wegen der ungewöhnlichen Rückgabesemantik. Möglich, dass es irgendwelche Tricks dafür gibt.

[camper]

Könnte z.B. so aussehen

#include <cstdint>
#include <cmath>
///////////////////////
// Ein paar Hilfstemplates um nicht alle Indizes aufzählen zu müssen
template <std::size_t... i> struct indexes
{
    typedef indexes type;
};

template <typename T, typename U> struct concat
    : concat<typename T::type, typename U::type> {};
template <std::size_t... i, std::size_t...j> struct concat<indexes<i...>, indexes<j...>>
    : indexes<i..., ( j + sizeof... i )...> {};

template <typename T> struct twice
    : concat<T, T> {};

template <std::size_t N> struct make_indexes
    : concat<twice<make_indexes<N / 2>>, make_indexes<N % 2>> {};
template <> struct make_indexes<1>
    : indexes<0> {};
template <> struct make_indexes<0>
    : indexes<> {};
///////////////////////////////////////////

constexpr std::uint32_t compute_md5_element(std::uint32_t i)
{
    return std::fabs( std::sin( i + 1 ) ) * 4294967296.0;
}

template <typename = make_indexes<64>::type> struct md5_table;
template <std::size_t... i> struct md5_table<indexes<i...>>
{
    static const std::uint32_t data[sizeof... i];
};
template <std::size_t... i>
const std::uint32_t md5_table<indexes<i...>>::data[sizeof... i] = { compute_md5_element( i )... };

// Eigentlich:
//template <std::size_t... i> struct md5_table<indexes<i...>>
//{
//    static constexpr std::uint32_t data[] = { compute_md5_element( i )... };
//};
// Aber gcc kommt mit dieser Syntax noch nicht zurecht

Das gewünschte Ergebnis ist dann einfach md5_table<>::data

[Illuminatus]

SeppJ schrieb:

Weil dein generateK() eine Funktion ist, const Rückgabewert hin oder her. Der Compiler kann/darf nicht in die Funktion gucken, ob der Ausdruck dort eine Compilezeitkonstante ist. Das const am Rückgabewert macht gar nichts.

Warum funktioniert das ganze dann aber wenn ich die Definition außerhalb der Klasse vornehme?

[camper]

Illuminatus schrieb:

SeppJ schrieb:

Weil dein generateK() eine Funktion ist, const Rückgabewert hin oder her. Der Compiler kann/darf nicht in die Funktion gucken, ob der Ausdruck dort eine Compilezeitkonstante ist. Das const am Rückgabewert macht gar nichts.

Warum funktioniert das ganze dann aber wenn ich die Definition außerhalb der Klasse vornehme?

Ohne Code gibts nur Glaskugelraten.

[Illuminatus]

class MD5
{
private:
static const unsigned int * k;
}

const unsigned int * MD5::k = generateK();

[SeppJ]

So wie du es jetzt schreibst, ist das eine Laufzeitkonstante die zum Programmstart ausgewertet wird:

#include <iostream>

const unsigned int * generateK()
{
  std::cout<<"Dies passiert erst zur Laufzeit\n";
  return 0;
}

class MD5
{
private:
  static const unsigned int * k;
};

const unsigned int * MD5::k = generateK();

int main(){}

Wird so vielleicht noch deutlicher:

const unsigned int generateK();

class MD5
{
public:
  static const unsigned int k;
};

const unsigned int MD5::k = generateK();

int main()
{
  int foo[MD5::k]; // Nur mit speziellen Compilererweiterungen für VLAs möglich
}

[314159265358979]

camper ist ein kranker Freak. Vielleicht kann der Freak ja seinen Code erklären?