Fix problem with late packets in NetEq

Since r7255, it could happen that an old packet would block the decoding
process until enough packet was received for the buffer to flush. This
CL fixes that by:
- Partially reverting r7255;
- Remove recent old packets before taking a decision for GetAudio;
- Remove all old packets after a packet has been extracted for decoding;
- Adding tests for reordered packets.

BUG=chrome:423985
R=tina.legrand@webrtc.org

Review URL: https://webrtc-codereview.appspot.com/25079004

git-svn-id: http://webrtc.googlecode.com/svn/trunk/webrtc@7612 4adac7df-926f-26a2-2b94-8c16560cd09d

8 files changed, 207 insertions, 20 deletions

diff --git a/modules/audio_coding/neteq/decision_logic_normal.cc b/modules/audio_coding/neteq/decision_logic_normal.cc
index 9e422041..f2382845 100644
--- a/modules/audio_coding/neteq/decision_logic_normal.cc
+++ b/modules/audio_coding/neteq/decision_logic_normal.cc
@@ -67,19 +67,19 @@ Operations DecisionLogicNormal::GetDecisionSpecialized(
     return kNormal;
   }
 
+  const uint32_t five_seconds_samples = 5 * 8000 * fs_mult_;
   // Check if the required packet is available.
   if (target_timestamp == available_timestamp) {
     return ExpectedPacketAvailable(prev_mode, play_dtmf);
-  } else if (IsNewerTimestamp(available_timestamp, target_timestamp)) {
+  } else if (!PacketBuffer::IsObsoleteTimestamp(
+                 available_timestamp, target_timestamp, five_seconds_samples)) {
     return FuturePacketAvailable(sync_buffer, expand, decoder_frame_length,
                                  prev_mode, target_timestamp,
                                  available_timestamp, play_dtmf);
   } else {
     // This implies that available_timestamp < target_timestamp, which can
-    // happen when a new stream or codec is received. Do Expand instead, and
-    // wait for a newer packet to arrive, or for the buffer to flush (resulting
-    // in a master reset).
-    return kExpand;
+    // happen when a new stream or codec is received. Signal for a reset.
+    return kUndefined;
   }
 }
 
diff --git a/modules/audio_coding/neteq/mock/mock_packet_buffer.h b/modules/audio_coding/neteq/mock/mock_packet_buffer.h
index 74eea6f0..0eb7edc9 100644
--- a/modules/audio_coding/neteq/mock/mock_packet_buffer.h
+++ b/modules/audio_coding/neteq/mock/mock_packet_buffer.h
@@ -44,7 +44,9 @@ class MockPacketBuffer : public PacketBuffer {
       Packet*(int* discard_count));
   MOCK_METHOD0(DiscardNextPacket,
       int());
