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..b6d14e168860493355be53562080a47a72c5b2df
--- /dev/null
+++ b/media/filters/video_renderer_algorithm.h
@@ -0,0 +1,256 @@
+// 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/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 {
+
+// A cadence based video rendering algorithm with coverage based fallback for
+// non-integer cadences. I.e., if the presentation interval is an integer
+// multiple or divisor of the wall clock frame duration the algorithm will
+// prefer to redisplay the current frame until a drift threshold is exceeded or
+// the optimal cadence is reached.
+//
+// In cases of non-integer cadence, the algorithm will fallback to choosing the
+// frame which covers the most of the current presentation interval. If no frame
+// covers the current interval, the least bad frame will be chosen based on its
+// drift from the interval.

[xhwang, 2015/04/15 18:05:28]

This class is not trivial. Can you explain more about how this class should be
used? For example, when should RemoveExpiredFrames() be called etc...

[DaleCurtis, 2015/04/15 19:10:53]

Good idea. I'll add more here. Essentially a class should EnqueueFrames() as it
receives them and call Render() on a periodic basis. If Render() callbacks are
expected to stop for any reason clients can manage the recency of the queue via
RemoveExpiredFrames() and EnqueueFrames().

+class MEDIA_EXPORT VideoRendererAlgorithm {
+ public:
+  // Used to convert a media timestamp into wall clock time.
+  using TimeConverterCB = base::Callback<base::TimeTicks(base::TimeDelta)>;

[xhwang, 2015/04/15 18:05:28]

add include for base::Callback

[DaleCurtis, 2015/04/16 01:48:01]

Done.

+
+  VideoRendererAlgorithm(const TimeConverterCB& time_converter_cb);

[xhwang, 2015/04/15 18:05:28]

explicit

[DaleCurtis, 2015/04/16 01:48:01]

Done.

+  ~VideoRendererAlgorithm();
+
+  // Chooses the best frame for the interval [deadline_min, deadline_max] based
+  // on available and previously rendered frames.
+  //
+  // The deadline interval provided to a Render() call should be adjacent to the
+  // deadline given to the previous Render() call.  Gaps which exceed the length
+  // of the deadline interval are assumed to be repeated frames for the purposes
+  // of cadence detection.

[xhwang, 2015/04/15 20:51:39]

Can you elaborate on this as well? By "adjacent", do you mean they can be
non-contiguous (allowing gaps)?

[DaleCurtis, 2015/04/16 01:48:01]

Yes, hence the "Gaps which exceed..." - do you still need more clarity?

+  //
+  // 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 display time is too far in the past.
+  scoped_refptr<VideoFrame> Render(base::TimeTicks deadline_min,
+                                   base::TimeTicks deadline_max,

[xhwang, 2015/04/15 18:05:28]

Bike shedding:

1. We have this deadline_min and deadline_max pattern in many places (in this CL
and the previous CL), which make me think why don't we have a class for it?
Something like TimeInterval or WallClockTimeInterval, where you can get min/max
(or begin/end), and duration etc.

2. A deadline interval is a bit odd. By definition, a deadline should be a time
(TimeTicks), not a duration/interval. Here it sounds more like a rendering
window, or a target interval.

[DaleCurtis, 2015/04/15 19:10:53]

Hmm, I'll have to think about adding a class for this; it feels like it would
complicate the interface and harm readability, but that may just be my
resistance to helper classes like that.

At the compositor level this is called "frame_time" so we could call it
frame_begin and frame_end or something similar. If we went with a class it could
be a FrameInterval.

[xhwang, 2015/04/15 20:51:39]

FrameInterval can be confused with frame duration...

Since this class is pretty generic: it's really a TimeDelta with a fixed
starting TimeTicks. The class name should be generic as well. That's why I was
proposing TimeInterval or WallClockTimeInterval, which has nothing to do with
rendering, frame etc.

+                                   int* frames_dropped);
+
+  // Removes all video frames which are unusable since their display interval
+  // [timestamp, timestamp + duration] is too far away from |deadline_min| than
+  // 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 expired.
+  int RemoveExpiredFrames(base::TimeTicks deadline_min);

[xhwang, 2015/04/15 18:05:28]

Wondering shouldn't this be handled internally in this class?

[DaleCurtis, 2015/04/15 19:10:53]

The VRI will use this to expire frames via a countdown timer when Render()
callbacks stop. I don't think we want to call this implicitly via
EnqueueFrames() or we won't count those frames as dropped.

I was thinking VRI's countdown timer would first expire old frames, set a
background_rendering flag, pump the decode loop (which would continue until
frame limits are met again), and then reset its countdown timer. This keeps
memory usage under control and maintains enough frames that switching back to
the tab won't be too far behind.

+
+  // 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
+  // timestamp will be sorted into appropriate order.  Frames inserted prior to
+  // the last rendered frame will be dropped.  Do not enqueue end of stream
+  // frames.
+  void EnqueueFrame(const scoped_refptr<VideoFrame>& frame);
+
+  // Removes all frames from the |frame_queue_| and clears predictors.

[xhwang, 2015/04/15 18:05:28]

Just to double check, does this set |this| to a clean state?

[DaleCurtis, 2015/04/15 19:10:53]

Yes. I use it extensively in the tests :)

