TensorUInt128.h
Go to the documentation of this file.
1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2015 Benoit Steiner <benoit.steiner.goog@gmail.com>
5 //
6 // This Source Code Form is subject to the terms of the Mozilla
7 // Public License v. 2.0. If a copy of the MPL was not distributed
8 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9 
10 #ifndef EIGEN_CXX11_TENSOR_TENSOR_UINT128_H
11 #define EIGEN_CXX11_TENSOR_TENSOR_UINT128_H
12 
13 namespace Eigen {
14 namespace internal {
15 
16 
17 template <uint64_t n>
18 struct static_val {
19  static const uint64_t value = n;
20  EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE operator uint64_t() const { return n; }
21 
23 
24  template <typename T>
27  eigen_assert(v == n);
28  }
29 };
30 
31 
32 template <typename HIGH = uint64_t, typename LOW = uint64_t>
34 {
35  HIGH high;
36  LOW low;
37 
38  template<typename OTHER_HIGH, typename OTHER_LOW>
40  TensorUInt128(const TensorUInt128<OTHER_HIGH, OTHER_LOW>& other) : high(other.high), low(other.low) {
41  EIGEN_STATIC_ASSERT(sizeof(OTHER_HIGH) <= sizeof(HIGH), YOU_MADE_A_PROGRAMMING_MISTAKE);
42  EIGEN_STATIC_ASSERT(sizeof(OTHER_LOW) <= sizeof(LOW), YOU_MADE_A_PROGRAMMING_MISTAKE);
43  }
44 
45  template<typename OTHER_HIGH, typename OTHER_LOW>
48  EIGEN_STATIC_ASSERT(sizeof(OTHER_HIGH) <= sizeof(HIGH), YOU_MADE_A_PROGRAMMING_MISTAKE);
49  EIGEN_STATIC_ASSERT(sizeof(OTHER_LOW) <= sizeof(LOW), YOU_MADE_A_PROGRAMMING_MISTAKE);
50  high = other.high;
51  low = other.low;
52  return *this;
53  }
54 
55  template<typename T>
57  explicit TensorUInt128(const T& x) : high(0), low(x) {
59  eigen_assert(x >= 0);
60  }
61 
63  TensorUInt128(HIGH y, LOW x) : high(y), low(x) { }
64 
65  EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE operator LOW() const {
66  return low;
67  }
69  return low;
70  }
72  return high;
73  }
74 };
75 
76 
77 template <typename HL, typename LL, typename HR, typename LR>
80 {
81  return (lhs.high == rhs.high) & (lhs.low == rhs.low);
82 }
83 
84 template <typename HL, typename LL, typename HR, typename LR>
87 {
88  return (lhs.high != rhs.high) | (lhs.low != rhs.low);
89 }
90 
91 template <typename HL, typename LL, typename HR, typename LR>
94 {
95  if (lhs.high != rhs.high) {
96  return lhs.high > rhs.high;
97  }
98  return lhs.low >= rhs.low;
99 }
100 
101 template <typename HL, typename LL, typename HR, typename LR>
103 bool operator < (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
104 {
105  if (lhs.high != rhs.high) {
106  return lhs.high < rhs.high;
107  }
108  return lhs.low < rhs.low;
109 }
110 
111 template <typename HL, typename LL, typename HR, typename LR>
114 {
116  if (result.low < rhs.low) {
117  result.high += 1;
118  }
119  return result;
120 }
121 
122 template <typename HL, typename LL, typename HR, typename LR>
125 {
127  if (result.low > lhs.low) {
128  result.high -= 1;
129  }
130  return result;
131 }
132 
133 
134 template <typename HL, typename LL, typename HR, typename LR>
137 {
138  // Split each 128-bit integer into 4 32-bit integers, and then do the
139  // multiplications by hand as follow:
140  // lhs a b c d
141  // rhs e f g h
142  // -----------
143  // ah bh ch dh
144  // bg cg dg
145  // cf df
146  // de
147  // The result is stored in 2 64bit integers, high and low.
148 
149  const uint64_t LOW = 0x00000000FFFFFFFFLL;
150  const uint64_t HIGH = 0xFFFFFFFF00000000LL;
151 
152  uint64_t d = lhs.low & LOW;
153  uint64_t c = (lhs.low & HIGH) >> 32LL;
154  uint64_t b = lhs.high & LOW;
155  uint64_t a = (lhs.high & HIGH) >> 32LL;
156 
157  uint64_t h = rhs.low & LOW;
158  uint64_t g = (rhs.low & HIGH) >> 32LL;
159  uint64_t f = rhs.high & LOW;
160  uint64_t e = (rhs.high & HIGH) >> 32LL;
161 
162  // Compute the low 32 bits of low
163  uint64_t acc = d * h;
164  uint64_t low = acc & LOW;
165  // Compute the high 32 bits of low. Add a carry every time we wrap around
166  acc >>= 32LL;
167  uint64_t carry = 0;
168  uint64_t acc2 = acc + c * h;
169  if (acc2 < acc) {
170  carry++;
171  }
172  acc = acc2 + d * g;
173  if (acc < acc2) {
174  carry++;
175  }
176  low |= (acc << 32LL);
177 
178  // Carry forward the high bits of acc to initiate the computation of the
179  // low 32 bits of high
180  acc2 = (acc >> 32LL) | (carry << 32LL);
181  carry = 0;
182 
183  acc = acc2 + b * h;
184  if (acc < acc2) {
185  carry++;
186  }
187  acc2 = acc + c * g;
188  if (acc2 < acc) {
189  carry++;
190  }
191  acc = acc2 + d * f;
192  if (acc < acc2) {
193  carry++;
194  }
195  uint64_t high = acc & LOW;
196 
197  // Start to compute the high 32 bits of high.
198  acc2 = (acc >> 32LL) | (carry << 32LL);
199 
200  acc = acc2 + a * h;
201  acc2 = acc + b * g;
202  acc = acc2 + c * f;
203  acc2 = acc + d * e;
204  high |= (acc2 << 32LL);
205 
206  return TensorUInt128<uint64_t, uint64_t>(high, low);
207 }
208 
209 template <typename HL, typename LL, typename HR, typename LR>
212 {
213  if (rhs == TensorUInt128<static_val<0>, static_val<1> >(1)) {
214  return TensorUInt128<uint64_t, uint64_t>(lhs.high, lhs.low);
215  } else if (lhs < rhs) {
217  } else {
218  // calculate the biggest power of 2 times rhs that's less than or equal to lhs
222  while (lhs >= d) {
223  tmp = tmp - d;
224  d = d + d;
225  power2 = power2 + power2;
226  }
227 
230  while (power2 != TensorUInt128<static_val<0>, static_val<0> >(0)) {
231  if (tmp >= d) {
232  tmp = tmp - d;
233  result = result + power2;
234  }
235  // Shift right
236  power2 = TensorUInt128<uint64_t, uint64_t>(power2.high >> 1, (power2.low >> 1) | (power2.high << 63));
237  d = TensorUInt128<uint64_t, uint64_t>(d.high >> 1, (d.low >> 1) | (d.high << 63));
238  }
239 
240  return result;
241  }
242 }
243 
244 
245 } // namespace internal
246 } // namespace Eigen
247 
248 
249 #endif // EIGEN_CXX11_TENSOR_TENSOR_UINT128_H
static EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE T operator/(const T &numerator, const TensorIntDivisor< T, div_gt_one > &divisor)
Definition: TensorIntDiv.h:255
#define EIGEN_ALWAYS_INLINE
Definition: Macros.h:932
#define EIGEN_STRONG_INLINE
Definition: Macros.h:917
EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE TensorUInt128< uint64_t, uint64_t > operator-(const TensorUInt128< HL, LL > &lhs, const TensorUInt128< HR, LR > &rhs)
Scalar * b
Definition: benchVecAdd.cpp:17
EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE LOW lower() const
Definition: TensorUInt128.h:68
int n
Scalar Scalar * c
Definition: benchVecAdd.cpp:17
Namespace containing all symbols from the Eigen library.
Definition: jet.h:637
EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool operator==(const TensorUInt128< HL, LL > &lhs, const TensorUInt128< HR, LR > &rhs)
Definition: TensorUInt128.h:79
Holds information about the various numeric (i.e. scalar) types allowed by Eigen. ...
Definition: NumTraits.h:232
#define EIGEN_STATIC_ASSERT(CONDITION, MSG)
Definition: StaticAssert.h:127
EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE HIGH upper() const
Definition: TensorUInt128.h:71
EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE static_val()
Definition: TensorUInt128.h:22
void g(const string &key, int i)
Definition: testBTree.cpp:41
EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE TensorUInt128(const TensorUInt128< OTHER_HIGH, OTHER_LOW > &other)
Definition: TensorUInt128.h:40
EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool operator!=(const TensorUInt128< HL, LL > &lhs, const TensorUInt128< HR, LR > &rhs)
Definition: TensorUInt128.h:86
static const uint64_t value
Definition: TensorUInt128.h:19
Values result
EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE static_val(const T &v)
Definition: TensorUInt128.h:25
#define eigen_assert(x)
Definition: Macros.h:1037
Array< int, Dynamic, 1 > v
unsigned __int64 uint64_t
Definition: ms_stdint.h:95
Point2(* f)(const Point3 &, OptionalJacobian< 2, 3 >)
Array< double, 1, 3 > e(1./3., 0.5, 2.)
static EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE TensorUInt128< uint64_t, uint64_t > operator*(const TensorUInt128< HL, LL > &lhs, const TensorUInt128< HR, LR > &rhs)
#define EIGEN_DEVICE_FUNC
Definition: Macros.h:976
const double h
EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE TensorUInt128(const T &x)
Definition: TensorUInt128.h:57
EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE TensorUInt128< uint64_t, uint64_t > operator+(const TensorUInt128< HL, LL > &lhs, const TensorUInt128< HR, LR > &rhs)
EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool operator>=(const TensorUInt128< HL, LL > &lhs, const TensorUInt128< HR, LR > &rhs)
Definition: TensorUInt128.h:93
EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE TensorUInt128(HIGH y, LOW x)
Definition: TensorUInt128.h:63
Generic expression where a coefficient-wise unary operator is applied to an expression.
Definition: CwiseUnaryOp.h:55
set noclip points set clip one set noclip two set bar set border lt lw set xdata set ydata set zdata set x2data set y2data set boxwidth set dummy x
#define EIGEN_UNUSED_VARIABLE(var)
Definition: Macros.h:1076


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:37:44