blob: e5c0c3bc4d0463e0a8907c58fc8b0b24556a6de9 [file] [log] [blame]
/*
* Copyright (c) 2013 The WebRTC project authors. All Rights Reserved.
*
* Use of this source code is governed by a BSD-style license
* that can be found in the LICENSE file in the root of the source
* tree. An additional intellectual property rights grant can be found
* in the file PATENTS. All contributing project authors may
* be found in the AUTHORS file in the root of the source tree.
*/
#include "webrtc/modules/audio_coding/neteq/nack_tracker.h"
#include <stdint.h>
#include <algorithm>
#include <memory>
#include "testing/gtest/include/gtest/gtest.h"
#include "webrtc/typedefs.h"
#include "webrtc/modules/audio_coding/include/audio_coding_module_typedefs.h"
namespace webrtc {
namespace {
const int kNackThreshold = 3;
const int kSampleRateHz = 16000;
const int kPacketSizeMs = 30;
const uint32_t kTimestampIncrement = 480; // 30 ms.
const int64_t kShortRoundTripTimeMs = 1;
bool IsNackListCorrect(const std::vector<uint16_t>& nack_list,
const uint16_t* lost_sequence_numbers,
size_t num_lost_packets) {
if (nack_list.size() != num_lost_packets)
return false;
if (num_lost_packets == 0)
return true;
for (size_t k = 0; k < nack_list.size(); ++k) {
int seq_num = nack_list[k];
bool seq_num_matched = false;
for (size_t n = 0; n < num_lost_packets; ++n) {
if (seq_num == lost_sequence_numbers[n]) {
seq_num_matched = true;
break;
}
}
if (!seq_num_matched)
return false;
}
return true;
}
} // namespace
TEST(NackTrackerTest, EmptyListWhenNoPacketLoss) {
std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
nack->UpdateSampleRate(kSampleRateHz);
int seq_num = 1;
uint32_t timestamp = 0;
std::vector<uint16_t> nack_list;
for (int n = 0; n < 100; n++) {
nack->UpdateLastReceivedPacket(seq_num, timestamp);
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
seq_num++;
timestamp += kTimestampIncrement;
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(nack_list.empty());
}
}
TEST(NackTrackerTest, NoNackIfReorderWithinNackThreshold) {
std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
nack->UpdateSampleRate(kSampleRateHz);
int seq_num = 1;
uint32_t timestamp = 0;
std::vector<uint16_t> nack_list;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(nack_list.empty());
int num_late_packets = kNackThreshold + 1;
// Push in reverse order
while (num_late_packets > 0) {
nack->UpdateLastReceivedPacket(
seq_num + num_late_packets,
timestamp + num_late_packets * kTimestampIncrement);
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(nack_list.empty());
num_late_packets--;
}
}
TEST(NackTrackerTest, LatePacketsMovedToNackThenNackListDoesNotChange) {
const uint16_t kSequenceNumberLostPackets[] = {2, 3, 4, 5, 6, 7, 8, 9};
static const int kNumAllLostPackets = sizeof(kSequenceNumberLostPackets) /
sizeof(kSequenceNumberLostPackets[0]);
for (int k = 0; k < 2; k++) { // Two iteration with/without wrap around.
std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
nack->UpdateSampleRate(kSampleRateHz);
uint16_t sequence_num_lost_packets[kNumAllLostPackets];
for (int n = 0; n < kNumAllLostPackets; n++) {
sequence_num_lost_packets[n] =
kSequenceNumberLostPackets[n] +
k * 65531; // Have wrap around in sequence numbers for |k == 1|.
}
uint16_t seq_num = sequence_num_lost_packets[0] - 1;
uint32_t timestamp = 0;
std::vector<uint16_t> nack_list;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(nack_list.empty());
seq_num = sequence_num_lost_packets[kNumAllLostPackets - 1] + 1;
timestamp += kTimestampIncrement * (kNumAllLostPackets + 1);
int num_lost_packets = std::max(0, kNumAllLostPackets - kNackThreshold);
for (int n = 0; n < kNackThreshold + 1; ++n) {
nack->UpdateLastReceivedPacket(seq_num, timestamp);
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(IsNackListCorrect(nack_list, sequence_num_lost_packets,
num_lost_packets));
seq_num++;
timestamp += kTimestampIncrement;
num_lost_packets++;
}
for (int n = 0; n < 100; ++n) {
nack->UpdateLastReceivedPacket(seq_num, timestamp);
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(IsNackListCorrect(nack_list, sequence_num_lost_packets,
kNumAllLostPackets));
seq_num++;
timestamp += kTimestampIncrement;
}
}
}
TEST(NackTrackerTest, ArrivedPacketsAreRemovedFromNackList) {
const uint16_t kSequenceNumberLostPackets[] = {2, 3, 4, 5, 6, 7, 8, 9};
static const int kNumAllLostPackets = sizeof(kSequenceNumberLostPackets) /
sizeof(kSequenceNumberLostPackets[0]);
for (int k = 0; k < 2; ++k) { // Two iteration with/without wrap around.
std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
nack->UpdateSampleRate(kSampleRateHz);
uint16_t sequence_num_lost_packets[kNumAllLostPackets];
for (int n = 0; n < kNumAllLostPackets; ++n) {
sequence_num_lost_packets[n] = kSequenceNumberLostPackets[n] +
k * 65531; // Wrap around for |k == 1|.
}
uint16_t seq_num = sequence_num_lost_packets[0] - 1;
uint32_t timestamp = 0;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
std::vector<uint16_t> nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(nack_list.empty());
size_t index_retransmitted_rtp = 0;
uint32_t timestamp_retransmitted_rtp = timestamp + kTimestampIncrement;
seq_num = sequence_num_lost_packets[kNumAllLostPackets - 1] + 1;
timestamp += kTimestampIncrement * (kNumAllLostPackets + 1);
size_t num_lost_packets = std::max(0, kNumAllLostPackets - kNackThreshold);
for (int n = 0; n < kNumAllLostPackets; ++n) {
// Number of lost packets does not change for the first
// |kNackThreshold + 1| packets, one is added to the list and one is
// removed. Thereafter, the list shrinks every iteration.
if (n >= kNackThreshold + 1)
num_lost_packets--;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(IsNackListCorrect(
nack_list, &sequence_num_lost_packets[index_retransmitted_rtp],
num_lost_packets));
seq_num++;
timestamp += kTimestampIncrement;
// Retransmission of a lost RTP.
nack->UpdateLastReceivedPacket(
sequence_num_lost_packets[index_retransmitted_rtp],
timestamp_retransmitted_rtp);
index_retransmitted_rtp++;
timestamp_retransmitted_rtp += kTimestampIncrement;
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(IsNackListCorrect(
nack_list, &sequence_num_lost_packets[index_retransmitted_rtp],
num_lost_packets - 1)); // One less lost packet in the list.
}
ASSERT_TRUE(nack_list.empty());
}
}
// Assess if estimation of timestamps and time-to-play is correct. Introduce all
// combinations that timestamps and sequence numbers might have wrap around.
TEST(NackTrackerTest, EstimateTimestampAndTimeToPlay) {
const uint16_t kLostPackets[] = {2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14, 15};
static const int kNumAllLostPackets =
sizeof(kLostPackets) / sizeof(kLostPackets[0]);
for (int k = 0; k < 4; ++k) {
std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
nack->UpdateSampleRate(kSampleRateHz);
// Sequence number wrap around if |k| is 2 or 3;
int seq_num_offset = (k < 2) ? 0 : 65531;
// Timestamp wrap around if |k| is 1 or 3.
uint32_t timestamp_offset =
(k & 0x1) ? static_cast<uint32_t>(0xffffffff) - 6 : 0;
uint32_t timestamp_lost_packets[kNumAllLostPackets];
uint16_t seq_num_lost_packets[kNumAllLostPackets];
for (int n = 0; n < kNumAllLostPackets; ++n) {
timestamp_lost_packets[n] =
timestamp_offset + kLostPackets[n] * kTimestampIncrement;
seq_num_lost_packets[n] = seq_num_offset + kLostPackets[n];
}
// We and to push two packets before lost burst starts.
uint16_t seq_num = seq_num_lost_packets[0] - 2;
uint32_t timestamp = timestamp_lost_packets[0] - 2 * kTimestampIncrement;
const uint16_t first_seq_num = seq_num;
const uint32_t first_timestamp = timestamp;
// Two consecutive packets to have a correct estimate of timestamp increase.
nack->UpdateLastReceivedPacket(seq_num, timestamp);
seq_num++;
timestamp += kTimestampIncrement;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
// A packet after the last one which is supposed to be lost.
seq_num = seq_num_lost_packets[kNumAllLostPackets - 1] + 1;
timestamp =
timestamp_lost_packets[kNumAllLostPackets - 1] + kTimestampIncrement;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
NackTracker::NackList nack_list = nack->GetNackList();
EXPECT_EQ(static_cast<size_t>(kNumAllLostPackets), nack_list.size());
// Pretend the first packet is decoded.
nack->UpdateLastDecodedPacket(first_seq_num, first_timestamp);
nack_list = nack->GetNackList();
NackTracker::NackList::iterator it = nack_list.begin();
while (it != nack_list.end()) {
seq_num = it->first - seq_num_offset;
int index = seq_num - kLostPackets[0];
EXPECT_EQ(timestamp_lost_packets[index], it->second.estimated_timestamp);
EXPECT_EQ((index + 2) * kPacketSizeMs, it->second.time_to_play_ms);
++it;
}
// Pretend 10 ms is passed, and we had pulled audio from NetEq, it still
// reports the same sequence number as decoded, time-to-play should be
// updated by 10 ms.
nack->UpdateLastDecodedPacket(first_seq_num, first_timestamp);
nack_list = nack->GetNackList();
it = nack_list.begin();
while (it != nack_list.end()) {
seq_num = it->first - seq_num_offset;
int index = seq_num - kLostPackets[0];
EXPECT_EQ((index + 2) * kPacketSizeMs - 10, it->second.time_to_play_ms);
++it;
}
}
}
TEST(NackTrackerTest,
MissingPacketsPriorToLastDecodedRtpShouldNotBeInNackList) {
for (int m = 0; m < 2; ++m) {
uint16_t seq_num_offset = (m == 0) ? 0 : 65531; // Wrap around if |m| is 1.
std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
nack->UpdateSampleRate(kSampleRateHz);
// Two consecutive packets to have a correct estimate of timestamp increase.
uint16_t seq_num = 0;
nack->UpdateLastReceivedPacket(seq_num_offset + seq_num,
seq_num * kTimestampIncrement);
seq_num++;
nack->UpdateLastReceivedPacket(seq_num_offset + seq_num,
seq_num * kTimestampIncrement);
// Skip 10 packets (larger than NACK threshold).
const int kNumLostPackets = 10;
seq_num += kNumLostPackets + 1;
nack->UpdateLastReceivedPacket(seq_num_offset + seq_num,
seq_num * kTimestampIncrement);
const size_t kExpectedListSize = kNumLostPackets - kNackThreshold;
std::vector<uint16_t> nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_EQ(kExpectedListSize, nack_list.size());
for (int k = 0; k < 2; ++k) {
// Decoding of the first and the second arrived packets.
for (int n = 0; n < kPacketSizeMs / 10; ++n) {
nack->UpdateLastDecodedPacket(seq_num_offset + k,
k * kTimestampIncrement);
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_EQ(kExpectedListSize, nack_list.size());
}
}
// Decoding of the last received packet.
nack->UpdateLastDecodedPacket(seq_num + seq_num_offset,
seq_num * kTimestampIncrement);
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(nack_list.empty());
// Make sure list of late packets is also empty. To check that, push few
// packets, if the late list is not empty its content will pop up in NACK
// list.
for (int n = 0; n < kNackThreshold + 10; ++n) {
seq_num++;
nack->UpdateLastReceivedPacket(seq_num_offset + seq_num,
seq_num * kTimestampIncrement);
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(nack_list.empty());
}
}
}
TEST(NackTrackerTest, Reset) {
std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
nack->UpdateSampleRate(kSampleRateHz);
// Two consecutive packets to have a correct estimate of timestamp increase.
uint16_t seq_num = 0;
nack->UpdateLastReceivedPacket(seq_num, seq_num * kTimestampIncrement);
seq_num++;
nack->UpdateLastReceivedPacket(seq_num, seq_num * kTimestampIncrement);
// Skip 10 packets (larger than NACK threshold).
const int kNumLostPackets = 10;
seq_num += kNumLostPackets + 1;
nack->UpdateLastReceivedPacket(seq_num, seq_num * kTimestampIncrement);
const size_t kExpectedListSize = kNumLostPackets - kNackThreshold;
std::vector<uint16_t> nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_EQ(kExpectedListSize, nack_list.size());
nack->Reset();
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(nack_list.empty());
}
TEST(NackTrackerTest, ListSizeAppliedFromBeginning) {
const size_t kNackListSize = 10;
for (int m = 0; m < 2; ++m) {
uint16_t seq_num_offset = (m == 0) ? 0 : 65525; // Wrap around if |m| is 1.
std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
nack->UpdateSampleRate(kSampleRateHz);
nack->SetMaxNackListSize(kNackListSize);
uint16_t seq_num = seq_num_offset;
uint32_t timestamp = 0x12345678;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
// Packet lost more than NACK-list size limit.
uint16_t num_lost_packets = kNackThreshold + kNackListSize + 5;
seq_num += num_lost_packets + 1;
timestamp += (num_lost_packets + 1) * kTimestampIncrement;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
std::vector<uint16_t> nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_EQ(kNackListSize - kNackThreshold, nack_list.size());
}
}
TEST(NackTrackerTest, ChangeOfListSizeAppliedAndOldElementsRemoved) {
const size_t kNackListSize = 10;
for (int m = 0; m < 2; ++m) {
uint16_t seq_num_offset = (m == 0) ? 0 : 65525; // Wrap around if |m| is 1.
std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
nack->UpdateSampleRate(kSampleRateHz);
uint16_t seq_num = seq_num_offset;
uint32_t timestamp = 0x87654321;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
// Packet lost more than NACK-list size limit.
uint16_t num_lost_packets = kNackThreshold + kNackListSize + 5;
std::unique_ptr<uint16_t[]> seq_num_lost(new uint16_t[num_lost_packets]);
for (int n = 0; n < num_lost_packets; ++n) {
seq_num_lost[n] = ++seq_num;
}
++seq_num;
timestamp += (num_lost_packets + 1) * kTimestampIncrement;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
size_t expected_size = num_lost_packets - kNackThreshold;
std::vector<uint16_t> nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_EQ(expected_size, nack_list.size());
nack->SetMaxNackListSize(kNackListSize);
expected_size = kNackListSize - kNackThreshold;
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(IsNackListCorrect(
nack_list, &seq_num_lost[num_lost_packets - kNackListSize],
expected_size));
// NACK list does not change size but the content is changing. The oldest
// element is removed and one from late list is inserted.
size_t n;
for (n = 1; n <= static_cast<size_t>(kNackThreshold); ++n) {
++seq_num;
timestamp += kTimestampIncrement;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(IsNackListCorrect(
nack_list, &seq_num_lost[num_lost_packets - kNackListSize + n],
expected_size));
}
// NACK list should shrink.
for (; n < kNackListSize; ++n) {
++seq_num;
timestamp += kTimestampIncrement;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
--expected_size;
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(IsNackListCorrect(
nack_list, &seq_num_lost[num_lost_packets - kNackListSize + n],
expected_size));
}
// After this packet, NACK list should be empty.
++seq_num;
timestamp += kTimestampIncrement;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
nack_list = nack->GetNackList(kShortRoundTripTimeMs);
EXPECT_TRUE(nack_list.empty());
}
}
TEST(NackTrackerTest, RoudTripTimeIsApplied) {
const int kNackListSize = 200;
std::unique_ptr<NackTracker> nack(NackTracker::Create(kNackThreshold));
nack->UpdateSampleRate(kSampleRateHz);
nack->SetMaxNackListSize(kNackListSize);
uint16_t seq_num = 0;
uint32_t timestamp = 0x87654321;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
// Packet lost more than NACK-list size limit.
uint16_t kNumLostPackets = kNackThreshold + 5;
seq_num += (1 + kNumLostPackets);
timestamp += (1 + kNumLostPackets) * kTimestampIncrement;
nack->UpdateLastReceivedPacket(seq_num, timestamp);
// Expected time-to-play are:
// kPacketSizeMs - 10, 2*kPacketSizeMs - 10, 3*kPacketSizeMs - 10, ...
//
// sequence number: 1, 2, 3, 4, 5
// time-to-play: 20, 50, 80, 110, 140
//
std::vector<uint16_t> nack_list = nack->GetNackList(100);
ASSERT_EQ(2u, nack_list.size());
EXPECT_EQ(4, nack_list[0]);
EXPECT_EQ(5, nack_list[1]);
}
} // namespace webrtc