From ad01bb16238b8c9e88784fccedbe8b93a2732431 Mon Sep 17 00:00:00 2001 From: cassowarii Date: Sun, 28 Jun 2026 09:40:55 -0700 Subject: [PATCH] very basic VM/bytecode functionality! it works! we can add numbers! --- src/data/integer.c | 2 +- src/data/integer.h | 2 +- src/data/value.c | 6 +- src/data/value.h | 9 ++- src/main.c | 33 ++++++++ src/mem/buffer.c | 12 +-- src/mem/buffer.h | 2 +- src/vm/block.c | 36 ++++++--- src/vm/block.h | 20 ++++- src/vm/bytecode.h | 29 +++---- src/vm/exec.c | 220 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/vm/exec.h | 74 ++++++++++++++++++ 12 files changed, 402 insertions(+), 43 deletions(-) diff --git a/src/data/integer.c b/src/data/integer.c index 37d91b7..68dd5ee 100644 --- a/src/data/integer.c +++ b/src/data/integer.c @@ -36,7 +36,7 @@ void sbInteger_sys_init() { sbBuffer_initialize(&g_bigint_blocks, sizeof(intblk*)); } -hInteger sbInteger_new(u64 value) { +hInteger sbInteger_new(i64 value) { if (value >= SARABANDE_INT_MIN && value <= SARABANDE_INT_MAX) { return value; } else { diff --git a/src/data/integer.h b/src/data/integer.h index a0a6d15..2d6225a 100644 --- a/src/data/integer.h +++ b/src/data/integer.h @@ -7,7 +7,7 @@ void sbInteger_sys_init(); -hInteger sbInteger_new(u64 value); +hInteger sbInteger_new(i64 value); hInteger sbInteger_sum(hInteger a, hInteger b); diff --git a/src/data/value.c b/src/data/value.c index 1475de6..68f40d0 100644 --- a/src/data/value.c +++ b/src/data/value.c @@ -51,7 +51,7 @@ hV sbV_int(hInteger i) { }; } -flag sbV_eq(hV *a, hV *b) { +flag sbV_eq(const hV *a, const hV *b) { if (a->type != b->type) return FALSE; if (a->type == ITX_TOMBSTONE || b->type == ITX_TOMBSTONE) return FALSE; if (a->type == IT_NOTHING || b->type == IT_NOTHING) return FALSE; @@ -81,7 +81,7 @@ flag sbV_eq(hV *a, hV *b) { } } -void sbV_retain(hV *a) { +void sbV_retain(const hV *a) { /* for some classes (e.g. nil, float), we don't need to retain them at all * because they are trivially copiable. some classes (integer, string) need * to sometimes be retained but sometimes not, so we delegate to them to @@ -91,7 +91,7 @@ void sbV_retain(hV *a) { } } -void sbV_release(hV *a) { +void sbV_release(const hV *a) { if (a->type == IT_STRING) { sbString_release(a->string); } diff --git a/src/data/value.h b/src/data/value.h index 746637f..94a032d 100644 --- a/src/data/value.h +++ b/src/data/value.h @@ -3,6 +3,9 @@ #include "common.h" +#define HVINT(n) ((hV) { .type = IT_INTEGER, .integer = n }) +#define HVSTR(s) ((hV) { .type = IT_STRING, .string = OBJSL(s) }) + typedef u64 hHash; typedef u64 hString; typedef u64 hSymbol; @@ -43,9 +46,9 @@ hV sbV_float(double fl); hV sbV_hash(hHash hash); hV sbV_int(hInteger i); -flag sbV_eq(hV *a, hV *b); +flag sbV_eq(const hV *a, const hV *b); -void sbV_retain(hV *a); -void sbV_release(hV *a); +void sbV_retain(const hV *a); +void sbV_release(const hV *a); #endif diff --git a/src/main.c b/src/main.c index 684b332..d4d09e9 100644 --- a/src/main.c +++ b/src/main.c @@ -4,6 +4,7 @@ #include "data/string.h" #include "data/hashtable.h" #include "data/symbol.h" +#include "vm/exec.h" int main(int argc, char **argv) { if (argc == 2) { @@ -32,4 +33,36 @@ int main(int argc, char **argv) { } else { fprintf(stderr, "please provide a file as input\n"); } + + sbVm vm = {0}; + sbVm_initialize(&vm, 1048576, 1048576); + + sbVmProgram pm; + sbVmProgram_initialize(&pm, 65536); + + sbVmPartialBlock pb = sbVmBlock_create(4096, 4096); + + u8 code[] = { + BC_LD_CONST, 0x00, + BC_LD_CONST, 0x01, + BC_OP_ADD, + BC_HALT, + }; + + sbVmBlock_write_code(&pb, code, sizeof(code)); + + sbVmBlock_add_constant(&pb, &HVINT(5)); + sbVmBlock_add_constant(&pb, &HVINT(11)); + + sbVmProgram_add_block(&pm, &pb); + + sbVm_execute(&vm, &pm); + + printf("Stack result: "); + for (u8 *p = vm.stack; p < vm.sp; p++) { + printf("%02X ", *p); + } + printf("\n"); + + sbVmBlock_deinitialize(&pb); } diff --git a/src/mem/buffer.c b/src/mem/buffer.c index 61898cf..783d7b9 100644 --- a/src/mem/buffer.c +++ b/src/mem/buffer.c @@ -20,8 +20,7 @@ void *sbBuffer_expand(hBuffer buf, usize expand_size) { if (expand_size == 0) return NULL; if (buf->capacity == 0 || buf->data == NULL) { - fprintf(stderr, "cannot expand invalid buffer!\n"); - return NULL; + PANIC("cannot expand invalid buffer!"); } char *result; @@ -38,8 +37,7 @@ void *sbBuffer_expand(hBuffer buf, usize expand_size) { buf->capacity = new_capacity; buf->data = new_data; } else { - fprintf(stderr, "failed to expand buffer!"); - return NULL; + PANIC("failed to expand buffer!"); } } @@ -73,11 +71,13 @@ void sbBuffer_set_size(hBuffer buf, usize new_size) { } } -void sbBuffer_append(hBuffer buf, const void *data, usize data_length) { - if (data_length == 0) return; +void *sbBuffer_append(hBuffer buf, const void *data, usize data_length) { + if (data_length == 0) return NULL; char *put = sbBuffer_expand(buf, data_length); memcpy(put, data, data_length); + + return put; } void sbBuffer_reset(hBuffer buf) { diff --git a/src/mem/buffer.h b/src/mem/buffer.h index 2540a00..3f93812 100644 --- a/src/mem/buffer.h +++ b/src/mem/buffer.h @@ -23,7 +23,7 @@ void *sbBuffer_shrink(hBuffer buf, usize shrink_size); void sbBuffer_set_size(hBuffer buf, usize new_size); -void sbBuffer_append(hBuffer buf, const void *data, usize data_length); +void *sbBuffer_append(hBuffer buf, const void *data, usize data_length); void sbBuffer_reset(hBuffer buf); diff --git a/src/vm/block.c b/src/vm/block.c index e90c047..fe6757e 100644 --- a/src/vm/block.c +++ b/src/vm/block.c @@ -2,11 +2,6 @@ #define INITIAL_PROGRAM_BLOCK_SIZE 32 -void sbVmProgram_init(sbVmProgram *pm, usize initial_arena_size) { - *pm = (sbVmProgram) {0}; - sbArena_initialize(&pm->arena, initial_arena_size); -} - sbVmPartialBlock sbVmBlock_create(usize initial_bytecode_size, usize initial_constant_size) { sbVmPartialBlock pb = {0}; sbBuffer_initialize(&pb.bytecode, initial_bytecode_size); @@ -24,24 +19,43 @@ void sbVmBlock_deinitialize(sbVmPartialBlock *pb) { sbBuffer_deinitialize(&pb->constants); } -void sbVmProgram_initialize(sbVmProgram *pm) { - pm->block_count = 0; +void sbVmBlock_write_code(sbVmPartialBlock *pb, const u8 *data, usize length) { + sbBuffer_append(&pb->bytecode, data, length); +} + +void sbVmBlock_add_constant(sbVmPartialBlock *pb, hV *constant) { + sbV_retain(constant); + + sbBuffer_append(&pb->constants, constant, sizeof(hV)); +} + +void sbVmProgram_initialize(sbVmProgram *pm, usize initial_arena_size) { + *pm = (sbVmProgram) {0}; + sbArena_initialize(&pm->arena, initial_arena_size); pm->block_capacity = INITIAL_PROGRAM_BLOCK_SIZE; pm->blocks = malloc(pm->block_capacity * sizeof(sbVmBlock)); } void sbVmProgram_deinitialize(sbVmProgram *pm) { free(pm->blocks); + sbArena_deinitialize(&pm->arena); *pm = (sbVmProgram) {0}; } +/* finalize a partial-block and add it to the program. + * copies the data, so the same partial-block object can be reset + * and reused after calling this function. */ sbBlockId sbVmProgram_add_block(sbVmProgram *pm, sbVmPartialBlock *pb) { - const usize bytecode_length = pb->bytecode.size; - char *bytecode = sbArena_alloc(&pm->arena, bytecode_length); + usize bytecode_length = pb->bytecode.size; + usize constants_length = pb->constants.size; + while (bytecode_length % 8 != 0) bytecode_length ++; + + u8 *block_data = sbArena_alloc(&pm->arena, bytecode_length + constants_length); + + u8 *bytecode = &block_data[0]; memcpy(bytecode, pb->bytecode.data, bytecode_length); - const usize constants_length = pb->constants.size; - char *constants = sbArena_alloc(&pm->arena, constants_length); + u8 *constants = &block_data[bytecode_length]; memcpy(constants, pb->constants.data, constants_length); sbVmBlock bk = { diff --git a/src/vm/block.h b/src/vm/block.h index 3f3919b..6e9fb71 100644 --- a/src/vm/block.h +++ b/src/vm/block.h @@ -1,5 +1,12 @@ #include "common.h" +#define TEST_VM_BLK(bc, cn) ((sbVmBlock) { \ + .bytecode = bc, \ + .bytecode_length = sizeof(bc), \ + .constants = cn, \ + .constants_count = sizeof(cn)/sizeof(hV) \ + }) + /* dynamic sized block that we can more easily add * things to while compiling */ typedef struct sbVmPartialBlock { @@ -9,7 +16,7 @@ typedef struct sbVmPartialBlock { /* fixed size / frozen block of bytecode */ typedef struct sbVmBlock { - const char *bytecode; + const u8 *bytecode; usize bytecode_length; const hV *constants; usize constants_count; @@ -24,16 +31,21 @@ typedef struct sbVmProgram { typedef usize sbBlockId; -void sbVmProgram_init(sbVmProgram *pm, usize initial_arena_size); - sbVmPartialBlock sbVmBlock_create(usize initial_bytecode_size, usize initial_constant_size); void sbVmBlock_reset(sbVmPartialBlock *pb); void sbVmBlock_deinitialize(sbVmPartialBlock *pb); -void sbVmProgram_initialize(sbVmProgram *pm); +void sbVmBlock_write_code(sbVmPartialBlock *pb, const u8 *data, usize length); + +void sbVmBlock_add_constant(sbVmPartialBlock *pb, hV *constant); + +void sbVmProgram_initialize(sbVmProgram *pm, usize initial_arena_size); void sbVmProgram_deinitialize(sbVmProgram *pm); +/* finalize a partial-block and add it to the program. + * copies the data, so the same partial-block object can be reset + * and reused after calling this function. */ sbBlockId sbVmProgram_add_block(sbVmProgram *pm, sbVmPartialBlock *pb); diff --git a/src/vm/bytecode.h b/src/vm/bytecode.h index 5a206b1..6f3fe4f 100644 --- a/src/vm/bytecode.h +++ b/src/vm/bytecode.h @@ -5,26 +5,29 @@ typedef enum sbOpcode { BC_NOP = 0, - BC_LD_CONST, - BC_LD_IMM, - BC_LD_VAR, - BC_LD_CTX, - BC_LD_UPVAL, - BC_ST_VAR, - BC_ST_UPVAL, - BC_CALL, - BC_JMP, - BC_RET = 10, - BC_SEND, + BC_LD_IMM, /* push immediate value to stack */ + BC_LD_CONST, /* push constants[index] to stack */ + BC_LD_CTX, /* look up key in context object and push result */ + BC_LD_VAR, /* push value onto stack from variable */ + BC_LD_UPVAL, /* push value onto stack from closure */ + BC_ST_VAR, /* pop value from stack into variable */ + BC_ST_UPVAL, /* pop value from stack into closure */ + BC_POP, /* pop value from stack */ + BC_CALL, /* push return address and jump to new block */ + BC_JMP, /* local jump inside current block */ + BC_RET, /* return to calling block */ + BC_SEND, /* like call, but jump to object method (maybe this is the same as call?) */ BC_OP_ADD, BC_OP_SUB, BC_OP_MUL, - BC_OP_DIV, + BC_OP_DIV = 0x10, + BC_OP_FLDIV, BC_OP_NEG, BC_OP_MOD, BC_OP_POW, BC_OP_DEREF, - BC_LIST_NEW = 20, + BC_ALLOC_VARS, + BC_LIST_NEW, BC_HASH_NEW, BC_LIST_ADD, BC_HASH_ADD, diff --git a/src/vm/exec.c b/src/vm/exec.c index b39c709..f485622 100644 --- a/src/vm/exec.c +++ b/src/vm/exec.c @@ -1 +1,221 @@ #include "vm/exec.h" + +#include "data/integer.h" + +void call_block(hVm vm, usize block_id); +void execute_instruction(hVm vm); + +void sbVm_initialize(hVm vm, usize stacksize, usize rstacksize) { + *vm = (sbVm) {0}; + vm->stack = malloc(stacksize); + vm->stacksize = stacksize; + vm->rstack = malloc(rstacksize); + vm->rstacksize = rstacksize; + + vm->sp = vm->stack; + vm->fp = (sbVmStackFrame*)vm->rstack; + vm->rp = vm->rstack; +} + +void sbVm_deinitialize(hVm vm) { + free(vm->stack); + free(vm->rstack); + *vm = (sbVm) {0}; +} + +sbVmStatus sbVm_execute(hVm vm, sbVmProgram *pm) { + vm->program = pm; + vm->running = TRUE; + + /* Let's start at the very beginning. + * A very good place to start. */ + call_block(vm, 0); + + while (vm->running) { + execute_instruction(vm); + } + + return VM_STAT_SUCCESS; +} + +/* --- */ + +void call_block(hVm vm, usize block_id) { + sbVmBlock *blk = &vm->program->blocks[block_id]; + + sbVmStackFrame frame = { + .return_addr = vm->ip, + .last_fp = vm->fp, + .last_rp = vm->rp, + .block = blk, + }; + *(sbVmStackFrame*)vm->rp = frame; + vm->fp = (sbVmStackFrame*)vm->rp; + vm->rp += sizeof(sbVmStackFrame); + vm->ip = &blk->bytecode[0]; +} + +void return_from_block(hVm vm) { + sbVmStackFrame *frame = (sbVmStackFrame*)vm->fp; + + vm->fp = frame->last_fp; + vm->rp = frame->last_rp; + vm->ip = frame->return_addr; +} + +void push_stack(hVm vm, const hV *value) { + sbV_retain(value); + *(hV*)vm->sp = *value; + vm->sp += sizeof(hV); +} + +hV *pop_stack(hVm vm) { + vm->sp -= sizeof(hV); + sbV_release((hV*)vm->sp); + return (hV*)vm->sp; +} + +sbOpcode get_opcode(hVm vm) { + return *(vm->ip++); +} + +/* small numbers that are parameters to opcodes can + * just be encoded directly as 1 byte. numbers of 16-bit + * scale can be encoded as FE + byte + byte, numbers of + * 32 bit scale can be FF + byte + byte + byte + byte, + * in big-endian format */ +u32 get_param(hVm vm) { + u32 result = *((u8*)vm->ip++); + + if (result == BC_LONG_NUM) { + result = *(vm->ip++); + result <<= 8; + result |= *(vm->ip++); + } else if (result == BC_VLONG_NUM) { + result = *(vm->ip++); + result <<= 8; + result |= *(vm->ip++); + result <<= 8; + result |= *(vm->ip++); + result <<= 8; + result |= *(vm->ip++); + } + + return result; +} + +/* execute one instruction! wow! */ +void execute_instruction(hVm vm) { + sbOpcode op = get_opcode(vm); + u32 param; + hV *v, a, b, c; + + switch (op) { + case BC_NOP: + return; + case BC_HALT: + vm->running = FALSE; + return; + case BC_LD_IMM: + param = get_param(vm); + push_stack(vm, &HVINT(param)); + return; + case BC_LD_CONST: + param = get_param(vm); + push_stack(vm, &vm->fp->block->constants[param]); + return; + case BC_LD_CTX: + PANIC("todo"); + case BC_LD_VAR: + param = get_param(vm); + push_stack(vm, &vm->fp->locals[param]); + return; + case BC_LD_UPVAL: + /* Hey, was there upval in there? */ + PANIC("todo"); + case BC_ST_VAR: + param = get_param(vm); + vm->fp->locals[param] = *pop_stack(vm); + return; + case BC_ST_UPVAL: + PANIC("todo"); + case BC_POP: + v = pop_stack(vm); + sbV_release(v); + return; + case BC_CALL: + param = get_param(vm); + call_block(vm, param); + return; + case BC_JMP: + param = get_param(vm); + vm->ip = &vm->fp->block->bytecode[param]; + return; + case BC_RET: + return_from_block(vm); + return; + case BC_SEND: + PANIC("todo"); + case BC_OP_ADD: + b = *pop_stack(vm); + a = *pop_stack(vm); + if (a.type == IT_INTEGER && b.type == IT_INTEGER) { + c = sbV_int(sbInteger_sum(a.integer, b.integer)); + push_stack(vm, &c); + } else { + PANIC("todo"); + } + return; + case BC_OP_SUB: + b = *pop_stack(vm); + a = *pop_stack(vm); + if (a.type == IT_INTEGER && b.type == IT_INTEGER) { + c = sbV_int(sbInteger_diff(a.integer, b.integer)); + push_stack(vm, &c); + } else { + PANIC("todo"); + } + return; + case BC_OP_MUL: + b = *pop_stack(vm); + a = *pop_stack(vm); + if (a.type == IT_INTEGER && b.type == IT_INTEGER) { + c = sbV_int(sbInteger_mul(a.integer, b.integer)); + push_stack(vm, &c); + } else { + PANIC("todo"); + } + return; + case BC_OP_DIV: + PANIC("todo"); + case BC_OP_FLDIV: + b = *pop_stack(vm); + a = *pop_stack(vm); + if (a.type == IT_INTEGER && b.type == IT_INTEGER) { + c = sbV_int(sbInteger_floordiv(a.integer, b.integer)); + push_stack(vm, &c); + } else { + PANIC("todo"); + } + return; + case BC_OP_NEG: + case BC_OP_MOD: + case BC_OP_POW: + case BC_OP_DEREF: + PANIC("todo"); + case BC_ALLOC_VARS: + param = get_param(vm); + vm->rp += param * sizeof(hV); + return; + case BC_LIST_NEW: + case BC_HASH_NEW: + case BC_LIST_ADD: + case BC_HASH_ADD: + PANIC("todo"); + case BC_LONG_NUM: + case BC_VLONG_NUM: + PANIC("illegal opcode $%02X at position $%08zX\n", op, (usize)vm->ip); + default: + PANIC("unrecognized opcode $%02X at position $%08zX\n", op, (usize)vm->ip); + } +} diff --git a/src/vm/exec.h b/src/vm/exec.h index 67c02a2..c3341f7 100644 --- a/src/vm/exec.h +++ b/src/vm/exec.h @@ -1 +1,75 @@ #include "common.h" + +#include "vm/block.h" + +/* OK so, we have two stacks (because iirc, you kind of need two stacks + * to make a stack machine work.) It's a little bit like FORTH, in that + * we have one "normal" stack which is used by most instructions (we + * can push values onto the stack, branch based on these values, etc.) + * and then one extra stack which tracks the function call structure and + * can be manipulated using special instructions. */ + +/* We also have the "rstack". When we call a function, a stack frame is + * pushed onto the rstack, which saves the return address, the last + * value of fp and rp, and a pointer to the current code block (so we can + * find things like constants.) then, *above* this on the stack, we can + * use the space to store local variables, using instructions to move + * those slots to/from the main stack by index. when we return, we reset + * the fp and rp to point to the calling function's stack frame instead. */ + +/* (we need to track fp so we can remember where the return address is, + * and we need to track rp so we know where to put the *next* frame. + * this then lets us leave function arguments and function return values + * on the normal stack, without worrying about needing to shuffle + * things around.) */ + +/* I guess really the rstack is kind of like the "normal" C call stack, + * in that it's where we put "stack-allocated" local variables and save + * the stack frame, and the "normal" stack here does things that would + * normally be accomplished using registers in a non-stack-machine + * system... but, ah well. */ + +/* Calling convention for function arguments + return values is to put + * a number at the top of the stack representing the number of arguments + * or values returned, followed by the values in order from top to + * bottom. */ + +/* Also these stacks grow upwards in memory, from low to high addresses. */ + +typedef enum sbVmStatus { + VM_STAT_UNKNOWN, + VM_STAT_SUCCESS, + VM_STAT_FAILURE, +} sbVmStatus; + +typedef struct sbVmStackFrame { + const u8 *return_addr; + struct sbVmStackFrame *last_fp; + u8 *last_rp; + const sbVmBlock *block; + hV locals[]; +} sbVmStackFrame; + +typedef struct sbVm { + u8 *stack; /* for calculations */ + u8 *rstack; /* for locals and return addresses, like FORTH */ + + const u8 *ip; /* instruction pointer */ + sbVmStackFrame *fp; /* frame pointer */ + u8 *sp; /* stack pointer */ + u8 *rp; /* rstack pointer */ + + usize stacksize; /* to detect overflow, save these */ + usize rstacksize; /* ^^ */ + + sbVmProgram *program; + flag running; +} sbVm; + +typedef sbVm *hVm; + +void sbVm_initialize(hVm vm, usize stacksize, usize rstacksize); + +void sbVm_deinitialize(hVm vm); + +sbVmStatus sbVm_execute(hVm vm, sbVmProgram *pm); -- 1.8.3.1