9
\$\begingroup\$

(See also the next iteration.)

I have this small virtual machine.

What is there:

  • Stack and, thus, recursion.
  • Conditional and unconditional jumps and, thus, choice and iteration.

What is not there:

  • Floating-point type support.
  • Bit manipulation instructions.
  • No input operations, all "input" must be hardcoded into the memory of the VM.

toyvm.h:

#ifndef TOYVM_H
#define TOYVM_H

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

/* Arithmetics */
const uint8_t ADD = 0x01;
const uint8_t NEG = 0x02;
const uint8_t MUL = 0x03;
const uint8_t DIV = 0x04;
const uint8_t MOD = 0x05;

/* Conditionals */
const uint8_t CMP = 0x10;
const uint8_t JA  = 0x11; /* Jump if above. */
const uint8_t JE  = 0x12; /* Jump if equal. */
const uint8_t JB  = 0x13; /* Jump if below. */
const uint8_t JMP = 0x14; /* Unconditional jump for implementing loops. */

/* Subroutines */
const uint8_t CALL = 0x20;
const uint8_t RET  = 0x21;

/* Moving data */
const uint8_t LOAD  = 0x30;
const uint8_t STORE = 0x31;
const uint8_t CONST = 0x32;

/* Auxiliary */
const uint8_t HALT = 0x40;
const uint8_t INT  = 0x41;
const uint8_t NOP  = 0x42;

/* Stack operations */
const uint8_t PUSH     = 0x50;
const uint8_t PUSH_ALL = 0x51;
const uint8_t POP      = 0x52;
const uint8_t POP_ALL  = 0x53;
const uint8_t LSP      = 0X54; /* Load Stack Pointer - used for accessing the */
                               /* function arguments.                         */
/* Register indices */
const uint8_t REG1 = 0x0;
const uint8_t REG2 = 0x1;
const uint8_t REG3 = 0x2;
const uint8_t REG4 = 0x3;

/* Status codes */
const uint8_t STATUS_HALT_BAD_INSTRUCTION   = 0x1;
const uint8_t STATUS_STACK_UNDERFLOW        = 0x2;
const uint8_t STATUS_STACK_OVERFLOW         = 0x4;
const uint8_t STATUS_INVALID_REGISTER_INDEX = 0x8;
const uint8_t STATUS_BAD_ACCESS             = 0x10;
const uint8_t STATUS_COMPARISON_BELOW       = 0x20;
const uint8_t STATUS_COMPARISON_EQUAL       = 0x40;
const uint8_t STATUS_COMPARISON_ABOVE       = 0x80;

/* Interrupts */
const uint8_t INTERRUPT_PRINT_INTEGER = 0x1;
const uint8_t INTERRUPT_PRINT_STRING  = 0x2;

const size_t N_REGISTERS = 4;

typedef struct VM_CPU {
    int32_t registers[N_REGISTERS];
    int32_t program_counter;
    int32_t stack_pointer;

    struct {
        uint8_t HALT_BAD_INSTRUCTION   : 1;
        uint8_t STACK_UNDERFLOW        : 1;
        uint8_t STACK_OVERFLOW         : 1;
        uint8_t INVALID_REGISTER_INDEX : 1;
        uint8_t BAD_ACCESS             : 1;
        uint8_t COMPARISON_BELOW       : 1;
        uint8_t COMPARISON_EQUAL       : 1;
        uint8_t COMPARISON_ABOVE       : 1;
    } status;
} VM_CPU;

typedef struct TOYVM {
    uint8_t* memory;
    int32_t  memory_size;
    int32_t  stack_limit;
    VM_CPU   cpu;
} TOYVM;

size_t GET_INSTRUCTION_LENGTH(uint8_t opcode)
{
    switch (opcode)
    {
        case PUSH_ALL:
        case POP_ALL:
        case RET:
        case HALT:
        case NOP:
            return 1;

        case LSP:
        case PUSH:
        case POP:
        case NEG:
        case INT:
            return 2;

        case ADD:
        case MUL:
        case DIV:
        case MOD:
        case CMP:
            return 3;

        case CALL:
        case JA:
        case JE:
        case JB:
        case JMP:
            return 5;

        case LOAD:
        case STORE:
        case CONST:
            return 6;

        default:
            return 0;
    }
}

static bool STACK_IS_EMPTY(TOYVM* vm)
{
    return vm->cpu.stack_pointer >= vm->memory_size;
}

static bool STACK_IS_FULL(TOYVM* vm)
{
    return vm->cpu.stack_pointer <= vm->stack_limit;
}

static int32_t AVAILABLE_STACK_SIZE(TOYVM* vm)
{
    return vm->cpu.stack_pointer - vm->stack_limit;
}

static int32_t OCCUPIED_STACK_SIZE(TOYVM* vm)
{
    return vm->memory_size - vm->cpu.stack_pointer;
}

