3. brainfuck-Compiler TMP style

brainfuck-Compiler TMP style

  • E

    Also, da muss ich etwas weiter ausholen. 😋
    Ich schreibe gerne Hacks für Spiele, die im Speicherbereich eines anderen Prozesses laufen, also per DLL-Injection. Nun benutze ich Linux und mache das auch mit Windows-Programmen, per Wine. Nun ist es aber so, dass unter Windows manche Funktionen gänzlich andersaufgerufen werden müssen ( http://en.wikipedia.org/wiki/X86_calling_conventions ), auch wenn der GCC da helfen kann, es funktioniert nicht immer. Die dreckige Lösung: Inline Assembler.

    Jetzt dachte ich mir, es wäre nett diese Calling-Conventions direkt in C++ zu definieren (Der Nte Integer/Float Parameter kommt in Register X), sollte zur Compilezeit kein Problem sein. Und dann damit und mit AsmJit ( http://code.google.com/p/asmjit/ ) zur Compilezeit Wrapperfunktionen bauen, in etwa so habe ich mir das vorgestellt:

    typedef calling_convention<RCX, RDX, R8, R9> windows_64;
typedef calling_convention<RDI, RSI, RDX, RCX, R8, R9> system_v_amd64;
auto malloc_wrapper = system_v_amd64::wrap_call<windows_64, void*, std::size_t>(&std::malloc);
void* ptr = malloc_wrapper(123);

    Habe mir dazu schon einiges an Gedanken gemacht, leider macht mein mangelndes Können in Sachen TMP immer wieder alles kaputt. 🤡

    0
  • 3

    Und ich habe keine Ahnung von Calling Conventions. 😃

    @Hacker: Hier mal eine schnell hingefrickelte Version eines "normalen" BF-Interpreters.

    #include <iostream>

void bf_run(char const* codeptr, unsigned char* memptr)
{
	while(*codeptr)
	{
		switch(*codeptr)
		{
		case '.':
			std::cout << static_cast<char>(*memptr);
			break;

		case ',':
			std::cin.read(reinterpret_cast<char*>(memptr), 1);
			break;

		case '>':
			++memptr;
			break;

		case '<':
			--memptr;
			break;

		case '+':
			++*memptr;
			break;

		case '-':
			--*memptr;
			break;

		case '[':
			++codeptr;

			while(*memptr)
				bf_run(codeptr, memptr);

			while(*codeptr && *codeptr != ']')
				++codeptr;

			break;

		case ']':
			return;

		default:
			break;
		}

		++codeptr;
	}
}

int main()
{
	// Hello, World!\r\n
	char const source[] =
	"++++++++++"
	"["
	">+++++++>++++++++++>+++>+<<<<-"
	"]"
	">++."
	">+."
	"+++++++."
	"."
	"+++."
	">++."
	"<<+++++++++++++++."
	">."
	"+++."
	"------."
	"--------."
	">+."
	">."
	"+++.";

	unsigned char memory[1024] = {};

	bf_run(source, memory);
}

    http://ideone.com/EVnTV

    0
  • C
    Mod

    314159265358979 schrieb:

    *push*

    Na, wie siehts aus? :p

    Mach ich, wenn mir mal wieder langweilig genug ist.

    Wenn du Probleme zum Lösen brauchst, hab ich ein paar (Schwierigkeitsgrad variiert, und einige Lösungen sind bekannt):

    Jedes Pack-Problem lässt sich in ein Problem mit Indexlisten (eine Templateklasse, deren Templateargumente ein einziges Pack aus Integern darstellen) umformulieren, also stelle ich die Probleme auch so:

    • 1. Erstelle eine Templatemetafunktion, die aus einer Indexliste zwei Listen erzeugt, in der jeweils die erste und die zweite Hälfte der Indizes enthalten ist F<0,1,2,3> -> <0,1>, <2,3>
    • 2. Erstelle eine Templatemetafunktion, die aus einer Indexliste zwei Listen erzeugt, in der jeweils die erste N und der Rest der Indizes getrennt werden F<<0,1,2,3,4,5>,2> -> <0,1>, <2,3,4,5>
    • 3. Erstelle eine Templatemetafunktion, die das letzte Element zurückgibt: F<0,1,2,3> -> 3
    • 4. Erstelle eine Templatemetafunktion, die das N-te Element zurückgibt: F<<5,6,7,8>,2> -> 7
    • 5. Erstelle eine Templatemetafunktion, die zwei Listen mischt, so dass die Elemente aus beiden Listen jeweils abwechseln: F<<0,1,2,3>,<6,7,8,9>> -> <0,6,1,7,2,8,3,9>
    • 6. Erstelle eine Templatemetafunktion, die zwei Listen mischt, so dass jedes Element der einen Liste mit jedem der anderen Liste verknüft, Bonuspunkte, wenn die Verknüpfung selbst ein Parameter ist
      z.B. F<<0,1,2>, <10,11,12>> -> <0+10,0+11,0+12,1+10,1+11,1+12,2+10,2+11,2+12>
    • 7. Erstelle eine Templatemetafunktion, die eine Liste erzeugt, in der die Elemente der ersten Liste sooft wiederholt werden, wie das korrespondierende Element der zweiten Liste vorgibt
      F<<0,1,2>,<3,1,2>> -> <0,0,0,1,2,2>

    Die Lösung sollte optimal in Hinblick auf Tiefe der rekursiven Instantiierung, algorithmische Komplexität und Speicherverbrauch sein. Bonuspunkte, wenn diese Kriterien gleichzeitig vorliegen (es kann durchaus mehrere Lösungen je nach Schwerpunkt geben).

    0
  • ?

    314159265358979 schrieb:

    @Hacker: Hier mal eine schnell hingefrickelte Version eines "normalen" BF-Interpreters.

    #include <iostream>

void bf_run(char const* codeptr, unsigned char* memptr)
{
	while(*codeptr)
	{
		switch(*codeptr)
		{
		case '.':
			std::cout << static_cast<char>(*memptr);
			break;

		case ',':
			std::cin.read(reinterpret_cast<char*>(memptr), 1);
			break;

		case '>':
			++memptr;
			break;

		case '<':
			--memptr;
			break;

		case '+':
			++*memptr;
			break;

		case '-':
			--*memptr;
			break;

		case '[':
			++codeptr;

			while(*memptr)
				bf_run(codeptr, memptr);

			while(*codeptr && *codeptr != ']')
				++codeptr;

			break;

		case ']':
			return;

		default:
			break;
		}

		++codeptr;
	}
}

int main()
{
	// Hello, World!\r\n
	char const source[] =
	"++++++++++"
	"["
	">+++++++>++++++++++>+++>+<<<<-"
	"]"
	">++."
	">+."
	"+++++++."
	"."
	"+++."
	">++."
	"<<+++++++++++++++."
	">."
	"+++."
	"------."
	"--------."
	">+."
	">."
	"+++.";

	unsigned char memory[1024] = {};

	bf_run(source, memory);
}

    http://ideone.com/EVnTV

    Schnell-hingefrickelt...
    Nicht Turing-Vollständig, aber abgesehen davon - kannst du Schleifen verschachteln? Und nebeneinander stehen können sie auch? :p

    0

  • Bei der Gelegenheit...

    Hier findet man sehr hübsche, schnelle und vor allem übersichtlich implementierte BF Interpreter:

    http://www.c-plusplus.net/forum/p2120628#2120628

    🤡

    0
  • 3

    @camper: Beispiel 1:

    template <typename, typename, int, int>
struct split_half_impl;

template <int HA, int... TA, int HB, int... TB, int NA, int NB>
struct split_half_impl<intlist<HA, TA...>, intlist<HB, TB...>, NA, NB>
	: split_half_impl<intlist<HA, TA..., HB>, intlist<TB...>, NA + 1, NB - 1>
{};

template <int HA, int... TA, int HB, int... TB, int N>
struct split_half_impl<intlist<HA, TA...>, intlist<HB, TB...>, N, N>
{
	typedef intlist<HA, TA...> first;
	typedef intlist<HB, TB...> second;
};

template <typename>
struct split_half;

template <int H, int... T>
struct split_half<intlist<H, T...>>
	: split_half_impl<intlist<H>, intlist<T...>, 1, sizeof...(T)>
{};

    Wie lieg ich so? 🤡

    (Für leere Listen sowie Listen mit ungerader Anzahl an Elementen hab ich mir die Implementierung erstmal erspart.)

    0
  • ?

    Hacker schrieb:

    Ethon schrieb:

    Also nur 'pseudo'.
    Trotzdem interessant, mach mal. 😉

    Was gibts eig. noch interessantes in der Richtung? Hab da grad voll Bock drauf 😃

    Hab grad einen Vortrag zu genau dem gleichen Thema gehört. Dort wurde ein Haskell Interpreter zur compile-Zeit gebaut: http://cppnow.org/files/2012/04/Sinkovics.Porkoláb.pdf

    0
  • 3

    ..

    0
  • 3

    Hey camper, sag doch mal was! 😞

    @Ethon: Ich finde deine Projektidee zwar interessant, aber ich kann damit immer noch nicht wirklich viel anfangen. Wie und wozu verwendet man sowas? 🤡

    0
  • ?

    314159265358979 schrieb:

    Hacker schrieb:

    Ethon schrieb:

    Also nur 'pseudo'.
    Trotzdem interessant, mach mal. 😉

    Was gibts eig. noch interessantes in der Richtung? Hab da grad voll Bock drauf 😃

    Unendlich viel. Schreib nen Mathe-Parser. Schreib einen Mergesort für Wert-Parameter. etc.

    So, mit dem Mathe-Parser bin ich praktisch fertig. Mergesort für Wertparameter - was ist daran so "aufregend" (ich habe glaub' ich nicht ganz verstanden was gefragt ist)?

    0
  • 3

    Zeig doch mal her den Matheparser.

    0
  • ?

    314159265358979 schrieb:

    Zeig doch mal her den Matheparser.

    Wenn du sicher bist, dass dein Magen das aushält... ich mach grad nen neuen Post.

    0
  • ?

    http://ideone.com/O77pp

    Den Dingensda am Anfang hab ich gebastelt, da mir die Reihenfolge der Speicherfreigabe (und der Destruktor-aufrufe) herzlich egal ist und ich keine lust hab es selbst zu machen... ( boost::ptr_set o. ä. hab ich ja nicht ^^)

    0
  • 3

    Mal abgesehen, dass man da jetzt noch viel verbessern kann: Was hat das mit TMP zu tun? 😕

    0
  • ?

    314159265358979 schrieb:

    Mal abgesehen, dass man da jetzt noch viel verbessern kann: Was hat das mit TMP zu tun? 😕

    Nein, es ist ein normaler Parser. Aber TMP werd ich jetzt auch mal versuchen 😃 Ich wusste nicht, dass du einen TMP wolltest ^^

    0
  • ?

    Aber wie soll ich output zur Compile-Zeit machen? Ein static_assert(0, "..."); oder wie...? 😕

    0
  • ?

    Ah nee, ich werd mich wohl mit boost::mpl auseinandersetzen müssen...

    0
  • 3

    Was willst du denn da ausgeben? Du brauchst doch nur eine Zahl als Ergebnis.

    std::cout << eval<'2', '+', '2'>::value;

    Oder so ähnlich.

    0
  • ?

    314159265358979 schrieb:

    Was willst du denn da ausgeben? Du brauchst doch nur eine Zahl als Ergebnis.

    std::cout << eval<'2', '+', '2'>::value;

    Oder so ähnlich.

    Hmm, gut 🙂 neues Ziel für die nächsten eineinhalb Stunden.

    Tja, schon ein wenig weitergekommen. Aber eigentlich sehe ich so etwas wie temp-programmierung als unnötig - ich mein', wozu brauchst du es in Applikationen? :p Oder es ist einfach lustig, sich in sowas auszukennen 😃

    0
  • O

    Hacker schrieb:

    Tja, schon ein wenig weitergekommen. Aber eigentlich sehe ich so etwas wie temp-programmierung als unnötig - ich mein', wozu brauchst du es in Applikationen? :p Oder es ist einfach lustig, sich in sowas auszukennen 😃

    Vielleicht sollte man sich vorher klar sein, warum man etwas tut, bevor man es tut. TMP in dieser Form hat vielleicht eine Handvoll Anwendungen. Hauptsächlich geht es darum, das es geht und das man damit unglaublich schlimme Bugs in einem Code verstecken kann. Dass das hier relativ sinnlos ist, wurde aber schon an anderer Stelle angemerkt.

    Die Frage ist: warum machst du es? Von dem was ich bislang so von dir gelesen habe, hab ich nicht den Eindruck, dass das etwas ist was a) in deinem Kerninteressenbereich liegt (im Gegensatz zu Pi) und b) dich in deiner Entwicklung als Programmierer weiter bringt.

    Was TMP angeht tüftel ich gerade etwas an einem intelligenteren Ansatz für expression templates rum. Es geht darum, Regeln zu definieren, um ein expression template in eine Normalform zu bringen. Das heißt, anstatt den Ausdruck 1:1 in sein (dummes) expression template umzuformen suche ich eine möglichst einfache Darstellung, die es zum einen dem Compiler einfach macht zu optimieren und zum anderen mir es einfacher macht, die richtigen Algorithmen zu wählen. Anwendung ist lineare Algebra, insbesondere elementweise Transformationen von Vektoren/Matrizen. Long Term überlege ich, ob es nicht sogar möglich ist, aus so einer Normalform einen Kern für GPU-Programmierung zu generieren. Aber wie gesagt: das ist hauptsächlich im Planungsstadium. Ich habe leider kaum Zeit, um das zu Programmieren.

    0
Anmelden zum Antworten