Komplizirtes C-Programm

Antoras

Mit GCC. Hat ohne Probleme geklappt.

Edit: Sry. Beim Kopieren scheint was schief gelaufen zu sein. Hab den Code oben mal editiert.

IOCCC?

Christoph

Die beiden magic strings kann man erstmal wegdefinieren. Außerdem kann man die ganzen ?:-Abfragen durch if-Abfragen ersetzen. Dann sieht das schonmal so aus:

#include <stdio.h>
#define MAGIC1 "@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+,/+#n+,/#;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# ){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c ;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# }'+}##(!!/"
#define MAGIC2 "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"

main(t,_,a)
char *a;
{
	if(t > 1) {
		if(t < 3)
			main(-79,-13,a+main(-87,1-_,main(-86, 0, a+1 )+a));
		if(t < _)
			main(t+1, _, a);
		if(main(-94, -27+t, a) && t == 2) {
			if(_ < 13)
				return main(2, _+1, "%s %d %d\n");
			else
				return 9;
		}
		else
			return 16;
	}
	else {
		if(t < 0) {
			if(t < -72)
				return main(_, t, MAGIC1);
			else {
				if(t < -50) {
					if(_ == *a)
						return putchar(a[31]);
					else
						return main(-65,_,a+1);
				}
				else
					return main((*a == '/') + t, _, a+1);
			}
		}
		else {
			if(0 < t)
				return main(2, 2, "%s");
			else
				return *a=='/' || main(0, main(-61, *a, MAGIC2), a+1);
		}
	}
}

Wenn man die Zweige jetzt abgeht, kann man sehen, dass main() niemals 0 zurückgibt. Die ganzen main()-Aufrufe innerhalb der if-Bedingungen bzw. in den return-Ausdrücken sind also nur dafür da, main() aufzurufen, aber nicht, um den Rückgabewert von main() auszuwerten. Die geschachtelten main-Aufrufe innerhalb der main-Aufrufe sind etwas trickreicher, aber vielleicht haben wir Glück und die Rückgabewerte sind dort auch unnötig (sie sind es tatsächlich). Außerdem kann man die if-Bedingungen über das t ganz außen etwas umsortieren:

#include <stdio.h>
#define MAGIC1 "@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+,/+#n+,/#;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# ){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c ;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# }'+}##(!!/"
#define MAGIC2 "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"

main(t, _, a)
char *a;
{
	if(t > 1) {
		if(t < 3)
			main(-79,-13,a+main(-87,1-_,main(-86, 0, a+1 )+a));
		if(t < _)
			main(t+1, _, a);
		main(-94, -27+t, a);
		if(t == 2) {
			if(_ < 13)
				main(2, _+1, "%s %d %d\n");
		}
	}
	else if(t < 0) {
			if(t < -72) {
				main(_, t, MAGIC1);
			}
			else {
				if(t < -50) {
					if(_ == *a)
						putchar(a[31]);
					else
						main(-65,_,a+1);
				}
				else
					main((*a == '/') + t, _, a+1);
			}
	}
	else if(t == 1)
		main(2, 2, "%s");
	else if(*a != '/')
		main(0, main(-61, *a, MAGIC2), a+1);
	return 0;
}

Was man jetzt kennen muss, ist spezielles C-Verhalten: Funktionsparameter ohne deklarierten Typ erhalten automatisch den Typ int. Die Variablen t und _ sind deswegen beide vom Typ int. Jetzt hat main() die Signatur main(int, int, char*), was natürlich ziemlich falsch ist. Normalerweise wäre es main(int, char*[]), der zweite Parameter wird also wahrscheinlich Müll enthalten. Der erste Parameter passt aber und enthält bei Programmstart deswegen die Zahl 1.

Das ist übrigens nicht vom C-Standard abgedeckt, soweit ich weiß. Die rekursiven Aufrufe der main-Funktion sind (AFAIK) auch nicht erlaubt laut Standard. Wenn man die if-Abfragen nachverfolgt kann man aber sehen, an welcher Stelle man das in eine eigene Funktion auslagern kann. Außerdem kann man wieder einige if-Bedingungen durch Nachverfolgen des Programmflusses auflösen. Man kann mit etwas Ausprobieren auch herausfinden, was die Variablen bedeuten. Warum ich sie "item" und "round" genannt habe, kann man vielleicht wegen Zeile 13 und 14 in der Ausgabe erahnen (es ist bisher auch nur eine Vermutung).

#include <stdio.h>
#define MAGIC1 "@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+,/+#n+,/#;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# ){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c ;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# }'+}##(!!/"
#define MAGIC2 "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"

void f(int item, int round, char* a);

int main() {
	f(2, 2, 0);
	return 0;
}

