From 6fb34179efc44a8d3d39cfa7a514ecaaed83e9f8 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl <0x6A73@pm.me> Date: Mon, 1 Apr 2024 14:00:27 -0600 Subject: initial --- .gitignore | 3 + Makefile | 16 +++ arch-spec | 79 +++++++++++ challenge.bin | Bin 0 -> 59914 bytes codes.txt | 8 ++ input.txt | 77 +++++++++++ main.c | 18 +++ memory.c | 31 +++++ memory.h | 13 ++ readme.md | 1 + stack.c | 20 +++ stack.h | 12 ++ util.c | 37 ++++++ util.h | 19 +++ validate.sh | 26 ++++ vm.c | 412 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ vm.h | 39 ++++++ 17 files changed, 811 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 arch-spec create mode 100644 challenge.bin create mode 100644 codes.txt create mode 100644 input.txt create mode 100644 main.c create mode 100644 memory.c create mode 100644 memory.h create mode 100644 readme.md create mode 100644 stack.c create mode 100644 stack.h create mode 100644 util.c create mode 100644 util.h create mode 100755 validate.sh create mode 100644 vm.c create mode 100644 vm.h 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 to the value of +push: 2 a + push onto the stack +pop: 3 a + remove the top element from the stack and write it into ; empty stack = error +eq: 4 a b c + set to 1 if is equal to ; set it to 0 otherwise +gt: 5 a b c + set to 1 if is greater than ; set it to 0 otherwise +jmp: 6 a + jump to +jt: 7 a b + if is nonzero, jump to +jf: 8 a b + if is zero, jump to +add: 9 a b c + assign into the sum of and (modulo 32768) +mult: 10 a b c + store into the product of and (modulo 32768) +mod: 11 a b c + store into the remainder of divided by +and: 12 a b c + stores into the bitwise and of and +or: 13 a b c + stores into the bitwise or of and +not: 14 a b + stores 15-bit bitwise inverse of in +rmem: 15 a b + read memory at address and write it to +wmem: 16 a b + write the value from into memory at address +call: 17 a + write the address of the next instruction to the stack and jump to +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 to the terminal +in: 20 a + read a character from the terminal and write its ascii code to ; 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 new file mode 100644 index 0000000..6e653f9 Binary files /dev/null and b/challenge.bin differ 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 diff --git a/main.c b/main.c new file mode 100644 index 0000000..840c8dc --- /dev/null +++ b/main.c @@ -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 \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 diff --git a/stack.c b/stack.c new file mode 100644 index 0000000..1ab7a47 --- /dev/null +++ b/stack.c @@ -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; +} diff --git a/stack.h b/stack.h new file mode 100644 index 0000000..289b93b --- /dev/null +++ b/stack.h @@ -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); diff --git a/util.c b/util.c new file mode 100644 index 0000000..c552a32 --- /dev/null +++ b/util.c @@ -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 diff --git a/util.h b/util.h new file mode 100644 index 0000000..460e903 --- /dev/null +++ b/util.h @@ -0,0 +1,19 @@ +// synacor challenge (@waffle87) +#include +#include +#include +#include +#include + +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 \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" diff --git a/vm.c b/vm.c new file mode 100644 index 0000000..cf76c03 --- /dev/null +++ b/vm.c @@ -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; } diff --git a/vm.h b/vm.h new file mode 100644 index 0000000..4a28d84 --- /dev/null +++ b/vm.h @@ -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); -- cgit v1.2.3