commit 939efe346da5dab0844f54d4dfad0d06a3582528
parent a3143f8fe845bef1e9e0fa76d97df038a2e34b77
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 17 Mar 2023 21:16:19 +0100
Fix submodules
Diffstat:
17 files changed, 2 insertions(+), 1267 deletions(-)
diff --git a/lib/libdvec b/lib/libdvec
@@ -0,0 +1 @@
+Subproject commit 765c583d2914a9d2ddc61bf50a3fa5e82917b154
diff --git a/lib/libdvec/.gitignore b/lib/libdvec/.gitignore
@@ -1,5 +0,0 @@
-compile_commands.json
-build
-.cache
-vgcore*
-test
diff --git a/lib/libdvec/LICENSE b/lib/libdvec/LICENSE
@@ -1,21 +0,0 @@
-MIT License
-
-Copyright (c) 2023 Louis Burda
-
-Permission is hereby granted, free of charge, to any person obtaining a copy
-of this software and associated documentation files (the "Software"), to deal
-in the Software without restriction, including without limitation the rights
-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the Software is
-furnished to do so, subject to the following conditions:
-
-The above copyright notice and this permission notice shall be included in all
-copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
-SOFTWARE.
diff --git a/lib/libdvec/Makefile b/lib/libdvec/Makefile
@@ -1,41 +0,0 @@
-PREFIX ?= /usr/local
-LIBDIR ?= /lib
-INCLDIR ?= /include
-
-CFLAGS = -I include -Wno-prototype -Wunused-function -Wunused-variable
-
-ifeq "$(DEBUG)" "1"
-CFLAGS += -g -DLIBDVEC_CHECK_ENABLE=1
-endif
-
-all: build/libdvec.so build/libdvec.a build/test
-
-clean:
- rm -rf build
-
-build:
- mkdir build
-
-build/libdvec.a: src/dvec.c include/dvec.h libdvec.api | build
- $(CC) -o build/tmp.o src/dvec.c $(CFLAGS) -r
- objcopy --keep-global-symbols=libdvec.api build/tmp.o build/fixed.o
- ar rcs $@ build/fixed.o
-
-build/libdvec.so: src/dvec.c include/dvec.h libdvec.lds | build
- $(CC) -o $@ src/dvec.c -fPIC $(CFLAGS) \
- -shared -Wl,-version-script libdvec.lds
-
-build/test: src/test.c build/libdvec.a
- $(CC) -o $@ $^ $(CFLAGS)
-
-install:
- install -m644 include/dvec.h -t "$(DESTDIR)$(PREFIX)$(INCLDIR)"
- install -m755 build/libdvec.so -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
- install -m755 build/libdvec.a -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
-
-uninstall:
- rm -f "$(DESTDIR)$(PREFIX)$(INCLDIR)/dvec.h"
- rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libdvec.so"
- rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libdvec.a"
-
-.PHONY: all clean install uninstall
diff --git a/lib/libdvec/include/dvec.h b/lib/libdvec/include/dvec.h
@@ -1,82 +0,0 @@
-#pragma once
-
-#include <stdbool.h>
-#include <stdlib.h>
-
-struct dvec {
- size_t dsize;
- size_t len, cap;
-
- void *data;
-};
-
-int dvec_init(struct dvec *dvec, size_t dsize, size_t cap);
-void dvec_deinit(struct dvec *dvec);
-
-int dvec_alloc(struct dvec **dvec, size_t dsize, size_t cap);
-void dvec_free(struct dvec *dvec);
-
-int dvec_copy(struct dvec *dst, struct dvec *src);
-void dvec_swap(struct dvec *dst, struct dvec *src);
-
-void dvec_clear(struct dvec *dvec);
-int dvec_reserve(struct dvec *dvec, size_t cap);
-int dvec_shrink(struct dvec *dvec);
-
-int dvec_add(struct dvec *dvec, size_t index, size_t count);
-void dvec_remove(struct dvec *dvec, size_t index, size_t count);
-void dvec_replace(struct dvec *dvec, size_t index, const void *data, size_t count);
-
-bool dvec_iter_fwd(struct dvec *dvec, void **p);
-bool dvec_iter_bwd(struct dvec *dvec, void **p);
-
-static inline void *
-dvec_at(struct dvec *dvec, size_t index)
-{
- return dvec->data + index * dvec->dsize;
-}
-
-static inline void *
-dvec_front(struct dvec *dvec)
-{
- return dvec->data;
-}
-
-static inline void *
-dvec_back(struct dvec *dvec)
-{
- return dvec->data + (dvec->len - 1) * dvec->dsize;
-}
-
-static inline bool
-dvec_empty(struct dvec *dvec)
-{
- return !dvec->len;
-}
-
-static inline void *
-dvec_add_slots(struct dvec *dvec, int *rc, size_t count)
-{
- *rc = dvec_add(dvec, dvec->len, count);
- if (*rc) return NULL;
-
- return dvec->data + (dvec->len - count) * dvec->dsize;
-}
-
-static inline void *
-dvec_add_slot(struct dvec *dvec, int *rc)
-{
- return dvec_add_slots(dvec, rc, 1);
-}
-
-static inline void
-dvec_rm_slots(struct dvec *dvec, void *slot, size_t count)
-{
- dvec_remove(dvec, (slot - dvec->data) / dvec->dsize, count);
-}
-
-static inline void
-dvec_rm_slot(struct dvec *dvec, void *slot)
-{
- dvec_rm_slots(dvec, slot, 1);
-}
diff --git a/lib/libdvec/libdvec.api b/lib/libdvec/libdvec.api
@@ -1,19 +0,0 @@
-dvec_init
-dvec_deinit
-
-dvec_alloc
-dvec_free
-
-dvec_copy
-dvec_swap
-
-dvec_clear
-dvec_reserve
-dvec_shrink
-
-dvec_add
-dvec_remove
-dvec_replace
-
-dvec_iter_fwd
-dvec_iter_bwd
diff --git a/lib/libdvec/libdvec.lds b/lib/libdvec/libdvec.lds
@@ -1,23 +0,0 @@
-LIBDVEC_1.1 {
- global:
- dvec_init;
- dvec_deinit;
-
- dvec_alloc;
- dvec_free;
-
- dvec_copy;
- dvec_swap;
-
- dvec_clear;
- dvec_reserve;
- dvec_shrink;
-
- dvec_add;
- dvec_remove;
- dvec_replace;
-
- dvec_iter_fwd;
- dvec_iter_bwd;
- local: *;
-};
diff --git a/lib/libdvec/src/dvec.c b/lib/libdvec/src/dvec.c
@@ -1,231 +0,0 @@
-#include "dvec.h"
-
-#include <errno.h>
-#include <string.h>
-#include <stdlib.h>
-
-#ifdef LIBDVEC_CHECK_ENABLE
-#include <stdio.h>
-#define LIBDVEC_CHECK(x) libdvec_assert((x), __FILE__, __LINE__, #x)
-#else
-#define LIBDVEC_CHECK(x)
-#endif
-
-#ifdef LIBDVEC_CHECK_ENABLE
-static inline void
-libdvec_assert(int cond, const char *file, int line, const char *condstr)
-{
- if (cond) return;
-
- fprintf(stderr, "libdvec: Assertion failed at %s:%i (%s)\n",
- file, line, condstr);
- abort();
-}
-#endif
-
-int
-dvec_init(struct dvec *dvec, size_t dsize, size_t cap)
-{
- LIBDVEC_CHECK(dvec != NULL && dsize > 0 && cap >= 0);
-
- dvec->dsize = dsize;
- dvec->cap = cap;
-
- dvec->len = 0;
- dvec->data = NULL;
- if (dvec->cap) {
- dvec->data = calloc(cap, dsize);
- if (!dvec->data) return -errno;
- }
-
- return 0;
-}
-
-void
-dvec_deinit(struct dvec *dvec)
-{
- LIBDVEC_CHECK(dvec != NULL);
-
- free(dvec->data);
-}
-
-int
-dvec_alloc(struct dvec **dvec, size_t dsize, size_t cap)
-{
- int rc;
-
- LIBDVEC_CHECK(dvec != NULL && dsize > 0 && cap > 0);
-
- *dvec = malloc(sizeof(struct dvec));
- if (!*dvec) return -errno;
-
- rc = dvec_init(*dvec, dsize, cap);
- if (rc) {
- free(dvec);
- return rc;
- }
-
- return 0;
-}
-
-void
-dvec_free(struct dvec *dvec)
-{
- LIBDVEC_CHECK(dvec != NULL);
-
- dvec_deinit(dvec);
- free(dvec);
-}
-
-int
-dvec_copy(struct dvec *dst, struct dvec *src)
-{
- int rc;
-
- dst->dsize = src->dsize;
- rc = dvec_reserve(dst, src->len);
- if (rc) return rc;
-
- dst->len = src->len;
- memcpy(dst->data, src->data, src->len * src->dsize);
-
- return 0;
-}
-
-void
-dvec_swap(struct dvec *dst, struct dvec *src)
-{
- struct dvec tmp;
-
- memcpy(&tmp, dst, sizeof(struct dvec));
- memcpy(dst, src, sizeof(struct dvec));
- memcpy(src, &tmp, sizeof(struct dvec));
-}
-
-void
-dvec_clear(struct dvec *dvec)
-{
- LIBDVEC_CHECK(dvec != NULL);
-
- dvec->len = 0;
-}
-
-int
-dvec_reserve(struct dvec *dvec, size_t len)
-{
- void *alloc;
-
- if (len <= dvec->cap) return 0;
-
- dvec->cap *= 2;
- if (len > dvec->cap) dvec->cap = len;
-
- alloc = realloc(dvec->data, dvec->cap * dvec->dsize);
- if (!alloc) return -errno;
- dvec->data = alloc;
-
- return 0;
-}
-
-int
-dvec_shrink(struct dvec *dvec)
-{
- void *alloc;
-
- LIBDVEC_CHECK(dvec != NULL);
-
- if (!dvec->len) {
- dvec->cap = 0;
- free(dvec->data);
- return 0;
- }
-
- dvec->cap = dvec->len;
-
- alloc = realloc(dvec->data, dvec->cap * dvec->dsize);
- if (!alloc) return -errno;
- dvec->data = alloc;
-
- return 0;
-}
-
-int
-dvec_add(struct dvec *dvec, size_t index, size_t len)
-{
- LIBDVEC_CHECK(dvec != NULL && index <= dvec->len);
-
- dvec_reserve(dvec, dvec->len + len);
-
- if (index < dvec->len) {
- memmove(dvec->data + (index + len) * dvec->dsize,
- dvec->data + index * dvec->dsize,
- (dvec->len - index) * dvec->dsize);
- }
-
- dvec->len += len;
-
- return 0;
-}
-
-void
-dvec_remove(struct dvec *dvec, size_t index, size_t count)
-{
- LIBDVEC_CHECK(dvec != NULL && count >= dvec->len
- && index + count <= dvec->len);
-
- if (index + count < dvec->len) {
- memmove(dvec->data + index * dvec->dsize,
- dvec->data + (index + count) * dvec->dsize,
- (dvec->len - (index + count)) * dvec->dsize);
- }
-
- dvec->len -= count;
-}
-
-void
-dvec_replace(struct dvec *dvec, size_t index, const void *data, size_t count)
-{
- LIBDVEC_CHECK(dvec != NULL && data != NULL && index + count < dvec->len);
-
- memcpy(dvec->data + index * dvec->dsize, data, count * dvec->dsize);
-}
-
-bool
-dvec_iter_fwd(struct dvec *dvec, void **p)
-{
- void **iter;
-
- LIBDVEC_CHECK(dvec != NULL && p != NULL);
-
- if (!dvec->len) return false;
-
- iter = p;
- if (*iter == NULL) {
- *iter = dvec->data;
- } else {
- *iter += dvec->dsize;
- }
-
- return *iter < dvec->data + dvec->dsize * dvec->len;
-}
-
-bool
-dvec_iter_bwd(struct dvec *dvec, void **p)
-{
- void **iter;
-
- LIBDVEC_CHECK(dvec != NULL && p != NULL);
-
- if (!dvec->len) return false;
-
- iter = p;
- if (*iter == NULL) {
- *iter = dvec->data + (dvec->len - 1) * dvec->dsize;
- } else if (*iter > dvec->data) {
- *iter -= dvec->dsize;
- } else {
- return false;
- }
-
- return true;
-}
diff --git a/lib/libdvec/src/test.c b/lib/libdvec/src/test.c
@@ -1,32 +0,0 @@
-#include "dvec.h"
-
-#include <err.h>
-#include <stdio.h>
-#include <string.h>
-#include <stdlib.h>
-
-#define LIBDVEC_ERR(rc) errx(1, "libdvec: %s", rc < 0 ? strerror(-rc) : "???")
-
-int
-main(int argc, const char **argv)
-{
- struct dvec dvec;
- int i, rc;
- int *val;
-
- rc = dvec_init(&dvec, sizeof(int), 10);
- if (rc) LIBDVEC_ERR(rc);
-
- for (i = 1; i < argc; i++) {
- val = dvec_add_slot(&dvec, &rc);
- if (rc) LIBDVEC_ERR(rc);
- *val = atoi(argv[i]);
- }
-
- for (i = 0; i < dvec.len; i++)
- printf("%i\n", *(int *)dvec_at(&dvec, i));
-
- printf("dvec len: %lu\n", dvec.len);
-
- dvec_deinit(&dvec);
-}
diff --git a/lib/libmaxint b/lib/libmaxint
@@ -0,0 +1 @@
+Subproject commit bf85311f8358c757d70b3e407d9ef7f25285ea5e
diff --git a/lib/libmaxint/.gitignore b/lib/libmaxint/.gitignore
@@ -1,3 +0,0 @@
-compile_commands.json
-build
-.cache
diff --git a/lib/libmaxint/Makefile b/lib/libmaxint/Makefile
@@ -1,37 +0,0 @@
-PREFIX ?= /usr/local
-LIBDIR ?= /lib
-
-CFLAGS = -Wunused-variable -Wunused-function -I include
-
-ifeq "$(DEBUG)" "1"
-CFLAGS += -g
-endif
-
-all: build/libmaxint.a build/libmaxint.so build/test
-
-clean:
- rm -rf build
-
-build:
- mkdir build
-
-build/libmaxint.a: src/maxint.c include/maxint.h libmaxint.api | build
- $(CC) -o build/tmp.o $< $(CFLAGS) -r
- objcopy --keep-global-symbols=libmaxint.api build/tmp.o build/fixed.o
- ar rcs $@ build/fixed.o
-
-build/libmaxint.so: src/maxint.c include/maxint.h libmaxint.lds | build
- $(CC) -o $@ $< -fPIC $(CFLAGS) -shared -Wl,-version-script libmaxint.lds
-
-build/test: src/test.c build/libmaxint.a | build
- $(CC) -o $@ $^ -g -I include
-
-install:
- install -m755 build/libmaxint.a -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
- install -m755 build/libmaxint.so -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
-
-uninstall:
- rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libmaxint.a"
- rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libmaxint.so"
-
-.PHONY: all clean install uninstall
diff --git a/lib/libmaxint/include/maxint.h b/lib/libmaxint/include/maxint.h
@@ -1,108 +0,0 @@
-#pragma once
-
-#include <stdint.h>
-#include <stdbool.h>
-#include <stdlib.h>
-
-#define MI_NEG 1
-#define MI_POS 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_INIT ((struct maxint) { \
- .data = NULL, \
- .size = 0, \
- .cap = 0, \
- .sign = MI_POS, \
-})
-
-/* unsigned underlying type */
-typedef uint64_t mi_ul;
-
-enum {
- MI_OK,
- MI_ERR_OOM,
- MI_ERR_INVAL,
-};
-
-struct maxint {
- mi_ul *data;
- size_t size, cap;
- int sign;
-};
-
-/* void mi_init(struct maxint *m); */
-void mi_deinit(struct maxint *m);
-
-int mi_set(struct maxint *m1, const struct maxint *m2);
-int mi_setv(struct maxint *m, mi_ul v, int sign);
-int mi_setstr(struct maxint *m, const char *str,
- const char **end, const char *alph);
-
-int mi_resize(struct maxint *m, size_t size);
-
-mi_ul mi_cast_ul(const struct maxint *m);
-
-bool mi_zero(const struct maxint *m);
-
-size_t mi_lastset(const struct maxint *m);
-
-ssize_t mi_str(const struct maxint *m, char *buf, size_t buflen,
- mi_ul base, const char *alph);
-ssize_t mi_hex(const struct maxint *m, char *buf, size_t buflen, bool capital);
-ssize_t mi_dec(const struct maxint *m, char *buf, size_t buflen);
-ssize_t mi_bin(const struct maxint *m, char *buf, size_t buflen);
-
-/* mi_add: o1 = i1 + i2
- * allowed: o1 == i1 */
-int mi_add(struct maxint *o1, const struct maxint *i1, const struct maxint *i2);
-
-/* mi_sub: o1 = i1 - i2
- * allowed: o1 == i1 */
-int mi_sub(struct maxint *o1, const struct maxint *i1, const struct maxint *i2);
-
-/* mi_shl: o1 = i1 << shift
- * allowed: o1 == i1 */
-int mi_shl(struct maxint *o1, const struct maxint *i1, size_t shift);
-
-/* mi_shr: o1 = i1 >> shift
- * allowed: o1 == i1 */
-int mi_shr(struct maxint *o1, const struct maxint *i1, size_t shift);
-
-/* mi_mul: o1 = i1 * i2
- * allowed: o1 == i1 */
-int mi_mul(struct maxint *o1, const struct maxint *i1, const struct maxint *i2);
-
-/* mi_div: o1 = i1 / i2, o2 = i1 % i2
- * allowed: o1 == i1 */
-int mi_div(struct maxint *o1, struct maxint *o2,
- const struct maxint *i1, const struct maxint *i2);
-
-/* mi_swap: o1 <=> o2 */
-void mi_swap(struct maxint *o1, struct maxint *o2);
-
-/* mi_gcm: o1 = gcm(i1, i2)
- * allowed: o1 == i1 */
-int mi_gcm(struct maxint *o1, const struct maxint *i1, const struct maxint *i2);
-
-/* mi_lcm: o1 = lcm(i1, i2)
- * allowed: o1 == i1 */
-int mi_lcm(struct maxint *o1, const struct maxint *i1, const struct maxint *i2);
-
-/* mi_cmp: (i1 < i2) => -1 | (i1 == i2) => 0 | (i1 < i2) => 1 */
-int mi_cmp(const struct maxint *i1, const struct maxint *i2);
-
-extern const struct maxint mi_one;
-
-static inline void
-mi_init(struct maxint *m)
-{
- m->data = NULL;
- m->size = 0;
- m->cap = 0;
- m->sign = MI_POS;
-}
diff --git a/lib/libmaxint/libmaxint.api b/lib/libmaxint/libmaxint.api
@@ -1,26 +0,0 @@
-mi_init
-mi_deinit
-mi_set
-mi_setv
-mi_setstr
-
-mi_resize
-mi_cast_ul
-mi_zero
-mi_lastset
-
-mi_str
-mi_hex
-mi_dec
-mi_bin
-
-mi_add
-mi_sub
-mi_shl
-mi_shr
-mi_mul
-mi_div
-mi_swap
-mi_gcm
-mi_lcm
-mi_cmp
diff --git a/lib/libmaxint/libmaxint.lds b/lib/libmaxint/libmaxint.lds
@@ -1,30 +0,0 @@
-LIBMAXINT_1.0 {
- global:
- mi_init;
- mi_deinit;
- mi_set;
- mi_setv;
- mi_setstr;
-
- mi_resize;
- mi_cast_ul;
- mi_zero;
- mi_lastset;
-
- mi_str;
- mi_hex;
- mi_dec;
- mi_bin;
-
- mi_add;
- mi_sub;
- mi_shl;
- mi_shr;
- mi_mul;
- mi_div;
- mi_swap;
- mi_gcm;
- mi_lcm;
- mi_cmp;
- local: *;
-};
diff --git a/lib/libmaxint/src/maxint.c b/lib/libmaxint/src/maxint.c
@@ -1,527 +0,0 @@
-#include "maxint.h"
-
-#include <sys/types.h>
-#include <err.h>
-#include <string.h>
-#include <stdbool.h>
-
-#define MAXINT_MAX_OVERCOMMIT 256
-
-#ifndef MAXINT_REALLOC
-#define MAXINT_REALLOC realloc
-#endif
-
-#ifndef MAXINT_FREE
-#define MAXINT_FREE free
-#endif
-
-#define MIN(a, b) ((b) > (a) ? (a) : (b))
-#define MAX(a, b) ((a) > (b) ? (a) : (b))
-#define DIVCEIL(a, b) ((a) / (b) + ((a) % (b) != 0))
-
-static mi_ul mi_one_v = 1;
-const struct maxint mi_one = {
- .data = &mi_one_v,
- .size = 1,
- .cap = 1,
- .sign = MI_POS
-};
-
-void
-mi_deinit(struct maxint *m)
-{
- MAXINT_FREE(m->data);
-}
-
-int
-mi_set(struct maxint *m1, const struct maxint *m2)
-{
- int rc;
-
- rc = mi_resize(m1, m2->size);
- if (rc) return rc;
-
- memcpy(m1->data, m2->data, m2->size * MI_ULBYTES);
- m1->sign = m2->sign;
-
- return 0;
-}
-
-int
-mi_setv(struct maxint *m, mi_ul v, int sign)
-{
- int rc;
-
- rc = mi_resize(m, 1);
- if (rc) return rc;
-
- memcpy(m->data, &v, MI_ULBYTES);
- m->sign = sign;
-
- return 0;
-}
-
-int
-mi_setstr(struct maxint *m, const char *str, const char **end, const char *alph)
-{
- const char *p, *cp;
- struct maxint tmp, base;
- int sign;
- int rc;
-
- sign = MI_POS;
- if (*str == '-') {
- sign = MI_NEG;
- str++;
- } else if (*str == '+') {
- str++;
- }
-
- mi_init(&base);
- rc = mi_setv(&base, strlen(alph), sign);
- if (rc) return rc;
-
- mi_init(&tmp);
- rc = mi_setv(m, 0, MI_POS);
- if (rc) return rc;
-
- for (p = str; *p && (cp = strchr(alph, *p)); p++) {
- rc = mi_mul(m, m, &base);
- if (rc) return rc;
-
- rc = mi_setv(&tmp, cp - alph, sign);
- if (rc) return rc;
-
- rc = mi_add(m, m, &tmp);
- if (rc) return rc;
- }
-
- *end = p;
-
- mi_deinit(&tmp);
- mi_deinit(&base);
-
- return 0;
-}
-
-int
-mi_resize(struct maxint *m, size_t size)
-{
- void *alloc;
-
- if (m->cap < size || m->cap > size + MAXINT_MAX_OVERCOMMIT) {
- if (size > m->cap) {
- m->cap = MAX(size, m->cap * 2);
- m->cap = MIN(m->cap, size + MAXINT_MAX_OVERCOMMIT - 1);
- } else {
- m->cap = size + 1;
- }
- alloc = MAXINT_REALLOC(m->data, m->cap * MI_ULBYTES);
- if (!alloc) return MI_ERR_OOM;
- m->data = alloc;
- }
-
- if (size > m->size)
- memset(&m->data[m->size], 0, (size - m->size) * MI_ULBYTES);
-
- m->size = size;
-
- return 0;
-}
-
-static int
-mi_add_internal(struct maxint *o1, const struct maxint *i1,
- const struct maxint *i2, int i2_sign)
-{
- mi_ul v;
- int carry;
- int i, msbs;
- int rc;
-
- if (o1 != i1) {
- rc = mi_set(o1, i1);
- if (rc) return rc;
- }
-
- msbs = i2->data[i2->size - 1] >> (MI_ULBITS - 1);
- msbs &= i1->data[i1->size - 1] >> (MI_ULBITS - 1);
- rc = mi_resize(o1, MAX(i1->size, i2->size) + (msbs != 0));
- if (rc) return rc;
-
- if (o1->sign != i2_sign) {
- for (carry = i = 0; i < o1->size; i++) {
- v = (i < i2->size ? i2->data[i] : 0);
- o1->data[i] -= v + carry;
- carry = o1->data[i] + v + carry < o1->data[i];
- }
-
- if (carry == 1) {
- if (o1->data[0] > 0) {
- o1->data[0]--;
- for (i = 0; i < o1->size; i++)
- o1->data[i] = ~o1->data[i];
- } else {
- for (i = 0; i < o1->size; i++)
- o1->data[i] = ~o1->data[i];
- o1->data[0]++;
- }
- o1->sign ^= 1;
- }
- } else {
- for (carry = i = 0; i < o1->size; i++) {
- v = (i < i2->size ? i2->data[i] : 0);
- o1->data[i] += v + carry;
- carry = o1->data[i] - v - carry > o1->data[i];
- }
- }
-
- return 0;
-}
-
-size_t
-mi_lastset(const struct maxint *m1)
-{
- size_t i;
-
- for (i = m1->size - 1; i >= 0; i--)
- if (m1->data[i] != 0) return i;
-
- return 0;
-}
-
-int
-mi_add(struct maxint *o1, const struct maxint *i1, const struct maxint *i2)
-{
- return mi_add_internal(o1, i1, i2, i2->sign);
-}
-
-int
-mi_sub(struct maxint *o1, const struct maxint *i1, const struct maxint *i2)
-{
- return mi_add_internal(o1, i1, i2, i2->sign ^ 1);
-}
-
-int
-mi_shl(struct maxint *o1, const struct maxint *i1, size_t shift)
-{
- int i, bit;
- int rc;
-
- if (!shift) return 0;
-
- rc = mi_resize(o1, mi_lastset(i1) + 1 + DIVCEIL(shift, MI_ULBITS));
- if (rc) return rc;
-
- for (i = o1->size * MI_ULBITS - 1; i >= 0; i--) {
- o1->data[i / MI_ULBITS] &= ~((mi_ul) 1 << (i % MI_ULBITS));
- if (i >= shift) {
- bit = MI_BITA(i1->data, MI_ULBITS, i - shift);
- o1->data[i / MI_ULBITS] |= (mi_ul) bit << (i % MI_ULBITS);
- }
- }
-
- return 0;
-}
-
-int
-mi_shr(struct maxint *o1, const struct maxint *i1, size_t shift)
-{
- int i, bit;
- int rc;
-
- if (!shift) return 0;
-
- if (o1 != i1) {
- rc = mi_resize(o1, mi_lastset(i1) + 1 - shift / MI_ULBITS);
- if (rc) return rc;
- }
-
- for (i = 0; i < i1->size * MI_ULBITS; i++) {
- i1->data[i / MI_ULBITS] &= ~((mi_ul) 1 << (i % MI_ULBITS));
- if (i + shift < i1->size * MI_ULBITS) {
- bit = MI_BITA(i1->data, MI_ULBITS, i + shift);
- i1->data[i / MI_ULBITS] |= (mi_ul) bit << (i % MI_ULBITS);
- }
- }
-
- return 0;
-}
-
-int
-mi_mul(struct maxint *osum, const struct maxint *i1, const struct maxint *i2)
-{
- struct maxint isum = MI_INIT;
- struct maxint *sum;
- ssize_t i;
- int rc = 0;
-
- sum = (osum == i1) ? &isum : osum;
-
- rc = mi_setv(sum, 0, MI_POS);
- if (rc) goto exit;
-
- for (i = i1->size * MI_ULBITS - 1; i >= 0; i--) {
- rc = mi_shl(sum, sum, 1);
- if (rc) goto exit;
-
- if (MI_BITA(i1->data, MI_ULBITS, i)) {
- if (i1->sign == MI_POS) {
- rc = mi_add(sum, sum, i2);
- if (rc) goto exit;
- } else {
- rc = mi_sub(sum, sum, i2);
- if (rc) goto exit;
- }
- }
- }
-
- if (osum == i1)
- mi_swap(sum, osum);
-
-exit:
- if (sum == &isum)
- mi_deinit(sum);
-
- return rc;
-}
-
-int
-mi_div(struct maxint *oquot, struct maxint *orem,
- const struct maxint *num, const struct maxint *div)
-{
- struct maxint iquot = MI_INIT;
- struct maxint irem = MI_INIT;
- struct maxint *quot, *rem;
- int i, k;
- int rc;
-
- quot = (oquot == NULL || oquot == num || oquot == div) ? &iquot : oquot;
- rem = (orem == NULL || orem == num || orem == div) ? &irem : orem;
-
- rc = mi_setv(quot, 0, MI_POS);
- if (rc) goto exit;
-
- rc = mi_setv(rem, 0, MI_POS);
- if (rc) goto exit;
-
- for (i = 0; i < num->size * MI_ULBITS; i++) {
- k = num->size * MI_ULBITS - 1 - i;
-
- /* rem = rem * 2 + [bit set] */
- rc = mi_shl(rem, rem, 1);
- if (rc) goto exit;
- if (MI_BITA(num->data, MI_ULBITS, k)) {
- rc = mi_add(rem, rem, &mi_one);
- if (rc) goto exit;
- }
-
- /* quot = 2 * quot + [rem >= div] */
- rc = mi_shl(quot, quot, 1);
- if (rc) goto exit;
- if (mi_cmp(rem, div) >= 0) {
- rc = mi_add(quot, quot, &mi_one);
- if (rc) goto exit;
- rc = mi_sub(rem, rem, div);
- if (rc) goto exit;
- }
- }
-
- if (quot->sign != div->sign) {
- rc = mi_sub(rem, rem, div);
- if (rc) goto exit;
- }
-
- rem->sign = div->sign;
- quot->sign = num->sign ^ div->sign;
-
- if (quot == &iquot && oquot)
- mi_swap(&iquot, oquot);
-
- if (rem == &irem && orem)
- mi_swap(&irem, orem);
-
-exit:
- mi_deinit(&iquot);
- mi_deinit(&irem);
-
- return rc;
-}
-
-void
-mi_swap(struct maxint *m1, struct maxint *m2)
-{
- struct maxint tmp;
-
- memcpy(&tmp, m1, sizeof(struct maxint));
- memcpy(m1, m2, sizeof(struct maxint));
- memcpy(m2, &tmp, sizeof(struct maxint));
-}
-
-int
-mi_gcd(struct maxint *o1, const struct maxint *i1, const struct maxint *i2)
-{
- struct maxint rem = MI_INIT;
- struct maxint tmp = MI_INIT;
- int rc = 0;
-
- rc = mi_setv(&rem, 0, MI_POS);
- if (rc) goto exit;
-
- rc = mi_set(&tmp, i2);
- if (rc) goto exit;
-
- if (o1 != i1) {
- rc = mi_set(o1, i1);
- if (rc) goto exit;
- }
-
- do {
- rc = mi_div(o1, &rem, o1, &tmp);
- if (rc) goto exit;
- mi_swap(o1, &tmp);
- mi_swap(&tmp, &rem);
- } while (!mi_zero(&tmp));
-
-exit:
- mi_deinit(&rem);
- mi_deinit(&tmp);
-
- return rc;
-}
-
-int
-mi_lcm(struct maxint *o1, const struct maxint *i1, const struct maxint *i2)
-{
- struct maxint lcm = MI_INIT;
- int rc = 0;
-
- rc = mi_set(&lcm, i1);
- if (rc) goto exit;
-
- rc = mi_gcd(&lcm, i1, i2);
- if (rc) goto exit;
-
- rc = mi_mul(o1, i1, i2);
- if (rc) goto exit;
-
- rc = mi_div(o1, NULL, o1, &lcm);
- if (rc) goto exit;
-
-exit:
- mi_deinit(&lcm);
-
- return rc;
-}
-
-int
-mi_cmp(const struct maxint *m1, const struct maxint *m2)
-{
- mi_ul v1, v2;
- size_t 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;
- }
-
- return 0;
-}
-
-mi_ul
-mi_cast_ul(const struct maxint *m1)
-{
- return m1->data[0];
-}
-
-bool
-mi_zero(const struct maxint *m1)
-{
- size_t i;
-
- for (i = 0; i < m1->size; i++) {
- if (m1->data[i] != 0)
- return false;
- }
-
- return true;
-}
-
-ssize_t
-mi_str(const struct maxint *m, char *buf, size_t buflen,
- mi_ul base_ul, const char *alph)
-{
- struct maxint num = MI_INIT;
- struct maxint rem = MI_INIT;
- struct maxint base = MI_INIT;
- size_t i, len;
- ssize_t ret = -1;
- mi_ul rem_ul;
- char tmp;
- int rc;
-
- if (!base_ul) return -1;
- if (!buflen) return -1;
-
- rc = mi_set(&num, m);
- if (rc) goto exit;
- num.sign = MI_POS;
-
- rc = mi_setv(&rem, 0, MI_POS);
- if (rc) goto exit;
-
- rc = mi_setv(&base, base_ul, MI_POS);
- if (rc) goto exit;
-
- len = 0;
- do {
- if (mi_div(&num, &rem, &num, &base))
- goto exit;
- rem_ul = mi_cast_ul(&rem);
-
- buf[len++] = alph[rem_ul];
- if (len == buflen)
- goto exit;
- } while (!mi_zero(&num));
-
- if (m->sign == MI_NEG) {
- buf[len++] = '-';
- if (len == buflen)
- goto exit;
- }
-
- for (i = 0; i < len / 2; i++) {
- tmp = buf[i];
- buf[i] = buf[len - 1 - i];
- buf[len - 1 - i] = tmp;
- }
-
- buf[len++] = '\0';
- ret = len;
-
-exit:
- mi_deinit(&rem);
- mi_deinit(&num);
- mi_deinit(&base);
-
- return ret;
-}
-
-ssize_t
-mi_hex(const struct maxint *m, char *buf, size_t buflen, bool capital)
-{
- return mi_str(m, buf, buflen, 16,
- capital ? "0123456789ABCDEF" : "0123456789abcdef");
-}
-
-ssize_t
-mi_dec(const struct maxint *m, char *buf, size_t buflen)
-{
- return mi_str(m, buf, buflen, 10, "0123456789");
-}
-
-ssize_t
-mi_bin(const struct maxint *m, char *buf, size_t buflen)
-{
- return mi_str(m, buf, buflen, 2, "01");
-}
diff --git a/lib/libmaxint/src/test.c b/lib/libmaxint/src/test.c
@@ -1,82 +0,0 @@
-#include "maxint.h"
-
-#include <stdio.h>
-
-int
-main(int argc, const char **argv)
-{
- char sa[256], sb[256], sc[256];
- struct maxint a = MI_INIT;
- struct maxint b = MI_INIT;
- struct maxint c = MI_INIT;
- ssize_t len = 0;
- int rc = 0;
-
- rc |= mi_setv(&a, 1014, MI_POS);
- rc |= mi_setv(&b, 9, MI_NEG);
- rc |= mi_add(&c, &a, &b);
- rc |= mi_dec(&a, sa, sizeof(sa)) < 0;
- rc |= mi_dec(&b, sb, sizeof(sb)) < 0;
- rc |= mi_dec(&c, sc, sizeof(sc)) < 0;
- if (rc) goto exit;
- printf("ADD: %s + %s = %s\n", sa, sb, sc);
-
- rc |= mi_setv(&a, 10000000000000000000ULL, MI_POS);
- rc |= mi_setv(&b, 10000000000000000000ULL, MI_POS);
- rc |= mi_add(&c, &a, &b);
- rc |= mi_dec(&a, sa, sizeof(sa)) < 0;
- rc |= mi_dec(&b, sb, sizeof(sb)) < 0;
- rc |= mi_dec(&c, sc, sizeof(sc)) < 0;
- if (rc) goto exit;
- printf("ADD: %s + %s = %s\n", sa, sb, sc);
-
- rc |= mi_setv(&a, 1, MI_NEG);
- rc |= mi_setv(&b, 1, MI_POS);
- rc |= mi_mul(&c, &a, &b);
- rc |= mi_bin(&a, sa, sizeof(sa)) < 0;
- rc |= mi_bin(&b, sb, sizeof(sb)) < 0;
- rc |= mi_bin(&c, sc, sizeof(sc)) < 0;
- if (rc) goto exit;
- printf("MUL: %s * %s = %s\n", sa, sb, sc);
-
- rc |= mi_setv(&a, 10000000000000000000ULL, MI_POS);
- rc |= mi_bin(&a, sa, sizeof(sa)) < 0;
- rc |= mi_shl(&b, &a, 2);
- rc |= mi_bin(&b, sb, sizeof(sb)) < 0;
- if (rc) goto exit;
- printf("SHL: %s << 2 = %s\n", sa, sb);
-
- rc |= mi_setv(&a, 10000000000000000000ULL, MI_POS);
- rc |= mi_setv(&b, 10000000000000000000ULL, MI_POS);
- rc |= mi_mul(&c, &a, &b);
- if (rc) goto exit;
- printf("%lu * %lu != %lu\n", a.data[0], b.data[0], a.data[0] * b.data[0]);
- rc |= mi_dec(&a, sa, sizeof(sa)) < 0;
- rc |= mi_dec(&b, sb, sizeof(sb)) < 0;
- rc |= mi_dec(&c, sc, sizeof(sc)) < 0;
- if (rc) goto exit;
- printf("%s * %s = %s\n", sa, sb, sc);
-
- rc |= mi_setv(&b, 33, MI_POS);
- if (rc) goto exit;
- rc |= mi_dec(&a, sa, sizeof(sa)) < 0;
- rc |= mi_dec(&b, sb, sizeof(sb)) < 0;
- printf("%s / %s = ", sa, sb);
- rc |= mi_div(&a, &c, &a, &b);
- rc |= mi_dec(&a, sa, sizeof(sa)) < 0;
- rc |= mi_dec(&c, sc, sizeof(sc)) < 0;
- if (rc) goto exit;
- printf("%s R %s\n", sa, sc);
-
- mi_dec(&a, sa, sizeof(sa));
- printf("DEC: %s\n", sa);
- mi_hex(&a, sa, sizeof(sa), true);
- printf("HEX: %s\n", sa);
-
-exit:
- mi_deinit(&a);
- mi_deinit(&b);
- mi_deinit(&c);
-
- return rc;
-}
