/*
* Wierd Interpreter:
*
* Wierd Language developed by Chris Pressey, August 1997
* Interpreter written 05 August 1997 by John Colagioia
*
* Deviations from the "Official" Wierd:
* Direction: The IP will always try to continue in the same
* direction (or as close as possible). When two
* equally-likely possibilities exist, it will choose
* the "leftmost" branch.
* Conditionals: When the IP connects to a 90-degree angle,
* it pops the stack. If the result is zero, it
* continues as if nothing interesting happens. If
* nonzero, it reverses the IP direction.
* Gap-Sparking: If the IP has just "sparked into" a
* location which is isolated, the program is
* considered erroneous, as the IP direction is
* undefined at that time.
*
* Revision History:
* R#: Date: Inits: Reason:
* 0 05aug97 jnc Origination
* 1 06aug97 jnc Various Bugfixes, Revised Conditionals
* 2 07aug97 jnc Added Multithreading, Revised Conditionals
* 3 08aug97 jnc Added "Gap-Sparking"
* 4 08aug97 jnc General Cleanup and Bugfixes
*
* To Do:
* -- Heavier testing (requires writing Wierd code...).
* -- Add a tty or graphical display routine.
*
*/
/*** Preprocessor Directives ***/
/* Included header files */
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
/* Constants and Macros */
#define SIZE 128
/*** Data Structures ***/
struct iplist /* An instruction pointer */
{
int ipid; /* A unique identifier */
int x; /* The current ordinate value */
int y; /* The current abscissa value */
int dx; /* The next change in x to be applied */
int dy; /* The next change in y to be applied */
int stack[SIZE]; /* A stack exclusive to this IP */
int s_top; /* A pointer to the stack top */
struct iplist *next; /* The next IP available */
};
/*** Function Prototypes (only for the function table below) ***/
int nop (struct iplist **);
int push1 (struct iplist **);
int subtract (struct iplist **);
int condition (struct iplist **);
int getput (struct iplist **);
int inputoutput (struct iplist **);
int terminus (struct iplist **);
/*** more prototypes, because my compiler likes them - cap */
int turn45 (int * xdir, int * ydir);
int getnextturn (int x, int y, int * dx, int * dy);
/*** Global Variables ***/
char workspace[SIZE][SIZE]; /* The "Wierd memory space" */
int tmpx, tmpy, /* temporary deltas */
ipid = 0, ip_killed; /* IP identifier, kill flag */
struct iplist *list; /* The list of IPs */
int (*function[])(struct iplist **) =
{ /* Function table */
nop, /* 0 degrees */
push1, /* 45 degrees */
condition, /* 90 degrees */
getput, /* 135 degrees */
terminus, /* 180 degrees */
inputoutput, /* 225 degrees */
condition, /* 270 degrees */
subtract /* 315 degrees */
};
/*** Source code for Interpreter Functions ***/
/* Function main():
* Initializes data structures and environment, and iterates through
* each IP until termination. Also handles most common errors.
*/
int main (int argc, char *argv[])
{
int i, x, y; /* Temporary variables */
FILE *infile; /* Input file */
if (argc < 2) /* Not enough arguments--don't know what to do */
{
fprintf (stderr, "Error:\n\t%s <Wierd Filename>\n", argv[0]);
exit (1);
}
infile = fopen (argv[1], "r");
if (infile == NULL) /* Bad input filename given */
{
fprintf (stderr, "Error: Invalid Wierd filename: \"%s\".\n",
argv[1]);
exit (2);
}
for (x=0;x<SIZE;++x) /* Clear the memoryspace */
for (y=0;y<SIZE;++y)
workspace[x][y] = '\000';
y = 1; /* Read the file into the memoryspace */
while (!feof (infile))
{
fscanf (infile, "%[^\n]", &workspace[y][1]);
fgetc (infile);
#ifdef DEBUG
printf ("%s\n", &workspace[y][1]);
#endif
++y;
}
fclose (infile); /* Clean up file handles */
for (x=0;x<SIZE;++x) /* Convert nulls to spaces */
for (y=0;y<SIZE;++y)
if (workspace[x][y] == '\000')
workspace[x][y] = ' ';
/* Initialize the first IP */
list = (struct iplist *) malloc (sizeof (struct iplist));
list->x = list->y = list->dx = list->dy = 1;
list->s_top = 0;
list->next = list;
list->ipid = ++ipid;
/* Loop as long as the location is valid */
while (workspace[list->x][list->y] != ' ')
{
ip_killed = 0; /* Initialize the kill-flag */
#ifdef DEBUG
printf ("<%d>\t", list->ipid);
printf ("(%d,%d)\t", list->y, list->x);
for (i=0;i<list->s_top;++i)
printf ("[%d] ", list->stack[i]);
#endif
tmpx = list->dx; /* Save the current direction */
tmpy = list->dy; /* and change it */
i = getnextturn (list->x, list->y, &tmpx, &tmpy);
#ifdef DEBUG
printf ("\t\t%d\n", i);
#endif
if (i % 45) /* Invalid direction! */
printf ("\007ERROR!!\007\n");
else { /* Call the appropriate function */
i = function[i/45](&list);
if (i == -1) /* Out of IPs */
{
free (list);
return 0;
}
}
if (!ip_killed) /* Only update if it's the same IP */
{
list->x += list->dx = tmpx; /* Update location */
list->y += list->dy = tmpy;
list = list->next; /* Next IP */
}
}
#ifdef DEBUG
printf ("Program ungracefully terminated!\n");
#endif
return 0;
}
/* Function checkdir():
* Simple function to determine validity of location a given delta
* from the given location.
*/
int checkdir (int x, int y, int dx, int dy)
{
return (workspace[x+dx][y+dy] != ' '); /* Only space is invalid */
}
/* Function rotate():
* Turns an IP the specified number of degrees (though only in 45-
* degree increments).
*/
int rotate (int * xdir, int * ydir, int turn)
{
int i;
for (i=0;i<turn;i+=45) /* We only work in 45-degree increments */
turn45 (xdir, ydir);
return 0;
}
/* Function turn45():
* Rotates a dx,dy heading 45 degrees clockwise. Very unclean
* implementation, but it works for now. Once we expand beyond two
* dimensions, though, this will have to be heavily rewritten.
*/
int turn45 (int * xdir, int * ydir)
{
if (*ydir == 1 && *xdir == -1 || *ydir == -1 && *xdir == 1)
*ydir = 0;
else if (*xdir == 1 && *ydir == 1 || *xdir == -1 && *ydir == -1)
*xdir = 0;
else if (*ydir)
*xdir -= *ydir;
else *ydir += *xdir;
return 0;
}
/* Function getnextturn():
* Checks the 7 of the 8 valid directions from the given point,
* choosing those 7 based on the IP delta. Returns the "leftmost"
* direction closest to "straight" that is available from the given
* location.
*/
int getnextturn (int x, int y, int * dx, int * dy)
{
if (checkdir (x, y, *dx, *dy))
return 0;
rotate (dx, dy, 45);
if (checkdir (x, y, *dx, *dy))
return 45;
rotate (dx, dy, 270);
if (checkdir (x, y, *dx, *dy))
return 315;
rotate (dx, dy, 135);
if (checkdir (x, y, *dx, *dy))
return 90;
rotate (dx, dy, 180);
if (checkdir (x, y, *dx, *dy))
return 270;
rotate (dx, dy, 225);
if (checkdir (x, y, *dx, *dy))
return 135;
rotate (dx, dy, 90);
if (checkdir (x, y, *dx, *dy))
return 225;
return 180;
}
/* Function add_thread():
* Inserts a node on the circular linked list of IPs, and initializes
* the node as a new IP.
*/
int add_thread (struct iplist * ip, int dx, int dy)
{
struct iplist *temp;
int i;
/* Create new node on list */
temp = (struct iplist *) malloc (sizeof (struct iplist));
temp->ipid = ++ipid; /* Give an identifier */
temp->next = ip->next; /* Insert into list */
temp->x = ip->x - dx; /* Initialize based on current IP */
temp->y = ip->y - dy;
temp->dx = - dx;
temp->dy = - dy;
temp->s_top = ip->s_top;
for (i=0;i<ip->s_top;++i)
temp->stack[i] = ip->stack[i];
ip->next = temp;
#ifdef DEBUG
printf ("Thread #%d created.\n", temp->ipid);
#endif
return 0;
}
/* Function kill_thread():
* Removes the current node from the circular linked list of IPs.
*/
int kill_thread (struct iplist ** ip)
{
struct iplist *temp;
#ifdef DEBUG
int id;
id = (*ip)->ipid;
#endif
temp = *ip;
while (temp->next != *ip) /* Get IP before this one */
temp = temp->next;
temp->next = (*ip)->next; /* Point around the current IP */
free (*ip); /* Deallocate the IP */
*ip = temp; /* Return the previous one */
#ifdef DEBUG
printf ("Thread #%d destroyed, passing to #%d.\n", id, (*ip)->ipid);
#endif
return 0;
}
/* Function find_far():
* Called when the IP has no obvious place to go. Checks the region
* around (7x7 locations) the current IP location for a "closest
* point" based on the current location as well as the current IP
* direction.
*/
int find_far (int x, int y, int dx, int dy, int **xcoors, int **ycoors)
{
int i, j, pts, xs[40], ys[40], ti, tj,
a[] = {2, 3, -2, -3, 0, 1, -1}; /* Order of precedence */
pts = 0;
for (i=0;i<7;++i) for (j=0;j<7;++j)
/* Scan along the array in two dimensions */
if (i < 4 || j < 4) /* If at least one index looks at {2,3} */
{
ti = dx>0?a[i]:-a[i]; /* Invert if a delta is */
tj = dy>0?a[j]:-a[j]; /* negative */
if (x>a[i] && y>a[j] &&
workspace[x+ti][y+tj] != ' ')
{ /* If the location exists and isn't */
xs[pts] = x + ti; /* a space */
ys[pts] = y + tj; /* Add to list */
if (xs[pts] > 0 && ys[pts] > 0)
++ pts;
}
}
*xcoors = (int *) malloc (sizeof (int) * pts);
*ycoors = (int *) malloc (sizeof (int) * pts);
for (i=0;i<pts;++i) /* Copy the list of candidates to where the */
{ /* calling function suggests */
(*xcoors)[i] = xs[i];
(*ycoors)[i] = ys[i];
}
return (pts); /* Return the number of points found */
}
/*** Source Code for internal Interpreter Operations (called from the
function table only ***/
/* Function nop():
* No-operation.
*/
int nop (struct iplist ** list)
{
return 0; /* Self-explanatory */
}
/* Function push1():
* Pushes a constant value 1 onto the IP's stack.
*/
int push1 (struct iplist ** ip)
{
struct iplist *list = *ip;
list->stack[list->s_top++] = 1; /* Self-explanatory */
return 0;
}
/* Function condition():
* If the top of the IP's stack is zero, functions as nop().
* Otherwise, it reverses the direction of the IP.
*/
int condition (struct iplist ** ip)
{
int i;
struct iplist *list = *ip;
/* Two coincident 90-degree turns spawns a new IP */
if (workspace[list->x-tmpx][list->y-tmpy] != ' ')
add_thread (list, tmpx, tmpy);
/* Otherwise, check top of the stack determines whether */
/* we continue or change direction */
else if (list->s_top && list->stack[--list->s_top])
{
list->x += tmpx;
list->y += tmpy;
i = tmpx; /* Reflect the IP */
tmpx = -tmpy;
tmpy = -i;
i = getnextturn (list->x, list->y, &tmpx, &tmpy);
#ifdef DEBUG
printf ("<%d>\t", list->ipid);
printf ("(%d,%d)\t", list->y, list->x);
for (i=0;i<list->s_top;++i)
printf ("[%d] ", list->stack[i]);
printf ("\t\t%d\n", i);
#endif
}
*ip = list; /* Fix the IP list in case the current thread changed */
return 0;
}
/* Function getput():
* If the top of the stack is zero, retrieves the byte stored at the
* coordinates specified on the stack. Otherwise, takes the element
* on the stack beneath the coordinates and stores the value at those
* coordinates.
*/
int getput (struct iplist ** ip)
{
int xcoor, ycoor;
struct iplist *list = *ip;
if (list->s_top < 3) /* Not enough stack elements to do anything */
return 1;
if (list->stack[--list->s_top]) /* A non-zero is a "put" */
{
xcoor = list->stack[--list->s_top];
ycoor = list->stack[--list->s_top];
list->stack[list->s_top++] = workspace[xcoor][ycoor];
}
else { /* Otherwise it's a "get" */
xcoor = list->stack[--list->s_top];
ycoor = list->stack[--list->s_top];
workspace[xcoor][ycoor] = list->stack[--list->s_top];
}
return 0;
}
/* Function inputoutput():
* If the top of the stack is zero, gets a character from input.
* Otherwise, it prints the next character on the stack.
*/
int inputoutput (struct iplist ** ip)
{
struct iplist *list = *ip;
if (list->s_top < 1) /* Nothing useful on the stack */
return 1;
if (list->stack[--list->s_top]) /* If it's nonzero, print the next */
putchar (list->stack[--list->s_top]);
/* Otherwise request a character */
else list->stack[list->s_top++] = getchar ();
return 0;
}
/* Function subtract():
* Subtracts the top two stack elements.
*/
int subtract (struct iplist ** ip)
{
struct iplist *list = *ip;
if (list->s_top < 2) /* Can't subtract without two elements */
return 1;
list->stack[list->s_top - 2] -= list->stack[list->s_top - 1];
--list->s_top; /* Otherwise, subtract top from under and pop */
return 0;
}
/* Function terminus():
* Based on current environmental conditions, either sparks the IP
* across the gap, or kills the IP.
*/
int terminus (struct iplist ** ip)
{
int i, j, k, *xlist, *ylist;
struct iplist *list = *ip;
/* Check for a line to spark to */
j = find_far (list->x, list->y, list->dx, list->dy, &xlist, &ylist);
#ifdef DEBUG
for (k=0;k<j;++k)
printf ("\t\t{%d,%d}\n", ylist[k], xlist[k]);
#endif
if (j < 3) /* Less than three means it's probably our */
{ /* incoming path */
if (list->next == list)
return -1; /* so kill the thread */
kill_thread (&list);
ip_killed = 1;
}
else { /* Otherwise, we have valid locations */
list->x = xlist[0]; /* and they *should* be ordered */
list->y = ylist[0]; /* by preference */
i = getnextturn (list->x, list->y, &tmpx, &tmpy);
#ifdef DEBUG
printf ("==> %d choices available.\n", j);
printf ("<%d>\t", list->ipid);
printf ("(%d,%d)\t", list->y, list->x);
for (i=0;i<list->s_top;++i)
printf ("[%d] ", list->stack[i]);
printf ("\t\t%d\n", i);
#endif
}
*ip = list; /* Fix the list pointer in case it was changed */
return 0;
}