static bool CAN_PERFORM_MULTIPUSH(TOYVM* vm)
{
    return AVAILABLE_STACK_SIZE(vm) >= sizeof(int32_t) * N_REGISTERS;
}

static bool CAN_PERFORM_MULTIPOP(TOYVM* vm)
{
    return OCCUPIED_STACK_SIZE(vm) >= sizeof(int32_t) * N_REGISTERS;
}

void INIT_VM(TOYVM* vm, int32_t memory_size, int32_t stack_limit)
{
    /* Make sure both 'memory_size' and 'stack_limit' are divisible by 4. */
    memory_size
        += sizeof(int32_t) - (memory_size % sizeof(int32_t));

    stack_limit
        += sizeof(int32_t) - (stack_limit % sizeof(int32_t));

    vm->memory              = calloc(memory_size, sizeof(uint8_t));
    vm->memory_size         = memory_size;
    vm->stack_limit         = stack_limit;
    vm->cpu.program_counter = 0;
    vm->cpu.stack_pointer   = (int32_t) memory_size;
    memset(vm->cpu.registers, 0, sizeof(int32_t) * N_REGISTERS);
}

void WRITE_VM_MEMORY(TOYVM* vm, uint8_t* mem, size_t size)
{
    memcpy(mem, vm->memory, size);
}

static int32_t READ_WORD(TOYVM* vm, int32_t address)
{
    uint8_t b1 = vm->memory[address];
    uint8_t b2 = vm->memory[address + 1];
    uint8_t b3 = vm->memory[address + 2];
    uint8_t b4 = vm->memory[address + 3];

    /* ToyVM is little-endian. */
    return (int32_t)((b4 << 24) | (b3 << 16) | (b2 << 8) | b1);
}

static void WRITE_WORD(TOYVM* vm, int32_t address, int32_t value)
{
    uint8_t b1 =  value & 0xff;
    uint8_t b2 = (value & 0xff00) >> 8;
    uint8_t b3 = (value & 0xff0000) >> 16;
    uint8_t b4 = (value & 0xff000000) >> 24;

    vm->memory[address]     = b1;
    vm->memory[address + 1] = b2;
    vm->memory[address + 2] = b3;
    vm->memory[address + 3] = b4;
}

static uint8_t READ_BYTE(TOYVM* vm, size_t address)
{
    return vm->memory[address];
}

static int32_t POP_VM(TOYVM* vm)
{
    if (STACK_IS_EMPTY(vm))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return 0;
    }

    int32_t word = READ_WORD(vm, vm->cpu.stack_pointer);
    vm->cpu.stack_pointer += 4;
    return word;
}

static void PUSH_VM(TOYVM* vm, uint32_t value)
{
    WRITE_WORD(vm, vm->cpu.stack_pointer -= 4, value);
}

static bool IS_VALID_REGISTER_INDEX(uint8_t byte)
{
    switch (byte)
    {
        case REG1:
        case REG2:
        case REG3:
        case REG4:
            return true;
    }

    return false;
}

/*******************************************************************************
* Checks that an instruction fits entirely in the memory.                      *
*******************************************************************************/
static bool INSTRUCTION_FITS_IN_MEMORY(TOYVM* vm, uint8_t opcode)
{
    size_t instruction_length = GET_INSTRUCTION_LENGTH(opcode);
    return vm->cpu.program_counter + instruction_length <= vm->memory_size;
}

static int32_t PROGRAM_COUNTER(TOYVM* vm)
{
    return vm->cpu.program_counter;
}

static bool EXECUTE_ADD(TOYVM* vm)
{
    uint8_t source_register_index;
    uint8_t target_register_index;

    if (!INSTRUCTION_FITS_IN_MEMORY(vm, ADD))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    source_register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);
    target_register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 2);

    if (!IS_VALID_REGISTER_INDEX(source_register_index) ||
        !IS_VALID_REGISTER_INDEX(target_register_index))
    {
        vm->cpu.status.INVALID_REGISTER_INDEX = 1;
        return false;
    }

    vm->cpu.registers[target_register_index]
        += vm->cpu.registers[source_register_index];

    /* Advance the program counter past this instruction. */
    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(ADD);
    return true;
}

static bool EXECUTE_NEG(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, NEG))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    uint8_t register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);

    if (!IS_VALID_REGISTER_INDEX(register_index))
    {
        vm->cpu.status.INVALID_REGISTER_INDEX = 1;
        return false;
    }

    vm->cpu.registers[register_index] = -vm->cpu.registers[register_index];
    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(NEG);
    return true;
}

