dom/media/TimeUnits.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include <cstdint>
   8 #include <cmath>
   9 #include <inttypes.h>
  10 #include <limits>
  11 #include <type_traits>
  12
  13 #include "TimeUnits.h"
  14 #include "Intervals.h"
  15 #include "mozilla/CheckedInt.h"
  16 #include "mozilla/FloatingPoint.h"
  17 #include "mozilla/Maybe.h"
  18 #include "mozilla/TimeStamp.h"
  19 #include "mozilla/IntegerPrintfMacros.h"
  20 #include "nsDebug.h"
  21 #include "nsPrintfCString.h"
  22 #include "nsStringFwd.h"
  23
  24 namespace mozilla::media {
  25 class TimeIntervals;
  26 }  // namespace mozilla::media
  27
  28 namespace mozilla {
  29
  30 namespace {
  31 struct Int96 {
  32   bool operator==(const Int96& aOther) const {
  33     return high == aOther.high && low == aOther.low;
  34   }
  35   bool operator>=(const Int96& aOther) const {
  36     if (high == aOther.high) {
  37       return low >= aOther.low;
  38     }
  39     return high > aOther.high;
  40   }
  41   bool operator<=(const Int96& aOther) const {
  42     if (high == aOther.high) {
  43       return low <= aOther.low;
  44     }
  45     return high < aOther.high;
  46   }
  47
  48   const int64_t high;
  49   const uint32_t low;
  50 };
  51 }  // anonymous namespace
  52
  53 static Int96 MultS64xU32(const CheckedInt64& a, int64_t b) {
  54   MOZ_ASSERT(b >= 0);
  55   MOZ_ASSERT(b <= UINT32_MAX);
  56   // Right shift of negative signed integers is implementation-defined until
  57   // C++20, but the C++20 two's complement behavior, used by all compilers
  58   // even prior to C++20, is assumed here.
  59   // (Left shift of negative signed integers would be undefined until C++20).
  60   int64_t high = (a.value() >> 32) * b;
  61   uint64_t low = a.value() & 0xFFFFFFFF;
  62   low *= b;
  63   // Move overflow from low multiplication to high.
  64   // This will not overflow because we have divided by 2^32 and multiplied
  65   // by b, which is less than 2^32.
  66   high += AssertedCast<int64_t>(low >> 32);
  67   return Int96{high, AssertedCast<uint32_t>(low & 0xFFFFFFFF)};
  68 };
  69
  70 namespace media {
  71
  72 TimeUnit TimeUnit::FromSeconds(double aValue, int64_t aBase) {
  73   MOZ_ASSERT(!std::isnan(aValue));
  74   MOZ_ASSERT(aBase > 0);
  75
  76   if (std::isinf(aValue)) {
  77     return aValue > 0 ? FromInfinity() : FromNegativeInfinity();
  78   }
  79   // Warn that a particular value won't be able to be roundtrip at the same
  80   // base -- we can keep this for some time until we're confident this is
  81   // stable.
  82   double inBase = aValue * static_cast<double>(aBase);
  83   if (std::abs(inBase) >
  84       static_cast<double>(std::numeric_limits<int64_t>::max())) {
  85     NS_WARNING(
  86         nsPrintfCString("Warning: base %" PRId64
  87                         " is too high to represent %lfs, returning Infinity.",
  88                         aBase, aValue)
  89             .get());
  90     if (inBase > 0) {
  91       return TimeUnit::FromInfinity();
  92     }
  93     return TimeUnit::FromNegativeInfinity();
  94   }
  95
  96   // inBase can large enough that it doesn't map to an exact integer, warn in
  97   // this case. This happens if aBase is large, and so the loss of precision is
  98   // likely small.
  99   if (inBase > std::pow(2, std::numeric_limits<double>::digits) - 1) {
 100     NS_WARNING(nsPrintfCString("Warning: base %" PRId64
 101                                " is too high to represent %lfs accurately.",
 102                                aBase, aValue)
 103                    .get());
 104   }
 105   return TimeUnit(static_cast<int64_t>(std::round(inBase)), aBase);
 106 }
 107
 108 TimeUnit TimeUnit::FromInfinity() { return TimeUnit(INT64_MAX); }
 109
 110 TimeUnit TimeUnit::FromNegativeInfinity() { return TimeUnit(INT64_MIN); }
 111
 112 TimeUnit TimeUnit::FromTimeDuration(const TimeDuration& aDuration) {
 113   // This could be made to choose the base
 114   return TimeUnit(AssertedCast<int64_t>(aDuration.ToMicroseconds()),
 115                   USECS_PER_S);
 116 }
 117
 118 TimeUnit TimeUnit::Invalid() {
 119   TimeUnit ret;
 120   ret.mTicks = CheckedInt64(INT64_MAX);
 121   // Force an overflow to render the CheckedInt invalid.
 122   ret.mTicks += 1;
 123   return ret;
 124 }
 125
 126 int64_t TimeUnit::ToMilliseconds() const { return ToCommonUnit(MSECS_PER_S); }
 127
 128 int64_t TimeUnit::ToMicroseconds() const { return ToCommonUnit(USECS_PER_S); }
 129
 130 int64_t TimeUnit::ToNanoseconds() const { return ToCommonUnit(NSECS_PER_S); }
 131
 132 int64_t TimeUnit::ToTicksAtRate(int64_t aRate) const {
 133   // Common case
 134   if (aRate == mBase) {
 135     return mTicks.value();
 136   }
 137   // Approximation
 138   return mTicks.value() * aRate / mBase;
 139 }
 140
 141 bool TimeUnit::IsBase(int64_t aBase) const { return aBase == mBase; }
 142
 143 double TimeUnit::ToSeconds() const {
 144   if (IsPosInf()) {
 145     return PositiveInfinity<double>();
 146   }
 147   if (IsNegInf()) {
 148     return NegativeInfinity<double>();
 149   }
 150   return static_cast<double>(mTicks.value()) / static_cast<double>(mBase);
 151 }
 152
 153 nsCString TimeUnit::ToString() const {
 154   nsCString dump;
 155   if (mTicks.isValid()) {
 156     dump += nsPrintfCString("{%" PRId64 ",%" PRId64 "}", mTicks.value(), mBase);
 157   } else {
 158     dump += nsLiteralCString("{invalid}"_ns);
 159   }
 160   return dump;
 161 }
 162
 163 TimeDuration TimeUnit::ToTimeDuration() const {
 164   return TimeDuration::FromSeconds(ToSeconds());
 165 }
 166
 167 bool TimeUnit::IsInfinite() const { return IsPosInf() || IsNegInf(); }
 168
 169 bool TimeUnit::IsPositive() const { return mTicks.value() > 0; }
 170
 171 bool TimeUnit::IsPositiveOrZero() const { return mTicks.value() >= 0; }
 172
 173 bool TimeUnit::IsZero() const { return mTicks.value() == 0; }
 174
 175 bool TimeUnit::IsNegative() const { return mTicks.value() < 0; }
 176
 177 // Returns true if the fractions are equal when converted to the smallest
 178 // base.
 179 bool TimeUnit::EqualsAtLowestResolution(const TimeUnit& aOther) const {
 180   MOZ_ASSERT(IsValid() && aOther.IsValid());
 181   if (aOther.mBase == mBase) {
 182     return mTicks == aOther.mTicks;
 183   }
 184   if (mBase > aOther.mBase) {
 185     TimeUnit thisInBase = ToBase(aOther.mBase);
 186     return thisInBase.mTicks == aOther.mTicks;
 187   }
 188   TimeUnit otherInBase = aOther.ToBase(mBase);
 189   return otherInBase.mTicks == mTicks;
 190 }
 191
 192 // Strict equality -- the fractions must be exactly equal
 193 bool TimeUnit::operator==(const TimeUnit& aOther) const {
 194   MOZ_ASSERT(IsValid() && aOther.IsValid());
 195   if (aOther.mBase == mBase) {
 196     return mTicks == aOther.mTicks;
 197   }
 198   // debatable mathematically
 199   if ((IsPosInf() && aOther.IsPosInf()) || (IsNegInf() && aOther.IsNegInf())) {
 200     return true;
 201   }
 202   if ((IsPosInf() && !aOther.IsPosInf()) ||
 203       (IsNegInf() && !aOther.IsNegInf())) {
 204     return false;
 205   }
 206   Int96 lhs = MultS64xU32(mTicks, aOther.mBase);
 207   Int96 rhs = MultS64xU32(aOther.mTicks, mBase);
 208   return lhs == rhs;
 209 }
 210 bool TimeUnit::operator!=(const TimeUnit& aOther) const {
 211   MOZ_ASSERT(IsValid() && aOther.IsValid());
 212   return !(aOther == *this);
 213 }
 214 bool TimeUnit::operator>=(const TimeUnit& aOther) const {
 215   MOZ_ASSERT(IsValid() && aOther.IsValid());
 216   if (aOther.mBase == mBase) {
 217     return mTicks.value() >= aOther.mTicks.value();
 218   }
 219   if ((!IsPosInf() && aOther.IsPosInf()) ||
 220       (IsNegInf() && !aOther.IsNegInf())) {
 221     return false;
 222   }
 223   if ((IsPosInf() && !aOther.IsPosInf()) ||
 224       (!IsNegInf() && aOther.IsNegInf())) {
 225     return true;
 226   }
 227   Int96 lhs = MultS64xU32(mTicks, aOther.mBase);
 228   Int96 rhs = MultS64xU32(aOther.mTicks, mBase);
 229   return lhs >= rhs;
 230 }
 231 bool TimeUnit::operator>(const TimeUnit& aOther) const {
 232   return !(*this <= aOther);
 233 }
 234 bool TimeUnit::operator<=(const TimeUnit& aOther) const {
 235   MOZ_ASSERT(IsValid() && aOther.IsValid());
 236   if (aOther.mBase == mBase) {
 237     return mTicks.value() <= aOther.mTicks.value();
 238   }
 239   if ((!IsPosInf() && aOther.IsPosInf()) ||
 240       (IsNegInf() && !aOther.IsNegInf())) {
 241     return true;
 242   }
 243   if ((IsPosInf() && !aOther.IsPosInf()) ||
 244       (!IsNegInf() && aOther.IsNegInf())) {
 245     return false;
 246   }
 247   Int96 lhs = MultS64xU32(mTicks, aOther.mBase);
 248   Int96 rhs = MultS64xU32(aOther.mTicks, mBase);
 249   return lhs <= rhs;
 250 }
 251 bool TimeUnit::operator<(const TimeUnit& aOther) const {
 252   return !(*this >= aOther);
 253 }
 254
 255 TimeUnit TimeUnit::operator%(const TimeUnit& aOther) const {
 256   MOZ_ASSERT(IsValid() && aOther.IsValid());
 257   if (aOther.mBase == mBase) {
 258     return TimeUnit(mTicks % aOther.mTicks, mBase);
 259   }
 260   // This path can be made better if need be.
 261   double a = ToSeconds();
 262   double b = aOther.ToSeconds();
 263   return TimeUnit::FromSeconds(fmod(a, b), mBase);
 264 }
 265
 266 TimeUnit TimeUnit::operator+(const TimeUnit& aOther) const {
 267   if (IsInfinite() || aOther.IsInfinite()) {
 268     // When adding at least one infinite value, the result is either
 269     // +/-Inf, or NaN. So do the calculation in floating point for
 270     // simplicity.
 271     double result = ToSeconds() + aOther.ToSeconds();
 272     return std::isnan(result) ? TimeUnit::Invalid() : FromSeconds(result);
 273   }
 274   if (aOther.mBase == mBase) {
 275     return TimeUnit(mTicks + aOther.mTicks, mBase);
 276   }
 277   if (aOther.IsZero()) {
 278     return *this;
 279   }
 280   if (IsZero()) {
 281     return aOther;
 282   }
 283
 284   double error;
 285   TimeUnit inBase = aOther.ToBase(mBase, error);
 286   if (error == 0.0) {
 287     return *this + inBase;
 288   }
 289
 290   // Last ditch: not exact
 291   double a = ToSeconds();
 292   double b = aOther.ToSeconds();
 293   return TimeUnit::FromSeconds(a + b, mBase);
 294 }
 295
 296 TimeUnit TimeUnit::operator-(const TimeUnit& aOther) const {
 297   if (IsInfinite() || aOther.IsInfinite()) {
 298     // When subtracting at least one infinite value, the result is either
 299     // +/-Inf, or NaN. So do the calculation in floating point for
 300     // simplicity.
 301     double result = ToSeconds() - aOther.ToSeconds();
 302     return std::isnan(result) ? TimeUnit::Invalid() : FromSeconds(result);
 303   }
 304   if (aOther.mBase == mBase) {
 305     return TimeUnit(mTicks - aOther.mTicks, mBase);
 306   }
 307   if (aOther.IsZero()) {
 308     return *this;
 309   }
 310
 311   if (IsZero()) {
 312     return TimeUnit(-aOther.mTicks, aOther.mBase);
 313   }
 314
 315   double error = 0.0;
 316   TimeUnit inBase = aOther.ToBase(mBase, error);
 317   if (error == 0) {
 318     return *this - inBase;
 319   }
 320
 321   // Last ditch: not exact
 322   double a = ToSeconds();
 323   double b = aOther.ToSeconds();
 324   return TimeUnit::FromSeconds(a - b, mBase);
 325 }
 326 TimeUnit& TimeUnit::operator+=(const TimeUnit& aOther) {
 327   if (aOther.mBase == mBase) {
 328     mTicks += aOther.mTicks;
 329     return *this;
 330   }
 331   *this = *this + aOther;
 332   return *this;
 333 }
 334 TimeUnit& TimeUnit::operator-=(const TimeUnit& aOther) {
 335   if (aOther.mBase == mBase) {
 336     mTicks -= aOther.mTicks;
 337     return *this;
 338   }
 339   *this = *this - aOther;
 340   return *this;
 341 }
 342
 343 TimeUnit TimeUnit::MultDouble(double aVal) const {
 344   double multiplied = AssertedCast<double>(mTicks.value()) * aVal;
 345   // Check is the result of the multiplication can be represented exactly as
 346   // an integer, in a double.
 347   if (multiplied > std::pow(2, std::numeric_limits<double>::digits) - 1) {
 348     printf_stderr("TimeUnit tick count after multiplication %" PRId64
 349                   " * %lf is too"
 350                   " high for the result to be exact",
 351                   mTicks.value(), aVal);
 352     MOZ_CRASH();
 353   }
 354   // static_cast is ok, the magnitude of the number has been checked just above.
 355   return TimeUnit(static_cast<int64_t>(multiplied), mBase);
 356 }
 357
 358 bool TimeUnit::IsValid() const { return mTicks.isValid(); }
 359
 360 bool TimeUnit::IsPosInf() const {
 361   return mTicks.isValid() && mTicks.value() == INT64_MAX;
 362 }
 363 bool TimeUnit::IsNegInf() const {
 364   return mTicks.isValid() && mTicks.value() == INT64_MIN;
 365 }
 366
 367 int64_t TimeUnit::ToCommonUnit(int64_t aRatio) const {
 368   CheckedInt<int64_t> rv = mTicks;
 369   // Avoid the risk overflowing in common cases, e.g. converting a TimeUnit
 370   // with a base of 1e9 back to nanoseconds.
 371   if (mBase == aRatio) {
 372     return rv.value();
 373   }
 374   // Avoid overflowing in other common cases, e.g. converting a TimeUnit with
 375   // a base of 1e9 to microseconds: the denominator is divisible by the target
 376   // unit so we can reorder the computation and keep the number within int64_t
 377   // range.
 378   if (aRatio < mBase && (mBase % aRatio) == 0) {
 379     int64_t exactDivisor = mBase / aRatio;
 380     rv /= exactDivisor;
 381     return rv.value();
 382   }
 383   rv *= aRatio;
 384   rv /= mBase;
 385   if (rv.isValid()) {
 386     return rv.value();
 387   }
 388   // Last ditch, perform the computation in floating point.
 389   double ratioFloating = AssertedCast<double>(aRatio);
 390   double baseFloating = AssertedCast<double>(mBase);
 391   double ticksFloating = static_cast<double>(mTicks.value());
 392   double approx = ticksFloating * (ratioFloating / baseFloating);
 393   // Clamp to a valid range. If this is clamped it's outside any usable time
 394   // value even in nanoseconds (thousands of years).
 395   if (approx > static_cast<double>(std::numeric_limits<int64_t>::max())) {
 396     return std::numeric_limits<int64_t>::max();
 397   }
 398   if (approx < static_cast<double>(std::numeric_limits<int64_t>::lowest())) {
 399     return std::numeric_limits<int64_t>::lowest();
 400   }
 401   return static_cast<int64_t>(approx);
 402 }
 403
 404 // Reduce a TimeUnit to the smallest possible ticks and base. This is useful
 405 // to comparison with big time values that can otherwise overflow.
 406 TimeUnit TimeUnit::Reduced() const {
 407   int64_t posTicks = abs(mTicks.value());
 408   bool wasNeg = mTicks.value() < 0;
 409   int64_t gcd = GCD(posTicks, mBase);
 410   int64_t signedTicks = wasNeg ? -posTicks : posTicks;
 411   signedTicks /= gcd;
 412   return TimeUnit(signedTicks, mBase / gcd);
 413 }
 414
 415 double RoundToMicrosecondResolution(double aSeconds) {
 416   return std::round(aSeconds * USECS_PER_S) / USECS_PER_S;
 417 }
 418
 419 TimeRanges TimeRanges::ToMicrosecondResolution() const {
 420   TimeRanges output;
 421
 422   for (const auto& interval : mIntervals) {
 423     TimeRange reducedPrecision{RoundToMicrosecondResolution(interval.mStart),
 424                                RoundToMicrosecondResolution(interval.mEnd),
 425                                RoundToMicrosecondResolution(interval.mFuzz)};
 426     output += reducedPrecision;
 427   }
 428   return output;
 429 }
 430
 431 };  // namespace media
 432
 433 }  // namespace mozilla