blob: 93a4a07c3ed6f634a12b7bbac4e1eb4526a52f11 [file] [edit]
// This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2025 Charlie Schlosser <cs.schlosser@gmail.com>
// Copyright (C) 2026 Rasmus Munk Larsen <rmlarsen@gmail.com>
//
// This Source Code Form is subject to the terms of the Mozilla
// Public License v. 2.0. If a copy of the MPL was not distributed
// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
// SPDX-License-Identifier: MPL-2.0
#include "main.h"
#include <vector>
// Truncating n / d by hardware division of the magnitudes. lowest() / -1 wraps to lowest(), as IntDivider documents.
template <typename Scalar, typename Divisor>
Scalar reference_quotient(Scalar n, Divisor d) {
uint64_t abs_n = internal::int_div::unsigned_abs(n);
uint64_t abs_d = internal::int_div::unsigned_abs(d);
uint64_t abs_q = abs_n / abs_d;
bool negative = internal::int_div::is_negative(n) != internal::int_div::is_negative(d);
return static_cast<Scalar>(negative ? uint64_t(0) - abs_q : abs_q);
}
template <typename Scalar, typename Divisor>
void verify_quotients(const Matrix<Scalar, Dynamic, 1>& numerators, Divisor d) {
IntDivider<Scalar> by(d);
// The expression takes the packet path where packet_traits<Scalar>::HasFastIntDiv; n / by takes the scalar path.
Matrix<Scalar, Dynamic, 1> quotients = numerators / by;
for (Index i = 0; i < numerators.size(); ++i) {
Scalar n = numerators(i);
Scalar expected = reference_quotient(n, d);
VERIFY_IS_EQUAL(quotients(i), expected);
VERIFY_IS_EQUAL(n / by, expected);
}
}
template <typename T>
std::vector<T> special_values() {
using Unsigned = std::make_unsigned_t<T>;
constexpr int kBits = CHAR_BIT * sizeof(T);
std::vector<T> values;
for (int e = 0; e < kBits; ++e) {
Unsigned p = static_cast<Unsigned>(Unsigned(1) << e);
for (Unsigned v : {p, static_cast<Unsigned>(p - 1), static_cast<Unsigned>(p + 1)}) {
values.push_back(static_cast<T>(v));
if (std::is_signed<T>::value) values.push_back(static_cast<T>(Unsigned(0) - v));
}
}
values.insert(values.end(),
{T(3), T(5), T(6), T(7), T(10), T(641), NumTraits<T>::highest(), NumTraits<T>::lowest(),
static_cast<T>(NumTraits<T>::highest() - 1), static_cast<T>(NumTraits<T>::lowest() + 1)});
return values;
}
// Uniform in bit length rather than in value, so that small divisors and numerators occur.
template <typename T>
T random_magnitude() {
using Unsigned = std::make_unsigned_t<T>;
constexpr int kBits = CHAR_BIT * sizeof(T);
Unsigned bits = internal::random<Unsigned>(0, NumTraits<Unsigned>::highest());
return static_cast<T>(bits >> internal::random<int>(0, kBits - 1));
}
// q * d + {-1, 0, 1} mod 2^k for a random q, in uint64_t: 16-bit operands would promote to int, where q * d can
// overflow.
template <typename Scalar, typename Divisor>
Scalar boundary_numerator(Divisor d) {
using Unsigned = std::make_unsigned_t<Scalar>;
uint64_t q = static_cast<uint64_t>(static_cast<int64_t>(random_magnitude<Scalar>()));
uint64_t offset = static_cast<uint64_t>(internal::random<int>(-1, 1));
return static_cast<Scalar>(static_cast<Unsigned>(q * static_cast<uint64_t>(d) + offset));
}
// Numerators on both sides of each quotient boundary q * d, and the extremes.
template <typename Scalar, typename Divisor>
Matrix<Scalar, Dynamic, 1> test_numerators(Divisor d, Index count) {
using Unsigned = std::make_unsigned_t<Scalar>;
Matrix<Scalar, Dynamic, 1> numerators(count);
std::vector<Scalar> special = special_values<Scalar>();
Index i = 0;
for (; i < Index(special.size()) && i < count; ++i) numerators(i) = special[i];
for (; i < count; ++i) {
Scalar n = i % 2 == 0 ? boundary_numerator<Scalar>(d) : random_magnitude<Scalar>();
// -n mod 2^k, since -lowest() overflows.
if (std::is_signed<Scalar>::value && internal::random<bool>()) {
n = static_cast<Scalar>(Unsigned(0) - static_cast<Unsigned>(n));
}
numerators(i) = n;
}
return numerators;
}
template <typename Scalar, typename Divisor>
void test_divisor_type() {
// Odd count: a scalar tail after the packets.
constexpr Index kCount = 1027;
for (Divisor d : special_values<Divisor>()) {
if (d == 0 || (!std::is_signed<Scalar>::value && internal::int_div::is_negative(d))) continue;
verify_quotients(test_numerators<Scalar>(d, kCount), d);
}
for (int repeat = 0; repeat < g_repeat; ++repeat) {
Divisor d = random_magnitude<Divisor>();
if (!std::is_signed<Scalar>::value && internal::int_div::is_negative(d)) d = static_cast<Divisor>(~d);
if (d == 0) d = 1;
verify_quotients(test_numerators<Scalar>(d, kCount), d);
}
}
template <typename Scalar>
void test_random_division() {
test_divisor_type<Scalar, uint8_t>();
test_divisor_type<Scalar, uint16_t>();
test_divisor_type<Scalar, uint32_t>();
test_divisor_type<Scalar, uint64_t>();
// Positive signed divisors are valid for unsigned numerators too.
test_divisor_type<Scalar, int8_t>();
test_divisor_type<Scalar, int16_t>();
test_divisor_type<Scalar, int32_t>();
test_divisor_type<Scalar, int64_t>();
}
// Every numerator against every divisor of Divisor.
template <typename Scalar, typename Divisor>
void test_exhaustive_division() {
using Unsigned = std::make_unsigned_t<Scalar>;
Index count = Index(NumTraits<Unsigned>::highest()) + 1;
Matrix<Scalar, Dynamic, 1> numerators(count);
for (Index i = 0; i < count; ++i) numerators(i) = static_cast<Scalar>(NumTraits<Scalar>::lowest() + i);
constexpr int kDivisorBits = CHAR_BIT * sizeof(Divisor);
constexpr bool kSignedDivisor = std::is_signed<Divisor>::value;
int64_t lowest = kSignedDivisor ? -(int64_t(1) << (kDivisorBits - 1)) : 0;
int64_t highest = (int64_t(1) << (kDivisorBits - int(kSignedDivisor))) - 1;
for (int64_t d = lowest; d <= highest; ++d) {
if (d == 0 || (!std::is_signed<Scalar>::value && d < 0)) continue;
verify_quotients(numerators, static_cast<Divisor>(d));
}
}
// Every special value, then at least as many quotient boundaries, through the kernel a packet at a time. The extremes
// and the boundaries are where a multiplier or an addend that is off by one shows.
template <typename Scalar, typename Packet, typename Divisor>
void verify_packet_kernel(Divisor d) {
constexpr int kSize = internal::unpacket_traits<Packet>::size;
IntDivider<Scalar> by(d);
std::vector<Scalar> numerators = special_values<Scalar>();
size_t special_count = numerators.size();
while (numerators.size() < 2 * special_count || numerators.size() % kSize != 0) {
numerators.push_back(boundary_numerator<Scalar>(d));
}
Scalar result[kSize];
for (size_t next = 0; next < numerators.size(); next += kSize) {
internal::pstoreu(result, by.functor().packetOp(internal::ploadu<Packet>(numerators.data() + next)));
for (int i = 0; i < kSize; ++i) VERIFY_IS_EQUAL(result[i], reference_quotient(numerators[next + i], d));
}
}
// The packet and half-packet kernels directly: an expression need not reach the half packet.
template <typename Scalar, typename Packet>
void test_packet_kernel() {
// Without a packet type the "packet" is a plain Scalar: packetOp is unreachable, since PacketAccess needs a kernel,
// and pabs(lowest()) would overflow where a real packet wraps.
if (std::is_same<Packet, Scalar>::value) return;
for (Scalar d : special_values<Scalar>()) {
if (d == 0) continue;
verify_packet_kernel<Scalar, Packet>(d);
}
for (int repeat = 0; repeat < 10 * g_repeat; ++repeat) {
Scalar d = random_magnitude<Scalar>();
if (d == 0) d = 1;
verify_packet_kernel<Scalar, Packet>(d);
}
// Divisors whose magnitude exceeds the numerators, where every quotient is 0.
if (sizeof(Scalar) < 8) {
for (uint64_t d : {uint64_t(1) << 32, (uint64_t(1) << 32) + 1, ~uint64_t(0), uint64_t(1) << 63}) {
verify_packet_kernel<Scalar, Packet>(d);
}
}
if (sizeof(Scalar) < 4) {
verify_packet_kernel<Scalar, Packet>(static_cast<uint32_t>(uint32_t(1) << (CHAR_BIT * sizeof(Scalar))));
}
}
template <typename Scalar>
void test_packet_kernels() {
test_packet_kernel<Scalar, typename internal::packet_traits<Scalar>::type>();
test_packet_kernel<Scalar, typename internal::packet_traits<Scalar>::half>();
}
template <typename Numerators, typename Quotients, typename Divisor>
void verify_coefficients(const DenseBase<Numerators>& numerators, const DenseBase<Quotients>& quotients, Divisor d) {
for (Index j = 0; j < numerators.cols(); ++j) {
for (Index i = 0; i < numerators.rows(); ++i) {
VERIFY_IS_EQUAL(quotients(i, j), reference_quotient(numerators(i, j), d));
}
}
}
// The quotient expression through dense types other than a plain vector.
template <typename Scalar>
void test_expressions() {
Scalar d = static_cast<Scalar>(random_magnitude<Scalar>() | 1);
IntDivider<Scalar> by(d);
using Array = Eigen::Array<Scalar, Dynamic, Dynamic>;
Array a = Array::Random(37, 29);
Array q = a / by;
Array q_block = by.divide(a.block(1, 2, 33, 21));
verify_coefficients(a, q, d);
verify_coefficients(a.block(1, 2, 33, 21), q_block, d);
using Matrix3 = Matrix<Scalar, 3, 3, RowMajor>;
Matrix3 m = Matrix3::Random();
Matrix3 qm = m.transpose() / by;
verify_coefficients(m.transpose(), qm, d);
// Fixed sizes whose best packet is a half packet or none.
Matrix<Scalar, 2, 1> v2 = Matrix<Scalar, 2, 1>::Random();
Matrix<Scalar, 2, 1> q2 = v2 / by;
Matrix<Scalar, 5, 1> v5 = Matrix<Scalar, 5, 1>::Random();
Matrix<Scalar, 5, 1> q5 = v5 / by;
verify_coefficients(v2, q2, d);
verify_coefficients(v5, q5, d);
// Compound assignment, and plain assignment over its own numerators.
Scalar n = a(0, 0);
VERIFY(&(n /= by) == &n);
VERIFY_IS_EQUAL(n, reference_quotient(a(0, 0), d));
Array in_place = a;
VERIFY(&(in_place /= by) == &in_place);
verify_coefficients(a, in_place, d);
Array self_assigned = a;
self_assigned = self_assigned / by;
verify_coefficients(a, self_assigned, d);
// Temporaries of the writable expressions, leaving the coefficients around them alone.
Array partial = a;
partial.block(1, 2, 33, 21) /= by;
verify_coefficients(a.block(1, 2, 33, 21), partial.block(1, 2, 33, 21), d);
VERIFY((partial.col(0) == a.col(0)).all());
VERIFY((partial.row(0) == a.row(0)).all());
VERIFY((partial.block(34, 2, 3, 21) == a.block(34, 2, 3, 21)).all());
VERIFY((partial.block(1, 23, 33, 6) == a.block(1, 23, 33, 6)).all());
Matrix3 m_in_place = m;
m_in_place.transpose() /= by;
verify_coefficients(m, m_in_place, d);
Matrix<Scalar, 5, 1> v5_in_place = v5;
v5_in_place /= by;
verify_coefficients(v5, v5_in_place, d);
}
// Default construction divides by 1; compute() replaces the divisor.
template <typename Scalar>
void test_compute() {
using Vector = Matrix<Scalar, Dynamic, 1>;
Vector a = Vector::Random(37);
IntDivider<Scalar> by;
VERIFY(Vector(a / by) == a);
for (int repeat = 0; repeat < g_repeat; ++repeat) {
Scalar d = static_cast<Scalar>(random_magnitude<Scalar>() | 1);
VERIFY(&by.compute(d) == &by);
verify_coefficients(a, Vector(a / by), d);
VERIFY_IS_EQUAL(a(0) / by, reference_quotient(a(0), d));
}
// A divisor of a wider type, beyond the range of Scalar.
if (sizeof(Scalar) < 8) {
by.compute(uint64_t(1) << 40);
VERIFY(Vector(a / by) == Vector::Zero(a.size()));
}
}
void test_traits() {
// Types without a kernel stay on the scalar path; a vectorized expression would compute lane-wise fallbacks.
STATIC_CHECK(!(internal::functor_traits<internal::scalar_int_div_op<int16_t>>::PacketAccess));
STATIC_CHECK(!(internal::functor_traits<internal::scalar_int_div_op<uint8_t>>::PacketAccess));
#if defined(EIGEN_VECTORIZE_SSE2) || defined(EIGEN_VECTORIZE_NEON)
STATIC_CHECK((internal::functor_traits<internal::scalar_int_div_op<int32_t>>::PacketAccess));
#endif
#if defined(EIGEN_VECTORIZE_AVX2) && EIGEN_ARCH_i386_OR_x86_64
STATIC_CHECK((internal::functor_traits<internal::scalar_int_div_op<int64_t>>::PacketAccess));
#endif
// AVX-512 leaves the unsigned types unvectorized.
#if (defined(EIGEN_VECTORIZE_SSE2) && !defined(EIGEN_VECTORIZE_AVX512)) || defined(EIGEN_VECTORIZE_NEON)
STATIC_CHECK((internal::functor_traits<internal::scalar_int_div_op<uint32_t>>::PacketAccess));
#endif
#if defined(EIGEN_VECTORIZE_AVX2) && !defined(EIGEN_VECTORIZE_AVX512) && EIGEN_ARCH_i386_OR_x86_64
STATIC_CHECK((internal::functor_traits<internal::scalar_int_div_op<uint64_t>>::PacketAccess));
#endif
// The x86 64-bit kernels take multiply-add constants, which int_div::params stores only where use_multiply_add
// holds: on x86, not under Emscripten, which also defines the SSE and AVX2 macros.
#if defined(EIGEN_VECTORIZE_SSE2) && !EIGEN_ARCH_i386_OR_x86_64
STATIC_CHECK(!(internal::functor_traits<internal::scalar_int_div_op<int64_t>>::PacketAccess));
STATIC_CHECK(!(internal::functor_traits<internal::scalar_int_div_op<uint64_t>>::PacketAccess));
#endif
}
// A scalar numerator of another integer type converts to Scalar first; int is allowed for literals and promotion.
// failtest/intdivider_float_numerator.cpp and intdivider_wide_numerator.cpp reject the truncating conversions.
void test_scalar_numerators() {
IntDivider<int8_t> by7(7);
STATIC_CHECK((std::is_same<decltype(100 / by7), int8_t>::value));
VERIFY_IS_EQUAL(100 / by7, int8_t(14));
int8_t a = 50, b = 50;
VERIFY_IS_EQUAL((a + b) / by7, int8_t(14));
VERIFY_IS_EQUAL(int8_t(-128) / IntDivider<int64_t>(-3), int64_t(42));
VERIFY_IS_EQUAL(7u / IntDivider<uint16_t>(2), uint16_t(3));
VERIFY_IS_EQUAL(int16_t(-9) / IntDivider<int>(2), -4);
}
EIGEN_DECLARE_TEST(integer_division) {
CALL_SUBTEST_1(test_traits());
CALL_SUBTEST_1(test_scalar_numerators());
CALL_SUBTEST_1((test_exhaustive_division<uint8_t, uint8_t>()));
CALL_SUBTEST_1((test_exhaustive_division<int8_t, int8_t>()));
CALL_SUBTEST_1((test_exhaustive_division<uint8_t, uint16_t>()));
CALL_SUBTEST_1((test_exhaustive_division<int8_t, int16_t>()));
CALL_SUBTEST_2((test_exhaustive_division<uint16_t, uint8_t>()));
CALL_SUBTEST_2((test_exhaustive_division<int16_t, int8_t>()));
CALL_SUBTEST_3((test_random_division<uint8_t>()));
CALL_SUBTEST_3((test_random_division<int8_t>()));
CALL_SUBTEST_3((test_random_division<uint16_t>()));
CALL_SUBTEST_3((test_random_division<int16_t>()));
CALL_SUBTEST_3((test_packet_kernels<uint8_t>()));
CALL_SUBTEST_3((test_packet_kernels<int8_t>()));
CALL_SUBTEST_3((test_packet_kernels<uint16_t>()));
CALL_SUBTEST_3((test_packet_kernels<int16_t>()));
CALL_SUBTEST_4((test_random_division<uint32_t>()));
CALL_SUBTEST_4((test_random_division<int32_t>()));
CALL_SUBTEST_4((test_packet_kernels<uint32_t>()));
CALL_SUBTEST_4((test_packet_kernels<int32_t>()));
CALL_SUBTEST_4((test_expressions<int32_t>()));
CALL_SUBTEST_4((test_compute<int32_t>()));
CALL_SUBTEST_4((test_compute<uint16_t>()));
CALL_SUBTEST_5((test_random_division<uint64_t>()));
CALL_SUBTEST_5((test_random_division<int64_t>()));
CALL_SUBTEST_5((test_random_division<long long>()));
CALL_SUBTEST_5((test_packet_kernels<uint64_t>()));
CALL_SUBTEST_5((test_packet_kernels<int64_t>()));
CALL_SUBTEST_5((test_expressions<int64_t>()));
CALL_SUBTEST_5((test_expressions<uint32_t>()));
CALL_SUBTEST_5((test_compute<int64_t>()));
CALL_SUBTEST_5((test_compute<uint64_t>()));
}