static bool EXECUTE_MUL(TOYVM* vm)
{
    uint8_t source_register_index;
    uint8_t target_register_index;

    if (!INSTRUCTION_FITS_IN_MEMORY(vm, MUL))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    source_register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);
    target_register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 2);

    if (!IS_VALID_REGISTER_INDEX(source_register_index) ||
        !IS_VALID_REGISTER_INDEX(target_register_index))
    {
        vm->cpu.status.INVALID_REGISTER_INDEX = 1;
        return false;
    }

    vm->cpu.registers[target_register_index] *=
    vm->cpu.registers[source_register_index];
    /* Advance the program counter past this instruction. */
    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(MUL);
    return true;
}

static bool EXECUTE_DIV(TOYVM* vm)
{
    uint8_t source_register_index;
    uint8_t target_register_index;

    if (!INSTRUCTION_FITS_IN_MEMORY(vm, DIV))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    source_register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);
    target_register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 2);

    if (!IS_VALID_REGISTER_INDEX(source_register_index) ||
        !IS_VALID_REGISTER_INDEX(target_register_index))
    {
        vm->cpu.status.INVALID_REGISTER_INDEX = 1;
        return false;
    }

    vm->cpu.registers[target_register_index] /=
    vm->cpu.registers[source_register_index];
    /* Advance the program counter past this instruction. */
    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(DIV);
    return true;
}

static bool EXECUTE_MOD(TOYVM* vm)
{
    uint8_t source_register_index;
    uint8_t target_register_index;

    if (!INSTRUCTION_FITS_IN_MEMORY(vm, MOD))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    source_register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);
    target_register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 2);

    if (!IS_VALID_REGISTER_INDEX(source_register_index) ||
        !IS_VALID_REGISTER_INDEX(target_register_index))
    {
        vm->cpu.status.INVALID_REGISTER_INDEX = 1;
        return false;
    }

    vm->cpu.registers[target_register_index] =
        vm->cpu.registers[source_register_index] %
        vm->cpu.registers[target_register_index];

    /* Advance the program counter past this instruction. */
    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(MOD);
    return true;
}

static bool EXECUTE_CMP(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, CMP))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    uint8_t register_index_1 = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);
    uint8_t register_index_2 = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 2);

    if (!IS_VALID_REGISTER_INDEX(register_index_1) ||
        !IS_VALID_REGISTER_INDEX(register_index_2))
    {
        vm->cpu.status.INVALID_REGISTER_INDEX = 1;
        return false;
    }

    int32_t register_1 = vm->cpu.registers[register_index_1];
    int32_t register_2 = vm->cpu.registers[register_index_2];

    if (register_1 < register_2)
    {
        vm->cpu.status.COMPARISON_ABOVE = 0;
        vm->cpu.status.COMPARISON_EQUAL = 0;
        vm->cpu.status.COMPARISON_BELOW = 1;
    }
    else if (register_1 > register_2)
    {
        vm->cpu.status.COMPARISON_ABOVE = 1;
        vm->cpu.status.COMPARISON_EQUAL = 0;
        vm->cpu.status.COMPARISON_BELOW = 0;
    }
    else
    {
        vm->cpu.status.COMPARISON_ABOVE = 0;
        vm->cpu.status.COMPARISON_EQUAL = 1;
        vm->cpu.status.COMPARISON_BELOW = 0;
    }

    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(CMP);
    return true;
}

static bool EXECUTE_JA(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, JA))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    if (vm->cpu.status.COMPARISON_ABOVE)
    {
        vm->cpu.program_counter = READ_WORD(vm, PROGRAM_COUNTER(vm) + 1);
    }
    else
    {
        vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(JA);
    }

    return true;
}

static bool EXECUTE_JE(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, JE))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    if (vm->cpu.status.COMPARISON_EQUAL)
    {
        vm->cpu.program_counter = READ_WORD(vm, PROGRAM_COUNTER(vm) + 1);
    }
    else
    {
        vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(JE);
    }

    return true;
}

static bool EXECUTE_JB(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, JB))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    if (vm->cpu.status.COMPARISON_BELOW)
    {
        vm->cpu.program_counter = READ_WORD(vm, PROGRAM_COUNTER(vm) + 1);
    }
    else
    {
        vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(JB);
    }

    return true;
}

static bool EXECUTE_JMP(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, JMP))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    vm->cpu.program_counter = READ_WORD(vm, PROGRAM_COUNTER(vm) + 1);
    return true;
}

static bool EXECUTE_CALL(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, CALL))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    if (AVAILABLE_STACK_SIZE(vm) < 4)
    {
        vm->cpu.status.STACK_OVERFLOW = 1;
        return false;
    }

    /* Save the return address on the stack. */
    uint32_t address = READ_WORD(vm, PROGRAM_COUNTER(vm) + 1);
    PUSH_VM(vm, (uint32_t)(PROGRAM_COUNTER(vm) + GET_INSTRUCTION_LENGTH(CALL)));
    /* Actual jump to the subroutine. */
    vm->cpu.program_counter = address;
    return true;
}

