Cadence Estimator Enhancement

Support up to 5-frame Cadence estimate.

Review URL: https://codereview.chromium.org/1293273003

Cr-Commit-Position: refs/heads/master@{#347450}

4 files changed, 168 insertions, 216 deletions

diff --git a/media/filters/video_cadence_estimator.cc b/media/filters/video_cadence_estimator.cc
index bad4fd0..fbbe836 100644
--- a/media/filters/video_cadence_estimator.cc
+++ b/media/filters/video_cadence_estimator.cc
@@ -5,6 +5,7 @@
 #include "media/filters/video_cadence_estimator.h"
 
 #include <algorithm>
+#include <cmath>
 #include <iterator>
 #include <limits>
 #include <string>
@@ -25,6 +26,42 @@ static void HistogramCadenceChangeCount(int cadence_changes) {
                               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_(
@@ -116,109 +153,58 @@ VideoCadenceEstimator::Cadence VideoCadenceEstimator::CalculateCadence(
     base::TimeDelta frame_duration,
     base::TimeDelta max_acceptable_drift,
     base::TimeDelta* time_until_max_drift) const {
-  // See if we can find a cadence which fits the data.
-  Cadence result;
-  if (CalculateOneFrameCadence(render_interval, frame_duration,
-                               max_acceptable_drift, &result,
-                               time_until_max_drift)) {
-    DCHECK_EQ(1u, result.size());
-  } else if (CalculateFractionalCadence(render_interval, frame_duration,
-                                        max_acceptable_drift, &result,
-                                        time_until_max_drift)) {
-    DCHECK(!result.empty());
-  } else if (CalculateOneFrameCadence(render_interval, frame_duration * 2,
-                                      max_acceptable_drift, &result,
-                                      time_until_max_drift)) {
-    // By finding cadence for double the frame duration, we're saying there
-    // exist two integers a and b, where a > b and a + b = |result|; this
-    // matches all patterns which regularly have half a frame per render
-    // interval; i.e. 24fps in 60hz.
-    DCHECK_EQ(1u, result.size());
-
-    // While we may find a two pattern cadence, sometimes one extra frame
-    // duration is enough to allow a match for 1-frame cadence if the
-    // |time_until_max_drift| was on the edge.
-    //
-    // All 2-frame cadence values should be odd, so we can detect this and fall
-    // back to 1-frame cadence when this occurs.
-    if (result[0] & 1) {
-      result[0] = std::ceil(result[0] / 2.0);
-      result.push_back(result[0] - 1);
-    } else {
-      result[0] /= 2;
-    }
-  }
-  return result;
-}
+  DCHECK_LT(max_acceptable_drift, minimum_time_until_max_drift_);
 
-bool VideoCadenceEstimator::CalculateOneFrameCadence(
-    base::TimeDelta render_interval,
-    base::TimeDelta frame_duration,
-    base::TimeDelta max_acceptable_drift,
-    Cadence* cadence,
-    base::TimeDelta* time_until_max_drift) const {
-  DCHECK(cadence->empty());
-
-  // The perfect cadence is the number of render intervals per frame, while the
-  // clamped cadence is the nearest matching integer value.
-  //
-  // As mentioned in the introduction, |perfect_cadence| is the ratio of the
-  // frame duration to render interval length; while |clamped_cadence| is the
-  // nearest integer value to |perfect_cadence|.
+  // The perfect cadence is the number of render intervals per frame.
   const double perfect_cadence =
       frame_duration.InSecondsF() / render_interval.InSecondsF();
-  const int clamped_cadence = perfect_cadence + 0.5;
-  if (!clamped_cadence)
-    return false;
 
-  // For cadence based rendering the actual frame duration is just the frame
-  // duration, while the |rendered_frame_duration| is how long the frame would
-  // be displayed for if we rendered it |clamped_cadence| times.
-  const base::TimeDelta rendered_frame_duration =
-      clamped_cadence * render_interval;
-  if (!IsAcceptableCadence(rendered_frame_duration, frame_duration,
-                           max_acceptable_drift, time_until_max_drift)) {
-    return false;
+  // 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.InSecondsF() /
+                             minimum_time_until_max_drift_.InSecondsF();
+  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;
+      }
+    }
   }
 
-  cadence->push_back(clamped_cadence);
-  return true;
-}
-
-bool VideoCadenceEstimator::CalculateFractionalCadence(
-    base::TimeDelta render_interval,
-    base::TimeDelta frame_duration,
-    base::TimeDelta max_acceptable_drift,
-    Cadence* cadence,
-    base::TimeDelta* time_until_max_drift) const {
-  DCHECK(cadence->empty());
-
-  // Fractional cadence allows us to see if we have a cadence which would look
-  // best if we consistently drop the same frames.
-  //
-  // In this case, the perfect cadence is the number of frames per render
-  // interval, while the clamped cadence is the nearest integer value.
-  const double perfect_cadence =
-      render_interval.InSecondsF() / frame_duration.InSecondsF();
-  const int clamped_cadence = perfect_cadence + 0.5;
-  if (!clamped_cadence)
-    return false;
+  if (!best_n) return Cadence();
 
-  // For fractional cadence, the rendered duration of each frame is just the
-  // render interval.  While the actual frame duration is the total duration of
-  // all the frames we would end up dropping during that time.
-  const base::TimeDelta actual_frame_duration =
-      clamped_cadence * frame_duration;
-  if (!IsAcceptableCadence(render_interval, actual_frame_duration,
-                           max_acceptable_drift, time_until_max_drift)) {
-    return false;
-  }
+  // If we've found a solution.
+  Cadence best_result = ConstructCadence(best_k, best_n);
+  *time_until_max_drift = max_acceptable_drift / best_error;
 
-  // Fractional cadence means we render the first of |clamped_cadence| frames
-  // and drop |clamped_cadence| - 1 frames.
-  cadence->insert(cadence->begin(), clamped_cadence, 0);
-  (*cadence)[0] = 1;
-  return true;
+  return best_result;
 }
 
 std::string VideoCadenceEstimator::CadenceToString(
@@ -234,28 +220,4 @@ std::string VideoCadenceEstimator::CadenceToString(
   return os.str();
 }
 
-bool VideoCadenceEstimator::IsAcceptableCadence(
-    base::TimeDelta rendered_frame_duration,
-    base::TimeDelta actual_frame_duration,
-    base::TimeDelta max_acceptable_drift,
-    base::TimeDelta* time_until_max_drift) const {
-  if (rendered_frame_duration == actual_frame_duration)
-    return true;
-
-  // Compute how long it'll take to exhaust the drift if frames are rendered for
-  // |rendered_frame_duration| instead of |actual_frame_duration|.
-  const double duration_delta =
-      (rendered_frame_duration - actual_frame_duration)
-          .magnitude()
-          .InMicroseconds();
-  const int64 frames_until_drift_exhausted =
-      std::ceil(max_acceptable_drift.InMicroseconds() / duration_delta);
-
-  // If the time until a frame would be repeated or dropped is greater than our
-  // limit of acceptability, the cadence is acceptable.
-  *time_until_max_drift =
-      rendered_frame_duration * frames_until_drift_exhausted;
-  return *time_until_max_drift >= minimum_time_until_max_drift_;
-}
-
 }  // namespace media
diff --git a/media/filters/video_cadence_estimator.h b/media/filters/video_cadence_estimator.h
index 89b2436..b1a79e6 100644
--- a/media/filters/video_cadence_estimator.h
+++ b/media/filters/video_cadence_estimator.h
@@ -17,8 +17,8 @@ namespace media {
 // durations over time.
 //
 // Cadence is the ideal repeating frame pattern for a group of frames; currently
-// VideoCadenceEstimator supports 1-frame ([N]), 2-frame ([3:2]), and N-frame
-// fractional ([1:0:...:0]) cadences.  Details on what this means are below.
+// VideoCadenceEstimator supports N-frame ([a1:a2:..:aN]) cadences where N <= 5.
+// Details on what this means are below.
 //
 // The perfect cadence of a set of frames is the ratio of the frame duration to
 // render interval length.  I.e. for 30fps in 60Hz the cadence would be (1/30) /
@@ -38,37 +38,33 @@ namespace media {
 // shortening or lengthening the actual rendered frame duration.  Doing so
 // ensures each frame gets an optimal amount of display time.
 //
+// For N-frame cadence, the idea is similar, we just round the perfect cadence
+// to some K/N, where K is an integer, and distribute [floor(K/N), floor(K/N)+1]
+// into the cadence vector as evenly as possible.  For example, 23.97fps in
+// 60Hz, the perfect cadence is 2.50313, we can round it to 2.5 = 5/2, and we
+// can then construct the cadence vector as [2:3].
+//
 // The delta between the perfect cadence and the rounded cadence leads to drift
 // over time of the actual VideoFrame timestamp relative to its rendered time,
 // so we perform some calculations to ensure we only use a cadence when it will
 // take some time to drift an undesirable amount; see CalculateCadence() for
 // details on how this calculation is made.
 //
-// 2-frame cadence is an extension of 1-frame cadence.  Consider the case of
-// 24fps in 60Hz, which has a perfect cadence of 2.5; rounding up to a cadence
-// of 3 would cause drift to accumulate unusably fast.  A better approximation
-// of this cadence would be [3:2].
-//
-// Fractional cadence is a special case of N-frame cadence which can be used
-// when the frame duration is shorter than the render interval; e.g. 120fps in
-// 60Hz.  In this case, the first frame in each group of N frames is displayed
-// once, while the next N - 1 frames are dropped; i.e. the cadence is of the
-// form [1:0:..:0].  Using the previous example N = 120/60 = 2, which means the
-// cadence would be [1:0].  See CalculateFractionalCadence() for more details.
-//
 // In practice this works out to the following for common setups if we use
 // cadence based selection:
 //
 //    29.5fps in 60Hz,    ~17ms max drift => exhausted in ~1 second.
 //    29.9fps in 60Hz,    ~17ms max drift => exhausted in ~16.4 seconds.
-//    24fps   in 60Hz,    ~21ms max drift => exhausted in ~0.15 seconds.
-//    25fps   in 60Hz,     20ms max drift => exhausted in ~4.0 seconds.
-//    59.9fps in 60Hz,   ~8.3ms max drift => exhausted in ~8.2 seconds.
+//    24fps   in 59.9Hz,  ~21ms max drift => exhausted in ~12.6 seconds.
+//    24.9fps in 60Hz,    ~20ms max drift => exhausted in ~4.0 seconds.
+//    59.9fps in 60Hz,    ~8.3ms max drift => exhausted in ~8.2 seconds.
 //    24.9fps in 50Hz,    ~20ms max drift => exhausted in ~20.5 seconds.
-//    120fps  in 59.9Hz, ~8.3ms max drift => exhausted in ~8.2 seconds.
+//    120fps  in 59.9Hz,  ~8.3ms max drift => exhausted in ~8.2 seconds.
 //
 class MEDIA_EXPORT VideoCadenceEstimator {
  public:
+  using Cadence = std::vector<int>;
+
   // As mentioned in the introduction, the determination of whether to clamp to
   // a given cadence is based on how long it takes before a frame would have to
   // be dropped or repeated to compensate for reaching the maximum acceptable
@@ -116,54 +112,20 @@ class MEDIA_EXPORT VideoCadenceEstimator {
   std::string GetCadenceForTesting() const { return CadenceToString(cadence_); }
 
  private:
-  using Cadence = std::vector<int>;
-
-  // Attempts to find a 1-frame, 2-frame, or N-frame fractional cadence; returns
-  // the cadence vector if cadence is found and sets |time_until_max_drift| for
-  // the computed cadence.
+  // Attempts to find an N-frame cadence.  Returns the cadence vector if cadence
+  // is found and sets |time_until_max_drift| for the computed cadence. If
+  // multiple cadences satisfying the max drift constraint exist, we are going
+  // to return the one with largest |time_until_max_drift|.
+  // For details on the math and algorithm, see https://goo.gl/QK0vbz
   Cadence CalculateCadence(base::TimeDelta render_interval,
                            base::TimeDelta frame_duration,
                            base::TimeDelta max_acceptable_drift,
                            base::TimeDelta* time_until_max_drift) const;
 
-  // Calculates the clamped cadence for the given |render_interval| and
-  // |frame_duration|, then calculates how long that cadence can be used before
-  // exhausting |max_acceptable_drift|.  If the time until exhaustion is greater
-  // than |minimum_time_until_max_drift_|, returns true and sets |cadence| to
-  // the clamped cadence.  If the clamped cadence is unusable, |cadence| will be
-  // set to zero.
-  //
-  // Sets |time_until_max_drift| to the computed glitch time.  Set to zero if
-  // the clamped cadence is unusable.
-  bool CalculateOneFrameCadence(base::TimeDelta render_interval,
-                                base::TimeDelta frame_duration,
-                                base::TimeDelta max_acceptable_drift,
-                                Cadence* cadence,
-                                base::TimeDelta* time_until_max_drift) const;
-
-  // Similar to CalculateCadence() except it tries to find the ideal number of
-  // frames which can fit into a |render_interval|; which means doing the same
-  // calculations as CalculateCadence() but with the ratio of |render_interval|
-  // to |frame_duration| instead of the other way around.
-  bool CalculateFractionalCadence(base::TimeDelta render_interval,
-                                  base::TimeDelta frame_duration,
-                                  base::TimeDelta max_acceptable_drift,
-                                  Cadence* cadence,
-                                  base::TimeDelta* time_until_max_drift) const;
-
   // Converts a cadence vector into a human readable string of the form
-  // "[a, b, ..., z]".
+  // "[a: b: ...: z]".
   std::string CadenceToString(const Cadence& cadence) const;
 
-  // Returns true if the drift of the rendered frame duration versus its actual
-  // frame duration take longer than |minimum_time_until_max_drift_| to exhaust
-  // |max_acceptable_drift|.  |time_until_max_drift| is set to how long it will
-  // take before a glitch (frame drop or repeat occurs).
-  bool IsAcceptableCadence(base::TimeDelta rendered_frame_duration,
-                           base::TimeDelta actual_frame_duration,
-                           base::TimeDelta max_acceptable_drift,
-                           base::TimeDelta* time_until_max_drift) const;
-
   // The approximate best N-frame cadence for all frames seen thus far; updated
   // by UpdateCadenceEstimate().  Empty when no cadence has been detected.
   Cadence cadence_;
diff --git a/media/filters/video_cadence_estimator_unittest.cc b/media/filters/video_cadence_estimator_unittest.cc
index 845bb3a..a5e498c 100644
--- a/media/filters/video_cadence_estimator_unittest.cc
+++ b/media/filters/video_cadence_estimator_unittest.cc
@@ -51,16 +51,20 @@ static void VerifyCadenceVector(VideoCadenceEstimator* estimator,
       CreateCadenceFromString(expected_cadence);
 
   estimator->Reset();
-  const base::TimeDelta acceptable_drift = Interval(frame_hertz) / 2;
+  const base::TimeDelta acceptable_drift = std::max(Interval(frame_hertz) / 2,
+                                                    Interval(render_hertz));
   const bool cadence_changed = estimator->UpdateCadenceEstimate(
       Interval(render_hertz), Interval(frame_hertz), acceptable_drift);
   EXPECT_EQ(cadence_changed, estimator->has_cadence());
   EXPECT_EQ(expected_cadence_vector.empty(), !estimator->has_cadence());
 
   // Nothing further to test.
-  if (expected_cadence_vector.empty())
+  if (expected_cadence_vector.empty() || !estimator->has_cadence())
     return;
 
+  EXPECT_EQ(expected_cadence_vector.size(),
+            estimator->cadence_size_for_testing());
+
   // Spot two cycles of the cadence.
   for (size_t i = 0; i < expected_cadence_vector.size() * 2; ++i) {
     ASSERT_EQ(expected_cadence_vector[i % expected_cadence_vector.size()],
@@ -75,30 +79,50 @@ TEST(VideoCadenceEstimatorTest, CadenceCalculations) {
   estimator.set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
 
   const std::string kEmptyCadence = "[]";
+  VerifyCadenceVector(&estimator, 1, NTSC(60), "[60]");
+
   VerifyCadenceVector(&estimator, 24, 60, "[3:2]");
   VerifyCadenceVector(&estimator, NTSC(24), 60, "[3:2]");
+  VerifyCadenceVector(&estimator, 24, NTSC(60), "[3:2]");
+
+  VerifyCadenceVector(&estimator, 25, 60, "[2:3:2:3:2]");
+  VerifyCadenceVector(&estimator, NTSC(25), 60, "[2:3:2:3:2]");
+  VerifyCadenceVector(&estimator, 25, NTSC(60), "[2:3:2:3:2]");
 
-  VerifyCadenceVector(&estimator, 25, 60, kEmptyCadence);
-  VerifyCadenceVector(&estimator, NTSC(30), 60, "[2]");
   VerifyCadenceVector(&estimator, 30, 60, "[2]");
-  VerifyCadenceVector(&estimator, 50, 60, kEmptyCadence);
+  VerifyCadenceVector(&estimator, NTSC(30), 60, "[2]");
+  VerifyCadenceVector(&estimator, 29.5, 60, kEmptyCadence);
+
+  VerifyCadenceVector(&estimator, 50, 60, "[1:1:2:1:1]");
+  VerifyCadenceVector(&estimator, NTSC(50), 60, "[1:1:2:1:1]");
+  VerifyCadenceVector(&estimator, 50, NTSC(60), "[1:1:2:1:1]");
+
   VerifyCadenceVector(&estimator, NTSC(60), 60, "[1]");
+  VerifyCadenceVector(&estimator, 60, NTSC(60), "[1]");
+
   VerifyCadenceVector(&estimator, 120, 60, "[1:0]");
+  VerifyCadenceVector(&estimator, NTSC(120), 60, "[1:0]");
+  VerifyCadenceVector(&estimator, 120, NTSC(60), "[1:0]");
+
+  // Test cases for cadence below 1.
   VerifyCadenceVector(&estimator, 120, 24, "[1:0:0:0:0]");
+  VerifyCadenceVector(&estimator, 120, 48, "[1:0:0:1:0]");
+  VerifyCadenceVector(&estimator, 120, 72, "[1:0:1:0:1]");
+  VerifyCadenceVector(&estimator, 90, 60, "[1:0:1]");
 
   // 50Hz is common in the EU.
   VerifyCadenceVector(&estimator, NTSC(24), 50, kEmptyCadence);
   VerifyCadenceVector(&estimator, 24, 50, kEmptyCadence);
+
   VerifyCadenceVector(&estimator, NTSC(25), 50, "[2]");
   VerifyCadenceVector(&estimator, 25, 50, "[2]");
-  VerifyCadenceVector(&estimator, NTSC(30), 50, kEmptyCadence);
-  VerifyCadenceVector(&estimator, 30, 50, kEmptyCadence);
+
+  VerifyCadenceVector(&estimator, NTSC(30), 50, "[2:1:2]");
+  VerifyCadenceVector(&estimator, 30, 50, "[2:1:2]");
+
   VerifyCadenceVector(&estimator, NTSC(60), 50, kEmptyCadence);
   VerifyCadenceVector(&estimator, 60, 50, kEmptyCadence);
 
-  VerifyCadenceVector(&estimator, 25, NTSC(60), kEmptyCadence);
-  VerifyCadenceVector(&estimator, 120, NTSC(60), kEmptyCadence);
-  VerifyCadenceVector(&estimator, 1, NTSC(60), "[60]");
 }
 
 TEST(VideoCadenceEstimatorTest, CadenceVariesWithAcceptableDrift) {
@@ -187,18 +211,4 @@ TEST(VideoCadenceEstimatorTest, CadenceHystersisPreventsOscillation) {
   EXPECT_FALSE(estimator->has_cadence());
 }
 
-TEST(VideoCadenceEstimatorTest, TwoFrameCadenceIsActuallyOneFrame) {
-  VideoCadenceEstimator estimator(
-      base::TimeDelta::FromSeconds(kMinimumAcceptableTimeBetweenGlitchesSecs));
-  estimator.set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
-
-  const base::TimeDelta render_interval =
-      base::TimeDelta::FromMicroseconds(16715);
-  const base::TimeDelta frame_duration =
-      base::TimeDelta::FromMicroseconds(33360);
-
-  EXPECT_TRUE(estimator.UpdateCadenceEstimate(render_interval, frame_duration,
-                                              frame_duration / 2));
-}
-
 }  // namespace media
diff --git a/media/filters/video_renderer_algorithm_unittest.cc b/media/filters/video_renderer_algorithm_unittest.cc
index 0df3f4e..ba29b4f 100644
--- a/media/filters/video_renderer_algorithm_unittest.cc
+++ b/media/filters/video_renderer_algorithm_unittest.cc
@@ -102,9 +102,28 @@ class VideoRendererAlgorithmTest : public testing::Test {
     return algorithm_.cadence_estimator_.has_cadence();
   }
 
-  bool IsUsingFractionalCadence() const {
-    return is_using_cadence() &&
-           !algorithm_.cadence_estimator_.GetCadenceForFrame(1);
+  bool IsCadenceBelowOne() const {
+    if (!is_using_cadence())
+      return false;
+
+    size_t size = algorithm_.cadence_estimator_.cadence_size_for_testing();
+    for (size_t i = 0; i < size; ++i) {
+      if (!algorithm_.cadence_estimator_.GetCadenceForFrame(i))
+        return true;
+    }
+
+    return false;
+  }
+
+  double CadenceValue() const {
+    int num_render_intervals = 0;
+    size_t size = algorithm_.cadence_estimator_.cadence_size_for_testing();
+    for (size_t i = 0; i < size; ++i) {
+      num_render_intervals +=
+          algorithm_.cadence_estimator_.GetCadenceForFrame(i);
+    }
+
+    return (num_render_intervals + 0.0) / size;
   }
 
   size_t frames_queued() const { return algorithm_.frame_queue_.size(); }
@@ -222,16 +241,15 @@ class VideoRendererAlgorithmTest : public testing::Test {
         ASSERT_NEAR(GetUsableFrameCount(deadline_max),
                     algorithm_.EffectiveFramesQueued(),
                     fresh_algorithm ? 0 : 1);
-      } else if (is_using_cadence() && !IsUsingFractionalCadence()) {
+      } else if (is_using_cadence() && !IsCadenceBelowOne()) {
         // If there was no glitch in the last render, the two queue sizes should
         // be off by exactly one frame; i.e., the current frame doesn't count.
         if (!last_render_had_glitch() && fresh_algorithm)
           ASSERT_EQ(frames_queued() - 1, algorithm_.EffectiveFramesQueued());
-      } else if (IsUsingFractionalCadence()) {
+      } else if (IsCadenceBelowOne()) {
         // The frame estimate should be off by at most one frame.
         const size_t estimated_frames_queued =
-            frames_queued() /
-            algorithm_.cadence_estimator_.cadence_size_for_testing();
+            std::floor(frames_queued() * CadenceValue());
         ASSERT_NEAR(algorithm_.EffectiveFramesQueued(), estimated_frames_queued,
                     1);
       }
@@ -1013,10 +1031,10 @@ TEST_F(VideoRendererAlgorithmTest, FilmCadence) {
 TEST_F(VideoRendererAlgorithmTest, CadenceCalculations) {
   ASSERT_EQ("[3:2]", GetCadence(24, 60));
   ASSERT_EQ("[3:2]", GetCadence(NTSC(24), 60));
-  ASSERT_EQ("[]", GetCadence(25, 60));
+  ASSERT_EQ("[2:3:2:3:2]", GetCadence(25, 60));
   ASSERT_EQ("[2]", GetCadence(NTSC(30), 60));
   ASSERT_EQ("[2]", GetCadence(30, 60));
-  ASSERT_EQ("[]", GetCadence(50, 60));
+  ASSERT_EQ("[1:1:2:1:1]", GetCadence(50, 60));
   ASSERT_EQ("[1]", GetCadence(NTSC(60), 60));
   ASSERT_EQ("[1:0]", GetCadence(120, 60));
 
@@ -1025,12 +1043,12 @@ TEST_F(VideoRendererAlgorithmTest, CadenceCalculations) {
   ASSERT_EQ("[]", GetCadence(24, 50));
   ASSERT_EQ("[2]", GetCadence(NTSC(25), 50));
   ASSERT_EQ("[2]", GetCadence(25, 50));
-  ASSERT_EQ("[]", GetCadence(NTSC(30), 50));
-  ASSERT_EQ("[]", GetCadence(30, 50));
+  ASSERT_EQ("[2:1:2]", GetCadence(NTSC(30), 50));
+  ASSERT_EQ("[2:1:2]", GetCadence(30, 50));
   ASSERT_EQ("[]", GetCadence(NTSC(60), 50));
   ASSERT_EQ("[]", GetCadence(60, 50));
 
-  ASSERT_EQ("[]", GetCadence(25, NTSC(60)));
+  ASSERT_EQ("[2:3:2:3:2]", GetCadence(25, NTSC(60)));
   ASSERT_EQ("[1:0]", GetCadence(120, NTSC(60)));
   ASSERT_EQ("[60]", GetCadence(1, NTSC(60)));
 }
@@ -1162,9 +1180,9 @@ TEST_F(VideoRendererAlgorithmTest, VariableFrameRateCadence) {
   TickGenerator frame_tg(base::TimeTicks(), NTSC(30));
   TickGenerator display_tg(tick_clock_->NowTicks(), 60);
 
-  const double kTestRates[] = {1.0, 2, 0.215, 0.5, 1.0};
-  const bool kTestRateHasCadence[arraysize(kTestRates)] = {
-      true, true, false, true, true};
+  const double kTestRates[] = {1.0, 2, 0.215, 0.5, 1.0, 3.15};
+  const bool kTestRateHasCadence[arraysize(kTestRates)] = {true, true, true,
+                                                           true, true, false};
 
   for (size_t i = 0; i < arraysize(kTestRates); ++i) {
     const double playback_rate = kTestRates[i];