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 #include "modules/remote_bitrate_estimator/packet_arrival_map.h"
11
12 #include <algorithm>
13 #include <cstdint>
14
15 #include "api/units/timestamp.h"
16 #include "rtc_base/checks.h"
17
18 namespace webrtc {
19
AddPacket(int64_t sequence_number,Timestamp arrival_time)20 void PacketArrivalTimeMap::AddPacket(int64_t sequence_number,
21 Timestamp arrival_time) {
22 RTC_DCHECK_GE(arrival_time, Timestamp::Zero());
23 if (!has_seen_packet()) {
24 // First packet.
25 Reallocate(kMinCapacity);
26 begin_sequence_number_ = sequence_number;
27 end_sequence_number_ = sequence_number + 1;
28 arrival_times_[Index(sequence_number)] = arrival_time;
29 return;
30 }
31
32 if (sequence_number >= begin_sequence_number() &&
33 sequence_number < end_sequence_number()) {
34 // The packet is within the buffer - no need to expand it.
35 arrival_times_[Index(sequence_number)] = arrival_time;
36 return;
37 }
38
39 if (sequence_number < begin_sequence_number()) {
40 // The packet goes before the current buffer. Expand to add packet, but only
41 // if it fits within kMaxNumberOfPackets.
42 int64_t new_size = end_sequence_number() - sequence_number;
43 if (new_size > kMaxNumberOfPackets) {
44 // Don't expand the buffer further, as that would remove newly received
45 // packets.
46 return;
47 }
48 AdjustToSize(new_size);
49
50 arrival_times_[Index(sequence_number)] = arrival_time;
51 SetNotReceived(sequence_number + 1, begin_sequence_number_);
52 begin_sequence_number_ = sequence_number;
53 return;
54 }
55
56 // The packet goes after the buffer.
57 RTC_DCHECK_GE(sequence_number, end_sequence_number_);
58 int64_t new_end_sequence_number = sequence_number + 1;
59
60 if (new_end_sequence_number >= end_sequence_number_ + kMaxNumberOfPackets) {
61 // All old packets have to be removed.
62 begin_sequence_number_ = sequence_number;
63 end_sequence_number_ = new_end_sequence_number;
64 arrival_times_[Index(sequence_number)] = arrival_time;
65 return;
66 }
67
68 if (begin_sequence_number_ < new_end_sequence_number - kMaxNumberOfPackets) {
69 // Remove oldest entries
70 begin_sequence_number_ = new_end_sequence_number - kMaxNumberOfPackets;
71 RTC_DCHECK_GT(end_sequence_number_, begin_sequence_number_);
72 // Also trim the buffer to remove leading non-received packets, to
73 // ensure that the buffer only spans received packets.
74 TrimLeadingNotReceivedEntries();
75 }
76
77 AdjustToSize(new_end_sequence_number - begin_sequence_number_);
78
79 // Packets can be received out-of-order. If this isn't the next expected
80 // packet, add enough placeholders to fill the gap.
81 SetNotReceived(end_sequence_number_, sequence_number);
82 end_sequence_number_ = new_end_sequence_number;
83 arrival_times_[Index(sequence_number)] = arrival_time;
84 }
85
TrimLeadingNotReceivedEntries()86 void PacketArrivalTimeMap::TrimLeadingNotReceivedEntries() {
87 const int begin_index = Index(begin_sequence_number_);
88 const Timestamp* const begin_it = arrival_times_.get() + begin_index;
89 const Timestamp* const end_it = arrival_times_.get() + capacity();
90
91 for (const Timestamp* it = begin_it; it != end_it; ++it) {
92 if (*it >= Timestamp::Zero()) {
93 begin_sequence_number_ += (it - begin_it);
94 return;
95 }
96 }
97 // Reached end of the arrival_times_ and all entries represent not received
98 // packets. Remove them.
99 begin_sequence_number_ += (capacity() - begin_index);
100 // Continue removing entries at the beginning of the circular buffer.
101 for (const Timestamp* it = arrival_times_.get(); it != begin_it; ++it) {
102 if (*it >= Timestamp::Zero()) {
103 begin_sequence_number_ += (it - arrival_times_.get());
104 return;
105 }
106 }
107
108 RTC_DCHECK_NOTREACHED() << "There should be at least one non-empty entry";
109 }
110
SetNotReceived(int64_t begin_sequence_number_inclusive,int64_t end_sequence_number_exclusive)111 void PacketArrivalTimeMap::SetNotReceived(
112 int64_t begin_sequence_number_inclusive,
113 int64_t end_sequence_number_exclusive) {
114 static constexpr Timestamp value = Timestamp::MinusInfinity();
115
116 int begin_index = Index(begin_sequence_number_inclusive);
117 int end_index = Index(end_sequence_number_exclusive);
118
119 if (begin_index <= end_index) {
120 // Entries to clear are in single block:
121 // [......{-----}....]
122 std::fill(arrival_times_.get() + begin_index,
123 arrival_times_.get() + end_index, value);
124 } else {
125 // Entries to clear span across arrival_times_ border:
126 // [--}..........{---]
127 std::fill(arrival_times_.get() + begin_index,
128 arrival_times_.get() + capacity(), value);
129 std::fill(arrival_times_.get(), arrival_times_.get() + end_index, value);
130 }
131 }
132
RemoveOldPackets(int64_t sequence_number,Timestamp arrival_time_limit)133 void PacketArrivalTimeMap::RemoveOldPackets(int64_t sequence_number,
134 Timestamp arrival_time_limit) {
135 int64_t check_to = std::min(sequence_number, end_sequence_number_);
136 while (begin_sequence_number_ < check_to &&
137 arrival_times_[Index(begin_sequence_number_)] <= arrival_time_limit) {
138 ++begin_sequence_number_;
139 }
140 AdjustToSize(end_sequence_number_ - begin_sequence_number_);
141 }
142
EraseTo(int64_t sequence_number)143 void PacketArrivalTimeMap::EraseTo(int64_t sequence_number) {
144 if (sequence_number < begin_sequence_number_) {
145 return;
146 }
147 if (sequence_number >= end_sequence_number_) {
148 // Erase all.
149 begin_sequence_number_ = end_sequence_number_;
150 return;
151 }
152 // Remove some.
153 begin_sequence_number_ = sequence_number;
154 AdjustToSize(end_sequence_number_ - begin_sequence_number_);
155 }
156
AdjustToSize(int new_size)157 void PacketArrivalTimeMap::AdjustToSize(int new_size) {
158 if (new_size > capacity()) {
159 int new_capacity = capacity();
160 while (new_capacity < new_size)
161 new_capacity *= 2;
162 Reallocate(new_capacity);
163 }
164 if (capacity() > std::max(kMinCapacity, 4 * new_size)) {
165 int new_capacity = capacity();
166 while (new_capacity > 2 * std::max(new_size, kMinCapacity)) {
167 new_capacity /= 2;
168 }
169 Reallocate(new_capacity);
170 }
171 RTC_DCHECK_LE(new_size, capacity());
172 }
173
Reallocate(int new_capacity)174 void PacketArrivalTimeMap::Reallocate(int new_capacity) {
175 int new_capacity_minus_1 = new_capacity - 1;
176 // Check capacity is a power of 2.
177 RTC_DCHECK_EQ(new_capacity & new_capacity_minus_1, 0);
178 // Create uninitialized memory.
179 // All valid entries should be set by `AddPacket` before use.
180 void* raw = operator new[](new_capacity * sizeof(Timestamp));
181 Timestamp* new_buffer = static_cast<Timestamp*>(raw);
182
183 for (int64_t sequence_number = begin_sequence_number_;
184 sequence_number < end_sequence_number_; ++sequence_number) {
185 new_buffer[sequence_number & new_capacity_minus_1] =
186 arrival_times_[sequence_number & capacity_minus_1_];
187 }
188 arrival_times_.reset(new_buffer);
189 capacity_minus_1_ = new_capacity_minus_1;
190 }
191
192 } // namespace webrtc
193