Add single DIGIT addition.

3 files changed, 186 insertions, 39 deletions

diff --git a/core/math/bigint/basic.odin b/core/math/bigint/basic.odin
index bf002e7d5..866124327 100644
--- a/core/math/bigint/basic.odin
+++ b/core/math/bigint/basic.odin
@@ -11,6 +11,7 @@ package bigint
 
 import "core:mem"
 import "core:intrinsics"
+import "core:fmt"
 
 /*
 	===========================
@@ -23,7 +24,7 @@ import "core:intrinsics"
 */
 add_two_ints :: proc(dest, a, b: ^Int) -> (err: Error) {
 	dest := dest; x := a; y := b;
-	_panic_if_uninitialized(a); _panic_if_uninitialized(b); _panic_if_uninitialized(dest);
+	assert_initialized(dest); assert_initialized(a); assert_initialized(b);
 
 	/*
 		Handle both negative or both positive.
@@ -52,9 +53,116 @@ add_two_ints :: proc(dest, a, b: ^Int) -> (err: Error) {
 
 	dest = a + digit;
 */
-add_digit :: proc(dest, a: ^int, digit: DIGIT) -> (err: Error) {
+add_digit :: proc(dest, a: ^Int, digit: DIGIT) -> (err: Error) {
+	dest := dest; x := a; digit := digit;
+	assert_initialized(dest); assert_initialized(a);
 
-	return .Unimplemented;
+	/*
+		Fast paths for destination and input Int being the same.
+	*/
+	if dest == a {
+		/*
+			Fast path for dest.digit[0] + digit fits in dest.digit[0] without overflow.
+		*/
+		if is_pos(dest) && (dest.digit[0] + digit < _DIGIT_MAX) {
+			dest.digit[0] += digit;
+			return .OK;
+		}
+		/*
+			Can be subtracted from dest.digit[0] without underflow.
+		*/
+		if is_neg(a) && (dest.digit[0] > digit) {
+			dest.digit[0] -= digit;
+			return .OK;
+		}
+	}
+
+	/*
+		Grow destination as required.
+	*/
+	err = grow(dest, a.used + 1);
+	if err != .OK {
+		return err;
+	}
+
+	/*
+		If `a` is negative and `|a|` >= `digit`, call `dest = |a| - digit`
+	*/
+	if is_neg(a) && (a.used > 1 || a.digit[0] >= digit) {
+		/*
+			Temporarily fix `a`'s sign.
+		*/
+		a.sign = .Zero_or_Positive;
+		/*
+			dest = |a| - digit
+		*/
+		err = sub(dest, a, digit);
+		/*
+			Restore sign and set `dest` sign.
+		*/
+		dest.sign = .Negative;
+		a.sign    = .Negative;
+
+		clamp(dest);
+
+		return err;
+	}
+
+	/*
+		Remember the currently used number of digits in `dest`.
+	*/
+	old_used := dest.used;
+
+	/*
+		If `a` is positive
+	*/
+	if is_pos(a) {
+		/*
+			Add digits, use `carry`.
+		*/
+		i: int;
+		carry := digit;
+		for i = 0; i < a.used; i += 1 {
+			dest.digit[i] = a.digit[i] + carry;
+			carry = dest.digit[i] >> _DIGIT_BITS;
+			dest.digit[i] &= _MASK;
+		}
+		/*
+			Set final carry.
+		*/
+		dest.digit[i] = carry;
+		/*
+			Set `dest` size.
+		*/
+		dest.used = a.used + 1;
+	} else {
+		/*
+			`a` was negative and |a| < digit.
+		*/
+		dest.used = 1;
+		/*
+			The result is a single DIGIT.
+		*/
+		dest.digit[0] = digit - a.digit[0] if a.used == 1 else digit;
+	}
+	/*
+		Sign is always positive.
+	*/
+	dest.sign = .Zero_or_Positive;
+
+	zero_count := old_used - dest.used;
+	/*
+		Zero remainder.
+	*/
+	if zero_count > 0 {
+		mem.zero_slice(dest.digit[dest.used:][:zero_count]);
+	}
+	/*
+		Adjust dest.used based on leading zeroes.
+	*/
+	clamp(dest);
+
+	return .OK;
 }
 
 add :: proc{add_two_ints, add_digit};
@@ -64,7 +172,7 @@ add :: proc{add_two_ints, add_digit};
 */
 sub_two_ints :: proc(dest, number, decrease: ^Int) -> (err: Error) {
 	dest := dest; x := number; y := decrease;
-	_panic_if_uninitialized(number); _panic_if_uninitialized(decrease); _panic_if_uninitialized(dest);
+	assert_initialized(number); assert_initialized(decrease); assert_initialized(dest);
 
 	if x.sign != y.sign {
 		/*
@@ -102,7 +210,7 @@ sub_two_ints :: proc(dest, number, decrease: ^Int) -> (err: Error) {
 
 	dest = number - decrease;
 */
-sub_digit :: proc(dest, number: ^int, decrease: DIGIT) -> (err: Error) {
+sub_digit :: proc(dest, number: ^Int, decrease: DIGIT) -> (err: Error) {
 
 	return .Unimplemented;
 }
@@ -121,7 +229,7 @@ sub :: proc{sub_two_ints, sub_digit};
 */
 _add :: proc(dest, a, b: ^Int) -> (err: Error) {
 	dest := dest; x := a; y := b;
-	_panic_if_uninitialized(a); _panic_if_uninitialized(b); _panic_if_uninitialized(dest);
+	assert_initialized(a); assert_initialized(b); assert_initialized(dest);
 
 	old_used, min_used, max_used, i: int;
 
@@ -202,7 +310,7 @@ _add :: proc(dest, a, b: ^Int) -> (err: Error) {
 */
 _sub :: proc(dest, number, decrease: ^Int) -> (err: Error) {
 	dest := dest; x := number; y := decrease;
-	_panic_if_uninitialized(number); _panic_if_uninitialized(decrease); _panic_if_uninitialized(dest);
+	assert_initialized(number); assert_initialized(decrease); assert_initialized(dest);
 
 	old_used := dest.used;
 	min_used := y.used;
diff --git a/core/math/bigint/example.odin b/core/math/bigint/example.odin
index 0b57d7a8d..0c88a6e1a 100644
--- a/core/math/bigint/example.odin
+++ b/core/math/bigint/example.odin
@@ -13,24 +13,43 @@ package bigint
 import "core:fmt"
 import "core:mem"
 
+print_int :: proc(a: ^Int, print_raw := false) -> string {
+	if print_raw {
+		return fmt.tprintf("%v", a);
+	}
+	sign := "-" if a.sign == .Negative else "";
+	if a.used <= 2 {
+		v := _WORD(a.digit[1]) << _DIGIT_BITS + _WORD(a.digit[0]);
+		return fmt.tprintf("%v%v", sign, v);
+	} else {
+		return fmt.tprintf("[%2d/%2d] %v%v", a.used, a.allocated, sign, a.digit[:a.used]);
+	}
+}
+
 demo :: proc() {
 	a, b, c: ^Int;
 	err:  Error;
 
 	a, err = init(21);
 	defer destroy(a);
-	fmt.printf("a: %v, err: %v\n\n", a, err);
+	fmt.printf("a: %v, err: %v\n\n", print_int(a), err);
 
-	b, err = init(-21);
+	b, err = init(21);
 	defer destroy(b);
 
-	fmt.printf("b: %v, err: %v\n\n", b, err);
+	fmt.printf("b: %v, err: %v\n\n", print_int(b), err);
 
 	c, err = init();
 	defer destroy(c);
+	fmt.printf("c: %v\n", print_int(c, true));
 
-	err = sub(c, a, b);
-	fmt.printf("c: %v, err: %v\n\n", c, err);
+	fmt.println("=== Add ===");
+	err = add(c, a, DIGIT(42));
+	// err = add(c, a, b);
+	fmt.printf("Error: %v\n", err);
+	fmt.printf("a: %v\n", print_int(a));
+	fmt.printf("b: %v\n", print_int(b));
+	fmt.printf("c: %v\n", print_int(c));
 }
 
 main :: proc() {
diff --git a/core/math/bigint/helpers.odin b/core/math/bigint/helpers.odin
index f96942954..170beb1bc 100644
--- a/core/math/bigint/helpers.odin
+++ b/core/math/bigint/helpers.odin
@@ -11,6 +11,7 @@ package bigint
 
 import "core:mem"
 import "core:intrinsics"
+import "core:fmt"
 
 /*
 	Deallocates the backing memory of an Int.
@@ -84,9 +85,9 @@ init :: proc{init_new, init_new_integer};
 	Helpers to set an `Int` to a specific value.
 */
 
-set_integer :: proc(a: ^Int, n: $T, minimize := false) where intrinsics.type_is_integer(T) {
+set_integer :: proc(a: ^Int, n: $T, minimize := false, loc := #caller_location) where intrinsics.type_is_integer(T) {
 	n := n;
-	_panic_if_uninitialized(a);
+	assert_initialized(a, loc);
 
 	a.used = 0;
 	a.sign = .Zero_or_Positive if n >= 0 else .Negative;
@@ -118,24 +119,45 @@ shrink :: proc(a: ^Int) -> (err: Error) {
 	return .OK;
 }
 
-grow :: proc(a: ^Int, n: int) -> (err: Error) {
-    _panic_if_uninitialized(a);
+grow :: proc(a: ^Int, n: int, allow_shrink := false) -> (err: Error) {
+	assert_initialized(a);
+	/*
+		By default, calling `grow` with `n` <= a.allocated won't resize.
+		With `allow_shrink` set to `true`, will call resize and shrink the `Int` as a result.
+	*/
+
+	/*
+		We need at least _MIN_DIGIT_COUNT or a.used digits, whichever is bigger.
+	*/
+	needed := max(_MIN_DIGIT_COUNT, a.used);
+	/*
+		The caller is asking for `n`. Let's be accomodating.
+	*/
+	needed  = max(needed, n);
+	/*
+		If `allow_shrink` == `false`, we need to needed >= `a.allocated`.
+	*/
+	if !allow_shrink {
+		needed = max(needed, a.allocated);
+	}
 
-    resize(&a.digit, n);
-    if len(a.digit) != n {
-    	return .Out_of_Memory;
-    }
+	if a.allocated != needed {
+		resize(&a.digit, needed);
+		if len(a.digit) != needed {
+			return .Out_of_Memory;
+		}
+	}
 
-    a.used = min(n, a.used);
-    a.allocated = n;
-    return .OK;
+	// a.used      = min(size, a.used);
+	a.allocated = needed;
+	return .OK;
 }
 
 /*
 	Clear `Int` and resize it to the default size.
 */
 clear :: proc(a: ^Int) -> (err: Error) {
-	_panic_if_uninitialized(a);
+	assert_initialized(a);
 
 	mem.zero_slice(a.digit[:]);
 	a.sign = .Zero_or_Positive;
@@ -149,11 +171,11 @@ clear :: proc(a: ^Int) -> (err: Error) {
 	Set the `Int` to 0 and optionally shrink it to the minimum backing size.
 */
 zero :: proc(a: ^Int, minimize := false) -> (err: Error) {
-	_panic_if_uninitialized(a);
+	assert_initialized(a);
 
-	mem.zero_slice(a.digit[:]);
 	a.sign = .Zero_or_Positive;
 	a.used = 0;
+	mem.zero_slice(a.digit[a.used:]);
 	if minimize {
 		return shrink(a);
 	}
@@ -165,12 +187,12 @@ zero :: proc(a: ^Int, minimize := false) -> (err: Error) {
 	Set the `Int` to 1 and optionally shrink it to the minimum backing size.
 */
 one :: proc(a: ^Int, minimize := false) -> (err: Error) {
-	_panic_if_uninitialized(a);
+	assert_initialized(a);
 
-	mem.zero_slice(a.digit[:]);
 	a.sign     = .Zero_or_Positive;
 	a.used     = 1;
 	a.digit[0] = 1;
+	mem.zero_slice(a.digit[a.used:]);
 	if minimize {
 		return shrink(a);
 	}
@@ -182,12 +204,12 @@ one :: proc(a: ^Int, minimize := false) -> (err: Error) {
 	Set the `Int` to -1 and optionally shrink it to the minimum backing size.
 */
 minus_one :: proc(a: ^Int, minimize := false) -> (err: Error) {
-	_panic_if_uninitialized(a);
+	assert_initialized(a);
 
-	mem.zero_slice(a.digit[:]);
 	a.sign     = .Negative;
 	a.used     = 1;
 	a.digit[0] = 1;
+	mem.zero_slice(a.digit[a.used:]);
 	if minimize {
 		return shrink(a);
 	}
@@ -199,27 +221,25 @@ minus_one :: proc(a: ^Int, minimize := false) -> (err: Error) {
 	Internal helpers.
 */
 
-_panic_if_uninitialized :: proc(a: ^Int, loc := #caller_location) {
-	if !is_initialized(a) {
-		panic("Int was not properly initialized.", loc);
-	}
+assert_initialized :: proc(a: ^Int, loc := #caller_location) {
+	assert(is_initialized(a), "`Int` was not properly initialized.", loc);
 }
 
 _zero_unused :: proc(a: ^Int) {
-	_panic_if_uninitialized(a);
+	assert_initialized(a);
 	if a.used < a.allocated {
 		mem.zero_slice(a.digit[a.used:]);
 	}
 }
 
 clamp :: proc(a: ^Int) {
-	_panic_if_uninitialized(a);
+	assert_initialized(a);
 	/*
 		Trim unused digits
-	 	This is used to ensure that leading zero digits are
-	 	trimmed and the leading "used" digit will be non-zero.
+		This is used to ensure that leading zero digits are
+		trimmed and the leading "used" digit will be non-zero.
 		Typically very fast.  Also fixes the sign if there
-	 	are no more leading digits.
+		are no more leading digits.
 	*/
 
 	for a.used > 0 && a.digit[a.used - 1] == 0 {