-  MOCK_METHOD1(DiscardOldPackets,
+  MOCK_METHOD2(DiscardOldPackets,
+      int(uint32_t timestamp_limit, uint32_t horizon_samples));
+  MOCK_METHOD1(DiscardAllOldPackets,
       int(uint32_t timestamp_limit));
   MOCK_CONST_METHOD0(NumPacketsInBuffer,
       int());
diff --git a/modules/audio_coding/neteq/neteq_external_decoder_unittest.cc b/modules/audio_coding/neteq/neteq_external_decoder_unittest.cc
index 2e07b490..d41bc543 100644
--- a/modules/audio_coding/neteq/neteq_external_decoder_unittest.cc
+++ b/modules/audio_coding/neteq/neteq_external_decoder_unittest.cc
@@ -308,6 +308,8 @@ class LargeTimestampJumpTest : public NetEqExternalDecoderTest {
       case kExpandPhase: {
         if (output_type == kOutputPLCtoCNG) {
           test_state_ = kFadedExpandPhase;
+        } else if (output_type == kOutputNormal) {
+          test_state_ = kRecovered;
         }
         break;
       }
@@ -337,9 +339,14 @@ class LargeTimestampJumpTest : public NetEqExternalDecoderTest {
   }
 
   int NumExpectedDecodeCalls(int num_loops) const OVERRIDE {
-    // Some packets won't be decoded because of the buffer being flushed after
-    // the timestamp jump.
-    return num_loops - (config_.max_packets_in_buffer + 1);
+    // Some packets at the end of the stream won't be decoded. When the jump in
+    // timestamp happens, NetEq will do Expand during one GetAudio call. In the
+    // next call it will decode the packet after the jump, but the net result is
+    // that the delay increased by 1 packet. In another call, a Pre-emptive
+    // Expand operation is performed, leading to delay increase by 1 packet. In
+    // total, the test will end with a 2-packet delay, which results in the 2
+    // last packets not being decoded.
+    return num_loops - 2;
   }
 
   TestStates test_state_;
diff --git a/modules/audio_coding/neteq/neteq_impl.cc b/modules/audio_coding/neteq/neteq_impl.cc
index 44faa22a..f3d1a4f6 100644
--- a/modules/audio_coding/neteq/neteq_impl.cc
+++ b/modules/audio_coding/neteq/neteq_impl.cc
@@ -868,6 +868,10 @@ int NetEqImpl::GetDecision(Operations* operation,
 
   assert(sync_buffer_.get());
   uint32_t end_timestamp = sync_buffer_->end_timestamp();
+  if (!new_codec_) {
+    const uint32_t five_seconds_samples = 5 * fs_hz_;
+    packet_buffer_->DiscardOldPackets(end_timestamp, five_seconds_samples);
+  }
   const RTPHeader* header = packet_buffer_->NextRtpHeader();
 
   if (decision_logic_->CngRfc3389On() || last_mode_ == kModeRfc3389Cng) {
@@ -884,7 +888,7 @@ int NetEqImpl::GetDecision(Operations* operation,
       }
       // Check buffer again.
       if (!new_codec_) {
-        packet_buffer_->DiscardOldPackets(end_timestamp);
+        packet_buffer_->DiscardOldPackets(end_timestamp, 5 * fs_hz_);
       }
       header = packet_buffer_->NextRtpHeader();
     }
@@ -1823,7 +1827,7 @@ int NetEqImpl::ExtractPackets(int required_samples, PacketList* packet_list) {
     // we could end up in the situation where we never decode anything, since
     // all incoming packets are considered too old but the buffer will also
     // never be flooded and flushed.
-    packet_buffer_->DiscardOldPackets(timestamp_);
+    packet_buffer_->DiscardAllOldPackets(timestamp_);
   }
 
   return extracted_samples;
diff --git a/modules/audio_coding/neteq/neteq_impl_unittest.cc b/modules/audio_coding/neteq/neteq_impl_unittest.cc
index b3bd69ba..8047fe20 100644
--- a/modules/audio_coding/neteq/neteq_impl_unittest.cc
+++ b/modules/audio_coding/neteq/neteq_impl_unittest.cc
@@ -32,9 +32,11 @@ using ::testing::Return;
 using ::testing::ReturnNull;
 using ::testing::_;
 using ::testing::SetArgPointee;
+using ::testing::SetArrayArgument;
 using ::testing::InSequence;
 using ::testing::Invoke;
 using ::testing::WithArg;
+using ::testing::Pointee;
 
 namespace webrtc {
 
@@ -494,4 +496,95 @@ TEST_F(NetEqImplTest, VerifyTimestampPropagation) {
             static_cast<int>(sync_buffer->FutureLength()));
 }
 
+TEST_F(NetEqImplTest, ReorderedPacket) {
+  UseNoMocks();
+  CreateInstance();
+
+  const uint8_t kPayloadType = 17;   // Just an arbitrary number.
+  const uint32_t kReceiveTime = 17;  // Value doesn't matter for this test.
+  const int kSampleRateHz = 8000;
+  const int kPayloadLengthSamples = 10 * kSampleRateHz / 1000;  // 10 ms.
+  const size_t kPayloadLengthBytes = kPayloadLengthSamples;
+  uint8_t payload[kPayloadLengthBytes] = {0};
+  WebRtcRTPHeader rtp_header;
+  rtp_header.header.payloadType = kPayloadType;
+  rtp_header.header.sequenceNumber = 0x1234;
+  rtp_header.header.timestamp = 0x12345678;
+  rtp_header.header.ssrc = 0x87654321;
+
+  // Create a mock decoder object.
+  MockAudioDecoder mock_decoder;
+  EXPECT_CALL(mock_decoder, Init()).WillRepeatedly(Return(0));
+  EXPECT_CALL(mock_decoder, IncomingPacket(_, kPayloadLengthBytes, _, _, _))
+      .WillRepeatedly(Return(0));
+  int16_t dummy_output[kPayloadLengthSamples] = {0};
+  // The below expectation will make the mock decoder write
+  // |kPayloadLengthSamples| zeros to the output array, and mark it as speech.
+  EXPECT_CALL(mock_decoder, Decode(Pointee(0), kPayloadLengthBytes, _, _))
+      .WillOnce(DoAll(SetArrayArgument<2>(dummy_output,
+                                          dummy_output + kPayloadLengthSamples),
+                      SetArgPointee<3>(AudioDecoder::kSpeech),
+                      Return(kPayloadLengthSamples)));
+  EXPECT_EQ(NetEq::kOK,
+            neteq_->RegisterExternalDecoder(
+                &mock_decoder, kDecoderPCM16B, kPayloadType));
+
+  // Insert one packet.
+  EXPECT_EQ(NetEq::kOK,
+            neteq_->InsertPacket(
+                rtp_header, payload, kPayloadLengthBytes, kReceiveTime));
+
+  // Pull audio once.
+  const int kMaxOutputSize = 10 * kSampleRateHz / 1000;
+  int16_t output[kMaxOutputSize];
+  int samples_per_channel;
+  int num_channels;
+  NetEqOutputType type;
+  EXPECT_EQ(
+      NetEq::kOK,
+      neteq_->GetAudio(
+          kMaxOutputSize, output, &samples_per_channel, &num_channels, &type));
+  ASSERT_EQ(kMaxOutputSize, samples_per_channel);
+  EXPECT_EQ(1, num_channels);
+  EXPECT_EQ(kOutputNormal, type);
+
+  // Insert two more packets. The first one is out of order, and is already too
+  // old, the second one is the expected next packet.
+  rtp_header.header.sequenceNumber -= 1;
+  rtp_header.header.timestamp -= kPayloadLengthSamples;
+  payload[0] = 1;
+  EXPECT_EQ(NetEq::kOK,
+            neteq_->InsertPacket(
+                rtp_header, payload, kPayloadLengthBytes, kReceiveTime));
+  rtp_header.header.sequenceNumber += 2;
+  rtp_header.header.timestamp += 2 * kPayloadLengthSamples;
+  payload[0] = 2;
+  EXPECT_EQ(NetEq::kOK,
+            neteq_->InsertPacket(
+                rtp_header, payload, kPayloadLengthBytes, kReceiveTime));
+
+  // Expect only the second packet to be decoded (the one with "2" as the first
+  // payload byte).
+  EXPECT_CALL(mock_decoder, Decode(Pointee(2), kPayloadLengthBytes, _, _))
+      .WillOnce(DoAll(SetArrayArgument<2>(dummy_output,
+                                          dummy_output + kPayloadLengthSamples),
+                      SetArgPointee<3>(AudioDecoder::kSpeech),
+                      Return(kPayloadLengthSamples)));
+
+  // Pull audio once.
+  EXPECT_EQ(
+      NetEq::kOK,
+      neteq_->GetAudio(
+          kMaxOutputSize, output, &samples_per_channel, &num_channels, &type));
+  ASSERT_EQ(kMaxOutputSize, samples_per_channel);
+  EXPECT_EQ(1, num_channels);
+  EXPECT_EQ(kOutputNormal, type);
+
+  // Now check the packet buffer, and make sure it is empty, since the
+  // out-of-order packet should have been discarded.
+  EXPECT_TRUE(packet_buffer_->Empty());
+
+  EXPECT_CALL(mock_decoder, Die());
+}
+
 }  // namespace webrtc
diff --git a/modules/audio_coding/neteq/packet_buffer.cc b/modules/audio_coding/neteq/packet_buffer.cc
index 4c484185..816713d8 100644
--- a/modules/audio_coding/neteq/packet_buffer.cc
+++ b/modules/audio_coding/neteq/packet_buffer.cc
@@ -216,12 +216,12 @@ int PacketBuffer::DiscardNextPacket() {
   return kOK;
 }
 
-int PacketBuffer::DiscardOldPackets(uint32_t timestamp_limit) {
-  while (!Empty() &&
-      timestamp_limit != buffer_.front()->header.timestamp &&
-      static_cast<uint32_t>(timestamp_limit
-                            - buffer_.front()->header.timestamp) <
-                            0xFFFFFFFF / 2) {
+int PacketBuffer::DiscardOldPackets(uint32_t timestamp_limit,
+                                    uint32_t horizon_samples) {
+  while (!Empty() && timestamp_limit != buffer_.front()->header.timestamp &&
+         IsObsoleteTimestamp(buffer_.front()->header.timestamp,
+                             timestamp_limit,
+                             horizon_samples)) {
     if (DiscardNextPacket() != kOK) {
       assert(false);  // Must be ok by design.
     }
diff --git a/modules/audio_coding/neteq/packet_buffer.h b/modules/audio_coding/neteq/packet_buffer.h
index 76c4ddd1..b9a16189 100644
--- a/modules/audio_coding/neteq/packet_buffer.h
+++ b/modules/audio_coding/neteq/packet_buffer.h
@@ -95,9 +95,19 @@ class PacketBuffer {
   // PacketBuffer::kOK otherwise.
   virtual int DiscardNextPacket();
 
-  // Discards all packets that are (strictly) older than |timestamp_limit|.
+  // Discards all packets that are (strictly) older than timestamp_limit,
+  // but newer than timestamp_limit - horizon_samples. Setting horizon_samples
+  // to zero implies that the horizon is set to half the timestamp range. That
+  // is, if a packet is more than 2^31 timestamps into the future compared with
+  // timestamp_limit (including wrap-around), it is considered old.
   // Returns number of packets discarded.
-  virtual int DiscardOldPackets(uint32_t timestamp_limit);
+  virtual int DiscardOldPackets(uint32_t timestamp_limit,
+                                uint32_t horizon_samples);
+
+  // Discards all packets that are (strictly) older than timestamp_limit.
+  virtual int DiscardAllOldPackets(uint32_t timestamp_limit) {
+    return DiscardOldPackets(timestamp_limit, 0);
+  }
 
   // Returns the number of packets in the buffer, including duplicates and
   // redundant packets.
@@ -125,6 +135,20 @@ class PacketBuffer {
   // in |packet_list|.
   static void DeleteAllPackets(PacketList* packet_list);
 
+  // Static method returning true if |timestamp| is older than |timestamp_limit|
+  // but less than |horizon_samples| behind |timestamp_limit|. For instance,
+  // with timestamp_limit = 100 and horizon_samples = 10, a timestamp in the
+  // range (90, 100) is considered obsolete, and will yield true.
+  // Setting |horizon_samples| to 0 is the same as setting it to 2^31, i.e.,
+  // half the 32-bit timestamp range.
+  static bool IsObsoleteTimestamp(uint32_t timestamp,
+                                  uint32_t timestamp_limit,
+                                  uint32_t horizon_samples) {
+    return IsNewerTimestamp(timestamp_limit, timestamp) &&
+           (horizon_samples == 0 ||
+            IsNewerTimestamp(timestamp, timestamp_limit - horizon_samples));
+  }
+
  private:
   size_t max_number_of_packets_;
   PacketList buffer_;
diff --git a/modules/audio_coding/neteq/packet_buffer_unittest.cc b/modules/audio_coding/neteq/packet_buffer_unittest.cc
index 478328cb..dc8b68c3 100644
--- a/modules/audio_coding/neteq/packet_buffer_unittest.cc
+++ b/modules/audio_coding/neteq/packet_buffer_unittest.cc
@@ -391,7 +391,7 @@ TEST(PacketBuffer, Failures) {
   EXPECT_EQ(NULL, buffer->NextRtpHeader());
   EXPECT_EQ(NULL, buffer->GetNextPacket(NULL));
   EXPECT_EQ(PacketBuffer::kBufferEmpty, buffer->DiscardNextPacket());
-  EXPECT_EQ(0, buffer->DiscardOldPackets(0));  // 0 packets discarded.
+  EXPECT_EQ(0, buffer->DiscardAllOldPackets(0));  // 0 packets discarded.
 
   // Insert one packet to make the buffer non-empty.
   packet = gen.NextPacket(payload_len);
@@ -513,4 +513,61 @@ TEST(PacketBuffer, DeleteAllPackets) {
   EXPECT_FALSE(PacketBuffer::DeleteFirstPacket(&list));
 }
 
+namespace {
+void TestIsObsoleteTimestamp(uint32_t limit_timestamp) {
+  // Check with zero horizon, which implies that the horizon is at 2^31, i.e.,
+  // half the timestamp range.
+  static const uint32_t kZeroHorizon = 0;
+  static const uint32_t k2Pow31Minus1 = 0x7FFFFFFF;
+  // Timestamp on the limit is not old.
+  EXPECT_FALSE(PacketBuffer::IsObsoleteTimestamp(
+      limit_timestamp, limit_timestamp, kZeroHorizon));
+  // 1 sample behind is old.
+  EXPECT_TRUE(PacketBuffer::IsObsoleteTimestamp(
+      limit_timestamp - 1, limit_timestamp, kZeroHorizon));
+  // 2^31 - 1 samples behind is old.
+  EXPECT_TRUE(PacketBuffer::IsObsoleteTimestamp(
+      limit_timestamp - k2Pow31Minus1, limit_timestamp, kZeroHorizon));
+  // 1 sample ahead is not old.
+  EXPECT_FALSE(PacketBuffer::IsObsoleteTimestamp(
+      limit_timestamp + 1, limit_timestamp, kZeroHorizon));
+  // 2^31 samples ahead is not old.
+  EXPECT_FALSE(PacketBuffer::IsObsoleteTimestamp(
+      limit_timestamp + (1 << 31), limit_timestamp, kZeroHorizon));
+
+  // Fixed horizon at 10 samples.
+  static const uint32_t kHorizon = 10;
+  // Timestamp on the limit is not old.
+  EXPECT_FALSE(PacketBuffer::IsObsoleteTimestamp(
+      limit_timestamp, limit_timestamp, kHorizon));
+  // 1 sample behind is old.
+  EXPECT_TRUE(PacketBuffer::IsObsoleteTimestamp(
+      limit_timestamp - 1, limit_timestamp, kHorizon));
+  // 9 samples behind is old.
+  EXPECT_TRUE(PacketBuffer::IsObsoleteTimestamp(
+      limit_timestamp - 9, limit_timestamp, kHorizon));
+  // 10 samples behind is not old.
+  EXPECT_FALSE(PacketBuffer::IsObsoleteTimestamp(
+      limit_timestamp - 10, limit_timestamp, kHorizon));
+  // 2^31 - 1 samples behind is not old.
+  EXPECT_FALSE(PacketBuffer::IsObsoleteTimestamp(
+      limit_timestamp - k2Pow31Minus1, limit_timestamp, kHorizon));
+  // 1 sample ahead is not old.
+  EXPECT_FALSE(PacketBuffer::IsObsoleteTimestamp(
+      limit_timestamp + 1, limit_timestamp, kHorizon));
+  // 2^31 samples ahead is not old.
+  EXPECT_FALSE(PacketBuffer::IsObsoleteTimestamp(
+      limit_timestamp + (1 << 31), limit_timestamp, kHorizon));
+}
+}  // namespace
+
+// Test the IsObsoleteTimestamp method with different limit timestamps.
+TEST(PacketBuffer, IsObsoleteTimestamp) {
+  TestIsObsoleteTimestamp(0);
+  TestIsObsoleteTimestamp(1);
+  TestIsObsoleteTimestamp(0xFFFFFFFF);  // -1 in uint32_t.
+  TestIsObsoleteTimestamp(0x80000000);  // 2^31.
+  TestIsObsoleteTimestamp(0x80000001);  // 2^31 + 1.
+  TestIsObsoleteTimestamp(0x7FFFFFFF);  // 2^31 - 1.
+}
 }  // namespace webrtc