Introduce cadence based VideoRendererAlgorithm.

media/filters/video_renderer_algorithm_unittest.cc

+// 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
+static double NTSC(double fps) {
+  return 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) const {
+    return base::TimeDelta::FromMicroseconds(tick_count *
+                                             microseconds_per_tick_);
+  }
+
+  base::TimeTicks current() const { 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_;
+  const double hertz_;
+  const 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_estimator_.disable_cadence_hysteresis_for_testing();
+  }
+
+  bool last_render_had_glitch() const {
+    return algorithm_.last_render_had_glitch_;
+  }
+
+  bool is_using_cadence() const {
+    return algorithm_.cadence_estimator_.has_cadence();
+  }
+
+  bool IsUsingFractionalCadence() const {
+    return is_using_cadence() &&
+           !algorithm_.cadence_estimator_.GetCadenceForFrame(1);
+  }
+
+  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.
+    size_t 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_.cadence_estimator_.get_cadence_for_testing();
+    time_source_.StopTicking();
+    algorithm_.Reset();
+    return cadence;
+  }
+
+  base::TimeDelta CalculateAbsoluteDriftForFrame(base::TimeTicks deadline_min,
+                                                 int frame_index) {
+    return algorithm_.CalculateAbsoluteDriftForFrame(deadline_min, frame_index);
+  }
+
+  bool DriftOfLastRenderWasWithinTolerance(base::TimeTicks deadline_min) {
+    return CalculateAbsoluteDriftForFrame(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();
+      }
+
+      size_t 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_NEAR(frame_tg->interval(1).InMicroseconds(),
+                    algorithm_.average_frame_duration().InMicroseconds(), 1);
+
+        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 there are no frames, we're not using cadence based selection, or
+      // a frame is under cadence the two queue size reports should be the same.
+      if (!is_using_cadence() || !frames_queued() ||
+          GetCurrentFrameDisplayCount() < GetCurrentFrameIdealDisplayCount()) {
+        ASSERT_EQ(frames_queued(), algorithm_.EffectiveFramesQueued());
+      } else if (is_using_cadence() && !IsUsingFractionalCadence()) {
+        // 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())
+          ASSERT_EQ(frames_queued() - 1, algorithm_.EffectiveFramesQueued());
+      } else if (IsUsingFractionalCadence()) {
+        // The frame estimate should be off by at most one frame.
+        const size_t estimated_frames_queued =
+            frames_queued() /
+            algorithm_.cadence_estimator_.get_cadence_for_testing();
+        ASSERT_NEAR(algorithm_.EffectiveFramesQueued(), estimated_frames_queued,
+                    1);
+      }
+    }
+
+    // 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,
+                           base::TimeDelta* selected_frame_drift) {
+    return algorithm_.FindBestFrameByDrift(deadline_min, selected_frame_drift);
+  }
+
+  int GetCurrentFrameDropCount() const {
+    DCHECK_GT(frames_queued(), 0u);
+    return algorithm_.frame_queue_[algorithm_.last_frame_index_].drop_count;
+  }
+
+  int GetCurrentFrameDisplayCount() const {
+    DCHECK_GT(frames_queued(), 0u);
+    return algorithm_.frame_queue_[algorithm_.last_frame_index_].render_count;
+  }
+
+  int GetCurrentFrameIdealDisplayCount() const {
+    DCHECK_GT(frames_queued(), 0u);
+    return algorithm_.frame_queue_[algorithm_.last_frame_index_]
+        .ideal_render_count;
+  }
+
+  int AccountForMissedIntervals(base::TimeTicks deadline_min,
+                                base::TimeTicks deadline_max) {
+    algorithm_.AccountForMissedIntervals(deadline_min, deadline_max);
+    return algorithm_.frames_queued() ? GetCurrentFrameDisplayCount() : -1;
+  }
+
+ 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);
+  size_t frames_dropped = 0;
+  EXPECT_EQ(0u, frames_queued());
+  EXPECT_FALSE(algorithm_.Render(tg.current(), tg.step(), &frames_dropped));
+  EXPECT_EQ(0u, 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());
+}
+
+TEST_F(VideoRendererAlgorithmTest, AccountForMissingIntervals) {
+  TickGenerator tg(tick_clock_->NowTicks(), 50);
+  time_source_.StartTicking();
+
+  // Disable hysteresis since AccountForMissingIntervals() only affects cadence
+  // based rendering.
+  disable_cadence_hysteresis();
+
+  // Simulate Render() called before any frames are present.
+  EXPECT_EQ(-1, AccountForMissedIntervals(tg.current(), tg.step()));
+
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(0)));
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(1)));
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(2)));
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(3)));
+
+  // Simulate Render() called before any frames have been rendered.
+  EXPECT_EQ(0, AccountForMissedIntervals(tg.current(), tg.step()));
+
+  // Render one frame (several are in the past and will be dropped).
+  base::TimeTicks deadline_min = tg.current();
+  base::TimeTicks deadline_max = tg.step();
+  size_t frames_dropped = 0;
+  scoped_refptr<VideoFrame> frame =
+      algorithm_.Render(deadline_min, deadline_max, &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(2), frame->timestamp());
+  EXPECT_EQ(2u, frames_dropped);
+
+  ASSERT_EQ(1, GetCurrentFrameDisplayCount());
+
+  // Now calling AccountForMissingIntervals with an interval which overlaps the
+  // previous should do nothing.
+  deadline_min += tg.interval(1) / 2;
+  deadline_max += tg.interval(1) / 2;
+  EXPECT_EQ(1, AccountForMissedIntervals(deadline_min, deadline_max));
+
+  // Steping by 1.5 intervals, is not enough to increase the count.
+  deadline_min += tg.interval(1);
+  deadline_max += tg.interval(1);
+  EXPECT_EQ(1, AccountForMissedIntervals(deadline_min, deadline_max));
+
+  // Calling it after a full skipped interval should increase the count by 1 for
+  // each skipped interval.
+  tg.step();
+  EXPECT_EQ(2, AccountForMissedIntervals(tg.current(), tg.step()));
+
+  // 4 because [tg.current(), tg.step()] now represents 2 additional intervals.
+  EXPECT_EQ(4, AccountForMissedIntervals(tg.current(), tg.step()));
+
+  // Frame should be way over cadence and no good frames remain, so last frame
+  // should be returned.
+  frame = algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(3), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+}
+
+TEST_F(VideoRendererAlgorithmTest, OnLastFrameDropped) {
+  TickGenerator frame_tg(base::TimeTicks(), 25);
+  TickGenerator display_tg(tick_clock_->NowTicks(), 50);
+  time_source_.StartTicking();
+
+  // Disable hysteresis since OnLastFrameDropped() only affects cadence based
+  // rendering.
+  disable_cadence_hysteresis();
+
+  algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(0)));
+  algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(1)));
+  algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(2)));
+
+  // Render one frame (several are in the past and will be dropped).
+  size_t frames_dropped = 0;
+  scoped_refptr<VideoFrame> frame = algorithm_.Render(
+      display_tg.current(), display_tg.step(), &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(frame_tg.interval(0), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+
+  // The frame should have its display count decremented once it's reported as
+  // dropped.
+  ASSERT_EQ(1, GetCurrentFrameDisplayCount());
+  ASSERT_EQ(0, GetCurrentFrameDropCount());
+  algorithm_.OnLastFrameDropped();
+  ASSERT_EQ(1, GetCurrentFrameDisplayCount());
+  ASSERT_EQ(1, GetCurrentFrameDropCount());
+
+  // Render the frame again and then force another drop.
+  frame = algorithm_.Render(display_tg.current(), display_tg.step(),
+                            &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(frame_tg.interval(0), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+
+  ASSERT_EQ(2, GetCurrentFrameDisplayCount());
+  ASSERT_EQ(1, GetCurrentFrameDropCount());
+  algorithm_.OnLastFrameDropped();
+  ASSERT_EQ(2, GetCurrentFrameDisplayCount());
+  ASSERT_EQ(2, GetCurrentFrameDropCount());
+
+  // The next Render() call should now count this frame as dropped.
+  frame = algorithm_.Render(display_tg.current(), display_tg.step(),
+                            &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(frame_tg.interval(1), frame->timestamp());
+  EXPECT_EQ(1u, frames_dropped);
+  ASSERT_EQ(1, GetCurrentFrameDisplayCount());
+  ASSERT_EQ(0, GetCurrentFrameDropCount());
+
+  // Rendering again should result in the same frame being displayed.
+  frame = algorithm_.Render(display_tg.current(), display_tg.step(),
+                            &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(frame_tg.interval(1), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+
+  // In this case, the drop count is less than the display count, so the frame
+  // should not be counted as dropped.
+  ASSERT_EQ(2, GetCurrentFrameDisplayCount());
+  ASSERT_EQ(0, GetCurrentFrameDropCount());
+  algorithm_.OnLastFrameDropped();
+  ASSERT_EQ(2, GetCurrentFrameDisplayCount());
+  ASSERT_EQ(1, GetCurrentFrameDropCount());
+
+  // The third frame should be rendered correctly now and the previous frame not
+  // counted as having been dropped.
+  frame = algorithm_.Render(display_tg.current(), display_tg.step(),
+                            &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(frame_tg.interval(2), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+}
+
+TEST_F(VideoRendererAlgorithmTest, EffectiveFramesQueued) {
+  TickGenerator frame_tg(base::TimeTicks(), 50);
+  TickGenerator display_tg(tick_clock_->NowTicks(), 25);
+
+  // Disable hysteresis since EffectiveFramesQueued() is tested as part of the
+  // normal frame pump tests when cadence is not present.
+  disable_cadence_hysteresis();
+
+  EXPECT_EQ(0u, algorithm_.EffectiveFramesQueued());
+  time_source_.StartTicking();
+
+  algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(0)));
+  EXPECT_EQ(1u, algorithm_.EffectiveFramesQueued());
+
+  algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(1)));
+  EXPECT_EQ(2u, algorithm_.EffectiveFramesQueued());
+
+  algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(2)));
+  EXPECT_EQ(3u, algorithm_.EffectiveFramesQueued());
+
+  algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(3)));
+  EXPECT_EQ(4u, algorithm_.EffectiveFramesQueued());
+  EXPECT_EQ(4u, algorithm_.frames_queued());
+
+  // Render one frame which will detect cadence...
+  size_t frames_dropped = 0;
+  scoped_refptr<VideoFrame> frame = algorithm_.Render(
+      display_tg.current(), display_tg.step(), &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(frame_tg.interval(0), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+
+  // Fractional cadence should be detected and the count will decrease.
+  ASSERT_TRUE(is_using_cadence());
+  EXPECT_EQ(1u, algorithm_.EffectiveFramesQueued());
+  EXPECT_EQ(4u, algorithm_.frames_queued());
+
+  // Dropping the last rendered frame should do nothing, since the last frame
+  // is already excluded from the count if it has a display count of 1.
+  algorithm_.OnLastFrameDropped();
+  EXPECT_EQ(1u, algorithm_.EffectiveFramesQueued());
+}
+
+// The maximum acceptable drift should be updated once we have two frames.
+TEST_F(VideoRendererAlgorithmTest, AcceptableDriftUpdated) {
+  TickGenerator tg(tick_clock_->NowTicks(), 50);
+
+  size_t 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.
+  size_t 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(0u, frames_dropped);
+  EXPECT_EQ(1u, frames_queued());
+  EXPECT_EQ(1u, algorithm_.EffectiveFramesQueued());
+
+  // 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(0u, frames_dropped);
+  EXPECT_EQ(1u, frames_queued());
+  EXPECT_EQ(1u, algorithm_.EffectiveFramesQueued());
+
+  // Ensure the next suitable frame is vended as time advances.
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(1)));
+  EXPECT_EQ(2u, frames_queued());
+  EXPECT_EQ(2u, algorithm_.EffectiveFramesQueued());
+  frame = algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(1), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+  EXPECT_EQ(1u, frames_queued());
+  EXPECT_EQ(1u, algorithm_.EffectiveFramesQueued());
+
+  // 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(0u, frames_dropped);
+  EXPECT_EQ(2u, frames_queued());
+  EXPECT_EQ(2u, algorithm_.EffectiveFramesQueued());
+}
+
+// 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());
+  EXPECT_EQ(2u, algorithm_.EffectiveFramesQueued());
+
+  time_source_.StartTicking();
+
+  // The first call should return the earliest frame appended.
+  size_t frames_dropped = 0;
+  scoped_refptr<VideoFrame> frame =
+      algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  EXPECT_EQ(0u, frames_dropped);
+  EXPECT_EQ(tg.interval(2), frame->timestamp());
+  EXPECT_EQ(2u, frames_queued());
+  EXPECT_EQ(2u, algorithm_.EffectiveFramesQueued());
+
+  // Since a frame has already been rendered, queuing 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)));
+  EXPECT_EQ(3u, frames_queued());
+  EXPECT_EQ(2u, algorithm_.EffectiveFramesQueued());
+  frame = algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  EXPECT_EQ(1u, frames_dropped);
+  EXPECT_EQ(tg.interval(2), frame->timestamp());
+  EXPECT_EQ(2u, frames_queued());
+  EXPECT_EQ(2u, algorithm_.EffectiveFramesQueued());
+}
+
+// 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, size_t frames_dropped) {
+          ASSERT_TRUE(frame);
+          ASSERT_EQ(0u, 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, BestFrameByCadenceOverdisplayed) {
+  TickGenerator frame_tg(base::TimeTicks(), 25);
+  TickGenerator display_tg(tick_clock_->NowTicks(), 50);
+  time_source_.StartTicking();
+  disable_cadence_hysteresis();
+
+  algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(0)));
+  algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(1)));
+
+  // Render frames until we've exhausted available frames and the last frame is
+  // forced to be overdisplayed.
+  for (int i = 0; i < 5; ++i) {
+    size_t frames_dropped = 0;
+    scoped_refptr<VideoFrame> frame = algorithm_.Render(
+        display_tg.current(), display_tg.step(), &frames_dropped);
+    ASSERT_TRUE(frame);
+    EXPECT_EQ(frame_tg.interval(i < 4 ? i / 2 : 1), frame->timestamp());
+    EXPECT_EQ(0u, frames_dropped);
+    ASSERT_EQ(2, GetCurrentFrameIdealDisplayCount());
+  }
+
+  // Verify last frame is above cadence (2 in this case)
+  ASSERT_EQ(GetCurrentFrameIdealDisplayCount() + 1,
+            GetCurrentFrameDisplayCount());
+  algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(2)));
+  algorithm_.EnqueueFrame(CreateFrame(frame_tg.interval(3)));
+
+  // The next frame should only be displayed once, since the previous one was
+  // overdisplayed by one frame.
+  size_t frames_dropped = 0;
+  scoped_refptr<VideoFrame> frame = algorithm_.Render(
+      display_tg.current(), display_tg.step(), &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(frame_tg.interval(2), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+  ASSERT_EQ(1, GetCurrentFrameIdealDisplayCount());
+
+  frame = algorithm_.Render(display_tg.current(), display_tg.step(),
+                            &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(frame_tg.interval(3), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+  ASSERT_EQ(2, GetCurrentFrameIdealDisplayCount());
+}
+
+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);
+
+  size_t 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(0u, 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);
+}
+
+TEST_F(VideoRendererAlgorithmTest, BestFrameByDriftAndDriftCalculations) {
+  TickGenerator tg(tick_clock_->NowTicks(), 50);
+  time_source_.StartTicking();
+
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(0)));
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(1)));
+
+  size_t frames_dropped = 0;
+  scoped_refptr<VideoFrame> frame = algorithm_.Render(
+      tg.current(), tg.current() + tg.interval(1), &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(0), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+
+  base::TimeDelta zero_drift, half_drift = tg.interval(1) / 2;
+  base::TimeDelta detected_drift;
+
+  // Frame_0 overlaps the deadline, Frame_1 is a full interval away.
+  base::TimeTicks deadline = tg.current();
+  EXPECT_EQ(zero_drift, CalculateAbsoluteDriftForFrame(deadline, 0));
+  EXPECT_EQ(tg.interval(1), CalculateAbsoluteDriftForFrame(deadline, 1));
+  EXPECT_EQ(0, FindBestFrameByDrift(deadline, &detected_drift));
+  EXPECT_EQ(zero_drift, detected_drift);
+
+  // Frame_0 overlaps the deadline, Frame_1 is a half interval away.
+  deadline += half_drift;
+  EXPECT_EQ(zero_drift, CalculateAbsoluteDriftForFrame(deadline, 0));
+  EXPECT_EQ(half_drift, CalculateAbsoluteDriftForFrame(deadline, 1));
+  EXPECT_EQ(0, FindBestFrameByDrift(deadline, &detected_drift));
+  EXPECT_EQ(zero_drift, detected_drift);
+
+  // Both frames overlap the deadline.
+  deadline += half_drift;
+  EXPECT_EQ(zero_drift, CalculateAbsoluteDriftForFrame(deadline, 0));
+  EXPECT_EQ(zero_drift, CalculateAbsoluteDriftForFrame(deadline, 1));
+  EXPECT_EQ(1, FindBestFrameByDrift(deadline, &detected_drift));
+  EXPECT_EQ(zero_drift, detected_drift);
+
+  // Frame_0 is half an interval away, Frame_1 overlaps the deadline.
+  deadline += half_drift;
+  EXPECT_EQ(half_drift, CalculateAbsoluteDriftForFrame(deadline, 0));
+  EXPECT_EQ(zero_drift, CalculateAbsoluteDriftForFrame(deadline, 1));
+  EXPECT_EQ(1, FindBestFrameByDrift(deadline, &detected_drift));
+  EXPECT_EQ(zero_drift, detected_drift);
+
+  // Frame_0 is a full interval away, Frame_1 overlaps the deadline.
+  deadline += half_drift;
+  EXPECT_EQ(tg.interval(1), CalculateAbsoluteDriftForFrame(deadline, 0));
+  EXPECT_EQ(zero_drift, CalculateAbsoluteDriftForFrame(deadline, 1));
+  EXPECT_EQ(1, FindBestFrameByDrift(deadline, &detected_drift));
+  EXPECT_EQ(zero_drift, detected_drift);
+
+  // Both frames are entirely before the deadline.
+  deadline += half_drift;
+  EXPECT_EQ(tg.interval(1) + half_drift,
+            CalculateAbsoluteDriftForFrame(deadline, 0));
+  EXPECT_EQ(half_drift, CalculateAbsoluteDriftForFrame(deadline, 1));
+  EXPECT_EQ(1, FindBestFrameByDrift(deadline, &detected_drift));
+  EXPECT_EQ(half_drift, detected_drift);
+}
+
+// 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 size_t 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, size_t 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(0u, 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, size_t frames_dropped) {
+          ASSERT_TRUE(frame);
+          ASSERT_EQ(0u, 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(0u, algorithm_.RemoveExpiredFrames(tg.current()));
+  EXPECT_EQ(1u, algorithm_.EffectiveFramesQueued());
+
+  time_source_.StartTicking();
+
+  size_t 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(0u, 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)));
+  EXPECT_EQ(5u, algorithm_.EffectiveFramesQueued());
+
+  tg.step(2);
+  ASSERT_EQ(2u, algorithm_.RemoveExpiredFrames(tg.current()));
+  frame = algorithm_.Render(tg.current(), tg.step(), &frames_dropped);
+  EXPECT_EQ(1u, frames_dropped);
+  EXPECT_EQ(2u, frames_queued());
+  EXPECT_EQ(2u, algorithm_.EffectiveFramesQueued());
+  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, size_t 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);
+
+  const double kTestRates[] = {1.0, 2, 0.215, 0.5, 1.0};
+  const bool kTestRateHasCadence[arraysize(kTestRates)] = {
+      true, true, false, true, true};
+
+  for (size_t i = 0; i < arraysize(kTestRates); ++i) {
+    const double playback_rate = kTestRates[i];
+    SCOPED_TRACE(base::StringPrintf("Playback Rate: %.03f", playback_rate));
+    time_source_.SetPlaybackRate(playback_rate);
+    RunFramePumpTest(false, &frame_tg, &display_tg,
+                     [this](const scoped_refptr<VideoFrame>& frame,
+                            size_t frames_dropped) {});
+    if (HasFatalFailure())
+      return;
+
+    ASSERT_EQ(kTestRateHasCadence[i], is_using_cadence());
+  }
+
+  // TODO(dalecurtis): It seems there should be some more things we can test
+  // here...
+}
+
+// Ensures media which only expresses timestamps in milliseconds, gets the right
+// cadence detection.
+TEST_F(VideoRendererAlgorithmTest, UglyTimestampsHaveCadence) {
+  TickGenerator display_tg(tick_clock_->NowTicks(), 60);
+  time_source_.StartTicking();
+
+  // 59.94fps, timestamp deltas from https://youtu.be/byoLvAo9qjs
+  const int kBadTimestampsMs[] = {
+      17, 16, 17, 17, 16, 17, 17, 16, 17, 17, 17, 16, 17, 17, 16, 17, 17, 16,
+      17, 17, 16, 17, 17, 16, 17, 17, 16, 17, 17, 17, 16, 17, 17, 16, 17, 17,
+      16, 17, 17, 16, 17, 17, 16, 17, 17, 16, 17, 17, 16, 17, 17, 17};
+
+  // Run throught ~1.6 seconds worth of frames.
+  bool cadence_detected = false;
+  base::TimeDelta timestamp;
+  for (size_t i = 0; i < arraysize(kBadTimestampsMs) * 2; ++i) {
+    while (algorithm_.EffectiveFramesQueued() < 3) {
+      algorithm_.EnqueueFrame(CreateFrame(timestamp));
+      timestamp += base::TimeDelta::FromMilliseconds(
+          kBadTimestampsMs[i % arraysize(kBadTimestampsMs)]);
+    }
+
+    size_t frames_dropped = 0;
+    algorithm_.Render(display_tg.current(), display_tg.step(), &frames_dropped);
+    ASSERT_EQ(0u, frames_dropped);
+
+    // Cadence won't be detected immediately on this clip, but it will after
+    // enough frames are encountered; after which it should not drop out of
+    // cadence.
+    if (is_using_cadence())
+      cadence_detected = true;
+
+    if (cadence_detected)
+      ASSERT_TRUE(is_using_cadence());
+  }
+}
+
+}  // namespace media