/* * um.c * by team Abstraction Anonymous: Bill Weiss, Daniel Lyons, David Baird * Written for the 2006 ICFP Programming Contest (www.icfpcontest.org) * * Complete working implementation of the virtual machine specified at * http://www.icfpcontest.org/um-spec.txt */ #include #include #include #include #include #include #include #include #include /* * Unpacking functions: uint32 -> instruction with operands * * For speed, we decided that these would all be macros. A good compiler * would probably make inline functions equivalent to this in speed, but * we were in a hurry. */ #define A(inst) ((inst >> 0x6) & 0x7) #define B(inst) ((inst >> 0x3) & 0x7) #define C(inst) (inst & 0x7) #define A13(inst) ((inst >> 25) & 0x7) #define DATA(inst) (inst & 0x1ffffff) #define OP(inst) (inst >> 28) #define REG(num) (registers[num]) #define REGA(inst) (REG(A(inst))) #define REGB(inst) (REG(B(inst))) #define REGC(inst) (REG(C(inst))) #define REGA13(inst) (REG(A13(inst))) /* * This was carefully tuned by increasing it every time memory allocation * failed in the VM. While that sounds like a bad way to go, it worked * ok. I suspect that the actual needs are near (1024 * 1024), but it * crashed after a while with only that much memory. We just added the * 32 in to make it work. */ #define MEMSIZ (1024 * 1024 * 32) typedef unsigned int platter; /* * For a while we thought we were going to use functions for this, and * wanted to not have to think about variable passing. Shameful, I know. * These could just all be put in main() now since we don't have any * functions,but this is the way it was during the competition. */ platter registers[8] = {0,0,0,0,0,0,0,0}; platter * arrays[MEMSIZ]; size_t siz_arrays[MEMSIZ]; size_t num_array = 1; platter finger = 0; int main(int argc, char *argv[]) { int lastloc = 0, i; platter cur; platter * temp; struct stat x; /* * I'm ashamed to say that originally, we were just hardcoding the * filesize (while we were making it work). This helped run the umix * image :) */ stat(argv[1], &x); /* * Originally, we were working directly on the mmap()ed file. Our * memory allocation system didn't play well with it (calling free() * on a mmap() pointer doesn't work), so we came up with this garbage. * It works pretty well. */ temp = (platter *) mmap(NULL, x.st_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, open(argv[1], O_RDONLY, 0600), (off_t) 0); arrays[0] = (platter *) malloc(x.st_size); memcpy(arrays[0], temp, x.st_size); munmap(temp, x.st_size); /* * The VM was written on a Mac, and this wasn't there (since the * endian-ness was the same). Once David came in, we had to add this * to make it work. Benchmarking found that this is really fast. * Since it's a one-time cost anyway, who cares? */ for (i = finger; i < (finger + x.st_size / sizeof(platter)); i++) arrays[0][i] = htonl(arrays[0][i]); siz_arrays[0] = x.st_size; /* * This is the (potentially) interesting part. Grab an instruction, * do it. */ while(1) { cur = arrays[0][finger++]; switch(OP(cur)) { /* #0. Conditional Move. * * The register A receives the value in register B, * unless the register C contains 0. */ case 0: if (REGC(cur) != 0) { REGA(cur) = REGB(cur); } break; /* #1. Array Index. * * The register A receives the value stored at offset * in register C in the array identified by B. */ case 1: REGA(cur) = arrays[REGB(cur)][REGC(cur)]; break; /* #2. Array Amendment. * * The array identified by A is amended at the offset * in register B to store the value in register C. */ case 2: assert(arrays[REGA(cur)] != 0); arrays[REGA(cur)][REGB(cur)] = REGC(cur); break; /* #3. Addition. * * The register A receives the value in register B plus * the value in register C, modulo 2^32. */ case 3: REGA(cur) = REGB(cur) + REGC(cur); break; /* #4. Multiplication. * * The register A receives the value in register B times * the value in register C, modulo 2^32. */ case 4: REGA(cur) = REGB(cur) * REGC(cur); break; /* #5. Division. * * The register A receives the value in register B * divided by the value in register C, if any, where * each quantity is treated treated as an unsigned 32 * bit number. */ case 5: REGA(cur) = REGB(cur) / REGC(cur); break; /* #6. Not-And. * * Each bit in the register A receives the 1 bit if * either register B or register C has a 0 bit in that * position. Otherwise the bit in register A receives * the 0 bit. */ case 6: REGA(cur) = ~ (REGB(cur) & REGC(cur)); break; /* #7. Halt. * * The universal machine stops computation. */ case 7: exit(0); break; /* #8. Allocation. * * A new array is created with a capacity of platters * commensurate to the value in the register C. This * new array is initialized entirely with platters * holding the value 0. A bit pattern not consisting of * exclusively the 0 bit, and that identifies no other * active allocated array, is placed in the B register. */ case 8: for (i = lastloc+1; arrays[i] != NULL && i != lastloc; i = (i + 1) % MEMSIZ); assert(i != lastloc); lastloc = i; arrays[i] = (platter *) calloc(REGC(cur), sizeof(platter)); siz_arrays[i] = REGC(cur); REGB(cur) = i; break; /* #9. Abandonment. * * The array identified by the register C is abandoned. * Future allocations may then reuse that identifier. */ case 9: free(arrays[REGC(cur)]); arrays[REGC(cur)] = 0; break; /* #10. Output. * * The value in the register C is displayed on the console * immediately. Only values between and including 0 and 255 * are allowed. */ case 10: if (REGC(cur) < 256) { putchar(REGC(cur)); fflush(stdout); } break; /* #11. Input. * * The universal machine waits for input on the console. * When input arrives, the register C is loaded with the * input, which must be between and including 0 and 255. * If the end of input has been signaled, then the * register C is endowed with a uniform value pattern * where every place is pregnant with the 1 bit. */ case 11: REGC(cur) = getchar(); break; /* #12. Load Program. * * The array identified by the B register is duplicated * and the duplicate shall replace the '0' array, * regardless of size. The execution finger is placed * to indicate the platter of this array that is * described by the offset given in C, where the value * 0 denotes the first platter, 1 the second, et * cetera. * * The '0' array shall be the most sublime choice for * loading, and shall be handled with the utmost * velocity. */ case 12: if (REGB(cur) != 0) { free(arrays[0]); arrays[0] = (platter *) calloc(siz_arrays[REGB(cur)], sizeof(platter)); assert(arrays[0] != 0); assert(arrays[REGB(cur)] != 0); memcpy(arrays[0], arrays[REGB(cur)], siz_arrays[REGB(cur)] * sizeof(platter)); siz_arrays[0] = siz_arrays[REGB(cur)]; } finger = REGC(cur); break; /* #13. Orthography. * * The value indicated is loaded into the register A * forthwith. */ case 13: REGA13(cur) = DATA(cur); break; /* There aren't opcodes 14 or 15, and it's permissible to just * fail when that happens. */ default: exit(1); } } }