static bool EXECUTE_RET(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, RET))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    if (STACK_IS_EMPTY(vm))
    {
        vm->cpu.stack_pointer |= STATUS_STACK_UNDERFLOW;
        return false;
    }

    vm->cpu.program_counter = POP_VM(vm);
    return true;
}

static bool EXECUTE_LOAD(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, LOAD))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    uint8_t register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);

    if (!IS_VALID_REGISTER_INDEX(register_index))
    {
        vm->cpu.status.INVALID_REGISTER_INDEX = 1;
        return false;
    }

    uint32_t address = READ_WORD(vm, PROGRAM_COUNTER(vm) + 2);
    vm->cpu.registers[register_index] = READ_WORD(vm, address);
    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(LOAD);
    return true;
}

static bool EXECUTE_STORE(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, STORE))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    uint8_t register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);

    if (!IS_VALID_REGISTER_INDEX(register_index))
    {
        vm->cpu.status.INVALID_REGISTER_INDEX = 1;
        return false;
    }

    uint32_t address = READ_WORD(vm, PROGRAM_COUNTER(vm) + 2);
    WRITE_WORD(vm, address, vm->cpu.registers[register_index]);
    return true;
}

static bool EXECUTE_CONST(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, CONST))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    uint8_t register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);
    int32_t datum = READ_WORD(vm, PROGRAM_COUNTER(vm) + 2);

    if (!IS_VALID_REGISTER_INDEX(register_index))
    {
        vm->cpu.status.INVALID_REGISTER_INDEX = 1;
        return false;
    }

    vm->cpu.registers[register_index] = datum;
    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(CONST);
    return true;
}

static void PRINT_STRING(TOYVM* vm, uint32_t address)
{
    printf("%s", (const char*)(&vm->memory[address]));
}

static bool EXECUTE_INT(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, INT))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    uint8_t interrupt_number = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);

    switch (interrupt_number)
    {
        case INTERRUPT_PRINT_INTEGER:
            if (STACK_IS_EMPTY(vm))
            {
                return false;
            }

            printf("%d", POP_VM(vm));
            break;

        case INTERRUPT_PRINT_STRING:
            if (STACK_IS_EMPTY(vm))
            {
                return false;
            }

            PRINT_STRING(vm, POP_VM(vm));
            break;

        default:
            return false;
    }

    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(INT);
    return true;
}

static bool EXECUTE_PUSH(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, PUSH))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    if (STACK_IS_FULL(vm))
    {
        return false;
    }

    uint8_t register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);

    if (!IS_VALID_REGISTER_INDEX(register_index))
    {
        vm->cpu.status.INVALID_REGISTER_INDEX = 1;
        return false;
    }

    WRITE_WORD(vm,
               vm->cpu.stack_pointer - 4,
               vm->cpu.registers[register_index]);

    vm->cpu.stack_pointer -= 4;
    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(PUSH);
    return true;
}

static bool EXECUTE_PUSH_ALL(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, PUSH_ALL))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    if (!CAN_PERFORM_MULTIPUSH(vm))
    {
        vm->cpu.status.STACK_OVERFLOW = 1;
        return false;
    }

    WRITE_WORD(vm, vm->cpu.stack_pointer -= 4, vm->cpu.registers[REG1]);
    WRITE_WORD(vm, vm->cpu.stack_pointer -= 4, vm->cpu.registers[REG2]);
    WRITE_WORD(vm, vm->cpu.stack_pointer -= 4, vm->cpu.registers[REG3]);
    WRITE_WORD(vm, vm->cpu.stack_pointer -= 4, vm->cpu.registers[REG4]);
    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(PUSH_ALL);
    return true;
}

static bool EXECUTE_POP(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, POP))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    if (STACK_IS_EMPTY(vm))
    {
        return false;
    }

    uint8_t register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);

    if (!IS_VALID_REGISTER_INDEX(register_index))
    {
        vm->cpu.status.INVALID_REGISTER_INDEX = 1;
        return false;
    }

    int32_t datum = READ_WORD(vm, PROGRAM_COUNTER(vm) + 2);
    vm->cpu.registers[register_index] = datum;
    vm->cpu.stack_pointer += 4;
    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(POP);
    return true;
}

static bool EXECUTE_POP_ALL(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, POP_ALL))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    if (!CAN_PERFORM_MULTIPOP(vm))
    {
        vm->cpu.status.STACK_UNDERFLOW = 1;
        return false;
    }

    vm->cpu.registers[REG4] = READ_WORD(vm, vm->cpu.stack_pointer);
    vm->cpu.registers[REG3] = READ_WORD(vm, vm->cpu.stack_pointer + 4);
    vm->cpu.registers[REG2] = READ_WORD(vm, vm->cpu.stack_pointer + 8);
    vm->cpu.registers[REG1] = READ_WORD(vm, vm->cpu.stack_pointer + 12);
    vm->cpu.stack_pointer += 16;
    vm->cpu.program_counter += GET_INSTRUCTION_LENGTH(POP_ALL);
    return true;
}

