1
;; bf.asm: Copyright (C) 1999 Brian Raiter <breadbox@muppetlabs.com>:
2
;; Licensed under the terms of the GNU General Public License, either
3
;; version 2 or (at your option) any later version.
4

5
;; To build:
6
;; nasm -f bin -o bf bf.asm && chmod +x bf
7
;; To use:
8
;; bf < foo.b > foo && chmod +x foo
9

10
BITS 32
11

12
;; This is the size of the data area supplied to compiled programs.
13

14
%define arraysize 30000
15

16
;; For the compiler, the text segment is also the data segment. The
17
;; memory image of the compiler is inside the code buffer, and is
18
;; modified in place to become the memory image of the compiled
19
;; program. The area of memory that is the data segment for compiled
20
;; programs is not used by the compiler. The text and data segments of
21
;; compiled programs are really only different areas in a single
22
;; segment, from the system's point of view. Both the compiler and
23
;; compiled programs load the entire file contents into a single
24
;; memory segment which is both writeable and executable.
25

26
%define TEXTORG		0x45E9B000
27
%define DATAOFFSET 	0x2000
28
%define DATAORG  	(TEXTORG + DATAOFFSET)
29

30
;; Here begins the file image.
31

32
org TEXTORG
33

34
;; At the beginning of the text segment is the ELF header and the
35
;; program header table, the latter consisting of a single entry. The
36
;; two structures overlap for a space of eight bytes. Nearly all
37
;; unused fields in the structures are used to hold bits of code.
38

39
;; The beginning of the ELF header.
40

41
db 0x7F, "ELF"				; ehdr.e_ident
42

43
;; The top(s) of the main compiling loop. The loop jumps back to
44
;; different positions, depending on how many bytes to copy into the
45
;; code buffer. After doing that, esi is initialized to point to the
46
;; epilog code chunk, a copy of edi (the pointer to the end of the
47
;; code buffer) is saved in ebp, the high bytes of eax are reset to
48
;; zero (via the exchange with ebx), and then the next character of
49
;; input is retrieved.
50

51
emitputchar:
52
	add esi, byte (putchar - decchar) - 4
53

54
emitgetchar:
55
	lodsd
56

57
emit6bytes:
58
	movsd
59

60
emit2bytes:
61
	movsb
62

63
emit1byte:
64
	movsb
65

66
compile:
67
	lea  esi, [byte ecx + epilog - filesize]
68
	xchg eax, ebx
69
	cmp  eax, 0x00030002	; ehdr.e_type (0x0002), ehdr.e_machine (0x0003)
70
	mov  ebp, edi			; ehdr.e_version
71
	jmp  short getchar
72

73
	;; The entry point for the compiler (and compiled programs), and the
74
	;; location of the program header table.
75

76
	dd _start				; ehdr.e_entry
77
	dd proghdr - $$			; ehdr.e_phoff
78

79
	;; The last routine of the compiler, called when there is no more
80
	;; input. The epilog code chunk is copied into the code buffer. The
81
	;; text origin is popped off the stack into ecx, and subtracted from
82
	;; edi to determine the size of the compiled program. This value is
83
	;; stored in the program header table, and then is moved into edx.
84
	;; The program then jumps to the putchar routine, which sends the
85
	;; compiled program to stdout before falling through to the epilog
86
	;; routine and exiting.
87

88
eof:
89
	movsd 					; ehdr.e_shoff
90
	xchg  eax, ecx
91
	pop   ecx
92
	sub   edi, ecx			; ehdr.e_flags
93
	xchg  eax, edi
94
	stosd
95
	xchg  eax, edx
96
	jmp   short putchar		; ehdr.e_ehsize
97

98
	;; 0x20 == the size of one program header table entry.
99

100
	dw 0x20					; ehdr.e_phentsize
101

102
;; The beginning of the program header table. 1 == PT_LOAD, indicating
103
;; that the segment is to be loaded into memory.
104

105
proghdr:
106
	dd 1					; ehdr.e_phnum & phdr.p_type, ehdr.e_shentsize
107
	dd 0					; ehdr.e_shnum & phdr.p_offset, ehdr.e_shstrndx
108

109
	;; (Note that the next four bytes, in addition to containing the first
110
	;; two instructions of the bracket routine, also comprise the memory
111
	;; address of the text origin.)
112

113
	db 0					; phdr.p_vaddr
114

115
;; The bracket routine emits code for the "[" instruction. This
116
;; instruction translates to a simple "jmp near", but the target of
117
;; the jump will not be known until the matching "]" is seen. The
118
;; routine thus outputs a random target, and pushes the location of
119
;; the target in the code buffer onto the stack.
120

121
bracket:
122
	mov  al, 0xE9
123
	inc  ebp
124
	push ebp				; phdr.p_paddr
125
	stosd
126
	jmp  short emit1byte
127

128
	;; This is where the size of the executable file is stored in the
129
	;; program header table. The compiler updates this value just before
130
	;; it outputs the compiled program. This is the only field in the two
131
	;; headers that differs between the compiler and its compiled
132
	;; programs. (While the compiler is reading input, the first byte of
133
	;; this field is also used as an input buffer.)
134

135
filesize:
136
	dd compilersize			; phdr.p_filesz
137

138
	;; The size of the program in memory. This entry creates an area of
139
	;; bytes, arraysize in size, all initialized to zero, starting at
140
	;; DATAORG.
141

