1 files changed, 144 insertions, 0 deletions
diff --git a/third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.h b/third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.h
new file mode 100644
index 0000000000..4ae47172bc
--- /dev/null
+++ b/third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.h
@@ -0,0 +1,144 @@
+/*
+ *  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.
+ */
+#ifndef MODULES_REMOTE_BITRATE_ESTIMATOR_PACKET_ARRIVAL_MAP_H_
+#define MODULES_REMOTE_BITRATE_ESTIMATOR_PACKET_ARRIVAL_MAP_H_
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+
+#include "api/units/timestamp.h"
+#include "rtc_base/checks.h"
+
+namespace webrtc {
+
+// PacketArrivalTimeMap is an optimized map of packet sequence number to arrival
+// time, limited in size to never exceed `kMaxNumberOfPackets`. It will grow as
+// needed, and remove old packets, and will expand to allow earlier packets to
+// be added (out-of-order).
+//
+// Not yet received packets have the arrival time zero. The queue will not span
+// larger than necessary and the last packet should always be received. The
+// first packet in the queue doesn't have to be received in case of receiving
+// packets out-of-order.
+class PacketArrivalTimeMap {
+ public:
+  struct PacketArrivalTime {
+    Timestamp arrival_time;
+    int64_t sequence_number;
+  };
+  // Impossible to request feedback older than what can be represented by 15
+  // bits.
+  static constexpr int kMaxNumberOfPackets = (1 << 15);
+
+  PacketArrivalTimeMap() = default;
+  PacketArrivalTimeMap(const PacketArrivalTimeMap&) = delete;
+  PacketArrivalTimeMap& operator=(const PacketArrivalTimeMap&) = delete;
+  ~PacketArrivalTimeMap() = default;
+
+  // Indicates if the packet with `sequence_number` has already been received.
+  bool has_received(int64_t sequence_number) const {
+    return sequence_number >= begin_sequence_number() &&
+           sequence_number < end_sequence_number() &&
+           arrival_times_[Index(sequence_number)] >= Timestamp::Zero();
+  }
+
+  // Returns the sequence number of the first entry in the map, i.e. the
+  // sequence number that a `begin()` iterator would represent.
+  int64_t begin_sequence_number() const { return begin_sequence_number_; }
+
+  // Returns the sequence number of the element just after the map, i.e. the
+  // sequence number that an `end()` iterator would represent.
+  int64_t end_sequence_number() const { return end_sequence_number_; }
+
+  // Returns an element by `sequence_number`, which must be valid, i.e.
+  // between [begin_sequence_number, end_sequence_number).
+  Timestamp get(int64_t sequence_number) {
+    RTC_DCHECK_GE(sequence_number, begin_sequence_number());
+    RTC_DCHECK_LT(sequence_number, end_sequence_number());
+    return arrival_times_[Index(sequence_number)];
+  }
+
+  // Returns timestamp and sequence number of the received packet with sequence
+  // number equal or larger than `sequence_number`. `sequence_number` must be in
+  // range [begin_sequence_number, end_sequence_number).
+  PacketArrivalTime FindNextAtOrAfter(int64_t sequence_number) const {
+    RTC_DCHECK_GE(sequence_number, begin_sequence_number());
+    RTC_DCHECK_LT(sequence_number, end_sequence_number());
+    while (true) {
+      Timestamp t = arrival_times_[Index(sequence_number)];
+      if (t >= Timestamp::Zero()) {
+        return {.arrival_time = t, .sequence_number = sequence_number};
+      }
+      ++sequence_number;
+    }
+  }
+
+  // Clamps `sequence_number` between [begin_sequence_number,
+  // end_sequence_number].
+  int64_t clamp(int64_t sequence_number) const {
+    return std::clamp(sequence_number, begin_sequence_number(),
+                      end_sequence_number());
+  }
+
+  // Erases all elements from the beginning of the map until `sequence_number`.
+  void EraseTo(int64_t sequence_number);
+
+  // Records the fact that a packet with `sequence_number` arrived at
+  // `arrival_time_ms`.
+  void AddPacket(int64_t sequence_number, Timestamp arrival_time);
+
+  // Removes packets from the beginning of the map as long as they are received
+  // before `sequence_number` and with an age older than `arrival_time_limit`
+  void RemoveOldPackets(int64_t sequence_number, Timestamp arrival_time_limit);
+
+ private:
+  static constexpr int kMinCapacity = 128;
+
+  // Returns index in the `arrival_times_` for value for `sequence_number`.
+  int Index(int64_t sequence_number) const {
+    // Note that sequence_number might be negative, thus taking '%' requires
+    // extra handling and can be slow. Because capacity is a power of two, it
+    // is much faster to use '&' operator.
+    return sequence_number & capacity_minus_1_;
+  }
+
+  void SetNotReceived(int64_t begin_sequence_number_inclusive,
+                      int64_t end_sequence_number_exclusive);
+
+  // Adjust capacity to match new_size, may reduce capacity.
+  // On return guarantees capacity >= new_size.
+  void AdjustToSize(int new_size);
+  void Reallocate(int new_capacity);
+
+  int capacity() const { return capacity_minus_1_ + 1; }
+  bool has_seen_packet() const { return arrival_times_ != nullptr; }
+
+  // Circular buffer. Packet with sequence number `sequence_number`
+  // is stored in the slot `sequence_number % capacity_`
+  std::unique_ptr<Timestamp[]> arrival_times_ = nullptr;
+
+  // Allocated size of the `arrival_times_`
+  // capacity_ is a power of 2 in range [kMinCapacity, kMaxNumberOfPackets]
+  // `capacity - 1` is used much more often than `capacity`, thus that value is
+  // stored.
+  int capacity_minus_1_ = -1;
+
+  // The unwrapped sequence number for valid range of sequence numbers.
+  // arrival_times_ entries only valid for sequence numbers in range
+  // `begin_sequence_number_ <= sequence_number < end_sequence_number_`
+  int64_t begin_sequence_number_ = 0;
+  int64_t end_sequence_number_ = 0;
+};
+
+}  // namespace webrtc
+
+#endif  // MODULES_REMOTE_BITRATE_ESTIMATOR_PACKET_ARRIVAL_MAP_H_