読者です 読者をやめる 読者になる 読者になる

maloader - a mach-o loader for linux

https://github.com/shinh/maloader

Linux で動く Mach-O loader を書いています。何ができるかというと、 Mac のバイナリが Linux でそれなりに動きます。今のところ、 gcc 、 otool 、 nm などの、いくつかのコマンドラインツールと、その gcc が生成した簡単なプログラムなんかが動きます。 Safari とか iTunes とかはもちろん動きませんし、動くようにしたいとも思ってないです。

仕組みとしては、引数に与えられた Mach-O バイナリを適当に読み込んで、指定された通りに mmap して、未定義なシンボルは linux の世界から探してきて再配置して、でエントリポイントに jmp する、と。まぁローダの説明そのまんまという感じです。

ローダはまぁ Mach-O のフォーマットが mach-o/loader.h からだけだとわかりにくかったという問題があったんですが、 dyld のコードとかを参考にするとだいたいわかる感じでした。 Mach-O は strip したバイナリを小さくしたいんだろうなぁという工夫がある感じで感心しました。

それと、実行したシンボル名がわかると、再配置したシンボルの中でクラッシュしてるとかがわかって嬉しいとかがあったので、トランポリンみたいなのを作って関数呼び出し前に関数名を表示できる機能をつけたりとかもしました。

意外と苦労したのがシンボルの解決でした。 printf が未定義ですよーとか言われると linux 側のシンボルを適当に探してきてそれを使う感じなんですが、まず存在しないシンボルが結構な数あります。まぁ存在しないぶんには似たようなもんを実装するなり、 apple の libc からコピってくれば良い感じでした。

どっちかというと問題は存在するけどやることが違う関数で、例えば open の引数の O_ASYNC に割り当たってる数字が linuxmac が違う…とかそういうものや、 dirent のようにユーザコードが構造体の中身を触る感じの API になっていて、その構造体のレイアウトが linuxmac で全然違う、なんてものがありました。

特にめんどくさかったのが FILE で、 FILE って普通は中身をユーザコードの中でいじることは無いはずなんですが、 stdio.h の中には結構マクロで定義されてる関数もあって、中身直接いじることもある感じぽかったのでした。しょうがないから mac ぽいレイアウト + 末尾に linux の FILE を持った FILE のラッパみたいな構造体を作ってやって、 FILE をやりとりする API では全部そのラップされた構造体を適当にどうこうするみたいなそういう感じになって、 FILE 使ってる API って結構あることから面倒な感じでした。ていうかまだ対応してない API が結構あるはず。

TODO としては色々ありますが、とりあえず Mac の dyld を読む機能はあってもいいと思ってます。あと、今のところ x86-64 べったりですが、 i686 も暇な時にやってみてもいいかなぁと思ってます。

それと最初は Mach-O => ELF のコンバータだったところを libc の初期化とかがめんどくさいということで今の形になっているのですが、この作りだと C++ 例外とかデバッグ情報とかどうしようもないので、コンバータの方をもうちょい頑張るというのもやってみてもいいかなぁと思っています。

wake 続き

http://shinh.skr.jp/wake/

なんか忘れてた $+ を足しました。一番最後にマッチした正規表現をひっかけるアレ。 primitive brainfuck code 書いてて忘れてたことに気付いた。

eban さんに文字列の外でも \ でエスケープできた方が空白含むアクションとか作れていいと指摘していただいたので、まぁそうだなぁとできるようにしておきました。

同じく eban さんに正規表現のトップレベルで | を使うとおかしいと指摘いただいたので、そのバグを潰しました。

ドキュメントに書き忘れてましたが \: を使えば正規表現中でコロンを使えます。

ドキュメントに書き忘れていましたが、 $< は何度でも使えます。 test/dup.wake なんかでは、

all: "$<" "$<"

とかやってます。

eval がよくわからんとのことなんですが、わかりにくいと思います。 std/num.wake を使うコードを見るといいかもしれないとのことなので、 0 から 9 までを表示するコードをドキュメントの方に足しておきました。

最小限に近い言語機能でライブラリが作れる言語にしたいと考てつけた機能なんで、これが無いとライブラリ的なものは作りにくいと思いますが、しかしゴルフする分には必要になる機会はやや少ないかもです。

