はじめてのにき(2006-11-10)

2006-11-10

_ なぜ前者がダメなのか

理解するのに時間かかった。

http://gusmachine.blog49.fc2.com/blog-category-2.html

(00:49)

_ まあとりあえずは

issigned を…

(00:44)

_ 何やっても int になっちゃうよなぁ

http://ukai.org/d/index.cgi?2004-06-21

んーむ。

GCC とか C++ なら簡単なんだけど。

(01:11)

_ これが最大人数なのかぁ

http://mixi.jp/view_community.pl?id=275305

via http://www.jmuk.org/d/?path=2006/11/09#d09t02

(01:52)

_ 本物の 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)

_ ぎゃー

http://d.hatena.ne.jp/kikx/20061110#1163114535

irb(main):005:0> 52-6+14
=> 60

どこに Hello, world!\n 入ってるねん。あとまぁ 1B ずつずらすのは考えたんですけど、前考えた時はどこにも入らんという結論だったのと、今回はすぐ頭が痛くなって日和ってますた…

(14:23)

_ どっか

ヘッダの意味を勘違いしてるみたいだ。有力候補は p_offset とか p_filesz 。

図をぱくらせてもらって考えてた。 s はでかい値だとダメで上の2つは 0 じゃないとダメだったはず…

1C が矛盾

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 ** ** ** ** ** ** **

1D が矛盾

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 は同じくダメ。

1C-20 が小さすぎ

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 ** ** ** ** ** ** **

1C 矛盾

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 もだめな気が。

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 もそう。

10 付近が矛盾してる

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 ** ** ** ** ** ** **

これしばらく続く。

2C 付近が矛盾

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 ** ** ** ** ** ** **

これもちょいと続くよ

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 ** ** ** ** ** ** **

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 ** ** ** ** ** ** **

2A あたりが矛盾

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 ** ** ** ** ** ** **

しばらく続いて、

今度は 1C が矛盾

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 はどこでも動くんだけど。

Ubuntu

i@u ~> uname -a
Linux u 2.6.17-10-generic #2 SMP Fri Oct 13 18:45:35 UTC 2006 i686 GNU/Linux

これが作業環境。

Debian

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 はオッケ。

Fedora Core 5

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 という罠がひどい。

Debian woodie

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

どっちも動く。俺の誕生日にカーネルビルドするとはやるな。

SuSE 9.0

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 のマシンらしいね

これなんだろ rpm あるから rpm 系

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

CentOS 4.2

-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

Debian 3.1

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

Fedora Core 2

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)

_ まあ

第一回くやしさまぎらわせ大会

Prime Factors

プギャー

1st  shinh      82   Ruby     10,000 (v32)
2nd  kinaba     83   Perl     9,879 (v16)
3rd  kik        83   Ruby     9,879 (v23)

Vigenere Cipher

プギャー

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)

_ XFS て

すげーなあ

(18:55)

_ でも

ということは、一定ポータブルって条件を入れたら、 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)