1 /*
2 * Copyright (c) 2011 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 "modules/video_coding/timing/timestamp_extrapolator.h"
12
13 #include <algorithm>
14
15 #include "absl/types/optional.h"
16 #include "modules/include/module_common_types_public.h"
17
18 namespace webrtc {
19
20 namespace {
21
22 constexpr double kLambda = 1;
23 constexpr uint32_t kStartUpFilterDelayInPackets = 2;
24 constexpr double kAlarmThreshold = 60e3;
25 // in timestamp ticks, i.e. 15 ms
26 constexpr double kAccDrift = 6600;
27 constexpr double kAccMaxError = 7000;
28 constexpr double kP11 = 1e10;
29
30 } // namespace
31
TimestampExtrapolator(Timestamp start)32 TimestampExtrapolator::TimestampExtrapolator(Timestamp start)
33 : start_(Timestamp::Zero()),
34 prev_(Timestamp::Zero()),
35 packet_count_(0),
36 detector_accumulator_pos_(0),
37 detector_accumulator_neg_(0) {
38 Reset(start);
39 }
40
Reset(Timestamp start)41 void TimestampExtrapolator::Reset(Timestamp start) {
42 start_ = start;
43 prev_ = start_;
44 first_unwrapped_timestamp_ = absl::nullopt;
45 w_[0] = 90.0;
46 w_[1] = 0;
47 p_[0][0] = 1;
48 p_[1][1] = kP11;
49 p_[0][1] = p_[1][0] = 0;
50 unwrapper_ = TimestampUnwrapper();
51 packet_count_ = 0;
52 detector_accumulator_pos_ = 0;
53 detector_accumulator_neg_ = 0;
54 }
55
Update(Timestamp now,uint32_t ts90khz)56 void TimestampExtrapolator::Update(Timestamp now, uint32_t ts90khz) {
57 if (now - prev_ > TimeDelta::Seconds(10)) {
58 // Ten seconds without a complete frame.
59 // Reset the extrapolator
60 Reset(now);
61 } else {
62 prev_ = now;
63 }
64
65 // Remove offset to prevent badly scaled matrices
66 const TimeDelta offset = now - start_;
67 double t_ms = offset.ms();
68
69 int64_t unwrapped_ts90khz = unwrapper_.Unwrap(ts90khz);
70
71 if (!first_unwrapped_timestamp_) {
72 // Make an initial guess of the offset,
73 // should be almost correct since t_ms - start
74 // should about zero at this time.
75 w_[1] = -w_[0] * t_ms;
76 first_unwrapped_timestamp_ = unwrapped_ts90khz;
77 }
78
79 double residual =
80 (static_cast<double>(unwrapped_ts90khz) - *first_unwrapped_timestamp_) -
81 t_ms * w_[0] - w_[1];
82 if (DelayChangeDetection(residual) &&
83 packet_count_ >= kStartUpFilterDelayInPackets) {
84 // A sudden change of average network delay has been detected.
85 // Force the filter to adjust its offset parameter by changing
86 // the offset uncertainty. Don't do this during startup.
87 p_[1][1] = kP11;
88 }
89
90 if (prev_unwrapped_timestamp_ &&
91 unwrapped_ts90khz < prev_unwrapped_timestamp_) {
92 // Drop reordered frames.
93 return;
94 }
95
96 // T = [t(k) 1]';
97 // that = T'*w;
98 // K = P*T/(lambda + T'*P*T);
99 double K[2];
100 K[0] = p_[0][0] * t_ms + p_[0][1];
101 K[1] = p_[1][0] * t_ms + p_[1][1];
102 double TPT = kLambda + t_ms * K[0] + K[1];
103 K[0] /= TPT;
104 K[1] /= TPT;
105 // w = w + K*(ts(k) - that);
106 w_[0] = w_[0] + K[0] * residual;
107 w_[1] = w_[1] + K[1] * residual;
108 // P = 1/lambda*(P - K*T'*P);
109 double p00 =
110 1 / kLambda * (p_[0][0] - (K[0] * t_ms * p_[0][0] + K[0] * p_[1][0]));
111 double p01 =
112 1 / kLambda * (p_[0][1] - (K[0] * t_ms * p_[0][1] + K[0] * p_[1][1]));
113 p_[1][0] =
114 1 / kLambda * (p_[1][0] - (K[1] * t_ms * p_[0][0] + K[1] * p_[1][0]));
115 p_[1][1] =
116 1 / kLambda * (p_[1][1] - (K[1] * t_ms * p_[0][1] + K[1] * p_[1][1]));
117 p_[0][0] = p00;
118 p_[0][1] = p01;
119 prev_unwrapped_timestamp_ = unwrapped_ts90khz;
120 if (packet_count_ < kStartUpFilterDelayInPackets) {
121 packet_count_++;
122 }
123 }
124
ExtrapolateLocalTime(uint32_t timestamp90khz) const125 absl::optional<Timestamp> TimestampExtrapolator::ExtrapolateLocalTime(
126 uint32_t timestamp90khz) const {
127 int64_t unwrapped_ts90khz = unwrapper_.UnwrapWithoutUpdate(timestamp90khz);
128
129 if (!first_unwrapped_timestamp_) {
130 return absl::nullopt;
131 } else if (packet_count_ < kStartUpFilterDelayInPackets) {
132 constexpr double kRtpTicksPerMs = 90;
133 TimeDelta diff = TimeDelta::Millis(
134 (unwrapped_ts90khz - *prev_unwrapped_timestamp_) / kRtpTicksPerMs);
135 return prev_ + diff;
136 } else if (w_[0] < 1e-3) {
137 return start_;
138 } else {
139 double timestampDiff = unwrapped_ts90khz - *first_unwrapped_timestamp_;
140 auto diff_ms = static_cast<int64_t>((timestampDiff - w_[1]) / w_[0] + 0.5);
141 return start_ + TimeDelta::Millis(diff_ms);
142 }
143 }
144
DelayChangeDetection(double error)145 bool TimestampExtrapolator::DelayChangeDetection(double error) {
146 // CUSUM detection of sudden delay changes
147 error = (error > 0) ? std::min(error, kAccMaxError)
148 : std::max(error, -kAccMaxError);
149 detector_accumulator_pos_ =
150 std::max(detector_accumulator_pos_ + error - kAccDrift, double{0});
151 detector_accumulator_neg_ =
152 std::min(detector_accumulator_neg_ + error + kAccDrift, double{0});
153 if (detector_accumulator_pos_ > kAlarmThreshold ||
154 detector_accumulator_neg_ < -kAlarmThreshold) {
155 // Alarm
156 detector_accumulator_pos_ = detector_accumulator_neg_ = 0;
157 return true;
158 }
159 return false;
160 }
161
162 } // namespace webrtc
163