![]() |
Eigen-unsupported
3.3.3
|
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