BrainfuckソースコードをJavaバイトコードにコンパイルするプログラムを作ってみたのでメモ。
詳細なJavaバイトコードの解説は行いません。
普通であればASMなどのライブラリーを使うところですが、せっかくなのでバイトを手書きしていきます。
The Java Virtual Machine Specification
クラスファイルについては4章、命令セットについては6章を参照されたし。
Brainfuckとは?
命令がわずか8つしかないチューリング完全なプログラミング言語。実用性はないが面白い。
大雑把に説明すると、Brainfuck実行環境はbyteの配列とその要素を指すポインタを持ち、それを命令セットで操作していく感じ。
詳細はリンク先を参照のこと。
準備
byte配列をちまちま作るのはやっていられないので、まず、Byteをまとめて書き込むためのコンビニエンスメソッドを定義する。
/**
* Helper class to create byte array fluently.
*/
public final class FluentByteWriter {
private final OutputStream os;
public FluentByteWriter(OutputStream os) {
this.os = os;
}
public FluentByteWriter write(Object... bytes) {
try {
for (Object o : bytes) {
// パターンマッチできない言語があるらしい
if (o instanceof Integer) {
os.write((Integer) o); // Note high-order bits are ignored
} else if (o instanceof Byte) {
os.write((Byte) o);
} else if (o instanceof byte[]) {
os.write((byte[]) o);
} else if (o instanceof String) {
os.write(((String) o).getBytes(StandardCharsets.UTF_8));
} else {
throw new UnsupportedOperationException("Unwritable class: " + o.getClass().getCanonicalName());
}
}
} catch (IOException e) {
throw new UncheckedIOException(e);
}
return this;
}
}
可変長引数でObjectを受け取って、その型に応じてOutputStreamに書き込んでいく。
OutputStream.write(int)は、引数のintの上位24ビットを無視して書き込むメソッド(Javaのintは4バイト)。
これがないと、Javaの16進リテラルは符号付のため、最上位の1ビットが有効な値を書き込めなくなってしまう
(例えば0xCAを書き込もうとしたとき、byteではなくint型とみなされ、byteを引数にとるメソッドでは利用できなくなる)。
次に、intを4バイト/2バイトのバイト配列に変換して書き込むヘルパーを定義。これも上位ビットは無視。
public static byte[] toByteArray4(int n) {
return ByteBuffer.allocate(4).putInt(n).array();
}
public static byte[] toByteArray2(short n) {
return ByteBuffer.allocate(2).putShort(n).array();
}
4バイト版だけならGuavaにInts.toByteArray()があるが、2バイト版も必要なので独自定義。
(今思うとShorts.toByteArray()でよかった)
コンパイル
出力されるバイトコードの仕様は以下の通り。
- デフォルトパッケージの
Mainクラス -
public static void main(String[] args)メソッドを持つので、javaコマンドで実行可能 - Brainfuckソースコードは、mainメソッドの中身にコンパイルされる
要するに、java Mainで変換されたバイトコードを実行できるようにする。
準備
0xCA, 0xFE, 0xBA, 0xBE, // CAFEBABE
0x00, 0x00, // miner version: 0
0x00, 0x31, // major version: 49 // Version 49 doesn't require stack map
0x00, 0x20, // constant pool count: 31 + 1
// constant pool
0x07, 0x00, 0x02, // 1. class: Main
0x01, 0x00, 0x04, // 2. utf8
"Main",
0x07, 0x00, 0x04, // 3. class: java/lang/Object
0x01, 0x00, 0x10, // 4. utf8
"java/lang/Object",
// System.out.print
0x09, 0x00, 0x06, 0x00, 0x08, // 5. fieldref System.out
0x07, 0x00, 0x07, // 6. class
0x01, 0x00, 0x10, // 7. utf8
"java/lang/System",
0x0C, 0x00, 0x09, 0x00, 0x0A, // 8. name and type
0x01, 0x00, 0x03, // 9. utf8
"out",
0x01, 0x00, 0x15, // 10. utf8
"Ljava/io/PrintStream;",
0x0A, 0x00, 0x0C, 0x00, 0x0E, // 11. method PrintStream.print(int)
0x07, 0x00, 0x0D, // 12. class
0x01, 0x00, 0x13, // 13. utf8
"java/io/PrintStream",
0x0C, 0x00, 0x0F, 0x00, 0x10, // 14. name and type
0x01, 0x00, 0x05, // 15. utf8
"print",
0x01, 0x00, 0x04, // 16. utf8
"(C)V",
// System.in.read(int)
0x09, 0x00, 0x06, 0x00, 0x12, // 17. fieldref System.in
0x0C, 0x00, 0x13, 0x00, 0x14, // 18. name and type
0x01, 0x00, 0x02, // 19. utf8
"in",
0x01, 0x00, 0x15, // 20. utf8
"Ljava/io/InputStream;",
0x0A, 0x00, 0x16, 0x00, 0x18, // 21. method InputStream.read(int)
0x07, 0x00, 0x17, // 22. class
0x01, 0x00, 0x13, // 23. utf8
"java/io/InputStream",
0x0C, 0x00, 0x19, 0x00, 0x1A, // 24. name and type
0x01, 0x00, 0x04, // 25. utf8
"read",
0x01, 0x00, 0x3, // 26. utf8
"()I",
// main
0x01, 0x00, 0x04, // 27. utf8
"main",
0x01, 0x00, 0x16, // 28. utf8
"([Ljava/lang/String;)V",
0x01, 0x00, 0x04, // 29. utf8
"args",
0x01, 0x00, 0x13, // 30. utf8
"[Ljava/lang/String;",
// "Code" for Attribute
0x01, 0x00, 0x04, // 31. utf8
"Code",
0x00, 0x21, // access_flags: ACC_SUPER ACC_PUBLIC
0x00, 0x01, // this class
0x00, 0x03, // super class
0x00, 0x00, // interfaces count
// interfaces[]
//NOP
0x00, 0x00, // fields count
// fields[]
// NOP
0x00, 0x01, // method count
特筆すべきことはなし。普通のJavaバイトコードを書き出していく。
インスタンス化する必要がないので<init>は持たない。
バイトコードのバージョンが49なのは、50からスタックマップが必要になって面倒なため。
(スタックマップについてはここを参照)
// methods[]
// main
0x00, 0x09, // access flags: ACC_PUBLIC ACC_STATIC
0x00, 0x1B, // name index: main
0x00, 0x1C, // descriptor index
0x00, 0x01, // attributes count
// attribute info
0x00, 0x1F // attribute name index: Code
);
byte[] code = compileCodes(is);
w.write(
ByteUtils.toByteArray4(code.length + 12), // attribute length
// info
0x00, 0x04, // max stack
0x00, 0x02, // max locals
// code length
ByteUtils.toByteArray4(code.length),
// code
code,
0x00, 0x00, // exception table length
// exception table
// NOP
0x00, 0x00, // attribute count
// attribute info[]
// NOP
// class attributes count
0x00, 0x00
// attributes
// NOP
compileCodes()メソッドが、実際のBrainfuck-Javaバイトコード変換を行っている。
Brainfuck-Javaバイトコード変換
まず環境を準備する。
w.write(
// creates data buffer
0x11, 0x75, 0x30, // sipush 30000
0xBC, 0x0A, // newarray int
0x4B, // astore_0 // ignore application arguments (String[] args)
// creates instruction pointer
0x03, // iconst_0
0x3C // istore_1
);
w.write(
compileCodeElements(is),
0xB1 // return
);
最初にバッファーを作る。
sipush 30000
newarray int
astore_0
何を間違えたのかbyteではなくintの配列を作っていた。気にしない気にしない……。
続いてインストラクションポインターを作る。
iconst_0
istore_1
compileCodeElements()
いよいよ実際のコード変換。
while ((i = is.read()) >= 0) {
switch (i) {
case ('+'):
// ...
break;
case ('-'):
// ...
break;
/*
* ....
レクサーもパーサーもいらないので楽。直接ストリームから一文字読み込み、switchでトークンを分岐していく。
+
0x2A, // aload_0
0x1B, // iload_1
0x5C, // dup2
0x2E, // iaload
0x04, // iconst_1
0x60, // iadd
0x4F // iastore
dup2はスタックの上二つを複製する命令。
ialoadで配列の値を読み込み、それを保存。
やっていることは単に1を足しただけ。そのまんま。
-
0x2A, // aload_0
0x1B, // iload_1
0x5C, // dup2
0x2E, // iaload
0x02, // iconst_m1
0x60, // iadd
0x4F // iastore
-1を足すようにしただけで、+とほぼ同じ。
>
0x84, 0x01, 0x01 // iinc 1 1
<
0x84, 0x01, 0xFF // iinc 1 -1
ローカル変数はiinc命令でインクリメント/デクリメントできるので、わずか一命令で書ける。
.
0xB2, 0x00, 0x05, // getstatic System.out
0x2A, // aload_0
0x1B, // iload_1
0x2E, // iaload
0x92, // i2c
0xB6, 0x00, 0x0B // invokevirtual print(C)V
文字列として出力したいので、intをcharに変換してから、System.out.print(char)を呼び出す。
,
0x2A, // aload_0
0x1B, // iload_1
0xB2, 0x00, 0x11, // getstatic System.in
0xB6, 0x00, 0x15, // invokevirtual read()I
0x4F // iastore
System.in.read()はintを返すので、そのまま配列に保存。
[
w.write((Object) compileLoop(is));
ループは別のメソッドを呼び出す。相互再帰的にcompileLoop()とcompileElement()を呼び出していけば、処理を綺麗に書けるという仕組み。
w.write(
// load current pointer value
0x2A, // aload_0
0x1B, // iload_1
0x2E // iaload
);
byte[] insideLoop = compileCodeElements(is);
w.write(
// if the current pointer indicates 0...
// 6 = ifeq(3) + goto(3)
0x99, ByteUtils.toByteArray2(insideLoop.length + 6), // ifeq
insideLoop,
0xA7, ByteUtils.toByteArray2(-(insideLoop.length + 6)) // goto
);
まず現在のポインターが指すバッファーの値を読み込む。
ifeq命令で0かどうかをチェックし、0ならばループ終わりにジャンプし、そうでなければ処理を行う。
処理終わりにはgotoでループの最初に戻る。
コードの長さに6を足しているのは、ifeqおよびgoto命令の長さを除くため。
初めジャンプ先の指定座標が絶対だと思い込んでいたので、何故かうまく動かず悩んでいた。実際には現在地からの相対サイズを指定する。
そのほうがコード生成がずっと楽。よく考えられているなぁと感心しました(小並感)。
上で述べたように相互再帰を利用してループを処理するので、よく見かけるBFインタプリタ―のように、ループの数を数えておかなくてもジャンプ先がわかる。
]
case (']'):
// exit loop
return baos.toByteArray();
処理を終了してループを抜ける。
もしマッチする[がないまま呼ばれた場合、処理が終了することになってしまう。
マッチが見つからなかった場合の仕様を発見できなかったため、未定義とみなして楽な処理にした。
コンパイルエラーにするほうが親切かもしれない。
最適化
TODO
POSTDの記事を参考にいつかやる。
- 同じ命令の繰り返しは容易に最適化できる。例えば
+命令では、iconst_1を命令の数に合わせて書き換えるだけでいい。 - ループは初めから位置を固定している。
- 記事の「その3」(
[-]など)はバイトコード自身に難しいところはあまりないと思われる。どちらかといえば入力を操作するほうが面倒。
感想
- 思っていたより簡単だった
- Javaバイトコードを出力するからと言ってJavaで書く必要はどこにもなかった。Javaは面倒。