static bool EXECUTE_LSP(TOYVM* vm)
{
    if (!INSTRUCTION_FITS_IN_MEMORY(vm, LSP))
    {
        vm->cpu.status.BAD_ACCESS = 1;
        return false;
    }

    uint8_t register_index = READ_BYTE(vm, PROGRAM_COUNTER(vm) + 1);

    if (!IS_VALID_REGISTER_INDEX(register_index))
    {
        vm->cpu.status.INVALID_REGISTER_INDEX = 1;
        return false;
    }

    vm->cpu.registers[register_index] = vm->cpu.stack_pointer;
    return true;
}

void PRINT_STATUS(TOYVM* vm)
{
    printf("HALT_BAD_INSTRUCTION  : %d\n", vm->cpu.status.HALT_BAD_INSTRUCTION);
    printf("STACK_UNDERFLOW       : %d\n", vm->cpu.status.STACK_UNDERFLOW);
    printf("STACK_OVERFLOW        : %d\n", vm->cpu.status.STACK_OVERFLOW);
    printf("INVALID_REGISTER_INDEX: %d\n",
            vm->cpu.status.INVALID_REGISTER_INDEX);

    printf("BAD_ACCESS            : %d\n", vm->cpu.status.BAD_ACCESS);
    printf("COMPARISON_ABOVE      : %d\n", vm->cpu.status.COMPARISON_ABOVE);
    printf("COMPARISON_EQUAL      : %d\n", vm->cpu.status.COMPARISON_EQUAL);
    printf("COMPARISON_BELOW      : %d\n", vm->cpu.status.COMPARISON_BELOW);
}

void RUN_VM(TOYVM* vm)
{
    uint8_t opcode = NOP;

    while (opcode != HALT)
    {
        opcode = vm->memory[vm->cpu.program_counter];

        switch (opcode)
        {
            case ADD:
                if (!EXECUTE_ADD(vm)) return;

                break;

            case NEG:
                if (!EXECUTE_NEG(vm)) return;

                break;

            case MUL:
                if (!EXECUTE_MUL(vm)) return;

                break;

            case DIV:
                if (!EXECUTE_DIV(vm)) return;

                break;

            case MOD:
                if (!EXECUTE_MOD(vm)) return;

                break;

            case CMP:
                if (!EXECUTE_CMP(vm)) return;

                break;

            case JA:
                if (!EXECUTE_JA(vm)) return;

                break;

            case JE:
                if (!EXECUTE_JE(vm)) return;

                break;

            case JB:
                if (!EXECUTE_JB(vm)) return;

                break;

            case JMP:
                if (!EXECUTE_JMP(vm)) return;

                break;

            case CALL:
                if (!EXECUTE_CALL(vm)) return;

                break;

            case RET:
                if (!EXECUTE_RET(vm)) return;

                break;

            case LOAD:
                if (!EXECUTE_LOAD(vm)) return;

                break;

            case STORE:
                if (!EXECUTE_STORE(vm)) return;

                break;

            case CONST:
                if (!EXECUTE_CONST(vm)) return;

                break;

            case PUSH:
                if (!EXECUTE_PUSH(vm)) return;

                break;

            case PUSH_ALL:
                if (!EXECUTE_PUSH_ALL(vm)) return;

                break;

            case POP:
                if (!EXECUTE_POP(vm)) return;

                break;

            case POP_ALL:
                if (!EXECUTE_POP_ALL(vm)) return;

                break;

            case LSP:
                if (!EXECUTE_LSP(vm)) return;

                break;

            case HALT:
                return;

            case INT:
                if (!EXECUTE_INT(vm)) return;

                break;

            case NOP:
                /* Do nothing. */
                break;

            default:
                vm->cpu.status.HALT_BAD_INSTRUCTION = 1;
                return;
        }
    }
}

#endif /* TOYVM_H */

main.c:

#include <stdio.h>
#include "toyvm.h"

