vm.c

/* types
  Button - represents a GPIO pin hooked to a button
  Neopixel - represents a GPIO pin hooked to neopixels
  Strip - represents a memory buffer for 1d array of colors
  Grid - represents a memory buffer for a 2d array of colors
  Position1d - represents a bounded 2D coordinate
  Position2d - represents a bounded 2D coordinate
  Interval - represents a clock 33345rtfv ith a given frequency
  Schedule - represents a schedule to alarm at given times
  Color - represents a 24 bit RGB color
*/
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

typedef enum opcode opcode_t;
enum opcode {
  // 0-63 represent themselves.
  OP_I8 = 64,  // Followed by 1 byte literal
  OP_I16,      // Followed by 2 byte literal
  OP_I32,      // Followed by 4 byte literal
  // Basic arithmatic
  OP_ADD,  // e + e
  OP_SUB,  // e - e
  OP_MUL,  // e * e
  OP_DIV,  // e / e
  OP_MOD,  // e % e
  OP_NEG,  // -e
  // Bitwise math (treat as unsigned)  booleans use these too.
  OP_AND,     // e & e
  OP_OR,      // e | e
  OP_XOR,     // e ^ e
  OP_NOT,     // ~e
  OP_RSHIFT,  // e >> e
  OP_LSHIFT,  // e << e

  OP_EQ,   // a == b
  OP_NEQ,  // a != b
  OP_GT,   // a > b
  OP_GTE,  // a >= b
  OP_LT,   // a < b
  OP_LTE,  // a <= b

  OP_INCRMOD,  // Followed by 3 expressions (num, incr, mod)

  OP_LOAD,   // Followed by 8 bits for address
  OP_STORE,  // Followed by 8 bits for address and expression

  OP_DUP,   // Duplicate the top item
  OP_DROP,  // Drop one item
  OP_SWAP,  // Swap top two items in stack

  OP_JUMP,    // Consume 2 bytes as i16, jump that far
  OP_UNLESS,  // Consume 2 bytes as i16, jump that far if top if zero
  OP_IF,      // Consume 2 bytes as i16, jump that far if top if not zero

  OP_YIELD,   // Defer to the event loop
  OP_SLEEP,   // ms - defer for number of ms
  OP_POLL,    // defer to event loop waiting for something to change
  OP_SELECT,  // defer to event loop waiting for anything in a set to change
  OP_END,     // Stop running function
  // 191-255 represent themselves as 2-complement I8
};

typedef struct coro coro_t;
struct coro {
  const uint8_t* code;
  size_t code_i;
  int32_t stack[256];
  size_t stack_i;
  coro_t* next;
};

typedef struct loop loop_t;
struct vm {
  uint32_t vars[256];
  coro_t* current;
};

static char tmp_hex[3];
static const char* hex = "0123456789abcdef";
static char* tohex(uint8_t n) {
  tmp_hex[0] = hex[n >> 4];
  tmp_hex[1] = hex[n & 0xf];
  return tmp_hex;
}

static const char* decompile(uint8_t op) {
  switch (op) {
    case OP_I8:
      return "I8";
    case OP_I16:
      return "I16";
    case OP_I32:
      return "I32";
    case OP_ADD:
      return "ADD";
    case OP_SUB:
      return "SUB";
    case OP_MUL:
      return "MUL";
    case OP_DIV:
      return "DIV";
    case OP_MOD:
      return "MOD";
    case OP_NEG:
      return "NEG";
    case OP_AND:
      return "AND";
    case OP_OR:
      return "OR";
    case OP_XOR:
      return "XOR";
    case OP_NOT:
      return "NOT";
    case OP_RSHIFT:
      return "RSHIFT";
    case OP_LSHIFT:
      return "LSHIFT";
    case OP_EQ:
      return "EQ";
    case OP_NEQ:
      return "NEQ";
    case OP_GT:
      return "GT";
    case OP_GTE:
      return "GTE";
    case OP_LT:
      return "LT";
    case OP_LTE:
      return "LTE";
    case OP_INCRMOD:
      return "INCRMOD";
    case OP_LOAD:
      return "LOAD";
    case OP_STORE:
      return "STORE";
    case OP_DUP:
      return "DUP";
    case OP_DROP:
      return "DROP";
    case OP_SWAP:
      return "SWAP";
    case OP_JUMP:
      return "JUMP";
    case OP_UNLESS:
      return "UNLESS";
    case OP_IF:
      return "IF";
    case OP_YIELD:
      return "YIELD";
    case OP_SLEEP:
      return "SLEEP";
    case OP_POLL:
      return "POLL";
    case OP_SELECT:
      return "SELECT";
    case OP_END:
      return "END";
  }
  return "UNKNOWN";
}

