Add choose and majority functions

13 files changed, 75 insertions, 47 deletions

diff --git a/src/lib/block/shacal2/shacal2.cpp b/src/lib/block/shacal2/shacal2.cpp
index 395613837..b77d2f042 100644
--- a/src/lib/block/shacal2/shacal2.cpp
+++ b/src/lib/block/shacal2/shacal2.cpp
@@ -8,6 +8,7 @@
 #include <botan/internal/shacal2.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/rotate.h>
+#include <botan/internal/bit_ops.h>
 #include <botan/internal/cpuid.h>
 
 namespace Botan {
@@ -21,9 +22,9 @@ inline void SHACAL2_Fwd(uint32_t A, uint32_t B, uint32_t C, uint32_t& D,
    const uint32_t A_rho = rotr<2>(A) ^ rotr<13>(A) ^ rotr<22>(A);
    const uint32_t E_rho = rotr<6>(E) ^ rotr<11>(E) ^ rotr<25>(E);
 
-   H += E_rho + ((E & F) ^ (~E & G)) + RK;
+   H += E_rho + choose(E, F, G) + RK;
    D += H;
-   H += A_rho + ((A & B) | ((A | B) & C));
+   H += A_rho + majority(A, B, C);
    }
 
 inline void SHACAL2_Rev(uint32_t A, uint32_t B, uint32_t C, uint32_t& D,
@@ -33,9 +34,9 @@ inline void SHACAL2_Rev(uint32_t A, uint32_t B, uint32_t C, uint32_t& D,
    const uint32_t A_rho = rotr<2>(A) ^ rotr<13>(A) ^ rotr<22>(A);
    const uint32_t E_rho = rotr<6>(E) ^ rotr<11>(E) ^ rotr<25>(E);
 
-   H -= A_rho + ((A & B) | ((A | B) & C));
+   H -= A_rho + majority(A, B, C);
    D -= H;
-   H -= E_rho + ((E & F) ^ (~E & G)) + RK;
+   H -= E_rho + choose(E, F, G) + RK;
    }
 
 }
diff --git a/src/lib/hash/md4/md4.cpp b/src/lib/hash/md4/md4.cpp
index 575536389..0f857a102 100644
--- a/src/lib/hash/md4/md4.cpp
+++ b/src/lib/hash/md4/md4.cpp
@@ -8,6 +8,7 @@
 #include <botan/internal/md4.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/rotate.h>
+#include <botan/internal/bit_ops.h>
 
 namespace Botan {
 
@@ -22,16 +23,16 @@ inline void FF4(uint32_t& A, uint32_t& B, uint32_t& C, uint32_t& D,
                 uint32_t M0, uint32_t M1, uint32_t M2, uint32_t M3)
 
    {
-   A += (D ^ (B & (C ^ D))) + M0;
+   A += choose(B, C, D) + M0;
    A = rotl<3>(A);
 
-   D += (C ^ (A & (B ^ C))) + M1;
+   D += choose(A, B, C) + M1;
    D = rotl<7>(D);
 
-   C += (B ^ (D & (A ^ B))) + M2;
+   C += choose(D, A, B) + M2;
    C = rotl<11>(C);
 
-   B += (A ^ (C & (D ^ A))) + M3;
+   B += choose(C, D, A) + M3;
    B = rotl<19>(B);
    }
 
@@ -39,6 +40,12 @@ inline void GG4(uint32_t& A, uint32_t& B, uint32_t& C, uint32_t& D,
                 uint32_t M0, uint32_t M1, uint32_t M2, uint32_t M3)
 
    {
+   /*
+   These are choose(D, B | C, B & C) but the below expression
+   takes advantage of the fact that B & C is a subset of B | C
+   to eliminate an and
+   */
+
    A += ((B & C) | (D & (B | C))) + M0 + 0x5A827999;
    A = rotl<3>(A);
 
diff --git a/src/lib/hash/md5/md5.cpp b/src/lib/hash/md5/md5.cpp
index facac0e20..66c06ef71 100644
--- a/src/lib/hash/md5/md5.cpp
+++ b/src/lib/hash/md5/md5.cpp
@@ -8,6 +8,7 @@
 #include <botan/internal/md5.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/rotate.h>
+#include <botan/internal/bit_ops.h>
 
 namespace Botan {
 
@@ -24,7 +25,7 @@ namespace {
 template<size_t S>
 inline void FF(uint32_t& A, uint32_t B, uint32_t C, uint32_t D, uint32_t M)
    {
-   A += (D ^ (B & (C ^ D))) + M;
+   A += choose(B, C, D) + M;
    A  = rotl<S>(A) + B;
    }
 
@@ -34,7 +35,7 @@ inline void FF(uint32_t& A, uint32_t B, uint32_t C, uint32_t D, uint32_t M)
 template<size_t S>
 inline void GG(uint32_t& A, uint32_t B, uint32_t C, uint32_t D, uint32_t M)
    {
-   A += (C ^ (D & (B ^ C))) + M;
+   A += choose(D, B, C) + M;
    A  = rotl<S>(A) + B;
    }
 
@@ -54,6 +55,7 @@ inline void HH(uint32_t& A, uint32_t B, uint32_t C, uint32_t D, uint32_t M)
 template<size_t S>
 inline void II(uint32_t& A, uint32_t B, uint32_t C, uint32_t D, uint32_t M)
    {
+   // This expr is choose(D, B ^ C, ~C), but that is slower
    A += (C ^ (B | ~D)) + M;
    A  = rotl<S>(A) + B;
    }
diff --git a/src/lib/hash/rmd160/rmd160.cpp b/src/lib/hash/rmd160/rmd160.cpp
index 6bce844b3..e091dc32d 100644
--- a/src/lib/hash/rmd160/rmd160.cpp
+++ b/src/lib/hash/rmd160/rmd160.cpp
@@ -8,6 +8,7 @@
 #include <botan/internal/rmd160.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/rotate.h>
+#include <botan/internal/bit_ops.h>
 
 namespace Botan {
 
@@ -37,7 +38,7 @@ template<size_t S>
 inline void F2(uint32_t& A, uint32_t B, uint32_t& C, uint32_t D, uint32_t E,
                uint32_t M)
    {
-   A += (D ^ (B & (C ^ D))) + M;
+   A += choose(B, C, D) + M;
    A  = rotl<S>(A) + E;
    C  = rotl<10>(C);
    }
@@ -61,7 +62,7 @@ template<size_t S>
 inline void F4(uint32_t& A, uint32_t B, uint32_t& C, uint32_t D, uint32_t E,
                uint32_t M)
    {
-   A += (C ^ (D & (B ^ C))) + M;
+   A += choose(D, B, C) + M;
    A  = rotl<S>(A) + E;
    C  = rotl<10>(C);
    }
diff --git a/src/lib/hash/sha1/sha160.cpp b/src/lib/hash/sha1/sha160.cpp
index 70f2f55b8..a6a918e52 100644
--- a/src/lib/hash/sha1/sha160.cpp
+++ b/src/lib/hash/sha1/sha160.cpp
@@ -8,6 +8,7 @@
 #include <botan/internal/sha160.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/rotate.h>
+#include <botan/internal/bit_ops.h>
 #include <botan/internal/cpuid.h>
 
 namespace Botan {
@@ -26,7 +27,7 @@ namespace {
 */
 inline void F1(uint32_t A, uint32_t& B, uint32_t C, uint32_t D, uint32_t& E, uint32_t msg)
    {
-   E += (D ^ (B & (C ^ D))) + msg + 0x5A827999 + rotl<5>(A);
+   E += choose(B, C, D) + msg + 0x5A827999 + rotl<5>(A);
    B  = rotl<30>(B);
    }
 
@@ -44,7 +45,7 @@ inline void F2(uint32_t A, uint32_t& B, uint32_t C, uint32_t D, uint32_t& E, uin
 */
 inline void F3(uint32_t A, uint32_t& B, uint32_t C, uint32_t D, uint32_t& E, uint32_t msg)
    {
-   E += ((B & C) | ((B | C) & D)) + msg + 0x8F1BBCDC + rotl<5>(A);
+   E += majority(B, C, D) + msg + 0x8F1BBCDC + rotl<5>(A);
    B  = rotl<30>(B);
    }
 
diff --git a/src/lib/hash/sha1/sha1_sse2/sha1_sse2.cpp b/src/lib/hash/sha1/sha1_sse2/sha1_sse2.cpp
index 7e60bd21c..c86693c98 100644
--- a/src/lib/hash/sha1/sha1_sse2/sha1_sse2.cpp
+++ b/src/lib/hash/sha1/sha1_sse2/sha1_sse2.cpp
@@ -9,6 +9,7 @@
 
 #include <botan/internal/sha160.h>
 #include <botan/internal/rotate.h>
+#include <botan/internal/bit_ops.h>
 #include <emmintrin.h>
 
 namespace Botan {
@@ -114,7 +115,7 @@ W0 = W[t]..W[t+3]
 */
 inline void F1(uint32_t A, uint32_t& B, uint32_t C, uint32_t D, uint32_t& E, uint32_t msg)
    {
-   E += (D ^ (B & (C ^ D))) + msg + rotl<5>(A);
+   E += choose(B, C, D) + msg + rotl<5>(A);
    B  = rotl<30>(B);
    }
 
@@ -132,7 +133,7 @@ inline void F2(uint32_t A, uint32_t& B, uint32_t C, uint32_t D, uint32_t& E, uin
 */
 inline void F3(uint32_t A, uint32_t& B, uint32_t C, uint32_t D, uint32_t& E, uint32_t msg)
    {
-   E += ((B & C) | ((B | C) & D)) + msg + rotl<5>(A);
+   E += majority(B, C, D) + msg + rotl<5>(A);
    B  = rotl<30>(B);
    }
 
diff --git a/src/lib/hash/sha2_32/sha2_32.cpp b/src/lib/hash/sha2_32/sha2_32.cpp
index 096028953..c43fe3db6 100644
--- a/src/lib/hash/sha2_32/sha2_32.cpp
+++ b/src/lib/hash/sha2_32/sha2_32.cpp
@@ -9,6 +9,7 @@
 #include <botan/internal/sha2_32.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/rotate.h>
+#include <botan/internal/bit_ops.h>
 #include <botan/internal/cpuid.h>
 
 namespace Botan {
@@ -59,15 +60,15 @@ std::unique_ptr<HashFunction> SHA_256::copy_state() const
 * Use a macro as many compilers won't inline a function this big,
 * even though it is much faster if inlined.
 */
-#define SHA2_32_F(A, B, C, D, E, F, G, H, M1, M2, M3, M4, magic) do {               \
-   uint32_t A_rho = rotr<2>(A) ^ rotr<13>(A) ^ rotr<22>(A); \
-   uint32_t E_rho = rotr<6>(E) ^ rotr<11>(E) ^ rotr<25>(E); \
-   uint32_t M2_sigma = rotr<17>(M2) ^ rotr<19>(M2) ^ (M2 >> 10);    \
-   uint32_t M4_sigma = rotr<7>(M4) ^ rotr<18>(M4) ^ (M4 >> 3);      \
-   H += magic + E_rho + ((E & F) ^ (~E & G)) + M1;                                  \
-   D += H;                                                                          \
-   H += A_rho + ((A & B) | ((A | B) & C));                                          \
-   M1 += M2_sigma + M3 + M4_sigma;                                                  \
+#define SHA2_32_F(A, B, C, D, E, F, G, H, M1, M2, M3, M4, magic) do {   \
+   uint32_t A_rho = rotr<2>(A) ^ rotr<13>(A) ^ rotr<22>(A);             \
+   uint32_t E_rho = rotr<6>(E) ^ rotr<11>(E) ^ rotr<25>(E);             \
+   uint32_t M2_sigma = rotr<17>(M2) ^ rotr<19>(M2) ^ (M2 >> 10);        \
+   uint32_t M4_sigma = rotr<7>(M4) ^ rotr<18>(M4) ^ (M4 >> 3);          \
+   H += magic + E_rho + choose(E, F, G) + M1;                           \
+   D += H;                                                              \
+   H += A_rho + majority(A, B, C);                                      \
+   M1 += M2_sigma + M3 + M4_sigma;                                      \
    } while(0);
 
 /*
diff --git a/src/lib/hash/sha2_32/sha2_32_bmi2/sha2_32_bmi2.cpp b/src/lib/hash/sha2_32/sha2_32_bmi2/sha2_32_bmi2.cpp
index 557585818..a6319d1f1 100644
--- a/src/lib/hash/sha2_32/sha2_32_bmi2/sha2_32_bmi2.cpp
+++ b/src/lib/hash/sha2_32/sha2_32_bmi2/sha2_32_bmi2.cpp
@@ -7,6 +7,7 @@
 #include <botan/internal/sha2_32.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/rotate.h>
+#include <botan/internal/bit_ops.h>
 
 namespace Botan {
 
@@ -23,9 +24,9 @@ Likely instruction scheduling could be improved by using inline asm.
    uint32_t E_rho = rotr<6>(E) ^ rotr<11>(E) ^ rotr<25>(E);             \
    uint32_t M2_sigma = rotr<17>(M2) ^ rotr<19>(M2) ^ (M2 >> 10);        \
    uint32_t M4_sigma = rotr<7>(M4) ^ rotr<18>(M4) ^ (M4 >> 3);          \
-   H += magic + E_rho + ((E & F) ^ (~E & G)) + M1;                      \
+   H += magic + E_rho + choose(E, F, G) + M1;                           \
    D += H;                                                              \
-   H += A_rho + ((A & B) | ((A | B) & C));                              \
+   H += A_rho + majority(A, B, C);                                      \
    M1 += M2_sigma + M3 + M4_sigma;                                      \
    } while(0);
 
diff --git a/src/lib/hash/sha2_64/sha2_64.cpp b/src/lib/hash/sha2_64/sha2_64.cpp
index b34623070..cc4690bbd 100644
--- a/src/lib/hash/sha2_64/sha2_64.cpp
+++ b/src/lib/hash/sha2_64/sha2_64.cpp
@@ -8,6 +8,7 @@
 #include <botan/internal/sha2_64.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/rotate.h>
+#include <botan/internal/bit_ops.h>
 #include <botan/internal/cpuid.h>
 
 namespace Botan {
@@ -55,9 +56,9 @@ std::unique_ptr<HashFunction> SHA_512_256::copy_state() const
       const uint64_t A_rho = rotr<28>(A) ^ rotr<34>(A) ^ rotr<39>(A);    \
       const uint64_t M2_sigma = rotr<19>(M2) ^ rotr<61>(M2) ^ (M2 >> 6); \
       const uint64_t M4_sigma = rotr<1>(M4) ^ rotr<8>(M4) ^ (M4 >> 7);   \
-      H += magic + E_rho + ((E & F) ^ (~E & G)) + M1;                    \
+      H += magic + E_rho + choose(E, F, G) + M1;                         \
       D += H;                                                            \
-      H += A_rho + ((A & B) | ((A | B) & C));                            \
+      H += A_rho + majority(A, B, C);                                    \
       M1 += M2_sigma + M3 + M4_sigma;                                    \
    } while(0);
 
diff --git a/src/lib/hash/sha2_64/sha2_64_bmi2/sha2_64_bmi2.cpp b/src/lib/hash/sha2_64/sha2_64_bmi2/sha2_64_bmi2.cpp
index b53da8cb4..9ebf76c78 100644
--- a/src/lib/hash/sha2_64/sha2_64_bmi2/sha2_64_bmi2.cpp
+++ b/src/lib/hash/sha2_64/sha2_64_bmi2/sha2_64_bmi2.cpp
@@ -7,6 +7,7 @@
 #include <botan/internal/sha2_64.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/rotate.h>
+#include <botan/internal/bit_ops.h>
 
 namespace Botan {
 
@@ -22,9 +23,9 @@ namespace Botan {
       const uint64_t A_rho = rotr<28>(A) ^ rotr<34>(A) ^ rotr<39>(A);    \
       const uint64_t M2_sigma = rotr<19>(M2) ^ rotr<61>(M2) ^ (M2 >> 6); \
       const uint64_t M4_sigma = rotr<1>(M4) ^ rotr<8>(M4) ^ (M4 >> 7);   \
-      H += magic + E_rho + ((E & F) ^ (~E & G)) + M1;                    \
+      H += magic + E_rho + choose(E, F, G) + M1;                         \
       D += H;                                                            \
-      H += A_rho + ((A & B) | ((A | B) & C));                            \
+      H += A_rho + majority(A, B, C);                                    \
       M1 += M2_sigma + M3 + M4_sigma;                                    \
    } while(0);
 
diff --git a/src/lib/hash/sm3/sm3.cpp b/src/lib/hash/sm3/sm3.cpp
index 608752363..d29f2b505 100644
--- a/src/lib/hash/sm3/sm3.cpp
+++ b/src/lib/hash/sm3/sm3.cpp
@@ -1,6 +1,7 @@
 /*
 * SM3
 * (C) 2017 Ribose Inc.
+* (C) 2021 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -8,6 +9,7 @@
 #include <botan/internal/sm3.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/rotate.h>
+#include <botan/internal/bit_ops.h>
 
 namespace Botan {
 
@@ -28,18 +30,6 @@ inline uint32_t P0(uint32_t X)
    return X ^ rotl<9>(X) ^ rotl<17>(X);
    }
 
-inline uint32_t FF1(uint32_t X, uint32_t Y, uint32_t Z)
-   {
-   return (X & Y) | ((X | Y) & Z);
-   //return (X & Y) | (X & Z) | (Y & Z);
-   }
-
-inline uint32_t GG1(uint32_t X, uint32_t Y, uint32_t Z)
-   {
-   //return (X & Y) | (~X & Z);
-   return ((Z ^ (X & (Y ^ Z))));
-   }
-
 inline void R1(uint32_t A, uint32_t& B, uint32_t C, uint32_t& D,
                uint32_t E, uint32_t& F, uint32_t G, uint32_t& H,
                uint32_t TJ, uint32_t Wi, uint32_t Wj)
@@ -61,8 +51,8 @@ inline void R2(uint32_t A, uint32_t& B, uint32_t C, uint32_t& D,
    {
    const uint32_t A12 = rotl<12>(A);
    const uint32_t SS1 = rotl<7>(A12 + E + TJ);
-   const uint32_t TT1 = FF1(A, B, C) + D + (SS1 ^ A12) + Wj;
-   const uint32_t TT2 = GG1(E, F, G) + H + SS1 + Wi;
+   const uint32_t TT1 = majority(A, B, C) + D + (SS1 ^ A12) + Wj;
+   const uint32_t TT2 = choose(E, F, G) + H + SS1 + Wi;
 
    B = rotl<9>(B);
    D = TT1;
diff --git a/src/lib/utils/bit_ops.h b/src/lib/utils/bit_ops.h
index 7162c7552..4e63775ce 100644
--- a/src/lib/utils/bit_ops.h
+++ b/src/lib/utils/bit_ops.h
@@ -166,6 +166,28 @@ inline constexpr void swap_bits(T& x, T& y, T mask, size_t shift)
    y ^= swap;
    }
 
+template<typename T>
+inline constexpr T choose(T mask, T a, T b)
+   {
+   //return (mask & a) | (~mask & b);
+   return (b ^ (mask & (a ^ b)));
+   }
+
+template<typename T>
+inline constexpr T majority(T a, T b, T c)
+   {
+   /*
+   Considering each bit of a, b, c individually
+
+   If a xor b is set, then c is the deciding vote.
+
+   If a xor b is not set then either a and b are both set or both unset.
+   In either case the value of c doesn't matter, and examining b (or a)
+   allows us to determine which case we are in.
+   */
+   return choose(a ^ b, c, b);
+   }
+
 }
 
 #endif
diff --git a/src/lib/utils/ct_utils.h b/src/lib/utils/ct_utils.h
index f2e745293..a23312fdb 100644
--- a/src/lib/utils/ct_utils.h
+++ b/src/lib/utils/ct_utils.h
@@ -287,8 +287,7 @@ class Mask
       */
       T select(T x, T y) const
          {
-         // (x & value()) | (y & ~value())
-         return static_cast<T>(y ^ (value() & (x ^ y)));
+         return choose(value(), x, y);
          }
 
       T select_and_unpoison(T x, T y) const