bigint: Working on `itoa` and `logn`.

6 files changed, 172 insertions, 28 deletions

diff --git a/core/math/bigint/basic.odin b/core/math/bigint/basic.odin
index a174799ba..c3b6395bb 100644
--- a/core/math/bigint/basic.odin
+++ b/core/math/bigint/basic.odin
@@ -7,6 +7,8 @@ package bigint
 	A BigInt implementation in Odin.
 	For the theoretical underpinnings, see Knuth's The Art of Computer Programming, Volume 2, section 4.3.
 	The code started out as an idiomatic source port of libTomMath, which is in the public domain, with thanks.
+
+	This file contains basic arithmetic operations like `add` and `sub`.
 */
 
 import "core:mem"
diff --git a/core/math/bigint/compare.odin b/core/math/bigint/compare.odin
index 1838d901e..9d48c4706 100644
--- a/core/math/bigint/compare.odin
+++ b/core/math/bigint/compare.odin
@@ -29,6 +29,29 @@ is_negative :: proc(a: ^Int) -> bool {
 }
 is_neg :: is_negative;
 
+is_even :: proc(a: ^Int) -> bool {
+	if is_initialized(a) {
+		if is_zero(a) {
+			return true;
+		}
+		if a.used > 0 && a.digit[0] & 1 == 0 {
+			return true;
+		}
+	}
+	return false;
+}
+
+is_odd :: proc(a: ^Int) -> bool {
+	if is_initialized(a) {
+		return !is_even(a);
+	}
+	return false;
+}
+
+is_power_of_two :: proc(x: int) -> bool {
+	return ((x) != 0) && (((x) & ((x) - 1)) == 0);
+}
+
 /*
 	Compare two `Int`s, signed.
 */
diff --git a/core/math/bigint/example.odin b/core/math/bigint/example.odin
index 145a8fc75..2d3f5e12d 100644
--- a/core/math/bigint/example.odin
+++ b/core/math/bigint/example.odin
@@ -41,43 +41,42 @@ _SQR_TOOM_CUTOFF,
 	fmt.println();
 }
 
-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;
+	a,  b,  c: ^Int;
+	as, bs, cs: string;
 	err:  Error;
 
 	a, err = init(512);
 	defer destroy(a);
-	fmt.printf("a: %v, err: %v\n\n", print_int(a), err);
+	as, err = itoa(a, 10);
+	fmt.printf("a: %v, err: %v\n\n", as, err);
+	delete(as);
 
 	b, err = init(42);
 	defer destroy(b);
-
-	fmt.printf("b: %v, err: %v\n\n", print_int(b), err);
+	bs, err = itoa(b, 10);
+	fmt.printf("b: %v, err: %v\n\n", bs, err);
+	delete(bs);
 
 	c, err = init();
 	defer destroy(c);
-	fmt.printf("c: %v\n", print_int(c, true));
+	cs, err = itoa(c, 10);
+	fmt.printf("c: %v\n", cs);
+	delete(cs);
 
 	fmt.println("=== Add ===");
 	err = sub(c, a, b);
-	// err = add(c, a, b);
+
 	fmt.printf("Error: %v\n", err);
