Loading...
Searching...
No Matches
uint128.h
1/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2 * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3 * Author(s): Marc Glisse
4 *
5 * Copyright (C) 2024 Inria
6 *
7 * Modification(s):
8 * - YYYY/MM Author: Description of the modification
9 */
10
11#ifndef GUDHI_UINT128_H_
12#define GUDHI_UINT128_H_
13#include <gudhi/Debug_utils.h>
14#include <cstdint>
15#include <utility>
16#include <boost/container_hash/hash.hpp>
17
18/* What about boost::multiprecision::uint128_t?
19 * It works on linux, mac, windows, etc.
20 * On linux x86_64, it has low overhead since it delegates to unsigned __int128.
21 * It is a bit slower than Fake_uint128, probably because of checks in << and >>, but I only noticed a 10%
22 * overhead compared to unsigned __int128 on 1 testcase.
23 * On windows, it is implemented as { size_t; uint64_t[2]; }, that's 50% overhead on storage. On the same
24 * testcase, forcing linux-gcc to use the windows code led to 4x slowdown. Other testcases were not affected.
25 * The pathological testcase is computing homology in all dimensions for the vertices of a regular 24-gon.
26 */
27
28// GUDHI_FORCE_FAKE_UINT128 is only used for tests
29#if !defined __SIZEOF_INT128__ || defined GUDHI_FORCE_FAKE_UINT128
30namespace Gudhi::numbers {
31class Fake_uint128 {
32 // Debug
33 #ifdef __SIZEOF_INT128__
34 unsigned __int128 native() const { return ((unsigned __int128)high << 64) + low; }
35 #define GUDHI_VERIF(X) GUDHI_CHECK(res.native() == (X), "")
36 #else
37 #define GUDHI_VERIF(X)
38 #endif
39 public:
40 constexpr Fake_uint128(): high(0), low(0) {}
41 constexpr Fake_uint128(std::uint64_t a): high(0), low(a) {}
42 // Arithmetic
43 // (multiplication and division are not needed for now)
44 friend Fake_uint128 operator+(Fake_uint128 a, Fake_uint128 b){
45 Fake_uint128 res;
46 res.low = a.low + b.low;
47 res.high = a.high + b.high + (res.low < a.low);
48 GUDHI_VERIF (a.native() + b.native());
49 return res;
50 }
51 friend Fake_uint128 operator-(Fake_uint128 a, Fake_uint128 b){
52 Fake_uint128 res;
53 res.low = a.low - b.low;
54 res.high = a.high - b.high - (res.low > a.low);
55 GUDHI_VERIF (a.native() - b.native());
56 return res;
57 }
58 friend Fake_uint128 operator<<(Fake_uint128 a, uint8_t b){
59 Fake_uint128 res;
60 GUDHI_CHECK(b < 128, "");
61 if (b >= 64) { res.low = 0; res.high = a.low << (b-64); }
62 else if (b == 0) { res = a; }
63 else { res.low = a.low << b; res.high = a.high << b | a.low >> (64-b); }
64 GUDHI_VERIF (a.native() << b);
65 return res;
66 }
67 friend Fake_uint128 operator>>(Fake_uint128 a, uint8_t b){
68 Fake_uint128 res;
69 GUDHI_CHECK(b < 128, "");
70 if (b >= 64) { res.high = 0; res.low = a.high >> (b-64); }
71 else if (b == 0) { res = a; }
72 else { res.high = a.high >> b; res.low = a.low >> b | a.high << (64-b); }
73 GUDHI_VERIF (a.native() >> b);
74 return res;
75 }
76 friend Fake_uint128 operator&(Fake_uint128 a, Fake_uint128 b){
77 Fake_uint128 res;
78 res.low = a.low & b.low;
79 res.high = a.high & b.high;
80 GUDHI_VERIF (a.native() & b.native());
81 return res;
82 }
83 friend Fake_uint128 operator|(Fake_uint128 a, Fake_uint128 b){
84 Fake_uint128 res;
85 res.low = a.low | b.low;
86 res.high = a.high | b.high;
87 GUDHI_VERIF (a.native() | b.native());
88 return res;
89 }
90 friend Fake_uint128 operator~(Fake_uint128 a){
91 Fake_uint128 res;
92 res.low = ~a.low;
93 res.high = ~a.high;
94 return res;
95 }
96 // In-place arithmetic
97 Fake_uint128& operator+=(Fake_uint128 a) { *this = *this + a; return *this; }
98 Fake_uint128& operator-=(Fake_uint128 a) { *this = *this - a; return *this; }
99 Fake_uint128& operator++() { if (++low == 0) ++high; return *this; }
100 Fake_uint128& operator--() { if (low-- == 0) --high; return *this; }
101 Fake_uint128& operator<<=(uint8_t a) { *this = *this << a; return *this; }
102 Fake_uint128& operator>>=(uint8_t a) { *this = *this >> a; return *this; }
103 Fake_uint128& operator&=(Fake_uint128 a) { *this = *this & a; return *this; }
104 Fake_uint128& operator|=(Fake_uint128 a) { *this = *this | a; return *this; }
105 // Comparisons
106 friend bool operator==(Fake_uint128 a, Fake_uint128 b){
107 return a.low == b.low && a.high == b.high;
108 }
109 friend bool operator!=(Fake_uint128 a, Fake_uint128 b){
110 return a.low != b.low || a.high != b.high;
111 }
112 friend bool operator<(Fake_uint128 a, Fake_uint128 b){
113 return a.high < b.high || (a.high == b.high && a.low < b.low);
114 }
115 friend bool operator>(Fake_uint128 a, Fake_uint128 b){
116 return a.high > b.high || (a.high == b.high && a.low > b.low);
117 }
118 friend bool operator<=(Fake_uint128 a, Fake_uint128 b){
119 return a.high < b.high || (a.high == b.high && a.low <= b.low);
120 }
121 friend bool operator>=(Fake_uint128 a, Fake_uint128 b){
122 return a.high > b.high || (a.high == b.high && a.low >= b.low);
123 }
124 // Misc
125 friend std::size_t hash_value(Fake_uint128 a) {
126 typedef std::pair<std::uint64_t, std::uint64_t> P;
127 return boost::hash_value(P(a.high, a.low));
128 }
129 template <class T, class=std::enable_if_t<std::is_integral_v<T>>>
130 explicit operator T() const {
131 GUDHI_CHECK(high == 0 && low <= std::numeric_limits<T>::max(), "");
132 return static_cast<T>(low);
133 }
134 private:
135 std::uint64_t high, low; // does the order matter?
136 #undef GUDHI_VERIF
137};
138typedef Fake_uint128 uint128_t;
139} // namespace Gudhi::numbers
140template<> class std::numeric_limits<Gudhi::numbers::Fake_uint128> {
141 public:
142 static constexpr bool is_specialized = true;
143 static constexpr bool is_signed = false;
144 static constexpr bool is_integer = true;
145 static constexpr bool is_exact = true;
146 static constexpr bool has_infinity = false;
147 static constexpr bool is_modulo = true;
148 static constexpr int digits = 128;
149 static constexpr int radix = 2;
150 // etc
151};
152#else
153namespace Gudhi::numbers {
154typedef unsigned __int128 uint128_t;
155} // namespace Gudhi::numbers
156#endif
157#endif // GUDHI_UINT128_H_
std::ostream & operator<<(std::ostream &os, const Permutahedral_representation< Vertex, OrderedSetPartition > &simplex)
Print a permutahedral representation to a stream.
Definition Permutahedral_representation.h:173
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14