Hello broken keyboardがすごかったので一年半ぶりに日記を書いてみる。
というか一年半も経つとさすがにはてな記法とかほとんど忘れてますね……それはさておき。
C
shinhさんの回答が凄すぎてよくわからない。
((int(*)())(t*t*(t*t+a*a)*t*t*(t*t+a*a)*(m+a*a*a*t*t)+**(int**)(((t+t*(t+a)*a*t*t)*(t*t+a*a*(t+a*a))+a)*((t+t*a*t*t*t)*(t+t*t*t*a+a*a*a*a)+m)*t)))
の部分は、計算すると
((int(*)())(294736+**(int**)134513438)
ということになるようです。134513438といえば関数やグローバル変数のアドレスに割と近いですが、そこにあるポインタの指すポインタの指す値が何を意味しているのか、それに294736を足すと何が起こるのかは謎です。(2012/9/15追記)
それに比べて私の回答はとてもわかりやすいですね。やっていることは単純で、
- まずは読み書き実行できる十分な量のメモリを確保する
- 「文字列先頭のポインタを1つ受け取ってその文字列を13bytes出力する機械語」をそのメモリに用意する
- メモリ上の別の場所に"Hello, world!"相当の13bytesのデータを用意する
- 2で用意した機械語に3の先頭のポインタを食わせる
というだけです。
まず1については、最初はグローバル変数にがしがし値を書き込んで実行しようと思ったのですが、書き込み可能な変数の領域は実行不可能という事実に気付き断念せざるを得ませんでした。const領域は実行可能なのですが、書き込みが不可能なのでこれでは意味がありません。
どうにかwritableでexecutableな領域を確保できないかと思って見つけたのがmmap()です。まあmalloc()の中でも使われてる割とメジャーな関数のようですが、pが入っている以外は名前が素晴らしいですね。引数が6つとやけに多いのですが、カンマに貴重な1種類を費やすわけにはいかないので、スタック領域を自力で書き換えて無理矢理引数を渡しています。
次に2について、今回用意したのは以下の処理です。
popl %ecx popl %ecx movl $13, %edx movl $4, %eax movl $1, %ebx int $0x80
文字列の(低水準)出力は、「eaxレジスタに4、ebxレジスタに1、ecxレジスタに文字列先頭へのポインタ、edxレジスタに文字列長を格納した状態で、int $0x80によるソフトウェア割り込みを行う」ことでなされるようです。なお、上記のコードはスタックの退避などを一切行っておらず、スタックトップにあった次の命令へのアドレスを捨ててしまっているうえretすら行っていないのでいつかはSegmentation faultで落ちますが、既に目的の出力は得られているため問題ありません(実際はHello, world!の領域なども機械語とみなし実行しているので具体的にどうなるかは予想がつきませんが)。
3と4については文字通りなので説明不要でしょう。Hello, world!を引き算と掛け算で作るのが大変と言えば大変でした。
謎の関数nan()
さて、コンテスト中に'm','a','i','n'の文字からなる便利な関数が何かないか頑張って探したところ、nan()という関数を見つけました。
nan 関数は文字列を double 型の NaN (非数) に変換します．
http://www.c-tipsref.com/reference/math/nan.html
説明を読んでもいまいちよくわかりませんが、
main(){printf("%d",nan("123"));}
このコードを実行すると
123
と表示されます。これはすごい。要するに、atoi()と同じことを1byte短く実行できるわけです。
ただ問題点もありまして、atoi()と比べると
- 引数の省略ができない
- 数としての扱いはあくまでもNaNなので、int型にキャストすると0や0x80000000などの値となる
といった欠点もあります。使いどころは難しそうですが、可能性を感じさせる関数です。
おまけ
せっかくなのでその他のコードも晒しておきます。
初めて16切った記念。printfではなくputcなのでした。
main(m,a,i,n,p,u,t){u--;u--;u--;u--;u--;u--;u--;u--;u--;u--;u--;putc(putc(putc(putc(putc(-u-u-u-u-u-u,n-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-p-(p-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-n-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-t-n)-m-m-m-m-m-m-(m-u-u-u-u-u-u-u-u-u-u-u-u-u-u-u-u))-u-u-u-m-m-m-m-m-m-m)-u-m-m-m-m-m))-(-m-m-m));putc(putc(putc(putc(putc(putc(putc(-u-u-u-u-m-m-m-m)-(-u))-u-u-u-u-u-u-(u-m-m-m))-(-m-m-m-m-u))-(-m-m-m))-m-m-m-m-m-m)-(-u-m-m-m-m));putc(-u-u-u-m-m-m);}初めて15切った記念。"&"を削って気合で頑張るコード。書いたコードそのものによってtとグローバル変数の位置の差が変わるため一番大変でした。
ra;ri;np;f;pp;ia;im;ni;a;p(){a++;a++;a++;a++;}m(){p(p(p(p(p(p(p(a++)))))));}r(){m(m(m(m(m(m(a++))))));a++;a++;a++;}na(){ra++;ra++;ri++;f++;f++;f++;pp++;pp++;pp++;ia++;ia++;ia++;im++;}n(){np++;im++;im++;r(na(ni++));}i(){n(n(n(n(n(n(n(n(na(ri++)))))))));ri++;f++;f++;p(p(p(p(a++))));a++;}nn(){i(i(i(i(pp++))));pp++;pp++;ni++;f++;f++;f++;}t(){ra++;ra++;ra++;ra++;ra++;ra++;ra++;}main(){nn();printf(t+a);t(t(t(t(ra++))));t(printf(t+a));printf(t+a);printf(t+a);ra++;ra++;ra++;p(printf(t+a));p(printf(t+a));p(printf(t+a));p(printf(t+a));printf(t+a);pp++;pp++;pp++;p(printf(t+a));p(printf(t+a));p(printf(t+a));printf(t+a);}
Perl
Perlはshinh先生のPerlで記号ゴルフを参考に、文字列どうしの論理演算でHello, world!を作ってprintするのが基本方針なのですが、文字種を削るとそれらの文字間の論理演算だけではprintやHello, world!をうまく作れないという問題が生じます。
ということで、"評価するとHello, world!になるPerlのコード"を論理演算を用いて作り、s///eeで二段evalすることで文字種を減らしています。
(一度に全部作ろうとすると長くなってしまうので、実際にはまず" world!"、"Hello,"の順に作り、最後に"print"を作ってs///eeeすることで出力しています)
なお、文字列を括るのにわざわざバックスラッシュのエスケープが必要なダブルクォーテーションを使っているのは、文字コードの関係上シングルクォーテーションでは論理和演算子"|"が作れず、二段階目でうまく任意の文字を作成できなかったためです(私が見落としているだけで、何かうまい方法があるかもしれません)。
よく考えたら"He"とか" "みたいに直に作れる文字は直に作ったらいいよねということで731bytesまで縮みました。それでもまだ長いですが、これ以上縮める気力はありません；
問題の公開当初は「こんなの二週間じゃ足りない……」とか思ってましたが、もし期間が一ヶ月とかだとそれはそれで大変そうだったのでこれぐらいで丁度よかったのかもしれません。
素晴らしい問題を作ったshinhさんに感謝です。皆さんお疲れ様でした。
2012/9/15追記
shinhさんによる解説が来てました。
アドレス134513438には__libc_start_main@pltという関数のジャンプ先アドレスが書いてあり、2回デリファレンスすることでlibc内の関数のアドレスを得られ、294736のオフセットを足してやることでputcharの実質にアクセスしているということです。なるほど……
このような解説を拝見するにつけ、私にコンパイラやリンカといった部分についての知識が欠けていることを実感しますね……。ゴルフのための付け焼き刃的な知識しか持っていないので、shinhさん等にはかなわないです。
あと、kikさんによる11.328ポイントの回答が来ていました。関数ポインタやポインタのグローバル変数との加算による暗黙型変換によって"int"の"t"を削除しているのに加え、デリファレンス回数が2回から1回に減っているようです。前者はともかく、後者はよくわかりません。
*(ma+a+n*n+(a*a+n)*(n*n*a*a+n+a)*(n+a*a+n*n*a*a*(n*a*a+m)*(m+n*n*a*a*a)))
の部分は、計算すると
*((int*)33629724)
となるようです。33629724(やけに数字が小さいですね)というのはどこのアドレスなのでしょうか。オフセットが同じことを考えるとおそらく__libc_start_main@pltのジャンプ先だとは思うのですが、そのアドレスが33629724で取れるという原理がよくわかりません。わからないことだらけです。
さらに追記
上の説明は実は全く間違っていて、実際はint*に加算するので33629724の値が4倍されます。
詳しくはコメントを参照ください。
