| // Copyright 2015 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "media/filters/video_cadence_estimator.h" |
| |
| #include <algorithm> |
| #include <cmath> |
| #include <iterator> |
| #include <limits> |
| #include <numeric> |
| #include <string> |
| |
| #include "base/logging.h" |
| #include "base/metrics/histogram_macros.h" |
| #include "media/base/media_switches.h" |
| |
| namespace media { |
| |
| // To prevent oscillation in and out of cadence or between cadence values, we |
| // require some time to elapse before a cadence switch is accepted. |
| const int kMinimumCadenceDurationMs = 100; |
| |
| // The numbers are used to decide whether the current video is variable FPS or |
| // constant FPS. If ratio of the sample deviation and the render length is |
| // above |kVariableFPSFactor|, then it is recognized as a variable FPS, and if |
| // the ratio is below |kConstantFPSFactor|, then it is recognized as a constant |
| // FPS, and if the ratio is in between the two factors, then we do not change |
| // previous recognition. |
| const double kVariableFPSFactor = 0.55; |
| const double kConstantFPSFactor = 0.45; |
| |
| // Records the number of cadence changes to UMA. |
| static void HistogramCadenceChangeCount(int cadence_changes) { |
| const int kCadenceChangeMax = 10; |
| UMA_HISTOGRAM_CUSTOM_COUNTS("Media.VideoRenderer.CadenceChanges", |
| cadence_changes, 1, kCadenceChangeMax, |
| kCadenceChangeMax); |
| } |
| |
| // Construct a Cadence vector, a vector of integers satisfying the following |
| // conditions: |
| // 1. Size is |n|. |
| // 2. Sum of entries is |k|. |
| // 3. Each entry is in {|k|/|n|, |k|/|n| + 1}. |
| // 4. Distribution of |k|/|n| and |k|/|n| + 1 is as even as possible. |
| VideoCadenceEstimator::Cadence ConstructCadence(int k, int n) { |
| const int quotient = k / n; |
| std::vector<int> output(n, 0); |
| |
| // Fill the vector entries with |quotient| or |quotient + 1|, and make sure |
| // the two values are distributed as evenly as possible. |
| int target_accumulate = 0; |
| int actual_accumulate = 0; |
| for (int i = 0; i < n; ++i) { |
| // After each loop |
| // target_accumulate = (i + 1) * k |
| // actual_accumulate = \sum_{j = 0}^i {n * V[j]} where V is output vector |
| // We want to make actual_accumulate as close to target_accumulate as |
| // possible. |
| // One exception is that in case k < n, we always want the vector to start |
| // with 1 to make sure the first frame is always rendered. |
| // (To avoid float calculation, we use scaled version of accumulated count) |
| target_accumulate += k; |
| const int target_current = target_accumulate - actual_accumulate; |
| if ((i == 0 && k < n) || target_current * 2 >= n * (quotient * 2 + 1)) { |
| output[i] = quotient + 1; |
| } else { |
| output[i] = quotient; |
| } |
| actual_accumulate += output[i] * n; |
| } |
| |
| return output; |
| } |
| |
| VideoCadenceEstimator::VideoCadenceEstimator( |
| base::TimeDelta minimum_time_until_max_drift) |
| : cadence_hysteresis_threshold_( |
| base::Milliseconds(kMinimumCadenceDurationMs)), |
| minimum_time_until_max_drift_(minimum_time_until_max_drift), |
| is_variable_frame_rate_(false) { |
| Reset(); |
| } |
| |
| VideoCadenceEstimator::~VideoCadenceEstimator() = default; |
| |
| void VideoCadenceEstimator::Reset() { |
| cadence_.clear(); |
| pending_cadence_.clear(); |
| cadence_changes_ = render_intervals_cadence_held_ = 0; |
| first_update_call_ = true; |
| |
| bm_.use_bresenham_cadence_ = |
| base::FeatureList::IsEnabled(media::kBresenhamCadence); |
| bm_.perfect_cadence_.reset(); |
| bm_.frame_index_shift_ = 0; |
| } |
| |
| bool VideoCadenceEstimator::UpdateCadenceEstimate( |
| base::TimeDelta render_interval, |
| base::TimeDelta frame_duration, |
| base::TimeDelta frame_duration_deviation, |
| base::TimeDelta max_acceptable_drift) { |
| DCHECK_GT(render_interval, base::TimeDelta()); |
| DCHECK_GT(frame_duration, base::TimeDelta()); |
| |
| if (frame_duration_deviation > kVariableFPSFactor * render_interval) { |
| is_variable_frame_rate_ = true; |
| } else if (frame_duration_deviation < kConstantFPSFactor * render_interval) { |
| is_variable_frame_rate_ = false; |
| } |
| |
| if (bm_.use_bresenham_cadence_) |
| return UpdateBresenhamCadenceEstimate(render_interval, frame_duration); |
| |
| // Variable FPS detected, turn off Cadence by force. |
| if (is_variable_frame_rate_) { |
| render_intervals_cadence_held_ = 0; |
| if (!cadence_.empty()) { |
| cadence_.clear(); |
| return true; |
| } |
| return false; |
| } |
| |
| base::TimeDelta time_until_max_drift; |
| |
| // See if we can find a cadence which fits the data. |
| Cadence new_cadence = |
| CalculateCadence(render_interval, frame_duration, max_acceptable_drift, |
| &time_until_max_drift); |
| |
| // If this is the first time UpdateCadenceEstimate() has been called, |
| // initialize the histogram with a zero count for cadence changes; this |
| // allows us to track the number of playbacks which have cadence at all. |
| if (first_update_call_) { |
| DCHECK_EQ(cadence_changes_, 0); |
| first_update_call_ = false; |
| HistogramCadenceChangeCount(0); |
| } |
| |
| // If nothing changed, do nothing. |
| if (new_cadence == cadence_) { |
| // Clear cadence hold to pending values from accumulating incorrectly. |
| render_intervals_cadence_held_ = 0; |
| return false; |
| } |
| |
| // Wait until enough render intervals have elapsed before accepting the |
| // cadence change. Prevents oscillation of the cadence selection. |
| bool update_pending_cadence = true; |
| if (new_cadence == pending_cadence_ || |
| cadence_hysteresis_threshold_ <= render_interval) { |
| if (++render_intervals_cadence_held_ * render_interval >= |
| cadence_hysteresis_threshold_) { |
| DVLOG(1) << "Cadence switch: " << CadenceToString(cadence_) << " -> " |
| << CadenceToString(new_cadence) |
| << " :: Time until drift exceeded: " << time_until_max_drift; |
| cadence_.swap(new_cadence); |
| |
| // Note: Because this class is transitively owned by a garbage collected |
| // object, WebMediaPlayer, we log cadence changes as they are encountered. |
| HistogramCadenceChangeCount(++cadence_changes_); |
| return true; |
| } |
| |
| update_pending_cadence = false; |
| } |
| |
| DVLOG(2) << "Hysteresis prevented cadence switch: " |
| << CadenceToString(cadence_) << " -> " |
| << CadenceToString(new_cadence); |
| |
| if (update_pending_cadence) { |
| pending_cadence_.swap(new_cadence); |
| render_intervals_cadence_held_ = 1; |
| } |
| |
| return false; |
| } |
| |
| int VideoCadenceEstimator::GetCadenceForFrame(uint64_t frame_number) const { |
| DCHECK(has_cadence()); |
| if (bm_.use_bresenham_cadence_) { |
| double cadence = *bm_.perfect_cadence_; |
| auto index = frame_number + bm_.frame_index_shift_; |
| auto result = static_cast<uint64_t>(cadence * (index + 1)) - |
| static_cast<uint64_t>(cadence * index); |
| DCHECK(frame_number > 0 || result > 0); |
| return result; |
| } |
| return cadence_[frame_number % cadence_.size()]; |
| } |
| |
| /* List of tests that are expected to fail when media::kBresenhamCadence |
| is enabled. |
| - VideoRendererAlgorithmTest.BestFrameByCadenceOverdisplayedForDrift |
| Reason: Bresenham cadence does not exhibit innate drift. |
| - VideoRendererAlgorithmTest.CadenceCalculations |
| Reason: The test inspects an internal data structures of the current alg. |
| - VideoRendererAlgorithmTest.VariablePlaybackRateCadence |
| Reason: The test assumes that cadence algorithm should fail for playback |
| rate of 3.15. Bresenham alg works fine. |
| |
| - VideoCadenceEstimatorTest.CadenceCalculationWithLargeDeviation |
| - VideoCadenceEstimatorTest.CadenceCalculationWithLargeDrift |
| - VideoCadenceEstimatorTest.CadenceCalculations |
| - VideoCadenceEstimatorTest.CadenceHystersisPreventsOscillation |
| - VideoCadenceEstimatorTest.CadenceVariesWithAcceptableDrift |
| - VideoCadenceEstimatorTest.CadenceVariesWithAcceptableGlitchTime |
| Reason: These tests inspects an internal data structures of the current |
| algorithm. |
| */ |
| bool VideoCadenceEstimator::UpdateBresenhamCadenceEstimate( |
| base::TimeDelta render_interval, |
| base::TimeDelta frame_duration) { |
| if (is_variable_frame_rate_) { |
| if (bm_.perfect_cadence_.has_value()) { |
| bm_.perfect_cadence_.reset(); |
| return true; |
| } |
| return false; |
| } |
| |
| if (++render_intervals_cadence_held_ * render_interval < |
| cadence_hysteresis_threshold_) { |
| return false; |
| } |
| |
| double current_cadence = bm_.perfect_cadence_.value_or(0.0); |
| double new_cadence = frame_duration / render_interval; |
| DCHECK_GE(new_cadence, 0.0); |
| |
| double cadence_relative_diff = std::abs(current_cadence - new_cadence) / |
| std::max(current_cadence, new_cadence); |
| |
| // Ignore small changes in cadence, as they are most likely just noise, |
| // caused by render_interval flickering on devices having difficulty to decode |
| // and render the video in real time. |
| // TODO(ezemtsov): Consider calculating and using avg. render_interval, |
| // the same way avg. frame duration is used now. |
| constexpr double kCadenceRoundingError = 0.008; |
| if (cadence_relative_diff <= kCadenceRoundingError) |
| return false; |
| |
| bm_.perfect_cadence_ = new_cadence; |
| if (render_interval > frame_duration) { |
| // When display refresh rate is lower than the video frame rate, |
| // not all frames can be shown. But we want to make sure that the very |
| // first frame is shown. That's why frame indexes are shifted by this |
| // much to make sure that the cadence sequence always has 1 in the |
| // beginning. |
| bm_.frame_index_shift_ = (render_interval.InMicroseconds() - 1) / |
| frame_duration.InMicroseconds(); |
| } else { |
| // It can be 0 (or anything), but it makes the output look more like |
| // an output of the current cadence algorithm. |
| bm_.frame_index_shift_ = 1; |
| } |
| |
| DVLOG(1) << "Cadence switch" |
| << " perfect_cadence: " << new_cadence |
| << " frame_index_shift: " << bm_.frame_index_shift_ |
| << " cadence_relative_diff: " << cadence_relative_diff |
| << " cadence_held: " << render_intervals_cadence_held_; |
| render_intervals_cadence_held_ = 0; |
| return true; |
| } |
| |
| VideoCadenceEstimator::Cadence VideoCadenceEstimator::CalculateCadence( |
| base::TimeDelta render_interval, |
| base::TimeDelta frame_duration, |
| base::TimeDelta max_acceptable_drift, |
| base::TimeDelta* time_until_max_drift) const { |
| // The perfect cadence is the number of render intervals per frame. |
| const double perfect_cadence = frame_duration / render_interval; |
| |
| // This case is very simple, just return a single frame cadence, because it |
| // is impossible for us to accumulate drift as large as max_acceptable_drift |
| // within minimum_time_until_max_drift. |
| if (max_acceptable_drift >= minimum_time_until_max_drift_) { |
| int cadence_value = round(perfect_cadence); |
| if (cadence_value < 0) |
| return Cadence(); |
| if (cadence_value == 0) |
| cadence_value = 1; |
| Cadence result = ConstructCadence(cadence_value, 1); |
| const double error = std::fabs(1.0 - perfect_cadence / cadence_value); |
| *time_until_max_drift = max_acceptable_drift / error; |
| return result; |
| } |
| |
| // We want to construct a cadence pattern to approximate the perfect cadence |
| // while ensuring error doesn't accumulate too quickly. |
| const double drift_ratio = |
| max_acceptable_drift / minimum_time_until_max_drift_; |
| const double minimum_acceptable_cadence = |
| perfect_cadence / (1.0 + drift_ratio); |
| const double maximum_acceptable_cadence = |
| perfect_cadence / (1.0 - drift_ratio); |
| |
| // We've arbitrarily chosen the maximum allowable cadence length as 5. It's |
| // proven sufficient to support most standard frame and render rates, while |
| // being small enough that small frame and render timing errors don't render |
| // it useless. |
| const int kMaxCadenceSize = 5; |
| |
| double best_error = 0; |
| int best_n = 0; |
| int best_k = 0; |
| for (int n = 1; n <= kMaxCadenceSize; ++n) { |
| // A cadence pattern only exists if there exists an integer K such that K/N |
| // is between |minimum_acceptable_cadence| and |maximum_acceptable_cadence|. |
| // The best pattern is the one with the smallest error over time relative to |
| // the |perfect_cadence|. |
| if (std::floor(minimum_acceptable_cadence * n) < |
| std::floor(maximum_acceptable_cadence * n)) { |
| const int k = round(perfect_cadence * n); |
| |
| const double error = std::fabs(1.0 - perfect_cadence * n / k); |
| |
| // Prefer the shorter cadence pattern unless a longer one "significantly" |
| // reduces the error. |
| if (!best_n || error < best_error * 0.99) { |
| best_error = error; |
| best_k = k; |
| best_n = n; |
| } |
| } |
| } |
| |
| if (!best_n) return Cadence(); |
| |
| // If we've found a solution. |
| Cadence best_result = ConstructCadence(best_k, best_n); |
| *time_until_max_drift = max_acceptable_drift / best_error; |
| |
| return best_result; |
| } |
| |
| std::string VideoCadenceEstimator::CadenceToString( |
| const Cadence& cadence) const { |
| if (cadence.empty()) |
| return std::string("[]"); |
| |
| std::ostringstream os; |
| os << "["; |
| std::copy(cadence.begin(), cadence.end() - 1, |
| std::ostream_iterator<int>(os, ":")); |
| os << cadence.back() << "]"; |
| return os.str(); |
| } |
| |
| double VideoCadenceEstimator::avg_cadence_for_testing() const { |
| if (!has_cadence()) |
| return 0.0; |
| if (bm_.use_bresenham_cadence_) |
| return bm_.perfect_cadence_.value(); |
| |
| int sum = std::accumulate(begin(cadence_), end(cadence_), 0); |
| return static_cast<double>(sum) / cadence_.size(); |
| } |
| |
| } // namespace media |