Implement a stack-based bytecode virtual machine with an assembler in C11 in this direc…

codexgpt-5.6-terra · 86 steps · 9m 00s · 9 filessession ddf0dfec-8dd@patrick-toulme
Implement a stack-based bytecode virtual machine with an assembler in C11 in this directory. Files: vm.c, vm.h (the VM: operand stack, call stack, ops PUSH, POP, DUP, SWAP, ADD, SUB, MUL, DIV, MOD, NEG, EQ, LT, GT, JMP, JZ, JNZ, CALL, RET, LOAD, STORE for 16 locals per frame, PRINT, HALT; robust error handling for stack under/overflow, division by zero, bad opcodes, out-of-range jumps), asm.c (a two-pass assembler from mnemonic text with labels and comments to bytecode), examples/ (fib.vasm computing fib(20) recursively, fact.vasm computing 10! iteratively, primes.vasm printing primes below 50), tests.c (runs each example through assembler+VM and asserts exact output; plus negative tests for each error path), Makefile (clang -std=c11 -Wall -Wextra -fsanitize=address). Build with make, run the tests under ASan, and fix failures until everything passes clean.
same matchclaude-code · 45 steps codex · 86 steps opencode · 46 steps pi · 59 steps antigravity · 28 steps
compare in arena
step 83 / 86
vm.cchange 1/1
#include "vm.h"
 
#include <inttypes.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct VMFileOutput {
    FILE *stream;
} VMFileOutput;
 
static VMError vm_fail(VM *vm, VMError error, size_t pc)
{
    if (vm != NULL) {
        vm->error = error;
        vm->error_pc = pc;
        vm->halted = 0;
    }
    return error;
}
 
static int opcode_is_valid(uint8_t opcode)
{
    return opcode >= VM_OP_PUSH && opcode <= VM_OP_HALT;
}
 
int vm_opcode_has_operand(uint8_t opcode)
{
    switch (opcode) {
    case VM_OP_PUSH:
    case VM_OP_JMP:
    case VM_OP_JZ:
    case VM_OP_JNZ:
    case VM_OP_CALL:
    case VM_OP_LOAD:
    case VM_OP_STORE:
        return 1;
    default:
        return 0;
    }
}
 
static size_t opcode_width(uint8_t opcode)
{
    if (!opcode_is_valid(opcode)) {
        return 0;
    }
    return VM_OPCODE_SIZE + (vm_opcode_has_operand(opcode) ? VM_OPERAND_SIZE : 0);
}
 
static int32_t read_i32_le(const uint8_t *bytes)
{
    uint32_t value = (uint32_t)bytes[0]
        | ((uint32_t)bytes[1] << 8)
        | ((uint32_t)bytes[2] << 16)
        | ((uint32_t)bytes[3] << 24);
 
    /* Avoid relying on an unsigned-to-signed representation conversion. */
    if (value <= INT32_MAX) {
        return (int32_t)value;
    }
    return (int32_t)((int64_t)value - ((int64_t)UINT32_MAX + 1));
}
 
/*
 * Validate every instruction before executing.  In addition to bounds checks,
 * the start map makes it impossible to jump into an immediate operand.
 */