このへんによると sed 好きな人にそれなりに遊んでもらっているようなので良かったなーと思いました。

http://jarp.does.notwork.org/diary/

http://ls-al.jp/blog2/

そういえば partial match じゃなくて full match ではまる、ってのは私もよくやります。 partial match を指示できる記法とか、 Perl の s///ge 的なのはあってもいいのかなーとは思ったんですが、まぁ make ぽさを殺さない記法を思いつかないし、最小限から遠くなっちゃうので、まぁそんなもんかなぁと思います。

しかしなんか結構な勢いでゴルフ場にコードが溜めていただいてますね… language ranking も結構上がってきてますし。例えば Go より上なので俺は Rob Pike に勝ったと言える。

http://golf.shinh.org/l.rb?wake

wake 続き

http://d.hatena.ne.jp/shinichiro_h/20100709#1278603483

の続き。

ドキュメントとか書きました。

http://shinh.skr.jp/wake/

パッケージもアップデートしました。

http://shinh.skr.jp/wake/wake.tgz

変更点は C++ 実装のインタプリタ (PCRE に依存) を追加したことと、 #include 、 std/num.wake とかいう加減乗除をする標準ライブラリ、あたりです。細かいバグフィックスもたぶんあったような気がします。

それなりに満足できたのでゴルフ場に追加しておきました。

プログラム言語 wake

Makefile正規表現とパターンマッチを混ぜたような、トイ言語を作ってみました。

http://shinh.skr.jp/wake/wake.tgz

Hello, world!

all: "Hello, world!"

wake のプログラムは Makefile のように書きます。つまり、 : で区切って左辺にターゲットを書いて、右辺にアクションを書く感じです。上記のように、 "" で修飾された文字列があると、その文字列を出力します。

Makefile のように、右辺には複数のターゲットを書けますし、文字列以外にも、他のターゲットを action として書くこともできます。

all: "Hello, " world
world: "world!"

正規表現

左辺のターゲットは、正規表現で書けます。例えば、

all: hoge hige fuga
.*: "yay!\n"

とすれば yay! が 3 回出力されます。正規表現Ruby のものに準じているので、インタプリタは waker という名前になっています。例えば JS なら wakejs とかにすればいいと思います。追記: あとで作った C++ 版は wake という名前で、 PCRE を使ってます。

右辺では、特殊変数 $&, $1, $2, $3, ... が使えます。それぞれ、 $& == マッチした文字列全体、 $N == N 番目の後方参照、です。これを使うと、

all: hoge "\n"
(.*)(.): "$2" $1
:

などとして hoge を逆順に出力するプログラムが書けます。 2 行目のターゲットは 1 文字以上の文字列全てにマッチします。アクションでは、一番最後の文字を "$2" で出力して、 "" のついていない、 $1 で、残った文字列を再帰的に評価しています。

3 行目の : は、 $1 がいずれ空文字列になってマッチする文字列が無くなるので、単に何もしないルールとして記述しています。

パターンマッチ

ルールは、常に上から順にマッチするかどうかを評価していきます。 o だけを O に変換して出力するプログラムなら、

all: hoge "\n"
o(.*): "O" $1
(.)(.*): "$1" $2
:

などとして書けます。

hoge を変換するだけのプログラムだとつまらないので、標準入力を処理することもできます。 $< という変数には標準入力が全て入っています。

all: $<
o(.*): "O" $1
(.)(.*): "$1" $2
:

eval

$(...) となっている表現があると、 ... の部分の文字列をターゲットとして現在のプログラムのルールを実行して、その実行結果の出力に展開されます。

今一つ短くて便利そうな例を思いつかないので、 FizzBuzz を例としてはっておきます。

fizzbuzz: fb@1,1

inc_mod3@2: "0"
inc_mod3@(\d): inc1@$1

inc1@9: "0"
inc1@8: "9"
inc1@7: "8"
inc1@6: "7"
inc1@5: "6"
inc1@4: "5"
inc1@3: "4"
inc1@2: "3"
inc1@1: "2"
inc1@0: "1"

inc_carry@(\d*)0: "$(inc@$1)0"
inc_carry@(\d+): "$1"

inc@: "1"
inc@(\d*)(\d): inc_carry@$1$(inc1@$2)