static coro_t spawn(uint8_t* code) {
  return (coro_t){.code_i = 0, .stack_i = 0, .code = code};
}

static void print_code(const uint8_t* code) {
  printf("\x1b[31m%p\x1b[0m:", code);
  int consume = 0;
  do {
    if (consume > 0) {
      consume--;
      printf("\x1b[34m%s\x1b[0m", tohex(*code));
      if (consume)
        printf(" ");
      else
        printf(")");
    } else if (*code < 0x40 || *code >= 0xc0) {
      printf(" \x1b[30;1m%s\x1b[0m", tohex(*code));
    } else {
      printf(" \x1b[34;1m%s\x1b[0m", decompile(*code));
      switch (*code) {
        case OP_I8:
        case OP_LOAD:
        case OP_STORE:
          consume = 1;
          break;
        case OP_I16:
        case OP_JUMP:
        case OP_UNLESS:
        case OP_IF:
          consume = 2;
          break;
        case OP_I32:
          consume = 4;
          break;
      }
      if (consume)
        printf("(");
    }
  } while (*++code != OP_END);
  printf("\n");
}

void run(coro_t* coro, int32_t* vars) {
  const uint8_t* code = &coro->code[coro->code_i];
  int32_t* top = &coro->stack[coro->stack_i] - 1;
  while (*code != OP_END) {
    uint8_t byte = *code++;
    if (byte < 0x40 || byte >= 0xc0) {
      *++top = (int8_t)byte;
    } else {
      switch ((opcode_t)byte) {
        case OP_I8:
          *++top = *((int8_t*)code++);
          break;
        case OP_I16:
          *++top = *((int16_t*)code);
          code += 2;
          break;
        case OP_I32:
          *++top = *((int32_t*)code);
          code += 4;
          break;
        case OP_ADD:
          top--;
          *top = *top + *(top + 1);
          break;
        case OP_SUB:
          top--;
          *top = *top - *(top + 1);
          break;
        case OP_MUL:
          top--;
          *top = *top * *(top + 1);
          break;
        case OP_DIV:
          top--;
          *top = *top / *(top + 1);
          break;
        case OP_MOD:
          top--;
          int32_t b = *(top + 1);
          int32_t a = *top % b;
          // Euclidean modulus is the behavior we want, not the default C style.
          *top = a < 0 ? a + abs(b) : a;
          break;
        case OP_NEG:
          *top = -*top;
          break;
        case OP_AND:
          top--;
          *top = *top & *(top + 1);
          break;
        case OP_OR:
          top--;
          *top = *top | *(top + 1);
          break;
        case OP_XOR:
          top--;
          *top = *top ^ *(top + 1);
          break;
        case OP_NOT:
          *top = ~*top;
          break;
        case OP_RSHIFT:
          top--;
          *top = (int32_t)((uint32_t)*top >> (uint32_t) * (top + 1));
          break;
        case OP_LSHIFT:
          top--;
          *top = (int32_t)((uint32_t)*top << (uint32_t) * (top + 1));
          break;
        case OP_EQ:
          top--;
          *top = *top == *(top + 1) ? -1 : 0;
          break;
        case OP_NEQ:
          top--;
          *top = *top != *(top + 1) ? -1 : 0;
          break;
        case OP_GT:
          top--;
          *top = *top > *(top + 1) ? -1 : 0;
          break;
        case OP_GTE:
          top--;
          *top = *top >= *(top + 1) ? -1 : 0;
          break;
        case OP_LT:
          top--;
          *top = *top < *(top + 1) ? -1 : 0;
          break;
        case OP_LTE:
          top--;
          *top = *top <= *(top + 1) ? -1 : 0;
          break;
        case OP_INCRMOD: {
          top -= 2;
          int32_t b = *(top + 2);
          int32_t a = (*top + *(top + 1)) % b;
          // Euclidean modulus is the behavior we want, not the default C style.
          *top = a < 0 ? a + abs(b) : a;
          break;
        }
        case OP_LOAD:
          *++top = vars[*code++];
          break;
        case OP_STORE:
          vars[*code++] = *top--;
          break;
        case OP_DUP:
          ++top;
          *top = *(top - 1);
          break;
        case OP_DROP:
          top--;
          break;
        case OP_SWAP: {
          int32_t t = *top;
          *top = *(top - 1);
          *(top - 1) = t;
          break;
        }
        case OP_JUMP:
          code += *(int16_t*)code;
          break;
        case OP_UNLESS:
          code += (*top-- == 0) ? *(int16_t*)code : 2;
          break;
        case OP_IF:
          code += (*top-- != 0) ? *(int16_t*)code : 2;
          break;
        default:
          printf("TODO: support opcode %s\n", decompile(byte));
          assert(0);
          break;
      }
    }
  }
  coro->code_i = code - coro->code;
  coro->stack_i = top + 1 - coro->stack;
}

