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