Line data Source code
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 "webrtc/modules/audio_coding/neteq/delay_manager.h"
12 :
13 : #include <assert.h>
14 : #include <math.h>
15 :
16 : #include <algorithm> // max, min
17 :
18 : #include "webrtc/base/safe_conversions.h"
19 : #include "webrtc/common_audio/signal_processing/include/signal_processing_library.h"
20 : #include "webrtc/modules/audio_coding/neteq/delay_peak_detector.h"
21 : #include "webrtc/modules/include/module_common_types.h"
22 : #include "webrtc/system_wrappers/include/logging.h"
23 :
24 : namespace webrtc {
25 :
26 0 : DelayManager::DelayManager(size_t max_packets_in_buffer,
27 : DelayPeakDetector* peak_detector,
28 0 : const TickTimer* tick_timer)
29 : : first_packet_received_(false),
30 : max_packets_in_buffer_(max_packets_in_buffer),
31 : iat_vector_(kMaxIat + 1, 0),
32 : iat_factor_(0),
33 : tick_timer_(tick_timer),
34 : base_target_level_(4), // In Q0 domain.
35 0 : target_level_(base_target_level_ << 8), // In Q8 domain.
36 : packet_len_ms_(0),
37 : streaming_mode_(false),
38 : last_seq_no_(0),
39 : last_timestamp_(0),
40 : minimum_delay_ms_(0),
41 0 : least_required_delay_ms_(target_level_),
42 0 : maximum_delay_ms_(target_level_),
43 : iat_cumulative_sum_(0),
44 : max_iat_cumulative_sum_(0),
45 : peak_detector_(*peak_detector),
46 0 : last_pack_cng_or_dtmf_(1) {
47 0 : assert(peak_detector); // Should never be NULL.
48 0 : Reset();
49 0 : }
50 :
51 0 : DelayManager::~DelayManager() {}
52 :
53 0 : const DelayManager::IATVector& DelayManager::iat_vector() const {
54 0 : return iat_vector_;
55 : }
56 :
57 : // Set the histogram vector to an exponentially decaying distribution
58 : // iat_vector_[i] = 0.5^(i+1), i = 0, 1, 2, ...
59 : // iat_vector_ is in Q30.
60 0 : void DelayManager::ResetHistogram() {
61 : // Set temp_prob to (slightly more than) 1 in Q14. This ensures that the sum
62 : // of iat_vector_ is 1.
63 0 : uint16_t temp_prob = 0x4002; // 16384 + 2 = 100000000000010 binary.
64 0 : IATVector::iterator it = iat_vector_.begin();
65 0 : for (; it < iat_vector_.end(); it++) {
66 0 : temp_prob >>= 1;
67 0 : (*it) = temp_prob << 16;
68 : }
69 0 : base_target_level_ = 4;
70 0 : target_level_ = base_target_level_ << 8;
71 0 : }
72 :
73 0 : int DelayManager::Update(uint16_t sequence_number,
74 : uint32_t timestamp,
75 : int sample_rate_hz) {
76 0 : if (sample_rate_hz <= 0) {
77 0 : return -1;
78 : }
79 :
80 0 : if (!first_packet_received_) {
81 : // Prepare for next packet arrival.
82 0 : packet_iat_stopwatch_ = tick_timer_->GetNewStopwatch();
83 0 : last_seq_no_ = sequence_number;
84 0 : last_timestamp_ = timestamp;
85 0 : first_packet_received_ = true;
86 0 : return 0;
87 : }
88 :
89 : // Try calculating packet length from current and previous timestamps.
90 : int packet_len_ms;
91 0 : if (!IsNewerTimestamp(timestamp, last_timestamp_) ||
92 0 : !IsNewerSequenceNumber(sequence_number, last_seq_no_)) {
93 : // Wrong timestamp or sequence order; use stored value.
94 0 : packet_len_ms = packet_len_ms_;
95 : } else {
96 : // Calculate timestamps per packet and derive packet length in ms.
97 : int64_t packet_len_samp =
98 0 : static_cast<uint32_t>(timestamp - last_timestamp_) /
99 0 : static_cast<uint16_t>(sequence_number - last_seq_no_);
100 : packet_len_ms =
101 0 : rtc::saturated_cast<int>(1000 * packet_len_samp / sample_rate_hz);
102 : }
103 :
104 0 : if (packet_len_ms > 0) {
105 : // Cannot update statistics unless |packet_len_ms| is valid.
106 : // Calculate inter-arrival time (IAT) in integer "packet times"
107 : // (rounding down). This is the value used as index to the histogram
108 : // vector |iat_vector_|.
109 0 : int iat_packets = packet_iat_stopwatch_->ElapsedMs() / packet_len_ms;
110 :
111 0 : if (streaming_mode_) {
112 0 : UpdateCumulativeSums(packet_len_ms, sequence_number);
113 : }
114 :
115 : // Check for discontinuous packet sequence and re-ordering.
116 0 : if (IsNewerSequenceNumber(sequence_number, last_seq_no_ + 1)) {
117 : // Compensate for gap in the sequence numbers. Reduce IAT with the
118 : // expected extra time due to lost packets, but ensure that the IAT is
119 : // not negative.
120 0 : iat_packets -= static_cast<uint16_t>(sequence_number - last_seq_no_ - 1);
121 0 : iat_packets = std::max(iat_packets, 0);
122 0 : } else if (!IsNewerSequenceNumber(sequence_number, last_seq_no_)) {
123 0 : iat_packets += static_cast<uint16_t>(last_seq_no_ + 1 - sequence_number);
124 : }
125 :
126 : // Saturate IAT at maximum value.
127 0 : const int max_iat = kMaxIat;
128 0 : iat_packets = std::min(iat_packets, max_iat);
129 0 : UpdateHistogram(iat_packets);
130 : // Calculate new |target_level_| based on updated statistics.
131 0 : target_level_ = CalculateTargetLevel(iat_packets);
132 0 : if (streaming_mode_) {
133 0 : target_level_ = std::max(target_level_, max_iat_cumulative_sum_);
134 : }
135 :
136 0 : LimitTargetLevel();
137 : } // End if (packet_len_ms > 0).
138 :
139 : // Prepare for next packet arrival.
140 0 : packet_iat_stopwatch_ = tick_timer_->GetNewStopwatch();
141 0 : last_seq_no_ = sequence_number;
142 0 : last_timestamp_ = timestamp;
143 0 : return 0;
144 : }
145 :
146 0 : void DelayManager::UpdateCumulativeSums(int packet_len_ms,
147 : uint16_t sequence_number) {
148 : // Calculate IAT in Q8, including fractions of a packet (i.e., more
149 : // accurate than |iat_packets|.
150 : int iat_packets_q8 =
151 0 : (packet_iat_stopwatch_->ElapsedMs() << 8) / packet_len_ms;
152 : // Calculate cumulative sum IAT with sequence number compensation. The sum
153 : // is zero if there is no clock-drift.
154 0 : iat_cumulative_sum_ += (iat_packets_q8 -
155 0 : (static_cast<int>(sequence_number - last_seq_no_) << 8));
156 : // Subtract drift term.
157 0 : iat_cumulative_sum_ -= kCumulativeSumDrift;
158 : // Ensure not negative.
159 0 : iat_cumulative_sum_ = std::max(iat_cumulative_sum_, 0);
160 0 : if (iat_cumulative_sum_ > max_iat_cumulative_sum_) {
161 : // Found a new maximum.
162 0 : max_iat_cumulative_sum_ = iat_cumulative_sum_;
163 0 : max_iat_stopwatch_ = tick_timer_->GetNewStopwatch();
164 : }
165 0 : if (max_iat_stopwatch_->ElapsedMs() > kMaxStreamingPeakPeriodMs) {
166 : // Too long since the last maximum was observed; decrease max value.
167 0 : max_iat_cumulative_sum_ -= kCumulativeSumDrift;
168 : }
169 0 : }
170 :
171 : // Each element in the vector is first multiplied by the forgetting factor
172 : // |iat_factor_|. Then the vector element indicated by |iat_packets| is then
173 : // increased (additive) by 1 - |iat_factor_|. This way, the probability of
174 : // |iat_packets| is slightly increased, while the sum of the histogram remains
175 : // constant (=1).
176 : // Due to inaccuracies in the fixed-point arithmetic, the histogram may no
177 : // longer sum up to 1 (in Q30) after the update. To correct this, a correction
178 : // term is added or subtracted from the first element (or elements) of the
179 : // vector.
180 : // The forgetting factor |iat_factor_| is also updated. When the DelayManager
181 : // is reset, the factor is set to 0 to facilitate rapid convergence in the
182 : // beginning. With each update of the histogram, the factor is increased towards
183 : // the steady-state value |kIatFactor_|.
184 0 : void DelayManager::UpdateHistogram(size_t iat_packets) {
185 0 : assert(iat_packets < iat_vector_.size());
186 0 : int vector_sum = 0; // Sum up the vector elements as they are processed.
187 : // Multiply each element in |iat_vector_| with |iat_factor_|.
188 0 : for (IATVector::iterator it = iat_vector_.begin();
189 0 : it != iat_vector_.end(); ++it) {
190 0 : *it = (static_cast<int64_t>(*it) * iat_factor_) >> 15;
191 0 : vector_sum += *it;
192 : }
193 :
194 : // Increase the probability for the currently observed inter-arrival time
195 : // by 1 - |iat_factor_|. The factor is in Q15, |iat_vector_| in Q30.
196 : // Thus, left-shift 15 steps to obtain result in Q30.
197 0 : iat_vector_[iat_packets] += (32768 - iat_factor_) << 15;
198 0 : vector_sum += (32768 - iat_factor_) << 15; // Add to vector sum.
199 :
200 : // |iat_vector_| should sum up to 1 (in Q30), but it may not due to
201 : // fixed-point rounding errors.
202 0 : vector_sum -= 1 << 30; // Should be zero. Compensate if not.
203 0 : if (vector_sum != 0) {
204 : // Modify a few values early in |iat_vector_|.
205 0 : int flip_sign = vector_sum > 0 ? -1 : 1;
206 0 : IATVector::iterator it = iat_vector_.begin();
207 0 : while (it != iat_vector_.end() && abs(vector_sum) > 0) {
208 : // Add/subtract 1/16 of the element, but not more than |vector_sum|.
209 0 : int correction = flip_sign * std::min(abs(vector_sum), (*it) >> 4);
210 0 : *it += correction;
211 0 : vector_sum += correction;
212 0 : ++it;
213 : }
214 : }
215 0 : assert(vector_sum == 0); // Verify that the above is correct.
216 :
217 : // Update |iat_factor_| (changes only during the first seconds after a reset).
218 : // The factor converges to |kIatFactor_|.
219 0 : iat_factor_ += (kIatFactor_ - iat_factor_ + 3) >> 2;
220 0 : }
221 :
222 : // Enforces upper and lower limits for |target_level_|. The upper limit is
223 : // chosen to be minimum of i) 75% of |max_packets_in_buffer_|, to leave some
224 : // headroom for natural fluctuations around the target, and ii) equivalent of
225 : // |maximum_delay_ms_| in packets. Note that in practice, if no
226 : // |maximum_delay_ms_| is specified, this does not have any impact, since the
227 : // target level is far below the buffer capacity in all reasonable cases.
228 : // The lower limit is equivalent of |minimum_delay_ms_| in packets. We update
229 : // |least_required_level_| while the above limits are applied.
230 : // TODO(hlundin): Move this check to the buffer logistics class.
231 0 : void DelayManager::LimitTargetLevel() {
232 0 : least_required_delay_ms_ = (target_level_ * packet_len_ms_) >> 8;
233 :
234 0 : if (packet_len_ms_ > 0 && minimum_delay_ms_ > 0) {
235 0 : int minimum_delay_packet_q8 = (minimum_delay_ms_ << 8) / packet_len_ms_;
236 0 : target_level_ = std::max(target_level_, minimum_delay_packet_q8);
237 : }
238 :
239 0 : if (maximum_delay_ms_ > 0 && packet_len_ms_ > 0) {
240 0 : int maximum_delay_packet_q8 = (maximum_delay_ms_ << 8) / packet_len_ms_;
241 0 : target_level_ = std::min(target_level_, maximum_delay_packet_q8);
242 : }
243 :
244 : // Shift to Q8, then 75%.;
245 : int max_buffer_packets_q8 =
246 0 : static_cast<int>((3 * (max_packets_in_buffer_ << 8)) / 4);
247 0 : target_level_ = std::min(target_level_, max_buffer_packets_q8);
248 :
249 : // Sanity check, at least 1 packet (in Q8).
250 0 : target_level_ = std::max(target_level_, 1 << 8);
251 0 : }
252 :
253 0 : int DelayManager::CalculateTargetLevel(int iat_packets) {
254 0 : int limit_probability = kLimitProbability;
255 0 : if (streaming_mode_) {
256 0 : limit_probability = kLimitProbabilityStreaming;
257 : }
258 :
259 : // Calculate target buffer level from inter-arrival time histogram.
260 : // Find the |iat_index| for which the probability of observing an
261 : // inter-arrival time larger than or equal to |iat_index| is less than or
262 : // equal to |limit_probability|. The sought probability is estimated using
263 : // the histogram as the reverse cumulant PDF, i.e., the sum of elements from
264 : // the end up until |iat_index|. Now, since the sum of all elements is 1
265 : // (in Q30) by definition, and since the solution is often a low value for
266 : // |iat_index|, it is more efficient to start with |sum| = 1 and subtract
267 : // elements from the start of the histogram.
268 0 : size_t index = 0; // Start from the beginning of |iat_vector_|.
269 0 : int sum = 1 << 30; // Assign to 1 in Q30.
270 0 : sum -= iat_vector_[index]; // Ensure that target level is >= 1.
271 :
272 0 : do {
273 : // Subtract the probabilities one by one until the sum is no longer greater
274 : // than limit_probability.
275 0 : ++index;
276 0 : sum -= iat_vector_[index];
277 0 : } while ((sum > limit_probability) && (index < iat_vector_.size() - 1));
278 :
279 : // This is the base value for the target buffer level.
280 0 : int target_level = static_cast<int>(index);
281 0 : base_target_level_ = static_cast<int>(index);
282 :
283 : // Update detector for delay peaks.
284 0 : bool delay_peak_found = peak_detector_.Update(iat_packets, target_level);
285 0 : if (delay_peak_found) {
286 0 : target_level = std::max(target_level, peak_detector_.MaxPeakHeight());
287 : }
288 :
289 : // Sanity check. |target_level| must be strictly positive.
290 0 : target_level = std::max(target_level, 1);
291 : // Scale to Q8 and assign to member variable.
292 0 : target_level_ = target_level << 8;
293 0 : return target_level_;
294 : }
295 :
296 0 : int DelayManager::SetPacketAudioLength(int length_ms) {
297 0 : if (length_ms <= 0) {
298 0 : LOG_F(LS_ERROR) << "length_ms = " << length_ms;
299 0 : return -1;
300 : }
301 0 : packet_len_ms_ = length_ms;
302 0 : peak_detector_.SetPacketAudioLength(packet_len_ms_);
303 0 : packet_iat_stopwatch_ = tick_timer_->GetNewStopwatch();
304 0 : last_pack_cng_or_dtmf_ = 1; // TODO(hlundin): Legacy. Remove?
305 0 : return 0;
306 : }
307 :
308 :
309 0 : void DelayManager::Reset() {
310 0 : packet_len_ms_ = 0; // Packet size unknown.
311 0 : streaming_mode_ = false;
312 0 : peak_detector_.Reset();
313 0 : ResetHistogram(); // Resets target levels too.
314 0 : iat_factor_ = 0; // Adapt the histogram faster for the first few packets.
315 0 : packet_iat_stopwatch_ = tick_timer_->GetNewStopwatch();
316 0 : max_iat_stopwatch_ = tick_timer_->GetNewStopwatch();
317 0 : iat_cumulative_sum_ = 0;
318 0 : max_iat_cumulative_sum_ = 0;
319 0 : last_pack_cng_or_dtmf_ = 1;
320 0 : }
321 :
322 0 : double DelayManager::EstimatedClockDriftPpm() const {
323 0 : double sum = 0.0;
324 : // Calculate the expected value based on the probabilities in |iat_vector_|.
325 0 : for (size_t i = 0; i < iat_vector_.size(); ++i) {
326 0 : sum += static_cast<double>(iat_vector_[i]) * i;
327 : }
328 : // The probabilities in |iat_vector_| are in Q30. Divide by 1 << 30 to convert
329 : // to Q0; subtract the nominal inter-arrival time (1) to make a zero
330 : // clockdrift represent as 0; mulitply by 1000000 to produce parts-per-million
331 : // (ppm).
332 0 : return (sum / (1 << 30) - 1) * 1e6;
333 : }
334 :
335 0 : bool DelayManager::PeakFound() const {
336 0 : return peak_detector_.peak_found();
337 : }
338 :
339 0 : void DelayManager::ResetPacketIatCount() {
340 0 : packet_iat_stopwatch_ = tick_timer_->GetNewStopwatch();
341 0 : }
342 :
343 : // Note that |low_limit| and |higher_limit| are not assigned to
344 : // |minimum_delay_ms_| and |maximum_delay_ms_| defined by the client of this
345 : // class. They are computed from |target_level_| and used for decision making.
346 0 : void DelayManager::BufferLimits(int* lower_limit, int* higher_limit) const {
347 0 : if (!lower_limit || !higher_limit) {
348 0 : LOG_F(LS_ERROR) << "NULL pointers supplied as input";
349 0 : assert(false);
350 : return;
351 : }
352 :
353 0 : int window_20ms = 0x7FFF; // Default large value for legacy bit-exactness.
354 0 : if (packet_len_ms_ > 0) {
355 0 : window_20ms = (20 << 8) / packet_len_ms_;
356 : }
357 :
358 : // |target_level_| is in Q8 already.
359 0 : *lower_limit = (target_level_ * 3) / 4;
360 : // |higher_limit| is equal to |target_level_|, but should at
361 : // least be 20 ms higher than |lower_limit_|.
362 0 : *higher_limit = std::max(target_level_, *lower_limit + window_20ms);
363 : }
364 :
365 0 : int DelayManager::TargetLevel() const {
366 0 : return target_level_;
367 : }
368 :
369 0 : void DelayManager::LastDecodedWasCngOrDtmf(bool it_was) {
370 0 : if (it_was) {
371 0 : last_pack_cng_or_dtmf_ = 1;
372 0 : } else if (last_pack_cng_or_dtmf_ != 0) {
373 0 : last_pack_cng_or_dtmf_ = -1;
374 : }
375 0 : }
376 :
377 0 : bool DelayManager::SetMinimumDelay(int delay_ms) {
378 : // Minimum delay shouldn't be more than maximum delay, if any maximum is set.
379 : // Also, if possible check |delay| to less than 75% of
380 : // |max_packets_in_buffer_|.
381 0 : if ((maximum_delay_ms_ > 0 && delay_ms > maximum_delay_ms_) ||
382 0 : (packet_len_ms_ > 0 &&
383 0 : delay_ms >
384 0 : static_cast<int>(3 * max_packets_in_buffer_ * packet_len_ms_ / 4))) {
385 0 : return false;
386 : }
387 0 : minimum_delay_ms_ = delay_ms;
388 0 : return true;
389 : }
390 :
391 0 : bool DelayManager::SetMaximumDelay(int delay_ms) {
392 0 : if (delay_ms == 0) {
393 : // Zero input unsets the maximum delay.
394 0 : maximum_delay_ms_ = 0;
395 0 : return true;
396 0 : } else if (delay_ms < minimum_delay_ms_ || delay_ms < packet_len_ms_) {
397 : // Maximum delay shouldn't be less than minimum delay or less than a packet.
398 0 : return false;
399 : }
400 0 : maximum_delay_ms_ = delay_ms;
401 0 : return true;
402 : }
403 :
404 0 : int DelayManager::least_required_delay_ms() const {
405 0 : return least_required_delay_ms_;
406 : }
407 :
408 0 : int DelayManager::base_target_level() const { return base_target_level_; }
409 0 : void DelayManager::set_streaming_mode(bool value) { streaming_mode_ = value; }
410 0 : int DelayManager::last_pack_cng_or_dtmf() const {
411 0 : return last_pack_cng_or_dtmf_;
412 : }
413 :
414 0 : void DelayManager::set_last_pack_cng_or_dtmf(int value) {
415 0 : last_pack_cng_or_dtmf_ = value;
416 0 : }
417 : } // namespace webrtc
|
