media/filters/video_renderer_algorithm.cc

   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.
   4
   5 #include "media/filters/video_renderer_algorithm.h"
   6
   7 #include <limits>
   8
   9 #include "base/ranges/algorithm.h"
  10 #include "media/base/media_log.h"
  11
  12 namespace media {
  13
  14 const int kMaxOutOfOrderFrameLogs = 10;
  15
  16 VideoRendererAlgorithm::ReadyFrame::ReadyFrame(
  17     scoped_refptr<VideoFrame> ready_frame)
  18     : frame(std::move(ready_frame)),
  19       has_estimated_end_time(true),
  20       ideal_render_count(0),
  21       render_count(0),
  22       drop_count(0) {}
  23
  24 VideoRendererAlgorithm::ReadyFrame::ReadyFrame(const ReadyFrame& other) =
  25     default;
  26
  27 VideoRendererAlgorithm::ReadyFrame::~ReadyFrame() = default;
  28
  29 bool VideoRendererAlgorithm::ReadyFrame::operator<(
  30     const ReadyFrame& other) const {
  31   return frame->timestamp() < other.frame->timestamp();
  32 }
  33
  34 VideoRendererAlgorithm::VideoRendererAlgorithm(
  35     const TimeSource::WallClockTimeCB& wall_clock_time_cb,
  36     MediaLog* media_log)
  37     : media_log_(media_log),
  38       cadence_estimator_(
  39           base::Seconds(kMinimumAcceptableTimeBetweenGlitchesSecs)),
  40       wall_clock_time_cb_(wall_clock_time_cb),
  41       frame_duration_calculator_(kMovingAverageSamples),
  42       frame_dropping_disabled_(false) {
  43   DCHECK(wall_clock_time_cb_);
  44   Reset();
  45 }
  46
  47 VideoRendererAlgorithm::~VideoRendererAlgorithm() = default;
  48
  49 scoped_refptr<VideoFrame> VideoRendererAlgorithm::Render(
  50     base::TimeTicks deadline_min,
  51     base::TimeTicks deadline_max,
  52     size_t* frames_dropped) {
  53   DCHECK_LE(deadline_min, deadline_max);
  54
  55   if (frame_queue_.empty())
  56     return nullptr;
  57
  58   if (frames_dropped)
  59     *frames_dropped = frames_dropped_during_enqueue_;
  60   frames_dropped_during_enqueue_ = 0;
  61   have_rendered_frames_ = true;
  62
  63   // Step 1: Update the current render interval for subroutines.
  64   render_interval_ = deadline_max - deadline_min;
  65
  66   // Step 2: Figure out if any intervals have been skipped since the last call
  67   // to Render().  If so, we assume the last frame provided was rendered during
  68   // those intervals and adjust its render count appropriately.
  69   AccountForMissedIntervals(deadline_min, deadline_max);
  70
  71   // Step 3: Update the wall clock timestamps and frame duration estimates for
  72   // all frames currently in the |frame_queue_|.
  73   UpdateFrameStatistics();
  74   const bool have_known_duration = average_frame_duration_.is_positive();
  75   if (!was_time_moving_ || !have_known_duration || render_interval_.is_zero()) {
  76     ReadyFrame& ready_frame = frame_queue_.front();
  77     DCHECK(ready_frame.frame);
  78     ++ready_frame.render_count;
  79     UpdateEffectiveFramesQueued();
  80
  81     // If time stops, we should reset the |first_frame_| marker.
  82     if (!was_time_moving_)
  83       first_frame_ = true;
  84     return ready_frame.frame;
  85   }
  86
  87   last_deadline_max_ = deadline_max;
  88   base::TimeDelta selected_frame_drift, cadence_frame_drift;
  89
  90   // Step 4: Attempt to find the best frame by cadence.
  91   const int cadence_frame = FindBestFrameByCadence();
  92   int frame_to_render = cadence_frame;
  93   if (frame_to_render >= 0) {
  94     cadence_frame_drift = selected_frame_drift =
  95         CalculateAbsoluteDriftForFrame(deadline_min, frame_to_render);
  96   }
  97
  98   // Step 5: If no frame could be found by cadence or the selected frame exceeds
  99   // acceptable drift, try to find the best frame by coverage of the deadline.
 100   if (frame_to_render < 0 || selected_frame_drift > max_acceptable_drift_) {
 101     int second_best_by_coverage = -1;
 102     const int best_by_coverage = FindBestFrameByCoverage(
 103         deadline_min, deadline_max, &second_best_by_coverage);
 104
 105     // If the frame was previously selected based on cadence, we're only here
 106     // because the drift is too large, so even if the cadence frame has the best
 107     // coverage, fallback to the second best by coverage if it has better drift.
 108     if (frame_to_render == best_by_coverage && second_best_by_coverage >= 0 &&
 109         CalculateAbsoluteDriftForFrame(deadline_min, second_best_by_coverage) <=
 110             selected_frame_drift) {
 111       frame_to_render = second_best_by_coverage;
 112     } else {
 113       frame_to_render = best_by_coverage;
 114     }
 115
 116     if (frame_to_render >= 0) {
 117       selected_frame_drift =
 118           CalculateAbsoluteDriftForFrame(deadline_min, frame_to_render);
 119     }
 120   }
 121
 122   // Step 6: If _still_ no frame could be found by coverage, try to choose the
 123   // least crappy option based on the drift from the deadline. If we're here the
 124   // selection is going to be bad because it means no suitable frame has any
 125   // coverage of the deadline interval.
 126   if (frame_to_render < 0 || selected_frame_drift > max_acceptable_drift_)
 127     frame_to_render = FindBestFrameByDrift(deadline_min, &selected_frame_drift);
 128
 129   const bool ignored_cadence_frame =
 130       cadence_frame >= 0 && frame_to_render != cadence_frame;
 131   if (ignored_cadence_frame) {
 132     DVLOG(2) << "Cadence frame "
 133              << frame_queue_[cadence_frame].frame->timestamp() << " ("
 134              << cadence_frame << ") overridden by drift: "
 135              << cadence_frame_drift.InMillisecondsF() << "ms, using "
 136              << frame_queue_[frame_to_render].frame->timestamp() << "("
 137              << frame_to_render << ") instead.";
 138   }
 139
 140   last_render_had_glitch_ = selected_frame_drift > max_acceptable_drift_;
 141   DVLOG_IF(2, last_render_had_glitch_)
 142       << "Frame drift is too far: " << selected_frame_drift.InMillisecondsF()
 143       << "ms";
 144
 145   DCHECK_GE(frame_to_render, 0);
 146
 147   // Drop some debugging information if a frame had poor cadence.
 148   if (cadence_estimator_.has_cadence()) {
 149     const ReadyFrame& last_frame_info = frame_queue_.front();
 150     if (frame_to_render &&
 151         last_frame_info.render_count < last_frame_info.ideal_render_count) {
 152       last_render_had_glitch_ = true;
 153       DVLOG(2) << "Under-rendered frame " << last_frame_info.frame->timestamp()
 154                << "; only " << last_frame_info.render_count
 155                << " times instead of " << last_frame_info.ideal_render_count;
 156     } else if (!frame_to_render &&
 157                last_frame_info.render_count >=
 158                    last_frame_info.ideal_render_count) {
 159       DVLOG(2) << "Over-rendered frame " << last_frame_info.frame->timestamp()
 160                << "; rendered " << last_frame_info.render_count + 1
 161                << " times instead of " << last_frame_info.ideal_render_count;
 162       last_render_had_glitch_ = true;
 163     }
 164   }
 165
 166   // Step 7: Drop frames which occur prior to the frame to be rendered. If any
 167   // frame unexpectedly has a zero render count it should be reported as
 168   // dropped. When using cadence some frames may be expected to be skipped and
 169   // should not be counted as dropped.
 170   if (frame_to_render > 0) {
 171     if (frames_dropped) {
 172       for (int i = 0; i < frame_to_render; ++i) {
 173         const ReadyFrame& frame = frame_queue_[i];
 174
 175         // If a frame was ever rendered, don't count it as dropped.
 176         if (frame.render_count != frame.drop_count)
 177           continue;
 178
 179         // If we expected to never render the frame, don't count it as dropped.
 180         if (cadence_estimator_.has_cadence() && !frame.ideal_render_count)
 181           continue;
 182
 183         // If frame dropping is disabled, ignore the results of the algorithm
 184         // and return the earliest unrendered frame.
 185         if (frame_dropping_disabled_) {
 186           frame_to_render = i;
 187           break;
 188         }
 189
 190         DVLOG(2) << "Dropping unrendered (or always dropped) frame "
 191                  << frame.frame->timestamp()
 192                  << ", wall clock: " << frame.start_time.ToInternalValue()
 193                  << " (" << frame.render_count << ", " << frame.drop_count
 194                  << ")";
 195         ++(*frames_dropped);
 196         if (!cadence_estimator_.has_cadence() || frame.ideal_render_count)
 197           last_render_had_glitch_ = true;
 198       }
 199     }
 200
 201     // Increment the frame counter for all frames removed after the last
 202     // rendered frame.
 203     cadence_frame_counter_ += frame_to_render;
 204     frame_queue_.erase(frame_queue_.begin(),
 205                        frame_queue_.begin() + frame_to_render);
 206   }
 207
 208   if (last_render_had_glitch_ && !first_frame_) {
 209     DVLOG(2) << "Deadline: [" << deadline_min.ToInternalValue() << ", "
 210              << deadline_max.ToInternalValue()
 211              << "], Interval: " << render_interval_.InMicroseconds()
 212              << ", Duration: " << average_frame_duration_.InMicroseconds();
 213   }
 214
 215   // Step 8: Congratulations, the frame selection gauntlet has been passed!
 216   if (first_frame_ && frame_to_render > 0)
 217     first_frame_ = false;
 218
 219   ++frame_queue_.front().render_count;
 220
 221   // Once we reach a glitch in our cadence sequence, reset the base frame number
 222   // used for defining the cadence sequence; the sequence restarts from the
 223   // selected frame.
 224   if (ignored_cadence_frame) {
 225     cadence_frame_counter_ = 0;
 226     UpdateCadenceForFrames();
 227   }
 228
 229   UpdateEffectiveFramesQueued();
 230   DCHECK(frame_queue_.front().frame);
 231   return frame_queue_.front().frame;
 232 }
 233
 234 size_t VideoRendererAlgorithm::RemoveExpiredFrames(base::TimeTicks deadline) {
 235   // Update |last_deadline_max_| if it's no longer accurate; this should always
 236   // be done or EffectiveFramesQueued() may never expire the last frame.
 237   if (deadline > last_deadline_max_)
 238     last_deadline_max_ = deadline;
 239
 240   if (frame_queue_.empty())
 241     return 0;
 242
 243   // Even though we may not be able to remove anything due to having only one
 244   // frame, correct any estimates which may have been set during EnqueueFrame().
 245   UpdateFrameStatistics();
 246   UpdateEffectiveFramesQueued();
 247
 248   // We always leave at least one frame in the queue, so if there's only one
 249   // frame there's nothing we can expire.
 250   if (frame_queue_.size() == 1)
 251     return 0;
 252
 253   DCHECK_GT(average_frame_duration_, base::TimeDelta());
 254
 255   // Expire everything before the first good frame or everything but the last
 256   // frame if there is no good frame.
 257   const int first_good_frame = FindFirstGoodFrame();
 258   const size_t frames_to_expire =
 259       first_good_frame < 0 ? frame_queue_.size() - 1 : first_good_frame;
 260   if (!frames_to_expire)
 261     return 0;
 262
 263   size_t frames_dropped_without_rendering = 0;
 264   for (size_t i = 0; i < frames_to_expire; ++i) {
 265     const ReadyFrame& frame = frame_queue_[i];
 266
 267     // Don't count frames that are intentionally dropped by cadence as dropped.
 268     if (frame.render_count == frame.drop_count &&
 269         (!cadence_estimator_.has_cadence() || frame.ideal_render_count)) {
 270       ++frames_dropped_without_rendering;
 271     }
 272   }
 273
 274   cadence_frame_counter_ += frames_to_expire;
 275   frame_queue_.erase(frame_queue_.begin(),
 276                      frame_queue_.begin() + frames_to_expire);
 277   return frames_dropped_without_rendering;
 278 }
 279
 280 void VideoRendererAlgorithm::OnLastFrameDropped() {
 281   // Since compositing is disconnected from the algorithm, the algorithm may be
 282   // Reset() in between ticks of the compositor, so discard notifications which
 283   // are invalid.
 284   if (!have_rendered_frames_ || frame_queue_.empty())
 285     return;
 286
 287   // If frames were expired by RemoveExpiredFrames() this count may be zero when
 288   // the OnLastFrameDropped() call comes in.
 289   ReadyFrame& frame = frame_queue_.front();
 290   if (!frame.render_count)
 291     return;
 292
 293   ++frame.drop_count;
 294   DCHECK_LE(frame.drop_count, frame.render_count);
 295   UpdateEffectiveFramesQueued();
 296 }
 297
 298 void VideoRendererAlgorithm::Reset(ResetFlag reset_flag) {
 299   out_of_order_frame_logs_ = 0;
 300   frames_dropped_during_enqueue_ = 0;
 301   have_rendered_frames_ = last_render_had_glitch_ = false;
 302   render_interval_ = base::TimeDelta();
 303   frame_queue_.clear();
 304   cadence_estimator_.Reset();
 305   if (reset_flag != ResetFlag::kPreserveNextFrameEstimates) {
 306     average_frame_duration_ = base::TimeDelta();
 307     last_deadline_max_ = base::TimeTicks();
 308     frame_duration_calculator_.Reset();
 309   }
 310   first_frame_ = true;
 311   effective_frames_queued_ = cadence_frame_counter_ = 0;
 312   was_time_moving_ = false;
 313
 314   // Default to ATSC IS/191 recommendations for maximum acceptable drift before
 315   // we have enough frames to base the maximum on frame duration.
 316   max_acceptable_drift_ = base::Milliseconds(15);
 317 }
 318
 319 int64_t VideoRendererAlgorithm::GetMemoryUsage() const {
 320   int64_t allocation_size = 0;
 321   for (const auto& ready_frame : frame_queue_) {
 322     allocation_size += VideoFrame::AllocationSize(
 323         ready_frame.frame->format(), ready_frame.frame->coded_size());
 324   }
 325   return allocation_size;
 326 }
 327
 328 void VideoRendererAlgorithm::EnqueueFrame(scoped_refptr<VideoFrame> frame) {
 329   DCHECK(frame);
 330   DCHECK(!frame->metadata().end_of_stream);
 331
 332   // Note: Not all frames have duration. E.g., this class is used with WebRTC
 333   // which does not provide duration information for its frames.
 334   base::TimeDelta metadata_frame_duration =
 335       frame->metadata().frame_duration.value_or(base::TimeDelta());
 336   auto timestamp = frame->timestamp();
 337   ReadyFrame ready_frame(std::move(frame));
 338   auto it = frame_queue_.empty()
 339                 ? frame_queue_.end()
 340                 : std::lower_bound(frame_queue_.begin(), frame_queue_.end(),
 341                                    ready_frame);
 342   DCHECK_GE(it - frame_queue_.begin(), 0);
 343
 344   // Drop any frames inserted before or at the last rendered frame if we've
 345   // already rendered any frames.
 346   const size_t new_frame_index = it - frame_queue_.begin();
 347   if (new_frame_index <= 0 && have_rendered_frames_) {
 348     LIMITED_MEDIA_LOG(INFO, media_log_, out_of_order_frame_logs_,
 349                       kMaxOutOfOrderFrameLogs)
 350         << "Dropping frame with timestamp " << timestamp
 351         << ", which is earlier than the last rendered frame ("
 352         << frame_queue_.front().frame->timestamp() << ").";
 353     ++frames_dropped_during_enqueue_;
 354     return;
 355   }
 356
 357   // Drop any frames which are less than a millisecond apart in media time (even
 358   // those with timestamps matching an already enqueued frame), there's no way
 359   // we can reasonably render these frames; it's effectively a 1000fps limit.
 360   const base::TimeDelta delta = std::min(
 361       new_frame_index < frame_queue_.size()
 362           ? frame_queue_[new_frame_index].frame->timestamp() - timestamp
 363           : base::TimeDelta::Max(),
 364       new_frame_index > 0
 365           ? timestamp - frame_queue_[new_frame_index - 1].frame->timestamp()
 366           : base::TimeDelta::Max());
 367   if (delta < base::Milliseconds(1)) {
 368     DVLOG(2) << "Dropping frame too close to an already enqueued frame: "
 369              << delta.InMicroseconds() << " us";
 370     ++frames_dropped_during_enqueue_;
 371     return;
 372   }
 373
 374   // Calculate an accurate start time and an estimated end time if possible for
 375   // the new frame; this allows EffectiveFramesQueued() to be relatively correct
 376   // immediately after a new frame is queued.
 377   std::vector<base::TimeDelta> media_timestamps(1, timestamp);
 378
 379   // If there are not enough frames to estimate duration based on end time, ask
 380   // the WallClockTimeCB to convert the estimated frame duration into wall clock
 381   // time.
 382   //
 383   // Note: This duration value is not compensated for playback rate and
 384   // thus is different than |average_frame_duration_| which is compensated.
 385   if (!frame_duration_calculator_.Count() &&
 386       metadata_frame_duration.is_positive()) {
 387     media_timestamps.push_back(timestamp + metadata_frame_duration);
 388   }
 389
 390   std::vector<base::TimeTicks> wall_clock_times;
 391   base::TimeDelta wallclock_duration;
 392   wall_clock_time_cb_.Run(media_timestamps, &wall_clock_times);
 393   ready_frame.start_time = wall_clock_times[0];
 394   if (frame_duration_calculator_.Count()) {
 395     ready_frame.end_time = ready_frame.start_time + average_frame_duration_;
 396     wallclock_duration = average_frame_duration_;
 397   } else if (wall_clock_times.size() > 1u) {
 398     ready_frame.end_time = wall_clock_times[1];
 399     wallclock_duration = ready_frame.end_time - ready_frame.start_time;
 400   }
 401
 402   ready_frame.frame->metadata().wallclock_frame_duration = wallclock_duration;
 403
 404   // The vast majority of cases should always append to the back, but in rare
 405   // circumstance we get out of order timestamps, http://crbug.com/386551.
 406   if (it != frame_queue_.end()) {
 407     LIMITED_MEDIA_LOG(INFO, media_log_, out_of_order_frame_logs_,
 408                       kMaxOutOfOrderFrameLogs)
 409         << "Decoded frame with timestamp " << timestamp << " is out of order.";
 410   }
 411   frame_queue_.insert(it, ready_frame);
 412
 413   // Project the current cadence calculations to include the new frame.  These
 414   // may not be accurate until the next Render() call.  These updates are done
 415   // to ensure EffectiveFramesQueued() returns a semi-reliable result.
 416   if (cadence_estimator_.has_cadence())
 417     UpdateCadenceForFrames();
 418
 419   UpdateEffectiveFramesQueued();
 420 #ifndef NDEBUG
 421   // Verify sorted order in debug mode.
 422   for (size_t i = 0; i < frame_queue_.size() - 1; ++i) {
 423     DCHECK(frame_queue_[i].frame->timestamp() <=
 424            frame_queue_[i + 1].frame->timestamp());
 425   }
 426 #endif
 427 }
 428
 429 void VideoRendererAlgorithm::AccountForMissedIntervals(
 430     base::TimeTicks deadline_min,
 431     base::TimeTicks deadline_max) {
 432   if (last_deadline_max_.is_null() || deadline_min <= last_deadline_max_ ||
 433       !have_rendered_frames_ || !was_time_moving_ ||
 434       render_interval_.is_zero()) {
 435     return;
 436   }
 437
 438   DCHECK_GT(render_interval_, base::TimeDelta());
 439   const int64_t render_cycle_count =
 440       (deadline_min - last_deadline_max_).IntDiv(render_interval_);
 441
 442   // In the ideal case this value will be zero.
 443   if (!render_cycle_count)
 444     return;
 445
 446   DVLOG(2) << "Missed " << render_cycle_count << " Render() intervals.";
 447
 448   // Only update render count if the frame was rendered at all; it may not have
 449   // been if the frame is at the head because we haven't rendered anything yet
 450   // or because previous frames were removed via RemoveExpiredFrames().
 451   ReadyFrame& ready_frame = frame_queue_.front();
 452   if (!ready_frame.render_count)
 453     return;
 454
 455   // If the frame was never really rendered since it was dropped each attempt,
 456   // we need to increase the drop count as well to match the new render count.
 457   // Otherwise we won't properly count the frame as dropped when it's discarded.
 458   // We always update the render count so FindBestFrameByCadence() can properly
 459   // account for potentially over-rendered frames.
 460   if (ready_frame.render_count == ready_frame.drop_count)
 461     ready_frame.drop_count += render_cycle_count;
 462   ready_frame.render_count += render_cycle_count;
 463 }
 464
 465 void VideoRendererAlgorithm::UpdateFrameStatistics() {
 466   DCHECK(!frame_queue_.empty());
 467
 468   // Figure out all current ready frame times at once.
 469   std::vector<base::TimeDelta> media_timestamps;
 470   media_timestamps.reserve(frame_queue_.size());
 471   for (const auto& ready_frame : frame_queue_)
 472     media_timestamps.push_back(ready_frame.frame->timestamp());
 473
 474   // If available, always use the last frame's metadata duration to estimate the
 475   // end time for that frame. This is useful when playback ends on long frame
 476   // duration content.
 477   //
 478   // Note: Not all frames have duration. E.g., this class is used with WebRTC
 479   // which does not provide duration information for its frames.
 480   bool have_metadata_duration = false;
 481   {
 482     const auto& last_frame = frame_queue_.back().frame;
 483     base::TimeDelta metadata_frame_duration =
 484         last_frame->metadata().frame_duration.value_or(base::TimeDelta());
 485     if (metadata_frame_duration.is_positive()) {
 486       have_metadata_duration = true;
 487       media_timestamps.push_back(last_frame->timestamp() +
 488                                  metadata_frame_duration);
 489     }
 490   }
 491
 492   std::vector<base::TimeTicks> wall_clock_times;
 493   was_time_moving_ =
 494       wall_clock_time_cb_.Run(media_timestamps, &wall_clock_times);
 495   DCHECK_EQ(wall_clock_times.size(),
 496             frame_queue_.size() + (have_metadata_duration ? 1 : 0));
 497
 498   // Transfer the converted wall clock times into our frame queue. Never process
 499   // the last frame in this loop; the last frame timing is handled below.
 500   for (size_t i = 0; i < frame_queue_.size() - 1; ++i) {
 501     ReadyFrame& frame = frame_queue_[i];
 502
 503     // Whenever a frame is added to the queue, |has_estimated_end_time| is true;
 504     // this remains true until we receive a later frame -- from which we use its
 505     // timestamp to assign the true |end_time| for the previous frame.
 506     //
 507     // So a new sample can always be determined by the |has_estimated_end_time|
 508     // flag and the fact that the frame is being processed in this loop which
 509     // never processes the last (and thus always estimated) frame.
 510     const bool new_sample = frame.has_estimated_end_time;
 511
 512     frame.start_time = wall_clock_times[i];
 513     frame.end_time = wall_clock_times[i + 1];
 514     frame.has_estimated_end_time = false;
 515     if (new_sample)
 516       frame_duration_calculator_.AddSample(frame.end_time - frame.start_time);
 517   }
 518
 519   base::TimeDelta deviation;
 520   if (frame_duration_calculator_.Count()) {
 521     // Compute |average_frame_duration_|, a moving average of the last few
 522     // frames; see kMovingAverageSamples for the exact number.
 523     average_frame_duration_ = frame_duration_calculator_.Mean();
 524     deviation = frame_duration_calculator_.Deviation();
 525   }
 526
 527   if (have_metadata_duration) {
 528     auto& frame = frame_queue_.back();
 529     frame.start_time = wall_clock_times.end()[-2];
 530     frame.end_time = wall_clock_times.end()[-1];
 531
 532     // This path will be taken for frames after the very first, but we only want
 533     // to use our estimate of |average_frame_duration_| when we have no samples
 534     // in |frame_duration_calculator_| -- since it's a more accurate reflection
 535     // of the per-frame on screen time.
 536     if (!frame_duration_calculator_.Count()) {
 537       average_frame_duration_ = frame.end_time - frame.start_time;
 538       if (average_frame_duration_.is_zero())
 539         return;
 540     }
 541   } else {
 542     frame_queue_.back().start_time = wall_clock_times.back();
 543
 544     // If |have_metadata_duration| is false and we don't have any subsequent
 545     // frames, we can't continue processing since the cadence estimate requires
 546     // |average_frame_duration_| and |deviation| to be non-zero.
 547     if (!frame_duration_calculator_.Count()) {
 548       return;
 549     }
 550
 551     // Update the frame end time for the last frame based on the average.
 552     frame_queue_.back().end_time =
 553         frame_queue_.back().start_time + average_frame_duration_;
 554   }
 555
 556   // ITU-R BR.265 recommends a maximum acceptable drift of +/- half of the frame
 557   // duration; there are other asymmetric, more lenient measures, that we're
 558   // forgoing in favor of simplicity.
 559   //
 560   // We'll always allow at least 16.66ms of drift since literature suggests it's
 561   // well below the floor of detection and is high enough to ensure stability
 562   // for 60fps content.
 563   max_acceptable_drift_ =
 564       std::max(average_frame_duration_ / 2, base::Seconds(1.0 / 60));
 565
 566   // If we were called via RemoveExpiredFrames() and Render() was never called,
 567   // we may not have a render interval yet.
 568   if (render_interval_.is_zero())
 569     return;
 570
 571   const bool cadence_changed = cadence_estimator_.UpdateCadenceEstimate(
 572       render_interval_, average_frame_duration_, deviation,
 573       max_acceptable_drift_);
 574
 575   // No need to update cadence if there's been no change; cadence will be set
 576   // as frames are added to the queue.
 577   if (!cadence_changed)
 578     return;
 579
 580   cadence_frame_counter_ = 0;
 581   UpdateCadenceForFrames();
 582 }
 583
 584 void VideoRendererAlgorithm::UpdateCadenceForFrames() {
 585   for (size_t i = 0; i < frame_queue_.size(); ++i) {
 586     // It's always okay to adjust the ideal render count, since the cadence
 587     // selection method will still count its current render count towards
 588     // cadence selection.
 589     frame_queue_[i].ideal_render_count =
 590         cadence_estimator_.has_cadence()
 591             ? cadence_estimator_.GetCadenceForFrame(cadence_frame_counter_ + i)
 592             : 0;
 593   }
 594 }
 595
 596 int VideoRendererAlgorithm::FindBestFrameByCadence() const {
 597   DCHECK(!frame_queue_.empty());
 598   if (!cadence_estimator_.has_cadence())
 599     return -1;
 600
 601   DCHECK(!frame_queue_.empty());
 602   DCHECK(cadence_estimator_.has_cadence());
 603   const ReadyFrame& current_frame = frame_queue_.front();
 604
 605   // If the current frame is below cadence, we should prefer it.
 606   if (current_frame.render_count < current_frame.ideal_render_count)
 607     return 0;
 608
 609   // If the current frame is on cadence or over cadence, find the next frame
 610   // with a positive ideal render count.
 611   for (size_t i = 1; i < frame_queue_.size(); ++i) {
 612     if (frame_queue_[i].ideal_render_count > 0)
 613       return i;
 614   }
 615
 616   // We don't have enough frames to find a better once by cadence.
 617   return -1;
 618 }
 619
 620 int VideoRendererAlgorithm::FindBestFrameByCoverage(
 621     base::TimeTicks deadline_min,
 622     base::TimeTicks deadline_max,
 623     int* second_best) const {
 624   DCHECK(!frame_queue_.empty());
 625
 626   // Find the frame which covers the most of the interval [deadline_min,
 627   // deadline_max]. Frames outside of the interval are considered to have no
 628   // coverage, while those which completely overlap the interval have complete
 629   // coverage.
 630   int best_frame_by_coverage = -1;
 631   base::TimeDelta best_coverage;
 632   std::vector<base::TimeDelta> coverage(frame_queue_.size(), base::TimeDelta());
 633   for (size_t i = 0; i < frame_queue_.size(); ++i) {
 634     const ReadyFrame& frame = frame_queue_[i];
 635
 636     // Frames which start after the deadline interval have zero coverage.
 637     if (frame.start_time > deadline_max)
 638       break;
 639
 640     // Clamp frame end times to a maximum of |deadline_max|.
 641     const base::TimeTicks end_time = std::min(deadline_max, frame.end_time);
 642
 643     // Frames entirely before the deadline interval have zero coverage.
 644     if (end_time < deadline_min)
 645       continue;
 646
 647     // If we're here, the current frame overlaps the deadline in some way; so
 648     // compute the duration of the interval which is covered.
 649     const base::TimeDelta duration =
 650         end_time - std::max(deadline_min, frame.start_time);
 651
 652     coverage[i] = duration;
 653     if (coverage[i] > best_coverage) {
 654       best_frame_by_coverage = i;
 655       best_coverage = coverage[i];
 656     }
 657   }
 658
 659   // Find the second best frame by coverage; done by zeroing the coverage for
 660   // the previous best and recomputing the maximum.
 661   *second_best = -1;
 662   if (best_frame_by_coverage >= 0) {
 663     coverage[best_frame_by_coverage] = base::TimeDelta();
 664     auto it = std::max_element(coverage.begin(), coverage.end());
 665     if (it->is_positive())
 666       *second_best = it - coverage.begin();
 667   }
 668
 669   // If two frames have coverage within half a millisecond, prefer the earliest
 670   // frame as having the best coverage.  Value chosen via experimentation to
 671   // ensure proper coverage calculation for 24fps in 60Hz where +/- 100us of
 672   // jitter is present within the |render_interval_|. At 60Hz this works out to
 673   // an allowed jitter of 3%.
 674   const base::TimeDelta kAllowableJitter = base::Microseconds(500);
 675   if (*second_best >= 0 && best_frame_by_coverage > *second_best &&
 676       (best_coverage - coverage[*second_best]).magnitude() <=
 677           kAllowableJitter) {
 678     std::swap(best_frame_by_coverage, *second_best);
 679   }
 680
 681   // TODO(dalecurtis): We may want to make a better decision about what to do
 682   // when multiple frames have equivalent coverage over an interval.  Jitter in
 683   // the render interval may result in irregular frame selection which may be
 684   // visible to a viewer.
 685   //
 686   // 23.974fps and 24fps in 60Hz are the most common susceptible rates, so
 687   // extensive tests have been added to ensure these cases work properly.
 688
 689   return best_frame_by_coverage;
 690 }
 691
 692 int VideoRendererAlgorithm::FindBestFrameByDrift(
 693     base::TimeTicks deadline_min,
 694     base::TimeDelta* selected_frame_drift) const {
 695   DCHECK(!frame_queue_.empty());
 696
 697   int best_frame_by_drift = -1;
 698   *selected_frame_drift = base::TimeDelta::Max();
 699
 700   for (size_t i = 0; i < frame_queue_.size(); ++i) {
 701     const base::TimeDelta drift =
 702         CalculateAbsoluteDriftForFrame(deadline_min, i);
 703     // We use <= here to prefer the latest frame with minimum drift.
 704     if (drift <= *selected_frame_drift) {
 705       *selected_frame_drift = drift;
 706       best_frame_by_drift = i;
 707     }
 708   }
 709
 710   return best_frame_by_drift;
 711 }
 712
 713 base::TimeDelta VideoRendererAlgorithm::CalculateAbsoluteDriftForFrame(
 714     base::TimeTicks deadline_min,
 715     int frame_index) const {
 716   const ReadyFrame& frame = frame_queue_[frame_index];
 717   // If the frame lies before the deadline, compute the delta against the end
 718   // of the frame's duration.
 719   if (frame.end_time < deadline_min)
 720     return deadline_min - frame.end_time;
 721
 722   // If the frame lies after the deadline, compute the delta against the frame's
 723   // start time.
 724   if (frame.start_time > deadline_min)
 725     return frame.start_time - deadline_min;
 726
 727   // Drift is zero for frames which overlap the deadline interval.
 728   DCHECK_GE(deadline_min, frame.start_time);
 729   DCHECK_GE(frame.end_time, deadline_min);
 730   return base::TimeDelta();
 731 }
 732
 733 void VideoRendererAlgorithm::UpdateEffectiveFramesQueued() {
 734   if (frame_queue_.empty() || average_frame_duration_.is_zero() ||
 735       last_deadline_max_.is_null()) {
 736     effective_frames_queued_ = frame_queue_.size();
 737     return;
 738   }
 739
 740   // Determine the lower bound of the number of effective queues first.
 741   // Normally, this is 0.
 742   size_t min_frames_queued = 0;
 743
 744   // If frame dropping is disabled, the lower bound is the number of frames
 745   // that were not rendered yet.
 746   if (frame_dropping_disabled_) {
 747     min_frames_queued =
 748         base::ranges::count(frame_queue_, 0, &ReadyFrame::render_count);
 749   }
 750
 751   // Next, see if can report more frames as queued.
 752   effective_frames_queued_ =
 753       std::max(min_frames_queued, CountEffectiveFramesQueued());
 754 }
 755
 756 int VideoRendererAlgorithm::FindFirstGoodFrame() const {
 757   const auto minimum_start_time =
 758       cadence_estimator_.has_cadence()
 759           ? last_deadline_max_ - max_acceptable_drift_
 760           : last_deadline_max_;
 761
 762   size_t start_index = 0;
 763   for (; start_index < frame_queue_.size(); ++start_index) {
 764     const ReadyFrame& frame = frame_queue_[start_index];
 765     if ((!cadence_estimator_.has_cadence() ||
 766          frame.render_count < frame.ideal_render_count) &&
 767         (frame.end_time.is_null() || frame.end_time > minimum_start_time)) {
 768       break;
 769     }
 770   }
 771
 772   return start_index == frame_queue_.size() ? -1 : start_index;
 773 }
 774
 775 size_t VideoRendererAlgorithm::CountEffectiveFramesQueued() const {
 776   const int start_index = FindFirstGoodFrame();
 777   if (start_index < 0)
 778     return 0;
 779
 780   if (!cadence_estimator_.has_cadence())
 781     return frame_queue_.size() - start_index;
 782
 783   // We should ignore zero cadence frames in our effective frame count.
 784   size_t renderable_frame_count = 0;
 785   for (size_t i = start_index; i < frame_queue_.size(); ++i) {
 786     if (frame_queue_[i].ideal_render_count)
 787       ++renderable_frame_count;
 788   }
 789   return renderable_frame_count;
 790 }
 791
 792 }  // namespace media