commit 388329ae05a27159e1864bf5c4904ee26e3d2a63
parent 24c8d3a4e5f641a8f1ebe6d07145b87ae4135801
Author: Louis Burda <quent.burda@gmail.com>
Date: Sun, 7 Nov 2021 21:47:28 +0100
Add day 9 and refactored maxint
Diffstat:
16 files changed, 838 insertions(+), 174 deletions(-)
diff --git a/libs/Makefile b/libs/Makefile
@@ -1,7 +1,10 @@
CFLAGS = -I include -g -L build
LDLIBS =
-all: build/libaoc.a
+AOC_OBJ_ = wrapper.o aoc.o util.o memvec.o hashmap.o maxint.o
+AOC_OBJ = $(addprefix build/, $(AOC_OBJ_))
+
+all: build/libaoc.a build/libicc.a build/libiccmp.a
clean:
rm -rf build
@@ -12,19 +15,25 @@ build:
build/%.o: src/%.c include/%.h | build
$(CC) -c -o $@ $< $(CFLAGS) $(LDLIBS)
-build/wrapper.o: src/wrapper.c
+build/wrapper.o: src/wrapper.c | build
$(CC) -c -o $@ $< $(CFLAGS) $(LDLIBS)
-build/libaoc.a: build/util.o build/aoc.o build/wrapper.o build/memvec.o build/icc.o build/hashmap.o
+build/libaoc.a: $(AOC_OBJ) | build
+ ar rcs $@ $^
+
+build/libicc.a: build/icc.o | build
+ ar rcs $@ $^
+
+build/libiccmp.a: build/iccmp.o | build
ar rcs $@ $^
-build/test_%: tests/%.c
+build/test_%: tests/%.c | build
$(CC) -o $@ $< $(CFLAGS) $(LDLIBS)
-build/test_maxint: tests/maxint.c build/maxint.o
+build/test_maxint: tests/maxint.c build/maxint.o | build
$(CC) -o $@ $^ $(CFLAGS) $(LDLIBS) -laoc
-build/test_%.log: build/test_%
+build/test_%.log: build/test_% | build
@echo "--- Running test: $< ---"
@valgrind --track-origins=yes --leak-check=full $< 2>&1 | tee $@
diff --git a/libs/include/iccmp.h b/libs/include/iccmp.h
@@ -0,0 +1,65 @@
+#include "aoc.h"
+#include "util.h"
+#include "memvec.h"
+#include "maxint.h"
+
+#include <stdlib.h>
+
+enum {
+ ICC_OK,
+ ICC_INPUT,
+ ICC_OUTPUT,
+ ICC_HALT
+};
+
+enum {
+ ICC_PARAM_IMM,
+ ICC_PARAM_POS,
+ ICC_PARAM_REL
+};
+
+enum {
+ ICC_INST_ADD = 1,
+ ICC_INST_MULT = 2,
+ ICC_INST_STORE = 3,
+ ICC_INST_LOAD = 4,
+ ICC_INST_JMPT = 5,
+ ICC_INST_JMPF = 6,
+ ICC_INST_TLT = 7,
+ ICC_INST_TEQ = 8,
+ ICC_INST_BASE = 9,
+
+ ICC_INST_HALT = 99
+};
+
+typedef uint64_t inst_t;
+
+struct icc {
+ int status;
+ struct maxint in, out;
+ struct maxint base;
+
+ /* general purpose registers */
+ struct maxint r1, r2, r3, r4;
+
+ size_t instp;
+ struct memvec instructions;
+};
+
+int icc_init(struct icc *icc);
+void icc_free(struct icc *icc);
+void icc_copy(struct icc *dst, struct icc *src);
+
+void * icc_inst_copy(struct icc *icc);
+void icc_reset(struct icc *icc, void *instcopy);
+
+int icc_parse_inst(struct icc *icc, const char *str, size_t len);
+void icc_step_inst(struct icc *icc);
+
+void icc_set_val(struct icc *icc, size_t addr, struct maxint *in);
+void icc_get_val(struct icc *icc, size_t addr, struct maxint *out);
+void icc_get_inst(struct icc *icc, size_t addr, inst_t *out);
+
+int icc_param_mode(inst_t inst, int param);
+void icc_get_param(struct icc *icc, int param, struct maxint *out);
+void icc_get_dest(struct icc *icc, int param, struct maxint *out);
diff --git a/libs/include/maxint.h b/libs/include/maxint.h
@@ -1,12 +1,13 @@
+#ifndef AOC_MAXINT_H
+#define AOC_MAXINT_H
+
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include "util.h"
-#define MI_MAX(a,b) ((a) > (b) ? (a) : (b))
-#define MI_MIN(a,b) ((a) < (b) ? (a) : (b))
-#define MI_SWAP(a,b) do { typeof(a) t = a; a = b; b = t; } while (0)
+#define MI_SWAP(a,b) a ^= b ^= a
#define MI_DIVCEIL(a,b) ((a) / (b) + ((a) % (b) != 0))
@@ -19,43 +20,50 @@
#define MI_NEG 1
#define MI_POS 0
+#define MI_INIT ((struct maxint) { \
+ .data = NULL, \
+ .size = 0, \
+ .cap = 0, \
+ .sign = MI_POS, \
+})
+
/* unsigned underlying type */
typedef uint64_t mi_ul;
struct maxint {
- mi_ul* data;
- mi_ul imm;
- size_t size, last;
- uint8_t sign;
+ mi_ul *data;
+ int size, cap;
+ int sign;
};
-void mi_shrink(struct maxint *m1);
-
-int mi_cmp(const struct maxint *m1, const struct maxint *m2); // m1 < m2 ? m2 > m1 ? 1 : 0 : -1
+void mi_parse(struct maxint *m, const char *str, const char **end, const char *alph);
+void mi_free(struct maxint *m);
-void mi_add(struct maxint *m1, const struct maxint *m2); // m1 += m2
-void mi_sub(struct maxint *m1, const struct maxint *m2); // m1 -= m2
-void mi_shl(struct maxint *m1, int64_t shift);
-void mi_mul(struct maxint *m1, const struct maxint *m2); // m1 *= m2
-void mi_div(struct maxint *m1, struct maxint *m2, const struct maxint *m3); // m1 /= m3, m2 %= m3
void mi_set(struct maxint *m1, const struct maxint *m2); // m1 = m2
-void mi_setv(struct maxint *m1, mi_ul v, int sign);
-void mi_swap(struct maxint *m1, struct maxint *m2); // m1 <=> m2
+void mi_setv(struct maxint *m, mi_ul v, int sign);
-void mi_resize(struct maxint *m1, size_t size);
+void mi_resize(struct maxint *m, int size);
-const struct maxint* mi_imm(struct maxint *dst, mi_ul v, int sign);
+mi_ul mi_cast_ul(const struct maxint *m);
-mi_ul mi_cast_ul(const struct maxint *m1);
+int mi_zero(const struct maxint *m);
-void mi_parse(struct maxint *m1, const char *vstr);
+int mi_lastset(const struct maxint *m);
-void mi_free(struct maxint *m1);
+void mi_add(struct maxint *m1, const struct maxint *m2); // m1 += m2
+void mi_sub(struct maxint *m1, const struct maxint *m2); // m1 -= m2
+void mi_shl(struct maxint *m, uint64_t shift); // m1 <<= shift
+void mi_shr(struct maxint *m, uint64_t shift); // m1 >>= shift
+void mi_mul(struct maxint *m1, const struct maxint *m2); // m1 *= m2
+void mi_div(struct maxint *m1, struct maxint *m2, const struct maxint *m3); // m1 /= m3, m2 = m1 % m3
+void mi_swap(struct maxint *m1, struct maxint *m2); // m1 <=> m2
+int mi_cmp(const struct maxint *m1, const struct maxint *m2); // m1 < m2 ? m2 > m1 ? 1 : 0 : -1
-int mi_zero(const struct maxint *m1);
+char * mi_convstr(char *alloc, const struct maxint *m, int base, const char *alph);
+char * mi_hexstr(char *alloc, const struct maxint *m, int cap);
+char * mi_decstr(char *alloc, const struct maxint *m);
+char * mi_binstr(char *alloc, const struct maxint *m);
-char* mi_convstr(const struct maxint *m1, int base, const char *alph);
-char* mi_hexstr(const struct maxint *m1, int cap);
-char* mi_decstr(const struct maxint *m1);
+extern struct maxint mi_one;
-extern struct maxint mi_tmp;
+#endif
diff --git a/libs/include/memvec.h b/libs/include/memvec.h
@@ -18,3 +18,4 @@ void memvec_set(struct memvec *v, size_t index, void *item);
int memvec_in_range(struct memvec *v, size_t index);
size_t memvec_len(struct memvec *v);
void memvec_copy(struct memvec *dst, struct memvec *src);
+void memvec_resize(struct memvec *v, size_t size);
diff --git a/libs/include/util.h b/libs/include/util.h
@@ -12,12 +12,11 @@
#define LOC() __FILE__ ":" STR(__LINE__)
#define ASSERT(expr) assert(expr, \
- "Assert '" #expr "' at " LOC() " failed\n")
-#define ASSERTV(expr, msg, ...) assert(expr, \
- LOC() " : " msg "\n" __VA_OPT__(,) __VA_ARGS__)
+ "Assert '" #expr "' at " LOC() " failed")
+#define ASSERTV(expr, ...) assert(expr, LOC() " : " __VA_ARGS__)
#define CHKP(ptr) chkp(ptr, \
- "Unexpected NULL pointer '" #ptr "' at " LOC() "\n")
+ "Unexpected NULL pointer '" #ptr "' at " LOC())
#define ABS(a) ((a) > 0 ? (a) : -(a))
diff --git a/libs/src/iccmp.c b/libs/src/iccmp.c
@@ -0,0 +1,424 @@
+#include "iccmp.h"
+
+int
+icc_init(struct icc *icc)
+{
+ icc->instp = 0;
+ icc->status = ICC_OK;
+ icc->base = MI_INIT;
+ mi_setv(&icc->base, 0, MI_POS);
+ icc->in = icc->out = MI_INIT;
+ icc->r1 = icc->r2 = icc->r3 = icc->r4 = MI_INIT;
+ return memvec_init(&icc->instructions, 0, sizeof(struct maxint));
+}
+
+void
+icc_free(struct icc *icc)
+{
+ mi_free(&icc->in);
+ mi_free(&icc->out);
+ mi_free(&icc->r1);
+ mi_free(&icc->r2);
+ mi_free(&icc->r3);
+ mi_free(&icc->r4);
+ memvec_free(&icc->instructions);
+}
+
+void
+icc_copy(struct icc *dst, struct icc *src)
+{
+ dst->instp = src->instp;
+ dst->status = src->status;
+ dst->base = src->base;
+ dst->in = MI_INIT;
+ mi_set(&dst->in, &src->in);
+ dst->out = MI_INIT;
+ mi_set(&dst->out, &src->out);
+ memvec_copy(&dst->instructions, &src->instructions);
+}
+
+void*
+icc_inst_copy(struct icc *icc)
+{
+ return CHKP(memdup(icc->instructions.data, icc->instructions.len));
+}
+
+void
+icc_reset(struct icc *icc, void *instcopy)
+{
+ icc->status = ICC_OK;
+ icc->instp = 0;
+ mi_setv(&icc->base, 0, MI_POS);
+ mi_setv(&icc->in, 0, MI_POS);
+ mi_setv(&icc->out, 0, MI_POS);
+ if (instcopy)
+ memcpy(icc->instructions.data, instcopy, icc->instructions.len);
+}
+
+int
+icc_parse_inst(struct icc *icc, const char *str, size_t len)
+{
+ const char *line = str, *nline, *end = str + len;
+ const char *endptr = NULL;
+ struct maxint val;
+ size_t linelen;
+
+ do {
+ nline = ntoken(line, end, &linelen, ",\n");
+ val = MI_INIT;
+ mi_parse(&val, line, &endptr, "0123456789");
+ if (endptr && !memchr(",\n", *endptr, 3))
+ goto fail;
+ if (!memvec_add(&icc->instructions, &val))
+ goto fail;
+ line = nline;
+ } while (nline);
+
+ return OK;
+
+fail:
+ mi_free(&val);
+ return FAIL;
+}
+
+void
+icc_debug_op(struct icc *icc, const char *opstr, int n, int dst)
+{
+ inst_t inst;
+ char *str;
+ int i;
+
+ if (!aoc.debug) return;
+
+ icc_get_inst(icc, icc->instp, &inst);
+
+ fprintf(stderr, "%04li: (%05lu) %s ", icc->instp, inst, opstr);
+
+ str = NULL;
+ for (i = 1; i <= n; i++) {
+ if (i > 1) fprintf(stderr, ", ");
+ icc_get_val(icc, icc->instp + i, &icc->r1);
+ switch (icc_param_mode(inst, i)) {
+ case ICC_PARAM_IMM:
+ str = mi_decstr(str, &icc->r1);
+ fprintf(stderr, "%s", str);
+ break;
+ case ICC_PARAM_POS:
+ str = mi_decstr(str, &icc->r1);
+ fprintf(stderr, "[%s]", str);
+ if (i != dst) {
+ icc_get_val(icc, mi_cast_ul(&icc->r1), &icc->r1);
+ str = mi_decstr(str, &icc->r1);
+ fprintf(stderr, "=%s", str);
+ }
+ break;
+ case ICC_PARAM_REL:
+ str = mi_decstr(str, &icc->r1);
+ fprintf(stderr, "[B%s%s=", *str == '-' ? "" : "+", str);
+ mi_add(&icc->r1, &icc->base);
+ str = mi_decstr(str, &icc->r1);
+ fprintf(stderr, "%s]", str);
+ if (i != dst) {
+ icc_get_val(icc, mi_cast_ul(&icc->r1), &icc->r1);
+ str = mi_decstr(str, &icc->r1);
+ fprintf(stderr, "=%s", str);
+ }
+ break;
+ default:
+ die("ICC: Unknown parmeter mode\n");
+ }
+ }
+ free(str);
+
+ fprintf(stderr, "\n");
+}
+
+void
+icc_inst_add(struct icc *icc)
+{
+ icc_debug_op(icc, "ADD", 3, 3);
+
+ icc_get_param(icc, 1, &icc->r1);
+ icc_get_param(icc, 2, &icc->r2);
+ icc_get_dest(icc, 3, &icc->r3);
+
+ mi_add(&icc->r1, &icc->r2);
+ icc_set_val(icc, mi_cast_ul(&icc->r3), &icc->r1);
+
+ icc->instp += 4;
+ icc->status = ICC_OK;
+}
+
+void
+icc_inst_mul(struct icc *icc)
+{
+ icc_debug_op(icc, "MUL", 3, 3);
+
+ icc_get_param(icc, 1, &icc->r1);
+ icc_get_param(icc, 2, &icc->r2);
+ icc_get_dest(icc, 3, &icc->r3);
+
+ mi_mul(&icc->r1, &icc->r2);
+ icc_set_val(icc, mi_cast_ul(&icc->r3), &icc->r1);
+
+ icc->instp += 4;
+ icc->status = ICC_OK;
+}
+
+void
+icc_inst_store(struct icc *icc)
+{
+ if (icc->status != ICC_INPUT) {
+ icc_debug_op(icc, "INPUT", 0, 0);
+ icc->status = ICC_INPUT;
+ } else {
+ icc_debug_op(icc, "STORE", 1, 1);
+ icc_get_dest(icc, 1, &icc->r1);
+ icc_set_val(icc, mi_cast_ul(&icc->r1), &icc->in);
+
+ icc->instp += 2;
+ icc->status = ICC_OK;
+ }
+}
+
+void
+icc_inst_load(struct icc *icc)
+{
+ if (icc->status != ICC_OUTPUT) {
+ icc_debug_op(icc, "LOAD", 1, 0);
+ icc_get_param(icc, 1, &icc->out);
+
+ icc->status = ICC_OUTPUT;
+ icc_debug_op(icc, "OUTPUT", 0, 0);
+ } else {
+ icc->instp += 2;
+ icc->status = ICC_OK;
+ }
+}
+
+void
+icc_inst_jmp_true(struct icc *icc)
+{
+ icc_debug_op(icc, "JMPT", 2, 0);
+
+ icc_get_param(icc, 1, &icc->r1);
+ icc_get_param(icc, 2, &icc->r2);
+
+ if (!mi_zero(&icc->r1)) icc->instp = mi_cast_ul(&icc->r2);
+ else icc->instp += 3;
+
+ icc->status = ICC_OK;}
+
+void
+icc_inst_jmp_false(struct icc *icc)
+{
+ icc_debug_op(icc, "JMPF", 2, 0);
+
+ icc_get_param(icc, 1, &icc->r1);
+ icc_get_param(icc, 2, &icc->r2);
+
+ if (mi_zero(&icc->r1)) icc->instp = mi_cast_ul(&icc->r2);
+ else icc->instp += 3;
+
+ icc->status = ICC_OK;
+}
+
+void
+icc_inst_test_lt(struct icc *icc)
+{
+ icc_debug_op(icc, "TLT", 3, 3);
+
+ icc_get_param(icc, 1, &icc->r1);
+ icc_get_param(icc, 2, &icc->r2);
+ icc_get_dest(icc, 3, &icc->r3);
+
+ mi_setv(&icc->r4, mi_cmp(&icc->r1, &icc->r2) < 0, MI_POS);
+ icc_set_val(icc, mi_cast_ul(&icc->r3), &icc->r4);
+
+ icc->instp += 4;
+ icc->status = ICC_OK;
+}
+
+void
+icc_inst_test_eq(struct icc *icc)
+{
+ icc_debug_op(icc, "TEQ", 3, 3);
+
+ icc_get_param(icc, 1, &icc->r1);
+ icc_get_param(icc, 2, &icc->r2);
+ icc_get_dest(icc, 3, &icc->r3);
+
+ mi_setv(&icc->r4, mi_cmp(&icc->r1, &icc->r2) == 0, MI_POS);
+ icc_set_val(icc, mi_cast_ul(&icc->r3), &icc->r4);
+
+ icc->instp += 4;
+ icc->status = ICC_OK;
+}
+
+void
+icc_inst_base(struct icc *icc)
+{
+ icc_debug_op(icc, "BASE", 1, 0);
+
+ icc_get_param(icc, 1, &icc->r1);
+ mi_add(&icc->base, &icc->r1);
+
+ icc->instp += 2;
+ icc->status = ICC_OK;
+}
+
+void
+icc_inst_halt(struct icc *icc)
+{
+ icc_debug_op(icc, "HALT", 0, 0);
+
+ icc->status = ICC_HALT;
+}
+
+void
+icc_step_inst(struct icc *icc)
+{
+ inst_t inst;
+
+ icc_get_inst(icc, icc->instp, &inst);
+ inst %= 100;
+
+ switch (inst) {
+ case ICC_INST_ADD:
+ icc_inst_add(icc);
+ break;
+ case ICC_INST_MULT:
+ icc_inst_mul(icc);
+ break;
+ case ICC_INST_STORE:
+ icc_inst_store(icc);
+ break;
+ case ICC_INST_LOAD:
+ icc_inst_load(icc);
+ break;
+ case ICC_INST_JMPT:
+ icc_inst_jmp_true(icc);
+ break;
+ case ICC_INST_JMPF:
+ icc_inst_jmp_false(icc);
+ break;
+ case ICC_INST_TLT:
+ icc_inst_test_lt(icc);
+ break;
+ case ICC_INST_TEQ:
+ icc_inst_test_eq(icc);
+ break;
+ case ICC_INST_BASE:
+ icc_inst_base(icc);
+ break;
+ case ICC_INST_HALT:
+ icc_inst_halt(icc);
+ break;
+ default:
+ die("ICC: Unknown instruction: '%i'\n", inst);
+ }
+}
+
+void
+icc_set_val(struct icc *icc, size_t addr, struct maxint *val)
+{
+ struct maxint *v, blank;
+ size_t i, len;
+
+ len = memvec_len(&icc->instructions);
+ if (addr >= len) {
+ blank = MI_INIT;
+ memvec_resize(&icc->instructions, addr + 1);
+ for (i = len; i <= addr; i++)
+ memvec_set(&icc->instructions, i, &blank);
+ }
+ v = memvec_get(&icc->instructions, addr);
+ mi_set(v, val);
+}
+
+void
+icc_get_val(struct icc *icc, size_t addr, struct maxint *out)
+{
+ struct maxint *src;
+
+ if (addr >= memvec_len(&icc->instructions)) {
+ mi_setv(out, 0, MI_POS);
+ } else {
+ src = memvec_get(&icc->instructions, addr);
+ mi_set(out, src);
+ }
+}
+
+void
+icc_get_inst(struct icc *icc, size_t addr, inst_t *out)
+{
+ struct maxint *src;
+
+ src = memvec_get(&icc->instructions, addr);
+ *out = mi_cast_ul(src);
+}
+
+int
+icc_param_mode(inst_t inst, int param)
+{
+ int div, i;
+
+ div = 100;
+ for (i = 1; i < param; i++) div *= 10;
+
+ switch ((inst / div) % 10) {
+ case 0:
+ return ICC_PARAM_POS;
+ case 1:
+ return ICC_PARAM_IMM;
+ case 2:
+ return ICC_PARAM_REL;
+ }
+
+ die("ICC: Invalid param mode %i\n");
+ return -1;
+}
+
+void
+icc_get_param(struct icc *icc, int param, struct maxint *out)
+{
+ inst_t inst;
+
+ icc_get_inst(icc, icc->instp, &inst);
+ switch (icc_param_mode(inst, param)) {
+ case ICC_PARAM_IMM:
+ icc_get_val(icc, icc->instp + param, out);
+ break;
+ case ICC_PARAM_POS:
+ icc_get_val(icc, icc->instp + param, out);
+ icc_get_val(icc, mi_cast_ul(out), out);
+ break;
+ case ICC_PARAM_REL:
+ icc_get_val(icc, icc->instp + param, out);
+ mi_add(out, &icc->base);
+ icc_get_val(icc, mi_cast_ul(out), out);
+ break;
+ default:
+ die("ICC: Invalid parmeter mode\n");
+ };
+}
+
+void
+icc_get_dest(struct icc *icc, int param, struct maxint *out)
+{
+ inst_t inst;
+
+ icc_get_inst(icc, icc->instp, &inst);
+ switch (icc_param_mode(inst, param)) {
+ case ICC_PARAM_POS:
+ icc_get_val(icc, icc->instp + param, out);
+ break;
+ case ICC_PARAM_REL:
+ icc_get_val(icc, icc->instp + param, out);
+ mi_add(out, &icc->base);
+ break;
+ default:
+ die("ICC: Invalid destination parmeter mode\n");
+ };
+}
+
diff --git a/libs/src/maxint.c b/libs/src/maxint.c
@@ -1,13 +1,88 @@
#include "maxint.h"
-struct maxint mi_tmp;
+mi_ul mi_one_v = 1;
+struct maxint mi_one = {
+ .data = &mi_one_v,
+ .size = 1,
+ .cap = 1,
+ .sign = MI_POS
+};
+
+void
+mi_parse(struct maxint *m, const char *str, const char **end, const char *alph)
+{
+ const char *p, *cp;
+ struct maxint tmp, base;
+ int sign;
+
+ sign = MI_POS;
+ if (*str == '-') {
+ sign = MI_NEG;
+ str++;
+ } else if (*str == '+')
+ str++;
+
+ base = MI_INIT;
+ mi_setv(&base, strlen(alph), sign);
+
+ tmp = MI_INIT;
+ mi_setv(m, 0, MI_POS);
+ for (p = str; *p && (cp = strchr(alph, *p)); p++) {
+ mi_mul(m, &base);
+ mi_setv(&tmp, cp - alph, sign);
+ mi_add(m, &tmp);
+ }
+
+ *end = p;
+
+ mi_free(&tmp);
+ mi_free(&base);
+}
+
+void
+mi_free(struct maxint *m)
+{
+ free(m->data);
+ m->data = NULL;
+ m->size = 0;
+ m->cap = 0;
+}
+
+void
+mi_set(struct maxint *m1, const struct maxint *m2)
+{
+ mi_resize(m1, m2->size);
+ memcpy(m1->data, m2->data, m2->size * MI_ULBYTES);
+ m1->sign = m2->sign;
+}
+
+void
+mi_setv(struct maxint *m, mi_ul v, int sign)
+{
+ mi_resize(m, 1);
+ memcpy(m->data, &v, MI_ULBYTES);
+ m->sign = sign;
+}
+
+void
+mi_resize(struct maxint *m, int size)
+{
+ if (size > m->cap || size < m->cap - 256) {
+ m->cap = size;
+ m->data = CHKP(realloc(m->data, m->cap * MI_ULBYTES));
+ }
+ if (size > m->size) {
+ memset(&m->data[m->size], 0, (size - m->size) * MI_ULBYTES);
+ }
+ m->size = size;
+}
void
mi_add_internal(struct maxint *m1, const struct maxint *m2, int m2_sign)
{
int carry, swapped;
- size_t i;
mi_ul v;
+ int i;
if (m2->size >= m1->size)
mi_resize(m1, m2->size + 1);
@@ -52,68 +127,51 @@ mi_sub(struct maxint *m1, const struct maxint *m2)
mi_add_internal(m1, m2, m2->sign ^ 1);
}
-int
-mi_cmp(const struct maxint *m1, const struct maxint *m2)
+void
+mi_shl(struct maxint *m, uint64_t shift)
{
- size_t i;
- mi_ul v1, v2;
+ int i, bit;
- for (i = 0; i < MI_MAX(m1->size, m2->size); i++) {
- v1 = (i >= m1->size ? 0 : m1->data[i]);
- v2 = (i >= m2->size ? 0 : m2->data[i]);
- if (v1 != v2) return v1 > v2 ? 1 : -1;
- }
+ if (!shift) return;
+ mi_resize(m, mi_lastset(m) + 1 + MI_DIVCEIL(shift, MI_ULBITS));
- return 0;
+ for (i = m->size * MI_ULBITS - 1; i >= 0; i--) {
+ m->data[i / MI_ULBITS] &= ~((mi_ul) 1 << (i % MI_ULBITS));
+ if (i >= shift) {
+ bit = MI_BITA(m->data, MI_ULBITS, i - shift);
+ m->data[i / MI_ULBITS] |= (mi_ul) bit << (i % MI_ULBITS);
+ }
+ }
}
-int
-mi_lastset(struct maxint *m1)
+void
+mi_shr(struct maxint *m, uint64_t shift)
{
- int64_t i;
+ int i, bit;
- for (i = m1->size - 1; i >= 0; i--)
- if (m1->data[i] != 0) return i;
- return 0;
-}
+ if (!shift) return;
-void
-mi_shl(struct maxint *m1, int64_t shift)
-{
- size_t newsize;
- int64_t i, k;
-
- if (shift > 0)
- mi_resize(m1, mi_lastset(m1) + MI_DIVCEIL(shift, MI_ULBITS));
-
- for (i = 0; i < m1->size * MI_ULBITS; i++) {
- k = (shift >= 0) ? (m1->size * MI_ULBITS - 1 - i) : i;
- m1->data[k / MI_ULBITS] &= ~((mi_ul) 1 << (k % MI_ULBITS));
- if (k - shift >= 0 && k - shift < MI_ULBITS)
- m1->data[k / MI_ULBITS] |= MI_BITA(m1->data, MI_ULBITS, k - shift)
- << (k % MI_ULBITS);
- //printf("%li ", k);
- //for (int j = 0; j < MI_ULBITS; j++) {
- // if (j == k % MI_ULBITS)
- // printf("X");
- // else
- // printf("%c", MI_BITA(m1->data, MI_ULBITS, j) ? '1' : '0');
- //}
- //printf("\n");
+ for (i = 0; i < m->size * MI_ULBITS; i++) {
+ m->data[i / MI_ULBITS] &= ~((mi_ul) 1 << (i % MI_ULBITS));
+ if (i + shift < m->size * MI_ULBITS) {
+ bit = MI_BITA(m->data, MI_ULBITS, i + shift);
+ m->data[i / MI_ULBITS] |= (mi_ul) bit << (i % MI_ULBITS);
+ }
}
}
void
mi_mul(struct maxint *m1, const struct maxint *m2)
{
- struct maxint sum = { 0 }, tmp = { 0 };
+ struct maxint sum;
int64_t i;
+ sum = MI_INIT;
mi_setv(&sum, 0, MI_POS);
for (i = m1->size * MI_ULBITS - 1; i >= 0; i--) {
+ mi_shl(&sum, 1);
if (MI_BITA(m1->data, MI_ULBITS, i))
mi_add(&sum, m2);
- mi_shl(&sum, 1);
}
mi_swap(&sum, m1);
@@ -123,30 +181,29 @@ mi_mul(struct maxint *m1, const struct maxint *m2)
void
mi_div(struct maxint *mul, struct maxint *urem, const struct maxint *div)
{
- struct maxint orig = { 0 }, tmp = { 0 }, irem = { 0 }, *rem;
- size_t i, k;
+ struct maxint orig, irem, one, *rem;
+ int i, k;
+ orig = irem = MI_INIT;
rem = (urem == NULL) ? &irem : urem;
mi_swap(&orig, mul);
mi_setv(mul, 0, MI_POS);
mi_setv(rem, 0, MI_POS);
+
for (i = 0; i < orig.size * MI_ULBITS; i++) {
k = orig.size * MI_ULBITS - 1 - i;
// rem = rem * 2 + [bit set]
mi_shl(rem, 1);
if (MI_BITA(orig.data, MI_ULBITS, k))
- mi_add(rem, mi_imm(&tmp, 1, MI_POS));
+ mi_add(rem, &mi_one);
// mul = 2 * mul + [rem >= div]
mi_shl(mul, 1);
- //printf(".\n");
- //printf("%li %li %li\n", k, rem->data[0], mul->data[0]);
if (mi_cmp(rem, div) >= 0) {
- mi_add(mul, mi_imm(&tmp, 1, MI_POS));
+ mi_add(mul, &mi_one);
mi_sub(rem, div);
}
- //printf("%li %li %li\n", k, rem->data[0], mul->data[0]);
}
if (orig.sign != div->sign)
@@ -160,128 +217,123 @@ mi_div(struct maxint *mul, struct maxint *urem, const struct maxint *div)
}
void
-mi_set(struct maxint *m1, const struct maxint *m2)
+mi_swap(struct maxint *m1, struct maxint *m2)
{
- if (m1->size < m2->size)
- mi_resize(m1, m2->size);
- memcpy(m1->data, m2->data, m2->size * MI_ULBYTES);
- if (m1->size > m2->size)
- memset(m1->data + m2->size * MI_ULBYTES, 0,
- (m1->size - m2->size) * MI_ULBYTES);
- m1->sign = m2->sign;
+ struct maxint tmp;
+
+ memcpy(&tmp, m1, sizeof(struct maxint));
+ memcpy(m1, m2, sizeof(struct maxint));
+ memcpy(m2, &tmp, sizeof(struct maxint));
}
-void
-mi_setv(struct maxint *m1, mi_ul v, int sign)
+int
+mi_cmp(const struct maxint *m1, const struct maxint *m2)
{
- if (m1->size < 1) {
- m1->data = CHKP(malloc(MI_ULBYTES));
- m1->size = 1;
+ mi_ul v1, v2;
+ int i;
+
+ for (i = 0; i < MAX(m1->size, m2->size); i++) {
+ v1 = (i >= m1->size ? 0 : m1->data[i]);
+ v2 = (i >= m2->size ? 0 : m2->data[i]);
+ if (v1 != v2) return v1 > v2 ? 1 : -1;
}
- m1->data[0] = v;
- m1->sign = sign;
-}
-void
-mi_swap(struct maxint *m1, struct maxint *m2)
-{
- MI_SWAP(m1->data, m2->data);
- MI_SWAP(m1->size, m2->size);
- MI_SWAP(m1->imm, m2->imm);
- MI_SWAP(m1->sign, m2->sign);
+ return 0;
}
-void
-mi_resize(struct maxint *m1, size_t size)
+int
+mi_lastset(const struct maxint *m1)
{
- m1->data = CHKP(realloc(m1->data, size * MI_ULBYTES));
- if (size > m1->size)
- memset(&m1->data[m1->size], 0, (size - m1->size) * MI_ULBYTES);
- m1->size = size;
-}
+ int i;
-const struct maxint*
-mi_imm(struct maxint *dst, mi_ul v, int sign)
-{
- dst->imm = v;
- dst->data = &(dst->imm);
- dst->size = 1;
- dst->sign = sign;
- return dst;
+ for (i = m1->size - 1; i >= 0; i--)
+ if (m1->data[i] != 0) return i;
+
+ return 0;
}
mi_ul
mi_cast_ul(const struct maxint *m1)
{
+ assert(mi_lastset(m1) == 0, "MAXINT: Attempted cast on too large value");
return m1->data[0];
}
-void
-mi_free(struct maxint *m1)
-{
- free(m1->data);
- m1->data = NULL;
- m1->size = 0;
-}
-
int
mi_zero(const struct maxint *m1)
{
- size_t i;
+ int i;
for (i = 0; i < m1->size; i++)
if (m1->data[i] != 0) return 0;
+
return 1;
}
-char*
-mi_convstr(const struct maxint *m1, int base, const char *alph)
+char *
+mi_convstr(char *alloc, const struct maxint *m, int base_ul, const char *alph)
{
- struct maxint num = { 0 }, rem = { 0 }, tmp = { 0 };
- size_t i, k, rest, slen, scap;
- char *strbuf;
+ struct maxint num, rem, base;
+ int i, k, slen, scap;
+ char *strbuf, tmp;
+ mi_ul rest;
int carry;
- if (base <= 1) return CHKP(strdup(""));
+ if (base_ul <= 1) return CHKP(strdup(""));
- mi_set(&num, m1);
+ num = rem = base = MI_INIT;
+ mi_set(&num, m);
+ num.sign = MI_POS;
mi_setv(&rem, 0, MI_POS);
scap = 16;
slen = 0;
- strbuf = malloc(scap);
+ strbuf = CHKP(alloc ? realloc(alloc, scap) : malloc(scap));
+ mi_setv(&base, base_ul, MI_POS);
do {
- mi_div(&num, &rem, mi_imm(&tmp, base, MI_POS));
+ mi_div(&num, &rem, &base);
rest = mi_cast_ul(&rem);
- strbuf[slen] = alph[rest];
- slen++;
- if (slen >= scap) {
+ if (slen + 1 >= scap) {
scap *= 2;
- strbuf = realloc(strbuf, scap);
+ strbuf = CHKP(realloc(strbuf, scap));
}
+ strbuf[slen] = alph[rest];
+ slen++;
} while (!mi_zero(&num));
- for (i = 0; i < slen / 2; i++)
- MI_SWAP(strbuf[i], strbuf[slen - 1 - i]);
+ if (m->sign == MI_NEG)
+ strbuf[slen++] = '-';
+
+ for (i = 0; i < slen / 2; i++) {
+ tmp = strbuf[i];
+ strbuf[i] = strbuf[slen - 1 - i];
+ strbuf[slen - 1 - i] = tmp;
+ }
strbuf[slen] = '\0';
mi_free(&rem);
mi_free(&num);
+ mi_free(&base);
return strbuf;
}
-char*
-mi_hexstr(const struct maxint *m1, int cap)
+char *
+mi_hexstr(char *alloc, const struct maxint *m, int cap)
{
- return mi_convstr(m1, 16, cap ? "0123456789ABCDEF" : "0123456789abcdef");
+ return mi_convstr(alloc, m, 16, cap ? "0123456789ABCDEF" : "0123456789abcdef");
}
-char*
-mi_decstr(const struct maxint *m1)
+char *
+mi_decstr(char *alloc, const struct maxint *m)
{
- return mi_convstr(m1, 10, "0123456789");
+ return mi_convstr(alloc, m, 10, "0123456789");
}
+char *
+mi_binstr(char *alloc, const struct maxint *m)
+{
+ return mi_convstr(alloc, m, 2, "01");
+}
diff --git a/libs/src/memvec.c b/libs/src/memvec.c
@@ -71,3 +71,13 @@ memvec_copy(struct memvec *dst, struct memvec *src)
dst->data = CHKP(malloc(src->cap));
memcpy(dst->data, src->data, src->cap);
}
+
+void
+memvec_resize(struct memvec *v, size_t size)
+{
+ v->len = size * v->itemsize;
+ if (v->len > v->cap || v->len < v->cap - 256) {
+ v->cap = v->len;
+ v->data = CHKP(realloc(v->data, v->cap));
+ }
+}
diff --git a/libs/src/util.c b/libs/src/util.c
@@ -21,6 +21,7 @@ assert(int res, const char *fmtstr, ...)
if (!res) {
va_start(ap, fmtstr);
vfprintf(stderr, fmtstr, ap);
+ fputc('\n', stderr);
va_end(ap);
exit(1);
@@ -35,6 +36,7 @@ chkp(void *ptr, const char *fmtstr, ...)
if (ptr == NULL) {
va_start(ap, fmtstr);
vfprintf(stderr, fmtstr, ap);
+ fputc('\n', stderr);
va_end(ap);
exit(1);
diff --git a/libs/tests/maxint.c b/libs/tests/maxint.c
@@ -3,21 +3,48 @@
int
main()
{
- struct maxint a = { 0 }, b = { 0 };
+ struct maxint a, b, c;
char *s1, *s2;
- mi_setv(&a, -1, MI_POS);
- mi_setv(&b, 33, MI_POS);
- printf("%lu / %lu = ", a.data[0], b.data[0]);
- mi_div(&a, NULL, &b);
- printf("%lu\n", a.data[0]);
+ a = b = c = MI_INIT;
+ s1 = s2 = NULL;
- printf("DEC: %s\n", (s1 = mi_convstr(&a, 10, "0123456789")));
- printf("HEX: %s\n", (s2 = mi_convstr(&a, 16, "0123456789ABCDEF")));
+ mi_setv(&a, 1014, MI_POS);
+ mi_setv(&b, 9, MI_NEG);
+ printf("ADD: %s + %s = ", (s1 = mi_decstr(s1, &a)), (s2 = mi_decstr(s2, &b)));
+ mi_add(&a, &b);
+ printf("%s\n", (s1 = mi_decstr(s1, &a)));
- mi_free(&a);
- mi_free(&b);
+ mi_setv(&a, 10000000000000000000ULL, MI_POS);
+ mi_setv(&b, 10000000000000000000ULL, MI_POS);
+ printf("ADD: %s + %s = ", (s1 = mi_decstr(s1, &a)), (s2 = mi_decstr(s2, &b)));
+ mi_add(&a, &b);
+ printf("%s\n", (s1 = mi_decstr(s1, &a)));
+
+ mi_setv(&a, 10000000000000000000ULL, MI_POS);
+ printf("SHL: %s << 2 = \n", (s1 = mi_binstr(s1, &a)));
+ mi_shl(&a, 2);
+ printf("%s\n", (s1 = mi_binstr(s1, &a)));
+
+ mi_setv(&a, 10000000000000000000ULL, MI_POS);
+ mi_setv(&b, 10000000000000000000ULL, MI_POS);
+ printf("%lu * %lu = ..\n", a.data[0], b.data[0]);
+ printf("%s * %s = ", (s1 = mi_decstr(s1, &a)), (s2 = mi_decstr(s2, &b)));
+ mi_mul(&a, &b);
+ printf("%s\n", (s1 = mi_decstr(s1, &a)));
+
+ mi_setv(&b, 33, MI_POS);
+ printf("%s / %s = ", (s1 = mi_decstr(s1, &a)), (s2 = mi_decstr(s2, &b)));
+ mi_div(&a, &c, &b);
+ printf("%s R %s\n", (s1 = mi_decstr(s1, &a)), (s2 = mi_decstr(s2, &c)));
+
+ printf("DEC: %s\n", (s1 = mi_decstr(s1, &a)));
+ printf("HEX: %s\n", (s2 = mi_hexstr(s2, &a, 1)));
free(s1);
free(s2);
+
+ mi_free(&a);
+ mi_free(&b);
+ mi_free(&c);
}
diff --git a/src/day2/Makefile b/src/day2/Makefile
@@ -1,5 +1,5 @@
CFLAGS = -g -I ../../libs/include -L ../../libs/build
-LDLIBS = -laoc
+LDLIBS = -licc -laoc
all: lib main
@@ -9,4 +9,5 @@ lib:
clean:
rm main
-main: main.c ../../libs/build/libaoc.a
+main: main.c ../../libs/build/*
+ $(CC) -o $@ $< $(CFLAGS) $(LDLIBS)
diff --git a/src/day5/Makefile b/src/day5/Makefile
@@ -1,5 +1,5 @@
CFLAGS = -g -I ../../libs/include -L ../../libs/build
-LDLIBS = -laoc
+LDLIBS = -licc -laoc
all: lib main
@@ -9,4 +9,5 @@ clean:
lib:
make -C ../../libs
-main: main.c ../../libs/build/libaoc.a
+main: main.c ../../libs/build/*
+ $(CC) -o $@ $< $(CFLAGS) $(LDLIBS)
diff --git a/src/day7/Makefile b/src/day7/Makefile
@@ -1,5 +1,5 @@
CFLAGS = -g -I ../../libs/include -L ../../libs/build
-LDLIBS = -laoc
+LDLIBS = -licc -laoc
all: lib main
@@ -9,4 +9,5 @@ clean:
lib:
make -C ../../libs
-main: main.c ../../libs/build/libaoc.a
+main: main.c ../../libs/build/*
+ $(CC) -o $@ $< $(CFLAGS) $(LDLIBS)
diff --git a/src/day9/Makefile b/src/day9/Makefile
@@ -1,5 +1,5 @@
CFLAGS = -g -I ../../libs/include -L ../../libs/build
-LDLIBS = -laoc
+LDLIBS = -liccmp -laoc
all: lib main
@@ -9,4 +9,5 @@ clean:
lib:
make -C ../../libs
-main: main.c ../../libs/build/libaoc.a
+main: main.c ../../libs/build/*
+ $(CC) -o $@ $< $(CFLAGS) $(LDLIBS)
diff --git a/src/day9/main.c b/src/day9/main.c
@@ -1,4 +1,5 @@
#include "aoc.h"
+#include "iccmp.h"
#include <stdlib.h>
#include <stdio.h>
@@ -6,11 +7,57 @@
void
part1(void)
{
+ struct icc icc;
+ char *s;
+ ASSERT(icc_init(&icc) == OK);
+ ASSERT(icc_parse_inst(&icc, aoc.input, aoc.input_size) == OK);
+
+ s = NULL;
+ while (icc.status != ICC_HALT) {
+ icc_step_inst(&icc);
+ switch (icc.status) {
+ case ICC_INPUT:
+ mi_setv(&icc.in, 1, MI_POS);
+ break;
+ case ICC_OUTPUT:
+ debug("OUTPUT : %s\n", (s = mi_decstr(s, &icc.out)));
+ break;
+ }
+ }
+
+ s = mi_decstr(s, &icc.out);
+ aoc.answer = CHKP(aprintf("%s", s));
+
+ free(s);
+ icc_free(&icc);
}
void
part2(void)
{
+ struct icc icc;
+ char *s;
+
+ ASSERT(icc_init(&icc) == OK);
+ ASSERT(icc_parse_inst(&icc, aoc.input, aoc.input_size) == OK);
+
+ s = NULL;
+ while (icc.status != ICC_HALT) {
+ icc_step_inst(&icc);
+ switch (icc.status) {
+ case ICC_INPUT:
+ mi_setv(&icc.in, 2, MI_POS);
+ break;
+ case ICC_OUTPUT:
+ debug("OUTPUT : %s\n", (s = mi_decstr(s, &icc.out)));
+ break;
+ }
+ }
+
+ s = mi_decstr(s, &icc.out);
+ aoc.answer = CHKP(aprintf("%s", s));
+ free(s);
+ icc_free(&icc);
}
diff --git a/src/day9/part2 b/src/day9/part2
@@ -0,0 +1,16 @@
+--- Part Two ---
+
+[1m[37mYou now have a complete Intcode computer.[0m
+
+Finally, you can lock on to the Ceres distress signal! You just need to boost your sensors using the
+BOOST program.
+
+The program runs in sensor boost mode by providing the input instruction the value 2. Once run, it
+will boost the sensors automatically, but it might take a few seconds to complete the operation on
+slower hardware. In sensor boost mode, the program will output a single value: [1m[37mthe
+coordinates of the distress signal[0m.
+
+Run the BOOST program in sensor boost mode. [1m[37mWhat are the coordinates of the distress
+signal?[0m
+
+
