xref: /src/sys/external/bsd/sljit/dist/doc/tutorial/brainfuck.c

/*
 *    Brainfuck interpreter with SLJIT
 *
 *    Copyright 2015 Wen Xichang (wenxichang (at) 163.com). All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification, are
 * permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright notice, this list of
 *      conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above copyright notice, this list
 *      of conditions and the following disclaimer in the documentation and/or other materials
 *      provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) AND CONTRIBUTORS ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
 * SHALL THE COPYRIGHT HOLDER(S) OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "sljitLir.h"

#include <stdio.h>
#include <stdlib.h>

#define BF_CELL_SIZE		3000
#define BF_LOOP_LEVEL		256

static int readvalid(FILE *src)
{
	int chr;

	while ((chr = fgetc(src)) != EOF) {
		switch (chr) {
		case '+':
		case '-':
		case '>':
		case '<':
		case '.':
		case ',':
		case '[':
		case ']':
			return chr;
		}
	}

	return chr;
}

/* reading same instruction, and count, for optimization */
/* ++++  -> '+', 4 */
static int gettoken(FILE *src, int *ntok)
{
	int chr = readvalid(src);
	int chr2;
	int cnt = 1;

	if (chr == EOF)
		return EOF;

	if (chr == '.' || chr == ',' || chr == '[' || chr == ']') {
		*ntok = 1;
		return chr;
	}

	while ((chr2 = readvalid(src)) == chr)
		cnt++;

	if (chr2 != EOF)
		ungetc(chr2, src);

	*ntok = cnt;
	return chr;
}

/* maintaining loop matched [] */
struct loop_node_st {
	struct sljit_label *loop_start;
	struct sljit_jump *loop_end;
};

/* stack of loops */
static struct loop_node_st loop_stack[BF_LOOP_LEVEL];
static int loop_sp;

static int loop_push(struct sljit_label *loop_start, struct sljit_jump *loop_end)
{
	if (loop_sp >= BF_LOOP_LEVEL)
		return -1;

	loop_stack[loop_sp].loop_start = loop_start;
	loop_stack[loop_sp].loop_end = loop_end;
	loop_sp++;
	return 0;
}

static int loop_pop(struct sljit_label **loop_start, struct sljit_jump **loop_end)
{
	if (loop_sp <= 0)
		return -1;

	loop_sp--;
	*loop_start = loop_stack[loop_sp].loop_start;
	*loop_end = loop_stack[loop_sp].loop_end;
	return 0;
}

static SLJIT_CALL void *my_alloc(long size, long n)
{
	return calloc(size, n);
}

static SLJIT_CALL void my_putchar(long c)
{
	putchar(c);
}

static SLJIT_CALL long my_getchar(void)
{
	return getchar();
}

static SLJIT_CALL void my_free(void *mem)
{
	free(mem);
}

#define loop_empty()		(loop_sp == 0)

