Loading...
Searching...
No Matches
uint128.h
/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
* See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
* Author(s): Marc Glisse
*
* Copyright (C) 2024 Inria
*
* Modification(s):
* - YYYY/MM Author: Description of the modification
*/
#ifndef GUDHI_UINT128_H_
#define GUDHI_UINT128_H_
#include <gudhi/Debug_utils.h>
#include <cstdint>
#include <utility>
#include <boost/container_hash/hash.hpp>
/* What about boost::multiprecision::uint128_t?
* It works on linux, mac, windows, etc.
* On linux x86_64, it has low overhead since it delegates to unsigned __int128.
* It is a bit slower than Fake_uint128, probably because of checks in << and >>, but I only noticed a 10%
* overhead compared to unsigned __int128 on 1 testcase.
* On windows, it is implemented as { size_t; uint64_t[2]; }, that's 50% overhead on storage. On the same
* testcase, forcing linux-gcc to use the windows code led to 4x slowdown. Other testcases were not affected.
* The pathological testcase is computing homology in all dimensions for the vertices of a regular 24-gon.
*/
// GUDHI_FORCE_FAKE_UINT128 is only used for tests
#if !defined __SIZEOF_INT128__ || defined GUDHI_FORCE_FAKE_UINT128
namespace Gudhi::numbers {
class Fake_uint128 {
// Debug
#ifdef __SIZEOF_INT128__
unsigned __int128 native() const { return ((unsigned __int128)high << 64) + low; }
#define GUDHI_VERIF(X) GUDHI_CHECK(res.native() == (X), "")
#else
#define GUDHI_VERIF(X)
#endif
public:
constexpr Fake_uint128(): high(0), low(0) {}
constexpr Fake_uint128(std::uint64_t a): high(0), low(a) {}
// Arithmetic
// (multiplication and division are not needed for now)
friend Fake_uint128 operator+(Fake_uint128 a, Fake_uint128 b){
Fake_uint128 res;
res.low = a.low + b.low;
res.high = a.high + b.high + (res.low < a.low);
GUDHI_VERIF (a.native() + b.native());
return res;
}
friend Fake_uint128 operator-(Fake_uint128 a, Fake_uint128 b){
Fake_uint128 res;
res.low = a.low - b.low;
res.high = a.high - b.high - (res.low > a.low);
GUDHI_VERIF (a.native() - b.native());
return res;
}
friend Fake_uint128 operator<<(Fake_uint128 a, uint8_t b){
Fake_uint128 res;
GUDHI_CHECK(b < 128, "");
if (b >= 64) { res.low = 0; res.high = a.low << (b-64); }
else if (b == 0) { res = a; }
else { res.low = a.low << b; res.high = a.high << b | a.low >> (64-b); }
GUDHI_VERIF (a.native() << b);
return res;
}
friend Fake_uint128 operator>>(Fake_uint128 a, uint8_t b){
Fake_uint128 res;
GUDHI_CHECK(b < 128, "");
if (b >= 64) { res.high = 0; res.low = a.high >> (b-64); }
else if (b == 0) { res = a; }
else { res.high = a.high >> b; res.low = a.low >> b | a.high << (64-b); }
GUDHI_VERIF (a.native() >> b);
return res;
}
friend Fake_uint128 operator&(Fake_uint128 a, Fake_uint128 b){
Fake_uint128 res;
res.low = a.low & b.low;
res.high = a.high & b.high;
GUDHI_VERIF (a.native() & b.native());
return res;
}
friend Fake_uint128 operator|(Fake_uint128 a, Fake_uint128 b){
Fake_uint128 res;
res.low = a.low | b.low;
res.high = a.high | b.high;
GUDHI_VERIF (a.native() | b.native());
return res;
}
friend Fake_uint128 operator~(Fake_uint128 a){
Fake_uint128 res;
res.low = ~a.low;
res.high = ~a.high;
return res;
}
// In-place arithmetic
Fake_uint128& operator+=(Fake_uint128 a) { *this = *this + a; return *this; }
Fake_uint128& operator-=(Fake_uint128 a) { *this = *this - a; return *this; }
Fake_uint128& operator++() { if (++low == 0) ++high; return *this; }
Fake_uint128& operator--() { if (low-- == 0) --high; return *this; }
Fake_uint128& operator<<=(uint8_t a) { *this = *this << a; return *this; }
Fake_uint128& operator>>=(uint8_t a) { *this = *this >> a; return *this; }
Fake_uint128& operator&=(Fake_uint128 a) { *this = *this & a; return *this; }
Fake_uint128& operator|=(Fake_uint128 a) { *this = *this | a; return *this; }
// Comparisons
friend bool operator==(Fake_uint128 a, Fake_uint128 b){
return a.low == b.low && a.high == b.high;
}
friend bool operator!=(Fake_uint128 a, Fake_uint128 b){
return a.low != b.low || a.high != b.high;
}
friend bool operator<(Fake_uint128 a, Fake_uint128 b){
return a.high < b.high || (a.high == b.high && a.low < b.low);
}
friend bool operator>(Fake_uint128 a, Fake_uint128 b){
return a.high > b.high || (a.high == b.high && a.low > b.low);
}
friend bool operator<=(Fake_uint128 a, Fake_uint128 b){
return a.high < b.high || (a.high == b.high && a.low <= b.low);
}
friend bool operator>=(Fake_uint128 a, Fake_uint128 b){
return a.high > b.high || (a.high == b.high && a.low >= b.low);
}
// Misc
friend std::size_t hash_value(Fake_uint128 a) {
typedef std::pair<std::uint64_t, std::uint64_t> P;
return boost::hash_value(P(a.high, a.low));
}
template <class T, class=std::enable_if_t<std::is_integral_v<T>>>
explicit operator T() const {
GUDHI_CHECK(high == 0 && low <= std::numeric_limits<T>::max(), "");
return static_cast<T>(low);
}
private:
std::uint64_t high, low; // does the order matter?
#undef GUDHI_VERIF
};
typedef Fake_uint128 uint128_t;
} // namespace Gudhi::numbers
template<> class std::numeric_limits<Gudhi::numbers::Fake_uint128> {
public:
static constexpr bool is_specialized = true;
static constexpr bool is_signed = false;
static constexpr bool is_integer = true;
static constexpr bool is_exact = true;
static constexpr bool has_infinity = false;
static constexpr bool is_modulo = true;
static constexpr int digits = 128;
static constexpr int radix = 2;
// etc
};
#else
namespace Gudhi::numbers {
typedef unsigned __int128 uint128_t;
} // namespace Gudhi::numbers
#endif
#endif // GUDHI_UINT128_H_
Gudhi
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14