+  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 display duration of all frames in |frame_queue_|
+  // as measured in wall clock (not media) time.
+  base::TimeDelta average_frame_duration() const { return frame_duration_; }
+
+  bool last_render_had_glitch() const { return last_render_had_glitch_; }
+
+  void disable_cadence_hysteresis_for_testing() {

[xhwang, 2015/04/15 18:05:28]

Move to private since you have the test class as a friend?

[DaleCurtis, 2015/04/16 01:48:01]

Removed, it's a relic of when I didn't have a bool for disabling hysteresis.

+    cadence_hysteresis_enabled_ = false;
+  }
+
+ private:
+  friend class VideoRendererAlgorithmTest;
+

[xhwang, 2015/04/15 20:51:39]

Maybe have a summary here on how the internal algorithm works. Explain cadence,
clamp, fraction, drift, glitches, coverage etc. That will make it much easier to
read.

[DaleCurtis, 2015/04/16 01:48:01]

I've given a high level summary at the top of the class, let me know if you want
more information there. Otherwise I feel the summary attached to each function
is sufficient.

+  enum {

[xhwang, 2015/04/15 18:05:28]

why enum instead of just a static const?

http://stackoverflow.com/questions/204983/static-const-member-value-vs-member...

[DaleCurtis, 2015/04/15 19:10:53]

Hmm, I was under the impression this would result in each includer of the header
getting its own copy of the value.

[xhwang, 2015/04/15 20:51:39]

Since this is an integer type, the value will be evaluated at compile time. I
don't think you'll have any extra copy of it.

[DaleCurtis, 2015/04/16 01:48:01]

http://stackoverflow.com/questions/92546/variable-declarations-in-header-file...

[xhwang, 2015/04/16 22:30:45]

[I am just learning on this :) Would be happy to get the bottom of it no matter
which one is true.]

I don't think that applies to static const class member. Typically if you have a
non-integral static const class member, you cannot define/initialize it in the
header file. You'll need to define it in a cc file. So you'll only have one
definition of it in the entire program. The fact that you can initialize a
static const "integral" class memeber in the header file is just a shortcut, but
it shouldn't change the fact that we only have one definition of it:

http://stackoverflow.com/questions/4547660/c-static-member-variable-and-its-i...

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

Looked into this a bit more, it seems okay for integral types:

https://randomascii.wordpress.com/2014/06/26/please-calculate-this-circles-ci...

+    // 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.

[xhwang, 2015/04/15 18:05:28]

I still don't follow how 8 seconds is calculated; can you elaborate more?

[DaleCurtis, 2015/04/15 19:10:53]

Essentially I played some videos and looked at how noticeable the glitches were
in relation to common rates which would benefit from cadence. I also compared a
couple of desktop players which use similar algorithms. The gist is we want to
ensure forcing cadence is relatively stable. This means that we won't repeat or
drop a frame for at least 8 seconds; versus without cadence (which may be much
shorter in cases where the render interval has jitter).

