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 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 */ 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 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 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 114 static SLJIT_CALL void *my_alloc(long size, long n) 115 { 116 return calloc(size, n); 117 } 118 119 static SLJIT_CALL void my_putchar(long c) 120 { 121 putchar(c); 122 } 123 124 static SLJIT_CALL long my_getchar(void) 125 { 126 return getchar(); 127 } 128 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() */ 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 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