141 lines
3.6 KiB
C
141 lines
3.6 KiB
C
// assert
|
|
#include <assert.h>
|
|
// uint32_t, int32_t, uint64_t, SIZE_MAX
|
|
#include <stdint.h>
|
|
// abort, malloc, realloc
|
|
#include <stdlib.h>
|
|
// memset, memcpy
|
|
#include <string.h>
|
|
|
|
// struct meri_object, meri_release
|
|
#include "meri_object.h"
|
|
// struct meri_bigint
|
|
#include "meri_bigint.h"
|
|
|
|
// Return: unique
|
|
static struct meri_bigint *meri_new_bigint(unsigned int nlimbs) {
|
|
// Check for integer overflow
|
|
if ((SIZE_MAX - sizeof(struct meri_bigint)) / sizeof(uint32_t) < nlimbs) {
|
|
abort(); // TODO: Nicer error messages
|
|
}
|
|
size_t size = sizeof(struct meri_bigint) + nlimbs * sizeof(uint32_t);
|
|
|
|
struct meri_bigint *allocation = malloc(size);
|
|
// We assume memory allocation can never fail
|
|
// If it does, we die
|
|
if (!allocation) {
|
|
abort(); // TODO: Nicer error messages
|
|
}
|
|
|
|
allocation->header.type = MERI_BIGINT;
|
|
allocation->header.refcount = 1;
|
|
allocation->nlimbs = nlimbs;
|
|
memset(allocation->limbs, 0, nlimbs * sizeof(uint32_t));
|
|
|
|
return allocation;
|
|
}
|
|
|
|
// Return: unique
|
|
struct meri_bigint *meri_bigint_from_u32(uint32_t value) {
|
|
struct meri_bigint *bigint = meri_new_bigint(1);
|
|
bigint->limbs[0] = value;
|
|
return bigint;
|
|
}
|
|
|
|
// p: borrowed unique
|
|
static void meri_resize_bigint(struct meri_bigint **p, unsigned int nlimbs) {
|
|
assert(p[0]->header.refcount == 1);
|
|
unsigned int old_nlimbs = p[0]->nlimbs;
|
|
|
|
// Check for integer overflow
|
|
if ((SIZE_MAX - sizeof(struct meri_bigint)) / sizeof(uint32_t) < nlimbs) {
|
|
abort(); // TODO: Nicer error messages
|
|
}
|
|
size_t size = sizeof(struct meri_bigint) + nlimbs * sizeof(uint32_t);
|
|
|
|
struct meri_bigint *allocation = realloc(*p, size);
|
|
// We assume memory allocation can never fail
|
|
// If it does, we die
|
|
if (!allocation) {
|
|
abort(); // TODO: Nicer error messages
|
|
}
|
|
*p = allocation;
|
|
|
|
p[0]->nlimbs = nlimbs;
|
|
if (old_nlimbs < nlimbs) {
|
|
memset(&p[0]->limbs[old_nlimbs], 0, (nlimbs - old_nlimbs) * sizeof(uint32_t));
|
|
}
|
|
}
|
|
|
|
// bigint: borrowed owned → borrowed unique
|
|
static void meri_unique_bigint(struct meri_bigint **p) {
|
|
if (p[0]->header.refcount == 1) {
|
|
return;
|
|
}
|
|
|
|
struct meri_bigint *shared = *p;
|
|
struct meri_bigint *unique = meri_new_bigint(p[0]->nlimbs);
|
|
memcpy(unique->limbs, shared->limbs, p[0]->nlimbs * sizeof(uint32_t));
|
|
meri_release(&shared->header);
|
|
*p = unique;
|
|
}
|
|
|
|
// p: borrowed unique
|
|
// addend: shared
|
|
static void meri_bigint_add_inplace(
|
|
struct meri_bigint **p, struct meri_bigint const *addend
|
|
) {
|
|
// TODO: shrink the resulting value if reasonable
|
|
assert(p[0]->header.refcount == 1);
|
|
assert(addend->nlimbs <= p[0]->nlimbs);
|
|
|
|
uint64_t acc = 0;
|
|
uint32_t p_extended = 0, addend_extended = 0;
|
|
for (unsigned int i = 0; i < p[0]->nlimbs; i++) {
|
|
acc >>= 32;
|
|
acc += p[0]->limbs[i];
|
|
p_extended = (int32_t)p[0]->limbs[i] >> 31;
|
|
if (i < addend->nlimbs) {
|
|
acc += addend->limbs[i];
|
|
addend_extended = (int32_t)addend->limbs[i] >> 31;
|
|
} else {
|
|
acc += addend_extended;
|
|
}
|
|
p[0]->limbs[i] = (uint32_t)acc;
|
|
}
|
|
|
|
uint32_t last_limb = (uint32_t)acc;
|
|
uint32_t last_limb_sign_extension = (int32_t)last_limb >> 31;
|
|
|
|
acc >>= 32;
|
|
acc += p_extended;
|
|
acc += addend_extended;
|
|
|
|
uint32_t extra_limb = (uint32_t)acc;
|
|
|
|
if (last_limb_sign_extension != extra_limb) {
|
|
meri_resize_bigint(p, p[0]->nlimbs + 1);
|
|
p[0]->limbs[p[0]->nlimbs - 1] = extra_limb;
|
|
}
|
|
}
|
|
|
|
// a, b: owned
|
|
// Return: owned
|
|
struct meri_bigint *meri_bigint_add(
|
|
struct meri_bigint *a, struct meri_bigint *b
|
|
) {
|
|
if (
|
|
b->nlimbs < a->nlimbs
|
|
|| b->nlimbs == a->nlimbs && a->header.refcount == 1
|
|
) {
|
|
meri_unique_bigint(&a);
|
|
meri_bigint_add_inplace(&a, b);
|
|
meri_release(&b->header);
|
|
return a;
|
|
} else {
|
|
meri_unique_bigint(&b);
|
|
meri_bigint_add_inplace(&b, a);
|
|
meri_release(&a->header);
|
|
return b;
|
|
}
|
|
}
|