big: `itoa` now works for arbitrary radixes.

4 files changed, 202 insertions, 80 deletions

diff --git a/core/math/big/basic.odin b/core/math/big/basic.odin
index bd1d25bb9..0807581b5 100644
--- a/core/math/big/basic.odin
+++ b/core/math/big/basic.odin
@@ -666,7 +666,7 @@ int_div :: proc(quotient, remainder, numerator, denominator: ^Int) -> (err: Erro
 	if err = clear_if_uninitialized(numerator);			err != .None { return err; }

 	if err = clear_if_uninitialized(denominator);		err != .None { return err; }

 

-	return _int_div(quotient, remainder, numerator, denominator);

+	return _int_div_small(quotient, remainder, numerator, denominator);

 }

 div :: proc{ int_div, };

 

@@ -1077,4 +1077,90 @@ _int_div_small :: proc(quotient, remainder, numerator, denominator: ^Int) -> (er
 	}

 	destroy(ta, tb, tq, q);

 	return err;

+}

+

+/*

+	Single digit division (based on routine from MPI).

+*/

+_int_div_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT) -> (remainder: int, err: Error) {

+	q := &Int{};

+	ix: int;

+

+	/*

+		Cannot divide by zero.

+	*/

+	if denominator == 0 {

+		return 0, .Division_by_Zero;

+	}

+

+	/*

+		Quick outs.

+	*/

+	if denominator == 1 || numerator.used == 0 {

+		err = .None;

+		if quotient != nil {

+			err = copy(quotient, numerator);

+		}

+		return 0, err;

+	}

+	/*

+		Power of two?

+	*/

+	if denominator == 2 {

+		if odd, _ := is_odd(numerator); odd {

+			remainder = 1;

+		}

+		if quotient == nil {

+			return remainder, .None;

+		}

+		return remainder, shr(quotient, numerator, 1);

+	}

+

+	if is_power_of_two(int(denominator)) {

+		ix = 1;

+		for ix < _DIGIT_BITS && denominator != (1 << uint(ix)) {

+			ix += 1;

+		}

+		remainder = int(numerator.digit[0]) & ((1 << uint(ix)) - 1);

+		if quotient == nil {

+			return remainder, .None;

+		}

+

+		return remainder, shr(quotient, numerator, int(ix));

+	}

+

+	/*

+		Three?

+	*/

+	if denominator == 3 {

+		return _int_div_3(quotient, numerator);

+	}

+

+	/*

+		No easy answer [c'est la vie].  Just division.

+	*/

+	if err = grow(q, numerator.used); err != .None { return 0, err; }

+

+	q.used = numerator.used;

+	q.sign = numerator.sign;

+

+	w := _WORD(0);

+

+	for ix = numerator.used - 1; ix >= 0; ix -= 1 {

+		t := DIGIT(0);

+		w = (w << _WORD(_DIGIT_BITS) | _WORD(numerator.digit[ix]));

+		if w >= _WORD(denominator) {

+			t = DIGIT(w / _WORD(denominator));

+			w -= _WORD(t) * _WORD(denominator);

+		}

+		q.digit[ix] = t;

+	}

+	remainder = int(w);

+

+	if quotient != nil {

+		clamp(q);

+		swap(q, quotient);

+	}

+	destroy(q);

+	return remainder, .None;

 }
