Add minimal big integer implementation

This is needed for floating point decimal conversion.

5 files changed, 1674 insertions, 0 deletions

diff --git a/src/bigint.c b/src/bigint.c
new file mode 100644
index 00000000..f8cd7081
--- /dev/null
+++ b/src/bigint.c
@@ -0,0 +1,623 @@
+/*
+  Copyright 2019-2020 David Robillard <http://drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#include "bigint.h"
+
+#include "int_math.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef uint64_t Hugit;
+
+static const uint32_t bigit_mask = ~(uint32_t)0;
+static const uint64_t carry_mask = (uint64_t)~(uint32_t)0 << 32;
+
+typedef struct
+{
+	unsigned bigits;
+	unsigned bits;
+} Offset;
+
+static inline Offset
+make_offset(const unsigned i)
+{
+	const unsigned bigits = i / BIGINT_BIGIT_BITS;
+	const unsigned bits   = i - bigits * BIGINT_BIGIT_BITS;
+
+	const Offset offset = {bigits, bits};
+	return offset;
+}
+
+#ifndef NDEBUG
+static inline bool
+serd_bigint_is_clamped(const SerdBigint* num)
+{
+	return num->n_bigits == 0 || num->bigits[num->n_bigits - 1];
+}
+#endif
+
+size_t
+serd_bigint_print_hex(FILE* const stream, const SerdBigint* const num)
+{
+	assert(serd_bigint_is_clamped(num));
+	if (num->n_bigits == 0) {
+		fprintf(stream, "0");
+		return 1;
+	}
+
+	int len = fprintf(stream, "%X", num->bigits[num->n_bigits - 1]);
+	for (unsigned i = 1; i < num->n_bigits; ++i) {
+		len += fprintf(stream, "%08X", num->bigits[num->n_bigits - 1 - i]);
+	}
+
+	return (size_t)len;
+}
+
+size_t
+serd_bigint_to_hex_string(const SerdBigint* const num,
+                          char* const             buf,
+                          const size_t            len)
+{
+	if (len < 9) {
+		return 0;
+	} else if (num->n_bigits == 0) {
+		buf[0] = '0';
+		buf[1] = '\0';
+		return 1;
+	}
+
+	size_t n = (size_t)snprintf(buf, len, "%X", num->bigits[num->n_bigits - 1]);
+	for (unsigned i = 1; n + 8 <= len && i < num->n_bigits; ++i) {
+		n += (size_t)snprintf(buf + n,
+		                      len - n,
+		                      "%08X",
+		                      num->bigits[num->n_bigits - 1 - i]);
+	}
+
+	return n;
+}
+
+void
+serd_bigint_shift_left(SerdBigint* num, const unsigned amount)
+{
+	assert(serd_bigint_is_clamped(num));
+	if (amount == 0 || num->n_bigits == 0) {
+		return;
+	}
+
+	const Offset offset = make_offset(amount);
+
+	assert(num->n_bigits + offset.bigits < BIGINT_MAX_BIGITS);
+	num->n_bigits += offset.bigits + (bool)offset.bits;
+
+	if (offset.bits == 0) { // Simple bigit-aligned shift
+		for (unsigned i = num->n_bigits - 1; i >= offset.bigits; --i) {
+			num->bigits[i] = num->bigits[i - offset.bigits];
+		}
+	} else { // Bigit + sub-bigit bit offset shift
+		const unsigned right_shift = BIGINT_BIGIT_BITS - offset.bits;
+		for (unsigned i = num->n_bigits - offset.bigits - 1; i > 0; --i) {
+			num->bigits[i + offset.bigits] =
+			        (num->bigits[i] << offset.bits) |
+			        (num->bigits[i - 1] >> right_shift);
+		}
+
+		num->bigits[offset.bigits] = num->bigits[0] << offset.bits;
+	}
+
+	// Zero LSBs
+	for (unsigned i = 0; i < offset.bigits; ++i) {
+		num->bigits[i] = 0;
+	}
+
+	serd_bigint_clamp(num);
+	assert(serd_bigint_is_clamped(num));
+}
+
+void
+serd_bigint_zero(SerdBigint* num)
+{
+	static const SerdBigint zero = {{0}, 0};
+
+	*num = zero;
+}
+
+void
+serd_bigint_set(SerdBigint* num, const SerdBigint* value)
+{
+	*num = *value;
+}
+
+void
+serd_bigint_set_u32(SerdBigint* num, const uint32_t value)
+{
+	serd_bigint_zero(num);
+
+	num->bigits[0] = value;
+	num->n_bigits  = (bool)value;
+}
+
+void
+serd_bigint_clamp(SerdBigint* num)
+{
+	while (num->n_bigits > 0 && num->bigits[num->n_bigits - 1] == 0) {
+		--num->n_bigits;
+	}
+}
+
+void
+serd_bigint_set_u64(SerdBigint* num, const uint64_t value)
+{
+	serd_bigint_zero(num);
+
+	num->bigits[0] = (Bigit)(value & bigit_mask);
+	num->bigits[1] = (Bigit)(value >> BIGINT_BIGIT_BITS);
+	num->n_bigits  = num->bigits[1] ? 2u : num->bigits[0] ? 1u : 0u;
+}
+
+void
+serd_bigint_set_pow10(SerdBigint* num, const unsigned exponent)
+{
+	serd_bigint_set_u32(num, 1);
+	serd_bigint_multiply_pow10(num, exponent);
+}
+
+static uint32_t
+read_u32(const char* const str, uint32_t* result, uint32_t* n_digits)
+{
+	static const size_t uint32_digits10 = 9;
+
+	*result = *n_digits = 0;
+
+	uint32_t i = 0;
+	for (; str[i] && *n_digits < uint32_digits10; ++i) {
+		if (str[i] >= '0' && str[i] <= '9') {
+			*result = *result * 10u + (unsigned)(str[i] - '0');
+			*n_digits += 1;
+		} else if (str[i] != '.') {
+			break;
+		}
+	}
+
+	return i;
+}
+
+void
+serd_bigint_set_decimal_string(SerdBigint* num, const char* const str)
+{
+	serd_bigint_zero(num);
+
+	uint32_t pos      = 0;
+	uint32_t n_digits = 0;
+	uint32_t n_read   = 0;
+	uint32_t word     = 0;
+	while ((n_read = read_u32(str + pos, &word, &n_digits))) {
+		serd_bigint_multiply_u32(num, (uint32_t)POW10[n_digits]);
+		serd_bigint_add_u32(num, word);
+		pos += n_read;
+	}
+
+	serd_bigint_clamp(num);
+}
+
+void
+serd_bigint_set_hex_string(SerdBigint* num, const char* const str)
+{
+	serd_bigint_zero(num);
+
+	// Read digits from right to left until we run off the beginning
+	const int length       = (int)strlen(str);
+	char      digit_buf[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
+	int       i            = length - 8;
+	for (; i >= 0; i -= 8) {
+		memcpy(digit_buf, str + i, 8);
+		num->bigits[num->n_bigits++] = (Bigit)strtoll(digit_buf, NULL, 16);
+	}
+
+	// Read leftovers into MSB if necessary
+	if (i > -8) {
+		memset(digit_buf, 0, sizeof(digit_buf));
+		memcpy(digit_buf, str, 8u + (unsigned)i);
+		num->bigits[num->n_bigits++] = (Bigit)strtoll(digit_buf, NULL, 16);
+	}
+
+	serd_bigint_clamp(num);
+}
+
+void
+serd_bigint_multiply_u32(SerdBigint* num, const uint32_t factor)
+{
+	switch (factor) {
+	case 0: serd_bigint_zero(num); return;
+	case 1: return;
+	default: break;
+	}
+
+	Hugit carry = 0;
+	for (unsigned i = 0; i < num->n_bigits; ++i) {
+		const Hugit p     = (Hugit)factor * num->bigits[i];
+		const Hugit hugit = p + (carry & bigit_mask);
+
+		num->bigits[i] = (Bigit)(hugit & bigit_mask);
+
+		carry = (hugit >> 32) + (carry >> 32);
+	}
+
+	for (; carry; carry >>= 32) {
+		assert(num->n_bigits + 1 <= BIGINT_MAX_BIGITS);
+		num->bigits[num->n_bigits++] = (Bigit)carry;
+	}
+}
+
+void
+serd_bigint_multiply_u64(SerdBigint* num, const uint64_t factor)
+{
+	switch (factor) {
+	case 0: serd_bigint_zero(num); return;
+	case 1: return;
+	default: break;
+	}
+
+	const Hugit f_lo = factor & bigit_mask;
+	const Hugit f_hi = factor >> 32;
+
+	Hugit carry = 0;
+	for (unsigned i = 0; i < num->n_bigits; ++i) {
+		const Hugit p_lo  = f_lo * num->bigits[i];
+		const Hugit p_hi  = f_hi * num->bigits[i];
+		const Hugit hugit = p_lo + (carry & bigit_mask);
+
+		num->bigits[i] = (Bigit)(hugit & bigit_mask);
+		carry          = p_hi + (hugit >> 32) + (carry >> 32);
+	}
+
+	for (; carry; carry >>= 32) {
+		assert(num->n_bigits + 1 <= BIGINT_MAX_BIGITS);
+		num->bigits[num->n_bigits++] = (Bigit)(carry & bigit_mask);
+	}
+}
+
+void
+serd_bigint_multiply_pow10(SerdBigint* num, const unsigned exponent)
+{
+	/* To reduce multiplication, we exploit 10^e = (2*5)^e = 2^e * 5^e to
+	   factor out an exponentiation by 5 instead of 10.  So, we first multiply
+	   by 5^e (hard), then by 2^e (just a single left shift). */
+
+	// 5^27, the largest power of 5 that fits in 64 bits
+	static const uint64_t pow5_27 = 7450580596923828125ull;
+
+	// Powers of 5 up to 5^13, the largest that fits in 32 bits
+	static const uint32_t pow5[] = {
+	        1,
+	        5,
+	        5 * 5,
+	        5 * 5 * 5,
+	        5 * 5 * 5 * 5,
+	        5 * 5 * 5 * 5 * 5,
+	        5 * 5 * 5 * 5 * 5 * 5,
+	        5 * 5 * 5 * 5 * 5 * 5 * 5,
+	        5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
+	        5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
+	        5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
+	        5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
+	        5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
+	        5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
+	};
+
+	if (exponent == 0 || num->n_bigits == 0) {
+		return;
+	}
+
+	// Multiply by 5^27 until e < 27 so we can switch to 32 bits
+	unsigned e = exponent;
+	while (e >= 27) {
+		serd_bigint_multiply_u64(num, pow5_27);
+		e -= 27;
+	}
+
+	// Multiply by 5^13 until e < 13 so we have only one multiplication left
+	while (e >= 13) {
+		serd_bigint_multiply_u32(num, pow5[13]);
+		e -= 13;
+	}
+
+	// Multiply by the final 5^e (which may be zero, making this a noop)
+	serd_bigint_multiply_u32(num, pow5[e]);
+
+	// Finally multiply by 2^e
+	serd_bigint_shift_left(num, exponent);
+}
+
+int
+serd_bigint_compare(const SerdBigint* lhs, const SerdBigint* rhs)
+{
+	if (lhs->n_bigits < rhs->n_bigits) {
+		return -1;
+	} else if (lhs->n_bigits > rhs->n_bigits) {
+		return 1;
+	}
+
+	for (int i = (int)lhs->n_bigits - 1; i >= 0; --i) {
+		const Bigit bigit_l = lhs->bigits[i];
+		const Bigit bigit_r = rhs->bigits[i];
+		if (bigit_l < bigit_r) {
+			return -1;
+		} else if (bigit_l > bigit_r) {
+			return 1;
+		}
+	}
+
+	return 0;
+}
+
+int
+serd_bigint_plus_compare(const SerdBigint* l,
+                         const SerdBigint* p,
+                         const SerdBigint* c)
+{
+	assert(serd_bigint_is_clamped(l));
+	assert(serd_bigint_is_clamped(p));
+	assert(serd_bigint_is_clamped(c));
+
+	if (l->n_bigits < p->n_bigits) {
+		return serd_bigint_plus_compare(p, l, c);
+	} else if (l->n_bigits + 1 < c->n_bigits) {
+		return -1;
+	} else if (l->n_bigits > c->n_bigits) {
+		return 1;
+	} else if (p->n_bigits < l->n_bigits && l->n_bigits < c->n_bigits) {
+		return -1;
+	}
+
+	Hugit borrow = 0;
+	for (int i = (int)c->n_bigits - 1; i >= 0; --i) {
+		const Bigit ai  = l->bigits[i];
+		const Bigit bi  = p->bigits[i];
+		const Bigit ci  = c->bigits[i];
+		const Hugit sum = (Hugit)ai + bi;
+
+		if (sum > ci + borrow) {
+			return 1;
+		} else if ((borrow += ci - sum) > 1) {
+			return -1;
+		}
+
+		borrow <<= 32;
+	}
+
+	return borrow ? -1 : 0;
+}
+
+void
+serd_bigint_add_u32(SerdBigint* lhs, const uint32_t rhs)
+{
+	if (lhs->n_bigits == 0) {
+		serd_bigint_set_u32(lhs, rhs);
+		return;
+	}
+
+	Hugit sum   = (Hugit)lhs->bigits[0] + rhs;
+	Bigit carry = (Bigit)(sum >> 32);
+
+	lhs->bigits[0] = (Bigit)(sum & bigit_mask);
+
+	unsigned i = 1;
+	for (; carry; ++i) {
+		assert(carry == 0 || carry == 1);
+
+		sum            = (Hugit)carry + lhs->bigits[i];
+		lhs->bigits[i] = (Bigit)(sum & bigit_mask);
+		carry          = (Bigit)((sum & carry_mask) >> 32);
+	}
+
+	lhs->n_bigits = MAX(i, lhs->n_bigits);
+	assert(serd_bigint_is_clamped(lhs));
+}
+
+void
+serd_bigint_add(SerdBigint* lhs, const SerdBigint* rhs)
+{
+	assert(MAX(lhs->n_bigits, rhs->n_bigits) + 1 <= BIGINT_MAX_BIGITS);
+
+	bool     carry = 0;
+	unsigned i     = 0;
+	for (; i < rhs->n_bigits; ++i) {
+		const Hugit sum = (Hugit)lhs->bigits[i] + rhs->bigits[i] + carry;
+
+		lhs->bigits[i] = (Bigit)(sum & bigit_mask);
+		carry          = (sum & carry_mask) >> 32;
+	}
+
+	for (; carry; ++i) {
+		const Hugit sum = (Hugit)lhs->bigits[i] + carry;
+
+		lhs->bigits[i] = (Bigit)(sum & bigit_mask);
+		carry          = (sum & carry_mask) >> 32;
+	}
+
+	lhs->n_bigits = MAX(i, lhs->n_bigits);
+	assert(serd_bigint_is_clamped(lhs));
+}
+
+void
+serd_bigint_subtract(SerdBigint* lhs, const SerdBigint* rhs)
+{
+	assert(serd_bigint_is_clamped(lhs));
+	assert(serd_bigint_is_clamped(rhs));
+	assert(serd_bigint_compare(lhs, rhs) >= 0);
+
+	bool     borrow = 0;
+	unsigned i      = 0;
+	for (i = 0; i < rhs->n_bigits; ++i) {
+		const Bigit l = lhs->bigits[i];
+		const Bigit r = rhs->bigits[i];
+
+		lhs->bigits[i] = l - r - borrow;
+		borrow         = l < r || (l == r && borrow);
+	}
+
+	for (; borrow; ++i) {
+		const Bigit l = lhs->bigits[i];
+
+		lhs->bigits[i] -= borrow;
+
+		borrow = l == 0;
+	}
+
+	serd_bigint_clamp(lhs);
+}
+
+static unsigned
+serd_bigint_leading_zeros(const SerdBigint* num)
+{
+	return 32 * (BIGINT_MAX_BIGITS - num->n_bigits) +
+	       serd_clz32(num->bigits[num->n_bigits - 1]);
+}
+
+static Bigit
+serd_bigint_left_shifted_bigit_i(const SerdBigint* num,
+                                 const Offset      amount,
+                                 const unsigned    index)
+{
+	assert(serd_bigint_is_clamped(num));
+	if (amount.bigits == 0 && amount.bits == 0) {
+		return num->bigits[index];
+	}
+
+	if (index < amount.bigits) {
+		return 0;
+	}
+
+	if (amount.bits == 0) { // Simple bigit-aligned shift
+		return num->bigits[index - amount.bigits];
+	} else if (index == amount.bigits) { // Last non-zero bigit
+		return num->bigits[0] << amount.bits;
+	} else { // Bigit + sub-bigit bit offset shift
+		const unsigned right_shift = BIGINT_BIGIT_BITS - amount.bits;
+		return (num->bigits[index - amount.bigits] << amount.bits) |
+		       (num->bigits[index - amount.bigits - 1] >> right_shift);
+	}
+}
+
+Bigit
+serd_bigint_left_shifted_bigit(const SerdBigint* num,
+                               const unsigned    amount,
+                               const unsigned    index)
+{
+	return serd_bigint_left_shifted_bigit_i(num, make_offset(amount), index);
+}
+
+void
+serd_bigint_subtract_left_shifted(SerdBigint*       lhs,
+                                  const SerdBigint* rhs,
+                                  const unsigned    amount)
+{
+	assert(serd_bigint_is_clamped(lhs));
+	assert(serd_bigint_is_clamped(rhs));
+#ifndef NDEBUG
+	{
+		SerdBigint check_rhs = *rhs;
+		serd_bigint_shift_left(&check_rhs, amount);
+		assert(serd_bigint_compare(lhs, &check_rhs) >= 0);
+	}
+#endif
+
+	const Offset   offset = make_offset(amount);
+	const unsigned r_n_bigits =
+	        rhs->n_bigits + offset.bigits + (bool)offset.bits;
+
+	bool     borrow = 0;
+	unsigned i      = 0;
+	for (i = 0; i < r_n_bigits; ++i) {
+		const Bigit l = lhs->bigits[i];
+		const Bigit r = serd_bigint_left_shifted_bigit_i(rhs, offset, i);
+
+		lhs->bigits[i] = l - r - borrow;
+		borrow         = l < r || ((l == r) && borrow);
+	}
+
+	for (; borrow; ++i) {
+		const Bigit l = lhs->bigits[i];
+
+		lhs->bigits[i] -= borrow;
+
+		borrow = l == 0;
+	}
+
+	serd_bigint_clamp(lhs);
+}
+
+uint32_t
+serd_bigint_divmod(SerdBigint* lhs, const SerdBigint* rhs)
+{
+	assert(serd_bigint_is_clamped(lhs));
+	assert(serd_bigint_is_clamped(rhs));
+	assert(rhs->n_bigits > 0);
+	if (lhs->n_bigits < rhs->n_bigits) {
+		return 0;
+	}
+
+	uint32_t       result = 0;
+	const Bigit    r0     = rhs->bigits[rhs->n_bigits - 1];
+	const unsigned rlz    = serd_bigint_leading_zeros(rhs);
+
+	// Shift and subtract until the LHS does not have more bigits
+	int big_steps = 0;
+	while (lhs->n_bigits > rhs->n_bigits) {
+		const unsigned llz   = serd_bigint_leading_zeros(lhs);
+		const unsigned shift = rlz - llz - 1;
+
+		result += 1u << shift;
+		serd_bigint_subtract_left_shifted(lhs, rhs, shift);
+		++big_steps;
+	}
+
+	// Handle simple termination cases
+	int cmp = serd_bigint_compare(lhs, rhs);
+	if (cmp < 0) {
+		return result;
+	} else if (cmp > 0 && lhs->n_bigits == 1) {
+		assert(rhs->n_bigits == 1);
+		const Bigit l0 = lhs->bigits[lhs->n_bigits - 1];
+
+		lhs->bigits[lhs->n_bigits - 1] = l0 % r0;
+		lhs->n_bigits -= (lhs->bigits[lhs->n_bigits - 1] == 0);
+		return result + l0 / r0;
+	}
+
+	// Both now have the same number of digits, finish with subtraction
+	int final_steps = 0;
+	for (; cmp >= 0; cmp = serd_bigint_compare(lhs, rhs)) {
+		const unsigned llz = serd_bigint_leading_zeros(lhs);
+		if (rlz == llz) {
+			// Both have the same number of leading zeros, just subtract
+			serd_bigint_subtract(lhs, rhs);
+			return result + 1;
+		}
+
+		const unsigned shift = rlz - llz - 1;
+		result += 1u << shift;
+		serd_bigint_subtract_left_shifted(lhs, rhs, shift);
+		++final_steps;
+	}
+
+	return result;
+}
diff --git a/src/bigint.h b/src/bigint.h
new file mode 100644
index 00000000..324a115d
--- /dev/null
+++ b/src/bigint.h
@@ -0,0 +1,117 @@
+/*
+  Copyright 2019-2020 David Robillard <http://drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#ifndef SERD_BIGINT_H
+#define SERD_BIGINT_H
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+
+typedef uint32_t Bigit;
+
+/* We need enough precision for any double, the "largest" of which (using
+   absolute exponents) is the smallest subnormal ~= 5e-324.  This is 1076 bits
+   long, but we need a bit more space for arithmetic.  This is absurd, but such
+   is decimal.  These are only used on the stack so it doesn't hurt too much.
+*/
+
+#define BIGINT_MAX_SIGNIFICANT_BITS 1280
+#define BIGINT_BIGIT_BITS 32
+#define BIGINT_MAX_BIGITS (BIGINT_MAX_SIGNIFICANT_BITS / BIGINT_BIGIT_BITS)
+
+typedef struct
+{
+	Bigit    bigits[BIGINT_MAX_BIGITS];
+	unsigned n_bigits;
+} SerdBigint;
+
+void
+serd_bigint_zero(SerdBigint* num);
+
+size_t
+serd_bigint_print_hex(FILE* stream, const SerdBigint* num);
+
+size_t
+serd_bigint_to_hex_string(const SerdBigint* num, char* buf, size_t len);
+
+void
+serd_bigint_clamp(SerdBigint* num);
+
+void
+serd_bigint_shift_left(SerdBigint* num, unsigned amount);
+
+void
+serd_bigint_set(SerdBigint* num, const SerdBigint* value);
+
+void
+serd_bigint_set_u32(SerdBigint* num, uint32_t value);
+
+void
+serd_bigint_set_u64(SerdBigint* num, uint64_t value);
+
+void
+serd_bigint_set_pow10(SerdBigint* num, unsigned exponent);
+
+void
+serd_bigint_set_decimal_string(SerdBigint* num, const char* str);
+
+void
+serd_bigint_set_hex_string(SerdBigint* num, const char* str);
+
+void
+serd_bigint_multiply_u32(SerdBigint* num, uint32_t factor);
+
+void
+serd_bigint_multiply_u64(SerdBigint* num, uint64_t factor);
+
+void
+serd_bigint_multiply_pow10(SerdBigint* num, unsigned exponent);
+
+int
+serd_bigint_compare(const SerdBigint* lhs, const SerdBigint* rhs);
+
+void
+serd_bigint_add_u32(SerdBigint* lhs, uint32_t rhs);
+
+void
+serd_bigint_add(SerdBigint* lhs, const SerdBigint* rhs);
+
+void
+serd_bigint_subtract(SerdBigint* lhs, const SerdBigint* rhs);
+
+Bigit
+serd_bigint_left_shifted_bigit(const SerdBigint* num,
+                               unsigned          amount,
+                               unsigned          index);
+
+/// Faster implementation of serd_bigint_subtract(lhs, rhs << amount)
+void
+serd_bigint_subtract_left_shifted(SerdBigint*       lhs,
+                                  const SerdBigint* rhs,
+                                  unsigned          amount);
+
+/// Faster implementation of serd_bigint_compare(l + p, c)
+int
+serd_bigint_plus_compare(const SerdBigint* l,
+                         const SerdBigint* p,
+                         const SerdBigint* c);
+
+/// Divide and set `lhs` to modulo
+uint32_t
+serd_bigint_divmod(SerdBigint* lhs, const SerdBigint* rhs);
+
+#endif // SERD_BIGINT_H
diff --git a/src/int_math.h b/src/int_math.h
index b2e66856..85305a4a 100644
--- a/src/int_math.h
+++ b/src/int_math.h
@@ -20,6 +20,7 @@
 #include <stdint.h>
 
 #define MIN(x, y) ((x) < (y) ? (x) : (y))
