1 /*
2 * Brainfuck interpreter with SLJIT
3 *
4 * Copyright 2015 Wen Xichang (wenxichang@163.com). All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without modification, are
7 * permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright notice, this list of
10 * conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
13 * of conditions and the following disclaimer in the documentation and/or other materials
14 * provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) AND CONTRIBUTORS ``AS IS'' AND ANY
17 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
19 * SHALL THE COPYRIGHT HOLDER(S) OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
21 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
22 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
24 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27 #include "sljitLir.h"
28
29 #include <stdio.h>
30 #include <stdlib.h>
31
32 #define BF_CELL_SIZE 3000
33 #define BF_LOOP_LEVEL 256
34
readvalid(FILE * src)35 static int readvalid(FILE *src)
36 {
37 int chr;
38
39 while ((chr = fgetc(src)) != EOF) {
40 switch (chr) {
41 case '+':
42 case '-':
43 case '>':
44 case '<':
45 case '.':
46 case ',':
47 case '[':
48 case ']':
49 return chr;
50 }
51 }
52
53 return chr;
54 }
55
56 /* reading same instruction, and count, for optimization */
57 /* ++++ -> '+', 4 */
gettoken(FILE * src,int * ntok)58 static int gettoken(FILE *src, int *ntok)
59 {
60 int chr = readvalid(src);
61 int chr2;
62 int cnt = 1;
63
64 if (chr == EOF)
65 return EOF;
66
67 if (chr == '.' || chr == ',' || chr == '[' || chr == ']') {
68 *ntok = 1;
69 return chr;
70 }
71
72 while ((chr2 = readvalid(src)) == chr)
73 cnt++;
74
75 if (chr2 != EOF)
76 ungetc(chr2, src);
77
78 *ntok = cnt;
79 return chr;
80 }
81
82 /* maintaining loop matched [] */
83 struct loop_node_st {
84 struct sljit_label *loop_start;
85 struct sljit_jump *loop_end;
86 };
87
88 /* stack of loops */
89 static struct loop_node_st loop_stack[BF_LOOP_LEVEL];
90 static int loop_sp;
91
loop_push(struct sljit_label * loop_start,struct sljit_jump * loop_end)92 static int loop_push(struct sljit_label *loop_start, struct sljit_jump *loop_end)
93 {
94 if (loop_sp >= BF_LOOP_LEVEL)
95 return -1;
96
97 loop_stack[loop_sp].loop_start = loop_start;
98 loop_stack[loop_sp].loop_end = loop_end;
99 loop_sp++;
100 return 0;
101 }
102
loop_pop(struct sljit_label ** loop_start,struct sljit_jump ** loop_end)103 static int loop_pop(struct sljit_label **loop_start, struct sljit_jump **loop_end)
104 {
105 if (loop_sp <= 0)
106 return -1;
107
108 loop_sp--;
109 *loop_start = loop_stack[loop_sp].loop_start;
110 *loop_end = loop_stack[loop_sp].loop_end;
111 return 0;
112 }
113
my_alloc(long size,long n)114 static SLJIT_CALL void *my_alloc(long size, long n)
115 {
116 return calloc(size, n);
117 }
118
my_putchar(long c)119 static SLJIT_CALL void my_putchar(long c)
120 {
121 putchar(c);
122 }
123
my_getchar(void)124 static SLJIT_CALL long my_getchar(void)
125 {
126 return getchar();
127 }
128
my_free(void * mem)129 static SLJIT_CALL void my_free(void *mem)
130 {
131 free(mem);
132 }
133
134 #define loop_empty() (loop_sp == 0)
135
136 /* compile bf source to a void func() */
compile(FILE * src,unsigned long * lcode)137 static void *compile(FILE *src, unsigned long *lcode)
138 {
139 void *code = NULL;
140 int chr;
141 int nchr;
142
143 struct sljit_compiler *C = sljit_create_compiler();
144 struct sljit_jump *end;
145 struct sljit_label *loop_start;
146 struct sljit_jump *loop_end;
147
148 int SP = SLJIT_S0; /* bf SP */
149 int CELLS = SLJIT_S1; /* bf array */
150
151 sljit_emit_enter(C, 0, 0, 2, 2, 0, 0, 0); /* opt arg R S FR FS local_size */
152
153 sljit_emit_op2(C, SLJIT_XOR, SP, 0, SP, 0, SP, 0); /* SP = 0 */
154
155 sljit_emit_op1(C, SLJIT_MOV, SLJIT_R0, 0, SLJIT_IMM, BF_CELL_SIZE);
156 sljit_emit_op1(C, SLJIT_MOV, SLJIT_R1, 0, SLJIT_IMM, 1);
157 sljit_emit_ijump(C, SLJIT_CALL1, SLJIT_IMM, SLJIT_FUNC_OFFSET(my_alloc));/* calloc(BF_CELL_SIZE, 1) => R0 */
158
159 end = sljit_emit_cmp(C, SLJIT_EQUAL, SLJIT_R0, 0, SLJIT_IMM, 0); /* R0 == 0 --> jump end */
160
161 sljit_emit_op1(C, SLJIT_MOV, CELLS, 0, SLJIT_R0, 0); /* CELLS = R0 */
162
163 while ((chr = gettoken(src, &nchr)) != EOF) {
164 switch (chr) {
165 case '+':
166 case '-':
167 sljit_emit_op1(C, SLJIT_MOV_UB, SLJIT_R0, 0, SLJIT_MEM2(CELLS, SP), 0); /* R0 = CELLS[SP] */
168 sljit_emit_op2(C, chr == '+' ? SLJIT_ADD : SLJIT_SUB,
169 SLJIT_R0, 0, SLJIT_R0, 0, SLJIT_IMM, nchr); /* R0 ?= nchr */
170 sljit_emit_op1(C, SLJIT_MOV_UB, SLJIT_MEM2(CELLS, SP), 0, SLJIT_R0, 0); /* CELLS[SP] = R0 */
171 break;
172 case '>':
173 case '<':
174 sljit_emit_op2(C, chr == '>' ? SLJIT_ADD : SLJIT_SUB,
175 SP, 0, SP, 0, SLJIT_IMM, nchr); /* SP ?= nchr */
176 break;
177 case '.':
178 sljit_emit_op1(C, SLJIT_MOV_UB, SLJIT_R0, 0, SLJIT_MEM2(CELLS, SP), 0); /* R0 = CELLS[SP] */
179 sljit_emit_ijump(C, SLJIT_CALL1, SLJIT_IMM, SLJIT_FUNC_OFFSET(my_putchar)); /* putchar(R0) */
180 break;
181 case ',':
182 sljit_emit_ijump(C, SLJIT_CALL0, SLJIT_IMM, SLJIT_FUNC_OFFSET(my_getchar)); /* R0 = getchar() */
183 sljit_emit_op1(C, SLJIT_MOV_UB, SLJIT_MEM2(CELLS, SP), 0, SLJIT_R0, 0); /* CELLS[SP] = R0 */
184 break;
185 case '[':
186 loop_start = sljit_emit_label(C); /* loop_start: */
187 sljit_emit_op1(C, SLJIT_MOV_UB, SLJIT_R0, 0, SLJIT_MEM2(CELLS, SP), 0); /* R0 = CELLS[SP] */
188 loop_end = sljit_emit_cmp(C, SLJIT_EQUAL, SLJIT_R0, 0, SLJIT_IMM, 0); /* IF R0 == 0 goto loop_end */
189
190 if (loop_push(loop_start, loop_end)) {
191 fprintf(stderr, "Too many loop level\n");
192 goto compile_failed;
193 }
194 break;
195 case ']':
196 if (loop_pop(&loop_start, &loop_end)) {
197 fprintf(stderr, "Unmatch loop ]\n");
198 goto compile_failed;
199 }
200
201 sljit_set_label(sljit_emit_jump(C, SLJIT_JUMP), loop_start); /* goto loop_start */
202 sljit_set_label(loop_end, sljit_emit_label(C)); /* loop_end: */
203 break;
204 }
205 }
206
207 if (!loop_empty()) {
208 fprintf(stderr, "Unmatch loop [\n");
209 goto compile_failed;
210 }
211
212 sljit_emit_op1(C, SLJIT_MOV, SLJIT_R0, 0, CELLS, 0);
213 sljit_emit_ijump(C, SLJIT_CALL1, SLJIT_IMM, SLJIT_FUNC_OFFSET(my_free)); /* free(CELLS) */
214
215 sljit_set_label(end, sljit_emit_label(C));
216 sljit_emit_return(C, SLJIT_UNUSED, 0, 0);
217
218 code = sljit_generate_code(C);
219 if (lcode)
220 *lcode = sljit_get_generated_code_size(C);
221
222 compile_failed:
223 sljit_free_compiler(C);
224 return code;
225 }
226
227 /* function prototype of bf compiled code */
228 typedef void (*bf_entry_t)(void);
229
main(int argc,char ** argv)230 int main(int argc, char **argv)
231 {
232 void *code;
233 bf_entry_t entry;
234 FILE *fp;
235
236 if (argc < 2) {
237 fprintf(stderr, "Usage: %s <brainfuck program>\n", argv[0]);
238 return -1;
239 }
240
241 fp = fopen(argv[1], "rb");
242 if (!fp) {
243 perror("open");
244 return -1;
245 }
246
247 code = compile(fp, NULL);
248 fclose(fp);
249
250 if (!code) {
251 fprintf(stderr, "[Fatal]: Compile failed\n");
252 return -1;
253 }
254
255 entry = (bf_entry_t)code;
256 entry();
257
258 sljit_free_code(code);
259 return 0;
260 }
261