TensorUInt128.h
00001 // This file is part of Eigen, a lightweight C++ template library
00002 // for linear algebra.
00003 //
00004 // Copyright (C) 2015 Benoit Steiner <benoit.steiner.goog@gmail.com>
00005 //
00006 // This Source Code Form is subject to the terms of the Mozilla
00007 // Public License v. 2.0. If a copy of the MPL was not distributed
00008 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
00009 
00010 #ifndef EIGEN_CXX11_TENSOR_TENSOR_UINT128_H
00011 #define EIGEN_CXX11_TENSOR_TENSOR_UINT128_H
00012 
00013 namespace Eigen {
00014 namespace internal {
00015 
00016 
00017 template <uint64_t n>
00018 struct static_val {
00019   static const uint64_t value = n;
00020   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE operator uint64_t() const { return n; }
00021 
00022   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE static_val() { }
00023 
00024   template <typename T>
00025   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE static_val(const T& v) {
00026     eigen_assert(v == n);
00027   }
00028 };
00029 
00030 
00031 template <typename HIGH = uint64_t, typename LOW = uint64_t>
00032 struct TensorUInt128
00033 {
00034   HIGH high;
00035   LOW low;
00036 
00037   template<typename OTHER_HIGH, typename OTHER_LOW>
00038   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
00039   TensorUInt128(const TensorUInt128<OTHER_HIGH, OTHER_LOW>& other) : high(other.high), low(other.low) {
00040     EIGEN_STATIC_ASSERT(sizeof(OTHER_HIGH) <= sizeof(HIGH), YOU_MADE_A_PROGRAMMING_MISTAKE);
00041     EIGEN_STATIC_ASSERT(sizeof(OTHER_LOW) <= sizeof(LOW), YOU_MADE_A_PROGRAMMING_MISTAKE);
00042   }
00043 
00044   template<typename OTHER_HIGH, typename OTHER_LOW>
00045   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
00046   TensorUInt128& operator = (const TensorUInt128<OTHER_HIGH, OTHER_LOW>& other) {
00047     EIGEN_STATIC_ASSERT(sizeof(OTHER_HIGH) <= sizeof(HIGH), YOU_MADE_A_PROGRAMMING_MISTAKE);
00048     EIGEN_STATIC_ASSERT(sizeof(OTHER_LOW) <= sizeof(LOW), YOU_MADE_A_PROGRAMMING_MISTAKE);
00049     high = other.high;
00050     low = other.low;
00051     return *this;
00052   }
00053 
00054   template<typename T>
00055   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
00056   explicit TensorUInt128(const T& x) : high(0), low(x) {
00057     eigen_assert((static_cast<typename conditional<sizeof(T) == 8, uint64_t, uint32_t>::type>(x) <= NumTraits<uint64_t>::highest()));
00058     eigen_assert(x >= 0);
00059   }
00060 
00061   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
00062   TensorUInt128(HIGH y, LOW x) : high(y), low(x) { }
00063 
00064   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE operator LOW() const {
00065     return low;
00066   }
00067   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE LOW lower() const {
00068     return low;
00069   }
00070   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE HIGH upper() const {
00071     return high;
00072   }
00073 };
00074 
00075 
00076 template <typename HL, typename LL, typename HR, typename LR>
00077 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
00078 bool operator == (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
00079 {
00080   return (lhs.high == rhs.high) & (lhs.low == rhs.low);
00081 }
00082 
00083 template <typename HL, typename LL, typename HR, typename LR>
00084 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
00085 bool operator != (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
00086 {
00087   return (lhs.high != rhs.high) | (lhs.low != rhs.low);
00088 }
00089 
00090 template <typename HL, typename LL, typename HR, typename LR>
00091 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
00092 bool operator >= (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
00093 {
00094   if (lhs.high != rhs.high) {
00095     return lhs.high > rhs.high;
00096   }
00097   return lhs.low >= rhs.low;
00098 }
00099 
00100 template <typename HL, typename LL, typename HR, typename LR>
00101 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
00102 bool operator < (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
00103 {
00104   if (lhs.high != rhs.high) {
00105     return lhs.high < rhs.high;
00106   }
00107   return lhs.low < rhs.low;
00108 }
00109 
00110 template <typename HL, typename LL, typename HR, typename LR>
00111 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
00112 TensorUInt128<uint64_t, uint64_t> operator + (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
00113 {
00114   TensorUInt128<uint64_t, uint64_t> result(lhs.high + rhs.high, lhs.low + rhs.low);
00115   if (result.low < rhs.low) {
00116     result.high += 1;
00117   }
00118   return result;
00119 }
00120 
00121 template <typename HL, typename LL, typename HR, typename LR>
00122 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
00123 TensorUInt128<uint64_t, uint64_t> operator - (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
00124 {
00125   TensorUInt128<uint64_t, uint64_t> result(lhs.high - rhs.high, lhs.low - rhs.low);
00126   if (result.low > lhs.low) {
00127     result.high -= 1;
00128   }
00129   return result;
00130 }
00131 
00132 
00133 template <typename HL, typename LL, typename HR, typename LR>
00134 static EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE
00135 TensorUInt128<uint64_t, uint64_t> operator * (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
00136 {
00137   // Split each 128-bit integer into 4 32-bit integers, and then do the
00138   // multiplications by hand as follow:
00139   //   lhs      a  b  c  d
00140   //   rhs      e  f  g  h
00141   //           -----------
00142   //           ah bh ch dh
00143   //           bg cg dg
00144   //           cf df
00145   //           de
00146   // The result is stored in 2 64bit integers, high and low.
00147 
00148   const uint64_t LOW = 0x00000000FFFFFFFFLL;
00149   const uint64_t HIGH = 0xFFFFFFFF00000000LL;
00150 
00151   uint64_t d = lhs.low & LOW;
00152   uint64_t c = (lhs.low & HIGH) >> 32LL;
00153   uint64_t b = lhs.high & LOW;
00154   uint64_t a = (lhs.high & HIGH) >> 32LL;
00155 
00156   uint64_t h = rhs.low & LOW;
00157   uint64_t g = (rhs.low & HIGH) >> 32LL;
00158   uint64_t f = rhs.high & LOW;
00159   uint64_t e = (rhs.high & HIGH) >> 32LL;
00160 
00161   // Compute the low 32 bits of low
00162   uint64_t acc = d * h;
00163   uint64_t low = acc & LOW;
00164   //  Compute the high 32 bits of low. Add a carry every time we wrap around
00165   acc >>= 32LL;
00166   uint64_t carry = 0;
00167   uint64_t acc2 = acc + c * h;
00168   if (acc2 < acc) {
00169     carry++;
00170   }
00171   acc = acc2 + d * g;
00172   if (acc < acc2) {
00173     carry++;
00174   }
00175   low |= (acc << 32LL);
00176 
00177   // Carry forward the high bits of acc to initiate the computation of the
00178   // low 32 bits of high
00179   acc2 = (acc >> 32LL) | (carry << 32LL);
00180   carry = 0;
00181 
00182   acc = acc2 + b * h;
00183   if (acc < acc2) {
00184     carry++;
00185   }
00186   acc2 = acc + c * g;
00187   if (acc2 < acc) {
00188     carry++;
00189   }
00190   acc = acc2 + d * f;
00191   if (acc < acc2) {
00192     carry++;
00193   }
00194   uint64_t high = acc & LOW;
00195 
00196   // Start to compute the high 32 bits of high.
00197   acc2 = (acc >> 32LL) | (carry << 32LL);
00198 
00199   acc = acc2 + a * h;
00200   acc2 = acc + b * g;
00201   acc = acc2 + c * f;
00202   acc2 = acc + d * e;
00203   high |= (acc2 << 32LL);
00204 
00205   return TensorUInt128<uint64_t, uint64_t>(high, low);
00206 }
00207 
00208 template <typename HL, typename LL, typename HR, typename LR>
00209 static EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE
00210 TensorUInt128<uint64_t, uint64_t> operator / (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
00211 {
00212   if (rhs == TensorUInt128<static_val<0>, static_val<1> >(1)) {
00213     return TensorUInt128<uint64_t, uint64_t>(lhs.high, lhs.low);
00214   } else if (lhs < rhs) {
00215     return TensorUInt128<uint64_t, uint64_t>(0);
00216   } else {
00217     // calculate the biggest power of 2 times rhs that's less than or equal to lhs
00218     TensorUInt128<uint64_t, uint64_t> power2(1);
00219     TensorUInt128<uint64_t, uint64_t> d(rhs);
00220     TensorUInt128<uint64_t, uint64_t> tmp(lhs - d);
00221     while (lhs >= d) {
00222       tmp = tmp - d;
00223       d = d + d;
00224       power2 = power2 + power2;
00225     }
00226 
00227     tmp = TensorUInt128<uint64_t, uint64_t>(lhs.high, lhs.low);
00228     TensorUInt128<uint64_t, uint64_t> result(0);
00229     while (power2 != TensorUInt128<static_val<0>, static_val<0> >(0)) {
00230       if (tmp >= d) {
00231         tmp = tmp - d;
00232         result = result + power2;
00233       }
00234       // Shift right
00235       power2 = TensorUInt128<uint64_t, uint64_t>(power2.high >> 1, (power2.low >> 1) | (power2.high << 63));
00236       d = TensorUInt128<uint64_t, uint64_t>(d.high >> 1, (d.low >> 1) | (d.high << 63));
00237     }
00238 
00239     return result;
00240   }
00241 }
00242 
00243 
00244 }  // namespace internal
00245 }  // namespace Eigen
00246 
00247 
00248 #endif  // EIGEN_CXX11_TENSOR_TENSOR_UINT128_H
 All Classes Functions Variables Typedefs Enumerator