void f(int item, int round, char* a) {
	if(item != 0 && round != 0)
		printf("item: %d, round: %d\n", item, round);
	if(item > 1) {
		if(item < 3) {
			f(0,   0, MAGIC1); // "On the "
			f(1-round, 0, MAGIC1); // "first", "second", ...
			f(-13, 0, MAGIC1); // " day of Christmas my true love gave to me\n"
		}
		if(item < round) {
			f(item+1, round, a);
		}
		f(-27 + item, 0, MAGIC1);
		if(item == 2 && round < 13)
			f(2, round+1, 0);
	}
	else if(item > -51 && item < 0)
		f((a[0] == '/') + item, 0, a+1);
	else if(a[0] != '/') {
		int i = 0;
		while(a[0] != MAGIC2[i])
			++i;
		putchar(MAGIC2[i + 31]);
		f(0, 0, a+1);
	}
}

Man kann das ganze in weitere Funktionen aufteilen. Der Fall item == 2 ist offensichtlich ein Spezialfall. Das ergibt

#include <stdio.h>
#define MAGIC1 "@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+,/+#n+,/#;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# ){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c ;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# }'+}##(!!/"
#define MAGIC2 "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"

void f(int t, int round, char* a);
void g(int round);

int main() {
	g(2);
	return 0;
}

void f(int item, int round, char* a) {
	if(item > 2) {
		if(item < round) // i.e., if not in last item
			f(item+1, round, a);
		f(-27 + item, 0, MAGIC1);
	}
	else if(item > -51 && item < 0)
		f((a[0] == '/') + item, 0, a+1);
	else if(a[0] != '/') {
		int i = 0;
		while(a[0] != MAGIC2[i])
			++i;
		putchar(MAGIC2[i + 31]);
		f(0, 0, a+1);
	}
}

void g(int round) {
	f(0,       0, MAGIC1); // "On the "
	f(1-round, 0, MAGIC1); // "first", "second", ...
	f(-13,     0, MAGIC1); // " day of Christmas my true love gave to me\n"
	if(round > 2)
		f(3, round, 0);
	f(-25, 0, MAGIC1);
	// If we're not done, start the next round.
	if(round < 13)
		g(round+1);
}

Die Funktion g ruft sich selbst am Ende rekursiv auf. Das ist also in Wirklichkeit eine einfache for-Schleife:

#include <stdio.h>
#define MAGIC1 "@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+,/+#n+,/#;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# ){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c ;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# }'+}##(!!/"
#define MAGIC2 "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"

void f(int t, int round, char* a);

int main() {
	int round;
	for(round = 2; round < 14; ++round) {
		f(0,       0, MAGIC1); // "On the "
		f(1-round, 0, MAGIC1); // "first", "second", ...
		f(-13,     0, MAGIC1); // " day of Christmas my true love gave to me\n"
		if(round > 2)
			f(3, round, 0);
		f(-25, 0, MAGIC1);
	}
	return 0;
}

void f(int item, int round, char* a) {
	if(item > 2) {
		if(item < round) // i.e., if not in last item
			f(item+1, round, a);
		f(-27 + item, 0, MAGIC1);
	}
	else if(item > -51 && item < 0)
		f((a[0] == '/') + item, 0, a+1);
	else if(a[0] != '/') {
		int i = 0;
		while(a[0] != MAGIC2[i])
			++i;
		putchar(MAGIC2[i + 31]);
		f(0, 0, a+1);
	}
}

Und so weiter. Nach einigen Umbenennungen, Index-Verschiebungen etc. mehr kommt man irgendwann auf sowas wie das folgende:

#include <stdio.h>
#define STRING_TABLE "@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+,/+#n+,/#;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# ){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c ;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# }'+}##(!!/"
#define CHAR_TABLE "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"

void print_string(int index);
void decode_char(char x);

int main() {
	int round, i;
	for(round = 0; round < 12; ++round) {
		print_string(0);       // "On the "
		print_string(1+round); // "first", "second", ...
		print_string(13);      // " day of Christmas my true love gave to me\n"
		if(round > 0) {
			for(i = round; i >= 1; --i)
				print_string(25 - i);
		}
		print_string(25); // "a partridge in a pear tree.\n\n"
	}
	return 0;
}

void print_string(int index) {
	const char* a = STRING_TABLE;
	// STRING_TABLE contains '/' delimited substrings. Skip to the n-th
	// substring.
	for(; index != 0; ++a)
		if(*a == '/')
			--index;
	// Decode it.
	for(; *a != '/'; ++a)
		decode_char(*a);
}
void decode_char(char x) {
	int i = 0;
	while(x != CHAR_TABLE[i])
		++i;
	putchar(CHAR_TABLE[i + 31]);
}

Ab da sollte das Prinzip, nach dem der Code arbeitet, hoffentlich erkennbar sein.

