Skip to content

Instantly share code, notes, and snippets.

@fis
Last active December 25, 2015 01:59
Show Gist options
  • Save fis/6898996 to your computer and use it in GitHub Desktop.
Save fis/6898996 to your computer and use it in GitHub Desktop.
ff3 - an allegedly speedy Befunge-93 interpreter
/*
* ff3.c - fast befunge-93 interpreter
* (C) 2010 Heikki Kallasjoki <fis@zem.fi>
*
* This is a reasonably fast, reasonably portable (needs GCC, some
* other assumptions) Befunge-93 interpreter. The main crafty trick
* here is that all (well, most) instructions have four
* implementations, specialized to the current delta, leading to a
* single indirect jump per executed instruction.
*
* Compile with something like:
* gcc -o ff3 [opts] ff3.c -Wall -Werror -O3 [other optimilization opts]
*
* Compile-time configuration options, with defaults:
*
* -DBOUNDARY_TRACKING [default undef]
*
* Wrap already at code bounding-box, enlarge as necessary on 'p'.
* Should improve efficiency especially for small programs that wrap
* a lot but don't 'p' much.
*
* -DTRACE [default undef]
*
* Output ip, direction, command and stack for most ticks.
*
* -DUNSAFE_STACK [default undef]
* -DSEGFAULT_STACK [default undef]
*
* With UNSAFE_STACK, do no stack underflow checking; will crash
* badly on programs that rely on popping the empty stack returning
* 0. With SEGFAULT_STACK, do the same except with a segfault
* handler that tries to restore sanity. This bit is rather
* platform-dependent and not portable at all.
*
* -DINTERLEAVED [default undef]
*
* Use the "interleaved" code-space layout. Basically the
* code-space is a three-dimensional grid, of dimensions (PF_X,
* PF_Y, 4), where the third dimension encodes the current delta;
* alternatively, you can think of it so that for each Befunge-93
* playfield cell the code-space holds a set of 4 different pointers
* to opcode implementations, for the four different deltas. In the
* "interleaved" layout, the code-space memory is ordered so that
* for each "pixel" (playfield cell), the four code-pointers are
* stored consecutively. The alternative is a "planar" layout,
* where there are four consecutife PF_X*PF_Y arrays of
* code-pointers.
*
* -DSTACK_SIZE=1024
*
* Stack size; self-evident, I hope.
*
* -DSTACK_TYPE=int
*
* Stack cell data type.
*
* -DPF_X=80 -DPF_Y=25
*
* Playfield size.
*
* -DPF_TYPE='unsigned char'
*
* Playfield cell data type. Note that using something else than
* 'unsigned char' here is not very safe, because the jump table of
* operations has been filled for values between 0 .. 2^CHAR_BIT-1
* only.
*/
#include <errno.h>
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
/* set defaults */
#ifndef STACK_SIZE
#define STACK_SIZE 1024
#endif
#ifndef STACK_TYPE
#define STACK_TYPE int
#endif
#ifndef PF_X
#define PF_X 80
#endif
#ifndef PF_Y
#define PF_Y 25
#endif
#ifndef PF_TYPE
#define PF_TYPE unsigned char
#endif
/* types */
typedef PF_TYPE pf_cell;
typedef STACK_TYPE stack_cell;
/* memory */
#define PF_OFFSET 2
#define PF_W (PF_X+2*PF_OFFSET)
#define PF_H (PF_Y+2*PF_OFFSET)
static pf_cell pf[PF_H*PF_W];
static void *pfcode[4*PF_H*PF_W];
#define PF_POS(x,y) (((y)+PF_OFFSET)*PF_W + (x)+PF_OFFSET)
/* this looks arbitrarily modifiable, but note that I do depend on
* the assumption that PF_DELTA(0,1,0) == PF_W*PF_DELTA(1,0,0) ... */
#ifdef INTERLEAVED
#define PF_DELTA(yd,xd,dd) ((dd)+(xd)*4+(yd)*PF_W*4)
#define SET_OPS(pos,tbl) memcpy(&pfcode[pos*4], (tbl), sizeof *(tbl))
#define IP_LOOKUP(offset,delta) do { \
offset = ip - pfcode; \
delta = offset % 4; \
offset /= 4; \
} while (0)
#else
#define PF_DELTA(yd,xd,dd) ((xd)+(yd)*PF_W+(dd)*PF_H*PF_W)
#define SET_OPS(pos,tbl) do { \
pfcode[pos] = (tbl)[0]; \
pfcode[pos+PF_W*PF_H] = (tbl)[1]; \
pfcode[pos+2*PF_W*PF_H] = (tbl)[2]; \
pfcode[pos+3*PF_W*PF_H] = (tbl)[3]; \
} while (0)
#define IP_LOOKUP(offset,delta) do { \
offset = ip - pfcode; \
delta = offset / (PF_W*PF_H); \
offset %= PF_W*PF_H; \
} while (0)
#endif
static void *ops[1 << CHAR_BIT][4];
static void *wrap_ops[4];
static void **ip;
#define IP_GOTO do { trace(); goto **ip; } while (0)
#ifdef BOUNDARY_TRACKING
static stack_cell pf_box_w = 0, pf_box_h = 0;
static inline void make_wall(int x0, int y0, int len, int delta, int pfdelta, void *op)
{
void **pc;
pc = &pfcode[PF_DELTA(PF_OFFSET+y0, PF_OFFSET+x0, delta)];
for (; len > 0; len--, pc += pfdelta)
*pc = op;
}
static void move_wall(stack_cell x, stack_cell y);
#define BOUNDARY_TRACK(x,y) do { if ((x) >= pf_box_w || (y) >= pf_box_h) move_wall(x, y); } while(0)
#else
#define pf_box_w PF_X
#define pf_box_h PF_Y
#define BOUNDARY_TRACK(x,y) /* no-op */
#endif
#if defined(SEGFAULT_STACK)
# error "SEGFAULT_STACK not implemented yet"
#elif defined(UNSAFE_STACK)
static stack_cell stack[STACK_SIZE] = {0};
#define STACK_BASE (&stack[0])
static stack_cell *top = STACK_BASE;
#define STACK_CHECK_POPS (void)0
#define STACK_CHECK_UNOP (void)0
#define STACK_CHECK_BINOP (void)0
#else
/* the three zeroes below are so that we can do stack-fixup after op */
static stack_cell stack[STACK_SIZE+3] = {0};
#define STACK_BASE (&stack[3])
static stack_cell *top = STACK_BASE;
#define STACK_CHECK_POPS do { \
if (top < STACK_BASE) top = STACK_BASE; \
} while (0)
#define STACK_CHECK_UNOP do { \
if (top == STACK_BASE) { \
*STACK_BASE = STACK_BASE[-1]; \
STACK_BASE[-1] = 0; \
top = STACK_BASE+1; \
} \
} while (0)
#define STACK_CHECK_BINOP do { \
if (top <= STACK_BASE) { \
*STACK_BASE = top[-1]; \
top[-1] = 0; \
top = STACK_BASE+1; \
} \
} while (0)
#endif
/* tracing support */
#ifdef TRACE
static void trace(void);
#else
#define trace() (void)0
#endif
/* initialization and main code */
static void run(void);
int main(int argc, char *argv[])
{
FILE *f;
size_t s;
if (argc != 2)
{
fprintf(stderr, "usage: %s file.b93\n", argc > 0 ? argv[0] : "ff3");
return EXIT_FAILURE;
}
/* load file */
if (sizeof *pf == 1)
memset(pf, 32, sizeof pf);
else
{
for (s = 0; s < sizeof pf / sizeof *pf; s++)
pf[s] = 32;
}
f = fopen(argv[1], "r");
if (!f)
{
fprintf(stderr, "can't read program: %s: %s\n", argv[1], strerror(errno));
return EXIT_FAILURE;
}
{
char buf[PF_X+2];
int skip_next = 0;
int x, y;
for (y = 0; y < PF_Y && fgets(buf, PF_X+2, f);)
{
if (skip_next)
x = strlen(buf)-1;
else
{
for (x = 0; x < PF_X && buf[x] && buf[x] != '\n'; x++)
pf[PF_POS(x,y)] = buf[x];
y++;
#ifdef BOUNDARY_TRACKING
if (x > pf_box_w) pf_box_w = x;
if (y > pf_box_h) pf_box_h = y;
#endif
}
skip_next = buf[x] != '\n';
}
}
fclose(f);
/* do the deed */
srand(time(0));
run();
return EXIT_SUCCESS;
}
/* actual interpreter part */
static void push_string(void);
static stack_cell read_number(void);
void run(void)
{
int i, j;
/* initialize the instruction set tables */
i = 0;
for (; i < (1 << CHAR_BIT); i++)
{
ops[i][0] = &&op_nop_left;
ops[i][1] = &&op_nop_right;
ops[i][2] = &&op_nop_up;
ops[i][3] = &&op_nop_down;
}
#define fill(tbl,d,suf) do { \
tbl['?'][d] = &&op_rand; tbl['@'][d] = &&op_exit; \
tbl['<'][d] = &&op_goleft##suf; tbl['>'][d] = &&op_goright##suf; \
tbl['^'][d] = &&op_goup##suf; tbl['v'][d] = &&op_godown##suf; \
tbl['_'][d] = &&op_if_h##suf; tbl['|'][d] = &&op_if_v##suf; \
tbl['#'][d] = &&op_skip##suf; tbl['"'][d] = &&op_str##suf; tbl['0'][d] = &&op_n0##suf; \
tbl['1'][d] = &&op_n1##suf; tbl['2'][d] = &&op_n2##suf; tbl['3'][d] = &&op_n3##suf; \
tbl['4'][d] = &&op_n4##suf; tbl['5'][d] = &&op_n5##suf; tbl['6'][d] = &&op_n6##suf; \
tbl['7'][d] = &&op_n7##suf; tbl['8'][d] = &&op_n8##suf; tbl['9'][d] = &&op_n9##suf; \
tbl[':'][d] = &&op_dup##suf; tbl['\\'][d] = &&op_swap##suf; tbl['$'][d] = &&op_drop##suf; \
tbl['+'][d] = &&op_add##suf; tbl['-'][d] = &&op_sub##suf; tbl['*'][d] = &&op_mul##suf; \
tbl['/'][d] = &&op_div##suf; tbl['%'][d] = &&op_mod##suf; \
tbl['!'][d] = &&op_not##suf; tbl['`'][d] = &&op_gt##suf; \
tbl['g'][d] = &&op_get##suf; tbl['p'][d] = &&op_put##suf; \
tbl['.'][d] = &&op_out_n##suf; tbl[','][d] = &&op_out_c##suf; \
tbl['&'][d] = &&op_in_n##suf; tbl['~'][d] = &&op_in_c##suf; \
} while (0)
fill(ops, 0, _left);
fill(ops, 1, _right);
fill(ops, 2, _up);
fill(ops, 3, _down);
#undef fill
wrap_ops[0] = &&op_wrap_west;
wrap_ops[1] = &&op_wrap_east;
wrap_ops[2] = &&op_wrap_north;
wrap_ops[3] = &&op_wrap_south;
/* copy the code to the pf_code array, set up the borders */
{
void **pc = pfcode;
pf_cell *p = pf;
for (i = 0; i < PF_OFFSET * PF_W; i++)
{
pc[PF_DELTA(0,0,2)] = &&op_wrap_north;
pc += PF_DELTA(0,1,0);
p++;
}
for (i = 1; i <= PF_Y; i++)
{
for (j = 0; j < PF_OFFSET; j++)
{
pc[PF_DELTA(0,0,0)] = &&op_wrap_west;
pc += PF_DELTA(0,1,0);
p++;
}
for (j = 1; j <= PF_X; j++)
#ifdef INTERLEAVED
{
memcpy(pc, ops[*p++], sizeof *ops);
pc += PF_DELTA(0,1,0);
}
#else
{
pc[PF_DELTA(0,0,0)] = ops[*p][0];
pc[PF_DELTA(0,0,1)] = ops[*p][1];
pc[PF_DELTA(0,0,2)] = ops[*p][2];
pc[PF_DELTA(0,0,3)] = ops[*p][3];
pc += PF_DELTA(0,1,0);
p++;
}
#endif
for (j = 0; j < PF_OFFSET; j++)
{
pc[PF_DELTA(0,0,1)] = &&op_wrap_east;
pc += PF_DELTA(0,1,0);
p++;
}
}
for (i = 0; i < PF_OFFSET * PF_W; i++)
{
pc[PF_DELTA(0,0,3)] = &&op_wrap_south;
pc += PF_DELTA(0,1,0);
p++;
}
}
#ifdef BOUNDARY_TRACKING
if (pf_box_w < PF_X) make_wall(pf_box_w, 0, pf_box_h, 1, PF_DELTA(1, 0, 0), wrap_ops[1]);
if (pf_box_w < PF_X-1) make_wall(pf_box_w+1, 0, pf_box_h, 1, PF_DELTA(1, 0, 0), wrap_ops[1]);
if (pf_box_h < PF_Y) make_wall(0, pf_box_h, pf_box_w, 3, PF_DELTA(0, 1, 0), wrap_ops[3]);
if (pf_box_h < PF_Y-1) make_wall(0, pf_box_h+1, pf_box_w, 3, PF_DELTA(0, 1, 0), wrap_ops[3]);
#endif
/* start to execute from (0,0) with delta=right */
ip = &pfcode[PF_DELTA(PF_OFFSET, PF_OFFSET, 1)];
IP_GOTO;
/* instruction set definition */
#define MOVE_LEFT ip += PF_DELTA(0,-1,0)
#define MOVE_RIGHT ip += PF_DELTA(0,1,0)
#define MOVE_UP ip += PF_DELTA(-1,0,0)
#define MOVE_DOWN ip += PF_DELTA(1,0,0)
#define NEXT_LEFT do { MOVE_LEFT; IP_GOTO; } while (0)
#define NEXT_RIGHT do { MOVE_RIGHT; IP_GOTO; } while (0)
#define NEXT_UP do { MOVE_UP; IP_GOTO; } while (0)
#define NEXT_DOWN do { MOVE_DOWN; IP_GOTO; } while (0)
#ifdef INTERLEAVED
#define TURN(x) do { \
ip -= (ip - pfcode) % 4; \
ip += x; \
} while (0)
#else
#define TURN(x) do { \
ip = pfcode + ((ip - pfcode) % (PF_W*PF_H)); \
ip += x*PF_W*PF_H; \
} while (0)
#endif
op_wrap_west:
ip += PF_DELTA(0, pf_box_w, 0); IP_GOTO;
op_wrap_east:
ip += PF_DELTA(0, -pf_box_w, 0); IP_GOTO;
op_wrap_north:
ip += PF_DELTA(pf_box_h, 0, 0); IP_GOTO;
op_wrap_south:
ip += PF_DELTA(-pf_box_h, 0, 0); IP_GOTO;
op_goleft_left: ip += PF_DELTA(0, -1, 0); IP_GOTO;
op_goleft_right: ip += PF_DELTA(0, -1, -1); IP_GOTO;
op_goleft_up: ip += PF_DELTA(0, -1, -2); IP_GOTO;
op_goleft_down: ip += PF_DELTA(0, -1, -3); IP_GOTO;
op_goright_left: ip += PF_DELTA(0, 1, 1); IP_GOTO;
op_goright_right: ip += PF_DELTA(0, 1, 0); IP_GOTO;
op_goright_up: ip += PF_DELTA(0, 1, -1); IP_GOTO;
op_goright_down: ip += PF_DELTA(0, 1, -2); IP_GOTO;
op_goup_left: ip += PF_DELTA(-1, 0, 2); IP_GOTO;
op_goup_right: ip += PF_DELTA(-1, 0, 1); IP_GOTO;
op_goup_up: ip += PF_DELTA(-1, 0, 0); IP_GOTO;
op_goup_down: ip += PF_DELTA(-1, 0, -1); IP_GOTO;
op_godown_left: ip += PF_DELTA(1, 0, 3); IP_GOTO;
op_godown_right: ip += PF_DELTA(1, 0, 2); IP_GOTO;
op_godown_up: ip += PF_DELTA(1, 0, 1); IP_GOTO;
op_godown_down: ip += PF_DELTA(1, 0, 0); IP_GOTO;
#define ifinsts(d,suf) \
op_if_h##suf: \
{ \
stack_cell t = *--top; STACK_CHECK_POPS; \
if (t) { ip += PF_DELTA(0, -1, 0-d); IP_GOTO; } \
else { ip += PF_DELTA(0, 1, 1-d); IP_GOTO; } \
} \
op_if_v##suf: \
{ \
stack_cell t = *--top; STACK_CHECK_POPS; \
if (t) { ip += PF_DELTA(-1, 0, 2-d); IP_GOTO; } \
else { ip += PF_DELTA(1, 0, 3-d); IP_GOTO; } \
}
ifinsts(0,_left);
ifinsts(1,_right);
ifinsts(2,_up);
ifinsts(3,_down);
op_rand: /* this could be directional too, but it's messy */
{
int t = rand() % 4;
if (t == 0) { TURN(0); NEXT_LEFT; }
else if (t == 1) { TURN(1); NEXT_RIGHT; }
else if (t == 2) { TURN(2); NEXT_UP; }
else { TURN(3); NEXT_DOWN; }
}
op_exit:
return;
#define insts(move,next,suf) \
op_nop##suf: \
next; \
op_skip##suf: \
move; next; \
op_str##suf: \
push_string(); \
next; \
op_dup##suf: \
*top = *(top-1); \
top++; \
next; \
op_swap##suf: \
{ \
stack_cell a = *--top; \
stack_cell b = *--top; \
STACK_CHECK_POPS; \
*top++ = a; \
*top++ = b; \
next; \
} \
op_drop##suf: \
--top; STACK_CHECK_POPS; \
next; \
op_add##suf: \
top[-2] += top[-1]; \
top--; \
STACK_CHECK_BINOP; \
next; \
op_sub##suf: \
top[-2] -= top[-1]; \
top--; \
STACK_CHECK_BINOP; \
next; \
op_mul##suf: \
top[-2] *= top[-1]; \
top--; \
STACK_CHECK_BINOP; \
next; \
op_div##suf: \
top[-2] /= top[-1]; \
top--; \
STACK_CHECK_BINOP; \
next; \
op_mod##suf: \
top[-2] %= top[-1]; \
top--; \
STACK_CHECK_BINOP; \
next; \
op_not##suf: \
top[-1] = !top[-1]; \
STACK_CHECK_UNOP; \
next; \
op_gt##suf: \
top[-2] = top[-2] > top[-1]; \
top--; \
STACK_CHECK_BINOP; \
next; \
op_get##suf: \
top[-2] = pf[PF_POS(top[-2], top[-1])]; \
top--; \
STACK_CHECK_BINOP; \
next; \
op_put##suf: \
{ \
stack_cell x = top[-2], y = top[-1]; \
int pos = PF_POS(x, y); \
pf_cell val = top[-3]; \
BOUNDARY_TRACK(x, y); \
pf[pos] = val; \
SET_OPS(pos, ops[val]); \
} \
top -= 3; \
STACK_CHECK_POPS; \
next; \
op_out_n##suf: \
top--; \
printf("%d ", (int)*top); \
STACK_CHECK_POPS; \
next; \
op_out_c##suf: \
top--; \
putchar(*top); \
STACK_CHECK_POPS; \
next; \
op_in_n##suf: \
*top++ = read_number(); \
next; \
op_in_c##suf: \
*top++ = getchar(); \
next; \
op_n0##suf: *top++ = 0; next; \
op_n1##suf: *top++ = 1; next; \
op_n2##suf: *top++ = 2; next; \
op_n3##suf: *top++ = 3; next; \
op_n4##suf: *top++ = 4; next; \
op_n5##suf: *top++ = 5; next; \
op_n6##suf: *top++ = 6; next; \
op_n7##suf: *top++ = 7; next; \
op_n8##suf: *top++ = 8; next; \
op_n9##suf: *top++ = 9; next
insts(MOVE_LEFT, NEXT_LEFT, _left);
insts(MOVE_RIGHT, NEXT_RIGHT, _right);
insts(MOVE_UP, NEXT_UP, _up);
insts(MOVE_DOWN, NEXT_DOWN, _down);
return;
}
stack_cell read_number(void)
{
int c;
stack_cell value = 0;
while ((c = getc(stdin)) >= '0' && c <= '9')
value = value*10 + (c - '0');
if (c > 0)
ungetc(c, stdin);
return value;
}
void push_string(void)
{
int ip_off, delta;
IP_LOOKUP(ip_off, delta);
int ip_x = ip_off % PF_W;
int ip_y = ip_off / PF_W;
int dx = delta > 0 ? delta > 1 ? 0 : 1 : -1;
int dy = delta < 3 ? delta < 2 ? 0 : -1 : 1;
while (1)
{
pf_cell t;
ip_x += dx;
if (ip_x < PF_OFFSET) ip_x += PF_W; else if (ip_x >= PF_X+PF_OFFSET) ip_x -= PF_W;
ip_y += dy;
if (ip_y < PF_OFFSET) ip_y += PF_H; else if (ip_y >= PF_Y+PF_OFFSET) ip_y -= PF_H;
if ((t = pf[ip_y*PF_W + ip_x]) == '"')
break;
*top++ = t;
}
ip = pfcode + PF_DELTA(ip_y, ip_x, delta);
}
#ifdef BOUNDARY_TRACKING
void move_wall(stack_cell x, stack_cell y)
{
void **pc;
int i;
if (pf_box_w < PF_X) make_wall(pf_box_w, 0, pf_box_h, 1, PF_DELTA(1, 0, 0), ops[32][1]);
if (pf_box_w < PF_X-1) make_wall(pf_box_w+1, 0, pf_box_h, 1, PF_DELTA(1, 0, 0), ops[32][1]);
if (pf_box_h < PF_Y) make_wall(0, pf_box_h, pf_box_w, 3, PF_DELTA(0, 1, 0), ops[32][3]);
if (pf_box_h < PF_Y-1) make_wall(0, pf_box_h+1, pf_box_w, 3, PF_DELTA(0, 1, 0), ops[32][3]);
if (x >= pf_box_w) pf_box_w = x+1;
if (y >= pf_box_h) pf_box_h = y+1;
if (pf_box_w < PF_X) make_wall(pf_box_w, 0, pf_box_h, 1, PF_DELTA(1, 0, 0), wrap_ops[1]);
if (pf_box_w < PF_X-1) make_wall(pf_box_w+1, 0, pf_box_h, 1, PF_DELTA(1, 0, 0), wrap_ops[1]);
if (pf_box_h < PF_Y) make_wall(0, pf_box_h, pf_box_w, 3, PF_DELTA(0, 1, 0), wrap_ops[3]);
if (pf_box_h < PF_Y-1) make_wall(0, pf_box_h+1, pf_box_w, 3, PF_DELTA(0, 1, 0), wrap_ops[3]);
}
#endif
#ifdef TRACE
void trace(void)
{
stack_cell *p = top;
int ip_off, delta;
IP_LOOKUP(ip_off, delta);
if (delta == 0) delta = '<';
else if (delta == 1) delta = '>';
else if (delta == 2) delta = '^';
else delta = 'v';
int ip_x = ip_off % PF_W - PF_OFFSET;
int ip_y = ip_off / PF_W - PF_OFFSET;
fprintf(stderr, "%p/%d ", (void *)ip, (int)(ip-pfcode));
if (ip_x < 0)
fprintf(stderr, "(-,%d)%c: >wrap: stack", ip_y, delta);
else if (ip_x >= PF_X)
fprintf(stderr, "(+,%d)%c: <wrap: stack", ip_y, delta);
else if (ip_y < 0)
fprintf(stderr, "(%d,-)%c: vwrap: stack", ip_x, delta);
else if (ip_y >= PF_Y)
fprintf(stderr, "(%d,+)%c: ^wrap: stack", ip_x, delta);
else
fprintf(stderr, "(%d,%d)%c: %c (%d): stack", ip_x, ip_y, delta,
pf[PF_POS(ip_x, ip_y)], pf[PF_POS(ip_x, ip_y)]);
while (p > STACK_BASE && top-p < 10)
fprintf(stderr, " %d", *--p);
if (p > STACK_BASE)
fprintf(stderr, " ...");
fputc('\n', stderr);
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment