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