output@\d*[50],0: "FizzBuzz"
output@\d*[50],\d: "Buzz"
output@\d+,0: "Fizz"
output@(\d+),\d: "$1"

# Done
fb@101,\d:

fb@(\d+),(\d): output@$1,$2 "\n" fb@$(inc@$1),$(inc_mod3@$2)

感想

インタプリタであるところの waker.rb は -v とかつけると、途中のルール適用が表示されるので、デバッグに便利かもしれません。読みにくいですが。上の @ は関数と引数の区切り、という気持ちです。読みにくいから空白とかの方が良かったかも。

こういう細かい書くべきことは色々ある気がするんですが、まぁいいことにします。

正規表現がとても好きなので、こいう感じになったんじゃないかなと思います。 sed と比較すると、 fizzbuzz 書くまでの時間とか考えるとだいぶラクだったかなぁとか思います。別にラクさを目的として作ったわけじゃないですが。

ミニマルな言語としては、こんなもんかなぁと思うのですが、なんか機能を足すとしたら、整数演算くらいは欲しいかな…とは思います。 $[...] があったらその中身を四則演算する、くらいかなぁと(追記: どっちかというと、 include をできるようにして、標準ライブラリとして提供すればいいか…)。昨日思いついただけのものなので、意見とかいただければ嬉しいです。先行研究括弧笑いとか調べてないので、似たようなものはあるかもしれませんが、それも教えていただければー、と。

今後の展望としては、 Quine くらいはすぐ書けるんじゃないかと思います。あと JS と C で書いた処理系が欲しい。それとゴルフしてみるべき。

ああそうだ Brainfuck インタプリタを書かないといけない。

fugatrace

なんか TCC だの WebKit だのを触っていると、ツリー構造を何度もなめてて同じコードを何度も通る感じになって、デバッガの breakpoint がイマイチ機能しない時があります。そういう時は printf を仕込んだり条件付き break を使ったりとかするわけですが、まぁそういうもののオルタナティブとして tracer を書いてみました。

http://github.com/shinh/fugatrace

Mach-O と ELF 両方で動かにゃならんので適当に RubyGDB を使ういい加減な作りになっています。名前は hogetrace リスペクトで。

出力としてはこんな感じ。

http://shinh.skr.jp/dat_dir/trace.html.gz

重要なオプションは -g と -b と -R で、 -g は gdb の rbreak を使って正規表現で breakpoint を指定します。 -b は手動で break 。複数仕込む時はカンマで区切る。 break で止める場所の前に @ とすることで を break した時に発行して記録に残せる。 -R は exclude リストで、 -g で過剰に指定しすぎちゃった breakpoint を外すためのもの。

本当は -r というフラグで GDB のじゃなくて Ruby正規表現で break する位置を指定できるようにしたかったのだけど、 MacGDB の rbreak が WebKit でやるとメモリ使いつくして落ちるので今のところやってません。

sevil and w3mimg_cocoa for Snow leopard

http://shinh.skr.jp/osx/

適当に Snow leopard 対応をやっておきました。ていうか Leopard で動くかどうかって全く知らないということを思い出したので今度調べておきます。どうせ昔のやつは検証できないし誰も使わないし頻繁にアップデートする必要もないし、ということで別バージョンとしてアップロードしていくことに。

変更点としては要は CGSGetWindowProperty が CGSValue をやりとりするんじゃなくて、 CFStringRef をやりとりするように変わったからそれを変える必要があるのだった、ということじゃないかなぁと。

あと Shared Menubar とかいう名前の window が一番最初に出てくるようになったみたいだから、それを適当にすっとばすようにした。明らかにキモい。 Accessibility API がえらく速くなったみたいなので、ちゃんとそっちで取ってもいい気がする。ただ Accessibility API 取る時に相変わらず single thread だったりするとイマイチだから現状でもいいか…

caddy

http://golf.shinh.org/caddy.tgz

上げなおしておきました。

  • output がカラでも実行するべきと eban さんに教えてもらった
  • statistics が出るようになった
  • 時間が出るようになった
  • squeezer ちょっとだけいじった
  • もろもろ

yshl さんのご指摘は each_line の方は each_line にすると手元の Ruby1.9 とかでもむしろ動かなくなったのでよくわかなくてとりあえず保留

http://d.hatena.ne.jp/yshl/20090814#1250197680

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h