GetTransportFeedbackVector() includes unreceived packets, sorted by seq-num

webrtc/modules/congestion_controller/transport_feedback_adapter.cc

 /*
  *  Copyright (c) 2015 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/congestion_controller/transport_feedback_adapter.h"
 
 #include <algorithm>
 #include <limits>
 
 #include "webrtc/base/checks.h"
 #include "webrtc/base/logging.h"
+#include "webrtc/base/mod_ops.h"
 #include "webrtc/logging/rtc_event_log/rtc_event_log.h"
 #include "webrtc/modules/bitrate_controller/include/bitrate_controller.h"
 #include "webrtc/modules/congestion_controller/delay_based_bwe.h"
 #include "webrtc/modules/rtp_rtcp/source/rtcp_packet/transport_feedback.h"
 #include "webrtc/modules/utility/include/process_thread.h"
 #include "webrtc/system_wrappers/include/field_trial.h"
 
 namespace webrtc {
 
 const int64_t kNoTimestamp = -1;
 const int64_t kSendTimeHistoryWindowMs = 60000;
 const int64_t kBaseTimestampScaleFactor =
     rtcp::TransportFeedback::kDeltaScaleFactor * (1 << 8);
 const int64_t kBaseTimestampRangeSizeUs = kBaseTimestampScaleFactor * (1 << 24);
 
-class PacketFeedbackComparator {
- public:
-  inline bool operator()(const PacketFeedback& lhs, const PacketFeedback& rhs) {
-    if (lhs.arrival_time_ms != rhs.arrival_time_ms)
-      return lhs.arrival_time_ms < rhs.arrival_time_ms;
-    if (lhs.send_time_ms != rhs.send_time_ms)
-      return lhs.send_time_ms < rhs.send_time_ms;
-    return lhs.sequence_number < rhs.sequence_number;
-  }
-};
-
 TransportFeedbackAdapter::TransportFeedbackAdapter(
     RtcEventLog* event_log,
     Clock* clock,
     BitrateController* bitrate_controller)
     : send_side_bwe_with_overhead_(
           webrtc::field_trial::IsEnabled("WebRTC-SendSideBwe-WithOverhead")),
       transport_overhead_bytes_per_packet_(0),
       send_time_history_(clock, kSendTimeHistoryWindowMs),
       event_log_(event_log),
       clock_(clock),
@@ skipping 62 matching lines @@
     } else if (std::abs(delta + kBaseTimestampRangeSizeUs) < std::abs(delta)) {
       delta += kBaseTimestampRangeSizeUs;  // Wrap forwards.
     }
 
     current_offset_ms_ += delta / 1000;
   }
   last_timestamp_us_ = timestamp_us;
 
   auto received_packets = feedback.GetReceivedPackets();
   std::vector<PacketFeedback> packet_feedback_vector;
-  packet_feedback_vector.reserve(received_packets.size());
   if (received_packets.empty()) {
     LOG(LS_INFO) << "Empty transport feedback packet received.";
     return packet_feedback_vector;
   }
+  const uint16_t last_sequence_number =
+      received_packets.back().sequence_number();
+  const size_t packet_count =
+      1 + ForwardDiff(feedback.GetBaseSequence(), last_sequence_number);
+  packet_feedback_vector.reserve(packet_count);
+  // feedback.GetStatusVector().size() is a less efficient way to reach what
+  // should be the same value.
+  RTC_DCHECK_EQ(packet_count, feedback.GetStatusVector().size());
+
   {
     rtc::CritScope cs(&lock_);
     size_t failed_lookups = 0;
     int64_t offset_us = 0;
     int64_t timestamp_ms = 0;
-    for (const auto& packet : feedback.GetReceivedPackets()) {
+    uint16_t seq_num = feedback.GetBaseSequence();
+    for (const auto& packet : received_packets) {
+      // Insert into the vector those unreceived packets which precede this
+      // iteration's received packet.
+      for (; seq_num != packet.sequence_number(); ++seq_num) {
+        PacketFeedback packet_feedback(PacketFeedback::kNotReceived, seq_num);
+        // Note: Element not removed from history because it might be reported
+        // as received by another feedback.
+        if (!send_time_history_.GetFeedback(&packet_feedback, false))
+          ++failed_lookups;
+        packet_feedback_vector.push_back(packet_feedback);
+      }
+
+      // Handle this iteration's received packet.
       offset_us += packet.delta_us();
       timestamp_ms = current_offset_ms_ + (offset_us / 1000);
       PacketFeedback packet_feedback(timestamp_ms, packet.sequence_number());
       if (!send_time_history_.GetFeedback(&packet_feedback, true))
         ++failed_lookups;
       packet_feedback_vector.push_back(packet_feedback);
+
+      ++seq_num;
     }
-    std::sort(packet_feedback_vector.begin(), packet_feedback_vector.end(),
-              PacketFeedbackComparator());
+
     if (failed_lookups > 0) {
       LOG(LS_WARNING) << "Failed to lookup send time for " << failed_lookups
                       << " packet" << (failed_lookups > 1 ? "s" : "")
                       << ". Send time history too small?";
     }
   }
   return packet_feedback_vector;
 }
 
 void TransportFeedbackAdapter::OnTransportFeedback(
@@ skipping 14 matching lines @@
   return last_packet_feedback_vector_;
 }
 
 void TransportFeedbackAdapter::OnRttUpdate(int64_t avg_rtt_ms,
                                            int64_t max_rtt_ms) {
   rtc::CritScope cs(&bwe_lock_);
   delay_based_bwe_->OnRttUpdate(avg_rtt_ms, max_rtt_ms);
 }
 
 }  // namespace webrtc