src/third_party/webrtc/modules/audio_coding/main/acm2/nack_unittest.cc

   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