// Copyright 2017 The Abseil Authors. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. // The implementation of the absl::Duration class, which is declared in // //absl/time.h. This class behaves like a numeric type; it has no public // methods and is used only through the operators defined here. // // Implementation notes: // // An absl::Duration is represented as // // rep_hi_ : (int64_t) Whole seconds // rep_lo_ : (uint32_t) Fractions of a second // // The seconds value (rep_hi_) may be positive or negative as appropriate. // The fractional seconds (rep_lo_) is always a positive offset from rep_hi_. // The API for Duration guarantees at least nanosecond resolution, which // means rep_lo_ could have a max value of 1B - 1 if it stored nanoseconds. // However, to utilize more of the available 32 bits of space in rep_lo_, // we instead store quarters of a nanosecond in rep_lo_ resulting in a max // value of 4B - 1. This allows us to correctly handle calculations like // 0.5 nanos + 0.5 nanos = 1 nano. The following example shows the actual // Duration rep using quarters of a nanosecond. // // 2.5 sec = {rep_hi_=2, rep_lo_=2000000000} // lo = 4 * 500000000 // -2.5 sec = {rep_hi_=-3, rep_lo_=2000000000} // // Infinite durations are represented as Durations with the rep_lo_ field set // to all 1s. // // +InfiniteDuration: // rep_hi_ : kint64max // rep_lo_ : ~0U // // -InfiniteDuration: // rep_hi_ : kint64min // rep_lo_ : ~0U // // Arithmetic overflows/underflows to +/- infinity and saturates. #include #include #include #include #include #include #include #include #include #include #include #include #include "absl/base/casts.h" #include "absl/numeric/int128.h" #include "absl/time/time.h" namespace absl { namespace { using time_internal::kTicksPerNanosecond; using time_internal::kTicksPerSecond; constexpr int64_t kint64max = std::numeric_limits::max(); constexpr int64_t kint64min = std::numeric_limits::min(); // Can't use std::isinfinite() because it doesn't exist on windows. inline bool IsFinite(double d) { return d != std::numeric_limits::infinity() && d != -std::numeric_limits::infinity(); } // Can't use std::round() because it is only available in C++11. // Note that we ignore the possibility of floating-point over/underflow. template inline double Round(Double d) { return d < 0 ? std::ceil(d - 0.5) : std::floor(d + 0.5); } // *sec may be positive or negative. *ticks must be in the range // -kTicksPerSecond < *ticks < kTicksPerSecond. If *ticks is negative it // will be normalized to a positive value by adjusting *sec accordingly. inline void NormalizeTicks(int64_t* sec, int64_t* ticks) { if (*ticks < 0) { --*sec; *ticks += kTicksPerSecond; } } // Makes a uint128 from the absolute value of the given scalar. inline uint128 MakeU128(int64_t a) { uint128 u128 = 0; if (a < 0) { ++u128; ++a; // Makes it safe to negate 'a' a = -a; } u128 += static_cast(a); return u128; } // Makes a uint128 count of ticks out of the absolute value of the Duration. inline uint128 MakeU128Ticks(Duration d) { int64_t rep_hi = time_internal::GetRepHi(d); uint32_t rep_lo = time_internal::GetRepLo(d); if (rep_hi < 0) { ++rep_hi; rep_hi = -rep_hi; rep_lo = kTicksPerSecond - rep_lo; } uint128 u128 = static_cast(rep_hi); u128 *= static_cast(kTicksPerSecond); u128 += rep_lo; return u128; } // Breaks a uint128 of ticks into a Duration. inline Duration MakeDurationFromU128(uint128 u128, bool is_neg) { int64_t rep_hi; uint32_t rep_lo; const uint64_t h64 = Uint128High64(u128); const uint64_t l64 = Uint128Low64(u128); if (h64 == 0) { // fastpath const uint64_t hi = l64 / kTicksPerSecond; rep_hi = static_cast(hi); rep_lo = static_cast(l64 - hi * kTicksPerSecond); } else { // kMaxRepHi64 is the high 64 bits of (2^63 * kTicksPerSecond). // Any positive tick count whose high 64 bits are >= kMaxRepHi64 // is not representable as a Duration. A negative tick count can // have its high 64 bits == kMaxRepHi64 but only when the low 64 // bits are all zero, otherwise it is not representable either. const uint64_t kMaxRepHi64 = 0x77359400UL; if (h64 >= kMaxRepHi64) { if (is_neg && h64 == kMaxRepHi64 && l64 == 0) { // Avoid trying to represent -kint64min below. return time_internal::MakeDuration(kint64min); } return is_neg ? -InfiniteDuration() : InfiniteDuration(); } const uint128 kTicksPerSecond128 = static_cast(kTicksPerSecond); const uint128 hi = u128 / kTicksPerSecond128; rep_hi = static_cast(Uint128Low64(hi)); rep_lo = static_cast(Uint128Low64(u128 - hi * kTicksPerSecond128)); } if (is_neg) { rep_hi = -rep_hi; if (rep_lo != 0) { --rep_hi; rep_lo = kTicksPerSecond - rep_lo; } } return time_internal::MakeDuration(rep_hi, rep_lo); } // Convert between int64_t and uint64_t, preserving representation. This // allows us to do arithmetic in the unsigned domain, where overflow has // well-defined behavior. See operator+=() and operator-=(). // // C99 7.20.1.1.1, as referenced by C++11 18.4.1.2, says, "The typedef // name intN_t designates a signed integer type with width N, no padding // bits, and a two's complement representation." So, we can convert to // and from the corresponding uint64_t value using a bit cast. inline uint64_t EncodeTwosComp(int64_t v) { return bit_cast(v); } inline int64_t DecodeTwosComp(uint64_t v) { return bit_cast(v); } // Note: The overflow detection in this function is done using greater/less *or // equal* because kint64max/min is too large to be represented exactly in a // double (which only has 53 bits of precision). In order to avoid assigning to // rep->hi a double value that is too large for an int64_t (and therefore is // undefined), we must consider computations that equal kint64max/min as a // double as overflow cases. inline bool SafeAddRepHi(double a_hi, double b_hi, Duration* d) { double c = a_hi + b_hi; if (c >= kint64max) { *d = InfiniteDuration(); return false; } if (c <= kint64min) { *d = -InfiniteDuration(); return false; } *d = time_internal::MakeDuration(c, time_internal::GetRepLo(*d)); return true; } // A functor that's similar to std::multiplies, except this returns the max // T value instead of overflowing. This is only defined for uint128. template struct SafeMultiply { uint128 operator()(uint128 a, uint128 b) const { // b hi is always zero because it originated as an int64_t. assert(Uint128High64(b) == 0); // Fastpath to avoid the expensive overflow check with division. if (Uint128High64(a) == 0) { return (((Uint128Low64(a) | Uint128Low64(b)) >> 32) == 0) ? static_cast(Uint128Low64(a) * Uint128Low64(b)) : a * b; } return b == 0 ? b : (a > kuint128max / b) ? kuint128max : a * b; } }; // Scales (i.e., multiplies or divides, depending on the Operation template) // the Duration d by the int64_t r. template