commit a56db3ca197612211365480617a15d3c14b5a680
parent 915a11e0c7b0a0fd23a1f6f60d6282442aa25a8c
Author: Louis Burda <quent.burda@gmail.com>
Date: Sat, 5 Jun 2021 20:35:32 +0200
Add own multiple precision integer library
Diffstat:
11 files changed, 399 insertions(+), 17 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -2,3 +2,4 @@ compile_commands.json
main
.cache
build
+vgcore*
diff --git a/libs/Makefile b/libs/Makefile
@@ -1,4 +1,4 @@
-CFLAGS = -I include -g
+CFLAGS = -I include -g -L build
LDLIBS =
all: build/libaoc.a
@@ -14,3 +14,16 @@ build/%.o: src/%.c include/%.h | build
build/libaoc.a: build/util.o build/wrapper.o
ar rcs $@ $^
+
+build/test_%: tests/%.c
+ $(CC) -o $@ $< $(CFLAGS) $(LDLIBS)
+
+build/test_maxint: tests/maxint.c build/maxint.o
+ $(CC) -o $@ $^ $(CFLAGS) $(LDLIBS) -laoc
+
+build/test_%.log: build/test_%
+ @echo "--- Running test: $< ---"
+ @valgrind --track-origins=yes --leak-check=full $< 2>&1 | tee $@
+
+tests: build/test_maxint.log
+
diff --git a/libs/include/aoc.h b/libs/include/aoc.h
@@ -0,0 +1,5 @@
+#include "util.h"
+#include "partinfo.h"
+
+void part1(struct partinfo *p);
+void part2(struct partinfo *p);
diff --git a/libs/include/maxint.h b/libs/include/maxint.h
@@ -0,0 +1,61 @@
+#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_DIVCEIL(a,b) ((a) / (b) + ((a) % (b) != 0))
+
+#define MI_BIT(a,n) ((mi_ul) ((a) >> (n)) & 1)
+#define MI_BITA(a,m,n) ((mi_ul) ((a)[(n) / (m)] >> ((n) % (m))) & 1)
+
+#define MI_ULBYTES (sizeof(mi_ul))
+#define MI_ULBITS (8 * sizeof(mi_ul))
+
+#define MI_NEG 1
+#define MI_POS 0
+
+/* unsigned underlying type */
+typedef uint64_t mi_ul;
+
+struct maxint {
+ mi_ul* data;
+ mi_ul imm;
+ size_t size, last;
+ uint8_t 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_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_resize(struct maxint *m1, size_t size);
+
+const struct maxint* mi_imm(struct maxint *dst, mi_ul v, int sign);
+
+mi_ul mi_cast_ul(const struct maxint *m1);
+
+void mi_parse(struct maxint *m1, const char *vstr);
+
+void mi_free(struct maxint *m1);
+
+int mi_zero(const struct maxint *m1);
+
+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_tmp;
diff --git a/libs/include/util.h b/libs/include/util.h
@@ -26,7 +26,7 @@ const char* ntoken(const char *start, const char *end, size_t *len, const char *
int min(int a, int b);
int max(int a, int b);
-void* assertp(void *alloc);
+void* chkp(void *alloc);
void* memdup(void *data, size_t size);
int readall(int fd, void **data, size_t *read);
diff --git a/libs/include/wrapper.h b/libs/include/wrapper.h
@@ -1,6 +0,0 @@
-#include "util.h"
-#include "partinfo.h"
-
-void part1(struct partinfo *p);
-void part2(struct partinfo *p);
-
diff --git a/libs/src/maxint.c b/libs/src/maxint.c
@@ -0,0 +1,287 @@
+#include "maxint.h"
+
+struct maxint mi_tmp;
+
+void
+mi_add_internal(struct maxint *m1, const struct maxint *m2, int m2_sign)
+{
+ int carry, swapped;
+ size_t i;
+ mi_ul v;
+
+ if (m2->size >= m1->size)
+ mi_resize(m1, m2->size + 1);
+
+ if (m1->sign != m2_sign) {
+ for (carry = i = 0; i < m1->size; i++) {
+ v = (i < m2->size ? m2->data[i] : 0);
+ m1->data[i] -= v + carry;
+ carry = m1->data[i] + v + carry < m1->data[i];
+ }
+
+ if (carry == 1) {
+ if (m1->data[0] > 0) {
+ m1->data[0]--;
+ for (i = 0; i < m1->size; i++)
+ m1->data[i] = ~m1->data[i];
+ } else {
+ for (i = 0; i < m1->size; i++)
+ m1->data[i] = ~m1->data[i];
+ m1->data[0]++;
+ }
+ m1->sign ^= 1;
+ }
+ } else {
+ for (carry = i = 0; i < m1->size; i++) {
+ v = (i < m2->size ? m2->data[i] : 0);
+ m1->data[i] += v + carry;
+ carry = m1->data[i] - v - carry > m1->data[i];
+ }
+ }
+}
+
+void
+mi_add(struct maxint *m1, const struct maxint *m2)
+{
+ mi_add_internal(m1, m2, m2->sign);
+}
+
+void
+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)
+{
+ size_t i;
+ mi_ul v1, v2;
+
+ 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;
+ }
+
+ return 0;
+}
+
+int
+mi_lastset(struct maxint *m1)
+{
+ int64_t i;
+
+ for (i = m1->size - 1; i >= 0; i--)
+ if (m1->data[i] != 0) return i;
+ return 0;
+}
+
+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");
+ }
+}
+
+void
+mi_mul(struct maxint *m1, const struct maxint *m2)
+{
+ struct maxint sum = { 0 }, tmp = { 0 };
+ int64_t i;
+
+ mi_setv(&sum, 0, MI_POS);
+ for (i = m1->size * MI_ULBITS - 1; i >= 0; i--) {
+ if (MI_BITA(m1->data, MI_ULBITS, i))
+ mi_add(&sum, m2);
+ mi_shl(&sum, 1);
+ }
+
+ mi_swap(&sum, m1);
+ mi_free(&sum);
+}
+
+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;
+
+ 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));
+
+ // 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_sub(rem, div);
+ }
+ //printf("%li %li %li\n", k, rem->data[0], mul->data[0]);
+ }
+
+ if (orig.sign != div->sign)
+ mi_sub(rem, div);
+ rem->sign = div->sign;
+ mul->sign = orig.sign ^ div->sign;
+
+ mi_free(&orig);
+ if (rem == &irem)
+ mi_free(&irem);
+}
+
+void
+mi_set(struct maxint *m1, const 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;
+}
+
+void
+mi_setv(struct maxint *m1, mi_ul v, int sign)
+{
+ if (m1->size < 1) {
+ m1->data = chkp(malloc(MI_ULBYTES));
+ m1->size = 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);
+}
+
+void
+mi_resize(struct maxint *m1, size_t size)
+{
+ 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;
+}
+
+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;
+}
+
+mi_ul
+mi_cast_ul(const struct maxint *m1)
+{
+ 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;
+
+ 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)
+{
+ struct maxint num = { 0 }, rem = { 0 }, tmp = { 0 };
+ size_t i, k, rest, slen, scap;
+ char *strbuf;
+ int carry;
+
+ if (base <= 1) return chkp(strdup(""));
+
+ mi_set(&num, m1);
+ mi_setv(&rem, 0, MI_POS);
+
+ scap = 16;
+ slen = 0;
+ strbuf = malloc(scap);
+
+ do {
+ mi_div(&num, &rem, mi_imm(&tmp, base, MI_POS));
+ rest = mi_cast_ul(&rem);
+
+ strbuf[slen] = alph[rest];
+ slen++;
+ if (slen >= scap) {
+ scap *= 2;
+ strbuf = realloc(strbuf, scap);
+ }
+ } while (!mi_zero(&num));
+
+ for (i = 0; i < slen / 2; i++)
+ MI_SWAP(strbuf[i], strbuf[slen - 1 - i]);
+ strbuf[slen] = '\0';
+
+ mi_free(&rem);
+ mi_free(&num);
+
+ return strbuf;
+}
+
+char*
+mi_hexstr(const struct maxint *m1, int cap)
+{
+ return mi_convstr(m1, 16, cap ? "0123456789ABCDEF" : "0123456789abcdef");
+}
+
+char*
+mi_decstr(const struct maxint *m1)
+{
+ return mi_convstr(m1, 10, "0123456789");
+}
+
diff --git a/libs/src/util.c b/libs/src/util.c
@@ -50,7 +50,7 @@ max(int a, int b)
}
void*
-assertp(void *alloc)
+chkp(void *alloc)
{
if (!alloc) die("Out of Memory\n");
return alloc;
@@ -61,7 +61,7 @@ memdup(void *data, size_t size)
{
void *new;
- new = assertp(malloc(size));
+ new = chkp(malloc(size));
memcpy(new, data, size);
return new;
}
@@ -71,14 +71,14 @@ readall(int fileno, void **data, size_t *totalread)
{
size_t allocsize = 10, want = allocsize, got;
- *data = assertp(malloc(allocsize));
+ *data = chkp(malloc(allocsize));
*totalread = 0;
while ((got = read(fileno, *data + *totalread, want)) > 0) {
if (got == want) {
allocsize *= 2;
*totalread += got;
- *data = assertp(realloc(*data, allocsize));
+ *data = chkp(realloc(*data, allocsize));
} else {
*totalread += got;
}
diff --git a/libs/tests/maxint.c b/libs/tests/maxint.c
@@ -0,0 +1,23 @@
+#include "maxint.h"
+
+int
+main()
+{
+ struct maxint a = { 0 }, b = { 0 };
+ 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]);
+
+ printf("DEC: %s\n", (s1 = mi_convstr(&a, 10, "0123456789")));
+ printf("HEX: %s\n", (s2 = mi_convstr(&a, 16, "0123456789ABCDEF")));
+
+ mi_free(&a);
+ mi_free(&b);
+
+ free(s1);
+ free(s2);
+}
diff --git a/src/day1/main.c b/src/day1/main.c
@@ -2,8 +2,7 @@
#include <stdio.h>
#include <string.h>
-#include "partinfo.h"
-#include "util.h"
+#include "aoc.h"
void
part1(struct partinfo *p)
diff --git a/src/day2/main.c b/src/day2/main.c
@@ -1,8 +1,7 @@
#include <stdlib.h>
#include <stdio.h>
-#include "partinfo.h"
-#include "util.h"
+#include "aoc.h"
#include "icc.h"
void
@@ -14,7 +13,7 @@ part1(struct partinfo *p)
assert(OK, icc_parse_inst(&config, p->input, p->input_size));
icc_set_inst(&config, 1, 12);
- icc_set_inst(&config, 2, 02);
+ icc_set_inst(&config, 2, 2);
while (config.status != ICC_HALT) {
icc_step_inst(&config);
