src/big_int.cpp: Use square-multiply for exponentiation

For utterly unrealistic constant sizes, this still crashes on my system,
but it crashes fast due to the OOM killer, and people using rediculously
large exponents get what they deserve.

1 files changed, 14 insertions, 3 deletions

diff --git a/src/big_int.cpp b/src/big_int.cpp
index 83235483c..8e476f090 100644
--- a/src/big_int.cpp
+++ b/src/big_int.cpp
@@ -62,6 +62,7 @@ gb_internal void big_int_shl    (BigInt *dst, BigInt const *x, BigInt const *y);
 gb_internal void big_int_shr    (BigInt *dst, BigInt const *x, BigInt const *y);
 gb_internal void big_int_mul    (BigInt *dst, BigInt const *x, BigInt const *y);
 gb_internal void big_int_mul_u64(BigInt *dst, BigInt const *x, u64 y);
+gb_internal void big_int_exp_u64(BigInt *dst, BigInt const *x, u64 y, bool *success);
 
 gb_internal void big_int_quo_rem(BigInt const *x, BigInt const *y, BigInt *q, BigInt *r);
 gb_internal void big_int_quo    (BigInt *z, BigInt const *x, BigInt const *y);
@@ -250,9 +251,7 @@ gb_internal void big_int_from_string(BigInt *dst, String const &s, bool *success
 			exp *= 10;
 			exp += v;
 		}
-		for (u64 x = 0; x < exp; x++) {
-			big_int_mul_eq(dst, &b);
-		}
+		big_int_exp_u64(dst, &b, exp, success);
 	}
 
 	if (is_negative) {
@@ -328,6 +327,18 @@ gb_internal void big_int_mul_u64(BigInt *dst, BigInt const *x, u64 y) {
 	big_int_dealloc(&d);
 }
 
+gb_internal void big_int_exp_u64(BigInt *dst, BigInt const *x, u64 y, bool *success) {
+	if (y > INT_MAX) {
+		*success = false;
+		return;
+	}
+
+	// Note: The cutoff for square-multiply being faster than the naive
+	// for loop is when exp > 4, but it probably isn't worth adding
+	// a fast path.
+	mp_err err = mp_expt_n(x, int(y), dst);
+	*success = err == MP_OKAY;
+}
 
 gb_internal void big_int_mul(BigInt *dst, BigInt const *x, BigInt const *y) {
 	mp_mul(x, y, dst);