Make ctz and high_bit faster and const-time-ish

They get compiled as const-time on x86-64 with GCC but I don't think
this can be totally relied on. But it is anyway an improvement.

And, faster, because we compute it recursively

3 files changed, 51 insertions, 48 deletions

diff --git a/src/lib/asn1/der_enc.cpp b/src/lib/asn1/der_enc.cpp
index 99b833d27..366af59f1 100644
--- a/src/lib/asn1/der_enc.cpp
+++ b/src/lib/asn1/der_enc.cpp
@@ -32,7 +32,7 @@ void encode_tag(std::vector<uint8_t>& encoded_tag,
       }
    else
       {
-      size_t blocks = high_bit(type_tag) + 6;
+      size_t blocks = high_bit(static_cast<uint32_t>(type_tag)) + 6;
       blocks = (blocks - (blocks % 7)) / 7;
 
       BOTAN_ASSERT_NOMSG(blocks > 0);
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index d8861fe65..75c87e5b6 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -279,12 +279,7 @@ size_t BigInt::top_bits_free() const
    const size_t words = sig_words();
 
    const word top_word = word_at(words - 1);
-
-   // Need to unpoison due to high_bit not being const time
-   CT::unpoison(top_word);
-
    const size_t bits_used = high_bit(top_word);
-
    return BOTAN_MP_WORD_BITS - bits_used;
    }
 
diff --git a/src/lib/utils/bit_ops.h b/src/lib/utils/bit_ops.h
index c6cce8ae2..f32250b9c 100644
--- a/src/lib/utils/bit_ops.h
+++ b/src/lib/utils/bit_ops.h
@@ -36,10 +36,23 @@ inline constexpr bool is_power_of_2(T arg)
 template<typename T>
 inline size_t high_bit(T n)
    {
-   for(size_t i = 8*sizeof(T); i > 0; --i)
-      if((n >> (i - 1)) & 0x01)
-         return i;
-   return 0;
+   size_t hb = 0;
+
+   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
+      {
+      /*
+      * The != 0 expression is not necessarily going to be const time,
+      * it will depend on the compiler and arch. GCC compiles this
+      * function to straight line code on x86-64, Aarch64 and ARM.
+      */
+      const size_t z = s * ((n >> s) != 0);
+      hb += z;
+      n >>= z;
+      }
+
+   hb += n;
+
+   return hb;
    }
 
 /**
@@ -79,48 +92,23 @@ inline size_t significant_bytes(T n)
 template<typename T>
 inline size_t ctz(T n)
    {
-   for(size_t i = 0; i != 8*sizeof(T); ++i)
-      if((n >> i) & 0x01)
-         return i;
-   return 8*sizeof(T);
-   }
-
-#if defined(BOTAN_BUILD_COMPILER_IS_GCC) || defined(BOTAN_BUILD_COMPILER_IS_CLANG)
-
-template<>
-inline size_t ctz(uint32_t n)
-   {
-   if(n == 0)
-      return 32;
-   return __builtin_ctz(n);
-   }
-
-template<>
-inline size_t ctz(uint64_t n)
-   {
-   if(n == 0)
-      return 64;
-   return __builtin_ctzll(n);
-   }
+   /*
+   * If n == 0 then this function will compute 8*sizeof(T)-1, so
+   * initialize lb to 1 if n == 0 to produce the expected result.
+   */
+   size_t lb = (n == 0);
 
-template<>
-inline size_t high_bit(uint32_t x)
-   {
-   if(x == 0)
-      return 0;
-   return (32 - __builtin_clz(x));
-   }
+   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
+      {
+      const T mask = (static_cast<T>(1) << s) - 1;
+      const T n_bits = (n & mask) == 0;
+      lb += s * n_bits;
+      n >>= s * n_bits;
+      }
 
-template<>
-inline size_t high_bit(uint64_t x)
-   {
-   if(x == 0)
-      return 0;
-   return (64 - __builtin_clzll(x));
+   return lb;
    }
 
-#endif
-
 template<typename T>
 size_t ceil_log2(T x)
    {
@@ -139,6 +127,26 @@ size_t ceil_log2(T x)
    return result;
    }
 
+#if defined(BOTAN_BUILD_COMPILER_IS_GCC) || defined(BOTAN_BUILD_COMPILER_IS_CLANG)
+
+template<>
+inline size_t ctz(uint32_t n)
+   {
+   if(n == 0)
+      return 32;
+   return __builtin_ctz(n);
+   }
+
+template<>
+inline size_t ctz(uint64_t n)
+   {
+   if(n == 0)
+      return 64;
+   return __builtin_ctzll(n);
+   }
+
+#endif
+
 }
 
 #endif