1/*
2 *  Copyright (c) 2013 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/main/acm2/nack.h"
12
13#include <assert.h>  // For assert.
14
15#include <algorithm>  // For std::max.
16
17#include "webrtc/modules/interface/module_common_types.h"
18#include "webrtc/system_wrappers/interface/logging.h"
19
20namespace webrtc {
21
22namespace acm2 {
23
24namespace {
25
26const int kDefaultSampleRateKhz = 48;
27const int kDefaultPacketSizeMs = 20;
28
29}  // namespace
30
31Nack::Nack(int nack_threshold_packets)
32    : nack_threshold_packets_(nack_threshold_packets),
33      sequence_num_last_received_rtp_(0),
34      timestamp_last_received_rtp_(0),
35      any_rtp_received_(false),
36      sequence_num_last_decoded_rtp_(0),
37      timestamp_last_decoded_rtp_(0),
38      any_rtp_decoded_(false),
39      sample_rate_khz_(kDefaultSampleRateKhz),
40      samples_per_packet_(sample_rate_khz_ * kDefaultPacketSizeMs),
41      max_nack_list_size_(kNackListSizeLimit) {}
42
43Nack* Nack::Create(int nack_threshold_packets) {
44  return new Nack(nack_threshold_packets);
45}
46
47void Nack::UpdateSampleRate(int sample_rate_hz) {
48  assert(sample_rate_hz > 0);
49  sample_rate_khz_ = sample_rate_hz / 1000;
50}
51
52void Nack::UpdateLastReceivedPacket(uint16_t sequence_number,
53                                    uint32_t timestamp) {
54  // Just record the value of sequence number and timestamp if this is the
55  // first packet.
56  if (!any_rtp_received_) {
57    sequence_num_last_received_rtp_ = sequence_number;
58    timestamp_last_received_rtp_ = timestamp;
59    any_rtp_received_ = true;
60    // If no packet is decoded, to have a reasonable estimate of time-to-play
61    // use the given values.
62    if (!any_rtp_decoded_) {
63      sequence_num_last_decoded_rtp_ = sequence_number;
64      timestamp_last_decoded_rtp_ = timestamp;
65    }
66    return;
67  }
68
69  if (sequence_number == sequence_num_last_received_rtp_)
70    return;
71
72  // Received RTP should not be in the list.
73  nack_list_.erase(sequence_number);
74
75  // If this is an old sequence number, no more action is required, return.
76  if (IsNewerSequenceNumber(sequence_num_last_received_rtp_, sequence_number))
77    return;
78
79  UpdateSamplesPerPacket(sequence_number, timestamp);
80
81  UpdateList(sequence_number);
82
83  sequence_num_last_received_rtp_ = sequence_number;
84  timestamp_last_received_rtp_ = timestamp;
85  LimitNackListSize();
86}
87
88void Nack::UpdateSamplesPerPacket(uint16_t sequence_number_current_received_rtp,
89                                  uint32_t timestamp_current_received_rtp) {
90  uint32_t timestamp_increase = timestamp_current_received_rtp -
91      timestamp_last_received_rtp_;
92  uint16_t sequence_num_increase = sequence_number_current_received_rtp -
93      sequence_num_last_received_rtp_;
94
95  samples_per_packet_ = timestamp_increase / sequence_num_increase;
96}
97
98void Nack::UpdateList(uint16_t sequence_number_current_received_rtp) {
99  // Some of the packets which were considered late, now are considered missing.
100  ChangeFromLateToMissing(sequence_number_current_received_rtp);
101
102  if (IsNewerSequenceNumber(sequence_number_current_received_rtp,
103                            sequence_num_last_received_rtp_ + 1))
104    AddToList(sequence_number_current_received_rtp);
105}
106
107void Nack::ChangeFromLateToMissing(
108    uint16_t sequence_number_current_received_rtp) {
109  NackList::const_iterator lower_bound = nack_list_.lower_bound(
110      static_cast<uint16_t>(sequence_number_current_received_rtp -
111                            nack_threshold_packets_));
112
113  for (NackList::iterator it = nack_list_.begin(); it != lower_bound; ++it)
114    it->second.is_missing = true;
115}
116
117uint32_t Nack::EstimateTimestamp(uint16_t sequence_num) {
118  uint16_t sequence_num_diff = sequence_num - sequence_num_last_received_rtp_;
119  return sequence_num_diff * samples_per_packet_ + timestamp_last_received_rtp_;
120}
121
122void Nack::AddToList(uint16_t sequence_number_current_received_rtp) {
123  assert(!any_rtp_decoded_ || IsNewerSequenceNumber(
124      sequence_number_current_received_rtp, sequence_num_last_decoded_rtp_));
125
126  // Packets with sequence numbers older than |upper_bound_missing| are
127  // considered missing, and the rest are considered late.
128  uint16_t upper_bound_missing = sequence_number_current_received_rtp -
129      nack_threshold_packets_;
130
131  for (uint16_t n = sequence_num_last_received_rtp_ + 1;
132      IsNewerSequenceNumber(sequence_number_current_received_rtp, n); ++n) {
133    bool is_missing = IsNewerSequenceNumber(upper_bound_missing, n);
134    uint32_t timestamp = EstimateTimestamp(n);
135    NackElement nack_element(TimeToPlay(timestamp), timestamp, is_missing);
136    nack_list_.insert(nack_list_.end(), std::make_pair(n, nack_element));
137  }
138}
139
140void Nack::UpdateEstimatedPlayoutTimeBy10ms() {
141  while (!nack_list_.empty() &&
142      nack_list_.begin()->second.time_to_play_ms <= 10)
143    nack_list_.erase(nack_list_.begin());
144
145  for (NackList::iterator it = nack_list_.begin(); it != nack_list_.end(); ++it)
146    it->second.time_to_play_ms -= 10;
147}
148
149void Nack::UpdateLastDecodedPacket(uint16_t sequence_number,
150                                   uint32_t timestamp) {
151  if (IsNewerSequenceNumber(sequence_number, sequence_num_last_decoded_rtp_) ||
152      !any_rtp_decoded_) {
153    sequence_num_last_decoded_rtp_ = sequence_number;
154    timestamp_last_decoded_rtp_ = timestamp;
155    // Packets in the list with sequence numbers less than the
156    // sequence number of the decoded RTP should be removed from the lists.
157    // They will be discarded by the jitter buffer if they arrive.
158    nack_list_.erase(nack_list_.begin(), nack_list_.upper_bound(
159        sequence_num_last_decoded_rtp_));
160
161    // Update estimated time-to-play.
162    for (NackList::iterator it = nack_list_.begin(); it != nack_list_.end();
163        ++it)
164      it->second.time_to_play_ms = TimeToPlay(it->second.estimated_timestamp);
165  } else {
166    assert(sequence_number == sequence_num_last_decoded_rtp_);
167
168    // Same sequence number as before. 10 ms is elapsed, update estimations for
169    // time-to-play.
170    UpdateEstimatedPlayoutTimeBy10ms();
171
172    // Update timestamp for better estimate of time-to-play, for packets which
173    // are added to NACK list later on.
174    timestamp_last_decoded_rtp_ += sample_rate_khz_ * 10;
175  }
176  any_rtp_decoded_ = true;
177}
178
179Nack::NackList Nack::GetNackList() const {
180  return nack_list_;
181}
182
183void Nack::Reset() {
184  nack_list_.clear();
185
186  sequence_num_last_received_rtp_ = 0;
187  timestamp_last_received_rtp_ = 0;
188  any_rtp_received_ = false;
189  sequence_num_last_decoded_rtp_ = 0;
190  timestamp_last_decoded_rtp_ = 0;
191  any_rtp_decoded_ = false;
192  sample_rate_khz_ = kDefaultSampleRateKhz;
193  samples_per_packet_ = sample_rate_khz_ * kDefaultPacketSizeMs;
194}
195
196int Nack::SetMaxNackListSize(size_t max_nack_list_size) {
197  if (max_nack_list_size == 0 || max_nack_list_size > kNackListSizeLimit)
198    return -1;
199  max_nack_list_size_ = max_nack_list_size;
200  LimitNackListSize();
201  return 0;
202}
203
204void Nack::LimitNackListSize() {
205  uint16_t limit = sequence_num_last_received_rtp_ -
206      static_cast<uint16_t>(max_nack_list_size_) - 1;
207  nack_list_.erase(nack_list_.begin(), nack_list_.upper_bound(limit));
208}
209
210int Nack::TimeToPlay(uint32_t timestamp) const {
211  uint32_t timestamp_increase = timestamp - timestamp_last_decoded_rtp_;
212  return timestamp_increase / sample_rate_khz_;
213}
214
215// We don't erase elements with time-to-play shorter than round-trip-time.
216std::vector<uint16_t> Nack::GetNackList(int round_trip_time_ms) const {
217  std::vector<uint16_t> sequence_numbers;
218  for (NackList::const_iterator it = nack_list_.begin(); it != nack_list_.end();
219      ++it) {
220    if (it->second.is_missing &&
221        it->second.time_to_play_ms > round_trip_time_ms)
222      sequence_numbers.push_back(it->first);
223  }
224  return sequence_numbers;
225}
226
227}  // namespace acm2
228
229}  // namespace webrtc
230