Introduce cadence based VideoRendererAlgorithm.

media/filters/video_renderer_algorithm.cc

Index: media/filters/video_renderer_algorithm.cc
diff --git a/media/filters/video_renderer_algorithm.cc b/media/filters/video_renderer_algorithm.cc
new file mode 100644
index 0000000000000000000000000000000000000000..3d55c31f2e9318694c5b2521c7a749204eff574f
--- /dev/null
+++ b/media/filters/video_renderer_algorithm.cc
@@ -0,0 +1,657 @@
+// 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 {
+
+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();

[miu, 2015/04/21 07:04:22]

nit: DCHECK(!time_converter_cb_.is_null());

[DaleCurtis, 2015/04/23 21:45:40]

Done.

+}
+
+VideoRendererAlgorithm::~VideoRendererAlgorithm() {
+}
+
+scoped_refptr<VideoFrame> VideoRendererAlgorithm::Render(
+    base::TimeTicks deadline_min,
+    base::TimeTicks deadline_max,
+    size_t* 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);
+  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()) {

[miu, 2015/04/21 07:04:21]

It feels expensive to update the wall clock timestamps for all frames and
recompute all the stats each time Render() is called.  Is there a reason we
expect  the values returned by |time_converter_cb_| to skew or otherwise not be
stateless?  If so, maybe that should be documented in the header file comments. 
Consider updating frame statistics using a more on-line algorithm and from
EnqueueFrame() instead of Render().

[DaleCurtis, 2015/04/23 21:45:40]

These values are directly calculated based on rendered audio frames in the ideal
case and predicted if they haven't been written to the audio device yet.  agree
it's not ideal to recalculate every time, but early in playback and especially
in the case of playback rate changes, these values can skew significantly.

I played with this a lot and didn't find a good solution :( I think to do better
we'd have to have some sort of registration callback on the timesource which
registered a timestamp and timeticks pointer which could be updated as
timestamps change.

In the other direction, once all this is wired up I can do some more extensive
testing to see just how accurate we need these values to be. I've been overly
cautious thus far. For cadence based rendering, we just need a frame duration
which should be stable even if the wall clock time jitters (since all times
would jitter the same for a given cycle). So long as we had a mechanism to
detect playback rate changes at Render() time, we could recompute only when
necessary.

+    DVLOG(2) << "Failed to update frame statistics.";
+    DCHECK(frame_queue_[last_frame_index_].frame);
+    return frame_queue_[last_frame_index_].frame;
+  }
+
+  base::TimeDelta selected_frame_drift;
+
+  // Step 4: Attempt to find the best frame by cadence.
+  int frame_to_render = -1;
+  if (ideal_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_) {
+    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_to_render = FindBestFrameByDrift(deadline_min);

[miu, 2015/04/21 07:04:22]

Minor optimization:

  frame_to_render = FindBestFrameByDrift(deadline_min, &selected_frame_drift);

...to avoid calling CalculateDriftForFrame() again.

[DaleCurtis, 2015/04/23 21:45:40]

Done.

+    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";
+  }

[xhwang, 2015/04/22 06:11:38]

You could use DVLOG_IF

[DaleCurtis, 2015/04/23 21:45:40]

Done.

