packet_arrival_map.h (5894B)
1 /* 2 * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 #ifndef MODULES_REMOTE_BITRATE_ESTIMATOR_PACKET_ARRIVAL_MAP_H_ 11 #define MODULES_REMOTE_BITRATE_ESTIMATOR_PACKET_ARRIVAL_MAP_H_ 12 13 #include <algorithm> 14 #include <cstddef> 15 #include <cstdint> 16 #include <memory> 17 18 #include "api/units/timestamp.h" 19 #include "rtc_base/checks.h" 20 21 namespace webrtc { 22 23 // PacketArrivalTimeMap is an optimized map of packet sequence number to arrival 24 // time, limited in size to never exceed `kMaxNumberOfPackets`. It will grow as 25 // needed, and remove old packets, and will expand to allow earlier packets to 26 // be added (out-of-order). 27 // 28 // Not yet received packets have the arrival time zero. The queue will not span 29 // larger than necessary and the last packet should always be received. The 30 // first packet in the queue doesn't have to be received in case of receiving 31 // packets out-of-order. 32 class PacketArrivalTimeMap { 33 public: 34 struct PacketArrivalTime { 35 Timestamp arrival_time; 36 int64_t sequence_number; 37 }; 38 // Impossible to request feedback older than what can be represented by 15 39 // bits. 40 static constexpr int kMaxNumberOfPackets = (1 << 15); 41 42 PacketArrivalTimeMap() = default; 43 PacketArrivalTimeMap(const PacketArrivalTimeMap&) = delete; 44 PacketArrivalTimeMap& operator=(const PacketArrivalTimeMap&) = delete; 45 ~PacketArrivalTimeMap() = default; 46 47 // Indicates if the packet with `sequence_number` has already been received. 48 bool has_received(int64_t sequence_number) const { 49 return sequence_number >= begin_sequence_number() && 50 sequence_number < end_sequence_number() && 51 arrival_times_[Index(sequence_number)] >= Timestamp::Zero(); 52 } 53 54 // Returns the sequence number of the first entry in the map, i.e. the 55 // sequence number that a `begin()` iterator would represent. 56 int64_t begin_sequence_number() const { return begin_sequence_number_; } 57 58 // Returns the sequence number of the element just after the map, i.e. the 59 // sequence number that an `end()` iterator would represent. 60 int64_t end_sequence_number() const { return end_sequence_number_; } 61 62 // Returns an element by `sequence_number`, which must be valid, i.e. 63 // between [begin_sequence_number, end_sequence_number). 64 Timestamp get(int64_t sequence_number) { 65 RTC_DCHECK_GE(sequence_number, begin_sequence_number()); 66 RTC_DCHECK_LT(sequence_number, end_sequence_number()); 67 return arrival_times_[Index(sequence_number)]; 68 } 69 70 // Returns timestamp and sequence number of the received packet with sequence 71 // number equal or larger than `sequence_number`. `sequence_number` must be in 72 // range [begin_sequence_number, end_sequence_number). 73 PacketArrivalTime FindNextAtOrAfter(int64_t sequence_number) const { 74 RTC_DCHECK_GE(sequence_number, begin_sequence_number()); 75 RTC_DCHECK_LT(sequence_number, end_sequence_number()); 76 while (true) { 77 Timestamp t = arrival_times_[Index(sequence_number)]; 78 if (t >= Timestamp::Zero()) { 79 return {.arrival_time = t, .sequence_number = sequence_number}; 80 } 81 ++sequence_number; 82 } 83 } 84 85 // Clamps `sequence_number` between [begin_sequence_number, 86 // end_sequence_number]. 87 int64_t clamp(int64_t sequence_number) const { 88 return std::clamp(sequence_number, begin_sequence_number(), 89 end_sequence_number()); 90 } 91 92 // Erases all elements from the beginning of the map until `sequence_number`. 93 void EraseTo(int64_t sequence_number); 94 95 // Records the fact that a packet with `sequence_number` arrived at 96 // `arrival_time_ms`. 97 void AddPacket(int64_t sequence_number, Timestamp arrival_time); 98 99 // Removes packets from the beginning of the map as long as they are received 100 // before `sequence_number` and with an age older than `arrival_time_limit` 101 void RemoveOldPackets(int64_t sequence_number, Timestamp arrival_time_limit); 102 103 private: 104 static constexpr int kMinCapacity = 128; 105 106 // Returns index in the `arrival_times_` for value for `sequence_number`. 107 int Index(int64_t sequence_number) const { 108 // Note that sequence_number might be negative, thus taking '%' requires 109 // extra handling and can be slow. Because capacity is a power of two, it 110 // is much faster to use '&' operator. 111 return sequence_number & capacity_minus_1_; 112 } 113 114 void SetNotReceived(int64_t begin_sequence_number_inclusive, 115 int64_t end_sequence_number_exclusive); 116 117 // Adjust capacity to match new_size, may reduce capacity. 118 // On return guarantees capacity >= new_size. 119 void AdjustToSize(int new_size); 120 void Reallocate(int new_capacity); 121 122 int capacity() const { return capacity_minus_1_ + 1; } 123 bool has_seen_packet() const { return arrival_times_ != nullptr; } 124 125 // Circular buffer. Packet with sequence number `sequence_number` 126 // is stored in the slot `sequence_number % capacity_` 127 std::unique_ptr<Timestamp[]> arrival_times_ = nullptr; 128 129 // Allocated size of the `arrival_times_` 130 // capacity_ is a power of 2 in range [kMinCapacity, kMaxNumberOfPackets] 131 // `capacity - 1` is used much more often than `capacity`, thus that value is 132 // stored. 133 int capacity_minus_1_ = -1; 134 135 // The unwrapped sequence number for valid range of sequence numbers. 136 // arrival_times_ entries only valid for sequence numbers in range 137 // `begin_sequence_number_ <= sequence_number < end_sequence_number_` 138 int64_t begin_sequence_number_ = 0; 139 int64_t end_sequence_number_ = 0; 140 }; 141 142 } // namespace webrtc 143 144 #endif // MODULES_REMOTE_BITRATE_ESTIMATOR_PACKET_ARRIVAL_MAP_H_