12#ifndef EIGEN_INTEGER_DIVISION_H
13#define EIGEN_INTEGER_DIVISION_H
16#include "./InternalHeaderCheck.h"
57EIGEN_DEVICE_FUNC
constexpr bool is_negative(
const T& x, std::true_type) {
61EIGEN_DEVICE_FUNC
constexpr bool is_negative(
const T&, std::false_type) {
65EIGEN_DEVICE_FUNC
constexpr bool is_negative(
const T& x) {
66 return is_negative(x, std::is_signed<T>());
71EIGEN_DEVICE_FUNC
constexpr std::make_unsigned_t<T> unsigned_abs(
const T& x) {
72 using Unsigned = std::make_unsigned_t<T>;
73 return is_negative(x) ?
static_cast<Unsigned
>(Unsigned(0) -
static_cast<Unsigned
>(x)) :
static_cast<Unsigned
>(x);
77template <
typename Un
signed, std::enable_if_t<sizeof(Un
signed) == 8,
int> = 0>
78EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Unsigned umulhi(Unsigned a, Unsigned b) {
79#if defined(EIGEN_GPU_COMPILE_PHASE)
80 return __umul64hi(a, b);
81#elif defined(EIGEN_SYCL_DEVICE_ONLY)
82 return cl::sycl::mul_hi(
static_cast<uint64_t
>(a),
static_cast<uint64_t
>(b));
83#elif EIGEN_COMP_MSVC && (EIGEN_ARCH_x86_64 || EIGEN_ARCH_ARM64)
85#elif EIGEN_HAS_BUILTIN_INT128
86 return static_cast<Unsigned
>((
static_cast<__uint128_t
>(a) * b) >> 64);
89 Unsigned a0 = a & 0xffffffffu, a1 = a >> 32, b0 = b & 0xffffffffu, b1 = b >> 32;
90 Unsigned u = a1 * b0 + ((a0 * b0) >> 32);
91 Unsigned w = a0 * b1 + (u & 0xffffffffu);
92 return a1 * b1 + (u >> 32) + (w >> 32);
97template <
typename Un
signed, std::enable_if_t<(sizeof(Un
signed) < 8),
int> = 0>
98EIGEN_DEVICE_FUNC Un
signed div_shifted(Un
signed r, Un
signed d) {
99 return static_cast<Un
signed>((static_cast<u
int64_t>(r) << (CHAR_BIT * sizeof(Un
signed))) / d);
101template <
typename Un
signed, std::enable_if_t<sizeof(Un
signed) == 8,
int> = 0>
102EIGEN_DEVICE_FUNC Unsigned div_shifted(Unsigned r, Unsigned d) {
103#if EIGEN_HAS_BUILTIN_INT128 && !defined(EIGEN_GPU_COMPILE_PHASE) && !defined(__SYCL_DEVICE_ONLY__)
104 return static_cast<Unsigned
>((
static_cast<__uint128_t
>(r) << 64) / d);
108 for (
int i = 0; i < 64; ++i) {
109 bool carry = (r >> 63) != 0;
112 if (carry || r >= d) {
123template <
typename Un
signed>
124struct use_multiply_add : std::integral_constant<bool, (
sizeof(Unsigned) < 8) || EIGEN_ARCH_i386_OR_x86_64> {};
128template <
typename Un
signed>
129using double_width_t = std::conditional_t<(
sizeof(Unsigned) < 4), uint32_t, uint64_t>;
132template <
typename Un
signed, std::enable_if_t<sizeof(Un
signed) == 8,
int> = 0>
133EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Unsigned umuladdhi(Unsigned a, Unsigned b, Unsigned c) {
134#if EIGEN_HAS_BUILTIN_INT128 && !defined(EIGEN_GPU_COMPILE_PHASE) && !defined(__SYCL_DEVICE_ONLY__)
135 return static_cast<Unsigned
>((
static_cast<__uint128_t
>(a) * b + c) >> 64);
137 Unsigned low = a * b;
138 return umulhi(a, b) +
static_cast<Unsigned
>(
static_cast<Unsigned
>(low + c) < low);
144template <
typename Un
signed, std::enable_if_t<(sizeof(Un
signed) < 8),
int> = 0>
145EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Un
signed udiv(Un
signed a, Un
signed magic, Un
signed addend,
int shift) {
146 using W
ide =
double_w
idth_t<Un
signed>;
147 return static_cast<Un
signed>((static_cast<W
ide>(a) * static_cast<W
ide>(magic) + static_cast<W
ide>(addend)) >>
148 (CHAR_BIT *
sizeof(Unsigned) + shift));
150template <
typename Un
signed, std::enable_if_t<sizeof(Un
signed) == 8 && use_multiply_add<Un
signed>::value,
int> = 0>
151EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Unsigned udiv(Unsigned a, Unsigned magic, Unsigned addend,
int shift) {
152 return umuladdhi(a, magic, addend) >> shift;
154template <typename Unsigned, std::enable_if_t<!use_multiply_add<Unsigned>::value,
int> = 0>
155EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Unsigned udiv(Unsigned a, Unsigned magic, Unsigned ,
int shift) {
156 Unsigned t = umulhi(a, magic);
157 int shift1 = shift > 0 ? 1 : 0;
158 return (t + ((a - t) >> shift1)) >> (shift - shift1);
161template <typename Unsigned, bool MultiplyAdd = use_multiply_add<Unsigned>::value>
164template <
typename Un
signed>
165struct params<Unsigned, true> {
166 static_assert(std::is_unsigned<Unsigned>::value,
"params takes the unsigned type of the numerators");
167 static constexpr int kBits = CHAR_BIT *
sizeof(Unsigned);
169 template <
typename Un
signedDivisor>
170 EIGEN_DEVICE_FUNC
explicit params(UnsignedDivisor d) : magic(0), addend(0), shift(0) {
171 eigen_assert(d != 0 &&
"IntDivider: division by zero");
173 if (d <=
static_cast<UnsignedDivisor
>(NumTraits<Unsigned>::highest())) {
174 using Wide = std::conditional_t<(
sizeof(Unsigned) < 4), uint32_t, Unsigned>;
175 Unsigned du =
static_cast<Unsigned
>(d);
176 int f = log_2_impl<Unsigned>::run_floor(du);
177 Wide power = Wide(1) << f;
179 magic = addend = NumTraits<Unsigned>::highest();
180 }
else if (Wide(du) == power) {
181 magic =
static_cast<Unsigned
>(Wide(1) << (kBits - 1));
184 Unsigned q = div_shifted(
static_cast<Unsigned
>(power), du);
186 Unsigned r =
static_cast<Unsigned
>(Wide(0) - Wide(q) * Wide(du));
187 bool round_up = Wide(du) - Wide(r) <= power;
188 magic =
static_cast<Unsigned
>(q + (round_up ? 1 : 0));
189 addend = round_up ? Unsigned(0) : q;
200template <
typename Un
signed>
201struct params<Unsigned, false> {
202 static_assert(std::is_unsigned<Unsigned>::value,
"params takes the unsigned type of the numerators");
203 static constexpr int kBits = CHAR_BIT *
sizeof(Unsigned);
205 template <
typename Un
signedDivisor>
206 EIGEN_DEVICE_FUNC
explicit params(UnsignedDivisor d) : magic(1), addend(0), shift(kBits) {
207 eigen_assert(d != 0 &&
"IntDivider: division by zero");
209 if (d <=
static_cast<UnsignedDivisor
>(NumTraits<Unsigned>::highest())) {
210 Unsigned du =
static_cast<Unsigned
>(d);
211 shift = log_2_impl<Unsigned>::run_ceil(du);
214 shift == kBits ?
static_cast<Unsigned
>(Unsigned(0) - du) : static_cast<Unsigned>((Unsigned(1) << shift) - du);
215 magic =
static_cast<Unsigned
>(div_shifted(r, du) + 1);
228template <
typename Scalar>
229struct signed_params {
230 static constexpr int kBits = CHAR_BIT *
sizeof(Scalar);
232 template <
typename Un
signedDivisor>
233 EIGEN_DEVICE_FUNC
explicit signed_params(UnsignedDivisor d) {
234 eigen_assert(d != 0 &&
"IntDivider: division by zero");
235 using Unsigned = std::make_unsigned_t<Scalar>;
237 bool fits = d <= static_cast<UnsignedDivisor>(NumTraits<Unsigned>::highest());
238 uint64_t magnitude = fits ?
static_cast<uint64_t
>(d) : uint64_t(1) << kBits;
239 shift = !fits ? kBits - 1 : numext::maxi(log_2_impl<Unsigned>::run_ceil(
static_cast<Unsigned
>(d)), 1) - 1;
240 uint64_t full_magic = (uint64_t(1) << (kBits + shift)) / magnitude + 1;
241 magic =
static_cast<uint32_t
>(full_magic);
242 total_shift = (full_magic >> 32) != 0 ? 0 : kBits + shift;
255template <
typename Scalar, std::enable_if_t<sizeof(Scalar) == 4,
int> = 0>
256EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Scalar sdiv(Scalar a, uint32_t magic,
int total_shift, Scalar divisor_sign) {
257 uint32_t a_sign =
static_cast<uint32_t
>(a >> 31);
258 uint32_t abs_a = (
static_cast<uint32_t
>(a) ^ a_sign) - a_sign;
259 uint32_t quotient =
static_cast<uint32_t
>((
static_cast<uint64_t
>(abs_a) * magic) >> total_shift);
260 uint32_t sign = a_sign ^
static_cast<uint32_t
>(divisor_sign);
261 return static_cast<Scalar
>((quotient ^ sign) - sign);
263template <
typename Scalar, std::enable_if_t<(sizeof(Scalar) < 4),
int> = 0>
264EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Scalar sdiv(Scalar a, u
int32_t magic,
int total_shift, Scalar divisor_sign) {
265 using Un
signed = std::make_
unsigned_t<Scalar>;
266 int32_t w
ide = static_cast<
int32_t>(a);
267 int32_t product = static_cast<
int32_t>(static_cast<u
int32_t>(w
ide) * magic);
269 static_cast<Un
signed>(static_cast<Un
signed>(product >> total_shift) -
static_cast<Unsigned
>(wide >> 31));
270 Unsigned sign =
static_cast<Unsigned
>(divisor_sign);
271 return static_cast<Scalar
>(
static_cast<Unsigned
>((quotient ^ sign) - sign));
279template <
typename Packet>
280EIGEN_DEVICE_FUNC
inline Packet pudiv_magic(
const Packet& a,
281 std::make_unsigned_t<
typename unpacket_traits<Packet>::type> magic,
282 std::make_unsigned_t<
typename unpacket_traits<Packet>::type> addend,
284 using Scalar =
typename unpacket_traits<Packet>::type;
285 using Unsigned = std::make_unsigned_t<Scalar>;
286 constexpr int kSize = unpacket_traits<Packet>::size;
289 for (
int i = 0; i < kSize; ++i) {
290 lanes[i] =
static_cast<Scalar
>(int_div::udiv(
static_cast<Unsigned
>(lanes[i]), magic, addend, shift));
292 return ploadu<Packet>(lanes);
297template <
typename Packet>
298EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet psdiv_magic(
299 const Packet& a, std::make_unsigned_t<
typename unpacket_traits<Packet>::type> magic,
300 std::make_unsigned_t<
typename unpacket_traits<Packet>::type> addend,
int shift,
const Packet& divisor_sign) {
302 Packet abs_quotient = pudiv_magic(pabs(a), magic, addend, shift);
303 Packet quotient_sign = pxor(psignbit(a), divisor_sign);
304 return psub(pxor(abs_quotient, quotient_sign), quotient_sign);
311template <
typename Packet>
312EIGEN_DEVICE_FUNC
inline Packet psdiv_signed_magic(
const Packet& a, uint32_t magic,
int ,
int total_shift,
313 const Packet& divisor_sign) {
314 using Scalar =
typename unpacket_traits<Packet>::type;
315 constexpr int kSize = unpacket_traits<Packet>::size;
316 Scalar sign = pfirst(divisor_sign);
319 for (
int i = 0; i < kSize; ++i) lanes[i] = int_div::sdiv(lanes[i], magic, total_shift, sign);
320 return ploadu<Packet>(lanes);
323template <typename Scalar, bool IsSigned = std::is_signed<Scalar>::value,
bool SignedMultiply = (
sizeof(Scalar) < 8)>
324struct scalar_int_div_op : int_div::params<Scalar> {
325 using Base = int_div::params<Scalar>;
326 using result_type = Scalar;
328 template <
typename Divisor>
329 EIGEN_DEVICE_FUNC
explicit scalar_int_div_op(
const Divisor& d) : Base(int_div::unsigned_abs(d)) {
330 eigen_assert(!int_div::is_negative(d) &&
"IntDivider: an unsigned numerator needs a positive divisor");
333 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Scalar operator()(
const Scalar& a)
const {
334 return int_div::udiv(a, this->magic, this->addend, this->shift);
336 template <
typename Packet>
337 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet packetOp(
const Packet& a)
const {
338 return pudiv_magic(a, this->magic, this->addend, this->shift);
343template <
typename Scalar>
344struct scalar_int_div_op<Scalar, true, false> : int_div::params<std::make_unsigned_t<Scalar>> {
345 using Unsigned = std::make_unsigned_t<Scalar>;
346 using Base = int_div::params<Unsigned>;
347 using result_type = Scalar;
349 template <
typename Divisor>
350 EIGEN_DEVICE_FUNC
explicit scalar_int_div_op(
const Divisor& d)
351 : Base(int_div::unsigned_abs(d)), divisor_sign(int_div::is_negative(d) ? Scalar(-1) : Scalar(0)) {}
356 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Scalar operator()(
const Scalar& a)
const {
357 Unsigned abs_quotient = int_div::udiv(int_div::unsigned_abs(a), this->magic, this->addend, this->shift);
358 Unsigned quotient_sign = (Unsigned(0) - Unsigned(a < 0)) ^
static_cast<Unsigned
>(divisor_sign);
359 return static_cast<Scalar
>((abs_quotient ^ quotient_sign) - quotient_sign);
361 template <
typename Packet>
362 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet packetOp(
const Packet& a)
const {
363 return psdiv_magic(a, this->magic, this->addend, this->shift, pset1<Packet>(divisor_sign));
370template <
typename Scalar>
371struct scalar_int_div_op<Scalar, true, true> : int_div::signed_params<Scalar> {
372 using Base = int_div::signed_params<Scalar>;
373 using result_type = Scalar;
375 template <
typename Divisor>
376 EIGEN_DEVICE_FUNC
explicit scalar_int_div_op(
const Divisor& d)
377 : Base(int_div::unsigned_abs(d)), divisor_sign(int_div::is_negative(d) ? Scalar(-1) : Scalar(0)) {}
379 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Scalar operator()(
const Scalar& a)
const {
380 return int_div::sdiv(a, this->magic, this->total_shift, divisor_sign);
382 template <
typename Packet>
383 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet packetOp(
const Packet& a)
const {
384 return psdiv_signed_magic(a, this->magic, this->shift, this->total_shift, pset1<Packet>(divisor_sign));
390template <
typename Scalar,
bool IsSigned,
bool SignedMultiply>
391struct functor_traits<scalar_int_div_op<Scalar, IsSigned, SignedMultiply>> {
392 static constexpr int Cost = 2 * NumTraits<Scalar>::MulCost + 5 * NumTraits<Scalar>::AddCost;
393 static constexpr bool PacketAccess = packet_traits<Scalar>::HasFastIntDiv;
439template <
typename Scalar_>
441 EIGEN_STATIC_ASSERT((std::is_integral<Scalar_>::value && !std::is_same<Scalar_, bool>::value),
442 THE_NUMERATOR_TYPE_MUST_BE_A_BUILT_IN_INTEGER)
445 using Scalar = Scalar_;
446 using Functor = internal::scalar_int_div_op<Scalar>;
452 template <
typename Divisor>
453 EIGEN_DEVICE_FUNC
explicit IntDivider(
const Divisor& divisor) : m_functor(divisor) {
454 EIGEN_STATIC_ASSERT((std::is_integral<Divisor>::value && !std::is_same<Divisor, bool>::value),
455 THE_DIVISOR_TYPE_MUST_BE_A_BUILT_IN_INTEGER)
459 template <
typename Divisor>
461 EIGEN_STATIC_ASSERT((std::is_integral<Divisor>::value && !std::is_same<Divisor, bool>::value),
462 THE_DIVISOR_TYPE_MUST_BE_A_BUILT_IN_INTEGER)
463 m_functor = Functor(divisor);
468 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Scalar
divide(
const Scalar& numerator)
const {
return m_functor(numerator); }
471 template <
typename Derived>
475 (std::is_same<typename Derived::Scalar, Scalar>::value),
476 YOU_MIXED_DIFFERENT_NUMERIC_TYPES__YOU_NEED_TO_USE_THE_CAST_METHOD_OF_MATRIXBASE_TO_CAST_NUMERIC_TYPES_EXPLICITLY)
481 EIGEN_DEVICE_FUNC
const Functor&
functor()
const {
return m_functor; }
490template <typename Numerator, typename Scalar, std::enable_if_t<std::is_arithmetic<Numerator>::value,
int> = 0>
495 (std::is_integral<Numerator>::value && (
sizeof(Numerator) <=
sizeof(Scalar) ||
sizeof(Numerator) <=
sizeof(
int))),
496 THE_NUMERATOR_MUST_BE_AN_INTEGER_NO_WIDER_THAN_THE_DIVIDER_SCALAR_OR_INT)
497 return divider.
divide(
static_cast<Scalar
>(numerator));
502template <
typename Scalar>
504 numerator = divider.
divide(numerator);
510template <
typename Derived,
typename Scalar>
513 return divider.
divide(numerators);
Generic expression where a coefficient-wise unary operator is applied to an expression.
Definition CwiseUnaryOp.h:55
Base class for all dense matrices, vectors, and arrays.
Definition DenseBase.h:45
IntDivider()
Definition IntegerDivision.h:449
const Functor & functor() const
Definition IntegerDivision.h:481
Scalar & operator/=(Scalar &numerator, const IntDivider< Scalar > ÷r)
Definition IntegerDivision.h:503
CwiseUnaryOp< internal::scalar_int_div_op< Scalar >, const Derived > operator/(const DenseBase< Derived > &numerators, const IntDivider< Scalar > ÷r)
Definition IntegerDivision.h:511
IntDivider(const Divisor &divisor)
Definition IntegerDivision.h:453
IntDivider & compute(const Divisor &divisor)
Definition IntegerDivision.h:460
Scalar operator/(const Numerator &numerator, const IntDivider< Scalar > ÷r)
Definition IntegerDivision.h:491
Scalar divide(const Scalar &numerator) const
Definition IntegerDivision.h:468
CwiseUnaryOp< Functor, const Derived > divide(const DenseBase< Derived > &numerators) const
Definition IntegerDivision.h:472