static VMError validate_program(VM *vm, const uint8_t *code, size_t code_len)
{
    uint8_t *starts;
    size_t pc;
 
    if (code == NULL && code_len != 0) {
        return vm_fail(vm, VM_ERR_INVALID_ARGUMENT, 0);
    }
    if (code_len == 0) {
        return VM_OK;
    }
 
    starts = calloc(code_len, sizeof(*starts));
    if (starts == NULL) {
        return vm_fail(vm, VM_ERR_ALLOCATION, 0);
    }
 
    pc = 0;
    while (pc < code_len) {
        size_t width;
 
        starts[pc] = 1;
        width = opcode_width(code[pc]);
        if (width == 0) {
            free(starts);
            return vm_fail(vm, VM_ERR_BAD_OPCODE, pc);
        }
        if (code_len - pc < width) {
            free(starts);
            return vm_fail(vm, VM_ERR_TRUNCATED_INSTRUCTION, pc);
        }
        pc += width;
    }
 
    pc = 0;
    while (pc < code_len) {
        uint8_t opcode = code[pc];
        size_t width = opcode_width(opcode);
 
        if (vm_opcode_has_operand(opcode)) {
            int32_t operand = read_i32_le(code + pc + VM_OPCODE_SIZE);
 
            if (opcode == VM_OP_JMP || opcode == VM_OP_JZ
                || opcode == VM_OP_JNZ || opcode == VM_OP_CALL) {
                if (operand < 0 || (size_t)operand >= code_len
                    || starts[(size_t)operand] == 0) {
                    free(starts);
                    return vm_fail(vm, VM_ERR_INVALID_JUMP, pc);
                }
            } else if ((opcode == VM_OP_LOAD || opcode == VM_OP_STORE)
                       && (operand < 0 || operand >= VM_LOCALS_PER_FRAME)) {
                free(starts);
                return vm_fail(vm, VM_ERR_INVALID_LOCAL, pc);
            }
        }
        pc += width;
    }
 
    free(starts);
    return VM_OK;
}
 
static int add_overflows_i64(int64_t left, int64_t right, int64_t *result)
{
    if ((right > 0 && left > INT64_MAX - right)
        || (right < 0 && left < INT64_MIN - right)) {
        return 1;
    }
    *result = left + right;
    return 0;
}
 
static int sub_overflows_i64(int64_t left, int64_t right, int64_t *result)
{
    if ((right > 0 && left < INT64_MIN + right)
        || (right < 0 && left > INT64_MAX + right)) {
        return 1;
    }
    *result = left - right;
    return 0;
}
 
static int mul_overflows_i64(int64_t left, int64_t right, int64_t *result)
{
    if (left == 0 || right == 0) {
        *result = 0;
        return 0;
    }
    if (left == -1) {
        if (right == INT64_MIN) {
            return 1;
        }
        *result = -right;
        return 0;
    }
    if (right == -1) {
        if (left == INT64_MIN) {
            return 1;
        }
        *result = -left;
        return 0;
    }
 
    if (left > 0) {
        if (right > 0) {
            if (left > INT64_MAX / right) {
                return 1;
            }
        } else if (right < INT64_MIN / left) {
            return 1;
        }
    } else if (right > 0) {
        if (left < INT64_MIN / right) {
            return 1;
        }
    } else if (left < INT64_MAX / right) {
        /* Both operands are negative, so the product must fit positively. */
        return 1;
    }
 
    *result = left * right;
    return 0;
}
 
static int file_output(void *user, int64_t value)
{
    VMFileOutput *output = user;
 
    return fprintf(output->stream, "%" PRId64 "\n", value) < 0 ? -1 : 0;
}
 
int vm_init(VM *vm, size_t max_stack, size_t max_call_frames)
{
    if (vm == NULL) {
        return -1;
    }
 
    memset(vm, 0, sizeof(*vm));
    if (max_stack == 0) {
        max_stack = VM_DEFAULT_STACK_LIMIT;
    }
    if (max_call_frames == 0) {
        max_call_frames = VM_DEFAULT_CALL_STACK_LIMIT;
    }
    if (max_stack > SIZE_MAX / sizeof(*vm->stack)
        || max_call_frames > SIZE_MAX / sizeof(*vm->frames)) {
        vm->error = VM_ERR_ALLOCATION;
        return -1;
    }
 
    vm->stack = calloc(max_stack, sizeof(*vm->stack));
    vm->frames = calloc(max_call_frames, sizeof(*vm->frames));
    if (vm->stack == NULL || vm->frames == NULL) {
        free(vm->stack);
        free(vm->frames);
        vm->stack = NULL;
        vm->frames = NULL;
        vm->error = VM_ERR_ALLOCATION;
        return -1;
    }
 
    vm->stack_capacity = max_stack;
    vm->frame_capacity = max_call_frames;
    vm->max_stack = max_stack;
    vm->max_call_frames = max_call_frames;
    vm->error = VM_OK;
    return 0;
}
 
