■ FizzBuzz x86 for バイナリアン
昨日の続き。今日は息抜きに FizzBuzz.com (MS-DOS 16bit版) を作ってみました。
0000000 b4 02 bb 31 30 30 ed e8 2c 00 e8 29 00 e8 39 00 0000020 e8 23 00 e8 3e 00 e8 30 00 e8 1a 00 e8 17 00 e8 0000040 27 00 e8 2f 00 e8 0e 00 e8 1e 00 e8 08 00 e8 05 0000060 00 e8 13 00 eb d1 80 ff 30 74 04 88 fa cd 21 88 0000100 da cd 21 e8 28 00 c3 fe c5 b2 46 cd 21 b2 69 cd 0000120 21 e9 08 00 b2 42 cd 21 b2 75 cd 21 b2 7a cd 21 0000140 cd 21 84 ed 75 04 e8 05 00 c3 30 ed eb e6 b2 0d 0000160 cd 21 b2 0a cd 21 fe c3 80 fb 3a 75 09 b3 30 fe 0000200 c7 80 ff 3a 74 01 c3 b8 00 4c cd 21 0000214
これで140byte
DISアセンブルするとこんな感じです。
00000000 B402 mov ah,0x2 00000002 BB3130 mov bx,0x3031 00000005 30ED xor ch,ch 00000007 E82C00 call 0x36 0000000A E82900 call 0x36 0000000D E83900 call 0x49 00000010 E82300 call 0x36 00000013 E83E00 call 0x54 00000016 E83000 call 0x49 00000019 E81A00 call 0x36 0000001C E81700 call 0x36 0000001F E82700 call 0x49 00000022 E82F00 call 0x54 00000025 E80E00 call 0x36 00000028 E81E00 call 0x49 0000002B E80800 call 0x36 0000002E E80500 call 0x36 00000031 E81300 call 0x47 00000034 EBD1 jmp short 0x7 00000036 80FF30 cmp bh,0x30 00000039 7404 jz 0x3f 0000003B 88FA mov dl,bh 0000003D CD21 int 0x21 0000003F 88DA mov dl,bl 00000041 CD21 int 0x21 00000043 E82800 call 0x6e 00000046 C3 ret 00000047 FEC5 inc ch 00000049 B246 mov dl,0x46 0000004B CD21 int 0x21 0000004D B269 mov dl,0x69 0000004F CD21 int 0x21 00000051 E90800 jmp 0x5c 00000054 B242 mov dl,0x42 00000056 CD21 int 0x21 00000058 B275 mov dl,0x75 0000005A CD21 int 0x21 0000005C B27A mov dl,0x7a 0000005E CD21 int 0x21 00000060 CD21 int 0x21 00000062 84ED test ch,ch 00000064 7504 jnz 0x6a 00000066 E80500 call 0x6e 00000069 C3 ret 0000006A 30ED xor ch,ch 0000006C EBE6 jmp short 0x54 0000006E B20D mov dl,0xd 00000070 CD21 int 0x21 00000072 B20A mov dl,0xa 00000074 CD21 int 0x21 00000076 FEC3 inc bl 00000078 80FB3A cmp bl,0x3a 0000007B 7509 jnz 0x86 0000007D B330 mov bl,0x30 0000007F FEC7 inc bh 00000081 80FF3A cmp bh,0x3a 00000084 7401 jz 0x87 00000086 C3 ret 00000087 B8004C mov ax,0x4c00 0000008A CD21 int 0x21
もっと短くできるかも。今日はここまで。
2007.05.12 追記
x86のオペコード・マップ（ニーモニック表）を見ると、まだ最適化できる余地が残っていることがわかります。
dias16.lzh に含まれる 80X86_OP.TXT
http://www.vector.co.jp/soft/dos/prog/se008548.html
IA-32 インテル(R) アーキテクチャ・ソフトウェア・デべロッパーズ・マニュアル
中巻：命令セット・リファレンス (日本語 PDF ファイル: 9,139KB)
ftp://download.intel.co.jp/jp/developer/jpdoc/24547103_j.pdf
- 第3章 命令セット・リファレンス (p.43-811)
- 付録A オペコード・マップ (p.815-834)
- 付録B 命令フォーマットおよびエンコーディング (p.837-888)
例えば、8bitのレジスタをINCするよりも16bitのワードレジスタをINCしたほうが実はオプコードが1byte少なかったりします。
inc ch ; FEC5 inc cl ; FEC1 inc cx ; 41
chレジスタの領域までオーバーフローしないときなら、inc cl の代わりに inc cx を使うと1byte節約することができます。
第一段階の最適化
inc *x / dec *x 命令をできるだけ使うようにレジスタを再配置して、call命令の呼び出し回数を減らし、ジャンプ命令を全部相対指定にしたら 140 → 118 byte (-32byte) に短縮できました。
あと、出力する区切り文字も CR LF(2byte) から半角スペース(1byte)に変更しました。
00000000 B402 mov ah,0x2 00000002 BB003A mov bx,0x3a00 00000005 B93130 mov cx,0x3031 00000008 E82000 call 0x2b 0000000B E83000 call 0x3e 0000000E E81D00 call 0x2e 00000011 E83400 call 0x48 00000014 E81100 call 0x28 00000017 E82400 call 0x3e 0000001A E82B00 call 0x48 0000001D E80E00 call 0x2e 00000020 E80500 call 0x28 00000023 E81700 call 0x3d 00000026 EBE0 jmp short 0x8 00000028 E81300 call 0x3e 0000002B E80000 call 0x2e 0000002E 80FD30 cmp ch,0x30 00000031 7404 jz 0x37 00000033 88EA mov dl,ch 00000035 CD21 int 0x21 00000037 88CA mov dl,cl 00000039 CD21 int 0x21 0000003B EB22 jmp short 0x5f 0000003D 43 inc bx 0000003E B246 mov dl,0x46 00000040 CD21 int 0x21 00000042 B269 mov dl,0x69 00000044 CD21 int 0x21 00000046 EB08 jmp short 0x50 00000048 B242 mov dl,0x42 0000004A CD21 int 0x21 0000004C B275 mov dl,0x75 0000004E CD21 int 0x21 00000050 B27A mov dl,0x7a 00000052 CD21 int 0x21 00000054 CD21 int 0x21 00000056 84DB test bl,bl 00000058 7502 jnz 0x5c 0000005A EB03 jmp short 0x5f 0000005C 4B dec bx 0000005D EBE9 jmp short 0x48 0000005F B220 mov dl,0x20 00000061 CD21 int 0x21 00000063 41 inc cx 00000064 38F9 cmp cl,bh 00000066 7508 jnz 0x70 00000068 B130 mov cl,0x30 0000006A FEC5 inc ch 0000006C 38FD cmp ch,bh 0000006E 7401 jz 0x71 00000070 C3 ret 00000071 B8004C mov ax,0x4c00 00000074 CD21 int 0x21
COM形式の実行ファイルをMS-DOSモードで実行した結果は以下の通りです。
コードの解説はあとで書く...かもしれない。
2007.05.12 追記
Yappoさんがコードにコメントをつけてくれました → http://subtech.g.hatena.ne.jp/yappo/20070511/1178907299
2007.05.14 追記
LOOPZ（＝LOOPE）命令を活用することにより88byteに短縮できました。
$ od -tx1 -Ax f88.com 000000 b9 05 00 be 03 00 bb 31 30 b4 02 4e 74 10 e2 23 000010 b1 05 b2 42 cd 21 b2 75 cd 21 84 ed eb 0b be 03 000020 00 b2 46 cd 21 b2 69 cd 21 b2 7a cd 21 cd 21 e1 000030 0f eb dd 80 ff 30 74 04 88 fa cd 21 88 da cd 21 000040 b2 20 cd 21 43 80 fb 3a 75 c1 b3 30 fe c7 80 ff 000050 3a 75 b8 b8 00 4c cd 21 000058
ndisasm(w) f88.com でDISアセンブルするとこんな感じです。
00000000 B90500 mov cx,0x5 00000003 BE0300 mov si,0x3 00000006 BB3130 mov bx,0x3031 00000009 B402 mov ah,0x2 0000000B 4E dec si 0000000C 7410 jz 0x1e 0000000E E223 loop 0x33 00000010 B105 mov cl,0x5 00000012 B242 mov dl,0x42 00000014 CD21 int 0x21 00000016 B275 mov dl,0x75 00000018 CD21 int 0x21 0000001A 84ED test ch,ch 0000001C EB0B jmp short 0x29 0000001E BE0300 mov si,0x3 00000021 B246 mov dl,0x46 00000023 CD21 int 0x21 00000025 B269 mov dl,0x69 00000027 CD21 int 0x21 00000029 B27A mov dl,0x7a 0000002B CD21 int 0x21 0000002D CD21 int 0x21 0000002F E10F loope 0x40 00000031 EBDD jmp short 0x10 00000033 80FF30 cmp bh,0x30 00000036 7404 jz 0x3c 00000038 88FA mov dl,bh 0000003A CD21 int 0x21 0000003C 88DA mov dl,bl 0000003E CD21 int 0x21 00000040 B220 mov dl,0x20 00000042 CD21 int 0x21 00000044 43 inc bx 00000045 80FB3A cmp bl,0x3a 00000048 75C1 jnz 0xb 0000004A B330 mov bl,0x30 0000004C FEC7 inc bh 0000004E 80FF3A cmp bh,0x3a 00000051 75B8 jnz 0xb 00000053 B8004C mov ax,0x4c00 00000056 CD21 int 0x21
MS-DOSで一文字ずつ出力する方法（ah=02h, int 21h）ではなく、 文字列表示命令（ah=09h, int 21h）を使えばもっと小さくできるかもしれません。