Introduce cadence based VideoRendererAlgorithm.

media/filters/video_renderer_algorithm.h

Index: media/filters/video_renderer_algorithm.h
diff --git a/media/filters/video_renderer_algorithm.h b/media/filters/video_renderer_algorithm.h
new file mode 100644
index 0000000000000000000000000000000000000000..6c09d7e6074d9bf0a0ff18b595a23afc9c3d9e64
--- /dev/null
+++ b/media/filters/video_renderer_algorithm.h
@@ -0,0 +1,308 @@
+// 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/video_frame.h"
+#include "media/base/video_renderer.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).
+//
+// Some definitions are necessary to understand how VRA selects frames: the
+// primary means of smooth frame selection is via forced integer cadence.
+// 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.
+//
+// Forced integer cadence means we round the actual cadence (~2.0029 in the
+// previous 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 forcing 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 force cadence when it will take many seconds
+// to drift an undesirable amount; see CalculateTimeUntilGlitch() 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 previous example N = 120/60 = 2. See implementations
+// of CalculateTimeUntilGlitch() and UpdateFrameStatistics() for more details.
+//
+// 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.
+  size_t RemoveExpiredFrames(base::TimeTicks deadline_min);
+
+  // 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 or if
+  // no cadence pattern is detected, this will be the same as the number of
+  // frames given to EnqueueFrame().
+  //
+  // If a cadence has been identified, this will return the number of frames
+  // which have a non-zero ideal render count.
+  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_;
+  }
+
+ 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;
+
+  // 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);
+
+  // Calculates how long until |max_acceptable_drift_| would be exhausted by
+  // showing a frame for |clamped_cadence| render intervals instead of for the
+  // ideal |perfect_cadence| intervals.
+  //
+  // 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.
+  //
+  // In practice this works out to the following for common setups if the
+  // |clamped_cadence| is used for rendering:
+  //
+  //    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.

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

Can we add UMA for the real fps/vsync combinations in a later CL?

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

Absolutely.

+  //
+  base::TimeDelta CalculateTimeUntilGlitch(double perfect_cadence,
+                                           double clamped_cadence,
+                                           bool fractional);
+
+  // 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 can occur if media time has stopped. Sets |ideal_cadence_| to a non
+  // zero value if an integer cadence was detected.
+  bool UpdateFrameStatistics();
+
+  // Updates the ideal render count for all frames in |frame_queue_| based on
+  // the given |fractional_cadence|.  The first of every |fractional_cadence|
+  // frames is given a render count of one, the rest are given zero.  The first
+  // frame is determined by |last_frame_index_|.
+  void UpdateFractionalCadenceForFrames(int fractional_cadence);
+
+  // If |ideal_cadence_| is non-zero and handles cases where the last frame is
+  // under cadence or exactly on cadence.  Returns -1 if not enough frames are

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

nit: The first sentence of this comment is incomplete.  Given the rest of the
comment, maybe it should just be deleted?

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

Edited.

+  // available for cadence selection or there is no |ideal_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 over selection, optionally

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

nit: s/in the case over/in the case of over/

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

Done.

+  // 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);
+
+  // 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.
+  int FindBestFrameByDrift(base::TimeTicks deadline_min);
+
+  // 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 CalculateDriftForFrame(base::TimeTicks deadline_min,

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

Since the values returned are absolute drift (i.e., they hide whether the frame
is before or after a point-in-time), should this be called
CalculateAbsoluteDriftForFrame()?

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

Done.

+                                         int frame_index);
+
+  struct ReadyFrame {

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

style nit: Types should be defined at the top of the "private:" section before
methods.

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

Done.

+    ReadyFrame(const scoped_refptr<VideoFrame>& frame);
+    ~ReadyFrame();
+
+    scoped_refptr<VideoFrame> frame;
+
+    base::TimeDelta media_timestamp;

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

Please remove this duplicate field.  It doesn't seem to be mutated after
construction, so all code can reference frame->timestamp() instead, right?

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

Done.

+    base::TimeTicks wall_clock_time;
+    int ideal_render_count;
+    int render_count;
+
+    // For use with std::lower_bound.
+    bool operator<(const ReadyFrame& other) const;

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

style nit: move to before member variables?

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

Done.

+  };
+
+  // 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_;
+
+  // The idealized cadence for all frames seen thus far; updated based upon the
+  // |average_frame_duration_| relative to the deadline interval provided to
+  // Render(). 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 ideal_cadence_;
+  int fractional_cadence_;
+
+  // Used as hysteresis to prevent oscillation between cadence and coverage
+  // based rendering methods.
+  int last_detected_cadence_;
+  int render_intervals_cadence_held_;
+  bool cadence_hysteresis_enabled_;
+
+  // 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.
+  TimeConverterCB time_converter_cb_;

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

nit: Type should be "const TimeConverterCB" since it's only set from the ctor
initializer list.

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

Done.

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

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

This doesn't need to be a member variable.  It can be local to the Render()
method.

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

It does if I don't want to pollute the Render() interface and expose it to
tests. Am I missing something?

+
+  DISALLOW_COPY_AND_ASSIGN(VideoRendererAlgorithm);
+};
+
+}  // namespace media
+
+#endif  // MEDIA_FILTERS_VIDEO_RENDERER_ALGORITHM_H_