int main(int argc, const char * argv[]) {
    TOYVM vm;
    INIT_VM(&vm, 1024, 512);

    // CONST REG4 100
    vm.memory[0] = CONST;
    vm.memory[1] = REG4;
    WRITE_WORD(&vm, 2, 100);

    // CONST REG2 1
    vm.memory[6] = CONST;
    vm.memory[7] = REG2;
    WRITE_WORD(&vm, 8, 1);

    // [12] ADD REG2 REG1
    vm.memory[12] = ADD;
    vm.memory[13] = REG2;
    vm.memory[14] = REG1;

    // CMP REG1 REG4
    vm.memory[15] = CMP;
    vm.memory[16] = REG1;
    vm.memory[17] = REG4;

    // JA 200
    vm.memory[18] = JA;
    WRITE_WORD(&vm, 19, 200);

    // PUSH_ALL
    vm.memory[23] = PUSH_ALL;

    // CALL 50
    vm.memory[24] = CALL;
    WRITE_WORD(&vm, 25, 50);

    // POP_ALL
    vm.memory[29] = POP_ALL;

    // JMP
    vm.memory[30] = JMP;
    WRITE_WORD(&vm, 31, 12);

//[50] CONST REG2 15
    vm.memory[50] = CONST;
    vm.memory[51] = REG2;
    WRITE_WORD(&vm, 52, 15);

    // MOD REG1 REG2
    vm.memory[56] = MOD;
    vm.memory[57] = REG1;
    vm.memory[58] = REG2;

    // CONST REG3 0
    vm.memory[59] = CONST;
    vm.memory[60] = REG3;
    WRITE_WORD(&vm, 61, 0);

    // CMP REG2 REG3
    vm.memory[65] = CMP;
    vm.memory[66] = REG2;
    vm.memory[67] = REG3;

    // JB 93
    vm.memory[68] = JB;
    WRITE_WORD(&vm, 69, 93);

    // JA 93
    vm.memory[73] = JA;
    WRITE_WORD(&vm, 74, 93);

    // CONST REG3 300
    vm.memory[78] = CONST;
    vm.memory[79] = REG3;
    WRITE_WORD(&vm, 80, 340);

    // PUHS REG3
    vm.memory[84] = PUSH;
    vm.memory[85] = REG3;

    // INT 2
    vm.memory[86] = INT;
    vm.memory[87] = INTERRUPT_PRINT_STRING;

    // JMP 193
    vm.memory[88] = JMP;
    WRITE_WORD(&vm, 89, 193);

////////////////////////////
//[93] CONST REG2 5
    vm.memory[93] = CONST;
    vm.memory[94] = REG2;
    WRITE_WORD(&vm, 95, 5);

    // MOD REG1 REG2
    vm.memory[99] = MOD;
    vm.memory[100] = REG1;
    vm.memory[101] = REG2;

    // CONST REG3 0
    vm.memory[102] = CONST;
    vm.memory[103] = REG3;
    WRITE_WORD(&vm, 104, 0);

    // CMP REG2 REG3
    vm.memory[108] = CMP;
    vm.memory[109] = REG2;
    vm.memory[110] = REG3;

    // JB 136
    vm.memory[111] = JB;
    WRITE_WORD(&vm, 112, 136);

    // JA 136
    vm.memory[116] = JA;
    WRITE_WORD(&vm, 117, 136);

    // CONST REG3 320
    vm.memory[121] = CONST;
    vm.memory[122] = REG3;
    WRITE_WORD(&vm, 123, 320);

    // PUHS REG3
    vm.memory[127] = PUSH;
    vm.memory[128] = REG3;

    // INT 2
    vm.memory[129] = INT;
    vm.memory[130] = 2;

    // JMP 193
    vm.memory[131] = JMP;
    WRITE_WORD(&vm, 132, 193);

//////////////////////////
//[136] CONST REG2 3
    vm.memory[136] = CONST;
    vm.memory[137] = REG2;
    WRITE_WORD(&vm, 138, 3);

    // MOD REG1 REG2
    vm.memory[142] = MOD;
    vm.memory[143] = REG1;
    vm.memory[144] = REG2;

    // CONST REG3 0
    vm.memory[145] = CONST;
    vm.memory[146] = REG3;
    WRITE_WORD(&vm, 147, 0);

    // CMP REG2 REG3
    vm.memory[151] = CMP;
    vm.memory[152] = REG2;
    vm.memory[153] = REG3;

    // JB 179
    vm.memory[154] = JB;
    WRITE_WORD(&vm, 155, 179);

    // JA 179
    vm.memory[159] = JA;
    WRITE_WORD(&vm, 160, 179);

    // CONST REG3 340
    vm.memory[164] = CONST;
    vm.memory[165] = REG3;
    WRITE_WORD(&vm, 166, 300);

    // PUHS REG3
    vm.memory[170] = PUSH;
    vm.memory[171] = REG3;

    // INT 2
    vm.memory[172] = INT;
    vm.memory[173] = 2;

    // JMP 193
    vm.memory[174] = JMP;
    WRITE_WORD(&vm, 175, 193);
    ////

//[179]: PUSH REG1
    vm.memory[179] = PUSH;
    vm.memory[180] = REG1;

    // INT 1
    vm.memory[181] = INT;
    vm.memory[182] = INTERRUPT_PRINT_INTEGER;

    // CONST REG4 350
    vm.memory[183] = CONST;
    vm.memory[184] = REG4;
    WRITE_WORD(&vm, 185, 350);

    // PUSH REG4
    vm.memory[189] = PUSH;
    vm.memory[190] = REG4;

    // INT INTEGER
    vm.memory[191] = INT;
    vm.memory[192] = INTERRUPT_PRINT_STRING;

//[193]:
    vm.memory[193] = RET;
    vm.memory[200] = HALT;

    memcpy(&vm.memory[300], "Fizz\n", strlen("Fizz\n"));
    memcpy(&vm.memory[320], "Buzz\n", strlen("Buzz\n"));
    memcpy(&vm.memory[340], "FizzBuzz\n", strlen("FizzBuzz\n"));
    memcpy(&vm.memory[350], "\n", strlen("\n"));

    RUN_VM(&vm);

    puts("\n--- MACHINE STATUS ---");
    PRINT_STATUS(&vm);
    return 0;
}

