aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/utils
diff options
context:
space:
mode:
authorJack Lloyd <[email protected]>2018-12-22 08:31:04 -0500
committerJack Lloyd <[email protected]>2018-12-22 08:31:04 -0500
commit108ccfa35f5d24e41c586c5b1184934f6f538d52 (patch)
tree3d48821506144c9a85f28d7176bf37554db8e575 /src/lib/utils
parent7c92530d47f9c7475f76e3d547480cb62c82a148 (diff)
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
Diffstat (limited to 'src/lib/utils')
-rw-r--r--src/lib/utils/bit_ops.h92
1 files changed, 50 insertions, 42 deletions
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