142
	dd DATAOFFSET + arraysize	; phdr.p_memsz
143

144
	;; The code chunk for the "." instruction. eax is set to 4 to invoke
145
	;; the write system call. ebx, the file handle to write to, is set to
146
	;; 1 for stdout. ecx points to the buffer containing the bytes to
147
	;; output, and edx equals the number of bytes to output. (Note that
148
	;; the first byte of the first instruction, which is also the least
149
	;; significant byte of the p_flags field, encodes to 0xB3. Having the
150
	;; 2-bit set marks the memory containing the compiler, and its
151
	;; compiled programs, as writeable.)
152

153
putchar:
154
	mov bl, 1				; phdr.p_flags
155
	mov al, 4
156
	int 0x80				; phdr.p_align
157

158
	;; The epilog code chunk. After restoring the initialized registers
159
	;; eax and ebx are both zero. eax is incremented to 1, so as to invoke
160
	;; the exit system call. ebx specifies the process's return value.
161

162
epilog:
163
	popa
164
	inc eax
165
	int 0x80
166

167
	;; The code chunks for the ">", "<", "+", and "-" instructions.
168

169
incptr:
170
	inc ecx
171

172
decptr:
173
	dec ecx
174

175
incchar:
176
	inc byte [ecx]
177

178
decchar:
179
	dec byte [ecx]
180

181
	;; The main loop of the compiler continues here, by obtaining the next
182
	;; character of input. This is also the code chunk for the ","
183
	;; instruction. eax is set to 3 to invoke the read system call. ebx
184
	;; the file handle to read from, is set to 0 for stdin. ecx points to
185
	;; a buffer to receive the bytes that are read, and edx equals the
186
	;; number of bytes to read.
187

188
getchar:
189
	mov al, 3
190
	xor ebx, ebx
191
	int 0x80
192

193
	;; If eax is zero or negative, then there is no more input, and the
194
	;; compiler proceeds to the eof routine.
195

196
	or  eax, eax
197
	jle eof
198

199
	;; Otherwise, esi is advanced four bytes (from the epilog code chunk
200
	;; to the incptr code chunk), and the character read from the input is
201
	;; stored in al, with the high bytes of eax reset to zero.
202

203
	lodsd
204
	mov eax, [ecx]
205

206
	;; The compiler compares the input character with ">" and "<". esi is
207
	;; advanced to the next code chunk with each failed test.
208

209
	cmp al, '>'
210
	jz  emit1byte
211
	inc esi
212
	cmp al, '<'
213
	jz  emit1byte
214
	inc esi
215

216
	;; The next four tests check for the characters "+", ",", "-", and
217
	;; ".", respectively. These four characters are contiguous in ASCII
218
	;; and so are tested for by doing successive decrements of eax.
219

220
	sub al, '+'
221
	jz  emit2bytes
222
	dec eax
223
	jz  emitgetchar
224
	inc esi
225
	inc esi
226
	dec eax
227
	jz  emit2bytes
228
	dec eax
229
	jz  emitputchar
230

231
	;; The remaining instructions, "[" and "]", have special routines for
232
	;; emitting the proper code. (Note that the jump back to the main loop
233
	;; is at the edge of the short-jump range. Routines below here
234
	;; therefore use this jump as a relay to return to the main loop
235
	;; however, in order to use it correctly, the routines must be sure
236
	;; that the zero flag is cleared at the time.)
237

238
	cmp al, '[' - '.'
239
	jz  bracket
240
	cmp al, ']' - '.'
241

242
relay:
243
	jnz compile
244

245
;; The endbracket routine emits code for the "]" instruction, as well
246
;; as completing the code for the matching "[". The compiler first
247
;; emits "cmp dh, [ecx]" and the first two bytes of a "jnz near". The
248
;; location of the missing target in the code for the "[" instruction
249
;; is then retrieved from the stack, the correct target value is
250
;; computed and stored, and then the current instruction's jmp target
251
;; is computed and emitted.
252

253
endbracket:
254
	mov eax, 0x850F313A
255
	stosd
256
	lea esi, [byte edi - 8]
257
	pop eax
258
	sub esi, eax
259
	mov [eax], esi
260
	sub eax, edi
261
	stosd
262
	jmp short relay
263

264
;; This is the entry point, for both the compiler and its compiled
265
;; programs. The shared initialization code sets ecx to the beginning
266
;; of the array that is the compiled program's data area, and edx to
267
;; one. (This also clears the zero flag for the relay jump below.) The
268
;; registers are then saved on the stack, to be restored at the end.
269

270
_start:
271
	mov ecx, DATAORG
272
	inc edx
273
	pusha
274

275
;; At this point, the compiler and its compiled programs diverge.
276
;; Although every compiled program includes all the code in this file
277
;; above this point, only the three instructions directly above are
278
;; actually used by both. This point is where the compiler begins
279
;; storing the generated code, so only the compiler sees the
280
;; instructions below. This routine first modifies ecx to contain
281
;; TEXTORG, which is stored on the stack, and then offsets it to point
282
;; to filesize. edi is set equal to codebuf, and then the compiler
283
;; enters the main loop.
284

285
codebuf:
286
	mov  ch, (TEXTORG >> 8) & 0xFF
287
	push ecx
288
	mov  cl, filesize - $$
289
	lea  edi, [byte ecx + codebuf - filesize]
290
	jmp  short relay
291

292
;; Here ends the file image.
293

294
compilersize equ $ - $$