tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

int128.cc (11370B)

      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 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
     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>
     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.
    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 uint128::uint128(float v) : uint128(MakeUint128FromFloat(v)) {}
    135 uint128::uint128(double v) : uint128(MakeUint128FromFloat(v)) {}
    136 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 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 
    202 std::string uint128::ToString() const {
    203  return Uint128ToFormattedString(*this, std::ios_base::dec);
    204 }
    205 
    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 
    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>
    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 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 
    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