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

【お知らせ】プログラミング記事の投稿はQiitaに移行しました。

Brainf*ckの分岐をJIT

x86の分岐命令は相対アドレス指定のため、分岐元と分岐先のアドレスが決まらなければ相対アドレスを求められません。

Brainf*ckではループの先頭と末尾で分岐が出てきます。相互に分岐しているので少し複雑です。

ループの先頭
loop_begin:
    cmp byte ptr[esi], 0  # 80 3e 00
    jz near loop_end      # 0f 84 ?? ?? ?? ??
ループの末尾
    jmp near loop_begin   # e9 ?? ?? ?? ??
loop_end:

相対アドレスの基点は次の命令の先頭です。これはCPUが命令を読み込んでから実行するため、実行するときにはPCが次の命令に行っているためです。

  • jz near loop_end => loop_end - (loop_begin + 9)
  • jmp near loop_begin => loop_begin - loop_end

ループの末尾を書き込むときには既に先頭のアドレスが分かっているため、特に問題なく相対アドレスを計算することができます。

問題はループの先頭で、ループの末尾の位置が確定するまで相対アドレスが計算できません。

そのためループの先頭のアドレスをキャッシュして仮にゼロを書き込んでおいて、ループの末尾を書き込むときにループの先頭の分岐も書き込みます。(遅延評価?)

codes = []
begin = []
(中略)
    elif cur == "[":
        begin += [len(codes)]
        codes += [0x80, 0x3e, 0x00]         # cmp byte ptr[esi], 0
        codes += [0x0f, 0x84, 0, 0, 0, 0]   # jz near ????
    elif cur == "]":
        ad1 = begin.pop()
        ad2 = len(codes) + 5
        codes[ad1+5:ad1+9] = conv32(ad2 - (ad1 + 9))
        codes += [0xe9] + conv32(ad1 - ad2) # jmp near begin

コード全体は以下を参照してください。

Pythonでポインタを扱う方法は以下を参照してください。

相対アドレスの計算については以下でも言及しています。