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 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 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 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 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 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. 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 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 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 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 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 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
