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/neteq/nack.h"
12
13 #include <assert.h> // For assert.
14
15 #include <algorithm> // For std::max.
16
17 #include "webrtc/base/checks.h"
18 #include "webrtc/modules/include/module_common_types.h"
19 #include "webrtc/system_wrappers/include/logging.h"
20
21 namespace webrtc {
22 namespace {
23
24 const int kDefaultSampleRateKhz = 48;
25 const int kDefaultPacketSizeMs = 20;
26
27 } // namespace
28
Nack(int nack_threshold_packets)29 Nack::Nack(int nack_threshold_packets)
30 : nack_threshold_packets_(nack_threshold_packets),
31 sequence_num_last_received_rtp_(0),
32 timestamp_last_received_rtp_(0),
33 any_rtp_received_(false),
34 sequence_num_last_decoded_rtp_(0),
35 timestamp_last_decoded_rtp_(0),
36 any_rtp_decoded_(false),
37 sample_rate_khz_(kDefaultSampleRateKhz),
38 samples_per_packet_(sample_rate_khz_ * kDefaultPacketSizeMs),
39 max_nack_list_size_(kNackListSizeLimit) {}
40
41 Nack::~Nack() = default;
42
Create(int nack_threshold_packets)43 Nack* Nack::Create(int nack_threshold_packets) {
44 return new Nack(nack_threshold_packets);
45 }
46
UpdateSampleRate(int sample_rate_hz)47 void Nack::UpdateSampleRate(int sample_rate_hz) {
48 assert(sample_rate_hz > 0);
49 sample_rate_khz_ = sample_rate_hz / 1000;
50 }
51
UpdateLastReceivedPacket(uint16_t sequence_number,uint32_t timestamp)52 void 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
UpdateSamplesPerPacket(uint16_t sequence_number_current_received_rtp,uint32_t timestamp_current_received_rtp)88 void Nack::UpdateSamplesPerPacket(uint16_t sequence_number_current_received_rtp,
89 uint32_t timestamp_current_received_rtp) {
90 uint32_t timestamp_increase =
91 timestamp_current_received_rtp - timestamp_last_received_rtp_;
92 uint16_t sequence_num_increase =
93 sequence_number_current_received_rtp - sequence_num_last_received_rtp_;
94
95 samples_per_packet_ = timestamp_increase / sequence_num_increase;
96 }
97
UpdateList(uint16_t sequence_number_current_received_rtp)98 void 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
ChangeFromLateToMissing(uint16_t sequence_number_current_received_rtp)107 void Nack::ChangeFromLateToMissing(
108 uint16_t sequence_number_current_received_rtp) {
109 NackList::const_iterator lower_bound =
110 nack_list_.lower_bound(static_cast<uint16_t>(
111 sequence_number_current_received_rtp - nack_threshold_packets_));
112
113 for (NackList::iterator it = nack_list_.begin(); it != lower_bound; ++it)
114 it->second.is_missing = true;
115 }
116
EstimateTimestamp(uint16_t sequence_num)117 uint32_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
AddToList(uint16_t sequence_number_current_received_rtp)122 void Nack::AddToList(uint16_t sequence_number_current_received_rtp) {
123 assert(!any_rtp_decoded_ ||
124 IsNewerSequenceNumber(sequence_number_current_received_rtp,
125 sequence_num_last_decoded_rtp_));
126
127 // Packets with sequence numbers older than |upper_bound_missing| are
128 // considered missing, and the rest are considered late.
129 uint16_t upper_bound_missing =
130 sequence_number_current_received_rtp - nack_threshold_packets_;
131
132 for (uint16_t n = sequence_num_last_received_rtp_ + 1;
133 IsNewerSequenceNumber(sequence_number_current_received_rtp, n); ++n) {
134 bool is_missing = IsNewerSequenceNumber(upper_bound_missing, n);
135 uint32_t timestamp = EstimateTimestamp(n);
136 NackElement nack_element(TimeToPlay(timestamp), timestamp, is_missing);
137 nack_list_.insert(nack_list_.end(), std::make_pair(n, nack_element));
138 }
139 }
140
UpdateEstimatedPlayoutTimeBy10ms()141 void Nack::UpdateEstimatedPlayoutTimeBy10ms() {
142 while (!nack_list_.empty() &&
143 nack_list_.begin()->second.time_to_play_ms <= 10)
144 nack_list_.erase(nack_list_.begin());
145
146 for (NackList::iterator it = nack_list_.begin(); it != nack_list_.end(); ++it)
147 it->second.time_to_play_ms -= 10;
148 }
149
UpdateLastDecodedPacket(uint16_t sequence_number,uint32_t timestamp)150 void Nack::UpdateLastDecodedPacket(uint16_t sequence_number,
151 uint32_t timestamp) {
152 if (IsNewerSequenceNumber(sequence_number, sequence_num_last_decoded_rtp_) ||
153 !any_rtp_decoded_) {
154 sequence_num_last_decoded_rtp_ = sequence_number;
155 timestamp_last_decoded_rtp_ = timestamp;
156 // Packets in the list with sequence numbers less than the
157 // sequence number of the decoded RTP should be removed from the lists.
158 // They will be discarded by the jitter buffer if they arrive.
159 nack_list_.erase(nack_list_.begin(),
160 nack_list_.upper_bound(sequence_num_last_decoded_rtp_));
161
162 // Update estimated time-to-play.
163 for (NackList::iterator it = nack_list_.begin(); it != nack_list_.end();
164 ++it)
165 it->second.time_to_play_ms = TimeToPlay(it->second.estimated_timestamp);
166 } else {
167 assert(sequence_number == sequence_num_last_decoded_rtp_);
168
169 // Same sequence number as before. 10 ms is elapsed, update estimations for
170 // time-to-play.
171 UpdateEstimatedPlayoutTimeBy10ms();
172
173 // Update timestamp for better estimate of time-to-play, for packets which
174 // are added to NACK list later on.
175 timestamp_last_decoded_rtp_ += sample_rate_khz_ * 10;
176 }
177 any_rtp_decoded_ = true;
178 }
179
GetNackList() const180 Nack::NackList Nack::GetNackList() const {
181 return nack_list_;
182 }
183
Reset()184 void Nack::Reset() {
185 nack_list_.clear();
186
187 sequence_num_last_received_rtp_ = 0;
188 timestamp_last_received_rtp_ = 0;
189 any_rtp_received_ = false;
190 sequence_num_last_decoded_rtp_ = 0;
191 timestamp_last_decoded_rtp_ = 0;
192 any_rtp_decoded_ = false;
193 sample_rate_khz_ = kDefaultSampleRateKhz;
194 samples_per_packet_ = sample_rate_khz_ * kDefaultPacketSizeMs;
195 }
196
SetMaxNackListSize(size_t max_nack_list_size)197 void Nack::SetMaxNackListSize(size_t max_nack_list_size) {
198 RTC_CHECK_GT(max_nack_list_size, 0u);
199 // Ugly hack to get around the problem of passing static consts by reference.
200 const size_t kNackListSizeLimitLocal = Nack::kNackListSizeLimit;
201 RTC_CHECK_LE(max_nack_list_size, kNackListSizeLimitLocal);
202
203 max_nack_list_size_ = max_nack_list_size;
204 LimitNackListSize();
205 }
206
LimitNackListSize()207 void Nack::LimitNackListSize() {
208 uint16_t limit = sequence_num_last_received_rtp_ -
209 static_cast<uint16_t>(max_nack_list_size_) - 1;
210 nack_list_.erase(nack_list_.begin(), nack_list_.upper_bound(limit));
211 }
212
TimeToPlay(uint32_t timestamp) const213 int64_t Nack::TimeToPlay(uint32_t timestamp) const {
214 uint32_t timestamp_increase = timestamp - timestamp_last_decoded_rtp_;
215 return timestamp_increase / sample_rate_khz_;
216 }
217
218 // We don't erase elements with time-to-play shorter than round-trip-time.
GetNackList(int64_t round_trip_time_ms) const219 std::vector<uint16_t> Nack::GetNackList(int64_t round_trip_time_ms) const {
220 RTC_DCHECK_GE(round_trip_time_ms, 0);
221 std::vector<uint16_t> sequence_numbers;
222 for (NackList::const_iterator it = nack_list_.begin(); it != nack_list_.end();
223 ++it) {
224 if (it->second.is_missing &&
225 it->second.time_to_play_ms > round_trip_time_ms)
226 sequence_numbers.push_back(it->first);
227 }
228 return sequence_numbers;
229 }
230
231 } // namespace webrtc
232