\ No newline at end of file
diff --git a/core/math/big/example.odin b/core/math/big/example.odin
index ca3fc5531..6ceeb4d26 100644
--- a/core/math/big/example.odin
+++ b/core/math/big/example.odin
@@ -43,47 +43,44 @@ _SQR_TOOM_CUTOFF,
 print :: proc(name: string, a: ^Int, base := i8(16)) {
 	as, err := itoa(a, base);
 	defer delete(as);
-	if err == .None {
-		cb, _ := count_bits(a);
-		fmt.printf("%v (base: %v, bits used: %v): %v\n", name, base, cb, as);
-	} else {
-		fmt.printf("%v (error: %v): %v\n", name, err, a);
+	cb, _ := count_bits(a);
+	fmt.printf("%v (base: %v, bits used: %v): %v\n", name, base, cb, as);
+	if err != .None {
+		fmt.printf("%v (error: %v | %v)\n", name, err, a);
 	}
+	
+}
+
+num_threads :: 16;
+global_traces_indexes := [num_threads]u16{};
+@thread_local local_traces_index : ^u16;
+
+init_thread_tracing :: proc(thread_id: u8) {
+    
+    fmt.printf("%p\n", &global_traces_indexes[thread_id]);
+    fmt.printf("%p\n", local_traces_index);
 }
 
 demo :: proc() {
 	err: Error;
-	i:   int;
+
 	destination, source, quotient, remainder, numerator, denominator := &Int{}, &Int{}, &Int{}, &Int{}, &Int{}, &Int{};
 	defer destroy(destination, source, quotient, remainder, numerator, denominator);
 
-	err = set(numerator,   15625);
-	err = set(denominator,     3);
-
-	print("numerator  ", numerator,   10);
-	print("denominator", denominator, 10);
-
-	i, err = _int_div_3(quotient, numerator);
-
-	print("quotient   ", quotient,    10);
-	fmt.println("remainder  ", i);
-	fmt.println("error", err);
-
-	fmt.println(); fmt.println();
-
-	err = set (numerator,   15625);
-	err = set (denominator,     3);
+	err = set (numerator,   2);
+	err = set (denominator, 3);
 	err = zero(quotient);
+	err = zero(remainder);
 
-	print("numerator  ", numerator,   10);
-	print("denominator", denominator, 10);
-
-	err = _int_div_small(quotient, remainder, numerator, denominator);
-
-	print("quotient   ", quotient,    10);
-	print("remainder  ", remainder,   10);
-
-
+	err = pow(numerator, numerator, 260);
+	if err != .None {
+		fmt.printf("Error: %v\n", err);
+	} else {
+		print("numerator  ", numerator,   16);
+		print("denominator", denominator, 10);
+		print("quotient   ", quotient,    10);
+		print("remainder  ", remainder,   10);
+	}
 }
 
 main :: proc() {
diff --git a/core/math/big/log.odin b/core/math/big/log.odin
index 3bd1f4f25..42f6ea6e3 100644
--- a/core/math/big/log.odin
+++ b/core/math/big/log.odin
@@ -217,8 +217,6 @@ int_log_digit :: proc(a: DIGIT, base: DIGIT) -> (log: int, err: Error) {
 _int_log :: proc(a: ^Int, base: DIGIT) -> (res: int, err: Error) {

 	bracket_low, bracket_high, bracket_mid, t, bi_base := &Int{}, &Int{}, &Int{}, &Int{}, &Int{};

 

-	cnt := 0;

-

 	ic, _ := cmp(a, base);

 	if ic == -1 || ic == 0 {

 		return 1 if ic == 0 else 0, .None;

@@ -256,12 +254,6 @@ _int_log :: proc(a: ^Int, base: DIGIT) -> (res: int, err: Error) {
 			destroy(bracket_low, bracket_high, bracket_mid, t, bi_base);

 			return -1, err;

 	 	}

-

-	 	cnt += 1;

-	 	if cnt == 7 {

-		 	destroy(bracket_low, bracket_high, bracket_mid, t, bi_base);

-			return -2, .Max_Iterations_Reached;

-	 	}

 	}

 

 	for (high - low) > 1 {

diff --git a/core/math/big/radix.odin b/core/math/big/radix.odin
index 2dba5d8b4..300ce12b9 100644
--- a/core/math/big/radix.odin
+++ b/core/math/big/radix.odin
@@ -12,8 +12,7 @@ package big
 */
 
 import "core:intrinsics"
-import "core:fmt"
-import "core:strings"
+import "core:mem"
 
 /*
 	This version of `itoa` allocates one behalf of the caller. The caller must free the string.
@@ -41,12 +40,7 @@ itoa_string :: proc(a: ^Int, radix := i8(-1), zero_terminate := false, allocator
 		Exit if calculating the size returned an error.
 	*/
 	if size, err = radix_size(a, radix, zero_terminate); err != .None {
-		f := strings.clone(fallback(a), allocator);
-		if zero_terminate {
-			c := strings.clone_to_cstring(f);
-			return string(c), err;
-		}
-		return f, err;
+		return "", err;
 	}
 
 	/*
@@ -58,28 +52,9 @@ itoa_string :: proc(a: ^Int, radix := i8(-1), zero_terminate := false, allocator
 		Write the digits out into the buffer.
 	*/
 	written: int;
-	if written, err = itoa_raw(a, radix, buffer, size, zero_terminate); err == .None {
-		return string(buffer[:written]), .None;
-	}
+	written, err = itoa_raw(a, radix, buffer, size, zero_terminate);
 
-	/*
-		For now, delete the buffer and fall back to the below on failure.
-	*/
-	delete(buffer);
-
-	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] %v%v", a.used, sign, a.digit[:a.used]);
-		   }
-	}
-	return strings.clone(fallback(a), allocator), .Unimplemented;
+	return string(buffer[:written]), err;
 }
 
 /*
@@ -166,7 +141,15 @@ itoa_raw :: proc(a: ^Int, radix: i8, buffer: []u8, size := int(-1), zero_termina
 			buffer[available] = '-';
 		}
 
-		return len(buffer) - available, .None;
+		/*
+			If we overestimated the size, we need to move the buffer left.
+		*/
+		written = len(buffer) - available;
+		if written < size {
+			diff := size - written;
+			mem.copy(&buffer[0], &buffer[diff], written);
+		}
+		return written, .None;
 	}
 
 	/*
@@ -190,11 +173,17 @@ itoa_raw :: proc(a: ^Int, radix: i8, buffer: []u8, size := int(-1), zero_termina
 			available -= 1;
 			buffer[available] = '-';
 		}
-		return len(buffer) - available, .None;
+
+		/*
+			If we overestimated the size, we need to move the buffer left.
+		*/
+		written = len(buffer) - available;
+		if written < size {
+			diff := size - written;
+			mem.copy(&buffer[0], &buffer[diff], written);
+		}
+		return written, .None;
 	}
