1 files changed, 171 insertions, 0 deletions
diff --git a/comm/third_party/botan/src/lib/utils/bit_ops.h b/comm/third_party/botan/src/lib/utils/bit_ops.h
new file mode 100644
index 0000000000..79d86f0f76
--- /dev/null
+++ b/comm/third_party/botan/src/lib/utils/bit_ops.h
@@ -0,0 +1,171 @@
+/*
+* Bit/Word Operations
+* (C) 1999-2008 Jack Lloyd
+* (C) Copyright Projet SECRET, INRIA, Rocquencourt
+* (C) Bhaskar Biswas and  Nicolas Sendrier
+* (C) 2014 cryptosource GmbH
+* (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_BIT_OPS_H_
+#define BOTAN_BIT_OPS_H_
+
+#include <botan/types.h>
+
+namespace Botan {
+
+/**
+* If top bit of arg is set, return ~0. Otherwise return 0.
+*/
+template<typename T>
+inline T expand_top_bit(T a)
+   {
+   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
+   }
+
+/**
+* If arg is zero, return ~0. Otherwise return 0
+*/
+template<typename T>
+inline T ct_is_zero(T x)
+   {
+   return expand_top_bit<T>(~x & (x - 1));
+   }
+
+/**
+* Power of 2 test. T should be an unsigned integer type
+* @param arg an integer value
+* @return true iff arg is 2^n for some n > 0
+*/
+template<typename T>
+inline constexpr bool is_power_of_2(T arg)
+   {
+   return (arg != 0) && (arg != 1) && ((arg & static_cast<T>(arg-1)) == 0);
+   }
+
+/**
+* Return the index of the highest set bit
+* T is an unsigned integer type
+* @param n an integer value
+* @return index of the highest set bit in n
+*/
+template<typename T>
+inline size_t high_bit(T n)
+   {
+   size_t hb = 0;
+
+   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
+      {
+      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
+      hb += z;
+      n >>= z;
+      }
+
+   hb += n;
+
+   return hb;
+   }
+
+/**
+* Return the number of significant bytes in n
+* @param n an integer value
+* @return number of significant bytes in n
+*/
+template<typename T>
+inline size_t significant_bytes(T n)
+   {
+   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;
+   }
+
+/**
+* Count the trailing zero bits in n
+* @param n an integer value
+* @return maximum x st 2^x divides n
+*/
+template<typename T>
+inline size_t ctz(T 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 = ct_is_zero(n) & 1;
+
+   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
+      {
+      const T mask = (static_cast<T>(1) << s) - 1;
+      const size_t z = s * (ct_is_zero(n & mask) & 1);
+      lb += z;
+      n >>= z;
+      }
+
+   return lb;
+   }
+
+template<typename T>
+uint8_t ceil_log2(T x)
+   {
+   static_assert(sizeof(T) < 32, "Abnormally large scalar");
+
+   if(x >> (sizeof(T)*8-1))
+      return sizeof(T)*8;
+
+   uint8_t result = 0;
+   T compare = 1;
+
+   while(compare < x)
+      {
+      compare <<= 1;
+      result++;
+      }
+
+   return result;
+   }
+
+// 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);
+#else
+   return ctz<uint32_t>(n);
+#endif
+   }
+
+template<typename T>
+inline T bit_permute_step(T x, T mask, size_t shift)
+   {
+   /*
+   See https://reflectionsonsecurity.wordpress.com/2014/05/11/efficient-bit-permutation-using-delta-swaps/
+   and http://programming.sirrida.de/bit_perm.html
+   */
+   const T swap = ((x >> shift) ^ x) & mask;
+   return (x ^ swap) ^ (swap << shift);
+   }
+
+template<typename T>
+inline void swap_bits(T& x, T& y, T mask, size_t shift)
+   {
+   const T swap = ((x >> shift) ^ y) & mask;
+   x ^= swap << shift;
+   y ^= swap;
+   }
+
+}
+
+#endif