/src/abseil-cpp/absl/numeric/int128.cc
Line | Count | Source (jump to first uncovered line) |
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 |
40 | 0 | inline ABSL_ATTRIBUTE_ALWAYS_INLINE int Fls128(uint128 n) { |
41 | 0 | if (uint64_t hi = Uint128High64(n)) { |
42 | 0 | ABSL_ASSUME(hi != 0); |
43 | 0 | return 127 - countl_zero(hi); |
44 | 0 | } |
45 | 0 | const uint64_t low = Uint128Low64(n); |
46 | 0 | ABSL_ASSUME(low != 0); |
47 | 0 | return 63 - countl_zero(low); |
48 | 0 | } |
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 |
53 | | inline void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret, |
54 | 0 | uint128* remainder_ret) { |
55 | 0 | assert(divisor != 0); |
56 | | |
57 | 0 | if (divisor > dividend) { |
58 | 0 | *quotient_ret = 0; |
59 | 0 | *remainder_ret = dividend; |
60 | 0 | return; |
61 | 0 | } |
62 | | |
63 | 0 | if (divisor == dividend) { |
64 | 0 | *quotient_ret = 1; |
65 | 0 | *remainder_ret = 0; |
66 | 0 | return; |
67 | 0 | } |
68 | | |
69 | 0 | uint128 denominator = divisor; |
70 | 0 | uint128 quotient = 0; |
71 | | |
72 | | // Left aligns the MSB of the denominator and the dividend. |
73 | 0 | const int shift = Fls128(dividend) - Fls128(denominator); |
74 | 0 | denominator <<= shift; |
75 | | |
76 | | // Uses shift-subtract algorithm to divide dividend by denominator. The |
77 | | // remainder will be left in dividend. |
78 | 0 | for (int i = 0; i <= shift; ++i) { |
79 | 0 | quotient <<= 1; |
80 | 0 | if (dividend >= denominator) { |
81 | 0 | dividend -= denominator; |
82 | 0 | quotient |= 1; |
83 | 0 | } |
84 | 0 | denominator >>= 1; |
85 | 0 | } |
86 | |
|
87 | 0 | *quotient_ret = quotient; |
88 | 0 | *remainder_ret = dividend; |
89 | 0 | } |
90 | | |
91 | | template <typename T> |
92 | 0 | uint128 MakeUint128FromFloat(T v) { |
93 | 0 | 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 | 0 | assert(std::isfinite(v) && v > -1 && |
99 | 0 | (std::numeric_limits<T>::max_exponent <= 128 || |
100 | 0 | v < std::ldexp(static_cast<T>(1), 128))); |
101 | | |
102 | 0 | if (v >= std::ldexp(static_cast<T>(1), 64)) { |
103 | 0 | uint64_t hi = static_cast<uint64_t>(std::ldexp(v, -64)); |
104 | 0 | uint64_t lo = static_cast<uint64_t>(v - std::ldexp(static_cast<T>(hi), 64)); |
105 | 0 | return MakeUint128(hi, lo); |
106 | 0 | } |
107 | | |
108 | 0 | return MakeUint128(0, static_cast<uint64_t>(v)); |
109 | 0 | } Unexecuted instantiation: int128.cc:absl::uint128 absl::(anonymous namespace)::MakeUint128FromFloat<float>(float) Unexecuted instantiation: int128.cc:absl::uint128 absl::(anonymous namespace)::MakeUint128FromFloat<double>(double) Unexecuted instantiation: int128.cc:absl::uint128 absl::(anonymous namespace)::MakeUint128FromFloat<long double>(long double) |
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. |
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 | | |
134 | 0 | uint128::uint128(float v) : uint128(MakeUint128FromFloat(v)) {} |
135 | 0 | uint128::uint128(double v) : uint128(MakeUint128FromFloat(v)) {} |
136 | 0 | uint128::uint128(long double v) : uint128(MakeUint128FromFloat(v)) {} |
137 | | |
138 | | #if !defined(ABSL_HAVE_INTRINSIC_INT128) |
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 | | |
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 | | |
156 | 0 | 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 | 0 | uint128 div; |
159 | 0 | int div_base_log; |
160 | 0 | switch (flags & std::ios::basefield) { |
161 | 0 | case std::ios::hex: |
162 | 0 | div = 0x1000000000000000; // 16^15 |
163 | 0 | div_base_log = 15; |
164 | 0 | break; |
165 | 0 | case std::ios::oct: |
166 | 0 | div = 01000000000000000000000; // 8^21 |
167 | 0 | div_base_log = 21; |
168 | 0 | break; |
169 | 0 | default: // std::ios::dec |
170 | 0 | div = 10000000000000000000u; // 10^19 |
171 | 0 | div_base_log = 19; |
172 | 0 | break; |
173 | 0 | } |
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 | 0 | std::ostringstream os; |
179 | 0 | std::ios_base::fmtflags copy_mask = |
180 | 0 | std::ios::basefield | std::ios::showbase | std::ios::uppercase; |
181 | 0 | os.setf(flags & copy_mask, copy_mask); |
182 | 0 | uint128 high = v; |
183 | 0 | uint128 low; |
184 | 0 | DivModImpl(high, div, &high, &low); |
185 | 0 | uint128 mid; |
186 | 0 | DivModImpl(high, div, &high, &mid); |
187 | 0 | if (Uint128Low64(high) != 0) { |
188 | 0 | os << Uint128Low64(high); |
189 | 0 | os << std::noshowbase << std::setfill('0') << std::setw(div_base_log); |
190 | 0 | os << Uint128Low64(mid); |
191 | 0 | os << std::setw(div_base_log); |
192 | 0 | } else if (Uint128Low64(mid) != 0) { |
193 | 0 | os << Uint128Low64(mid); |
194 | 0 | os << std::noshowbase << std::setfill('0') << std::setw(div_base_log); |
195 | 0 | } |
196 | 0 | os << Uint128Low64(low); |
197 | 0 | return os.str(); |
198 | 0 | } |
199 | | |
200 | | } // namespace |
201 | | |
202 | 0 | std::string uint128::ToString() const { |
203 | 0 | return Uint128ToFormattedString(*this, std::ios_base::dec); |
204 | 0 | } |
205 | | |
206 | 0 | std::ostream& operator<<(std::ostream& os, uint128 v) { |
207 | 0 | std::ios_base::fmtflags flags = os.flags(); |
208 | 0 | std::string rep = Uint128ToFormattedString(v, flags); |
209 | | |
210 | | // Add the requisite padding. |
211 | 0 | std::streamsize width = os.width(0); |
212 | 0 | if (static_cast<size_t>(width) > rep.size()) { |
213 | 0 | const size_t count = static_cast<size_t>(width) - rep.size(); |
214 | 0 | std::ios::fmtflags adjustfield = flags & std::ios::adjustfield; |
215 | 0 | if (adjustfield == std::ios::left) { |
216 | 0 | rep.append(count, os.fill()); |
217 | 0 | } else if (adjustfield == std::ios::internal && |
218 | 0 | (flags & std::ios::showbase) && |
219 | 0 | (flags & std::ios::basefield) == std::ios::hex && v != 0) { |
220 | 0 | rep.insert(size_t{2}, count, os.fill()); |
221 | 0 | } else { |
222 | 0 | rep.insert(size_t{0}, count, os.fill()); |
223 | 0 | } |
224 | 0 | } |
225 | |
|
226 | 0 | return os << rep; |
227 | 0 | } |
228 | | |
229 | | namespace { |
230 | | |
231 | 0 | uint128 UnsignedAbsoluteValue(int128 v) { |
232 | | // Cast to uint128 before possibly negating because -Int128Min() is undefined. |
233 | 0 | return Int128High64(v) < 0 ? -uint128(v) : uint128(v); |
234 | 0 | } |
235 | | |
236 | | } // namespace |
237 | | |
238 | | #if !defined(ABSL_HAVE_INTRINSIC_INT128) |
239 | | namespace { |
240 | | |
241 | | template <typename T> |
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 | | |
260 | | int128::int128(float v) : int128(MakeInt128FromFloat(v)) {} |
261 | | int128::int128(double v) : int128(MakeInt128FromFloat(v)) {} |
262 | | int128::int128(long double v) : int128(MakeInt128FromFloat(v)) {} |
263 | | |
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 | | |
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 | | |
289 | 0 | std::string int128::ToString() const { |
290 | 0 | std::string rep; |
291 | 0 | if (Int128High64(*this) < 0) rep = "-"; |
292 | 0 | rep.append(Uint128ToFormattedString(UnsignedAbsoluteValue(*this), |
293 | 0 | std::ios_base::dec)); |
294 | 0 | return rep; |
295 | 0 | } |
296 | | |
297 | 0 | std::ostream& operator<<(std::ostream& os, int128 v) { |
298 | 0 | std::ios_base::fmtflags flags = os.flags(); |
299 | 0 | std::string rep; |
300 | | |
301 | | // Add the sign if needed. |
302 | 0 | bool print_as_decimal = |
303 | 0 | (flags & std::ios::basefield) == std::ios::dec || |
304 | 0 | (flags & std::ios::basefield) == std::ios_base::fmtflags(); |
305 | 0 | if (print_as_decimal) { |
306 | 0 | if (Int128High64(v) < 0) { |
307 | 0 | rep = "-"; |
308 | 0 | } else if (flags & std::ios::showpos) { |
309 | 0 | rep = "+"; |
310 | 0 | } |
311 | 0 | } |
312 | |
|
313 | 0 | rep.append(Uint128ToFormattedString( |
314 | 0 | print_as_decimal ? UnsignedAbsoluteValue(v) : uint128(v), os.flags())); |
315 | | |
316 | | // Add the requisite padding. |
317 | 0 | std::streamsize width = os.width(0); |
318 | 0 | if (static_cast<size_t>(width) > rep.size()) { |
319 | 0 | const size_t count = static_cast<size_t>(width) - rep.size(); |
320 | 0 | switch (flags & std::ios::adjustfield) { |
321 | 0 | case std::ios::left: |
322 | 0 | rep.append(count, os.fill()); |
323 | 0 | break; |
324 | 0 | case std::ios::internal: |
325 | 0 | if (print_as_decimal && (rep[0] == '+' || rep[0] == '-')) { |
326 | 0 | rep.insert(size_t{1}, count, os.fill()); |
327 | 0 | } else if ((flags & std::ios::basefield) == std::ios::hex && |
328 | 0 | (flags & std::ios::showbase) && v != 0) { |
329 | 0 | rep.insert(size_t{2}, count, os.fill()); |
330 | 0 | } else { |
331 | 0 | rep.insert(size_t{0}, count, os.fill()); |
332 | 0 | } |
333 | 0 | break; |
334 | 0 | default: // std::ios::right |
335 | 0 | rep.insert(size_t{0}, count, os.fill()); |
336 | 0 | break; |
337 | 0 | } |
338 | 0 | } |
339 | | |
340 | 0 | return os << rep; |
341 | 0 | } |
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 |