diff options
Diffstat (limited to 'third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.h')
-rw-r--r-- | third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.h | 144 |
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_ |