Please, tell me anything that comes to mind. (Also, I don't have any assembler for ToyVM, so had to code FizzBuzz at instruction set level.)

\$\endgroup\$
  • 1
    \$\begingroup\$ The first thing that springs to mind is you have virtually no comments or documentation. This makes it hard to read and understand, particularly if someone is not familiar with the design of a VM. You have functions in the header file which is generally not a good idea, and also the entire VM is in one file. Splitting it across files would be a good idea. Also, do you have any kind of testing/unit testing for the VM? Testing is important, and especially with something like a VM that can have so many edge cases that are hard to debug etc. \$\endgroup\$ – user9993 Mar 9 '16 at 17:27
  • \$\begingroup\$ Fair enough. Unfortunately, the only "test" is the Fizz Buzz in the demo. \$\endgroup\$ – coderodde Mar 9 '16 at 17:28
  • 1
    \$\begingroup\$ One last point, you use bitfields which are a sadly broken feature of C that often can only be solved by using bitmasks instead. Bitfields are broken because the C standard is (typical for the C standard) ambiguous about bitfields meaning that the order of the bits is entirely architecture and even compiler dependant. This means your VM might work fine on one machine but not on another. \$\endgroup\$ – user9993 Mar 9 '16 at 17:29
  • 1
    \$\begingroup\$ @user9993 Bitfields are not broken if used correctly, as in this code. This code does not rely on the packing or ordering of the individual fields (which are the problematic, nonportable things some try to use) and therefore this VM will work as intended on any platform for which there is a compliant C compiler. \$\endgroup\$ – Edward Mar 9 '16 at 18:39
11
\$\begingroup\$

I see a number of things that may help you improve your code.

Don't use const where it is forbidden

Normally, I'd prefer to use const as you've done in this code. However, there are circumstances in C where it's not allowed and several of those instances appear in your code. The first is with the registers array in VM_CPU and the second is all of the opcode cases within the switch. See this question for why that's a problem. There are two possible fixes. One would be to use an enum:

enum { N_REGISTERS = 4 };

and the other is to use #define

#define N_REGISTERS 4

Of the two, I think I'd prefer the enum flavor for this code. It means that at least you have an integral type, even though you can't really declare it to be size_t type (or uint8_t type in the case of the opcodes).

Separate interface from implementation

The interface goes into a header file and the implementation (that is, everything that actually emits bytes including all functions and data) should be in a separate .c file. The reason is that you might have multiple source files including the .h file but only one instance of the corresponding .c file. In other words, split your existing toyvm.h file into a .h file and a .c file.

Initialize completely

The INIT_VM function does not set the status, so the effect is that the PRINT_STATUS call is relying the values of uninitialized memory. Better would be to completely initialize the virtual CPU in the same way that a real CPU is initialized by a reset signal.

Write for the typical usage

In every case in which an EXECUTE_xxx() function is executed, its return value is negated before testing. Why not invert the sense of those functions so that they return true on error? It would save some code.

Consider an alternate data representation

At the moment, information about each instruction is manifest in several different places. There is the name of it, the value of the opcode, the instruction length and the code that implements the instruction. I'd suggest gathering all of that together into a struct:

struct instruction {
    uint8_t opcode;
    char *name;
    unsigned size;
    bool (*evaluate)(TOYVM *);
};

const struct instruction instructions[] = {
    { ADD, "ADD", 3, EXECUTE_ADD },
    { NEG, "NEG", 2, EXECUTE_NEG },
    // etc.
};

Then execution of each instruction would simply be a matter of table lookup and the calling the evaluate function. You might wish to also incorporate functions for assemble and disassemble as well to make it extremely easy to write assembler, diassembler and related tools.

Reconsider naming convention

Having all of the functions all caps like INSTRUCTION_FITS_IN_MEMORY is not typical. More often that's used for #define names and functions are in mixed case. Following a more conventional convention will help others read and understand your code.

Eliminate return 0 at the end of main

Since C99, the compiler automatically generates the code corresponding to return 0 at the end of main so there is no need to explicitly write it.

\$\endgroup\$
7
\$\begingroup\$

FizzBuzz

When you write the string constants to memory using memcpy(), you need to copy the NUL terminator too.

There is an odd gap in the program between offsets 32 and 49.

Implementation

The EXECUTE_instruction() functions are all pretty repetitive. You could factor out the validation into the decoding loop.

Library design

This virtual machine is too complex to be a header-only library. It should be split into a toyvm.h and a toyvm.c. A lot of these functions should be renamed so that they don't look like macros. I suggest names like vm_init(), vm_run(), vm_print_status(), etc., so that the library has a coherent naming scheme.

Even if you did want a header-only library, you would have to be sure to declare every function static. Otherwise, you will run into problems if the program links more than one .c file that includes toyvm.h.

There should be better status reporting, namely a non-zero exit status on failure. Diagnostic information should be printed to stderr so as not to contaminate stdout.

You said you don't have an assembler. Still, I find it dissatisfying that your FizzBuzz program is hard-coded as instructions within main() rather than treated as data. The project should look more like this:

#include <stdio.h>
#include "toyvm.h"

static uint8_t FIZZBUZZ[] = {
    /*   0 */ CONST, REG4, WORD(100),
    /*   6 */ CONST, REG2, WORD(1),
    /*  12 */ ADD, REG2, REG1,
    /*  15 */ CMP, REG1, REG4,
    /*  18 */ JA, WORD(200),
    /*  23 */ PUSH_ALL,
    /*  24 */ CALL, WORD(50),
    /*  29 */ POP_ALL,
    /*  30 */ JMP, WORD(12),
              0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    /*  50 */ CONST, REG2, WORD(15),
    /*  56 */ MOD, REG1, REG2,
    /*  59 */ CONST, REG3, WORD(0),
    /*  65 */ CMP, REG2, REG3,
    /*  68 */ JB, WORD(93),
    /*  73 */ JA, WORD(93),
    /*  78 */ CONST, REG3, WORD(340),
    /*  84 */ PUSH, REG3,
    /*  86 */ INT, INTERRUPT_PRINT_STRING,
    /*  88 */ JMP, WORD(193),

    /*  93 */ CONST, REG2, WORD(5),
    /*  99 */ MOD, REG1, REG2,
    /* 102 */ CONST, REG3, WORD(0),
    /* 108 */ CMP, REG2, REG3,
    /* 111 */ JB, WORD(136),
    /* 116 */ JA, WORD(136),
    /* 121 */ CONST, REG3, WORD(320),
    /* 127 */ PUSH, REG3,
    /* 129 */ INT, 2,
    /* 131 */ JMP, WORD(193),

    /* 136 */ CONST, REG2, WORD(3),
    /* 142 */ MOD, REG1, REG2,
    /* 145 */ CONST, REG3, WORD(0),
    /* 151 */ CMP, REG2, REG3,
    /* 154 */ JB, WORD(179),
    /* 159 */ JA, WORD(179),
    /* 164 */ CONST, REG3, WORD(300),
    /* 170 */ PUSH, REG3,
    /* 172 */ INT, 2,
    /* 174 */ JMP, WORD(193),

    /* 179 */ PUSH, REG1,
    /* 181 */ INT, INTERRUPT_PRINT_INTEGER,
    /* 183 */ CONST, REG4, WORD(350),
    /* 189 */ PUSH, REG4,
    /* 191 */ INT, INTERRUPT_PRINT_STRING,
    /* 193 */ RET,
    /* 194 */ HALT
};

int main(int argc, const char * argv[]) {
    TOYVM vm;
    vm_init(&vm, 1024, 512);

    vm_write_mem(&vm, 0, FIZZBUZZ, sizeof FIZZBUZZ);
    vm_write_mem(&vm, 300, "Fizz\n", strlen("Fizz\n") + 1);
    vm_write_mem(&vm, 320, "Buzz\n", strlen("Buzz\n") + 1);
    vm_write_mem(&vm, 340, "FizzBuzz\n", strlen("FizzBuzz\n") + 1);
    vm_write_mem(&vm, 350, "\n", strlen("\n") + 1);

    int status = vm_run(&vm);
    vm_print_status(&vm, stderr);
    return status;
}

Here, WORD is a macro defined in toyvm.h:

#define WORD(le32val) (le32val >>  0 & 0xff), \
                      (le32val >>  8 & 0xff), \
                      (le32val >> 16 & 0xff), \
                      (le32val >> 24 & 0xff)
\$\endgroup\$
  • \$\begingroup\$ A minor comment on the very first point in FizzBuzz section: upon initialization the machine sets all memory to zero. \$\endgroup\$ – coderodde Mar 12 '16 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.