+#define MAX(x, y) ((x) > (y) ? (x) : (y))
 
 static const uint64_t POW10[] = {1ull,
                                  10ull,
diff --git a/tests/bigint_test.c b/tests/bigint_test.c
new file mode 100644
index 00000000..1bead4cf
--- /dev/null
+++ b/tests/bigint_test.c
@@ -0,0 +1,930 @@
+/*
+  Copyright 2011-2020 David Robillard <http://drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#undef NDEBUG
+
+#include "../src/bigint.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+
+#define MAX_HEX_LEN 512
+
+/* Some test data borrowed from http://github.com/google/double-conversion
+   which uses a completely different bigint representation (so if these agree,
+   everything is probably fine).  Others cases are either made up to hit the
+   edges of the implementation, or interesting cases collected from testing the
+   decimal implementation.  Almost everything here uses the hex representation
+   so it is easy to dump into Python as a sanity check. */
+
+static inline SerdBigint
+bigint_from_hex(const char* str)
+{
+	SerdBigint num;
+	serd_bigint_set_hex_string(&num, str);
+	return num;
+}
+
+static bool
+check_string_equals(const char* const actual, const char* const expected)
+{
+	if (strcmp(actual, expected)) {
+		fprintf(stderr, "error: result   \"%s\"\n", actual);
+		fprintf(stderr, "note:  expected \"%s\"\n", expected);
+		return false;
+	}
+
+	return true;
+}
+
+static bool
+check_hex_equals(const char* const str, const SerdBigint* const num)
+{
+	char buffer[MAX_HEX_LEN] = {0};
+	serd_bigint_to_hex_string(num, buffer, sizeof(buffer));
+
+	const char* s = str;
+	while (*s == ' ') {
+		++s; // Skip leading whitespace
+	}
+
+	return check_string_equals(buffer, s);
+}
+
+#define CHECK_HEXEQ(str, num) assert(check_hex_equals(str, num))
+#define CHECK_STREQ(s1, s2) assert(check_string_equals(s1, s2))
+
+#define CHECK_SET(setter, value, expected)     \
+	do {                                       \
+		SerdBigint num;                        \
+		serd_bigint_set_##setter(&num, value); \
+		CHECK_HEXEQ(expected, &num);           \
+	} while (0)
+
+static void
+test_set(void)
+{
+	CHECK_SET(u32, 0, "0");
+	CHECK_SET(u32, 0xA, "A");
+	CHECK_SET(u32, 0x20, "20");
+	CHECK_SET(u32, 0x12345678, "12345678");
+
+	CHECK_SET(u64, 0, "0");
+	CHECK_SET(u64, 0xA, "A");
+	CHECK_SET(u64, 0x20, "20");
+	CHECK_SET(u64, 0x12345678, "12345678");
+	CHECK_SET(u64, 0xFFFFFFFFFFFFFFFFull, "FFFFFFFFFFFFFFFF");
+	CHECK_SET(u64, 0x123456789ABCDEF0ull, "123456789ABCDEF0");
+	CHECK_SET(u64, 0x123456789ABCDEF0ull, "123456789ABCDEF0");
+
+	CHECK_SET(decimal_string, "0", "0");
+	CHECK_SET(decimal_string, "1", "1");
+	CHECK_SET(decimal_string, "01234567890", "499602D2");
+	CHECK_SET(decimal_string, "12345.67890", "499602D2");
+	CHECK_SET(decimal_string, "12345.67890EOF", "499602D2");
+	CHECK_SET(decimal_string, "012345678901", "2DFDC1C35");
+	CHECK_SET(decimal_string, "12345.678901", "2DFDC1C35");
+	CHECK_SET(decimal_string,
+	          "340282366920938463463374607431768211456",
+	          "100000000000000000000000000000000");
+
+	CHECK_SET(hex_string, "0", "0");
+	CHECK_SET(hex_string, "123456789ABCDEF0", "123456789ABCDEF0");
+
+	const SerdBigint orig = bigint_from_hex("123456789ABCDEF01");
+	SerdBigint       copy;
+	serd_bigint_set(&copy, &orig);
+	CHECK_HEXEQ("123456789ABCDEF01", &copy);
+}
+
+static void
+check_print_hex(const char* value, const size_t len)
+{
+	assert(len <= MAX_HEX_LEN);
+
+	FILE* const      stream = tmpfile();
+	const SerdBigint num    = bigint_from_hex(value);
+
+	serd_bigint_print_hex(stream, &num);
+	fseek(stream, 0, SEEK_SET);
+
+	char         buf[MAX_HEX_LEN] = {0};
+	const size_t n_read           = fread(buf, 1, len, stream);
+
+	fclose(stream);
+
+	CHECK_STREQ(buf, value);
+	assert(n_read == len);
+}
+
+static void
+check_to_hex_string(const char*  value,
+                    const size_t len,
+                    const char*  expected,
+                    const size_t expected_n_written)
+{
+	const SerdBigint num              = bigint_from_hex(value);
+	char             buf[MAX_HEX_LEN] = {0};
+	const size_t     n_written = serd_bigint_to_hex_string(&num, buf, len);
+
+	assert(n_written == expected_n_written);
+	CHECK_STREQ(buf, expected);
+}
+
+static void
+test_output(void)
+{
+	check_print_hex("0", 1);
+	check_print_hex("1", 1);
+	check_print_hex("1234567", 7);
+	check_print_hex("12345678", 8);
+	check_print_hex("123456789ABCDEF0", 16);
+	check_print_hex("123456789ABCDEF01", 17);
+
+	check_to_hex_string("123456789", 1, "", 0);
+	check_to_hex_string("123456789", 9, "12345678", 9);
+	check_to_hex_string("123456789", 10, "123456789", 9);
+	check_to_hex_string("123456789ABCDEF", 16, "123456789ABCDEF", 15);
+}
+
+static void
+check_left_shifted_bigit(const char*    value,
+                         const unsigned amount,
+                         const unsigned index,
+                         const Bigit    expected)
+{
+	const SerdBigint num = bigint_from_hex(value);
+	const Bigit actual   = serd_bigint_left_shifted_bigit(&num, amount, index);
+
+	assert(expected == actual);
+}
+
+static void
+test_left_shifted_bigit(void)
+{
+	check_left_shifted_bigit("0", 100, 1, 0x0);
+	check_left_shifted_bigit("1", 0, 0, 0x1);
+	check_left_shifted_bigit("1", 1, 0, 0x2);
+	check_left_shifted_bigit("1", 4, 0, 0x10);
+	check_left_shifted_bigit("1", 32, 0, 0x0);
+	check_left_shifted_bigit("1", 32, 1, 0x1);
+	check_left_shifted_bigit("1", 64, 0, 0x0);
+	check_left_shifted_bigit("1", 64, 1, 0x0);
+	check_left_shifted_bigit("1", 64, 2, 0x1);
+	check_left_shifted_bigit("123456789ABCDEF", 64, 0, 0x0);
+	check_left_shifted_bigit("123456789ABCDEF", 64, 1, 0x0);
+	check_left_shifted_bigit("123456789ABCDEF", 64, 2, 0x89ABCDEF);
+	check_left_shifted_bigit("123456789ABCDEF", 64, 3, 0x1234567);
+	check_left_shifted_bigit("123456789ABCDEF", 64, 4, 0x0);
+	check_left_shifted_bigit("123456789ABCDEF", 65, 0, 0x0);
+	check_left_shifted_bigit("123456789ABCDEF", 65, 1, 0x0);
+	check_left_shifted_bigit("123456789ABCDEF", 65, 2, 0x13579BDE);
+	check_left_shifted_bigit("123456789ABCDEF", 65, 3, 0x2468ACF);
+	check_left_shifted_bigit("123456789ABCDEF", 65, 4, 0x0);
+}
+
+static void
+check_shift_left(const char* value, const unsigned amount, const char* expected)
+{
+	SerdBigint num = bigint_from_hex(value);
+	serd_bigint_shift_left(&num, amount);
+	CHECK_HEXEQ(expected, &num);
+}
+
+static void
+test_shift_left(void)
+{
+	check_shift_left("0", 100, "0");
+	check_shift_left("1", 1, "2");
+	check_shift_left("1", 4, "10");
+	check_shift_left("1", 32, "100000000");
+	check_shift_left("1", 64, "10000000000000000");
+	check_shift_left("123456789ABCDEF", 0, "123456789ABCDEF");
+	check_shift_left("123456789ABCDEF", 64, "123456789ABCDEF0000000000000000");
+	check_shift_left("123456789ABCDEF", 65, "2468ACF13579BDE0000000000000000");
+	check_shift_left("16B8B5E06EDC79", 23, "B5C5AF0376E3C800000");
+}
+
+static void
+check_add_u32(const char* value, const uint32_t rhs, const char* expected)
+{
+	SerdBigint num = bigint_from_hex(value);
+	serd_bigint_add_u32(&num, rhs);
+	CHECK_HEXEQ(expected, &num);
+}
+
+static void
+test_add_u32(void)
+{
+	check_add_u32("0", 1, "1");
+	check_add_u32("1", 1, "2");
+	check_add_u32("FFFFFFF", 1, "10000000");
+	check_add_u32("FFFFFFFFFFFFFF", 1, "100000000000000");
+
+	check_add_u32("10000000000000000000000000000000000080000000",
+	              0x80000000,
+	              "10000000000000000000000000000000000100000000");
+
+	check_add_u32("10000000000000000000000000000000000000000000",
+	              0x1,
+	              "10000000000000000000000000000000000000000001");
+}
+
+static void
+check_add(const char* lhs_hex, const char* rhs_hex, const char* expected)
+{
+	SerdBigint       lhs = bigint_from_hex(lhs_hex);
+	const SerdBigint rhs = bigint_from_hex(rhs_hex);
+
+	serd_bigint_add(&lhs, &rhs);
+	CHECK_HEXEQ(expected, &lhs);
+}
+
+static void
+test_add(void)
+{
+	check_add("1", "0", "1");
+	check_add("1", "1", "2");
+	check_add("FFFFFFF", "1", "10000000");
+	check_add("FFFFFFFFFFFFFF", "1", "100000000000000");
+	check_add("1", "1000000000000", "1000000000001");
+	check_add("FFFFFFF", "1000000000000", "100000FFFFFFF");
+
+	check_add("10000000000000000000000000000000000000000000",
+	          "1",
+	          "10000000000000000000000000000000000000000001");
+
+	check_add("10000000000000000000000000000000000000000000",
+	          "1000000000000",
+	          "10000000000000000000000000000001000000000000");
+
+	check_add("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
+	          "1000000000000",
+	          "1000000000000000000000000000000FFFFFFFFFFFF");
+
+	check_add("10000000000000000000000000",
+	          "1000000000000",
+	          "10000000000001000000000000");
+
+	check_add("1",
+	          "10000000000000000000000000000",
+	          "10000000000000000000000000001");
+
+	check_add("FFFFFFF",
+	          "10000000000000000000000000000",
+	          "1000000000000000000000FFFFFFF");
+
+	check_add("10000000000000000000000000000000000000000000",
+	          "10000000000000000000000000000",
+	          "10000000000000010000000000000000000000000000");
+
+	check_add("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
+	          "10000000000000000000000000000",
+	          "100000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFF");
+
+	check_add("10000000000000000000000000",
+	          "10000000000000000000000000000",
+	          "10010000000000000000000000000");
+}
+
+static void
+check_subtract(const char* lhs_hex, const char* rhs_hex, const char* expected)
+{
+	SerdBigint       lhs = bigint_from_hex(lhs_hex);
+	const SerdBigint rhs = bigint_from_hex(rhs_hex);
+
+	serd_bigint_subtract(&lhs, &rhs);
+	CHECK_HEXEQ(expected, &lhs);
+}
+
+static void
+test_subtract(void)
+{
+	check_subtract("1", "0", "1");
+	check_subtract("2", "0", "2");
+	check_subtract("10000000", "1", "FFFFFFF");
+	check_subtract("1FFFFFFFF00000000", "FFFFFFFF", "1FFFFFFFE00000001");
+	check_subtract("100000000000000", "1", "FFFFFFFFFFFFFF");
+	check_subtract("1000000000001", "1000000000000", "1");
+	check_subtract("100000FFFFFFF", "1000000000000", "FFFFFFF");
+
+	check_subtract("11F2678326EA00000000",
+	               "0878678326EAC9000000",
+	               "979FFFFFFFF37000000");
+
+	check_subtract("10000000000000000000000000000000000000000001",
+	               "00000000000000000000000000000000000000000001",
+	               "10000000000000000000000000000000000000000000");
+
+	check_subtract("10000000000000000000000000000001000000000000",
+	               "00000000000000000000000000000001000000000000",
+	               "10000000000000000000000000000000000000000000");
+
+	check_subtract("1000000000000000000000000000000FFFFFFFFFFFF",
+	               "0000000000000000000000000000001000000000000",
+	               " FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
+
+	check_subtract("10000000000000000000000000",
+	               "00000000000001000000000000",
+	               " FFFFFFFFFFFFF000000000000");
+
+	check_subtract("10000000000000000000000000",
+	               "1000000000000000000000000",
+	               "F000000000000000000000000");
+
+	check_subtract("FFFFFFF000000000000000",
+	               "0000000000000800000000",
+	               "FFFFFFEFFFFFF800000000");
+
+	check_subtract("10000000000000000000000000000000000000000000",
+	               "00000000000000000000000000000000000800000000",
+	               "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF800000000");
+
+	check_subtract("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
+	               "000000000000000000000000000000000800000000",
+	               "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFFF");
+}
+
+static void
+check_subtract_left_shifted(const char*    lhs_hex,
+                            const char*    rhs_hex,
+                            const unsigned amount,
+                            const char*    expected)
+{
+	SerdBigint       lhs = bigint_from_hex(lhs_hex);
+	const SerdBigint rhs = bigint_from_hex(rhs_hex);
+
+	serd_bigint_subtract_left_shifted(&lhs, &rhs, amount);
+	CHECK_HEXEQ(expected, &lhs);
+}
+
+static void
+test_subtract_left_shifted(void)
+{
+	check_subtract_left_shifted("1", "0", 1, "1");
+	check_subtract_left_shifted("10000000", "1", 1, "FFFFFFE");
+	check_subtract_left_shifted("100000000", "40000000", 2, "0");
+	check_subtract_left_shifted("1000000000000000", "400000000000000", 2, "0");
+	check_subtract_left_shifted("1000000000000000", "800000000000000", 1, "0");
+	check_subtract_left_shifted("1000000000000000", "F", 16, "FFFFFFFFFF10000");
+	check_subtract_left_shifted("1000000000000000", "F", 24, "FFFFFFFF1000000");
+	check_subtract_left_shifted("100000000000000", "1", 0, "FFFFFFFFFFFFFF");
+	check_subtract_left_shifted("100000000000000", "1", 56, "0");
+
+	check_subtract_left_shifted("11F2678326EA00000000",
+	                            "43C33C1937564800000",
+	                            1,
+	                            "979FFFFFFFF37000000");
+}
+
+static void
+check_multiply_u32(const char* value, const uint32_t rhs, const char* expected)
+{
+	SerdBigint num = bigint_from_hex(value);
+	serd_bigint_multiply_u32(&num, rhs);
+	CHECK_HEXEQ(expected, &num);
+}
+
+static void
+test_multiply_u32(void)
+{
+	check_multiply_u32("0", 0x25, "0");
+	check_multiply_u32("123456789ABCDEF", 0, "0");
+	check_multiply_u32("2", 0x5, "A");
+	check_multiply_u32("10000000", 0x9, "90000000");
+	check_multiply_u32("100000000000000", 0xFFFF, "FFFF00000000000000");
+	check_multiply_u32("100000000000000", 0xFFFFFFFF, "FFFFFFFF00000000000000");
+	check_multiply_u32("1234567ABCD", 0xFFF, "12333335552433");
+	check_multiply_u32("1234567ABCD", 0xFFFFFFF, "12345679998A985433");
+	check_multiply_u32("FFFFFFFFFFFFFFFF", 0x2, "1FFFFFFFFFFFFFFFE");
+	check_multiply_u32("FFFFFFFFFFFFFFFF", 0x4, "3FFFFFFFFFFFFFFFC");
+	check_multiply_u32("FFFFFFFFFFFFFFFF", 0xF, "EFFFFFFFFFFFFFFF1");
+	check_multiply_u32("FFFFFFFFFFFFFFFF", 0xFFFFFF, "FFFFFEFFFFFFFFFF000001");
+	check_multiply_u32("377654D193A171", 10000000, "210EDD6D4CDD2580EE80");
+	check_multiply_u32("2E3F36D108373C00000", 10, "1CE78242A52285800000");
+
+	check_multiply_u32("10000000000000000000000000",
+	                   0x00000002,
+	                   "20000000000000000000000000");
+
+	check_multiply_u32("10000000000000000000000000",
+	                   0x0000000F,
+	                   "F0000000000000000000000000");
+
+	check_multiply_u32("FFFF0000000000000000000000000",
+	                   0xFFFF,
+	                   "FFFE00010000000000000000000000000");
+
+	check_multiply_u32("FFFF0000000000000000000000000",
+	                   0xFFFFFFFF,
+	                   "FFFEFFFF00010000000000000000000000000");
+
+	check_multiply_u32("FFFF0000000000000000000000000",
+	                   0xFFFFFFFF,
+	                   "FFFEFFFF00010000000000000000000000000");
+}
+
+static void
+check_multiply_u64(const char* value, const uint64_t rhs, const char* expected)
+{
+	SerdBigint num = bigint_from_hex(value);
+	serd_bigint_multiply_u64(&num, rhs);
+	CHECK_HEXEQ(expected, &num);
+}
+
+static void
+test_multiply_u64(void)
+{
+	check_multiply_u64("0", 0x25, "0");
+	check_multiply_u64("123456789ABCDEF", 0, "0");
+	check_multiply_u64("123456789ABCDEF", 1, "123456789ABCDEF");
+	check_multiply_u64("2", 0x5, "A");
+	check_multiply_u64("10000000", 0x9, "90000000");
+	check_multiply_u64("100000000000000", 0xFFFF, "FFFF00000000000000");
+	check_multiply_u64("1234567ABCD", 0xFFF, "12333335552433");
+	check_multiply_u64("1234567ABCD", 0xFFFFFFFFFFull, "1234567ABCBDCBA985433");
+	check_multiply_u64("FFFFFFFFFFFFFFFF", 0x2, "1FFFFFFFFFFFFFFFE");
+	check_multiply_u64("FFFFFFFFFFFFFFFF", 0x4, "3FFFFFFFFFFFFFFFC");
+	check_multiply_u64("FFFFFFFFFFFFFFFF", 0xF, "EFFFFFFFFFFFFFFF1");
+
+	check_multiply_u64("100000000000000",
+	                   0xFFFFFFFFFFFFFFFFull,
+	                   "FFFFFFFFFFFFFFFF00000000000000");
+
+	check_multiply_u64("FFFFFFFFFFFFFFFF",
+	                   0xFFFFFFFFFFFFFFFFull,
+	                   "FFFFFFFFFFFFFFFE0000000000000001");
+
+	check_multiply_u64("10000000000000000000000000",
+	                   0x00000002,
+	                   "20000000000000000000000000");
+
+	check_multiply_u64("10000000000000000000000000",
+	                   0x0000000F,
+	                   "F0000000000000000000000000");
+
+	check_multiply_u64("FFFF0000000000000000000000000",
+	                   0xFFFF,
+	                   "FFFE00010000000000000000000000000");
+
+	check_multiply_u64("FFFF0000000000000000000000000",
+	                   0xFFFFFFFF,
+	                   "FFFEFFFF00010000000000000000000000000");
+
+	check_multiply_u64("FFFF0000000000000000000000000",
+	                   0xFFFFFFFFFFFFFFFFull,
+	                   "FFFEFFFFFFFFFFFF00010000000000000000000000000");
+
+	check_multiply_u64("377654D193A171",
+	                   0x8AC7230489E80000ull,
+	                   "1E10EE4B11D15A7F3DE7F3C7680000");
+}
+
+static void
+check_multiply_pow10(const char*    value,
+                     const unsigned exponent,
+                     const char*    expected)
+{
+	SerdBigint num = bigint_from_hex(value);
+	serd_bigint_multiply_pow10(&num, exponent);
+	CHECK_HEXEQ(expected, &num);
+}
+
+static void
+test_multiply_pow10(void)
+{
+	check_multiply_pow10("0", 10, "0");
+	check_multiply_pow10("1234", 0, "1234");
+	check_multiply_pow10("4D2", 1, "3034");
+	check_multiply_pow10("4D2", 2, "1E208");
+	check_multiply_pow10("4D2", 3, "12D450");
+	check_multiply_pow10("4D2", 4, "BC4B20");
+	check_multiply_pow10("4D2", 5, "75AEF40");
+	check_multiply_pow10("4D2", 6, "498D5880");
+	check_multiply_pow10("4D2", 7, "2DF857500");
+	check_multiply_pow10("4D2", 8, "1CBB369200");
+	check_multiply_pow10("4D2", 9, "11F5021B400");
+	check_multiply_pow10("4D2", 10, "B3921510800");
+	check_multiply_pow10("4D2", 11, "703B4D2A5000");
+	check_multiply_pow10("4D2", 12, "4625103A72000");
+	check_multiply_pow10("4D2", 13, "2BD72A24874000");
+	check_multiply_pow10("4D2", 14, "1B667A56D488000");
+	check_multiply_pow10("4D2", 15, "11200C7644D50000");
+	check_multiply_pow10("4D2", 16, "AB407C9EB0520000");
+	check_multiply_pow10("4D2", 17, "6B084DE32E3340000");
+	check_multiply_pow10("4D2", 18, "42E530ADFCE0080000");
+	check_multiply_pow10("4D2", 19, "29CF3E6CBE0C0500000");
+	check_multiply_pow10("4D2", 20, "1A218703F6C783200000");
+	check_multiply_pow10("4D2", 21, "1054F4627A3CB1F400000");
+	check_multiply_pow10("4D2", 22, "A3518BD8C65EF38800000");
+	check_multiply_pow10("4D2", 23, "6612F7677BFB5835000000");
+	check_multiply_pow10("4D2", 24, "3FCBDAA0AD7D17212000000");
+	check_multiply_pow10("4D2", 25, "27DF68A46C6E2E74B4000000");
+	check_multiply_pow10("4D2", 26, "18EBA166C3C4DD08F08000000");
+	check_multiply_pow10("4D2", 27, "F9344E03A5B0A259650000000");
+	check_multiply_pow10("4D2", 28, "9BC0B0C2478E6577DF20000000");
+	check_multiply_pow10("4D2", 29, "61586E796CB8FF6AEB740000000");
+	check_multiply_pow10("4D2", 30, "3CD7450BE3F39FA2D32880000000");
+	check_multiply_pow10("4D2", 31, "26068B276E7843C5C3F9500000000");
+
+	check_multiply_pow10("4D2",
+	                     50,
+	                     "149D1B4CFED03B23AB5F4E1196EF45C0"
+	                     "8000000000000");
+
+	check_multiply_pow10("4D2",
+	                     100,
+	                     "5827249F27165024FBC47DFCA9359BF3"
+	                     "16332D1B91ACEECF471FBAB06D9B2000"
+	                     "0000000000000000000000");
+
+	check_multiply_pow10("4D2",
+	                     305,
+	                     "AFBA390D657B0829339F5B98DC852A89"
+	                     "682758E01829EADFD016D1528D4D548B"
+	                     "80894B9ED9C2EC6A9CABB4881302A637"
+	                     "9FF3058908FEAC310C52FCA009799718"
+	                     "8260B0B2E2EC96E471B7892AD9B4F9F9"
+	                     "A448CBF150D2E87F3934000000000000"
+	                     "00000000000000000000000000000000"
+	                     "00000000000000000000000000000000");
+
+	check_multiply_pow10("123456789ABCDEF0", 0, "123456789ABCDEF0");
+	check_multiply_pow10("123456789ABCDEF0",
+	                     44,
+	                     "51A1AD66ACE4E5C79209330F58F52DE3"
+	                     "7CEFFF1F000000000000");
+	check_multiply_pow10("123456789ABCDEF0",
+	                     88,
+	                     "16E0C6D18F4BFA7D0289B88382F56151"
+	                     "EB9DA5DB09D56C9BA5D8305619CEE057"
+	                     "4F00000000000000000000000");
+	check_multiply_pow10("123456789ABCDEF0",
+	                     132,
+	                     "6696B1DA27BEA173B5EFCAABBB8492A9"
+	                     "2AE3D97F7EE3C7314FB7E2FF8AEFD329"
+	                     "F5F8202C22650BB79A7D9F3867F00000"
+	                     "00000000000000000000000000000");
+	check_multiply_pow10("123456789ABCDEF0",
+	                     176,
+	                     "1CC05FF0499D8BC7D8EBE0C6DC2FDC09"
+	                     "E93765F3448235FB16AD09D98BBB3A0A"
+	                     "843372D33A318EE63DAE6998DA59EF34"
+	                     "B15C40A65B9B65ABF3CAF00000000000"
+	                     "00000000000000000000000000000000"
+	                     "00");
+	check_multiply_pow10("123456789ABCDEF0",
+	                     220,
+	                     "80ED0FD9A6C0F56A495F466320D34E22"
+	                     "507FAA83F0519E7FF909FDDBDA184682"
+	                     "BB70D38D43284C828A3681540722E550"
+	                     "960567BAB1C25389C1BE7705228BE8CC"
+	                     "AF3EBD382829DF000000000000000000"
+	                     "00000000000000000000000000000000"
+	                     "000000");
+	check_multiply_pow10("123456789ABCDEF0",
+	                     264,
+	                     "2421FD0F55C486D05211339D45EC2DC4"
+	                     "12AE7A64DDFE619DA81B73C069088D3E"
+	                     "83D7AA9F99B571815DE939A5275FB4A6"
+	                     "9D8930798C01FB96781B9D633BB59AD5"
+	                     "A7F322A7EC14154D1B8B5DF1718779A5"
+	                     "2291FE0F000000000000000000000000"
+	                     "00000000000000000000000000000000"
+	                     "00000000000");
+	check_multiply_pow10("123456789ABCDEF0",
+	                     308,
+	                     "A206620F35C83E9E780ECC07DCAF13BB"
+	                     "0A7EE2E213747914340BC172D783BA56"
+	                     "661E8DCFFD03C398BD66F5570F445AC6"
+	                     "737126283C64AE1A289B9D8BB4531033"
+	                     "8C3E34DE2D534187092ABA1F4706100E"
+	                     "ECF66D14059461A05A9BEBBCCBA0F693"
+	                     "F0000000000000000000000000000000"
+	                     "00000000000000000000000000000000"
+	                     "000000000000000");
+}
+
+static void
+check_divmod(const char*    lhs_hex,
+             const char*    rhs_hex,
+             const uint32_t expected_divisor,
+             const char*    expected_mod_hex)
+{
+	SerdBigint       lhs     = bigint_from_hex(lhs_hex);
+	const SerdBigint rhs     = bigint_from_hex(rhs_hex);
+	const uint32_t   divisor = serd_bigint_divmod(&lhs, &rhs);
+
+	assert(divisor == expected_divisor);
+	CHECK_HEXEQ(expected_mod_hex, &lhs);
+}
+
+static void
+test_divmod(void)
+{
+	check_divmod("A", "2", 5, "0");
+	check_divmod("B", "2", 5, "1");
+	check_divmod("C", "2", 6, "0");
+	check_divmod("A", "1234567890", 0, "A");
+	check_divmod("FFFFFFFF", "3", 0x55555555, "0");
+	check_divmod("12345678", "3789012", 5, "D9861E");
+	check_divmod("70000001", "1FFFFFFF", 3, "10000004");
+	check_divmod("28000000", "12A05F20", 2, "2BF41C0");
+	check_divmod("FFFFFFFFF", "FFFFFFFF", 16, "F");
+	check_divmod("100000000000001", "FFFFFFF", 0x10000001, "2");
+	check_divmod("40000000000002", "2FAF0800000000", 1, "1050F800000002");
+	check_divmod("40000000000000", "40000000000000", 1, "0");
+
+	check_divmod("43DE72C3DF858FC278A361EEB5A000000",
+	             "80000000000000000000000000000000",
+	             8,
+	             "3DE72C3DF858FC278A361EEB5A000000");
+
+	check_divmod("B5C5AF0376E3C800000",
+	             "43C33C1937564800000",
+	             2,
+	             "2E3F36D108373800000");
+
+
+	check_divmod("A0000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "000000000000000000000000000000",
+	             "20000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "000000000000000000000000000000",
+	             5,
+	             "0");
+
+	check_divmod("A0000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "000000000000000000000000000001",
+	             "20000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "000000000000000000000000000000",
+	             5,
+	             "1");
+
+	check_divmod("B6080000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "000000000000000000000000000000FF"
+	             "F",
+	             "A0000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "000000000000000000000000000000",
+	             0x1234,
+	             "FFF");
+
+	check_divmod("B6080000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "00000000000000000000000000000000"
+	             "0",
+	             "9FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+	             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+	             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+	             "FFFFFFFFFFFFFFFFFFFFFFFFFFF001",
+	             0x1234,
+	             "1232DCC");
+}
+
+static void
+check_compare(const char* lhs_hex, const char* rhs_hex, const int expected_cmp)
+{
+	const SerdBigint lhs = bigint_from_hex(lhs_hex);
+	const SerdBigint rhs = bigint_from_hex(rhs_hex);
+	const int        cmp = serd_bigint_compare(&lhs, &rhs);
+
+	assert(cmp == expected_cmp);
+
+	if (cmp) {
+		const int rcmp = serd_bigint_compare(&rhs, &lhs);
+		assert(rcmp == -cmp);
+	}
+}
+
+static void
+test_compare(void)
+{
+	check_compare("1", "1", 0);
+	check_compare("0", "1", -1);
+	check_compare("F", "FF", -1);
+	check_compare("F", "FFFFFFFFF", -1);
+	check_compare("10000000000000000", "10000000000000000", 0);
+	check_compare("10000000000000000", "10000000000000001", -1);
+	check_compare("FFFFFFFFFFFFFFFFF", "100000000000000000", -1);
+	check_compare("10000000000000000", "10000000000000001", -1);
+	check_compare("1234567890ABCDEF12345", "1234567890ABCDEF12345", 0);
+	check_compare("1234567890ABCDEF12345", "1234567890ABCDEF12346", -1);
+
+	const char* const huge = "123456789ABCDEF0123456789ABCDEF0"
+	                         "123456789ABCDEF0123456789ABCDEF0"
+	                         "123456789ABCDEF0123456789ABCDEF0"
+	                         "123456789ABCDEF0123456789ABCDEF0";
+
+	const char* const huger = "123456789ABCDEF0123456789ABCDEF0"
+	                          "123456789ABCDEF0123456789ABCDEF0"
+	                          "123456789ABCDEF0123456789ABCDEF0"
+	                          "123456789ABCDEF0123456789ABCDEF1";
+
+	check_compare(huge, huge, 0);
+	check_compare(huger, huger, 0);
+	check_compare(huge, huger, -1);
+}
+
+static void
+check_plus_compare(const char* l_hex,
+                   const char* p_hex,
+                   const char* c_hex,
+                   const int   expected_cmp)
+{
+	const SerdBigint l    = bigint_from_hex(l_hex);
+	const SerdBigint p    = bigint_from_hex(p_hex);
+	const SerdBigint c    = bigint_from_hex(c_hex);
+	const int        cmp  = serd_bigint_plus_compare(&l, &p, &c);
+	const int        rcmp = serd_bigint_plus_compare(&p, &l, &c);
+
+	assert(cmp == expected_cmp);
+	assert(rcmp == expected_cmp);
+}
+
+static void
+test_plus_compare(void)
+{
+	check_plus_compare("1", "0", "1", 0);
+	check_plus_compare("0", "0", "1", -1);
+	check_plus_compare("FFFFFFFFF", "F", "F", 1);
+	check_plus_compare("F", "F", "800000000", -1);
+	check_plus_compare("F", "F", "80000000000000000", -1);
+	check_plus_compare("800000000", "F", "80000000000000000", -1);
+	check_plus_compare("2D79883D20000", "2D79883D20000", "5AF3107A40000", 0);
+	check_plus_compare("20000000000000", "1", "20000000000000", +1);
+
+	check_plus_compare("0588A503282FE00000",
+	                   "0588A503282FE00000",
+	                   "0AD78EBC5AC6200000",
+	                   +1);
+
+	check_plus_compare("2F06018572BEADD1280000000",
+	                   "0204FCE5E3E25026110000000",
+	                   "4000000000000000000000000",
+	                   -1);
+
+	check_plus_compare("1234567890ABCDEF12345",
+	                   "000000000000000000001",
+	                   "1234567890ABCDEF12345",
+	                   +1);
+
+	check_plus_compare("1234567890ABCDEF12344",
+	                   "000000000000000000001",
+	                   "1234567890ABCDEF12345",
+	                   0);
+
+	check_plus_compare("123456789000000000000",
+	                   "0000000000ABCDEF12345",
+	                   "1234567890ABCDEF12345",
+	                   0);
+
+	check_plus_compare("123456789000000000000",
+	                   "0000000000ABCDEF12344",
+	                   "1234567890ABCDEF12345",
+	                   -1);
+
+	check_plus_compare("123456789000000000000",
+	                   "0000000000ABCDEF12346",
+	                   "1234567890ABCDEF12345",
+	                   1);
+
+	check_plus_compare("123456789100000000000",
+	                   "0000000000ABCDEF12345",
+	                   "1234567890ABCDEF12345",
+	                   1);
+
+	check_plus_compare("123456788900000000000",
+	                   "0000000000ABCDEF12345",
+	                   "1234567890ABCDEF12345",
+	                   -1);
+
+	check_plus_compare("12345678900000000000000000000",
+	                   "0000000000ABCDEF1234500000000",
+	                   "1234567890ABCDEF1234500000000",
+	                   0);
+
+	check_plus_compare("12345678900000000000000000000",
+	                   "0000000000ABCDEF1234400000000",
+	                   "1234567890ABCDEF1234500000000",
+	                   -1);
+
+	check_plus_compare("12345678900000000000000000000",
+	                   "0000000000ABCDEF1234600000000",
+	                   "1234567890ABCDEF1234500000000",
+	                   1);
+
+	check_plus_compare("12345678910000000000000000000",
+	                   "0000000000ABCDEF1234500000000",
+	                   "1234567890ABCDEF1234500000000",
+	                   1);
+	check_plus_compare("12345678890000000000000000000",
+	                   "0000000000ABCDEF1234500000000",
+	                   "1234567890ABCDEF1234500000000",
+	                   -1);
+
+	check_plus_compare("12345678900000000000000000000",
+	                   "000000000000000000ABCDEF12345",
+	                   "123456789000000000ABCDEF12345",
+	                   0);
+
+	check_plus_compare("12345678900000000000000000000",
+	                   "000000000000000000ABCDEF12346",
+	                   "123456789000000000ABCDEF12345",
+	                   1);
+
+	check_plus_compare("12345678900000000000000000000",
+	                   "000000000000000000ABCDEF12344",
+	                   "123456789000000000ABCDEF12345",
+	                   -1);
+
+	check_plus_compare("12345678900000000000000000000",
+	                   "000000000000000000ABCDEF12345",
+	                   "12345678900000ABCDEF123450000",
+	                   -1);
+
+	check_plus_compare("12345678900000000000000000000",
+	                   "000000000000000000ABCDEF12344",
+	                   "12345678900000ABCDEF123450000",
+	                   -1);
+
+	check_plus_compare("12345678900000000000000000000",
+	                   "000000000000000000ABCDEF12345",
+	                   "12345678900000ABCDEF123450001",
+	                   -1);
+
+	check_plus_compare("12345678900000000000000000000",
+	                   "00000000000000ABCDEF123460000",
+	                   "12345678900000ABCDEF123450000",
+	                   1);
+}
+
+static void
+check_pow10(const unsigned exponent, const char* expected)
+{
+	SerdBigint num;
+	serd_bigint_set_pow10(&num, exponent);
+	CHECK_HEXEQ(expected, &num);
+}
+
+static void
+test_set_pow10(void)
+{
+	check_pow10(0, "1");
+	check_pow10(1, "A");
+	check_pow10(2, "64");
+	check_pow10(5, "186A0");
+	check_pow10(8, "5F5E100");
+	check_pow10(16, "2386F26FC10000");
+	check_pow10(30, "C9F2C9CD04674EDEA40000000");
+	check_pow10(31, "7E37BE2022C0914B2680000000");
+}
+
+int
+main(void)
+{
+	test_set();
+	test_output();
+	test_left_shifted_bigit();
+	test_shift_left();
+	test_add_u32();
+	test_add();
+	test_subtract();
+	test_subtract_left_shifted();
+	test_multiply_u32();
+	test_multiply_u64();
+	test_multiply_pow10();
+	test_divmod();
+	test_compare();
+	test_plus_compare();
+	test_set_pow10();
+
+	return 0;
+}
diff --git a/wscript b/wscript
index 2943731d..55d1e5fb 100644
--- a/wscript
+++ b/wscript
@@ -168,6 +168,7 @@ def configure(conf):
 lib_headers = ['src/reader.h']
 
 lib_source = ['src/base64.c',
+              'src/bigint.c',
               'src/byte_sink.c',
               'src/byte_source.c',
               'src/cursor.c',
@@ -259,6 +260,7 @@ def build(bld):
         # Test programs
         for prog in [('serdi_static', 'src/serdi.c'),
                      ('base64_test', 'tests/base64_test.c'),
+                     ('bigint_test', 'tests/bigint_test.c'),
                      ('cursor_test', 'tests/cursor_test.c'),
                      ('decimal_test', 'tests/decimal_test.c'),
                      ('env_test', 'tests/env_test.c'),
@@ -692,6 +694,7 @@ def test(tst):
 
     with tst.group('Unit') as check:
         check(['./base64_test'])
+        check(['./bigint_test'])
         check(['./cursor_test'])
         check(['./decimal_test'])
         check(['./env_test'])