video_renderer_algorithm.h 16 KB

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