Beautiful in mathematical but ugly for programmer
Brainfuck ，也稱做是 BrainF 是一個 Esolang 但符合圖靈完全的程式語言： 主要利用八個符號來轉移所有的狀態，其中包含了目前狀態的的轉移、值的運算、條件運算以及 I/O。 因為結構簡單也自我完備 (可以用自己來撰寫自己的編譯器或直譯器)。 下面是一個用 Python 實作的直譯器：利用八個 if 條件式來判斷 input 並且作狀態的轉移。
if __name__ == "__main__":
import sys
import argparse
parser = argparse.ArgumentParser(description="BrainF Interpreter")
parser.add_argument("file")
args = parser.parse_args()
with open(args.file) as f:
buf = f.read()
space, cur, idx = ['\x00']*10240, 0, 0
while idx < len(buf):
if '+' == buf[idx]:
space[cur] = chr(ord(space[cur])+1)
elif '-' == buf[idx]:
space[cur] = chr(ord(space[cur])-1)
elif '<' == buf[idx]:
cur-= 1
elif '>' == buf[idx]:
cur += 1
elif '[' == buf[idx]:
if '\x00' == space[cur]:
cnt = 0
for idx in range(idx+1, len(buf)):
if '[' == buf[idx]:
cnt += 1
elif ']' == buf[idx] and cnt:
cnt -= 1
elif ']' == buf[idx]:
break
else:
raise TypeError("Missing ']'")
elif ']' == buf[idx]:
if '\x00' != space[cur]:
cnt = 0
for idx in range(idx-1, -1, -1):
if ']' == buf[idx]:
cnt += 1
elif '[' == buf[idx] and cnt:
cnt -= 1
elif '[' == buf[idx]:
break
else:
raise TypeError("Missing '['")
elif ',' == buf[idx]:
space[cur] = sys.stdin.read(1)
elif '.' == buf[idx]:
sys.stdout.write(space[cur])
idx += 1
上面的程式碼只是一個直譯器，但是當我們需要產生一個可以執行的 BrainF 的程式碼時， 需要的則是一個編譯器，我們利用 nasm 的 assembly language 來當作是一個 IR ： 產生一個合法的 ASM 並且交由 nasm 跟 gcc 來產生一個可執行的 BrainF 執行檔。
if __name__ == "__main__":
import sys, commands
import argparse
parser = argparse.ArgumentParser(description="BrainF Compiler on ELF/64")
parser.add_argument("file")
parser.add_argument("--outfile", default="a.out")
args = parser.parse_args()
## Read the BrainF source code
with open(args.file) as f:
buf = f.read()
with open("BrainF.S", 'w') as fd:
## Set 64 bits mode
fd.write("BITS 64\n")
## Initial section
fd.write("SECTION .text\n")
fd.write("global main\n")
fd.write("main:\n")
## Dynamically allocat a memory space
fd.write("mov rax, 0x09\n")
fd.write("mov rdi, 0x00\n")
fd.write("mov rsi, 0x100000\n")
fd.write("mov rdx, 0x03\n")
fd.write("mov r10, 0x22\n")
fd.write("mov r8, -1\n")
fd.write("mov r9, 0x00\n")
fd.write("syscall\n")
## Scanner and Lexer
lable, cnt = [], 0
for idx in range(len(buf)):
if '+' == buf[idx]:
fd.write("inc byte [rax]\n")
elif '-' == buf[idx]:
fd.write("dec byte [rax]\n")
elif '<' == buf[idx]:
fd.write("sub rax, 0x04\n")
elif '>' == buf[idx]:
fd.write("add rax, 0x04\n")
elif '[' == buf[idx]:
lable.append("lable{0}".format(cnt))
cnt += 1
fd.write("cmp byte [rax], 0x0\n")
fd.write("je {0}_END\n".format(lable[-1]))
fd.write("{0}:\n".format(lable[-1]))
elif ']' == buf[idx]:
fd.write("cmp byte [rax], 0x0\n")
fd.write("jne {0}\n".format(lable[-1]))
fd.write("{0}_END:\n".format(lable[-1]))
lable = lable[:-1]
elif ',' == buf[idx]:
fd.write("mov rsi, rax\n")
fd.write("push rax\n")
fd.write("mov rax, 0x00\n")
fd.write("mov rdi, 0x00\n")
fd.write("mov rdx, 0x01\n")
fd.write("syscall\n")
fd.write("pop rax\n")
elif '.' == buf[idx]:
fd.write("mov rsi, rax\n")
fd.write("push rax\n")
fd.write("mov rax, 0x01\n")
fd.write("mov rdi, 0x01\n")
fd.write("mov rdx, 0x01\n")
fd.write("syscall\n")
fd.write("pop rax\n")
## Exit via exit_group
fd.write("mov rax, 0xE7\n")
fd.write("syscall")
## Compile with nasm and gcc
print "Assemble ...", commands.getoutput("nasm -f elf64 BrainF.S")
print "Link ...", commands.getoutput("gcc -o {0} BrainF.o".format(args.outfile))
當然，上面的程式碼完全有改善的空間，包含了：Code Generator 應該重複利用相同的邏輯、 使用更短的指令集等。但是這只是個 POC ，就不用在意這麼多了。
接下來另一個實作是不利用 ASM 以及其他的工具，而是直接產生出 ELF64 的可執行檔： 包含需要實作符合 ELF 64-bits 格式的 header 以及相對應的 64-bits opcode 。 所以首先需要有一個 ELF 檔案格式的產生器：在這個產生器中，我們只需要提供 BrainF 所需要的八個能力，並且轉換成相對的 x86_64 opcode。
class ELF64(object):
""" Generate the valid ELF/64 format file """
def __init__(self, size=2**20):
self.data, self.offset = "", 0
self.mmap(size)
def __str__(self):
self.data += self.exit_group
return self.header + self.segment + self.data
@property
def header(self):
""" ELF/64 header """
header = "\x7FELF" ## Magic
header += '\x02' ## Class
header += '\x01' ## Endianness
header += '\x01' ## Version
header += '\x00' ## OS ABI
header += '\x00' ## OS ABI Ver
header += '\x00'*7 ## Reserverd
header += '\x02\x00' ## Executable
header += '\x3E\x00' ## Machine (AMD-64)
header += '\x01\x00\x00\x00' ## Version
header += '\x78\x00\x10\x00\x00\x00\x00\x00' ## Entry
header += '\x40\x00\x00\x00\x00\x00\x00\x00' ## Segment offset
header += '\x00\x00\x00\x00\x00\x00\x00\x00' ## Section offset
header += '\x00\x00\x00\x00' ## Flag
header += '\x40\x00' ## Size of this header
header += '\x38\x00' ## Segment size
header += '\x01\x00' ## Number of segment
header += '\x00\x00' ## Section size
header += '\x00\x00' ## Number of section
header += '\x00\x00' ## Index of the .shstrtab section
return header
@property
def segment(self):
from struct import pack
size = pack("Q", len(self.data) + 64 + 56)
header = '\x01\x00\x00\x00' ## Type
header += '\x05\x00\x00\x00' ## Flags
header += '\x00\x00\x00\x00\x00\x00\x00\x00' ## Offset
header += '\x00\x00\x10\x00\x00\x00\x00\x00' ## Virt Addr
header += '\x00\x00\x10\x00\x00\x00\x00\x00' ## Phy Addr
header += size
header += size
header += '\x00\x10\x00\x00\x00\x00\x00\x00' ## Align
return header
@property
def exit_group(self):
opcode = '\x48\x31\xFF\x48\xC7\xC0\xE7\x00\x00\x00\x0F\x05'
self.offset += len(opcode)
return opcode
def mmap(self, size):
""" Create a memoery space and return on rax"""
from struct import pack
size = pack("I", size)
opcode = '\x48\xC7\xC0\x09\x00\x00\x00' ## mov 0x09 rax
opcode += '\x48\xC7\xC7\x00\x00\x00\x00' ## mov 0x00 rdi
opcode += '\x48\xC7\xC6'+size ## mov size rsi
opcode += '\x48\xC7\xC2\x03\x00\x00\x00' ## mov 0x05 rdx
opcode += '\x49\xC7\xC2\x22\x00\x00\x00' ## mov 0x01 r10
opcode += '\x49\xC7\xC0\xFF\xFF\xFF\xFF' ## mov 0xFFFFFFFF r8
opcode += '\x41\xB9\x00\x00\x00\x00' ## mov 0x00 r9d
opcode += '\x0F\x05' ## syscall
self.data += opcode
self.offset += len(opcode)
return opcode
def add(self):
opcode = '\x48\x83\xC0\x04' ## add 0x04 rax
self.data += opcode
self.offset += len(opcode)
return opcode
def sub(self):
opcode = '\x48\x83\xE8\x04' ## sub 0x04 rax
self.data += opcode
self.offset += len(opcode)
return opcode
def inc(self):
opcode = '\xFE\x00' ## inc rax
self.data += opcode
self.offset += len(opcode)
return opcode
def dec(self):
opcode = '\xFE\x08' ## dec rax
self.data += opcode
self.offset += len(opcode)
return opcode
def read(self):
opcode = '\x48\x89\xC6' ## mov rax rsi
opcode += '\x50' ## push rax
opcode += '\x48\xC7\xC0\x00\x00\x00\x00' ## mov 1 rax
opcode += '\x48\xC7\xC7\x01\x00\x00\x00' ## mov 1 rdi
opcode += '\x48\xC7\xC2\x01\x00\x00\x00' ## mov 1 rdx
opcode += '\x0F\x05' ## syscall
opcode += '\x58' ## pop rax
self.data += opcode
self.offset += len(opcode)
return opcode
def write(self):
opcode = '\x48\x89\xC6' ## mov rax rsi
opcode += '\x50' ## push rax
opcode += '\x48\xC7\xC0\x01\x00\x00\x00' ## mov 1 rax
opcode += '\x48\xC7\xC7\x01\x00\x00\x00' ## mov 1 rdi
opcode += '\x48\xC7\xC2\x01\x00\x00\x00' ## mov 1 rdx
opcode += '\x0F\x05' ## syscall
opcode += '\x58' ## pop rax
self.data += opcode
self.offset += len(opcode)
return opcode
def jumpIfZero(self, label):
opcode = '\x80\x38\x00' ## cmp 0x00 rax
opcode += '\x74{{{label}}}' ## je
## FIXME - Always add one byte for address shift
self.offset += 5
self.data += opcode.format(label=label)
return opcode
def jumpIfNotZero(self, label):
opcode = '\x80\x38\x00' ## cmp 0x00 rax
opcode += '\x75{{{label}}}' ## jnz
## FIXME - Always add one byte for address shift
self.offset += 5
self.data += opcode.format(label=label)
return opcode
最後跟原本的邏輯一樣，一個簡單的 Scanner/Lexer 處理檔案並且利用之前的 ELF Generator 來產生合法的可執行檔。
if __name__ == "__main__":
import sys, os
import argparse
parser = argparse.ArgumentParser(description="BrainF Compiler on ELF/64")
parser.add_argument("file")
parser.add_argument("--outfile", default="a.out")
args = parser.parse_args()
with open(args.file) as f:
buf = f.read()
## ELF Generator, label count and label stack
elf, cnt, label, stack = ELF64(), 0, {}, []
if True:
space, cur, idx = ['\x00']*10240, 0, 0
while idx < len(buf):
if '+' == buf[idx]:
elf.inc()
elif '-' == buf[idx]:
elf.dec()
elif '<' == buf[idx]:
elf.sub()
elif '>' == buf[idx]:
elf.add()
elif '[' == buf[idx]:
## Set the jump label, and fill the address finally
_label_ = "label{0}".format(cnt)
elf.jumpIfZero(_label_)
label.update({_label_ : elf.offset})
stack.append(_label_)
cnt += 1
elif ']' == buf[idx]:
from struct import pack
_label_ = "{0}_END".format(stack[-1])
elf.jumpIfNotZero(_label_)
## First set the end of condition offset
off = 0xFF + label[stack[-1]] - elf.offset + 1
label.update({_label_ : pack("B", off)})
## Second, reset the offset at the previous condition
off = elf.offset - label[stack[-1]]
label.update({stack[-1] : pack("B", off)})
stack = stack[:-1]
elif ',' == buf[idx]:
elf.read()
elif '.' == buf[idx]:
elf.write()
idx += 1
with open(args.outfile, 'wb') as f:
f.write((str(elf).format(**label)))
os.chmod(args.outfile, 0777)