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 VmError validate_target(const VM *vm, int64_t target) {
80 if (target < 0 || (uint64_t)target >= vm->code->count) {
81 return VM_ERR_BAD_JUMP;
82 }
83 if (!is_valid_opcode(vm->code->words[target])) {
84 return VM_ERR_BAD_JUMP;
85 }
86 return VM_OK;
87}
88
89VmError vm_run(VM *vm) {
90 if (!vm->code) {
91 vm->last_error = VM_ERR_BAD_OPERAND;
92 return vm->last_error;
93 }
94
95 for (;;) {
96 if (vm->ip >= vm->code->count) {
97 vm->last_error = VM_ERR_NO_HALT;
98 return vm->last_error;
99 }
100
101 int64_t raw_opcode = vm->code->words[vm->ip++];
102 if (!is_valid_opcode(raw_opcode)) {
103 vm->last_error = VM_ERR_BAD_OPCODE;
104 return vm->last_error;
105 }
106
107 VmOpcode opcode = (VmOpcode)raw_opcode;
108 int64_t a = 0;
109 int64_t b = 0;
110 int64_t operand = 0;
111 VmError err = VM_OK;
112
113 switch (opcode) {
114 case OP_PUSH:
115 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
116 if ((err = push(vm, operand)) != VM_OK) goto fail;
117 break;
118
119 case OP_POP:
120 if ((err = pop(vm, &a)) != VM_OK) goto fail;
121 break;
122
123 case OP_DUP:
124 if (vm->sp == 0) {
125 err = VM_ERR_STACK_UNDERFLOW;
126 goto fail;
127 }
128 if ((err = push(vm, vm->stack[vm->sp - 1])) != VM_OK) goto fail;
129 break;
130
131 case OP_SWAP:
132 if (vm->sp < 2) {
133 err = VM_ERR_STACK_UNDERFLOW;
134 goto fail;
135 }
136 a = vm->stack[vm->sp - 1];
137 vm->stack[vm->sp - 1] = vm->stack[vm->sp - 2];
138 vm->stack[vm->sp - 2] = a;
139 break;
140
141 case OP_ADD:
142 if ((err = pop(vm, &b)) != VM_OK) goto fail;
143 if ((err = pop(vm, &a)) != VM_OK) goto fail;
144 if ((err = push(vm, a + b)) != VM_OK) goto fail;
145 break;
146
147 case OP_SUB:
148 if ((err = pop(vm, &b)) != VM_OK) goto fail;
149 if ((err = pop(vm, &a)) != VM_OK) goto fail;
150 if ((err = push(vm, a - b)) != VM_OK) goto fail;
151 break;
152
153 case OP_MUL:
154 if ((err = pop(vm, &b)) != VM_OK) goto fail;
155 if ((err = pop(vm, &a)) != VM_OK) goto fail;
156 if ((err = push(vm, a * b)) != VM_OK) goto fail;
157 break;
158
159 case OP_DIV:
160 if ((err = pop(vm, &b)) != VM_OK) goto fail;
161 if ((err = pop(vm, &a)) != VM_OK) goto fail;
162 if (b == 0) {
163 err = VM_ERR_DIVISION_BY_ZERO;
164 goto fail;
165 }
166 if ((err = push(vm, a / b)) != VM_OK) goto fail;
167 break;
168
169 case OP_MOD:
170 if ((err = pop(vm, &b)) != VM_OK) goto fail;
171 if ((err = pop(vm, &a)) != VM_OK) goto fail;
172 if (b == 0) {
173 err = VM_ERR_DIVISION_BY_ZERO;
174 goto fail;
175 }
176 if ((err = push(vm, a % b)) != VM_OK) goto fail;
177 break;
178
179 case OP_NEG:
180 if ((err = pop(vm, &a)) != VM_OK) goto fail;
181 if ((err = push(vm, -a)) != VM_OK) goto fail;
182 break;
183
184 case OP_EQ:
185 if ((err = pop(vm, &b)) != VM_OK) goto fail;
186 if ((err = pop(vm, &a)) != VM_OK) goto fail;
187 if ((err = push(vm, a == b ? 1 : 0)) != VM_OK) goto fail;
188 break;
189
190 case OP_LT:
191 if ((err = pop(vm, &b)) != VM_OK) goto fail;
192 if ((err = pop(vm, &a)) != VM_OK) goto fail;
193 if ((err = push(vm, a < b ? 1 : 0)) != VM_OK) goto fail;
194 break;
195
196 case OP_GT:
197 if ((err = pop(vm, &b)) != VM_OK) goto fail;
198 if ((err = pop(vm, &a)) != VM_OK) goto fail;
199 if ((err = push(vm, a > b ? 1 : 0)) != VM_OK) goto fail;
200 break;
201
202 case OP_JMP:
203 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
204 if ((err = validate_target(vm, operand)) != VM_OK) goto fail;
205 vm->ip = (size_t)operand;
206 break;
207
208 case OP_JZ:
209 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
210 if ((err = pop(vm, &a)) != VM_OK) goto fail;
211 if (a == 0) {
212 if ((err = validate_target(vm, operand)) != VM_OK) goto fail;
213 vm->ip = (size_t)operand;
214 }
215 break;
216
217 case OP_JNZ:
218 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
219 if ((err = pop(vm, &a)) != VM_OK) goto fail;
220 if (a != 0) {
221 if ((err = validate_target(vm, operand)) != VM_OK) goto fail;
222 vm->ip = (size_t)operand;
223 }
224 break;
225
226 case OP_CALL:
227 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
228 if ((err = validate_target(vm, operand)) != VM_OK) goto fail;
229 if (vm->frame_count >= VM_CALL_STACK_MAX) {
230 err = VM_ERR_CALL_OVERFLOW;
231 goto fail;
232 }
233 vm->frames[vm->frame_count].return_ip = vm->ip;
234 memset(vm->frames[vm->frame_count].locals, 0, sizeof(vm->frames[vm->frame_count].locals));
235 vm->frame_count++;
236 vm->ip = (size_t)operand;
237 break;
238
239 case OP_RET:
240 if (vm->frame_count <= 1) {
241 err = VM_ERR_CALL_UNDERFLOW;
242 goto fail;
243 }
244 vm->frame_count--;
245 vm->ip = vm->frames[vm->frame_count].return_ip;
246 break;
247
248 case OP_LOAD:
249 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
250 if (operand < 0 || operand >= VM_LOCALS_PER_FRAME) {
251 err = VM_ERR_BAD_LOCAL;
252 goto fail;
253 }
254 if ((err = push(vm, vm->frames[vm->frame_count - 1].locals[operand])) != VM_OK) goto fail;
255 break;
256
257 case OP_STORE:
258 if ((err = read_operand(vm, &operand)) != VM_OK) goto fail;
259 if (operand < 0 || operand >= VM_LOCALS_PER_FRAME) {
260 err = VM_ERR_BAD_LOCAL;
261 goto fail;
262 }
263 if ((err = pop(vm, &a)) != VM_OK) goto fail;
264 vm->frames[vm->frame_count - 1].locals[operand] = a;
265 break;
266
267 case OP_PRINT:
268 if ((err = pop(vm, &a)) != VM_OK) goto fail;
269 if (vm->output(a, vm->output_userdata) != 0) {
270 err = VM_ERR_OUTPUT;
271 goto fail;
272 }
273 break;
274
275 case OP_HALT:
276 vm->last_error = VM_OK;
277 return VM_OK;
278 }
279 }
280
281fail:
282 vm->last_error = err;
283 return err;
284}
285
286const char *vm_error_string(VmError error) {
287 switch (error) {
288 case VM_OK: return "ok";
289 case VM_ERR_STACK_UNDERFLOW: return "stack underflow";
290 case VM_ERR_STACK_OVERFLOW: return "stack overflow";
291 case VM_ERR_CALL_UNDERFLOW: return "call stack underflow";
292 case VM_ERR_CALL_OVERFLOW: return "call stack overflow";
293 case VM_ERR_DIVISION_BY_ZERO: return "division by zero";
294 case VM_ERR_BAD_OPCODE: return "bad opcode";
295 case VM_ERR_BAD_OPERAND: return "bad operand";
296 case VM_ERR_BAD_LOCAL: return "bad local";
297 case VM_ERR_BAD_JUMP: return "out-of-range jump";
298 case VM_ERR_TRUNCATED_INSTRUCTION: return "truncated instruction";
299 case VM_ERR_NO_HALT: return "program ended without halt";
300 case VM_ERR_OUT_OF_MEMORY: return "out of memory";
301 case VM_ERR_OUTPUT: return "output error";
302 default: return "unknown error";
303 }
304}
305
Discussion
No comments yet. Start the discussion. Recorded by @patrick-toulme.