Introduce cadence based VideoRendererAlgorithm.

media/filters/video_renderer_algorithm.cc

+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "media/filters/video_renderer_algorithm.h"
+
+#include <algorithm>
+#include <limits>
+
+namespace media {
+
+enum FrameSelector { NONE, CADENCE, COVERAGE, DRIFT };
+
+VideoRendererAlgorithm::ReadyFrame::ReadyFrame(
+    const scoped_refptr<VideoFrame>& ready_frame)
+    : frame(ready_frame),
+      media_timestamp(ready_frame->timestamp()),
+      ideal_render_count(0),
+      render_count(0) {
+}
+
+VideoRendererAlgorithm::ReadyFrame::~ReadyFrame() {
+}
+
+bool VideoRendererAlgorithm::ReadyFrame::operator<(
+    const ReadyFrame& other) const {
+  return media_timestamp < other.media_timestamp;
+}
+
+VideoRendererAlgorithm::VideoRendererAlgorithm(
+    const TimeConverterCB& time_converter_cb)
+    : time_converter_cb_(time_converter_cb) {
+  Reset();
+}
+
+VideoRendererAlgorithm::~VideoRendererAlgorithm() {
+}
+
+scoped_refptr<VideoFrame> VideoRendererAlgorithm::Render(
+    base::TimeTicks deadline_min,
+    base::TimeTicks deadline_max,
+    int* frames_dropped) {
+  DCHECK(deadline_min < deadline_max);
+
+  if (frame_queue_.empty())
+    return nullptr;
+
+  // 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);
+
+  // 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.";
+    DCHECK(frame_queue_[last_frame_index_].frame);
+    return frame_queue_[last_frame_index_].frame;
+  }
+
+  FrameSelector frame_selector = NONE;

[xhwang, 2015/04/17 06:18:32]

This is set but not used for anything?

[DaleCurtis, 2015/04/18 01:29:21]

Was used for debug logs, removed.

+  base::TimeDelta selected_frame_drift;
+
+  // Step 4: Attempt to find the best frame by cadence.
+  int frame_to_render = -1;
+  if (ideal_cadence_) {
+    frame_selector = CADENCE;
+    frame_to_render = FindBestFrameByCadence();
+
+    if (frame_to_render >= 0) {
+      selected_frame_drift =
+          CalculateDriftForFrame(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_) {
+    frame_selector = COVERAGE;
+    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 &&
+        CalculateDriftForFrame(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 =
+          CalculateDriftForFrame(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_selector = DRIFT;
+    frame_to_render = FindBestFrameByDrift(deadline_min);
+    selected_frame_drift =
+        CalculateDriftForFrame(deadline_min, frame_to_render);
+  }
+
+  last_render_had_glitch_ = selected_frame_drift > max_acceptable_drift_;
+  if (last_render_had_glitch_) {
+    DVLOG(2) << "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 (ideal_cadence_) {
+    const ReadyFrame& last_frame_info = frame_queue_[last_frame_index_];
+    if (frame_to_render != last_frame_index_ &&
+        last_frame_info.render_count < last_frame_info.ideal_render_count) {
+      last_render_had_glitch_ = true;
+      DVLOG(2) << "Underdisplayed frame " << last_frame_info.media_timestamp
+               << "; only " << last_frame_info.render_count
+               << " times instead of " << last_frame_info.ideal_render_count;
+    } else if (frame_to_render == last_frame_index_ &&
+               last_frame_info.render_count >=
+                   last_frame_info.ideal_render_count) {
+      DVLOG(2) << "Overdisplayed frame " << last_frame_info.media_timestamp
+               << "; displayed " << 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) {
+        if (!frame_queue_[i].render_count) {
+          DVLOG(2) << "Dropping undisplayed frame "
+                   << frame_queue_[i].media_timestamp;
+          ++(*frames_dropped);
+          if (!fractional_cadence_)
+            last_render_had_glitch_ = true;
+        }
+      }
+    }
+
+    frame_queue_.erase(frame_queue_.begin(),
+                       frame_queue_.begin() + frame_to_render);
+  }
+
+  // Step 8: Congratulations, the frame selection guantlet has been passed!
+  last_frame_index_ = 0;
+  ++frame_queue_.front().render_count;
+  DCHECK(frame_queue_.front().frame);
+  return frame_queue_.front().frame;
+}
+
+int VideoRendererAlgorithm::RemoveExpiredFrames(base::TimeTicks deadline_min) {
+  if (!UpdateFrameStatistics() || frame_duration_ == base::TimeDelta())
+    return 0;
+
+  DCHECK_GE(frame_queue_.size(), 2u);
+
+  // Finds and removes all frames which are too old to be used; I.e., the end of
+  // their display interval is further than |max_acceptable_drift_| from the
+  // given |deadline_min|.
+  int frames_to_expire = 0;
+  const base::TimeTicks mininum_frame_time =
+      deadline_min - max_acceptable_drift_ - frame_duration_;
+  for (; static_cast<size_t>(frames_to_expire) < frame_queue_.size() - 1;
+       ++frames_to_expire) {
+    if (frame_queue_[frames_to_expire].wall_clock_time >= mininum_frame_time)
+      break;
+  }
+
+  if (!frames_to_expire)
+    return 0;
+
+  frame_queue_.erase(frame_queue_.begin(),
+                     frame_queue_.begin() + frames_to_expire);
+
+  last_frame_index_ = std::max(0, last_frame_index_ - frames_to_expire);
+  return frames_to_expire;
+}
+
+void VideoRendererAlgorithm::OnLastFrameDropped() {
+  DCHECK(!frame_queue_.empty());
+
+  // We only care if the frame was never rendered at all; otherwise we assume
+  // that the frame was redisplayed even if the renderer was told otherwise.
+  if (frame_queue_[last_frame_index_].render_count == 1)
+    frame_queue_[last_frame_index_].render_count = 0;
+}
+
+void VideoRendererAlgorithm::Reset() {
+  last_frame_index_ = ideal_cadence_ = fractional_cadence_ = 0;
+  last_detected_cadence_ = render_intervals_cadence_held_ = 0;
+  have_rendered_frames_ = last_render_had_glitch_ = false;
+  cadence_hysteresis_enabled_ = true;
+  last_deadline_max_ = base::TimeTicks();
+  frame_duration_ = render_interval_ = base::TimeDelta();
+  frame_queue_.clear();
+
+  // Default to ATSC IS/191 recommendations for maximum acceptable drift before
+  // we have enough frames to base the the maximum on frame duration.
+  max_acceptable_drift_ = base::TimeDelta::FromMilliseconds(15);
+}
+
+size_t VideoRendererAlgorithm::EffectiveFramesQueued() const {
+  if (!have_rendered_frames_ || !ideal_cadence_)
+    return frame_queue_.size();
+
+  size_t renderable_frame_count = 0;
+  for (size_t i = last_frame_index_; i < frame_queue_.size(); ++i) {
+    if (frame_queue_[i].ideal_render_count > 0)
+      ++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);
+
+  // If a frame was inserted before the first frame, update the index. On the
+  // next call to Render() it will be dropped.
+  if (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 (ideal_cadence_ && !fractional_cadence_)
+    it->ideal_render_count = ideal_cadence_;
+  else if (fractional_cadence_)
+    UpdateFractionalCadenceForFrames(fractional_cadence_);
+
+  // 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());
+  }
+}
+
+void VideoRendererAlgorithm::AccountForMissedIntervals(
+    base::TimeTicks deadline_min,
+    base::TimeTicks deadline_max) {
+  const base::TimeTicks previous_deadline_max = last_deadline_max_;
+  last_deadline_max_ = deadline_max;
+
+  if (previous_deadline_max.is_null())
+    return;
+
+  const int64 render_cycle_count =
+      std::abs((deadline_min - previous_deadline_max) / render_interval_);

[brianderson, 2015/04/16 22:57:56]

Is the abs here to round render_cycle_count down to 0 when the deadline ticks
backwards slightly?

Would this fail in weird ways if we gave you a tick that went backwards too much
and caused render_cycle_count to be >=1?

Might be safer to use std::max(0, ...) and DCHECK that the deadlines_min/max's
are "sufficiently" monotonic.

[DaleCurtis, 2015/04/17 02:38:12]

Yes, fractional values should be zero. I see your point, I'll ensure we only run
this calculation when deadline_min > previous_deadline_max.

[DaleCurtis, 2015/04/18 01:29:21]

Done.

+
+  // In the ideal case this value will be zero.
+  if (!render_cycle_count)
+    return;
+
+  DVLOG(2) << "Missed " << render_cycle_count << " Render() intervals.";
+
+  // Only update display count if the frame was displayed at all; it may not
+  // have been if OnFrameDropped() was called.
+  if (frame_queue_[last_frame_index_].render_count)

[brianderson, 2015/04/16 22:57:56]

Does this need to be a loop for the case were render_count + render_cycle_count
> ideal_render_count?

[DaleCurtis, 2015/04/17 02:38:12]

No, the FindBestFrameByCadence() will handle overages.

+    frame_queue_[last_frame_index_].render_count += render_cycle_count;
+}
+
+base::TimeDelta VideoRendererAlgorithm::CalculateTimeUntilGlitch(
+    double perfect_cadence,
+    double clamped_cadence,
+    bool fractional) {
+  if (clamped_cadence == 0.0)
+    return base::TimeDelta();
+
+  // Calculate the drift in microseconds for each frame we render at cadence
+  // instead of for its real duration.
+  const double rendered_frame_duration =
+      fractional ? render_interval_.InMicroseconds()
+                 : clamped_cadence * render_interval_.InMicroseconds();
+
+  // 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
+  // displayed after accounting for those |clamped_cadence| frames.
+  const double actual_frame_duration =
+      fractional ? clamped_cadence * frame_duration_.InMicroseconds()
+                 : frame_duration_.InMicroseconds();
+
+  const double rendered_vs_actual_duration_delta =
+      std::abs(rendered_frame_duration - actual_frame_duration);
+  if (rendered_vs_actual_duration_delta <
+      std::numeric_limits<double>::epsilon()) {
+    return kInfiniteDuration();
+  }
+
+  const double frames_rendered_before_drift_exhausted =
+      std::ceil(max_acceptable_drift_.InMicroseconds() /
+                rendered_vs_actual_duration_delta);
+
+  const base::TimeDelta time_until_glitch = base::TimeDelta::FromMicroseconds(
+      rendered_frame_duration * frames_rendered_before_drift_exhausted);
+
+  return time_until_glitch;
+}
+
+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 (auto& frame_info : frame_queue_) {
+    frame_info.wall_clock_time =
+        time_converter_cb_.Run(frame_info.media_timestamp);
+
+    // If time stops or never started, exit immediately.
+    if (frame_info.wall_clock_time.is_null())
+      return false;
+  }
+
+  // Do we have enough frames to compute statistics?
+  const bool have_frame_duration = frame_duration_ != base::TimeDelta();
+  if (frame_queue_.size() < 2 && !have_frame_duration)
+    return true;
+
+  // Update |frame_duration_| estimate weighted towards the existing duration.
+  const base::TimeDelta wall_clock_delta = frame_queue_.back().wall_clock_time -
+                                           frame_queue_.front().wall_clock_time;
+  if (!have_frame_duration) {
+    frame_duration_ = wall_clock_delta / (frame_queue_.size() - 1);
+  } else {
+    frame_duration_ =
+        (frame_duration_ + wall_clock_delta) / frame_queue_.size();
+  }
+
+  // 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(frame_duration_ / 2, base::TimeDelta::FromSecondsD(1.0 / 120));
+
+  // The perfect cadence is the number of render intervals per frame, while the
+  // clamped cadence is the nearest matching integer cadence.
+  const double perfect_cadence =
+      frame_duration_.InSecondsF() / render_interval_.InSecondsF();
+  const int clamped_cadence = perfect_cadence + 0.5;
+
+  // Inverse cadence is checked to see if we have a fractional cadence which
+  // would look best if we consistently drop the same frames.  A fractional
+  // cadence is something like 120fps content on a 60Hz display.
+  const double inverse_perfect_cadence = 1.0 / perfect_cadence;
+  const int clamped_inverse_cadence = inverse_perfect_cadence + 0.5;
+
+  const base::TimeDelta minimum_glitch_time =
+      base::TimeDelta::FromSeconds(kMinimumAcceptableTimeBetweenGlitchesSecs);
+
+  // See if the clamped cadence fits acceptable thresholds for exhausting drift.

[brianderson, 2015/04/16 22:57:56]

Ok. I understand now how this block makes sure 29.97fps video will have a 2
frame cadence, glitch once when the drift is bad enough, and then enter the 2
frame cadence again avoid the problem I was concerned about in
https://docs.google.com/drawings/d/19babNb3eGdZiz36dBE0NCbIVn_PUFguXAC_RPlqyO...
.

+  int new_cadence = 0, new_fractional_cadence = 0;
+  if (CalculateTimeUntilGlitch(perfect_cadence, clamped_cadence, false) >=
+      minimum_glitch_time) {
+    new_cadence = clamped_cadence;
+  } else if (CalculateTimeUntilGlitch(inverse_perfect_cadence,
+                                      clamped_inverse_cadence,
+                                      true) >= minimum_glitch_time) {
+    new_cadence = 1;
+    new_fractional_cadence = clamped_inverse_cadence;
+  }
+
+  // If hysteresis is enabled, require cadence to hold for some time before
+  // switching in or out of cadence based rendering mode.
+  if (cadence_hysteresis_enabled_) {
+    if (new_fractional_cadence) {
+      if (last_detected_cadence_ == new_fractional_cadence) {
+        ++render_intervals_cadence_held_;
+      } else {
+        last_detected_cadence_ = new_fractional_cadence;
+        render_intervals_cadence_held_ = 0;
+      }
+    } else {
+      if (last_detected_cadence_ == new_cadence) {
+        ++render_intervals_cadence_held_;
+      } else {
+        last_detected_cadence_ = new_cadence;
+        render_intervals_cadence_held_ = 0;
+      }
+    }
+
+    // To prevent oscillation of cadence selection, ensure cadence selections
+    // are held for some time before applying them. Value chosen arbitrarily.
+    const base::TimeDelta cadence_hysteresis =
+        base::TimeDelta::FromMilliseconds(100);
+    if (render_intervals_cadence_held_ * render_interval_ < cadence_hysteresis)
+      return true;
+  }
+
+  // No need to update cadence if there's been no change; cadence will be set
+  // as frames are added to the queue.
+  if (ideal_cadence_ == new_cadence &&
+      new_fractional_cadence == fractional_cadence_) {
+    return true;
+  }
+
+  if (new_fractional_cadence) {
+    UpdateFractionalCadenceForFrames(new_fractional_cadence);
+  } else {
+    // |new_cadence| may be zero at this point, which clears previous cadences.
+    for (auto& frame_info : frame_queue_)
+      frame_info.ideal_render_count = new_cadence;
+  }
+
+  // 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.
+
+  if (ideal_cadence_ != new_cadence) {
+    DVLOG(1) << "Cadence switch from " << ideal_cadence_ << " to "
+             << new_cadence << "; perfect_cadence: " << perfect_cadence;
+  }
+  if (fractional_cadence_ != new_fractional_cadence) {
+    DVLOG(1) << "Fractional cadence switch from " << fractional_cadence_
+             << " to " << new_fractional_cadence
+             << "; inverse_perfect_cadence: " << inverse_perfect_cadence;
+  }
+
+  ideal_cadence_ = new_cadence;
+  fractional_cadence_ = new_fractional_cadence;
+  return true;
+}
+
+void VideoRendererAlgorithm::UpdateFractionalCadenceForFrames(
+    int fractional_cadence) {
+  // Cadence is 1 for the first of every |fractional_cadence| frames and zero
+  // elsewhere.
+  for (size_t i = last_frame_index_; i < frame_queue_.size(); ++i) {
+    frame_queue_[i].ideal_render_count =
+        static_cast<int>((i - last_frame_index_) % fractional_cadence == 0);
+  }
+}
+
+int VideoRendererAlgorithm::FindBestFrameByCadence() {
+  DCHECK(!frame_queue_.empty());
+  if (!ideal_cadence_)
+    return -1;
+
+  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)
+    return last_frame_index_;
+
+  // If the current frame is on cadence, find the next displayable frame.
+  if (current_frame.render_count == current_frame.ideal_render_count) {
+    for (size_t i = last_frame_index_ + 1; i < frame_queue_.size(); ++i) {
+      if (frame_queue_[i].ideal_render_count > 0)
+        return i;
+    }
+  }
+
+  // The frame is overdisplayed or we don't have enough frames to find a better
+  // once by cadence, so return nothing.
+  return -1;
+}
+
+int VideoRendererAlgorithm::FindBestFrameByCoverage(
+    base::TimeTicks deadline_min,
+    base::TimeTicks deadline_max,
+    int* second_best) {
+  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 0%
+  // coverage, while those which completely overlap the interval have 100%.
+  double best_coverage = 0.0;
+  int best_frame_by_coverage = -1;
+  std::vector<double> coverage(frame_queue_.size(), 0.0);
+  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)
+      continue;
+
+    // Clamp frame times to a maximum of |deadline_max|.
+    const base::TimeTicks next_frame_time = std::min(
+        deadline_max, i + 1 < frame_queue_.size()
+                          ? frame_queue_[i + 1].wall_clock_time
+                          : frame_queue_[i].wall_clock_time + frame_duration_);
+
+    // Frames entirely before the deadline interval have zero coverage.
+    if (next_frame_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 =
+        next_frame_time -
+        std::max(deadline_min, frame_queue_[i].wall_clock_time);
+
+    coverage[i] = duration.InSecondsF() / render_interval_.InSecondsF();
+    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] = 0.0;
+    auto it = std::max_element(coverage.begin(), coverage.end());
+    if (*it > 0)
+      *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 double kAllowableJitter = 500.0 / render_interval_.InMicroseconds();
+  if (*second_best >= 0 && best_frame_by_coverage > *second_best &&
+      std::abs(best_coverage - coverage[*second_best]) <= kAllowableJitter) {
+    std::swap(best_frame_by_coverage, *second_best);
+  }
+
+  // TODO(dalecurtis): We may want to make a better decision about what to do

[brianderson, 2015/04/16 22:57:56]

Thanks for adding this TODO. Fixing this shouldn't block landing of this patch,
but we should definitely get some numbers to see if this is a real problem.

For ~24fps video, some runs will be immune to jitter naturally if the frame
phases don't align with the vsync phase, so the problem may be intermittent.

+  // 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.974 fps and 24 fps 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) {
+  DCHECK(!frame_queue_.empty());
+
+  int best_frame_by_drift = -1;
+  base::TimeDelta min_drift = base::TimeDelta::Max();
+
+  for (size_t i = last_frame_index_; i < frame_queue_.size(); ++i) {
+    const base::TimeDelta drift = CalculateDriftForFrame(deadline_min, i);
+    if (drift < min_drift) {
+      min_drift = drift;
+      best_frame_by_drift = i;
+    }
+  }
+
+  return best_frame_by_drift;
+}
+
+base::TimeDelta VideoRendererAlgorithm::CalculateDriftForFrame(
+    base::TimeTicks deadline_min,
+    int frame_index) {
+  const ReadyFrame& frame = frame_queue_[frame_index];
+
+  // If the frame lies before the deadline, compute the delta against the end
+  // of the frame's correct display duration.
+  if (frame.wall_clock_time < deadline_min &&
+      frame.wall_clock_time + frame_duration_ < deadline_min) {
+    return deadline_min - (frame.wall_clock_time + frame_duration_);
+  }
+
+  // If the frame lies after the deadline, compute the delta against the start
+  // of the frame's correct display time.
+  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.wall_clock_time + frame_duration_, deadline_min);
+  return base::TimeDelta();
+}
+
+}  // namespace media