/*
* 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <arpa/inet.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
/*
* 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);
}
}
}