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