aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/lib/modes/aead/ocb/ocb.cpp6
-rw-r--r--src/lib/utils/bit_ops.h57
-rw-r--r--src/lib/x509/x509_ext.cpp2
-rw-r--r--src/tests/test_utils.cpp50
4 files changed, 75 insertions, 40 deletions
diff --git a/src/lib/modes/aead/ocb/ocb.cpp b/src/lib/modes/aead/ocb/ocb.cpp
index 866527800..b25abbe6a 100644
--- a/src/lib/modes/aead/ocb/ocb.cpp
+++ b/src/lib/modes/aead/ocb/ocb.cpp
@@ -69,7 +69,7 @@ class L_computer final
// ntz(4*i+2) == 1
// ntz(4*i+3) == 0
block_index += 4;
- const size_t ntz4 = ctz<uint32_t>(static_cast<uint32_t>(block_index));
+ const size_t ntz4 = var_ctz32(static_cast<uint32_t>(block_index));
xor_buf(offsets, m_offset.data(), L0.data(), m_BS);
offsets += m_BS;
@@ -91,7 +91,7 @@ class L_computer final
for(size_t i = 0; i != blocks; ++i)
{ // could be done in parallel
- const size_t ntz = ctz<uint32_t>(static_cast<uint32_t>(block_index + i + 1));
+ const size_t ntz = var_ctz32(static_cast<uint32_t>(block_index + i + 1));
xor_buf(m_offset.data(), get(ntz).data(), m_BS);
copy_mem(offsets, m_offset.data(), m_BS);
offsets += m_BS;
@@ -136,7 +136,7 @@ secure_vector<uint8_t> ocb_hash(const L_computer& L,
for(size_t i = 0; i != ad_blocks; ++i)
{
// this loop could run in parallel
- offset ^= L.get(ctz<uint32_t>(static_cast<uint32_t>(i+1)));
+ offset ^= L.get(var_ctz32(static_cast<uint32_t>(i+1)));
buf = offset;
xor_buf(buf.data(), &ad[BS*i], BS);
cipher.encrypt(buf);
diff --git a/src/lib/utils/bit_ops.h b/src/lib/utils/bit_ops.h
index cab714146..553dae4a2 100644
--- a/src/lib/utils/bit_ops.h
+++ b/src/lib/utils/bit_ops.h
@@ -69,21 +69,6 @@ inline size_t high_bit(T n)
}
/**
-* Return the index of the lowest set bit
-* T is an unsigned integer type
-* @param n an integer value
-* @return index of the lowest set bit in n
-*/
-template<typename T>
-inline size_t low_bit(T n)
- {
- for(size_t i = 0; i != 8*sizeof(T); ++i)
- if((n >> i) & 0x01)
- return (i + 1);
- return 0;
- }
-
-/**
* Return the number of significant bytes in n
* @param n an integer value
* @return number of significant bytes in n
@@ -91,10 +76,18 @@ inline size_t low_bit(T n)
template<typename T>
inline size_t significant_bytes(T n)
{
- for(size_t i = 0; i != sizeof(T); ++i)
- if(get_byte(i, n))
- return sizeof(T)-i;
- return 0;
+ size_t b = 0;
+
+ for(size_t s = 8*sizeof(n) / 2; s >= 8; s /= 2)
+ {
+ const size_t z = s * (~ct_is_zero(n >> s) & 1);
+ b += z/8;
+ n >>= z;
+ }
+
+ b += (n != 0);
+
+ return b;
}
/**
@@ -114,9 +107,9 @@ inline size_t ctz(T n)
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 = ct_is_zero(n & mask) & 1;
- lb += s * n_bits;
- n >>= s * n_bits;
+ const T z = s * (ct_is_zero(n & mask) & 1);
+ lb += z;
+ n >>= z;
}
return lb;
@@ -140,25 +133,17 @@ 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)
+// Potentially variable time ctz used for OCB
+inline size_t var_ctz32(uint32_t n)
{
+#if defined(BOTAN_BUILD_COMPILER_IS_GCC) || defined(BOTAN_BUILD_COMPILER_IS_CLANG)
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);
- }
-
+#else
+ return ctz<uint32_t>(n);
#endif
+ }
}
diff --git a/src/lib/x509/x509_ext.cpp b/src/lib/x509/x509_ext.cpp
index 97c291f6e..a6bc09a82 100644
--- a/src/lib/x509/x509_ext.cpp
+++ b/src/lib/x509/x509_ext.cpp
@@ -345,7 +345,7 @@ std::vector<uint8_t> Key_Usage::encode_inner() const
if(m_constraints == NO_CONSTRAINTS)
throw Encoding_Error("Cannot encode zero usage constraints");
- const size_t unused_bits = low_bit(m_constraints) - 1;
+ const size_t unused_bits = ctz(static_cast<uint32_t>(m_constraints));
std::vector<uint8_t> der;
der.push_back(BIT_STRING);
diff --git a/src/tests/test_utils.cpp b/src/tests/test_utils.cpp
index 485d72a2a..de9db6683 100644
--- a/src/tests/test_utils.cpp
+++ b/src/tests/test_utils.cpp
@@ -245,11 +245,61 @@ class BitOps_Tests final : public Test
std::vector<Test::Result> results;
results.push_back(test_power_of_2());
+ results.push_back(test_ctz());
+ results.push_back(test_sig_bytes());
return results;
}
private:
template<typename T>
+ void test_ctz(Test::Result& result, T val, size_t expected)
+ {
+ result.test_eq("ctz(" + std::to_string(val) + ")", Botan::ctz<T>(val), expected);
+ }
+
+ Test::Result test_ctz()
+ {
+ Test::Result result("ctz");
+ test_ctz<uint32_t>(result, 0, 32);
+ test_ctz<uint32_t>(result, 1, 0);
+ test_ctz<uint32_t>(result, 0x80, 7);
+ test_ctz<uint32_t>(result, 0x8000000, 27);
+ test_ctz<uint32_t>(result, 0x8100000, 20);
+ test_ctz<uint32_t>(result, 0x80000000, 31);
+
+ return result;
+ }
+
+ template<typename T>
+ void test_sig_bytes(Test::Result& result, T val, size_t expected)
+ {
+ result.test_eq("significant_bytes(" + std::to_string(val) + ")",
+ Botan::significant_bytes<T>(val), expected);
+ }
+
+ Test::Result test_sig_bytes()
+ {
+ Test::Result result("significant_bytes");
+ test_sig_bytes<uint32_t>(result, 0, 0);
+ test_sig_bytes<uint32_t>(result, 1, 1);
+ test_sig_bytes<uint32_t>(result, 0x80, 1);
+ test_sig_bytes<uint32_t>(result, 255, 1);
+ test_sig_bytes<uint32_t>(result, 256, 2);
+ test_sig_bytes<uint32_t>(result, 65535, 2);
+ test_sig_bytes<uint32_t>(result, 65536, 3);
+ test_sig_bytes<uint32_t>(result, 0x80000000, 4);
+
+ test_sig_bytes<uint64_t>(result, 0, 0);
+ test_sig_bytes<uint64_t>(result, 1, 1);
+ test_sig_bytes<uint64_t>(result, 0x80, 1);
+ test_sig_bytes<uint64_t>(result, 256, 2);
+ test_sig_bytes<uint64_t>(result, 0x80000000, 4);
+ test_sig_bytes<uint64_t>(result, 0x100000000, 5);
+
+ return result;
+ }
+
+ template<typename T>
void test_power_of_2(Test::Result& result, T val, bool expected)
{
result.test_eq("power_of_2(" + std::to_string(val) + ")", Botan::is_power_of_2<T>(val), expected);
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-27 01:53:19 +0000