Coverage Report

Created: 2024-09-23 06:29

/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, &quotient, &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, &quotient, &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
             &quotient, &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
             &quotient, &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