連載企画 FizzBuzz ではじめる Code Golf (x86 32bit) 入門

Code Golf とは? Matzにっき(2006-10-05) より

ゴルフとは如何に少ないストロークでホールインするかを競う競技である。
コードゴルフとは、如何に少ないキーストローク(バイト数)で、プログラムを実装できるかを競う競技である。

先日FizzBuzz.com (MS-DOS 16bit版) を作ってみたら、32bit版のプログラムにも挑戦したくなりましたので、x86 32bitで命令長を減らすテクニックについて紹介したいと思います。

※まずはコード長の比較のみで実行クロック数は競わないことにします。

■ x86 32bit コード最適化

【問題】EBXレジスタに1を、EAXレジスタに4を代入したい

できるだけ短いバイト数でコードを実現するためには、いろいろなx86命令をフル活用することを考えます。

自分の思いついた解答をNASMの記法で書いてみます。

(1) 10byteの解答 – 素直に32bit数値をMOVする

BB 01 00 00 00          mov EBX, 1
B8 04 00 00 00          mov EAX, 4

これが一番素直な方法ですが、レジスタ長が32bitのため、コードに 00 が6個もうまってしまっているのがもったいないです。

(2) 8byteの解答 – XORでゼロクリアして、INCで1を作る

31 DB                   xor EBX, EBX
43                      inc EBX
89 D8                   mov EAX, EBX
40                      inc EAX
40                      inc EAX
40                      inc EAX

そこで、XOR命令でレジスタをゼロクリアし、INC命令を繰り返して目的の値を作る方法を考えます。-2byteの節約です。しかし、4を作るのにINC命令が3つ並んでいるのはもったいないです。

(3) 8byteの解答 – シフト命令を使う

31 DB                   xor EBX, EBX
43                      inc EBX
89 D8                   mov EAX, EBX
C1 E0 02                shl EAX, 2

シフト命令で一気に1→4にしてしまいます。左2のシフト命令は3byteなので(2)と比べてコード長は変わりませんでしたが、実行クロックを減らすことはできました。

(4) 7byteの解答 – ALレジスタを活用して8bit代入

31 DB                   xor EBX, EBX
43                      inc EBX
31 DB                   xor EAX, EAX
B0 04                   mov AL, 4

32bitのEAXレジスタ、16bitのAXレジスタ、8bitのAH,ALレジスタの包含関係に着目して、下位8bitだけ4を代入する方法を考えます。これで-1byteの節約です。

(5) 6byteの解答 – LEA命令を使う

31 DB                   xor EBX, EBX
43                      inc EBX
8D 43 03                lea EAX, [EBX+3]

→ 6byte達成

EBXレジスタが必ずゼロクリアされているという前提があれば、先頭のXOR命令は省略できるので4byteで目的を達成することができます。

このように、LEA命令は覚えておくと大変便利です。

このようなx86の定石(パターン)は32bit x86 Tips – x86 TIPS AND TRICKSなどのページにまとまっています。

次回はこれらを踏まえたx86 32bit FizzBuzzプログラムの最適化テクニックを紹介する予定です。

コメントは受け付けていません。