1 files changed, 164 insertions, 0 deletions
diff --git a/third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.cc b/third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.cc
new file mode 100644
index 0000000000..182297d303
--- /dev/null
+++ b/third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.cc
@@ -0,0 +1,164 @@
+/*
+ *  Copyright (c) 2021 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 "modules/remote_bitrate_estimator/packet_arrival_map.h"
+
+#include <algorithm>
+#include <cstdint>
+
+#include "api/units/timestamp.h"
+#include "rtc_base/checks.h"
+
+namespace webrtc {
+
+void PacketArrivalTimeMap::AddPacket(int64_t sequence_number,
+                                     Timestamp arrival_time) {
+  RTC_DCHECK_GE(arrival_time, Timestamp::Zero());
+  if (!has_seen_packet()) {
+    // First packet.
+    Reallocate(kMinCapacity);
+    begin_sequence_number_ = sequence_number;
+    end_sequence_number_ = sequence_number + 1;
+    arrival_times_[Index(sequence_number)] = arrival_time;
+    return;
+  }
+
+  if (sequence_number >= begin_sequence_number() &&
+      sequence_number < end_sequence_number()) {
+    // The packet is within the buffer - no need to expand it.
+    arrival_times_[Index(sequence_number)] = arrival_time;
+    return;
+  }
+
+  if (sequence_number < begin_sequence_number()) {
+    // The packet goes before the current buffer. Expand to add packet, but only
+    // if it fits within kMaxNumberOfPackets.
+    int64_t new_size = end_sequence_number() - sequence_number;
+    if (new_size > kMaxNumberOfPackets) {
+      // Don't expand the buffer further, as that would remove newly received
+      // packets.
+      return;
+    }
+    AdjustToSize(new_size);
+
+    arrival_times_[Index(sequence_number)] = arrival_time;
+    SetNotReceived(sequence_number + 1, begin_sequence_number_);
+    begin_sequence_number_ = sequence_number;
+    return;
+  }
+
+  // The packet goes after the buffer.
+  RTC_DCHECK_GE(sequence_number, end_sequence_number_);
+  int64_t new_end_sequence_number = sequence_number + 1;
+
+  if (new_end_sequence_number >= end_sequence_number_ + kMaxNumberOfPackets) {
+    // All old packets have to be removed.
+    begin_sequence_number_ = sequence_number;
+    end_sequence_number_ = new_end_sequence_number;
+    arrival_times_[Index(sequence_number)] = arrival_time;
+    return;
+  }
+
+  if (begin_sequence_number_ < new_end_sequence_number - kMaxNumberOfPackets) {
+    // Remove oldest entries
+    begin_sequence_number_ = new_end_sequence_number - kMaxNumberOfPackets;
+    RTC_DCHECK_GT(end_sequence_number_, begin_sequence_number_);
+  }
+
+  AdjustToSize(new_end_sequence_number - begin_sequence_number_);
+
+  // Packets can be received out-of-order. If this isn't the next expected
+  // packet, add enough placeholders to fill the gap.
+  SetNotReceived(end_sequence_number_, sequence_number);
+  end_sequence_number_ = new_end_sequence_number;
+  arrival_times_[Index(sequence_number)] = arrival_time;
+}
+
+void PacketArrivalTimeMap::SetNotReceived(
+    int64_t begin_sequence_number_inclusive,
+    int64_t end_sequence_number_exclusive) {
+  static constexpr Timestamp value = Timestamp::MinusInfinity();
+
+  int begin_index = Index(begin_sequence_number_inclusive);
+  int end_index = Index(end_sequence_number_exclusive);
+
+  if (begin_index <= end_index) {
+    // Entries to clear are in single block:
+    // [......{-----}....]
+    std::fill(arrival_times_.get() + begin_index,
+              arrival_times_.get() + end_index, value);
+  } else {
+    // Entries to clear span across arrival_times_ border:
+    // [--}..........{---]
+    std::fill(arrival_times_.get() + begin_index,
+              arrival_times_.get() + capacity(), value);
+    std::fill(arrival_times_.get(), arrival_times_.get() + end_index, value);
+  }
+}
+
+void PacketArrivalTimeMap::RemoveOldPackets(int64_t sequence_number,
+                                            Timestamp arrival_time_limit) {
+  int64_t check_to = std::min(sequence_number, end_sequence_number_);
+  while (begin_sequence_number_ < check_to &&
+         arrival_times_[Index(begin_sequence_number_)] <= arrival_time_limit) {
+    ++begin_sequence_number_;
+  }
+  AdjustToSize(end_sequence_number_ - begin_sequence_number_);
+}
+
+void PacketArrivalTimeMap::EraseTo(int64_t sequence_number) {
+  if (sequence_number < begin_sequence_number_) {
+    return;
+  }
+  if (sequence_number >= end_sequence_number_) {
+    // Erase all.
+    begin_sequence_number_ = end_sequence_number_;
+    return;
+  }
+  // Remove some.
+  begin_sequence_number_ = sequence_number;
+  AdjustToSize(end_sequence_number_ - begin_sequence_number_);
+}
+
+void PacketArrivalTimeMap::AdjustToSize(int new_size) {
+  if (new_size > capacity()) {
+    int new_capacity = capacity();
+    while (new_capacity < new_size)
+      new_capacity *= 2;
+    Reallocate(new_capacity);
+  }
+  if (capacity() > std::max(kMinCapacity, 4 * new_size)) {
+    int new_capacity = capacity();
+    while (new_capacity > 2 * std::max(new_size, kMinCapacity)) {
+      new_capacity /= 2;
+    }
+    Reallocate(new_capacity);
+  }
+  RTC_DCHECK_LE(new_size, capacity());
+}
+
+void PacketArrivalTimeMap::Reallocate(int new_capacity) {
+  int new_capacity_minus_1 = new_capacity - 1;
+  // Check capacity is a power of 2.
+  RTC_DCHECK_EQ(new_capacity & new_capacity_minus_1, 0);
+  // Create uninitialized memory.
+  // All valid entries should be set by `AddPacket` before use.
+  void* raw = operator new[](new_capacity * sizeof(Timestamp));
+  Timestamp* new_buffer = static_cast<Timestamp*>(raw);
+
+  for (int64_t sequence_number = begin_sequence_number_;
+       sequence_number < end_sequence_number_; ++sequence_number) {
+    new_buffer[sequence_number & new_capacity_minus_1] =
+        arrival_times_[sequence_number & capacity_minus_1_];
+  }
+  arrival_times_.reset(new_buffer);
+  capacity_minus_1_ = new_capacity_minus_1;
+}
+
+}  // namespace webrtc