From 63cbaf52e414b2ac138d1c95143a3238741df21c Mon Sep 17 00:00:00 2001
From: Jack Lloyd <jack@randombit.net>
Date: Fri, 7 Sep 2018 17:16:02 -0400
Subject: Optimize CT::is_zero, CT::expand_mask, CT::expand_top_bit

---
 src/lib/block/idea/idea.cpp |  9 ++++-----
 src/lib/utils/ct_utils.h    | 41 ++++++++++++++++++++---------------------
 2 files changed, 24 insertions(+), 26 deletions(-)

(limited to 'src')

diff --git a/src/lib/block/idea/idea.cpp b/src/lib/block/idea/idea.cpp
index ffd1bf56a..de153e2c5 100644
--- a/src/lib/block/idea/idea.cpp
+++ b/src/lib/block/idea/idea.cpp
@@ -20,8 +20,7 @@ namespace {
 inline uint16_t mul(uint16_t x, uint16_t y)
    {
    const uint32_t P = static_cast<uint32_t>(x) * y;
-
-   const uint16_t Z_mask = static_cast<uint16_t>(CT::expand_mask(P) & 0xFFFF);
+   const uint16_t P_mask = static_cast<uint16_t>(CT::is_zero(P) & 0xFFFF);
 
    const uint32_t P_hi = P >> 16;
    const uint32_t P_lo = P & 0xFFFF;
@@ -30,7 +29,7 @@ inline uint16_t mul(uint16_t x, uint16_t y)
    const uint16_t r_1 = static_cast<uint16_t>((P_lo - P_hi) + carry);
    const uint16_t r_2 = 1 - x - y;
 
-   return CT::select(Z_mask, r_1, r_2);
+   return CT::select(P_mask, r_2, r_1);
    }
 
 /*
@@ -80,10 +79,10 @@ void idea_op(const uint8_t in[], uint8_t out[], size_t blocks, const uint16_t K[
          X3 += K[6*j+2];
          X4 = mul(X4, K[6*j+3]);
 
-         uint16_t T0 = X3;
+         const uint16_t T0 = X3;
          X3 = mul(X3 ^ X1, K[6*j+4]);
 
-         uint16_t T1 = X2;
+         const uint16_t T1 = X2;
          X2 = mul((X2 ^ X4) + X3, K[6*j+5]);
          X3 += X2;
 
diff --git a/src/lib/utils/ct_utils.h b/src/lib/utils/ct_utils.h
index 013267874..4fd06ec3d 100644
--- a/src/lib/utils/ct_utils.h
+++ b/src/lib/utils/ct_utils.h
@@ -15,6 +15,7 @@
 #define BOTAN_TIMING_ATTACK_CM_H_
 
 #include <botan/secmem.h>
+#include <type_traits>
 #include <vector>
 
 #if defined(BOTAN_HAS_VALGRIND)
@@ -74,6 +75,22 @@ inline void unpoison(T& p)
 #endif
    }
 
+/* Mask generation */
+
+template<typename T>
+inline T expand_top_bit(T a)
+   {
+   static_assert(std::is_unsigned<T>::value, "unsigned integer type required");
+   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
+   }
+
+template<typename T>
+inline T is_zero(T x)
+   {
+   static_assert(std::is_unsigned<T>::value, "unsigned integer type required");
+   return expand_top_bit<T>(~x & (x - 1));
+   }
+
 /*
 * T should be an unsigned machine integer type
 * Expand to a mask used for other operations
@@ -85,26 +102,14 @@ inline void unpoison(T& p)
 template<typename T>
 inline T expand_mask(T x)
    {
-   T r = x;
-   // First fold r down to a single bit
-   for(size_t i = 1; i != sizeof(T)*8; i *= 2)
-      {
-      r = r | static_cast<T>(r >> i);
-      }
-   r &= 1;
-   r = static_cast<T>(~(r - 1));
-   return r;
-   }
-
-template<typename T>
-inline T expand_top_bit(T a)
-   {
-   return expand_mask<T>(a >> (sizeof(T)*8-1));
+   static_assert(std::is_unsigned<T>::value, "unsigned integer type required");
+   return ~is_zero(x);
    }
 
 template<typename T>
 inline T select(T mask, T from0, T from1)
    {
+   static_assert(std::is_unsigned<T>::value, "unsigned integer type required");
    return static_cast<T>((from0 & mask) | (from1 & ~mask));
    }
 
@@ -126,12 +131,6 @@ inline ValT val_or_zero(PredT pred_val, ValT val)
    return select(CT::expand_mask<ValT>(pred_val), val, static_cast<ValT>(0));
    }
 
-template<typename T>
-inline T is_zero(T x)
-   {
-   return static_cast<T>(~expand_mask(x));
-   }
-
 template<typename T>
 inline T is_equal(T x, T y)
    {
-- 
cgit v1.2.3