1// Copyright (c) 2013 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#include "content/browser/media/capture/video_capture_oracle.h" 6 7#include <algorithm> 8 9#include "base/debug/trace_event.h" 10#include "base/format_macros.h" 11#include "base/strings/stringprintf.h" 12 13namespace content { 14 15namespace { 16 17// This value controls how many redundant, timer-base captures occur when the 18// content is static. Redundantly capturing the same frame allows iterative 19// quality enhancement, and also allows the buffer to fill in "buffered mode". 20// 21// TODO(nick): Controlling this here is a hack and a layering violation, since 22// it's a strategy specific to the WebRTC consumer, and probably just papers 23// over some frame dropping and quality bugs. It should either be controlled at 24// a higher level, or else redundant frame generation should be pushed down 25// further into the WebRTC encoding stack. 26const int kNumRedundantCapturesOfStaticContent = 200; 27 28// These specify the minimum/maximum amount of recent event history to examine 29// to detect animated content. If the values are too low, there is a greater 30// risk of false-positive detections and low accuracy. If they are too high, 31// the the implementation will be slow to lock-in/out, and also will not react 32// well to mildly-variable frame rate content (e.g., 25 +/- 1 FPS). 33// 34// These values were established by experimenting with a wide variety of 35// scenarios, including 24/25/30 FPS videos, 60 FPS WebGL demos, and the 36// transitions between static and animated content. 37const int kMinObservationWindowMillis = 1000; 38const int kMaxObservationWindowMillis = 2000; 39 40// The maximum amount of time that can elapse before declaring two subsequent 41// events as "not animating." This is the same value found in 42// cc::FrameRateCounter. 43const int kNonAnimatingThresholdMillis = 250; // 4 FPS 44 45// The slowest that content can be animating in order for AnimatedContentSampler 46// to lock-in. This is the threshold at which the "smoothness" problem is no 47// longer relevant. 48const int kMaxLockInPeriodMicros = 83333; // 12 FPS 49 50// The amount of time over which to fully correct the drift of the rewritten 51// frame timestamps from the presentation event timestamps. The lower the 52// value, the higher the variance in frame timestamps. 53const int kDriftCorrectionMillis = 6000; 54 55// Given the amount of time between frames, compare to the expected amount of 56// time between frames at |frame_rate| and return the fractional difference. 57double FractionFromExpectedFrameRate(base::TimeDelta delta, int frame_rate) { 58 DCHECK_GT(frame_rate, 0); 59 const base::TimeDelta expected_delta = 60 base::TimeDelta::FromSeconds(1) / frame_rate; 61 return (delta - expected_delta).InMillisecondsF() / 62 expected_delta.InMillisecondsF(); 63} 64 65} // anonymous namespace 66 67VideoCaptureOracle::VideoCaptureOracle(base::TimeDelta min_capture_period, 68 bool events_are_reliable) 69 : frame_number_(0), 70 last_delivered_frame_number_(-1), 71 smoothing_sampler_(min_capture_period, 72 events_are_reliable, 73 kNumRedundantCapturesOfStaticContent), 74 content_sampler_(min_capture_period) { 75} 76 77VideoCaptureOracle::~VideoCaptureOracle() {} 78 79bool VideoCaptureOracle::ObserveEventAndDecideCapture( 80 Event event, 81 const gfx::Rect& damage_rect, 82 base::TimeTicks event_time) { 83 DCHECK_GE(event, 0); 84 DCHECK_LT(event, kNumEvents); 85 if (event_time < last_event_time_[event]) { 86 LOG(WARNING) << "Event time is not monotonically non-decreasing. " 87 << "Deciding not to capture this frame."; 88 return false; 89 } 90 last_event_time_[event] = event_time; 91 92 bool should_sample; 93 switch (event) { 94 case kCompositorUpdate: 95 case kSoftwarePaint: 96 smoothing_sampler_.ConsiderPresentationEvent(event_time); 97 content_sampler_.ConsiderPresentationEvent(damage_rect, event_time); 98 if (content_sampler_.HasProposal()) { 99 should_sample = content_sampler_.ShouldSample(); 100 if (should_sample) 101 event_time = content_sampler_.frame_timestamp(); 102 } else { 103 should_sample = smoothing_sampler_.ShouldSample(); 104 } 105 break; 106 default: 107 should_sample = smoothing_sampler_.IsOverdueForSamplingAt(event_time); 108 break; 109 } 110 111 SetFrameTimestamp(frame_number_, event_time); 112 return should_sample; 113} 114 115int VideoCaptureOracle::RecordCapture() { 116 smoothing_sampler_.RecordSample(); 117 content_sampler_.RecordSample(GetFrameTimestamp(frame_number_)); 118 return frame_number_++; 119} 120 121bool VideoCaptureOracle::CompleteCapture(int frame_number, 122 base::TimeTicks* frame_timestamp) { 123 // Drop frame if previous frame number is higher. 124 if (last_delivered_frame_number_ > frame_number) { 125 LOG(WARNING) << "Out of order frame delivery detected. Dropping frame."; 126 return false; 127 } 128 last_delivered_frame_number_ = frame_number; 129 130 *frame_timestamp = GetFrameTimestamp(frame_number); 131 132 // If enabled, log a measurement of how this frame timestamp has incremented 133 // in relation to an ideal increment. 134 if (VLOG_IS_ON(2) && frame_number > 0) { 135 const base::TimeDelta delta = 136 *frame_timestamp - GetFrameTimestamp(frame_number - 1); 137 if (content_sampler_.HasProposal()) { 138 const double estimated_frame_rate = 139 1000000.0 / content_sampler_.detected_period().InMicroseconds(); 140 const int rounded_frame_rate = 141 static_cast<int>(estimated_frame_rate + 0.5); 142 VLOG(2) << base::StringPrintf( 143 "Captured #%d: delta=%" PRId64 " usec" 144 ", now locked into {%s}, %+0.1f%% slower than %d FPS", 145 frame_number, 146 delta.InMicroseconds(), 147 content_sampler_.detected_region().ToString().c_str(), 148 100.0 * FractionFromExpectedFrameRate(delta, rounded_frame_rate), 149 rounded_frame_rate); 150 } else { 151 VLOG(2) << base::StringPrintf( 152 "Captured #%d: delta=%" PRId64 " usec" 153 ", d/30fps=%+0.1f%%, d/25fps=%+0.1f%%, d/24fps=%+0.1f%%", 154 frame_number, 155 delta.InMicroseconds(), 156 100.0 * FractionFromExpectedFrameRate(delta, 30), 157 100.0 * FractionFromExpectedFrameRate(delta, 25), 158 100.0 * FractionFromExpectedFrameRate(delta, 24)); 159 } 160 } 161 162 return !frame_timestamp->is_null(); 163} 164 165base::TimeTicks VideoCaptureOracle::GetFrameTimestamp(int frame_number) const { 166 DCHECK_LE(frame_number, frame_number_); 167 DCHECK_LT(frame_number_ - frame_number, kMaxFrameTimestamps); 168 return frame_timestamps_[frame_number % kMaxFrameTimestamps]; 169} 170 171void VideoCaptureOracle::SetFrameTimestamp(int frame_number, 172 base::TimeTicks timestamp) { 173 frame_timestamps_[frame_number % kMaxFrameTimestamps] = timestamp; 174} 175 176SmoothEventSampler::SmoothEventSampler(base::TimeDelta min_capture_period, 177 bool events_are_reliable, 178 int redundant_capture_goal) 179 : events_are_reliable_(events_are_reliable), 180 min_capture_period_(min_capture_period), 181 redundant_capture_goal_(redundant_capture_goal), 182 token_bucket_capacity_(min_capture_period + min_capture_period / 2), 183 overdue_sample_count_(0), 184 token_bucket_(token_bucket_capacity_) { 185 DCHECK_GT(min_capture_period_.InMicroseconds(), 0); 186} 187 188void SmoothEventSampler::ConsiderPresentationEvent(base::TimeTicks event_time) { 189 DCHECK(!event_time.is_null()); 190 191 // Add tokens to the bucket based on advancement in time. Then, re-bound the 192 // number of tokens in the bucket. Overflow occurs when there is too much 193 // time between events (a common case), or when RecordSample() is not being 194 // called often enough (a bug). On the other hand, if RecordSample() is being 195 // called too often (e.g., as a reaction to IsOverdueForSamplingAt()), the 196 // bucket will underflow. 197 if (!current_event_.is_null()) { 198 if (current_event_ < event_time) { 199 token_bucket_ += event_time - current_event_; 200 if (token_bucket_ > token_bucket_capacity_) 201 token_bucket_ = token_bucket_capacity_; 202 } 203 TRACE_COUNTER1("mirroring", 204 "MirroringTokenBucketUsec", 205 std::max<int64>(0, token_bucket_.InMicroseconds())); 206 } 207 current_event_ = event_time; 208} 209 210bool SmoothEventSampler::ShouldSample() const { 211 return token_bucket_ >= min_capture_period_; 212} 213 214void SmoothEventSampler::RecordSample() { 215 token_bucket_ -= min_capture_period_; 216 if (token_bucket_ < base::TimeDelta()) 217 token_bucket_ = base::TimeDelta(); 218 TRACE_COUNTER1("mirroring", 219 "MirroringTokenBucketUsec", 220 std::max<int64>(0, token_bucket_.InMicroseconds())); 221 222 if (HasUnrecordedEvent()) { 223 last_sample_ = current_event_; 224 overdue_sample_count_ = 0; 225 } else { 226 ++overdue_sample_count_; 227 } 228} 229 230bool SmoothEventSampler::IsOverdueForSamplingAt(base::TimeTicks event_time) 231 const { 232 DCHECK(!event_time.is_null()); 233 234 // If we don't get events on compositor updates on this platform, then we 235 // don't reliably know whether we're dirty. 236 if (events_are_reliable_) { 237 if (!HasUnrecordedEvent() && 238 overdue_sample_count_ >= redundant_capture_goal_) { 239 return false; // Not dirty. 240 } 241 } 242 243 if (last_sample_.is_null()) 244 return true; 245 246 // If we're dirty but not yet old, then we've recently gotten updates, so we 247 // won't request a sample just yet. 248 base::TimeDelta dirty_interval = event_time - last_sample_; 249 return dirty_interval >= 250 base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis); 251} 252 253bool SmoothEventSampler::HasUnrecordedEvent() const { 254 return !current_event_.is_null() && current_event_ != last_sample_; 255} 256 257AnimatedContentSampler::AnimatedContentSampler( 258 base::TimeDelta min_capture_period) 259 : min_capture_period_(min_capture_period) {} 260 261AnimatedContentSampler::~AnimatedContentSampler() {} 262 263void AnimatedContentSampler::ConsiderPresentationEvent( 264 const gfx::Rect& damage_rect, base::TimeTicks event_time) { 265 AddObservation(damage_rect, event_time); 266 267 if (AnalyzeObservations(event_time, &detected_region_, &detected_period_) && 268 detected_period_ > base::TimeDelta() && 269 detected_period_ <= 270 base::TimeDelta::FromMicroseconds(kMaxLockInPeriodMicros)) { 271 if (damage_rect == detected_region_) 272 UpdateFrameTimestamp(event_time); 273 else 274 frame_timestamp_ = base::TimeTicks(); 275 } else { 276 detected_region_ = gfx::Rect(); 277 detected_period_ = base::TimeDelta(); 278 frame_timestamp_ = base::TimeTicks(); 279 } 280} 281 282bool AnimatedContentSampler::HasProposal() const { 283 return detected_period_ > base::TimeDelta(); 284} 285 286bool AnimatedContentSampler::ShouldSample() const { 287 return !frame_timestamp_.is_null(); 288} 289 290void AnimatedContentSampler::RecordSample(base::TimeTicks frame_timestamp) { 291 recorded_frame_timestamp_ = frame_timestamp; 292 sequence_offset_ = base::TimeDelta(); 293} 294 295void AnimatedContentSampler::AddObservation(const gfx::Rect& damage_rect, 296 base::TimeTicks event_time) { 297 if (damage_rect.IsEmpty()) 298 return; // Useless observation. 299 300 // Add the observation to the FIFO queue. 301 if (!observations_.empty() && observations_.back().event_time > event_time) 302 return; // The implementation assumes chronological order. 303 observations_.push_back(Observation(damage_rect, event_time)); 304 305 // Prune-out old observations. 306 const base::TimeDelta threshold = 307 base::TimeDelta::FromMilliseconds(kMaxObservationWindowMillis); 308 while ((event_time - observations_.front().event_time) > threshold) 309 observations_.pop_front(); 310} 311 312gfx::Rect AnimatedContentSampler::ElectMajorityDamageRect() const { 313 // This is an derivative of the Boyer-Moore Majority Vote Algorithm where each 314 // pixel in a candidate gets one vote, as opposed to each candidate getting 315 // one vote. 316 const gfx::Rect* candidate = NULL; 317 int64 votes = 0; 318 for (ObservationFifo::const_iterator i = observations_.begin(); 319 i != observations_.end(); ++i) { 320 DCHECK_GT(i->damage_rect.size().GetArea(), 0); 321 if (votes == 0) { 322 candidate = &(i->damage_rect); 323 votes = candidate->size().GetArea(); 324 } else if (i->damage_rect == *candidate) { 325 votes += i->damage_rect.size().GetArea(); 326 } else { 327 votes -= i->damage_rect.size().GetArea(); 328 if (votes < 0) { 329 candidate = &(i->damage_rect); 330 votes = -votes; 331 } 332 } 333 } 334 return (votes > 0) ? *candidate : gfx::Rect(); 335} 336 337bool AnimatedContentSampler::AnalyzeObservations( 338 base::TimeTicks event_time, 339 gfx::Rect* rect, 340 base::TimeDelta* period) const { 341 const gfx::Rect elected_rect = ElectMajorityDamageRect(); 342 if (elected_rect.IsEmpty()) 343 return false; // There is no regular animation present. 344 345 // Scan |observations_|, gathering metrics about the ones having a damage Rect 346 // equivalent to the |elected_rect|. Along the way, break early whenever the 347 // event times reveal a non-animating period. 348 int64 num_pixels_damaged_in_all = 0; 349 int64 num_pixels_damaged_in_chosen = 0; 350 base::TimeDelta sum_frame_durations; 351 size_t count_frame_durations = 0; 352 base::TimeTicks first_event_time; 353 base::TimeTicks last_event_time; 354 for (ObservationFifo::const_reverse_iterator i = observations_.rbegin(); 355 i != observations_.rend(); ++i) { 356 const int area = i->damage_rect.size().GetArea(); 357 num_pixels_damaged_in_all += area; 358 if (i->damage_rect != elected_rect) 359 continue; 360 num_pixels_damaged_in_chosen += area; 361 if (last_event_time.is_null()) { 362 last_event_time = i->event_time; 363 if ((event_time - last_event_time) >= 364 base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis)) { 365 return false; // Content animation has recently ended. 366 } 367 } else { 368 const base::TimeDelta frame_duration = first_event_time - i->event_time; 369 if (frame_duration >= 370 base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis)) { 371 break; // Content not animating before this point. 372 } 373 sum_frame_durations += frame_duration; 374 ++count_frame_durations; 375 } 376 first_event_time = i->event_time; 377 } 378 379 if ((last_event_time - first_event_time) < 380 base::TimeDelta::FromMilliseconds(kMinObservationWindowMillis)) { 381 return false; // Content has not animated for long enough for accuracy. 382 } 383 if (num_pixels_damaged_in_chosen <= (num_pixels_damaged_in_all * 2 / 3)) 384 return false; // Animation is not damaging a supermajority of pixels. 385 386 *rect = elected_rect; 387 DCHECK_GT(count_frame_durations, 0u); 388 *period = sum_frame_durations / count_frame_durations; 389 return true; 390} 391 392void AnimatedContentSampler::UpdateFrameTimestamp(base::TimeTicks event_time) { 393 // This is how much time to advance from the last frame timestamp. Never 394 // advance by less than |min_capture_period_| because the downstream consumer 395 // cannot handle the higher frame rate. If |detected_period_| is less than 396 // |min_capture_period_|, excess frames should be dropped. 397 const base::TimeDelta advancement = 398 std::max(detected_period_, min_capture_period_); 399 400 // Compute the |timebase| upon which to determine the |frame_timestamp_|. 401 // Ideally, this would always equal the timestamp of the last recorded frame 402 // sampling. Determine how much drift from the ideal is present, then adjust 403 // the timebase by a small amount to spread out the entire correction over 404 // many frame timestamps. 405 // 406 // This accounts for two main sources of drift: 1) The clock drift of the 407 // system clock relative to the video hardware, which affects the event times; 408 // and 2) The small error introduced by this frame timestamp rewriting, as it 409 // is based on averaging over recent events. 410 base::TimeTicks timebase = event_time - sequence_offset_ - advancement; 411 if (!recorded_frame_timestamp_.is_null()) { 412 const base::TimeDelta drift = recorded_frame_timestamp_ - timebase; 413 const int64 correct_over_num_frames = 414 base::TimeDelta::FromMilliseconds(kDriftCorrectionMillis) / 415 detected_period_; 416 DCHECK_GT(correct_over_num_frames, 0); 417 timebase = recorded_frame_timestamp_ - (drift / correct_over_num_frames); 418 } 419 420 // Compute |frame_timestamp_|. Whenever |detected_period_| is less than 421 // |min_capture_period_|, some extra time is "borrowed" to be able to advance 422 // by the full |min_capture_period_|. Then, whenever the total amount of 423 // borrowed time reaches a full |min_capture_period_|, drop a frame. Note 424 // that when |detected_period_| is greater or equal to |min_capture_period_|, 425 // this logic is effectively disabled. 426 borrowed_time_ += advancement - detected_period_; 427 if (borrowed_time_ >= min_capture_period_) { 428 borrowed_time_ -= min_capture_period_; 429 frame_timestamp_ = base::TimeTicks(); 430 } else { 431 sequence_offset_ += advancement; 432 frame_timestamp_ = timebase + sequence_offset_; 433 } 434} 435 436} // namespace content 437