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