bigint: `itoa` support for arbitrary precision if `is_power_of_two(radix)`

4 files changed, 82 insertions, 16 deletions

diff --git a/core/math/bigint/bigint.odin b/core/math/bigint/bigint.odin
index 8f6cb1cf7..50934e429 100644
--- a/core/math/bigint/bigint.odin
+++ b/core/math/bigint/bigint.odin
@@ -111,6 +111,7 @@ _DIGIT_TYPE_BITS :: 8 * size_of(DIGIT);
 _WORD_TYPE_BITS  :: 8 * size_of(_WORD);
 
 _DIGIT_BITS      :: _DIGIT_TYPE_BITS - 4;
+_WORD_BITS       :: 2 * _DIGIT_BITS;
 
 _MASK            :: (DIGIT(1) << DIGIT(_DIGIT_BITS)) - DIGIT(1);
 _DIGIT_MAX       :: _MASK;
diff --git a/core/math/bigint/example.odin b/core/math/bigint/example.odin
index 930c11b7f..38290369d 100644
--- a/core/math/bigint/example.odin
+++ b/core/math/bigint/example.odin
@@ -46,37 +46,39 @@ demo :: proc() {
 	as, bs, cs: string;
 	err:  Error;
 
-	a, err = init(-512);
+	a, err = init();
+	a.digit[2] = 512;
+	a.used = 3;
 	defer destroy(a);
-	as, err = itoa(a);
+	as, err = itoa(a, 16);
 	fmt.printf("a: %v, err: %v\n\n", as, err);
 	delete(as);
 
 	b, err = init(42);
 	defer destroy(b);
-	bs, err = itoa(b);
+	bs, err = itoa(b, 16);
 	fmt.printf("b: %s, err: %v\n\n", bs, err);
 	delete(bs);
 
 	c, err = init(-4);
 	defer destroy(c);
-	cs, err = itoa(c);
+	cs, err = itoa(c, 16);
 	fmt.printf("c: %s, err: %v\n\n", cs, err);
 	delete(cs);
 
-	cstr: cstring;
-	defer delete(cstr);
+	// cstr: cstring;
+	// defer delete(cstr);
 
-	cstr, err = itoa_cstring(a);
-	fmt.printf("cstring: %v, err: %v\n\n", cstr, err);
+	// cstr, err = itoa_cstring(a);
+	// fmt.printf("cstring: %v, err: %v\n\n", cstr, err);
 
 	fmt.println("=== Add ===");
 	err = sub(c, a, b);
 
 	fmt.printf("Error: %v\n", err);
-	as, err = itoa(a, 8);
-	bs, err = itoa(b);
-	cs, err = itoa(c);
+	as, err = itoa(a, 16);
+	bs, err = itoa(b, 16);
+	cs, err = itoa(c, 16);
 	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));
diff --git a/core/math/bigint/helpers.odin b/core/math/bigint/helpers.odin
index 3b6e108d7..a96eabb2c 100644
--- a/core/math/bigint/helpers.odin
+++ b/core/math/bigint/helpers.odin
@@ -103,6 +103,39 @@ set_integer :: proc(a: ^Int, n: $T, minimize := false, loc := #caller_location)
 set :: proc{set_integer};
 
 /*
+	Helpers to extract values from the `Int`.
+*/
+extract_bit :: proc(a: ^Int, bit_offset: int) -> (bit: DIGIT, err: Error) {
+	limb := bit_offset / _DIGIT_BITS;
+	if limb < 0 || limb >= a.used {
+		return 0, .Invalid_Input;
+	}
+
+	i := DIGIT(1 << DIGIT((bit_offset % _DIGIT_BITS)));
+
+	return 1 if ((a.digit[limb] & i) != 0) else 0, .OK;
+}
+
+extract_bits :: proc(a: ^Int, offset, count: int) -> (res: _WORD, err: Error) {
+	if count > _WORD_BITS || count < 1 {
+		return 0, .Invalid_Input;
+	}
+
+	v: DIGIT;
+	e: Error;
+	for shift := 0; shift < count; shift += 1 {
+		o   := offset + shift;
+		v, e = extract_bit(a, o);
+		if e != .OK {
+			break;
+		}
+		res = res + _WORD(v) << uint(shift);
+	}
+
+	return res, e;
+}
+
+/*
 	Resize backing store.
 */
 shrink :: proc(a: ^Int) -> (err: Error) {
diff --git a/core/math/bigint/radix.odin b/core/math/bigint/radix.odin
index f939aa7da..7cacdbc56 100644
--- a/core/math/bigint/radix.odin
+++ b/core/math/bigint/radix.odin
@@ -37,15 +37,16 @@ itoa_string :: proc(a: ^Int, radix := i8(-1), zero_terminate := false, allocator
 	*/
 	size: int;
 	size, err = radix_size(a, radix, zero_terminate);
-
 	/*
 		Exit if calculating the size returned an error.
 	*/
 	if err != .OK {
+		f := strings.clone(fallback(a), allocator);
 		if zero_terminate {
-			return string(cstring("")), err;
+			c := strings.clone_to_cstring(f);
+			return string(c), err;
 		}
-		return "", err;
+		return f, err;
 	}
 
 	/*
@@ -149,7 +150,6 @@ itoa_raw :: proc(a: ^Int, radix: i8, buffer: []u8, size := int(-1), zero_termina
 			available -= 1;
 			buffer[available] = 0;
 		}
-
 		available -= 1;
 		buffer[available] = RADIX_TABLE[a.digit[0]];
 
@@ -184,13 +184,40 @@ itoa_raw :: proc(a: ^Int, radix: i8, buffer: []u8, size := int(-1), zero_termina
 		}
 		return len(buffer) - available, .OK;
 	}
+	/*
+		At least 3 DIGITs are in use if we made it this far.
+	*/
 
 	/*
 		Fast path for radixes that are a power of two.
 	*/
 	if is_power_of_two(int(radix)) {
+		if zero_terminate {
+			available -= 1;
+			buffer[available] = 0;
+		}
 
-		// return len(buffer), .OK;
+		mask  := _WORD(radix - 1);
+		shift := int(log_n(DIGIT(radix), 2));
+		count := int(count_bits(a));
+		digit: _WORD;
+
+		for offset := 0; offset < count; offset += 4 {
+			bits_to_get := int(min(count - offset, shift));
+			digit, err  := extract_bits(a, offset, bits_to_get);
+			if err != .OK {
+				return len(buffer) - available, .Invalid_Input;
+			}
+			available -= 1;
+			buffer[available] = RADIX_TABLE[digit];
+		}
+
+		if is_neg(a) {
+			available -= 1;
+			buffer[available] = '-';
+		}
+
+		return len(buffer) - available, .OK;
 	}
 
 	return -1, .Unimplemented;
@@ -209,6 +236,9 @@ radix_size :: proc(a: ^Int, radix: i8, zero_terminate := false) -> (size: int, e
 	}
 
  	if is_zero(a) {
+ 		if zero_terminate {
+ 			return 2, .OK;
+ 		}
  		return 1, .OK;
  	}