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 <stdint.h>
14
15 #include <algorithm>
16
17 #include "testing/gtest/include/gtest/gtest.h"
18 #include "webrtc/base/scoped_ptr.h"
19 #include "webrtc/typedefs.h"
20 #include "webrtc/modules/audio_coding/include/audio_coding_module_typedefs.h"
21
22 namespace webrtc {
23 namespace {
24
25 const int kNackThreshold = 3;
26 const int kSampleRateHz = 16000;
27 const int kPacketSizeMs = 30;
28 const uint32_t kTimestampIncrement = 480; // 30 ms.
29 const int64_t kShortRoundTripTimeMs = 1;
30
IsNackListCorrect(const std::vector<uint16_t> & nack_list,const uint16_t * lost_sequence_numbers,size_t num_lost_packets)31 bool IsNackListCorrect(const std::vector<uint16_t>& nack_list,
32 const uint16_t* lost_sequence_numbers,
33 size_t num_lost_packets) {
34 if (nack_list.size() != num_lost_packets)
35 return false;
36
37 if (num_lost_packets == 0)
38 return true;
39
40 for (size_t k = 0; k < nack_list.size(); ++k) {
41 int seq_num = nack_list[k];
42 bool seq_num_matched = false;
43 for (size_t n = 0; n < num_lost_packets; ++n) {
44 if (seq_num == lost_sequence_numbers[n]) {
45 seq_num_matched = true;
46 break;
47 }
48 }
49 if (!seq_num_matched)
50 return false;
51 }
52 return true;
53 }
54
55 } // namespace
56
TEST(NackTest,EmptyListWhenNoPacketLoss)57 TEST(NackTest, EmptyListWhenNoPacketLoss) {
58 rtc::scoped_ptr<Nack> nack(Nack::Create(kNackThreshold));
59 nack->UpdateSampleRate(kSampleRateHz);
60
61 int seq_num = 1;
62 uint32_t timestamp = 0;
63
64 std::vector<uint16_t> nack_list;
65 for (int n = 0; n < 100; n++) {
66 nack->UpdateLastReceivedPacket(seq_num, timestamp);
67 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
68 seq_num++;
69 timestamp += kTimestampIncrement;
70 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
71 EXPECT_TRUE(nack_list.empty());
72 }
73 }
74
TEST(NackTest,NoNackIfReorderWithinNackThreshold)75 TEST(NackTest, NoNackIfReorderWithinNackThreshold) {
76 rtc::scoped_ptr<Nack> nack(Nack::Create(kNackThreshold));
77 nack->UpdateSampleRate(kSampleRateHz);
78
79 int seq_num = 1;
80 uint32_t timestamp = 0;
81 std::vector<uint16_t> nack_list;
82
83 nack->UpdateLastReceivedPacket(seq_num, timestamp);
84 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
85 EXPECT_TRUE(nack_list.empty());
86 int num_late_packets = kNackThreshold + 1;
87
88 // Push in reverse order
89 while (num_late_packets > 0) {
90 nack->UpdateLastReceivedPacket(
91 seq_num + num_late_packets,
92 timestamp + num_late_packets * kTimestampIncrement);
93 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
94 EXPECT_TRUE(nack_list.empty());
95 num_late_packets--;
96 }
97 }
98
TEST(NackTest,LatePacketsMovedToNackThenNackListDoesNotChange)99 TEST(NackTest, LatePacketsMovedToNackThenNackListDoesNotChange) {
100 const uint16_t kSequenceNumberLostPackets[] = {2, 3, 4, 5, 6, 7, 8, 9};
101 static const int kNumAllLostPackets = sizeof(kSequenceNumberLostPackets) /
102 sizeof(kSequenceNumberLostPackets[0]);
103
104 for (int k = 0; k < 2; k++) { // Two iteration with/without wrap around.
105 rtc::scoped_ptr<Nack> nack(Nack::Create(kNackThreshold));
106 nack->UpdateSampleRate(kSampleRateHz);
107
108 uint16_t sequence_num_lost_packets[kNumAllLostPackets];
109 for (int n = 0; n < kNumAllLostPackets; n++) {
110 sequence_num_lost_packets[n] =
111 kSequenceNumberLostPackets[n] +
112 k * 65531; // Have wrap around in sequence numbers for |k == 1|.
113 }
114 uint16_t seq_num = sequence_num_lost_packets[0] - 1;
115
116 uint32_t timestamp = 0;
117 std::vector<uint16_t> nack_list;
118
119 nack->UpdateLastReceivedPacket(seq_num, timestamp);
120 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
121 EXPECT_TRUE(nack_list.empty());
122
123 seq_num = sequence_num_lost_packets[kNumAllLostPackets - 1] + 1;
124 timestamp += kTimestampIncrement * (kNumAllLostPackets + 1);
125 int num_lost_packets = std::max(0, kNumAllLostPackets - kNackThreshold);
126
127 for (int n = 0; n < kNackThreshold + 1; ++n) {
128 nack->UpdateLastReceivedPacket(seq_num, timestamp);
129 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
130 EXPECT_TRUE(IsNackListCorrect(nack_list, sequence_num_lost_packets,
131 num_lost_packets));
132 seq_num++;
133 timestamp += kTimestampIncrement;
134 num_lost_packets++;
135 }
136
137 for (int n = 0; n < 100; ++n) {
138 nack->UpdateLastReceivedPacket(seq_num, timestamp);
139 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
140 EXPECT_TRUE(IsNackListCorrect(nack_list, sequence_num_lost_packets,
141 kNumAllLostPackets));
142 seq_num++;
143 timestamp += kTimestampIncrement;
144 }
145 }
146 }
147
TEST(NackTest,ArrivedPacketsAreRemovedFromNackList)148 TEST(NackTest, ArrivedPacketsAreRemovedFromNackList) {
149 const uint16_t kSequenceNumberLostPackets[] = {2, 3, 4, 5, 6, 7, 8, 9};
150 static const int kNumAllLostPackets = sizeof(kSequenceNumberLostPackets) /
151 sizeof(kSequenceNumberLostPackets[0]);
152
153 for (int k = 0; k < 2; ++k) { // Two iteration with/without wrap around.
154 rtc::scoped_ptr<Nack> nack(Nack::Create(kNackThreshold));
155 nack->UpdateSampleRate(kSampleRateHz);
156
157 uint16_t sequence_num_lost_packets[kNumAllLostPackets];
158 for (int n = 0; n < kNumAllLostPackets; ++n) {
159 sequence_num_lost_packets[n] = kSequenceNumberLostPackets[n] +
160 k * 65531; // Wrap around for |k == 1|.
161 }
162
163 uint16_t seq_num = sequence_num_lost_packets[0] - 1;
164 uint32_t timestamp = 0;
165
166 nack->UpdateLastReceivedPacket(seq_num, timestamp);
167 std::vector<uint16_t> nack_list = nack->GetNackList(kShortRoundTripTimeMs);
168 EXPECT_TRUE(nack_list.empty());
169
170 size_t index_retransmitted_rtp = 0;
171 uint32_t timestamp_retransmitted_rtp = timestamp + kTimestampIncrement;
172
173 seq_num = sequence_num_lost_packets[kNumAllLostPackets - 1] + 1;
174 timestamp += kTimestampIncrement * (kNumAllLostPackets + 1);
175 size_t num_lost_packets = std::max(0, kNumAllLostPackets - kNackThreshold);
176 for (int n = 0; n < kNumAllLostPackets; ++n) {
177 // Number of lost packets does not change for the first
178 // |kNackThreshold + 1| packets, one is added to the list and one is
179 // removed. Thereafter, the list shrinks every iteration.
180 if (n >= kNackThreshold + 1)
181 num_lost_packets--;
182
183 nack->UpdateLastReceivedPacket(seq_num, timestamp);
184 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
185 EXPECT_TRUE(IsNackListCorrect(
186 nack_list, &sequence_num_lost_packets[index_retransmitted_rtp],
187 num_lost_packets));
188 seq_num++;
189 timestamp += kTimestampIncrement;
190
191 // Retransmission of a lost RTP.
192 nack->UpdateLastReceivedPacket(
193 sequence_num_lost_packets[index_retransmitted_rtp],
194 timestamp_retransmitted_rtp);
195 index_retransmitted_rtp++;
196 timestamp_retransmitted_rtp += kTimestampIncrement;
197
198 nack_list = nack->GetNackList(kShortRoundTripTimeMs);
199 EXPECT_TRUE(IsNackListCorrect(
200 nack_list, &sequence_num_lost_packets[index_retransmitted_rtp],
201 num_lost_packets - 1)); // One less lost packet in the list.
202 }
203 ASSERT_TRUE(nack_list.empty());
204 }
205 }
206
207 // Assess if estimation of timestamps and time-to-play is correct. Introduce all
208 // combinations that timestamps and sequence numbers might have wrap around.
TEST(NackTest,EstimateTimestampAndTimeToPlay)209 TEST(NackTest, EstimateTimestampAndTimeToPlay) {
210 const uint16_t kLostPackets[] = {2, 3, 4, 5, 6, 7, 8,
211 9, 10, 11, 12, 13, 14, 15};
212 static const int kNumAllLostPackets =
213 sizeof(kLostPackets) / sizeof(kLostPackets[0]);
214
215 for (int k = 0; k < 4; ++k) {
216 rtc::scoped_ptr<Nack> nack(Nack::Create(kNackThreshold));
217 nack->UpdateSampleRate(kSampleRateHz);
218
219 // Sequence number wrap around if |k| is 2 or 3;
220 int seq_num_offset = (k < 2) ? 0 : 65531;
221
222 // Timestamp wrap around if |k| is 1 or 3.
223 uint32_t timestamp_offset =
224 (k & 0x1) ? static_cast<uint32_t>(0xffffffff) - 6 : 0;
225
226 uint32_t timestamp_lost_packets[kNumAllLostPackets];
227 uint16_t seq_num_lost_packets[kNumAllLostPackets];
228 for (int n = 0; n < kNumAllLostPackets; ++n) {
229 timestamp_lost_packets[n] =
230 timestamp_offset + kLostPackets[n] * kTimestampIncrement;
231 seq_num_lost_packets[n] = seq_num_offset + kLostPackets[n];
232 }
233
234 // We and to push two packets before lost burst starts.
235 uint16_t seq_num = seq_num_lost_packets[0] - 2;
236 uint32_t timestamp = timestamp_lost_packets[0] - 2 * kTimestampIncrement;
237
238 const uint16_t first_seq_num = seq_num;
239 const uint32_t first_timestamp = timestamp;
240
241 // Two consecutive packets to have a correct estimate of timestamp increase.
242 nack->UpdateLastReceivedPacket(seq_num, timestamp);
243 seq_num++;
244 timestamp += kTimestampIncrement;
245 nack->UpdateLastReceivedPacket(seq_num, timestamp);
246
247 // A packet after the last one which is supposed to be lost.
248 seq_num = seq_num_lost_packets[kNumAllLostPackets - 1] + 1;
249 timestamp =
250 timestamp_lost_packets[kNumAllLostPackets - 1] + kTimestampIncrement;
251 nack->UpdateLastReceivedPacket(seq_num, timestamp);
252
253 Nack::NackList nack_list = nack->GetNackList();
254 EXPECT_EQ(static_cast<size_t>(kNumAllLostPackets), nack_list.size());
255
256 // Pretend the first packet is decoded.
257 nack->UpdateLastDecodedPacket(first_seq_num, first_timestamp);
258 nack_list = nack->GetNackList();
259
260 Nack::NackList::iterator it = nack_list.begin();
261 while (it != nack_list.end()) {
262 seq_num = it->first - seq_num_offset;
263 int index = seq_num - kLostPackets[0];
264 EXPECT_EQ(timestamp_lost_packets[index], it->second.estimated_timestamp);
265 EXPECT_EQ((index + 2) * kPacketSizeMs, it->second.time_to_play_ms);
266 ++it;
267 }
268
269 // Pretend 10 ms is passed, and we had pulled audio from NetEq, it still
270 // reports the same sequence number as decoded, time-to-play should be
271 // updated by 10 ms.
272 nack->UpdateLastDecodedPacket(first_seq_num, first_timestamp);
273 nack_list = nack->GetNackList();
274 it = nack_list.begin();
275 while (it != nack_list.end()) {
276 seq_num = it->first - seq_num_offset;
277 int index = seq_num - kLostPackets[0];
278 EXPECT_EQ((index + 2) * kPacketSizeMs - 10, it->second.time_to_play_ms);
279 ++it;
280 }
281 }
282 }
283
TEST(NackTest,MissingPacketsPriorToLastDecodedRtpShouldNotBeInNackList)284 TEST(NackTest, 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 rtc::scoped_ptr<Nack> nack(Nack::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(NackTest,Reset)337 TEST(NackTest, Reset) {
338 rtc::scoped_ptr<Nack> nack(Nack::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(NackTest,ListSizeAppliedFromBeginning)361 TEST(NackTest, 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 rtc::scoped_ptr<Nack> nack(Nack::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(NackTest,ChangeOfListSizeAppliedAndOldElementsRemoved)385 TEST(NackTest, 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 rtc::scoped_ptr<Nack> nack(Nack::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 rtc::scoped_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(NackTest,RoudTripTimeIsApplied)453 TEST(NackTest, RoudTripTimeIsApplied) {
454 const int kNackListSize = 200;
455 rtc::scoped_ptr<Nack> nack(Nack::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