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