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 // The implementation of the absl::Duration class, which is declared in
16 // //absl/time.h. This class behaves like a numeric type; it has no public
17 // methods and is used only through the operators defined here.
18 //
19 // Implementation notes:
20 //
21 // An absl::Duration is represented as
22 //
23 // rep_hi_ : (int64_t) Whole seconds
24 // rep_lo_ : (uint32_t) Fractions of a second
25 //
26 // The seconds value (rep_hi_) may be positive or negative as appropriate.
27 // The fractional seconds (rep_lo_) is always a positive offset from rep_hi_.
28 // The API for Duration guarantees at least nanosecond resolution, which
29 // means rep_lo_ could have a max value of 1B - 1 if it stored nanoseconds.
30 // However, to utilize more of the available 32 bits of space in rep_lo_,
31 // we instead store quarters of a nanosecond in rep_lo_ resulting in a max
32 // value of 4B - 1. This allows us to correctly handle calculations like
33 // 0.5 nanos + 0.5 nanos = 1 nano. The following example shows the actual
34 // Duration rep using quarters of a nanosecond.
35 //
36 // 2.5 sec = {rep_hi_=2, rep_lo_=2000000000} // lo = 4 * 500000000
37 // -2.5 sec = {rep_hi_=-3, rep_lo_=2000000000}
38 //
39 // Infinite durations are represented as Durations with the rep_lo_ field set
40 // to all 1s.
41 //
42 // +InfiniteDuration:
43 // rep_hi_ : kint64max
44 // rep_lo_ : ~0U
45 //
46 // -InfiniteDuration:
47 // rep_hi_ : kint64min
48 // rep_lo_ : ~0U
49 //
50 // Arithmetic overflows/underflows to +/- infinity and saturates.
51
52 #if defined(_MSC_VER)
53 #include <winsock2.h> // for timeval
54 #endif
55
56 #include <algorithm>
57 #include <cassert>
58 #include <chrono> // NOLINT(build/c++11)
59 #include <cmath>
60 #include <cstdint>
61 #include <cstdlib>
62 #include <cstring>
63 #include <ctime>
64 #include <functional>
65 #include <limits>
66 #include <string>
67
68 #include "absl/base/attributes.h"
69 #include "absl/base/casts.h"
70 #include "absl/base/config.h"
71 #include "absl/numeric/int128.h"
72 #include "absl/strings/string_view.h"
73 #include "absl/strings/strip.h"
74 #include "absl/time/time.h"
75
76 namespace absl {
77 ABSL_NAMESPACE_BEGIN
78
79 namespace {
80
81 using time_internal::kTicksPerNanosecond;
82 using time_internal::kTicksPerSecond;
83
84 constexpr int64_t kint64max = std::numeric_limits<int64_t>::max();
85 constexpr int64_t kint64min = std::numeric_limits<int64_t>::min();
86
87 // Can't use std::isinfinite() because it doesn't exist on windows.
IsFinite(double d)88 inline bool IsFinite(double d) {
89 if (std::isnan(d)) return false;
90 return d != std::numeric_limits<double>::infinity() &&
91 d != -std::numeric_limits<double>::infinity();
92 }
93
IsValidDivisor(double d)94 inline bool IsValidDivisor(double d) {
95 if (std::isnan(d)) return false;
96 return d != 0.0;
97 }
98
99 // *sec may be positive or negative. *ticks must be in the range
100 // -kTicksPerSecond < *ticks < kTicksPerSecond. If *ticks is negative it
101 // will be normalized to a positive value by adjusting *sec accordingly.
NormalizeTicks(int64_t * sec,int64_t * ticks)102 inline void NormalizeTicks(int64_t* sec, int64_t* ticks) {
103 if (*ticks < 0) {
104 --*sec;
105 *ticks += kTicksPerSecond;
106 }
107 }
108
109 // Makes a uint128 from the absolute value of the given scalar.
MakeU128(int64_t a)110 inline uint128 MakeU128(int64_t a) {
111 uint128 u128 = 0;
112 if (a < 0) {
113 ++u128;
114 ++a; // Makes it safe to negate 'a'
115 a = -a;
116 }
117 u128 += static_cast<uint64_t>(a);
118 return u128;
119 }
120
121 // Makes a uint128 count of ticks out of the absolute value of the Duration.
MakeU128Ticks(Duration d)122 inline uint128 MakeU128Ticks(Duration d) {
123 int64_t rep_hi = time_internal::GetRepHi(d);
124 uint32_t rep_lo = time_internal::GetRepLo(d);
125 if (rep_hi < 0) {
126 ++rep_hi;
127 rep_hi = -rep_hi;
128 rep_lo = kTicksPerSecond - rep_lo;
129 }
130 uint128 u128 = static_cast<uint64_t>(rep_hi);
131 u128 *= static_cast<uint64_t>(kTicksPerSecond);
132 u128 += rep_lo;
133 return u128;
134 }
135
136 // Breaks a uint128 of ticks into a Duration.
MakeDurationFromU128(uint128 u128,bool is_neg)137 inline Duration MakeDurationFromU128(uint128 u128, bool is_neg) {
138 int64_t rep_hi;
139 uint32_t rep_lo;
140 const uint64_t h64 = Uint128High64(u128);
141 const uint64_t l64 = Uint128Low64(u128);
142 if (h64 == 0) { // fastpath
143 const uint64_t hi = l64 / kTicksPerSecond;
144 rep_hi = static_cast<int64_t>(hi);
145 rep_lo = static_cast<uint32_t>(l64 - hi * kTicksPerSecond);
146 } else {
147 // kMaxRepHi64 is the high 64 bits of (2^63 * kTicksPerSecond).
148 // Any positive tick count whose high 64 bits are >= kMaxRepHi64
149 // is not representable as a Duration. A negative tick count can
150 // have its high 64 bits == kMaxRepHi64 but only when the low 64
151 // bits are all zero, otherwise it is not representable either.
152 const uint64_t kMaxRepHi64 = 0x77359400UL;
153 if (h64 >= kMaxRepHi64) {
154 if (is_neg && h64 == kMaxRepHi64 && l64 == 0) {
155 // Avoid trying to represent -kint64min below.
156 return time_internal::MakeDuration(kint64min);
157 }
158 return is_neg ? -InfiniteDuration() : InfiniteDuration();
159 }
160 const uint128 kTicksPerSecond128 = static_cast<uint64_t>(kTicksPerSecond);
161 const uint128 hi = u128 / kTicksPerSecond128;
162 rep_hi = static_cast<int64_t>(Uint128Low64(hi));
163 rep_lo =
164 static_cast<uint32_t>(Uint128Low64(u128 - hi * kTicksPerSecond128));
165 }
166 if (is_neg) {
167 rep_hi = -rep_hi;
168 if (rep_lo != 0) {
169 --rep_hi;
170 rep_lo = kTicksPerSecond - rep_lo;
171 }
172 }
173 return time_internal::MakeDuration(rep_hi, rep_lo);
174 }
175
176 // Convert between int64_t and uint64_t, preserving representation. This
177 // allows us to do arithmetic in the unsigned domain, where overflow has
178 // well-defined behavior. See operator+=() and operator-=().
179 //
180 // C99 7.20.1.1.1, as referenced by C++11 18.4.1.2, says, "The typedef
181 // name intN_t designates a signed integer type with width N, no padding
182 // bits, and a two's complement representation." So, we can convert to
183 // and from the corresponding uint64_t value using a bit cast.
EncodeTwosComp(int64_t v)184 inline uint64_t EncodeTwosComp(int64_t v) {
185 return absl::bit_cast<uint64_t>(v);
186 }
DecodeTwosComp(uint64_t v)187 inline int64_t DecodeTwosComp(uint64_t v) { return absl::bit_cast<int64_t>(v); }
188
189 // Note: The overflow detection in this function is done using greater/less *or
190 // equal* because kint64max/min is too large to be represented exactly in a
191 // double (which only has 53 bits of precision). In order to avoid assigning to
192 // rep->hi a double value that is too large for an int64_t (and therefore is
193 // undefined), we must consider computations that equal kint64max/min as a
194 // double as overflow cases.
SafeAddRepHi(double a_hi,double b_hi,Duration * d)195 inline bool SafeAddRepHi(double a_hi, double b_hi, Duration* d) {
196 double c = a_hi + b_hi;
197 if (c >= static_cast<double>(kint64max)) {
198 *d = InfiniteDuration();
199 return false;
200 }
201 if (c <= static_cast<double>(kint64min)) {
202 *d = -InfiniteDuration();
203 return false;
204 }
205 *d = time_internal::MakeDuration(c, time_internal::GetRepLo(*d));
206 return true;
207 }
208
209 // A functor that's similar to std::multiplies<T>, except this returns the max
210 // T value instead of overflowing. This is only defined for uint128.
211 template <typename Ignored>
212 struct SafeMultiply {
operator ()absl::__anonc93d22b20111::SafeMultiply213 uint128 operator()(uint128 a, uint128 b) const {
214 // b hi is always zero because it originated as an int64_t.
215 assert(Uint128High64(b) == 0);
216 // Fastpath to avoid the expensive overflow check with division.
217 if (Uint128High64(a) == 0) {
218 return (((Uint128Low64(a) | Uint128Low64(b)) >> 32) == 0)
219 ? static_cast<uint128>(Uint128Low64(a) * Uint128Low64(b))
220 : a * b;
221 }
222 return b == 0 ? b : (a > Uint128Max() / b) ? Uint128Max() : a * b;
223 }
224 };
225
226 // Scales (i.e., multiplies or divides, depending on the Operation template)
227 // the Duration d by the int64_t r.
228 template <template <typename> class Operation>
ScaleFixed(Duration d,int64_t r)229 inline Duration ScaleFixed(Duration d, int64_t r) {
230 const uint128 a = MakeU128Ticks(d);
231 const uint128 b = MakeU128(r);
232 const uint128 q = Operation<uint128>()(a, b);
233 const bool is_neg = (time_internal::GetRepHi(d) < 0) != (r < 0);
234 return MakeDurationFromU128(q, is_neg);
235 }
236
237 // Scales (i.e., multiplies or divides, depending on the Operation template)
238 // the Duration d by the double r.
239 template <template <typename> class Operation>
ScaleDouble(Duration d,double r)240 inline Duration ScaleDouble(Duration d, double r) {
241 Operation<double> op;
242 double hi_doub = op(time_internal::GetRepHi(d), r);
243 double lo_doub = op(time_internal::GetRepLo(d), r);
244
245 double hi_int = 0;
246 double hi_frac = std::modf(hi_doub, &hi_int);
247
248 // Moves hi's fractional bits to lo.
249 lo_doub /= kTicksPerSecond;
250 lo_doub += hi_frac;
251
252 double lo_int = 0;
253 double lo_frac = std::modf(lo_doub, &lo_int);
254
255 // Rolls lo into hi if necessary.
256 int64_t lo64 = std::round(lo_frac * kTicksPerSecond);
257
258 Duration ans;
259 if (!SafeAddRepHi(hi_int, lo_int, &ans)) return ans;
260 int64_t hi64 = time_internal::GetRepHi(ans);
261 if (!SafeAddRepHi(hi64, lo64 / kTicksPerSecond, &ans)) return ans;
262 hi64 = time_internal::GetRepHi(ans);
263 lo64 %= kTicksPerSecond;
264 NormalizeTicks(&hi64, &lo64);
265 return time_internal::MakeDuration(hi64, lo64);
266 }
267
268 // Tries to divide num by den as fast as possible by looking for common, easy
269 // cases. If the division was done, the quotient is in *q and the remainder is
270 // in *rem and true will be returned.
IDivFastPath(const Duration num,const Duration den,int64_t * q,Duration * rem)271 inline bool IDivFastPath(const Duration num, const Duration den, int64_t* q,
272 Duration* rem) {
273 // Bail if num or den is an infinity.
274 if (time_internal::IsInfiniteDuration(num) ||
275 time_internal::IsInfiniteDuration(den))
276 return false;
277
278 int64_t num_hi = time_internal::GetRepHi(num);
279 uint32_t num_lo = time_internal::GetRepLo(num);
280 int64_t den_hi = time_internal::GetRepHi(den);
281 uint32_t den_lo = time_internal::GetRepLo(den);
282
283 if (den_hi == 0) {
284 if (den_lo == kTicksPerNanosecond) {
285 // Dividing by 1ns
286 if (num_hi >= 0 && num_hi < (kint64max - kTicksPerSecond) / 1000000000) {
287 *q = num_hi * 1000000000 + num_lo / kTicksPerNanosecond;
288 *rem = time_internal::MakeDuration(0, num_lo % den_lo);
289 return true;
290 }
291 } else if (den_lo == 100 * kTicksPerNanosecond) {
292 // Dividing by 100ns (common when converting to Universal time)
293 if (num_hi >= 0 && num_hi < (kint64max - kTicksPerSecond) / 10000000) {
294 *q = num_hi * 10000000 + num_lo / (100 * kTicksPerNanosecond);
295 *rem = time_internal::MakeDuration(0, num_lo % den_lo);
296 return true;
297 }
298 } else if (den_lo == 1000 * kTicksPerNanosecond) {
299 // Dividing by 1us
300 if (num_hi >= 0 && num_hi < (kint64max - kTicksPerSecond) / 1000000) {
301 *q = num_hi * 1000000 + num_lo / (1000 * kTicksPerNanosecond);
302 *rem = time_internal::MakeDuration(0, num_lo % den_lo);
303 return true;
304 }
305 } else if (den_lo == 1000000 * kTicksPerNanosecond) {
306 // Dividing by 1ms
307 if (num_hi >= 0 && num_hi < (kint64max - kTicksPerSecond) / 1000) {
308 *q = num_hi * 1000 + num_lo / (1000000 * kTicksPerNanosecond);
309 *rem = time_internal::MakeDuration(0, num_lo % den_lo);
310 return true;
311 }
312 }
313 } else if (den_hi > 0 && den_lo == 0) {
314 // Dividing by positive multiple of 1s
315 if (num_hi >= 0) {
316 if (den_hi == 1) {
317 *q = num_hi;
318 *rem = time_internal::MakeDuration(0, num_lo);
319 return true;
320 }
321 *q = num_hi / den_hi;
322 *rem = time_internal::MakeDuration(num_hi % den_hi, num_lo);
323 return true;
324 }
325 if (num_lo != 0) {
326 num_hi += 1;
327 }
328 int64_t quotient = num_hi / den_hi;
329 int64_t rem_sec = num_hi % den_hi;
330 if (rem_sec > 0) {
331 rem_sec -= den_hi;
332 quotient += 1;
333 }
334 if (num_lo != 0) {
335 rem_sec -= 1;
336 }
337 *q = quotient;
338 *rem = time_internal::MakeDuration(rem_sec, num_lo);
339 return true;
340 }
341
342 return false;
343 }
344
345 } // namespace
346
347 namespace {
348
IDivSlowPath(bool satq,const Duration num,const Duration den,Duration * rem)349 int64_t IDivSlowPath(bool satq, const Duration num, const Duration den,
350 Duration* rem) {
351 const bool num_neg = num < ZeroDuration();
352 const bool den_neg = den < ZeroDuration();
353 const bool quotient_neg = num_neg != den_neg;
354
355 if (time_internal::IsInfiniteDuration(num) || den == ZeroDuration()) {
356 *rem = num_neg ? -InfiniteDuration() : InfiniteDuration();
357 return quotient_neg ? kint64min : kint64max;
358 }
359 if (time_internal::IsInfiniteDuration(den)) {
360 *rem = num;
361 return 0;
362 }
363
364 const uint128 a = MakeU128Ticks(num);
365 const uint128 b = MakeU128Ticks(den);
366 uint128 quotient128 = a / b;
367
368 if (satq) {
369 // Limits the quotient to the range of int64_t.
370 if (quotient128 > uint128(static_cast<uint64_t>(kint64max))) {
371 quotient128 = quotient_neg ? uint128(static_cast<uint64_t>(kint64min))
372 : uint128(static_cast<uint64_t>(kint64max));
373 }
374 }
375
376 const uint128 remainder128 = a - quotient128 * b;
377 *rem = MakeDurationFromU128(remainder128, num_neg);
378
379 if (!quotient_neg || quotient128 == 0) {
380 return Uint128Low64(quotient128) & kint64max;
381 }
382 // The quotient needs to be negated, but we need to carefully handle
383 // quotient128s with the top bit on.
384 return -static_cast<int64_t>(Uint128Low64(quotient128 - 1) & kint64max) - 1;
385 }
386
387 // The 'satq' argument indicates whether the quotient should saturate at the
388 // bounds of int64_t. If it does saturate, the difference will spill over to
389 // the remainder. If it does not saturate, the remainder remain accurate,
390 // but the returned quotient will over/underflow int64_t and should not be used.
IDivDurationImpl(bool satq,const Duration num,const Duration den,Duration * rem)391 ABSL_ATTRIBUTE_ALWAYS_INLINE inline int64_t IDivDurationImpl(bool satq,
392 const Duration num,
393 const Duration den,
394 Duration* rem) {
395 int64_t q = 0;
396 if (IDivFastPath(num, den, &q, rem)) {
397 return q;
398 }
399 return IDivSlowPath(satq, num, den, rem);
400 }
401
402 } // namespace
403
IDivDuration(Duration num,Duration den,Duration * rem)404 int64_t IDivDuration(Duration num, Duration den, Duration* rem) {
405 return IDivDurationImpl(true, num, den,
406 rem); // trunc towards zero
407 }
408
409 //
410 // Additive operators.
411 //
412
operator +=(Duration rhs)413 Duration& Duration::operator+=(Duration rhs) {
414 if (time_internal::IsInfiniteDuration(*this)) return *this;
415 if (time_internal::IsInfiniteDuration(rhs)) return *this = rhs;
416 const int64_t orig_rep_hi = rep_hi_.Get();
417 rep_hi_ = DecodeTwosComp(EncodeTwosComp(rep_hi_.Get()) +
418 EncodeTwosComp(rhs.rep_hi_.Get()));
419 if (rep_lo_ >= kTicksPerSecond - rhs.rep_lo_) {
420 rep_hi_ = DecodeTwosComp(EncodeTwosComp(rep_hi_.Get()) + 1);
421 rep_lo_ -= kTicksPerSecond;
422 }
423 rep_lo_ += rhs.rep_lo_;
424 if (rhs.rep_hi_.Get() < 0 ? rep_hi_.Get() > orig_rep_hi
425 : rep_hi_.Get() < orig_rep_hi) {
426 return *this =
427 rhs.rep_hi_.Get() < 0 ? -InfiniteDuration() : InfiniteDuration();
428 }
429 return *this;
430 }
431
operator -=(Duration rhs)432 Duration& Duration::operator-=(Duration rhs) {
433 if (time_internal::IsInfiniteDuration(*this)) return *this;
434 if (time_internal::IsInfiniteDuration(rhs)) {
435 return *this = rhs.rep_hi_.Get() >= 0 ? -InfiniteDuration()
436 : InfiniteDuration();
437 }
438 const int64_t orig_rep_hi = rep_hi_.Get();
439 rep_hi_ = DecodeTwosComp(EncodeTwosComp(rep_hi_.Get()) -
440 EncodeTwosComp(rhs.rep_hi_.Get()));
441 if (rep_lo_ < rhs.rep_lo_) {
442 rep_hi_ = DecodeTwosComp(EncodeTwosComp(rep_hi_.Get()) - 1);
443 rep_lo_ += kTicksPerSecond;
444 }
445 rep_lo_ -= rhs.rep_lo_;
446 if (rhs.rep_hi_.Get() < 0 ? rep_hi_.Get() < orig_rep_hi
447 : rep_hi_.Get() > orig_rep_hi) {
448 return *this = rhs.rep_hi_.Get() >= 0 ? -InfiniteDuration()
449 : InfiniteDuration();
450 }
451 return *this;
452 }
453
454 //
455 // Multiplicative operators.
456 //
457
operator *=(int64_t r)458 Duration& Duration::operator*=(int64_t r) {
459 if (time_internal::IsInfiniteDuration(*this)) {
460 const bool is_neg = (r < 0) != (rep_hi_.Get() < 0);
461 return *this = is_neg ? -InfiniteDuration() : InfiniteDuration();
462 }
463 return *this = ScaleFixed<SafeMultiply>(*this, r);
464 }
465
operator *=(double r)466 Duration& Duration::operator*=(double r) {
467 if (time_internal::IsInfiniteDuration(*this) || !IsFinite(r)) {
468 const bool is_neg = std::signbit(r) != (rep_hi_.Get() < 0);
469 return *this = is_neg ? -InfiniteDuration() : InfiniteDuration();
470 }
471 return *this = ScaleDouble<std::multiplies>(*this, r);
472 }
473
operator /=(int64_t r)474 Duration& Duration::operator/=(int64_t r) {
475 if (time_internal::IsInfiniteDuration(*this) || r == 0) {
476 const bool is_neg = (r < 0) != (rep_hi_.Get() < 0);
477 return *this = is_neg ? -InfiniteDuration() : InfiniteDuration();
478 }
479 return *this = ScaleFixed<std::divides>(*this, r);
480 }
481
operator /=(double r)482 Duration& Duration::operator/=(double r) {
483 if (time_internal::IsInfiniteDuration(*this) || !IsValidDivisor(r)) {
484 const bool is_neg = std::signbit(r) != (rep_hi_.Get() < 0);
485 return *this = is_neg ? -InfiniteDuration() : InfiniteDuration();
486 }
487 return *this = ScaleDouble<std::divides>(*this, r);
488 }
489
operator %=(Duration rhs)490 Duration& Duration::operator%=(Duration rhs) {
491 IDivDurationImpl(false, *this, rhs, this);
492 return *this;
493 }
494
FDivDuration(Duration num,Duration den)495 double FDivDuration(Duration num, Duration den) {
496 // Arithmetic with infinity is sticky.
497 if (time_internal::IsInfiniteDuration(num) || den == ZeroDuration()) {
498 return (num < ZeroDuration()) == (den < ZeroDuration())
499 ? std::numeric_limits<double>::infinity()
500 : -std::numeric_limits<double>::infinity();
501 }
502 if (time_internal::IsInfiniteDuration(den)) return 0.0;
503
504 double a =
505 static_cast<double>(time_internal::GetRepHi(num)) * kTicksPerSecond +
506 time_internal::GetRepLo(num);
507 double b =
508 static_cast<double>(time_internal::GetRepHi(den)) * kTicksPerSecond +
509 time_internal::GetRepLo(den);
510 return a / b;
511 }
512
513 //
514 // Trunc/Floor/Ceil.
515 //
516
Trunc(Duration d,Duration unit)517 Duration Trunc(Duration d, Duration unit) { return d - (d % unit); }
518
Floor(const Duration d,const Duration unit)519 Duration Floor(const Duration d, const Duration unit) {
520 const absl::Duration td = Trunc(d, unit);
521 return td <= d ? td : td - AbsDuration(unit);
522 }
523
Ceil(const Duration d,const Duration unit)524 Duration Ceil(const Duration d, const Duration unit) {
525 const absl::Duration td = Trunc(d, unit);
526 return td >= d ? td : td + AbsDuration(unit);
527 }
528
529 //
530 // Factory functions.
531 //
532
DurationFromTimespec(timespec ts)533 Duration DurationFromTimespec(timespec ts) {
534 if (static_cast<uint64_t>(ts.tv_nsec) < 1000 * 1000 * 1000) {
535 int64_t ticks = ts.tv_nsec * kTicksPerNanosecond;
536 return time_internal::MakeDuration(ts.tv_sec, ticks);
537 }
538 return Seconds(ts.tv_sec) + Nanoseconds(ts.tv_nsec);
539 }
540
DurationFromTimeval(timeval tv)541 Duration DurationFromTimeval(timeval tv) {
542 if (static_cast<uint64_t>(tv.tv_usec) < 1000 * 1000) {
543 int64_t ticks = tv.tv_usec * 1000 * kTicksPerNanosecond;
544 return time_internal::MakeDuration(tv.tv_sec, ticks);
545 }
546 return Seconds(tv.tv_sec) + Microseconds(tv.tv_usec);
547 }
548
549 //
550 // Conversion to other duration types.
551 //
552
ToInt64Nanoseconds(Duration d)553 int64_t ToInt64Nanoseconds(Duration d) {
554 if (time_internal::GetRepHi(d) >= 0 &&
555 time_internal::GetRepHi(d) >> 33 == 0) {
556 return (time_internal::GetRepHi(d) * 1000 * 1000 * 1000) +
557 (time_internal::GetRepLo(d) / kTicksPerNanosecond);
558 }
559 return d / Nanoseconds(1);
560 }
ToInt64Microseconds(Duration d)561 int64_t ToInt64Microseconds(Duration d) {
562 if (time_internal::GetRepHi(d) >= 0 &&
563 time_internal::GetRepHi(d) >> 43 == 0) {
564 return (time_internal::GetRepHi(d) * 1000 * 1000) +
565 (time_internal::GetRepLo(d) / (kTicksPerNanosecond * 1000));
566 }
567 return d / Microseconds(1);
568 }
ToInt64Milliseconds(Duration d)569 int64_t ToInt64Milliseconds(Duration d) {
570 if (time_internal::GetRepHi(d) >= 0 &&
571 time_internal::GetRepHi(d) >> 53 == 0) {
572 return (time_internal::GetRepHi(d) * 1000) +
573 (time_internal::GetRepLo(d) / (kTicksPerNanosecond * 1000 * 1000));
574 }
575 return d / Milliseconds(1);
576 }
ToInt64Seconds(Duration d)577 int64_t ToInt64Seconds(Duration d) {
578 int64_t hi = time_internal::GetRepHi(d);
579 if (time_internal::IsInfiniteDuration(d)) return hi;
580 if (hi < 0 && time_internal::GetRepLo(d) != 0) ++hi;
581 return hi;
582 }
ToInt64Minutes(Duration d)583 int64_t ToInt64Minutes(Duration d) {
584 int64_t hi = time_internal::GetRepHi(d);
585 if (time_internal::IsInfiniteDuration(d)) return hi;
586 if (hi < 0 && time_internal::GetRepLo(d) != 0) ++hi;
587 return hi / 60;
588 }
ToInt64Hours(Duration d)589 int64_t ToInt64Hours(Duration d) {
590 int64_t hi = time_internal::GetRepHi(d);
591 if (time_internal::IsInfiniteDuration(d)) return hi;
592 if (hi < 0 && time_internal::GetRepLo(d) != 0) ++hi;
593 return hi / (60 * 60);
594 }
595
ToDoubleNanoseconds(Duration d)596 double ToDoubleNanoseconds(Duration d) {
597 return FDivDuration(d, Nanoseconds(1));
598 }
ToDoubleMicroseconds(Duration d)599 double ToDoubleMicroseconds(Duration d) {
600 return FDivDuration(d, Microseconds(1));
601 }
ToDoubleMilliseconds(Duration d)602 double ToDoubleMilliseconds(Duration d) {
603 return FDivDuration(d, Milliseconds(1));
604 }
ToDoubleSeconds(Duration d)605 double ToDoubleSeconds(Duration d) { return FDivDuration(d, Seconds(1)); }
ToDoubleMinutes(Duration d)606 double ToDoubleMinutes(Duration d) { return FDivDuration(d, Minutes(1)); }
ToDoubleHours(Duration d)607 double ToDoubleHours(Duration d) { return FDivDuration(d, Hours(1)); }
608
ToTimespec(Duration d)609 timespec ToTimespec(Duration d) {
610 timespec ts;
611 if (!time_internal::IsInfiniteDuration(d)) {
612 int64_t rep_hi = time_internal::GetRepHi(d);
613 uint32_t rep_lo = time_internal::GetRepLo(d);
614 if (rep_hi < 0) {
615 // Tweak the fields so that unsigned division of rep_lo
616 // maps to truncation (towards zero) for the timespec.
617 rep_lo += kTicksPerNanosecond - 1;
618 if (rep_lo >= kTicksPerSecond) {
619 rep_hi += 1;
620 rep_lo -= kTicksPerSecond;
621 }
622 }
623 ts.tv_sec = static_cast<decltype(ts.tv_sec)>(rep_hi);
624 if (ts.tv_sec == rep_hi) { // no time_t narrowing
625 ts.tv_nsec = rep_lo / kTicksPerNanosecond;
626 return ts;
627 }
628 }
629 if (d >= ZeroDuration()) {
630 ts.tv_sec = std::numeric_limits<time_t>::max();
631 ts.tv_nsec = 1000 * 1000 * 1000 - 1;
632 } else {
633 ts.tv_sec = std::numeric_limits<time_t>::min();
634 ts.tv_nsec = 0;
635 }
636 return ts;
637 }
638
ToTimeval(Duration d)639 timeval ToTimeval(Duration d) {
640 timeval tv;
641 timespec ts = ToTimespec(d);
642 if (ts.tv_sec < 0) {
643 // Tweak the fields so that positive division of tv_nsec
644 // maps to truncation (towards zero) for the timeval.
645 ts.tv_nsec += 1000 - 1;
646 if (ts.tv_nsec >= 1000 * 1000 * 1000) {
647 ts.tv_sec += 1;
648 ts.tv_nsec -= 1000 * 1000 * 1000;
649 }
650 }
651 tv.tv_sec = static_cast<decltype(tv.tv_sec)>(ts.tv_sec);
652 if (tv.tv_sec != ts.tv_sec) { // narrowing
653 if (ts.tv_sec < 0) {
654 tv.tv_sec = std::numeric_limits<decltype(tv.tv_sec)>::min();
655 tv.tv_usec = 0;
656 } else {
657 tv.tv_sec = std::numeric_limits<decltype(tv.tv_sec)>::max();
658 tv.tv_usec = 1000 * 1000 - 1;
659 }
660 return tv;
661 }
662 tv.tv_usec = static_cast<int>(ts.tv_nsec / 1000); // suseconds_t
663 return tv;
664 }
665
ToChronoNanoseconds(Duration d)666 std::chrono::nanoseconds ToChronoNanoseconds(Duration d) {
667 return time_internal::ToChronoDuration<std::chrono::nanoseconds>(d);
668 }
ToChronoMicroseconds(Duration d)669 std::chrono::microseconds ToChronoMicroseconds(Duration d) {
670 return time_internal::ToChronoDuration<std::chrono::microseconds>(d);
671 }
ToChronoMilliseconds(Duration d)672 std::chrono::milliseconds ToChronoMilliseconds(Duration d) {
673 return time_internal::ToChronoDuration<std::chrono::milliseconds>(d);
674 }
ToChronoSeconds(Duration d)675 std::chrono::seconds ToChronoSeconds(Duration d) {
676 return time_internal::ToChronoDuration<std::chrono::seconds>(d);
677 }
ToChronoMinutes(Duration d)678 std::chrono::minutes ToChronoMinutes(Duration d) {
679 return time_internal::ToChronoDuration<std::chrono::minutes>(d);
680 }
ToChronoHours(Duration d)681 std::chrono::hours ToChronoHours(Duration d) {
682 return time_internal::ToChronoDuration<std::chrono::hours>(d);
683 }
684
685 //
686 // To/From string formatting.
687 //
688
689 namespace {
690
691 // Formats a positive 64-bit integer in the given field width. Note that
692 // it is up to the caller of Format64() to ensure that there is sufficient
693 // space before ep to hold the conversion.
Format64(char * ep,int width,int64_t v)694 char* Format64(char* ep, int width, int64_t v) {
695 do {
696 --width;
697 *--ep = static_cast<char>('0' + (v % 10)); // contiguous digits
698 } while (v /= 10);
699 while (--width >= 0) *--ep = '0'; // zero pad
700 return ep;
701 }
702
703 // Helpers for FormatDuration() that format 'n' and append it to 'out'
704 // followed by the given 'unit'. If 'n' formats to "0", nothing is
705 // appended (not even the unit).
706
707 // A type that encapsulates how to display a value of a particular unit. For
708 // values that are displayed with fractional parts, the precision indicates
709 // where to round the value. The precision varies with the display unit because
710 // a Duration can hold only quarters of a nanosecond, so displaying information
711 // beyond that is just noise.
712 //
713 // For example, a microsecond value of 42.00025xxxxx should not display beyond 5
714 // fractional digits, because it is in the noise of what a Duration can
715 // represent.
716 struct DisplayUnit {
717 absl::string_view abbr;
718 int prec;
719 double pow10;
720 };
721 ABSL_CONST_INIT const DisplayUnit kDisplayNano = {"ns", 2, 1e2};
722 ABSL_CONST_INIT const DisplayUnit kDisplayMicro = {"us", 5, 1e5};
723 ABSL_CONST_INIT const DisplayUnit kDisplayMilli = {"ms", 8, 1e8};
724 ABSL_CONST_INIT const DisplayUnit kDisplaySec = {"s", 11, 1e11};
725 ABSL_CONST_INIT const DisplayUnit kDisplayMin = {"m", -1, 0.0}; // prec ignored
726 ABSL_CONST_INIT const DisplayUnit kDisplayHour = {"h", -1,
727 0.0}; // prec ignored
728
AppendNumberUnit(std::string * out,int64_t n,DisplayUnit unit)729 void AppendNumberUnit(std::string* out, int64_t n, DisplayUnit unit) {
730 char buf[sizeof("2562047788015216")]; // hours in max duration
731 char* const ep = buf + sizeof(buf);
732 char* bp = Format64(ep, 0, n);
733 if (*bp != '0' || bp + 1 != ep) {
734 out->append(bp, static_cast<size_t>(ep - bp));
735 out->append(unit.abbr.data(), unit.abbr.size());
736 }
737 }
738
739 // Note: unit.prec is limited to double's digits10 value (typically 15) so it
740 // always fits in buf[].
AppendNumberUnit(std::string * out,double n,DisplayUnit unit)741 void AppendNumberUnit(std::string* out, double n, DisplayUnit unit) {
742 constexpr int kBufferSize = std::numeric_limits<double>::digits10;
743 const int prec = std::min(kBufferSize, unit.prec);
744 char buf[kBufferSize]; // also large enough to hold integer part
745 char* ep = buf + sizeof(buf);
746 double d = 0;
747 int64_t frac_part = std::round(std::modf(n, &d) * unit.pow10);
748 int64_t int_part = d;
749 if (int_part != 0 || frac_part != 0) {
750 char* bp = Format64(ep, 0, int_part); // always < 1000
751 out->append(bp, static_cast<size_t>(ep - bp));
752 if (frac_part != 0) {
753 out->push_back('.');
754 bp = Format64(ep, prec, frac_part);
755 while (ep[-1] == '0') --ep;
756 out->append(bp, static_cast<size_t>(ep - bp));
757 }
758 out->append(unit.abbr.data(), unit.abbr.size());
759 }
760 }
761
762 } // namespace
763
764 // From Go's doc at https://golang.org/pkg/time/#Duration.String
765 // [FormatDuration] returns a string representing the duration in the
766 // form "72h3m0.5s". Leading zero units are omitted. As a special
767 // case, durations less than one second format use a smaller unit
768 // (milli-, micro-, or nanoseconds) to ensure that the leading digit
769 // is non-zero.
770 // Unlike Go, we format the zero duration as 0, with no unit.
FormatDuration(Duration d)771 std::string FormatDuration(Duration d) {
772 constexpr Duration kMinDuration = Seconds(kint64min);
773 std::string s;
774 if (d == kMinDuration) {
775 // Avoid needing to negate kint64min by directly returning what the
776 // following code should produce in that case.
777 s = "-2562047788015215h30m8s";
778 return s;
779 }
780 if (d < ZeroDuration()) {
781 s.append("-");
782 d = -d;
783 }
784 if (d == InfiniteDuration()) {
785 s.append("inf");
786 } else if (d < Seconds(1)) {
787 // Special case for durations with a magnitude < 1 second. The duration
788 // is printed as a fraction of a single unit, e.g., "1.2ms".
789 if (d < Microseconds(1)) {
790 AppendNumberUnit(&s, FDivDuration(d, Nanoseconds(1)), kDisplayNano);
791 } else if (d < Milliseconds(1)) {
792 AppendNumberUnit(&s, FDivDuration(d, Microseconds(1)), kDisplayMicro);
793 } else {
794 AppendNumberUnit(&s, FDivDuration(d, Milliseconds(1)), kDisplayMilli);
795 }
796 } else {
797 AppendNumberUnit(&s, IDivDuration(d, Hours(1), &d), kDisplayHour);
798 AppendNumberUnit(&s, IDivDuration(d, Minutes(1), &d), kDisplayMin);
799 AppendNumberUnit(&s, FDivDuration(d, Seconds(1)), kDisplaySec);
800 }
801 if (s.empty() || s == "-") {
802 s = "0";
803 }
804 return s;
805 }
806
807 namespace {
808
809 // A helper for ParseDuration() that parses a leading number from the given
810 // string and stores the result in *int_part/*frac_part/*frac_scale. The
811 // given string pointer is modified to point to the first unconsumed char.
ConsumeDurationNumber(const char ** dpp,const char * ep,int64_t * int_part,int64_t * frac_part,int64_t * frac_scale)812 bool ConsumeDurationNumber(const char** dpp, const char* ep, int64_t* int_part,
813 int64_t* frac_part, int64_t* frac_scale) {
814 *int_part = 0;
815 *frac_part = 0;
816 *frac_scale = 1; // invariant: *frac_part < *frac_scale
817 const char* start = *dpp;
818 for (; *dpp != ep; *dpp += 1) {
819 const int d = **dpp - '0'; // contiguous digits
820 if (d < 0 || 10 <= d) break;
821
822 if (*int_part > kint64max / 10) return false;
823 *int_part *= 10;
824 if (*int_part > kint64max - d) return false;
825 *int_part += d;
826 }
827 const bool int_part_empty = (*dpp == start);
828 if (*dpp == ep || **dpp != '.') return !int_part_empty;
829
830 for (*dpp += 1; *dpp != ep; *dpp += 1) {
831 const int d = **dpp - '0'; // contiguous digits
832 if (d < 0 || 10 <= d) break;
833 if (*frac_scale <= kint64max / 10) {
834 *frac_part *= 10;
835 *frac_part += d;
836 *frac_scale *= 10;
837 }
838 }
839 return !int_part_empty || *frac_scale != 1;
840 }
841
842 // A helper for ParseDuration() that parses a leading unit designator (e.g.,
843 // ns, us, ms, s, m, h) from the given string and stores the resulting unit
844 // in "*unit". The given string pointer is modified to point to the first
845 // unconsumed char.
ConsumeDurationUnit(const char ** start,const char * end,Duration * unit)846 bool ConsumeDurationUnit(const char** start, const char* end, Duration* unit) {
847 size_t size = static_cast<size_t>(end - *start);
848 switch (size) {
849 case 0:
850 return false;
851 default:
852 switch (**start) {
853 case 'n':
854 if (*(*start + 1) == 's') {
855 *start += 2;
856 *unit = Nanoseconds(1);
857 return true;
858 }
859 break;
860 case 'u':
861 if (*(*start + 1) == 's') {
862 *start += 2;
863 *unit = Microseconds(1);
864 return true;
865 }
866 break;
867 case 'm':
868 if (*(*start + 1) == 's') {
869 *start += 2;
870 *unit = Milliseconds(1);
871 return true;
872 }
873 break;
874 default:
875 break;
876 }
877 ABSL_FALLTHROUGH_INTENDED;
878 case 1:
879 switch (**start) {
880 case 's':
881 *unit = Seconds(1);
882 *start += 1;
883 return true;
884 case 'm':
885 *unit = Minutes(1);
886 *start += 1;
887 return true;
888 case 'h':
889 *unit = Hours(1);
890 *start += 1;
891 return true;
892 default:
893 return false;
894 }
895 }
896 }
897
898 } // namespace
899
900 // From Go's doc at https://golang.org/pkg/time/#ParseDuration
901 // [ParseDuration] parses a duration string. A duration string is
902 // a possibly signed sequence of decimal numbers, each with optional
903 // fraction and a unit suffix, such as "300ms", "-1.5h" or "2h45m".
904 // Valid time units are "ns", "us" "ms", "s", "m", "h".
ParseDuration(absl::string_view dur_sv,Duration * d)905 bool ParseDuration(absl::string_view dur_sv, Duration* d) {
906 int sign = 1;
907 if (absl::ConsumePrefix(&dur_sv, "-")) {
908 sign = -1;
909 } else {
910 absl::ConsumePrefix(&dur_sv, "+");
911 }
912 if (dur_sv.empty()) return false;
913
914 // Special case for a string of "0".
915 if (dur_sv == "0") {
916 *d = ZeroDuration();
917 return true;
918 }
919
920 if (dur_sv == "inf") {
921 *d = sign * InfiniteDuration();
922 return true;
923 }
924
925 const char* start = dur_sv.data();
926 const char* end = start + dur_sv.size();
927
928 Duration dur;
929 while (start != end) {
930 int64_t int_part;
931 int64_t frac_part;
932 int64_t frac_scale;
933 Duration unit;
934 if (!ConsumeDurationNumber(&start, end, &int_part, &frac_part,
935 &frac_scale) ||
936 !ConsumeDurationUnit(&start, end, &unit)) {
937 return false;
938 }
939 if (int_part != 0) dur += sign * int_part * unit;
940 if (frac_part != 0) dur += sign * frac_part * unit / frac_scale;
941 }
942 *d = dur;
943 return true;
944 }
945
AbslParseFlag(absl::string_view text,Duration * dst,std::string *)946 bool AbslParseFlag(absl::string_view text, Duration* dst, std::string*) {
947 return ParseDuration(text, dst);
948 }
949
AbslUnparseFlag(Duration d)950 std::string AbslUnparseFlag(Duration d) { return FormatDuration(d); }
ParseFlag(const std::string & text,Duration * dst,std::string *)951 bool ParseFlag(const std::string& text, Duration* dst, std::string* ) {
952 return ParseDuration(text, dst);
953 }
954
UnparseFlag(Duration d)955 std::string UnparseFlag(Duration d) { return FormatDuration(d); }
956
957 ABSL_NAMESPACE_END
958 } // namespace absl
959