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

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

Brainf*ckトランスレータ (3) 変数とメモリ

Brainf*ck

前回に引き続きBrainf*ckのトランスレータを見ていきます。

Brainf*ckには変数が1つあります。トランスレータではこれをレジスタに割り当てます。

ABIにより関数呼び出しで破壊されないレジスタが決められています。保存されるレジスタを使えば、値の破壊を気にせずに変数とほぼ等価に使用できます。今回は32bitではesi、64bitではr12を使用します。

※64bitでesiを使用すると、関数(putcharなど)を呼び出したときに値が破壊される可能性があります。

メモリ

Brainf*ckの仕様では30,000バイトのメモリを持つと定義されています。変数はメモリのアドレスを指すポインタとして使用します。

アセンブリでは.commとしてbssにメモリを確保します。

# char mem[30000];
.comm mem, 30000

初期値

memの指すアドレスをレジスタに入れます。単純にmovするとmemの指すメモリの中身が入ってしまうため、lea命令を使用します。

# i386
.comm mem, 30000
.text
leal mem, %esi

※Mac OS XではデフォルトでPIC(位置独立コード)を要求されるため、単純にleaで処理すると警告されます。PICは(5)位置独立コードで説明しています。

mov

leaがどういう命令かを説明する前に、比較対象としてmov命令を見てみます。

レジスタに即値を代入する場合、mov命令を使うのが基本的な方法です。

# eax = 0x1234
movl $0x1234, %eax # AT&T
mov  eax, 0x1234   # Intel

AT&T記法では$を外すとメモリの中身が対象となります。Intel記法ではアドレスであることを示すブラケットで囲みます。

# eax = *(long *)0x1234
movl 0x1234, %eax  # AT&T
mov  eax, [0x1234] # Intel

メモリが以下の内容であれば、eax=0x12345678となります。

00001230: 00 01 02 03 78 56 34 12 aa bb cc dd 00 00 00 00

メモリから1バイトだけ取って上位をゼロで埋める場合はmovzx命令を使用します。AT&T記法ではmovzblとなりますが、ニーモニックがmovz、ソースのサイズがb、デスティネーション(レジスタ)のサイズがlとなります。

# eax = *(char *)0x1234
movzbl 0x1234, %eax  # AT&T
movzx  eax, [0x1234] # Intel

メモリが先ほど示した内容であれば、eax=0x78となります。

lea

指定したアドレスが指すメモリの内容ではなく、アドレスの値を代入する命令がleaです。メモリの内容は一切関係ありません。

# eax = 0x1234
leal 0x1234, %eax  # AT&T
lea  eax, [0x1234] # Intel

先ほどのmemの例では、memがアドレスとして扱われているため、メモリの中身ではなく、アドレスを値として取り出すのにleaを使用しています。

退避

mainはCRTから呼び出されます。esi/r12は呼び出し元に対して値を保存しなければならないため、mainから抜ける際に元の値に戻す必要があります。そのためmainの最初でpushして、最後でpopします。main自体の戻り値は0とするため、eaxに0をmovしてretします。

mainは通常のC関数と同じ扱いのため、呼び出し規約で必要とされる場合は接頭辞のアンダーバーを付けます。以下では接頭辞が必要ないELFの例を示します。

# i386(ELF)
.comm mem, 30000
.text
.globl main
main:
    pushl %esi
    leal mem, %esi
    # ...
    popl %esi
    movl $0, %eax
    ret
# x86_64(ELF)
.comm mem, 30000
.text
.globl main
main:
    pushq %r12
    leaq mem, %r12
    # ...
    popq %r12
    movl $0, %eax
    ret

増減

本来、変数の値を増減させる際に、変数の指すアドレスがメモリ空間からはみ出さないようにチェックする必要があります。今回は説明を単純化するためチェックは行いません。

Brainf*ckでは変数は1ずつ増減します。x86では1だけ増やす命令がinc、1だけ減らす命令がdecです。

# i386
incl %esi # esi++
decl %esi # esi--
# x86_64
incq %r12 # r12++
decq %r12 # r12--

メモリの増減

Brainf*ckにはメモリの中身を1バイト単位で増減させる命令があります。ニーモニックの接尾辞bでバイト指定にして、オペランドを括弧で囲みます。

# i386
incb (%esi) # (*(char *)esi)++
decb (%esi) # (*(char *)esi)--
# x86_64
incb (%r12) # (*(char *)r12)++
decb (%r12) # (*(char *)r12)--

AT&T記法での括弧は、Intel記法でのブラケットに相当します。AT&T記法での接尾辞がIntel記法ではキーワードとして表記されるため、見た目は長くなります。

# i386
.intel_syntax noprefix
inc byte ptr [esi] # (*(char *)esi)++
dec byte ptr [esi] # (*(char *)esi)--
# x86_64
.intel_syntax noprefix
inc byte ptr [r12] # (*(char *)r12)++
dec byte ptr [r12] # (*(char *)r12)--