Add TransportFeedbackPacketLossTracker.

webrtc/modules/remote_bitrate_estimator/transport_feedback_packet_loss_tracker.cc

Index: webrtc/modules/remote_bitrate_estimator/transport_feedback_packet_loss_tracker.cc
diff --git a/webrtc/modules/remote_bitrate_estimator/transport_feedback_packet_loss_tracker.cc b/webrtc/modules/remote_bitrate_estimator/transport_feedback_packet_loss_tracker.cc
new file mode 100644
index 0000000000000000000000000000000000000000..494b6837a780f7ce786d5248d9466042ed026ccb
--- /dev/null
+++ b/webrtc/modules/remote_bitrate_estimator/transport_feedback_packet_loss_tracker.cc
@@ -0,0 +1,258 @@
+/*
+ *  Copyright (c) 2016 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/remote_bitrate_estimator/transport_feedback_packet_loss_tracker.h"
+
+#include <limits>
+#include <utility>
+
+#include "webrtc/base/checks.h"
+#include "webrtc/base/mod_ops.h"
+#include "webrtc/modules/rtp_rtcp/source/rtcp_packet/transport_feedback.h"
+
+namespace {
+constexpr uint16_t kSeqNumHalf = 0x8000u;
+constexpr uint16_t kSeqNumQuarter = kSeqNumHalf / 2;
+constexpr size_t kMaxConsecutiveOldReports = 4;
+}  // namespace
+
+namespace webrtc {
+
+TransportFeedbackPacketLossTracker::TransportFeedbackPacketLossTracker(
+    size_t min_window_size,
+    size_t max_window_size)
+    : min_window_size_(min_window_size),
+      max_window_size_(max_window_size),
+      ref_packet_status_(packet_status_window_.begin()) {
+  RTC_DCHECK_GT(min_window_size, 0u);
+  RTC_DCHECK_GE(max_window_size_, min_window_size_);
+  RTC_DCHECK_LE(max_window_size_, kSeqNumHalf);
+  Reset();
+}
+
+void TransportFeedbackPacketLossTracker::Reset() {
+  num_received_packets_ = 0;
+  num_lost_packets_ = 0;
+  num_consecutive_losses_ = 0;
+  num_consecutive_old_reports_ = 0;
+  packet_status_window_.clear();
+  ref_packet_status_ = packet_status_window_.begin();
+}
+
+uint16_t TransportFeedbackPacketLossTracker::ReferenceSequenceNumber() const {
+  RTC_DCHECK(!packet_status_window_.empty());
+  return ref_packet_status_->first;
+}
+
+bool TransportFeedbackPacketLossTracker::IsOldSequenceNumber(
+    uint16_t seq_num) const {
+  if (packet_status_window_.empty()) {
+    return false;
+  }
+  uint16_t diff = ForwardDiff(ReferenceSequenceNumber(), seq_num);
+  return diff >= 3 * kSeqNumQuarter;
+}
+
+void TransportFeedbackPacketLossTracker::OnReceivedTransportFeedback(
+    const rtcp::TransportFeedback& feedback) {
+  const auto& fb_vector = feedback.GetStatusVector();
+  const uint16_t base_seq_num = feedback.GetBaseSequence();
+
+  if (IsOldSequenceNumber(base_seq_num)) {
+    ++num_consecutive_old_reports_;
+    if (num_consecutive_old_reports_ <= kMaxConsecutiveOldReports) {
+      // If the number consecutive old reports have not exceed a threshold, we
+      // consider this packet as a late arrival. We could consider adding it to
+      // |packet_status_window_|, but in current implementation, we simply
+      // ignore it.
+      return;
+    }
+    // If we see several consecutive older reports, we assume that we've not
+    // received reports for an exceedingly long time, and do a reset.
+    Reset();
+    RTC_DCHECK(!IsOldSequenceNumber(base_seq_num));
+  } else {
+    num_consecutive_old_reports_ = 0;
+  }
+
+  uint16_t seq_num = base_seq_num;
+  for (size_t i = 0; i < fb_vector.size(); ++i, ++seq_num) {
+    // Remove the oldest feedbacks so that the distance between the oldest and
+    // the packet to be added does not exceed or equal to half of total sequence
+    // numbers.
+    while (!packet_status_window_.empty() &&
+           ForwardDiff(ReferenceSequenceNumber(), seq_num) >= kSeqNumHalf) {
+      RemoveOldestPacketStatus();
+    }
+
+    bool received = fb_vector[i] !=
+                    webrtc::rtcp::TransportFeedback::StatusSymbol::kNotReceived;
+    InsertPacketStatus(seq_num, received);
+
+    while (packet_status_window_.size() > max_window_size_) {
+      // Make sure that the window holds up to |max_window_size_| items.
+      RemoveOldestPacketStatus();
+    }
+  }
+}
+
+bool TransportFeedbackPacketLossTracker::GetPacketLossRates(
+    float* packet_loss_rate,
+    float* consecutive_packet_loss_rate) const {
+  size_t total = num_lost_packets_ + num_received_packets_;
+  if (total < min_window_size_)
+    return false;
+  *packet_loss_rate = static_cast<float>(num_lost_packets_) / total;
+  *consecutive_packet_loss_rate =
+      static_cast<float>(num_consecutive_losses_) / total;
+  return true;
+}
+
+void TransportFeedbackPacketLossTracker::InsertPacketStatus(uint16_t seq_num,
+                                                            bool received) {
+  const auto& ret =
+      packet_status_window_.insert(std::make_pair(seq_num, received));
+  if (!ret.second) {
+    if (!ret.first->second && received) {
+      // if older status said that the packet was lost but newer one says it

[stefan-webrtc, 2016/12/19 09:17:00]

If

[minyue-webrtc, 2016/12/19 10:21:55]

Done.

+      // it received, we take the newer one.

[stefan-webrtc, 2016/12/19 09:17:00]

is received

[minyue-webrtc, 2016/12/19 10:21:55]

Done.

+      UndoPacketStatus(ret.first);
+      ret.first->second = received;
+    } else {
+      // If the value is unchanged or if older status said that the packet was
+      // received but the newer one says it is lost, we ignore it.
+      return;
+    }
+  }
+
+  if (packet_status_window_.size() == 1)
+    ref_packet_status_ = ret.first;
+
+  if (received) {

[stefan-webrtc, 2016/12/19 09:17:00]

I would have split this method in two so that I had a method "SetPacketStatus"
or something like that, which was the exact opposite of UndoPacketStatus below.
I think it would improve readability.

[minyue-webrtc, 2016/12/19 10:21:55]

Done.

+    ++num_received_packets_;
+  } else {
+    ++num_lost_packets_;
+    const auto& next = NextPacketStatus(ret.first);
+    if (next != packet_status_window_.end() &&
+        next->first == static_cast<uint16_t>(seq_num + 1) && !next->second) {
+      // Feedback shows that the next packet has been lost. Since this
+      // packet is lost, we increase the consecutive loss counter.
+      ++num_consecutive_losses_;
+    }
+    const auto& it = PreviousPacketStatus(ret.first);
+    if (it != packet_status_window_.end() &&
+        it->first == static_cast<uint16_t>(seq_num - 1) && !it->second) {
+      // Feedback shows that the previous packet has been lost. Since this
+      // packet is lost, we increase the consecutive loss counter.
+      ++num_consecutive_losses_;
+    }
+  }
+}
+
+void TransportFeedbackPacketLossTracker::RemoveOldestPacketStatus() {
+  UndoPacketStatus(ref_packet_status_);
+  const auto it = ref_packet_status_;
+  ref_packet_status_ = NextPacketStatus(it);
+  packet_status_window_.erase(it);
+}
+
+void TransportFeedbackPacketLossTracker::UndoPacketStatus(
+    PacketStatusIterator it) {
+  RTC_DCHECK(it != packet_status_window_.end());
+  if (it->second) {
+    RTC_DCHECK_GT(num_received_packets_, 0u);
+    --num_received_packets_;
+  } else {
+    RTC_DCHECK_GT(num_lost_packets_, 0u);
+    --num_lost_packets_;
+    const auto& next = NextPacketStatus(it);
+    if (next != packet_status_window_.end() &&
+        next->first == static_cast<uint16_t>(it->first + 1) && !next->second) {
+      RTC_DCHECK_GT(num_consecutive_losses_, 0u);
+      --num_consecutive_losses_;
+    }
+    const auto& pre = PreviousPacketStatus(it);
+    if (pre != packet_status_window_.end() &&
+        pre->first == static_cast<uint16_t>(it->first - 1) && !pre->second) {
+      RTC_DCHECK_GT(num_consecutive_losses_, 0u);
+      --num_consecutive_losses_;
+    }
+  }
+}
+
+TransportFeedbackPacketLossTracker::PacketStatusIterator
+TransportFeedbackPacketLossTracker::PreviousPacketStatus(
+    PacketStatusIterator it) {
+  RTC_DCHECK(it != packet_status_window_.end());
+  if (it == ref_packet_status_)
+    return packet_status_window_.end();

[stefan-webrtc, 2016/12/19 09:17:00]

How does this work?

Let's say we have this:
1 2 3 ... FFFF
  ^---ref
  ^---it
    
moving to the previous gives us:
1 2 3 ... FFFF
  ^---ref
            ^---it

does this mean we'll never take the first element into account? Or maybe this
shouldn't ever happen for some reason?

[minyue-webrtc, 2016/12/19 10:21:55]

It is important to know that ::end refers to "past-the-end element is the
theoretical element that would follow the last element in the vector. It does
not point to any element." Here we only use "end" for its "no ref" property. It
is like "queue.find(sth) == queue.end()" means sth does not exist.

Another solution may be DCHECK(it != ref_packet_status_), then we have to treat
the case that "it == ref_packet_status_" before calling the method.

[minyue-webrtc, 2016/12/20 11:40:34]

I agree with you on the weirdness of this. Since Next(Prev(it)) might not equal
it in some cases.

I modified it a bit so that
1. if it == ref_packet_status_, no Prev(it) can be allowed.
2. if it == packet_status_window_.end(), Prev(it) points to the last element of
the map

[stefan-webrtc, 2016/12/20 12:13:41]

I think this is a bit hard to follow, but I'm not sure it's possible to make it
much simpler...

+  if (it == packet_status_window_.begin()) {

[stefan-webrtc, 2016/12/19 09:17:00]

Can this happen? Isn't it always between end() and ref_packet_status_?

[minyue-webrtc, 2016/12/19 10:21:55]

no, this can happen, using elements between end() and ref_packet_status_ is not
enough. say if 

ref_packet_status_ = 0xfffe, end() can not be larger than 0xffff (due to the
natural ordering of map.)

[stefan-webrtc, 2016/12/20 12:13:41]

Agree

+    // Due to the circular nature of sequence numbers, we let the iterator
+    // go to the end.
+    it = packet_status_window_.end();
+  }
+  return --it;
+}
+
+TransportFeedbackPacketLossTracker::PacketStatusIterator
+TransportFeedbackPacketLossTracker::NextPacketStatus(PacketStatusIterator it) {
+  RTC_DCHECK(it != packet_status_window_.end());
+  ++it;
+  if (it == packet_status_window_.end()) {
+    // Due to the circular nature of sequence numbers, we let the iterator
+    // goes back to the beginning.
+    it = packet_status_window_.begin();
+  }
+  if (it == ref_packet_status_)
+    return packet_status_window_.end();
+  return it;
+}
+
+void TransportFeedbackPacketLossTracker::Validate() const {  // Testing only!

[stefan-webrtc, 2016/12/19 09:17:00]

I don't think we should have test code here. This should be moved to the
unittest file. Perhaps we can write the test code in a less specific way to
avoid accessing class internals?

[minyue-webrtc, 2016/12/19 10:21:55]

To be honest, I have been struggling a lot on whether to place this here.
Finally, I decided to do this for the following reasons
1. This is used in both unittests and fuzzer tests, so we don't want to
duplicate the function
2. The method is very tight to the implementation details (as opposed to check
input-output relation). It might be easier to maintain if we place it here.
(say, if we change something, we are somehow reminded to change this method,
otherwise, we may need to wait for units/fuzzer tests to fail to see such a
need.)

[stefan-webrtc, 2016/12/20 12:13:41]

I don't think this is a good reason to have the test code be part of production
code. You can have a helper file for your unittests which is shared by the
unittests and the fuzzer.
That's a bad sign. We shouldn't be writing test code that relies on
implementation details in my opinion. Isn't what you truly care about the loss
rates that you get from GetPacketLossRates()? Then I'd imagine that it should be
possible to pass in a feedback message and put expectations on the loss rates
instead?

Another bad thing with this is that you will crash the test executable if these
tests start failing.

+  RTC_CHECK_LE(packet_status_window_.size(), max_window_size_);
+  RTC_CHECK_GE(num_lost_packets_, num_consecutive_losses_);
+  RTC_CHECK_EQ(packet_status_window_.size(),
+               num_lost_packets_ + num_received_packets_);
+
+  size_t received_packets = 0;
+  size_t lost_packets = 0;
+  size_t consecutive_losses = 0;
+
+  if (!packet_status_window_.empty()) {
+    PacketStatusIterator it = ref_packet_status_;
+    bool pre_lost = false;
+    uint16_t pre_seq_num = it->first - 1;
+    do {
+      if (it->second) {
+        ++received_packets;
+      } else {
+        ++lost_packets;
+        if (pre_lost && pre_seq_num == static_cast<uint16_t>(it->first - 1))
+          ++consecutive_losses;
+      }
+
+      RTC_CHECK_LT(ForwardDiff(ReferenceSequenceNumber(), it->first),
+                   kSeqNumHalf);
+
+      pre_lost = !it->second;
+      pre_seq_num = it->first;
+
+      ++it;
+      if (it == packet_status_window_.end())
+        it = packet_status_window_.begin();
+    } while (it != ref_packet_status_);
+  }
+
+  RTC_CHECK_EQ(num_received_packets_, received_packets);
+  RTC_CHECK_EQ(num_lost_packets_, lost_packets);
+  RTC_CHECK_EQ(num_consecutive_losses_, consecutive_losses);
+}
+
+}  // namespace webrtc