int128.cc
Go to the documentation of this file.
1 // Copyright 2017 The Abseil Authors.
2 //
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
8 //
9 // Unless required by applicable law or agreed to in writing, software
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/numeric/int128.h"
16
17 #include <stddef.h>
18 #include <cassert>
19 #include <iomanip>
21 #include <sstream>
22 #include <string>
23 #include <type_traits>
24
25 namespace absl {
26
27 const uint128 kuint128max = MakeUint128(std::numeric_limits<uint64_t>::max(),
28  std::numeric_limits<uint64_t>::max());
29
30 namespace {
31
32 // Returns the 0-based position of the last set bit (i.e., most significant bit)
33 // in the given uint64_t. The argument may not be 0.
34 //
35 // For example:
36 // Given: 5 (decimal) == 101 (binary)
37 // Returns: 2
38 #define STEP(T, n, pos, sh) \
39  do { \
40  if ((n) >= (static_cast<T>(1) << (sh))) { \
41  (n) = (n) >> (sh); \
42  (pos) |= (sh); \
43  } \
44  } while (0)
45 static inline int Fls64(uint64_t n) {
46  assert(n != 0);
47  int pos = 0;
48  STEP(uint64_t, n, pos, 0x20);
49  uint32_t n32 = static_cast<uint32_t>(n);
50  STEP(uint32_t, n32, pos, 0x10);
51  STEP(uint32_t, n32, pos, 0x08);
52  STEP(uint32_t, n32, pos, 0x04);
53  return pos + ((uint64_t{0x3333333322221100} >> (n32 << 2)) & 0x3);
54 }
55 #undef STEP
56
57 // Like Fls64() above, but returns the 0-based position of the last set bit
58 // (i.e., most significant bit) in the given uint128. The argument may not be 0.
59 static inline int Fls128(uint128 n) {
60  if (uint64_t hi = Uint128High64(n)) {
61  return Fls64(hi) + 64;
62  }
63  return Fls64(Uint128Low64(n));
64 }
65
66 // Long division/modulo for uint128 implemented using the shift-subtract
67 // division algorithm adapted from:
68 // https://stackoverflow.com/questions/5386377/division-without-using
69 void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret,
70  uint128* remainder_ret) {
71  assert(divisor != 0);
72
73  if (divisor > dividend) {
74  *quotient_ret = 0;
75  *remainder_ret = dividend;
76  return;
77  }
78
79  if (divisor == dividend) {
80  *quotient_ret = 1;
81  *remainder_ret = 0;
82  return;
83  }
84
85  uint128 denominator = divisor;
86  uint128 quotient = 0;
87
88  // Left aligns the MSB of the denominator and the dividend.
89  const int shift = Fls128(dividend) - Fls128(denominator);
90  denominator <<= shift;
91
92  // Uses shift-subtract algorithm to divide dividend by denominator. The
93  // remainder will be left in dividend.
94  for (int i = 0; i <= shift; ++i) {
95  quotient <<= 1;
96  if (dividend >= denominator) {
97  dividend -= denominator;
98  quotient |= 1;
99  }
100  denominator >>= 1;
101  }
102
103  *quotient_ret = quotient;
104  *remainder_ret = dividend;
105 }
106
107 template <typename T>
108 uint128 MakeUint128FromFloat(T v) {
109  static_assert(std::is_floating_point<T>::value, "");
110
111  // Rounding behavior is towards zero, same as for built-in types.
112
113  // Undefined behavior if v is NaN or cannot fit into uint128.
114  assert(std::isfinite(v) && v > -1 &&
115  (std::numeric_limits<T>::max_exponent <= 128 ||
116  v < std::ldexp(static_cast<T>(1), 128)));
117
118  if (v >= std::ldexp(static_cast<T>(1), 64)) {
119  uint64_t hi = static_cast<uint64_t>(std::ldexp(v, -64));
120  uint64_t lo = static_cast<uint64_t>(v - std::ldexp(static_cast<T>(hi), 64));
121  return MakeUint128(hi, lo);
122  }
123
124  return MakeUint128(0, static_cast<uint64_t>(v));
125 }
126
127 #if defined(__clang__) && !defined(__SSE3__)
128 // Workaround for clang bug: https://bugs.llvm.org/show_bug.cgi?id=38289
129 // Casting from long double to uint64_t is miscompiled and drops bits.
130 // It is more work, so only use when we need the workaround.
131 uint128 MakeUint128FromFloat(long double v) {
132  // Go 50 bits at a time, that fits in a double
133  static_assert(std::numeric_limits<double>::digits >= 50, "");
134  static_assert(std::numeric_limits<long double>::digits <= 150, "");
135  // Undefined behavior if v is not finite or cannot fit into uint128.
136  assert(std::isfinite(v) && v > -1 && v < std::ldexp(1.0L, 128));
137
138  v = std::ldexp(v, -100);
139  uint64_t w0 = static_cast<uint64_t>(static_cast<double>(std::trunc(v)));
140  v = std::ldexp(v - static_cast<double>(w0), 50);
141  uint64_t w1 = static_cast<uint64_t>(static_cast<double>(std::trunc(v)));
142  v = std::ldexp(v - static_cast<double>(w1), 50);
143  uint64_t w2 = static_cast<uint64_t>(static_cast<double>(std::trunc(v)));
144  return (static_cast<uint128>(w0) << 100) | (static_cast<uint128>(w1) << 50) |
145  static_cast<uint128>(w2);
146 }
147 #endif // __clang__ && !__SSE3__
148 } // namespace
149
150 uint128::uint128(float v) : uint128(MakeUint128FromFloat(v)) {}
151 uint128::uint128(double v) : uint128(MakeUint128FromFloat(v)) {}
152 uint128::uint128(long double v) : uint128(MakeUint128FromFloat(v)) {}
153
155 #if defined(ABSL_HAVE_INTRINSIC_INT128)
156  return static_cast<unsigned __int128>(lhs) /
157  static_cast<unsigned __int128>(rhs);
158 #else // ABSL_HAVE_INTRINSIC_INT128
159  uint128 quotient = 0;
160  uint128 remainder = 0;
161  DivModImpl(lhs, rhs, &quotient, &remainder);
162  return quotient;
163 #endif // ABSL_HAVE_INTRINSIC_INT128
164 }
166 #if defined(ABSL_HAVE_INTRINSIC_INT128)
167  return static_cast<unsigned __int128>(lhs) %
168  static_cast<unsigned __int128>(rhs);
169 #else // ABSL_HAVE_INTRINSIC_INT128
170  uint128 quotient = 0;
171  uint128 remainder = 0;
172  DivModImpl(lhs, rhs, &quotient, &remainder);
173  return remainder;
174 #endif // ABSL_HAVE_INTRINSIC_INT128
175 }
176
177 namespace {
178
179 std::string Uint128ToFormattedString(uint128 v, std::ios_base::fmtflags flags) {
180  // Select a divisor which is the largest power of the base < 2^64.
181  uint128 div;
182  int div_base_log;
183  switch (flags & std::ios::basefield) {
184  case std::ios::hex:
185  div = 0x1000000000000000; // 16^15
186  div_base_log = 15;
187  break;
188  case std::ios::oct:
189  div = 01000000000000000000000; // 8^21
190  div_base_log = 21;
191  break;
192  default: // std::ios::dec
193  div = 10000000000000000000u; // 10^19
194  div_base_log = 19;
195  break;
196  }
197
198  // Now piece together the uint128 representation from three chunks of the
199  // original value, each less than "div" and therefore representable as a
200  // uint64_t.
201  std::ostringstream os;
203  std::ios::basefield | std::ios::showbase | std::ios::uppercase;
205  uint128 high = v;
206  uint128 low;
207  DivModImpl(high, div, &high, &low);
208  uint128 mid;
209  DivModImpl(high, div, &high, &mid);
210  if (Uint128Low64(high) != 0) {
211  os << Uint128Low64(high);
212  os << std::noshowbase << std::setfill('0') << std::setw(div_base_log);
213  os << Uint128Low64(mid);
214  os << std::setw(div_base_log);
215  } else if (Uint128Low64(mid) != 0) {
216  os << Uint128Low64(mid);
217  os << std::noshowbase << std::setfill('0') << std::setw(div_base_log);
218  }
219  os << Uint128Low64(low);
220  return os.str();
221 }
222
223 } // namespace
224
225 std::ostream& operator<<(std::ostream& os, uint128 v) {
226  std::ios_base::fmtflags flags = os.flags();
227  std::string rep = Uint128ToFormattedString(v, flags);
228
230  std::streamsize width = os.width(0);
231  if (static_cast<size_t>(width) > rep.size()) {
233  if (adjustfield == std::ios::left) {
234  rep.append(width - rep.size(), os.fill());
235  } else if (adjustfield == std::ios::internal &&
236  (flags & std::ios::showbase) &&
237  (flags & std::ios::basefield) == std::ios::hex && v != 0) {
238  rep.insert(2, width - rep.size(), os.fill());
239  } else {
240  rep.insert(0, width - rep.size(), os.fill());
241  }
242  }
243
244  return os << rep;
245 }
246
247 } // namespace absl
248
249 namespace std {
250 constexpr bool numeric_limits<absl::uint128>::is_specialized;
251 constexpr bool numeric_limits<absl::uint128>::is_signed;
252 constexpr bool numeric_limits<absl::uint128>::is_integer;
253 constexpr bool numeric_limits<absl::uint128>::is_exact;
254 constexpr bool numeric_limits<absl::uint128>::has_infinity;
255 constexpr bool numeric_limits<absl::uint128>::has_quiet_NaN;
256 constexpr bool numeric_limits<absl::uint128>::has_signaling_NaN;
257 constexpr float_denorm_style numeric_limits<absl::uint128>::has_denorm;
258 constexpr bool numeric_limits<absl::uint128>::has_denorm_loss;
259 constexpr float_round_style numeric_limits<absl::uint128>::round_style;
260 constexpr bool numeric_limits<absl::uint128>::is_iec559;
261 constexpr bool numeric_limits<absl::uint128>::is_bounded;
262 constexpr bool numeric_limits<absl::uint128>::is_modulo;
263 constexpr int numeric_limits<absl::uint128>::digits;
264 constexpr int numeric_limits<absl::uint128>::digits10;
265 constexpr int numeric_limits<absl::uint128>::max_digits10;
267 constexpr int numeric_limits<absl::uint128>::min_exponent;
268 constexpr int numeric_limits<absl::uint128>::min_exponent10;
269 constexpr int numeric_limits<absl::uint128>::max_exponent;
270 constexpr int numeric_limits<absl::uint128>::max_exponent10;
271 constexpr bool numeric_limits<absl::uint128>::traps;
272 constexpr bool numeric_limits<absl::uint128>::tinyness_before;
273 } // namespace std
int v
Definition: variant_test.cc:81
constexpr uint64_t Uint128High64(uint128 v)
Definition: int128.h:389
uint128()=default
friend constexpr uint64_t Uint128Low64(uint128 v)
Definition: int128.h:387
std::ostream & operator<<(std::ostream &os, absl::LogSeverity s)
Definition: log_severity.cc:21
uint128 operator%(uint128 lhs, uint128 rhs)
Definition: int128.cc:165
constexpr uint64_t Uint128Low64(uint128 v)
Definition: int128.h:387
std::pair< uint64_t, uint64_t > uint128
Definition: city.h:55
Definition: algorithm.h:29
#define STEP(T, n, pos, sh)
Definition: int128.cc:38
size_t value
const uint128 kuint128max
Definition: int128.cc:27
constexpr uint128 MakeUint128(uint64_t high, uint64_t low)
Definition: int128.h:301