/*---------------------------------------------------------------------- File : rmsim.c Contents: register machine simulation Author : Christian Borgelt History : 22.11.1997 file created 24.11.1997 register machine program of example 3.7 added 26.11.1997 register machine program of example 3.8 added 02.12.1997 register machine definitions moved to regmach.h 08.12.1997 comment on compilation added ----------------------------------------------------------------------*/ #include #include #include #include "regmach.h" /*---------------------------------------------------------------------- Register Machine Programs ----------------------------------------------------------------------*/ void example3_7 (int cinit[], int n) { /* --- program of example 3.7 */ int pc = 1; /* program counter */ int c[4] = { 0, 5, 3, 0 }; /* registers */ PRG_BEGIN /* start of register machine program */ 1: CLOAD(1) /* load x^0 = 1 for an arbitrary x */ 2: STORE(3) /* and store it in the result reg. */ 3: LOAD(2) /* test the exponent and if it is 0, */ 4: IF (c0 = 0) GOTO(12) /* jump to the end of the program */ 5: LOAD(3) /* load the intermediary result, */ 6: MULT(1) /* multiply it by the base and */ 7: STORE(3) /* store the new result */ 8: LOAD(2) /* get the exponent, */ 9: CSUB(1) /* decrement it, */ 10: STORE(2) /* and store it */ 11: GOTO(4) /* go back to the exponent test */ 12: END /* stop the register machine */ PRG_END /* end of register machine program */ } /* example3_7() */ /*---------------------------------------------------------------------- This is the register machine program of example 3.7 discussed in the lecture. It computes the function x^y, where x is the value of register c1 and y the value of register c2 at the start of the program. The result is stored in register c3. The above register machine program is equivalent to the C-code c3 = 1; while (c2 > 0) { c3 *= c1; c2--; } ----------------------------------------------------------------------*/ void example3_8 (int cinit[], int n) { /* --- program of example 3.8 */ int pc = 1; /* program counter */ int c[4] = { 0, 2, 0, 0 }; /* registers */ PRG_BEGIN /* start of register machine program */ 1: LOAD(1) /* load argument (number to test) */ 2: CSUB(1) /* if the argument is <= 1, */ 3: IF (c0 = 0) GOTO(20) /* go to result: `no prime number' */ 4: CLOAD(2) /* load first test divisor */ 5: STORE(2) /* store the (next) test divisor */ 6: LOAD(1) /* load argument and */ 7: SUB(2) /* if the current divisor is greater, */ 8: IF (c0 = 0) GOTO(19) /* go to result: `prime number' */ 9: LOAD(1) /* otherwise load argument, */ 10: DIV(2) /* divide it by the divisor */ 11: MULT(2) /* and multiply it by the divisor */ 12: STORE(3) /* store the result (= (c1/c2)*c2) */ 13: LOAD(1) /* load the argument and compute */ 14: SUB(3) /* the remainder of argument/divisor */ 15: IF (c0 = 0) GOTO(20) /* if the remainder is zero, jump */ 16: LOAD(2) /* otherwise load the test divisor, */ 17: CADD(1) /* increment it, */ 18: GOTO(5) /* and restart the loop */ 19: CLOAD(1) /* load `prime number' */ 20: STORE(2) /* store the result of the test */ 21: END /* stop the register machine */ PRG_END /* end of register machine program */ } /* example3_8() */ /*---------------------------------------------------------------------- This is the register machine program of example 3.8 discussed in the lecture. It tests whether the argument given in register c1 is a prime number or not. If it is, a one, if it is not, a zero is written into register c2. The above register machine program is equivalent to the C-code if (c1 <= 1) { c2 = 0; goto end; } for (c2 = 2; c2 < c1; c2++) { if (c1 -(c1/c2)*c2 == 0) { c2 = 0; goto end; } } c2 = 1; end: ----------------------------------------------------------------------*/ void exercise16 (int cinit[], int n) { /* --- program of exercise 16 */ int pc = 1; /* program counter */ int c[4] = { 0, 15, 0, 0 }; /* registers */ PRG_BEGIN /* start of register machine program */ 1: CLOAD(0) /* load a zero and */ 2: STORE(2) /* initialize the counter */ 3: LOAD(2) /* load the counter and */ 4: MULT(2) /* compute its square */ 5: STORE(3) /* note the squared counter */ 6: LOAD(1) /* load the function argument and */ 7: SUB(3) /* compare it to the squared counter */ 8: IF (c0 = 0) GOTO(12) /* if the sq. counter is larger, jump */ 9: LOAD(2) /* load the counter, */ 10: CADD(1) /* increment it, and */ 11: GOTO(2) /* go back to the square computation */ 12: END /* stop the register machine */ PRG_END /* end of register machine program */ } /* exercise16() */ /*---------------------------------------------------------------------- At the end of the program the register c2 contains the ceiling of the square root of the argument, which is contained in register c1 at the start of the program (i.e. c2 = \lceil\sqrt(c1)\rceil). Register c3 contains the square of the contents of c2, i.e. c3 contains the smallest square number greater than or equal to the argument in c1. The above register machine program is equivalent to the C-code c2 = 0; while (1) { c3 = c2 * c2; if (c3 >= c1) break; c2++; } ----------------------------------------------------------------------*/ void exercise17a (int cinit[], int n) { /* --- program of exercise 17 a */ int pc = 1; /* program counter */ int c[3] = { 0, 0, 0 }; /* registers */ PRG_BEGIN /* start of register machine program */ 1: LOAD(2) /* load the second argument */ 2: IF (c0 = 0) GOTO(10) /* if it is zero, jump */ 3: LOAD(1) /* load the first argument, */ 4: CADD(1) /* increment it, and */ 5: STORE(1) /* store the new value */ 6: LOAD(2) /* load the second argument, */ 7: CSUB(1) /* decrement it, and */ 8: STORE(2) /* store the reduced value */ 9: GOTO(2) /* go back to the test of the 2nd arg */ 10: END /* stop the register machine */ PRG_END /* end of register machine program */ } /* exercise17a() */ /*---------------------------------------------------------------------- At the end of the program the register c1 contains the sum of the numbers that were contained in the registers c1 and c2 at the start of the program. This is achieved by increasing the contents of c1 by one and decreasing the contents of c2 by 1 until the contents of c2 is 0. The above register machine program is equivalent to the C-code while (c2 > 0) { c1++; c2--; } ----------------------------------------------------------------------*/ void exercise17b (int cinit[], int n) { /* --- program of exercise 17 b */ int pc = 1; /* program counter */ int c[3] = { 0, 0, 0 }; /* registers */ PRG_BEGIN /* start of register machine program */ 1: LOAD(2) /* load the second argument */ 2: CSUB(5) /* compare it to 5 */ 3: IF (c0 = 0) GOTO(8) /* if it is less or equal, jump */ 4: LOAD(2) /* reload the second argument, */ 5: MULT(1) /* multiply it by the first */ 6: STORE(1) /* and store the result, then */ 7: GOTO(11) /* jump to the end of the program */ 8: LOAD(2) /* if the second argument is less */ 9: ADD(1) /* than 5, add the first argument */ 10: STORE(1) /* and store the result */ 11: END /* stop the register machine */ PRG_END /* end of register machine program */ } /* exercise17b() */ /*---------------------------------------------------------------------- If the second argument (contained in register c2) is greater than 5, then at the end of the program the register c1 contains the product of the numbers that were contained in the registers c1 and c2 at the start of the program. If the second argument (contained in register c2) is less than or equal to 5, then at the end of the program the register c1 contains the sum of the numbers that were contained in the registers c1 and c2 at the start of the program. The above register machine program is equivalent to the C-code if (c2 > 5) c1 *= c2; else c1 += c2; ----------------------------------------------------------------------*/ /*---------------------------------------------------------------------- Main Function ----------------------------------------------------------------------*/ int main (int argc, char *argv[]) { /* --- main function */ int n = 0; /* number of filled registers */ int c[16]; /* registers */ if (argc <= 1) { /* if no arguments given */ printf("usage: %s ex [c0 c1 ...]\n", argv[0]); printf("simulate a register machine\n"); printf("ex example/exercise number (3.7/3.8/16/17a/17b)\n"); printf("c0 c1 ... initial register contents\n"); return 0; /* print a usage message */ } /* and abort the program */ if (argc > 18) argc = 18; /* get at most 16 numbers */ while (n < argc-2) { /* traverse additional arguments */ c[n] = atoi(argv[n+2]); /* get contents of next register */ if (c[n] < 0) c[n] = 0; /* if it is negative, set it to zero */ n++; /* increment register index */ } if (strcmp(argv[1], "3.7") == 0) example3_7 (c, n); else if (strcmp(argv[1], "3.8") == 0) example3_8 (c, n); else if (strcmp(argv[1], "16") == 0) exercise16 (c, n); else if (strcmp(argv[1], "17a") == 0) exercise17a(c, n); else if (strcmp(argv[1], "17b") == 0) exercise17b(c, n); else { printf("%s: illegal number\n", argv[0]); return 1; } return 0; /* return 'ok' */ } /* main() */ /*---------------------------------------------------------------------- This program needs the files `regmach.h' and `regmach.c' to compile. To get an executable program type: gcc -ansi -Wall -pedantic rmsim.c regmach.c -o rmsim ----------------------------------------------------------------------*/