Eigen-unsupported  5.0.1-dev+284dcc12
 
Loading...
Searching...
No Matches
TensorUInt128.h
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// IWYU pragma: private
14#include "./InternalHeaderCheck.h"
15
16namespace Eigen {
17namespace internal {
18
19template <uint64_t n>
20struct static_val {
21 static const uint64_t value = n;
22 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE operator uint64_t() const { return n; }
23
24 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE static_val() {}
25
26 template <typename T>
27 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE static_val(const T& v) {
28 EIGEN_UNUSED_VARIABLE(v);
29 eigen_assert(v == n);
30 }
31};
32
33template <typename HIGH = uint64_t, typename LOW = uint64_t>
34struct TensorUInt128 {
35 HIGH high;
36 LOW low;
37
38 template <typename OTHER_HIGH, typename OTHER_LOW>
39 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE TensorUInt128(const TensorUInt128<OTHER_HIGH, OTHER_LOW>& other)
40 : 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>
46 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE TensorUInt128& operator=(const TensorUInt128<OTHER_HIGH, OTHER_LOW>& other) {
47 EIGEN_STATIC_ASSERT(sizeof(OTHER_HIGH) <= sizeof(HIGH), YOU_MADE_A_PROGRAMMING_MISTAKE);
48 EIGEN_STATIC_ASSERT(sizeof(OTHER_LOW) <= sizeof(LOW), YOU_MADE_A_PROGRAMMING_MISTAKE);
49 high = other.high;
50 low = other.low;
51 return *this;
52 }
53
54 template <typename T>
55 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE explicit TensorUInt128(const T& x) : high(0), low(x) {
56 eigen_assert(
57 (static_cast<std::conditional_t<sizeof(T) == 8, uint64_t, uint32_t>>(x) <= NumTraits<uint64_t>::highest()));
58 eigen_assert(x >= 0);
59 }
60
61 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE TensorUInt128(HIGH y, LOW x) : high(y), low(x) {}
62
63 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE operator LOW() const { return low; }
64 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE LOW lower() const { return low; }
65 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE HIGH upper() const { return high; }
66};
67
68template <typename HL, typename LL, typename HR, typename LR>
69EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool operator==(const TensorUInt128<HL, LL>& lhs,
70 const TensorUInt128<HR, LR>& rhs) {
71 return (lhs.high == rhs.high) && (lhs.low == rhs.low);
72}
73
74template <typename HL, typename LL, typename HR, typename LR>
75EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool operator!=(const TensorUInt128<HL, LL>& lhs,
76 const TensorUInt128<HR, LR>& rhs) {
77 return (lhs.high != rhs.high) || (lhs.low != rhs.low);
78}
79
80template <typename HL, typename LL, typename HR, typename LR>
81EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool operator>=(const TensorUInt128<HL, LL>& lhs,
82 const TensorUInt128<HR, LR>& rhs) {
83 if (lhs.high != rhs.high) {
84 return lhs.high > rhs.high;
85 }
86 return lhs.low >= rhs.low;
87}
88
89template <typename HL, typename LL, typename HR, typename LR>
90EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool operator<(const TensorUInt128<HL, LL>& lhs,
91 const TensorUInt128<HR, LR>& rhs) {
92 if (lhs.high != rhs.high) {
93 return lhs.high < rhs.high;
94 }
95 return lhs.low < rhs.low;
96}
97
98template <typename HL, typename LL, typename HR, typename LR>
99EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE TensorUInt128<uint64_t, uint64_t> operator+(const TensorUInt128<HL, LL>& lhs,
100 const TensorUInt128<HR, LR>& rhs) {
101 TensorUInt128<uint64_t, uint64_t> result(lhs.high + rhs.high, lhs.low + rhs.low);
102 if (result.low < rhs.low) {
103 result.high += 1;
104 }
105 return result;
106}
107
108template <typename HL, typename LL, typename HR, typename LR>
109EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE TensorUInt128<uint64_t, uint64_t> operator-(const TensorUInt128<HL, LL>& lhs,
110 const TensorUInt128<HR, LR>& rhs) {
111 TensorUInt128<uint64_t, uint64_t> result(lhs.high - rhs.high, lhs.low - rhs.low);
112 if (result.low > lhs.low) {
113 result.high -= 1;
114 }
115 return result;
116}
117
118template <typename HL, typename LL, typename HR, typename LR>
119static EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE TensorUInt128<uint64_t, uint64_t> operator*(
120 const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs) {
121 // Split each 128-bit integer into 4 32-bit integers, and then do the
122 // multiplications by hand as follow:
123 // lhs a b c d
124 // rhs e f g h
125 // -----------
126 // ah bh ch dh
127 // bg cg dg
128 // cf df
129 // de
130 // The result is stored in 2 64bit integers, high and low.
131
132 const uint64_t LOW = 0x00000000FFFFFFFFLL;
133 const uint64_t HIGH = 0xFFFFFFFF00000000LL;
134
135 uint64_t d = lhs.low & LOW;
136 uint64_t c = (lhs.low & HIGH) >> 32LL;
137 uint64_t b = lhs.high & LOW;
138 uint64_t a = (lhs.high & HIGH) >> 32LL;
139
140 uint64_t h = rhs.low & LOW;
141 uint64_t g = (rhs.low & HIGH) >> 32LL;
142 uint64_t f = rhs.high & LOW;
143 uint64_t e = (rhs.high & HIGH) >> 32LL;
144
145 // Compute the low 32 bits of low
146 uint64_t acc = d * h;
147 uint64_t low = acc & LOW;
148 // Compute the high 32 bits of low. Add a carry every time we wrap around
149 acc >>= 32LL;
150 uint64_t carry = 0;
151 uint64_t acc2 = acc + c * h;
152 if (acc2 < acc) {
153 carry++;
154 }
155 acc = acc2 + d * g;
156 if (acc < acc2) {
157 carry++;
158 }
159 low |= (acc << 32LL);
160
161 // Carry forward the high bits of acc to initiate the computation of the
162 // low 32 bits of high
163 acc2 = (acc >> 32LL) | (carry << 32LL);
164 carry = 0;
165
166 acc = acc2 + b * h;
167 if (acc < acc2) {
168 carry++;
169 }
170 acc2 = acc + c * g;
171 if (acc2 < acc) {
172 carry++;
173 }
174 acc = acc2 + d * f;
175 if (acc < acc2) {
176 carry++;
177 }
178 uint64_t high = acc & LOW;
179
180 // Start to compute the high 32 bits of high.
181 acc2 = (acc >> 32LL) | (carry << 32LL);
182
183 acc = acc2 + a * h;
184 acc2 = acc + b * g;
185 acc = acc2 + c * f;
186 acc2 = acc + d * e;
187 high |= (acc2 << 32LL);
188
189 return TensorUInt128<uint64_t, uint64_t>(high, low);
190}
191
192template <typename HL, typename LL, typename HR, typename LR>
193static EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE TensorUInt128<uint64_t, uint64_t> operator/(
194 const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs) {
195 if (rhs == TensorUInt128<static_val<0>, static_val<1>>(1)) {
196 return TensorUInt128<uint64_t, uint64_t>(lhs.high, lhs.low);
197 } else if (lhs < rhs) {
198 return TensorUInt128<uint64_t, uint64_t>(0);
199 } else {
200 // calculate the biggest power of 2 times rhs that's less than or equal to lhs
201 TensorUInt128<uint64_t, uint64_t> power2(1);
202 TensorUInt128<uint64_t, uint64_t> d(rhs);
203 TensorUInt128<uint64_t, uint64_t> tmp(lhs - d);
204 while (lhs >= d) {
205 tmp = tmp - d;
206 d = d + d;
207 power2 = power2 + power2;
208 }
209
210 tmp = TensorUInt128<uint64_t, uint64_t>(lhs.high, lhs.low);
211 TensorUInt128<uint64_t, uint64_t> result(0);
212 while (power2 != TensorUInt128<static_val<0>, static_val<0>>(0)) {
213 if (tmp >= d) {
214 tmp = tmp - d;
215 result = result + power2;
216 }
217 // Shift right
218 power2 = TensorUInt128<uint64_t, uint64_t>(power2.high >> 1, (power2.low >> 1) | (power2.high << 63));
219 d = TensorUInt128<uint64_t, uint64_t>(d.high >> 1, (d.low >> 1) | (d.high << 63));
220 }
221
222 return result;
223 }
224}
225
226} // namespace internal
227} // namespace Eigen
228
229#endif // EIGEN_CXX11_TENSOR_TENSOR_UINT128_H
Eigen
Namespace containing all symbols from the Eigen library.