1 /*
2 * Copyright (c) 2012 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 "system_wrappers/include/rtp_to_ntp_estimator.h"
12
13 #include <stddef.h>
14
15 #include <cmath>
16 #include <vector>
17
18 #include "api/array_view.h"
19 #include "rtc_base/checks.h"
20 #include "rtc_base/logging.h"
21
22 namespace webrtc {
23 namespace {
24 // Maximum number of RTCP SR reports to use to map between RTP and NTP.
25 const size_t kNumRtcpReportsToUse = 20;
26 // Don't allow NTP timestamps to jump more than 1 hour. Chosen arbitrary as big
27 // enough to not affect normal use-cases. Yet it is smaller than RTP wrap-around
28 // half-period (90khz RTP clock wrap-arounds every 13.25 hours). After half of
29 // wrap-around period it is impossible to unwrap RTP timestamps correctly.
30 const int kMaxAllowedRtcpNtpIntervalMs = 60 * 60 * 1000;
31
Contains(const std::list<RtpToNtpEstimator::RtcpMeasurement> & measurements,const RtpToNtpEstimator::RtcpMeasurement & other)32 bool Contains(const std::list<RtpToNtpEstimator::RtcpMeasurement>& measurements,
33 const RtpToNtpEstimator::RtcpMeasurement& other) {
34 for (const auto& measurement : measurements) {
35 if (measurement.IsEqual(other))
36 return true;
37 }
38 return false;
39 }
40
41 // Given x[] and y[] writes out such k and b that line y=k*x+b approximates
42 // given points in the best way (Least Squares Method).
LinearRegression(rtc::ArrayView<const double> x,rtc::ArrayView<const double> y,double * k,double * b)43 bool LinearRegression(rtc::ArrayView<const double> x,
44 rtc::ArrayView<const double> y,
45 double* k,
46 double* b) {
47 size_t n = x.size();
48 if (n < 2)
49 return false;
50
51 if (y.size() != n)
52 return false;
53
54 double avg_x = 0;
55 double avg_y = 0;
56 for (size_t i = 0; i < n; ++i) {
57 avg_x += x[i];
58 avg_y += y[i];
59 }
60 avg_x /= n;
61 avg_y /= n;
62
63 double variance_x = 0;
64 double covariance_xy = 0;
65 for (size_t i = 0; i < n; ++i) {
66 double normalized_x = x[i] - avg_x;
67 double normalized_y = y[i] - avg_y;
68 variance_x += normalized_x * normalized_x;
69 covariance_xy += normalized_x * normalized_y;
70 }
71
72 if (std::fabs(variance_x) < 1e-8)
73 return false;
74
75 *k = static_cast<double>(covariance_xy / variance_x);
76 *b = static_cast<double>(avg_y - (*k) * avg_x);
77 return true;
78 }
79
80 } // namespace
81
RtcpMeasurement(uint32_t ntp_secs,uint32_t ntp_frac,int64_t unwrapped_timestamp)82 RtpToNtpEstimator::RtcpMeasurement::RtcpMeasurement(uint32_t ntp_secs,
83 uint32_t ntp_frac,
84 int64_t unwrapped_timestamp)
85 : ntp_time(ntp_secs, ntp_frac),
86 unwrapped_rtp_timestamp(unwrapped_timestamp) {}
87
IsEqual(const RtcpMeasurement & other) const88 bool RtpToNtpEstimator::RtcpMeasurement::IsEqual(
89 const RtcpMeasurement& other) const {
90 // Use || since two equal timestamps will result in zero frequency and in
91 // RtpToNtpMs, |rtp_timestamp_ms| is estimated by dividing by the frequency.
92 return (ntp_time == other.ntp_time) ||
93 (unwrapped_rtp_timestamp == other.unwrapped_rtp_timestamp);
94 }
95
96 // Class for converting an RTP timestamp to the NTP domain.
RtpToNtpEstimator()97 RtpToNtpEstimator::RtpToNtpEstimator() : consecutive_invalid_samples_(0) {}
98
~RtpToNtpEstimator()99 RtpToNtpEstimator::~RtpToNtpEstimator() {}
100
UpdateParameters()101 void RtpToNtpEstimator::UpdateParameters() {
102 if (measurements_.size() < 2)
103 return;
104
105 std::vector<double> x;
106 std::vector<double> y;
107 x.reserve(measurements_.size());
108 y.reserve(measurements_.size());
109 for (auto it = measurements_.begin(); it != measurements_.end(); ++it) {
110 x.push_back(it->unwrapped_rtp_timestamp);
111 y.push_back(it->ntp_time.ToMs());
112 }
113 double slope, offset;
114
115 if (!LinearRegression(x, y, &slope, &offset)) {
116 return;
117 }
118
119 params_.emplace(1 / slope, offset);
120 }
121
UpdateMeasurements(uint32_t ntp_secs,uint32_t ntp_frac,uint32_t rtp_timestamp,bool * new_rtcp_sr)122 bool RtpToNtpEstimator::UpdateMeasurements(uint32_t ntp_secs,
123 uint32_t ntp_frac,
124 uint32_t rtp_timestamp,
125 bool* new_rtcp_sr) {
126 *new_rtcp_sr = false;
127
128 int64_t unwrapped_rtp_timestamp = unwrapper_.Unwrap(rtp_timestamp);
129
130 RtcpMeasurement new_measurement(ntp_secs, ntp_frac, unwrapped_rtp_timestamp);
131
132 if (Contains(measurements_, new_measurement)) {
133 // RTCP SR report already added.
134 return true;
135 }
136
137 if (!new_measurement.ntp_time.Valid())
138 return false;
139
140 int64_t ntp_ms_new = new_measurement.ntp_time.ToMs();
141 bool invalid_sample = false;
142 if (!measurements_.empty()) {
143 int64_t old_rtp_timestamp = measurements_.front().unwrapped_rtp_timestamp;
144 int64_t old_ntp_ms = measurements_.front().ntp_time.ToMs();
145 if (ntp_ms_new <= old_ntp_ms ||
146 ntp_ms_new > old_ntp_ms + kMaxAllowedRtcpNtpIntervalMs) {
147 invalid_sample = true;
148 } else if (unwrapped_rtp_timestamp <= old_rtp_timestamp) {
149 RTC_LOG(LS_WARNING)
150 << "Newer RTCP SR report with older RTP timestamp, dropping";
151 invalid_sample = true;
152 } else if (unwrapped_rtp_timestamp - old_rtp_timestamp > (1 << 25)) {
153 // Sanity check. No jumps too far into the future in rtp.
154 invalid_sample = true;
155 }
156 }
157
158 if (invalid_sample) {
159 ++consecutive_invalid_samples_;
160 if (consecutive_invalid_samples_ < kMaxInvalidSamples) {
161 return false;
162 }
163 RTC_LOG(LS_WARNING) << "Multiple consecutively invalid RTCP SR reports, "
164 "clearing measurements.";
165 measurements_.clear();
166 params_ = absl::nullopt;
167 }
168 consecutive_invalid_samples_ = 0;
169
170 // Insert new RTCP SR report.
171 if (measurements_.size() == kNumRtcpReportsToUse)
172 measurements_.pop_back();
173
174 measurements_.push_front(new_measurement);
175 *new_rtcp_sr = true;
176
177 // List updated, calculate new parameters.
178 UpdateParameters();
179 return true;
180 }
181
Estimate(int64_t rtp_timestamp,int64_t * ntp_timestamp_ms) const182 bool RtpToNtpEstimator::Estimate(int64_t rtp_timestamp,
183 int64_t* ntp_timestamp_ms) const {
184 if (!params_)
185 return false;
186
187 int64_t rtp_timestamp_unwrapped = unwrapper_.Unwrap(rtp_timestamp);
188
189 // params_calculated_ should not be true unless ms params.frequency_khz has
190 // been calculated to something non zero.
191 RTC_DCHECK_NE(params_->frequency_khz, 0.0);
192 double rtp_ms =
193 static_cast<double>(rtp_timestamp_unwrapped) / params_->frequency_khz +
194 params_->offset_ms + 0.5f;
195
196 if (rtp_ms < 0)
197 return false;
198
199 *ntp_timestamp_ms = rtp_ms;
200
201 return true;
202 }
203
params() const204 const absl::optional<RtpToNtpEstimator::Parameters> RtpToNtpEstimator::params()
205 const {
206 return params_;
207 }
208 } // namespace webrtc
209