1#include "vm.h"
2
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6
7void bytecode_init(Bytecode *bc) {
8 bc->words = NULL;
9 bc->count = 0;
10 bc->capacity = 0;
11}
12
13void bytecode_free(Bytecode *bc) {
14 free(bc->words);
15 bc->words = NULL;
16 bc->count = 0;
17 bc->capacity = 0;
18}
19
20VmError bytecode_emit(Bytecode *bc, int64_t word) {
21 if (bc->count == bc->capacity) {
22 size_t new_capacity = bc->capacity == 0 ? 64 : bc->capacity * 2;
23 int64_t *new_words = (int64_t *)realloc(bc->words, new_capacity * sizeof(*new_words));
24 if (!new_words) {
25 return VM_ERR_OUT_OF_MEMORY;
26 }
27 bc->words = new_words;
28 bc->capacity = new_capacity;
29 }
30 bc->words[bc->count++] = word;
31 return VM_OK;
32}
33
34static int default_output(int64_t value, void *userdata) {
35 (void)userdata;
36 return printf("%lld\n", (long long)value) < 0 ? -1 : 0;
37}
38
39void vm_init(VM *vm, const Bytecode *code) {
40 memset(vm, 0, sizeof(*vm));
41 vm->code = code;
42 vm->output = default_output;
43 vm->frame_count = 1;
44}
45
46void vm_set_output(VM *vm, VmOutputFn output, void *userdata) {
47 vm->output = output ? output : default_output;
48 vm->output_userdata = userdata;
49}
50
51static VmError push(VM *vm, int64_t value) {
52 if (vm->sp >= VM_STACK_MAX) {
53 return VM_ERR_STACK_OVERFLOW;
54 }
55 vm->stack[vm->sp++] = value;
56 return VM_OK;
57}
58
59static VmError pop(VM *vm, int64_t *out) {
60 if (vm->sp == 0) {
61 return VM_ERR_STACK_UNDERFLOW;
62 }
63 *out = vm->stack[--vm->sp];
64 return VM_OK;
65}
66
67static VmError read_operand(VM *vm, int64_t *out) {
68 if (vm->ip >= vm->code->count) {
69 return VM_ERR_TRUNCATED_INSTRUCTION;
70 }
71 *out = vm->code->words[vm->ip++];
72 return VM_OK;
73}
74
75static int is_valid_opcode(int64_t opcode) {
76 return opcode >= OP_PUSH && opcode <= OP_HALT;
77}
78
79static int opcode_operand_count(int64_t opcode, size_t *count) {
80 if (!is_valid_opcode(opcode)) {
81 return 0;
82 }
83 switch ((VmOpcode)opcode) {
84 case OP_PUSH:
85 case OP_JMP:
86 case OP_JZ:
87 case OP_JNZ:
88 case OP_CALL:
89 case OP_LOAD:
90 case OP_STORE:
91 *count = 1;
92 return 1;
93 case OP_POP:
94 case OP_DUP:
95 case OP_SWAP:
96 case OP_ADD:
97 case OP_SUB:
98 case OP_MUL:
99 case OP_DIV:
100 case OP_MOD:
101 case OP_NEG:
102 case OP_EQ:
103 case OP_LT:
104 case OP_GT:
105 case OP_RET:
106 case OP_PRINT:
107 case OP_HALT:
108 *count = 0;
109 return 1;
110 }
111 return 0;
112}
113
114static int is_instruction_boundary(const VM *vm, size_t target) {
115 size_t pos = 0;
116 while (pos < vm->code->count) {
117 if (pos == target) {
118 return 1;
119 }
120 size_t operands = 0;
121 if (!opcode_operand_count(vm->code->words[pos], &operands)) {
122 return 0;
123 }
124 if (pos + 1 + operands > vm->code->count) {
125 return 0;
126 }
127 pos += 1 + operands;
128 }
129 return 0;
130}
131
132static VmError validate_target(const VM *vm, int64_t target) {
133 if (target < 0 || (uint64_t)target >= vm->code->count) {
134 return VM_ERR_BAD_JUMP;
135 }
136 if (!is_instruction_boundary(vm, (size_t)target)) {
137 return VM_ERR_BAD_JUMP;
138 }
139 return VM_OK;
140}
141
142VmError vm_run(VM *vm) {
143 if (!vm->code) {
144 vm->last_error = VM_ERR_BAD_OPERAND;
145 return vm->last_error;
146 }
147
148 VmError err = VM_OK;
149 for (;;) {
150 err = VM_OK;
151 if (vm->ip >= vm->code->count) {
152 vm->last_error = VM_ERR_NO_HALT;
153 return vm->last_error;
154 }
155
156 int64_t raw_opcode = vm->code->words[vm->ip++];
157 if (!is_valid_opcode(raw_opcode)) {
158 vm->last_error = VM_ERR_BAD_OPCODE;
159 return vm->last_error;
160 }
161
162 VmOpcode opcode = (VmOpcode)raw_opcode;
163 int64_t a = 0;
164 int64_t b = 0;
165 int64_t operand = 0;
166
167 switch (opcode) {
168 case OP_PUSH:
169 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
170 if ((err = push(vm, operand)) != VM_OK) goto fail;
171 break;
172
173 case OP_POP:
174 if ((err = pop(vm, &a)) != VM_OK) goto fail;
175 break;
176
177 case OP_DUP:
178 if (vm->sp == 0) {
179 err = VM_ERR_STACK_UNDERFLOW;
180 goto fail;
181 }
182 if ((err = push(vm, vm->stack[vm->sp - 1])) != VM_OK) goto fail;
183 break;
184
185 case OP_SWAP:
186 if (vm->sp < 2) {
187 err = VM_ERR_STACK_UNDERFLOW;
188 goto fail;
189 }
190 a = vm->stack[vm->sp - 1];
191 vm->stack[vm->sp - 1] = vm->stack[vm->sp - 2];
192 vm->stack[vm->sp - 2] = a;
193 break;
194
195 case OP_ADD:
196 if ((err = pop(vm, &b)) != VM_OK) goto fail;
197 if ((err = pop(vm, &a)) != VM_OK) goto fail;
198 if ((err = push(vm, a + b)) != VM_OK) goto fail;
199 break;
200
201 case OP_SUB:
202 if ((err = pop(vm, &b)) != VM_OK) goto fail;
203 if ((err = pop(vm, &a)) != VM_OK) goto fail;
204 if ((err = push(vm, a - b)) != VM_OK) goto fail;
205 break;
206
207 case OP_MUL:
208 if ((err = pop(vm, &b)) != VM_OK) goto fail;
209 if ((err = pop(vm, &a)) != VM_OK) goto fail;
210 if ((err = push(vm, a * b)) != VM_OK) goto fail;
211 break;
212
213 case OP_DIV:
214 if ((err = pop(vm, &b)) != VM_OK) goto fail;
215 if ((err = pop(vm, &a)) != VM_OK) goto fail;
216 if (b == 0) {
217 err = VM_ERR_DIVISION_BY_ZERO;
218 goto fail;
219 }
220 if ((err = push(vm, a / b)) != VM_OK) goto fail;
221 break;
222
223 case OP_MOD:
224 if ((err = pop(vm, &b)) != VM_OK) goto fail;
225 if ((err = pop(vm, &a)) != VM_OK) goto fail;
226 if (b == 0) {
227 err = VM_ERR_DIVISION_BY_ZERO;
228 goto fail;
229 }
230 if ((err = push(vm, a % b)) != VM_OK) goto fail;
231 break;
232
233 case OP_NEG:
234 if ((err = pop(vm, &a)) != VM_OK) goto fail;
235 if ((err = push(vm, -a)) != VM_OK) goto fail;
236 break;
237
238 case OP_EQ:
239 if ((err = pop(vm, &b)) != VM_OK) goto fail;
240 if ((err = pop(vm, &a)) != VM_OK) goto fail;
241 if ((err = push(vm, a == b ? 1 : 0)) != VM_OK) goto fail;
242 break;
243
244 case OP_LT:
245 if ((err = pop(vm, &b)) != VM_OK) goto fail;
246 if ((err = pop(vm, &a)) != VM_OK) goto fail;
247 if ((err = push(vm, a < b ? 1 : 0)) != VM_OK) goto fail;
248 break;
249
250 case OP_GT:
251 if ((err = pop(vm, &b)) != VM_OK) goto fail;
252 if ((err = pop(vm, &a)) != VM_OK) goto fail;
253 if ((err = push(vm, a > b ? 1 : 0)) != VM_OK) goto fail;
254 break;
255
256 case OP_JMP:
257 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
258 if ((err = validate_target(vm, operand)) != VM_OK) goto fail;
259 vm->ip = (size_t)operand;
260 break;
261
262 case OP_JZ:
263 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
264 if ((err = pop(vm, &a)) != VM_OK) goto fail;
265 if (a == 0) {
266 if ((err = validate_target(vm, operand)) != VM_OK) goto fail;
267 vm->ip = (size_t)operand;
268 }
269 break;
270
271 case OP_JNZ:
272 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
273 if ((err = pop(vm, &a)) != VM_OK) goto fail;
274 if (a != 0) {
275 if ((err = validate_target(vm, operand)) != VM_OK) goto fail;
276 vm->ip = (size_t)operand;
277 }
278 break;
279
280 case OP_CALL:
281 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
282 if ((err = validate_target(vm, operand)) != VM_OK) goto fail;
283 if (vm->frame_count >= VM_CALL_STACK_MAX) {
284 err = VM_ERR_CALL_OVERFLOW;
285 goto fail;
286 }
287 vm->frames[vm->frame_count].return_ip = vm->ip;
288 memset(vm->frames[vm->frame_count].locals, 0, sizeof(vm->frames[vm->frame_count].locals));
289 vm->frame_count++;
290 vm->ip = (size_t)operand;
291 break;
292
293 case OP_RET:
294 if (vm->frame_count <= 1) {
295 err = VM_ERR_CALL_UNDERFLOW;
296 goto fail;
297 }
298 vm->frame_count--;
299 vm->ip = vm->frames[vm->frame_count].return_ip;
300 break;
301
302 case OP_LOAD:
303 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
304 if (operand < 0 || operand >= VM_LOCALS_PER_FRAME) {
305 err = VM_ERR_BAD_LOCAL;
306 goto fail;
307 }
308 if ((err = push(vm, vm->frames[vm->frame_count - 1].locals[operand])) != VM_OK) goto fail;
309 break;
310
311 case OP_STORE:
312 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
313 if (operand < 0 || operand >= VM_LOCALS_PER_FRAME) {
314 err = VM_ERR_BAD_LOCAL;
315 goto fail;
316 }
317 if ((err = pop(vm, &a)) != VM_OK) goto fail;
318 vm->frames[vm->frame_count - 1].locals[operand] = a;
319 break;
320
321 case OP_PRINT:
322 if ((err = pop(vm, &a)) != VM_OK) goto fail;
323 if (vm->output(a, vm->output_userdata) != 0) {
324 err = VM_ERR_OUTPUT;
325 goto fail;
326 }
327 break;
328
329 case OP_HALT:
330 vm->last_error = VM_OK;
331 return VM_OK;
332 }
333 }
334
335fail:
336 vm->last_error = err;
337 return err;
338}
339
340const char *vm_error_string(VmError error) {
341 switch (error) {
342 case VM_OK: return "ok";
343 case VM_ERR_STACK_UNDERFLOW: return "stack underflow";
344 case VM_ERR_STACK_OVERFLOW: return "stack overflow";
345 case VM_ERR_CALL_UNDERFLOW: return "call stack underflow";
346 case VM_ERR_CALL_OVERFLOW: return "call stack overflow";
347 case VM_ERR_DIVISION_BY_ZERO: return "division by zero";
348 case VM_ERR_BAD_OPCODE: return "bad opcode";
349 case VM_ERR_BAD_OPERAND: return "bad operand";
350 case VM_ERR_BAD_LOCAL: return "bad local";
351 case VM_ERR_BAD_JUMP: return "out-of-range jump";
352 case VM_ERR_TRUNCATED_INSTRUCTION: return "truncated instruction";
353 case VM_ERR_NO_HALT: return "program ended without halt";
354 case VM_ERR_OUT_OF_MEMORY: return "out of memory";
355 case VM_ERR_OUTPUT: return "output error";
356 default: return "unknown error";
357 }
358}
359
Discussion
No comments yet. Start the discussion. Recorded by @patrick-toulme.