1 /*
2 * Copyright 2016 The WebRTC Project Authors. All rights reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #include "rtc_base/timestamp_aligner.h"
12
13 #include <math.h>
14
15 #include <algorithm>
16 #include <limits>
17
18 #include "rtc_base/random.h"
19 #include "rtc_base/time_utils.h"
20 #include "test/gtest.h"
21
22 namespace rtc {
23
24 namespace {
25 // Computes the difference x_k - mean(x), when x_k is the linear sequence x_k =
26 // k, and the "mean" is plain mean for the first |window_size| samples, followed
27 // by exponential averaging with weight 1 / |window_size| for each new sample.
28 // This is needed to predict the effect of camera clock drift on the timestamp
29 // translation. See the comment on TimestampAligner::UpdateOffset for more
30 // context.
MeanTimeDifference(int nsamples,int window_size)31 double MeanTimeDifference(int nsamples, int window_size) {
32 if (nsamples <= window_size) {
33 // Plain averaging.
34 return nsamples / 2.0;
35 } else {
36 // Exponential convergence towards
37 // interval_error * (window_size - 1)
38 double alpha = 1.0 - 1.0 / window_size;
39
40 return ((window_size - 1) -
41 (window_size / 2.0 - 1) * pow(alpha, nsamples - window_size));
42 }
43 }
44
45 class TimestampAlignerForTest : public TimestampAligner {
46 // Make internal methods accessible to testing.
47 public:
48 using TimestampAligner::ClipTimestamp;
49 using TimestampAligner::UpdateOffset;
50 };
51
TestTimestampFilter(double rel_freq_error)52 void TestTimestampFilter(double rel_freq_error) {
53 TimestampAlignerForTest timestamp_aligner_for_test;
54 TimestampAligner timestamp_aligner;
55 const int64_t kEpoch = 10000;
56 const int64_t kJitterUs = 5000;
57 const int64_t kIntervalUs = 33333; // 30 FPS
58 const int kWindowSize = 100;
59 const int kNumFrames = 3 * kWindowSize;
60
61 int64_t interval_error_us = kIntervalUs * rel_freq_error;
62 int64_t system_start_us = rtc::TimeMicros();
63 webrtc::Random random(17);
64
65 int64_t prev_translated_time_us = system_start_us;
66
67 for (int i = 0; i < kNumFrames; i++) {
68 // Camera time subject to drift.
69 int64_t camera_time_us = kEpoch + i * (kIntervalUs + interval_error_us);
70 int64_t system_time_us = system_start_us + i * kIntervalUs;
71 // And system time readings are subject to jitter.
72 int64_t system_measured_us = system_time_us + random.Rand(kJitterUs);
73
74 int64_t offset_us = timestamp_aligner_for_test.UpdateOffset(
75 camera_time_us, system_measured_us);
76
77 int64_t filtered_time_us = camera_time_us + offset_us;
78 int64_t translated_time_us = timestamp_aligner_for_test.ClipTimestamp(
79 filtered_time_us, system_measured_us);
80
81 // Check that we get identical result from the all-in-one helper method.
82 ASSERT_EQ(translated_time_us, timestamp_aligner.TranslateTimestamp(
83 camera_time_us, system_measured_us));
84
85 EXPECT_LE(translated_time_us, system_measured_us);
86 EXPECT_GE(translated_time_us,
87 prev_translated_time_us + rtc::kNumMicrosecsPerMillisec);
88
89 // The relative frequency error contributes to the expected error
90 // by a factor which is the difference between the current time
91 // and the average of earlier sample times.
92 int64_t expected_error_us =
93 kJitterUs / 2 +
94 rel_freq_error * kIntervalUs * MeanTimeDifference(i, kWindowSize);
95
96 int64_t bias_us = filtered_time_us - translated_time_us;
97 EXPECT_GE(bias_us, 0);
98
99 if (i == 0) {
100 EXPECT_EQ(translated_time_us, system_measured_us);
101 } else {
102 EXPECT_NEAR(filtered_time_us, system_time_us + expected_error_us,
103 2.0 * kJitterUs / sqrt(std::max(i, kWindowSize)));
104 }
105 // If the camera clock runs too fast (rel_freq_error > 0.0), The
106 // bias is expected to roughly cancel the expected error from the
107 // clock drift, as this grows. Otherwise, it reflects the
108 // measurement noise. The tolerances here were selected after some
109 // trial and error.
110 if (i < 10 || rel_freq_error <= 0.0) {
111 EXPECT_LE(bias_us, 3000);
112 } else {
113 EXPECT_NEAR(bias_us, expected_error_us, 1500);
114 }
115 prev_translated_time_us = translated_time_us;
116 }
117 }
118
119 } // Anonymous namespace
120
TEST(TimestampAlignerTest,AttenuateTimestampJitterNoDrift)121 TEST(TimestampAlignerTest, AttenuateTimestampJitterNoDrift) {
122 TestTimestampFilter(0.0);
123 }
124
125 // 100 ppm is a worst case for a reasonable crystal.
TEST(TimestampAlignerTest,AttenuateTimestampJitterSmallPosDrift)126 TEST(TimestampAlignerTest, AttenuateTimestampJitterSmallPosDrift) {
127 TestTimestampFilter(0.0001);
128 }
129
TEST(TimestampAlignerTest,AttenuateTimestampJitterSmallNegDrift)130 TEST(TimestampAlignerTest, AttenuateTimestampJitterSmallNegDrift) {
131 TestTimestampFilter(-0.0001);
132 }
133
134 // 3000 ppm, 3 ms / s, is the worst observed drift, see
135 // https://bugs.chromium.org/p/webrtc/issues/detail?id=5456
TEST(TimestampAlignerTest,AttenuateTimestampJitterLargePosDrift)136 TEST(TimestampAlignerTest, AttenuateTimestampJitterLargePosDrift) {
137 TestTimestampFilter(0.003);
138 }
139
TEST(TimestampAlignerTest,AttenuateTimestampJitterLargeNegDrift)140 TEST(TimestampAlignerTest, AttenuateTimestampJitterLargeNegDrift) {
141 TestTimestampFilter(-0.003);
142 }
143
144 // Exhibits a mostly hypothetical problem, where certain inputs to the
145 // TimestampAligner.UpdateOffset filter result in non-monotonous
146 // translated timestamps. This test verifies that the ClipTimestamp
147 // logic handles this case correctly.
TEST(TimestampAlignerTest,ClipToMonotonous)148 TEST(TimestampAlignerTest, ClipToMonotonous) {
149 TimestampAlignerForTest timestamp_aligner;
150
151 // For system time stamps { 0, s1, s1 + s2 }, and camera timestamps
152 // {0, c1, c1 + c2}, we exhibit non-monotonous behaviour if and only
153 // if c1 > s1 + 2 s2 + 4 c2.
154 const int kNumSamples = 3;
155 const int64_t kCaptureTimeUs[kNumSamples] = {0, 80000, 90001};
156 const int64_t kSystemTimeUs[kNumSamples] = {0, 10000, 20000};
157 const int64_t expected_offset_us[kNumSamples] = {0, -35000, -46667};
158
159 // Non-monotonic translated timestamps can happen when only for
160 // translated timestamps in the future. Which is tolerated if
161 // |timestamp_aligner.clip_bias_us| is large enough. Instead of
162 // changing that private member for this test, just add the bias to
163 // |kSystemTimeUs| when calling ClipTimestamp.
164 const int64_t kClipBiasUs = 100000;
165
166 bool did_clip = false;
167 int64_t prev_timestamp_us = std::numeric_limits<int64_t>::min();
168 for (int i = 0; i < kNumSamples; i++) {
169 int64_t offset_us =
170 timestamp_aligner.UpdateOffset(kCaptureTimeUs[i], kSystemTimeUs[i]);
171 EXPECT_EQ(offset_us, expected_offset_us[i]);
172
173 int64_t translated_timestamp_us = kCaptureTimeUs[i] + offset_us;
174 int64_t clip_timestamp_us = timestamp_aligner.ClipTimestamp(
175 translated_timestamp_us, kSystemTimeUs[i] + kClipBiasUs);
176 if (translated_timestamp_us <= prev_timestamp_us) {
177 did_clip = true;
178 EXPECT_EQ(clip_timestamp_us,
179 prev_timestamp_us + rtc::kNumMicrosecsPerMillisec);
180 } else {
181 // No change from clipping.
182 EXPECT_EQ(clip_timestamp_us, translated_timestamp_us);
183 }
184 prev_timestamp_us = clip_timestamp_us;
185 }
186 EXPECT_TRUE(did_clip);
187 }
188
TEST(TimestampAlignerTest,TranslateTimestampWithoutStateUpdate)189 TEST(TimestampAlignerTest, TranslateTimestampWithoutStateUpdate) {
190 TimestampAligner timestamp_aligner;
191
192 constexpr int kNumSamples = 4;
193 constexpr int64_t kCaptureTimeUs[kNumSamples] = {0, 80000, 90001, 100000};
194 constexpr int64_t kSystemTimeUs[kNumSamples] = {0, 10000, 20000, 30000};
195 constexpr int64_t kQueryCaptureTimeOffsetUs[kNumSamples] = {0, 123, -321,
196 345};
197
198 for (int i = 0; i < kNumSamples; i++) {
199 int64_t reference_timestamp = timestamp_aligner.TranslateTimestamp(
200 kCaptureTimeUs[i], kSystemTimeUs[i]);
201 EXPECT_EQ(reference_timestamp - kQueryCaptureTimeOffsetUs[i],
202 timestamp_aligner.TranslateTimestamp(
203 kCaptureTimeUs[i] - kQueryCaptureTimeOffsetUs[i]));
204 }
205 }
206
207 } // namespace rtc
208