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