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 "modules/audio_coding/neteq/nack_tracker.h"
12
13 #include <stdint.h>
14
15 #include <algorithm>
16 #include <memory>
17
18 #include "modules/audio_coding/include/audio_coding_module_typedefs.h"
19 #include "test/gtest.h"
20
21 namespace webrtc {
22 namespace {
23
24 const int kNackThreshold = 3;
25 const int kSampleRateHz = 16000;
26 const int kPacketSizeMs = 30;
27 const uint32_t kTimestampIncrement = 480; // 30 ms.
28 const int64_t kShortRoundTripTimeMs = 1;
29
IsNackListCorrect(const std::vector<uint16_t> & nack_list,const uint16_t * lost_sequence_numbers,size_t num_lost_packets)30 bool IsNackListCorrect(const std::vector<uint16_t>& nack_list,
31 const uint16_t* lost_sequence_numbers,
32 size_t num_lost_packets) {
33 if (nack_list.size() != num_lost_packets)
34 return false;
35
36 if (num_lost_packets == 0)
37 return true;
38
39 for (size_t k = 0; k < nack_list.size(); ++k) {
40 int seq_num = nack_list[k];
41 bool seq_num_matched = false;
42 for (size_t n = 0; n < num_lost_packets; ++n) {
43 if (seq_num == lost_sequence_numbers[n]) {
44 seq_num_matched = true;
45 break;
46 }
47 }
48 if (!seq_num_matched)
49 return false;
50 }
51 return true;
52 }
53
54 } // namespace
55
TEST(NackTrackerTest,EmptyListWhenNoPacketLoss)56 TEST(NackTrackerTest, EmptyListWhenNoPacketLoss) {
57 std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
58 nack->UpdateSampleRate(kSampleRateHz);
59
60 int seq_num = 1;
61 uint32_t timestamp = 0;
62
63 std::vector<uint16_t> nack_list;
64 for (int n = 0; n < 100; n++) {
65 nack->UpdateLastReceivedPacket(seq_num, timestamp);
66 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
67 seq_num++;
68 timestamp += kTimestampIncrement;
69 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
70 EXPECT_TRUE(nack_list.empty());
71 }
72 }
73
TEST(NackTrackerTest,NoNackIfReorderWithinNackThreshold)74 TEST(NackTrackerTest, NoNackIfReorderWithinNackThreshold) {
75 std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
76 nack->UpdateSampleRate(kSampleRateHz);
77
78 int seq_num = 1;
79 uint32_t timestamp = 0;
80 std::vector<uint16_t> nack_list;
81
82 nack->UpdateLastReceivedPacket(seq_num, timestamp);
83 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
84 EXPECT_TRUE(nack_list.empty());
85 int num_late_packets = kNackThreshold + 1;
86
87 // Push in reverse order
88 while (num_late_packets > 0) {
89 nack->UpdateLastReceivedPacket(
90 seq_num + num_late_packets,
91 timestamp + num_late_packets * kTimestampIncrement);
92 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
93 EXPECT_TRUE(nack_list.empty());
94 num_late_packets--;
95 }
96 }
97
TEST(NackTrackerTest,LatePacketsMovedToNackThenNackListDoesNotChange)98 TEST(NackTrackerTest, LatePacketsMovedToNackThenNackListDoesNotChange) {
99 const uint16_t kSequenceNumberLostPackets[] = {2, 3, 4, 5, 6, 7, 8, 9};
100 static const int kNumAllLostPackets = sizeof(kSequenceNumberLostPackets) /
101 sizeof(kSequenceNumberLostPackets[0]);
102
103 for (int k = 0; k < 2; k++) { // Two iteration with/without wrap around.
104 std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
105 nack->UpdateSampleRate(kSampleRateHz);
106
107 uint16_t sequence_num_lost_packets[kNumAllLostPackets];
108 for (int n = 0; n < kNumAllLostPackets; n++) {
109 sequence_num_lost_packets[n] =
110 kSequenceNumberLostPackets[n] +
111 k * 65531; // Have wrap around in sequence numbers for |k == 1|.
112 }
113 uint16_t seq_num = sequence_num_lost_packets[0] - 1;
114
115 uint32_t timestamp = 0;
116 std::vector<uint16_t> nack_list;
117
118 nack->UpdateLastReceivedPacket(seq_num, timestamp);
119 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
120 EXPECT_TRUE(nack_list.empty());
121
122 seq_num = sequence_num_lost_packets[kNumAllLostPackets - 1] + 1;
123 timestamp += kTimestampIncrement * (kNumAllLostPackets + 1);
124 int num_lost_packets = std::max(0, kNumAllLostPackets - kNackThreshold);
125
126 for (int n = 0; n < kNackThreshold + 1; ++n) {
127 nack->UpdateLastReceivedPacket(seq_num, timestamp);
128 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
129 EXPECT_TRUE(IsNackListCorrect(nack_list, sequence_num_lost_packets,
130 num_lost_packets));
131 seq_num++;
132 timestamp += kTimestampIncrement;
133 num_lost_packets++;
134 }
135
136 for (int n = 0; n < 100; ++n) {
137 nack->UpdateLastReceivedPacket(seq_num, timestamp);
138 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
139 EXPECT_TRUE(IsNackListCorrect(nack_list, sequence_num_lost_packets,
140 kNumAllLostPackets));
141 seq_num++;
142 timestamp += kTimestampIncrement;
143 }
144 }
145 }
146
TEST(NackTrackerTest,ArrivedPacketsAreRemovedFromNackList)147 TEST(NackTrackerTest, ArrivedPacketsAreRemovedFromNackList) {
148 const uint16_t kSequenceNumberLostPackets[] = {2, 3, 4, 5, 6, 7, 8, 9};
149 static const int kNumAllLostPackets = sizeof(kSequenceNumberLostPackets) /
150 sizeof(kSequenceNumberLostPackets[0]);
151
152 for (int k = 0; k < 2; ++k) { // Two iteration with/without wrap around.
153 std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
154 nack->UpdateSampleRate(kSampleRateHz);
155
156 uint16_t sequence_num_lost_packets[kNumAllLostPackets];
157 for (int n = 0; n < kNumAllLostPackets; ++n) {
158 sequence_num_lost_packets[n] = kSequenceNumberLostPackets[n] +
159 k * 65531; // Wrap around for |k == 1|.
160 }
161
162 uint16_t seq_num = sequence_num_lost_packets[0] - 1;
163 uint32_t timestamp = 0;
164
165 nack->UpdateLastReceivedPacket(seq_num, timestamp);
166 std::vector<uint16_t> nack_list = nack->GetNackList(kShortRoundTripTimeMs);
167 EXPECT_TRUE(nack_list.empty());
168
169 size_t index_retransmitted_rtp = 0;
170 uint32_t timestamp_retransmitted_rtp = timestamp + kTimestampIncrement;
171
172 seq_num = sequence_num_lost_packets[kNumAllLostPackets - 1] + 1;
173 timestamp += kTimestampIncrement * (kNumAllLostPackets + 1);
174 size_t num_lost_packets = std::max(0, kNumAllLostPackets - kNackThreshold);
175 for (int n = 0; n < kNumAllLostPackets; ++n) {
176 // Number of lost packets does not change for the first
177 // |kNackThreshold + 1| packets, one is added to the list and one is
178 // removed. Thereafter, the list shrinks every iteration.
179 if (n >= kNackThreshold + 1)
180 num_lost_packets--;
181
182 nack->UpdateLastReceivedPacket(seq_num, timestamp);
183 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
184 EXPECT_TRUE(IsNackListCorrect(
185 nack_list, &sequence_num_lost_packets[index_retransmitted_rtp],
186 num_lost_packets));
187 seq_num++;
188 timestamp += kTimestampIncrement;
189
190 // Retransmission of a lost RTP.
191 nack->UpdateLastReceivedPacket(
192 sequence_num_lost_packets[index_retransmitted_rtp],
193 timestamp_retransmitted_rtp);
194 index_retransmitted_rtp++;
195 timestamp_retransmitted_rtp += kTimestampIncrement;
196
197 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
198 EXPECT_TRUE(IsNackListCorrect(
199 nack_list, &sequence_num_lost_packets[index_retransmitted_rtp],
200 num_lost_packets - 1)); // One less lost packet in the list.
201 }
202 ASSERT_TRUE(nack_list.empty());
203 }
204 }
205
206 // Assess if estimation of timestamps and time-to-play is correct. Introduce all
207 // combinations that timestamps and sequence numbers might have wrap around.
TEST(NackTrackerTest,EstimateTimestampAndTimeToPlay)208 TEST(NackTrackerTest, EstimateTimestampAndTimeToPlay) {
209 const uint16_t kLostPackets[] = {2, 3, 4, 5, 6, 7, 8,
210 9, 10, 11, 12, 13, 14, 15};
211 static const int kNumAllLostPackets =
212 sizeof(kLostPackets) / sizeof(kLostPackets[0]);
213
214 for (int k = 0; k < 4; ++k) {
215 std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
216 nack->UpdateSampleRate(kSampleRateHz);
217
218 // Sequence number wrap around if |k| is 2 or 3;
219 int seq_num_offset = (k < 2) ? 0 : 65531;
220
221 // Timestamp wrap around if |k| is 1 or 3.
222 uint32_t timestamp_offset =
223 (k & 0x1) ? static_cast<uint32_t>(0xffffffff) - 6 : 0;
224
225 uint32_t timestamp_lost_packets[kNumAllLostPackets];
226 uint16_t seq_num_lost_packets[kNumAllLostPackets];
227 for (int n = 0; n < kNumAllLostPackets; ++n) {
228 timestamp_lost_packets[n] =
229 timestamp_offset + kLostPackets[n] * kTimestampIncrement;
230 seq_num_lost_packets[n] = seq_num_offset + kLostPackets[n];
231 }
232
233 // We and to push two packets before lost burst starts.
234 uint16_t seq_num = seq_num_lost_packets[0] - 2;
235 uint32_t timestamp = timestamp_lost_packets[0] - 2 * kTimestampIncrement;
236
237 const uint16_t first_seq_num = seq_num;
238 const uint32_t first_timestamp = timestamp;
239
240 // Two consecutive packets to have a correct estimate of timestamp increase.
241 nack->UpdateLastReceivedPacket(seq_num, timestamp);
242 seq_num++;
243 timestamp += kTimestampIncrement;
244 nack->UpdateLastReceivedPacket(seq_num, timestamp);
245
246 // A packet after the last one which is supposed to be lost.
247 seq_num = seq_num_lost_packets[kNumAllLostPackets - 1] + 1;
248 timestamp =
249 timestamp_lost_packets[kNumAllLostPackets - 1] + kTimestampIncrement;
250 nack->UpdateLastReceivedPacket(seq_num, timestamp);
251
252 NackTracker::NackList nack_list = nack->GetNackList();
253 EXPECT_EQ(static_cast<size_t>(kNumAllLostPackets), nack_list.size());
254
255 // Pretend the first packet is decoded.
256 nack->UpdateLastDecodedPacket(first_seq_num, first_timestamp);
257 nack_list = nack->GetNackList();
258
259 NackTracker::NackList::iterator it = nack_list.begin();
260 while (it != nack_list.end()) {
261 seq_num = it->first - seq_num_offset;
262 int index = seq_num - kLostPackets[0];
263 EXPECT_EQ(timestamp_lost_packets[index], it->second.estimated_timestamp);
264 EXPECT_EQ((index + 2) * kPacketSizeMs, it->second.time_to_play_ms);
265 ++it;
266 }
267
268 // Pretend 10 ms is passed, and we had pulled audio from NetEq, it still
269 // reports the same sequence number as decoded, time-to-play should be
270 // updated by 10 ms.
271 nack->UpdateLastDecodedPacket(first_seq_num, first_timestamp);
272 nack_list = nack->GetNackList();
273 it = nack_list.begin();
274 while (it != nack_list.end()) {
275 seq_num = it->first - seq_num_offset;
276 int index = seq_num - kLostPackets[0];
277 EXPECT_EQ((index + 2) * kPacketSizeMs - 10, it->second.time_to_play_ms);
278 ++it;
279 }
280 }
281 }
282
TEST(NackTrackerTest,MissingPacketsPriorToLastDecodedRtpShouldNotBeInNackList)283 TEST(NackTrackerTest,
284 MissingPacketsPriorToLastDecodedRtpShouldNotBeInNackList) {
285 for (int m = 0; m < 2; ++m) {
286 uint16_t seq_num_offset = (m == 0) ? 0 : 65531; // Wrap around if |m| is 1.
287 std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
288 nack->UpdateSampleRate(kSampleRateHz);
289
290 // Two consecutive packets to have a correct estimate of timestamp increase.
291 uint16_t seq_num = 0;
292 nack->UpdateLastReceivedPacket(seq_num_offset + seq_num,
293 seq_num * kTimestampIncrement);
294 seq_num++;
295 nack->UpdateLastReceivedPacket(seq_num_offset + seq_num,
296 seq_num * kTimestampIncrement);
297
298 // Skip 10 packets (larger than NACK threshold).
299 const int kNumLostPackets = 10;
300 seq_num += kNumLostPackets + 1;
301 nack->UpdateLastReceivedPacket(seq_num_offset + seq_num,
302 seq_num * kTimestampIncrement);
303
304 const size_t kExpectedListSize = kNumLostPackets - kNackThreshold;
305 std::vector<uint16_t> nack_list = nack->GetNackList(kShortRoundTripTimeMs);
306 EXPECT_EQ(kExpectedListSize, nack_list.size());
307
308 for (int k = 0; k < 2; ++k) {
309 // Decoding of the first and the second arrived packets.
310 for (int n = 0; n < kPacketSizeMs / 10; ++n) {
311 nack->UpdateLastDecodedPacket(seq_num_offset + k,
312 k * kTimestampIncrement);
313 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
314 EXPECT_EQ(kExpectedListSize, nack_list.size());
315 }
316 }
317
318 // Decoding of the last received packet.
319 nack->UpdateLastDecodedPacket(seq_num + seq_num_offset,
320 seq_num * kTimestampIncrement);
321 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
322 EXPECT_TRUE(nack_list.empty());
323
324 // Make sure list of late packets is also empty. To check that, push few
325 // packets, if the late list is not empty its content will pop up in NACK
326 // list.
327 for (int n = 0; n < kNackThreshold + 10; ++n) {
328 seq_num++;
329 nack->UpdateLastReceivedPacket(seq_num_offset + seq_num,
330 seq_num * kTimestampIncrement);
331 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
332 EXPECT_TRUE(nack_list.empty());
333 }
334 }
335 }
336
TEST(NackTrackerTest,Reset)337 TEST(NackTrackerTest, Reset) {
338 std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
339 nack->UpdateSampleRate(kSampleRateHz);
340
341 // Two consecutive packets to have a correct estimate of timestamp increase.
342 uint16_t seq_num = 0;
343 nack->UpdateLastReceivedPacket(seq_num, seq_num * kTimestampIncrement);
344 seq_num++;
345 nack->UpdateLastReceivedPacket(seq_num, seq_num * kTimestampIncrement);
346
347 // Skip 10 packets (larger than NACK threshold).
348 const int kNumLostPackets = 10;
349 seq_num += kNumLostPackets + 1;
350 nack->UpdateLastReceivedPacket(seq_num, seq_num * kTimestampIncrement);
351
352 const size_t kExpectedListSize = kNumLostPackets - kNackThreshold;
353 std::vector<uint16_t> nack_list = nack->GetNackList(kShortRoundTripTimeMs);
354 EXPECT_EQ(kExpectedListSize, nack_list.size());
355
356 nack->Reset();
357 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
358 EXPECT_TRUE(nack_list.empty());
359 }
360
TEST(NackTrackerTest,ListSizeAppliedFromBeginning)361 TEST(NackTrackerTest, ListSizeAppliedFromBeginning) {
362 const size_t kNackListSize = 10;
363 for (int m = 0; m < 2; ++m) {
364 uint16_t seq_num_offset = (m == 0) ? 0 : 65525; // Wrap around if |m| is 1.
365 std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
366 nack->UpdateSampleRate(kSampleRateHz);
367 nack->SetMaxNackListSize(kNackListSize);
368
369 uint16_t seq_num = seq_num_offset;
370 uint32_t timestamp = 0x12345678;
371 nack->UpdateLastReceivedPacket(seq_num, timestamp);
372
373 // Packet lost more than NACK-list size limit.
374 uint16_t num_lost_packets = kNackThreshold + kNackListSize + 5;
375
376 seq_num += num_lost_packets + 1;
377 timestamp += (num_lost_packets + 1) * kTimestampIncrement;
378 nack->UpdateLastReceivedPacket(seq_num, timestamp);
379
380 std::vector<uint16_t> nack_list = nack->GetNackList(kShortRoundTripTimeMs);
381 EXPECT_EQ(kNackListSize - kNackThreshold, nack_list.size());
382 }
383 }
384
TEST(NackTrackerTest,ChangeOfListSizeAppliedAndOldElementsRemoved)385 TEST(NackTrackerTest, ChangeOfListSizeAppliedAndOldElementsRemoved) {
386 const size_t kNackListSize = 10;
387 for (int m = 0; m < 2; ++m) {
388 uint16_t seq_num_offset = (m == 0) ? 0 : 65525; // Wrap around if |m| is 1.
389 std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
390 nack->UpdateSampleRate(kSampleRateHz);
391
392 uint16_t seq_num = seq_num_offset;
393 uint32_t timestamp = 0x87654321;
394 nack->UpdateLastReceivedPacket(seq_num, timestamp);
395
396 // Packet lost more than NACK-list size limit.
397 uint16_t num_lost_packets = kNackThreshold + kNackListSize + 5;
398
399 std::unique_ptr<uint16_t[]> seq_num_lost(new uint16_t[num_lost_packets]);
400 for (int n = 0; n < num_lost_packets; ++n) {
401 seq_num_lost[n] = ++seq_num;
402 }
403
404 ++seq_num;
405 timestamp += (num_lost_packets + 1) * kTimestampIncrement;
406 nack->UpdateLastReceivedPacket(seq_num, timestamp);
407 size_t expected_size = num_lost_packets - kNackThreshold;
408
409 std::vector<uint16_t> nack_list = nack->GetNackList(kShortRoundTripTimeMs);
410 EXPECT_EQ(expected_size, nack_list.size());
411
412 nack->SetMaxNackListSize(kNackListSize);
413 expected_size = kNackListSize - kNackThreshold;
414 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
415 EXPECT_TRUE(IsNackListCorrect(
416 nack_list, &seq_num_lost[num_lost_packets - kNackListSize],
417 expected_size));
418
419 // NACK list does not change size but the content is changing. The oldest
420 // element is removed and one from late list is inserted.
421 size_t n;
422 for (n = 1; n <= static_cast<size_t>(kNackThreshold); ++n) {
423 ++seq_num;
424 timestamp += kTimestampIncrement;
425 nack->UpdateLastReceivedPacket(seq_num, timestamp);
426 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
427 EXPECT_TRUE(IsNackListCorrect(
428 nack_list, &seq_num_lost[num_lost_packets - kNackListSize + n],
429 expected_size));
430 }
431
432 // NACK list should shrink.
433 for (; n < kNackListSize; ++n) {
434 ++seq_num;
435 timestamp += kTimestampIncrement;
436 nack->UpdateLastReceivedPacket(seq_num, timestamp);
437 --expected_size;
438 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
439 EXPECT_TRUE(IsNackListCorrect(
440 nack_list, &seq_num_lost[num_lost_packets - kNackListSize + n],
441 expected_size));
442 }
443
444 // After this packet, NACK list should be empty.
445 ++seq_num;
446 timestamp += kTimestampIncrement;
447 nack->UpdateLastReceivedPacket(seq_num, timestamp);
448 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
449 EXPECT_TRUE(nack_list.empty());
450 }
451 }
452
TEST(NackTrackerTest,RoudTripTimeIsApplied)453 TEST(NackTrackerTest, RoudTripTimeIsApplied) {
454 const int kNackListSize = 200;
455 std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
456 nack->UpdateSampleRate(kSampleRateHz);
457 nack->SetMaxNackListSize(kNackListSize);
458
459 uint16_t seq_num = 0;
460 uint32_t timestamp = 0x87654321;
461 nack->UpdateLastReceivedPacket(seq_num, timestamp);
462
463 // Packet lost more than NACK-list size limit.
464 uint16_t kNumLostPackets = kNackThreshold + 5;
465
466 seq_num += (1 + kNumLostPackets);
467 timestamp += (1 + kNumLostPackets) * kTimestampIncrement;
468 nack->UpdateLastReceivedPacket(seq_num, timestamp);
469
470 // Expected time-to-play are:
471 // kPacketSizeMs - 10, 2*kPacketSizeMs - 10, 3*kPacketSizeMs - 10, ...
472 //
473 // sequence number: 1, 2, 3, 4, 5
474 // time-to-play: 20, 50, 80, 110, 140
475 //
476 std::vector<uint16_t> nack_list = nack->GetNackList(100);
477 ASSERT_EQ(2u, nack_list.size());
478 EXPECT_EQ(4, nack_list[0]);
479 EXPECT_EQ(5, nack_list[1]);
480 }
481
482 } // namespace webrtc
483