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..606067bc56b2a4837f84edf20311547b4950c407
--- /dev/null
+++ b/media/filters/video_renderer_algorithm.h
@@ -0,0 +1,294 @@
+// 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 from with the goal of providing a smooth playback experience.  I.e.,

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

s/from//

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

Done.

+// 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 30 fps 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.974 fps 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; see implementations
+// of CalculateTimeUntilGlitch() and UpdateFrameStatistics() for 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.
+  //
+  // The deadline interval provided to a Render() call should be adjacent to the

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

tiny nit: Since this is part of the API, it would be nicer to make it clear that
the intervals will not overlap, could have gaps and will monotonically increase.

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

Actually, I forgot Brian told me the other day that the end of the frame
interval is estimated, so the next start could overlap slightly. I'll update the
comment to reflect this.

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

Done.

+  // 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.
+  //
+  // If provided, |frames_dropped| will be set to the number of frames which
+  // were removed from |frame_queue_|, during this call, which were never

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

Does this include the frame dropped during EnqueueFrame()? From this comment it
shouldn't.

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

There are no frames dropped during EnqueueFrame. Do you mean during
RemoveExpiredFrames()? It doesn't include those. It only includes frames which
were dropped in the normal course of events (no background expiry).

[xhwang, 2015/04/17 04:02:14]

I was referring to the comment at l.104-105:
"Frames inserted prior to the last rendered frame will be dropped."

[DaleCurtis, 2015/04/17 04:15:55]

Ah, my bad! That is confusing. They are counted here, not in EnqueueFrames. I'll
reword this to be less confusing.

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

Done.

+  // 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/16 22:30:45]

We can iterate on this in a later CL if you prefer. There are other places we
need update anyways.

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

Yeah, lets handle this in another CL. I'm starting to like the idea in terms of
the number of member variables and calculations it condenses.

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

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

nit: s/expired/removed

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

Done.

+  int RemoveExpiredFrames(base::TimeTicks deadline_min);

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

nit: How about just return a size_t to be consistent with
EffectiveFramesQueued() and avoid a static cast in the implementation? (Not sure
how this will be called though, where we might need to cast anyways.)

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

This spirals out into a couple of of size_t conversions since -1 is used to
signal no frame found, but since these are object counts, I think it makes sense
to do this.

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

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

What about a super old frame was enqueued and therefore was dropped even no
cadence pattern has been detected?

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

It does not count, in the implementation you can see we start counting from
|last_frame_index_| which a super old frame would be added before.

I think you might be mixing up when frames are dropped too. Again, frames aren't
dropped during EnqueueFrame(). They're dropped by Render() or removed by
RemoveExpiredFrames(). EnqueueFrames() always adds frames.

+  //
+  // If a cadence has been identified, this will return the number of frames
+  // which have a non-zero ideal render count.

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

What is "non-zero ideal render count"?

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

A positive render count :) I guess I need to explain fractional cadence in the
introduction too instead of eliding over it. If you look at
|fractional_cadence_| below it has some details.  Essentially when rendering
120fps/60hz we'd render the first frame (ideal render count == 1) and drop the
second frame (ideal render count == 0) of each pair of frames.

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

Thinking wildly... 

I wonder why we need to treat fractional_cadence_ as a special case. It seems
the cadence detection can be generalized to support any perfect cadence if we
define cadence as an array (frame display pattern), instead of one integer
number. For example:

fps   Hz  PerfectCadence DetectedCadence (each element is the number of times a
frame should be rendered)
30    60  2                       2
24    50  25/12               2 2 2 2 2 2 2 2 2 2 2 3
24    60  5/2                   2 3
25    60  12/5                 2 2 3 2 3
29.5  60  120/59             2...2 (29 2s) 3 2...2 (27 2s) 3
29.9  60  600/299           (this is will be crazily long...)
60    30  1/2                   1 0
60    50  5/6                   1 1 1 1 1 0
120   30  1/4                   1 0 0 0

BTW, I assume 2 2 3 2 3 isn't treated as "glitch" because it's really the best
we can do: if we don't use cadence and fallback to coverage based, it can only
be worse, and could be subject to render interval errors.

In theory, the DetectedCadence can have infinite precision, which isn't
realistic because:
1) It can result is a super long cadence
2) The PerfectCadence is already an estimation because we don't know the exact
frame rate.
But we can still use some approximation. For example, we can limit the length
(L) of DetectedCadence. For example, L <= 16. Note that "clamped cadence" in the
current implementation is a special case where L = 1.

Some extra notes:
- The TimeUntilGlitch will be much longer for most common combinations, e.g.
24fps at 50Hz. 
- Fractional cadence is naturally supported and we don't need to have any
special treatment for it.
- Overtime we'll still have drifts. We can still add or remove one frame from
time to time (using the existing code), but that should be much less frequent
because our cadence is more accurate.

That said, I am not sure how easy/hard it'll be to implement this. Cadence
estimation is a pure math problem and should be easy to tackle. Then for each
queued frame, we need to use the estimated cadence (an array) to decide how many
times a frame should be rendered...

I am writing this down because I feel it has a potential to simplify some
implementation, and/or improve performance because we can use cadence in more
cases. But I am pretty sure I am over simplifying a lot of things. Feel free to
ignore if it's unnecessarily complex and/or overkill.

[DaleCurtis, 2015/04/17 16:47:31]

Very astute observation! You're correct and that's the reason I designed the
fractional cadence support the way I did (ideal+actual count per frame vs global
counts). Maybe one day we can extend it for arbitrary cadence sequences.

The problem (I think) is that the math problem is an optimization problem which
can get hairy fast; but I haven't given it deep thought. I do know it is subject
to noise and thus may fluctuate similarly to BestFrameByCoverage; most
importantly in ways that the simple time based hysteresis can't account for.
We'd need to use a schmitt trigger or something similar as briananderson@
originally suggested.

Before diving in on that complexity I wanted to make sure it's necessary, which
for 3:2 hasn't been the case, see my comments on l.408 in UpdateFrameStatistics.

I may be overestimating the difficulty of solving this problem though, so I'd
love to chat and hear your thoughts :) I think it's a v2.0 type thing though as
I'm pretty sure it can only add complexity.

The reason fractional_cadence_ is it's own variable is so that EnqueueFrames()
can extend the cadence to new frames appropriately (and thus callers can use
EffectiveFramesQueued() immediately after).

+  size_t EffectiveFramesQueued() const;

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

nit: Add an empty line here.

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

Done.

+  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_; }
+
+ private:
+  friend class VideoRendererAlgorithmTest;
+
+  enum {
+    // 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.
+    kMinimumAcceptableTimeBetweenGlitchesSecs = 8

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

See comment in the previous PS.

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

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

In this case, do we need to pass in |clamped_cadence| at all? If we already know
perfect_cadence, calculating clamped_cadence should be trivial?

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

This function is first passed |frame_duration| / |render_interval| to see if it
can find a normal integer cadence, it is then given |render_interval| /
|frame_duration| to see if a fractional cadence fits. In this case |fractional|
is then set to true.

+  // cadence (1/|perfect_cadence|), |fractional| must be set to true to ensure
+  // the rendered and actual frame durations are computed correctly.

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

So when |fractional| is true, we must have |perfect_cadence < 1|? Is this
correct? Is the reverse correct as well (I guess not)?

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

No, this isn't true, this function powers two calculations; see above comment.

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

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

nit: s/frame_duration_/average_frame_duration/

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

Done.

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