/* * A simple register machine, based on the description of Alexander * Asteroth and Christel Baier in their book 'Theoretische Informatik' * p. 18. Note that the implementation differs from the description * in the book in the way, that i only have one set of registers where * code and data is stored ;) * * Copyright (C) 2005 Marcus Fritzsch * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2, or (at your option) * any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software Foundation, * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ /* * Description * ----------- * * This is a model of a simplistic register machine. The whole memory * consists of lots of registers (by defaulz 65535), of which the regular * memory starts at index 1 and index 0 represents the accumulator. * * Each operation stores it's result in the accumulator which is also * the first operand to most operations. * * * Commands * -------- * * LOAD x c(0) := v(x); b++ * * STORE i c(i) := c(0); b++ * STORE *i IF c(i) >= 1 * THEN c(c(i)) := c(0); b++ * ELSE b := INFINITY (* program aborts *) * FI * * ADD x c(0) += v(x); b++ * * SUB x c(0) -= v(x); b++ * * MUL x c(0) *= v(x); b++ * * DIV x IF c(x) > 0 * THEN c(0) /= v(x); b++ * ELSE b := INFINITY (* program aborts *) * FI * * MOD x IF c(x) > 0 * THEN c(0) %= v(x); b++ * ELSE b := INFINITY (* program aborts *) * FI * * GOTO j b := j * * JZERO j IF c(0) == 0 THEN b := j ELSE b++ FI * * END b := INFINITY * * * Symbols * ------- * * v(x) = { * x if operand is immediate (#x) * c(x) if operand is direct (x) * c(c(x)) if operand is indirect (*x) * } * * c(x) = value of register x * * b = program counter, on program start = 1 * * * Compilation and usage * ----------- * To compile use the following command * * cc -O rm.c -o rm * * To run the machine, use: * * ./rm [program] * * If no program is given, try loading 'prg.rm' */ /* sample program, collatz.rm - prints the collatz sequence starting * ----------- * load #27 * print * store 100 * mod #2 * jzero 10 * load 100 * mul #3 * add #1 * goto 12 * load 100 * div #2 * print * store 101 * sub #1 * jzero 18 * load 101 * goto 3 * end * ----------- */ #include #include #include #include #include #include /* #define DEBUG */ typedef enum Eoperator { LOAD, /* load operand into c(0) */ STORE, /* store c(0) to register of operand */ ADD, /* add operand to c(0) */ SUB, /* sub operand from c(0) */ MUL, /* mul operand with c(0) */ DIV, /* div c(0) by operand */ PRINT, /* print c(operand) */ END, /* end program */ GOTO, /* uncoditional jump, b = operand */ JZERO, /* jump if c(0) == 0: b = operand */ MOD, /* mod c(0) by operand */ NONE } operator; typedef enum Eoptype { NOOP, IMMED, /* #1 -> value is 1 */ DIRECT, /* 1 -> value is c(1) */ INDIRECT /* *1 -> value is c(c(1)) */ } optype; typedef struct Sregister { operator op; optype type; int val; } Register; #define MEMSIZE 0xffff typedef struct Smachine { Register c [MEMSIZE + 1]; int b; /* program counter */ } machine; void loadProgram (char * prgFile, machine * mach) { int i = 0, curr = 0; FILE * in; /* init states */ mach->b = 0; for (i = 0; i < MEMSIZE; i++) { mach->c [i].op = NONE; mach->c [i].type = NOOP; mach->c [i].val = 0; } /* do the nasty file thing... */ in = fopen (prgFile, "r"); if (! in) { fprintf (stderr, "RM: open (%s) failed: %s\n", prgFile, strerror (errno)); return; } while (! feof (in)) { char line [100], *ntok, *t, *tline; t = tline = &line [0]; ++curr; fgets (line, 100, in); /* handle comments... */ if (line [0] == '#') continue; while ((ntok = strtok (tline, "\n\v \t"))) { tline = 0; if (mach->c [curr].op != NONE) { int tlen = strlen (ntok); /* token len */ if (tlen) { if (ntok [0] == '#') /* immediate */ mach->c [curr].val = atoi (ntok + 1), mach->c [curr].type = IMMED; else if (ntok [0] == '*') /* indirect */ mach->c [curr].val = atoi (ntok + 1), mach->c [curr].type = INDIRECT; else if (isdigit (ntok [0])) /* direct */ mach->c [curr].val = atoi (ntok), mach->c [curr].type = DIRECT; else { fprintf (stderr, "RM: token error on line %d\n", curr); exit (1); } } continue; } if (! strcasecmp (ntok, "end")) mach->c [curr].op = END; else if (! strcasecmp (ntok, "load")) mach->c [curr].op = LOAD; else if (! strcasecmp (ntok, "store")) mach->c [curr].op = STORE; else if (! strcasecmp (ntok, "add")) mach->c [curr].op = ADD; else if (! strcasecmp (ntok, "sub")) mach->c [curr].op = SUB; else if (! strcasecmp (ntok, "mul")) mach->c [curr].op = MUL; else if (! strcasecmp (ntok, "div")) mach->c [curr].op = DIV; else if (! strcasecmp (ntok, "print")) mach->c [curr].op = PRINT; else if (! strcasecmp (ntok, "goto")) mach->c [curr].op = GOTO; else if (! strcasecmp (ntok, "jzero")) mach->c [curr].op = JZERO; else if (! strcasecmp (ntok, "mod")) mach->c [curr].op = MOD; else { fprintf (stderr, "RM: syntax error on line %d\n", curr); exit (1); } } } } int getOp (machine * mach) { switch (mach->c [mach->b].type) { case NOOP: case IMMED: return mach->c [mach->b].val; case DIRECT: return mach->c [mach->c [mach->b].val].val; case INDIRECT: return mach->c [mach->c [mach->c [mach->b].val].val].val; } return 0; } int runProgram (machine * mach) { int tmp = 0; mach->b = 1; while (mach->b != MEMSIZE) { switch (mach->c [mach->b].op) { case LOAD: if (mach->c [mach->b].type == IMMED) { mach->c [0].val = mach->c [mach->b].val; #ifdef DEBUG printf ("LOAD @%d: %d\n", mach->b, mach->c [0].val); #endif /* DEBUG */ } else { mach->c [0].val = mach->c [mach->c [mach->b].val].val; #ifdef DEBUG printf ("LOAD @%d: %d\n", mach->c [mach->b].val, mach->c [0].val); #endif /* DEBUG */ } ++mach->b; break; case STORE: tmp = mach->c [mach->b].val; if (mach->c [mach->b].type == INDIRECT && tmp < 1) { mach->b = MEMSIZE; printf ("STORE %d ---> ABORT\n", tmp); mach->c [0].val = 1; break; } if (mach->c [mach->b].type == DIRECT) mach->c [tmp].val = mach->c [0].val; else if (mach->c [mach->b].type == INDIRECT) mach->c [mach->c [tmp].val].val = mach->c [0].val; #ifdef DEBUG printf ("STORE %d to @%d\n", mach->c [0].val, mach->c [mach->b].val); #endif /* DEBUG */ ++mach->b; break; case ADD: mach->c [0].val += getOp (mach); #ifdef DEBUG printf ("ADD %d = %d\n", getOp (mach), mach->c [0].val); #endif /* DEBUG */ ++mach->b; break; case SUB: mach->c [0].val -= getOp (mach); if (mach->c [0].val < 0) mach->c [0].val = 0; #ifdef DEBUG printf ("SUB %d = %d\n", getOp (mach), mach->c [0].val); #endif /* DEBUG */ ++mach->b; break; case MUL: mach->c [0].val *= getOp (mach); #ifdef DEBUG printf ("MUL %d = %d\n", getOp (mach), mach->c [0].val); #endif /* DEBUG */ ++mach->b; break; case DIV: tmp = getOp (mach); if (tmp > 0) { mach->c [0].val /= tmp; #ifdef DEBUG printf ("DIV %d = %d\n", tmp, mach->c [0].val); #endif /* DEBUG */ ++mach->b; } else { mach->b = MEMSIZE; printf ("DIV %d ---> ABORT\n", tmp); mach->c [0].val = 1; } break; case MOD: tmp = getOp (mach); if (tmp > 0) { mach->c [0].val %= tmp; #ifdef DEBUG printf ("MOD %d = %d\n", tmp, mach->c [0].val); #endif /* DEBUG */ ++mach->b; } else { mach->b = MEMSIZE; printf ("MOD %d ---> ABORT\n", tmp); mach->c [0].val = 1; } break; case PRINT: #ifdef DEBUG printf ("PRINT %d\n", mach->c [0].val); #endif /* DEBUG */ printf ("%d\n", mach->c [0].val); ++mach->b; break; case END: #ifdef DEBUG printf ("END\n"); #endif /* DEBUG */ mach->b = MEMSIZE; mach->c [0].val = 0; break; case GOTO: mach->b = mach->c [mach->b].val; #ifdef DEBUG printf ("GOTO %d\n", mach->b); #endif /* DEBUG */ break; case JZERO: if (! mach->c [0].val) { mach->b = mach->c [mach->b].val; #ifdef DEBUG printf ("JZERO %d\n", mach->b); #endif /* DEBUG */ } else ++mach->b; break; case NONE: ++mach->b; break; } } return mach->c [0].val; } int main (int argc, char ** argv) { machine mach; loadProgram (argv [1] ? argv [1] : "prg.rm", &mach); return runProgram (&mach); }