First-order-FEC recoverability calculation

webrtc/voice_engine/transport_feedback_packet_loss_tracker.cc

 /*
  *  Copyright (c) 2017 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/voice_engine/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;
+
+inline void UpdateCounter(size_t& counter, bool increment) {

[minyue-webrtc, 2017/01/25 09:38:45]

remove "inline", it happens automatically.

[minyue-webrtc, 2017/01/25 09:38:45]

& always goes with const, so use

size_t* counter

+  increment ? ++counter : --counter;
+}
+
 }  // 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, 0);
-  RTC_DCHECK_GE(max_window_size_, min_window_size_);
-  RTC_DCHECK_LE(max_window_size_, kSeqNumHalf);
+    size_t max_window_size,
+    size_t min_pairs_num_for_rplr)
+    : max_window_size_(max_window_size),
+      ref_packet_status_(packet_status_window_.begin()),
+      plr_state_(min_window_size),
+      rplr_state_(min_pairs_num_for_rplr) {
+  RTC_DCHECK_GT(min_window_size, 0u);

[minyue-webrtc, 2017/01/25 09:38:45]

remove "u" after 0

[elad.alon_webrtc.org, 2017/01/25 12:47:54]

Rebase relic. Done.

+  RTC_DCHECK_GE(max_window_size, min_window_size);
+  RTC_DCHECK_LE(max_window_size, kSeqNumHalf);
+  RTC_DCHECK_GT(min_pairs_num_for_rplr, 0);
+  RTC_DCHECK_GT(max_window_size, min_pairs_num_for_rplr);
   Reset();
 }
 
 void TransportFeedbackPacketLossTracker::Reset() {
-  num_received_packets_ = 0;
-  num_lost_packets_ = 0;
-  num_consecutive_losses_ = 0;
+  plr_state_.Reset();
+  rplr_state_.Reset();
   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;
 }
 
@@ skipping 43 matching lines @@
         webrtc::rtcp::TransportFeedback::StatusSymbol::kNotReceived;
     InsertPacketStatus(seq_num, received);
 
     while (packet_status_window_.size() > max_window_size_) {
       // Make sure that the window holds at most |max_window_size_| items.
       RemoveOldestPacketStatus();
     }
   }
 }
 
-bool TransportFeedbackPacketLossTracker::GetPacketLossRates(
-    float* packet_loss_rate,
-    float* consecutive_packet_loss_rate) const {
-  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;
+rtc::Optional<float>
+TransportFeedbackPacketLossTracker::GetPacketLossRate() const {
+  return plr_state_.GetMetric();
+}
+
+// Returns the first-order-FEC recoverable packet loss rate, if the window

[minyue-webrtc, 2017/01/25 09:38:45]

merge this comment to the header file

[elad.alon_webrtc.org, 2017/01/25 12:47:54]

Done.

+// has enough data to reliably compute it.
+rtc::Optional<float>
+TransportFeedbackPacketLossTracker::GetRecoverablePacketLossRate() const {
+  return rplr_state_.GetMetric();
 }
 
 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
       // is received, we take the newer one.
-      UndoPacketStatus(ret.first);
+      UpdateMetrics(ret.first, false);
       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;
     }
   }
-  ApplyPacketStatus(ret.first);
+  UpdateMetrics(ret.first, true);
   if (packet_status_window_.size() == 1)
     ref_packet_status_ = ret.first;
 }
 
 void TransportFeedbackPacketLossTracker::RemoveOldestPacketStatus() {
-  UndoPacketStatus(ref_packet_status_);
+  UpdateMetrics(ref_packet_status_, false);
   const auto it = ref_packet_status_;
   ref_packet_status_ = NextPacketStatus(it);
   packet_status_window_.erase(it);
 }
 
-void TransportFeedbackPacketLossTracker::ApplyPacketStatus(
-    PacketStatusIterator it) {
+void TransportFeedbackPacketLossTracker::UpdateMetrics(
+    PacketStatusIterator it,
+    bool apply /* false = undo */) {
   RTC_DCHECK(it != packet_status_window_.end());
+  UpdatePlr(it, apply);
+  UpdateRplr(it, apply);
+}
+
+void TransportFeedbackPacketLossTracker::UpdatePlr(
+    PacketStatusIterator it,
+    bool apply /* false = undo */) {
+  // Record or undo recetion status of currently handled packet.

[minyue-webrtc, 2017/01/25 09:38:45]

reception

But I think the code is clear enough to remove the whole comment.

[elad.alon_webrtc.org, 2017/01/25 12:47:54]

I want this comment to indicate the "currently handled packet" part, as opposed
to the RPLR calculation, which handles pairs. Can't hurt, imho.

   if (it->second) {
-    ++num_received_packets_;
+    UpdateCounter(plr_state_.num_received_packets_, apply);
   } else {
-    ++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) {
-      // Feedback shows that the next packet has been lost. Since this
-      // packet is lost, we increase the consecutive loss counter.
-      ++num_consecutive_losses_;
-    }
-    if (it != ref_packet_status_) {
-      const auto& pre = PreviousPacketStatus(it);
-      if (pre->first == static_cast<uint16_t>(it->first - 1) && !pre->second) {
-        // Feedback shows that the previous packet has been lost. Since this
-        // packet is lost, we increase the consecutive loss counter.
-        ++num_consecutive_losses_;
+    UpdateCounter(plr_state_.num_lost_packets_, apply);
+  }
+}
+
+void TransportFeedbackPacketLossTracker::UpdateRplr(
+    PacketStatusIterator it,
+    bool apply /* false = undo */) {
+  // Previous packet and current packet might compose a pair.

[minyue-webrtc, 2017/01/25 09:38:45]

preferably, move the comment after 180 and write

// Previous packet and current packet compose a pair.

[elad.alon_webrtc.org, 2017/01/25 12:47:54]

IMHO, clearer to have it over the entire block, which makes it clearer what the
entire block does. If inside the block, someone who reads this quickly could
think it only illuminates some particular part only.

+  if (it != ref_packet_status_) {
+    const auto& prev = PreviousPacketStatus(it);
+    if (prev->first == static_cast<uint16_t>(it->first - 1)) {
+      UpdateCounter(rplr_state_.num_known_status_pairs_, apply);
+      if (!prev->second && it->second) {
+        UpdateCounter(rplr_state_.num_loss_followed_by_reception_pairs_, apply);
       }
     }
   }
-}
 
-void TransportFeedbackPacketLossTracker::UndoPacketStatus(
-    PacketStatusIterator it) {
-  RTC_DCHECK(it != packet_status_window_.end());
-  if (it->second) {
-    RTC_DCHECK_GT(num_received_packets_, 0);
-    --num_received_packets_;
-  } else {
-    RTC_DCHECK_GT(num_lost_packets_, 0);
-    --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_, 0);
-      --num_consecutive_losses_;
-    }
-    if (it != ref_packet_status_) {
-      const auto& pre = PreviousPacketStatus(it);
-      if (pre->first == static_cast<uint16_t>(it->first - 1) && !pre->second) {
-        RTC_DCHECK_GT(num_consecutive_losses_, 0);
-        --num_consecutive_losses_;
-      }
+  // Current packet and next packet might compose a pair.

[minyue-webrtc, 2017/01/25 09:38:45]

preferably, move the comment after 190 and write

// Current packet and next packet compose a pair.

[elad.alon_webrtc.org, 2017/01/25 12:47:54]

Similarly.

+  const auto& next = NextPacketStatus(it);
+  if (next != packet_status_window_.end() &&
+      next->first == static_cast<uint16_t>(it->first + 1)) {
+    UpdateCounter(rplr_state_.num_known_status_pairs_, apply);
+    if (!it->second && next->second) {
+      UpdateCounter(rplr_state_.num_loss_followed_by_reception_pairs_, apply);
     }
   }
 }
 
 TransportFeedbackPacketLossTracker::PacketStatusIterator
 TransportFeedbackPacketLossTracker::PreviousPacketStatus(
     PacketStatusIterator it) {
   RTC_DCHECK(it != ref_packet_status_);
   if (it == packet_status_window_.end()) {
     // This is to make PreviousPacketStatus(packet_status_window_.end()) point
@@ skipping 26 matching lines @@
   return it;
 }
 
 // TODO(minyue): This method checks the states of this class do not misbehave.
 // The method is used both in unit tests and a fuzzer test. The fuzzer test
 // is present to help finding potential errors. Once the fuzzer test shows no
 // error after long period, we can remove the fuzzer test, and move this method
 // to unit test.
 void TransportFeedbackPacketLossTracker::Validate() const {  // Testing only!
   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_);
+               plr_state_.num_lost_packets_ + plr_state_.num_received_packets_);
+  RTC_CHECK_LE(rplr_state_.num_loss_followed_by_reception_pairs_,
+               rplr_state_.num_known_status_pairs_);
+  RTC_CHECK_LE(rplr_state_.num_known_status_pairs_,
+               packet_status_window_.size() - 1);
 
   size_t received_packets = 0;
   size_t lost_packets = 0;
-  size_t consecutive_losses = 0;
+  size_t known_status_pairs = 0;

[minyue-webrtc, 2017/01/25 09:38:45]

if you accept to simplify the private var to num_pairs_, this can be simplified
to "pairs"

[elad.alon_webrtc.org, 2017/01/25 12:47:54]

I prefer known_status_pairs, because the next CL introduces the possibility of
pairs of type (SENT, LOST), where SENT is unacked, and therefore not "a real
pair", or more accurately not a fully known-status pair.

+  size_t loss_followed_by_reception_pairs = 0;

[minyue-webrtc, 2017/01/25 09:38:45]

lost_received_pairs

[elad.alon_webrtc.org, 2017/01/25 12:47:54]

Discussed in .h file comments. More feedback welcome.

 
   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;
+      }
+
+      auto next = std::next(it);
+      if (next == packet_status_window_.end())
+        next = packet_status_window_.begin();
+
+      if (next != ref_packet_status_ &&
+          static_cast<uint16_t>(it->first + 1) == next->first) {

[minyue-webrtc, 2017/01/25 09:38:45]

next->first == static_cast<uint16_t>(it->first + 1)

[elad.alon_webrtc.org, 2017/01/25 12:47:54]

Done.

+        ++known_status_pairs;
+        if (!it->second && next->second)
+          ++loss_followed_by_reception_pairs;
       }
 
       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();
