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
25namespace absl {
26
27const uint128 kuint128max = MakeUint128(std::numeric_limits<uint64_t>::max(),
28 std::numeric_limits<uint64_t>::max());
29
30namespace {
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)
45static 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.
59static 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
69void 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
107template <typename T>
108uint128 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.
131uint128 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
150uint128::uint128(float v) : uint128(MakeUint128FromFloat(v)) {}
151uint128::uint128(double v) : uint128(MakeUint128FromFloat(v)) {}
152uint128::uint128(long double v) : uint128(MakeUint128FromFloat(v)) {}
153
154uint128 operator/(uint128 lhs, uint128 rhs) {
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}
165uint128 operator%(uint128 lhs, uint128 rhs) {
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
177namespace {
178
179std::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;
202 std::ios_base::fmtflags copy_mask =
203 std::ios::basefield | std::ios::showbase | std::ios::uppercase;
204 os.setf(flags & copy_mask, copy_mask);
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
225std::ostream& operator<<(std::ostream& os, uint128 v) {
226 std::ios_base::fmtflags flags = os.flags();
227 std::string rep = Uint128ToFormattedString(v, flags);
228
229 // Add the requisite padding.
230 std::streamsize width = os.width(0);
231 if (static_cast<size_t>(width) > rep.size()) {
232 std::ios::fmtflags adjustfield = flags & std::ios::adjustfield;
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
249namespace std {
250constexpr bool numeric_limits<absl::uint128>::is_specialized;
251constexpr bool numeric_limits<absl::uint128>::is_signed;
252constexpr bool numeric_limits<absl::uint128>::is_integer;
253constexpr bool numeric_limits<absl::uint128>::is_exact;
254constexpr bool numeric_limits<absl::uint128>::has_infinity;
255constexpr bool numeric_limits<absl::uint128>::has_quiet_NaN;
256constexpr bool numeric_limits<absl::uint128>::has_signaling_NaN;
257constexpr float_denorm_style numeric_limits<absl::uint128>::has_denorm;
258constexpr bool numeric_limits<absl::uint128>::has_denorm_loss;
259constexpr float_round_style numeric_limits<absl::uint128>::round_style;
260constexpr bool numeric_limits<absl::uint128>::is_iec559;
261constexpr bool numeric_limits<absl::uint128>::is_bounded;
262constexpr bool numeric_limits<absl::uint128>::is_modulo;
263constexpr int numeric_limits<absl::uint128>::digits;
264constexpr int numeric_limits<absl::uint128>::digits10;
265constexpr int numeric_limits<absl::uint128>::max_digits10;
266constexpr int numeric_limits<absl::uint128>::radix;
267constexpr int numeric_limits<absl::uint128>::min_exponent;
268constexpr int numeric_limits<absl::uint128>::min_exponent10;
269constexpr int numeric_limits<absl::uint128>::max_exponent;
270constexpr int numeric_limits<absl::uint128>::max_exponent10;
271constexpr bool numeric_limits<absl::uint128>::traps;
272constexpr bool numeric_limits<absl::uint128>::tinyness_before;
273} // namespace std
274