diff options
author | Jack Sangdahl <[email protected]> | 2024-04-01 14:00:27 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-04-01 14:00:27 -0600 |
commit | 6fb34179efc44a8d3d39cfa7a514ecaaed83e9f8 (patch) | |
tree | f4712db984d79223630c4d9bd15a2a29a4d4ea38 | |
download | synacor_challenge-6fb34179efc44a8d3d39cfa7a514ecaaed83e9f8.tar.gz synacor_challenge-6fb34179efc44a8d3d39cfa7a514ecaaed83e9f8.zip |
initial
-rw-r--r-- | .gitignore | 3 | ||||
-rw-r--r-- | Makefile | 16 | ||||
-rw-r--r-- | arch-spec | 79 | ||||
-rw-r--r-- | challenge.bin | bin | 0 -> 59914 bytes | |||
-rw-r--r-- | codes.txt | 8 | ||||
-rw-r--r-- | input.txt | 77 | ||||
-rw-r--r-- | main.c | 18 | ||||
-rw-r--r-- | memory.c | 31 | ||||
-rw-r--r-- | memory.h | 13 | ||||
-rw-r--r-- | readme.md | 1 | ||||
-rw-r--r-- | stack.c | 20 | ||||
-rw-r--r-- | stack.h | 12 | ||||
-rw-r--r-- | util.c | 37 | ||||
-rw-r--r-- | util.h | 19 | ||||
-rwxr-xr-x | validate.sh | 26 | ||||
-rw-r--r-- | vm.c | 412 | ||||
-rw-r--r-- | vm.h | 39 |
17 files changed, 811 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..f0e03e5 --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +vm +*.o +.gdb* diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..896bfd4 --- /dev/null +++ b/Makefile @@ -0,0 +1,16 @@ +OBJS = main.o util.o vm.o memory.o stack.o +CFLAGS = -Wall -DNDEBUG + +all: $(OBJS) + cc $(CFLAGS) -o vm $(OBJS) + +test: + ./validate.sh codes.txt + +clean: + rm *.o vm + +util.o: util.h +vm.o: vm.h +memory.o: memory.h +stack.o: stack.h diff --git a/arch-spec b/arch-spec new file mode 100644 index 0000000..a2a1902 --- /dev/null +++ b/arch-spec @@ -0,0 +1,79 @@ +== Synacor OSCON 2012 Challenge == +In this challenge, your job is to use this architecture spec to create a +virtual machine capable of running the included binary. Along the way, +you will find codes; submit these to the challenge website to track +your progress. Good luck! + + +== architecture == +- three storage regions + - memory with 15-bit address space storing 16-bit values + - eight registers + - an unbounded stack which holds individual 16-bit values +- all numbers are unsigned integers 0..32767 (15-bit) +- all math is modulo 32768; 32758 + 15 => 5 + +== binary format == +- each number is stored as a 16-bit little-endian pair (low byte, high byte) +- numbers 0..32767 mean a literal value +- numbers 32768..32775 instead mean registers 0..7 +- numbers 32776..65535 are invalid +- programs are loaded into memory starting at address 0 +- address 0 is the first 16-bit value, address 1 is the second 16-bit value, etc + +== execution == +- After an operation is executed, the next instruction to read is immediately after the last argument of the current operation. If a jump was performed, the next operation is instead the exact destination of the jump. +- Encountering a register as an operation argument should be taken as reading from the register or setting into the register as appropriate. + +== hints == +- Start with operations 0, 19, and 21. +- Here's a code for the challenge website: LDOb7UGhTi +- The program "9,32768,32769,4,19,32768" occupies six memory addresses and should: + - Store into register 0 the sum of 4 and the value contained in register 1. + - Output to the terminal the character with the ascii code contained in register 0. + +== opcode listing == +halt: 0 + stop execution and terminate the program +set: 1 a b + set register <a> to the value of <b> +push: 2 a + push <a> onto the stack +pop: 3 a + remove the top element from the stack and write it into <a>; empty stack = error +eq: 4 a b c + set <a> to 1 if <b> is equal to <c>; set it to 0 otherwise +gt: 5 a b c + set <a> to 1 if <b> is greater than <c>; set it to 0 otherwise +jmp: 6 a + jump to <a> +jt: 7 a b + if <a> is nonzero, jump to <b> +jf: 8 a b + if <a> is zero, jump to <b> +add: 9 a b c + assign into <a> the sum of <b> and <c> (modulo 32768) +mult: 10 a b c + store into <a> the product of <b> and <c> (modulo 32768) +mod: 11 a b c + store into <a> the remainder of <b> divided by <c> +and: 12 a b c + stores into <a> the bitwise and of <b> and <c> +or: 13 a b c + stores into <a> the bitwise or of <b> and <c> +not: 14 a b + stores 15-bit bitwise inverse of <b> in <a> +rmem: 15 a b + read memory at address <b> and write it to <a> +wmem: 16 a b + write the value from <b> into memory at address <a> +call: 17 a + write the address of the next instruction to the stack and jump to <a> +ret: 18 + remove the top element from the stack and jump to it; empty stack = halt +out: 19 a + write the character represented by ascii code <a> to the terminal +in: 20 a + read a character from the terminal and write its ascii code to <a>; it can be assumed that once input starts, it will continue until a newline is encountered; this means that you can safely read whole lines from the keyboard instead of having to figure out how to read individual characters +noop: 21 + no operation diff --git a/challenge.bin b/challenge.bin Binary files differnew file mode 100644 index 0000000..6e653f9 --- /dev/null +++ b/challenge.bin diff --git a/codes.txt b/codes.txt new file mode 100644 index 0000000..ce821ec --- /dev/null +++ b/codes.txt @@ -0,0 +1,8 @@ +LDOb7UGhTi +ImoFztWQCvxj +BNCyODLfQkIl +pWDWTEfURAdS +rdMkyZhveeIv +JyDQhSbkpyns +NBlOWKLbTMgY +qo8HqHOwU8Wi diff --git a/input.txt b/input.txt new file mode 100644 index 0000000..a301f61 --- /dev/null +++ b/input.txt @@ -0,0 +1,77 @@ +take tablet +look tablet +use tablet +doorway +north +north +bridge +continue +down +east +take empty lantern +west +west +passage +ladder +west +south +north +take can +use can +use lantern +west +ladder +darkness +continue +west +west +west +west +north +take red coin +north +west +take blue coin +up +take shiny coin +down +east +east +take concave coin +down +take corroded coin +up +west +use blue coin +use red coin +use shiny coin +use concave coin +use corroded coin +north +take teleporter +use teleporter +north +north +north +north +north +north +north +north +north +take orb +north +east +east +north +west +south +east +east +west +north +north +east +vault +take mirror +use mirror @@ -0,0 +1,18 @@ +// synacor challenge (@waffle87) +#include "vm.h" + +Stack s; +Memory m; + +int main(int argc, char **argv) { + if (argc < 2) { + fprintf(stderr, "usage: %s <challenge.bin>\n", argv[0]); + return EXIT_FAILURE; + } + stack_init(&s); + mem_init(&m); + int res = parse(argv[1]); + mem_free(&m); + stack_free(&s); + return res; +} diff --git a/memory.c b/memory.c new file mode 100644 index 0000000..60bcafb --- /dev/null +++ b/memory.c @@ -0,0 +1,31 @@ +// synacor challenge (@waffle87) +#include "memory.h" + +void mem_init(Memory *m) { + m->size = INT16_MAX; + m->mem = malloc(sizeof(u16) * m->size); + memset(m->mem, 0, sizeof(u16) * m->size); +} + +void mem_free(Memory *m) { + free(m->mem); + m->size = 0; +} + +void mem_set(Memory *m, u16 addr, u16 value) { + addr = addr * 2; + m->mem[addr] = value; + m->mem[addr + 1] = value >> 8; +} + +u16 mem_get(Memory *m, u16 addr) { + u16 pair; + addr = addr * 2; + get_next_pair(m->mem + addr, &pair); + return pair; +} + +u8 *get_next_pair(u8 *buffer, u16 *pair) { + *pair = (*(buffer + 1) << 8) + *buffer; + return buffer + 2; +} diff --git a/memory.h b/memory.h new file mode 100644 index 0000000..57f74be --- /dev/null +++ b/memory.h @@ -0,0 +1,13 @@ +// synacor challenge (@waffle87) +#include "util.h" + +typedef struct { + u8 *mem; + u16 size; +} Memory; + +void mem_init(Memory *m); +void mem_free(Memory *m); +void mem_set(Memory *m, u16 addr, u16 value); +u16 mem_get(Memory *m, u16 addr); +u8 *get_next_pair(u8 *buffer, u16 *pair); diff --git a/readme.md b/readme.md new file mode 100644 index 0000000..8e11e12 --- /dev/null +++ b/readme.md @@ -0,0 +1 @@ +see [here](https://lzycat.xyz/synacor) for more information @@ -0,0 +1,20 @@ +// synacor challenge (@waffle87) +#include "stack.h" + +void stack_init(Stack *s) { + s->data = malloc(UINT16_MAX); + s->pointer = 0; +} + +void stack_free(Stack *s) { free(s->data); } + +void stack_push(Stack *s, u16 value) { + s->data[s->pointer] = value; + s->pointer = s->pointer + 1; +} + +u16 stack_pop(Stack *s) { + u16 value = s->data[s->pointer - 1]; + s->pointer = s->pointer - 1; + return value; +} @@ -0,0 +1,12 @@ +// synacor challenge (@waffle87) +#include "util.h" + +typedef struct { + u16 *data; + u16 pointer; +} Stack; + +void stack_init(Stack *s); +void stack_free(Stack *s); +void stack_push(Stack *s, u16 value); +u16 stack_pop(Stack *s); @@ -0,0 +1,37 @@ +// synacor challenge (@waffle87) +#include "util.h" + +#ifndef NDEBUG +char *reg_string(unsigned short r) { + static char str[6]; + switch (r) { + case 32768: + sprintf(str, "r0"); + break; + case 32769: + sprintf(str, "r1"); + break; + case 32770: + sprintf(str, "r2"); + break; + case 32771: + sprintf(str, "r3"); + break; + case 32772: + sprintf(str, "r4"); + break; + case 32773: + sprintf(str, "r5"); + break; + case 32774: + sprintf(str, "r6"); + break; + case 32775: + sprintf(str, "r7"); + break; + default: + sprintf(str, "null"); + } + return str; +} +#endif // NDEBUG @@ -0,0 +1,19 @@ +// synacor challenge (@waffle87) +#include <assert.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +typedef unsigned char u8; +typedef unsigned short u16; +typedef int (*instruction_ptr)(u8 *buffer); + +#ifdef NDEBUG +#define LOG(fmt, ...) ((void)0) +#define REG(x) ((void)0) +#else +#define LOG(...) fprintf(stdout, __VA_ARGS__) +#define REG(x) reg_string(x) +char *reg_string(unsigned short r); +#endif diff --git a/validate.sh b/validate.sh new file mode 100755 index 0000000..b1247ea --- /dev/null +++ b/validate.sh @@ -0,0 +1,26 @@ +#!/bin/sh + +if [ "$#" -eq 0 ]; then + printf "usage: %s <codes.txt>\n" $0 + exit 1 +fi + +n=0 +master="6fcd818224b42f563e10b91b4f2a5ae8" +sums=( + "76ec2408e8fe3f1753c25db51efd8eb3" + "0e6aa7be1f68d930926d72b3741a145c" + "7997a3b2941eab92c1c0345d5747b420" + "186f842951c0dcfe8838af1e7222b7d4" + "2bf84e54b95ce97aefd9fc920451fc45" + "e09640936b3ef532b7b8e83ce8f125f4" + "4873cf6b76f62ac7d5a53605b2535a0c" + "d0c54d4ed7f943280ce3e19532dbb1a6" +) + +while read i; do + curr=$(echo -n "$i" | md5sum $master - 2>/dev/null) + curr="${curr%?}" + printf "code %s:\nproduce:\t%s\nexpect:\t\t%s\n" $i $curr ${sums[$n]} + ((n++)) +done < "$1" @@ -0,0 +1,412 @@ +// synacor challenge (@waffle87) +#include "vm.h" + +u16 rPC = 0; +u16 r0 = 0; +u16 r1 = 0; +u16 r2 = 0; +u16 r3 = 0; +u16 r4 = 0; +u16 r5 = 0; +u16 r6 = 0; +u16 r7 = 0; + +int parse(char const *filename) { + FILE *fptr = fopen(filename, "rb"); + if (!fptr) { + fprintf(stderr, "error: opening file: %s\n", filename); + return EXIT_FAILURE; + } + if (fseek(fptr, 0, SEEK_END)) { + fprintf(stderr, "error: opening file: %s\n", filename); + fclose(fptr); + return EXIT_FAILURE; + } + long file_size = ftell(fptr); + if (file_size == EOF) { + fprintf(stderr, "error: opening file: %s\n", filename); + fclose(fptr); + return EXIT_FAILURE; + } + if (fseek(fptr, 0, SEEK_SET)) { + fprintf(stderr, "error: opening file: %s\n", filename); + fclose(fptr); + return EXIT_FAILURE; + } + size_t size_read = fread(m.mem, 1, file_size, fptr); + if (size_read != file_size) { + fprintf(stderr, "error: reading file: %s\n", filename); + fclose(fptr); + return EXIT_FAILURE; + } + int res; + u16 opcode; + u8 *buffer = m.mem; + rPC = 0; + while (1) { + get_next_pair(buffer + rPC, &opcode); + res = operate(opcode, buffer + rPC + 2); + if (res == -1) + break; + rPC = res; + } + fclose(fptr); + return EXIT_SUCCESS; +} + +int operate(u16 opcode, unsigned char *buffer) { + instruction_ptr instr; + int next; + instr = get_instruction(opcode); + if (!instr) + LOG("opcode: %d\n", opcode); + assert(instr); + next = instr(buffer); + if (next == -1) + return EXIT_FAILURE; + return next; +} + +int is_valid(u16 opcode) { return opcode < 32776; } + +int is_literal(u16 opcode) { return opcode < 32768; } + +int is_register(u16 opcode) { return opcode >= 32768 && opcode <= 32775; } + +u16 *get_register(u16 opcode) { + switch (opcode) { + case 32768: + return &r0; + case 32769: + return &r1; + case 32770: + return &r2; + case 32771: + return &r3; + case 32772: + return &r4; + case 32773: + return &r5; + case 32774: + return &r6; + case 32775: + return &r7; + default: + return NULL; + } +} + +instruction_ptr get_instruction(u16 opcode) { + switch (opcode) { + case 0: + return &instruction_halt; + case 1: + return &instruction_set; + case 2: + return &instruction_push; + case 3: + return &instruction_pop; + case 4: + return &instruction_eq; + case 5: + return &instruction_gt; + case 6: + return &instruction_jmp; + case 7: + return &instruction_jt; + case 8: + return &instruction_jf; + case 9: + return &instruction_add; + case 10: + return &instruction_mult; + case 11: + return &instruction_mod; + case 12: + return &instruction_and; + case 13: + return &instruction_or; + case 14: + return &instruction_not; + case 15: + return &instruction_rmem; + case 16: + return &instruction_wmem; + case 17: + return &instruction_call; + case 18: + return &instruction_ret; + case 19: + return &instruction_out; + case 20: + return &instruction_in; + case 21: + return &instruction_noop; + default: + return NULL; + } +} + +int instruction_halt(u8 *buffer) { return -1; } + +int instruction_set(u8 *buffer) { + u16 next, *a; + buffer = get_next_pair(buffer, &next); + LOG("set: %d", next); + a = get_register(next); + buffer = get_next_pair(buffer, &next); + if (is_register(next)) + next = *get_register(next); + LOG(" %d\n", next); + *a = next; + return rPC + 6; +} + +int instruction_push(u8 *buffer) { + u16 next; + buffer = get_next_pair(buffer, &next); + if (is_register(next)) + next = *get_register(next); + stack_push(&s, next); + LOG("push: %d\n", next); + return rPC + 4; +} + +int instruction_pop(u8 *buffer) { + u16 next, *a; + buffer = get_next_pair(buffer, &next); + a = get_register(next); + *a = stack_pop(&s); + LOG("pop: %d\n", *a); + return rPC + 4; +} + +int instruction_eq(u8 *buffer) { + u16 next, *a, b, c; + buffer = get_next_pair(buffer, &next); + LOG("%d: eq: %s", rPC, REG(next)); + a = get_register(next); + buffer = get_next_pair(buffer, &b); + LOG(" %s", REG(b)); + if (is_register(b)) + b = *get_register(b); + LOG("(%d)", b); + buffer = get_next_pair(buffer, &c); + LOG(" %s", REG(c)); + if (is_register(c)) + c = *get_register(c); + LOG("(%d)\n", c); + *a = b == c ? 1 : 0; + return rPC + 8; +} + +int instruction_gt(u8 *buffer) { + u16 next, *a, b, c; + buffer = get_next_pair(buffer, &next); + LOG("gt: %d", next); + a = get_register(next); + buffer = get_next_pair(buffer, &b); + if (is_register(b)) + b = *get_register(b); + buffer = get_next_pair(buffer, &c); + if (is_register(c)) + c = *get_register(c); + *a = b > c ? 1 : 0; + LOG(" %d %d\n", b, c); + return rPC + 2 + 6; +} + +int instruction_jmp(u8 *buffer) { + u16 next; + buffer = get_next_pair(buffer, &next); + if (is_register(next)) + next = *get_register(next); + LOG("jmp: %d\n", next); + return next * 2; +} + +int instruction_jt(u8 *buffer) { + u16 a, b; + buffer = get_next_pair(buffer, &a); + LOG("jt: %d", a); + if (is_register(a)) + a = *get_register(a); + buffer = get_next_pair(buffer, &b); + if (is_register(b)) + b = *get_register(b); + LOG(" %d\n", b); + return a ? b * 2 : rPC + 6; +} + +int instruction_jf(u8 *buffer) { + u16 a, b; + buffer = get_next_pair(buffer, &a); + LOG("jf: %d", a); + if (is_register(a)) + a = *get_register(a); + buffer = get_next_pair(buffer, &b); + if (is_register(b)) + b = *get_register(b); + LOG(" %d\n", b); + return !a ? b * 2 : rPC + 6; +} + +int instruction_add(u8 *buffer) { + u16 next, *a, b, c; + buffer = get_next_pair(buffer, &next); + a = get_register(next); + LOG("add: %d ", next); + buffer = get_next_pair(buffer, &b); + if (is_register(b)) + b = *get_register(b); + buffer = get_next_pair(buffer, &c); + if (is_register(c)) + c = *get_register(c); + *a = (b + c) % 32768; + LOG("%d %d\n", b, c); + return rPC + 8; +} + +int instruction_mult(u8 *buffer) { + u16 next, *a, b, c; + buffer = get_next_pair(buffer, &next); + a = get_register(next); + LOG("mult: %d ", next); + buffer = get_next_pair(buffer, &b); + if (is_register(b)) + b = *get_register(b); + buffer = get_next_pair(buffer, &c); + if (is_register(c)) + c = *get_register(c); + *a = (b * c) % 32768; + LOG("%d %d\n", b, c); + return rPC + 8; +} + +int instruction_mod(u8 *buffer) { + u16 next, *a, b, c; + buffer = get_next_pair(buffer, &next); + a = get_register(next); + LOG("mod: %d ", next); + buffer = get_next_pair(buffer, &b); + if (is_register(b)) + b = *get_register(b); + buffer = get_next_pair(buffer, &c); + if (is_register(c)) + c = *get_register(c); + *a = (b % c); + LOG("%d %d\n", b, c); + return rPC + 8; +} + +int instruction_and(u8 *buffer) { + u16 next, *a, b, c; + buffer = get_next_pair(buffer, &next); + LOG("and: %d", next); + a = get_register(next); + buffer = get_next_pair(buffer, &b); + if (is_register(b)) + b = *get_register(b); + buffer = get_next_pair(buffer, &c); + if (is_register(c)) + c = *get_register(c); + LOG(" %d %d\n", b, c); + *a = b & c; + return rPC + 8; +} + +int instruction_or(u8 *buffer) { + u16 next, *a, b, c; + buffer = get_next_pair(buffer, &next); + LOG("or: %d", next); + a = get_register(next); + buffer = get_next_pair(buffer, &b); + if (is_register(b)) + b = *get_register(b); + buffer = get_next_pair(buffer, &c); + if (is_register(c)) + c = *get_register(c); + LOG(" %d %d\n", b, c); + *a = b | c; + return rPC + 8; +} + +int instruction_not(u8 *buffer) { + u16 next, *a, b; + buffer = get_next_pair(buffer, &next); + LOG("not: %d", next); + a = get_register(next); + buffer = get_next_pair(buffer, &b); + if (is_register(b)) + b = *get_register(b); + LOG(" %d\n", b); + *a = ~b; + *a ^= 0x8000; + return rPC + 6; +} + +int instruction_rmem(u8 *buffer) { + u16 next, *a, b; + buffer = get_next_pair(buffer, &next); + LOG("%d: rmem: %d", rPC, next); + a = get_register(next); + buffer = get_next_pair(buffer, &b); + LOG(" %d\n", b); + if (is_register(b)) + b = *get_register(b); + *a = mem_get(&m, b); + return rPC + 6; +} + +int instruction_wmem(u8 *buffer) { + u16 a, b; + buffer = get_next_pair(buffer, &a); + LOG("wmem: %d", a); + if (is_register(a)) + a = *get_register(a); + buffer = get_next_pair(buffer, &b); + LOG(" %d\n", b); + if (is_register(b)) + b = *get_register(b); + mem_set(&m, a, b); + return rPC + 6; +} + +int instruction_call(u8 *buffer) { + u16 a; + buffer = get_next_pair(buffer, &a); + if (is_register(a)) + a = *get_register(a); + LOG("call: %d\n", a); + stack_push(&s, (rPC + 4) / 2); + return a * 2; +} + +int instruction_ret(u8 *buffer) { + u16 addr; + LOG("ret\n"); + addr = stack_pop(&s); + return addr * 2; +} + +int instruction_out(u8 *buffer) { + u16 next; + buffer = get_next_pair(buffer, &next); + if (is_register(next)) + next = *get_register(next); + fprintf(stdout, "%c", next); + return rPC + 4; +} + +int instruction_in(u8 *buffer) { + char in; + u16 addr, *reg = NULL; + get_next_pair(buffer, &addr); + reg = get_register(addr); + LOG("in: %d\n", addr); + in = getchar(); + *reg = in; + return rPC + 4; +} + +int instruction_noop(u8 *buffer) { return rPC + 2; } @@ -0,0 +1,39 @@ +// synacor challenge (@waffle87) +#include "memory.h" +#include "stack.h" +#include "util.h" + +extern Stack s; +extern Memory m; + +int parse(char const *filename); +int operate(u16 opcode, u8 *buffer); + +int is_valid(u16 opcode); +int is_literal(u16 opcode); +int is_register(u16 opcode); +u16 *get_register(u16 opcode); +instruction_ptr get_instruction(u16 opcode); + +int instruction_halt(u8 *buffer); +int instruction_set(u8 *buffer); +int instruction_push(u8 *buffer); +int instruction_pop(u8 *buffer); +int instruction_eq(u8 *buffer); +int instruction_gt(u8 *buffer); +int instruction_jmp(u8 *buffer); +int instruction_jt(u8 *buffer); +int instruction_jf(u8 *buffer); +int instruction_add(u8 *buffer); +int instruction_mult(u8 *buffer); +int instruction_mod(u8 *buffer); +int instruction_and(u8 *buffer); +int instruction_or(u8 *buffer); +int instruction_not(u8 *buffer); +int instruction_rmem(u8 *buffer); +int instruction_wmem(u8 *buffer); +int instruction_call(u8 *buffer); +int instruction_ret(u8 *buffer); +int instruction_out(u8 *buffer); +int instruction_in(u8 *buffer); +int instruction_noop(u8 *buffer); |