Introduce cadence based VideoRendererAlgorithm.

media/filters/video_cadence_estimator.cc

Index: media/filters/video_cadence_estimator.cc
diff --git a/media/filters/video_cadence_estimator.cc b/media/filters/video_cadence_estimator.cc
new file mode 100644
index 0000000000000000000000000000000000000000..85044d9b732bcf51885943a07393937d502393ca
--- /dev/null
+++ b/media/filters/video_cadence_estimator.cc
@@ -0,0 +1,161 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "media/filters/video_cadence_estimator.h"
+
+#include <algorithm>
+#include <limits>
+
+namespace media {
+
+VideoCadenceEstimator::VideoCadenceEstimator(
+    base::TimeDelta minimum_time_until_glitch)
+    : cadence_hysteresis_enabled_(true),
+      minimum_time_until_glitch_(minimum_time_until_glitch) {
+  Reset();
+}
+
+VideoCadenceEstimator::~VideoCadenceEstimator() {
+}
+
+void VideoCadenceEstimator::Reset() {
+  cadence_ = fractional_cadence_ = 0;
+  previous_cadence_ = previous_fractional_cadence_ = 0;
+  render_intervals_cadence_held_ = 0;
+}
+
+bool VideoCadenceEstimator::UpdateCadenceEstimate(
+    base::TimeDelta render_interval,
+    base::TimeDelta frame_duration,
+    base::TimeDelta max_acceptable_drift) {
+  DCHECK_GT(render_interval, base::TimeDelta());
+  DCHECK_GT(frame_duration, base::TimeDelta());
+
+  base::TimeDelta time_until_cadence_glitch;
+  base::TimeDelta time_until_fractional_cadence_glitch;

[xhwang, 2015/04/28 16:01:08]

It seems these two are only for logging? Can we just have one variable, e.g.
time_until_cadence_glitch?

[DaleCurtis, 2015/04/28 21:45:24]

No, because we need both values for the log message if both calculations fail.

[xhwang, 2015/04/28 22:17:39]

Acknowledged.

+
+  // See if the clamped cadence fits acceptable thresholds for exhausting drift.
+  int new_cadence = 0, new_fractional_cadence = 0;
+  if (CalculateCadence(render_interval, frame_duration, max_acceptable_drift,
+                       false, &new_cadence, &time_until_cadence_glitch)) {

[xhwang, 2015/04/28 16:01:08]

DCHECK(new_cadence)?

[DaleCurtis, 2015/04/28 21:45:24]

Done.

+  } else if (CalculateCadence(render_interval, frame_duration,
+                              max_acceptable_drift, true,
+                              &new_fractional_cadence,
+                              &time_until_fractional_cadence_glitch)) {
+    new_cadence = 1;
+  }
+
+  // Nothing changed, so do nothing.
+  if (new_cadence == cadence_ &&
+      new_fractional_cadence == fractional_cadence_) {
+    render_intervals_cadence_held_ = 0;

[xhwang, 2015/04/28 16:01:08]

The comment says 

132   // ...  |render_intervals_cadence_held_| is
133   // incremented for each UpdateCadenceEstimate() where the cadence remains
the
134   // same.

But here we are reset it to zero...

[DaleCurtis, 2015/04/28 21:45:24]

This prevents the previous cadence values from accumulating incorrectly. I've
clarified the comments.

+    return false;
+  }
+
+  if (!cadence_hysteresis_enabled_) {
+    cadence_ = new_cadence;
+    fractional_cadence_ = new_fractional_cadence;
+    return true;
+  }
+
+  // Wait until enough render intervals have elapsed before accepting the
+  // cadence change.  Prevents oscillation of the cadence selection.
+  if (new_cadence == previous_cadence_ &&

[xhwang, 2015/04/28 16:01:08]

|previous_cadence| is really a |pending_cadence_| or a |pending_new_cadence_|.
It hasn't  been used yet, so |previous| is a bit misleading.

[DaleCurtis, 2015/04/28 21:45:24]

Done.

+      new_fractional_cadence == previous_fractional_cadence_) {
+    if (++render_intervals_cadence_held_ * render_interval >=

[xhwang, 2015/04/28 16:01:08]

note: render_interval can be different every time so this is an approximate. But
I guess it's good enough in real life.

[DaleCurtis, 2015/04/28 21:45:24]

Yup.

+        base::TimeDelta::FromMilliseconds(kMinimumCadenceDurationMs)) {
+      DVLOG(1) << "Cadence switch: (" << cadence_ << ", " << fractional_cadence_
+               << ") -> (" << new_cadence << ", " << new_fractional_cadence
+               << ") :: (" << time_until_cadence_glitch << ", "
+               << time_until_fractional_cadence_glitch << ")";
+
+      cadence_ = new_cadence;
+      fractional_cadence_ = new_fractional_cadence;
+      return true;
+    } else {
+      DVLOG(2) << "Hysteresis prevented cadence switch: (" << cadence_ << ", "
+               << fractional_cadence_ << ") -> (" << new_cadence << ", "
+               << new_fractional_cadence << ") :: ("
+               << time_until_cadence_glitch << ", "
+               << time_until_fractional_cadence_glitch << ")";

[xhwang, 2015/04/28 16:01:08]

nit: just return false here, so that you don't need "else" on l.83?

[DaleCurtis, 2015/04/28 21:45:24]

Done.

+    }
+  } else {
+    previous_cadence_ = new_cadence;
+    previous_fractional_cadence_ = new_fractional_cadence;
+    render_intervals_cadence_held_ = 1;

[xhwang, 2015/04/28 16:01:08]

If in the extreme case where cadence estimation oscillates randomly (e.g. for
the 2:3 case when the ideal cadence is 2.5, and the estimate could be either 2
or 3), we could have |previous_cadence_| changing pretty often so that it can
take very long to reach kMinimumCadenceDurationMs because we are resetting
|render_intervals_cadence_held_| here. Is that expected?

[DaleCurtis, 2015/04/28 21:45:24]

2.5 is pretty unlikely to clamp to 2 or 3, it exhausts the allowable drift in a
single frame. It should almost always clamp to zero. Even if it does clamp once
or twice, I doubt it would clamp for 100ms.  Though we'll want some UMA
statistics added to this later on for seeing common frame durations.

[xhwang, 2015/04/28 22:17:39]

Acknowledged.

+  }
+
+  return false;
+}
+
+bool VideoCadenceEstimator::CalculateCadence(
+    base::TimeDelta render_interval,
+    base::TimeDelta frame_duration,
+    base::TimeDelta max_acceptable_drift,
+    bool fractional,
+    int* cadence,
+    base::TimeDelta* time_until_glitch) {
+  *cadence = 0;
+  *time_until_glitch = base::TimeDelta();

[xhwang, 2015/04/28 16:01:08]

DCHECK instead of set?

[DaleCurtis, 2015/04/28 21:45:24]

No, I want to clear them every time.

[xhwang, 2015/04/28 22:17:39]

hmm, wondering why? The caller already initializes them. This could hide errors
in the caller side.

[DaleCurtis, 2015/04/29 00:11:12]

Actually, they don't need to be initialized here anymore; that was older code
that I ditched. Removed.

+
+  // The perfect cadence is the number of render intervals per frame, while the
+  // clamped cadence is the nearest matching integer cadence.
+  //
+  // Fractional cadence is checked to see if we have a cadence which would look
+  // best if we consistently drop the same frames.
+  //
+  // As mentioned in the introduction, |perfect_cadence| is the ratio of the
+  // frame duration to render interval length; while |clamped_cadence| is the
+  // nearest integer value to |perfect_cadence|.  When computing a fractional
+  // cadence (1/|perfect_cadence|), |fractional| must be set to true to ensure
+  // the rendered and actual frame durations are computed correctly.
+  const double perfect_cadence =
+      fractional ? render_interval.InSecondsF() / frame_duration.InSecondsF()
+                 : frame_duration.InSecondsF() / render_interval.InSecondsF();
+  const int clamped_cadence = perfect_cadence + 0.5;
+  if (!clamped_cadence)
+    return false;
+
+  // Calculate the drift in microseconds for each frame we render at cadence
+  // instead of for its real duration.
+  const base::TimeDelta rendered_frame_duration =
+      fractional ? render_interval : clamped_cadence * render_interval;
+
+  // When computing a fractional drift, we render the first of |clamped_cadence|
+  // frames and drop |clamped_cadence| - 1 frames.  To make the calculations
+  // below work we need to project out the timestamp of the frame which would be
+  // rendered after accounting for those |clamped_cadence| frames.

[xhwang, 2015/04/28 16:01:08]

We are checking "fractional ?" in 3 places in this function. Maybe we should
just split this function into CalculateCalmpedCadence() and
CalculateFractionalCadence()... Then we can just do the estimation in a
straightforward way using simple math...

[DaleCurtis, 2015/04/28 21:45:24]

The math is already tricky, I'd rather not duplicate it in two places. Splitting
the functions just adds to the complexity because I'll need a third helper
function for the last bit of calculations. It also doesn't simplify the math in
any way as far as I can tell, can you elaborate on why you think it would
simplify the math?

I feel it's more readable done within a single function too as it's easier to
figure out what's going on when you see how fractional calculations only change
the inputs slightly.

[xhwang, 2015/04/28 22:17:39]

For me I have to read this function twice, one with fractional being true, one
being false to understand how things work. Since I already read through this,
it's not a problem now. But I do feel readability could improve by splitting it
to two functions, where you don't need to introduce new concepts like
rendered_frame_duration and actual_frame_duration. You may end up doing the
division twice but that'll be only a few lines.

Maybe it's only me though :) If other reviewers (+miu) feel it's okay, I have no
problem with the current code.

[DaleCurtis, 2015/04/29 00:11:11]

l.136, l.148 would end up in a third function with a bunch of variables passed
in to avoid duplicating that code; two of those variables would be
"actual_frame_duration and "rendered_frame_duration", so they wouldn't go away
:)

+  const base::TimeDelta actual_frame_duration =
+      fractional ? clamped_cadence * frame_duration : frame_duration;
+  if (rendered_frame_duration == actual_frame_duration) {
+    *cadence = clamped_cadence;
+    return true;
+  }
+
+  // Compute how long it'll take to exhaust the drift using |clamped_cadence|.
+  const double duration_delta = std::abs(
+      (rendered_frame_duration - actual_frame_duration).InMicroseconds());
+  const int64 frames_until_drift_exhausted =
+      std::ceil(max_acceptable_drift.InMicroseconds() / duration_delta);
+  *time_until_glitch = rendered_frame_duration * frames_until_drift_exhausted;
+
+  if (*time_until_glitch >= minimum_time_until_glitch_) {
+    *cadence = clamped_cadence;
+    return true;
+  }
+
+  return false;
+}
+
+int VideoCadenceEstimator::GetCadenceForFrame(int index) const {
+  DCHECK(has_cadence());
+  DCHECK_GE(index, 0);
+
+  if (fractional_cadence_)
+    return index % fractional_cadence_ == 0 ? 1 : 0;
+
+  return cadence_;
+}
+
+}  // namespace media