1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
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
19 #include <cassert>
20 #include <iomanip>
21 #include <ostream> // NOLINT(readability/streams)
22 #include <sstream>
23 #include <string>
24 #include <type_traits>
25
26 #include "absl/base/optimization.h"
27 #include "absl/numeric/bits.h"
28
29 namespace absl {
30 ABSL_NAMESPACE_BEGIN
31
32 namespace {
33
34 // Returns the 0-based position of the last set bit (i.e., most significant bit)
35 // in the given uint128. The argument is not 0.
36 //
37 // For example:
38 // Given: 5 (decimal) == 101 (binary)
39 // Returns: 2
Fls128(uint128 n)40 inline ABSL_ATTRIBUTE_ALWAYS_INLINE int Fls128(uint128 n) {
41 if (uint64_t hi = Uint128High64(n)) {
42 ABSL_ASSUME(hi != 0);
43 return 127 - countl_zero(hi);
44 }
45 const uint64_t low = Uint128Low64(n);
46 ABSL_ASSUME(low != 0);
47 return 63 - countl_zero(low);
48 }
49
50 // Long division/modulo for uint128 implemented using the shift-subtract
51 // division algorithm adapted from:
52 // https://stackoverflow.com/questions/5386377/division-without-using
DivModImpl(uint128 dividend,uint128 divisor,uint128 * quotient_ret,uint128 * remainder_ret)53 inline void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret,
54 uint128* remainder_ret) {
55 assert(divisor != 0);
56
57 if (divisor > dividend) {
58 *quotient_ret = 0;
59 *remainder_ret = dividend;
60 return;
61 }
62
63 if (divisor == dividend) {
64 *quotient_ret = 1;
65 *remainder_ret = 0;
66 return;
67 }
68
69 uint128 denominator = divisor;
70 uint128 quotient = 0;
71
72 // Left aligns the MSB of the denominator and the dividend.
73 const int shift = Fls128(dividend) - Fls128(denominator);
74 denominator <<= shift;
75
76 // Uses shift-subtract algorithm to divide dividend by denominator. The
77 // remainder will be left in dividend.
78 for (int i = 0; i <= shift; ++i) {
79 quotient <<= 1;
80 if (dividend >= denominator) {
81 dividend -= denominator;
82 quotient |= 1;
83 }
84 denominator >>= 1;
85 }
86
87 *quotient_ret = quotient;
88 *remainder_ret = dividend;
89 }
90
91 template <typename T>
MakeUint128FromFloat(T v)92 uint128 MakeUint128FromFloat(T v) {
93 static_assert(std::is_floating_point<T>::value, "");
94
95 // Rounding behavior is towards zero, same as for built-in types.
96
97 // Undefined behavior if v is NaN or cannot fit into uint128.
98 assert(std::isfinite(v) && v > -1 &&
99 (std::numeric_limits<T>::max_exponent <= 128 ||
100 v < std::ldexp(static_cast<T>(1), 128)));
101
102 if (v >= std::ldexp(static_cast<T>(1), 64)) {
103 uint64_t hi = static_cast<uint64_t>(std::ldexp(v, -64));
104 uint64_t lo = static_cast<uint64_t>(v - std::ldexp(static_cast<T>(hi), 64));
105 return MakeUint128(hi, lo);
106 }
107
108 return MakeUint128(0, static_cast<uint64_t>(v));
109 }
110
111 #if defined(__clang__) && (__clang_major__ < 9) && !defined(__SSE3__)
112 // Workaround for clang bug: https://bugs.llvm.org/show_bug.cgi?id=38289
113 // Casting from long double to uint64_t is miscompiled and drops bits.
114 // It is more work, so only use when we need the workaround.
MakeUint128FromFloat(long double v)115 uint128 MakeUint128FromFloat(long double v) {
116 // Go 50 bits at a time, that fits in a double
117 static_assert(std::numeric_limits<double>::digits >= 50, "");
118 static_assert(std::numeric_limits<long double>::digits <= 150, "");
119 // Undefined behavior if v is not finite or cannot fit into uint128.
120 assert(std::isfinite(v) && v > -1 && v < std::ldexp(1.0L, 128));
121
122 v = std::ldexp(v, -100);
123 uint64_t w0 = static_cast<uint64_t>(static_cast<double>(std::trunc(v)));
124 v = std::ldexp(v - static_cast<double>(w0), 50);
125 uint64_t w1 = static_cast<uint64_t>(static_cast<double>(std::trunc(v)));
126 v = std::ldexp(v - static_cast<double>(w1), 50);
127 uint64_t w2 = static_cast<uint64_t>(static_cast<double>(std::trunc(v)));
128 return (static_cast<uint128>(w0) << 100) | (static_cast<uint128>(w1) << 50) |
129 static_cast<uint128>(w2);
130 }
131 #endif // __clang__ && (__clang_major__ < 9) && !__SSE3__
132 } // namespace
133
uint128(float v)134 uint128::uint128(float v) : uint128(MakeUint128FromFloat(v)) {}
uint128(double v)135 uint128::uint128(double v) : uint128(MakeUint128FromFloat(v)) {}
uint128(long double v)136 uint128::uint128(long double v) : uint128(MakeUint128FromFloat(v)) {}
137
138 #if !defined(ABSL_HAVE_INTRINSIC_INT128)
operator /(uint128 lhs,uint128 rhs)139 uint128 operator/(uint128 lhs, uint128 rhs) {
140 uint128 quotient = 0;
141 uint128 remainder = 0;
142 DivModImpl(lhs, rhs, "ient, &remainder);
143 return quotient;
144 }
145
operator %(uint128 lhs,uint128 rhs)146 uint128 operator%(uint128 lhs, uint128 rhs) {
147 uint128 quotient = 0;
148 uint128 remainder = 0;
149 DivModImpl(lhs, rhs, "ient, &remainder);
150 return remainder;
151 }
152 #endif // !defined(ABSL_HAVE_INTRINSIC_INT128)
153
154 namespace {
155
Uint128ToFormattedString(uint128 v,std::ios_base::fmtflags flags)156 std::string Uint128ToFormattedString(uint128 v, std::ios_base::fmtflags flags) {
157 // Select a divisor which is the largest power of the base < 2^64.
158 uint128 div;
159 int div_base_log;
160 switch (flags & std::ios::basefield) {
161 case std::ios::hex:
162 div = 0x1000000000000000; // 16^15
163 div_base_log = 15;
164 break;
165 case std::ios::oct:
166 div = 01000000000000000000000; // 8^21
167 div_base_log = 21;
168 break;
169 default: // std::ios::dec
170 div = 10000000000000000000u; // 10^19
171 div_base_log = 19;
172 break;
173 }
174
175 // Now piece together the uint128 representation from three chunks of the
176 // original value, each less than "div" and therefore representable as a
177 // uint64_t.
178 std::ostringstream os;
179 std::ios_base::fmtflags copy_mask =
180 std::ios::basefield | std::ios::showbase | std::ios::uppercase;
181 os.setf(flags & copy_mask, copy_mask);
182 uint128 high = v;
183 uint128 low;
184 DivModImpl(high, div, &high, &low);
185 uint128 mid;
186 DivModImpl(high, div, &high, &mid);
187 if (Uint128Low64(high) != 0) {
188 os << Uint128Low64(high);
189 os << std::noshowbase << std::setfill('0') << std::setw(div_base_log);
190 os << Uint128Low64(mid);
191 os << std::setw(div_base_log);
192 } else if (Uint128Low64(mid) != 0) {
193 os << Uint128Low64(mid);
194 os << std::noshowbase << std::setfill('0') << std::setw(div_base_log);
195 }
196 os << Uint128Low64(low);
197 return os.str();
198 }
199
200 } // namespace
201
ToString() const202 std::string uint128::ToString() const {
203 return Uint128ToFormattedString(*this, std::ios_base::dec);
204 }
205
operator <<(std::ostream & os,uint128 v)206 std::ostream& operator<<(std::ostream& os, uint128 v) {
207 std::ios_base::fmtflags flags = os.flags();
208 std::string rep = Uint128ToFormattedString(v, flags);
209
210 // Add the requisite padding.
211 std::streamsize width = os.width(0);
212 if (static_cast<size_t>(width) > rep.size()) {
213 const size_t count = static_cast<size_t>(width) - rep.size();
214 std::ios::fmtflags adjustfield = flags & std::ios::adjustfield;
215 if (adjustfield == std::ios::left) {
216 rep.append(count, os.fill());
217 } else if (adjustfield == std::ios::internal &&
218 (flags & std::ios::showbase) &&
219 (flags & std::ios::basefield) == std::ios::hex && v != 0) {
220 rep.insert(size_t{2}, count, os.fill());
221 } else {
222 rep.insert(size_t{0}, count, os.fill());
223 }
224 }
225
226 return os << rep;
227 }
228
229 namespace {
230
UnsignedAbsoluteValue(int128 v)231 uint128 UnsignedAbsoluteValue(int128 v) {
232 // Cast to uint128 before possibly negating because -Int128Min() is undefined.
233 return Int128High64(v) < 0 ? -uint128(v) : uint128(v);
234 }
235
236 } // namespace
237
238 #if !defined(ABSL_HAVE_INTRINSIC_INT128)
239 namespace {
240
241 template <typename T>
MakeInt128FromFloat(T v)242 int128 MakeInt128FromFloat(T v) {
243 // Conversion when v is NaN or cannot fit into int128 would be undefined
244 // behavior if using an intrinsic 128-bit integer.
245 assert(std::isfinite(v) && (std::numeric_limits<T>::max_exponent <= 127 ||
246 (v >= -std::ldexp(static_cast<T>(1), 127) &&
247 v < std::ldexp(static_cast<T>(1), 127))));
248
249 // We must convert the absolute value and then negate as needed, because
250 // floating point types are typically sign-magnitude. Otherwise, the
251 // difference between the high and low 64 bits when interpreted as two's
252 // complement overwhelms the precision of the mantissa.
253 uint128 result = v < 0 ? -MakeUint128FromFloat(-v) : MakeUint128FromFloat(v);
254 return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(result)),
255 Uint128Low64(result));
256 }
257
258 } // namespace
259
int128(float v)260 int128::int128(float v) : int128(MakeInt128FromFloat(v)) {}
int128(double v)261 int128::int128(double v) : int128(MakeInt128FromFloat(v)) {}
int128(long double v)262 int128::int128(long double v) : int128(MakeInt128FromFloat(v)) {}
263
operator /(int128 lhs,int128 rhs)264 int128 operator/(int128 lhs, int128 rhs) {
265 assert(lhs != Int128Min() || rhs != -1); // UB on two's complement.
266
267 uint128 quotient = 0;
268 uint128 remainder = 0;
269 DivModImpl(UnsignedAbsoluteValue(lhs), UnsignedAbsoluteValue(rhs),
270 "ient, &remainder);
271 if ((Int128High64(lhs) < 0) != (Int128High64(rhs) < 0)) quotient = -quotient;
272 return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(quotient)),
273 Uint128Low64(quotient));
274 }
275
operator %(int128 lhs,int128 rhs)276 int128 operator%(int128 lhs, int128 rhs) {
277 assert(lhs != Int128Min() || rhs != -1); // UB on two's complement.
278
279 uint128 quotient = 0;
280 uint128 remainder = 0;
281 DivModImpl(UnsignedAbsoluteValue(lhs), UnsignedAbsoluteValue(rhs),
282 "ient, &remainder);
283 if (Int128High64(lhs) < 0) remainder = -remainder;
284 return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(remainder)),
285 Uint128Low64(remainder));
286 }
287 #endif // ABSL_HAVE_INTRINSIC_INT128
288
ToString() const289 std::string int128::ToString() const {
290 std::string rep;
291 if (Int128High64(*this) < 0) rep = "-";
292 rep.append(Uint128ToFormattedString(UnsignedAbsoluteValue(*this),
293 std::ios_base::dec));
294 return rep;
295 }
296
operator <<(std::ostream & os,int128 v)297 std::ostream& operator<<(std::ostream& os, int128 v) {
298 std::ios_base::fmtflags flags = os.flags();
299 std::string rep;
300
301 // Add the sign if needed.
302 bool print_as_decimal =
303 (flags & std::ios::basefield) == std::ios::dec ||
304 (flags & std::ios::basefield) == std::ios_base::fmtflags();
305 if (print_as_decimal) {
306 if (Int128High64(v) < 0) {
307 rep = "-";
308 } else if (flags & std::ios::showpos) {
309 rep = "+";
310 }
311 }
312
313 rep.append(Uint128ToFormattedString(
314 print_as_decimal ? UnsignedAbsoluteValue(v) : uint128(v), os.flags()));
315
316 // Add the requisite padding.
317 std::streamsize width = os.width(0);
318 if (static_cast<size_t>(width) > rep.size()) {
319 const size_t count = static_cast<size_t>(width) - rep.size();
320 switch (flags & std::ios::adjustfield) {
321 case std::ios::left:
322 rep.append(count, os.fill());
323 break;
324 case std::ios::internal:
325 if (print_as_decimal && (rep[0] == '+' || rep[0] == '-')) {
326 rep.insert(size_t{1}, count, os.fill());
327 } else if ((flags & std::ios::basefield) == std::ios::hex &&
328 (flags & std::ios::showbase) && v != 0) {
329 rep.insert(size_t{2}, count, os.fill());
330 } else {
331 rep.insert(size_t{0}, count, os.fill());
332 }
333 break;
334 default: // std::ios::right
335 rep.insert(size_t{0}, count, os.fill());
336 break;
337 }
338 }
339
340 return os << rep;
341 }
342
343 ABSL_NAMESPACE_END
344 } // namespace absl
345
346 #ifdef ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL
347 namespace std {
348 constexpr bool numeric_limits<absl::uint128>::is_specialized;
349 constexpr bool numeric_limits<absl::uint128>::is_signed;
350 constexpr bool numeric_limits<absl::uint128>::is_integer;
351 constexpr bool numeric_limits<absl::uint128>::is_exact;
352 constexpr bool numeric_limits<absl::uint128>::has_infinity;
353 constexpr bool numeric_limits<absl::uint128>::has_quiet_NaN;
354 constexpr bool numeric_limits<absl::uint128>::has_signaling_NaN;
355 constexpr float_denorm_style numeric_limits<absl::uint128>::has_denorm;
356 constexpr bool numeric_limits<absl::uint128>::has_denorm_loss;
357 constexpr float_round_style numeric_limits<absl::uint128>::round_style;
358 constexpr bool numeric_limits<absl::uint128>::is_iec559;
359 constexpr bool numeric_limits<absl::uint128>::is_bounded;
360 constexpr bool numeric_limits<absl::uint128>::is_modulo;
361 constexpr int numeric_limits<absl::uint128>::digits;
362 constexpr int numeric_limits<absl::uint128>::digits10;
363 constexpr int numeric_limits<absl::uint128>::max_digits10;
364 constexpr int numeric_limits<absl::uint128>::radix;
365 constexpr int numeric_limits<absl::uint128>::min_exponent;
366 constexpr int numeric_limits<absl::uint128>::min_exponent10;
367 constexpr int numeric_limits<absl::uint128>::max_exponent;
368 constexpr int numeric_limits<absl::uint128>::max_exponent10;
369 constexpr bool numeric_limits<absl::uint128>::traps;
370 constexpr bool numeric_limits<absl::uint128>::tinyness_before;
371
372 constexpr bool numeric_limits<absl::int128>::is_specialized;
373 constexpr bool numeric_limits<absl::int128>::is_signed;
374 constexpr bool numeric_limits<absl::int128>::is_integer;
375 constexpr bool numeric_limits<absl::int128>::is_exact;
376 constexpr bool numeric_limits<absl::int128>::has_infinity;
377 constexpr bool numeric_limits<absl::int128>::has_quiet_NaN;
378 constexpr bool numeric_limits<absl::int128>::has_signaling_NaN;
379 constexpr float_denorm_style numeric_limits<absl::int128>::has_denorm;
380 constexpr bool numeric_limits<absl::int128>::has_denorm_loss;
381 constexpr float_round_style numeric_limits<absl::int128>::round_style;
382 constexpr bool numeric_limits<absl::int128>::is_iec559;
383 constexpr bool numeric_limits<absl::int128>::is_bounded;
384 constexpr bool numeric_limits<absl::int128>::is_modulo;
385 constexpr int numeric_limits<absl::int128>::digits;
386 constexpr int numeric_limits<absl::int128>::digits10;
387 constexpr int numeric_limits<absl::int128>::max_digits10;
388 constexpr int numeric_limits<absl::int128>::radix;
389 constexpr int numeric_limits<absl::int128>::min_exponent;
390 constexpr int numeric_limits<absl::int128>::min_exponent10;
391 constexpr int numeric_limits<absl::int128>::max_exponent;
392 constexpr int numeric_limits<absl::int128>::max_exponent10;
393 constexpr bool numeric_limits<absl::int128>::traps;
394 constexpr bool numeric_limits<absl::int128>::tinyness_before;
395 } // namespace std
396 #endif
397