共有回帖数 0 个
-
cu的链接：blog.chinaunix.net/space.php?uid=28110881&do=blog&id=3401900
本篇并不涉及有关语言和可计算性的理论，单纯对一个brainf*ck编译器的实现作出讨论。
有关brainf*ck语言的细节很容易wiki到，这里也略去。
编译器的原作者给出了长篇幅的注释，对理解程序的运行很有帮助，但毕竟不能给出完整
的图景，所以本文中去掉了大部分注释，代以自行添加的简短注释。文中将会对编译器的
全部代码进行分析，代码附加的行号用作参考；行号缺失的部分往往是空行或是被略去的
注释，而不是实际的汇编代码。
我个人在阅读代码的过程中，对代码进行了一些排版，但并没有规范地对齐注释。
因为文中代码较多，建议阅读本文时使用等宽字体。
这个编译器被设计成ELF格式，运行在i386体系上，总长度170字节。比起使用二进制
lambda演算的抽象机器＋解释器的尺寸之和要大一些，但相对好理解。
有关二进制lambda演算的内容，只好一边学一边说着〔推到下一个故事〕了。
同时也感谢freenode #c_lang_cn上，nick为randomclown的朋友推荐了二进制lambda演算
这话题以及相关的参考，真是大开眼界。
代码参考这里：pastebin. [HX] mozilla.org/1924352
0 ELF首部备考
为了便于参照，给出文中涉及到的ELF首部结构。代码来自个人的微内核实现（坑）nvm.
在i386上，类型和尺寸的关系如下：
elf32_uchar 1B
elf32_half 2B
elf32_word 4B
elf32_sword 4B
elf32_addr 4B
elf32_off 4B
除了elf32_sword是有符号的之外，其它类型都是无符号的。
下面是ELF首部的结构：
13 #define EI_NIDENT 16
14
15 struct elf32_hdr_struct {
16 elf32_uchar e_ident[EI_NIDENT];
17 elf32_half e_type; // file type
18 elf32_half e_machine; // architecture
19 elf32_word e_version;
20 elf32_addr e_entry; // entry point
21 elf32_off e_phoff; // PH table offset
22 elf32_off e_shoff; // SH table offset
23 elf32_word e_flags;
24 elf32_half e_ehsize; // header size in bytes
25 elf32_half e_phentsize; // PH size
26 elf32_half e_phnum; // PH number
27 elf32_half e_shentsize; // SH size
28 elf32_half e_shnum; // SH number
29 elf32_half e_shstrndx; // SH name string table index
30 } __attribute__ ((packed));
31 typedef struct elf32_hdr_struct elf32_hdr_t;
正确填充即充分的部分包括e_ident的前四字节，e_type, e_machine, e_entry, e_phoff,
e_phentsize, e_phnum, e_shnum.
下面是ELF程序首部的结构：
64 struct elf32_program_hdr_struct {
65 elf32_word p_type;
66 elf32_off p_offset;
67 elf32_addr p_vaddr;
68 elf32_addr p_paddr; // ignored
69 elf32_word p_filesz; // segment size in file
70 elf32_word p_memsz; // segment size in memory
71 elf32_word p_flags;
72 elf32_word p_align;
73 } __attribute__ ((packed));
74 typedef struct elf32_program_hdr_struct elf32_program_hdr_t;
正确填充即充分的部分包括p_type, p_offset, p_vaddr, p_filesz, p_memsz, p_flags.
实际上，由于其它部分被用于存放其值作为首部字段并不正确的指令，objdump和gdb并不
能正确识别可执行印象格式，但readelf可以按照ELF格式对文件进行分析。
另外，我并没有试过手工对这编译器进行ptrace.
1 常数备考和可执行映像布局
下面的代码定义了常数和布局：
1 BITS 32
2
3 %define arraysize 30000
4
5 %define TEXTORG 0x45E9B000
6 %define DATAOFFSET 0x2000
7 %define DATAORG (TEXTORG + DATAOFFSET)
8
9
10 org TEXTORG
206 compilersize equ $ - $$
TEXTORG指出了正文部分的起始地址（编译器和可执行映像使用相同的布局），语言约定
的数据区由此向高址偏移0x2000字节，长度为30000字节。
0x45e9b000这一起始地址对于Linux i386实现而言是可用的（一个可用的典型起始地址
是0x40000000）。实际上，它是两条指令和一字节常数构成的。
compilersize为0xaa, 即170字节。它用于指定程序首部中的p_filesz.
所编译出的程序具有正确的映像尺寸；除此例外，程序和编译器到标号codebuf对应的
偏移为止，具有相同的目标代码，但程序自身运行时会自_start起顺序向下执行，不再
执行编译器用于目标代码生成的代码。
2 编译器的ELF首部
为了减少编译器的尺寸，相当数量的代码被存储在ELF首部中，其中也有一部分代码参与
构成首部中的关键字段。下面对首部进行按字段的分析。为了清晰起见，代码的实际含
义留在后文解释，这里主要涉及代码如何正确地填充各首部。
注释中的记法(+x/y)对应一个当前字段，x给出了本指令／数据在字段中所占的字节数
（有跨字段的指令），y给出了字段当前已经累计的字节数。
* ELF魔数、文件类型和体系结构
13 db 0x7F, "ELF" ; ehdr.e_ident (+4/4)
14
15 emitputchar: add esi, byte (putchar - decchar) - 4 ; (+3/7)
16 ; write 3 instructions @ putchar
17 emitgetchar: lodsd ; (+1/8)
18 ; 4 bytes forward from incchar
19 ; and write 3 instructions @ getchar
20 emit6bytes: movsd ; (+1/9)
21 emit2bytes: movsb ; (+1/10)
22 emit1byte: movsb ; (+1/11)
23
24 ; init ecx = TEXTORG+filesize-$$
25 ; init edi = TEXTORG+codebuf-$$
26 ; ecx on the stack
27 compile:
28 lea esi, [byte ecx + epilog - filesize] ; (+3/14)
29 ; esi = TEXTORG+epilog-$$
30 xchg eax, ebx ; (+1/15)
31 ; padding
32 cmp eax, 0x00030002 ; ehdr.e_type (0x0002)
33 ; (+1/16)
34 ; (+2/2)
35 ; (+2/2)
36 ; ehdr.e_machine (0x0003)
ELF首部标识共长16字节，前四字节应当是0x7f和ascii串"ELF"。此后的部分被用于存储
实际使用的指令，并不具有padding意义。
指令
cmp eax, 0x00030002
同时给出了首部标识的最后一字节、文件类型（EXEC）和体系结构（Intel 80386）。
* 版本、入口地址、程序首部偏移
38 mov ebp, edi ; ehdr.e_version
39 ; (+2/2)
40 jmp short getchar ; (+2/4)
41
42 dd _start ; ehdr.e_entry (45e9b095)
43 dd proghdr - $$ ; ehdr.e_phoff (0000002c)
e_version的值并无意义，它只用于编译器本身的逻辑。
_start和proghdr - $$的值在注释中标出了，它们是正确的入口地址和程序首部偏移。
* 零散字段
46 eof:
47 movsd ; ehdr.e_shoff
48 ; copy epilog - exit
49 ; (+1/1)
50 xchg eax, ecx ; (+1/2)
51 pop ecx ; (+1/3)
52 ; ecx = TEXTORG
53 sub edi, ecx ; ehdr.e_flags
54 ; edi = size of program
55 ; (+1/4)
56 ; (+1/1)
57 xchg eax, edi ; (+1/2)
58 stosd ; (+1/3)
59 ; store size of prog in filesize
60 xchg eax, edx ; (+1/4)
61 ; 3rd arg of write
62 jmp short putchar ; ehdr.e_ehsize
63 ; (+2/2)
64
65 dw 0x20 ; ehdr.e_phentsize
这里有意义的字段只有e_phentsize, 它指出一个程序首部长32字节。
其余的指令用于在源程序输入结束时，将生成的目标代码输出成可执行文件。
* ELF首部的其他字段和重叠的程序首部
67 ; off = 2c
68 proghdr:
69 dd 1 ; ehdr.e_phnum & phdr.p_type
70 ; ehdr.e_shentsize
71 dd 0 ; ehdr.e_shnum & phdr.p_offset
72 ; ehdr.e_shstrndx
73 ; ehdr ends here
到71行为止，ELF首部已经结束。相对地，从位于文件偏移0x2c处的标号proghdr开始，
定义了程序首部。这些值是正确的（type为LOAD, offset=0）。
* 装载段地址
75 db 0 ; phdr.p_vaddr
76
77 ; esi @ decchar
78 ; ebp = edi
79 bracket:
80 ; opcode e9 = jmp rel16
81 mov al, 0xE9 ; (+2/3)
82 inc ebp ; p_vaddr = 45e9b000 (+1/4)
83 ; ebp (actually edi) on stack
84 push ebp ; phdr.p_paddr
85 ; (+1/1)
86 ; eax = ??????e9
87 stosd ; (+1/2)
88 jmp short emit1byte ; (+2/4)
对于Linux i386（以及多数IA32体系下的现代OS实现）来说，p_paddr会被忽略，因为没
法保证能分配合适的物理地址；但p_vaddr必须是正确的，它将决定程序段被装进地址空
间的位置（由于地址空间的实现基本平面化，这一地址往往是线性的）。
字节数据0x00, 指令
mov al, 0xE9
inc ebp
共同构成了p_vaddr的值0x45e9b000。同时，立即数0xe9也是jmp(rel16)的操作码，用于
生成一条向后跳转指令的残桩，等待回填。
p_paddr的值是无意义的。
* 文件尺寸、主存尺寸、标志和对齐
95 filesize:
96 dd compilersize ; phdr.p_filesz (=000000aa)
97
98
99 dd DATAOFFSET + arraysize ; phdr.p_memsz (=00009530)
100
101
102 putchar:
103 mov bl, 1 ; phdr.p_flags
104 ; (+2/2)
105 ; STDOUT_FILENO
106 mov al, 4 ; (+2/4)
107 int 0x80 ; phdr.p_align
108 ; (+2/2)
109
110
111 epilog:
112 popa ; (+1/3)
113 ; exit
114 inc eax ; (+1/4)
115 ; all headers ends here
标号filesize处的两个尺寸至关重要，它们给出了映像自身的尺寸，以及加载到主存之后
应当为程序分配的主存数。数值已经标在了注释中，也可以再参照第1节的介绍。
标志p_flags也被正确设置（WE），对齐字段的值则是无意义的。
特别注意，此段是可写的：编译器的逻辑将会对自身不再执行的代码进行修改，这些代码
位于映像的尾部、标号codebuf对应的偏移处，将被实际的目标代码填充。
到114行为止，唯一的一个程序段首部也已经结束。这些指令和数据共同构成了一个较小
功能的ELF首部，支持程序的基本运行，但不一定能被大部分分析工具正确分析。
3 目标代码生成
编译器从标准输入获得源程序，并最终将可执行映像写到标准输出。在此期间，目标代码
将会被写到标号codebuf对应的偏移处暂存。
目标代码生成期间，具有一定用处的寄存器包括
esi: 在为每一条指令生成目标代码前，esi都指向epilog处；
edi: 指向下一条指令对应目标代码序列的首址，初始为codebuf处；
ebp: 保存了分析开始前的edi值，用于生成[指令和]指令对应的跳转目的。
另外，编译器令ecx指向TEXTORG+filesize处。编译出的程序使用ecx作为数据指针。
* 初始化过程
188 _start:
189 xor ebx, ebx
190 mul ebx
191 mov ecx, DATAORG ; =45e9d000
192 inc edx
193 pusha
194
195
196 codebuf:
197 mov ch, (TEXTORG 8) & 0xFF ; cx=b000
198 push ecx
199 ; ecx = TEXTORG+filesize-$$
200 mov cl, filesize - $$
201 ; edi = TEXTORG+codebuf-$$
202 lea edi, [byte ecx + codebuf - filesize]
203 jmp short relay
这一过程完成了前述ecx和edi的初始化。edx被初始化为1，用于单字符getchar和putchar
的第三实参（读／写字节数）。
这里的getchar和putchar使用了系统调用read(2)和write(2)。
relay是一个中转标号，它将控制流转移到编译逻辑的主循环：
168 relay:
169 jnz compile
运行时的逻辑保证必然发生的转移正确发生。不发生转移的唯一状况是匹配到了]指令。
* 编译循环
27 compile:
28 lea esi, [byte ecx + epilog - filesize] ; (+3/14)
29 ; esi = TEXTORG+epilog-$$
30 xchg eax, ebx ; (+1/15)
31 ; padding
32 cmp eax, 0x00030002 ; ehdr.e_type (0x0002)
33 ; (+1/16)
34 ; (+2/2)
35 ; (+2/2)
36 ; ehdr.e_machine (0x0003)
37 ; ebp = TEXTORG+codebuf-$$ initially
38 mov ebp, edi ; ehdr.e_version
39 ; (+2/2)
40 jmp short getchar ; (+2/4)
每次循环都会重置esi, 使其指向epilog处，以定位目标代码。xchg和cmp都是padding.
在开始读取下一brainf*ck指令之前，将edi的当前值备份在ebp中。
getchar负责读取brainf*ck指令，并决定生成目标代码的分支。
* 目标代码（一）
102 putchar:
103 mov bl, 1 ; phdr.p_flags
104 ; (+2/2)
105 ; STDOUT_FILENO
106 mov al, 4 ; (+2/4)
107 int 0x80 ; phdr.p_align
108 ; (+2/2)
109
110
111 epilog:
112 popa ; (+1/3)
113 ; exit
114 inc eax ; (+1/4)
115 ; all headers ends here
116 int 0x80
117
118
119 incptr: inc ecx ; esi+4
120 decptr: dec ecx ; esi+5
121 incchar: inc byte [ecx] ; esi+6
122 decchar: dec byte [ecx] ; esi+8
123
124
125 ; init ecx = TEXTORG+filesize-$$
126 ; init esi = TEXTORG+epilog-$$
127 ; init edi = TEXTORG+codebuf-$$
128 ; ebp = edi
129 getchar:
130 mov al, 3 ; read(2)
131 xor ebx, ebx ; STDIN_FILENO
132 ; buf @ ecx
133 ; count = edx (==1)
134 int 0x80 ; trigger
上面的段落对应了六种brainf*ck指令的目标代码，以及_exit(2)对应的目标码epilog.
、、+、-这四条brainf*ck指令对应incptr至decchar的四条汇编指令。前两者各长1字
节，后两者各长2字节。,和.这两条brainf*ck指令分别对应getchar和putchar标号处的
三条汇编指令（均共长6字节）。
* 分支预备
自134行以下，源码分析的段落共享了getchar处的三条指令用于读取一字节输入。
137 or eax, eax ; eax = 0?
138 jle eof ; ZF = 1, eax = 0, EOF reached
read(2)返回后，上面的段落检查返回值。当检测到EOF的时候离开编译循环，转向EOF处
理过程，重写首部并输出映像。
141 lodsd ; 4 bytes advanced, esi begin @ incptr
142 mov eax, [ecx] ; 4 bytes from stdin buffer
141行将esi从epilog移到incptr处，预备生成brainf*ck指令对应的目标码。142行则直接
把输入的一字节传入eax（长度并不重要，分支时只使用al）。
实际的分支从145行开始。
楼主 2015-11-19 13:11 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