edit:
Mir ist aufgefallen, dass ich einen entscheidenden Trick vielleicht doch besser kommentieren sollte: Wie genau schafft es der ursprüngliche Code eigentlich, den n-ten '/'-getrennten-Teilstring innerhalb von STRING_TABLE zu finden?

Ich nehme die vorletzte Version als Basis, weil die Stelle praktisch unverändert zum Originalcode ist. Alles außer der entscheidenden Stelle ist auskommentiert:

void f(int item, int round, char* a) {
	if(item > 2) {
		/ *... */
	}
	else if(item > -51 && item < 0)
		f((a[0] == '/') + item, 0, a+1);
	else if(a[0] != '/') {
		/* print something */
	}
}

In rekursiven Aufruf f((a[0] == '/') + item, 0, a+1) landet der Programmfluss wieder exakt an der gleichen Stelle. Das passiert so lange, bis item == 0 ist. Sobald das gilt, geht er in die Zeile mit /* print something */.

Der Trick hier ist nun, dass der dritte Parameter (a) in jedem Schritt um 1 erhöht wird. a zeigt zu Beginn immer auf den Anfang von MAGIC1, d.h. auf den Anfang von STRING_TABLE (das kann man leicht prüfen). Jedes mal, wenn a[0] == '/' ist, wird item um 1 erhöht, weil (a==a) zu 1 ausgewertet wird in einem int-Kontext.

Das ist der Grund, warum der Code den n-ten '/'-getrennten Teilstring finden kann.

SeppJ

Wow, Christoph . Mir war zwar auch klar, wie das Programm funktioniert, aber den Versuch das von Hand zu deobfuskieren habe ich nach 15 Minuten entnervt abgebrochen. Und nach den 15 Minuten war ich noch nicht sehr weit gekommen. Wie lange hast du dafür gebraucht?

Christoph

SeppJ schrieb:

Wow, Christoph . Mir war zwar auch klar, wie das Programm funktioniert, aber den Versuch das von Hand zu deobfuskieren habe ich nach 15 Minuten entnervt abgebrochen. Und nach den 15 Minuten war ich noch nicht sehr weit gekommen. Wie lange hast du dafür gebraucht?

Etwas länger, als ich erwartet hatte: Inklusive Schreiben des Beitrags circa 1,5 Stunden.

Edit: Viel Zeit gekostet hat mich der allererste Schritt, weil ich zu jedem ? erstmal das passende : suchen musste, und mir das nicht leicht fiel. Die Transformation ?: nach if müsste man eigentlich mal automatisieren.

C++ Forumbot

Dieser Thread wurde von Moderator/in rüdiger aus dem Forum Themen rund um den PC in das Forum ANSI C verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Antoras

Vielen Dank Christoph! Dass jemand das Programm so genau aufschlüsselt hätte ich jetzt nicht erwartet. Dein Beitrag ist echt beeindruckend. Hab selbst schon versucht den Code ein wenig zu entschlüsseln, aber nachdem das Auflösen der ternären Operatoren schon ewig gedauert hat, hab ich aufgegeben und mich lieber hier an das Forum gewandt.
Ich hab deinen Beitrag bisher nur überflogen und versucht das Wichtigste zu verstehen, werde das aber, sobald ich die Zeit dazu finde, alles Schritt für Schritt noch genau durchgehen um zu verstehen wie das genau funktioniert. Finde das hochinteressant.
Was mir noch nicht ganz klar ist: Wie genau kommt man von den Zeichen der beiden Strings auf die Ausgabe? Ich meine die Aufteilung in die Unterstrings verstanden zu haben, aber die Bedeutung der Zeichen in den Strings ist mir noch unklar.

asasas schrieb:

IOCCC?

Weiß nicht ob der Code dort eingereicht wurde. Ich hab den auf irgendeiner Seite gefunden, weiß aber nicht mehr auf welcher.

Christoph

Antoras schrieb:

Was mir noch nicht ganz klar ist: Wie genau kommt man von den Zeichen der beiden Strings auf die Ausgabe? Ich meine die Aufteilung in die Unterstrings verstanden zu haben, aber die Bedeutung der Zeichen in den Strings ist mir noch unklar.

Den ersten Schritt hast du schon erkannt: Der lange String STRING_TABLE wird in Teilstrings geplittet. Der Slash '/' ist dabei der Teilstring-Trenner. Die Teilstrings sind allerdings kodiert und müssen vor der Ausgabe dekodiert werden. Das Dekodieren ist eine reine Zeichen-Substition, die von der Funktion decode_char ausgeführt wird.

Antoras

Ok, dann werd ich mich mal dranmachen das zu verstehen. Bin ich bestimmt einige Zeit beschäftigt aber es dürfte sich auch lohnen so ein - auf den ersten Blick sinnloses - Programm mal verstanden zu haben...

Wenn es kompliziert ist, dann kann man es töten, eh ich meine debuggen.