Universal Machine Interpreter (ICFP 2006)

umi.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct segment {
  unsigned len;
  unsigned next_free_segment;
  unsigned* data;
};

struct um_state {
  unsigned pc;
  unsigned registers[8];
  unsigned reserved_segments;
  unsigned next_free_segment;
  struct segment* segments;
} um_state;

#define NO_FREE_SEGMENTS_LEFT UINT_MAX

unsigned find_next_free_segment(struct um_state* state) {
  unsigned free_segment_idx = um_state.next_free_segment;

  if (free_segment_idx == NO_FREE_SEGMENTS_LEFT) {
    free_segment_idx = um_state.reserved_segments;

    um_state.reserved_segments++;
    um_state.segments = realloc(
      um_state.segments,
      sizeof(struct segment) * um_state.reserved_segments
    );

    if (um_state.segments == NULL) {
      perror("Error allocating new segment");
      exit(1);
    }

  } else {
    um_state.next_free_segment = um_state.segments[free_segment_idx].next_free_segment;
  }

  return free_segment_idx;
}

void* memdup(const void* src, unsigned len) {
  void* dst = malloc(len);

  if (dst == NULL) {
    return NULL;
  }

  return memcpy(dst, src, len);
}

void* read_file(const char* filename, unsigned* length) {
  unsigned file_length;
  void* file_data;
  FILE* file = fopen(filename, "rb");

  if (file == NULL) {
    perror("Error reading file");
    exit(1);
  }

  fseek(file, 0, SEEK_END);
  file_length = ftell(file);
  rewind(file);
  file_data = malloc(file_length);

  if (file_data == NULL) {
    perror("Error allocating memory for file contents");
    exit(1);
  }

  fread(file_data, file_length, 1, file);
  fclose(file);

  if (length != NULL) {
    *length = file_length;
  }

  return file_data;
}

unsigned convert_endianness(unsigned input) {
  return ((input >> 24) & 0xFF) <<  0
       | ((input >> 16) & 0xFF) <<  8
       | ((input >>  8) & 0xFF) << 16
       | ((input >>  0) & 0xFF) << 24;
}

#define GET_OPCODE(operation) (((operation) >> 28) & 0b1111)
#define GET_ARG_A(operation)  (((operation) >>  6) &  0b111)
#define GET_ARG_B(operation)  (((operation) >>  3) &  0b111)
#define GET_ARG_C(operation)  (((operation) >>  0) &  0b111)

#define GET_LIT(operation) ((operation) & 0b1111111111111111111111111)
#define GET_LIT_DEST(operation) (((operation) >> 25) & 0b111)

enum um_operation {
  CMOV, LOAD, STORE, ADD, MUL, DIV, NAND,
  HALT, ALLOC, FREE, WRITE, READ, EXEC,
  LIT,
  INVALID
};

const char* operation_names[] = {
  "CMOV", "LOAD", "STORE", "ADD", "MUL", "DIV", "NAND",
  "HALT", "ALLOC", "FREE", "WRITE", "READ", "EXEC",
  "LIT",
  "INVALID"
};

void run_op(int operation) {
  enum um_operation opcode = GET_OPCODE(operation);
  unsigned* arg_a = &um_state.registers[GET_ARG_A(operation)];
  unsigned* arg_b = &um_state.registers[GET_ARG_B(operation)];
  unsigned* arg_c = &um_state.registers[GET_ARG_C(operation)];

  switch (opcode) {
    unsigned free_segment_idx;

    case CMOV:
      if (*arg_c != 0) {
        *arg_a = *arg_b;
      }
      break;
    case LOAD:
      *arg_a = um_state.segments[*arg_b].data[*arg_c];
      break;
    case STORE:
      um_state.segments[*arg_a].data[*arg_b] = *arg_c;
      break;
    case ADD:
      *arg_a = *arg_b + *arg_c;
      break;
    case MUL:
      *arg_a = *arg_b * *arg_c;
      break;
    case DIV:
      *arg_a = *arg_b / *arg_c;
      break;
    case NAND:
      *arg_a = ~(*arg_b & *arg_c);
      break;
    case HALT:
      puts("Halt requested, bye!");
      exit(0);
      break;
    case ALLOC:
      free_segment_idx = find_next_free_segment(&um_state);
      um_state.segments[free_segment_idx].len = *arg_c;
      um_state.segments[free_segment_idx].data = calloc(*arg_c, sizeof(unsigned));

      if (um_state.segments[free_segment_idx].data == NULL) {
        perror("Failed to allocate segment contents");
        exit(1);
      }

      *arg_b = free_segment_idx;
      break;
    case FREE:
      free(um_state.segments[*arg_c].data);
      um_state.segments[*arg_c].len = 0;
      um_state.segments[*arg_c].data = NULL;
      um_state.segments[*arg_c].next_free_segment = um_state.next_free_segment;
      um_state.next_free_segment = *arg_c;
      break;
    case WRITE:
      putchar(*arg_c);
      break;
    case READ:
      *arg_c = getchar();
      break;
    case EXEC:
      if (*arg_b != 0) {
        free(um_state.segments[0].data);
        um_state.segments[0].len = um_state.segments[*arg_b].len;
        um_state.segments[0].data = memdup(
          um_state.segments[*arg_b].data,
          sizeof(unsigned) * um_state.segments[*arg_b].len
        );

        if (um_state.segments[0].data == NULL) {
          perror("Failed to duplicate segment for exec");
          exit(1);
        }
      }
      um_state.pc = *arg_c;
      return;
    case LIT:
      um_state.registers[GET_LIT_DEST(operation)] = GET_LIT(operation);
      break;
    default:
      perror("Invalid instruction!");
      exit(1);
  }
  um_state.pc++;
}

int main(int argc, const char* argv[]) {
  if (argc < 2) {
    printf("Usage: %s [file]\n", argv[0]);
    exit(0);
  }

  unsigned program_length;
  void* program_data = read_file(argv[1], &program_length);

  um_state.reserved_segments = 1;
  um_state.segments = malloc(sizeof(struct segment));
  um_state.segments[0].len = program_length / sizeof(unsigned);
  um_state.segments[0].data = program_data;
  um_state.next_free_segment = NO_FREE_SEGMENTS_LEFT;

  for (unsigned i = 0; i < um_state.segments[0].len; i++) {
    um_state.segments[0].data[i] =
      convert_endianness(um_state.segments[0].data[i]);
  }

  while (um_state.pc < um_state.segments[0].len) {
    unsigned operation = um_state.segments[0].data[um_state.pc];
    run_op(um_state.segments[0].data[um_state.pc]);
  }

  return 0;
}