+
+  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 (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.media_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.media_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 (frames_dropped)
+    *frames_dropped = 0;
+
+  if (frame_to_render > 0) {
+    if (frames_dropped) {
+      for (int i = 0; i < frame_to_render; ++i) {
+        if (!frame_queue_[i].render_count) {

[xhwang, 2015/04/22 06:11:38]

nit: how about for (const auto& frame : frame_queue_)

[DaleCurtis, 2015/04/23 21:45:40]

We're only iterating up to |frame_to_render| here, so that doesn't work here.
I've added a local variable to avoid all the lookups though.

+          DVLOG(2) << "Dropping unrendered 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;
+}
+
+size_t VideoRendererAlgorithm::RemoveExpiredFrames(
+    base::TimeTicks deadline_min) {
+  if (!UpdateFrameStatistics() || average_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 render interval is further than |max_acceptable_drift_| from the
+  // given |deadline_min|.
+  size_t frames_to_expire = 0;
+  const base::TimeTicks mininum_frame_time =
+      deadline_min - 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 >= 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_ = 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());
+
+  // We only care if the frame was never rendered at all; otherwise we assume
+  // that the frame was repeated (since no other frame has been issued since).
+  if (frame_queue_[last_frame_index_].render_count == 1) {
+    frame_queue_[last_frame_index_].render_count = 0;
+
+    // Reduce the ideal render count so that the frame is properly dropped when
+    // enough render intervals have passed (even if it was never rendered).
+    --frame_queue_[last_frame_index_].ideal_render_count;
+  }
+}
+
+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();
+  average_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 {
+  // Even if we don't have cadence, subtract off any frames which are before
+  // the last rendered frame.
+  if (!have_rendered_frames_ || !ideal_cadence_) {
+    if (!frame_queue_.empty()) {
+      DCHECK_LT(last_frame_index_, frame_queue_.size());
+    } else {
+      DCHECK_EQ(last_frame_index_, 0u);
+    }
+    return frame_queue_.size() - last_frame_index_;
+  }
+
+  // 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_;
+  }

[xhwang, 2015/04/22 06:11:38]

If you store frame_queue_ as a map<media_time, ReadyFrame>, and keep
|last_frame_index_| as the iterator to the last frame, then
- you don't need to calculate the lower_bound on l.262.
- you don't need to update last frame index when you insert/erase frames.

The drawback is that when you iterator through all frames, you'll need i->second
to access the ReadyFrame. But that seems not too bad to me.

[miu, 2015/04/23 18:23:00]

I disagree.  The deque is much more memory efficient, and using the map for the
reasons you state doesn't actually gain anything:
std::lower_bound() is implemented as a binary search on an ordered array and is
O(lg n).  The look-up for any element in a binary tree is also O(lg n).
It always has to be checked/updated anyway in case you insert the first frame,
or erase the only frame, in the frame_queue_.

If there wasn't a need to iterate frames in-order for the various analyses, a
min-heap would probably be the best data structure option.

[DaleCurtis, 2015/04/23 21:45:40]

Yeah, I prefer the deque here for the constant iteration needs. In the vast
majority of cases the lower_bound should complete without any internal
iterations since timestamps are generally in order.

+
+  // 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) {

[miu, 2015/04/21 07:04:21]

Consider surrounding this loop with: #ifndef NDEBUG ... #endif

[miu, 2015/04/21 07:04:21]

ditto: Consider #ifndef NDEBUG ... #endif around this loop.

[DaleCurtis, 2015/04/23 21:45:40]

Done.

+    DCHECK(frame_queue_[i].frame->timestamp() <=
+           frame_queue_[i + 1].frame->timestamp());
+  }
+}
+
+void VideoRendererAlgorithm::AccountForMissedIntervals(
+    base::TimeTicks deadline_min,
+    base::TimeTicks deadline_max) {
+  if (last_deadline_max_.is_null() || deadline_min <= last_deadline_max_)
+    return;
+
+  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 OnLastFrameDropped() was called.
+  if (frame_queue_[last_frame_index_].render_count)
+    frame_queue_[last_frame_index_].render_count += render_cycle_count;
+}
+
+base::TimeDelta VideoRendererAlgorithm::CalculateTimeUntilGlitch(
+    double perfect_cadence,
+    double clamped_cadence,

[miu, 2015/04/21 07:04:22]

The type of the |clamped_cadence| arg should be int, not double, right?

[DaleCurtis, 2015/04/23 21:45:40]

Removed, now just TimeDelta is passed around in VideoCadenceEstimator.

+    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
+  // rendered after accounting for those |clamped_cadence| frames.
+  const double actual_frame_duration =
+      fractional ? clamped_cadence * average_frame_duration_.InMicroseconds()
+                 : average_frame_duration_.InMicroseconds();
+
+  const double rendered_vs_actual_duration_delta =
+      std::abs(rendered_frame_duration - actual_frame_duration);
+  if (rendered_vs_actual_duration_delta <

[miu, 2015/04/21 07:04:22]

The type of |rendered_frame_duration|, |actual_frame_duration|, and
|rendered_vs_actual_duration_delta| could be base::TimeDelta.  Then, you can
compare less-than-or-equal to zero here rather than deal with epsilon.

[DaleCurtis, 2015/04/23 21:45:40]

Done, mostly, but kept the duration delta as a double to avoid a static_cast in
the ceil() computation.

+      std::numeric_limits<double>::epsilon()) {
+    return kInfiniteDuration();
+  }
+
+  const double frames_rendered_before_drift_exhausted =

[miu, 2015/04/21 07:04:22]

Should be of type int, not double.

[DaleCurtis, 2015/04/23 21:45:40]

Done.

+      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())

[miu, 2015/04/21 07:04:21]

bikeshedding: Is it possible for frame timestamps to be negative?  If so, it's
possible for wall_clock_time to be validly set to a zero value.

[DaleCurtis, 2015/04/23 21:45:40]

They should never be negative, we have DCHECKS in FFmpegDemuxer for this.

+      return false;
+  }
+
+  // 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 true;

[miu, 2015/04/21 07:04:22]

Should this return false here, since average_frame_duration_ ==
base::TimeDelta() at this point?

[DaleCurtis, 2015/04/23 21:45:40]

It shouldn't have before, but you're right that it's a bit odd that the rest of
the calculations are attempted when the duration is zero. I've short circuited
this and changed the code to return false (which failed unit tests until I
repaired the render count).

+
+  // Update |average_frame_duration_|,  weighted towards the existing duration.

[miu, 2015/04/21 07:04:22]

nit: extra space after comma

[DaleCurtis, 2015/04/23 21:45:41]

Done.

+  const base::TimeDelta wall_clock_delta = frame_queue_.back().wall_clock_time -
+                                           frame_queue_.front().wall_clock_time;
+  if (!have_frame_duration) {
+    average_frame_duration_ = wall_clock_delta / (frame_queue_.size() - 1);
+  } else {
+    average_frame_duration_ =
+        (average_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(average_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 =
+      average_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.
+  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;
+
+  int new_ideal_render_count = 0;
+  const int best_frame =
+      FindBestFrameByCadenceInternal(&new_ideal_render_count);
+  if (best_frame < 0)
+    return -1;
+
+  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(ideal_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 =

[miu, 2015/04/21 07:04:22]

nit/consistency: This statement becomes one line if you use the reference
variable:

  *adjusted_ideal_render_count = current_frame.ideal_render_count;

[DaleCurtis, 2015/04/23 21:45:40]

Done.

+          frame_queue_[last_frame_index_].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) {
+    if (frame_queue_[i].ideal_render_count > render_count_overage) {
+      if (adjusted_ideal_render_count) {
+        *adjusted_ideal_render_count =
+            frame_queue_[i].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_queue_[i].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(

[xhwang, 2015/04/22 06:11:37]

Wondering can we use media::Ranges to help simplify this function?

https://code.google.com/p/chromium/codesearch#chromium/src/media/base/ranges....

[DaleCurtis, 2015/04/23 21:45:40]

I think it'd be just as much work to get translate the frame data into ranges
and then transform the results into a double.

+    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;

[miu, 2015/04/21 07:04:22]

Should this be a break statement instead of a continue statement?  Or, can
wall_clock_time values be out-of-order even when the media timestamps are
in-order?  Perhaps this assumption should be DCHECK'ed where the wall_clock_time
values are computed/assigned?

[DaleCurtis, 2015/04/23 21:45:41]

Good point, it should be a break, but it's possible that these are out of order
if we get an unlucky playback rate change with our calls into the time converter
(which is potentially running on a different thread). For now I've added a
CHECK() to UpdateFrameStatistics to see how frequently this happens...

We may need either a capped retry mechanism for time calculations or the ability
to give all of our timestamps to the TimeConverterCB at once.

+
+    // Clamp frame times to a maximum of |deadline_max|.
+    const base::TimeTicks next_frame_time =

[miu, 2015/04/21 07:04:22]

naming: For clarity, this is really frame_end_time, not next_frame_time.

[DaleCurtis, 2015/04/23 21:45:40]

Done.

+        std::min(deadline_max, i + 1 < frame_queue_.size()
+                                   ? frame_queue_[i + 1].wall_clock_time
+                                   : frame_queue_[i].wall_clock_time +
+                                         average_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();

[miu, 2015/04/21 07:04:22]

To simplify, how about just:

  coverage[i] = duration;

Meaning, there's no need to divide by render_interval_.  You get the same result
without the extra float conversions and floating-point division operations.

[DaleCurtis, 2015/04/23 21:45:40]

Done, great suggestion.

+    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();

[miu, 2015/04/21 07:04:22]

Side note: If you take my advice above, more floating-point math is avoided,
since this simplifies to:

  const int kAllowableJitterUsec = 500;
  if (*second_best >= base::TimeDelta() && best_frame_by_coverage > *second_best
&&
      (best_coverage - coverage[*second_best]).magnitude().InMicroseconds() <=
kAllowableJitterUsec) {
    std::swap(...);
  }

[DaleCurtis, 2015/04/23 21:45:40]

Done.

+  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
+  // 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) {
+  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);
+    // We use <= here to prefer the latest frame with minimum drift.
+    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 duration.
+  if (frame.wall_clock_time < deadline_min &&

[miu, 2015/04/21 07:04:21]

It the LHS of the logical-and expression needed?  Seems like the LHS is always
true if the RHS is true (but the compiler optimizer won't know that).

[DaleCurtis, 2015/04/23 21:45:40]

Done.

+      frame.wall_clock_time + average_frame_duration_ < deadline_min) {
+    return deadline_min - (frame.wall_clock_time + average_frame_duration_);

[miu, 2015/04/21 07:04:21]

This could all be simplified as:

  const base::TimeDelta before_deadline = deadline_min - (frame.wall_clock_time
+ average_frame_duration_);
  if (before_deadline > base::TimeDelta())
    return before_deadline;

[DaleCurtis, 2015/04/23 21:45:40]

I like the readability better as is, I did simplify a bit by bringing in
frame_end_time for the above function.

+  }
+
+  // If the frame lies after the deadline, compute the delta against the frame's
+  // wall clock 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 + average_frame_duration_, deadline_min);
+  return base::TimeDelta();
+}
+
+}  // namespace media