1 // Copyright 2015 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #ifndef MEDIA_FILTERS_VIDEO_RENDERER_ALGORITHM_H_
6 #define MEDIA_FILTERS_VIDEO_RENDERER_ALGORITHM_H_
11 #include "base/callback.h"
12 #include "base/containers/circular_deque.h"
13 #include "base/memory/raw_ptr.h"
14 #include "base/memory/ref_counted.h"
15 #include "base/time/time.h"
16 #include "media/base/media_export.h"
17 #include "media/base/moving_average.h"
18 #include "media/base/video_frame.h"
19 #include "media/base/video_renderer.h"
20 #include "media/filters/video_cadence_estimator.h"
26 // VideoRendererAlgorithm manages a queue of VideoFrames from which it chooses
27 // frames with the goal of providing a smooth playback experience. I.e., the
28 // selection process results in the best possible uniformity for displayed frame
29 // durations over time.
31 // Clients will provide frames to VRA via EnqueueFrame() and then VRA will yield
32 // one of those frames in response to a future Render() call. Each Render()
33 // call takes a render interval which is used to compute the best frame for
34 // display during that interval.
36 // Render() calls are expected to happen on a regular basis. Failure to do so
37 // will result in suboptimal rendering experiences. If a client knows that
38 // Render() callbacks are stalled for any reason, it should tell VRA to expire
39 // frames which are unusable via RemoveExpiredFrames(); this prevents useless
40 // accumulation of stale VideoFrame objects (which are frequently quite large).
42 // The primary means of smooth frame selection is via forced integer cadence,
43 // see VideoCadenceEstimator for details on this process. In cases of non-
44 // integer cadence, the algorithm will fall back to choosing the frame which
45 // covers the most of the current render interval. If no frame covers the
46 // current interval, the least bad frame will be chosen based on its drift from
47 // the start of the interval.
49 // Combined these three approaches enforce optimal smoothness in many cases.
50 class MEDIA_EXPORT VideoRendererAlgorithm {
52 VideoRendererAlgorithm(const TimeSource::WallClockTimeCB& wall_clock_time_cb,
55 VideoRendererAlgorithm(const VideoRendererAlgorithm&) = delete;
56 VideoRendererAlgorithm& operator=(const VideoRendererAlgorithm&) = delete;
58 ~VideoRendererAlgorithm();
60 // Chooses the best frame for the interval [deadline_min, deadline_max] based
61 // on available and previously rendered frames.
63 // Under ideal circumstances the deadline interval provided to a Render() call
64 // should be directly adjacent to the deadline given to the previous Render()
65 // call with no overlap or gaps. In practice, |deadline_max| is an estimated
66 // value, which means the next |deadline_min| may overlap it slightly or have
67 // a slight gap. Gaps which exceed the length of the deadline interval are
68 // assumed to be repeated frames for the purposes of cadence detection.
70 // If provided, |frames_dropped| will be set to the number of frames which
71 // were removed from |frame_queue_|, during this call, which were never
72 // returned during a previous Render() call and are no longer suitable for
73 // rendering since their wall clock time is too far in the past.
74 scoped_refptr<VideoFrame> Render(base::TimeTicks deadline_min,
75 base::TimeTicks deadline_max,
76 size_t* frames_dropped);
78 // Removes all video frames which are unusable since their ideal render
79 // interval [timestamp, timestamp + duration] is too far away from
80 // |deadline_min| than is allowed by drift constraints.
82 // At least one frame will always remain after this call so that subsequent
83 // Render() calls have a frame to return if no new frames are enqueued before
84 // then. Returns the number of frames removed that were never rendered.
86 // Note: In cases where there is no known frame duration (i.e. perhaps a video
87 // with only a single frame), the last frame can not be expired, regardless of
88 // the given deadline. Clients must handle this case externally.
89 size_t RemoveExpiredFrames(base::TimeTicks deadline);
91 // Clients should call this if the last frame provided by Render() was never
92 // rendered; it ensures the presented cadence matches internal models. This
93 // must be called before the next Render() call.
94 void OnLastFrameDropped();
96 // Adds a frame to |frame_queue_| for consideration by Render(). Out of order
97 // timestamps will be sorted into appropriate order. Do not enqueue end of
98 // stream frames. Frames inserted prior to the last rendered frame will not
99 // be used. They will be discarded on the next call to Render(), counting as
100 // dropped frames, or by RemoveExpiredFrames(), counting as expired frames.
102 // Attempting to enqueue a frame with the same timestamp as a previous frame
103 // will result in the previous frame being replaced if it has not been
104 // rendered yet. If it has been rendered, the new frame will be dropped.
106 // EnqueueFrame() will compute the current start time and an estimated end
107 // time of the frame based on previous frames or the value of
108 // VideoFrameMetadata::FRAME_DURATION if no previous frames, so that
109 // EffectiveFramesQueued() is relatively accurate immediately after this call.
110 void EnqueueFrame(scoped_refptr<VideoFrame> frame);
112 // Removes all frames from the |frame_queue_| and clears predictors. The
113 // algorithm will be as if freshly constructed after this call. By default
114 // everything is reset, but if kPreserveNextFrameEstimates is specified, then
115 // predictors for the start time of the next frame given to EnqueueFrame()
116 // will be kept; allowing EffectiveFramesQueued() accuracy with one frame.
117 enum class ResetFlag { kEverything, kPreserveNextFrameEstimates };
118 void Reset(ResetFlag reset_flag = ResetFlag::kEverything);
120 // Returns the number of frames currently buffered which could be rendered
121 // assuming current Render() interval trends.
123 // If a cadence has been identified, this will return the number of frames
124 // which have a non-zero ideal render count.
126 // If cadence has not been identified, this will return the number of frames
127 // which have a frame end time greater than the end of the last render
128 // interval passed to Render(). Note: If Render() callbacks become suspended
129 // and the duration is unknown the last frame may never be stop counting as
130 // effective. Clients must handle this case externally.
132 // In either case, frames enqueued before the last displayed frame will not
133 // be counted as effective.
134 size_t effective_frames_queued() const { return effective_frames_queued_; }
136 // Returns an estimate of the amount of memory (in bytes) used for frames.
137 int64_t GetMemoryUsage() const;
139 // Tells the algorithm that Render() callbacks have been suspended for a known
140 // reason and such stoppage shouldn't be counted against future frames.
141 void set_time_stopped() { was_time_moving_ = false; }
143 size_t frames_queued() const { return frame_queue_.size(); }
145 // Returns the average of the duration of all frames in |frame_queue_|
146 // as measured in wall clock (not media) time.
147 base::TimeDelta average_frame_duration() const {
148 return average_frame_duration_;
151 // End time of the last frame.
152 base::TimeTicks last_frame_end_time() const {
153 return frame_queue_.back().end_time;
156 const VideoFrame& last_frame() const { return *frame_queue_.back().frame; }
158 // Current render interval.
159 base::TimeDelta render_interval() const { return render_interval_; }
161 // Method used for testing which disables frame dropping, in this mode the
162 // algorithm will never drop frames and instead always return every frame
163 // for display at least once.
164 void disable_frame_dropping() { frame_dropping_disabled_ = true; }
167 // The number of frames to store for moving average calculations. Value
168 // picked after experimenting with playback of various local media and
170 kMovingAverageSamples = 32
174 friend class VideoRendererAlgorithmTest;
176 // The determination of whether to clamp to a given cadence is based on the
177 // number of seconds before a frame would have to be dropped or repeated to
178 // compensate for reaching the maximum acceptable drift.
180 // We've chosen 8 seconds based on practical observations and the fact that it
181 // allows 29.9fps and 59.94fps in 60Hz and vice versa.
183 // Most users will not be able to see a single frame repeated or dropped every
184 // 8 seconds and certainly should notice it less than the randomly variable
186 static const int kMinimumAcceptableTimeBetweenGlitchesSecs = 8;
188 // Metadata container for enqueued frames. See |frame_queue_| below.
190 ReadyFrame(scoped_refptr<VideoFrame> frame);
191 ReadyFrame(const ReadyFrame& other);
194 // For use with std::lower_bound.
195 bool operator<(const ReadyFrame& other) const;
197 scoped_refptr<VideoFrame> frame;
199 // |start_time| is only available after UpdateFrameStatistics() has been
200 // called and |end_time| only after we have more than one frame.
201 base::TimeTicks start_time;
202 base::TimeTicks end_time;
204 // True if this frame's end time is based on the average frame duration and
205 // not the time of the next frame.
206 bool has_estimated_end_time;
208 int ideal_render_count;
213 // Updates the render count for the last rendered frame based on the number
214 // of missing intervals between Render() calls.
215 void AccountForMissedIntervals(base::TimeTicks deadline_min,
216 base::TimeTicks deadline_max);
218 // Updates the render count and wall clock timestamps for all frames in
219 // |frame_queue_|. Updates |was_time_stopped_|, |cadence_estimator_| and
220 // |frame_duration_calculator_|.
222 // Note: Wall clock time is recomputed each Render() call because it's
223 // expected that the TimeSource powering TimeSource::WallClockTimeCB will skew
224 // slightly based on the audio clock.
226 // TODO(dalecurtis): Investigate how accurate we need the wall clock times to
227 // be, so we can avoid recomputing every time (we would need to recompute when
228 // playback rate changes occur though).
229 void UpdateFrameStatistics();
231 // Updates the ideal render count for all frames in |frame_queue_| based on
232 // the cadence returned by |cadence_estimator_|. Cadence is assigned based
233 // on |frame_counter_|.
234 void UpdateCadenceForFrames();
236 // If |cadence_estimator_| has detected a valid cadence, attempts to find the
237 // next frame which should be rendered. Returns -1 if not enough frames are
238 // available for cadence selection or there is no cadence.
239 int FindBestFrameByCadence() const;
241 // Iterates over |frame_queue_| and finds the frame which covers the most of
242 // the deadline interval. If multiple frames have coverage of the interval,
243 // |second_best| will be set to the index of the frame with the next highest
244 // coverage. Returns -1 if no frame has any coverage of the current interval.
246 // Prefers the earliest frame if multiple frames have similar coverage (within
247 // a few percent of each other).
248 int FindBestFrameByCoverage(base::TimeTicks deadline_min,
249 base::TimeTicks deadline_max,
250 int* second_best) const;
252 // Iterates over |frame_queue_| and find the frame which drifts the least from
253 // |deadline_min|. There's always a best frame by drift, so the return value
254 // is always a valid frame index. |selected_frame_drift| will be set to the
255 // drift of the chosen frame.
257 // Note: Drift calculations assume contiguous frames in the time domain, so
258 // it's not possible to have a case where a frame is -10ms from |deadline_min|
259 // and another frame which is at some time after |deadline_min|. The second
260 // frame would be considered to start at -10ms before |deadline_min| and would
261 // overlap |deadline_min|, so its drift would be zero.
262 int FindBestFrameByDrift(base::TimeTicks deadline_min,
263 base::TimeDelta* selected_frame_drift) const;
265 // Calculates the drift from |deadline_min| for the given |frame_index|. If
266 // the [start_time, end_time] lies before |deadline_min| the drift is
267 // the delta between |deadline_min| and |end_time|. If the frame
268 // overlaps |deadline_min| the drift is zero. If the frame lies after
269 // |deadline_min| the drift is the delta between |deadline_min| and
271 base::TimeDelta CalculateAbsoluteDriftForFrame(base::TimeTicks deadline_min,
272 int frame_index) const;
274 // Returns the index of the first usable frame or -1 if no usable frames.
275 int FindFirstGoodFrame() const;
277 // Updates |effective_frames_queued_| which is typically called far more
278 // frequently (~4x) than the value changes. This must be called whenever
279 // frames are added or removed from the queue or when any property of a
280 // ReadyFrame within the queue changes.
281 void UpdateEffectiveFramesQueued();
283 // Computes the unclamped count of effective frames. Used by
284 // UpdateEffectiveFramesQueued().
285 size_t CountEffectiveFramesQueued() const;
287 raw_ptr<MediaLog> media_log_;
288 int out_of_order_frame_logs_ = 0;
290 // Queue of incoming frames waiting for rendering.
291 using VideoFrameQueue = base::circular_deque<ReadyFrame>;
292 VideoFrameQueue frame_queue_;
294 // Handles cadence detection and frame cadence assignments.
295 VideoCadenceEstimator cadence_estimator_;
297 // Indicates if any calls to Render() have successfully yielded a frame yet.
298 bool have_rendered_frames_;
300 // Callback used to convert media timestamps into wall clock timestamps.
301 const TimeSource::WallClockTimeCB wall_clock_time_cb_;
303 // The last |deadline_max| provided to Render(), used to predict whether
304 // frames were rendered over cadence between Render() calls.
305 base::TimeTicks last_deadline_max_;
307 // The average of the duration of all frames in |frame_queue_| as measured in
308 // wall clock (not media) time at the time of the last Render().
309 MovingAverage frame_duration_calculator_;
310 base::TimeDelta average_frame_duration_;
312 // The length of the last deadline interval given to Render(), updated at the
313 // start of Render().
314 base::TimeDelta render_interval_;
316 // The maximum acceptable drift before a frame can no longer be considered for
317 // rendering within a given interval.
318 base::TimeDelta max_acceptable_drift_;
320 // Indicates that the last call to Render() experienced a rendering glitch; it
321 // may have: under-rendered a frame, over-rendered a frame, dropped one or
322 // more frames, or chosen a frame which exceeded acceptable drift.
323 bool last_render_had_glitch_;
325 // For testing functionality which enables clockless playback of all frames,
326 // does not prevent frame dropping due to equivalent timestamps.
327 bool frame_dropping_disabled_;
329 // Tracks frames dropped during enqueue when identical timestamps are added
330 // to the queue. Callers are told about these frames during Render().
331 size_t frames_dropped_during_enqueue_;
333 // When cadence is present, we don't want to start counting against cadence
334 // until the first frame has reached its presentation time.
337 // The frame number of the last rendered frame; incremented for every frame
338 // rendered and every frame dropped or expired since the last rendered frame.
340 // Given to |cadence_estimator_| when assigning cadence values to the
341 // ReadyFrameQueue. Cleared when a new cadence is detected.
342 uint64_t cadence_frame_counter_;
344 // Indicates if time was moving, set to the return value from
345 // UpdateFrameStatistics() during Render() or externally by
346 // set_time_stopped().
347 bool was_time_moving_;
349 // Current number of effective frames in the |frame_queue_|. Updated by calls
350 // to UpdateEffectiveFramesQueued() whenever the |frame_queue_| is changed.
351 size_t effective_frames_queued_;
356 #endif // MEDIA_FILTERS_VIDEO_RENDERER_ALGORITHM_H_