asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 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 | |
Mirko Bonadei | 92ea95e | 2017-09-15 06:47:31 +0200 | [diff] [blame] | 11 | #include "system_wrappers/include/rtp_to_ntp_estimator.h" |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 12 | |
Yves Gerey | 988cc08 | 2018-10-23 12:03:01 +0200 | [diff] [blame] | 13 | #include <stddef.h> |
Jonas Olsson | a4d8737 | 2019-07-05 19:08:33 +0200 | [diff] [blame] | 14 | |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 15 | #include <cmath> |
| 16 | #include <vector> |
Yves Gerey | 988cc08 | 2018-10-23 12:03:01 +0200 | [diff] [blame] | 17 | |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 18 | #include "api/array_view.h" |
Mirko Bonadei | 92ea95e | 2017-09-15 06:47:31 +0200 | [diff] [blame] | 19 | #include "rtc_base/checks.h" |
| 20 | #include "rtc_base/logging.h" |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 21 | |
| 22 | namespace webrtc { |
| 23 | namespace { |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 24 | // Maximum number of RTCP SR reports to use to map between RTP and NTP. |
| 25 | const size_t kNumRtcpReportsToUse = 20; |
Ilya Nikolaevskiy | ee45f90 | 2018-11-09 10:52:39 +0100 | [diff] [blame] | 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; |
Ilya Nikolaevskiy | 8b64fd8 | 2017-11-15 16:48:04 +0000 | [diff] [blame] | 31 | |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 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 | } |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 40 | |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 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). |
| 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) |
Ilya Nikolaevskiy | 8b64fd8 | 2017-11-15 16:48:04 +0000 | [diff] [blame] | 49 | return false; |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 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]; |
Ilya Nikolaevskiy | 8b64fd8 | 2017-11-15 16:48:04 +0000 | [diff] [blame] | 59 | } |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 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; |
Ilya Nikolaevskiy | 8b64fd8 | 2017-11-15 16:48:04 +0000 | [diff] [blame] | 78 | } |
| 79 | |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 80 | } // namespace |
Ilya Nikolaevskiy | 8b64fd8 | 2017-11-15 16:48:04 +0000 | [diff] [blame] | 81 | |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 82 | RtpToNtpEstimator::RtcpMeasurement::RtcpMeasurement(uint32_t ntp_secs, |
| 83 | uint32_t ntp_frac, |
Ilya Nikolaevskiy | 558cabf | 2017-11-14 10:32:15 +0100 | [diff] [blame] | 84 | int64_t unwrapped_timestamp) |
| 85 | : ntp_time(ntp_secs, ntp_frac), |
| 86 | unwrapped_rtp_timestamp(unwrapped_timestamp) {} |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 87 | |
| 88 | 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. |
Ilya Nikolaevskiy | 558cabf | 2017-11-14 10:32:15 +0100 | [diff] [blame] | 92 | return (ntp_time == other.ntp_time) || |
| 93 | (unwrapped_rtp_timestamp == other.unwrapped_rtp_timestamp); |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 94 | } |
| 95 | |
| 96 | // Class for converting an RTP timestamp to the NTP domain. |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 97 | RtpToNtpEstimator::RtpToNtpEstimator() : consecutive_invalid_samples_(0) {} |
Ilya Nikolaevskiy | 8b64fd8 | 2017-11-15 16:48:04 +0000 | [diff] [blame] | 98 | |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 99 | RtpToNtpEstimator::~RtpToNtpEstimator() {} |
| 100 | |
| 101 | void RtpToNtpEstimator::UpdateParameters() { |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 102 | if (measurements_.size() < 2) |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 103 | return; |
| 104 | |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 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; |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 114 | |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 115 | if (!LinearRegression(x, y, &slope, &offset)) { |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 116 | return; |
| 117 | } |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 118 | |
| 119 | params_.emplace(1 / slope, offset); |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 120 | } |
| 121 | |
| 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 | |
Ilya Nikolaevskiy | 558cabf | 2017-11-14 10:32:15 +0100 | [diff] [blame] | 128 | int64_t unwrapped_rtp_timestamp = unwrapper_.Unwrap(rtp_timestamp); |
| 129 | |
| 130 | RtcpMeasurement new_measurement(ntp_secs, ntp_frac, unwrapped_rtp_timestamp); |
| 131 | |
stefan | 1009cfc | 2017-06-30 06:28:13 -0700 | [diff] [blame] | 132 | if (Contains(measurements_, new_measurement)) { |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 133 | // RTCP SR report already added. |
| 134 | return true; |
| 135 | } |
Ilya Nikolaevskiy | 8b64fd8 | 2017-11-15 16:48:04 +0000 | [diff] [blame] | 136 | |
stefan | 1009cfc | 2017-06-30 06:28:13 -0700 | [diff] [blame] | 137 | if (!new_measurement.ntp_time.Valid()) |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 138 | return false; |
stefan | 1009cfc | 2017-06-30 06:28:13 -0700 | [diff] [blame] | 139 | |
| 140 | int64_t ntp_ms_new = new_measurement.ntp_time.ToMs(); |
| 141 | bool invalid_sample = false; |
Ilya Nikolaevskiy | 558cabf | 2017-11-14 10:32:15 +0100 | [diff] [blame] | 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(); |
Ilya Nikolaevskiy | ee45f90 | 2018-11-09 10:52:39 +0100 | [diff] [blame] | 145 | if (ntp_ms_new <= old_ntp_ms || |
| 146 | ntp_ms_new > old_ntp_ms + kMaxAllowedRtcpNtpIntervalMs) { |
stefan | 1009cfc | 2017-06-30 06:28:13 -0700 | [diff] [blame] | 147 | invalid_sample = true; |
Ilya Nikolaevskiy | 558cabf | 2017-11-14 10:32:15 +0100 | [diff] [blame] | 148 | } else if (unwrapped_rtp_timestamp <= old_rtp_timestamp) { |
Mirko Bonadei | 675513b | 2017-11-09 11:09:25 +0100 | [diff] [blame] | 149 | RTC_LOG(LS_WARNING) |
stefan | 1009cfc | 2017-06-30 06:28:13 -0700 | [diff] [blame] | 150 | << "Newer RTCP SR report with older RTP timestamp, dropping"; |
| 151 | invalid_sample = true; |
Ilya Nikolaevskiy | 558cabf | 2017-11-14 10:32:15 +0100 | [diff] [blame] | 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; |
stefan | 1009cfc | 2017-06-30 06:28:13 -0700 | [diff] [blame] | 155 | } |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 156 | } |
Ilya Nikolaevskiy | 558cabf | 2017-11-14 10:32:15 +0100 | [diff] [blame] | 157 | |
stefan | 1009cfc | 2017-06-30 06:28:13 -0700 | [diff] [blame] | 158 | if (invalid_sample) { |
| 159 | ++consecutive_invalid_samples_; |
| 160 | if (consecutive_invalid_samples_ < kMaxInvalidSamples) { |
| 161 | return false; |
| 162 | } |
Mirko Bonadei | 675513b | 2017-11-09 11:09:25 +0100 | [diff] [blame] | 163 | RTC_LOG(LS_WARNING) << "Multiple consecutively invalid RTCP SR reports, " |
| 164 | "clearing measurements."; |
stefan | 1009cfc | 2017-06-30 06:28:13 -0700 | [diff] [blame] | 165 | measurements_.clear(); |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 166 | params_ = absl::nullopt; |
stefan | 1009cfc | 2017-06-30 06:28:13 -0700 | [diff] [blame] | 167 | } |
| 168 | consecutive_invalid_samples_ = 0; |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 169 | |
| 170 | // Insert new RTCP SR report. |
| 171 | if (measurements_.size() == kNumRtcpReportsToUse) |
| 172 | measurements_.pop_back(); |
| 173 | |
stefan | 1009cfc | 2017-06-30 06:28:13 -0700 | [diff] [blame] | 174 | measurements_.push_front(new_measurement); |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 175 | *new_rtcp_sr = true; |
| 176 | |
| 177 | // List updated, calculate new parameters. |
| 178 | UpdateParameters(); |
| 179 | return true; |
| 180 | } |
| 181 | |
| 182 | bool RtpToNtpEstimator::Estimate(int64_t rtp_timestamp, |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 183 | int64_t* ntp_timestamp_ms) const { |
| 184 | if (!params_) |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 185 | return false; |
| 186 | |
Ilya Nikolaevskiy | 558cabf | 2017-11-14 10:32:15 +0100 | [diff] [blame] | 187 | int64_t rtp_timestamp_unwrapped = unwrapper_.Unwrap(rtp_timestamp); |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 188 | |
Ilya Nikolaevskiy | 8b64fd8 | 2017-11-15 16:48:04 +0000 | [diff] [blame] | 189 | // params_calculated_ should not be true unless ms params.frequency_khz has |
Ilya Nikolaevskiy | 558cabf | 2017-11-14 10:32:15 +0100 | [diff] [blame] | 190 | // been calculated to something non zero. |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 191 | RTC_DCHECK_NE(params_->frequency_khz, 0.0); |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 192 | double rtp_ms = |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 193 | static_cast<double>(rtp_timestamp_unwrapped) / params_->frequency_khz + |
| 194 | params_->offset_ms + 0.5f; |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 195 | |
| 196 | if (rtp_ms < 0) |
| 197 | return false; |
| 198 | |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 199 | *ntp_timestamp_ms = rtp_ms; |
| 200 | |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 201 | return true; |
| 202 | } |
Ilya Nikolaevskiy | 8b64fd8 | 2017-11-15 16:48:04 +0000 | [diff] [blame] | 203 | |
Danil Chapovalov | 196100e | 2018-06-21 10:17:24 +0200 | [diff] [blame] | 204 | const absl::optional<RtpToNtpEstimator::Parameters> RtpToNtpEstimator::params() |
Ilya Nikolaevskiy | 8b64fd8 | 2017-11-15 16:48:04 +0000 | [diff] [blame] | 205 | const { |
Ilya Nikolaevskiy | f1cc3a2 | 2018-11-12 15:03:51 +0100 | [diff] [blame] | 206 | return params_; |
Ilya Nikolaevskiy | 8b64fd8 | 2017-11-15 16:48:04 +0000 | [diff] [blame] | 207 | } |
asapersson | fe50b4d | 2016-12-22 07:53:51 -0800 | [diff] [blame] | 208 | } // namespace webrtc |