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