_ まあとりあえずは
issigned を…
(00:44)
_ 本物の Perl golfer が
1st tybalt89 56 Perl 10,000 (v2)
2nd kinaba 67 Perl 8,358 (v11)
来たみたいですね…
(02:20)
_ 63B を考える会
なんせまずオーバーラップのしかたからしてたぶん違う。
一番短いアレは
BITS 32
org 0
db 0x7f, "ELF" ; e_ident
phdr: dd 1 ; p_type
dd 0 ; p_offset
dd 0 ; p_vaddr
dw 2 ; e_type ; p_paddr
dw 3 ; e_machine
dd filesize ; e_version ; p_filesz
dd filesize ; e_entry ; p_memsz
dd phdr ; e_phoff ; p_flags
dd 0 ; e_shoff ; p_align
dd 0 ; e_flags
dw 0 ; e_shsize
dw 32 ; e_phentsize
dw 1 ; e_phnum
dw 0,0,0
filesize equ $ - $$
これが原形。
これはすごい綺麗に重なってるけど、
e_phoff と p_flags がうまくいかんのだよね。
パーミッションがあわん
(05:18)
_ フッシギー
i@u ~/wrk/binhacks> nasm tiny.asm
i@u ~/wrk/binhacks> la tiny
-rwxr-xr-x 1 i 64 2006-11-10 05:22 tiny*
i@u ~/wrk/binhacks> ./tiny
zsh: no such file or directory: ./tiny
(05:22)
_ でまあ
これより少なくなると、
もうなんか無いんだよなぁ…
e_shoff と p_type 重ねるのがどう見ても限界というか
(05:22)
_ 遠くおよばないー
i@u ~/wrk/binhacks> ./hello73
Hello world
i@u ~/wrk/binhacks> la hello73
-rwxr-xr-x 1 i 70 2006-11-10 05:47 hello73*
(05:48)
_ まだまだ
愛が足りないですね…
i@u ~/wrk/binhacks> nasm hello73.asm
i@u ~/wrk/binhacks> la hello73
-rwxr-xr-x 1 i 65 2006-11-10 07:16 hello73*
i@u ~/wrk/binhacks> ./hello73
Hello world
(07:16)
_ うーん
繰り返しになるけどそもそも現行方針は64Bが打ち止めなわけで。
- e_phentsize < 32 がありえる
- p_flags か e_phoff をなんかうまくごまかせる
- e_type と p_vaddr がオーバーラップするなにか(できる感じしないけど)
(07:23)
_ どっか
ヘッダの意味を勘違いしてるみたいだ。
有力候補は p_offset とか p_filesz 。
図をぱくらせてもらって考えてた。
s はでかい値だとダメで上の2つは 0 じゃないとダメだったはず…
00 04 08 0C 10 14 18 1C 20 24 28 2C 30
7f 45 4c 46 ** ** ** ** ** ** ** ** ** ** ** ** 02 00 03 00 ** ** ** ** SS SS SS SS PP 00 00 00 ** ** ** ** ** ** ** ** ** ** 20 00 01 00 ** ** ** ** ** **
01 00 00 00 oo oo oo oo VV VV VV VV ** ** ** ** ss ss 00 00 mm mm mm mm *7 ** ** ** ** ** ** **
00 04 08 0C 10 14 18 1C 20 24 28 2C 30
7f 45 4c 46 ** ** ** ** ** ** ** ** ** ** ** ** 02 00 03 00 ** ** ** ** SS SS SS SS PP 00 00 00 ** ** ** ** ** ** ** ** ** ** 20 00 01 00 ** ** ** ** ** **
01 00 00 00 oo oo oo oo VV VV VV VV ** ** ** ** ss ss 00 00 mm mm mm mm *7 ** ** ** ** ** ** **
ここから 2B は同じくダメ。
00 04 08 0C 10 14 18 1C 20 24 28 2C 30
7f 45 4c 46 ** ** ** ** ** ** ** ** ** ** ** ** 02 00 03 00 ** ** ** ** SS SS SS SS PP 00 00 00 ** ** ** ** ** ** ** ** ** ** 20 00 01 00 ** ** ** ** ** **
01 00 00 00 oo oo oo oo VV VV VV VV ** ** ** ** ss ss 00 00 mm mm mm mm *7 ** ** ** ** ** ** **
00 04 08 0C 10 14 18 1C 20 24 28 2C 30
7f 45 4c 46 ** ** ** ** ** ** ** ** ** ** ** ** 02 00 03 00 ** ** ** ** SS SS SS SS PP 00 00 00 ** ** ** ** ** ** ** ** ** ** 20 00 01 00 ** ** ** ** ** **
01 00 00 00 oo oo oo oo VV VV VV VV ** ** ** ** ss ss 00 00 mm mm mm mm *7 ** ** ** ** ** ** **
次の 1B もそう。あ、 p_offset もだめな気が。
00 04 08 0C 10 14 18 1C 20 24 28 2C 30
7f 45 4c 46 ** ** ** ** ** ** ** ** ** ** ** ** 02 00 03 00 ** ** ** ** SS SS SS SS PP 00 00 00 ** ** ** ** ** ** ** ** ** ** 20 00 01 00 ** ** ** ** ** **
01 00 00 00 oo oo oo oo VV VV VV VV ** ** ** ** ss ss 00 00 mm mm mm mm *7 ** ** ** ** ** ** **
次の 2B もそう。
00 04 08 0C 10 14 18 1C 20 24 28 2C 30
7f 45 4c 46 ** ** ** ** ** ** ** ** ** ** ** ** 02 00 03 00 ** ** ** ** SS SS SS SS PP 00 00 00 ** ** ** ** ** ** ** ** ** ** 20 00 01 00 ** ** ** ** ** **
01 00 00 00 oo oo oo oo VV VV VV VV ** ** ** ** ss ss 00 00 mm mm mm mm *7 ** ** ** ** ** ** **
これしばらく続く。
00 04 08 0C 10 14 18 1C 20 24 28 2C 30
7f 45 4c 46 ** ** ** ** ** ** ** ** ** ** ** ** 02 00 03 00 ** ** ** ** SS SS SS SS PP 00 00 00 ** ** ** ** ** ** ** ** ** ** 20 00 01 00 ** ** ** ** ** **
01 00 00 00 oo oo oo oo VV VV VV VV ** ** ** ** ss ss 00 00 mm mm mm mm *7 ** ** ** ** ** ** **
これもちょいと続くよ
00 04 08 0C 10 14 18 1C 20 24 28 2C 30
7f 45 4c 46 ** ** ** ** ** ** ** ** ** ** ** ** 02 00 03 00 ** ** ** ** SS SS SS SS PP 00 00 00 ** ** ** ** ** ** ** ** ** ** 20 00 01 00 ** ** ** ** ** **
01 00 00 00 oo oo oo oo VV VV VV VV ** ** ** ** ss ss 00 00 mm mm mm mm *7 ** ** ** ** ** ** **
00 04 08 0C 10 14 18 1C 20 24 28 2C 30
7f 45 4c 46 ** ** ** ** ** ** ** ** ** ** ** ** 02 00 03 00 ** ** ** ** SS SS SS SS PP 00 00 00 ** ** ** ** ** ** ** ** ** ** 20 00 01 00 ** ** ** ** ** **
01 00 00 00 oo oo oo oo VV VV VV VV ** ** ** ** ss ss 00 00 mm mm mm mm *7 ** ** ** ** ** ** **
00 04 08 0C 10 14 18 1C 20 24 28 2C 30
7f 45 4c 46 ** ** ** ** ** ** ** ** ** ** ** ** 02 00 03 00 ** ** ** ** SS SS SS SS PP 00 00 00 ** ** ** ** ** ** ** ** ** ** 20 00 01 00 ** ** ** ** ** **
01 00 00 00 oo oo oo oo VV VV VV VV ** ** ** ** ss ss 00 00 mm mm mm mm *7 ** ** ** ** ** ** **
しばらく続いて、
00 04 08 0C 10 14 18 1C 20 24 28 2C 30
7f 45 4c 46 ** ** ** ** ** ** ** ** ** ** ** ** 02 00 03 00 ** ** ** ** SS SS SS SS PP 00 00 00 ** ** ** ** ** ** ** ** ** ** 20 00 01 00 ** ** ** ** ** **
01 00 00 00 oo oo oo oo VV VV VV VV ** ** ** ** ss ss 00 00 mm mm mm mm *7 ** ** ** ** ** ** **
これも続いて、結局、
00 04 08 0C 10 14 18 1C 20 24 28 2C 30
7f 45 4c 46 ** ** ** ** ** ** ** ** ** ** ** ** 02 00 03 00 ** ** ** ** SS SS SS SS PP 00 00 00 ** ** ** ** ** ** ** ** ** ** 20 00 01 00 ** ** ** ** ** **
01 00 00 00 oo oo oo oo VV VV VV VV ** ** ** ** ss ss 00 00 mm mm mm mm *7 ** ** ** ** ** ** **
これじゃあ64Bが限界。
まぁどっかに勘違いがあるなり
(15:01)
_ とりあえず
ヘッダの値域の確認…とかする前に。
(16:32)
_ LFSって！
http://d.hatena.ne.jp/kikx/20061110#1163148475
どこが普通やねんと…！
にしてもどこで止まってるんだろう。
kernel オプションとかだとすると
p_flags 以外で止まるか止まらんか差があるってのもアレだなぁ。
strace してやるとだいたいどこで止まったかは
予想がつくものですが。
うちだと
- ヘッダが全部ファイルに無い
- IO error
- p_flagsが不適切(ちなみに4はいらなかったような3でいいというか)
- SEGV
- 指定したファイルサイズがでかすぎたり小さかったり
- killed とか SEGV とか
- その他のたいてい
- executable format がどうこう
とかだった気がします。
いや全然覚えてないぞ…！
なんにせよそのサイズで
ヘッダに命令埋めつくしたのはすごいです…
(17:58)
_ うちでもー
76B はどこでも動くんだけど。
i@u ~> uname -a
Linux u 2.6.17-10-generic #2 SMP Fri Oct 13 18:45:35 UTC 2006 i686 GNU/Linux
これが作業環境。
i@u3 ~/t> uname -a
Linux u3 2.6.7-1-386 #1 Thu Jul 8 05:08:04 EDT 2004 i686 GNU/Linux
i@u3 ~/t> la hello73
-rwxr-xr-x 1 i 65 2006-11-10 18:01 hello73*
i@u3 ~/t> ./hello73
zsh: killed ./hello73
ぎゃー 65B のヤツが動かない。
65B のヤツは p_filesz と p_memsz に侵食してるから、
そこの制約が厳しいんだろうなぁ。
i@u3 ~/t> la ./hello72
-rwxr-xr-x 1 i 72 2006-11-10 18:00 ./hello72*
i@u3 ~/t> ./hello72
Hello world
侵食してない 72B はオッケ。
i@un ~/t> uname -a
Linux un 2.6.15.4 #1 SMP Mon Feb 27 17:28:54 JST 2006 i686 i686 i386 GNU/Linux
i@un ~/t> ./hello73
Hello world
i@un ~/t> ./hello72
Hello world
どっちもオケ。しかし hello73 が 65B という罠がひどい。
cf.sf.jp にて。
shinh@cf-x86-linux:~/t$ uname -a
Linux cf-x86-linux 2.4.29-blade #1 2005年 3月 22日 火曜日 18:17:12 JST i686 GNU/Linux
shinh@cf-x86-linux:~/t$ ./hello73
Hello world
shinh@cf-x86-linux:~/t$ ./hello72
Hello world
どっちも動く。俺の誕生日にカーネルビルドするとはやるな。
cf.sf.jp
shinh@cf-amd64-linux:~/t> uname -a
Linux cf-amd64-linux 2.4.21-297-smp #1 SMP Sat Jul 23 00:45:13 UTC 2005 x86_64 x86_64 x86_64 GNU/Linux
shinh@cf-amd64-linux:~/t> ./hello72
Hello world
shinh@cf-amd64-linux:~/t> ./hello73
Hello world
Opteron のマシンらしいね
sf.net のシェルサーバ
[shinh@sc8-pr-shell1]~/t% uname -a
Linux sc8-pr-shell1.sourceforge.net 2.6.17.6 #1 SMP Sat Jul 15 16:00:03 PDT 2006 i686 i686 i386 GNU/Linux
[shinh@sc8-pr-shell1]~/t% ./hello72
Hello world
[shinh@sc8-pr-shell1]~/t% ./hello73
Hello world
-bash-3.00$ uname -a
Linux shell.cf.sourceforge.net 2.6.9-42.0.2.ELsmp #1 SMP Wed Aug 23 00:17:26 CDT 2006 i686 i686 i386 GNU/Linux
-bash-3.00$ ./hello72
Hello world
-bash-3.00$ ./hello73
Hello world
shinh@x86-linux1:~/t$ uname -a
Linux x86-linux1 2.6.8-2-386 #1 Tue Aug 16 12:46:35 UTC 2005 i686 GNU/Linux
shinh@x86-linux1:~/t$ ./hello72
Hello world
shinh@x86-linux1:~/t$ ./hello73
Hello world
shinh@x86-linux2:~/t$ uname -a
Linux x86-linux2.cf.sourceforge.net 2.6.10-1.771_FC2smp #1 SMP Mon Mar 28 01:10:51 EST 2005 i686 i686 i386 GNU/Linux
shinh@x86-linux2:~/t$ ./hello72
Hello world
shinh@x86-linux2:~/t$ ./hello73
Hello world
- Linux 2.6 (Fedora Core 3 on AMD64 Opteron)
shinh@amd64-linux1:~/t$ uname -a
Linux amd64-linux1.sourceforge.net 2.6.9-1.667smp #1 SMP Tue Nov 2 15:09:11 EST 2004 x86_64 x86_64 x86_64 GNU/Linux
shinh@amd64-linux1:~/t$ ./hello76
Segmentation fault
shinh@amd64-linux1:~/t$ ./hello73
Hello world
Segmentation fault
shinh@amd64-linux1:~/t$ ./hello72
72Bの方が帰ってこないよ！
全部どっかしらで問題出てるし。
というか 65B のヤツ_だけ_が動く64bit環境ってなにがおきてるの。
ちなみにすげーてきとうにぶっこんだファイル
http://shinh.skr.jp/t/t.tgz
(18:20)
_ とりあえず
Hello, world!\n が出る 64B を目指そうじゃないかと思った
それができないと負け犬
まぁ俺は負け犬なのでどうでもいいが
(18:38)
_ まあ
第一回くやしさまぎらわせ大会
プギャー
1st shinh 82 Ruby 10,000 (v32)
2nd kinaba 83 Perl 9,879 (v16)
3rd kik 83 Ruby 9,879 (v23)
プギャー
2nd primo 50 Ruby 9,200 (v23)
3rd shinh 50 Ruby 9,200 (v17)
4th queball 51 Ruby 9,019 (v3)
5th kik 51 Ruby 9,019 (v5)
6th mame 51 Ruby 9,019 (v2)
とか書くと瞬時に逆転されそうで怖いのであった
(18:40)
_ でも
ということは、一定ポータブルって条件を入れたら、
64B の Hello world (!,無し) が最短になる可能性が高いんだろうか。
そのくらいの難易度の争いじゃないと
歯牙にもかからん予感…
Debian でコケてた 65B hello73 は、
i@u3 ~/t> readelf -l hello73
readelf: エラー: Unable to read in 0x4b9 bytes of section headers
readelf: エラー: Unable to read in 0x972000 bytes of section headers
Elf ファイルタイプは EXEC (実行可能ファイル) です
エントリポイント 0x20002e
1 個のプログラムヘッダ、始点オフセット 32
Program Headers:
タイプ オフセット 仮想Addr 物理Addr FileSiz MemSiz Flg Align
LOAD 0x000000 0x00200000 0x04b90001 0x02000 0xd578d01 WE 0xeb9380cd
この MemSiz がでかすぎる模様。
というわけでぶっちゃけこんなのはすぐ調整できる
つーか lea 入れかえるだけだった。
; hello65.asm
BITS 32
org 0x00200000
db 0x7F, "ELF" ; e_ident
hello:
db "Hello world", 0xa
dw 2 ; e_type
dw 3 ; e_machine
exit: xor EBX, EBX ; e_version
int 0x80
dd _start ; e_entry
dd phdr - $$ ; e_phoff
phdr: dd 1 ; e_shoff ; p_type
dd 0 ; e_flags ; p_offset
dd $$ ; e_ehsize ; p_vaddr
; e_phentsize
dw 1 ; e_phnum ; p_paddr
_start:
mov ECX, 0x00200004
add [ECX], AL
lea EAX, [EDI+4]
inc EBX
lea EDX, [EDI+0xd]
int 0x80
xchg EBX, EAX
jmp exit
とりあえず今晩はこれを 64B にしよう。
(19:07)
_ くいーん
うわさどおり短い問題だ。
i@u ~/wrk/golf> ./golf.rb queen.rb
173
test 1:
SUCCESS! 0.000000 0.000000 0.016667 ( 0.017802)
test 2:
SUCCESS! 0.000000 0.000000 0.016667 ( 0.018432)
test 3:
SUCCESS! 0.000000 0.000000 0.033333 ( 0.016652)
test 4:
SUCCESS! 0.000000 0.000000 0.033333 ( 0.016837)
173
(22:58)
_ 87B
80切るようなことはあるだろうか。
無いんじゃないかなあ。
そうだとするとしばらく放置しても2位キープできる
というかそんな思考になってしまった僕が、悲しい。
(23:50)
_ Jeucrjbg [この間も俊太郎の詩をお http://www.stlouisbusinesslist.com/business/5..]