media/filters/video_cadence_estimator.cc

   1 // Copyright 2015 The Chromium Authors
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "media/filters/video_cadence_estimator.h"
   6
   7 #include <algorithm>
   8 #include <cmath>
   9 #include <iterator>
  10 #include <limits>
  11 #include <numeric>
  12 #include <string>
  13
  14 #include "base/logging.h"
  15 #include "base/metrics/histogram_macros.h"
  16 #include "media/base/media_switches.h"
  17
  18 namespace media {
  19
  20 // To prevent oscillation in and out of cadence or between cadence values, we
  21 // require some time to elapse before a cadence switch is accepted.
  22 const int kMinimumCadenceDurationMs = 100;
  23
  24 // The numbers are used to decide whether the current video is variable FPS or
  25 // constant FPS. If ratio of the sample deviation and the render length is
  26 // above |kVariableFPSFactor|, then it is recognized as a variable FPS, and if
  27 // the ratio is below |kConstantFPSFactor|, then it is recognized as a constant
  28 // FPS, and if the ratio is in between the two factors, then we do not change
  29 // previous recognition.
  30 const double kVariableFPSFactor = 0.55;
  31 const double kConstantFPSFactor = 0.45;
  32
  33 // Records the number of cadence changes to UMA.
  34 static void HistogramCadenceChangeCount(int cadence_changes) {
  35   const int kCadenceChangeMax = 10;
  36   UMA_HISTOGRAM_CUSTOM_COUNTS("Media.VideoRenderer.CadenceChanges",
  37                               cadence_changes, 1, kCadenceChangeMax,
  38                               kCadenceChangeMax);
  39 }
  40
  41 // Construct a Cadence vector, a vector of integers satisfying the following
  42 // conditions:
  43 // 1. Size is |n|.
  44 // 2. Sum of entries is |k|.
  45 // 3. Each entry is in {|k|/|n|, |k|/|n| + 1}.
  46 // 4. Distribution of |k|/|n| and |k|/|n| + 1 is as even as possible.
  47 VideoCadenceEstimator::Cadence ConstructCadence(int k, int n) {
  48   const int quotient = k / n;
  49   std::vector<int> output(n, 0);
  50
  51   // Fill the vector entries with |quotient| or |quotient + 1|, and make sure
  52   // the two values are distributed as evenly as possible.
  53   int target_accumulate = 0;
  54   int actual_accumulate = 0;
  55   for (int i = 0; i < n; ++i) {
  56     // After each loop
  57     // target_accumulate = (i + 1) * k
  58     // actual_accumulate = \sum_{j = 0}^i {n * V[j]} where V is output vector
  59     // We want to make actual_accumulate as close to target_accumulate as
  60     // possible.
  61     // One exception is that in case k < n, we always want the vector to start
  62     // with 1 to make sure the first frame is always rendered.
  63     // (To avoid float calculation, we use scaled version of accumulated count)
  64     target_accumulate += k;
  65     const int target_current = target_accumulate - actual_accumulate;
  66     if ((i == 0 && k < n) || target_current * 2 >= n * (quotient * 2 + 1)) {
  67       output[i] = quotient + 1;
  68     } else {
  69       output[i] = quotient;
  70     }
  71     actual_accumulate += output[i] * n;
  72   }
  73
  74   return output;
  75 }
  76
  77 VideoCadenceEstimator::Cadence ConstructSimpleCadence(
  78     double perfect_cadence,
  79     base::TimeDelta max_acceptable_drift,
  80     base::TimeDelta* time_until_max_drift) {
  81   int cadence_value = round(perfect_cadence);
  82   if (cadence_value < 0) {
  83     return VideoCadenceEstimator::Cadence();
  84   }
  85   if (cadence_value == 0) {
  86     cadence_value = 1;
  87   }
  88   VideoCadenceEstimator::Cadence result = ConstructCadence(cadence_value, 1);
  89
  90   // The computation for time_until_max_drift below is equivalent to
  91   // time_until_max_drift = render_interval * (max_acceptable_drift /
  92   // abs(frame_duration - render_interval))
  93   const double error = std::fabs(1.0 - perfect_cadence / cadence_value);
  94   *time_until_max_drift = max_acceptable_drift / error;
  95   return result;
  96 }
  97
  98 VideoCadenceEstimator::VideoCadenceEstimator(
  99     base::TimeDelta minimum_time_until_max_drift)
 100     : cadence_hysteresis_threshold_(
 101           base::Milliseconds(kMinimumCadenceDurationMs)),
 102       minimum_time_until_max_drift_(minimum_time_until_max_drift),
 103       is_variable_frame_rate_(false) {
 104   Reset();
 105 }
 106
 107 VideoCadenceEstimator::~VideoCadenceEstimator() = default;
 108
 109 void VideoCadenceEstimator::Reset() {
 110   cadence_.clear();
 111   pending_cadence_.clear();
 112   cadence_changes_ = render_intervals_cadence_held_ = 0;
 113   first_update_call_ = true;
 114 }
 115
 116 bool VideoCadenceEstimator::UpdateCadenceEstimate(
 117     base::TimeDelta render_interval,
 118     base::TimeDelta frame_duration,
 119     base::TimeDelta frame_duration_deviation,
 120     base::TimeDelta max_acceptable_drift) {
 121   DCHECK_GT(render_interval, base::TimeDelta());
 122   DCHECK_GT(frame_duration, base::TimeDelta());
 123
 124   if (frame_duration_deviation > kVariableFPSFactor * render_interval) {
 125     is_variable_frame_rate_ = true;
 126   } else if (frame_duration_deviation < kConstantFPSFactor * render_interval) {
 127     is_variable_frame_rate_ = false;
 128   }
 129
 130   // Variable FPS detected, turn off Cadence by force.
 131   if (is_variable_frame_rate_) {
 132     render_intervals_cadence_held_ = 0;
 133     if (!cadence_.empty()) {
 134       cadence_.clear();
 135       return true;
 136     }
 137     return false;
 138   }
 139
 140   base::TimeDelta time_until_max_drift;
 141
 142   // See if we can find a cadence which fits the data.
 143   Cadence new_cadence =
 144       CalculateCadence(render_interval, frame_duration, max_acceptable_drift,
 145                        &time_until_max_drift);
 146
 147   // If this is the first time UpdateCadenceEstimate() has been called,
 148   // initialize the histogram with a zero count for cadence changes; this
 149   // allows us to track the number of playbacks which have cadence at all.
 150   if (first_update_call_) {
 151     DCHECK_EQ(cadence_changes_, 0);
 152     first_update_call_ = false;
 153     HistogramCadenceChangeCount(0);
 154   }
 155
 156   // If nothing changed, do nothing.
 157   if (new_cadence == cadence_) {
 158     // Clear cadence hold to pending values from accumulating incorrectly.
 159     render_intervals_cadence_held_ = 0;
 160     return false;
 161   }
 162
 163   // Wait until enough render intervals have elapsed before accepting the
 164   // cadence change.  Prevents oscillation of the cadence selection.
 165   bool update_pending_cadence = true;
 166   if (new_cadence == pending_cadence_ ||
 167       cadence_hysteresis_threshold_ <= render_interval) {
 168     if (++render_intervals_cadence_held_ * render_interval >=
 169         cadence_hysteresis_threshold_) {
 170       DVLOG(1) << "Cadence switch: " << CadenceToString(cadence_) << " -> "
 171                << CadenceToString(new_cadence)
 172                << " :: Time until drift exceeded: " << time_until_max_drift;
 173       cadence_.swap(new_cadence);
 174
 175       // Note: Because this class is transitively owned by a garbage collected
 176       // object, WebMediaPlayer, we log cadence changes as they are encountered.
 177       HistogramCadenceChangeCount(++cadence_changes_);
 178       return true;
 179     }
 180
 181     update_pending_cadence = false;
 182   }
 183
 184   DVLOG(2) << "Hysteresis prevented cadence switch: "
 185            << CadenceToString(cadence_) << " -> "
 186            << CadenceToString(new_cadence);
 187
 188   if (update_pending_cadence) {
 189     pending_cadence_.swap(new_cadence);
 190     render_intervals_cadence_held_ = 1;
 191   }
 192
 193   return false;
 194 }
 195
 196 int VideoCadenceEstimator::GetCadenceForFrame(uint64_t frame_number) const {
 197   DCHECK(has_cadence());
 198   return cadence_[frame_number % cadence_.size()];
 199 }
 200
 201 bool VideoCadenceEstimator::HasSimpleCadence(
 202     base::TimeDelta render_interval,
 203     base::TimeDelta frame_duration,
 204     base::TimeDelta minimum_time_until_max_drift) {
 205   const double perfect_cadence = frame_duration / render_interval;
 206   base::TimeDelta time_until_max_drift;
 207   auto cadence = ConstructSimpleCadence(perfect_cadence, render_interval,
 208                                         &time_until_max_drift);
 209   return !cadence.empty() &&
 210          time_until_max_drift >= minimum_time_until_max_drift;
 211 }
 212
 213 VideoCadenceEstimator::Cadence VideoCadenceEstimator::CalculateCadence(
 214     base::TimeDelta render_interval,
 215     base::TimeDelta frame_duration,
 216     base::TimeDelta max_acceptable_drift,
 217     base::TimeDelta* time_until_max_drift) const {
 218   // The perfect cadence is the number of render intervals per frame.
 219   const double perfect_cadence = frame_duration / render_interval;
 220
 221   // This case is very simple, just return a single frame cadence, because it
 222   // is impossible for us to accumulate drift as large as max_acceptable_drift
 223   // within minimum_time_until_max_drift.
 224   if (max_acceptable_drift >= minimum_time_until_max_drift_) {
 225     return ConstructSimpleCadence(perfect_cadence, max_acceptable_drift,
 226                                   time_until_max_drift);
 227   }
 228
 229   // We want to construct a cadence pattern to approximate the perfect cadence
 230   // while ensuring error doesn't accumulate too quickly.
 231   const double drift_ratio =
 232       max_acceptable_drift / minimum_time_until_max_drift_;
 233   const double minimum_acceptable_cadence =
 234       perfect_cadence / (1.0 + drift_ratio);
 235   const double maximum_acceptable_cadence =
 236       perfect_cadence / (1.0 - drift_ratio);
 237
 238   // We've arbitrarily chosen the maximum allowable cadence length as 5. It's
 239   // proven sufficient to support most standard frame and render rates, while
 240   // being small enough that small frame and render timing errors don't render
 241   // it useless.
 242   const int kMaxCadenceSize = 5;
 243
 244   double best_error = 0;
 245   int best_n = 0;
 246   int best_k = 0;
 247   for (int n = 1; n <= kMaxCadenceSize; ++n) {
 248     // A cadence pattern only exists if there exists an integer K such that K/N
 249     // is between |minimum_acceptable_cadence| and |maximum_acceptable_cadence|.
 250     // The best pattern is the one with the smallest error over time relative to
 251     // the |perfect_cadence|.
 252     if (std::floor(minimum_acceptable_cadence * n) <
 253         std::floor(maximum_acceptable_cadence * n)) {
 254       const int k = round(perfect_cadence * n);
 255
 256       const double error = std::fabs(1.0 - perfect_cadence * n / k);
 257
 258       // Prefer the shorter cadence pattern unless a longer one "significantly"
 259       // reduces the error.
 260       if (!best_n || error < best_error * 0.99) {
 261         best_error = error;
 262         best_k = k;
 263         best_n = n;
 264       }
 265     }
 266   }
 267
 268   if (!best_n) {
 269     Cadence cadence = ConstructSimpleCadence(
 270         perfect_cadence, max_acceptable_drift, time_until_max_drift);
 271     if (!cadence.empty() &&
 272         *time_until_max_drift >= minimum_time_until_max_drift_) {
 273       return cadence;
 274     }
 275     return Cadence();
 276   }
 277
 278   // If we've found a solution.
 279   Cadence best_result = ConstructCadence(best_k, best_n);
 280   *time_until_max_drift = max_acceptable_drift / best_error;
 281
 282   return best_result;
 283 }
 284
 285 std::string VideoCadenceEstimator::CadenceToString(
 286     const Cadence& cadence) const {
 287   if (cadence.empty())
 288     return std::string("[]");
 289
 290   std::ostringstream os;
 291   os << "[";
 292   std::copy(cadence.begin(), cadence.end() - 1,
 293             std::ostream_iterator<int>(os, ":"));
 294   os << cadence.back() << "]";
 295   return os.str();
 296 }
 297
 298 double VideoCadenceEstimator::avg_cadence_for_testing() const {
 299   if (!has_cadence())
 300     return 0.0;
 301
 302   int sum = std::accumulate(begin(cadence_), end(cadence_), 0);
 303   return static_cast<double>(sum) / cadence_.size();
 304 }
 305
 306 }  // namespace media