void vm_free(VM *vm)
{
    if (vm == NULL) {
        return;
    }
    free(vm->stack);
    free(vm->frames);
    memset(vm, 0, sizeof(*vm));
}
 
void vm_reset(VM *vm)
{
    if (vm == NULL) {
        return;
    }
    vm->stack_size = 0;
    vm->frame_count = 0;
    vm->error = VM_OK;
    vm->error_pc = 0;
    vm->halted = 0;
}
 
VMError vm_run_callback(VM *vm, const uint8_t *code, size_t code_len,
                        VMOutputFn output, void *output_user)
{
    VMError validation_error;
    size_t pc = 0;
 
    if (vm == NULL) {
        return VM_ERR_INVALID_ARGUMENT;
    }
    vm_reset(vm);
    if (vm->stack == NULL || vm->frames == NULL || vm->stack_capacity == 0
        || vm->frame_capacity == 0 || vm->max_stack == 0
        || vm->max_call_frames == 0) {
        return vm_fail(vm, VM_ERR_INVALID_ARGUMENT, 0);
    }
 
    validation_error = validate_program(vm, code, code_len);
    if (validation_error != VM_OK) {
        return validation_error;
    }
 
    /* The initial frame starts with all 16 locals set to zero. */
    memset(&vm->frames[0], 0, sizeof(vm->frames[0]));
    vm->frames[0].return_pc = SIZE_MAX;
    vm->frame_count = 1;
 
    while (pc < code_len) {
        size_t instruction_pc = pc;
        uint8_t opcode = code[pc++];
        int32_t operand = 0;
 
        if (vm_opcode_has_operand(opcode)) {
            /* validate_program has already verified the operand's four bytes. */
            operand = read_i32_le(code + pc);
            pc += VM_OPERAND_SIZE;
        }
 
        switch (opcode) {
        case VM_OP_PUSH:
            if (vm->stack_size >= vm->max_stack
                || vm->stack_size >= vm->stack_capacity) {
                return vm_fail(vm, VM_ERR_STACK_OVERFLOW, instruction_pc);
            }
            vm->stack[vm->stack_size++] = operand;
            break;
 
        case VM_OP_POP:
            if (vm->stack_size < 1) {
                return vm_fail(vm, VM_ERR_STACK_UNDERFLOW, instruction_pc);
            }
            --vm->stack_size;
            break;
 
        case VM_OP_DUP:
            if (vm->stack_size < 1) {
                return vm_fail(vm, VM_ERR_STACK_UNDERFLOW, instruction_pc);
            }
            if (vm->stack_size >= vm->max_stack
                || vm->stack_size >= vm->stack_capacity) {
                return vm_fail(vm, VM_ERR_STACK_OVERFLOW, instruction_pc);
            }
            vm->stack[vm->stack_size] = vm->stack[vm->stack_size - 1];
            ++vm->stack_size;
            break;
 
        case VM_OP_SWAP:
            if (vm->stack_size < 2) {
                return vm_fail(vm, VM_ERR_STACK_UNDERFLOW, instruction_pc);
            } else {
                int64_t top = vm->stack[vm->stack_size - 1];
                vm->stack[vm->stack_size - 1] = vm->stack[vm->stack_size - 2];
                vm->stack[vm->stack_size - 2] = top;
            }
            break;
 
        case VM_OP_ADD:
        case VM_OP_SUB:
        case VM_OP_MUL:
        case VM_OP_DIV:
        case VM_OP_MOD:
        case VM_OP_EQ:
        case VM_OP_LT:
        case VM_OP_GT:
            if (vm->stack_size < 2) {
                return vm_fail(vm, VM_ERR_STACK_UNDERFLOW, instruction_pc);
            } else {
                int64_t left = vm->stack[vm->stack_size - 2];
                int64_t right = vm->stack[vm->stack_size - 1];
                int64_t result;
 
                switch (opcode) {
                case VM_OP_ADD:
                    if (add_overflows_i64(left, right, &result)) {
                        return vm_fail(vm, VM_ERR_ARITHMETIC_OVERFLOW,
                                       instruction_pc);
                    }
                    break;
                case VM_OP_SUB:
                    if (sub_overflows_i64(left, right, &result)) {
                        return vm_fail(vm, VM_ERR_ARITHMETIC_OVERFLOW,
                                       instruction_pc);
                    }
                    break;
                case VM_OP_MUL:
                    if (mul_overflows_i64(left, right, &result)) {
                        return vm_fail(vm, VM_ERR_ARITHMETIC_OVERFLOW,
                                       instruction_pc);
                    }
                    break;
                case VM_OP_DIV:
                    if (right == 0) {
                        return vm_fail(vm, VM_ERR_DIVISION_BY_ZERO,
                                       instruction_pc);
                    }
                    if (left == INT64_MIN && right == -1) {
                        return vm_fail(vm, VM_ERR_ARITHMETIC_OVERFLOW,
                                       instruction_pc);
                    }
                    result = left / right;
                    break;
                case VM_OP_MOD:
                    if (right == 0) {
                        return vm_fail(vm, VM_ERR_DIVISION_BY_ZERO,
                                       instruction_pc);
                    }
                    if (left == INT64_MIN && right == -1) {
                        return vm_fail(vm, VM_ERR_ARITHMETIC_OVERFLOW,
                                       instruction_pc);
                    }
                    result = left % right;
                    break;
                case VM_OP_EQ:
                    result = left == right;
                    break;
                case VM_OP_LT:
                    result = left < right;
                    break;
                case VM_OP_GT:
                    result = left > right;
                    break;
                default:
                    return vm_fail(vm, VM_ERR_BAD_OPCODE, instruction_pc);
                }
 
                vm->stack[vm->stack_size - 2] = result;
                --vm->stack_size;
            }
            break;
 
        case VM_OP_NEG:
            if (vm->stack_size < 1) {
                return vm_fail(vm, VM_ERR_STACK_UNDERFLOW, instruction_pc);
            }
            if (vm->stack[vm->stack_size - 1] == INT64_MIN) {
                return vm_fail(vm, VM_ERR_ARITHMETIC_OVERFLOW, instruction_pc);
            }
            vm->stack[vm->stack_size - 1] = -vm->stack[vm->stack_size - 1];
            break;
 
        case VM_OP_JMP:
            pc = (size_t)operand;
            break;
 
        case VM_OP_JZ:
        case VM_OP_JNZ:
            if (vm->stack_size < 1) {
                return vm_fail(vm, VM_ERR_STACK_UNDERFLOW, instruction_pc);
            } else {
                int64_t condition = vm->stack[--vm->stack_size];
                if ((opcode == VM_OP_JZ && condition == 0)
                    || (opcode == VM_OP_JNZ && condition != 0)) {
                    pc = (size_t)operand;
                }
            }
            break;
 
        case VM_OP_CALL:
            if (vm->frame_count >= vm->max_call_frames
                || vm->frame_count >= vm->frame_capacity) {
                return vm_fail(vm, VM_ERR_CALL_STACK_OVERFLOW, instruction_pc);
            }
            memset(&vm->frames[vm->frame_count], 0,
                   sizeof(vm->frames[vm->frame_count]));
            vm->frames[vm->frame_count].return_pc = pc;
            ++vm->frame_count;
            pc = (size_t)operand;
            break;
 
        case VM_OP_RET:
            if (vm->frame_count <= 1) {
                return vm_fail(vm, VM_ERR_CALL_STACK_UNDERFLOW, instruction_pc);
            }
            --vm->frame_count;
            pc = vm->frames[vm->frame_count].return_pc;
            break;
 
        case VM_OP_LOAD:
            if (operand < 0 || operand >= VM_LOCALS_PER_FRAME) {
                return vm_fail(vm, VM_ERR_INVALID_LOCAL, instruction_pc);
            }
            if (vm->stack_size >= vm->max_stack
                || vm->stack_size >= vm->stack_capacity) {
                return vm_fail(vm, VM_ERR_STACK_OVERFLOW, instruction_pc);
            }
            vm->stack[vm->stack_size++] =
                vm->frames[vm->frame_count - 1].locals[(size_t)operand];
            break;
 
        case VM_OP_STORE:
            if (operand < 0 || operand >= VM_LOCALS_PER_FRAME) {
                return vm_fail(vm, VM_ERR_INVALID_LOCAL, instruction_pc);
            }
            if (vm->stack_size < 1) {
                return vm_fail(vm, VM_ERR_STACK_UNDERFLOW, instruction_pc);
            }
            vm->frames[vm->frame_count - 1].locals[(size_t)operand] =
                vm->stack[--vm->stack_size];
            break;
 
        case VM_OP_PRINT:
            if (vm->stack_size < 1) {
                return vm_fail(vm, VM_ERR_STACK_UNDERFLOW, instruction_pc);
            }
            if (output != NULL
                && output(output_user, vm->stack[vm->stack_size - 1]) != 0) {
                return vm_fail(vm, VM_ERR_OUTPUT, instruction_pc);
            }
            --vm->stack_size;
            break;
 
        case VM_OP_HALT:
            vm->halted = 1;
            vm->error = VM_OK;
            vm->error_pc = instruction_pc;
            return VM_OK;
 
        default:
            return vm_fail(vm, VM_ERR_BAD_OPCODE, instruction_pc);
        }
    }
 
    return vm_fail(vm, VM_ERR_NO_HALT, pc);
}
 
