Introduce cadence based VideoRendererAlgorithm.

media/filters/video_renderer_algorithm_unittest.cc

Index: media/filters/video_renderer_algorithm_unittest.cc
diff --git a/media/filters/video_renderer_algorithm_unittest.cc b/media/filters/video_renderer_algorithm_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..8fd7fbb9d8d6e6515163ec6cf113d6838b3e1a96
--- /dev/null
+++ b/media/filters/video_renderer_algorithm_unittest.cc
@@ -0,0 +1,662 @@
+// 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 <cmath>
+
+#include "base/bind.h"
+#include "base/bind_helpers.h"
+#include "base/strings/stringprintf.h"
+#include "base/test/simple_test_tick_clock.h"
+#include "media/base/video_frame_pool.h"
+#include "media/base/wall_clock_time_source.h"
+#include "media/filters/video_renderer_algorithm.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace media {
+
+// Slows down the given |fps| according to NTSC field reduction standards; see
+// http://en.wikipedia.org/wiki/Frame_rate#Digital_video_and_television
+#define NTSC(fps) fps / 1.001
+
+// Helper class for generating TimeTicks in a sequence according to a frequency.
+class TickGenerator {
+ public:
+  TickGenerator(base::TimeTicks base_timestamp, double hertz)
+      : tick_count_(0),
+        hertz_(hertz),
+        microseconds_per_tick_(base::Time::kMicrosecondsPerSecond / hertz),
+        base_time_(base_timestamp) {}
+
+  base::TimeDelta interval(int tick_count) {
+    return base::TimeDelta::FromMicroseconds(tick_count *
+                                             microseconds_per_tick_);
+  }
+
+  base::TimeTicks current() { return base_time_ + interval(tick_count_); }
+  base::TimeTicks step() { return step(1); }
+  base::TimeTicks step(int n) {
+    tick_count_ += n;
+    return current();
+  }
+
+  double hertz() const { return hertz_; }
+
+  void Reset(base::TimeTicks base_timestamp) {
+    base_time_ = base_timestamp;
+    tick_count_ = 0;
+  }
+
+ private:
+  // Track a tick count and seconds per tick value to ensure we don't drift too
+  // far due to accumulated errors during testing.
+  int64_t tick_count_;
+  double hertz_;
+  double microseconds_per_tick_;
+  base::TimeTicks base_time_;
+
+  DISALLOW_COPY_AND_ASSIGN(TickGenerator);
+};
+
+class VideoRendererAlgorithmTest : public testing::Test {
+ public:
+  VideoRendererAlgorithmTest()
+      : tick_clock_(new base::SimpleTestTickClock()),
+        algorithm_(base::Bind(&WallClockTimeSource::GetWallClockTime,
+                              base::Unretained(&time_source_))) {
+    // Always start the TickClock at a non-zero value since null values have
+    // special connotations.
+    tick_clock_->Advance(base::TimeDelta::FromMicroseconds(10000));
+    time_source_.SetTickClockForTesting(
+        scoped_ptr<base::TickClock>(tick_clock_));
+  }
+  ~VideoRendererAlgorithmTest() override {}
+
+  scoped_refptr<VideoFrame> CreateFrame(base::TimeDelta timestamp) {
+    const gfx::Size natural_size(8, 8);
+    return frame_pool_.CreateFrame(VideoFrame::YV12, natural_size,
+                                   gfx::Rect(natural_size), natural_size,
+                                   timestamp);
+  }
+
+  base::TimeDelta minimum_glitch_time() const {
+    return base::TimeDelta::FromSeconds(
+        VideoRendererAlgorithm::kMinimumAcceptableTimeBetweenGlitchesSecs);
+  }
+
+  base::TimeDelta max_acceptable_drift() const {
+    return algorithm_.max_acceptable_drift_;
+  }
+
+  void disable_cadence_hysteresis() {
+    algorithm_.cadence_hysteresis_enabled_ = false;
+  }
+
+  bool last_render_had_glitch() const {
+    return algorithm_.last_render_had_glitch_;
+  }
+
+  bool is_using_cadence() const { return algorithm_.ideal_cadence_ > 0; }
+
+  size_t frames_queued() const { return algorithm_.frame_queue_.size(); }
+
+  int GetCadence(double frame_rate, double display_rate) {
+    TickGenerator display_tg(tick_clock_->NowTicks(), display_rate);
+    TickGenerator frame_tg(base::TimeTicks(), frame_rate);
+    time_source_.StartTicking();
+
+    // Enqueue enough frames for cadence detection.
+    int frames_dropped = 0;
+    disable_cadence_hysteresis();
+    algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(0)));
+    algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(1)));
+    EXPECT_TRUE(algorithm_.Render(display_tg.current(), display_tg.step(),
+                                  &frames_dropped));
+
+    // Store cadence before reseting the algorithm.
+    const int cadence = algorithm_.fractional_cadence_
+                            ? algorithm_.fractional_cadence_
+                            : algorithm_.ideal_cadence_;
+
+    time_source_.StopTicking();
+    algorithm_.Reset();
+    return cadence;
+  }
+
+  bool DriftOfLastRenderWasWithinTolerance(base::TimeTicks deadline_min) {
+    return algorithm_.CalculateDriftForFrame(deadline_min, 0) <=
+           algorithm_.max_acceptable_drift_;
+  }
+
+  // Allows tests to run a Render() loop with sufficient frames for the various
+  // rendering modes. Upon each Render() |render_test_func| will be called with
+  // the rendered frame and the number of frames dropped.
+  template <typename OnRenderCallback>
+  void RunFramePumpTest(bool reset,
+                        TickGenerator* frame_tg,
+                        TickGenerator* display_tg,
+                        OnRenderCallback render_test_func) {
+    SCOPED_TRACE(base::StringPrintf("Rendering %.03f fps into %0.03f",
+                                    frame_tg->hertz(), display_tg->hertz()));
+    tick_clock_->Advance(display_tg->current() - tick_clock_->NowTicks());
+    time_source_.StartTicking();
+
+    const bool fresh_algorithm = !algorithm_.have_rendered_frames_;
+
+    base::TimeDelta last_frame_timestamp = kNoTimestamp();
+    bool should_use_cadence = false;
+    int glitch_count = 0;
+    const base::TimeTicks start_time = tick_clock_->NowTicks();
+    while (tick_clock_->NowTicks() - start_time < minimum_glitch_time()) {
+      while (algorithm_.EffectiveFramesQueued() < 3 ||
+             frame_tg->current() - time_source_.CurrentMediaTime() <
+                 base::TimeTicks()) {
+        algorithm_.EnqueueFrame(
+            CreateFrame(frame_tg->current() - base::TimeTicks()));
+        frame_tg->step();
+      }
+
+      int frames_dropped = 0;
+      const base::TimeTicks deadline_min = display_tg->current();
+      const base::TimeTicks deadline_max = display_tg->step();
+      scoped_refptr<VideoFrame> frame =
+          algorithm_.Render(deadline_min, deadline_max, &frames_dropped);
+
+      render_test_func(frame, frames_dropped);
+      tick_clock_->Advance(display_tg->current() - tick_clock_->NowTicks());
+
+      if (HasFatalFailure())
+        return;
+
+      // Render() should always return a frame within drift tolerances.
+      ASSERT_TRUE(DriftOfLastRenderWasWithinTolerance(deadline_min));
+
+      // If we have a frame, the timestamps should always be monotonically
+      // increasing.
+      if (frame) {
+        if (last_frame_timestamp != kNoTimestamp())
+          ASSERT_LE(last_frame_timestamp, frame->timestamp());
+        else
+          last_frame_timestamp = frame->timestamp();
+      }
+
+      // Only verify certain properties for fresh instances.
+      if (fresh_algorithm) {
+        ASSERT_EQ(frame_tg->interval(1), algorithm_.average_frame_duration());
+
+        if (is_using_cadence() && last_render_had_glitch())
+          ++glitch_count;
+
+        // Once cadence starts, it should never stop for the current set of
+        // tests.
+        if (is_using_cadence())
+          should_use_cadence = true;
+        ASSERT_EQ(is_using_cadence(), should_use_cadence);
+      }
+    }
+
+    // When using cadence, the glitch count should be at most one for when
+    // rendering for the less than minimum_glitch_time().
+    if (fresh_algorithm && is_using_cadence())
+      ASSERT_LE(glitch_count, 1);
+
+    time_source_.StopTicking();
+    if (reset) {
+      algorithm_.Reset();
+      time_source_.SetMediaTime(base::TimeDelta());
+    }
+  }
+
+  int FindBestFrameByCoverage(base::TimeTicks deadline_min,
+                              base::TimeTicks deadline_max,
+                              int* second_best) {
+    return algorithm_.FindBestFrameByCoverage(deadline_min, deadline_max,
+                                              second_best);
+  }
+
+  int FindBestFrameByDrift(base::TimeTicks deadline_min) {
+    return algorithm_.FindBestFrameByDrift(deadline_min);
+  }
+
+ protected:
+  VideoFramePool frame_pool_;
+  WallClockTimeSource time_source_;
+  base::SimpleTestTickClock* tick_clock_;  // Owned by |time_source_|.
+  VideoRendererAlgorithm algorithm_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(VideoRendererAlgorithmTest);
+};
+
+TEST_F(VideoRendererAlgorithmTest, Empty) {
+  TickGenerator tg(tick_clock_->NowTicks(), 50);
+  int frames_dropped = 0;
+  EXPECT_EQ(0u, frames_queued());
+  EXPECT_FALSE(algorithm_.Render(tg.current(), tg.step(), &frames_dropped));
+  EXPECT_EQ(0, frames_dropped);
+  EXPECT_EQ(0u, frames_queued());
+  EXPECT_NE(base::TimeDelta(), max_acceptable_drift());
+}
+
+TEST_F(VideoRendererAlgorithmTest, Reset) {
+  TickGenerator tg(tick_clock_->NowTicks(), 50);
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(0)));
+  EXPECT_EQ(1u, frames_queued());
+  EXPECT_NE(base::TimeDelta(), max_acceptable_drift());
+  algorithm_.Reset();
+  EXPECT_EQ(0u, frames_queued());
+  EXPECT_NE(base::TimeDelta(), max_acceptable_drift());
+}
+
+// The maximum acceptable drift should be updated once we have two frames.
+TEST_F(VideoRendererAlgorithmTest, AcceptableDriftUpdated) {
+  TickGenerator tg(tick_clock_->NowTicks(), 50);
+
+  int frames_dropped = 0;
+  const base::TimeDelta original_drift = max_acceptable_drift();
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(0)));
+  EXPECT_EQ(1u, frames_queued());
+  EXPECT_TRUE(algorithm_.Render(tg.current(), tg.step(), &frames_dropped));
+  EXPECT_EQ(original_drift, max_acceptable_drift());
+
+  // Time must be ticking to get wall clock times for frames.
+  time_source_.StartTicking();
+
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(1)));
+  EXPECT_EQ(2u, frames_queued());
+  EXPECT_TRUE(algorithm_.Render(tg.current(), tg.step(), &frames_dropped));
+  EXPECT_NE(original_drift, max_acceptable_drift());
+}
+
+// Verifies behavior when time stops.
+TEST_F(VideoRendererAlgorithmTest, TimeIsStopped) {
+  TickGenerator tg(tick_clock_->NowTicks(), 50);
+
+  // Prior to rendering the first frame, the algorithm should always return the
+  // first available frame.
+  int frames_dropped = 0;
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(0)));
+  EXPECT_EQ(1u, frames_queued());
+  scoped_refptr<VideoFrame> frame =
+      algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(0), frame->timestamp());
+  EXPECT_EQ(0, frames_dropped);
+  EXPECT_EQ(1u, frames_queued());
+
+  // The same timestamp should be returned after time starts.
+  tick_clock_->Advance(tg.interval(1));
+  time_source_.StartTicking();
+  frame = algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(0), frame->timestamp());
+  EXPECT_EQ(0, frames_dropped);
+  EXPECT_EQ(1u, frames_queued());
+
+  // Ensure the next suitable frame is vended as time advances.
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(1)));
+  EXPECT_EQ(2u, frames_queued());
+  frame = algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(1), frame->timestamp());
+  EXPECT_EQ(0, frames_dropped);
+  EXPECT_EQ(1u, frames_queued());
+
+  // Once time stops ticking, any further frames shouldn't be returned, even if
+  // the interval requested more closely matches.
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(2)));
+  time_source_.StopTicking();
+  frame = algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(1), frame->timestamp());
+  EXPECT_EQ(0, frames_dropped);
+  EXPECT_EQ(2u, frames_queued());
+}
+
+// Verify frames inserted out of order end up in the right spot and are rendered
+// according to the API contract.
+TEST_F(VideoRendererAlgorithmTest, SortedFrameQueue) {
+  TickGenerator tg(tick_clock_->NowTicks(), 50);
+
+  // Ensure frames handed in out of order before time starts ticking are sorted
+  // and returned in the correct order upon Render().
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(3)));
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(2)));
+  EXPECT_EQ(2u, frames_queued());
+
+  time_source_.StartTicking();
+
+  // The first call should return the earliest frame appended.
+  int frames_dropped = 0;
+  scoped_refptr<VideoFrame> frame =
+      algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  EXPECT_EQ(0, frames_dropped);
+  EXPECT_EQ(tg.interval(2), frame->timestamp());
+  EXPECT_EQ(2u, frames_queued());
+
+  // Since a frame has already been rendered, enqueing this frame and calling
+  // Render() should result in it being dropped; even though it's a better
+  // candidate for the desired interval.
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(1)));
+  frame = algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  EXPECT_EQ(1, frames_dropped);
+  EXPECT_EQ(tg.interval(2), frame->timestamp());
+  EXPECT_EQ(2u, frames_queued());
+}
+
+// Run through integer cadence selection for 1, 2, 3, and 4.
+TEST_F(VideoRendererAlgorithmTest, BestFrameByCadence) {
+  const double kTestRates[][2] = {{60, 60}, {30, 60}, {25, 75}, {25, 100}};
+
+  for (const auto& test_rate : kTestRates) {
+    disable_cadence_hysteresis();
+
+    TickGenerator frame_tg(base::TimeTicks(), test_rate[0]);
+    TickGenerator display_tg(tick_clock_->NowTicks(), test_rate[1]);
+
+    int actual_frame_pattern = 0;
+    const int desired_frame_pattern = test_rate[1] / test_rate[0];
+    scoped_refptr<VideoFrame> current_frame;
+    RunFramePumpTest(
+        true, &frame_tg, &display_tg,
+        [&current_frame, &actual_frame_pattern, desired_frame_pattern, this](
+            const scoped_refptr<VideoFrame>& frame, int frames_dropped) {
+          ASSERT_TRUE(frame);
+          ASSERT_EQ(0, frames_dropped);
+
+          // Each frame should display for exactly it's desired cadence pattern.
+          if (!current_frame || current_frame == frame) {
+            actual_frame_pattern++;
+          } else {
+            ASSERT_EQ(actual_frame_pattern, desired_frame_pattern);
+            actual_frame_pattern = 1;
+          }
+
+          current_frame = frame;
+          ASSERT_TRUE(is_using_cadence());
+        });
+
+    if (HasFatalFailure())
+      return;
+  }
+}
+
+TEST_F(VideoRendererAlgorithmTest, BestFrameByCoverage) {
+  TickGenerator tg(tick_clock_->NowTicks(), 50);
+  time_source_.StartTicking();
+
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(0)));
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(1)));
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(2)));
+
+  base::TimeTicks deadline_min = tg.current();
+  base::TimeTicks deadline_max = deadline_min + tg.interval(1);
+
+  int frames_dropped = 0;
+  scoped_refptr<VideoFrame> frame =
+      algorithm_.Render(deadline_min, deadline_max, &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(0), frame->timestamp());
+  EXPECT_EQ(0, frames_dropped);
+
+  int second_best = 0;
+
+  // Coverage should be 1 for if the frame overlaps the interval entirely, no
+  // second best should be found.
+  EXPECT_EQ(0,
+            FindBestFrameByCoverage(deadline_min, deadline_max, &second_best));
+  EXPECT_EQ(-1, second_best);
+
+  // 49/51 coverage for frame 0 and frame 1 should be within tolerance such that
+  // the earlier frame should still be chosen.
+  deadline_min = tg.current() + tg.interval(1) / 2 +
+                 base::TimeDelta::FromMicroseconds(250);
+  deadline_max = deadline_min + tg.interval(1);
+  EXPECT_EQ(0,
+            FindBestFrameByCoverage(deadline_min, deadline_max, &second_best));
+  EXPECT_EQ(1, second_best);
+
+  // 48/52 coverage should result in the second frame being chosen.
+  deadline_min = tg.current() + tg.interval(1) / 2 +
+                 base::TimeDelta::FromMicroseconds(500);
+  deadline_max = deadline_min + tg.interval(1);
+  EXPECT_EQ(1,
+            FindBestFrameByCoverage(deadline_min, deadline_max, &second_best));
+  EXPECT_EQ(0, second_best);
+
+  // Overlapping three frames should choose the one with the most coverage and
+  // the second best should be the earliest frame.
+  deadline_min = tg.current() + tg.interval(1) / 2;
+  deadline_max = deadline_min + tg.interval(2);
+  EXPECT_EQ(1,
+            FindBestFrameByCoverage(deadline_min, deadline_max, &second_best));
+  EXPECT_EQ(0, second_best);
+
+  // Requesting coverage outside of all known frames should return -1 for both
+  // best indices.
+  deadline_min = tg.current() + tg.interval(frames_queued());
+  deadline_max = deadline_min + tg.interval(1);
+  EXPECT_EQ(-1,
+            FindBestFrameByCoverage(deadline_min, deadline_max, &second_best));
+  EXPECT_EQ(-1, second_best);
+}
+
+// Run through fractional cadence selection for 1/2, 1/3, and 1/4.
+TEST_F(VideoRendererAlgorithmTest, BestFrameByFractionalCadence) {
+  const double kTestRates[][2] = {{120, 60}, {72, 24}, {100, 25}};
+
+  for (const auto& test_rate : kTestRates) {
+    disable_cadence_hysteresis();
+
+    TickGenerator frame_tg(base::TimeTicks(), test_rate[0]);
+    TickGenerator display_tg(tick_clock_->NowTicks(), test_rate[1]);
+
+    const int desired_drop_pattern = test_rate[0] / test_rate[1] - 1;
+    scoped_refptr<VideoFrame> current_frame;
+    RunFramePumpTest(
+        true, &frame_tg, &display_tg,
+        [&current_frame, desired_drop_pattern, this](
+            const scoped_refptr<VideoFrame>& frame, int frames_dropped) {
+          ASSERT_TRUE(frame);
+
+          // The first frame should have zero dropped frames, but each Render()
+          // call after should drop the same number of frames based on the
+          // fractional cadence.
+          if (!current_frame)
+            ASSERT_EQ(0, frames_dropped);
+          else
+            ASSERT_EQ(desired_drop_pattern, frames_dropped);
+
+          ASSERT_NE(current_frame, frame);
+          ASSERT_TRUE(is_using_cadence());
+          current_frame = frame;
+        });
+
+    if (HasFatalFailure())
+      return;
+  }
+}
+// Verify a 3:2 frame pattern for 23.974fps in 60Hz; doubles as a test for best
+// frame by coverage.
+TEST_F(VideoRendererAlgorithmTest, FilmCadence) {
+  const double kTestRates[] = {NTSC(24), 24};
+
+  for (double frame_rate : kTestRates) {
+    scoped_refptr<VideoFrame> current_frame;
+    int actual_frame_pattern = 0, desired_frame_pattern = 3;
+
+    TickGenerator frame_tg(base::TimeTicks(), frame_rate);
+    TickGenerator display_tg(tick_clock_->NowTicks(), 60);
+
+    RunFramePumpTest(
+        true, &frame_tg, &display_tg,
+        [&current_frame, &actual_frame_pattern, &desired_frame_pattern, this](
+            const scoped_refptr<VideoFrame>& frame, int frames_dropped) {
+          ASSERT_TRUE(frame);
+          ASSERT_EQ(0, frames_dropped);
+
+          if (!current_frame || current_frame == frame) {
+            actual_frame_pattern++;
+          } else {
+            ASSERT_EQ(actual_frame_pattern, desired_frame_pattern);
+            actual_frame_pattern = 1;
+            desired_frame_pattern = (desired_frame_pattern == 3 ? 2 : 3);
+          }
+
+          current_frame = frame;
+          ASSERT_FALSE(is_using_cadence());
+        });
+
+    if (HasFatalFailure())
+      return;
+  }
+}
+
+// Spot check common display and frame rate pairs for correctness.
+TEST_F(VideoRendererAlgorithmTest, CadenceCalculations) {
+  ASSERT_FALSE(GetCadence(24, 60));
+  ASSERT_FALSE(GetCadence(NTSC(24), 60));
+  ASSERT_FALSE(GetCadence(25, 60));
+  ASSERT_EQ(2, GetCadence(NTSC(30), 60));
+  ASSERT_EQ(2, GetCadence(30, 60));
+  ASSERT_FALSE(GetCadence(50, 60));
+  ASSERT_EQ(1, GetCadence(NTSC(60), 60));
+  ASSERT_EQ(2, GetCadence(120, 60));
+
+  // 50Hz is common in the EU.
+  ASSERT_FALSE(GetCadence(NTSC(24), 50));
+  ASSERT_FALSE(GetCadence(24, 50));
+  ASSERT_EQ(2, GetCadence(NTSC(25), 50));
+  ASSERT_EQ(2, GetCadence(25, 50));
+  ASSERT_FALSE(GetCadence(NTSC(30), 50));
+  ASSERT_FALSE(GetCadence(30, 50));
+  ASSERT_FALSE(GetCadence(NTSC(60), 50));
+  ASSERT_FALSE(GetCadence(60, 50));
+
+  ASSERT_FALSE(GetCadence(25, NTSC(60)));
+  ASSERT_EQ(2, GetCadence(120, NTSC(60)));
+  ASSERT_EQ(60, GetCadence(1, NTSC(60)));
+}
+
+TEST_F(VideoRendererAlgorithmTest, RemoveExpiredFrames) {
+  TickGenerator tg(tick_clock_->NowTicks(), 50);
+
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(0)));
+  ASSERT_EQ(0, algorithm_.RemoveExpiredFrames(tg.current()));
+
+  time_source_.StartTicking();
+
+  int frames_dropped = 0;
+  scoped_refptr<VideoFrame> frame =
+      algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(0), frame->timestamp());
+  EXPECT_EQ(0, frames_dropped);
+
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(1)));
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(2)));
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(3)));
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(4)));
+
+  tg.step(2);
+  ASSERT_EQ(2, algorithm_.RemoveExpiredFrames(tg.current()));
+  frame = algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  EXPECT_EQ(1, frames_dropped);
+  EXPECT_EQ(2u, frames_queued());
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(3), frame->timestamp());
+}
+
+TEST_F(VideoRendererAlgorithmTest, CadenceBasedTest) {
+  // Common display rates.
+  const double kDisplayRates[] = {
+      NTSC(24),
+      24,
+      NTSC(25),
+      25,
+      NTSC(30),
+      30,
+      48,
+      NTSC(50),
+      50,
+      NTSC(60),
+      60,
+      75,
+      120,
+      144,
+  };
+
+  // List of common frame rate values. Values pulled from local test media,
+  // videostack test matrix, and Wikipedia.
+  const double kTestRates[] = {
+      1,        10, 12.5,  15,  NTSC(24), 24,  NTSC(25), 25,
+      NTSC(30), 30, 30.12, 48,  NTSC(50), 50,  58.74,    NTSC(60),
+      60,       72, 90,    100, 120,      144, 240,      300,
+  };
+
+  for (double display_rate : kDisplayRates) {
+    for (double frame_rate : kTestRates) {
+      TickGenerator frame_tg(base::TimeTicks(), frame_rate);
+      TickGenerator display_tg(tick_clock_->NowTicks(), display_rate);
+      RunFramePumpTest(
+          true, &frame_tg, &display_tg,
+          [](const scoped_refptr<VideoFrame>& frame, int frames_dropped) {});
+      if (HasFatalFailure())
+        return;
+    }
+  }
+}
+
+// Rotate through various playback rates and ensure algorithm adapts correctly.
+TEST_F(VideoRendererAlgorithmTest, VariableFrameRateCadence) {
+  TickGenerator frame_tg(base::TimeTicks(), NTSC(30));
+  TickGenerator display_tg(tick_clock_->NowTicks(), 60);
+
+  RunFramePumpTest(
+      false, &frame_tg, &display_tg,
+      [this](const scoped_refptr<VideoFrame>& frame, int frames_dropped) {});
+  if (HasFatalFailure())
+    return;
+  ASSERT_TRUE(is_using_cadence());
+
+  time_source_.SetPlaybackRate(2);
+
+  RunFramePumpTest(
+      false, &frame_tg, &display_tg,
+      [this](const scoped_refptr<VideoFrame>& frame, int frames_dropped) {});
+  if (HasFatalFailure())
+    return;
+  ASSERT_TRUE(is_using_cadence());
+
+  time_source_.SetPlaybackRate(0.215);
+
+  RunFramePumpTest(
+      false, &frame_tg, &display_tg,
+      [this](const scoped_refptr<VideoFrame>& frame, int frames_dropped) {});
+  if (HasFatalFailure())
+    return;
+  ASSERT_FALSE(is_using_cadence());
+
+  time_source_.SetPlaybackRate(0.5);
+
+  RunFramePumpTest(
+      false, &frame_tg, &display_tg,
+      [this](const scoped_refptr<VideoFrame>& frame, int frames_dropped) {});
+  if (HasFatalFailure())
+    return;
+  ASSERT_TRUE(is_using_cadence());
+
+  time_source_.SetPlaybackRate(1.0);
+
+  RunFramePumpTest(
+      false, &frame_tg, &display_tg,
+      [this](const scoped_refptr<VideoFrame>& frame, int frames_dropped) {});
+  if (HasFatalFailure())
+    return;
+  ASSERT_TRUE(is_using_cadence());
+
+  // TODO(dalecurtis): It seems there should be some more things we can test
+  // here...
+}
+
+}  // namespace media