Eigen-unsupported  5.0.1-dev+284dcc12
 
Loading...
Searching...
No Matches
TensorIntDiv.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2014 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_INTDIV_H
11#define EIGEN_CXX11_TENSOR_TENSOR_INTDIV_H
12
13// IWYU pragma: private
14#include "./InternalHeaderCheck.h"
15
16namespace Eigen {
17
18namespace internal {
19
20// Note: result is undefined if val == 0
21template <typename T>
22EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE std::enable_if_t<sizeof(T) == 4, int> count_leading_zeros(const T val) {
23#ifdef EIGEN_GPU_COMPILE_PHASE
24 return __clz(val);
25#elif defined(SYCL_DEVICE_ONLY)
26 return cl::sycl::clz(val);
27#elif EIGEN_COMP_MSVC
28 unsigned long index;
29 _BitScanReverse(&index, val);
30 return 31 - index;
31#else
32 EIGEN_STATIC_ASSERT(sizeof(unsigned long long) == 8, YOU_MADE_A_PROGRAMMING_MISTAKE);
33 return __builtin_clz(static_cast<uint32_t>(val));
34#endif
35}
36
37template <typename T>
38EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE std::enable_if_t<sizeof(T) == 8, int> count_leading_zeros(const T val) {
39#ifdef EIGEN_GPU_COMPILE_PHASE
40 return __clzll(val);
41#elif defined(SYCL_DEVICE_ONLY)
42 return static_cast<int>(cl::sycl::clz(val));
43#elif EIGEN_COMP_MSVC && EIGEN_ARCH_x86_64
44 unsigned long index;
45 _BitScanReverse64(&index, val);
46 return 63 - index;
47#elif EIGEN_COMP_MSVC
48 // MSVC's _BitScanReverse64 is not available for 32bits builds.
49 unsigned int lo = (unsigned int)(val & 0xffffffff);
50 unsigned int hi = (unsigned int)((val >> 32) & 0xffffffff);
51 int n;
52 if (hi == 0)
53 n = 32 + count_leading_zeros<unsigned int>(lo);
54 else
55 n = count_leading_zeros<unsigned int>(hi);
56 return n;
57#else
58 EIGEN_STATIC_ASSERT(sizeof(unsigned long long) == 8, YOU_MADE_A_PROGRAMMING_MISTAKE);
59 return __builtin_clzll(static_cast<uint64_t>(val));
60#endif
61}
62
63template <typename T>
64struct UnsignedTraits {
65 typedef std::conditional_t<sizeof(T) == 8, uint64_t, uint32_t> type;
66};
67
68template <typename T>
69struct DividerTraits {
70 typedef typename UnsignedTraits<T>::type type;
71 static constexpr int N = sizeof(T) * 8;
72};
73
74template <typename T>
75EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE uint32_t muluh(const uint32_t a, const T b) {
76#if defined(EIGEN_GPU_COMPILE_PHASE)
77 return __umulhi(a, b);
78#elif defined(SYCL_DEVICE_ONLY)
79 return cl::sycl::mul_hi(a, static_cast<uint32_t>(b));
80#else
81 return (static_cast<uint64_t>(a) * b) >> 32;
82#endif
83}
84
85template <typename T>
86EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE uint64_t muluh(const uint64_t a, const T b) {
87#if defined(EIGEN_GPU_COMPILE_PHASE)
88 return __umul64hi(a, b);
89#elif defined(SYCL_DEVICE_ONLY)
90 return cl::sycl::mul_hi(a, static_cast<uint64_t>(b));
91#elif EIGEN_COMP_MSVC && (EIGEN_ARCH_x86_64 || EIGEN_ARCH_ARM64)
92 return __umulh(a, static_cast<uint64_t>(b));
93#elif EIGEN_HAS_BUILTIN_INT128
94 __uint128_t v = static_cast<__uint128_t>(a) * static_cast<__uint128_t>(b);
95 return static_cast<uint64_t>(v >> 64);
96#else
97 return (TensorUInt128<static_val<0>, uint64_t>(a) * TensorUInt128<static_val<0>, uint64_t>(b)).upper();
98#endif
99}
100
101template <int N, typename T>
102struct DividerHelper {
103 static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE uint32_t computeMultiplier(const int log_div, const T divider) {
104 EIGEN_STATIC_ASSERT(N == 32, YOU_MADE_A_PROGRAMMING_MISTAKE);
105 return static_cast<uint32_t>((static_cast<uint64_t>(1) << (N + log_div)) / divider -
106 (static_cast<uint64_t>(1) << N) + 1);
107 }
108};
109
110template <typename T>
111struct DividerHelper<64, T> {
112 static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE uint64_t computeMultiplier(const int log_div, const T divider) {
113#if EIGEN_HAS_BUILTIN_INT128 && !defined(EIGEN_GPU_COMPILE_PHASE) && !defined(SYCL_DEVICE_ONLY)
114 return static_cast<uint64_t>((static_cast<__uint128_t>(1) << (64 + log_div)) / static_cast<__uint128_t>(divider) -
115 (static_cast<__uint128_t>(1) << 64) + 1);
116#else
117 const uint64_t shift = 1ULL << log_div;
118 TensorUInt128<uint64_t, uint64_t> result =
119 TensorUInt128<uint64_t, static_val<0> >(shift, 0) / TensorUInt128<static_val<0>, uint64_t>(divider) -
120 TensorUInt128<static_val<1>, static_val<0> >(1, 0) + TensorUInt128<static_val<0>, static_val<1> >(1);
121 return static_cast<uint64_t>(result);
122#endif
123 }
124};
125
137template <typename T, bool div_gt_one = false>
138struct TensorIntDivisor {
139 public:
140 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE TensorIntDivisor() {
141 multiplier = 0;
142 shift1 = 0;
143 shift2 = 0;
144 }
145
146 // Must have 0 < divider < 2^31. This is relaxed to
147 // 0 < divider < 2^63 when using 64-bit indices on platforms that support
148 // the __uint128_t type.
149 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE TensorIntDivisor(const T divider) {
150 const int N = DividerTraits<T>::N;
151 eigen_assert(static_cast<typename UnsignedTraits<T>::type>(divider) < NumTraits<UnsignedType>::highest() / 2);
152 eigen_assert(divider > 0);
153
154 // fast ln2
155 const int leading_zeros = count_leading_zeros(static_cast<UnsignedType>(divider));
156 int log_div = N - leading_zeros;
157 // if divider is a power of two then log_div is 1 more than it should be.
158 if ((static_cast<typename UnsignedTraits<T>::type>(1) << (log_div - 1)) ==
159 static_cast<typename UnsignedTraits<T>::type>(divider))
160 log_div--;
161
162 multiplier = DividerHelper<N, T>::computeMultiplier(log_div, divider);
163 shift1 = log_div > 1 ? 1 : log_div;
164 shift2 = log_div > 1 ? log_div - 1 : 0;
165 }
166
167 // Must have 0 <= numerator. On platforms that don't support the __uint128_t
168 // type numerator should also be less than 2^32-1.
169 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE T divide(const T numerator) const {
170 eigen_assert(static_cast<typename UnsignedTraits<T>::type>(numerator) < NumTraits<UnsignedType>::highest() / 2);
171 // eigen_assert(numerator >= 0); // this is implicitly asserted by the line above
172
173 UnsignedType t1 = muluh(multiplier, numerator);
174 UnsignedType t = (static_cast<UnsignedType>(numerator) - t1) >> shift1;
175 return (t1 + t) >> shift2;
176 }
177
178 private:
179 typedef typename DividerTraits<T>::type UnsignedType;
180 UnsignedType multiplier;
181 int32_t shift1;
182 int32_t shift2;
183};
184
185// Optimized version for signed 32 bit integers.
186// Derived from Hacker's Delight.
187// Only works for divisors strictly greater than one
188template <>
189class TensorIntDivisor<int32_t, true> {
190 public:
191 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE TensorIntDivisor() {
192 magic = 0;
193 shift = 0;
194 }
195 // Must have 2 <= divider
196 EIGEN_DEVICE_FUNC TensorIntDivisor(int32_t divider) {
197 eigen_assert(divider >= 2);
198 calcMagic(divider);
199 }
200
201 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE int divide(const int32_t n) const {
202#ifdef EIGEN_GPU_COMPILE_PHASE
203 return (__umulhi(magic, n) >> shift);
204#elif defined(SYCL_DEVICE_ONLY)
205 return (cl::sycl::mul_hi(magic, static_cast<uint32_t>(n)) >> shift);
206#else
207 uint64_t v = static_cast<uint64_t>(magic) * static_cast<uint64_t>(n);
208 return (static_cast<uint32_t>(v >> 32) >> shift);
209#endif
210 }
211
212 private:
213 // Compute the magic numbers. See Hacker's Delight section 10 for an in
214 // depth explanation.
215 EIGEN_DEVICE_FUNC void calcMagic(int32_t d) {
216 const unsigned two31 = 0x80000000; // 2**31.
217 unsigned ad = d;
218 unsigned t = two31 + (ad >> 31);
219 unsigned anc = t - 1 - t % ad; // Absolute value of nc.
220 int p = 31; // Init. p.
221 unsigned q1 = two31 / anc; // Init. q1 = 2**p/|nc|.
222 unsigned r1 = two31 - q1 * anc; // Init. r1 = rem(2**p, |nc|).
223 unsigned q2 = two31 / ad; // Init. q2 = 2**p/|d|.
224 unsigned r2 = two31 - q2 * ad; // Init. r2 = rem(2**p, |d|).
225 unsigned delta = 0;
226 do {
227 p = p + 1;
228 q1 = 2 * q1; // Update q1 = 2**p/|nc|.
229 r1 = 2 * r1; // Update r1 = rem(2**p, |nc|).
230 if (r1 >= anc) { // (Must be an unsigned
231 q1 = q1 + 1; // comparison here).
232 r1 = r1 - anc;
233 }
234 q2 = 2 * q2; // Update q2 = 2**p/|d|.
235 r2 = 2 * r2; // Update r2 = rem(2**p, |d|).
236 if (r2 >= ad) { // (Must be an unsigned
237 q2 = q2 + 1; // comparison here).
238 r2 = r2 - ad;
239 }
240 delta = ad - r2;
241 } while (q1 < delta || (q1 == delta && r1 == 0));
242
243 magic = (unsigned)(q2 + 1);
244 shift = p - 32;
245 }
246
247 uint32_t magic;
248 int32_t shift;
249};
250
251template <typename T, bool div_gt_one>
252EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE T operator/(const T& numerator, const TensorIntDivisor<T, div_gt_one>& divisor) {
253 return divisor.divide(numerator);
254}
255
256} // end namespace internal
257} // end namespace Eigen
258
259#endif // EIGEN_CXX11_TENSOR_TENSOR_INTDIV_H
Eigen
Namespace containing all symbols from the Eigen library.