| /* |
| * 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); |
| |
| void TrimLeadingNotReceivedEntries(); |
| |
| // 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_ |