Note: We no longer publish the latest version of our code here. We primarily use a kumc-bmi github organization. The heron ETL repository, in particular, is not public. Peers in the informatics community should see MultiSiteDev for details on requesting access.

source: webrtc/webrtc/modules/audio_coding/neteq4/delay_manager.cc @ 0:4bda6873e34c

pub_scrub_3792 tip
Last change on this file since 0:4bda6873e34c was 0:4bda6873e34c, checked in by Michael Prittie <mprittie@…>, 6 years ago

Scrubbed password for publication.

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