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