I originally had this at 18 seconds based on estimated short term memory limits,
but that proved too high for common frame rates. The cadence approach is
superior in terms of glitch counts to coverage, so it should be used as much as
possible. 8 seconds may even be too high. We may want to allow down to 4
seconds.

Consider that the coverage based approach in this case would generally model the
cadence approach, but may drift away faster based on jitter in the vsync
interval. See this diagram from the compositor folk for more details on how
jitter can affect the selection process (of note is my comment at the end of
BestFrameByCoverage too):

https://docs.google.com/drawings/d/19babNb3eGdZiz36dBE0NCbIVn_PUFguXAC_RPlqyO...

+    //
+    // 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.
+    kMinimumAcceptableTimeBetweenGlitchesSecs = 8
+  };
+
+  // Updates the display 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.
+  //
+  // 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.

[xhwang, 2015/04/15 18:05:28]

Is 29.5 the perfect cadence, and 60 the clamped cadence? May need to be more
explicit in the comment. Also, what is |fractional| here?

[DaleCurtis, 2015/04/15 19:10:53]

29.5fps is the video frame rate, 60Hz is the display rate, the clamped cadence
would be 2 (round(60/29.5)). Fractional cadence would be zero in this case. In
the 120fps in 59.9Hz case, ideal_cadence would be "1" and the fractional_cadence
would also be 1 (round(120/59.9) - 1); which tells us that the frame we select
should be displayed once, and then we should always drop the next frame.

[xhwang, 2015/04/15 20:51:39]

Thanks for the explanation. We definitely need more docs on these parameters...

[DaleCurtis, 2015/04/16 01:48:01]

Done.

+  //    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.
+  //
+  base::TimeDelta CalculateTimeUntilGlitch(double perfect_cadence,
+                                           double clamped_cadence,
+                                           bool fractional);
+
+  // Updates the display 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 display count for all frames in |frame_queue_| based on
+  // the given |fractional_cadence|.  The first of every |fractional_cadence|
+  // frames is given a display 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 the last frame is above
+  // cadence or there is no |ideal_cadence_|.
+  int FindBestFrameByCadence();
+
+  // 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 + frame_duration_] lies before
+  // |deadline_min| the drift is the delta between |deadline_min| and
+  // |wall_clock_time + 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,
+                                         int frame_index);
+
+  struct ReadyFrame {
+    ReadyFrame(const scoped_refptr<VideoFrame>& frame);
+    ~ReadyFrame();
+
+    scoped_refptr<VideoFrame> frame;
+
+    base::TimeDelta media_timestamp;
+    base::TimeTicks wall_clock_time;
+    int ideal_render_count;
+    int render_count;
+
+    // For use with std::lower_bound.
+    bool operator<(const ReadyFrame& other) 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 displayed frame may be moved.
+  int last_frame_index_;
+
+  // The idealized cadence for all frames seen thus far; updated based upon the
+  // |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 displayed 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_;
+
+  // The last |deadline_max| provided to Render(), used to predict whether
+  // frames were displayed over cadence between Render() calls.
+  base::TimeTicks last_deadline_max_;
+
+  // The average of the display duration of all frames in |frame_queue_| as
+  // measured in wall clock (not media) time at the time of the last Render().
+  base::TimeDelta frame_duration_;
+
+  // The length of the last deadline interval given to Render(), updated at the
+  // start of Render().
+  base::TimeDelta render_interval_;

[xhwang, 2015/04/15 18:05:28]

How about |last_interval_|? If you have a class for the interval, you can merge
this and the |last_deadline_max_|.

[DaleCurtis, 2015/04/16 01:48:01]

Still thinking about this; it seems reasonable, but I didn't have time to play
with the code today.

+
+  // 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-displayed a frame, over-displayed a frame, dropped one or
+  // more frames, or chosen a frame which exceeded acceptable drift.
+  bool last_render_had_glitch_;
+
+  DISALLOW_COPY_AND_ASSIGN(VideoRendererAlgorithm);
+};
+
+}  // namespace media
+
+#endif  // MEDIA_FILTERS_VIDEO_RENDERER_ALGORITHM_H_