typedef struct test test_t;
struct test {
  uint8_t* code;
  size_t len;
  int32_t* stack;
};
const test_t tests[] = {
    {.code = (uint8_t[]){0x3f, -0x3f, OP_END},
     .len = 2,
     .stack = (int32_t[]){0x0000003f, 0xffffffc1}},
    {.code = (uint8_t[]){-10, -5, -1, 0, 1, 5, 10, OP_END},
     .len = 7,
     .stack = (int32_t[]){-10, -5, -1, 0, 1, 5, 10}},
    {.code = (uint8_t[]){OP_I8, -1, OP_I16, 0x11, 0x22, OP_I32, 0xef, 0xbe,
                         0xad, 0xde, 9, OP_END},
     .len = 4,
     .stack = (int32_t[]){-1, 0x2211, 0xdeadbeef, 9}},
    {.code = (uint8_t[]){1, 2, OP_ADD, 10, 5, OP_SUB, OP_MUL, OP_END},
     .len = 1,
     .stack = (int32_t[]){15}},
    {.code = (uint8_t[]){1, 0,      OP_AND, 1, 0, OP_OR,  1, 0, OP_XOR,
                         1, 1,      OP_XOR, 0, 0, OP_XOR, 0, 1, OP_XOR,
                         1, OP_NOT, OP_END},
     .len = 7,
     .stack = (int32_t[]){0, 1, 1, 0, 0, 1, ~1}},
    {.code = (uint8_t[]){OP_I32, 0b11001100, 0b11001100, 0b11001100, 0b11001100,
                         OP_I32, 0b00001111, 0b00001111, 0b00001111, 0b00001111,
                         OP_XOR, OP_END},
     .len = 1,
     .stack = (int32_t[]){0b11000011110000111100001111000011}},
    {.code = (uint8_t[]){OP_I32, 0b11001100, 0b11001100, 0b11001100, 0b11001100,
                         OP_I32, 0b00001111, 0b00001111, 0b00001111, 0b00001111,
                         OP_AND, OP_END},
     .len = 1,
     .stack = (int32_t[]){0b00001100000011000000110000001100}},
    {.code = (uint8_t[]){OP_I32, 0b11001100, 0b11001100, 0b11001100, 0b11001100,
                         OP_I32, 0b00001111, 0b00001111, 0b00001111, 0b00001111,
                         OP_OR, OP_END},
     .len = 1,
     .stack = (int32_t[]){0b11001111110011111100111111001111}},
    {.code = (uint8_t[]){OP_I32, 0b11001100, 0b11001100, 0b11001100, 0b11001100,
                         OP_I32, 0b00001111, 0b00001111, 0b00001111, 0b00001111,
                         OP_NOT, OP_END},
     .len = 2,
     .stack = (int32_t[]){0b11001100110011001100110011001100,
                          0b11110000111100001111000011110000}},
    {.code = (uint8_t[]){OP_I32, 0b11001100, 0b11001100, 0b11001100, 0b11001100,
                         7, OP_RSHIFT, OP_END},
     .len = 1,
     .stack = (int32_t[]){0b00000001100110011001100110011001}},
    {.code = (uint8_t[]){OP_I32, 0b11001100, 0b11001100, 0b11001100, 0b11001100,
                         7, OP_LSHIFT, OP_END},
     .len = 1,
     .stack = (int32_t[]){0b01100110011001100110011000000000}},
    {.code = (uint8_t[]){3, 10, 10, OP_INCRMOD, 3, -10, 10, OP_INCRMOD, 3,
                         OP_I8, -100, 10, OP_INCRMOD, OP_END},
     .len = 3,
     .stack = (uint32_t[]){3, 3, 3}},
    {.code = (uint8_t[]){0, 10, 10, OP_INCRMOD, 0, -10, 10, OP_INCRMOD, 0,
                         OP_I8, -100, 10, OP_INCRMOD, OP_END},
     .len = 3,
     .stack = (uint32_t[]){0, 0, 0}},
    {.code = (uint8_t[]){9, 10, 10, OP_INCRMOD, 9, -10, 10, OP_INCRMOD, 9,
                         OP_I8, -100, 10, OP_INCRMOD, OP_END},
     .len = 3,
     .stack = (uint32_t[]){9, 9, 9}},
    {.code =
         (uint8_t[]){3, 10, OP_MOD, -7, 10, OP_MOD, -17, 10, OP_MOD, OP_END},
     .len = 3,
     .stack = (uint32_t[]){3, 3, 3}},
    {.code =
         (uint8_t[]){0, 10, OP_MOD, -10, 10, OP_MOD, -20, 10, OP_MOD, OP_END},
     .len = 3,
     .stack = (uint32_t[]){0, 0, 0}},
    {.code =
         (uint8_t[]){9, 10, OP_MOD, -1, 10, OP_MOD, -11, 10, OP_MOD, OP_END},
     .len = 3,
     .stack = (uint32_t[]){9, 9, 9}},
    {.code = (uint8_t[]){42, OP_STORE, 10, OP_LOAD, 10, OP_LOAD, 10, OP_END},
     .len = 2,
     .stack = (uint32_t[]){42, 42}},

    {.code = (uint8_t[]){1, 2, 3, OP_DROP, OP_END},
     .len = 2,
     .stack = (uint32_t[]){1, 2}},
    {.code = (uint8_t[]){1, 2, 3, OP_DUP, OP_END},
     .len = 4,
     .stack = (uint32_t[]){1, 2, 3, 3}},
    {.code = (uint8_t[]){1, 2, 3, OP_SWAP, OP_END},
     .len = 3,
     .stack = (uint32_t[]){1, 3, 2}},
    {.code = (uint8_t[]){1, 2, OP_EQ, 1, 2, OP_NEQ, 1, 2, OP_GT, 1, 2, OP_GTE,
                         1, 2, OP_LT, 1, 2, OP_LTE, OP_END},
     .len = 6,
     .stack = (uint32_t[]){0, -1, 0, 0, -1, -1}},
    {.code = (uint8_t[]){0, OP_UNLESS, 6, 0, 10, OP_JUMP, 3, 0, 20, OP_END},
     .len = 1,
     .stack = (uint32_t[]){20}},
    {.code = (uint8_t[]){0, OP_IF, 6, 0, 10, OP_JUMP, 3, 0, 20, OP_END},
     .len = 1,
     .stack = (uint32_t[]){10}},

    {(uint8_t[]){OP_END}, 0, (uint32_t[]){}},
};

int32_t vars[256];

int main() {
  int failures = 0;
  for (int t = 0; tests[t].code[0] != OP_END; t++) {
    coro_t coro = spawn(tests[t].code);
    print_code(coro.code);
    run(&coro, &vars[0]);
    for (int i = 0; i < coro.stack_i || i < tests[t].len; i++) {
      bool passed = i < coro.stack_i && i < tests[t].len &&
                    tests[t].stack[i] == coro.stack[i];
      if (!passed)
        failures++;
      const char* color = passed ? "\x1b[32m" : "\x1b[31;1m";
      printf("stack[\x1b[35;1m%02x\x1b[0m]", i);
      if (i < tests[t].len)
        printf(" expected=[%s%08x\x1b[0m]", color, tests[t].stack[i]);
      else
        printf(" expected=[%s--------\x1b[0m]", color);
      if (i < coro.stack_i)
        printf(" actual=[%s%08x\x1b[0m]\n", color, coro.stack[i]);
      else
        printf(" actual=[%s--------\x1b[0m]\n", color);
    }
    if (failures > 0) {
      printf("<<< FAILED %d TEST%s >>>\n", failures, failures == 1 ? "" : "S");
      return -1;
    }
  }
}