-	/*
-		At least 3 DIGITs are in use if we made it this far.
-	*/
 
 	/*
 		Fast path for radixes that are a power of two.
@@ -225,10 +214,18 @@ itoa_raw :: proc(a: ^Int, radix: i8, buffer: []u8, size := int(-1), zero_termina
 			buffer[available] = '-';
 		}
 
-		return len(buffer) - available, .None;
+		/*
+			If we overestimated the size, we need to move the buffer left.
+		*/
+		written = len(buffer) - available;
+		if written < size {
+			diff := size - written;
+			mem.copy(&buffer[0], &buffer[diff], written);
+		}
+		return written, .None;
 	}
 
-	return -1, .Unimplemented;
+	return _itoa_raw_full(a, radix, buffer, zero_terminate);
 }
 
 itoa :: proc{itoa_string, itoa_raw};
@@ -236,7 +233,7 @@ int_to_string  :: itoa;
 int_to_cstring :: itoa_cstring;
 
 /*
-	We size for `string`, not `cstring`.
+	We size for `string` by default.
 */
 radix_size :: proc(a: ^Int, radix: i8, zero_terminate := false) -> (size: int, err: Error) {
 	a := a;
@@ -270,8 +267,7 @@ radix_size :: proc(a: ^Int, radix: i8, zero_terminate := false) -> (size: int, e
 	/*
 		log truncates to zero, so we need to add one more, and one for `-` if negative.
 	*/
-	n, _ := is_neg(a);
-	size += 2 if n else 1;
+	size += 2 if a.sign == .Negative else 1;
 	size += 1 if zero_terminate else 0;
 	return size, .None;
 }
@@ -289,4 +285,55 @@ RADIX_TABLE_REVERSE := [80]u8{
    0xff, 0xff, 0xff, 0xff, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, /* ]^_`abcdef */
    0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, /* ghijklmnop */
    0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, /* qrstuvwxyz */
-};
\ No newline at end of file
+};
+
+/*
+	Stores a bignum as a ASCII string in a given radix (2..64)
+	The buffer must be appropriately sized. This routine doesn't check.
+*/
+_itoa_raw_full :: proc(a: ^Int, radix: i8, buffer: []u8, zero_terminate := false) -> (written: int, err: Error) {
+	temp, denominator := &Int{}, &Int{};
+
+	if err = copy(temp, a); err != .None { return 0, err; }
+	if err = set(denominator, radix); err != .None { return 0, err; }
+
+	available := len(buffer);
+	if zero_terminate {
+		available -= 1;
+		buffer[available] = 0;
+	}
+
+	if a.sign == .Negative {
+		temp.sign = .Zero_or_Positive;
+	}
+
+	remainder: int;
+	for {
+		if remainder, err = _int_div_digit(temp, temp, DIGIT(radix)); err != .None {
+			destroy(temp, denominator);
+			return len(buffer) - available, err;
+		}
+		available -= 1;
+		buffer[available] = RADIX_TABLE[remainder];
+		if temp.used == 0 {
+			break;
+		}
+	}
+
+	if a.sign == .Negative {
+		available -= 1;
+		buffer[available] = '-';
+	}
+
+	destroy(temp, denominator);
+
+	/*
+		If we overestimated the size, we need to move the buffer left.
+	*/
+	written = len(buffer) - available;
+	if written < len(buffer) {
+		diff := len(buffer) - written;
+		mem.copy(&buffer[0], &buffer[diff], written);
+	}
+	return written, .None;
+}
\ No newline at end of file