Hello broken keyboard
http://golf.shinh.org/p.rb?Hello+broken+keyboard
ゴルフなんだけど、文字数じゃなくて文字種を減らす、という問題。 Hello, world! だとあまり面白くもないかな…と予想してたんだけど、予想に反してかなり楽しい問題になったようだった。
C のこの解答が謎だと言われたりしてるようなので適当に説明。
http://golf.shinh.org/reveal.rb?Hello+broken+keyboard/shinh_1346768972&c
putchar とか printf とか puts 文字種増えすぎるので使ったら負けと思ってて、というわけで putchar のアドレスをそのまま使って、 ( ( int ) ( * ) ( int ) ) にキャストして使ってやればいいだろう、ってのが基本的なアイデア。ただし、 putchar のアドレスってやつは libc 内なので address randomization で毎回変わるので、なんとかしないといけない。
ローダの仕組みとかを知ってると libc のアドレス得る方法は割と普通に思いつくと思うんですが、プログラムから shared object の関数を呼ぶ時は PLT ってやつを経由してまして、 PLT ってのは puts が 10 個ある時に 10 回 relocate すると遅いから、 puts@plt ってとこにいったん飛んで、そこから puts に飛ぶことによってシンボル1つにつき1回の relocate ですむようにしよう、という工夫。
08048320 <puts@plt>: 8048320: ff 25 c0 96 04 08 jmp *0x80496c0 8048326: 68 10 00 00 00 push $0x10 804832b: e9 c0 ff ff ff jmp 80482f0 <_init+0x38> 080483e4 <main>: 80483e4: 55 push %ebp 80483e5: 89 e5 mov %esp,%ebp 80483e7: 83 e4 f0 and $0xfffffff0,%esp 80483ea: 83 ec 10 sub $0x10,%esp 80483ed: c7 04 24 d4 84 04 08 movl $0x80484d4,(%esp) 80483f4: e8 27 ff ff ff call 8048320 <puts@plt> 80483f9: c9 leave 80483fa: c3 ret
の puts@plt がそれ。 GDB で見てやると
(gdb) p (void*)**(int**)(0x8048320+2) $6 = (void *) 0x8048326
とのこと。 objdump とかよくする人は、あれこのアドレスの雰囲気は libc 内じゃなくねーと思うと思うんですが、その通りで、
(gdb) start ... (gdb) n ... (gdb) p (void*)**(int**)(0x8048320+2) $7 = (void *) 0x4c07e130
などと、一度プログラムを走らせると本当の puts のアドレスに変わります。つまり遅延ロードされてて、初回呼び出し時に relocate をする感じの仕組みになっています。詳細は PLT GOT あたりでぐぐってください。
あとは maint 以外の文字をなるべく使ってない関数を探して、そこからのオフセットで putchar にアクセスすれば OK 。具体的には
A+**(int**)(2+(int)mmap)
などとする。 mmap のアドレスから 2 足したところが jmp の参照先、間接 jmp なんで、2回デリファレンスしてやると libc 内の mmap のアドレスになるんで、そこからのオフセットを A で指定してやる。
libc のシンボルしか見てなかったので、 libm に入ってた nan は見落としていて、この段階で 13 種。
こういうシンボルとしては mmap やら atoi 、 tmpnam などがあるわけですが、そのへんで一種類増えるの気にいらないなぁ、ということで眺めてやると __libc_start_main@plt っていう関数は常にあるっぽくて、かつ main が呼ばれた段階で既に呼ばれてて遅延ロード完了してやるので、この固定アドレスから参照してやれば OK 、といのが 12 種。
11種は int があるせいで t で一種増えちゃってるので、それを除去した形。関数へのキャストで ( ( * ) ( ) ) なんて書けないので、 int は取りのぞけないかな…と思ってたんですが、 (*mm)(); などとして定義した関数ポインタに対して加算 (void* への演算と同じく非標準なんでしょうけど) してやれば関数ポインタを int 無しで得られる、と。
あとは __libc_start_main のアドレス作るのに手間かかるので、 nan のアドレスを使えば種類は減らないけどいいんじゃないかな…と思ってたんですが、 int* に対して加算することになるので4倍かかっちゃってきついのかな…と思います。たぶん。
最後に、 m=1 n=2 a=3 の前提で、 'H' を出力するための 72 を足し算かけ算で作る最小の式はなんでしょうか…っていう問題があるんですが、これはもろに DP な感じ。 __libc_start_main とかの 0x080483a0 とかは O(n*2) かかる DP なので、この領域までは計算できないわけですが、適当に素因数分解してそれぞれの部分の最短の式を使う感じでやってました。このへんで本当に最短かっていうとたぶん最短じゃない、ってのが少し気持ち悪い感じではあります…
あとは他の言語だと perl と befunge がすごそうなのでちゃんと確認しないとですね…あと z80 とか 数字しばりプログラミング した時のコードをそのまま提出しただけだったんですが、たった3種類でいけるもんなんですね… ADD A,IMM と HALT と CALL だけ、ですかね?
