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 
5 #include "media/filters/video_cadence_estimator.h"
6 
7 #include <math.h>
8 #include <stddef.h>
9 
10 #include <memory>
11 
12 #include "base/strings/string_number_conversions.h"
13 #include "base/strings/string_split.h"
14 #include "base/strings/stringprintf.h"
15 #include "base/test/scoped_feature_list.h"
16 #include "media/base/media_switches.h"
17 #include "testing/gtest/include/gtest/gtest.h"
18 
19 namespace media {
20 
21 // See VideoCadenceEstimator header for more details.
22 const int kMinimumAcceptableTimeBetweenGlitchesSecs = 8;
23 
24 // Slows down the given |fps| according to NTSC field reduction standards; see
25 // http://en.wikipedia.org/wiki/Frame_rate#Digital_video_and_television
NTSC(double fps)26 static double NTSC(double fps) {
27   return fps / 1.001;
28 }
29 
Interval(double hertz)30 static base::TimeDelta Interval(double hertz) {
31   return base::TimeDelta::FromSecondsD(1.0 / hertz);
32 }
33 
CreateCadenceFromString(const std::string & cadence)34 std::vector<int> CreateCadenceFromString(const std::string& cadence) {
35   CHECK_EQ('[', cadence.front());
36   CHECK_EQ(']', cadence.back());
37 
38   std::vector<int> result;
39   for (const std::string& token :
40        base::SplitString(cadence.substr(1, cadence.length() - 2),
41                          ":", base::TRIM_WHITESPACE, base::SPLIT_WANT_ALL)) {
42     int cadence_value = 0;
43     CHECK(base::StringToInt(token, &cadence_value)) << token;
44     result.push_back(cadence_value);
45   }
46 
47   return result;
48 }
49 
VerifyCadenceVectorWithCustomDeviationAndDrift(VideoCadenceEstimator * estimator,double frame_hertz,double render_hertz,base::TimeDelta deviation,base::TimeDelta acceptable_drift,const std::string & expected_cadence)50 static void VerifyCadenceVectorWithCustomDeviationAndDrift(
51     VideoCadenceEstimator* estimator,
52     double frame_hertz,
53     double render_hertz,
54     base::TimeDelta deviation,
55     base::TimeDelta acceptable_drift,
56     const std::string& expected_cadence) {
57   SCOPED_TRACE(base::StringPrintf("Checking %.03f fps into %0.03f", frame_hertz,
58                                   render_hertz));
59 
60   const std::vector<int> expected_cadence_vector =
61       CreateCadenceFromString(expected_cadence);
62 
63   estimator->Reset();
64   const bool cadence_changed = estimator->UpdateCadenceEstimate(
65       Interval(render_hertz), Interval(frame_hertz), deviation,
66       acceptable_drift);
67   EXPECT_EQ(cadence_changed, estimator->has_cadence());
68   EXPECT_EQ(expected_cadence_vector.empty(), !estimator->has_cadence());
69 
70   // Nothing further to test.
71   if (expected_cadence_vector.empty() || !estimator->has_cadence())
72     return;
73 
74   EXPECT_EQ(expected_cadence_vector.size(),
75             estimator->cadence_size_for_testing());
76 
77   // Spot two cycles of the cadence.
78   for (size_t i = 0; i < expected_cadence_vector.size() * 2; ++i) {
79     ASSERT_EQ(expected_cadence_vector[i % expected_cadence_vector.size()],
80               estimator->GetCadenceForFrame(i));
81   }
82 }
83 
VerifyCadenceVectorWithCustomDrift(VideoCadenceEstimator * estimator,double frame_hertz,double render_hertz,base::TimeDelta acceptable_drift,const std::string & expected_cadence)84 static void VerifyCadenceVectorWithCustomDrift(
85     VideoCadenceEstimator* estimator,
86     double frame_hertz,
87     double render_hertz,
88     base::TimeDelta acceptable_drift,
89     const std::string& expected_cadence) {
90   VerifyCadenceVectorWithCustomDeviationAndDrift(
91       estimator, frame_hertz, render_hertz, base::TimeDelta(), acceptable_drift,
92       expected_cadence);
93 }
94 
VerifyCadenceVectorWithCustomDeviation(VideoCadenceEstimator * estimator,double frame_hertz,double render_hertz,base::TimeDelta deviation,const std::string & expected_cadence)95 static void VerifyCadenceVectorWithCustomDeviation(
96     VideoCadenceEstimator* estimator,
97     double frame_hertz,
98     double render_hertz,
99     base::TimeDelta deviation,
100     const std::string& expected_cadence) {
101   const base::TimeDelta acceptable_drift =
102       std::max(Interval(frame_hertz) / 2, Interval(render_hertz));
103   VerifyCadenceVectorWithCustomDeviationAndDrift(
104       estimator, frame_hertz, render_hertz, deviation, acceptable_drift,
105       expected_cadence);
106 }
107 
VerifyCadenceVector(VideoCadenceEstimator * estimator,double frame_hertz,double render_hertz,const std::string & expected_cadence)108 static void VerifyCadenceVector(VideoCadenceEstimator* estimator,
109                                 double frame_hertz,
110                                 double render_hertz,
111                                 const std::string& expected_cadence) {
112   const base::TimeDelta acceptable_drift =
113       std::max(Interval(frame_hertz) / 2, Interval(render_hertz));
114   VerifyCadenceVectorWithCustomDeviationAndDrift(
115       estimator, frame_hertz, render_hertz, base::TimeDelta(), acceptable_drift,
116       expected_cadence);
117 }
118 
119 // Spot check common display and frame rate pairs for correctness.
TEST(VideoCadenceEstimatorTest,CadenceCalculations)120 TEST(VideoCadenceEstimatorTest, CadenceCalculations) {
121   VideoCadenceEstimator estimator(
122       base::TimeDelta::FromSeconds(kMinimumAcceptableTimeBetweenGlitchesSecs));
123   estimator.set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
124 
125   const std::string kEmptyCadence = "[]";
126   VerifyCadenceVector(&estimator, 1, NTSC(60), "[60]");
127 
128   VerifyCadenceVector(&estimator, 24, 60, "[3:2]");
129   VerifyCadenceVector(&estimator, NTSC(24), 60, "[3:2]");
130   VerifyCadenceVector(&estimator, 24, NTSC(60), "[3:2]");
131 
132   VerifyCadenceVector(&estimator, 25, 60, "[2:3:2:3:2]");
133   VerifyCadenceVector(&estimator, NTSC(25), 60, "[2:3:2:3:2]");
134   VerifyCadenceVector(&estimator, 25, NTSC(60), "[2:3:2:3:2]");
135 
136   VerifyCadenceVector(&estimator, 30, 60, "[2]");
137   VerifyCadenceVector(&estimator, NTSC(30), 60, "[2]");
138   VerifyCadenceVector(&estimator, 29.5, 60, kEmptyCadence);
139 
140   VerifyCadenceVector(&estimator, 50, 60, "[1:1:2:1:1]");
141   VerifyCadenceVector(&estimator, NTSC(50), 60, "[1:1:2:1:1]");
142   VerifyCadenceVector(&estimator, 50, NTSC(60), "[1:1:2:1:1]");
143 
144   VerifyCadenceVector(&estimator, NTSC(60), 60, "[1]");
145   VerifyCadenceVector(&estimator, 60, NTSC(60), "[1]");
146 
147   VerifyCadenceVector(&estimator, 120, 60, "[1:0]");
148   VerifyCadenceVector(&estimator, NTSC(120), 60, "[1:0]");
149   VerifyCadenceVector(&estimator, 120, NTSC(60), "[1:0]");
150 
151   // Test cases for cadence below 1.
152   VerifyCadenceVector(&estimator, 120, 24, "[1:0:0:0:0]");
153   VerifyCadenceVector(&estimator, 120, 48, "[1:0:0:1:0]");
154   VerifyCadenceVector(&estimator, 120, 72, "[1:0:1:0:1]");
155   VerifyCadenceVector(&estimator, 90, 60, "[1:0:1]");
156 
157   // 50Hz is common in the EU.
158   VerifyCadenceVector(&estimator, NTSC(24), 50, kEmptyCadence);
159   VerifyCadenceVector(&estimator, 24, 50, kEmptyCadence);
160 
161   VerifyCadenceVector(&estimator, NTSC(25), 50, "[2]");
162   VerifyCadenceVector(&estimator, 25, 50, "[2]");
163 
164   VerifyCadenceVector(&estimator, NTSC(30), 50, "[2:1:2]");
165   VerifyCadenceVector(&estimator, 30, 50, "[2:1:2]");
166 
167   VerifyCadenceVector(&estimator, NTSC(60), 50, kEmptyCadence);
168   VerifyCadenceVector(&estimator, 60, 50, kEmptyCadence);
169 
170 }
171 
172 // Check the extreme case that max_acceptable_drift is larger than
173 // minimum_time_until_max_drift.
TEST(VideoCadenceEstimatorTest,CadenceCalculationWithLargeDrift)174 TEST(VideoCadenceEstimatorTest, CadenceCalculationWithLargeDrift) {
175   VideoCadenceEstimator estimator(
176       base::TimeDelta::FromSeconds(kMinimumAcceptableTimeBetweenGlitchesSecs));
177   estimator.set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
178 
179   base::TimeDelta drift = base::TimeDelta::FromHours(1);
180   VerifyCadenceVectorWithCustomDrift(&estimator, 1, NTSC(60), drift, "[60]");
181 
182   VerifyCadenceVectorWithCustomDrift(&estimator, 30, 60, drift, "[2]");
183   VerifyCadenceVectorWithCustomDrift(&estimator, NTSC(30), 60, drift, "[2]");
184   VerifyCadenceVectorWithCustomDrift(&estimator, 30, NTSC(60), drift, "[2]");
185 
186   VerifyCadenceVectorWithCustomDrift(&estimator, 25, 60, drift, "[2]");
187   VerifyCadenceVectorWithCustomDrift(&estimator, NTSC(25), 60, drift, "[2]");
188   VerifyCadenceVectorWithCustomDrift(&estimator, 25, NTSC(60), drift, "[2]");
189 
190   // Test cases for cadence below 1.
191   VerifyCadenceVectorWithCustomDrift(&estimator, 120, 24, drift, "[1]");
192   VerifyCadenceVectorWithCustomDrift(&estimator, 120, 48, drift, "[1]");
193   VerifyCadenceVectorWithCustomDrift(&estimator, 120, 72, drift, "[1]");
194   VerifyCadenceVectorWithCustomDrift(&estimator, 90, 60, drift, "[1]");
195 }
196 
197 // Check the case that the estimator excludes variable FPS case from Cadence.
TEST(VideoCadenceEstimatorTest,CadenceCalculationWithLargeDeviation)198 TEST(VideoCadenceEstimatorTest, CadenceCalculationWithLargeDeviation) {
199   VideoCadenceEstimator estimator(
200       base::TimeDelta::FromSeconds(kMinimumAcceptableTimeBetweenGlitchesSecs));
201   estimator.set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
202 
203   const base::TimeDelta deviation = base::TimeDelta::FromMilliseconds(30);
204   VerifyCadenceVectorWithCustomDeviation(&estimator, 1, 60, deviation, "[]");
205   VerifyCadenceVectorWithCustomDeviation(&estimator, 30, 60, deviation, "[]");
206   VerifyCadenceVectorWithCustomDeviation(&estimator, 25, 60, deviation, "[]");
207 
208   // Test cases for cadence with low refresh rate.
209   VerifyCadenceVectorWithCustomDeviation(&estimator, 60, 12, deviation,
210                                          "[1:0:0:0:0]");
211 }
212 
TEST(VideoCadenceEstimatorTest,CadenceVariesWithAcceptableDrift)213 TEST(VideoCadenceEstimatorTest, CadenceVariesWithAcceptableDrift) {
214   VideoCadenceEstimator estimator(
215       base::TimeDelta::FromSeconds(kMinimumAcceptableTimeBetweenGlitchesSecs));
216   estimator.set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
217 
218   const base::TimeDelta render_interval = Interval(NTSC(60));
219   const base::TimeDelta frame_interval = Interval(120);
220 
221   base::TimeDelta acceptable_drift = frame_interval / 2;
222   EXPECT_FALSE(estimator.UpdateCadenceEstimate(
223       render_interval, frame_interval, base::TimeDelta(), acceptable_drift));
224   EXPECT_FALSE(estimator.has_cadence());
225 
226   // Increasing the acceptable drift should be result in more permissive
227   // detection of cadence.
228   acceptable_drift = render_interval;
229   EXPECT_TRUE(estimator.UpdateCadenceEstimate(
230       render_interval, frame_interval, base::TimeDelta(), acceptable_drift));
231   EXPECT_TRUE(estimator.has_cadence());
232   EXPECT_EQ("[1:0]", estimator.GetCadenceForTesting());
233 }
234 
TEST(VideoCadenceEstimatorTest,CadenceVariesWithAcceptableGlitchTime)235 TEST(VideoCadenceEstimatorTest, CadenceVariesWithAcceptableGlitchTime) {
236   std::unique_ptr<VideoCadenceEstimator> estimator(new VideoCadenceEstimator(
237       base::TimeDelta::FromSeconds(kMinimumAcceptableTimeBetweenGlitchesSecs)));
238   estimator->set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
239 
240   const base::TimeDelta render_interval = Interval(NTSC(60));
241   const base::TimeDelta frame_interval = Interval(120);
242   const base::TimeDelta acceptable_drift = frame_interval / 2;
243 
244   EXPECT_FALSE(estimator->UpdateCadenceEstimate(
245       render_interval, frame_interval, base::TimeDelta(), acceptable_drift));
246   EXPECT_FALSE(estimator->has_cadence());
247 
248   // Decreasing the acceptable glitch time should be result in more permissive
249   // detection of cadence.
250   estimator.reset(new VideoCadenceEstimator(base::TimeDelta::FromSeconds(
251       kMinimumAcceptableTimeBetweenGlitchesSecs / 2)));
252   estimator->set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
253   EXPECT_TRUE(estimator->UpdateCadenceEstimate(
254       render_interval, frame_interval, base::TimeDelta(), acceptable_drift));
255   EXPECT_TRUE(estimator->has_cadence());
256   EXPECT_EQ("[1:0]", estimator->GetCadenceForTesting());
257 }
258 
TEST(VideoCadenceEstimatorTest,CadenceHystersisPreventsOscillation)259 TEST(VideoCadenceEstimatorTest, CadenceHystersisPreventsOscillation) {
260   std::unique_ptr<VideoCadenceEstimator> estimator(new VideoCadenceEstimator(
261       base::TimeDelta::FromSeconds(kMinimumAcceptableTimeBetweenGlitchesSecs)));
262 
263   const base::TimeDelta render_interval = Interval(30);
264   const base::TimeDelta frame_interval = Interval(60);
265   const base::TimeDelta acceptable_drift = frame_interval / 2;
266   estimator->set_cadence_hysteresis_threshold_for_testing(render_interval * 2);
267 
268   // Cadence hysteresis should prevent the cadence from taking effect yet.
269   EXPECT_FALSE(estimator->UpdateCadenceEstimate(
270       render_interval, frame_interval, base::TimeDelta(), acceptable_drift));
271   EXPECT_FALSE(estimator->has_cadence());
272 
273   // A second call should exceed cadence hysteresis and take into effect.
274   EXPECT_TRUE(estimator->UpdateCadenceEstimate(
275       render_interval, frame_interval, base::TimeDelta(), acceptable_drift));
276   EXPECT_TRUE(estimator->has_cadence());
277 
278   // One bad interval shouldn't cause cadence to drop
279   EXPECT_FALSE(
280       estimator->UpdateCadenceEstimate(render_interval, frame_interval * 0.75,
281                                        base::TimeDelta(), acceptable_drift));
282   EXPECT_TRUE(estimator->has_cadence());
283 
284   // Resumption of cadence should clear bad interval count.
285   EXPECT_FALSE(estimator->UpdateCadenceEstimate(
286       render_interval, frame_interval, base::TimeDelta(), acceptable_drift));
287   EXPECT_TRUE(estimator->has_cadence());
288 
289   // So one more bad interval shouldn't cause cadence to drop
290   EXPECT_FALSE(
291       estimator->UpdateCadenceEstimate(render_interval, frame_interval * 0.75,
292                                        base::TimeDelta(), acceptable_drift));
293   EXPECT_TRUE(estimator->has_cadence());
294 
295   // Two bad intervals should.
296   EXPECT_TRUE(
297       estimator->UpdateCadenceEstimate(render_interval, frame_interval * 0.75,
298                                        base::TimeDelta(), acceptable_drift));
299   EXPECT_FALSE(estimator->has_cadence());
300 }
301 
VerifyCadenceSequence(VideoCadenceEstimator * estimator,double frame_rate,double display_rate,std::vector<int> expected_cadence)302 void VerifyCadenceSequence(VideoCadenceEstimator* estimator,
303                            double frame_rate,
304                            double display_rate,
305                            std::vector<int> expected_cadence) {
306   SCOPED_TRACE(base::StringPrintf("Checking %.03f fps into %0.03f", frame_rate,
307                                   display_rate));
308 
309   const base::TimeDelta render_interval = Interval(display_rate);
310   const base::TimeDelta frame_interval = Interval(frame_rate);
311   const base::TimeDelta acceptable_drift =
312       frame_interval < render_interval ? render_interval : frame_interval;
313   const base::TimeDelta test_runtime = base::TimeDelta::FromSeconds(10 * 60);
314   const int test_frames = test_runtime / frame_interval;
315 
316   estimator->Reset();
317   EXPECT_TRUE(estimator->UpdateCadenceEstimate(
318       render_interval, frame_interval, base::TimeDelta(), acceptable_drift));
319   EXPECT_TRUE(estimator->has_cadence());
320   for (auto i = 0u; i < expected_cadence.size(); i++) {
321     ASSERT_EQ(expected_cadence[i], estimator->GetCadenceForFrame(i))
322         << " i=" << i;
323   }
324 
325   int total_display_cycles = 0;
326   for (int i = 0; i < test_frames; i++) {
327     total_display_cycles += estimator->GetCadenceForFrame(i);
328     base::TimeDelta drift =
329         (total_display_cycles * render_interval) - ((i + 1) * frame_interval);
330     EXPECT_LE(drift.magnitude(), acceptable_drift)
331         << " i=" << i << " time=" << (total_display_cycles * render_interval);
332     if (drift.magnitude() > acceptable_drift)
333       break;
334   }
335 }
336 
TEST(VideoCadenceEstimatorTest,BresenhamCadencePatterns)337 TEST(VideoCadenceEstimatorTest, BresenhamCadencePatterns) {
338   base::test::ScopedFeatureList scoped_feature_list;
339   scoped_feature_list.InitAndEnableFeature(media::kBresenhamCadence);
340   VideoCadenceEstimator estimator(base::TimeDelta::FromSeconds(1));
341   estimator.set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
342 
343   VerifyCadenceSequence(&estimator, 30, 60,
344                         {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2});
345   VerifyCadenceSequence(&estimator, NTSC(30), 60,
346                         {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2});
347   VerifyCadenceSequence(&estimator, 30, NTSC(60),
348                         {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2});
349 
350   VerifyCadenceSequence(&estimator, 25, 60, {2, 3, 2, 3, 2, 2, 3, 2});
351 
352   VerifyCadenceSequence(&estimator, 24, 60, {3, 2, 3, 2, 3, 2, 3, 2});
353   VerifyCadenceSequence(&estimator, NTSC(24), 60, {3, 2, 3, 2, 3, 2, 3, 2});
354   VerifyCadenceSequence(&estimator, 24, NTSC(60), {2, 3, 2, 3, 2, 3, 2, 3, 2});
355 
356   VerifyCadenceSequence(&estimator, 24, 50,
357                         {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2});
358   VerifyCadenceSequence(&estimator, NTSC(24), 50,
359                         {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2});
360 
361   VerifyCadenceSequence(&estimator, 30, 50, {2, 1, 2, 2, 1, 2, 2});
362   VerifyCadenceSequence(&estimator, NTSC(30), 50, {2, 2, 1, 2, 2});
363   VerifyCadenceSequence(&estimator, 120, 24, {1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1});
364   VerifyCadenceSequence(&estimator, 60, 50, {1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0});
365   VerifyCadenceSequence(&estimator, 25, 50, {2, 2, 2, 2, 2, 2, 2, 2, 2});
366 
367   VerifyCadenceSequence(&estimator, 50, 25, {1, 0, 1, 0, 1, 0, 1, 0});
368   VerifyCadenceSequence(&estimator, 120, 60, {1, 0, 1, 0, 1, 0, 1, 0});
369 
370   // Frame rate deviation is too high, refuse to provide cadence.
371   EXPECT_TRUE(estimator.UpdateCadenceEstimate(
372       Interval(60), Interval(30), base::TimeDelta::FromMilliseconds(20),
373       base::TimeDelta::FromSeconds(100)));
374   EXPECT_FALSE(estimator.has_cadence());
375 
376   // No cadence change for neglegable rate changes
377   EXPECT_TRUE(estimator.UpdateCadenceEstimate(
378       Interval(60), Interval(30), base::TimeDelta(), base::TimeDelta()));
379   EXPECT_FALSE(estimator.UpdateCadenceEstimate(Interval(60 * 1.0001),
380                                                Interval(30), base::TimeDelta(),
381                                                base::TimeDelta()));
382 }
383 
TEST(VideoCadenceEstimatorTest,BresenhamCadenceChange)384 TEST(VideoCadenceEstimatorTest, BresenhamCadenceChange) {
385   base::test::ScopedFeatureList scoped_feature_list;
386   scoped_feature_list.InitAndEnableFeature(media::kBresenhamCadence);
387   VideoCadenceEstimator estimator(base::TimeDelta::FromSeconds(1));
388   estimator.set_cadence_hysteresis_threshold_for_testing(base::TimeDelta());
389 
390   base::TimeDelta render_interval = Interval(60);
391   base::TimeDelta frame_duration = Interval(24);
392   EXPECT_TRUE(estimator.UpdateCadenceEstimate(
393       render_interval, frame_duration, base::TimeDelta(), base::TimeDelta()));
394   EXPECT_FALSE(estimator.UpdateCadenceEstimate(
395       render_interval, frame_duration, base::TimeDelta(), base::TimeDelta()));
396 
397   for (double t = 0.0; t < 10.0; t += 0.1) {
398     // +-100us drift of the rendering interval, a totally realistic thing.
399     base::TimeDelta new_render_interval =
400         render_interval + base::TimeDelta::FromMicrosecondsD(std::sin(t) * 100);
401 
402     EXPECT_FALSE(
403         estimator.UpdateCadenceEstimate(new_render_interval, frame_duration,
404                                         base::TimeDelta(), base::TimeDelta()))
405         << "render interval: " << new_render_interval
406         << " hz: " << (1e6 / new_render_interval.InMicrosecondsF());
407   }
408 
409   EXPECT_TRUE(estimator.UpdateCadenceEstimate(
410       Interval(59), frame_duration, base::TimeDelta(), base::TimeDelta()));
411 }
412 
413 }  // namespace media
414