+      it = next;
     } 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);
+  RTC_CHECK_EQ(plr_state_.num_received_packets_, received_packets);
+  RTC_CHECK_EQ(plr_state_.num_lost_packets_, lost_packets);
+  RTC_CHECK_EQ(rplr_state_.num_known_status_pairs_, known_status_pairs);
+  RTC_CHECK_EQ(rplr_state_.num_loss_followed_by_reception_pairs_,
+               loss_followed_by_reception_pairs);
+}
+
+rtc::Optional<float>
+TransportFeedbackPacketLossTracker::PlrState::GetMetric() const {
+  const size_t total = num_lost_packets_ + num_received_packets_;
+  if (total < min_window_size_)

[minyue-webrtc, 2017/01/25 09:38:45]

have to add {} when there are multiple lines in if.

[elad.alon_webrtc.org, 2017/01/25 12:47:54]

There aren't multiple lines here. Or do you mean visual lines?
Coding-style-wise? If so - done.

[minyue-webrtc, 2017/01/25 20:00:59]

when else is present, it is considered multiple line :)

+    return rtc::Optional<float>();
+  else
+    return rtc::Optional<float>(
+        static_cast<float>(num_lost_packets_) / total);
+}
+
+rtc::Optional<float>
+TransportFeedbackPacketLossTracker::RplrState::GetMetric() const {
+  if (num_known_status_pairs_ < min_pairs_)

[minyue-webrtc, 2017/01/25 09:38:45]

add {} around if and else

[elad.alon_webrtc.org, 2017/01/25 12:47:54]

Similarly.

+    return rtc::Optional<float>();
+  else
+    return rtc::Optional<float>(
+        static_cast<float>(num_loss_followed_by_reception_pairs_) /
+        num_known_status_pairs_);
 }
 
 }  // namespace webrtc