mpi/arith: optimize "highest bit" with GCC builtins.

* arith.c (highest_bit): On GCC, use __builtin_clz.

* mpi/mpi.c (s_highest_bit): Likewise.

2 files changed, 14 insertions, 2 deletions

diff --git a/arith.c b/arith.c
index f36c76ec..968d4a2c 100644
--- a/arith.c
+++ b/arith.c
@@ -268,7 +268,13 @@ val bignum_len(val num)
 
 int highest_bit(int_ptr_t n)
 {
-#if CHAR_BIT * SIZEOF_PTR == 64
+#if defined __GNUC__ && SIZEOF_PTR == SIZEOF_INT
+  return (n == 0) ? 0 : (CHAR_BIT * SIZEOF_PTR - __builtin_clz(n));
+#elif defined __GNUC__ && SIZEOF_PTR == SIZEOF_LONG
+  return (n == 0) ? 0 : (CHAR_BIT * SIZEOF_PTR - __builtin_clzl(n));
+#elif defined __GNUC__ && SIZEOF_PTR == SIZEOF_LONGLONG_T
+  return (n == 0) ? 0 : (CHAR_BIT * SIZEOF_PTR - __builtin_clzll(n));
+#elif CHAR_BIT * SIZEOF_PTR == 64
   if (n & 0x7FFFFFFF00000000) {
     if (n & 0x7FFF000000000000) {
       if (n & 0x7F00000000000000) {
diff --git a/mpi/mpi.c b/mpi/mpi.c
index 6aa905bb..579a43a6 100644
--- a/mpi/mpi.c
+++ b/mpi/mpi.c
@@ -2949,7 +2949,13 @@ void s_mp_clamp(mp_int *mp)
 
 static mp_size s_highest_bit(mp_digit n)
 {
-#if MP_DIGIT_SIZE == 8
+#if defined __GNUC__ && MP_DIGIT_SIZE == SIZEOF_INT
+  return (n == 0) ? 0 : (MP_DIGIT_BIT - __builtin_clz(n));
+#elif defined __GNUC__ && MP_DIGIT_SIZE == SIZEOF_LONG
+  return (n == 0) ? 0 : (MP_DIGIT_BIT - __builtin_clzl(n));
+#elif defined __GNUC__ && MP_DIGIT_SIZE == SIZEOF_LONGLONG_T
+  return (n == 0) ? 0 : (MP_DIGIT_BIT - __builtin_clzll(n));
+#elif MP_DIGIT_SIZE == 8
   if (n & 0xFFFFFFFF00000000) {
     if (n & 0xFFFF000000000000) {
       if (n & 0xFF00000000000000) {