Introduce cadence based VideoRendererAlgorithm.

This is the engine which will power the new video
rendering pipeline! VideoRendererImpl will use this
to manage frame selection (as audio uses a similarly
named AudioRendererAlgorithm).

It attempts to first find a cadence match for a set
of frames (i.e. 30fps in 60Hz would have each frame
displayed for two render intervals). If it can not
find a cadence match, it attempts to find the frame
which covers the vsync interval the most. If no frame
covers the interval it then chooses the frame which
is closest to the deadline.

Cadence fitting is based on a calculation of how long
it would take for a frame to be repeated or dropped
if the cadence is forced from say X.# to just X.0.

It handles both integer (30fps in 60Hz) and fractional
cadences (120fps in 60Hz). It uses a hysteresis of
100ms to avoid oscillation of the cadence.

Clients may use have a secondary pumping mechanism
which can expire frames which fall too far behind
the current media time; this is to handle cases where
the compositor has stopped providing callbacks.

Testing shows it's significantly smoother than the
existing rendering pipeline! \o/

Profiling notes over 45 minutes of simulated time:
- 83ms, UpdateFrameStatistics() most expensive.
- 73ms, for removal of frames from the deque.
- 20ms, for CalculateCadence().

Overall nothing is much of a hot spot, 45 minutes of
simulated time takes ~400ms to run.

BUG=439548
TEST=new unittest.

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

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

12 files changed, 2637 insertions, 0 deletions