VMError vm_run(VM *vm, const uint8_t *code, size_t code_len, FILE *output)
{
    VMFileOutput file_sink;
 
    file_sink.stream = output;
    return vm_run_callback(vm, code, code_len,
                           output == NULL ? NULL : file_output, &file_sink);
}
 
const char *vm_error_string(VMError error)
{
    switch (error) {
    case VM_OK:
        return "success";
    case VM_ERR_INVALID_ARGUMENT:
        return "invalid argument";
    case VM_ERR_ALLOCATION:
        return "allocation failure";
    case VM_ERR_STACK_UNDERFLOW:
        return "operand stack underflow";
    case VM_ERR_STACK_OVERFLOW:
        return "operand stack overflow";
    case VM_ERR_CALL_STACK_UNDERFLOW:
        return "call stack underflow";
    case VM_ERR_CALL_STACK_OVERFLOW:
        return "call stack overflow";
    case VM_ERR_DIVISION_BY_ZERO:
        return "division by zero";
    case VM_ERR_ARITHMETIC_OVERFLOW:
        return "arithmetic overflow";
    case VM_ERR_BAD_OPCODE:
        return "bad opcode";
    case VM_ERR_TRUNCATED_INSTRUCTION:
        return "truncated instruction";
    case VM_ERR_INVALID_JUMP:
        return "invalid jump target";
    case VM_ERR_INVALID_LOCAL:
        return "invalid local index";
    case VM_ERR_OUTPUT:
        return "output failure";
    case VM_ERR_NO_HALT:
        return "program ended without HALT";
    default:
        return "unknown VM error";
    }
}
 
549 linesc
Delegates wait_agent
Files at this step
drag the rail to scrub
Discussion

No comments yet. Start the discussion. Recorded by @patrick-toulme.
#c #codex #gpt #gpt-5.6-terra #quick #subagents #testing
v2-codex
← all sessions