Best abuse of the rules

ルールの最高の悪用

Line wrap

Highlight

#include <stdio.h>
#define k *(int*)
#define a if(
#define c ad()
#define i else
#define p while(
#define x *(char*)
#define b ==
#define V =calloc(1,99999)
#define f ()
#define J return
#define l ae(
#define n e)
#define u d!=
#define F int 
#define y (j)
#define r m=
#define t +4
F d,z,C,h,P,K,ac,q,G,v,Q,R,D,L,W,M;
E(n{
x D++=e;
}
o f{
a L){
h=x L++;
a h b 2){
L=0;
h=W;
}
}
i h=fgetc(Q);
}
X f{
J isalnum(h)|h b 95;
}
Y f{
a h b 92){
o f;
a h b 110)h=10;
}
}
c{
F e,j,m;
p isspace(h)|h b 35){
a h b 35){
o f;
c;
a d b 536){
c;
E(32);
k d=1;
k(d t)=D;
}
p h!=10){
E(h);
o f;
}
E(h);
E(2);
}
o f;
}
C=0;
d=h;
a X f){
E(32);
M=D;
p X f){
E(h);
o f;
}
a isdigit(d)){
z=strtol(M,0,0);
d=2;
}
i{
x D=32;
d=strstr(R,M-1)-R;
x D=0;
d=d*8+256;
a d>536){
d=P+d;
a k d b 1){
L=k(d t);
W=h;
o f;
c;
}
}
}
}
i{
o f;
a d b 39){
d=2;
Y f;
z=h;
o f;
o f;
}
i a d b 47&h b 42){
o f;
p h){
p h!=42)o f;
o f;
a h b 47)h=0;
}
o f;
c;
}
i{
e="++#m--%am*@R<^1c/@%[_[H3c%@%[_[H3c+@.B#d-@%:_^BKd<<Z/03e>>`/03e<=0f>=/f<@.f>@1f==&g!='g&&k||#l&@.BCh^@.BSi|@.B+j~@/%Yd!@&d*@b";
p j=x e++){
r x e++;
z=0;
p(C=x e++-98)<0)z=z*64+C+64;
a j b d&(m b h|m b 64)){
a m b h){
o f;
d=1;
}
break;
}
}
}
}
}
l g){
p g&&g!=-1){
x q++=g;
g=g>>8;
}
}
A(n{
F g;
p n{
g=k e;
k e=q-e-4;
e=g;
}
}
s(g,n{
l g);
k q=e;
e=q;
q=q t;
J e;
}
H(n{
s(184,n;
}
B(n{
J s(233,n;
}
S(j,n{
l 1032325);
J s(132+j,n;
}
Z(n{
l 49465);
H(0);
l 15);
l e+144);
l 192);
}
N(j,n{
l j+131);
s((e<512)<<7|5,n;
}
T y{
F g,e,m,aa;
g=1;
a d b 34){
H(v);
p h!=34){
Y f;
x v++=h;
o f;
}
x v=0;
v=v t&-4;
o f;
c;
}
i{
aa=C;
r z;
e=d;
c;
a e b 2){
H(m);
}
i a aa b 2){
T(0);
s(185,0);
a e b 33)Z(m);
i l m);
}
i a e b 40){
w f;
c;
}
i a e b 42){
c;
e=d;
c;
c;
a d b 42){
c;
c;
c;
c;
e=0;
}
c;
T(0);
a d b 61){
c;
l 80);
w f;
l 89);
l 392+(e b 256));
}
i a n{
a e b 256)l 139);
i l 48655);
q++;
}
}
i a e b 38){
N(10,k d);
c;
}
i{
g=k e;
a!g)g=dlsym(0,M);
a d b 61&j){
c;
w f;
N(6,g);
}
i a u 40){
N(8,g);
a C b 11){
N(0,g);
l z);
c;
}
}
}
}
a d b 40){
a g b 1)l 80);
r s(60545,0);
c;
j=0;
p u 41){
w f;
s(2393225,j);
a d b 44)c;
j=j t;
}
k r j;
c;
a!g){
e=e t;
k e=s(232,k n;
}
i a g b 1){
s(2397439,j);
j=j t;
}
i{
s(232,g-q-5);
}
a j)s(50305,j);
}
}
O y{
F e,g,m;
a j--b 1)T(1);
i{
O y;
r 0;
p j b C){
g=d;
e=z;
c;
a j>8){
r S(e,m);
O y;
}
i{
l 80);
O y;
l 89);
a j b 4|j b 5){
Z(n;
}
i{
l n;
a g b 37)l 146);
}
}
}
a m&&j>8){
r S(e,m);
H(e^1);
B(5);
A(m);
H(n;
}
}
}
w f{
O(11);
}
U f{
w f;
J S(0,0);
}
I y{
F m,g,e;
a d b 288){
c;
c;
r U f;
c;
I y;
a d b 312){
c;
g=B(0);
A(m);
I y;
A(g);
}
i{
A(m);
}
}
i a d b 352|d b 504){
e=d;
c;
c;
a e b 352){
g=q;
r U f;
}
i{
a u 59)w f;
c;
g=q;
r 0;
a u 59)r U f;
c;
a u 41){
e=B(0);
w f;
B(g-q-5);
A(n;
g=e t;
}
}
c;
I(&m);
B(g-q-5);
A(m);
}
i a d b 123){
c;
ab(1);
p u 125)I y;
c;
}
i{
a d b 448){
c;
a u 59)w f;
K=B(K);
}
i a d b 400){
c;
k j=B(k j);
}
i a u 59)w f;
c;
}
}
ab y{
F m;
p d b 256|u-1&!j){
a d b 256){
c;
p u 59){
a j){
G=G t;
k d=-G;
}
i{
k d=v;
v=v t;
}
c;
a d b 44)c;
}
c;
}
i{
A(k(d t));
k d=q;
c;
c;
r 8;
p u 41){
k d=m;
r m t;
c;
a d b 44)c;
}
c;
K=G=0;
l 15042901);
r s(60545,0);
I(0);
A(K);
l 50121);
k r G;
}
}
}
main(g,n{
Q=stdin;
a g-->1){
e=e t;
Q=fopen(k e,"r");
}
D=strcpy(R V," int if else while break return for define main ")+48;
v V;
q=ac V;
P V;
o f;
c;
ab(0);
J(*(int(*)f)k(P+592))(g,n;
}

引用元：https://www.ioccc.org/2001/bellard.c

審査員・作者による説明：https://github.com/ioccc-src/winner/blob/main/2001/bellard.hint

動作

セルフホスト可能なC言語のサブセットのコンパイラ。次は、添付されているbellard.otccex.cから一部だけ抜粋したコードfib.cを動かす例。

$ gcc -m32 -rdynamic bellard.c -o bellard -ldl

$ cat fib.c
fib(n) {
    if (n <= 2)
        return 1;
    else
        return fib(n-1) + fib(n-2);
}
main(argc, argv) {
    int n;
    n = atoi(*(int *)(argv + 4));
    printf("fib(%d) = %d\n", n, fib(n));
    return 0;
}

$ ./bellard fib.c 10
fib(10) = 55

./bellard fib.c 10はfib.cをコンパイルして実行している。見かけ上は、C言語インタプリタのようになる。セルフホストは最後に示す。

解説

C言語のソースコードを読んで機械語（x86）に変換し、その機械語を実行する。ただし、実行可能ファイルを出力するのではなく、メモリ内に命令列を構築し、その中のmain関数をcallして実行する。たとえば./bellard foo.cと実行すると、foo.cをメモリ内にコンパイルし、その結果を実行するので、見かけの挙動はC言語インタプリタのようになっている。実行ファイルにするにはELFフォーマットを作る必要があるので、コードサイズ制限に合わなかったか。

コード形状による難読化はないが、サイズ制限に収まっているだけでもすごい。

x86しかサポートしていないので、-m32が必要。値とポインタがともに4バイトであることを強く仮定したコードになっているので、-m32なしで動かすのはとても大変だと思う。また、calloc関数で得たメモリに機械語を構築してcallするが、現代ではこのようなメモリは実行フラグが立っていない（実行保護を参照のこと）ので、mmapでメモリ確保するようにした。

作者自身が解説サイトを作っているので興味あれば参照されたい。最近、難読化されていないバージョンも公開された。なお作者（Fabrice Bellard）はその後、この作品を元にtccを作っている。

残念ながら、現代の環境ではfibまでは動かせたが、bellard.otccex.cを完全動作させることができなかった。詳しくは調べていないが、関数ポインタが動いていないような気がする。腕に自信のあるバイナリアンに解析してもらいたい。

当時のOS環境であるDebian 2.2 (potato)をQEMUでセットアップしたところ、bellard.otccex.cだけでなくセルフホストまで動作確認できた。

./bellard bellard.otccex.c 10はbellard.otccex.cをコンパイルして動かしているだけ。 ./bellard bellard.c bellard.otccex.c 10はbellard.cをコンパイルしてコンパイラを作り、その新しいコンパイラでbellard.otccex.cをコンパイルして実行する。 ./bellard bellard.c bellard.c bellard.otccex.c 10はコンパイラのコンパイルをもう一段階増やしている。

パッチ

--- bellard.c
+++ bellard.c
@@ -1,4 +1,6 @@
 #include <stdio.h>
+#include <stdlib.h>
+#include <sys/mman.h>
 #define k *(int*)
 #define a if(
 #define c ad()
@@ -6,7 +8,7 @@
 #define p while(
 #define x *(char*)
 #define b ==
-#define V =calloc(1,99999)
+#define V =mmap(NULL, 99999/16*16+16, PROT_EXEC | PROT_WRITE | PROT_READ, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0)
 #define f ()
 #define J return
 #define l ae(

パッチをダウンロード