diff --git a/media/BUILD.gn b/media/BUILD.gn
index b62b0ea..ce839dd 100644
--- a/media/BUILD.gn
+++ b/media/BUILD.gn
@@ -142,6 +142,10 @@ component("media") {
     "filters/source_buffer_stream.h",
     "filters/stream_parser_factory.cc",
     "filters/stream_parser_factory.h",
+    "filters/video_cadence_estimator.cc",
+    "filters/video_cadence_estimator.h",
+    "filters/video_renderer_algorithm.cc",
+    "filters/video_renderer_algorithm.h",
     "filters/vp8_bool_decoder.cc",
     "filters/vp8_bool_decoder.h",
     "filters/vp8_parser.cc",
@@ -515,8 +519,10 @@ test("media_unittests") {
     "filters/h264_parser_unittest.cc",
     "filters/jpeg_parser_unittest.cc",
     "filters/source_buffer_stream_unittest.cc",
+    "filters/video_cadence_estimator_unittest.cc",
     "filters/video_decoder_selector_unittest.cc",
     "filters/video_frame_stream_unittest.cc",
+    "filters/video_renderer_algorithm_unittest.cc",
     "filters/vp8_bool_decoder_unittest.cc",
     "filters/vp8_parser_unittest.cc",
     "formats/common/offset_byte_queue_unittest.cc",
diff --git a/media/base/BUILD.gn b/media/base/BUILD.gn
index f8f3c69..0602408 100644
--- a/media/base/BUILD.gn
+++ b/media/base/BUILD.gn
@@ -119,6 +119,8 @@ source_set("base") {
     "media_permission.h",
     "media_switches.cc",
     "media_switches.h",
+    "moving_average.cc",
+    "moving_average.h",
     "multi_channel_resampler.cc",
     "multi_channel_resampler.h",
     "null_video_sink.cc",
@@ -375,6 +377,7 @@ source_set("unittests") {
     "djb2_unittest.cc",
     "gmock_callback_support_unittest.cc",
     "key_systems_unittest.cc",
+    "moving_average_unittest.cc",
     "multi_channel_resampler_unittest.cc",
     "null_video_sink_unittest.cc",
     "pipeline_unittest.cc",
diff --git a/media/base/moving_average.cc b/media/base/moving_average.cc
new file mode 100644
index 0000000..c8ca7dd
--- /dev/null
+++ b/media/base/moving_average.cc
@@ -0,0 +1,41 @@
+// 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/base/moving_average.h"
+
+#include <algorithm>
+
+namespace media {
+
+MovingAverage::MovingAverage(size_t depth)
+    : depth_(depth), count_(0), samples_(depth_) {
+}
+
+MovingAverage::~MovingAverage() {
+}
+
+void MovingAverage::AddSample(base::TimeDelta sample) {
+  // |samples_| is zero-initialized, so |oldest| is also zero before |count_|
+  // exceeds |depth_|.
+  base::TimeDelta& oldest = samples_[count_++ % depth_];
+  total_ += sample - oldest;
+  oldest = sample;
+}
+
+base::TimeDelta MovingAverage::Average() const {
+  DCHECK_GT(count_, 0u);
+
+  // TODO(dalecurtis): Consider limiting |depth| to powers of two so that we can
+  // replace the integer divide with a bit shift operation.
+
+  return total_ / std::min(depth_, count_);
+}
+
+void MovingAverage::Reset() {
+  count_ = 0;
+  total_ = base::TimeDelta();
+  std::fill(samples_.begin(), samples_.end(), base::TimeDelta());
+}
+
+}  // namespace media
diff --git a/media/base/moving_average.h b/media/base/moving_average.h
new file mode 100644
index 0000000..aa69750
--- /dev/null
+++ b/media/base/moving_average.h
@@ -0,0 +1,47 @@
+// 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.
+
+#ifndef MEDIA_BASE_MOVING_AVERAGE_H_
+#define MEDIA_BASE_MOVING_AVERAGE_H_
+
+#include <vector>
+
+#include "base/time/time.h"
+#include "media/base/media_export.h"
+
+namespace media {
+
+// Simple class for calculating a moving average of fixed size.
+class MEDIA_EXPORT MovingAverage {
+ public:
+  // Creates a MovingAverage instance with space for |depth| samples.
+  explicit MovingAverage(size_t depth);
+  ~MovingAverage();
+
+  // Adds a new sample to the average; replaces the oldest sample if |depth_|
+  // has been exceeded.  Updates |total_| to the new sum of values.
+  void AddSample(base::TimeDelta sample);
+
+  // Returns the current average of all held samples.
+  base::TimeDelta Average() const;
+
+  // Resets the state of the class to its initial post-construction state.
+  void Reset();
+
+ private:
+  // Maximum number of elements allowed in the average.
+  const size_t depth_;
+
+  // Number of elements seen thus far.
+  size_t count_;
+
+  std::vector<base::TimeDelta> samples_;
+  base::TimeDelta total_;
+
+  DISALLOW_COPY_AND_ASSIGN(MovingAverage);
+};
+
+}  // namespace media
+
+#endif  // MEDIA_BASE_MOVING_AVERAGE_H_
diff --git a/media/base/moving_average_unittest.cc b/media/base/moving_average_unittest.cc
new file mode 100644
index 0000000..da8e519
--- /dev/null
+++ b/media/base/moving_average_unittest.cc
@@ -0,0 +1,36 @@
+// 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 "base/time/time.h"
+#include "media/base/moving_average.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace media {
+
+TEST(MovingAverageTest, Average) {
+  const int kSamples = 5;
+  MovingAverage moving_average(kSamples);
+  moving_average.AddSample(base::TimeDelta::FromSeconds(1));
+  EXPECT_EQ(base::TimeDelta::FromSeconds(1), moving_average.Average());
+  for (int i = 0; i < kSamples - 1; ++i)
+    moving_average.AddSample(base::TimeDelta::FromSeconds(1));
+  EXPECT_EQ(base::TimeDelta::FromSeconds(1), moving_average.Average());
+
+  for (int i = 0; i < kSamples; ++i) {
+    moving_average.AddSample(base::TimeDelta::FromMilliseconds(500));
+    EXPECT_EQ(base::TimeDelta::FromMilliseconds(1000 - (i + 1) * 100),
+              moving_average.Average());
+  }
+}
+
+TEST(MovingAverageTest, Reset) {
+  MovingAverage moving_average(2);
+  moving_average.AddSample(base::TimeDelta::FromSeconds(1));
+  EXPECT_EQ(base::TimeDelta::FromSeconds(1), moving_average.Average());
+  moving_average.Reset();
+  moving_average.AddSample(base::TimeDelta());
+  EXPECT_EQ(base::TimeDelta(), moving_average.Average());
+}
+
+}  // namespace media
diff --git a/media/filters/video_cadence_estimator.cc b/media/filters/video_cadence_estimator.cc
new file mode 100644
index 0000000..57b71b4
--- /dev/null
+++ b/media/filters/video_cadence_estimator.cc
@@ -0,0 +1,167 @@
+// 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 <limits>
+
+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;
+
+VideoCadenceEstimator::VideoCadenceEstimator(
+    base::TimeDelta minimum_time_until_glitch)
+    : cadence_hysteresis_threshold_(
+          base::TimeDelta::FromMilliseconds(kMinimumCadenceDurationMs)),
+      minimum_time_until_glitch_(minimum_time_until_glitch) {
+  Reset();
+}
+
+VideoCadenceEstimator::~VideoCadenceEstimator() {
+}
+
+void VideoCadenceEstimator::Reset() {
+  cadence_ = fractional_cadence_ = 0;
+  pending_cadence_ = pending_fractional_cadence_ = 0;
+  render_intervals_cadence_held_ = 0;
+}
+
+bool VideoCadenceEstimator::UpdateCadenceEstimate(
+    base::TimeDelta render_interval,
+    base::TimeDelta frame_duration,
+    base::TimeDelta max_acceptable_drift) {
+  DCHECK_GT(render_interval, base::TimeDelta());
+  DCHECK_GT(frame_duration, base::TimeDelta());
+
+  base::TimeDelta time_until_cadence_glitch;
+  base::TimeDelta time_until_fractional_cadence_glitch;
+
+  // See if the clamped cadence fits acceptable thresholds for exhausting drift.
+  int new_cadence = 0, new_fractional_cadence = 0;
+  if (CalculateCadence(render_interval, frame_duration, max_acceptable_drift,
+                       false, &new_cadence, &time_until_cadence_glitch)) {
+    DCHECK(new_cadence);
+  } else if (CalculateCadence(render_interval, frame_duration,
+                              max_acceptable_drift, true,
+                              &new_fractional_cadence,
+                              &time_until_fractional_cadence_glitch)) {
+    new_cadence = 1;
+    DCHECK(new_fractional_cadence);
+  }
+
+  // Nothing changed, so do nothing.
+  if (new_cadence == cadence_ &&
+      new_fractional_cadence == fractional_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_ &&
+       new_fractional_cadence == pending_fractional_cadence_) ||
+      cadence_hysteresis_threshold_ <= render_interval) {
+    if (++render_intervals_cadence_held_ * render_interval >=
+        cadence_hysteresis_threshold_) {
+      DVLOG(1) << "Cadence switch: (" << cadence_ << ", " << fractional_cadence_
+               << ") -> (" << new_cadence << ", " << new_fractional_cadence
+               << ") :: (" << time_until_cadence_glitch << ", "
+               << time_until_fractional_cadence_glitch << ")";
+
+      cadence_ = new_cadence;
+      fractional_cadence_ = new_fractional_cadence;
+      return true;
+    }
+
+    update_pending_cadence = false;
+  }
+
+  DVLOG(2) << "Hysteresis prevented cadence switch: (" << cadence_ << ", "
+           << fractional_cadence_ << ") -> (" << new_cadence << ", "
+           << new_fractional_cadence << ") :: (" << time_until_cadence_glitch
+           << ", " << time_until_fractional_cadence_glitch << ")";
+
+  if (update_pending_cadence) {
+    pending_cadence_ = new_cadence;
+    pending_fractional_cadence_ = new_fractional_cadence;
+    render_intervals_cadence_held_ = 1;
+  }
+
+  return false;
+}
+
+bool VideoCadenceEstimator::CalculateCadence(
+    base::TimeDelta render_interval,
+    base::TimeDelta frame_duration,
+    base::TimeDelta max_acceptable_drift,
+    bool fractional,
+    int* cadence,
+    base::TimeDelta* time_until_glitch) {
+  // The perfect cadence is the number of render intervals per frame, while the
+  // clamped cadence is the nearest matching integer cadence.
+  //
+  // Fractional cadence is checked to see if we have a cadence which would look
+  // best if we consistently drop the same frames.
+  //
+  // 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|.  When computing a fractional
+  // cadence (1/|perfect_cadence|), |fractional| must be set to true to ensure
+  // the rendered and actual frame durations are computed correctly.
+  const double perfect_cadence =
+      fractional ? render_interval.InSecondsF() / frame_duration.InSecondsF()
+                 : frame_duration.InSecondsF() / render_interval.InSecondsF();
+  const int clamped_cadence = perfect_cadence + 0.5;
+  if (!clamped_cadence)
+    return false;
+
+  // Calculate the drift in microseconds for each frame we render at cadence
+  // instead of for its real duration.
+  const base::TimeDelta rendered_frame_duration =
+      fractional ? render_interval : clamped_cadence * render_interval;
+
+  // When computing a fractional drift, we render the first of |clamped_cadence|
+  // frames and drop |clamped_cadence| - 1 frames.  To make the calculations
+  // below work we need to project out the timestamp of the frame which would be
+  // rendered after accounting for those |clamped_cadence| frames.
+  const base::TimeDelta actual_frame_duration =
+      fractional ? clamped_cadence * frame_duration : frame_duration;
+  if (rendered_frame_duration == actual_frame_duration) {
+    *cadence = clamped_cadence;
+    return true;
+  }
+
+  // Compute how long it'll take to exhaust the drift using |clamped_cadence|.
+  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);
+  *time_until_glitch = rendered_frame_duration * frames_until_drift_exhausted;
+
+  if (*time_until_glitch >= minimum_time_until_glitch_) {
+    *cadence = clamped_cadence;
+    return true;
+  }
+
+  return false;
+}
+
+int VideoCadenceEstimator::GetCadenceForFrame(int index) const {
+  DCHECK(has_cadence());
+  DCHECK_GE(index, 0);
+
+  if (fractional_cadence_)
+    return index % fractional_cadence_ == 0 ? 1 : 0;
+
+  return cadence_;
+}
+
+}  // namespace media
diff --git a/media/filters/video_cadence_estimator.h b/media/filters/video_cadence_estimator.h
new file mode 100644
index 0000000..efd1feb
--- /dev/null
+++ b/media/filters/video_cadence_estimator.h
@@ -0,0 +1,154 @@
+// 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.
+
+#ifndef MEDIA_FILTERS_VIDEO_CADENCE_ESTIMATOR_H_
+#define MEDIA_FILTERS_VIDEO_CADENCE_ESTIMATOR_H_
+
+#include "base/time/time.h"
+#include "media/base/media_export.h"
+
+namespace media {
+
+// Estimates whether a given frame duration and render interval length have a
+// render cadence which would allow for optimal uniformity of displayed frame
+// durations over time.
+//
+// Cadence is the ratio of the frame duration to render interval length.  I.e.
+// for 30fps in 60Hz the cadence would be (1/30) / (1/60) = 60 / 30 = 2.  It's
+// common that this is not an exact integer, e.g., 29.974fps in 60Hz which
+// would have a cadence of (1/29.974) / (1/60) = ~2.0029.
+//
+// Clamped integer cadence means we round the actual cadence (~2.0029 in the
+// pending example) to the nearest integer value (2 in this case).  If the
+// delta between those values is small, we can choose to render frames for the
+// integer number of render intervals; shortening or lengthening the actual
+// rendered frame duration.  Doing so ensures each frame gets an optimal amount
+// of display time.
+//
+// Obviously clamping cadence like that leads to drift over time of the actual
+// VideoFrame timestamp relative to its rendered time, so we perform some
+// calculations to ensure we only clamp cadence when it will take some time to
+// drift an undesirable amount; see CalculateCadence() for details on how this
+// calculation is made.
+//
+// Notably, this concept can be extended to include fractional cadence 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; where N is the fractional cadence of the
+// frame group.  Using the pending example N = 120/60 = 2. See implementations
+// of CalculateCadence() and UpdateCadenceEstimate() 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.
+//    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.
+//
+class MEDIA_EXPORT VideoCadenceEstimator {
+ public:
+  // 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
+  // drift; this time length is controlled by |minimum_time_until_glitch|.
+  explicit VideoCadenceEstimator(base::TimeDelta minimum_time_until_glitch);
+  ~VideoCadenceEstimator();
+
+  // Clears stored cadence information.
+  void Reset();
+
+  // Updates the estimates for |cadence_| and |fractional_cadence_| based on the
+  // given values as described in the introduction above.
+  //
+  // Clients should call this and then update the cadence for all frames via the
+  // GetCadenceForFrame() method.
+  //
+  // Cadence changes will not take affect until enough render intervals have
+  // elapsed.  For the purposes of hysteresis, each UpdateCadenceEstimate() call
+  // is assumed to elapse one |render_interval| worth of time.
+  //
+  // Returns true if the cadence has changed since the last call.
+  bool UpdateCadenceEstimate(base::TimeDelta render_interval,
+                             base::TimeDelta frame_duration,
+                             base::TimeDelta max_acceptable_drift);
+
+  // Returns true if a useful cadence was found.
+  bool has_cadence() const { return cadence_ > 0; }
+
+  // Given a frame |index|, where zero is the most recently rendered frame,
+  // returns the ideal cadence for that frame.
+  int GetCadenceForFrame(int index) const;
+
+  void set_cadence_hysteresis_threshold_for_testing(base::TimeDelta threshold) {
+    cadence_hysteresis_threshold_ = threshold;
+  }
+
+  int get_cadence_for_testing() const {
+    return cadence_ && fractional_cadence_ ? fractional_cadence_ : cadence_;
+  }
+
+ private:
+  // 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_glitch_|, returns true and sets |cadence| to the
+  // clamped cadence.  If the clamped cadence is unusable, |cadence| will be set
+  // to zero.
+  //
+  // If |fractional| is true, GetCadence() will calculate the clamped cadence
+  // using the ratio of the |render_interval| to |frame_duration| instead of
+  // vice versa.
+  //
+  // Sets |time_until_glitch| to the computed glitch time.  Set to zero if the
+  // clamped cadence is unusable.
+  bool CalculateCadence(base::TimeDelta render_interval,
+                        base::TimeDelta frame_duration,
+                        base::TimeDelta max_acceptable_drift,
+                        bool fractional,
+                        int* cadence,
+                        base::TimeDelta* time_until_glitch);
+
+  // The idealized cadence for all frames seen thus far; updated based upon the
+  // ratio of |frame_duration| to |render_interval|, or vice versa, as given to
+  // UpdateCadenceEstimate().  Zero if no integer cadence could be detected.
+  //
+  // Fractional cadences are handled by strongly preferring the first frame in
+  // a series if it fits within acceptable drift. E.g., with 120fps content on
+  // a 60Hz monitor we'll strongly prefer the first frame of every 2 frames.
+  //
+  // |fractional_cadence_| is the number of frames per render interval; the
+  // first of which would be rendered and the rest dropped.
+  int cadence_;
+  int fractional_cadence_;
+
+  // Used as hysteresis to prevent oscillation between cadence and coverage
+  // based rendering methods.  Pending values are updated upon each new cadence
+  // detected by UpdateCadenceEstimate().
+  //
+  // Once a new cadence is detected, |render_intervals_cadence_held_| is
+  // incremented for each UpdateCadenceEstimate() call where the cadence matches
+  // one of the pending values.  |render_intervals_cadence_held_| is cleared
+  // when a "new" cadence matches |cadence_| or |pending_cadence_|.
+  //
+  // Once |kMinimumCadenceDurationMs| is exceeded in render intervals, the
+  // detected cadence is set in |cadence_| and |fractional_cadence_|.
+  int pending_cadence_;
+  int pending_fractional_cadence_;
+  int render_intervals_cadence_held_;
+  base::TimeDelta cadence_hysteresis_threshold_;
+
+  // The minimum amount of time allowed before a glitch occurs before confirming
+  // cadence for a given render interval and frame duration.
+  const base::TimeDelta minimum_time_until_glitch_;
+
+  DISALLOW_COPY_AND_ASSIGN(VideoCadenceEstimator);
+};
+
+}  // namespace media
+
+#endif  // MEDIA_FILTERS_VIDEO_CADENCE_ESTIMATOR_H_
diff --git a/media/filters/video_cadence_estimator_unittest.cc b/media/filters/video_cadence_estimator_unittest.cc
new file mode 100644
index 0000000..04ca70c
--- /dev/null
+++ b/media/filters/video_cadence_estimator_unittest.cc
@@ -0,0 +1,171 @@
+// 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 "base/memory/scoped_ptr.h"
+#include "base/strings/stringprintf.h"
+#include "media/filters/video_cadence_estimator.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace media {
+
+// See VideoCadenceEstimator header for more details.
+const int kMinimumAcceptableTimeBetweenGlitchesSecs = 8;
+
+// 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;
+}
+
+static base::TimeDelta Interval(double hertz) {
+  return base::TimeDelta::FromSecondsD(1.0 / hertz);
+}
+
+static void VerifyCadence(VideoCadenceEstimator* estimator,
+                          double frame_hertz,
+                          double render_hertz,
+                          int expected_cadence) {
+  SCOPED_TRACE(base::StringPrintf("Checking %.03f fps into %0.03f", frame_hertz,
+                                  render_hertz));
+  estimator->Reset();
+  const base::TimeDelta acceptable_drift = Interval(frame_hertz) / 2;
+  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, estimator->has_cadence());
+
+  // Nothing further to test.
+  if (!expected_cadence)
+    return;
+
+  // Spot check a few frame indices.
+  if (frame_hertz <= render_hertz) {
+    EXPECT_EQ(expected_cadence, estimator->GetCadenceForFrame(0));
+    EXPECT_EQ(expected_cadence, estimator->GetCadenceForFrame(1));
+    EXPECT_EQ(expected_cadence, estimator->GetCadenceForFrame(2));
+  } else {
+    EXPECT_EQ(1, estimator->GetCadenceForFrame(0));
+    EXPECT_EQ(0, estimator->GetCadenceForFrame(1));
+    EXPECT_EQ(1, estimator->GetCadenceForFrame(expected_cadence));
+    EXPECT_EQ(0, estimator->GetCadenceForFrame(expected_cadence + 1));
+  }
+}
+
+// Spot check common display and frame rate pairs for correctness.
+TEST(VideoCadenceEstimatorTest, CadenceCalculations) {
+  VideoCadenceEstimator estimator(
+      base::TimeDelta::FromSeconds(kMinimumAcceptableTimeBetweenGlitchesSecs));
+  estimator.set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
+
+  VerifyCadence(&estimator, 24, 60, 0);
+  VerifyCadence(&estimator, NTSC(24), 60, 0);
+  VerifyCadence(&estimator, 25, 60, 0);
+  VerifyCadence(&estimator, NTSC(30), 60, 2);
+  VerifyCadence(&estimator, 30, 60, 2);
+  VerifyCadence(&estimator, 50, 60, 0);
+  VerifyCadence(&estimator, NTSC(60), 60, 1);
+  VerifyCadence(&estimator, 120, 60, 2);
+
+  // 50Hz is common in the EU.
+  VerifyCadence(&estimator, NTSC(24), 50, 0);
+  VerifyCadence(&estimator, 24, 50, 0);
+  VerifyCadence(&estimator, NTSC(25), 50, 2);
+  VerifyCadence(&estimator, 25, 50, 2);
+  VerifyCadence(&estimator, NTSC(30), 50, 0);
+  VerifyCadence(&estimator, 30, 50, 0);
+  VerifyCadence(&estimator, NTSC(60), 50, 0);
+  VerifyCadence(&estimator, 60, 50, 0);
+
+  VerifyCadence(&estimator, 25, NTSC(60), 0);
+  VerifyCadence(&estimator, 120, NTSC(60), 0);
+  VerifyCadence(&estimator, 1, NTSC(60), 60);
+}
+
+TEST(VideoCadenceEstimatorTest, CadenceVariesWithAcceptableDrift) {
+  VideoCadenceEstimator estimator(
+      base::TimeDelta::FromSeconds(kMinimumAcceptableTimeBetweenGlitchesSecs));
+  estimator.set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
+
+  const base::TimeDelta render_interval = Interval(NTSC(60));
+  const base::TimeDelta frame_interval = Interval(120);
+
+  base::TimeDelta acceptable_drift = frame_interval / 2;
+  EXPECT_FALSE(estimator.UpdateCadenceEstimate(render_interval, frame_interval,
+                                               acceptable_drift));
+  EXPECT_FALSE(estimator.has_cadence());
+
+  // Increasing the acceptable drift should be result in more permissive
+  // detection of cadence.
+  acceptable_drift = render_interval;
+  EXPECT_TRUE(estimator.UpdateCadenceEstimate(render_interval, frame_interval,
+                                              acceptable_drift));
+  EXPECT_TRUE(estimator.has_cadence());
+  EXPECT_EQ(2, estimator.get_cadence_for_testing());
+}
+
+TEST(VideoCadenceEstimatorTest, CadenceVariesWithAcceptableGlitchTime) {
+  scoped_ptr<VideoCadenceEstimator> estimator(new VideoCadenceEstimator(
+      base::TimeDelta::FromSeconds(kMinimumAcceptableTimeBetweenGlitchesSecs)));
+  estimator->set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
+
+  const base::TimeDelta render_interval = Interval(NTSC(60));
+  const base::TimeDelta frame_interval = Interval(120);
+  const base::TimeDelta acceptable_drift = frame_interval / 2;
+
+  EXPECT_FALSE(estimator->UpdateCadenceEstimate(render_interval, frame_interval,
+                                                acceptable_drift));
+  EXPECT_FALSE(estimator->has_cadence());
+
+  // Decreasing the acceptable glitch time should be result in more permissive
+  // detection of cadence.
+  estimator.reset(new VideoCadenceEstimator(base::TimeDelta::FromSeconds(
+      kMinimumAcceptableTimeBetweenGlitchesSecs / 2)));
+  estimator->set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
+  EXPECT_TRUE(estimator->UpdateCadenceEstimate(render_interval, frame_interval,
+                                               acceptable_drift));
+  EXPECT_TRUE(estimator->has_cadence());
+  EXPECT_EQ(2, estimator->get_cadence_for_testing());
+}
+
+TEST(VideoCadenceEstimatorTest, CadenceHystersisPreventsOscillation) {
+  scoped_ptr<VideoCadenceEstimator> estimator(new VideoCadenceEstimator(
+      base::TimeDelta::FromSeconds(kMinimumAcceptableTimeBetweenGlitchesSecs)));
+
+  const base::TimeDelta render_interval = Interval(30);
+  const base::TimeDelta frame_interval = Interval(60);
+  const base::TimeDelta acceptable_drift = frame_interval / 2;
+  estimator->set_cadence_hysteresis_threshold_for_testing(render_interval * 2);
+
+  // Cadence hysteresis should prevent the cadence from taking effect yet.
+  EXPECT_FALSE(estimator->UpdateCadenceEstimate(render_interval, frame_interval,
+                                                acceptable_drift));
+  EXPECT_FALSE(estimator->has_cadence());
+
+  // A second call should exceed cadence hysteresis and take into effect.
+  EXPECT_TRUE(estimator->UpdateCadenceEstimate(render_interval, frame_interval,
+                                               acceptable_drift));
+  EXPECT_TRUE(estimator->has_cadence());
+
+  // One bad interval shouldn't cause cadence to drop
+  EXPECT_FALSE(estimator->UpdateCadenceEstimate(
+      render_interval, frame_interval * 0.75, acceptable_drift));
+  EXPECT_TRUE(estimator->has_cadence());
+
+  // Resumption of cadence should clear bad interval count.
+  EXPECT_FALSE(estimator->UpdateCadenceEstimate(render_interval, frame_interval,
+                                                acceptable_drift));
+  EXPECT_TRUE(estimator->has_cadence());
+
+  // So one more bad interval shouldn't cause cadence to drop
+  EXPECT_FALSE(estimator->UpdateCadenceEstimate(
+      render_interval, frame_interval * 0.75, acceptable_drift));
+  EXPECT_TRUE(estimator->has_cadence());
+
+  // Two bad intervals should.
+  EXPECT_TRUE(estimator->UpdateCadenceEstimate(
+      render_interval, frame_interval * 0.75, acceptable_drift));
+  EXPECT_FALSE(estimator->has_cadence());
+}
+
+}  // namespace media
diff --git a/media/filters/video_renderer_algorithm.cc b/media/filters/video_renderer_algorithm.cc
new file mode 100644
index 0000000..0a2bc57
--- /dev/null
+++ b/media/filters/video_renderer_algorithm.cc
@@ -0,0 +1,627 @@
+// 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_renderer_algorithm.h"
+
+#include <algorithm>
+#include <limits>
+
+namespace media {
+
+// The number of frames to store for moving average calculations.  Value picked
+// after experimenting with playback of various local media and YouTube clips.
+const int kMovingAverageSamples = 25;
+
+VideoRendererAlgorithm::ReadyFrame::ReadyFrame(
+    const scoped_refptr<VideoFrame>& ready_frame)
+    : frame(ready_frame),
+      ideal_render_count(0),
+      render_count(0),
+      drop_count(0) {
+}
+
+VideoRendererAlgorithm::ReadyFrame::~ReadyFrame() {
+}
+
+bool VideoRendererAlgorithm::ReadyFrame::operator<(
+    const ReadyFrame& other) const {
+  return frame->timestamp() < other.frame->timestamp();
+}
+
+VideoRendererAlgorithm::VideoRendererAlgorithm(
+    const TimeConverterCB& time_converter_cb)
+    : cadence_estimator_(base::TimeDelta::FromSeconds(
+          kMinimumAcceptableTimeBetweenGlitchesSecs)),
+      time_converter_cb_(time_converter_cb),
+      frame_duration_calculator_(kMovingAverageSamples),
+      frame_dropping_disabled_(false) {
+  DCHECK(!time_converter_cb_.is_null());
+  Reset();
+}
+
+VideoRendererAlgorithm::~VideoRendererAlgorithm() {
+}
+
+scoped_refptr<VideoFrame> VideoRendererAlgorithm::Render(
+    base::TimeTicks deadline_min,
+    base::TimeTicks deadline_max,
+    size_t* frames_dropped) {
+  DCHECK_LT(deadline_min, deadline_max);
+
+  if (frame_queue_.empty())
+    return nullptr;
+
+  if (frames_dropped)
+    *frames_dropped = 0;
+
+  // Once Render() is called |last_frame_index_| has meaning and should thus be
+  // preserved even if better frames come in before it due to out of order
+  // timestamps.
+  have_rendered_frames_ = true;
+
+  // Step 1: Update the current render interval for subroutines.
+  render_interval_ = deadline_max - deadline_min;
+
+  // Step 2: Figure out if any intervals have been skipped since the last call
+  // to Render().  If so, we assume the last frame provided was rendered during
+  // those intervals and adjust its render count appropriately.
+  AccountForMissedIntervals(deadline_min, deadline_max);
+  last_deadline_max_ = deadline_max;
+
+  // Step 3: Update the wall clock timestamps and frame duration estimates for
+  // all frames currently in the |frame_queue_|.
+  if (!UpdateFrameStatistics()) {
+    DVLOG(2) << "Failed to update frame statistics.";
+
+    ReadyFrame& ready_frame = frame_queue_[last_frame_index_];
+    DCHECK(ready_frame.frame);
+
+    // If duration is unknown, we don't have enough frames to make a good guess
+    // about which frame to use, so always choose the first.
+    if (average_frame_duration_ == base::TimeDelta() &&
+        !ready_frame.wall_clock_time.is_null()) {
+      ++ready_frame.render_count;
+    }
+
+    return ready_frame.frame;
+  }
+
+  DCHECK_GT(average_frame_duration_, base::TimeDelta());
+
+  base::TimeDelta selected_frame_drift;
+
+  // Step 4: Attempt to find the best frame by cadence.
+  int frame_to_render = FindBestFrameByCadence();
+  if (frame_to_render >= 0) {
+    selected_frame_drift =
+        CalculateAbsoluteDriftForFrame(deadline_min, frame_to_render);
+  }
+
+  // Step 5: If no frame could be found by cadence or the selected frame exceeds
+  // acceptable drift, try to find the best frame by coverage of the deadline.
+  if (frame_to_render < 0 || selected_frame_drift > max_acceptable_drift_) {
+    int second_best_by_coverage = -1;
+    const int best_by_coverage = FindBestFrameByCoverage(
+        deadline_min, deadline_max, &second_best_by_coverage);
+
+    // If the frame was previously selected based on cadence, we're only here
+    // because the drift is too large, so even if the cadence frame has the best
+    // coverage, fallback to the second best by coverage if it has better drift.
+    if (frame_to_render == best_by_coverage && second_best_by_coverage >= 0 &&
+        CalculateAbsoluteDriftForFrame(deadline_min, second_best_by_coverage) <=
+            selected_frame_drift) {
+      frame_to_render = second_best_by_coverage;
+    } else {
+      frame_to_render = best_by_coverage;
+    }
+
+    if (frame_to_render >= 0) {
+      selected_frame_drift =
+          CalculateAbsoluteDriftForFrame(deadline_min, frame_to_render);
+    }
+  }
+
+  // Step 6: If _still_ no frame could be found by coverage, try to choose the
+  // least crappy option based on the drift from the deadline. If we're here the
+  // selection is going to be bad because it means no suitable frame has any
+  // coverage of the deadline interval.
+  if (frame_to_render < 0 || selected_frame_drift > max_acceptable_drift_)
+    frame_to_render = FindBestFrameByDrift(deadline_min, &selected_frame_drift);
+
+  last_render_had_glitch_ = selected_frame_drift > max_acceptable_drift_;
+  DVLOG_IF(2, last_render_had_glitch_)
+      << "Frame drift is too far: " << selected_frame_drift.InMillisecondsF()
+      << "ms";
+
+  DCHECK_GE(frame_to_render, 0);
+
+  // Drop some debugging information if a frame had poor cadence.
+  if (cadence_estimator_.has_cadence()) {
+    const ReadyFrame& last_frame_info = frame_queue_[last_frame_index_];
+    if (static_cast<size_t>(frame_to_render) != last_frame_index_ &&
+        last_frame_info.render_count < last_frame_info.ideal_render_count) {
+      last_render_had_glitch_ = true;
+      DVLOG(2) << "Under-rendered frame " << last_frame_info.frame->timestamp()
+               << "; only " << last_frame_info.render_count
+               << " times instead of " << last_frame_info.ideal_render_count;
+    } else if (static_cast<size_t>(frame_to_render) == last_frame_index_ &&
+               last_frame_info.render_count >=
+                   last_frame_info.ideal_render_count) {
+      DVLOG(2) << "Over-rendered frame " << last_frame_info.frame->timestamp()
+               << "; rendered " << last_frame_info.render_count + 1
+               << " times instead of " << last_frame_info.ideal_render_count;
+      last_render_had_glitch_ = true;
+    }
+  }
+
+  // Step 7: Drop frames which occur prior to the frame to be rendered. If any
+  // frame has a zero render count it should be reported as dropped.
+  if (frame_to_render > 0) {
+    if (frames_dropped) {
+      for (int i = 0; i < frame_to_render; ++i) {
+        const ReadyFrame& frame = frame_queue_[i];
+        if (frame.render_count != frame.drop_count)
+          continue;
+
+        // If frame dropping is disabled, ignore the results of the algorithm
+        // and return the earliest unrendered frame.
+        if (frame_dropping_disabled_) {
+          frame_to_render = i;
+          break;
+        }
+
+        DVLOG(2) << "Dropping unrendered (or always dropped) frame "
+                 << frame.frame->timestamp()
+                 << ", wall clock: " << frame.wall_clock_time.ToInternalValue()
+                 << " (" << frame.render_count << ", " << frame.drop_count
+                 << ")";
+        ++(*frames_dropped);
+        if (!cadence_estimator_.has_cadence() || frame.ideal_render_count)
+          last_render_had_glitch_ = true;
+      }
+    }
+
+    frame_queue_.erase(frame_queue_.begin(),
+                       frame_queue_.begin() + frame_to_render);
+  }
+
+  if (last_render_had_glitch_) {
+    DVLOG(2) << "Deadline: [" << deadline_min.ToInternalValue() << ", "
+             << deadline_max.ToInternalValue()
+             << "], Interval: " << render_interval_.InMicroseconds()
+             << ", Duration: " << average_frame_duration_.InMicroseconds();
+  }
+
+  // Step 8: Congratulations, the frame selection gauntlet has been passed!
+  last_frame_index_ = 0;
+  ++frame_queue_.front().render_count;
+  DCHECK(frame_queue_.front().frame);
+  return frame_queue_.front().frame;
+}
+
+size_t VideoRendererAlgorithm::RemoveExpiredFrames(base::TimeTicks deadline) {
+  // Update |last_deadline_max_| if it's no longer accurate; this should always
+  // be done or EffectiveFramesQueued() may never expire the last frame.
+  if (deadline > last_deadline_max_)
+    last_deadline_max_ = deadline;
+
+  if (!UpdateFrameStatistics() || frame_queue_.size() < 2)
+    return 0;
+
+  DCHECK_GT(average_frame_duration_, base::TimeDelta());
+
+  // Finds and removes all frames which are too old to be used; I.e., the end of
+  // their render interval is further than |max_acceptable_drift_| from the
+  // given |deadline|.
+  size_t frames_to_expire = 0;
+  const base::TimeTicks minimum_frame_time =
+      deadline - max_acceptable_drift_ - average_frame_duration_;
+  for (; frames_to_expire < frame_queue_.size() - 1; ++frames_to_expire) {
+    if (frame_queue_[frames_to_expire].wall_clock_time >= minimum_frame_time)
+      break;
+  }
+
+  if (!frames_to_expire)
+    return 0;
+
+  frame_queue_.erase(frame_queue_.begin(),
+                     frame_queue_.begin() + frames_to_expire);
+
+  last_frame_index_ = last_frame_index_ > frames_to_expire
+                          ? last_frame_index_ - frames_to_expire
+                          : 0;
+  return frames_to_expire;
+}
+
+void VideoRendererAlgorithm::OnLastFrameDropped() {
+  DCHECK(have_rendered_frames_);
+  DCHECK(!frame_queue_.empty());
+  // If frames were expired by RemoveExpiredFrames() this count may be zero when
+  // the OnLastFrameDropped() call comes in.
+  if (!frame_queue_[last_frame_index_].render_count)
+    return;
+
+  ++frame_queue_[last_frame_index_].drop_count;
+  DCHECK_LE(frame_queue_[last_frame_index_].drop_count,
+            frame_queue_[last_frame_index_].render_count);
+}
+
+void VideoRendererAlgorithm::Reset() {
+  last_frame_index_ = 0;
+  have_rendered_frames_ = last_render_had_glitch_ = false;
+  last_deadline_max_ = base::TimeTicks();
+  average_frame_duration_ = render_interval_ = base::TimeDelta();
+  frame_queue_.clear();
+  cadence_estimator_.Reset();
+  frame_duration_calculator_.Reset();
+
+  // Default to ATSC IS/191 recommendations for maximum acceptable drift before
+  // we have enough frames to base the maximum on frame duration.
+  max_acceptable_drift_ = base::TimeDelta::FromMilliseconds(15);
+}
+
+size_t VideoRendererAlgorithm::EffectiveFramesQueued() const {
+  if (frame_queue_.empty() || average_frame_duration_ == base::TimeDelta() ||
+      last_deadline_max_.is_null()) {
+    return frame_queue_.size();
+  }
+
+  // If we don't have cadence, subtract off any frames which are before
+  // the last rendered frame or are past their expected rendering time.
+  if (!cadence_estimator_.has_cadence()) {
+    size_t expired_frames = last_frame_index_;
+    DCHECK_LT(last_frame_index_, frame_queue_.size());
+    for (; expired_frames < frame_queue_.size(); ++expired_frames) {
+      if (frame_queue_[expired_frames].wall_clock_time.is_null() ||
+          EndTimeForFrame(expired_frames) > last_deadline_max_) {
+        break;
+      }
+    }
+    return frame_queue_.size() - expired_frames;
+  }
+
+  // Find the first usable frame to start counting from.
+  const int start_index = FindBestFrameByCadenceInternal(nullptr);
+  if (start_index < 0)
+    return 0;
+
+  size_t renderable_frame_count = 0;
+  for (size_t i = start_index; i < frame_queue_.size(); ++i) {
+    if (frame_queue_[i].render_count < frame_queue_[i].ideal_render_count)
+      ++renderable_frame_count;
+  }
+
+  return renderable_frame_count;
+}
+
+void VideoRendererAlgorithm::EnqueueFrame(
+    const scoped_refptr<VideoFrame>& frame) {
+  DCHECK(frame);
+  DCHECK(!frame->end_of_stream());
+
+  ReadyFrame ready_frame(frame);
+  auto it = frame_queue_.empty() ? frame_queue_.end()
+                                 : std::lower_bound(frame_queue_.begin(),
+                                                    frame_queue_.end(), frame);
+  DCHECK_GE(it - frame_queue_.begin(), 0);
+
+  // If a frame was inserted before the first frame, update the index. On the
+  // next call to Render() it will be dropped.
+  if (static_cast<size_t>(it - frame_queue_.begin()) <= last_frame_index_ &&
+      have_rendered_frames_) {
+    ++last_frame_index_;
+  }
+
+  // The vast majority of cases should always append to the back, but in rare
+  // circumstance we get out of order timestamps, http://crbug.com/386551.
+  it = frame_queue_.insert(it, ready_frame);
+
+  // Project the current cadence calculations to include the new frame.  These
+  // may not be accurate until the next Render() call.  These updates are done
+  // to ensure EffectiveFramesQueued() returns a semi-reliable result.
+  if (cadence_estimator_.has_cadence())
+    UpdateCadenceForFrames();
+
+#ifndef NDEBUG
+  // Verify sorted order in debug mode.
+  for (size_t i = 0; i < frame_queue_.size() - 1; ++i) {
+    DCHECK(frame_queue_[i].frame->timestamp() <=
+           frame_queue_[i + 1].frame->timestamp());
+  }
+#endif
+}
+
+void VideoRendererAlgorithm::AccountForMissedIntervals(
+    base::TimeTicks deadline_min,
+    base::TimeTicks deadline_max) {
+  if (last_deadline_max_.is_null() || deadline_min <= last_deadline_max_ ||
+      !have_rendered_frames_) {
+    return;
+  }
+
+  DCHECK_GT(render_interval_, base::TimeDelta());
+  const int64 render_cycle_count =
+      (deadline_min - last_deadline_max_) / render_interval_;
+
+  // In the ideal case this value will be zero.
+  if (!render_cycle_count)
+    return;
+
+  DVLOG(2) << "Missed " << render_cycle_count << " Render() intervals.";
+
+  // Only update render count if the frame was rendered at all; it may not have
+  // been if the frame is at the head because we haven't rendered anything yet
+  // or because previous frames were removed via RemoveExpiredFrames().
+  ReadyFrame& ready_frame = frame_queue_[last_frame_index_];
+  if (!ready_frame.render_count)
+    return;
+
+  // If the frame was never really rendered since it was dropped each attempt,
+  // we need to increase the drop count as well to match the new render count.
+  // Otherwise we won't properly count the frame as dropped when it's discarded.
+  // We always update the render count so FindBestFrameByCadenceInternal() can
+  // properly account for potentially over-rendered frames.
+  if (ready_frame.render_count == ready_frame.drop_count)
+    ready_frame.drop_count += render_cycle_count;
+  ready_frame.render_count += render_cycle_count;
+}
+
+bool VideoRendererAlgorithm::UpdateFrameStatistics() {
+  // Figure out all current ready frame times at once so we minimize the drift
+  // relative to real time as the code below executes.
+  for (size_t i = 0; i < frame_queue_.size(); ++i) {
+    ReadyFrame& frame = frame_queue_[i];
+    const bool new_frame = frame.wall_clock_time.is_null();
+    frame.wall_clock_time = time_converter_cb_.Run(frame.frame->timestamp());
+
+    // If time stops or never started, exit immediately.
+    if (frame.wall_clock_time.is_null())
+      return false;
+
+    // TODO(dalecurtis): An unlucky tick of a playback rate change could cause
+    // this to skew so much that time goes backwards between calls.  Fix this by
+    // either converting all timestamps at once or with some retry logic.
+    if (i > 0) {
+      const base::TimeDelta delta =
+          frame.wall_clock_time - frame_queue_[i - 1].wall_clock_time;
+      CHECK_GT(delta, base::TimeDelta());
+      if (new_frame)
+        frame_duration_calculator_.AddSample(delta);
+    }
+  }
+
+  // Do we have enough frames to compute statistics?
+  const bool have_frame_duration = average_frame_duration_ != base::TimeDelta();
+  if (frame_queue_.size() < 2 && !have_frame_duration)
+    return false;
+
+  // Compute |average_frame_duration_|, a moving average of the last few frames;
+  // see kMovingAverageSamples for the exact number.
+  average_frame_duration_ = frame_duration_calculator_.Average();
+
+  // ITU-R BR.265 recommends a maximum acceptable drift of +/- half of the frame
+  // duration; there are other asymmetric, more lenient measures, that we're
+  // forgoing in favor of simplicity.
+  //
+  // We'll always allow at least 8.33ms of drift since literature suggests it's
+  // well below the floor of detection.
+  max_acceptable_drift_ = std::max(average_frame_duration_ / 2,
+                                   base::TimeDelta::FromSecondsD(1.0 / 120));
+
+  // If we were called via RemoveExpiredFrames() and Render() was never called,
+  // we may not have a render interval yet.
+  if (render_interval_ == base::TimeDelta())
+    return true;
+
+  const bool cadence_changed = cadence_estimator_.UpdateCadenceEstimate(
+      render_interval_, average_frame_duration_, max_acceptable_drift_);
+
+  // No need to update cadence if there's been no change; cadence will be set
+  // as frames are added to the queue.
+  if (!cadence_changed)
+    return true;
+
+  UpdateCadenceForFrames();
+
+  // Thus far there appears to be no need for special 3:2 considerations, the
+  // smoothness scores seem to naturally fit that pattern based on maximizing
+  // frame coverage.
+  return true;
+}
+
+void VideoRendererAlgorithm::UpdateCadenceForFrames() {
+  for (size_t i = last_frame_index_; i < frame_queue_.size(); ++i) {
+    // It's always okay to adjust the ideal render count, since the cadence
+    // selection method will still count its current render count towards
+    // cadence selection.
+    frame_queue_[i].ideal_render_count =
+        cadence_estimator_.has_cadence()
+            ? cadence_estimator_.GetCadenceForFrame(i - last_frame_index_)
+            : 0;
+  }
+}
+
+int VideoRendererAlgorithm::FindBestFrameByCadence() {
+  DCHECK(!frame_queue_.empty());
+  if (!cadence_estimator_.has_cadence())
+    return -1;
+
+  int new_ideal_render_count = 0;
+  const int best_frame =
+      FindBestFrameByCadenceInternal(&new_ideal_render_count);
+  if (best_frame < 0)
+    return -1;
+
+  DCHECK_GT(new_ideal_render_count, 0);
+  frame_queue_[best_frame].ideal_render_count = new_ideal_render_count;
+  return best_frame;
+}
+
+int VideoRendererAlgorithm::FindBestFrameByCadenceInternal(
+    int* adjusted_ideal_render_count) const {
+  DCHECK(!frame_queue_.empty());
+  DCHECK(cadence_estimator_.has_cadence());
+  const ReadyFrame& current_frame = frame_queue_[last_frame_index_];
+
+  // If the current frame is below cadence, we should prefer it.
+  if (current_frame.render_count < current_frame.ideal_render_count) {
+    if (adjusted_ideal_render_count)
+      *adjusted_ideal_render_count = current_frame.ideal_render_count;
+    return last_frame_index_;
+  }
+
+  // For over-rendered frames we need to ensure we skip frames and subtract
+  // each skipped frame's ideal cadence from the over-render count until we
+  // find a frame which still has a positive ideal render count.
+  int render_count_overage = std::max(
+      0, current_frame.render_count - current_frame.ideal_render_count);
+
+  // If the current frame is on cadence or over cadence, find the next frame
+  // with a positive ideal render count.
+  for (size_t i = last_frame_index_ + 1; i < frame_queue_.size(); ++i) {
+    const ReadyFrame& frame = frame_queue_[i];
+    if (frame.ideal_render_count > render_count_overage) {
+      if (adjusted_ideal_render_count) {
+        *adjusted_ideal_render_count =
+            frame.ideal_render_count - render_count_overage;
+      }
+      return i;
+    } else {
+      // The ideal render count should always be zero or smaller than the
+      // over-render count.
+      render_count_overage -= frame.ideal_render_count;
+      DCHECK_GE(render_count_overage, 0);
+    }
+  }
+
+  // We don't have enough frames to find a better once by cadence.
+  return -1;
+}
+
+int VideoRendererAlgorithm::FindBestFrameByCoverage(
+    base::TimeTicks deadline_min,
+    base::TimeTicks deadline_max,
+    int* second_best) const {
+  DCHECK(!frame_queue_.empty());
+
+  // Find the frame which covers the most of the interval [deadline_min,
+  // deadline_max]. Frames outside of the interval are considered to have no
+  // coverage, while those which completely overlap the interval have complete
+  // coverage.
+  int best_frame_by_coverage = -1;
+  base::TimeDelta best_coverage;
+  std::vector<base::TimeDelta> coverage(frame_queue_.size(), base::TimeDelta());
+  for (size_t i = last_frame_index_; i < frame_queue_.size(); ++i) {
+    // Frames which start after the deadline interval have zero coverage.
+    if (frame_queue_[i].wall_clock_time > deadline_max)
+      break;
+
+    // Clamp frame end times to a maximum of |deadline_max|.
+    const base::TimeTicks frame_end_time =
+        std::min(deadline_max, EndTimeForFrame(i));
+
+    // Frames entirely before the deadline interval have zero coverage.
+    if (frame_end_time < deadline_min)
+      continue;
+
+    // If we're here, the current frame overlaps the deadline in some way; so
+    // compute the duration of the interval which is covered.
+    const base::TimeDelta duration =
+        frame_end_time -
+        std::max(deadline_min, frame_queue_[i].wall_clock_time);
+
+    coverage[i] = duration;
+    if (coverage[i] > best_coverage) {
+      best_frame_by_coverage = i;
+      best_coverage = coverage[i];
+    }
+  }
+
+  // Find the second best frame by coverage; done by zeroing the coverage for
+  // the previous best and recomputing the maximum.
+  *second_best = -1;
+  if (best_frame_by_coverage >= 0) {
+    coverage[best_frame_by_coverage] = base::TimeDelta();
+    auto it = std::max_element(coverage.begin(), coverage.end());
+    if (*it > base::TimeDelta())
+      *second_best = it - coverage.begin();
+  }
+
+  // If two frames have coverage within half a millisecond, prefer the earliest
+  // frame as having the best coverage.  Value chosen via experimentation to
+  // ensure proper coverage calculation for 24fps in 60Hz where +/- 100us of
+  // jitter is present within the |render_interval_|. At 60Hz this works out to
+  // an allowed jitter of 3%.
+  const base::TimeDelta kAllowableJitter =
+      base::TimeDelta::FromMicroseconds(500);
+  if (*second_best >= 0 && best_frame_by_coverage > *second_best &&
+      (best_coverage - coverage[*second_best]).magnitude() <=
+          kAllowableJitter) {
+    std::swap(best_frame_by_coverage, *second_best);
+  }
+
+  // TODO(dalecurtis): We may want to make a better decision about what to do
+  // when multiple frames have equivalent coverage over an interval.  Jitter in
+  // the render interval may result in irregular frame selection which may be
+  // visible to a viewer.
+  //
+  // 23.974fps and 24fps in 60Hz are the most common susceptible rates, so
+  // extensive tests have been added to ensure these cases work properly.
+
+  return best_frame_by_coverage;
+}
+
+int VideoRendererAlgorithm::FindBestFrameByDrift(
+    base::TimeTicks deadline_min,
+    base::TimeDelta* selected_frame_drift) const {
+  DCHECK(!frame_queue_.empty());
+
+  int best_frame_by_drift = -1;
+  *selected_frame_drift = base::TimeDelta::Max();
+
+  for (size_t i = last_frame_index_; i < frame_queue_.size(); ++i) {
+    const base::TimeDelta drift =
+        CalculateAbsoluteDriftForFrame(deadline_min, i);
+    // We use <= here to prefer the latest frame with minimum drift.
+    if (drift <= *selected_frame_drift) {
+      *selected_frame_drift = drift;
+      best_frame_by_drift = i;
+    }
+  }
+
+  return best_frame_by_drift;
+}
+
+base::TimeDelta VideoRendererAlgorithm::CalculateAbsoluteDriftForFrame(
+    base::TimeTicks deadline_min,
+    int frame_index) const {
+  // If the frame lies before the deadline, compute the delta against the end
+  // of the frame's duration.
+  const base::TimeTicks frame_end_time = EndTimeForFrame(frame_index);
+  if (frame_end_time < deadline_min)
+    return deadline_min - frame_end_time;
+
+  // If the frame lies after the deadline, compute the delta against the frame's
+  // wall clock time.
+  const ReadyFrame& frame = frame_queue_[frame_index];
+  if (frame.wall_clock_time > deadline_min)
+    return frame.wall_clock_time - deadline_min;
+
+  // Drift is zero for frames which overlap the deadline interval.
+  DCHECK_GE(deadline_min, frame.wall_clock_time);
+  DCHECK_GE(frame_end_time, deadline_min);
+  return base::TimeDelta();
+}
+
+base::TimeTicks VideoRendererAlgorithm::EndTimeForFrame(
+    size_t frame_index) const {
+  DCHECK_LT(frame_index, frame_queue_.size());
+  DCHECK_GT(average_frame_duration_, base::TimeDelta());
+  return frame_index + 1 < frame_queue_.size()
+             ? frame_queue_[frame_index + 1].wall_clock_time
+             : frame_queue_[frame_index].wall_clock_time +
+                   average_frame_duration_;
+}
+
+}  // namespace media
diff --git a/media/filters/video_renderer_algorithm.h b/media/filters/video_renderer_algorithm.h
new file mode 100644
index 0000000..83276e7
--- /dev/null
+++ b/media/filters/video_renderer_algorithm.h
@@ -0,0 +1,285 @@
+// 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.
+
+#ifndef MEDIA_FILTERS_VIDEO_RENDERER_ALGORITHM_H_
+#define MEDIA_FILTERS_VIDEO_RENDERER_ALGORITHM_H_
+
+#include <deque>
+
+#include "base/callback.h"
+#include "base/memory/ref_counted.h"
+#include "base/time/time.h"
+#include "media/base/media_export.h"
+#include "media/base/moving_average.h"
+#include "media/base/video_frame.h"
+#include "media/base/video_renderer.h"
+#include "media/filters/video_cadence_estimator.h"
+
+namespace media {
+
+// VideoRendererAlgorithm manages a queue of VideoFrames from which it chooses
+// frames with the goal of providing a smooth playback experience.  I.e., the
+// selection process results in the best possible uniformity for displayed frame
+// durations over time.
+//
+// Clients will provide frames to VRA via EnqueueFrame() and then VRA will yield
+// one of those frames in response to a future Render() call.  Each Render()
+// call takes a render interval which is used to compute the best frame for
+// display during that interval.
+//
+// Render() calls are expected to happen on a regular basis.  Failure to do so
+// will result in suboptimal rendering experiences.  If a client knows that
+// Render() callbacks are stalled for any reason, it should tell VRA to expire
+// frames which are unusable via RemoveExpiredFrames(); this prevents useless
+// accumulation of stale VideoFrame objects (which are frequently quite large).
+//
+// The primary means of smooth frame selection is via forced integer cadence,
+// see VideoCadenceEstimator for details on this process.  In cases of non-
+// integer cadence, the algorithm will fall back to choosing the frame which
+// covers the most of the current render interval.  If no frame covers the
+// current interval, the least bad frame will be chosen based on its drift from
+// the start of the interval.
+//
+// Combined these three approaches enforce optimal smoothness in many cases.
+class MEDIA_EXPORT VideoRendererAlgorithm {
+ public:
+  // Used to convert a media timestamp into wall clock time.
+  using TimeConverterCB = base::Callback<base::TimeTicks(base::TimeDelta)>;
+
+  explicit VideoRendererAlgorithm(const TimeConverterCB& time_converter_cb);
+  ~VideoRendererAlgorithm();
+
+  // Chooses the best frame for the interval [deadline_min, deadline_max] based
+  // on available and previously rendered frames.
+  //
+  // Under ideal circumstances the deadline interval provided to a Render() call
+  // should be directly adjacent to the deadline given to the previous Render()
+  // call with no overlap or gaps.  In practice, |deadline_max| is an estimated
+  // value, which means the next |deadline_min| may overlap it slightly or have
+  // a slight gap.  Gaps which exceed the length of the deadline interval are
+  // assumed to be repeated frames for the purposes of cadence detection.
+  //
+  // If provided, |frames_dropped| will be set to the number of frames which
+  // were removed from |frame_queue_|, during this call, which were never
+  // returned during a previous Render() call and are no longer suitable for
+  // rendering since their wall clock time is too far in the past.
+  scoped_refptr<VideoFrame> Render(base::TimeTicks deadline_min,
+                                   base::TimeTicks deadline_max,
+                                   size_t* frames_dropped);
+
+  // Removes all video frames which are unusable since their ideal render
+  // interval [timestamp, timestamp + duration] is too far away from
+  // |deadline_min| than is allowed by drift constraints.
+  //
+  // At least one frame will always remain after this call so that subsequent
+  // Render() calls have a frame to return if no new frames are enqueued before
+  // then.  Returns the number of frames removed.
+  //
+  // Note: In cases where there is no known frame duration (i.e. perhaps a video
+  // with only a single frame), the last frame can not be expired, regardless of
+  // the given deadline.  Clients must handle this case externally.
+  size_t RemoveExpiredFrames(base::TimeTicks deadline);
+
+  // Clients should call this if the last frame provided by Render() was never
+  // rendered; it ensures the presented cadence matches internal models.  This
+  // must be called before the next Render() call.
+  void OnLastFrameDropped();
+
+  // Adds a frame to |frame_queue_| for consideration by Render().  Out of order
+  // timestamps will be sorted into appropriate order.  Do not enqueue end of
+  // stream frames.  Frames inserted prior to the last rendered frame will not
+  // be used.  They will be discarded on the next call to Render(), counting as
+  // dropped frames, or by RemoveExpiredFrames(), counting as expired frames.
+  void EnqueueFrame(const scoped_refptr<VideoFrame>& frame);
+
+  // Removes all frames from the |frame_queue_| and clears predictors.  The
+  // algorithm will be as if freshly constructed after this call.
+  void Reset();
+
+  // Returns the number of frames currently buffered which could be rendered
+  // assuming current Render() interval trends.  Before Render() is called, this
+  // will be the same as the number of frames given to EnqueueFrame().  After
+  // Render() has been called, one of two things will be returned:
+  //
+  // If a cadence has been identified, this will return the number of frames
+  // which have a non-zero ideal render count.
+  //
+  // If cadence has not been identified, this will return the number of frames
+  // which have a frame end time greater than the end of the last render
+  // interval passed to Render().  Note: If Render() callbacks become suspended
+  // and the duration is unknown the last frame may never be stop counting as
+  // effective.  Clients must handle this case externally.
+  //
+  // In either case, frames enqueued before the last displayed frame will not
+  // be counted as effective.
+  size_t EffectiveFramesQueued() const;
+
+  size_t frames_queued() const { return frame_queue_.size(); }
+
+  // Returns the average of the duration of all frames in |frame_queue_|
+  // as measured in wall clock (not media) time.
+  base::TimeDelta average_frame_duration() const {
+    return average_frame_duration_;
+  }
+
+  // Method used for testing which disables frame dropping, in this mode the
+  // algorithm will never drop frames and instead always return every frame
+  // for display at least once.
+  void disable_frame_dropping() { frame_dropping_disabled_ = true; }
+
+ private:
+  friend class VideoRendererAlgorithmTest;
+
+  // The determination of whether to clamp to a given cadence is based on the
+  // number of seconds before a frame would have to be dropped or repeated to
+  // compensate for reaching the maximum acceptable drift.
+  //
+  // We've chosen 8 seconds based on practical observations and the fact that it
+  // allows 29.9fps and 59.94fps in 60Hz and vice versa.
+  //
+  // Most users will not be able to see a single frame repeated or dropped every
+  // 8 seconds and certainly should notice it less than the randomly variable
+  // frame durations.
+  static const int kMinimumAcceptableTimeBetweenGlitchesSecs = 8;
+
+  // Metadata container for enqueued frames.  See |frame_queue_| below.
+  struct ReadyFrame {
+    ReadyFrame(const scoped_refptr<VideoFrame>& frame);
+    ~ReadyFrame();
+
+    // For use with std::lower_bound.
+    bool operator<(const ReadyFrame& other) const;
+
+    scoped_refptr<VideoFrame> frame;
+    base::TimeTicks wall_clock_time;
+    int ideal_render_count;
+    int render_count;
+    int drop_count;
+  };
+
+  // Updates the render count for the last rendered frame based on the number
+  // of missing intervals between Render() calls.
+  void AccountForMissedIntervals(base::TimeTicks deadline_min,
+                                 base::TimeTicks deadline_max);
+
+  // Updates the render count and wall clock timestamps for all frames in
+  // |frame_queue_|. Returns false if statistics can't be updated at this time;
+  // which occurs if media time has stopped or there are not enough frames to
+  // calculate an average frame duration.  Updates |cadence_estimator_|.
+  //
+  // Note: Wall clock time is recomputed each Render() call because it's
+  // expected that the TimeSource powering TimeConverterCB will skew slightly
+  // based on the audio clock.
+  //
+  // TODO(dalecurtis): Investigate how accurate we need the wall clock times to
+  // be, so we can avoid recomputing every time (we would need to recompute when
+  // playback rate changes occur though).
+  bool UpdateFrameStatistics();
+
+  // Updates the ideal render count for all frames in |frame_queue_| based on
+  // the cadence returned by |cadence_estimator_|.
+  void UpdateCadenceForFrames();
+
+  // If |cadence_estimator_| has detected a valid cadence, attempts to find the
+  // next frame which should be rendered.  Returns -1 if not enough frames are
+  // available for cadence selection or there is no cadence.  Will adjust the
+  // selected frame's ideal render count if the last rendered frame has been
+  // over selected.
+  int FindBestFrameByCadence();
+
+  // Similar to FindBestFrameByCadence(), but instead of adjusting the last
+  // rendered frame's ideal render count in the case of over selection,
+  // optionally returns the new ideal render count via
+  // |adjusted_ideal_render_count|.
+  int FindBestFrameByCadenceInternal(int* adjusted_ideal_render_count) const;
+
+  // Iterates over |frame_queue_| and finds the frame which covers the most of
+  // the deadline interval.  If multiple frames have coverage of the interval,
+  // |second_best| will be set to the index of the frame with the next highest
+  // coverage.  Returns -1 if no frame has any coverage of the current interval.
+  //
+  // Prefers the earliest frame if multiple frames have similar coverage (within
+  // a few percent of each other).
+  int FindBestFrameByCoverage(base::TimeTicks deadline_min,
+                              base::TimeTicks deadline_max,
+                              int* second_best) const;
+
+  // Iterates over |frame_queue_| and find the frame which drifts the least from
+  // |deadline_min|.  There's always a best frame by drift, so the return value
+  // is always a valid frame index.  |selected_frame_drift| will be set to the
+  // drift of the chosen frame.
+  //
+  // Note: Drift calculations assume contiguous frames in the time domain, so
+  // it's not possible to have a case where a frame is -10ms from |deadline_min|
+  // and another frame which is at some time after |deadline_min|.  The second
+  // frame would be considered to start at -10ms before |deadline_min| and would
+  // overlap |deadline_min|, so its drift would be zero.
+  int FindBestFrameByDrift(base::TimeTicks deadline_min,
+                           base::TimeDelta* selected_frame_drift) const;
+
+  // Calculates the drift from |deadline_min| for the given |frame_index|.  If
+  // the [wall_clock_time, wall_clock_time + average_frame_duration_] lies
+  // before |deadline_min| the drift is the delta between |deadline_min| and
+  // |wall_clock_time + average_frame_duration_|. If the frame overlaps
+  // |deadline_min| the drift is zero. If the frame lies after |deadline_min|
+  // the drift is the delta between |deadline_min| and |wall_clock_time|.
+  base::TimeDelta CalculateAbsoluteDriftForFrame(base::TimeTicks deadline_min,
+                                                 int frame_index) const;
+
+  // Returns the wall clock time of the next frame if it exists, otherwise it
+  // returns the time of the requested frame plus |average_frame_duration_|.
+  base::TimeTicks EndTimeForFrame(size_t frame_index) const;
+
+  // Queue of incoming frames waiting for rendering.
+  using VideoFrameQueue = std::deque<ReadyFrame>;
+  VideoFrameQueue frame_queue_;
+
+  // The index of the last frame rendered; presumed to be the first frame if no
+  // frame has been rendered yet. Updated by Render() and EnqueueFrame() if any
+  // frames are added or removed.
+  //
+  // In most cases this value is zero, but when out of order timestamps are
+  // present, the last rendered frame may be moved.
+  size_t last_frame_index_;
+
+  // Handles cadence detection and frame cadence assignments.
+  VideoCadenceEstimator cadence_estimator_;
+
+  // Indicates if any calls to Render() have successfully yielded a frame yet.
+  bool have_rendered_frames_;
+
+  // Callback used to convert media timestamps into wall clock timestamps.
+  const TimeConverterCB time_converter_cb_;
+
+  // The last |deadline_max| provided to Render(), used to predict whether
+  // frames were rendered over cadence between Render() calls.
+  base::TimeTicks last_deadline_max_;
+
+  // The average of the duration of all frames in |frame_queue_| as measured in
+  // wall clock (not media) time at the time of the last Render().
+  MovingAverage frame_duration_calculator_;
+  base::TimeDelta average_frame_duration_;
+
+  // The length of the last deadline interval given to Render(), updated at the
+  // start of Render().
+  base::TimeDelta render_interval_;
+
+  // The maximum acceptable drift before a frame can no longer be considered for
+  // rendering within a given interval.
+  base::TimeDelta max_acceptable_drift_;
+
+  // Indicates that the last call to Render() experienced a rendering glitch; it
+  // may have: under-rendered a frame, over-rendered a frame, dropped one or
+  // more frames, or chosen a frame which exceeded acceptable drift.
+  bool last_render_had_glitch_;
+
+  // For testing functionality which enables clockless playback of all frames.
+  bool frame_dropping_disabled_;
+
+  DISALLOW_COPY_AND_ASSIGN(VideoRendererAlgorithm);
+};
+
+}  // namespace media
+
+#endif  // MEDIA_FILTERS_VIDEO_RENDERER_ALGORITHM_H_
diff --git a/media/filters/video_renderer_algorithm_unittest.cc b/media/filters/video_renderer_algorithm_unittest.cc
new file mode 100644
index 0000000..9082d26
--- /dev/null
+++ b/media/filters/video_renderer_algorithm_unittest.cc
@@ -0,0 +1,1091 @@
+// 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_.set_cadence_hysteresis_threshold_for_testing(
+        base::TimeDelta());
+  }
+
+  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(RenderAndStep(&display_tg, &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_;
+  }
+
+  scoped_refptr<VideoFrame> RenderAndStep(TickGenerator* tg,
+                                          size_t* frames_dropped) {
+    const base::TimeTicks start = tg->current();
+    const base::TimeTicks end = tg->step();
+    return algorithm_.Render(start, end, frames_dropped);
+  }
+
+  // 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 equal to
+      // the number of usable frames; i.e. those frames whose end time was not
+      // within the last render interval.
+      if (!is_using_cadence() || !frames_queued() ||
+          GetCurrentFrameDisplayCount() < GetCurrentFrameIdealDisplayCount()) {
+        ASSERT_EQ(GetUsableFrameCount(deadline_max),
+                  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 AccountForMissedIntervalsAndStep(TickGenerator* tg) {
+    const base::TimeTicks start = tg->current();
+    const base::TimeTicks end = tg->step();
+    return AccountForMissedIntervals(start, end);
+  }
+
+  int AccountForMissedIntervals(base::TimeTicks deadline_min,
+                                base::TimeTicks deadline_max) {
+    algorithm_.AccountForMissedIntervals(deadline_min, deadline_max);
+    return frames_queued() ? GetCurrentFrameDisplayCount() : -1;
+  }
+
+  size_t GetUsableFrameCount(base::TimeTicks deadline_max) {
+    if (is_using_cadence())
+      return frames_queued();
+
+    for (size_t i = 0; i < frames_queued(); ++i)
+      if (algorithm_.EndTimeForFrame(i) > deadline_max)
+        return frames_queued() - i;
+    return 0;
+  }
+
+ 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(RenderAndStep(&tg, &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, AccountForMissedIntervalsAndStep(&tg));
+
+  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, AccountForMissedIntervalsAndStep(&tg));
+
+  // 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, AccountForMissedIntervalsAndStep(&tg));
+
+  // 4 because [tg.current(), tg.step()] now represents 2 additional intervals.
+  EXPECT_EQ(4, AccountForMissedIntervalsAndStep(&tg));
+
+  // Frame should be way over cadence and no good frames remain, so last frame
+  // should be returned.
+  frame = RenderAndStep(&tg, &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 = RenderAndStep(&display_tg, &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 = RenderAndStep(&display_tg, &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 = RenderAndStep(&display_tg, &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 = RenderAndStep(&display_tg, &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 = RenderAndStep(&display_tg, &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, frames_queued());
+
+  // Render one frame which will detect cadence...
+  size_t frames_dropped = 0;
+  scoped_refptr<VideoFrame> frame = RenderAndStep(&display_tg, &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, 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());
+}
+
+TEST_F(VideoRendererAlgorithmTest, EffectiveFramesQueuedWithoutCadence) {
+  TickGenerator tg(tick_clock_->NowTicks(), 60);
+
+  EXPECT_EQ(0u, algorithm_.EffectiveFramesQueued());
+  time_source_.StartTicking();
+
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(0)));
+  EXPECT_EQ(1u, algorithm_.EffectiveFramesQueued());
+
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(1)));
+  EXPECT_EQ(2u, algorithm_.EffectiveFramesQueued());
+
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(2)));
+  EXPECT_EQ(3u, algorithm_.EffectiveFramesQueued());
+
+  algorithm_.EnqueueFrame(CreateFrame(tg.interval(3)));
+  EXPECT_EQ(4u, algorithm_.EffectiveFramesQueued());
+  EXPECT_EQ(4u, frames_queued());
+
+  // Issue a render call that should drop the first two frames and mark the 3rd
+  // as consumed.
+  tg.step(2);
+  size_t frames_dropped = 0;
+  scoped_refptr<VideoFrame> frame = RenderAndStep(&tg, &frames_dropped);
+  ASSERT_FALSE(is_using_cadence());
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(2u, frames_dropped);
+  EXPECT_EQ(tg.interval(2), frame->timestamp());
+  EXPECT_EQ(1u, algorithm_.EffectiveFramesQueued());
+  EXPECT_EQ(2u, frames_queued());
+
+  // Rendering one more frame should return 0 effective frames queued.
+  frame = RenderAndStep(&tg, &frames_dropped);
+  ASSERT_FALSE(is_using_cadence());
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(0u, frames_dropped);
+  EXPECT_EQ(tg.interval(3), frame->timestamp());
+  EXPECT_EQ(0u, algorithm_.EffectiveFramesQueued());
+  EXPECT_EQ(1u, frames_queued());
+}
+
+// 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(RenderAndStep(&tg, &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(RenderAndStep(&tg, &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 = RenderAndStep(&tg, &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 = RenderAndStep(&tg, &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 = RenderAndStep(&tg, &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(1), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+  EXPECT_EQ(1u, frames_queued());
+  EXPECT_EQ(0u, 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 = RenderAndStep(&tg, &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 = RenderAndStep(&tg, &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 = RenderAndStep(&tg, &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 =
+        RenderAndStep(&display_tg, &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 = RenderAndStep(&display_tg, &frames_dropped);
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(frame_tg.interval(2), frame->timestamp());
+  EXPECT_EQ(0u, frames_dropped);
+  ASSERT_EQ(1, GetCurrentFrameIdealDisplayCount());
+
+  frame = RenderAndStep(&display_tg, &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 = RenderAndStep(&tg, &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 = RenderAndStep(&tg, &frames_dropped);
+  EXPECT_EQ(1u, frames_dropped);
+  EXPECT_EQ(2u, frames_queued());
+  EXPECT_EQ(1u, algorithm_.EffectiveFramesQueued());
+  ASSERT_TRUE(frame);
+  EXPECT_EQ(tg.interval(3), frame->timestamp());
+
+  // Advance expiry enough that one frame is removed, but one remains and is
+  // still counted as effective.
+  ASSERT_EQ(
+      1u, algorithm_.RemoveExpiredFrames(tg.current() + tg.interval(1) * 0.75));
+  EXPECT_EQ(1u, frames_queued());
+  EXPECT_EQ(1u, algorithm_.EffectiveFramesQueued());
+
+  // Advancing expiry once more should mark the frame as ineffective.
+  tg.step();
+  ASSERT_EQ(0u, algorithm_.RemoveExpiredFrames(tg.current()));
+  EXPECT_EQ(1u, frames_queued());
+  EXPECT_EQ(0u, algorithm_.EffectiveFramesQueued());
+}
+
+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): Is there more 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;
+    RenderAndStep(&display_tg, &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
diff --git a/media/media.gyp b/media/media.gyp
index dac02a3..c25e9de 100644
--- a/media/media.gyp
+++ b/media/media.gyp
@@ -330,6 +330,8 @@
         'base/media_switches.cc',
         'base/media_switches.h',
         'base/media_win.cc',
+        'base/moving_average.cc',
+        'base/moving_average.h',
         'base/multi_channel_resampler.cc',
         'base/multi_channel_resampler.h',
         'base/null_video_sink.cc',
@@ -478,6 +480,10 @@
         'filters/source_buffer_stream.h',
         'filters/stream_parser_factory.cc',
         'filters/stream_parser_factory.h',
+        'filters/video_cadence_estimator.cc',
+        'filters/video_cadence_estimator.h',
+        'filters/video_renderer_algorithm.cc',
+        'filters/video_renderer_algorithm.h',
         'filters/vp8_bool_decoder.cc',
         'filters/vp8_bool_decoder.h',
         'filters/vp8_parser.cc',
@@ -1162,6 +1168,7 @@
         'base/key_systems_unittest.cc',
         'base/mac/video_frame_mac_unittests.cc',
         'base/media_file_checker_unittest.cc',
+        'base/moving_average_unittest.cc',
         'base/multi_channel_resampler_unittest.cc',
         'base/null_video_sink_unittest.cc',
         'base/pipeline_unittest.cc',
@@ -1213,8 +1220,10 @@
         'filters/in_memory_url_protocol_unittest.cc',
         'filters/jpeg_parser_unittest.cc',
         'filters/source_buffer_stream_unittest.cc',
+        'filters/video_cadence_estimator_unittest.cc',
         'filters/video_decoder_selector_unittest.cc',
         'filters/video_frame_stream_unittest.cc',
+        'filters/video_renderer_algorithm_unittest.cc',
         'filters/vp8_bool_decoder_unittest.cc',
         'filters/vp8_parser_unittest.cc',
         'formats/common/offset_byte_queue_unittest.cc',