/* compile bf source to a void func() */
static void *compile(FILE *src, unsigned long *lcode)
{
	void *code = NULL;
	int chr;
	int nchr;

	struct sljit_compiler *C = sljit_create_compiler();
	struct sljit_jump *end;
	struct sljit_label *loop_start;
	struct sljit_jump *loop_end;

	int SP = SLJIT_S0;			/* bf SP */
	int CELLS = SLJIT_S1;		/* bf array */

	sljit_emit_enter(C, 0,  0,  2, 2, 0, 0, 0);								/* opt arg R  S  FR FS local_size */

	sljit_emit_op2(C, SLJIT_XOR, SP, 0, SP, 0, SP, 0);						/* SP = 0 */

	sljit_emit_op1(C, SLJIT_MOV, SLJIT_R0, 0, SLJIT_IMM, BF_CELL_SIZE);
	sljit_emit_op1(C, SLJIT_MOV, SLJIT_R1, 0, SLJIT_IMM, 1);
	sljit_emit_ijump(C, SLJIT_CALL1, SLJIT_IMM, SLJIT_FUNC_OFFSET(my_alloc));/* calloc(BF_CELL_SIZE, 1) => R0 */

	end = sljit_emit_cmp(C, SLJIT_EQUAL, SLJIT_R0, 0, SLJIT_IMM, 0);		/* R0 == 0 --> jump end */

	sljit_emit_op1(C, SLJIT_MOV, CELLS, 0, SLJIT_R0, 0);					/* CELLS = R0 */

	while ((chr = gettoken(src, &nchr)) != EOF) {
		switch (chr) {
		case '+':
		case '-':
			sljit_emit_op1(C, SLJIT_MOV_UB, SLJIT_R0, 0, SLJIT_MEM2(CELLS, SP), 0);		/* R0 = CELLS[SP] */
			sljit_emit_op2(C, chr == '+' ? SLJIT_ADD : SLJIT_SUB,
						   SLJIT_R0, 0, SLJIT_R0, 0, SLJIT_IMM, nchr);					/* R0 ?= nchr */
			sljit_emit_op1(C, SLJIT_MOV_UB, SLJIT_MEM2(CELLS, SP), 0, SLJIT_R0, 0);		/* CELLS[SP] = R0 */
			break;
		case '>':
		case '<':
			sljit_emit_op2(C, chr == '>' ? SLJIT_ADD : SLJIT_SUB,
						   SP, 0, SP, 0, SLJIT_IMM, nchr);								/* SP ?= nchr */
			break;
		case '.':
			sljit_emit_op1(C, SLJIT_MOV_UB, SLJIT_R0, 0, SLJIT_MEM2(CELLS, SP), 0);		/* R0 = CELLS[SP] */
			sljit_emit_ijump(C, SLJIT_CALL1, SLJIT_IMM, SLJIT_FUNC_OFFSET(my_putchar));	/* putchar(R0) */
			break;
		case ',':
			sljit_emit_ijump(C, SLJIT_CALL0, SLJIT_IMM, SLJIT_FUNC_OFFSET(my_getchar));	/* R0 = getchar() */
			sljit_emit_op1(C, SLJIT_MOV_UB, SLJIT_MEM2(CELLS, SP), 0, SLJIT_R0, 0);		/* CELLS[SP] = R0 */
			break;
		case '[':
			loop_start = sljit_emit_label(C);											/* loop_start: */
			sljit_emit_op1(C, SLJIT_MOV_UB, SLJIT_R0, 0, SLJIT_MEM2(CELLS, SP), 0);		/* R0 = CELLS[SP] */
			loop_end = sljit_emit_cmp(C, SLJIT_EQUAL, SLJIT_R0, 0, SLJIT_IMM, 0);		/* IF R0 == 0 goto loop_end */

			if (loop_push(loop_start, loop_end)) {
				fprintf(stderr, "Too many loop level\n");
				goto compile_failed;
			}
			break;
		case ']':
			if (loop_pop(&loop_start, &loop_end)) {
				fprintf(stderr, "Unmatch loop ]\n");
				goto compile_failed;
			}

			sljit_set_label(sljit_emit_jump(C, SLJIT_JUMP), loop_start);				/* goto loop_start */
			sljit_set_label(loop_end, sljit_emit_label(C));								/* loop_end: */
			break;
		}
	}

	if (!loop_empty()) {
		fprintf(stderr, "Unmatch loop [\n");
		goto compile_failed;
	}

	sljit_emit_op1(C, SLJIT_MOV, SLJIT_R0, 0, CELLS, 0);
	sljit_emit_ijump(C, SLJIT_CALL1, SLJIT_IMM, SLJIT_FUNC_OFFSET(my_free));	/* free(CELLS) */

	sljit_set_label(end, sljit_emit_label(C));
	sljit_emit_return(C, SLJIT_UNUSED, 0, 0);

	code = sljit_generate_code(C);
	if (lcode)
		*lcode = sljit_get_generated_code_size(C);

compile_failed:
	sljit_free_compiler(C);
	return code;
}

/* function prototype of bf compiled code */
typedef void (*bf_entry_t)(void);

int main(int argc, char **argv)
{
	void *code;
	bf_entry_t entry;
	FILE *fp;

	if (argc < 2) {
		fprintf(stderr, "Usage: %s <brainfuck program>\n", argv[0]);
		return -1;
	}

	fp = fopen(argv[1], "rb");
	if (!fp) {
		perror("open");
		return -1;
	}

	code = compile(fp, NULL);
	fclose(fp);

	if (!code) {
		fprintf(stderr, "[Fatal]: Compile failed\n");
		return -1;
	}

	entry = (bf_entry_t)code;
	entry();

	sljit_free_code(code);
	return 0;
}