-	fmt.printf("a: %v, bits: %v\n", print_int(a), count_bits(a));
-	fmt.printf("b: %v, bits: %v\n", print_int(b), count_bits(b));
-	fmt.printf("c: %v, bits: %v\n", print_int(c), count_bits(c));
+	as, err = itoa(a, 10);
+	bs, err = itoa(b, 10);
+	cs, err = itoa(c, 10);
+	fmt.printf("a: %v, bits: %v\n", as, count_bits(a));
+	fmt.printf("b: %v, bits: %v\n", bs, count_bits(b));
+	fmt.printf("c: %v, bits: %v\n", cs, count_bits(c));
+	delete(as); delete(bs); delete(cs);
+
+	fmt.println("log2:", log_n(a, 8));
 }
 
 main :: proc() {
diff --git a/core/math/bigint/helpers.odin b/core/math/bigint/helpers.odin
index 3d25230f2..869bd3e26 100644
--- a/core/math/bigint/helpers.odin
+++ b/core/math/bigint/helpers.odin
@@ -16,7 +16,6 @@ import "core:fmt"
 /*
 	Deallocates the backing memory of an Int.
 */
-
 destroy :: proc(a: ^Int, allocator_zeroes := false, free_int := true, loc := #caller_location) {
 	if !is_initialized(a) {
 		// Nothing to do.
@@ -37,7 +36,6 @@ destroy :: proc(a: ^Int, allocator_zeroes := false, free_int := true, loc := #ca
 /*
 	Creates and returns a new `Int`.
 */
-
 init_new :: proc(allocator_zeroes := true, allocator := context.allocator, size := _DEFAULT_DIGIT_COUNT) -> (a: ^Int, err: Error) {
 	/*
 		Allocating a new variable.
@@ -64,7 +62,6 @@ init_new :: proc(allocator_zeroes := true, allocator := context.allocator, size
 	Initialize from a signed or unsigned integer.
 	Inits a new `Int` and then calls the appropriate `set` routine.
 */
-
 init_new_integer :: proc(u: $T, minimize := false, allocator_zeroes := true, allocator := context.allocator) -> (a: ^Int, err: Error) where intrinsics.type_is_integer(T) {
 
 	n := _DEFAULT_DIGIT_COUNT;
@@ -84,7 +81,6 @@ 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, loc := #caller_location) where intrinsics.type_is_integer(T) {
 	n := n;
 	assert_initialized(a, loc);
@@ -109,7 +105,6 @@ set :: proc{set_integer};
 /*
 	Resize backing store.
 */
-
 shrink :: proc(a: ^Int) -> (err: Error) {
 	needed := max(_MIN_DIGIT_COUNT, a.used);
 
@@ -243,7 +238,6 @@ count_bits :: proc(a: ^Int) -> (count: int) {
 /*
 	Internal helpers.
 */
-
 assert_initialized :: proc(a: ^Int, loc := #caller_location) {
 	assert(is_initialized(a), "`Int` was not properly initialized.", loc);
 }
diff --git a/core/math/bigint/log.odin b/core/math/bigint/log.odin
new file mode 100644
index 000000000..fd8116b78
--- /dev/null
+++ b/core/math/bigint/log.odin
@@ -0,0 +1,46 @@
+package bigint
+
+/*
+	Copyright 2021 Jeroen van Rijn <nom@duclavier.com>.
+	Made available under Odin's BSD-2 license.
+
+	A BigInt implementation in Odin.
+	For the theoretical underpinnings, see Knuth's The Art of Computer Programming, Volume 2, section 4.3.
+	The code started out as an idiomatic source port of libTomMath, which is in the public domain, with thanks.
+*/
+
+log_n :: proc(a: ^Int, base: int) -> (log: int, err: Error) {
+	assert_initialized(a);
+	if is_neg(a) || is_zero(a) || base < 2 || DIGIT(base) > _DIGIT_MAX {
+		return -1, .Invalid_Input;
+	}
+
+	if is_power_of_two(base) {
+		return _log_power_of_two(a, base), .OK;
+	}
+
+   // if (MP_HAS(S_MP_LOG_D) && (a->used == 1)) {
+   //    *c = s_mp_log_d((mp_digit)base, a->dp[0]);
+   //    return MP_OKAY;
+   // }
+
+   // if (MP_HAS(S_MP_LOG)) {
+   //    return s_mp_log(a, (mp_digit)base, c);
+   // }
+
+	return -1, .Unimplemented;
+}
+
+/*
+	Returns the log2 of an `Int`, provided `base` is a power of two.
+	Don't call it if it isn't.
+*/
+_log_power_of_two :: proc(a: ^Int, base: int) -> (log: int) {
+	base := base;
+	y: int;
+	for y = 0; base & 1 == 0; {
+		y += 1;
+		base >>= 1;
+	}
+	return (count_bits(a) - 1) / y;
+}
diff --git a/core/math/bigint/radix.odin b/core/math/bigint/radix.odin
new file mode 100644
index 000000000..5bfb6b9a0
--- /dev/null
+++ b/core/math/bigint/radix.odin
@@ -0,0 +1,80 @@
+package bigint
+
+/*
+	Copyright 2021 Jeroen van Rijn <nom@duclavier.com>.
+	Made available under Odin's BSD-2 license.
+
+	A BigInt implementation in Odin.
+	For the theoretical underpinnings, see Knuth's The Art of Computer Programming, Volume 2, section 4.3.
+	The code started out as an idiomatic source port of libTomMath, which is in the public domain, with thanks.
+
+	This file contains radix conversions, `string_to_int` (atoi) and `int_to_string` (itoa).
+*/
+
+import "core:mem"
+import "core:intrinsics"
+import "core:fmt"
+import "core:strings"
+
+itoa :: proc(a: ^Int, radix: int, allocator := context.allocator) -> (res: string, err: Error) {
+	assert_initialized(a);
+
+	if radix < 2 || radix > 64 {
+		return strings.clone("", allocator), .Invalid_Input;
+	}
+
+	/*
+		Fast path for radixes that are a power of two.
+	*/
+	if radix & 1 == 0 {
+
+
+	}
+
+
+
+
+	fallback :: 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]);
+		   }
+	}
+	return strings.clone(fallback(a), allocator), .Unimplemented;
+}
+
+int_to_string :: itoa;
+
+
+radix_size :: proc(a: ^Int, base: int) -> (size: int, err: Error) {
+   // mp_err err;
+   // mp_int a_;
+   // int b;
+
+   // /* make sure the radix is in range */
+   // if ((radix < 2) || (radix > 64)) {
+   //    return MP_VAL;
+   // }
+
+   // if (mp_iszero(a)) {
+   //    *size = 2;
+   //    return MP_OKAY;
+   // }
+
+   // a_ = *a;
+   // a_.sign = MP_ZPOS;
+   // if ((err = mp_log_n(&a_, radix, &b)) != MP_OKAY) {
+   //    return err;
+   // }
+
+   // /* mp_ilogb truncates to zero, hence we need one extra put on top and one for `\0`. */
+   // *size = (size_t)b + 2U + (mp_isneg(a) ? 1U : 0U);
+
+   return size, .OK;
+}
\ No newline at end of file